Research On The Path Planning Algorithm Of Mobile Elements In Wireless Sensor Network Based On Halin Graph

Wireless Sensor Networks (WSN) consists of a large number of sensor nodes, and they are often been deployed in harsh condition and inaccessible places, hence researchers have to face the challenges of limited energy. How to use the limited node energy to maximize the network performance and prolong the network lifetime is an issue that people generally concerned. After studying and analyzing the relevant literature of network lifetime optimization algorithms, we propose the path planning algorithm of mobile elements (ME) in WSN based on Halin graph (PPA-H), which use ME to gather data in sensing area, that can reduce the communication frequency between nodes, balance the energy consumption, and effectively extend the network lifetime.The design and implementation is as following:ⅰ) Firstly, dividing the sensing area into several sub-regions. The difference of nodes number in any two neighbor sub-regions is at most one, which can minimize the difference of each sub-region’s total energy consumption, and balance the energy consumption of all nodes to realize global optimum;ⅱ) Then according to the idea of Weber’s site, selecting a virtual rendezvous for each sub-region, and ensure that the distance from the rendezvous to each node is equal or approximately equal. Let the ME move to the sub-region to gather data, rather than transmission the data through multi-hop routing, can balance the energy consumption of all nodes to realize local optimum;ⅲ) Thirdly, mapping the rendezvous into a Halin graph. Let the base station (BS) be the root and rendezvous be the tree-node and leaf-node. According the idea of shrinking the Halin graph to solve the Traveling Salesman Problem (TSP), we can easily plan the shortest path of ME, which can minimize the delay and save the energy consumed in caching data and monitoring channel;ⅳ) Finally, we propose a cooperative path planning algorithm for multiple mobile elements (Multi-MEs). The solution is decompose the characteristic tree into several sub-trees with some adjustment to ensure that every sub-tree has the same weight, and each ME be responsible for a sub-tree, which can reduce network delay and prolong network lifetime further.At the end of this paper, the simulation experiments compared with GBME and RP-UGO on the Matlab simulation platform shows that PPA-H has better performance in various scenarios for it has concerned how to balance the energy consumption effectively.