access icon free Optimal topological balancing strategy for performance optimisation of consensus-based clock synchronisation protocols in wireless sensor networks: a genetic algorithm-based approach

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.

Inspec keywords: genetic algorithms; communication complexity; protocols; wireless sensor networks; iterative methods; resource allocation; synchronisation; telecommunication network topology

Other keywords: genetic algorithm-based approach; optimal synchronisation error; virtual backbone; packet loss; NP-complete problem; message complexity; load balanced connected dominating set problem; wireless sensor network; energy consumption; optimal topological balancing strategy; consensus-based clock synchronisation protocol; extensive message exchange; CCS protocol; performance optimisation

Subjects: Optimisation techniques; Interpolation and function approximation (numerical analysis); Communication network design, planning and routing; Protocols; Wireless sensor networks

References

    1. 1)
      • 36. Prowler Simulator’, http//www.isis.vanderbilt.edu/projects/nest/prowler.
    2. 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. 110.
    3. 3)
    4. 4)
    5. 5)
    6. 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. 171177.
    7. 7)
    8. 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. 873880.
    9. 9)
    10. 10)
    11. 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. 16.
    12. 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. 18.
    13. 13)
      • 28. Yong, L., Lixin, G.: ‘On the Placement of Clock Reference Nodes for Time Synchronization in Sensor Networks’, rio.ecs.umass.edu.
    14. 14)
    15. 15)
    16. 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. 389392.
    17. 17)
    18. 18)
    19. 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. 125133.
    20. 20)
    21. 21)
    22. 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. 19.
    23. 23)
    24. 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. 78827887.
    25. 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. 147163.
    26. 26)
      • 3. Shivaratri, N., Singhal, M.: ‘Advanced concepts in operating system’ (TMH Press, 1994, 1st edn.).
    27. 27)
    28. 28)
    29. 29)
    30. 30)
    31. 31)
    32. 32)
    33. 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. 138149.
    34. 34)
      • 4. Jamalipour, A., Zheng, J.: ‘Wireless sensor network: a networking perspective’ (Willey-IEEE Press, 2009, 1st edn.).
    35. 35)
    36. 36)
    37. 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. 115.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-wss.2014.0063
Loading

Related content

content/journals/10.1049/iet-wss.2014.0063
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading