| Home |
Location is an important feature for many applications, and wireless networks can better serve their clients by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors, using a two-year trace of the mobility patterns of over 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. The surprising results provide critical evidence for anyone designing or using mobility predictors.
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.
Wireless local area networks (WLANs) are emerging as a popular technology for access to the Internet and enterprise networks. In the long term, the success of WLANs depends on services that support mobile network clients.
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.
URL: http://www.ieee-infocom.org/2004/technicalprogram.htm
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2004-491/
URL: http://doi.acm.org/10.1145/965732.965747
URL: http://www.sigmobile.org/mobicom/2005/posters.html
Traditional mobile ad~hoc network (MANET) routing protocols assume that contemporaneous end-to-end communication paths exist between data senders and receivers. In some mobile ad~hoc networks with a sparse node population, an end-to-end communication path may break frequently or may not exist at any time. Many routing protocols have been proposed in the literature to address the problem. But few were evaluated in a realistic ``opportunistic'' network setting. We use simulation and contact traces (derived from logs in a production network) to evaluate and compare five existing protocols: direct-delivery, epidemic, random, PRoPHET, and Link-State, as well as our own proposed routing protocol. We show that the direct delivery and epidemic routing protocols suffer either low delivery ratio or high resource usage, and other protocols make tradeoffs between delivery ratio and resource usage.