© The Institution of Engineering and Technology
Consensus-based clock synchronisation (CCS) protocols have gained recent attention in wireless sensor networks. However, the well-known and state-of-the-art protocols are ‘all node based’, that is, every node iterates the consensus algorithm to reach to the synchronised state by exchanging synchronisation messages with the neighbours. This increases the congestion in the network because of extensive message exchanges and induces packet losses and delay in the network. Hence, it is desirable that a subset of connected sensors along with a balanced number of neighbouring sensors should be selected to form a logical topology which will serve as a virtual backbone for the CCS algorithm. This will minimise the overall message complexity and energy consumption in the network as well as balances and minimises delay for faster consensus convergence with optimal synchronisation error. This problem is claimed to be a generalisation of Load Balanced Connected Dominating Set problem which is recently proved to be NP-complete. To make the problem tractable, a genetic algorithm-based strategy is proposed to select the synchronising nodes to form an optimal logical topology.
References
-
-
1)
-
36. ‘Prowler Simulator’, .
-
2)
-
25. Zhou, H., Liang, T., Xu, C., Xie, J.: ‘Multiobjective coverage control strategy for energy-efficient wireless sensor networks’, Int. J. Distrib. Sens. Netw., 2012, 1, pp. 1–10.
-
3)
-
1. Ranganathan, P., Nygard, K.: ‘Time synchronization in wireless sensor networks: a survey’, Int. J. Ubicomp (IJU), 2010, 1, (2), pp. 92–102 (doi: 10.5121/iju.2010.1206).
-
4)
-
6. Ding, R., Wu, J., Jiao, L.: ‘Average time synchronization in wireless sensor networks using pairwise messages’, Complet Commun., 2012, 35, (2), pp. 221–233 (doi: 10.1016/j.comcom.2011.09.007).
-
5)
-
R. Olfati-Saber ,
R.M. Murray
.
Consensus problems in networks of agents with switching topology and time-delays.
IEEE Trans. Autom. Control
,
9 ,
1520 -
1533
-
6)
-
17. Lee, S.H., Choi, L.: ‘Chaining clock synchronization: an energy-efficient clock synchronization scheme for wireless sensor networks’. Proc. Tenth Int. Symp. on Pervasive Systems, Algorithms and Networks, 2009, pp. 171–177.
-
7)
-
29. Xiong, G., Kishore, S.: ‘Analysis of distributed consensus time synchronization with Gaussian delay over wireless sensor networks’, EURASIP J. Wirel. Commun. Netw., 2009, 1, pp. 1–8 (doi: 10.1155/2009/623537).
-
8)
-
11. Dou, L.H., Gan, M.G., Chen, J., Yu, M.: ‘A fast averaging synchronization algorithm for clock oscillators in nonlinear dynamical network with arbitrary time-delays’, Acta Autom. Sinica, 2010, 36, (6), pp. 873–880.
-
9)
-
23. Djenouri, D.: ‘R4sync: relative referenceless receiver/receiver time synchronization in wireless sensor networks’, IEEE Signal Process. Lett., 2012, 19, (4), pp. 175–178 (doi: 10.1109/LSP.2012.2185491).
-
10)
-
12. Shen, X., Choi, B.J., Liang, H., Zhuang, W.: ‘DCS: distributed asynchronous clock synchronization in delay tolerant network’, IEEE Trans. Parallel Distrib. Syst., 2012, 23, (3), pp. 491–504 (doi: 10.1109/TPDS.2011.179).
-
11)
-
37. Nawab, F., Jamshaid, K., Shihada, B., Ho, P.H.: ‘TMAC: Time stamp ordered MAC for CSMA/CA wireless mesh networks’. Proc. IEEE ICCCN'11, 2011, pp. 1–6.
-
12)
-
27. Ratnaparkhe, T., Natekar, S., Chandan, S., Sadaphal, V.P.: ‘Selection of time synchronizing nodes in wireless sensor network’. Proc. IEEE conf. on COMSNETS, 2010, pp. 1–8.
-
13)
-
28. Yong, L., Lixin, G.: ‘On the Placement of Clock Reference Nodes for Time Synchronization in Sensor Networks’, .
-
14)
-
34. Jiguo, Y., Wang, N., Wang, G., Yu, D.: ‘Connected dominating sets in wireless ad hoc and sensor networks a comprehensive survey’, Complet Commun., 2013, 36, (2), pp. 121–134 (doi: 10.1016/j.comcom.2012.10.005).
-
15)
-
19. Yigitler, H., Mahmood, A., Virrankoski, R., Jantti, R.: ‘Recursive clock skew estimation for wireless sensor networks using reference broadcasts’, IET Wirel. Sens. Syst., 2012, 2, (4), pp. 338–350 (doi: 10.1049/iet-wss.2011.0137).
-
16)
-
26. Kuk, Y., Lee, M.G., Jung, K.K., et al: ‘Optimum sensor nodes deployment using fuzzy C-means algorithm’. Proc. ISCCS'11, 2011, pp. 389–392.
-
17)
-
14. Sarwate, A.D., Scaglione, A., Aysal, T.C., Yildiz, M.E.: ‘Broadcast gossip algorithms for consensus’, IEEE Trans. Signal Process., 2009, 57, (7), pp. 2748–2761 (doi: 10.1109/TSP.2009.2016247).
-
18)
-
13. Seatzu, C., Franceschelli, M., Giua, A.: ‘Distributed averaging in sensor networks based on broadcast gossip algorithms’, IEEE Sens. J., 2011, 11, (3), pp. 808–817 (doi: 10.1109/JSEN.2010.2064295).
-
19)
-
18. Nett, E., Mock, M., Frings, R., Trikaliotis, S.: ‘Continuous clock synchronization in wireless real time application’. Proc. 19th IEEE Symp. on Reliable Distributed Systems, October 2000, pp. 125–133.
-
20)
-
33. He, J., Ji, S., Pan, Y., et al: ‘Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks’, Theor. Comput Sci., 2013, 507, (0), pp. 2–16 (doi: 10.1016/j.tcs.2012.11.020).
-
21)
-
5. Mahapatro, A., Khilar, M.P.: ‘Energy-efficient distributed approach for clustering-based fault detection and diagnosis in image sensor networks’, IET Wirel. Sens. Syst., 2013, 3, (1), pp. 26–36 (doi: 10.1049/iet-wss.2011.0125).
-
22)
-
21. Qaraqe, K., Noh, K.L., Wu, Y.C., Suter, B.: ‘Extension of pairwise broadcasting clock synchronization for multi-cluster sensor networks’. EURASIP, 2008, pp. 1–9.
-
23)
-
K. Noh ,
E. Serpedin ,
K. Qaraqe
.
A new approach for time synchronization in wireless sensor networks: pairwise broadcast synchronization.
IEEE Trans. Wirel. Commun.
,
9 ,
3318 -
3322
-
24)
-
9. Cheng, L., Shi, J., Chen, J., He, P.: ‘Time synchronization in WSNs: a maximum value based consensus approach’. Proc. 50th IEEE Conf. on Decision and Control and European Control, 12–15 December 2011, pp. 7882–7887.
-
25)
-
15. Girod, L., Elson, J., Estrin, D.: ‘Fine-grained network time synchronization using reference broadcasts’. Proc. Fifth USENIX Symp. on Operating System Design and Implementation, December 2002, pp. 147–163.
-
26)
-
3. Shivaratri, N., Singhal, M.: ‘Advanced concepts in operating system’ (TMH Press, 1994, 1st edn.).
-
27)
-
Q. Li ,
D. Rus
.
Global clock synchronization in sensor networks.
IEEE Trans. Comput.
,
2 ,
214 -
226
-
28)
-
N. Freris ,
S. Graham ,
P. Kumar
.
Fundamental limits on synchronizing clocks over networks.
IEEE Trans. Autom. Control
,
6 ,
1352 -
1364
-
29)
-
32. Chu, S., Wei, P., Zhong, X., et al: ‘Deployment of a connected reinforced backbone network with a limited number of backbone nodes’, IEEE Trans. Mob. Comput., 2013, 12, (6), pp. 1188–1200 (doi: 10.1109/TMC.2012.88).
-
30)
-
Y. Zou ,
K. Chakrabarty
.
A distributed coverage- and connectivity-centric technique for selecting active nodes in wireless sensor networks.
IEEE Trans. Comput.
,
8 ,
978 -
991
-
31)
-
4. Schenato, L., Fiorentin, F.: ‘Average TimeSynch: a consensus-based protocol for clock synchronization in wireless sensor networks’, Automatica, 2011, 47, (9), pp. 1878–1886 (doi: 10.1016/j.automatica.2011.06.012).
-
32)
-
35. Kuila, P., Gupta, S.K., Jana, P.K.: ‘A novel evolutionary approach for load balanced clustering problem for wireless sensor network’, Swarm Evol. Comput., 2013, 12, pp. 48–56 (doi: 10.1016/j.swevo.2013.04.002).
-
33)
-
16. Srivastava, M.B., Ganeriwal, S., Kumar, R.: ‘Timing-sync protocol for sensor networks’. Proc. First ACM Conf. on Embedded Networked Sensor Systems, 2003, pp. 138–149.
-
34)
-
4. Jamalipour, A., Zheng, J.: ‘Wireless sensor network: a networking perspective’ (Willey-IEEE Press, 2009, 1st edn.).
-
35)
-
K. Cheng ,
K. Lui ,
Y. Wu ,
V. Tam
.
A distributed multihop time synchronization protocol for wireless sensor networks using pairwise broadcast synchronization.
IEEE Trans. Wirel. Commun.
,
4 ,
1764 -
1772
-
36)
-
14. M K Maggs, M.K., O’Keefe, S.G., Thiel, D.V.: ‘Consensus clock synchronization for wireless sensor networks’, IEEE Sensors J., 2012, 12, (6), pp. 2269–2277 (doi: 10.1109/JSEN.2011.2182045).
-
37)
-
31. Ryu, J., Yu, J., Noel, E., et al: ‘Borel Cayley graph-based topology control for consensus protocol in wireless sensor networks’. ISRN Sensor Networks, 2013, pp. 1–15.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-wss.2014.0063
Related content
content/journals/10.1049/iet-wss.2014.0063
pub_keyword,iet_inspecKeyword,pub_concept
6
6