基于多级异构网络的无线传感器网络高效分簇路由算法

李新路 张贯虹

（合肥学院，安徽 合肥 230601）

基于多级异构网络的无线传感器网络高效分簇路由算法

李新路 张贯虹

（合肥学院，安徽 合肥 230601）

在较大规模的无线传感器网络周期性数据采集应用中，经常会出现异构网络，LEACH等协议没有考虑节点的异质性。提出一种基于多级异构网络的高效路由分簇协议，考虑了节点的异质性，为不同类型节点设置不同簇头选举概率及阈值函数，优化簇头选举策略，较高初始能量和剩余能量的节点比低能量节点拥有更多的机会成为簇头节点。实验结果表明，能够高效地利用传感器网络采集数据，网络负载总体均衡，并延长网络生存周期。

无线传感器网络；异构网络；能量高效

无线传感器网络（Wireless Sensor Networks，WSNs）由许多小型的，资源有限的传感器节点以及基站组成的自组织、分布式网络［1］。随着传感器系统，数据处理及无线通信的发展，无线传感器网络技术被广泛的应用于各类应用，如环境监测、军事、化工检测、医疗服务等行业［2］。由于传感器节点的初始能量、带宽、计算能力的限制，广泛应用于有线网络或Ad Hoc网络中的协议并不适用与WSNs。因而，设计出能量高效的路由协议，从而延长网络生命周期，成为WSNs研究的一个热点问题［1］［3］。

1 相关工作

在WSNs路由协议的设计中，分簇路由协议是较为经典、高效的路由协议，它将网络中的节点划分成簇头节点和成员节点两类，首先使用特定的策略选举簇头，再根据距离等权函数形成簇，簇头负责管理簇内成员节点，执行数据聚合函数，并传输数据到基站。LEACH（Low-Energy Adaptive Clustering Hierarchy）［4］是WSNs中最早提出的分簇路由协议，它是分簇路由协议的基础。其基本思想是，通过等概率随机周期性的选择簇头，再利用节点与簇头之间的距离形成簇，将整个网络的能耗均匀地分配到每一节点，从而达到降低能耗总量，延长网络生命周期的目的。但是LEACH没有考虑到节点的剩余能量问题，加速热点问题（hot spot problem）的形成。文献［5］提出一种DCHS路由协议，DCHS改进了簇头选举过程中的阈值函数，考虑了节点的剩余能量因素，使得节点能耗更加均匀，避免节点过早“死亡”。

HEED［6］是一种混合式能量高效的分布式分簇协议，它根据节点的剩余能量来选择候选簇头，并使用节点的度或邻接节点距离作为内部通信代价，以此来竞争产生最终簇头。实验证明，在一定的节点密度和簇内簇间通信半径下，HEED可以确定一个连通的分簇网络，延长网络生命周期，并使得网络更具有扩展性。但是，HEED需要有限次迭代来选择簇头，其簇头选举开销比LEACH大了许多，在采用单跳模式下，其性能不如LEACH。

EECS［7］适用于周期性的数据收集应用，它在簇头选举阶段选取部分节点参加竞争，采用无迭代过程的局部通信方式，选取剩余能量较多的节点担任簇头，进一步，在簇的形成阶段使用了一种簇头负载均衡的方法。EECS协议控制消息开销小，形成的簇在空间上分布近似均匀，网络能量利用率高。

这些基于LEACH的路由协议大都假定网络节点是同质的，即节点具有相同的初始能量和计算能力，然而在一些应用中，如在现有网络中增加部分新节点，网络中会存在大量异质节点。Mhatre等人在文献［8］［9］中同时考量能耗成本及硬件成本作为整个网络成本，较早地分析比较了WSNs中同质网络和异构网络的路由协议。UCS协议［10］针对异构网络，提出了非均匀分簇的路由策略，UCS假定所有高初始能量的节点位置已知，并指定其为簇头节点，簇间通信采用多跳方式。为均衡能量负载，UCS利用文献［8］提出的能耗模型，使网络中的分簇大小不均匀分布，即距离基站较近的簇成员较少，从而达到整个网络中簇头能耗均匀的目的。SEP［11］协议考虑网络中存在两种初始能量不同的节点，通过在簇头选举概率和阈值函数中引入初始能量，使得具有较高能量的节点具有较大概率成为簇头，延长了传感器网络的稳定周期①稳定周期指从网络开始运行直到第一个传感器节点失效的时间间隔。在一些应用中，当一个传感器节点失效后，网络会变的很不稳定。。

本文提出一种基于三级异构网络的分簇路由协议。LEACH及类LEACH分簇协议基于同构网络，在处理异构网络时没有考虑节点的异质性，从而使得节点的能耗分布不均匀。而UCS协议需要提前获取异质节点的位置，并且要求它们位置分布均匀，因而具有很大的局限性，不能满足无线传感器网络的拓扑变化。本文的协议区别于这两类协议，在考虑网络扩展性和稳定性的基础上，使得节点能量负载均衡，从而延长网络的生命周期。

2 问题描述和能量模型

2.1 问题描述

本文提出的协议基于周期性数据收集应用，如环境监测等，我们假定：

（1）节点随机均匀地分布在监测区域，位置信息未知，基站位置固定；

（2）节点能量有限，网络中存在异质节点，基站能量不受限制；

（3）节点具有相似的处理及通信能力，可以担任簇头或普通节点；

（4）节点通信功率可控，可以根据距离来调节发射功率的大小，并可以根据接收信号的强度来计算节点之间的距离。

本文研究的无线传感器网络模型中有n个传感器节点，一个基站。传感器节点初始能量不均匀。同时，我们假定在网络中有三种不同类型的节点：普通节点（normal nodes），中级节点（moderate nodes），高级节点（advance nodes）。

2.2 能量模型

本文采取与文献［12］相同的能量模型。节点传输l比特的消息到距离为d的位置，消耗的能量由发射电路损耗和功率放大损耗两部分组成，即

同时，为了接收比特的消息，需消耗能量为：

其中，Eelec表示发射电路损耗的能量。d0为阈值，当传输距离d大于等于d0时，功率放大损耗采用多路径衰减模型，损耗系数取4；反之，采用自由空间模型，损耗系数取2。此外，在数据融合时仍需消耗能量，用EDA表示融合单位比特数据消耗的能量。

3 三级异构网络的分簇协议

3.1 LEACH分簇策略

LEACH协议通过轮（Round）来周期性的选择簇头。每轮中，每个节点都以概率Popt成为节点，建立簇时，每个节点产生0～1之间的随机数，并于阈值函数T（s）比较，若小于T（s），则成为簇头。

簇头选择结束后，每个簇头通知其他非簇头节点当选消息，而非簇头节点会依据与所有簇头通信信号的强弱判断加入哪个簇。在稳定阶段，簇头收集来自簇内的信息，进行数据融合，传输至WSNs基站。

在上述阈值函数中，Popt指节点优化簇头概率，在n个节点中，簇头优化数量为kopt，根据文献［12］，

由公式（4）（5）可知，Popt及kopt独立于网络的大小，并且只依赖于传感器节点的数量。

LEACH协议基于同构网络，适用于节点同质，且均匀分布的无线传感器网络。然而在应用中，会出现大量异质节点，如网络运行一段时间后，节点能量必定会分布不均匀，或者网络加入了新节点。在我们讨论的模型中，假定有三类异质节点。

3.2 三级异构网络的分簇协议

文献［10］中，UCS假定高级节点作为簇头，因而需要高级节点位置已知，并且分布均匀。在本文讨论的协议中，所有节点都有概率成为簇头，即不需要提前获得节点位置信息。直观上，我们期望高级节点和中级节点成为簇头的概率大于普通节点，从而使得整个网络负载均衡，延长网络生命周期，为此，协议为不同类型节点设定不同的概率函数及阈值函数。

如前所述，网络中存在三种类型节点，其初始能量及比例如下表：

表1 节点初始能量及数量

根据表1，三级异构网络的初始总能量可以描述成：

如前所述，优化簇头概率Popt只依赖于传感器节点的数量，在三级异构网络中，相比较于LEACH协议中的同构网络，根据公式（6），可以理解成增加了α·m＋β·a个虚拟普通节点。为了使得网络节点能量负载均衡，协议必须保证高级节点和中级节点当选簇头的概率大于普通节点，即满足如下条件：

（4）每轮当选的簇头平均数量为n·Popt。

为此，给优化簇头概率Popt增加权值，普通节点，中级节点和高级节点的优化簇头概率计算公式分别如下：

4 仿真及性能评估

为验证协议的有效性，我们分别考虑如下性能参数：

网络生命周期：不失一般性，本文分别从第一个节点死亡时间（First Node Dies，FND），半数节点存活时间（Half of Nodes Alive，HNA）两方面来验证网络生命周期。

数据吞吐量：本文比较异构网络的数据吞吐量，分别衡量簇内节点至簇头及簇头至基站的数据吞吐量。

每轮簇头平均数：为验证协议的簇头优化概率及簇头优化数量，本文分析比较每轮当选簇头的平均数量。

本文采用与LEACH协议相似的实验参数，各项参数设置如表2所示。

表2 实验参数

根据表2中的参数，本文使用Matlab作为仿真工具，模拟实现了LEACH协议及本文所提出的新协议，并进行性能比较分析。

4.1 网络生命周期

图1为网络中采用LEACH协议及本文协议网络存活节点数曲线图，可以看到，采用本文协议的网络稳定周期明显长于LEACH协议，此外网络的活跃时间也长于LEACH协议。为了直观的比较网络生命周期，图2列出了LEACH协议及本文所提出协议的生命周期对比图，比较了第一个节点死亡时间（FND）及半数节点存活时间（HNA），在实际的应用中，这两中生命周期度量比最后一个节点死亡时间更加实际。由图2可知，使用本文的协议，FND和HNA均提高了约10%的性能。这表明本文的协议考虑到异构节点的特性，并能够更好的处理多级异构网络，延长了网络的生命周期。

图1 生命周期对比图

图2 节点存活数曲线图

4.2 网络数据吞吐量

观察图3可知，采用本文协议的网络数据吞吐量在生命周期内明显高于LEACH协议。WSNs数据吞吐量包括传感器节点至簇头数据吞吐量，簇头至基站数据吞吐量。本文提出的协议基于周期性数据收集应用，如环境监测等，高数据吞吐量可以更加频繁地采集数据，高效地利用传感器网络。

图3 簇头节点数分布

图4 网络数据吞吐量

4.3 每轮簇头平均数

图4分析了每一轮选举产生的簇头数量分布，由图可知，约1000轮之前，LEACH协议及本文提出的协议每轮选举的簇头数均分布在10左右，根据文献［12］及公式（4），簇头优化数量kopt只与网络规模相关，而根据本文所采用的网络参数，计算出kopt＝n·Popt=10，在1000轮之后，随着部分节点能量逐渐耗尽，网络规模逐步减少，每轮簇头数量也随之降低。由此可知，根据本文提出的簇头选举策略产生的簇头数量与理论上所需的簇头优化数量基本一致，从而达到网络负载总体均衡的目的。

5 总结

在较大规模的WSNs周期性数据采集应用中，经常会出现异构网络，或初始节点异质，或运行一段时间后产生异质节点。本文提出一种多级异构网络的高效路由分簇协议。该协议考虑了节点的异质性，为不同类型节点设置不同簇头选举概率及阈值函数，优化簇头选举策略。实验结果表明，本文提出的协议，能够高效地利用传感器网络采集数据，网络负载总体均衡，并延长网络生存周期。

［1］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，（7）：1588-1600.

［2］Akkaya K，Younis M.A survey on routing protocols for wireless sensor networks［J］.Ad hoc networks，2005，（3）：325-349.

［3］Liu X.A survey on clustering routing protocols in wireless sensor networks［J］.Sensors，2012，（8）：11113-11153.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］.System sciences，2000.Proceedings of the 33rd annual Hawaii international conference on.IEEE，2000：10.

［5］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection［C］.Mobile and Wireless Communications Network，2002.4th International Workshop on.IEEE，2002：368-372.

［6］Younis O，Fahmy S.HEED：a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks［J］.Mobile Computing，IEEE Transactions on，2004，（4）：366-379.

［7］陈贵海，李成法，叶懋，等.EECS：一种无线传感器网络中节能的聚类方案［J］.计算机科学与探索，2007，（2）.

［8］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks：communication，clustering and aggregation［J］.Ad Hoc Networks，2004，（1）：45-63.

［9］Mhatre V，Rosenberg C.Homogeneous vs heterogeneous clustered sensor networks：a comparative study［C］.Communications，2004 IEEE International Conference on.IEEE，2004：3646-3651.

［10］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］.Parallel and Distributed Processing Symposium，2005.Proceedings.19th IEEE International.IEEE，2005：8.

［11］Smaragdakis G，Matta I，Bestavros A.SEP：A stable election protocol for clustered heterogeneous wireless sensor networks［R］.Boston University Computer Science Department，2004.

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

TP393

A

1672-2868（2015）03-0020-06

2015-03-15

合肥学院科研发展基金一般项目（项目编号：12KY07ZR）

李新路（1980-），男，安徽无为人。合肥学院计算机科学与技术系，讲师。研究方向：无线传感器网络。

陈 侃