Faculty Search Colloquium: Towards Building Robust Mobile Networks: Robust Geographic Routing and Mobility Modeling
|Author:||Ahmed Helmy University of Southern California|
|Date:||February 21, 2006|
In this talk I shall provide a birds-eye view of the research projects and directions pursued by the wireless networking laboratory at USC under my supervision. The talk will focus on two main topics: (A) robust geographic services in wireless sensor and ad hoc networks, and (B) mobility modeling and analysis.
(A) Geographic services refer to classes of protocols and location-based applications. The talk outlines our research on of robust geographic routing. Geographic routing provides efficient routing in ad hoc and sensor networks. Its stateless nature and low overhead give it an edge over traditional ad hoc routing. Correctness of geographic routing has been proven under assumptions of accurate location information and ideal channel characteristics. The first half of this talk focuses on issues of sensitivity of geographic routing to inaccurate location information and lossy link characteristics. Our study on geographic face routing shows how correctness is violated with inaccuracy. A novel micro-level algorithmic analysis of planarization algorithms reveals the bounds and conditions of its correctness. Our study shows how performance can degrade drastically with inaccuracy. Effective protocol modifications are provided that achieves near-perfect performance even with large loc alization errors. Then the 'weakest link' problem is introduced in greedy geographic routing with lossy links. A channel model is developed based on real traces from deployed sensor networks. The notion of 'black listing' based on link quality is introduced, and the following trade-off is articulated: If only highest quality links are used, this leads to longer paths with larger number of hops and may lead to disconnections, whereas if no black listing is performed (as in traditional greedy forwarding) very poor packet delivery is incurred. The study investigates several distance-based and quality-based black-listing strategies and introduces the energy-optimal metric for geographic forwarding.
(B) In mobile networks, one of the main factors affecting protocol performance is mobility. Relative movement of the nodes leads to link breakage, triggering protocol mechanisms to react to topology dynamics, and subsequently affecting throughput and overhead. To capture the essence of such interaction between the mobility characteristics and the protocol mechanistic building blocks, we propose the IMPORTANT mobility framework. This framework defines three mobility dimensions, including (i) spatial correlation, (ii) temporal correlation and (iii) geographic restrictions. We use a rich set of parameterized mobility models, including Freeway, Manhattan, Group mobility and Random Waypoint, to span those dimensions. Several wireless routing protocols, including DSR, AODV, DSDV, GPSR and GLS, are studied across the different mobility models. The results clearly show the performance sensitivity of these protocols to mobility. The talk attempts to answer the following: To what degree does mobility affect performance? Why and how does it affect performance? The answers lie in the effects of mobility on link and path characteristics (through the PATHs study), and the interaction between mobility and the protocols mechanisms (through the BRICS study). Current directions include trace-based mobility models on campus and for vehicular networks. We have recently finished the IMPACT study analyzing the most comprehensive set of wireless networks traces on university campuses (covering more than 12,000 users and 4 major universities). Our findings point to distinct, yet consistent, patterns of wireless users behavior. We leverage our understanding to propose new protocols for future wireless and ad hoc networks. [nile.usc.edu/MobiLib].
Dr. Ahmed Helmy received his Ph.D. in Computer Science in 1999 with Prof. Deborah Estrin from the University of Southern California (USC), M.S. in Electrical Engineering 1995 from USC, MS Eng. Math 1994 and B.S. in Electronics and Communications Engineering in 1992 from Cairo University, Egypt. He has been on the faculty of the Electrical Engineering Dept at USC since Fall 1999.
Dr. Helmy is conducting research on design and analysis of mobile ad hoc networks and wireless sensor networks, in addition to protocol testing techniques. He currently has three active NSF projects (MARS, ACQUIRE and STRESS). In 2002, Dr. Helmy received the National Science Foundation (NSF) CAREER Award for his research on "Resource Discovery, Query Resolution, Rendezvous and Mobility Modeling in Large-Scale Wireless Ad Hoc and Sensor Networks" (MARS). He received the Zumberge award for individual research (in 2000) from USC to pursue work on power-aware wireless routing protocols. He also founded and is currently directing the Electrical Engineering laboratory for wireless networking (nile.usc.edu). He is currently co-establishing a new wireless networking laboratory at USC.