基于非均匀分簇的无线传感器网络多跳路由算法

林 仁，夏方礼，王 扉(湖南城市学院 数学与计算科学学院，湖南 益阳 413000)

基于非均匀分簇的无线传感器网络多跳路由算法

林 仁，夏方礼，王 扉
(湖南城市学院 数学与计算科学学院，湖南 益阳 413000)

针对低功耗自适应分簇(LEACH)路由协议中均匀分簇方式和簇头选择的不合理以及远距离数据传输过程中能量消耗过多的问题，提出了一种基于非均匀分簇的多跳路由算法LEACH-MRUC．在分簇过程中，该算法充分考虑了节点的能量及地理位置，同时采用非均匀分簇方式构建规模不同的簇结构；在数据传输过程中，簇头与基站之间采用单跳和多跳相结合的路由方式来进行通信．仿真结果表明，LEACH-MRUC算法既使得网络的能量消耗有效地得到均衡，又使得能量的利用效率得到显著提高，并且显著延长了网络的寿命．

负载均衡；非均匀分簇；无线传感器网络；能量高效

1 概述

无线传感器网络是大量微小传感器节点组成的自组织(Ad-hoc)网络系统，这些微小传感器部署在监测区域内，其目的就是协助感知、采集和处理监测区域内感知对象的有效信息，并最终将其发送给观测者[1]．无线传感器网络很好的将网络世界、客观的物质世界以及人类社会有机的结合在一起，它无需固定网络设施的支持，具有快速展开、抗毁性强等特点，可广泛应用于军事侦察、环境监测、医疗护理以及空间探索等领域[2-3]．由于传感器节点通常被随机部署在无人值守的区域且一般采用电池供电，因此，研究高效、负载均衡的路由协议对无线传感器网络意义重大．

目前，研究者们已提出了各种路由协议．一般从网络的逻辑结构来看，可以分为层次路由协议和平面路由协议两种.所有传感器节点在平面路由协议中地位平等且缺乏中心控制节点．因此，网络的可扩展性以及对资源的优化管理能力较弱，对动态变化网络的反应速度也相对较慢；层次路由协议则通过将网络划分为多个规模较小的簇，由簇头节点来实现局部范围内簇内成员的管理，从而实现节点之间的协同工作．层次路由协议的出现在很大程度上解决了平面路由协议中存在的一些问题，它也是当前路由协议研究的主流[4]．

LEACH[5]协议是无线传感器网络中最经典的层次路由协议之一，本文研究了LEACH协议及相关改进协议，并且针对其数据传输以及簇头选举等一些方面存在的先天性不足，进而提出了一种基于非均匀分簇的多跳路由算法 LEACHMRUC(Mutil-hop Routing Algorithm Based on Uneven Clustering of LEACH)．

2 LEACH协议

2.1 LEACH协议介绍

MIT的Heinzelman等人提出的第一个基于分簇思想的层次路由协议便是 LEACH，其后许多路由协议都是在它基础上发展而来的．LEACH协议的主要思想是通过自适应分簇的方式将整个网络划分为多个不同的簇，并采用轮换的随机性簇头选举机制来达到均衡网络负载、延长网络生命周期的目的．其拓扑结构见图1．

图1 LEACH协议的拓扑结构图

LEACH引人了“轮”(round)的概念，每轮循环由两个阶段组成，即簇的建立阶段和稳定传输阶段，并且其协议的执行过程是周期性的．每个传感器节点在簇的建立阶段选择一个介于0和1之间的随机数．若该随机数小于阈值T(n)，则此节点在这一轮中被选举为簇头．

其中，p表示在网络中簇头所占节点的百分比大小；集合G中的元素表示在最近1/p轮中还未当选过簇头的节点；轮数r表示当前已完成的．

簇头在节点选定后通过广播方式将其成为簇头的消息告知网络，而其他节点是根据接收到信息的信号强弱来决定其所从属的簇，并向相应簇头发送请求加入消息，从而完成簇的建立工作．随后，簇头节点采用TDMA方式为簇内成员分配传播数据的时间片，并告知簇内成员．

稳定传输阶段，簇内成员节点将在所属时间片内采集到的数据发送给簇头，簇头节点将接收到的簇内成员数据进行相应的融合处理，最后将融合后的数据发往基站，之后又开始新一轮循环．

2.2 LEACH协议缺陷

LEACH 协议在无线传感器网络中意义重大，但也有几点缺陷：(1)LEACH协议基于初始能量同构前提，在实际应用中存在着局限；(2)LEACH协议采用随机性的簇头选举及均匀分簇方式，可能使得某些节点过多担任簇头而过早耗尽能量，从而产生网络监测“盲区”；(3)由于所有簇头与基站之间采用单跳路由方式，导致簇头负载过重，远距离通信能耗开销较大；(4)LEACH协议的可扩展性差，不适合大规模的无线传感器网络．

3 LEACH-MRUC协议

在LEACH-MRUC协议的簇头选举过程中，它充分考虑了节点的能量及位置因素，确保剩余能量较高的节点优先当选为簇头，并且在能量消耗大致相同的情况下，距离基站较近的节点成为簇头的可能性更大；此外，由于距离基站较远的簇头能量消耗速度较快，因此，LEACH-MRUC协议采用非均匀分簇策略，通过构建规模不同的簇结构来均衡负载；在数据传输的过程中，采用单跳和多跳相结合的路由方式来实现簇头与基站的数据通信，既节省了簇头节点与基站远距离通信的开销，也使得网络的可扩展性得以加强．

3.1 新的成簇机制

在进行簇头选举时，LEACH-MRUC算法与LEACH具有相似的选举机制．不同的是，基站在网络部署阶段需发送一个广播消息，其功率足够大，根据接收到的信号强度RSSI，需要计算传感器节点与基站的近似距离[7]．考虑到 LEACH协议不适合节点初始能量不同的场合，且簇头选举算法没有考虑节点的实际情况，本文结合节点的能量和距离因子，给出了如下阈值T(n)的计算公式：其中，Ecurrt：节点的剩余能量，Einit：节点的初始能量，n：网络预计要运行的轮数，d：当前节点到基站的距离，节点到基站的最大值、最小值，常数w大于0小于1，随网络规模和场景的不同进行大小设置．

基于公式(2)的改进，当选为簇头往往是剩余能量较高的节点，而如果能量相当，成为簇头的可能性就处决于距离基站远近，从而确保选出的簇头位置合理且具有较多能量，优化所形成簇的结构．

无线传感器网络中，第一顺序无线电模型[6]一般被采用，节点发送k比特数据所消耗的能量：

其中，Eelec：电路消耗的能量，功率放大器的能量损耗系数，d：传输距离，dc：距离阈值．

节点接收数据时的能耗为

在基于多跳方式的路由协议中，距离基站较近的节点需承担数据转发工作，此外，根据多径衰减模型可知，节点与基站进行远距离传输时能量的消耗与距离的4次方成正比，因此，为了均衡不同地理位置的簇头节点的能耗，LEACHMRUC算法中采用非均匀分簇的策略，通过控制各簇头的广播范围来构建不均等的簇结构．

定义节点i的广播半径Ri为

由公式(5)可知，节点的广播半径与节点到基站距离的大小成正比，节点的广播范围始终在R与之间变化，与基站相距越近的节点其广播半径越小，用于管理簇内成员所消耗的能量也就越少，从而使其具有更多的能量用于多跳通信时的数据转发．

3.2 数据传输策略

LEACH-MRUC协议中，簇头与基站进行通信时采用单跳和多跳相结合的传输模式．算法中引入了一个临界值TD_MAX，当簇头与基站的距离大于临界值TD_MAX时，簇头以多跳路由的方式与基站进行通信，否则与基站直接进行通信，最终形成一棵以基站为根节点的路由树．

在稳定传输阶段开始前，各个当选为簇头的节点以相同的功率向全网广播一条包含其自身ID、当前剩余能量以及它与基站距离的消息，当某个簇头节点收到来自其他簇头节点的广播消息后通过计算获得它们之间的距离值．在采用多跳路由进行通信的过程中，假设簇头i的下一跳候选簇头节点的集合为MCH，则MCH应满足

假设簇头i选择簇头j作为其数据转发的下一跳并将数据发往基站，根据能耗计算公式，传输k比特数据所消耗的总能量为

图2 路由树模型

4 仿真结果及分析

本文通过NS2平台对LEACH-MRUC算法仿真，将200个传感器节点随机部署在300 m*300 m的监测区域，基站坐标为(150,350)，节点的初始能量为 3 J，发送和接受数据的能量损耗为 50 nJ/bit，ω为0.8，TD_MAX为140 m，λ为0.5，假设数据在转发过程中无丢失．

本文分别从网络存活节点数、网络能量消耗及每轮簇头所消耗的总能量三方面对 LEACHMRUC、LEACH以及HEED协议进行比较．

4.1 每轮存活节点数目比较

图3 网络存活节点对比

图3为网络存活节点数的对比，从图中可以看出，在210 s及350 s附近，LEACH和HEED协议开始有节点出现死亡，到600 s和760 s的时候网络中的节点已全部死亡，而LEACH-MRUC算法中第一个死亡节点出现的时间为620 s附近，最后一个节点死亡的时间则为970 s左右．

图3中的曲线显示，LEACH-MRUC算法的存活节点数目随时间变化的曲线明显优于LEACH 和HEED，这主要是因为LEACH-MRUC算法中节点的负载均衡度更好，避免了某些节点负载过重而过早死亡的现象．

此外，在无线传感器网络中，第一个节点和最后一个节点死亡的时间跨度可以很好的反映网络稳定工作的情况，跨度越短说明网络的能耗均衡度越好，因而性能也就越稳定．表 1显示LEACH-MRUC既使得网络寿命得到有效的延长，并且由于时间跨度明显小于另外两种协议，使得网络的性能得到显著提高．

表1 节点寿命值对照

4.2 总能量消耗对比

图4为网络的总损耗随时间变化的曲线，图中显示LEACH的总能量消耗速度最快，HEED略优于LEACH，而LEACH-MRUC算法的曲线斜率大都低于LEACH和HEED，因而其总能量消耗速度相对而言更为缓慢，这很大程度上得益于LEACH-MRUC算法在簇头选举过程中考虑了位置因素和节点能量，对所形成簇的结构进行了优化，同时改进了对簇间的路由方式，减少了基站与簇头远距离通信的开销，节约了能量．

图4 网络总能耗比较

4.3 每轮簇头消耗能量对比

在分簇路由协议中，簇头节点所消耗的能量在网络的总能量消耗中所占比重非常大，簇头相对普通节点所承担的任务更多，因而也更容易由于负载过重而导致失效，因此，对比网络中每轮簇头节点所消耗的能量也是评估协议性能优劣的重要手段．图5为实验过程中各随机选取连续16轮所统计的簇头总能耗对比．

从图5可以看出，LEACH-MRUC各轮中簇头节点消耗的总能量低于LEACH、HEED，这与该算法中采用非均匀分簇的策略进行分簇是密不可分的，非均匀的簇结构很好的均衡了不同地理位置的簇头的负载．同时，LEACH-MRUC在通信过程中采用了单跳与多跳相结合的通信机制，减少了与基站直接通信的簇头的数目，节省了簇头远距离通信的能耗代价．相对LEACH和HEED而言，图5中LEACH-MRUC算法所代表的曲线的波动性也较小，这也说明LEACH-MRUC算法在稳定性及负载均衡度方面得到了提升．

图5 各协议每轮簇头总能耗比较

5 结束语

本文对LEACH协议进行了详细的分析，并针对其问题提出了一种基于非均匀分簇的无线传感器多跳路由算法(LEACH-MRUC)．在LEACHMRUC算法中，新的成簇机制确保了选出簇头的合理性，同时非均匀分簇的方式也很好的均衡了网络中簇头节点的负载，此外单跳与多跳相结合的路由方式避免了所有簇头与基站远距离直接通信时不必要的能量消耗．仿真实验表明，该算法在节点存活情况、网络总能耗以及每轮簇头所消耗能量方面均优于LEACH和HEED，既延长了网络的生命周期，又有效提高了能量的利用效率．

[1]黄海宁, 任丰原, 林闯. 无线传感器网络[J]. 软件学报, 2003, 14(7): 1252-1291.

[2]Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[3]Zhonghua Zhao,Wei Huangfu, Linmin Sun.NSSN: A network monitoring and packet sniffing tool for wireless sensor networks[C]//Proceedings of the 8th International Conference on Wireless Communications and Mobile Computing, 2012: 537-542.

[4]Zhang Wenya, Liang Zize, Hou Zengguang,et al. A power efficient routing protocol for wireless sensor network[C]// Proceedings of the IEEE International Conference on Networking Sensing and Control. Washington, DC: IEEE Computer Society, 2007: 20-25.

[5]Heinzelman W, Chandrakasan A, Balakrishnan H. Energyefficient communication protocol for wireless Micro-sensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: IEEE Computer Society, 2000: 3005-3014.

[6]Zhang Jun-guo, LI Wen-bin, CUI Dong-xu,et al. The NS2-based simulation and research on wireless sensor network route protocol[C]//Proceedings of the 5th International Conference on Wireless Communications, Netwarking and Mobile Computing. Piscataway, 2009: 3146-3149.

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

(责任编校：蒋冬初)

A Mutil-hop Routing Algorithm Based on Uneven Clustering for Wireless Sensor Networks

LIN Ren, XIA Fang-li, WANG Fei
(College of Mathematics & Computer Science, Hunan City University, Yiyang, Hunan 413000, China)

Concerning the deficiencies of Low Energy Adaptive Clustering Hierarchy (LEACH) routing protocol, approximately uniform cluster structure, unreasonable cluster-head nodes selection and also more than one cluster-heads consuming excessive energy in the process of long-distance communications, a mutil-hop routing algorithm based on uneven clustering is proposed. In the set-up phase, the remaining energy and the geographical position of nodes are fully considered, and it uses non-uniform clustering way to build cluster structure of different sizes. In the steady-state phase, a routing method with single-hop and multi-hop is also introduced to the communicate between cluster-heads and Base Station (BS). Simulation results show that the algorithm effectively balances the energy consumption of networks, improves energy efficiency and obvious prolongs the network lifetime.

wireless sensor networks; load balancing; uneven clustering; energy efficient

O646

A

10.3969/j.issn.1672-7304.2017.01.11

1672–7304(2017)01–0049–05

2016-11-10

中央高校基本科研业务费专题项目(SWJTU12ZT12)；国家教育部人文社会科学研究规划基金项目(13YJA630144)；益阳市科技计划项目(益科字[2016]51号)

林仁(1979-)，男，湖南邵阳人，讲师，博士，主要从事项目管理与调度优化、智能优化算法研究．E-mail: 232898945@qq.com