Kei SAKAGUCHI Van Ky NGUYEN Yu TAO Gia Khanh TRAN Kiyomichi ARAKI
It is known that demand and supply power balancing is an essential method to operate power delivery system and prevent blackouts caused by power shortage. In this paper, we focus on the implementation of demand response strategy to save power during peak hours by using Smart Grid. It is obviously impractical with centralized power control network to realize the real-time control performance, where a single central controller measures the huge metering data and sends control command back to all customers. For that purpose, we propose a new architecture of hierarchical distributed power control network which is scalable regardless of the network size. The sub-controllers are introduced to partition the large system into smaller distributed clusters where low-latency local feedback power control loops are conducted to guarantee control stability. Furthermore, sub-controllers are stacked up in an hierarchical manner such that data are fed back layer-by-layer in the inbound while in the outbound control responses are decentralized in each local sub-controller for realizing the global objectives. Numerical simulations in a realistic scenario of up to 5000 consumers show the effectiveness of the proposed scheme to achieve a desired 10% peak power saving by using off-the-shelf wireless devices with IEEE802.15.4g standard. In addition, a small-scale power control system for green building test-bed is implemented to demonstrate the potential use of the proposed scheme for power saving in real life.
Training one-class support vector machines (one-class SVMs) involves solving a quadratic programming (QP) problem. By increasing the number of training samples, solving this QP problem becomes intractable. In this paper, we describe a modified Pegasos algorithm for fast training of one-class SVMs. We show that this algorithm is much faster than the standard one-class SVM without loss of performance in the case of linear kernel.
Takeshi KUBO Atsushi TAGAMI Teruyuki HASEGAWA Toru HASEGAWA
In forthcoming sensor networks, a multitude of sensor nodes deployed over a large geographical area for monitoring traffic, climate, etc. are expected to become an inevitable infrastructure. Clustering algorithms play an important role in aggregating a large volume of data that are produced continuously by the huge number of sensor nodes. In such networks, equal-sized multi-hop clusters which include an equal number of nodes are useful for efficiency and resiliency. In addition, scalability is important in such large-scale networks. In this paper, we mathematically design a decentralized equal-sized clustering algorithm using a partial differential equation based on the Fourier transform technique, and then design its protocol by discretizing the equation. We evaluated through simulations the equality of cluster sizes and the resiliency against packet loss and node failure in two-dimensional perturbed grid topologies.
Htoo HTOO Yutaka OHSAWA Noboru SONEHARA Masao SAKAUCHI
Searching for the shortest paths from a query point to several target points on a road network is an essential operation for several types of queries in location-based services. This search can be performed using Dijkstra's algorithm. Although the A* algorithm is faster than Dijkstra's algorithm for finding the shortest path from a query point to a target point, the A* algorithm is not so fast to find all paths between each point and the query point when several target points are given. In this case, the search areas on road network overlap for each search, and the total number of operations at each node is increased, especially when the number of query points increases. In the present paper, we propose the single-source multi-target A* (SSMTA*) algorithm, which is a multi-target version of the A* algorithm. The SSMTA* algorithm guarantees at most one operation for each road network node, and the searched area on road network is smaller than that of Dijkstra's algorithm. Deng et al. proposed the LBC approach with the same objective. However, several heaps are used to manage the search area on the road network and the contents in each heap must always be kept the same in their method. This operation requires much processing time. Since the proposed method uses only one heap, such content synchronization is not necessary. The present paper demonstrates through empirical evaluations that the proposed method outperforms other similar methods.
Hidenori WATANABE Shogo MURAMATSU
This work proposes an exponential computation with low-computational complexity and applies this technique to the expectation-maximization (EM) algorithm for Gaussian mixture model (GMM). For certain machine-learning techniques, such as the EM algorithm for the GMM, fast and low-cost implementations are preferred over high precision ones. Since the exponential function is frequently used in machine-learning algorithms, this work proposes reducing computational complexity by transforming the function into powers of two and introducing a look-up table. Moreover, to improve efficiency the look-up table is scaled. To verify the validity of the proposed technique, this work obtains simulation results for the EM algorithm used for parameter estimation and evaluates the performances of the results in terms of the mean absolute error and computational time. This work compares our proposed method against the Taylor expansion and the exp( ) function in a standard C library, and shows that the computational time of the EM algorithm is reduced while maintaining comparable precision in the estimation results.
Qing LIU Tomohiro ODAKA Jousuke KUROIWA Hisakazu OGURA
An artificial fish swarm algorithm for solving symbolic regression problems is introduced in this paper. In the proposed AFSA, AF individuals represent candidate solutions, which are represented by the gene expression scheme in GEP. For evaluating AF individuals, a penalty-based fitness function, in which the node number of the parse tree is considered to be a constraint, was designed in order to obtain a solution expression that not only fits the given data well but is also compact. A number of important conceptions are defined, including distance, partners, congestion degree, and feature code. Based on the above concepts, we designed four behaviors, namely, randomly moving behavior, preying behavior, following behavior, and avoiding behavior, and present their respective formalized descriptions. The exhaustive simulation results demonstrate that the proposed algorithm can not only obtain a high-quality solution expression but also provides remarkable robustness and quick convergence.
Kazuo MOROKUMA Atsushi TAKEMOTO Yoshio KARASAWA
We propose a novel propagation measurement scheme for terrestrial TV signal indoor reception based on a virtual array technique. The system proposed in this paper carries out two-branch recording of target signals and the reference signal. By using the signal phase reference in the reference signal, we clarify the spatial propagation characteristics obtained from the two-dimensional virtual array outputs. Outdoor measurements were performed first to investigate the validity of the proposed measurement system. The results confirm its effectiveness in accurately determining the direction-of-arrival (DOA). We then investigated the propagation characteristics in an indoor environment. The angular spectrum obtained showed clear wave propagation structure. Thus, our proposed system is promising as a very accurate measurement tool for indoor propagation analysis.
Yosuke SUGIURA Arata KAWAMURA Youji IIGUNI
This paper proposes a new adaptive comb filter which automatically designs its characteristics. The comb filter is used to eliminate a periodic noise from an observed signal. To design the comb filter, there exists three important factors which are so-called notch frequency, notch gain, and notch bandwidth. The notch frequency is the null frequency which is aligned at equally spaced frequencies. The notch gain controls an elimination quantity of the observed signal at notch frequencies. The notch bandwidth controls an elimination bandwidth of the observed signal at notch frequencies. We have previously proposed a comb filter which can adjust the notch gain adaptively to eliminate the periodic noise. In this paper, to eliminate the periodic noise when its frequencies fluctuate, we propose the comb filter which achieves the adaptive notch gain and the adaptive notch bandwidth, simultaneously. Simulation results show the effectiveness of the proposed adaptive comb filter.
Three dimensional integration using Through-Silicon Vias (TSVs) offers short inter-layer interconnects and higher packing density. In order to take advantage of these attributes, a novel hybrid 3D NoC-Bus architecture is proposed in the paper. For vertical link, a Fake Token Bus architecture is elaborated, which utilizes the bandwidth efficiently by updating token synchronously. Based on this bus architecture, a methodology of hybrid 3D NoC-Bus design is introduced. The network hybridizes with the bus in vertical link and distributes long links of the full connected network into different layers, which achieves a network with a diameter of only 3 hops and limited radix. In addition, a congestion-aware routing algorithm applied to the hybrid network is proposed. The algorithm routes packets in horizontal firstly when the bus is busy, which balances the communication and reduces the possibility of congestion. Experimental results show that our network can achieve a 34.4% reduction in latency and a 43% reduction in power consumption under uniform random traffic and a 36.9% reduction in latency and a 48% reduction in power consumption under hotspot traffic over regular 3D mesh implementations on average.
Gina KWON Keum-Cheol HWANG Joon-Young PARK Seon-Joo KIM Dong-Hwan KIM
A hybrid approach for the synthesis of square thinned arrays with low sidelobes is presented. The proposed method combines the advantages of a genetic algorithm and combinatorial technique-cyclic difference sets (CDSs). The peak sidelobe level (PSL) and the thinning factor are numerically evaluated to show the effectiveness and reliability of the proposed hybrid method. In the proposed GA-enhanced square arrays with the DS and the best CDS, reductions of the PSL, of 4.16 dB and 2.45 dB, respectively, were achieved as compared to the results of conventional rectangular DS and CDS arrays.
Rie SUZUKI Tsubasa MARUYAMA Hao SAN Kazuyuki AIHARA Masao HOTTA
In this paper, a robust cyclic ADC architecture with β-encoder is proposed and circuit scheme using switched-capacitor (SC) circuit is introduced. Different from the conventional binary ADC, the redundancy of proposed cyclic ADC outputs β-expansion code and has an advantage of error correction. This feature makes ADC robust against the offset of comparator capacitor mismatch and finite DC gain of amplifier in multiplying-DAC (MDAC). Because the power penalty of high-gain wideband amplifier and the required accuracy of circuit elements for high resolution ADC can be relaxed, the proposed architecture is suitable for deep submicron CMOS technologies beyond 90 nm. We also propose a β-value estimation algorithm to realize high accuracy ADC based on β-expansion. The simulation results show the effectiveness of proposed architecture and robustness of β-encoder.
Fused Blocked Pattern Matching is a kind of approximate matching based on Blocked Pattern Matching, and can be used in identification of fused peptides in tumor genomes. In this paper, we propose a new algorithm for fused blocked pattern matching. We give a comparison between Julio's solution and ours, which shows our algorithm is more efficient.
This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.
Zhi DENG Huaxi GU Yingtang YANG Hua YOU
In this paper, an energy- and traffic-balance-aware mapping algorithm from IP cores to nodes in a network is proposed for application-specific Network-on-Chip(NoC). The multi-objective optimization model is set up by considering the NoC architecture, and addressed by the proposed mapping algorithm that decomposes mapping optimization into a number of scalar subproblems simultaneously. In order to show performance of the proposed algorithm, the application specific benchmark is applied in the simulation. The experimental results demonstrate that the algorithm has advantages in energy consumption and traffic balance over other algorithms.
We propose a novel network traffic matrix decomposition method named Stable Principal Component Pursuit with Frequency-Domain Regularization (SPCP-FDR), which improves the Stable Principal Component Pursuit (SPCP) method by using a frequency-domain noise regularization function. An experiment demonstrates the feasibility of this new decomposition method.
Toshiaki SHIOTA Kazuki NAKAGAMI Takao NISHITANI
A novel shadow removal approach is proposed by using block-wise transform domain shadow detection. The approach is based on the fact that the spatial frequency distributions on normal background areas and those under casted shadows from foreground objects are the same. The proposed approach is especially useful for silhouette extraction by using the Gaussian Mixture background Model (GMM) foreground segmentation in the transform domain, because the frequency distribution has already been calculated in the foreground segmentation. The stable shadow removal is realized, due to the transform domain implementation.
Myung-Ho PARK Ki-Gon NAM Jin Seok KIM Dae Hyun YUM Pil Joong LEE
With the increased deployment of wireless sensor networks (WSNs) in location-based services, the need for accurate localization of sensor nodes is gaining importance. Sensor nodes in a WSN localize themselves with the help of anchors that know their own positions. Some anchors may be malicious and provide incorrect information to the sensor nodes. In this case, accurate localization of a sensor node may be severely affected. In this study, we propose a secure and lightweight localization method. In the proposed method, uncertainties in the estimated distance between the anchors and a sensor node are taken into account to improve localization accuracy. That is, we minimize the weighted summation of the residual squares. Simulation results show that our method is very effective for accurate localization of sensor nodes. The proposed method can accurately localize a sensor node in the presence of malicious anchors and it is computationally efficient.
Given a graph G = (V,E) together with a nonnegative integer requirement on vertices r:V Z+, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E - M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721n) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306k)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not.
Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI Yoshiyuki KARUNO
In this paper, we consider a problem of simultaneously optimizing a sequence of graphs and a route which exhaustively visits the vertices from each pair of successive graphs in the sequence. This type of problem arises from repetitive routing of grasp-and-delivery robots used in the production of printed circuit boards. The problem is formulated as follows. We are given a metric graph G*=(V*,E*), a set of m+1 disjoint subsets Ci ⊆ V* of vertices with |Ci|=n, i=0,1,...,m, and a starting vertex s ∈ C0. We seek to find a sequence π=(Ci1, Ci2, ..., Cim) of the subsets of vertices and a shortest walk P which visits all (m+1)n vertices in G* in such a way that after starting from s, the walk alternately visits the vertices in Cik-1 and Cik, for k=1,2,...,m (i0=0). Thus, P is a walk with m(2n-1) edges obtained by concatenating m alternating Hamiltonian paths between Cik-1 and Cik, k=1,2,...,m. In this paper, we show that an approximate sequence of subsets of vertices and an approximate walk with at most three times the optimal route length can be found in polynomial time.
Masashi KIYOMI Toshiki SAITOH Ryuhei UEHARA
PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n4(n+m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n-1 vertices and O(n2) edges, the input size is O(n3) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.