崔維慶

（中國(guó)石油大學(xué)（華東）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 青島 266580）

1 引言

近年來(lái)，傳感器網(wǎng)絡(luò)被廣泛應(yīng)用到農(nóng)作物環(huán)境檢測(cè)、森林火災(zāi)檢測(cè)、健康監(jiān)護(hù)、交通控制以及家庭自動(dòng)化等領(lǐng)域，可以有效地檢測(cè)溫度、濕度、壓力、聲音及運(yùn)動(dòng)狀態(tài)等信息。然而，傳感器網(wǎng)絡(luò)中的傳感器設(shè)備電池容量有限且計(jì)算能力有限，并且位置偏遠(yuǎn)或惡劣環(huán)境中的傳感器不方便進(jìn)行信息采集處理［1］。這對(duì)傳感器設(shè)備帶來(lái)了許多挑戰(zhàn)。

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

本文將無(wú)人機(jī)作為移動(dòng)基站收集傳感器設(shè)備的信息，并作為邊緣云與中央云共同分析處理收集到的數(shù)據(jù)。首先根據(jù)數(shù)據(jù)流動(dòng)方向設(shè)計(jì)無(wú)人機(jī)端的任務(wù)緩存模型，動(dòng)態(tài)表示系統(tǒng)中的數(shù)據(jù)流向。然后使用基于天牛群算法的塊坐標(biāo)下降法來(lái)優(yōu)化無(wú)人機(jī)的通信資源、計(jì)算資源和飛行軌跡來(lái)最大化無(wú)人機(jī)的能耗效率，并且引入Cubic混沌映射和Lvy飛行對(duì)天牛群算法進(jìn)行改進(jìn)。

2 問(wèn)題描述

2.1 通信模型

傳感器網(wǎng)絡(luò)中無(wú)人機(jī)支持下的移動(dòng)邊緣計(jì)算系統(tǒng)模型如圖1 所示，其中中央云與基站有線(xiàn)連接。無(wú)人機(jī)作為移動(dòng)基站配備有信號(hào)收發(fā)器可以為傳感器提供通信服務(wù)，并且作為邊緣云配備有輕量級(jí)服務(wù)器可以提供計(jì)算服務(wù)。本文采用部分卸載策略，無(wú)人機(jī)接收傳感器上傳的數(shù)據(jù)并在本地處理一部分?jǐn)?shù)據(jù)，然后將剩余數(shù)據(jù)卸載到中央云，無(wú)人機(jī)可以同時(shí)進(jìn)行數(shù)據(jù)收集、數(shù)據(jù)處理和任務(wù)卸載。

圖1 無(wú)人機(jī)支持下的移動(dòng)邊緣計(jì)算系統(tǒng)模型圖

為了結(jié)合現(xiàn)實(shí)，無(wú)人機(jī)支持下的移動(dòng)邊緣計(jì)算系統(tǒng)使用了一個(gè)三維的歐幾里得坐標(biāo)。M個(gè)異構(gòu)傳感器不均勻地分布在二維平面內(nèi)，在平面內(nèi)的位置表示為qm=[xm,ym]，m∈M，M=｛1，2，…，M｝，并且這些傳感器設(shè)備的坐標(biāo)對(duì)無(wú)人機(jī)來(lái)說(shuō)是已知的。在整個(gè)任務(wù)處理期間，無(wú)人機(jī)在一個(gè)固定的高度H 飛行，并且本文將無(wú)人機(jī)軌跡分解為N條軌跡段，用N+1 個(gè)軌跡點(diǎn)來(lái)表示，n∈N，N=｛1，2，…，N｝。表示無(wú)人機(jī)在第n條軌跡段飛行的時(shí)間。傳感器設(shè)備中的任務(wù)數(shù)據(jù)可分，即可以在兩個(gè)或多個(gè)服務(wù)器中處理該數(shù)據(jù)并將反饋的結(jié)果統(tǒng)一分析。將每個(gè)傳感器設(shè)備中待處理的任務(wù)定義為｛Rm,Fm｝，m∈M。Rm表示第m個(gè)設(shè)備待處理任務(wù)的數(shù)據(jù)規(guī)模，F(xiàn)m表示處理任務(wù)所需的CPU周期數(shù)。

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

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

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

當(dāng)無(wú)人機(jī)接收到傳感器上傳的數(shù)據(jù)后，其中一部分?jǐn)?shù)據(jù)在本地進(jìn)行處理，另一部分卸載到中央云，卸載速率表示為

2.2 任務(wù)緩存模型

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

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

Dn表示無(wú)人機(jī)在第n條軌跡段在本地處理的數(shù)據(jù)以及卸載數(shù)據(jù)的總和，表示為

其中?=0.025 表示處理單位比特?cái)?shù)據(jù)所需的CPU周期數(shù)，并且本文假設(shè)無(wú)人機(jī)從第2 條軌跡段開(kāi)始處理和卸載數(shù)據(jù)。則在時(shí)間T內(nèi)處理的總數(shù)據(jù)量表示為

2.3 能耗效率模型

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

其中k=10-26表示能量轉(zhuǎn)化能力。無(wú)人機(jī)在整個(gè)任務(wù)處理時(shí)間T內(nèi)卸載數(shù)據(jù)的能耗表示為

本文所使用的無(wú)人機(jī)為固定翼無(wú)人機(jī)，其能耗模型表示為

其中c1和c2是兩個(gè)與無(wú)人機(jī)重量、飛行翼范圍及密度有關(guān)的常數(shù)；v[n]表示無(wú)人機(jī)在第n條軌跡段的飛行速度，表示為

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

2.4 問(wèn)題描述

本文的優(yōu)化問(wèn)題是最大化無(wú)人機(jī)在傳感器網(wǎng)絡(luò)中的能耗效率。讓F=｛fn,?n?N｝，P=｛Pn,?n?N｝，T=｛tn,?n?N｝，Q=｛qn,?n?N｝，則問(wèn)題P可以表示為

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

3 基于天牛群算法的塊坐標(biāo)下降法

問(wèn)題P 的目標(biāo)函數(shù)和限制條件有非凸性，因此本文使用塊坐標(biāo)下降法來(lái)分布迭代求解問(wèn)題P，得到最優(yōu)的資源分配和無(wú)人機(jī)軌跡。

3.1 資源分配

本文首先將問(wèn)題P 轉(zhuǎn)化為兩個(gè)有關(guān)計(jì)算資源F和通信資源P的子問(wèn)題P1和P2，問(wèn)題P1表示為

問(wèn)題P2表示為

本文對(duì)問(wèn)題P1和問(wèn)題P2分別使用KKT 條件和拉格朗日乘子法求解［15］，得到最優(yōu)的計(jì)算資源F*和通信資源P*。

3.2 軌跡優(yōu)化

根據(jù)得到的最優(yōu)的計(jì)算資源和通信資源，本文將問(wèn)題P 轉(zhuǎn)化為兩個(gè)有關(guān)無(wú)人機(jī)飛行時(shí)間T和無(wú)人機(jī)軌跡Q的子問(wèn)題P3和P4，問(wèn)題P3表示為

不難看出問(wèn)題P3是一個(gè)線(xiàn)性規(guī)劃問(wèn)題，本文使用Matlab里的linprog函數(shù)對(duì)問(wèn)題P3求解得到最優(yōu)的無(wú)人機(jī)飛行時(shí)間T*。

有關(guān)無(wú)人機(jī)飛行軌跡的子問(wèn)題P4表示為

本文使用改進(jìn)的天牛群算法來(lái)求解此問(wèn)題［14］，天牛群算法結(jié)合了天牛須算法和粒子群算法［15～16］，解決了傳統(tǒng)天牛須算法面對(duì)多維問(wèn)題收斂性差的問(wèn)題。并且本文引入了Cubic混沌映射生成多樣性的初始種群［17］，引入Lvy 飛行策略擾動(dòng)最優(yōu)個(gè)體位置避免求得局部最優(yōu)解［18］?；贑ubic混沌映射與Lvy 飛行的天牛群算法介紹如下：

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

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

天牛須長(zhǎng)與最優(yōu)的種群位置和個(gè)體最優(yōu)位置相關(guān)，因此每架無(wú)人機(jī)的左右須長(zhǎng)表示為

其中β表示縮放因子。

然后每架無(wú)人機(jī)的左右須坐標(biāo)分別表示為

每架無(wú)人機(jī)的速度更行方式為

其中ω表示慣性權(quán)重；C1和C2是兩個(gè)常數(shù)代表學(xué)習(xí)因子；A*B 表示具有相同形狀的矩陣A 和B 對(duì)應(yīng)元素逐個(gè)相乘。本文設(shè)置慣性權(quán)重和縮放因子隨時(shí)間遞減來(lái)增強(qiáng)前期的全局搜索能力和后期的局部搜索能力。

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

其中λ=0.6。

然而，啟發(fā)式算法容易出現(xiàn)早熟收斂狀態(tài)，此時(shí)無(wú)人機(jī)最優(yōu)位置為一局部最優(yōu)解，無(wú)人機(jī)通常向無(wú)人機(jī)群最優(yōu)解位置靠近，從而導(dǎo)致無(wú)人機(jī)聚集在局部最優(yōu)解附近。為了使無(wú)人機(jī)跳出局部最優(yōu)解，本文對(duì)最優(yōu)的無(wú)人機(jī)位置使用Lvy 飛行對(duì)進(jìn)行擾動(dòng)，使其跳出局部最優(yōu)解，Lvy 飛行擾動(dòng)表示如下：

3.3 算法實(shí)現(xiàn)

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

4 實(shí)驗(yàn)分析

本文將基于天牛群算法的塊坐標(biāo)下降法應(yīng)用于傳感器網(wǎng)絡(luò)中無(wú)人機(jī)的資源分配和軌跡優(yōu)化，使用Matlab軟件進(jìn)行算法仿真實(shí)驗(yàn)，本文提出的算法和對(duì)比算法均部署在Windows 10，64bit；Matlab 2018b，處理器為AMD Ryzen 5600H；主頻為3.3GHz；內(nèi)存為16.0GB。

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

表1 模擬實(shí)驗(yàn)所用的參數(shù)

使用基于天牛群算法的塊坐標(biāo)下降法得到的無(wú)人機(jī)軌跡如圖3所示。

圖3 無(wú)人機(jī)軌跡圖

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

圖4 無(wú)人機(jī)能耗效率對(duì)比圖

5 結(jié)語(yǔ)

基于傳感器網(wǎng)絡(luò)中傳感器設(shè)備計(jì)算能力不足和不方便收集處理其存儲(chǔ)數(shù)據(jù)的問(wèn)題，本論文提出一種傳感器網(wǎng)絡(luò)中無(wú)人機(jī)支持下的移動(dòng)邊緣計(jì)算系統(tǒng)模型。首先設(shè)計(jì)一種無(wú)人機(jī)端的任務(wù)緩存模型動(dòng)態(tài)表示數(shù)據(jù)流動(dòng)方向，然后提出一種基于天牛群算法的塊坐標(biāo)下降法來(lái)優(yōu)化無(wú)人機(jī)的通信資源、計(jì)算資源和飛行軌跡，其中天牛群算法中引入了Cubic 混沌映射和Lvy 飛行策略能夠得到最優(yōu)的無(wú)人機(jī)軌跡，最終得到了最大的無(wú)人機(jī)能耗效率。實(shí)驗(yàn)結(jié)果表明，該算法能夠顯著提高無(wú)人機(jī)的能耗效率，從而保證無(wú)人機(jī)給傳感器設(shè)備帶來(lái)計(jì)算服務(wù)的同時(shí)能夠有效控制自身功耗。