Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Exact and approximate algorithms for clustering problem in wireless sensor networks

© The Institution of Engineering and Technology
Received 13/05/2019, Accepted 21/10/2019, Revised 02/10/2019, Published 30/10/2019

Clustering is an effective method for improving the network lifetime and the overall scalability of a wireless sensor network. The problem of balancing the load of the cluster heads is called load-balanced clustering problem (LBCP), which is an NP-hard problem. In this study, the authors use parameterised complexity to cope with this NP-hard problem. The authors show that LBCP can be solved by a k-additive approximation algorithm with a running time of , where k is an upper bound on the maximum load assigned to the cluster heads and n is the input size. Also, LBCP is FPT with respect to the maximum load of the sensor nodes and the number of sensor nodes. The authors propose an fpt-algorithm with respect to these parameters for this problem. In addition, they prove that LBCP is when the number of the cluster heads is selected as the parameter.

Inspec keywords: telecommunication network reliability; pattern clustering; communication complexity; wireless sensor networks; optimisation; resource allocation; approximation theory

Other keywords: load-balanced clustering problem; FPT algorithm; wireless sensor network; LBCP; NP-hard problem; network lifetime; k-additive approximation algorithm; parameterised complexity

Subjects: Wireless sensor networks; Reliability; Interpolation and function approximation (numerical analysis); Optimisation techniques

References

    1. 1)
      • 8. Kuila, P., Jana, P.K.: ‘Energy efficient clustering and routing algorithms for wireless sensor networks: particle swarm optimization approach’, Eng. Appl. Artif. Intell., 2014, 33, pp. 127–140.
    2. 2)
      • 12. Gupta, S.K., Jana, P.K.: ‘Energy efficient clustering and routing algorithms for wireless sensor networks: Ga based approach’, Wirel. Pers. Commun., 2015, 83, (3), pp. 2403–2423.
    3. 3)
      • 13. Kuila, P., Jana, P.K.: ‘A novel differential evolution based clustering algorithm for wireless sensor networks’, Appl. Soft Comput., 2014, 25, pp. 414–425.
    4. 4)
      • 25. Kannan, R.: ‘Minkowski's convex body theorem and integer programming’, Math. Oper. Res., 1987, 12, (3), pp. 415–440.
    5. 5)
      • 7. Yarinezhad, R., Hashemi, S.N.: ‘An efficient data dissemination model for wireless sensor networks’, Wirel. Netw., 2019, 25, (6), pp. 3419–3439.
    6. 6)
      • 10. Kuila, P., Gupta, S.K., Jana, P.K.: ‘A novel evolutionary approach for load balanced clustering problem for wireless sensor networks’, Swarm Evol. Comput., 2013, 12, pp. 48–56.
    7. 7)
      • 4. Sucasas, V., Radwan, A., Marques, H., et al: ‘A survey on clustering techniques for cooperative wireless networks’, Ad Hoc Netw., 2016, 47, pp. 53–81.
    8. 8)
      • 26. Gramm, J., Niedermeier, R., Rossmanith, P., et al: ‘Fixed-parameter algorithms for closest string and related problems’, Algorithmica, 2003, 37, (1), pp. 25–42.
    9. 9)
      • 3. Sha, K., Gehlot, J., Greve, R.: ‘Multipath routing techniques in wireless sensor networks: a survey’, Wirel. Pers. Commun., 2013, 70, (2), pp. 1–23.
    10. 10)
      • 21. Yarinezhad, R., Hashemi, S.N.: ‘Solving the load balanced clustering and routing problems in wsns with an fpt-approximation algorithm and a grid structure’, Pervasive Mob. Comput., 2019, 58, p. 101033.
    11. 11)
      • 16. Yarinezhad, R., Hashemi, S.N.: ‘A cellular data dissemination model for wireless sensor networks’, Pervasive Mob. Comput., 2018, 48, pp. 118–136.
    12. 12)
      • 18. Gupta, G.P., Jha, S.: ‘Integrated clustering and routing protocol for wireless sensor networks using cuckoo and harmony search based metaheuristic techniques’, Eng. Appl. Artif. Intell., 2018, 68, pp. 101–109.
    13. 13)
      • 14. Randhawa, S., Jain, S.: ‘Mlbc: multi-objective load balancing clustering technique in wireless sensor networks’, Appl. Soft Comput., 2019, 74, pp. 66–89.
    14. 14)
      • 9. Kuila, P., Jana, P.K.: ‘Approximation schemes for load balanced clustering in wireless sensor networks’, J. Supercomput., 2014, 68, (1), pp. 87–105.
    15. 15)
      • 29. Lampis, M., Mitsou, V.: ‘The computational complexity of the game of set and its theoretical applications’. Latin American Symp. on Theoretical Informatics (LATIN), Montevideo, Uruguay, 2014, 8394, 24–34.
    16. 16)
      • 17. Kaur, S., Mahajan, R.: ‘Hybrid meta-heuristic optimization based energy efficient protocol for wireless sensor networks’, Egypt. Inf. J., 2018, 19, (3), pp. 145–150.
    17. 17)
      • 6. Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: ‘Energy-efficient communication protocol for wireless microsensor networks’. Proc. 33rd Annual Hawaii Int. Conf. on System Sciences, Maui, USA, 2000, p. 10.
    18. 18)
      • 19. Azharuddin, M., Jana, P.K.: ‘PSO-based approach for energy-efficient and energy-balanced routing and clustering in wireless sensor networks’, Soft Comput., 2017, 21, (22), pp. 6825–6839.
    19. 19)
      • 27. Karmarkar, N., Karp, R.M.: ‘An efficient approximation scheme for the one-dimensional bin-packing problem’. 23rd Annual Symp. on Foundations of Computer Science (SFCS 1982), Chicago, USA, 1982, pp. 312–320.
    20. 20)
      • 1. Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., et al: ‘Wireless sensor networks: a survey’, Comput. Netw., 2002, 38, (4), pp. 393–422.
    21. 21)
      • 15. Yarinezhad, R.: ‘Reducing delay and prolonging the lifetime of wireless sensor network using efficient routing protocol based on mobile sink and virtual infrastructure’, Ad Hoc Netw., 2019, 84, pp. 42–55.
    22. 22)
      • 24. Lenstra, H.W.Jr: ‘Integer programming with a fixed number of variables’, Math. Oper. Res., 1983, 8, (4), pp. 538–548.
    23. 23)
      • 23. Downey, R.G., Fellows, M.R.: ‘Fundamentals of parameterized complexity’, vol. 4 (Springer, London, UK, 2013).
    24. 24)
      • 2. Curry, R.M., Smith, J.C.: ‘A survey of optimization algorithms for wireless sensor network lifetime maximization’, Comput. Ind. Eng., 2016, 101, pp. 145–166.
    25. 25)
      • 22. Flum, J., Grohe, M.: ‘Parameterized complexity theory’ (Springer Science & Business Media, Berlin, Germany, 2006).
    26. 26)
      • 28. De La Vega, W.F., Lueker, G.S.: ‘Bin packing can be solved within 1+ε in linear time’, Combinatorica, 1981, 1, (4), pp. 349–355.
    27. 27)
      • 20. Yarinezhad, R., Hashemi, S.N.: ‘A routing algorithm for wireless sensor networks based on clustering and an fpt-approximation algorithm’, J. Syst. Softw., 2019, 155, pp. 145–161.
    28. 28)
      • 11. Low, C.P., Fang, C., Ng, J.M., et al: ‘Efficient load-balanced clustering algorithms for wireless sensor networks’, Comput. Commun., 2008, 31, (4), pp. 750–759.
    29. 29)
      • 5. Manap, Z., Ali, B.M., Ng, C.K., et al: ‘A review on hierarchical routing protocols for wireless sensor networks’, Wirel. Pers. Commun., 2013, 72, (2), pp. 1077–1104.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2019.0510
Loading

Related content

content/journals/10.1049/iet-com.2019.0510
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address