張 洪，高 楊

(1.成都大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都 610106;2.成都大學(xué) 模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室，四川 成都 610106)

0 引 言

Ad hoc 網(wǎng)絡(luò)是一種特殊的無(wú)線移動(dòng)網(wǎng)絡(luò)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的地位平等，無(wú)需設(shè)置任何的中心控制節(jié)點(diǎn).網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅具有普通移動(dòng)終端所需的功能，而且具有報(bào)文轉(zhuǎn)發(fā)能力.與普通的移動(dòng)網(wǎng)絡(luò)和固定網(wǎng)絡(luò)相比，它具有無(wú)中心、自組織、多跳路由和動(dòng)態(tài)拓?fù)涞奶攸c(diǎn)，適用于無(wú)法或不便預(yù)先鋪設(shè)網(wǎng)絡(luò)設(shè)施的場(chǎng)合［1－2］.本研究在傳統(tǒng)優(yōu)化鏈路狀態(tài)路由(Optmized Link State Routing，OLSR)協(xié)議的基礎(chǔ)上，通過(guò)組合數(shù)和按位運(yùn)算結(jié)合的方法，不僅能達(dá)到傳統(tǒng)OLSR 協(xié)議的目的，并且能有效找出特殊情況的MPR 集，減少不必要的數(shù)據(jù)轉(zhuǎn)發(fā)開(kāi)銷(xiāo)，使其具有高效性，最后通過(guò)仿真平臺(tái)實(shí)現(xiàn)了重新定義OLSR 的MPR 集算法.

1 OLSR與MPR簡(jiǎn)介

1.1 OLSR簡(jiǎn)介

OLSR 是根據(jù)MANET 的要求，在傳統(tǒng)的LS(Link state)協(xié)議的基礎(chǔ)上進(jìn)行優(yōu)化實(shí)現(xiàn)的.OLSR中的關(guān)鍵概念是多點(diǎn)轉(zhuǎn)播MPRs，MPRs 在廣播泛洪的過(guò)程中挑選轉(zhuǎn)發(fā)廣播的節(jié)點(diǎn).傳統(tǒng)的鏈路狀態(tài)協(xié)議每個(gè)節(jié)點(diǎn)都轉(zhuǎn)發(fā)它收到的信息的第一份拷貝，同它相比，OLSR 在很大程度上減少了轉(zhuǎn)發(fā)的信息.

1.2 MPR的簡(jiǎn)介

1.2.1 MPR 的定義.OLSR 協(xié)議的核心是多點(diǎn)中繼技術(shù).多點(diǎn)中繼的思路是通過(guò)減少同一區(qū)域內(nèi)相同控制分組的重復(fù)轉(zhuǎn)發(fā)次數(shù)來(lái)減少網(wǎng)絡(luò)中廣播分組的數(shù)量.網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)選取其鄰節(jié)點(diǎn)的一個(gè)子集用于轉(zhuǎn)發(fā)該節(jié)點(diǎn)發(fā)送的控制分組，這些被選擇的節(jié)點(diǎn)就稱為MPR.由此可見(jiàn)，網(wǎng)絡(luò)中所有的節(jié)點(diǎn)可分為MPR 和非MPR.節(jié)點(diǎn)N 發(fā)送的廣播分組會(huì)通過(guò)MPR 轉(zhuǎn)發(fā)到達(dá)節(jié)點(diǎn)N 兩跳以外的節(jié)點(diǎn)，而非MPR 只能進(jìn)行讀取和處理，不能轉(zhuǎn)發(fā).

1.2.2 傳統(tǒng)OLSR 協(xié)議選擇MPR 集存在的問(wèn)題.

為了使用較少的數(shù)據(jù)轉(zhuǎn)發(fā)開(kāi)銷(xiāo)，獲得與全網(wǎng)泛洪一樣的數(shù)據(jù)傳輸效果，區(qū)分MPR 集和非MPR 集是廣播中繼泛洪的核心.圖1 中，節(jié)點(diǎn)N 向下一跳(節(jié)點(diǎn)a、b、c)發(fā)送廣播數(shù)據(jù).其中，節(jié)點(diǎn)b 的連接度最高，下一跳有5 個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)2、3、4、5、6)，因此b節(jié)點(diǎn)即為首選的MPR.對(duì)于節(jié)點(diǎn)N 的兩跳鄰居(節(jié)點(diǎn)1、7)只能分別通過(guò)節(jié)點(diǎn)N 的一跳鄰居a 和c 來(lái)接收廣播數(shù)據(jù).因此，節(jié)點(diǎn)a 和c 也為MPR.根據(jù)廣播中繼泛洪的思路，MPR={a，b，c}.

圖1 廣播中繼泛洪的特例

觀察圖1 可見(jiàn)，節(jié)點(diǎn)a 的下一跳為節(jié)點(diǎn)1、2、3，節(jié)點(diǎn)c 的下一跳為節(jié)點(diǎn)4、5、6、7.而節(jié)點(diǎn)1 ～7 恰好全部為節(jié)點(diǎn)N 的兩跳鄰居.因此，節(jié)點(diǎn)N 通過(guò)節(jié)點(diǎn)a、c，廣播數(shù)據(jù)同樣可以達(dá)到全網(wǎng)泛洪的數(shù)據(jù)傳輸效果.相比傳統(tǒng)的廣播中繼泛洪的方法，MPR = {a，c}，進(jìn)一步減少了數(shù)據(jù)轉(zhuǎn)發(fā)開(kāi)銷(xiāo).

2 重新定義MPR集的OLSR改進(jìn)方案

基于上述分析，本研究提出一種新的MPR 集選擇算法，其思路是:

(1)全網(wǎng)泛洪，在每一節(jié)點(diǎn)定義變量并賦值為0，為后續(xù)的位運(yùn)算做準(zhǔn)備，并設(shè)置MPR 集初值為空.

(2)對(duì)中心節(jié)點(diǎn)的鄰節(jié)點(diǎn)進(jìn)行組合，Cin，(i =1，2，3，…，n)，其中，n 為中心節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù).

(3)在每一次的組合中，凡是通過(guò)中心節(jié)點(diǎn)的鄰節(jié)點(diǎn)能被訪問(wèn)到的二跳鄰居全部自增1.

(4)對(duì)所有二跳鄰居進(jìn)行“與”運(yùn)算，結(jié)果若為0，則變量的值全部重置為0，該節(jié)點(diǎn)不為MRP 集;結(jié)果若為1，則組合中的節(jié)點(diǎn)即為MPR 集.

(5)重復(fù)步驟(2)，直到所有一跳節(jié)點(diǎn)遍歷完成，算法結(jié)束.

下面就圖1 情況進(jìn)行詳細(xì)說(shuō)明.

首先，將所有節(jié)點(diǎn)N 的二跳鄰居定義變量并賦值為0，然后將分支節(jié)點(diǎn)a、b、c 進(jìn)行組合，每一次組合即進(jìn)行一次循環(huán)，訪問(wèn)到一次終端節(jié)點(diǎn)便自增1，最后進(jìn)行按位“與”的運(yùn)算，結(jié)果為0 便進(jìn)行下一種組合的循環(huán)，直到“與”的運(yùn)算結(jié)果為非零，即表示通過(guò)此次組合的分支節(jié)點(diǎn)能轉(zhuǎn)發(fā)廣播數(shù)據(jù)到下一跳的所有鄰居.方法的具體實(shí)現(xiàn)步驟如下:

(1)首先從節(jié)點(diǎn)N 進(jìn)行訪問(wèn)，在訪問(wèn)到的所有二跳鄰居1 ～7 中分別定義變量TwoHopNeiI(I≤7，I∈N+)并賦予初值為0，然后將分支節(jié)點(diǎn)a、b、c 進(jìn)行組合，即，

(2)第一次循環(huán)，分支節(jié)點(diǎn)a.

通過(guò)分支節(jié)點(diǎn)a 訪問(wèn)它的后繼節(jié)點(diǎn)1、2、3.則節(jié)點(diǎn)中的變量TwoHopNeiI(I =1，2，3)自增1，結(jié)果為1.其他終端節(jié)點(diǎn)4 ～7 中變量的值不變，為0.然后進(jìn)行所有終端節(jié)點(diǎn)中變量“與”的運(yùn)算，即，

TwoHopNeiI(I=1，2，3)+ +;

TwoHopNeiI(I=4，5，6，7)= =0;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =0;

所有終端節(jié)點(diǎn)變量的值重置為0，進(jìn)行第二次循環(huán).

(3)第二次循環(huán)，分支節(jié)點(diǎn)b.

通過(guò)分支節(jié)點(diǎn)b 訪問(wèn)它的后繼節(jié)點(diǎn)2、3、4、5、6，則節(jié)點(diǎn)中的變量ChildI(I=2，3，4，5，6)自增1，結(jié)果為1，其他終端節(jié)點(diǎn)1、7 中變量的值不變，為0.然后進(jìn)行“與”的運(yùn)算，即，

TwoHopNeiI(I=2，3，4，5，6)+ +;

TwoHopNeiI(I=1，7)= =0;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =0;

所有終端節(jié)點(diǎn)變量的值重置為0，進(jìn)行第三次循環(huán).

(4)第三次循環(huán)，分支節(jié)點(diǎn)c.

同理，“與”結(jié)果為0，進(jìn)行第四次循環(huán).

(5)第四次循環(huán)，分支節(jié)點(diǎn)a、b.

通過(guò)分支節(jié)點(diǎn)a 訪問(wèn)它的后繼節(jié)點(diǎn)1、2、3，則節(jié)點(diǎn)中的變量ChildI(I =1，2，3)自增1，結(jié)果為1.通過(guò)分支節(jié)點(diǎn)b 訪問(wèn)它的后繼節(jié)點(diǎn)2、3、4、5、6，則節(jié)點(diǎn)中的變量ChildI(I =1，4，5，6)自增1，結(jié)果為1.而終端節(jié)點(diǎn)2、3 自增2 次，結(jié)果為2.剩余終端節(jié)點(diǎn)7 中變量的值不變，為0.“與”的結(jié)果為，

TwoHopNeiI(I=1，2，3)+ +;

TwoHopNeiI(I=2，3，4，5，6)+ +;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =0;

“與”結(jié)果為0，進(jìn)行第五次循環(huán).

(6)第五次循環(huán)，分支節(jié)點(diǎn)a、c.

通過(guò)分支節(jié)點(diǎn)a 訪問(wèn)它的后繼節(jié)點(diǎn)1、2、3，則節(jié)點(diǎn)中的變量ChildI(I =1，2，3)自增1，結(jié)果為1.通過(guò)分支節(jié)點(diǎn)c 訪問(wèn)它的后繼節(jié)點(diǎn)4、5、6、7，則節(jié)點(diǎn)中的變量ChildI(I =4，5，6，7)自增1，結(jié)果為1.此次進(jìn)行“與”的運(yùn)算結(jié)果為，

TwoHopNeiI(I=1，2，3)+ +;

TwoHopNeiI(I=4，5，6，7)+ +;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =1;

結(jié)果非零，跳出循環(huán).

所以，MPR={a，c}.

3 實(shí) 驗(yàn)

本實(shí)驗(yàn)通過(guò)仿真平臺(tái)進(jìn)行，本研究參考Ad hoc網(wǎng)絡(luò)模型，在OPNET 網(wǎng)絡(luò)仿真軟件中實(shí)現(xiàn).

1)仿真參數(shù)的設(shè)置.網(wǎng)絡(luò)覆蓋面積，3 ×3 km2;節(jié)點(diǎn)個(gè)數(shù)，25 個(gè);節(jié)點(diǎn)的通信距離，300 m;信號(hào)的傳輸速度，0.5 Mb/s.

2)底層MAC 采用IEEE802.11 協(xié)議，以CSMA/CA 方式接入，物理層采用擴(kuò)頻跳頻方式，網(wǎng)絡(luò)層采用表驅(qū)動(dòng)路由協(xié)議OLSR 協(xié)議.

實(shí)驗(yàn)仿真了網(wǎng)絡(luò)在改進(jìn)前后的數(shù)據(jù)傳輸成功率及數(shù)據(jù)傳輸時(shí)延，實(shí)驗(yàn)結(jié)果如圖2、3 所示.

圖2 數(shù)據(jù)傳輸成功率對(duì)比

圖3 數(shù)據(jù)傳輸時(shí)延對(duì)比

從圖2、3 可以看出，200 s 內(nèi)，數(shù)據(jù)傳輸成功率明顯提升，數(shù)據(jù)傳輸時(shí)延顯著減少.此表明，采用組合數(shù)和按位“與”運(yùn)算相結(jié)合的方法尋找最簡(jiǎn)MPR集不僅能達(dá)到傳統(tǒng)OLSR 協(xié)議的目的，并且能有效地找出特殊情況的MPR 集，從而減少不必要的數(shù)據(jù)轉(zhuǎn)發(fā)開(kāi)銷(xiāo)，使其具有高效性.

4 結(jié) 論

本研究所提的方法不僅能滿足傳統(tǒng)OLSR 協(xié)議的目標(biāo)，即區(qū)分MPR 集和非MPR 集，使用較少的數(shù)據(jù)轉(zhuǎn)發(fā)開(kāi)銷(xiāo)，獲得與全網(wǎng)泛洪的數(shù)據(jù)傳輸效果，而且能有效地解決傳統(tǒng)OLSR 協(xié)議選擇MPR 集存在的問(wèn)題.對(duì)于非特殊情況的全網(wǎng)泛洪，通過(guò)訪問(wèn)組合后1 跳鄰居的后繼節(jié)點(diǎn)以及按位進(jìn)行“與”的運(yùn)算能有效判斷該種組合是否能達(dá)到泛洪全網(wǎng)的效果，從而有效區(qū)分出MPR 集與非MPR 集.

［1］周懿，郭偉，任智.戰(zhàn)術(shù)互聯(lián)網(wǎng)中的OLSR 路由協(xié)議研究［J］.電子技術(shù)，2004，37(3):11－19.

［2］張信明，曾依靈，干國(guó)政，等.用遺傳算法尋找OLSR 協(xié)議的最小MPR 集［J］.軟件學(xué)報(bào)，2006，17(4):932－938.

［3］盧宇，魏敏，吳欽章.基于MAC 層信息的OLSR 改進(jìn)方案［J］.計(jì)算機(jī)工程，2007，33(22):121－123.

［4］陳文宇，陳潔蓮，孫世新.面向鏈路狀態(tài)信息的路由算法LSDSR［J］.電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，38(6):993－996.

［5］張洪，黃閩英.基于高速移動(dòng)節(jié)點(diǎn)網(wǎng)絡(luò)的OLSR 路由協(xié)議改進(jìn)［J］.成都大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，27(1):38－40.