基于能量限制的分布式無線傳感器網絡調度

衛朝霞，劉志超，羅 佳

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

0 引言

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

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

分布式網絡結構不需要將數據傳輸到信息處理中心，每個傳感器自身具有信息處理功能，從而大大減小了傳感器之間的通信能量消耗[14-15]。因此，本文針對分布式無線傳感器能量管理問題，提出基于能量限制的分布式無線傳感器網絡調度方法。

1 分布式目標狀態估計方法

1.1 分布式無線傳感器網絡

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

為節省傳感器計算能量消耗及傳感器之間的盲目信息傳輸消耗，設置“頭領傳感器”。在觀測時刻k，設對目標t觀測的傳感器集合為λk(t)，“頭領傳感器”記為hk(t)，hk(t)∈λk(t)；λk(t)內的其他傳感器統稱為“成員傳感器”，位于傳感器網絡不能觀測到該目標的傳感器稱為“閑置傳感器”。在觀測時刻k，傳感器集合中的所有傳感器將收集到的目標信息傳遞給該hk(t)，由hk(t)對目標信息進行融合得到關于狀態信息的最佳估計并將估計結果發送給到k+1時刻的“頭領傳感器”hk+1(t)，并由hk+1(t)將目標信息發送給集合λk+1(t)中的其他傳感器，以便傳感器能夠對準目標快速獲取觀測值。

按照上述傳感器網絡對目標的跟蹤框架，目標跟蹤過程如圖1所示。

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

在觀測時刻k，設對傳感器的調度方案為Ak，由Ak得到λk(t)。“成員傳感器”僅需按照傳感器調度指令對目標進行探測，獲得觀測值后將目標信息傳遞給“頭領傳感器”。而“頭領傳感器”需要進行如下活動：

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

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

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

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

1.2 目標跟蹤理論

(1)

(2)

基于UKF目標狀態估計過程為：

步驟3 傳遞目標狀態樣本和量測樣本

(3)

步驟4 時間更新

(4)

(5)

步驟5 量測更新

(6)

(7)

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

(8)

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

(9)

2 基于能量限制無線傳感器調度

2.1 傳感器調度目標函數

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

1)傳感器對目標狀態進行觀測；

2)傳感器之間數據傳送；

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

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

(10)

約束條件為：

(11)

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

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

(12)

約束條件為：

(13)

2.2 模型分析

(14)

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

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

(15)

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

E(1)=eK+eampKdλ

(16)

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

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

E(2)=erecK

(17)

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

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

(18)

綜上，目標函數轉化為：

(19)

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

(20)

約束條件同式(13)。

2.3 觀測周期分析

(21)

將上式對Tk-k+1求導，有：

(22)

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

(23)

2.4 模型求解算法

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

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

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

(24)

(25)

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

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

2)算法運行開始。

when(K≤Number 1)

進行如下判斷：

forj=1:Number 2

end

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

適應度較優的鳥巢延續到下一次迭代；

記錄種群中的最優鳥巢及適應度值；

K=K+1

end

3)輸出最優解。

3 仿真分析

分布式傳感器網絡在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 調度方案計算過程仿真分析

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

圖4 優化算法對比Fig.4 Comparison of optimization algorithms

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

3.2 傳感器短時調度分析

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

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

如圖5所示，“+”軌跡為目標實際飛行位置，“◇”軌跡為對目標狀態的估計值；“頭領傳感器”為黑色實心“·”，“成員傳感器”為灰色實心“·”，“閑置傳感器”為黑色空心“·”。在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可知，與其他兩種方法相比，本文方法在保持較好的目標跟蹤效果的同時，能夠大大減小傳感器網絡能量消耗，從而有效提高傳感器網絡壽命。

3.3 傳感器長時調度分析

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

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

表1 調度方法對比結果Tab.1 The comparison result of sensor scheduling methods

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

4 結論

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