Skip to main content

Research Repository

Advanced Search

Energy-Aware Constrained Relay Node Deployment for Sustainable Wireless Sensor Networks

Djenouri, Djamel; Bagaa, Miloud


Miloud Bagaa


© 2016 IEEE. This paper considers the problem of communication coverage for sustainable data forwarding in wireless sensor networks, where an energy-aware deployment model of relay nodes (RNs) is proposed. The model used in this paper considers constrained placement and is different from the existing one-tiered and two-tiered models. It supposes two different types of sensor nodes to be deployed, i) energy rich nodes (ERNs), and ii) energy limited nodes (ELNs). The aim is thus to use only the ERNs for relaying packets, while ELN's use will be limited to sensing and transmitting their own readings. A minimum number of RNs is added if necessary to help ELNs. This intuitively ensures sustainable coverage and prolongs the network lifetime. The problem is reduced to the traditional problem of minimum weighted connected dominating set (MWCDS) in a vertex weighted graph. It is then solved by taking advantage of the simple form of the weight function, both when deriving exact and approximate solutions. Optimal solution is derived using integer linear programming (ILP), and a heuristic is given for the approximate solution. Upper bounds for the approximation of the heuristic (versus the optimal solution) and for its runtime are formally derived. The proposed model and solutions are also evaluated by simulation. The proposed model is compared with the one-tiered and two-tiered models when using similar solution to determine RNs positions, i.e., minimum connected dominating set (MCDS) calculation. Results demonstrate the proposed model considerably improves the network life time compared to the one-tiered model, and this by adding a lower number of RNs compared to the two-tiered model. Further, both the heuristic and the ILP for the MWCDS are evaluated and compared with a state-of-the-art algorithm. The results show the proposed heuristic has runtime close to the ILP while clearly reducing the runtime compared to both ILP and existing heuristics. The results also demonstrate scalability of the proposed solution.


Djenouri, D., & Bagaa, M. (2017). Energy-Aware Constrained Relay Node Deployment for Sustainable Wireless Sensor Networks. IEEE Transactions on Sustainable Computing, 2(1), 30-42.

Journal Article Type Article
Acceptance Date Feb 7, 2017
Online Publication Date Feb 13, 2017
Publication Date Mar 1, 2017
Deposit Date Jan 21, 2020
Publicly Available Date Jan 22, 2020
Journal IEEE Transactions on Sustainable Computing
Print ISSN 2377-3782
Electronic ISSN 2377-3782
Publisher Institute of Electrical and Electronics Engineers (IEEE)
Peer Reviewed Peer Reviewed
Volume 2
Issue 1
Pages 30-42
Keywords wireless sensor networks; energy harvesting; relays; data models; sensors; runtime; computational modeling; wireless sensor networks (mobile applications- computer applications); relay node placement; energy efficient deployment; energy harvesting
Public URL
Publisher URL


Energy-Aware Constrained Relay Node Deployment for Sustainable Wireless Sensor Networks (229 Kb)


Publisher Licence URL

Copyright Statement
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

You might also like

Downloadable Citations