Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: K. Arvind, Probabilistic Clock Synchronization in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.474-487, May 1994 [doi>10.1109/71.282558]
• 2: Vineet Bafna , Piotr Berman , Toshihiro Fujito, A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, SIAM Journal on Discrete Mathematics, v.12 n.3, p.289-297, Sept. 1999 [doi>10.1137/S0895480196305124]
• 3: Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
• 4: Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
• 5: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 6: G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica, 20(2):151--174, 1998.
• 7: F. V. Fomin, S. Gaspers, and A. V. Pyatkin. Finding a Minimum Feedback Vertex Set in Time o(1.7548n). In IWPEC 2006: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, pages 184--191, 2006.
• 8: T. Gallai. Maximum-minimum sätze über graphen. Acta Mathematicae, Academiae Scientiarum Hungaricae, 9:395--434, 1958.
• 9: Saurabh Ganeriwal , Srdjan Čapkun , Chih-Chieh Han , Mani B. Srivastava, Secure time synchronization service for sensor networks, Proceedings of the 4th ACM workshop on Wireless security, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080793.1080809]
• 10: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 11: Saurabh Ganeriwal , Christina Pöpper , Srdjan Čapkun , Mani B. Srivastava, Secure Time Synchronization in Sensor Networks, ACM Transactions on Information and System Security (TISSEC), v.11 n.4, p.1-35, July 2008 [doi>10.1145/1380564.1380571]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, New York, NY, 2008
• 14: J. Hastad. Clique is Hard to Approximate within n^/1--ε. Acta Mathematics, 182:105--142, 2002.
• 15: Murtuza Jadliwala , Qi Duan , Jinhui Xu , Shambhu Upadhyaya, On extracting consistent graphs in wireless sensor networks, International Journal of Sensor Networks, v.2 n.3/4, p.149-162, June 2007 [doi>10.1504/IJSNET.2007.013195]
• 16: R. Karp. Complexity of Computer Computations, chapter Reducibility Among Combinatorial Problems, pages 85--104. Plenum Press, 1972.
• 17: Leonid Khachiyan , Endre Boros , Konrad Borys , Khaled Elbassioni , Vladimir Gurvich, Generating all vertices of a polyhedron is hard, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.758-765, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109640]
• 18: M. D. Lemmon , J. Ganguly , L. Xia, Model-based clock synchronization in networks with drifting clocks, Proceedings of the 2000 Pacific Rim International Symposium on Dependable Computing, p.177, December 18-20, 2000
• 19: H. Li, Y. Zheng, M. Wen, and K. Chen. A Secure Time Synchronization Protocol for Sensor Network, chapter Emerging Technologies in Knowledge Discovery and Data Mining, pages 515--526. Springer Berlin / Heidelberg, 2007.
• 20: H. Li, Y. Zheng, M. Wen, and K. Chen. A Secure Time Synchronization Protocol for Sensor Network, chapter Emerging Technologies in Knowledge Discovery and Data Mining, pages 515--526. Springer Berlin / Heidelberg, 2007.
• 21: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 22: D. Mills. Internet time synchronization: The network time protocol. In Global States and Time in Distributed Systems, IEEE Computer Society Press. 1994.
• 23: S. B. Moon , P. Skelly , D. Towsley, Estimation and Removal of Clock Skew from Network Delay Measurements, University of Massachusetts, Amherst, MA, 1998
• 24: P. P. Papadimitratos, M. Poturalski, P. Schaller, P. Lafourcade, D. Basin, S. Capkun, and J.-P. Hubaux. Secure Neighborhood Discovery: A Fundamental Element for Mobile Ad Hoc Networking. IEEE Communications Magazine, 46(2), 2008.
• 25: S. Ping. Delay Measurement Time Synchronization for Wireless Sensor Networks. Intel Research, IRB-TR-03-013, June 2003.
• 26: I. Razgon. Exact Computation of Maximum Induced Forest. In SWAT '06: Proceedings of the 10thScandinavian Workshop on Algorithm Theory, pages 160--171, 2006.
• 27: R. Read and R. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees. Networks, 5:237--252, 1975.
• 28: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 29: M. Sichitiu and C. Veerarittiphan. Simple, Accurate Time Synchronization for Wireless Sensor Networks. In WCNC 2003: Proceedings of the IEEE Wireless Communications and Networking Conference, pages 1266--1273, 2003.
• 30: H. Song, S. Zhu, and G. Cao. Attack-Resilient Time Synchronization for Wireless Sensor Networks. In MASS 2005: Proceedings of the 2nd IEEE International Conference on Mobile Ad Hoc and Sensor Systems, pages 765--772, 2005.
• 31: Kun Sun , Peng Ning , Cliff Wang, TinySeRSync: secure and resilient time synchronization in wireless sensor networks, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180439]
• 32: B. Sundararaman, U. Buy, and A. D. Kshemkalyani. Clock Synchronization in Wireless Sensor Networks: A Survey. Ad-Hoc Networks, 3(3):281--323, 2005.
• 33: Jana van Greunen , Jan Rabaey, Lightweight time synchronization for sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941353]
• 34: Y. Xianglan, Q. Wangdong, and F. Fei. ASTS: An Agile Secure Time Synchronization Protocol for Wireless Sensor Networks. In WiCom '07: Proceedings of the 3rd International Conference on Wireless Communications, Networking and Mobile Computing, pages 2808--2811, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Security, Theory

Keywords:
approximation algorithms, time synchronization, wireless sensor networks