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

Partition detection for large scale ad hoc networks

作　　者：李建东[1] 田野[1] 盛敏[1] 张琰[1] 姚俊良[1] 

机构地区：[1]西安电子科技大学ISN国家重点实验室信息科学研究所,陕西西安710071

出　　处：《通信学报》2008年第9期54-61,共8页Journal on Communications

基　　金：国家自然科学基金资助项目(60572146);国家杰出青年科学基金资助项目(60725105);新世纪优秀人才支持计划项目;教育部科学技术研究重点基金资助项目(107103);国家高技术研究发展计划("863"计划)基金资助项目(2007AA01Z217);高等学校博士学科点专项科研基金资助项目(20050701007);高等学校优秀青年教师教学科研奖励计划基金资助项目;高等学校科学创新引智计划基金资助项目(B08038)~~

摘　　要：针对网络中极易导致网络拓扑分割的关键节点,首先证明了关键节点的判定准则,它从本质上揭示了关键节点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.

关 键 词：无线AD HOC网络 大规模 分割探测 关键节点 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]