張 洪，王傳真，陳海霞，葉 雪，羅 陽

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

0 引 言

Ad Hoc 網(wǎng)是一種多跳的、無中心的自組織無線網(wǎng)絡(luò)，又稱為多跳網(wǎng)(Multi-hop Network)或自組織網(wǎng)(Self-organizing Network)［1］.整個網(wǎng)絡(luò)沒有固定的基礎(chǔ)設(shè)施，每個節(jié)點都是移動的，并且都能以任意方式動態(tài)地保持與其他節(jié)點的聯(lián)系.OLSR［2］協(xié)議是一個重要的MANET 路由協(xié)議，而支撐此協(xié)議的關(guān)鍵技術(shù)在于MPR.對此，張信明等［3］通過采用不同遺傳策略將此遺傳算法衍生成了4 個序列算法，并在隨機生成的拓撲上對其進行模擬，取得了一些成果，但該遺傳算法的編程實現(xiàn)比較復雜;鐘珞等［4］將蟻群優(yōu)化用于最小MPR 集選取問題的求解，給出了一種基于候選解的改進蟻群算法CSACO，但由于蟻群算法利用信息的正反饋特點，容易使結(jié)果陷入局部最優(yōu)解.在此基礎(chǔ)上，本研究提出了一種改進方案，以此尋找最小MPR 集，并通過仿真驗證了改進方案的有效性.

1 OLSR 特點

OLSR 是一種先應式鏈路狀態(tài)路由協(xié)議，主要應用于MANET 網(wǎng)絡(luò)［5］，并根據(jù)MANET 的要求在傳統(tǒng)的LS(Link State)協(xié)議的基礎(chǔ)上進行優(yōu)化，其關(guān)鍵在于多點轉(zhuǎn)播(Multi Point Relays，MPRS).它對于傳統(tǒng)的LS 協(xié)議做出的優(yōu)化有:

1)僅選擇部分節(jié)點作為中繼節(jié)點來控制分組，這樣做減小了控制分組的洪泛范圍.因為任一節(jié)點僅選擇部分鄰節(jié)點作為它的中繼節(jié)點，而也只有中繼節(jié)點才能轉(zhuǎn)發(fā)和控制分組，其余鄰節(jié)點只處理收到的分組信息而不轉(zhuǎn)發(fā)，所有被選中轉(zhuǎn)發(fā)和控制分組的鄰節(jié)點被稱為中繼節(jié)點MPRS.

2)縮減控制分組的大小.節(jié)點并不發(fā)布與所有相鄰節(jié)點的鏈路狀態(tài)信息，而是只發(fā)送與它相鄰MPR 點之間的鏈路狀態(tài)信息.

2 傳統(tǒng)OLSR 的局限性

2.1 傳統(tǒng)MPR 選擇

傳統(tǒng)的OLSR 路由協(xié)議采用2 種方法來減少由于鏈路狀態(tài)信息洪泛所帶來的路由開銷.第一種方法是采用多點中繼，每個節(jié)點在自己的一跳鄰居節(jié)點中選擇一部分節(jié)點作為自己的MPR，由MPR 而不是所有的一跳鄰居節(jié)點轉(zhuǎn)發(fā)鏈路狀態(tài)消息，通過MPR 實現(xiàn)路由控制消息的選擇性洪泛;第二種方法是鏈路狀態(tài)信息的壓縮［6］，鏈路狀態(tài)信息只是描述MPR 選擇節(jié)點(MPR Selector)與MPR 之間的鏈路，而不是與所有的一跳鄰居節(jié)點的鏈路.而在選擇MPR 時，經(jīng)典的OLSR 路由協(xié)議采用以連接度為參考標準的算法.

2.2 傳統(tǒng)MPR 選擇的問題

由于傳統(tǒng)OLSR 路由協(xié)議只計算跳數(shù)最短路徑，而且路由協(xié)議只是盡力而為地傳輸數(shù)據(jù)分組，沒有考慮網(wǎng)絡(luò)中間節(jié)點的擁塞情況和無線鏈路的實際狀態(tài)，所以選擇的MPR 集不一定是最小的.因此，傳統(tǒng)OLSR 路由協(xié)議已經(jīng)無法滿足移動Ad Hoc 網(wǎng)絡(luò)提供更高質(zhì)量和更多種類業(yè)務的要求.

3 MPR 選擇的改進

3.1 傳統(tǒng)選擇產(chǎn)生的問題

傳統(tǒng)MPR 選擇節(jié)點如圖1 所示，具體步驟如下:

1)選取唯一的二跳鄰居，將其所在的一跳鄰居所包含的所有二跳從整個二跳鄰居中去除，得到MPR 節(jié)點集合{e，f}.

2)對剩下的二跳鄰居進行最大連接度選擇直至二跳鄰居為空，最終得到的MPR 節(jié)點集合{e，f，b，c，a}.

圖1 傳統(tǒng)MPR 節(jié)點選擇算法示意圖

對于圖1，理論最優(yōu)的MPR 節(jié)點數(shù)為4，即MPR節(jié)點集合{f，e，a，c}.如何尋找數(shù)量最優(yōu)的MPR 節(jié)點成為本研究的關(guān)鍵.

3.2 MPR 選擇改進方案出發(fā)點

本研究改進方案的出發(fā)點是，從集合問題的角度看待網(wǎng)絡(luò)中的鄰居關(guān)系，具體如圖2 所示.

圖2 網(wǎng)絡(luò)示例

對于一個基本的網(wǎng)絡(luò)可將其分成3 種集合:①A的二跳鄰居集合SEC{1，2，3，4，5，6，7，8，9};②一跳鄰居集合FIR{a，b，c，d，e};③每個一跳鄰居a(或b，…)所存在的集合a{7，8，9}.具體如圖3 所示.

3.3 方案思路

本方案的思路是為尋找唯一的二跳鄰居，從而選出MPR，并保證選出的MPR 節(jié)點數(shù)是最少的.該方法與傳統(tǒng)方法的不同之處在于傳統(tǒng)第二步是找最大連接度的一跳鄰居作為MPR，而本方法將繼續(xù)沿用尋找唯一的方法進行下去直至二跳鄰居SEC{1，2，3，…，n}為空.

圖3 集合劃分示意圖

顯然，進行完第一次MPR 節(jié)點的選取后所剩下的二跳鄰居點，沒有一個二跳鄰居是唯一屬于一跳鄰居的.圖4 為第一次選擇后的結(jié)果.

圖4 一次選擇結(jié)果示意圖

圖5 集合關(guān)系示意圖

對此，將圖4 以集合關(guān)系抽象成圖5，其中包含集合g{1}，a{1，2，3，4}，b{2，3，4，5，6}，c{5，6，7，8}，d{7，8}以及二跳鄰居集合SEC{1，2，3，4，5，6，7，8}和一跳鄰居FIR{g，a，b，c，d}.這些集合出現(xiàn)了一些冗余狀況(即集合中的包含狀況，a 包含g，將g去除，但不去除g 的子集)，當將冗余集合去除后會得到圖6 所示的情況，此時問題已解決，圖6 已變?yōu)榛厩闆r，通過找唯一二跳(理論唯一二跳)就可解決.由此可得到一個結(jié)論:去除冗余集合后不一定會得到唯一二跳，但唯一二跳一定出現(xiàn)在冗余處.

3.4 應用于網(wǎng)絡(luò)的算法架構(gòu)

本研究所提方案的算法整體架構(gòu)為:

1)檢查SEC{1，2，3，…，n}是否為空.

圖6 冗余去除示意圖

2)唯一二跳(即唯一點)節(jié)點的尋找.為SEC{1，2，3，…，n}每一個元素賦予初始權(quán)重0，從FIR{a，b，c，…}中讀取每個子集合的元素并給予其權(quán)重加1，讀取結(jié)束后查找權(quán)重為1 的元素，并將其所在的集合從FIR{a，b，c，…}中去除，然后重置權(quán)重.當尋找到一個唯一點會涉及到信號量(環(huán)狀網(wǎng)絡(luò)的判斷量)的變化，初始值為0，然后變換狀態(tài)加1，不重置.

3)利用信號量判斷是否為環(huán)狀網(wǎng)絡(luò).SEC{1，2，3，…}中所有元素的權(quán)重都大于1，進行冗余去除.

4)網(wǎng)絡(luò)為環(huán)狀網(wǎng)絡(luò)，SEC{1，2，3，…，n}，所有元素的權(quán)重都大于2.

步驟一.去除冗余集合，為了防止網(wǎng)絡(luò)是復雜的環(huán)狀網(wǎng)絡(luò)(即SEC{1，2，3，…，n}中每一元素權(quán)重都大于2).

步驟二.當SEC{1，2，3，…，n}中所有元素的權(quán)重為2 時，才強行打破環(huán)狀網(wǎng)絡(luò)以保證算法的運行.打破時可隨機選取FIR{a，b，c，…}中的一個元素，將其去除，而不去除其所包含集合的子元素(強行打破環(huán)狀網(wǎng)絡(luò)可以保證其以后所選MPR 節(jié)點數(shù)一定最少.事實上，偶數(shù)形式的環(huán)狀網(wǎng)絡(luò)，無論打破哪一個，得到的MPR 節(jié)點數(shù)=N(N 為一跳鄰居數(shù))/2，而奇數(shù)環(huán)狀網(wǎng)絡(luò)，MPR 節(jié)點數(shù)=(N+1)/2).

具體應用中，環(huán)狀網(wǎng)絡(luò)現(xiàn)象并不多見，而且打破環(huán)的操作最多只執(zhí)行一次.

上述方案中，去除冗余集合(去除被包含的集合)得到的MPR 節(jié)點數(shù)一定為最少.如果一個集合包含子集，必須將冗余子集去除，因為如果能選取子集作為MPR.很顯然，選取包含該子集的更大的集合將其選為MPR 才是最好的選擇，從而保證MPR節(jié)點數(shù)量最少.

4 仿真及結(jié)果分析

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

仿真參數(shù)的設(shè)置為:

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

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

圖7 所示為數(shù)據(jù)傳輸成功率對比，從曲線的走勢可以看出，在網(wǎng)絡(luò)建立初期，改進算法成功率略低于傳統(tǒng)算法，但隨時間的推移與網(wǎng)絡(luò)的完善，改進算法的優(yōu)勢體現(xiàn)得更明顯.

圖7 數(shù)據(jù)傳輸成功率

圖8 為傳輸時延對比，在傳輸時延方面，改進算法直接降低了數(shù)據(jù)的傳輸時延，并比傳統(tǒng)算法一直保持穩(wěn)定的優(yōu)勢.

圖8 數(shù)據(jù)傳輸時延

5 結(jié) 論

本研究從數(shù)學集合的角度分析了MPR 的選擇問題，通過將一跳鄰居節(jié)點及其所連接的一跳鄰居節(jié)點抽象化為包含子集的集合，計算剩余集合的獨立子集生成MPR 中繼節(jié)點，從而找到節(jié)點數(shù)量最少的MPR 集，該方法比較適合節(jié)點運動速度比較快、節(jié)點密度比較大的網(wǎng)絡(luò).仿真實驗表明，本算法能夠?qū)?shù)據(jù)傳輸時延和成功率有顯著改進.

［1］張洪.高速移動自組網(wǎng)OLSR 路由協(xié)議研究與改進［D］.成都:西南交通大學，2007.

［2］Shamsi M，Saad P B，Ibrahim S B，et al.Fast algorithm for iris localization using daugman circular integro differential operator［C］//Proc of the 2009 International Conference on Soft Computing and Pattern Recognition.Washington，DC:IEEE Computer Society，2009:393－398.

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

［4］鐘珞，趙先明，夏紅霞.求解最小MPR 集的蟻群算法與仿真［J］.智能系統(tǒng)學報，2011，6(2):166－171.

［5］張可，張偉，李煒，等.ad hoc 網(wǎng)絡(luò)先應式路由維護機制的優(yōu)化模型研究［J］.電子學報，2006，34(1):114－118.

［6］秦軍，蘇志和，張海鵬.一種基于組合度量的OLSR 擴展鏈路狀態(tài)路由協(xié)議［J］.計算機技術(shù)與發(fā)展，2013，23(4):47－50.