GENERATION AND ANALYSIS OF REALISTIC MOBILITY MODELS FOR MOBILE AD HOC NETWORKS by Hassan Tahir B Sc , University of South Asia, Lahore, Pakistan, 2005 THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN MATHEMATICAL, COMPUTER AND PHYSICAL SCIENCES THE UNIVERSITY OF NORTHERN BRITISH COLUMBIA August 2010 ©Hassan Tahir, 2010 1*1 Library and Archives Canada Bibhotheque et Archives Canada Published Heritage Branch Direction du Patnmoine de I'edition 395 Wellington Street Ottawa ON K1A 0N4 Canada 395, rue Wellington Ottawa ON K1A 0N4 Canada Your file Votre r6f6rence ISBN 978-0-494-75110-7 Our file Notre reference ISBN 978-0-494-75110-7 NOTICE AVIS The author has granted a nonexclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distribute and sell theses worldwide, for commercial or noncommercial purposes, in microform, paper, electronic and/or any other formats L'auteur a accorde une licence non exclusive permettant a la Bibhotheque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par telecommunication ou par I'lnternet, preter, distnbuer 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 propnete 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 autonsation In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis Conformement a la loi canadienne sur la protection de la vie privee, quelques formulaires secondaires ont ete enleves de cette these While these forms may be included in the document page count, their removal does not represent any loss of content from the thesis Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant 1*1 Canada 11 Abstract Simulation modeling is an integral part of conducting research in communication networks and distributed systems In systems involving mobile nodes, accurate modeling of mobility has primary importance Mobility has a fundamental influence on the behavior and performance of the system However, only few mobility models have been used in nearly all simulations in the past These models are simple and highly random As a result, the simulation studies based on these random mobility models have been heavily criticized for their credibility We feel that availability of a software tool with the following capability, at least in part, would alleviate this crisis The software must facilitate researchers to (1) model a wide range of mobility with varying degrees of realism, (n) analyze the modeled mobility visually and statistically, and (in) transport the mobility trace in a format that can be used in most widely used simulators The development of a software tool with the above mentioned capabilities is the mam contribution of this thesis In this thesis, after presenting a comprehensive survey on realistic mobility models, we present a realistic mobility generator software called R L M o b i G e n that can be used to specify, generate, analyze, and then export the mobility trace The mobility trace can then be used in the simulation studies of mobile ad hoc networks RLMobiGen is a comprehensive, highly interactive, and user friendly software in Contents 1 2 Abstract iv Table of Contents iv List of Tables vn List of Figures ix Publications From This Thesis x Acknowledgments xi Introduction 1 1 1 Background 1 1 11 Role of Mobility in MANET 5 1 12 Role of Simulation m MANET 5 12 Motivation and Observations 6 13 Contributions 6 14 Thesis Organization 8 Literature Review 9 21 Survey of Mobility Models 9 211 Random Mobility Models 9 2 12 Realistic Mobility Models 12 22 3 Survey of Mobility Generators 15 A Unified Framework for Realistic Mobility M o d e l s 19 31 19 Introduction iv 4 32 A Classification of Mobility Models 20 33 Characterization of Force Points 22 34 Boundary Actions 22 35 Mobility Generation 23 36 Derivation of Realistic Mobility Models 25 37 Performance Metrics 26 371 Coverage Analysis 30 372 Connectivity Analysis 30 RLMobiGen 31 41 Computer Simulation 31 42 Architecture of RLMobiGen 32 421 Geometry Extraction 34 422 Geometry Generation by Vertical and Horizontal Roads 35 423 Geometry Generation from Real World Maps 37 43 44 45 Design 41 431 Simulation Initializer Parameters 41 432 Road Parameters 41 433 Force Point Parameters 42 434 Intersection Parameters 44 435 Node Carrier Parameters 44 436 Node Parameters 46 Implementation 46 441 User Interface 46 442 User Manual 51 Mobility Trace Files 53 451 NS-2 Mobility Trace Format 53 452 GloMoSim Mobility Trace Format 54 453 NAM Mobility Trace Format 55 46 5 XML Mobility Trace Format 56 455 JPG Mobility Trace Format 57 456 PDF Mobility Trace Format 57 Summary 57 Experiments 59 5 1 Experimental Setup 59 52 Movement Analysis 60 521 60 53 54 6 454 Leg Calculation Coverage Analysis 62 531 Node Placement 62 Connectivity Analysis 62 Conclusion and Future Directions 64 61 Conclusion 64 62 Future Directions 66 Bibliography 68 vi List of Tables 41 Open street map xml file ( osm) format 42 Node Carrier's Speed Range Selection 43 Example of trace file in the ns-2 format 44 Example of trace file in the GloMoSim format 45 Example of trace file in the NAM format 46 RLMobiGen xml trace file ( rmg) format 5 1 Node Carrier Parameters 6 1 Comparison of RLMobiGen and Other Mobility Generation vn List of Figures 31 Classification of Mobility Models 21 32 Realistic Mobility 24 33 Uni-directional Link 28 34 Bi-directional Link 28 35 Uni-directional Path 29 36 Bi-directional Different Path 29 37 Bi-directional Same Path 29 41 RLMobiGen Architecture 33 42 Vertical Roads 35 43 Connecting Roads 36 44 Horizontal Roads 36 45 OpenStreetMap GIS Data Export Tool 37 46 Geometry Editor Panel 47 47 Simulation Configuration Panel 47 48 Animation Panel 48 49 Animation Panel with Trace 48 4 10 Animation Panel with Transmission Range 49 4 11 Individual Stat subpanel 49 4 12 Sceneno Stat subpanel 50 4 13 Export Trace subpanel 50 4 14 Mobility trace for a single node m JPG format 57 vm 4 15 Mobility trace for a single node in PDF format 58 5 1 Number of Legs in Non-GIS Model 61 52 Number of Legs in GIS Based Model 61 53 Number of Legs 61 54 Average Distance Traveled 61 55 Node Placement in Non-GIS Model 62 56 Node Placement in GIS Based Model 62 57 Connection Changes 63 58 Session Duration 63 IX Publications From This Thesis 1 A Aravind, and H Tahir Towards Modeling Realistic Mobility for Performance Evaluations in MANET Proc of the 9th International Networks and Wireless (ADHOC-NOW), Conference onAd Hoc Lecture Notes in Computer Science (LNCS) , Springer-Verlag, 109-122, 2010 2 A Aravind, H Tahir, and Baldeep RealMobiSim realistic mobility simulator and analyzer Proc of the 3rd A CM Workshop on Performance Monitoring and Measurement of Heterogeneous Wireless and Wired Networks, 186-189, 2008 x Acknowledgments Throughout my time as a graduate student at UNBC, I came across many people who have encouraged me in one way or another, accompanied me through the tough times and helped me I can not possibly name them all here, but I would like to single out special thanks to a few First of all, I would like to express my sincere gratitude to my supervisor, Dr Alex Aravmd for his continued guidance, constant encouragement and support Without his unconditional help and erudite supervision this research would not have been possible I am also very thankful to Dr Waqar Haque and Dr Balbinder Deo for serving on my graduate committee and endowing me with their encouraging words, advice and valuable suggestions My thanks are also due to the external examiner for his/her time to read this thesis Here, I would like to take this opportunity to thank Dr Ian Hartley, Dean of Graduate Studies at UNBC for generously supporting my research through a Graduate Research Assistantship and a travel grant A special word of gratitude to all my colleagues and friends that I have worked and spent memorable time with over the past few years in Canada my fellow graduate students at UNBC, Mr I must thank Bharath Govinda Reddy, Ms Baldeep and Mr Viswanathan Mamckam for engaging me in useful research discussion They each helped make my time more fun and interesting I would also like to thank Mrs Alex Aravmd for her dinner invitations on various occasions I will always be thankful to my parents who have influenced my life in so many ways I must acknowledge my wife, Sidra, without her love, encouragement and patience, I would not have finished this thesis I also thank God for bestowing upon me such a loving and supportive family I doubt that I will ever be able to convey my appreciation fully, but I owe everyone my eternal gratitude XI Chapter 1 Introduction 1.1 Background Networks are infrastructures created and used throughout human civilization primarily for sharing resources The resources could be physical (such as food, water, electricity, etc ) or logical (such as message, data, voice, services, etc ) Among these networks, computing and communication networks have revolutionized the world in the last several decades and also played a fundamental role in creating other types of networks This thesis is concerned with a special type of networks called mobile ad hoc networks (MANETs) Telecommunication networks (telephone and telegraph networks), were created for people to talk to each other or send and receive messages In telephone networks, telephones were initially connected directly together in pairs, which later connected thiough telephone exchanges These exchanges are connected to each other, form- ing a network called public switched telephone network (PSTN) Telephone networks connect telephones to exchange voice and computer networks connect computers to exchange digital data They are similar in the sense that they both exchange information but in different form The evolution of computer networks has been driven essentially by two goals, sharing local resources and connecting to remote computers These two goals led to 1 two types of computer networks to emerge and they are called local area network (LAN) and wide area network (WAN) Initially, in the early 1960s, LAN started with connecting terminals to mainframes to share the computing power (a precious resource at that time) This network of terminals, typically placed in a room, and connected to the mainframe, allowed multiple users to share the system in parallel As processors became cheaper, desktop computers emerged and replaced the terminals This allowed the users to have their own computers in their offices connected to other systems within an organization Typically, LAN connects two or more computers over a relatively short distance normally withm a house or an office building On the WAN side, in 1969, the first network connected two computers from distant locations (University of California, Loss Angeles and Stanford Research Institute) Soon, two more nodes, one from the University of Utah and the other from the Univeisity of California, Santa Baibaia, weie added forming the fiist 4-node WAN called Advanced Research Project Agency Network (ARPANET) Until late 1980s, the distinction between LAN and WAN, ( e g , in data transfer rates and methods, in length and quality of communication links, and in services) was evident and then started to fade slowly Now, in most cases, WANs are typically used to connect LANs Today, Internet, the most widely known network, the largest WAN spanning the entire world, is a collection of LANs and small WANs After the establishment of LANs and WANs, again based on distance, moie classifications of computer networks emerged For example, the networks that are larger than LAN and smaller than WAN are called metropolitan area network (MAN), and the networks that are smaller than LAN are called personal area network (PAN) A PAN connects the computer and different devices close to one person All these networks have three main compo- nents nodes, links, and protocols Nodes and links form the topology and protocols and algorithms dictate network behaviour Nodes could be computers, telephones, switches, and other devices used to produce, consume, and/or forward resources (message, data, voice, etc ) Links are communication medium to transport resources, and the protocols are to regulate the formation and operation of the network 2 Irrespective of the network, communication between two directly connected nodes is simple and straightforward This is not the case when several intermediate nodes are involved in establishing communication between two end user nodes Setting up a "path" between two communicating nodes across the network and maintaining it throughout the communication period involves a number of tasks, particularly when several asynchronous communication are initiated Earlier telephone networks used a technique called circuit switching, in which the communication path is decided upon before the data transmission starts Then, for the entire session, the path stays as dedicated and exclusive Computer networks took a different innovative technique called packet switching In packet-switching, messages are broken into small pieces called packets, and the packets are sent towards the destination irrespective of each other This technique works very similar to how postal systems work There is no picdeteimined path and each packet has to find its own path to leach the destination Basically, each intermediate node decides, based on several factors including the destination address, congestion at that time, priority of the packet, etc , where to forward the packet next The process is repeated until the packet reaches the destination For quite some time, these networks used physical wires as the communication medium The mtioduction of wireless communication created a whole new dimen- sion for these networks to evolve further Apart from eliminating the complex mess of physical wires, wireless networks allow the nodes to move freely As a result, wireless LANs and PANs have become very common and a new type of telephone network called cellular network started to emerge A cellular network has a number of cells (a transmission region), and each cell is seived by a fixed wireless node called base station When joined together these base stations provide the coverage over a wider geographic area With this setup, people or vehicles with mobile devices such as mobile phones, pagers, etc , could communicate with each other without losing communication when they move from one location to another The network of base stations takes care of the "hand-off" communication between adjacent cells during 3 the mobility of the end user node In this setup, devices such as computers, routers, and switches play key roles in implementing the communication protocols and network management More importantly, computer and telephone networks started to adopt and use devices and technologies from each other and the distinction between these two networks is more blurred than before Most modern networks are hybrid in nature than either of the pure networks described above The networks discussed so far typically have a centralized control and are supported by fixed infrastructure also known as the backbone of the system These infrastructures involve several components such as wires, bridges, routers, base stations, etc Setting up a fixed infrastructure involves several resources such as time, money, permit, etc However, such infrastructure is not viable or even feasible in several situations involving applications such as wildlife tracking, military exercises in battlefield to maneuvei war fighters, environment monitoring, foicst file monitoring, flood monitoring, traffic monitoring, mine site operations, mobile patient monitoring, remote health, conferences and business meetings, etc This application pull and technology push discussed above paved the way for a new type of networks called Mobile Ad Hoc Network (MANET), which enables people setup and connect their computing and communication devices to networks whenever they need and wherever they go In a nutshell, MANET is a wireless communication technology designed to build a network with the following characteristics • Spontaneous and Ad hoc - the network must be setup in a shorter period of time, typically within hours and days instead of months and years, typically for a specific application • Self Organized - the nodes in the network must reorganize themselves with no or least assistance from human to establish the network Each node can perform the roles of both hosts and routers • No Fixed Infrastructure - the network should not depend on a fixed infrastructure, because such an infrastructure may not be feasible or possible 4 • No Centralized Control - the network must operate by the cooperation of all or most of the nodes in the network The responsibility of the network is typically shared among the nodes in the system due to several constraints such as energy, security, stability, availability, etc 1.1.1 Role of Mobility in M A N E T In MANETs, mobility plays a fundamental role Mobility influences the stiuctuie and behavior of the network and facilitates services across the network It impacts connectivity, coverage, routing and communication, and capacity of the network When mobility becomes inseparable from MANETs, selection of suitable mobility pattern and modeling it accurately are not only helpful but also essential for the understanding and interpretation of the performance of the protocols and services under study A good mobility model should capture an acceptable level of realistic mobility patterns of the expected scenarios 112 Role of Simulation in M A N E T Simulation is a technique of emulating or reproducing a real-life situation, process or a hypothetical circumstance In general, simulation is heavily used to study the behavior of complex dynamic systems MANETs encompass a wide range of dy- namic systems which are typically complex Due to their versatility, dynamic nature, and inherent complexity, it is difficult to characterize them analytically 01 conduct experiment using mobile nodes and wireless networks in realistic scenarios Real implementation of MANETs entails high cost and intensive toil Simulation is a useful and attractive alternative prior to actual implementation Therefore, nearly all published research works in this field are heavily based on simulations[5, 13, 20, 23] 5 1.2 Motivation and Observations Although most published works in MANET are heavily based on simulations, they have been heavily criticized, particularly in recent times, on the lack of rigor in simulation studies and questioned the credibility of the published claims[5, 13, 20, 23, 32, 34] Specifically, these studies indicate that the credibility of the simulation results in the field has decreased while the use of simulation has steadily increased However, there is no consensus on how to address the concern constructively and systematically This thesis makes a step towards addressing this important issue in relation to mobility models Most simulations in MANET uses random mobility models, particularly random waypomt model and its variations A specific type of MANET called vehicular ad hoc network (VANET) uses specifically designed mobility models incorporating roads and vehicular aspects Simulation with a very simple model and simulation with high realism are two extreme cases Between simple and sophisticated modeling, there is a spectrum of simulation models in which several useful models can be chosen with varying levels of details We feel that the purpose and contribution of the research should dictate the level of details in simulation Not all these mobility models are easy to implement from scratch Some, particularly those involving high level of realism, are very challenging to implement In such cases, how to ease this burden? What are the bases for realism in most common applications 7 Addressing these issues is the main motivation of this thesis 1.3 Contributions This thesis focuses on addressing the issues outlined in the motivation section by design and implementation of a mobility generation software tool called RLMobiGen [1] This tool can be used to create and analyze various mobility models suitable for a wide range of MANET applications The main contributions of this thesis aie 6 1 A comprehensive survey of realistic mobility models and survey of mobility generation softwares 2 Characterization of a unified framework for important geometric objects in the simulation region that has the potential to influence the mobility of the nodes in the system 3 Design and Implementation of RLMobiGen RLMobiGen has four main components 1 Creation of geometric elements 2 Visualization and analysis of movement scenarios 3 Calculation, analysis, and visualization of statistical metrics 4 Exporting mobility tiaces in 6 diffeicnt formats (NS-2, GloMoSim/Qualnct, NAM, XML, JPG, and PDF) Creation of geometric elements involves both random creation and extraction from GIS databases The latter involves extraction of realistic road topology, actual road speed limits, point of interests, traffic signals and stop signs information, etc , fiom Open Street Map GIS database RLMobiGen provides the following performance metrics 1 Movement metrics number of legs, leg distance, leg speed, leg duration, etc 2 Connectivity metrics number of connections, connection duration, connection changes, connection availability, etc 3 Coverage metrics node distribution, coverage, etc By using our software tool, users can generate, analyze, and adjust various scenarios of the specified mobility model By suitably controlling the parameters, various mobility models with diffeicnt level of icahsm can be generated and visualized 7 1.4 Thesis Organization A comprehensive survey of realistic mobility models and survey of mobility generation softwares are presented in Chapter 2 Next, in Chapter 3, we discuss the unified framework of realistic mobility models Chapter 4 presents the design of the RLMobiGen, a simulation software that we built and implemented to generate and analyze several realistic mobility models, which can be used in performance studies Experiments performed using RLMobiGen are discussed in Chapter 5 Finally, in Chapter 6, we conclude the thesis while outlining some future directions to extend the work carried out in this thesis 8 Chapter 2 Literature Review This chapter reviews the literature on mobility models and mobility generation softwares There exists a variety of mobility models that have been proposed in the hterature[16, 18, 28, 36] 2.1 Survey of Mobility Models Mobility models aie classified in the literature as purely random or realistic This section reviews the mobility models specifically proposed for mobile ad-hoc networks 2.1 1 R a n d o m Mobility Models Guerm's mobility model [46] has become the basis for a number of mobility models In Guerm's Mobility Model, as the simulation starts, each mobile node randomly chooses a direction 6 from the range (0 27r), randomly selects the speed from a user-defined distubution of speeds and then each node moves in its selected direction at its selected speed for randomly chosen period of time and the process repeats Various variations of this model have been proposed over the time One variance of this model is referred as Brownian Motion [41] The implementation of this mobility model is as follows as the simulation starts, each mobile node chooses a direction 9 from the range (0 2TT) using uniform distribution, selects the speed using normal 9 distribution and then the node travels in the chosen direction with selected speed for randomly chosen time period and the process repeats It is renamed as Random Direction model in [36] In a different variation of this model [44] when a node hits the simulation boundary on the vertical edge it is reflected back into the coverage area with an angle of -6 and with an angle of (ir-0) in case if it hits the simulation boundary on horizontal edge Another simplified variation of this model is introduced in [33] Unlike the previous model the velocity of the node is held constant until it hits the boundary When it hits the boundary, it bounces back into the simulation region without pausing at the boundary In a different variation of this model [35] when a node hits the simulation boundary, it pauses for the fixed time and then randomly chooses a direction 8 from the range (0 ir) A variation in random direction mobility model is introduced in [36] and referred as Smooth Random Mobility Model In this model, speed and direction of mobile node changes incrementally, and smoothly and the direction change correlates with the speed change (l e node slows down while changing the direction) In Random Walk Model (RW) as described in [28], each mobile node randomly chooses a direction 9 from the range (0 2ir), selects the speed between 0 and lOm/s and then travels foi a fixed time period of 60 seconds and the process repeats In anothei variation of this model as also described in [28], instead of traveling foi a fixed time period (60s), each mobile node travels a fixed number of steps (10 steps) in a direction 6 randomly chosen from the range (0 2ir) at the speed between 0 and lOm/s A variation of random walk model is implemented in Global Mobile Information System Simulator (GloMoSim) [47] and referred as Random Drunken Mobility Model In this model, each node is randomly placed withm a field The node then moves m a direction randomly chosen from the list of possible directions and ensures that it remains m the field boundaries If a node is at location (x,y) then it can move to any of the (x, y-1), (x, y+1), (x-1, y), or (x+1, y) locations as long as the new location is withm the coverage region 10 The Gauss-Markov Mobility Model is introduced in [42] In this model, the current speed and direction determines the next speed and direction, for every fixed interval of time Therefore, it is a temporally dependent mobility model and the memory level parameter determines the degree of dependency One frequently used mobility model is Random Waypoint Model (RWM) It was introduced in [43] It became a benchmark mobility model to evaluate the MANET protocols, because of its simplicity and wide availability The implementation of this mobility model is as follows as the simulation starts, each mobile node randomly selects one location in the simulation region, then the node pauses at its current location for a fixed period, which is called pause time, chosen uniformly from the range of minimum and maximum pause time, and then randomly chooses a new location as the destination, it then travels towards the destination with constant velocity chosen randomly from the range of minimum and maximum velocity by using uniform distribution and the process repeats Another model is introduced in [45] and referred as Boundless Simulation Mobility model Area It is proposed to eradicate the border effect in simulation aiea by introducing wrap around effect on a simulation boundary In this model, when a node hits a boundary of the simulation area it reappears from the opposite side of the simulation boundary with the same speed and direction This technique creates a torus-shaped simulation area allowing mobile nodes to travel unobstructed But one of the inadequacies of this model is that a stationary node and a mobile node moving in same direction become neighbors over and over again [28] The Reference Point Group Mobility model was introduced in [39] In this model, several mobile nodes move together, forming a group as well as each individual mobile node moves randomly within the group The mobility of the logical center for each group, and the mobility of each individual mobile node within the group, are both implemented using the Random Waypoint mobility model The Pursue Mobility model as mentioned in [28] is based on reference point group mobility model This model simulates scenarios where several mobile nodes attempt 11 to capture single mobile node ahead For example, this model could represent police officers (1 e , seeker nodes) attempting to catch an escaped criminal (1 e , target node) The target node moves freely using Random Waypoint model and seeker nodes try to capture the target node by directing themselves towards the position of the targeted node A generalized model is introduced in [30] and referred as Graph-based Mobility model In this model, the graph represents the locations that the user might visit and the edges model the connection between these locations, for example, streets or tram connections Initially, each mobile node is placed at a random vertex m the graph and selects another vertex randomly as its destination and then moves towards it using the shortest possible path After reaching the destination, the node pauses for some randomly selected period and then selects another destination and the process repeats 2 12 Realistic Mobility Models Several researchers have proposed mobility models discussed below, which are designed to be more realistic than the models discussed earlier A variation of random waypoint model is proposed m [11] and referred as Realistic Mobility Model As the simulation starts, both initial location and the destination are randomly chosen from uniform distribution, speed of the node is determined by speed zone which has minimum and maximum speed limits, and initial direction is chosen from 5 directions that are separated by segments with equal angles (^f) The direction towards the destination is chosen with probability do, while a direction that is i segments away from the leading direction is chosen with probability of d% Street Map-based model is introduced in [25] to extract the roads from Tiger database [58] In this model, a node randomly selects a destination point on the road graph and moves towards it using Dijkstra's shortest path algorithm An activity based mobility model is introduced in [40] In this model, simulation region is divided into multiple cells and each cell represents a unique location Node 12 selects an activity (or trip purpose) duration and location Each activity has an associated time of day, Given the current activity, the current time period and the node type, the next activity is randomly selected from the corresponding entries in activity transition matrix Once the activity is selected, its duration is chosen from the activity duration matrix Node then travels to a new location, determined from the type of the activity After reaching at the destination cell, node stays there for the duration of the activity and the process repeats Another simple realistic mobility model is introduced using random waypoint model in [29] and referred as Restricted Random Waypoint model also called as Localized Random Waypoint model To bring realism to random waypoint model, towns and highways are introduced Towns are sub geographic regions that are connected with highways inside a simulation region Node moves with the random waypoint mobility model inside towns for majority of the time However, after a certain number of movements in the same town, a node moves to another town over a highway To simulate the geometry of city streets, City Section Mobility model [37], is proposed It models a section of the city having a downtown area with freeway Initially, each mobile node is placed randomly on some point in street, and then randomly chooses a new location on some other street as the destination It then travels towards the destination through shortest path between two points keeping the safe driving characteristics such as speed limit and safe distance between two nodes Upon reaching the destination, the node pauses at its current location for a fixed period and repeats the process until the simulation ends To synthesize the real-world mobility, couple of models are introduced in [26] and referred as Freeway Mobility model and Manhattan Mobility model The movement of node is restricted to pathways m the simulation field In the freeway mobility model, the map consists of several freeways and each freeway has lanes in both directions The velocity of mobile node is temporally dependent on its previous velocity Also, the velocity of the following node cannot exceed the velocity of preceding node - also known as spatial dependency In Manhattan mobility model, the map consists of 13 horizontal and vertical lines representing downtown area The movement of node is restricted to horizontal and vertical pathways in the simulation field At an intersection, the mobile node can turn left, right or go straight with a probability of 0 25, 0 25, and 0 5 respectively Unlike freeway mobility model where node cannot change the lane, Manhattan mobility model gives a node some freedom to change its direction Except the above diffeience, the Manhattan model is the same as Fieeway model because the Manhattan mobility model also has high spatial and temporal dependence A variation of Manhattan mobility model is introduced in [6] and referred as Simple Model which models vertical and horizontal mobility patterns without direction changes Another mobility model is introduced in [27] and referred as Obstacle Mobility model A realistic movement model is created through the incorporation of obsta- cles and pathways using Voronoi diagram [38] of obstacle vertices in the simulation field These obstacles are used to restrict node movement as well as obstruct wire- less transmissions In this model each node randomly selects a destination point and then moves towards the selected point through the shortest route from its current location After Icaching the destination, the node pauses for some time penod The process repeats The obstacles also impact the way ladio propagates However, since the location of obstacles and destination of each motion phase is randomly chosen, a certain level of randomness still exists for this model Several mobility modeling tools for vehicular ad hoc network (VANET) extracts necessary geometry from the local GIS databases such as Tiger database [58] or Geobase [51] The models rely on GIS maps also called GIS Models VANETs are a subclass of MANETs in which mobility patterns are more constrained as they involve specific aspects such as traffic rules, traffic flow; road capacity, vehicle characteristics, etc As one of the important characteristics of vehicular mobility is the behavior of mobile nodes at traffic intersections (stop signs, traffic light) A model was introduced by Potnis and Mahajan [14] known as Stop Sign/Traffic 14 Sign Model that simulates the stop sign and traffic lights In the Stop Sign Model, each vehicle stops at every intersection and waits for a fixed time period In the Traffic Sign Model, vehicles stop with probability of 0 5 for a random time m front of a traffic light Another mobility model called Car-Following Model (GIS-F) [4], is designed to simulate the microscopic behavior of vehicles In this model, the current speed of a vehicle depends on it's previous speed and the desired speed, also maintaining the minimum safety distance to the front vehicle (if any) Another variation of this model is called GIS-F-T (car-following & traffic lights) [4] It is the same as GIS-F however traffic lights are incorporated at intersections 2.2 Survey of Mobility Generators In this section, we present the comparison of existing mobility generation tools Several software tools are available that can be used for mobile computing simulations Some of them are proprietary tools that are not freely available, such as QualNet [55], OPNET [53], or VISSIM [59] However, there are freeware and open source simulation software which are widely used by the research community Simulation softwares can be divided into three main categories (a) mobility generators (b) network simulators, and (c) combination of both mobility generators and network simulator Several mobility generation tools exists which are as follows • NS-2 The network simulator is a discrete event simulator, developed by VINT project research group and suppoited by DARPA [52] NS-2 provides substantial support for simulation of network communication protocols over both wired and wireless (local and satellite) networks NS-2 was later extended to include node mobility feature by Monarch research group and it supports random waypoint mobility model • GloMoSim It is a parallel discrete-event simulator, developed by the parallel computing laboratory at UCLA [50] 15 It exhibits a scalable simulation envi- ronment for both wireless and wired networks It supports random waypoint, random drunken and trace based mobility models • QualNet It is a commercial version of GloMoSim which provides ultra high- fidelity network evaluation [55] • STRAW Street Random Waypoint [56] is specifically designed foi VANET, uses a vehicular mobility model on US road topology, which constraints the node movement to streets of real US cities It is limited in providing the whole world map data and also the generated mobility trace can only be exported for SWAN [57] • SUMO Simulation of Urban Mobility [31] is also based on vehicular mobility model and extracts the real world road topology Its mam features include multilane streets with lane changing capability, collision detection and intersection based rules Though it is a powerful tool to generate traffic network simulation, it does not have an option to export generated traces for available network simulators, which makes it very limited to study network protocols • M O V E Mobility Model Generator for Vehicular Networks [10] is built on top of SUMO, which generates mobility models for vehicular network simulations The mobility trace can be exported for network simulation tool such as NS-2 or GloMoSim • VanetMobiSim Vehicular Ad Hoc Network Mobility Simulator [15] is an ex- tension of another tool called CanuMobiSim [48] which generates mobility trace from a user specified XML configuration of a mobility pattern VanetMobiSim can import maps from the TIGER [58] database as well as generate random maps using Voronoi tessellation Its main features include vehicle acceleration, deceleration, multi-lane streets with lane changing functionality, but does not provide a support of multiple vehicle types However, the generated mobil- ity trace can be exported for diffeient mobile networks tools including NS-2, 16 GloMoSim, and QualNet • GrooveSim It is a mobility and communication simulator [19] GrooveSim imports map files from the TIGER database to generate realistic topologies It was designed to simulate the motion constraints of vehicles related to the speed limit of roads However, it does not model vehicles micro-mobility and does not provide facility to export generated traces for available network simulators • MobiREAL It is proposed with the intent of modeling a real world envi- ronment, specifically designed to study urban pedestrian mobility [2] It is a network simulator that can simulate realistic mobility of nodes using probabilistic destination selection User creates street graph and routes though GUI using mouse clicks which creates an extreme time overhead It was initially designed to simulate MANETs and was later extended to include VANETs by incorporating the traffic simulator NETSTREAM [17] that was developed by TOYOTA Since NETSTREAM is a proprietary software, user can not access and modify this part of the simulator which limits its wide usage • CityMob It generates the mobility based on three models, Simple Model, Manhattan Model, and Downtown model [6] It generates the random road network using Manhattan grid model and does not provide the facility to create user defined roads or road extraction through GIS data All streets are two- way, with lanes in both directions and node moves with random speed, withm an user-defined range of values Generated mobility trace can be exported m NS-2 format • FreeSim Free Way Simulator [49] is specifically designed for VANET that allows for multiple freeway systems to be easily represented and loaded into the simulator as a graph data structure The traffic data used by the simulator can be user generated or be converted from real-time data gathered by a transportation organization However, FreeSim does not support multiple node types and 17 its generated trace can not be used by the available network simulators, which is a serious shortcoming • I M P O R T A N T The IMPORTANT framework [26] contains metrics to capture mobility characteristics and evaluate the impact of the performance of routing protocols but does not offer visualization of animation • G M S F The Generic Mobility Simulator Framework [9] is a tool to simulate and analyze node mobility in vehicular ad hoc networks The road topology is extracted from official Swiss national map (Landeskarte) which constrains the node movement to Swiss streets The mobility trace can be generated using Random Waypoint model, Manhattan model, GIS model, and MMTS model The MMTS mobility model uses the vehicular traces to generate the movement of mobile node Only roads which are accessible by vehicles are imported into the road topology The mobility trace can be exported in multiple formats • G E M M This tool is proposed m [22], brings realism into random way point model by introducing attraction points, activities, roles and group behavior Given the role type, activity is chosen based on its trigger time and hence the attraction point is selected based on its popularity level and the activity triggered Nodes may move between attraction points or any other random location (similar to random waypoint) SUMO, MOVE, STRAW, and VanetMobiSim all have good software features However, only VanetMobiSim provides excellent trace support [3] Generic simulation tools like NS-2 [52], OPNET [53], QualNet [55] support only limited mobility models such as random waypoint model and its variations various random mobility models is proposed in [7] 18 Similar softwaie to generate Chapter 3 A Unified Framework for Realistic Mobility Models 3.1 Introduction In this section we introduce some basic terminology related to mobility models, and piovidc a simple classification of mobility models, chaiacteiize a fiamcwoik foi geometric objects which influence realism in mobility, and discuss some performance metrics Fust we introduce some definitions which will be used latei Definition 3 1 A node refers to the mobile devices used in MANET ie mobile phone, PDA, laptop, palmtop, etc Definition 3 2 A node carrier (NC) refers to the transporter of the node This can be a car, a pedestrian or a bicycle, for example Definition 3 3 A force point is known as a point of interest where node may or may not go Definition 3 4 A road is known as a straight path between two points Definition 3 5 An intersection is a road junction where two or more roads either meet or cross at the same level 19 Definition 3 6 A connecting point is a point on the road where a road crosses the simulation boundary region 3.2 A Classification of Mobility Models Though several attempts have been made in the literature to classify mobility models, the distinction between random mobility and realistic mobility is not clear and the boundary between them is often fuzzy For example, many mobility models that just avoid sharp turns and sudden speed change are referred as realistic mobility models in the hterature[18 / 22, 24, 28], although they are heavily influenced by randomness We use different classifications to make the distinction better We classify the mobility models into two classes unguided mobility and guided mobility [8] as shown in figure 3 1 In unguided scheme, the mobility is mamly governed by the characteristics of the node In guided scheme, the mobility of a node is governed by both the characteristics of the node as well as the geometry of the region Primary geometry includes mainly the transportation paths such as roads, railways, ferry routes etc Many additional geometrical elements such as malls, gas stations, hotels, etc can be introduced mto the region to create more realism Although random mobility is very useful for many research studies, mobility of living creatures do not follow a complete random mobility pattern Often they are guided by many factors such as infrastructure (roads, malls, trails, playgrounds, mountains, etc ), piofession or role (students, bus drivers, factory workeis, flight attendants, etc ), activities, time, etc That is, mobile nodes in real life often follow constrained and predictable mobility patterns, and also, the mobility of a node may be bounded by streets, freeways, obstacles or buildings 20 Mobility Models Un-Guided Mobility Models Guided Mobility Models Guenn's mobility Model Realistic Mobility Model Browman Motion Activity-based Mobility Model Random Walk Model Restricted Random Waypomt Random Waypomt Model City Section Mobility Model Random Direction Model Freeway Mobility Model Smooth Random Mobility Model Manhattan Mobility Model Random Drunken Mobility Model Simple Model Boundless Simulation Area Mobility Model Obstacle Mobility Model Reference Point Group Mobility Model Stop Sign/Traffic Sign Model Pursue Mobility Model Car Following Mode! Gauss-Markov Mobility Model Graph-based Mobility Model Street Map-based Model Figure 3 1 Classification of Mobility Models 21 3.3 Characterization of Force Points Generally, regions of interest have objects that could influence the mobility of the nodes m the system These objects are broadly identified in the literature as obstacles that the mobile nodes cannot pass through, attraction points that the mobile nodes might attracted to, and repulsion points that the mobile nodes would want to avoid going near to To bring all these objects into a generic framework, we refer to them collectively as force points and the force between an individual class of nodes and a force point can be defined using suitable force function Let FP be the set of all force points and iV be the set of diffcient classes of mobile nodes Then the domain of the mter-force function FF is FP x N (Cartesian product of FP and N) and the range is R (real numbers) For any class of mobile nodes, the force point is attraction point if the value of inter-force falls in the range (-00, 0) Similarly, the force point is repulsion point if the value of mter-force falls in the range (0, 00) The force point is obstacle, when the force is 0 These force points could be stationary or mobile For example, ice cream trucks, ambulance, trucks with inflammable materials can be consideicd as mobile foicc points Parks, theater, museum, etc , can be considered as stationary force points So each force point may be attached with a speed parameter The value of this parameter may vary with time Now, we have three parameters related to each force point speed, time, and mter-force If we consider these three parameters in three orthogonal dimensions, each force point will have a unique position in this space This unified characterization of obstacles, attraction points, and repulsion points, along with their mobile characteristics as force points in a common framework may be useful to model and study the characterization of mobile nodes in MANET 3.4 Boundary Actions Another interesting issue in generating mobility trace with a bounded region is what happens when a node hits the simulation boundary This can be handled m many 22 ways We implement three simple approaches and we refer them as exit, replace, and enter-and-exit Approach 3 1 Exit The node instantaneously disappears when it hits the boundary In this model, the number of nodes in the system decreases as system progresses Approach 3 2 Replace When a node hits the boundary, it reappears from another random location on any of the road in the simulation region In this scheme, the number of nodes remains the same throughout the simulation Approach 3 3 Enter-and-Exit the boundary The node instantaneously disappears when it hits Also, nodes appear from the boundary randomly In this model, the number of nodes in the system varies according to enter and exit rate set by the user In realistic mobility scenario a node may enter in and exits from a simulation region In a trip, a node may choose either a force point or a connecting point as its destination and proceeds towards it System collects all the possible connecting points based on the load tiaffic flow (unidnectional or bidirectional) 3.5 Mobility Generation The main goal of RLMobiGen is to generate mobility with high realism We emphasize that environmental factors influence leahsm in the mobility models as illustrated in figure 3 2 The first step in generating the mobility is the identification of all the environmental factors which impacts the mobility behaviour We have divided the environmental factors into two sub classes force point scheduling and road geometry Having all the information about the force point, scheduler calculates the availability of all the force points in a given simulation time Road geometry keeps information about all the vertices in a geometry and location of the force points It also stores the location of all the road points intersecting the boundary to implement the boundary action 23 Nta» to r>9w loujtton environments Factors List of all possible force pewits with storting ending <«id »Muse urse Mobility Generanort FWCH Points Sctadyiing D*^ Road Geomelry AltoAed / tabidden roads f W « Pe!pUK>l Cwt«.idarlnq<3il 9lla*ed waft Spssd Control SpBKl Limit • Traffic Ssgna! Speed Adjustment 1r With psppct to the road and no** s>pml fingers Figure 3 2 Realistic Mobility The next step in mobility generation is destination selection A node selects either a force point or a connecting point as its destination This becomes possible by the information provided by environmental factors Force point is selected based on the force value set for specific node class The next step is to generate a route from current location to the destination We call the movement between current location and the destination the trip of the mobility Normally, the shortest route between these two points is calculated, but the force value of all the force points on the calculated route may change the path (the user prefers to go through other attraction points and avoid repulsion points on the way) Once the route selection is done, speed adjustment is carried out through out the trip Once again environmental factors like traffic lights, road limits and node's own speed capability are the deciding factors in speed selection be multiple intermediate points in a trip There can We call the movement between any two consecutive intermediate points the leg of the mobility On reaching the destination, the node selects another destination and this process repeats until the simulation ends 24 3.6 Derivation of Realistic Mobility Models Realistic mobility models can be derived in several ways • Deriving directly from real traces • Introducing realistic aspects like making turns, directions, speeds, and pauses in constrained ways into random mobility models • Introducing geometric objects such as roads, highways, obstacles, attraction and repulsion points randomly or based on some graphs in the simulation region • Introducing group mobility based on social networks In these, models derived from real traces would give highly realistic mobility model But, the availability of such traces are rare and even available historical data are remotely useful as they seldom reflect the future pattern Random mobility models aie synthetic and, therefoie, they may not leflcct mobility of a piactical system However, it was considered reasonable to use such models, and particularly one of the random mobility models called random waypoint model is expected to exist as the benchmark mobility model m MANET simulations[21] Random waypoint model is simple and supported by mathematical foundations It will remain natural choice for most proof of concept type simulations However, for simulation of more realistic MANETs, we believe that the rate of use of random mobility models in MANET simulations would decrease drastically if better alternates are available systems will rarely have nodes with random dominated mobilities Practical Therefore, we consider mobility models based on GIS would be more desirable in designing more realistic MANET simulations Again, introducing geometric objects may be done in, at least, three ways • Creating random objects and roads • Extracting objects of real world scenarios from geogiaphic information system (GIS) databases 25 • Combination of above two 3.7 Performance Metrics In Mobile ad hoc network, the node's mobility plays a vital role that causes constant changes in ad hoc network topology and hence urges a need to study statistical properties of node mobility In order to evaluate mobility, several performance metrics are introduced in literature Performance metrics used to analyze mobility models fall mainly into three categories [7], movement metrics, connectivity metrics and coverage metrics 1 Movement metrics It can be computed for number of legs, leg distance, leg speed, leg duration, origin, destination, direction etc 2 Connectivity metrics It can be calculated to analyze the connectivity between number of nodes, which may include metrics like number of connections, connection duration, connection changes, connection availability, etc 3 Coverage metrics It can be calculated to analyze the netwoik graph coverage which may include metrics like node distribution, node coverage, etc The above metrics, if applicable and meaningful, may be computed for minimum, maximum, average, total, standard deviation, rate, ratio, etc , and also at individual, group, or system level RLMobiGen provides the following instant information for each node n at the sampling time - node instant position (x, y) - origin (x, y) - destination (x, y) - current speed (km/h) 26 - leg start time (seconds) - leg duration (seconds) - pause at destination (seconds) In almost every networked system, communication is a fundamental problem for most applications and in dynamic system like mobile ad hoc network, even achieving effective communication between the mobile nodes is challenging In mobile networks, the nodes with transmission range form a dynamic graph known as connectivity graph The connectivity and the coverage of this graph influence the performance of most of the communication protocols The following terminologies related to connectivity and coverage are introduced in [12] Definition 3 7 A link is said to exist or be ON between two nodes i and j if they are within each other's transmission and it is denoted by range Link is a boolean function over time t hnk(i,j,t) Definition 3 8 A p a t h is said to exist or be ON between two nodes i and j if there is a sequence of nodes and the links between consecutive nodes in the sequence are ON Path is also a boolean function over time t and it is denoted by path(i,j,t) Definition 3 9 The interval between ON state and immediate OFF state of a path between the nodes % and j is a session and it is denoted by Session is also a boolean function on time t session(i,j,t) We define a new teimmologies i elated to link and path which aie tcimed as directional link and directional path Definition 3 10 A Directional link is said to exist or be ON between two nodes i and j if any of them is in each other's transmission range Link can be uni-directional (shown in Figure 3 3) or bi-directional (shown in Figure mission range of two nodes Link is a function link(i,j,t) 27 3 4) based on the trans- over time t and it is denoted by y / * t \ A \ \ / / / / \ / \ \ \ ^ % • J?; V \ \ ^ / / / s / Figure 3 4 Bi-directional Link Figure 3 3 Um-directional Link hnk(i,j,t) \ ^ "V, \jf \K 1 / B /• / returns any of the following three values, • 0 - Link is OFF • 1 - Link is ON and it is uni-directional • 2 - Link is ON and it is bi-directional Figure 3 3 shows a um-directional link between node A and node B Node B can send the data to node A but node B can not receive the data from node A, as node B is not in the range of node A A -*• B but B -»• A A ^ B Figure 3 4 shows a bi-directional link between node A and node B Node A can send the data to node B and also can receive the data from node B A -> B and B -»• A A ^B Definition 3 11 A D i r e c t i o n a l p a t h is said to exist or be ON between two nodes i and j if there is a sequence of nodes and the links between consecutive nodes in the sequence are ON Path can be uni-directional or bi-directional based on the links Path is a function over time t and it is denoted by path(i,j,t) path(t,j,t) returns any of the following four values, 0 - Path is OFF 28 • 1 - Path is ON and uni-directional (all links are uni-directional) • 2 - Path is ON, bi-directional and one or more links are uni-directional • 3 - Path is ON, bi-directional and all links are bi-directional ' A % - , I \ \ I ' "' -v c J Figure 3 5 Uni-directional Path Figure 3 5 shows a uni-directional path between node A and node D Node A can send the data to node D through node B and node C, however node D can not send the data to node A, as no node is in the range of node D A-»B-*C-»-DbutD^A A => D Figure 3 6 shows a bi-directional path between node A and node D but through two different uni-directional paths Node A can send the data to node D through node B and node C however node A receives the data from node D through node E Go , \ \ Figure 3 6 Bi-directional Different Path Figure 3 7 Bi-directional Same Path 29 A^B^C-*DandD^E^A=»A?±D Figure 3 7 shows a bi-directional path between node A and node D where all links are bi-directional Node A can send and receive the data from node D through node B and node C A ^ B ^ C - ^ D a n d D ^ C ^ B ^ A = ^ A ^ D 3.7 1 Coverage Analysis Coverage is influenced by both mobility and transmission range of the nodes Node distribution and the ratio of the simulation area covered by transmission range to the total area are useful metrics to be analyzed for coverage Since RLMobiGen is a discrete time based simulator, the metrics are computed over discrete times Here the objective is to study how the nodes spread in the simulation region during simulation To compute the node spread or spatial distribution, the region is divided into small cells of equal height (h) and width (w), where h and w are two positive integer values and then the nodes are counted inside each cell after specific interval of time 3 72 Connectivity Analysis For connectivity analysis, we mainly study two metrics the connection changes and the session duration Path duration is an important metric for testing communica- tion protocols For example, some protocols referred as connection-oriented protocols require the path between source and destination to be ON throughout the communication 30 Chapter 4 RLMobiGen This chapter presents the software architecture and design of RLMobiGen RLMobiGen is a tool to simulate, analyze, visualize, and generate the trace of realistic mobility models Before presenting RLMobiGen, we briefly describe computer simulation 4.1 Computer Simulation Computer simulation of a system is simply a computer program that runs on a computer and transforms the state of the system in discrete time points over a specified period of time Computer simulation can be divided into multiple categories If the simulation program solves mathematical equations (most dynamic systems are usually modeled using differential equations) periodically, and uses the solutions to change the state and output of the simulation, then this simulation is called continuous simulation Originally, analog computers were used to run these kind of simulations If the system changes it state at discrete points in time where events occur probabilistically and can not be described directly using mathematical equations is known as discrete simulation Discrete simulation can be furthei classified as discrete-time and discrete-event simulation Discrete event simulation consists of event list, simulation clock and event scheduler In discrete event simulation the simulator maintains a queue of events (also 31 called event list) sorted by the simulated time they should occur Simulation clock maintains the simulation time and it is advanced to the time of occurrence of next event in the event list Since, it is not important to execute the simulation in real-time, the advancement of the simulation time can be same, faster or slower than real-time For example, in the simulation of humans evacuating a building, the queues buildup can be visualized using fastei than real-time simulations, simulation of current flow through an electric circuit can be shown using slower than real-time simulations, and in-training simulations (1 e flight simulators) can be exhibited using real-time simulations Event scheduler executes event from the event list and the system state changes at the occurrence of each event in the system System state is represented by state variables For instance, m simulating the behavior of queue at the bank-teller, the number of customers arnved and the number of customers served are state variables and these will be updated on the occurrence of some event in the system The number of customers arrived will be updated when the customer arrives in the bank and the number of customers served will be updated when the bank-teller serves the customer Simulation continues until either event list becomes empty or simulation time ends The performance metrics of the system are collected from the state variables, and also by using various ways of scientific visualization, simulation results are often aggregated into static images 4.2 Architecture of RLMobiGen In higher level, the architecture of RLMobiGen is illustrated in figure 4 1 RLMobiGen has following five mam logical components • Simulation Initializer Simulation initializer (SI) is responsible foi generating the basic simulation environment It initializes the simulation with parameters such as simulation area, simulation time, and boundary action • Geometry Geneiator Geometry generator (GG) is responsible for generating 32 GUI RLMobiGen ZL. Simulation Initializer Geometry Generator • Mobility Trace Generator Execution Trace -i * Mobility Scenario Manager Mobility Trace Exporter 3QE Performance metrics & visualization GUI Figure 4 1 RLMobiGen NS2 trace Architecture the geometry of real life artifacts such as roads, malls, and trails which guide the mobility of the nodes • Mobility Generator Mobility generator (MG) is responsible for creating nodes and generating their mobility trace The trace also contains information re- quired for visualization and statistical metrics computations based on the parameters set in SI, GG, and MG • Mobility Scenario Manager This component is responsible for extracting various statistical insights and providing visualizations • Mobility Trace Exporter ity trace RLMobiGen also allows user to export the mobil- It is responsible for converting the mobility trace into following six formats 1 NS-2 33 2 GloMoSim/QualNet 3 NAM 4 JPG 5 PDF 6 XML The development of RLMobiGen involves four main tasks (I) generating geometry for the simulation region, (n) characterizing mobile nodes and mobile locations, (in) modeling mobility, and (IV) providing meaningful statistical analysis 4.2.1 Geometry Extraction Generating the geometry for simulation region can be done in several ways Particularly, geometry can be generated randomly or extracted from maps of real world Again, generating random roads can be done in many ways generate vertical and horizontal roads or generate Voronoi tessellation on a set of random points in the given region Realistic geometry of real life artifacts such as roads, malls, and trails can only be generated by extracting the data from real world map Our software offers three mam ways of generating geometry (l) generate random geometry of vertical and horizontal roads, (a) generate geometry from real world map, and (m) combination of both - hist generating from real world map and then editing that either by adding or deleting artifacts 34 Minimum distance two roads Available wes to crease road SegrnenSs. - Figure 4 2 Vertical Roads 4 2.2 G e o m e t r y Generation by Vertical and Horizontal Roads The first step in creating combination of vertical and horizontal roads is to create vertical roads and then connect all the vertical roads through multiple connecting roads To create vertical road, system requires an input for maximum vertical roads and minimum gap between two consecutive vertical roads Based on the total sim- ulation width, system divides the simulation area into several horizontal segments, which is calculated as follows, horizontal segment width - simulation maximum width vertical roads System randomly chooses "x" point within the available area of each segment to draw a straight road from top to the bottom of simulation area Each segment has only one veitical road as lllustiatcd in figuie 4 2 Once the vertical roads are placed in the simulation region, multiple connecting roads are created between each vertical road We have implemented three types of connecting roads as illustrated in figure To create connecting roads, system 43 requires an input for maximum connecting roads and minimum distance between two consecutive connecting roads Based on the the total simulation height, system divides 35 (a) (b) (c) Figure 4 3 Connecting Roads the simulation area into several vertical segments, which is calculated as follows, vertical segment height - simulation height maximum connecting roads The system chooses any one of the three connecting roads randomly and then selects "y" point withm each segment to draw a connecting road in between two consecutive veitical loads Each segment has only one connecting load as illustiated in figuic 44 Available «ea to uette to id Minimum distant t» tWO MrMS Figure 4 4 Horizontal Roads The system also assigns a speed limit to each road from the range (vrmin - vrrna.r) and sets the road type as "residential" Both the speed limits and road type for each road segment can later be changed by the user 36 / Figure 4 5 OpenStreetMap GIS Data Export Tool 4 23 Geometry Generation from Real World M a p s Open Street Map (OSM) website [54] allows everyone to use geographical data free of cost from anywhere on earth and can be exported from the website as shown in figure 4 5 User can use the "Export" tab on the main map display to export the map image or raw data of a particular area By default the export engine takes the area of the map currently within view, however user can also manually select the rectangular area (bounding box) in the map It allows user to export data m following formats, • O p e n S t r e e t M a p X M L D a t a Allows export of the raw OpenStreetMap data in an XML format OpenStreetMap API retrieves the data of a bounding box region The XML data can be saved to a osm file and opened withm tools like JOSM Mapmk Image Allows export of PNG, JPEG, SVG, PDF, and PostScript maps m the OpenStreetMap Mapmk, Osmarender, Cycle Map, and NoName style Osmarender Image Allows export of a map image in the style produced by tiles@home (Osmarender) by using the MapOf service 37 • Embeddable H T M L Creates HTML code which can be embedded in any web page using zframe We have used OpenStreetMap XML Data to create geometry OpenStreetMap uses a topological data structure Nodes are points with a geographic position are lists of nodes, representing a polyline or polygon Ways Tags can be applied to nodes or ways and consist of tag-name = "value" pairs For example, Table 4 1 shows a sample file which we used to explain basic file structure Among various information in the osm file, the essential information is discussed below - minlat and minion at line 3 refers to the latitude and longitude of the starting point for the bounding region, whereas maxlat and maxlon at line 4 refers to the latitude and longitude of the ending point for the bounding region respectively - Line 5 to 8 contains the information about the point in a bounding region, whereas lat and Ion refers to latitude and longitude of that point There can be multiple points in an OSM file - "" tag in line 13 to 20 contains the information about the road or building depending upon the value m "" as shown in line 18 (in this case, it is a road of type "footway") "" tag as shown at line 16 and 17 contains the information of the points in a road or building There can be multiple ways in an OSM file In case of a road, first point is considered as starting point and last point is considered as ending point, whereas all points in between are considered as intermediate points in a road so that the precise data of the road curvature can be approximated by piecewise linear curve The osm file also contains information about load type, number of lanes, speed range, traffic direction flow building types, railway tracks water ways etc 38 1 2 3 8 9 12 13 16 17 18 19 20 21 Table 4 1 Open street map xml file ( osm) format 39 Road T y p e s The following listing defines the different road types available m OSM GIS data - track, - trunk, trunkjmk, - secondary, secondary Jink, - primary, primary Jink, - service, - motorway, motorway Jink, - tertiary, - footway, - unclassified, - path, - dnveway, - pedestrian, - road, - steps, - cycleway, and - residential For the simplification of the data we have combined trunk and trunk Jink as one road type (trunk) and the same is done with secondary, primary and motorway 40 4.3 Design RLMobiGen is capable of generating complex scenarios, in which the mobility behavior of all the nodes is dynamic, each node is capable of exhibiting different mobility behavior at different instance of time in the simulation The simulation parame- ters of RLMobiGen are simple, intuitive, yet their combination provides a powerful mechanism for simulating realistic mobility scenarios 431 Simulation Initializer Parameters These parameters state the basic simulation characteristics like simulation area, duration and boundary action simulation area is used to determine the distance between one point to another During the simulation the number of mobile nodes can increase, decrease or remain same based on the boundary action(i e Exit, Replace, and Enter &; Exit) In case of Enter & Exit selection, system takes input of Enter Sz Exit rate Simulation parameters are • Simulation area • Simulation start time • Simulation end time • Boundary action • Enter & Exit Rate 4 3.2 Road Parameters Road constitutes the gcometiy and can be extiacted from OSM XML file Each load is a five-tuple consisting of name, type, minimum and maximum speed and traffic flow direction Road parameters are 41 • Road name • Road type • Road mm speed • Road max speed • Road traffic flow Road name refers to the name of the road (1 e University Way, Davis road, etc ) Road type refers to type of the road (1 e Motorway, Freeway, etc ), multiple roads can have the same type the road Road mm speed (tvm,„) refers to the minimum speed of Road max speed (vrmax) refers to the maximum speed of the road User can assign a speed limit to each road that limits the node's own capability to move by adjusting its own speed un to the road speed range the direction, nodes can move on the road 1 e Road traffic flow refers to unidirectional (road is one-way) or bi-directional (road is two-way) GG parses the OSM file and automatically initializes all the roads with its attributes accordingly, that can later be changed by the user, if needed 4.3 3 Force Point Parameters Force points are the regions of interest that determine the possible destinations towards which mobile nodes can move Each force point is a nine-tuple consisting of x-y coordinates, type, availability and pause duration Force point parameters are • x-coordinate • y-coordinate • Type • Start time 42 • End time • Minimum pause time • Maximum pause time • Minimum speed • Maximum speed Type refers to the type of force point (1 e restaurant, educational building, fuel station, etc ) Multiple force points can have the same type Start time refers to the time from where onwards, force point can be accessible End time refers to the time till which force point is accessible Minimum pause time (tmin) refers to the minimum pause time a mobile node can stay after reaching at the force point Maximum pause time (tmm) refers to the maximum pause time a mobile node can stay after reaching at the force point On reaching the force point, node pauses for time t, chosen uniformly from (tmin, tmax) Force point can also move at the speed chosen from the range of minimum speed and maximum speed Minimum speed and maximum speed is set to zero, if force point is stationary Foice point can be attached to a node carrier with a force value which identifies the force point as attraction point, obstacle and repulsion point as mentioned below • -100 to -1 (attraction point) • 0 (obstacle) • 1 to 100 (repulsion point) Force value also determines the probability of a force point been selected as a potential destination One force point can act simultaneously as attraction point for one class of node and repulsion point for the other class of node 43 4.3.4 Intersection Parameters An intersection can have any one of the following two properties, • Traffic lights • Stop sign Traffic Lights refers to red, yellow and green signal, where node stops at red light and moves on green light System captures green light time duration for individual intersections and simulates the traffic light for each individual road of the intersection using round-robin scheduling algorithm Stop Sign refers to the point where node comes to complete stop and then proceed towards its desired destination 4.3.5 Node Carrier Parameters Each node carrier is a eight-tuple consisting of category, type, speed, rate of change in speed, allowed road types and population Node carrier parameters are • Node Category • Node Type • NC Mm Speed • NC Max Speed • Acceleration Rate • Deceleiation Rate • Allowed Road Types • Total Nodes Node category refers to the transporter of the node fiorn the picdefincd list of following six values, 44 User selects node category (1) bicycle (n) bus (m) car (IV) motorcycle (v) pedestrian (vi) taxi Node type is a user supplied value to differentiate between multiple node categories, multiple node carrier can have the same category (e g mobile phone of young pedestrian, mobile phone of old pedestrian, etc ) NC minimum speed (vnm7n) refers to minimum speed a node carrier can travel NC maximum speed (vnma:c) refers to maximum speed a node carrier can travel irrespective of road maximum speed (vTma:c) For example, maximum allowed speed for cars in downtown is 50 km/h but car has capability to travel at 100 km/h The movement of each node carrier is restricted to the road it is moving on and the speed rules apply to node carrier % as mentioned in Table 4 2 Node carnei adjusts the speed based on acceleration or deceleration late We must have vmin < v^t) < vmax at any time t if vn < vT J ""rmn — ' mm min ~ v u — Vnmax v max "•max > vr and vn ' min. iimaj: < vr — then ' rnox rm,n otherwise if vn TtXXTh ^max and vn > vr and vn < vr and vn > vr then '^mtn - v rmax otherwise Umin ~ ^ n m t n 'Umax — 'Urima.x Table 4 2 Node Carrier's Speed Range Selection to achieve desired speed A node moves only on the allowed roads, selected by the 45 user User may select more than one road type for a particular node carrier Multiple mobile nodes can be generated having same features of a particular node carrier 4.3.6 Node P a r a m e t e r s Mobile node inherits mobility features from its node carrier However the transmission range is not dependent on the mobility, rather two or more mobile nodes with same mobility features can have different transmission langes Node s transmission range is a user supplied non-negative value which determines the distance a mobile node can transmit the data 4.4 Implementation We used Java Swing and AWT package with the help of NetBeans IDE to build the graphical user interface (GUI) for RLMobiGen 4 4.1 User Interface Heie, we present snapshots of the RLMobiGen graphical user interface (GUI) Building a useful and attractive interface is a complex task GUI of RLMobiGen is organized as hierarchical panels • G e o m e t r y E d i t o r p a n e l (figure 4 6) Allows user to generate and edit geometry • Configure S i m u l a t i o n p a n e l (figure 4 7) Allows user to set simulation, node class and force point configuration • A n i m a t i o n p a n e l (figure 4 8) Traces animation Animation panel provides following subpanels to see the performance metrics and visualize the scenarios 46 Figure 4 6 Geometry Editor Panel & ft£Mab4£!&R £tea3ivti£ tv&d&)tiW&&f»«ei4i? iftd ftj^fc^^^^^^^^^^^^w^^K ^^^^S^^^fP^J^^^^,7| S(nj!aSuTLo!ifigi,retiM SfmufiitKusAH*a UJW* f $%,hm Bi«aSsn A»aMt<»S>.»i PCfllj idi> t i T i 5¥ t !i Unified Strews iraflvwsmt i R w p 1J pLtledwi TQt3lHutJ*»s 13 " ^ I t£ 1 S f orre Pom " o f figuratijr FoicsPoiHJTvpe ff»te » (t»r a * i a t e Add 1 fit •" [ 0 , fclp,,,^ U Rmr-p f i.y-i= 0 Re*. 1 ! "i 0 f 3 foU>t Haite<« 1ft Figure 4 7 Simulation Configuration Panel 47 f&Kk*<$!rt 8«i&&$9 Uuocfc Ge3mel!n Edrtar G^iwrste Hu&iift? Ajssiiisttua Pd i d iftdftfidsai SiBt \ $c«4i3fwj Stat Expert Trare Sternwarf f lusfcwrt fcf xifina ic Paiei a, vssufctt Mat . SC«(dl(L S.!P( £*{.jtt fl^L -b e-jsr W*wTnS^ rate = *! * • * **1 *jrwnary tr-siar>Ur1WmaJiw o. -5 l l j ' . K f * irstC ~ se wee £ - - 1 - sr- r •= 1 ^L. i t- J 4 - s o r ^ ^ f fc lr » 1 J i*: to Toijf-et Nid tof Jus L«!3¥ U H _ IQ- *• S J f ad *}jn a Figure 4 9 Animation Panel with Trace 48 hj-j -Is** %a*sfeiCej) ^eafrtnt WbBlKf GenttsiAfsid AB%M( S &reu!stftw t i vmw« G t ' Uwnt-SfceBineififtifrfci j animation Panel Sutrmary *_tarllnf maton - e i « < . eu Figure 4 10 Animation Panel with Transmission Range iidwtduat Stat > Scenario Stat Export Trace ^overrent Trace For Kcde & •] g Summatj ¥saw Tsacsa J Instant Information j 114nioie"in 361S Sees 3E1 s V c s in motion C Sees id! ng € C ^ Average Speed M % km b Aith 3T0 23 5 lota* Drian^e " r a v e M 1 J1 Okm CoffmecJsras Info 1"4 csr^ect ^ r chsn^ec Has connecter i s O rc*d*s (t ' • H ) Peer! 1 | C^sy irtdirected 1 2 ' Conned For Dtscsnnect Dirsd__ H38 3E*3~ ~j 3-3 i~,£ h012 CSBJL ]6C3 7 1^81^ i test - J.EC 2C8<" » ' 4^ Cosioeeiting Info To a P&ar Node ~ype r s r o c s eme-nts 2793 Average Speed €0 & k 11lr ^veiage ^loE on ^me 3523 S pecs A-iemga Tra^e sd Distance 155$ S m WihSdev 28 €2 Average idle Fate S 0 CoanectMty Info I 0K I Total number of Cc inectior Changes 631 rses Average Pe Se3«.ton Duatson 203 S sees Aw age Patn Duration 5$3 8 sees '12 8 ' of the totai o~enaro ttn e) M e age Lint Duration 2S79se^s ^?3 of I w tctal scenario time, Average Path Ava abl > 44 ~?-' Figure 4 12 Scenerio Stat subpanel lndi"rdaa! Stat ! Scenario Stat |flS_2 __ Snjje_fi s«t>„b1'i00 Export TracsT] _ Jjs^ Genenate snjjc„u .otf_' :ooo SIlOdM o s»tZ i 0 ->njd>>_ 1 =et>_401 0C iittOiP 1 -et7_0 i Snt_ at 3 03 Srudd J O , softest 513 00 559 00 3 24 3ns_ i l 12 42 Siio*MQ> s-tdest 5UU 03 553 00 0 33 3ns„ it 26 34 Jnode_iOi s°t-set<*e) set X_ $node_() set Y_ $node_() set Z_ and the future destinations of the mobile node is set by the following command, $ns_ at