张晓花，董荣胜

(桂林电子科技大学 计算机与信息安全学院，广西 桂林　541004)



基于OBDD的无线传感器网络可用度算法

张晓花，董荣胜

(桂林电子科技大学 计算机与信息安全学院，广西 桂林541004)

为降低传感器节点的能量消耗，提高无线传感器网络可用度，构建了可用度评估的离散概率模型，提出了一种符号A_OBDD算法。该算法利用马尔科夫链描述节点状态转移过程，实现了对节点可用度的动态评估，引入有序二叉决策图，有效缓解了“组合爆炸”。实验结果表明，WSN节点状态转移概率对可用度有较大影响，验证了A_OBDD算法可以有效评估WSN可用度。

无线传感器网络；可用度；能量约束；马尔科夫链；有序二叉决策图

近年来，无线传感器网络(wireless sensor networks，简称WSN)的研究大都集中在数据管理和可靠性方面，在工业应用中对可靠性有严格的要求。然而，WSN可用度也是系统评估其完成任务能力的一个重要参数。数据的成功传输不仅依赖网络的连通性，也依赖节点所处的状态。只有能够完成传输任务的路径才是可用路径。廉价的传感器节点由低电压电池提供能量，电池能量的有限性限制了其寿命。为了减少传感器节点能量的消耗，节点必须在活动和睡眠状态之间切换。

WSN可靠度计算是一个#P-hard问题[1-2]。传统的方法很难对大规模WSN可靠性进行有效评估。Chang等[3]以网络连通性作为网络正常工作与否的标准，通过使用有序二叉决策图(ordered binary decision diagrams，简称OBDD)表示网络状态、计算网络可靠性。文献[4-5]考虑边的容量约束……