Ahmed Helmy

Please download to get full document.

View again

of 81
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 2 | Pages: 81

Extension: PPT | Download: 0

Related documents
For example, RWP model, Vmax=30m/s, RS=12.6m/s, Dspatial=0.03. 27. Connectivity Graph Metrics ... For SG/MG, strong degree of spatial dependence ...
Title: Ahmed Helmy 1 TutorialMobility Modeling for Future Mobile Network Design and Simulation
  • Ahmed Helmy
  • Computer and Information Science and Engineering (CISE)
  • College of Engineering
  • University of Florida
  • helmy_at_ufl.edu , http//www.cise.ufl.edu/helmy
  • Founder and Director
  • Wireless Mobile Networking Lab http//nile.cise.uf l.edu
  • Founder of the NOMADS research group
  • (Affiliated with Electrical Engineering Departments at UF and USC)
  • 2 Outline
  • Mobile Ad Hoc Networks Mobility Classification
  • Synthetic and Trace-based Mobility Models
  • The Need for Systematic Mobility Framework
  • Survey of the Major Mobility Models
  • Random models - Group mobility models Vehicular (Manhattan/Freeway) models - Obstacle models
  • Characterizing the Mobility Space
  • Mobility Dimensions (spatial and temporal dependency, geographic restrictions)
  • Mobility Metrics (spatio-temporal correlations, path and link duration)
  • 3 Outline (contd.)
  • Mobility-centric framework to analyze ad hoc networks
  • The IMPORTANT mobility framework
  • Case Studies BRICS, PATHS, MAID
  • Trace-based mobility modeling
  • Analyzing wireless network measurements and traces
  • The TVC model, and profile-cast
  • Mobility simulation and analysis tools
  • Software packages and tools
  • Resources and related projects
  • 4 Wireless Mobile Ad hoc Networks (MANETs)
  • A Mobile Ad hoc Network (MANET) is a collection of mobile devices forming a multi-hop wireless network with minimal (or no) infrastructure
  • To evaluate/study adhoc networks mobility and traffic patterns are two significant factors affecting protocol performance.
  • Wireless network performance evaluation uses
  • Mobility Patterns usually, uniformly and randomly chosen destinations (random waypoint model)
  • Traffic Patterns usually, uniformly and randomly chosen communicating nodes with long-lived connections
  • Impact of mobility on wireless networks and ad hoc routing protocols is significant
  • 5 Example Ad hoc Networks Mobile devices (laptop, PDAs) Vehicular Networks on Highways Hybrid urban ad hoc network (vehicular, pedestrian, hot spots,) 6 Classification of Mobility and Mobility Models I- Based on Controllability II- Based on Model Construction 7 Mobility Dimensions Classification of Synthetic Uncontrolled Mobility Models F. Bai, A. Helmy, "A Survey of Mobility Modeling and Analysis in Wireles Adhoc Networks", Book Chapter in the book "Wireless Ad Hoc and Sensor Networks, Kluwer Academic Publishers, June 2004. 8 I. Random Waypoint (RWP) Model
  • A node chooses a random destination anywhere in the network field
  • The node moves towards that destination with a velocity chosen randomly from 0, Vmax
  • After reaching the destination, the node stops for a duration defined by the pause time parameter.
  • This procedure is repeated until the simulation ends
  • Parameters Pause time T, max velocity Vmax
  • Comments
  • Speed decay problem, non-uniform node distribution
  • Variants random walk, random direction, smooth random, ...
  • 9 Random Way Point Basics 10 Random Way Point Example 11
  • 1- RWP leads to non-uniform distribution of nodes due to bias towards the center of the area, due to non-uniform direction selection. To remedy this the random direction mobility model can be chosen.
  • 2- Average speed decays over time due to nodes getting stuck at low speeds
  • 12 II. Random (RWK) Walk Model
  • Similar to RWP but
  • Nodes change their speed/direction every time slot
  • New direction ? is chosen randomly between (0,2?
  • New speed chosen from uniform (or Gaussian) distribution
  • When node reaches boundary it bounces back with (?-?)
  • 13 Random Walk 14 III. Reference Point Group Mobility (RPGM)
  • Nodes are divided into groups
  • Each group has a leader
  • The leaders mobility follows random way point
  • The members of the group follow the leaders mobility closely, with some deviation
  • Examples
  • Group tours, conferences, museum visits
  • Emergency crews, rescue teams
  • Military divisions/platoons
  • 15 Group Mobility Single Group 16 Group Mobility Multiple Groups 17 IV. Obstacle/Pathway Model
  • Obstacles/bldgs map
  • Nodes move on pathways between obstacles
  • Nodes may enter/exit buildings
  • Pathways constructed by computing Voronoi graph (i.e., pathways equidistant to nearby buildings)
  • Obstacles affect communication
  • Nodes on opposite sides (or in/outside) of a building cannot communicate
  • 18 V. Related Real-world Mobility Scenarios
  • Pedestrian Mobility
  • University or business campuses
  • Usually mixes group and RWP models, with obstacles and pathways
  • Vehicular Mobility
  • Urban streets (Manhattan-like)
  • Freeways
  • Restricted to streets, involves driving rules
  • 19 (No Transcript) 20 Streets - Manhattan Urban Street 21 Freeway Map 22 Motivation
  • Randomized models (e.g., random waypoint) do not capture
  • (I) Existence of geographic restriction (obstacles)
  • (II) Temporal dependence of node movement (correlation over history)
  • (III) Spatial dependence (correlation) of movement among nodes
  • A systematic framework is needed to investigate the impact of various mobility models on the performance of different routing protocols for MANETs
  • This study attempts to answer
  • What are key characteristics of the mobility space?
  • Which metrics can compare mobility models in a meaningful way?
  • Whether mobility matters? To what degree?
  • If the answer is yes, why? How?
  • Geographic Restriction Mobility Space Spatial Correlation Temporal Correlation 23 IMPORTANT A framework to systematically analyze the "Impact of Mobility on Performance Of RouTing in Ad-hoc NeTworks" Fan Bai, Narayanan Sadagopan, Ahmed Helmy fbai, nsadagop, helmy_at_usc.edu website http//nile.usc.edu/important F. Bai, N. Sadagopan, A. Helmy, "IMPORTANT A framework to systematically analyze the Impact of Mobility on Performance of RouTing protocols for Adhoc NeTworks", IEEE INFOCOM, pp. 825-835, April 2003. F. Bai, N. Sadagopan, A. Helmy, The IMPORTANT Framework for Analyzing the Impact of Mobility on Performance of Routing for Ad Hoc NetworksAdHoc Networks Journal - Elsevier Science, Vol. 1, Issue 4, pp. 383-403, November 2003. F. Bai, A. Helmy, "The IMPORTANT Framework for Analyzing and Modeling the Impact of Mobility in Wireless Adhoc Networks", Book Chapter in the book "Wireless Ad Hoc and Sensor Networks, Kluwer Academic Publishers, June 2004. 24 Framework Goals (Questions to Answer)
  • Whether mobility matters? and How much does it matter?
  • Rich set of mobility models that capture characteristics of different types of movement
  • Protocol independent metrics such as mobility metrics and connectivity graph metrics to capture the above characteristics
  • Why?
  • Analysis process to relate performance with a specific characteristic of mobility via connectivity metrics
  • How?
  • Systematic process to study the performance of protocol mechanistic building blocks (BRICS) across various mobility characteristics
  • 25 The IMPORTANT Framework Overview Routing Protocol Performance Mobility Models 26 Mobility Metrics
  • Relative Speed (mobility metric I)
  • The magnitude of relative speed of two nodes, averaged over all neighborhood pairs and all time
  • Spatial Dependence (mobility metric II)
  • The value of extent of similarity of the velocities/dir of two nodes that are not too far apart, averaged over all neighborhood pairs and all time
  • For example, RWP model, Vmax30m/s, RS12.6m/s, Dspatial0.03 27 Connectivity Graph Metrics
  • Average link duration (connectivity metric I)
  • The value of link duration, averaged over all nodes pairs
  • Link/Path duration distributions (PATHS study)
  • Protocol Performance Metrics
  • Throughput delivery ratio
  • Overhead number of routing control packets sent
  • 28 Mobility Models Summary Spatial Dependence Geographic Restriction Application Random Waypoint Model General (uncorrelated straight lines) No No Group Mobility Model No Yes Conventions, Campus Freeway Mobility Model Metropolitan Traffic/Vehicular Yes Yes Manhattan Mobility Model Urban Traffic/Vehicular No Yes 29 Parameterized Mobility Models
  • Random Waypoint Model (RWP)
  • Each node chooses a random destination and moves towards it with a random velocity chosen from 0, Vmax. After reaching the destination, the node stops for a duration defined by the pause time parameter. This procedure is repeated until simulation ends
  • Parameters Pause time T, max velocity Vmax
  • Reference Point Group Model (RPGM)
  • Each group has a logical center (group leader) that determines the groups motion behavior
  • Each nodes within group has a speed and direction that is derived by randomly deviating from that of the group leader
  • Parameters Angle Deviation Ratio(ADR) and Speed Deviation Ratio(SDR), number of groups, max velocity Vmax. In our study, ADRSDR0.1
  • In our study, we use two scenarios Single Group (SG) and Multiple Group (MG)
  • 30 Parameterized Mobility Models
  • Freeway Model (FW)
  • Each mobile node is restricted to its lane on the freeway
  • The velocity of mobile node is temporally dependent on its previous velocity
  • If two mobile nodes on the same freeway lane are within the Safety Distance (SD), the velocity of the following node cannot exceed the velocity of preceding node
  • Parameter Map layout, Vmax
  • Manhattan Model (MH)
  • Similar to Freeway model, but it allows node to make turns at each corner of street
  • Parameter Map layout, Vmax
  • Map for FW Map for MH 31 Experiment I Analysis of mobility characteristics
  • IMPORTANT mobility tool
  • integrated with NS-2 (released Jan 04, Aug 05)
  • http//nile.cise.ufl.edu/important
  • Simulation done using our mobility generator and analyzer
  • Number of nodes(N) 40, Simulation Time(T) 900 sec
  • Area 1000m x 1000m
  • Vmax set to 1,5,10,20,30,40,50,60 m/sec across simulations
  • RWP, pause time T0
  • SG/MG, ADR0.1, SDR0.1
  • FW/MH, map layout in the previous slide
  • 32 Mobility metrics
  • Objective
  • validate whether proposed mobility models span the mobility space we explore
  • Relative speed
  • For same Vmax, MH/FW is higher than RWP, which is higher than SG/MG
  • Spatial dependence
  • For SG/MG, strong degree of spatial dependence
  • For RWP/FW/MH, no obvious spatial dependence is observed
  • Relative Speed Spatial Dependence 33 Connectivity Graph Metrics Link duration
  • Link duration
  • For same Vmax, SG/MG is higher than RWP, which is higher than FW, which is higher than MH
  • Summary
  • Freeway and Manhattan model exhibits a high relative speed
  • Spatial Dependence for group mobility is high, while it is low for random waypoint and other models
  • Link Duration for group mobility is higher than Freeway, Manhattan and random waypoint
  • Path duration - Similar observations for Path duration 34 Experiment II Protocol Performance across Mobility Models
  • Simulations done in ns-2
  • Routing protocols DSR, AODV, DSDV
  • Same set of mobility trace files used in experiment1
  • Traffic pattern consists of source-destination pairs chosen at random
  • 20 source, 30 connections, CBR traffic
  • Data rate is 4packets/sec (low data rate to avoid congestion)
  • For each mobility trace file, we vary traffic patterns and run the simulations for 3 times
  • 35 Results and Observations
  • Performance of routing protocols may vary drastically across mobility patterns (Example for DSR)
  • There is a difference of 40 for throughput and an order of magnitude difference for routing overhead across mobility models!
  • Throughput Routing Overhead 36 Which Protocol Has the Highest Throughput ?
  • We observe that using different mobility models may alter the ranking of protocols in terms of the throughput!
  • Manhattan AODV ! Random Waypoint DSR 37 Which Protocol Has the Lowest Overhead ?
  • We observe that using different mobility models may alter the ranking of protocols in terms of the routing overhead!
  • Recall Whether mobility impacts protocol performance?
  • Conclusion Mobility DOES matter, significantly, in evaluation of protocol performance and in comparison of various protocols!
  • RPGM(single group) DSR Manhattan DSDV 38 Putting the Pieces Together
  • Why does mobility affect protocol performance?
  • We observe a very clear trend between mobility metric, connectivity and performance
  • With similar average spatial dependency
  • Relative Speed increases? Link Duration decreases? Routing Overhead increases and throughput decreases
  • With similar average relative speed
  • Spatial Dependence increase ?Link Duration increases?Throughput increases and routing overhead decreases
  • Conclusion Mobility Metrics influence Connectivity Metrics which in turn influence protocol performance metrics !
  • 39 Putting the Pieces Together Relative Velocity Link Duration Throughput Spatial Dependence Path Duration Overhead 40 Mechanistic Building Blocks (BRICS)
  • How does mobility affect the protocol performance?
  • Approach
  • The protocol is decomposed into its constituent mechanistic, parameterized building block, each implements a well-defined functionality
  • Various protocols choose different parameter settings for the same building block. For a specific mobility scenario, the building block with different parameters behaves differently, affecting the performance of the protocol
  • We are interested in the contribution of building blocks to the overall performance in the face of mobility
  • Case study
  • Reactive protocols (e.g., DSR and AODV)
  • F. Bai, N. Sadagopan, A. Helmy, "BRICS A Building-block approach for analyzing RoutIng protoCols in Ad Hoc Networks - A Case Study of Reactive Routing Protocols", IEEE International Conference on Communications (ICC), June 2004. 41 Building Block Diagram for reactive protocols 42 How useful is caching? AODV DSR
  • In RW, FW and MH model, most of route replies come from the cache, rather than destination (gt80 for DSR, gt60 for AODV in most cases)
  • The difference in the route replies coming from cache between DSR and AODV is greater than 20 for all mobility models, maybe because of caching mode
  • 43 Is aggressive caching always good? DSR
  • The invalid cached routes increase from RPGM to RW to FW to MH mobility models
  • Aggressive Caching may have adverse effect at high mobility scenarios!
  • 44 Conclusions
  • Mobility patterns are very IMPORTANT in evaluating performance of ad hoc networks
  • A rich set of mobility models is needed for a good evaluation framework.
  • Richness of those models should be evaluated using quantitative mobility metrics.
  • Observation
  • In the previous study only average link duration was considered.
  • Are we missing something by looking only at averages?
  • Next We conduct the PATHS study to investigate statistics and distribution of link and path duration.
  • 45 PATHS Analysis of PATH Duration Statistics and their Impact on Reactive MANET Routing Protocols
  • Fan Bai, Narayanan Sadagopan,
  • Bhaskar Krishnamachari, Ahmed Helmy
  • fbai, nsadagop, brksihna, helmy_at_usc.edu
  • F. Bai, N. Sadagopan, B. Krishnamachari, A. Helmy, "Modeling Path Duration Distributions in MANETs and their Impact on Routing Performance", IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Quality of Service in Variable Topology Networks, Vol. 22, No. 7, pp. 1357-1373, Sept 2004.
  • N. Sadagopan, F. Bai, B. Krishnamachari, A. Helmy, "PATHS analysis of PATH duration Statistics and their impact on reactive MANET routing protocols", ACM MobiHoc, pp. 245-256, June 2003.
  • 46 Motivation and Goal
  • Mobility affects connectivity (i.e., links), and in turn protocol mechanisms and performance
  • It is essential to understanding effects of mobility on link and path characteristics
  • In this study
  • Closer look at the mobility effects on connectivity metrics (statistics of link duration (LD) and path duration (PD))
  • Develop approximate expressions for LD PD distributions (Is it really exponential? When is it exponential?)
  • Develop first order models for Tput Overhead as f(PD)
  • Protocol Mechanisms Performance (Throughput, Overhead) Mobility Connectivity 47 Connectivity Metrics
  • Link Duration (LD)
  • For nodes i,j, the durat
  • We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks

    We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

    More details...

    Sign Now!

    We are very appreciated for your Prompt Action!