Transcript Ad-hoc network…

Modelling Ad Hoc
Networks
Lecture 9
Use Cases
2
Possibilities
•Telephones (cellular, cordless, other)
•Cordless multimedia (headsets, speakers, mic.)
•Portable computers (Laptops, desktop, other)
•Cordless computer peripherals (keyboard, mouse)
•LAN – Local Area Network peripherals (printer,
fax)
•PDAs - Personal Digital Assistants (palm top/pilot)
•Digital cameras
3
Ad-…what?
Ad-hoc network…
…a LAN or other small network,
…with wireless connections
…devices are part of the network only for the
duration of a communications session
Or …while in close proximity to the network
4
Ad-hoc Networking
Collection of wireless mobile nodes (devices)
dynamically forming a temporary network
without the use of any existing network
infrastructure or centralized administration
5
Properties
•Requires devices to cooperate autonomously
•Without user intervention
•Rapid self-organizing wireless network
•Independent of infrastructure
•Heterogeneous & adaptive
6
Why?
Microprocessor embedding trend in:
•cellular phones, car stereos, televisions, VCRs,
watches, GPS (Global Positioning System)
receivers, digital camera.
•Ensembles of computational devices for:
•environmental monitoring
•personal area networks
•geophysical measurement
7
How?
Transmission Standards:
1.
Piconet
2.
HomeRF (Radio Frequency)
3.
IEEE 802.11 Wireless LAN WG (Working Group)
4.
Bluetooth SIG (Special Interest Group)
•
5.
These above use radio waves from licence-exempt
ISM (Industrial, Scientific and Medical)
frequency band - around 2.4 GHz
IrDA (InfraRed Data Association)
• which uses infrared instead of radio waves
8
Piconet
• A general purpose, low-powered, ad-hoc
network
• It allows two devices near each other to
inter-operate
• These devices can be either mobile or fixed
• The range is said to be reasonably short
9
HomeRF
Uses Shared Wireless Access Protocol (SWAP)
system
• carries both voice and data traffic
• inter-operate with the PSTN
(Public Switched Telephone Network)
and the Internet
• the range covers typical home and yard
10
IEEE 802.11 Wireless LAN
The principles of Wireless Local Area Network
(WLAN) are defined in IEEE 802.11 standard
• It defines two different topologies:
ad-hoc network and infrastructure network
• This ad-hoc network is able to use only created
wireless connection instead of fixed
infrastructure
11
Bluetooth
• The code name for an open specification for
short-range wireless connectivity
• Effortless, instant wireless connections between
a wide range of communication devices in a
small environment
• The BT range restricts the environment to about
10 meters
• Used in virtually any mobile device like that can
have Bluetooth radios integrated into them 12
IrDA
•
based on technology similar to the remote
control devices
• high-speed short range, point-to-point cordless
data transfer
• in-room cordless peripherals to host-PC
• maturity and standardization activities
advantage over radio
13
Challenges Facing Ad Hoc
•
•
•
•
•
•
Security
scalability
load balancing / etiquette between hosts
QoS
CPU/memory overhead
effect on devices’ battery life
14
Issues in Protocol Design
•
•
•
•
•
Must run in distributed environment
must provide loop-free routes
must be able to find multiple routes
must establish routes quickly
must minimize overhead in its
communication / reaction to topology
change
15
Some Implementation Choices
•
•
•
•
•
•
Flat vs. hierarchical architecture
proactive vs. reactive to topology changes
table-based, demand-driven, associativity-driven
topology change dissemination methods
when/how often to exchange topology info
assumptions about rate of change of topology
and/or quality of connections
16
Some Ad Hoc Protocols
• DARPA (1970s military packet radio)
used with SURAN (SURvivable Adaptive Network; an early ad hoc networking testbed)
•
•
•
•
CGSR (hierarchical)
TORA (time-based; uses link reversal)
DSR
AODV
17
CGSR: Hierarchical Routing
• All nodes send their
data to cluster head
nodes
• heads act as second-tier,
high-power network
• +: simpler routing
-: poor load balancing,
not secure
18
In-Depth: AODV
(Ad-hoc On-demand Distance Vector routing)
• purely on-demand (no routes determined until needed)
• each node contains routing table of nexthop information for how to get to every
other node
19
AODV Path Discovery
• Source node broadcasts a path
discovery
• message continues until it
reaches destination, or node
with path in table
• sequence nums
• discovery response sent back
along reverse path
20
AODV Path/Connection Maintenance
• Nodes ‘ping’ with hello messages to test links
• timeouts assumed to be broken links
• (only) recent active nodes notified of
topology changes--propogated to neighbors
21
Contrast: DSR
(Dynamic Source Routing)
• resides in kernel IP layer (based on IPv6 format)
• nodes contain tables of full paths to other nodes
• messages: Route Request, Route Reply,
Route Error, ACK
• Send, Retransmit buffers
• passive ACK
22
Mobility models classification
• Entity
MMs
A node’s movement does not influence in anyhow other nodes’
movements. Nodes move independently from each other.
— Random Walk ( & its probabilistic version)
— Random Waypoint
— Random Direction
— Gauss-Markov
— City section mobility models
• Group MMs
represent MNs whose movements are dependent. Used when MNs
collaborate together to accomplish a common goal. Typical situations do
exist in military environments (soldiers move together)…
— Column MM
— Nomadic Community
— Pursue
— Reference Point Group MM
Random Walk (1)
It wants represent the movement of the entities in an unpredictable way. In
particular, a node moves from its current location to a new one by
randomly choosing:
— Direction between [0,2pi]
— Speed between [MinSpeed, MaxSpeed]
— Either duration of movement tm OR distance d
• Direction and speed are both uniformly distributed
• A node which “crashes” against the boundary keeps on moving on an
opposite direction between [0,pi] depending on the incoming one.
OBSERVATIONS:
1) Nodes start moving at t=0. Choosing a DURATION implies that all the
nodes change directions at the same time and travel for different distances. In
contrast, choosing a DISTANCE implies same distances but different duration.
2) The pattern is memory-less i.e. current speed and direction do not depend
upon the previous ones. Therefore, there will be sharp and sudden turns.
3) Short tm or d lead the nodes to move around their current location. Unless it
is necessary to study a semi-static network, they MUST be chosen large.
Random Walk (2)
Example of a travelling pattern of a mobile node using the 2D
Random Walk MM
Surface size 300 x 600 m, tm = 60s
Random Waypoint (1)
It is a variation of Random Walk. It introduces the concept of pause time. A
node randomly chooses (Parameters uniformly distributed):
— Pause Time (to wait before resuming the movement) [Pmin,Pmax]
— Direction [0,2pi]
— Speed [Minvel,Maxvel]
— Destination point (x,y) to reach..
OBSERVATIONS:
1) the duration of the movement depends on the destination point chosen.
2) nodes do not start roaming all together unless Pmin = Pmax = 0.
3) the pattern becomes a Random Walk when (Pmin = Pmax = 0 ) AND
([Minvel,Maxvel] = [MinSpeed, MaxSpeed])
4) it is the most commonly used MM in ad-hoc network simulation studies
(often times is modified).
– It needs particular attention to choose the initial locations. Discard the initial part
of the simulation OR save the node’s location OR do not place the nodes randomly.
– The choice of Pauses and Speeds is relevant. Fast nodes and long pauses
produces a more stable network than slow nodes and short pauses.
– The most argued issue is that nodes are more likely to be in the central part of the
topology rather than close to the bounds.
Random Waypoint (2)
Example of a travelling pattern of a mobile node using the
Random Waypoint MM
• Clearly the motion is
centrally happening
• Nodes appear to
converge, disperse and
converge again
• Nodes tend to have
many neighbors when in
the center and almost
none when they disperse.
Surface size 300 x 600 m
Random Direction (1)
Designed to overcame the concentration of the nodes of which R. Waypoint
suffers. Nodes start moving by choosing
— Direction between [0,2pi]
— Speed between [MinSpeed, MaxSpeed]
• Nodes will travel till the bound is reached. On this position they’ll stand
for a pause time before leaving to a New-Direction [0,pi].
OBSERVATIONS:
1) Nodes are forced to basically stay away from the center for the most of the
time. In fact, they ALL pause somewhere on the perimeter.
– Implications:
• Average Hop count for Data-packets will be much higher than in R.
Waypoint or R Walk. (nodes are on average far from each others)
• Higher probability to have Network partition (especially with few
MNs).
Random Direction (2)
Example of a travelling pattern of a mobile node using the
Random Direction MM
Surface size 300 x 600 m
Questions
30