一种新的移动Ad Hoc网络中的关键节点探测算法

　　【摘要】移动AdHoc网络中的“关键节点”是指那些一旦失效或离开就会导致网络分割的节点，它们对AdHoc网络的连通性有极大的影响。为及时准确地探测到关键节点，进行网络分割预测，提出了一种先在局部范围内进而在全局范围内探测关键节点的算法。仿真结果表明，该算法能以较小的开销、较高的准确率探测到网络中的关键节点，且适用于不同规模的网络。

　　【关键词】AdHoc网络关键节点探测算法

　　MANET[1]（MobileAdHocNetwork，移动AdHoc网络）是由一组无线节点组成的自治集合，它不需要任何预先布设的基础设施（如基站），无中心管理，可临时组织，并且具有高度移动性，可广泛应用于军事通信、紧急救援通信、传感器网络，以及其它需要快速部署、动态组网的通信场合。

　　在AdHoc网络中，节点的移动性导致拓扑快速变化，断链、分割频繁发生。如果需要进行通信的源节点与目的节点恰在不同的分割块中，通信将无法进行，因此确保高动态环境下网络拓扑的连通性是AdHoc网络应用中的一个根本问题。AdHoc网络中会存在一些“关键节点”，该节点或与之相连的某条链路的失效将导致网络成为分割的几部分，如图1所示，节点C即是一个关键节点。可以看出，关键节点会极大地影响网络的连通性。因此，及时准确地探测到关键节点，是进行网络分割预测的前提。

　　目前已有一些算法对关键节点进行研究。文献[2]采用了集中式的Depth-First-Search（DFS，深度优先搜索）算法计算网络中的关键节点，但前提是计算者必须知道整个网络的拓扑，这对于节点具有移动性、拓扑不停变化的AdHoc网络而言，显然效率低、开销大；Micha?lHauspie等人在文献[3]中定义了k跳拓扑关键节点，提出以k跳拓扑关键节点作为全局关键节点的思想，给出了相应的准确率，但并未指出在拓扑动态变化的网络中采用何种标准选取重要参数k；文献[4]中作者提出了基于中点圆的探测算法用于探测局部关键节点，并论证了中点圆以0.196r（r为节点通信半径）为半径时将获得最高的准确率。

　　本文提出了一种先在局部范围，进而在全局范围内探测关键节点的分布式算法，有效地减少了探测关键节点的开销，并通过仿真验证了本算法能在中低速网络中以较高的准确率探测到关键节点。

　　1关键节点探测算法

　　1.1关键节点探测算法的理论依据

　　依据图论，可将网络模拟成一个图，其中V代表网络中的节点集，E代表链路集，当且仅当节点u，v∈V在彼此的通信范围内时，存在边。这里假设所有的边都是双向的，即若，则，且假设网络中最大跳数为K跳。

　　定义1：当且仅当两个节点之间的最短路径为k（1≤k≤K）跳时，它们互为k跳邻节点（1跳邻节点简称为邻节点）。由节点v及v的所有i（1≤i≤k）跳邻节点以及这些节点之间的链路（不包括k跳邻节点之间的链路）构成节点v的k跳拓扑子图[3]。

　　定义2：如果在节点v的k跳拓扑子图中去掉v及与其直接相连的链路将导致子图断开，就称节点v为k跳拓扑关键节点[3]，也可称为局部关键节点。k=K时称节点v为全局关键节点。

　　由以上定义可以看出，在图1中，方形框选中的节点C即为全局关键节点，多边形框内的节点均为2跳拓扑关键节点，即局部关键节点。

　　从全局关键节点与局部关键节点的定义可以看出，二者的作用范围不同，全局关键节点易导致整个网络分割，而局部关键节点易导致本节点的k跳拓扑子图不连通。因此，一个节点如果是全局关键节点，则它必定也是局部关键节点，而一个局部关键节点则可能成为全局关键节点。

　　命题1：在节点v的k跳拓扑子图中，如果存在节点i，j满足且i，j之间的所有路径上都包含节点v，则节点v是k跳拓扑关键节点。若k=K，则节点v是全局关键节点。

　　证明：假设在节点v的k跳拓扑子图中，存在节点i，j满足且i，j之间的所有路径上都包含节点v，则若v失效（即挪去节点v以及与其相连的链路），i和j将无法连通，不可能出现在同一个连通块中，因此节点v的k跳拓扑子图必分割成至少两个连通块。所以，v是k跳拓扑关键节点，命题成立。

　　命题2：在节点v的k跳拓扑子图中，当且仅当所有满足的节点i，j之间都存在一条不包含节点v的路径时，节点v不是k跳拓扑关键节点。若k=K，则节点v不是全局关键节点。

　　证明：先证充分性。假设在节点v的k跳拓扑子图中，所有满足的节点i，j之间都存在一条不包含节点v的路径。则即使v失效，这些节点仍可以通过各自的不经过v的路径而连通，因此仍在一个连通块中，节点v的k跳拓扑子图没有分割。所以，v不是k跳拓扑关键节点。

　　再证必要性。因为v不是k跳拓扑关键节点，所以挪去v及与其直接相连的链路，子图应仍是连通的，即子图中的所有节点对之间都至少存在一条路径，则所有满足的节点i，j之间也都存在一条路径，且这条路径上不包含v。所以，命题2成立。

　　命题3：若节点v不是k（1≤k≤K）跳拓扑关键节点，则节点v必定不是全局关键节点。

　　证明：若节点v不是k（1≤k≤K）跳拓扑关键节点，则由命题2可知，在节点v的k跳拓扑子图中，所有满足的节点i，j之间都存在一条不包含节点v的路径。而节点v的k跳拓扑子图是v的K跳拓扑子图的一个子集，因此所有满足的节点i，j以及它们之间的不包含节点v的路径都包含于节点v的K跳拓扑子图，根据命题2可知，节点v不是全局关键节点，命题成立。

　　1.2全局关键节点探测算法的描述

　　基于全局关键节点与局部关键节点的关系，本文采用了先在局部范围内探测k跳拓扑关键节点，再针对出现的k跳拓扑关键节点发起泛洪，在全局范围内检测该节点是否为全局关键节点的算法，这里选取k=2。因为k值过大将导致局部探测时间过长而使得算法无法跟踪快速变化的网络拓扑，k值过小又不能有效地减少需进行全局检测的节点数目也就使得泛洪开销过大。而由实验获知70%以上的2跳拓扑关键节点确实是全局关键节点[3]，因此折衷后取k=2。该算法是分布式的，每个节点可独立启动算法，根据收集到的其它节点给予的各种反馈信息做出自我判断。在此假设数据包的传送是完全可靠的。