Arshad Jhumka
Luca Mottola
Skip Abstract Section
Abstract
Wireless sensor networks (WSNs) are characterized by localized interactions, that is, protocols are often based on message exchanges within a node’s direct radio range. We recognize that for these protocols to work effectively, nodes must have consistent information about their shared neighborhoods. Different types of faults, however, can affect this information, severely impacting a protocol’s performance. We factor this problem out of existing WSN protocols and argue that a notion of neighborhood view consistency (NVC) can be embedded within existing designs to improve their performance. To this end, we study the problem from both a theoretical and a system perspective. We prove that the problem cannot be solved in an asynchronous system using any of Chandra and Toueg’s failure detectors. Because of this, we introduce a new software device called pseudocrash failure detector (PCD), study its properties, and identify necessary and sufficient conditions for solving NVC with PCDs. We prove that, in the presence of transient faults, NVC is impossible to solve with any PCDs, thus define two weaker specifications of the problem. We develop a global algorithm that satisfies both specifications in the presence of unidirectional links, and a localized algorithm that solves the weakest specification in networks of bidirectional links. We implement the latter atop two different WSN operating systems, integrate our implementations with four different WSN protocols, and run extensive micro-benchmarks and full-stack experiments on a real 90-node WSN testbed. Our results show that the performance significantly improves for NVC-equipped protocols; for example, the Collection Tree Protocol (CTP) halves energy consumption with higher data delivery.
- M. K. Aguilera and others. 2000. Failure detection and consensus in the crash recovery model. Distributed Computing 13, 2. Google Scholar
Digital Library
- B. Alpern and F. B. Schneider. 1985. Defining liveness. Information Processing Letters 21.Google Scholar
- H. Alwan and A. Agarwal. 2009. A survey on fault-tolerant routing techniques in wireless sensor networks. In Proceedings International Conference on Sensor Technologies and Applications. Google ScholarDigital Library
- E. Anagnostou and V. Hadzilacos. 1993. Tolerating transient and permanent failures. In Proceedings of the 7th International Workshop on Distributed Algorithms (WDAG’93). Google ScholarDigital Library
- A. Arora and others. 2004. A line in the sand: A wireless sensor network for target detection, classification, and tracking. Computer Networks 46, 5 (2004). Google ScholarDigital Library
- A. Arora and S. S. Kulkarni. 1998. Detectors and correctors: A theory of fault-tolerance components. In Proceedings of the 18th International Conference on Distributed Computing Systems (ICDCS’98). Google ScholarDigital Library
- N. Baccour and others. 2012. Radio link quality estimation in wireless sensor networks: A survey. ACM Transactions on Sensor Networks 8, 4. Google ScholarDigital Library
- L. Balzano and R. Nowak. 2007. Blind calibration of sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN’07). Google ScholarDigital Library
- G. Barrenetxea and others. 2008. The hitchhiker’s guide to successful wireless sensor network deployments. In Proceedings of the 6th Conference on Embedded Network Sensor Systems (SENSYS’08). Google ScholarDigital Library
- J. Beauquier and others. 1998. Transient fault detectors. In Proceedings of the 12th International Symposium on Distributed Computing (DISC’98). Google ScholarDigital Library
- J. Beauquier and S. Kekkonen-Moneta. 1997. On FTSS-solvable distributed problems. In Proceedings of the 16th Symposium on Principles of Distributed Computing (DISC’97). Google ScholarDigital Library
- J. Beutel and others. 2009. Operating a sensor network at 3500 m above sea level. In Proceedings of the 8th International Conference on Information Processing in Sensor Networks (IPSN’09). Google ScholarDigital Library
- N. Bhatti and L. Mottola. 2016. Efficient state retention for transiently-powered embedded sensing. In Proceedings of the 13th ACM International Conference on Embedded Wireless Systems and Networks (EWSN’16). Google ScholarDigital Library
- C. A. Boano and others. 2009. Controllable radio interference for experimental and testing purposes in wireless sensor networks. In Proceedings of the 4th International Workshop on Practical Issues in Building Sensor Network Applications (SENSEAPP’09).Google ScholarCross Ref
- B. J. Bonfils and P. Bonnet. 2003. Adaptive and decentralized operator placement for in-network query processing. In Proceedings of 2nd International Workshop on Information Processing in Sensor Networks (IPSN’03). Google ScholarDigital Library
- N. Burri, P. von Rickenbach, and R. Wattenhofer. 2007. Dozer: Ultra-low power data gathering in sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN’07). Google ScholarDigital Library
- Q. Cao, T. He, and T. Abdelzaher. 2007. uCast: Unified connectionless multicast for energy efficient content distribution in sensor networks. IEEE Transactions on Parallel and Distributed Systems 18, 2. Google ScholarDigital Library
- M. Cattani and others. 2014. Lightweight neighborhood cardinality estimation in dynamic wireless networks. In Proceedings of the 13th International Symposium on Information Processing in Sensor Networks (IPSN’14). Google ScholarDigital Library
- M. Ceriotti and others. 2009. Monitoring heritage buildings with wireless sensor networks: The Torre Aquila deployment. In Proceedings of the 8th International Conference on Information Processing in Sensor Networks (IPSN). Google ScholarDigital Library
- M. Ceriotti and others. 2011. Is there light at the ends of the tunnel? Wireless sensor networks for adaptive lighting in road tunnels. In Proceedings of the 10th International Conference on Information Processing in Sensor Networks (IPSN’11).Google Scholar
- T. D. Chandra and S. Toueg. 1996. Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43, 2. Google ScholarDigital Library
- Y. Chen and others. 2009. Surviving sensor network software faults. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (SOSP’09). Google ScholarDigital Library
- J. Choi, M. Kazandjieva, M. Jain, and P. Levis. 2009. The case for a network protocol isolation layer. In Proceedings of the 7th Conference on Embedded Networked Sensor Systems (SENSYS’09). Google ScholarDigital Library
- M. Cinque, A. Coronato, A. Testa, and C. Di Martino. 2013. A survey on resiliency assessment techniques for wireless sensor networks. In Proceedings of MobiWAC. Google ScholarDigital Library
- N. Cooprider and others. 2007. Efficient memory safety for TinyOS. In Proceedings of the 5th International Conference on Embedded Networked Sensor Systems (SENSYS’07). Google ScholarDigital Library
- A. Cornejo and others. 2014. Reliable neighbor discovery for mobile ad-hoc networks. Ad Hoc Networks 12. Google ScholarDigital Library
- P. Costa and others. 2007. Programming wireless sensor networks with the TeenyLime middleware. In Proceedings of the 8th ACM/USENIX International Middleware Conference. Google ScholarDigital Library
- S. Dawson-Haggerty and others. 2012. @Scale: Insights from a large, long-lived appliance energy WSN. In Proceedings of the 11th International Conference on Information Processing in Sensor Networks (IPSN’12). Google ScholarDigital Library
- C. Delporte-Gallet and others. 2005. Revisiting failure detection and consensus in omission failure environments. In Proceedings of ICTAC. Google ScholarDigital Library
- I. Demirkol and others. 2006. MAC protocols for wireless sensor networks: A survey. IEEE Communications Magazine 44, 4. Google ScholarDigital Library
- E. W. Dijkstra. 1974. Self stabilizing systems in spite of distributed control. Communications of the ACM 17, 11. Google ScholarDigital Library
- S. Dolev. 2000. Self-stabilization. MIT Press, Cambridge, MA. Google ScholarDigital Library
- A. Dunkels and others. 2004. Contiki - A lightweight and flexible operating system for tiny networked sensors. In Proceedings of 1st Workshop on Embedded Networked Sensors. Google ScholarDigital Library
- A. Dunkels and others. 2007a. An adaptive communication architecture for wireless sensor networks. In Proceedings of the 5th Conference on Networked Sensor Systems (SENSYS’07). Google ScholarDigital Library
- A. Dunkels and others. 2007b. Software-based on-line energy estimation for sensor nodes. In Proceedings of the 4th International Workshop on Embedded Networked Sensors. Google ScholarDigital Library
- A. Dunkels and others. 2011. Announcements: Efficient protocol concurrency in low-power wireless networks. In Proceedings of the European Conference on Wireless Sensor Networks (EWSN’11).Google Scholar
- S. Duquennoy and others. 2013. Let the tree bloom: Scalable opportunistic routing with ORPL. In Proceedings of the 11th Conference on Embedded Networked Sensor Systems (SENSYS’13). Google ScholarDigital Library
- P. Dutta and others. 2006. Trio: Enabling sustainable and scalable outdoor wireless sensor network deployments. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN’08). Google ScholarDigital Library
- P. Dutta and D. Culler. 2008. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications. In Proceedings of the 6th Conference on Embedded Network Sensor Systems (SENSYS’08). Google ScholarDigital Library
- D. Estrin and others. 1999. Next century challenges: Scalable coordination in sensor networks. In Proceedings of the 5th International Conference on Mobile Computing and Networking (MOBICOM’99). Google ScholarDigital Library
- F. Ferrari and others. 2011. Efficient network flooding and time synchronization with Glossy. In Proceedings of the 12th International Conference on Information Processing in Sensor Networks (IPSN’11).Google Scholar
- F. Ferrari and others. 2012. Low-power wireless bus. In Proceedings of the 10th Conference on Embedded Networked Sensor Systems (SENSYS’12). Google ScholarDigital Library
- N. Finne and others. 2008. Experiences from two sensor network deployments self-monitoring and self-configuration keys to success. In Proceedings of the International Conference on Wired/Wireless Internet Communications (WWIC’08). Google ScholarDigital Library
- R. Flury and R. Wattenhofer. 2007. Routing, anycast, and multicast for mesh and sensor networks. In Proceedings of the 5th International Conference on Embedded Networked Sensor Systems (SENSYS’07).Google Scholar
- F. C. Gärtner and S. Pleisch. 2002. Failure detection sequencers: Necessary and sufficient information about failures to solve predicate detection. In Proceedings of the 22nd Symposium on Principles of Distributed Computing (DISC’02). Google ScholarDigital Library
- O. Gnawali and others. 2009. Collection tree protocol. In Proceedings of the 8th International Conference on Embedded Networked Sensor Systems (SENSYS’09). Google ScholarDigital Library
- S. Guo, H. Zhang, Z. Zhong, J. Cheng, Q. Cao, and T. He. 2014. Detecting faulty nodes with data errors for wireless sensor networks. In ACM Transactions on Sensor Networks. Google ScholarDigital Library
- V. Handziski and others. 2006. TWIST: A scalable and reconfigurable testbed for wireless indoor experiments with sensor networks. In REALMAN. Google ScholarDigital Library
- M. Hansen and others. 2011. Unified broadcast in sensor networks. In Proceedings of the 10th International Conference on Information Processing in Sensor Networks (IPSN’11).Google Scholar
- J. Hill and others. 2000. System architecture directions for networked sensors. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’00). Google ScholarDigital Library
- T. W. Hnat and others. 2011. The hitchhiker’s guide to successful residential sensing deployments. In Proceedings of the 9th Conference on Embedded Networked Sensor Systems (SENSYS’11). Google ScholarDigital Library
- R. Huang and others. 2012. Real-world sensor network for long-term volcano monitoring: Design and findings. IEEE Transactions on Parallel and Distributed Systems 23. Google ScholarDigital Library
- C. Intanagonwiwat and others. 2002. Impact of network density on data aggregation in wireless sensor networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS’02). Google ScholarDigital Library
- O. Iova and others. 2013. Stability and efficiency of RPL under realistic conditions in wireless sensor networks. In Proceedings of the 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC’13).Google ScholarCross Ref
- V. Iyer and others. 2011. NetDetect: Neighborhood discovery in wireless networks using adaptive beacons. In Proceedings of the 5th International Conference on Self-Adaptive and Self-Organizing Systems (SASO’11). Google ScholarDigital Library
- A. Jhumka, M. Bradbury, and S. Saginbekov. 2014. Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks. Journal of Parallel and Distributed Computing 74, 1, 1789--1801. Google ScholarDigital Library
- A. Jhumka and L. Mottola. 2009. On consistent neighborhood views in wireless sensor networks. In Proceedings of the 28th International Symposium on Reliable Distributed Systems (SRDS’09). Google ScholarDigital Library
- A. Jhumka and L. Mottola. 2014. Neighborhood Monitoring and View Consistency Enforcement in Wireless Sensor Networks. Technical Report TR-2014-12, Politecnico di Milano (Italy). Retrieved June 11, 2016 from home.deib.polimi.it/mottola/techRep/trPoli2014-12.pdf.Google Scholar
- A. Kandhalu and others. 2010. U-connect: A low-latency energy-efficient asynchronous neighbor discovery protocol. In Proceedings of the 9th International Conference on Information Processing in Sensor Networks (IPSN’10). Google ScholarDigital Library
- A. S. M. Zahid Kausar and others. 2015. Energizing wireless sensor networks by energy harvesting systems: Scopes, challenges and approaches. Renewable and Sustainable Energy Reviews 38 (2015).Google Scholar
- M. Keller and others. 2012. How was your journey? Uncovering routing dynamics in deployed sensor networks with multi-hop network tomography. In Proceedings of the 10th Conference on Embedded Networked Sensor Systems (SENSYS’12). Google ScholarDigital Library
- S. Kim and others. 2007a. Flush: A reliable bulk transport protocol for multi-hop wireless networks. In Proceedings of the 5th International Conference on Embedded Networked Sensor Systems (SENSYS 07). Google ScholarDigital Library
- S. Kim and others. 2007b. Health monitoring of civil infrastructures using wireless sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN'07). Google ScholarDigital Library
- J. Ko and others. 2011. Beyond interoperability: Pushing the performance of Sensornet IP stacks. In Proceedings of the 11th International Conference on Embedded Networked Sensor Systems (SENSYS’11). Google ScholarDigital Library
- K. Langendoen and others. 2006. Murphy loves potatoes: Experiences from a pilot sensor network deployment in precision agriculture. In Proceedings of the 20th International Conference on Parallel and Distributed Processing (IPDPS’06). Google ScholarDigital Library
- K. Langendoen and N. Reijers. 2003. Distributed localization in wireless sensor networks: A quantitative comparison. Computer Nets. 43, 4. Google ScholarDigital Library
- M.-H. Lee and Y.-H. Choi. 2008. Fault detection of wireless sensor networks. Computer Communications Journal 31, 14, 3469--3475. Google ScholarDigital Library
- P. Levis and others. 2004. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In Proceedings of the 1st Conference on Networked Systems Design and Implementation (NSDI’04). Google ScholarDigital Library
- N. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann, San Mateo, CA. Google ScholarDigital Library
- A. Mahapatro and P. M. Khilar. 2013. Fault diagnosis in wireless sensor networks: A survey. IEEE Communications Surverys and Tutorials 15, 4 (2013).Google Scholar
- M. Maróti and others. 2004. The flooding time synchronization protocol. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SENSYS’04). Google ScholarDigital Library
- T. Masuzawa. 1995. A fault-tolerant and self-stabilizing protocol for topology problem. In Proceedings of the Workshop on Self-stabilizing Systems.Google Scholar
- W. P. McCartney and N. Sridhar. 2006. Abstractions for safe concurrent programming in networked embedded systems. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SENSYS’06). Google ScholarDigital Library
- L. Mottola and others. 2010. Not all wireless sensor networks are created equal: A comparative study on tunnels. ACM Transactions on Sensor Networks 7, 2. Google ScholarDigital Library
- L. Mottola and G. P. Picco. 2011. MUSTER: Adaptive energy-aware multi-sink routing in wireless sensor networks. IEEE Transactions on Mobile Computing 10, 12. Google ScholarDigital Library
- A. Munir, J. Antoon, and A. Gordon-Ross. 2015. Modeling and analysis of fault detection and fault tolerance in wireless sensor networks. ACM Transactions on Embedded Computing Systems 14, 1. Google ScholarDigital Library
- M. Nesterenko and A. Arora. 2002. Dining philosophers that tolerate malicious crashes. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS’02). Google ScholarDigital Library
- K. Ni and others. 2009. Sensor networks data fault types. ACM Transactions on Sensor Networks 5, 3.Google ScholarDigital Library
- F. Österlind and others. 2009. Sensornet checkpointing: Enabling repeatability in testbeds and realism in simulations. In Proceedings of the 6th European Conference on Wireless Sensor Networks (EWSN’09). Google ScholarDigital Library
- E. Ould-Ahmed-Vall, B. Ferri, and G. Riley. 2012. Distributed fault-tolerance for event detection using heterogeneous wireless sensor networks. IEEE Transactions on Mobile Computing 11, 12. Google ScholarDigital Library
- P. Pannuto and others. 2014. A networked embedded system platform for the post-mote era. In Proceedings of the 12th Conference on Embedded Network Sensor Systems (SENSYS’12). Google ScholarDigital Library
- L. Paradis and Q. Han. 2007. A survey of fault management in wireless sensor networks. Journal of Network and System Management 15, 2. Google ScholarDigital Library
- B. Pásztor and others. 2010. Selective reprogramming of mobile sensor networks through social community detection. In Proceedings of the 7th European Conference on Wireless Sensor Networks (EWSN’10). Google ScholarDigital Library
- J. Polastre and others. 2005. A unifying link abstraction for wireless sensor networks. In Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SENSYS’05). Google ScholarDigital Library
- D. Puccinelli and others. 2012. Broadcast-free collection protocol. In Proceedings of the 10th Conference on Embedded Network Sensor Systems. Google ScholarDigital Library
- B. Ransford and others. 2011. MementOS: System support for long-running computation on RFID-scale Devices. SIGARCH Computer Architecture News 39. Google ScholarDigital Library
- I. Rhee and others. 2008. Z-MAC: A hybrid MAC for wireless sensor networks. IEEE/ACM Transactions on Networking 16, 3. Google ScholarDigital Library
- K. Romer and J. Ma. 2009. PDA: Passive distributed assertions for sensor networks. In Proceedings of the 8th International Conference on Information Processing in Sensor Networks (IPSN’09). Google ScholarDigital Library
- A. Saifullah and others. 2010. Real-Time scheduling for WirelessHART networks. In Proceedings of the Real-Time Systems Symposium (RTSS’10). Google ScholarDigital Library
- A. Saifullah and others. 2011. End-to-end delay analysis for fixed priority scheduling in WirelessHART networks. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium (RTAS’11). Google ScholarDigital Library
- P. Santi. 2005. Topology control in wireless ad-hoc and sensor networks. Computing Surveys 37, 2. (2005). Google ScholarDigital Library
- T. Schmid and others. 2010. A case against routing-integrated time synchronization. In Proceedings of the 8th Conference on Embedded Networked Sensor Systems (SENSYS’10). Google ScholarDigital Library
- A. Sharma and others. 2007. On the prevalence of sensor faults in real-world deployments. In Proceedings of the International Conference on Sensor and Ad-hoc Communications and Networks (SECON’07).Google ScholarCross Ref
- A. Sharma, L. Golubchik, and R. Govindan. 2010. Sensor faults: Detection methods and prevalence in real-world datasets. ACM Transactions on Sensor Networks 6, 3. Google ScholarDigital Library
- W.-Z. Song and others. 2009. TreeMAC: Localized TDMA MAC protocol for real-time high data-rate sensor networks. Pervasive Mobile Computing 5, 6. Google ScholarDigital Library
- K. Srinivasan and others. 2010. An empirical study of low-power wireless. ACM Transaction on Sensor Networks 6, 2. Google ScholarDigital Library
- S. Sudevalayam and P. Kulkarni. 2011. Energy harvesting sensor nodes: Survey and implications. IEEE Communications Surveys Tutorials 13.Google Scholar
- B. Sundararaman and others. 2005. Clock synchronization for wireless sensor networks: A survey. Ad Hoc Networks 3, 3.Google ScholarCross Ref
- T. Voigt and F. Österlind. 2008. CoReDac: Collision-free command-response data collection. In Proceedings of the International Conference on Emerging Technologies and Factory Automation (ETFA).Google ScholarCross Ref
- G. Werner-Allen and others. 2006. Fidelity and yield in a volcano monitoring sensor network. In Proceedings of the7th Symposium on Operating Systems Design and Implementation (OSDI’06). Google ScholarDigital Library
- K. Whitehouse and others. 2004. Hood: A neighborhood abstraction for sensor networks. In Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services (MOBISYS’04). Google ScholarDigital Library
- M. Yu and others. 2007. Fault management in wireless sensor networks. IEEE Wireless Communications 14, 6. Google ScholarDigital Library
- D. Zhang and others. 2012. Acc: Generic on-demand accelerations for neighbor discovery in mobile applications. In Proceedings of the 10th Conference on Embedded Networked Sensor Systems (SENSYS’12). Google ScholarDigital Library
Index Terms
- Neighborhood View Consistency in Wireless Sensor Networks
Recommendations
Relay Node Placement in Wireless Sensor Networks
A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy ...
Sensor scheduling for p-percent coverage in wireless sensor networks
We study sensor scheduling problems of p-percent coverage in this paper and propose two scheduling algorithms to prolong network lifetime due to the fact that for some applications full coverage is not necessary and different subareas of the monitored ...
The optimization of sensor relocation in wireless mobile sensor networks
Wireless Sensor Networks (WSNs) have been an active research area these years due to their broad range of potential applications. Several research issues, which include energy-aware routing, sensor deployment problems, data aggregation, etc., have been ...
Comments