异构传感网中一种能量均衡非均匀分簇算法

武 朗，胡艳军

(安徽大学 计算智能与信号处理教育部重点实验室，安徽 合肥 230039)

无线传感器网络(wireless sensor network， 简称WSN)由许多具有感知能力、功率低的传感器节点组成，已得到广泛应用，如远程监控环境、栖息地、汽车和灾区.WSN具有耗能较低、节点数量多、以数据为中心和动态拓扑等特点，此特点决定了现有的网络协议很难适应WSN对网络生存时间、扩展性和负载均衡的需求.对于具有大量节点的WSN，分簇算法可有效提高网络寿命，同时其扩展性可满足网络负载均衡要求[1-4]. LEACH分簇算法[5]基于“轮”的思想选取簇头(cluster heads，简称CHs)，但其对CHs的选取是随机的，导致整个WSN中CHs能量消耗不均衡.SEP分簇算法[6]中CHs选取由节点初始能量决定，但没有考虑节点的当前能量.DEEC分簇算法[7]中CHs的选择基于节点的剩余能量与网络平均能量的比值，需要计算网络平均能量.BEEC分簇算法[8]在CHs选取的最终阶段引入了竞争机制，在簇构建阶段，只考虑了节点到CHs的距离，并没有考虑整个WSN因传输路径规划不合理导致的能量消耗.HEED分簇算法[9]根据节点剩余能量概率选取候选簇头，再依据簇内通信代价的高低产生最终的CHs.非均匀分簇算法[10-11]解决了多跳通信带来的簇间能耗不均衡问题，但没有考虑异构网络的情况.笔者针对异构网络中的单跳通信，提出一种适用于异构无线传感网的能量均衡非均匀分簇(energy equilibrium non-uniform clustering，简称EENC)算法.

1 能量均衡非均匀分簇算法

不同类型的传感器节点初始状态下配置的能量不同，感知区域内随机分布的节点在运行时消耗剩余能量也不同，导致传感器网络不同节点出现能量异构[7].在异构传感网单跳均匀分簇路由协议中，远离BS的CHs消耗更多能量，导致CHs间能量消耗不均衡.下面具体介绍笔者提出的EENC算法细节.

1.1 初始化

异构传感网由2级能量异构节点构成，在感知区域内随机分布一定比例的普通节点和高级节点.对网络节点假设如下：

(1) 每个节点都有唯一的ID；

(2) 根据节点与接收者的距离，调整发射功率；

(3) 一旦节点部署完成，所有节点保持静止；

(4) 节点根据接收信号强度(RSSI)计算发送者到自己的距离；

(5) 每个节点知道基站位置.

初始化阶段涉及的信息如表1所示.

表1 节点信息表

1.2 簇头选取

簇头选取分为临时簇头选取和最终簇头确定.临时簇头选取采用LEACH算法中“轮”的思想和DEEC算法中簇头选取方法.最终簇头确定中，引入非均匀竞争机制，根据能量因子从临时簇头中选取最优簇头.

1.2.1 临时簇头选取

临时簇头选取直接采用LEACH和DEEC簇头算法，两算法的详细介绍见文献[4，6].LEACH算法中簇头选取的阈值T(i)定义如下

(1)

其中：p为传感器节点当选CHs的比例，r为当前轮数，G为当前1/p轮数中未能成为CHs的节点集合.

2级能量异构网络中，DEEC算法中高级节点和普通节点当选临时簇头的概率分别为

(2)

(3)

将式(2)，(3)计算出的概率padv，pnrm，替代式(1)中的p，得到不同能级节点当选临时簇头对应的阈值.比较节点随机产生的值与阈值的大小，确定该节点能否在本轮中当选临时簇头.

1.2.2 簇头最终确定

簇头最终确定要使用非均匀多跳路由EEUC算法，并引入竞争机制选取簇头.依据临时簇头与基站间的距离设定临时簇头竞争范围，距离基站远的临时簇头竞争范围小，距离基站近的临时簇头竞争范围大.临时簇头通过竞争产生最终簇头，使距离基站较远的簇内拥有较少的节点，这样可减少该簇头向基站传输的数据量，从而缓解单跳分簇路由中，因簇头与基站距离的不同而造成的簇头能量消耗不均衡.离基站相对较近的节点可以直接向基站传输数据，进一步减少该区域内簇头的负担.图1为经过非均匀竞争后簇头的最终分布，图中大小不等的圆表示簇头竞争范围.

图1 经过非均匀竞争后簇头的最终分布

不同的临时簇头i分别引入不同的竞争半径Ri，其表达式如下

(4)

其中：dmax为传感网中临时簇头与BS间的最大距离，dmin为临时簇头与BS间的最小距离，di_to_BS为临时簇头i与BS的距离，Rc为最小竞争半径，c为0到1之间的常数.由(4)式可知，临时簇头竞争半径Ri与其到基站的距离di_to_BS有关.di_to_BS越大时，Ri值越小，即当其位置离基站越远时，其竞争范围越小.

每个临时簇头在各自的竞争范围内，根据自身能量因子γi=Ei/di_to_BS的大小，与其他临时簇头竞争最终簇头.Ei为临时簇头i的剩余能量，di_to_BS为临时簇头i与基站的距离.竞争范围内一旦临时簇头i竞选成功，则成为最终簇头CHi.其他临时簇头则退出竞争，成为节点成员，簇头选取流程如图2所示.

图2 簇头选取流程

1.3 簇的构建

根据文献[7]中FORM节点能量模型可知，节点的能量消耗与其传输距离密切相关.BEEC算法中，如果只考虑节点与簇头间距及簇头的剩余能量这两种因素，则节点加入簇头的过程如图3实线所示.

节点i，j加入簇头CH1后，簇头CH1对节点i，j传来的数据进行接收、融合，并把融合后的数据传输给BS. 这样虽然减少了剩余能量少的簇头能量消耗，却增加了整个网络的能量消耗.合理的传输路径不仅考虑节点与簇头间距、簇头剩余能量，还要考虑节点与基站的位置关系.如图3虚线所示，节点i，j加入簇头CH2，CH2向BS传输数据，这样可大大缩短总的传输距离，减少网络的总能量消耗.

图3 节点加入簇头的示意图

节点加入簇头前，要计算节点i与基站的距离di_to_BS及与簇头的最短距离dmin(CH_to_BS).如果di_to_BS小于最短距离dmin(CH_to_BS)，则节点i直接向BS传输数据，这既减少了节点自身的通信损耗，也降低了簇头的负担.否则，节点将加入最大的costjoin_to_CHk对应的簇头，costjoin_to_CHk的表达式如下

(5)

1.4 数据传输

一旦完成簇的构建，则进入数据传输阶段.节点能量消耗公式[12]为

ERX(l,d)=l·Eele，

(6)

(7)

其中：ERX(l,d)为接收端接收l比特(bit)数据量所消耗的能量；ETX(l,d)为发送端发送l比特(bit)数据量所需要的能量；Eele为发送或接受单位比特(bit)数据消耗的能量，Eele=5 nJ·bit-1；εfs，εamp分别为自由空间和多径衰落信道中放大器的能耗，εfs=10 pJ·bit-1·m-2,εamp=0.001 3 pJ·bit-1·m-4；d0为距离阈值，d0=87 m.

2 仿真及分析

对提出的EENC算法在网络生存周期、吞吐量和网络节点剩余能量方面与LEACH，SEP，DEEC算法进行比较.簇头每向基站发送一次数据视为网络执行一轮，仿真采用MATLAB数学工具，以下的实验值是20次实验的平均值.仿真中使用的参数见表2.

表2 仿真参数

在簇头最终确定阶段，对临时簇头引入竞争机制.变量Rc的值决定最终簇头的数量，影响网络生存周期.Rc值增加，临时簇头的竞争范围变大，生成的最终簇头数量就会减少，反之Rc值减小，生成的最终簇头数量就会增加.下面通过仿真选取Rc的最佳值.

图4 网络生存周期所对应轮数与簇头竞争半径的关系

由图4可以看出，Rc=15 m时网络生存时间最长.簇头竞争半径较小时，网络簇头数量较多，大量节点与基站通信，网络能耗快.而当竞争半径较大时，网络簇头数量较少，簇头处理簇内数据的能耗增多，第一个节点会过早死亡.

2.1 网络生存周期

从开始到第1个节点死亡所经历的轮数为网络生存周期.在2级能量异构网络下，图5为网络节点生存数随轮数变化情况.

图5 网络节点生存数随轮数变化

从图5中可以看出，笔者提出的EENC算法网络生存周期长，非稳定时间短，EENC，DEEC，SEP，LEACH算法对应的网络生存周期分别为1628，1487，1261，989.EENC算法的网络生存周期相对DEEC，SEP，LEACH的，分别提高了9%，29%，64%.因此，EENC算法延长了网络生存周期，均衡了网络节点的能量消耗.

2.2 网络吞吐量

图6 为基站接收的数据量随轮数的变化情况.由图6可知，网络中第一个节点死亡之前，即曲线拐点处，基站接收的数据量随轮数近似线性变化.由于节点过早死亡，导致基站接收数据量的速率下降，表现为曲线斜率逐渐变缓，直至所有节点死亡，曲线趋于水平.EENC算法基站最终接收数据总量比其他算法更大.

图6 基站接收的数据量随轮数的变化

2.3 网络节点剩余能量

图7为网络节点剩余能量随轮数变化的情况.由图7可知，与其他算法相比，EENC算法网络节点剩余能量随轮数变化的斜率最小，说明EENC算法整个网络节点能量消耗速率较慢.从第一个网络节点死亡到整个网络节点死亡，EENC算法网络节点剩余能量随轮数增大而缓慢递减，且无明显的拐点.EENC算法能很好地均衡整个网络节点的能量消耗，能量利用率高.

图7 网络节点剩余能量随轮数的变化

3 结束语

笔者针对能量异构无线传感网单跳分簇路由的特点，提出了能量均衡非均匀分簇算法.该算法在簇头最终确定阶段对临时簇头引入不同的竞争半径，使整个网络形成非均匀分簇结构，缓解距离基站较远的簇头消耗过多能量.在簇的构建阶段，考虑节点与基站的距离因素，降低了整个网络的能量消耗.与LEACH，SEP，DEEC算法相比，该算法有效均衡了簇头能量消耗、延长了网络寿命.

参考文献：

[1] SOHRABI K, GAO J, AILAWADHI V, et al. Protocols for self-organization of a wireless sensor network[J]. IEEE Personal Communications, 2000, 7 (5): 16-27.

[2] SIRSIKAR S, WANKHEDE K. Comparison of clustering algorithms to design new clustering approach[C] //International Conference on Advances in Computing, Communication and Control(ICAC3’15), 2015: 147-154.

[3] LIU X X . A typical hierarchical routing protocols for wireless sensor networks: a review[J]. IEEE Sensors Journal, 2015, 15 (10): 5372-5383.

[4] NAM C S, CHO H Y, SHIN D R. Setting up the threshold based on cluster head selection algorithm in wireless sensor networks[C]//IEEE Education Technology and Computer (ICETC), Shanghai, 2010: 22-24.

[5] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communication, 2002, 1 (4): 660-670.

[6] SMARAGDAKIS G, MATTA I, BESTAVROS A. SEP: a stable election protocol for clustered heterogeneous wireless sensor networks[C]//Proceedings of 2nd International Workshop on SANPA, 2004 : 1-11.

[7] 卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效成簇算法[J]. 软件学报, 2006, 17 (3): 481-489.

[8] LIU J J, HU Y J. A balanced and energy-efficient clustering algorithm for heterogeneous wireless sensor networks[C]//IEEE Wireless Communications and Signal Processing (WCSP), Hefei, 2014: 1-6.

[9] YOUNIS O, FAHMY S. HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Transactions on Mobile Computing, 2004, 3 (4): 660-669.

[10] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Washington, 2005: 597-604.

[11] 李成法, 陈贵海, 叶懋, 等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报, 2007, 30 (1): 27-36.

[12] HEINZELMAN W B, CHANDRANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1 (4): 660-670.