Research On Geometric Routing Algorithms Based On Graph Embedding In Wireless Sensor Networks

Geometric routing protocols provide efficient and scalable routing for wireless sensor networks.A new branch of geometric routing protocols is called virtual coordinate-based geometric routingprotocol, in which the sensors do not need to know the predefined geographic coordinates, thelocations which routing is based on are obtained from the graph embedding method instead, and theenergy consumption caused by localization is then reduced effectively. The routing algorithm is thesoul of routing protocol. The main drawback of related works is that the represent of virtualcoordinates is not succinct, which can not be standed in sensor networks because of the overhead ofmemory. At present, Schnyder geometric routing algorithm can solve this problem and make thegeometric routing simple and efficiency. The drawback of Schnyder geometric routing algorithm isthat the algorithm is based on strict mathematical structure, this means when the network topologychanges dynamically(especially when node failure), the algorithm will no longer apply. This problemis researched in this thesis, which mainly concludes research on geometric routing algorithms basedon graph embedding and solves the problem of node failure.Based on Schnyder geometric routing algorithm, geometric routing algorithms which tolerancenode failure are proposed in this thesis. First, for topology models of3-connected planar graphs andplane triangulations, a simple and efficient algorithm which is called Greedy-Compass Double ModeRouting Algorithm is proposed, this algorithm can direct message delivery. Then, to provide100%message delivery rate, secondary embedding methods are used in this thesis. For topology models of3-connected planar graphs, Tree Routing Algorithm based on graph st-orientation is proposed, thealgorithm inherites the succinctness of nodes represent in Schnyder geometric routing algorithm. Inorder to solve the "hole" problem caused by nodes failure in topology models of plane triangulations,a Conformal Mapping Algorithm based on Ricci flows is used to map the network with irregularshape holes to the unit disk with circular holes, the algorithm guarantees that local minimum will notexist in the network and greedy forwarding will never get stuck.For geometric routing algorithms proposed above, simulation experiments and analyses onexperimental results are carried out. The results show that geometric routing algorithms proposed inthis thesis can solve the problem of node failure effectively.