Publications at NRL

Search by Title


Search by Author




Efficient Flooding in Ad hoc Networks using On-Demand (Passive) Cluster Formation


Many ad hoc network protocols (e.g., routing, service discovery, etc.) use flooding as the basic mechanism to propagate control messages. In flooding, a node transmits a message to all of its neighbors. The neighbors in turn transmit to their neighbors and so on until the message has been propagated to the entire net- work. Typically, only a subset of the neighbors is required to for- ward the message in order to guarantee complete flooding to the entire network. If the node geographic density (i.e., the number of neighbors within a node’s radio reach) is much higher than what is strictly required to maintain connectivity, one can easily see that flooding becomes inefficient because of redundant, “superfluous” forwarding. In fact, superfluous flooding increases link O/H and wireless medium congestion. In a large network, with heavy load, this extra O/H can have severe impact on performance and should be eliminated. Clustering and, more generally, route aggregation techniques have been proposed in the past to reduce the flooding O/H. These techniques operate in a proactive, background mode. They use explicit control packets to elect a small set of nodes (cluster-heads, gateways or, more generally, flood forwarding nodes) and restrict to such set the flood forwarding function. The problem of such proactive schemes is the constant traffic O/H introduced in the network. In this paper, we propose a new flooding mechanism based on passive, on-demand clustering. This mechanism reduces flooding overhead without loss of network performance. Passive cluster- ing dynamically partitions the network in clusters interconnected by gateways. Passive clustering is an ”on demand” protocol. It executes only when there is user data traffic; it exploits data pack- ets for cluster formation. Passive clustering has many advantages compared with “active” clustering and route aggregation tech- niques: (1) it eliminates cluster set up latency and extra control overhead (by exploiting on-going packets); (2) it uses a novel, effi- cient gateway selection heuristic to elect the minimum number of forwarding nodes (thus reducing superfluous flooding); (3) it re- duces node power consumption by eliminating the periodic, back- ground control packet exchange. Simulation results show that passive clustering can reduce re- dundant flooding by up to 70% with negligible extra protocol over- head. Moreover, we show that passive clustering can be applied to several reactive, on-demand routing protocols (e.g., AODV, DSR and ODMRP) with substantial performance gains.

Paper: PDF file of paper

Information & Date

MOBIHOC 2002, , October. 2002


Yunjung Yi