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

access icon free Delay constraint energy-efficient routing based on Lagrange relaxation in wireless sensor networks

Most of researches on wireless sensor network (WSN) are focused on how to reduce energy consumption to increase the network lifetime. There are few researches solving the problem of energy optimization ensuring delay constraint. Whereas, the delay is important factor for applications that require delay-sensitive data. Several works have been published to balance the energy consumption and delay. They achieved many different results but each proposal has certain limitations. Some proposals have high computational and messaging complexity. Some others have not found the optimal solution. In this study, we investigate in finding solution to improve the energy efficiency of sensor nodes satisfying end-to-end delay to transmit data from sensor nodes to sink in multi-hop WSNs. Based on Lagrange relaxation method, we propose an aggregate cost function between energy consumption and delay as well as an efficient method to find the optimal multiplier for that objective function. We provide two algorithms to find paths with least energy consumption while maintaining end-to-end delay requirement from any sensor node to sink. Besides analyzing the complexity and convergence of the algorithm, the simulation results also show that the proposed algorithm achieved good balance between energy consumption and delay compared with the previous proposals.

References

    1. 1)
      • 22. Bai, S., Zhang, W., Xu, G., et al: ‘DEAR: delay-bounded energy-constrained adaptive routing in wireless sensor networks’, Proc. IEEE INFOCOM, FL, USA, 2012, pp. 15931601.
    2. 2)
      • 16. Huynh, T.T., Hong, C.S.: ‘An energy*delay efficient multi-hop routing scheme for wireless sensor networks’, IEICE Trans. Inf. Syst., 2006, E89-D, (5), pp. 16541661.
    3. 3)
      • 5. Huynh, T. T., Duc, A. V. D., Tran, C. H.: ‘Energy efficient delay-aware routing in multi-tier architecture for wireless sensor networks’. IEEE Int. Conf. Advanced Technologies for Communications, Hochiminh City, Vietnam, 2013, pp. 439444.
    4. 4)
      • 15. Durresi, A., Paruchuri, V., Barolli, L.: ‘Delay-energy aware routing protocol for sensor and actor networks’. The 11th Int. Conf. Parallel and Distributed Systems, Fukuoka, Japan, 2005, pp. 292298.
    5. 5)
      • 11. Munir, M. F., Kherani, A. A., Filali, F.: ‘Distributed algorithm for minimizing delay in multi-hop wireless sensor networks’. The Seventh IEEE Int. Symp. Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Seoul, Korea, 2009, pp. 19.
    6. 6)
      • 6. Sun, Y., Sun, J., Zhao, F., et al: ‘Delay constraint multipath routing for wireless multimedia ad hoc networks’, Int. J. Commun. Syst., 2016, 29, (1), pp. 210225.
    7. 7)
      • 12. Kumar, D., Patel, R. B.: ‘Multi-hop data communication algorithm for clustered wireless sensor networks’, Int. J. Distrib. Sens. Netw., 2011, 2011, p. 10, doi: 10.1155/2011/984795, Article ID 984795.
    8. 8)
      • 8. Cheng, C.-T., Leung, H., Maupin, P.: ‘A delay-aware network structure for wireless sensor networks with in-network data fusion’, IEEE Sens. J., 2013, 13, (5), pp. 16221631.
    9. 9)
      • 4. Cheng, C.-T., Tse, C. K., Lau, F. C. M.: ‘A delay-aware data collection network structure for wireless sensor networks’, IEEE Sens. J., 2011, 11, (3), pp. 699710.
    10. 10)
      • 26. Eppstein, D.: ‘Finding the k shortest paths’, SIAM J. Comput., 1998, 28, (2), pp. 652673.
    11. 11)
      • 19. Yang, Y., Cardei, M.: ‘Delay-constrained energy-efficient routing in heterogeneous wireless sensor networks’, Int. J. Sens. Netw., 2010, 7, (4), pp. 236247.
    12. 12)
      • 28. (Latest version 3.2). Castalia wireless sensor network simulator. Available at https://castalia.forge.nicta.com.au/index.php/en/.
    13. 13)
      • 9. Neamatollahi, P., Taheri, H., Naghibzadeh, M., et al: ‘A distributed clustering scheme for wireless sensor networks’. Sixth IEEE Int. Conf. Information and Knowledge Technology, Shahrood, Iran, 2014, pp. 2024.
    14. 14)
      • 20. Do, T. D., Nguyen, Q. D., Kim, D.-S.: ‘GRATA: gradient-based traffic-aware routing for wireless sensor networks’, IET J. Wirel. Sens. Syst., 2013, 3, (2), pp. 104111, doi: 10.1049/iet-wss.2012.0083.
    15. 15)
      • 1. Wang, X., Wang, X., Liu, L, et al: ‘DutyCon: a dynamic duty-cycle control approach to end-to-end delay guarantees in wireless sensor networks’, ACM Trans. Sens. Netw., 2013, 9, (4), pp. 133, article no. 42.
    16. 16)
      • 24. Han, S.-W., Jeong, I.-S., Kang, S.-H.: ‘Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks’, J. Netw. Comput. Appl., 2013, 36, (1), pp. 156166.
    17. 17)
      • 14. Chen, S., Nahrstedt, K.: ‘An overview of quality of service routing for next-generation high-speed networks: problems and solutions’, IEEE J. Mag. Netw., 1998, 12, (6), pp. 6479.
    18. 18)
      • 17. Shahraki, A., Rafsanjani, M.K., Saeid, A.B.: ‘A new approach for energy and delay trade-off intra-clustering routing in WSNs’, Elsevier Int. J. Comput. Math. Appl., 2011, 62, (4), pp. 16701676.
    19. 19)
      • 23. Yao, Y., Cao, Q., Vasilakos, A. V.: ‘EDAL: an energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks’, IEEE/ACM Trans. Netw., 2015, 23, (3), pp. 810823.
    20. 20)
      • 10. Anindita, R., Debashis, D.: ‘Energy efficient clustering protocol based on K-means (EECPK-means)-midpoint algorithm for enhanced network lifetime in wireless sensor network’, IET J. Wirel. Sens. Syst., 2016, 6, (6), pp. 181191, doi: 10.1049/iet-wss.2015.0087.
    21. 21)
      • 25. Niu, J., Cheng, L., Gu, Y., et al: ‘Minimum-delay and energy-efficient flooding tree in asynchronous low-duty-cycle wireless sensor networks’, IEEE Wireless Communications and Networking Conf., Shanghai, China, 2013, pp. 12611266.
    22. 22)
      • 27. Sedgewick, R.: ‘Algorithms in C + +: graph algorithms’ (Pearson Education, 2002, 3rd edn.), ISBN 978-0-201-36118-6.
    23. 23)
      • 2. Tang, L., Guan, Q., Jiang, S., et al: ‘A deadline-aware and distance-aware packet scheduling algorithm for wireless multimedia sensor networks’, Int. J. Distrib. Sens. Netw., 2015, 2015, pp. 18, doi: 10.1155/2015/803123, article ID 803123.
    24. 24)
      • 13. Huynh, T.T., Tran, C. H., Duc, A. V. D.: ‘Delay-energy aware clustering multi-hop routing in wireless sensor networks’, Inf. Sci. Appl. Lect. Notes Electr. Eng. Springer, 2016, 376, pp. 3140.
    25. 25)
      • 7. Le, H. N., Zalyubovskiy, V., Choo, H.: ‘Delay-minimized energy-efficient data aggregation in wireless sensor networks’. Proc. IEEE INFOCOM, Sanya, China, 2012, pp. 401407.
    26. 26)
      • 18. Pothuri, P. K., Sarangan, V., Thomas, J. P.: ‘Delay-constrained, energy-efficient routing in wireless sensor networks through topology control’. IEEE Int. Conf. Networking, Sensing and Control, FL, USA, 2006, pp. 3541.
    27. 27)
      • 3. Dao, T.-N., Yoon, S., Kim, J.: ‘A Deadline-aware scheduling and forwarding scheme in wireless sensor networks’, J. Sens., 2016, 16, (59), pp. 117, doi: 10.3390/s16010059.
    28. 28)
      • 21. Ergen, S.C., Varaiya, P.: ‘Energy efficient routing with delay guarantee for sensor networks’, Springer J. Wirel. Netw., 2007, 13, (5), pp. 679690.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-wss.2017.0038
Loading

Related content

content/journals/10.1049/iet-wss.2017.0038
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address