基于移動邊緣計算的無人機資源分配及軌跡優化?

崔維慶

（中國石油大學（華東）計算機科學與技術學院 青島 266580）

1 引言

近年來，傳感器網絡被廣泛應用到農作物環境檢測、森林火災檢測、健康監護、交通控制以及家庭自動化等領域，可以有效地檢測溫度、濕度、壓力、聲音及運動狀態等信息。然而，傳感器網絡中的傳感器設備電池容量有限且計算能力有限，并且位置偏遠或惡劣環境中的傳感器不方便進行信息采集處理［1］。這對傳感器設備帶來了許多挑戰。

將無人機應用到傳感器網絡中利用了移動邊緣計算（MEC）的思想［2～3］，無人機作為移動邊緣云更加靠近傳感器，能夠減少路徑損耗［4～6］，進而提高傳感器設備的上傳速率，為MEC 系統帶來更大的收益。另一方面，MEC 系統中的無人機給傳感器設備帶來便利的同時也造成了也給自身帶來了相當多的能耗［7］，并且優化無人機在整個MEC系統中的資源分配可以合理利用無人機作為邊緣云和移動基站的計算資源和通信資源［8～9］，設計無人機的飛行軌跡可以減少無人機的飛行能耗并且給傳感器設備帶來更加有力的通信條件［10～11］。Zeng 等設計一種新型的基于時分多址的工作流模型，并聯合優化無人機和物聯網設備之間的通信關聯、計算資源、無人機懸停時間和物聯網設備的服務序列來最小化無人機的總能耗［12］。Mei 等將無人機作為邊緣云為每一個地面終端配備了移動克隆，通過網絡功能虛擬化實現的移動克隆來執行地面終端卸載的任務，最終使用塊坐標下降法得到最優的資源分配和無人機軌跡［13］。

本文將無人機作為移動基站收集傳感器設備的信息，并作為邊緣云與中央云共同分析處理收集到的數據。首先根據數據流動方向設計無人機端的任務緩存模型，動態表示系統中的數據流向。然后使用基于天牛群算法的塊坐標下降法來優化無人機的通信資源、計算資源和飛行軌跡來最大化無人機的能耗效率，并且引入Cubic混沌映射和Lvy飛行對天牛群算法進行改進。

2 問題描述

2.1 通信模型

傳感器網絡中無人機支持下的移動邊緣計算系統模型如圖1 所示，其中中央云與基站有線連接。無人機作為移動基站配備有信號收發器可以為傳感器提供通信服務，并且作為邊緣云配備有輕量級服務器可以提供計算服務。本文采用部分卸載策略，無人機接收傳感器上傳的數據并在本地處理一部分數據，然后將剩余數據卸載到中央云，無人機可以同時進行數據收集、數據處理和任務卸載。

圖1 無人機支持下的移動邊緣計算系統模型圖

為了結合現實，無人機支持下的移動邊緣計算系統使用了一個三維的歐幾里得坐標。M個異構傳感器不均勻地分布在二維平面內，在平面內的位置表示為qm=[xm,ym]，m∈M，M=｛1，2，…，M｝，并且這些傳感器設備的坐標對無人機來說是已知的。在整個任務處理期間，無人機在一個固定的高度H 飛行，并且本文將無人機軌跡分解為N條軌跡段，用N+1 個軌跡點來表示，n∈N，N=｛1，2，…，N｝。表示無人機在第n條軌跡段飛行的時間。傳感器設備中的任務數據可分，即可以在兩個或多個服務器中處理該數據并將反饋的結果統一分析。將每個傳感器設備中待處理的任務定義為｛Rm,Fm｝，m∈M。Rm表示第m個設備待處理任務的數據規模，Fm表示處理任務所需的CPU周期數。

本文使用正交頻分多址來消除傳感器與無人機之間的通信干擾［14］，無人機和傳感器m之間的信道增益表示為

其中β0是距離為1m 時的信道增益；dm,n表示無人機在第n條軌跡段與傳感器m之間的距離；‖?‖表示歐幾里得范數。則傳感器m在無人機第n條軌跡段的上傳速率表示為

其中αm[n]B1表示分配給傳感器m的帶寬；Pm是傳感器m的上傳功率；σ2表示傳感器m上的噪聲功率。值得注意的是，當無人機在第n條軌跡段和傳感器m沒有通信連接時，Vm[n] 的值為0。

當無人機接收到傳感器上傳的數據后，其中一部分數據在本地進行處理，另一部分卸載到中央云，卸載速率表示為

2.2 任務緩存模型

對于本地計算方法，本文假設無人機數據的一部分βDn（β∈［0，1］）在無人機本地處理，則剩余的(1 -β)Dn卸載到中央云上處理，本文定義fn≤Fu為無人機的計算能力（每秒的CPU 周期數），Fu表示無人機服務器的最大計算能力。

對于中央云服務器計算方法，中央云邊收集無人機上傳的數據邊進行分析處理。中央云有充足的計算能力能夠確保數據在有限時間內處理完成。讓Hn表示無人機在每一軌跡段終點的隊列長度，表示為Hn+1=Hn-Dn+An。An表示無人機在第n條軌跡段接收到的數據，表示為

Dn表示無人機在第n條軌跡段在本地處理的數據以及卸載數據的總和，表示為

其中?=0.025 表示處理單位比特數據所需的CPU周期數，并且本文假設無人機從第2 條軌跡段開始處理和卸載數據。則在時間T內處理的總數據量表示為

2.3 能耗效率模型

本文的目標是最大化無人機的能耗效率，首先建立無人機的能耗模型，無人機的能耗由三部分組成：本地計算的能耗、卸載數據的能耗以及飛行能耗。無人機服務器在本地處理數據的能耗表示為

其中k=10-26表示能量轉化能力。無人機在整個任務處理時間T內卸載數據的能耗表示為

本文所使用的無人機為固定翼無人機，其能耗模型表示為

其中c1和c2是兩個與無人機重量、飛行翼范圍及密度有關的常數；v[n]表示無人機在第n條軌跡段的飛行速度，表示為

其中‖qu[n] -qu[n-1]‖表示無人機在第n條軌跡段的飛行距離。

2.4 問題描述

本文的優化問題是最大化無人機在傳感器網絡中的能耗效率。讓F=｛fn,?n?N｝，P=｛Pn,?n?N｝，T=｛tn,?n?N｝，Q=｛qn,?n?N｝，則問題P可以表示為

其中C1 是有關無人機飛行時間的限制條件；C2 確保無人機的上傳功率在可控制的范圍內；C3 確保無人機的計算能力不超過其最大限制；C4 確無人機的飛行速度在可控制范圍內；C5 確保在每條軌跡段內無人機和傳感器設備之間的距離基本不變。

3 基于天牛群算法的塊坐標下降法

問題P 的目標函數和限制條件有非凸性，因此本文使用塊坐標下降法來分布迭代求解問題P，得到最優的資源分配和無人機軌跡。

3.1 資源分配

本文首先將問題P 轉化為兩個有關計算資源F和通信資源P的子問題P1和P2，問題P1表示為

問題P2表示為

本文對問題P1和問題P2分別使用KKT 條件和拉格朗日乘子法求解［15］，得到最優的計算資源F*和通信資源P*。

3.2 軌跡優化

根據得到的最優的計算資源和通信資源，本文將問題P 轉化為兩個有關無人機飛行時間T和無人機軌跡Q的子問題P3和P4，問題P3表示為

不難看出問題P3是一個線性規劃問題，本文使用Matlab里的linprog函數對問題P3求解得到最優的無人機飛行時間T*。

有關無人機飛行軌跡的子問題P4表示為

本文使用改進的天牛群算法來求解此問題［14］，天牛群算法結合了天牛須算法和粒子群算法［15～16］，解決了傳統天牛須算法面對多維問題收斂性差的問題。并且本文引入了Cubic混沌映射生成多樣性的初始種群［17］，引入Lvy 飛行策略擾動最優個體位置避免求得局部最優解［18］。基于Cubic混沌映射與Lvy 飛行的天牛群算法介紹如下：

首先，使用Cubic 混沌映射生成多樣性的初始種群：

其中i?I表示第i個天牛，I=｛1，2，…，I｝，ρ為控制參數。

天牛須長與最優的種群位置和個體最優位置相關，因此每架無人機的左右須長表示為

其中β表示縮放因子。

然后每架無人機的左右須坐標分別表示為

每架無人機的速度更行方式為

其中ω表示慣性權重；C1和C2是兩個常數代表學習因子；A*B 表示具有相同形狀的矩陣A 和B 對應元素逐個相乘。本文設置慣性權重和縮放因子隨時間遞減來增強前期的全局搜索能力和后期的局部搜索能力。

另外本文定義增量函數ξ的更新方式為

其中λ=0.6。

然而，啟發式算法容易出現早熟收斂狀態，此時無人機最優位置為一局部最優解，無人機通常向無人機群最優解位置靠近，從而導致無人機聚集在局部最優解附近。為了使無人機跳出局部最優解，本文對最優的無人機位置使用Lvy 飛行對進行擾動，使其跳出局部最優解，Lvy 飛行擾動表示如下：

3.3 算法實現

基于天牛群算法的塊坐標下降法流程如圖2所示。

4 實驗分析

本文將基于天牛群算法的塊坐標下降法應用于傳感器網絡中無人機的資源分配和軌跡優化，使用Matlab軟件進行算法仿真實驗，本文提出的算法和對比算法均部署在Windows 10，64bit；Matlab 2018b，處理器為AMD Ryzen 5600H；主頻為3.3GHz；內存為16.0GB。

本文假設傳感器設備不均勻地分布在100×100 m2的地面上，且基站的坐標為［0，0］，具體的參數如表1所示。

表1 模擬實驗所用的參數

使用基于天牛群算法的塊坐標下降法得到的無人機軌跡如圖3所示。

圖3 無人機軌跡圖

為了驗證本論文提出的算法（OP）的有效性，將其與另外三種方法進行比較，方法1 采用了二元卸載策略（BOM），方法2 使用了網絡功能虛擬化技術（NFV）［12］，方法3使用了工作流調度（WS）［13］。如圖4 所示，以收集數據規模為橫坐標，以無人機能耗效率為縱坐標畫出本論文算法與其他方法的對比圖，能夠直觀看出采用本文基于天牛群算法的塊坐標下降法的能耗效率要大于其他三種方法。這說明本文提出的算法性能更好，并使得無人機的能耗效率更高，進而降低無人機能耗給傳感器網絡中的無人機帶來更大的收益。

圖4 無人機能耗效率對比圖

5 結語

基于傳感器網絡中傳感器設備計算能力不足和不方便收集處理其存儲數據的問題，本論文提出一種傳感器網絡中無人機支持下的移動邊緣計算系統模型。首先設計一種無人機端的任務緩存模型動態表示數據流動方向，然后提出一種基于天牛群算法的塊坐標下降法來優化無人機的通信資源、計算資源和飛行軌跡，其中天牛群算法中引入了Cubic 混沌映射和Lvy 飛行策略能夠得到最優的無人機軌跡，最終得到了最大的無人機能耗效率。實驗結果表明，該算法能夠顯著提高無人機的能耗效率，從而保證無人機給傳感器設備帶來計算服務的同時能夠有效控制自身功耗。