Transcript New PowerPoint Template

An Analysis of the Optimum Node
Density for Ad hoc Mobile Networks
Elizabeth M. Royer, P. Michael
Melliar-Smith and Louise E. Moser
Presented by Aki Happonen
Outline
•
•
•
•
•
Introduction
Scope of The Paper
AODV (Ad hoc On-Demand Distance Vector Routing)
Simulations
Simulations
•
•
•
•
•
•
•
AODV
The Mobility Model
Topology Changes
Node Distribution
Throughput
Path Length
Probability to Establish Initial Route
• Related Work
• Conclusions
• Future Work And Some Thoughts
Introduction
• Ad hoc mobility network is a collection of nodes
•
•
Each communicates over wireless channel
Capable of movement
• Each node have unique capability of transmission at
different power levels
• In mobile networks battery life and channel bandwidth
are limited resources
•
Raises importance of transmission power to overall performance of
network
• Kleinrock, Silvester in 1978: Optimum number of
neighbors for node is 5.89, so radius should be
adjusted so that each node has six neighbors
•
Stationary network
Scope of the Paper
• This paper examines effects of transmission
power on mobile networks
•
Does any mobile has optimum transmission radius
determined for stationary networks
• Ad hoc On-Demand Distance Vector (AODV)
routing protocol was used for route
establishment
•
Result can be generalized to most on-demand ad hoc routing
protocols
AODV
• Route discovery
•
•
•
Source node broadcasts a Route Request (RREQ) containing IP address
of destination and last known sequence number – timer to wait for reply
Nodes respond with Route Reply (RREP) to RREQ if
• They are the destination
• They have unexpired route to destination
If source does not receive RREP after timer is expired it rebroadcast
RREQ for some maximum number of attempts – after that session is
aborted
• Route maintenance
•
Route Error (RERR) message is send in case of link breaks in active
route
• Advantages of AODV:
•
•
•
•
•
•
Nodes store only the routes that are needed
Need for broadcast is minimized
Reduce memory requirements and needless duplications
Quick response to link breakage in active routes
Loop-free routes maintained by use of destination sequence number
Scalable to large population of nodes
Simulations
• GloMoSim Network Simulator by UCLA was used
• Free space propagation model with threshold cutoff
was used
•
Free space model has power attenuation of 1/d2, where d is the distance
between nodes
• Four different mobilities between 0m/s and 10m/s
• Each simulation results are average of 10 different
initial network configuration
• Each simulation simulates 240 seconds and models a
network of 100 nodes in 1000m x 1000m area
• Number sources is set at 40 and each source sends 12
512-byte data packets/s
•
Network saturation
Simulations - AODV
• AODV does not guarantee packet delivery –
does find good routes for IP’s best-effort
delivery
• Data packets are not buffered for
retransmission, these packets are likely to be
lost
• If a collision involving a data packet occurs at a
node and packet cannot be captured, the packet
is lost
• Focus on the number of packets received by
destination NOT the ratio of number of packets
received to number of packets send
Simulations – The Mobility Model
• Original model was Random Waypoint model
• In the beginning:
•
•
Randomly placed nodes within the predefined simulation area
Each node selects destination and speed from a uniform distribution of
user-specific speed
• In simulation:
•
•
•
The node travels to its selected destination at selected speed
After reaching the destination it is stationary for some predefined time
At the end of pause time node selects a new destination and speed
combination and resumes movement
• Continues changes in topology of the network and
number of neighbors varies as a function of time
Simulations – The Mobility Model
• New model was developed – Random Direction
• Instead of selection destination, node selects a
direction (in degrees) in which to travel
• In the beginning
•
•
Nodes select a degree between 0 and 359 – destination is found from the
boundary in this direction of travel
Then node selects the speed
• In simulation:
•
•
•
•
Node travels to destination at the given speed
After reaching the destination node rests for given pause time and then
selects a new degree between 0 and 180
Degree is limited because node is on the boundary and they are not
allowed to pass through it
Degree is relative to the wall of the boundary area which the node is
located
• In Modified Random Direction model destination can
be selected anywhere along that direction of travel
Simulations – Topology Changes
Average neighbors/node:
1m/s
5m/s
Simulations – Node Distribution
• In the beginning of
the simulation nodes
are evenly distributed
• After 400 s
simulation time
Random Waypoint
model causes higher
density
• Random Direction
maintains initial node
density
Simulations Results - Throughput
• Small radius and low
connectivity, few data
packets are delivered
• As the connectivity
increases the number of
delivered packets increases
rapidly until curves level off
• There does not appear to be
global optimal number of
neighbors for all mobilities
•For
0m/s is it 7-8, almost the same
than Kleinrock proved but when
mobility increases optimal shifts to
higher connectivity
Simulations Results – Path Length
• Lower transmission
powers do have shorter
path lengths – only routes
that are able to complete
• When network is fully
connected, path length
increases and start to
decrease when
transmission power
increases and fewer hops
are needed to connect
source and destination
Simulations Results – Probability to
Establish Initial Route
• Sparsely connected
network probability is
fairly low
• When density
increases the
probability increases
rapidly until stabilizes
to one
Related Work
• Sanchez, Manzoni and Haas:
•
Calculated the minimum value for the transmission range
that maintains full connectivity in the network- all network
nodes use the same transmission range.
• Ramanathan and Rosales-Hain:
•
Power control algorithm to respond topology changes
• ElBatt, Krishnamurthy, Connors and Dao:
•
Networks with power control has better performance than
networks without that kind of scheme
Conclusions
• In this paper it has been explored transmission
power trade off in mobile networks to
determine the optimum node density for
delivering maximum number of data packets
• This paper shows that there does not exist a
global optimum density
• To achieve the maximum the node density
should increase as the rate of node movement
increases
Future Work And Some Thoughts
• Extend model towards real world conditions
•
Terrain and atmospheric conditions effect to connectivity
• Presenter thoughts:
•
•
•
What are requirements for power control algorithms?
Optimum number of neighbors is very close to L. Kleinrock
and J. Silvester finding in their paper “Optimum
Transmission Radii for Packet Radio Networks or Why Six
is Magic Number”
Who about connect channel capacity and routing
algorithms?