一種新型MPR集選擇算法

張 洪，高 楊

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

0 引 言

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

1 OLSR與MPR簡介

1.1 OLSR簡介

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

1.2 MPR的簡介

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

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

為了使用較少的數據轉發(fā)開銷，獲得與全網泛洪一樣的數據傳輸效果，區(qū)分MPR 集和非MPR 集是廣播中繼泛洪的核心.圖1 中，節(jié)點N 向下一跳(節(jié)點a、b、c)發(fā)送廣播數據.其中，節(jié)點b 的連接度最高，下一跳有5 個節(jié)點(節(jié)點2、3、4、5、6)，因此b節(jié)點即為首選的MPR.對于節(jié)點N 的兩跳鄰居(節(jié)點1、7)只能分別通過節(jié)點N 的一跳鄰居a 和c 來接收廣播數據.因此，節(jié)點a 和c 也為MPR.根據廣播中繼泛洪的思路，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，廣播數據同樣可以達到全網泛洪的數據傳輸效果.相比傳統(tǒng)的廣播中繼泛洪的方法，MPR = {a，c}，進一步減少了數據轉發(fā)開銷.

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

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

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

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

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

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

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

下面就圖1 情況進行詳細說明.

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

(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，結果為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，結果為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.

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

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

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

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

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

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

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

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

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

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

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

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

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

所以，MPR={a，c}.

3 實 驗

本實驗通過仿真平臺進行，本研究參考Ad hoc網絡模型，在OPNET 網絡仿真軟件中實現.

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

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

實驗仿真了網絡在改進前后的數據傳輸成功率及數據傳輸時延，實驗結果如圖2、3 所示.

圖2 數據傳輸成功率對比

圖3 數據傳輸時延對比

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

4 結 論

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

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

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

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

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

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