A greedy distributed time synchronization algorithm for wireless sensor networks

被引：3

作者：

Cheng, King-Yip ^{[1
]}

Lui, King-Shan ^{[1
]}

Wu, Yik-Chung ^{[1
]}

Tam, Vincent ^{[1
]}

机构：

[1] Univ Hong Kong, Dept Elect & Elect Engn, Hong Kong, Hong Kong, Peoples R China

来源：

2008 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, PROCEEDINGS, VOLS 1-13 | 2008年

关键词：

D O I：

10.1109/ICC.2008.443

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, a distributed network-wise synchronization protocol is presented. The protocol employs Pairwise Broadcast Synchronization (PBS) in which sensors can be synchronized by merely overhearing the exchange of synchronization packets. We investigate how to minimize the number of PBS required to synchronize all nodes in a network. We show that the problem of finding the minimum number of PBS required is NP-complete. A distributed greedy algorithm is proposed. The protocol is tested by extensive simulations. Although the algorithm behind is heuristic-based, the performance is closed to the centralized algorithm. The message overhead is compared with that of Timing-Sync Protocol for Sensor Networks (TPSN).

引用

页码：2327 / 2331

页数：5

共 10 条

[1] Wireless sensor networks: a survey [J].

Akyildiz, IF ;

Su, W ;

Sankarasubramaniam, Y ;

Cayirci, E .

COMPUTER NETWORKS, 2002, 38 (04) :393-422

[2]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[3] Wireless sensor networks:: A new regime for time synchronization [J].

Elson, J ;

Römer, K .

ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2003, 33 (01) :149-154

[4] Fine-grained network time synchronization using reference broadcasts [J].

Elson, J ;

Girod, L ;

Estrin, D .

USENIX ASSOCIATION PROCEEDINGS OF THE FIFTH SYMPOSIUM ON OPERATING SYSTEMS DESIGN AND IMPLEMENTATION, 2002, :147-163

[5]

Estrin D., 1999, P MOBICOM, DOI DOI 10.1145/313451.313556

[6]

Ganeriwal S., 2003, International Conference on Embedded Networked Sensor Systems, P138, DOI DOI 10.1145/958491.958508

[7]

Karp R.M., 1972, Complexity of Computer Computations, P85, DOI DOI 10.1007/978-1-4684-2001-2_9

[8]

Maroti Miklos, 2004, P 2 INT C EMBEDDED N, P39, DOI DOI 10.1145/1031495.1031501

[9]

NOH KL, 2007, IEEE INT WORKSH THEO

[10]

Sichitiu ML, 2003, IEEE WCNC, P1266

← 1 →