TY - JOUR
T1 - An Approximation Algorithm for the h-Hop Independently Submodular Maximization Problem and Its Applications
AU - Xu, Wenzheng
AU - Xie, Hongbin
AU - Wang, Chenxi
AU - Liang, Weifa
AU - Jia, Xiaohua
AU - Xu, Zichuan
AU - Zhou, Pan
AU - Wu, Weigang
AU - Chen, Xiang
PY - 2022/10/5
Y1 - 2022/10/5
N2 - This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given Κ UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem - the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a (1-1/e)⁄(2h+3) -approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a (1-1/e)⁄11 -approximate solution to the MCCP problem with h = 4, which significantly improves its currently best (1-1/e)⁄32 -approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.
AB - This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given Κ UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem - the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a (1-1/e)⁄(2h+3) -approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a (1-1/e)⁄11 -approximate solution to the MCCP problem with h = 4, which significantly improves its currently best (1-1/e)⁄32 -approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.
KW - UAV communication networks
KW - maximum connected coverage problem
KW - connected sensor coverage problem
KW - submodular function maximization
KW - approximation algorithms
KW - COMMUNICATION
KW - NETWORKS
UR - http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000865089600001
U2 - 10.1109/TNET.2022.3210825
DO - 10.1109/TNET.2022.3210825
M3 - RGC 21 - Publication in refereed journal
SN - 1063-6692
JO - IEEE - ACM Transactions on Networking
JF - IEEE - ACM Transactions on Networking
ER -