We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2|ε(S)|)-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.

The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms.

Packet classification is used to determine the behavior of incoming packets in network devices according to defined rules. As it is achieved using a linear search on a classification rule list, a large number of rules will lead to longer communication latency. To solve this, the problem of finding the order of rules minimizing the latency has been studied. Misherghi et al. and Harada et al. have proposed a problem that relaxes to policy-based constraints. In this paper, we show that the Relaxed Optimal Rule Ordering (RORO) for the allowlist is NP-hard, and by reducing from this we show that RORO for the general rule list is NP-hard. We also propose a heuristic algorithm based on the greedy method for an allowlist. Furthermore, we demonstrate the effectiveness of our method using ClassBench, which is a benchmark for packet classification algorithms.

The CGL hash function is a provably secure hash function using walks on isogeny graphs of supersingular elliptic curves. A dominant cost of its computation comes from iterative computations of power roots over quadratic extension fields. In this paper, we reduce the necessary number of power root computations by almost half, by applying and also extending an existing method of efficient isogeny sequence computation on Legendre curves (Hashimoto and Nuida, CASC 2021). We also point out some relationship between 2-isogenies for Legendre curves and those for Edwards curves, which is of independent interests, and develop a method of efficient computation for 2e-th roots in quadratic extension fields.

High-performance deep learning-based object detection models can reduce traffic accidents using dashcam images during nighttime driving. Deep learning requires a large-scale dataset to obtain a high-performance model. However, existing object detection datasets are mostly daytime scenes and a few nighttime scenes. Increasing the nighttime dataset is laborious and time-consuming. In such a case, it is possible to convert daytime images to nighttime images by image-to-image translation model to augment the nighttime dataset with less effort so that the translated dataset can utilize the annotations of the daytime dataset. Therefore, in this study, a GAN-based image-to-image translation model is proposed by incorporating self-attention with cycle consistency and content/style separation for nighttime data augmentation that shows high fidelity to annotations of the daytime dataset. Experimental results highlight the effectiveness of the proposed model compared with other models in terms of translated images and FID scores. Moreover, the high fidelity of translated images to the annotations is verified by a small object detection model according to detection results and mAP. Ablation studies confirm the effectiveness of self-attention in the proposed model. As a contribution to GAN-based data augmentation, the source code of the proposed image translation model is publicly available at https://github.com/subecky/Image-Translation-With-Self-Attention

The existing target-dependent scalable image compression network can control the target of the compressed images between the human visual system and the deep learning based classification task. However, in its RNN based structure controls the bit-rate through the number of iterations, where each iteration generates a fixed size of the bit stream. Therefore, a large number of iterations are required at the high BPP, and fine-grained image quality control is not supported at the low BPP. In this paper, we propose a novel RNN-based image compression model that can schedule the channel size per iteration, to reduce the number of iterations at the high BPP and fine-grained bit-rate control at the low BPP. To further enhance the efficiency, multiple network models for various channel sizes are combined into a single model using the slimmable network architecture. The experimental results show that the proposed method achieves comparable performance to the existing method with finer BPP adjustment, increases parameters by only 0.15% and reduces the average amount of computation by 40.4%.

Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites.

Considering the growth of the IoT network, there is a demand for a decentralized solution. Incorporating the blockchain technology will eliminate the challenges faced in centralized solutions, such as i) high infrastructure, ii) maintenance cost, iii) lack of transparency, iv) privacy, and v) data tampering. Blockchain-based IoT network allows businesses to access and share the IoT data within their organization without a central authority. Data in the blockchain are stored as blocks, which should be validated and added to the chain, for this consensus mechanism plays a significant role. However, existing methods are not designed for IoT applications and lack features like i) decentralization, ii) scalability, iii) throughput, iv) faster convergence, and v) network overhead. Moreover, current blockchain frameworks failed to support resource-constrained IoT applications. In this paper, we proposed a new consensus method (WoG) and a lightweight blockchain framework (iLEDGER), mainly for resource-constrained IoT applications in a permissioned environment. The proposed work is tested in an application that tracks the assets using IoT devices (Raspberry Pi 4 and RFID). Furthermore, the proposed consensus method is analyzed against benign failures, and performance parameters such as CPU usage, memory usage, throughput, transaction execution time, and block generation time are compared with state-of-the-art methods.

In this paper, the notion of 2-tuples distribution matrices of the rotation symmetric orbits is proposed, by using the properties of the 2-tuples distribution matrix, a new characterization of 2-resilient rotation symmetric Boolean functions is demonstrated. Based on the new characterization of 2-resilient rotation symmetric Boolean functions, constructions of 2-resilient rotation symmetric Boolean functions (RSBFs) are further studied, and new 2-resilient rotation symmetric Boolean functions with prime variables are constructed.

This letter is devoted to constructing new Type-II Z-complementary pairs (ZCPs). A ZCP of length N with ZCZ width Z is referred to in short by the designation (N, Z)-ZCP. Inspired by existing works of ZCPs, systematic constructions of (2N+3, N+2)-ZCPs and (4N+4, 7/2N+4)-ZCPs are proposed by appropriately inserting elements into concatenated GCPs. The odd-length binary Z-complementary pairs (OB-ZCPs) are Z-optimal. Furthermore, the proposed construction can generate even-length binary Z-complementary pairs (EB-ZCPs) with ZCZ ratio (i.e. ZCZ width over the sequence length) of 7/8. It turns out that the PMEPR of resultant EB-ZCPs are upper bounded by 4.

Technology for sixth-generation (6G) mobile communication system is now being widely studied. A sub-Terahertz band is expected to play a great role in 6G to enable extremely high data-rate transmission. This paper has two goals. (1) Introduction of 6G concept and propagation characteristics of sub-Terahertz-band radio waves. (2) Performance evaluation of intelligent reflecting surfaces (IRSs) based on beamforming in a sub-Terahertz band for smart radio environments (SREs). We briefly review research on SREs with reconfigurable intelligent surfaces (RISs), and describe requirements and key features of 6G with a sub-Terahertz band. After that, we explain propagation characteristics of sub-Terahertz band radio waves. Important feature is that the number of multipath components is small in a sub-Terahertz band in indoor office environments. This leads to an IRS control method based on beamforming because the number of radio waves out of the optimum beam is very small and power that is not used for transmission from the IRS to user equipment (UE) is little in the environments. We use beams generated by a Butler matrix or a DFT matrix. In simulations, we compare the received power at a UE with that of the upper bound value. Simulation results show that the proposed method reveals good performance in the sense that the received power is not so lower than the upper bound value.

This paper proposes two full-digital receive beamforming (BF) methods for low-complexity and high-accuracy uplink signal detection via Gaussian belief propagation (GaBP) at base stations (BSs) adopting massive multi-input multi-output (MIMO) for open radio access network (O-RAN). In addition, beyond fifth generation mobile communication (beyond 5G) systems will increase uplink capacity. In the scenarios such as O-RAN and beyond 5G, it is vital to reduce the cost of the BSs by limiting the bandwidth of fronthaul (FH) links, and the dimensionality reduction of the received signal based on the receive BF at a radio unit is a well-known strategy to reduce the amount of data transported via the FH links. In this paper, we clarify appropriate criteria for designing a BF weight considering the subsequent GaBP signal detection with the proposed methods: singular-value-decomposition-based BF and QR-decomposition-based BF with the aid of discrete-Fourier-transformation-based spreading. Both methods achieve the dimensionality reduction without compromising the desired signal power by taking advantage of a null space of channels. The proposed receive BF methods reduce correlations between the received signals in the BF domain, which improves the robustness of GaBP against spatial correlation among fading coefficients. Simulation results assuming realistic BS and user equipment arrangement show that the proposed methods improve detection capability while significantly reducing the computational cost.

With the rapid increase in the amount of data communication in 5G networks, there is a strong demand to reduce the power of the entire network, so the use of highly power-efficient millimeter-wave (mm-wave) networks is being considered. However, while mm-wave communication has high power efficiency, it has strong straightness, so it is difficult to secure stable communication in an environment with blocking. Especially when considering use cases such as autonomous driving, continuous communication is required when transmitting streaming data such as moving images taken by vehicles, it is necessary to compensate the blocking problem. For this reason, the authors examined an optimum radio access technology (RAT) selection scheme which selects mm-wave communication when mm-wave can be used and select wide-area macro-communication when mm-wave may be blocked. In addition, the authors implemented the scheme on a prototype device and conducted field tests and confirmed that mm-wave communication and macro communication were switched at an appropriate timing.

This paper investigates a service deployment model for network function virtualization which handles per-flow priority to minimize the deployment cost. Service providers need to implement network services each of which consists of one or more virtual network functions (VNFs) with satisfying requirements of service delays. In our previous work, we studied the service deployment model with per-host priority; flows belonging to the same service, for the same VNF, and handled on the same host have the same priority. We formulated the model as an optimization problem, and developed a heuristic algorithm named FlexSize to solve it in practical time. In this paper, we address per-flow priority, in which flows of the same service, VNF, and host have different priorities. In addition, we expand FlexSize to handle per-flow priority. We evaluate per-flow and per-host priorities, and the numerical results show that per-flow priority reduces deployment cost compared with per-host priority.

This paper proposes a backup resource allocation model for virtual network functions (VNFs) to minimize the total allocated computing capacity for backup with considering the service delay. If failures occur to primary hosts, the VNFs in failed hosts are recovered by backup hosts whose allocation is pre-determined. We introduce probabilistic protection, where the probability that the protection by a backup host fails is limited within a given value; it allows backup resource sharing to reduce the total allocated computing capacity. The previous work does not consider the service delay constraint in the backup resource allocation problem. The proposed model considers that the probability that the service delay, which consists of networking delay between hosts and processing delay in each VNF, exceeds its threshold is constrained within a given value. We introduce a basic algorithm to solve our formulated delay-constraint optimization problem. In a problem with the size that cannot be solved within an acceptable computation time limit by the basic algorithm, we develop a simulated annealing algorithm incorporating Yen's algorithm to handle the delay constraint heuristically. We observe that both algorithms in the proposed model reduce the total allocated computing capacity by up to 56.3% compared to a baseline; the simulated annealing algorithm can get feasible solutions in problems where the basic algorithm cannot.

Machine learning (ML) has been used for various tasks in network operations in recent years. However, since the scale of networks has grown and the amount of data generated has increased, it has been increasingly difficult for network operators to conduct their tasks with a single server using ML. Thus, ML with edge-cloud cooperation has been attracting attention for efficiently processing and analyzing a large amount of data. In the edge-cloud cooperation setting, although transmission latency, bandwidth congestion, and accuracy of tasks using ML depend on the load balance of processing data with edge servers and a cloud server in edge-cloud cooperation, the relationship is too complex to estimate. In this paper, we focus on monitoring anomalous traffic as an example of ML tasks for network operations and formulate transmission latency, bandwidth congestion, and the accuracy of the task with edge-cloud cooperation considering the ratio of the amount of data preprocessed in edge servers to that in a cloud server. Moreover, we formulate an optimization problem under constraints for transmission latency and bandwidth congestion to select the proper ratio by using our formulation. By solving our optimization problem, the optimal load balance between edge servers and a cloud server can be selected, and the accuracy of anomalous traffic monitoring can be estimated. Our formulation and optimization framework can be used for other ML tasks by considering the generating distribution of data and the type of an ML model. In accordance with our formulation, we simulated the optimal load balance of edge-cloud cooperation in a topology that mimicked a Japanese network and conducted an anomalous traffic detection experiment by using real traffic data to compare the estimated accuracy based on our formulation and the actual accuracy based on the experiment.

This paper proposes a multiple code block transmission scheme using hierarchical modulation (HM) for a broadcast channel in the orthogonal frequency division multiplexing (OFDM) downlink. We investigate the average bit error rate (BER) performance of two-layer HM using 16 quadrature amplitude modulation (QAM) and three-layer HM using 64QAM in multipath Rayleigh fading channels. In multiple code block transmission using HM, the basic information bits are demodulated and decoded to all users within a cell that satisfy the bit error rate (BER) requirement. Hence, we investigate non-uniform QAM constellations to find one that suppresses the loss in the average BER of the basic information bits for HM to a low level compared to that using the original constellation in which only the basic information bits are transmitted while simultaneously minimizing the loss in the average BER of the secondary and tertiary information bits from the original constellations in which the information bits of the respective layers are transmitted alone. Based on the path loss equations in the Urban Macro and Rural Macro scenarios, we also investigate the maximum distance from a base station (BS) for the information bits of each layer to attain the required average received signal-to-noise power ratio (SNR) that achieves the average BER of 10-3.

To enhance safety and efficiency in the traffic environment, developing intelligent transportation systems (ITSs) is of paramount importance. In ITSs, roadside units (RSUs) are critical components that enable the environment awareness and connectivity via using radar sensing and communications. In this paper, we focus on RSUs with multiple radar systems. Specifically, we propose a parameter selection method of multiple radar systems to enhance the overall sensing performance. Furthermore, since different radars provide different sensing and tracking results, to benefit from multiple radars, we propose fusion algorithms to integrate the tracking results of different radars. We use two commercial frequency-modulated continuous wave (FMCW) radars to conduct experiments at Hsinchu city in Taiwan. The experimental results validate that our proposed approaches can improve the overall sensing performance.

We experimentally evaluated transmission characteristics of 120-GHz-band close-proximity wireless link that employs a split-ring resonator (SRR) millimeter-wave (MMW) absorber integrated on planar slot antennas in 120-GHz-band close-proximity wireless links. We fabricated the SRR MMW absorber made of a 0.28-μm-thick TaN film on a quartz substrate, and integrated it on planar single slot antennas. When the TaN SRRs are not integrated on the planar slot antennas, multiple reflections between the two antennas occur, and a >10-dB fluctuation of S21 at 100-140GHz is observed. When the TaN SRRs are integrated on the planar antennas, the fluctuation of S21 is suppressed to be 3.5dB at 100-140GHz. However, the transmittance of the close-proximity wireless link decreases by integrating TaN SRRs on the planar slot antenna because of reflection at the quartz substrate surface. The integration of the radiator that is composed of single SRR with two capacitors just above the slot antenna increased S21 by 3.5dB at 125GHz. We conducted a data transmission experiment over a close-proximity wireless link that employs radiator-and-TaN-SRR-integrated slot antennas for Tx and Rx, and succeeded to transmit 10-Gbit/s data over the close-proximity wireless link for the first time.

We developed a self-controllable voltage level (SVL) circuit and applied this circuit to a single-power-supply, six-transistor complementary metal-oxide-semiconductor static random-access memory (SRAM) to not only improve both write and read performances but also to achieve low standby power and data retention (holding) capability. The SVL circuit comprises only three MOSFETs (i.e., pull-up, pull-down and bypass MOSFETs). The SVL circuit is able to adaptively generate both optimal memory cell voltages and word line voltages depending on which mode of operation (i.e., write, read or hold operation) was used. The write margin (VWM) and read margin (VRM) of the developed (dvlp) SRAM at a supply voltage (VDD) of 1V were 0.470 and 0.1923V, respectively. These values were 1.309 and 2.093 times VWM and VRM of the conventional (conv) SRAM, respectively. At a large threshold voltage (Vt) variability (=+6σ), the minimum power supply voltage (VMin) for the write operation of the conv SRAM was 0.37V, whereas it decreased to 0.22V for the dvlp SRAM. VMin for the read operation of the conv SRAM was 1.05V when the Vt variability (=-6σ) was large, but the dvlp SRAM lowered it to 0.41V. These results show that the SVL circuit expands the operating voltage range for both write and read operations to lower voltages. The dvlp SRAM reduces the standby power consumption (PST) while retaining data. The measured PST of the 2k-bit, 90-nm dvlp SRAM was only 0.957µW at VDD=1.0V, which was 9.46% of PST of the conv SRAM (10.12µW). The Si area overhead of the SVL circuits was only 1.383% of the dvlp SRAM.