移动自组网中基于按需加权的NTDR分簇算法

胡波

1 福建省财税信息中心 福建 350003

2 中南大学信息科学与工程学院 湖南 410083

0 引言

在移动自组网环境中，分簇的入侵检测系统能有效控制移动节点间通信开销，节约网络资源和节点能量，实现高效协作式检测机制。因此，移动自组网IDS采用分簇结构能否高效，分簇算法成为实现的关键技术之一。

1 分簇定义及分簇算法目标

移动自组网分簇是一种将节点分成逻辑上独立的组的一种机制。分簇算法目标是以较少的计算和通信开销来构造与维护一个簇集合，使其能在覆盖整个网络的同时较好地支持资源管理和路由协议的相互连接，并在网络结构发生变化时生成新的簇结构，确保网络正常通信。为减少分簇开销，分簇算法应简单高效，理想情况下希望以最少的簇头覆盖整个网络。分簇算法在拓扑侦听的基础上完成分簇形成和分簇连接。

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

2.1 最小ID分簇算法

最小 ID分簇算法工作过程为：①网络各节点分配惟一ID标识。②选择具有最小ID的节点作簇头。③其一跳邻居节点成为该簇成员节点，并不再参与分簇。④剩余重复执行②，③步骤，直到所有节点都属于某个簇。该算法特点是计算简单，算法收敛较快；在移动环境下，簇头更新频率较慢，簇维护开销较小。但该算法倾向选择ID较小的节点为簇头，导致这些节点耗能较多，且没有考虑负载平衡等因素。

2.2 最高节点度分簇算法

最高节点度分簇算法的目标是提高网络控制能力和减少簇的数目。算法工作过程为最小 ID分簇算法步骤②改为选择具有连接度最大的节点作为簇头，节点度相同时选择ID较小的节点为簇头，其他步骤一样。该算法特点是簇数目较少，减少了分组投递时延与信道空间重用率。由于簇内节点数不受限制，且信道由节点共享，当簇内节点数量过多时，每个节点吞吐量急剧下降。此外，当节点移动性较强时，簇头更新频率较高，簇维护开销较大。

2.3 最小移动性分簇算法

最小移动性分簇算法是节点权值分簇算法的一种，即按照一定规则给网络中每个节点赋予权值，依据权值选取簇头。算法工作过程为最小 ID分簇算法步骤②选择相邻节点中具有最大权值的节点被选作簇头，权值相同时选择 ID 较小的节点为簇头。在移动性较强时，该算法可明显减少簇头更新频率，缺点是节点权重更新较频繁，簇头计算开销较大，且未考虑负载平衡和节点能量损耗问题。

2.4 NTDR

NTDR不仅是一种分簇算法，而且还是一种簇运行控制算法。算法工作过程如下：①一个节点如果发现它附近无簇头节点，或探测到自己可修复一个网络分割，则认为自己要成为簇头。②为防止同时有多个节点做出反应导致簇头“竞争”，该节点等待一段随机时间间隔后重测，当条件仍然为真时认定自己是簇头。③每个新簇头在认定自己为簇头后，立即声明簇头地位。④没有加入某个簇的节点根据一定原则选择是否加入某个簇。⑤已经是某个簇的成员节点一般保持簇从属关系不变，但在下列情况发生时，也根据④寻找新的从属关系，包括簇头放弃簇头地位、簇头已经不再列出这个节点、到簇头的链路状况已经恶化到无法接受的程度以及从簇头接收信号强度过低。⑥如果簇头同意该节点加入，则向所有其它的簇头发布更新后的簇内成员列表，通告该节点已经属于自己这个簇。如果新加入的节点在加入该簇之前属于另外一个簇，则簇头还要通告该节点以前的簇头。该算法优点是分簇时间短，且为弥补原簇头失效情况，当某一个簇头失效时，会有一个新簇头被迅速选举出来。缺点是产生的簇头数相对过多，系统稳定性不强，原因是节点声明为簇头时没有考虑节点各方面的综合能力，导致加入该簇的成员相对较少，增加了簇头的个数与通信开销。

3 基于按需加权的NTDR(DWNTDR)

对于移动自组网入侵检测来说，NTDR相对其他分簇算法具有更大的实用性。但NTDR产生的簇头数相对过多，系统稳定性不强。因此在此对其进行改进，提出一种基于按需加权的NTDR(DWNTDR, On-demand Weighting NTDR)。

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

其中：①D(n)，节点n的节点度，M表示每个簇内理想的簇成员数。②T(n)，节点n担当簇头的时间。③M(n)，节点n的平均移动速度。④P(n)，到所有邻居节点距离之和。⑤x表示一个增量。如果在上一次选举时，节点n被选为簇头，则在本次选举时，为其权值附加这个增量。若在上次选举中节点n为簇成员，则权值的计算公式中不包含这个增量。⑥a，b，c，d表示加权系数，且满足a+b+c+d=1。

其算法描述为：①网络各节点分配惟一 ID标识，并分配相同的能量。②一个节点如果发现附近无簇头节点，或探测到自己可以修复一个网络分割，并且在邻居节点中具有最小W，则认为自己要成为簇头。如果W相同，则选择ID最小的为簇头。③每个新的簇头在认定自己为簇头后，立即声明自己的簇头地位。④其一跳邻居节点中没有加入某个簇的节点成为该簇成员节点，并不再参与分簇。⑤⑥与NTDR算法相同。⑦簇头在自己剩余能量小于某个规定阈值时则放弃自己的簇头地位。⑧剩余重复执行②～⑦步骤，直到所有节点都属于某个簇。当分簇完成后，如果簇头失效，则立即在此簇中剩余能量大于某个规定阈值的节点中选举具有最小W的节点为新簇头，如果W相同，则选择ID最小的为新簇头。

4 算法模拟与分析

4.1 模拟假设前提和模拟环境

4.1.1 模拟假设前提

（1）网络中所有节点是对等节点，各节点随机部署在网络中，且每个节点在网络中具有惟一ID号。

（2）各节点通信能力相同，并能和通信范围内其它节点正常通信，不考虑背景噪声和分组传输差错等因素的影响。

（3）节点无线通信能力有限，即节点传输距离有限制。

（4）节点之间连接对称。即连接的两个节点 V1和 V2可以互相通信。为了更好地比较，各节点初始位置相同，并且五种算法均采用按需更新簇头的簇维护策略。

4.1.2 模拟环境

模拟环境为在一个 100×100 单位距离的区域内随机放置N 个节点，节点移动方向在[0, 2∏]内随机分布，移动速度在[0,maxV]内变化。当节点到达区域边界时，它向区域内反射。节点的数量、传输范围(以单位距离数表示)和移动速度均可根据要求动态调整，模拟时间为10000个单位时间。

4.2 算法性能评价指标

（1）平均簇数。簇数是指整个网络所包含的簇数目，决定了网络中路径的平均长度，对入侵检测性能有直接影响，在仿真中对其求平均值得到平均簇数。

（2）单位时间内簇头更新次数。一次簇头更新指某个节点由簇头变为簇成员或由簇成员变为簇头。此指标用来说明重新运行分簇算法的频率，该指标在很大程度上决定分簇算法性能。

（3）单位时间内簇间转移次数。簇间转移次数是指簇成员在不同簇之间移动的次数。该指标用于说明在重新计算统治集的时间间隔内簇维护开销。

4.3 模拟结果比较和分析

通过算法模拟结果来对比分析五种算法性能，这五种算法分别是最小 ID 算法(LowID)、最高连接度算法(HighD)、最小移动性算法(LowM)，NTDR、基于按需加权的 NTDR(DWNTDR)。在此取网络节点数N=30，maxV=5，节点传输范围从5～60单位距离变化。对于DWNTDR，理想的簇成员M=8，a=0.2，b=0.3，c=0.3，d=0.2，x=1，并且节点刚开始的能量是1000能量单位，每单位时间簇头消耗能量0.2%，簇成员为0.05%，能量阈值为100能量单位。

图1给出不同分簇算法平均簇头数随节点传输范围的变化情况。从图1看出，簇头数随节点传输范围增加而减少，当传输范围大于30后，速度逐渐变慢。并且HighD算法得到的平均簇数明显偏低，因为这种算法选择节点度较高的节点成为簇头，这样单个簇内所包含的节点数就较多，产生较少的簇，从而降低分组投递延迟，简化簇结构的管理。但较少簇数也会降低信道的空间重用率，同时单个簇内的节点数过多会使簇头负担加重。同时 DWNTDR，NTDR的平均簇头数略多于LowM和LowID算法的平均簇头数。并且DWNTDR的簇头数较NTDR要少，主要是因为DWNTDR比NTDR多考虑了节点度，速度等因素，减少了冗余簇头的产生。

图1 平均簇头数随传输范围的变化

图2给出了不同分簇算法单位时间内簇头更新次数随节点传输范围的变化情况。从图2数据显示，当节点的传输范围非常小时，簇数较多，簇成员与簇头的距离很近，节点离开原簇的概率较小，因此单位时间内簇头更新次数较低。随着传输范围增加，单位时间内簇头更新次数逐渐增加，并在10左右达到峰值。随着节点传输范围的进一步增大反而使单位时间内簇头更新次数降低，这是因为尽管节点仍然保持移动状态，但由于簇头传输范围较大，节点移出统治域的概率减小。从图2还可以看出，由于节点移动使各节点的节点度不断变化，造成HighD分簇算法单位时间内的簇头更新次数明显大于其它几种分簇算法，而DWNTDR分簇算法单位时间内簇头更新次数较其它算法都要小，并且 DWNTDR的簇头更新次数明显小于NTDR，这就降低了簇头更新引入的系统开销，说明此算法稳定性要优于其它几种算法。

图2 单位时间内簇头更新次数

图3给出不同分簇算法单位时间内簇间转移次数随节点传输范围的变化情况。与图2相同的原因，单位时间内簇间转移次数先上升达到峰值再单调下降。并在传输范围为 25左右达到最大值。从图3可以看出，各算法的性能差别较小。其中HighD分簇算法单位时间内簇间转移次数略高于其它算法。而DWNTDR单位时间内的簇间转移次数较其它算法要低，由此可以说明DWNTDR的簇结构稳定性远大于另外几种分簇算法。

图3 单位时间内簇间转移次数

5 结论

本文通过对移动自组网络拓扑结构的分析，决定将簇结构用于移动自组网入侵检测系统中，并分析几种现有分簇算法。针对现有移动自组网分簇算法的不足之处再在此基础上对 NTDR进行改进，提出基于按需加权的 NTDR(DWNTDR)，并模拟各分簇算法。通过对各分簇算法的性能评价指标的分析和比较，剖析了这些算法的优缺点。由于DWNTDR综合考虑了影响移动自组网网络性能的多种因素，采用按需簇维护策略，单位时间内的簇头更新次数和簇间转移次数都明显少于另外几种分簇算法，而且能够在原簇头失效时迅速选出新簇头，从而改善了系统的灵活性和通用性，提高了簇结构的稳定性，更加适应于移动自组网的入侵检测。

[1] 吴迪,李晴,冯永新,王光兴.一种基于地理定位信息的 Ad Hoc分簇算法.计算机工程与应用.2005.

[2] 王寒凝,王亚弟,费晓飞,韩继红.移动自组网中一种基于分簇的信任评估方案.计算机科学.2006.