This project is no longer active; this page is no longer updated.
Related projects: [CRAWDAD], [Wi-Fi-measurement]
Related keywords: [manet], [wifi]
Mobility modeling: Much research in mobile computing, including many papers on ad hoc networks, wireless networks, and pervasive computing, evaluated their proposed systems or algorithms through simulation; since they dealt with mobile devices, the simulation included a mobility model. Most such research, unfortunately, used woefully inadequate models based on random-walk behavior ("random waypoint" and similar models). Building upon traces collected from Dartmouth's wireless network [see the Wi-Fi-measurement project], we derived mobility models and parameters that more closely match the mobility behaviors of real users. Papers include [kim:anomaly, kim:jclassify, kim:classify, kim:wardriving, kim:mobility, kim:hotspots, lee:thesis, mare:models].
Mobility prediction: Leveraging Dartmouth's collection of wireless-network data [see the Wi-Fi-measurement project], we developed and evaluated methods to predict the next access point where a Wi-Fi device was likely to associate, based on its past history. There was a lot of prior work that provided nice theoretical results; our papers were the first to evaluate all those algorithms with real mobility data. The results show that the more sophisticated algorithms do not provide any substantial advantage, and that simple predictors suffice. Papers include [song:thesis, song:dtn, song:chapter, song:reserv, song:jpredict, song:predict].
MANET and ad hoc networks: Mobile ad hoc networks (MANET) were a subject of frequent study. Most researchers evaluated their systems and algorithms using simulation -- but most such simulations depended on models of the physical layer that were overly simplistic. We evaluated the relative performance of MANET simulations and MANET experiments. In the process, we identified the common assumptions made in MANET research and quantitatively showed how simulation results will not match reality unless good models are used. We conducted the largest-ever outdoor experiment with multiple routing algorithms, and developed new ways to drive a simulator with conditions that match those in the experiment. Papers include [newport:axioms, newport:thesis, kotz:axioms, gray:compare, liu:jdirex, liu:direx].
Modeling: Minkyong Kim, Jeff Fielding, Songkuk Kim, and David Kotz.
Prediction: Libo Song, Udayan Deshpande, Ravi Jain, David Kotz, Ulas Kozat, and Xiaoning He.
MANET and ad hoc networks: Calvin Newport, Yougu Yuan, Robert S. Gray, Jason Liu, Chip Elliott, David M. Nicol, Nikita Dubrovsky, Aaron Fiske, Christopher Masone, Susan McGrath, Luiz Felipe Perrone, and David Kotz.
The views and conclusions contained on this site and in its documents are those of the authors and should not be interpreted as necessarily representing the official position or policies, either expressed or implied, of the sponsor(s). Any mention of specific companies or products does not imply any endorsement by the authors or by the sponsor(s).
[Also available in BibTeX]
Papers are listed in reverse-chronological order;
click an entry to pop up the abstract.
For full information and pdf, please click Details link.
Follow updates with RSS.
We implemented and compared the prediction accuracy of several location predictors drawn from four major families of domain-independent predictors, namely Markov-based, compression-based, PPM, and SPM predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors.
Although other researchers have explored mobility prediction in hypothetical scenarios, evaluating their predictors analytically or with synthetic data, few studies have been able to evaluate their predictors with real user mobility data. As a first step towards filling this fundamental gap, we work with a large data set collected from the Dartmouth College campus-wide wireless network that hosts more than 500 access points and 6,000 users. Extending our earlier work that focuses on predicting the next-visited access point (i.e., location), in this work we explore the predictability of the time of user mobility. Indeed, our contributions are two-fold. First, we evaluate a series of predictors that reflect possible dependencies across time and space while benefiting from either individual or group mobility behaviors. Second, as a case study we examine voice applications and the use of handoff prediction for advance bandwidth reservation. Using application-specific performance metrics such as call drop and call block rates, we provide a picture of the potential gains of prediction.
Our results indicate that it is difficult to predict handoff time accurately, when applied to real campus WLAN data. However, the findings of our case study also suggest that application performance can be improved significantly even with predictors that are only moderately accurate. The gains depend on the applications’ ability to use predictions and tolerate inaccurate predictions. In the case study, we combine the real mobility data with synthesized traffic data. The results show that intelligent prediction can lead to significant reductions in the rate at which active calls are dropped due to handoffs with marginal increments in the rate at which new calls are blocked.
In this paper, we present a general methodology for extracting mobility information from wireless network traces, and for classifying mobile users and APs. We used the Fourier transform to convert time-dependent location information to the frequency domain, then chose the two strongest periods and used them as parameters to a classification system based on Bayesian theory. To classify mobile users, we computed diameter (the maximum distance between any two APs visited by a user during a fixed time period) and observed how this quantity changes or repeats over time. We found that user mobility had a strong period of one day, but there was also a large group of users that had either a much smaller or much bigger primary period. Both primary and secondary periods had important roles in determining classes of mobile users. Users with one day as their primary period and a smaller secondary period were most prevalent; we expect that they were mostly students taking regular classes. To classify APs, we counted the number of users visited each AP. The primary period did not play a critical role because it was equal to one day for most of the APs; the secondary period was the determining parameter. APs with one day as their primary period and one week as their secondary period were most prevalent. By plotting the classes of APs on our campus map, we discovered that this periodic behavior of APs seemed to be independent of their geographical locations, but may depend on the relative locations of nearby APs. Ultimately, we hope that our study can help the design of location-aware services by providing a base for user mobility models that reflect the movements of real users.
In this paper, we present a general methodology for extracting mobility information from wireless network traces, and for classifying mobile users and APs. We used the Fourier transform to convert time-dependent location information to the frequency domain, then chose the two strongest periods and used them as parameters to a classification system based on Bayesian theory. To classify mobile users, we computed diameter (the maximum distance between any two APs visited by a user during a fixed time period) and observed how this quantity changes or repeats over time. We found that user mobility had a strong period of one day, but there was also a large group of users that had either a much smaller or much bigger primary period. Both primary and secondary periods had important roles in determining classes of mobile users. Users with one day as their primary period and a smaller secondary period were most prevalent; we expect that they were mostly students taking regular classes. To classify APs, we counted the number of users visited each AP. The primary period did not play a critical role because it was equal to one day for most of the APs; the secondary period was the determining parameter. APs with one day as their primary period and one week as their secondary period were most prevalent. By plotting the classes of APs on our campus map, we discovered that this periodic behavior of APs seemed to be independent of their geographical locations, but may depend on the relative locations of nearby APs. Ultimately, we hope that our study can help the design of location-aware services by providing a base for user mobility models that reflect the movements of real users.
In this study, we begin with a large outdoor routing experiment testing the performance of four popular ad hoc algorithms (AODV, APRL, ODMRP, and STARA). We present a detailed comparative analysis of these four implementations. Then, using the outdoor results as a baseline of reality, we disprove a set of common assumptions used in simulation design, and quantify the impact of these assumptions on simulated results. We also more specifically validate a group of popular radio models with our real-world data, and explore the sensitivity of various simulation parameters in predicting accurate results. We close with a series of specific recommendations for simulation and ad hoc routing protocol designers.
We implemented and compared the prediction accuracy of several location predictors drawn from two major families of domain-independent predictors, namely Markov-based and compression-based predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors. Predictors of both families fail to make a prediction when the recent context has not been previously seen. To overcome this drawback, we added a simple fallback feature to each predictor and found that it significantly enhanced its accuracy in exchange for modest effort. Thus the Order-2 Markov predictor with fallback was the best predictor we studied, obtaining a median accuracy of about 72% for users with long trace lengths. We also investigated a simplification of the Markov predictors, where the prediction is based not on the most frequently seen context in the past, but the most recent, resulting in significant space and computational savings. We found that Markov predictors with this recency semantics can rival the accuracy of standard Markov predictors in some cases. Finally, we considered several seemingly obvious enhancements, such as smarter tie-breaking and aging of context information, and discovered that they had little effect on accuracy. The paper ends with a discussion and suggestions for further work.
We found that most of the users of Dartmouth's network have short association times and a high rate of mobility. This observation fits with the predominantly student population of Dartmouth College, because students do not have a fixed workplace and are moving to and from classes all day.