大规模ad hoc网络拓扑分割探测研究

Partition detection for large scale ad hoc networks

针对网络中极易导致网络拓扑分割的关键节点,首先证明了关键节点的判定准则,它从本质上揭示了关键节点i的产生与两个决定性因素(邻节点度Ni以及基本回路度Mi)间的关系,指出Ni?Mi≥2是关键节点i存在的充要条件,极大地方便了关键节点的判定。在此基础之上,结合ad hoc网络具体应用背景,提出了一种分布式拓扑分割探测算法——DPDP(distributed partition detection protocol)算法。通过在局部范围内进行关键节点的探测,该算法能够有效达到网络拓扑分割探测目的。理论分析及实验结果表明:DPDP算法具有复杂度低、准确度高、开销小、扩展性好的特点,性能优于其他算法。

As the failure of a critical node will directly partition a network, a theorem for critical node identification was proved, which indicates that node degree Ni and elementary loop degree Mi of node i are two decisive factors for the existence of a critical node and shows that Ni--Mi ≥ 2 is the necessary and sufficient condition for node i being critical. Based on the theorem, a distributed topology partition detection algorithm （distributed partition detection protocol, DPDP） was presented for large scale networks, which achieves the goal of partition detection efficiently by detecting critical nodes in a local area. Theoretic analysis and experiment results show that DPDP has the advantages of low complexity, high accuracy, low cost as well as good scalability, and is superior to other algorithms.