Milen Nikolov

Fig. 1: A scenario of relay node splacement in the context of a smart home. Blue nodes are relay and the red are already placed devices whose positions are fixed.
Fig. 2: A sample network topology of 4 fixed nodes and 2 relay nodes. The solutions obtained by algorithms (Euclidean and Generalized Steiner trees) used in recent works are not optimal. The optimal solution is found as characterized in our framework; our RePlace algorithm obtains it here.

Fig. 3: Our heuristic solution (blue) overlaps with the optimal solution (red). The computation of the colored polygons is part of the solution algorithm and is described in our upcoming manuscript. The black points represent Monte Carlo samples again utilized in our solution to increase RePlace's implementaiton efficiency.

Networks of wireless sensors have been deployed to monitor various physical processes, ranging from measuring soil moisture for precision agriculture to monitoring power consumption in buildings. In many of these applications, network's lifetime depends on the network communication efficiency. For instance, higher number of packet retransmissions leads to drastically reduced network lifetime, crucially affecting the success or failure of applications' deployment. An important factor driving the number of packet retransmission is network's links quality. The weaker the signal, the higher the number of packet retransmissions until information is conveyed.

To improve links' quality and decrease communication cost in wireless networks, researchers and practitioners often rely on the deployment of relay nodes (see Fig. 1). Relay nodes do not introduce new traffic in the network and only retransmit packets received from a set of source nodes.

Given a set of n fixed source nodes, along with their locations and traffic demands, and a budget of k relay nodes, the problem posed is to find the optimal locations of the k relay nodes minimizing the communication cost in the network. In recent years a number of projects and research works have attempted to tackle this optimizatopm placement problem. Unfortunately, the majority of the attempts do not succeed in modeling the problem accurately. This leads to certain inefficiencies, as shown in Fig. 2, for example. We model accurately the placement optimization problem, prove that the algorithm finding the optimal solution is intractable, and provide an efficient heuristic. See, for instance, Fig. 3 where our heuristic finds the same solution as the optimal algorithm on typical network instances.