用OBDD算法评估无线传感网的可靠度和结点重要性  

Evaluate the reliability and node importance of wireless sensor networks with OBDD algorithm

作　　者：肖宇峰[1,2] 陈山枝[3] 李昕[1] 李玉宏[1] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室宽带网研究中心,北京100876 [2]西南科技大学信息工程学院,绵阳621010 [3]电信科学技术研究院无线移动通信国家重点实验室,北京100083

出　　处：《高技术通讯》2009年第12期1245-1250,共6页Chinese High Technology Letters

基　　金：国家自然科学基金(60672086);863计划(2007AA01Z2A1)资助项目

摘　　要：基于有序二叉判定图(OBDD),提出用结点扩张(NE)算法来评估无线传感网的可靠度和结点重要性。NE算法执行结点扩张操作来处理不可靠结点,从两方面增强了计算效率:利用OBDD结构表示网络状态,减少了大量冗余的等价状态;利用Hash表存储同构子网的OBDD,减少了同构子网的重复计算。另外,该算法对结点重要性进行了评估,为脆弱结点的保护提供参考。实验结果表明NE算法的计算开销比传统的factoring算法低,能有效评估无线传感网的可靠度。The paper proposes an ordered binary decision diagram （OBDD） algorithm, named the node expansion （NE） algo- rithm to evaluate the reliability and node importance of wireless sensor networks. This algorithm executes node expansion to deal with unreliable nodes and enhances the reliability computations from two points： firstly, the OBDD representation of network states avoids large numbers of redundant equivalent states; secondly, the Hash table of isomorphic sub-net- works decreases the repeated computations of same structure networks. Furthermore, the NE algorithm evaluates the node importance and guides the protection of weak nodes. The experiment shows that the NE algorithm＇ s computation costs are lower than the factoring algorithm＇ s and it can efficiently evaluate the reliability of wireless sensor networks.

关 键 词：无线传感网 网络可靠度 有序二叉判定图(OBDD) 因子分解 

分 类 号：TP212.9[自动化与计算机技术—检测技术与自动化装置] TN929.5[自动化与计算机技术—控制科学与工程]