基于圓形堆積理論的優(yōu)化無線網(wǎng)絡(luò)的覆蓋時(shí)間算法

龔丁海+譚可久

摘 要： 通過無人機(jī)（UAVs）扮演空中基站以提高無線網(wǎng)絡(luò)的覆蓋率已成為最有前景的技術(shù)。為此，研究多個(gè)無人機(jī)部署問題。首先，推導(dǎo)基于海拔高度和天線增益的UAVs的下行鏈路覆蓋概率函數(shù)，然后依據(jù)圓形堆積理論計(jì)算UAVs的位置，進(jìn)而在保證UAVs最大覆蓋時(shí)間的同時(shí)，最大化覆蓋區(qū)域，并推導(dǎo)了在保證目標(biāo)覆蓋概率時(shí)所需的UAVs數(shù)。實(shí)驗(yàn)結(jié)果表明，依據(jù)全向天線的波束寬度和覆蓋要求，調(diào)整UAVs海拔高度，可消除UAVs間的互干擾，并最大化覆蓋時(shí)間。

關(guān)鍵詞： 無人機(jī)； 網(wǎng)絡(luò)覆蓋率； 空中基站； 位置計(jì)算； 覆蓋時(shí)間

中圖分類號(hào)： TN911?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

利用無人機(jī)（Unmanned Aerial Vehicles，UAVs）作為飛行基站[1]可提高無線網(wǎng)絡(luò)的覆蓋和數(shù)據(jù)傳輸性能，因此，基于無人機(jī)的基站也成為無線網(wǎng)絡(luò)的研究熱點(diǎn)。例如，移動(dòng)的UAVs能夠有效地建立通信鏈路，能及時(shí)地將消息傳輸?shù)降孛嬗脩?，如傳感?jié)點(diǎn)[2]。確實(shí)，利用UAVs作為空中基站具有很大的優(yōu)勢(shì)。首先，由于UAVs具有較高的高度，空中基站與地面用戶形成可視距（Line?of?Sight，LOS）鏈路的概率更高；其次，UAVs移動(dòng)便捷，部署方便。因此，UAVs能夠提供快速、實(shí)時(shí)的通信服務(wù)[3]。

盡管利用UAVs作為飛行基站存在眾多優(yōu)勢(shì)，但是仍存在一些技術(shù)挑戰(zhàn)，這些挑戰(zhàn)包括優(yōu)化UAVs的三維空間部署、能量受限、干擾管理以及路徑規(guī)劃[1?5]。實(shí)際上，部署問題與能量消耗、干擾問題同等重要。

然而，目前只有少量文獻(xiàn)關(guān)注了UAVs部署問題[4?6]。例如，文獻(xiàn)[5]利用多個(gè)UAVs作為無線轉(zhuǎn)發(fā)節(jié)點(diǎn)，提高UAVs的覆蓋區(qū)域， 增強(qiáng)地面用戶服務(wù)質(zhì)量。然而，文獻(xiàn)[5]并沒有考慮到將UAVs作為空中基站以及它們?cè)谙滦墟溌吠ㄐ胖械母蓴_問題。文獻(xiàn)[6]利用進(jìn)化算法搜索低空平臺(tái)（Low Altitude Platforms，LAPs）的優(yōu)化位置，然而，文獻(xiàn)[6]的模型假定了LAPs的重疊區(qū)域可利用區(qū)間干擾控制，這增加了額外的通信開銷。

為此，本文針對(duì)UAVs的部署問題展開分析，提出基于圓形堆積理論（Circle Packing Theory）[7]優(yōu)化UAVs部署算法，記為CPTOP算法。其目的在于：通過優(yōu)化UAVs的部署，以最小傳輸功率實(shí)現(xiàn)下行鏈路覆蓋性能的最大化。在給定目標(biāo)地理區(qū)域、地面用戶的覆蓋要求以及UAVs數(shù)量的前提下，利用圓形堆積理論優(yōu)化UAVs的部署。首先，推導(dǎo)了基于UAVs高度和天線增益的下行鏈路覆蓋函數(shù)；然后，利用圓形堆積理論優(yōu)化部署UAVs。

1 系統(tǒng)模型及CPTOP算法概述

1.1 系統(tǒng)模型

2.3 基于圓形堆積理論求解

2.2節(jié)建立最大化覆蓋壽命問題的形式化表述，如式（14）～式（17）所示。式（15）保證不存在覆蓋重疊，而式（16）要求UAVs不覆蓋目標(biāo)地理區(qū)域以外的空間。因此，UAVs間的干擾可以避免，位于目標(biāo)地理區(qū)域外的用戶就不受UAVs的傳輸影響。

然而，由于非線性約束，求解式（14）是非常具有挑戰(zhàn)性的。為此，利用圓形堆積理論[7]求解此問題。在圓形堆積理論中，[M]個(gè)圓應(yīng)當(dāng)合理地排列在給定的區(qū)域，致使堆積密度最大，并且沒有圓重疊。例如，如圖4所示，三個(gè)等圓以堆積理論放置于一個(gè)大圓內(nèi)（目標(biāo)區(qū)域），這三個(gè)圓互不重疊地放置，并使得它們占有面積的最大化。

在目標(biāo)區(qū)域一定，且UAVs數(shù)固定。從圖4可知，即目標(biāo)區(qū)域圓半徑[Rc]一定，圓的個(gè)數(shù)[M]固定。在這個(gè)前提下，如何使得[M]個(gè)圓能夠最大化地覆蓋目標(biāo)區(qū)域。換而言之，就是[M]個(gè)UAVs最大化地覆蓋目標(biāo)區(qū)域。這涉及兩個(gè)問題：如何放置UAVs；每個(gè)UAV的最大覆蓋半徑[ru。]這兩個(gè)問題反映到圖4中就是：如何排列圓；圓的半徑的設(shè)置。endprint

表1 列舉了在給定目標(biāo)區(qū)域，當(dāng)[M]變化時(shí)，[ru]與[Rc]呈不同關(guān)系時(shí)，所能夠覆蓋的目標(biāo)區(qū)域。從表1可知，[ru]減少，UAVs數(shù)量就要增加?？傮w覆蓋區(qū)域表示UAVs所覆蓋區(qū)域占目標(biāo)區(qū)域的比例。

在通常情況下，在邊界區(qū)域內(nèi)求解圓堆積問題是非常復(fù)雜的。不存在通用的堆積策略，能夠保證在任意[M]情況下，最大化覆蓋目標(biāo)區(qū)域。換而言之，只能在特定[M]條件下，尋找最優(yōu)堆積策略，進(jìn)而最大化覆蓋區(qū)域。仍以圖2為例，且[M]=3，目標(biāo)區(qū)域半徑為[Rc]。顯然，如果兩個(gè)相隔最遠(yuǎn)的圓間的最大距離能夠被最小化，則堆積密度就最大，即在不重疊條件下，覆蓋最多的目標(biāo)區(qū)域。從圖4可知，當(dāng)三個(gè)圓的切線的交點(diǎn)是由三個(gè)圓心所形成的等邊三角形的中心時(shí)，就能實(shí)現(xiàn)堆積密度最大化，即最優(yōu)部署UAVs。從圖4可知，這三個(gè)圓心離目標(biāo)區(qū)域的圓心距離[x]為：

3 性能分析

3.1 實(shí)驗(yàn)環(huán)境

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

首先考慮不同UAVs數(shù)對(duì)歸一化覆蓋率和歸一化覆蓋時(shí)間的影響。歸一化覆蓋百分率是指[M]個(gè)UAVs所覆蓋的區(qū)域占總目標(biāo)區(qū)域百分率。而歸一化網(wǎng)絡(luò)壽命是指[M]個(gè)UAVs能夠保持的最大覆蓋所維持的時(shí)間占總仿真時(shí)間的百分比。

從圖7可知，通常目標(biāo)區(qū)域越大，需要的UAV越多，進(jìn)而滿足覆蓋率。此外，發(fā)現(xiàn)一個(gè)有意義的現(xiàn)象：為了滿足至少0.7的覆蓋率，要么1個(gè)UAV，要么要大于6個(gè)UAVs才能實(shí)現(xiàn)，換而言之，當(dāng)[1

當(dāng)目標(biāo)區(qū)域半徑[Rc<]5 400 m時(shí)，只利用1個(gè)UAV便能滿足0.6的覆蓋率。然而，當(dāng)目標(biāo)區(qū)域增大時(shí)，需要更多的UAVs。因此，UAV的個(gè)數(shù)依賴于覆蓋率和目標(biāo)區(qū)域大小。

4 結(jié) 語

本文研究了裝有全向天線的多個(gè)UAVs部署問題。首先，依據(jù)LOS和NLOS鏈路發(fā)生概率，推導(dǎo)了下行鏈路覆蓋概率；然后，建立目標(biāo)函數(shù)，再利用圓形堆積理論求解目標(biāo)函數(shù)，從而優(yōu)化多個(gè)UAVs部署。實(shí)驗(yàn)結(jié)果表明，UAVs的最優(yōu)海拔高度和位置可通過UAVs數(shù)、天線增益和波束寬度進(jìn)行調(diào)整。

參考文獻(xiàn)

[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.