一种基于能量平衡的分簇算法

黄成兵

(阿坝师范学院 计算机科学系,四川 汶川 623002)



一种基于能量平衡的分簇算法

黄成兵

(阿坝师范学院 计算机科学系,四川 汶川 623002)

针对簇结构形成后的稳定性问题，分析当前移动自组织网络中常见分簇算法的不足，提出了一种基于能量平衡的分簇算法。该算法在分簇过程中选簇首时，尽量减少信息交互次数，选取能量最优且离汇聚节点最近的节点为簇首，形成一个完整的簇。结果表明，该算法能够节约节点能量，使簇结构稳定时间最长。

分簇算法；能量平衡；移动自组网；簇稳定性

移动自组网又称为移动Ad Hoc网络，是一种由若干个既充当路由功能又充当节点功能的无线终端组成的网络，其特点是自组织、多跳和无需骨干网支撑，广泛应用在世界各国的应急救灾、军事通讯、交通预警[1]及深海探测等不方便搭建基础设施的重要领域。其抗毁性极强，具有十分重要的应用前景。最初移动自组网的结构采用所有节点都对等的平面式结构，即每个节点均有路由器和终端两项功能。这种方式的最大优点是在源节点和目的节点之间实现多条通信路径，减少拥塞。但由于移动自组网具有动态拓扑(节点随处移动导致时常有新节点加入或退出网络)、能量有限(依靠电池供电)及带宽有限等特点，当节点数目增多时就会带来路由开销大、可扩展性差、移动管理复杂等问题。因而平面结构只适用于节点数较少的移动自组网。对于节点数较多的移动自组网，则应采用相应的分簇算法构成分层拓扑结构。通过不同的分簇算法，使相邻的一组节点组成一个簇，簇内节点有簇首、网关和簇成员三种身份。处于相同簇内的各成员之间通信只需要经过簇首即可完成。处于不同簇内的多个节点之间进行通信，则需要通过各簇的网关节点进行转发。相比平面结构而言，分层拓扑具有扩展性强、减少控制开销、易于管理和优化带宽等优点。

1 常见分簇算法及不足

分簇算法的目标是使用尽量简单高效的算法建立起稳定且覆盖全网的簇集合。这些簇应具有良好的稳定性及抗毁性，同时在链路容量许可的情况下簇首节点的数量应尽可能少。早期典型的分簇算法主要有最小标识优先算法(Lowest-ID)[2]和最大连接度(Max-Degree)优先算法[3]。它们均以移动自组网中某单个因素作为簇首的选取条件。如最小标识优先算法以ID值小的节点为簇首，最大连接度优先算法以连接度最多的节点为簇首，这样导致网络性能较差且缺乏公平性。后来有研究者对这两个基本算法加以改进，如基于权值的分簇算法(DCA)[4]，它假设每个节点有唯一的权值，权值综合考虑了节点连接度和标识等因素，最后取邻居节点中权值最大的节点作为簇首，但作者并未对权值的计算作深入的讨论。文献[5]中也曾提到基于能量均衡的分簇算法，该算法在进行簇首选举时，选举剩余能量高于平均能量的节点成为簇首。该算法虽能够保证所选举出的簇首能量相对较优，但因簇首结点可能会过多而形成更多的簇。相比平面结构而言，分簇的优势不能够得到很好的体现。另外还有一些算法，其簇首的选择与ID或最大连接度无关[6]，如基于节点位置预测的分簇算[7]、基于节点移动性的分簇算法、基于链路稳定性的分簇算法、基于模式识别的分簇算法等[8]。这些算法都因需要增加额外设备、应用环境要求较高、实现极其复杂等原因，在应用中仍末获得较理想的效果，还需进一步完善。

2 基于能量平衡的分簇算法

经分析，现有移动自组网分簇算法存在各种缺陷或不足。受移动自组网自身能量十分有限且节点随机移动性等特点制约，对移动自组网网络结构研究的最终目的，就是为了在快速可靠的基础上，找到尽可能长时间维持网络结构不变的分簇算法，更长时间维护每个通信节点的生命周期。因而，节能、稳定成为分簇研究时最需要考虑的问题。前面提到的几个分簇算法，对于节能的考虑，主要是从单个节点的角度进行思考，没有对整个网络的节能进行全面综合的考虑。因簇首的负载大小及能量使用时限均取决于其所支持的节点数，维护簇结构与簇间路由需要消耗簇首大量资源。若选出的簇首能量有限，将使生成的簇很快解散，带来系统更多的开销和不稳定性。因而若将邻居节点中能量最大的节点作为簇首是一种保障分簇结构相对维持较久时间的有效方法。同时，在设计整个分簇算法时，簇的形成及工作维持要尽量减少信息交互的次数，因为无线网络通信模块所消耗的能量将远远大于处理器模块消耗的能量[9]。基于以上考虑，本文提出一种基于能量平衡的分簇算法EBCA(The energy balance clustering algorithm)。算法的基本思想是：当移动自组网各节点初始化成功后，在进行簇首选择过程中，汇聚层节点收集与其连接的普通移动节点能量及距离等相关信息，结合给定的阈值，通过使用模糊理论计算出移动自组网各节点信号强度来判断各自节点能量的优劣及距离，最终选取能量最优且离汇聚层相对较近的节点作为该簇的簇首。当簇首确定之后，找出簇间网关节点，最终建立快速可靠的，且尽可能长时间维持网络生命周期的分簇结构。当簇结构在运行过程中若因某些节点加入或退出，或者因节点位置发生改变而导致拓扑结构变化时，将触发新一次的分簇算法，重新选取簇首。在新一次的分簇算法中，原有的簇首可将其职责转移给簇内其他最优成员节点。在整个算法运行过程中，均尽量考虑减少信息交互的次数，减少能源消耗，达到能量最优的目的。

3 基本描述

本文假设移动自组网中各节点工作时功率相同，能量各有不同，每个节点的能量范围都是一个同心圆且半径为1，当两个同心圆有两个交点时，认为这两个节点之间可以直接进行双向通信。对于网络中的每一个节点，均分配有一个全网唯一的ID值，设定一个阈值 T(n)，用于确定该自组织网络分簇，当分簇算法运行成功结束后，一个簇内只有一个簇头，并且簇头到簇内任意一节点的跳数均为1。基于以上假设，希望通过分簇算法分簇后，最终能够达到使成簇速度尽可能迅速且全网中簇数量尽可能少，簇生成后维持最长时间(即簇结构的稳定性)的目标。簇的运行方式将分为簇建立阶段和簇维护阶段，所设计的算法将在移动自组网初始化或运行过程中拓扑发生改变(有节点加入或退出，位置发生变化)时自动运行。

4 网络模型

文中假设有n个移动自组网工作节点，并且任其随机分布在一个二维平面之内，同时具备如下特点：

a)初始化时所有节点能量均各有不同，且各节点能准确知道自身剩余能量百分比。

b)各节点处于平等地位且均具备数据处理能力和计算能力。

c)每个簇首选取出来后，簇内节点通过单跳即可到达簇首。

d)每个移动自组网节点均可根据自身接收的信号强度指示(RSSI)，判断链路质量，决定是否增大广播发送强度。通过接收到的信号强弱测定发送者与自身节点之间的距离，进而根据相应数据进行定位。

e)各节点采用广播方式向四周发送无线信号，消耗自身能量。

5 具体算法

5.1 初始化阶段

移动自组网初始化时，汇聚节点向整个网络发送初始化的广播信息。各节点收到初始化信息后计算出自身到汇聚节点距离，并检测自身当前剩余能量百分比。普通节点收到初始化信息后，根据RSSI计算出自身到汇聚节点距离，并检测本节点当前剩余能量，以百分比表示。最后，将距离和能量信息传送至汇聚节点，其中传送的数据包中包含节点ID、剩余能量、与汇聚节点距离。

表1 普通节点向汇聚节点报告报文格式

当汇聚节点收到周边节点发送的相关信息后，计算出当前平均能量值Eavg和平均距离Davg，并把这两个平均值又返回给附近移动节点。Eavg和Davg计算公式如下：

(1)

(2)

5.2 簇首选举

在推选簇首的过程中，每个移动自组网节点将自己当前剩余能量与式(1)中得到的Eavg进行对比，小于Eavg，则不再参与竞选，大于Eavg，则参加下一轮竞选。在高于平均能量的节点中产生一个0～1的随机数，将产生的随机数与阈值T(n)比较，小于T(n)则成为候补簇首节点。T(n)由如下公式得出：

在比较过程中若遇节点能量及距离值相等则取ID值小的为簇首。当簇首节点确定后，普通节点(非簇首节点)则根据信号强弱来选择离自己最近的簇加入，并等待簇首返回确认信息。选举出的簇首在收到成员节点的请求后根据簇内的节点数目产生一个 TDMA 时隙表，并为每个加入的成员节点分配一个时隙，然后告知簇内的每个节点在分配的时间段内进行数据传输，簇内成员节点也是根据 TDMA 表来判断何时发送数据的[10]，至此，完成整个簇生成过程。

5.3 簇运行维护阶段

当簇结构建立以后，由于节点的一些行为可能会导致对簇结构产生严重影响，增加控制和通信开销。为防止簇结构频繁变化，须建立良好的簇维护方法。根据节点异常行为，可归纳为三种情况，即新节点加入，节点离开网络，节点在网络中移动。

a) 新节点加入。当一个新节点加入到现有的移动自组网时，将导致原有节点从休眠状态转为工作状态并重新连接通信链路。此时的处理方法是，先给新加入节点分配ID值，根据信号强度指标寻找距新节点最近的簇首进行加入，宣布成为该簇的成员节点，记录簇首信息，接着进行泛洪广播，获取该簇中其他节点信息。

b) 节点离开网络。有几种情况可导致节点离开网络：节点从工作转为休眠、节点能量不足导致关闭、节点链路中断等。当节点离开移动自组网时，簇头发送探测信息时无法获取该节点信息，则簇头更新其成员列表，若离开节点是簇头节点则立即启动初始化流程。

c)节点在网络中移动。当节点在移动自组网中移动时，其位置发生变化。即从一个簇所在范围移动到另一个簇所在范围。因此，对于原有簇而言就是节点离开行为。对于后一个簇而言就是新节点的加入。节点在移动的过程中应向其他节点发送广播信号使其他节点知道其在移动，否则按新节点加入来处理。

6 总结

在移动自组网中，分簇算法的优劣直接影响着网络的生存时间和工作性能。本文提出一种基于能量平衡的分簇算法(EBCA)，该算法在进行分簇时，选取具有最优能量，离汇聚层结点距离最近的结点作为簇首，同时在生成过程中尽量减少信息交互次数。该算法有效地使移动自组网在实现快速可靠传输的基础上，尽可能更长时间维持网络生命。从而实现了在有限条件下提供最大化簇结构稳定时间,增强移动自组网稳定性，提高分组投递率，加快簇间数据转发效率的目的。

[1] 刘越甲.车联网路口场景下分簇算法的研究[D].北京:北京交通大学,2016:1-6.

[2] Gerla M,Tsai J T C.Multicluster mobile,multimedia radio network.Wireless Networks,1995,1(3):255-265.

[3] Parekh A K.Selecting routers in ad-hoc wireless networks[C]//Proceedings SBT/IEEE Intl Telecommunications Symposium. 1994: 420-424.

[4] Basagni S.Distrbuted clustering for Ad Hoc networks[C]//Parallel Architectures, Algorithms, and Networks, 1999.(I-SPAN'99) Proceedings. Fourth InternationalSymposium on. IEEE, 1999: 310-315.

[5] 胡晓禹.基于能量均衡的分簇路由协议研究[D].太原:太原科技大学,2013:1-3.

[6] 付华,赵刚.无线传感器网络中一种能量均衡的分簇策略[J].计算机应用研究,2009.4:1494-1496.

[7] 吴迪，李晴，冯永新，等.一种基于地理定位信息的Ad Hoc分簇算法[J].计算机工程与应用，2005，42(14):135-141.

[8] Fall K,Varadhan K.The ns Manual(formerly ns notes and documentation).California: UC Berkeley, LBL, USC/ISI, and Xerox PARC,2007.

[9] Estrin D. Wireless sensor networks tutorial part IV: sensor network protocols[C]//Proc of the 8th Annual International Conference on Mobile Computing and Networking， 2002: 23-28.

[10] 龚本灿.一种能量均衡的无线传感器网络分簇算法[J].计算机应用研究,2008(11):3424-3429.

(责任编辑：熊文涛)

A Clustering Algorithm Based on Energy Balance

Huang Chengbing

(ComputerScienceDepartment,AbaTeachersUniversity,Wenchuan,Sichuan623002,China)

The shortcomings of common clustering algorithms are analyzed in current mobile ad hoc networks. A clustering algorithm is proposed based on energy balance for the stability of the cluster structure. In the clustering process, the algorithm can reduce the number of information interaction, and select the best energy and the nearest node from the sink node to become the cluster head, and further form a complete cluster. The results show that the algorithm can achieve the goal of saving energy and the longest time of cluster structure stability.

clustering algorithm; energy balance; mobile ad hoc network; cluster stability

2016-09-25

四川省教育厅重点课题 (11ZB151)；阿坝师范学院重点课题 (ASA12-23)

黄成兵(1980- ),男,四川宜宾人,阿坝师范学院计算机科学系副教授,硕士。

TP393

A

2095-4824(2016)06-0062-04