基于圆形堆积理论的优化无线网络的覆盖时间算法
龚丁海+谭可久
摘 要： 通过无人机（UAVs）扮演空中基站以提高无线网络的覆盖率已成为最有前景的技术。为此，研究多个无人机部署问题。首先，推导基于海拔高度和天线增益的UAVs的下行链路覆盖概率函数，然后依据圆形堆积理论计算UAVs的位置，进而在保证UAVs最大覆盖时间的同时，最大化覆盖区域，并推导了在保证目标覆盖概率时所需的UAVs数。实验结果表明，依据全向天线的波束宽度和覆盖要求，调整UAVs海拔高度，可消除UAVs间的互干扰，并最大化覆盖时间。
关键词： 无人机； 网络覆盖率； 空中基站； 位置计算； 覆盖时间
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）23?0010?05
Abstract： The air base station acted by unmanned aerial vehicles （UAVs） has become a most promising technology to enhance the coverage rate of wireless network， so the efficient deployment of multiple UAVs is studied. The UAVs′ downlink coverage probability function based on altitude and antenna gain is deduced. According to the circle packing theory， the locations of the UAVs are calculated to maximize the coverage area while guaranteeing the maximum coverage time. The required quantity of UAVs is deduced to guarantee the target coverage probability. The experimental results show that， according to the beam width and coverage requirements of the omnidirectional antenna， the altitude adjustment of the UAVs can eliminate the mutual interference of the UAVs and maximize the coverage time.
Keywords： unmanned aerial vehicle； network coverage rate； air base station； location calculation； coverage time
0 引 言
利用无人机（Unmanned Aerial Vehicles，UAVs）作为飞行基站[1]可提高无线网络的覆盖和数据传输性能，因此，基于无人机的基站也成为无线网络的研究热点。例如，移动的UAVs能够有效地建立通信链路，能及时地将消息传输到地面用户，如传感节点[2]。确实，利用UAVs作为空中基站具有很大的优势。首先，由于UAVs具有较高的高度，空中基站与地面用户形成可视距（Line?of?Sight，LOS）链路的概率更高；其次，UAVs移动便捷，部署方便。因此，UAVs能够提供快速、实时的通信服务[3]。
尽管利用UAVs作为飞行基站存在众多优势，但是仍存在一些技术挑战，这些挑战包括优化UAVs的三维空间部署、能量受限、干扰管理以及路径规划[1?5]。实际上，部署问题与能量消耗、干扰问题同等重要。
然而，目前只有少量文献关注了UAVs部署问题[4?6]。例如，文献[5]利用多个UAVs作为无线转发节点，提高UAVs的覆盖区域， 增强地面用户服务质量。然而，文献[5]并没有考虑到将UAVs作为空中基站以及它们在下行链路通信中的干扰问题。文献[6]利用进化算法搜索低空平台（Low Altitude Platforms，LAPs）的优化位置，然而，文献[6]的模型假定了LAPs的重叠区域可利用区间干扰控制，这增加了额外的通信开销。
为此，本文针对UAVs的部署问题展开分析，提出基于圆形堆积理论（Circle Packing Theory）[7]优化UAVs部署算法，记为CPTOP算法。其目的在于：通过优化UAVs的部署，以最小传输功率实现下行链路覆盖性能的最大化。在给定目标地理区域、地面用户的覆盖要求以及UAVs数量的前提下，利用圆形堆积理论优化UAVs的部署。首先，推导了基于UAVs高度和天线增益的下行链路覆盖函数；然后，利用圆形堆积理论优化部署UAVs。
1 系统模型及CPTOP算法概述
1.1 系统模型
2.3 基于圆形堆积理论求解
2.2节建立最大化覆盖寿命问题的形式化表述，如式（14）～式（17）所示。式（15）保证不存在覆盖重叠，而式（16）要求UAVs不覆盖目标地理区域以外的空间。因此，UAVs间的干扰可以避免，位于目标地理区域外的用户就不受UAVs的传输影响。
然而，由于非线性约束，求解式（14）是非常具有挑战性的。为此，利用圆形堆积理论[7]求解此问题。在圆形堆积理论中，[M]个圆应当合理地排列在给定的区域，致使堆积密度最大，并且没有圆重叠。例如，如图4所示，三个等圆以堆积理论放置于一个大圆内（目标区域），这三个圆互不重叠地放置，并使得它们占有面积的最大化。
在目标区域一定，且UAVs数固定。从图4可知，即目标区域圆半径[Rc]一定，圆的个数[M]固定。在这个前提下，如何使得[M]个圆能够最大化地覆盖目标区域。换而言之，就是[M]个UAVs最大化地覆盖目标区域。这涉及两个问题：如何放置UAVs；每个UAV的最大覆盖半径[ru。]这两个问题反映到图4中就是：如何排列圆；圆的半径的设置。
表1 列举了在给定目标区域，当[M]变化时，[ru]与[Rc]呈不同关系时，所能够覆盖的目标区域。从表1可知，[ru]减少，UAVs数量就要增加。总体覆盖区域表示UAVs所覆盖区域占目标区域的比例。
在通常情况下，在边界区域内求解圆堆积问题是非常复杂的。不存在通用的堆积策略，能够保证在任意[M]情况下，最大化覆盖目标区域。换而言之，只能在特定[M]条件下，寻找最优堆积策略，进而最大化覆盖区域。仍以图2为例，且[M]=3，目标区域半径为[Rc]。显然，如果两个相隔最远的圆间的最大距离能够被最小化，则堆积密度就最大，即在不重叠条件下，覆盖最多的目标区域。从图4可知，当三个圆的切线的交点是由三个圆心所形成的等边三角形的中心时，就能实现堆积密度最大化，即最优部署UAVs。从图4可知，这三个圆心离目标区域的圆心距离[x]为：
3 性能分析
3.1 实验环境
3.2 实验数据分析
首先考虑不同UAVs数对归一化覆盖率和归一化覆盖时间的影响。归一化覆盖百分率是指[M]个UAVs所覆盖的区域占总目标区域百分率。而归一化网络寿命是指[M]个UAVs能够保持的最大覆盖所维持的时间占总仿真时间的百分比。
从图7可知，通常目标区域越大，需要的UAV越多，进而满足覆盖率。此外，发现一个有意义的现象：为了满足至少0.7的覆盖率，要么1个UAV，要么要大于6个UAVs才能实现，换而言之，当[1<m<7]时，是无法满足0.7的覆盖率。
当目标区域半径[Rc<]5 400 m时，只利用1个UAV便能满足0.6的覆盖率。然而，当目标区域增大时，需要更多的UAVs。因此，UAV的个数依赖于覆盖率和目标区域大小。
4 结 语
本文研究了装有全向天线的多个UAVs部署问题。首先，依据LOS和NLOS链路发生概率，推导了下行链路覆盖概率；然后，建立目标函数，再利用圆形堆积理论求解目标函数，从而优化多个UAVs部署。实验结果表明，UAVs的最优海拔高度和位置可通过UAVs数、天线增益和波束宽度进行调整。
参考文献
[1] MOZAFFARI M， SAAD W， BENNIS M， et al. Drone small cells in the clouds： design， deployment and performance analysis [C]// Proceedings of 2015 IEEE Global Communications Conference. San Diego： IEEE， 2015： 1?6.
[2] FREITAS E P， HEIMFARTH T， VINEL A， et al. Cooperation among wirelessly connected static and mobile sensor nodes for surveillance applications [J]. Sensors， 2013， 13（10）： 12903?12928.
[3] BEKMEZCI I， SAHINGOZ O K， TEMEL S. Flying AdHoc networks （FANETs）： a survey [J]. Ad Hoc networks， 2013， 11（3）： 1254?1270.
[4] MOZAFFARI M， SAAD W， BENNIS M， et al. Unmanned aerial vehicle with underlaid device?to?device communications： performance and tradeoffs [J]. IEEE transactions on wireless communications， 2016， 15（6）： 3949?3963.
[5] ORFANUS D， FREITAS E P， ELIASSEN F. Self?organization as a supporting paradigm for military UAV relay networks [J]. IEEE communications letters， 2016， 20（4）： 804?807.
[6] KO?MERL J， VILHAR A. Base stations placement optimization in wireless networks for emergency communications [C]// Proceedings of 2014 IEEE International Conference on Communications. Sydney： IEEE， 2014： 200?205.
[7] TUUMINEN T. Upper bound of density for packing of equal circles in special domains in the plane [J]. Periodica polytechnica civil engineering， 2012， 44（1）： 784?785.
[8] BALANIS C A. Antenna theory： analysis and design [M]. New York： Wiley， 2016.
[9] AL?HOURANI A， KANDEEPAN S， JAMALIPOUR A. Mode?ling air?to?ground path loss for low altitude platforms in urban environments [C]// Proceedings of 2014 IEEE Global Communication Conference. Austin： IEEE， 2014： 2898?2904. </m
摘 要： 通过无人机（UAVs）扮演空中基站以提高无线网络的覆盖率已成为最有前景的技术。为此，研究多个无人机部署问题。首先，推导基于海拔高度和天线增益的UAVs的下行链路覆盖概率函数，然后依据圆形堆积理论计算UAVs的位置，进而在保证UAVs最大覆盖时间的同时，最大化覆盖区域，并推导了在保证目标覆盖概率时所需的UAVs数。实验结果表明，依据全向天线的波束宽度和覆盖要求，调整UAVs海拔高度，可消除UAVs间的互干扰，并最大化覆盖时间。
关键词： 无人机； 网络覆盖率； 空中基站； 位置计算； 覆盖时间
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）23?0010?05
Abstract： The air base station acted by unmanned aerial vehicles （UAVs） has become a most promising technology to enhance the coverage rate of wireless network， so the efficient deployment of multiple UAVs is studied. The UAVs′ downlink coverage probability function based on altitude and antenna gain is deduced. According to the circle packing theory， the locations of the UAVs are calculated to maximize the coverage area while guaranteeing the maximum coverage time. The required quantity of UAVs is deduced to guarantee the target coverage probability. The experimental results show that， according to the beam width and coverage requirements of the omnidirectional antenna， the altitude adjustment of the UAVs can eliminate the mutual interference of the UAVs and maximize the coverage time.
Keywords： unmanned aerial vehicle； network coverage rate； air base station； location calculation； coverage time
0 引 言
利用无人机（Unmanned Aerial Vehicles，UAVs）作为飞行基站[1]可提高无线网络的覆盖和数据传输性能，因此，基于无人机的基站也成为无线网络的研究热点。例如，移动的UAVs能够有效地建立通信链路，能及时地将消息传输到地面用户，如传感节点[2]。确实，利用UAVs作为空中基站具有很大的优势。首先，由于UAVs具有较高的高度，空中基站与地面用户形成可视距（Line?of?Sight，LOS）链路的概率更高；其次，UAVs移动便捷，部署方便。因此，UAVs能够提供快速、实时的通信服务[3]。
尽管利用UAVs作为飞行基站存在众多优势，但是仍存在一些技术挑战，这些挑战包括优化UAVs的三维空间部署、能量受限、干扰管理以及路径规划[1?5]。实际上，部署问题与能量消耗、干扰问题同等重要。
然而，目前只有少量文献关注了UAVs部署问题[4?6]。例如，文献[5]利用多个UAVs作为无线转发节点，提高UAVs的覆盖区域， 增强地面用户服务质量。然而，文献[5]并没有考虑到将UAVs作为空中基站以及它们在下行链路通信中的干扰问题。文献[6]利用进化算法搜索低空平台（Low Altitude Platforms，LAPs）的优化位置，然而，文献[6]的模型假定了LAPs的重叠区域可利用区间干扰控制，这增加了额外的通信开销。
为此，本文针对UAVs的部署问题展开分析，提出基于圆形堆积理论（Circle Packing Theory）[7]优化UAVs部署算法，记为CPTOP算法。其目的在于：通过优化UAVs的部署，以最小传输功率实现下行链路覆盖性能的最大化。在给定目标地理区域、地面用户的覆盖要求以及UAVs数量的前提下，利用圆形堆积理论优化UAVs的部署。首先，推导了基于UAVs高度和天线增益的下行链路覆盖函数；然后，利用圆形堆积理论优化部署UAVs。
1 系统模型及CPTOP算法概述
1.1 系统模型
2.3 基于圆形堆积理论求解
2.2节建立最大化覆盖寿命问题的形式化表述，如式（14）～式（17）所示。式（15）保证不存在覆盖重叠，而式（16）要求UAVs不覆盖目标地理区域以外的空间。因此，UAVs间的干扰可以避免，位于目标地理区域外的用户就不受UAVs的传输影响。
然而，由于非线性约束，求解式（14）是非常具有挑战性的。为此，利用圆形堆积理论[7]求解此问题。在圆形堆积理论中，[M]个圆应当合理地排列在给定的区域，致使堆积密度最大，并且没有圆重叠。例如，如图4所示，三个等圆以堆积理论放置于一个大圆内（目标区域），这三个圆互不重叠地放置，并使得它们占有面积的最大化。
在目标区域一定，且UAVs数固定。从图4可知，即目标区域圆半径[Rc]一定，圆的个数[M]固定。在这个前提下，如何使得[M]个圆能够最大化地覆盖目标区域。换而言之，就是[M]个UAVs最大化地覆盖目标区域。这涉及两个问题：如何放置UAVs；每个UAV的最大覆盖半径[ru。]这两个问题反映到图4中就是：如何排列圆；圆的半径的设置。
表1 列举了在给定目标区域，当[M]变化时，[ru]与[Rc]呈不同关系时，所能够覆盖的目标区域。从表1可知，[ru]减少，UAVs数量就要增加。总体覆盖区域表示UAVs所覆盖区域占目标区域的比例。
在通常情况下，在边界区域内求解圆堆积问题是非常复杂的。不存在通用的堆积策略，能够保证在任意[M]情况下，最大化覆盖目标区域。换而言之，只能在特定[M]条件下，寻找最优堆积策略，进而最大化覆盖区域。仍以图2为例，且[M]=3，目标区域半径为[Rc]。显然，如果两个相隔最远的圆间的最大距离能够被最小化，则堆积密度就最大，即在不重叠条件下，覆盖最多的目标区域。从图4可知，当三个圆的切线的交点是由三个圆心所形成的等边三角形的中心时，就能实现堆积密度最大化，即最优部署UAVs。从图4可知，这三个圆心离目标区域的圆心距离[x]为：
3 性能分析
3.1 实验环境
3.2 实验数据分析
首先考虑不同UAVs数对归一化覆盖率和归一化覆盖时间的影响。归一化覆盖百分率是指[M]个UAVs所覆盖的区域占总目标区域百分率。而归一化网络寿命是指[M]个UAVs能够保持的最大覆盖所维持的时间占总仿真时间的百分比。
从图7可知，通常目标区域越大，需要的UAV越多，进而满足覆盖率。此外，发现一个有意义的现象：为了满足至少0.7的覆盖率，要么1个UAV，要么要大于6个UAVs才能实现，换而言之，当[1<m<7]时，是无法满足0.7的覆盖率。
当目标区域半径[Rc<]5 400 m时，只利用1个UAV便能满足0.6的覆盖率。然而，当目标区域增大时，需要更多的UAVs。因此，UAV的个数依赖于覆盖率和目标区域大小。
4 结 语
本文研究了装有全向天线的多个UAVs部署问题。首先，依据LOS和NLOS链路发生概率，推导了下行链路覆盖概率；然后，建立目标函数，再利用圆形堆积理论求解目标函数，从而优化多个UAVs部署。实验结果表明，UAVs的最优海拔高度和位置可通过UAVs数、天线增益和波束宽度进行调整。
参考文献
[1] MOZAFFARI M， SAAD W， BENNIS M， et al. Drone small cells in the clouds： design， deployment and performance analysis [C]// Proceedings of 2015 IEEE Global Communications Conference. San Diego： IEEE， 2015： 1?6.
[2] FREITAS E P， HEIMFARTH T， VINEL A， et al. Cooperation among wirelessly connected static and mobile sensor nodes for surveillance applications [J]. Sensors， 2013， 13（10）： 12903?12928.
[3] BEKMEZCI I， SAHINGOZ O K， TEMEL S. Flying AdHoc networks （FANETs）： a survey [J]. Ad Hoc networks， 2013， 11（3）： 1254?1270.
[4] MOZAFFARI M， SAAD W， BENNIS M， et al. Unmanned aerial vehicle with underlaid device?to?device communications： performance and tradeoffs [J]. IEEE transactions on wireless communications， 2016， 15（6）： 3949?3963.
[5] ORFANUS D， FREITAS E P， ELIASSEN F. Self?organization as a supporting paradigm for military UAV relay networks [J]. IEEE communications letters， 2016， 20（4）： 804?807.
[6] KO?MERL J， VILHAR A. Base stations placement optimization in wireless networks for emergency communications [C]// Proceedings of 2014 IEEE International Conference on Communications. Sydney： IEEE， 2014： 200?205.
[7] TUUMINEN T. Upper bound of density for packing of equal circles in special domains in the plane [J]. Periodica polytechnica civil engineering， 2012， 44（1）： 784?785.
[8] BALANIS C A. Antenna theory： analysis and design [M]. New York： Wiley， 2016.
[9] AL?HOURANI A， KANDEEPAN S， JAMALIPOUR A. Mode?ling air?to?ground path loss for low altitude platforms in urban environments [C]// Proceedings of 2014 IEEE Global Communication Conference. Austin： IEEE， 2014： 2898?2904. </m
