Transcript Introduction

Efficient Flooding in Ad hoc Networks using
On-demand (Passive) Cluster Formation
2003. 04. 18
ICNS Lab
Na Gajin
Contents
•
•
•
•
•
•
•
Introduction
Blind Flooding / Efficient Flooding
Related Works and Motivations
Clustering in Ad hoc Networks
Passive Clustering
Simulation Studies
Conclusion
Introduction
• Mobile ad hoc networks (MANET)
– Self-creating, self-organizing and self-administrating without
deploying any kind of infrastructure
– Wide application in military, commercial and educational
environments where fixed infrastructure is not easily acquired
– Two nodes communicate directly or via a multi-hop route with the
cooperation of other nodes
– To find a multi-hop path to another nodes, each MANET node
widely use flooding or broadcast
Introduction
• Route Discovery (DSR protocol)
“A”
A
“A,B”
B
id=2
“A,B,C”
C
id=2
D
id=2
destination
source
A
B
C
D
A
B
C
D
• Route Maintenance
A
Hello messages
A
B
C
D
Introduction
ᆞ Blind Flooding
– Node transmits a message to all of its neighbors
– The neighbors in turn relay to their neighbors and so on until the
message has been propagated to the entire network.
– Neighbor degree gets higher, the blind flooding suffers from the
increases of
1. redundant and superfluous packets
2. the probability of collision
3. congestion of wireless medium
Blind Flooding
redundant and superfluous packets
Introduction
• Efficient Flooding
– Only a subset of neighbors is required to participate in flooding
to guarantee the complete flooding
– In MANET, collecting topological information is very difficult
(huge extra overhead)
– Many on-demand ad hoc routing schemes and service discovery
protocols simply use blind flooding
Introduction
•
•
New mechanism for efficient flooding suitable for
on-demand protocols based on passive clustering
Several contributions with previous flooding
mechanisms
1. It does not need any periodic messages
2. It does not have any setup latency, and it saves energy with no
traffic
3. Its maintenance is well adaptive to dynamic topology and
resource availability changes
Related Works
•
Proposed several heuristics to reduce rebroadcasts
1. Probabilistic scheme
 Rebroadcast the packet with the randomly chosen probability
2. Counter-based scheme
 Rebroadcast if the number of received duplicate packets is less
than a threshold
3. Distance-based scheme
 Uses the relative distance between hosts to make the decision
4. Location-based scheme
 Based on pre-acquired location information of neighbors
5. Cluster-based scheme
 Only cluster heads and gateways forward again
Related Works
• Another approach : exploit topological information
– Self-pruning
• Each forwarding node piggybacks the list of neighbors of itself on
outgoing packet
– Dominant-pruning
• Extends the range of neighbor information to two-hop away
neighbors
• Still depend on the periodic hello messages to collect
topological information
– Extra hello messages consume resources and drop the network
throughput in MANETs
Motivations
• Clustering
– Reducing the routing table size
– Reducing the communication overhead
– Stabling network topology
– Be ease of location management
– Providing a simple and feasible power control mechanisms
Brief Overview of Clustering
• Clustering : Another method to select forwarding nodes
– Cluster head : representative of each group (cluster)
– Gateway : a node belongings to more than two clusters at the
same time
– Ordinary nodes
• Transmission area (radio range) of the cluster head defines a cluster
• k-hop clustering
Efficient Flooding with Clustering
CLUSTER HEAD
GATEWAY
S
ORDINARY NODE
Flooding
Only cluster heads and gateways rebroadcast and ordinary nodes stop forwarding
Motivations
• Clustering in ad hoc networks
–
–
–
–
Hierarchical routing schemes
Master election algorithms
Power control
Reliable and efficient broadcast
• Cluster architecture commonly not used
– Previous clustering schemes are based on the complete knowledge of
neighbors
– None of the clustering algorithms has proposed a gateway reduction
mechanism to select the minimal number of gateways
– The previous clustering requires huge maintenance cost in high
mobility
Lowest-ID Clustering
•
Each node is assigned a distinct ID
•
Periodically, the node broadcasts the
list of nodes that it can hear
•
A node which only hears nodes with
ID higher than itself is a “clusterhead”
Clusterhead
Gateway
Ordinary Node
MPR (Multipoint Relays)
•
Reduce the flooding of broadcast
messages
•
Set of one-hop neighbors and twohop neighbors
•
To get the information about the
one-hop neighbors, most
protocols use some form of
HELLO messages periodically
Three Important Observations
1. The selection mechanism to choose the dominant set
should be efficient and dynamic
2. In a MANET, collecting accurate topological information
is very hard and carries the huge overhead
3. Clustering schemes is independent of the network
topology
 With keeping advantages of clustering, our scheme
eliminates the main control overhead
Overview of Passive Clustering
• On-demand protocol
• Constructs and maintains the cluster architecture only when there
are on-going data packets that piggyback “cluster-related
information”
• Each node collets neighbor information through promiscuous packet
receptions
• First Declaration Wins
– Node that first claims to be a cluster head “rules” the rest of nodes in its
clustered area
• Gateway Selection Heuristic
– Elect the minimal number of gateways
Construction and Maintenance
• The IP option field for cluster information
– Node ID : the IP address of the sender node
– State of cluster : the cluster state of the sender node
– If a sender node is a gateway, then it tags two IP addresses of
cluster heads which are reachable from the gateway
• Initially joining node or floating node sets the cluster
state to INITIAL
Passive Clustering Algorithm
• Cluster states
– INITIAL, CLUSTER_HEAD, ORDINARY_NODE, GATEWAY,
CH_READY, GW_READY and DIST_GW
• Packet handling
– Upon sending a packet, each node piggybacks
cluster-related information
– Upon a promiscuous packet reception, each node
extracts cluster-related information of neighbors and
updates neighbor information table
Passive Clustering Algorithm
• A cluster head declaration
– INITIAL  CH_READY : packet arrives from another node that
is not a cluster head
– With outgoing packet, a CH_READY node can declare as a
cluster head
• Becoming a member
– A node becomes a member of a cluster once it has heard or
overheard a message from any cluster head.
– A member node can serve as a gateway or an ordinary node
depending on the collected neighbor information
– A member node can settle as an ordinary node only after it has
learned enough neighbor gateways
Gateway Selection Heuristic
• Gateway : a bridge node that connects two adjacent clusters
• Only one gateway is needed for the each pair of two adjacent
clusters
• Gateway selection mechanism that eventually allows only one
gateway for each pair of two neighboring cluster heads
Gateway Selection Heuristic
• candidate gateway : a node belongs to more than two clusters at the
same time
• If the node finds 2 cluster heads, then it finalizes its role as a
gateway and announces 2 cluster heads to neighbors
• If a gateway has received a packet from another gateway which has
announced the same pair of CHs, then this node compares the node
ID of itself with that of the sender.
• If this node has the lower ID, it keeps its role as the gateway.
• Otherwise it changes the pair of CHs or changes its state
Gateway Selection Heuristic
4
1
(1,4)
(1,7)
CLUSTER HEAD
GATEWAY
(4,5)
ORDINARY NODE
GW_READY NODE
(5,7)
5
7
There is at most one gateway between
any pair of two cluster heads
Simulation Studies
• Flooding efficiency with passive clustering
• Apply passive clustering to representative reactive ad
hoc routing protocols (AODV, DSR)
• Flooding Experiments
– TNP (the Total Number of Packets sent for one broadcast)
– NDB (the Number of nodes Delivered the Broadcast)
–
–
–
–
BF (Blind Flooding)
MPR-F (Flooding with MPR scheme)
AC_LID-F (Flooding with active clustering with Lowest Id )
PC_LID-F (Flooding with passive clustering)
Flooding Experiments
• Fixed network size with node mobility (100 nodes)
Total Number of Packet sent
Delivery Count (NDB)
On-demand Routing -AODV
Normalized Control Overhead
Delivery Ratio
On-demand Routing - DSR
Normalized Control Overhead
Delivery Ratio
Conclusion
• Passive Clustering protocol
– Effective gateway selection heuristic
– Efficient flooding based on topological information
– Applicability of passive clustering to a few reactive routing
protocols
References
• Taek Jin Kwon , Mario Gerla, “Efficient Flooding in Ad hoc
Networks using On-Demand (Passive) Cluster Formation”, ACM
SIGCOMM Computer Communication Review ,2002.
• Gerla, M.; Taek Jin Kwon; Pei, G., ”On-demand routing in large ad
hoc wireless networks with passive clustering”, Wireless
Communications and Networking Conference, 2000.
• Amir Qayyum, Laurent Viennot, Anis Laouiti, “Multipoint relaying: An
ecient technique for flooding in mobile wireless networks”, Technical
Report RR-3898, INRIA, February 2000.