Optimal relay node placement in delay constrained wireless sensor network design

Optimal relay node placement in delay constrained wireless sensor network design

0.00 Avg rating0 Votes
Article ID: iaor20141186
Volume: 233
Issue: 1
Start Page Number: 220
End Page Number: 233
Publication Date: Feb 2014
Journal: European Journal of Operational Research
Authors: ,
Keywords: design
Abstract:

The Delay Constrained Relay Node Placement Problem (DCRNPP) frequently arises in the Wireless Sensor Network (WSN) design. In WSN, Sensor Nodes are placed across a target geographical region to detect relevant signals. These signals are communicated to a central location, known as the Base Station, for further processing. The DCRNPP aims to place the minimum number of additional Relay Nodes at a subset of Candidate Relay Node locations in such a manner that signals from various Sensor Nodes can be communicated to the Base Station within a pre‐specified delay bound. In this paper, we study the structure of the projection polyhedron of the problem and develop valid inequalities in form of the nodecut inequalities. We also derive conditions under which these inequalities are facet defining for the projection polyhedron. We formulate a branch‐and‐cut algorithm, based upon the projection formulation, to solve DCRNPP optimally. A Lagrangian relaxation based heuristic is used to generate a good initial solution for the problem that is used as an initial incumbent solution in the branch‐and‐cut approach. Computational results are reported on several randomly generated instances to demonstrate the efficacy of the proposed algorithm.

Reviews

Required fields are marked *. Your email address will not be published.