基于最優子集的MPR選擇算法研究

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

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

0 引 言

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

1 OLSR 特點

OLSR 是一種先應式鏈路狀態路由協議，主要應用于MANET 網絡［5］，并根據MANET 的要求在傳統的LS(Link State)協議的基礎上進行優化，其關鍵在于多點轉播(Multi Point Relays，MPRS).它對于傳統的LS 協議做出的優化有:

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

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

2 傳統OLSR 的局限性

2.1 傳統MPR 選擇

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

2.2 傳統MPR 選擇的問題

由于傳統OLSR 路由協議只計算跳數最短路徑，而且路由協議只是盡力而為地傳輸數據分組，沒有考慮網絡中間節點的擁塞情況和無線鏈路的實際狀態，所以選擇的MPR 集不一定是最小的.因此，傳統OLSR 路由協議已經無法滿足移動Ad Hoc 網絡提供更高質量和更多種類業務的要求.

3 MPR 選擇的改進

3.1 傳統選擇產生的問題

傳統MPR 選擇節點如圖1 所示，具體步驟如下:

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

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

圖1 傳統MPR 節點選擇算法示意圖

對于圖1，理論最優的MPR 節點數為4，即MPR節點集合{f，e，a，c}.如何尋找數量最優的MPR 節點成為本研究的關鍵.

3.2 MPR 選擇改進方案出發點

本研究改進方案的出發點是，從集合問題的角度看待網絡中的鄰居關系，具體如圖2 所示.

圖2 網絡示例

對于一個基本的網絡可將其分成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 節點數是最少的.該方法與傳統方法的不同之處在于傳統第二步是找最大連接度的一跳鄰居作為MPR，而本方法將繼續沿用尋找唯一的方法進行下去直至二跳鄰居SEC{1，2，3，…，n}為空.

圖3 集合劃分示意圖

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

圖4 一次選擇結果示意圖

圖5 集合關系示意圖

對此，將圖4 以集合關系抽象成圖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}.這些集合出現了一些冗余狀況(即集合中的包含狀況，a 包含g，將g去除，但不去除g 的子集)，當將冗余集合去除后會得到圖6 所示的情況，此時問題已解決，圖6 已變為基本情況，通過找唯一二跳(理論唯一二跳)就可解決.由此可得到一個結論:去除冗余集合后不一定會得到唯一二跳，但唯一二跳一定出現在冗余處.

3.4 應用于網絡的算法架構

本研究所提方案的算法整體架構為:

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

圖6 冗余去除示意圖

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

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

4)網絡為環狀網絡，SEC{1，2，3，…，n}，所有元素的權重都大于2.

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

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

具體應用中，環狀網絡現象并不多見，而且打破環的操作最多只執行一次.

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

4 仿真及結果分析

本仿真實驗通過仿真平臺(OPNET)，參考Ad Hoc 的網絡模型，在OPNET 網絡仿真軟件中實現.

仿真參數的設置為:

1)網絡覆蓋面積，4 ×4 km2;節點個數，30;節點的通信距離，300 m;信號的傳輸速度，0.5 Mb/s.

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

圖7 所示為數據傳輸成功率對比，從曲線的走勢可以看出，在網絡建立初期，改進算法成功率略低于傳統算法，但隨時間的推移與網絡的完善，改進算法的優勢體現得更明顯.

圖7 數據傳輸成功率

圖8 為傳輸時延對比，在傳輸時延方面，改進算法直接降低了數據的傳輸時延，并比傳統算法一直保持穩定的優勢.

圖8 數據傳輸時延

5 結 論

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

［1］張洪.高速移動自組網OLSR 路由協議研究與改進［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 協議的最小MPR 集［J］.軟件學報，2006，17(4):932－939.

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

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

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