Multi-Hop Relay Deployment In Wireless Networks

The traditional relay deployment problem usually assumes that the locations of users are known and stationary,which is not realistic in practice.The prevalence of mobile devices have made it possible to collect user trajectory and account for user movement when deploying re-lays.Under this background,we identify a novel problem Trajectory-Based Relay Deployment(TBRD)which aims at maximizing user connection time as the users roam through the target area while complying with relay resource constraints.To solve the TBRD,we first propose the concept Demand Nodes(DNs),which are virtual weighted nodes representing the locations where users often pass or stay for long periods of time.Next,we design a Demand Node Gener-ation(DNG)algorithm that transforms the continuous historical user trajectory into a number of discrete DNs.By generating DNs,we convert the TBRD problem into a Demand Node Cover-age(DNC)problem,which is proved to be NP-complete.After that,we design an approximation algorithm,named Submodular Iterative Deployment Algorithm(SIDA),to solve the DNC prob-lem with the approximation factor 1-1/(?),where e is the mathematical constant,and k is the relay number constraint.Finally,we use five real trajectory datasets to evaluate our proposed algorithm,and the simulation results demonstrate that our algorithm can obtain high coverage for users in motion,leading to better user experience.In addition,we also analyze the impact of different parameters on the coverage performance.According to our knowledge,we are the first to utilize user trajectories for relay deployment in wireless networks.