随机能量多覆盖问题

摘要

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

关键词

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