基于中國(guó)剩余定理的SMR路由協(xié)議研究

童孟軍,鄭 拓

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院,浙江杭州310018)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)是一種低能耗需求,并且可以在無(wú)基站或其他設(shè)施支持下快速部署的無(wú)線網(wǎng)絡(luò)[1]?；谶@種特性,它可以廣泛應(yīng)用在環(huán)境監(jiān)測(cè),災(zāi)后臨時(shí)通信,戰(zhàn)時(shí)通信網(wǎng)絡(luò)快速部署等很多方面。多路徑按需路由協(xié)議是無(wú)線傳感器網(wǎng)絡(luò)目前研究的熱點(diǎn)。這種路由協(xié)議不僅具有按需路由協(xié)議[2]具有的控制信息最少化,高效路由信息交換的優(yōu)點(diǎn),同時(shí)具備多路徑路由協(xié)議的一切特點(diǎn)。過(guò)去流行的單路徑路由協(xié)議,雖然具有算法簡(jiǎn)單,易于管理和配置等優(yōu)點(diǎn),但是存在可靠性低,帶寬受限,拓?fù)渥兓m應(yīng)性弱等等不足。使用多條路徑來(lái)傳輸數(shù)據(jù)可以很好的解決這一問(wèn)題,路徑的聚合帶寬可以很容易的滿足這一應(yīng)用的要求。而且多路徑有更多的可用帶寬,端到端的延時(shí)會(huì)更小。多路徑路由可在源和中間結(jié)點(diǎn)上提供候選路徑,極大的提高了容錯(cuò)性。如S建立了3條到目的結(jié)點(diǎn)的路徑,如果結(jié)點(diǎn)S沿著3個(gè)路徑發(fā)送相同的報(bào)文,只要最少保證其中一條不失敗,結(jié)點(diǎn)D就會(huì)收到這個(gè)報(bào)文。多路徑路由可以提供負(fù)載均衡,改善MANET中的鏈路利用率。大量的仿真結(jié)果證明多路徑路由協(xié)議可以明顯的改善分組轉(zhuǎn)發(fā)成功率,端到端的延時(shí)和TCP及UDP的吞吐率等。

1 SMR路由協(xié)議

分割多路徑路由協(xié)議[3]是一種基于DSR的改進(jìn)型多路徑按需路由協(xié)議[4]。與DSR[5]僅維護(hù)并通過(guò)一條路徑傳輸數(shù)據(jù)不同的是,SMR維護(hù)多條到達(dá)目的節(jié)點(diǎn)的路徑,當(dāng)有數(shù)據(jù)發(fā)送時(shí),數(shù)據(jù)被分割并通過(guò)不同路徑到達(dá)目的地。SMR協(xié)議主要特點(diǎn)就是實(shí)現(xiàn)多條路徑盡可能的不交叉。它主要是通過(guò)兩種改進(jìn)機(jī)制實(shí)現(xiàn)的:

(1)在SMR協(xié)議中,節(jié)點(diǎn)間的路由信息被包含在RREQ包里,中間的節(jié)點(diǎn)即使有到達(dá)目標(biāo)節(jié)點(diǎn)的路由也不能回復(fù)RREP,這樣就保證了盡可能多的RREQ通過(guò)不同路徑到達(dá)目標(biāo)節(jié)點(diǎn),實(shí)現(xiàn)了最大不交叉的多路徑路由;

(2)為了避免重疊路由問(wèn)題,SMR摒棄常用的中間節(jié)點(diǎn)丟棄重復(fù)RREQ的做法,而是要有選擇的轉(zhuǎn)發(fā)重復(fù)的RREQ,被轉(zhuǎn)發(fā)的重復(fù)RREQ要符合下列條件。

被轉(zhuǎn)發(fā)的RREQ重復(fù)包要與節(jié)點(diǎn)第一次收到的RREQ包來(lái)自不同的鏈路。

被轉(zhuǎn)發(fā)的RREQ重復(fù)包的跳數(shù)計(jì)數(shù)器的值必須小于第一次收到的RREQ包的相應(yīng)值。

如圖1、2所示分別是未采用上述避免交叉機(jī)制的多路徑路由和采用后的多路徑路由。

圖1 交叉的多路徑路由

圖2 最大不交叉多路徑路由

2 基于中國(guó)剩余定理的SMR協(xié)議研究

研究發(fā)現(xiàn)Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗主要是用于數(shù)據(jù)傳輸,因此為了增強(qiáng)無(wú)線網(wǎng)絡(luò)使用多路徑協(xié)議時(shí)候節(jié)點(diǎn)的生存能力,不可避免的要考慮減少節(jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)候的消耗。使用基于中國(guó)剩余定理[6]的SMR路由傳輸,通過(guò)減少發(fā)送的數(shù)據(jù)冗余來(lái)提高節(jié)點(diǎn)的生存能力,可以顯著地提高了整個(gè)網(wǎng)絡(luò)的有效帶寬。

2.1 中國(guó)剩余定理

在我國(guó)古代著名數(shù)學(xué)著作孫子算經(jīng)中,有一道題目叫做“物不知數(shù)”,原文如下:

有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二。問(wèn)物幾何?

即一個(gè)整數(shù)除以三余二,除以五余三,除以七余二,求這個(gè)整數(shù)。用數(shù)學(xué)方法概括如下:

假設(shè)有N個(gè)素?cái)?shù)pi＞1,其中i∈{1,…,N},那么素?cái)?shù)的積M=Πipi。對(duì)任一給定的整數(shù)集合{m1,m2,…,mN},存在唯一的整數(shù)m＜M,使得m=mi(mod pi)。m的計(jì)算方法為:中的系數(shù)ci=Qiqi,Qi=M/pi,qi使得ci=1(mod pi)。

2.2 理想狀態(tài)下中國(guó)剩余定理在多路徑中的應(yīng)用

在多路徑傳輸中,使用中國(guó)剩余定理基本思想是:在節(jié)點(diǎn)內(nèi)部定義固有的素?cái)?shù)pi,i∈{1,…,N},N代表傳輸數(shù)據(jù)時(shí)候能夠采用的最多路徑數(shù),傳輸一個(gè)數(shù)據(jù)m的時(shí)候,只用在各條路徑上單獨(dú)傳輸mi即可。用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明:假設(shè)A要向B發(fā)送一個(gè)數(shù)據(jù)m,且A與B之間建立了N條路徑,節(jié)點(diǎn)內(nèi)部預(yù)設(shè)的素?cái)?shù)為pi,i∈{1,…,N},其中m=64,N=3,p1=3,p2=5,p3=7。由m=mi(mod pi),可以得出應(yīng)用中國(guó)剩余定理實(shí)際需要傳輸?shù)臄?shù)據(jù)僅為m1=1,m2=4,m3=1。需要7bit單鏈路傳輸?shù)臄?shù)據(jù),僅用單鏈路不超過(guò)3bit就可以傳輸。

2.3 基于中國(guó)剩余定理的CRT-SMR路由協(xié)議

Ad Hoc網(wǎng)絡(luò)是一種節(jié)點(diǎn)自組織網(wǎng)絡(luò),在實(shí)際網(wǎng)絡(luò)環(huán)境下,節(jié)點(diǎn)的移動(dòng),新節(jié)點(diǎn)的加入,原有節(jié)點(diǎn)的死亡等都會(huì)造成網(wǎng)絡(luò)拓?fù)涞淖兓?從而使原有節(jié)點(diǎn)間建立的通信鏈路發(fā)生變化。因此在改進(jìn)協(xié)議的時(shí)候要充分考慮到這一點(diǎn)。

在SMR協(xié)議中,當(dāng)一個(gè)節(jié)點(diǎn)無(wú)法向下一跳傳輸數(shù)據(jù)或者無(wú)法接收到確認(rèn)通知,該節(jié)點(diǎn)將會(huì)向上游鏈路發(fā)送RERR來(lái)告知鏈路中斷,從而使得數(shù)據(jù)發(fā)送源節(jié)點(diǎn)不在使用該條鏈路。

在CRT-SMR協(xié)議中,使用冗余鏈路可以很好的保證整個(gè)網(wǎng)絡(luò)的魯棒性。這里使用最小可用鏈路集MAS-f來(lái)決定多路徑的鏈路出現(xiàn)中斷時(shí)何時(shí)來(lái)采取路由重發(fā)現(xiàn)機(jī)制[7]。

在該機(jī)制中,f為數(shù)據(jù)傳輸需要的最少鏈路數(shù)[8],k為出現(xiàn)的鏈路失效數(shù)目。對(duì)一個(gè)擁有N條可用鏈路的CRT-SMR路由中,啟動(dòng)路由重發(fā)現(xiàn)機(jī)制必須滿足下列條件:(1)源節(jié)點(diǎn)收到某條鏈路發(fā)送的RERR后,刪除路由表中當(dāng)前對(duì)應(yīng)的鏈路,同時(shí)可用鏈路計(jì)數(shù)器減1;(2)源節(jié)點(diǎn)有數(shù)據(jù)發(fā)送需求,同時(shí)當(dāng)前可用鏈路計(jì)數(shù)器的值小于f。

2.3.1 CRT-SMR初始化

在該路由機(jī)制中,要求各節(jié)點(diǎn)使用的最小素?cái)?shù)集MPS=f,即保證傳輸過(guò)程中只要N個(gè)分組中任意f個(gè)分組到達(dá)目的節(jié)點(diǎn),就可以還原出原始數(shù)據(jù)。在正常的傳輸過(guò)程中使用N個(gè)素?cái)?shù)的集合,其中冗余素?cái)?shù)個(gè)數(shù)為N-f。初始化階段基本步驟:(1)通知目的節(jié)點(diǎn)所有的素?cái)?shù)pi,i∈{1,…,N}和f的值;(2)源節(jié)點(diǎn)的N個(gè)下一條節(jié)點(diǎn),隨機(jī)選擇一個(gè)pi,并且各節(jié)點(diǎn)選擇沒(méi)有重復(fù);(3)源節(jié)點(diǎn)的下一條收到相同的數(shù)據(jù)m,然后得出自己實(shí)際需要發(fā)送的數(shù)據(jù)mi,m=mi(mod pi),并把i加入對(duì)應(yīng)的信息ID。

2.3.2 CRT-SMR轉(zhuǎn)發(fā)策略

目的節(jié)點(diǎn)收到數(shù)據(jù)后,必須要找到對(duì)應(yīng)的mi和pi,進(jìn)而才能完成數(shù)據(jù)重組。實(shí)現(xiàn)方法如下:

定義數(shù)據(jù)中信息ID,占用N+1位。其中第一位表示是否為CRT分組,后面N位表示當(dāng)前分組對(duì)應(yīng)的mi,首位為1的分組不得再啟用CRT分組機(jī)制。假設(shè)S要向M傳輸數(shù)據(jù),N=5,f=3,則對(duì)應(yīng)的信息ID分組集為{100001,100010,100100,101000,110000}。

CRT-SMR采用的是最大不交叉機(jī)制,并不能保證所有路徑的完全不交叉。該機(jī)制中源節(jié)點(diǎn)的下一條節(jié)點(diǎn){A,B,C,D,E}負(fù)責(zé)使用CRT計(jì)算mi,其它中間節(jié)點(diǎn){F,G,H,I}負(fù)責(zé)對(duì)其進(jìn)行轉(zhuǎn)發(fā)和發(fā)現(xiàn)鏈路斷裂后發(fā)送給源節(jié)點(diǎn)RERR。

3 仿真及性能比較

仿真基于NS-2平臺(tái)。比較3種協(xié)議:

(1)DSR;

(2)SMR-5,初始化階段選擇5鏈路的SMR協(xié)議,當(dāng)且僅當(dāng)5條鏈路斷裂時(shí)啟動(dòng)路由重發(fā)現(xiàn)機(jī)制;

(3)CRT-SMR,設(shè)置其N=5,f=2,當(dāng)且僅當(dāng)?shù)陀?條可用鏈路時(shí)啟動(dòng)路由重發(fā)現(xiàn)機(jī)制。

基本仿真場(chǎng)景為:50個(gè)節(jié)點(diǎn)隨機(jī)分布在1 000m×500m的區(qū)域內(nèi),節(jié)點(diǎn)按照random waypoint方式移動(dòng),每個(gè)節(jié)點(diǎn)選擇0到10m/s之間的移動(dòng)速度。節(jié)點(diǎn)MAC層采用IEEE 802.11 DCF規(guī)范,傳輸范圍250m,數(shù)據(jù)率為2Mb/s。傳播方式采用Free space propagationmodel,仿真時(shí)間300s。

如圖3所示各協(xié)議丟包數(shù)曲線。從圖3中可以看出SMR-5和CRT-SMR要遠(yuǎn)優(yōu)于DSR,在初期節(jié)點(diǎn)停留時(shí)間短的時(shí)候尤為明顯。這是因?yàn)樵诠?jié)點(diǎn)移動(dòng)相對(duì)較快時(shí)候DSR協(xié)議需要不斷的啟動(dòng)路由重發(fā)現(xiàn)機(jī)制,帶來(lái)的是大量的包的丟棄。而已經(jīng)失效的緩存數(shù)據(jù)會(huì)使這一情況雪上加霜。另外兩種協(xié)議比較,可以發(fā)現(xiàn)后者更優(yōu),這主要是因?yàn)槭褂弥袊?guó)剩余定理后,單條鏈路負(fù)荷大大減小,很大程度上避免擁塞丟包情況。

圖3 丟包數(shù)

圖4 分組投遞率

如圖4所示分組投遞率的數(shù)據(jù)。比較可以得出,采用多路徑的后兩者由于擁有冗余鏈路有更好的表現(xiàn)。CRT-SMR采用中國(guó)剩余定理算法,大大減少了數(shù)據(jù)發(fā)送量,帶來(lái)了更大的有效帶寬,使得在分組投遞率上表現(xiàn)比SMR更出色。

從以上簡(jiǎn)單的分析,可以看出基于中國(guó)剩余定理的SMR協(xié)議,具有更強(qiáng)的適應(yīng)性,在提高網(wǎng)絡(luò)有效帶寬的同時(shí)對(duì)網(wǎng)絡(luò)整體性能有較大的提升。

4 結(jié)束語(yǔ)

SMR協(xié)議由于采用冗余鏈路,使用各路徑分片發(fā)送數(shù)據(jù),因此不需要經(jīng)常性的啟動(dòng)路由重發(fā)現(xiàn)機(jī)制,這大大的減少了網(wǎng)絡(luò)中控制包的數(shù)量,增強(qiáng)了網(wǎng)絡(luò)的健壯性,但是采用多條路徑會(huì)增大路由的開(kāi)銷。本文提出的基于中國(guó)剩余定理的SMR協(xié)議,可以很好的減少實(shí)際傳輸?shù)臄?shù)據(jù),彌補(bǔ)了這一缺陷,因此可以很好的適合Ad Hoc網(wǎng)絡(luò)。

[1] 孫利民,李建中,陳渝,等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005:20-39.

[2] Nasipuri A,Das SR.On-Demand Mu ltipath Routing for Mobile Ad Hoc Networks[C].Montreal:Eight International Conference,1999:64-70.

[3] Lee S J,Gerla M.SplitMultipath Routing with Maximally Disjoint Paths in Ad Hoc Networks[C].Boston:IEEE International Conference,2001:3 201-3 205.

[4] Johnson D,Maltz D.Dynamic Source Routing in Ad Hoc W ireless Networks[C].Santa Cruz:IEEE International Conference,1994:158-163.

[5] Campobello G,Leonardi A.A novel reliable and energy-saving forwarding technique for wireless sensor networks[C].Messina:ACM International Conference,2009:269-278.

[6] Dulman S,Nieberg T.Trade-off between traffic overhead and reliability inmultipath routing for wireless sensor net-works[J].W ireless Communications Networking,2003,18(3):1 918-1 922.

[7] Perkins C,Royer EM.Ad-hoc on-demand distance vector rout-ing[J].Second IEEEWorkshop.1999,10(9):90-100.[8] Wang L,Oliver W.Multipath source routing in wireless ad hoc network[C].Canadian:Electrical and Computer Conference,2000:479-483.