骨干节点充当簇首的层次路由协议设计*

刘志强， 关乾煜， 王瑞利， 何平基， 张 旭

(内蒙古工业大学 信息工程学院，内蒙古 呼和浩特 010080)

0 引 言

由于无线传感器网络(wireless sensor networks,WSNs)部署的环境特殊，网络中各节点的能量消耗成为影响整个网络生命周期的关键因素[1]。而硬件条件的限制，使得高效的拓扑路由协议成为了WSNs领域研究的热点。根据网络的拓扑结构，可以将WSNs划分为两种类型的拓扑路由协议，分别为平面型和层次型[2]。

层次型路由算法低能量自适应聚簇分层(low energy adaptive clustering hierarchy,LEACH)[3]是最早提出分簇概念的层次路由协议，被视作层次路由协议中的经典。在这一算法中，利用“轮”这一单位来分割网络生命周期，一轮即重新分簇(建簇阶段)到数据传输(拓扑稳定阶段)两个阶段的过程。在这种算法中，有效划分了网络节点的角色，高效率分配了不同节点的任务，其最大的突破在于极大的压缩了网络能耗。

但是这种算法的问题主要体现在簇的划分、簇头的选取等方面。因此，业内人士纷纷探索LEACH拓扑路由算法的改进策略。LEACH-C(LEACH-centralized)[4]和LEACH-F(LEACH-fixed)[5]这两种改进算法，同样沿袭了由建簇阶段到数据传输的拓扑稳定阶段的过程，在建簇阶段便强调了节点的能耗问题，节点会向基站节点发送自身的能耗状况，基站节点在获取到基础数据后，会展开模拟退火算法(simulated annealing algorithm)进而得到最优的簇头分配方案，以此方案为指导来进行网络分簇。相比于LEACH算法，上述两类算法并未对数据传输的稳定阶段进行出改进，其特殊之处主要体现在应用模拟退火算法来计算各节点的能耗数据，以此实现降低网络开销。

Improved-LEACH[6]算法中增设了节点未当选簇头的轮数间隔以及节点的剩余能量这两类信息，一次影响节点成为簇头的概率，且呈现出明显的正相关关系。针对此算法展开了仿真实验，结果显示，相比于LEACH算法，第一个节点死亡时间的提升幅度高达106 %，由此可见，应用此算法能够有效提升网络的生命周期。

LEACH-CR[7](low energy adaptive clustering hierarchy-consumption reduction)算法首先明确了分簇数量，通过设置阈值M(M=节点数/分簇数量/2)来完成逻辑分区操作。分区后的每个分簇内，簇头节点的选择秉持着能量优先的原则，即优先选取能量最大的节点来执行与基站节点通信的任务。因此，簇内的网络能耗得以分担，整体网络寿命也会有大幅延长。

由上分析可见，在层次型拓扑路由结构中，簇头的选择是延长WSNs生命周期的关键，目前簇头多数是基于剩余能耗或者随机数下选取的，弊端较大。本文在LEACH算法的基础上，研究簇头选取机制。

1 以骨干节点作为簇首的拓扑路由算法

LEACH算法所有节点都参与到簇头的选择中，导致簇头分布不均匀[8]。另外，簇头的选取都是各个节点产生一个随机数，当该随机数小于指定值时，选作簇头,一定会出现大于指定值的情况，这时，各个节点又得产生新的随机数，重新进行比较，降低效率，增加了损耗。近年来，很多改进算法都考虑到了能耗问题，但仍存在一些缺陷,不能够达到更好的能耗均衡的效果。

鉴于这些问题，以及WSNs中的传感器节点硬件资源的局限性，提出了一种以骨干节点充当簇头的(skeleton nodes acting as cluster head,SNACH)拓扑路由算法，使得簇头均匀分布以实现网络能量均衡。

1.1 算法描述

SNACH算法的创新点在于将图像处理技术中图形骨架的概念运用到WSNs中，图形中提取的骨架可以抽象表示出图形原本的模样，在WSNs中提取的骨架节点也能够反映出原始网络的结构特征。这些“骨架”上的节点到边界的距离基本相等，并大致处于网络的中轴位置,将该特点应用到WSNs层次路由协议的簇头选取中，令这些骨架节点以及骨架节点的1～3跳节点作为簇头的备选集合，并根据最优簇头的数目设定一个步长，使集合中的节点轮流当选簇头，这样能够使簇头均匀分布，并均衡了网络能耗。

1.2 在监测区域内提取骨干节点

1)识别边界节点

识别监测区域的边界节点，用于准确提取出骨干节点。本文采用多维标度(multi-dimensional scaling,MDS)分析技术。在网络中选取任意一个网络内部节点以及边界节点，这两个节点通过发送局部的洪泛消息，从而获得局部邻居节点信息，再根据这些信息得到邻居节点间最小跳数矩阵，进而通过MDS算法进行维度规约，得到节点的虚拟坐标，最终分析出网络的边界节点信息。

2)提取骨干节点

以图像G为对象，首先根据边界节点进行计算分析，确定其所有对应的连通分支，所有连通分支就将同属于一个边界分支集合C中。假设G中任意两个节点及相应的边界分支，分别用参数u，v和Ci表示，那么节点u与v之间的最短路径长度就可表述为d(u,v)。节点v与边界分支C之间的距离用D(v,Ci)表示，对应的节点v与分支内所有节点最小距离值由D(v,Ci)=min(d(v,w),w∈Ci)进行计算。在图G中，任一节点到两个及以上最近边界分支的距离相同，则该节点就将以骨架节点进行判定。这一结果的理论依据可以简单描述为：若网络存在多个边界分支，那么每个骨架节点所处于的位置不得低于两条边界分支的中间，即骨架节点是不同边界分支的中间节点。这一判定的具体原理为：首先定义每个边界节点，参数〈Ci,IDj〉的含义是边界分支Ci内的一个叫IDj的节点，以此为基础，所定义的边界节点将以自身名字等为洪泛信息向图G发送，同时为该信息定义一种计数器对转发的次数进行统计记录。则所有内部节点所接收和记录的洪泛信息中计数器值最小的节点，其与边界分支的距离就将作为最短距离。洪泛信息实现了对每个节点与边界分支距离的计算和确定。骨干节点形式化的定义为

对于任一的网络连接图而言，G与v分别表示连通图与图内的任一节点，若节点v与G的关系存在以下任意一项，则可将节点v判定为骨干节点：

1)若网络连通图G中存在不低于两条的边界分支(边界分支用Ci,…,Cj表示)，如果存在D(v,Ci)=…=D(v,Cj)=minD(v,B(G))，即节点v与上述边界分支的距离相等且均为最小值；

按照骨干节点的定义方式，就能够在簇内提取出一定数量的骨干节点。这时，就可以将这些骨干节点作为簇头节点。在网络中，这些簇头基本处于“中轴”位置，并且至少存在两个边界节点到该点的最短距离相同。

3)扩展骨干节点

骨干节点是选举簇头的最优集合，但考虑到簇头节点能量消耗大的问题，在骨架节点的基础上对骨架节点进行扩展，得到一个簇头的备选集合，称为骨架节点网络带。对于监测区域内传感器节点较少的网络而言，可以直接将骨架节点3跳以内的邻居节点作为对原始骨架节点的扩展，并加入到簇头的备选集合中。对于节点较为密集的监测区域而言，就可以经扩展得到更多的簇头备选节点。首先，找到距离最近的两个骨架节点连通分支，从而得到两个分支的最短路径，并将路径上的节点都作为簇头备选节点加入到骨架节点集合中去，最终得到一条扩展的骨架节点连通分支，形成一个包含最优骨架节点以及扩展骨架节点的集合，集合内节点相对于其他节点而言都位于网络的中间位置到边界距离相对平均，是选择簇头的最优备选集合。

1.3 节点成簇完成网络拓扑结构

成簇的过程是一个簇头广播公告消息和普通节点选择是否加入的双向过程。首先，当选簇头的节点广播一个包含自己身份信息的消息，这个消息的广播方式同样是利用载波侦听多路访问(carrier sense multiple access,CSMA)协议。此时各节点会接收到很多包含簇头自身信息的消息，对于普通节点而言，会选择接收时信号较强的节点作为自己的簇头，并发送一个包含自身信息的反馈消息，将该节点入簇的请求告知簇头。当每个节点都找到合适的簇头后，分簇完成。此时簇头可以根据簇内节点信息进行时分多址(time division multiple address,TDMA)调度表的创建，令节点只在自己所分配的TDMA时隙中发送数据，其他时间处于休眠状态，这样既降低了能耗，又防止了数据传输冲突。SNACH算法的工作流程如图1所示。

图1 SNACH算法流程

1.4 算法步骤

1)在整个监测区域内识别边界节点，通过边界节点信息提取骨干节点作为簇头；

2)对骨干节点进行扩展，得到一个连通性较好的骨干带网络作为簇头的备选集合；

do{

3)对簇头以及簇头的备选集合中的各节点建立能量模型；

4)簇头广播一个通告消息，其他节点通过收到消息的信号强弱来判断选择哪一个簇头，直到每一个节点都加入到簇中，分簇完成。

}while(簇头节点能量过低)。

1.5 算法分析

在拓扑发现的过程中先提取骨架节点作为簇头，这些骨架节点在监测区域内基本处于“中轴”位置，而对骨架节点进行扩展后的骨架节点网络带也处于整个监测区域的中间位置。在簇内的各个节点都需要将自身的信息发送给簇头，再由簇头发送给基站。因此，选取一个在物理空间里，位置适当的节点作为簇头，则能够大大减少节点发送自身信息时的传送距离，减少簇内成员节点与簇头通信过程中能量的消耗。以此为基础，在簇头的备选集合中建立节点能量模型，当簇头能量过低时，选取能量相对最高的节点作为簇头，在实现了能量均衡的同时，延长了节点寿命，保证了整个网络的正常运行。

2 OMNeT++仿真实验

2.1 仿真环境

搭建OMNeT++5.0仿真平台，编写NED网络模块以及消息文件，并通过C++编程语言实现对应模块的逻辑结构，最后在omnetpp.ini文件中编写相应的网络设置参数。其中，定义了200个节点在边界为200 m×200 m的区域中进行1 000轮仿真测试。TDMA时序表帧设为5，则簇头节点和BS节点进行5次通信后，网络重新进行分簇。另外，网络中节点的分布是通过随机数的生成而实现的，但OMNeT++中为了保证每次仿真的可重复性，在定义网络拓扑的NED文件中，没有设置随机数种子的函数，要避免伪随机数的情况，就需要在omnetpp.ini文件中手动设置随机数种子。如下述代码所述，设置了两个随机数种子，分别为13和9

num-rngs=2，seed-0-mt=13，seed-1-mt=9

2.2 仿真结果

如图2所示，分别为LEACH算法和SNACH算法在第5轮时簇头的分布情况，可以看出在LEACH算法中，3个簇头节点承担了网络中大部分节点的数据收集及传输任务，而另3个簇头节点则“集中”在了一起，只承担了一小部分的节点数据收集及传输任务，簇头节点分布十分不均匀。而SNACH算法可以看出处于骨干节点网络带上的簇头节点分布十分均匀，6个簇头节点分担了网络中的数据收集及传输任务，使得网络中能耗更加均衡。

图2 LEACH和SNACH算法第5轮拓扑对比

如图3所示，分别是LEACH算法和SNACH算法在第454轮时的拓扑情况，实验将死亡节点标记为黑色，可以看出，此时LEACH算法网络中已有50 %以上的节点死亡，并且随机产生的6个簇头节点都集中在了网络的上半部分。而SNACH算法在454轮时，只有一个节点死亡。

图3 LEACH和SNACH算法第454轮拓扑对比

如图4所示，BS处于不同位置时，仿真网络存活节点进行了对比。

图4 1000轮仿真网络存活节点对比

BS节点坐标为(100,100)时，SNACH算法与LEACH算法进行了1 000轮的仿真实验。可以看出，LEACH算法在第152轮时开始出现节点死亡的现象，在第445轮时网络中50 %的节点已经死亡，从第645轮开始，剩余节点数骤降，又经过4轮运行之后，剩余节点稳定在3个直到1 000轮仿真结束。反观SNACH算法，运行到第452轮才有节点开始死亡，之后剩余节点一直均匀减少，直到1 000轮仿真结束时，仍有28个节点存活。SNACH算法的网络生存周期远远高于LEACH算法，网络中节点开始死亡的时间比LEACH算法多197 %。BS节点坐标为(0,0)时，SNACH算法与LEACH算法进行了1 000轮的仿真实验。可以看出，LEACH算法和SNACH算法分别在第89轮和第286轮时开始出现节点死亡的现象，网络中节点开始死亡的时间SNACH算法比LEACH算法多221%。BS节点坐标为(250,100)时，同样SNACH算法与LEACH算法进行了1 000轮的仿真实验。可以看出LEACH算法和SNACH算法分别在第95轮和第299轮时开始出现节点死亡的现象，网络中节点开始死亡的时间SNACH算法比LEACH算法多214 %。

3 结束语

本文在整个网络中提取骨干节点并进行扩展，得到一个簇头的备选集合，其核心为利用集合中的节点轮替充当簇头。其优点在于将簇头节点均匀的分布在网络中，降低了簇头的“压力”，减小了节点能耗，从而延长了整个网络的寿命。在后续研究中，本算法还将进一步完善。