Abstract-In this paper, we propme a novel general technique, hased on renewal theory, for analyzing niohility mndels in ad hoc networks. Our technique rnahles an accurate derivation of the steady state distrihution functions for nude movenient parameters such as distnnre and speed. We first apply our technique to the random waypoint model and provide alternative proofs for previous claims about the discrepancy between the steady slate average speed and the average speed userialed with the simulated distrihution [l]. Our main contribution i 9 a new methodology tiw simulating mobility which guarantees steady date for node movement distrihutinns from the start of the simulation. Our methodology enahles the correct and efficient siniuiation of a desired steady state distrihutinn, and can he iniplemented in a manner transparent to the user. We support our claims thmugh hotli formal proofs as well as extensive simulations. The defining characteristics of mobile ad hoc networks include the lack of a fixed communication infrastructure, limited resources for computation and energy. and the mobility of the network nodes. Consequently, ad hoc network protocols need to be decentralized. need to use limited computational and energy power. and should he robust to h e movement of the nodes. While the notions of "decentralized" protocols. and energy-and computational-efficiency can be formalized and indeed has been done in previous studies (e.g.. see [21. [31, [4]), the notion of robustness to mobility is still vague. One of the main hurdles in making this notion precise is the lack of analytical models for capturing mobility. Simulations provide a valuable means to compare different protocols and study their performance in terms of efficiency and robustness. Indeed. network simulation environments such as ns-2 [SI. GloMoSim [6]. Qualnet 171. or @net [81 are the most commonly used tool to evaluate and compare the performance of mobile ad hoc networks (MANET) protocols. Since mobility models are inherently probabilistic. the assumption is that averaging over suficiently many runs will lead to a good estimate. One of the problems with existing simulations of the underlying mobility models is that the simulation may not capture the steady state behavior since the convergence time may exceed the length of the simulation. This was noted in a . Analytical: We present the random waypoint model as a renewal process and derive an accurate characterization of the steady-state distributions of speed and residual distance. given arbitrary distributions for speed and distance of individual node movements. Our analysis provides a derivation of the steady state average speed for the random waypoint model and contirms previous claims that there may be significant discrepancies between the steady state average and the average specified by the user [I]. . Methodological: A useful property of our analysis is that we are able to quantitatively characterize the steady state di.striDiitions rather than specific parameters thereof. such as the expectation or particular moments. We exploit this generality to provide a novel methodology for simulating mobility with arbitrary steady state distributions. Importantly. our methodology guarantees steady state for node movement distributions from the start of the sbiiulation. thus enabling die efficient simulation of large-scale ad hoc networks (see Theorem 3 and Corollary 3.1). Furthermore. it can be implemented in a manner transparent to the user. We support our claims through both' formal proofs as well as extensive simulations. Finally. we illustrate the generality of our analysis and methodology by applying them to the random waypoint model with arhiumy pause time distributions. uniformly at random from a given interval. the speed o f a node in steady state is not necessarily from the same distribution; indeed. it was argued that the two may significantly differ [l].  454
Another related work is that of Lin, Noubir, and Rajaraman REF that studies a class of mobility models where travel distance and travel speed between transition points can be modeled as a renewal process.
Mobility models for ad hoc network simulation
IEEE INFOCOM 2004
IEEE INFOCOM 2004
Computer Science