基于非均匀分簇与路径优化的 WSN路由协议*

刘国繁，许 多

（1.湖南工程学院电气信息学院，湖南 湘潭 411104；2.湘潭大学信息工程学院，湖南 湘潭 411105）

基于非均匀分簇与路径优化的 WSN路由协议*

刘国繁1，许 多2

（1.湖南工程学院电气信息学院，湖南 湘潭 411104；2.湘潭大学信息工程学院，湖南 湘潭 411105）

在无线传感网络中，传感节点的能量有限性，使得能量有效利用成为其“热点”问题。针对LEACH协议簇头的随机选择，导致成簇不合理或簇头节点加速死亡，簇首与基站直接通信能量消耗大的问题。提出了一种高能效路由协议 UCPO。该协议根据最佳簇头个数划分区域，综合考虑簇内能量消耗和节点剩余能量选择簇头，以多跳方式完成数据的发送。仿真表明，改进协议显著减少整个网络能量消耗，延长了网络的生存周期。

LEACH；非均匀分簇；路径优化；最佳簇头数；Dijkstra算法

1 引言

无线传感网络WSN（Wireless Sensor Network）是当今的一个热门领域，它集成了分布式算法、信号处理、网络与协议、数据库和信息管理技术、嵌入式系统［1］。网络中的传感节点能够自组网络［2］，将监测数据从偏远或危险区域汇集给用户。由于节点能量一般无法补充，为了尽量延长网络生存时间，如何使用网络节点能量成为该领域研究的一个重要内 容［3，4］。WSN中 的能 量 消耗［5］主 要 包括通信能耗、计算存储能耗、数据采集能耗，其中通信能量消耗所占比重最大，因此如何减少通信的能耗成为关键问题。

LEACH（Low Energy Adaptive Clustering Hierarchy）协议［6］是较早提出来的无线传感器网络自适应集簇分层路由协议。近年来，很多研究学者对LEACH协议进行了改进，主要有以下三类：改 进阈 值 公式［7］、簇 内 优 化［8］和 通 信路 径 优化［9～11］。这些改进协议 从不同 方 面减 少 了无 线传感网络节点能量消耗。

大量研究表明，通信过程中簇头的选择方式及位置、簇头与基站的通信路径能够减少节点能量消耗。本文从能耗角度分析LEACH协议和LEACH-MC［12］协议，针对LEACH协议簇头的随机选择可能导致簇头剩余能量不足、簇头数波动和分布不合理，以及簇头与基站直接通信导致簇头能耗较大，提出了一种基于非均匀分簇与路径优化UCPO（Uneven Clustering and Path Optimizing）的无线传感网络路由协议，该协议能有效提高WSN的生存时间。与其他改进协议一样，本协议不考虑网络的时延和丢包。

2 非均匀分簇与路径优化

2.1 非均匀分簇

2.1.1 最优簇头数

对于LEACH协议，簇头数目不同，整个网络的能耗也不同，且总能耗差距比较明显。因此，寻找总能耗最小的最佳簇头数很有意义。为了便于分析，我们假设每轮所选簇头个数为k，监测区域大小为M*M，分布的节点总数为N，于是，平均每个簇的节点个数为N/k，每个簇中有1个簇头和（N/k）—1个成员节点。每个簇头从成员节点接收采集的数据，经过融合后发送到基站。假定簇头向基站传输的能耗模型是多路径损耗模式［6］，则簇的能量消耗ECH如下：

其中，l表示每次传输数 据的比特 数，dto-BS表示簇头与基站之间的距离，Eelec是 发送 或接 收一 个字节所消耗的能量，EDA为数 据融 合 率，εamp为 功率 放大器的放大倍数。

对于成员节点，采集完数据，进行融合处理并发送给簇头，每个成员节点一次向簇头发送一帧数据。成员节点与簇头的距离在同一簇内一般较近，不会超出一阶无线电模式的自由空间能耗阈值d0，所以普通节点向簇头发送数据的能量消耗Enon-CH如下：

其中，dto-CH表示该成 员节 点到 本 簇簇 头 的距 离，εfs为功率放大器倍数。

假设把监测区域均匀划分，那么所划分的每个虚拟小区域的面积是M2/k。设随机布放的一个节点坐标为ρ（x，y），则簇内节点到簇头的距离平方期望值如下：

为了便于计算分析，用一个与虚拟小区域面积相同的圆作等价变换，这个圆的面积为M2/k，则由圆面积公式可得该圆的半径是：

把上式所得的R代入到式（3），经过化简、计算可得：

如果区域内节点分布密度是均匀的，可以得到：

将上面所得的ρ代入式（5）得：

将得到的dto-CH平方期望值代入到式（2）得：

一个簇内的能量消耗由簇头能耗和成员节点能耗两部分组成，因此，一个 簇的能量 消耗Ecluster如下：

整个监测区域是由k个簇组成，那么整个区域的能耗Etotal如下：

将每个簇的能耗代入式（10），可得：

根据式（11），可以求出整个监测区域能耗最小时的k值，它就是最佳簇头数kopt，如下式：

2.1.2 区域划分

根据上面的计算，UCPO协议将监测区域划分为若干虚拟小区，每个虚拟小区选择一个节点作为簇头，虚拟小区的个数为式（12）确定的最佳簇头数。UCPO协议采用非均匀分簇，即各虚拟小区面积不等，簇的大小也不同。距离基站较近的虚拟小区，面积相对减小，簇也相应较小；距离基站较远的虚拟小区，面积相对增大，簇也相应较大。

假设在一个100×100的正方形区域，随机分布100个无线传感器节点，基站位置在 （50，220），由式（12）可得，最佳簇头数为5，于是，将整个监测区域划分成5个虚拟子区域，对每个虚拟区域中的节点都作标记node_area。如果节点在子区域i（i=1～5），则该节点的node_area=i。采用非均匀分簇，以整个区域上下方向的中线为分割线，将整个区域分成上下两个部分，再将靠近基站的上部分分成三个大小相等的子区域，下部分分成两个大小相同的子区域，具体划分如图1所示。

Figure 1 Areas division图1 区域的划分

2.1.3 簇头选择

在上述虚拟区域中，设某个区域有j个节点，其中任一个节点i的坐标为 （xi，yi），可以求出该区域j个节点的“中心”Center的坐标如下：

所得“中心”位于虚拟区域的中心，选择距离“中心”位置最近的节点作为该区域的候选簇头，检查该节点的剩余能量是否超过了该区域节点剩余能量平均值Eaver：

如果该节点的剩余能量大于Eaver，则当选为簇头；否则，选择距离“中心”位置次近的节点作为候选簇头，如此循环直至在该区域找到簇头。

选出簇头后，UCPO协议本“轮”的后续运行

接收节点收到l比特数据需要消耗的能量ERX如下：

式（15）、式（16）中，Eelec表示节点发送或接收l比特数据所需要消耗的能量，εfs、εamp分别表示自由空间模型和多径衰减模型下功率放大器倍数。

UCPO协议的多跳方式采用了Dijkstra算法思想。Dijkstra算法原理如下：

（1）N为每轮选出的簇头总数，V为除路径起始簇头O外的其他簇头集，S为已求出最短路径的簇头集，E（i）表示簇头到基站的能量消耗，E（i，j）表示从簇头i到簇头j的能量消耗，node_id保存最佳路径簇头的id，node_id的初始值为簇头O的id。

（2）在V中找出簇头j，使之符合E（O，j）= Min｛E|vj∈V｝，则簇头j就是簇头O最小能量消耗的下一跳簇头，路径就是E（O，j），将簇头j并入集合S：S=S∪｛j｝。

（3）找出下一跳簇头节点j后，从簇头j出发继续寻找下一跳簇头n，使簇头n发送数据到簇头节点j能耗最小。

（4）重复步骤（2）、（3）直至到达基站为止。

按UCPO协议，其簇头总数由式（12）确定，从距离基站最远的簇头到基站的数据传输不需要经过太多中继簇头，因此我们对Dijkstra算法进行了适当改进。改进的Dijkstra算法如下：

假设某条路径的起始簇头节点仍为O节点，中继节点为r节点，E（O，j）表示从起始簇头到中继簇头的能量消耗，E（O）表示从簇头O到基站的能耗，D是最佳路径的节点标号集。

（1）初始化：将较远子区域的簇头节点O标号与LEACH协议相同。在下一“轮”簇头选择时，再按上述簇头选择的方法选择新一“轮”簇头运行，直至网络失效。

2.2 路径优化

UCPO协议从簇头到基站的数据传输采用多跳传送。设通信的两簇头节点距离为d，如果距离d＜d0，则发送节点的能耗模型是自由空间损耗模型；若d≥d0，则发送节点的能耗模型是多路径衰减模型。因此，发送节点和接收节点间的距离为d时，发 送 和 接 收l比 特 数 据，发送节点的 能 耗［6］ETX如下：放入D中，较近子区域的簇头直接与基站通信。

（2）计算其它簇头r到簇头O的能量消耗值，存入E（O，r）中，再计算中继簇头r到基站的能量消耗，存入E（r）中。

（3）选择能耗E（O，r）+E（r）最小的路径进行传输。

（4）如此循环进行，直至所有簇头的数据向基站发送完成。然后，进入下一轮的运行。

与Dijkstra算法相比，改进算法能避免所有的数据都通过距离基站最近的簇头转发，防止距离基站最近的簇头过早死亡。如图2所示，五角星代表基站，如果按照Dijkstra算法传输，簇头A向基站发送数据，簇头A首先选择距离最近的簇头B作为下一跳簇头，簇头B则选择最近的簇头C为下一跳簇头，簇头C直接向基站发送数据，则传输路径是A→B→C→基站。而采用改进算法，簇头A则会选择B或者C作为下一跳的簇头，再由下一跳簇头向基站传输数据，如果A→B→基站这条路径的能耗小于A→C→基站，则选择A→B→基站这条路径传输数据。

Figure 2 Data transmission path of the improved Dijkstra algorithm图2 Dijkstra改进算法的数据传输路径

3 仿真结果和分析

我们采用Matlab仿真软件对LEACH、LEACH-MC和UCPO协议进行比较分析。对比了LEACH协议簇头数目和改进协议簇头数目的

稳定 性、分 布 位 置 的 均匀性，计 算 LEACH、LEACH-MC和UCPO三种协议的簇头存活数，分析它 们 的能 量 效率，证 明 UCPO协 议 优 于LEACH协议和LEACH-MC协议。实验中所用的环境参数如表1所示，其能耗模型的相关参数取自文献［13］。

Table 1 Experiment parameters表1 实验参数

Figure 3 Cluster heads'number of the LEACH rounds图3 LEACH协议各轮簇头个数

由图3可知，LEACH协议的簇头产生的波动性较大，簇头数目最少是2，最多可达8。UCPO协议根据公式（12）确定最优簇头数为5，这种方法不存在簇头数目的波动问题。由前面的分析计算可知，簇头个数为最优簇头数，能够使整个网络的能量消耗始终保持在较低水平。

Figure 4 Cluster heads distribution of a LEACH round图4 LEACH协议某轮簇头分布

图4是LEACH协议某轮的簇头（用实心圆表示）分布图，图5是UCPO协议的某轮簇头（用实心圆表示）分布图。通过对比可看出，LEACH协议的簇头数为3，簇头偏离了最佳簇头数，且分布在整个监测区域的右侧，左边的区域完全没有簇头，分布很不合理。UCPO协议簇头的数目一直保持最优，簇头分布比较均匀，簇头与簇头之间的距离合适，能够改善簇头能耗，从而有效降低整个网络的能量消耗，延长网络生存时间。

Figure 5 Cluster heads distribution of a UCPO round图5 UCPO协议某轮簇头分布

三种协议存活节点数对比如图6所示。由图6可知，LEACH-MC优于LEACH协议，UCPO协议优于前两者。一是因为簇头数大部分时间保持为最佳簇头数，使整个网络的能耗大部分阶段处在较低水平；二是因为簇头靠近簇“中心”位置，对成簇有利，簇内数据传输的能量消耗与簇头位于其他位置相比，能耗要小很多；三是因为簇头与基站的通信改用了多跳通信，减小了簇头的能量消耗。

Figure 6 Survival node number of the three protocols图6 三种协议的存活节点数

LEACH、LEACH-MC和UCPO协议死亡相同数目节点的运行轮数对比如图7所示。由图7可知，三个协议的第一个死亡节点分别发生在395轮、595轮和855轮，死亡一半节点分别发生在490轮、789轮和1 023轮，网络节点完全死亡分别发生在701轮、1 012轮和1 103轮。UCPO协议与LEACH协议相比，在各个阶段分别提升了460轮、533轮和402轮，与LEACH-MC比较各个阶段分别提升了260轮、234轮和91轮。可以看出，UCPO协议的网络生存时间，比LEACH协议和LEACH-MC协议的网络生存时间，都有较明显的提高。

Figure 7 Comparison in the amount of operation rounds with the same number of dead nodes图7 死亡相同数目节点的运行轮数对比

4 结束语

本文提出了一种基于非均匀分簇和路径优化的无线传感器网络路由协议，其核心思想是根据最佳簇头数，将整个网络划分成与之个数相等的虚拟子区域，并适当减小靠近基站的子区域面积，增加较远子区域面积。在子区域中，每个区域选择剩余能量高于该区域剩余能量平均值且靠近区域“中心”位置的节点担任簇头，簇头与基站的多跳路径依据改进的Dijkstra算法，选择总能耗最小的路径传输数据。仿真实验表明，UCPO协议优化了整个网络的能量消耗，特别是减少了簇内的能耗，与

LEACH协议及LEACH-MC协议相比，有效延长了网络的存活时间。下一步的工作是对非均匀分簇进行动态研究，路径选择考虑采用更加节能的方法。

［1］ Kumar N，Kaur J.Improved LEACH protocol for wireless sensor networks［C］∥Proc of the 7th International Conference on Wireless Communications，Networking and Mobile Computing（WiCOM），2011：1.

［2］ Li Bin，Wang Wen-jie，Yin Qin-ye，et al.An energy-efficient geographic routing based on cooperative transmission in wireless sensor networks［J］.Science China Information Sciences，2013，56（7）：1-10.

［3］ Vural S，Ekici E.On multihop distances in wireless sensor networks with random node locations［J］.IEEE Transactions on Mobile Computing，2010，4（9）：540-552.

［4］ Lin Zhang-xiao，Wei Liang，Yu Hai-bin，et al.Survey of transmission scheduling methods in wireless sensor networks ［J］.Journal on Communications，2012，33（5）：143-157.

［5］ Li Cheng-fa，Chen Gui-hai，Ye Mao，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］. Chinese Journal of Computers，2007，30（1）：27-36.（in Chi-nese）

［6］ Heinzelman W B，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks［C］∥Proc of the 33rd Annual Hawaii International Conference on System Sciences，2000：1.

［7］ Zhang Deng-yong，Xiong Hao-xiang，Li Feng，et al.The improvement of wireless sensor networks LEACH protocol based on the energy efficiency［J］.Journal of Changsha University of Science and Technology，2007，9（4）：79-82.（in Chinese）

［8］ Bai Feng-e，Wang Li-li，Ma Yan-yan，et al.Algorithm analysis of routing protocols LEACH for wireless sensor networks［J］.Journal of Taiyuan University of Technology，2009，40（4）：15-19.（in Chinese）

［9］ Fan Yi-ming，Chen Qing-zhang，Yu Jian-jun.New routing protocol for wireless sensor networks based on the minimum spanning tree of the cluster head［J］.Chinese Journal of Sensors and Actuators，2008，12（24）：47-50.（in Chinese）

［10］ Zhang De-gan，Li Guang，Zheng Ke，et al.An energy-balanced routing method based on forward-aware factor for wireless sensor networks［J］.IEEE Transactions on Industrial Informatics，2014，1（10）：766-773.

［11］ Lindsey S，Raghavendra C S.PEGASIS：Power-efficient gathering in sensor information systems［C］∥Proc of IEEE Aerospace Conference Proceedings，2002：1125-1130.

［12］ Luo Bing，Huang Yu-qing.An improved multistage clustering algorithm of LEACH protocol［J］.Computer Engineering，2013，39（6）：99-102.（in Chinese）

［13］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

附中文参考文献：

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

［7］ 章登勇，熊昊翔，李峰，等.基于节能的无线传感器网络LEACH协议改进［J］.长沙理工大学学报，2007，9（4）：79-82.

［8］ 白凤 娥，王 莉莉，马 艳 艳，等.无线 传 感 器 网络 路 由 协 议LEACH的算法分析［J］.太原理工大学学报，2009，40（4）：15-19.

［9］ 范一鸣，陈庆章，余建军.一种基于簇首生成树的无线传感器网络分层路由协议［J］.传感技术学报，2008，12（24）：47-50.

［12］ 罗冰，黄玉清.一种LEACH协议的多级分簇改进算法［J］.计算机工程，2013，39（6）：99-102.

刘国繁（1959），男，湖南华容人，教授，研究方向为计算机应用技术。E-mail：Liugf59@foxmail.com

LIU Guo-fan，born in 1959，professor，his research interest includes computer application technology.

许多（1988 ），男，湖南衡阳人，硕士生，研究方向为无线传感网络。E-mail：406875627@qq.com

XU Duo，born in 1988，MS candidate，his research interest includes wireless sensor network.

A routing protocol based on uneven clustering and path optimization in wireless sensor networks

LIU Guo-fan1，XU Duo2
（1.School of Electrical Information，Hunan Institute of Engineering，Xiangtan 411104；
2.College of Information Engineering，Xiangtan University，Xiangtan 411105，China）

Due to the limited energy of sensor nodes in wireless sensor networks，how to use energy efficiently has become a hot topic.The random selection of the LEACH's cluster heads leads to unreasonable cluster composition，accelerates the death of cluster heads，and the communication between cluster heads and the base station causes huge energy consumption.To solve the problems listed above，in this paper we put forward a routing protocol with higher energy efficiency，in which the area is divided based on the number of the best cluster heads.The cluster heads are selected with comprehensive consideration of the energy consumption within cluster heads and the rest energy of the nodes，and the energy is transmitted by multi-hops.Simulation results show that the improved protocol can reduce the energy consumption of the whole network dramatically and effectively prolong the network's lifetime.

LEACH；uneven clustering；path optimization；optimal number of cluster head；Dijkstra algorithm

TP301

A

10.3969/j.issn.1007-130X.2015.08.012

1007-130X（2015）08-1492-06

2014-08-07；

2014-10-27

湖南省科技计划资助项目（2012SK3173）

通信地址：411104湖南省湘潭市福星东路88号湖南工程学院电气信息学院

Address：School of Electrical Information，Hunan Institute of Engineering，88 Fuxing Rd East，Xiangtan 411104，Hunan，P.R.China