On Augmented OBDD and Performability for Sensor Networks

摘要

The expected hop count (EHC) or performability of a wireless sensor network (WSN) with probabilistic node failures provides the expected number of operational nodes a message traverses from a set of sensors to reach its target station. This paper proposes a novel approach for computing the EHC of a practical communication model for WSN, k-of-all-sources to any-terminal (k-of-S,t). Techniques based on factoring and Boolean techniques solve the EHC when k=1 for |S| ≥1 However, they fail to scale with large WSN and are not useful for computing the EHC with k>1. To overcome these problems, we propose an Augmented Ordered Binary Decision Diagram (OBDD-A) approach, which obtains the EHC for all cases of (k-of-S, t). We use randomly generated wireless networks and grid networks having up to 4.6×10~(20) (s,t)-minpaths to generate results. Results show that OBDD-A can obtain the EHC for networks that are unsolvable with existing approaches.