季鵬飛,徐曾春,胡 平

(南京工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211816)

1 引 言

目前,無人機(jī)以其快速、機(jī)動(dòng)、靈活等優(yōu)點(diǎn)被廣泛地應(yīng)用于測繪,航拍,救災(zāi)等領(lǐng)域.隨著科技的發(fā)展,其運(yùn)用方式從最初的單機(jī)任務(wù)向多駕無人機(jī)組成編隊(duì)協(xié)同完成任務(wù)發(fā)展[1].如何對無人機(jī)編隊(duì)進(jìn)行統(tǒng)一管理、合理調(diào)度,使其快速高效地完成作業(yè)任務(wù)是無人機(jī)研究的關(guān)鍵問題之一[2].

在無人機(jī)編隊(duì)執(zhí)行野外搜救任務(wù)時(shí),疑似目標(biāo)在地面的分布是隨機(jī)的,不可預(yù)知的,這就意味著同一時(shí)間無人機(jī)網(wǎng)絡(luò)中的各節(jié)點(diǎn)負(fù)載極有可能是不均衡的,這可能導(dǎo)致部分無人機(jī)長時(shí)間過載提前耗盡能量,進(jìn)而影響整個(gè)編隊(duì)的續(xù)航.通過任務(wù)間卸載調(diào)度使各節(jié)點(diǎn)互相幫助,可以實(shí)現(xiàn)節(jié)點(diǎn)之間的負(fù)載均衡.但無人機(jī)編隊(duì)的調(diào)度多依賴于云臺(tái)控制,在野外的通信環(huán)境中可能難以連接到云臺(tái),邊緣計(jì)算模型可以為該問題提供解決方案.邊緣計(jì)算是指在網(wǎng)絡(luò)邊緣執(zhí)行計(jì)算的一種新型計(jì)算模型,其基本理念是將計(jì)算任務(wù)在接近數(shù)據(jù)源的計(jì)算資源上運(yùn)行.邊緣計(jì)算模型將原有云計(jì)算中心的部分或全部計(jì)算任務(wù)遷移到數(shù)據(jù)源的附近執(zhí)行[3].

本研究的核心問題是在純邊緣環(huán)境中為無人機(jī)節(jié)點(diǎn)間的可卸載作業(yè)做出調(diào)度決策.在做出調(diào)度決策之前,需要確定哪些節(jié)點(diǎn)的狀態(tài)信息(NSI,node status information)需要共享以及共享的頻率.但這并不是說無人機(jī)在作業(yè)時(shí)必須進(jìn)行任務(wù)卸載,這要看把任務(wù)卸載給其他鄰節(jié)點(diǎn)能否給自身帶來時(shí)間或能耗上的收益[4].本文使用排隊(duì)論使底層硬件的調(diào)度算法抽象化,假設(shè)系統(tǒng)由中央處理器(CPU)節(jié)點(diǎn)或?qū)Ｓ眉铀倨?如圖形處理器和FPGA)組成,避免了為每項(xiàng)任務(wù)做出決策的需要,提出了一個(gè)純粹的邊緣分布式解決方案,其中節(jié)點(diǎn)只需要與跟它們直連的相鄰節(jié)點(diǎn)通信.根據(jù)求解程序的執(zhí)行位置以及數(shù)據(jù)共享方式的不同,提出了四種算法,并將其性能與非協(xié)作情況進(jìn)行比較.總之,本文的主要貢獻(xiàn)如下:

1)針對無人機(jī)自組網(wǎng)絡(luò)中的邊緣分布式系統(tǒng)提出了用于實(shí)時(shí)工作負(fù)載均衡的新算法.

2)制定了包含電池電量、鏈路帶寬和CPU可用性等節(jié)點(diǎn)狀態(tài)信息(NSI)的卸載成本函數(shù).

3)設(shè)計(jì)了可模擬無人機(jī)工作過程的模擬器.

4)與非協(xié)作(NC)系統(tǒng)相比,驗(yàn)證了所提出的算法改進(jìn)了無人機(jī)自組網(wǎng)絡(luò)系統(tǒng)的性能.

第2節(jié)介紹相關(guān)工作,第3節(jié)使用隊(duì)列網(wǎng)絡(luò)對無人機(jī)網(wǎng)絡(luò)進(jìn)行建模并正式定義問題.第4節(jié)詳細(xì)介紹了提出的負(fù)載均衡算法.第5節(jié)中描述了實(shí)驗(yàn)設(shè)置和仿真結(jié)果.最后進(jìn)行總結(jié)和展望.

2 相關(guān)工作

多無人機(jī)協(xié)同系統(tǒng)本質(zhì)上是任務(wù)分配和資源調(diào)度的問題.解決問題的核心是合理建模和優(yōu)化.針對這一問題,目前有一些相關(guān)研究.例如Li等人[5]提出了一種多無人機(jī)協(xié)同偵察任務(wù)規(guī)劃模型MPCU,采用遺傳算法對模型進(jìn)行優(yōu)化.Gu等人[6]提出了基于動(dòng)物群體感知方法的多無人機(jī)協(xié)同資源調(diào)度和任務(wù)分配方案.Denis等人[7]提出了面向無人機(jī)編隊(duì)實(shí)時(shí)任務(wù)調(diào)度的網(wǎng)絡(luò)中心多智能體系統(tǒng).考慮了初始調(diào)度和動(dòng)態(tài)重新調(diào)度兩部分.Simi等人[8]為多無人機(jī)網(wǎng)絡(luò)提出了一種分布式任務(wù)分配算法,使用動(dòng)力感知協(xié)調(diào)和規(guī)劃方法來協(xié)調(diào)多個(gè)無人機(jī)的活動(dòng).但是這些研究都存在以下不足:1)研究的基礎(chǔ)都不同程度地依賴云端的計(jì)算能力,這就要求無人機(jī)與云端之間有可用的通信鏈路,而這樣的通信條件在無人機(jī)野外或?yàn)?zāi)后作業(yè)中可能無法滿足.2)相關(guān)文獻(xiàn)中,單個(gè)無人機(jī)在任務(wù)分配后只完成自己分配到的任務(wù),無人機(jī)間不存在單個(gè)任務(wù)拆分卸載后共同完成的行為.各節(jié)點(diǎn)間只有信息交互,而沒有任務(wù)處理方面的互相幫助.3)在任務(wù)分配調(diào)度過程中沒有充分考慮無人機(jī)的實(shí)時(shí)能量狀態(tài)和計(jì)算能力.這可能加劇節(jié)點(diǎn)間的任務(wù)負(fù)載不均衡,進(jìn)而使部分無人機(jī)能量提前耗盡退出編隊(duì),打亂原有計(jì)劃.

針對以上不足,本文提出了一種基于邊緣計(jì)算的多機(jī)協(xié)同互助作業(yè)方案.該方案與普通邊緣計(jì)算方案有所區(qū)別,普通邊緣計(jì)算方案多是云霧地三層架構(gòu)[9],在云層和底層設(shè)備間構(gòu)建中間霧層提供緩存和計(jì)算服務(wù).本文重點(diǎn)研究當(dāng)云層和霧層能提供的計(jì)算能力很弱甚至完全不可用時(shí)如何在真正處于最邊緣的設(shè)備(無人機(jī))上完成作業(yè)的方案,并且將能耗作為一個(gè)重要指標(biāo)納入算法考核范圍.

3 系統(tǒng)建模

圖1是一個(gè)無人機(jī)搜救編隊(duì),當(dāng)執(zhí)行搜救任務(wù)時(shí),無人機(jī)編隊(duì)在事發(fā)區(qū)域內(nèi)按照事先規(guī)劃的航線飛行搜索,因?yàn)闊o人機(jī)飛行時(shí)需要不斷對疑似目標(biāo)進(jìn)行識(shí)別且各無人機(jī)的視場角疊加后需要完全覆蓋當(dāng)前工作區(qū)域,所以編隊(duì)內(nèi)各無人機(jī)飛行速度不能過快且間隔距離不能過遠(yuǎn).對無人機(jī)網(wǎng)絡(luò)進(jìn)行建模.建立如下關(guān)系:

G=(N,A)

其中,G是一個(gè)有向網(wǎng)絡(luò),N是n個(gè)節(jié)點(diǎn)的集合,A是m個(gè)有向弧的集合.弧(i,j)∈A代表從節(jié)點(diǎn)i到節(jié)點(diǎn)j的一條通信鏈路(例如Wi-Fi),并且有一個(gè)相關(guān)的成本函數(shù)Cij表示該弧上每單位流量的成本.

圖1 無人機(jī)搜救編隊(duì)Fig.1 UAV search and rescue formation

3.1 節(jié)點(diǎn)

每個(gè)節(jié)點(diǎn)都是一個(gè)帶有CPU,Wi-Fi,攝像頭等傳感設(shè)備的無人機(jī).使用M/M/1隊(duì)列來對其中每個(gè)模塊的工作進(jìn)行建模.M/M/1具有先到先服務(wù)(FCFS)調(diào)度規(guī)則,任務(wù)到達(dá)過程是泊松過程并且服務(wù)時(shí)間呈指數(shù)分布[10].對于通信部分,同樣使用兩個(gè)M/M/1隊(duì)列(發(fā)送方和接收方)對Wi-Fi模塊進(jìn)行建模,定義Wi-Fi發(fā)送、接收和傳輸速率相等(即μiWS=μiWR=μiWF).最終建模如圖2所示,其中CPU,WR,WS分別代表CPU,Wi-Fi接收器和Wi-Fi發(fā)送器隊(duì)列.每個(gè)節(jié)點(diǎn)可以被定義為一個(gè)數(shù)組{γi,γi0,μiCPU,μiWF} 其中γi是可卸載任務(wù)的速率,γi0是不可卸載任務(wù)的速率,μiCPU是CPU的服務(wù)率,μiWF是Wi-Fi傳輸速率,本文將這些節(jié)點(diǎn)信息定義為節(jié)點(diǎn)狀態(tài)信息(NSI).每個(gè)在無人機(jī)視野范圍內(nèi)出現(xiàn)的疑似目標(biāo)都會(huì)生成一個(gè)可卸載的任務(wù).節(jié)點(diǎn)本身必須自己完成的任務(wù)(如操作系統(tǒng))和不能從卸載中受益的任務(wù)被歸為不可卸載任務(wù).

圖2 無人機(jī)節(jié)點(diǎn)建模為隊(duì)列網(wǎng)絡(luò)Fig.2 UAV node modelled as network of queues

3.2 隊(duì)列網(wǎng)絡(luò)

如果有外部任務(wù)進(jìn)入系統(tǒng),則隊(duì)列網(wǎng)絡(luò)被定義為開放網(wǎng)絡(luò).這些網(wǎng)絡(luò)可以使用Open Jackson網(wǎng)絡(luò)進(jìn)行建模[10].Vilaplana[11]將其用于建模云計(jì)算范例.Open Jackson網(wǎng)絡(luò)指出隊(duì)列a∈{1,…,k}的到達(dá)率可以由公式(1)給出,基于這個(gè)公式,可以計(jì)算系統(tǒng)中所有隊(duì)列的任務(wù)到達(dá)率和任務(wù)輸出率.

(1)

其中,γa是外部任務(wù)的到達(dá)率,λb是隊(duì)列b的到達(dá)率,Pba一個(gè)任務(wù)從隊(duì)列b移動(dòng)到隊(duì)列a的概率.

3.3 問題表述及定義

在無人機(jī)編隊(duì)執(zhí)行搜救或航測任務(wù)時(shí),編隊(duì)在指定區(qū)域內(nèi)按照事先規(guī)劃好的航線以中低速飛行搜索,整個(gè)過程中,編隊(duì)隊(duì)形基本不變,編隊(duì)內(nèi)各無人機(jī)節(jié)點(diǎn)間的相對運(yùn)動(dòng)速度很小[12].因此,無人機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)基本穩(wěn)定.本文將調(diào)度決策問題制定為最小成本流問題(方程2),約束條件是所有的任務(wù)都被調(diào)度,并且不會(huì)影響隊(duì)列的穩(wěn)定性.決策變量xij∈R(n×m)代表通信鏈路(i,j)∈A上的任務(wù)流.xii是本地處理的任務(wù)率.平均到達(dá)率小于平均服務(wù)率時(shí),隊(duì)列速率保持穩(wěn)定.若節(jié)點(diǎn)中CPU隊(duì)列的平均任務(wù)到達(dá)率大于其服務(wù)率,則需尋找替代方案.等式(2b)中的約束條件確保所有任務(wù)都被分配,而(2c)中的不等式約束確保任務(wù)可以被所分配到的相應(yīng)節(jié)點(diǎn)處理.該公式使用來自所有節(jié)點(diǎn)的 NSI 并且同時(shí)對所有節(jié)點(diǎn)調(diào)度.該問題中的成本函數(shù)Cij在下文3.5節(jié)中具體描述.該最小成本流問題在每次有節(jié)點(diǎn)需要幫助時(shí)都會(huì)被執(zhí)行,在執(zhí)行該解算器前后,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和通信成本不會(huì)發(fā)生明顯變化.

(2a)

(2b)

方程(2)中的決策方案也可以用如下的決策矩陣定義:

(3)

定義矩陣X的每一行為決策向量(dv).決策向量dvi決定節(jié)點(diǎn) i如何處理傳入的任務(wù).矩陣的第i列表示其他節(jié)點(diǎn)如何把任務(wù)卸載到節(jié)點(diǎn)i.

3.4 邊緣分布式解決方案

考慮到任務(wù)到達(dá)率的時(shí)間變化性質(zhì),無人機(jī)編隊(duì)需要頻繁地解決方程(2)中的問題.下文5.1節(jié)指出,問題的復(fù)雜性取決于n(節(jié)點(diǎn)的總數(shù))和m(弧的總數(shù)).所以可以通過原始分解來簡化問題,由此每個(gè)節(jié)點(diǎn)計(jì)算自己的dv.這與Meskar[13]用于MCC 的類高斯-賽德爾方法相似.該方法主要與其最近的鄰節(jié)點(diǎn)通信,以了解他們可以提供何種幫助并作出決策.這種方法不是自私地把所有任務(wù)都卸載給鄰節(jié)點(diǎn),它也考慮鄰節(jié)點(diǎn)的計(jì)算資源,方程(4)為N中的每個(gè)節(jié)點(diǎn)i定義了這個(gè)問題.它與方程(2)中的中心問題不同,這里的每個(gè)節(jié)點(diǎn)i只根據(jù)從其近鄰處可獲得的信息盡量減少自身目標(biāo)函數(shù)的成本.

(4a)

(4b)

3.5 成本函數(shù)

只要所有到達(dá)的任務(wù)都可以進(jìn)行調(diào)度,即可保證所有隊(duì)列速率穩(wěn)定,我們希望以最小成本實(shí)現(xiàn).定義如下的成本函數(shù)Cij作為從節(jié)點(diǎn)i調(diào)度單位任務(wù)到節(jié)點(diǎn)j的成本.

(5)

其中,D是數(shù)據(jù)量,f是平均重傳次數(shù)(見公式6a),BWij是節(jié)點(diǎn)i和j之間的預(yù)期帶寬,Bi,Bj是節(jié)點(diǎn)i和j中的剩余電量,Li和Lj是節(jié)點(diǎn)i和j中已有的任務(wù)量,ω1,ω2,ω3是權(quán)重因子.

成本包括三個(gè)不同的組成部分:通信成本、能量可用性以及CPU可用性.它們的重要性可以通過權(quán)重因子ω1,ω2和ω3來調(diào)整,在下面詳細(xì)介紹.

1)通信成本

移動(dòng)節(jié)點(diǎn)間的通信成本取決于兩個(gè)節(jié)點(diǎn)間的預(yù)期帶寬,數(shù)據(jù)量和信道環(huán)境,同時(shí)要考慮到兩個(gè)節(jié)點(diǎn)間相對位移導(dǎo)致的鏈路生存時(shí)間變化,收發(fā)功率變化和多普勒頻移等現(xiàn)象.本文中由于無人機(jī)編隊(duì)內(nèi)各節(jié)點(diǎn)的相對位移很小,所以鏈路和收發(fā)功率穩(wěn)定,多普勒頻移可以忽略不計(jì).但由于各種噪聲和干擾,通信信道不可能完美,本文使用重傳因子f來描述信道環(huán)境.在實(shí)驗(yàn)中隨機(jī)抽樣兩個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)包投遞率(PDR),并使用幾何分布的均值來計(jì)算將數(shù)據(jù)從一個(gè)節(jié)點(diǎn)發(fā)送到另一個(gè)節(jié)點(diǎn)的平均傳輸次數(shù)(公式6a).這種關(guān)系(見圖3)表明,隨著PDR的降低,平均重傳次數(shù)呈指數(shù)增長.通過仿真實(shí)驗(yàn),發(fā)現(xiàn)0.5是建立有效通信鏈路的最低PDR.

f(PDR)=E[g(x;PDR)]

(6a)

g(x;PDR)=PDR(1-PDR)x-1,?x∈{0,…,∞}

(6b)

圖3 在非理想信道下的平均重傳次數(shù)Fig.3 Average no of retransmissions required due to imperfect channel

2)能量可用性

成本函數(shù)的第二個(gè)要素是節(jié)點(diǎn)的剩余能量水平,其重要性可以通過權(quán)重因子ω2來調(diào)整.在任務(wù)卸載調(diào)度過程中充分考慮節(jié)點(diǎn)的能量水平可避免木桶效應(yīng)引發(fā)整個(gè)編隊(duì)航程縮短,并且可以在一定程度上提高由電池供電的無人機(jī)電池的使用壽命.

3)CPU可用性

使用CPU隊(duì)列中現(xiàn)有任務(wù)的數(shù)量來衡量CPU的可用性.較高的數(shù)字表明低可用性,反之亦然.這也適用于調(diào)度決策中的自我處理.

3.6 模擬器

本文使用模擬器進(jìn)行仿真實(shí)驗(yàn),在模擬器上可以為目標(biāo)平臺(tái)使用簡化的算法流程模型,并根據(jù)需要更新組件.Wu等人用隊(duì)列模型來模擬分布式節(jié)點(diǎn)的工作量[14].但他們假設(shè)節(jié)點(diǎn)在沒有工作負(fù)載時(shí)不消耗能量,這在實(shí)際應(yīng)用中是不現(xiàn)實(shí)的,本文對此進(jìn)行改良.該模擬器的主要組件包含算法任務(wù)模擬,無人機(jī)功耗模擬和通信鏈路模擬等.

3.6.1 算法任務(wù)

算法任務(wù)的模擬器模型的特征是操作數(shù)(OP)、輸入和輸出數(shù)據(jù)量.例如人物檢測算法輸入尺寸為M×N的圖像,每幅圖像經(jīng)過約C個(gè)OP后輸出圖像中的人數(shù).假設(shè)每個(gè)時(shí)鐘周期有一個(gè)OP,那么算法在無人機(jī)上的執(zhí)行時(shí)間可以根據(jù)時(shí)鐘頻率估算.

(7)

在不同的處理器中,一個(gè)OP可能需要不止一個(gè)周期,一個(gè)周期也有可能有多個(gè)OP,但是這種近似的時(shí)間估計(jì)沒有詳細(xì)執(zhí)行信息(公式(7)).在實(shí)際應(yīng)用中,算法也可以先在測試設(shè)備(DUT)上執(zhí)行以測量更精確地執(zhí)行時(shí)間.

算法所需的操作數(shù)也不是一定的.例如在用于背景減除的梯度混合(MOG)算法中,操作數(shù)取決于檢測特定像素的匹配高斯分布的速度[15].為了使計(jì)算更易模擬,本文采用未找到匹配高斯的最壞情況.

3.6.2 無人機(jī)功耗模擬

本文不考慮無人機(jī)的飛行動(dòng)力能耗,因?yàn)楸疚牡难芯恐攸c(diǎn)是無人機(jī)的任務(wù)計(jì)算能耗,飛行耗能是不可避免的.為了真實(shí)地模擬其行為,無人機(jī)被分為中央處理器(CPU)、圖像傳感器和WI-FI等模塊,使用Jung等人的基于利用率的模型來計(jì)算能耗[16],相關(guān)參數(shù)可以針對不同的DUT進(jìn)行設(shè)置和校準(zhǔn).

1)圖像傳感器

連續(xù)使用時(shí),圖像傳感器在無人機(jī)中消耗大量能量.根據(jù)Likamwa等人,圖像傳感器每幀的能量消耗可以建模如下[17].

Ecamera=Pidle×(Tframe-Tactive)+Pactive×Tactive

(8a)

(8b)

由公式(8)可知降低圖像分辨率可以降低Tactive,進(jìn)而降低能耗,或者降低采樣率也可達(dá)到同樣目的.

2)處理器

CPU功率由閑時(shí)功率和運(yùn)行功率兩部分組成,如下所示:

(9)

CPU利用率根據(jù)使用時(shí)間與每幀可用時(shí)間的比率來計(jì)算.但操作系統(tǒng)(OS)和其他正在運(yùn)行的應(yīng)用程序也使用CPU.Dargie使用正態(tài)和指數(shù)分布來模擬工作量[18].我們也使用了一個(gè)隨機(jī)變量r從高斯分布采樣來模擬這些其他活動(dòng).通過調(diào)整r的均值可以模擬忙碌傳感器和空閑傳感器.總利用率計(jì)算如下:

(10a)

(10b)

其中N是要處理的算法的數(shù)量,Texeci是第i步算法的執(zhí)行時(shí)間(如背景減除算法、人物檢測算法等),TFrame是每幀可用時(shí)間.在檢測算法特別復(fù)雜時(shí)有可能出現(xiàn)Texeci大于TFrame的情況,我們只運(yùn)行CPU到100%的負(fù)載,并在下一幀運(yùn)行算法的其余部分,依此類推.

3)Wi-Fi

Wi-Fi模型計(jì)算連接模式下Wi-Fi模塊的時(shí)間和能量.根據(jù)不同的分組速率有如下兩種模式.

(11)

其中pr是分組速率,βLT、βHT、βLT base和βHT base是文獻(xiàn)[16]中的DUT參數(shù).如果每秒的分組數(shù)超過閾值,則Wi-Fi處于高功率狀態(tài),否則處于低功率狀態(tài).功耗與數(shù)據(jù)速率成正比.本文不考慮Wi-Fi在掃描模式下的能量消耗,因?yàn)楸狙芯康幕A(chǔ)是無人機(jī)之間已經(jīng)建立起連接.

4 均衡調(diào)度算法

上一節(jié)將任務(wù)卸載調(diào)度問題制定為中心式和分布式問題.本節(jié)定義一個(gè)協(xié)作環(huán)境,在該環(huán)境下所有節(jié)點(diǎn)都試圖通過協(xié)作實(shí)現(xiàn)全局目標(biāo)(即在分配的時(shí)間內(nèi)處理盡可能多的任務(wù)).該環(huán)境下如果一個(gè)節(jié)點(diǎn)發(fā)送一個(gè)任務(wù)到另一個(gè)節(jié)點(diǎn),另一個(gè)節(jié)點(diǎn)必須執(zhí)行它.但也要考慮到節(jié)點(diǎn)不能是自私的,只有在有必要卸載時(shí)才卸載.考慮兩種數(shù)據(jù)共享機(jī)制:主動(dòng)式和反饋式.根據(jù)這些數(shù)據(jù)在節(jié)點(diǎn)之間共享的方式以及算法的執(zhí)行位置不同,本文提出以下四種算法.并將這四種算法與非協(xié)作(NC)的情況進(jìn)行比較.

4.1 Oracle式(O)

這是一個(gè)理想化的算法,Oracle可以全程訪問所有無人機(jī)節(jié)點(diǎn)的NSI,每秒鐘同時(shí)向所有節(jié)點(diǎn)發(fā)送dv.該算法解決了方程(2)中的成本最小化問題.這在實(shí)際應(yīng)用中是不現(xiàn)實(shí)的,但它為其他算法的比較提供了最理想的結(jié)果.實(shí)驗(yàn)表明,即使忽略NSI的通信成本和執(zhí)行解算器的成本,它的能量消耗也是最多的.

4.2 主動(dòng)集中式(PC)

這是一個(gè)更為現(xiàn)實(shí)可行的Oracle版本.在該方法中指定其中一架無人機(jī)為服務(wù)器,其余所有節(jié)點(diǎn)將NSI發(fā)送給指定的服務(wù)器,然后解決方程(2)中的問題并將相應(yīng)的決策向量dv發(fā)送回每個(gè)節(jié)點(diǎn).在仿真實(shí)驗(yàn)中,服務(wù)器連接到所有節(jié)點(diǎn),但這不是必需的,因?yàn)镹SI和dv可以通過節(jié)點(diǎn)多跳傳輸.實(shí)驗(yàn)中考慮NSI的通信成本以及執(zhí)行解算器的成本.在新的廣播播出前,其他所有節(jié)點(diǎn)都必須遵循服務(wù)器做出的決策根據(jù)dv進(jìn)行計(jì)算和卸載.我們希望找到最合適的廣播NSI的頻率以避免過勤廣播浪費(fèi)資源,但這個(gè)問題沒有單一的答案,它取決于很多因素,如通信帶寬,NSI的信息量大小,PDR和網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù).如果有n-1個(gè)節(jié)點(diǎn)每隔t秒將NSI發(fā)送到服務(wù)器,忙碌概率最高的隊(duì)列就是服務(wù)器的接收隊(duì)列.分析其表現(xiàn)如下:

(12)

(13)

(14)

P[0]=1-ρ

(15)

其中,P[0]是隊(duì)列中沒有任務(wù)的概率.根據(jù)到達(dá)率和服務(wù)率,可以估計(jì)服務(wù)器接收隊(duì)列的性能.例如,假設(shè)有11個(gè)無人機(jī)節(jié)點(diǎn)以54 Mbps的數(shù)據(jù)速率連接,PDR為0.7,NSI為1 Mbits,每10秒發(fā)送一次NSI.然后據(jù)公式(6a)估算隊(duì)列利用率約為0.03,無需等待的時(shí)間約占97%.平均延遲約為0.03秒.圖4顯示了不同NSI更新頻率和不同網(wǎng)絡(luò)條件下的服務(wù)器隊(duì)列利用率.

圖4 服務(wù)器在各種網(wǎng)絡(luò)環(huán)境和NSI更新頻率下的隊(duì)列利用率Fig.4 Queue utilization of the server in proactive under various network conditions and NSI update frequency

4.3 主動(dòng)分布式(PD)

PD除了以下三個(gè)主要區(qū)別之外與PC類似.

1)它是純粹分布式的.沒有服務(wù)器,每個(gè)節(jié)點(diǎn)都必須解決自身的優(yōu)化問題.

2)每個(gè)節(jié)點(diǎn)只解決方程(4)中的分布式問題,而不是解決方程(2)中的中心問題.

3)集合N包含距離最近的鄰居節(jié)點(diǎn)而不是所有節(jié)點(diǎn),即使總節(jié)點(diǎn)很大(>100),N也被限制為幾十個(gè)節(jié)點(diǎn).

4.4 反饋分布式(RD)

如果只有少數(shù)節(jié)點(diǎn)過載并且低頻發(fā)生,定期傳輸NSI可能會(huì)浪費(fèi)資源.而且節(jié)點(diǎn)定期傳輸NSI會(huì)導(dǎo)致無人機(jī)經(jīng)常處于高功率狀態(tài)[16].在該算法中,節(jié)點(diǎn)只在需要幫助時(shí)進(jìn)行通信.尋求幫助的節(jié)點(diǎn)廣播請求幫助信息(RFH)并等待鄰居發(fā)送他們的NSI進(jìn)行響應(yīng).如果相鄰節(jié)點(diǎn)的平均CPU利用率小于設(shè)定的閾值,則必須響應(yīng).一旦尋求幫助的節(jié)點(diǎn)從其他節(jié)點(diǎn)接收到NSI,它就制定并解決方程(4).為了避免使用舊信息并及時(shí)更新鄰節(jié)點(diǎn)的當(dāng)前狀況,可以設(shè)置一個(gè)計(jì)時(shí)器Tth.一旦超過設(shè)定時(shí)間,節(jié)點(diǎn)必須廣播RFH重新開始.該算法具體表述如下:

算法1.反饋分布式

1.ifγi+γi0≤μi//到達(dá)率小于計(jì)算能力

2. Setdvito not offload //無需卸載

3.else

4.ifRFH broadcasted & decision time

5. Follow previousdvi

6.else

7. Broadcast RFH to all nodes

8. Wait Twaitseconds for NSI

9.ifNo of NSI received≥2

10. solve Eqn.(4)for newdviand follow it

11.else

12. Broadcast RFH again,follow previousdvi

13. end if

14. end if

15. end if

5 實(shí)驗(yàn)比較與分析

在各調(diào)度算法運(yùn)行時(shí)需要頻繁解決方程(2)和方程(4)中所述的優(yōu)化問題,該問題可以使用高效的線性編程技術(shù)來解決.目前解決線性問題的算法很多,所以在進(jìn)行仿真實(shí)驗(yàn)比較各調(diào)度算法前先測試各線性規(guī)劃算法的時(shí)間復(fù)雜度,以確定選用哪種線性規(guī)劃算法.

5.1 計(jì)算復(fù)雜度測試

對偶單純形和內(nèi)點(diǎn)算法是解決線性問題的常用方法.內(nèi)點(diǎn)算法被認(rèn)為是較有效,且占用內(nèi)存少的算法.在不同數(shù)量的節(jié)點(diǎn)下進(jìn)行實(shí)驗(yàn)來測量各算法的時(shí)間復(fù)雜度,發(fā)現(xiàn)內(nèi)點(diǎn)是效果最好的(見圖5),所以最終選定內(nèi)點(diǎn)算法解決方程(2)和方程(4)中的優(yōu)化問題.該實(shí)驗(yàn)是在臺(tái)式機(jī)上使用英特爾E5-2630處理器,并在Linux環(huán)境下運(yùn)行MATLAB 2013a進(jìn)行的.這些算法在無人機(jī)上的運(yùn)行時(shí)間可能會(huì)更長,但應(yīng)該遵循相似的規(guī)律.

5.2 仿真實(shí)驗(yàn)設(shè)置

使用上文中設(shè)計(jì)的模擬器進(jìn)行均衡調(diào)度算法的比較實(shí)驗(yàn),該模擬器可以適應(yīng)無人機(jī)類三維移動(dòng)目標(biāo).模擬器模擬放置在3×3網(wǎng)格上的九個(gè)如圖1所示的無人機(jī),無人機(jī)間通過Wi-Fi相互連接,Wi-Fi設(shè)置為10 Mbps.每架無人機(jī)可以檢測穿過其視場角的目標(biāo).為便于實(shí)驗(yàn),假設(shè)所有節(jié)點(diǎn)的資源信息(剩余能量,實(shí)時(shí)CPU負(fù)載等)可用,并且所有無人機(jī)具有相同的初始計(jì)算能力.在模擬開始時(shí),電池電量均勻分布在0-10瓦時(shí)之間.公式(10)中r的均值從0-1(滿載)均勻分布,標(biāo)準(zhǔn)偏差固定為0.1.測試設(shè)備的CPU參數(shù)見表1.這些參數(shù)在仿真過程中不會(huì)改變.對于任務(wù)模擬,本文使用隨機(jī)路點(diǎn)模型(RWP)[19].在RWP中,目標(biāo)在三維空間隨機(jī)位置產(chǎn)生.目標(biāo)

表1 CPU參數(shù)
Table 1 CPU parameters

Frequency245.0384.0460.8499.2576.0614.4652.8691.2768.0806.4844.8998.4βcpufreq201.0257.2286.0303.7332.7356.3378.4400.3443.4470.7493.1559.5βcpuidle35.139.535.236.539.538.536.739.640.238.443.545.6

可能暫停一段時(shí)間,也可能移動(dòng)到下一個(gè)目的地.當(dāng)它選擇下一個(gè)目的地時(shí),它會(huì)以隨機(jī)但恒定的速度向它移動(dòng);該過程重復(fù),直到它移出平臺(tái).RWP的非均勻空間現(xiàn)象意味著目標(biāo)集中在平臺(tái)的中間[19],可以使用這種現(xiàn)象和不規(guī)則的視場角來模擬九架無人機(jī)間的不規(guī)則負(fù)載.位于平臺(tái)中間的無人機(jī)可檢測到目標(biāo)數(shù)量最多.

圖5 各線性規(guī)劃算法的時(shí)間復(fù)雜度Fig.5 Time complexity of various linear problem solvers

5.3 仿真實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)運(yùn)行100次蒙特卡洛模擬,每次運(yùn)行代表20分鐘的仿真時(shí)間.實(shí)驗(yàn)過程中目標(biāo)產(chǎn)卵率高于死亡率,因此所有節(jié)點(diǎn)的任務(wù)到達(dá)率通常會(huì)隨時(shí)間增加(見圖6).每隔一分鐘拍下任務(wù)完成情況和能量消耗的快照,并將其作為任務(wù)到達(dá)率γ的函數(shù)進(jìn)行繪制(見圖7).結(jié)果符合預(yù)期,Oracle的結(jié)果最理想,NC表現(xiàn)最差.PC的結(jié)果次好,但也消耗更多能量.在到達(dá)率上升到總標(biāo)準(zhǔn)到達(dá)率的約60%之前,RD和PD的性能優(yōu)于PC,明顯優(yōu)于非協(xié)作情況.并且RD的功耗僅略高于PC,PD在該點(diǎn)附近甚至低于PC.但是隨著目標(biāo)到達(dá)率的升高,分布式算法的性能明顯降低.此外,圖7(b)顯示了RD在更高的目標(biāo)到達(dá)率下的較低功耗,但這也與其性能的下降一致.這是因?yàn)殡S著目標(biāo)到達(dá)率升高,越來越多的鄰節(jié)點(diǎn)更加忙碌.實(shí)驗(yàn)表明分布式算法適合較低的任務(wù)到達(dá)率,而集中式算法適合較高的任務(wù)到達(dá)率.

圖6 仿真時(shí)間內(nèi)每個(gè)節(jié)點(diǎn)的任務(wù)到達(dá)率Fig.6 Task arrival rate per nodes over simulation time

圖7 仿真過程中的任務(wù)處理與能耗情況Fig.7 Task processing and energy consumption in the simulation process

實(shí)驗(yàn)中將處理得分定義為在分配時(shí)間內(nèi)成功執(zhí)行的任務(wù)與到達(dá)任務(wù)的百分比,并將其作為能量消耗的函數(shù)進(jìn)行繪制(見圖8).效能得分定義為成功執(zhí)行量與消耗能量的比率,結(jié)果見表2.綜合比較表2和圖8發(fā)現(xiàn),圖8中性能和能耗幾乎成線性關(guān)系,這意味著在必要的時(shí)候可以通過增加額外的能耗來提高性能,只要所有節(jié)點(diǎn)的任務(wù)到達(dá)率小于無人機(jī)網(wǎng)絡(luò)的總計(jì)算能力,就可以考慮通過增加一定的能耗來換取性能和效率上的收益.

表2 仿真結(jié)果(平均超過100次)
Table 2 Simulation results(averaged over 100 runs)

算法到達(dá)率/分鐘服務(wù)率/分鐘能量消耗(J)處理得分效能得分(/100J)NCOPCPDRD6.916.916.916.916.914.346.105.844.845.3499510611055100910430.630.880.850.700.770.440.570.550.480.51

圖8 所提算法的處理得分Fig.8 Process score of proposed algorithms

6 結(jié) 論

本文使用Open Jackson網(wǎng)絡(luò)將多無人機(jī)邊緣自組網(wǎng)絡(luò)建模為隊(duì)列網(wǎng)絡(luò).提出了多種主動(dòng)式和反饋式協(xié)作算法,與非協(xié)作的無卸載式方案相比,顯著提高了無人機(jī)編隊(duì)野外作業(yè)系統(tǒng)的性能.結(jié)果符合預(yù)期,即如果總?cè)蝿?wù)到達(dá)率小于總計(jì)算能力,并且其他節(jié)點(diǎn)的NSI可用,系統(tǒng)就可以不依賴云端在邊緣完成所有任務(wù).反饋分布式和主動(dòng)集中式分別適用于不同的外部任務(wù)到達(dá)率,在未來的工作中,我們計(jì)劃制定一個(gè)混合策略,可以根據(jù)任務(wù)到達(dá)率在它們之間切換.并且在真實(shí)的動(dòng)態(tài)場景上應(yīng)用該方案.