无线传感器网络能量均衡问题的研究

王琨　孙嘉骏

摘 要：在使用无线传感器网络进行数据传输时经常会碰到网络空洞问题。为了避免网络空洞问题，提升无线传感器网络整体的使用寿命，我们提出一种基于网络划分的分簇路由算法。在该算法中，我们先将网络按照距离基站的距离划分为近距离和远距离两部分。在远距离节点中依据节点的邻居节点数目，剩余能量和距离基站距离选择簇首节点，进行分簇路由。仿真实验表明该算法在平衡节点能耗、提升网络生存时间等方面发挥了显著作用。

关键词：能量平衡；无线传感器网络；分簇路由

中图分类号：TP393.0 文献标识码：A

1 引言（Introduction）

无线传感器网络是由大量的传感器节点组成的特殊的数据采集、传输、接收以及处理的网络系统。在该网络中，通过将传感器节点部署到目标区域的各个角落来进行对目标区域内特定数据的采集工作，随后通过无线传输的方法将各个节点采集到的数据传输给基站节点，并由基站节点完成对数据的后续加工处理，从而实现对目标区域进行实时监控的目标。特别地，无线传感器网络在不适宜人类活动的场所发挥着不可替代的应用。然而随着无线传感器网络推广和应用，人们发现能量问题是其实际应用中必须解决的难题。无线传感器中每个传感器节点体积有限，难以配置大容量的供电设备，致使每个传感器节点的能量有限，如果单个节点的能量耗尽，那么它将不再参与后续的数据的转发、接收工作，我们将这类节点称为“死亡节点”。特别地，在数据的传输过程中，存在这样一类节点：它们由于其自身位置的特殊的原因，会比周围其他节点更多次的进行数据转发和接收，从而提前死亡。它们死亡后周边区域内的节点会因为找不到替代的中继节点而无法将数据发送给基站节点。我们将这类问题称为无线传感器网络的传输空洞问题。当传送空洞范围无限扩大时，网络的连通性就会被破坏，造成远端节点即使有能量也无法将数据传送给基站，或者必须使用大能耗的远距离单跳传输方式传输，最终导致整个网络提前死亡。为了避免和解决传输空洞问题，学者们进行了广泛的研究，尝试了各种策略。研究表明分簇路由算法在平衡能量消耗、节省能量等方面比平面路由算法有更好的表现。如图1所示，分簇路由将网络分割成不同的节点簇，每个簇包含一个簇首节点和若干个簇成员节点。簇成员节点将信息以单跳发送给簇首节点，而簇首节点则负责对簇内节点发送的数据进行数据融合，去掉冗余的数据，将融合后的数据转发给接簇外的节点。一般情况下，簇首节点距离基站节点距离较远，而研究表明，在远距离无线传输的情况下，使用多跳传输比单跳传输更节省能量，所以分簇路由实际上是通过由簇首节点组成的骨干网络将各分簇内的数据转发给基站节点的。不难发现，簇首节点在分簇路由算法中发挥中至关重要的作用，簇首节点会比簇内其他节点耗费更多的能量。因此分簇路由往往依据特定的标准定期重新选择新的簇首节点，并以此生成新的簇重新进行分簇路由传输。簇首节点的选择方法是影响分簇算法效果的关键因素。优秀的簇首选择算法可以生成高效的节点簇，大大降低生成节点簇的能量消耗，平衡整个网络的节点能量消耗。与此同时，距离基站较近的节点也会由于其位置的原因，比其他的节点更多的参与到数据的转发过程中，能量开销也比其他节点大。显然良好的分簇路由算法应该避免近距离节点成为簇首节点，因为这样会大幅度增加近距离节点的能量开销，容易产生网络空洞。本文的主要思想是根据节点距离基站的距离对网络进行划分，近距离节点不参与分簇路由，直接使用单跳传输与基站交互；远距离节点则根据其剩余能量、周围的网络拓扑特征等多个因素制定簇首选择的方案，并以此为依据建立簇并进行分簇路由，将数据从各簇成员节点通过由簇首节点组成的骨干网转发给基站节点。

本文第2节介绍相关工作；第3节给出系统模型；第4节全面阐述网络划分方法以及分簇算法；第5节对路由算法进行仿真对比，说明本文提出的算法的有效性；第6节给出论文的结论。

图1 分簇路由结构图

Fig.1 The structure of the cluster-routing

2 相关工作（Related work）

近年来，学者们先后提出几类典型的基于分簇的分层路由协议。比如LEACH[1]、LEACH-C[2]、HEED[3]等。其中LEACH算法根据同等概率随机选取小部分节点成为簇首，所有的节点按照该概率轮流成为簇首。簇首选择完毕，其他的节点将按照位置关系选择合适的簇首节点生成簇。在LEACH中，这些簇的大小是相同的。簇首节点直接通过单跳的方式将数据发送给基站。研究表明该算法在能耗和能量均衡使用方面存在弊端。相比之下HEED算法在选择簇首节点时则优先考虑候节点的剩余能量，初步生成一个符合剩余能量条件的备选节点集合。然后依据备选集合中各节点的簇内通信开销来选择最终的簇首节点。该算法需要在竞争半径内发送过多的消息，能量开销较大。上述的算法的思想都是让所有的节点都有近似相同的概率成为簇首节点，同时兼顾簇内节点向簇首节点传输的开销均衡，通过不断重新划分簇来均衡不同节点的能量消耗，达到均衡节点能量消耗的目标。而在实际中存在着这样的一个事实：距离基站节点近的节点总是会比其他距离较远的节点传输更多的数据，消耗更多的能量。因此如果仅仅追求通过公平的划分簇，同等概率的选择簇首节点来均衡节点开销势必难以弥补该类近距离节点由于其位置原因而额外传输数据所产生的额外的能量开销。而这些额外的开销最终会导致这些近距离节点提前能量耗尽，产生网络空洞。在近距离区域成为网络空洞的条件下，远端节点必须放弃多跳路由而改用单跳路由将数据传输给基站节点，造成更多的能量消耗，加快整个网络的死亡。为了解决这个问题，EEUC[4]提出划分大小不同的簇，降低近距离节点成为簇首的概率以及减少近距离节点簇的规模，降低近距离节点由于参与分簇路由而产生的能耗。除此之外，I-EEUC[5]和ACOUC[6]也都采用了EEUC的思想。这些非平衡的分簇路由协议在均衡网络节点能耗，延长网络使用寿命等方面发挥了显著效果。

3 系统模型（System model）

3.1 网络模型

我们假设被研究的网络具备以下特点：被监测的区域是个M*M的方形区域。所有的节点随机分布在该区域内。该网络仅有一个基站，该基站位于被监测区域外侧并且具有充足的能量。区域中有n个节点。

我们假设每个节点都具备以下特点：所有的节点都是静止节点；每个节点有一个唯一的标识ID；每个节点都有相同的初始能量，相同的运算能力和传输数据能力。节点可以根据传输距离调节传输能量强度；每个节点可以根据接收到的信号强度（RSSI）来判定信号源距离其本身的距离。

3.2 能量消耗模型

无线传感器节点通常情况下由四个模块组成：感知模块、数据处理模块、数据传送接收模块、电池模块。其中数据传送和接收所消耗的能量要远远大于其他模块。因此本文在考虑节点能耗时仅仅考虑节点接收和发送数据产生的能耗，其他能耗忽略不计。根据能量消耗模型，传输k比特的数据，消耗的能量由式（1）来计算。其中k是被传输的比特数；d是传输距离；当d小于阈值d0时功率放大损耗采用自由空间模型；当传输距离大于等于阈值d0时，采用多路径衰减模型。、分别为这两种模型中功率放大所需的能量。接收k比特的数据时，能耗由式（2）计算。

（1）

（2）

4 算法设计（Algorithm design）

从上节的式中不难看出，节点的能耗与节点距离基站节点的距离是有关联的。特别地，在我们的网络模型中，基站节点位于被监测节点的外侧，近基站区域的节点会比非近基站区域的节点有更高的概率成为中继节点，将数据转发给基站节点。因此该区域内的节点的能耗将比其他区域的节点高很多。为了平衡不同节点间的能量消耗，我们决定先对网络进行划分，找出近距离节点的集合和远距离节点的集合。近距离节点不参与分簇路由，而是专门负责转发其他远距离节点的数据给基站节点。而远距离节点则仍然使用非均衡的分簇路由方式将数据传递给近距离节点。我们认为这种划分和分簇相结合的方法对于均衡网络能耗来说是非常必要的。

4.1 网络划分

网络划分阶段分为两个步骤。首先，基站向监控区域内发送广播信号。在系统模型中我们已经假设过基站的能量是充足的。所以这里我们可以保证基站发送的信号能量强度是足够强的，区域内的所有节点都可以接收到这个信号。每个节点接收到信号后立刻根据该信号的能量强度RSSI来估测其距离基站节点的距离。这里我们使用式（3）估测节点距离基站节点的距离。之后，我们开始依据每个节点距离基站的距离进行网络划分。图2给出了符合系统模型要求的应用场景。基站节点位于待监控区域的某一侧，通过设定不同的半径我们可以获得若干个以基站为圆心的同心圆，这些圆会逐渐覆盖区域内的所有节点。这里我们的划分目标是找到一个合适的圆环，将圆环内的节点划分为近距离节点，圆环外边缘到远方监控区域边界的节点划分为远距离节点。这里我们假设从基站到被监测区域最近的距离是R，现在的问题是要选取一个圆环的宽度r确定一个圆环，使得圆环内的节点划分为近距离节点。通过实验和推导，我们选定用式（4）计算r，其中c为预期的近距离节点占节点总数的比例。之后每个节点按照其距离基站的距离来判断其是否为近距离节点。如果，则其为近距离节点；如果，则其为远距离节点。

（3）

（4）

4.2 分簇的建立

当近距离区域划分完毕后，所有近距离节点进入休眠状态，不参与分簇的过程。其余的节点采用竞争的方法竞选簇首节点。为了参加竞争，每个节点必须先计算出其自身的竞争半径。然后向其竞争半径内的节点广播其自身信息。我们可以根据式（5）计算节点的竞争半径。其中表示区域边缘距离基站的最大距离；c是属于区间[0，1]的调整系数，是默认的节点最大竞争半径。不难看出，节点的竞争半径与其距离基站的距离成正比。这样我们可以保证距离基站远的节点有更大的概率成为簇首节点，同时它的簇成员数量也要多于距离近的节点。

（5）

图2 应用拓扑图

Fig.2 Application topological graph

以下我们详细描述簇的划分与生成步骤。在初始化状态时，节点依据基站节点发送的信号强度估测其距离基站节点的距离。之后比较与R+r的大小关系，认定自身是否为近距离区域节点。在分簇过程时，所有的近距离节点进入休眠状态，不参与此过程。所有的远距离节点根据式（5）计算出各自的竞争半径，然后向竞争半径内的所有节点广播自身的ID信息。节点依据在此阶段收到的其他节点的广播信息来更新自身的邻居节点数量（节点度）。同时节点还根据式（3）依据信号强度计算出自身到每个邻居节点的距离。接下来我们要依据式（6）计算每个节点的竞争时间长度。每个节点在其竞争时间内如果收到了其他节点的簇首节点的声明信息，那么该节点会放弃竞争簇首节点。当竞争时长结束时，如果没有收到其他节点的关于簇首的声明信息，那么它自身向竞争半径内的其他节点发送簇首声明信息。当所有的节点的竞争时长都结束时，没有成功竞争成为簇首的节点会按照距离的远近选择最近的簇首节点生成分簇。如果存在多个簇首节点距离其本身的距离相同，则选择节点度数较低的簇首节点加入。此过程结束，节点或者成为簇首节点，或者成为簇成员节点。不难发现，节点的竞争时间段越短，其竞争成功的概率就越大。从式（6）可以发现，当节点具备更大的剩余能量Er_i，更大的节点度，更广泛的竞争半径，它的竞争时间就越小，成为簇首的概率就越高。

（6）

4.3 簇间路由

当远距离节点完成分簇时，簇成员节点会将数据直接发送给各自的簇首节点，而簇首节点则按照下面的规则通过多跳的方式将数据转发给基站节点。

初始信息更新阶段：近距离节点和簇首节点开始广播路由信息。其中包含簇首节点ID，其距离基站的距离。其他的簇首节点接收到该信息后比较自身基站距离与广播包中声明的基站距离，如果包中声明的距离大于其自身的距离，则说明该簇首对应的簇距离基站比当前节点本身距离基站还要远，因此忽略不计。如果自身的距离大于包中声明的距离，则把该簇首节点作为备选下一跳节点加入到备选集合中。光结束后，簇首节点选择距离自己最近的备选节点作为下一跳路由节点。

5 仿真实验（Simulation）

5.1 仿真条件介绍

我们选用Matlab平台来进行仿真。对比的对象包括LEACH算法、EEUC算法、I-EEUC算法，在实验中我们分别用（a）、（b）、（c）来表示，（d）代表我们的算法。实验中，被监控区域的大小为200m*200m，节点被随机部署到该区域的各个角落。基站节点位于监控区域的一侧，坐标为（250，100）。

5.2 仿真结果

图3展示的是节点能量消耗仿真实验的结果。d代表的我们的算法，a、b、c分别代表的LEACH、EEUC、I-EEUC算法。在多轮实验中我们的算法的节点能量消耗始终小于其他三个算法。由此可见我们的想法是正确的，算法是可行的。图4展示的是节点能量消耗的标准差对比，反映的是算法的节点能耗均衡程度。从图中可以看出：除了LEACH算法在能耗平衡方面存在明确的缺陷外，其他三个算法在能耗均衡方面都有着不错的表现。图5展示的是网络的生存时间长度对比。可以看出，我们的算法比其他三个算法更有效的提高了网络整体生存时间。从以上的三个仿真实验中我们不难看出：本文提出的算法在节约节点能耗、均衡节点能耗、延长网络生存时间等方面比传统的分簇路由算法有着更好的表现。

6 结论（Conclusion）

本文提出了一种基于网络划分的分簇路由算法。该算法依据距离将网络划分为近距离节点和远距离节点。远距离节点依据邻居节点数目、节点剩余能量等因素选择簇首节点，建立大小不等的分簇，使用分簇路由的方法将数据包转发给近距离节点，再由近距离节点转发给基站节点。实验证明，我们的算法不仅提高了网络节点能耗的均衡程度，还提高了网络的生存时间。我们相信将分簇算法与网络拓扑特征相结合的想法是正确的，能够帮助改善无线传感器网络在实际应用中的使用效果。

图3 能量消耗对比图

Fig.3 Comparison of energy consumption

图4 能量消耗标准差

Fig.4 Standard deviation of energy consumption

图5 网络生存时间

Fig.5 Network lifetime

参考文献（References）

[1] Degan Zhang，Guang Li，Ke Zheng.An energy-balanced

routing method based on forward-aware factor for Wireless

Sensor Network[J].IEEE Transactions on Industrial Informatics，

2014，10（1）：766-773.

[2] Yan Xingfang，Xi Jiangtao，Joe F Chicharo.An energy-aware

multilevel Clusteringalgorithm for wireless sensornetworks[C].

Sydney：InternationalConference on Intelligent Sensors，Sensor

Networks and Information Processing，2008：387-392.

[3] Baojie Chai，Baoying Ma，Shuping Fan.An improved EEUC

routingalgorithm for wireless sensor network[J].Microcomputer

Information，2012，28（9）：366-368.

[4] LEI Jie.Clustering routing algorithm for wireless sensor networks

basedon changing energy[J].Computer Engineering and

Applications，2009，45（33）：105-107.

[5] Degan Zhang，Yannan Zhu.A new constructing approach for

a weighted topology of wireless sensor networks based on local-

world theory for the Internet of Things（IOT）[J].Computers &

Mathematics with Applications，2012，64（5）：1044-1055.

[6] Younis O，Fahmy S.Heed：A hybrid，energy-efficient，distributed

clustering approach for ad-hoc sensor networks[J].IEEE

Transaction on Mobile Computing，2004，3（4）：660-669.

作者简介：

王 琨（1985-），男，硕士，讲师.研究领域：无线网络.

孙嘉骏（1985-），男，硕士，讲师.研究领域：自动化控制.