Partition detection for large scale ad hoc networks - LI Jian-dong; TIAN Ye; SHENG Min; ZHANG Yan; YAO Jun-liang (Tongxin xuebao)
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 exis-tence 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.