基于圓形堆積理論的優化無線網絡的覆蓋時間算法

龔丁海+譚可久

摘 要： 通過無人機（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中就是：如何排列圓；圓的半徑的設置。endprint

表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

當目標區域半徑[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.