基于双簇头网格调度的WSNs能量空洞缓解*

张人上, 曲开社

(1.山西财经大学,山西 太原 030006；2.山西大学 计算机与信息技术学院，山西 太原 030006)

基于双簇头网格调度的WSNs能量空洞缓解*

张人上1, 曲开社2

(1.山西财经大学,山西 太原 030006；2.山西大学 计算机与信息技术学院，山西 太原 030006)

设计了基于双簇头网格调度反馈结构的无线传感器网络(WSNs)非均布节点能量空洞缓解机制，并设计了主副簇头网格聚类算法，形成网格单元；依据节点身份(ID)与网格ID，定义鉴定规则，确定网格中的WSNs节点；构造了网格单元中心点的计算数学模型，依据该中心点坐标确定每个网格单元的簇头，调度网格内的节点；构建了主—副—相邻簇头的数据调度传输结构，有效分散了节点所承担的负载,并对本机制性能进行理论分析。仿真结果表明：与其他机制相比，在非均布节点环境下，该算法更能有效避免网络能量空洞，其节点持续时间最长，显著消除了“漏斗效应”。

能量空洞；双簇头网格聚类；漏斗效应；数据收集；网络效率

0 引 言

无线传感器网络(wireless sensor networks,WSNs)已经在目标追踪、国防等领域得到了飞快发展，成为当前的研究热点[1]。 在WSNs中，静态Sink节点在收集数据时，其附近的节点都有可能参与数据转发，使得其能量迅速消耗，导致网络时效与瘫痪，产生了“能量空洞”，显著降低了网络寿命[2]。能量空洞形成后，会形成“漏斗效应”[3]。对此，余育青等人[4]构造设计了基于时空特性的网络能量空洞研究，测试结果表明其算法能够显著提高网络寿命。李斌等人[5]提出了基于蚁群算法的WSNs节点能量空洞规避机制，实验结果显示其机制显著提高了网络寿命。刘安丰等人[6]提出了异构传感器网络能量空洞分析与避免机制，实验结果体现了该算法的合理性。

但是这些算法的优异性都是在节点以均匀分布条件下取得的，在非均匀分布情况下，这些机制容易形成严重的能量分布不均，无法有效地规避能量空洞现象；且这些算法都是随机择取主簇头，导致网络效率降低[7～9]。

为了解决上述不足，本文设计了基于双簇头网格调度反馈结构的WSNs非均布节点能量空洞缓解机制,并在仿真平台上测试本文机制性能。

1 基于双簇头网格聚类算法设计

1.1 网格单元的形成

将整个网络区域分割成尺寸相等的2D静态Sink网格，见图1。每个网格都是尺寸为d×d的方形单元；且每个网格的鉴定都是依据自身的IDCi来完成，其中，i=0,1,2,…，n代表网格单元ID的引擎。在图中，从左到右，第一行的网格单元ID依次为C0,C1,C2,…,C5；同样的，第二行的网格单元ID依次为C6,C7,C8,…,C11，其他的，依此类推。整个网络区域面积为X×Y(X=Y)，(图中X=Y=30)。起初，每个网格单元的长度为固定值d(图中d=5)，则定义2个变量α,β

(1)

(2)

其中，X,Y分别代表网络区域的长度与宽度。

若网络区域内所形成的网格单元数量为Z,则

Z=α×β.

(3)

由于每个网格单元的IDCi与网络区域面积相关,故网格单元的IDCi的坐标如下

(4)

其中，x,y分别代表与网格单元的ID引擎i相关的坐标值

x=i%a,

(5)

y=i/α.

(6)

如图1所示，X=Y=30，d=5，Z=36，网格引擎i=0,1,2,…,36。为了找出C10的坐标，依据模型(5)～模型(6)，求得x=10 %6=4,y=10/6=1；依据模型(4)，求得C10坐标为

(7)

通过上述程序，可计算出所有网格单元的ID；根据网格单元位置引擎i可得到每个网格单元的坐标。

图1 网格的形成及其引擎Fig 1 Formation of grid and its engine

1.2 网格单元中心点的数学模型的构造

依据1.1小节得到的网格单元，计算每个单元的中心点坐标，以便确定簇头

(8)

(9)

其中，Xmid,Ymid分别代表中心点的横、纵坐标；其余参数与模型(4)相同。

根据图1，则C10的中心点坐标为(45,15)。

1.3 网格单元中的WSNs节点鉴定

(10)

其中，x(j)代表节点j的横坐标x值；y(j)代表节点j的纵坐标y值；&代表按位与运算。

按照模型(10),即可确定每个网格单元内的节点，并且将其归入相应的簇群内。

1.4 簇头的择取

1)主簇头的择取

本文将与网格单元中心最近的节点视为簇头。每个节点j坐标(xj,yj)与中心点(Xmid,Ymid)之间的距离D为

(11)

当D最小时，此时的j被择取为主簇头；然后借助静态Sink广播网格ID、网格单元ID的中心点以及每个网格内的节点ID。通过静态Sink更新主簇头信息，以便用于副簇头的择取。

2)副簇头的择取

主簇头会择取能量与之相近，且距离中心点(Xmid,Ymid)最近的节点视为副簇头

(12)

其中，Esecond代表副簇头的能量；MT()为取最接近值运算；Eprimary为主簇头的能量；Di代表节点i与中心点(Xmid,Ymid)之间的最小距离。

3)相邻簇头的择取

由于每个簇头都包含了静态Sink的信息，故每个簇头都会择取与静态Sink最近的节点视为相邻簇头。

通过主簇头—副簇头—相邻簇头的数据调度传输结构，有效分散了节点所承受的负载，降低了能量消耗速度，有效增加了网络寿命,见图2。

图2 主簇头—副簇头—相邻簇头调度结构Fig 2 Scheduling structure with main-vice-adjacent cluster head

1.5 数据收集阶段

1.6 更新阶段

在此阶段，当前簇头会查询每个节点的能量。根据每个节点的能量ei，对节点进行排序，形成集合A={e1,e2,…，en}；再计算网格单元内所有节点能量的均值Eaverage,并挑选出能量大于Eaverage的节点，当然这些节点均离中心点最近

(13)

令B∈A代表这些能量大于Eaverage的节点。对于B而言，其距离网格单元中心点最近的节点被择取为簇头；下一个与中心点最近的节点被视为副簇头。通过这样的方式，可确保选取的簇头始终具有最大的能量，且与网格单元中心点最近。

2 能量空洞缓解机制性能分析

假设整个网络区域是由n个同心正方形构成，每个同心正方形都是由尺寸为r×r的小网格单元构成。静态Sink位于网络区域中心。由图3，获取第i个同心正方形面积为

Ai=(2i-1)A1,i≠0,i≥1.

(14)

其中，Ai代表第i个同心正方形面积，则整个网络区域面积为

(15)

对于A1来说，若其网格单元的数量g,则整个网络的网格单元总数N为

(16)

最内侧同心方形的每个簇头节点的负载W计算如下

(17)

其中，W为簇头负载；M为最内侧同心方形中簇头节点数量；Cost为所有簇头的簇内通信成本。

若ρ为网络区域内的节点密度；每个节点的数据传输率为β,则簇内通信成本c为

c=r2ρβ.

(18)

如图3所示，最内侧同心正方形的簇通信成本为4r2ρβ。因此，第i个同心正方形的簇通信成本为

Cost(i)=(2i-1)×4r2ρβ.

(19)

联合模型(17)～式(19)，得到所有簇头的簇内通信成本Cost和负载W为

(20)

(21)

对于本文算法，总的通信跳数V应该是簇间通信成本与簇内通信成本的总和。

簇内通信总成本Z

(22)

簇间通信总成本J

(23)

则V为

(24)

总的通信跳数V体现了节点在网络中的能量消耗程度，故V越大，则能量消耗越大。对于非均匀节点分布，是不断变化的；但总的通信跳数V是不变的。

图3 从Sink中心将网络划分为同心方形Fig 3 Divide grid into concentric square from Sink centre

3 仿真结果与分析

借助NS—2平台来测试本文机制。仿真环境为：采用因特尔I7,2.3 GH z 双核CPU，400 GB硬盘，8 GB的内存,操作系统为Windows Xp,并设置对照组：文献[6]与文献[7]。采用非均匀分布节点进行实验，其拓扑结构见图4，实验参数为：模拟面积500 m×500 m；传感器节点为200个；静态Sink为1个；100个网格单元；无线射频范围[20,180]m；数据包大小为512 bytes；天线类别为全向；流量类型为CBR；初始能量为1 J；Tx,Rx功率耗散分别为0.0156,0.012 8 W；网格大小为50×50；起初节点的传输范围为[40,150]m。

图4 仿真所用的拓扑结构Fig 4 Topology structure used in simulation

3.1 网络效率对比分析

网络效率是直观体现能量空洞现象的指标之一[10,11],不同能量空洞避免机制对应的网络效率见图5。从图5中可知，本文设计的能量空洞规避机制具有更高的网络效率；而对照组两种算法的网络效率较低。原因是本文算法设计了双簇头网格聚类算法，使簇头的能量始终保持在较高水平，延长了网络寿命；而对照组的簇头择取方式是随机的，无法使择取的新簇头能量始终保持较大值，导致网络效率低下。

图5 不用能量规避机制的网络效率Fig 5 Network efficiency without using energy evasion mechanisms

3.2 网络寿命对比分析

本文测试了节点距离与节点寿命的关系曲线，见图6。从图中可知，本文机制可有效规避能量空洞，如图中箭头所指(曲线凹部分)，节点寿命持续时间达到92 s；而对照组的两种机制在非均匀分布节点条件下，其能量空洞缓解效果有限，“漏斗效应”出现的比较早。可见本文机制具有更好的能量空洞缓解效果。

图6 网络持续时间仿真结果Fig 6 Simulation results of network duration time

为了直观反映网络寿命，本文测试不同机制的网络寿命，见图7。从图中可知，随着节点数量的增加，三种不同机制对应的网络寿命都在延长；但本文机制的网络寿命最长。主要原因是本文构造了双簇头网格调度反馈结构，有效分散了节点的负载，通过相邻簇头的反馈，达到簇头能量持续更新。

图7 网络寿命测试结果Fig 7 Tests results of network lifetime

3.3 基于Sink的数据收集率对比分析

图8为不同缓解机制的数据收集率测试结果。从图中可知，随着节点数量的增加，其数据收集率先增大后下降；但本文机制在节点数据为75个时，其收集率达到最大值，约为95.86 %；而对照组都是100个节点时，达到最大收集率，分别为93.75 %(文献[6])，91.07 %(文献[7])。

图8 不同能量空洞缓解机制的数据收集率测试结果Fig 8 Result of data collection rate test of different energy hole alleviation mechanisms

3.4 平均能量耗散对比分析

图9为距离静态Sink的不同位置节点的能量耗散测试结果。从图中可知，随着距离的增大，能量耗散逐步减小，见图中箭头所指；但本文机制的能量耗散最小，约为0.63 J；文献[6]算法的能量耗散最大，为0.86 J。可见本文机制能够有效缓解能量空洞。

图9 能量耗散测试结果Fig 9 Tests results of energy dissipation

图10为网络平局能量耗散测试结果。从图中可以看到，随着节点数量则增加，三种不同机制的平均能量耗散都在增大；但是本文机制的能量耗散始终是最小。这与图9得到的结论是一致。根据模式(22)～模式(24)可知，由于文献[6,7]算法所需的节点密度较大，直接使得簇内通信总成本增大，最终使得总的通信跳数V增多，从而造成平均能量耗散比本文大。

4 结 论

本文设计了双簇头网格聚类算法，并将其用于WSNs非均布节点能量空洞缓解问题，且构造了主簇头—副簇头—相邻簇头的数据调度传输结构，由主簇头调度簇间通信，由副簇头调度簇内通信，通过相邻簇头将能量与位置信息反馈给主簇头，分散了节点所承担的负载，完成数据更新与广播。测试结果验证了本文机制的优越性。

图10 不同能量空洞缓解机制的平均能量耗散测试结果Fig 10 Average energy dissipation tests results of different energy hole alleviation mechanisms

[1] Arora R,Sandhu S S ,Agarwal P.A proposal for deployment of wireless sensor network in day-to-day home and industrial app-liances for a greener environment[J].Advances in Intelligent Systems and Computing，2014，236(78)：1081-1086.

[2] LU Yuting,Wang Weiyang.Energy hole solution algorithm in wireless sensor network[J].Journal of Networks,2014,9(4)：956-963.

[3] Diwakaran S.Energy efficient scheduling in wireless sensor networks[J].International Journal of Scientific Engineering and Research，2014，2(1)：48-51.

[4] 余育青，郝 平.WSNs中基于时空特性的网络能量空洞研究[J].计算机工程与应用，2013，49(15)：105-112.

[5] 李 斌，王 镇，刘学军.无线传感器网络中基于蚁群算法的能量空洞规避策略[J].计算机科学，2013，40(8)：66-71.

[6] 刘安丰,任 炬,徐 娟.异构传感器网络能量空洞分析与避免研究[J].软件学报，2012，23(9)：2438-2448.

[7] Zhang X,Wu Z.The balance of routing energy consumption in wireless sensor networks[J].ACM Journal of Parallel and Distributed Computing,2011,71(7):1024-1033.

[8] Lin K,Chen M.Balancing energy consumption with mobile agents in wireless sensor networks[J].Journal of Future Generation Computer Systems,2012,28(2):446-456.

[9] Martaa M,Cardei M.Improved sensor network lifetime with multiple mobile sinks[J].Journal of Pervasive and Mobile Computing,2009,5(5):542-555.

[10] Yan R,Yang Y,Kong X P.A non-uniform node distribution policy for routing holes avoidance[J].Achievements in Engineering Sciences，2014，13(6)：1424-1429.

[11] Liu A,Liu Z H,Nurudeen M.An elaborate chronological and spatial analysis of energy hole for wireless sensor networks[J].Computer Standards & Interfaces，2013，35(1)：132-149.

Energy hole alleviation of WSNs based on dual cluster head grid scheduling*

ZHANG Ren-shang1, QU Kai-she2

(1.Shaanxi University of Finance and Economics,Taiyuan 030006,China;2.School of Computer & Information Technology,Shanaxi University,Taiyuan 030006,China)

WSNs energy hole alleviate algorithm based on dual cluster grid-based scheduling is designed,primary and secondary cluster head grid clustering algorithm is designed to form grid cells; nodes are identified according to nodes ID and grid ID; and the computer math model of centre point of grid cell is constructed to determine the cluster head of each cell grid for scheduling the node in cell; as well as data scheduling transmission structure with primary-secondary-neighboring cluster heads is constructed to effectively disperse load of nodes,and theory analysis is carried out on performance of this scheme.Simulation results show that compared with others mechanism,this algorithm effectively avoid energy hole,and node duration time is longest under the conditions of non-uniformly distributed nodes,remarkably eliminate‘funnel effect’.

energy hole; dual cluster head grid clustering; funnel effect; data gathering; network efficiency

10.13873/J.1000—9787(2014)10—0133—04

2014—07—11

山西省自然科学基金资助项目(20120005)

TP 393

A

1000—9787(2014)10—0133—04

张人上(1978-)，男，山西忻州人，硕士，讲师，主要研究方向为无线传感器网络。