H-hop independently submodular maximization problem with curvature

Abstract

The Connected Sensor Problem (CSP) presents a prevalent challenge in the realms of communication and Internet of Things (IoT) applications. Its primary aim is to maximize the coverage of users while maintaining connectivity among K sensors. Addressing the challenge of managing a large user base alongside a finite number of candidate locations, this paper proposes an extension to the CSP: the h-hop independently submodular maximization problem characterized by curvature α. We have developed an approximation algorithm that achieves a ratio of $\frac{1-e^{-\alpha}}{(2 h+3) \alpha}$. The efficacy of this algorithm is demonstrated on the CSP, where it shows superior performance over existing algorithms, marked by an average enhancement of 8.4%.

Keywords

Internet of things / UAV communication / Approximation algorithms

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

The first and third authors are supported by Beijing Natural Science Foundation Project (Z220004). The second author is supported by the Natural Science Foundation of China (12371320). The fourth author is supported by the Natural Science Foundation of China (12101587) and China Postdoctoral Science Foundation (2022M720329).

References

[1] W. Khawaja, I. Guvenc, D.W. Matolak, U.-C. Fiebig, N. Schneckenburger, A survey of air-to-ground propagation channel modeling for unmanned aerial vehicles, IEEE Commun. Surv. Tutor. 21 (3) (2019) 2361-2391.

[2] A.A. Khuwaja, Y. Chen, N. Zhao, M.-S. Alouini, P. Dobbins, A survey of channel modeling for UAV communications, IEEE Commun. Surv. Tutor. 20 (4) (2018) 2804-2821.

[3] M. Mozaffari, W. Saad, M. Bennis, Y.-H. Nam, M. Debbah, A tutorial on UAVs for wireless networks: Applications, challenges, and open problems, IEEE Commun. Surv. Tutor. 21 (3) (2019) 2334-2360.

[4] L.X. Fan Anqi, Chinese drones provide lifeline network services for flood-stranded residents, URL https://www.globaltimes.cn/page/202107/1229363.shtml.

[5] L. Huang, J. Li, Q. Shi, Approximation algorithms for the connected sensor cover problem, in: International Computing and Combinatorics Conference, Springer, 2015, pp. 183-196.

[6] M. Mozaffari, W. Saad, M. Bennis, M. Debbah, Mobile unmanned aerial vehicles (UAVs) for energy-efficient Internet of Things communications, IEEE Trans. Wireless Commun. 16 (11) (2017) 7574-7589.

[7] J. Xu, Y. Zeng, R. Zhang, UAV-enabled wireless power transfer: Trajectory design and energy optimization, IEEE Trans. Wirel. Commun. 17 (8) (2018) 5092-5106.

[8] Y. Zeng, R. Zhang, Energy-efficient UAV communication with trajectory optimization, IEEE Trans. Wirel. Commun. 16 (6) (2017) 3747-3760.

[9] K. Wang, C. Pan, H. Ren, W. Xu, L. Zhang, A. Nallanathan, Packet error probability and effective throughput for ultra-reliable and low-latency UAV communications, IEEE Trans. Commun. 69 (1) (2020) 73-84.

[10] Y. Yu, X. Bu, K. Yang, H. Yang, Z. Han, UAV-aided low latency mobile edge computing with mmwave backhaul, in: ICC 2019-2019 IEEE International Conference on Communications, ICC, IEEE, 2019, pp. 1-7.

[11] M. Li, N. Cheng, J. Gao, Y. Wang, L. Zhao, X. Shen, Energy-efficient UAV-assisted mobile edge computing: Resource allocation and trajectory optimization, IEEE Trans. Veh. Technol. 69 (3) (2020) 3424-3438.

[12] J. Zhou, D. Tian, Y. Yan, X. Duan, X. Shen, Joint optimization of mobility and reliability-guaranteed air-to-ground communication for UAVs, IEEE Trans. Mob. Comput. (2022).

[13] S. Li, C. Xiang, W. Xu, J. Peng, Z. Xu, J. Li, W. Liang, X. Jia, Coverage maximization of heterogeneous UAV networks, in: 2023 IEEE 43rd Inter-national Conference on Distributed Computing Systems, ICDCS, IEEE, 2023, pp. 120-130.

[14] W. Xu, Y. Sun, R. Zou, W. Liang, Q. Xia, F. Shan, T. Wang, X. Jia, Z. Li, Throughput maximization of UAV networks, IEEE/ACM Trans. Netw. 30 (2) (2021) 881-895.

[15] W. Xu, H. Xie, C. Wang, W. Liang, X. Jia, Z. Xu, P. Zhou, W. Wu, X. Chen, An approximation algorithm for the h-Hop independently submodular maximization problem and its applications, IEEE/ACM Trans. Netw. (2022).

[16] G.L. Nemhauser, L.A. Wolsey, M.L. Fisher, An analysis of approximations for maximizing submodular set functions—I, Math. Program. 14 (1978) 265-294.

[17] M. Conforti, G. Cornuéjols, Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem, Discrete Appl. Math. 7 (3) (1984) 251-274.

[18] J. Yu, S. Ahmed, Maximizing expected utility over a knapsack constraint, Oper. Res. Lett. 44 (2) (2016) 180-185.

[19] T.-W. Kuo, K.C.-J. Lin, M.-J. Tsai, Maximizing submodular set function with connectivity constraint: Theory and application to networks, IEEE/ACM Trans. Netw. 23 (2) (2014) 533-546.

[20] Z. Fang, H. Fu, T. Gu, Z. Qian, T. Jaeger, P. Hu, P. Mohapatra, A model checking-based security analysis framework for IoT systems, High-Confidence Comput. 1 (1) (2021) 100004.

[21] S. Zhu, R. Li, Z. Cai, D. Kim, D. Seo, W. Li, Secure verifiable aggregation for blockchain-based federated averaging, High-Confidence Comput. 2 (1) (2022) 100046.

[22] D.S. Johnson, M. Minkoff, S. Phillips, The prize collecting steiner tree problem: Theory and practice, in: SODA, vol. 1, ( no. 0.6) Citeseer, 2000, p. 4.

[23] N. Garg, Saving an epsilon: A 2-approximation for the k-MST problem in graphs,in:Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, 2005, pp. 396-402.

[24] S. Khuller, M. Purohit, K.K. Sarpatwar, Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems,in:Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014, pp. 1702-1713.