基于模糊區間識別的鏈路評估器研究

（東北大學 信息科學與工程學院 遼寧省嵌入式技術重點實驗室， 沈陽 110004）

摘 要：研究發現基于有限數據包統計出的收包率并不能準確體現當前節點工作的區間，而鏈路丟包特性在無須海量數據的前提下卻可以比較精確地體現節點工作區間。通過模糊集理論可以實時地判斷出當前工作區間，對不同區間內的丟包事件不一樣的加權可以合理地反映出鏈路狀況。研究結果顯示，基于模糊區間識別的鏈路評估器能夠準確反映當前鏈路狀況，更具實用性。

關鍵詞：無線傳感器網絡；鏈路評估器；模糊區間識別；丟包特性

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2009)01029405

Research of link estimator based on fuzzy region recognition

ZHU Jian，ZHAO Hai，XU Jiuqiang，LI Yan

(Liaoning Provincial Key Laboratory of Embedded Technology， School of Information Science Engineering， Northeastern University，Shenyang 110004， China)

Abstract:The study found that the packet reception rate counted from limited packets could’t describe which region was the nodes in.While the characteristic of packets loss could describe the regions well based on a few packets.This paper identified the regions by fuzzy theory realtimely， and differently weighted in packets loss different regions. The results show that fuzzy region recognition based link estimator can describe the link quality well， and has more practicability.

Key words:wireless sensor networks;link estimator;fuzzy region recognition;packet loss characteristic

無線傳感器網絡[1]是一種全新的計算模式，它集成了傳感器、微電、無線通信和分布式信息處理等技術。在傳感器網絡中，鏈路層的質量評估直接影響到拓撲控制和通信協議的設計。隨著傳感器網絡規模的增加，會出現兩個重要的問題：a）鏈路變化頻繁導致連接失效。低功率的無線射頻通信由于信道噪聲、多跳路由、環境變化、節點移動、失效等因素，有高度的不穩定性。鏈路評估器要足夠靈敏，能及時檢測出無效鏈路，更新路由表；同時，在鏈路變化過渡過程中，網絡重新穩定的時間要盡量短，這就要求鏈路評估器能迅速達到穩定。如何在靈敏與穩定之間達到平衡是一個需要折中考慮的問題。b）能量和資源受限。傳感器節點由電池供電，能量受限，同時計算能力和存儲量也很有限。在設計基于鏈路質量的路由協議前，要選擇適當的傳感器網絡的鏈路質量評估器，以避免大量復雜的計算。

當前比較典型的鏈路評估器EWMA[2](指數加權移動平均)是一種基于鏈路收包率[3]的鏈路評估器，在此基礎上延伸出一系列基于收包率的評估器如FlipFlop EWMA、TWMA、FFPLSI、WMEWMA。由于收包率在實際應用中變化非常劇烈，單純依照收包率對鏈路進行評估會導致其結果并不可用。本文采用模糊區間識別[4]法使鏈路評估器更具實用性、合理性。

本文在研究無線鏈路的丟包特性的基礎上提出一種新的鏈路區間劃分方法，并運用模糊數學方法對鏈路區間建模，進而提出一種基于鏈路區間的加權思想，避免了傳統鏈路評估器需要的海量數據。

1 EWMA鏈路評估器

在本文經常用到的一些參數與術語如下：

M事件是數據包到達節點接收端構成的事件。

T 事件是定時器到達設定時間構成的事件。

R為節點的發包速率。

鏈路評估器工作模型如圖1所示。從圖1可以看出鏈路評估器的輸入包括兩部分，即M事件和T事件。每一個數據包包含一個序列號，當發生數據包丟失后，將不會觸發M事件，但當下一個數據包被接收到時，通過序列號可以判斷出有多少個數據包發生丟失。實際應用中很有可能出現節點丟失事件，即當接收節點接收到最后一個數據包后再也沒有接收到發送節點發出的數據包。這樣M事件處理方法就不適用了，它無法判斷整個過程中發生的丟包次數。為了彌補這一缺陷，鏈路評估器必須同步使用T事件，即每隔一個時間間隔t就會統計一次丟包數。設丟包次數為N，在該時間間隔內接收的數據包數為S，則有N=Rt-S。

通過上述可知在任一M事件或T事件中，t時間內的平均收包率p(t)可以被計算出。傳統鏈路評估器認為在同一理想環境下p(t)是穩定的數值，從而可以通過p(t)判斷當前鏈路是否可用。當環境發生改變，如兩節點距離發生變化，則p(t)會從一個穩定值躍變到另一個穩定值，如圖2所示。

僅按收包率來判斷鏈路質量存在不足，當鏈路中節點突然丟失，則收包率理論上應該立即為0。但由于p(t)是一個統計值，這就會導致在節點丟失后，收包率會從一個穩定數值緩慢變化為0，這樣遲鈍的反映會對路由的選擇造成嚴重錯誤指導。由此引出兩個概念：a）進入穩定時間，是指當收包率發生躍變時，從躍變發生那一刻到收包率進入下一個穩定值的±ε%內且不再超出的這段時間。b）突破穩定時間，是指當收包率發生躍變時從躍變發生那一刻到收包率首次突破當前收包率±ε%的這段時間。本文設ε＝10。進入穩定時間與突破穩定時間直接決定著鏈路評估器對實際鏈路變化反映的穩定性與靈敏性。

為了更好地權衡鏈路評估器的穩定性和靈敏性[5]，很多鏈路評估器選擇了EWMA算法。設移動窗口為n，則在k時間點一個窗口內的收包率評估值為

k=（1/n）ki=k-n+1pi(1)

根據移動平均指數加權[6]的思想則有

k+1=1/(n+1)k+1i=k-n+1pi=1/(n+1)（pk+1+nk）=[1/(n+1)]pk+1+[n/(n+1)]k(2)

回退一個時間點則有

k=(1-α)pk+αk-1，α=n/(n+1)(3)

從式（3）中不難看出，若想計算出k時間點的收包率評估值，只需知道上個時間點的收包率評估值與k時間點的收包率。

設基于序列號得到的丟包數為m，k為基于發包速率預測的丟包數，L為綜合預測丟包數，L=max(m-k，0)。本文設k=0，若連續丟失L個數據包則意味著連續L個pk=0，由式(3)可知

k=αLk-1，α=n/(n+1)(4)

上述算法即為EWMA算法，其主要思想是對最近的評估值加大重視程度，通過窗口大小調節鏈路評估器的靈敏性與穩定性。所以最近鏈路的評估值k-1對當前時刻鏈路評估結果至關重要，本文將詳細討論如何科學地計算它。

2 無線鏈路丟包特性研究

21 實驗環境

本文硬件平臺是MicaZ節點。MicaZ節點是由Crossbow公司生產的無線傳感器節點，它的通信模塊CC2420[7]具有強大的通信功能，豐富的資源讓本文的實驗更加完善；它的核心是ATmega128[8]，是一款低功耗、高速率、功能全的處理器。

本文軟件平臺是MANTIS[9]嵌入式操作系統，它能夠很好地支持點對點通信。該系統完全由C語言寫成，本文在其之上用C語言編程實現實驗。選擇地點為空曠操場，周圍無射頻信號干擾源。

22 無線鏈路丟包特性

傳統的鏈路評估器認為收包率在同一理想環境下是穩定的，如圖2所示。收包率總在不同距離上穩定在一個值左右。但實際無線鏈路的特性不是這樣的。無線鏈路的丟包主要是受電磁波能量強弱影響，RSSI[10](接收信號強度指示)可以很好地反映電磁波能量。本文在不同的距離點上測試RSSI值500次，算出其方差得出圖3。從圖3中可看出，在距離為3 m內時RSSI變化很小；當距離達到3 m后RSSI方差比較大而且不穩定，這說明在3 m后RSSI變化幅度開始增大。所以隨著距離增加丟包率應該越來越不穩定，不可能穩定在一個值上。

為了更加清晰地看出無線鏈路的丟包特性，本文進行了實驗。實驗步驟如下：

a）測試距離為10 m，每一米上連續傳輸5 000個數據包，記錄被成功接收的數據包序列號，然后計算出丟失數據包的序列號。

b）統計丟失數據包的序列號，連續丟失n個數據包計為1次丟包事件。

c）一共發生的丟包事件次數m。

d）統計n∈(0，10)，(10，50)，(50，100)，(100，300)，(300，600)的丟包事件次數m1，m2，m3，m4，m5。

e）計算每個距離點上的mi/m值，i∈[1，5]。

f）作出mi/m值與距離的關系表(表1)。

從圖4可以看出，距離在4 m內幾乎無大規模連續丟包事件發生；當距離達到4 m后開始出現連續丟包，在4~8 m內，連續丟失的數據包數在0～10和10～50內的丟包事件占主要地位；8 m后連續丟包數在0～10內的丟包事件發生次數變小，連續丟包數在10～50內的丟包事件基本持平，連續丟包數在50以上的大規模連續丟包事件的出現頻率逐步上升，連續丟失300以上數據包的事件發生頻率明顯上升。

通過反復實驗，本文得出結論：a)無線鏈路中的丟包是連續的，即一旦出現丟包通常是連續丟失n個數據包。b)無線鏈路中的數據包丟失存在特點，即隨著距離增加小規模連續丟包事件發生頻率逐步變??；大規模連續丟包事件發生頻率逐步上升。c)多次實驗得出mi/m值基本一致，即無線鏈路的連續丟包特點在相同距離點上比較穩定。

對比于傳統的鏈路分析方法，從無線鏈路的丟包特點來觀察無線鏈路質量，要比從收包率觀察鏈路質量更加穩定和客觀。為了對比說明，本文所做的收包率與距離的變化關系如圖5所示。無線鏈路可以劃分為三個區［11］，即優質區、過渡區和劣質區。從圖5可以看出，距離4 m內的鏈路質量良好，收包率幾乎為1；在4～8 m內收包率變化非常不穩定，忽大忽小；8 m后進入劣質區，此區內的收包率幾乎為0。

由于收包率是統計值，統計量不可能無限大，在實際應用中，過渡區內的收包率仍然可以達到1或為0，這樣會導致基于收包率的區間劃分沒有意義。

結合圖4、5可以看出，在優質區內幾乎無丟包事件發生；在過渡區內由于丟包是連續的，在統計收包率時可能出現收包率忽大忽小，如節點每次發送1 000個數據包，統計窗口為1 000，在當前時刻統計的收包率為1，但是下一時刻可能連續丟失500個數據包，則統計的收包率為0.5。由于無線鏈路的丟包是連續的，這樣導致了無線鏈路的收包率在非優質區是不穩定的，從而造成了圖5的結果。在劣質區內連續丟包數通常很大，這樣在有限的統計窗口內，收包率反而會穩定在一個很小的數值上，其實此時的無線鏈路只能偶爾收到幾個數據包。所以圖5其實是圖4的一個必然結果，利用無線鏈路的丟包特性可以看到無線鏈路的本質，加上該特性比較穩定，在鏈路評估中更具應用價值。

23 傳統鏈路評估器的不足

通過22節分析可以看出無線鏈路的丟包特性。為了看出傳統鏈路評估器的不足，本文采用EWMA鏈路評估器實驗對實際鏈路進行了測試，設置窗口為350，結果如圖6所示。2 min內兩節點的距離很近，這時鏈路評估器的評估結果比較穩定為1；2～4 min內將距離增加到8 m，鏈路評估器的結果開始劇烈變化；4～6 min內將距離變為4 m；6～8 min內將距離變為6 m；8～10 min內將距離變為3 m。2 min后圖6顯示的評估結果幾乎不可用，實際路由選路時頻繁地改變路由可能會使整個無線網絡崩潰。

為什么EWMA鏈路評估器會出現這種結果？式(2)中EWMA窗口為n，pi為當前收包率，若收到則為1；若沒被接收到則為0。所以EWMA鏈路評估器是計算一個窗口內的統計收包率，然后將其作為下一時刻收包率的參考值。式(4)表明，EWMA的最終評估結果是完全基于統計收包率的。以上研究表明，由于無線鏈路的丟包是連續的，窗口內的收包數可能忽大忽??；而固定的窗口又導致收包率會忽大忽小，可能當前時刻窗口內的數據包全被接收，而緊鄰的100個數據包全部丟失，這樣就會導致在很短的事件內，收包率從1降到0.7，從而造成圖6中的鏈路評估結果。

在任何無線鏈路區間內，僅僅依靠公平地統計收包率對鏈路進行評估既不科學，也毫無意義。若窗口無窮大，則可以通過EWMA來對鏈路進行評估，因為基于無窮大的統計基數得出的收包率能反映無線鏈路的真實狀態；但是無線傳感器網絡資源受限，能夠承受的統計基數很小，基于小統計基數得出的收包率是不能真實反映鏈路的真實狀態的。所以本文從無線鏈路的物理特性著手，應用模糊識別理論對無線鏈路進行數學模型的建立，從而使節點在很小的統計基數基礎上能夠客觀地對實際鏈路質量進行評估。

3 模糊區間識別方法

實際鏈路中各個區間的特性存在很多元素，僅僅依賴于任何一個元素進行區間劃分是不科學的。針對這一特點本文采用模糊集理論解決區間劃分這一問題。

31 最大值、最小值貼近度

設A、B為給定論域U上的兩個模糊子集，u1， u2，…，un是U中n個待選對象，則A、B的最大值、最小值貼近度定義如下：

(A，B)=ni=1[μA(ui)∧μB(ui)]/ni=1[μA(ui)∨μB(ui)]（5）

式中：μA(ui)、μB(ui)為ui對模糊子集A、B的隸屬度。

32 擇近原則

式(8)中：Ri為第i類型評價指標構成的模糊關系。

同理，利用上述方法可建立起已知工況對評價指標集各功能的要求，從而得到模糊關系B，用矩陣表示為

B=β1β2βm（9）

式中：βj(j=1，2，…，m)為已知工況對評價指標集各功能的隸屬度，且滿足以下關系：

mj=1βj=1（10）

用最大值、最小值貼近度公式表示為

(Ri，B)=nj=1(rij∧βj)/

nj=1(rij∨βj) (i=1，2，…，n)（11）

計算各類型對所給工況的貼近度。比較各貼近度的值，選取最大值所對應的類型，即為最佳類型。



4 區間識別在鏈路區間劃分中的應用

41 類型集的確定

無線鏈路分為優質區、過渡區和劣質區，則無線鏈路的類型集為

T={T1，T2，T3}={優質區，過渡區，劣質區}（12）

42 評價指標集的確定

評價分區特性的指標如下：P1為較小規模連續丟包；P2為小規模連續丟包；P3為中等規模連續丟包；P4為大規模連續丟包；P5為較大規模連續丟包。以上指標構成評價指標集:

P={P1，P2，P3，P4，P5}（13）

若距離繼續增加則連續丟包數目大幅度增加，而距離比較近時距離的增加只能導致連續丟包數目小幅度變化，所以分區特性指標與連續丟包數不應該呈線性關系。本文選定較小規模連續丟包為連續丟包數在0～10；小規模連續丟包為連續丟包數在10～50；中等規模連續丟包為連續丟包數在50～100；大規模連續丟包為連續丟包數在100～300；較大規模連續丟包為連續丟包數在300～600。

43 各區間對評價指標的模糊關系矩陣

42節將各分區的評價指標分為五個等級，即較小規模、小規模、中等規模、大規模、較大規模。結合圖4、5可以看出優質區在0～3 m內；過渡區在4～7 m內；劣質區在8 m以外。事實上到10 m時已經幾乎接收不到數據包了。

設F(x，y)為x距離點上連續丟包數在y范圍內的事件發生次數占據總丟包事件次數的比重，則優質區間的分區特性指標計算公式如下：

Pi優質=3x=1F(x，yi)/3，Pi過渡=7x=4F(x，yi)/4，Pi劣質=10x=8F(x，yi)/3（14）

其中i∈[1，5]，其值對應于連續丟包數在范圍0～10、10～50、50～100、100～300、300～600內的事件。結合式（14）與表1，可得出分區特性指標，如表2所示。

d）結合式（11）（15）（16）計算出(Ri，B)值，選取最大(Ri，B)值對應的區間類型為當前窗口所在的區間類型。

e）設置一個數組prr[L]，若第i個數據包被成功接收則prr[i]=1，否則prr[i]=0。針對不同的區間對prr[i]進行不同的加權，設優質區、過渡區、劣質區對prr[i]=0的加權為α、β、χ，設N(prr[i]=0)為窗口內丟失的包數，結合式（2）有

k=[L-xN(prr[i]=0)]/L(17)

其中：x∈{α，β，χ}，k≥0。

f）利用式（4）進行EWMA運算。

步驟e）中的加權系數將對鏈路評估器的穩定性、靈敏性存在一定的影響，針對具體應用可以選擇適當的加權系數，本文實驗中選擇α＝0.1，β=0.8，χ=1.6。從算法可以看出整個計算流程中無循環、無指數對數運算，所以計算復雜度比較低。隨著硬件設備的飛速發展，節點的計算能力大大增強，一些簡單運算花費的時間很少；而無線通信中能量消耗主要集中在發送接收數據時，少量的程序運算幾乎不會造成什么能量消耗。

5 結果分析

51 存儲空間分析

EWMA算法主要的存儲空間需求在于窗口長度：窗口長則進入穩定時間、突破穩定時間長，存儲空間需求大；窗口小則穩定時間、突破穩定時間短，存儲空間需求小。對于路由選擇應用來講，頻繁地改變拓撲結構所需代價非常巨大，所以EWMA窗口需要很大才能使鏈路評估結果可用，如圖6中顯示的結果，窗口為350時其結果幾乎不可用。若繼續增加窗口則會帶來進入穩定時間、突破穩定時間變長而評估結果仍然不理想，這些矛盾使得EWMA算法左右為難。

FEWMA主要是考慮丟包的特點而不需要太大的數據量，只需要窗口可以容納樣本就可以。從圖4中可以看出最大樣本是300～600，只要窗口大于300就可以建立模糊關系從而進行區間識別，所以在FEWMA實驗中窗口被設置為350。相比于EWMA而言，FEWMA的窗口是節約而有效的。

52 進入穩定、突破穩定時間分析

無線傳感器網絡中資源非常有限，存儲空間較小，所以窗口不能選擇太大。而一個較小的窗口內的統計收包率是不可信的，所以本文在現有的EWMA算法上進行了改進，得到FEWMA鏈路評估器。為了分析算法對進入穩定時間與突破穩定時間的影響，本文對各段穩定值進行仿真，設0～9.5、9.5～175、175～21、21～26.5、26.5～30 min內的收包率穩定值分別為2.63%、46.57%、83.40%、28.22%、91.18%。收包率在9.5 min時發生躍變，由于EWMA中k-1是依賴于一個窗口內收包數的統計值，當躍變發生時收包數是一個一個地增加的，收包率不能立刻達到46.57%，需要一段時間才能進入46.57%(1±10%)。當在17.5 min時收包率再次發生躍變，同理可知，收包率若想超過46.57%(1±10%)仍需要一段時間，它也不可能瞬間變化成83.40％，由此產生了進入穩定時間。

FEWMA算法中進入穩定時間與突破穩定時間主要受分區特性指標的影響。假設窗口內丟失一個數據包，則由加權算法可知，該數據包對k-1影響很小。與此類似，只要丟包數不使模糊區間識別結果發生改變，則最終k-1值均會比較穩定；一旦區間識別結果發生改變，丟包的權重立刻改變，這就會導致k-1立刻改變。所以對FEWMA而言進入穩定時間與突破穩定時間主要取決于區間識別結果改變所需要的時間，而與窗口大小關系不大，這樣FEWMA解決了EWMA窗口選擇時遇到的矛盾。

為了能與圖6形成對比，本文在0～2 min、2～4 min、4～6 min、6～8 min、8～10 min內，分別將兩個MicaZ節點的距離變為2 m、8 m、4 m、6 m、3 m，測試環境與圖6的測試環境完全一樣，均是每秒發送10個數據包。最終測試結果如圖7所示。

圖7中，在2 min附近收包率發生躍變后進入穩定時間比較長，這是因為區間評估結果需要發生兩次變化。由于權重的影響，導致收包率一開始變化緩慢，隨著連續丟包數目的增加，會造成區間的改變，一旦權重發生變化則收包率立即開始急劇下降。EWMA與FEWMA的性能對比結果如表3所示。

表3中的錯誤率是指一個距離點上誤差大于均值20％的測試結果發生概率。

結合圖6、7不難看出FEWMA的最終測試結果比較穩定，而且該穩定值能反映出圖6中的每一個距離點上的總體趨勢。這說明FEWMA的最終測試結果并沒有偏離實際，而且它在路由選擇應用中使拓撲結構更加穩定、更具應用價值。

6 結束語

本文從大量實驗數據中分析出無線鏈路的數據包丟失存在一定特征，即鏈路質量非常不好時連續丟包數目比較大；反之在鏈路質量較好的情況下連續丟包數目比較小，由此分析出傳統EWMA鏈路評估器存在的不足，并實驗加以驗證。針對EWMA的不足與無線鏈路的丟包特性，提出一種基于鏈路丟包特性對無線鏈路進行劃分區間的思想，并運用模糊數學方法對區間劃分進行建模，從而在EWMA基礎上產生FEWMA鏈路評估器。FEWMA針對不同區間對丟包事件進行不同權重的加權，使最終測量結果趨于穩定，同時保持結果的正確性與合理性。最終測試結果表明，FEWMA不但能夠節約存儲空間、靈敏響應鏈路突變，而且更具應用性。

鏈路評估器在路由選擇應用中作用非常巨大。由于無線通信是以電磁波形式進行數據傳輸，在無線傳感器網絡中每個節點在其他節點通信時均可以采用overhearing[12]技術監聽通信信息并統計，從而可以評估出周圍鄰居節點與自己的鏈路狀況，最終選擇最合適的路由。這種方法將改變傳統依靠周期發送探測包進行路由更新手段的不足，后期工作將會集中于此。

參考文獻：

［1］

任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14(7):12821291.

［2］WOO A，CULLER D.Evaluation of efficient link reliability estimators for lowpower wireless networks，UCB/CSD031270[R].Derkeley:University of California，2003.

［3］CERPA A，WONG J L，KUANG L，et al.Statistical model of lossy links in wireless sensor networks[C]//Proc of the 4th International Symposium on Information Processing in Sensor Networks.Piscataway:IEEE Press，2005:116.

［4］張躍，鄒壽平，宿芬.模糊數學方法及其應用[M].北京：煤炭工業出版社，1992:55100.

［5］KIM M，NOBLE B.Mobile network estimation[C]//Proc of the 7th ACM Conference on Mobile Computing and Networking.New York:ACM Press，2001:298309.

［6］侯蓉暉，史浩山，楊少軍．一種無線傳感器網絡以數據為中心的QoS路由協議[J].傳感技術學報，2006，19(6):7074.

［7］2.4 GHz IEEE 802.15.4/ZigBeeready RF transceiver[EB/OL].http://www.chipcon.com/files/CC2420_Data_Sheet_1_3.pdf.

［8］霍宏偉，牛延超，黃吉瑩．Atmega128/2560系列單片機原理與高級應用[M].北京：中國林業出版社，2006:220230.

［9］BHATTI S，CARLSON J，DAI Hui，et al.MANTIS OS:an embedded multithreaded operating system for wireless micro sensor platforms[J].Mobile Networks and Applications，2005，10(4):563579.

［10］BAHL P，PADMANABHAN V N.RADAR:an inbuilding RFbased user location and tracking system[C]//Proc of the 19th Annual Joint Conference on IEEE Computer and Communications Societies.2000:775784.

［11］ZUNIGA M，KRISHNAMACHARI B.Analyzing the transitional region in low power wireless links[C]//Proc of the 1st Annual IEEE Communication Society Conference on Sensor and Ad hoc Communications and Network.Santa Clara: IEEE Communications Society，2004:517526.

［12］WOO A，TONG T，CULLER D.Taming the underlying challenges of reliable multihop routing in sensor networks[C]//Proc of the 1st International Conference on Embedded Networked Sensor Systems.New York:ACM Press， 2003:1427.