Transcript Heterogeneity-aware Ad hoc Networking

Heterogeneity-aware Ad hoc Networking
[Routing Perspective]
Dr. Young-Bae Ko
([email protected])
Dept. of Information and Computer Engineering
Ajou University
Contents
 Contents
PART 1: Mobile Ad
–
–
–
–

hoc Networks in General
Brief overview
Main issue: “Routing”
Different approaches in routing protocol design
Key observations
PART 2: Heterogeneity-aware Ad hoc Networks
– Motivation
– Heterogeneity-aware ad hoc “routing” protocols
• AODV-BlackListing protocol
• Our proposal
• Performance Evaluation
– Conclusions
Mobile Ad Hoc Networks

Infrastructure-less wireless networks
– Neither pre-existing, wired backbone nor centralized administration
– Peer-to-Peer and self-organizing networks

Characteristics
– Easy and rapid deployment
– Dynamic topology change
– Limited resources

Applications
–
–
–
–
Military environments (battlefield network)
Emergency services (disaster relief, search-and-rescue sites)
Spontaneous networking (unplanned meetings or conferences)
Embedded computing and networking applications (ubiquitous computers
with short-range interactions, vehicle networks)
– Wireless sensor networks
Main Issue – “Routing”

Each mobile serves as routers, not just an end point
– If there is NO direct link between a source and a destination, multi-hop
routing is needed to discover their routes.

Routing is a very challenging task.
– Mobility and link failure/repair may cause
route changes.
– Routing protocol must be distributed,
a minimal overhead.

frequent
Significant research has been conducted.
– Mostly designed for IP based, homogeneous, mobile ad hoc networks.
– Focuses on fast route establishment and maintenance with minimal
overhead
with
Different Approaches in Protocol Design

Proactive, Table-driven Approach
– Based on traditional link-state and distance-vector routing protocols.
– Continuously update the topological view of the network by periodically
exchanging appropriate information among the nodes.
– Determine routes independent of traffic pattern
– Examples: DSDV, OLSR, TBRPF etc.

Reactive, On-demand Approach
– Discover and maintain routes only if needed
– Do not continuously maintain the overall network topology
– The network is flooded with “route request” control packets when a new
route is required.
– Examples: DSR, AODV, LAR, etc.

Hybrid Approach
– Combine the two approaches above: locally proactive, globally reactive !
– Example: ZRP
Key Observations

Routing problems are quite well-understood.
– At least, when using common assumptions about the network,
Designing reactive protocols: “Solved” problem &
Designing proactive protocols: “Solved” problem
– However, interesting issues still exist when other missing parameters are
considered.
• Energy efficiency, QoS support, Heterogeneity, physical layer properties (e.g.,
directional antennas),

Most of proposed ad hoc routing protocols are NOT
heterogeneity-aware.
– They assume a physically flat network architecture with bidirectional,
symmetric routes.
– The performance of these protocols may degrade in networks with
heterogeneous nodes.
PART II
Heterogeneity-aware Ad Hoc Routing
“Heterogeneity” in Ad Hoc Networks
Motivation

In real-world multi-hop wireless networks, a physically
hierarchical network architecture is quite natural.

Reasons:
– Node Heterogeneity: There exist various types of mobile hosts with
different characteristics, roles, capacities, and mobility patterns.
• e.g.) In the military scenarios, the troop leader usually have more capable
networking equipment than the private soldiers.
– Link Heterogeneity: There are difference in radio transceiver
capabilities of nodes (i.e., different propagation range) and difference
in wireless channel interference experienced by each node.
• Unidirectional links can be quite common in ad hoc networks.
Motivation

Motivation
Such
an heterogeneity may create challenges to current ad hoc
networking protocols, most of which simply assume a
physically flat architecture.
– Most ad hoc unicast routing protocols do not take heterogeneity into
account when making routing decisions
• Each node is considered “identical” in capabilities.
• All network links are considered “bidirectional”.
– Most of the proposed ad hoc multicasting protocols such as ODMRP and
ADMR also assume a flat network architecture.
• There are schemes that propose to utilize clustering to build hierarchical
networks, but these hierarchies are merely logical, as opposed to physical.
– Current IEEE 802.11 MAC protocols with RTS/CTS handshake
mechanism simply assume that links are symmetric.
• when node A can send RTS to node B, A will also be able to receive CTS
from B.
Heterogeneity-aware Ad Hoc Routing

Routing performance can be suffered from the existence of
unidirectional links and routes.
E
S
A
B
C
D
The link between B and C is a unidirectional link. The packets
transmitted by node B reach node C, but not vice versa.
Related Works

Motivation
There
has been recent attention on routing in ad hoc networks
with unidirectional links [1, 2, 3].
– However, these protocols rely on proactive routing mechanisms where
each node periodically exchange link information for route maintenance.

Very few reactive, on-demand protocols give attention to
unidirectional links [4].
– DSR requires two separate route discoveries to find unidirectional paths:
one from the source and the other from the destination, as opposed to a
single route discovery to find bidirectional paths.
– In the latest AODV draft, some mechanisms are newly added to handle
the problem of unidirectional links
• We refer to this version of AODV as the “AODV-BL (Blacklist)” scheme.
Basic AODV protocol

Two important assumptions of the basic AODV protocol
– All links between neighboring nodes are symmetric.
– Only one RREQ arrives at a final destination via the shortest path.

Example scenario with the previous figure:
– A RREQ packet generated by a source node S traverses the path,
S-A-B-C-D.
– When node D receives the RREQ, it sends a RREP back to node S via the
reverse path, D-C-B-A-S.
– However, the RREP is NOT able to reach to node B from C because node
B is not located within node C’s transmission range.
– As a result of a RREP transmission failure by node C, the source S
cannot receive the corresponding RREP packet and hence it experiences
a route discovery failure in its first trial.
• Such a failure will cause a number of route discoveries repeatedly with no
benefit !
AODV-BL (BlackListing) protocol

The newly proposed scheme for AODV for efficient operation in
presence of unidirectional links
– Whenever a node detects a unidirectional link to its neighbor, it blacklists
that neighbor from which a link is unidirectional.
– Later when the node receives a RREQ from one of the nodes in its blacklist
set, it silently discards the RREQ to avoid forming a reverse path with
unidirectional link.

The example scenario continued:
– Node C cannot be acknowledged by node B and therefore it will put node B in its
blacklist set.
– Later when node S re-broadcasts a new RREQ packet, node C will ignore this
RREQ received from B but forward another copy of the RREQ from node E.
– Finally, a destination node D will receive the RREQ through a longer route at this
time, and return a RREP back to the source S via a reverse path; D-C-E-B-A-S,
having no unidirectional links.
Problems of AODV-BL

This modified AODV scheme is simple and may be efficient
when there are few unidirectional links

However, as a number of asymmetric links increase, its routing
overhead is likely to become higher since a source node will
always suffer from a failure in its first trial of route discovery.
– It needs to flood RREQ messages more than once to find a symmetric
route with all bidirectional links.
– Thus, more number of route discoveries may be needed before a fully
symmetric route is found.

It also results in an increase of a route discovery delay.
Our Proposal

We propose the improved scheme, in which a node detects a
unidirectional link immediately in its a RREQ forwarding process.
– All nodes receiving RREQ packet are required to decide whether to
forward it or not.
– This decision is based on the comparison of transmission range and distance

Our Simple Idea
– When a node X receives a RREQ from node Y, node X compares its
transmission range using the highest power level to an estimated distance
between them.
• Question: How to calculate an estimated distance between X and Y ?
– If the estimated distance from X to Y is larger than the transmission range of
node X, node X considers its link towards Y to be unidirectional, and
therefore drops the receiving RREQ packet without any further broadcast.
Illustration
RX: Transmission range of node X
d: Estimated distance between S and R)
RS
RS
RR
RR
S
R
d
(a) Bidirectional link (d<RR)
S
R
d
(b) Unidirectional link (d>RR)
How To Calculate the Distance (1)

Question: How to calculate an estimated distance between two
communicating nodes for a RREQ message, especially at a
receiver side ?
– This can be done in two different ways as described below.

Network Layer Solution with location information
– Assumption: Each node can know its position.
– How to work:
• A transmitter node X includes its own location information with a RREQ to be
flooded.
• When some node Y receives the RREQ from X, Y can calculate the estimated
distance, based on its own physical location.
– This method can be useful and easy to implement, but requires that
information about physical location of the participating nodes be
available.
How To Calculate the Distance (2)

A Cross Layer Solution
– Utilize a path loss model for the two-ray ground reflection model.
– In wireless networks, if we know the transmitted power of a packet at
the transmitter and a separation distance of the receiver, the received
power is given by the following equation.
Pt * Gt * Gr * (ht2 * hr2)
Pr =
(1)
d4 * L
– We can then derive the following equation from the equation above.
d=
4
Pt * Gt * Gr * (ht2 * hr2)
Pr * L
(2)
Appendix
The variables used in the previous equations are listed below.
Parameters
Meaning
Default Value
Pt
Pr
Gt
Gr
ht
hr
L
d
Transmitter power
Received power
Transmitter antenna gain
Receiver antenna gain
Transmitter antenna height
Receiver antenna height
System loss factor
Transmitter-Receiver separation
distance in meters
1.0
1.0
1.5
1.5
1.0 (No loss)
How To Calculate the Distance (3)

A Cross Layer Solution (cont’d)
– Eq. (2) shows that a distance between two communicating nodes can be
estimated at a receiver side, if the transmitted power level (Pt) of the
packet transmitter and the power received at the receiver (Pr) are known.
– To implement this method, the transmitter should make the transmitted
power information available for the receiver, by putting the power
information either to a RREQ or to a MAC frame.
• The latter approach may cause a compatibility problem to IEEE 802.11,
because it has to modify the format of the MAC header
• Instead, we use the former approach of modifying a RREQ packet format for
our simulation.
– In order for these lower layer information (such as values of both
transmitted and received power levels) visible to the networking layer, we
can borrow a Cross Layer Design Concept from [5].
A Cross Layer Design Concept

Lower layer parameters affect the parameters in the higher layer.

Illustration of the Cross Layer communication
– At the physical layer, channel estimation is
performed to obtain the instantaneous SNRi of
a link.
– A transmitter then chooses a transmission rate Ri
based on the estimated SNRi. This in turn affects
the packet delay Di of the link.
– At the network layer, routing decisions are made
based on the packet delay associated with each link.
– The routing decisions in turn affect the offered load
distribution in the network and impact the
Parameters Di, Ri and SNRi on individual links.
the communication of various layers are
related.
Network
(make routing decision)
D_i
MAC packet delay
R_i
Link capacity
SNR_i
SNR information
MAC
PHY
Thus
Channelinter-
Performance Evaluation

Simulation Model (ns2 w/ CMU extensions)
– 100 nodes in a rectangular region of 1000×1000 unit area.
– Two different values for a node’s transmission range: 250 and 125 units
• Equal probability
– Traffic pattern: 10 CBR connections running on UDP.
• Each CBR source generates four 512-byte data packets every second.
– Mobility model: Random Waypoint model.
• Each node moves with a maximum speed of 20 units per second (i.e., average
speeds of 10 units per second).
Performance Evaluation – cont’d.

Performance metrics:
– Data Packet Delivery Ratio:
• Packet Delivery Ratio is defined as the ratio of the number of data
packets received by the CBR sink at a final destination, and the number
of data packets originated by the application layer CBR source.
– Normalized Routing Overhead:
• The Normalized Routing Overhead is defined as the ratio between the
total number of routing control packets transmitted by all nodes and the
total number of data packets received by all destinations
– Route Discovery Delay:
• The Route Discovery Delay is the average delay that takes to find a
route from the source to the destination.
Simulation Results (1)
Packet delivery ratio
as a function of pause time

Our proposed scheme’s delivery ratio is consistently higher than others.
– Due to more efficient and fast detection method of unidirectional links.
Simulation Results (2)
Normalized routing overhead
as a function of pause time

Our proposed scheme provides a lower rate of increase than the other two.
– This is because, with the proposed scheme, number of route requests is
significantly reduced by preventing route discovery failures due to a route
reply packet loss caused by the existence of unidirectional links.
Simulation Results (3)
Route Discovery Delay
as a function of pause time

We see that the proposed routing scheme yields a better performance
(i.e., smaller latency) than others, due to the similar reasons before.
Conclusions

We motivated and presented heterogeneity-aware approaches for
protocol design at the network layer in physically hierarchical
ad hoc networks.
– Simulation results indicate that our protocols perform well in
heterogeneous ad hoc networking environments.

Topics for Future Research
– More complete cross-layer system solution ?
– More powerful heterogeneity-aware routing protocols ?
– What about multicasting and MAC ?
• I have a short paper [6] for a multicast case though.
– And more…
References
1.
2.
3.
4.
5.
6.
L. Bao and J.J. Garcia-Luna-Aceves, “Link state routing in networks with
unidirectional links,” in Proc. of IEEE ICCCN’99
R. Prakash, “A routing algorithm for wireless ad hoc networks with
unidirectional links,” ACM/Kluwer Wireless Networks, Vol. 7(6), pp.617625, Nov. 2001.
V. Ramasubramanian, R. Chandra, and D. mosse, “Providing a bidirectional
abstraction for unidirectional ad hoc networks,” in Proc. of INFOCOM’02.
IETF mobile ad hoc networks (MANET) working group charter. [Online].
Available: http://www.ietf.org/html.charters/manet-charter.html
W. Yuen, H.-N. Lee, and T. Anderson, “Simple but effective cross-layer
networking system for mobile ad hoc networks,” in Proc. of IEEE
PIMRC’02.
Young-bae Ko and S.-J. Lee, “A Multicast protocol for physically
hierarchical ad hoc networks,” in Proc. of VTC’03 Spring.
THANK YOU !
For more information on whatever (:-), please visit
my homepage at
http://dmc.ajou.ac.kr/~youngko
(Distributed and Mobile Computing Lab)