一種基于SPRR的鏈路質(zhì)量預(yù)測(cè)算法*

高澤鵬，程良倫*，胡 莘

(1.廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，廣州510006)2.廣東工業(yè)大學(xué)信息工程學(xué)院，廣州 510006)

無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量有限，通信通常采用低功率射頻信號(hào)。因此，容易受到周圍環(huán)境噪聲等干擾，造成信號(hào)的失真，通信鏈路的不可靠和波動(dòng)。在無線傳感器網(wǎng)絡(luò)中，如果數(shù)據(jù)包在低質(zhì)量的鏈路上進(jìn)行傳輸，會(huì)造成傳送失敗而導(dǎo)致數(shù)據(jù)包的重傳動(dòng)作，這不僅降低了網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性，同時(shí)也浪費(fèi)了節(jié)點(diǎn)中寶貴的能量，增加了能耗。因此，通過對(duì)鏈路質(zhì)量的預(yù)測(cè)，從而選擇穩(wěn)定的路徑，高質(zhì)量的鏈路進(jìn)行數(shù)據(jù)的傳輸在無線傳感器網(wǎng)絡(luò)中是非常重要的，不僅可以提高整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)吞吐率，降低節(jié)點(diǎn)的能耗，還可以延長(zhǎng)整個(gè)網(wǎng)絡(luò)的工作時(shí)間［1－2］。

預(yù)測(cè)技術(shù)在無線網(wǎng)絡(luò)中，已經(jīng)有很多方面的研究，譬如LMS和Kalman過濾器，神經(jīng)網(wǎng)、自回歸模型、自回歸滑動(dòng)平均以及分形自回歸求和滑動(dòng)平均模型(F－ARIMA)和小波模型(Wavelet)等［3－5］。但它們都建立在復(fù)雜的運(yùn)算處理上，而在能量和計(jì)算處理能力都有限的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)上，明顯不適用。文獻(xiàn)［6］只對(duì)RSSI和LQI的值進(jìn)行平均處理，忽略了鏈路的不對(duì)稱性;文獻(xiàn)［7］提出了基于LQI的鏈路質(zhì)量評(píng)估模型，但仍沒解決LQI原理上的不足;文獻(xiàn)［8］提出把幾個(gè)鏈路性質(zhì)指標(biāo)用于模糊算法當(dāng)中，但沒有給出具體的計(jì)算方法和公式。

本文對(duì)基于SPRR的預(yù)測(cè)算法進(jìn)行改進(jìn)和研究，第一節(jié)首先對(duì) LQI、RSSI、PRR、RNP這幾個(gè)鏈路質(zhì)量量度進(jìn)行原理上的分析和性能的比較。第二節(jié)運(yùn)用移動(dòng)窗口加權(quán)指數(shù)平(WMEWMA)對(duì)PRR量度進(jìn)行平滑化處理和其時(shí)效性的研究。第三節(jié)中，考慮到節(jié)點(diǎn)之間鏈路質(zhì)量的不對(duì)稱性，綜合鏈路上行SPRR和下行SPRR來計(jì)算出鏈路數(shù)據(jù)傳輸成功的期望傳輸次數(shù)A－ETC。最后，通過實(shí)驗(yàn)來驗(yàn)證分析該算法在穩(wěn)定性，平滑性，精確度上的效果。

1 鏈路質(zhì)量量度的比較分析

無線傳感器網(wǎng)絡(luò)中，鏈路質(zhì)量主要有以下幾個(gè)度量標(biāo)準(zhǔn)［9］:

RSSI在IEEE802.11標(biāo)準(zhǔn)中定義為是通信鏈路上的接收信號(hào)強(qiáng)度，因此，在一定的意義上能夠反映鏈路狀態(tài)。結(jié)合特定的芯片，如Chipcon CC1000，CC2420無線通信模塊中提供了信號(hào)強(qiáng)度的模擬值，只需通過ADC轉(zhuǎn)換便可獲得數(shù)字信號(hào)，其獲取相對(duì)容易，而且能耗低。但RSSI對(duì)收包率的變化并不敏感［10］，且背景噪聲較大的環(huán)境下，很難對(duì)當(dāng)前鏈路通信質(zhì)量做出準(zhǔn)確的估計(jì)。

(2)LQI(Link Quality Indicator)

LQI在IEEE802.15.4標(biāo)準(zhǔn)中定義為通信鏈路信噪比的估計(jì)值，Chipcon CC2420芯片中，對(duì)與每個(gè)接收包起始幀分隔符的8個(gè)比特進(jìn)行比特誤碼率的統(tǒng)計(jì)，所以，LQI實(shí)際為比特水平的度量標(biāo)準(zhǔn)。LQI只根據(jù)8比特來判斷整個(gè)數(shù)據(jù)包的接收情況，而且只統(tǒng)計(jì)接收到的數(shù)據(jù)包，那些在通信時(shí)傳輸失敗的數(shù)據(jù)包并沒有統(tǒng)計(jì)在內(nèi)，因此不能很準(zhǔn)確的反映鏈路質(zhì)量。

(3)RNP(Required Number of Packet)

RNP為衡量一個(gè)周期內(nèi)節(jié)點(diǎn)在成功接收數(shù)據(jù)包之前傳送和轉(zhuǎn)發(fā)此包的次數(shù)，即傳送和轉(zhuǎn)發(fā)數(shù)據(jù)包的個(gè)數(shù)與成功接收數(shù)據(jù)包之和的比值。RNP是在每個(gè)時(shí)間窗內(nèi)在發(fā)送節(jié)點(diǎn)處對(duì)數(shù)據(jù)包進(jìn)行統(tǒng)計(jì)，而沒有考慮到節(jié)點(diǎn)之間鏈路的方向問題。

(4)PRR(Packet Reception Ratio)

PRR是反映鏈路質(zhì)量最直觀的度量標(biāo)準(zhǔn)，其定義為周期內(nèi)節(jié)點(diǎn)成功接收數(shù)據(jù)包的個(gè)數(shù)占總發(fā)送次數(shù)的比例。PRR通過統(tǒng)計(jì)數(shù)據(jù)成功接收與失敗接收的情況來評(píng)估通信鏈路的質(zhì)量，在接收節(jié)點(diǎn)處需要一定量的采樣。

基于硬件的鏈路質(zhì)量量度RSSI和LQI其獲取簡(jiǎn)單方便，不用大量的計(jì)算，但是，它們的測(cè)量都存在缺陷，LQI和RSSI的測(cè)量都是建立在接收到的數(shù)據(jù)包的基礎(chǔ)上，而忽略了傳輸中接收和發(fā)送失敗的數(shù)據(jù)包，而且不能準(zhǔn)確細(xì)化地描述當(dāng)前鏈路質(zhì)量，只能大概的分出鏈路質(zhì)量的好和差，不能滿足路由協(xié)議對(duì)鏈路質(zhì)量準(zhǔn)確預(yù)測(cè)的要求。

基于軟件的鏈路質(zhì)量量度RNP和PRR都是通過統(tǒng)計(jì)數(shù)據(jù)包的方式來描述鏈路質(zhì)量的，RNP的統(tǒng)計(jì)在發(fā)送節(jié)點(diǎn)處，PRR則在接收節(jié)點(diǎn)處。其中，RNP在發(fā)送節(jié)點(diǎn)處統(tǒng)計(jì)，在接收節(jié)點(diǎn)成功接收之前傳送和轉(zhuǎn)發(fā)的數(shù)據(jù)包數(shù)目，即時(shí)間點(diǎn)是在接收節(jié)點(diǎn)確定的，這就造成了不能準(zhǔn)確確定接收節(jié)點(diǎn)在成功接收數(shù)據(jù)包之前是否有過轉(zhuǎn)發(fā)此數(shù)據(jù)包的過程。PRR對(duì)接收節(jié)點(diǎn)的接收包率進(jìn)行統(tǒng)計(jì)，而忽略了轉(zhuǎn)發(fā)中丟失的數(shù)據(jù)包。

綜上所述，基于硬件的鏈路質(zhì)量量度 LQI和RSSI的獲取簡(jiǎn)單方便，但是靈敏度太高，穩(wěn)定性差，加上對(duì)環(huán)境噪聲的變化不敏感，不適合單獨(dú)作為描述鏈路質(zhì)量的量度。基于軟件的鏈路質(zhì)量雖然在時(shí)效性上比LQI和RSSI稍差一點(diǎn)，但它們能比LQI和RSSI更準(zhǔn)確的描述鏈路質(zhì)量，也不需要進(jìn)行硬件的校正，通過后期計(jì)算處理可以克服原理上的不足。PRR與RNP相比，從原理上更直觀，沒有考慮轉(zhuǎn)發(fā)的數(shù)據(jù)，計(jì)算上相對(duì)簡(jiǎn)單。

本文采用PRR作鏈路質(zhì)量的量度，雖然PRR和以上的幾種量度一樣，都只能對(duì)當(dāng)前鏈路質(zhì)量進(jìn)行評(píng)估，不能很好的對(duì)鏈路質(zhì)量的變化趨勢(shì)進(jìn)行預(yù)測(cè)，文章的第2、3節(jié)將基于PRR的歷史數(shù)據(jù)，通過WMEWMA的平滑化處理和實(shí)效性的研究，加以對(duì)鏈路不對(duì)稱性的考慮，來對(duì)鏈路質(zhì)量變化趨勢(shì)的預(yù)測(cè)算法進(jìn)行研究。

2 平滑化處理和時(shí)效性研究

2.1 PRR的平滑化處理

PRR是每個(gè)周期內(nèi)的統(tǒng)計(jì)值，代表了周期內(nèi)鏈路的情況。但是可以看出PRR值是離散的，相鄰兩個(gè)值之間可能會(huì)出現(xiàn)很大的變化。如果周期設(shè)定較短，PRR值就會(huì)呈現(xiàn)很大的波動(dòng)，這會(huì)對(duì)上層協(xié)議策略判斷的造成困難，降低了對(duì)鏈路質(zhì)量預(yù)測(cè)的精度。因此，對(duì)PRR值進(jìn)行平滑化處理變得非常重要，PRR值變化越穩(wěn)定、越平滑，對(duì)鏈路質(zhì)量變化的趨勢(shì)判斷就越準(zhǔn)確，越有利于上層路由協(xié)議策略的執(zhí)行。

經(jīng)過平滑化處理的PRR，我們可以稱為SPRR(Smooth PRR)。本文采用移動(dòng)窗口指數(shù)加權(quán)平均法(WMEWMA，Window Mean Exponentially Weighted Moving Average)來對(duì)PRR進(jìn)行平滑化處理。

移動(dòng)窗口指數(shù)加權(quán)平均法(WMEWMA)通過迭代的方式進(jìn)行計(jì)算，時(shí)刻n的預(yù)測(cè)值SPRRn僅與上一時(shí)刻的預(yù)測(cè)值SPRRn－1和當(dāng)前時(shí)刻測(cè)量值PRRn有關(guān)，計(jì)算公式如下:

運(yùn)用WMEWMA的方法，就可以通過歷史的鏈路質(zhì)量預(yù)測(cè)值SPRRn－1和當(dāng)前鏈路質(zhì)量值PRRn，計(jì)算出下一時(shí)刻的鏈路質(zhì)量預(yù)測(cè)值SPRRn。這種迭代的方式與歷史數(shù)據(jù)均值法相比，降低了存儲(chǔ)需求。除了需要存儲(chǔ) SPRRn－1、PRRn、w和 α 外不需要額外的存儲(chǔ)變量。其中w表示時(shí)間窗口為多少個(gè)PRR采樣數(shù)據(jù)的時(shí)間，α為權(quán)值。同時(shí)，該方法預(yù)測(cè)值的穩(wěn)定性與參數(shù)w和α有關(guān)，通過改變w和α的參數(shù)值，就可以使預(yù)測(cè)值的變化更加平滑穩(wěn)定。

WMEWMA采用了移動(dòng)窗口，預(yù)測(cè)值SPRRn只跟窗口內(nèi)測(cè)量值有關(guān)，充分反映了鏈路質(zhì)量隨時(shí)間推移的變化趨勢(shì)，優(yōu)于歷史數(shù)據(jù)均值的方法;WMEWMA對(duì)不同時(shí)間的測(cè)量值SPRRn給予不同的權(quán)值，比移動(dòng)窗口平均法更能體現(xiàn)時(shí)效性;WMEWMA只需要存儲(chǔ)4個(gè)數(shù)據(jù)，遠(yuǎn)比加權(quán)移動(dòng)平均法的存儲(chǔ)量少。顯然，WMEWMA在穩(wěn)定性，存儲(chǔ)量和時(shí)效性方面都比其他3種方法性能更優(yōu)秀。

圖1為PRR的鏈路質(zhì)量預(yù)測(cè)曲線，圖2為SPRR(w=30，α=0.6)的預(yù)測(cè)曲線。從圖1、圖2可以看出，PRR對(duì)于鏈路質(zhì)量的實(shí)時(shí)測(cè)量變化很大，但是，在均值上來說，比較接近鏈路質(zhì)量的真實(shí)值，而經(jīng)過平滑化處理的SPRR比PRR更加的穩(wěn)定準(zhǔn)確，能很好的預(yù)測(cè)無線傳感器網(wǎng)絡(luò)中鏈路的質(zhì)量。這證明采用WMEWMA對(duì)PRR平滑化處理的效果明顯可靠，同時(shí)更接近鏈路質(zhì)量當(dāng)前時(shí)刻的真實(shí)值。

圖1PRR

圖 2 SPRR(w=30，α=0.6)

2.2 SPRR的時(shí)效性研究

上文提到WMEWMA方法的穩(wěn)定性與w和α有關(guān)，下面對(duì)WMEWMA的時(shí)效性進(jìn)行進(jìn)一步的研究。

估計(jì)所需的歷史信息都體現(xiàn)在 SPRRn－1中，其中α∈(0，1)負(fù)責(zé)控制歷史值對(duì)當(dāng)前值的貢獻(xiàn)度，可以用α來調(diào)節(jié)預(yù)測(cè)算法對(duì)鏈路質(zhì)量變化的靈敏度。如果α增大，SPRRn－1對(duì)SPRRn的貢獻(xiàn)度也會(huì)增大，預(yù)測(cè)值SPRRn的變化就會(huì)變平穩(wěn)，但實(shí)時(shí)性會(huì)降低;如果 α 減小，SPRRn－1對(duì) SPRRn的貢獻(xiàn)度也會(huì)減小，預(yù)測(cè)值SPRRn的變化就會(huì)變靈敏，實(shí)時(shí)性得到加強(qiáng)。同時(shí)，移動(dòng)窗口大小w的設(shè)定也會(huì)對(duì)SPRRn影響，窗口采樣個(gè)數(shù)過少，對(duì)鏈路質(zhì)量的預(yù)測(cè)就越靈敏，精度越低;窗口采樣個(gè)數(shù)過多，歷史樣本在預(yù)測(cè)中的貢獻(xiàn)度越大，不能體現(xiàn)出預(yù)測(cè)算法的實(shí)時(shí)性。

圖3為 SPRR(w=30，α=0.5)時(shí)的預(yù)測(cè)曲線，圖4為SPRR(w=30，α=0.8)時(shí)的預(yù)測(cè)曲線。明顯可以看出，當(dāng)α=0.5時(shí)，算法對(duì)鏈路質(zhì)量的變化比α=0.8時(shí)的敏感，時(shí)效性更強(qiáng);但是在靈敏的同時(shí)，相對(duì)的波動(dòng)較大，在精度上比α=0.8時(shí)差。

圖3 SPRR(w=30，α=0.5)

圖4 SPRR(w=30，α=0.8)

圖5為SPRR(w=100，α=0.6)時(shí)的預(yù)測(cè)曲線?？梢钥闯觯阪溌焚|(zhì)量變化時(shí)，預(yù)測(cè)曲線相對(duì)比較滯后。與圖2相比，實(shí)時(shí)性較差。

文獻(xiàn)［11］中指出，α 的取值范圍在(0.5，0.8)內(nèi)，其中α=0.6，且移動(dòng)窗口內(nèi)有30個(gè)采樣值時(shí)平滑化得效果最好。

圖 5 SPRR(w=100，α=0.6)

3 鏈路的不對(duì)稱性

文獻(xiàn)［12］已有實(shí)證研究表明，通信鏈路中存在不對(duì)稱性，主要表現(xiàn)為發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的鏈路質(zhì)量是不一致的。導(dǎo)致這個(gè)問題的主要原因是因?yàn)楣?jié)點(diǎn)的硬件電路有差異，從而發(fā)射功率不相同，還有各自剩余能量不同，進(jìn)一步增大了數(shù)據(jù)發(fā)送接收工作在節(jié)點(diǎn)之間的差異，同時(shí)外圍環(huán)境也會(huì)增加鏈路的不對(duì)稱性。

但是，現(xiàn)有的幾個(gè)鏈路質(zhì)量量度都只在單方面描述的，如RNP在發(fā)送節(jié)點(diǎn)處進(jìn)行統(tǒng)計(jì)，用上行鏈路的質(zhì)量代表了節(jié)點(diǎn)之間雙向的鏈路質(zhì)量，PRR和SPRR在接收節(jié)點(diǎn)處進(jìn)行統(tǒng)計(jì)，用下行鏈路的質(zhì)量代表了節(jié)點(diǎn)之間雙向的鏈路質(zhì)量，RSSI、LQI也是如此。這樣就會(huì)出現(xiàn)接收節(jié)點(diǎn)成功接收到數(shù)據(jù)包后，由于下行鏈路質(zhì)量較差，使得確認(rèn)幀無法傳回發(fā)送節(jié)點(diǎn)，從而導(dǎo)致這次的數(shù)據(jù)傳輸失敗，浪費(fèi)了節(jié)點(diǎn)的能量，失敗重傳、轉(zhuǎn)發(fā)也降低了網(wǎng)絡(luò)的實(shí)時(shí)性。

針對(duì)鏈路的不對(duì)稱性，本節(jié)對(duì)上面的SPRR做出以下的改進(jìn)。首先定義一次成功的數(shù)據(jù)收發(fā)過程是發(fā)送者向接收者發(fā)送數(shù)據(jù)幀，接收者對(duì)所接收的數(shù)據(jù)幀返回ACK，只有當(dāng)發(fā)送者成功接收到接收者返回的ACK時(shí)，才算發(fā)送成功。現(xiàn)定義SPRRup為鏈路的上行包接收率，SPRRdown為鏈路的下行包接收率，SPRRu－d為鏈路的雙向包接收率。

設(shè)A－ETC(ACK－Expected Transmission Count)為兩節(jié)點(diǎn)之間收發(fā)成功傳輸次數(shù)的數(shù)學(xué)期望值。

其中k表示數(shù)據(jù)傳輸次數(shù)，S(k)表示經(jīng)過k次傳輸才成功一次的概率，所以

將式(3)代入式(2)得出

由式(8)、式(9)可以得出式(10)

將式(12)代回式(5)，得

∵ (1－SPRRu－d)∈(0，1)，

∴ (1－SPRRu－d)k～0，k×(1－SPRRu－d)k～0

能夠得出公式:

在窗口采樣后得出的PRR，經(jīng)過平滑化處理得到SPRR，之后換算成A－ETC值作為節(jié)點(diǎn)之間鏈路質(zhì)量的一個(gè)直觀量化表示方式。A－ETC值不僅綜合考慮了鏈路的不對(duì)稱性，也具備了SPRR的實(shí)時(shí)性和平滑性，使得其可以成為上層路由協(xié)議策略判斷的有力依據(jù)。

圖6 為 A－ETC(w=30，α=0.5)的預(yù)測(cè)曲線，圖7為 A－ETC(w=30，α=0.6)的預(yù)測(cè)曲線，其中 A－ETC的上行下行w和α值均相同。從圖6、圖7的比較中可以看出，在(100，200)的時(shí)間段里，w值同為30的時(shí)候，α=0.5的A－ETC預(yù)測(cè)曲線波動(dòng)的幅值比α=0.6的A－ETC預(yù)測(cè)曲線的大，靈敏度較強(qiáng)。從曲線的整體上來說，α=0.6的A－ETC預(yù)測(cè)曲線更穩(wěn)定，更接近真實(shí)值，更能表現(xiàn)出鏈路質(zhì)量的變化趨勢(shì)。這也驗(yàn)證了第2節(jié)中相同w值時(shí)，α=0.6比α=0.5的SPRR更穩(wěn)定的結(jié)論。

圖6 A－ETC(w=30，α=0.5)

圖7 A－ETC(w=30，α=0.6)

4 結(jié)語

本文通過對(duì) LQI、RSSI、PRR、RNP 這幾個(gè)鏈路質(zhì)量的量度進(jìn)行比較分析，選擇了PRR量度來描述鏈路質(zhì)量，運(yùn)用移動(dòng)窗口加權(quán)指數(shù)平均法(WMEWMA)對(duì)PRR量度進(jìn)行平滑化處理，得出的SPRR可以有效的對(duì)鏈路質(zhì)量進(jìn)行預(yù)測(cè)，從本文仿真實(shí)驗(yàn)的分析比較中可以看出，SPRR比PRR在穩(wěn)定性和時(shí)效性有了很大的改進(jìn)?？紤]到節(jié)點(diǎn)之間鏈路質(zhì)量的不對(duì)稱性，綜合鏈路上行SPRR和下行SPRR來計(jì)算出鏈路數(shù)據(jù)傳輸成功的期望傳輸次數(shù)A－ETC，得出更能準(zhǔn)確的表現(xiàn)出鏈路質(zhì)量變化趨勢(shì)的預(yù)測(cè)算法。從實(shí)驗(yàn)結(jié)果表明，該基于SPRR的鏈路質(zhì)量預(yù)測(cè)算法相比原來的PRR量度，在穩(wěn)定性、實(shí)時(shí)性、精確度上都有很大的提高。

［1］SrinivasanK，Kazandjieva M A，Agarwal S，et al.The Betafactor:Measuring Wireless Link Burstiness［C］//SenSys’08:Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems，2008:29－42.

［2］Becher A，Landsiedel O，Wehrle K.Towards Short-Term Wireless Link Quality Estimation［J］//Proceedings-Real-Time Systems Symposium，2009:227－237.

［3］孫偉，金心宇，張昱，等.基于預(yù)測(cè)的WMSNs目標(biāo)跟蹤協(xié)作處理方法［J］.傳感技術(shù)學(xué)報(bào)，2009，22(8):1175－1181.

［4］楊彩，賈松潔，等.基于ARMA的WSN流量預(yù)測(cè)模型［J］.計(jì)算機(jī)應(yīng)用技術(shù)，2009，26(6):75－77.

［5］李捷，劉先省，韓志杰.基于ARMA的無線傳感器網(wǎng)絡(luò)流量預(yù)測(cè)模型的研究［J］.電子與信息學(xué)報(bào)，2007，29(5):1224－1227.

［6］孫佩剛，趙海，羅玎玎，等.無線傳感器網(wǎng)絡(luò)鏈路通信質(zhì)量測(cè)量研究［J］.通信學(xué)報(bào)，2007，28(10):14－22.

［7］朱劍，趙海，張希元，等.基于LQI量度的無線鏈路質(zhì)量評(píng)估模型［J］.東北大學(xué)學(xué)報(bào)，2008，29(9):1262－1265.

［8］Baccour N，Koubaa A，Youssef H，et al.A Fuzzy Link Quality EstimatorforWireless Sensor Networks［C］//7th European Conference on Wireless Sensor Networks(EWSN 2010)，2010:240－255.

［9］Baccour N，Koubaa A，Ben Jamaa M，et al.A Comparative Simulation Study of Link Quality Estimators in Wireless Sensor Networks［C］//17th IEEE/ACM International Symposium on Modelling，A-nalysis and Simulation ofComputerand Telecommunication Systems(MASCOTS)，2009:301－310.

［10］李燕君，王智，孫優(yōu)賢.無線傳感器網(wǎng)絡(luò)的鏈路分析與建模［J］.傳感技術(shù)學(xué)報(bào)，2007，20(8):1846－1851.

［11］Woo A，CullerD.Evaluation ofEfficientLink Reliability Estimators for Low-Power Wireless Networks［D］.EECS Department，University of California，Berkeley，2003.

［12］Du J，Shi W，Sha K.Asymmetry-Aware Link Quality Services in Wireless Sensor Networks［C］//Proceedings-Embedded and U-biquitous Computing-International Conference，2005:227－237.