Shunta TERUI Katsuhisa YAMANAKA Takashi HIRAYAMA Takashi HORIYAMA Kazuhiro KURITA Takeaki UNO
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.
In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1) × (n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n × 2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 20n × 16n grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 10n × 5n grid if T(G) has exactly five leaves. We also present a linear-time algorithm to find such a drawing.
Hiroshi FUJIWARA Masaya KAWAGUCHI Daiki TAKIZAWA Hiroaki YAMAMOTO
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.
We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent.
For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings.
Takashi YAMAZOE Jinyu TANG Gin INOUE Kenji SUGIYAMA
HDR video is possible to display the maximum 1200% luminance, however, it is limited in SDR display. In this study, we expand high luminance area considering with perceptual performance to improve a presentation performance of HDR video in the SDR display. As results of objective experiments, it is recognized that the proposed method can improve the presentation performance maximally 0.8dB in WPSNR.
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.
Veeramani KARTHIKA Suresh JAGANATHAN
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.
Jiao DU Ziyu CHEN Le DONG Tianyin WANG Shanqi PANG
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.
Hideaki TAKAHASHI Hisashi ONOZAWA Satish K. Mikko A. UUSITALO
6G research has been extensively conducted by individual organizations as well as pre-competitive joint research initiatives. One of the joint initiatives is the Hexa-X European 6G flagship project. This paper shares the up-to-date deliverables through which Hexa-X is envisioning the 6G era. The Hexa-X deliverables presented in this paper encompass the overall 6G vision, use cases and technical enablers. The latest deliverables on tenets of 6G architectural design and central pillars of technical enablers are presented. In conclusion, the authors encourage joint research and PoC collaboration with Japanese industry, academia and research initiatives for the potential technical enablers presented in this paper, aimed at global harmonization towards 6G standards.
Ryo TAKAHASHI Hidenori MATSUO Sijie XIA Qiang CHEN Fumiyuki ADACHI
Cell-free massive MIMO (CF-mMIMO), which cooperatively utilizes a large number of antennas deployed over a communication area, has been attracting great attention as an important technology for realizing 5G-advanced and 6G systems. Recently, to ensure system scalability and mitigate inter-user interference in CF-mMIMO, a user-centric (UC) approach was investigated. In this UC approach, user-centric antenna-sets are formed by selecting appropriate antennas for each user, and postcoding is applied to reduce the strong interference from users whose antenna-sets overlap. However, in very high user density environments, since the number of interfering users increases due to increased overlapping of antenna-sets, the achievable link capacity may degrade. In this paper, we propose a user-cluster-centric (UCC) approach, which groups neighborhood users into a user-cluster and associates the predetermined number of antennas to this user-cluster for spatial multiplexing. We derive the uplink postcoding weights and explain the effectiveness of the proposed UCC approach in terms of the computational complexity of the weight computation. We also compare the uplink user capacities achievable with UC and UCC approaches by computer simulation and clarify situations where the UCC approach is effective. Furthermore, we discuss the impact of the number of interfering users considered in the zero-forcing and minimum mean square error postcoding weight computation on the user capacity.
Mitsuru UESUGI Yoshiaki SHINAGAWA Kazuhiro KOSAKA Toru OKADA Takeo UETA Kosuke ONO
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.
Shinya HORIMOTO Fujun HE Eiji OKI
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.
Kengo TAJIRI Ryoichi KAWAHARA Yoichi MATSUO
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.
Daiki MITAMURA Mamoru SAWAHASHI Yoshihisa KISHIYAMA
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.
Tadayoshi ENOMOTO Nobuaki KOBAYASHI
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.
A fully analog pipelined deep neural network (DNN) accelerator is proposed, which is constructed by using pipeline registers based on master-slave switched capacitors. The idea of the master-slave switched capacitors is an analog equivalent of the delayed flip-flop (D-FF) which has been used as a digital pipeline register. To estimate the performance of the pipeline register, it is applied to a conventional DNN which performs non-pipeline operation. Compared with the conventional DNN, the cycle time is reduced by 61.5% and data rate is increased by 160%. The accuracy reaches 99.6% in MNIST classification test. The energy consumption per classification is reduced by 88.2% to 0.128µJ, achieving an energy efficiency of 1.05TOPS/W and a throughput of 0.538TOPS in 180nm technology node.
Kosuke MURAKAMI Takahiro KASAMA Daisuke INOUE
Since the outbreak of IoT malware “Mirai,” several incidents have occurred in which IoT devices have been infected with malware. The malware targets IoT devices whose Telnet and SSH services are accessible from the Internet and whose ID/Password settings are not strong enough. Several IoT malware families, including Mirai, are also known that restrict access to Telnet and other services to keep the devices from being infected by other malware after infection. However, tens of thousands of devices in Japan can be still accessed Telnet services over the Internet according to network scan results. Does this imply that these devices can avoid malware infection by setting strong enough passwords, and thus cannot be used as a stepping stone for cyber attacks? In February 2019, we initiated the National Operation Toward IoT Clean Environment (NOTICE) project in Japan to investigate IoT devices with weak credentials and notify the device users. In this study, we analyze the results of the NOTICE project from February 2021 to May 2021 and the results of the large-scale darknet monitoring to reveal whether IoT devices with weak credentials are infected with malware or not. Moreover, we analyze the IoT devices with weak credentials to find out the factors that prevent these devices from being infected with malware and to assess the risk of abuse for cyber attacks. From the results of the analysis, it is discovered that approximately 2,000 devices can be easily logged in using weak credentials in one month in Japan. We also clarify that no device are infected with Mirai and its variants malware due to lack of functions used for malware infection excluding only one host. Finally, even the devices which are logged in by NOTICE project are not infected with Mirai, we find that at least 80% and 93% of the devices can execute arbitrary scripts and can send packets to arbitrary destinations respectively.
Takashi NORIMATSU Yuichi NAKAMURA Toshihiro YAMAUCHI
Two problems occur when an authorization server is utilized for a use case where a different security profile needs to be applied to a unique client request for accessing a distinct type of an API, such as open banking. A security profile can be applied to a client request by using the settings of an authorization server and client. However, this method can only apply the same security profile to all client requests. Therefore, multiple authorization servers or isolated environments, such as realms of an authorization server, are needed to apply a different security profile. However, this increases managerial costs for the authorization server administration. Moreover, new settings and logic need to be added to an authorization server if the existing client settings are inadequate for applying a security profile, which requires modification of an authorization server's source code. We aims to propose the policy-based method that resolves these problems. The proposed method does not completely rely on the settings of a client and can determine an applied security profile using a policy and the context of the client's request. Therefore, only one authorization server or isolated environment, such as a realm of an authorization server, is required to support multiple different security profiles. Additionally, the proposed method can implement a security profile as a pluggable software module. Thus, the source code of the authorization server need not be modified. The proposed method and Financial-grade application programming interface (FAPI) security profiles were implemented in Keycloak, which is an open-source identity and access management solution, and evaluation scenarios were executed. The results of the evaluation confirmed that the proposed method resolves these problems. The implementation has been contributed to Keycloak, making the proposed method and FAPI security profiles publicly available.