Identifying the Intertwined Links between Mobility and ...

ROUTING IN OPPORTUNISTIC NETWORKS Chapter 1: Identifying the Intertwined Links between Mobility and Routing in Opportunistic Networks Xiaoyan Hong Bo Gu University of Alabama University of Alabama 1 Outline Introduction Mobility models Mobility characteristics Routing protocols Future directions Summary University of Alabama

2 MOTIVATION Mobility intertwines with routing protocols to play a vital role in opportunistic networks Mobility properties are utilized by routing protocols to improve performance Study on mobility models, analytical results on motion characteristics and routing strategies will help developing novel integrated mobility and message dissemination solutions for opportunistic networks University of Alabama 3 INTRODUCTION Present a survey over mobility models, analytical results on motion characteristics and routing strategies Mobility models are the evaluation tools for routing protocols and the sources for movement pattern analysis Analytical results contribute to new mobility models

with increased exibility in reproducing desired network scenarios Routing protocols can make use of underlying mobile topological structures from results of mobility analysis University of Alabama 4 Intertwined Three Components Motion Characteristics Spatial properties University of Alabama 5 A n al ys i

s ng no map, no intention w map, no intention no map, w intention w map, w intention i ut ro Mobility Models t m

Graph properties is ss A ew N Temporal properties el d o Routing Protocols Proactive routing Evaluation Reactive routing -contact based -community based -auxiliary node

based Outline: Mobility Models Motion Characteristics New model Mobility Models Temporal properties Analysis no map, no intention Graph properties Assist routing w map, no intention no map, w intention w map, w intention

University of Alabama Spatial properties Routing Protocols Proactive routing Evaluation 6 Reactive routing -contact based -community based -auxiliary node based MOBILITY MODELS Movements are most likely the explicit or implicit results of their social or personal activities. Physical locations Social intentions Classifications

Non-Map Without-Intention Models Map Without-Intention Models Non-Map With-Intention Models Map With-Intention Models University of Alabama 7 Non-Map Without-Intention Models Attributes: no restrictions on paths nor intention of movement Basic model Random Walk Model [8]: Memoryless Random Waypoint Model [28]: Delay factor to simulate pauses Random Direction Mobility Model[43]: Additionally deal with the movements when hitting simulation boundary Realistic model

Gauss-Markov Mobility Model [30]: Simulate the acceleration and deceleration Heterogeneous Random Walk[40]: Simulate the clustered network University of Alabama 8 Map Without-Intention Models Attributes: movements are restricted to physical world paths. Freeway model[1]: Vertical and horizontal tracks of freeway City block[14]: Street grid Street Random Waypoint mobility model[11]: Considering the intra-segment mobility and intersegment mobility on street grid Vehicular network model[44]: Stop signs, timed traffic lights and control on next road University of Alabama 9

Non-Map With-Intention Models Attributes: No path restriction With individual or shared movement intentions Group based model Reference Point Group Mobility Model (RPGM)[22]: paths of nodes in the same group following the movement of the group leader Interaction-based mobility model[34]: characterizes the formation and disaggregation of hot spots at random times and locations Community based model Community based mobility model[35]: Captures the feature that a number of hosts are grouped together Community model with cyclic pattern[54]: defines the repeating time period to model re-visits to the same locations University of Alabama 10 Map With-Intention Models

Attributes Realistic features such as moving along paths and with intentions Trace based model Bus traces[2], GPS trace[9], WLAN trace[51], Trace in campus [23] Agenda Driven Mobility model[59]: use National Household Travel Survey (NHTS) data to synthesize each nodes agenda, which derives its mobility of when, where and what (pause time) Graph-based model Area Graph based mobility model[4]: A directed and weighted graph to model locations and paths between locations Levy walk based model Heavy-tail distribution[41]: movement increment is distributed according to a heavy-tail distribution University of Alabama 11

Summary of the Models Trend of mobility modeling has moved towards more realistic by taking considerations of both social intentions and geographical features Artificially consider social interaction and attraction Analyzing real world traces WLAN associations give hits on mobility Impact Effective evaluation tools Play an important role for message forwarding in opportunistic networks University of Alabama 12 Outline: Mobility Characteristics Motion Characteristics Spatial properties no map, no intention w map,

no intention no map, w intention w map, w intention University of Alabama 13 An a ly si s N ew Mobility Models g

in ut ro m Graph properties t is ss A od el Temporal properties Routing Protocols Proactive routing Evaluation Reactive routing

-contact based -community based -auxiliary node based MOBILITY CHARACTERISTICS Contribute to performance evaluation, simulation calibration, routings protocol design Classifications Characteristics of Flight Locality Distribution Temporal Characteristics Joint Spatial and Temporal Analysis Graph Characteristics University of Alabama 14

Characteristics of Flight Flight: the longest straight line trip from one location to another Flight length distribution can be heavy-tail, or exponential Flight reects the diffusivity of mobility Models with different diffusivity Random Waypoint model, Brownian Motion, Levy Walk model Impact Diffusive nodes are helpful for relaying messages to larger areas University of Alabama 15 Locality Distribution Different movement patterns lead to various spatial locality distributions Distributions can be uniform or heterogeneous Discussed models: Brownian-motion, Random Waypoint Model, Heterogeneous

Random Walk Impact Cluster based routing is suitable in networks with heterogeneous distribution University of Alabama 16 Temporal Characteristics Many properties have been analyzed: encounter frequency, pause time, hitting time, meeting time, inter-contact time, filling time, scattering time Impact Encounter history matters for choosing next forwarder Pause time, hitting time, meeting time, inter-contact time are useful in estimating message delay and delivery rate Filling time and scattering time describe the dynamics of hot spots, can be useful for cluster-based routing University of Alabama

17 Joint Spatial and Temporal Analysis Time and space are closely related in mobility Trajectory similarity: Compute similarity using a set of metrics including Euclidean distance, etc. Discussed models: Vehicular model[29], Mobyspace [27], location based time-dependent link analysis[20] [21] Impact Routing uses clusters or high similarity nodes Help to identify popular locations in mobile networks and trajectory segments Calculate communication latency University of Alabama 18 Graph Characteristics Using graph properties to identify mobility patterns Centrality [17] Degree centrality, closeness centrality, betweenness centrality Social networks

k-clique community, network connectivity Discussed models: Clique community[25], Continuum framework [10] Impact Node with higher centrality as forwarder, community helps to group mobile nodes, connectivity analysis University of Alabama 19 Summary: Characteristic Analysis (I) Categories Mobility Characteristics Features for Routing Flight Length Longest straight line trip from one location to next location; node

diffusivity Message forwarder adopts high diffusive nodes for fast dissemination Locality Distribution Distribution of node positions during moving process is either uniform or heterogeneous Cluster based routing is suitable in networks with heterogeneous distribution Temporal Characteristics Encounter frequency,

pause time, hitting time, meeting time, inter-contact time, filling time, scattering time Encounter history for choosing next forwarder; Estimating message delay and delivery rate University of Alabama 20 Summary: Characteristic Analysis(II) Categories Mobility Characteristics Features for Routing Joint SpatialTemporal

Time and location relationships of groups, trajectory similarity Routing uses clusters or nodes with high similarity Graph Characteristics Degree centrality, closeness centrality, betweenness centrality, k-clique community Nodes with higher centrality as forwarder; community helps to group mobile nodes; connectivity analysis and evolution for performance

University of Alabama 21 Outline: Routing Protocols Motion Characteristics Spatial properties Temporal properties Assist ro uting Analysis New model Graph properties Mobility Models no map, no intention w map,

no intention no map, w intention w map, w intention University of Alabama 22 n Evaluatio Routing Protocols Proactive routing Reactive routing -contact based -community based -auxiliary node based

ROUTING STRATEGIES Routing principle: store-carry-forward Classifications: Proactive Routing: with centralized or off-line knowledge about network Reactive Routing: without a global or predetermined knowledge Contact based routing: forward messages using the encounter history Community based routing: identify and rely on various clusters Auxiliary node based routing: introduce mobile or static message ferries University of Alabama 23 Proactive Routing knowledge such as contacts history, queuing length and traffic demands Use a graph with time-varying delay and capacity Discussed protocols: Framework of DTN routing which takes different levels of network knowledge [26]

Treat routing as a resource allocation problem[2] Link with contact probability calculated from cyclic movement pattern [32] Routing assisted by static relay nodes deployed at critical locations for cyclic movement pattern[19] Mobyspace with the assumption of full network knowledge [27] University of Alabama 24 Reactive: Contact based routing Forwarding decision is made when two nodes encounter each other Discussed protocols Epidemic routing [52]: forward to each contact PROPHET: employ a probabilistic metric called delivery predictability [31] Spray and Wait protocol: broadcasts only a fixed number of copies of message [49] Seek and Focus protocol: hybrid protocol which includes utilitybased routing and randomized routing [49] University of Alabama

25 Reactive: Community based routing Identify and use a special group of nodes Better sociability Frequent contacts with the destinations Attached to a hot location Discussed Protocols Distributed method to identify central nodes[13] Multicast routing [18] Island Hopping [46] Connected dominating set for VANET [33] University of Alabama 26 Reactive: Auxiliary node based

routing Introduce nodes specially designed for message relay, either mobile or static Discussed routing Auxiliary node with Levy Walk pattern[47] Levy Walk searching[53] Mobile message ferry[57] Static throw box[58] University of Alabama 27 Summary: Routing Protocols Relationships among routing strategies, mobility models and their characteristics TABLE II and TABLE III summarize the following

Categories Routing protocols Main routing strategies Mobility models and features Applicable environments University of Alabama 28 FUTURE DIRECTIONS Social network related analysis and its connection to opportunistic networks Movements within a real road system Novel message dissemination schemes that explore new social network properties Management of opportunistic networks, examples include extending coverage, capacity and traffic aggregation

University of Alabama 29 CHAPTER SUMMARY This chapter presents a survey over mobility models, analytical results on motion characteristics, and routing strategies that largely rely on mobility in opportunistic networks More important, it provides a systematical overview and identifies the intertwining connections among the three areas. University of Alabama 30 CHAPTER SUMMARY Applications of Opportunistic Networks Comm. support Routing Schemes

Mobility assistance Evaluation Mobility Characteristics Abstraction Movement Patterns University of Alabama 31 Gossipmule, content spreading in mobile social networks, opportunistic Internet access, rural area networks) Proactive routing, reactive routing (contact based, community based, auxiliary node based))) Flight, locality, temporal characteristics, joint spatial-temporal, graph features

Random walk, Manhattan Random Model, waypoint, Freeway model, Group Mobility Trace based model, model, Graph community based model, based model, Thanks for your attention! University of Alabama 32

Recently Viewed Presentations

  • Research in the International Finance and Macroeconomics ...

    Research in the International Finance and Macroeconomics ...

    Research more often has been sympathetic to a specific kind of capital control — Chile-style penalties on short-term capital inflows under the theory that they tilt the composition in favor of more stable long-term inflows. E.g., De Gregorio, Edwards, &...
  • Diapositive 1 - Des bâtons dans les roues

    Diapositive 1 - Des bâtons dans les roues

    La conception communique efficacement à l'utilisateur l'information nécessaire, quelles que soient les conditions ambiantes ou les capacités sensorielles de la personne. 4a. Utiliser différents modes (illustré, verbal, tactile) pour la présentation redondante de l'information essentielle. 4b.
  • Through the Eyes of the Client - Client Journey Experiential ...

    Through the Eyes of the Client - Client Journey Experiential ...

    "Through the Eyes of the Client" Client Journey Experiential Study ... the hospice in Golf Links Road were fabulous. Psych came to talk to us, husband came home, brought bed to house, nurses twice dailt. ... Boneo / Cape Schanck...
  • The Politics of Pay Reform - GSDRC

    The Politics of Pay Reform - GSDRC

    Corporatism Tactics and Techniques Models Predominantly driven by political pressures/exigencies Politically reactive (PRE) Measured consideration to political factors (explicit or implicit) Primacy of egalitarian concerns Politically rational (PRA) Neo-liberal economics and/or HRM orientation (ideal) Largely impervious to political pressures ...
  • The Second Teacher: Putting Classroom Walls to Work for You

    The Second Teacher: Putting Classroom Walls to Work for You

    www.onevoiceone.wikispaces.com. To access documents - double click on document. ... Posters or classroom displays may not be copied and moved to an alternative testing location which creates an artificial environment and may lead students to believe that they should use...
  • 5 Themes of Geography - Coach Tony Wolfe

    5 Themes of Geography - Coach Tony Wolfe

    Georgia is north of Florida, south of Tennessee, west of South Carolina, and East of Alabama. LOCATION. PLACE. What is it like? Physical Characteristics. Rivers, Lakes, Mountains, Valleys. ... Landform Regions. Agricultural Regions. How is the Mall of Georgia divided?...
  • PowerPoint Presentation

    PowerPoint Presentation

    NONVASCULAR AND SEEDLESS VASCULAR PLANTS Phylum Anthocerophyta (Hornworts) Phylum Hepaticophyta (Liverworts) Phylum Bryophyta (Mosses) Bryophytes- nonvascular; reproduce via spores, seedless plants; includes the mosses, liverworts, and hornworts Bryophytes Definition: - nonvascular plants (do not have specialized tissues that conduct water...
  • Hypertension and Stroke - Virginia Commonwealth University

    Hypertension and Stroke - Virginia Commonwealth University

    Hypertension and Stroke. Presented by: Carrie Miller, MPH. Ahmed Alquthami, MD, MHSA