WSN 中基于簇首重构的层次路由协议设计

龙昭华，王 波，蒋贵全

（重庆邮电大学 计算机科学与技术学院，重庆400065）

0 引 言

无线传感器网络［1］是由布置在监控区域的大量无线传感器网络节点自组织而成，用来及时、有效、快速的为人们采集相关信息。无线传感器网络发展迅速，应用领域广泛，可以在多个应用场景下提供广泛的服务。资料显示未来无线传感器网络将在工业自动化，物流，海洋和空间探索等领域有着良好的应用前景。

无线传感器网络路由协议是现阶段人们研究的关键点［2］之一。路由协议设计的一个主要目标是通过高质量的能量管理策略来提升网络的生命周期［3］。为了均衡网络的能耗和延长网络的生存期，层次路由协议提出了网络分簇的概念，整个网络按照合理的规则被划分为若干个簇，每个簇由一个簇首节点和若干个非簇首节点组成。非簇首节点只负责数据采集，并把数据发给所属簇首节点，簇首负责把数据发送给基站。这种分簇结构使得层次路由协议被公认为是最有希望减少能耗，缓解 “能量空洞”［4］，延长网络生存期的方法。

鉴于层次路由的特点，本文的设计目的是在深入分析现有的典型层次路由协议的基础上，改进并提出一种能够有效解决网络能耗问题的方法。

1 相关工作及存在的问题

为了满足不同的应用需求，研究者已经提出了大量有关层次路由协议的算法。以下是对现阶段几种典型的层次路由协议进行的分析。

文献 ［5］是对低功耗自适应集群分层型LEACH 协议的描述。在LEACH 协议中，节点按照轮的方式对簇进行周期性的划分，每一次组簇过程称为一轮，一轮又分为两个过程，即簇的组建和数据的稳定传输。每个节点根据下式竞选成为簇首

式中：k——簇首节点站网络中的全部节点的百分比，r——已经完成的回合数 （即轮数），rmod（1／k）为每轮被选出的簇首节点的数目，G——还没有被选举为簇首的节点集合。

当节点竞选成为簇首以后，立即广播其成为簇首的消息至全网，非簇首节点按照接收到的信号强度选择最近的簇首加入，并会获得一个特有的收发时序。当发送数据时，簇首节点会按照之前分配好的时序依次接收簇内各节点数据，经过簇首处理后转发给基站。LEACH 协议的主要缺点是需要重复进行簇的组建，对网络的能量消耗比较大。

文献 ［6］是能量有效的分簇路由协议，即EECS 协议。类似于LEACH 的成簇结构，不同点在于EECS 协议中的簇首节点是在随机产生的候选簇首节点中以固定的通信半径依据本身的剩余能量竞选产生的，而普通节点将会依据节约自身的能耗和平衡簇首的负载等因素来确定非簇首节点选择哪个簇首去加入。EECS协议的主要缺点也是需要重复进行簇的组建，对网络的能量消耗比较大。

文献 ［7］给出了PEGASIS协议，将网络的所有节点构成一条 “链”，全网只选择一个簇首节点，称为leader。链中的每个节点利用信号的强度来调整发射功率，保证只有最近的邻居节点才能够收到信号。然后通过该邻居节点把采集到的数据沿着链逐跳传递到leader节点，再由leader转发给基站。当每个节点都将数据发送完毕，则进行下一轮的leader选举。PEGASIS协议的缺点在于可能存在leader节点与基站距离较远，需要多跳才能到达基站的情况，而且协议需要动态调整拓扑结构，拓扑的调整会带来更大的能量开销。

文献 ［8］是由Jae－hwan Noh等人给出的一个类似于LEACH 的协议MRPS，该协议的执行同样是周期性的，每一轮也包括分簇和数据的稳定传输两个阶段，不同的是MRPS协议引入了一个主簇首节点，负责收集所有簇首的数据，然后由主簇首将数据发送给基站。该协议的缺点之一同样是网络能耗问题，且网络延迟较大。

针对以上协议目前存在的问题，本文在LEACH、EECS协议的基础上改进了一种基于簇首重构的无线传感器网络层次路由协议—HRP－CHR 协议。该协议具有多跳，分层，簇域重构，能耗均衡等特点，能够使整个网络的性能得到显著的提高。

2 通信模型

HRP－CHR协议使用了无线传感器网络专用的低功耗模型，主要由自由空间信道模型和多径衰落信道模型构成。当节点间的通信距离R 小于节点的最大发射距离时采用自由空间信道模型，当节点间的通信距离大于节点的最大发射距离R 时采用多径衰落信道模型。R 是一个门限距离，即接收电路和发送电路之间距离的临界值，这个临界值R的定义如下

式中：L——传输损耗，hr、ht——接收端、发送端的天线高度，λ——无线电波的波长。

假设ETx代表节点发送数据时消耗的能量，ERx代表节点接收数据时消耗的能量。节点发送k比特数据到距离为d的目的节点所消耗的能量表示为［9］

节点接收发送过来的k比特数据所消耗的能量为

式中：Eelec——电路固定能耗值 （j／bit）；εfs——自由传输系数 （j／bit／m2）；εmp——多径衰落系数 （j／bit／m4）。

通过上述的参数和公式，我们可以看出同等条件下，多径衰落传输模型消耗的能量要远大于自由空间能量传输模型。因此，在HRP－CHR 协议路由算法的设计过程中，主要采用自由空间传输模型，目的是尽可能减小整个传输过程中能量的消耗。

3 HRP－CHR路由协议的设计

3.1 设计思路

由于靠近基站较近的传感器节点一方面要传输本簇内的数据，另一方面要转发大量来自其它簇的数据而容易过早地死亡，继而在其所监控的范围内造成能量空洞，所以在多跳的网络中应当使离基站较近的区域形成较小规模的簇，离基站较远的区域形成更大规模的簇，进而达到均衡网络能耗的目的。HRP－CHR协议基于以下的主要思想：

（1）网络初始化时建立一个以数据接入点为中心的圆形的网络 （图1），然后由基站依次向外对网络划分层次，每层的宽度依次递增，传感器节点均匀地分布在网络环境中，节点根据自身的坐标、剩余能量及所属的层次确定出该层次的簇首，并根据自身的通信半径与相应的节点建立连接并组建成簇。

图1 网络拓扑结构

（2）进行簇首的选择时，节点通过接收基站广播的簇首选择消息，并结合自身坐标和剩余能量采用集中式的选举策略进行选择。保证通过基站选举出的簇首能够均匀的分布于整个网络中且数量尽量的接近于最佳簇首数目，目的是尽可能的避免网络能量空洞的出现。

（3）在组簇的时候，非簇首节点可以合理地选择合适的簇首去加入，并组建成簇。

（4）节点在簇内与簇间的路由搭建［10］。簇内的节点采取单跳的形式将数据传送到相应的簇首节点；簇间采取多跳的形式将汇集到的数据进行简单处理之后传送到基站，从而完成整个网络路由搭建的过程。

3.2 数据结构和报文设计

节点的数据结构定义如下所示：

协议中使用的报文格式见表1，协议中的报文共有11种消息类型分别见表2。

表1 协议的报文结构

表2 协议中的消息类型

3.3 组簇机制研究

3.3.1 层次宽度大小与簇域半径的关系

HRP－CHR协议是一个多跳的非均匀层次结构的网络［11，12］，为了达到在能耗均衡的前提下网络的生命周期最长的目的，需要使每一层在处理同等数据量Kbit的情况下能耗最少，也即等同于在此条件下各层内簇域的能耗Ei最少。而簇域半径ri与层间距xi的大小关系直接决定着各簇域的能量消耗情况，所以以下的证明给出了最佳簇域半径与层宽关系的计算方法。

设第i（1＜＝i＜＝n）层圆环的宽度为xi，它的簇域半径是ri。为了保证一个簇域可以完全覆盖所在层次圆环的宽度，簇域的半径ri首先必须要满足ri＞＝xi／2。其次设簇首位于簇域的中心，S是节点j距簇首的距离，则距离期望可表示为

节点j传输单位数据造成的网络总能耗Ej为

所以该簇中n个普通节点的传输总能耗E为

由式 （10）可知：r越大，一个簇的传输总能耗越大，也即层间能耗就越大，所以在满足数据采集任务的前提下，层间能耗取得最小值的临界点为簇半径取最小值，而由于ri＞＝xi／2，所以ri取最小值ri＝xi／2。显然，由于内层节点需要转发外层数据而消耗部分额外能量，在此不难推出，当层宽相对过大时，外层簇域面积由于过大会使簇首节点过早死亡；当层宽相对过小时，又会增加网络多跳时延。因此，在层间能耗达到最低值的前提下，如何寻求层宽的最佳值［13］使得网络能耗达到均衡是需要解决的问题。

设检测区域为以a为半径的圆形区域，且节点的铺设密度为λ，其中成员节点的密度为λ1，簇首节点的密度为λ2。设每个消息大小为单位K，网络分为n层，第n圆环的宽度为xn，第n层中的成员节点到簇首的距离期望值为kn。则有第n层圆环的节点平均能耗为

其中，Ech是第i层所有簇首的能耗，Enormal是第i层成员节点的能耗，ER是接受信息的能耗，ET是发射信息能耗。

由于HRP－CHR协议中高层次的数据要经过低层次转发到基站。所以第n－1层除了传输本层节点产生的数据外还要接受和转发第n层的数据

所以有

第i层则负责转发第n层到第i＋1层的数据。所以根据上式可以推出第i层的平均能耗为

为了均衡能耗，平衡网络负载，协议尽量使整个网络的每个节点平均能耗相等，即满足

EΔi为上层簇首发来的数据引起的能耗，如果EΔi为零，那么每层的宽度均为R 便可满足每层平均能耗相等。但是实际上EΔi不可能为零，所以满足能耗均衡的层宽度xi需满足

式中：ζ，τ，ρ——关于εfs，λ，λ1，λ2的一个常量。为了使第一层尽量包含多的节点直接和基站通信，所以取第一层的宽度为R，即x1＝R。这样在式 （21）的前提下解出的每层宽度的最优值大小xi必然能够保证整个网络能耗的相对均衡，从而达到延长网络生命周期的目的。

3.3.2 最佳簇首数的确定

通过以上的分析可以得知，网络结构中每层的层次宽度和簇域大小已基本确定，也即确保了网络具有能耗最小且能耗均衡的特点。因此接下来就需要在此条件下确定簇域内最佳簇首个数的问题。通过分析网络拓扑结构模型可以得出每层簇的个数也即最佳簇首的个数为簇所在层次的总面积与单个簇的面积之比。在图1的基础上，假设L 为网络半径，N 为簇首个数，则当i为第n层时

当i为其它层 （0＜i＜n）时

至此，网络的层次宽度和簇半径的大小，以及最佳簇首数已确定，这样就基本确定了整个网络的最优化配置，下一步就需要进行路由搭建工作。

3.4 多跳路由的搭建

簇间路由的作用是将网络中独立的簇链接起来。然后在此基础上通过综合衡量与下一跳簇首之间的距离及下一跳簇首的剩余能量，从而形成从目标簇首到基站之间的最佳路由。

簇间路由主要由路由建立和路径维护两部分构成。路由建立方法因网络层次不同而有所区别，路径维护是保证路由健壮性不可缺少的组成部分。

（1）簇间路由的建立：当第i（0＜i＜＝n）层的某个簇首A 有数据需要回传给基站时，则开始进行路由的搭建：

步骤1 簇首A 首先广播消息Msg＿to＿Next至i－1层。

步骤2 当第i－1层的簇首节点收到该信息之后，便回传消息Msg＿ElectB 给A。其中Msg＿ElectB 消息包含其簇首节点的层次ID、剩余能量和坐标。

步骤3 A 分别计算与每个回传消息的簇首节点的距离d和其剩余能量E，选取E／d的值最大的簇首节点B 作为下一跳节点。A 节点设A.Next＝B。

步骤4 节点A 发送Msg＿ACK＿B 消息，为了给B节点进行确认，B 节点设B.Last＝A。此时一跳的路径搭建成功。

步骤5 随后B节点继续发送Msg＿to＿Next给i－2层，完成下一跳路由发现。

以此类推，直到A 的消息被转发到基站时，从簇首节点A 到基站的路由搭建宣布完成。在包含有多条到基站的路径中，A 会根据距离d和剩余能量E 选取最佳路径到基站。紧接着基站反方向的沿该条路径发送消息Msg＿OK去通知簇首A 可以开始发送数据Msg＿Data。

簇间路由搭建的过程如图2所示。

图2 簇间路由搭建

（2）路径维护策略：当相同的一条的传输路径在使用一段时间之后，该路径上的一些传感器节点会出现能量消耗过快的现象。在本协议中采用为退出节点寻找E／d次大的值的替补策略重新填补路径，而不需要重新搭建路径。某条路径中的簇首节点B的能耗达到该簇内的平均值E－时，该节点就需要退出路径。其过程如下：

步骤1 首先节点B发送一个消息，Msg＿ExitB，它包含下一跳节点C的层次ID 消息，给自己的上一跳A 节点，而节点B不再成为该路径上的节点，即Node（B）.Type＝1。

步骤2 而节点A 按照上面所述的路由搭建方法，重新发送Msg＿Reto＿Next寻找到下一跳节点D。则D 回传消息Msg＿ReElectB。

步骤3 此时A 发送包含节点C 的层次ID 的消息Msg＿NextNext给D。D 设置D.last＝A，D.Next＝C，从而D 完成了对节点B的补充，使整个路径得到了重新填补，当然数据传输可以继续的进行。

路径维护策略的过程如图3所示。

图3 路径维护策略

综上所诉，HRP－CHR 协议与LEACH、EECS协议相比较，改进的地方有：

（1）摒弃轮询的组簇机制，采用网络初始化时一次分簇的策略，这样能节省更多能量用于真实数据传输。

（2）网络初始化为一个以基站为中心，层次宽度由内向外依次增大的非均匀拓扑结构，经验证能够有效均衡全网节点的能耗，避免能量空洞的出现。

（3）簇的重建不再在全网进行，而是以簇域为单位，采用簇首重构策略进行组建。

4 实验分析

实验以Matlab作为实验平台，分别从网络生存期，网络能耗情况和数据传输总量3个方面对HRP－CHR 协议进行分析。实验环境为在半径为R＝200m 的圆形监测目标区域内，基站随机分布在监测区域的任意位置，实验环境中的所有传感器节点负责采集数据，并按固定的频率回传，具体实验参数设置见表3。

表3 仿真实验中的参数设置

网络系统搭建好后的监测区域如图4所示，其中黑色星状代表传感器节点，正方形状代表基站。

图4 网络节点铺设情况

（1）网络生存时间对比情况：网络生存时间反映了网络中节点的数量随着网络的运行，节点的存活数量的状况。从实验结果 （图5）可得HRP－CHR 协议中最后一个节点的死亡时间要晚于EECS和LEACH 协议中最后一个节点的死亡时间。HRP－CHR 协议的生存时间优于EECS 和LEACH 协议，更适合于大规模网络的环境，更加适合无线传感器网络的发展。

图5 网络生存时间实验

（2）网络总能耗对比情况：网络总能耗反映了网络内节点随着协议的运行总的消耗能量情况。实验可以得出在大部分时间下，HRP－CHR 协议中网络总能量都要大于EECS和LEACH 协议中的网络总能量。因此HRP－CHR的总的能量大于EECS和LEACH，这主要是由于对网络进行了分层均衡了网络的能耗的原因。

网络能耗实验如图6所示。

图6 网络能耗实验

（3）基站接收数据量对比情况：基站收到的数据量的情况不仅能反映出网络中簇的数量，而且还能反映出网络中节点的整体生存情况。实验表明HRP－CHR 协议中基站接收的数据量要大于EECS 和LEACH 协议中的数据量，即HRP－CHR协议发送给基站的数据量最多。这是因为由于HRP－CHR协议采用簇首重构从而摒弃了轮询的方法，使得整个络用于传输数据的时间大大的增加。

数据传输总量实验如图7所示。

图7 数据传输总量实验

由仿真实验结果可知：在大范围的无线传感器网络环境中，HRP－CHR 协议的生存时间要优于LEACH、EECS协议，同一时间段，HRP－CHR 协议的总能耗要小于后两者，而且，HRP－CHR 协议发送给基站的数据量也要多于后两者。说明HRP－CHR协议具有良好的网络性能。

5 结束语

本文分析了目前无线传感器网络层次路由协议的不足，在原有的基础上改进了一种基于簇首重构的路由协议—HRP－CHR协议，并设计了协议中主要用到的报文格式。此外还详细分析了该协议的工作流程，这其中涉及了网络模型的大量计算。最后通过MATLAB 仿真工具验证了该协议与LEACH 和EECS协议在网络生存期，网络能耗和网络数据量3个方面的性能表现，得出HRP－CHR 协议具有更好的有效性和实用性。

［1］Li Jianzhong，Gao Hong.Survey on sensor network research［J］.Journal of Computer Research and Development，2008，45 （1）：1－15.

［2］Roman R，Lopez J.Wireless sensor networks and the Internet：A security analysis［J］.Electronic Networking Applications and Policy，2009，19 （2）：249－259.

［3］Sun Dayang，Liu Yanheng，Yang Dong，et al.Lifetime optimizing scheme of WSN ［J］.Journal of Computer Research and Development，2012，49 （1）：193－201.

［4］Zheng Zhidong，Sun Yugeng，Liu Yang，et al.Energy model in wireless sensor networks［J］.Journal of Tianjin University，2007，40 （9）：1029－1034.

［5］JIANG Yang，CHEN Biyun，WU Lei.LEACH research on energy upon cooperation transmission in wireless sensor networks［J］.Transducer and Microsystem Technologies，2012，31 （3）：50－53 （in Chinese）. ［蒋 阳，陈 碧 云，吴 磊.LEACH 无线传感器网络中协作传输的能耗研究 ［J］.传感器与微系统，2012，31 （3）：50－53.］

［6］Ye M，Li C F，Chen G，et al.EECS：An energy efficient clustering scheme in wireless sensor networks［J］.Journal of Frontiers of Computer Science and Technology，2007，1 （2）：170－179.

［7］LI Jianqi，CAO Binfang，WANG Li，et al.Improveld routing protocol in wireless sensor network based on LEACH and PEGASIS ［J］.Journal of Transduction Technology，2012，25（2）：263－267 （in Chinese）. ［李 建 奇，曹 斌 芳，王立，等.一种结合LEACH 和PEGASIS协议的WSN 的路由协议研究［J］.传感技术学报，2012，25 （2）：263－267.］

［8］Noh Jae hwan，Byeong jik，Ha Nam koo，et al.Routing protocols based on super cluster header in wireless sensor network P ［G］.Lecture Notes in Computer Science 3420：NetworkingICN，2005：731－739.

［9］TU Pu，ZHAO Quanjun.Irregular communication model in WSN based on continuous percolation flow ［J］.Computer Engineering，2012，38 （12）：66－68 （in Chinese）.［涂扑，赵全军.基于连续渗流的WSN 非规则通信模型 ［J］.计算机工程，2012，38 （12）：66－68.］

［10］Liu Xingcheng，Yuan Dongsheng，Liang Pingyuan.Performance analysis of cost function based energy－efficient routing protocol in WSN ［J］.Journal on Communications，2011，32（6）：132－140.

［11］CUI Xiaoyan，Yang Sikun，Zhang Xiaodong，et al.A novel neighboring propagation algorithm based on hierarchical routing scheme for power constrained wireless sensor networks ［J］.Chinese Journal of Electronics，2012，21 （CJE－2）：327－331.

［12］Wang J，Cao YT，Xie JY，et al.Energy efficient back off hierarchical clustering algorithms for multi－top wireless sensor networks［J］.Journal of Computer Science and Technology，2011，26 （2）：283－291.

［13］HUANG Jiayi，CHENG Lianglun.Balanced energy clustering algorithm of WSN which cluster region were adjusted adaptively ［J］.Application Research of Computer，2012，29（11）：4276－4279 （in Chinese）. ［黄加异，程良伦.一种聚类区域自适应调整的WSN 能耗均衡分簇算法 ［J］.计算机应用研究，2012，29 （11）：4276－4279.］