Date Added: Aug 2012
Wireless sensor networks are subject to failures. Deployment planning should ensure that when a 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 sensors. For network performance requirements, there may also be path-length constraints for each sensor node. The authors propose two local search algorithms, GRASP-MSP and GRASP-MSRP, to solve the problem of multiple sink placement and the problem of multiple sink and relay placement, respectively. GRASP-MSP minimizes 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.