基于非均匀分簇的野外观测仪器网络路由协议研究

胡 军，王 磊，火久元，刘 梦，巨 涛

（1.甘肃亿网科技网络技术有限公司，甘肃 兰州 730000；2.兰州交通大学 电子与信息工程学院，甘肃 兰州 730070）

0 引言

野外观测通过在野外建立观测站对地球系统的关键要素进行长期的监测与分析，是大气科学、生态学、环境科学等研究的主要数据来源。我国寒旱区面积广阔，生态环境脆弱复杂，自然资源丰富。寒旱区野外观测经过50 多年的发展，已经形成覆盖我国寒旱区主要生态、环境区的野外观测网络体系。该观测系统通过观测、实验以及示范，为寒旱区的科学研究提供了重要依据，是我国寒旱区科学研究体系中不可缺少的组成部分［1］。

受到环境限制，寒旱区野外观测台站大部分位于高寒、干旱的恶劣环境下，影响了台站的网络建设和信息获取，这些问题严重阻碍了寒旱区科学研究工作的进展。因此，需要对寒旱区观测仪器组网问题进行研究，设计一种高效、稳定的路由协议，实现对寒旱区野外环境长期、有效的观测。经过前期的调查研究，本文发现野外观测仪器组网和无线传感器网络（Wireless Sensor Network，WSN）具有很高的相似性，例如二者都是自组织网络，且都是无线传输介质等［2-3］。因此，本文将根据野外观测仪器组网特点，结合WSN 技术对路由协议进行设计与改进。

为了减少网络的通信能耗，学者们提出多种基于分簇的层次性路由协议［4］。分簇减少了发送的数据包数量和网络信息冗余，可以降低能耗，延长网络的生命周期。基于分簇的路由协议可分为均匀分簇和非均匀分簇两种。均匀分簇算法在网络中构造大小相同的分簇，虽然通过合理的选择簇头可以延长网络生命周期，但无法有效均衡网络的能量消耗。相比于均匀分簇协议，非均匀分簇协议在均衡网络能耗方面具有更好的性能。非均匀分簇算法通常在网络中构造远大近小的分簇结构，使靠近基站的簇头在簇内通信上消耗的能量小于远离基站的簇头，节省的能量可用来转发远离基站的簇头信息，从而解决能耗不均衡的问题［5］。

因此，为了解决寒旱区野外观测仪器网络在多跳路由中能量消耗不均匀的问题，本文基于文献［5］中的非均匀分簇思想，提出一种能量均衡的非均匀分簇路由协议（Energy-balanced Unequal Clustering Routing Protocol，EBUCR）。该协议簇头通过局部竞争产生，可以得到数量稳定的分簇数目。每一轮选举开始时，首先选择候选簇头，然后基于时序选举正式簇头，减少了簇头选举过程中的能量消耗。同时，改进了竞争半径公式和广播时间公式。改进后的公式综合考虑了节点能量、距离基站的距离及周围节点的密度，使簇头分布更加合理，从而得到合理的分簇结构。在簇间通信时，使用混合粒子群算法进行最优路径搜索，以减少和均衡网络能量消耗，使该算法可适用于大规模网络。仿真实验结果表明，该算法能够有效均衡能量消耗，延长网络生命周期。

1 相关研究

低功耗自适应集簇分层型（Low Energy Adaptive Clustering Hierarchy，LEACH）协议［6］是最早提出的层次型路由协议，节点分为簇头节点和成员节点，成员节点将信息发送给簇头，由簇头进行数据融合再发送给基站，通过节点轮流担任簇头来均衡能量消耗。然而，LEACH 协议仍存在许多不足，例如簇头与基站之间直接传输信息会导致远离基站的节点过早死亡；随机选举簇头的机制会导致簇头分布不均、各簇成员数目相差较大等情况，也会将能量较低的节点选举为簇头，导致节点快速死亡。文献［7］在LEACH 协议基础上对阈值公式进行了修改，修改后的阈值公式考虑了节点的剩余能量与到基站的距离，同时结合多跳路由延长网络生命周期。但在该算法中，靠近基站的簇头需要转发远离基站簇头的信息，导致消耗过快而率先死亡，造成“热点”问题。文献［8］利用粒子群算法（Particle Swarm Optimization，PSO）来优化分簇，通过适应度函数综合考虑节点的剩余能量和位置，构建合理的分簇结构。同时，建立基于最小生成树的多跳数据传输路径，缩短节点的通信距离，减少能量消耗并延长网络生命周期。

上述算法都是基于均匀分簇的思想，无法有效解决能耗不均问题，采用单跳通信时，远离基站的节点率先死亡，采用多跳通信时，靠近基站的节点由于需要转发信息而率先死亡。为了解决此问题，Soro 等［5］首次提出非均匀分簇思想，在网络内构造大小不一的簇，靠近基站的簇规模小，远离基站的簇规模大，使靠近基站的簇头在簇内通信上消耗的能量小于远离基站的簇头，节省的能量用来转发远离基站簇头的信息，从而解决能耗不均衡问题。但该协议考虑的是一个异构网络，其中簇头是预先计算好的，并且能量不受限。文献［9］提出一个非均匀分簇结合多跳的路由（Energy-Efficient Uneven Clustering，EEUC）协议，每一轮选举出候选簇头，然后通过非均匀的竞争半径竞选能量较高的节点成为最终簇头，形成大小不一的簇。该协议每轮都会产生大量候选簇头，并且在正式簇头竞争阶段需要广播和接收大量信息，从而产生额外的能量消耗。文献［10］提出一种基于位置的非均匀分簇算法（Location-based Unequal Clustering Algorithm，LUCA），该算法类似于EEUC 算法，根据簇头与基站之间的距离确定簇的大小，远离基站的簇规模较大，同时对网络的最佳簇大小进行数学推导与分析，详细阐述了非均匀分簇的核心思想。文献［11］提出一种能量均衡的分布式非均匀分簇（Distributed Energybalanced Unequal Clustering Routing Protocol，DEBUC）算法，候选簇头的广播时间取决于自身的剩余能量和周围节点剩余能量大小，根据节点不同的竞争半径，使得靠近基站的簇规模小，远离基站的簇规模大。该协议减少了簇头竞争阶段的能量消耗，延长了网络生命周期。文献［12］提出一种基于LEACH 协议改进的簇间多跳路由（Cluster Head Multi-hops Routing Algorithm Improved Based on LEACH Algorithm，CMRAOL）协议。根据节点的能量大小和距离基站的距离选举簇头，能量越大，距离基站的距离越小，则成为簇头的概率越大，使靠近基站的簇规模较小，远离基站的簇规模较大。文献［13］将网络进行非均匀分层，在各层依据节点的剩余能量和到层中间线的距离选举簇头，同时结合多跳路由减少能量消耗。

为了更好地实现能耗均衡，文献［14］提出基于分层思想的非均匀分簇协议。不同于其它非均匀分簇协议，该算法将整个网络分成不同的层，限制两个簇头之间的最小距离，使簇头均匀地分布在同一层中，并且靠近基站的层簇头间距大，远离基站的层簇头间距小，以达到非均匀分簇的效果。当簇头距离基站较远时，向基站传输数据的能量消耗较大，可通过减少簇内节点的数量均衡能量消耗。然而，该协议采用单跳通信，无法适用于大规模网络。此外，有些学者将智能优化算法与WSN 的非均匀分簇路由协议设计结合起来。例如文献［15］基于萤火虫群优化算法（Glowworm Swarm Optimization，GSO），依据簇头密度、簇头距离、簇头能量、簇的紧凑性来选举簇头，形成不均匀的簇。分簇结束后，考虑能量消耗和下一跳节点的剩余能量，在簇间构建转发树，将簇头的信息通过转发树传递到基站。文献［16］是一个基于蚁群算法设计的非均匀分簇协议，结合能量因子、距离因子、密度因子改进簇头选举过程，并且利用改进的蚁群算法选择下一跳节点。文献［17］在簇头选择阶段使用遗传算法（Genetic Algorithm，GA）选择簇头，选择剩余能量较高且靠近基站的节点作为簇头。同时结合多跳路由，降低能耗并延长网络生命周期。文献［18］提出一种基于遗传算法和粒子群算法的路由（GAPSO-based Clustering and Routing，GA-PSO）算法，使用遗传算法优化聚类以获得合理的聚类结构，并使用粒子群优化算法优化路由以降低能耗。但是，该算法没有考虑集群头部选择阶段节点的残余能量，从而导致节点的早期死亡。

这些非均匀分簇算法虽然一定程度上延长了网络生命周期，但协议的簇头选举策略仍有很大的改进空间。与已有的非均匀分簇路由协议相比，本文主要做了以下工作：①基于剩余能量、距离和节点密度改进了竞争半径公式和广播时间公式，可以得到合理的分簇结构；②建立基于混合粒子群算法的簇间多跳路径以减少能量消耗；③通过实验验证了EBUCR 协议的性能。

2 网络模型与无线通信消耗模型

2.1 网络模型

本文考虑观测网络是由随机布置在正方形区域内的节点组成，对网络进行如下假设：①基站位于网络外，能量不受限，且仪器组网节点和基站部署完成后，均不可移动；②仪器组网节点是同构的，随机部署在网络中，能量受限，每个节点都有自己唯一的ID 编号；③仪器组网节点可根据收到信息的信号强弱判断到信息发送者之间的距离，并且可以调节自己的发射功率；④仪器组网节点可以对数据进行融合，以减少传输的数据量。

2.2 无线通信能量消耗模型

本文使用与LEACH 协议相同的无线通信能耗模型，即一阶无线通信模型能量模型，如图1所示。

Fig.1 Wireless communication energy model图1 无线通信能量模型

发送者与接收者之间的距离为d时，发射大小为L比特的数据需要消耗的能量如公式（1）所示。式中，Eelec为运行发射电路和接收电路每比特的能量损耗，εfs和εmp取决于本文使用的发射器放大器模型。do为距离阈值，当d≤do时，采用自由空间模型；当d＞do时，采用多路衰减模型。接收一个L比特的消息，无线电需要消耗的能量为ERX（L，d）=L×Eelec。

3 能量均衡的非均匀分簇路由协议

EBUCR 协议采用“轮”的方式运行，每轮分为两个阶段，分别进行簇的建立和数据传输。在网络初始化阶段，基站需要以一定的功率向全网路广播一条信息，然后网络中每个节点依据接收到信息的信号强弱计算自身到基站的距离。该距离可以用于计算各节点的竞争半径，并以此达到图2 所示的非均匀分簇效果。由图2 可知，距离基站较近的簇规模小于距离基站较远的簇，簇的规模小，用于簇内通信的能量少，节省的能量可用来转发远方簇头传递的信息，达到均衡能耗的效果。每轮开始时，各节点随机生成一个随机数，与自身相应的阈值进行比较，若小于阈值，则成为候选簇头；成为候选簇头的节点需要广播自己成为候选簇头的信息，并生成自身的邻居簇头节点信息表，普通节点则进入休眠；然后，候选簇头依据自身的时间进度广播成为当选簇头的信息；簇头选举完成后，普通节点结束休眠，加入离自己最近的簇；分簇完成后，簇成员节点给簇头节点发送信息；簇头节点接收信息后，将数据进行融合，按照一定的通信路径发送给基站。

Fig.2 Schematic diagram of unequal clustering routing protocol图2 非均匀分簇路由协议原理

簇头的竞争规则定义为：竞争过程中，若候选簇头Si宣布自己当选簇头，则其邻居簇头节点信息表中的其它所有候选簇头均不能成为簇头，并退出竞争。

候选簇头节点Si的邻居簇头节点信息表定义为：neighbori=｛Sj|Sj是候选簇头，且d（Si，Sj）≤Max（Ri，Rj）｝。

3.1 簇的建立

与EEUC 协议类似，EBUCR 协议簇头节点依靠局部竞争产生。在EEUC 协议中，候选簇头的产生是每个节点随机生成一个随机数。当该随机数小于提前设置好的阈值时，则成为候选簇头。但是该阈值是固定的，每个节点的阈值相等，因此可能将能量较低的节点选为候选簇头，并且每轮都产生大量簇头，在竞争过程中会耗费大量能量。

在EBUCR 协议中，利用文献［19］中的正式簇头选举方法来选举候选簇头。在每一轮开始阶段，首先根据存活节点的剩余能量值计算网络中节点的平均能量，然后比较每个节点的剩余能量与平均能量大小，当节点剩余能量大于等于平均能量时，节点加入节点集合G。集合G中的节点随机生成一个0～1 之间的随机数，如果随机数小于节点对应的阈值T（n），则该节点成为候选簇头。T（n）计算公式如公式（3）所示：

式中，p表示候选簇头节点占全部节点的比值，r表示当前所处的轮数。采用该方式选择候选簇头，能够将网络中剩余能量较高的节点选为候选簇头，从而避免能量较低的节点当选候选簇头。同时避免了产生大量候选簇头，可以有效减少正式簇头竞争过程中的能量消耗。

候选簇头产生后，要在一定范围内广播自己成为候选簇头的消息，周围的候选簇头依据收到的消息产生自己的邻居簇头节点信息表，然后按照一定的规则竞争产生正式簇头。如公式（4）所示，原有的竞争半径公式仅考虑了候选簇头与基站的距离大小，当网络运行了一段时间后，网络中节点的能量产生异构，此时若仅根据距离计算竞争半径会导致个别节点能量损耗过快。EBUCR 协议考虑节点的剩余能量，对竞争半径公式作了修改。在候选簇头距离基站相同距离的情况下，节点剩余能量越大，竞争半径越大，节点剩余能量越小，竞争半径越小，更有利于网络全局的能耗均衡。改进后的竞争半径如公式（5）所示。

式中，Emax代表当前的最大剩余能量，Emin代表当前的最小剩余能量，dmax表示节点到基站的最大距离，dmin表示节点到基站的最小距离，Rmax表示最大竞争半径。

EBUCR 协议在簇头局部竞争阶段不同于EEUC 协议的协商机制，而是基于时序选举簇头。每个候选簇头有自己的广播时间ti，在时间ti未到达之前，如果接收到其它邻居节点当选为簇头的消息，则退出竞选并广播退出竞选的消息，如果未收到其它邻居节点当选簇头的消息，等时间ti到达，则广播自己成为簇头的消息。等待时间ti如公式（6）所示：

式中，k为0.9～1 之间的随机数，以避免等待时间发生冲突，Tch表示簇头竞争需要的最大等待时间，Eni_avg为邻居节点的平均剩余能量，Qi表示节点密度（距离当前节点距离Rmax内的节点数量），Qmin为最小节点密度，α、β、γ为能量因子、距离因子和密度因子的加权系数，通过大量实验，取α=0.5，β=0.2，γ=0.3。根据上述公式，广播时间不仅取决于节点剩余能量，而且需要考虑节点到基站的距离和节点密度。剩余能量大、距离基站近、节点密度大的节点等待时间就越少。簇头竞选流程如图3所示。

3.2 数据传输

在分簇完成之后，网络进入数据传输阶段，分为簇内通信和簇间通信。簇内通信时，采用单跳方式进行通信，成员节点将数据直接发送给簇头，由簇头进行数据融合后发送到基站；簇间通信时，采用多跳方式进行通信，基站根据每个簇头节点的位置计算簇头的最佳传输路径。

本文的目标是既要减少多跳消耗的能量，又要使各个簇头消耗的能量均衡，因此引入混合粒子群算法计算簇头的多跳路径。适应度函数如公式（7）所示，其中Econsume为簇头消耗的总能量，D为簇头消耗能量的方差，适应度值越大，代表粒子对应的路径越优。

基站计算得到簇头的最佳路径后，将路径发送给簇头，然后簇头沿着路径将信息发送到基站。

Fig.3 Cluster head selection flow图3 簇头竞选流程

4 协议分析及仿真实验

本文使用MATLAB 编写EBUCR 协议仿真程序，将其与LEACH［6］、EEUC［9］、DEBUC［11］、CMRAOL［12］、GAPSO［18］协议进行对比，以验证EBUCR 协议的性能，仿真实验相关参数设置如表1所示。

Table 1 Parameter setting of simulation experiment表1 仿真实验相关参数设置

4.1 簇头分布分析

在网络拓扑固定的情况下，一个稳定的分簇协议应该生成数量比较一致的簇头来优化网络的能量消耗。在网络运行过程中随机抽取100 轮，在没有任何节点死亡的情况下，统计6 种协议簇头数目分布情况，结果如图4 所示。从图4 可以看出，LEACH、CMRAOL 与GA-PSO 协议的簇头数目波动较大，这是因为LEACH、CMRAOL 与GA-PSO协议均采用随机选举簇头的方法，无法控制簇头数量，往往会造成簇头分布密集的情况，导致耗费大量能量。DEBUC、EEUC 与EBUCR 协议均采用局部竞争的方式选举簇头，产生的簇头数目波动较小。总体来说，EBUCR 协议可以产生稳定的分簇数量，有助于网络稳定，并延长网络寿命。

Fig.4 Distribution of the number of cluster head produced by six protocols图4 6种协议生成的簇头数目分布统计

4.2 网络能量效率分析

4.2.1 网络生命周期分析

网络的生命周期是指网络开始工作到第一个节点死亡的时间。在网络生命周期内，整个网络区域可以得到有效监控，一旦生命周期结束，节点开始死亡。虽然网络内仍有节点在继续工作，但对于整个网络而言，监控存在漏洞，因此无法做到对整个网络的有效监控。尤其是对于一些对监控信息准确性要求极高的应用，生命周期显得格外重要。图5（彩图扫OSID 码可见，下同）显示了EBUCR 协议与CMRAOL、DEBUC、GA-PSO、EEUC 和LEACH 协议的生命周期对比。从图中可以看出，相比于其它几种协议而言，EBUCR 协议明显延长了网络生命周期。EBUCR 协议第一个节点在544 轮死亡，CMRAOL、DEBUC、GA-PSO、EEUC 与LEACH 协 议 第 一 个 节 点 分 别 在476 轮、452 轮、309 轮、228 轮和95 轮死亡，EBUCR 协议第一个节点死亡的时间比其他4 种协议分别延长了14%、20%、76%、139%和473%；EBUCR 协议最后一个节点在641 轮死亡，CMRAOL、DEBUC、GA-PSO、EEUC 与LEACH 协议最后一个节点分别在560 轮、607 轮、546 轮、447 轮和480 轮死亡，EBUCR 协议最后一个节点死亡的时间比其他4 种协议分别延长了14%、6%、17%、43%和34%，数据对比如表2 所示。这是因为EBUCR 协议的簇头选择综合考虑了剩余能量、距离基站距离和周围节点密度，再结合能量和距离优化后的非均匀竞争半径，使得簇头分布更加合理，可以均衡靠近基站的簇头与远离基站簇头的能量消耗，延长网络生命周期。

Fig.5 Network lifetime comparison of the six protocols图5 6种协议网络生命周期比较

在文献［20］中，采用网络的有效性作为评估无线网络生命周期的指标，而不是仅用存活节点数量衡量网络生命周期。因为具有相同数量存活节点的网络节点分布不同，所以在监测覆盖方面具有不同性能。如图6 所示，网络中虽然都只有8 个存活节点，但网络的监测覆盖面积有很大差异。

公式（8）给出了网络有效性的定义，其中TotalArea表示网络总面积，TotalNodes表示节点总个数，AreaCovered表示存活节点覆盖面积，SurvivingNodes表示存活节点个数。网络的生命周期为网络开始运行到网络有效性不低于70%的时间，图7 给出了用有效性表示的网络生命周期对比图。结果表明，与LEACH、CMRAOL、DEBUC、EEUC 和GA-PSO 协议相比，EBUCR 协议可以延长网络生命周期，EBUCR 协议的生命周期相比CMRAOL、DEBUC、GA-PSO、EEUC、LEACH 协议分别延长了13%、11%、18%、47%和160%。

Fig.6 The possible distribution of eight surviving nodes图6 8个存活节点的可能分布

Fig.7 Effectiveness of six protocols图7 6种协议的有效性

4.2.2 网络能量消耗分析

本文通过网络剩余能量、网络总耗能和簇头总耗能3个方面对6 种协议进行能量消耗对比分析。图8 为6 种协议网络剩余总能量随着运行周期变化的对比图。可以清楚地看出，随着运行轮数的增加，EBUCR 协议的网络剩余能量明显大于其它几种协议，且斜率基本保持不变，说明EBUCR 协议可以明显减少能量消耗。图9、图10 为6 种协议网络消耗能量对比图，在网络运行过程中，随机抽取100轮并计算每轮网络消耗的总能量和簇头消耗的能量。其中，图9 为网络总消耗能量对比图，图10 为簇头消耗能量对比图。从网络消耗的总能量来看，EBUCR 协议网络消耗总能量明显低于LEACH 和EEUC 协议，与CMRAOL、DEBUC 及GA-PSO 协议相比，EBUCR 协议消耗的总能量相差不大，但波动较小，协议稳定性更强。从簇头消耗的能量来看，EBUCR 协议簇头每轮消耗的能量均低于其它几种协议，说明相比于其它几种协议，EBUCR 协议能有效减少能量消耗，延长网络寿命。

4.2.3 网络吞吐量分析

Fig.8 Residual energy of six protocols图8 6种协议剩余能量

Fig.9 Energy consumption of total network图9 网络总耗能

Fig.10 Total energy consumption of cluster heads图10 簇头总耗能

图11 为6 种协议簇头接收到数据包数量的对比图。从图11 可以看出，6 种协议接收到数据包的数量均随着时间的增加而增加。算法刚开始运行时，几种协议簇头接收到的数据包数量相差不大。随着算法的运行，其余几种协议的节点开始死亡，其接收到的数据包数量小于EBUCR协议。并且在其他协议簇头停止接收数据时，EBUCR 协议簇头仍能从成员节点接收到监测数据，表明该协议能够延长网络对监控区域的监控时间。

4.3 能量均衡分析

Fig.11 Throughput energy of six protocols图11 6种协议吞吐量

能量均衡分析也是评价路由协议性能的一项重要指标。图12 使用剩余能量方差对6 种协议进行能量均衡方面的对比分析。图中曲线为随着运行时间增加，网络中所有节点剩余能量方差的变化趋势。相比于其他几种协议，EBUCR 协议的方差数值基本保持最小，且波动较小，说明EBUCR 协议能够有效均衡能量消耗，能量均衡性最好。

Fig.12 Variance of residual energy of nodes图12 节点剩余能量方差

5 结语

针对大规模的野外观测仪器组网网络，为了均衡网络能量消耗、延长网络生命周期，本文提出一种能量均衡的非均匀分簇路由协议。该路由协议在簇头竞争阶段基于时序来竞争簇头，并综合考虑节点的剩余能量、到基站的距离、周围节点密度实现非均匀分簇。同时，将混合粒子群算法应用到多跳路径搜索中，选择最优路径完成簇头间的信息传输。实验结果表明，EBUCR 协议相比LEACH、DEBUC、CMRAOL 和EEUC 协议能节省更多能量，具有更强的稳定性，可以延长网络生命周期，并有效均衡能量消耗。然而，本文致力于设计能量高效且均衡的分簇路由协议，并未对整个协议运行时间的收敛性方面进行深入研究，而这在实际应用中是必须解决的问题，希望在未来作进一步研究。