无人机最小部署问题：在三维空间中存在若干固定位置且接入需求已知的地面终端，这些终端只能通过部署在空中的中继无人机接入网络。 每架中继无人机具有受限的留空高度范围（高度上下限）、覆盖半径或链路容量等通信性能约束。 我们的目标是在满足所有地面终端接入需求的前提下，确定所需部署的中继无人机数量最少。这个问题可以建模为集合覆盖问题。

---

问题抽象

将中继无人机最小部署问题形式化为如下模型：

1. 终端集合: 地面终端集合 $U = \{t_1, t_2, \dots, t_n\}$，其中 $t_i$ 表示第 $i$ 个地面终端。

2. 候选无人机部署方案: 候选部署位置集合 $\mathcal{P} = \{p_1, p_2, \dots, p_m\}$。 对于每一个候选方案 $p_j$（包含位置、高度等），其能覆盖的地面终端子集为 $S_j \subseteq U$。

3. 集合族: 所有候选方案对应的覆盖子集构成集合族 $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$。

4. 目标: 从 $\mathcal{S}$ 中选出最少的子集，使其并集覆盖 $U$。

注

Q: 怎么确定UAV的初始的候选位置集合$\mathcal{P}$?可否通过终端集合的位置通过一些特定的模型继而生成一些较为合理的初始位置?

Q: 对于某一具体的UAV，怎么确定其覆盖终端子集$S_j$?

数学建模

符号定义

符号	定义
$U=\{1,2,\dots,n\}$	地面终端集合，第 $i$ 个终端位置 $(x_i,y_i)$
$\mathcal{P}=\{p_1,\dots,p_m\}$	候选 UAV 位置集合，每个候选 $p_j=(x_j,y_j,h_j)$
$x_j \in \{0,1\}$	决策变量：是否在候选点 $p_j$ 部署 UAV
$y_{ij} \in \{0,1\}$	决策变量：终端 $i$ 是否被无人机 $j$ 服务(即终端 $i$ 在可被无人机覆盖的情况下是否选择无人机 $j$ 为他服务)
$P_t, f_c, B, N_0$	发射功率、载波频率、带宽、噪声功率谱密度
$h_{\min}, h_{\max}$	UAV 高度限制
$C_j, R_{\min}$	UAV 容量限制、最小速率需求

覆盖判定模型

判断一个 UAV 是否能服务某个用户，需满足几何与通信约束。

1. 计算几何距离与仰角 水平距离 $d_{ij}^{\text{h}}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$ 三维距离 $d_{ij}=\sqrt{(d_{ij}^{\text{h}})^2 + h_j^2}$ 仰角 $\theta_{ij}=\arctan\left(\frac{h_j}{d_{ij}^{\text{h}}}\right)$

2. 估计 LoS（视距）概率 使用 Al-Hourani 模型：

   $$P_{\text{LoS}}(\theta)=\frac{1}{1 + a \exp(-b(\theta - a))}$$

   其中 $a,b$ 为环境参数（如城市环境 $a=9.61, b=0.16$）。

3. 计算路径损耗 平均路径损耗（dB）：

   $$L_{ij} = P_{\text{LoS}}(\theta_{ij})\cdot L_{\text{LoS}}(d_{ij}) + (1-P_{\text{LoS}}(\theta_{ij}))\cdot L_{\text{NLoS}}(d_{ij})$$

   其中 $L_{\text{LoS}}$ 和 $L_{\text{NLoS}}$ 为自由空间损耗加上附加损耗 $\eta$。

4. 计算信噪比与速率 接收功率 $P_{r,ij} = P_t / 10^{L_{ij}/10}$ 信噪比 $\text{SNR}_{ij} = \frac{P_{r,ij}}{N_0 B}$ 速率 $R_{ij} = B\log_2(1+\text{SNR}_{ij})$

5. 判定覆盖 若 $R_{ij} \ge R_{\min}$ 且 $h_{\min} \le h_j \le h_{\max}$，则认为终端 $i$ 可被候选点 $p_j$ 覆盖，即 $i \in S_j$。

候选点生成

由于部署位置是连续的，通常采用离散化方法生成候选集合 $\mathcal{P}$。

1. 水平网格化：在目标区域按步长 $g$（如 50m）划分网格，取网格点作为水平坐标 $(x,y)$。
2. 高度离散化：对每个水平点，取若干离散高度 $h \in \{h_1, h_2, \dots\}$。
3. 生成集合：所有 $(x,y,h)$ 组合构成候选集合 $\mathcal{P}$。

整数规划模型 (ILP)

将问题建模为 0-1 整数线性规划问题：

$$\begin{aligned} \min \quad & \sum_{j=1}^{m} x_j \\ \text{s.t.} \quad & \sum_{j: i\in S_j} y_{ij} \ge 1, \quad \forall i \in U \quad (\text{覆盖约束}) \\ & y_{ij} \le x_j, \quad \forall i,j \quad (\text{关联约束}) \\ & \sum_{i: i\in S_j} d_i y_{ij} \le C_j x_j, \quad \forall j \quad (\text{容量约束}) \\ & x_j, y_{ij} \in \{0,1\} \end{aligned}$$

求解算法

算法	说明	适用场景
贪心算法 (Greedy)	每次选择能覆盖最多终端的候选点	Baseline，速度快，近似解
整数规划 (ILP)	使用 Gurobi/CPLEX 求解精确最优解	小规模问题 ($n,m$ 较小)
聚类 + 局部优化	先 K-means 分簇，再簇内求解	大规模问题，实用性强
元启发式 (GA/PSO)	遗传算法或粒子群算法搜索	复杂非线性约束 (如 SINR)

通信参数

• 载波频率: $f_c = 2$ GHz
• 光速: $c = 3 \times 10^8$ m/s
• 系统带宽: $B = 10$ MHz
• 发射功率: $P_t = 10$ dBm
• 噪声谱密度: $N_0 = -174$ dBm/Hz
• 终端最小速率需求: $R_{min} = 5$ Mbps
• 单个终端容量: $d_i = 0.2 - 5$ Mbps的均匀分布
• 单 UAV 容量: $C_{max} = 50$ Mbps

提示

• 指挥/控制（C&C）、低速遥测）：60–100 kb/s。这是 3GPP 和多篇论文常用的 C&C 门槛。
• 低速数据 / IoT 设备：10–100 kb/s（取决应用）
• 普通网页/消息/轻量应用：100–500 kb/s（0.1–0.5 Mbps）
• 视频通话 / 标清视频流：500 kb/s – 2 Mbps
• 高清视频流 / 高质量多媒体：2–8 Mbps（或更高）
• 大流量回传 / 高速上网：>10 Mbps

环境参数 (Urban Micro)

• 路径损耗参数: $a = 9.61$, $b = 0.16$
• LoS 附加损耗: $\eta_{LoS} = 1.0$ dB
• NLoS 附加损耗: $\eta_{NLoS} = 20.0$ dB

几何约束

• UAV 高度范围: $h_{min} = 100$ m, $h_{max} = 150$ m
• 服务区域: $1000 \times 1000$ m²

---

信道模型

1. LoS 概率模型

   基于 Al-Hourani 模型，仰角 $\theta$ 的 LoS 概率为：

   $$P_{LoS}(\theta) = \frac{1}{1 + a \cdot \exp(-b \cdot (\theta - a))}$$

   其中仰角 $\theta = \arctan\left(\frac{h}{d_{2D}}\right)$，$d_{2D}$ 为水平距离。

2. 路径损耗模型

   自由空间路径损耗 (FSPL)：

   $$L_{FSPL} = 20\log_{10}(d_{3D}) + 20\log_{10}(f_c) + 20\log_{10}\left(\frac{4\pi}{c}\right)$$

   平均路径损耗：

   $$L_{avg} = P_{LoS} \cdot L_{LoS} + (1 - P_{LoS}) \cdot L_{NLoS}$$

   其中：

   $$L_{LoS} = L_{FSPL} + \eta_{LoS}$$

   $$L_{NLoS} = L_{FSPL} + \eta_{NLoS}$$

3. 速率计算

   接收功率：

   $$P_r = \frac{P_t}{10^{L_{avg}/10}}$$

   信噪比：

   $$SNR = \frac{P_r}{N_0 \cdot B}$$

   香农容量：

   $$R = B \cdot \log_2(1 + SNR)$$

决策变量

• $x_j \in \{0,1\}$: 是否在候选点 $j$ 部署 UAV
• $y_{ij} \in \{0,1\}$: 用户 $i$ 是否连接到 UAV $j$

目标函数

$$\min \sum_{j \in \mathcal{J}} x_j$$

约束条件

1. 覆盖约束 (每个用户至少连接一个 UAV)：

   $$\sum_{j \in \mathcal{J}} y_{ij} \geq 1, \quad \forall i \in \mathcal{I}$$

2. 关联约束 (只有部署的 UAV 才能提供服务)：

   $$y_{ij} \leq x_j, \quad \forall i \in \mathcal{I}, j \in \mathcal{J}$$

3. 容量约束 (每个 UAV 的总服务需求不超过容量)：

   $$\sum_{i \in \mathcal{I}} d_i \cdot y_{ij} \leq C_{max} \cdot x_j, \quad \forall j \in \mathcal{J}$$

4. 覆盖质量约束 (隐含在候选点生成中)：

   $$y_{ij} = 0, \quad \text{if } R_{ij} < R_{min}$$

其中：

• $\mathcal{I}$: 用户集合
• $\mathcal{J}$: 候选部署点集合
• $d_i$: 用户 $i$ 的需求
• $R_{ij}$: 候选点 $j$ 对用户 $i$ 的可达速率

algorithm-ILP

算法流程

1. 候选点生成: 在三维网格中生成候选位置
2. 覆盖矩阵预计算: 计算 $R_{ij} \geq R_{min}$ 的覆盖关系
3. ILP 模型构建: 建立上述数学模型
4. CBC 求解器求解: 使用分支定界法求解
5. 结果提取: 获得最优 $x_j$ 和 $y_{ij}$

重要

复杂度分析：

• 时间复杂度: $O(|\mathcal{J}| \cdot |\mathcal{I}| \cdot \text{poly}(n))$
• 空间复杂度: $O(|\mathcal{J}| \cdot |\mathcal{I}|)$

algorithm-(K-means)

算法思路：采用聚类 + 局部搜索 + 自适应分裂的三阶段框架：

算法流程

1. 初始化与 K 值估算

   基于容量约束估算 UAV 数量下界：

   $$K_{min} = \lceil \frac{\sum_{i \in \mathcal{I}} d_i}{C_{max}} \rceil$$

2. 全局 K-means 聚类

   使用标准 K-means 算法将用户划分为 $K_{min}$ 个簇：

   $$\min_{\{C_k\}} \sum_{k=1}^{K} \sum_{i \in C_k} ||\mathbf{p}_i - \mathbf{c}_k||^2$$

   其中 $\mathbf{p}_i$ 为用户 $i$ 的位置，$\mathbf{c}_k$ 为簇 $k$ 的质心。

3. 递归处理每个簇

   Step 1: 局部搜索

   对每个簇 $C_k$，以质心 $\mathbf{c}_k$ 为中心进行三维搜索：

   搜索空间：

   $$\mathcal{S}_k = \{[x,y,h] : |x-c_{k,x}| \leq \Delta, |y-c_{k,y}| \leq \Delta, h_{min} \leq h \leq h_{max}\}$$

   寻找满足以下条件的 UAV 位置 $\mathbf{u}^* = [x^*, y^*, h^*]$：

   $$R_{i,\mathbf{u}^*} \geq R_{min}, \quad \forall i \in C_k$$

   $$\sum_{i \in C_k} d_i \leq C_{max}$$

   Step 2: 自适应分裂

   如果局部搜索失败，对簇 $C_k$ 进行 2-means 分裂：

   $$C_k \rightarrow C_{k1} \cup C_{k2}$$

   递归处理子簇，直到：

   • 子簇可被单架 UAV 覆盖，或子簇只剩单个用户 (直接部署)

重要

复杂度分析

• 时间复杂度: $O(K \cdot n \cdot d \cdot I + K \cdot S^3 \cdot R)$
  • $K$: 初始簇数, $n$: 用户数, $d$: 维度, $I$: K-means 迭代次数
  • $S$: 搜索范围, $R$: 递归深度
• 空间复杂度: $O(n + K \cdot S^3)$

---

终端驱动的求解算法

1. 候选点生成

   从终端中心位置和其覆盖圆的交点生成候选部署位置。

2. 候选点剪枝

   移除被其他候选点包含的子集，以减少问题规模。

3. UAV 选取

   使用整数线性规划（ILP）找出覆盖所有终端所需的最少 UAV 数量。

4. 分配与精细调优（Minimax 优化）

   选择候选点后，将每个终端分配给特定的 UAV（通常是最近的选择），然后优化 UAV 的位置以最小化到其分配终端的最大距离。

   每个 UAV $k$ 的优化问题：

   令 $S_k$ 为分配给 UAV $k$ 的终端集合，我们想要找到最优的三维位置 $u = (x, y, z)$。

   目标： 最小化最大距离 $R$：

   $$min R$$

   约束条件：

   1. 覆盖约束： 到每个分配终端 $p_i$ 的距离必须在 $R$ 范围内：

      $$\|u - p_i\| \le R, \quad \forall i \in S_k$$

   2. 可行性约束： 距离不得超过终端的通信范围 $R_{3d, i}$：

      $$\|u - p_i\| \le R_{3d, i}, \quad \forall i \in S_k$$

   3. 高度约束： UAV 必须在允许的高度范围内：

      $$h_{min} \le z \le h_{max}$$

   我们使用 CVXPY 来解决这个二阶锥规划（SOCP）问题。

交叠区域

给定一个有限圆集合：

$$\mathcal C = \{ C_1, C_2, \dots, C_n \},$$

其中每个 $C_i$ 是平面上的一个圆。

定义覆盖数函数：

$$f(x) = \bigl| \{\, C_i \in \mathcal C \mid x \in C_i \,\} \bigr|.$$

对任意圆子集 $I \subseteq \mathcal C$，定义“覆盖组合区域”：

$$S_I = \{\, x \in \mathbb{R}^2 \mid \{ C_i \mid x\in C_i\} = I \}.$$

即：
$S_I$ 表示 恰好被集合 $I$ 中的圆覆盖，并且不被其他圆覆盖的区域。

根据覆盖圆的数量，对所有非空 $S_I$ 分类：

$$S_k = \{\, I \subseteq \mathcal C \mid |I| = k,\; S_I \neq \varnothing \,\}, \qquad k=1,2,\dots,n.$$

用户终端最大覆盖半径推导（线性链路预算）

1. 速率 → 最小 SNR

   信道容量（香农公式）为

   $$R = B\log_2(1+\mathrm{SNR})$$

   因此最小所需 SNR 为

   $$\mathrm{SNR}_{\min} = 2^{R_{\min}/B}-1.$$

2. 链路预算（线性形式）

   接收功率与发射功率及路径损耗关系为

   $$P_r(d)=\frac{P_t}{L(d)}.$$

   噪声功率（线性刻度）为

   $$N = N_0 B.$$

   因此 SNR 为

   $$\mathrm{SNR}(d)=\frac{P_r(d)}{N} =\frac{P_t}{L(d)N}.$$

   要求

   $$\mathrm{SNR}(d)\ge\mathrm{SNR}_{\min}$$

   等价于

   $$L(d)\le \frac{P_t}{N\,\mathrm{SNR}_{\min}}.$$

3. 使用自由空间路径损耗（FSPL）

   若路径损耗模型为

   $$L_{\mathrm{FS}}(d)=\left(\frac{4\pi f d}{c}\right)^2,$$

   则代入可得到最大允许距离 (d_{\max})：

   $$\left(\frac{4\pi f d_{\max}}{c}\right)^2 = \frac{P_t}{N\,\mathrm{SNR}_{\min}}$$

4. 解出最大距离

   $$d_{\max}= \frac{c}{4\pi f} \sqrt{ \frac{P_t}{N_0 B\,(2^{R_{\min}/B}-1)} }.$$