An Optimized Flooding Algorithm Based on Multipoint Relaying for Mobile Ad Hoc Networks

It is proved that multipoint relaying (MPR) is an efficient strategy for on-the-fly flooding in mobile ad hoc networks. Upon receiving a flooding packet, each relaying node designated by the packet selects nodes from its neighbors for next packet relay. All the selected relaying nodes finally form a connected dominating set (CDS) for the network. Selecting fewest neighbors as relaying nodes to cover all the nodes within 2-hop neighborhood is the key issue for MPR. However, existing MPR-based flooding algorithms neglect the impact of common adjacency relation of relaying nodes. The analysis of connecting topology of relaying nodes indicates that the cardinality of uncovered 2-hop neighbors can be further reduced, which means less redundant relaying nodes. Nodes that are adjacent to several relaying nodes only need to be covered by just one of them. As a result, the workload of other relaying nodes would be reduced. Meanwhile, self-pruning is involved to improve MPR's performance. That is, selected nodes can decide whether to relay a packet or not all by themselves. According to these facts, the optimized flooding algorithm based on eliminating common adjacency relation with self-pruning (ECARSP) is proposed. Both theoretical analysis and experiment results show that ECARSP outperforms the existing flooding algorithms in terms of the number of relaying nodes and network workload.