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

(1.三明學院 現(xiàn)代教育技術(shù)中心, 福建 三明 365004; 2.三明學院 信息工程學院， 福建 三明 365004;3.福建省農(nóng)業(yè)物聯(lián)網(wǎng)應用重點實驗室， 福建 三明 365004)

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

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

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

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

1 機會路由

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

1) 每個網(wǎng)絡節(jié)點發(fā)送問候消息以發(fā)現(xiàn)相鄰節(jié)點。

2) 每個節(jié)點將相同的消息發(fā)送到相鄰節(jié)點。

3) 使用協(xié)調(diào)方法選擇最佳節(jié)點。

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

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

圖1 機會路由多路徑機制

圖2 多節(jié)點轉(zhuǎn)發(fā)機制

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

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

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

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

2 SFLOR機會路由協(xié)議

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

2.1 轉(zhuǎn)發(fā)列表的選擇和優(yōu)化

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

(1)

其中：1-euvi是節(jié)點u正確地將數(shù)據(jù)包發(fā)送到節(jié)點v的概率。轉(zhuǎn)發(fā)列表的計算方法為

FWD(u)=vi…vj,i

(2)

根據(jù)列表中的成本來處理節(jié)點。在計算每個節(jié)點的轉(zhuǎn)發(fā)列表后，計算從源節(jié)點到目標節(jié)點發(fā)送數(shù)據(jù)包的總成本，總成本分為3個部分：

(3)

C(FWD*)=W/P

(4)

(5)

(6)

2.2 本文協(xié)議網(wǎng)絡模型

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

在網(wǎng)絡中發(fā)送的從源節(jié)點到目標節(jié)點的分組可以被認為包括3個部分：

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

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

3) 在發(fā)送節(jié)點的鄰居之間選擇實際中繼節(jié)點的協(xié)議。

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

圖3 本文協(xié)議模型和預期成本

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

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

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

對本文協(xié)議算法進行驗證，節(jié)點無法在轉(zhuǎn)發(fā)列表中選擇其所有鄰居。

步驟1計算轉(zhuǎn)發(fā)列表中節(jié)點v1的成本。

FWD{Source}={N1}

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

(7)

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

(8)

(9)

因此，轉(zhuǎn)發(fā)列表包含N3，因為該節(jié)點最接近目標節(jié)點?？偝杀镜?/d的增加顯示了轉(zhuǎn)發(fā)列表最小化和最佳節(jié)點的選擇。

3 實驗結(jié)果與分析

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

表1 網(wǎng)絡參數(shù)

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

表2 網(wǎng)絡模型中符表示意義

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

圖4 不同協(xié)議的能耗

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

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

圖5 不同協(xié)議的丟包率

圖6 不同協(xié)議源和目標節(jié)點之間的候選集選擇數(shù)

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

4 結(jié)束語

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