基于自適應(yīng)二進(jìn)制灰狼算法的節(jié)點(diǎn)協(xié)同跟蹤

王 珂，江瀟瀟，王永琦，江玉潔

（1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，松江 201620；2.上海第二工業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，上海 201209）

0 引言

近年來(lái)，隨著相關(guān)技術(shù)的發(fā)展，傳感器的生產(chǎn)和部署成本逐漸降低，越來(lái)越多的學(xué)者聚焦于大規(guī)模傳感器網(wǎng)絡(luò)的理論和實(shí)踐研究[1,2]，目標(biāo)跟蹤就是其中一個(gè)重要的研究方向[3]。在大規(guī)模傳感器網(wǎng)絡(luò)中進(jìn)行目標(biāo)跟蹤時(shí)，部署的傳感器數(shù)量通常大于進(jìn)行數(shù)據(jù)處理時(shí)需要的節(jié)點(diǎn)數(shù)量，另外，全部節(jié)點(diǎn)之間數(shù)據(jù)傳輸也會(huì)加快電池能量消耗，降低網(wǎng)絡(luò)壽命[4]。為了解決上述問(wèn)題，需要在保證跟蹤精度的情況下，在特定的時(shí)間間隔內(nèi)選擇一組最優(yōu)的傳感器節(jié)點(diǎn)參與跟蹤。

近年來(lái)，眾多學(xué)者針對(duì)傳感器節(jié)點(diǎn)選擇問(wèn)題提出很多解決方法和模型，如基于信息論的方法，即熵[5]，相對(duì)熵[6]，以及瑞利散度[7]等，基于信息論的方法一般是通過(guò)最大化信息增益來(lái)選擇傳感器節(jié)點(diǎn)，這種方法存在的問(wèn)題是其計(jì)算復(fù)雜度太高，尤其是在每個(gè)時(shí)間節(jié)點(diǎn)激活的傳感器數(shù)目較大時(shí)。還有一種方法是基于后驗(yàn)克拉美羅下界（Posterior Cramer-Rao Lower Bounds，PCRLB）[8]進(jìn)行求解，PCRLB是一個(gè)重要的工具，它對(duì)貝葉斯框架下的任何非線性濾波問(wèn)題的狀態(tài)估計(jì)提供了理論上的均方誤差（mean squareed error，MSE）界限。L.Zuo等[9]提出了條件后驗(yàn)克拉美羅下界（Conditional Posterior Cramer-Rao Lower Bounds，CPCRLB），它基于真實(shí)的量測(cè)信息給出了比PCRLB更準(zhǔn)確和有效的均方誤差界限，更加適合于無(wú)線傳感器網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)管理。楊小軍[10]等人采用窮舉的方法解決節(jié)點(diǎn)選擇問(wèn)題。魏聲云[11]等人采用二進(jìn)制粒子群優(yōu)化算法進(jìn)行求解。但是以上算法在處理大規(guī)模傳感器網(wǎng)絡(luò)時(shí)，都存在收斂速度慢，容易陷入局部最優(yōu)的問(wèn)題?；依撬惴ǎ℅rey Wolf optimizition，GWO）[12]是Mirjalili等于2014年提出的一種群智能優(yōu)化算法。

本文基于CPCRLB和自適應(yīng)二進(jìn)制灰狼優(yōu)化算法解決WSN中目標(biāo)跟蹤時(shí)的節(jié)點(diǎn)選擇問(wèn)題，本文的貢獻(xiàn)在于提出了一種自適應(yīng)二進(jìn)制灰狼優(yōu)化算法，其采用自適應(yīng)收斂因子，提高了算法的全局搜索能力，平衡了算法的探索和開(kāi)發(fā)兩個(gè)過(guò)程。同時(shí)，其采用V型函數(shù)的位置更新原則，加快了算法的收斂速度和局部尋優(yōu)能力。最后將其應(yīng)用于基于CPCRLB節(jié)點(diǎn)選擇優(yōu)化模型的求解，并在獲得節(jié)點(diǎn)子集以后采用粒子濾波器目標(biāo)跟蹤，大量的仿真結(jié)果證明了該算法在處理大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤中節(jié)點(diǎn)選擇問(wèn)題的有效性。

1 節(jié)點(diǎn)選擇模型建立

1.1 目標(biāo)狀態(tài)方程和傳感器節(jié)點(diǎn)量測(cè)方程

1）狀態(tài)方程

其中，F(xiàn)k為狀態(tài)轉(zhuǎn)移矩陣，Wk為過(guò)程噪聲且為高斯白噪聲，其協(xié)方差矩陣為Q。

2）量測(cè)方程

1.2 基于CPCRLB的節(jié)點(diǎn)選擇模型

CPCRLB可以作為一個(gè)解決傳感網(wǎng)中目標(biāo)跟蹤時(shí)節(jié)點(diǎn)選擇問(wèn)題的解決方案，它是費(fèi)歇爾信息矩陣（Fisher information matrix，F(xiàn)IM）的逆，可以表示當(dāng)前選擇的傳感器節(jié)點(diǎn)的跟蹤性能的下界[9]。CPCRLB越小，說(shuō)明當(dāng)前選擇的傳感器節(jié)點(diǎn)的跟蹤性能越好。

假設(shè)x?為x的估計(jì)值，用x0:k和z1:k表示從0到k時(shí)刻的目標(biāo)狀態(tài)和量測(cè)，已知初始的聯(lián)合概率密度p（x0），以及噪聲模型Wk和vk，其中兩個(gè)噪聲相互獨(dú)立。

在傳統(tǒng)的無(wú)條件PCRLB中，x0:k和z1:k都是隨機(jī)向量，邊界是通過(guò)對(duì)所有的z1:k和x0:k取平均值。實(shí)際上，在k+1時(shí)刻，除了目標(biāo)狀態(tài)方程和量測(cè)方程之外，還可能知道z1:k。在已知過(guò)去所有z1:k的條件下，當(dāng)新的量測(cè)zk+1到達(dá)時(shí),估計(jì)目標(biāo)狀態(tài)xk+1的條件MSE的下界滿足式(3)[10]：

文獻(xiàn)[15,18]中提供了一個(gè)更加直接的CPCRLB近似迭代公式，如式(4)所示：

根據(jù)目標(biāo)運(yùn)動(dòng)的狀態(tài)方程，量測(cè)方程以及式(4)，可以近似的計(jì)算出其FIM，如式(5)所示。

CPCRLB基于迄今為止獲得的真實(shí)量測(cè)給出了目標(biāo)跟蹤過(guò)程中的一個(gè)預(yù)測(cè)性能邊界。由于在目標(biāo)跟蹤過(guò)程中，只需要關(guān)心目標(biāo)當(dāng)前位置，因此采用FIM中對(duì)應(yīng)于目標(biāo)位置分量的和作為節(jié)點(diǎn)選擇的適應(yīng)度函數(shù)。假設(shè)在k+1時(shí)刻，從Na個(gè)傳感器節(jié)點(diǎn)中選擇Ns個(gè)傳感器節(jié)點(diǎn)集為S×（k+1），則：

由式(6)可知，節(jié)點(diǎn)選擇問(wèn)題是一個(gè)具有約束條件的NP難組合優(yōu)化問(wèn)題[11]。這種問(wèn)題目前廣泛采用群優(yōu)化算法進(jìn)行求解。

3 基于自適應(yīng)灰狼優(yōu)化算法的CPCRLB的求解

3.1 灰狼優(yōu)化算法

灰狼算法[14]主要是模擬灰狼種群的嚴(yán)格的金字塔等級(jí)制度，將最優(yōu)解視為α狼（僅存在一個(gè)），次優(yōu)解和第三優(yōu)的解視為β狼和δ狼。其余的候選解被假定為ω狼。在GWO算法中狩獵（優(yōu)化）過(guò)程由α狼，β狼，和δ狼引導(dǎo)，ω狼跟隨上述狼群進(jìn)行搜索。

1）包圍獵物

在這個(gè)階段，狼群所執(zhí)行的最重要的活動(dòng)是環(huán)繞獵物，如式(7)所示：

其中，當(dāng)前迭代次數(shù)為l，D由式(8)求解，獵物的位置向量XP，X（l）表示在迭代次數(shù)為l時(shí)灰狼的位置矢量。

A和C表示向量系數(shù)，可由式(9)求解。

其中，α為收斂因子，r1和r2分別為[0，1]之間的隨機(jī)數(shù)。

2）狩獵階段

灰狼能夠識(shí)別獵物的位置并包圍它們。狩獵通常由α狼引導(dǎo)，β狼和δ狼也可能偶爾參與狩獵。通過(guò)α狼，β狼和δ狼估計(jì)獵物的位置，ω狼隨機(jī)更新它們的位置，如式(10)～式(12)所示。

3.2 自適應(yīng)二進(jìn)制灰狼優(yōu)化算法

由式(10)可知，等級(jí)較低的狼根據(jù)依靠α狼更新自身位置，所以當(dāng)?shù)燃?jí)高的狼陷入局部最優(yōu)時(shí)，等級(jí)低的狼很可能會(huì)跟隨他們陷入局部最優(yōu)。針對(duì)以上問(wèn)題，采用以下方法進(jìn)行改進(jìn)。

3.2.1 非線性自適應(yīng)收斂因子

在群智能優(yōu)化方法中，尋找全局最優(yōu)通常分為兩個(gè)基本階段:探索階段和開(kāi)發(fā)階段。在探索階段，算法嘗試著搜索整個(gè)解空間，而不是圍繞局部進(jìn)行搜索。在開(kāi)發(fā)階段，算法使用前階段獲取的信息來(lái)收斂于全局最優(yōu)。探索階段較長(zhǎng)會(huì)大大增加算法的隨機(jī)性，可能會(huì)產(chǎn)生不好的優(yōu)化結(jié)果，而太長(zhǎng)時(shí)間處于開(kāi)發(fā)階段又會(huì)降低算法的隨機(jī)性，所以探索和開(kāi)發(fā)兩個(gè)階段應(yīng)該保持平衡。在GWO中，通過(guò)微調(diào)A和a可以平衡這兩個(gè)階段，以更快的收斂速度尋找全局最優(yōu)。當(dāng)|A|≥1時(shí)，算法處于探索階段，灰狼傾向于偏離獵物,從而實(shí)現(xiàn)全局搜索，當(dāng)|A|＜1時(shí)，算法處于開(kāi)發(fā)階段，灰狼趨向于獵物，從而實(shí)現(xiàn)局部搜索[12]。由式(9)可知，A的值或隨著收斂因子a的值逐漸減小，文獻(xiàn)[13]中a隨著迭代次數(shù)的增加線性減少，在包圍獵物時(shí)容易出現(xiàn)停滯，影響算法的搜索能力，很難滿足現(xiàn)實(shí)中優(yōu)化問(wèn)題的多樣性。

針對(duì)以上問(wèn)題，提出了非線性自適應(yīng)動(dòng)態(tài)收斂因子，通過(guò)控制A的值來(lái)提高算法的全局和局部搜索能力。

提出的自適應(yīng)收斂因子表達(dá)式如式(13)所示：在式(24)中，a_max為收斂因子設(shè)置的最大值，a_min為收斂因子的最小值，Maxlter為總迭代次數(shù)。

3.2.2 V型函數(shù)位置更新原則

在進(jìn)行目標(biāo)跟蹤時(shí)，通常需要將位置信息轉(zhuǎn)換到二進(jìn)制空間，轉(zhuǎn)換函數(shù)是設(shè)計(jì)二進(jìn)制優(yōu)化算法時(shí)經(jīng)常使用的方法，本文采用V型轉(zhuǎn)換函數(shù)作為新的位置更新原則。這種位置更新原則的優(yōu)點(diǎn)是其根據(jù)當(dāng)前獵物位置來(lái)改變灰狼個(gè)體位置。當(dāng)距離獵物位置較近時(shí)，V型函數(shù)鼓勵(lì)灰狼停留在當(dāng)前位置，以尋找最佳獵物位置，當(dāng)距離獵物位置較遠(yuǎn)時(shí)，V型函數(shù)將灰狼位置轉(zhuǎn)換為其當(dāng)前位置的補(bǔ)碼，即增加遠(yuǎn)離獵物位置的灰狼尋找新獵物位置的概率。

采用的V型函數(shù)如式(14)所示：

3.2.3 基于自適應(yīng)二進(jìn)制灰狼算法的CPCRLB的求解

1）約束條件A

觀測(cè)區(qū)域內(nèi)存在個(gè)目標(biāo)和傳感器節(jié)點(diǎn)，需要在不同的時(shí)刻選擇最優(yōu)節(jié)點(diǎn)分配給不同的目標(biāo)。采用二進(jìn)制編碼的灰狼種群來(lái)表示傳感器節(jié)點(diǎn)。種群POP為一個(gè)pop_n×Na（pop_n為種群個(gè)體數(shù)量）的矩陣設(shè)置如下：

如果選擇的節(jié)點(diǎn)數(shù)的和（Ns’）大于需要的節(jié)點(diǎn)數(shù)的和（Ns），那么就從Ns’中隨機(jī)選擇Ns個(gè)節(jié)點(diǎn)數(shù)。如果選擇的節(jié)點(diǎn)數(shù)的和（Ns’）小于需要的節(jié)點(diǎn)數(shù)的和（Ns），那就從剩余的節(jié)點(diǎn)數(shù)中以相同的概率選擇（Ns- Ns’）個(gè)節(jié)點(diǎn)。

在開(kāi)始迭代時(shí)，我們隨機(jī)初始化種群，但是在算法的迭代過(guò)程中，對(duì)種群進(jìn)行更新以后，產(chǎn)生的新的種群中被選擇的傳感器節(jié)點(diǎn)數(shù)可能不能滿足需要的傳感器節(jié)點(diǎn)數(shù)，因此在每次迭代后通過(guò)以下方法來(lái)滿足被選擇的傳感器節(jié)點(diǎn)數(shù)等于需要的傳感器節(jié)點(diǎn)數(shù)。

2）約束條件B

3）算法流程

綜合上方提到的改進(jìn)方法，自適應(yīng)二進(jìn)制灰狼算法（VBGWO）的流程（流程圖如圖2所示）如下：

STEP 1：設(shè)置種群POP，需要選擇的節(jié)點(diǎn)數(shù)Ns，粒子群數(shù)目Np，最大迭代次數(shù)，初始的適應(yīng)度函數(shù)值等參數(shù)。

STEP 2：根據(jù)約束條件A隨機(jī)初始化灰狼種群。

STEP 3：根據(jù)式(6)計(jì)算適應(yīng)度函數(shù)值，選取適應(yīng)度值在前三的狼，并記錄對(duì)應(yīng)的位置。

STEP 4：利用式(13)計(jì)算收斂因子a的值，利用式(9)計(jì)算A，C的值。并利用式(10)～式(12)計(jì)算距離信息。

STEP 5：利用新的位置更新原則式(14)，產(chǎn)生新的種群。

STEP 6：判斷產(chǎn)生的種群中被激活的節(jié)點(diǎn)個(gè)數(shù)是否滿足約束條件B。

STEP 7：判斷是否滿足結(jié)束條件，若達(dá)到最大迭代次數(shù)，則輸出最優(yōu)位置及對(duì)應(yīng)的適應(yīng)度函數(shù)值，否則重復(fù)執(zhí)行STEP（3～6）。

圖1 自適應(yīng)二進(jìn)制算法流程圖

4 實(shí)驗(yàn)仿真

分別為k時(shí)刻目標(biāo)狀態(tài)的估計(jì)值，Mc為蒙特卡羅次數(shù)，采用50次蒙特卡洛仿真。

表1給出了選取不同算法在k=15時(shí)的適應(yīng)度函數(shù)值對(duì)比，由表可知，VBGWO能夠獲得更好的平均適應(yīng)度函數(shù)值和最佳適應(yīng)度函數(shù)，為了更好的對(duì)比各種算法的優(yōu)劣性，我們隨機(jī)選取其中一組優(yōu)化過(guò)程如圖2所示。

表1 50次蒙特卡洛 k=15時(shí)的適應(yīng)度函數(shù)值對(duì)比

圖2 Ns=50，Na=3時(shí)間k=15時(shí)適應(yīng)度函數(shù)值

由圖2可知，VBGWO大約在第12次時(shí)達(dá)到最佳函數(shù)值，而B(niǎo)PSO則大約在50次時(shí)達(dá)到最佳適應(yīng)度函數(shù)值，說(shuō)明VBGWO可以保持較高的收斂速度，同時(shí)，VBGWO在循環(huán)至10次左右時(shí)就獲得了BPSO最終的適應(yīng)度函數(shù)值，最終VBGWO取得的最佳函數(shù)值大于BPSO取得的適應(yīng)度函數(shù)值，說(shuō)明VBGWO擁有較高的收斂精度。在迭代后期，相對(duì)于其他兩種算法，VBGWO的曲線并沒(méi)有出現(xiàn)太多的階躍，說(shuō)明VBGWO能夠更好的跳出局部最優(yōu)并搜索到最佳適應(yīng)度值。相對(duì)于上述兩種算法，VBGWO采用了非線性自適應(yīng)收斂因子和V型位置更新原則更好的提高了算法收斂速度和局部尋優(yōu)能力，較快的收斂速度對(duì)于無(wú)線傳感器網(wǎng)絡(luò)的實(shí)時(shí)性是非常重要的，所以，VBGWO更加適合于無(wú)線傳感器網(wǎng)絡(luò)。

圖3 不同算法的RMSE誤差對(duì)比

圖3采用不同算法從50個(gè)傳感器節(jié)點(diǎn)中選取3個(gè)傳感器節(jié)點(diǎn)的RMSE誤差對(duì)比圖，由圖可知，VBGWO相對(duì)于其他兩種算法，能選擇一組最優(yōu)的傳感器觀測(cè)節(jié)點(diǎn)集合,而且估計(jì)出的狀態(tài)具有較小的均方根誤差，所以擁有較佳的跟蹤性能。

圖4為k=15時(shí)從50，80，100個(gè)傳感器節(jié)點(diǎn)中選取圖6為k=15時(shí)從50，80，100個(gè)傳感器節(jié)點(diǎn)中選取三個(gè)傳感器節(jié)點(diǎn)的迭代過(guò)程。由圖可知，隨著傳感器節(jié)點(diǎn)總數(shù)的增加，相對(duì)于其他兩種算法，VBGWO依舊可以保持良好的收斂速度，說(shuō)明VBGWO有較強(qiáng)的全局搜索能力。同時(shí)其最佳適應(yīng)度函數(shù)值始終大于其他兩種算法，表明其具有具有較小的跟蹤誤差。

圖4 k=15時(shí)，當(dāng)Ns=50，80，100（從上到下）時(shí)，選取3個(gè)傳感器節(jié)點(diǎn)的適應(yīng)度函數(shù)值

5 結(jié)語(yǔ)

主要研究了大規(guī)模傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)選擇問(wèn)題，采用基于粒子濾波的CPCRLB作為優(yōu)化條件建立節(jié)點(diǎn)選擇模型，并提出自適應(yīng)二進(jìn)制灰狼優(yōu)化算法進(jìn)行模型求解。仿真結(jié)果表明，采用自適應(yīng)動(dòng)態(tài)收斂因子和V型函數(shù)的自適應(yīng)二進(jìn)制灰狼算法針對(duì)于節(jié)點(diǎn)選擇問(wèn)題是有效的，其擁有較高的收斂速度，能夠避免陷入局部最優(yōu)。后續(xù)的研究工作是主要是將目前提出的算法應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)多傳感器多目標(biāo)跟蹤時(shí)的節(jié)點(diǎn)選擇問(wèn)題。