WSNs中基于剩余能量的機會路由協議

呂曉軍，王小書，賈新春，陳瑞鳳，李建玉+

(1.中國鐵道科學研究院 電子計算技術研究所，北京 100081；2.山西大學 數學科學學院，山西 太原 030006)

0 引 言

由于機會路由協議提高了網絡數據包傳輸的可靠性并減少了由于數據包重傳所引起的不必要的能量消耗[1,2]，因此，近幾年來，機會路由協議已經獲得了國內外許多學者的關注和研究[3-5]。

機會任意路徑轉發(OAPF)協議[6]采用期望任意路徑傳輸次數(EAX)作為其路由指標。EAX指標充分利用了數據傳輸過程中可能存在的多條路徑，從而使其可以有效的用于機會路由協議的數據轉發過程中。在文獻[7]中，一個能量有效的機會路由協議(EEOR)被提出，它使用期望成本路由指標來計算數據傳輸過程中的成本。文獻[8]提出的機會路由協議以傳輸節點與移動目的節點之間的距離作為路由指標，并通過計算網絡期望時延來選擇合理的轉發節點。文獻[9]提出了一個可靠的并且能量有效的機會路由協議，該協議使用剩余能量和期望成本的比值作為它的路由指標。一個基于功率控制的協同機會路由協議在文獻[10]中給出，它通過研究數據轉發機制的有效性來減少節點的能量消耗。

在現有的機會路由協議的設計中，所考慮的路由指標往往是固定不變的，因此，這些指標可以用于候選節點集的選擇算法。但是，在實際的應用場景中，往往需要用一些變化的指標來作為節點的路由指標，如節點的剩余能量和節點狀態等?，F有的路由協議中，針對這種變化的路由指標所設計的候選節點選擇算法還比較少。為此，本文提出了一個度量指標——剩余傳輸次數指標，并且提出了一個以節點剩余能量為路由指標的機會路由協議。這個路由協議采用剩余傳輸次數指標來對節點的候選節點集進行選擇。

1 網絡模型及準備

1.1 網絡模型

我們考慮一個由n個節點組成的無線傳感器網絡并假設所有的節點都有一個唯一的身份標識，即i∈[1,n]。這個無線傳感器網絡可以建模為一個有向通信拓撲圖G=(V,E,W)。其中，V是所有節點的集合，即|V|=n，E是所有通信鏈路的集合，W表示每一個節點出度的上界，即節點可擁有的最大子節點的個數。每條通信鏈路都有一個誤差概率，表示為e(u,v)，其中u，v分別表示鏈路兩端的傳感器節點。1-e(u,v)表示節點u沿著鏈路(u,v)成功發送一個數據包到節點v的概率。

本文所考慮的無線傳感器網絡模型包含一個源節點，一個目的節點以及若干個中繼節點，其中，源節點負責采集數據，并將數據發送給鄰近的中繼節點或者目的節點；目的節點負責收集來自源節點和中繼節點的數據；中繼節點負責接收來自源節點或者其它中繼節點的數據，并對這些數據進行處理和轉發。

圖1所給的是采用機會路由協議的無線傳感器網絡模型，其中，s為源節點，V1～Vn表示中繼節點，d表示目的節點。在圖1中，源節點s的候選節點集為{V1,V2,…,Vn}。源節點s發送的數據包可以被其候選節點集中的節點接收，然后由候選節點集中優先級最高的節點來對數據包進行轉發，從而有效地利用潛在的路徑來增加網絡傳輸的可靠性，減少數據包的重復傳輸。

圖1 無線傳感器網絡模型

本文所考慮的無線傳感器網絡是以輪的方式來對源節點采集的數據進行收集的。網絡生存周期定義為當網絡中有一個節點失效時網絡所運行的輪數。

1.2 準 備

為了更好說明本文所提的基于剩余能量的機會路由協議，我們首先給出了如下的假設。

假設：候選節點集中的候選節點回復的應答包可以100%的被發送節點和其它候選節點接收到。

注：這是一個常常被用到的假設，事實上，候選節點可以通過多次發送應答包來近似的認為所發送的應答包可以被發送節點和其它候選節點100%接收[7]。

網絡發送和接收數據包的一階能量消耗模型給出如下[9]

Etx(k,r)=Eeleck+kεampr2

(1)

Erx(k,r)=Eeleck

(2)

其中，k表示發送的信息量，單位為比特，r表示傳輸距離，Eelec表示電路元器件發送和接收1比特數據所消耗的能量。εamp表示功率放大器發送每比特數據的能耗系數。在本文中，傳輸損耗指數設置為2。Etx(k,r)和Erx(k,r)分別表示發送和接收k比特數據所消耗的能量。

2 基于剩余能量的機會路由協議

2.1 剩余傳輸次數

在現有的一些機會路由協議設計中，候選節點集的選擇往往與一些固定的路由指標相關聯。在這里我們以OAPF機會路由協議所采用的EAX路由指標為例進行說明。

EAX指標表示由發送節點到目的節點的期望任意路徑傳播次數，它的數學表達式給出如下

EAX(s,d)=S(s,d)+Z(s,d)

(3)

(4)

(5)

其中，s表示發送節點，d表示目的節點。A表示發送節點s的候選節點集，候選節點集中的節點按照各自的EAX指標從小到大進行排序，并編號為1到|A|，pj表示由發送節點s發送數據包到編號為j的候選節點的成功率。S(s,d)表示節點s發送數據包到候選節點集A中，并且至少有一個候選節點接收到數據包的期望傳輸次數。Z(s,d)表示由節點s的候選節點集A中的節點轉發數據包到目的節點的期望傳輸次數，其中，由于候選節點的EAX指標是固定的，因此，Z(s,d)的計算考慮了候選節點集中節點關于EAX指標的優先級。

然而，在許多的實際應用中，節點的剩余能量被用在機會路由協議中的路由指標中[8]。節點的剩余能量是隨著網絡的運行在不斷變化的，因此，它很難像EAX指標一樣被選擇作為候選節點集的一種選擇標準。為此，我們提出了一種新的度量指標——剩余傳輸次數(RTX)，使用它來進行候選節點集的選擇。

我們考慮如圖2所示的兩種情形。在圖2(a)中，節點s包含3個候選節點，分別為V1，V2和V3。在數據包傳輸過程中，由于節點V1，V2和V3的剩余能量是不斷變化的，因此，這3個節點在轉發數據包上的優先級也是不斷變化的。在圖2(b)中，由于目的節點d是節點s的候選節點，因此，在數據包轉發上，目的節點d始終擁有最高的優先級，節點V1和V3根據各自的剩余能量來確定各自的優先級。

圖2 RTX度量指標設計的兩種情況

我們首先考慮圖2(a)所示的情形，即節點的鄰居節點集中沒有目的節點的情形。假設A是節點s的候選節點集，則節點s的RTX指標RTX(s,d)可以計算如下

RTX(s,d)=S(s,d)+Z(s,d)

(6)

(7)

(8)

其中，候選節點集A中的節點被隨機的編號為1到|A|，pj表示由發送節點s發送數據包到編號為j的候選節點的成功率。S(s,d)表示節點s發送數據包到候選節點集A中，并且至少有一個候選節點接收到數據包的期望傳輸次數。Z(s,d)表示由節點s的候選節點集A中的節點轉發數據包到目的節點的期望傳輸次數，它是候選節點集中節點RTX指標的加權平均值。

考慮圖2(b)所示的情形，即節點的候選節點集中包含目的節點。由于目的節點在任意候選節點集中總是擁有最高的優先級，而在式(8)的計算過程中，候選節點集中的節點是沒有優先級的，因此，采用式(8)來表示節點s的候選節點集中的節點到目的節點d之間的傳輸次數是不合適的。為此，我們將式(8)重寫為

(9)

在這里，我們假設目的節點d在候選節點集A中的編號為|A|，即p|A|表示由節點s發送數據包到目的節點d的成功率。節點s發送數據包到候選節點集A中，并且至少有一個候選節點接收到數據包所需要的期望傳輸次數為S(s,d)。因此，在式(9)中，候選節點集A中目的節點d接收到數據包的概率為(1-p|A|)S(s,d)-1p|A|，而目的節點沒有接收到數據包的概率為(1-p|A|)S(s,d)。如果目的節點d接收到數據包，則不需要對數據包進行轉發，剩余傳輸次數為0。而如果目的節點d沒有接收到數據包，則由候選節點集A中的其它節點對數據包進行轉發的剩余傳輸次數為

(10)

這里，Z(s,A-g0gggggg)表示由節點s的候選節點集A-g0gggggg中的節點發送數據包到目的節點的期望傳輸次數。由條件概率公式可知，由節點s的候選節點集中的節點發送數據包到目的節點d的期望傳輸次數為(1-p|A|)S(s,d)-1p|A|·0+(1-p|A|)S(s,d)·Z(s,A-g0gggggg)。

2.2 尋找最優候選節點集

在本文中，RTX指標被用來選擇節點的候選節點集。在基于剩余能量為路由指標的機會路由協議中，通過最小化節點的RTX指標可以有效減少節點傳輸到目的節點的傳輸次數，從而減少不必要的能量消耗。

算法1給出了一個節點s的最優候選節點集選擇方法以及其自身RTX指標的計算方法。算法1的工作流程如下：首先初始化節點的候選節點集C為空集，且RTX(s,C)=∞。這里RTX(s,C)表示節點s以C為候選節點集時的RTX指標。然后從節點s的鄰居節點集N(s)中任選一個子集Ω，該子集中的元素個數不能大于節點的出度W，即|Ω|≤W。接下來計算RTX(s,Ω)。這樣遍歷的尋找一個子集Ω，使得RTX(s,Ω)最小。最后所得到的子集Ω就是節點s的最優候選節點集C，節點s的RTX指標為RTX(s,C)，即RTX(s,d)=RTX(s,C)。

算法1： 候選節點集選擇算法

Input： the RTX metrics of all neighboring nodesN(s),the destination noded.

Output： the candidate set of the nodesand its RTX metric.

(1) LetCbe the set that represents the candidate of the nodesandC←?,RTX(s,C)←∞;

(2) LetΩbe a set andΩ←?;

(3)fori=1：Wdo

(4)forΩ← any i number of nodes∈N(s)do

(5)ifd∈Ωdo

(6) calculateRTX(s,Ω) by (6),(7),(9);

(7)else

(8) calculateRTX(s,Ω) by (6),(7),(8);

(9)endif

(10)ifRTX(s,Ω)

(11)C←Ω;

(12)endif

(13)endfor

(14)endfor

(15)returncandidate setCandRTX(s,C).

定理1 如果節點s的鄰居節點集N(s)中包含目的節點d，則由算法1得到的節點s的候選節點集包含目的節點d。

證明：我們采用反證法。

假設節點s的最優候選節點集為C，g0gggggg∩C=?，使得RTX(s,C)≤RTX(s,Ω),?Ω?N(s)。

由1-∏j∈C(1-pj)<1-∏j∈C∪g0gggggg(1-pj)，得S(s,C)>S(s,C∪g0gggggg)。其中，S(s,C)表示由節點s發送數據包到其候選節點集C中，并且至少有一個候選節點接收到數據包所需要的期望傳輸次數。另一方面，由式(9)，我們有Z(s,C∪g0gggggg)=αZ(s,C)，α=(1-p|A|)S(s,d)<1，故Z(s,C)>Z(s,C∪g0gggggg)。所以，我們可以找到一個集合C∪g0gggggg?N(s)，使得RTX(s,C)>RTX(s,C∪g0gggggg)。故假設不成立，定理得證。

如何合理的應用算法1來求取網絡中每一個節點的RTX指標是我們接下來考慮的問題。為此，我們提出了一個初始化算法來求取無線傳感器網絡中每一個節點的RTX指標。

算法2： 初始化算法

Input：network topologyG=(V,E,W),destination noded.

Output：the RTX metric and candidate set of each node

(1) LetRTX(d,d)←0,RTX(u,d)←∞,?u≠d;

(2) LetC1←V,C2←?;

(3)while|C1|>0do

(4) letvbe the node inC1,which has the smallest RTX metric;

(5)C1←C1-{v};

(6)C2←C2∪{v};

(7)foreach nodeu∈C1∩N(v)do

(8) run Algorithm 1 for nodeu;

(9)endfor

(10)endwhile

算法2首先初始化目的節點d的RTX指標為0，其余節點的RTX指標為∞，并初始化兩個集合C1=V，C2=?。然后選擇集合C1中RTX指標最小的節點添加到集合C2中。假設新加入到集合C2中的節點為v，遍歷C1中的節點，如果這個節點屬于節點v的鄰居節點集N(v)，則采用算法1計算這個節點的RTX指標。然后再次選擇集合C1中RTX指標最小的節點添加到集合C2中。如此循環往復，直到集合C1為空集。

2.3 候選節點之間的協調方法

在本文所提的基于剩余能量的機會路由協議中，我們采用節點的剩余能量來對候選節點集中節點的優先級進行排序，即節點的剩余能量越大，優先級越高。由于在網絡的運行過程中，節點的剩余能量是不斷變化的，因此，一個候選節點集中節點的優先級排序結果也是不斷更新的。為了避免數據包的冗余傳輸，我們采用基于應答包的協調機制來對候選節點集中的節點進行協調。關于基于應答包的協調機制的工作原理請參見文獻[6]。

3 仿 真

在本文的仿真中，一個200 m×100 m的矩形區域被用來作為仿真場景，如圖3所示。

圖3 仿真場景

一個匯聚節點(用實心三角形表示)位于坐標(200,50)處。若干個中繼節點(用實心圓點表示)隨機均勻分布在這個200 m×100 m的區間內。源節點(用空心圓點表示)位于坐標(0,50)處。其它一些仿真中用到的參數在表1中給出。仿真通過將本文所提的RE-OR機會路由協議與現有的機會路由協議ExOR、EEOR和OAPF進行比較來體現本文所提的機會路由協議在網絡生存周期上的優點。此外，本文還研究了節點出度W、通信距離以及中繼節點個數對本文所提的RE-OR機會路由協議的影響。

表1 仿真中的一些參數

圖4給出了RE-OR機會路由協議與傳統的ExOR、OAPF和EEOR機會路由協議的比較結果。從圖4中，我們可以看到，RE-OR機會路由協議相較于另外3種機會路由協議可以很大提升網絡的生存周期。

圖4 多種機會路由協議仿真的比較結果

圖5～圖7分別給出了節點出度W，通信距離以及中繼節點個數對RE-OR機會路由協議的影響。從圖5和圖6中我們可以看到，選擇合適的節點出度和合適的通信距離有助于增加網絡的生存周期。這是由于選擇較多的子節點可以使得更多的節點參與到每一輪數據的轉發過程中，同時也增加了網絡接收數據的開銷。此外，較大的通信距離意味著比較大的傳輸成本，而較小的通信距離又會增加數據包傳輸的跳數，從而增加網絡的通信成本。在圖6中，中繼節點的個數不同，最大網絡生存周期對應的節點通信距離不同。可見，節點通信距離的選擇與網絡中的節點密度有很大關系。從圖7中我們可以看到，網絡的生存周期隨著中繼節點個數的增加而增加。但是，中繼節點個數的增加無疑增加了網絡的硬件成本。因此，選擇一個合適的網絡規模也是有必要的。

圖5 節點出度對RE-OR協議的影響

圖6 傳輸距離對RE-OR協議的影響

圖7 中繼節點個數對RE-OR協議的影響

4 結束語

本文首先提出了一個剩余傳輸次數指標，這個指標可以被用來選擇網絡中節點的候選節點集。然后，本文將剩余傳輸次數指標應用到以節點剩余能量為路由指標的機會路由協議RE-OR中。仿真結果表明，本文所提的基于剩余能量的機會路由協議RE-OR可以有效的延長網絡的生存周期。并且，仿真結果還表明，在網絡拓撲結構設計中，選擇合適的節點出度，通信距離以及中繼節點個數是比較重要的。