Forward-node-set-based broadcast in clustered mobile ad hoc networks

A taxonomy of broadcast protocols in mobile ad hoc networks (MANETs) is given where protocols are classified into four groups: global, quasi-global, quasi-local, and local. The taxonomy also divides protocols based on the nature of algorithms: probabilistic and deterministic. The locality of maintenance also plays an important role in evaluating the protocol. An important objective in designing a broadcast protocol is to reduce broadcast redundancy to save scarce resources such as energy and bandwidth and to avoid the broadcast storm problem. This objective should be achieved without introducing excessive overhead and time delay, measured by sequential rounds of information exchanges. This is done by choosing a small forward node set that forms a connected dominating set (CDS) to carry out a broadcast process. In this paper, a clustered network model is proposed in which each node is a clusterhead in the clustered architecture. Clusterheads are connected by carefully selecting non-clusterhead nodes locally at each clusterhead to connect clusterheads within the 2.5-hop coverage, a novel notion proposed in this paper. Information of neighbor clusterheads is piggybacked on the broadcast packet to further reduce each forward node set. It is shown that this approach is quasi-local with locality of maintenance. In addition, this approach has a constant approximation ratio to the minimum connected dominating set (MCDS) and generates a small forward node set in the average case. Comparisons are also done through simulation with representative protocols from each of the four groups of protocols based on the proposed taxonomy. We also simulate the proposed broadcast protocol in a dynamic network and analyze its performance. Copyright (C) 2003 John Wiley Sons, Ltd.