论文部分内容阅读
无线传感器网络(Wireless Sensor Networks, WSN)在军事、医疗和环境健康监测等领域具有重要的应用价值,而可靠性评估是其走向实际应用的关键步骤。受节点状态的组合复杂性制约,当网络规模较大时,WSN可靠性计算会产生组合爆炸问题。决策图技术是缓解或者部分程度上避免组合爆炸问题的一种有效方法。有序二叉决策图(Ordered Binary Decision Diagram, OBDD)及代数决策图(Algebraic Decision Diagram, ADD)以其可以实现状态空间或变量组合的隐式表示及搜索的特性,已被广泛应用于网络可靠性分析中。WSN通信模式可以归为两大类:基础设施通信和应用通信,而基础设施通信下又有三种数据传输模式:单播、组播和广播。本文从基础设施通信出发,基于决策图技术,对单播和组播模式下WSN可靠性展开了研究。主要成果有: (1)针对单播模式下忽略节点的能量消耗从而导致过高评估可靠性水平的问题,引入Heinzelman的能量消耗模型,构建了单播模式下WSN形式化模型。通过节点的二进制编码,对该模型进行符号ADD表示,实现了单播模式下WSN的压缩存储。针对组播模式,构建了组播模式下WSN形式化模型。利用二进制编码技术,结合OBDD对该模型进行符号表述,实现了组播模式下WSN状态信息的高效存储,为可靠性分析算法的设计提供了一个紧凑高效的存储结构。 (2)在单播模式下WSN符号ADD表示的基础上,给出可靠性分析的符号ADD_Unicast算法。该算法利用自定义操作“AndPlus”、“MinOr”构建可靠性函数的ADD,有效降低了WSN可靠性分析的复杂性。通过与AboElFotoh的factoring算法进行实验对比,结果表明ADD_Unicast算法避免了同构子网的冗余计算,具有更高的运行效率,相对于AboElFotoh的factoring算法,ADD_Unicast算法适合处理更大规模WSN可靠性问题。 (3)在组播模式下WSN符号OBDD表示的基础上,给出评估WSN可靠性的符号OBDD_Multicast算法。该算法利用OBDD的“与”和“或”操作,结合节点扩展技术,构建组播下WSN可靠性函数的OBDD。通过识别相邻节点的冗余路径和s-t非连通冗余路径,避免冗余扩展,减少中间子网的个数,进一步降低了WSN可靠性分析的复杂性。最后,针对3×n型网络,与Xing的OBDD算法进行实验对比,结果表明OBDD_Multicast算法具有较少的时间开销,相对于Xing的OBDD算法, OBDD_Multicast算法能够有效分析组播下更大规模WSN的可靠性。