Transcript Document

SWAN – A Simulator for
Wireless “Ad Hoc”
Networks
Luiz Felipe Perrone
[email protected]
Institute for Security Technology Studies
Dartmouth College
With Jason Liu, David Nicol and Michael Liljenstam
December 7, 2001
Colorado School of Mines
1
Wireless Ad-Hoc Networks
Battery operated
computing devices
Communication happens
via radio or laser beams
Nodes are free to move
Single or multihop
Automagic configuration
No need for infrastructure
December 7, 2001
Colorado School of Mines
2
An Application: Sensor networks
M
Intelligence,
Surveillance,
Emergency Response
M
December 7, 2001
Colorado School of Mines
3
Technology Challenges
Medium Access Control (MAC):
How do we coordinate multiple,
autonomous entities access to a
common portion of the communication
spectrum?
December 7, 2001
Colorado School of Mines
4
Technology Challenges
Routing:
How do we set up routing services for a
network with a potentially very large
number of nodes?
December 7, 2001
Colorado School of Mines
5
Technology Challenges
Security:
How do we give this network “nice”
properties such as availability,
confidentiality, integrity, authentication
and nonrepudiation?
December 7, 2001
Colorado School of Mines
6
Technology Challenges
Power awareness:
How do we do all this in a way so as to
minimize power consumption at each
node and maximize the network lifetime?
December 7, 2001
Colorado School of Mines
7
Who Needs Simulation?
We have a complex system that defies mathematical
analysis.
This system has several components tightly interconnected.
Experiments in validation and verification will call for
repeatability and controllability.
Again, who needs simulation?
We do!!!
December 7, 2001
Colorado School of Mines
8
Wish List for an WAN Simulator
Detail
Completeness
Performance
Scalability
December 7, 2001
Colorado School of Mines
9
Related Work
CMU: Monarch Project
http://www.monarch.cs.cmu.edu/cmu-ns.html
detailed radio propagation models, complete implementations of
MAC and routing algorithms, scenario generation, visualization
tools, network emulation, etc.
UCLA: SensorSim (pre-release stage)
http://nesl.ee.ucla.edu/projects/sensorsim/
sensing channel and sensor models, battery models, lightweight
protocol stacks for wireless microsensors, scenario generation,
and hybrid simulation.
Common major drawback: they are based on ns-2.
December 7, 2001
Colorado School of Mines
10
How We’re Making It Happen
We started out with the Scalable Simulation Framework (SSF)
http://www.ssfnet.org
Entity
container for state variables
outChannel
Process
SSF
endpoints of communication
links between entities
inChannel
entity’s state evolution
Event
messages between entities
SSF is not a simulator: it’s a specification with bindings for Java and C++.
December 7, 2001
Colorado School of Mines
11
SSF Modeling
Entity A
state
Entity B
outChannel
inChannel
state
Event
process
inChannel
outChannel
process
A.alignto(B)
Timeline
Channels have an associated delay which is used by the kernel to
determine lookahead for parallel simulation. Channels are mapped to
one another.
Obviously large models would be painful to construct with this
mechanism alone: enter DML (Domain Modeling Language).
December 7, 2001
Colorado School of Mines
12
DML and Design Patterns
The model is described by a
hierarchical list of key-attribute
pairs.
Each key is looked up in a
database, a class is fetched, and
the list of attributes is passed to
the corresponding class
constructor.
The model is constructed from the
DML specification.
December 7, 2001
SMARTDUST [
ID 1
xpos 0 ypos 0
battery 1000.000000
graph [
ProtocolSession [
name "app" use "app.sensor-session"
inter_arrival_time 0.002400
packet_size 100
total_neighbors 1
neighbor 2]
ProtocolSession [
name "net" use "net.aodv-session"]
ProtocolSession [
name "mac" use "mac.mac-802-11-session“]
ProtocolSession [
name "phy" use "phy.phy-802-11-session"
attach 2]
]
]
Colorado School of Mines
13
SSFNET-like Architecture
Our host descriptions were “borrowed” from the architecture of SSFNET
http://www.ssfnet.org
Protocol Graph
A ProtocolSession models a
protocol layer (as in the ISO/OSI
reference model).
A ProtocolGraph is a list of
ProtocolSessions and models the
complete protocol stack in a host.
Adjacent ProtocolSessions
communicate by exchanging
ProtocolMessages.
December 7, 2001
Colorado School of Mines
Application Session
Transport Session
Network Session
Link Session
PHY Session
14
The ProtocolSession API
A ProtocolSession is a class
that defines three methods:
pop, push and control.
ProtocolSession N+1
push
ProtocolSession N
pop
(push)
ProtocolSession N-1
December 7, 2001
control
(pop)
An element higher in the stack
can send it messages invoking
push. An element lower in the
stack can send it messages
invoking pop.
Anything that is not related to
the protocol models is
communicated using control.
Colorado School of Mines
15
ProtocolMessage
PHY
MAC
Network
Application
PHY
Header
MAC
Header
Router+IP
Header
Data
Message
Radio Frame
December 7, 2001
Colorado School of Mines
16
The DaSSF Homebrew
http://www.cs.dartmouth.edu/research/DaSSF
An SSF-compliant simulator:
Fast threading mechanism,
Efficient memory utilization,
Portable: runs on sequential and parallel
machines (shared and distributed memory);
IRIX/Solaris/SunOS/Linux/OSF.
December 7, 2001
Colorado School of Mines
17
The Architecture of SWAN
read terrain
features
Physical Process
memory
Terrain
Model
Protocol
Graph
time
run
thread
OS
Model
(DaSSF
Runtime
Kernel)
Host model
read terrain
features
December 7, 2001
RF Channel Model
Colorado School of Mines
18
Where Things Get Complicated
Physical Process: How do we simulate
different physical phenomena with accuracy
and efficiency?
RF Channel Model: The multiple access
technique determines the difficulty of model
construction. Besides, will it scale up?
Level of detail: Less may be better. More
abstraction can mean faster simulation with no
significant loss of accuracy.
December 7, 2001
Colorado School of Mines
19
802.11 RF Channel Model
a
b
If transmitter is close enough so
that receiver is within carrier
range, packets are accepted.
Otherwise, they are thrown away.
R
c
r
Cutoff  model scalability 
efficient parallelization.
d
December 7, 2001
Colorado School of Mines
20
802.11 RF Channel Model (cont.)
b
 k  Elapsed time between tx of messages k and (k-1)
a
R
c
r
If message length is exponentially dist. with mean 1/,
then
Pr{msg sent k agois still in channel}  e k
Channel busy-ness: model the number of “active” messages in the channel.
Bk ( k )  1  e
December 7, 2001
 k
Bk 1 ( k 1 )
Colorado School of Mines
21
802.11 RF Channel Model (cont.)
b
a
R
Bk ( k )  1  e k Bk 1 ( k 1 )
r
+
c
Pkloss 
The general shape of the curve for CSMA +
Some mathematical manipulation
Probability that a message is lost at k
The loss model is now very simple: at the receiver, throw a
Bernoulli( Pkloss )
to determine if a message is to be successfully received or discarded (lost).
December 7, 2001
Colorado School of Mines
22
Milestones Reached
Abstraction of the RF Channel Model for
802.11 implemented.
Detailed model for 802.11 DCF ported from
GloMoSim and used to validate our abstracted
RF Channel Model.
Proof of concept simulations with networks of
chemical sensors powered by BBN WiroKit
routers.
December 7, 2001
Colorado School of Mines
23
Current State
SWAN: Is it available for the general public
yet? We’re sorry to say it isn’t, not yet.
Routing: In order to have a public distribution,
we need public domain technology.
Mobility: support is being added.
Host models: under revision to support power
consumption.
A Berkeley TinyOS port is in the works.
Security: Ultimately our goal is to
develop/study layers for ad hoc networks.
December 7, 2001
Colorado School of Mines
24
A Call to Arms
Rome wasn’t built in a
day.
SSFNET wasn’t built
by one group alone.
We can use a lot of help to turn the duckling
into the SWAN it’s meant to be.
December 7, 2001
Colorado School of Mines
25