Studies On Path Planning Method For Water Surface Mobile Sink Based On Voronoi Diagram And Bipartite Graph

In recent years, with the development of related research, Wireless Sensor Networks (WSNs) have become a very important information technology which is widely used in the areas of production, monitoring, communication and military. As an important branch of WSNs, sensors in Surface Sensor Networks (SSNs) are sparsely deployed. So it is difficult to gather sensors’ data by multi-hop routing. At present, it is an effective data gathering method by the mobile sink travelling in the networks. How to plan an optimal path for the mobile sink becomes a key problem in SSNs. In this thesis, we study in this key problem and propose a path planning method for the water surface mobile sink based on Voronoi Diagram and bipartite graph. Extensive experiments demonstrate that the proposed method can effectively plan the path for the mobile sink to gather all sensors’ data with several advantages of short path, high energy efficiency, and balanced energy consumption among sensors.The main problem studied and major innovations in this thesis are summarized as follows:(1) Voronoi Diagram theory is introduced into the path planning for the mobile sink in SSNs. The SSNs are modeled by Voronoi Diagram theory. And the Voronoi Diagram is constructed based on sensor nodes to provide a series of data gathering "candidate vertexes", which are Voronoi vertexes. Compared with traditional methods to gather data nearby sensor nodes, an innovative method for the mobile sink to gather data at Voronoi vertexes is designed in this thesis. Theoretical and experimental results show that sensors’ energy consumptions are balanced when the mobile sink collects their data at Voronoi vertexes.(2) Bipartite Graph and Dominating Set are introduced into the Voronoi Diagram model. The Bipartite Graph is constructed by the relationship between Voronoi vertexes and sensor nodes. Then the "domination" is defined. So the dominating relationship between sensor nodes and Voronoi vertexes can be described by the Bipartite Graph. Drawing lessons from the theory of Dominating Set, the "minimal effective dominating set" is defined. And the accurate solution and quick approximate solution for the minimal effective dominating set are both given. So the path planning for the mobile sink becomes a Traveling Salesman Problem based on the minimal effective dominating set. Finally, a large number of simulation experiments verify the validity and advancement of this method.The thesis has some reference value to improve the theoretical and engineering level of the path planning for the water surface mobile sink.