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

（1.空軍工程大學防空反導學院，西安 710051；2.空軍工程大學研究生院，西安 710051）

0 引言

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

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

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

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

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

1.1 決策變量

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

1）跟蹤精度Cα

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

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

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

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

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

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

3）傳感器資源消耗Cμ

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

1.3 約束條件

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

1）觀測時間約束

2 基于差分進化的改進布谷鳥算法

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

2.1 標準布谷鳥搜索算法

2.1.1 Levy 飛行

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

圖1 Levy 飛行模擬圖

2.1.2 布谷鳥算法的前提

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

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

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

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

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

2.2 布谷鳥搜索算法的改進

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

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

具體操作為：

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

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

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

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

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

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

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

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

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

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

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

4 仿真分析

4.1 仿真條件

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

圖3 來襲目標運動軌跡

仿真實驗中假定的傳感器和目標的信息分別如表1～表2 所示。

表1 傳感器信息

表2 目標信息

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

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

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

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

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

4.2.1 性能分析

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

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

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

4.2.2 收斂速度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.3 收斂性

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

圖9 DE-CS 算法收斂圖

圖10 CS 算法收斂圖

4.2.4 算法時間

DE-CS 算法和CS 算法在迭代50 次的條件下分別進行10 次實驗，平均耗時情況如表4 所示。

表4 算法時間性能對比

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

綜上所述，從算法性能、收斂速度、收斂性方面進行對比，在相同的實驗條件下，DE-CS 算法比CS算法有著更好的性能。

5 結(jié)論

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