移动自组织网络中一种基于多点中继策略的优化泛洪广播算法

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

多点中继(multipoint relaying,MPR)是一种有效的移动ad hoc网络即时泛洪广播策略.选择尽量少的邻节点以覆盖2跳(2-hop)范围内所有节点是MPR策略的关键.然而现有的基于MPR策略的泛洪算法忽视了转发节点之间所存在的共有邻接关系对结果的影响.在分析转发节点之间连接拓扑关系的基础上,发现尚未被覆盖的2跳节点集合的势(cardinality)可以进一步压缩,从而进一步减少冗余的转发节点.同时,讨论了利用自裁减(self-pruning)提升MPR性能的可能性.据此提出了基于共有邻接关系消除的自裁减辅助MPR优化泛洪广播算法(ECARSP).理论分析和实验结果表明,ECARSP在转发节点数量和网络负载等方面均要优于现有的移动ad hoc网络MPR泛洪算法.

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.