Optimization of Total Energy Consumption for Unmanned Aerial Vehicle-enabled Wireless Sensor Networks
-
摘要: 为降低无人机(Unmanned aerial vehicle, UAV)使能的无线传感网(Wireless sensor networks, WSNs)的能耗, 延长网络生命周期, 提出一种在地面节点能量预算下系统总能耗优化方法. 首先, 提出地面节点聚类方法, 利用目标函数确定最优簇数, 改进模糊C均值(Fuzzy C-mean, FCM)算法构建能量均衡的集群, 采用退避定时器机制根据隶属度和能量值选择各集群的最优簇头, 减少地面节点的能耗; 然后, 根据已选簇头位置, 利用遗传算法规划UAV飞行轨迹, 减少UAV能耗; 最后, 通过单纯形搜索算法和连续凸逼近(Successive convex approximation, SCA)算法联合优化簇头发射功率和UAV悬停位置, 减少数据采集时系统的总能耗. 仿真结果表明, 该方法优于其他方法.Abstract: To reduce the total energy consumption for unmanned aerial vehicle (UAV) enabled wireless sensor networks (WSNs) and prolong the network lifetime, this paper proposes a scheme to optimize the total energy consumption of the system within the energy budget of ground nodes. Firstly, a clustering algorithm for ground nodes is proposed, where the optimal number of clusters is determined according to the objective function, then a fuzzy C-mean (FCM) algorithm is improved to form the energy-balanced clusters and a receding timer mechanism is employed to select the optimal cluster heads based on the affiliation and energy values, so as to reduce the energy consumption of ground nodes. Secondly, the flight trajectory of the UAV is planned according to the locations of the selected cluster heads by employing a genetic algorithm, which cuts down the energy consumption of UAV. Finally, the transmit power of the ground nodes and the UAV＇s hovering positions are optimized jointly by a simplex search algorithm and a successive convex approximation (SCA) algorithm to decrease the total energy consumption of the system for data collection. The simulation results verify that the proposal outperforms the compared schemes.
-
近年来, 无人机(Unmanned aerial vehicle, UAV)因具有机动性高、部署灵活等特点, 常被用作移动数据采集器, 与随机布撒的地面节点一起, 快速构建无人机使能的无线传感网(Unmanned aerial ve-hicle-enabled wireless sensor networks, UAV-WSNs), 执行偏远、危险或不可达地区的数据采集任务. 根据不同的应用需求, 目前针对UAV-WSNs的研究主要集中在任务完成时间最小化[1-2]、吞吐量最大化[3-4]和能耗最小化3个方面. 其中, 能耗最小化是网络对能效的高需求体现. 在大规模且节点能量有限的UAV-WSNs中, 地面节点的工作环境通常较恶劣, 不便或无法更换电池, 节点能量难以补给, 当电量耗尽时, 节点将被迫停止工作; 同时, 由于UAV常采用机载电池供电, 为减少重量和体积, 机载电池容量十分有限, 这严重制约了UAV的续航时间和飞行距离. 为保障UAV-WSNs系统地面节点数据采集的完整性, 提升UAV采集数据的有效性, 优化并降低系统能耗是UAV-WSNs急需解决的问题.
为减少地面节点的能耗, 延长网络生命周期, 传统的无线传感网(Wireless sensor networks, WSNs)常采用聚类方法降低或均衡节点的能耗. 文献[5]率先提出低功耗自适应集簇分层算法, 其主要思想是随机化选择簇头, 并使节点加入最近的簇头, 形成动态集群. 该方法可能导致能量较低的节点被选为簇头, 使其加快死亡. 针对这个问题, 文献[6]提出基于剩余能量的低功耗自适应聚类算法, 综合考虑初始能量、剩余能量等来选择最佳簇头, 从而避免低能量节点被选为簇头, 有效均衡了节点能耗, 延长了网络生命周期. 在大规模WSNs中, 集群内部距离成本(Distance, DT)增加, 基于剩余能量的低功耗自适应聚类算法难以适用. 为此, 文献[7]提出一种基于模糊C均值的最优分簇机制(Optimal clustering mechanism based on fuzzy C-mean, OCM-FCM)算法, 根据节点密度估算簇头数, 改进模糊C均值(Fuzzy C-mean, FCM)算法, 形成静态簇, 降低了集群内部的距离成本. OCM-FCM算法每轮均需根据节点剩余能量选择簇头, 这增加了集群成员间信息交换的能耗. 为此, 文献[8]提出改进能效聚类(Improved energy-efficient clustering protocol, IEECP)算法, 降低集群成员间的信息交换能耗. 在IEECP算法中, 首先改进FCM算法确定最优均衡簇数; 然后, 在簇头选择阶段, 使用退避定时器减少节点开销; 最后, 在簇头旋转阶段, 利用消耗能量与初始能量之比设置阈值, 平衡成员间的能耗. 以上研究降低或均衡了节点能耗, 延长了网络生命周期.
在UAV-WSNs中, 除了节点能耗外, UAV能耗也是影响网络性能的重要因素. 目前, UAV-WSNs能耗最小化的研究可分为以下3类: 1)只考虑地面节点的能耗最小化[9-12]. 文献[9]通过优化UAV轨迹、节点通信调度和发射功率, 在满足UAV能量预算的同时, 最小化节点能耗; 文献[10]通过优化节点唤醒调度和UAV轨迹, 最小化节点能耗; 文献[11]通过制订节点聚类、优化簇内转发树以及UAV的轨迹, 使节点能耗最小; 文献[12]提出基于四轴飞行器的无线充电平台, 为能量耗尽的节点提供充电服务, 以延长节点生命周期. 2)优化UAV能效, 减少其能耗[13-15]. 文献[13]提出在满足节点通信吞吐量需求的前提下, 联合优化UAV轨迹、节点间通信时间分配以及完成时间, 最小化UAV能耗; 文献[14]通过联合优化UAV轨迹和速度来最大化UAV能效; 文献[15]通过K均值算法对节点进行分簇并部署簇头, 同时制订离线和在线数据采集方法, 使系统部署成本和能耗最小. 单方面降低节点或UAV能耗, 可能导致UAV-WSNs能耗不匹配, 降低网络的采集效率和性能. 例如, 若节点能耗过快, 很早退出网络, 则UAV无法采集该节点数据; 若UAV能量不足, 则其中途需返回补充能量, 既定任务难以完成或完成时间过长. 3)权衡地面节点和UAV能耗, 以延长网络的生命周期[16-19]. 文献[16]分别考虑UAV圆形飞行轨迹和直线飞行轨迹2种情况, 通过优化节点发射功率和UAV轨迹, 实现能耗权衡; 文献[17]通过联合优化UAV轨迹、任务完成时间和所有节点唤醒调度, 最小化UAV和节点的能耗加权和; 文献[18]提出物联网空地节点部署协同优化方法, 将节点通信能耗和UAV移动能耗建成二次约束二次规划问题, 以平衡节点和UAV能耗; 文献[19]提出交替优化算法联合优化UAV轨迹和系统资源分配来平衡节点和UAV能耗. 文献[16-19]均考虑UAV直接与地面每个节点通信, 但在节点分布密集的大规模UAV-WSNs中, 这无疑将急速增大UAV的能耗, 使得数据采集效率降低. 为解决大规模UAV-WSNs的能耗优化问题, Zhu等[20-21]利用深度强化学习, 联合优化簇头选择和UAV的飞行路径, 使UAV-WSNs系统能耗最小.
文献[20-21]采用均匀方式聚类节点, 即固定簇的数量, 每个簇中成员数量相同. 这种分簇方式虽然能平衡节点分布均匀网络簇间的能耗, 但对于节点分布不均匀网络, 极易造成簇间能耗失衡, 从而缩短网络生命周期. 同时, 不考虑簇头的剩余能耗, 只根据簇成员间距离和UAV飞行距离选择簇头, 会导致所选簇头能耗超过自身能提供的剩余能量, 即能耗大于能量预算, 致使簇头无法完成数据传输任务, 严重影响网络传输性能. 针对以上问题, 本文提出一种UAV和节点总能耗优化方法, 根据节点分布, 确定最优簇数, 改进FCM算法均衡集群, 并优化簇头选择, 平衡和减少地面节点的能耗; 在考虑簇头能量预算下, 联合优化UAV悬停位置和簇头发射功率, 减少UAV-WSNs系统的能耗, 延长网络生命周期. 本文主要贡献如下:
1)将簇间区域重叠数学模型与UAV和节点的能耗模型相结合, 推导最优簇数; 基于次高隶属度的FCM (Second-highest membership based FCM, SHM-FCM)算法, 形成平衡集群, 降低簇内距离成本; 利用退避定时器机制根据隶属度和能量值选择最优簇头, 以平衡和减少地面节点能耗.
2)依据选择簇头的位置, 建立簇头服务顺序和UAV飞行轨迹的能耗模型, 并转化为旅行商问题, 通过遗传算法求解, 使UAV飞行能耗最小.
3)因UAV悬停位置与簇头发射功率相耦合, 直接求解困难. 通过分析发射功率与悬停位置间的关系, 采用单纯形搜索法和连续凸逼近(Successive convex approximation, SCA)算法, 联合优化UAV悬停位置和簇头发射功率, 减少UAV-WSNs系统能耗.
1. 系统模型
如图1所示, 本文构建由一架旋翼UAV和$ N $个地面节点组成的无线传感网. 地面节点被分为$ K $个集群, 每个集群含$ {{G}_{k}} $个节点, $ 1\le k\le K $, 其中包括1个簇头$ k $和${{G}_{k}}-1$个簇成员, 簇头$ k $与UAV通信能耗限制为$ {{E}_{0}} $. UAV作为移动数据采集器从数据中心出发, 以固定高度$ H $飞至簇头$ k $上方, 并下降一定高度$ {{h}_{k}} $后悬停, 采集簇头$ k $的数据. 采集完成后爬升至高度$ H $, 并飞至下一个簇头$ k' $采集数据, 直至采集完所有簇头数据后, 返回数据中心.
1.1 信道模型
假定UAV和节点均配置无线电接口, UAV可在特定频段内收发数据. 根据文献[22]中空对地路径损耗模型, UAV与簇头$ k $间的平均路径损耗表示为:
$$ {{L}_{u,k}} = P_{u,k}^{LoS}L_{u,k}^{LoS}+(1-P_{u,k}^{LoS})L_{u,k}^{NLoS} $$ (1) 式中, $ L_{u,k}^{LoS} $和$ L_{u,k}^{NLoS} $分别为UAV在簇头$ k $处视距链路和非视距链路下的路径损耗:
$$ {\left\{ \begin{split} & L_{u,k}^{LoS} = {{\left( \frac{4\pi {{f}_{c}}{{d}_{0}}}{c} \right)}^{2}}{{\left( \frac{{{d}_{u,k}}}{{{d}_{0}}} \right)}^{2}}\eta LoS \\ & L_{u,k}^{NLoS} = {{\left( \frac{4\pi {{f}_{c}}{{d}_{0}}}{c} \right)}^{2}}{{\left( \frac{{{d}_{u,k}}}{{{d}_{0}}} \right)}^{2}}\eta NLoS \\ \end{split} \right.} $$ (2) 式中, $ {{d}_{u,k}} $为UAV与簇头$ k $间的距离, $ {{f}_{c}} $为载波频率, $ c $为光速, $ {{d}_{0}} $为自由空间参考距离, $ \eta LoS $和$ \eta NLoS $分别为视距和非视距的平均额外路径损耗. $ P_{u,k}^{LoS} $为视距链路概率, 其表达式为:
$$ {P_{u,k}^{LoS} = \frac{1}{1+\alpha (\exp (-\beta (90-\alpha )))}} $$ (3) 式中, $ \alpha $和$ \beta $为传播环境参数. 簇头$ k $与UAV数据传输速率$ {{R}_{k}} $为:
$$ {{{R}_{k}} = B{{\log }_{2}}\left( 1+\frac{{{p}_{k}}}{{{L}_{u,k}}{{\sigma }^{2}}} \right)} $$ (4) 式中, $ B $为带宽, $ {{p}_{k}} $为簇头$ k $的发射功率, $ {{\sigma }^{2}} $为噪声功率.
1.2 节点能耗模型
假定各地面节点具有相同数据采集、聚合和传输能力, 且一旦被部署, 其位置固定. 每个节点均能充当簇头. 集群形成后, 每个集群中节点位置和数目固定. 成员节点定时向簇头传输所感知的数据. 簇头在能量预算范围内, 将收集的数据转发给UAV. UAV采用时分多址技术进行通信, 每次只能调度1个簇头, 且簇头与簇头间不存在干扰. 不计节点的数据感知能耗, 其节点能耗包括2个部分: 1)成员节点和簇头通信能耗; 2)簇头和UAV通信能耗.
由文献[8]的一阶无线电模型可知, 成员节点与簇头的通信能耗主要取决于簇头和成员节点间距离, 成员节点$ i $向簇头$ k $发送$ l $bit数据的能耗, 计算如下:
$$ { E_{i}^{k}(l,{{d}_{ki}}) = \left\{ \begin{split} & l{{E}_{elec}}+l{{\varepsilon }_{fs}}d_{ki}^{2},\text{ }\text{ }\text{ }{{d}_{ki}}\le {{d}_{T}} \\ & l{{E}_{elec}}+l{{\varepsilon }_{amp}}d_{ki}^{4},\text{}\text{ }{{d}_{ki}}>{{d}_{T}} \\ \end{split} \right. } $$ (5) 式中, $ {{\varepsilon }_{fs}} $和$ {{\varepsilon }_{amp}} $为传播损耗系数, $ {{d}_{T}} = \sqrt{{{\varepsilon }_{fs}}/{{\varepsilon }_{amp}}} $为传输距离阈值, $ {{E}_{elec}} $为电子系统的能耗, $ {{d}_{ki}} $为簇头$ k $与成员节点$ i $间距离, $ l $为数据大小. 在簇头$ k $的集群中, 簇头$ k $的总能耗$ {{E}_{k}} $主要包括接收成员节点数据的能耗$ E_{k}^{TR} $以及与UAV传输数据的能耗$ E_{k}^{u} $, 即:
$$ {{{E}_{k}} = E_{k}^{TR}+E_{k}^{u} = \sum\limits_{i = 1}^{{{G}_{k}}-1}{l{{E}_{elec}}}+\frac{{{G}_{k}}l{{p}_{k}}}{{{R}_{k}}}} $$ (6) 因此, 地面节点的总能耗为:
$$ {{{E}_{g}} = \sum\limits_{k = 1}^{K}{\left( \sum\limits_{i = 1}^{{{G}_{k}}-1}{E_{i}^{k}+{{E}_{k}}} \right)}} $$ (7) 1.3 UAV能耗模型
UAV能耗主要包括通信能耗和推进能耗, 因通信能耗比推进能耗小几个数量级[13], 故本文忽略通信能耗. 而UAV的推进能耗主要与飞行速度和加速度有关, 为便于分析, 参考文献[20], 本文忽略UAV加/减速过程. 因此, UAV在数据采集过程中的推进能耗包括直飞、下降、悬停、爬升所消耗的能量. 假设其直飞速度为$ {{v}_{u}} $, 下降/爬升速度为$ {{v}_{v}} $, 由文献[13]的能耗模型, 可得UAV的直飞推进功率为:
$$ \begin{split} {{P}_{prop}}({{v}_{u}}) =\;& {{P}_{i}}{{\left( \sqrt{1+\frac{v_{u}^{4}}{4v_{0}^{4}}}-\frac{v_{u}^{2}}{2v_{0}^{2}} \right)}^{\frac{1}{2}}}\;+\\ &{{P}_{0}}\left( 1+\frac{3v_{u}^{2}}{U_{{tip}}^{2}} \right)+\frac{1}{2}{{d}_{r}}\varphi r{{A}_{a}}v_{u}^{3} \end{split}$$ (8) 式中, $ {{P}_{i}} $和$ {{P}_{0}} $分别为叶片诱导功率和型阻功率, $ {{U}_{tip}} $为旋翼桨的叶尖角速度, $ {{v}_{0}} $为旋翼的平均诱导速度, $ \varphi $为空气密度, $ {{d}_{r}} $为机身阻力比, $ r $为总叶片面积与叶片扫过面积之比, $ {{A}_{a}} $为旋翼桨盘面积.
UAV处于直飞模式时, 直飞速度$ {{v}_{u}}>0 $. 由式(8), 可推导出UAV从簇头$ k $飞到簇头$ k' $时的能耗:
$$ {E_{k,k'}^{flight} = {{P}_{prop}}T_{k,k'}^{flight} = \frac{{{P}_{prop}}{{d}_{k,k'}}}{{{v}_{u}}}} $$ (9) 式中, $ T_{k,k'}^{flight} $和$ {{d}_{k,k'}} $分别为UAV从簇头$ k $至簇头$ k' $的飞行时间和距离. 定义$ {{x}_{k,k'}} $为UAV将要飞往簇头的指示变量, 若UAV从簇头$ k $采集完数据后直接飞往簇头$ k' $采集数据, 则$ {{x}_{k,k'}} = $1; 反之, $ {{x}_{k,k'}} = 0 $. 为统一表示, 假设$ k = 0 $, $ k' = 0 $表示UAV从数据中心出发或返回数据中心. 因此, UAV直线飞行的总能耗为:
$$ {{{E}_{flight}} = \sum\limits_{k = 0}^{K}{\sum\limits_{\begin{smallmatrix} k' = 0 \\ k'\ne k \end{smallmatrix}}^{K}{{{x}_{k,k'}}}}E_{k,k'}^{flight}} $$ (10) 当UAV悬停时, 其直飞速度$ {{v}_{u}} = 0 $, 此时UAV的悬停功率为:
$$ {{{P}_{hov}} = {{P}_{prop}}({{v}_{u}} = 0) = {{P}_{0}}+{{P}_{i}}} $$ (11) 当UAV采集簇头$ k $数据时, UAV的悬停能耗为:
$$ {{{E}_{hov}} = \frac{\left( {{P}_{0}}+{{P}_{i}} \right){{G}_{k}}l}{{{R}_{k}}}} $$ (12) 根据文献[22]的UAV能耗模型, 可推导出UAV下降至悬停位置的下降功率$ {{P}_{d}}({{v}_{v}}) $和爬升至飞行高度$ H $的爬升功率$ {{P}_{c}}({{v}_{v}}) $分别为:
$$ {{{P}_{d}}({{v}_{v}}) = \frac{W}{2}{{v}_{v}}-\frac{W}{2}\sqrt{v_{v}^{2}-\frac{2W}{\varphi {{A}_{a}}}}} $$ (13) $$ {{{P}_{c}}({{v}_{v}}) = \frac{W}{2}{{v}_{v}}+\frac{W}{2}\sqrt{v_{v}^{2}+\frac{2W}{\varphi {{A}_{a}}}}} $$ (14) 式中, $ W $为UAV的重力. 当UAV位于被采数据簇头$ k $上方时, 需下降高度$ {{h}_{k}} $采集数据, 并在任务完成后爬升至高度$ H $, 上升和下降过程的总能耗为:
$$ {{{E}_{dac}} = \frac{{{h}_{k}}({{P}_{d}}+{{P}_{c}})}{{{v}_{v}}}} $$ (15) 通过上述分析, UAV的总能耗表示为:
$$ {{{E}_{uav}} = {{E}_{flight}}+\sum\limits_{k = 1}^{K}{\left( {{E}_{dac}}+{{E}_{hov}} \right)}} $$ (16) 2. 问题描述及求解
2.1 优化问题描述
本文的优化目标是在满足簇头能量预算和保证所有节点数据完全被采集条件下, 通过优化簇头的发射功率$p $、无人机的下降高度$h $和飞行距离$d $, 最小化UAV-WSNs总能耗. 因此, 优化问题可表述为:
$$ \begin{split} &\,\underset{p,h,d}{\mathop{\min }}\,\text{ (}\phi {{E}_{g}}+{{E}_{uav}}) \\ &\,\text{s}\text{.t}\text{. } \\ &\sum\limits_{\begin{smallmatrix} k = 0\\ k\ne k' \end{smallmatrix}}^{K}{{{x}_{k,k'}}} = 1\text{, 0}\le k'\le K \\ &\sum\limits_{\begin{smallmatrix} k' = 0 \\ k'\ne k \end{smallmatrix}}^{K}{{{x}_{k,k'}}} = 1\text{, }0\le k\le K \\ &\sum\limits_{k,k'\in S}{{{x}_{k,k'}}}\le \left| S \right|{-1},\text{ }\left| S \right|\ge 2;\text{ }S\subset \left\{ 1, 2, \cdots , K \right\} \\ &\,0<{{p}_{k}}\le P_{k}^{\max }\text{, }0<k<K \\ &\,\frac{{{G}_{k}}l{{p}_{k}}}{{{R}_{k}}}\le {{E}_{0}}\text{, }0<k<K \\ &\,0\le {{h}_{k}}<H\text{, }0<k<K \\[-10pt] \end{split} $$ (17) 式中, $ \phi $为能耗补偿系数, 保证UAV和WSNs能耗处于相同层级[17]. 式(17)中包含6个约束条件依次表述为: 约束1和约束2确保每个簇头只被UAV访问一次; 约束3确保UAV无回路路径; 约束4表示簇头的发射功率不超过最大发射功率$ P^{\max } $; 约束5确保簇头传输数据的能耗不能超过能量预算$ {{E}_{0}} $; 约束6表明UAV下降高度不超过水平飞行高度$ H $. 该优化问题是一个约束组合优化的NP-hard问题, 无法直接求解. 故将其分解为地面节点聚类方法、UAV轨迹规划、UAV悬停位置和簇头发射功率联合优化3个子问题进行求解.
2.2 地面节点聚类方法
在UAV-WSNs中, 节点能耗取决于节点的部署和节点聚类方法, 因为节点都是随机部署的, 所以节点聚类方法对降低节点能耗至关重要. 本文所提地面节点聚类算法主要包括最优簇头数确立、集群成员平衡和簇头选择3个部分.
2.2.1 最优簇头数确立
在UAV采集数据的分簇网络中, 簇头数不仅关乎整个网络的生命周期, 还影响UAV的能耗. 若簇头数过多, 则会增加UAV的能耗; 若簇头数过少, 则簇头承担的数据任务加重, 加速簇头死亡, 影响整个网络运行. 因此, 需确定最优簇头数.
利用磁盘数学模型[8], 预测边长为$ M $的正方形中成员节点与簇头的距离, 距离预测结果可表示为$E[{{d}_{CH}}] = 1.262{{M}^{2}}/(2\pi K)$, 簇头与簇头间的距离可表示为$ E[{{d}_{k,k'}}] = 2M/\sqrt{\pi K} $. 根据地面节点距离预测表达式以及UAV和节点的能耗模型, 可确定最优簇头数. 假设每个集群中均含$N/(K-1)$个成员节点, 成员节点与簇头通信的能耗遵循自由空间模型$d < {{d}_{0}}$. 则系统总能耗$ {{E}_{total}} = \phi {{E}_{g}}+{{E}_{uav}} $, 即:
$$ \begin{split} {{E}_{total}} =\;&\phi \sum\limits_{k = 1}^{K}{\left( \sum\limits_{i = 1}^{{{G}_{k}}-1}{E_{i}^{k}+{{E}_{k}}} \right)}+{{E}_{flight}}\;+\\ &\sum\limits_{k = 1}^{K}{\left( {{E}_{dac}}+{{E}_{hov}} \right)} \text{ }\approx\\ &\sum\limits_{k = 1}^{K}{\left( \phi \left( \sum\limits_{i = 1}^{N/K}{E_{i}^{k}+{{E}_{k}}} \right)+{{E}_{dac}}+{{E}_{hov}} \right)}\;+\\ &\sum\limits_{k = 1}^{K}{\frac{2M{{P}_{prop}}}{{{v}_{u}}\sqrt{\pi K}}} \\[-15pt] \end{split}$$ (18) 给定$ {{E}_{total}} $中其他参数值, 则$ {{E}_{total}} $是只含参数$ K $的函数, 对$ K $求导, 可得:
$$ {\pi {{v}_{u}}{{E}_{dac}}{{K}^{2}}+\sqrt{\pi }M{{P}_{prop}}{{K}^{\frac{3}{2}}} = 0.631\phi Nl{{\varepsilon }_{fs}}{{v}_{u}}{{M}^{2}}} $$ (19) 利用数学工具求解上式, 获得最优簇头数$ {{K}_{opt}} $.
2.2.2 集群成员平衡
获得最优簇头数$ {{K}_{opt}} $后, 需对节点进行聚类. 目前常采用K均值算法和FCM算法对节点聚类, K均值算法采用硬分区方式聚类, 可能无法正确分类位于集群边界上的节点, 而FCM算法通过软聚类方式, 为各节点相对各簇质心分配一个隶属度, 将各节点分配到其隶属度最大的集群中, 以克服集群边界节点无法正确分类问题. 同时, 因节点通常随机部署, 采用传统FCM算法聚类会产生不平衡集群, 导致节点能耗可能失衡, 缩短网络生命周期. 为形成平衡集群, 本文SHM-FCM算法包括2个阶段: 1)利用FCM算法形成初始集群; 2)运用次高隶属度, 实行少进多出机制, 平衡集群成员数量.
初始集群的形成主要通过迭代计算各节点隶属度、簇质心和目标函数后, 各节点根据最高隶属度归属的簇质心, 形成集群. FCM算法的目标函数表示为[7]:
$$ {{{J}_{FCM}} = \sum\limits_{i = 1}^{N}{\sum\limits_{j = 1}^{K}{\mu _{ij}^{m}}}d_{ij}^{2}} $$ (20) 式中, $ {{\mu }_{ij}} $和$ {{d}_{ij}} $分别为节点$ i $对簇质心$ {{C}_{j}} $的隶属度以及两者间的欧氏距离, $ m $为模糊指标$ (m>0) $. 在满足隶属度约束条件$ \text{ }\sum\nolimits_{j = 1}^{K}{{{\mu }_{ij}}} = 1\text{ , }\mu \in \left[ 0\text{ },\text{ }1 \right] $情况下, 采用拉格朗日乘子法优化目标函数, 可得隶属度$ {{\mu }_{ij}} $和簇质心$ {{C}_{j}} $的计算公式为:
$$ {{{\mu }_{ij}} = \frac{1}{\sum\limits_{l = 1}^{K}{{{\left( \frac{{{d}_{ij}}}{{{d}_{il}}} \right)}^{\frac{2}{m-1}}}}}\text{ }} $$ (21) $$ {{{C}_{j}} = \frac{\sum\limits_{i = 1}^{N}{\mu _{ij}^{m}{{x}_{i}}}}{\sum\limits_{i = 1}^{N}{\mu _{ij}^{m}}}} $$ (22) 式中, $x_i $为第$i $个地面节点的坐标. 得到初始集群后, 需再利用次高隶属度, 实行少进多出机制, 平衡集群成员数量. 由于FCM算法利用节点最高隶属度归属集群, 一些最高隶属度与次高隶属度差值较小的节点按最高隶属度归属于相应集群. 若此集群中成员数量较大, 则按次高隶属度将部分节点归属到其他成员数量少的集群, 以平衡集群成员数量. SHM-FCM算法如算法1所示.
算法1. SHM-FCM算法
输入. $ N $, $ {{K}_{opt}} $, 迭代次数$ T $, 迭代停止条件$ \varepsilon $, 阈值$ {N}/{{{K}_{opt}}} $.
输出. 平衡集群.
1)随机生成$ {{K}_{opt}} $个初始质心;
2) 根据式(20) ~ (22), 更新隶属度矩阵, 计算新质心, 计算新目标函数;
3)重复步骤2), 直至满足迭代条件$ T $或$ \varepsilon $形成初始集群;
4) 计算各集群节点个数, 形成大于等于和小于阈值的集合A、B, 并计算各集群需添加或剔除节点个数;
5) 计算A中集群节点次高隶属度属于B的个数, 并与需剔除节点个数比较, 根据比较结果升序排列, 并对应更新A中顺序;
6) 提取A中节点最高隶属度和次高隶属度作差, 将差值升序排列, 按剔除节点个数依序将次高隶属度属于B的节点从A中剔除, 并将剔除节点添加至B;
7) 若剔除后节点数仍大于阈值, 则将多余节点按差值序列添加至A中其他集群;
8) 依次提取A中集群, 重复步骤5) ~ 7), 直至A中最后一个集群完成节点剔除;
9) 判断次高隶属度所属集群节点数是否满足阈值, 若满足, 该节点由所在集群保留, 反之剔除;
10) 各集群根据成员节点的最终位置, 由$(( {( \sum\nolimits_{i = 1}^{n}{{{x}_{i}}} )}/ {n}\; ), ( ( \sum\nolimits_{i = 1}^{n}{{{y}_{i}}} )/ {n}\; ) )$计算新质心, 形成最终集群.
2.2.3 簇头选择
集群形成后, 还需选取各集群的最优簇头, 本文采用退避定时器机制选择簇头. 在集群中, 节点$ i $通过簇质心$ {{C}_{k}} $对各节点的隶属度和能量剩余率定义其目标函数为:
$$ {F(i) = {{\alpha }_{1}}\frac{{{E}_{i}}}{{{E}_{cap}}}+{{\alpha }_{2}}\frac{\sum\limits_{j = 1}^{n}{{{d}_{j{{C}_{k}}}}}}{{{d}_{i{{C}_{k}}}}}} $$ (23) 式中, $ {{\alpha }_{1}} $、$ {{\alpha }_{2}} $为介于0至1间的常数, 且${{\alpha }_{1}}+{{\alpha }_{2}} = 1.$ $ {{E}_{i}} $和$ {{E}_{cap}} $分别为节点剩余能量和电池容量, $ {{E}_{i}}/{{E}_{cap}} $表示各节点的能量剩余率. $ \sum\nolimits_{j = 1}^{n}{{{d}_{jCk}}/{{d}_{iCk}}} $表示该集群簇质心对节点的隶属度. 能量剩余率大、隶属度高的节点更有可能被选举为簇头.
各集群成员节点根据与簇质心的距离标识自身身份(Identity, ID), 距离簇质心越近, ID值越小. 簇头选择时隙, 各节点根据式(23)设置自身定时器$ {{T}_{b}}\left( i \right) = 1/F(i) $. 定时期间, 若节点收到来自所在集群中其他节点发来的含有ID的广播消息, 它将取消自身定时器, 并成为成员节点; 若定时结束仍未收到其他节点的广播消息, 则其当选为簇头, 并向外广播消息. 若当定时结束时收到其他节点发来的广播消息, 即2个节点$ F(i) $相等. 2个节点比较自身ID和对方ID, ID值大的节点为成员节点, ID值小的节点为簇头, 并向外广播消息.
当UAV完成本次数据采集后, 在下轮数据采集时, 各集群根据式(23), 重新选择簇头和UAV通信, 以保证数据完整性.
2.3 UAV轨迹规划
UAV能耗与其飞行轨迹紧密相关, 而UAV轨迹与各簇头位置相关联. 当地面节点完成聚类后, UAV依次飞往各节点正上方采集数据, 其轨迹规划子问题可简化为:
$$ \begin{split} &\underset{d}{\mathop{\min }}\,\text{ }\sum\limits_{k = 0}^{K}{\sum\limits_{\begin{smallmatrix} k' = 0 \\ k'\ne k \end{smallmatrix}}^{K}{{{x}_{k,k'}}}}E_{k,k'}^{flight} \\ &\text{s}\text{.t}\text{. } \\ &\sum\limits_{\begin{smallmatrix} k = 0 \\ k\ne k' \end{smallmatrix}}^{K}{{{x}_{k,k'}}} = 1,\;\; 0\le k'\le K \\ &\sum\limits_{\begin{smallmatrix} k' = 0 \\ k'\ne k \end{smallmatrix}}^{K}{{{x}_{k,k'}}} = 1, \;\;0\le k\le K \\ &\sum\limits_{k,k'\in S}{{{x}_{k,k'}}}\le \left| S \right|-1,\text{ }\left| S \right|\ge 2;\text{ }S\subset \left\{ 1, 2, \cdots , K \right\} \end{split} $$ (24) 因为UAV的起点和终点相同, 式(24)所述问题为标准的旅行商问题. 旅行商问题是NP-hard问题, 无法精确求解, 目前通常采用遗传算法、粒子群算法、图搜索算法和启发式算法等智能算法寻找次优解. 与其他智能算法相比, 遗传算法通过遗传进化的方式进行搜索, 通过交叉、变异等操作产生新的解, 可以有效避免陷入局部最优解, 并且可以在较短时间内快速收敛到近似最优解. 因而, 本文采用遗传算法获得UAV的飞行轨迹.
2.4 UAV悬停位置和簇头发射功率的联合优化
在获取UAV的飞行轨迹后, UAV可依次悬停在各簇头正上方采集数据. 由于UAV与簇头间距离较大, 簇头的传输功率有限, 为可靠传输数据, UAV需下降一定高度, 通过悬停方式采集数据. 为进一步降低UAV-WSNs系统总能耗, 需要联合优化UAV的下降高度(即悬停位置)和簇头发射功率. UAV悬停位置和簇头发射功率的联合优化可归结如下:
$$ \begin{split} &{\underset{p,h}{\mathop{\min }}\,\text{ }\frac{{{P}_{d}}+{{P}_{c}}}{{{v}_{v}}}}\sum\limits_{k = 1}^{K}{{{h}_{k}}}+\frac{{{G}_{k}}l\left( {{P}_{i}}+{{P}_{0}}+\phi {{p}_{k}} \right)}{B}\;\times \\ &\quad\quad\sum\limits_{k = 1}^{K}{\log _{2}^{-1}}\left( 1+\frac{{{p}_{k}}}{{{L}_{u,k}}{{\sigma }^{2}}} \right) \\ &\text{s}\text{.t}\text{. } \\ &0<{{p}_{k}}\le P_{k}^{\max }\text{, }0<k<K \\ &0<{{\left( H-{{h}_{k}} \right)}^{2}}\le \tilde{l}\left( {{p}_{k}} \right)\text{, }0<k<K \end{split}$$ (25) 式中, $\tilde{l}\left( p_k \right)$为发射功率$p_k$的函数, 由约束条件$ {{{G}_{k}}l{{p}_{k}}}/ {{{R}_{k}}}\;\le {{E}_{0}}\text{, }0<k<K $求得, 其表达式为:
$$ {\tilde{l}(p_k) = \frac{p_k}{{{\sigma }^{2}}\varsigma \left( {{2}^{\frac{{{G}_{k}}p_kl}{{{E}_{0}}B}}}-1 \right)}} $$ (26) 式中, $\varsigma \;=\; \left( P_{u}^{LoS}\left( \eta LoS\;-\;\eta NLoS \right)\;+\;\eta NLoS \right)\times {{\left( 4\pi {{f}_{c}}/c \right)}^{2}}$, 因$\tilde{l}\left( p_k \right)$值随$p_k$的增大而减小, 则$p_k\le {{p}^{({{G}_{k}})}}$, 因此定义$ {{\tilde{P}}^{\max }} = \min \left\{ {{p}^{({{G}_{k}})}}\text{, }{{P}^{\max }} \right\} $. 其约束条件$ 0<{{p}_{k}}\le P_{k}^{\max }\text{, }0<k<K $可改写为$0 < {{p}_{k}}\le \tilde{P}_{k}^{\max }\text{, } 0\le k\le K$.
由于UAV悬停位置和簇头发射功率互相耦合, 无法直接求解式(25), 故采用单纯形搜索算法寻找簇头发射功率向量$ {{P}^{(r)}} $. 当获取$ {{P}^{(r)}} $后, 式(25)可简化为优化$ h $, 即:
$$ \begin{split} &\underset{h}{\mathop{\min }}\,\text{ }\frac{{{P}_{d}}+{{P}_{c}}}{{{v}_{v}}}\sum\limits_{k = 1}^{K}{{{h}_{k}}}+\frac{{{G}_{k}}l\left( {{P}_{i}}+{{P}_{0}}+\phi {p_{k}^{(r)}}\right)}{B}\;\times \\ &\quad\quad\quad\sum\limits_{k = 1}^{K}{\log _{2}^{-1}}\left( 1+\frac{p_{k}^{(r)}}{{{L}_{u,k}}{{\sigma }^{2}}} \right) \\ &\text{s}\text{.t}\text{. } \\ &0<{{\left( H-{{h}_{k}} \right)}^{2}}\le \tilde{l}\left( p_{k}^{(r)} \right)\text{, }0<k<K \\[-16pt] \end{split} $$ (27) 通过引用辅助变量$ \zeta $, 式(27)可转化为:
$$ \begin{split} &\underset{h,\zeta }{\mathop{\min }}\,\text{ }\zeta \\ &\text{s}\text{.t}\text{. } \\ &\frac{{{P}_{d}}+{{P}_{c}}}{{{v}_{v}}}\sum\limits_{k = 1}^{K}{{{h}_{k}}}-\zeta+\frac{{{G}_{k}}l\left( {{P}_{i}}+{{P}_{0}}+\phi p_{k}^{(r)} \right)}{B}\;\times \\ &\quad\quad\sum\limits_{k = 1}^{K}{{\tilde{f_k}}}({{h}_{k}}) \le 0 \\ &0<{{\left( H-{{h}_{k}} \right)}^{2}}\le \tilde{l}\left( p_{k}^{(r)} \right)\text{, }0<k<K \\[-16pt] \end{split} $$ (28) 式中, ${{f}_{k}}({{h}_{k}})\; =\; \log _{2}^{-1}( \;1+\;{p_{k}^{(r)}}/{( {{\sigma }^{2}}\varsigma {{(H\;-\;{{h}_{k}})}^{2}} )} )$. 因$ \tilde{f}(x) = \log _{2}^{-1}\left( 1+{a}/{x}\right) $为凹函数, 故$ {{f}_{k}}({{h}_{k}}) $是$( H- {{h}_{k}} )^{2}$的凹函数. 利用一阶泰勒展开式, 得到不等式:
$$ {\text{ }\tilde{f}(x)\le \text{ }\tilde{f}({{x}_{0}})+\text{ }{\tilde{f}}'({{x}_{0}})(x-{{x}_{0}}) = f({{x}_{0}},x) } $$ (29) 令$a = p_{k}^{*}/(\varsigma {{\sigma }^{2}})$, $x = {{( H-{{h}_{k}} )}^{2}}$, ${{x}_{0}} = {{( H-h_{k}^{[e]} )}^{2}}$, 则有:
$$ {{{f}_{k}}({{h}_{k}})\le f\left( {{\left( H-h_{k}^{[e]} \right)}^{2}},{{\left( H-{{h}_{k}} \right)}^{2}} \right) = \tilde{f}(h_{k}^{[e]},{{h}_{k}}) } $$ (30) 将${{h}^{[e]}} = ( h_{1}^{[e]},h_{2}^{[e]},\cdots ,h_{K}^{[e]} )$表示第$ e $次迭代中的优化悬停点的向量, 式(28)可转化为:
$$ \begin{split} &\underset{h,\zeta }{\mathop{\min }}\,\text{ }\zeta \\ &\text{s}\text{.t}\text{. } \\ &\frac{{{P}_{d}}+{{P}_{c}}}{{{v}_{v}}}\sum\limits_{k = 1}^{K}{{{h}_{k}}}-\zeta+\frac{{{G}_{k}}l\left( {{P}_{i}}+{{P}_{0}}+\phi p_{k}^{(r)} \right)}{B} \;\times \end{split} $$ $$ \begin{split} &\quad\quad\sum\limits_{k = 1}^{K}{{\tilde{f}}}(h_{k}^{[e]},\text{ }{{h}_{k}}) \le 0 \\ &0<{{\left( H-{{h}_{k}} \right)}^{2}}\le \tilde{l}\left( p_{k}^{(r)} \right)\text{, }0<k<K \end{split} $$ (31) 根据上述推导可知, 由于UAV的悬停位置与簇头的发射功率相互耦合, 且式(25)为非凸问题, 难以直接求解. 然而单纯形搜索算法和SCA算法具有全局搜索能力强、收敛速度快等优势, 是解决非凸问题的有效方法之一. 故本文首先采用单纯形搜索算法, 获得满足条件的簇头发射功率, 根据求得的簇头发射功率, 引入辅助变量和求解非凸问题一阶泰勒展开式, 获取全局下界, 将非凸问题式(25)逐步转化成凸优化问题式(31); 然后, 采用SCA算法求解获得UAV最优悬停位置. UAV悬停位置与簇头发射功率联合优化算法如算法2所示.
算法2. UAV悬停位置与簇头发射功率联合优化算法
输入. 初始化$ {{P}^{(0)}} $.
输出. 优化结果$ {{P}^{*}} $, $ {{h}^{*}} $.
1) 使用单纯形搜索算法搜索使目标函数值最小的$ {{P}^{(r)}} $, 将每次搜索到的$ {{P}^{(r)}} $代入式(31);
2)初始化$ {{h}^{[0]}} $, 设置步长$ {e = 0} $;
3) 将$ {{h}^{[e]}} $代入式(31), 利用凸优化工具箱求解式(31), 得到最优解$ {{h}^{[e+1]}} $;
4) $ {e = e+1} $;
5)重复步骤3)和步骤4), 直至$h^{[e+1]}-h^{[e]} \le 0.001$.
3. 仿真结果与分析
为验证本文算法的性能, 进行模拟仿真实验. 设置$N =$
1000 个节点随机分布在面积为$1 \text{ km}\; \times 1\text{ km}$的有界区域内, 簇头的最大发射功率${{P}^{{\rm{max}} }} = 25\text{ dBm}$, 簇头能量预算为${{E}_{0}}\text{ = 0}\text{.2 J.}$ UAV从位于$ (500\text{ m},500\text{ m}) $的数据中心出发, 初始飞行高度$H = 100\text{ m}$, 依次飞至各簇头上空采集数据. 节点和UAV能耗参数与文献[13, 20]一致, 其他参数设置见表1.表 1 仿真参数Table 1 Simulation parameter参数 参数值 参数 参数值 $\alpha$ 0.03 ${{v}_{v}}$ 10 m/s $\beta$ 10 ${{E}_{cap}}$ 50 J $\eta LoS$ 3 dB $l$ 1 Mb $\eta NLoS$ 13 dB ${{\alpha }_{1}}$,${{\alpha }_{2}}$ 0.5 ${{d}_{0}}$ 1 m $\phi $ 1000 ${{\sigma }^{2}}$ −174 dBm/Hz ${{v}_{u}}$ 15 m/s 3.1 最优簇数验证
采用表1、文献[13, 20]的数据和约束条件$ {{{G}_{k}}l{{p}_{k}}}/{{{R}_{k}}}\;\le {{E}_{0}}\text{, }0<k<K $对式(19)进行验证, 得到最佳簇头数为$ 37\le {{K}_{opt}}\le 44 $. 在模拟仿真实验中, 将簇头数从36改变至45, 进行一轮模拟, 不同簇头个数的系统总能耗如图2所示. 可以看出, 最优簇头数为40, 这与式(19)结果吻合. 当网络中簇头数较少时, 虽然减少了UAV能耗, 但增加了簇头与成员节点的能耗, 缩短了网络生命周期. 当网络中簇头数较多时, 虽然延长了网络生命周期, 但增加了UAV能耗, 会导致UAV不能采集完网络的感知数据.
图 2 不同簇头个数的系统总能耗Fig. 2 Total energy consumption of the system with different numbers of cluster head3.2 均衡集群形成评估
通过对比OCM-FCM算法和IEECP算法的集群规模变化(Variation in size of cluster, VSC)值和集群内距离成本值, 以验证本文SHM-FCM算法均衡集群的效果. 与传统FCM算法随机选取簇质心不同, OCM-FCM算法是根据节点密度选取初始簇质心, 使得簇质心始终围绕节点密度高的区域. 首先, 计算节点密度, 选取节点密度高的区域为初始簇质心; 然后, 根据簇质心, 迭代计算各节点隶属度矩阵、新簇质心和新目标函数; 最后, 形成集群. IEECP算法首先利用传统FCM算法形成初始集群; 然后, 计算各初始集群簇质心与各节点的距离; 最后, 将距离最近并满足簇内阈值数的节点添加至各簇质心对应集群, 形成最终集群. 用VSC值表征集群间的节点数目的差异:
$$ {\text{VSC} = \frac{\sum\limits_{k = 1}^{K}{{{\left| {{G}_{k}}-\bar{x} \right|}^{2}}}}{K} } $$ (32) 式中, $ \bar{x} $表示集群中节点的平均值. VSC值越小, 越能表征集群成员数目平衡, 效果越好, 比较结果如图3和表2所示.
表 2 不同算法的VSC值比较Table 2 Comparison of VSC values for different algorithms实验次数 OCM-FCM IEECP SHM-FCM 1 428.40 52.85 48.50 2 362.35 49.05 46.70 3 271.15 66.55 57.65 4 254.20 51.75 43.45 5 272.40 58.65 50.50 6 387.50 52.90 31.75 7 329.15 49.35 43.54 8 289.45 58.45 62.55 9 290.25 55.80 55.20 10 319.15 46.75 37.50 用DT值评估集群内成本值, 来表征平衡集群的形成对网络总能耗的影响:
$$ {\text{DT} = \sum\limits_{j = 1}^{K}{\sum\limits_{i = 1}^{{{G}_{k}}}{d{{({{x}_{i}},{{C}_{j}})}^{2}}}}} $$ (33) 式中, $ d({{x}_{i}},{{C}_{j}}) $表示节点$ {{x}_{i}} $到簇质心$ {{C}_{j}} $的距离. 在形成平衡簇时, DT值越小, 表示网络总能耗越小, 效果越好, 比较结果如图4所示.
由图3和表2可知, SHM-FCM算法形成集群的VSC值明显小于OCM-FCM算法, 大多数也小于IEECP. 由图4可知, SHM-FCM算法的DT值均小于OCM-FCM算法和IEECP算法. 由图3、表2和图4分析可知, SHM-FCM算法和IEECP算法的VSC值小于OCM-FCM算法, 但SHM-FCM算法和OCM-FCM算法的DT值小于IEECP算法. 其原因主要是OCM-FCM算法选择节点密度高处为聚类中心形成集群, 使得节点密度高处集群成员节点较多, 节点密度低处集群成员节点较少, 导致各集群成员不均衡, 虽有利于降低DT值, 但会相应地增加VSC值; IEECP算法利用簇内节点阈值数与距离形成集群, 为满足簇内节点阈值数强制加入或剔除节点, 使其只能保证VSC值偏小, 不能保证DT值偏小; 而SHM-FCM算法尽可能选择使各集群成员节点均衡处作为聚类中心, 并利用节点次高隶属度实行少进多出机制, 可以在保证VSC值偏小的同时, 保证DT值偏小. 在第8次实验时, SHM-FCM算法的VSC值略高于IEECP算法, 但DT值比IEECP算法小. 其主要原因是网络中存在某区域节点分布太稀疏的极端情况, IEECP算法将分散节点加入最近的簇, 而SHM-FCM算法是将分散节点组织成1个集群. 总之, 与现有的分簇算法相比, SHM-FCM算法在平衡集群成员方面具有明显的优势.
3.3 算法性能评估
通过对比IEECP算法、OCM-FCM算法的网络生命周期和网络能耗, 以验证本文算法的有效性. 在模拟实验中, 节点能量在0 ~ 50 J间随机生成. 网络生命周期可分为3个阶段, 即第1个节点死亡(First node dies, FND)前的高效稳定阶段、一半节点死亡(Half of the nodes die, HND)前的有效稳定阶段和位于HND后和最后1个节点死亡(Last node dies, LND)前的不稳定阶段. 若以最后1个节点的死亡时间作为网络的生命周期, 则第1个节点死亡时间越大, 网络高效稳定阶段越长, 这意味着所有节点参与数据采集和传输的时间越长. 因此, 为评估网络的稳定性, 采用加权第1节点死亡(Weighted first node dies, WFND)来反映节点参与网络的状态和网络稳定性[8]:
$$ {\text{WFND} = \frac{\text{FND}}{\text{LND }-\text{ FND}}} $$ (34) 由式(34)可以看出, FND越大, 则WFND值越高, 即第1个节点死亡时间越晚, 网络稳定性越好. WFND越大, 意味着相同能量预算下, 网络能耗越少, 所有节点工作时间越长, 网络性能越好.
图5、表3展示了不同算法下节点存活数和网络稳定性的比较. 可以看出, 因为节点能量是随机生成的, 在IEECP和OCM-FCM算法中, 能量较低的节点很快死亡. 原因是这2种算法在簇头选择方面, 均未考虑集群内部的距离成本对集群内节点的能耗, 进而导致低能量节点退出网络. 与其他算法相比, SHM-FCM算法不管是FND、WFND还是LND, 均表现出较好的网络稳定性, 并能延长所有节点的生命周期.
表 3 网络稳定性比较Table 3 Comparison of network stability算法名称 FND HND LND WFND OCM-FCM 1 75 154 0.0065 IEECP 2 104 226 0.0089 SHM-FCM 9 176 416 0.0220 网络能耗性能是衡量网络能量利用率的关键因素, 由图6可知, SHM-FCM算法能耗性能最优. 在运行100轮时, 与IEECP和OCM-FCM算法相比, SHM-FCM算法能耗分别节省了36.51%和43.52%. 其主要原因是SHM-FCM算法考虑成员节点间的距离成本, 而且节点隶属度计算和簇内通信确定距离等能量开销均由知道整个网络全局信息的数据中心执行. 因此, SHM-FCM算法的网络剩余能量最多, 即网络能耗最低.
3.4 簇头与UAV的能耗评估
图7展现了不同数据采集方式下的系统能耗, 即本文方法和2种UAV悬停位置下采集方法. 2种悬停方法分别是固定发射功率、簇头周边悬停[13]和固定发射功率、几何中心悬停[20]. 由图7可知, 本文方法能耗最少, 优于其他方法. 这是因为其他方法只能保证UAV或簇头的能耗最小, 不能保证整个系统能耗最小. 而本文方法则根据簇头所含数据量和簇头能量预算, 自适应优化簇头发射功率和UAV悬停位置, 从而减少整个系统的能耗. 此外, 图7还给出了本文方法下簇头传输数据能耗和UAV各种飞行模式下的能耗. 由于UAV的通信能耗远小于推进能耗, 为方便分析, 在仿真实验时, 忽略这个参数[9-11, 13-15, 17, 19]. 同时, 本文在UAV能耗建模时, 由于簇头节点间距较远, UAV的推进能耗主要来自于飞行和悬停, 故忽略了加/减速过程, 将其简化成理想的匀速飞行. 由图7可知, UAV飞行能耗最高, 悬停能耗次之, 下降和爬升能耗较小, 簇头上传数据能耗最小. 为便于比较, 图7中表示的簇头上传数据能耗是乘以3个数量级后的值. 值得注意的是, 在实际应用时, 若簇头位置间隔较小或UAV需要频繁启停时, 加/减速所消耗的能量不能忽视, 在问题建模和仿真时需考虑这个因素.
3.5 UAV飞行路径
图8展现了UAV飞行轨迹, 由于文献[20]和本文方法UAV均选择悬停在节点正上方采集数据, 当簇头服务顺序相同时, 其飞行轨迹平面图重合. 由图8可知, 文献[13] UAV悬停在簇头周围的轨迹比悬停在簇头上方的轨迹更短, 其飞行能耗最小, 但不能代表其系统总能耗最小. 其主要原因为当簇头能量受限并以固定功率传输数据时, UAV距离簇头越远, 数据传输速率越慢, UAV悬停时间越长, 其悬停能耗占比增大, 而且簇头传输时间越长其能耗越大, 从而使得系统能耗增大. 同理, 文献[20]以固定高度悬停在簇头正上方采集数据以减少簇头能耗为目的, 当簇头以固定功率发送数据时, 无疑会增加无人机的悬停能耗, 而使得整个系统能耗增加. 总之, 合理优化UAV的悬停位置和簇头发射功率是降低系统能耗最有效的方法.
3.6 系统参数对性能的影响
图9给出了在单一集群内, 簇头能量预算相同$ {{E}_{0}} = 0.2\text{ J} $, 簇成员数量${{G}_{k}}$不同的条件下, 联合优化UAV悬停位置和簇头发射功率与系统能耗间的关系. 由图9可知, 随着簇头上传数据量的增加, 最优发射功率逐渐减少, UAV悬停位置越靠近簇头, 以可靠完成数据采集, 这使得系统能耗增大. 其原因是簇头上传的数据量较大时, 簇头需要消耗的能量越多, 为满足簇头自身的能量预算, 需减少发射功率, 这导致UAV的悬停位置必须逼近簇头, 以减少簇头上传数据时的能耗.
图 9 不同簇成员个数时簇头发射功率与系统能耗/悬停位置的关系Fig. 9 Relationship between cluster head transmit power and system energy consumption/hovering positions with different numbers of cluster members图10展示了在单一集群内, 成员节点个数相同$ {{G}_{k}} = 25 $, 但簇头能量预算$ {{E}_{0}} $不同条件下, 联合优化UAV悬停位置以及簇头发射功率与系统能耗间的关系. 由图10可知, 随着$ {{E}_{0}} $减少, 最优发射功率逐渐减少, 系统能耗增大. 结合图10(a)、图10(b)可知, 集群内成员节点数量相同, 即簇头所含数据量相同, 随着簇头能量预算的减少, 簇头的最优发射功率逐渐降低. 为确保无人机能够完全采集簇头数据, UAV悬停位置需更靠近簇头, 以降低簇头能耗. 但UAV越靠近簇头, 其飞行能耗就越大, 从而使整个系统能耗增加.
图 10 不同簇头能量预算对系统能耗的影响Fig. 10 Impact of different cluster head energy budgets on system energy consumption4. 结束语
本文研究了UAV-WSNs节能通信, 通过分析UAV和WSNs能耗模型建立优化函数, 在满足节点能量预算情况下, 最小化UAV-WSNs总能耗. 首先, 提出地面节点聚类算法选择簇头, 降低节点能耗; 其次, 利用遗传算法优化UAV飞行轨迹, 降低UAV飞行能耗; 最后, 通过单纯形搜索算法和SCA算法联合优化簇头发射功率和UAV悬停位置, 减少数据采集时系统的总能耗. 数值仿真实验结果验证了本文方法的有效性.
-
图 2 不同簇头个数的系统总能耗
Fig. 2 Total energy consumption of the system with different numbers of cluster head
图 9 不同簇成员个数时簇头发射功率与系统能耗/悬停位置的关系
Fig. 9 Relationship between cluster head transmit power and system energy consumption/hovering positions with different numbers of cluster members
图 10 不同簇头能量预算对系统能耗的影响
Fig. 10 Impact of different cluster head energy budgets on system energy consumption
表 1 仿真参数
Table 1 Simulation parameter
参数 参数值 参数 参数值 $\alpha$ 0.03 ${{v}_{v}}$ 10 m/s $\beta$ 10 ${{E}_{cap}}$ 50 J $\eta LoS$ 3 dB $l$ 1 Mb $\eta NLoS$ 13 dB ${{\alpha }_{1}}$,${{\alpha }_{2}}$ 0.5 ${{d}_{0}}$ 1 m $\phi $ 1000 ${{\sigma }^{2}}$ −174 dBm/Hz ${{v}_{u}}$ 15 m/s 
下载: 导出CSV
表 2 不同算法的VSC值比较
Table 2 Comparison of VSC values for different algorithms
实验次数 OCM-FCM IEECP SHM-FCM 1 428.40 52.85 48.50 2 362.35 49.05 46.70 3 271.15 66.55 57.65 4 254.20 51.75 43.45 5 272.40 58.65 50.50 6 387.50 52.90 31.75 7 329.15 49.35 43.54 8 289.45 58.45 62.55 9 290.25 55.80 55.20 10 319.15 46.75 37.50
下载: 导出CSV
表 3 网络稳定性比较
Table 3 Comparison of network stability
算法名称 FND HND LND WFND OCM-FCM 1 75 154 0.0065 IEECP 2 104 226 0.0089 SHM-FCM 9 176 416 0.0220
下载: 导出CSV
-
[1] Li J X, Zhao H T, Wang H J, Gu F L, Wei J B, Yin H, et al. Joint optimization on trajectory, altitude, velocity, and link scheduling for minimum mission time in UAV-aided data collection. IEEE Internet of Things Journal, 2019, 7(2): 1464−1475 [2] 王峰, 黄子路, 韩孟臣, 邢立宁, 王凌. 基于KnCMPSO算法的异构无人机协同多任务分配. 自动化学报, 2023, 49(2): 399−414 doi: 10.16383/j.aas.c210696Wang Feng, Huang Zi-Lu, Han Meng-Chen, Xing Li-Ning, Wang Ling. A knee point based coevolution multi-objective particle swarm optimization algorithm for heterogeneous UAV cooperative multi-task allocation. Acta Automatica Sinica, 2023, 49(2): 399−414 doi: 10.16383/j.aas.c210696 [3] Samir M, Sharafeddine S, Assi C M, Nguyen T M, Ghrayeb A. UAV trajectory planning for data collection from time-constr-ained IoT devices. IEEE Transactions on Wireless Communications, 2019, 19(1): 34−46 [4] 刘志新, 赵松晗, 杨毅, 袁亚洲. 智能反射面辅助的无人机无线携能通信网络吞吐量最大化算法研究. 电子与信息学报, 2022, 44(7): 2325−2331 doi: 10.11999/JEIT220195Liu Zhi-Xin, Zhao Song-Han, Yang Yi, Yuan Ya-Zhou. Thro-ugh put maximization algorithm for intelligent reflecting surface-aided unmanned aerial vehicle communication networks with wireless energy transfer. Journal of Electronics & Information Technology, 2022, 44(7): 2325−2331 doi: 10.11999/JEIT220195 [5] Heinzelman W B, Chandrakasan A P, Balakrishnan H. Approximate policy-based accelerated deep reinforcement learning. An Application-specific Protocol Architecture for Wireless Microsensor Networks, 2002, 1(4): 660−670 [6] Behera T M, Mohapatra S K, Samal U C, Khan S M, Daneshmand M, Gandomi A H. Residual energy-based cluster-head selection in WSNs for IoT application. IEEE Internet of Things Journal, 2019, 6(3): 5132−5139 doi: 10.1109/JIOT.2019.2897119 [7] Su S C, Zhao S G. An optimal clustering mechanism based on Fuzzy-C means for wireless sensor networks. Sustainable Computing: Informatics and Systems, 2018, 18: 127−134 doi: 10.1016/j.suscom.2017.08.001 [8] Hassan A A H, Shah W M, Habeb A H H, Othman M F I, Al-Mhiqani M N. An improved energy-efficient clustering protocol to prolong the lifetime of the WSN-based IoT. IEEE Access, 2020, 8: 200500−200517 doi: 10.1109/ACCESS.2020.3035624 [9] Zhan C, Lai H. Energy minimization in internet-of-things system based on rotary-wing UAV. IEEE Wireless Communications Letters, 2019, 8(5): 1341−1344 doi: 10.1109/LWC.2019.2916549 [10] Zhan C, Zeng Y, Zhang R. Energy-efficient data collection in UAV enabled wireless sensor network. IEEE Wireless Communications Letters, 2017, 7(3): 328−331 [11] Ebrahimi D, Sharafeddine S, Ho P H, Assi C. UAV-aided projection-based compressive data gathering in wireless sensor networks. IEEE Internet of Things Journal, 2018, 6(2): 1893−1905 [12] Chen J M, Li S Y, Chen S, He S B, Shi Z G. Q-charge: A quadcopter-based wireless charging platform for large-scale sensing applications. IEEE Network, 2017, 31(6): 56−61 doi: 10.1109/MNET.2017.1700071 [13] Zeng Y, Xu J, Zhang R. Energy minimization for wireless communication with rotary-wing UAV. IEEE Transactions on Wireless Communications, 2019, 18(4): 2329−2345 doi: 10.1109/TWC.2019.2902559 [14] Zeng Y, Zhang R. Energy-efficient UAV communication with trajectory optimization. IEEE Transactions on Wireless Communications, 2017, 16(6): 3747−3760 doi: 10.1109/TWC.2017.2688328 [15] Ghdiri O, Jaafar W, Alfattani S, Abderrazak J B, Yanikomeroglu H. Offline and online UAV-enabled data collection in time-constrained IoT networks. IEEE Transactions on Green Communications and Networking, 2021, 5(4): 1918−1933 doi: 10.1109/TGCN.2021.3104801 [16] Yang D C, Wu Q Q, Zeng Y, Zhang R. Energy tradeoff in ground-to-UAV communication via trajectory design. IEEE Transactions on Vehicular Technology, 2018, 67(7): 6721−6726 doi: 10.1109/TVT.2018.2816244 [17] Zhan C, Huang R J. Energy minimization for data collection in wireless sensor networks with UAV. In: Proceedings of the IEEE Global Communications Conference. Waikoloa, USA: IEEE, 2019. 1−6 [18] 王巍, 彭力, 赵继军, 朱天宇, 崔益豪, 田立勤. 基于旋翼无人机近地面空间应急物联网节点动态协同部署. 自动化学报, 2021, 47(8): 2002−2015 doi: 10.16383/j.aas.c180146Wang Wei, Peng Li, Zhao Ji-Jun, Zhu Tian-Yu, Cui Yi-Hao, Tian Li-Qin. Dynamic cooperative deployment of emergency internet of things near ground space based on drone. Acta Automatica Sinica, 2021, 47(8): 2002−2015 doi: 10.16383/j.aas.c180146 [19] 李安, 戴龙斌, 余礼苏, 王振. 加权能耗最小化的无人机辅助移动边缘计算资源分配策略. 电子与信息学报, 2022, 44(11): 3858−3865 doi: 10.11999/JEIT210832Li An, Dai Long-Bin, Yu Li-Su, Wang Zhen. Resource allocation for unmanned aerial vehicle-assisted mobile edge computing to minimize weighted energy consumption. Journal of Electronics & Information Technology, 2022, 44(11): 3858−3865 doi: 10.11999/JEIT210832 [20] Zhu B T, Bedeer E, Nguyen H H, Barton R, Henry J. UAV trajectory planning in wireless sensor networks for energy consumption minimization by deep reinforcement learning. IEEE Transactions on Vehicular Technology, 2021, 70(5): 9540−9554 [21] Zhu B T, Bedeer E, Nguyen H H, Barton R, Henry J. Joint cluster head selection and trajectory planning in UAV-aided IoT networks by reinforcement learning with sequential model. IEEE Internet of Things Journal, 2021, 9(14): 12071−12084 [22] Mozaffari M, Saad W, Bennis M, Debbah M. Mobile unmanned aerial vehicles (UAVs) for energy-efficient Internet of Things communications. IEEE Internet of Things Journal, 2017, 16(11): 7574−7589 -
下载:
计量
- 文章访问数: 698
- HTML全文浏览量: 247
- PDF下载量: 103
- 被引次数: 0
