基于改進虛擬力算法的無人機邊緣節點部署

王峻偉，魏祥麟，范建華，胡永揚

(1. 陸軍工程大學研究生院，江蘇 南京 210000；2. 國防科技大學第六十三研究所，江蘇 南京 210007)

1 引言

移動邊緣計算通過將計算和存儲資源下沉到網絡邊緣，為移動用戶提供了高性能、低延遲與高帶寬的服務環境。另一方面，得益于成本低、機動靈活、快速部署等優勢，將無人機作為邊緣計算節點的技術在災難救援和應急響應等特殊環境中廣泛應用。作為邊緣節點的無人機可以緩存熱門內容(地圖數據、導航數據、災難評估數據、氣象水文數據等)，并根據地面設備發送的內容請求，將緩存內容直接傳輸給地面設備，無需從遠端云服務器下載，大幅度地降低了內容傳輸時延[1]。然而，該技術也面臨著許多挑戰，包括無人機邊緣節點的最佳部署、能量限制、干擾管理和路徑規劃等[2-6]。

基于此，本文重點研究了無人機邊緣節點部署問題，針對傳統部署算法在多無人機邊緣節點部署中收斂速度慢、計算時延大的缺點[7]，設計了一種基于改進虛擬力算法(Improved virtual force algorithm，IVFA)的無人機邊緣節點部署算法，在降低服務時延的同時，實現對地面設備的快速有效覆蓋。

2 國內外研究現狀

現有無人機部署可分為靜態部署和動態部署兩類：通過人工方式將每一架無人機部屬在事先規劃的位置并且位置不再改變，稱為靜態部署；動態部署則是根據環境和網絡拓撲結構變化，通過無人機移動提高服務區域的覆蓋率和連通度。

關于無人機的動態部署相關研究很多，Zeng等人以通信吞吐量和無人機能耗為約束，通過遺傳算法求解所需無人機數目及其最優位置[7]。Wang等人基于負載均衡的思想，實現了節點最小移動距離下的均勻覆蓋[8]。然而，上述研究側重于單架無人機上通信信道以及傳輸功率的優化，無法保證邊緣計算場景下的整體優化效果。文獻[9-11]研究了多無人機場景下的部署，Hayajneh等人研究了固定無人機數量下的覆蓋概率，同時也分析了多無人機間存在的干擾[9]。Akarsu在此基礎上，考慮了地面設備的公平性，以最小化最大傳輸時延為目標優化了多無人機的部署[10]。Mozaffari等人將計算資源和覆蓋效果進行博弈，給出了基于納什均衡的部署算法[11]。

以上關于無人機的部署具有應用靈活、優化效果明顯等優點，為無人機邊緣節點的部署提供了理論支撐。然而，上述研究僅考慮了通信需求，忽略了邊緣計算場景下地面設備內容請求對于部署的影響。事實上，每架無人機邊緣節點的緩存空間有限，地面設備請求的動態性會導致部分無人機邊緣節點請求承載不均勻，部分過載節點部署區域服務質量下降，顯著增加了通信排隊和內容響應時延[12]；另一方面，無人機邊緣節點的機載能量有限，已有通過各類啟發式算法求解所需無人機邊緣節點數目及其最優位置的方法,大多只在理想狀態下進行部署，在多個無人機邊緣節點協作部署的聯合優化過程中消耗了過多的計算資源，不適用于小規模、高機動性的典型無人機邊緣計算場景。

因此，為優化無人機邊緣節點的部署，研究者們引入了虛擬力的概念，即假定節點受到由周圍環境根據某種關系所產生的虛擬力作用，使多個無人機邊緣節點在動態環境中能夠維持彼此間的關系，將復雜的多無人機邊緣節點通信質量保證問題轉換為節點控制問題，只要無人機邊緣節點之間的距離維持在適當地范圍之內，就能一定程度上保持覆蓋的質量，降低計算開銷，此類利用虛擬力推動部署優化的算法統稱為虛擬力算法。Howard等人率先將虛擬力算法引入到解決提高無線傳感節點的覆蓋率的問題中，將網絡中的每個傳感器節點視為帶有等量同性電荷的粒子，將節點間的力模擬為粒子間的虛擬力[13]。Liu等人在此基礎上，提出了一種基于分子力的部署算法(Virtual force algorithm,VFA)，在固定節點數量下實現覆蓋面積的最大化。同時，該算法還考慮到了實際部署中節點間障礙對于部署的影響，通過多次迭代尋找出節點的最優部署方案[14]。Loscri等人對于虛擬力算法進行了改進，限制了節點間力的作用范圍，減少節點的頻繁移動；同時限制節點的移動距離，防止因節點移出監測區域而降低覆蓋率；并在節點運動受力公式中加入阻尼，隨著節點間能量消耗，系統趨于穩定，以此設定了部署優化的終止條件[15]。

3 場景描述與定義

3.1 無人機邊緣計算場景

典型的無人邊緣計算場景如圖1所示，其中包含了云數據中心、多個無人機邊緣節點和地面移動設備。云數據中心維持一個完整內容清單，且具有足夠空間存儲所有的內容。無人機邊緣節點具有有限的存儲空間，但其可以連接到云數據中心請求特定內容，并由四個模塊組成：無線接口模塊、計算模塊、存儲模塊和網絡回程連接模塊。無線接口模塊通常采用IEEE 802.11無線網絡通信協議，該協議具有實時調整無線鏈路上下行調制速率的功能，可以較好地適應動態條件下邊緣計算范式中的異構環境；存儲模塊根據緩存策略有選擇地存儲流行度高的內容；計算模塊用于處理用戶請求和感知無人機邊緣節點間的狀態信息；網絡回程連接模塊用于提供到云數據中心和其它無人機邊緣節點間的高速連接[16]。基于以上功能，無人機邊緣節點在接收到地面設備的內容請求后，如果請求的內容已存儲在緩存中，則無人機邊緣節點直接為地面設備提供服務；否則，需要通過主干鏈路從云數據中心請求內容。

圖1 典型無人機邊緣計算場景

3.2 部署參數定義

3.2.1 地面設備覆蓋率

地面設備覆蓋率是衡量服務覆蓋情況的重要指標，定義為部署區域內無人機邊緣節點服務的地面設備數量與服務區域內所有發送請求的地面設備數量的比值，比值越大表明覆蓋效果越好，覆蓋率小于等于1。

3.2.2 區域覆蓋均勻度

區域覆蓋均勻度反映了區域內所有無人機邊緣節點地理分布均勻狀況，定義為無人機邊緣節點間距離與理想部署距離的標準差。標準差值越小，無人機邊緣節點覆蓋均勻度就越高，在目標服務區域的覆蓋就越均勻，反之，無人機邊緣節點分布的均勻狀態就越差，在部分目標服務區域會出現無人機邊緣節點緩存服務的缺失。

3.2.3 服務時延

無人機邊緣節點的部署，需要考慮地面設備接受服務的時延容忍度。無人機的部署必須滿足每一個時隙中接受服務地面設備的時延需要，定義為自地面設備發起內容請求到獲取完整內容之間的時間。

3.3 模型建立

3.3.1 無人機邊緣節點二元感知模型

二元感知模型又稱為圓盤感知模型，如圖2所示，該模型中無人機邊緣節點的服務范圍是以該節點水平面坐標為圓心，r為服務半徑的圓。為了表示無人機邊緣節點與地面設備間的服務關系，引入了二元變量pic。當pic=1 時，表示地面設備c處于無人機邊緣節點i的服務范內。

(1)

圖2 無人機邊緣節點覆蓋場景

(2)

其中，d(i，c)為在無人機與地面設備的平面距離。

3.3.2 單個無人機邊緣節點最優部署

每一個在邊緣計算場景下的無人機節點，周期地收集地面節點的最新位置和內容請求信息,并根據收集到的信息計算當前的最優位置，以此動態地調整飛行軌跡。

假設地面設備處于同一水平面,無人機節點的飛行高度近似不變。在t時刻，無人機的平面坐標為XUAV(t),目標服務區域地面設備平面坐標為Yc(t)且數量C(t)，(xstart，xfinish)、(ystart，yfinish) 為服務區域的邊界，計算單架無人機的最優位置問題可化為以下約束：

(3)

(4)

(5)

(6)

(7)

(8)

Zc(t)是目標服務區域內地面設備的服務請求權重，來源于無人機根據自身緩存對內容請求感知后的分配，例如：在t時刻，服務區域中有C(t)個地面設備，每個地面設備請求Mc個內容，Mc的大小會隨著時隙改變。這些內容若處于無人機邊緣節點的緩存中，可以通過無人機直接提供服務，稱之為請求命中；否則，稱之為請求丟失，具有較大的服務時延。因此，為了提高對地面設備的服務能力，將每個發送請求的地面設備請求權重Zc(t)設置為與請求命中數負相關的函數，請求命中數越小，請求權重越大，請求內容數量越多，權重越大。

(9)

(10)

其中mc(t)為每個地面設備在時隙t的請求命中數。

此外，在實際無人機運動中，還需要考慮無人機的能耗、速度v、最大轉彎角W1等影響因素。本文假設無人機以固定高度飛行，固定高度下的無人機飛行能量消耗只取決于速度和最大轉彎角[17]，在此基礎上定義無人機在飛行約束下的最大移動距離Mstep。

上述問題可以描述為一個混合整數非線性規劃問題，采用多種群優化遺傳算法求解得到無人機邊緣節點的服務最優位置，其中，輸入XUAV(t)和Yc(t)作為多種群優化遺傳算法的移民算子，由式(3)可得適應度函數，通過選擇、交叉、變異生成下一代后，執行移民操作和人工選擇，得到單個無人機邊緣節點的最優位置。

4 無人機邊緣節點的部署算法IVFA

在單架無人機邊緣計算場景中,無人機邊緣節點只需周期地計算服務最優位置,然后沿飛行軌跡飛往預定區域上空即可。然而,在多無人機邊緣節點的動態部署中,為了確保服務區域內的地面設備能夠得到穩定的服務，不僅需要考慮地面設備覆蓋率還需兼顧區域覆蓋均勻度，以適應動態條件下的對地面設備的服務需要。

為此，本文在傳統虛擬力模型的基礎上，改進虛擬力為無人機邊緣節點與地面設備的萬有引力和節點間的分子力，通過虛擬力的作用優化部署，在保證對地面設備的服務的同時提高了覆蓋的效率。

4.1 初始狀態下的理想部署

在對于服務區域進行初始狀態下的部署時，可以假設地面設備為均勻分布，此時的部署可以簡化為一個在固定服務區域內，用多個圓覆蓋該區域的數學模型。圓的半徑為無人機邊緣節點的服務半徑r，目標是以最小節點數實現最大化的區域覆蓋率。由于解析初始狀態下部署時，覆蓋區域中的盲區和重疊是無法避免的。因此，當相鄰圓的相交面積越小時，區域覆蓋效率越高，如圖3所示，所有實線圓表示無人機邊緣節點的服務范圍。

圖3 初始狀態下的幾種部署方法

圖4 補償半徑選取

通過補償半徑計算出無人機邊緣節點的服務面積S(R)，此時在服務區域面積Ssevcie中的無人機邊緣節點數量為

(11)

(12)

在此基礎上，給出了初始狀態下的理想部署，如圖5所示。其中，每個圓表示無人機邊緣節點的覆蓋范圍，圓中的數字為無人機編號。

圖5 理想狀態初始分布圖

4.2 改進虛擬力算法

4.2.2 無人機邊緣節點間的作用力

對于動態場景中的無人機邊緣節點部署，本文參考帶電電子之間相互作用的分子力，使用排斥、吸引、盤旋這3個準則來調整節點的分布位置，使節點的區域覆蓋率達到最大。無人機邊緣節點i受到節點j的作用力定義如下

(13)

無人機邊緣節點i所受其它節點作用力的合力為

(14)

4.2.3 無人機邊緣節點與地面設備間的作用力

動態部署中地面設備對無人機邊緣節點同樣具有作用力，促使節點維持在服務區域內的最優部署。假設地面設備作用于節點間的虛擬力基于萬有引力定律，無人機邊緣節點與地面設備的作用力如下

(15)

其中,M分別為無人機邊緣節點i服務地面設備數量的倒數，m為地面設備在通信范圍內可以選擇的無人機邊緣節點數的倒數。dic為節點與地面設備之間的距離，G為萬有引力系數。無人機邊緣節點與地面設備間萬有引力越大，其建立的連接穩定性越強。

4.2.3 虛擬力轉化為位移策略

在每個時隙計算完無人機邊緣節點動態部署的虛擬力后，需要將虛擬力轉化為相應的移動距離，驅動所有受力無人機邊緣節點移動到最佳部署位置。

首先，計算無人機邊緣節點上受到虛擬力的合力

(16)

將虛合力分解為沿x軸和y軸兩個方向上的力，此時在虛擬力作用下對無人機邊緣節點飛行軌跡進行調整，將虛擬分力轉換為移動距離。

(17)

(18)

(19)

(20)

(21)

(22)

4.3 算法描述

本文的算法步驟描述如下：

① 初始化：按照理想部署分布，計算固定區域內補償半徑，最小化無人機邊緣節點數，并記錄下無人機節點的初始位置信息；

② 設置相關的虛擬力系數和部署系數。

③ 計算單個無人機邊緣節點最優位置：根據不同時隙發送請求的地面設備的狀態信息，統計每一架無人機邊緣節點上的請求內容數和請求命中數，由式(3)-(10)計算地面設備請求權重，并在固定飛行速度，最大轉彎角約束下，由多種群遺傳算法計算得到單架無人機邊緣節點的最優部署；

④ 虛擬力計算：根據不同時隙中無人機邊緣節點服務用戶數量以及地面設備可選擇無人機邊緣節點數量，由式(13)-(15)分別計算無人機邊緣節點上相應的虛擬力。

⑤ 無人機邊緣節點位移：根據式(16)-(22)將力轉化為無人機邊緣節點的位移，驅動無人機移動到最佳部署位置。

5 真與結果分析

5.1 仿真環境及參數設定

仿真平臺為MATLAB R2017a。仿真研究的目標檢測區域設置為7.5km × 4.5km 的水平區域，在該區域內隨機分布500 個地面設備，每個設備選擇距離最近的無人機邊緣節點周期性地發送數量為Mc的內容請求。

目標檢測區域中部署48架無人機邊緣節點，具有固定的飛行高度和緩存容量。參考文獻[20]中空對地信道模型的設計，處于相同高度的無人機邊緣節點的服務半徑為0.5km，其傳輸速率只與位置狀態相關。無人機邊緣節點飛行時還要受到最大轉彎角等飛行條件約束。主要仿真參數如表1所示。

表1 仿真參數

5.2 結果分析

圖6(a)為通過基于改進虛擬力算法IVFA對無人機邊緣節點的部署示意圖，為了更好地研究實際部署效果，選取了文獻[16]中單純依靠分子力的傳統虛擬力算法VFA作為對比。可以發現VFA算法隨著優化進行，過多的節點聚集到區域的邊界，區域覆蓋均勻度降低明顯。而通過IVFA算法進行部署優化，能在保證地面設備覆蓋率的同時，較好的維持區域的均勻覆蓋，并且避免了無人機邊緣節點在部署時由于距離過近而產生的碰撞。圖6(b)中對兩種虛擬力算法的地面設備覆蓋率和區域覆蓋均勻度進行了分析，可以發現，IVFA算法同時具有較高的地面設備覆蓋率和覆蓋均勻度，且隨著時隙變化，覆蓋效果始終保持穩定。

圖6 無人機邊緣節點部署示意圖

圖7分析了3組虛擬力系數條件下的地面設備覆蓋率，可以看出，萬有引力系數G較大時，在優化初期能保持較好的覆蓋率，但隨著優化次數的增加，覆蓋效果下降明顯。這是由于隨著優化的進行，無人機邊緣節點的部署過于集中于前一時隙中的地面設備，從而使得下一時隙對地面設備的優化效果下降。

圖7 不同虛擬力系數下地面設備覆蓋率

圖8反應了30個時隙中地面設備的內容請求時延，這里忽略了任務處理時延，將用戶的平均時延簡化如下

Ttotal=E1+E2+E3

(23)

圖8 地面設備平均服務時延

其中，E1為邊緣節點到地面設備的傳輸時延，E2為任務排隊時延，E3為云數據中心處理任務產生的額外時延。根據文獻[20]中的定義，E1中傳輸速率由空地通道模型確立，E2根據M/M/1排隊模型確定。可以看出IVFA算法大幅縮短了地面設備的內容請求時延，同時，隨著迭代次數增長，性能保持穩定。

6 總結分析

本文針對無人機邊緣節點動態部署問題，提出了一種基于改進虛擬力算法IVFA，在邊緣計算場景下無人機邊緣節點受虛擬力作用，根據地面設備和周圍節點的情況，調整部署位置以滿足服務區域覆蓋需要。仿真顯示，與傳統虛擬力算法相比，該算法大大提高了地面設備覆蓋率和區域覆蓋均勻度，并降低了對地面設備的服務時延。