论文部分内容阅读
网络可靠性评估是无线传感器网络(Wireless Sensor Networks, WSN)设计和优化的核心步骤,但现有的WSN可靠度求解模型没有考虑WSN在通信时延、不完全覆盖(ImPerfect Coverage,IPC)、和共因失效(Common Cause Failures,CCF)等方面区别于普通网络的特征;同时,针对多状态WSN系统状态空间规模随节点数量增多而产生的“组合爆炸”问题,基于多值决策图(Multi-valued Decision Diagram,MDD)的多状态系统评估方法在降低状态组合复杂度方面性能较高,但因需要完成最小路集枚举,计算量会随路集数量增多呈指数级增长。针对上述问题,本文构建了一个同时考虑节点时延、不完全覆盖和共因失效的多状态WSN模型,并给出了基于多状态多值决策图(Multi-state Multi-valued Decision Diagram,MMDD)的多状态WSN可靠度求解算法。主要成果如下: (1)构建了节点三态的WSN形式化模型,分析了时延约束下三态WSN可靠度求解过程及其复杂度,并给出了求解时延约束下三态WSN可靠性的MMDD符号算法。算法通过MMDD自定义操作对三态WSN进行按需构建,避免枚举所有路径。实验结果显示,对多态WSN性能特征和失效模式综合建模更接近现实情况,只考虑链路传输时延的WSN建模会高估WSN的可靠性,而且给出的MMDD算法的空间复杂度和时间复杂度均低于Robert给出的MDD算法。 (2)同时考虑IPC和CCF对3态WSN可靠性的影响,将网络性能和故障特性综合在一个模型下分析,给出CCF和IPC共同影响下的三态WSN可靠度MMDD求解算法。该算法充分利用MMDD的结构优势,只需要创建一个MMDD便可根据共因集计算WSN可靠度,不仅能准确计算IPC和CCF影响下三态WSN的可靠性,并且具有较高的空间存储效率。实验结果表明,给出的MMDD求解算法可以完成受IPC、CCF和时延约束的WSN可靠性评估任务,而且计算得到的可靠度值低于忽略网络拥塞以及IPC、CCF影响的WSN模型求解结果。 (3)从通信能力、数据传输能力和容错性能三个角度,分析比较了树形、网状和簇形拓扑结构的三态WSN可靠度随时延约束值、网络流量大小、覆盖因子、共因数量等指标变化的情况,为无线网设计以及不同应用下WSN拓扑选择提供了较全面的信息。