An exact optimization approach for relay node location in wireless sensor networks

I study the problem of locating Relay nodes (RN) to improve the connectivity of a set

of already deployed sensor nodes (SN) in a Wireless Sensor Network (WSN). This is

known as the Relay Node Placement Problem (RNPP). In this problem, one or more

nodes called Base Stations (BS) serve as the collection point of all the information

captured by SNs. SNs have limited transmission range and hence signals are transmitted

from the SNs to the BS through multi-hop routing. As a result, the WSN

is said to be connected if there exists a path for from each SN to the BS through

which signals can be hopped. The communication range of each node is modeled

with a disk of known radius such that two nodes are said to communicate if their

communication disks overlap. The goal is to locate a given number of RNs anywhere

in the continuous space of the WSN to maximize the number of SNs connected (i.e.,

maximize the network connectivity). To solve this problem, I propose an integer

programming based approach that iteratively approximates the Euclidean distance

needed to enforce sensor communication. This is achieved through a cutting-plane

approach with a polynomial-time separation algorithm that identies distance violations.

I illustrate the use of my algorithm on large-scale instances of up to 75 nodes

which can be solved in less than 60 minutes. The proposed method shows solutions

times many times faster than an alternative nonlinear formulation.