基于能量模型的多权值分簇算法

韩 波，郑 凯

(华东师范大学 计算机科学与软件工程学院，上海 200062)

0 引 言

移动自组织网络(mobile ad-hoc network，MANET)是由若干自由移动的节点组成的一个多跳、自组织、无中心、临时性的自治系统[1]。MANET网络根据拓扑结构的不同分为两类：一类是平面结构，该结构所有节点的地位是平等的，不同节点之间可存在多条路径，但网络开销会随着节点数目的增加而急剧增大，所以此类网络的可扩展性较差，适用于小规模的网络;另一类是层次结构，该结构是由多个簇组成，节点被分为簇首和簇成员，簇首节点具有路由决策和路由转发功能，簇成员节点只具备发送和接收功能。在网络中引入分层结构，将网络划分为簇，可以方便网络的资源管理，灵活地分配各种资源，可扩展性好，适用于大规模网络。分簇机制减少了节点之间的控制信息开销和路由开销，拓扑结构的变化更加容易控制，降低了节点能量消耗，增加了网络容量和生命周期[2-3]，因此逐渐成为网络研究的热点。

到目前为止，研究人员已经提出了多种分簇算法，如最高节点度启发式算法,该算法仅仅根据节点的度数选举簇头节点，算法运行速度快，但容易导致单个节点负担过重，减少了簇的生存时间。加权分簇算法WCA[4]，考虑节点的度数、节点移动性等因素，选择较优的节点担任簇头，增加了网络的稳定性，但节点的计算复杂，影响了分簇速度，未考虑簇头节点数量的最小化原则，降低了网络的收敛时间。S-LEACH算法[5]在簇形成阶段采用分布式协商策略，在簇维护阶段采用集中式处理策略，这两种方式可以避免节点死亡时的网络中断。WCACDS算法根据组合权值衡量节点性能，利用改进后的连通支配集算法进行分簇，减少了簇头数量，增强了簇头性能，提高了网络负载平衡能力。这些算法各有优缺点和应用场景[6-7]。在上述研究的基础上，文中提出一种具有通用性的分簇算法：自适应按需加权分簇算法。

1 自适应按需加权分簇算法

1.1 算法概述

自适应按需加权分簇算法(adaptive on-demand weighting，AOW)[8]依据节点度数、节点能量、节点移动性和节点距离等参数，通过权值因子的调整以适应各种网络，如式1，因此具有广泛的适用性。AOW算法要求节点工作于半双工模式且每个节点具有唯一的ID号，该算法执行期间，网络的拓扑结构需要保持稳定状态。

wn=c1Δn+c2Dn+c3Vn+c4En

(1)

其中，Δn表示节点的差异度，Dn表示节点与邻居节点距离之和，Vn表示节点移动速率，En表示节点的能量值，进而反映了节点的能量消耗状态；c1、c2、c3和c4为对应不同参数的权值因子，并且满足c1+c2+c3+c4=1。

1.2 AOW算法存在的问题

AOW算法虽然综合考虑了节点的多个权值，使簇头的选举更加合理，但仍存在以下问题：

(1)AOW算法的权重选择没有考虑到节点本身处理能力，节点的权重计算都是假定所有节点处理能力都一样这个前提(即节点是同构的)，而真实的情况却是网络节点的处理能力差别很大，即节点是异构的，分簇时应考虑节点处理能力的差异。

(2)AOW算法计算节点移动速率是以每个节点在一个时间周期T内的绝对速率的累积值作为参数，这种方法仅能说明这一节点相对于上一个位置的状态变化，不能反映它相对于整个簇的稳定性情况，因此具有一定的局限性，应该考虑相对于所有邻居节点的移动更为合理。

(3)AOW算法只考虑了各节点的剩余能量，没有从整体能量消耗最小的角度来规划算法。

2 基于能量模型的多权值分簇算法

2.1 MANET网络的能量模型

为了设计一种整体能量消耗最小的分簇算法，引入了MANET网络的能量模型。MANET网络节点的总通信能量消耗包括发送消息能耗、接收消息能耗、侦听能耗和控制报文能耗。

根据MANET网络能量消耗的组成部分可知，让节点处于睡眠状态时，可以降低节点的能量消耗，因此应该在保证网络正常运行的情况下尽可能地减少节点发送和接收消息包的时间，网络的能量浪费主要出现在以下几个方面：

(1)侦听能耗是指节点处于空闲状态时，为了识别可能会传给自己的数据进行信道侦测所消耗的能量。这种侦听的目的是保证需要接收数据时，节点能够及时完成接收状态的转换，不过长时间侦听信道会浪费能量，因此可以在节点不需要发送和接收消息时使节点处于睡眠状态以节省能量消耗。

(2)控制消息的开销：在MANET网络的分簇过程中都需要发送一定数量的控制消息包，这些消息包是额外开销，不是最终用户或者应用所需要的数据，因此分簇算法的设计过程中应该尽量减少以降低能量损耗。

文中均假设无线信道是完全对称的，即双向信道的通信能耗相同。考虑LEACH[9]协议使用的无线网络能量模型，在这个模型下节点总能量消耗主要包括驱动电路的能耗Eelec、发送能耗ETx(k,d)和接收能耗ERx(k)，其中Eelec与电路的硬件设计有关，例如数字编码、信号调制解调、滤波器和带宽不同，电路的消耗也不同。根据通信距离d与通信阈值d0之间的关系，分为自由空间(free space)和多径衰落(multipath fading)两种信道模型。在距离d的两个节点间传输k比特消息时，ETx(k,d)和ERx(k)的计算如式2和式3，节点的侦听能耗Esense(k)的计算如式4。

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=

(2)

ERx(k)=ERx-elec(k)=kEelec

(3)

Esense(k)=α1k

(4)

在节点一致的情况下，Eelec是一个常数。从式2～4中可以看出，发送能耗、接收能耗以及侦听能耗与数据量成正比。

2.2 基于能量模型的多权值分簇算法

针对AOW算法存在的问题，结合节点能量模型，提出一种基于能量模型的多权值分簇算法(Energy-AOW，EAOW)。算法中包含五个参数：节点度数(D)、节点传输功率(P)、节点移动性(M)、节点剩余能量(E)和节点处理能力(A)。相比AOW算法有如下改进：

(1)结合节点的能量消耗模型，使簇头的选举更加依赖于节点能量这个关键因素，提高了节点的生命周期，优化了节点在生命周期的能量消耗，减少了能量的浪费。

(2)在簇头选举成功后，选举权值仅小于簇头的节点担任候选簇头，当簇区域发生变化时，候选簇头节点可以迅速担任新的簇头，划分新的簇区域，通过这种替代机制可以减少节点间的消息传递次数，缩短节点成簇时间。

(3)通过优化权值的计算方法，提高了分簇的效率和准确性，使分簇的统治集更加均匀，每个簇的节点数目保持在合理水平，采用相对移动性，使簇头的选择更加合理，节点剩余能量参数可以使能量最高的节点成为簇头，提高簇的整体生存时间。

2.3 算法描述

EAOW算法选举簇头时根据节点的五个权值，并在这五个权值赋上相应的权值因子，权值因子可以根据环境系统的变化进行动态调整，然后计算每个节点的综合权重，与邻居节点的权重值进行比较，依据选举规则，最后选出簇头节点和候选簇头节点，从而划分成不同的簇区域。

2.3.1 簇头选举算法流程

算法流程如图1所示。

图1 算法流程

具体权值计算如下描述：

(1)节点度数的计算。

每个节点v根据其相邻节点的数目确定相应的度数值，在实际计算过程中，计算其节点度数与理想度数σ之间的差值作为参数，记为：

Dv=|dv-σ|

(5)

其中，dv为节点的平均度数，表示相邻范围内邻居节点的数目，计算如式6：

(6)

其中，T表示节点总数;H(v,v′)表示节点收到不同邻居消息包的次数。

(2)节点相对移动性的计算。

(7)

其中

(8)

(3)节点功率的计算。

节点功率可能在运行过程中发生变化，所以考虑使用节点覆盖范围表示节点的发射和接收功率，覆盖范围为节点到所有邻居节点的总和的均值，故节点功率Pv的计算公式为：

(4)节点剩余能量的计算。

节点剩余能量是簇头选举的关键参数，对于簇头节点，它的能量消耗远远大于普通节点，能量值的变化会影响簇头选举过程，节点剩余能量Ev计算公式为：

Ev=Ei-ETx(k,d)-ERx(k)-Esense(k)

(10)

其中，Ei为节点的初始能量；ETx(k,d)为节点发送的能量消耗；ERx(k)为节点接收的能量消耗；Esense(k)为节点侦听的能量消耗。

(5)节点处理能力的计算。

节点的处理能力与多种因素相关，在仿真试验中人为将节点的处理能力划分为不同的等级，其中最低等级配置的节点处理能力Av设为1，其他节点的处理能力值随性能指标的提高依次递增。

(6)计算每个节点v在多权值条件下，根据权值因子得到的组合权值：

Wv=w1Dv+w2Mv+w3Pv+w4Ev+w5Av

(11)

(7)每个节点计算出自己的组合权值，然后相邻间节点的权值做比较，权值最大的作为簇头节点，权值次大的作为候选簇头节点，当有多个最大权值相等时，比较节点度数，以节点度数大的作为簇头节点，本簇内的成员节点为与簇头相邻的一跳节点，已经划分到簇内的普通节点不能成为簇头节点，但可以成为簇间网关节点。

(8)依次进行上述过程，直到网络中的所有节点划分完毕，产生簇头节点、簇成员节点、候选簇头节点或者簇间节点。

2.3.2 簇结构的形成与更新维护过程

该算法是一种动态变化、分步计算的加权分簇算法，每一个节点都有唯一的ID号，作为节点的标识。节点Vi使用CH(Vi)作为簇头节点宣告消息，使用Jo(Vi,Vj)请求加入簇头节点Vi的簇内，成为该簇的簇成员节点。当Vi为簇头节点时，则用Ac(Vi,Vj)消息接受节点Vi的入簇请求，或者使用Re(Vi,Vj)消息拒绝节点Vj的入簇请求，以下为分簇算法的具体阶段。

(1)簇结构的初始化阶段。

首先，由于所有节点处于初始化状态，此时所有节点的状态位为未决定状态(Undecide)，由于节点的相对移动性无法立即计算出来，所以在初始化阶段使用最小节点ID分簇算法，通过Hello消息包中的ID号判断簇头节点，初始化完成以后，当无线网络中的节点出现变化时，各个节点通过Hello消息包向相邻节点传递本节点的相关信息，各个节点之间通过权值的比较来执行相应的子过程。

(2)簇结构的建立阶段。

①如果节点Vi通过Hello消息包中的权值信息判断出自己比相邻节点Vj的权值大时，则向邻居节点Vj发送CH(Vi)消息，同时将节点状态位标为簇头状态(ClusterHead)，并向相邻的邻居节点发送入簇请求Jo(Vi,Vj)，直到所有节点都加入簇，即Ac(Vi,Vj)=N(v)。

②如果节点Vi通过Hello消息包中的权值信息判断自己比相邻节点Vj的权值小且节点Vj发送了CH(Vj)消息包，则节点Vi可知Vj为簇头节点，然后向节点Vj发送Jo(Vi,Vj)入簇请求，如果节点Vi收到节点Vj发送的Ac(Vj,Vi)允许加入消息或者在节点Vj的Hello消息中找到了本节点的ID标识号，则表示节点Vi可以加入以节点Vj为簇头的簇中，此时节点Vi会在发出的Hello消息中设置其为成员节点和簇头节点的ID号，同时节点Vi的状态位设置为簇成员状态(Member)。

③如果节点Vi通过Hello消息包中的权值判断自己比相邻节点Vj的权值大，可是所有邻居节点所在簇可用度数为零时，或者没有成员节点加入该簇时，则节点Vi会发出CH(Vi)消息表明自己单独成为簇头，同时节点Vi的状态位设置为簇头状态(ClusterHead)。

(3)簇结构的更新维护阶段。

①如果一个新节点加入网络时，它首先要向邻居节点广播Hello消息，Hello消息中包含了节点的所有权值信息，依据分簇算法计算节点的组合权值，同时与簇内的簇头节点和候选簇头节点的权值相比较，如果新节点权值比簇头节点权值大，则宣告自己成为新的簇头节点；否则，与候选簇头节点权值进行比较，如果大于候选簇头节点权值，则宣告自己成为候选簇头节点；否则，新节点为普通簇成员节点。

②当一个节点要退出簇时，如果是簇首节点，则候选簇头节点直接成为新的簇头节点，并向簇内其他节点广播；如果是非簇头节点，只需要它的所有邻居节点在邻居表中删除该节点即可；如果是候选簇头节点，则需要在簇成员节点中重新选举候选簇头节点。

③当一个簇成员节点发生移动时，如果该节点收到新簇头发出的宣告消息，但失去了原簇头的消息，则直接加入该簇，此时与新节点入簇情况相同；若仍能收到原簇头消息，则该节点成为簇间网关节点，同时在新簇内选举簇头节点和候选簇头节点。

3 算法性能仿真

结合两种广泛应用的最小节点ID算法[11](LOWID)和最高节点度算法[12](HIGHD)，通过相应的比较，验证EAOW算法的有效性和可行性。

3.1 性能评价指标

分簇算法的性能评估指标用于评估算法运行的效率，主要有以下几种[13]：

(1)簇头节点变化频率：表示单位时间内簇头节点的更新变化次数。

(2)节点状态变化频率：表示单位时间内节点位置移动后在簇间产生切换的次数。

(3)统治集更新频率：表示簇结构的变化频率。

(4)节点成簇时间：表示所有节点完成分簇所花费的时间成本，代表了分簇算法的效率。

3.2 仿真参数配置

为了获知分簇算法的性能，将使用NS2[14]进行仿真实验，参数配置如表1所示。

表1 节点参数设置

3.3 仿真结果的比较与分析

根据以上节点参数，使用仿真软件对算法进行仿真实验。

测试一：簇头变化率与通信范围。

不同通信范围下的簇头变化率如图2所示。

图2 不同通信范围下的簇头变化率

从仿真实验可以看出，随着节点通信范围的扩大，簇头变化率呈现先增大后减少的趋势，这是由于通信距离增加后，簇头的选举竞争减少，簇头的数目会减少，簇头之间的距离增加，因此簇头的变化率减少。通过四种分簇算法的对比，显示EAOW算法相比于其他三种算法有一定的提高，减少了簇头的变化率，提高了簇的稳定性。

测试二：统治集更新频率与节点速率。

不同节点速率下的统治集更新频率如图3所示。

图3 不同节点速率下的统治集更新频率

当节点速率增加时，簇的稳定性降低，导致簇头的竞争选举概率增大，统治集更新频繁，从而统治集更新的频率增加。随着节点速率的增大，簇头之间选举频繁，簇头的变化率提高，统治集的更新加快。从实验结果可以看出，EAOW算法的统治集更新频率低于其他分簇算法，因为该算法考虑了节点的相对移动性，使分簇更加合理，从而优于其他三种算法。

测试三：节点状态变化率与节点速率。

不同节点速率下的节点状态变化率如图4所示。

从仿真结果看，EAOW算法在节点速率增大的过程中，节点状态变化率低于前三种算法，说明此算法具有良好的分簇结构，能适应网络的动态变化，由于EAOW算法充分考虑了节点的相对移动性，当节点出现动态移动时，能够保持较低的节点状态变化率，说明了改进算法的有效性。

图4 不同节点速率下的节点状态变化率

测试四：节点成簇时间与节点数目。

不同节点数目下的节点成簇时间如图5所示。

图5 不同节点数目下的节点成簇时间

从实验可以看出，当节点数目较少时，四种分簇算法的成簇时间差别很小，当节点数目增多时，成簇时间明显增加。由于EAOW算法的分簇过程使用了候选簇头节点的策略，所以节点的成簇时间低于AOW算法，这体现了候选簇头在分簇中的优势，验证了改进算法的有效性。

4 结束语

提出了一种基于能量模型的多权值分簇算法EAOW，该算法是对AOW算法的改进，通过考虑网络的整体能量消耗，增加和调整了簇头选择时考虑的条件因子，通过组合权值的计算，优化了簇头选举策略，提高了分簇的性能和效率，减少了节点的能量消耗，提高了节点的生存时间，并通过仿真验证了该算法的优越性。

目前的工作只涉及分簇算法本身，尚未与路由结合。因此结合路由选择算法，基于分簇的路由将是下一步的研究工作。