D evelop m en t O f A Trace G eneration A nd A nalysis Softw are For R and om M ob ility M odels X ian g Cui BSc., University of Northern British Columbia, 2004 Thesis Submitted In Partial Fulfillment Of The Requirements For The Degree Of Master Of Science in Mathematical, Computer, and Physical Sciences (Computer Science) The University of Northern British Columbia May 2006 © Xiang Cui, 2006 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Library and Archives Canada Bibliotheque et Archives Canada Published Heritage Branch Direction du Patrimoine de I'edition 395 Wellington Street Ottawa ON K1A 0N4 Canada 395, rue Wellington Ottawa ON K1A 0N4 Canada Your file Votre reference ISBN: 978-0-494-28365-3 Our file Notre reference ISBN: 978-0-494-28365-3 NOTICE: The author has granted a non­ exclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distribute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. AVIS: L'auteur a accorde une licence non exclusive permettant a la Bibliotheque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par telecommunication ou par I'lnternet, preter, distribuer et vendre des theses partout dans le monde, a des fins commerciales ou autres, sur support microforme, papier, electronique et/ou autres formats. The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. L'auteur conserve la propriete du droit d'auteur et des droits moraux qui protege cette these. Ni la these ni des extraits substantiels de celle-ci ne doivent etre imprimes ou autrement reproduits sans son autorisation. In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis. Conformement a la loi canadienne sur la protection de la vie privee, quelques formulaires secondaires ont ete enleves de cette these. While these forms may be included in the document page count, their removal does not represent any loss of content from the thesis. Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant. i*i Canada Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Dedicated to my parents, Cui Jun and Wang Yuan Yuan ii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Abstract Simulation is an integral p art of most research studies in mobile com puting context and building a valid, credible, and appropriately detailed simulation model is crucial for conducting accurate and meaningful simulation study. Al­ though many sim ulation softwares are freely available in the Internet for mobile com puting simulations, we found th a t there is no comprehensive software freely available for the researchers to visualize, analyze, and then generate suitable mobility trace for their simulation study. Lack of such a comprehensive soft­ ware constrains the researchers to choose only from a few models supported in the generic sim ulation softwares and th a t in tu rn questions the validity of most simulation results. This hypothesis has been reaffirmed in a recent survey conducted on the papers published in the proceedings of ACM MobiHoc sym­ posium between 2000 and 2005. T he survey observes th at the credibility of the simulation results has decreased while the use of simulation has increased. P art of this credibility crisis is clearly related to mobility model used to simulate the mobile nodes in the simulation system. We believe th at the availability of a software to choose, visualize, and analyze mobility patterns before generating suitable mobility trace to use in the simulations, would resolve the mobility related concerns raised in the survey. The objective of this thesis is to develop such a software. This thesis presents a mobility generator software called RMobiGen th a t we developed using Java. RM obiGen can be used to specify, visualize, analyze, and then generate mobility traces for various random mobility models. iii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. In addition to its rich functionality, the software has a user friendly interface which increases its appeal for wider use. We followed software engineering techniques and used UML diagram s during analysis and design phases of the development and then implemented using Java. We also surveyed the mobility models proposed in the literature and conducted various experim ents on them using RMobiGen. During the experim entation, we confirmed the phenomena related to mobility models indicated in the literature and also encountered m any new interesting behaviors and patterns. iv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C ontents 1 2 A b s tr a c t...................................................................................................................... v C o n te n ts...................................................................................................................... v List of F ig u res............................................................................................................ x Publications from this th e s is .................................................................................. xi Acknowledgments..................................................................................................... xii In trodu ction 1 1.1 B a c k g ro u n d ...................................................................................................... 1 1.1.1 M otivation............................................................................................. 3 1.1.2 C o n trib u tio n s ...................................................................................... 4 1.1.3 Organization 4 ...................................................................................... R andom M ob ility M odels 5 2.1 In tro d u c tio n ...................................................................................................... 5 2.2 A C lassificatio n ................................................................................................ 6 2.3 Performance M e t r i c s ...................................................................................... 7 2.3.1 Term inology.......................................................................................... 8 v Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 2.4 2.5 3 5 9 2.4.1 Mobility M odels.................................................................................. 9 2.4.2 Simulation Softwares Supporting some Random Mobility Models 15 Summary ........................................................................................................ 18 R M ob iG en 19 3.1 Specification..................................................................................................... 19 3.2 A rch ite ctu re..................................................................................................... 21 3.3 Class D iag ram .................................................................................................. 22 3.4 Modeling Key Operations ........................................................................... 24 3.4.1 Trace G e n e ra tio n .............................................................................. 24 3.4.2 Performance Metrics Computation .............................................. 26 3.4.3 User In te rfa c e ..................................................................................... 28 3.5 4 R ev iew ............................................................................................................... Summary ........................................................................................................ 29 Sim ulation S tu d y 30 4.1 Experimental S e tu p ........................................................................................ 31 4.2 Movement A n a ly sis........................................................................................ 31 4.3 Coverage A nalysis........................................................................................... 36 4.4 Connectivity A nalysis..................................................................................... 40 4.5 Implementation C o m p le x ity ........................................................................ 42 4.6 Summary 43 ........................................................................................................ 44 Sum m ary and Future D irection s vi Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5.1 Summary ......................................................................................................... 44 5.2 Future D ire c tio n s ............................................................................................ 45 B ibliography 46 vii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. List o f Figures 3.1 Internal Structure of Execution T r a c e ...................................................... 21 3.2 Usecase D ia g r a m .......................................................................................... 22 3.3 RMobiGen A r c h ite c tu r e ............................................................................. 23 3.4 Class D iag ram ................................................................................................. 24 3.5 General Scenario Setting Panel ................................................................ 27 3.6 Leg Param eter Setting P a n e l...................................................................... 27 3.7 Mobility Trace Generated .......................................................................... 27 3.8 Individual Stat s u b p a n e l............................................................................. 27 3.9 Scenario Stat s u b p a n e l................................................................................ 27 3.10 Animation su b p an el....................................................................................... 27 3.11 Snapshot s u b p a n e l ....................................................................................... 28 3.12 E x p o rt to NS s u b p a n e l ......................................................................................... 28 4.1 Uniform Speed ............................................................................................. 33 4.2 Normal and Uniform S p e e d s ...................................................................... 33 4.3 Destination-Speed M o d e l........................... 33 viii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.4 Direction-speed-distance M o d e l ................................................................ 33 4.5 Destination-Speed M o d e l............................................................................. 34 4.6 Direction-speed-distance M o d e l ................................................................ 34 4.7 Uniform D irection........................................................................................... 35 4.8 Normal D ir e c tio n .......................................................................................... 35 4.9 Number of L e g s .............................................................................................. 35 4.10 Average Leg Length .................................................................................... 35 4.11 Average Distance T ra v e le d .......................................................................... 36 4.12 Distance Ratio for Random W ay p o in t...................................................... 36 4.13 D estination-speed.......................................................................................... 38 4.14 Destination-time .......................................................................................... 38 4.15 Direction-speed-distance ( R F ) ................................................................... 38 4.16 Direction-speed-distance ( R S ) .................................................................... 38 4.17 Direction-speed-time ( R F ) .......................................................................... 39 4.18 Direction-speed-time ( R S ) .......................................................................... 39 4.19 Direction-distance-time ( R F ) ....................................................................... 39 4.20 Direction-distance-time ( R S ) ....................................................................... 39 4.21 Markov-Destination ( i ) ................................................................................. 40 4.22 Markov-Destination ( | ) ................................................................................. 40 4.23 Connection C h a n g e ....................................................................................... 41 4.24 Session D u r a t i o n .......................................................................................... 41 4.25 Connection C h a n g e ....................................................................................... 41 ix Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.26 Session D u r a t i o n .......................................................................................... 41 4.27 Connection C h a n g e ....................................................................................... 42 4.28 Session D u r a t i o n .......................................................................................... 42 x Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. P u b lication s 1. Alex A. Aravind and X ian g Cui, RMobiGen: A Trace Generation, Scenario Visualization, and Performance Analysis Tool for Random Mobility Models, Submitted for AC M Mobile Computing and Communication Review. 2. Jernej Polajnar, Tyler Nielson, X ian g Cui, and Alex A. Aravind, Simple and Efficient Protocols for Guaranteed Message Delivery in Wireless Ad Hoc Net­ works, Proc. of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications Conference (WiMob), 93-100, 2005. 3. Yong Sun, X iang Cui, and K. Alagarsamy, Efficient Connectionless Semicompulsory Routing Protocols for Mobile Ad-hoc Networks, Proc. of the IA STE D Intl. Conf. on Wireless Networks and Emerging Technologies (W N ET), 484489, 2004. 4. X iang Cui, Yong Sun, and K. Alagarsamy, Simple and Efficient Connectionless Semi-Compulsory Routing Protocols for Mobile Ad-hoc Networks, Proc. of the Intl. Conf. on Wireless Networks (ICW N), 906-909, 2004. XI Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. A ck now ledgm ents First of all, I would like to express my profound gratitude to my supervisor, Dr. Alex Alagarsamy Aravind for his invaluable support and constant encouragement. W ithout his guidance and endless patience this research would not have made it so far. I would also like to thank the members of the Examining Committee, Dr. Robert Tait (Dean of G raduate Studies), Dr. Waqar Haque, Dr. Jing Chen, and the external examiner, for their time and effort on my thesis. Thanks to G raduate Studies Office and the Computer Science Department of University of Northern British Columbia for financially supporting my research through Teaching and Research Assistantships. I am thankful to former graduate students Yong Sun and Baljeet Singh M alhotra for their helpful and fruitful discussions on my research and my fellow graduate stu­ dents Jeyaprakash, Srinivas, and B harath for proofreading the draft of my thesis. I would also like to thank Paul Stokes for maintaining a reliable Tsdev server and Rob Lucas for the computing support. Taking this opportunity, I would like to thank Dr. Alex’s wife, Dr. Mahi and the family for the wonderful family dinners and parties on various events and occasions. Last but not least, I would like to express my deepest gratitude to my family, who have always believed in me and supported me. Their tremendous support made me to come to Canada and earn a M aster’s degree. xii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 1 Introduction 1.1 B ackgr ound Mobile computing is a technology which enables people to connect their comput­ ing and communication devices to networks whenever and wherever they go. The m aturity of technology and the falling cost of equipments make the applications of mobile computing widely available and affordable to both business executives and common users. Most of the traditional wireless networks, such as cellular telephony, personal communication systems, wireless local area networks, etc., are supported by static infrastructure (also called backbone). The infrastructure consists of fixed base stations or access points, which are connected either through wires or by long range wireless transmissions to act as gateways and bridges in the network. However, setting up of a fixed infrastructure is not always viable in ad-hoc situations such as battlefield, emergency search, rescue operation, etc. In such situations, an infrastruc- 1 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. tureless network known as Mobile Ad-hoc Network (MANET) is more attractive. A mobile ad-hoc network is a collection of mobile hosts with wireless interfaces forming a tem porary network without the aid of any established infrastructure or centralized administration. Research studies in mobile computing are carried out mainly through simulations because of their flexibility and cost effectiveness. Building a valid, credible, and appropriately detailed simulation model is crucial for conducting meaningful and ac­ curate simulation study. In most of these simulation based research studies, modeling mobility of participating nodes plays a crucial role. The underlying mobility pattern heavily influences the behavior of the system under investigation. Random mobility models are dominantly used to model the mobility patterns of the mobile nodes in the system. A typical random mobility model is characterized as follows. A collec­ tion of mobile nodes is initially placed within a simulation area and then each node moves randomly within th a t area. It is generally assumed th a t individual nodes move completely independent of each other, which makes the implementation of this class of movement models sufficiently simple. Recently a survey has been conducted on the MANET research papers published in MobiHoc Symposiums proceedings between 2000 to 2005 [11]. In th at, it is observed th a t 75% of the papers used simulations in their research and in th a t simulations 38.5% of the papers used mobility in the study. There are many mobility models proposed in the literature, in th at, the random mobility model called random waypoint is used dominantly (more than 73%) [11]. 2 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1.1.1 M o tiv a tio n Although many simulation softwares are freely available in the Internet for mobile computing simulations, we found th a t there is no comprehensive software freely avail­ able for the researchers with the following characteristics: (i) support for a wide range of random mobility models, (ii) support for visualization and analysis of the mobility trace1 of the chosen model so th a t a suitable choice can be made, (iii) support for performance observations from the mobility trace to get more accurate insight about the system behavior, and (iv) support of a user friendly interface to effectively exploit the supports (i), (ii), and (iii). Lack of such a comprehensive software for generating mobility trace constrains the researchers to choose only from a few models supported in the generic simulation softwares and th a t in tu rn questions the validity of most simulation results. On the other hand, the availability of a comprehensive software to generate, analyze, and adjust various scenarios by suitably controlling the mobility parameters before applying it to the simulation would be extremely useful for the researchers in the mobile computing field. The concern related to credibility of simulations has been reaffirmed in a recent survey showing th a t the credibility of the simulation results has decreased while the use of simulation has increased [11]. P art of this credibility crisis is clearly related to mobility model used to simulate the mobile nodes in the simulation system. The objective of this thesis is to develop a comprehensive mobility trace generator and analysis software. 1T he trails of mobile nodes. 3 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1.1.2 C o n trib u tio n s This thesis presents the mobility generator software called R M ob iG en th a t we de­ veloped using Java. RMobiGen can be used to specify, visualize, analyze, and then generate mobility traces for various random mobility models. In addition to its rich functionality, the software has a user friendly interface which increases its appeal for its wider use. We followed software engineering techniques and used UML diagrams during analysis and design phases of the development and then implemented using Java. We also surveyed the mobility models and some popular softwares supporting the mobility models presented in the literature. Finally, we conducted various ex­ periments on them using RMobiGen. During the experimentation, we confirmed the phenomena related to mobility models indicated in the literature and also encountered many new interesting behaviors and patterns. We believe th a t our work would serve as a guideline for researchers to choose the right model for their simulations. Also, this thesis brings many key concepts and observations scattered in the literature together under a common classification along with some new insights. 1.1 .3 O rg a n iza tio n The rest of the thesis is organized as follows. Chapter 2 reviews random mobility models and relevant performance metrics. Chapter 3 presents the development of RMobiGen and simulation experiments using RMobiGen for various mobility models are described in Chapter 4. The thesis is concluded in Chapter 5. 4 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 2 R andom M obility M odels 2.1 In trod u ction Most simulations use random mobility models to test the protocols, algorithms, or systems under study. In this section, we first describe the random mobility models and the performance metrics used to analyse the models. Then we review the random mobility models presented in the literature and the popular software tools th at have implemented some of these models. Although random mobility models have been analyzed in the literature for complex subspaces like Fish Bowl, Torus, Swiss Flag, etc. [13], the practical implementations are mostly restricted to either 2-dimensional square or 2-dimensional rectangle for ad hoc networks. We consider 2-dimensional rectangle as the region of mobility in RMobiGen. A random mobility model can be viewed as an alternating sequence of pause and a 5 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. continuous movement. We call the continuous movement between any two consecutive pauses as a leg of the mobility. T hat is, pause and leg are the components of a random mobility and it acquires the randomness from the computation of one or both of these two components. Probability distributions are used to generate the random values for these components. Computing a value for a pause is simple and therefore the crux of constructing a mobility model is in computing the legs. 2.2 A C lassification Although random mobility models appear to be simple, their behavior is less obvious, sometimes even counter-intuitive. In this section, we classify the random mobility models based on the way they compute leg and pause. There are five parameters, referred as leg parameters, th a t can be used to compute a leg: i) speed (S'), ii) direction (9), iii) distance (A), iv) time duration (T) and v) destination (D) in the simulation region R. Based on the parameters used to compute the leg, random mobility models can be classified, into five categories: (1) random destination-speed model, (2) random destination-time model, (3) random direction-speed-time model, (4) random directionspeed-distance model, and (5) random direction-time-distance model. We have implemented these five models in RMobiGen. In random direction mod­ els, it is possible for a mobile node to hit the boundary during a leg travel. So, the random direction models require some kind of boundary actions. We have imple­ mented the following three boundary actions suggested in the literature. 6 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1. Reflection: The boundary is treated as a mirror to reflect the node into the mobile region when it hits the boundary. 2. Wrap-around: The node instantaneously reappears at the corresponding posi­ tion on the opposite boundary. 3. Restart: The node pauses at the edge and then generates a new leg to move into the mobile region. Three probability distributions, uniform, normal, and exponential are supported in RMobiGen to compute the parameters and the default distribution is uniform. Next we discuss the performance metrics used to analyze the mobility aspects. 2.3 P erform ance M etrics Performance metrics used to analyze mobility models fall mainly into the following categories. 1. movement metrics: number of legs, leg distance, leg speed, leg duration, etc. 2. connectivity metrics: number of connections, connection duration, connection changes, connection availability, etc. 3. coverage metrics: node distribution, coverage, etc. These metrics, if applicable and meaningful, may be computed for minimum, maximum, average, total, standard deviation, rate, ratio, etc., and also for individual, 7 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. group, or system level. For example, connectivity may be analyzed between two nodes, between one and a group of nodes, or among all nodes. Movement metrics are easy to understand and straightforward to compute. Connectivity and coverage metrics require some elucidation. Communication is a fundamental problem for most applications in any networked systems and achieving effective communication between the mobile nodes is challeng­ ing due to the dynamics involved in the network. In mobile networks, the nodes with transmission range form a dynamic graph called con n ectiv ity graph. The perfor­ mance of most of the communication protocols in this context is heavily influenced by the connectivity and the coverage of this graph. We introduce some terminology related to connectivity and coverage which will be used later in our experiments to compute performance metrics. 2 .3.1 T erm in o lo g y D efinition 2.1 A link is said to exist or be ON between two nodes i and j if they are within each other’s transmission range. Link is a boolean function over time t and it is denoted by link(i, j,t) . Link is a communication channel and it can be generalized to path as follows. D efinition 2.2 A p ath is said to exist or be ON between two nodes i and j if there is a sequence of nodes and the links between consecutive nodes in the sequence are ON. Path is also a boolean function over time t and it is denoted by p a th (i,j,t). 8 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. The next definition is to capture the duration of path existence. The state of the path oscillates between ON and OFF. D efin ition 2.3 We define the interval between ON and immediate OFF state of a path between the nodes i and j as a session. Session is also a boolean function on time t and it is denoted by se ssio n (i,j,t). P ath duration is an im portant metric for testing communication protocols. For example, some protocols referred as connection-oriented protocols require the path between source and destination to be ON throughout the communication. Coverage is influenced by both mobility and transmission range of the nodes. Node distribution and the ratio of the area covered by transmission range to the total area are useful metrics to be analyzed for coverage. Since RMobiGen is a discrete time based simulator, the metrics are computed over discrete times. 2.4 R eview This section reviews the random mobility models proposed in the literature and the simulation softwares which support some of these models. 2 .4.1 M o b ility M o d e ls Brownian Motion in science and random walk in mathematics are historically well known random mobility models. The m athematical description and analysis of Brow­ nian motion goes back at least to 1900 by Louis Bachelier in his PhD thesis and then 9 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. later by Einstein in 1905. First we briefly review these two models. In one dimensional random walk, imagine th a t a walker is moving randomly on the integers [38]. The walker starts at 0 and at every integer time n the walker flips a coin and moves one step to the right if it comes up heads and one step to the left if it comes up tails. This is generalized to n-dimension as the walker is moving randomly on the n-dimensional integer grid. The model has both the time and space increments as 1. T hat is, the walker moves once every 1 time unit and when the walker moves, he or she moves a distance of 1 unit. The random walk model has the following interesting property [38]. P ro p erty 2.1 A random walk on a one or two dimensional surface returns to the origin with probability 1, and when n > 2 the probability of returning to the origin becomes strictly less than 1. Brownian motion is a model of continuous random motion. One of the ways of defining Brownian motion is to look at it as a limit of a simple random walk where the time and space increments approach 0. T hat is, when the time and space increments are close to 0, the random walk appears as almost a continuous motion. Next we discuss the random mobility models used in the mobile computing. In the cellular networks context, where the cells are used in the mobility model, a mobile node chooses one of its neighboring cells to move next. In such cases, the direction change is determined by a probability matrix. This is applicable to random walks on graphs also. In mobile ad hoc networks, there are two classes of models used 10 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. with minor variations and they are referred as random direction/walk models and random waypoint models. We review these models next. In the review, for brevity of reference, we label the models. R andom W a lk /D irectio n M odels This class of models are variations and in some cases generalizations of classical random walk models. We will review them next. R D 1: This model is introduced in [35]. In this model, the movement of each mobile node in the coverage area is characterized by its velocity vector v = (v , 9), where v is the node’s speed and 6 is the direction, measured with respect to the positive x-axis. The position of the node and its velocity vector are updated periodically, by choosing the increments or decrements of 6 and v from the given ranges uniformly. The mobile node th a t exits the coverage area from one side, reenters the coverage area on the opposite side with the same velocity and same direction. R D 2: This model referred as random walk model in [22] is described as follows. Each mobile node randomly chooses a direction in [0, 27r), a speed between 0 and lOm/s and travels for a fixed period (60s). This process repeats. R D 3: This model also referred as random walk model in [22] is described as follows. Each mobile node randomly chooses a direction in [0, 27r), a speed between 0 and lOm/s and travels a fixed number of steps (10 steps). 11 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. This process repeats. RDA: This model referred as Brownian Motion in [31] and renamed as ran­ dom direction model in [25] is described as follows. Each mobile node chooses a direction in [0, 27r) using uniform distribution, a speed value using normal dis­ tribution, and a time from fixed value or from exponential distribution. Then, the node travels in the chosen direction with the chosen speed for the chosen time period. The process repeats. When a node hits the boundary, it bounces off the simulation border with an angle determined by the incoming direction. R D 5: This model a simplified version of R D i and it is introduced in [24], In this model, each node chooses a direction and moves with a constant speed until it hits the boundary. When it hits the boundary, it will be reflected back into the coverage area immediately. R D 6: This model is proposed and referred as random direction model in [26]. It is another simplified version of RDA with pause time and similar to R D 5 without pause time. In this model, each node chooses a direction and a random speed to travel until it hits the boundary. When it hits the boundary, it pauses fo r a fixed time and then chooses a direction in [0 , t t ] to travel into the coverage area. This model was introduced in response to the density wave phenomenon observed in random waypoint model. R D 7: This is a variation to RDQ called modified random direction introduced in [26], and in th a t instead of the nodes always hitting the boundary they may 12 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. choose a random destination along the chosen direction. R D 8: This variation called smooth random mobility model was introduced in [25]. It is a random direction model with the following additional feature called autocorrelation. In this model, (i) the speed is changed incrementally by the current acceleration of the mobile user, and also the direction change is smooth, and (ii) the movement patterns correlate the direction change with the speed change. RD9: This model called random drunken mobility model is implemented in GloMoSim [9]. It is basically the simple random walk on grids, described in the beginning of this section. T hat is, if a node is at a position (x, y) then it can move to one of (x-1, y), (x+1, y), (x, y-1), and (x, y+1) as long as the new position is within the coverage region. R D 10: This model, given in [23], is a generalization of RD9. In this model, the nodes can choose all possible directions. RD11: This model, called Gauss-Markov model, was implemented in [32] as follows: at fixed intervals of time, movement occurs by updating the speed and direction of each mobile node. The next speed and direction is computed based on the current speed and direction. Comparing these models with the models in our classification given in Section 2.2, RD 1, RD 2, RD 4, RD5, and R D 6 are random direction-speed-time models, and 13 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. R D 8 and R D 11 are random direction-speed-time models with Markov property. The models R D 3 and R D 7 are random direction-speed-distance models. The models R D 9 and R D 10 are random direction-time-distance models. R andom W aypoint M odels Random waypoint model is the most popularly used model for simulations in MANET and it has been analyzed extensively in the literature. RW 1: This model is the first in random destination class, introduced in [37], and named as random waypoint in [34], In this model, each node pauses at its current location for a fixed period, which is called pause time, and then randomly chooses a new location and velocity from a uniform distribution to move to. This behavior is continued, alternatively pausing and moving to the new location in the coverage region. This model has been implemented in NS2 [!]■ RW 2: This variation is introduced and used in [28]. Instead of using a constant value, the pause time is also chosen from a uniform distribution. R W 3: This variation called steady-state random waypoint model is introduced in [16]. In this model, the speed and destinations are generated from steady-state distributions derived in [14]. RW 4: In [21], random waypoint model is generalized in such a way th a t the destination is chosen from uniform distribution and velocity and pause time are 14 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. chosen from arbitrary distributions. Comparing these models with the models in our classification, the models R W 1 to R W 4 are random destination-speed models. In some models, particularly proposed in [20, 21], some of the nodes are chosen to be stationary in the beginning. Properties of random mobility models and a simple relationship to random waypoint model is given in [12]. 2 .4 .2 S im u la tio n S oftw ares S u p p o r tin g so m e R a n d o m M o b il­ ity M o d e ls Numerous simulation softwares are available th a t can be used for mobile computing simulations. Here we review only the widely used simulation softwares. 1. NS2: A discrete event simulator developed jointly by UCB, USC/ISI, and Xe­ rox targeted at research over fixed and wireless (local and satellite) networks [1]. It supports random waypoint mobility model. 2. G loM oSim : A scalable simulation environment for wireless and wired network systems with parallel discrete-event simulation capability provided by Parsec, a parallel programming language. GloMoSim is developed at UCLA[2] and it supports random waypoint, random-drunken, RPGM (group mobility) models. 3. Q ualN et: The commercial version of GloMoSim with enhanced features[3]. 15 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4. O P N E T : The largest, most comprehensive library of simulation models for the industry-level network modeling, analysis, and design[4], The OPNET wireless module provides the ability to model many aspects of wireless transmissions. 5. M A TLA B: A general purpose mathematical software package for high per­ formance numerical computation and visualization^]. Simulation for wireless communications is supported by an integrated interactive simulation environ­ ment called Simulink. 6. SW AN : A configurable and scalable simulator designed purely for wireless network simulations [6]. It is organized as independent components th a t can be composed to form a complete wireless network or a sensor network configura­ tions. SWAN’s capabilities are similar to NS2 and GloMoSim, but is claimed to be able to simulate much larger networks. SWAN is developed at Dartm outh College and it supports random waypoint, Brownian, probwaypoint (random direction with predetermined probabilities to choosing same or different direc­ tions), Gauss-Markov, Boundless (RD1) models. In the above list, QualNet, OPNET, and MATLAB are commercial softwares and the rest are free and open source softwares and hence widely used by the academic community. Among the open source softwares, NS2 is the most widely used one. Basically, there are two techniques to incorporate node mobility into the simulators: (i) simulators having internal support for mobility and (ii) mobility trace is generated externally using other softwares and is given as an input to the network simulator. 16 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. For example, in NS2, the following command “$node_($i) random-motion s t a t e ” is specified in the simulation script. Specifying state 1 chooses the random mobility model built in NS2 and choosing state 0 either allows mobility trace from external or keeps the nodes stationary. For GloMoSim and SWAN, the user can choose a mobility model by specifying it in the simulation configuration file. The following tools were designed specifically to generate and/or visualize mobility models. • nam: A visualization tool comes with NS2 distribution allowing users to play­ back simulation output file generated after a simulation is over. It is originally designed for wired network and has the following drawbacks: — animation is limited to only node movements — no statistical insights provided — animation is based on a simulation output file generated after the simu­ lation completion; this process can take lots of time and the output file generated can grow to be hundreds of megabytes. • iN S p ect: Another visualization and animation tool designed for NS2 simulator[10]. It takes a NS2 trace file as the input and displays nodes movement as well as wireless links. The transmissions are displayed with route lines and color coded nodes. Because it can animate a movement scenario without running NS2, com­ pared to nam, iNSpect is a better tool th a t can be utilized with minimal over­ head. However, other than visualization, no statistical analysis is supported. 17 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. • B on nM otion: It is a Java-based tool which generates movement scenarios of a set of random models on grids: random waypoint, M anhattanG rid, GaussMarkov, and RPGM)[8]. Some statistical measures, such as relative mobility, average node degree, and average link duration, are provided. • setd est: This also comes with the NS2 distribution which generates mobility trace for random waypoint model. • m obgen: A tool developed by Tracy Camp’s research group on the steady state distribution for the random waypoint model. 2.5 Sum m ary This Chapter, after presenting a comprehensive overview and a simple classification of various mobility models, provides a review of existing mobility models and the popular simulation softwares th a t implement some of the models. As the number of nodes and movement duration increases, the mobility trace file will become overwhelmingly hard to analyze. This, in most cases, forces the researchers to adopt the mobility trace with little knowledge of what is exactly going on w ith in th e tra c e before app ly in g it to th e sim ulation. T herefore, it is desirable to have the mobility generator and analysis software independent of simulator itself. We present RMobiGen, designed to help the researchers to choose the mobility models suitable for their research, in next Chapter. 18 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 3 R M obiG en This Chapter presents the design and development of RMobiGen, a software of size about 8,000 lines Java code - the major contribution in this thesis. We used software engineering approach during the developmental stages of RMobiGen. We start with the requirement specification. 3.1 S p ecification From the user’s point of view, when the user specifies a mobility model, RMobiGen has to generate the movement trace accordingly. More importantly, it should allow the users to analyze the generated mobility trace for various aspects before exporting it in a required format. This requires a multilevel user interface for the users to navigate the system conveniently, in specifying and analyzing the mobility models. To get the formal specification of the system, we start with use-case diagram. 19 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Constructing an use-case diagram involves the following three steps. • Identification of the actors (the roles played by various users while accessing the system). • Identification of the use-cases (the ways of using the system). • Setting the relationships between the actors and use-cases, and between the use-cases themselves. The researcher, who is interested in using RMobiGen to analyze and generate mobility trace, is the only actor in the system. The main use-cases are: • Generating the mobility trace, • Analyzing and visualizing various scenarios from the trace, and • Exporting the trace to NS2 format. Since the pauses can be extracted from the start and end times of the legs, the mobility trace of a node can be considered as a sequence of legs. The mobility trace for all the nodes is the collection of the mobility traces of the individual nodes, as shown in Figure 3.1. Generating the mobility trace includes generating the mobility traces from the five random mobility models discussed in the previous Chapter. Visualization and analysis of the mobility trace include, visual analysis and computing statistical metrics for movement, connectivity, and coverage aspects, discussed in Chapter 2. Adding together all these use-cases, we get the use-case diagram given in Figure 3.2. 20 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. T * Leg 2 Leg 2 * Leg 2 T Leg 3 Leg3 Start Destination Speed Direction Start time End time Pause time Figure 3.1: Internal Structure of Execution Trace Next we present the higher level architecture and subsequently explain the design of its components. 3.2 A rch itectu re Based on the use case diagram, in a higher level, RMobiGen can be constructed by three main components. • Mobility Trace Generator: Responsible for generating the mobility trace. • Mobility Trace Manager: Responsible for extracting various statistical insights and providing visualizations. • Mobility Trace Exporter: Responsible for converting the mobility trace into NS2 format explained in Chapter 2. 21 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. cov erage m etrics individual trac e m etrics sna p sh o t connectivity m etrics anim ation visual analysis using model include E x p o rt T rac e M obility T rac e Analyze Scenario Figure 3.2: Usecase Diagram Figure 3.3 illustrates the basic architecture. 3.3 C lass D iagram Class diagram depicts the structural aspects of the system. A class essentially has three logical components: data attributes, operations th at involve services from other classes, and operations to access the member attributes of the class. Identifying classes is an iterative process. Based on the insights we obtained from the above analysis, the following main classes are identified for RMobiGen. • User specifications (Parameter) • Mobility Trace Generator (MobilityGenerator, RandomNumberGenerator, LegGen22 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. mobility model specification R M o b iG en Mobility Trace G enerator Execution Trace Mobility S cenario M anager Mobility Trace E xporter GUI NS2 tri visualizations Figure 3.3: RMobiGen Architecture erator) • Mobility Trace Manager (MetricGenerator, Visualizer) • Mobility Trace Exporter (TraceExporter) The class diagram illustrating the classes and their relationships is given in Figure 3.4. 23 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. _______________ LegGenerator -id: int •configuration: Parameter -oneRandomLeg: RandomLeg •individualTrace: List •simulationClock: double________ Parameter -speedRange & distribution -directionRange & distribution •distanceRange & distribution -destinationRange & distribution -durationRange & distribution -pauseTimeRange & distribution -boundary ActionType •transmissionRange: double •width: double -height: double -duration: double -warmupDuration: double -num berOfNodes: int fgenNextRandom LegO: RandomLeg ■FboundaryActionReflectionO: double 4-boundaiyActionWrapAroundO: void 1 generate taken by RandomLeg MobilltyGenerator •startingPosition: Position •destination: Position •speed: double •direction: double •startTime: double •endTime: double •pauseTime: double_______ -traceSpecification: Parameter KraceG enQ : MobilityTrace «utility» RandomNumberGenerator random V alue: double -variance: double low erBound: double -upperBound: double +samp1eD: double utilized by MetricsGenerator analyzed by ■target: MobilityTrace HnstantRandom LegO: RandomLeg ■KnstantPositionO: Position fgetN eighborO : List fhasPathO : bool -HaverageSpeedO: double f averageDistanceO: double fnum berOfLinkChangeQ: int______ 1 MobilityTrace -individualTraces: List 1 exported by MobilityExporter -targ et: MobilityTrace visualized by 4-exportQ: string -target: MobilityTrace +snapshot(): void •KndividualTraceO: void -t-animateO: void Figure 3.4: Class Diagram 3.4 M od elin g K ey O p erations In this section, we present some key operations implemented in RMobiGen. Building interface is a complex task and we used Java Swing and AWT package with the help of JBuilder IDE. Here, we present some selected operations of mobility trace generation and performance metrics computation. 3.4.1 T race G en er a tio n The trace generator uses the event-driven method to build the mobility trace for each node as follows. 24 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 1. Set simulation clock value to 0. 2. Compute the leg param eter values according to the input specification. 3. Set the leg start time to simulation clock value and leg end time to simulation clock value + leg travel time. 4. Set simulation clock value to leg end time + pause time. 5. If simulation clock value < simulation end time, then go to step 2. Leg parameters are sampled based on its range and the probability distribution type using the RandomNumberGenerator. sample () operation. The different versions of genNextRandomLegO operation can be described in terms of different mobility models as follows: 1. Random destination-speed model: Sample a new destination, a new speed, and a new pause time. 2. Random destination-time model: Sample a new destination, a new time dura­ tion, and a new pause time. 3. Random direction-speed-distance model: Sample a new direction, a new speed, a new distance, a new pause time. 4. Random direction-speed-time model: Sample a new direction, a new speed, a new time duration, and a new pause time. 25 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 5. Random direction-time-distance model: Sample a new direction, a new distance, a new time duration, and a new pause time. 3.4 .2 P erfo rm a n ce M etr ic s C o m p u ta tio n Performance metrics are extracted from the mobility trace by the M etricsG en erator. It uses time-step based technique to collect data. The time-step based d ata collection works as follows. 1. Set simulation clock value to 0. 2. Collect d ata from the legs whose time matches the simulation clock value. 3. Increment simulation clock time by a fixed unit. 4. If simulation clock value < simulation end time, then go to step 2. The computation from the collected d ata may be updated as soon as the data is collected for th a t time step or computed at the end. Individual metrics are collected by traversing through the in d iv id u a lT ra c e list at a node and the system metrics can be obtained by iterating through all the in d iv id u a lT ra c e lists. To compute the connectivity metrics, a series of “snapshots” of the connectivity graph is taken once for every time step using the in s ta n tP o s itio n O operation. 26 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C^Id W--S- - lo j,u IP Figure 3.5: Panel General Scenario Setting Figure 3.6: Leg Param eter Setting Panel ■2BE1 |jtB y p MitH a 81 1 1 6 lilSltw » eg? / 7I—+1 1 if ^ I I I I I I a l\ vC\IPf W \ \* S V\V ' \ W JsSurail --- 1-_i^~"~ o ...... ..{*;.•?« ' 4 X axis 7 8 9 Y axis 10 Figure 4.13: Destination-speed Figure 4.14: Destination-time enters from the opposite boundary. In case of restart action, since the nodes pause at the boundary, the clustering occurs at the boundary. The coverage for the random direction models with reflection as the boundary action are shown in Figures 4.15, 4.17, & 4.19, and the coverage for the random direction models with restart as the boundary action are given in Figures 4.16, 4.18, & 4.20. Figure 4.15: Direction-speed-distance (RF) Figure 4.16: Direction-speed-distance (RS) Center clustering, boundary clustering, or completely uniform are not realistic 38 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Figure 4.17: Direction-speed-time (RF) Figure 4.18: Direction-speed-time (RS) » ^ :O y. Figure 4.19: Direction-distance-time (RF) ■ . i M JSBBsiin Figure 4.20: Direction-distance-time (RS) situations in most cases. In many cases, (i) it is common th a t more nodes stay in the inner region compared to the boundary regions at any instance and (ii) the spatial distribution is generally less uniform. To achieve these, we developed a mobility model in which the next position is chosen in the neighborhood of current position. We call this model as M arkov-destination m odel. We simulated this model using RMobiGen and we observed th a t it does not have the clustering phenomenon either in the center or along the boundary, as shown in Figures 4.21 h 4.22. In Figure 4.21 39 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. the destination is chosen within a rectangular neighborhood of size \th. of the mobility region and in Figure 4.22 the destination is chosen within a rectangular neighborhood of size ~th of the mobility region. Figure 4.21: Markov-Destination ( |) 4.4 Figure 4.22: Markov-Destination ( |) C o n n ectiv ity A n alysis For connectivity analysis, we mainly study two metrics: the connection changes and the session duration defined in Chapter 2. Three experiments were conducted by changing the transmission range, the speed, and the size of the simulation region. For each experiment, 16 nodes were simulated for 500 seconds. The observations are presented in Figures 4.23 & 4.24 by varying transmission range, in Figures 4.25 & 4.26 by varying speed, and in Figures 4.27 & 4.28 by varying size of the simulation regions. From Figures 4.23 to 4.28, we make the following observations. • The change in connectivity is small when the range is small (hardly get con40 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Transm ission Range (meters) Transm ission Range (m stsrs) j Hdestlnation-speed H direction-speed-distance □direction-speed-time | [adsstination-speed ■ direction-speed-distance □dlrection-speed-time ""j Figure 4.24: Session Duration Figure 4.23: Connection Change Maximum Speed (m/s) Maximum Speed (m/s) Igdestination-speed ■direction-speed-distance □direction-speed-tir gdestination-speed ■direction-speed-distance □direction-speed- Figure 4.25: Connection Change Figure 4.26: Session Duration nected), or the range is high (often connected). The change in connectivity is high when the range is medium. • The change in connectivity is small when the simulation area size is small, or the size is high. The change in connectivity is high when the size is medium. • The change in connectivity increases as the speed increases. • The average session duration increases as the transmission range increases and decreases as the size of the simulation region increases or as the speed increases. The connectivity metrics will be useful when studying communication protocols using these models. 41 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 500 x 500 1000x 1000 1500x 1500 2000 x 2000 1000x 1000 2500 x 2500 1500x1500 2000 x 2000 2500 x 2500 Size of Simulation Area (m eters x meters) Size of Simulation Area (meters x meters) jadestination-speed ■direction-speed-distance odirection-speed-tiir Figure 4.27: Connection Change 4.5 Figure 4.28: Session Duration Im p lem en tation C om p lexity Random waypoint is the most popular model heavily used for simulations. The main reason, in addition to its support in NS2, is stated in the literature as follows. A ssertion 4.1 Random waypoint is a simple model that is easy to analyze and im ­ plement. This has, probably, been the main reason fo r the widespread use of this model for simulations [22], The assertion is true only for the particular case where the mobility region is an ndimensional rectangle with sides aligned to coordinate axes. It loses its simplicity even for rectangles if the sides are not aligned with the coordinate axes. Also, implementing random direction models is not terribly complex compared to the implementation of random waypoint model. So the researchers should not hesitate to consider using other random mobility models if they are more relevant for their study. 42 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 4.6 Sum m ary In this Chapter, we presented a selected set of experiments using RMobiGen on Random mobility models. The experiments clearly illustrate the variations and their impact on the dynamics of the mobility models. Also, our experiments confirm some of the widely observed phenomena and presents some new observations. 43 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. C hapter 5 Sum m ary and Future D irections 5.1 Sum m ary In recent times, mobile computing has received increasing attention from the research community. Also, many applications based on mobile networks will be realized in the near future. Research studies in mobile computing are carried out mainly through simulations due to its flexibility and cost effectiveness. In most of these simulation based research studies, modeling the mobility of participating nodes plays a crucial role. This thesis deals with mobility related issues. The contributions in this are manyfold: First we presented a comprehensive overview of random mobility models and a simple classification. Next, the exist­ ing random mobility models and the popular softwares th at support some of these models were presented. Then the design and implementation of RMobiGen, which are the major contributions of this thesis, were presented. We followed software engi- 44 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. neering techniques and used UML diagrams during analysis and design phases of the development and then implemented using Java. RMobiGen can be used to generate, analyze, and adjust various scenarios by suitably controlling the mobility parame­ ters before applying it to the simulation. Finally, we conducted an extensive set of experiments to analyze various characteristics of random mobility models. We believe th a t our work and the insights we presented from our experiments on random mobility models would serve as guidelines for researchers to choose the right model for their simulations. 5.2 Future D irection s There are many directions in which the work presented in this thesis can be expanded. We outline some of them next. • RMobiGen assumes the mobility region as 2-dimensional rectangle. It can be extended to accommodate other geometric regions. • The mobility models can be extended to the regions with obstacles. • Also, the models can be further extended to the regions with attraction points, introduced in[17], to create more realistic mobility patterns. 45 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Bibliography [1] The Network Simulator - ns-2, http://w w w .isi.edu/nsnam /ns/. [2] Global Mobile Information Systems Simulation Library - GloMoSim, http: / / pcl.cs.ucla.edu/projects / glomosim/. [3] QualNet, Network Simulation Software, http://www.scalable- networks.com. [4] OPNET Technologies, http://w w w .opnet.com /. [5] MATLAB - The Language of Technical Computing, http://w w w .m athw orks.com /products/m atlab/. [6] SWAN Simulator for Wireless Ad-hoc Networks, h ttp :/ / www.eg. bucknell.edu / swan. [7] SWAN Manual, http://w w w .eg.bucknell.edu/sw an/doc/refm an.pdf. [8] BonnMotion tion and - A analysis mobility tool, scenario genera­ http://w eb.inform atik.uni- bonn.de/IV /M itarbeiter/dew aal/B onnM otion 46 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [9] L. Bajaj, M. Takai, R. Ahuja, K. Tang, R. Bagrodia, and M. Gerla, GloMoSim: A Scalable Network Simulation Environment, Report, Uni­ versity of California, Los Angeles. [10] Stuart Kurkowski, Tracy Camp, and Michael Colagrosso, “A Visual­ ization and Animation Tool for NS-2 Wireless Simulations: iNSpect” , Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.503-506, September 27-29, 2005. [11] S. Kurkowski, T. Camp, and M. Colagrosso, MANET Simulation Stud­ ies: the Incredibles, Mobile Computing and Communications Review, 9(4):50-61, 2005. [12] P. Nain, D. Towsley, B. Liu, and Z. Liu, Properties of Random Direction Models, Proc. of the IEEE INFOCOM, 2005. [13] J.-Y. Le Boudec and M. Vojnovi, Perfect Simulation and Stationarity of a Class of Mobility Models, Technical report, EPFL, July 2004. [14] W. Navidi and T. Camp, Stationary Distributions for the Random Waypoint Mobility Model, IE E E Transactions on Mobile Computing, 3(1):99-108, 2004. [15] C. A. V. Campos, D. C. Otero, and L. F. M. de Moraes, Realistic Individual Mobility Markovian Models for Mobile Ad hoc Networks, 47 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Proc. of the IE E E Wireless Communication and Networking Conference, 2004. [16] W. Navidi, T. Camp, and N. Bauer, Improving the Accuracy of Random Waypoint Simulations through Steady-State Initialization, Proc. o f the 15th International Conference on Modeling and Simulation, 319-326, 2004. [17] Michael Feeley, Norman Hutchinson, and Suprio Ray, Realistic Mobility for Mobile Ad Hoc Network Simulation, AD H OC-NO W 2004, 324-329, 2004. [18] J. Yoon, M. Liu, and B. Noble, Random Waypoint Considered Harmful, Proc. of the IEEE INFOCOM, 2003. [19] J. Yoon, M. Liu, and B. Noble, Sound Mobility Models, Proc. of the AC M MobiCom, 2003. [20] Tracy Camp, Jeff Boleng, Brad Williams, Lucas Wilcox, William Navidi, Performance Comparison of Two Location Based Routing Protocols for Ad Hoc Networks. In Proc. of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, 1678-1687, 2002. [21] G. Resta and P. Santi, An Analysis of the Node Spatial Distribution of the Random Waypoint Model for Ad Hoc Networks. Proc. A C M Work­ shop on Principles of Mobile Computing, 44-50, 2002. 48 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [22] T. Camp, J. Boleng and V. Davies, A Survey of Mobility Models for Ad Hoc Network Research, Wireless Communication and Mobile Comput­ ing, 2(5):483-502, August 2002. [23] K. Obraczka and K. Viswanath, Flooding for Reliable Multicast in Multi-Hop Ad Hoc Networks, Wireless Networks 7, 627-634, 2001. [24] Z. J. Haas and M. R. Pearlman, The Performance of Query Control Schemes for the Zone Routing Protocol, IE E E /A C M Transactions on Networking, 9(4):427-438, 2001. [25] C. Bettsetter, Smooth is Better than Sharp: A Random Mobility Model for Simulation of Wireless Networks, Proc. of the 4th A C M International Workshop on Modeling, Analysis, and Simulation of Wireless and Mo­ bile Systems, 2001. [26] E. M. Royer, P. M. Melliar-Smith, and L. E. Moser, An Analysis of the Optimum Node Density for Ad Hoc Mobile Networks, Proc. of the IEEE International Conference on Communications, 2001. [27] K. Pawlikowski, H.-D. J. Jeong, and J.-S.R. Lee, On Credibility of Simu­ lation Studies of Telecommunication Networks, IEEE Communications Magazine, 132-139, 2001. [28] E.M. Royer and C.E.Perkins, Multicast Operation of the Ad Hoc Ondemand Distance Vector routing protocol, Proc. AC M MobiCom, 1999. 49 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [29] B. Liang and Z. Haas, Predictive distance-based mobility management for PCS networks, Proc. of IEEE INFOCOM, 1999. [30] X. Hong, M. Gerla, G. Pei, and C. C. Chiang, A Group Mobility Model for Ad Hoc Wireless Networks. Proc. A C M /IE E E MSWiM, 53-60, 1999. [31] C. Hartm an and H.-J. Vogel, Teletraffic Analysis of SDMA-Systems with Inhomogeneous MS Location Distribution and Mobility, Kluwer Wire­ less Personal Communications, ll(l):45-62, 1999. [32] V. Tolety, Load Reduction in Ad Hoc Networks Using Mobile Servers. M aster’s thesis, Colorado School of Mines, 1999. [33] C. Chiang, Wireless Networks Multicasting. PhD thesis, Department of Computer Science, University of California, Los Angeles, USA, 1998. [34] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, A Per­ formance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, Proc. of the Fourth Annual A C M /IE E E Intl. Conf. on Mobile Computing and Networking, 85-97, 1998. [35] Z. Haas, A New Routing Protocol for the Reconfigurable Wireless Net­ works, Proceedings of the ICUP, 1997. [36] Amotz Bar-Noy, Ilan Kessler and Moshe Sidi, Mobile Users: To Update or Not to Update?, A C M /Baltzer Wireless Net, vol. 1, no. 2, pp. 175185, 1995. 50 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. [37] D. B. Johnson and D. A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks, In Mobile Computing, ed. T. Imielinski and H. Horth, 153-181, Kluwer Academic Publishers, 1996. [38] Eds: G. F. Lawler and L. N. Coyle, Lectures on Comtemporary Proba­ bility, American M athematical Society, 1991. [39] O. Balci, Credibility Assessment of Simulation Results, Proc. of the Winter Simulation Conference, 38-43, 1986. 51 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.