WSN中基于排序轉發列表的機會路由協議

劉友武，王 晶，劉持標，3

(1.三明學院 現代教育技術中心, 福建 三明 365004; 2.三明學院 信息工程學院， 福建 三明 365004;3.福建省農業物聯網應用重點實驗室， 福建 三明 365004)

無線傳感器網絡因其低成本、可快速部署等優點正逐漸成為一種新的有吸引力的通信模式[1]。在大多數傳感器網絡中，降低能耗是主要的挑戰[2]。通常，傳感器網絡被設計成長時間無人看管模式，因此必須節省電池充電，以延長每個傳感器和整個傳感器網絡的壽命[3]。當路由協議應用于傳感器網絡時，應始終考慮協議對傳感器壽命的影響，能量效率是無線傳感器網絡路由協議設計的主要考慮因素之一[4-5]。目前，越來越多的WNS協議在設計時考慮能量效率問題，如異構無線傳感器網絡的節能數據收集協議[6]，能量有效的無線傳感器網絡無標度拓撲模型[7]等。

對于無線傳感器網絡節能路由協議已經進行了大量研究。文獻[8]提出一種具有移動sink的無線傳感器網絡的節能ring路由協議，減少了移動sink的位置通告給網絡在能量消耗和分組延遲方面引入的開銷。文獻[9]提出了基于PSO的路由和用于無線傳感器網絡的聚類，PSO路由建立了傳輸距離和跳數之間的權衡，聚類算法平衡了CH的能量消耗，在網絡壽命和能耗方面具有優越性。文獻[10]提出一種基于非均勻分簇的無線傳感器網絡路由協議，通過多維條件(如剩余能量、到節點的距離等)來選擇簇頭，然后通過單跳和多跳混合方法發送數據。該方法能夠緩解能量空洞問題，延長網絡壽命。

機會路由中節點分布稀疏，網絡拓撲結構不斷發生變化，數據方法是多跳，其轉發節點從多個候選節點選出最終的轉發節點，其優點是具有更高的傳輸可靠性以及端到端的吞吐量。機會路由允許在轉發器列表中(能夠偷聽傳輸并且更接近目的地)的節點參與到包保護中，根據當前鏈路質量狀況進行機會選擇得到路由路徑[11]。文獻[12]提出一種候選節點間協同時延最優的機會路由協議，實現對候選節點協同轉發過程的機理建模，得到期望端到端協同時延，并以此作為路由測度，增加了網絡吞吐量，減少了端到端的平均時延。文獻[13]提出針對異步工作循環無線傳感器網絡的網絡內聚合的機會路由，能提高保持數據包的節點的占空比，增加網內聚合的機會，從而降低能耗，延長網絡生命周期。文獻[14]提出一種多跳傳感器網絡中基于能量感知的機會路由協議，在平衡鏈路質量和能量的前提下提出一種新的路由度量標準，并以此為準則，設計了候選集選擇算法和節點協調機制。文獻[15]提出一種基于網絡編碼的WSN機會路由優化算法，通過計算接收編碼包失敗的概率減少編碼包的重傳次數，達到延長網絡生存時間、降低平均能耗的目的。

本文在研究現有無線傳感器網絡的機會路由協議的基礎上，提出了一種節能的排序轉發列表的機會路由(sorted forwarding list-based opportunistic routing,SFLOR)協議，給出轉發列表的選擇和優化算法，得到最大范圍傳感器節點的轉發列表，使得能耗最小化。SFLOR協議能夠降低網絡能耗和丟包率，改善網絡中節點能量的均衡性。

1 機會路由

為確保無線傳感器網絡的可靠通信，Biswas等提出的機會路由根據與目的地的接近標準選擇下一個鄰居。機會路由是無線傳感器網絡中一種新的路由選擇方法，它充分利用無線信道的廣播特征，提供高吞吐量，降低能耗成本，并在選擇最佳路由時使用優先級概念。 機會路由基于以下規則：

1) 每個網絡節點發送問候消息以發現相鄰節點。

2) 每個節點將相同的消息發送到相鄰節點。

3) 使用協調方法選擇最佳節點。

4) 選擇目標的最近節點。

機會路由協議針對無線信號的時變性以及不穩定性問題，利用無線信道廣播的特征，從多路徑機制和多節點轉發機制這兩個方面減少數據分組傳輸過程中的路由跳數，提高單跳傳輸成功率。機會路由多路徑機制和多節點轉發機制如圖1、2所示。

圖1 機會路由多路徑機制

圖2 多節點轉發機制

圖1中，S、A、B、D分別表示源節點、中間節點、中間節點和目的節點，百分數字表示傳輸成功率。在源節點S發送消息到目的節點D時，直接轉發是最簡單的方式，但由于鏈路質量問題導致傳輸效率只有20%。對于傳統路由協議，為了提高傳輸成功率，選擇鏈路質量好的路徑轉發數據。例如，數據分組選擇S→A→B→D的路徑，該路徑的傳輸成功率最高，降低了分組重傳的次數，缺點是數據分組轉發次數較多。

對于機會路由協議，節點的鄰居節點以大概率偵聽到本節點的廣播數據。在源節點S廣播數據分組的過程中，目的節點可以直接接收數據分組，其優于傳統路由的方面在于：數據分組無需按照選定的路徑傳輸，在未收到數據的情況下，目的節點能夠通過中間節點A或B的廣播接收數據分組，在保證傳輸成功率的同時節省了網絡資源。機會路由不需要提前選定傳輸路徑，利用多路徑機制和信道的廣播特性，能夠使得數據分組快速到達目的節點，在減少傳輸過程中路由跳數的同時節省網絡資源，提高網絡吞吐量。

機會路由的下一跳是選擇最佳轉發節點進行轉發，選擇條件是按照一定的度量。在圖2中，假設源節點S至相鄰3個節點之間的數據傳輸成功率相等且均為30%，在傳統路由協議中，源節點S通過預設的路徑(選擇3個中間節點的1個作為中間節點)將數據傳輸到目的節點D，此時，源節點S到目的節點D的數據傳輸成功率只有30%。在幾種路由中，3個節點都有可能作為下一跳接收到數據包并轉發給D，此時，數據傳輸的成功率為1-(1-30%)3=0.657，較傳統路由協議有了很大的提高。因此，在鏈路質量較差的無線傳感器網絡條件下，機會路由能顯著提高網絡端到端的可靠性。

MIT開發的ExOR(extremely opportunistic routing)協議是較經典的機會路由協議，其中路由度量是預期傳輸計數(expected transmission count,ETX)，是最受歡迎的路由度量之一，在確定鏈路質量方面具有良好的準確性。ETX可用于提高網絡吞吐量，特別是對于長路徑情況。

2 SFLOR機會路由協議

無線傳感器網絡因其獨特的特性(易于部署和靈活性)被認為是技術發展最活躍的領域之一。為延長網絡壽命，無線傳感器網絡的研究主要圍繞能耗參數的路由算法展開。在這種情況下，本文提出了一種排序轉發列表的機會路由(sorted forwarding list-based opportunistic routing,SFLOR)協議。SFLOR協議是節能機會路由(energy efficient opportunistic routing,EEOR)的改進協議，其中選擇到目的地的距離最小的節點被添加到EEOR協議中。另外，本文的機會路由協議采用多元維度(到目的地的距離、錯誤率、節點的能量和發送成本)度量，以提高無線傳感器網絡的路由性能。本文中SFLOR協議的目標是：① 最大限度地降低能耗；② 延長傳感器網絡的使用壽命；③ 增加傳輸的數據量；④ 最小化控制消息的數量。

2.1 轉發列表的選擇和優化

無線傳感器網絡模型為G(u,FWD)，其中u代表傳感器節點，FWD是u的轉發列表。兩個節點(i,j)之間鏈路的成本由C=1-P計算得到。該表達式表示正確接收分組的概率，P是傳感器u發送分組但未被任何節點接收的概率。

(1)

其中：1-euvi是節點u正確地將數據包發送到節點v的概率。轉發列表的計算方法為

FWD(u)=vi…vj,i

(2)

根據列表中的成本來處理節點。在計算每個節點的轉發列表后，計算從源節點到目標節點發送數據包的總成本，總成本分為3個部分：

(3)

C(FWD*)=W/P

(4)

(5)

(6)

2.2 本文協議網絡模型

無線傳感器網絡中的傳感器節點可以使用單跳或多跳連接，具體取決于傳感器節點的傳輸范圍。 連接源節點和目標節點的跳數增加會增大節點傳輸和節能的延遲。本文SFLOR協議的目的是減少傳感器節點在接收、傳輸信息時所消耗的能量，并減少無線傳感器網絡中從源節點到目標節點傳輸數據的延遲。假設無線傳感器網絡中：傳感器節點部署的類型是靜態的；網絡中的節點密度是一致的；所有傳感器節點具有相同的初始能量；網絡中數據生成的頻率是一致的；網絡中所有節點具有相同的傳輸范圍。

在網絡中發送的從源節點到目標節點的分組可以被認為包括3個部分：

1) 源節點將分組發送到一個鄰居節點，并且該節點是目標節點；

2) 如果目標節點是遠離源節點的一跳，則在鄰居列表中至少有1個節點將分組中繼到目標；

3) 在發送節點的鄰居之間選擇實際中繼節點的協議。

本文協議在假設數據聚合的情況下提出了最大化壽命的問題，對于僅具有1個源節點和1個目標節點的傳感器陣列，考慮具有調整傳輸功率能力的傳感器，得到最短路徑處理路由。網絡建模為G(U,V)，U是節點集，V是鏈路集，每個有向鏈路(i,j)具有非負權重，由w(i,j)表示，是節點i向節點j發送分組所需的最小傳輸功率。節點i的相鄰節點的數量隨著節點i在發送分組時消耗的功率而變化。當節點i以功率w發送時，令Nw(i)表示節點i的相鄰節點。當未提及下標w時，意味著節點正在使用最大功率，即N(i)=NW(i)。此外，每個鏈路(i,j)的錯誤概率用e表示，是鏈路(i,j)上傳輸不成功的概率。節點i必須消耗至少w(i,j)功率才有1-e的機會將數據包發送到節點j，否則無法傳輸。節點U和目標節點之間的距離用d表示，c表示節點的預期成本。本文SFLOR協議的模型和預期成本如圖3所示。

圖3 本文協議模型和預期成本

本文中，路由協議給出轉發列表進行選擇和優化，并將選擇到目標節點的距離最小的節點添加到轉發列表，得到最大范圍的轉發列表。SFLOR策略基于組合度量來提高無線傳感器網絡的路由性能，組合度量包括預期成本、錯誤率、源節點與目標節點距離的組合。SFLOR算法基于2個步驟：轉發列表和計算成本。

步驟1:轉發列表FWD輸入:目標節點,源節點,預期成本、錯誤率和源節點和目標節點距離的組合(c,e,d),功率w。輸出:每個節點的轉發列表。 a.在FWD列表中添加源節點 b.計算FWD(u)=v1時的預期成本 C=w+(1-e)?1c?1d()(1-e) c.如果FWD的預期成本<∑FWD中節點成本,則添加節點

步驟2:計算成本輸入:轉發列表中的每個節點,目標節點、源節點、預期成本、錯誤率與源節點和目標節點距離的組合(c,e,d),功率w。輸出:從節點u到節點t的預期成本Cu(FWD)。 a.計算每個FWD列表的能源成本 Chu(FWD?)=W/P b.計算U下的總成本,使用FWD列表將數據包轉發到目的地 Chu(FWD?)=β/P c.計算通信成本達成最佳路徑選擇協議,直到沒有節點添加轉發器列表Ccu

對本文協議算法進行驗證，節點無法在轉發列表中選擇其所有鄰居。

步驟1計算轉發列表中節點v1的成本。

FWD{Source}={N1}

C=(w+(1-e1)×1/c1×1/d1)/(1-e1)=2.33

(7)

步驟2比較節點N1的成本和添加N1后的總成本，C=2.33>c1=1。要添加節點，除非N1成本小于轉發列表中節點的總成本，否則完成N1。

(8)

(9)

因此，轉發列表包含N3，因為該節點最接近目標節點。總成本的1/d的增加顯示了轉發列表最小化和最佳節點的選擇。

3 實驗結果與分析

本文路由協議實驗中，實驗對象為n∈[10,200]節點拓撲傳感器，其中每個無線鏈路有固定的誤差率，節點以預測的隨機間隔恢復能量，并假設其電池是理想的。指定本文模擬實驗在網絡G(U,V)上進行，其中U={N1,N2,N3,…,Ni},i∈[1,n]，n∈[10,200]是節點數，V是鏈路集，網絡參數如表1所示。

表1 網絡參數

實驗在筆記本電腦上進行。機器配置為8 Intel CORE i7，4GB Ram。模擬的傳感器節點配備應用層、隨機線性網絡編碼、機會路由、對介質的隨機訪問和物理層。表2給出了網絡模型和符號。

表2 網絡模型中符表示意義

將本文協議與經典ExOR協議、節能機會路由EEOR協議進行比較。圖4給出了3種路由協議的能量消耗。

圖4 不同協議的能耗

可以看出：本文SFLOR路由協議相比EEOR和ExOR協議具有更好的性能。這是因為本文算法選擇到目標節點距離最小的節點添加到EEOR協議，最大限度地降低了能耗。圖5給出了不同協議傳輸過程中丟棄的數據包總數。

圖5表明：SFLOR協議在丟棄數據包數量方面提供了更好的性能，SFLOR協議比ExOR協議的丟包率降低了20%左右，比EEOR協議的丟包率降低了11%左右。圖6給出了不同協議下的候選節點選擇。

圖5 不同協議的丟包率

圖6 不同協議源和目標節點之間的候選集選擇數

更具體地說，在當前節點發送數據分組時，所有成功接收的節點都是FRW，它們彼此協調以確定實際傳遞的FRW。從圖6可以看出：本文SFLOR協議比其他2種協議具有更少的源和目標節點之間的候選集選擇數，因而本文SFLOR協議能夠以較少的能耗實現數據包傳輸。

4 結束語

本文研究了如何選擇和優先轉發列表，減少單播能耗，提出一種排序轉發列表的機會路由SFLOR協議。該協議給出了傳輸功率固定條件下，每個節點選擇和排序轉發列表的算法，并將選擇到目標節點的距離最小的節點添加到轉發列表。通過同ExOR協議和EEOR協議的實驗表明：SFLOR協議在能耗、丟包率、源與目標節點之間的候選集選擇數3個方面的性能優于其他2種機會路由協議。下一步工作中，將選擇用于組播和廣播的最優轉發列表的算法，研究如何將機會路由與網絡編碼和鏈路層錯誤校正相結合，以提高吞吐量并減少重傳。