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 MORE EFFICIENT PATH OPTIMIZATION FOR GREEDY GEOGRAPHIC ROUTING INWIRELESS SENSOR NETWORKS Le Dinh Thanh1, Ho Thuan2, Nguyen Dai Tho1 1VNU University of Engineering and Technology 2VAST Institute of Information Technology 1E-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. Both greedy forwarding and recovery routing can be lightweight in the sense that only information on the position of neighboring nodes is maintained at each node. Although existing 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 to communication. Recently, we proposed GPOR, a greedy with path optimization protocol for geographic routing in wireless sensor networks [11]. GPOR deals with the problem of nearly optimal path discovery by using a novel shortcut creation mechanism for early detection and avoidance of obstacles. The scope of destinations in the routing tables refers to an area instead of a point as usually the case in traditional routing. The protocol has been shown by simulation to be more efficient than BOUNDHOLE [6] in terms of packet delivery 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 areas specified in the routing tables. Then, extensive simulations are done with the upgraded protocol to compare its performances with GPOR. 2. Content 2.1. Related Works Greedy forwarding [1] is simple, scalable and efficient but suffers from local minima due to obstacles. To overcome this problem, greedy forwarding is combined with recovery routing. When greedy forwarding fails, a recovery routing strategy is used in order to route the packet to a node where greedy forwarding can be resumed. Recovery routing 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 simple but inefficient. The main problem with face routing is that existing planar graph extraction methods produce incorrect planar graphs in case of non-uniform radio patterns and thus can cause the routing to fail. Boundary detouring is practical and lightweight. But it produces long routing paths in cases where packets are forced to detour around large geographic holes. In addition, data traffic may become heavy on the boundaries of the holes, 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 early detection and avoidance of obstacles. In [10], another path optimization scheme was proposed, 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 to greedy forwarding as an option of last resort. The routing tables specify shortcut paths 151 Le Dinh Thanh, Ho Thuan, Nguyen Dai Tho for packet transmission and are updated by a novel shortcut creation technique that makes routing entries better and better after each data transmission. Unlike topological routing where each node maintains a routing entry for each destination, each entry in the GPOR routing tables corresponds to a specified destination area. This enlargement of the scope of destinations allows more efficient exploitation of the routing entries. To the best of our 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 and exploits these paths more efficiently. 2.2. Improvement We further expand the destination areas in the GPOR routing tables by adding a new field, named lastlm, to each table entry. The new format of the routing entries is shown in Table 1. Table 1. Extended format of routing entries with lastlm Field Description pos Targeted position next Identifier of the neighbor that is chosen as the next hop if the current 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 a routing entry 〈posx, nextx, lastlmx, ttlx〉 at node C, we define a 2-dimensional Cartesian coordinate system with its origin at lastlmx position and with x-axis being the direction from lastlmx to the targeted position posx. We regard the x-axis of the defined coordinate system as the west-east direction (W-E). Then, we divide the plane into four quadrants labeled clockwise NE, ES, SW and WN. The routing entry 〈posx, nextx, lastlmx, ttlx〉 at node C is applicable for the destination D if its ttlx is greater than 0 and at least one of the following conditions is met. - Condition 1: The distance from D to posx is not greater than r, where r is the radio range of the nodes. - Condition 2: D is in the ES area, C is either in the WN area or the SW area, and vector Cnextx points west or D is on the left side of Cnextx if Cnextx points east. Figure 2 gives two examples on the scope of applicability of the routing entries. In the first example, vector Cnextx points west, the destination area of the routing entry contains the ES area and those points not farther away from posx than r. In the second example, Cnextx points east, the destination area of the routing entry contains the points 152 More efficient path optimization for greedy geographic routing in wireless sensor networks in the ES area and on the left of Cnextx, and the points not farther away from posx than r. Figure 2. Scope of applicability of the routing entry 〈posx, nextx, lastlmx, ttlx〉 at node C: (a) Cnextx points west; (b) Cnextx points east 2.3. Simulation We update our GPOR’s implementation in the open-source network simulator ns-2 [12] with the extensions presented in the previous section. Then, we perform extensive simulations using the same settings and scripts as in [11]. Simulation results show that the extensions to GPOR improve the packet delivery rate and reduce the average path length. From now on, we refer to the original version of the GPOR protocol as GPOR-original. The simulation results in Figure 3 and Figure 4 show that the packet delivery success rate of GPOR is increased thanks to the expansion of the destination areas. The reduction of the average path length as a result of more frequent use of the routing entries is also confirmed in Figure 5 and Figure 6. Simulation results in Figure 7 and Figure 8 indicate that the expansion of destination areas slightly reduces communication overhead. Figure 3. Packet delivery success rate with varying the number of concurrent traffic flows 153 Le Dinh Thanh, Ho Thuan, Nguyen Dai Tho Figure 4. Packet delivery success rate with varying network diameter Figure 5. Average path length with varying the number of concurrent traffic flows Figure 6. Average path length with varying network diameter 154 More efficient path optimization for greedy geographic routing in wireless sensor networks Figure 7. Overhead with varying the number of concurrent traffic flows Figure 8. Overhead with varying network diameter 3. Conclusion We have upgraded our previously proposed GPOR protocol with a more efficient path optimization mechanism. In the near future, we intend to conduct additional research on shortcut creation techniques in order to make our geographic routing paradigm even more efficient. REFERENCES [1] Finn GG., 1987. Routing and Addressing Problems in Large Metropolitan-Scale Internetwork.Tech. Rep. ISI/RR-87-180. [2] Stojmenovic I, Lin X., 2001. Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks. IEEE Trans. on Parallel and Distributed Systems, 12: 1023-1032. [3] Guping Z, Yu W., 2009. Advance detour strategy for geographic routing in wireless sensor networks. International Forum on Information Technology and Applications, 155 Le Dinh Thanh, Ho Thuan, Nguyen Dai Tho pages 296-299. [4] Karp B, Kung HT., 2000. GPSR: Greedy perimeter stateless routing for wireless sensor networks. In Proc. of Mobicom, pages 243-254. [5] Bose P, Morin P, Stojmenovic I, Urrutia J., 2001. Routing with guaranteed delivery in ad hoc wireless networks. J. Wireless Networks, 7 (6): 609-616. [6] Fang Q, Gao J, Guibas L., 2006. Locating and bypassing routing holes in sensor networks. J. Mobile Networks and Applications 11 2: 187-200. [7] Nikoletseas S, Powell O., 2007. Simple and efficient geographic routing around obstacles for wireless sensor networks. In Proc. of the 6th Workshop on Efficient and Experimental Algorithms, pages 161-174. [8] Moraru L, Leone P, Nikoletseas S, Rolim JDP, 2007.Near optimal geographic routing with obstacle avoidance in wireless sensor networks by fast-converging trust-based algorithms. In Proc. of the 3rd ACM Workshop on QoS and Security for Wireless and Mobile Networks, pages 31-38. [9] Huc F, Jarry A, Leone P, Moraru L, Nikoletseas S, Rolim J., 2009. Early obstacle detection and avoidance for all to all traffic pattern in wireless sensor networks. LGOSENSORS, pages 102-115. [10] Koutsopoulos A, Nikoletseas S, Rolim JDP, 2009. Near-optimal data propagation by efficiently advertising obstacle boundaries. In Proc. of the 6thACM Symposium on Performance Evaluation of Wireless Ad hoc, Sensor, and Ubiquitous Networks, pages 15-22. [11] Dinh TL, Nguyen DT., 2010. Greedy geographic routing with path optimization in wireless sensor networks. In Proc. of the 2010 IEEE-RIVF Int’l Conf. on Computing and Communications Technologies, pages 148-153. [12] The Network Simulator - ns-2. [Online]. Available: 156