Optimal relay placement in multi-hop wireless networks

Relay node placement in wireless environments is a research topic recurrently studied in the specialized literature. A variety of network performance goals, such as coverage, data rate and network lifetime, are considered as criteria to lead the placement of the nodes. In this work, a new relay placement approach to maximize network connectivity in a multi-hop wireless network is presented. Here, connectivity is defined as a combination of inter-node reachability and network throughput. The nodes are placed following a two-step procedure: (i) initial distribution, and (ii) solution selection. Additionally, a third stage for placement optimization is optionally proposed to maximize throughput. This tries to be a general approach for placement, and several initialization, selection and optimization algorithms can be used in each of the steps. For experimentation purposes, a leave-one-out selection procedure and a PSO related optimization algorithm are employed and evaluated for second and third stages, respectively. Other node placement solutions available in the literature are compared with the proposed one in realistic simulated scenarios. The results obtained through the properly devised experiments show the improvements achieved by the proposed approach.