安 雷,吉 兵,李召瑞

(陸軍工程大學(xué)石家莊校區(qū),河北 石家莊 050051)

隨著合成孔徑雷達(dá)、相控陣?yán)走_(dá)、敵我識(shí)別器、前視紅外雷達(dá)、電子支持測量等先進(jìn)傳感器在軍事領(lǐng)域的大量應(yīng)用,如何有效提高傳感器利用效率,實(shí)現(xiàn)對(duì)傳感器的快速、自動(dòng)管理,實(shí)現(xiàn)對(duì)觀測數(shù)據(jù)的高效集成和處理成為了傳感器管理和傳感器調(diào)度研究的熱點(diǎn)。傳感器調(diào)度作為傳感器管理的一個(gè)重要組成部分,指在確定的時(shí)間區(qū)間內(nèi),在遵循各類約束條件的前提下,根據(jù)傳感器資源可用情況和目標(biāo)探測需求,為各探測目標(biāo)分配適當(dāng)?shù)膫鞲衅髻Y源和探測時(shí)間區(qū)間,生成每個(gè)傳感器在該時(shí)間區(qū)間內(nèi)的工作計(jì)劃,從而達(dá)到某項(xiàng)或某些指標(biāo)的綜合最優(yōu)。傳感器管理研究主要關(guān)注的是優(yōu)化方法、制定策略,與控制論、統(tǒng)計(jì)學(xué)、信息論、信號(hào)處理等學(xué)科密切相關(guān)[1],相比之下,傳感器調(diào)度則更偏向于對(duì)傳感器每一時(shí)刻狀態(tài)的管理和控制,例如控制傳感器定時(shí)開關(guān)機(jī)、按照既定策略選擇工作模式、根據(jù)目標(biāo)運(yùn)動(dòng)狀態(tài)確定機(jī)動(dòng)方向等。

1 部分可觀馬爾可夫決策過程

結(jié)合已有文獻(xiàn),可以將傳感器調(diào)度簡要描述為一個(gè)決策過程，即以雷達(dá)等為終端的傳感器系統(tǒng)在一定的約束條件下,依據(jù)k時(shí)刻追蹤目標(biāo)所得到的測量信息zk,制定傳感器下一步控制動(dòng)作,以達(dá)到使回報(bào)期望最大化或風(fēng)險(xiǎn)函數(shù)最小化的目的。這個(gè)過程實(shí)際上就是馬爾可夫決策過程(Markov Decision Process,MDP)[2],這里假設(shè)了k+1時(shí)刻傳感器的控制動(dòng)作僅由k時(shí)刻對(duì)跟蹤目標(biāo)的觀測值z(mì)k決定,而且所跟蹤目標(biāo)的狀態(tài)是完全可以被傳感器觀測到的。但實(shí)際上由于敵方干擾以及使用代價(jià)影響等因素,目標(biāo)狀態(tài)的觀測是不完全的,測量得到的信息存在一定的不確定性,由此便引入了部分可觀馬爾可夫決策過程(Partially Observed MDP,POMPD)[3],通過利用POMDP對(duì)傳感器調(diào)度問題進(jìn)行建模,可以在測量得到的不完全信息的基礎(chǔ)上,僅憑歷史調(diào)度策略集和當(dāng)前調(diào)度動(dòng)作反饋效果進(jìn)行決策,為有效改善動(dòng)態(tài)不確定情況下的調(diào)度性能,提供了可靠的理論基礎(chǔ)和可行的解決方案,其基本架構(gòu)如圖1所示。

該圖可利用六元組〈S,A,Z,T,R,O〉來表示,其中,S表示狀態(tài)集,為所有可能環(huán)境狀態(tài)的集合;A表示行動(dòng)集,為系統(tǒng)所有可選調(diào)度動(dòng)作的集合;Z表示觀測集,為系統(tǒng)所有觀測結(jié)果的集合;T為狀態(tài)轉(zhuǎn)移函數(shù),指系統(tǒng)在狀態(tài)s的情況下執(zhí)行動(dòng)作a后轉(zhuǎn)移到狀態(tài)s′的概率,表示為T(s,a,s′);R為回報(bào)函數(shù),表示在狀態(tài)s的情況下執(zhí)行動(dòng)作a之后得到反饋結(jié)果,其值滿足Rmin≤R≤Rmax;O為觀察函數(shù),指在上一時(shí)刻系統(tǒng)采取動(dòng)作a后,由狀態(tài)s轉(zhuǎn)移到狀態(tài)s′,觀察得到z的概率,表示為O(s′,a,z)[4-5]。其具體的運(yùn)行流程為:在已知狀態(tài)sk和觀測值z(mì)k的情況下,從行動(dòng)集A中選取調(diào)度動(dòng)作ak,產(chǎn)生單步收益R,則狀態(tài)sk在狀態(tài)轉(zhuǎn)移函數(shù)T的作用下變?yōu)閟k+1,同時(shí)根據(jù)觀測函數(shù)O,得到觀測值z(mì)k+1,并依次反復(fù)循環(huán)。

2 傳感器調(diào)度基本模型

面向目標(biāo)跟蹤的傳感器調(diào)度,主要以目標(biāo)跟蹤為應(yīng)用場景、以跟蹤精度和使用代價(jià)綜合效能最佳為優(yōu)化指標(biāo),創(chuàng)建目標(biāo)函數(shù)、求解調(diào)度方案,實(shí)施傳感器資源選擇和分配,使傳感器系統(tǒng)達(dá)到最優(yōu)的工作狀態(tài),其基本模型如圖2所示。

基于圖2,可以將調(diào)度過程視為一個(gè)“跟蹤—調(diào)度—反饋”的閉環(huán)回路,能夠有效克服目標(biāo)跟蹤中存在的動(dòng)態(tài)變化問題,具備根據(jù)傳感器觀測數(shù)據(jù)更新目標(biāo)和環(huán)境狀態(tài),依據(jù)使用代價(jià)預(yù)測和跟蹤精度預(yù)測進(jìn)行未來傳感器調(diào)度規(guī)劃,分配傳感器繼續(xù)完成跟蹤目標(biāo)任務(wù)的功能。其基本流程為:在某一k時(shí)刻,系統(tǒng)以自身傳感器的相關(guān)參數(shù)、作戰(zhàn)目標(biāo)機(jī)動(dòng)狀態(tài)、戰(zhàn)場環(huán)境特點(diǎn)、作戰(zhàn)任務(wù)需要等已有信息為決策依據(jù),對(duì)下一步或多步?jīng)Q策時(shí)長內(nèi)各備選調(diào)度方案所產(chǎn)生的跟蹤精度和使用代價(jià)進(jìn)行預(yù)測,以綜合效能達(dá)到最優(yōu)為目標(biāo),結(jié)合約束條件建立目標(biāo)函數(shù),選取適當(dāng)?shù)膶?yōu)算法求解得到k+1時(shí)刻的最優(yōu)調(diào)度方案,執(zhí)行后測量得到新的目標(biāo)信息,完成對(duì)目標(biāo)狀態(tài)的更新。

2.1 相關(guān)規(guī)則

1)一定的跟蹤精度。跟蹤精度直接反映了傳感器的工作性能,但在實(shí)際應(yīng)用中,越高的跟蹤精度意味著更多的數(shù)據(jù)和更大的能量消耗,所以跟蹤精度通常只要求滿足任務(wù)需求即可,常用的衡量指標(biāo)有協(xié)方差矩陣的跡、互信息量、后驗(yàn)克拉美羅下界等[6-7]。

2)適當(dāng)?shù)氖褂么鷥r(jià)。使用代價(jià)指傳感器在使用或調(diào)度中所產(chǎn)生的損耗,包括能量損耗、輻射代價(jià)以及響應(yīng)延遲等,能量損耗主要存在于無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)中,由于傳感器能量有限,導(dǎo)致在跟蹤過程中必然存在通信、探測和計(jì)算等產(chǎn)生能量消耗的問題,常用的量化模型有常數(shù)模型、路徑能耗模型[8]和自由空間傳播模型。輻射代價(jià)是指主動(dòng)傳感器在工作時(shí)向外輻射電磁波導(dǎo)致位置暴露的問題,常采用固定常數(shù)、截獲概率[9]和輻射度影響進(jìn)行量化。響應(yīng)延遲是傳感器在調(diào)度中由于頻繁切換工作模式或傳感器性能不足、通信質(zhì)量一般等導(dǎo)致調(diào)度效果達(dá)不到預(yù)期目標(biāo)的問題,通常描述為固定常數(shù)[10]。

3)較強(qiáng)的系統(tǒng)魯棒性。當(dāng)跟蹤目標(biāo)在進(jìn)行復(fù)雜機(jī)動(dòng)或針對(duì)傳感器的觀測采取干擾措施的情況下,傳感器調(diào)度必須要能夠保證穩(wěn)定的跟蹤精度以及綜合效能的有效平衡。

4)實(shí)時(shí)的數(shù)據(jù)反饋。軍事應(yīng)用中的目標(biāo)跟蹤對(duì)觀測數(shù)據(jù)的獲取、調(diào)度方案的求解以及調(diào)度動(dòng)作的展開有嚴(yán)格的時(shí)效性要求,必須充分考慮時(shí)延問題,平衡好算法復(fù)雜度和跟蹤精度、跟蹤時(shí)效之間的矛盾。

2.2 約束條件

1)實(shí)際任務(wù)需要。主動(dòng)傳感器在考慮輻射風(fēng)險(xiǎn)的條件下開展目標(biāo)跟蹤時(shí),在已設(shè)置跟蹤精度閾值的前提下,必須以輻射代價(jià)最小或者不超過一定值為優(yōu)化目標(biāo)創(chuàng)建目標(biāo)函數(shù),求解調(diào)度方案,在確保跟蹤任務(wù)完成的同時(shí),降低傳感器輻射風(fēng)險(xiǎn)[11]。

2)傳感器性能局限。在制定目標(biāo)函數(shù)時(shí),必須充分考慮傳感器的最小可檢測信號(hào)、最大作用距離、波束寬度等基本參數(shù),確保目標(biāo)能被觀測到。

3)環(huán)境因素影響。在不同的作戰(zhàn)條件下,傳感器的工作性能不盡相同,在實(shí)際調(diào)度中,必須充分考慮地理環(huán)境等對(duì)傳感器機(jī)動(dòng)性能的影響和對(duì)探測目標(biāo)的遮蔽等因素,確保對(duì)目標(biāo)的準(zhǔn)確跟蹤。

3 傳感器調(diào)度的決策指標(biāo)

基于POMDP的理念,根據(jù)決策執(zhí)行后所帶來回報(bào)的時(shí)間尺度,可將傳感器調(diào)度劃分為短時(shí)調(diào)度和長時(shí)調(diào)度兩種。傳感器短時(shí)調(diào)度的過程可簡單描述為一個(gè)單步的最優(yōu)化決策過程,一般以單個(gè)調(diào)度動(dòng)作所產(chǎn)生的短期收益作為決策依據(jù),以傳感器對(duì)目標(biāo)的單步偵察效能(收益與代價(jià)的綜合)為優(yōu)化指標(biāo)集,構(gòu)建管理算法、建立調(diào)度模型,進(jìn)而求得最優(yōu)解。Kreucher[12]針對(duì)多目標(biāo)跟蹤問題,以單步Rényi信息增量最大化為決策依據(jù),提出一種基于信息論的傳感器短期調(diào)度方法。文獻(xiàn)[13]基于高斯混合多目標(biāo)濾波器(GM-MTF),利用巴氏距離和Rényi散度作為評(píng)價(jià)指標(biāo)函數(shù),提出了以單步最優(yōu)為控制準(zhǔn)則的傳感器控制策略。

傳感器長時(shí)調(diào)度則以一段時(shí)域內(nèi)的調(diào)度序列所產(chǎn)生的累積收益為決策依據(jù),在性能上要優(yōu)于短時(shí)調(diào)度。實(shí)際應(yīng)用中,主動(dòng)傳感器由于存在基于輻射量的跟蹤代價(jià),為有效平衡各類指標(biāo),一般在建立目標(biāo)函數(shù)時(shí)采取長時(shí)調(diào)度的方式,將其決策信息定為一段時(shí)域內(nèi)的所有時(shí)刻偵察收益和輻射代價(jià)的綜合[14-15]。針對(duì)空基預(yù)警探測系統(tǒng)特點(diǎn),唐書娟[16]采取長期調(diào)度和動(dòng)態(tài)調(diào)度相結(jié)合的分配策略,提出了一種基于任務(wù)控制思想的傳感器分配方案,降低了傳感器調(diào)度頻次。文獻(xiàn)[17]結(jié)合空天高速目標(biāo)跟蹤任務(wù),提出了多源異構(gòu)傳感器調(diào)度多目標(biāo)優(yōu)化模型和柔性果蠅算法,設(shè)計(jì)了“目標(biāo)-時(shí)間-傳感器”三維編碼方式,解決了傳感器調(diào)度時(shí)間碎片化和局部最優(yōu)的問題。

傳感器短時(shí)調(diào)度僅以一步收益為決策依據(jù),計(jì)算復(fù)雜度低,易于實(shí)現(xiàn),但調(diào)度效果往往不理想,不適用于對(duì)跟蹤精度等戰(zhàn)術(shù)指標(biāo)收益要求極高的任務(wù)。傳感器長時(shí)調(diào)度雖然在調(diào)度性能方面優(yōu)于短時(shí)調(diào)度,但隨著決策步長的增加,其可行解的數(shù)量呈現(xiàn)出指數(shù)上升的態(tài)勢,極大增加了目標(biāo)函數(shù)求解的計(jì)算復(fù)雜度,不易于實(shí)際工程實(shí)現(xiàn)。

4 傳感器調(diào)度的優(yōu)化方式

傳感器調(diào)度必須嚴(yán)格以實(shí)際任務(wù)的需要為決策依據(jù),要具備一定的跟蹤精度,能夠有效控制使用代價(jià)。但要獲得更高的跟蹤精度,勢必會(huì)產(chǎn)生更大的使用代價(jià),這就限制了調(diào)度策略的制定必須始終圍繞處理跟蹤精度與使用代價(jià)之間相互矛盾的關(guān)系展開,根據(jù)傳感器調(diào)度效果的評(píng)價(jià)內(nèi)容是跟蹤精度最大化或是使用代價(jià)最小化或是兩者平衡,可以將傳感器調(diào)度分為平衡優(yōu)化調(diào)度和約束優(yōu)化調(diào)度。

平衡優(yōu)化調(diào)度以多個(gè)指標(biāo)的平衡為優(yōu)化目標(biāo),通過權(quán)衡回報(bào)期望和使用代價(jià)的綜合效能,使得一定時(shí)域范圍內(nèi)的回報(bào)期望和使用代價(jià)達(dá)到最佳平衡的狀態(tài)。針對(duì)多傳感器數(shù)據(jù)融合中的系統(tǒng)資源消耗問題,文獻(xiàn)[18]按照平衡消耗代價(jià)的思路,提出了一種以能量消耗和信息熵增量加權(quán)值為效用的線性規(guī)劃的傳感器管理算法,有效提高了跟蹤效能。文獻(xiàn)[19]為降低空中目標(biāo)威脅評(píng)估結(jié)果不準(zhǔn)確及傳感器輻射等潛在風(fēng)險(xiǎn),基于POMPD建立傳感器調(diào)度模型,以兩種風(fēng)險(xiǎn)的加權(quán)和最小為優(yōu)化目標(biāo)建立長期目標(biāo)函數(shù),實(shí)現(xiàn)了對(duì)風(fēng)險(xiǎn)的準(zhǔn)確預(yù)測。約束優(yōu)化調(diào)度以單個(gè)指標(biāo)的最優(yōu)為優(yōu)化目標(biāo),通過單純對(duì)回報(bào)期望或者使用代價(jià)進(jìn)行優(yōu)化,充分利用有限的傳感器資源,在規(guī)定的調(diào)度時(shí)間內(nèi),實(shí)現(xiàn)最佳的單方面性能,這種調(diào)度方式一般更加適用于目標(biāo)跟蹤場景。Kaplan[20]針對(duì)分布式WSN調(diào)度問題,以目標(biāo)跟蹤精度的幾何稀釋因子為準(zhǔn)則,采取全局節(jié)點(diǎn)選擇算法,提出傳感器分配方案。針對(duì)主/被動(dòng)傳感器調(diào)度問題,文獻(xiàn)[21]以跟蹤精度為約束、以系統(tǒng)輻射代價(jià)最小為優(yōu)化目標(biāo)建立目標(biāo)函數(shù),改進(jìn)了分布式拍賣算法,有效降低了目標(biāo)跟蹤時(shí)傳感器系統(tǒng)的輻射風(fēng)險(xiǎn)。

總的來說,相比約束優(yōu)化調(diào)度,平衡優(yōu)化調(diào)度需要考慮的因素更多,模型設(shè)計(jì)和運(yùn)算求解最優(yōu)調(diào)度方案更加復(fù)雜,為滿足時(shí)效性的要求,一般需要借助尋優(yōu)求解算法獲得最優(yōu)調(diào)度方案。

5 傳感器調(diào)度的尋優(yōu)算法

實(shí)際應(yīng)用中,傳感器調(diào)度為提高跟蹤精度、降低使用代價(jià),采取了一系列技術(shù)及算法,導(dǎo)致普遍存在求解過程復(fù)雜和計(jì)算量巨大的問題。如何在最短的時(shí)間內(nèi)正確選擇各時(shí)刻的調(diào)度方案及控制動(dòng)作,以達(dá)到滿足調(diào)度策略或任務(wù)要求的最優(yōu)狀態(tài),必須依賴于各類尋優(yōu)算法。

5.1 動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃方法(Dynamic Programming Method,DPM)主要用于求解多階段決策過程最優(yōu)化問題,其應(yīng)用貝爾曼原理,將原本的多階段過程轉(zhuǎn)換成較為簡單但相互之間又有密切關(guān)聯(lián)的子問題,并根據(jù)各階段遞推關(guān)系進(jìn)行快速求解,能夠有效實(shí)現(xiàn)當(dāng)前利益和未來效益的綜合考量[22],一般適用于平衡優(yōu)化問題且調(diào)度效果與基策略選取相關(guān)。運(yùn)用該方法求解決策的前提在于問題是否滿足無后效性原則,即未來狀態(tài)與歷史狀態(tài)無關(guān),只與當(dāng)前狀態(tài)有關(guān)。在傳感器調(diào)度中,下一時(shí)刻調(diào)度動(dòng)作的產(chǎn)生,僅由當(dāng)前時(shí)刻傳感器的觀測值決定,滿足無后效性原則,但由于節(jié)點(diǎn)狀態(tài)和路徑代價(jià)取決于歷史調(diào)度序列,導(dǎo)致了經(jīng)典動(dòng)態(tài)規(guī)劃方法的應(yīng)用效果并不理想,基于此,Bertsekas[23]提出了rollout算法,通過實(shí)時(shí)計(jì)算仿真Q值來獲得次優(yōu)傳感器調(diào)度序列;Cheng[24]則使用基于樹的結(jié)構(gòu)作為調(diào)度算法輸入,區(qū)分樹內(nèi)、樹外進(jìn)行沖突處理,提出了一種WSN最短路徑算法。

5.2 智能優(yōu)化算法

智能優(yōu)化算法(Intelligent Optimization Algorithm,IOA)主要包括遺傳算法、蟻群算法、人工蜂群算法、布谷鳥算法、模擬退火算法等一系列基于生物學(xué)、物理學(xué)原理的算法。此類算法實(shí)現(xiàn)了復(fù)雜非線性問題次優(yōu)解的快速求取,具有較強(qiáng)的搜索能力、較優(yōu)的適應(yīng)性和較好的穩(wěn)健性,且計(jì)算量不隨傳感器數(shù)目的增加而劇烈變化,在傳感器管理中常用于求解多傳感器目標(biāo)分配問題,經(jīng)過合理的迭代能夠接近最優(yōu)解。根據(jù)驗(yàn)證[25],當(dāng)決策時(shí)長和傳感器數(shù)目較大時(shí),智能優(yōu)化算法容易陷入局部最優(yōu),導(dǎo)致搜索性能降低。

1)遺傳算法(Genetic Algorithm,GA)是對(duì)生物基因遺傳和進(jìn)化原理的計(jì)算機(jī)仿真應(yīng)用,包含編碼和解碼兩個(gè)過程,在求解計(jì)算中,首先從包含若干已編碼個(gè)體的初始種群開始,按照適者生存的原理,以適應(yīng)度大小為依據(jù)篩選個(gè)體進(jìn)行交叉和變異,產(chǎn)生新一代種群,實(shí)現(xiàn)近似解的逐代優(yōu)化,并依次類推,最終獲得的末代種群解碼后即為近似最優(yōu)解。由于遺傳算法是在搜索空間對(duì)編碼集進(jìn)行多點(diǎn)求解,能夠有效避免限制條件的約束,便于復(fù)雜問題的求解,同時(shí)也方便代入已有的調(diào)度模型,擴(kuò)展性較強(qiáng)。Milton L.Cone[26]針對(duì)傳感器調(diào)度技術(shù)選擇問題,建立了一套評(píng)估準(zhǔn)則,首次對(duì)遺傳算法應(yīng)用于調(diào)度方案求解的實(shí)際效果進(jìn)行評(píng)價(jià),并提出了相關(guān)修改意見。為解決遺傳算法進(jìn)化緩慢、易早熟,局部尋優(yōu)能力差等問題,文獻(xiàn)[27]基于廣義鄰域搜索算法的統(tǒng)一結(jié)構(gòu),將遺傳算法和模擬退火算法有效結(jié)合,構(gòu)造遺傳模擬退火算法(GASA),實(shí)現(xiàn)優(yōu)勢互補(bǔ),在滿足傳感器調(diào)度實(shí)時(shí)性要求的同時(shí),提高了算法的尋優(yōu)特性。文獻(xiàn)[28]以WSN節(jié)點(diǎn)調(diào)度問題為研究對(duì)象,基于適應(yīng)度比例的選擇,采取優(yōu)化的輪盤賭方法篩選適應(yīng)度較高的個(gè)體進(jìn)行交叉變異,更加符合“適者生存”的原則。

2)人工蜂群算法(Artificial Bee Colony,ABC),由Karaboga[29]于2005年首次提出,其將當(dāng)前問題的潛在解用蜜源位置來表示,通過模擬蜜蜂采蜜當(dāng)中引領(lǐng)蜂對(duì)蜜源的搜索,引領(lǐng)蜂對(duì)蜜源信息的共享,跟隨蜂以相同概率對(duì)蜜源的搜索,引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉浜笤谙鄳?yīng)空間內(nèi)進(jìn)行的隨機(jī)搜索等一系列操作,來解決科研和生活中的多維多模優(yōu)化問題,在目標(biāo)跟蹤、數(shù)據(jù)收集、工程實(shí)踐等多個(gè)領(lǐng)域得到了廣泛應(yīng)用,具有求解操作簡便、控制變量少、方法易于實(shí)現(xiàn)等特點(diǎn),存在的不足是容易陷入局部最優(yōu)。為進(jìn)一步提高ABC的尋優(yōu)性能,Karaboga[30]于2014年對(duì)該算法進(jìn)行了修改,通過改進(jìn)新蜜源搜索公式vij=xij+φij(xij-xkj),找到當(dāng)前開采蜜源附近(假定為半徑r的圓)最好的蜜源進(jìn)行開采,提出了快速人工蜂群算法(qABC);文獻(xiàn)[31]則在新蜜源搜索公式中引入振動(dòng)頻率M和振動(dòng)幅度S,將新蜜源搜索維度由1調(diào)整為M,將隨機(jī)數(shù)φij的取值范圍由[-1,+1]調(diào)整為[-S,+S],有效提高了收斂速度;文獻(xiàn)[32]通過采取雙向輪盤賭的方式選擇引領(lǐng)蜂,推動(dòng)種群朝著極大、極小兩個(gè)方向進(jìn)化,保證了種群多樣性的延續(xù),改善了ABC的尋優(yōu)能力和計(jì)算速度。

5.3 決策樹搜索算法

決策樹(Decision Tree,DT)是一種樹狀結(jié)構(gòu)的分類算法,主要用于處理、求解多階段和多種可能性的決策問題,進(jìn)而獲取最優(yōu)方案。在實(shí)際運(yùn)算中,主要根據(jù)樹節(jié)點(diǎn)上訓(xùn)練數(shù)據(jù)的最優(yōu)特征進(jìn)行劃分,運(yùn)用概率方法計(jì)算各方案損益值,并按照決策原則進(jìn)行優(yōu)選,最優(yōu)特征選擇的度量指標(biāo)有信息增益、信息增益比和基尼指數(shù)等。決策樹搜索算法被廣泛運(yùn)用于人工智能和運(yùn)籌學(xué)領(lǐng)域,例如單路徑尋優(yōu)問題、約束滿足問題和車輛路徑問題。在傳感器調(diào)度應(yīng)用中,一般先將調(diào)度問題構(gòu)建成決策樹,然后采用合適的搜索技術(shù)進(jìn)行求解。

圖3 決策樹示意圖

1)窮舉搜索法(Exhaustive Search Method,ESM)是進(jìn)行決策樹搜索的常用方法,在求取最優(yōu)方案時(shí),從樹的根節(jié)點(diǎn)出發(fā)至最底層節(jié)點(diǎn),對(duì)初始狀態(tài)到目標(biāo)狀態(tài)的每一種可能狀態(tài)都進(jìn)行搜索,不進(jìn)行剪支、不作取舍,可以視為一種無啟發(fā)信息的盲目搜索,主要包括標(biāo)準(zhǔn)代價(jià)搜索(Uniform Cost Search,UCS)、寬度優(yōu)先搜索(Breadth First Search,BFS)和深度優(yōu)先搜索(Depth First Search,DFS),由于UCS算法在打開節(jié)點(diǎn)時(shí)不考慮其所在深度,優(yōu)先打開代價(jià)最小的節(jié)點(diǎn),故其節(jié)點(diǎn)打開比最低。窮舉搜索法的最主要特點(diǎn)是求解過程簡單,但計(jì)算量大,處理時(shí)間長,難以滿足傳感器調(diào)度實(shí)時(shí)性的要求。

2)基于閾值的方法(Threshold Based Method,TBM),為降低傳感器調(diào)度方案的求解計(jì)算復(fù)雜度,Huber M F引入分支剔除的思想[33],設(shè)置信息增量閾值參數(shù)?(?≥1),將某一深度H上達(dá)不到?值的傳感器組合序列排除在最優(yōu)調(diào)度序列之外,并依此對(duì)決策樹分支進(jìn)行裁剪,在不丟失最優(yōu)傳感器序列的前提下,有效減少了搜索時(shí)間。文獻(xiàn)[34]將長時(shí)調(diào)度增量模型描述為信息決策樹,并采取基于閾值的分支剔除技術(shù)搜索最優(yōu)解,有效降低了長時(shí)信息增量最優(yōu)搜索的運(yùn)算量。隨著?值的增大,裁剪的條件逐漸降低,進(jìn)行決策樹搜索時(shí)會(huì)有更多的分支被刪除,進(jìn)而加快搜索速度,但同時(shí)也會(huì)導(dǎo)致最優(yōu)解和部分次優(yōu)解所在分支被剔除,影響調(diào)度性能。

3)分支定界法(Branch and Bound Method,BBM)是一種構(gòu)造性的搜索算法,主要用于求解組合最優(yōu)問題,通過逐層剖析最優(yōu)解的各項(xiàng)可行域,證明解的最優(yōu)性,原則是進(jìn)行反復(fù)分支,每次分支都對(duì)子集合計(jì)算最優(yōu)解的界,通過逐代分支搜索,直至子集合僅含有一個(gè)解時(shí)為止。其中,剖析并分解可行域的過程稱為分支過程,在可行域中選擇目標(biāo)函數(shù)上下界的過程稱為定界過程[35]。針對(duì)相控陣?yán)走_(dá)調(diào)度問題,文獻(xiàn)[36]提出了一種基于分支定界法的傳感器調(diào)度算法,通過對(duì)已有調(diào)度結(jié)果采取“分支”、“刪減”等操作,實(shí)現(xiàn)對(duì)空間范圍的有效控制。文獻(xiàn)[37]按照節(jié)點(diǎn)間互相優(yōu)化定位的思路,通過精確裁剪待定位節(jié)點(diǎn)的蒙特卡洛盒,增加節(jié)點(diǎn)的粒子濾波條件,實(shí)現(xiàn)了移動(dòng)WSN節(jié)點(diǎn)的精確定位。文獻(xiàn)[38]根據(jù)先見優(yōu)化的思想,借助精度收益及輻射代價(jià)將調(diào)度問題轉(zhuǎn)化成決策樹問題,并采用分枝定界方法求解,使綜合跟蹤效能達(dá)到了最佳平衡。

6 結(jié)束語

隨著數(shù)據(jù)融合技術(shù)的不斷發(fā)展,以及應(yīng)用環(huán)境實(shí)際調(diào)度模型等的逐步完善,基于能量消耗、網(wǎng)絡(luò)通信、體系壽命、有效覆蓋等多指標(biāo)的傳感器調(diào)度逐漸成為研究的熱點(diǎn)。結(jié)合當(dāng)前國內(nèi)外參考文獻(xiàn),如何科學(xué)設(shè)計(jì)傳感器工作和調(diào)度模型,優(yōu)化改進(jìn)目標(biāo)函數(shù)、跟蹤算法、尋優(yōu)算法,從而克服實(shí)際應(yīng)用場景對(duì)傳感器系統(tǒng)感知、通信、機(jī)動(dòng)能力的削弱,降低環(huán)境雜波和電磁干擾對(duì)跟蹤精度的影響,平衡各類使用代價(jià),高效完成目標(biāo)檢測、識(shí)別、跟蹤和威脅評(píng)估及火力打擊等各項(xiàng)任務(wù),還需要深一步的研究。