Research On Lifetime Optimization In Wireless Sensor Networks

Wireless sensor network is considered a promising infrastructure to change the physical environment, and hence our life in this environment. It has been an active research area in the past few years. Wireless sensor networks are presumed to be deployed using battery-powered stationary sensor nodes equipped with sensing, computing and wireless communicating modules. In a broad range of potential applications, inexpensive sensors can be embedded into buildings or scattered into spaces to collect, process and send out relevant information for various civilian or military purposes.Since sensors have significant power constraints, and the radio transceiver typically consumes more energy than any other hardware component onboard a sensor node, design of energy efficient communication algorithms is of great importance. For prolonging system lifetime by reducing the energy consumed by communications, various algorithms have been proposed. They can be categorized into two families: lifetime maximization and sleeping scheduling. Lifetime maximization problem focuses on how to balance the energy consumption of data transmission so that the system lifetime that the first"die-out"node lives could be prolonged as much as possible. However, sleeping scheduling focuses on how to force as many as possible nodes to go to sleep so that the energy consumed by idle listening could be conserved. A promising perspective on combining lifetime maximization and sleeping scheduling should be taken to prolong system lifetime.The data flow in a sensor network is very different from data flow in an ordinary network, and therefore the common protocols used in the Internet or Manet paradigm are inadequate to handle. Such special data flow poses novel challenges and also chances in designing efficient routing algorithms in sensor networks. That is to perform global optimization in traffic planning to prolong system lifetime as much as possible.We abstract a kind of multi-source-to-multi-sink communication lifetime maximization problem of non-power-controllable sensor networks into a kind of one-source-to-one-sink single-commodity flow maximization problem on a directed graph with arc and vertex capacities. Based on this model, three polynomial-time algorithms VABA, FAT and ADALM are presented to estimate whether a sensor network can live a given lifetime or not. Through binary search, these algorithms can find out the maximum lifetime and the best traffic planning under a given precision.Precious sensor node battery power can be saved by power control measures that can dynamically adjust the radio transmission range of a sensor node. Therefore we extend VABA to I-VABA in order to handle the lifetime maximization problem of power-controllable sensor networks. In particular, a heuristic algorithm AOC is presented to perform circle flow adjustment when I-VABA is blocked so that additional flow augmentations could be achieved. Compared with other heuristic algorithms, AOC achieves a higher or a similar approximation ratio but uses a much fewer run time.In sensor networks, the communication cost is often several orders of magnitude higher than the computation cost. So in-network data aggregation is considered an effective technique for energy conservation. In addition, QoS constraints are also important for providing congestion-free and latency-bounded data transmission service. We formulize such kind of lifetime maximization problem with considering data aggregation and QoS constraints as non-linear programming and propose a genetic algorithm GAMSN to solve it. GAMSN takes unit-flow-rate paths as genes and constructs a chromosome for each source node by a set of unit paths that originated from it. In particular, a parameter named"PREC"is set to serve the purpose of control the number of genes of a chromosome and hence the precision in which GAMSN could approximate the maximum lifetime. This approach has a reasonable time complexity and performs well in experiments.However, a major drawback of GAMSN is the additional individual diversity overhead resulted from increased PREC. With the increase of individual diversity, much greater population size is needed to ensure that there are some good individuals in a randomly generated initial population. Therefore, the increase of individual diversity will adversely impact the algorithm effectiveness. We propose a diversity-controllable genetic algorithm DCGA as an improvement of GAMSN to address this problem. DCGA uses two methods to control the individual diversity. The first is to control the number of genes in a chromosome through parameter PREC. The second is to control the type of genes by limiting the hop counts of randomly generated unit paths. DCGA gains remarkable performance improvement under high PREC by diversity control.Compared with a kind of algorithms which use multi-commodity approximate methods to solve programming problems, DCGA can also achieve a high approximation ratio but has lower time complexity. Compared with a kind of heuristic algorithms, DCGA achieves a higher approximation ratio with a little increased order of computations. To the best of our knowledge, GAMSN and it diversity-controllable improvement DCGA are the first algorithms that can solve multi-commodity lifetime maximization problems of power-controllable sensor networks with data aggregation and QoS constraints.Synchronized periodic duty cycling of the sensor nodes is suggested to minimize the energy consumption of idle listening. Each node follows a periodic cycle of active/sleep radio states. During the sleep period, the radio is completely turned off, and during the active period, the radio is turned on and all generated data is send to the sink. So the important problem is to reduce the length of active period as much as possible. In sensor networks with data aggregation, an intermediate node must to wait for all incoming data to arrive before it can perform data aggregation and send the aggregated data to the downstream nodes. If an upstream node decides to send it outgoing data to another node firstly, the current node has to wait for it and put off its data aggregation and out sending. Consequently, all nodes that wait for incoming data from the current node have to put off their process as the same. Such kind of wait results in significant delay and prolong the time that is needed to send all data generated in a periodic of active/sleep cycle to the sink. Therefore it is very important to schedule the transmission order on each node to reduce the wait time and consequently the length of active period. We call this traffic scheduling and propose a heuristic algorithm named PYTMS based on the adjustments on critical paths. It can reduce the active period remarkably.