随机能量多覆盖问题

The stochastic power multi-coverage problem

摘要

该文研究随机能量多覆盖问题：给定一些用户和基站，以及几种可能发生的场景和每种场景发生的概率，每种场景下需要被覆盖的用户以及覆盖次数需求已知，不同场景的用户集需要使用不同的信号覆盖，每个基站发射信号消耗的能量都满足一个能量方程。其目标是要为每一个基站确定发射信号的类型及其覆盖半径，满足所有场景中需要被覆盖用户的覆盖次数需求，并且期望消耗能量总和达到最小。该问题是最小能量覆盖问题的一种推广形式，具有两阶段随机优化问题中的有限场景特征，与点覆盖和集合覆盖等经典优化问题关系密切。利用点覆盖与集合覆盖问题中的“度权”函数与“分层”策略，把问题实例中每个圆盘的权重分解为一系列度权，分而治之地优先选择各场景中度权较小的圆盘，运用该策略设计出求解随机能量多覆盖问题的一个多项式时间近似算法。

Abstract

This paper studies the stochastic power multi-coverage problem: Given some users and base stations, as well as several possible scenarios and the probability of each scenario occurring, the users that need to be covered and the number of times of coverage for each user required in each scenario are known; different signal coverages are needed for the user sets in different scenarios; the power consumed by each base station in transmitting signal all satisfies the power equation, the objective of the stochastic power multi-coverage problem is to determine the type of transmitted signal and its coverage radius for each base station, to meet the coverage requirements for the users in all scenarios and minimize the total expected power consumption. This problem is a generalization of the minimum power coverage problem and has the characteristic of finite scenarios in two-stage stochastic optimization problems, closely related to classical optimization problems such as vertex cover and set cover. By using the "degree-weighted" function and the "layering" strategy from the vertex cover and the set cover problems, the weight of each disk in the problem instance are decomposed into a series of degree weights. The algorithm then proceeds by prioritizing the disks with smaller degree weights in each scenario, and this strategy is employed to design a polynomial-time approximation algorithm for solving the stochastic power multi-coverage problem.

关键词

多覆盖 / 随机优化 / 有限场景 / 度权函数 / 近似算法

Key words

multi-coverage / stochastic optimization / finite scenario / degree-weighted function / approximation algorithm

参考文献

[1] ABUNIMA H, PARK W H, GLICK M B, et al. Two—stage stochastic optimization for operating a renewable—based microgrid[J]. Applied Energy, 2022, 325: 119848.

[2] BERTSIMAS D, SHTERN S, STURT B. Two—stage sample robust optimization[J]. Operations Research, 2022, 70(1): 624-640.

[3] 张得志, 乔馨, 李双艳, 等. 考虑多重覆盖的应急设施多级协同布局鲁棒优化[J]. 控制与决策, 2022, 37(7): 1853-1861.

[4] ZHANG D Z, QIAO X, LI S Y, et al. Robust optimization of hierarchical cooperative layout of emergency facilities considering multiple coverage[J]. Control and Decision, 2022, 37(7): 1853-1861.

[5] FREUND A, RAWITZ D. Combinatorial interpretations of dual fitting and primal fitting[C]// International Workshop on Approximation and Online Algorithms. Berlin: Springer, 2003: 137-150.

[6] CHARIKAR M, PANIGRAHY R. Clustering to minimize the sum of cluster diameters[C]// Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. New York: ACM, 2001: 1-10.

[7] BILÓ V, CARAGIANNIS I, et al. Geometric clustering to minimize the sum of cluster sizes[C]// Algorithms—ESA 2005: 13th Annual European Symposium, Palma de Mallorca. Spain: Springer, 2005: 460-471.

[8] ALT H, ARKIN E M, BRÖNNIMANN H, et al. Minimum cost coverage of point sets by disks[C]// Proceedings of the 22 Annual Symposium on Computational Geometry. New York: ACM, 2006: 449-458.

[9] LEV—TOV N, PELEG D. Polynomial time approximation schemes for base station coverage with minimum total radii[J]. Computer Networks, 2005, 47(4): 489-501.

[10] LI M H, RAN Y L, ZHANG Z. A primal—dual algorithm for the minimum power partial cover problem[J]. Journal of Combinatorial Optimization, 2022, 44(3): 1913-1923.

[11] DAI H, DENG B, LI W D, et al. A note on the minimum power partial cover problem on the plane[J]. Journal of Combinatorial Optimization, 2022, 44(2): 970-978.

[12] LIU X F, LI W D, XIE R T. A primal—dual approximation algorithm for the k—prize—collecting minimum power cover problem[J]. Optimization Letters, 2022, 16(8): 2373-2385.

[13] DAI H, LI W D, LIU X F. An approximation algorithm for the h—prize—collecting power cover problem[C]// International Workshop on Frontiers in Algorithmics. Hong Kong, China: Springer, 2022: 89-98.

[14] 刘晓非, 代涵, 李思哲, 等. 平面上带次模惩罚费用的最小能量部分覆盖问题[J]. 中国科学: 信息科学, 2022, 52(6): 947-959.

[15] LIU X F, DAI H, LI S Z, et al. k—prize—collecting minimum power cover problem with submodular penalties on a plane [J]. SCIENTIA SIAICA Information, 2022, 52(6): 947-959.

[16] ABU—AFFASH A K, CARMI P, KATZ M J, et al. Multi cover of a polygon minimizing the sum of areas[J]. International Journal of Computational Geometry Applications, 2011, 21(6): 685-698.

[17] BAR—YEHUDA R, RAWITZ D. A note on multicovering with disks[J]. Computational Geometry, 2013, 46(3): 394-399.

[18] BHOWMICK S, VARADARAJAN K, XUE S K. A constant—factor approximation for multi—covering with disks[C]// Proceedings of the 29 Annual Symposium on Computational Geometry. New York: ACM, 2013: 243-248.

[19] BHOWMICK S, INAMDAR T, VARADARAJAN K. On metric multi—covering problems[EB/OL]. [ 2024—03—10]. https://arxiv.org/abs/1602.04152.

[20] RAN Y L, HUANG X H, ZHANG Z, et al. Approximation algorithm for minimum power partial multi—coverage in wireless sensor networks[J]. Journal of Global Optimization, 2021, 80(3): 661-677.

[21] DAI H. An Approximation algorithm for the minimum soft capacitated disk multi—coverage problem[C]// National Conference of Theoretical Computer Science. Singapore: Springer, 2022: 96-104.

[22] RAVI R, SINHA A. Hedging uncertainty: Approximation algorithms for stochastic optimization problems[J]. Mathematical Programming, 2006, 108: 97-114.

[23] LI J, LIU Y. Approximation Algorithms for stochastic combinatorial optimization problems[J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-47.

[24] PARTHASARATHY S. Adaptive greedy algorithms for stochastic set cover problems[EB/OL]. [ 2024—04—15]. https://arxiv.org/abs/1803.07639.

[25] SUN J, SHENG H, SUN Y, et al. Approximation algorithms for stochastic set cover and single sink rent—or—buy with submodular penalty[J]. Journal of Combinatorial Optimization, 2022, 44(4): 2626-2641.

[26] VAZIRANI V V. Approximation algorithms[M]. Berlin: Springer, 2001.

基金资助

国家自然科学基金(11801498)