A S T U D Y O F T H E D E S T IN A T IO N G U ID E D M O B IL IT Y M O D E L S by M D . A Z IZ U R R A H M A N M.Sc., University of R ajshahi, Rajshahi, Bangladesh, 2003 THESIS SUBMITTED IN PARTIAL FULFILLM ENT O F TH E REQUIREM ENTS FOR T H E D EG R EE OF M A STER O F SCIENCE IN MATHEMATICAL, C O M PU TER AND PHYSICAL SCIENCES TH E UNIVERSITY OF NORTHERN BRITISH COLUMBIA June 2012 © MD. AZIZUR RAHMAN, 2012 1+1 Library and Archives Canada Bibliotheque et Archives Canada Published Heritage Branch Direction du Patrimoine de I'edition 395 Wellington Street Ottawa ON K1A0N4 Canada 395, rue Wellington Ottawa ON K1A 0N4 Canada Your file Votre reference ISBN: 978-0-494-94120-1 Our file Notre reference ISBN: 978-0-494-94120-1 NOTICE: AVIS: 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, distrbute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. 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. Conform em ent a la loi canadienne sur la protection de la vie privee, quelques formulaires secondaires ont ete enleves de cette these. W hile 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. Canada A b stra c t Mobility models play a critical role in the simulation studies of Mobile Ad hoc Networks (MANETs). They greatly influence th e performance of M A N ET routing protocols. For M ANET simulations, random mobility models have been used in nearly all research studies in th e past. In recent times, several studies have criticised the use of random mobility models in the performance studies of MANETs for the lack of realism in modelling mobility. Therefore, questions have been raised regarding the credibility of M ANET simulation studies. Realism and simplicity are two attractive properties of mobility models; achiev­ ing both together in modelling mobility has been a challenging task. Recently, a framework of mobility models called D estination Guided Mobility (DGM ) models for MANETs with a basic software tool was proposed [1]. This framework can be used to develop several simple DGM models with improved realism. This thesis is primarily interested in studying DGM models for their suitability in modelling mobility in various M ANET scenarios. Our study requires a suitable simulation testbed for DGM models. Designing such a tool, referred to as DGM Gen, w ith suitable functionality to study DGM models is the secondary objective of this thesis. More specifically, after the design and im plem entation of DGMGen, we study: i) the generality of the DGM models by modelling different real world scenarios; ii) the connectivity analysis of three basic DGM models in comparison with th e widely used Random Waypoint (RWP) mobility model; iii) how to model a real life scenario using DGM models, based on th e trace collected from th a t scenario; and iv) th e im pact of DGM models on the Ad hoc On-demand Distance Vector (AODV) routing protocol using NS2. Our study shows th a t i) the DGM framework is powerful in capturing various MANET scenarios simply and more accurately, ii) DGM models confirm higher level connectivity prevailed in most real world scenarios, iii) DGM models can generate approximately the similar trace based on the insights of a real trace, and iv) the mobility models can influence the performance of th e routing protocol under study. D edicated To 97^ 4 979^ 999^ 4 cm , cc9za/ 971^ 4 cd & b ly ^ C ^ lc c T c < ^ yi/ / e4 c c a m o f ttz ^ - d tc > & z< ^ c7 c -^ & z7 9 , ‘A ccrued * S ^ c . vo/£%)& 4ctcbc/cc& c& naf4 c c /^ c ^ new eb l A ck n o w led g em en ts As a graduate student a t UNBC, I had the privilege of encountering m any individuals who have supported and encouraged me in one way or another. I would like to acknowledge their support. Specifically, some deserve special recognition. Foremost, I would like to express my heartfelt gratitude to my supervisor, Dr. Alex Aravind, for his erudite supervision and unconditional help, for th e m otivational papers he used to provide us to shape the goal of how to be a good g raduate student, for his patience, enthusiasm and immense knowledge, and for the phrase he commonly used, "Aziz, enjoy doing your work". Honestly speaking, this phrase changed my outlook toward my studies and I gradually began to enjoy doing my g raduate work. I sincerely thank Dr. W aqar Haque and Dr. Karim a Fredj, the m em ber of the examining committee, for their valuable time, effort, and suggestions on th is thesis. I would like to extend my gratitude to the external exam iner and th e chair of my defence for reviewing my thesis. I gratefully acknowledge th e financial support of th e Pacific C entury G raduate Scholarship I received through this wonderful university. I would like take to the opportunity to thank Dr. Ian Hartley, dean of graduate studies, and Dr. M argot Mandy, graduate chair of CSAM, for their adm inistrative support. Thanks are due to my friends - Viswanathan Manickam, Baldeep Pawer, Adiba M ahjabin Nitu, Fakhar U1 Islam, Behnish Mann, Heinrich Butow, and Rafael Roman, whose involvement in discussion gave me clarity and in chatting provided me w ith an enjoyable diversion. I gratefully acknowledge the help of N itu, Caleb Tarzwell, David Peterson and Farhana Afrin for reading my thesis meticulously. My sincere thanks to Dr. Mahi Aravind for hosting dinners in her home and sending delicious cakes to the lab often. I will always be thankful to my parents who have supported me in all my en­ deavours. I acknowledge my wife, Tanu, for her sacrifice, love, encouragement, and patience. I will always be thankful to my sister, M ehrun and my brother-in-law , Yunus Ali, for supporting me, my son, and my wife during our studies. I will never be able to convey my full appreciation, b u t I am forever indebted to everyone who has supported and encouraged me. Contents A b stra ct i A ck n ow led gem en ts ii C on ten ts iii List o f F igu res vi L ist o f T ables v iii 1 In tro d u ctio n 1 1.1 In tro d u c tio n ........................................................................................................ 2 1 1.1.1 B a c k g ro u n d .......................................................................................... 1 1.1.2 M otiv atio n.............................................................................................. 4 1.2 C o n trib u tio n s ..................................................................................................... 7 1.3 Organization of This T h e s i s ........................................................................... 8 L iteratu re R ev iew 9 2.1 Mobility M o d els.................................................................................................. 9 2.2 Analysis of Real Mobility Traces of MANETs .......................................... 15 2.3 Mobility Trace Generation and Analysis T o o l s ........................................... 16 2.4 Network Performance A n aly sis....................................................................... 19 iii 3 4 5 2.5 M ANET Routing P r o t o c o l s ......................................................................... 22 2.6 S u m m a r y .......................................................................................................... 22 P erform an ce M etrics 24 3.1 Connectivity M e tr i c s ...................................................................................... 25 3.2 T erm inology....................................................................................................... 26 3.3 Connectivity M e tr i c s ...................................................................................... 28 3.4 Performance Metrics for Routing P r o to c o ls .............................................. 33 3.5 S u m m a r y .......................................................................................................... 33 Trace G en eration and N etw o rk E x p lo ra tio n T ools 35 4.1 DGMGen - A r c h ite c tu r e ................................................................................ 35 4.2 DGMGen- Im plem entation and U s e ............................................................ 39 4.3 Routing Protocol Performance S u ite ............................................................ 48 4.4 S u m m a r y .......................................................................................................... 51 E x p lo ra tio n o f D G M M o d els 53 5.1 DGM M o d e l s .................................................................................................... 54 5.2 Representative MANET S cen ario s............................................................... 55 5.2.1 MANET Scenarios on L a n d ............................................................. 55 5.2.2 MANET Scenarios on/under W a t e r ................................................ 58 5.2.3 MANET Scenarios in A i r .................................................................... 59 5.3 5.4 Versatility of the DGM Models .................................................................. 59 5.3.1 Representative DGM M o d els............................................................ 60 5.3.2 Scenario M o d e llin g ............................................................................. 61 Connectivity Analysis of th e DGM M o d e ls .............................................. 65 5.4.1 66 Simulation S e t u p .................................................................................. iv 5.4.2 67 5.5 Modelling and Analysis a Scenario Based on Real Trace ...................... 75 5.6 Performance Study on M ANET Routing P r o t o c o l.................................. 79 5.6.1 Simulation S e t u p ................................................................................ 80 5.6.2 Simulation E x p e r im e n ts ................................................................... 80 5.7 6 Simulation E x p e r im e n ts ................................................................... Summary .......................................................................................................... C onclu sion and F u tu re D ir e c tio n s B ib liograp h y 83 85 97 v List of Figures 3.1 Connection by Link and P ath or Isolated N o d e s ..................................... 25 4.1 Higher Level Architecture of the DGMGen T o o l ..................................... 36 4.2 The Param eter Setting W indow...................................................................... 40 4.3 The Mobility Generator and Animation P anel............................................ 41 4.4 The Pair-level Statistics P anel......................................................................... 42 4.5 The Average Statistics Sub-panel.................................................................... 43 4.6 The D istribution Sub-panel.............................................................................. 44 4.7 The Real Trace Statistics Sub-panel.............................................................. 45 4.8 The M ultiple Scenarios Performance Analysis P anel................................. 46 4.9 The Performance Observation Window in the DGM Gen......................... 47 4.10 The Export Trace Panel of the DGM Gen.................................................... 47 4.11 The Routing Protocol Performance S u i t e ................................................... 49 4.12 A GUI Snapshot of AODV Simulation in Ad Hoc Network in NS2. . . 50 4.13 A Snapshot of AODV Routing Trace File in NS2 .................................. 50 5.1 Modelling Fish M o v e m e n t............................................................................. 62 5.2 Ship or Aircraft Movement T r a c e ................................................................ 63 5.3 Human or Vehicles’ Movement Trace in a C i t y ......................................... 63 5.4 Students’ Movement Traces in a C a m p u s .................................................. 64 vi 5.5 One Group Movement Trace in Battle-field S c e n a r io s ........................... 65 5.6 Variation of Contacts, Connection Changes, and Contact D uration vs. Transmission R ange............................................................................................ 68 5.7 Variation of Contacts, Connection Changes, C ontact Duration vs. Speed. 70 5.8 Clustering Coefficient of th e Networks G enerated by the Studied Models. 71 5.9 Degree D istribution of the Networks G enerated by Three Studied Models. 72 5.10 Number of Different Hop Length P aths During the Simulations . . . . 74 5.11 A Snapshot of Real Trace T h a t Contains C ontact Information Recorded by iMote D e v ic e s .............................................................................................. 75 5.12 Inter-contact Time D is tr ib u tio n ................................................................... 77 5.13 Contact Time D is trib u tio n ............................................................................. 78 5.14 Im pact of Mobility Models on the Performance of AODV vs. Number of N o d e s .............................................................................................................. 81 5.15 Im pact of Mobility Models on th e Performance of AODV vs. D ata G enerating S o u r c e s .......................................................................................... 83 List of Tables 5.1 Simulation Param eters for Mobility M o d e llin g ........................................ 66 5.2 Simulation Param eters for Modelling Scenario Derived from Real Trace 76 5.3 NS2 Simulation Param eters 80 .......................................................................... viii Chapter 1 Introduction 1.1 Introduction 1.1.1 B a ck g ro u n d Traditional communication networks such as Internet and cellular networks, have established infrastructure and well regulated controls to facilitate com m unication be­ tween the nodes in those networks. Mobile Ad hoc Network (MANET) is a new class of communication networks where nodes are mobile and they communicate w ith each other w ithout any pre-existing infrastructure [2). T h at is, MANETs are expected to be set up spontaneously in an ad hoc fashion using a collection of mobile nodes to establish communication. They are typically set up for specific purposes under special circumstances. In particular, MANETs are suitable for the scenarios where no established infrastructure is available or even possible. Some scenarios or appli­ cations envisioned for MANETs are: disaster m anagement where th e infrastructure is partially or completely destroyed, communication network for scientific or business conferences held in remote resorts and locations, m ilitary communication network set up in enemy regions during war times, etc. Quick deploym ent with minimal configura­ tion makes MANETs suitable and attractive for many real-life applications. In recent times, in addition to their potential applications, technological advancements in com­ munication and computing have generated a great deal of interest in MANETs [3-5]. Despite their potential use and technological feasibility, setting up and m anaging MANETs effectively are complex tasks. T he topology of MANETs is highly dynam ic as the nodes are expected to move unpredictably. Also, the size of th e network could vary tim e to time as nodes can join and leave th e network a t any time. Due to the complexity, most research studies in MANETs are based on simulations [3,5,6]. MANETs are prim arily set up for message com m unication and message routing is an essential component of message communication. R outing of a message between two nodes, say A and B, in a network is a process of transferring th e message from node A to node B, often involving other interm ediary nodes in the network. As the nodes in MANETs are mobile, the mobility of nodes heavily influences th e routing of a message. Therefore, mobility is one of the fundam ental characteristics of MANETs. As indicated earlier, most research studies on MANETs are done using simulation. Modelling and simulation of MANETs intrinsically involve th e modelling of mobility. Mobility models generate a trace of the mobility of the nodes in the network; th a t, in turn, is used in the performance study of routing and related activities in th e network. A survey conducted in 2005 showed th a t m ost of th e earlier research studies on MANETs were conducted using random mobility models (80% of studies are based on random mobility models.) [3]. Such research studies have been widely criticized for the lack of rigour and accuracy in modelling th e network. Hence, questions have been raised regarding the validity of the sim ulation results [3,7-9]. As modelling the mobility of the nodes plays an integral role in the modelling and sim ulation of 2 MANETs, using the random m obility models is prim arily responsible for th e inaccu­ racies and criticisms. We believe the main reasons for th e continued use of random mobility models are: (i) the simplicity and hence ease of use; (ii) widely supported in the existing MANET sim ulation tools; and (iii) lack of mobility generation and analysis tools supporting alternative and more realistic mobility models. In response to th e criticisms of MANETs simulations, several ideas have been proposed in the literature to increase realism in modelling mobility by including real life objects such as roads, building, etc. [2,4,5,10-13]. Although these proposals improve the appearance of realism, they have increased th e complexity of modelling and implementation of mobility in the simulation studies of MANETs. Therefore, the use of these refined models has been limited and m ost simulation studies on MANETs continue to use the random mobility models [14] even though their use is widely questioned [3,7-9]. Recently, a framework of m obility models called Destination G uided Mobility (DGM) models was proposed [1], The basic idea behind DGM models is th a t a fixed number of destinations are assumed to be an integral part of th e network and the nodes only move between those destinations w ith specified transition probabilities. This set-up is reasonable, realistic, and useful in th a t it is seldom th a t M A N ET nodes walk randomly in the network region (as modelled by the random m obility models). By suitably controlling th e num ber and positions of the destinations and th e m obility of nodes between them, several interesting mobility models w ith improved realism can be modelled and studied. The framework proposed in [1] was primarily aimed a t addressing th e concerns ex­ pressed in [3,7-9] by providing guidelines for mobility model specification an d a soft­ ware tool to generate suitable mobility trace for th e performance studies of MANETs. 3 It was claimed th a t the framework is simple and capable of modelling mobility in a variety of real life scenarios. However, despite th e appeal of the idea behind the proposed framework in modelling various mobility patterns, th e work presented in [1] is limited at least in two aspects: (i) The work presented is preliminary and lacks detailed analysis and study of the proposed mobility models; and (ii) th e software tool presented to generate different DGM mobility models has limited functionality. We feel th a t more study on DGM models is needed to explore the strengths and weak­ nesses of the DGM models so they can be understood well before widely adopted for the performance study of MANETs. This thesis is an extension of the work presented in [1] in the two directions identified above. More specifically, we are interested in studying the versatility and some performance aspects of DGM models. 1 .1.2 M o tiv a tio n As discussed earlier, most past research on the performance study of th e protocols for MANETs have used random mobility models [3,9]. However, the m obility of the nodes in real life MANETs cannot be completely random to be modelled using random mobility models. More specifically, we believe, using random mobility as th e default model for MANETs is a dubious approach to study the performance of MANETs. Also, as indicated earlier, MANETs are application specific and therefore modelling of a MANET is dependent on the scenario th a t it intended to capture. Hence, we concur with the observation reported in the literature [3,7-9] th a t th e performance studies on MANET protocols using random mobility models are not realistic and therefore lack accuracy and credibility. Therefore, for th e research studies on MANETs to be credible and useful, they m ust be conducted based on more realistic mobility models. In this context, realism refers to the closeness of actual scenario to be modelled. Furtherm ore, a model to be widely understood and used, it m ust be simple and generic. 4 We consider a model as generic if, w ith suitable tuning, it can model a large number of common scenarios. T he question here is: • How generic is the DGM framework in modelling mobility of th e nodes in MANETs under different scenarios? Exploring the above question is the prim ary objective of this thesis. This explo­ ration involves several sub-questions th a t need to be addressed including: • W hat are the representative scenarios in which MANETs could be viable? • Is the DGM framework capable of generating mobility traces closer to th e real traces? • How do we illustrate or test whether th e DGM framework is capable of modelling a chosen scenario? • How the proposed DGM mobility modelling tool can be enhanced to support a variety of representative mobility models? Mobility models can be best understood only by studying the behaviour and per­ formance of the nodes in the system. Connectivity is a fundamental requirem ent for communication between nodes [15-21], Establishing a stable connection between nodes of MANETs is necessary for their communication. Mobility of the nodes and their communication range influence the connectivity between them. Since connectiv­ ity has such a fundamental influence on th e performance of th e protocols in MANETs, a systematic study on th e connectivity aspects of more realistic mobility models is critical and necessary. The question here is: 5 • W hat are the interesting connectivity metrics involved in M ANETs and how they can be implemented in mobility generation and analysis tool to study connectivity analysis of supported DGM models? Although it is hard to define th e characteristic of MANETs, the scale-free property and the clustering coefficient have been found to be defining characteristics of various real life networks th a t MANET is intended to model [22]. Scale-free pro p erty relates to a power-law distribution of the degrees of th e nodes, and clustering coefficient defines the propensity of nodes to be gathered in small groups th a t are highly interconnected. These observed basic characteristics of real life networks have been seldom studied in the context of MANETs. An interesting problem here is: • How to implement and explore th e scale-free property and clustering coefficient for a selected set of DGM models? Message routing is an im portant task in com puter networks and it is a process of transferring message from a source node to a destination node. Among th e routing protocols of MANETs, Ad hoc On-dem and Distance Vector (AODV), D ynam ic Source Routing (DSR), and D estination Sequence Distance Vector (DSDV) are th e m ost popular and widely studied. AODV and DSR are reactive protocols th a t establish a route to a destination only on dem and. In contrast, DSDV is a proactive protocol which maintains a routing table at each node containing destination node, next hop, hop count, and other metrics for every other node. These tables of all nodes are updated periodically. We may ask: • How does AODV perform under some representative DGM models as com pared to the RWP model? 6 The above questions are the main m otivations for this thesis. 1.2 C ontributions The objective of this thesis is to explore the behaviour of the DGM models. The main contributions of this thesis are: 1. Enhancement of the DGM mobility generation tool presented in [1], T he tool is enhanced in four main directions: • Redesign of the destination and mobility generation in a way th a t a large number of scenarios can be modelled by setting suitably chosen param eters. • Im plem entation of a comprehensive set of performance m etrics to analyse the mobility trace. • Design and integration of a model and comparison with real traces. • Design and integration of a component to visualize the result of th e per­ formance of mobility models. We refer to the enhanced mobility generation and analysis tool as DGM Gen. 2. An illustration of the generality of th e DGM framework provided by modelling various real world scenarios. 3. An experimental evaluation of performance metrics such as average num ber of contacts, average number of connection changes, average contact tim e, contact time distribution, inter-contact tim e distribution, node degree distribution, clus­ tering coefficient, and fc-hop paths, etc., for a set of DGM models is conducted and compared with th a t of the RW P model. 7 4. An experimental evaluation of the traces generated by the studied models is conducted and compared w ith the traces observed in real scenarios. 5. A study on the performance im pact of the DGM models on one of th e popular routing protocols (AODV) of M ANET is presented using NS2. 1.3 O rganization of T his T hesis The docum entation of this research work is distributed in the remaining five chap­ ters. Chapter 2 provides the literature review related to this thesis work. More specifically, it provides th e literature review on mobility models, connectivity anal­ ysis, real traces, performance analysis of routing protocols, and mobility generation tools. The selected performance metrics for analysing mobility models and evaluating the performance of routing protocols under the influence of DGM models have been presented in C hapter 3. C hapter 4 presents the trace generation and network explo­ ration tool we enhanced for analysing th e traces. A set of experiments for showing the versatility of the DGM models and for evaluating th e performance of th e DGM m od­ els including RWP model and their im pact on th e performance of the AODV routing protocol is presented in C hapter 5. Finally, C hapter 6 summarizes this research effort and outlines the directions for further research. 8 Chapter 2 Literature Review The work presented in this thesis is related to mobility models for MANETs, real trace analysis, software tool for mobility trace generation and analysis, network per­ formance analysis, and M ANET routing protocols. This chapter provides the litera­ ture survey related to the above five topics. Section 2.1 and Section 2.2 review related mobility models and the im portance of real mobility traces for the study of MANETs. Section 2.3 reviews the related mobility trace generation and analysis tools. Section 2.4 describes the network performance analysis emphasizing the connectivity metrics. Finally, Section 2.5 provides a brief survey on MANET routing protocols. 2.1 M obility M odels Mobility models play an influential role in the simulation studies of MANETs, and they are used to represent the movement patterns of mobile nodes for th e M AN ET scenarios to be studied. There are several surveys available for mobility models pro­ posed for MANETs [2,11,13,23,24], and a comprehensive survey can be found in [5]. In this chapter, to set the context, we review only a representative set of mobility 9 models. Brownian motion [25] is one of the simplest and oldest basic mobility models to represent the unpredictable movement of th e entities of a system. In this model, each entity moves from its current location to new location by choosing a random direction and a random speed until it hits another entity or the boundary. This model was proposed to mimic the movements of particles in a fluid. The R andom Direction Mobility Model (RDMM) [26,27] can be considered as a variation of Brownian motion. In the RDMM, each mobile node moves from its current location to a new location by randomly choosing a direction 6 from th e interval [0, 2ix) using a uniform distribution and randomly choosing a speed using a normal distribution in some given range. Then the node travels for a selected tim e period and th e process is repeated. In this model, when a node hits the boundary of the simulation field, th e node is bounced back in the simulation region w ith an angle of —0 or (it — 0) if th e node hits th e horizontal boundary. A number of simplified derivatives of th is model has been introduced in [28]. One of the im portant derivatives is Random Walk Mobility Model [11], where each mobile node chooses a direction 6 from th e interval [0, 27t), selects th e speed between 0 and 10 m /s, and then travels either for a fixed num ber of steps or fixed tim e period such as 60 seconds. Then the process repeats. A nother variation is R andom Drunken Mobility Model [29] where a node periodically moves to a position chosen random ly from its immediate neighbouring positions as long as the new position is w ithin the coverage area. T he frequency of the change of nodes’ positions can be controlled based on user-defined param eters. The Random W aypoint (RWP) model introduced in [30], is the m ost widely used random mobility model in M ANET simulations where each mobile node random ly selects one point (waypoint) in th e simulation area as the destination and th en travels to the chosen destination with constant speed chosen from a given range using uniform 10 distribution. Upon reaching th e destination, the node pauses for a fixed period called pause time which is chosen uniformly from a specific range. After this duration, the node chooses another random point in the sim ulation area and continues in th e same way until the simulation time period is over. RDMM and RW P are th e basic random mobility models used in MANETs. All other random mobility models proposed later are variations of these two models. It is observed in [2] th a t in varying velocity range and pause time in RWP model, various mobility scenarios with different levels of nodal speed can be generated. For example, we can generate a relatively stationary network if we choose speed w ithin a range of smaller velocities and long pause time; similarly we can create a highly dynamic network by choosing speed w ithin a range of higher velocities and small pause time. Several variations have been proposed to increase realism by controlling the speed, the direction, an d /o r th e destination. Two im portant variations of th e RW P model are the Random Borderpoint Model [31] and the Realistic Mobility Model [32]. The objective of the Random Borderpoint Model [31] is to create h o t spots in the simulation area where clusters of nodes can be located at any time. In this model, destinations are only located at the border region of the simulation area. A lthough the model is simplified for m athem atical derivations, due to th e restriction of destination to th e border area it creates some non-uniform node distribution in th e sim ulation region. The basic idea behind the Realistic Mobility Model [32] is that th e nodes select an initial speed and a direction of movement. A t discrete time steps, which are determined by the simulation environment, th e speed and direction of movement are re-evaluated, based on the current state of th e mobile node, and using a Markovian process. 11 The Gauss-Markov Mobility Model [33] and th e Smooth Random M obility Model [26] are tem poral dependent mobility models where th e velocity of mobile node is correlated over time. The Gauss-Markov model uses memory history to represent the degree of dependency and a variety of mobility models can be generated based on the weak or strong memory history. In Smooth Random model, in a given range, a set of speed values with fixed probabilities are specified and th e remaining speeds are chosen using a uniform distribution. Along th e way, acceleration and deceleration are introduced and they are chosen uniformly w ithin the given ranges. T he movement direction is uniformly distributed in the interval [0, 27t]. The Freeway Mobility Model [34], the M anhattan Mobility Model [34], th e City Section Mobility Model [35] and the Obstacle Mobility Model [6] go one step further to represent reality by introducing real life objects to the implementation. B ut these models are very scenario specific and require considerable effort in incorporating real life objects into the model. In m ost of these models, th e selection of a destination and initial distribution follows th e RWP model. To capture the battle field scenarios, th e disaster management scenarios and the other scenarios where a group of people work to achieve one objective, a num ber of mobility models such as the Reference Point Group Mobility (RPGM) M odel [36], the Reference Velocity Group Mobility (RVGM) Model [37], the Colum n Mobility Model [11,38], the Pursue Mobility Model [11,38], and th e Nomadic Com m unity Mobility Model [11,38] have been introduced. In these models, a group of nodes shares a common mobility pattern. More specifically, each group has a logical center which controls the movement patterns (i.e., speed, direction, acceleration, deceleration, etc.) of all its member nodes. In the RVGM model, a mean velocity of a group is used as the velocity for th a t group. However, in these models, the logical center is chosen based on the RWP model. The V irtual Track Based Mobility Model [39] is another 12 group mobility model where a group of nodes moves as a group along a track. This model captures the two im portant group dynamics such as split and merge. Recently a generic framework is proposed in [1] th a t can generate a set of m obility models called th e DGM models. The basic idea behind DGM models is th a t a fixed number of destinations are assumed to be an integral p a rt of the network and the nodes only move between the destinations. This is a reasonable, realistic, and use­ ful assumption th a t seldom M ANET nodes walk randomly in the network region (as modelled by th e random mobility models). By suitably controlling th e num ber and positions of the destinations, and the mobility of nodes between them, several inter­ esting mobility models w ith increased realism can be modelled and studied. Since this thesis is prim arily interested in studying DGM models, we reproduce th e definition of M ANET incorporating DGM models given in [1]. D efin itio n 1 A M A N E T is a sextuple < 91, fKm,2),5!D,55,3c > ; where 91 - a finite set o f mobile nodes. - mobility space where the mobile nodes can move. D - a finite set o f destinations within fRm. - a function to choose a destination from 5?. 5s - a function to choose travel speed. 5c - a function from 2) x 2) to {0,1}. 5c(di,dj) = 1 means th e destinations dt and dj are connected and therefore communicate. W ith suitable im plem entation of 5c, various types of MANETs can be designed. If ViVj,'[5c(di, dj) — 0] then the described M A N ET has no communication infrastructure. 13 D e fin itio n 2 A p a u s e p o f a node is a period in which it is stationary. D e fin itio n 3 A leg t is a continuous m ovem ent fro m its current location to a new location in 2). Using p and r , we define th e mobility of an individual node in 0 such th a t P{ x) « x~x 31 for large x. An im portant property of scale-free networks is th e preferential attachment and growth. Social networks, cellular metabolism, research collabo­ rations, world wide web and protein interaction are some examples of scale-free networks. To measure at which extent a network is scale-free, th e scale-free metric is proposed in [68]. A more explanation regarding this m etric can be found in [68,74,75]. To define the scale-free metric in a simplified way, let — G = (V, E) be a graph where V and E are th e sets of nodes and edges, respectively, — etj denotes an edge between nodes i and j, — deg(i) is the degree of node i € V, — H denotes the set of all the graphs having the identical node degree distri­ bution of G. the m etric s(G) is defined [75] as s(G) = ■deg(j). eijZE The value of s(G) is maximized when high degree nodes are connected to other high degree nodes and s ( G) depends only on the graph G not th e process of how G has been constructed. Therefore, th e scale-free metric can be defined as S( G) = where Smax is the maximized value of s( H) . If S ( G ) closes to 0, th e graph/netw ork is scale-rich and if S (G ) closes to 1, th e network is scale-free [68,75]. 32 3.4 Perform ance M etrics for R ou tin g P rotocols To compare the im pact of th e DGM models in comparison to th e RW P model on performance of routing protocols (e.g., AODV) in MANETs, we use th e following metrics. • Data loss ( D r ) : It is th e ratio between the num ber of lost packets ( N l ) and the number of generated d a ta packets (N t )• T h a t is, DL - ^ . Nx • Data delivery ratio ( D r ) : It is th e ratio between th e number of received d a ta packets ( N r ) and th e num ber of generated d a ta packets. Formally, r> - N « Dr~ W • End-to-end delay ( E d ): It is th e tim e between send and receipt of th e d a ta packet. D ata loss and d a ta delivery ration are usually estim ated in percentage (i.e., ( D l -100%) and ( D r • 100%), respectively). 3.5 Sum m ary In this chapter, we described the performance metrics for analysing th e connec­ tivity of the mobility models and evaluating the performance of the M A N ET routing protocols. First, we explained th e basic concept of connectivity that reflects th e pres­ ence of the connection between nodes. Then, we summarized some im p o rtan t connec33 tivity metrics. These metrics are used to evaluate DGM models. T hree perform ance metrics for analysing MANET routing protocol performance were also discussed. 34 Chapter 4 Trace Generation and Network Exploration Tools This chapter describes the architecture and the functionality of the mobility gener­ ation and analysis tool, DGMGen. It also describes the architecture of th e routing protocol performance suite designed for analysing th e performance of a M AN ET ro u t­ ing protocol. Section 4.1 describes th e higher level architecture of DGM Gen and its main components. Section 4.2 explains DGM Gen from users’ point of view. Section 4.3 presents the higher level architecture of th e routing protocol performance suite. Finally, Section 4.4 gives a brief sum m ary of this chapter. 4.1 D G M G en - A rchitecture DGMGen is a software tool th a t can be used to generate th e trace of mobile nodes in a MANET using DGM models and analyse the trace by visualizing th e movements and performance metrics. The tool has a graphical user interface to set in p u t param ­ eters, to visualize the movements, to com pute performance metrics, and to show the 35 results dynamically. Internally, it has com ponents to model the destinations and the mobility of nodes, to create mobility trace, to com pute performance and anim ation geometries, and to parse real traces. The higher level architecture of DGM G en is given in Fig. 4.1. I Performance Observation Window Parameter Setting Window S/////////Z///S | Animation Window | Destination Creation sz. Real Trace Parser Mobility Trace Generator 777777777/777. Animation -----1/ '<■ Engine ■ ^ k Performance Calculation Engine '//////////, W ///////J , Mobility Trace Exporter Figure 4.1: Higher Level Architecture of the DGMGen Tool The development of the DGMGen started in [l], as a p art of the effort to present a DGM framework to model and generate mobility traces. In that effort, five com­ ponents Parameter Setting Window, Destination Creation, Mobility Trace Generator, Anim ation Engine, and Anim ation Window were implemented. These com ponents are shown in bold (solid and dotted) rectangles. The remaining com ponents have been added to increase its functionality. T he dotted bold rectangles indicate th a t 36 the components have been redesigned to enhance the capability of generating more variations of DGM models. The shaded rectangles such as Real Trace, Mobility Trace and Different Trace Formats represent simple files containing the mobility traces in different formats. The functionality of the m ain components of our developed tool are briefly de­ scribed as follows: • P a r a m e te r S e ttin g W in d o w : This component is used for initializing the sim­ ulation param eters like simulation area, simulation s ta rt and end times, speci­ fication of mobility, speed and pause-time ranges, probability distributions for choosing speed and pause, and startin g the basic simulation environment. It is also used to im port real trace files as well as previously saved param eter setting files. • D e s tin a tio n C re a tio n : This component basically helps to create destinations in two modes: (i) one a t a tim e and (ii) as random clusters. The tool also allows addition or deletion of destinations, individually or a t a cluster level. While creating a random cluster of destinations, th e steps of addition and deletion can be repeated until a desired scenario of destinations is created. • M o b ility T ra c e G e n e r a to r: The mobility trace generator is accountable for placing the mobile nodes and generating their mobility trace based on the de­ fined param eters. The generated trace, referred to as Mobility Trace, contains information required for visualization and statistical an d /o r connectivity infor­ m ation for further analysis in th e Performance Calculation Engine. • A n im a tio n E n g in e : This com ponent refines the mobility trace and makes the trace in a presentable form for th e Anim ation Window. 37 • A n im a tio n W in d o w : This window is used for animating th e nodes’ move­ ment and visualizing the traces for individual node, as well as for all th e nodes together. • R e a l T rac e: Real trace is a mobility trace collected from a real-world network or a practical system. For this thesis, we obtained the real trace from the CRAWDAD repository [761• R e a l T ra c e P a r s e r : This is a parser module which takes the raw real trace d ata as input from a file, parses it, and produces th e trace into a form at convenient for the Performance Calculation Engine module. • P e rfo rm a n c e C a lc u la tio n E n g in e : The Performance Calculation Engine is responsible for analysing the mobility trace (real or synthetic). It takes different synthetic traces generated by mobility models and refined real trace from the Real Trace Parser module, com putes the performance metrics of these traces and stores the results in different d a ta structures for graphical representation. • M o b ility T ra c e E x p o r te r : This com ponent allows users to export th e mobil­ ity trace into a desired form at (e.g., NS2, NAM) so th a t it can further be used in the simulation studies of the M ANET routing protocols. • P e rfo rm a n c e O b s e rv a tio n W in d o w : This window is used for observing the different performance metrics graphically. It takes th e numerical result of each performance metric from the Performance Calculation Engine and presents it graphically. The results can be viewed for individual ru n as well as for m ultiple runs at the same time. DGMGen has four main logical functions th a t are typically invoked in th e order for a typical use. 38 • D e s tin a tio n s C re a tio n : To create desired destinations. • M o b ility T ra c e G e n e r a tio n : To generate the trace of the mobile nodes in the system for the desired period. • M o b ility T ra c e A n a ly s is : To analyse the trace visually and using statistical param eters to study the properties of the trace. • M o b ility T ra c e E x p o r ta tio n : To transform the trace in a form at th a t can be used in the network simulator. 4.2 D G M G en- Im p lem en tation and U se The DGMGen has been implem ented in Java. W ith th e help of N etBeans ID E 7.0.1, we used Java Swing package, the AWT package and th e open source jF reeC hart -1.0.13 package to build the graphical user interface (GUI) for the DGM Gen. The GUI components of DGMGen have been implemented as hierarchical panels. The seven main GUI components are described here. • P a r a m e te r S e ttin g W in d o w : T he param eter setting window shown in Fig. 4.2 is used to configure th e param eters for th e simulation. It allows users to set simulation param eters and node param eters. The input for the sim ulation pa­ rameters are: simulation w idth, simulation height, duration of sim ulation, warm up period, node class, and m obility model. T he input for the node param eters are: number of nodes (or num ber of groups and number of members in a group), speed range, pause time range, transm ission range, and default probability dis­ tributions for choosing speed and pause time. The param eter Boundary A ction is only used for the RW P model which has been implemented in th is tool for comparative analysis purpose. After setting the node param eters, th e user can 39 C onfiguration Configuration Fite: Simulation Parameters Simulation W id th : ____ [SOOQ j (m e te rs ) Duration : ( se c o n d s ) Simulation H eight: [2000 W arm u p perio d : [100 Mobility M odel: ) ( m e te rs ) Mode C l a s s : >1 - N o d e P a r a m e t e r s -- N um ber o f n o d e s : Speed: |50 j U <*> P a u s e T im e: jo_ __j to T ran sm issio n R ange : iso D istrib u tio n s: \2 ' 'j ~| jurtrt'onrTj ^ j (se c o n d s ) D istributions: (u n ito rrn ” (m e te rs) jR e s ta r t Boundary Action : Mode C lass P a r a m e te r tto tte C fa s I......” j^ j ..... 11 1 • ►i P r o c e e d to (destination CreBtkm S av e C onfiguration Figure 4.2: The P aram eter Setting Window. add the configured param eters into th e Node Class Parameter list by pressing the Double Right Arrow button. Once the simulation param eters and th e node param eters are entered, th e user can save th e configuration into a file by press­ ing the Save Configuration button. The Browse and Load b u tto n s are used to retrieve the previously saved configuration file for simulation study. Once th e simulation configuration is ready, the user can proceed to th e D estination Creation phase by pressing the Proceed to D estination Creation button. • M o b ility G enerator an d A n im a tio n P anel: The mobility generator and an­ im ation panel depicted in Fig. 4.3 is used to create destinations (individual or cluster), set priority for transition m atrix, generate mobility, see th e generated traces, run animation, and save the created destination configuration into a file. This component has four parts: Destination Draw and Animation, Individual, Cluster, and Mobility Generator panels. First, the user can create destinations 40 ( Destination Draw and Animation ' Random Creation £ Refresh Set Priority j Ouster 1 s iz e fl_ 3 NoQf d e s tin a tio n s [_ Figure 4.3: The Mobility Generator and Animation Panel. in the anim ation window panel by pressing the Refresh button. T he user can also manually add or delete destinations into/from the Destination Draw and Anim ation panel after pressing the Add and Delete buttons respectively. The Set Priority button is used to set priority to any designed destination individu­ ally. To design a cluster-based scenario, at first, a user needs to set th e cluster size and the number of destinations in th e cluster in th e Size box and th e No. of destinations box respectively. Thereafter, by pressing the Create Cluster b u t­ ton, one can create his/her desired cluster in the Animation panel by clicking the mouse. Once th e destination creation is done, th e user can generate mo­ bility by pressing th e Generate Mobility button, observe the trace graphically by pressing the Trace button (Node box is used if user wants to see th e trace of one selected node), run the anim ation by pressing th e Animate bu tto n , and save the destination configuration into a file by pressing the Capture button. 41 Pair-level Statistics Multiple Scenarios Performance Analysis Movement Trace for Node # R 1 Coimecthifty Irrfo t o Alt n o d e s .......... \ Dismay Connectivity Info Peerld c o n n ected 15 25 0 0 ,84 1 154 25 ^i“ir 0 2 3 4 5 6 7 ................. et D isco n n ected D irected 0 5397 0 5387 5412 0 5 41 2 0 48 5328 54 5358 5387 25 Aa.OjR sCZ indirect 15 25 O o ------------- Connectivity In fo w ith a n Indivtdoal Node 36 O O n----------1--------------1 — ........ Enter a peer node IDand dick the Putton To From 0 54 79 706 •y a ** ..... 54 79 706 742 ........ * O C (=. Type S tate OFF ON OFF ON r ^ c tz - Direct - indirect J I "1 ■ : Figure 4.4: The Pair-level Statistics Panel. • P a ir-le v e l S ta tis tic s P a n e l: This panel shown in Fig. 4.4 is used for observing the contact time and inter-contact time among node pairs. This com ponent basically allows the user to observe th e connectivity (e.g., connection by link or path, contact duration of each individual connection between each node pair, inter-contact time, and so on) among nodes. By p u ttin g one node num ber in the Movement Trace fo r Node # box and pressing th e Display Connectivity Info button, one can observe the to tal connected time, disconnected tim e, directly connected time, or indirectly connected tim e of the given node w ith all other nodes in the upper table. Inserting a peer node ID in the box preceded the Display button and then pressing the button, the user can observe each contact duration (e.g.,From, To, State, and Type) and inter-contact tim e of th e given node with the provided peer node. • S ingle S c e n a rio P e r f o r m a n c e A n a ly s is P a n e l: Both the Single Scenario 42 [ Average Statistics ' Distribution Real Trace Statistics Average Trace Statistics: Average njmber cf Connection changes : 4.9 tm es Average number of Contacts ; 2.4 times Average Session Duration : 32.9 seconds Average Path Duration : 9.0 secconds. Average Link Duration : 50.5 seconds. Average Path Availably : 82.8% Figure 4.5: The Average Statistics Sub-panel. Performance Analysis and the Multiple Scenarios Performance Analysis panels are used to measure the same set of performance metrics. But th e Single Sce­ nario Performance Analysis Panel is used to observe th e performance m etrics for an individual scenario whereas th e Multiple Scenarios Performance Analysis Panel is designed to observe the performance metrics for multiple runs a t the same time. This panel has three sub-panels: Average Statistics, D istribution and Real Trace Statistics. Figure 4.5 expands the Average Statistics sub-panel where the user can observe average num ber of connection changes, average num ber of contacts, average contact duration, link duration and p ath duration by pressing the Average Trace Statistics button. Figure 4.6 expands the D istribution sub­ panel under the Single Scenario Performance Analysis Panel where th e user can observe node degree distribution, node degree distribution a t a particular 43 f Average Statistics | Distribution \ Real Trace Statistics Degree Distribution N o d s D egree D estitu tio n N ode D egree Otsirfcution s i Contact Time Distribution A verage N o d e D egree inter-contact Time Distribution N ode D egree o n InSeval N od e d e g r e e d istr ib u tio n @ 1 0 0 th se c o 20 S 10 1.0 1.5 2.0 2.5 3.0 3.5 N o d e d eg ree 4.0 RDGM model Figure 4.6: The D istribution Sub-panel. tim e (e.g., node degree distribution at 100th second has been shown graphically for RDGM model by pressing the Node Degree Distribution at bu tto n ), aver­ age node degree, node degree at interval, clustering coefficient, contact-tim e distribution and inter-contact tim e distribution by pressing th e corresponding captioned buttons. Figure 4.7 expands th e Real Trace Statistics sub-panel. Using this com ponent, the user can read a real trace file by selecting th e trace name in the Real Trace Analysis combo-box and then pressing th e Read Trace button. Thereafter, the user can observe contact-tim e and inter-contact tim e distribution graphically by pressing the Inter-contact Time D istribution and Contact Tim e Distribution buttons respectively. • M u ltip le S c e n a rio s P e rfo rm a n c e A n a ly s is P a n e l: This com ponent shown 44 Average Statistics \ Distribution \ Rea) Trace Statistics Real Trace Analysis Careibridge-intel Read Trace Contact Time Distribution Sinter-contact Time Distribution1 In te r -C o n ta c t tim e d istrib u tio n A 1.00 0.75 0.50 0.25 0.00 m too 10000 tim e(s) [•— Intel Trace Figure 4.7: The Real Trace Statistics Sub-panel. in Fig. 4.8 is designed for measuring the same set of performance m etrics as the Single Scenario Performance Analysis Panel. B ut it is used to observe th e per­ formance metrics of multiple scenarios a t the same time. The user can execute multiple runs (multiple models) at the same time in th e DGMGen and anal­ yse their comparative results using this panel. The panel has two sub-panels: Computation and Result. In the Computation sub-panel, pressing th e Average Trace Statistics button, th e user can analyse the average num ber of connec­ tion changes, the average num ber of contacts, the average contact duration, the link duration and th e p ath duration for multiple runs simultaneously. Using the K -hop Paths button, the p ath of distinct lengths are calculated for the entire simulation time. Similarly, the Clustering Coefficient, th e Node Degree Distribution, and the Contact Time & Inter-contact Tim e Distribution compo- 45 f Pair-level Statistics \ Multiple Scenarios Performance Analysts Com putation A verage T r a ce S ta tistic s C o n ta ct Tim e Distribution J K-tiop P attis Inter-C ontact T im e Distribution j I ttode D e g ree distribution C lustering C oefficien t ; R e s u lt ----------------------------------------- ------- ------------- ------------------- V iew C om parative R esu lt Figure 4.8: The Multiple Scenarios Performance Analysis Panel. nents provide the facility to measure th e clustering coefficient, th e node degree distribution, the contact tim e distribution, and inter-contact tim e distribution respectively. All of these components allow multiple, simultaneous runs for analysing the respective metrics. T he buttons in the Computation sub-panel are used to calculate the respective metrics and store the num erical results. The user can observe the calculated results by pressing the View Comparative Result button. The View Comparative Result bu tto n pops up th e Performance Observation Window where the user can observe th eir calculated m etrics one by one. • P e rfo rm a n c e O b s e rv a tio n W in d o w : The performance observation window, shown in Fig. 4.9 allows the user to observe th e result dynamically in graphical mode. The window has an option to choose the performance m etrics to be 46 @ Graphical ^presentation: Performance M e tr ic ^ S Comparative Analysis Selected P erform ance Uetric for C&s ervsfcon Avsrage num ber of contacts varying s p e e d Select Performance Metric Sho\y Graph Average number of contacts Number of Contacts Vs Speed 4 S 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Maximum speed (m/s) 14 ^ RDGM model i f r RCDCM model ♦RDCRPGM m odel 4»-RWP model | Figure 4.9: The Performance Observation Window in the DGMGen. Single Scenarton Slat Indivkiual Stat Connectivity Analysis Generate Trace SrisL af 49 5 3 '~ & n 6 d & Z X * & ).setd est 2 5 .0 0 1 90 7.0 0 7 .46 “ S ns at 3 36.08 “Snode_C49> s e t d e s t 5 44 .00 8 2 3 .0 0 9.88“ Sn.s_ a t 4 5 9 .5 3 “S n o d e C.49) s e t d e s t 1 6 6 6 .0 0 123 2.0 0 3.10" S n s „ at 6 08.28 “Snode_<49> s e t d e s t 3 7 8 .0 0 7 1 1..00 7.72“ S ns at 7 88 .8 2 “Snode_<49> s e t d e s t 1 8 1 9 .0 0 1 3 1 4 .0 0 8 .01 “ $ n s _ at 9 8 4 .9 5 “Snode_C49> s e t d e s t 9 52 .0 0 1 5 1 5 .0 0 5.25* Sns at 115 6.1 2 ~Snode_{49> s e t d e s t 1485.00 103 1.0 0 7 .03 “ S n s_ at 1259.83 “$ nade_(49> s e t d e s t 3 21 .00 1 9 5 4 .0 0 7.17" S n s _ a t 1 4 6 8 .2 3 “Snode_(49> s e t d e s t 1 2 3 .0 0 4 2 2 .0 0 6.19“ S n s _ at 1 71 9.6 2 “Snode_(49> s e t d e s t 2 2 .0 0 1 92 0.0 0 9.62“ S n s_ at 1877.09 “Snode_<49> s e t d e s t 1 18 0.0 0 5 3 1 .0 0 7 .4 3 “ Sns__ a t 2122.2.3 “Snode_(49> s e t d e s t 7 7 3 .0 0 1 68 5.0 0 5 2 6 “ S n s _ a t 2 3 5 5 .0 7 “$node_(49> s e t d e s t 5 8 9 .0 0 1 0 9 2 .0 0 7 .04 “ Sns__ a t 2 4 4 3 .3 5 “S n o d e _ (4 9 ) s e t d e s t 6 7 7 .0 0 9 5 4 .0 0 9.10" S n s _ at 2 46 2.1 4 “Snode_jC49) s e t d e s t 8 20 .0 0 1 0 8 6 .0 0 6 .53 “ S n s _ at 2 4 9 2 .0 5 “S n o d e _ (4 9 ) s e t d e s t 5 44 .0 0 8 2 3 .0 0 7 .65 “ S n s _ at 2 5 4 3 .4 2 “S n o d e _ (4 9 ) s e t d e s t 1 2 0 4 .0 0 5 4 7 .0 0 9 .64 “ Sns at 2 6 1 8 .7 6 “SriOde_j£49) s e t d e s t 7 6 5 .0 0 5 9 6 .0 0 7.68“ S n s_ at 2 6 7 7 .3 5 “$ n o d e _ (4 9 ) s e t d e s t 9 22 .00 6 6 4 .0 0 5 .5 8 “ S n s _ at 2 7 0 9 .0 0 “$ n o d e _ (4 9 ) s e t d e s t 7 1 8 .0 0 1 6 3 5 .0 0 5.71" 3 n s _ at 2 8 8 3 .4 5 “Snode_(49> s e t d e s t 1766.00 8 4 5 .0 0 8 .3 6 “ S n s_ at 3 0 4 1 .7 7 “S n o d e _ (4 9 ) s e t d e s t 1 7 0 9 .0 0 1 5 47 .00 8.52* S n s _ at 312 4,5 8 “Snode_(49> s e t d e s t 2 0 8 .0 0 1 6 7 1 .0 0 8.30" S n s _ at 3 3 0 5 .5 9 "Snode_(49> s e t d e s t 1 23 .00 4 2 2 .0 0 8.79" S n s _ at 3 4 5 0 .9 3 “5node_<49) s e t d e s t 1 99 0.0 0 1 1 8 3 .0 0 5 .89 “ Figure 4.10: The Export Trace Panel of th e DGMGen. 47 observed out of a list of performance metrics. M ultiple simulation runs can be observed and th e results can be compared a t th e same time. T he user can analyse any metric choosing the desired m etric from th e given list of metrics. • T ra c e E x p o r te r P a n e l: The trace exporter panel shown in Fig. 4.10 is used to convert the generated mobility trace of a particular scenario into th e desired network simulator form at so th a t it can be used for analysing th e different protocols. This com ponent allows th e user to convert the generated m obility trace into NS2, GlomoSim, and NAM format. T he user can generate their desired trace by selecting th e trace nam e from the given Combobox selector and then pressing the Generate Trace button. As an example, the NS2 trace shown in the box in the Fig. 4.10 is obtained by selecting th e NS2 form at in th e drop down combo-box and then pressing th e Generate Trace button. 4.3 R outing P rotocol Perform ance Suite The higher level architecture of the routing protocol performance suite is shown in Fig. 4.11. It has six com ponents th a t are described next. • M o b ility T ra c e in N S 2 F o r m a t: This com ponent is a file containing a mo­ bility trace generated by DGMGen. The trace is in NS2 format so th a t the performance of a routing protocol can be executed and tested in NS2. • T C L S c rip t: This com ponent is the TCL (Tool Command Language) script for the routing protocol to be studied. To study the im pact of th e DGM models, we write the TCL scripts for sim ulating AODV routing protocol for various con­ figurations and run these TC L scripts using th e traces imported from DGM Gen in NS2 simulation environm ent (shown in Fig 4.12). During th e execution of 48 M obility Trace in NS2 Form at TCL Script For R outing P rotocol NS2 Routing P rotocol Trace from NS2 NS2 T race Parser P erfo rm a n ce O b serv a tio n W in d o w Figure 4.11: The Routing Protocol Performance Suite those scripts, NS2 generates traces of the AODV routing protocol. T he Traces are stored for further analysis. • N S 2 : The network simulator (NS2) [47], developed by the V INT project sup­ ported by DARPA, is a discrete event simulator th a t provides substantial sup­ port for th e simulation of the Transmission Control Protocol (T C P) and routing protocols over wired and wireless networks including satellite networks. This sim ulator provides an environment to sim ulate mobile nodes w ith wireless inter­ face as well as multi-hop wireless ad hoc networks. By default, th e NS2 supports random waypoint mobility model; however, any mobility model can be im ported into NS2 to test the performance of the intended protocols. We used this tool to study the AODV routing protocol. • R o u tin g P r o to c o l T ra c e s F ro m N S 2 : After running the TCL script w ritten 49 ^ 0 9 ram : aadv20D.ram Figure 4.12: A GUI Snapshot of AODV Simulation in Ad Hoc Network in NS2. s 7.915032539 _ 1_ AGT — 23 cbr 512 [0 0 0 0 ] ------ [1:0 2:0 32 0] [22] 0 0 r 7.915032539 _ 1_ RTR — 23 c b r512 [ 0 0 0 0 ] ------- [1:0 2:0 32 0] [22] 0 0 s 7.915032539 _ 1_ RTR — 23 cbr 532 [0 0 0 0 ] ------- [1:0 2:0 30 2] [22] 0 0 s 7.915107539 _ 1_ MAC — 0 R T S 4 4 [1 4 e e 2 1 0] r 7.915459565 _2_ MAC — 0 R T S 4 4 [1 4 e e 2 1 0] s 7.915469565 _2_ MAC — 0C T S 38 [13b4 1 0 0] r 7.915773590 MAC — 0C T S 38 [13b4 1 0 0] s 7.915783590 _ 1_ MAC — 23 cbr 590 [13a 2 1 800] ------- [1:0 2:0 30 2] [22] 0 0 r 7.920503616 _2_ MAC — 23 cbr 532 [13a 2 1 800] ------- [1:0 2:0 30 2] [22] 1 0 s 7.920513616 _2_ MAC — 0 ACK 38 [0 1 0 0] r 7.920528616 _2_ AGT — 23 cbr 532 [13a 2 1 800]- ------ [1:0 2:0 30 2] [22] 1 0 r 7.920817641 MAC — 0 ACK 38 [0 1 0 0] s 7.967622462 AGT — 24 cbr 512 [0 0 0 0 ] ------ [7:2 9:0 32 0] [ 1] 0 0 r 7.967622462 _7_ RTR — 24 cbr 512 [0 0 0 0 ] ------- [7:2 9:0 32 0] [1 ]0 0 s 7.967622462 _7_ RTR — 24 cbr 532 [0 0 0 0 ] ------- [7:2 9:0 30 9] [1 ]0 0 Figure 4.13: A Snapshot of AODV Routing Trace File in NS2 50 for the routing protocol which uses th e synthetic mobility trace generated by any of the studied mobility models, the NS2 generates the traces called the routing protocol trace. As an example, a snapshot of a routing protocol trace from NS2 is shown in Fig. 4.13. For each run, one routing trace file is obtained. Those files are stored for further analysis in the NS2 Trace Parser module. • N S 2 T ra c e P a r s e r : This is a Java-based parser which takes routing proto­ col trace file(s) as input, analyses them , and produces a numerical result. It basically parses the trace im ported from NS2 and provides th e inform ation of how much d ata have been successfully transferred, w hat is th e delivery ratio, and what is the end-to-end delay for sending the d a ta packet. T he num erical result is sent to the Performance Observation Window for observing th e result graphically. • P e rfo rm a n c e O b s e rv a tio n W in d o w : This module is used to visually observe the studied performance metrics of routing protocols. It takes th e num erical result from the NS2 Trace Parser and displays the results graphically. 4.4 Sum m ary In this chapter, we presented th e higher level architecture of the DGM G en with its background. We also described how the developed tool can be used to generate the mobility traces, im port the real traces, visualize and analyse th e connectivity characteristics of those traces, compare those trace characteristics dynamically, export the generated trace into different network sim ulator formats, and finally produce the result graphically. A higher level architecture of the routing protocol perform ance suite has also been discussed. In the next chapter, we will present th e experim ents we conducted for analysing the DGM models and evaluating the performance of one 51 routing protocol using these tools. Chapter 5 Exploration of DG M M odels The objective of this chapter is to present our study on DGM models. The study is conducted with two main objectives in mind: i) to illustrate th e versatility of th e DGM models, and ii) to analyse DGM models using connectivity metrics in com parison w ith RWP mobility model. The chapter is organized as follows. After providing a brief discussion on DGM models in Section 5.1, we present some representative real-world scenarios in Section 5.2 and, in Section 5.3, show how the different real-world scenarios can be suitably modelled using DGM models. Section 5.4 presents a set of experiments we conducted for analysing the performance (connectivity) of th e m obility traces generated by DGM models. A comparative analysis between th e generated synthetic trace and th e real trace has been shown in Section 5.5. Section 5.6 describes two sets of experim ents for evaluating the impact of the studied mobility models on the performance of the AODV routing protocol. We conclude th e chapter by providing a brief sum m ary in Section 5.7. 53 5.1 D G M M odels We s ta rt with restating the definition of M ANET provided in [1]: A MANET is a sextuple < 91,9tm,2 ),3 s,3 s,3 c >> where 91 - a finite set of mobile nodes. 91m - mobility space where the mobile nodes can move. D - a finite set of destinations w ithin 9lm. 3 s - a function to choose a destination from 3). 3s - a function to choose travel speed. 3c - a function from 2) x T) to {0,1}. 3c(di, d j) = 1 means the destinations di and dj are connected and therefore they communicate. W ith suitable im plem entation of 3c, various types of MANETs can be designed. If VzV^[3c(di, dj) = 0] th en the described M AN ET has no communication infrastructure. The models generated using the above framework are called DGM models. The most significant components in this definition of M ANET are th e destination selection function 3 s and the speed selection function 3s- They essentially model the transition probabilities and are highly abstract. These two functions 3® and 3s, when implemented properly, can introduce realism in various levels. T h a t is, using these two functions, we can model various scenarios by properly controlling bo th the probability for choosing the next destination to move and th e probability for choosing the speed to travel. 54 The type of destination, the time, the role, and the speed of the mobile nodes can heavily influence these functions. As an example, let th e destination be a bus stop, the tim e be a morning, and th e mobile node be a college student. As individuals usually follow significant regularity in their travel p attern, th e most likely destination of this college student is one of the local colleges and his/h er speed will be a bus speed. Moreover, the model deliberately avoids complex geometries; destinations are kept simply as locations. This abstraction keeps the DGM models simple and th a t will help the researchers to focus on developing and im plementing the functions 5s) and 5s systematically and gradually to capture more sophisticated mobility models, including group mobility and mobility of vehicular ad hoc networks. In th e next two sections, we present some representative real-world scenarios. We model some of these scenarios using th e DGM framework and illustrate how those scenarios are modelled by ju st controlling th e num ber of destinations and the destination selection function 5 d - 5.2 R epresentative M A N E T Scenarios To provide some real-world representative scenarios for MANETs, we look from three different perspectives: land, water, and air. We illustrate some interesting MANET scenarios under these topics next. 5.2.1 M A N E T S cen a rio s o n L an d On land surface, there are many possible M ANET scenarios. For example, hu­ man/vehicle movement in a city, student movement in a campus, p articip an t move­ ment in a conference, pedestrian mobility in different stations, user movement in 55 a beach or any big recreation place, rescue worker mobility in disaster areas, sol­ dier movement in a battle-field, and hum an/vehicle movement w ithin and between cities are interesting M ANET scenarios. Some of these representative scenarios are described below. • C ity scen ario s: A city generally has a set of popular places such as stores, shopping malls, institutions, parks or recreational places, and so on. People or vehicles in a city most frequently visit these popular places w ith th e preference to the nearest places and less frequently some unpopular or far distan t places. • C a m p u s scen ario s: A university cam pus has a set of class room s/labs, li­ braries, cafeteria(s), coffee-shop(s), sport centre(s), parking lot(s), and a few gathering places. Students, faculty and staff usually move among these men­ tioned places and spend their tim e based on th e purpose of visit. For example, a student attending a class normally stays in the class 50 to 80 m inutes b u t the same student usually spends 25 - 30 m inutes in Cafeteria. T he observation is th a t the mobility of the students in campus are normally guided m ostly by those aforementioned destinations as well as by th e time and type of th e destinations. • P e d e s tr ia n m o b ility in s ta tio n s : T he scenarios such as train stations, pas­ senger ports or big bus stations have various types of mobile users. These scenarios are not occupied only by the restricted types of users like students in campus environment, participants in conference, and so on. In stations or passenger ports or big bus stations, passengers /pedestrians usually visit ticket counter(s), food court(s), arrival area(s), departure area(s), washroom(s), w ait­ ing room(s), and so on. Though the pedestrians have different speed based on the type of pedestrians, their mobility is generally influenced by th e mentioned places. 56 B e a c h o r a n y r e c r e a tio n a l p la c e sc e n a rio s: A t a beach, th ere are some common places such as volleyball court(s), washroom(s), snack bar(s), and some predefined p ath through the landscape. Beach users such as sun-bather(s), walker(s), jogger(s), biker(s), and volleyball-player(s) are unevenly d istributed over the landscape. Some of the beach users may be stationary while others may move with different characteristics an d /o r speeds. However, th e actions th a t beach users take are not always random. R ather, some of th eir movements tend to be toward certain previously mentioned common places and others move in a predefined p ath through the landscape [77]. In te r - c ity sc e n a rio s: Almost all cities have some popular locations th a t have already been mentioned in city scenarios. A person or a vehicle generally moves among these popular places w ithin the city and rarely moves random ly in differ­ ent locations. The same person or vehicle may travel from one city to another city, move within the destination city with a preferred set of destinations in mind, come back to the previous city and th e process may be repeated. The observation regarding the mobility of the nodes (e.g., vehicles or peoples) in these scenarios is th a t their mobility is controlled by th e different com mon places within the city th a t they most frequently visit and less frequently between cities. D is a s te r a r e a sc e n a rio s: In the disaster area scenarios, the whole infrastruc­ ture for mobile communication may be partially or completely destroyed. In disaster areas, there may be injured people, animals, and so on who need help. To help them, civil protection services work as different groups such as medi­ cal teams, fire brigades, rescue team s, and so on. These groups in th e disaster area scenario do not move randomly. They walk tow ard some specified regions in the disaster area and work under the leadership of different group leaders. The authors in [78] studied the two different real-life disasters th a t happened in Germany, and divided the disaster area and its surrounding into five different zones: the technical operation command, th e incident site, the casualties treat­ m ent area, the transport zone, and th e hospital zone. Here, the m obility of the nodes such as medical team s, fire brigades, rescue team s is guided mostly by the regions and the group leader. • B a ttle -fie ld sc e n a rio s: Like th e disaster area scenario, a battle-field scenario is a set of strategic locations where soldiers move as different groups. Instead of moving random ly from location to location in th e entire b attle field area, the soldiers move from one strategic location to another strategic location as a group. The mobility of the nodes (e.g., soldiers, vehicles, tanks) in these types of scenarios is also guided by the different strategic locations (destinations) as well as by the group leader. 5 .2 .2 M A N E T S cen a rio s o n /u n d e r W a ter Under water, some scenarios are single fish movement, th e movement of schools of fish, pursuing one fish by the other, and so on. On the surface of th e w ater, ship movements from port to port, and even b o at movements between locations defined by different latitudes and longitudes are possible scenarios. Two representative scenarios are given below. • F is h m o v e m e n t sc e n a rio s: Fish movement scenario is one of th e under w ater scenarios. Fish generally swim in w ater randomly. They move or swim individ­ ually or as a group. Even the movement of fish sometimes is influenced by the places where foods sources are dense. • S h ip m o v e m e n t sc e n a rio s: Ship movement scenarios are heavily influenced by their infrastructure/destinations (e.g., ports ). Ships travel from one selected 58 port to another selected port. 5 .2 .3 M A N E T S cen a rios in A ir An aircraft scenario (single or group in m ilitary scenario) is one exam ple in this category. Two aircraft scenarios are explained below. • S in g le A ir c r a f t sc e n a rio s: Aircraft are heavily influenced by their destina­ tions (e.g., airports). Single aircraft travel from one military airstrip to another military airstrip or to some predefined destinations; they generally never fly randomly from location to location. Here, the mobility of th e nodes such as aircraft is primarily controlled by their airports (destinations). • G ro u p a ir c r a f t sc e n a rio s: In b attle field, a group of aircraft flies together to achieve their strategic objectives. Even in such scenarios, their movements are controlled by different strategic locations in th e air defined by th e latitu d e and longitude as well as the land positions. From a mobile nodes perspective, th e nodes either move independently or as a group. Their mobility is typically influenced by their destinations. B oth of these points can be closely modelled by suitably controlling the destinations in DGM m od­ els. 5.3 V ersatility of th e D G M M odels To model the scenarios and subsequently study the DGM models, we chose four DGM models th a t have the potential to represent several of the above described scenarios. 59 5 .3 .1 R e p r e se n ta tiv e D G M M o d e ls • R W P m o d e l *: This model considers all the points in the sim ulation region as destinations. T he transition probabilities for choosing the next destination, speed, and pause time from their respective given ranges are derived from a uniform distribution. This model can capture the fish movement (individual movement) scenario or th e movements of birds flying in the air aimlessly. • R D G M (R a n d o m D e s tin a tio n G u id e d M o b ility ) m o d el: T his model considers a finite set of uniformly distributed points in the simulation region as destinations. The transition probabilities for choosing next destination, speed, and pause-time are generally uniform. By suitably controlling th e num ber of destinations, and th e transition probability to choose destinations, we can model the mobility of people/vehicles in a city, in different stations and in beach sce­ narios. • R C D G M ( R a n d o m C lu s te r e d D e s tin a tio n G u id e d M o b ility ) m o d e l: This model considers a finite set of points in the simulation region as destina­ tions but these destinations have to be organized into different clusters. Each cluster has its own session tim e which dictates how long a mobile node will stay inside th a t cluster once th e node enters th a t cluster. The transition probabil­ ities for choosing th e next cluster and the next destination can be uniform or user-defined. By suitably controlling th e number of clusters, the num ber of des­ tinations within cluster, and th e transition probabilities for choosing th e next cluster and the next destination, we can model scenarios such as cam pus, beach, inter-city, etc. :RWP modes is an extreme case of DGM models where all the points in the mobility region are considered as destinations. Therefore, we use RWP model as the base model to compare other proper DGM models. 60 • R D G R P G M (R a n d o m D e s tin a tio n G u id e d R e fe re n c e P o in t G r o u p M o b ility ) m o d e l: This model considers a finite set of uniformly distributed points in the simulation region as destinations. The transition probabilities for choosing next destinations, speed, and pause time are also uniform. The nodes are divided into different groups; one node from each group is designated as a leader node and the remaining nodes are kept as th e member nodes. Only leader nodes choose the next destination based on th e transition probabilities but the member nodes follow their respective leader’s mobility. This model can capture battle field scenarios, group aircraft scenarios, and. a t least partially, disaster area scenarios. The power of the DGM framework is th a t it can model various scenarios ju st by tuning its param eters suitably. We don’t require an separate im plem entation for each scenario. To illustrate, next we model some of th e real-world scenarios m entioned in the previous section ju st by controlling the destination and the destination selection functions of the DGM framework. As a case study, we have considered th e following scenarios: 5 .3.2 S cen ario M o d e llin g • F is h m o v e m e n t s c e n a rio s: In these scenarios, th e nodes are fish and all the points in the swimming space are th e destinations. So th e RWP mobility model can capture this scenario (single fish movement). If we consider all points in the simulation area as destinations, we can model the mobility of a group of fish movement using a RDGRPGM model. The trace generated by two DGM models (RWP model and its variant) using DGMGen for capturing th e movement of a fish or a group of fish moving together 61 (a) Fish Movement Trace (single) (b) Fish Movement Trace (group) Figure 5.1: Modelling Fish Movement shown in Fig. 5.1. Fig. 5.1(a) shows the trace of a single fish movement and Fig. 5.1(b) shows the trace of a group of fish movement. Here, we set all th e points in simulation region as destinations, the speed range as 0 - 10 m eters/second, and the pause tim e as 0 - 5 seconds. • S h ip o r a irc r a f t sc e n a rio s: These scenarios can closely be captured by the RDGM model. In these scenarios, the nodes are ships or aircraft. To model these scenarios, each port or airport or landing station is assumed as a destination, the boarding time as the pause tim e and the travelling speed as the speed. Therefore, a user, based on th e num ber of ports, can define th e num ber of destinations as well as set ex tra priority to a destination which will represent a busy port. The trace of a ship or an aircraft modelled by the RDGM model is shown in Fig. 5.2. Here, we set the number of destinations as 25, speed range as 100 to 150 meters/second, and pause tim e as 1800 to 3600 seconds to model this scenario. • C ity scen ario s: In city scenarios, the nodes are th e people or vehicles. All the common places such as shopping mall(s), different institutions, park(s), or recreational place (s) are preferred destinations and th e places are ordinary 62 Figure 5.2: Ship or Aircraft Movement Trace destinations. The RDGM model can closely capture these scenarios. (a) Single Node Trace (b) Traces of All Nodes Figure 5.3: Human or Vehicles’ Movement Trace in a C ity A sample trace for th e city scenario modelled by th e RDGM model is shown in Fig. 5.3 where few destinations have been assigned higher priority to be chosen by the mobile nodes. Fig. 5.3(a) shows the trace of a single node and Fig. 5.3(b) shows the trace of all the nodes in the simulation. Here, we set the num ber of destinations as 100 (3 destinations as higher priority destinations), th e speed range as 0 - 5 m eters/second, and the pause time as 600 - 900 seconds. • C a m p u s sc e n a rio s: In these scenarios, th e nodes are the stu d en ts and the common places such as classes, labs, sport centre(s), coffee-shop(s) and cafete63 Figure 5.4: Students’ Movement Traces in a Campus ria(s) are considered as clustered destinations. These scenarios can closely be captured by the RCDGM model. A sample trace of a university campus modelled by the RCDGM model is shown in Fig. 5.4. Here, the session tim e of each cluster is randomly chosen from 5 minutes to 60 minutes, th e speed range as 0 to 2 m eters/second, and th e pause tim e varies based on the cluster. Similarly, one can model inter-city scenarios using the RCDGM model. • B a ttle -fie ld sc e n a rio s: In battle-field scenarios, the nodes are th e soldiers and tanks (even helicopters). All th e strategic locations are the destinations. These scenarios can be captured by the RD GRPG M model. A sample trace of group of soldiers’ mobility in a battle-filed modelled by the RDGRPGM model is shown in Fig. 5.5. Here, we set th e number of destinations as 50, th e speed range as 5 - 10 m eters/second, the pause tim e range 0 to 5 seconds, and the group size as 5 nodes. 64 Figure 5.5: One Group Movement Trace in Battle-field Scenarios Similarly, we can model various real world scenarios including th e rem aining sce­ narios mentioned in-the previous section by the DGM framework. W h at the user needs is to set the right param eter after getting th e intuition about th e scenarios to be modelled. W ith this understanding of the representative DGM models, we next analyse them for connectivity metrics. This, in a way, is a com parative study of three proper DGM models with its extreme case, RWP model - a widely used model in M AN ET simulation so far. 5.4 C onnectivity A n alysis o f th e D G M M odels The simulation study of connectivity analysis is conducted using a system w ith the following configuration: • Operating System : U buntu 10.11 • Processor (CPU) : Intel(R) Core(TM)i7-2600 CPU 3.40GHz 65 • Installed Memory (RAM) : 12.0 GB • Mobility Generator and Analysis Tool : DGMGen • Network Simulator : NS2 5.4.1 S im u la tio n S e tu p In this study, we are interested in analysing th e connectivity m etrics on four mo­ bility models: RWP, RDGM, RCDGM, and RDGRPGM models. T he common simu­ lation param eters such as the simulation area, the number of nodes, th e transm ission range, the speed range, th e pause time, and the simulation time, and th eir values are summarized in Table 5.1. V a lu e (s) 50 2000m x 2000m 40-100 P a r a m e te r s Nodes Simulation area Transmission range Speed range Pause time range Simulation time 0 m /s - 25 m /s 0s - 2s 1 hour Table 5.1: Simulation Param eters for Mobility Modelling For all four models, th e pause tim e is chosen within th e given range using uniform distribution. For the RWP model, th e next destination w ithin the sim ulation region is selected using a uniform distribution. T he speed of the node is also chosen within the given range using a uniform distribution. For the RDGM model, one hundred destinations are chosen within th e sim ulation region using a uniform distribution. Each node chooses one of th e rem aining 99 destinations as its next destination to move and its travelling speed w ithin th e given range using a uniform distribution. 66 For the RCDGM model, four clusters w ithin the area of 150m x l5 0 m in the four corners of the simulation regions are chosen. Each cluster has 25 nodes chosen uniformly within their region. Each node has a home cluster where it is initiated. A node after entering a cluster moves within th a t cluster for a duration (referred to as a session) chosen uniformly randomly w ithin th e range of 0 to 6 m inutes (one ten th of the simulation time). After a session expires, a node stays in th e sam e cluster for another session with probability 0.2, may choose to move to another cluster with probability 0.3, or return to its home cluster with probability 0.5. For the RDGRPGM model, th e nodes move as a group where one acts as a group leader and the others act as members of the group. All nodes are organized into different groups. One hundred destinations are chosen w ithin the sim ulation region using a uniform distribution. T he group leader node chooses one of th e rem aining 99 destinations as its next destination to move to and chooses its travelling speed w ithin the given range using a uniform distributions. T he member nodes place themselves randomly around their group leader’s current position and move with th e sam e speed as their leader. 5 .4 .2 S im u la tio n E x p e r im e n ts The objective of our experiment is to study the connectivity in RDGM , RCDGM, and RDGRPGM models, in comparison w ith th a t of the RW P model. Connectivity is a complex m etric and has several dimensions. We have conducted two sets each of 3 experiments, mainly observing the connection changes, number of contacts, and contact duration by varying the transm ission range and th e speed of th e nodes. E x p e r im e n t 1 In this experiment, we computed the average number o f connection changes, the average number o f contacts, and the average contact duration fo r fo u r 67 mobility models, RW P, RDGM, RCDGM, and RD G RPG M , by varying the transm is­ sion range as 40m, 60m, 80m, and 100m. The result is shown in Fig. 5.6. Contacts Vs Transmission Ranges Contact Duration Vs ^Transmission Ranges ^Collection Changes Vs ^Transmission Ranges <£, 800 iS 12.5 !P600 13 500 S 400 4) 200 40 50 50 70 80 90 40 100 < Transmission range ♦ R D G M m o d el 4 r RCDGM m odel ♦ R D G R P G M m odel ♦ R W P m odel (a) Number of Contacts ♦ 50 60 70 80 90 100 Transmission range 40 50 60 70 80 RDGM rrodei s i r RCDGM mode! ♦ R D G M model ♦ R C D G M m o d el RDGRPGM model ♦ R W P model ♦ R D G R P G M m o d el ♦ R W P m o d e l (b) Connection Changes 90 100 Transmission range (c) Contact Duration Figure 5.6: Variation of Contacts, Connection Changes, and Contact D uration vs. Transmission Range. As the nodes in the RWP wander around randomly w ithin the sim ulation area, a node meets another node rarely. Therefore, the average num ber of contacts is low for the RWP model, as shown in Fig. 5.6(a). Since the nodes rarely establish contacts w ith other nodes, the average number of connection changes is also low as shown in Fig. 5.6(b). Though the number of contacts and th e connection change increases as the increment in transmission range, th e trend is very low. T he contact d uration in all cases for the RWP model is also low as compared to the other models. As this model is very random, it provides the least num ber of contacts and the contact duration. As a result, any performance study of routing protocol on the RWP model will be biased by the random property of this model which may not be tru e in many real scenarios. On the other hand in the RDGM, as mobile nodes choose destination from a fixed set of locations, more nodes will choose the common location. W hen they move toward the selected destination, they will have higher chance to have contact w ith 68 one another. As a result, the average num ber of connection changes and the number of contacts are higher than th a t of th e RWP model. The almost increases linearly as the transmission range increases. However, in the RCDGM, the average number of connection changes and contacts increases very sharply as the nodes’ transm ission range increases. This is because destinations are placed in compact way w ithin a smaller region. Therefore, the nodes have a higher chance to meet. However, after certain ranges, the trend is flat and even goes down. This is because th e connected nodes remain connected for long tim e for their high transmission range. T he contact duration has th e opposite effect as shown in Fig. 5.6(c). In the RD G R PG M model, the contact duration increases as the increment of the transmission range upto 60 meters b u t the duration decreases after th a t level. This is because th e likelihood of one group of nodes meeting with another group of nodes for higher transm ission range is high b u t contact tim e is low as they are different groups; however these contacts have greater im pact on th e average contact time. E x p e rim e n t 2 In this experiment, we computed the average number o f connection changes, the average number o f contacts, and the average contact duration fo r four mobility models, RWP, RDGM, RCDGM, and R D G R P G M models, by varying the speed as 5 m /s, 10 m /s, 15 m /s, 20 m /s, and 25 m /s while keeping the number o f nodes fixed at 50 and keeping other parameters constant. For the RD G RPG M , 50 nodes are divided into 10 groups; each group consists o f 5 nodes. The result is shown in Fig. 5.7. Again, as explained with E xperim ent 3, the performance under th e RW P model is not properly pronounced as com pared to th e DGM models and therefore, th e RW P model may not be a suitable model to study protocols useful for practical MANETs. 69 Number of Contacts Vs Speed Conection Changes Vs Speed Contact duration Vs Speed 1000 ® M C o c 0> (9 < D 1 £ 5 10 15 S 25 Maximum speed (m /s) ▼•RDGM m o d e l RCDGM m odel ♦R D G R P G M m o d el ♦ R W P m odel (a) Number of Contacts 10 15 2D 25 Maximum speed (m /s ) ♦ RDGM m o d el A ♦ RDGRPGM m o d e l -# -R W P m odal RCDGM m odel (b) Connection Changes 5 10 15 20 25 Maximum speed (m /s ) ♦ R D G M model ^ rR C D G M m o d e l RDGRPGM m o d el ♦ R W P m o d e l (c) Contact Duration Figure 5.7: Variation of Contacts, Connection Changes, C ontact D uration vs. Speed. W hen the same study is repeated on th e RDGM and th e RCDGM models, the performance on the average number of contacts, connection changes, and contact duration are high. Furthermore, their variations w ith respect to change in th e speed are sensitive, as they increase (or decrease) almost linearly, as shown in Fig. 5.7(a c). The almost linear trend in performance is clear th a t th e slower nodes can have fewer contacts overall, b u t each contact can last longer. T h e reason for th e b etter performance of the RCDGM over RDGM model is intuitive in that in th e RCDGM model the nodes have higher probability of staying longer tim e within the sam e cluster (smaller region), and hence have a higher chance of being connected longer. For an experimental result to be useful and relevant, the performance results m ust be significant and sensitive to the changes of the critical param eters of M ANETs such as nodes’ speed and their transm ission range. From these experiments, we observe th a t all the models are sensitive to th e changes of nodes’ transmission range and speed. We observed th a t DGM models always perform b etter. Therefore, we believe th a t the performance study of protocols m ust be conducted based on more realistic mobility models such as DGM models for the results to be more credible and useful. E x p e r im e n t 3 In this experiment, we computed the clustering coefficient o f the ad hoc networks generated by the studied mobility models while keeping the speed range at 5 -10 m /s, the number of nodes as 50, the transmission range as 50 meters, and all o f the other parameters at the default shown in Table 5.1. The result fo r a selected duration (0 to 1000 second) is shown in Fig. 5.8. Network Clustering Coefficient Times (sec) |<— RDGM model «*P.O)GM m ods! «e»RDGRPGM m odel RWP m odel | Figure 5.8: Clustering Coefficient of the Networks Generated by the Studied Models. As the nodes wander around in th e RWP model, the clustering coefficient of the ad-hoc network generated by the RW P model shows a very poor connection in the entire simulation time shown in Fig. 5.8. In contrast to th e RWP model, th e RDGM model represents a network th a t is b etter connected th an th a t of the RW P model. The prim ary reason behind this is th a t th e nodes move among th e selected destinations only; they do not wander around random ly w ithin the entire simulation area. The network generated by the RCDGM model is far more connected than even th a t of the RDGM model. This is because the nodes move m ost of th e time w ithin th e cluster 71 where the destinations are arranged very com pactly w ithin the different clusters and travel between the clusters less frequently. The other DGM model, th e RD G R PG M model, which shows th a t the network is almost fully connected as th e nodes move as a group from destination to destination. W hen th e nodes move as a group, th e nodes of one group maintain connection w ithin the group most of th e time. From th e graph shown in 5.8, we can easily infer th a t DGM models provide better connectivity th an th a t of RWP model. This, we believe, is the likely case for many real life MANETs. E x p e r im e n t 4 In this experiment, we computed the node degree distribution at a particular tim e instant o f the networks generated by the RDGM, the RCDGM , and the RW P models in the configuration where the number of nodes is 50, the speed range 5 -1 0 meters/second, the transmission range is 50 meters, and all other parameters remain the same as shown in Table 5.1. The result is shown in Fig. 5.9. sec 0 40 ••RDGMmodel♦RCDGMmode!*=»rwpnwfel Figure 5.9: Degree D istribution of the Networks G enerated by Three Studied Models. 72 The graph shown in Fig. 5.9 presents w hat percentages of the nodes have con­ nected neighbours and how many neighbours are there for a particular node in the network. A t a particular time, say a t 700th second, alm ost 85% of nodes are isolated and even though the remaining 15% have connected neighbours, b u t they have only one neighbour in RWP model. In contrast to th e RWP model, 69% of nodes are isolated and th e remaining 31% have connection to other nodes. Of them , 19% have one neighbour, 9% have two connected neighbours and 3% even have three neigh­ bours. In the RCDGM model, 39% of nodes are isolated a t the observed tim e while the remaining 61% have 1 to 4 neighbours. Of th e connected nodes, 37% have one neighbour, 15% have two neighbours, 6% have three neighbours and th e rem aining 3% have even four neighbours. B oth the RDGM and the RCDGM models have the trends th a t reflect the power law distribution in term s of node degree distribution. This is because the nodes visit within the destinations arranged in different com pact area for th e RCDGM model and move only among th e selected destinations. So, the nodes have higher chances to meet one another in the RDGM model and a far b etter chance to meet one another in th e RCDGM model than th a t of th e RW P model. This graph clearly shows th a t if the nodes move following the DGM models, then they will have higher chance to meet other peers. This happens in m ost of the real world scenarios. E x p e r im e n t 5 In this experiment, we computed the number of different hop length paths seen during the entire simulation in the networks generated by the RDGM , the RCDGM, and the R W P models in the configuration where the number o f nodes is 100, the speed range 5 - 1 0 meters/second, the transmission range is 50 meters, and all o f the other parameters remain the same as shown in Table 5.1. The result is shown in Fig. 5.10. 73 Number of distinct connected node pairs 100000 ->--------------------------------------------------------------------------------------------------------------------------------------------------------------------- 10000 RWP RDGM RCDGM Mobility Model ■ P ath ten g th -l ■ Path length-2 ■ P athlength-4 S Pathlength-5 3 Path Length-3 Figure 5.10: Number of Different Hop Length P aths During the Simulations This Fig. 5.10 shows how many distinct length paths exist under different m obility models. The RCDGM model has 1-hop to 5-hop length paths, the RDGM has 1-hop to 3-hop length paths and the RW P has 1-hop to 2-hop length paths. Again, as the nodes wander around in the RWP model, one node meets another node rarely and if they meet, they are connected mostly by link and less frequently by 2-hop length paths. By contrast, the RDGM model has some 3-hop length paths. This is because the RDGM model uses a limited num ber of destinations; therefore, a set of nodes can build a larger length when entering/leaving into/from any common destination. The reason for having higher length paths in th e RCDGM model is th a t th e nodes are visiting the destinations th a t are arranged in a cluster. T he presence of th e long paths reflects th a t the respective model conforms b etter connectivity and captures clustering nature as well as series nature (e.g., a set of vehicles follows th e sam e road) seen in real world scenarios. 74 5.5 M odelling and A nalysis a Scenario B ased on R eal Trace So far, we have seen how to model mobility of known scenarios using DGM models. Suppose we have a real trace of a mobility model collected from a scenario which is not explicitly known. The question is: can we model th a t scenario using DGM models? This section is an attem p t to answer this question. We take a real trace collected from the Haggel project a t Cambridge [46] and derive intuition to determine th e num ber of destinations, the number of nodes, th e pause time, the speed, and th e transition probabilities to choose th e next destination. A snapshot of th e real trace is shown in Fig. 5.11. ID1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ID2 BeginContactTime EndContactTime iThContactTime, 121 121 1 8 236 347 1 3 347 1 4 236 121 464 1 5 8 585 585 2 589 10 589 1 700 816 2 5 940 2 589 3 4 589 940 2 940 940 1 9 1306 1306 1 2 11 121 1430 1 1430 1430 1 12 1662 1662 3 8 1782 1 121 13 2025 2158 4 8 2275 2387 2 13 InterContactTime 0 0 0 0 464 0 236 242 242 0 0 0 0 1077 0 363 493 Figure 5.11: A Snapshot of Real Trace T h a t Contains C ontact Information Recorded by iMote Devices In Fig. 5.11, th e first and second columns represent the devices’ IDs. F irst column 75 gives ID of the devices which record th e seen device ID represented in th e second column. The third and fourth columns show th e s ta rt tim e and th e end tim e ID l meets ID2. The fifth column enumerates the number of contacts happened between ID l and ID2. The last column shows th e tim e difference between th e end of previous contact and the beginning of the current contact of ID l and ID2. This real trace is about a group of users carrying small devices for six days in th e Intel Research Cambridge Corporate Laboratory. The users are research students. T he intuition behind this trace is th a t the probability of the users to stay a long tim e a t th e lab is high, the number of travelling places m ight be limited, they may visit a num ber of place in the university (th at could be representative in cluster), and so on. Based on this intuition th a t we get from the given real trace, we have considered the following simulation param eters for modelling this scenario using DGM models. P a r a m e te r s Nodes Number of destinations Cluster size Destinations in a cluster Cluster session time Simulation area Transmission range Speed range Pause tim e range Simulation time V a lu e (s) 9 15 100m x 100m 3 0 - 8 hours 2000m x 2000m 50 0 m /s - 5 m /s 0s - 1800s 3 days (259200s) Table 5.2: Simulation Param eters for Modelling Scenario Derived from Real Trace Using the above simulation configuration, we have conducted th e following two experiments. E x p e r im e n t 6 In this experiment, we computed and compared the inter-contact tim e distribution o f the generated synthetic traces with that o f the real trace collected from the Haggel project at Cambridge [f6]. The result is shown in Fig. 5.12. 76 Inter-Contact Time Distribution 20.5 5 0,4 U L 0.3 100 1000 200 100000 Timet — RDGM model — RCDGM model — RWP model Real Trace Figure 5.12: Inter-contact Tim e D istribution The graph shown in Fig. 5.12 presents the inter-contact time distribution of the node pairs in the networks generated by the chosen DGM models and th e real trace. In this test, as compared to the RWP model, the RDGM, and the RCDGM models show th e closer proximity to th a t of the real trace. The trend of the inter-contact time distribution follows the power law distribution which is one of the im portant properties of many real world networks such as collaboration networks, Internet, W W W , proteinprotein interaction network, social networks, and so on. The possible reason for showing the close proximity in the RDGM and th e RCDGM models are th e num ber of limited contact locations, the cluster size and its session time, and the transition probability. The trend is even closer in case of the RCDGM model. This is because the destinations are organized as cluster consisting of only a few destinations and the nodes frequently visit within a cluster, which is also true in the activity of research students. 77 Though it is difficult to model a scenario accurately based on intuition alone, our observation is th a t th e DGM models can be the good choice as it has a set of param eters such as destinations, transitions probabilities to choose destination, and cluster size th a t can be tuned to fit th e real world scenario to be studied. A lthough the inter-contact tim e is totally random for this experiment for all models, th is can be tuned to represent the real-world scenario in the DGM models by properly choosing the destination as well as by incorporating the activity properties of th e nodes. E x p e r im e n t 7 In this experiment, we computed and compared the contact tim e dis­ tribution of our generated synthetic traces with that of the real trace collected from the Haggel project at Cambridge {46j. The comparative result is shown in Fig. 5.13. Contact Time Distribution E 0,6 *3 1u 0.5 2 0,4 a 0.2 20 30 100 200 1000 10000 T im et 'RWP model 'RDGM model — RCDGM Real Trace Figure 5.13: C ontact Time D istribution In Fig. 5.13, the trends of the contact time distribution of the studied traces clearly depict th a t the RDGM and the RCDGM models show similar tren d as to the 78 real trace. This is because the number of destinations are very limited ( which m ight be also true in the real trace as research students rarely visit a large num ber of places). The trend is even very close in case of th e RCDGM model. The reason behind this is th a t the destinations are organized into clusters consisting of only few destinations. The nodes move w ithin the cluster frequently which is also true in th e stu d en ts’ life. They may stay in lab, go to take class and spend time in cafeteria. D uring these times, they may remain connected. Similarly, th e size of th e clusters influences the contact time distribution. From this observation, we believe th a t we can model a scenario based on real trace more accurately by tuning param eters like the num ber of destinations, th e transition probability, the speed range, th e pause time, th e cluster size, and th e session tim e of cluster. Though modelling a scenario based on real trace is a complex task, it is possible through trial and error process if we have a sufficient insight of th e real trace. In this perspective, DGM models provide the b etter tuning mechanisms to model a real world scenario. 5.6 Perform ance S tu dy on M A N E T R outing P ro to ­ col In this section, we present th e performance study on a MANET routing protocol, AODV, under DGM models in comparison with th e RWP model. The performance is measured based on the protocol performance metrics mentioned in C hapter 3. Here we describe w hat was the simulation setup we followed, and then illustrate the experiments we did. Throughout the experiments, the behaviour of AODV is b etter pronounced in DGM models th a n th a t of the RWP mobility model. 79 5 .6.1 S im u la tio n S e tu p In this study, we are interested in analyzing th e performance of AODV based on the four mobility models. We use NS2 to conduct our simulation of routing. The common simulation param eters such as th e num ber of nodes, the speed range, the simulation region, the d a ta sources, the transm ission range, the simulation time, and their values are summarized in Table 5.3. P a r a m e te r s N a m e Number of nodes Node speed range Simulation region D ata sources Transmission range Routing protocol Simulation time V a lu e (s) 40 - 80 5 - 1 0 m/ s 2000m x 2000m 30 - 50 CBR sources(4 pkt/sec, Packet size 512) 250m AODV 700 sec + 400 sec warmup Table 5.3: NS2 Simulation Param eters Mobility traces of the RWP, th e RDGM, the RCDGM and the R D GRPG M models were generated using the DGMGen software tool. For all four models, th e traces are generated by varying the number of nodes as 40, 50, 60, 70, and 80, and th e speed range as 5 to 10 m /s. We used CMU generator embedded in NS2 to generate CBR traffics as data. 5 .6 .2 S im u la tio n E x p e r im e n ts We have conducted two sets each of 3 simulation experiments, prim arily observing the d ata delivery ratio, the d ata loss, and th e end-to-end delay, by varying th e number of nodes and the number of d ata generating sources. E x p e r im e n t 8 In this experiment, we computed the data delivery ratio, the data loss, 80 and the average end-to-end delay of A O D V for fo u r models RWP, RDGM , RC D G M and RD G RPG M by varying the number of nodes as 40, 50, 60, 70, and 80, while keeping the number of data generating sources constant as 35 at each cases. The result is shown in Fig. 5 .14- Data delivery ratio Vs Number of nodes Data loss Vs N um ber of nodes End-to-end Delay Vs Number of Nodes ?£ . 670 0 ffi 50 O « 40 3 30 40 45 50 55 60 65 70 75 80 40 45 50 55 60 65 70 75 80 N um ber o f n odes N um ber o f n o d e s ‘■RDGM m o d e l ■SirRCDGM m o d el ‘•RDGM m o d e l sfe-RCDGM m o d el ►RDGRPGM m o d e l ■•■RWP m o d el ►RDGRPGM m o d e l -# -R W P m o d e l (a) Data Delivery Ratio (b) Data Losses 50 60 70 80 N um ber o f n o d e s ■^‘•RDGM m odel sfc-RCDGM m o d e l RDGRPGM m o d el ■ •■ R W P m o d e l (c) Average End-to-End Delay Figure 5.14: Im pact of Mobility Models on the Performance of AODV vs. N um ber of Nodes As noted in the previous section, th e poor connectivity in RWP model causes the d ata delivery ratio to be very low as shown in Fig. 5.14. The delivery gets b etter only when the region is highly populated with mobile nodes. Even then th e decrease of data loss is very slow. The end-to-end delay is com puted only for those delivered data. The true performance m ust include all the data, in which case th e RW P model performs very poorly. Also, it is hard to explain the behaviour considering th a t the nodes move randomly. In RDGM and RCDGM models, th e d ata delivery ratios are higher while the d ata loss is lower than the RWP model , b u t their trends are linearly increasing and decreasing respectively, as shown in Fig. 5.14(a & b). The increasing tren d of the d ata delivery ratio in the RDGM and the RWP models is higher th a n th a t of the 81 RCDGM model. This is because the nodes in the RDGM move uniformly w ithin the larger region, whereas the nodes in the RCDGM stay w ithin the cluster of smaller regions longer than it moves between clusters. So, if a node moves w ith d a ta to a new cluster, then it will have a lower chance of delivering the d a ta to a location outside of th a t cluster during its session. The end-to-end delay and delivery ratio in the RDGM increase as the num ber of nodes increases. This seems to suggest th a t more nodes facilitate more delivery and the increased portion is more likely th e delayed deliveries. However, it is interesting to note th a t the end-to-end delay increases in th e RCDGM model too, even though d ata delivery in the RCDGM increases very slowly as th e number of nodes increases. This is because, although the number of sources is fixed, the num ber of possible receivers increases as the number of nodes increases. In addition, each receiver is confined within a cluster longer duration than it travels between clusters. In this experim ent, AODV shows very high d a ta delivery and very low d ata loss in the R D G RPG M model. This is because a set of nodes are almost always connected which greatly im pacts on the overall the d a ta delivery ratio, th e d ata loss and the end-to-end factors. E x p e r im e n t 9 In this experiment, we computed the data delivery ratio, the data loss, and the average end-to-end delay o f A O D V fo r fo u r models, RWP, RD G M , RC D G M and RDGRPGM , by varying the number o f data generating sources as 20, 30, f.0, and 50, while keeping the total number o f nodes constant as 70 at each cases. The result is shown in Fig. 5.15. Again, Fig. 5.15(a) shows th a t the d ata delivery ratio in RWP model is very low, and therefore makes the same im pact th a t we already discussed. These experim ents illustrate th a t increasing th e num ber of source nodes decrease the d ata delivery ratio, and increase the d a ta loss and the end-to-end delay. This is because, more data, 82 Data delivery ratio Vs Number of Data Sources Data loss Vs Number of Data Sources End-to-end Delay Vs Ifumber of Data Sources £60 2 50 <0 L_ £ V -vi 30 *3 2 0 20 25 30 35 40 45 50 N um ber o f D ata Sources 20 25 30 35 40 45 N um ber o f D ata S ources 50 20 25 30 35 40 ♦ R D G M m o d e l ♦ R C D G M m cctel IR D C M m o d e l d r RCDGM m o d el t RDGM m odel ^ p R C D G M m o d e l ♦ R D G R P G M m o d e l ■•►r w p m o d e l -RDGRPGM m o d e l ♦ R W P m o d e l -RDGRPGM m o d e l ♦ R W P m o d e l (a) Data Delivery Ratio (b) Data Losses 45 50 Num ber o f D ata S ources (c) Average End-to-End Delay Figure 5.15: Im pact of Mobility Models on th e Performance of AODV vs. G enerating Sources D ata more loss, and more delayed delivery result in an increased average end-to-end delay increased. Overall, the performance of routing protocols using DGM models is more pronounced and has consistent explanation based upon the topology of th e network. 5.7 Sum mary In this chapter, first, we presented a set of real world representative scenarios and how different scenarios can closely be captured by the basic DGM models (RWP, RDGM, RCDGM and RDGRPGM models). Second, we explained the experim ents conducted for analysing the performance metrics such as th e average num ber of con­ nection change, the average number of contacts and the average contact duration by varying the transmission range and the speed. In addition, we showed th e tren d of the node degree distribution,the clustering coefficient and th e distinct k — hop paths exhibited in the mobility traces generated by the DGM models. The trends of the node degree distribution and the /c-hop paths of the DGM models’ traces follow the power law distribution in some extent. T he metrics such as the average num ber of 83 connection changes, the average num ber of contacts, the average contact duration, and the clustering coefficients in th e conducted experim ents indicate th a t th e DGM models better capture the connectivity p attern s prevalent in real-world scenarios than th a t of the RWP model. Third, the experiments conducted incorporating real trace exhibited another strength of the DGM models. Though those two experim ents are based on the intuition we obtained from th e real trace, th e close proxim ity trends of metrics such as the inter-contact tim e distribution and the contact tim e distribution explored the possibility th a t th e larger social scenarios can be captured by th e DGM models. Finally, we presented two sets of experiments for evaluating th e perform ance of the AODV routing protocol using the DGM models. As per our expectation, the experiments showed th a t AODV performs b etter under the proper DGM models th an under the RWP model. 84 Chapter 6 Conclusion and Future Directions Mobile ad-hoc networks have received a great deal of interest in recent times, due to their potential applications and their technological advancements. T he topology of MANETs is highly dynamic as th e nodes are expected to move unpredictably. Due to their complexity, most research studies in MANETs are based on simulation. As the mobility of nodes is one of the fundam ental characteristics of MANETs, mobility models have been proposed over th e years with the objective of accurately capturing the mobility of the users in MANETs. Due to the possibility of numerous com binations and unknown factors, it is difficult to model mobility in a satisfactory way. Therefore, the credibility of simulations studies on M ANET have been criticised heavily. Recently, a generic framework to generate mobility models has been proposed to model mobility under several scenarios of MANET. DGM models are m ainly based on the concept of destinations. The approach emphasizes th a t th e destinations m ust be considered as an integral com ponent of MANETs and th a t mobility can be modelled more accurately and easily based on destinations. In this thesis, we have imple­ mented a mobility modelling and analysis software tool and have conducted a study 85 on DGM models framework to te st its versatility an d suitability for modelling mobility in MANETs. Through an analysis of representative scenarios (including real trace) and simu­ lation studies using DGM models, we found th a t the DGM framework can be used to model mobility for a variety of M ANET scenarios more accurately and easily than using the earlier mobility models of MANETs. T h a t is, using DGM models framework mobility can be modelled more realistically w ith little effort than th e earlier mobil­ ity models used in MANETs. Also, we conducted a simulation study of one of the dominantly used MANET routing protocols AODV. As we expected, th e performance study of AODV shows th a t it performs b etter under more realistic DGM models than under RWP model. Overall, the work we did for this thesis confirms our initial intuition th a t th e DGM framework is simple and capable of modelling mobility for MANETs more accurately than the earlier models used in MANETs simulations. Therefore, we believe, if the DGM framework is used to model and analyse th e mobility traces properly before using the trace to study MANETs, some of the scepticisms raised in th e literature regarding MANET simulation studies can be dispelled. In th a t regard, we believe our work is interesting and useful. Our thesis work is a first study on DGM models. It can be extended in several directions, and some of them are the following. • More sophisticated or more specific M A N ET scenarios can be modelled and studied in detail using the DGM framework. For example, a specific real life scenario like a wild-life scenario or an office scenario can be modelled and studied in depth. 86 • An interesting research exercise would be examining the suitability of DGM models in modelling delay tolerant network scenario (e.g., a bus tra n sit system, a message ferry in a remote village, etc.). • The connectivity analysis can be done assuming th a t the destinations are con­ nected to the Internet or connected to cellular networks. • The performance analysis of other routing protocols such as DSR and DSDV can be conducted under DGM models and compared with their perform ance under RWP models. • More experiments can be conducted im porting traces of different real-world scenarios collected by different organizations, experimenting w ith DGM models to determine under w hat circumstance the DGM framework can sim ulate the collected real traces. • Several analytical results have been reported in the literature for RW P and its variant models. It would be interesting to see how those m etrics could be characterized and derived for DGM models. 87 Bibliography [1] A. Aravind and V. Manickam, “Destination guided mobility models for mobile ad hoc networks,” The 7th International Conference on Future Inform ation Tech­ nology , FutureTech 2012, June 26 - 28, Vancouver, Canada, 2012. [2] F. Bai and A. Helmy, “A survey of mobility modeling and analysis in wireless adhoc networks,” Book Chapter in the book, Wireless Ad Hoc and Sensor Networks, Springer, October 2006, ISBN : 978-0-387-25483-8., 2006. [3] S. Kurkowski, T. Camp, and M. Colagrosso, “M ANET simulation studies: the incredibles,” SIG M O B ILE Mob. Computer Communicatin Review, vol. 9, pp. 5061, October 2005. [4] N. Aschenbruck, A. Munjal, and T. Camp, “Trace-based mobility modeling for multi-hop wireless networks.,” Computer Communications, vol. 34, pp. 704 - 714, 2011 . [5] R. R. Roy, Handbook o f Mobile Ad Hoc Networks fo r Mobility Models. Springer,, 2011. [6] A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, and S. Suri, “Towards realistic mobility models for mobile ad hoc networks,” in Proceeding o f the 9th annual 88 international conference on Mobile computing and networking, MobiCom ’03, (New York, NY, USA), pp. 217-229, ACM, 2003. [7] T. R. Andel and A. Yasinac, "On th e Credibility of M anet Simulations,” Com­ puter, vol. 39, pp. 48-54, July 2006. [8] D. Cavin, Y. Sasson, and A. Schiper, “On the accuracy of m anet sim ulators,” in Proceeding of the second A C M international workshop on Principles o f mobile computing, POMC ’02, (New York, NY, USA), pp. 38-43, ACM, 2002. [9] I. Stojmenovic, “Simulations in wireless sensor and ad hoc networks: M atching and advancing models, metrics, and solutions,,” IE E E Communication Magazine, pp. 102 - 107, 2008. [10] A. Aravind and H. Tahir, “Towards modeling realistic mobility for perform ance evaluations in m anet,” AD H OC-NO W , Lecture Notes in Com puter Science, vol. 6288, pp. 109-122, 2010. [11] T. Camp, J. Boleng, and V. Davies, “A survey of mobility models for ad hoc network research,” Wireless Communications and Mobile Computing (W CM C): Special Issues on Mobile Ad Hoc Networking : Research, Trends, and Applica­ tions, vol. 2, pp. 483-502, 2002. [12] M. Feeley, N. Hutchinson, and S. Ray. “Realistic mobility for mobile ad hoc network simulation,” A D H O C -N O W 2004, L N C S 3158, ©Springer-Verlag Berlin Heidelberg 2004, PP- 324 -329, 2004. [13] M. Musolesi and C. Mascolo, “Mobility models for systems evaluation - a survey,” in Middleware fo r Network Eccentric and Mobile Applications, pp. 43-62, 2009. 89 [14] J. Collins and R. Bagrodia. “A quantitative comparison of com m unication paradigms for m anets,” in Proceeding of the 7th International IC S T Conference on MobiQuitous, 2010. [15] C. B ettstetter, “On th e connectivity of ad hoc networks," The Com puter Journal, © The British Computer Society; all rights reserved, vol. 47 No.4, pp. 432-447, 2004. [16] M. Boegsted, J. G. Rasmussen, and H. P. Schwefel, “Connectivity analysis of one-dimensional ad-hoc networks,” Wireless Netw © Springer Science + Business Media, L L C 2010., vol. 17, pp. 87-101, January 2011. [17] H. Conceigao, M. Ferreira, and J. Barros, “A cautionary view of mobility and connectivity modeling in vehicular ad-hoc networks.,” in VTC Spring, IEEE, 2009. [18] O. Dousse and P. Thiran, “Connectivity vs capacity in dense ad hoc networks,” in Twenty-third AnnualJoint Conference o f the IE E E Computer and C om m uni­ cations Societies (INFO CO M 2004 )■, 2004. [19] P. Lassila, E. Hyytia, and H. Koskinen, “Connectivity properties of random way­ point mobility model for ad hoc networks,” in Proceeding o f the f t h Annual Mediterranean Workshop on Ad Hoc Networks ( MedHoc-Net), pp. 159-168, 2005. [20] J. Nykvist and K. Phanse, “Modeling connectivity in mobile ad-hoc network environments,” in Proceeding o f the 6th Scandinavian workshop on Wireless Ad Hoc Networks (AD H OC 06), Johanesberg Slotts, Stockholm, May, 2006. [21] H. Pishro-Nik, K. Chan, and F. Fekri, “Connectivity properties of large-scale sensor networks,” Wireless Netw © Springer Science + Business Media, L L C 2009, vol. 15, pp. 945-964, O ctober 2009. [22] V. Borrel, M. D. de Amorim, and S. Fdida., “On natural m obility models.,” International Workshop on Autonom ic Communication (WAC), Lecture Notes in Computer Science, pp. 243-253, 2005. [23] N. Aschenbruck, E. Gerhards-Padilla, and P. M artini, “A survey on mobility models for performance analysis in tactical mobile networks,” Journal o f Cluster Computingnal o f Telecommunication and Inform ation Technology (JT IT ), vol. 2, pp. 54-61, 2008. [24] J. Harri, F. Filali, C. Bonnet, and M. Fiore, “Vanetmobisim: generating realistic mobility p attern s for vanets,” in Proceeding o f the 3rd international workshop on Vehicular ad hoc networks, VANET !06, (New York, NY, USA), pp. 96-97, ACM, 2006. [25] C. H artm ann and H.-J. Vogel, “Teletraffic analysis of sdma-systems w ith inhomogeneous ms location distribution and mobility,” Wirel. Pers. Commun., vol. 11, pp. 45-62, October 1999. [26] C. B ettstetter, “Smooth is b etter th a n sharp: a random mobility model for simu­ lation of wireless networks,” in Proceeding of the 4th A C M international workshop on Modeling, analysis and simulation o f wireless and mobile systems, MSWIM ’01, (New York, NY, USA), pp. 19-27, ACM, 2001. [27] P. Nain, D. Towsley, L. Benyuan, and L. Zhen, “Properties of random direction models,” in Proceeding of IE E E 24th Annual Joint Conference o f the IE E E Com ­ puter and Communications Societies(IN FO C O M ‘05.), vol. 3, pp. 1897 - 1907, 2005. 91 [28] E. M. Royer, P. M. M elliar-smith, and L. E. Moser, “An analysis of th e optim um node density for ad hoc mobile networks,” in Proceeding o f the IE E E International Conference on Communications, pp. 857-861, 2001. [29] L. B ajaj, M. Takai, R. Ahuja, K. Tang, R. Bagrodia, and M. Gerla, “Glomosim: A scalable network simulation environm ent,” Com puter Science Department, Uni­ versity of California, Los Angeles, Los Angeles, CA 90095. [30] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, “A perform ance comparison of multi-hop wireless ad hoc network routing protocols,” in Proceeding of the 4th annual A C M /IE E E international conference on Mobile computing and networking, MobiCom ’98, (New York, NY, USA), pp. 85-97, ACM, 1998. [31] C. B ettstetter and C. Wagner, “The spatial node distribution of th e random waypoint mobility model,” in Mobile Ad-Hoc Netzwerke, 1. deutscher Workshop iiber Mobile Ad-Hoc Netzwerke W M A N 2002, pp. 41-58, GI, 2002. [32] A. E. Kamal and J. N. Al-Karaki, “RMM: A new realistic mobility model for mobile ad hoc networks,” in Proceeding of the IE E E International Conference on Communications (ICC), 2007. [33] B. Liang and Z. J. Haas, “Predictive distance-based mobility m anagem ent for pcs networks,” in In Proceedings o f IE E E Inform ation Communications Conference(INFOCOM 1999), pp. 1377-1384, 1999. [34] F. Bai, N. Sadagopan, and A. Helmy, “The IM PORTANT framework for an­ alyzing the im pact of mobility on performance of routing protocols for adhoc networks,” A d Hoc Networks, vol. 1, pp. 383-403, 2003. [35] V. A. Davies, “Evaluating mobility models w ithin an ad-hoc network,” M a ster’s Thesis, Colrado School of Mines, 2000. [36] X. Hong, M. Gerla, G. Pei, and C.-C. Chiang, “A group mobility model for ad hoc wireless networks,” in Proceeding o f the 2nd A C M international workshop on Modeling, analysis and sim ulation of wireless and mobile systems, MSWiM ’99, (New York, NY, USA), pp. 53-60, ACM, 1999. [37] K. H. Wang and B. Li, “G roup mobility and p artition prediction in wireless ad-hoc networks,” Proceedings o f IE E E International Conference on Com munications(ICC’02), vol. 2, pp. 1017 - 1021, 2002. [38] M. Sanchez and P. Manzoni, “ANEJOS: a Java based simulator for ad hoc net­ works,” Future Generation Computer Systems, vol. 17, Issues 5, pp. 573-583, 2001 . [39] B. Zhou, , K. Xu, and M. Gerla, “Group and swarm mobility models for ad hoc network scenarios using virtual tracks,” In IE E E Proceedings o f M ILCOM , pp. 289 -294, 2004. [40] Roof-top network at M IT, http://pdos.csail.m it.edu/roofnet/. [41] TFA wireless data at Rice University, h ttp ://tfa .rice.ed u /. [42] Traces and tools at N U S T Wireless and Secure NetworksResearch Lab, http://w w w . wisnet. seecs. nust. edu.pk/downloads.php,. [43] UMass Trace Repository, http://traces.cs.um ass.edu/. [44] UCSD Wireless Topology Discovery, h ttp ://sysnet.ucsd.edu/w td/. [45] U N C /FO RTH Archive of Wireless Traces, Models, and Tools, http://netserver. ics.forth.gr/datatraces/. [46] A Community Resource fo r Archiving Wireless Data A t Dartmouth (C R A W DAD) , http://craw dad.cs.dartm outh.edu/. 93 [47] ns-2 - The Network Simulator - ns-2, h ttp ://w w w .isi.ed u /n sn a m /n s/. [48] GloMoSim - Global Mobile Inform ation System s Simulation Library , http://pci. cs.ucla.edu/projects/glomosim/. [49] QualNet Netwrok Simulator, http://www.scalable-networks.com/. [50] O PN ET Simulator, http://w w w .opnet.com /. [51] http://w w w .om netpp.org/. [52] N. Aschenbruck, R. Ernst, E. Gerhards-Padilla, and M. Schwamborn, “Bonnmotion - a mobility scenario generation and analysis tool,” in SIM UTools 2010 March 1 5 i£jl9, Torremolinos, Malaga, Spain. Copyright 2010 IC S T , IS B N 78963-9799-87-5. Digital Object Identifier: 10.4108/IC ST.SIM U TO O LS2010.8684, 2010 . [53] A. A. Aravind and X. Cui, “Rmobigen: a trace generation, visualization, and performance analysis tool for random mobility models,” in Proceedings o f the 2008 Spring simulation multiconference, SpringSim ’08, (San Diego, CA, USA), pp. 403-412, Society for C om puter Simulation International, 2008. [54] (CanuMobiSim) - C AN U Mobility Sim ulation E nvironm ent , http://canu. informatik. uni-stuttgart. de/m obisim /. [55] Tiger Database, Topologically Integrated Geographic Encoding and Referencing system, http://w w w . census.gov/geo/w ww/tiger/. [56] F. Martinez, J.-C. Cano, C. Calafate, and P. Manzoni, “CityMob: a mobility model pattern generator for vanets,” in Proceeding o f the IEEE International Conference on Communication(ICC), pp. 370 -374, 2008. 94 [57] P. Sommer, “Design and analysis of realistic mobility models for wireless mesh networks.” M aster’s thesis, Communication System Group, C om puter Engineer­ ing and Networks Laboratory(TIK ), D epartm ent of Information Technologoy and Electrical Engineering, Institute of Technology, Zurich, 2007. [58] S T R A W - STreet RA ndom Waypoint - vehicular mobility model fo r network sim ­ ulations, http://w w w . aqualab. cs. northwestern. edu/projects/STR A W /index.php. [59] FreeSim - Freeway Sim ulator , http://w ww .freew aysim ulator.com /index.htm l. [60] M. Behrisch, L. Bieker, J. Erdm ann, and D. Krajzewicz, “Sumo - sim ulation of urban mobility: An overview,” in SIM UL 2011, The Third International Confer­ ence on Advances in System Simulation, (Barcelona, Spain), pp. 63-68, October 2011 . [61] F. K. Karnadi, Z. H. Mo, and K. chan Lan, “R apid generation of realistic mo­ bility models for vanet,” in Proceeding of the IE E E Wireless C om m unications & Networking Conference, 2506-2511, 2007. [62] Opnet Steet Map, http://www .openstreetm ap.org/. [63] M. M. Artimy, W. Robertson, and W. J. Phillips, “Connectivity in inter-vehicle ad hoc networks,” CCECE 2004 - CCG EI 2004 Niagara Falls, © 2004 IEEE, vol. 1, pp. 293-298, 2004. [64] F. Theoleyre, R. Tout, and F. Valois, “New m etrics to evaluate m obility models properties,” tech. rep., CITI Laboratory -INRIA Rhone Alpes - INSA Lyon, 21, Avenue Jean Capelle -69621 Villeurbanne Cedex -France, 2007. [65] E. R. Cavalcanti and M. A. Spohn, “Estim ating the im pact of mobility m odels’ param eters on mobility metrics in m anets,” in Proceeding of the Eighth IE E E 95 International Symposium on Network Computing and Applications, NCA ’09, (Washington, DC, USA), pp. 227-233, IEEE Com puter Society, 2009. [66] I. W. H. Ho, K. K. Leung, J. W. Polak, and R. Mangharam, “Node connectivity in vehicular ad hoc networks w ith structured mobility,” in Proceeding o f the 32nd IE E E Conference on Local Computer Networks, (Washington, DC, USA), pp. 635-642, IEEE Computer Society, 2007. [67] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Pocket switched networks: Real-world mobility and its consequences for opportunistic forwarding,” tech. rep., University of Cambridge Computer Laboratory, Tech. Rep. UCAM-CL-TR-617, February, 2005. [68] L. Li, D. Alderson, J. C. Doyle, and W . Willinger. “Towards a theory of scale-free graphs: Definition, properties, and im plications (extended version),” arXiw.condmat/0501169v2, the prim ary verstion o f this paper at Internet M athematics, vol 2, page 4, 2005. [69] P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark, “Scenario-based performance analysis of routing protocols for mobile ad-hoc net­ works,” in Proceedings of the 5th annual A C M /IE E E international conference on Mobile computing and networking, MobiCom ’99, (New York, NY, USA), pp. 195-206, ACM, 1999. [70] D. B. Johnson and D. A. M altz, “Dynamic source routing in ad hoc wireless networks,” the book Mobile Computing, Chapter 5, edited by Tomasz Im ielinsk and, Hank Korth (Eds.), Kluwer Academic Publishers, Boston, pp. 153 - 181, 1996. 96 [71] S. Tang and B. Zhang, “A robust aodv protocol w ith local u p d ate,” The 2004 Joint Conference o f the 10th Asia-Pacific Conference on Communications, 2004 and the 5th International Symposium on Multi-Dimensional Mobile C om m uni­ cations Proceedings., vol. 1, pp. 418 - 422, 2004. [72] C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (aodv) routing.,” IETF. R F C 3561, July, 2003. [73] K. Amjad, “Performance analysis of dsr protocol under the influence of rpgm model in mobile ad-hoc networks.,” in 31st International Conference on Dis­ tributed Computing Systems Workshops, pp. 100-104, IEEE C om puter Society, 2011 . [74] A.-L. Barabasi, “Scale-free networks: A decade and beyond,” SCIENCE, vol. 325, pp. 412 - 413, 2009. [75] A. Polynikis, “Random Walks & Scale-Free NeTworks,” M aster’s thesis, D epart­ ment of M athem atics, University of York, August, 2006. [76] J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot. and A. Chaintreau, “CRAWDAD trace cam bridge/haggle/im ote/intel (v. 2006-01-31) ” Downloaded from http://craw dad.cs.dartm outh.edu/cam bridge/haggle/im ote/intel, Jan. 2006. [77] S. Ray, “Realistic mobility for M ANET simulation,” M aster’s thesis, University of British Columbia, Vancouver, C anada, 2003. [78] N. Aschenbruck, M. Frank, P. M artini, and J. Tolle, “Human mobility in m anet disaster area simulation - a realistic approach,” in Proceeding of the 29th A nnual IE E E International Conference on Local Computer Networks, LCN ’04, (Wash­ ington, DC, USA), pp. 668-675, IEEE C om puter Society, 2004. 97