基于通信节点的WSN自主聚类非均匀分簇路由协议

刘一珏, 王 军, 田 鹍

(沈阳化工大学 计算机科学与技术学院，辽宁 沈阳 110142)

无线传感器网络(WSNs)是由大量的微型传感器节点通过无线通信部署在监控区域中形成的自组织网络系统.通过传感器节点收集和聚集环境信息，最后将数据发送到基站进行进一步处理.许多领域，如军事、航空、环境、医疗等都可以受益于无线传感器网络的应用[1-2].然而，无线传感器网络仍面临许多挑战.因为传感器节点的能量非常有限，所以能量消耗是首要考虑的问题.研究表明，分簇路由可以更好地降低传感器节点的能量消耗，平衡网络能量分布，延长网络寿命[3-4].LEACH[5]是基于分簇路由协议提出的，该协议利用簇头的随机选择，在网络中的传感器之间均匀地分配能量负载，有效地从全局角度减少能量耗散并提高网络寿命.但该协议仍有许多不足之处[6-7].近年来，基于簇的路由协议不断完善，提出了LEACH-C、HMR等[8-10].然而，这些分簇路由协议仍存在一些问题，如簇头开销过大、多跳传输不合理等，导致靠近基站的节点重载流量等.

LEACH的缺点是簇头分布的不均匀导致了一些网络区域的能量消耗过大以及可用性差.随后提出了许多改进意见.LEACH-C[11]是一种基于LEACH的改进版本，其使用基站来形成集群并减少节点在创建集群时的能量消耗；LEACH-CC[12]是一种基于功率的LEACH-C的改进，其通过改变簇头节点的范围来平衡网络的能量分布；LEACH-H[13]采用遗传算法(GA)获得簇首选择的阈值公式，GA优化了公式的3个因素，包括节点的剩余能量、邻居的数量、节点和节点与基站之间的距离；基姆等[14]提出了一种利用新的概率函数确定每个回合中簇首数目的方案.上述协议改进了具有中心控制机制和剩余能量的簇首选举算法，还引入了其他参数来保证簇头的良好分布.但由于存在节点间距离相对较长的情况，所以数据传输会消耗大量的节点能量[15-17].

本文提出一种基于通信节点和多跳传输相结合的多因素自主聚类分簇路由MFACRP(mutile factors autonomous clutering routing protocol)协议.定义了2种主要节点：通信节点和簇头节点.为减少簇首的负担，采用通信节点进行中继，实现多跳数据传输.当选择簇头时，仔细考虑节点剩余能量、节点位置和邻居节点数等多个因素.新协议有效地减少节点的能量消耗，更好地平衡网络的能量分布，并大大延长网络的寿命.实验评估表明采用多跳路由和双功能节点相结合的方法可以延长网络的使用寿命.

1 系统假设和能量消耗模型

1.1 系统假设

不同的无线传感器网络路由协议有不同的应用场景.MFACRP协议的应用场景具有以下特点：

(1)传感器节点采用正态分布随机部署在监控区域内，基站位于监控区域之外.

(2)传感器节点和基站在部署后位置固定，传感器节点的能量有限，基站的能量不受限制.

(3)传感器节点通过接收信号强度与节点间距离之间的关系确定监测区域内节点的位置.

(4)传感器节点周期性地收集检测区域内的数据并将数据发送到基站.

(5)每个传感器节点的无线电发射机功率是可控的.节点可以根据发射距离选择无线电发射机的功率.

1.2 拓扑结构

根据所提MFACRP协议的应用场景的描述，假设传感器网络中有N个节点，并且基站位于监控区域之外.传感器节点的位置随机分布在监视区域中，且基站位置固定.将N个节点通过二维正态分布[18]将其部署在监视区域上.它被描述为

(1)

其中：(mi，ni)表示节点i的部署点；σm和σn分别是M维和N维的标准偏差；相对位置参数(m，n)作为该区域的中心点.如图1所示，以基站为中心，将网络区域划分为内部区域和外部区域，以对应于单跳和多跳传输.内部和外部区域中的节点通过分层方法被组织成许多局部聚类.每个簇中有簇头和一些标准节点(非簇头节点).标准节点收集监测区域内的信息并将数据发送到相应的簇头.簇头收集并聚合数据，然后根据它们所在的区域通过单跳或多跳传输将数据转发给基站.中间通信节点用来中继数据传输，平衡通信节点两端节点的能量消耗，减轻簇头的负载，降低簇头节点的能耗.

图1 拓扑结构

1.3 能耗模型

网络节点发送数据时其能耗模型[6]为

(2)

式中:Eelec为节点发送或接收单位数据所耗费的电路能量,其大小受信号的编码方式、处理以及传播方式所影响；l为要发送或接收的数据长度(比特)；d为数据发送所经过的有效距离(当d

Erx(l)=lEelec.

(3)

此种模型是无线通信过程中采用的标准模型，通信过程中融合数据所消耗的能量不做考虑.

1.4 协议中的符号

为平衡所有节点之间的能量消耗，需要获得整个网络中节点剩余能量的水平.引入下面的剩余能量估计方法来粗略估计网络的每个操作回合消耗的能量.

假设E0是网络中每个节点的初始能量，引入常数R来表示无线传感器网络的理论运行周期，每个回合中每个节点的平均能量消耗定义为

(4)

在第r轮中，每个节点的平均剩余能量定义为

(5)

其中：E(r)表示节点在每轮成功当选为簇首的能量阈值，仅当节点的剩余能量大于阈值时，节点才会有机会被选择为簇头.

协议中还定义了节点到基站的平均距离的计算方法，用常数davg来表示.由于节点随机部署在监测区域，所以采用以中间为基准的方法，将监控区域中心到基站的距离作为平均距离.计算公式为

(6)

其中：(X,Y)表示基站的坐标；(x，y)表示监视区域中心的坐标.

Davg表示节点的相邻节点的平均数目.计算公式为

(7)

其中：S表示所有的节点的集合；Ddgee(i)表示节点i的邻居节点的数目.

2 MFACRP路由协议

MFACRP协议与现有的分簇路由协议类似，MFACRP协议也是采用一轮再一轮地不断完善和修订的簇头和簇间数据传输路径的过程.

无线传感器网络首先执行初始化过程，然后将监测区域划分为单跳和多跳传输区域，接着进行一轮再一轮的簇头选取和簇间数据传输路径优化工作.每一轮MFACRP分为2个阶段：聚类和稳定传输.聚类阶段包括选举通信节点和簇头节点；稳定传输阶段处理簇间多跳路由和数据传输.为了减少由聚类引起的额外能量消耗，稳定传输阶段应远长于聚类阶段.MFACRP的工作过程如图2所示.

图2 工作时隙图

2.1 协议初始化

在聚类阶段，无线传感器网络通过执行初始化，根据节点到基站的距离，将网络的监视区域划分为内部区域和外部区域.划分内外区域的目的是减少簇头节点与基站数据传输的平均距离，平衡传感器节点的能量消耗.

在初始化期间，每个传感器节点需要通过接收信号强度指示(RSSI)来估计自己与基站的距离.首先，基站向网络中的所有节点发送广播消息，然后每个节点根据接收到的信号强度来估计自己与基站的距离.每个节点独立地决定它属于哪个区域.如果节点与基站之间的距离小于阈值，则节点属于内部区域，否则节点位于外部区域.这里将网络节点最大传输距离的一半作为划分区域的阈值.

簇头采用单跳或多跳传输，当簇头节点与基站之间的距离小于阈值时，多跳传输的能量消耗大于单跳传输的能量消耗.因此根据它们所在的区域向基站转发数据.在内部区域中，由簇头聚合的数据将通过单跳传输直接发送到基站，而外部区域中的簇头将通过多跳传输将聚合数据发送到基站.

2.2 协议工作过程

为减轻个别簇头的通信量可能过大的问题，引入通信节点进行中继和小区域的簇头选择.在簇头选举阶段开始时，通过阈值确定通信节点，然后由通信节点选择簇头.根据节点的能量和节点位置，优化簇头的选举过程.通过改进的簇头选举算法，可以保证簇头的合理分布.

2.2.1 成簇阶段

在MFACR协议中，进行成簇时必须首先选择通信节点.通信节点的选举算法采用与LEACH簇首选举算法类似的算法，这样能够确保所选通信节点可以在网络中分布均匀，不会出现通信节点空白区.通信节点作为多跳传输的中继节点，负责选择簇头.每个节点在0和1之间产生一个随机数，以决定是否成为通信节点.只有当随机数小于阈值T(n)时，它才成为通信节点.阈值T(n)计算公式为

(8)

其中：预定义参数p表示当选为通信节点的概率；参数r表示当前轮数；G是在上一轮中没有被选择为通信节点的节点集合,即当一个节点在此轮中作为通信节点，它就不能成为下一轮中的通信节点.

簇头由通信节点选出，而不采用传统的基站选择簇头的方法.这样保证了簇头节点与通信节点的距离最优且合理地分布在网络中，同时还减少了在通信过程中与基站通信的能量消耗.

在选择簇头的过程中，每个通信节点向一定距离内的节点发送广播消息，并从接收广播消息的节点接收响应消息.一旦非通信节点在本回合中接收到广播消息，它们将向通信节点发送它们的响应.响应消息为

Rep[i,E(i),dtoBS(i),Ddgee(i)].

(9)

其中：i表示节点i的ID；E(i)表示节点i的当前剩余能量；dtoBS(i)代表节点i与基站的距离，Ddgee(i)是节点i的邻居节点数.

通信节点i分别计算出向其发送响应消息的节点的阈值Gi(n)，然后选择具有最大阈值的节点作为簇头.阈值计算公式为：

(10)

式中：w1、w2、w3分别为节点剩余能量、与基站的距离、邻居节点的数量3个因子的权重值；E(r)表示节点在第r轮中成为簇头的能量阈值；davg表示所有节点与基站的平均距离；Davg表示所有节点邻居节点的平均数目.从公式(10)可以看出：剩余能量越大，与基站距离越近，邻居节点越多，则节点当选簇首的概率就越大.

在选择簇头之后，每个簇头向网络中的所有节点广播成簇消息.在接收到消息之后，每个非簇头节点根据所接收信号的强度来决定它加入哪个簇.同时，每个非簇头节点需要向自身选择的簇头发送连接请求消息.一旦形成簇，簇头便会创建TDMA调度，指定分配给簇中每个成员节点固定的通信时隙，并将此TDMA调度计划广播回簇中的每个成员节点.

2.2.2 协议的二次聚类

图3 二次聚类结构

由于簇头都是由通信节点选出，所以选出距离通信节点最近的节点作为新簇头进行数据传输.这样很大程度减少簇头因频繁传输数据而造成能量损耗，从而增加网络的生存时间.

2.2.3 稳定传输阶段

在聚类阶段之后，稳定的数据传输阶段开始.非簇头节点在簇头给它们分配的通信时间段内将它们的数据传输到簇头，数据将聚集在簇头中，然后发送到基站.位于内部区域的簇头将直接将聚合数据发送到基站.而位于外部区域的簇头将通过多跳传输将数据转发给基站.通信节点被用作多跳传输的中继节点.

3 实验结果分析

使用MATLAB验证MFACRP协议的性能，从整个网络的剩余能量、存活节点数和死节点数等方面来评估网络寿命.实验比较了LEACH、LEACH-H、HMR和MFACRP的性能.

假设300个节点在边长300 m的正方形区域的无线传感器网络中随机分布，为了简单起见，假设基站位于该区域之外，位于(350,350)的位置.仿真中的其他参数列于表1中.

簇头选举阈值公式中各因子的权重依次为W1=0.6，W2=0.27，W3=0.13.

表1 仿真参数

节点的剩余能量能够反映网络总能耗的状态，所以可以通过网络中节点的剩余能量来衡量网络寿命.在运行相同轮数的情况下，网络中节点的剩余能量越多，网络能量利用效率越高.

在仿真实验中，规定网络生存周期从开始到存活节点的数量小于总节点的10 %结束.因此稳定期即为从网络运行开始直到死亡节点的数目超过总节点的90 %时.稳定期越长，协议的性能越好.

图4显示了在相同环境下，LEACH、LEACH-H、HMR和MFACRP在经历了相同轮次后的存活节点数量变化趋势.在协议运行过程中，协议的稳定周期分别达到230轮、531轮、866轮和1 274轮.4种协议的生命周期分别为966轮、1 262轮、1 252轮和1 581轮.与LEACH协议相比，两个改进的协议LEACH-H和HMR可以有效地将网络寿命延长近31 %.而MFACRP的寿命可延长64 %.在MFACRP协议中，稳定传输阶段期间采用通信节点作为数据传输的中继，这种改进降低了节点与基站通信的能量消耗，并解决了簇头的通信过载问题.通信节点的引入有效地延长了稳定期.

图4 节点数量对比

数据传输性能可通过基站接收的数据包数量来证明.图5显示了在相同环境中相同运行轮次下LEACH、LEACH-H、HMR和MFACRP协议的基站接收数据包数量变化趋势.

图5 接收数据包对比

从图5可以看出：随着操作轮次的增加，基站在MFACRP协议中接收的数据包数量远远大于相同轮次下其他协议接收的数据包数量.在MFACRP中发送到基站的数据包大约在第 1 500 轮时饱和，同时基站大约接收了20 800个数据包.基站在LEACH、LEACH-H和HMR中接收的数据包数量远小于MFACRP.因此，MFACRP协议可以显著提高数据传输能力和交互能力，表明在相同的运行环境中可以收集更多的数据并且提高网络性能.

4 结 论

如何有效利用有限的节点能量来延长无线传感器网络的生存时间是无线传感器网络面临的一个重要挑战.本文提出的MFACRP协议以减少传感器节点的能量消耗，同时使网络节点能量负载均衡，以及优化簇头的选择.为了减少簇头的能量开销，引入通信节点作为多跳传输的中继节点，通信节点同时负责选择簇头.为使簇头选举过程更加合理高效，在成簇完成后，对于重叠度较高的簇重新进行聚类.为了适应不同的传输方式，将监控区域划分为不同的区域，簇头将采用单跳或多跳传输，根据它们所在的区域将数据转发给基站.同时MFACRP协议利用局部最优路径构造算法来有效减少多跳路径中节点的能量消耗.仿真结果表明，该协议能够提高节点的能量利用效率，有效地平衡网络的能量分布，从而延长网络的使用寿命.