Node Deployment Algorithm Design For Special Applications

In Wireless Sensor Networks(WSN),the node deployment is concerned with the effectiveness of sensing the interested region,the deployment cost,and the elimination of coverage holes.The effective node deployment is important to guarantee the quality of service in WSNs,and thus it needs to be addressed when considering the practical application of wireless sensor network system.Most existing node deployment algorithms assume that the sensing model is ideal for a perfect circle,there are no obstacles,the application environment is two-dimensional,or the sensing range of node is omni-directional.However,these assumptions are generally impractical in WSNs.For example,the sensing model of sensor node is usually not a perfect circle;there exist some obstacles;the application environment is three-dimensional;the sensing range is directional and so on.To this end,this thesis aims at proposing node deployment algorithms for practical WSNs.The main contributions of this thesis are as follows:(1)For the WSN where the sensing model of sensors is not a perfect circle,we propose the Deployment Algorithm with Irregular Sensing Range.(DAWISR).In particular,the proposed algorithm works as follows.First of all,we divide the deployed nodes into groups by Delaunay triangulation.Second,we deploy new nodes outside the center position to expand coverage area by the nature that three vertices of the triangle have the same distance to its circumcenter.Third,we further adjust the positions of newly deployed nodes according to the grid coverage around the circumcenters of triangles and the distance between circumcenters and vertices.Finally,to address the issue that it is not easy to choose the sensor nodes close to the boundary,we propose the "border reinforcement mechanism" and the "obtuse triangle TP-point optimization strategy"to increase coverage effectively.Simulation results show that the DAWISR algorithm can increase coverage to more than 90%through effectively using randomly deployed sensor nodes.Furthermore,the DAWISR algorithm can decrease the redundant sensor region,increase the coverage with a few number of nodes.(2)For the WSN in which there exist obstacles,we propose the Node Deployment Algorithm based on Delaunay Triangulation and Weight(NDADTW).This algorithm can maximize the sensing coverage ratio in the deployment area when the network connectivity is satisfied.First,the coverage holes near the boundaries of the deployment area and obstacles are eliminated by deploying sensor nodes along their contour.Then,possible positions of deploying nodes are generated by Delaunay triangulation.Finally,the deployment positions that maximize the sensing coverage ratio are determined based on the weighted mechanism of binary sensing model.Simulation results show that the coverage ratio of NDADTW algorithm,is 23%higher than the grid-based algorithm,and 10%higher than the random-based algorithm on average,when existing obstacles in the target area and deploying the same number of nodes.(3)For the WSN which applies to 3-dimensional environments such as building fire emergency rescue WSN,marine monitoring WSN,atmospheric monitoring WSN,we propose the Self-Deployment Algorithm based on Density Control in 3-Dimensional Space(SDADC).In particular,we first propose the node clustering algorithm for the 3-dimensional space by combining the traditional minimum ID clustering algorithm with 3-dimensional sensing model.We further propose the virtual force algorithm based on the 3-dimensional sensing model by applying the virtual force to formulate the interaction force among nodes and obstacles.At last,we find the method of moving nodes from high density area to low density area through the density control strategy.Specifically,the method achieves the synchronous node deployment through controlling the density of each node,and the distributed self-deployment through balancing the density in different areas.Simulation results indicate that in athe3-dimensional space with obstacles,the initial random deployment of nodes within a small area can rapidly move and eventually cover the entire space evenly with 82%of coverage.(4)For the directional WSN such as video surveillance system and radar surveillance system,we propose a time coverage model of rotatable and directional sensor to monitor objects and design a MGDCD(Modified Geometric Disk Cover Deployment)and a DOOP(Disk Overlap Optimization Deployment for deployment).The MGDCD algorithm calculates the disk area set by modified GDC,and the position and the number of deployed nodes by marking objects and cutting sector.By this doing,the MGDCD algorithm can cover the maximum number of objects by the minimum number of sensors.It is suitable for application scenarios when monitored objects are congregated or clustered distribution.The DOOP algorithm can apply to application scenarios when monitored objects are arbitrarily distributed by exploiting joint sector of the overlap between disks to save sensors.Simulation results show that the MGDCD algorithm and the DOOP algorithm can cover the maximum number of objects with the minimum number of sensor.In particular the MGDCD algorithm performs better when objects congregate at some locations,while the DOOP algorithm can reduce the number of sensors when objects are randomly distributed in the sensing field.According to four different WSN application environments,the new node deployment algorithms are proposed to improve the coverage of wireless sensor network.Simulation results show that the algorithms are feasible and obtain high coverage ratio,which Our work is significant for the node deployment in the practical application of wireless sensor networks.