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

　　算法步骤如下：

　　第一步：节点v（）发0号包广播自己的ID号（假设节点的ID号全网唯一），v的邻节点u收到后将其存入自己的1跳邻节点表中。包的格式如表1：

　　第二步：节点v发1号包广播自己的1跳邻节点表；包格式与表1类似，只是将1跳邻节点表附于包尾。

　　第三步：节点v根据收到的所有邻节点的1跳邻节点表，构建自己的2跳拓扑矩阵，由矩阵判断出v是否是2跳拓扑关键节点，如果是，则转第四步。

　　第四步：2跳拓扑关键节点i从自己的1跳邻节点表中随机选取一个邻节点j，向j发送2号包，要求节点j发3号包引发泛洪。3号包格式也与0号包类似，仅多了一个名为“待检测节点”的域，其值为节点i的ID号。节点i不参与转发“待检测节点”域为自己ID号的3号包。其它节点第一次收到关于节点i的3号包时查看i是否为自己的邻节点，若是，就向节点i发送4号包，然后转发该3号包；若不是，则仅转发该3号包。

　　第五步：2跳拓扑关键节点i根据收到的4号包的数目判定i是否为全局关键节点。若收到的4号包的数目与邻节点的数目相等，则说明即使节点i失效，i的所有邻节点之间仍能正常通信，节点i不是全局关键节点；若4号包的数目少于邻节点的数目，则说明节点i是全局关键节点。

　　2关键节点探测算法的性能

　　算法运行一次探测的时间称为算法周期。在每个算法周期内将拓扑信息导出，用深度优先算法计算出图中实际的全局关键节点，与本算法探测结果对比，根据式（1）计算出每一次探测的准确率。静态场景下取一次拓扑即可，移动场景下，在每个算法周期（3s）内，等间隔地取两次拓扑。

　　其中，r表示准确率，M表示图中实际的全局关键节点的数目，N表示本算法探测出的全局关键节点的数目，Nr表示本算法探测出且确实是全局关键节点的数目。

　　2.1静态场景下算法的性能

　　在OPNET环境下随机生成了10000幅含20个节点的连通拓扑图，运行该算法探测全局关键节点，正确率为99.97%；又随机生成了10000幅含50个节点的连通拓扑图，运行该算法，正确率为99.99%。由此可见，在静态情况下，该算法性能极好，完全可以探测到网络中的全局关键节点。

　　2.2移动场景下算法的性能

　　由于该算法探测关键节点需要节点之间进行信息交互，并且在探测到2跳拓扑关键节点后，需要进行泛洪以确定该局部关键节点是否为全局关键节点，因此，算法需要一定的时间才能给出探测结果。而在算法运行的过程中，由于节点的移动性，导致网络拓扑不停地变化，进而影响算法的准确度。所以，算法运行时间要尽量地短，尽可能地跟踪上拓扑的变化，才能保证探测结果的准确性。

　　（1）移动模型

　　在现有的移动模型中，RandomWaypoint（RWP）模型获得了最大的关注，也已经有人分析了它的随机特性和稳态分布[5]。因此，在仿真中采用了这种运动模型。在RWP模型中，首先给每个节点分配一个初始位置（x0，y0），一个目的位置（x1，y1）和速度S，（x0，y0）和（x1，y1）是相互独立地从节点所在的整个区域中均匀选取，速度是从（v0，v1）中均匀选取，与初始位置和目的位置相互独立。节点运动到目的位置后，将被分配一个新的目的位置（服从区域上的均匀分布）和新的速度（服从（v0，v1）上的均匀分布），它们的取值与节点以前所有的位置和速度无关。节点在到达某一个目的位置后，可能停留片刻，也可能立即开往下一个目的地，如果节点停留，那么停留时间将独立于速度和位置。

　　（2）仿真结果

　　笔者在800×800m2的区域内均匀布设了20个节点，通信半径为250m，由式（2）计算出平均节点密度为6.13。

　　其中，ρ表示平均节点密度，n表示网络中的节点数目，l表示正方形区域的边长，R表示节点的通信半径。

　　节点都采用了RWP运动模型，三组仿真中节点的速度分别服从（0.1，1）m/s，（1，10）m/s，（10，20）m/s上的均匀分布，每一组中停留时间分别为无停留（即停留时间为常数0），以及服从（0，20）s、（0，100）s、（0，200）s、（0，300）s上的均匀分布。每种情况下都收集了10000幅拓扑图，但由于部分拓扑图显示网络已分割，所以实际参与准确率计算的拓扑图少于10000幅。在所有连通的拓扑图中根据式（1）计算出每一次探测的准确率，最后取代数平均值，如图2所示：

　　从图2中可以看出，随着移动速度的提高，算法的准确率有所下降，这是由于高速环境下拓扑变化快，周期3s的探测算法已无法紧紧跟踪拓扑的持续变化。在低速环境下，增大节点的停留时间似乎对算法的准确率没有什么影响，但在中速环境下（（10，20）m/s），增大停留时间在一定程度上降低了移动性，进而使得算法的准确率有了很大提高。随着停留时间的增加，网络趋于静态，各种速度下的算法准确率都趋于静态时的准确率。

　　笔者又在2000×2000m2的区域内均匀布设了50个节点，通信半径为400m，平均节点密度为6.28。算法准确率如图3所示：

　　对比图2和图3，可以看出，在同样的速度下，尽管两个场景中节点数目相差较大，但算法的准确率变化不大。仅在（10，20）m/s的环境下，50个节点场景中的准确率略低于20个节点场景中的准确率。以上数据说明，该算法性能稳定，能很好地适应不同规模的网络。

　　3结论

　　在移动性的影响下，AdHoc网络易出现分割，导致通信中断。而网络中的关键节点对网络的连通性有着举足轻重的影响，因此要及时地探测出存在的关键节点。本文提出了一种分布式的关键节点探测算法，并通过仿真表明，在中低速网络中，该算法能以较高的准确率探测出网络中的关键节点，从而为下一步的网络分割预测和连通性补偿工作提供可靠的保证。

　　参考文献：

　　[1]RamRamanathan，JasonRadi.ABriefOverviewofAdHocNetwork：ChallengesandDirections[A].IEEECommunicationMagazine[C].2002：20-22.

　　[2]GoyalD，CafferyJ.PartitioningavoidanceinmobileadHocnetworksusingnetworksurvivabilityconcepts[A].Proc.IEEEInt.Symp.ComputersandCommunicationsISCC[C].2002：553-558.

　　[3]Micha?lHauspie.LocalizedAlgorithmsforDetectionofCriticalNodesandLinksforConnectivityinAdHocNetworks[C].Proc.3rdIFIPMediterraneanAdHocNetworkingWorkshop（MED-HOC-NET2004），2004.

　　[4]ShengMin，LiJiandong，YanShi.CriticalNodesDetectioninMobileAdHocNetworks[C].HWISE2006，20thInternationalconferenceonAdvancedInformationNetworkingandApplications，AINA2006，2006：336-340.

　　[5]NavidiW，CampT.StationaryDistributionsfortheRandomWaypointMobilityModel[J].IEEETransactionsonMobileComputing，2004（1）：99-108.