IMPORTANT: An evaluation framework to study the 

"Impact of Mobility Patterns On RouTing in Ad-hoc NeTworks"

(under the MARMALADeS (MARS) Research Project )  

　

Fan Bai (now at General Motors Research Labs), Narayanan Sadagopan (now at Yahoo! Research), Prof. Ahmed Helmy  

Affiliation: Mobile Wireless Networks Design and Testing Group (NOMADS),

Dept. of Electrical Engineering, 

Viterbi School of Engineering, 

University of Southern California

　

　

[Overview]

A Mobile Ad hoc Network (MANET) is a collection of wireless nodes communicating with each other without any infrastructure. Among other impacting factors, mobility plays an important role in determining the protocol performance in MANET. To study the impact of mobility on performance of Mobile Ad Hoc Network (MANET) routing protocols in a systematic way, we propose the IMPORTANT (Impact of Mobility Patterns On Routing proTocol in the mobile Ad hoc NeTworks) framework.

In this framework, mobility is viewed as a multi-dimensional evaluation space, with each dimension to represent a specific mobility characteristic. Various protocol independent metrics are proposed to capture interesting mobility characteristics of mobility space and connectivity graph. By using a rich set of parameterized mobility models (including Random Waypoint, Random Walk, Reference Point Group Mobility, Freeway, Manhattan and City Section models), several 'test-suite' scenarios are chosen carefully to span the mobility space.

We demonstrate the utility of our test-suite by evaluating various MANET routing protocols, including traditional routing protocols (DSR, AODV and DSDV) and mobility-assisted protocol (MAID). For traditional protocols, our results show that the protocol performance may vary drastically across mobility models. This effect is explained by the interaction of the mobility characteristics with the connectivity graph properties (link duration and path duration), in both a qualitative way and a quantitative way. We also attempt to decompose the protocols into mechanistic ``building blocks'' to gain a deeper insight into the performance variations across protocols in the face of mobility. 

　

For mobility-assisted protocol, the results indicate that the protocol performance at transitional state is significantly affected by mobility while the protocol performance at steady state is less sensitive to the underlying mobility. This phenomenon is also explained by the interaction of mobility characteristics with the connectivity graph properties (characteristics of age gradient tree).

Via our studies, we believe that IMPORTANT framework is a generic framework to evaluate the protocol performance for different MANET routing protocols with different mechanisms. I wish that the deep understanding of mobility gained in this thesis could help in designing efficient protocols for the wireless networks of the future.

　

　

[Research Components and Publications]

IMPORTANT Evaluation Framework: Impact of Mobility Patterns On conventional Routing proTocol in mobile Ad hoc NeTwork

Highlights: This study introduces the IMPORTANT framework for systematic modeling and characterization of mobility by presenting the concept of mobility dimensions and metrics. Mobility dimensions include spatial correlation, temporal correlation and obstacles. A 'rich' set of mobility models (Manhattan, Freeway, Group and Random mobility) are identified to span these dimensions. The study challenges the common practice of using random mobility in wireless networking research, and clearly establishes the need for more realistic mobility models. This is achieved by showing the drastic difference between ad hoc routing performance over realistic mobility and that over random mobility. Using a building-block analysis, the study also answers questions of how and why mobility modeling is important.

　

PATH Analysis Methodology: modeling PATH duration distributions and their impact on routing performance 

Highlights: This study investigates fundamental characteristics of mobile networks connectivity. It shows that, contrary to common assumptions, that the 'link' durations in mobile networks are 'not' exponentially distributed. It further establishes, for the first time, that the shortest 'path' duration is indeed 'exponentially distributed' for random and correlated mobility models. These results are used to establish first order models for throughput and overhead in ad hoc networks using path duration statistics.

　

MAID Analysis Study: impact of mobility on Mobility-Assisted Information Diffusion (MAID) protocol in mobile ad hoc network

Highlights: This study analyzes a class of protocols, MAID, that utilize mobility for information diffusion. MAID uses encounter information to create age gradients towards the target, and can be used for discovering resources, routing or locating nodes efficiently in future mobile networks. Analytical models are developed to evaluate MAID's performance during its various (transient and steady-state) phases of operation. Extensive simulations are used to validate these models and to study the sensitivity of MAID to a rich set of mobility models. We find that although MAID is sensitive to the mobility pattern, its steady state performance is, surprisingly, insensitive to velocity. We identify the properties of the 'age gradient tree' as the key factor to explain this interplay between mobility and the MAID protocols.

　

　

[Mobility Trace Generator and Analysis Toolbox]

The USC mobility generator tool is a set of mobility scenario generators, including Random Waypoint model, Reference Point Group Mobility model, Freeway mobility model and Manhattan mobility model. The traces generated by this tool are compatible with the ns-2 simulator. Those traces could be either directly used in ns-2 simulator or easily analyzed by the other programs.

　

The USC mobility analysis tool is a toolbox to analyze the mobility characteristics (including relative speed, temporal dependence, spatial dependence, and node density) and connectivity graph characteristics (including link duration and path duration) for a specific mobility scenario. The traces input into the analysis tool should be compatible with the ns-2 mobility trace format.

　

　

[Impact of IMPORTANT framework and feedback]

The IMPORTANT framework (both publications and software toolbox) has been widely used in the area of the mobility modeling and analysis in the wireless network research society. More than 20 research groups in different universities and research labs across the world had utilized the IMPORTANT framework. Some of the citation and comments are listed here.

　

You are also welcome to provide your valuable comments and feedback via email to fan_bai@yahoo.com, so that we can continue to improve our research, gain better understanding of user mobility, and contribute to the research community.

　

[Related Project]

A community-wide library of mobile wireless networks (mainly WLANs) from various university campuses (or the Mobility Library "MobiLib").

　

　

[Acknowledgement]

This research is part of the MARMALADeS Research Project under the supervision of Prof. Ahmed Helmy at EE dept, USC.
This material is based upon work supported by the National Science Foundation under Grant No. 0134650 and Intel Research Grant.
Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

　

This Website is still under construction´ More to come´ Maintained by Fan Bai (email: fan_bai@yahoo.com). Last Update: 8/15/2005