Transcript Mobility Models and Traces

Mobility Models and Traces
Wei-jen Hsu
Advised by Dr. Ahmed Helmy
Presented in CIS6930 class, Spring 2008
Outline
• Simulation of user mobility
– Within NS-2
– As a stand-alone code
• Traces from existing wireless networks
Simulation of User Mobility
• Why?
– Mobile ad hoc networks are still not widely
deployed, even though a lot of research has
been done.
– But it is a fundamental factor that influences
network protocol performance.
– Use simulation as a way to perform
experiments in a controlled environment.
Simulation of User Mobility
• How?
– Use existing network simulation tools (e.g.,
NS-2) with extensions to handle user mobility.
– Build you tool from scratch.
Simulation of User Mobility
• How to choose a suitable approach?
– NS-2
• Powerful simulation tool, with many existing
protocols implemented for it.
• Hence complex, with high overhead
• You have to fit your idea into its structure
– You own tool
• You can do anything you want, focusing on the
part that matters to you
• Clean-slate implementation
• You have to re-build everything; credibility
Simulation of User Mobility
• What do you want from the simulation?
– Mobility metrics or statistics for the mobility
model
– Performance of routing protocols under the
mobility model
NS-2 Mobility Interface
Protocol performance
Mobility metric
Mobility
generator
Protocol
Simulation
(NS)
NS trace file format
Ns-2 Mobility file format
• Mobility trace file
– Format (the line you need to instruct how a
node moves):
• $ns_ at <time> “$node_(<id>) setdest <x> <y>
<speed>”
– Example:
$ns_ at 0.000000 "$MN2 setdest 610.107730
230.884732 40.608997“
– Why is this format chosen??
Ns-2 Mobility file format
Ns-2 Mobility file format
• NS provides only linear movement
• What if I want a movement trajectory of
arbitrary curve?
B(t1)
A(t0)
Plugging scenario files into NS
• It’s simple, just add these lines in your tcl
script
– Create tcl variables for file location
• set val(cp) "../mobility/scene/cbr-3-test"
• set val(sc) "../mobility/scene/scen-3-test"
– Include these files in simulation
• source $val(cp)
• source $val(sc)
How do I generate these files?
• Default mobility file generator is RWP
model.
/indep-utils/cmu-scen-gen/setdest/setdest
• Default traffic file generator is “random
UDP flows”
/indep-utils/cmu-scen-gen/cbrgen.tcl
• Use IMPORTANT tool to generate more
complex mobility scenario
• Or… Write your own stand alone code!
How to use IMPORTANT tool?
• Remember that it is a stand-alone
program, with nothing to do with NS
except that it’s output scenario files are
NS-compatible.
• So understand the program, compile it,
provide parameters you want, and run it!

What mobility models does
IMPORTANT tool provide?
Application
Temporal
Dependence
Spatial
Dependence
Geographic
Restriction
Random
Waypoint
Model
General
No
No
No
Group
Mobility
Model
Battlefield
No
Yes
No
Metropolitan
Traffic
Yes
Yes
Yes
Metropolitan
Traffic
Yes
No
Yes
Freeway
Mobility
Model
Manhattan
Mobility
Model
Random waypoint
• Random Waypoint Model
– 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
– After this duration, it again chooses a random
destination and repeats the whole process again until
the simulation ends
– Parameters: Max Velocity Vmax, Pause time T
Setdest utility
• Format
–
–
–
–
$node(<id>) set X_ <x0>
$node(<id>) set Y_ <y0>
$node(<id>) set Z_ <z0>
$ns_ at <time> “$node_(<id>) setdest <x> <y>
<speed>”
• Command
– ./setdest –n <num_of_nodes> -p <pause_time> -M
<max_speed> -t <simu_time> -x <max_x> -y
<max_y> > <trace_filename>
Reference Point Group Mobility
• Reference Point Group Model
– Each group has a logical center (group leader) that
determines the group’s motion behavior
– Each nodes within group has a speed and direction
that is derived by randomly deviating from that of the
group leader


| Vmember (t ) |  | Vleader (t ) |  random()  SDR  max_ speed
 member (t )  leader (t )  random()  ADR  max_ angle
– Parameter:
• Angle Deviation Ratio(ADR) and Speed Deviation
Ratio(SDR)
• Max_velocity
Group Mobility Generator
• In simulation, we use two sets
of trace files
– Single group: all nodes move within
one group
– Multiple group: each group moves
independent of each other and in an
overlapping fashion
SG
• Input
– Mobility trace file of group
leaders
• Output
– Mobility trace file of all nodes
MG
Freeway Model
• Freeway Model
– 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
Implementation
• Parameters
– Map and Max_velocity
• Input: map format
– <freeway id> <lane id> <x0,y0>
<x1,y1>
• Output
– Trace file for all nodes
• Key
– Link list to maintain the order of
nodes on the same lane
– Randomly insert the nodes into
various lane
Manhattan Model
• Similar specification with freeway, but it allows
node to make turns at each corner of street
• At each intersection
– Probability of moving on the same street is 0.5
– Probability of turning right is 0.25
– Probability of turning left is 0.25
• Parameter
– Map
– Max_velocity
Manhattan Map
• Input: map
– Street: <street_id> <lane_id> <direction> <x0,y0>
<x1,y1>
– Corner: <ver_str_id> <hrn_str_id> <x,y>
Time-Variant Community Model
• Available at
http://nile.cise.ufl.edu/~w
eijenhs/TVC_model/
– User manual and mobility
trace generator.
– It generates mobility trace
in 2 formats – NS-2 format
and (x, y, t) format
– You can configure the time
period structure and
communities for each node
with full freedom
TP1
TP2 TP3
TP1
TP2 TP3
Time
Repetitive time period structure
Time period 1 (TP1)
C o m m 11
Time period 2 (TP2)
Time period 3 (TP3)
C o m m 13
C o m m 21
C o m m 22 C o m m 1
C o m m 23
2
C o m m 33
C o m m 31
C o m m 43
Issues with Mobility Models
• Open network v.s. closed network
– Each node has an ID, there is a given number
of nodes, and they don’t leave the simulation
area
• This does not really capture the dynamics for a
highly given environment
– Potential solution: the “black hole”
• Take care of the dynamics, but it is
still the same node
– Reuse the same node for a
different virtual ID?
Issues with Mobility Models
• Boundary Effects
– The boundary can be
also “torus” or “reflective”
• Torus is unrealistic but
analytically nice. Reflective is more realistic.
• You need to make decisions on all these
small things in the mobility model!!
Traces
• Why traces?
– A realistic measurement of user’s behavior in
wireless networks
– For example, “re-play” the trace as a mobility
input for users in the simulation
– Note this is a very different approach from
mobility modeling (philosophy and granularity)
Where to get the traces?
• Collect it yourself
– Sniffers, bluetooth encounters, etc.
• Monitor the existing infrastructure
– WLANs? Cellular phone networks? Internet
traffic?
• Go to the trace archives
– http://nile.cise.ufl.edu/MobiLib/
– http://crawdad.cs.dartmouth.edu/
The UF WLAN Trace
• Collected from the on-campus WLAN in
UF, at two different levels
– Access points report syslogs
– Authentication servers report syslogs
• The trace is being uploaded to our server
in the lab at almost “real time”
Access Points Syslogs
• Users are reported by MAC addresses
– When they associate with a AP
– When they disaccosiate from a AP
– When they roam away from a AP
– When some other event happens (error in
packet checksum, max retry for a packet
reached, etc.)
Authentication server syslogs
• The authentication server reports the
following events
– DHCP lease – IP xxx is given to MAC yyy
– User log in – User Gatorlink-ID logs in from
MAC yyy
– User log out – User Gatorlink-ID logs out, and it
has been online for time ttt, sent/received bbb
bytes
– Every 30 minutes, each online user is reported
for its traffic usage in the past 30 mins
What is new?
• The differentiation of “having the intention
to use wireless network” v.s. “just turning
on the computer”
• The capability to analyze the data at
“device level (MAC address)” and “user
level (Gatorlink ID)”
• Getting the trace at “almost real time”
• Traffic summary with location information
Other Popular WLAN traces
• USC trace
– Collected from summer 2005 to today
– Time/location information of the user
(association) at switch port level. The
mapping between switch port and building is
available but messy (changing a lot)
• Dartmouth trace
– Collected from 2001 to 2004
– Time/location information of user, SNMP logs
from access points, tcpdump traffic headers
Other Popular WLAN traces
• UCSD – PDA experiment
– ~275 PDA users
– Time/location information, each PDA logs all
APs in communication range
• MIT/IBM
– Corporate users from 3 buildings
– Time/location information, SNMP logs
Traces of Other Types
• Encounter traces
– The Intel/Cambridge Haggle/Pocket Switch
Network project
– The U of Toronto PDA-based encounter
experiments
• Cellphone traces
– MIT Reality Mining: encounter, location of
users (by cellphone tower/bluetooth), call log
Usage of the Traces
• To understand existing systems (WLANs)
– How, when, where do users use WLAN?
– Can users be classified based on their behaviors?
– Can we build models of users?
• To leverage it as a ground for not-yet-deployed
services/protocols
– IF users behave like this, what if we do….
– IF users continue to develop a trend, where will we be
in year 201X?
Final Notes
• Downside of trace-based work
– Unable to access the ground truth
– Using the current user data to speculate the future
– We have plenty data sets for the normal scenarios,
but should they be the focus?
• Concerns
– Privacy
– What’s a real-world application that can’t be done with
today’s the great Internet?
Potential Directions
• Combing the trace with small-scale
experiments
• Build new testbeds and prototype new
services
• Come up with a specific scenario to
provide solutions for
• Challenge the established knowledge
Tricks of Trace Processing
• Identify a common format that you can convert
multiple traces into
– I use one file for each user, within each file, each line
represents “time location duration”
• Abuse your hard drive
– Keep intermediate results if they take long time to
generate.... You will thank your former self years after
you generated those files
• Learn handy tools
– Shell script, perl, database (Udayan’s turn)