基于网格的无线传感器网络非均匀分簇算法

韩鹏玮，王庆生，张 博

(1.太原理工大学计算机科学与技术学院，山西 太原 030024;2.北京大学工学院，北京 100871)

责任编辑:李 薇

无线传感器网络由于在灾难管理、战场监控、医学诊断和环境与栖息地检测等方面的广泛应用，成为研究的热点。然而无线传感器网络作为一个自组织网络，在设计与实现上面临了一些技术方面的挑战［1］。大多数传感器节点由于其电池的不可替换性，使得无线传感器网络通过网络管理技术来进行能量控制机制成为一种挑战。针对分布密度较高的无线传感器网络，目前一种比较有效的节能方法是在网络内对冗余数据进行处理，即在网络层中让路由协议结合数据融合机制，中间节点收到数据后，在转发之前先要对数据进行融合处理，将所需的数据量压缩到最小，平衡网络中各个节点的能量消耗［2］。

对于节点分布密度较大的无线传感器网络，本文提出一种基于网格的无线传感器网络非均匀分簇算法UECG(Uneven Clustering Algorithm Based on Grid in WSN)，平衡了各个节点的能量损耗，进而减少网络总能量的消耗。算法通过划分虚拟网格，减少了各个网格中活跃节点的总数，休眠冗余节点，以降低冗余数据以及传输干扰，并减少不必要的信道侦听，同时在各个网格选出激活节点后通过非均匀分簇算法来解决簇间能量消耗的不平衡问题，从而节省下更多的能量用于簇间数据传送，平衡了网络整体的功耗，最终达到延长网络使用寿命的目的。

1 典型路由协议分析

无线传感器网络的路由协议所包含的内容很多，但其核心思想是簇首选择与分簇以及如何在簇间传输数据［3－4］。分簇方法有很多，簇内可以应用不同的数据交换方法。同时，由于选择簇首采用的方法不同，算法也不相同［5－6］。

1.1 LEACH协议

LEACH(Low－Energy Adaptive Clustering Hierarchy)［7］协议是一种经典的无线传感器网络分簇算法，具有周期性的特点，每个周期分为两个阶段:簇的形成阶段与数据传递阶段。在第一阶段，无线传感器网络用自组织的方式来随机生成簇首节点。在簇首节点被选出之后，簇首以广播方式通知全网络，其余节点则根据接收到的信号强弱来判断加入哪个簇，并告知簇首，以此来形成完整的簇群。在第二阶段，簇内的节点在其相应的通信时间内将数据发送到簇首节点，簇首节点把收集到的数据经过处理后直接发送给基站。在LEACH算法中，节点轮流成为簇首节点，这在一定程度上均衡了节点能耗，从而可以节约网络能量，进而延长网络寿命。

从上述分析中，不难看出LEACH协议的缺点是在不同的簇内，簇首与非簇首的距离是不相同的，节点通信过程中簇首的能耗明显多于普通节点。

1.2 EEUC协议

EEUC(Energy－Efficient Uneven Clustering)［8］针 对LEACH协议的缺点，提出了一种非均匀分簇的思想，它充分考虑到节点间的多跳通信模式。与基站距离较远的簇首节点均通过距离基站较近的簇首节点来进行数据传输，这样距离基站较近的簇首节点会耗费较多能量，因此会引起网络能耗的不均衡。EEUC算法正是为解决这种问题而提出的，它采用非均匀的分簇方法，通过分布式机制来建立簇群。每个节点根据节点与基站的距离来计算竞争半径，也就是成簇半径。充分考虑到节点与基站之间的距离，减轻了距基站较近的簇首负载，避免了据基站较近的簇首节点的过早死亡，从而实现了均衡整个网络的负载。但是EEUC算法的缺点是网络中仍然有大量的冗余数据，并且考虑竞争半径时，没有考虑到簇首剩余能量的问题。

2 能量模型及网络模型

2.1 能量模型

无线传感器网络节点能耗的主要来源是数据的采集、计算与传输，由于传输的能耗远远多于计算与采集的能耗，所以本文主要考虑网络的传输，暂不考虑采集与计算的能量损失。本文采用和文献［7］相同的传输模型。传输模型在发送数据和接收数据时，所消耗的能量为

式中:k是数据长度;d是数据发送距离;ETx－elec(k)是收发电路发送长度为k的数据的电路能耗;ETx－amp(k，d)是长度为k的数据发送距离为d的放大器能耗;Eelec是发射(接收)电路发送(接收)1 bit信息的能耗;εfs和εamp分别是自由空间模型和多路径衰减模型的放大器能耗;ERx－elec(k)是收发电路接收长度为k的数据的电路能耗。

2.2 网络模型

在以S为边长的正方形区域内随机分布N个相同的节点。基站位于方形区域外。本文假设下述条件成立:

1)所有节点都具有相同的结构，具有一样的数据处理能力以及无线通信能力，并且初始能量相同。

2)所有节点的能量无法进行补充，并且都处于静止状态。

3)检测的范围远大于无线传感器网络的边界区域。

4)节点间相互通信能耗相同，即传输链路对称。

3 算法设计与实现

3.1 划分网格

首先将待监控的区域划分为N个等同大小的虚拟网格。传感器节点被随机分散部署在监测区内，每个网格区域里的节点为一组。每个网格由该网格的中心点坐标(x，y)来表示，用(x，y，i)来区分网格的状态是否有效，其中，x与y是网格中心点的横纵坐标，i代表网格当前的状态，i=0和i=1分别表示该网格失效和有效。每个节点设定一个固定的ID值，用来表示该节点所处的网格。每次传输数据，都要激活有效网格内能量最大的节点，休眠余下节点。网格内的活跃节点用来采集相关信息并传送数据，处于休眠中的节点则等待被激活。

3.2 非均匀分簇

非均匀分簇的主要思想是将激活节点分划为规模不同的簇群，簇群的大小由各簇簇首到基站的距离来决定。由于离基站近的簇群转移发送能耗高，故划分较小的簇规模，从而有效减少簇群内部传输的消耗，节省能量填补簇群间的转发能量损耗;给距离基站较远的簇群划分较大的区域，这样可以增加簇群内部各个节点间传输能量消耗，从而平衡了簇群在簇内能耗和簇间能耗。

具体非均匀分簇的步骤如下:

1)分簇阶段，首先需要考虑到的是簇首节点的个数。簇首节点的数量将对网络的能耗产生影响，因此，如何求得最优的簇首节点个数［9］是至关重要的。设网络节点个数为n，K为簇的个数，dtoBS是簇首与基站之间的距离，dtoCH是簇内节点到簇首的距离，EDF是单位数据融合所耗费的能量，I是数据包的大小(二进制位数)。

簇首节点在每一轮中的能耗为

簇内节点在每一轮中的能耗为

整个网络在每一轮中的能耗为

式中:A为正方形区域的边长;LBS是常量，表示基站与正方形区域中心的距离。

将Etotal对K求导，同时使其为0，得到K的最优值使得Etotal的值最小。K的最优值是

从式(6)可以得出，最佳簇首个数与网络的节点个数n、正方形区域边长A和基站与正方形区域中心的距离LBS有关。

2)算出最优簇首个数后，根据各个激活节点的剩余能量，以P概率在激活节点中选出部分节点成为簇首，激活节点被选为簇首的概率为T(n)，T(n)是事先设置好的阈值。每个激活节点都会随机产生一个数，将该数与阈值T(n)进行比较，若小于T(n)，该节点被选为簇首，否则作为普通节点。考虑到LEACH协议中选取簇首时未将节点剩余能量考虑进去，本文在LEACH协议基础上将阈值T(n)改进为

式中:G表示在最后1/p轮中没有当选过簇首的节点集合;p表示簇首节点在所有节点中所占的百分比;r表示选取的轮数;Eremain表示节点的剩余能量;表示第r轮网络中激活节点平均剩余能量。

3)簇首被选出后，根据簇首到基站的距离设定簇的竞争半径Rc。考虑到离基站距离远的节点能量缺失，成簇半径越大导致节点能量损耗越大，因此本文在EEUC协议中竞争半径公式的基础上进行了改进，公式里考虑了能量因素，增加了节点的剩余能量。竞争半径为

式中:dmax和dmin表示网络中簇首到基站的最大距离和最小距离;R表示最大的竞争半径值;pi和pn分别表示已激活节点的初始能量与余留能量;pd是节点失效的临界能量值，即表示节点能量降低到pd时节点失效。节点si到基站的距离记为d(si，BS)，c∈(0，1)用来限制取值范围。从式(8)可以看出，竞争半径根据节点余留能量与据基站位置的改变而变化。

各个簇首在竞争半径内向其余节点广播消息，其余普通激活节点加入并最终形成簇。簇群一旦建立成功便进入到信息采集与传输阶段，利用节点间的多跳通信模式，距离基站较远的簇首节点通过距离基站较近的簇首节点传输数据。

4 UECG仿真与性能分析

本文采用MATLAB仿真，仿真实验均基于同一实验场景，参数配置如表1所示。

表1 网络环境与参数配置

首先将100 m×100 m的范围均匀划分为64个虚拟网格，在此基础上的节点分布和覆盖图如图1所示。从图1中可以看到，多数区域被传感器节点多次重复检测，这样会使大量冗余的信息被采集。在每个网格中激活一个能量最大的节点，休眠其余节点后，检测区域的节点分布及覆盖如图2所示。比较图1与图2可以看出，本算法减少了区域的重复覆盖度，从而大幅减少了冗余数据。同时从图2可以看出通过网格选取出的64个激活节点能保证所监控的覆盖区域在95%以上。

节点分布优化后，选出的64个激活节点通过非均匀成簇后的示意图如图3所示。从图中可以看出，距离基站(50，－50)越近的簇范围越小，而距离基站越远的簇的范围越大。

图3 节点非均匀分簇示意图

在部署400节点的条件下，本算法与LEACH协议和EEUC协议进行比较的结果如图4所示，在实验进行到1 403轮时，LEACH协议的全部节点死亡，EEUC协议在1 784轮时，最后一个节点死亡，而本文提出的算法，在2 201轮时，最后一个节点死亡。比LEACH协议的网络寿命提高了56.88%，比EEUC协议的网络寿命提高了23.37%。

图4 存活节点与网络运行关系示意图

图5是基站接收到的数据总量，从图5可以清楚地看出，UECG协议比LEACH协议和EEUC协议传输的基站接收到的数据总量多，这意味着无线传感器网络通信有更高的利用率。

5 结论

图5 基站接收到数据量

本文研究了无线传感器网络中的LEACH协议和EEUC协议的优缺点，综合之后提出基于网格的无线传感器网络非均匀分簇算法。算法利用虚拟网格来降低数据冗余，并根据簇首与基站之间距离的远近来设定簇群的范围大小。距离基站较近的簇由于簇间转发功耗较高而设定较小的簇规模，通过减少簇内部的能量消耗，补充簇间转发数据的能耗;而距基站较远的簇群在簇间的转发消耗较少，从而可以划分较大的范围来包含更多的节点，增加簇本身的能量消耗。平衡了簇群在簇内与簇间的功耗，有效增加无线传感器网络的生存时间。本文接下来的研究重心将放在寻找异构、非静态网络环境里的节能算法。

［1］王磊，施荣华.无线传感器路由算法中的仿真研究［J］.计算机仿真，2011，28(3):170－173.

［2］李志宇，史浩山.基于最小Steiner树的无线传感器网络数据融合算法［J］.西北工业大学学报，2009，27(4):558－564.

［3］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1588－1600.

［4］周新莲，吴敏，徐建波.BPEC:无线传感器网络中一种能量感知的分布式分簇算法［J］.计算机研究与发展，2009，46(5):723－730.

［5］陶晓玲，王桂凤，王勇.基于Dijkstra的无线传感器网络分簇路由算法［J］.计算机工程与设计，2010，31(17):3807－3811.

［6］王春雷，柴乔林，王华，等.基于分簇的无线传感器网络节能路由算法［J］.计算机应用，2007，27(2):342－345.

［7］HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol for wireless microsensor networks［C］//Proc.the 33rd Annual awaii Int’l Conf.on System Sciences.Maui:IEEE Computer Society，2000:3005－3014.

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

［9］何延杰，李腊元，邢明彦.WSN中一种能量均衡的分簇路由协议的设计［J］.传感技术学报，2009，22(10):1510－1514.