基于2-可诊断CDS的WSN骨干构建算法

王哲; 尹吉嵩; 梁新宇; 牛佳豪

doi:10.13624/j.cnki.issn.1001-7445.2025.1219

广西大学学报（自然科学版） ›› 2025, Vol. 50 ›› Issue (06) : 1219 -1233. DOI: 10.13624/j.cnki.issn.1001-7445.2025.1219

基于2-可诊断CDS的WSN骨干构建算法

王哲, 尹吉嵩, 梁新宇, 牛佳豪

作者信息 +

Author information +

文章历史 +

PDF

摘要

在无线传感器网络(WSN)中构建虚拟骨干(VB)可以有效减少路由节点数量，从而延长网络寿命及有效避免广播风暴，通常，将异质WSN抽象为圆盘图G,其对应的VB抽象为连通控制集(CDS)。现有研究多通过构建容错VB应对节点故障且失效的场景，却忽略了节点故障但未失效这一关键情况。基于PMC(Preparata, Metze和Chien)模型，提出一种在异质WSN中构建具有故障诊断结构的VB近似构建算法。首先，引入t-可诊断连通控制集(t-DCDS)的概念以及拓扑约束，并针对t=2的情况，分析2-可诊断CDS(2-DCDS)所需的结构条件；其次，利用两段式的方法在G中构建CDS并通过构造生成树，将叶子节点在G中的部分邻居加入CDS中，使其满足2-DCDS结构条件，验证算法的正确性并计算其近似比。结果表明，所提算法在CDS规模、运行时间、能量消耗和故障诊断性能等方面具有一定的优势。