Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-35873-9_30
Title: State space reduction for sensor networks using two-level partial order reduction
Authors: Zheng, M.
Sanań, D.
Sun, J.
Liu, Y.
Dong, J.S. 
Gu, Y.
Issue Date: 2013
Citation: Zheng, M.,Sanań, D.,Sun, J.,Liu, Y.,Dong, J.S.,Gu, Y. (2013). State space reduction for sensor networks using two-level partial order reduction. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7737 LNCS : 515-535. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-35873-9_30
Abstract: Wireless sensor networks may be used to conduct critical tasks like fire detection or surveillance monitoring. It is thus important to guarantee the correctness of such systems by systematically analyzing their behaviors. Formal verification of wireless sensor networks is an extremely challenging task as the state space of sensor networks is huge, e.g., due to interleaving of sensors and intra-sensor interrupts. In this work, we develop a method to reduce the state space significantly so that state space exploration methods can be applied to a much smaller state space without missing a counterexample. Our method explores the nature of networked NesC programs and uses a novel two-level partial order reduction approach to reduce interleaving among sensors and intra-sensor interrupts. We define systematic rules for identifying dependence at sensor and network levels so that partial order reduction can be applied effectively. We have proved the soundness of the proposed reduction technique, and present experimental results to demonstrate the effectiveness of our approach. © Springer-Verlag 2013.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/78358
ISBN: 9783642358722
ISSN: 16113349
DOI: 10.1007/978-3-642-35873-9_30
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Nov 8, 2018

Page view(s)

25
checked on Aug 3, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.