权重选择下的低延迟飞艇自适应部署

何 烨，刘建明，李 龙，谢维佳

（1.桂林电子科技大学 计算机科学与工程学院，广西 桂林541004；2.桂林电子科技大学 机电工程学院，广西 桂林541004；3.桂林电子科技大学 电子工程与自动化学院，广西 桂林541004）

0 引 言

当前，高空平台主要是关于单平台下的飞艇通信信道建模、通信干扰、天线、传输和编码技术的研究［1－4］。然而关于多平台下的飞艇部署方面的研究很少［5，6］，文献 ［7］提出一种基于k均值聚类的方法，但文章中并没有关于卫星对其网络的影响；文献 ［8］提出一种基于遗传算法的飞艇优化模型，但它的解决方案具有较高的时间复杂度。

本文从提高覆盖率、缩短通信时延两个方面着手，开发出一种自适应的飞艇部署策略。同时，为解决飞艇覆盖下存在的空洞问题，本文在现有通信条件的基础上，采用由地面层、HAP 层和卫星层共同构成的3 层异构网络架构［9，10］，并基于此网络环境，进一步将飞艇与用户间的通信方式分为3种：直接与用户通信、通过中继飞艇与用户进行通信、通过卫星与用户通信［11］。在实际应用中，为达到最大化飞艇覆盖范围同时最小化传输时延的部署目标，飞艇部署应以自组织的方式实现相互间的协同工作，为网络使用者提供最佳无线服务。因此，本文将飞艇部署问题模型化为游戏算法，并使用带有权重选择的时延作为移动因子，完成受限空间自适应 （RSAP）学习，该算法能够保证飞艇根据用户分布和通信要求以高概率收敛到最佳位置。仿真结果表明，该方案是可行有效的。

1 异构网络

本文中异构网络由陆地层、HAP层和卫星层组成。如图1所示，该网络环境使地面用户与飞艇间的通信更加畅通。

图1 异构网络系统

（1）任务层：任务层中包含需要进行通信的用户，使用U ＝｛u1，…，ui，…，uI｝进行表示。Su＝｛s，…，，…，｝表示用户在任务层分布情况，其中表示用户ui的地理位置。

（2）HAP层：HAP层高度为h，由为用户提供服务的高空飞艇组成，使用H ＝｛h1，…，hk，…hK｝进行表示，其分布情况表示为Sh＝，…，…｝，其中代表飞艇hk的空中位置。

Qk代表飞艇组中飞艇hk的通信范围，即

式中：Rhh——飞艇间的最大通信距离，shk－shj——飞艇hk和飞艇hj之间的欧几里得距离。

Ωi代表用户与飞艇hk间通信范围，即

（3）卫星层：假定在卫星层只有一个卫星，其通信范围可覆盖所有用户和飞艇。

（4）异构网络：为简化建模，本文假设在该异构网络环境中只存在一跳中继行为。即对于不能直接被飞艇覆盖的用户的情况，可借助于卫星或其它飞艇的中继将用户和飞艇相连接，从而使地面所有用户都能够被飞艇有效访问。

用户间的通信具有3种不同的方式：通过单个飞艇进行通信、通过相邻的两个飞艇进行通信、通过飞艇以及中继卫星进行通信。如图1所示，若用户1想要与用户2进行通信，必须经过飞艇1及作为中继飞艇的飞艇3；而用户3只能借助于卫星完成与用户1间的通信。

Mi代表直接被飞艇hk覆盖的用户，即

Vi代表被其它飞艇覆盖的用户，即

Si代表既不在飞艇的直接覆盖范围也不再其间接覆盖范围下，只在卫星覆盖下的地面用户，即

通过式 （3）～式 （5）得出

即，Mi、Vi和Si是地面用户的通信划分方式。

2 部署目标

在卫星－HAP－陆地异构网络中，飞艇作为中继为地面用户提供无线通信服务。本文通过研究其部署结构对通信性能的影响，设计合理的部署模型，以实现通信中高覆盖率和低时延的综合优化。

2.1 基本延迟模型

在异构网络环境下，建立时间模型［12，13］，以便提取时延参数。该模型中将飞艇通信时延简化为飞艇和用户间距离的函数。

飞艇hk直接与地面用户通信的时延定义如下

式中：Ak、α——飞艇时延参数；

飞艇hk通过中继飞艇与地面用户通信的时延定义如下

式中：Bk、β——飞艇hk的时延参数；

卫星作为中继连接地面用户时飞艇hk与地面用户通信的时延定义如下

由式 （8）～式 （10）可以得到飞艇hk覆盖地面用户的总体时延Tk，即

为提高飞艇覆盖率，减少时延，均衡飞艇间负载，在3种延迟前设置相应权重［14］，进一步得出飞艇hk的总时延

由以上分析得出所有飞艇的总时延Φ，如下

飞艇网络目标是用最少时间完成地面用户通信需求。给出一组用户U 及其对应位置Sh，解决下面的优化问题

在限制条件下，Sh代表飞艇hk可达空间位置，其中是离散并且有限的。

飞艇网络时延由飞艇与用户距离和HAP传输能量共同决定，假设HAP发射功率不变，总时延由飞艇位置Sh＝｛，…，…｝和用户位置Su＝，…，…，｝决定。

2.2 游戏算法模型

为完成多飞艇的位置优化，将该问题模型化为游戏算法，并将每轮游戏中飞艇的位置选择归结为纳什均衡问题。

每个飞艇作为个体，不与其它飞艇合作，将该通信场景建模为非合作博弈，其中飞艇是不合作玩家，它们可移动的所有位置构成动作操作集。地面用户的分布范围是飞艇进行部署时需要覆盖的区域。游戏执行过程中，任一次t＞0，每个飞艇玩家hk∈H 按照预先规定的学习规则 （非合作博弈）以及与第 （t－1）次的交互，选择此时的动作（t－1）） Sh。飞艇玩家通过提高对地面用户的覆盖率和缩短其通信时延而获益。

使用uuk代表飞艇玩家hk的利益，是一组动作的获益之和。一个游戏的纳什均衡是当所有玩家不再获益，则达到均衡。即对任意hk∈H

定义每个高空平台飞艇玩家hk的收益满足以下关系式

3 学习算法

在介绍完飞艇部署要达到的目的和所要解决的问题后，本节将对飞艇高覆盖部署中使用的学习算法进行阐述。

若用户位置已知，飞艇可通过搜索或者遗传算法等找到自身最佳位置。然而，用户分布通常未知，甚至随着飞艇部署过程改变，导致集中式算法在实际应用中效果较差；启发式算法 （如贪婪算法）虽可应用于游戏，但该类方法只收敛到局部最优。本文采用限制性空间自适应 （RSAP）学习算法，该算法不存在中央控制器，允许飞艇以自组织方式工作，使游戏趋于纳什均衡，实现飞艇的最佳部署。

RSAP学习算法：

纳什均衡游戏规则在所有玩家眼中是次优选择。因此，为确保最优解最大化，学习算法以重复博弈的形式工作，以确定各玩家最优位置。

在博弈中，通常允许玩家执行动作操作集中的任一动作。然而飞艇部署过程中，飞艇每次只移动到以当前位置为圆心、半径固定的圆上某一位置，因此玩家只能根据其现有状态采取受限制的动作。

基于该受限制的博弈部署活动，引进限制空间自适应学习算法［15］，允许每个玩家以现有状态从一组有限操作集选择一个动作，保证博弈函数通过迭代收敛于纯纳什均衡。

表1 RSAP学习算法

该算法可归纳为一个独特稳态分布的马尔可夫过程［13］。其中

式中：珒sh——动作配置文件，珝Sh——动作配置文件空间。随着β趋于无穷大，并且操作次数t足够多，玩家就能够选择动作配置文件中使其势函数最大化的动作，最终达到使游戏结果收敛于最佳分布。

在飞艇部署游戏中，所有玩家都可以只根据局部用户分布而非全局用户分布评估其收益，且所有学习过程由玩家自己完成不需要任何监督。当t和β 足够大时，通过该学习算法就可得到飞艇最优部署。

4 仿真结果

仿真环境设置成500km×500km 区域。该片区域中存在400个用户。为模拟城市人口分布，将该区域中的用户分布于两个地域中心，且均服从高斯分布。假设高空飞艇所在高度为20km，卫星所在位置为 （250km，250km，36000km），同时使用通信距离代替时延。

图2为飞艇分布图，共有5 个飞艇分布在该片区域，其通信半径设为100km，移动半径为50km。图2 （a）中权重系数取值分别为α ＝0.93，β ＝0.01，γ ＝0.06，图2（b）中 权 重 系 数 取 值 分 别 为α ＝0.796，β ＝0.005，γ ＝0.199。由该图可知，对于不同的权重设置，飞艇部署位置不同，进而导致飞艇间的连通率及覆盖取向的改变。

图2 飞艇分布

图3所示为权重系α＝0.93，β＝0.01，γ＝0.06和α＝0.796，β＝0.005，γ＝0.199下5个飞艇移动前后时延对比图，由该图可知，飞艇移动后的通信时延显著减小。

图3 时延对比

5 结束语

本文主要讨论在异构网络环境下的飞艇部署问题。将带有权重系数的通信时延作为移动因子，建立限制性游戏算法模型使目标函数趋于纳什均衡以达到最优覆盖。仿真结果显示，①基于不同的权重系数，飞艇部署策略不同。权重系数改变，飞艇连通率改变，与飞艇直接连接用户改变。高空平台下飞艇部署策略可以根据任务性质，设置合理权重系数。②在优化部署后，时延明显减少。

［1］WANG Yanguang，YAO Wei，LI Yong.Research of stratospheric airships and its application prospects［J］.Satellite and Network，2010 （4）：18－21 （in Chinese）. ［王彦广，姚伟，李勇.平流层飞艇技术发展及其应用前景展望 ［J］.卫星与网络，2010 （4）：18－21.］

［2］Widiawan AK，Tafazolli R.High altitude platform station（HAPS）：A review of new infrastructure development for future wireless communications［J］.Wireless Personal Communications，2007，42 （3）：387－404.

［3］Mohammed A，Yang Z.Broadband communication and appli－cations from high altitude platform ［J］.International Journal of Recent Trends in Engineering，2009，1 （3）：239－243.

［4］Alejandro AZ，Jose LC，Joss AD.High－altitude platforms for wireless communications［M］.United Kingdom：Wiley Press，2008.

［5］Mohammed A，Hult T.Capacity evaluation of a high altitude platform diversity system equipped with compact MIMO antennas［J］.International Journal of Recent Trends in Engineering，2009，1 （3）：244－247.

［6］Michailidis ET，Kanatas AG.Three－dimensional HAP－MIMO channels：Modeling and analysis of space－time correlation ［J］.IEEE Transactions on Vehicular Technology，2010，59 （5）：2232－2242.

［7］Song HY.A method of mobile base station placement for high altitude platform based network with geographical clustering of mobile ground nodes ［J］.Journal of Telecommunications and Information Technology，2009 （2）：22－33.

［8］Wang X，Gao X，Zong Ru.An optimal model and solution of deployment of airships for high altitude platforms ［C］／／Proceedings of the International Wireless Communications and Signal Processing，2010.

［9］Nia MM，Rahman TA.Spectrum correlated criteria and their impacts on high altitude platform station （HAPS）and fixed satellite service （FSS）coexistence in frequency range 5，850－7，075 MHz［J］.Wireless Personal Communications，2013，69（1）：357－372.

［10］Jeon S，Ji C.Randomized and distributed self－configuration of wireless networks：Two－layer Markov random fields and near－optimality［J］.IEEE Transactions on Signal Processing，2010，58（9）：4859－4864.

［11］Wang X，Gao X，Zong R.Energy－efficient deployment of airships for high altitude platforms：A deterministic annealing approach ［C］／／Global Telecommunications Conference，2011：1－6.

［12］Sun B，Wang W，Qi Q.Satellites scheduling algorithm based on dynamic constraint satisfaction problem ［C］／／International Conference on Computer Science and Software Engineering，2008：167－170.

［13］ZHU Zhiliang，YE Ning，LIU Jun，et al.Deployment optimization algorithm for regional MANET containing near space vehicles as a part［J］.Journal of Electronics ＆Information Technology，2011，33 （4）：915－921（in Chinese）.［朱志良，叶宁，刘军，等.基于临近空间飞行器的区域自组网优化部署算法 ［J］.电子与信息学报，2011，33 （4）：915－921.］

［14］ZHOU Ling，YANG Wenyin.QoS supported geography position routing algorithm based on Baidu system ［J］.Computer Engineering，2012，38 （11）：73－76 （in Chinese）. ［周灵，杨文茵.基于北斗系统的QoS保障地理位置路由算法 ［J］.计算机工程，2012，38 （11）：73－76.］

［15］Marden JR，Arslan G，Shamma JS.Cooperative control and potential games［J］.IEEE Transactions on Systems，Man，and Cybernetics.Part B，Cybernetics，2009，39 （6）：1393－1407.