王峻偉，魏祥麟，范建華，胡永揚(yáng)

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

1 引言

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

基于此，本文重點(diǎn)研究了無(wú)人機(jī)邊緣節(jié)點(diǎn)部署問(wèn)題，針對(duì)傳統(tǒng)部署算法在多無(wú)人機(jī)邊緣節(jié)點(diǎn)部署中收斂速度慢、計(jì)算時(shí)延大的缺點(diǎn)[7]，設(shè)計(jì)了一種基于改進(jìn)虛擬力算法(Improved virtual force algorithm，IVFA)的無(wú)人機(jī)邊緣節(jié)點(diǎn)部署算法，在降低服務(wù)時(shí)延的同時(shí)，實(shí)現(xiàn)對(duì)地面設(shè)備的快速有效覆蓋。

2 國(guó)內(nèi)外研究現(xiàn)狀

現(xiàn)有無(wú)人機(jī)部署可分為靜態(tài)部署和動(dòng)態(tài)部署兩類：通過(guò)人工方式將每一架無(wú)人機(jī)部屬在事先規(guī)劃的位置并且位置不再改變，稱為靜態(tài)部署；動(dòng)態(tài)部署則是根據(jù)環(huán)境和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化，通過(guò)無(wú)人機(jī)移動(dòng)提高服務(wù)區(qū)域的覆蓋率和連通度。

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

以上關(guān)于無(wú)人機(jī)的部署具有應(yīng)用靈活、優(yōu)化效果明顯等優(yōu)點(diǎn)，為無(wú)人機(jī)邊緣節(jié)點(diǎn)的部署提供了理論支撐。然而，上述研究?jī)H考慮了通信需求，忽略了邊緣計(jì)算場(chǎng)景下地面設(shè)備內(nèi)容請(qǐng)求對(duì)于部署的影響。事實(shí)上，每架無(wú)人機(jī)邊緣節(jié)點(diǎn)的緩存空間有限，地面設(shè)備請(qǐng)求的動(dòng)態(tài)性會(huì)導(dǎo)致部分無(wú)人機(jī)邊緣節(jié)點(diǎn)請(qǐng)求承載不均勻，部分過(guò)載節(jié)點(diǎn)部署區(qū)域服務(wù)質(zhì)量下降，顯著增加了通信排隊(duì)和內(nèi)容響應(yīng)時(shí)延[12]；另一方面，無(wú)人機(jī)邊緣節(jié)點(diǎn)的機(jī)載能量有限，已有通過(guò)各類啟發(fā)式算法求解所需無(wú)人機(jī)邊緣節(jié)點(diǎn)數(shù)目及其最優(yōu)位置的方法,大多只在理想狀態(tài)下進(jìn)行部署，在多個(gè)無(wú)人機(jī)邊緣節(jié)點(diǎn)協(xié)作部署的聯(lián)合優(yōu)化過(guò)程中消耗了過(guò)多的計(jì)算資源，不適用于小規(guī)模、高機(jī)動(dòng)性的典型無(wú)人機(jī)邊緣計(jì)算場(chǎng)景。

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

3 場(chǎng)景描述與定義

3.1 無(wú)人機(jī)邊緣計(jì)算場(chǎng)景

典型的無(wú)人邊緣計(jì)算場(chǎng)景如圖1所示，其中包含了云數(shù)據(jù)中心、多個(gè)無(wú)人機(jī)邊緣節(jié)點(diǎn)和地面移動(dòng)設(shè)備。云數(shù)據(jù)中心維持一個(gè)完整內(nèi)容清單，且具有足夠空間存儲(chǔ)所有的內(nèi)容。無(wú)人機(jī)邊緣節(jié)點(diǎn)具有有限的存儲(chǔ)空間，但其可以連接到云數(shù)據(jù)中心請(qǐng)求特定內(nèi)容，并由四個(gè)模塊組成：無(wú)線接口模塊、計(jì)算模塊、存儲(chǔ)模塊和網(wǎng)絡(luò)回程連接模塊。無(wú)線接口模塊通常采用IEEE 802.11無(wú)線網(wǎng)絡(luò)通信協(xié)議，該協(xié)議具有實(shí)時(shí)調(diào)整無(wú)線鏈路上下行調(diào)制速率的功能，可以較好地適應(yīng)動(dòng)態(tài)條件下邊緣計(jì)算范式中的異構(gòu)環(huán)境；存儲(chǔ)模塊根據(jù)緩存策略有選擇地存儲(chǔ)流行度高的內(nèi)容；計(jì)算模塊用于處理用戶請(qǐng)求和感知無(wú)人機(jī)邊緣節(jié)點(diǎn)間的狀態(tài)信息；網(wǎng)絡(luò)回程連接模塊用于提供到云數(shù)據(jù)中心和其它無(wú)人機(jī)邊緣節(jié)點(diǎn)間的高速連接[16]?；谝陨瞎δ?，無(wú)人機(jī)邊緣節(jié)點(diǎn)在接收到地面設(shè)備的內(nèi)容請(qǐng)求后，如果請(qǐng)求的內(nèi)容已存儲(chǔ)在緩存中，則無(wú)人機(jī)邊緣節(jié)點(diǎn)直接為地面設(shè)備提供服務(wù)；否則，需要通過(guò)主干鏈路從云數(shù)據(jù)中心請(qǐng)求內(nèi)容。

圖1 典型無(wú)人機(jī)邊緣計(jì)算場(chǎng)景

3.2 部署參數(shù)定義

3.2.1 地面設(shè)備覆蓋率

地面設(shè)備覆蓋率是衡量服務(wù)覆蓋情況的重要指標(biāo)，定義為部署區(qū)域內(nèi)無(wú)人機(jī)邊緣節(jié)點(diǎn)服務(wù)的地面設(shè)備數(shù)量與服務(wù)區(qū)域內(nèi)所有發(fā)送請(qǐng)求的地面設(shè)備數(shù)量的比值，比值越大表明覆蓋效果越好，覆蓋率小于等于1。

3.2.2 區(qū)域覆蓋均勻度

區(qū)域覆蓋均勻度反映了區(qū)域內(nèi)所有無(wú)人機(jī)邊緣節(jié)點(diǎn)地理分布均勻狀況，定義為無(wú)人機(jī)邊緣節(jié)點(diǎn)間距離與理想部署距離的標(biāo)準(zhǔn)差。標(biāo)準(zhǔn)差值越小，無(wú)人機(jī)邊緣節(jié)點(diǎn)覆蓋均勻度就越高，在目標(biāo)服務(wù)區(qū)域的覆蓋就越均勻，反之，無(wú)人機(jī)邊緣節(jié)點(diǎn)分布的均勻狀態(tài)就越差，在部分目標(biāo)服務(wù)區(qū)域會(huì)出現(xiàn)無(wú)人機(jī)邊緣節(jié)點(diǎn)緩存服務(wù)的缺失。

3.2.3 服務(wù)時(shí)延

無(wú)人機(jī)邊緣節(jié)點(diǎn)的部署，需要考慮地面設(shè)備接受服務(wù)的時(shí)延容忍度。無(wú)人機(jī)的部署必須滿足每一個(gè)時(shí)隙中接受服務(wù)地面設(shè)備的時(shí)延需要，定義為自地面設(shè)備發(fā)起內(nèi)容請(qǐng)求到獲取完整內(nèi)容之間的時(shí)間。

3.3 模型建立

3.3.1 無(wú)人機(jī)邊緣節(jié)點(diǎn)二元感知模型

二元感知模型又稱為圓盤(pán)感知模型，如圖2所示，該模型中無(wú)人機(jī)邊緣節(jié)點(diǎn)的服務(wù)范圍是以該節(jié)點(diǎn)水平面坐標(biāo)為圓心，r為服務(wù)半徑的圓。為了表示無(wú)人機(jī)邊緣節(jié)點(diǎn)與地面設(shè)備間的服務(wù)關(guān)系，引入了二元變量pic。當(dāng)pic=1 時(shí)，表示地面設(shè)備c處于無(wú)人機(jī)邊緣節(jié)點(diǎn)i的服務(wù)范內(nèi)。

(1)

圖2 無(wú)人機(jī)邊緣節(jié)點(diǎn)覆蓋場(chǎng)景

(2)

其中，d(i，c)為在無(wú)人機(jī)與地面設(shè)備的平面距離。

3.3.2 單個(gè)無(wú)人機(jī)邊緣節(jié)點(diǎn)最優(yōu)部署

每一個(gè)在邊緣計(jì)算場(chǎng)景下的無(wú)人機(jī)節(jié)點(diǎn)，周期地收集地面節(jié)點(diǎn)的最新位置和內(nèi)容請(qǐng)求信息,并根據(jù)收集到的信息計(jì)算當(dāng)前的最優(yōu)位置，以此動(dòng)態(tài)地調(diào)整飛行軌跡。

假設(shè)地面設(shè)備處于同一水平面,無(wú)人機(jī)節(jié)點(diǎn)的飛行高度近似不變。在t時(shí)刻，無(wú)人機(jī)的平面坐標(biāo)為XUAV(t),目標(biāo)服務(wù)區(qū)域地面設(shè)備平面坐標(biāo)為Yc(t)且數(shù)量C(t)，(xstart，xfinish)、(ystart，yfinish) 為服務(wù)區(qū)域的邊界，計(jì)算單架無(wú)人機(jī)的最優(yōu)位置問(wèn)題可化為以下約束：

(3)

(4)

(5)

(6)

(7)

(8)

Zc(t)是目標(biāo)服務(wù)區(qū)域內(nèi)地面設(shè)備的服務(wù)請(qǐng)求權(quán)重，來(lái)源于無(wú)人機(jī)根據(jù)自身緩存對(duì)內(nèi)容請(qǐng)求感知后的分配，例如：在t時(shí)刻，服務(wù)區(qū)域中有C(t)個(gè)地面設(shè)備，每個(gè)地面設(shè)備請(qǐng)求Mc個(gè)內(nèi)容，Mc的大小會(huì)隨著時(shí)隙改變。這些內(nèi)容若處于無(wú)人機(jī)邊緣節(jié)點(diǎn)的緩存中，可以通過(guò)無(wú)人機(jī)直接提供服務(wù)，稱之為請(qǐng)求命中；否則，稱之為請(qǐng)求丟失，具有較大的服務(wù)時(shí)延。因此，為了提高對(duì)地面設(shè)備的服務(wù)能力，將每個(gè)發(fā)送請(qǐng)求的地面設(shè)備請(qǐng)求權(quán)重Zc(t)設(shè)置為與請(qǐng)求命中數(shù)負(fù)相關(guān)的函數(shù)，請(qǐng)求命中數(shù)越小，請(qǐng)求權(quán)重越大，請(qǐng)求內(nèi)容數(shù)量越多，權(quán)重越大。

(9)

(10)

其中mc(t)為每個(gè)地面設(shè)備在時(shí)隙t的請(qǐng)求命中數(shù)。

此外，在實(shí)際無(wú)人機(jī)運(yùn)動(dòng)中，還需要考慮無(wú)人機(jī)的能耗、速度v、最大轉(zhuǎn)彎角W1等影響因素。本文假設(shè)無(wú)人機(jī)以固定高度飛行，固定高度下的無(wú)人機(jī)飛行能量消耗只取決于速度和最大轉(zhuǎn)彎角[17]，在此基礎(chǔ)上定義無(wú)人機(jī)在飛行約束下的最大移動(dòng)距離Mstep。

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

4 無(wú)人機(jī)邊緣節(jié)點(diǎn)的部署算法IVFA

在單架無(wú)人機(jī)邊緣計(jì)算場(chǎng)景中,無(wú)人機(jī)邊緣節(jié)點(diǎn)只需周期地計(jì)算服務(wù)最優(yōu)位置,然后沿飛行軌跡飛往預(yù)定區(qū)域上空即可。然而,在多無(wú)人機(jī)邊緣節(jié)點(diǎn)的動(dòng)態(tài)部署中,為了確保服務(wù)區(qū)域內(nèi)的地面設(shè)備能夠得到穩(wěn)定的服務(wù)，不僅需要考慮地面設(shè)備覆蓋率還需兼顧區(qū)域覆蓋均勻度，以適應(yīng)動(dòng)態(tài)條件下的對(duì)地面設(shè)備的服務(wù)需要。

為此，本文在傳統(tǒng)虛擬力模型的基礎(chǔ)上，改進(jìn)虛擬力為無(wú)人機(jī)邊緣節(jié)點(diǎn)與地面設(shè)備的萬(wàn)有引力和節(jié)點(diǎn)間的分子力，通過(guò)虛擬力的作用優(yōu)化部署，在保證對(duì)地面設(shè)備的服務(wù)的同時(shí)提高了覆蓋的效率。

4.1 初始狀態(tài)下的理想部署

在對(duì)于服務(wù)區(qū)域進(jìn)行初始狀態(tài)下的部署時(shí)，可以假設(shè)地面設(shè)備為均勻分布，此時(shí)的部署可以簡(jiǎn)化為一個(gè)在固定服務(wù)區(qū)域內(nèi)，用多個(gè)圓覆蓋該區(qū)域的數(shù)學(xué)模型。圓的半徑為無(wú)人機(jī)邊緣節(jié)點(diǎn)的服務(wù)半徑r，目標(biāo)是以最小節(jié)點(diǎn)數(shù)實(shí)現(xiàn)最大化的區(qū)域覆蓋率。由于解析初始狀態(tài)下部署時(shí)，覆蓋區(qū)域中的盲區(qū)和重疊是無(wú)法避免的。因此，當(dāng)相鄰圓的相交面積越小時(shí)，區(qū)域覆蓋效率越高，如圖3所示，所有實(shí)線圓表示無(wú)人機(jī)邊緣節(jié)點(diǎn)的服務(wù)范圍。

圖3 初始狀態(tài)下的幾種部署方法

圖4 補(bǔ)償半徑選取

通過(guò)補(bǔ)償半徑計(jì)算出無(wú)人機(jī)邊緣節(jié)點(diǎn)的服務(wù)面積S(R)，此時(shí)在服務(wù)區(qū)域面積Ssevcie中的無(wú)人機(jī)邊緣節(jié)點(diǎn)數(shù)量為

(11)

(12)

在此基礎(chǔ)上，給出了初始狀態(tài)下的理想部署，如圖5所示。其中，每個(gè)圓表示無(wú)人機(jī)邊緣節(jié)點(diǎn)的覆蓋范圍，圓中的數(shù)字為無(wú)人機(jī)編號(hào)。

圖5 理想狀態(tài)初始分布圖

4.2 改進(jìn)虛擬力算法

4.2.2 無(wú)人機(jī)邊緣節(jié)點(diǎn)間的作用力

對(duì)于動(dòng)態(tài)場(chǎng)景中的無(wú)人機(jī)邊緣節(jié)點(diǎn)部署，本文參考帶電電子之間相互作用的分子力，使用排斥、吸引、盤(pán)旋這3個(gè)準(zhǔn)則來(lái)調(diào)整節(jié)點(diǎn)的分布位置，使節(jié)點(diǎn)的區(qū)域覆蓋率達(dá)到最大。無(wú)人機(jī)邊緣節(jié)點(diǎn)i受到節(jié)點(diǎn)j的作用力定義如下

(13)

無(wú)人機(jī)邊緣節(jié)點(diǎn)i所受其它節(jié)點(diǎn)作用力的合力為

(14)

4.2.3 無(wú)人機(jī)邊緣節(jié)點(diǎn)與地面設(shè)備間的作用力

動(dòng)態(tài)部署中地面設(shè)備對(duì)無(wú)人機(jī)邊緣節(jié)點(diǎn)同樣具有作用力，促使節(jié)點(diǎn)維持在服務(wù)區(qū)域內(nèi)的最優(yōu)部署。假設(shè)地面設(shè)備作用于節(jié)點(diǎn)間的虛擬力基于萬(wàn)有引力定律，無(wú)人機(jī)邊緣節(jié)點(diǎn)與地面設(shè)備的作用力如下

(15)

其中,M分別為無(wú)人機(jī)邊緣節(jié)點(diǎn)i服務(wù)地面設(shè)備數(shù)量的倒數(shù)，m為地面設(shè)備在通信范圍內(nèi)可以選擇的無(wú)人機(jī)邊緣節(jié)點(diǎn)數(shù)的倒數(shù)。dic為節(jié)點(diǎn)與地面設(shè)備之間的距離，G為萬(wàn)有引力系數(shù)。無(wú)人機(jī)邊緣節(jié)點(diǎn)與地面設(shè)備間萬(wàn)有引力越大，其建立的連接穩(wěn)定性越強(qiáng)。

4.2.3 虛擬力轉(zhuǎn)化為位移策略

在每個(gè)時(shí)隙計(jì)算完無(wú)人機(jī)邊緣節(jié)點(diǎn)動(dòng)態(tài)部署的虛擬力后，需要將虛擬力轉(zhuǎn)化為相應(yīng)的移動(dòng)距離，驅(qū)動(dòng)所有受力無(wú)人機(jī)邊緣節(jié)點(diǎn)移動(dòng)到最佳部署位置。

首先，計(jì)算無(wú)人機(jī)邊緣節(jié)點(diǎn)上受到虛擬力的合力

(16)

將虛合力分解為沿x軸和y軸兩個(gè)方向上的力，此時(shí)在虛擬力作用下對(duì)無(wú)人機(jī)邊緣節(jié)點(diǎn)飛行軌跡進(jìn)行調(diào)整，將虛擬分力轉(zhuǎn)換為移動(dòng)距離。

(17)

(18)

(19)

(20)

(21)

(22)

4.3 算法描述

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

① 初始化：按照理想部署分布，計(jì)算固定區(qū)域內(nèi)補(bǔ)償半徑，最小化無(wú)人機(jī)邊緣節(jié)點(diǎn)數(shù)，并記錄下無(wú)人機(jī)節(jié)點(diǎn)的初始位置信息；

② 設(shè)置相關(guān)的虛擬力系數(shù)和部署系數(shù)。

③ 計(jì)算單個(gè)無(wú)人機(jī)邊緣節(jié)點(diǎn)最優(yōu)位置：根據(jù)不同時(shí)隙發(fā)送請(qǐng)求的地面設(shè)備的狀態(tài)信息，統(tǒng)計(jì)每一架無(wú)人機(jī)邊緣節(jié)點(diǎn)上的請(qǐng)求內(nèi)容數(shù)和請(qǐng)求命中數(shù)，由式(3)-(10)計(jì)算地面設(shè)備請(qǐng)求權(quán)重，并在固定飛行速度，最大轉(zhuǎn)彎角約束下，由多種群遺傳算法計(jì)算得到單架無(wú)人機(jī)邊緣節(jié)點(diǎn)的最優(yōu)部署；

④ 虛擬力計(jì)算：根據(jù)不同時(shí)隙中無(wú)人機(jī)邊緣節(jié)點(diǎn)服務(wù)用戶數(shù)量以及地面設(shè)備可選擇無(wú)人機(jī)邊緣節(jié)點(diǎn)數(shù)量，由式(13)-(15)分別計(jì)算無(wú)人機(jī)邊緣節(jié)點(diǎn)上相應(yīng)的虛擬力。

⑤ 無(wú)人機(jī)邊緣節(jié)點(diǎn)位移：根據(jù)式(16)-(22)將力轉(zhuǎn)化為無(wú)人機(jī)邊緣節(jié)點(diǎn)的位移，驅(qū)動(dòng)無(wú)人機(jī)移動(dòng)到最佳部署位置。

5 真與結(jié)果分析

5.1 仿真環(huán)境及參數(shù)設(shè)定

仿真平臺(tái)為MATLAB R2017a。仿真研究的目標(biāo)檢測(cè)區(qū)域設(shè)置為7.5km × 4.5km 的水平區(qū)域，在該區(qū)域內(nèi)隨機(jī)分布500 個(gè)地面設(shè)備，每個(gè)設(shè)備選擇距離最近的無(wú)人機(jī)邊緣節(jié)點(diǎn)周期性地發(fā)送數(shù)量為Mc的內(nèi)容請(qǐng)求。

目標(biāo)檢測(cè)區(qū)域中部署48架無(wú)人機(jī)邊緣節(jié)點(diǎn)，具有固定的飛行高度和緩存容量。參考文獻(xiàn)[20]中空對(duì)地信道模型的設(shè)計(jì)，處于相同高度的無(wú)人機(jī)邊緣節(jié)點(diǎn)的服務(wù)半徑為0.5km，其傳輸速率只與位置狀態(tài)相關(guān)。無(wú)人機(jī)邊緣節(jié)點(diǎn)飛行時(shí)還要受到最大轉(zhuǎn)彎角等飛行條件約束。主要仿真參數(shù)如表1所示。

表1 仿真參數(shù)

5.2 結(jié)果分析

圖6(a)為通過(guò)基于改進(jìn)虛擬力算法IVFA對(duì)無(wú)人機(jī)邊緣節(jié)點(diǎn)的部署示意圖，為了更好地研究實(shí)際部署效果，選取了文獻(xiàn)[16]中單純依靠分子力的傳統(tǒng)虛擬力算法VFA作為對(duì)比?？梢园l(fā)現(xiàn)VFA算法隨著優(yōu)化進(jìn)行，過(guò)多的節(jié)點(diǎn)聚集到區(qū)域的邊界，區(qū)域覆蓋均勻度降低明顯。而通過(guò)IVFA算法進(jìn)行部署優(yōu)化，能在保證地面設(shè)備覆蓋率的同時(shí)，較好的維持區(qū)域的均勻覆蓋，并且避免了無(wú)人機(jī)邊緣節(jié)點(diǎn)在部署時(shí)由于距離過(guò)近而產(chǎn)生的碰撞。圖6(b)中對(duì)兩種虛擬力算法的地面設(shè)備覆蓋率和區(qū)域覆蓋均勻度進(jìn)行了分析，可以發(fā)現(xiàn)，IVFA算法同時(shí)具有較高的地面設(shè)備覆蓋率和覆蓋均勻度，且隨著時(shí)隙變化，覆蓋效果始終保持穩(wěn)定。

圖6 無(wú)人機(jī)邊緣節(jié)點(diǎn)部署示意圖

圖7分析了3組虛擬力系數(shù)條件下的地面設(shè)備覆蓋率，可以看出，萬(wàn)有引力系數(shù)G較大時(shí)，在優(yōu)化初期能保持較好的覆蓋率，但隨著優(yōu)化次數(shù)的增加，覆蓋效果下降明顯。這是由于隨著優(yōu)化的進(jìn)行，無(wú)人機(jī)邊緣節(jié)點(diǎn)的部署過(guò)于集中于前一時(shí)隙中的地面設(shè)備，從而使得下一時(shí)隙對(duì)地面設(shè)備的優(yōu)化效果下降。

圖7 不同虛擬力系數(shù)下地面設(shè)備覆蓋率

圖8反應(yīng)了30個(gè)時(shí)隙中地面設(shè)備的內(nèi)容請(qǐng)求時(shí)延，這里忽略了任務(wù)處理時(shí)延，將用戶的平均時(shí)延簡(jiǎn)化如下

Ttotal=E1+E2+E3

(23)

圖8 地面設(shè)備平均服務(wù)時(shí)延

其中，E1為邊緣節(jié)點(diǎn)到地面設(shè)備的傳輸時(shí)延，E2為任務(wù)排隊(duì)時(shí)延，E3為云數(shù)據(jù)中心處理任務(wù)產(chǎn)生的額外時(shí)延。根據(jù)文獻(xiàn)[20]中的定義，E1中傳輸速率由空地通道模型確立，E2根據(jù)M/M/1排隊(duì)模型確定。可以看出IVFA算法大幅縮短了地面設(shè)備的內(nèi)容請(qǐng)求時(shí)延，同時(shí)，隨著迭代次數(shù)增長(zhǎng)，性能保持穩(wěn)定。

6 總結(jié)分析

本文針對(duì)無(wú)人機(jī)邊緣節(jié)點(diǎn)動(dòng)態(tài)部署問(wèn)題，提出了一種基于改進(jìn)虛擬力算法IVFA，在邊緣計(jì)算場(chǎng)景下無(wú)人機(jī)邊緣節(jié)點(diǎn)受虛擬力作用，根據(jù)地面設(shè)備和周?chē)?jié)點(diǎn)的情況，調(diào)整部署位置以滿足服務(wù)區(qū)域覆蓋需要。仿真顯示，與傳統(tǒng)虛擬力算法相比，該算法大大提高了地面設(shè)備覆蓋率和區(qū)域覆蓋均勻度，并降低了對(duì)地面設(shè)備的服務(wù)時(shí)延。