基于二次灰色馬爾科夫預(yù)測的WSN狀態(tài)判定算法＊

林 蔚，李 波，韓麗紅

（哈爾濱工程大學(xué)理學(xué)院，黑龍江 哈爾濱150001）

1 引言

在以監(jiān)測為主要目的的無線傳感網(wǎng)絡(luò)應(yīng)用環(huán)境中，監(jiān)測的最終目標(biāo)并不是要得到監(jiān)測環(huán)境的全部實時數(shù)據(jù)，更主要的是要得到其異常數(shù)據(jù)，那么就不需要對全體監(jiān)測數(shù)據(jù)進(jìn)行傳輸。但是，數(shù)據(jù)何時出現(xiàn)異常是未知的，因此預(yù)測可以幫助提高監(jiān)測效率，也即只需要傳感器節(jié)點預(yù)測出下一個時間點數(shù)據(jù)的變異狀態(tài)并將其發(fā)送到基站。本文提出一種無線傳感器網(wǎng)絡(luò)監(jiān)測環(huán)境的狀態(tài)預(yù)測思想：根據(jù)具體的監(jiān)測環(huán)境和監(jiān)測目的，制定不同的狀態(tài)準(zhǔn)則，以此預(yù)測下一個時刻的環(huán)境狀態(tài)且用簡單的符號或數(shù)字對狀態(tài)做標(biāo)識，將標(biāo)識進(jìn)行傳輸。

無線傳感器網(wǎng)絡(luò)節(jié)點采集數(shù)據(jù)的時間點和采集的數(shù)據(jù)具有離散的特性，且采集的數(shù)據(jù)僅與當(dāng)時采樣的監(jiān)測環(huán)境有關(guān)系，即在某一時刻采集的數(shù)據(jù)僅依賴于現(xiàn)在而不依賴于過去，這一點正與馬爾科夫模型的性質(zhì)相同。馬爾科夫預(yù)測［1～4］是基于馬爾可夫鏈、根據(jù)事件的當(dāng)前狀況預(yù)測其將來時刻（或時期）變動狀況的一種事件概率預(yù)測方法。它利用狀態(tài)之間的轉(zhuǎn)移概率矩陣預(yù)測事件發(fā)生的狀態(tài)及其發(fā)展變化的趨勢，因而比較適合長期的、隨機(jī)波動性較大的預(yù)測問題［5］。由于無線傳感器網(wǎng)絡(luò)節(jié)點存儲空間有限，不能存儲大量的采樣數(shù)據(jù)，直接將馬爾科夫預(yù)測方法應(yīng)用到無線傳感器網(wǎng)絡(luò)，會導(dǎo)致節(jié)點存儲的堵塞。盡管灰色預(yù)測方法適用于時間短、數(shù)量少、波動不大的預(yù)測問題，但是灰色預(yù)測模型本身存在較大誤差，得到的預(yù)測結(jié)果并不精確［6～9］。因此，針對無線傳感器網(wǎng)絡(luò)的特點，本文結(jié)合馬爾科夫預(yù)測思想，對灰色預(yù)測模型進(jìn)行改進(jìn)，提出二次無偏灰色馬爾科夫預(yù)測模型，解決網(wǎng)絡(luò)狀態(tài)預(yù)測問題，降低網(wǎng)絡(luò)能量消耗，延長網(wǎng)絡(luò)生命期。

2 二次無偏灰色預(yù)測模型

由于灰色預(yù)測模型本身存在較大的預(yù)測誤差，不能得到較好的預(yù)測結(jié)果，如圖1所示，直接將其應(yīng)用到受多種因素影響的實時監(jiān)測的無線傳感器網(wǎng)絡(luò)中，得到的預(yù)測數(shù)據(jù)精確度會很低，所以需要尋找一種能夠彌補(bǔ)灰色預(yù)測本身所存在誤差的方法，減弱其自身對數(shù)據(jù)預(yù)測的影響。為此，本節(jié)提出了二次無偏灰色預(yù)測方法，先對原始采樣數(shù)據(jù)進(jìn)行弱化處理，對處理后的數(shù)據(jù)采用二次擬合，之后建立二次無偏灰色預(yù)測模型。

Figure 1 Gray measure schema圖1 灰色預(yù)測示意圖

首先將傳感器節(jié)點采集的時間數(shù)據(jù)序列看作一個馬爾科夫原始時間序列鏈，記為＝ （（t1，d1），（t2，d2），…，（tn，dn）），其中t是時間點，d 為t時刻的采樣數(shù)據(jù)，n表示一個采樣周期的時間點個數(shù)。

（1）采樣原始數(shù)據(jù)序列，記為D（0）＝ （d（0）（1），d（0）（2），…，d（0）（n））。

（2）對原始數(shù)據(jù)弱化處理，得到弱化序列為：H（0）＝ （h（0）（1），h（0）（2），…，h（0）（n）），其中，h（0）（i）＝（n）），i＝1，2，…，n。

（3）對 H（0）一次累加，得到：D（1）＝ （d（1）（1），d（1）（2），…，d（1）（n）），其中k＝1，2，…，n。

（4）一次模型記為d（1）（k＋1）＝λe－αk＋γ，k＝1，2，…，n，其中，λ＝d（1）（1）－β／α，γ＝β／α。

（5）根據(jù)灰色模型預(yù)測求得的α，對二階擬合參數(shù)λ、γ進(jìn)行估計：將一次模型寫成矩陣形式，有D（1）＝F（λ γ）Τ，其中：

（6）采 用最 小 二乘 法 求 解：（λ γ）Τ＝（FΤF）－1FΤD（1）；

（7）計算無偏二次模型的參數(shù)：通過對模型分析知道，預(yù)測的數(shù)據(jù) H∧（0）（k＋1）與k有指數(shù)關(guān)系［10］，則將具有指數(shù)趨勢的預(yù)測數(shù)據(jù)記為：h∧（0）（k＋1）＝Αebk，生成一次累加序列：

則有：

（10）根據(jù)弱化序列的預(yù)測值做強(qiáng)化運(yùn)算，得到原始數(shù)據(jù)的預(yù)測值為：

二次無偏灰色預(yù)測模型首先對采樣數(shù)據(jù)進(jìn)行了弱化處理，減弱參加預(yù)測數(shù)據(jù)的波動性；之后進(jìn)行二次灰色擬合，使得模型系數(shù)的預(yù)測更為準(zhǔn)確；之后根據(jù)灰色預(yù)測模型預(yù)測數(shù)據(jù)的指數(shù)趨勢，采用無偏方法，消除采用灰色預(yù)測產(chǎn)生的固有偏差，從兩次運(yùn)算的角度提高了模型預(yù)測的準(zhǔn)確度，為狀態(tài)預(yù)測的判定提供了準(zhǔn)確的數(shù)據(jù)。到此，我們得到的是數(shù)據(jù)，但還沒得到環(huán)境的狀態(tài)，為此，還需要結(jié)合馬爾科夫預(yù)測的思路進(jìn)行狀態(tài)判定。

3 馬爾科夫狀態(tài)預(yù)測

（11）根據(jù)二次無偏灰色模型求出原始數(shù)據(jù)序列的預(yù)測值d∧（0）（t）。

（14）根據(jù)檢測的具體環(huán)境和用戶的需求，在理想的狀態(tài)下將數(shù)據(jù)進(jìn)行劃分。

無線傳感器網(wǎng)絡(luò)監(jiān)測的環(huán)境是隨機(jī)的某種未知狀態(tài)，那么在對狀態(tài)進(jìn)行劃分時要考慮環(huán)境因素，為了使算法更具一般性，下面根據(jù)一般狀態(tài)馬爾可夫鏈定義無線傳感器網(wǎng)絡(luò)中的狀態(tài)。

3.1 定義

定義1 狀態(tài)：指某一監(jiān)測事件在某個時刻監(jiān)測的某種結(jié)果。一般而言，根據(jù)所監(jiān)測環(huán)境及其預(yù)測目標(biāo)的不同，狀態(tài)可以有多種劃分方式。

定義2 狀態(tài)轉(zhuǎn)移過程：在監(jiān)測事件的變化過程中，從一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)，稱為狀態(tài)轉(zhuǎn)移；監(jiān)測事件的變化，隨著時間所做的狀態(tài)轉(zhuǎn)移或者說狀態(tài)轉(zhuǎn)移與時間的關(guān)系，稱為狀態(tài)轉(zhuǎn)移過程，簡稱過程。

3.2 狀態(tài)判定準(zhǔn)則

根據(jù)具體監(jiān)測環(huán)境的目標(biāo)不同，對于狀態(tài)的劃分也會不同，為了減少數(shù)據(jù)傳輸量，對于監(jiān)測環(huán)境可能會出現(xiàn)的狀態(tài)分別標(biāo)識為?i，i＝1，2，…，m，m≤n；同時規(guī)定，在進(jìn)行數(shù)據(jù)傳輸時，仍需要根據(jù)實際需要來定義傳輸協(xié)議。下面給出適應(yīng)于無線傳感器網(wǎng)絡(luò)的狀態(tài)劃分判定。

根據(jù)無線傳感器網(wǎng)絡(luò)的實際應(yīng)用環(huán)境，將預(yù)測狀態(tài)分為正常和異常兩種狀態(tài)，同時為了節(jié)省傳輸過程中能量的消耗，減少數(shù)據(jù)傳輸量，分別標(biāo)識正常的狀態(tài)為0，異常的狀態(tài)為1；同時規(guī)定，正常狀態(tài)時不發(fā)送任何數(shù)據(jù)，只傳輸預(yù)測到的異常狀態(tài)（即標(biāo)識狀態(tài)為1時）的時刻點及異常數(shù)據(jù)。根據(jù)設(shè)定，誤差相對值ε（）k的取值為0或1。

3.2.1 初始化數(shù)據(jù)

初始化節(jié)點采樣數(shù)據(jù)D（0）＝ （d1，d2，…，dn），其初始數(shù)據(jù)長度為n。

3.2.2 目標(biāo)函數(shù)

以預(yù)測值與采樣數(shù)據(jù)誤差相對值ε（）k的均值作為目標(biāo)函數(shù)，使數(shù)據(jù)間的依存度最大，做出最優(yōu)決策，記

3.2.3 判定準(zhǔn)則

異常判定：對于下一個采樣數(shù)據(jù)與預(yù)測值的誤差的相對值，存在ε（k ＋1）＞ω，則將其誤差相對值狀態(tài)記為1，說明檢測結(jié)果是異常；

正常判定：對于下一個采樣數(shù)據(jù)與預(yù)測值的誤差的相對值，存在ε（k）≤ω，則將其誤差相對值狀態(tài)記為0，說明檢測結(jié)果是正常。

（1）記判定狀態(tài)空間為E ＝ ｛0，1｝。

（2）計算下一時刻數(shù)據(jù)點所處的狀態(tài)：設(shè)狀態(tài)空間 E ＝ ｛0，1｝的 轉(zhuǎn) 移 概 率 矩 陣 為P ＝，其中0＜λ，μ＜1，且λ＋μ≠1。（3）初始分布為π，有π0＝πdi＝（）0＝i＝1，2，…，n。

（4）根據(jù)設(shè)定的狀態(tài)劃分得到初始分布，同時根據(jù)前面得到的k步轉(zhuǎn)移概率為Pij（）k＝mij（）k／Mi，式中mij（）k為狀態(tài)Ei經(jīng)k步轉(zhuǎn)移后到達(dá)狀態(tài)Ej的次數(shù)，Mi為狀態(tài)Ei出現(xiàn)的次數(shù)，由于數(shù)據(jù)序列的最后狀態(tài)的轉(zhuǎn)向不明確，故計算Mi時要去掉數(shù)據(jù)序列中最末的一個數(shù)據(jù)；當(dāng)k＝1時，即為一步轉(zhuǎn)移概率Pij，其矩陣形式可記為

（5）由P（1）＝P（0）P1，考察P（1）中的n個值，若Pkj＝Pkl，則認(rèn)為下一時刻系統(tǒng)最有可能由狀態(tài)Ek轉(zhuǎn)向狀態(tài)El，即下一時刻最有可能處于狀態(tài)El。

（6）由P（2）＝P（1 ）P1，…，P （n）＝P（n－1）P1可知n時刻后系統(tǒng)最有可能所處的狀態(tài)。

4 算法仿真與分析

由于在無線傳感器網(wǎng)絡(luò)進(jìn)行監(jiān)測的過程中，傳感器節(jié)點會得到實時的監(jiān)測數(shù)據(jù)，對于k步轉(zhuǎn)移概率的應(yīng)用起到的作用是大范圍的預(yù)測，但不精確，為使無線傳感器網(wǎng)絡(luò)監(jiān)測的預(yù)測更加準(zhǔn)確，下述的仿真采用一步轉(zhuǎn)移概率進(jìn)行較為準(zhǔn)確的預(yù)測。

4.1 仿真環(huán)境

本文實驗在傳感器節(jié)點作為數(shù)據(jù)提供方、傳感器Sink節(jié)點作為接收方其處理能力一定的前提下，提供考慮預(yù)測的準(zhǔn)確性問題。仿真工具為Matlab 7.0，采樣間隔時間為600s。

4.2 仿真過程

（1）給出原始數(shù)據(jù)列d（0），如圖2所示。

Figure 2 Monitorng data圖2 監(jiān)測數(shù)據(jù)

（2）經(jīng)二次無偏灰色模型預(yù)測到預(yù)測值，如圖3所示。

Figure 3 Raw data prediction圖3 原始數(shù)據(jù)預(yù)測值

（3）求出預(yù)測值與采樣數(shù)據(jù)的誤差Δk，并計算誤差的相對值ε（）k，如圖4所示。

Figure 4 Original error relative value schematic diagram圖4 誤差相對值示意圖

（4）狀態(tài)劃分：誤差相對值ε（）k均值，ω＝8.02%；根據(jù)狀態(tài)劃分判定方法得到狀態(tài)空間E＝｛0，1｝，具體狀態(tài)如圖5所示。

Figure 5 State schematic diagram圖5 狀態(tài)示意圖

Table 1 State table表1 狀態(tài)表

（6）初始分布π＝ （π0， π1）＝ （0.6316，0.3684）。

（7）P（1）＝P（0）P1＝ πP1＝ （0.631 6，（8）maxPkj＝Pk1＝0.6316，所以下一個狀

j態(tài)是0，誤差相對值狀態(tài)記為0，說明檢測結(jié)果是在誤差范圍內(nèi)，則不發(fā)送狀態(tài)標(biāo)識。

4.3 仿真結(jié)果分析

通過二次無偏灰色模型對數(shù)據(jù)進(jìn)行預(yù)測的結(jié)果（如圖3所示）可以看出，曲線擬合趨勢與監(jiān)測數(shù)據(jù)趨勢大致相同，預(yù)測誤差較??；經(jīng)過仿真得到下一個時間點數(shù)據(jù)為＝46.987 8，而實際的采樣數(shù)據(jù)是d21＝47.352 6，根據(jù)誤差相對值的公式有誤差相對值的平均值ω進(jìn)行比較，有ε（21）＜ω，所以灰色馬爾科夫預(yù)測模型的驗證結(jié)果同實際預(yù)測結(jié)果相同，預(yù)測也是較為準(zhǔn)確的。仿真實驗基本上涉及整個周期采樣數(shù)據(jù)的各種數(shù)據(jù)，同時得到較大的壓縮比，對于能量十分有限的傳感器節(jié)點起到了節(jié)省能量的作用。但是，其中也有不足，從40 min到140min期間，由于數(shù)據(jù)波動大，使預(yù)測擬合偏離較大，可能是由于算法對原始數(shù)據(jù)弱化后減弱了波動趨勢，導(dǎo)致擬合存在誤差，還需要進(jìn)一步討論。綜上所述，采用二次無偏灰色馬爾科夫狀態(tài)判定的方法既可以得到較好的數(shù)據(jù)預(yù)測，也可以對環(huán)境的狀態(tài)進(jìn)行準(zhǔn)確的判定，還可以有效地減少整個網(wǎng)絡(luò)的數(shù)據(jù)傳輸量。

5 結(jié)束語

根據(jù)無線傳感器網(wǎng)絡(luò)特點，本文在其監(jiān)測環(huán)境中采取了狀態(tài)判定，提出了二次無偏灰色馬爾可夫預(yù)測模型。該模型與傳統(tǒng)的數(shù)據(jù)壓縮的本質(zhì)有所不同，它將灰色模型和馬爾可夫鏈模型的優(yōu)點結(jié)合起來，并進(jìn)行了改進(jìn)，提高了預(yù)測精度。同時，根據(jù)監(jiān)測的目的，只對判定的狀態(tài)標(biāo)識進(jìn)行傳輸，不需要在匯聚節(jié)點或用戶端對傳輸?shù)臄?shù)據(jù)進(jìn)行解壓縮，減少了能量消耗，對于延長整個網(wǎng)絡(luò)的生命周期起著關(guān)鍵性的作用且計算過程不復(fù)雜，非常適用于能量有限的傳感器節(jié)點。改進(jìn)的模型給出了狀態(tài)分類的判定方法，能夠按概率特性對狀態(tài)進(jìn)行合理區(qū)別，提高狀態(tài)預(yù)測的準(zhǔn)確度，大幅度降低數(shù)據(jù)的傳輸量。

［1］ Zimmermann M，Dostert K.Analysis and modeling of impulsive noise in broad－band line communications［J］.IEEE Transactions on Electromagnetic Compatibility，2001，44（1）：249－258.

［2］ Ephraim Y，William J J.An EM algorithm for Markov modulated Markov processes［J］.IEEE Transactions on Signal Processing，2009，57（2）：463－470.

［3］ Liao Rui－jin，Xiao Zhong－nan，Gong Jing，et al.Markov model for reliability assessment of power transformers［J］.High Voltage Engineering，2010，36（2）：322－328.（in Chinese）

［4］ Wang Xian，Niu Dong－xiao.Forecasting on competition ability of electric power resource based on Markov chain［J］.Modern Electric Power，2004，21（1）：94－97.（in Chinese）

［5］ Yi Hong.Methods to study of ship’s overall reliability universal model and ship reliability engineering［D］.Shanghai：Shanghai Jiaotong University，2003.（in Chinese）

［6］ Wang Li－xia，Xia Le－tian.The application in the prediction of stock market based on gray Markov chain model［EB／OL］.［2009－08－05］.http：／／www.paper.edu.cn.（in Chinese）

［7］ Xue Xun－guo，Liu Bao－xin，Li Bai－chuan.The application in the prediction of road accidents based on gray Markov chain model［J］.Chinese Journal of Ergonomics，2006，12（3）：26－28.（in Chinese）

［8］ Tang Na，Gui Yu－feng，Li Bao.Predict gas emiissing quantity of mining coal face wuth inproved Grey Markov model［C］∥The Fifth China Annual Conference on Uncertainty，2007：195－198.（in Chinese）

［9］ Sun Xiang.Wireless sensor network data flow model on semi－Markow chain［M］.Hebei：Hebei University of Engineering，2011.（in Chinese）

［10］ Zhang Xin，Ren Yong－tai，Wang Fu－lin，et al.Prediction of annual precipitation based on improved Grey Markov Model［J］.Mathematics in Practice and Theory，2011，41（11）：51－57.（in Chinese）

附中文參考文獻(xiàn)：

［3］ 廖瑞金，肖中男，鞏晶，等.應(yīng)用馬爾可夫鏈模型評估電力變壓器可靠性［J］.高電壓技術(shù)，2010，36（2）：322－328.

［4］ 王賢，牛東曉.基于馬爾可夫鏈的電力能源競爭力預(yù)測［J］.現(xiàn)代電力，2004，21（1）：94－97.

［5］ 易宏.艦船總體可靠性通用模型及艦船可靠性工程的方法研究［D］.上海：上海交通大學(xué)，2003.

［6］ 王禮霞，夏樂天.灰色—馬爾可夫鏈模型在股市預(yù)測中的應(yīng)用［EB／OL］.［2009－08－05］.http：／／www.paper.edu.cn.

［7］ 薛勛國，劉寶新，李百川.灰色馬爾可夫鏈在道路交通事故預(yù)測中的應(yīng)用［J］.人類工效學(xué)，2006，12（3）：26－28.

［8］ 唐娜，桂預(yù)風(fēng)，李寶.灰色馬爾可夫模型應(yīng)用于股指分析［C］∥第五屆中國不確定系統(tǒng)年會，2007：195－198.

［9］ 孫翔.基于半馬爾可夫鏈的無線傳感器網(wǎng)絡(luò)能耗模型研究［M］.河北：河北工程大學(xué)，2011.

［10］ 張鑫，任永泰，王福林，等.基于改進(jìn)灰色馬爾科夫模型的年降水量預(yù)測［J］.數(shù)學(xué)的實踐與認(rèn)識，2011，41（11）：51－57.