基于最優(yōu)子集的MPR選擇算法研究

張 洪，王傳真，陳海霞，葉 雪，羅 陽(yáng)

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

0 引 言

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

1 OLSR 特點(diǎn)

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

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

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

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

2.1 傳統(tǒng)MPR 選擇

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

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

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

3 MPR 選擇的改進(jìn)

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

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

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

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

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

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

3.2 MPR 選擇改進(jìn)方案出發(fā)點(diǎn)

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

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

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

3.3 方案思路

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

圖3 集合劃分示意圖

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

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

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

對(duì)此，將圖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 的子集)，當(dāng)將冗余集合去除后會(huì)得到圖6 所示的情況，此時(shí)問(wèn)題已解決，圖6 已變?yōu)榛厩闆r，通過(guò)找唯一二跳(理論唯一二跳)就可解決.由此可得到一個(gè)結(jié)論:去除冗余集合后不一定會(huì)得到唯一二跳，但唯一二跳一定出現(xiàn)在冗余處.

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

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

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

圖6 冗余去除示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

［1］張洪.高速移動(dòng)自組網(wǎng)OLSR 路由協(xié)議研究與改進(jìn)［D］.成都:西南交通大學(xué)，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］張信明，曾依靈，干國(guó)政，等.用遺傳算法尋找OLSR 協(xié)議的最小MPR 集［J］.軟件學(xué)報(bào)，2006，17(4):932－939.

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

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

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