A Distributed Heuristic Algorithm for Delay Constrained Energy Efficient Routing in Wireless Sensor Networks

Trong-Thua Huynh, Cong-Hung Tran, Anh-Vu Dinh-Duc


Besides energy restriction, wireless sensor networks (WSNs) should be able to provide bounded end-to-end delay when they are used to support real-time applications such as early forest fire alarm systems. In this paper, we investigate the problem of finding the least energy consumption route subject to a delay constraint with low computational complexity in such networks. Based on the distance-vector routing approach, which has less computational complexity and message overhead, we propose a distributed heuristic algorithm called Delay Constrained Energy Efficient Routing (DCEER) in order to minimize the total energy consumption while meeting the end-to-end delay requirement. DCEER only requires a moderate amount of information at each sensor node and does not suffer from the excessive running time. We prove that our proposed algorithm always finishes within a finite time and the computation complexity is only O(n), where n is a divisor of the number of sensor nodes. By mathematical proof and simulation, we verify that DCEER is suitable for large-scale WSNs because the number of messages exchanged between sensor nodes are represented by a polynomial function. Furthermore, we evaluate our proposal to compare its performance with related protocols.

Full Text:



T. T. Huynh and C. S. Hong, “An energy* delay efficient multi-hop routing scheme for wireless sensor networks,” IEICE Transactions on Information and Systems, vol. 89, no. 5, pp. 1654–1661, 2006.

X. Zhang and L. Zhang, “Optimizing energy-latency trade-off in wireless sensor networks with mobile element,” in 16th IEEE International Conference on Parallel and Distributed Systems (ICPADS), 2010, pp. 534–541.

Y. Jin, D. Wei, A. Gluhak, and K. Moessner, “Latency and energy-consumption optimized task allocation in wireless sensor networks,” in IEEE Wireless Communication and Networking Conference, 2010, pp. 1–6.

R. Cohen and B. Kapchits, “Energy-delay optimization in an asynchronous sensor network with multiple gateways,” in 8th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2011, pp. 98–106.

T. T. Huynh, A.-V. Dinh-Duc, and C. H. Tran, “Energy efficient delay-aware routing in multi-tier architecture for wireless sensor networks,” in International Conference on Advanced Technologies for Communications (ATC), 2013, pp. 603–608.

T.-T. Huynh, C.-H. Tran, and A.-V. Dinh-Duc, “Delay-energy aware clustering multi-hop routing in wireless sensor networks,” in Information Science and Applications (ICISA). Springer, 2016, pp. 31–40.

K. Akkaya and I. Ari, “In-network data aggregation in wireless sensor networks,” in Handbook of Computer Networks: LANs, MANs, WANs, the Internet, and Global, Cellular, and Wireless Networks. Wiley Online Library, 2007, vol. 2, pp. 1131–1146.

O. Boyinbode, H. Le, A. Mbogho, M. Takizawa, and R. Poliah, “A survey on clustering algorithms for wireless sensor networks,” in 13th International Conference on Network-Based Information Systems (NBiS), 2010, pp. 358–364.

S. Rani and S. H. Ahmed, Multi-hop Routing in Wireless Sensor Networks: An Overview, Taxonomy, and Research Challenges. Springer, 2016, ch. 2, pp. 15–28.

O. Younis and S. Fahmy, “HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366–379, 2004.

K. Akkaya and M. Younis, “Energy and QoS aware routing in wireless sensor networks,” Cluster Computing, vol. 8, no. 2-3, pp. 179–188, 2005.

Q. Liang, D. Yao, and H. Liu, “Energy-Efficient and Delay-Constrained Routing for different services in Wireless Sensor Network.” Journal of Convergence Information Technology, vol. 7, no. 5, pp. 233–243, 2012.

S.-W. Han, I.-S. Jeong, and S.-H. Kang, “Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks,” Journal of Network and Computer Applications, vol. 36, no. 1, pp. 156–166, 2013.

J. Niu, L. Cheng, Y. Gu, J. Jun, and Q. Zhang, “Minimum-delay and energy-efficient flooding tree in asynchronous low-duty-cycle wireless sensor networks,” in IEEE wireless communications and networking conference (WCNC), 2013, pp. 1261–1266.

Q. Nadeem, M. B. Rasheed, N. Javaid, Z. Khan, Y. Maqsood, and A. Din, “M-GEAR: Gateway-based energy-aware multi-hop routing protocol for WSNs,” in 8th IEEE International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA), 2013, pp. 164–169.

D. L. Guidoni, F. S. H. Souza, J. Ueyama, and L. A. Villas, “RouT: a routing protocol based on topologies for heterogeneous wireless sensor networks,” IEEE Latin America Transactions, vol. 12, no. 4, pp. 812–817, 2014.

S. Bai, W. Zhang, G. Xue, J. Tang, and C. Wang, “DEAR: Delay-bounded energy-constrained adaptive routing in wireless sensor networks,” in 31st IEEE International Conference on Computer Communications (INFOCOM), 2012, pp. 1593–1601.

Y. Yao, Q. Cao, and A. V. Vasilakos, “EDAL: An energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks,” IEEE/ACM Transactions on Networking, vol. 23, no. 3, pp. 810–823, 2015.

O. Goldreich, P, NP, and NP-Completeness: The Basics of Computational Complexity. Cambridge University Press, 2010.

J. Xu, W. Liu, F. Lang, Y. Zhang, and C. Wang, “Distance measurement model based on RSSI in WSN,” Wireless Sensor Network, vol. 2, no. 8, pp. 606–611, 2010.

Castalia, Wireless Sensor Network Simulator (Latest version 3.2), https://castalia.forge.nicta.com.au/index.php/en/.

D. B. Johnson and D. A. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Mobile Computing. Springer, 1996, pp. 153–181.

DOI: http://dx.doi.org/10.21553/rev-jec.114

Copyright (c) 2017 REV Journal on Electronics and Communications

ISSN: 1859-378X

Copyright © 2011-2024
Radio and Electronics Association of Vietnam
All rights reserved