Research On Geographic Routing Algorithm Based On Planarization For Wireless Networks

With the rapid development of wireless communication technology, informationtechnology and wireless network nodes, wireless networks are becoming more andmore popular in various fields, represented by Ad-hoc. As a key issue of wirelessnetwork technology, routing protocols get more and more attention and research.Traditional routing protocols are mainly based on network topology, which makes themhave many congenital deficiencies in terms of scalability and overhead. On the otherhand, as wireless location technology becoming mature and wireless network nodesbeing powerful, many nodes themselves have the ability of geographical locationinformation awareness. With the aid of geographical location information, geographicrouting algorithms have congenital advantages over other routing algorithms, soresearch of geographic routing algorithms has important practical significance.After declaration of research background and prior conditions, this thesisintroduced some relevant theories on geographic routing algorithms based onplanarization, including greedy routing algorithm, face routing algorithm andplanarization algorithm. Greedy routing algorithm is the basic algorithm of geographicrouting algorithms. However, greedy routing algorithm may fail in voids, so facerouting algorithm can be used to get out of the voids. Since face routing algorithm needsthe support of planar graph, so planarization algorithm is needed to transform theoriginal wireless network into planar graph. On the basis of theoretical analysis, thisthesis simulated two types of planar graphs, and then systematically simulated andanalyzed greedy routing algorithm, face routing algorithm and combined greedy facerouting algorithm.After the introduction of theoretical basis, this thesis briefly explained the strategyand basic principle of the classical geographic routing algorithm, namely GPSR. Aimingat the detour of GSPR in perimeter probing, this thesis proposed a simple strategy and arouting protocol, namely Improved-GPSR. Improved-GPSR can effectively reduce thenumber of hops caused by detour. Thereafter, this thesis simulated the routingalgorithms under different network topologies and scenes, and then compared therouting paths of the two routing algorithms in perimeter probing, tested mainperformance indexes and scalability, and finally discussed the impact of beacon periodon performance of the two routing algorithms.In the end, to validate the practicality of Improved-GPSR, this thesis implementedit on the Android platform and put it into simple communication software. Through thissoftware, the actual performance of the algorithm can be demonstrated. This thesis explained the modeling and design of the software, then showed the test result, andfinally pointed out the meaning and weakness of the test.