Sociological orbit based mobility profiling and routing for wireless networks
MetadataShow full item record
A study of wireless users' mobility has been proven beneficial to several applications such as radio link lifetime estimation, location prediction, resource allocation, etc. However, the suggested approaches to studying mobility have varied in terms of the details of the mobility information required. In our empirical study, we show that each network user has a probabilistic list of places (e.g., buildings on campus) to visit each day, also referred to as a mobility profile. We further show that over a period of time (e.g., a week) a user may repeatedly follow a mixture of mobility profiles with certain probabilities, also referred to as a sociological orbit. Unlike earlier work, we present a novel profiling technique capable of processing sporadic mobility data (which is more commonly found) and building mobility profiles for each user, using a Mixture of Bernoulli's distribution based on the Expectation-Maximization algorithm. We demonstrate the usefulness of our mobility profiles in hub-level location predictions with 10% to 30% higher accuracy than a common statistical method. We propose a suite of Sociological Orbit aware Location Approximation and Routing (SOLAR) protocols that leverage upon mobility profile information exchange. Within MANET, extensive performance analysis shows that our SOLAR variations significantly outperform conventional routing protocols like Dynamic Source Routing (DSR) and Location Aided Routing (LAR) in terms of higher data throughput, lower control overhead, and lower end-to-end delay. Within Intermittently Connected Mobile Ad hoc Networks (ICMAN), similar results are obtained by comparing our multi-path hub-level routing method called SOLAR-HUB, and two variations of user-level routing techniques (S-SOLAR-KSP and D-SOLAR-KSP) based on "contact probabilities" with the performance of Epidemic Routing. Finally, we formulate a novel routing problem within probabilistic graphs of finding an optimal delivery sub-graph that maximizes the delivery probability. Our multi-fold solution proves the hardness of our optimization problem and presents an algorithm to approximate the objective function. We then model user mobility with Semi-Markov Processes to compute pair-wise user contact probabilities, and propose and highlight the superiority of an edge-constrained routing protocol over a probabilistic routing protocol, and an epidemic routing protocol proposed in literature for intermittently connected networks.