基于能量限制的分布式無線傳感器網(wǎng)絡(luò)調(diào)度

衛(wèi)朝霞，劉志超，羅 佳

(1.四川大學(xué)錦城學(xué)院，四川 成都 611731；2.無錫太湖學(xué)院物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214064；3.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122；4.四川大學(xué)錦江學(xué)院，四川 彭山 620860)

0 引言

無線傳感器網(wǎng)絡(luò)具有體積小、重量輕、價格低廉等特點，被廣泛應(yīng)用于氣象預(yù)報、目標跟蹤、火災(zāi)監(jiān)控等領(lǐng)域[1-2]。本文主要研究傳感器網(wǎng)絡(luò)對目標的跟蹤問題，采用傳感器調(diào)度技術(shù)根據(jù)某種準則確定傳感器網(wǎng)絡(luò)的最佳工作模式[3]，此類問題可以看作凸優(yōu)化問題[4]，包含兩方面內(nèi)容：一方面是建立目標函數(shù)；另一方面是對目標函數(shù)求解得到調(diào)度方案。基于優(yōu)化理論，常見的調(diào)度方法有：基于協(xié)方差矩陣的調(diào)度方法[5]、基于熵理論的調(diào)度方法[6]、基于后驗克拉美羅下界的調(diào)度方法[7]、基于馬爾科夫決策過程的調(diào)度方法[8]、基于智能算法的調(diào)度方法[9-10]以及其他自適應(yīng)控制方法[11]。

以上方法僅從對目標的跟蹤性能上考慮調(diào)度問題，以目標跟蹤效果的好壞評價調(diào)度方案的優(yōu)劣。與雷達等大型供電供能傳感器不同之處在于，無線傳感器網(wǎng)絡(luò)供能來源于固定電池，而電池容量是有限的，因此，在調(diào)度過程中，也應(yīng)同時考慮傳感器網(wǎng)絡(luò)的能量消耗問題，在提高跟蹤效果和節(jié)省能量延長傳感器網(wǎng)絡(luò)使用壽命之間找到平衡[12-13]。

分布式網(wǎng)絡(luò)結(jié)構(gòu)不需要將數(shù)據(jù)傳輸?shù)叫畔⑻幚碇行?，每個傳感器自身具有信息處理功能，從而大大減小了傳感器之間的通信能量消耗[14-15]。因此，本文針對分布式無線傳感器能量管理問題，提出基于能量限制的分布式無線傳感器網(wǎng)絡(luò)調(diào)度方法。

1 分布式目標狀態(tài)估計方法

1.1 分布式無線傳感器網(wǎng)絡(luò)

在分布式無線傳感器網(wǎng)絡(luò)中，每個傳感器除具有一般傳感器具有的信息收集功能和信息傳輸、接收功能外，還同時具有信息處理和決策功能，即能將自身收集到的目標信息與接收到的來自其他傳感器的目標信息進行融合，得到關(guān)于目標狀態(tài)的更佳估計，同時能夠進行自主決策，決定將自身收集到的信息是否傳遞給其他傳感器、傳遞給哪個傳感器。

為節(jié)省傳感器計算能量消耗及傳感器之間的盲目信息傳輸消耗，設(shè)置“頭領(lǐng)傳感器”。在觀測時刻k，設(shè)對目標t觀測的傳感器集合為λk(t)，“頭領(lǐng)傳感器”記為hk(t)，hk(t)∈λk(t)；λk(t)內(nèi)的其他傳感器統(tǒng)稱為“成員傳感器”，位于傳感器網(wǎng)絡(luò)不能觀測到該目標的傳感器稱為“閑置傳感器”。在觀測時刻k，傳感器集合中的所有傳感器將收集到的目標信息傳遞給該hk(t)，由hk(t)對目標信息進行融合得到關(guān)于狀態(tài)信息的最佳估計并將估計結(jié)果發(fā)送給到k+1時刻的“頭領(lǐng)傳感器”hk+1(t)，并由hk+1(t)將目標信息發(fā)送給集合λk+1(t)中的其他傳感器，以便傳感器能夠?qū)誓繕丝焖佾@取觀測值。

按照上述傳感器網(wǎng)絡(luò)對目標的跟蹤框架，目標跟蹤過程如圖1所示。

圖1 傳感器視域及目標跟蹤示意圖Fig.1 The FOV of sensors and the tracking process

在觀測時刻k，設(shè)對傳感器的調(diào)度方案為Ak，由Ak得到λk(t)?！俺蓡T傳感器”僅需按照傳感器調(diào)度指令對目標進行探測，獲得觀測值后將目標信息傳遞給“頭領(lǐng)傳感器”。而“頭領(lǐng)傳感器”需要進行如下活動：

1)對目標進行觀測，獲得觀測值；

2)接收“成員傳感器”發(fā)送的關(guān)于目標狀態(tài)的信息，并通過濾波算法對觀測信息進行融合；

3)計算k時刻和k+1時刻的觀測時間Tk-k+1；

4)預(yù)測k+1時刻目標狀態(tài)，以此為依據(jù)確定Ak+1、λk+1(t)和hk+1(t)，并將關(guān)于目標的狀態(tài)信息傳遞給λk+1(t)中的傳感器。

1.2 目標跟蹤理論

(1)

(2)

基于UKF目標狀態(tài)估計過程為：

步驟3 傳遞目標狀態(tài)樣本和量測樣本

(3)

步驟4 時間更新

(4)

(5)

步驟5 量測更新

(6)

(7)

步驟6k+1時刻，根據(jù)傳感器si觀測值，對目標后驗狀態(tài)估計均值和協(xié)方差矩陣為：

(8)

步驟7 融合估計。設(shè)k+1時刻共有nk+1個傳感器對目標觀測，則對目標狀態(tài)估計得最終融合結(jié)果為：

(9)

2 基于能量限制無線傳感器調(diào)度

2.1 傳感器調(diào)度目標函數(shù)

在整個傳感器網(wǎng)絡(luò)對目標的跟蹤過程中，消耗能量的過程主要有以下幾個方面：

1)傳感器對目標狀態(tài)進行觀測；

2)傳感器之間數(shù)據(jù)傳送；

3)傳感器對信息進行處理。

根據(jù)以上分析，傳感器在k時刻調(diào)度以獲取k+1時刻的觀測值的過程中應(yīng)從以上三方面入手減小能量消耗，同時盡量增大較大的傳感器對目標觀測的時間間隔，故在調(diào)度中，目標函數(shù)為：

(10)

約束條件為：

(11)

由于在k時刻尚未獲知k+1時刻關(guān)于目標的量測及估計狀態(tài)，故在估計過程中均采用式(6)—(7)中的預(yù)測值代替。

一般情況下，若觀測時間序列較長，常采用長時調(diào)度方法，不僅考慮某個時刻最優(yōu)，而且進一步考慮整個時間段最優(yōu)，通常選擇一個時域周期TH，且TH通常取值范圍為TH～{2,3,4,5}，在該時域周期內(nèi)計算傳感器調(diào)度方案，則該調(diào)度問題轉(zhuǎn)化為“滾動時域調(diào)度”[16]問題，目標函數(shù)為：

(12)

約束條件為：

(13)

2.2 模型分析

(14)

式(14)中，nk+1為傳感器個數(shù)，esen為單個傳感器獲取觀測值消耗的能量。

圖2 信息傳遞能量消耗Fig.2 The energy consumption in information transmitting

(15)

傳感器si發(fā)送Kbit信息到傳感器sj消耗的能量為：

E(1)=eK+eampKdλ

(16)

式(16)中，e為發(fā)射每bit信息所需能量；eamp為放大器放大每bit所需能量；d為兩個傳感器之間的距離；λ為距離衰減系數(shù)，一般有λ≥2。

傳感器sj接收Kbit信息消耗的能量為：

E(2)=erecK

(17)

式(17)中，erec為接收每bit所需能量。

由于傳感器之間交流的信息均為目標信息，不妨假定該信息均包含Kbit，根據(jù)以上分析，有：

(18)

綜上，目標函數(shù)轉(zhuǎn)化為：

(19)

約束條件通式(11)。若采用滾動時域調(diào)度(長時調(diào)度)方法，則模型轉(zhuǎn)換為：

(20)

約束條件同式(13)。

2.3 觀測周期分析

(21)

將上式對Tk-k+1求導(dǎo)，有：

(22)

很明顯，式(18)為關(guān)于Tk-k+1的單調(diào)增函數(shù)，當且僅當φk+1|k=φ0時，可取得最優(yōu)值，故通過對如下公式求解，可得到最佳觀測周期。

(23)

2.4 模型求解算法

在求得觀測周期后，需要計算傳感器調(diào)度方案，方案的求解過程是一個NP爆炸問題，且由于目標速度運動較快，要求算法具有計算時間短、求解精度高等特點。

由于布谷鳥捜索算法具有參數(shù)少、易擴展、全局搜索能力強、易于實現(xiàn)等優(yōu)點[18]，本文引入布谷鳥算法求解傳感器調(diào)度方案，并進行了一定的改進，用Boltzmann選擇策略[19]代替基本算法中的Levy fights策略，在原有可行解的基礎(chǔ)上生成新解，進一步提高算法搜索能力。

與Levy fights策略相比，Boltzmann選擇策略具有穩(wěn)定性、魯棒性、并行性等優(yōu)點，對初始解不敏感，具有較好的自適應(yīng)性。在改進布谷鳥搜索算法中，基于Boltzmann選擇策略的捜索步長公式為：

(24)

(25)

式(25)中，randn為生成隨機數(shù)函數(shù)。

基于Boltzmann選擇策略的改進布谷鳥算法流程如下：

2)算法運行開始。

when(K≤Number 1)

進行如下判斷：

forj=1:Number 2

end

一部分適應(yīng)度較差的鳥巢以概率Pa被拋棄并在相應(yīng)位置生成新解；

適應(yīng)度較優(yōu)的鳥巢延續(xù)到下一次迭代；

記錄種群中的最優(yōu)鳥巢及適應(yīng)度值；

K=K+1

end

3)輸出最優(yōu)解。

3 仿真分析

分布式傳感器網(wǎng)絡(luò)在1 000 m×1 000 m的分布位置及目標的運動軌跡如圖3所示。傳感器的探測半徑和通信半徑均為150 m，目標初始時刻位置為(510,190)。

圖3 傳感器分布及目標運動軌跡Fig.3 Distribution of sensor networks and the motion trajectory of the target

3.1 調(diào)度方案計算過程仿真分析

在初始時刻，采用本文提出的改進布谷鳥算法計算傳感器調(diào)度方案，并與其他算法進行對比，傳感器調(diào)度方案的生成過程如圖4所示。其中，改進算法記為算法1，基本布谷鳥算法記為算法2，狼群算法[20]記為算法3，粒子群算法[21]記為算法4。

圖4 優(yōu)化算法對比Fig.4 Comparison of optimization algorithms

由圖4可知，與其他三種算法相比，改進布谷鳥算法收斂速度明顯提升，且具有較好的求解質(zhì)量。

3.2 傳感器短時調(diào)度分析

采用短時調(diào)度方法對傳感器進行調(diào)度。在目標運動過程當中，當需要調(diào)度傳感器對目標進行觀測時，采用本文提出的改進布谷鳥算法生成傳感器調(diào)度方案。對目標的軌跡估計圖像及目標軌跡如圖5所示。

圖5 傳感器調(diào)度方案及目標軌跡估計結(jié)果Fig.5 The sensor scheduling scheme and estimation of target’s motion states

如圖5所示，“+”軌跡為目標實際飛行位置，“◇”軌跡為對目標狀態(tài)的估計值；“頭領(lǐng)傳感器”為黑色實心“·”，“成員傳感器”為灰色實心“·”，“閑置傳感器”為黑色空心“·”。在25個時刻中，僅有14個時刻傳感器對目標進行了觀測，這14個時刻分別為：k=1，k=2，k=4，k=6，k=8，k=9，k=14，k=15，k=17，k=18，k=20，k=21，k=23，k=25。

圖6 方法對比曲線Fig.6 Comparisons of scheduling methods

由圖6可知，與其他兩種方法相比，本文方法在保持較好的目標跟蹤效果的同時，能夠大大減小傳感器網(wǎng)絡(luò)能量消耗，從而有效提高傳感器網(wǎng)絡(luò)壽命。

3.3 傳感器長時調(diào)度分析

采用長時(滾動時域)調(diào)度方法對傳感器網(wǎng)絡(luò)進行調(diào)度，從而對目標進行跟蹤。目標運動過程當中，當需要調(diào)度傳感器對目標進行觀測時，采用本文提出的改進布谷鳥算法生成傳感器調(diào)度方案。

分別取TH=2，TH=3，TH=4三種情況，傳感器調(diào)度過程中，對目標跟蹤的累積位置誤差、累積能量消耗和平均計算時間如表1所示。在仿真過程中，由于TH=5時，計算量過大，在時間間隔內(nèi)不能及時計算出傳感器調(diào)度位置，故不再考慮。TH=1時即為短時調(diào)度。

表1 調(diào)度方法對比結(jié)果Tab.1 The comparison result of sensor scheduling methods

由表1可知，與短時調(diào)度方法相比，長時調(diào)度方法雖然能夠減小對目標狀態(tài)的估計誤差，降低傳感器網(wǎng)絡(luò)能耗，但是以提高計算時間為代價，且計算時間大幅增加。一般情況下，為縮短計算時間，為其他操作留出響應(yīng)時間，采用短時調(diào)度即可滿足相應(yīng)需求。

4 結(jié)論

本文提出基于能量限制的分布式無線傳感器網(wǎng)絡(luò)調(diào)度方法。該方法同時考慮傳感器感知能量消耗、傳輸能量消耗以及計算能力消耗建立傳感器調(diào)度目標函數(shù)，并采用基于Boltzmann選擇策略的改進布谷鳥算法求解傳感器調(diào)度方案。仿真實驗驗證結(jié)果表明，為節(jié)省計算時間，在目標狀態(tài)改變速度較快的情況下，選擇本文提出的短時調(diào)度方法既能縮短調(diào)度方案的計算時間，又能獲得較好的目標跟蹤效果。