移动自组网的分簇算法研究

摘要本文分析了移动自组网的现有分簇算法，并针对现有分簇算法的不足对ntdr进行了改进，提出了基于按需加权的ntdr（dwntdr）。
关键词：移动自组网,分簇,分簇算法

在移动自组网环境中，分簇的入侵检测系统能有效控制移动节点间的入侵检测通信开销，节约网络资源和节点能量，实现高效协作式检测机制。因此，移动自组网ids采用分簇结构能否高效，ids分簇算法起着非常重要的作用。

2 几种典型移动自组网分簇算法

移动自组网的分簇算法目标就是以较少的计算和通信开销来构造与维护一个簇集合，使其能在覆盖整个网络的同时较好地支持资源管理和路由协议的相互连接，并在网络结构发生变化时生成新的簇结构，确保网络正常通信。在此将对几种典型分簇算法进行阐述。

1. 最小id分簇算法

最小id分簇算法，它由grela和tsai在链路分簇算法（lca）基础上改进而得。该

算法特点是计算简单, 实现方便，算法收敛较快。但是该算法节点消耗的能量多,而且加快了网络出现分割的时间, 同时没有考虑负载平衡等因素。

2. 最高节点度分簇算法

该算法特点是簇数目较少，减少了分组投递时延, 但同时也减少了信道空间重用率。由于簇内节点数不受限制, 并且信道由节点共享, 当簇内节点数量过多时, 每个节点的吞吐量急剧下降。此外, 当节点移动性较强时, 簇头更新频率较高，簇维护开销较大。因此，该算法适合于移动性较弱且节点密度较低的场合。

3. 最小移动性分簇算法

最小移动性分簇算法是节点权值分簇算法的一种，在移动性较强时, 该算法可以明显减少簇头更新频率。它的缺点是节点权重的更新较频繁, 簇头计算开销较大, 并且未考虑负载平衡和节点能量损耗问题。

4．ntdr

该算法优点是分簇时间短，而且为了弥补当原簇头失效的情况，当某一个簇头失效时，会有一个新簇头被迅速选举出来。缺点是产生的簇头数相对过多，系统稳定性不强，原因是节点声明为簇头时没有考虑节点的各方面的综合能力，导致加入该簇的成员相对较少，增加了簇头的个数，同时也增加通信开销。

3 基于按需加权的ntdr（dwntdr）

前三种分簇算法都只是单纯的分簇算法，没有考虑移动自组网入侵检测和军事方面的需要。而ntdr专门应用于军事方面，对于移动自组网入侵检测来说具有更大的实用性。但ntdr产生的簇头数相对过多，系统稳定性不强。因此在此对其进行改进，提出一种基于按需加权的ntdr（dwntdr，on-demand weighting ntdr）。

此算法根据每个节点的权值来选择簇头，权值较小的节点优先成为簇头。在计算节点权值时，综合考虑它的节点度、剩余能量和移动性。为了增加簇结构的稳定性，减少簇头的更新次数，还为原有簇头引人了一定的增量以减小其权值，使其再次被选举为簇头的可能性增加。节点权值的计算公式为:

w（n）=a·|d（n）-m|+b·t（n）+c·m（n）+d·p（n）-x

其中: d（n）表示节点n的节点度，m表示每个簇内理想的簇成员数；t（n）表示节点n担当簇头的时间；m（n）表示节点n的平均移动速度；p（n）表示到所有邻居节点的距离之和；x表示一个增量；a，b，c,d表示加权系数，且满足a+b+c+d=1。

其算法描述为：

（1）网络各节点分配唯一id标识，并分配相同的能量。

（2）一个dwntdr节点如果发现它的附近没有一个簇头节点，或者是它探测到自己可以修复一个网络分割，并且在邻居节点中具有最小w，则认为自己要成为簇头。如果w相同，则选择id最小的为簇头。

（3）每个新的簇头在认定自己为簇头后，则立即声明自己的簇头地位。

（4）其一跳邻居节点中没有加入某个簇的节点成为该簇成员节点，并不再参与分簇。

（5）已经是某个簇的成员节点一般保持簇从属关系不变，但在下列情况发生时，也可以加入此簇头，并不再参与分簇，包括：簇头放弃自己的簇头地位、簇头已经不再列出这个节点、到簇头的链路状况已经恶化到无法接受的程度以及从簇头接收的信号强度过低。

（6）如果簇头同意该节点加入，则向所有其它的簇头发布立即更新后的簇内成员列表，通告其它所有簇头该节点已经属于自己这个簇，明确这个节点的当前位置。如果新加入的节点在加入该簇之前属于另外一个簇，则簇头还要通告该节点以前的簇头，指示该节点已经有了新的簇从属关系。

（7）簇头在自己的剩余能量小于某个规定的阈值时则放弃自己的簇头地 位，不再为簇头。

（8）剩余重复执行（2）～（7）步骤，直到所有节点都属于某个簇。

为了减小簇维护所引入的系统开销，采取按需策略，规定只有当网络中的某个节点与现有的任何簇头都不是相邻节点时，才重新选举簇头。

4 算法模拟与分析

为了便于实现，本文用java语言编制的简单模拟环境来对上述五种分簇算法进行模拟与分析。模拟环境为在一个100×100 单位距离的区域内随机放置n 个节点, 节点移动方向在[0, 2∏]内随机分布, 移动速度在[0,maxv ]内变化。当节点到达区域边界时, 它向区域内反射。节点的数量、传输范围（以单位距离数表示）和移动速度均可根据要求动态调整，模拟时间为10000个单位时间。主要通过不同移动环境下的算法模拟结果来对比分析五种分簇算法的性能，这五种算法分别是最小id算法（lowid）、最大连接度算法（highd）、最小移动性算法（lowm），ntdr、基于按需加权的ntdr（dwntdr）。

在此取网络节点数n=30，maxv=5，节点传输范围从5～60单位距离变化。对于基于按需加权的ntdr，理想的簇成员m=8，a=0.2，b=0.3，c=0.3，d=0.2，x=1，并且节点刚开始的能量是1000能量单位，每单位时间簇头消耗能量0.2%，簇成员为0.05%，能量阈值为100能量单位。

簇头数随节点传输范围的增加而减少, 当传输范围大于30后, 速度逐渐变慢。dwntdr，ntdr的平均簇头数略多于最小移动性和最小id分簇算法的平均簇头数。并且dwntdr的簇头数较ntdr要少, 主要是因为dwntdr比ntdr多考虑了节点度，速度等因素，减少了冗余簇头的产生。

最高节点度分簇算法的单位时间内的簇间转移次数略高于其它分簇算法。而dwntdr单位时间内的簇间转移次数较其它算法要低，由此可以说明dwntdr的簇结构稳定性远大于另外几种分簇算法。

综上所述，通过对不同算法的模拟与分析，可以看出dwntdr分簇算法在稳定性，对网络拓扑变化的适应力等方面要明显优于其它几种算法，而且dwntdr还保留了ntdr算法在原簇头失效时迅速选出新簇头的优点，从而改善了系统的灵活性和通用性，提高了簇结构的稳定性，更加适应移动自组网入侵检测。

5 结束语

本文针对现有移动自组网分簇算法的不足之处在此基础上对ntdr进行了改进，提出基于按需加权的ntdr（dwntdr），该算法综合考虑了影响移动自组网性能的节点度，速度等多种因素，改善了系统的灵活性和通用性，提高了簇结构的稳定性，更适合移动自组网入侵检测系统。

参考文献（略）

本文收集整理于网络，如有侵权请联系客服删除！