On augmented OBDD and performability for sensor networks
|dc.identifier.citation||Herrmann, Johannes and Soh, Sieteng and Rai, Suresh and West, Geoffrey. 2010. On augmented OBDD and performability for sensor networks. International Journal of Performability Engineering. 6 (4): pp. 305-316.|
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| greater than/equal to 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.6x1020 (s,t)-minpaths to generate results. Results show that OBDD-A can obtain the EHC for networks that are unsolvable with existing approaches.
|dc.subject||expected hop count|
|dc.subject||Binary decision diagram|
|dc.title||On augmented OBDD and performability for sensor networks|
|dcterms.source.title||International Journal of Performability Engineering|
|curtin.department||Department of Computing|