基于双Sink非均匀成簇的无线传感器网络能量空洞避免策略

谢琳

（四川大学计算机学院，成都　610065)

基于双Sink非均匀成簇的无线传感器网络能量空洞避免策略

谢琳

（四川大学计算机学院，成都610065)

无线传感器网络；能量空洞；双Sink；非均匀成簇

0　引言

近年来，无线传感器网络（Wireless Sensor Network，WSN）由于其良好的扩展性以及较强的抗毁性，已经被广泛应用[1]，如环境监测、健康医疗、抢险救灾、战场监视等领域[2]。WSN在众多领域的广泛应用给人们生活以及工业生产都带来了极大的便利，然而传感器节点的能量受限问题制约了WSN的发展。在网络中，各个区域的传感器节点通信负载不同，通信负载较大的区域的传感器节点能量消耗更快，进而会过早的耗尽能量，成为死亡节点，导致网络数据传输中断，出现“能量空洞”现象[3]。研究表明，当网络出现能量空洞时，网络剩余能量为70%以上，大多数网络甚至高达90%[4]。然而，当传感器节点自身携带的电池能量耗尽时，以人工方式为其更换电池是不现实的。鉴于此，如何在有限能量的情况下提高能量利用率、避免能量空洞、延长网络生命周期具有重要的研究价值和现实意义[5]。

本文针对无线传感器网络的能量空洞问题，提出一种双Sink部署的节点非均匀成簇算法DS-EEUC。在无线传感器网络中部署两个Sink，可以有效缩短传感器节点与Sink之间的距离，有效降低节点在通信过程中的能量消耗，又能提高网络可靠性。在成簇阶段，采用非均匀成簇策略。其原理是根据簇头与Sink距离的不同，调节簇的竞争半径，以达到减缓簇头能耗速率、延长网络寿命的目的。算法的实现包括以下几个方面：确定网络中两个Sink的最优位置；在成簇阶段，网络内每个节点根据剩余能量和与Sink相对距离决定是否成为簇头或者成为某个簇中的成员；在数据传输阶段，根据该簇头与Sink的距离，簇头作出判断将融合后的数据通过最短路径多跳传输到距离较短的Sink。

1　网络与能耗模型

1.1双 Sink 无线传感器网络模型

在本文中，对网络模型做出以下假设：

（1）网络位于一个A×A的方形区域内，A默认值为300m；

（2）网络中存在两个Sink，它们具有极强的计算和存储能力、并且有充足的能量。Sink分别位于方形网络中以对角线划分的三角形的重心处，位置固定不变；

（3）N个传感器节点在网络范围内随机分布，并且，传感器节点在部署后不再移动；

（4）网络内各个传感器节点具有相同的初始能量Einit，传感器节点的无线发射功率可调，即节点可以根据接收者的距离来调整其发射功率；

（5）网络内节点非均匀成簇，簇头在数据融合处理后，负责传输到Sink；

（6）链接是对称的.如果传输功率已知，则节点可以根据接收到的信号的强度来计算距离。

网络模型结构如图1 所示。

图1　网络模型

1.2双Sink的 最优位置计算

方形网络均分为两个等腰直角三角形，双Sink的最优位置分别为两个三角形的重心处。

如图2 所示，△ABC中，做三条中线，相交于一点，该点叫做三角形的重心。

图2　Sink位置布局

该重心满足以下三个性质：

（1）通过三条中线划分得到的六个三角形面积相等；

（2）重心和三角形3个顶点组成的3个三角形面积相等；

（3）重心到三角形3个顶点距离的平方和最小。

综上可得，若Sink放置在重心位置，一方面可以使Sink在网络各方向均匀覆盖；另一方面可以使网络内簇头节点与其的数据传输距离整体上保持较短，提高网络总的能量利用率。至此，确定两个Sink在网络中的位置。

1.3能量模型

本文使用能量消耗模型与文献[3]相同，不考虑节点计算、存储等过程的能耗，仅考虑节点数据通信的能耗。经过距离d传输lbit信息，发送端能量消耗为：

其中， Eelec表示发送或接收1bit数据时的能量消耗，是发送1bit数据放大器的能量消耗。

2　成簇算法

2.1簇竞争半径的计算

由于网络采用节点随机分布，节点密度近似均匀。所以在计算每个簇竞争半径时，仅考虑簇头与Sink距离即可，无需考虑节点密度因素。

公式3中，α为常数因子，dmax和dmin分别代表网络中节点到Sink的最大距离和最小距离为最大竞争半径，d（i，Sink1）为节点到Sink1的距离值，min[d（i，Sink1），d（i，Sink2）]是取节点i到Sink1和Sink2距离的最小值。根据公式可得，节点i在网络中会选择离自己较近的Sink发送数据，并且节点i的竞争半径与其到Sink的距离呈线性正相关，即，节点i与Sink距离越近，其竞争半径越小。则靠近Sink的簇头，其在簇内数据通信方面所消耗的能量会大幅降低，在有限的初始能量下，可以有更多的能量用于簇间的数据转发，所以，网络中不同区域簇头的能耗得到平衡，可以有效延长网络生命周期。

2.2 构建簇

本文根据剩余能量比率RRE（i）和竞争半径比率RD（i）共同选举簇头，节点成为簇头的概率计算既要考虑簇头节点要拥有更多的剩余能量，也要考虑尽量减少簇内的通信能耗。簇头选择过程如图3 所示，簇头选择概率公式计算如下：

P为节点成为簇头的概率值。RRE（i）表明节点i的邻居节点的平均剩余能量与节点i的剩余能量之比。即表示节点i的所有邻居节点的剩余能量的均值代表节点i自身的剩余能量。若RRE（i）＜1，则说明节点i的剩余能量大于其通信半径内节点的平均剩余能量，可加入候选簇头集合；RD（i）表明候选簇头i和其竞争半径范围内所有节点距离的平均值与候选簇头i竞争半径的比重。即，

图3　簇头生成过程

确定簇头后，普通节点j根据簇头节点的剩余能量，以及j和各个簇头之间的距离选择簇加入。

2.4数据转发路由

簇头首先判断其与两个Sink的距离，选择将数据传输给距离较短的Sink，公式如下：

其次，选择中继簇头进行数据转发。转发概率的计算同时考虑节点剩余能量和与选定Sink的距离。转发概率Q的计算如公式（6）所示为节点当前的剩为网络中各个簇头剩余能量的均值，maxd（i，Sink）为网络中簇头与Sink的最大距离，d（k，Sink）为该簇头与Sink的距离。根据公式（7）可得，若该簇头的剩余能量越高，与Sink距离越近，则其成为中继簇头的概率Q越高。

3　实验与仿真

本文用C语言对DS-EEUC算法进行仿真实验，将DS-EEUC、LEACH[6]、EEUC[7]算法做相关性能的对比，表1为实验采用的多种参数。余能量

表1　实验参数

在LEACH、EEUC、DS-EEUC算法中，随机选取10轮，取每轮簇头消耗能量之和，如图4所示。图中LEACH算法的簇头能耗最大，由于它采用单跳传输方式，导致簇头能耗过大；EEUC和DS-EEUC由于采用多跳通信方式，所以簇头能耗较小，而DS-EEUC采用双Sink，可以有效缩短簇头到Sink的转发路径长度，使得本算法的簇头能耗最低。图5 为三种算法下的网络生命周期对比，DS-EEUC算法有效地延长了网络生命周期。图6为三种算法下网络剩余能量的比较，从图中可以看出，DS-EEUC算法的网络剩余能量曲线的斜率p均低于LEACH、EEUC算法。即本算法有效降低了每轮网络的能量消耗。

图4　簇头能耗总和

图5　网络生命周期

图6　网络剩余能量

4　结语

本文通过建立双Sink、非均匀成簇的网络模型，提出DS-EEUC算法。通过实验仿真情况可以得到，与LEACH、EEUC算法相比，DS-EEUC可以有效提高网络能量利用率、延缓能量空洞的形成、延长了网络生命周期。

[1]李建中，高宏.无线传感器网络的研究进展[J].计算机研究与发展，2008，45（1）:1-15.

[2]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）:1282-1291.

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

[4]Song C，Liu M，Cao J，et al.Maximizing Network Lifetime Based on Transmission Range Adjustment in Wireless Sensor Networks[J]. Computer Communications，2009，32（11）:1316-1325.

[5]曾志文，陈志刚，刘安丰.无线传感器网络中基于可调发射功率的能量空洞避免[J].计算机学报，2010，33（1）:12-22.

[6]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].Wireless Communications，IEEE Transactions on，2002，1（4）:660-670.

[7]蒋畅江，石为人，唐贤伦.能量均衡的无线传感器网络非均匀分簇路由协议 [J].软件学报，2012，23（5）:1222-1232.

Wireless Sensor Networks;Energy Hole;Double Sink;Non-Uniform Clustering

Energy Hole Avoidance Strategy Based on Double Sink and Non-Uniform Clustering for Wireless Sensor Networks

XIE Lin
（College of Computer Science，Sichuan University，Chengdu 610065）

谢琳（1992-），女，黑龙江密山人，硕士研究生，研究方向为无线传感器网络

2015-11-19

2016-01-15

为了解决无线传感器网络的能量空洞问题，延长网络生命周期，对能量空洞现象进行研究，建立双Sink、节点随机分布的方形网络模型；通过分析确定Sink位置，优化簇构建过程，提出层次路由算法。给出基于双Sink非均匀成簇的无线传感器网络能量空洞避免算法DS-EEUC。仿真结果表明，该算法和LEACH、EEUC相比，在网络寿命和能量利用率方面有显著提高。

In order to solve the problem of energy hole in the wireless sensor networks,prolong the lifetime of network,studies the phenomenon of the energy hole,constructs the network model with double Sink,and nodes are randomly distributed.Determines the position of Sink by analysis,optimizes the process of cluster construction and proposes hierarchical routing algorithm.Proposes Energy Hole Avoidance Strategy Based on Double Sink and Non-uniform Clustering for Wireless Sensor Networks(DS-EEUC).The simulation results show that,compared with LEACH and EEUC,DS-EEUC improves the network lifetime and network energy efficiency.