Formal Reliability Analysis of Wireless Sensor Network Data Transport Protocols using HOL

摘要

In recent times, Wireless Sensor Networks (WSNs) have shown a great potential for monitoring physical or environmental conditions in a variety of safety and financialcritical applications, ranging from medicine to transportation and surveillance. Given the extreme conditions of most of the WSN environments, it is very important to make WSN communication resilient to network failures. Various data transport protocols have been proposed in the literature to serve this purpose. The reliability of these WSN data transport protocols is usually assessed by using Reliability Block Diagrams (RBDs). Traditionally, RBD-based reliability analyses of WSN data transport protocols is done using paper-and-pencil proofs or computer simulations, which cannot ascertain absolute correctness due to their inherent incompleteness. As a complementary approach, we propose to use the higher-order-logic theorem prover HOL to conduct the RBD-based reliability analysis of WSN data transport protocols. In particular, the paper provides a higher-order-logic formalization of series, parallel and parallel-series RBDs. These RBDs are then used to do the formal reliability analysis of the end-to-end (e2e) data transport mechanism, and the Event to Sink Reliable Transport (ESRT) and Reliable Multi-Segment Transport (RMST) data transport protocols.