Location-Based Routing Algorithms for Wireless Sensor Network

     The Wireless Sensor Network (WSN) is an intelligent autonomous monitoring system where lots of micro sensor nodes with communication and computing capabilities are deployed in the unattended monitoring regions. In actual applications, especially military, it is often required to locate the sensor nodes in order to obtain the geographical location information of a monitoring region. As a result, it is a natural thing to consider location information in the design of WSN routing algorithms. The routing algorithm based on location information has become an important subject in current WSN research and has attracted widespread attention.

     The location information-based routing algorithm uses location information to guide routing discovery and maintenance as well as data forwarding, enabling directional transmission of the information and avoiding information flooding in the entire network. Consequently, the control overhead of the algorithm is reduced, and routing is optimized. Moreover, with network topology based on nodes’ location information, network management becomes simple and global network optimization can be
easily achieved.

     The researchers around the world have put forward several location information-based routing algorithms for various application scenarios. Among other issues, how to make full use of location information to achieve efficient routing is a focus. This paper analyzes the application of location information in routing algorithms from three aspects: flooding restriction, virtual area partition, and optimal routing choice.

1 Flooding Restriction
Traditional flooding routing protocols have such advantages as simplicity and robustness[1], many of which have adopted the flooding routing idea. However, flooding routing is apt to information redundancy and "implosion", bringing unwanted resource consumption. To address this problem, location information, such as distance and position, is used to guide and restrict the flooding by defining the search region of flooding routing, thus the orientation and effectiveness of routing search are greatly improved. When no suitable path is available in the restricted region, flooding region would be adaptively adjusted, or traditional flooding methods would be used to continue routing search. Flooding restriction comes into several forms, including distance-based, angle-based, and rectangle-based.

1.1 Distance-Based Flooding Restriction
When the location of a target region is uncertain, a simple distance-based flooding restriction region can be created: The routing search information is flooded to the nodes far away from the sender. Only when a node far away from the sender receives the data packet, it forwards the packet. In this way, information redundancy is reduced. When the location of a target region is certain, a request zone can be created with the nodes nearer than the target region. The Location-Aided Routing (LAR) scheme for determining the request zone adopts this concept[2].

1.2 Angle-Based Flooding Restriction
In the angle-based flooding restriction mechanism, the restricted region is determined by an angle. That is to say, only the intermediate nodes that are in a certain angle range can be used as relay nodes for routing flooding. There are many ways to decide the restriction angle. Figure 1, Figure 2 and Figure 3 illustrate three of them.

     In Figure 1, the angle-restricted region is confined by the two rays: OM and OP[3] and the restriction angle ∠SOM is determined as follows: First, use the source node S and the destination node D as the centers and RS and Rd  (supposing RS >Rd ) as the radiuses respectively to form two circles; then draw the two common tangents of the two circles, which meet at point O ; and finally, calculate the degree of the restriction angle ∠SOM. The sizes of RS and Rd  are adjustable, depending on specific applications.
In Figure 2, the restriction angle is variable rather than fixed. Assume S is the source node, D is the destination node, and X is an intermediate node. The routing request packet forwarded by X contains the restriction angle ∠DXM, which is calculated out with the following formula:

     When nodes J and K receive the data packet forwarded by X, they compute ∠DXJ and ∠DXK  respectively, and compare them with ∠DXM. If the computed angle (e.g. ∠DXK in this case) is greater than ∠DXM, the related node (K) drops the packet; if the computed angle (e.g. ∠DXJ  in this case) is less than ∠DXM, the node (J) continues to forward the data packet and updates the restriction angle with the computed one (∠DXJ  here).

     In Figure 3, the routing request packet of the source node S includes its own location information and a predefined restriction angle[4]. After an intermediate node M receives the packet, it uses trigonometric formulae to compute its included angle (∠SMD ) with the source node S and the destination
node D. If ∠SMD  is greater than the predefined restriction angle, the node M continues to forward the packet, otherwise, it discards the packet. The predefined restriction angle can be set based on actual applications.

1.3 Rectangle-Based Flooding Restriction
Rectangle-restricted region is a rectangle flooding region determined by certain policies. Figures 4 and 5 illustrate two ways of constructing such a rectangle.

     In Figure 4, the restriction rectangle is constructed using source node S and destination node D as two vertexes. To increase the success rate of routing request, the destination can be expanded into a circle with a radius of R. The R  should not exceed the communication radius of the destination node and its value can be adjusted according to the density of the nodes. Generally, in order to ensure the success rate of routing, the R  is set to be a small value if the nodes are densely deployed, but a large value if the nodes are sparse.

     In Figure 5, the rectangle restriction region is constructed[5] as follows: source node S and destination node D are the center points of two sides (i.e. L1 and L2) of the rectangle respectively, which are vertical to the line passing through S and D. The other two sides L3 and L4 are parallel with the line passing S and D. w is the length of L1 and L2), which sizes can be adjusted for actual applications.
In addition, the protocols which divide the entire region into grids and flood queries within each rectangle grid, such as Two-Tier Data Dissemination (TTDD)[6], can be also regarded as a construction method for restriction rectangle.

2 Virtual Area Partition
The virtual partition scheme first divides the entire monitoring region into many sub-regions by location and then designs the routing according to the location information of the sub-regions. This scheme is scalable and suitable for large-scale networks because it solves the coordination problem using organizational structure design. The location information included in each sub-region can help routing setup and enable directional transmission, thus avoiding blindness in information transmission and reducing redundancy; and meanwhile, it facilitates information fusion and mobile node processing, thus allowing better real-time transmission. Moreover, by allocating and scheduling the tasks among the nodes in a region, some nodes can be in sleeping state, leading to energy saving and longer network lifetime.

     Virtual area partition can be realized in many forms, including regular geometrical pattern, virtual polar coordinate system, and clustering-based irregular partition. In practice, the entire network can be evenly divided into several grids, or divided into several sub-regions unevenly based on node density, connectivity and network scale. A routing search can be done in two steps: Intra-region routing and inter-region routing.

2.1 Regular Partition
Regular geometric patterns that are used for network partition include rectangle, regular hexagon, triangle, diamond, circle, and sector. The regular hexagonal pattern adopts the cell mechanism in cellular networks but it is seldom used because it involves very complicated computing. The circle partition method determines a node’s partition by comparing the partition radius with the distance from the node to the center, but the partitions may overlap at their boundaries. Reference[7] discusses triangle and diamond partition methods, which divide the network into triangle or diamond grids respectively. In Reference [8], the network is divided into annulus sector grids. In practice, rectangle partition method is used the most because there is not any overlapped area, and its implementation is very simple.

     Among all rectangles, square grid is the most common used in many protocols, for instance, Geographical Adaptive Fidelity (GAF)[9], TTDD, GRID and Grid-Clustering Routing Protocol (GROUP)[10]. Here we analyze several typical square grid-based routing protocols.

     In GAF, the whole network area is divided into small virtual grids based on the nodes’ location information and communication ranges, ensuring that any two nodes, which are in two adjacent grids respectively, can directly communicate with each other. Assume the communication range of all nodes is R, and the side of the virtual grid is r. To ensure communication between nodes in any two grids, it is required to satisfy.Within a grid, the topology control algorithm is adopted to let some nodes be in the sleeping state, thus achieving energy conservation. Meanwhile, the states of all nodes are controlled with a state transition mechanism. The core concept of GAF is to keep the network connective by letting the representative node in each virtual grid be always active.

     In TTDD protocol, when multiple nodes detect an event, they select one node as the source node to send the data. This source node itself acts as one crossing point to construct a grid. The construction process is as follows: The source first calculates the locations of its four neighboring dissemination points and simply uses greedy forwarding algorithm to request a neighbor node that has the smallest distance to any dissemination point to be a forwarding node. The neighbor node continues the forwarding in a similar way till the request times out or the edge of the network is reached. The forwarding node saves the event as well as the source node information, and will be a participant in future data transmission. When a sink queries data, it floods the query among the dissemination nodes and the flooding stops until finally the query reaches the source. The queried data are then transmitted to the sink in a reverse direction.
In GRID protocol, the entire network is divided into many virtual grids of the same size, and a path is made up of a group of specific virtual grids. By certain means, each grid selects a node as the gateway, which is responsible for forwarding all data packets that pass this grid and the routing is from one grid to another. Reference [5] gives several methods of determining grid side length. Simulations show that once the side length r  meets the following requirement:(where R  is the communication radius of the node), the nodes in two diagonal grids can communicate with each other without any obstacle. That is to say, a node can communicate with nodes in its eight neighbor grids.

     In GROUP, the sink selects a seed node periodically and builds a virtual grid structure of certain width based on the seed node. In each grid, a node is selected as the cluster head, which is often near to the grid intersection. The nodes around the head belong to this cluster.

2.2 Virtual Polar Coordinate System
Virtual polar coordinate system is a special angle partition method. The basic idea of Graph Embedding (GEM)[11] for data-centric storage is to build a virtual polar coordinate system to align with the actual network topology. The nodes in the network form a ringed tree whose root is a convergence node. Each node is denoted with the number of hops to the root of the tree and a virtual angle range, and the node-to-node routing is denoted with a ringed tree. The virtual polar coordinate system is created as follows: The root node assigns each child node an angle range, e.g. [0, 90], which size is proportional to the size of that child node’s subtree. Each node then assigns each of its child nodes a subset of its angle range. The process continues recursively until every leaf node is assigned an angle range. In this way, a node can assign angle ranges to its child nodes based on a uniform rule (e.g. clockwise), enabling the angle ranges assigned to the nodes at the same level to increase or decrease proportionally. Thus the nodes that are the same hops away from the root form a ring and the entire network becomes a ringed tree whose root is the convergence node. The basic routing process of the virtual polar coordinate system is: When a node sends a data packet, it forwards the packet to its parent if the destination’s angle is not within its angle range. The parent, in turn, uses the same method to handle the packet. The routing goes on in this manner until the packet reaches the node whose angle is closer to the destination angle range.

2.3 Clustering-Based Irregular Partition
Location information also plays an important role in the clustered routing. The clusters coming from different clustering algorithms are irregular and form virtual network sub-regions. In a cluster, the cluster head is the basis for cluster construction. One important criterion used in cluster head election algorithms is location information of the cluster, including the distance of a node to the cluster head, the distance of the cluster head to the BS and the ratio of distance to energy consumption. For example, the Cluster-head Election using Fuzzy Logic (CEFL)[12] algorithm uses node centrality as a criterion for cluster head election. The centrality means how much a node approaches the cluster center, which is calculated on the basis of the sum of the squared distances of the node to other nodes in the cluster. After cluster heads are elected, the nodes around the heads will selectively join the clusters based on the distribution of cluster heads. In Energy Efficient Clustering Scheme (EECS)[13] protocol, the distance from a node to the cluster head and the distance from the cluster head to the BS are considered in the formula for computing the cost at which the node decides to join a cluster.

3 Optimal Path Choice
In selecting nodes for multi-hop forwarding, certain criteria are often followed to choose the optimal node. The optimal path choice scheme based on location information is supposed to use the location information such as angle or distance as a route selection criterion. In the following chapters, we discuss several typical routing algorithms to explain the importance of location information in choosing the optimal path.

3.1 GPSR
Greedy Perimeter Stateless Routing (GPSR)[14] is a typical protocol that adopts greedy forwarding algorithm. When a node is required to forward data packets, it first selects the nearest neighbor as the next-hop node, and then forwards the packets to the node. To address the local optimization problem arisen from greedy algorithm, that is, a satisfying next-hop node is not available, GPSR suggests perimeter forwarding algorithm, which acts as a supplement to greedy forwarding algorithm. This algorithm constructs a planar graph on the original network topology to solve the route hole problem. That is to say, the route is recovered by routing to the destination around the edge of the graph. The full GPSR protocol combines greedy forwarding algorithm with perimeter forwarding algorithm to achieve routing to destination node. In the network, greedy forwarding is the main approach for routing, but when satisfying next-hop nodes are not available, the perimeter forwarding algorithm is used on the planar graph to choose the next-hop.

3.2 GEAR
Geographic and Energy Aware Routing (GEAR)[15] sets up a path from the source node to the target region by means of query. Taking advantage of the greedy algorithm in GPSR, this protocol uses the nodes’ location information as well as the remaining energy level to select the neighbor node with the least overall overhead (a combination of the distance to the destination and the remaining energy level) for forwarding and thus sets up a path to the target region for the query packet. After the query packet reaches the target region, recursive geographic forwarding or restricted flooding can be used to disseminate the packet.
In recursive geographic forwarding approach, the node that first receives the query request within the target region splits the target region into several sub-regions and forwards the query request to the centers of all sub-regions. Similarly, the node nearest to the center of a sub-region, upon receiving the query request, further splits the sub-region into several smaller ones and forwards the query request. This recursive splitting and forwarding procedure is repeated until a node finds itself the only one inside the sub-region. After the forwarding procedures in all sub-regions finish, the entire recursive procedure terminates. This approach is better suitable for the applications where the nodes are densely deployed.

3.3 TBF
Trajectory Based Forwarding (TBF)[16] uses parameters to specify a trajectory rather than routing node sequence in packet headers. Each forwarding node, based on its trajectory parameter and its neighbors’ locations, makes greedy decision to find the nearest node and select it as the next-hop node. By specifying different trajectory parameters, multipath propagation or broadcast as well as broadcast or
multi-cast in a specific region can be easily achieved.

3.4 SPAN
SPAN[17] is an energy-efficient coordination algorithm which elects some nodes as coordinators based on their locations. These elected coordinators form a backbone, specially responsible for message forwarding. The nodes that do not join the backbone will go to sleep periodically. Each node in the network can independently and periodically decide whether it should sleep or wake up.

4 Conclusions
The routing algorithms based on location information are an important subject in the research of routing protocols. In the long term, these algorithms should be further studied from the following perspectives:

     (1) Combination with location technologies: Most of existing geographic routing protocols do not discuss the specific method to obtain the location information of a node, and their research is always carried out upon the assumption that the node’s location information is known. In fact, the location technology is still an important and challenging subject in current WSN research because the location procedure and precision have great impact on the design of routing protocols. With location algorithms being combined with and the impact of location precision on protocol performance being taken into account, the routing protocols can be much more effective and application-specific. The Geographic Routing without Location Information (GRWLI) [18] suggests a routing mechanism, where only a few nodes’ precise locations are used. The key of the algorithm is to use some beacon nodes to construct a global coordinate space as well as the positions of other nodes in the coordinate space.

     (2) The impact of topography on routing algorithms: In actual applications, WSNs are often affected by topographical factors, such as landform and surface feature. Some of existing routing algorithms are based on a virtual 2-dimensional geographic space rather than actual environments. As a result, the actual geographic environment is also an issue to be addressed in the research of routing protocols.

     (3) Coverage control: Another issue that has to be considered in the design of routing protocols is the node’s connectivity and network coverage. Particularly, the coverage control has to be analyzed when sleeping mechanism is included in the routing design.

     (4) Security: In many applications, especially military, the security of routing protocols must be considered. For example, Reference [19] studies geographical location-based key distribution.

     (5) Routing protocols for underwater, deep space and underground WSNs. Related research should be done for these special application scenarios.

References
[1] HEDETNIEMI S, LIESTMAN A. A survey of gossiping and broadcasting in communication networks [J]. Networks, 1998, 18(4): 319-349.
[2] KO Young Bae, VAIDYA N H. Location-Aided Routing (LAR) in mobile Ad Hoc networks [J]. Wireless Networks, 2000, 6(4): 307-321.
[3] 张锦. 传感器网络中基于位置信息的路由算法研究 [D]. 长沙: 湖南大学, 2004: 14-20.
[4] 王军, 于海斌. 一种两段式传感器网络路由协议 [J]. 仪器仪表学报, 2007, 28(5): 908-913.
[5] LIAO W H, TENG Y C, SHEU J P. GRID: a fully location-aware routing protocol for mobile Ad Hoc networks [J]. Telecommunication Systems, 2001,
18(1): 37-60.
[6] YE F, LUO H, CHENG J, et al. A two-tier data dissemination model for large-scale wireless sensor networks [J].Wireless Networks, 2005, 11(2):
161-175.
[7] WANG Xueqing, YANG Yongtian, ZHANG Zhonglin, et al. A virtual rhomb grid-based movement-assisted sensor deployment algorithm in wireless sensor networks [C]// Proceedings of the International
Multi-symposiums on Computer and Computational Sciences: Vol. 1, Apr 20-24, 2006, Hangzhou, China. Piscataway, NJ, USA: IEEE Computer Society, 2006: 491-495.
[8] 孙雨耕, 李桂丹, 武晓光, 等. 基于基站辅助定位的无线传感器网络通信协议 [J]. 天津大学学报, 2007, 40(1): 98-103.
[9] XU Y, HEIDEMANN J, ESTRIN D. Geography informed energy conservation for Ad-hoc routing [C]//Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking, Jul 16-21, 2001. Rome, Italy. 2001:
70-84.
[10] YU Livang, WANG Neng, ZHANG Wei. GROUP: a Grid-clustering Routing Protocol for Wireless Sensor Networks[C]// proceedings of International Conference on Wireless Communications, Networking and Mobile Computing, Sep 22-24, 2006, Wuhan, China. Piscataway, NJ, USA: IEEE, 2006: 1-5.
[11] NEWSOME J, SONG D. GEM: Graph embedding for routing and data-centric storage in sensor networks without geographic information [C]//Proceeding of 1st ACM Conference on Embedded Networked Sensor Systems, Nov 5-7, 2003, Los Angeles, CA, USA. New York, NY, USA: ACM, 2003: 76-88.
[12] GUPTA I, RIORDAN D. Cluster-head election using fuzzy logic for wireless sensor networks [C]//Proceedings of the 3rd Annual Communication Networks and Services Research Conference, May 16-18, 2005, Halifax, Canada. 2005: 255-260.
[13] YE M, LI C F, CHEN G H, et al. EECS: An energy efficient clustering scheme in wireless sensor networks [C]//Proceeding of the IEEE International Performance Computing and Communications Conference, Apr 7-9, 2005, Phoenix, AZ, USA. New York, NY, USA: IEEE, 2005: 535-540.
[14] KARP B, KUNG H. GPSR: Greedy perimeter stateless routing for wireless networks [C]//Proceeding of the 6th Annual International Conference on Mobile Computing and networking, Aug 6-11, 2000, Boston, MA, USA. New York, NY, USA: ACM, 2000: 243-254.
[15] YU Y, GOVINDAN R, ESTRIN D. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks [R].
UCLA/CSD-TR-01-0023. 2001.
[16] NICULESU D, NATH B. Trajectory based forwarding and its applications [C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, Sep 14-19, 2003, San Diego, CA, USA. New York, NY, USA: ACM, 2003: 260-272.
[17] CHEN B, JAMIESON K, BALAKRISHNAN H, et al. SPAN: an energy efficient coordination algorithm for topology maintenance in ad hoc wireless networks [J]. Wireless Networks, 2002, 8(5): 481-494.
[18] RAO A, RATNASAMY S, PAPADIMITRIOU C, et al. Geographic Routing without Location Information [C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, Sep 14-19, 2003, San Diego, CA, USA. New York, NY, USA: ACM, 2003: 96-108.
[19] 蔡晓, 杨庚, 王江涛. 一种基于位置信息的WSN随机密钥预分配方法 [J]. 南京邮电大学学报:自然科学版, 2007, 27(1): 20–24.

[Abstract] Routing algorithms based on geographical location is an important research subject in the Wireless Sensor Network (WSN). They use location information to guide routing discovery and maintenance as well as packet forwarding, thus enabling the best routing to be selected, reducing energy consumption and optimizing the whole network. Through three aspects involving the flooding restriction scheme, the virtual area partition scheme and the best routing choice scheme, the importance of location information is seen in the routing algorithm.