Analysis of a clock synchronization protocol for wireless sensor networks

F. Heidarian, J. Schmaltz, F.W. Vaandrager

Research output: Contribution to journalArticleAcademicpeer-review

26 Citations (Scopus)

Abstract

The Dutch company Chess develops a wireless sensor network (WSN) platform using an epidemic communication model. One of the greatest challenges in the design is to find suitable mechanisms for clock synchronization. In this paper, we study a proposed clock synchronization protocol for the Chess platform. First, we model the protocol as a network of timed automata and verify various instances using the Uppaal model checker. Next, we present a full parametric analysis of the protocol for the special case of cliques (networks with full connectivity), that is, we give constraints on the parameters that are both necessary and sufficient for correctness. These results have been checked using the proof assistant Isabelle. We report on the exhaustive analysis of the protocol for networks with four nodes, and we present a negative result for the special case of line topologies: for any instantiation of the parameters, the protocol will eventually fail if the network grows. Keywords: Industrial application of formal methods; Clock synchronization algorithms; Timed automata; Model checking; Theorem proving; Wireless sensor networks
Original languageEnglish
Pages (from-to)87-105
Number of pages19
JournalTheoretical Computer Science
Volume413
Issue number1
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint Dive into the research topics of 'Analysis of a clock synchronization protocol for wireless sensor networks'. Together they form a unique fingerprint.

  • Cite this