Network-Wide Time Synchronization in Multi-Channel Wireless Sensor Networks

Jari Nieminen, Lijun Qian, Riku Jäntti

.

DOI: 10.4236/wsn.2011.32005                

Abstract

Recent advances in wireless sensor technology have enabled simultaneous exploitation of multiple channels in wireless sensor systems. In this paper, a novel time synchronization algorithm is proposed for multi- channel Wireless Sensor Networks (WSNs) called Multi-Channel Time Synchronization (MCTS) protocol. Time synchronization is critical for many WSN applications and enables efficient communications between sensor nodes along with intelligent spectrum access. Contrary to many existing protocols that do not exploit multi-channel communications, the protocol takes advantage of potential multiple channels and distributes the synchronization of different nodes to distinct channels and thus, reduces the convergence time of synchronization processes significantly.

Keywords

Time Synchronization, Multi-Channel Communications, Wireless Sensor Networks

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. Yick, B. Mukherjee and D. Ghosal, “Wireless Sensor Net-work Survey,” Computer Networks, Vol. 52, No. 12, August 2008, pp. 2292-2330. doi:10.1016/j.comnet.2008. 04.002
[2]	I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks, Vol. 38, No. 4, March 2002, pp. 393- 422. doi:10.1016/S1389-1286(01)00302-4
[3]	G. Zhou, J. Stan-kovic and S. Song, “Crowded Spectrum in Wireless Sensor Networks,” Proceedings of the Third Workshop on Embedded Networked Sensors, Cambridge, May 2006, pp. 1-5.
[4]	L. Stabellini and M. U. Javed, “Experimental Comparison of Dy-namic Spectrum Access Techniques for Wireless Sensor Net-works,” Proceedings of the IEEE 71st Vehicular Technology Conference, Taipei, May 2010, pp. 1-5.
[5]	O. B. Akan, O. B. Karli and O. Ergul, “Cognitive Radio Sensor Networks,” IEEE Network, Vol. 23, No. 4, July-August 2009, pp. 34-40.
[6]	S. Gao, L. Qian, D. R. Vaman and Q. Qu, “Energy Efficient Adaptive Modulation in Wireless Cognitive Radio Sensor Networks,” Proceedings of the IEEE International Conference on Communications, Glasgow, June 2007, pp. 3980-3986. doi:10.1109/ICC.2007.655
[7]	S. Gao, L. Qian and D. R. Vaman, “Distributed Energy Efficient Spectrum Access in Wireless Cognitive Radio Sensor Networks,” Proceedings of the IEEE Wireless Communications & Networking Conference, Las Vegas, March 2008, pp. 1442-1447.
[8]	V. Gungor and G. Hancke, “Industrial Wireless Sensor Networks: Challenges, Design Principles, and Technical Approaches,” IEEE Transac-tions on Industrial Electronics, Vol. 56, No. 10, October 2009, pp. 4258-4265. doi:10. 1109/TIE.2009.2015754
[9]	S. Chen, A. Dunkels, F. ?sterlind, T. Voigt and M. Johansson, “Time Synchronization for Predictable and Secure Data Collection in Wireless Sensor Networks,” Sixth Annual Mediterranean Ad Hoc Networking Workshop, Corfu, June 2007, pp. 165-172.
[10]	Y. Uchimura, T. Nasu and M. Takahashi, “Time Synchronized Wireless Sensor Network and Its Application to Building Vibration Measurement,” Proceedings of the 33rd Annual Conference of the IEEE Industrial Electronics Society, Taipei, November 2007, pp. 2633- 2638.
[11]	V. Krishnamur-thy, K. Fowler and E. Sazonov, “The Effect of Time Synchro-nization of Wireless Sensors on the Modal Analysis of Struc-tures,” Smart Materials and Structures, Vol. 17, August 2008, pp. 1-13.
[12]	J. Chen, S. T. Sheu and C.A. Yang, “A New Multichannel Access Protocol for IEEE 802.11 Ad Hoc Wire-less LANs,” Proceedings of the 14th International Symposium on Personal, Indoor and Mobile Radio Communications, Bei-jing, September 2003, Vol. 3, pp. 2291-2296.
[13]	J. So and N. H. Vaidya, “Multi-channel MAC for Ad Hoc Networks: Han-dling Multi-channel Hidden Terminals Using a Single Tran-sceiver,” Proceedings of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing, Tokyo, May 2004, pp. 222-233.
[14]	J. Elson and K. R?mer, “Wireless Sensor Networks: A New Regime for Time Synchronization,” ACM SIGCOMM Computer Communication Review, Vol. 33, No. 1, January 2003, pp. 149-154. doi:10.1145/774763.774 787
[15]	D. L. Mills, “Internet Time Synchronization: The Network Time Protocol,” IEEE Transactions on Communica-tions, Vol. 39, No. 10, October 1991, pp. 1482-1493. doi:10.1109/26.103043
[16]	K. R?mer, “Time Synchronization in Ad Hoc Networks,” Proceedings of the 2nd ACM In-ternational Symposium on Mobile Ad Hoc Networking and Computing, Long Beach, October 2001, pp. 173-182. doi:10.1145/501416.501440
[17]	J. Elson, L. Girod and D. Estrin, “Fine-Grained Network Time Synchronization using Reference Broadcasts,” Proceedings of the 5th Symposium on Operating Systems Design and Implementations, Boston, De-cember 2002, pp. 147-163. doi:10.1145/1060289.1060304
[18]	S. Ganeriwal, R. Kumar and M. B. Srivastava, “Timing-sync Protocol for Sensor Net-works,” Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems, Los Angeles, November 2003, pp. 138-149.
[19]	M. Maróti, B. Kusy, G. Simon and A. Lédeczi, “The Flooding Time Synchronization Protocol,” Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems, Baltimore, November 2004, pp. 39-49. doi:10.1145/1031495.1031501
[20]	W. Su and I. F. Akyildiz, “Time-Diffusion Synchronization Protocol for Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, Vol. 13, No. 2, April 2005, pp. 384-397. doi:10.1109/TNET.2004.842228
[21]	Y. W. Hong and A. A. Scaglione, “A Scalable Synchronization Protocol for Large Scale Sensor Networks and Its Applications,” IEEE Journal on Selected Areas in Communications, Vol. 23, No. 5, May 2005, pp. 1085- 1099. doi:10.1109/JSAC.2005.845418
[22]	K. L. Noh, E. Serpedin and K. A. Qaraqe, “New Approach for Time Synchronization in Wireless Sensor Networks: Pairwise Broadcast Synchronization,” IEEE Transactions on Wireless Communications, Vol. 7, No. 9, September 2008, pp. 3318-3322. doi:10.1109/TWC.2008. 070343
[23]	K. L. Noh, Y. C. Wu, K. Qaraqe and B. W. Suter, “Extension of Pairwise Broadcast Clock Synchronization for Multicluster Sensor Net-works,” EURASIP Journal on Advances in Signal Processing, Vol. 2008, 2008, pp. 1- 10. doi:10.1155/2008/286168
[24]	H. S. W. So, G. Nguyen and J. Walrand, “Practical Synchronization Techniques for Multi-Channel MAC,” Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, Los Angeles, September 2006, pp. 134-145.
[25]	J. Nieminen, R. J?ntti and L. Qian,”Time Synchronization of Cognitive Radio Networks”, IEEE Global Communications Conference, Honolulu, December 2009, pp. 1-6.
[26]	S. Yoon, C. Veerarittiphan and M. L. Sichitiu, “Tiny-sync: Tight Time Synchronization for Wireless Sensor Networks,” ACM Transaction on Sensor Networks, Vol. 3, no. 2, June 2007, pp. 1-34.
[27]	M. Lemmon, J. Ganguly and L. Xia, “Model-based Clock Synchronization in Networks with Drifting Clocks,” Proceedings of the Pacific Rim International Symposium on Dependable Computing, Los Angeles, December 2000, pp. 177-184. doi:10.1109/PRDC.2000.897300
[28]	S. L. Wu, C. Y. Lin, Y. C. Tseng and J. L. Sheu, “A New Multi-channel MAC Protocol with On-demand Channel Assignment for Multi-hop Mobile Ad Hoc Networks,” Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, Dallas/Richard- son, December 2000, pp. 232-237.
[29]	S. Y. Shin, H. S. Park and W. H. Kwon, “Mutual Interference Analysis of IEEE 802.15.4 and IEEE 802.11b,” Computer Networks, Vol. 51, No. 12, August 2007, pp. 3338-3353. doi:10.1016/j.comnet.2007.01.034
[30]	M. Petrova, L. Wu, P. M?h?nen and J. Riihijarvi, “Interference Measurements on Performance Degradation between Colocated IEEE 802.11g/n and IEEE 802.15.4 Networks,” Proceedings of the Sixth Inter-national Conference on Networking, Sainte-Luce, April 2007, pp. 93- 98.
[31]	E. M. Royer and C. E. Perkins, “Multicast Operations of the Ad-hoc On-Demand Distance Vector Routing Protocol,” Proceedings of the Fifth Annual ACM/IEEE Interna-tional Conference on Mobile Computing and Networking, Seattle, August 1999, pp. 207-218. doi:10.1145/ 313451.313538
[32]	N. Malpani, J. Welch and N. Vaidya, “Leader Election Algorithms for Mobile Ad Hoc Networks,” Proceedings of the Fourth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Commu-nications, Boston, August 2000, pp. 96-103.
[33]	K. P. Hatzis, G. P. Pentaris, P. G. Spirakis, V. T. Tampakas and R. B. Tan, “Fundamental Control Algorithms in Mobile Networks,” Pro-ceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, Bar Harbor, July 1999, pp. 251-260. doi:10.1145/ 305619.305649
[34]	S. Vasudevan, J. Kurose and D. Towsley, “Design and Analysis of a Leader Election Algorithm for Mobile Ad Hoc Networks,” Proceedings of the 12th IEEE International Conference on Network Protocols, Berlin, October 2004, pp. 350-360. doi:10.1109/ICNP.2004.1348124
[35]	E. Minieka, “The m-Center Problem,” SIAM Review, Vol. 12, No. 1, January 1970, pp. 138-139. doi:10.1137/1012 016
[36]	M. S. Daskin, “A New Approach to Solving the Vertex p-center Problem to Optimality: Algorithm and Computational Results,” Commu-nications of the Operations Research Society of Japan, Vol. 49, No. 9, 2000, pp. 428- 436.
[37]	D. Hochbaum and D. Shmoys, “A Best Possible Heuristic for the k-Center Problem,” Mathe-matics of Operations Research, Vol. 10, No. 2, May 1985, pp. 180-184. doi:10.1287/moor.10.2.180
[38]	J. Mihelic and B. Robic, “Approximation Algorithms for the k-center Problem: An Experimental Evaluation,” Proceedings of Operations Research, 2002, pp. 1-6.
[39]	N. Megiddo, “The Weighted Euclidean 1-center Problem,” Mathematics of Operations Research, Vol. 8, No. 4, November 1983, pp. 14-25. doi:10.1287/moor.8.4.498
[40]	S. Guha and S. Khuller, “Ap-proximation Algorithms for Connected dominating Sets,” Al-gorithmica, Vol. 20, No. 4, April 1998, pp. 374-387. doi:10.1007/PL00009201
[41]	J. Wu and H. Li, “On Calculat-ing Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks,” Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, August 1999, pp. 7-14.
[42]	P. J. Wan, K. M. Alzoubi and O. Frieder, “Distri-buted Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” Proceedings of the 21st IEEE International Conference on Computer Communications, New York, June 2002, pp. 1597-1604.