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

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

0 引 言

由于機(jī)會路由協(xié)議提高了網(wǎng)絡(luò)數(shù)據(jù)包傳輸?shù)目煽啃圆p少了由于數(shù)據(jù)包重傳所引起的不必要的能量消耗[1,2]，因此，近幾年來，機(jī)會路由協(xié)議已經(jīng)獲得了國內(nèi)外許多學(xué)者的關(guān)注和研究[3-5]。

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

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

1 網(wǎng)絡(luò)模型及準(zhǔn)備

1.1 網(wǎng)絡(luò)模型

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

本文所考慮的無線傳感器網(wǎng)絡(luò)模型包含一個源節(jié)點，一個目的節(jié)點以及若干個中繼節(jié)點，其中，源節(jié)點負(fù)責(zé)采集數(shù)據(jù)，并將數(shù)據(jù)發(fā)送給鄰近的中繼節(jié)點或者目的節(jié)點；目的節(jié)點負(fù)責(zé)收集來自源節(jié)點和中繼節(jié)點的數(shù)據(jù)；中繼節(jié)點負(fù)責(zé)接收來自源節(jié)點或者其它中繼節(jié)點的數(shù)據(jù)，并對這些數(shù)據(jù)進(jìn)行處理和轉(zhuǎn)發(fā)。

圖1所給的是采用機(jī)會路由協(xié)議的無線傳感器網(wǎng)絡(luò)模型，其中，s為源節(jié)點，V1～Vn表示中繼節(jié)點，d表示目的節(jié)點。在圖1中，源節(jié)點s的候選節(jié)點集為{V1,V2,…,Vn}。源節(jié)點s發(fā)送的數(shù)據(jù)包可以被其候選節(jié)點集中的節(jié)點接收，然后由候選節(jié)點集中優(yōu)先級最高的節(jié)點來對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，從而有效地利用潛在的路徑來增加網(wǎng)絡(luò)傳輸?shù)目煽啃?，減少數(shù)據(jù)包的重復(fù)傳輸。

圖1 無線傳感器網(wǎng)絡(luò)模型

本文所考慮的無線傳感器網(wǎng)絡(luò)是以輪的方式來對源節(jié)點采集的數(shù)據(jù)進(jìn)行收集的。網(wǎng)絡(luò)生存周期定義為當(dāng)網(wǎng)絡(luò)中有一個節(jié)點失效時網(wǎng)絡(luò)所運(yùn)行的輪數(shù)。

1.2 準(zhǔn) 備

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

假設(shè)：候選節(jié)點集中的候選節(jié)點回復(fù)的應(yīng)答包可以100%的被發(fā)送節(jié)點和其它候選節(jié)點接收到。

注：這是一個常常被用到的假設(shè)，事實上，候選節(jié)點可以通過多次發(fā)送應(yīng)答包來近似的認(rèn)為所發(fā)送的應(yīng)答包可以被發(fā)送節(jié)點和其它候選節(jié)點100%接收[7]。

網(wǎng)絡(luò)發(fā)送和接收數(shù)據(jù)包的一階能量消耗模型給出如下[9]

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

(1)

Erx(k,r)=Eeleck

(2)

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

2 基于剩余能量的機(jī)會路由協(xié)議

2.1 剩余傳輸次數(shù)

在現(xiàn)有的一些機(jī)會路由協(xié)議設(shè)計中，候選節(jié)點集的選擇往往與一些固定的路由指標(biāo)相關(guān)聯(lián)。在這里我們以O(shè)APF機(jī)會路由協(xié)議所采用的EAX路由指標(biāo)為例進(jìn)行說明。

EAX指標(biāo)表示由發(fā)送節(jié)點到目的節(jié)點的期望任意路徑傳播次數(shù)，它的數(shù)學(xué)表達(dá)式給出如下

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

(3)

(4)

(5)

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

然而，在許多的實際應(yīng)用中，節(jié)點的剩余能量被用在機(jī)會路由協(xié)議中的路由指標(biāo)中[8]。節(jié)點的剩余能量是隨著網(wǎng)絡(luò)的運(yùn)行在不斷變化的，因此，它很難像EAX指標(biāo)一樣被選擇作為候選節(jié)點集的一種選擇標(biāo)準(zhǔn)。為此，我們提出了一種新的度量指標(biāo)——剩余傳輸次數(shù)(RTX)，使用它來進(jìn)行候選節(jié)點集的選擇。

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

圖2 RTX度量指標(biāo)設(shè)計的兩種情況

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

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

(6)

(7)

(8)

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

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

(9)

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

(10)

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

2.2 尋找最優(yōu)候選節(jié)點集

在本文中，RTX指標(biāo)被用來選擇節(jié)點的候選節(jié)點集。在基于剩余能量為路由指標(biāo)的機(jī)會路由協(xié)議中，通過最小化節(jié)點的RTX指標(biāo)可以有效減少節(jié)點傳輸?shù)侥康墓?jié)點的傳輸次數(shù)，從而減少不必要的能量消耗。

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

算法1： 候選節(jié)點集選擇算法

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 如果節(jié)點s的鄰居節(jié)點集N(s)中包含目的節(jié)點d，則由算法1得到的節(jié)點s的候選節(jié)點集包含目的節(jié)點d。

證明：我們采用反證法。

假設(shè)節(jié)點s的最優(yōu)候選節(jié)點集為C，jnb5tx5∩C=?，使得RTX(s,C)≤RTX(s,Ω),?Ω?N(s)。

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

如何合理的應(yīng)用算法1來求取網(wǎng)絡(luò)中每一個節(jié)點的RTX指標(biāo)是我們接下來考慮的問題。為此，我們提出了一個初始化算法來求取無線傳感器網(wǎng)絡(luò)中每一個節(jié)點的RTX指標(biāo)。

算法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首先初始化目的節(jié)點d的RTX指標(biāo)為0，其余節(jié)點的RTX指標(biāo)為∞，并初始化兩個集合C1=V，C2=?。然后選擇集合C1中RTX指標(biāo)最小的節(jié)點添加到集合C2中。假設(shè)新加入到集合C2中的節(jié)點為v，遍歷C1中的節(jié)點，如果這個節(jié)點屬于節(jié)點v的鄰居節(jié)點集N(v)，則采用算法1計算這個節(jié)點的RTX指標(biāo)。然后再次選擇集合C1中RTX指標(biāo)最小的節(jié)點添加到集合C2中。如此循環(huán)往復(fù)，直到集合C1為空集。

2.3 候選節(jié)點之間的協(xié)調(diào)方法

在本文所提的基于剩余能量的機(jī)會路由協(xié)議中，我們采用節(jié)點的剩余能量來對候選節(jié)點集中節(jié)點的優(yōu)先級進(jìn)行排序，即節(jié)點的剩余能量越大，優(yōu)先級越高。由于在網(wǎng)絡(luò)的運(yùn)行過程中，節(jié)點的剩余能量是不斷變化的，因此，一個候選節(jié)點集中節(jié)點的優(yōu)先級排序結(jié)果也是不斷更新的。為了避免數(shù)據(jù)包的冗余傳輸，我們采用基于應(yīng)答包的協(xié)調(diào)機(jī)制來對候選節(jié)點集中的節(jié)點進(jìn)行協(xié)調(diào)。關(guān)于基于應(yīng)答包的協(xié)調(diào)機(jī)制的工作原理請參見文獻(xiàn)[6]。

3 仿 真

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

圖3 仿真場景

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

表1 仿真中的一些參數(shù)

圖4給出了RE-OR機(jī)會路由協(xié)議與傳統(tǒng)的ExOR、OAPF和EEOR機(jī)會路由協(xié)議的比較結(jié)果。從圖4中，我們可以看到，RE-OR機(jī)會路由協(xié)議相較于另外3種機(jī)會路由協(xié)議可以很大提升網(wǎng)絡(luò)的生存周期。

圖4 多種機(jī)會路由協(xié)議仿真的比較結(jié)果

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

圖5 節(jié)點出度對RE-OR協(xié)議的影響

圖6 傳輸距離對RE-OR協(xié)議的影響

圖7 中繼節(jié)點個數(shù)對RE-OR協(xié)議的影響

4 結(jié)束語

本文首先提出了一個剩余傳輸次數(shù)指標(biāo)，這個指標(biāo)可以被用來選擇網(wǎng)絡(luò)中節(jié)點的候選節(jié)點集。然后，本文將剩余傳輸次數(shù)指標(biāo)應(yīng)用到以節(jié)點剩余能量為路由指標(biāo)的機(jī)會路由協(xié)議RE-OR中。仿真結(jié)果表明，本文所提的基于剩余能量的機(jī)會路由協(xié)議RE-OR可以有效的延長網(wǎng)絡(luò)的生存周期。并且，仿真結(jié)果還表明，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計中，選擇合適的節(jié)點出度，通信距離以及中繼節(jié)點個數(shù)是比較重要的。