基于多簇头K连通的抗毁拓扑构建方法

2021-08-06陈雯柏王文凯

重庆理工大学学报(自然科学) 2021年7期

吴昊，陈雯柏，2，王文凯，郝翠

（1.北京信息科技大学自动化学院，北京 100192；2.北京市通信与信息系统重点实验室，北京 100044）

当前，无线传感器网络（wireless sensor networks，WSNs）广泛应用于社会各领域［1－2］。当处于复杂、对抗和恶劣的网络环境中时，系统拓扑结构的抗毁性和可靠性是无线传感器节点成功完成任务的关键［3－4］。人为打击、能量耗尽以及恶劣的感知环境等因素，将直接或间接导致无线传感器节点的失效，进而致使WSNs系统拓扑结构分割，降低WSNs系统的性能，进而导致感知任务失败［5］。

为增强WSNs系统拓扑结构抗毁性，Yin等［6］基于WSNs无标度拓扑展开研究，得到度分布指数和幂律系数与WSNs容错性能正相关这一结论。李雅倩等［7］利用概率母函数法求解WSNs无标度拓扑级联失效的临界负载值。但这种平面型网络拓扑结构缺乏灵活性，在网络中会存在大量冗余链接，加大整个WSNs系统的通信负载量，使得WSNs的能量消耗加剧，从而缩短网络的整体生存周期。相对而言，层次型网络拓扑结构可有效对节点进行分层管理，减少节点通信能耗，并且网络可扩展性较好。近年来，基于分簇机制的层次型拓扑控制成为研究热点。Dasgupta等［8］提出一种基于分簇的启发式算法使网络存活时间最大化。常铁原等［9］通过平衡簇内节点通信与簇间节点通信的能耗，使用副簇头进行中继转发延长网络寿命。周远林等［10］提出一种基于演化博弈论的无线传感器网络节能分簇路由算法，均衡节点间能耗，有效延长网络生命周期。但这些算法大多只是针对网络能量消耗进行优化以延长网络寿命，并未考虑节点失效的情况。

在WSNs系统中，传感器节点的失效会导致网络拓扑结构不断改变，网络中容易出现连通性较差的节点。该节点的存在会造成感知信息传递的拥塞，一旦能量耗尽或者遭受到恶意攻击，很可能使得网络拓扑结构断裂，甚至网络崩溃［11－13］。本文针对于无线传感器网络复杂应用环境中簇头节点失效问题，提出一种改进的多簇头K连通抗毁拓扑结构的构建方法，并基于OPNET仿真，验证分析了算法的有效性。

1 系统抗毁性模型

假设WSNs系统中各节点功率可调，t时刻节点vi的发射功率为0≤pi（t）≤pmax，其中pmax表示所有成员节点vi的最大发射功率。根据传输媒介中的噪音类型，各个节点需要的传输能耗由无线传输模型进行计算［14］。

采用的无线传输模型不仅考虑了接收器的接收功耗，还考虑到了发射器的传输功耗。t时刻发射器传输功耗与节点vi和节点vj间的距离dij（t）成正比。pij（t）表示t时刻节点vi和节点vj之间能实现信息交互需要的传输功率。所以，经过dij（t）的距离传输b bits信息，各个节点需要的传输功耗如下：

式中：pelec和λamp分别为发射器和接收器的驱动电路以及放大器需要的无线传输损耗。

每个节点的初始传输功率一致，节点随机部署后，可得到一个动态的网络拓扑图G（t）＝（V，E（t）），其中节点集V＝（v1，v2，…，vn）表示WSNs系统中的传感器节点，若t时刻两传感器节点间进行了通信，则边集E（t）表示随时间变化的各传感器节点间的无向信息交互边，如式（4）所示：

式中：传感器节点vi和vj间的信息交互边用（vi，vj）来表示。

引入以下相关定义与假设：

定义1 在分簇算法中用无向图来表示节点之间的双向链路连接，不考虑隐藏终端和暴露终端等问题。

定义2 在t时刻，图G（t）＝（V，E（t））是K连通的，图G（t）中任意K－1个节点失效，图G（t）会分割为2个或多个连通子图。

定义3 AP节点使用全向天线进行广播通信，AP节点能量无限且全网一跳可达。

定义4 节点vi和vj之间的距离dij＜R，说明vi和vj可直接通信，则vi和vj之间的跳数DH（vi，vj）；若vi和vj之间不能通信，则DH（vi，vj）＝0。

定义5 各节点有唯一标识id（vi）＝i。节点的一跳邻居数为Nbn，即节点的度。

定义6 簇头是簇的管理者和信息收集中心。簇头集合用CH表示。

定义7 簇集合用C表示，C＝（C1，C2，…，CK），CH（i）为簇Ci的簇头，其id为id（CHi），簇大小即簇内成员节点数用NC（Ci）表示。

2 改进多簇头K连通网络抗毁算法

改进多簇头K连通网络抗毁策略分为3个阶段：第1阶段为簇头选举；第2阶段为簇内关键节点检测；第3阶段是构建簇内K连通网络。簇头选举前，需要对网络进行分簇，网络分簇采用KMeans聚类算法把WSNs系统划分为K个互不相交叠的簇；网络分簇后，基于节点连通可靠度来进行簇头选举，然后簇头节点为建立簇内成员节点与簇头节点之间的通信路径，加载地理位置路由算法在簇内进行泛洪，产生节点路由信息表，检测关键节点，若节点维护的邻居节点的路由表中没有K个邻居，则簇头节点给成员节点发送hello消息包，成员节点收到消息包后，调节节点发射功率，使其可以与其他节点进行通信。

2.1 基于连通可靠度的多簇头选举算法

基于连通可靠度的多簇头选举算法需要计算节点连通性，采用连通可靠度约束确定临时簇头集合，根据临时簇头节点的权值大小确定工作簇头。多簇头选举算法描述如算法1所示。

输入：网络相关参数

do k-means；

do选取临时簇头；

do选举簇头；

if簇头失效

then临时簇头升级为簇头；

end if

在水泥混凝土路面切缝方面，应该实施横向施工缝配合锯缝方法，保证缝深度在6cm左右，缝宽度在5mm左右。切缝过程中要始终保证充足注水，且允许在切缝过程中直接切断，但需要时刻关注刀片的注水情况。另外在接缝位置要采用灌缝料加工方法，锯缝位置浇灌水泥混合沥青，且在灌缝之前需要清除缝隙内存在的临时密堵材料，保证缝顶面高度施工与路面位置平齐，全面提高水泥混凝土路面的施工质量[4]。

节点初始化之后，利用K-Means算法对节点集合进行分簇。分簇完成后，每个节点开始检测1跳邻居节点，并记录1跳邻居节点身份、位置等信息，统计直接邻居数。各节点根据自身1跳邻居数与1跳邻居节点的直接邻居的数目进行比较，选取1跳邻居节点中直接邻居数最多的1跳邻居作为自己的临时簇头，把所有簇头节点加入临时簇头集合TH中。

Sensor为非簇头节点，按式（5）计算其连通可靠度，TCH为临时簇头节点，按式（6）计算自身的连通可靠度。

式中：CH（i）表示节点i的簇头；deg（i，CH（i））表示节点i连通可靠度，当成员节点与其簇头在一起时，deg（i，CH（i））＝0，CPS（vi）＝1。

对于节点i的分簇C（i），假设其簇头为CH（i），临时簇头节点的连通可靠度为：

其中：NC（Ci）是簇C（i）的成员节点个数。

由式（6）可知，如果一个临时簇头节点的成员节点数量少，则连通簇头的可靠度就低。

由于节点与分簇质心距离越近，节点通信总代价越小，并在WSNs中节点的连通度为6～8时，网络的性能最优。因此权值公式：

式中：w1及w2为权重因子；dist为临时簇头到聚类质心的欧氏距离；deg为簇头节点的连通度。从临时簇头集合中选取权值W最大的节点作为簇头。

簇头节点不仅可以收集、处理簇内成员节点的感知消息［15］，而且还可以调节成员节点的发射功率，因此簇头节点的负载和通信量远远大于簇内普通的成员节点，更容易成为选择性攻击破坏的目标，故簇头节点的故障失效率远大于成员节点。簇头节点一旦失效，则感知数据也会随之丢失，会严重影响系统的稳定性、可靠性以及抗毁性。为提高WSNs系统抗毁性，提升网络性能，在K-Means分簇算法构建的分簇网络的基础上，提出了多簇头机制，即在每个簇内选择多个簇头，当正在工作的簇头遭受攻击或者电池能量不足时，临时簇头集合中权值最大的节点自动升级成为簇头。

在每个簇内维护一个由K个备份簇头组成的簇头集合，系统中的每一个簇当前仅有一个簇头节点正在工作，当前工作的簇头节点故障时，簇内成员节点可以快速地与簇头集合中的备份簇头节点之间建立连接，保证数据能够及时、准确地发送到控制节点AP，多簇头机制模型如图1所示。

图1 多簇头网络拓扑模型示意图

多簇头机制模型容错性与抗毁性的提升是通过当前工作的每个簇头节点维护着一份簇头节点集合路由表实现的，通过簇头节点的冗余增大了各个成员节点将数据通过多跳形式转发到簇头节点的概率。这一方法实现较为简单，每个备份簇头集合根据簇头选举算法的权值公式重新计算临时簇头的权值大小，不过将临时簇头与质心节点之间的距离变为与簇头之间的距离，选出权值最大的临时簇头作为备份簇头，不断循环，形成备份簇头集合。当前簇头由于故障失效时，备份簇头则自动转化成簇头，并在簇内进行泛洪，这样就减少了由于簇头失效进行簇头选举所使用的时间，提高了网络容错性能的水平。

2.2 K连通节点检测

WSNs系统拓扑结构用无向图G＝（V，E）表示。V为节点集合，E为传感器节点间的通信路径组成的边集。若两传感器节点间只有一条通信路径，则称该无向图G是单连通的；若任意两传感器节点间的通信路径不止一条，则称该无向图G是双连通或多连通，删除该双连通或多连通图中任意一条信息交互边，该图的连通性也基本不会发生改变。

基于簇的层次型网络的初始拓扑结构并非全是双连通或者多连通的，提出一种K连通检测算法，用来查找网络中的单连通节点，即关键节点，然后通过网络中的簇头节点来调节该关键节点的发射功率，使其可以与周围的其他传感器节点之间建立通信路径，不用移动WSNs系统中的任何节点，即可实现WSNs系统转化为K连通网络，从而保证网络不会由于某一传感器节点的失效而致使整个WSNs系统拓扑结构的割裂，提高系统在不同环境下的可靠性和抗毁性。

WSNs系统节点的通信半径和节点的部署位置决定了网络的初始拓扑结构［16］。调节节点的发射功率，使最终形成的系统拓扑结构是K连通的，并在该基础上，最大化降低WSNs系统中传感器节点的通信传输损耗，延长WSNs系统的生存周期。

K连通描述的是系统网络拓扑结构的全局特征，单个传感器节点仅拥有其自身及1跳邻居节点的拓扑信息，因此无法直接确定当前系统是否是K连通的。本文中采用了分布式策略，首先采用WSNs系统的经典分簇算法［17－18］，将整个网络划分为多个互相不交叠的簇，然后检测各个簇是否均为K连通。若某些簇不是K连通的，则在系统的网络拓扑结构改变之前，采取相应的措施来将其构建成为K连通的簇。

在网络分簇及簇头选举之后，簇头节点通过周期性的泛洪状态信息，簇内成员节点收到消息后，通过地理位置路由算法不断维护其自身的路由信息表，表1所示为节点所维护的路由信息表，其中包含了源节点、目的节点、传输功率、最大传输功率及节点的删除指数。路由信息表包含了节点通信过程中所需的必要信息，网络中所有节点的路由信息表构成了网络的拓扑结构。节点的删除指数表明了当前节点的连通度以及信息的可靠性，节点的删除指数越大，则意味着节点所收到的信息越可靠。

表1 路由信息

每个簇头节点获取其所在簇中所有成员节点的状态信息，通过表中的相关路由信息，判断当前簇是否为K连通。如图2所示，根据节点1的路由状态信息表，可知在节点1所在的簇中，节点1与簇内其他节点之间至少存在2条信息交互边，即节点2和节点3。但是通过检测簇内所有节点的状态信息表可以发现，节点6只有1条与节点2的信息交互边，因此可知该簇是单连通的，需要将其构建成为K连通网络。

图2 簇拓扑图和簇信息表结构框图

2.3 改进多簇头K连通抗毁拓扑构建

考虑到WSNs系统中节点的移动性差等特点，同时为了不影响网络的初始部署与分配，网络经过K连通检测之后，簇头节点将需要构建K连通的节点存入消息包内，称这些节点为关键节点。然后簇头发送泛洪消息，调节关键节点发射功率，使其与网络中其他节点产生新的信息交互边，使系统中所有关键节点逐步成为非关键节点，从而实现WSNs系统K连通拓扑结构的构建。

在系统的网络拓扑结构已经分簇的基础上，根据K连通检测算法，判断当前簇是K连通的，且K＜Kth，采用Harary图思想［18］，构建需要的连通簇。Kth连通簇的构建首先需要对网络进行初始化，进行网络分簇与多簇头选举。簇头节点处理成员节点转发的消息数据包，找出网络中的关键节点。如果需要构建K连通的簇的连通性Kth是偶数，则将簇中关键节点与各个方向上与该节点相邻的（Kth－1）／2个节点进行相连，得到最终的拓扑图GKCth－1，n（GC（K））。若需要构建K连通的簇的连通性Kth是奇数，则将簇中关键成员节点与各个方向上与该点相邻的（Kth－1）／2个节点进行相连，得到最终的拓扑图GKCth－1，n（GC（K））。Kth连通簇构建算法伪代码如算法2所示。

根据以上算法，簇头计算出簇中每个关键节点所需的发射功率，进而计算出节点所需添加的信息交互边。若簇头发现某些关键节点的最大发射功率小于需要的发射功率，那么簇头节点应相应地增大关键节点需要连接的节点的接收功率来建立连接，若还是无法通信，则放弃该节点。

图3（a）是基于K-Means聚类算法与簇头选举算法后得到的单连通拓扑结构。网络拓扑中，通过关键节点检测算法可以得到节点5与节点7为关键节点。首先，簇头节点收集各簇内节点经过地理位置路由泛洪发送过来的数据包，然后检测出是否有节点为单连通。若存在，则计算与其最近的非连通节点与关键节点之间的距离，计算出与非连通节点进行通信所需要的功率。之后在簇内发送泛洪消息，簇内节点接收到数据包后，判断自己是否为目的节点。若是，则开始增大发射功率至其可与其他节点进行通信；否则丢弃该数据包。以节点7为例，增大其发射功率后，其与节点6与簇头1之间均建立了信息交互边。节点5同理与节点2之间也建立了信息交互边。如图3（b）所示，节点5和节点7也不再是关键节点，从而构建出一个K连通拓扑结构。

图3 K连通拓扑结构示意图

采用K-Means聚类算法的分布式策略后，经过关键节点的检测和关键节点的功率控制相结合的分布式算法，使网络中的所有的关键节点转变为非关键节点，构建出了一个K连通的网络拓扑结构，从而增强了整个系统的拓扑结构的抗毁性和可靠性。

3 算法性能分析

模型中的传感器节点随机部署在网络区域中，普通传感器节点能量受限，但是其功率可调节，AP节点能量无限，其他具体参数如表2所示。

表2 WSNs系统网络参数

如图4所示为基于改进多簇头K连通抗毁策略的WSNs系统在仿真后产生的网络收发包的大小曲线。从图中可以看出：随着仿真时间的推进，网络的收发包数量大小已经趋于稳定，因而可以使用稳定阶段的网络收发包的数量大小来计算网络的丢包率。由图可知，在网络仿真运行300 s时，基于改进多簇头K连通WSNs系统抗毁策略构建的网络发送数据包大小为410 824 bits，接收包大小为374 294 bits，因此可计算出网络的丢包率为8.89%，比基于K-Means算法的普通分簇网络的丢包率降低了15.63%。可见，就网络丢包率来看，改进多簇头K连通WSNs系统具有很好的抗毁性。算法通过节点连通可靠度选举多个簇头，利用K连通检测算法检测出关键节点并调整其发射功率，节约了簇头节点失效后网络重新进行簇头选举所耗费的时间，因此网络丢包率明显降低。

图4 WSNs系统平均收发包数量曲线

图5给出了基于改进多簇头K连通抗毁策略的效果对比。从图中可以看出：随着仿真时间的推进，网络的端到端时延已经趋于稳定，因而可以使用稳定阶段的网络端到端时延大小来研究网络的抗毁性能。由图可知：在网络仿真运行300 s时，基于改进多簇头K连通WSNs系统抗毁策略构建的网络端到端时延为9.95 ms，比基于KMeans算法的普通分簇网络的端到端时延降低了20.1%。从网络时延方面来看，改进多簇头K连通WSNs系统也具有较好的抗毁性。算法通过选举多个簇头并检测出关键节点，调整其发射功率，选取最优备份簇头节点，在簇头失效后，备份簇头成为簇头节点，簇内节点与新簇头节点距离减小，端到端时延得到降低。