Paper Info
Title
Towards a theory for securing time synchronization in wireless sensor networks
Abstract
Time synchronization in highly distributed wireless systems like sensor and ad hoc networks is extremely important in order to maintain a consistent notion of time throughout the network and to support the various timing-based applications. But, cheating behavior by the participating nodes in the network can severely jeopardize the accuracy of the associated time synchronization process. Despite recent advances in this direction, a key fundamental question still remains unanswered: Is it theoretically feasible to secure distributed time synchronization protocols, given complete (or global) time and time difference information in the network? In this paper, we attempt to answer this question with the help of sound mathematical modeling and analysis. We first formulate the problem of distributed time synchronization as a Constraint Satisfaction Problem (CSP) in a graph-based model of the network. Then, we prove that efficiently eliminating cheating behavior in distributed time synchronization protocols is combinatorially hard (NP-hard), i.e., it is highly unlikely that there exists an algorithm that solves, or even approximates, this problem in polynomial (in terms of total number of nodes) time. Due to this negative result for the general case, we focus on studying the problem for a special case of the graph-based model of the network, namely completely connected graphs. We derive an upper bound on the best possible solution quality for this problem, propose two polynomial-time approximation strategies, and present an empirical evaluation of their performance.
Year
DOI
Venue
2009
10.1145/1514274.1514303
WISEC
Keywords
Field
DocType
time difference information,special case,key fundamental question,wireless sensor network,cheating behavior,time synchronization protocol,associated time synchronization process,time synchronization,constraint satisfaction,general case,graph-based model,networks,graph theory,ad hoc network,connected graph,approximation algorithms,upper bound,wireless sensor networks,constraint satisfaction problem,mathematical model
Graph theory,Approximation algorithm,Polynomial,Computer science,Data synchronization,Computer network,Constraint satisfaction problem,Theoretical computer science,Wireless ad hoc network,Synchronization (computer science),Wireless sensor network,Distributed computing
Conference
Citations 
PageRank 
References 
3
0.54
27
Authors
4
Name
Order
Citations
PageRank
Murtuza Jadliwala126625.26
Qi Duan230.54
Shambhu J. Upadhyaya378169.61
Jinhui Xu466578.86