基于能耗均衡的均匀分簇算法研究

雷宇飞，简必建

(泉州信息工程学院，福建泉州 362000)

无线传感器网络(WSN)是由大量廉价的、低成本的感知设备组成的网络。具有实时性、低能耗、低成本、低速率、自适应等特点，由于能量由一次性微型电池供应，因此能量有限成为了WSN的最大限制，而通信部分消耗的能耗最大[1]，所以如何设计能量高效的路由协议是无线传感器网络的关键问题之一。

无线传感器网络路由协议是面向应用的，不同的应用场合有着不同的路由协议，随着无线传感器网的发展，近年来国内外学者提出了大量的路由协议。根据网络拓扑结构的不同，路由协议分为平面路由协议和分簇路由协议。研究表明，无线传感器网络采用分簇的路由协议以及簇间通过多跳转发发送数据能够明显地降低网络能耗[2-3]。因此，近年来学者们提出了许多能量高效的分簇路由协议。分簇算法根据成簇阶段簇的形成方式的不同，分为均匀分簇算法和非均匀分簇算法，主要的均匀分簇算法有LEACH算法、LEACH-C和HEED协议[4]等，该类协议将目标区域划分为大小相同的小区域，每个区域中有且只有一个簇头节点，普通节点只能和所在区域的簇头进行数据传输，最后由簇头节点将数据发送至网关节点。其中，LEACH算法是典型的低功耗自适应的分簇算法，能有效地提高节点的能量效率，是一种高效的路由协议。主要的非均匀分簇算法有UCS协议[5]、EEUC协议[6]等，此类协议的基本思想是将网络的区域根据节点距离网关节点的远近不同，划分为大小不一的簇，远离网关节点的簇的规模较大，更多地承担收集采样数据的功能，靠近网关节点的簇则更多地担任数据转发的任务，通过多跳的方式将数据传输至网关节点，从而实现全局范围内簇头节点能耗的均衡。

1 LEACH算法与问题分析

1.1 LEACH协议

LEACH[7](Low Energy Adaptive Clustering Hierarchy)是MIT研究人员A.Chandrakasan等为无线传感器网络设计的低功耗的自适应分簇路由协议。它打破了原有成簇算法中固定簇头的思想，采用本地簇头随机轮流当选簇头的机制将能量负载均匀分布到网络中的所有节点，提高了网络寿命。LEACH路由协议网络模型如图1所示。

图1 LEACH路由协议网络模型

LEACH协议执行过程是周期性的，称为“轮”(Rounds)，每个周期分为簇的建立阶段和稳定状态阶段。簇的建立阶段又可以分为簇头选举阶段和成簇阶段，一般规定簇的建立阶段比稳定阶段的时间短，算法流程图如图2所示。

图2 LEACH算法流程图

簇的建立阶段，网络中的每个节点都产生一个0到1之间的随机数用于与阈值T(si)比较，如果节点产生的随机数小于阈值则成为本轮簇首，阈值T(si)的计算公式为：

(1)

其中，p是一个预先设定的常量，表示期望簇头节点占所有节点的比例；r为当前轮数；si表示传感器节点标识；G表示在过去rmod(1/p)中簇头竞选失败的节点。由公式(1)可以看出，每1/p轮网络所有节点均依照一定概率当选过一次簇头，直到所有节点都当选过簇头后才重新获得竞选簇头的权利。簇头节点竞选成功之后，则向全网发布一条消息宣布自己成为簇头。未成为簇头的节点根据接收到信号强度加入到离自己最近的簇头，并发送申请加入请求消息，簇头根据成员数量建立一个TDMA调度，并将这个调度发送给所有成员，防止节点数据传输发生冲突，节点收到调度之后整个网络就进入稳定状态阶段。

在稳定状态阶段，普通节点只能在簇内指定的持续时间内(时隙)发送自己感知的数据给簇头节点。普通节点在没有发送数据时，将进入休眠状态以节省能量，而簇头则保持工作状态以接收数据。簇头节点接收数据后经融合处理后，最后由单跳发送至Sink节点。

1.2 LEACH协议的问题分析

LEACH算法采用随机选举簇首的机制，在新一轮竞选的过程中，最近几轮为当选过簇首的节点随机产生(0,1)的随机数，然后与阈值T(si)比较，如果节点产生的随机数小于阈值则成为本轮簇首。由于竞选过程中未考虑节点的位置，导致产生的簇头节点会出现位置集中的情况，同时会出现簇头节点位置不理想导致节点间的通信能耗浪费的情况，如图3所示。

图3 LEACH算法分簇结果图

在LEACH算法中，在簇头选举阶段若只考虑节点的当选簇首的频率，未考虑簇头节点能量因素，会导致某些节点因距离网关节点远近差异或者由于簇成员数目不一致而导致能量消耗不均衡的问题。

2 LEACH-M算法

基于对现有路由算法的研究与分析，本文提出了基于能量均衡的均匀分簇路由算法(LEACH-M)。采用二次竞选的方法来产生最终簇首，综合考虑节点的能量因素，通过轮换的机制首先产生候选簇首，然后根据节点的通信半径，综合考虑节点的能耗产生最终簇首。

2.1 网络模型与通信模型

考虑一个由N个传感器节点随机均匀分布的方形监测区域，检测数据被周期性地收集，定义周期为轮，由Sink节点根据实际应用背景在初始化时设置并广播，每轮包括分簇阶段和数据传输阶段，在数据传输阶段普通节点将采集数据直接传输给簇头，簇头对收集到的数据进行数据融合处理,然后通过多跳方式发送给汇聚节点。对于网络模型有以下假设：

(1)Sink节点位于监测区域外，且Sink节点和传感器节点在部署后处于静止状态，位置不再变化。

(2)传感器节点si,i=1,2,…,N的初始能量相同，功能、结构也相同，每个节点均有唯一的标识(ID)。

(3)传感器节点的地理位置可知，通过接收信号强度来估计二者之间的距离。

(4)传感器节点可以根据接收方的距离来自主调节发送功率。

LEACH-M协议采用典型的无线通信能耗模型[8]传输k比特的数据包通过距离d的能耗为：

(2)

其中，Etx为传输电路能耗；Eamp为放大电路的能耗；β是一个路径损耗常数，依赖于传输环境。当d≤d0和d>d0时，功率放大损耗分别采用“自由空间模型”和“多路径衰减模型”，d0的取值如式(3)所示。

(3)

接收k比特数据能耗的计算公式：

Erx(k,d)=kErx.

(4)

其中，Erx表示接收电路能耗；融合k比特数据包的能耗Eag(k)=kEag。

2.2 簇的建立阶段

2.2.1 簇首选举策略

簇首选举流程如图4所示。

图4 LEACH-M算法分簇流程图

假设监测区域中有N个节点，监测区域的面积为S，假设簇的通信半径为Rc，规定小区域的簇内有且只有一个节点成为簇头节点，监测区域内最多有个ceil(S/(πRc_min2))簇头节点，进而可以得到期望簇首与节点的比例：

(5)

每经过1/pt轮后所有节点同时获得竞选簇首的权利，因此可通过轮流竞选簇首方式来产生最终簇首。在新一轮中，节点si,i=1,2,…,N是否成为候选簇首由动态阈值T(si)决定，T(si)的计算公式：

(6)

其中，p表示期望候选簇首占所有节点的百分比；rm=rmod(1/pt)表示轮换周期的临界值；pt表示期望最终簇首占所有节点的最大百分比；G表示在前(r-1)mod(rm)未当选为最终簇首的集合；si表示节点标识。

由式(6)首先随机产生候选簇首节点，通过轮换的机制，保证所有节点在一定周期内当选簇首的频率是相同的，从而在时间分布上消除节点因当选簇首频率差异导致过早失效的情况。如果仅考虑节点当选簇首的频率而不考虑节点位置以及能量因素会导致节点间能耗不均衡的情况。因此首先引入通信半径Rc来构造邻居簇首集合SCH，候选簇首sj的邻簇首集sj·SCH为：

sj·SCH={sm|sm∈tentativeCHs,d(sj,sm)≤Rc}.

(7)

如果候选簇首sj一旦发现自身在邻簇首集合中自身的剩余能量最大，则竞选成功并广播获胜消息给其邻居候选簇首，成为最终簇首。如果在邻居簇首集中自身的剩余能量不是最大，则需等待邻居簇首集中剩余能量大的节点先做出决策：若收到剩余能量比自己大的邻簇首sk竞选成功的消息，则候选簇首sj立即宣布退出竞选，成为普通节点；若候选簇首sj收到剩余能量比自己大的邻簇首sm退出竞选的消息，则将sm在邻簇首集合sj·SCH中删除。由此整个簇首选举过程结束。

2.2.2 分簇阶段

簇首产生之后，未参与竞选的节点被重新唤醒，然后簇首向全网广播自身成为簇首的消息，普通节点选择加入信号强度强的簇，成为该簇的成员节点，并向对应的簇首发送加入消息。

簇头节点根据簇成员数目，全网广播的形式向所有簇成员节点发送一个TDMA调度表，保证所有节点不冲突地发送数据给簇头。

2.3 数据传输阶段

2.3.1 簇内数据传输

为了便于实现，簇内数据通信采用与EEUC协议相同的通信方式——单跳通信，具体过程不再赘述。

2.3.2 簇间数据传输

为了验证LEACH-M算法的有效性，簇间采用单跳通信，即簇头节点直接和网关节点通信。

3 实验仿真与结果分析

通过MATLAB进行实验仿真，分析LEACH-M协议的能量效率和网络的能量分布情况,并和LEACH协议进行比较。为了便于分析，假设采用理想的MAC协议，忽略无线通信发生丢包情况。仿真过程中应考虑路由建立过程中所有的通信能耗，包括广播包、数据包的能耗及数据融合的能耗，为了保证数据的精度，只融合本簇内数据。具体仿真数据如表1所示。

表1 仿真参数

3.1 网络拓扑分析

图5显示了LEACH-M协议的网络拓扑。可以看出，LEACH-M协议在分簇阶段采用了竞选的机制,综合考虑了位置和能量，保证了簇首的均匀分布，避免了簇首扎堆的情况，有利于均衡簇首间的能耗。

图5 LEACH-M协议网络拓扑

图6 两种算法网络生存时间曲线图

3.2 网络的能量效率

由图6可以看出，LEACH算法的第一个节点死亡时间为202，LEACH-M算法的第一个节点死亡时间为668,结果表明LEACH-M算法能够有效延长网络的生存时间。图7是网络总能量随工作时间变化的曲线图，可以看出LEACH-M算法每轮能耗相对均衡，能量总量值与工作时间成反比关系，而LEACH算法网络总能耗随工作时间变化关系不是曲线关系，轮与轮之间能耗不均衡。图8为每轮网络能耗随工作时间变化曲线图。可以看出LEACH-M算法的节点能耗相对于LEACH算法更均衡、更稳定。

图7 网络剩余总能量变化曲线图

图8 平均能耗使用曲线

4 结语

本文在现有均匀分簇算法研究与分析基础上，提出了一种基于能耗均衡的均匀分簇算法(LEACH-M)。首先以轮换的机制先产生候选簇首，然后综合考虑候选簇首的位置和能量因素，竞争产生最终簇首。仿真结果表明，LEACH-M算法能够有效地延长网络的生存时间，而且均衡整个网络的能耗，提高网络的性能。

[参考文献]

[1]Tashtarian,E Haghighat,A T Honary,et al.A new energy-efficient cluster algorithm for wireless sensor networks[C].Sofiware,Telecommunications and Computer Networks,15th Intemational Conferenee on,2007.

[2]孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[3]Mhatre V,Rosenberg C.Design guidelines for wireless sensor networks:communication,clustering and aggregation[J]. Ad Hoc Networks,2004(1):45-63.

[4]Younis O,Fahmy S.HEED:A Hybrid,Energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J]. IEEE Transactions on Mobile Computing,2004(4):366-379.

[5]Akyildiz LF, Su W,Sankara subramaniam Y.Wireless sensor network[J].A survey Computer Networks,2002(4):22-34.

[6]Zhiyuan S,Liu F,Hou B,et al.Energy-efficient uneven clustering routing protocol for wireless sensor networks[J].Transducer & Microsystem Technology,2013(12):67-60.

[7]Holger K,Andreas W.Protocols and architectures for wireless sensor networks[M].Beijing: Publishing House of Electronics Industy,2007.

[8]Zheng L,Gao L,Yu T.An Energy-balanced clustering algorithm for wireless sensor networks based on distance and distribution[C].Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation,Atlantis Press,2016:229-240.