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

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

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Wireless Sensor Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


    1. 1)
      • 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.
    2. 2)
      • 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.
    3. 3)
      • 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.
    4. 4)
      • 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.
    5. 5)
      • 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.
    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)
      • 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.
    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)
      • 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.
    10. 10)
      • 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.
    11. 11)
      • 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.
    12. 12)
      • 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.
    13. 13)
      • 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.
    14. 14)
      • 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.
    15. 15)
      • 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.
    16. 16)
      • 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.
    17. 17)
      • 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.
    18. 18)
      • 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.
    19. 19)
      • 19. Yang, Y., Cardei, M.: ‘Delay-constrained energy-efficient routing in heterogeneous wireless sensor networks’, Int. J. Sens. Netw., 2010, 7, (4), pp. 236247.
    20. 20)
      • 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.
    21. 21)
      • 21. Ergen, S.C., Varaiya, P.: ‘Energy efficient routing with delay guarantee for sensor networks’, Springer J. Wirel. Netw., 2007, 13, (5), pp. 679690.
    22. 22)
      • 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.
    23. 23)
      • 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.
    24. 24)
      • 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.
    25. 25)
      • 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.
    26. 26)
      • 26. Eppstein, D.: ‘Finding the k shortest paths’, SIAM J. Comput., 1998, 28, (2), pp. 652673.
    27. 27)
      • 27. Sedgewick, R.: ‘Algorithms in C + +: graph algorithms’ (Pearson Education, 2002, 3rd edn.), ISBN 978-0-201-36118-6.
    28. 28)
      • 28. (Latest version 3.2). Castalia wireless sensor network simulator. Available at

Related content

This is a required field
Please enter a valid email address