Realistic Mobility for M A N E T Simulation Suprio Ray B . E . ( C . S . E . ) , Regional Kngineering College, Trichy, India, 1999 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S FOR. T H E D E G R E E O F Master of Science in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Department of Computer Science) We accept, this thesis as conforming to the required standard The University of British Columbia Dec-ember 2003 (e) Suprio Ray, 2003 Library Authorization In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Title of Thesis: KFALtS He HQi^iLiTY Bj ^ Name of Author (please print) Date (dd/mm/yyyy) Degree: 74.. Sc Year: 2-0 c ^ j Department of P O T SO) p ( \ | c £ The University of British Columbia Vancouver, BC Canada Abst rac t In order to conduct meaningful performance analysis of routing algorithms in the context of Mobile Ad Hoc Networks (MANET), it is essential that the underlying mobility model on which the simulation is based reflects realistic mobility behavior. However, current mobility models for M A N E T simulation are either unrealistic or are tailor-made for particular scenarios. Furthermore, none of the existing mobility models support heterogeneous mobility behavior among different mobile nodes in the simulation. This thesis introduces G E M M , a tool for generating mobility models that are both realistic and heterogeneous. These models are capable of simulating complex and dynamic mobility patterns representative of real-world situations. The input to G E M M is a set of model descriptions and the output is a mobility scenario that can be used by either the Glomosim or NS2 network simulator. Simulation results are presented using AODV, OLSR and ZRP, three previously published M A N E T routing algorithms. These results illustrate that mobility-model changes have a significant impact on their performance. The results underscore the importance of using realistic mobility scenarios in M A N E T simulation and demonstrate the ability of G E M M to generate such mobility scenarios. ii Contents Abstract ii Contents iii List of Figures vi Acknowledgements viii Dedication ix 1 Introduction 1 2 Related Work 5 2.1 Entity Mobility Models .' 6 2.2 Group Mobility Models 10 2.3 Relevant Mobility Research Inspired by Computer Graphics and AI 11 2.4 Discussion 12 3 Case Study of a Realistic Mobil i ty Scenario 13 3.1 The Beach Scenario 14 3.2 A Realistic Yet Simple Model 16 iii 4 G E M M - A Generic Mobil i ty Mode l 18 4.1 Concepts of G E M M ' 19 4.1.1 Attraction Points 19 4.1.2 Activities 20 4.1.3 Habits . 2 0 4.1.4 Roles 21 4.1.5 Perception 21 4.1.6 Group Behavior 22 4.2 Discussion 22 5 Implementation and Usage 24 5.1 Implementation 24 5.2 Simulation Parameters 26 5.2.1 General simulation parameters 26 5.2.2 Attraction point parameters 27 5.2.3 Activity parameters 28 5.2.4 Role parameters 29 •5.2.5 Group mobility parameters 30 5.3 Example scenarios 31 5.4 Simulation of other mobility models 31 6 Evaluation 34 6.1 M A N E T Routing Protocols Studied 35 6.2 Experimental Setup 35 6.2.1 Attraction points 36 6.2.2 Mobility scenarios 36 iv 6.2.3 Understanding the scenarios 38 6.3 Results 44 6.3.1 Different Mobility Scenarios " 44 6.3.2 Impact of Speed Variation 45 6.3.3 Group Mobility Behavior 48 7 Conclusion 49 Bibliography 51 v List of Figures 3.1 A Simple Model of Mental States 15 3.2 Intention Algorithm for Beach Scenario 16 4.1 Determinants of mobility patterns 19 5.1 Example of the simulation of a mobility scenario in G E M M 31 5.2 Mobility trace of the scenario 32 5.3 Mobility Trace of Random Waypoint as Simulated by G E M M . . . . 32 5.4 G E M M Parameters for Random Waypoint Simulation 33 6.1 OAP-RTO mobility trace 37 6.2 T A P mobility trace 37 6.3 Relative mobility of four mobility models 38 6.4 Link breaks (% of total links) in four models 39 6.5 Pause Time vs % of Nodes with Average Node Degree (less than or equal to max degree) for Scenarios (a) OAP-RTO (b) T A P - R T O and (c) T A P 40 6.6 Comparison between the four scenarios of the pause time vs packet delivery ratio for (a) OLSR (b) AODV and (c) ZRP 41 6.7 Routing overhead (a) OLSR, (b) AODV and (c) ZRP 42 vi 6.8 Number of packets dropped or left waiting (a) OLSR (b) A O D V and (c) ZRP 43 6.9 Speed-variation normalized' packet delivery ratio for (a) OLSR, (b) AODV, and (c) ZRP .46 6.10 Group mobility normalized packet delivery ratio for (a) OLSR (b) AODV and (c) ZRP 47 vii Acknowledgements I would like to express my sincere gratitude to my supervisor Dr. Mike Feeley whose continued guidance, support and motivation made this thesis a reality. Dr. Feeley has been very kind in letting me venture into an area which was not his primary area of research interest. I am grateful to Dr. Norm Hutchinson for his active encouragement, enthusiasm and guidance. Thanks to Dr. Alan Wagner and Dr. Mark Greenstreet who assisted me with valuable suggestions and agreed to be in the supervisory committee. Also, thanks to Dr. Charles Krasic who has kindly offered me some great comments. My fellow project mate Kan Cai and other DSG Lab members deserve big thanks. Last but not the least, I thank all my fellow class mates with whom I came in touch at various times of my graduate studies. I am indebted to the Computer Science department of the University of British Columbia for taking care of the financial matters and for providing such an excellent research environment. Finally, I acknowledge the sacrifice and love of my parents, who are always supportive in all my endeavors. S U P R I O R A Y The University of British Columbia December 2003 viii To my parents always there for me, no matter what Chapter 1 Introduction Amazing progress in processor, memory and networking technologies usher the era of ubiquitous computing in which computers become pervasive and invisible. Mobile computing is an important step forward toward that vision. A Mobile Ad Hoc Network (MANET) is a spontaneous, self-organizing network of mobile computing devices, having no fixed infrastructure or administrative support, where each mobile node also acts as a router of network packets. In recent times, research in M A N E T has gained significant momentum, especially in the development of novel routing protocols. The standard way to evaluate these protocols is simulation, key to which is a model of node mobility. Due to the dynamic nature and mobility of users in a M A N E T , a key challenge in the evaluation of such routing algorithms is to conduct the performance analysis with realistic mobility models that accurately reflect the mobile users' movement. Several evaluations [9, 33, 15] of M A N E T routing algorithms have ignored the importance of realistic mobility patterns and used variants of random mobility models like Random Waypoint [24] or Random Walk [7] in their simulations. By virtue of their simplicity, these random models allow researchers to simplify 1 the comparison of results generated by different protocols. In random waypoint, for instance, nodes simply move among randomly chosen locations with a parameterized speed and wait-time at each location. The hope is that a simple model captures enough of the key characteristics of human mobility to make protocol evaluations meaningful. However, such random models are not representative of real-world mobility scenarios. For instance, in a beach scenario, mobile users don't move in a random manner. Beach users are unevenly distributed over the landscape. Some, of them may be stationary and others move at different characteristic speeds: walkers, jog-gers, bikers, sun-bathers and volleyball-players. The course that mobile users take is not random. Rather, some of their movements tend to be toward certain attrac-tion points such as volleyball playing spots, washrooms and snack bars; while others move in a predefined path through the landscape. Several researchers [22, 45] have observed that the performance of routing algorithms may be influenced by the choice of mobility models. More recently, there have been attempts to design specific mobility scenarios [22] that are more realistic than random models, but their limited applicability suggests that the effort of inventing and implementing a new mobility scenario on an ad-hoc basis is hardly a solution. Moreover, in none of the existing models it is possible for different nodes to have different mobility behavior. In this thesis a generic mobility model, G E M M , is introduced. G E M M [2] is used for generating realistic and heterogeneous mobility scenarios. This mobility model endeavors to represent realistic mobility scenarios by taking into account the fact that different nodes in the simulation can have different mobility patterns, and even dynamically assume different mobility behavior at different instants of time 2 in the simulation. Furthermore, the mobility behavior of each individual node can be influenced, in varying degree, by the mobility behavior of adjacent nodes. In our model, each mobile node can display different individual mobility patterns or combinations of different mobility patterns. Also, nodes can be made to demon-strate different group mobility behavior. As a result, G E M M can generate complex dynamic mobility scenarios, which to our belief is the first such model. Our model is easily tunable. That is, by changing a few parameters it is possible to derive completely different simulation scenarios. G E M M can also simulate other existing models such as Random Waypoint. The key contribution of this thesis is that it introduces heterogeneous, goal-oriented mobility pattern to represent realistic individual node mobility. Further-more, it integrates the characteristics of group mobility behavior [41] to represent interaction among the individual mobile nodes. In order to generate any mobility scenario, G E M M takes as input a description of the scenario in terms of four pa-rameters: attraction points, activities, roles and group behavior. Thus, the thesis presents a generic approach to depict intuitively realistic mobility behavior. In the random mobility models used for M A N E T simulation, a mobile node chooses a random destination in the'simulation area and moves toward that. Real-world human movement involves directed motion toward destinations of interest. Attraction points denote such relevant rather than random destinations.GEMM en-ables us to designate certain attraction points and allows additional attributes such as popularity and radius of the attraction point. An activity is the process of moving to an attraction point and remaining there for a period of time. Activities are parameterized by the path taken to the attraction point and the duration of wait at the attraction point. 3 People having different occupation demonstrate different inherent movement tendencies. For instance a peddler exhibits completely different mobility pattern than a computer programmer. Roles embody such characteristic movement behav-ior. • • Group behavior essentially takes into account the interaction among individ-ual mobile nodes such that their mobility behavior is influenced. People may tend to cluster in groups, match each others velocity or avoid colliding with each other. In order to evaluate the impact of mobility while simulating a M A N E T rout-ing protocol, it is imperative that the underlying mobility model accurately captures real-world node mobility or at least the essential charteristics. To this end, we be-lieve that this thesis makes a valuable contribution by providing a generic approach that can be directly utilized by popular M A N E T simulators. To compare the im-. pact of realistic node mobility vis-a-vis random node mobility models, we consider three routing algorithms, OLSR, A O D V and ZRP, each representative of the three different classes of routing algorithms, namely, proactive, on-demand and hybrid. Using different mobility scenarios created by G E M M , we demonstrate the significant impact of the mobility on the performance of routing algorithms. The organization of this thesis is as follows. In Chapter 2 we explore related works. Chapter 3 depicts the case study of a realistic mobility scenario. In Chapter 4, we describe concepts of our model (GEMM). The implementation of G E M M , the usage and the process of generating different mobility scenarios are presented in Chapter 5. The evaluation with three different routing algorithms is documented in Chapter 6. We conclude the thesis in Chapter 7. 4 Chapter 2 Related Work The freedom of movement makes wireless communication attractive. But at the same time mobility brings challenges owing to bandwidth and power constraints, limited or no infrastructure and mobility of users. Realizing the opportunities and challenges, wireless network researchers have made significant advancements in de-veloping technologies leading toward the vision of seamless mobile communication. One of the topics of interest is ways to deal with mobility. Since direct experi-mentation with real wireless network is expensive and time consuming, researchers usually take recourse into simulation. Two classes [39] of mobility models are used in the simulation of wireless networks - trace-driven and synthetic model based. Trace-driven models may be very useful and accurate if they are obtained through lengthy observation in the field involving real user-participants. Synthetic models do not provide such accuracy, but in attempting to model realistic user mobility behavior, they enable us to gain significant insight and thus are usually preferable over trace-driven models due to cost and time savings. So, in this thesis we shall be primarily concerned with synthetic models of mobility. Davies et. al. [16] have classified synthetic mobility models into entity mobility models and group mobility 5 models depending on whether individual nodes or a group of nodes are concerned. We shall also explore relevant research works from computer graphics and A l . 2.1 Entity Mobility Models Entity mobility models [12] deal with individual mobile node's mobility behavior, where the mobility action of each node is completely independent of any other node. An entity mobility model attempts to simulate the movements of a real mobile user. The changes in speed and direction of the mobile user's movement along with period of rest are some of the traits that are considered. Mobile user tracking strategies have been studied in the context of cellular wireless networks. The random walk mobility model was considered in [7], where a mobile node starts traveling by randomly choosing a direction and speed. The node may change its speed and direction after traveling a specified time or distance. Since the present speed and direction of a node is independent of its past speed and direction [21], this model can generate unrealistic movements like sudden stops and sharp turns [12]. With the advent of wireless technology standards like I E E E 802.11 and Blue-tooth, the Mobile Ad Hoc Network (MANET) has become a topic of increasing interest in the wireless research community. In this context, researchers have devel-oped a number of M A N E T routing algorithms, including DSDV [31] , OLSR [14], DSR [23, 24], A O D V [32], T O R A [30] and ZRP [19]. Although, there have been several works that conducted evaluation and performance comparisons of some of these algorithms, the assessments were based on random mobility models.. Maltz et. al. [9, 24] conducted performance comparison of DSDV, T O R A , DSR and A O D V in the which the random waypoint was used as the mobility model. Random 6 waypoint attempts to rectify the problem of abrupt stop and start in the random walk model by introducing pause times between changes in direction and speed. A mobile node starts by pausing for a specified period and after that chooses a random destination in the simulation area and a speed that is uniformly distributed between minspeed and maxspeed. The node then travels toward the chosen destination and upon arrival, pauses again before initiating the process again. Perkins et. al. [33] compared DSR and A O D V based on random waypoint. Das et. al. [15] conducted performance evaluation of DSDV, T O R A , DSR and AODV with a random way-point mobility model where the distance is exponentially distributed with mean 5m and pause time 0 (for stress testing). It has been observed by Royer et. al. [38] that the random waypoint model causes clustering of nodes near the center of the simulation area, which was termed a density wave. To overcome this, they proposed the random direction mobility model, in which a node chooses a random direction in which to travel, similar to the random walk model. A node then travels to the boundary of the simulation area in that direction. Once the simulation boundary is reached, the node pauses for a specified time, chooses another angular direction and continues the process. But such a model is unrealistic [12] since it is unlikely for people to spread themselves evenly throughout an area and pause only at the edge of a given area. In order to eliminate the impacts of simulation-edge effects, the Boundless Simulation Area Mobility Model [18] was proposed that allows nodes to travel unobstructed in the simulation area. But one of the undesired side-effects [12] of this model is that a static node, and a mobile node moving in the same direc-tion become neighbors repetitively. In all the random mobility models mentioned so far, the nodes follow straight movement, due to the memory-less nature of the models. The Gauss-Markov mobility model [27] was proposed in which at each 7 interval the next position of an node is calculated based on the current position, speed and direction of movement. In this model, each node is assigned an initial current speed and direction. At fixed time intervals t, the values of the speed and direction of each node are calculated and their values at tth instance is calculated based upon the values of speed and direction at (t — l)st instance using the equations [43] below: st = cxst-i + (1 - a)s + a2)sx t_! dt — adt-i + (1 - ajd + ^/{l^c^jd^j^ where st and dt are the new speed and direction of the node at interval t; a, is the tuning parameter that is used to vary the randomness of movement; s and d are constants representing the mean value of speed and direction as t —> oo; and sXf_L and dXl_1 are random variables from a Gaussian distribution. When a = 0, the node motion is completely random and when a — 1, the node motion is linear. At each time interval t, a node's position is given by the equations: xt — xt-i + st-i cos dt-\ Vt =Vt-\ + s t_i sin dt-i where (xt,yt) and (xt-i,yt-i) are the x and y coordinates of the node's position at the tth and (t — l)st time intervals, respectively, and s t_i and dt-i are the speed and direction of the node, respectively, at the (t — l)st time interval. Chiang [13] proposed a probabilistic random walk mobility model, in which the position of an individual node in the next time step is determined by a probability matrix. Three different states for position x and position y can be used in the matrix: state 0 for the current (x or y) position of a node, state 1 represents the previous position and 8 state 2 denotes the next position if the node continues to move in the same direction. The probability matrix is given by: P(0,0) P(0,1) P(0,2) P(1,0) P ( l , l ) . P(l,2) _ P(2,0) P(2,l) P(2,2) _ where each entry P(a, b) signifies the probability that a node will go from state a to state b. However, choosing appropriate values of P(a, b) may prove difficult, if not impossible [12] , unless the traces are available for the given mobility scenario. Since the random models don't reflect realistic mobility patterns, there have been attempts to design custom-made mobility scenarios to get an understanding of how M A N E T protocols behave in realistic environments. Johansson et. al. [22] proposed three mobility scenarios, namely, Conference, Event Coverage and Disaster Area. To simulate networks of streets in a city section, the City Section Mobility Model [16] and Manhattan Grid Mobility Model [5] were proposed, where the city streets form a grid and the nodes are allowed to move on predefined paths along the grid. A generalization of this model, the Graph-Based Mobility Model was proposed by Tian et. al. [42]. In this model, each node is initialized at a random vertex in the graph and moves on the shortest possible path toward another vertex, which is selected randomly as its destination. Shah et. al. developed a visual tool called C A D - H O C [40] that can be used generate visually realistic scenarios like airport, bus terminal, highways etc. Although tailor-made realistic scenario can be useful, a significant drawback of these approaches is the development cost associated with each individual simulation scenario and the limited usability. 9 2.2 Group Mobility Models Entity mobility models are useful to simulate individual node's mobility behavior. However, a node's movement is not always orthogonal to another adjacent node's mobility characteristics. In reality, the mobility behavior of a node may be influenced by neighboring nodes in cases like rescue party, a platoon of soldiers, etc. Exponential Correlated Random Mobility Model [21] is a group mobility model in which a motion function is used to create node-movements. Given the position of a node at time t, b (t) is used to define the next position at time t + 1, b (t + 1): where r adjusts the rate of change from the node's previous location to its new location and r is a random Gaussian variable with variance a. Sanchez [28] explored several custom-made group mobility models such as Column Mobility Model, Pursue Mobility Model and Nomadic Community Mobility Model. In the Column Mobility Model, a set of nodes move around a given line, which is advancing in a forward direction. A row of soldiers marching together, was cited as an example of this. Nomadic Community mobility model represents a collection of nodes that move together from one point to another. In this model, . each node in the group follows any entity mobility model to wander around a given point of reference. As the point of reference shifts, all nodes in the group drift to the new area around the reference point and continue moving around it. Pursue Mobility Model presents a pack of nodes attempting to follow a certain target. The current positon of a node, a random vector (obtained by an entity mobility model) and an acceleration function are combined to calculate the subsequent position of a node. 10 The Reference Point Group Mobility Model (RPGM) is a general group mo-bility model that dictates group movements through a logical center and group > motion vector, GM for each group. Individual nodes within a group move about their own predefined reference points whose movement depends on the group move-ment. As an individual reference point moves from its position at time t to a new position at time t+ 1, its movement is dictated by the group's logical center. Once the updated reference points, RP(t + 1), are calculated, they are combined with a random motion vector, RM, to update the position of each individual mobile node in the group. 2.3 Relevant Mobility Research Inspired by Computer Graphics and A l In the computer graphics and animation research community, work [37, 44] has been done in the area of animation of a collection of moving entities such as schools of fish or flocks of birds based on the principles of particle systems [35]. In these systems, the aggregate motion of the simulated group is determined by the collective mobility behavior of individual group members, where each member can chart out its own course of individual mobility action. Based upon these models, Tan et. al. [41] developed Individually Simulated Mobility Model in which the overall mobility pattern is the result of interaction between behaviors of individual nodes. Robotics and A l researchers have long been working on methods for finding suitable paths for robot navigation and collision avoidance through an arbitrary environment [8, 26]. These research works have been applied to virtual humans walking through environments in the contexts of animation [6, 29, 17, 10], city 11 planning [20] and fire hazard [25]. Although these works have explored the flocking behavior and group interaction, the question of realistic individual human walking path was avoided. The work of Renold [36] presented a comprehensive set of reactive controls for walking path determination. At each point of time, an avatar reevaluates the immediate environment and attempts to reach a goal while avoiding obstacles. 2.4 Discussion Although it is arguable as to what mobility characteristics constitute a realistic mobility model, the entity mobility models and group mobility models present some useful behavior features of mobile users of wireless communication technology, but they are still short of being generic realistic mobility models. In all existing mobility models for M A N E T simulation, realistic or random, every node in the simulation demonstrates homogenous mobility behavior that is, it is not possible to create a mobility scenario where different nodes in the simulation follow entirely different mobility models. We believe that in order for any mobility scenario to be truly realistic, heterogeneous mobility behavior has to be considered. To this end, we take inspiration from existing works from all possible areas like M A N E T , computer graphics and animation and Robotics: 12 Chapter 3 Case Study of a Realistic Mobi l i t y Scenario As wireless communication becomes more popular with the advent of increasingly new applications, use cases of mobile devices become diverse. Realistic mobility models should reflect as closely as possible those real-world use case scenarios. In no realistic mobility scenario do mobile users move in a completely random or erratic manner. In order to determine the factors that influence mobility in the real-world, we embark on exploring a realistic scenario where mobile users take part in various activities and thus give rise to a complex and dynamic mobility scenario. The goal is to obtain a better understanding of a complex mobility scneario by simulating a use case of movile devices. The simulation is carried out from a behavioral point of view, taking into account different psychological characteristics such as mental states and intentions, different physiological traits such as age, appetite and health and subjective concepts such as activities and roles. From the systems perspective 13 this may appear inconsequential and even digressive. However, our focus is to isolate the factors that contribute to the complex real-world human mobility patterns and attempt to abstract away those factors. In the end, we aim to formulate an abstract model of human mobility. 3.1 The Beach Scenario The beach is a typical example scenario where mobile users partake in various out-door activities. Some sports enthusiasts may be engaged in playing sports like beach volleyball. Some biking fans would use the beach trail to follow their cherished act of biking. A few would stroll aimlessly. Occasionally, people would go to the nearby snack bar or washroom. When anyone gets tired, she may just stop her current ac-tivity and simply sit idle and enjoy the sun. We observe that people usually either stay at a place and take part in some activities (i.e., volleyball spot) or move toward a certain point of interest (i.e., washroom). These points of interests are termed as Attraction Points. For our study, we identify a few roles that these groups of beach lovers fit into such as player, biker and stroller. The activities that each role can participate in can be specified in the following manner: Role Activities Player Plays (volleyball), takes rest, goes to washroom, eating place Biker Rides bike, takes rest, goes to washroom, eating place Stroller Wanders around, takes rest, goes to washroom, eating place The activity or a certain mobility behavior that a person will demonstrate is deter-mined by her current intention; for instance a person who is hungry would intend to move toward the nearby snack bar. The act of being hungry is her current mental 14 Hunger Urge at timet", Ht' = rninfl, 1 - (amount of food eaten at time t) * DR(time since last eaten, t' -1) /apetite)] Digestion Rate, DRfx) = 1 - Cdr * x Cdr = constant of digestion rate Wash urge urge at time f, Wt' = min[1, WFftime since last washed, f -1) * (1 - Ht) ]; Wash Function WF(x)= Cw' x Cw = Constant of wash function Resting urge (tired) at time t', R:' = rnin[1, TF(t'-t) * { 1 - FITNESSfage, health)}] Tiring Function, TF(x) = x * Ctr FITNESSfage, heaith) = (1 - age ' Cfitness)' health Ctr = tiring constant Cfitness = fitness function Playing Urge at time t', Pr = Booleanfrole = player)" min [1, 1 - Ht'" Wr' Re] Strolling Urge at timer, St' = Booleanfrole == stroller) * min [1, 1 - Hr * Wt" R-'l Biking Urge at time f, Br = Booleanfrole = biker) ' min [1; 1 - Ht" Wr * Rf] Figure 3.1: A Simple Model of Mental States state. That is, intention is again governed by mental states. The mental state of a person is a function of various factors. For example, how often a person gets hungry is regulated by habits and characteristics such as age, health, appetite, the time since last eating and the amount of food taken at that time. Figure 3.1 depicts a simple model of different mental states of different roles in a beach scenario. In Figure 3.2 the intention algorithm is illustrated, which determines what mobility act a person will take part in. When a person starts to move toward a certain attraction point, if she en-counters any obstacles like trees, she will try to avoid them. On her way to the desired destination, if she finds other persons who are also going toward the same destination she may form a group and try to match the velocity of other members in the group. 15 if (rcle ='= player) then if (mental state == need wash) then go to washing place, wash else if (mental state == hungry) then go to eating place, eat else if (mental state == tired) then stop, take rest else if (! playing) then go to a playground, play else play else if (role == stroller) then if (mental state == need wash) then go to washing place, wash else if (mental state == hungry) then go to eating place, eat else if (mental state == tired) then stop, take rest else stroll else if (role == biker) then if (mental state == need wash) then go tc washing place, wash else if (mental state == hungry) then go to eating place, eat else if (mental state == tired) then stop, take rest else if (! biking) then gc to the biking trail, start biking else bike Figure 3.2: Intention Algorithm for Beach Scenario 3.2 A Realistic Yet Simple Model In order to mimic realistic agent-motion, many behavioral aspects like habits, inten-tion, mental-states, perception and group interaction can be taken into consideration [44]. In the computer graphics and AI research community these are important in or-der to generate either life-like motion pictures or robotic movements. With respect to MANETs , the primary domain of usage for mobility models is the evaluation of routing protocols. Hence, the goal should be to develop the simplest possible model that is realistic enough to evaluate M A N E T routing protocols. This begs the question as to what mobility facets really matter. Our exploration of the beach scenario facilitates in gaining a clearer perspec-tive of the factors that influence human mobility behavior. The interplay of the mobility factors contribute to a certain mobility pattern of an individual. The in-teraction among individuals delermines a complex mobility scenario. We formulate 16 a generic moblity model, for M A N E T simulation, by conceptualizing a few abstract notions that capture the essential characteristics of the behavioral model. 17 Chapter 4 G E M M - A Generic Mobility Model Mobile A d Hoc Networks are spontaneously formed by mobile computing devices when carrier human beings gather close enough. So, any realistic mobility model for M A N E T simulation needs to take into account the dynamics of human motion. Pedestrian navigation is one example of complex human motion which is a function of human dynamics, a desired destination, and the presence of obstacles [11]. We would like to present mobility patterns as realistically as possible. Real world events take place due to causations. No mobility event is an isolated phe-nomenon. In order to be able to simulate real world mobility scenarios, it is im-perative to identify the factors that directly and indirectly influence the mobility behavior of mobile users. We have observed in our exploration of the beach scenario that a particular mobility pattern is the outcome of several factors. We introduce G E M M , a novel approach to generate realistic, heterogeneous mobility scenarios. The term G E M M is coined as an abbreviation of generic mobility 18 INFLUENCES —18 A T T R A C T I O N P O I N T INFLUENCES M O B I L I T Y P A T T E R N P E R C E P T I O N H A B I T G R O U P M O B I L I T Y B E H A V I O R Figure 4.1: Determinants of mobility patterns model. The approach of G E M M is generic in the way that it is based on a few parametric concepts, termed as mobility determinants, which describe a mobility scenario. Figure 4.1 shows the relationship between different mobility determinants in G E M M . These determinants are the abstract notions that we aimed to develop. 4.1 Concepts of G E M M G E M M is based on an abstract model that attempts to capture all possible factors influencing human mobility dynamics. A realistic heterogeneous mobility scenario is described with the following mobility determinants. 4.1.1 A t t r a c t i o n P o i n t s An attraction point is a destination of interest to multiple mobile users. In a univer-sity campus, for example, students tend to move between certain areas of interest 19 like classrooms, the cafeteria, the student-union-building, etc. In an airport, people move between the shopping mall or the waiting lounge. Such destinations of inter-ests are hot-spots or attraction points. Despite the existense of atraction points, it is also possible for certain nodes to move without heading toward any particular destination. For instance, in a forest, hikers may stroll, apparently showing no affin-ity toward any attraction point. Nodes may move among attraction points or from non-attraction points to attraction points and back. 4.1.2 Activities In the context of user mobility behavior, we define activity as the task of moving toward a particular attraction point and remaining there for some period of time. When, the destination doesn't involve any particular attraction point, the activity is simply to continue the movement for a certain period of time. An activity like eating involves going to a snack-bar (attraction point) and upon arrival, taking part in having food. An example of an activity without a particular attraction point is hiking. 4.1.3 Habits Habits influence activities. For instance, if the activity is going to the snack bar, this is influenced by the personal habits such as appetite, age, health, frequency of eating, etc. Since we are only interested in the fact that, habit affects activities and not the details-of different behavioral-habits, we introduce activity trigger time to capture the effect of habits. For instance, a person may eat a meal not more than eight hours later and at least two hours after having a meal. In this case, the maximum trigger interval is eight hours and minimum trigger interval is two hours. 20 4.1.4 Roles A role characterizes the mobility tendencies intrinsic to different classes of people. For example, university students spend much more time moving among classrooms than professors; some people bike, others walk. Each individual mobile user may participate in a few activities at different points of time. Depending on the current activity, the mobile user may move toward a particular attraction point and once at the destination, the person may perform some tasks. For example a beacher (a person interested in beach activities) may choose to play volleyball at a point of time. As a result she would move toward the nearest volleyball spot and play volleyball once she arrives there. After some time, she may get hungry and go toward a snack-bar. Later on, she may be interested to stroll in the beach. So, we can say that the role beacher can take part in activities such as playing, eating and strolling. 4.1.5 Perception Perception involves the act of observation, processing information obtained by the senses and cognizance. Perception is important in order to be able to take part in an activity. A mobile user needs to follow, a path toward an attraction point, avoid obstacles on her way and detect the moment of arrival at that attraction point. Perception is also essential to successfully exhibit group mobility behavior. In our model, each mobile node implicitly demonstrates perceptual abilities by taking part in activities and group mobility. 21 4.1.6 Group Behavior Group behavior captures the way that people influence each others mobility. The characteristics of human group movements have been studied in several research works [37, 29, 10].' We adopt a group mobility model similar to the idea of the Individually Simulated Mobility Model [41], that outlines the four behavioral traits: group centering or the inclination to stay close to nearby nodes, velocity matching or the propensity to match the velocity of adjacent nodes, collision avoidance or the urge to avoid collisions within the group, and inertia or the tendency to the maintain current velocity. As a mobile node takes part in a certain activity and moves toward an attraction point, it uses perceptual information to determine, the position and relative velocity of nearby nodes. This helps the node to take decisions as to change its course to avoid collision, match velocity of adjacent nodes and maintain current velocity. 4.2 Discussion G E M M offers a generic approach to capture realistic mobility. However, this may not appear very easy to set the simulation parameters. Approaches based on ran-dom models are simple and hence parameter setting is relatively easy. They provide standard mechanisms to compare the simulation results of different routing pro-tocols. However, as we have demonstrated, the real-world mobility behaviors are much more complex and are the outcome of the interplay of a number of factors. Thus, the random mobility models are too simplistic. Accordingly, the results of performance comparison of the routing algorithms based on the random models may not be meaningful. Realizing this, M A N E T researchers have attempted to come up 22 with more realistic models. Some of these approaches [22, 16, 5, 40, 28] are not generic enough to offer universal applicability. Other approaches [42] are either not intuitively realistic enough or are focussed on a particular aspect of realistic mobility, namely, group behavior [41]. In comparison with the existing mobility models, G E M M , on one hand provides a generic approach and on the other, renders a mechanism that takes into account of the various aspects of user mobility in a comprehensive manner. With regards to the issue of parameter setting, we show in the next chapter that they are intuitive and simple enough. Although the argument can still be made on the account that the performance comparison among different routing protocols becomes difficult with G E M M , the same argument can also be made against the other existing approaches that attempt to offer mobility models, more realistic than the random models. 23 Chapter 5 Implementation and Usage Mobile Ad Hoc of Network (MANET) is an active area of research. The performance analysis of M A N E T protocols can be done either by designing and deploying real M A N E T environments or by means of simulation. In the first approach, one or more use cases of mobile devices are deployed with actual systems. This ensures that the real-world mobility characteristics are closely taken into account. However, as the number of interesting applications of mobile devices increases at a fast rate, this approach will call for implementing of all possible use cases, which is difficult, if not impossible. With the other approach, i.e., simulation, abstract models are used to represent real-world mobility conditions. Besides being simpler, this provides a yardstick to compare similar protocols. However, the risk of this approach is that unrealistic models may lead us to unsound conclusions. 5.1 Implementation In order to validate the ideas of G E M M and demonstrate its ability, we have im-plemented G E M M , which is essentially a M A N E T simulation software. Instead of 24 developing a simulation environment anew from scratch, we wanted to take advan-tage of the existing works and focus on developing a generic mobility model that can produce realistic mobility scenarios. An important implementation goal of G E M M was to be able to generate mobility scenarios that can be directly utilized by the existing popular M A N E T simulators. This would enable the respective users of the existing simulators to use our implementation. To this end,, operating systems independence was our another implementation goal. Several simulators, such as NS-2 [4], Glomosim [3] are available for aca-demic research purposes. They have grown in popularity among the academia and public. With NS-2, protocols are implemented in C++ and simulation scenarios are described using Object Tel scripts. Whereas, the discrete event simulation language Parsec has been used to implement Glomosim. However, none of these programming languages are truly platform independent. BonnMotion [1] is a mobility generation and analysis tool. A key advantage of BonnMotion is that the generated scenarios can be exported to be used in both NS-2 and Glomosim. BonnMotion is imple-mented in Java and provides some useful APIs. G E M M [2] has been implemented in Java by utilizing BonnMotion APIs and conforms to the same output file format [1]. Besides offering platform independent source code (by virtue of Java), G E M M outputs a detailed mobility scenario that can be used directly by either NS-2 or Glomosim network simulator. G E M M im-plementation has been made publicly available under GNU General Public License at the URL: http://www.cs.ubc.ca/~sray/research/gemm/index.html. The input to G E M M is a set of parameter settings. There are three general parameters: simulation area, duration and node density. Additional parameters specify attraction points, activities, roles and group behavior. 25 The basic framework is that each node is statically assigned a distinct role. This role specifies a set of activities that the node performs, chosen randomly during the simulation. Each activity consists of moving to a new location and specifies zero or more attraction points as possible destinations. The details of these parameter settings are given below. 5.2 Simulation Parameters G E M M is capable of generating complex scenarios in which different sets of nodes in the same simulation scenario exhibit different mobility behavior. Moreover, the mobility behavior of each node is dynamic; each node can assume different mobility patterns at different instants of time in the simulation. The symbiosis of individual node's mobility behavior is expressed as group mobility behavior. G E M M is also able to simulate other existing mobility models. G E M M is able to achieve these without being complicated. The simulation parameters of G E M M are simple, intuitive, yet their combination provides a powerful mechanism for simulating realistic mobility scenarios. 5.2.1 Genera l s imulat ion parameters These parameters dictate the basic simulation characteristics like simulation area, duration, population etc. • simulation area • duration of the simulation • number of nodes in the simulation 26 5.2.2 Attraction point parameters Attraction points determine the possible destinations toward which mobile nodes can move. Each attraction point is a five-tuple consisting of x-y co-ordinates, pop-ularity, radius and type. Nodes select attraction points randomly weighted by their popularity. Nodes at an attraction point are uniformly distributed in an area of the specified radius. Type is a user supplied name used when specifying activities; multiple attraction points can have the same type. Optionally, the user can specify that G E M M should randomly determine the attraction point's co-ordinates. Attraction points can be specified with -A. Multiple attraction. points are separated by commas. The simulation parameters are: • x-coord • y-coord • popularity • radius of attraction point • attraction point type It is also possible to create any number of attraction points (at random positions) without specifying the actual coordinates by using the option -numAttrPts in which the locations are not specified: • number of random attraction points • radius of attraction point • attraction point type 27 5.2.3 A c t i v i t y parameters Activities are specified by a six-tuple consisting of minimum and maximum trigger and duration, destination and type. When a new activity is chosen, the wait time before the node begins to move is chosen uniformly between minimum and maxi-mum trigger time. Similarly, once a node arrives at its destination, its wait time is chosen from the minimum and maximum durations. The node's destination is spec-ified either to be a random location (similar to random waypoint) or an attraction point type. If multiple attraction points have the same type, one is chosen by its popularity. Type is a user supplied name used when specifying roles. In G E M M , an activity is usually associated with an attraction point. For example, the activity eating involves going toward an eating place and upon arrival, taking part in having a meal for a certain period. An activity can be non-goal-oriented i.e., may not involve going toward an attraction point. Strolling is an example of such an activity. As explained earlier, each activity can be triggered after at least a minimum trigger period and at most a maximum trigger period. When an activity is over, a mobile node chooses a new activity among the activities that it can take part, that has the smallest time left to be triggered. Activity parameters are specified with -V option. Multiple activities are separated by commas. The simulation parameters are: • minimum trigger period for the activity • maximum trigger period for the activity • minimum activity duration • maximum activity duration 28 • attraction point to go to • activity type A -2 in the attraction points denotes that the node can choose any point in the simulation area as its destination. It is also possible to specify a number of activities with -numActivities in conjunction with the random attraction point option i.e., -numAttrPts . Random minimum and maximum trigger times are chosen when the value of minimum and maximum trigger periods are both 0. • number of activities • minimum trigger period for the activity • maximum trigger period for the activity • minimum activity duration • maximum activity duration 5.2.4 Role parameters Roles determine the activities that a mobile node can take part in. Roles are specified by a five-tuple consisting of weight, minimum and maximum speed and activity set. Nodes are statically assigned a role according to role weights. The role specifies a speed range used whenever a node moves. It also specifies set of activity types that the node performs, chosen randomly from this set. Finally, a -1 in the activity set signifies that the node should return to its original position at the completion of the activity; otherwise, the node remains at its destination. Role is specified using -R option and the set of activity types that this role can take part in is an n-tuple enclosed by '(' and ')', having indefinite number of 29 entries i.e. n > 0. Thus, it is possible for a role to take part in any number of activities. Different roles are separated by commas. The simulation parameters: • percentage of nodes that assume this role • maximum speed of the node • minimum speed of the node • role type • activity types that this role can take part, separated by , 5.2.5 G r o u p m o b i l i t y parameters We implement a group mobility model similar to [41] and thus take similar param-eters. The parameters are specified by a four-tuple consisting of collision-avoidance, inertia, velocity-matching • and group-centering probabilities. Each probability is express as the fraction of nodes that exhibit the specified group behavior. Group mobility is specified by -G option. The simulation parameters are: • collision avoidance probability • probability of maintaining inertia • velocity matching probability • group centering probability When not specified, group mobility is not taken into account. This is useful; especially while simulating other simplistic models, such as Random Waypoint, that do not consider group mobility. 30 GEMMTUsnge: creation of u scenario with 2 different Rota, 5: different types of Activities and-3 difcrcnt types of Attraction: poiuis.taiA'GroupAieiiiili^ -f scenario_i -x 950 -y 700 -r. 50 -d 300 -A 750.50,1,30.0, 741, 2«0 .1,30.1, 640,593,1.30,2 923,364,1,30,3 , 127,512,1,30,4 -V 50 , 20 ,60,0 ;0', 0 . 60,35,75,0,1,, 1, 45,10,35,0,2,2. 60,15, 60,0,.3,3. 50, 25, 60/0; 4,-4 -R B O . 1 . 6 . l . O , <-1. .4,0,2} . 20, 11', 4,1, (3,1) -C- 100.100,100,100 Figure 5.1: Example of the simulation of a mobility scenario in G E M M 5.3 Example scenarios G E M M provides a flexible, yet simple way of generating different realistic mobility scenarios. In Figure 5.1 we demonstrate how to describe a mobility scenario in G E M M with 2 different roles, five different activities, five different attraction points and Group mobility. Figure 5.2 shows the mobility trace of the same scenario. 5.4 Simulation of other mobility models G E M M can simulate other mobility models. Figure 5.3 demonstrates the movement trace of random waypoint model as simulated by G E M M . The simulation parameters specified in G E M M in order to simulate random waypoint is shown in Figure 5.4. 31 Figure 5.2: Mobility trace of the scenario - _ • • 8 J i l . V " • j r j i • _ -• rjr" \ Figure 5.3: Mobility Trace of Random Waypoint as Simulated by G E M M 32 Simulating Random Waypoint Model With G E M M : -f RWP_SIM-x 9 5 0 - y 7.00 -n 5 0 - d 300 -R 100,20,0,0.(0) -V 0,0,100,0,-2,0 Figure 5.4: G E M M Parameters for Random Waypoint Simulation 33 Chapter 6 Evaluation Several unicast routing algorithms have been proposed for M A N E T and a number of studies have been conducted to compare these routing algorithms. Most of these performance comparisons [9, 33, 15] are based on the random waypoint mobility model, due to its simplicity. However, it was soon observed [45] that the choice of mobility models has an impact on the performance of routing protocols [45]. Real-izing the fact that the simplistic mobility models are not representative of real-world mobility scenarios, Johansson et. al. [22] conducted a scenario based performance analysis of a few routing algorithms in which they used three tailor-made scenarios. We intend to conduct performance comparisons of M A N E T routing algo-rithms with truly realistic mobility scenarios. As our model, G E M M , is able to generate complex, heterogeneous and goal-oriented crowd motion, we believe that these scenarios are representative of real-world mobility models. Since no perfor-mance analysis studies with truly realistic mobility models exists, it is not evident what factors might influence the performance of routing protocols. We conduct several experiments to find out the impact of heterogeneity, directed motion, speed and group mobility behavior. 34 6.1 M A N E T Routing Protocols Studied Although quite a number of unicast routing protocols for M A N E T s exist, they can be classified into proactive, reactive and hybrid routing algorithms. The proactive routing protocols attempt to maintain up-to-date routing information for all the nodes in the network by periodic flooding of routing information. DSDV and OLSR are examples of proactive protocols. The reactive routing protocols cache topological information and update the cached information on-demand [34]. Some examples of reactive routing protocols are AODV, DSR and T O R A . Hybrid routing protocols maintain clustering of the network and keep routing information up-to-date within a cluster while using a reactive paradigm for collecting information about nodes outside a cluster [34]. In order to conduct comparison studies with G E M M , we select OLSR, AODV and ZRP, which are representative of proactive, reactive and hybrid routing algorithms respectively. 6.2 Experimental Setup The goal of our simulation experiments is to assess the impact of different aspects of realistic mobility scenarios on the ability of the M A N E T routing protocols to successfully deliver data packets. We base our performance comparison on the packet delivery ratio achieved by the three M A N E T routing protocols. We adopt a simulation environment similar to [9], where 50 mobile nodes move about in an area of 1500m x 300m. Each node in the simulation has a radio transmission range of 250m. For the experiment of packet delivery ratio vs. pause time, we conduct our simulations with different pause times: 0, 30, 60, 120 and 300 seconds. The maximum speed of each node is 20m/sec. The data traffic charac-35 teristics is based on constant bit rate (CBR), in which each of the 20 C B R sources sends 4 packets every second, each packet being 64 bytes in size. Reported results are the average of multiple trials. 6.2.1 At t rac t ion points The goal of this first set of simulations is to illustrate the ways in which attraction points changes algorithm behavior. In this first set of simulations, node speed is chosen uniformly between 0 and 20m/sec similar to [9]. 6.2.2 Mob i l i t y scenarios We used G E M M to generate the following mobility scenarios. Figures 6.1 and 6.2 give mobility traces for two of these scenarios. R W P The standard random waypoint model. O A P - R T O Nodes move to a single attraction point, pause and return to their original position. T A P - R T O Nodes randomly choose among three attraction points, pause and re-turn to their original position. T A P Nodes randomly choose among three attraction points, pause and move to another randomly chosen attraction point. For OAP-RTO, the attraction point was chosen to be the middle of the simulation area. For TAP-RTO and TAP, the three attraction points were chosen to be evenly distributed in the simulation area. These choices were mostly arbitrary, but since our goal is simply to determine whether attraction points matter, this approach seems adequate. 36 V / ft Si. \ i i 1 • Figure 6.1: OAP-RTO mobility trace 37 - * - RWP •+• OAP-RTO TAP-RTO -e- TAP 0 50 100 150 200 250 300 Pause Time Figure 6.3: Relative mobility of four mobility models. 6.2.3 Understanding the scenarios Before presenting simulation results for the routing algorithms using these models, it is illustrative to compare the models themselves against three, key characteristics: relative mobility,- link breaks and node density. Figure 6.3 shows the relative mobility [22] for the four scenarios for different pause times. Relative mobility is a measure of average node velocity as a vector sum. T A P - R T O has the highest average relative mobility and RWP has the lowest average relative mobility. In other words, since node speed is the same in every model, this graph shows that TAP-RTO nodes chose destinations that are on average more distant- than does RWP. This is not surprising, since RWP chooses its destinations randomly, while TAP-RTO is constrained to attraction points. For all the scenarios, relative mobility decreases with increasing pause times, as expected because nodes spend less time moving. Figure 6.4 shows the total number of link breaks as a percentage of the total number of links. A link is defined to exist between every pair of nodes that are in 38 0 50 100 150 200 250 300 Pause Time Figure 6.4: Link breaks (% of total links) in four models. radio range of each other. This is a key metric, because the main way that mobility impacts a routing algorithm is by breaking links and thus invalidating cached routes. RWP has the highest percentage of link breaks and in all the scenarios the percentage of link breaks decreased as the pause time increased. Figure 6.5 shows the distribution of node densities, approximated by node degree, for OAP-RTO, TAP-RTO and TAP. RWP is not shown because it has a uniform degree of 16. For each pause time, each graph shows the fraction of nodes that have node degree smaller than the y-axis value. OAP-RTO has a high node density spike, over half the nodes have node degree higher than 35, as they congregate at the single attraction point. TAP-RTO lowers density substantially. T A P has the highest density, because nodes are evenly divided among the three attraction points. In every case a substantial fraction of the nodes have significantly higher degree than any node in RWP. 39 (c) Figure 6.5: Pause Time vs % of Nodes with Average Node Degree (less than equal to max degree) for Scenarios (a) OAP-RTO (b) T A P - R T O and (c) T A P 40 41 42 43 6.3 Results 6.3.1 Different Mob i l i t y Scenarios Figure 6.6 shows the packet delivery ratios for OLSR, AODV and ZRP respectively for all four mobility scenarios. The first and most important thing to notice is that there are substantial differences among the mobility scenarios. Furthermore, each algorithm reacts differently to mobility-model changes. While OLSR performs best with OAP-RTO and worst with TAP-RTO, for example, A O D V performs better with T A P - R T O than OAP-RTO. Similarly, ZRP performs well with T A P (second best), but OLSR and AODV do not. These differences indicate that the choice of mobility has a big impact on comparisons among competing algorithms. With RWP, for example, A O D V is the best performing algorithm of the three. With OAP-RTO, however, OLSR performs far better than AODV. In fact, for AODV all of the mobility models result in worst performance compared to RWP. This fact can be explained by Figure 6.8b, which shows that AODV drops fewer packets under RWP than the more realistic models. Figure 6.7 shows the routing overhead for OLSR, A O D V and ZRP. ZRP has five to six times the overhead of other models. For short pause times it has an overhead spike for T A P and a smaller one for TAP-RTO. AODV shows a similar but smaller spike for T A P and TAP-RTO. For AODV, however, R A P - R T O has higher overhead, while for ZRP, TAP has the highest. For long pause times, OAP-RTO produces the lowest overhead and the highest overhead for ZRP. Figure 6.8 gives the number of packets dropped for OLSR, AODV, and ZRP. OLSR drops roughly 2000 packets and ZRP drops around 1500 packets. A O D V 44 shows a large packet-loss spike for OAP-RTO at short pause times. For long pause times, T A P causes the most packet loss and RWP the least. 6.3.2 Impact of Speed Variat ion The earlier experiments were conducted to make comparison against previously published evaluations where maximum node speed was 20m/sec. We now turn to simulations using realistic human walking and bicycling speeds of 1-1.6 m/s and 4-11 m/s respectively. We add the suffix HS to the model names to signify walking-speed and M I X E D to signify a mix of 20% bikers and 80% walkers. Figure 6.9 shows the normalized packet delivery ratio attained by three routing algorithms, OLSR, AODV and ZRP, for these six scenarios (OAP-RTO-HS, OAP-RTO-MIXED, TAP-RTO-HS, TAP-RTO-MIXED, TAP-HS and T A P - R T O -MIXED). The normalization is done with respect the earlier scenarios with nodes having maximum speed 20m/s. For instance, the packet delivery ratio for OAP-RTO-HS is normalized with respect to OAP-RTO. Again the key thing to observe from these graphs is that performance differs substantially among the mobility models. This difference can be seen in two ways. First, as expected, lowering speed improves packet delivery ratio in most cases (i.e., normalized ratios greater than 1). Surprisingly, AODV performs worse at lower speeds. In any case, all of the algorithms are sensitive to speed changes for most mobility scenarios. Second, the extent to which speed changes matter differs widely among the different mobility scenarios. For OLSR, for example, TAP-RTO-HS is around 1.7 times better than TAP-RTO, but TAP-MIXED is only around 1.1 times better than TAP. The performance differences are most notable for ZRP. 45 (a) (b) OAP-RTO-HS * OAP-RTO-MIXED - - TAP-RTO-HS TAP-RTO-MIXED TAP-HS TAP-MIXED (c) Figure 6.9: Speed-variation normalized packet delivery ratio for (a) OLSR, (b) AODV, and (c) ZRP 46 47 6.3.3 Group Mobi l i t y Behavior Finally we turn to group mobility. For this simulation we generated group mobil-ity variants of the mixed walking/biking scenarios. For these models, we set all four group parameter values to 100, indicating that every node acts with all group behaviors. We add a - G M suffix to these models names. The results are shown in Figure 6.10, which shows packet delivery ratio normalized to the non-group variant of each scenario. Again we see that group settings seem to matter, though less so than for speed variation, particularly for AODV. 48 Chapter 7 Conclusion Some of the existing mobility models for M A N E T , which are variants of the ran-dom model, are too simplistic. Although a few tailor-made mobility scenarios are proposed they are too narrow in their scopes. We have introduced G E M M , a novel tool for generating intuitively realis-tic scenarios based on its. principles of attraction points and heterogeneous node roles. G E M M provides a mechanism whereby heterogeneous and dynamic mobility scenarios can be created by specifying a few parameters. Our model can be used to generate realistic mobility scenarios with any combination of different mobility aspects like speed, pause time, attraction point, number of nodes having similar characteristics, group behavior, etc. We have shown that G E M M can be used to generate models that are arguably more realistic. We simulated three algorithms, AODV, OLSR and ZRP, using a variety of mobility scenarios designed to be more realistic than random waypoint. Key features of these models are (1) nodes move to or among designated attraction points rather than moving randomly, (2) nodes move at a variety of speeds, (3) group mobility is considered and (4) a simulation can combine a variety of mobility 49 . patterns. Our results show that the algorithms we studied behaved substantially differently under the models we generated than they did under random waypoint. We have also illustrated that a number of different basic mobility patterns, when combined in different ways, yield different results. Furthermore, we've shown that mobility assumptions affect performance in major ways and that these assumptions also affect the choice of which algorithm is better. These results point the way toward more realistic simulations and thus more useful evaluations of routing protocols. Moving from simple models such as random waypoint to more realistic mod-els, as we suggest, comes with a potential problem. A key benefit of random way-point has been that it is simple and has few parameters. The danger with more realistic models models is that they have many more parameters, making parame-ters setting more difficult and comparisons more complex. We believe that the ben-efit of more realistic evaluation is worth the trouble and that the generic approach of G E M M provides substantial benefit with this problem. We hope that G E M M will be useful within M A N E T research community in the evaluation of M A N E T protocols. 50 Bibliography [1] Bonnmotion mobility model generator. http://web.informatik.uni-bonn.de/iv/mitarbeiter / dewaal/bonnmotion / . [2] Gemm: A generic mobility model for generating realistic mobility scenarios. http://www.cs.ubc.ca/~sray/research/gemm/index.html. [3] Glomosim, scalable simulation environment for wireless and wired network sys-tems. http://pcl.cs.ucla.edu/projects/glomosim/. [4] The network simulator - ns2. http://www.isi.edu/nsnam/ns/. [5] Selection procedures for the choice of radio transmission technologies of the umts. Technical report tr 101 112 v3.2.0, etsi smg-5, Sophia Antipolis, France, April 1998. [6] S. Bandi and D. Thalmann. Path finding for human motion in virtual environ-ments. Computational Geometry, 2003. [7] A. Bar-Noy, I.Kessler, and M.Sidi. Mobile users: To update or not to update? In Proceedings of the Joint Conference of the IEEE Computer and Communi-cations Societies (INFOCOM), 1994. [8] J. Borenstein and Y. Koren. Real-time obstacles avoidance for fast mobile robots. IEEE Transactions on Systems, Man and Cybernetics, 1989. [9] Josh Broch, David A. Maltz, David B.Johnson, Y . - C . Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proceedings of ACM/IEEE Mobicom, Dallas, USA, 1998. [10] David C. Brogan and J. Hodgins. Group behaviors for systems with significant dynamics. Autonomous Robots, 4(1): 137-153, 1997. [11] David C. Brogan and Nicholas L. Johnson. Realistic human walking paths. In Proceedings of the 16th International Conference on Computer Animation and Social Agents (CASA 2003), New Brunswick, New Jersey, USA, May 2003. 51 [12] T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communication and Mobile Computing : Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, pages 438-502, 2002. [13] C. Chiang. Wireless Network Multicasting. PhD thesis, University of California, Los Angeles, 1998. [14] T .H . Clausen, G. Hansen, L. Christensen, and G. Behrmann. The optimized link state routing protocol, evaluation through experiments and simulation. September 2001. [15] S. R. Das, R. Casta neda, and J. Yan. Simulation-based performance evalua-tion of routing protocols for mobile ad hoc networks. In Mobile Networks and Applications, 2000. [16] V. Davies. Evaluating mobility models within an adhoc network. Master's thesis, Colorado School of Mines, 2000. [17] S. Goldenstein, E . Large, and D. Metaxas. Non-linear dynamical system ap-proach to behavior modeling. Visual computer, 15:349-364, 1999. [18] Z. Haas. A new routing protocol for reconfigurable wireless networks. In Pro-ceedings of the IEEE International Conference on Universal Personal Commu-nications (ICUPC), Oct 1997. [19] Z.J. Haas and M.R. Pearlman. The zone routing protocol (zrp) for ad hoc networks. Internet draft, draft-ietf-manet-zone-zrp-02.txt, June 1999. [20] M. Haklay, D. O'Sullivan, M . Thurstain-Goodwin, and T. Schelhorn. So go downtown: Simulating pedestrian movement in town centres. Environment and Planning B: Planning and Design, 28(3):343-359, 2001. [21] X. Hong, M . Gerla, G. Pei, and C. Chiang. A group mobility model for ad hoc wireless networks. In Proceedings of the ACM International Workshop on Modeling and Simulation of Wireless and Mobile Systems (MSWiM), August 1999. [22] P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark. Sce-nario based performance analysis of routing protocols for mobile ad hoc net-works. In Proceedings of Mobicom'99, Seattle, USA, 1999. 52 [23] David. B. Johnson. Routing in ad hoc betworks of mobile hosts. In Proceed-ings of the IEEE Workshop on Mobile Computing Systems and Applications, December 1994. [24] David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, pages 153-181, 1996. [25] W. Jones. The evolution of hazard, the fire hazard assessment methodology. Fire Technology, 33(2):167-182, 1997. [26] B. Krogh and C. Thorpe. Integrated path planning and dynamic control for autonomous vehicles. In Proceedings of the IEEE International Conference on Robotics and Automation, Piscataway, N.J, USA, 1986. B. Liang and Z. Haas. Predictive distance-based mobility management for pes networks. In Proceedings of the Joint Conference of the IEEE Computer and Commutations Societies (INFOCOM), March 1999. Sanchez M . Mobility models. http://www/disca.upv.es/ misan/mobmodel.htm. S. Musse and D. Thalmann. A model of human crowd behavior: Group inter-relation and collision detection analysis. In Computer Animation and Simu-lations 1997, Proceedings of Eurographics Workshop, Budapest,Hungary, 1997. Springer-Verlag, Wien, Austria. [30] Vincent D. Park and M . Scott Corson. A performance comparison of tora and ideal link state routing. In In Proceedings of IEEE Symposium on Computers and Communication, June 1998. [31] Charles E . Perkins and Pravin Bhagawat. Highly dynamic destination se-quenced distance-vector routing (dsdv) for mobile computers. In Proceedings of the SIGCOMM '9^ Conference on Communications Architectures, Protocols and Applications, August 1994. [32] Charles E . Perkins and Elizabeth M. Royer. Ad hoc on-demand distance vec-tor routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, USA, February 1999. [33] Charles E . Perkins, Elizabeth M . Royer, S. R. Das, and M . K. Marina. Perfor-mance comparison of two on-demand routing protocols for ad hoc networks. In Proceedings of the IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000. [34] Rajmohan Rajaraman. Topology control and routing in ad hoc networks: A survey. SIG ACT News, June 2002. 53 [35] W. T. Reeves. Particle systems - a technique for modeling a class of fuzzy objects. 2, 1983. [36] C. Reynolds. Steering behaviors for autonomous characters. In Proceedings of the 1999 Game Developer's Conference, 1999. [37] C. W. Reynolds. Flocks, herds and schools: A distributed behavioral model. In Siggraph '87, 1987. [38] Elizabeth Royer, P.M. Melliar-Smith, and L. Moser. An analysis of the op-timum node density for ad hoc mobile networks. In Proceedings of the IEEE International Conference on Communication (ICC), 2001. [39] M. Sanchez and P. Manzoni. A java-based ad hoc network simulator. In Proceed-ings of the SCS Western Multiconference Web-based Simulation Track, January 2000. [40] S. Shah, E . Hernandez, and A.S. Helal. Cad-hoc: A cad like tool for generating mobility benchmarks in ad-hoc networks. In Proceedings of the Symposium on Applications and the Internet (SAINT), Nara City, Japan, 2002. [41] D. S. Tan, S. Zhou, J. Ho, J.S. Mehta, and H. Tanabe. Design and evaluation of an individually simulated mobility model in wireless ad hoc networks. In Proceedings of the Communication Networks and Distributed Systems Modeling and Simulation Conference, 2002. [42] J. Tian, J. Hahner, C. Becker, I. Stepanov, and K. Rothermel. Graph-based mobility model for mobile ad hoc network simulation. In Proceedings of the 35th Annual Simulation Symposium, San Diego, USA, 2002. [43] V. Tolty. Load reduction in ad hoc networks using mobile servers. Master's thesis, Colorado School of Mines, 1999. [44] Xiaoyuan Tu and Demetri Terzopoulos. Artificial fishes: Physics, locomotion, perception, behavior. In Proceedings of ACM SIGGRAPH'94, Orlando, F L , USA, July 1994. [45] M. Gerla X. Hong and C. Ciang. A group mobility model for ad hoc wireless networks. In Proceedings of the ACM International Workshop on Modeling and Simulation of Wireless and Mobile Systems (MSWiM), August 1999. 54