The Effect of Mobility-Induced Location Errors on Geographic Routing in Mobile Ad Hoc and Sensor Networks: Analysis and Improvement Using Mobility Prediction
|
Geographic routing has been introduced in mobile ad hoc networks and sensor networks. Under ideal settings, it has been proven to provide drastic performance improvement over strictly address-centric routing schemes. While geographic routing has been shown to be correct and efficient when location information is accurate, its performance in the face of location errors is not well understood. In this paper, we study the effect of inaccurate location information caused by node mobility under a rich set of scenarios and mobility models. We identify two main problems, named LLNK and LOOP, that are caused by mobility-induced location errors. Based on analysis via ns-2 simulations, we propose two mobility prediction schemes—neighbor location prediction (NLP) and destination location prediction (DLP) to mitigate these problems. Simulation results show noticeable improvement under all mobility models used in our study. Under the settings we examine, our schemes achieve up to 27 percent improvement in packet delivery and 37 percent reduction in network resource wastage, on average, without incurring any additional communication or intense computation.
[1] 233 E. Kaplan, Understanding GPS. Artech House, 1996.
[2] B. Karp and H.T. Kung, Greedy Perimeter Stateless Routing for Wireless Networks Proc. Mobicom, pp. 243-254, 2000.
[3] S. Basagni, I. Chlamtac, V.R. Syrotiuk, and B.A. Woodward, A Distance Routing Effect Algorithm for Mobility (DREAM) Proc. Mobicom '98, 1998.
[4] Y. Ko and N.H. Vaidya, Location-Aided Routing (LAR) in Mobile Ad Hoc Networks Proc. Mobicom '98, pp. 66-75, 1998.
[5] L. Blazevic, L. Buttyan, S. Capkun, S. Giordano, J.-P. Hubaux, and J.-Y. Le Boudec, “Self-Organization in Mobile Ad Hoc Networks: The Approach of Terminodes,” IEEE Comm. Magazine, June 2001.
[6] D. Johnson and D. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks Mobile Computing, pp. 153-181, 1996.
[7] T. Camp, J. Boleng, B. Williams, L. Wilcox, and W. Navidi, Performance Comparison of Two Location Based Routing Protocols for Ad Hoc Networks Proc. 20th Ann. Joint Conf. IEEE Computer and Comm. Soc. (INFOCOM 2002), pp. 1678-1687, June 2002.
[8] V. Park and S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks Proc. 18th Ann. Joint Conf. IEEE Computer and Comm. Soc. (INFOCOM), pp. 1405-1414, Apr. 1997.
[9] C. Perkins and E. Royer, Ad Hoc on Demand Distance Vector (AODV) Routing Proc. Second IEEE Workshop Mobile Computing Systems and Applications, pp. 90-100, Feb. 1999.
[10] F. Bai, N. Sadagopan, and A. Helmy, IMPORTANT: A Framework to Systematically Analyze the Impact of Mobility on Performance of RouTing Protocols for Adhoc NeTworks Proc. IEEE Infocom, pp. 825-835, Apr. 2003.
[11] B. Karp, Geographic Routing for Wireless Networks PhD dissertation, Harvard Univ., Oct. 2000.
[12] L. Breslau et al., "Advances in Network Simulation," Computer, vol. 33, no. 5, May 2000, pp. 59-67.
[13] W. Su, S.-J. Lee, and M. Gerla, Mobility Prediction and Routing in Ad Hoc Wireless Networks Int'l J. Network Management, no. 11, vol. 1, Feb. 2001.
[14] W. Su and M. Gerla, IPv6 Flow Handoff in Ad-Hoc Wireless Networks Using Mobility Prediction Proc. IEEE GLOBECOM '99, pp. 271-275, 1999.
[15] W. Su, Motion Prediction in Mobile/Wireless Networks PhD dissertation, UCLA Computer Science Dept., Dec. 1999.
[16] S.-J. Lee, W. Su, and M. Gerla, Ad Hoc Wireless Multicast with Mobility Prediction Proc. IEEE Int'l Conf. Computer Comm. and Networks (ICCCN '99), pp. 4-9, Oct. 1999.
[17] N. Verma, Mobility Prediction in Ad Hoc Networks and Its Application to Routing Research Workshop, Virginia Tech, May 2002.
[18] S.H. Shah and K. Nahrstedt, Predictive Location-Based QoS Routing in Mobile Ad Hoc Networks Proc. IEEE Int'l Conf. Comm. (ICC '02), 2002.
[19] Y. Yu, R. Govindan, and D. Estrin, Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks Technical Report UCLA/CSD-TR-01-0023, UCLA Computer Science Dept., May 2001.
[20] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, Geographic Routing without Location Information Proc. MobiCom '03, 2003.
[21] G.T. Sibley, M.H. Rahimi, and G.S. Sukhatme, Robomote: A Tiny Mobile Robot Platform for Large-Scale Ad-Hoc Sensor Networks Proc. IEEE Int'l Conf. Robotics and Automation (IRCA), 2002.
[22] S. Giordano and M. Hamdi, Mobility Management: The Virtual Home Region technical report, Oct. 1999.
[23] C. Shete, S. Sawhney, S. Herwadka, V. Mehandru, and A. Helmy, Analysis of the Effects of Mobility and Node Density on the Grid Location Service in Ad Hoc Networks Proc. IEEE Int'l Conf. Comm. (ICC), June 2004.
[24] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, Routing with Guaranteed Delivery in Ad Hoc Wireless Networks ACM Wireless Networks, Nov. 2001.
[25] D. Son, A. Helmy, and B. Krishnamachari, The Effect of Mobility-Induced Location Errors on Geographic Routing in Ad Hoc Networks: Analysis and Improvement Using Mobility Prediction Proc. IEEE Wireless Comm. and Networking Conf. (WCNC), Mar. 2004.
[26] D.B. Johnson and D.A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks Mobile Computing, T. Imielinski and H.F. Korth, eds., vol. 353, Kluwer Academic Publishers, 1996.
[27] I. Stojmenovic, M. Russell, and B. Vukojevic, Depth First Search and Location Based Routing and QoS Routing in Wireless Networks Computers and Informatics, vol. 21, no. 2, pp. 149-165, 2002.
[28] N. Sadagopan, F. Bai, B. Krishnamachari, and A. Helmy, PATHS: Analysis of PATH Duration Statistics and Their Impact on Reactive MANET Routing Protocols Proc. Fourth ACM International Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), June 2003.
Index Terms:
Location error, mobility prediction, mobile ad hoc networks, wireless sensor networks.
Citation:
Dongjin Son, Ahmed Helmy, Bhaskar Krishnamachari, "The Effect of Mobility-Induced Location Errors on Geographic Routing in Mobile Ad Hoc and Sensor Networks: Analysis and Improvement Using Mobility Prediction," IEEE Transactions on Mobile Computing, vol. 3, no. 3, pp. 233-245, July 2004, doi:10.1109/TMC.2004.28
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb