Delay Guarantee Schemes For Low-Duty-Cycle Sensor Networks

Recent advances in wireless communication technologies, embedded computing, sensor technology, micro-electro-mechanical systems (MEMS) technology make Wireless Senor Networks (WSNs) a rapid growth in development. WSNs, made up of a large number of low-cost, low-power, and multi-function sensor nodes, are designed for monitoring tasks, such as battlefield surveillance, equipment supervision, intruder detection, and wildlife observation. Usually, sensor nodes in a WSN are battery-powered and it is difficult to recharge or replace batteries in harsh or hostile environment. It is well known that keeping nodes in sleep mode, i.e., letting them operate in low-duty-cycle mode, can effectively save energy at the cost of increased communication delays. Therefore, how to achieve real-time data delivery in a low-duty-cycle WSNs is a problem worth investigating.The main idea of this paper is to guarantee end-to-end communication delay by means of augmenting minimal number of active slots of the sensor nodes, which causes minimal extra power consumption to be expended. Through system modeling, we formulate a multi-objective optimization problem, which augments minimal number of active slots and keeps the end-to-end delay within the delay bound. In addition, an optimization algorithm based on Non-dominated Sorting Genetic Algorithm (NSGA-Ⅱ) is presented to solve the problem. Meanwhile, the idea of immune is introduced into the algorithm, which is realized by eliminating the initial active slot of each node before the genetic operation phase, and thus we can guarantee each node has at least one active slot in a duty cycle. In a linear network, dynamic programming (DP) can be used to recursively augment the node's active slot so that an optimized solution can be obtained. However, in a complex network with multiple crossing paths, the DP becomes an NP-hard problem. The proposed NSGA-Ⅱbased optimization algorithm, whose complexity is O(mN2) in which m is the number of objectives and N is the population size, is able to guarantee deliver data within delay bound in a large scale complex network. Finally, simulations are conducted in both linear and complex networks. Simulation results show that, in linear networks, the results obtained by the proposed algorithm are close to those obtained by DP. Furthermore, in complex networks, the proposed algorithm can remedy the shortcoming of DP and effectively solve the real-time delivery problem in low duty-cycle sensor networks.