DOC PREVIEW
UConn CSE 3300 - Perfect Simulation and Stationarity

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

TECHNICAL REPORT IC/2004/59; http://lcawww.epfl.ch/Publications/LeBoudec/lebvoj04.pdf 1Perfect Simulation and Stationarity of a Class ofMobility ModelsJean-Yves Le Boudec and Milan Vojnovi´cAbstract—We define “random trip", a generic mobilitymodel for independent mobiles that contains as specialcases: the random waypoint on convex or non convexdomains, random walk with reflection or wrapping, citysection, space graph and other models. We use Palmcalculus to study the model and give a necessary andsufficient condition for a stationary regime to exist. Whenthis condition is satisfied, we compute the stationary regimeand give an algorithm to start a simulation in steady state(perfect simulation). The algorithm does not require theknowledge of geometric constants. For the special case ofrandom waypoint, we provide for the first time a proof anda sufficient and necessary condition of the existence of astationary regime. Further, we extend its applicability toa broad class of non convex and multi-site examples, andprovide a ready-to-use algorithm for perfect simulation.For the special case of random walks with reflection orwrapping, we show that, in the stationary regime, themobile location is uniformly distributed and is independentof the speed vector, and that there is no speed decay.Our framework provides a rich set of well understoodmodels that can be used to simulate mobile networks withindependent node movements. Our perfect sampling isimplemented to use with ns-2, and it is freely availableto download from http://ica1www.epfl.ch/RandomTrip.I. INTRODUCTIONA. Mobility Models and StationarityOur goal is to provide a class of mobility models(1) that is rich enough to accommodate a large varietyof examples and (2) whose simulation can easily bemastered. The latter point is motivated by recent findingsabout the random waypoint, an apparently simple modelthat fits in our framework. The simulation of the randomwaypoint poses a surprising number of challenges, suchas speed decay, a change in the distribution of locationand speed as the simulation progresses [16], [12], [14],[8]. All of these observations are related to the existenceof a stationary regime. Camp, Navidi and Bauer [14]point out that if the model has a stationary regime, it isAuthor affiliations: Jean-Yves Le Boudec, EPFL, CH-1015, Lau-sanne, Switzerland, Email: [email protected]; Milan Vo-jnovi´c, Microsoft Research Ltd, CB3 0FB Cambridge, United King-dom, Email: [email protected] to simulate it in this regime; otherwise, if theinitial configuration is not sampled from the stationaryregime, the performance evaluation of a system understudy may be biased and non reproducible.B. Perfect SimulationA standard method for avoiding such a bias is to(1) make sure the used model has a stationary regimeand (2) remove the beginning of all simulation runs inthe hope that long runs converge to stationary regime.However, as we show now, the length of transients maybe prohibitively long for even simple mobility models.Our example is the space graph explained in Figure 1.There are a little less than 5000 possible paths; inFigure 1 we show the distribution of the path used by themobile at time t, given that initially a path is selecteduniformly among all possible paths (i.e. the mobile isinitially placed uniformly among all nodes). This wasobtained analytically (see Appendix for details). Figure 1illustrates that the transient period may be long comparedto typical simulation lengths (for example 900 sec in[5]). A major difficulty with transient removal is toknow when the transient ends; if it may be long, aswe illustrated, considerable care should be used. Analternative, called “perfect simulation", is to sample theinitial simulation state from the stationary regime. Formost models this is hard to do, but, as we show, this isquite easy (from an implementation viewpoint) for therandom trip model. Perfect simulation for the randomwaypoint was advocated and solved by Navidi andCamp in [13] who also give the stationary distribution(assuming location and speed are independent in thestationary regime, an issue later resolved in [10] usingthe Palm techniques in this paper).C. The Palm Calculus FrameworkThe derivations in [13] involve long and sophisticatedcomputations. We use a different approach, based onPalm calculus, a set of formulas that relate time averagesto event averages. Palm calculus is now well established,but not widely used or even known in applied areas.For a quick overview of Palm calculus, see [11]; forThis is the version with appendix of the Infocom'05 paper with same titleInfocom 2005 Best Paper Award0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000246x 10−4t=50 secondspathP0(Patht=path)0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000246x 10−4t=100 secondspathP0(Patht=path)0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000246x 10−4t=300 secondspathP0(Patht=path)0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000246x 10−4t=500 secondspathP0(Patht=path)0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000246x 10−4t=1000 secondspathP0(Patht=path)0 500 1000 1500 2000 2500 3000 3500 4000 4500 50000246x 10−4t=2000 secondspathP0(Patht=path)Fig. 1. Top: “Space Graph", a model proposed by Jardosh et al[9]. A mobile starts from a randomly chosen circle and goes alonga shortest path towards another randomly chosen circle. Numericalspeed is constant = 1.25 m/s. Bounding area 1 km ×1 km. Bottom:Probability distribution of the path used by a mobile at time t.Initially, the path is chosen uniformly among all possible paths. x-axis: path index, sorted by path length; y-axis: probability that thispath is used at time t for t = 50,100,300,500,1000,2000 seconds ofsimulated time. Horizontal solid line: initial distribution; other solidline: time-stationary distribution. The transient lasts for a long time.a full fledged theory, see [1]. This framework allowsus to generalize the results in [13] to a broad classof models, as discussed next. Incidentally, even forthe original random waypoint model, we provide newelements: a proof that a stationary regime exists whenvmin> 0 and a sampling algorithm that, for complicated,non convex areas, does not require a priori computationof geometric integrals. More fundamentally, the Palmcalculus framework allows us derive simple samplingalgorithms for the generic random trip model – a taskthat would be formidable without this tool.D. Contributions of This


View Full Document

UConn CSE 3300 - Perfect Simulation and Stationarity

Download Perfect Simulation and Stationarity
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Perfect Simulation and Stationarity and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Perfect Simulation and Stationarity 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?