張 洪，高 楊

(1.成都大學(xué) 計算機學(xué)院，四川 成都 610106;2.成都大學(xué) 模式識別與智能信息處理四川省高校重點實驗室，四川 成都 610106)

0 引 言

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

1 OLSR與MPR簡介

1.1 OLSR簡介

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

1.2 MPR的簡介

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

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

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

圖1 廣播中繼泛洪的特例

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

2 重新定義MPR集的OLSR改進方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過分支節(jié)點a 訪問它的后繼節(jié)點1、2、3，則節(jié)點中的變量ChildI(I =1，2，3)自增1，結(jié)果為1.通過分支節(jié)點c 訪問它的后繼節(jié)點4、5、6、7，則節(jié)點中的變量ChildI(I =4，5，6，7)自增1，結(jié)果為1.此次進行“與”的運算結(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 實 驗

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

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

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

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