Wireless sensor nodes are becoming more and more common in various settings and require a long battery life for better maintainability. Since most sensor nodes are powered by batteries, energy efficiency is a critical problem. In an experiment, we observed that when peak power consumption is high, battery voltage drops quickly, and the sensor stops working even though some useful charge remains in the battery. We propose three off-line algorithms that extend battery life by scheduling sensors' execution time that is able to reduce peak power consumption as much as possible under a deadline constraint. We also developed a simulator to evaluate the effectiveness of these algorithms. The simulation results showed that one of the three algorithms dramatically can extend battery life approximately three time as long as in simultaneous sensor activation.

A non-regular tree T with a prescribed branching sequence (s1,s2,...,sn) is a rooted and ordered tree such that its internal nodes are numbered from 1 to n in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n2) time and O(n2+nSn-1) time, respectively, provided a preprocessing takes O(n2Sn-1) time and space in advance, where .

Dichotomous coordinate descent (DCD) iterations method has been proposed for adaptive feedback cancellation, which uses a fixed number of iterations and a fixed amplitude range. In this paper, improved DCD algorithms are proposed, which substitute the constant number of iterations and the amplitude range with a variable number of iterations(VI) and/or a variable amplitude range(VA). Thus VI-DCD, VA-DCD and VIA-DCD algorithms are obtained. Computer simulations are used to compare the performance of the proposed algorithms against original DCD algorithm, and simulation results demonstrate that significant improvements are achieved in the convergence speed and accuracy. Another notable conclusion by further simulations is that the proposed algorithms achieve superior performance with a real speech segment as the input.

Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive number, called the supply or demand. Each demand vertex v must be supplied an amount of “power,” equal to the demand of v, from exactly one supply vertex through edges in T. Each edge is assigned a positive number called the capacity. One wishes to partition T into subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and the power flow through each edge is no more than capacity of the edge. The “partition problem” is a decision problem to ask whether T has such a partition. The “maximum partition problem” is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.

A rectangular drawing is a plane drawing of a graph in which every face is a rectangle. Rectangular drawings have an application for floorplans, which may have a huge number of faces, so compact code to store the drawings is desired. The most compact code for rectangular drawings needs at most 4f-4 bits, where f is the number of inner faces of the drawing. The code stores only the graph structure of rectangular drawings, so the length of each edge is not encoded. A grid rectangular drawing is a rectangular drawing in which each vertex has integer coordinates. To store grid rectangular drawings, we need to store some information for lengths or coordinates. One can store a grid rectangular drawing by the code for rectangular drawings and the width and height of each inner face. Such a code needs 4f-4 + f⌈log W⌉ + f⌈log H⌉ + o(f) + o(W) + o(H) bits*, where W and H are the maximum width and the maximum height of inner faces, respectively. In this paper we design a simple and compact code for grid rectangular drawings. The code needs 4f-4 + (f+1)⌈log L⌉ + o(f) + o(L) bits for each grid rectangular drawing, where L is the maximum length of edges in the drawing. Note that L ≤ max{W,H} holds. Our encoding and decoding algorithms run in O(f) time.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.