More efficient path optimization for greedy geographic routing in wireless sensor networks

In this paper, we propose an improvement of our previous protocol for geographic routing in wireless sensor networks. The original protocol uses a combination of greedy forwarding and recovery strategies for route discovery. At the same time, shortcut paths are created and then each of these paths is gradually made shorter than the one preceding.
Nội dung trích xuất từ tài liệu:
More efficient path optimization for greedy geographic routing in wireless sensor networks JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 150-156 This paper is available online at http://stdb.hnue.edu.vn MORE EFFICIENT PATH OPTIMIZATION FOR GREEDY GEOGRAPHIC ROUTING IN WIRELESS SENSOR NETWORKS Le Dinh Thanh1, Ho Thuan2, Nguyen Dai Tho1 1 VNU University of Engineering and Technology 2 VAST Institute of Information Technology 1 E-mail: thanhld@vnu.edu.vn. Abstract. In this paper, we propose an improvement of our previous protocol for geographic routing in wireless sensor networks. The original protocol uses a combination of greedy forwarding and recovery strategies for route discovery. At the same time, shortcut paths are created and then each of these paths is gradually made shorter than the one preceding. The scope of destinations is extended from a point to an area. The current work further enlarges the destination areas specified in the routing tables. Extensive simulation results show that the upgraded protocol is more efficient than the previous one. Keywords: Path optimization, geographic routing, wireless sensor networks.1. Introduction Geographic routing, a combination of greedy forwarding [1] and recovery routing[2], [7], is particularly suitable to resource-constrained wireless sensor networks. Bothgreedy forwarding and recovery routing can be lightweight in the sense that onlyinformation on the position of neighboring nodes is maintained at each node. Althoughexisting geographic routing protocols can be very efficient and scalable in dense networks,they generally do not perform well in the presence of holes that represent obstacles tocommunication. Recently, we proposed GPOR, a greedy with path optimization protocol forgeographic routing in wireless sensor networks [11]. GPOR deals with the problem ofnearly optimal path discovery by using a novel shortcut creation mechanism for earlydetection and avoidance of obstacles. The scope of destinations in the routing tables refersto an area instead of a point as usually the case in traditional routing. The protocol hasbeen shown by simulation to be more efficient than BOUNDHOLE [6] in terms of packetdelivery rate and end-to-end delay.150 More efficient path optimization for greedy geographic routing in wireless sensor networks In this paper, we improve GPOR by further expanding the destination areasspecified in the routing tables. Then, extensive simulations are done with the upgradedprotocol to compare its performances with GPOR.2. Content2.1. Related Works Greedy forwarding [1] is simple, scalable and efficient but suffers from localminima due to obstacles. To overcome this problem, greedy forwarding is combined withrecovery routing. When greedy forwarding fails, a recovery routing strategy is used inorder to route the packet to a node where greedy forwarding can be resumed. Recoveryrouting schemes can be classified into four main classes: flooding [2], backtracking [3],face routing [4], [5] and boundary touring [6], [7]. Flooding and backtracking are simplebut inefficient. The main problem with face routing is that existing planar graph extractionmethods produce incorrect planar graphs in case of non-uniform radio patterns and thuscan cause the routing to fail. Boundary detouring is practical and lightweight. But itproduces long routing paths in cases where packets are forced to detour around largegeographic holes. In addition, data traffic may become heavy on the boundaries of theholes, something that can lead to congestion. Figure 1. Behavior of nodes in GPOR The geographic routing protocols in [8] and [9] use a trust-based scheme for earlydetection and avoidance of obstacles. In [10], another path optimization scheme wasproposed, based on the marking of areas around obstacles with beacon sequences. GPOR[11] (see Figure 1) makes path decisions based on routing tables before switching togreedy forwarding as an option of last resort. The routing tables specify shortcut paths 151 Le Dinh Thanh, Ho Thuan, Nguyen Dai Thofor packet transmission and are updated by a novel shortcut creation technique that makesrouting entries better and better after each data transmission. Unlike topological routingwhere each node maintains a routing entry for each destination, each entry in the GPORrouting tables corresponds to a specified destination area. This enlargement of the scopeof destinations allows more efficient exploitation of the routing entries. To the best ofour knowledge, GPOR is the first scheme that can be applied to all-to-all traffic pattern.Compared to existing path optimization schemes, GPOR creates shorten paths faster andexploits these paths more efficiently.2.2. Improvement We further expand the destination areas in the GPOR routing tables by adding anew field, named lastlm, to each table entry. The new format of the routing entries isshown in Table 1. Table 1. Extended format of routing entries with lastlm Field Description pos Targeted position Identifier of the neighbor that is chosen as the next hop if the current next routing entry is used lastlm Position of the last local minimum ttl Time to live The expansion of the scope of the destination areas is as follows. Given arouting entry hposx , nextx , lastlmx , ttlx i a ...