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...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
RAMS Consultants
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/26257 |
| _version_ | 1848751934918361088 |
|---|---|
| author | Herrmann, Johannes Soh, Sieteng Rai, S. West, Geoffrey |
| author_facet | Herrmann, Johannes Soh, Sieteng Rai, S. West, Geoffrey |
| author_sort | Herrmann, Johannes |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T08:00:37Z |
| format | Journal Article |
| id | curtin-20.500.11937-26257 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:00:37Z |
| publishDate | 2010 |
| publisher | RAMS Consultants |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-262572017-01-30T12:52:33Z On augmented OBDD and performability for sensor networks Herrmann, Johannes Soh, Sieteng Rai, S. West, Geoffrey network reliability expected hop count many-to-one communication sensor network Binary decision diagram 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. 2010 Journal Article http://hdl.handle.net/20.500.11937/26257 RAMS Consultants fulltext |
| spellingShingle | network reliability expected hop count many-to-one communication sensor network Binary decision diagram Herrmann, Johannes Soh, Sieteng Rai, S. West, Geoffrey On augmented OBDD and performability for sensor networks |
| title | On augmented OBDD and performability for sensor networks |
| title_full | On augmented OBDD and performability for sensor networks |
| title_fullStr | On augmented OBDD and performability for sensor networks |
| title_full_unstemmed | On augmented OBDD and performability for sensor networks |
| title_short | On augmented OBDD and performability for sensor networks |
| title_sort | on augmented obdd and performability for sensor networks |
| topic | network reliability expected hop count many-to-one communication sensor network Binary decision diagram |
| url | http://hdl.handle.net/20.500.11937/26257 |