Research On Geometric Routing For Wireless Sensor Network

Wireless sensor networks are networks of small low-power devices that can operate unattended to monitor and measure different phenomena in the environment. Sensor networks suited for monitoring, tracking and infrastructure protection. Routing and topology control are two key problems. The efficency of commuinication largely depends on the routing protocols and the topology of the network is determined by topology control protocols. As the performance of routing protocols is closely related to network topology, therefore, routing problem and topology control problem are the focuses of the thesis.Geometric routing protocols are very suited for wireless sensor networks. These protocols take advantage of the position information of nodes to provide high efficient and scalable routing. In wireless sensor networks, nodes are distributed in some geographic areas; the distance between nodes determines whether they can communicate each othe directly. Therefore, geometric routing protocols are suited for the characteristic of wireless sensor network. The availability of small and cheap GPS receivers and the researches of GPS-free location algorithms make it possible to deploy geometric routing in wireless sensor network.In this paper, based on analyzing the limitations of existing works, a new geometric routing protocol, forwarding rectangle constrained greedy face routing protocol (CGFR), is proposed. CGFR protocol mainly aims to ensure the success of packet delivery, and then to reduce the length or hops of route travesed by packet.The foundation of CGFR protocol is topology control. The purpose of toplogy control is to construct a topology to satisfy the requirement of geometric protocol and to improve the performance of geometric routing protocol. The main idea of topology conrol is to construct a planar t-spanner of the original topology, i.e. for every pair of nodes the length of the shortest path between them in the topology constructed by the topology control algorithm is no more than that of the original topology. As the topology constructed by the topology control algorithm is planar, it may ensure the delivery of geometric routing algorithm. As the topology constructed by the topology control algorithm is a t-spanner, it provides shorter path for geometric routing protocol.Topology control includes static topology control algorithm and dynamic topology control algorithm. Static topology control algorithm constructs planar t-spanner for static network, which is the base of dynamic topology control algorithm. Dynamic topoplogy control algorithm can maintain the topology to be a planar t-spanner in dynamic networks, where nodes can join and leave network at anytime and anywhere.The core of CGFR is geometric routing, whose aim is to improve the forwarding efficiency at the base of the successful delivery. Geometric routing algorithm incudes forwarding-rectangle constrained greedy routing (CGR) algorithm, forwarding-rectangle constrained face routing (CFR) algorithm and forwarding-rectangle constrained greedy face routing (CGFR) algorithm.The idea of CGR algorithm is constraining the candidate of next hop nodes in forwarding-rectangle to bound the length or hops of the route travered by packet. It is proved that CGR algorithm can bound the length or hops of the route traversed by packet by constant times of the length or hops of the route in ideal network. Simulation results show that although forwarding-rectangle decreases the ration of successful delivery, it bounds the length or hops of route.As all other face-based routing, CFR algorithm ensures the successful delivery. It use a way like binary search to avoid the high overhead of pure face routing algorithms, which approximates the overhead of broadcast algorithm. The conjecture is confirmed by simulation results.CGFR algorithm combines the advantage of CGR algorithm and CFR algorithm, which ensure the successful delivery and high efficiency. It is proved that the cost of CGFR algorithm is the same quantity as the optimal geometric routing algorithm. Simulation results show that the cost of CGFR algorithm is less than that of any existing geometric algorithms.The research of geometric routing protocol will greatly promote the application of wireless sensor network. However, relevant researches in this field are just beginning. Many efforts still need to be made to realize its future application.