Double Barrier Coverage And SparseDT Topology Control Protocol In Dense Sensor Networks

In large scale sensor networks, system energy and network congestion are always the key constraint of well functioning. Out of cost consideration, sensors are generally deployed randomly and statically in a large scale network, so that there might be a lot of redundant sensors. Topology control aims to find out these redundant sensors and schedule them out to conserve energy. Along with the coverage and connectivity issues, a topology should have planar, sparse, bounded degree or well-spanning structure. In this thesis, we concentrate on the topology control problem and the barrier coverage problem in large scale static sensor network which is randomly deployed in monitoring region. Following is the abstract of these works:(1) Bring forward a new planar graph, named "Sparse Delaunay Triangulation", or SparseDT in short. Some nice attributes are proved including asymptotic connectivity and better network dilation, and a distributed algorithm is given to construct the SparseDT structure.(2) Bring forward the "Double Barrier Coverage" problem. That is, a sensor network is said to provide double barrier coverage if any target crossing the monitoring region will be detected by two sensors simultaneously at some point on its path. A simple and efficient distributed algorithm is given based on the SparseDT structure, the number of active sensors to construct the barrier network is analyzed, and a centralized algorithm is given to solve the similar K-Barrier Coverage problem.(3) Bring forward a simple topology control protocol, named "Convergent SparseDT". It could control the density of active sensors, guarantee the asymptotic coverage and connectivity, and reduce greatly the communicating and computing overhead to maintain the topology. Convergence and run time performanceof this protocol are analyzed statistically. (4) Convergent SparseDT protocol and Double Barrier Coverage algorithm are implemented on NS2 simulator. Run time energy consumption and network congestion problem are considered, message passing procedure and node scheduling scheme are designed, and a simple sensing model is used to patch NS2 simulator. Simulation results verify the theoretical analysis perfectly.Main contribution and innovation in this thesis are:(1) The Double Barrier Coverage problem is proposed at the first time. Compared with method of constructing barrier with paths, a 2-covered barrier could detect effectively target crossing the region at high speed.(2) The SparseDT topology conserves nice network attributes and could be easily constructed. Compared with most distributed Deluany triangulation, it reduces greatly the communicating and computing overhead.(3) Potential theory and virtual potential field technique are adopted in the Convergent SparseDT topology control protocol. It is an experiment in applying the continuous and dynamic optimization technique in the topology control of discrete and static sensor networks.