说明书

无人机位置优化模拟退火项目说明书

说明无人机位置优化项目的数学模型、数据结构、模拟退火流程、输入输出和当前源码实现边界。

项目说明书2024-10-15模拟退火算法求解无人机位置C++模拟退火无人机通信数据结构与算法

一、项目定位

本项目是中国矿业大学《数据结构与算法分析》课程设计，主题是基于模拟退火算法的无人机位置优化。系统在二维地面上随机生成多个用户，假设一架无人机位于空中，通过搜索无人机坐标，使其到所有用户的最大距离尽可能小，并进一步计算满足用户服务容量所需的发射功率。

项目源码为单文件 C++ 程序：模拟退火-无人机.cpp。配套资料包括课程论文、三维关系图和算法流程图。

地面用户坐标记为 (x_i, y_i, 0)，无人机坐标记为 (x, y, H)。两者之间的距离为：

d_i = sqrt((x - x_i)^2 + (y - y_i)^2 + H^2)

位置优化目标为：

minimize max(d_i)

通信模型中，信道系数取 h_i = 1 / d_i^2。当噪声功率 N0 = 1 时，为满足用户容量 C_i，所需发射功率可以写为：

P_i = (2^C_i - 1) / h_i
    = (2^C_i - 1) * d_i^2

这里要区分两个目标：模拟退火当前直接优化的是最大距离，功率是得到无人机位置后再计算的结果，并不是同时参与退火搜索的目标函数。

程序使用 jiji 结构体保存单个用户的数据：

用户数组 a[1005] 能够容纳最多 1004 个用户。全局变量 sx 和 sy 用于计算用户坐标平均值，作为无人机搜索的初始横纵坐标；ansx、ansy、ansz 保存当前最优位置，ans 保存当前最小最大距离。

程序从标准输入读取用户数量 n，再使用随机数生成用户坐标和服务容量。坐标范围为 [-100, 100]，用户位于地面平面。

程序将所有用户横纵坐标的平均值作为初始位置，初始高度 z 设为 0，然后调用 SA() 执行模拟退火。solve() 会连续调用五次 SA()，以提高随机搜索结果的稳定性。

每轮搜索根据当前温度生成一个随机扰动位置，并调用 calc() 计算该位置到所有用户的最大距离。若新解更优则接受；若新解更差，则按照退火概率接受。之后执行：

t = t * 0.997

当温度低于 1e-14 时终止本轮搜索。

搜索结束后，程序输出无人机坐标，再逐个计算用户信道系数和所需功率，最后累加得到总发射功率。

输入只有一个整数，表示用户数量。例如：

输出包括三部分：随机生成的用户坐标与容量、模拟退火得到的无人机坐标、所有用户所需的总发射功率。由于输入数据由当前时间作为随机种子，重复运行同一个 n 不会得到完全相同的用户集合和结果。

在安装 g++ 的环境中，可以使用：

g++ -std=c++17 -O2 模拟退火-无人机.cpp -o uav_sa
echo 100 | ./uav_sa

本次核验中，源码能够使用 C++17 编译并运行，程序可以完成随机用户生成、模拟退火搜索和结果输出。

论文将无人机高度描述为固定值 H=50，但当前源码把 z 作为随机扰动的一部分参与搜索，并从 0 开始。因此，论文模型和程序实现之间存在版本差异。若要严格实现固定高度模型，应将 z 固定为 H，或者明确把问题改成三维位置优化。

程序使用当前时间设置随机种子，没有提供固定种子或输入文件。实验对比时应增加固定随机种子、保存用户数据，并记录退火参数和最终结果。

当前程序先最小化最大距离，再计算总发射功率。如果项目要研究总功率最小化，应把功率加入目标函数，或者设计加权目标和约束条件。

当前功率计算代码中，距离函数调用把 ansy 作为无人机高度参数传入，和变量命名及论文中的高度定义不一致。该处建议改为使用最终高度变量，并补充单元测试验证距离、信道系数和功率公式。