Research On Node Deployment For Coverage And Con-Nectivity In Wireless Networks

In last decade, with the depth research of related technologies and the advancement in hardware, wireless networks, such as Wirelss Sensor Networks (WSNs) and WiMAX networks are deployed widely in practice and draw a mass attention from a broad range of applications. As fundamental problems in these wireless networks, node(sensor in WSNs, relay in WiMAX) deployment and coverage control are researched widely. The network deployment scheme significantly impacts the cost of construction of network, the quality of coverage, topology and routing protocols. Especially, it is assumed as a foundation for solving coverage problems. In order to achieve energy efficiency and cost, coverage control exploits node redundancy, node scheduling and density controlling to meet network quality requirement. For the purpose of improving coverage and connectivity with energy efficiency, this thesis studies several problems that involve minimum deployment and path planning issues. The main contributions of this dissertation are showed as follows.(1) In wireless sensor networks (WSNs), deterministic placement of sensors can achieve low cost, high quality in coverage and connectivity. Most existing works assume that the monitoring area is infinite or large enough so that the boundary effect can be ignored, which in practice leads to coverage holes. In order to detect and eliminate the boundary effect, extra deployment work is required which leads to high cost in human resources, materials and time. In this thesis, we propose a growth rings like deployment (GRLD) algorithm to achieve both coverage and connectivity without boundary effects. GRLD is designed to be suitable for different relationships of the communication radius and sensing radius of sensors. We prove that GRLD can guarantee full coverage of the area and connectivity of the network. Sensor density of GRLD is derived in theory to assess its efficiency and the accuracy is verified by simulation results. Extensive simulations are conducted to evaluate GRLD’s performance compared with existing popular deployment patterns, in terms of sensor density, efficiency on eliminating boundary effects and flexibility to different relationships of the communication radius and sensing radius of sensors.(2) Coverage of interest points and connectivity of the network are two main issues in the performance of wireless sensor networks (WSNs). With the emergence of mobile sensors, many researchers have exploited sensors’ mobility to improve the quality of coverage and connectivity. However, little attention has been paid to minimize sensor’s movement, which consumes the majority of a sensor’s limited energy. Since sensors have limited energy storage and their operations continue until their energy drains, movement of mobile sensors should be minimized to extend the lifetime of the network. This thesis studies how to deploy mobile sensors with minimum movement to form a WSN that provides both target coverage and network connectivity with minimum movement. We call this problem the mobile sensor deployment problem (MSD), which could be divided into two sub-problems, Target COVerage (TCOV) problem and Network CONnectivity (NCON) problem. For TCOV problem, we prove it is NP-complete. An extend Hungarian method is designed to get the optimal solution to the TCOV problem for a special case. Two heuristic algorithms, respectively based on clique partition and Voronoi diagram are proposed for general cases. For the NCON problem, we give an efficient solution based on the edge length constrained steiner tree. Analyses show that, our algorithms have low complexity and could enhance the robustness of WSNs to sensor failures. Extensive simulation results are presented to evaluate solutions, which exhibit superior performance in large-scale WSNs.(3) In WiMAX mesh networks based on IEEE802.16j, when transmission power of the base station (BS) and the number of radios and channels are settled, data rate at the subscriber (SS) is decided by the distance between the SS and its uplink relay station (RS). In this thesis, we study the problem of deploying a minimum number of RSs to satisfy all SSs’ distance requirements. Firstly, we translate it into a minimum clique partition problem, which is NP-complete. Based on SSs’ neighbor information and location information, we then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, rspectively. Simulationresults show that compared with the lateMIS and HS algorithms, MAXDCP uses23.8%fewer relays than MIS with the same time complexity, and GEOCP uses35%fewer relays than MIS in the same time and18.5%fewer relays than HS in much less time.(4) In mobile WiMAX networks with fixed relays (FRs), mobile users pass in and out the coverage zone of different FRs in different time. The user flows cause overload to the corresponding FR, therefore make user’s data rate decreased. In our work, mobile relays are adopted to patrol FRs, and play as temporary replays when they reach the FR. In order to relax this problem with the lowest deployment cost, we define Minimum Mobile Relay Patrol problem (MMRP), whose goal is to plan the minimum path of mobile relays to patrol FRs. The MMPR prolem is formulated as a Minimum Vertex-disjiont Path Cover problem (MVPC), which is P in DAG and NP-hard when the directed graph has cycles. Two heuristic algorithms are proposed based on Maximum Cardinality Bipartite Matching and Maximum Flow, respectively。In summary, this thesis focuses on node deployment to enhance the network performance, such as coverage and connectivity. Our research has academic and practical value for advancing the theory and practicability in wireless sensor networks.