Acta Metallurgica Sinica(English letters) ›› 2009, Vol. 16 ›› Issue (5): 62-70.doi: 10.1016/S1005-8885(08)60270-8

• Networks • 上一篇    下一篇

Reliability evaluation of wireless sensor networks using
an enhanced OBDD algorithm

肖宇峰,陈山枝,李昕,李玉宏   

  1. State Key Laboratory of Networking and Switching, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • 收稿日期:2008-12-11 修回日期:1900-01-01 出版日期:2009-10-30
  • 通讯作者: 肖宇峰

Reliability evaluation of wireless sensor networks using
an enhanced OBDD algorithm

XIAO Yu-feng, CHEN Shan-zhi, LI Xin, LI Yu-hong   

  1. State Key Laboratory of Networking and Switching, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2008-12-11 Revised:1900-01-01 Online:2009-10-30
  • Contact: XIAO Yu-feng

摘要:

An enhanced ordered binary decision diagram (EOBDD) algorithm is proposed to evaluate the reliability of wireless sensor networks (WSNs), based on the considerations of the common cause failure (CCF) and a large number of nodes in WSNs. The EOBDD algorithm analyzes the common cause event (CCE) and the network structure when CCE takes place according to the stochastic graph and the CCF model of WSNs. After constructing the ordered binary decision diagram (OBDD) of the original network with node expansion, it uses a set of OBDD variables (SOV) to guide reliability computations along this OBDD. The two steps about OBDD can decrease the cost of OBDD constructions and storage. Furthermore, the efficient OBDD structure and Hash tables can greatly decrease redundant computations of isomorphs. The experiment results show that the EOBDD can be used to evaluate the reliability of WSN efficiently.

关键词:

network;reliability,;ordered;binary;decision;diagram,;wireless;sensor;networks,;common;cause;failure,;common;cause;event

Abstract:

An enhanced ordered binary decision diagram (EOBDD) algorithm is proposed to evaluate the reliability of wireless sensor networks (WSNs), based on the considerations of the common cause failure (CCF) and a large number of nodes in WSNs. The EOBDD algorithm analyzes the common cause event (CCE) and the network structure when CCE takes place according to the stochastic graph and the CCF model of WSNs. After constructing the ordered binary decision diagram (OBDD) of the original network with node expansion, it uses a set of OBDD variables (SOV) to guide reliability computations along this OBDD. The two steps about OBDD can decrease the cost of OBDD constructions and storage. Furthermore, the efficient OBDD structure and Hash tables can greatly decrease redundant computations of isomorphs. The experiment results show that the EOBDD can be used to evaluate the reliability of WSN efficiently.

Key words:

network reliability;ordered binary decision diagram;wireless sensor networks;common cause failure;common cause event