基于改進(jìn)混合粒子群算法和匹配理論的無人機(jī)電力巡檢卸載策略
2023-12-31 00:00:00黃冬梅徐琦孫錦中胡安鐸
計算機(jī)應(yīng)用研究 2023年7期
摘 要：無人機(jī)搭載深度神經(jīng)網(wǎng)絡(luò)進(jìn)行自主電力巡檢時由于受到設(shè)備本身計算能力、電池容量、深度神經(jīng)網(wǎng)絡(luò)計算負(fù)載的限制，無法獨立處理巡檢任務(wù)中產(chǎn)生的海量圖像數(shù)據(jù)。為解決該問題，提出了一種基于改進(jìn)混合粒子群算法和匹配理論的無人機(jī)電力巡檢卸載策略，該策略將系統(tǒng)成本最小化問題分解為深度神經(jīng)網(wǎng)絡(luò)計算任務(wù)協(xié)同分割和邊緣服務(wù)器選擇兩個子問題。針對協(xié)同分割子問題，基于深度神經(jīng)網(wǎng)絡(luò)計算任務(wù)的執(zhí)行流程提出了一種錯時傳輸方法，通過改進(jìn)混合粒子群算法求解多無人機(jī)任務(wù)協(xié)同分割層。針對邊緣服務(wù)器選擇子問題，定義無人機(jī)與邊緣服務(wù)器各自偏好函數(shù)，根據(jù)偏好函數(shù)通過匹配理論建立兩者間的穩(wěn)定匹配，得到邊緣服務(wù)器選擇策略。仿真結(jié)果表明，與其他卸載策略相比，所提策略能有效降低無人機(jī)能耗和計算任務(wù)處理時延，促進(jìn)邊緣服務(wù)器負(fù)載均衡。
關(guān)鍵詞：改進(jìn)混合粒子群算法； 匹配理論； 無人機(jī)巡檢； 邊緣服務(wù)器
中圖分類號：TM755
文獻(xiàn)標(biāo)志碼：A
文章編號：1001-3695（2023）07-029-2111-06
doi：10.19734/j.issn.1001-3695.2022.11.0791
Power inspection and unloading strategy of UAV based on improved hybrid particle swarm algorithm and matching theory
Huang Dongmeia， Xu Qib?， Sun Jinzhonga， Hu Anduoa
（a.College of Electronic amp; Information Engineering， b.College of Electrical Engineering， Shanghai University of Electric Power， Shanghai 200090， China）
Abstract：When UAVs are equipped with a deep neural network for power inspection， because the device computing power and battery capacity as well as the deep neural network computation load limit， it cannot independently process the massive amount of image data generated in the inspection task. To address this problem， this paper proposed an unloading strategy for UAV power inspection based on improved hybrid particle swarm algorithm and matching theory， which decomposed the system cost minimization problem into two sub-problems， such as cooperative partitioning of deep neural network computing tasks and edge server selection. For the collaborative partition problem， it proposed a staggered transmission method based on the execution process of deep neural network computational tasks， and an improved hybrid particle swarm algorithm solved the multi-UAV task collaborative partition layer. For the server selection problem， it defined the respective preference functions of the UAV and the server， and established a stable match between them through matching theory according to the preference functions to obtain the server selection policy. Simulation results show that the proposed strategy can effectively reduce the energy consumption and computational task processing delay of UAVs and promote the load balancing of edge servers compared with other offloading strategies.
Key words：hybrid particle swarm algorithm; matching theory; UAV inspection; edge server
0 引言
傳統(tǒng)無人機(jī)電力巡檢是由飛手操控?zé)o人機(jī)拍攝圖片或視頻［1］，通過網(wǎng)絡(luò)上傳至電網(wǎng)數(shù)字化應(yīng)用云平臺，再利用人工智能與人工篩選相結(jié)合的方式完成圖像識別。傳統(tǒng)方法作業(yè)水平取決于巡檢人員的技能水平，且上傳巡檢圖片或視頻到云服務(wù)器會導(dǎo)致極大的響應(yīng)時延和傳輸能耗。鑒于此情況，無人機(jī)自主巡檢被逐漸提及，通過搭載深度神經(jīng)網(wǎng)絡(luò)（deep neural network，DNN）實現(xiàn)無人機(jī)本地實時分析航拍數(shù)據(jù)，以及線路隱患自動識別［2］。但由于無人機(jī)受到計算能力、電池容量、深度神經(jīng)網(wǎng)絡(luò)計算負(fù)載的限制，無法獨立處理巡檢任務(wù)中產(chǎn)生的海量圖像數(shù)據(jù)。本文將電力巡檢與移動邊緣計算（mobile edge computing，MEC）架構(gòu)結(jié)合。MEC在網(wǎng)絡(luò)邊緣部署各種資源并充分利用，從而減少無人機(jī)計算能耗與傳輸能耗，同時網(wǎng)絡(luò)數(shù)據(jù)流量壓力得到減輕［3］。
典型的DNN通常具有多層結(jié)構(gòu)，圖片被喂入輸入層，通過DNN的前向傳播，信息被逐層傳遞、精煉提取，每一個網(wǎng)絡(luò)層輸出數(shù)據(jù)大小迅速縮減。根據(jù)DNN的結(jié)構(gòu)特點，可以將DNN以網(wǎng)絡(luò)層為細(xì)粒度設(shè)計層級計算分區(qū)策略［4］。雖然MEC可以將DNN卸載至邊緣端，但是由于DNN各層具有不同的輸入、輸出數(shù)據(jù)大小和計算負(fù)載，需要設(shè)計一種高效的卸載算法，根據(jù)時延和能耗等因素，決定將DNN中每個層的任務(wù)在對應(yīng)的邊緣服務(wù)器上卸載。
合理的DNN計算分區(qū)策略有助于降低MEC系統(tǒng)的時延和能耗。在單用戶場景下，Zhang等人［5］構(gòu)建了一個協(xié)作式深度卸載系統(tǒng)，該系統(tǒng)的基本思想是將DNN按層劃分為在移動設(shè)備上運行的前端部分和在邊緣服務(wù)器上運行的后端部分，通過在線學(xué)習(xí)模塊自動學(xué)習(xí)最佳分區(qū)點以滿足系統(tǒng)環(huán)境變化。Lee等人［6］針對卸載場景中通信效率低的問題，提出了一種新的神經(jīng)架構(gòu)搜索方法，并引入資源和通道選擇掩碼，在保證DNN任務(wù)分區(qū)計算準(zhǔn)確性的同時提高通信效率。在多用戶場景下，高寒等人［7］提出了一種基于DNN層次結(jié)構(gòu)的粒子群優(yōu)化算法卸載方案，該方案在滿足多用戶任務(wù)時間限制的同時，充分優(yōu)化用戶能耗。Xue等人［8］針對大規(guī)模DNN數(shù)據(jù)傳輸問題，考慮DNN分層模型設(shè)計了一種在資源有限的邊緣—云協(xié)作環(huán)境中并行卸載大規(guī)模DNN模型的優(yōu)化方法。但上述研究均未考慮多用戶場景下DNN計算任務(wù)的執(zhí)行流程，可能導(dǎo)致通信資源利用率不高。
匹配博弈理論被廣泛用于指導(dǎo)設(shè)計資源匹配機(jī)制，以解決資源的有效分配和利用問題。毛鶯池等人［9］針對多用戶卸載問題，將其轉(zhuǎn)換為用戶與服務(wù)器之間的相互選擇問題，并基于延遲接受的思想不斷迭代，降低任務(wù)卸載成本，然而該策略未考慮到匹配過程中服務(wù)器負(fù)載的動態(tài)變化。王汝言等人［10］將優(yōu)化問題分為資源分配計算和卸載決策兩個子問題，首先使用拉格朗日乘數(shù)法獲得計算資源分配，然后使用匹配博弈理論獲得卸載策略，可有效降低系統(tǒng)開銷。但其批量接受用戶卸載請求可能導(dǎo)致該用戶與多臺服務(wù)器形成匹配的情況。
針對上述問題，本文提出了一種基于改進(jìn)混合粒子群算法和匹配理論的無人機(jī)電力巡檢卸載策略。不同于上述研究：a）該策略考慮了DNN計算任務(wù)執(zhí)行過程與傳統(tǒng)多任務(wù)并行卸載不同，是一個具有時間先后順序的過程，提高了通信資源利用率，并提出了一種改進(jìn)混合粒子群算法，應(yīng)用到協(xié)同分割層選擇，提升估計精度;b）該策略考慮到無人機(jī)與邊緣服務(wù)器的自私性，構(gòu)建了兩者間多對一的穩(wěn)定匹配;每輪匹配后服務(wù)器選擇偏好度最好的無人機(jī)，將其任務(wù)加入服務(wù)器的待處理時間隊列中，并用于下一輪計算無人機(jī)偏好度。此信息更新機(jī)制更加有助于促進(jìn)服務(wù)器負(fù)載均衡。
1 系統(tǒng)模型與優(yōu)化問題制定
1.1 系統(tǒng)架構(gòu)
圖1是面向自主電力巡檢邊緣計算系統(tǒng)架構(gòu)模型，其組成包括多個巡檢無人機(jī)和多個邊緣服務(wù)器。無人機(jī)U=（1，2，…，n）、基站與邊緣服務(wù)器S=（1，2，…，m）均部署完整的DNN模型。由無人機(jī)拍攝圖片或視頻，并只在無人機(jī)上執(zhí)行部分DNN計算任務(wù)，此區(qū)段的輸出值會傳送至邊緣服務(wù)器上，該邊緣服務(wù)器會取得中間值，以從任何中斷點重復(fù)計算［11］，并執(zhí)行剩余計算任務(wù)。本文考慮了一個準(zhǔn)靜態(tài)場景，即認(rèn)為在一段時間內(nèi)系統(tǒng)信道狀態(tài)、服務(wù)器待處理任務(wù)隊列狀態(tài)、無人機(jī)位置不發(fā)生改變，此時卸載算法在邊緣服務(wù)器上運行，得出卸載決策后傳送至對應(yīng)無人機(jī)和邊緣服務(wù)器。
在邊緣服務(wù)器網(wǎng)絡(luò)中，邊緣服務(wù)器之間可以直接通信，也可以通過其他邊緣服務(wù)器進(jìn)行間接路由通信。本文采用路由閾值hpi，j來衡量無人機(jī)與邊緣服務(wù)器之間的路由距離［12，13］。當(dāng)無人機(jī)i能夠直接通過無線鏈路關(guān)聯(lián)訪問邊緣服務(wù)器j時，定義邊緣服務(wù)器j為無人機(jī)i的本地服務(wù)器；當(dāng)無人機(jī)i必須通過本地服務(wù)器j的高速鏈路訪問邊緣服務(wù)器j′時，定義邊緣服務(wù)器j′為無人機(jī)i的鄰居服務(wù)器。
1.2 基于DNN的計算任務(wù)模型
根據(jù)DNN結(jié)構(gòu)，層級計算任務(wù)由輸出數(shù)據(jù)大小、計算負(fù)載、各層級任務(wù)輸入輸出之間的依賴關(guān)系三部分組成。文獻(xiàn)［14～16］對上述內(nèi)容有了很好的研究，并且神經(jīng)網(wǎng)絡(luò)層級分區(qū)不是文中討論的重點，因此文中只做簡述。
a）DNN計算任務(wù)第k層輸出數(shù)據(jù)可由經(jīng)驗數(shù)據(jù)計算［17］。
其中：Di表示無人機(jī)i任務(wù)數(shù)據(jù)大小；ωik表示DNN第k層輸出數(shù)據(jù)大小與任務(wù)數(shù)據(jù)大小的比值。
b）DNN任務(wù)計算負(fù)載采用浮點運算次數(shù)（floating-point operation，F(xiàn)LOP）［18］表示。本文給出幾種常見神經(jīng)網(wǎng)絡(luò)層的FLOP計算模型。
（a）卷積層如式（2）所示。
（b）全連接層如式（3）所示。
（c）池化層可以簡單地視為對每一個輸入值進(jìn)行一次計算，如式（4）所示。
（d）激活層一般設(shè)在卷積層后面，對卷積層的每一個輸出值進(jìn)行判斷計算，因此其計算量為
其中：Cin表示輸入通道數(shù)；K×K表示卷積核的長度和寬度；Hout表示輸出特征圖的長度；Wout表示輸出特征圖的寬度；Cout表示卷積核的數(shù)目，即輸出通道數(shù)；I和O分別表示輸入神經(jīng)元數(shù)目和輸出神經(jīng)元數(shù)目；Hin和Win表示池化層輸入特征圖的長度和寬度；在考慮偏置時，括號內(nèi)的-1應(yīng)刪去。
c）將層級任務(wù)輸入輸出之間的依賴關(guān)系描述為C=（cen，ex），（en，ex=1，2，…，L;en≠ex），式中L表示DNN層的總數(shù)，每個向量cen，ex=（cen，cex）的頂點和方向分別表示各層的計算任務(wù)和各層計算任務(wù)的計算順序，cex必須在cen之后執(zhí)行，且cen的輸出是cex的輸入。
綜上所述，無人機(jī)i的巡檢任務(wù)定義為Qi=（Fi，Di，Wi，Ci）。Fi=（fi1，fi2，…，fil，…，fiL）表示各層FLOP；Wi=（ωi1，ωi2，…，ωik，…，ωiL）表示各層輸出數(shù)據(jù)大小與任務(wù)數(shù)據(jù)大小的比值。
1.3 卸載模型
根據(jù)1.2節(jié)DNN計算任務(wù)模型，巡檢任務(wù)可被分割為一連串具有先后執(zhí)行順序的子任務(wù)，考慮到如果將任務(wù)分割成多個部分放置在不同計算節(jié)點，所帶來的通信開銷過大，所以每個計算任務(wù)最多能被分為兩個部分。在對無人機(jī)任務(wù)進(jìn)行處理時，考慮到邊緣服務(wù)器計算資源有限，本文采用協(xié)作式卸載。具體而言，無人機(jī)在本地計算前k層DNN計算任務(wù)，并將剩余k-L層DNN計算任務(wù)卸載至本地服務(wù)器。但是，當(dāng)該本地服務(wù)器的計算資源不足時，本地服務(wù)器需將剩余k-L層DNN計算任務(wù)卸載至鄰居服務(wù)器上。時延與能耗的分析如下：
a）本地計算。無人機(jī)i的前k層DNN計算任務(wù)在本地計算的時延Ti，k和能耗Ei，k為
其中：Filocal表示無人機(jī)i的計算能力，用每秒浮點運算次數(shù)（floating-point operations per second，F(xiàn)LOP）表示；Pc表示無人機(jī)i的CPU計算功率。
b）卸載至本地服務(wù)器j。由于服務(wù)器通過電源供電，一般不會出現(xiàn)能量不足的情況，所以本文不考慮服務(wù)器的能耗，且考慮到計算結(jié)果的數(shù)據(jù)量非常小，忽略其傳輸時延和能耗。無人機(jī)i的剩余k-L層DNN計算任務(wù)卸載到本地服務(wù)器并計算完成的時延Ti，j，L和消耗的能量Ei，j，L為
1.4 優(yōu)化問題制定
DNN計算任務(wù)的執(zhí)行流程與傳統(tǒng)任務(wù)的部分卸載不同。前者須等待前k層在無人機(jī)本地計算完成方可將剩余k-L層DNN計算任務(wù)卸載至邊緣服務(wù)器，而后者本地計算與卸載至邊緣服務(wù)器可同時進(jìn)行。于是，無人機(jī)i的時延Ti和能耗Ei可分別表示為
其中：xij表示無人機(jī)i的任務(wù)卸載決策。
本文考慮能耗與時延的聯(lián)合優(yōu)化。具體而言，聯(lián)合優(yōu)化DNN計算任務(wù)分割層決策K={ki，i∈U}和卸載決策X={xij，i∈U，j∈S}以最小化系統(tǒng)成本。優(yōu)化問題可表示為
其中：N表示系統(tǒng)中參與卸載的無人機(jī)數(shù)量；約束C1表示任務(wù)分割層均為整數(shù)，其范圍不能超過該DNN的總層數(shù)；C2表示任意無人機(jī)最多卸載至一個邊緣服務(wù)器;α和β分別為時延與能耗的權(quán)重參數(shù)，無人機(jī)可根據(jù)系統(tǒng)狀態(tài)靈活調(diào)整。
1.5 問題分解
不難發(fā)現(xiàn)，式（13）是一個整數(shù)規(guī)劃問題。為了解決該問題，已有許多研究采用了問題分解的次優(yōu)化方法。因此，本文將優(yōu)化問題分解為具有較低復(fù)雜度的兩個子問題。子問題1是在給定卸載決策X下的DNN計算任務(wù)分割層決策問題：
子問題2是在給定DNN計算任務(wù)分割層決策K下的卸載對象決策問題：
2 卸載策略
本章提出了基于改進(jìn)混合粒子群算法和匹配理論的無人機(jī)任務(wù)卸載策略。該策略首先將子問題1轉(zhuǎn)換為DNN計算任務(wù)協(xié)同分割問題，利用改進(jìn)粒子群算法求解，然后子問題2轉(zhuǎn)換為無人機(jī)與邊緣服務(wù)器雙向選擇，進(jìn)一步采用匹配理論求解。
2.1 DNN計算任務(wù)協(xié)同分割
2.1.1 錯時傳輸方法
關(guān)聯(lián)同一本地服務(wù)器（基站）的大量無人機(jī)同時接入網(wǎng)絡(luò)進(jìn)行任務(wù)卸載，低網(wǎng)絡(luò)吞吐量會造成更高的傳輸時延，并且傳輸速率低時無人機(jī)會增大傳輸功率，消耗更多能耗。因此，本文根據(jù)DNN計算任務(wù)的分層卸載執(zhí)行過程，設(shè)計了一種分割層錯時傳輸方法。通過為關(guān)聯(lián)同一本地服務(wù)器（基站）的無人機(jī)任務(wù)設(shè)置不同的DNN分割層，可以將數(shù)據(jù)傳輸時間錯開，充分利用各時間段內(nèi)的空閑通信資源。但由于DNN計算任務(wù)各層計算負(fù)載和數(shù)據(jù)的大小不同，調(diào)控分割層可能會使某些無人機(jī)面臨更大的本地計算負(fù)載或傳輸數(shù)據(jù)，所以在應(yīng)用錯時傳輸方法時要盡可能減少因調(diào)控分割層產(chǎn)生的無人機(jī)附加能耗。值得注意的是，在通信資源充足時優(yōu)先考慮成本最小的分割層而非錯時傳輸協(xié)同分割層。
本文采用粒子群算法求解DNN計算任務(wù)協(xié)同分割決策，但傳統(tǒng)粒子群算法容易陷入局部最優(yōu)，因此需要對其進(jìn)行改進(jìn)以增強(qiáng)全局搜索能力。
2.1.2 改進(jìn)混合粒子群算法
傳統(tǒng)粒子群算法采用線性權(quán)重遞減方法，在迭代初期權(quán)重較大，具有較好的全局搜索能力。但隨著迭代進(jìn)行，權(quán)重逐漸減小，此時粒子沒有足夠的速度跳出局部最優(yōu)。因此需要在粒子陷入局部最優(yōu)時賦予粒子較大的速度，增大其全局搜索能力，避免粒子早熟。
人工免疫算法中的濃度機(jī)制可以用來反映粒子多樣性。低濃度表明種群分散，多樣性好，此時粒子全局搜索能力強(qiáng)；高濃度表明種群過于集中，容易陷入局部最優(yōu)。基于矢量矩的濃度機(jī)制如下所示。
其中：ηa表示第a個粒子；d（ηa）表示第a個粒子的濃度；p（ηa）表示第a個粒子的適應(yīng)度值；Y表示初始化粒子個體數(shù)量。
本文在傳統(tǒng)粒子群方法中引入濃度機(jī)制，提出了一種改進(jìn)混合粒子群算法。在種群初始化時將其分成數(shù)目一致的子群A和B，子群A遵循線性權(quán)重遞減方法，子群B遵循濃度權(quán)重方法。
子群A的線性權(quán)重為
其中：γκ表示第κ次迭代的慣性權(quán)重值；γmax為慣性權(quán)重初始值；γmin為最后一次迭代的慣性權(quán)重；κmax為最大迭代次數(shù)。
子群B的濃度權(quán)重為
其中：dmax為種群的粒子最大濃度值而非任一子群的粒子最大濃度值；為了使?jié)舛葯?quán)重能夠靈敏地改變權(quán)重值，又能限制權(quán)重值過大，在濃度權(quán)重中引入sigmoid函數(shù)；同時對dmax進(jìn)行歸一化處理。
若選取子群A最優(yōu)解作為全局最優(yōu)解，則改進(jìn)混合粒子群算法在種群初始化時就使得粒子多樣性下降，影響算法性能；若選取子群B最優(yōu)解作為全局最優(yōu)解，則有可能使得算法后期的搜索速度過大而無法鎖定最優(yōu)解。因此，改進(jìn)混合粒子群算法選取種群最優(yōu)解作為全局最優(yōu)解，在算法初期，由于子群A保留傳統(tǒng)粒子群算法初期具有較好全局搜索能力的特點且種群濃度較低，算法全局搜索能力較強(qiáng)。隨著算法進(jìn)行，線性權(quán)重降低，粒子濃度增加，子群A在小范圍內(nèi)尋找全局最優(yōu)解，子群B則嘗試擴(kuò)大范圍尋找新的全局最優(yōu)解，既保證了改進(jìn)混合粒子群算法的局部搜索能力又增加其全局搜索能力。
由于改進(jìn)混合粒子群將種群一分為二，使得任一子群的初始化粒子多樣性下降，所以本文在優(yōu)秀粒子的基礎(chǔ)上添加自適應(yīng)速度搜索，增加其多樣性。具體方法如下：當(dāng)粒子鄰近4代全局最優(yōu)適應(yīng)度值變化度小于閾值，表明粒子有可能陷入局部最優(yōu)，此時在優(yōu)秀粒子的速度值中添加一些隨機(jī)速度搜索。隨機(jī)速度的添加方式是以優(yōu)秀粒子的速度為中心，以濃度為半徑在其周圍范圍搜索。
其中：vκa表示第κ次迭代時第a個粒子的速度；vmax表示粒子速度最大閾值；rand（·）表示范圍內(nèi)的一個隨機(jī)數(shù)。在粒子陷入局部最優(yōu)時，賦予優(yōu)秀粒子跳出局部最優(yōu)的速度，這個速度與粒子最大濃度值呈正相關(guān)。當(dāng)濃度值較大時，增加其搜索范圍，使粒子分散在群體極值的較大范圍內(nèi)；當(dāng)濃度較小時，縮小其搜索范圍，使粒子在群體極值附近尋找最優(yōu)解。圖2為改進(jìn)混合式粒子群算法流程。
為了驗證所提算法的優(yōu)越性，將采用固定權(quán)重和線性遞減權(quán)重的粒子群算法與本文所提的改進(jìn)混合粒子群算法進(jìn)行對比。選取測試函數(shù)Rastrigin，種群規(guī)模和最大迭代次數(shù)分別為40和100，重復(fù)運行30次，求出三種算法在測試函數(shù)5維、10維時估計結(jié)果的最優(yōu)值、最差值、平均值、平均收斂代數(shù)、運行時間。具體結(jié)果如表1所示。可以看出，所提的混合式粒子群算法具有更好的最優(yōu)值和平均值，收斂代數(shù)與其他算法相差不大，這表明其具有較好的全局搜索能力和局部搜索能力。
2.1.3 改進(jìn)混合粒子群編碼
設(shè)粒子群算法最大迭代次數(shù)為κmax，種群規(guī)模為Y，單個粒子由N個無人機(jī)的卸載決策X組成，粒子向量的j維分量表示第j架無人機(jī)的分割層。采用隨機(jī)生成法初始化所有粒子，xij初始化表示如下：xij=rand（{1，2，…，L}）。
適應(yīng)度函數(shù)被用來評估粒子所對應(yīng)協(xié)同分割方案的優(yōu)劣。綜合考慮任務(wù)執(zhí)行過程、時延與能耗模型，本文設(shè)計出一種新的適應(yīng)度函數(shù)，如下所示。
其中：N′表示關(guān)聯(lián)同一本地服務(wù)器（基站）的無人機(jī)數(shù)量；Pw表示無人機(jī)待機(jī)功率；實際分割層組合中很難出現(xiàn)一架無人機(jī)的本地計算時間和傳輸時間與另一架無人機(jī)本地計算時間完全相等的情況，所以用誤差時間Twi，k表示兩者之間的差值。適應(yīng)度函數(shù)由兩部分構(gòu)成：a）關(guān)聯(lián)同一本地服務(wù)器（基站）無人機(jī)錯時傳輸成本；b）系統(tǒng)總成本。
2.2 無人機(jī)與邊緣服務(wù)器雙向選擇
在多無人機(jī)多服務(wù)器的邊緣計算環(huán)境中，無人機(jī)與服務(wù)器的行為都是自私的，雙方都會根據(jù)自身偏好追求自身利益最大化。匹配博弈理論中的雙邊匹配理論是一種廣泛應(yīng)用在建立兩種不交集合匹配關(guān)系的分布式求解方法［19～21］，每個參與者都會根據(jù)自身偏好與其他參與者建立穩(wěn)定匹配關(guān)系。因此將雙邊匹配理論應(yīng)用在無人機(jī)與服務(wù)器組合問題求解是非常可行的。本文認(rèn)為一個任務(wù)只能選擇一臺邊緣服務(wù)器進(jìn)行卸載，多個任務(wù)的卸載請求可以由一臺邊緣服務(wù)器同時接收，無人機(jī)和服務(wù)器之間構(gòu)成多對一雙邊匹配。
雙邊匹配理論首先需要定義匹配雙方的偏好函數(shù)。
a）無人機(jī)偏好。在選擇邊緣服務(wù)器時，無人機(jī)為滿足任務(wù)時間約束會考慮多項偏好因素，包括所選服務(wù)器的FLOPS和待處理隊列等。因此無人機(jī)偏好函數(shù)θi，l（j）為用戶成本函數(shù)：
b）邊緣服務(wù)器偏好。當(dāng)服務(wù)器選擇卸載無人機(jī)時，它會盡可能考慮任務(wù)數(shù)據(jù)上傳時間較少的用戶［10］，從而避免服務(wù)器在無人機(jī)計算資源上花費太長的空閑時間，進(jìn)而提高計算資源的利用率；服務(wù)器嘗試選擇路由閾值較低的無人機(jī)，減少任務(wù)數(shù)據(jù)在服務(wù)器之間的遷移成本，降低服務(wù)器能耗；服務(wù)器為了避免自身負(fù)載率過高而優(yōu)先接收計算資源需求量小的任務(wù)。因此邊緣服務(wù)器偏好函數(shù)θj，l（i）為
具體的無人機(jī)與服務(wù)器雙向選擇算法如算法1所示。
每個邊緣服務(wù)器都有請求卸載列表Greqj、接受卸載列表Grecj、拒絕卸載列表Grejj、待處理任務(wù)隊列Tquej。首先所有產(chǎn)生任務(wù)的N架無人機(jī)會根據(jù)效用函數(shù)θi，l（j）生成升序排列的邊緣服務(wù)器偏好列表，并選擇最佳邊緣服務(wù)器發(fā)送卸載請求。然后，在所有無人機(jī)的卸載請求都發(fā)出去之后，接收到卸載請求的M臺邊緣服務(wù)器會根據(jù)效用函數(shù)θj，k（i）生成升序排列的無人機(jī)偏好列表，選擇最佳無人機(jī)接收卸載請求，并根據(jù)任務(wù)分割層將待處理任務(wù)時延更新到Tquej，各服務(wù)器Grejj中的無人機(jī)會再次根據(jù)更新后的服務(wù)器信息與邊緣服務(wù)器進(jìn)行雙向選擇，直到所有無人機(jī)被邊緣服務(wù)器接受。
算法1 無人機(jī)與服務(wù)器雙向選擇算法
輸入：無人機(jī)的任務(wù)狀態(tài)信息Qi，服務(wù)器待處理隊列Tquej、FLOP。
輸出：無人機(jī)與服務(wù)器之間相互選擇決策Pij。
初始化Greqj=?，Grecj=?，Grejj=?，Tquej=Tquej0，N=N0，M=M0，l={1，2，…，L}
while N0gt;0 do：
for i∈N0 do：
根據(jù)θi，l（j）建立邊緣服務(wù)器偏好列表
尋找j=argmin（θi，l（j）），發(fā)送卸載請求
end for
for j∈M0 do：
服務(wù)器j將Greqj 中的無人機(jī)根據(jù)θj，l（i）建立偏好列表
尋找i=argmin（θi，l（i））并接受此卸載請求，拒絕其余任務(wù)卸載請求
更新Tquej0、Grejjj∈M0，清空Greqj
end for
N0=N0－M
end while
3 仿真分析
本文運用PyCharm進(jìn)行仿真實驗，解釋器為Python3.7，運行環(huán)境為AMD Ryzen5 4600h 3.0 GHz CPU 16 GB內(nèi)存的PC機(jī)。根據(jù)ResNet-v1-34結(jié)構(gòu)生成依賴關(guān)系向量，一旦DNN結(jié)構(gòu)確定，每個巡檢任務(wù)根據(jù)任務(wù)數(shù)據(jù)大小可得到不同的中間數(shù)據(jù)和各層計算時間。將基于改進(jìn)混合粒子群和匹配理論的卸載算法進(jìn)行了詳細(xì)評估：a）基于改進(jìn)混合粒子群算法的協(xié)同分割算法的有效性評估；b）基于匹配理論的雙向選擇算法的有效性評估；c）本文卸載策略與其他四種卸載策略從能耗、時延、服務(wù)器均衡程度方面進(jìn)行比較分析。
多無人機(jī)多邊緣服務(wù)器環(huán)境，由m=7臺邊緣服務(wù)器和不同數(shù)量的無人機(jī)組成。根據(jù)文獻(xiàn)［7，22，23］，本文仿真實驗設(shè)置無人機(jī)的計算功率為1 W，傳輸功率2 W，待機(jī)功率0.1 W，其計算能力為2.9 GFLOP;邊緣服務(wù)器的計算能力在［1.0，1.5］TFLOP;單位任務(wù)數(shù)據(jù)量為2 MB，F(xiàn)LOP為3.67×109，無人機(jī)任務(wù)參數(shù)為單位任務(wù)參數(shù)的隨機(jī)倍數(shù)。此外，本文認(rèn)為基站間傳輸速率是無人機(jī)與基站之間的10倍。
3.1 協(xié)同分割算法的有效性分析
圖3是協(xié)同分割算法的有效性評估。假設(shè)所有無人機(jī)關(guān)聯(lián)同一基站，且基站帶寬與單架無人機(jī)占用帶寬相等。從圖中可以看出，各無人機(jī)的數(shù)據(jù)傳輸時間錯開，避免了網(wǎng)絡(luò)擁堵帶來的無人機(jī)計算任務(wù)高時延和高能耗問題，且由于適應(yīng)度函數(shù)將誤差時間考慮在內(nèi)，減小了無人機(jī)等待時延與待機(jī)能耗。
3.2 雙向選擇算法的有效性分析
圖4給出了無人機(jī)數(shù)量與邊緣服務(wù)器的待處理任務(wù)時間隊列方差之間的關(guān)系。待處理任務(wù)時間隊列方差可以反映出邊緣服務(wù)器的負(fù)載均衡程度，方差越低說明邊緣服務(wù)器負(fù)載越均衡。從圖4中可看出，隨著無人機(jī)數(shù)量的增加，方差逐漸降低。
3.3 不同卸載策略的對比分析
將本文卸載策略與本地計算、就近卸載、遺傳算法（GA）、GT-SLA［23］四種卸載策略從能耗、時延、服務(wù)器均衡程度三個方面進(jìn)行比較分析。其中：
a）本地計算：計算任務(wù)在無人機(jī)本地計算。
b）就近卸載：計算任務(wù)卸載到本地服務(wù)器計算。
c）GA：綜合考慮本地計算、傳輸數(shù)據(jù)、邊緣服務(wù)器計算的能耗與時延選擇最佳卸載決策。
d）GT-SLA：基于博弈論和強(qiáng)化學(xué)習(xí)的一種分布式卸載策略。在無人機(jī)間建立非合作博弈，利用分布式算法求解納什均衡；再利用基于SLA的強(qiáng)化學(xué)習(xí)方法自主選擇邊緣服務(wù)器。
無人機(jī)數(shù)量與無人機(jī)總能耗的關(guān)系如圖5所示。無人機(jī)數(shù)量較少時，就近卸載、GA、GT-SLA的無人機(jī)總能耗相近，而本地計算能耗最大，這是因為此時通信資源充足，傳輸能耗小于本地計算能耗，無人機(jī)傾向于進(jìn)行任務(wù)卸載；本文策略能耗最小，這是因為中間分割層的傳輸數(shù)據(jù)量較小，且無人機(jī)的層級計算任務(wù)數(shù)據(jù)量較小。當(dāng)無人機(jī)數(shù)量大于4時，就近卸載的能耗最大。這是因為無人機(jī)之間競爭基站的通信資源，無人機(jī)平均通信資源低，導(dǎo)致高傳輸能耗。本文策略能耗相較于GA和GT-SLA差距隨著無人機(jī)數(shù)量增加而明顯加大，這是因為GA和GT-SLA雖然綜合考慮了計算能耗和傳輸能耗，為無人機(jī)選擇卸載方式和卸載位置，但由于其未考慮到任務(wù)部分卸載，增大了傳輸能耗，本文策略選擇合適分割層組合將數(shù)據(jù)傳輸時間錯開，使無人機(jī)傳輸能耗降低。
無人機(jī)數(shù)量與計算任務(wù)平均處理時延的關(guān)系如圖6所示。本地計算策略未能充分利用邊緣服務(wù)器的計算資源，導(dǎo)致總時延過高。就近卸載策略在無人機(jī)數(shù)量增多時平均處理時延最大是因為多無人機(jī)競爭帶寬導(dǎo)致傳輸時延增大。無人機(jī)數(shù)量小于4時GT-SLA平均處理時延大于GA和本文策略，這是因為其依據(jù)計算能力、距離、用戶效用三種因素選擇服務(wù)器，用戶效用的影響被弱化。本文策略的平均處理時延隨著無人機(jī)數(shù)量增加始終低于GA和GT-SLA，這是因為本文策略的協(xié)同分割層提高了通信資源利用率，減少傳輸時延，且在選擇服務(wù)器時考慮了服務(wù)器的待處理隊列，合理進(jìn)行計算負(fù)載分配，減少了多個任務(wù)排隊時間。
無人機(jī)數(shù)量與邊緣服務(wù)器待處理時間隊列方差的關(guān)系如圖7所示。隨著無人機(jī)數(shù)量的增長，就近卸載策略的方差值最高且增長最快，其次是GA，本文策略最低且趨于平穩(wěn)，本地計算策略保持不變。主要是因為本文策略考慮了服務(wù)器接收任務(wù)的偏好，且在服務(wù)器每一輪接收任務(wù)后更新待處理時間隊列信息，實現(xiàn)了均衡分配邊緣服務(wù)器的工作負(fù)載，減少了服務(wù)器等待時延和任務(wù)排隊時延。GT-SLA和本文策略波形相似，由于本文策略的服務(wù)器效用函數(shù)與時延密切相關(guān)，所以本文策略在服務(wù)器負(fù)載均衡方面更占優(yōu)勢。
4 結(jié)束語
本文提出的面向多無人機(jī)多服務(wù)器的計算任務(wù)卸載策略，充分利用了各時段的通信資源，同時無人機(jī)與邊緣服務(wù)器可根據(jù)自身偏好選擇最優(yōu)卸載策略，并且針對粒子群算法早熟問題，提出的改進(jìn)混合粒子群算法能較好兼顧全局搜索和局部搜索。通過仿真可知，該策略能有效減少無人機(jī)本地能耗，均衡服務(wù)器負(fù)載，并能同時兼顧減少無人機(jī)本地能耗和降低任務(wù)處理時延。后續(xù)的研究中，將考慮到無人機(jī)高速移動時任務(wù)數(shù)據(jù)在邊緣服務(wù)器中的遷移問題。
參考文獻(xiàn)：
[1]隋宇，寧平凡，牛萍娟，等.面向架空輸電線路的掛載無人機(jī)電力巡檢技術(shù)研究綜述［J］.電網(wǎng)技術(shù)，2021，45（9）：3636-3648.（Sui Yu， Ning Pingfan， Niu Pingjuan， et al. Review on mounted UAV for transmission line inspection［J］.Power System Technology，2021，45（9）：3636-3648.）
［2]趙樂，王先培，姚鴻泰，等.基于可見光航拍圖像的電力線提取算法綜述［J］.電網(wǎng)技術(shù)，2021，45（4）：1536-1546.（Zhao Le， Wang Xianpei， Yao Hongtai， et al. Survey of power line extraction methods based on visible light aerial image［J］.Power System Technology，2021，45（4）：1536-1546.）
［3]Roman R， Lopez J， Mambo M ，et al. Mobile edge computing， fog ： a survey and analysis of security threats and challenges［J］.Future Generation Computer Systems，2018，78：680-698.
［4]Kang Yaping， Hauswald J， Gao Cao， et al. Neurosurgeon： collaborative intelligence between the cloud and mobile edge［J］.ACM SIGARCH Computer Architecture News，2017，45（1）：615-629.
［5]Zhang Letian， Chen Lixing， Xu Jie. Autodidactic neurosurgeon： collaborative deep inference for mobile edge intelligence via online lear-ning［C］//Proc of Web Conference 2021.New York：ACM Press，2021：3111-3123.
［6]Lee K C， Kim H， Chan Y H， et al. Neural architecture search for computation offloading of DNNs from mobile devices to the edge server［C］//Proc of the 12th International Conference on ICT Convergence （ICTC） -Beyond the Pandemic Era with ICT Convergence Innovation.Piscataway，NJ：IEEE Press，2021：134-139.
［7]高寒，李學(xué)俊，周博文，等.移動邊緣計算環(huán)境中基于能耗優(yōu)化的深度神經(jīng)網(wǎng)絡(luò)計算任務(wù)卸載策略［J］.計算機(jī)集成制造系統(tǒng)，2020，26（6）：1607-1615.（Gao Han， Li Xuejun， Zhou Bowen， et al. Energy efficient computing task offloading strategy for deep neural networks in mobile edge computing［J］.Computer Integrated Manu-facturing Systems，2020，26（6）：1607-1615.）
［8]Xue Min， Wu Huaming， Peng Guang， et al. DDPQN： an efficient DNN offloading strategy in local-edge-cloud collaborative environments［J］.IEEE Trans on Services Computing，2021，15（2）：640-655.
［9]毛鶯池，徐雪松，劉鵬飛.基于穩(wěn)定匹配的多用戶任務(wù)卸載策略［J］.計算機(jī)應(yīng)用，2021，41（3）：786-793.（Mao Yingchi， Xu Xuesong， Liu Pengfei. Multi-user task offloading strategy based on stable allocation［J］.Journal of Computer Applications，2021，41（3）：786-793.）
［10]王汝言，吳和，崔亞平，等.超密集網(wǎng)絡(luò)中多基站博弈邊緣卸載策略［J］.西安電子科技大學(xué)學(xué)報，2021，48（4）：1-10.（Wang Ru-yan， Wu He， Cui Yaping， et al. Edge offloading strategy for the multi-base station game in ultra-dense networks［J］.Journal of Xidian University，2021，48（4）：1-10.）
［11]Li Liangzhi， Ota K， Dong Mianxiong. Sustainable CNN for robotic： an offloading game in the 3D vision computation［J］.IEEE Trans on Sustainable Computing，2018，4（1）：67-76.
［12]Guo Hongzhi， Liu Jiajia. Collaborative computation offloading for multiaccess edge computing over fiber-wireless networks［J］.IEEE Trans on Vehicular Technology，2018，67（5）：4514-4526.
［13]Chen Lixing， Zhou Sheng， Xu Jie. Computation peer offloading for energy-constrained mobile edge computing in small-cell networks［J］.IEEE/ACM Trans on Networking，2018，26（4）：1619-1632.
［14]Jeong H J， Lee H J， Shin C H， et al. IONN： incremental offloading of neural network computations from mobile devices to edge servers［C］//Proc of ACM Symposium on Cloud Computing.New York：ACM Press，2018：401-411.
［15]Hajabdollahi M， Esfandiarpoor R， Najarian K， et al. Hierarchical pruning for simplification of convolutional neural networks in diabetic retinopathy classification［C］//Proc of the 41st Annual International Conference of the IEEE Engineering in Medicine and Biology Society.New York：IEEE Press，2019：970-973.
［16]Lane N D， Bhattacharya S， Georgiev P， et al. DeepX： a software accelerator for low-power deep learning inference on mobile devices［C］//Proc of the 15th ACM/IEEE International Conference on Information Processing in Sensor Networks.New York：IEEE Press，2016：1-12.
［17]Xu Zichuan， Zhao Liqian， Liang Weifa， et al. Energy-aware infe-rence offloading for DNN-driven applications in mobile edge clouds［J］.IEEE Trans on Parallel and Distributed Systems，2020，32（4）：799-814.
［18]Li He， Ota K， Dong Mianxiong. Learning IoT in edge： deep learning for the Internet of Things with edge computing［J］.IEEE Network，2018，32（1）：96-101.
［19]蘇春霞.面向物聯(lián)網(wǎng)用戶服務(wù)需求的資源分配算法研究［D］.哈爾濱：哈爾濱工程大學(xué)，2021.（Su Chunxia. Service request-oriented resource allocation algorithm for Internet of Things users［D］.Harbin：Harbin Engineering University，2021.）
［20]趙磊，郭乃網(wǎng)，解梁軍，等.基于穩(wěn)定匹配理論的信息安全平臺構(gòu)建［J］.華東電力，2014，42（12）：2882-2884.（Zhao Lei， Guo Naiwang， Xie Liangjun， et al. Construction of information security platform based on stable matching theory［J］.East China Electric Po-wer，2014，42（12）：2882-2884.）
［21]Gu Yunan， Saad W， Bennis M， et al. Matching theory for future wireless networks： fundamentals and applications［J］.IEEE Communications Magazine，2015，53（5）：52-59.
［22]鄧芳明，單運，解忠鑫，等.基于博弈論和強(qiáng)化學(xué)習(xí)的無人機(jī)電力巡檢卸載策略［J］.電網(wǎng)技術(shù)，2021，45（9）：3649-3657.（Deng Fangming， Shan Yun， Xie Zhongxing， et al. The power inspection and unloading strategy of UAV based on game theory and reinforcement learning［J］.Power System Technology，2021，45（9）：3649-3657.）
［23]徐思雅，邢逸斐，郭少勇，等.基于深度強(qiáng)化學(xué)習(xí)的能源互聯(lián)網(wǎng)智能巡檢任務(wù)分配機(jī)制［J］.通信學(xué)報，2021，42（5）：191-204.（Xu Siya， Xing Yifei， Guo Shaoyong. et al. Deep reinforcement learning based task allocation mechanism for intelligent inspection services in energy internet［J］.Journal on Communications，2021，42（5）：191-204.）
