Approximation Design for Cooperative Relay Deployment in Wireless Networks
Haotian Wang, Shilei Tian, Xiaofeng Gao, Lidong Wu and Guihai Chen
Shanghai Jiao Tong University, Shanghai Jiao Tong University, Shanghai Jiao Tong University, University of Texas at Tyler, Shanghai Jiao Tong University

In this paper, we aim to maximize users’ satisfaction by deploying limited number of relays in a target region to form a wireless relay network, and define the Deployment of Cooperative Relay (DoCR) problem, which is proved to be NP-complete. We first propose two approximation algorithms, an O(\ log n) algorithm that utilizes the algorithms for budget weighted Steiner tree problem with novel position weighting assignment, and an O(pk) algorithm that iteratively scans potential positions and determines relay placement plan with the help of submodular function theory, partition technique, and greedy strategy. We name them REDA and SIDA respectively. We further propose GDBA, a heuristic method, to solve the DoCR problem releasing potential location constraint. Our extensive experiments indicate that the algorithms we propose can significantly improve the total satisfaction of the network. Furthermore, we establish a testbed using USRP to showcase our designs in real scenarios. To the best of our knowledge, we are the first to propose approximation algorithms for relay placement problem to maximize user satisfaction, which has both theoretical and practical significance in the related area.