一种容错型混合连通支配集的构建方法、系统及应用

本发明涉及无线通信网络，具体为一种容错型混合连通支配集的构建方法、系统及应用。

背景技术：

1、无线传感器网络广泛应用于环境监测、灾害救援、工业传感等场景，通常基于单位圆盘图建模，以连通支配集作为虚拟骨干承担数据转发任务，以此缓解广播风暴、降低网络能耗。

2、传统连通支配集仅聚焦单一的节点故障或边故障类型，然而在实际无线传感器网络运行中，节点失效与链路断裂并非总是独立发生，而常以混合失效形式共存。如在森林火灾监测、深处矿井探测等危险场景中，节点失效与链路信号阻断的同步出现，将直接导致虚拟骨干整体损毁并碎片化，引发严重通信中断。但传统连通支配集难以有效应对节点与边同时失效的复杂场景。此外，在多通信模式无线网络中，不同通信模式下的协议（如蓝牙、wifi、zigbee等）在传输半径以及能耗特性等方面存在显著差异，但连通支配集设计通常基于单一通信模式构建，当侧重减少连通支配集规模来控制能耗时，其容错性往往难以兼顾；若选取容错型连通支配集以提升网络抗失效能力，则势必造成连通支配集规模的冗余增大。

技术实现思路

1、本发明的目的是提供一种容错型混合连通支配集的构建方法、系统及应用。

2、本发明技术方案如下：

3、一种容错型混合连通支配集的构建方法，包括如下操作：

4、s1、获取无线传感器网络的网络拓扑结构，在网络拓扑结构中构建（2,m）-连通支配集，将（2,m）-连通支配集中所有节点进行第一标记，作为初始连通支配集；

5、s2、对初始连通支配集，依次进行双边失效、点边混合失效、双节点失效的检测与修复，直至初始连通支配集中不存在双边失效、或点边混合失效、或双节点失效，得到筛选连通支配集；

6、三类失效按双边失效、点边混合失效、双节点失效的顺序依次遍历检测；

7、针对同一类失效，先检出相应类全部失效集合，再批量开展修复；单类失效修复过程为：删除失效对应的故障元素，使支配集诱导子图分割为多个连通分量；在原始网络拓扑结构图中选取连通各分量的修复路径，将路径内非支配集节点并入支配集以消除当前失效；循环检测、修复直至该类失效完全消除后，再进入下一类失效处理流程；

8、s3、按节点度数升序遍历筛选连通支配集内所有节点，逐一判定并删减冗余节点，冗余节点为被移除后支配集诱导子图仍满足3-混合连通性、且全网节点均满足m重支配约束的节点，m为预设支配重数；循环遍历直至不存在可删减的冗余节点，输出能够抵御双节点失效、双边失效、点边混合失效中任意两类混合故障的(3,m)-混合连通支配集。

9、s2中，三类失效判定规则为：双边失效：支配集内两条独立通信边，同步移除两条边后，支配集诱导子图分割为多个连通分量；点边混合失效：单个支配集节点搭配单条通信边，同步移除该节点与该边后，支配集诱导子图不再连通；双节点失效：一对支配集节点，同步移除两个节点后，支配集诱导子图分割为多个连通分量。

10、修复路径为连接分裂连通分量的全局最短路径，且路径上仅允许最多2个非支配集中间节点。

11、在s2的每一类失效检测完成后，先根据节点故障概率与边故障概率计算各失效的失效风险权重，再按照失效风险权重从高到低的顺序依次选取失效进行修复。

12、双边失效的失效风险权重为对应两条边的故障概率之积，点边混合失效的失效风险权重为对应节点故障概率与对应边故障概率之积，双节点失效的失效风险权重为相应两个节点的故障概率之积。

13、在s3删减冗余节点的操作之后，还包括进行混合不相交支配路径校验，具体为遍历全部非支配集节点，为每个节点筛选m条接入支配集的通信路径，约束任意两条路径无公共支配集节点、无公共传输链路；若无法满足则在缺失路径上新增支配集节点。

14、3-混合连通性为支配集诱导子图的混合连通度，需要移除至少3个混合失效元素，才能够使支配集诱导子图变为不连通，混合失效元素为失效节点或者失效通信边；m重支配约束是指网络中每一个非支配集节点，至少存在m个支配集节点作为其邻居，非支配集节点可通过上述邻居接入支配集。

15、一种容错型混合连通支配集的构建系统，用于实现上述的容错型混合连通支配集的构建方法，包括：

16、初始连通支配集生成模块，用于获取无线传感器网络的网络拓扑结构，在网络拓扑结构中构建（2,m）-连通支配集，将（2,m）-连通支配集中所有节点进行第一标记，作为初始连通支配集；

17、筛选连通支配集生成模块，用于对初始连通支配集，依次进行双边失效、点边混合失效、双节点失效的检测与修复，直至初始连通支配集中不存在双边失效、点边混合失效和双节点失效，得到筛选连通支配集；三类失效按双边失效、点边混合失效、双节点失效的顺序依次遍历检测；针对同一类失效，先检出相应类全部失效集合，再批量开展修复；单类失效修复过程为：删除失效对应的故障元素，使支配集诱导子图分割为多个连通分量；在原始网络拓扑结构图中选取连通各分量的修复路径，将路径内非支配集节点并入支配集以消除当前失效；循环检测、修复直至该类失效完全消除后，再进入下一类失效处理流程；

18、(3,m)-混合连通支配集生成模块，用于按节点度数升序遍历筛选连通支配集内所有节点，逐一判定并删减冗余节点，冗余节点为被移除后支配集诱导子图仍满足3-混合连通性、且全网节点均满足m重支配约束的节点，m为预设支配重数；循环遍历直至不存在可删减的冗余节点，输出能够抵御双节点失效、双边失效、点边混合失效中任意两类混合故障的(3,m)-混合连通支配集。

19、一种容错型混合连通支配集的应用，应用在多传输半径多通信模式无线传感器网络中，网络节点同时搭载两类通信模块，分别对应第一半径低功耗通信协议、第二半径广覆盖通信协议；将原始网络拓扑结构拆分为两层子图：第一半径协议诱导生成主要层网络子图，第二半径协议诱导生成备份层网络子图；第一半径小于第二半径；在主要层网络子图构建常规连通支配集作为日常传输主集合，在备份层网络子图采用上述方法构建的(3,m)-混合连通支配集作为故障备用集合；网络正常运行使用主要层支配集，主集合失效时切换至备份层混合连通支配集。

20、在主要层网络子图和备份层网络子图协同运行时增设跨层局部补全机制：实时监测主要层支配集连通状态，若仅局部出现失效、整体未断开，则调用备份层网络子图对应通信链路补充主集合；仅当主集合失效节点与链路总数量超过对应阈值时，全网完整切换至备份层混合连通支配集运行。

21、本发明的有益效果在于：

22、本发明提供的一种容错型混合连通支配集的构建方法，首先以具备基础2连通、m重支配特性的连通支配集作为初始拓扑基底，提前赋予网络基础抗单点、单链路故障的能力，降低后续容错加固的计算开销；然后按照双边、点边、双节点三类混合失效的固定顺序分层排查修复，针对每类故障薄弱结构单独拆分处理，依托完整原始全网拓扑寻找连通路径补充支配节点，系统性消除所有会造成混合失效断裂的拓扑隐患；最后，以节点度数升序的规则循环剔除无作用冗余支配节点，在保障3-混合连通、m重支配两大核心约束不变的前提下压缩支配集整体规模，避免骨干节点过多带来的能耗冗余，得到的(3,m)-混合连通支配集可兼容抵御任意两类点、边组合混合故障，相比传统仅适配单一故障类型的支配集，大幅提升野外传感网络在节点损毁、链路遮挡同步发生场景下的通信稳定性，同时兼顾骨干规模轻量化与全域混合容错双重优势。

23、本发明提供的一种容错型混合连通支配集的构建方法，首次将点边混合连通度引入连通支配集领域，构建了(3,m)-混合连通支配集，用统一的混合失效元素总数度量容错能力，可同时抵御双节点失效、双边失效、点边混合失效三类任意组合的混合故障，突破了传统连通支配集仅能应对单类型故障或固定组合故障的局限，适配真实复杂场景的混合失效环境。

24、本发明提供的一种容错型混合连通支配集的构建方法，基于故障概率的失效优先级修复机制，结合节点剩余能量、环境干扰、遮挡分布等实际场景因素计算失效风险，优先修复高风险失效，相较于传统固定顺序修复，本发明方法可在相同支配集规模下，显著降低高概率故障造成的骨干断裂风险，适合野外监测、灾害预警等真实部署场景。

25、本发明提供的一种容错型混合连通支配集的应用，应用在多传输半径多通信模式无线传感器网络中，针对传输半径最短、功耗较低的通信协议，在对应的主要层子网中构建正常连通支配集来减小支配集规模，保证通信过程中的高效率与低能耗；针对传输半径较长，覆盖范围更广的通信协议，在对应的备份层子网中使用(3,m)-混合连通支配集，以增强系统在节点和链路混合失效下的容错能力。