百度智能建站系统,wordpress标签有问题,东莞seo,郑州网站建设渠道此篇文章为Multi-objective Deployment Optimization of UAVs for Energy-Efficient Wireless Coverage的论文学习笔记#xff0c;只供学习使用#xff0c;不作商业用途#xff0c;侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正!
创新点
RD算法
混合…此篇文章为Multi-objective Deployment Optimization of UAVs for Energy-Efficient Wireless Coverage的论文学习笔记只供学习使用不作商业用途侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正!
创新点
RD算法
混合解初始化算法
改进的多目标灰狼优化ImMOGWO算法
在本节中我们首先介绍所提出的改进的多目标灰狼优化ImMOGWO算法的动机。随后将介绍作为ImMOGWO算法第一部分的角色确定RD算法。最后ImMOGWO算法的第二部分包括混合解初始化HSI算法和基于Levy飞行与正余弦方法LSCMGA的解决方案更新操作。
D. 整体算法设计与复杂度分析 提出的 ImMOGWO 算法的整体过程如算法 4 所示。我们的算法旨在通过优化无人机UAV的数量、三维位置和速度以实现良好的覆盖率和低能耗。首先基于移动地面用户GU的分布我们设计了 RD 算法对地面用户进行聚类为无人机的数量和位置初始化做准备。接着由于优化变量的多样性我们提出了 HSI 算法来初始化所有变量以提高算法的收敛效果。此外我们应用 LSC 方法在LSCMGA算法中避免局部最优并加速收敛。考虑到每个时间段用户的移动性上述三部分将在每个时间段优化无人机的部署位置。由于RD算法和HSI算法克服了随机初始化造成的缺点 ImMOGWO 算法的收敛速度相对较快这也表明提出的 ImMOGWO 算法具有良好的收敛性能。我们提出的算法不仅可以应用于本文中的多无人机部署场景还可以应用于移动边缘计算中无人机作为边缘服务器的通信和位置优化场景。
令 N G U N_{GU} NGU 表示GU基站用户的数量 N c N_c Nc 表示簇的数量。单个时间槽中RD资源分配的计算复杂度为 O ( N i t ⋅ N G U ⋅ N c ) O(N_{it} \cdot N_{GU} \cdot N_c) O(Nit⋅NGU⋅Nc)其中 N i t N_{it} Nit 是收敛所需的迭代次数。当变量数量为 n v n_v nv 时单个时间槽中HSI互联网卫星的计算复杂度为 O ( n v ⋅ K ) O(n_v \cdot K) O(nv⋅K)其中 K K K 是无人机的数量。设 k k k 和 N p N_p Np 分别表示优化目标的数量和种群大小。当帕累托存档的大小与种群 N p N_p Np 相同时LSCMGA算法中对帕累托存档中的 N p N_p Np 个解进行排序的计算复杂度为 O ( k ⋅ N p ⋅ log ( N p ) ) O(k \cdot N_p \cdot \log(N_p)) O(k⋅Np⋅log(Np))。因此所提出的 ImMOGWO 在 N T N_T NT 个时间槽期间的整体计算复杂度为 O ( N T ( N i t ⋅ N G U ⋅ N c n v ⋅ K k ⋅ N p ⋅ log ( N p ) ) ) O(N_T (N_{it} \cdot N_{GU} \cdot N_c n_v \cdot K k \cdot N_p \cdot \log(N_p))) O(NT(Nit⋅NGU⋅Ncnv⋅Kk⋅Np⋅log(Np)))。
这个伪代码描述的是“ImMOGWO算法”其由以下几个部分组成
输入第1行输入参数是时间槽的数量 N T N_T NT。时间槽循环第2-10行 对于每个时间槽 t t t 1 ≤ t ≤ N T 1 \leq t \leq N_T 1≤t≤NT执行以下步骤第2行。每个地面用户GU随机改变其位置第3行。利用算法1获得当前时间槽的群集分布 χ [ t ] \chi[t] χ[t]第4行。基于群集分布通过算法2初始化无人机UAV的数量、位置和速度第5行。接着执行算法3进行优化处理第6行。如果 t ≥ 1 t \geq 1 t≥1且当前时间槽的群集分布与前一时间槽相同 χ [ t ] χ [ t − 1 ] \chi[t] \chi[t-1] χ[t]χ[t−1]则中断循环第7-9行。 输出第11行输出结果是在良好覆盖和高能效要求下的无人机部署方案。 总结来说ImMOGWO算法通过在不同时间槽内调整无人机的数量、位置和速度以响应地面用户的位置变化从而达到优化无人机部署的目的关注于覆盖范围的最大化和能源效率的提高。
A. 动机
多目标优化与单目标优化不同在多目标优化问题MOP中比较解决方案较为困难因为多目标空间具有多重目标比较度量。MOGWO算法通过狼的狩猎规则接近目标[44]。每只灰狼的位置代表解空间中的一个可行解。在群体中三只灰狼占据最佳位置分别命名为α、β、δ。其余非领导狼统一命名为ω。在狩猎过程中这三只狼将带领其余狼移动并捕捉猎物直到找到猎物最优解。 提出了ImMOGWO算法以解决上述缺点其中RD算法旨在克服随机初始化引起的算法低效问题。由于混合解被求解HSI用于初始化混合解。然后我们使用基于MOGWO算法的LSC方法增加解决方案的多样性并提高算法效率。 加权切比雪夫方法[45]可以提供一个最优帕累托点。然而使用均匀加权切比雪夫方法获得的解通常不是均匀分布的。为解决这个问题改进的加权切比雪夫方法增加了参数ρ。但是参数ρ难以设置。一个值可能会导致计算困难而较大的值可能会导致一些非支配点被忽视。此外我们的优化问题中考虑了混合物理因素如用户移动性、无人机的数量、位置和速度它们相互影响。每个个体包含所有无人机的信息这是一个多维变量。
B. 地面用户GUs角色确定算法
鉴于地面用户GUs可以随机移动且分布不均使用无人机UAV的随机初始位置初始化是非常低效的。为了防止无人机随机初始化导致的算法效率低下我们设计了用于无人机位置初始化的角色确定RD算法。然后对于一些传统的聚类算法例如K-means算法[46]需要预先给定簇的数量。此外聚类结果严重受到初始聚类中心选择的影响[47]。**为了弥补传统聚类算法的不足RD算法旨在将地面用户划分为几个簇并根据簇内用户的 数量和距离 预测无人机的数量和位置。**在每个时间段内地面用户被视为静止的使用RD算法确定每个时间段的簇分布。当地面用户的位置随着时间段的变化而变化时RD算法将再次运行。 每个基站用户GU可以决定其角色即作为簇中心或非簇中心。簇分布表示为 χ { χ 1 , χ 2 , . . . , χ N } \chi \{\chi_1, \chi_2, ..., \chi_N\} χ{χ1,χ2,...,χN} 其中 χ i ∈ { 0 , 1 } \chi_i \in \{0,1\} χi∈{0,1} 。当 χ i 0 \chi_i 0 χi0时表示第 i i i 个 GU 作为簇中心。当 χ i 1 \chi_i 1 χi1 时表示第 i i i 个 GU 是非簇中心。对于给定的簇分布 χ \chi χ 适应度函数 F i t ( χ ) Fit(\chi) Fit(χ) 被定义为反映簇内个体的身份以及不同簇之间的差异其表达方式为 其中 N ( χ ) N(\chi) N(χ) 是簇的数量。 R χ ( i ) R_\chi(i) Rχ(i) 表示最小的组间距离与组内距离的比率用于评估配置 χ \chi χ 的聚类效果其定义为。这里 R χ ( i ) min j ≠ i m i j e i e j . e j \begin{aligned}R_\chi(i)\min_{j\neq i}\frac{m_{ij}}{e_ie_j}.e_j\end{aligned} Rχ(i)jimineiejmij.ej的 e j e_j ej 是第 j j j 个簇中基站用户GU与该簇中心之间的平均距离 e i e_i ei 是第 i i i 个簇中的 GU 与其簇中心之间的平均距离。 m i j m_{ij} mij 则是第 i i i 个簇和第 j j j 个簇的中心之间的距离。
其中 B 是一个正常数。为了获得最优的簇分布必须最大化适应度函数 F i t ( χ ) Fit(\chi) Fit(χ)。设X代表所有可行的 χ \chi χ 的集合即 所提出的RD算法在每个时间槽的过程如算法1所示。
每个GU都会随机地初始化其角色无论是否充当聚类中心。此时 G U n GU_n GUn 将广播其包括角色和位置信息在内的信息并接收其他GU的信息。当所有 GU 都接收到其他 GU 的信息后每个GU将根据欧几里得距离加入最近的聚类。这时将获得聚类分布 χ \chi χ 。同时每个 GU 计算 R χ ( i ) ( i 1 , 2 , . . . , N ( χ ) ) R_{\chi}(i)(i1,2,...,N(\chi)) Rχ(i)(i1,2,...,N(χ)) 和 F i t ( χ ) Fit(\chi) Fit(χ) 。然后每个 GU 生成一个遵循指数分布的随机数该分布的平均值为正。**GU将基于生成的随机数进行衰减。**在衰减至零后GU将根据概率 p χ ^ χ p_{\hat{\chi}\chi} pχ^χ 改变当前角色。也就是说**GU的角色将从非聚类中心变为聚类中心或从聚类中心变为非聚类中心。**GU将根据概率 1 − p χ ^ χ 1-p_{\hat{\chi}\chi} 1−pχ^χ保持当前角色。如果GU没有改变其角色它将再次生成一个遵循指数分布的随机数并进行衰减。
如果GU改变了当前的角色状态它将向其他用户广播新角色并生成一个新的随机数以重新启动衰减过程。当其他GU接收到新角色时它们可能会退出当前聚类并加入一个新的聚类。这时将获得新的聚类分布 χ ^ \hat{\chi} χ^。再次计算 R χ ^ ( i ) ( i 1 , 2 , . . . , N ( χ ^ ) ) R_{\hat{\chi}}(i)(i1,2,...,N(\hat{\chi})) Rχ^(i)(i1,2,...,N(χ^))。然后每个GU继续其衰减过程。在GU的衰减过程结束时将基于聚类分布 χ ^ \hat{\chi} χ^重新计算改变角色的概率。迭代结束直到适应度函数 F i t m Fit_m Fitm收敛可以获得聚类分布的结果。RD算法通过将GU分组到聚类中为混合解初始化算法HSI做准备以提高算法的收敛效果。
主循环第2-12行 这个模块是算法的核心包括所有主要的处理步骤。 角色选择与信息广播第3行每个GU群体单元随机选择其角色并广播其信息。集群分布获取第4行在接收到其他GUs的角色后GU n n n 可以得到当前的集群分布 χ \chi χ。角色评估与适应度计算第5行GU n n n 计算 R χ ( i ) R_{\chi}(i) Rχ(i)对于 i 1 , 2 , . . . , N ( χ ) i 1,2,...,N(\chi) i1,2,...,N(χ)和 Fit ( χ ) \text{Fit}(\chi) Fit(χ)即集群的适应度。计时器生成与倒计时第6行GU n n n 生成一个遵循指数分布的计时器并开始倒计时。角色变更决策第7行计时器到期后GU n n n 根据概率 p χ χ ^ p_{\chi \hat{\chi}} pχχ^ 改变其角色或以 1 − p χ χ ^ 1 - p_{\chi \hat{\chi}} 1−pχχ^ 的概率保持其角色。角色更新与新集群配置第8行如果GU n n n 改变了其角色它将广播新角色并获取新的集群配置 χ ^ \hat{\chi} χ^。新配置下的适应度计算第9行其他GUs在新的集群配置 χ ^ \hat{\chi} χ^ 下计算 Fit ( χ ^ ) \text{Fit}(\hat{\chi}) Fit(χ^)。新计时器生成与重复过程第10-11行GU n n n 生成一个新的计时器并重复步骤7-10。 输出结果第13行 这个模块负责输出最终的集群配置 χ \chi χ集群数量 N cluster N ( χ ) N_{\text{cluster}} N(\chi) NclusterN(χ)每个集群中GU的数量 C j , num C_{j,\text{num}} Cj,num以及每个集群中心的位置 po cc → \overrightarrow{\text{po}_{\text{cc}}} pocc 。 每个模块都是算法的一个关键部分共同协作以实现角色决策RD算法的目标。
C. 无人机的能源高效部署
为了增强传统的多目标灰狼优化 MOGWO 算法的性能并克服其面临的挑战提出了混合解初始化算法 HSI 以初始化所有变量从而改善算法的收敛效果。此外为了避免局部最优并加速收敛 LSC 方法被应用于局部搜索聚类多目标遗传算法 LSCMGA 该算法可以在每个时间槽中运行。
解决方案初始化为此我们提出了混合解初始化算法 HSI 以初始化决策变量加快收敛速度并提高个体初始化的多样性。在该算法中所需无人机 UAV 的数量和每架无人机的位置被纳入我们的决策变量。当簇的数量过大时每个簇对应一架无人机显然是不现实的。因此我们提出在一定概率下一个簇由一架无人机相对应地覆盖。我们将无人机的状态定义为 U N cluster × 1 [ U 1 , U 2 , . . . , U N cluster ] UN_{\text{cluster}} \times 1 [U_1, U_2, ..., U_{N_{\text{cluster}}}] UNcluster×1[U1,U2,...,UNcluster] 且 U j ∈ { 0 , 1 } U_j \in \{0,1\} Uj∈{0,1} 。当 U j 1 U_j 1 Uj1 时表示第 j j j 架无人机需要覆盖第 j j j 个簇否则第 j j j 架无人机将不被考虑。这里我们定义第 j j j 个簇的重要性为。它与簇中用户 ϖ c c j , j ∈ { 1 , 2 , . . , N c l u s t e r } \begin{aligned}\varpi_{cc}^j,j\in\{1,2,..,N_{cluster}\}\end{aligned} ϖccj,j∈{1,2,..,Ncluster} 的数量成正比可以表示为 ϖ c c j ∝ C j , n u m \varpi_{cc}^j\propto C_{j,num} ϖccj∝Cj,num 。这意味着簇中 GU基站用户越多该簇的重要性就越高。然后第 j j j 个候选无人机对应第 j j j 个簇的需求概率由簇的重要性和簇之间的距离决定表达为 其中 r j m i n min j ≠ i r i , j \begin{aligned}r_j^{min}\min_{j\neq i}r_{i,j}\end{aligned} rjminjiminri,j 表示第 j j j 个簇与其他簇之间的最小距离。簇的重要性越大且最小距离越长相应的无人机被需要的概率就越高。根据方程式(18)我们可以得到 [ U 1 , U 2 , . . . , U N cluster ] [U_1, U_2, ..., U_{N_{\text{cluster}}}] [U1,U2,...,UNcluster] 。因此无人机的数量初始化为 K ∑ i U i K \sum_i U_i K∑iUi 。 接着每架所需无人机的位置通过相应簇中心位置进行初始化。我们使用正态分布来计算无人机在不同区域降落的概率。
HSI算法的过程展示在算法2中。 初始化输入第1行集群与无人机需求计算第2-4行 根据算法第一步的输出这个模块计算每个无人机被需要的概率步骤3以及实际所需无人机的数量步骤4。 无人机位置与安全距离检查第5-12行 在这个模块中每个所需的无人机根据一定概率找到其在对应集群中的初始水平位置步骤6。 能量方程与初始速度计算第13行解决方案检查与循环第15-17行 如果当前解决方案集为空则返回步骤3重新计算。 输出结果第18行 最终输出所有初始解决方案的集合 W ⃗ [ K , X , Y , H , V ] \vec{W} [K,X,Y,H,V] W [K,X,Y,H,V]其中包括每个无人机的编号、位置和速度。
**最优解被视为α狼。β狼和δ狼分别是第二和第三优的解决方案。其余非领导狼均被统称为ω狼。**在我们提出的LSCMGA算法中在根据适应度函数值选出前三个最优解后我们采用了SCA的思想来接近猎物以避免陷入局部优化。其公式如下 其中 i { 1 , 2 , 3 } i \{1,2,3\} i{1,2,3} j { α , β , δ } j \{\alpha, \beta, \delta\} j{α,β,δ}。 r ⃗ i 1 \vec{r}_{i1} r i1决定了解决方案在当前解决方案与目的地之间空间中的下一个位置。 r ⃗ i 2 ∈ [ 0 , 2 π ] \vec{r}_{i2} \in [0,2\pi] r i2∈[0,2π]定义了向目的地移动或远离目的地的距离。 r ⃗ i 3 \vec{r}_{i3} r i3赋予目的地随机权重以便在定义距离时随机加强 r ⃗ i 3 1 \vec{r}_{i3} 1 r i31或削弱 r ⃗ i 3 1 \vec{r}_{i3} 1 r i31目的地的影响。最后参数 r ⃗ i 4 \vec{r}_{i4} r i4是[0,1]之间的随机数控制正弦和余弦分量的选择。然后对于每个搜索代理的位置更新我们应用Levy飞行策略使狼群接近这三位领导者即 其中 W k → ( ℓ 1 ) \overrightarrow{W_k}(\ell1) Wk (ℓ1) 是第 k k k 个 ω 狼在第 ( ℓ 1 ) (\ell1) (ℓ1) 次迭代中的位置 r 5 r_5 r5 是 [0,1] 范围内的随机值。 a a a 是步长缩放因子。 ⊕ \oplus ⊕ 表示元素间的乘法。 L e υ y ( β ^ ) Le\upsilon y(\hat{\beta}) Leυy(β^) 是服从 Levy 分布的随机步长通过 L e v y ( β ^ ) u ∣ v ∣ 1 β ^ \begin{aligned}\boldsymbol{Levy}(\hat{\beta})\frac u{|v|^{\frac1{\hat{\beta}}}}\end{aligned} Levy(β^)∣v∣β^1u 计算得出。 u ∼ N ( 0 , σ u 2 ) u \sim N(0,\sigma_u^2) u∼N(0,σu2) v ∼ N ( 0 , σ v 2 ) v \sim N(0,\sigma_v^2) v∼N(0,σv2)其中 σ v 2 ( Γ ( 1 β ^ ) s i n ( π β ^ 2 ) Γ ( 1 β ^ 2 ) β ^ ⋅ 2 β ^ − 1 2 ) 1 β ^ , \begin{aligned}\sigma_v^2~~(\frac{\Gamma(1\hat{\beta})sin(\frac{\pi\hat{\beta}}{2})}{\Gamma(\frac{1\hat{\beta}}{2})\hat{\beta}\cdot2^{\frac{\hat{\beta}-1}{2}}})^{\frac{1}{\hat{\beta}}},\end{aligned} σv2 (Γ(21β^)β^⋅22β^−1Γ(1β^)sin(2πβ^))β^1, σ u 2 1 \sigma_u^2 1 σu21 β ^ ∈ ( 0 , 2 ] \hat{\beta} \in (0,2] β^∈(0,2] .
获得的非支配解将被存储在存档中。值得注意的是存档的容量是有限的且容量大小是一个固定值。在迭代过程中获得的新的非支配解将与存档中的解进行比较以更新存档。如果存档中没有空间且新解支配了存档中的一个或多个解则我们将启动网格机制删除当前存档中的一个或多个解以腾出空间存储新解。网格机制用于根据解的价值密度将目标空间划分为几个段。然后我们将优先考虑最集中的段落并从该段中提取并删除解决方案以提供存储新解的空间。如果存档中有空间存储新解决方案只有当新解决方案支配存档中的一个或多个解时新解决方案才能成为存档的成员。还有一种特殊情况是新添加的解决方案位于所有段之外。那么网格将被更新以包含新解决方案。
我们还需要通过比较解决方案来选择最佳领导者。为了避免在多目标搜索空间中选择与三位领导者相同的解决方案我们使用领导者选择机制来寻找三个不同的领导者。如前所述我们已经有一个存档里面存放了到目前为止获得的非支配解。在网格机制将目标空间划分为几个段落后领导者选择机制将采用轮盘赌方法在最不集中的段落中选择一个解作为三位领导者之一该段落具有最分散的函数值。如果最不集中的段落中的解决方案少于三个则会寻找次不集中的段落来选择其他领导者直到找到三个不同的领导者。因此领导者选择机制防止了算法为α、β或δ狼选择相似领导者来更新 ω 狼的位置。 所提出的 LSCMGA 的伪代码显示在算法3中。 初始化第1行 使用算法2初始化灰狼群体 X i ( i 1 , 2 , . . . , n ) X_i (i 1,2,...,n) Xi(i1,2,...,n) 和计数器 τ 1 \tau 1 τ1。这是算法开始的基础步骤确保了每个灰狼的初始位置都是根据混合解决方案初始化算法设定的。 计算每个灰狼的目标值与非支配解初始化再存档第2-3行领导者选择与位置记录第4行 通过领导力选择机制从存档中找到领导者 α \alpha α、 β \beta β、 δ \delta δ 狼并记录其位置 X α , X β , X δ X_\alpha, X_\beta, X_\delta Xα,Xβ,Xδ。这一步是为了后续的位置更新提供参考。 主循环第5-20行 这是算法的核心部分包括位置更新、参数更新、目标值计算、存档更新等步骤。 位置更新第6-8行根据三位领导者的位置更新当前搜索代理的位置依据公式(23)-(24)。参数更新第9行更新算法中的参数如 r i 1 , r i 2 , r i 3 , r i 4 , i { 1 , 2 , 3 } , r 5 , a , β ^ r_{i1}, r_{i2}, r_{i3}, r_{i4}, i \{1,2,3\}, r_5, a, \hat{\beta} ri1,ri2,ri3,ri4,i{1,2,3},r5,a,β^。目标值计算与非支配解更新第10-11行为每个搜索代理计算目标值并找出非支配解更新存档以反映获得的非支配解。存档管理第12-17行 迭代与存档返回第19-21行 更新迭代计数器 τ \tau τ 并检查是否达到迭代次数 N iter N_{\text{iter}} Niter 的条件。如果没有重复主循环。最终返回存档作为算法的输出存档包含了算法寻找到的最优解集。 这个算法通过精心设计的循环和更新机制确保了灰狼优化算法能够有效地搜索解空间并通过存档机制保留最优的非支配解。
