基于Floyd的无线传感器网络簇内能量优化

唐君超

(上海海事大学 信息工程学院，上海201306)



基于Floyd的无线传感器网络簇内能量优化

唐君超

(上海海事大学 信息工程学院，上海201306)

摘要：无线传感器网络中的能量空洞是无法避免的，能量空洞问题会加速整个网络生命的死亡。针对簇型网络中容易出现能量空洞问题，提出一种新的基于能量效率的簇中路由算法(a Route Algorithm based Energy Optimization in Cluster，RAEOC)。网络被划分成多个等区域的簇类，RAEOC将Floyd算法应用到簇内节点路由机制中，使节点传输数据到汇聚节点的使用能量最优化，并且平衡整个网络的能量消耗。仿真结果表明，RAEOC算法比传统的分簇算法如LEACH和PEGASIS可分别节省68%和54%的能量。

关键词：移动汇聚节点；能量空洞； Floyd算法；能量优化

引用格式：唐君超. 基于Floyd的无线传感器网络簇内能量优化[J].微型机与应用，2016,35(13)：60-63.

0引言

无线传感器网络由大量的传感器节点通过无线通信的方式自组织成一个分布式网络系统，这些传感器节点一起协同运行工作，检测并采集传感器感应范围内的信息数据。一般情况下传感器节点搜集信息数据后把数据传输给汇聚节点(Sink)或基站进行再次处理[1]。

在无线传感器网络系统中主要靠能量策略和路由协议来决定该系统的生存时间。能量策略中的节能技术[2]占更大的比重。无线传感器网络在应用中需要布置到无人值守的区域，所以一旦部署完成，节点的电池就无法更换，因此在运用节能技术的同时应尽可能延长网络的生存时间。

本文提出一种新的基于能量效率的簇中路由算法(a Route Algorithm based Energy Optimization in Cluster，RAEOC)，通过在使用移动Sink的无线传感器网络中进行区域分簇，然后在簇中使用基于能量优化的路由策略。RAEOC的最终目标是利用能量优化策略来达到整个网络寿命的延长。

1相关工作

在传统的无线传感器网络的路由场景中，由于数据进行传输和转发是基于多对一的多跳路由通信模型，所以网络中会存在能量消耗不平衡的情况[3]。靠近静态基站的节点由于转发任务过重，导致能量消耗相对过大，从而死亡，这种现象称为无线传感器网络的能量空洞问题。

1.1网络层次分簇

LEACH协议[4]的基本思想是以循环的方式随机选择簇头(Cluster Head，CH)节点，将整个网络的能量负载平均分配到每个传感器节点上。其缺点是不确定的簇头数量导致簇头分布不均，从而使网络能耗不均匀。而且其只适用于小规模的网络系统。PEGASIS[5]是对LEACH的一种改进协议。它采用基于链式结构的协议，运行PEGASIS协议时每个节点首先利用信号强度来探测所有邻居节点的远近，调整信号强度仅使最近邻居节点能够接收信号，链中只选择一个节点作为汇聚节点进行任务传输。优点是减少了LEACH在簇重构过程中产生的开销，并且通过数据融合降低了收发任务的次数，从而降低能耗。缺点是由于传感器节点需要知道邻居的能量情况，协议需要动态调整拓扑结构，在利用率高的网络中，拓扑的调整会带来更大的开销。

1.2移动Sink模式

其原理为基于策略的移动Sink沿着预先设定的路径收集数据。参考文献[6]提出了三层体系结构下移动Sink随机地在节点区域移动，并收集移动路径上感知范围内的节点数据。Sink会遍历整个网络，一旦到达原始出发点就结束了一轮收集。参考文献[7]提出了一种基于能量效率的数据收集策略，原理是将一个名为SenCar的数据监测器作为移动Sink，当Sink的传输范围不够时，需要进行网络分簇并计算出其移动的转折点(Turning Points)，这个策略在实验中可以延长整个网络寿命，但缺点是延迟较高。

2模型与假设

2.1能量模型

本文采用参考文献[8]中的能量模型。根据节点间距离的不同，可以分为两种模型，分别是自由空间模型和多路径衰减模型。距离为d的情况下发送lbit数据所消耗的能量为：

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

(1)

接收lbit数据所消耗的能量为：

ERx(l)=ERx-elec(l)=lEelec

(2)

其中，Eelec为发送或接收单位比特数据所消耗的能量；εfs和εamp代表放大器系数；d0是距离边界值。

2.2网络模型假设

假设整个无线传感器网络由N个传感器节点组成，节点用SN表示，{S1，S2，...，SN}被随机部署在一个半径为R的圆形检测区域G内。移动汇聚节点(Mobile Sink Node，MSN)分布在监控区域边界。对网络作如下假设：

(1)节点SN的部署位置在监控区域G内服从均匀分布；

(2)节点SN拥有唯一ID号并且初始能量相同；

(3)根据通信距离的远近，SN的发射功率可以调节；

(4)MSN沿着G的边界进行匀速移动来收集数据。

图1　网络模型

图2　MSN收集数据策略

网络模型如图1所示，其中，●为监测节点，▼为MSN。此处MSN的移动轨迹和收集并汇聚数据的策略参考了文献[9]中的方法。MSN通过均匀速度v沿着监测区域G的边界移动来收集数据，当MSN开始移动时，它负责向整个区域广播自己的位置P和速度v，此时普通节点和CH记录MSN的数据P和v，然后通过计算得到何时需要发送数据给MSN，如图2。计算方式如下：

(3)

当MSN从P0点出发，向区域广播自身位置时，CH到P1点距离可以由CH点到圆心点距离计算得出，P1点即MSN收集数据停留点，根据式(3)计算出时间t，然后CH在接收到MSN广播后经过时间t后向MSN发送所收集到的数据，发送功率可以调节为CH到P1的距离。由此可以最优化地利用能量。这里假设MSN在收集数据时会停留足够长的时间来完成数据的收集，完成后继续沿边界移动并再次发出广播。

2.3簇类划分和簇头选举

本文引用参考文献[9]中的分簇方法和簇头选举算法，但稍作修改来适应文本中实验的要求。采用此方法的原因是其可以适用于各种类型的无线传感器网络。无需采用其他复杂的分簇算法和簇头选举算法，因为本文重点关注的是如何优化簇中的路由能量优化。

3RAEOC算法

许多路由问题往往可以规约为一个图的问题，本文将传感器节点看作图中的点，节点之间的通信作为边，通信所需要的能量消耗当作边上的赋权，此时基于能量的路由研究问题即可当作图的极值问题来建立模型。

图3　簇内的拓扑网络

(1)构建图模型。如图3，将簇内网络构建成图模型，CH和MSN也为其中成员节点。由于CH是被竞选为能量最多的节点，所以计算拓扑等都由CH来计算。在竞选簇头时，各个节点都对其邻居节点发送过广播，所以各个节点的距离都已知，通过距离根据能量模型便可以求出发送数据所消耗的能量。

(2)建立图中边和赋权。节点与其邻居节点可以相互通信，便可以建立成边。边上赋权则根据能量公式计算而得。此处假设网络环境不复杂，使用自由空间模型。例如S5与S6之间的距离为a，则能量消耗为：

E(S5,S6,l,a)=ETx(l,d)+ERx(l)=

lEelec+lεfsa2+lEelec=l(2Eelec+εfsa2)

(4)

此处，算法中引入两个权重系数：一个是剩余能量系数RE，另一个是数据量系数DV。在运行算法过程中由于各节点相对位置不变化，而计算边权时主要依赖于节点之间的距离条件，所以随着网络运行的周期增加，节点之间边权值不变，传输数据会一直选择同一条路由，从而会过早出现能量空洞。本算法中加入两个边权权重系数，可使能量剩余不多的节点减少使用率。以下为节点Sa到Sb的边权计算方式：

E(Sa,Sb)=E(Sa,Sb,l,b)×RE(Sb)×DV(Sa)

(5)其中,RE(Sb)为节点Sb的剩余能量系数，DV(Sa)为节点Sa所发送数据量的系数。对于RE和DV两系数，有如下定义：

(6)

(7)

(3)使用Floyd算法[10]来求得所有节点到MSN的最短路径。将图的拓扑关系用矩阵M[i][j]n×n来表示，若Si一步到达Sj，则cij=M(0)[i][j]为最短距离；若Si和Sj无连接，则cij=∞；若Si二步到达Sj，则设Si经过一个中间点Sr到达Sj，则M(1)[i][j]为最短距离矩阵。

M(1)[i][j]=Minfor(r→n){cir+crj}

(8)

若Si经过k步到达Sj，则根据迭代，可得出最短距离矩阵M(k)[i][j]，迭代公式如下：

M(k)[i][j]=Minfor(r→n){M(k-1)ir+M(k-1)rj}

(9)

在此处，由于应用此算法很有可能出现多跳情况将数据传输给汇聚节点，所以中继节点将会承受巨大压力。结合实际情况，节点可以越过簇头，直接将数据传输给汇聚节点，所以此处将会选择能量消耗较小的路径来传输数据。

最终Si到MSN的能量消耗可以表示为：

E(Si,MSN)=

Min{E(Si,MSN,l,d),M(k)[i][MSN]}

(10)

以下是整个网络运作的过程：

(1)划分网络成几个均匀的簇组；

(2)簇类中所有节点都遍历发送广播消息；

(3)选出簇头并且计算出各邻居节点之间的边权值；

(4)MSN开始移动，并且广播自身位置和速度；

(5)CH计算出距离MSN最近的时刻，并设置任务，在此时刻发送融合的数据；

(6)CH获得整个簇内拓扑模型并使用RAEOC算法对模型求解，寻找各节点到MSN的最短路径；

(7)CH向各节点广播计算的结果路径和发送时间；

(8)各节点沿着最短路径发送收集的信息给MSN。

4仿真实验

4.1仿真环境

为了评价RAEOC算法的性能，利用MATLAB在相同的环境下对LEACH、PEGASIS和本文算法进行仿真，并进行比较。在实验中模拟了不同算法对网络整体能量消耗和监测区域大小变化对能量消耗的影响，仿真环境如表1所示。

表1　网络环境参数

4.2实验结果分析

首先对比了RAEOC、LEACH和PEGASIS三种协议模拟20轮后消耗能量的大小。将100个节点随机平均分布在300 m×300 m的监测区域，从图4中可以看出，经过20轮后，RAEOC所消耗的总能量远比另外两种算法少，相比LEACH总能量消耗可节省68%，相比PEGASIS总能量消耗可节省54%。这主要是因为RAEOC使用了分簇算法并进行数据融合，使数据在路径上传输所消耗的能量降低了。LEACH由于单纯地采用随机数和阈值的策略产生簇头，会使簇头分布不均，导致网络能耗不平衡。在图4中，LEACH的曲线随着轮数的增加，斜率起伏变化，说明每轮能量消耗都不同，更容易产生能量空洞。PEGASIS虽然改进了LEACH，减少了在簇重构过程中产生的开销，但在动态调整网络拓扑结构时效率会降低。

图4　LEACH，PEGASIS和RAEOC消耗的总能量

在多MSN的情况下，网络能量消耗的情况，如图5所示。在300 m×300 m的区域中，随着MSN的数量增多，总能量消耗会降低。同样如图6，在500 m×500 m的区域中也是如此。当MSN为3个时，总能量消耗降低明显，但超过3个后，效果并不明显，减少的余地很小。所以得出结论，部署3个MSN对于能量消耗减少效果相对较好。

图5　300 m×300 m区域下多MSN消耗的总能量

图6　500 m×500 m区域下多MSN消耗的总能量

5结论

基于在无线传感器网络中能量的消耗问题，提出了一种分簇并优化簇内路由的算法。该算法可以帮助网络节省能量消耗，延长网络寿命，并且通过簇内算法平衡每个节点的能量消耗，可以减缓出现能量空洞的时间。仿真结果也表明，相比传统的LEACH和PEGASIS，本文算法在整体网络能量消耗上减少更多。在今后的研究中，可以考虑使用改进型的Floyd算法或者其他多源最短路径算法来替代Floyd算法。

参考文献

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8):102-114.

[2] PANTAZIS N A, VERGADOS D D. A survey on power control issues in wireless sensor networks[J]. Communications Surveys

& Tutorials, 2007, 9(4):86-107.

[3] CHEN G, LI C, YE M, et al. An unequal cluster-based routing protocol in wireless sensor networks[J]. Wireless Networks, 2007, 15(2):193-207.

[4] STOJMENOVIC I, LIN X. Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks[J]. Parallel and Distributed Systems, 2001, 12(10):1023-1032.

[5] LINDSEY S, RAGHAVENDRA C S. PEGASIS: power-efficient gathering in sensor information systems[J]. ASAIO Journal, 1996, 42(5):1125-1130.

[6] SHAH R C, ROY S, JAIN S, et al. Data MULEs: modeling and analysis of a three-tier architecture for sparse sensor networks[J]. Ad Hoc Networks, 2003, 1(2-3):215-233.

[7] MA M, YANG Y. SenCar: an energy efficient data gathering mechanism for large scale multihop sensor networks[J]. Parallel & Distributed Systems IEEE Transactions on, 2006, 18(10):1476-1488.

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

[9] Wang Jin, Yin Yue, KIM J U, et al. An mobile-sink based energy-efficient clustering algorithm for wireless sensor networks[C].Computer and Information Technology (CIT),2012 IEEE 12th International Conference on. IEEE, 2012:678-683.

[10] CORMEN T H, LEISERSON C E, RIVEST R L, et al. 算法导论(第三版)[M]. 殷建平,徐云, 王刚,等，译. 北京:机械工业出版社, 2013.

中图分类号：TP393

文献标识码：A

DOI：10.19358/j.issn.1674- 7720.2016.13.020

(收稿日期：2016-03-14)

作者简介：

唐君超(1988-)，男，硕士研究生，主要研究方向：无线传感器网络。

Wireless sensor network energy optimization in cluster based on Floyd

Tang Junchao

(School of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Abstract:Suffering from energy hole problem is inevitable in the wireless sensor networks. Energy hole problem will hasten the death of the whole network. To solve this problem in the clustering network, we propose a route algorithm based energy optimization in cluster (RAEOC). The network is divided into some uniform clusters, and RAEOC applies the Floyd algorithm to intra-cluster routing. It optimizes the energy consume of data transmission from sensor nodes to sink, and balances the energy consume of the whole network. Simulation results indicate that RAEOC algorithm can save energy 68% and 54% than traditional clustering algorithms such as LEACH and PEGASIS.

Key words:mobile sink node; energy hole; Floyd algorithm; energy optimization