基于權(quán)重控制剪枝的無(wú)人機(jī)服務(wù)替換方法

孫士勇，劉 暢，孫 琳，李萍萍，陳勝楠，陳昊鵬，歸 琳

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081；2.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200240)

0 引言

無(wú)人機(jī)技術(shù)在過(guò)去的幾十年里得到了突飛猛進(jìn)的發(fā)展，這使得在各種領(lǐng)域應(yīng)用無(wú)人機(jī)成為可能，包括民用領(lǐng)域的航拍和軍事領(lǐng)域的目標(biāo)跟蹤以及信息采集等等。鑒于其便于搭載傳感器的特點(diǎn)以及移動(dòng)性強(qiáng)的優(yōu)勢(shì)，越來(lái)越多的無(wú)人機(jī)將被投入使用。因此，針對(duì)無(wú)人機(jī)各種問(wèn)題的研究也逐漸成了近些年來(lái)許多學(xué)者研究的熱門。無(wú)人機(jī)內(nèi)部問(wèn)題的研究圍繞單個(gè)個(gè)體展開(kāi)，例如文獻(xiàn)[1]提出了在無(wú)人機(jī)機(jī)翼發(fā)生故障后如何進(jìn)行自適應(yīng)飛行角度控制。文獻(xiàn)[2]針對(duì)無(wú)人機(jī)可能受到的干擾問(wèn)題提出了安全態(tài)勢(shì)感知方法，以提高戰(zhàn)場(chǎng)中的無(wú)人機(jī)的防御能力。文獻(xiàn)[3]針對(duì)多無(wú)人機(jī)多任務(wù)場(chǎng)景，考慮深度學(xué)習(xí)應(yīng)用于無(wú)人機(jī)自主決策規(guī)劃，以適應(yīng)復(fù)雜多變的戰(zhàn)場(chǎng)場(chǎng)景。無(wú)人機(jī)外部問(wèn)題包括飛行路徑設(shè)計(jì)等整體規(guī)劃研究，文獻(xiàn)[4]設(shè)計(jì)編排了無(wú)人機(jī)群覆蓋模型以提高目標(biāo)區(qū)域覆蓋率進(jìn)而提升效率。文獻(xiàn)[5]考慮了無(wú)人機(jī)群的吞吐量以及飛行能耗，設(shè)計(jì)了節(jié)能的無(wú)人機(jī)軌跡路徑。文獻(xiàn)[6]將無(wú)人機(jī)群作為移動(dòng)基站，基于能耗問(wèn)題進(jìn)行了基站和無(wú)人機(jī)的聯(lián)合優(yōu)化。文獻(xiàn)[7-8]針對(duì)無(wú)人機(jī)目標(biāo)跟蹤定位問(wèn)題，采用無(wú)人機(jī)群傳感器數(shù)據(jù)收集分析的方式完成對(duì)被測(cè)目標(biāo)的定位。

在實(shí)際應(yīng)用場(chǎng)景中，許多學(xué)者的研究熱點(diǎn)問(wèn)題大多是由于無(wú)人機(jī)所處環(huán)境及其高移動(dòng)性所帶來(lái)的不穩(wěn)定性所導(dǎo)致的，例如飛行過(guò)程中可能受到各種干擾，包括對(duì)抗場(chǎng)景下的干擾以及空間環(huán)境的干擾等等，這些干擾會(huì)影響無(wú)人機(jī)的工作。還有很大一部分的研究是針對(duì)于無(wú)人機(jī)的能耗以及效率問(wèn)題展開(kāi)的，目標(biāo)是在有限的能源條件下盡可能多地完成任務(wù)。

上述研究多基于無(wú)人機(jī)具有可控的飛行狀態(tài)，本文關(guān)注的是另一個(gè)非常重要的問(wèn)題：在無(wú)人機(jī)發(fā)崩潰過(guò)載無(wú)法正常工作或失聯(lián)時(shí)，為了盡可能使正在執(zhí)行的任務(wù)處理不受影響，需要快速尋找替代的無(wú)人機(jī)群以替補(bǔ)完成原始任務(wù)。為此，將無(wú)人機(jī)具備的能力資源描述為服務(wù)，任務(wù)抽象成由一個(gè)或多個(gè)服務(wù)構(gòu)成的工作流，無(wú)人機(jī)崩潰映射成服務(wù)崩潰。在此抽象模型下，無(wú)人機(jī)崩潰后由其他節(jié)點(diǎn)執(zhí)行崩潰任務(wù)就映射成了服務(wù)替換問(wèn)題。當(dāng)崩潰任務(wù)復(fù)雜時(shí)，需要多架無(wú)人機(jī)以工作流的形式完成組合服務(wù)替換，因此需要研究服務(wù)組合替換問(wèn)題。

服務(wù)組合替換的核心一方面是需要完成任務(wù)-服務(wù)資源的語(yǔ)義匹配，另一方面是快速獲取最優(yōu)性能下的替換方案。前者通過(guò)服務(wù)組合圖方法生成替補(bǔ)無(wú)人機(jī)解空間，后者需要通過(guò)剪枝算法來(lái)實(shí)現(xiàn)解空間的快速收斂。針對(duì)上述兩方面問(wèn)題，引入組合服務(wù)替換流程，包括2個(gè)部分：① 組合服務(wù)圖構(gòu)建；② 剪枝算法。目前,剪枝算法的研究多針對(duì)神經(jīng)網(wǎng)絡(luò)下的修剪以及對(duì)機(jī)器學(xué)習(xí)生成的決策樹(shù)進(jìn)行剪枝，例如文獻(xiàn)[10]提出了采集、決策到剪枝的三步策略，通過(guò)結(jié)構(gòu)化剪枝以及細(xì)粒度剪枝來(lái)完成神經(jīng)網(wǎng)絡(luò)的去冗余。文獻(xiàn)[11]針對(duì)3種非結(jié)構(gòu)化剪枝技術(shù)展開(kāi)研究，分析了剪枝對(duì)于神經(jīng)網(wǎng)絡(luò)帶來(lái)的影響。文獻(xiàn)[12]通過(guò)對(duì)于神經(jīng)網(wǎng)絡(luò)隱藏層神經(jīng)元的刪除，達(dá)到修剪神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的同時(shí)提高其泛化能力的修剪目的。文獻(xiàn)[13]提出了一種后剪枝算法，在不犧牲精度的情況下降低了決策樹(shù)的復(fù)雜度。文獻(xiàn)[14]提出了一種并行共享決策樹(shù)的不精確錯(cuò)誤剪枝算法，優(yōu)化了決策樹(shù)分類問(wèn)題。本文則從無(wú)人機(jī)場(chǎng)景出發(fā)，為實(shí)現(xiàn)最佳路徑的快速回溯而進(jìn)行剪枝。

本文從無(wú)人機(jī)場(chǎng)景出發(fā)，為實(shí)現(xiàn)最佳路徑的快速回溯而進(jìn)行剪枝。說(shuō)明了組合服務(wù)圖的構(gòu)建流程，提出了一種基于權(quán)重的剪枝算法，用于減少對(duì)于可用無(wú)人機(jī)資源遍歷所產(chǎn)生的復(fù)雜度，從而高效地找到一組可替換崩潰節(jié)點(diǎn)的無(wú)人機(jī)群，盡可能地提高原始任務(wù)的完成率，對(duì)基于權(quán)重控制剪枝算法的有效性進(jìn)行了驗(yàn)證。

1 問(wèn)題建模與組合服務(wù)圖構(gòu)建

組合服務(wù)替換過(guò)程僅在發(fā)現(xiàn)正在執(zhí)行任務(wù)的無(wú)人機(jī)系統(tǒng)崩潰過(guò)載已無(wú)法正常工作或因故失聯(lián)與墜毀時(shí)才會(huì)啟用，尋找一組或多組無(wú)人機(jī)群，完成對(duì)崩潰服務(wù)的替換。首先需要尋找無(wú)人機(jī)組合服務(wù)配對(duì)，而進(jìn)行服務(wù)替換的依據(jù)是節(jié)點(diǎn)之間的輸入?yún)?shù)以及輸出參數(shù)的關(guān)系，當(dāng)一個(gè)服務(wù)的輸出參數(shù)與另一個(gè)服務(wù)的輸入?yún)?shù)保持一致時(shí)，就可以認(rèn)為2個(gè)服務(wù)之間屬于前驅(qū)服務(wù)以及后繼服務(wù)的關(guān)系。在這里，將崩潰服務(wù)前后的2個(gè)節(jié)點(diǎn)抽象為替補(bǔ)節(jié)點(diǎn)集的源節(jié)點(diǎn)和終端節(jié)點(diǎn)，源節(jié)點(diǎn)只有輸出參數(shù)OutS，它與崩潰服務(wù)節(jié)點(diǎn)的輸入?yún)?shù)InC相匹配；終端節(jié)點(diǎn)只有輸入?yún)?shù)InT，它與崩潰服務(wù)節(jié)點(diǎn)的輸出參數(shù)OutC相匹配，如圖1所示。

圖1 崩潰節(jié)點(diǎn)輸入輸出參數(shù)Fig.1 Input and output parameters of crash node

組合服務(wù)參數(shù)匹配算法的過(guò)程就是不斷地推進(jìn)尋找輸入輸出相匹配的后繼服務(wù)節(jié)點(diǎn)，直到從崩潰服務(wù)的前驅(qū)節(jié)點(diǎn)找到其后繼節(jié)點(diǎn)的過(guò)程。首先完成崩潰任務(wù)到候選子任務(wù)流之間的重構(gòu)，以此確定崩潰任務(wù)需要由幾個(gè)節(jié)點(diǎn)完成以及節(jié)點(diǎn)編排順序；其次，完成子任務(wù)到無(wú)人機(jī)服務(wù)節(jié)點(diǎn)的映射。當(dāng)無(wú)可用無(wú)人機(jī)來(lái)完成任務(wù)流到服務(wù)的匹配時(shí)，重新生成工作流調(diào)度關(guān)系，細(xì)化任務(wù)屬性并擴(kuò)充節(jié)點(diǎn)集來(lái)完成任務(wù)流的構(gòu)建，直到找到合適的替補(bǔ)無(wú)人機(jī)群對(duì)原崩潰無(wú)人機(jī)節(jié)點(diǎn)進(jìn)行替換，保證任務(wù)的順利執(zhí)行。其結(jié)果描述為組合服務(wù)圖的形式，如圖2所示?？紤]S?W1?X1路徑，由于在X1處無(wú)法完成推進(jìn)，即沒(méi)有合適的無(wú)人機(jī)節(jié)點(diǎn)完成匹配，因此將整條路徑判定為無(wú)效路徑，細(xì)化任務(wù)屬性并擴(kuò)充路徑節(jié)點(diǎn)數(shù)量，再次進(jìn)行組合服務(wù)圖構(gòu)建。組合服務(wù)圖是一個(gè)有向無(wú)環(huán)圖(Directed Acyclic Graph，DAG)，即一個(gè)無(wú)回路的有向圖，對(duì)于圖中所有非源節(jié)點(diǎn)，都可能存在多條從起點(diǎn)到該節(jié)點(diǎn)的不同路徑，但是有向無(wú)環(huán)圖只存在一個(gè)源節(jié)點(diǎn)以及一個(gè)終端節(jié)點(diǎn)，用白色圓圈表示，圖中的每一個(gè)其他節(jié)點(diǎn)都代表了組合替換過(guò)程中找到的候選無(wú)人機(jī)服務(wù)，用黑色或灰色表示，可以稱其為候選服務(wù)節(jié)點(diǎn)，每個(gè)連接代表服務(wù)執(zhí)行先后順序的偏序關(guān)系，這種偏序關(guān)系中包含無(wú)人機(jī)服務(wù)節(jié)點(diǎn)之間的選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和并行結(jié)構(gòu)等，文獻(xiàn)[9]證明這些結(jié)構(gòu)都可以被轉(zhuǎn)換成順序結(jié)構(gòu)。

圖2 無(wú)人機(jī)任務(wù)組合服務(wù)Fig.2 UAV task composite service

通過(guò)組合服務(wù)替換算法，最終將會(huì)得到一個(gè)包含多條路徑的可選替換集合(Collection)，其中每條從源節(jié)點(diǎn)到終端節(jié)點(diǎn)的路徑都是由一組候選服務(wù)集(Set)構(gòu)成的組合替換方案，其中的候選服務(wù)集可以看作是當(dāng)前組合替換方案中對(duì)崩潰服務(wù)的“分解”。在匹配過(guò)程中當(dāng)組合服務(wù)圖構(gòu)建的某條路徑無(wú)論如何推進(jìn)都無(wú)法到達(dá)終端節(jié)點(diǎn)時(shí)，為避免搜索深度過(guò)深導(dǎo)致搜索空間過(guò)大現(xiàn)象的發(fā)生，預(yù)先設(shè)定了最長(zhǎng)推進(jìn)路徑深度l，當(dāng)超過(guò)此深度時(shí)，判定此條路徑無(wú)法推進(jìn)到終端節(jié)點(diǎn)。在匹配過(guò)程中，出入度數(shù)量較多的候選節(jié)點(diǎn)是多條路徑的交匯點(diǎn)，在搜索匹配過(guò)程中將會(huì)被重復(fù)檢索，為提升執(zhí)行效率，采用記憶化的搜索方式來(lái)推進(jìn)組合服務(wù)圖的構(gòu)建，保存節(jié)點(diǎn)的歷史匹配結(jié)果，在匹配后繼服務(wù)時(shí)，若在歷史記錄中存在，則直接調(diào)用匹配結(jié)果，例如圖中的X2節(jié)點(diǎn)與Y節(jié)點(diǎn)，第一次匹配后的結(jié)果將作為歷史數(shù)據(jù)被記錄。

在查找可替換無(wú)人機(jī)的過(guò)程中，遵循的原則為優(yōu)先從具有連接關(guān)系的候補(bǔ)無(wú)人機(jī)群中搜尋匹配無(wú)人機(jī)，當(dāng)無(wú)可匹配無(wú)人機(jī)時(shí)，進(jìn)行資源補(bǔ)充，增加可用在線無(wú)人機(jī)數(shù)量，列入組合服務(wù)圖中，使用虛線表示，如圖2中的節(jié)點(diǎn)Z2就是補(bǔ)充的無(wú)人機(jī)節(jié)點(diǎn)。

2 權(quán)重控制剪枝算法

通過(guò)組合服務(wù)替換之后，可以得到一個(gè)由多條分支組成的有向無(wú)環(huán)圖，這個(gè)多節(jié)點(diǎn)的有向無(wú)環(huán)圖存在多條連接，當(dāng)替補(bǔ)無(wú)人機(jī)數(shù)量龐大時(shí)，需要利用剪枝算法對(duì)不滿足崩潰服務(wù)資源約束條件的路徑進(jìn)行修剪，從而降低最優(yōu)路徑搜索復(fù)雜度，高效完成組合路徑回溯。剪枝算法查找路徑的最終目標(biāo)是找到一條如圖2所示的黑色節(jié)點(diǎn)路徑，完成服務(wù)最佳替換。

由于在組合服務(wù)圖構(gòu)建過(guò)程中已經(jīng)完成了前驅(qū)后繼節(jié)點(diǎn)的匹配，因此剪枝算法的依據(jù)不再來(lái)自于提供服務(wù)的無(wú)人機(jī)輸入輸出參數(shù)，而是基于各條路徑的服務(wù)組合結(jié)果與崩潰無(wú)人機(jī)服務(wù)的資源約束RC。隨著無(wú)人機(jī)技術(shù)的不斷發(fā)展，其可攜帶的資源類型將會(huì)越來(lái)越多，可以將無(wú)人機(jī)資源歸結(jié)為2類：第1類為可疊加資源，例如CPU資源、內(nèi)存資源以及通信資源等等，在多個(gè)無(wú)人機(jī)節(jié)點(diǎn)進(jìn)行資源疊加后可以滿足崩潰節(jié)點(diǎn)資源的條件時(shí)，認(rèn)為該替補(bǔ)無(wú)人機(jī)集合滿足資源約束條件，可以替換；另一類為不可疊加資源，不同無(wú)人機(jī)擁有同類型資源時(shí)，不能進(jìn)行資源的疊加處理，例如攝像精度、傳感器功率等等，當(dāng)多個(gè)節(jié)點(diǎn)擁有這類服務(wù)能力時(shí)，取無(wú)人機(jī)群中最佳的節(jié)點(diǎn)作為集合資源能力。

現(xiàn)有的剪枝方法多集中在同一維度下進(jìn)行，沒(méi)有考慮到資源屬性及其類型的多樣化，但是在組合服務(wù)替換過(guò)程中生成的有向無(wú)環(huán)圖中的不同無(wú)人機(jī)節(jié)點(diǎn)卻擁有多維度不同屬性的資源約束，按照?qǐng)D2進(jìn)行舉例，替補(bǔ)無(wú)人機(jī)W2當(dāng)前空余的CPU資源可以提供計(jì)算能力，替補(bǔ)無(wú)人機(jī)X2當(dāng)前空閑的轉(zhuǎn)發(fā)器可以提供一定的通信能力，這些資源信息來(lái)自于不同維度的表征，一個(gè)節(jié)點(diǎn)存在一個(gè)到多個(gè)的不同維度的能力，其約束要求也不盡相同，這就使得一般的方法不再適用。

本文提出了一種基于權(quán)重的剪枝算法，可以處理每個(gè)節(jié)點(diǎn)擁有不同維度資源的情況。剪枝算法輸入來(lái)自于組合服務(wù)圖構(gòu)建算法中生成的組合服務(wù)圖。每一個(gè)節(jié)點(diǎn)都存在各自的資源使用情況，因此每條可選替補(bǔ)路徑都存在多維度資源，崩潰服務(wù)節(jié)點(diǎn)也存在多維度資源，必須在查找替換無(wú)人機(jī)群的過(guò)程中選出一條能夠覆蓋崩潰無(wú)人機(jī)資源的最優(yōu)路徑。

為降低剪枝搜索復(fù)雜度，采用了兩步剪枝的方式：第一步靜態(tài)剪枝，在剪枝過(guò)程中對(duì)于每層節(jié)點(diǎn)集合，根據(jù)預(yù)先設(shè)定的閾值，優(yōu)先將可用資源過(guò)小的節(jié)點(diǎn)以及負(fù)載過(guò)大的節(jié)點(diǎn)進(jìn)行剪枝。第二步需求值剪枝需要計(jì)算節(jié)點(diǎn)需求值，首先針對(duì)每個(gè)節(jié)點(diǎn)自身進(jìn)行計(jì)算，可以提供較多維度資源并且每種維度資源越多的輕負(fù)載無(wú)人機(jī)節(jié)點(diǎn)在加權(quán)后將生成越大需求值，同時(shí)考慮到無(wú)人機(jī)網(wǎng)絡(luò)層間節(jié)點(diǎn)并非全連接狀態(tài)，因此在計(jì)算結(jié)點(diǎn)需求值時(shí)，把每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)情況也作為計(jì)算權(quán)重的因素之一。鑒于無(wú)人機(jī)具有部署靈活性的特點(diǎn)，可補(bǔ)充無(wú)人機(jī)資源作為可選替補(bǔ)節(jié)點(diǎn)，但是考慮到無(wú)人機(jī)飛行開(kāi)銷以及資源部署時(shí)間消耗，因此不做優(yōu)先使用，僅在無(wú)可用替換路徑時(shí)作為備選項(xiàng)。

獲取了每個(gè)節(jié)點(diǎn)的需求值后，算法在每層節(jié)點(diǎn)集合中按照需求值進(jìn)行排序，根據(jù)既定修剪率刪除每層中需求值較小的節(jié)點(diǎn)以減小最優(yōu)路徑搜索計(jì)算復(fù)雜度，再采用枚舉方式獲得路徑需求值最大的節(jié)點(diǎn)與路徑，這種方式將在不影響精度的情況下有效地縮短最優(yōu)路徑查找的工作量。最后驗(yàn)證其資源組合結(jié)果是否滿足崩潰服務(wù)的資源約束RC，若符合條件，就將其作為最終替換路徑，否則就重新依據(jù)路徑需求值大小查找符合崩潰服務(wù)資源約束的替換路徑。剪枝算法的性能依賴于組合服務(wù)圖的規(guī)模，即路徑數(shù)以及路徑上的節(jié)點(diǎn)數(shù)。算法偽代碼如下所示。

算法1 權(quán)重控制剪枝算法輸入:組合服務(wù)圖G(nodes),節(jié)點(diǎn)資源信息Resource(nodes),節(jié)點(diǎn)負(fù)載信息Load(nodes);輸出:最佳替補(bǔ)無(wú)人機(jī)節(jié)點(diǎn)集Set;1.L ← getNumofLayers(G);2.forl ← 1 to Ldo3. fornode in Gdo4. ifResource (node,l) > thresholdr and Load (node,l) < thresh-oldlthen5. Add node to afterFirstPrune (node,l);6. end if7. end for8.end for9.forl ← 1 to Ldo10. fornode in afterFirstPrune (node,l)do11. Value (node,l) = calculateNodeValue (G,Resource,Load,node);12. end for13. reorderedNodesSet (node,l) = numSort (Value (node,l));14. Add node to afterSecondPrune (node,l) according to reordered-NodesSet (node,l) and pruneRate;15.end for16.count ← 1;17.while true do18. selectedPath = choosePathValue (afterSecondPrune,count);19. ifselectedPath match Constraintsthen20. Add selectedPath to Set;21. break;22. else23. Add selectedPath to invalidPath;24. count = count + 1;25. end if26.end while

算法第1行獲取了組合服務(wù)圖深度；第2～8行完成了第一步靜態(tài)剪枝；第9～15行完成了第二步需求值剪枝；第16～26行完成了最佳候選節(jié)點(diǎn)集的選取以及資源約束的匹配，最終輸出最佳節(jié)點(diǎn)集。

偽代碼第11行的節(jié)點(diǎn)需求值計(jì)算式為：

3 仿真分析

針對(duì)服務(wù)組合替換所構(gòu)建得到的有向無(wú)環(huán)圖進(jìn)行仿真，模擬圖1中無(wú)人機(jī)的工作場(chǎng)景。在節(jié)點(diǎn)C發(fā)生崩潰之前，正常工作流調(diào)度順序依照S?C?T的順序進(jìn)行，當(dāng)節(jié)點(diǎn)C發(fā)生崩潰之后，系統(tǒng)根據(jù)任務(wù)流調(diào)度順序優(yōu)先進(jìn)行深度為1的S?C’?T的任務(wù)流調(diào)度模式匹配，查找當(dāng)前可用無(wú)人機(jī)資源池中是否有單個(gè)可直接替補(bǔ)的節(jié)點(diǎn)完成崩潰無(wú)人機(jī)的任務(wù)，當(dāng)無(wú)可用服務(wù)存在時(shí)，查找深度為2的S?W?X?T任務(wù)流調(diào)度模式尋找無(wú)人機(jī)服務(wù)資源進(jìn)行替換，當(dāng)依舊不存在合適解進(jìn)行替換，即無(wú)法找到滿足此任務(wù)流執(zhí)行關(guān)系的節(jié)點(diǎn)時(shí)，系統(tǒng)將進(jìn)一步細(xì)分工作流為深度3的S?W?X?Y?T甚至深度4的S?W?X?Y?Z?T的子任務(wù)流執(zhí)行關(guān)系，直到存在可用替補(bǔ)無(wú)人機(jī)服務(wù)資源滿足工作流關(guān)系或達(dá)到深度上限為止，不同細(xì)分程度的工作流體現(xiàn)為最長(zhǎng)組合路徑深度的差異，最終形成組合服務(wù)圖。

仿真基于S?C?T的無(wú)人機(jī)任務(wù)流執(zhí)行關(guān)系完成資源崩潰下的替換，搜尋S?C’?T,S?W?X?T,S?W?X?Y?T以及S?W?X?Y?Z?T幾種不同深度下的任務(wù)流調(diào)度關(guān)系以及候補(bǔ)無(wú)人機(jī)服務(wù)映射，實(shí)現(xiàn)崩潰任務(wù)的重調(diào)度。在深度為4的工作流下，隨機(jī)生成如圖3所示的無(wú)人機(jī)集合組合服務(wù)圖。第1層可完成W任務(wù)的替補(bǔ)無(wú)人機(jī)節(jié)點(diǎn)為1 000個(gè)，分別用W1～W1 000表示，第2層可完成X任務(wù)的無(wú)人機(jī)節(jié)點(diǎn)為10個(gè)，分別用X1～X10表示，第3層無(wú)人機(jī)節(jié)點(diǎn)為10個(gè)，用Y1～Y10表示，第4層無(wú)人機(jī)節(jié)點(diǎn)為2個(gè)，用Z1，Z2表示，同時(shí)，每一層都有2個(gè)可以補(bǔ)充的無(wú)人機(jī)節(jié)點(diǎn)，用虛線表示節(jié)點(diǎn)及其連接關(guān)系。仿真設(shè)置的無(wú)人機(jī)節(jié)點(diǎn)參數(shù)抽象為：CPU資源、通信帶寬資源、攝像分辨率以及負(fù)載，仿真中組合服務(wù)圖每個(gè)節(jié)點(diǎn)之間的差異性表現(xiàn)在這4個(gè)參數(shù)上。

圖3 仿真場(chǎng)景無(wú)人機(jī)組合服務(wù)圖Fig.3 UAV composite service diagram in simulation scenario

在組合服務(wù)圖構(gòu)建時(shí)，為了體現(xiàn)算法應(yīng)用場(chǎng)景的隨機(jī)性，無(wú)人機(jī)節(jié)點(diǎn)層間連接關(guān)系隨機(jī)生成，由于工作流的特性，層內(nèi)節(jié)點(diǎn)之間沒(méi)有連接關(guān)系；無(wú)人機(jī)節(jié)點(diǎn)的資源以及負(fù)載情況隨機(jī)生成，其中CPU資源以及帶寬余量作為可疊加性資源，采用[0,100]內(nèi)的隨機(jī)數(shù)表示，最大空閑資源量為100；攝像分辨率作為不可疊加性資源，采用{0,1}隨機(jī)表示，當(dāng)滿足崩潰節(jié)點(diǎn)精度要求時(shí)，值為1，否則為0；負(fù)載量采用[0,100]內(nèi)的隨機(jī)數(shù)表示，滿負(fù)荷表示為100，在需求值計(jì)算過(guò)程中，統(tǒng)一根據(jù)需求值計(jì)算公式采用歸一化的方式計(jì)算。組合服務(wù)圖對(duì)剪枝算法性能的影響表現(xiàn)為最長(zhǎng)組合路徑深度的區(qū)別、每層節(jié)點(diǎn)數(shù)量的不同以及無(wú)人機(jī)之間不同的連接關(guān)系上，其影響有向無(wú)環(huán)圖的組合路徑數(shù)量，最終影響剪枝算法執(zhí)行效率。在仿真過(guò)程中，由于每層之間不是全連通網(wǎng)絡(luò)，因此組合路徑數(shù)量將不會(huì)超過(guò)最大組合的路徑數(shù)量。

仿真首先基于深度為1的S?C’?T組合服務(wù)圖進(jìn)行剪枝以及最優(yōu)路徑查找，也就是僅針對(duì)圖3中的第一層進(jìn)行，當(dāng)未找到現(xiàn)有服務(wù)完成一對(duì)一替換時(shí)，依據(jù)深度為2的S?W?X?T組合服務(wù)圖進(jìn)行剪枝與最優(yōu)路徑查找，也就是圖3中第1層加第2層的形式，以此類推增加查找深度，直到找到最優(yōu)路徑或達(dá)到深度上限。本文基于最大深度為4下的不同最長(zhǎng)組合路徑深度情況進(jìn)行仿真，考慮組合服務(wù)圖的連通性以及是否剪枝，分析4種情況下系統(tǒng)運(yùn)行時(shí)間如表1所示。

表1 網(wǎng)絡(luò)連通性以及剪枝對(duì)于系統(tǒng)性能的影響Tab.1 Influence of network connectivity and pruning on system performance

可以發(fā)現(xiàn)，在路徑深度為2時(shí)，4種場(chǎng)景下的性能一致，這是由于當(dāng)采用S?C’?T的工作流形式時(shí)，網(wǎng)絡(luò)為簡(jiǎn)單的單層扁平式結(jié)構(gòu)，需要遍歷計(jì)算最佳路徑導(dǎo)致剪枝算法不起作用。由于最長(zhǎng)組合路徑深度的增加導(dǎo)致連接數(shù)的增多與復(fù)雜性的增大，系統(tǒng)執(zhí)行時(shí)間將會(huì)增加。但是可以發(fā)現(xiàn)，隨著工作流的細(xì)分與路徑數(shù)量的逐漸增加，無(wú)論是在層間全連接還是在層間隨機(jī)連接的情況下，權(quán)重控制剪枝算法的性能均可以得到較大的改善，證明了本算法的有效性。

4 結(jié)束語(yǔ)

針對(duì)執(zhí)行任務(wù)的無(wú)人機(jī)發(fā)生崩潰的場(chǎng)景展開(kāi)討論，分析了無(wú)人機(jī)發(fā)生崩潰時(shí)應(yīng)采取的流程。將組合服務(wù)替換過(guò)程分解為2個(gè)步驟，先進(jìn)行組合服務(wù)圖的構(gòu)建，再對(duì)構(gòu)建好的圖進(jìn)行權(quán)重控制剪枝算法來(lái)完成多維復(fù)雜資源類型多節(jié)點(diǎn)的剪枝處理?？紤]可疊加性資源、不可疊加性資源以及節(jié)點(diǎn)間的連接關(guān)系，采用2步剪枝的方式來(lái)減少最優(yōu)路徑查找復(fù)雜度，最終完成組合路徑的回溯，以較快的方式獲得最佳無(wú)人機(jī)替換選擇。仿真驗(yàn)證了算法的有效性，相較于不剪枝的直接搜索方法，在具有較長(zhǎng)深度組合路徑的長(zhǎng)度下，權(quán)重控制剪枝算法使最佳路徑回溯的時(shí)間大大縮短。