You are here

Planning the Deployment of Multiple Sinks and Relays in Wireless Sensor Networks


Lanny Sitanayah, Ken Brown, Cormac Sreenan

Publication Type: 
Refereed Original Article
Wireless sensor networks are subject to failures. Deployment planning should ensure that when a data sink or sensor node fails, the remaining network can still be connected, and so may require placing multiple sinks and relay nodes in addition to sensor nodes. For network performance requirements, there may also be path-length constraints for each sensor node. We propose four algorithms, Greedy-MSP and GRASP-MSP to solve the problem of multiple sink placement, and Greedy-MSRP and GRASP-MSRP for the problem of multiple sink and relay placement. Greedy-MSP and GRASP-MSP minimise the deployment cost, while ensuring that each sensor node in the network is double-covered, i.e. it has two length-constrained paths to two sinks. Greedy-MSRP and GRASP-MSRP deploys sinks and relays to minimise the deployment cost and to guarantee that all sensor nodes in the network are double-covered and noncritical. A sensor node is noncritical if upon its removal, all remaining sensor nodes still have length-constrained paths to sinks. We evaluate the algorithms empirically and show that these algorithms outperform the closely-related algorithms from the literature for the lowest total deployment cost.
Digital Object Identifer (DOI): 
Publication Status: 
Date Accepted for Publication: 
Tuesday, 15 July, 2014
Publication Date: 
Journal of Heuristics
National University of Ireland, Cork (UCC)
Open access repository: