基于改進(jìn)布谷鳥搜索算法的多傳感器調(diào)度方法*

魏文鳳，劉昌云，田桂林，岳韶華

（1.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051；2.空軍工程大學(xué)研究生院，西安 710051）

0 引言

20 世紀(jì)以來，隨著通信技術(shù)的飛躍發(fā)展，現(xiàn)代戰(zhàn)爭正在逐步信息化，多傳感器數(shù)據(jù)融合技在獲取探測信息和數(shù)據(jù)采集方面有著廣泛的應(yīng)用。為了進(jìn)行最優(yōu)數(shù)據(jù)獲取，對(duì)有限的傳感器資源進(jìn)行合理的分配利用是非常重要的。多傳感器資源調(diào)度是依據(jù)一定的優(yōu)化準(zhǔn)則，在確定的時(shí)間區(qū)間內(nèi)，為傳感器網(wǎng)絡(luò)中的各傳感器資源安排跟蹤探測任務(wù)，以滿足對(duì)多目標(biāo)的跟蹤要求，從而達(dá)到某項(xiàng)或某些指標(biāo)的綜合最優(yōu)［1-2］。傳感器調(diào)度可以改善多傳感器系統(tǒng)的系統(tǒng)性能，提高其運(yùn)行速率，因此，合理的傳感器調(diào)度是機(jī)動(dòng)目標(biāo)跟蹤領(lǐng)域中的研究熱點(diǎn)。

本文是在多傳感器多目標(biāo)跟蹤任務(wù)下進(jìn)行研究，在該領(lǐng)域多數(shù)研究有在給定傳感器序列下對(duì)所有目標(biāo)跟蹤精度的計(jì)算方法，如Chakravarty［3］提出的粒子濾波法；Preeti A［4］提出了決策樹方法；喬成霖［5］等提出建立基于部分馬爾可夫決策過程（POMDP）的目標(biāo)跟蹤與輻射控制模型，以隨機(jī)分布粒子計(jì)算新生目標(biāo)檢測概率，以后驗(yàn)克拉美-羅下界（PCRLB）預(yù)測長時(shí)跟蹤精度，利用基于貪婪搜索的分支定界算法求解最優(yōu)調(diào)度序列；李建平［6］用跟蹤目標(biāo)的重要程度之和作為目標(biāo)函數(shù)，建立了0-1規(guī)劃的數(shù)學(xué)模型，并利用割平面方法求解得出最優(yōu)調(diào)度策略。除此之外，近年來新興的智能算法也開始被用于傳感器調(diào)度的問題，如任俊亮［7］、劉建業(yè)［8］以及胡崇海［9］等分別采用了自適應(yīng)粒子群算法、遺傳模擬退火算法，以及動(dòng)態(tài)連續(xù)蟻群算法來解決不同背景下的傳感器調(diào)度問題。

多傳感器多目標(biāo)跟蹤任務(wù)下的傳感器是一個(gè)復(fù)雜的組合優(yōu)化問題，目前，用來求解大規(guī)模優(yōu)化問題時(shí)常用的方法有群智能算法，比如，遺傳算法、模擬退火算法、蟻群算法等。這些算法都在可允許的時(shí)間范圍內(nèi)得出近似最優(yōu)解。而布谷鳥算法［10-11］（Cuckoo Search，CS）是一種模仿布谷鳥行為的仿生算法，具有算法流程簡單、計(jì)算速度快、參數(shù)少等特點(diǎn)，因而得到了廣泛應(yīng)用。但是布谷鳥搜索算法依賴隨機(jī)步長，故存在收斂速度慢、精度較低的問題，且比較適用于求解連續(xù)型優(yōu)化問題，而多傳感器調(diào)度屬于離散型的組合優(yōu)化問題。因而，為提高多傳感器調(diào)度算法的收斂速度和精度，在CS 算法過程中引入差分進(jìn)化算法，提高布谷鳥算法種群多樣性，以提高其收斂時(shí)間和精度。仿真結(jié)果表明，利用DE-CS 算法求解目標(biāo)跟蹤背景下的多傳感器調(diào)度模型，具有較快的收斂速度和較高的精度。

1 多傳感器多目標(biāo)跟蹤下的傳感器調(diào)度模型

在多傳感器多跟蹤目標(biāo)任務(wù)背景下，傳感器調(diào)度需要綜合考慮多方面的指標(biāo)要求。首先，從任務(wù)完成方面來講，要求盡可能提高跟蹤任務(wù)的跟蹤精度，此項(xiàng)指標(biāo)可以從跟蹤模型中傳感器濾波協(xié)方差、傳感器濾波估計(jì)狀態(tài)與目標(biāo)實(shí)際狀態(tài)之間的位置均方誤差反映得出；其次，從系統(tǒng)角度來講，要求多傳感器系統(tǒng)盡可能多地完成任務(wù)；第三，由于傳感器節(jié)點(diǎn)的可利用資源是有限的，如何最有效地利用資源，盡可能延長傳感器的生命周期，也是傳感器調(diào)度過程中全都需要考慮的問題。

1.1 決策變量

1.2 調(diào)度指標(biāo)及目標(biāo)函數(shù)

1）跟蹤精度Cα

針對(duì)單目標(biāo)t，pt（k|k）是在時(shí)刻k 對(duì)目標(biāo)狀態(tài)的估計(jì)誤差協(xié)方差矩陣，如果傳感器調(diào)度結(jié)束的時(shí)刻為k，根據(jù)目標(biāo)跟蹤模型計(jì)算得到pt（k|k），pt（k|k）也就是在該調(diào)度序列下對(duì)跟蹤任務(wù)t 的跟蹤誤差矩陣。跟蹤精度需要綜合考慮所有的目標(biāo)跟蹤精度，李國輝［12］等提出，利用pt（k|k）的跡（Trace）計(jì)算任務(wù)t 的跟蹤精度dt，如式（1）。

設(shè)M 為要跟蹤的目標(biāo)總數(shù)量，Cα是所有跟蹤目標(biāo)的精度均值，如式（2）。

2）任務(wù)完成率指標(biāo)Cβ

在多目標(biāo)跟蹤場景下，有限的傳感器資源可能無法滿足所有目標(biāo)的跟蹤需求，這就需要區(qū)分目標(biāo)的重要程度，以便對(duì)重點(diǎn)目標(biāo)優(yōu)先跟蹤。也就是說，每一個(gè)觀測目標(biāo)都有各自的優(yōu)先級(jí)，目標(biāo)的優(yōu)先級(jí)取決于目標(biāo)的類型、速度、飛行距離、飛行航向角以及威脅程度等因素，每個(gè)目標(biāo)的優(yōu)先級(jí)是不同的。因?yàn)閭鞲衅鞲櫽^測的能力有限，所以在調(diào)度時(shí)為了能夠更有效地完成任務(wù)，具有較高優(yōu)先級(jí)的觀測目標(biāo)會(huì)比相對(duì)較低的觀測目標(biāo)有更大概率被合適的傳感器資源跟蹤。故本指標(biāo)除了能夠反應(yīng)目標(biāo)被跟蹤的數(shù)量，也可以反映出在本問題中各目標(biāo)的優(yōu)先級(jí)。

設(shè)目標(biāo)t 的優(yōu)先級(jí)為pt，Cβ可以用已完成跟蹤目標(biāo)的優(yōu)先級(jí)之和與所有跟蹤目標(biāo)的優(yōu)先級(jí)之和來計(jì)算得出，如式（3）。

其中，Xt是二進(jìn)制變量，表示任務(wù)t 是否被調(diào)度完成，N 是傳感器總數(shù)量。

3）傳感器資源消耗Cμ

傳感器資源消耗是指傳感器對(duì)目標(biāo)進(jìn)行探測時(shí)消耗的能量，傳感器的能量是有限的，要在傳感器資源范圍內(nèi)最大程度地進(jìn)行探測。在此定義傳感器資源能耗為Cμ，計(jì)算方法參考文獻(xiàn)［13］，因?yàn)楸疚脑O(shè)定任務(wù)約束（由1.3 中提出），且本文目標(biāo)函數(shù)計(jì)算最大值，故改進(jìn)后計(jì)算方法如式（4）。

1.3 約束條件

本文所研究的傳感器調(diào)度問題在幾個(gè)方面存在約束：

1）觀測時(shí)間約束

2 基于差分進(jìn)化的改進(jìn)布谷鳥算法

布谷鳥算法是Xin-she Yang 和Suash Deb 提出的一種模仿布谷鳥“巢寄生”行為的仿生算法，該算法流程簡單、計(jì)算速度快，參數(shù)少。布谷鳥搜索算法近些年來得到頗多關(guān)注［10-11］，因?yàn)樗粌H能夠在本地搜索，還可以通過Levy 飛行來全球游走，從而進(jìn)行全球搜索，故而收斂達(dá)到全局最優(yōu)。

2.1 標(biāo)準(zhǔn)布谷鳥搜索算法

2.1.1 Levy 飛行

Levy 飛行是一種流行的隨機(jī)游走，通過該隨機(jī)游走可以定義動(dòng)物或者昆蟲在食物搜索空間內(nèi)的運(yùn)動(dòng)。在Levy 飛行中，步長是由具有一定概率分布的分布步長定義的，即重尾概率分布，步長的方向是各向同性且隨機(jī)的。布谷鳥算法在考慮基于Levy 飛行的隨機(jī)游走時(shí)的效果比在單純隨機(jī)游走時(shí)更好。在二維平面里模擬Levy 飛行，如圖1所示。

圖1 Levy 飛行模擬圖

2.1.2 布谷鳥算法的前提

布谷鳥算法以下列3 種假設(shè)為前提：

1）每只布谷鳥每次只孵化一個(gè)蛋，然后將它放在隨機(jī)選擇的巢中；

2）具有較高品質(zhì)的巢被視為最佳孵化巢穴，并將延續(xù)到下一代；

3）可選用的宿主鳥巢數(shù)量是一定的，而布谷鳥的卵有可能被宿主發(fā)現(xiàn)而導(dǎo)致孵化失敗。

基于以上前提，鳥巢位置更新公式為：

2.2 布谷鳥搜索算法的改進(jìn)

標(biāo)準(zhǔn)的布谷鳥搜索算法依賴隨機(jī)步長，故有收斂速度慢的現(xiàn)象，多位學(xué)者對(duì)該算法利用不同方法進(jìn)行改進(jìn)［14-16］。本文借鑒差分進(jìn)化算法對(duì)CS 算法進(jìn)行改進(jìn)，以提高其收斂速度和精度，并將其離散化，從而適合解決NP-hard 問題。

差分進(jìn)化算法［17］是基于種群差異、優(yōu)勝劣汰的進(jìn)化算法。該算法通過反復(fù)迭代，保留那些適合環(huán)境的個(gè)體，淘汰適應(yīng)性弱的個(gè)體，是一種被廣泛應(yīng)用的全局優(yōu)化算法。在標(biāo)準(zhǔn)的布谷鳥搜索算法中，是初始化種群后的鳥巢位置，對(duì)進(jìn)行差分進(jìn)化操作，此操作后的鳥巢個(gè)體可以部分甚至全部繼承父輩優(yōu)秀基因，從而使其像種群中的最優(yōu)位置迅速靠攏。差分進(jìn)化之后再回到標(biāo)準(zhǔn)CS 算法，利用Levy飛行對(duì)位置進(jìn)行更行，從而增加了種群多樣性，避免陷入局部最優(yōu)，提高了收斂速度和精度。

具體操作為：

1）變異。變異操作是差分進(jìn)化算法的關(guān)鍵，此操作可以獲得多個(gè)個(gè)體的遺傳信息。根據(jù)下式獲得變異個(gè)體：

改進(jìn)的布谷鳥搜索算法，稱為DE-CS 算法，其具體步驟如下：

步驟1：初始化種群，設(shè)置初始參數(shù)，隨機(jī)產(chǎn)生N 個(gè)鳥巢的位置。

步驟2：設(shè)置終止條件，判斷是否有無鳥巢位置滿足該條件，若停止，輸出最優(yōu)值，否則，繼續(xù)步驟3。

步驟3：對(duì)初始化鳥巢進(jìn)行評(píng)估并保留較好的位置，按照式（9）通過Levy 飛行隨機(jī)搜索下一代鳥巢的位置。

步驟4：按照發(fā)現(xiàn)概率Pa對(duì)鳥巢進(jìn)行丟棄操作。

步驟5：根據(jù)式（11）～ 式（13）進(jìn)行差分進(jìn)化操作，并根據(jù)式（5）計(jì)算目標(biāo)函數(shù)值。然后比較新的鳥巢和之前鳥巢的適應(yīng)值，保留較優(yōu)的一個(gè)。

步驟6：重復(fù)進(jìn)行步驟3～ 步驟5，判斷是否滿足終止條件，若滿足，則輸出最優(yōu)值；否則，繼續(xù)進(jìn)行搜索鳥巢的操作。

3 基于DE-CS 算法的傳感器調(diào)度仿真流程

根據(jù)DE-CS 算法進(jìn)行傳感器調(diào)度的仿真流程如圖2 所示。

圖2 基于DE-CS 算法的多傳感器調(diào)度仿真流程圖

4 仿真分析

4.1 仿真條件

假設(shè)作戰(zhàn)區(qū)域是范圍為1 000 km×1 000 km 的一塊正方形區(qū)域，其坐標(biāo)范圍為從（0，0）至（1 000，1 000），該區(qū)域內(nèi)設(shè)置5 個(gè)探測傳感器。假設(shè)在一段時(shí)間0 s～1 000 s 內(nèi)，該區(qū)域會(huì)出現(xiàn)5 個(gè)敵對(duì)來襲目標(biāo)，其觀測優(yōu)先度根據(jù)其型號(hào)信息可得。為簡化運(yùn)算，這些目標(biāo)均作直線運(yùn)動(dòng)，但其初始位置和方向都是不一樣的。其運(yùn)動(dòng)軌跡如下頁圖3 所示。

圖3 來襲目標(biāo)運(yùn)動(dòng)軌跡

仿真實(shí)驗(yàn)中假定的傳感器和目標(biāo)的信息分別如表1～表2 所示。

表1 傳感器信息

表2 目標(biāo)信息

將一次調(diào)度周期按照時(shí)間劃分的任務(wù)分解方法分成10 個(gè)片段，最小觀測時(shí)間為20 s：［0，98］，［98，182］，［182，201］，［201，350］，［350，405］，［405，531］，［531，550］，［550，720］，［720，840］，［840，1 000］。假設(shè)各傳感器在可探測時(shí)間內(nèi)對(duì)任意目標(biāo)均可進(jìn)行探測，則傳感器與目標(biāo)之間一共有5×5×10=250 個(gè)可探測關(guān)系。調(diào)度目的就是在這段時(shí)間內(nèi)將這些目標(biāo)分配給傳感器進(jìn)行探測跟蹤。

4.2 仿真結(jié)果與分析

設(shè)定布谷鳥搜索算法參數(shù)：最大迭代次數(shù)為100，發(fā)現(xiàn)概率Pa為0.25，交叉概率Pc為0.6。按照本文改進(jìn)的布谷鳥算法，編制程序，進(jìn)行仿真。傳感器調(diào)度結(jié)果如圖4 所示。

圖4 傳感器-目標(biāo)調(diào)度結(jié)果

為了驗(yàn)證改進(jìn)后的布谷鳥搜索算法是否具有有效性，將DE-CS 算法與CS 算法分別從性能、收斂斂速度收斂性和算法時(shí)間4 個(gè)方面進(jìn)行仿真分析。

4.2.1 性能分析

在參數(shù)γα=0.3、γβ=0.5、γμ=0.2，迭代次數(shù)為100的條件下，分別對(duì)兩種算法做10 組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如下頁表3 所示。

由表3 中可得：采用DE-CS 算法所求得的最優(yōu)適應(yīng)度值高于基礎(chǔ)CS 算法所求得的最優(yōu)適應(yīng)度值，計(jì)算得到DE-CS 算法平均值為0.640 4，CS 算法為0.637 1。這是因?yàn)镈E-CS 算法在差分進(jìn)化操作之后能獲得更多遺傳信息，生成新的個(gè)體，在迭代中能夠增加種群的多樣性，從而避免陷入局部最優(yōu)，因此，其具有更好的尋優(yōu)能力，更高的求解性能。

表3 算法最優(yōu)適應(yīng)度比較

4.2.2 收斂速度

分別設(shè)置迭代次數(shù)為10 次、20 次、50 次、100 次記錄達(dá)到最優(yōu)時(shí)迭代次數(shù)。

1）迭代次數(shù)為10 次

迭代次數(shù)為10 次的CS 算法與DE-CS 算法仿真結(jié)果如圖5 所示。

圖5 迭代次數(shù)10 次對(duì)比

2）迭代次數(shù)為20 次

迭代次數(shù)為20 次的CS 算法與DE-CS 算法仿真結(jié)果如圖6 所示。

圖6 迭代次數(shù)20 次對(duì)比

3）迭代次數(shù)為50 次

迭代次數(shù)為50 次的CS 算法與DE-CS 算法仿真結(jié)果如下頁圖7 所示。

圖7 迭代次數(shù)50 次對(duì)比

4）迭代次數(shù)為100 次

迭代次數(shù)為100 次的CS 算法與DE-CS 算法仿真結(jié)果如圖8 所示。

在圖5～圖8 四組仿真實(shí)驗(yàn)圖中，橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)為目標(biāo)函數(shù)值，標(biāo)注的點(diǎn)為達(dá)到收斂時(shí)的迭代次數(shù)以及目標(biāo)函數(shù)值，其中，每組實(shí)驗(yàn)的（b）為不同迭代次數(shù)下DE-CS 算法的仿真結(jié)果，（a）為不同迭代次數(shù)下標(biāo)準(zhǔn)布谷鳥算法的仿真結(jié)果。從4 組仿真結(jié)果可得：在相同的條件下（如設(shè)置迭代次數(shù)為100 次時(shí)，DE-CS 算法在第81 次迭代時(shí)達(dá)到收斂，目標(biāo)函數(shù)值為0.698；基礎(chǔ)CS 算法在第91 次迭代時(shí)達(dá)到收斂，目標(biāo)函數(shù)值為0.681 9），改進(jìn)后的CS 算法相比于CS 算法除了有更高的適應(yīng)度值外，且能更快地收斂到最優(yōu)。

圖8 迭代次數(shù)100 次對(duì)比

4.2.3 收斂性

圖9～圖10 分別為DE-CS 算法和CS 算法的收斂性曲線，兩圖相比除了可以看出改進(jìn)后的DE-CS 算法的最佳適應(yīng)度函數(shù)值高于CS 算法外，收斂性也更好。

圖9 DE-CS 算法收斂圖

圖10 CS 算法收斂圖

4.2.4 算法時(shí)間

DE-CS 算法和CS 算法在迭代50 次的條件下分別進(jìn)行10 次實(shí)驗(yàn)，平均耗時(shí)情況如表4 所示。

表4 算法時(shí)間性能對(duì)比

從表4 中可知：DE-CS 算法所耗時(shí)長略高于改進(jìn)之前。兩種算法的耗時(shí)差距體現(xiàn)在解空間的更新上，因?yàn)镈E-CS 算法添加了交叉、變異操作，但是這些計(jì)算采用并行計(jì)算，所以兩種算法的時(shí)間性能相差在可接受范圍內(nèi)。

綜上所述，從算法性能、收斂速度、收斂性方面進(jìn)行對(duì)比，在相同的實(shí)驗(yàn)條件下，DE-CS 算法比CS算法有著更好的性能。

5 結(jié)論

傳感器調(diào)度問題是傳感器網(wǎng)絡(luò)管理中的一個(gè)重要研究方向，本文針對(duì)戰(zhàn)場環(huán)境下多傳感器資源調(diào)度問題的特點(diǎn)，建立了基于跟蹤精度、目標(biāo)優(yōu)先級(jí)以及傳感器資源消耗率為指標(biāo)的多傳感器調(diào)度模型，針對(duì)該問題進(jìn)行任務(wù)分解，根據(jù)調(diào)度周期進(jìn)行分割，構(gòu)建目標(biāo)- 時(shí)間- 傳感器的模型求解流程，并將改進(jìn)的CS 算法用于求解該模型，給出了仿真流程以及仿真實(shí)例，驗(yàn)證了本文提出的改進(jìn)算法適用于多傳感器多目標(biāo)的調(diào)度問題。仿真實(shí)驗(yàn)表明，改進(jìn)后的布谷鳥算法具有更快的收斂速度、更高的求解性能，對(duì)于多傳感器多目標(biāo)的調(diào)度問題求解具有更高的有效性。