Energy Conservation In Wireless Sensor Networks And Related Issues Of Graph

Since the prolonged exponential growth continues in the underlying semiconductor technology, recent technological advances have led to the emergence of small, low-power devices that integrate sensors with limited on-board processing and wireless communication capabilities, called sensor node. Pervasive networks of such sensor nodes open new perspectives for many potential applications, such as battle field surveillance, environment monitoring, machine failure diagnosis, biological detection, home security, smart spaces, inventory tracking, etc. A wireless sensor network (WSN) consists of multiple sensor nodes and each sensor can sense certain physical phenomena like light, temperature or vibrations around its location. The purpose of WSN is to process some high-level sensing tasks and report the data to the application.However, since the WSNs have to be self-configuration, self-adaptation, and self-management after the sensor nodes are deployed, several challenges emerge. Energy source provided for sensors, processors and antennas is usually battery cell, which is impossible to recharge during WSNs work. Minimizing energy consumption to prolong the system lifetime is one of major design objectives for WSNs. Another design objective is to guarantee the Quality-of-Service (QoS) for applications provided by WSNs. The application performance is often evaluated by the accuracy and latency of information obtained in wireless sensor networks. In this thesis, we focus our work on the problem of energy conservation with two Qos, coverage and efficient routing, respectively in WSNs.Chapter 1 introduce the emergence of wireless sensor networks and its characteristics according to which the new problems of wireless sensor networks arise compared with the traditional networks and wireless networks. We mainly consider three issues in this thesis, energy conservation, coverage and efficient routing. Energy conservation is the most significant problem in wireless sensor networks due to its limited energy source intuitively. The other two issues are usually combined with the energy conservation problem. The goal of coverage requirement is to have each location in the targeted physical space within sensing range of at least one sensor node. And efficient routing aims to solve the problem that the collected data are efficiently reported to end-users. We introduce several related works and conclude these researches concerning their various characteristics. And we explain the difference of our works compared with the previous works according to these characteristics. Furthermore, we introduce the basic definitions and notations of graph theory that we use frequently in this thesis.Chapter 2-4 present the problem of energy conservation with coverage. We address an application which monitors a set of targets with known locations by a set of sensor nodes in heterogeneous wireless sensor networks. We propose an efficient method toextend the network lifetime by splitting the sensor nodes into a maximal number of disjoint sets which are activated successively. Only the sensor nodes from the active sets are responsible for monitor all the targets as well as each activated set remains connected for data collection. We present the Maximum Disjoint Sets for Maintaining Coverage and Connectivity (MDS-MCC) problem, and we prove it is NP-complete. And we design an algorithm and present an efficient implementation of heuristic functions for this algorithm. Theoretical analysis and experimental evaluations are also presented to show the efficiency of our algorithm. For further studies, we consider the MDS-MCC problem under some specific conditions. We consider the wireless sensor networks satisfying that each node monitors one target or just for connection. We assume the wireless sensor network has l targets, and each is monitored by k sensor nodes. If k = 2 and the graph G corresponding to the wireless sensor network is (l+ max{1,l-4})-connected, or k≥3 and G is (l(k-1) + 1)-connected, then we can find k (the maximum number) disjoint sets each of which completely covers all the targets and remains connected to one of sinks. Furthermore, we continue this work and defines the working time of a node is exactly d times. An efficient approach is presented to organize the sensor nodes into different sets, each of which complete covers all the targets and remains connected to one of sinks. We show that it is NP-complete to find the maximum lifetime of the WSNs, even though the network satisfy some conditions of connectivity. An algorithm is designed to improve the lifetime of WSNs. Theoretical analysis and experimental evaluations are also presented.In chapter 5, present the efficient data routing problem for mobile tracking wireless sensor networks. We study the network lifetime maximization problem and the delay time minimization problem together related to routing problems in mobile tracking wireless sensor networks. To make both problems tractable, we have the assumption that each sensor node keeps working since it turns on. And we formulate the network lifetime maximization problem as maximizing the number of sensor nodes who don't turn on, and the delay time minimization problem as minimizing the routing path length, after achieving the required tracking tasks. Since we prove the problems are NP-complete and APX-complete, we propose three heuristic algorithms to solve them. And we present several experiments to show the advantages and disadvantages referring to the network lifetime and the delay time among these three algorithms on three models, random graphs, grids and hypercubes. Furthermore, we implement the distributed version of these algorithms.