密集MANET 下MPR 的改進(jìn)蟻群優(yōu)化算法研究

趙啟超，楊余旺，謝勇盛，湯小芳，李 操

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094）

0 概述

移動(dòng)自組網(wǎng)（Mobile Ad-hoc Network，MANet）是由一系列對(duì)等通信節(jié)點(diǎn)組成的分散式網(wǎng)絡(luò)［1］，該網(wǎng)絡(luò)無(wú)中心控制節(jié)點(diǎn)且節(jié)點(diǎn)間相互獨(dú)立，旨在不依賴預(yù)先存在的基礎(chǔ)架構(gòu)下提供網(wǎng)絡(luò)無(wú)線服務(wù)［2］。隨著網(wǎng)絡(luò)設(shè)備的不斷增加，自組網(wǎng)已經(jīng)延伸至各行各業(yè)，而人群的聚集與流動(dòng)性通常給自組網(wǎng)帶來(lái)巨大的挑戰(zhàn)，密集型移動(dòng)自組網(wǎng)中由于節(jié)點(diǎn)數(shù)目龐大且分組數(shù)量繁多，易導(dǎo)致網(wǎng)絡(luò)擁塞甚至癱瘓，因此研究適用于密集流動(dòng)型復(fù)雜場(chǎng)景的路由協(xié)議對(duì)于改善網(wǎng)絡(luò)性能具有重要的意義。

優(yōu)化鏈路狀態(tài)（Optimized Link State Routing，OLSR）協(xié)議中多點(diǎn)中繼（Multi-Point Relay，MPR）機(jī)制［3］有效抑制了消息開銷，每個(gè)節(jié)點(diǎn)在接收到消息時(shí)都會(huì)重傳消息，而MPR 機(jī)制中的消息僅由被選為MPR 的節(jié)點(diǎn)轉(zhuǎn)發(fā)，實(shí)現(xiàn)了控制消息數(shù)量的優(yōu)化，使得OLSR 協(xié)議在密集MANET 中具有很好的應(yīng)用。傳統(tǒng)的MPR 機(jī)制使用貪心算法，二跳節(jié)點(diǎn)覆蓋數(shù)多的鄰居被優(yōu)先選為MPR，這導(dǎo)致MPR 集合存在較大冗余且網(wǎng)絡(luò)越密集發(fā)生的概率越大。

蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［4］是一種來(lái)自于模仿螞蟻覓食而得到的群體智能優(yōu)化啟發(fā)式算法［5-7］。該算法的優(yōu)勢(shì)在于其搜索的隨機(jī)性，而傳統(tǒng)貪心算法沒有進(jìn)行全局檢測(cè)，僅限于當(dāng)前最優(yōu)。ACO 算法利用隨機(jī)概率選擇下一路徑，但由于信息素和權(quán)值等因素的影響，導(dǎo)致某一路徑的選擇概率大幅增加，當(dāng)概率增加到1 時(shí)，蟻群算法退化為傳統(tǒng)貪心算法，將會(huì)陷入某一局部最優(yōu)解。啟發(fā)式蟻群算法在貪心算法基礎(chǔ)上有所改進(jìn)，但仍存在迭代時(shí)間過(guò)長(zhǎng)而容易陷入局部最優(yōu)解等缺陷［8-9］。針對(duì)MPR 貪心機(jī)制的局限性，本文結(jié)合ACO 算法的全局搜索能力對(duì)原有ACO 算法的路徑選擇以及狀態(tài)更新機(jī)制進(jìn)行改進(jìn)，從而將該算法應(yīng)用到MPR 問(wèn)題中，達(dá)到優(yōu)化MPR 求解集合的目的。

1 相關(guān)工作

為解決MPR 節(jié)點(diǎn)的高能耗問(wèn)題，文獻(xiàn)［10-11］提出一種基于剩余能量與可達(dá)性的計(jì)算方法，該方法對(duì)節(jié)點(diǎn)能量的消耗進(jìn)行優(yōu)化，但是存在對(duì)MPR 的求解精度欠佳的問(wèn)題。與其不同的是，文獻(xiàn)［12］在追求網(wǎng)絡(luò)服務(wù)質(zhì)量的前提下提出了Min-Max 算法，并通過(guò)最大信號(hào)范圍選擇MPR 節(jié)點(diǎn)，使得在MPR 集合求解準(zhǔn)確率上有所改進(jìn)。文獻(xiàn)［13］利用原始算法的優(yōu)勢(shì)，并引入三跳鄰居的本地?cái)?shù)據(jù)庫(kù)加入MPR 的附加決策函數(shù)，達(dá)到進(jìn)一步優(yōu)化MPR 的目的，但是由于三跳鄰居被考慮入MPR 選擇時(shí)會(huì)造成計(jì)算量成倍增大的問(wèn)題。為提高密集MANET 下的MPR 計(jì)算速度，文獻(xiàn)［14］利用一種協(xié)作式MPR 選擇程序允許節(jié)點(diǎn)的選擇過(guò)程獨(dú)立于其鄰居節(jié)點(diǎn)進(jìn)行，該算法實(shí)質(zhì)為節(jié)點(diǎn)的分布計(jì)算，并不能達(dá)到滿意的結(jié)果。最小MPR 問(wèn)題是一個(gè)NP 完全問(wèn)題，可采用群體智能方法進(jìn)行解決［15］。蟻群優(yōu)化算法被引入MPR 問(wèn)題進(jìn)行求解［16］時(shí)取得了良好的效果，但其采用傳統(tǒng)的狀態(tài)更新機(jī)制在迭代速度與求解精度上尚有不足。

ACO 算法已應(yīng)用于多種領(lǐng)域，目前已有很多研究人員針對(duì)不同問(wèn)題對(duì)蟻群算法進(jìn)行相應(yīng)的改進(jìn)，比如文獻(xiàn)［17］將變異機(jī)制引入蟻群算法以改善迭代時(shí)間過(guò)長(zhǎng)的缺陷。文獻(xiàn)［18］提出一種自適應(yīng)調(diào)整信息素的蟻群算法，有助于算法跳離局部最優(yōu)解。文獻(xiàn)［19］在處理資源受限的項(xiàng)目調(diào)度問(wèn)題時(shí)，提出一種用兩種信息素組合的綜合評(píng)估方法，處理該問(wèn)題時(shí)較其他算法具有更優(yōu)的性能表現(xiàn)。文獻(xiàn)［20］從蟻群數(shù)目方面著手，利用多個(gè)蟻群進(jìn)行相對(duì)競(jìng)爭(zhēng)求解，并將其用于車輛路徑問(wèn)題，可實(shí)現(xiàn)對(duì)多路線進(jìn)行同步搜索，并有效降低局部最優(yōu)概率。文獻(xiàn)［21］利用目標(biāo)地址泛洪負(fù)載信息的方法來(lái)模擬食物氣味散發(fā)的過(guò)程，該方法可使得每個(gè)節(jié)點(diǎn)獲得服務(wù)器與鏈路的最新信息，從而加快算法的迭代速度。文獻(xiàn)［22］將ACO 算法應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域中，并提取出一種基于規(guī)則的分類器。該分類器使用一種基于螞蟻的分類技術(shù)AntMiner+為蟻群提供了明確定義，且具有處理多類問(wèn)題以及包括間隔規(guī)則的能力，改善了局部最優(yōu)解的情況。基于此，文獻(xiàn)［23］開發(fā)出包括基于ACO 的特征選擇和數(shù)據(jù)分類的金融危機(jī)預(yù)測(cè)模型，以進(jìn)一步優(yōu)化局部最優(yōu)解和改善分類性能。目前ACO 改進(jìn)算法針對(duì)不同的目標(biāo)，優(yōu)化策略也隨之變化，但實(shí)際上其改進(jìn)策略可歸結(jié)為對(duì)蟻群尋路算法以及狀態(tài)更新機(jī)制的改進(jìn)，多數(shù)尋路算法根據(jù)不同的應(yīng)用場(chǎng)景，選取相應(yīng)的啟發(fā)參數(shù)來(lái)追求全局搜索能力與完善正反饋機(jī)制。對(duì)于狀態(tài)更新機(jī)制，多數(shù)改進(jìn)算法僅使用某種信息素更新規(guī)則，忽略了錯(cuò)誤路徑信息素的過(guò)度增長(zhǎng)問(wèn)題，從而導(dǎo)致算法迭代速度下降。

蟻群算法的群體智能特性使得其在各種優(yōu)化問(wèn)題上具有良好的應(yīng)用，本文將蟻群優(yōu)化算法與MPR選擇問(wèn)題相結(jié)合，并在ACO 算法基礎(chǔ)上進(jìn)行改進(jìn)，提出基于狀態(tài)信息的動(dòng)態(tài)更新ACO（Dynamic Update ACO，DUACO）算法。利用源節(jié)點(diǎn)到其一跳與二跳鄰居集合來(lái)構(gòu)建路徑，通過(guò)蟻群選路的形式進(jìn)行MPR 節(jié)點(diǎn)的選擇?？紤]到MANET 中的節(jié)點(diǎn)移動(dòng)性問(wèn)題，在ACO 的路徑選擇概率基礎(chǔ)上，本文將節(jié)點(diǎn)的移動(dòng)性指標(biāo)加入計(jì)算。此外，本文利用一種狀態(tài)信息動(dòng)態(tài)更新的規(guī)則，并引入補(bǔ)償-懲罰機(jī)制用于相應(yīng)地提升和抑制正確和錯(cuò)誤節(jié)點(diǎn)的信息素增長(zhǎng)。通過(guò)對(duì)比DUACO 算法、傳統(tǒng)貪心算法和ACO 算法，驗(yàn)證DUACO 算法提高了收斂速度并解決蟻群算法易陷入局部最優(yōu)的問(wèn)題，且可有效改善MANET 網(wǎng)絡(luò)性能。

2 MPR 問(wèn)題描述

多點(diǎn)中繼的原理是在轉(zhuǎn)發(fā)廣播數(shù)據(jù)包時(shí)減少重復(fù)轉(zhuǎn)發(fā)的次數(shù)，它能夠?qū)⒄嬲D(zhuǎn)發(fā)數(shù)據(jù)分組的節(jié)點(diǎn)變?yōu)樵修D(zhuǎn)發(fā)節(jié)點(diǎn)的子集。每個(gè)節(jié)點(diǎn)都從自身的一跳鄰居節(jié)點(diǎn)中選取出某些節(jié)點(diǎn)作為MPR 節(jié)點(diǎn)，該節(jié)點(diǎn)為其轉(zhuǎn)發(fā)數(shù)據(jù)分組，可以看出MPR 節(jié)點(diǎn)的數(shù)量直接影響了數(shù)據(jù)分組轉(zhuǎn)發(fā)的數(shù)量。因此MPR 節(jié)點(diǎn)的數(shù)量應(yīng)盡可能地少，以達(dá)到減少數(shù)據(jù)包重傳的目的。

OLSR 協(xié)議中傳統(tǒng)的網(wǎng)絡(luò)泛洪機(jī)制為MPR，每個(gè)節(jié)點(diǎn)都會(huì)定期地更新自身的MPR 集合。MPR 問(wèn)題可被描述為：給定節(jié)點(diǎn)集合N1={N11，N12，…，N1m}，N2={N21，N22，…，N2n}，N1 為源節(jié)點(diǎn)的一跳鄰居集合，N2 為源節(jié)點(diǎn)的二跳鄰居集合。假設(shè)cover(N)為節(jié)點(diǎn)集N在N2 中的覆蓋集，算法的目的是在保證cover(N)等于N2 的前提下，使得|N|最小，即：

3 傳統(tǒng)MPR 算法

OLSR 協(xié)議中只有被選為MPR 的節(jié)點(diǎn)才具有轉(zhuǎn)發(fā)消息的權(quán)利，其余節(jié)點(diǎn)對(duì)接收到的消息進(jìn)行處理或丟棄操作，并不進(jìn)行轉(zhuǎn)發(fā)處理。因此，MPR 集合的大小很大程度上影響了網(wǎng)絡(luò)的負(fù)載能力。MPR選擇算法的具體步驟如下：

步驟1源節(jié)點(diǎn)的MPR 集合從源節(jié)點(diǎn)一跳鄰居中轉(zhuǎn)發(fā)意愿為WILL_ALWAYS 的節(jié)點(diǎn)所組成的集合中待選。

步驟2計(jì)算一跳鄰居節(jié)點(diǎn)的度數(shù)，一個(gè)節(jié)點(diǎn)的度數(shù)是指該節(jié)點(diǎn)的對(duì)稱鄰居節(jié)點(diǎn)的數(shù)目，但不包括執(zhí)行計(jì)算的源節(jié)點(diǎn)。

步驟3如果某個(gè)二跳鄰居節(jié)點(diǎn)只能被某個(gè)一跳鄰居所覆蓋（對(duì)稱鏈接關(guān)系），那么將該一跳鄰居加入到MPR 集合中，并從二跳鄰居集中去除那些可以被MPR 集合中節(jié)點(diǎn)覆蓋掉的節(jié)點(diǎn)。

步驟4對(duì)于二跳鄰居中被多個(gè)一跳鄰居覆蓋的節(jié)點(diǎn)，應(yīng)該按照以下優(yōu)先級(jí)進(jìn)行考慮：

1）根據(jù)一跳鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)意愿等級(jí)，等級(jí)高的優(yōu)先加入。

2）等級(jí)相同的按照節(jié)點(diǎn)的可達(dá)性（在N2 中覆蓋且未被MPR 集合覆蓋的節(jié)點(diǎn)數(shù)目），可達(dá)性大的優(yōu)先加入。

3）可達(dá)性相同的，節(jié)點(diǎn)度數(shù)較大的優(yōu)先加入，否則，隨機(jī)選取。

一種網(wǎng)絡(luò)拓?fù)錉顟B(tài)如圖1 所示。針對(duì)源節(jié)點(diǎn)S，其一跳鄰居節(jié)點(diǎn)為｛A，B，C，D，E，F(xiàn)｝，二跳鄰居節(jié)點(diǎn)為｛1，2，3，4，5，6，7｝。根據(jù)OLSR 傳統(tǒng)的貪心計(jì)算方法得到的一種MPR 集合為｛A，C，E，F(xiàn)｝，且最小MPR 集的大小為4，而實(shí)際上源節(jié)點(diǎn)S的最小MPR集合為｛B，D，F(xiàn)｝，該算法優(yōu)點(diǎn)在于快速簡(jiǎn)單，但是步驟4 中根據(jù)節(jié)點(diǎn)的覆蓋數(shù)目來(lái)確定MPR 節(jié)點(diǎn)容易帶來(lái)集合冗余且無(wú)法得到最優(yōu)解的問(wèn)題。

圖1 MPR 冗余網(wǎng)絡(luò)拓?fù)錉顟B(tài)示意圖Fig.1 Schematic diagram of MPR redundant network topology status

4 改進(jìn)MPR 算法

針對(duì)傳統(tǒng)MPR 算法的不足之處，本節(jié)將給出改進(jìn)蟻群優(yōu)化算法并對(duì)該算法進(jìn)行建模。DUACO 算法以減少M(fèi)PR 集合冗余為目的，算法在每次迭代時(shí)，蟻群都需要根據(jù)信息素等多種信息計(jì)算得出需要移動(dòng)的下一路徑，當(dāng)螞蟻選擇一條路徑并移動(dòng)后，該路徑會(huì)被留下信息素，各路徑上的信息素都會(huì)周期性的揮發(fā)，隨著正反饋機(jī)制激勵(lì)下某一路徑上的信息素濃度不斷增加，該路徑最終被選為最優(yōu)路徑，即該節(jié)點(diǎn)被選入MPR 集合。因此，DUACO 算法的核心是路徑選擇概率以及信息素等狀態(tài)更新的計(jì)算。

4.1 目標(biāo)函數(shù)

針對(duì)OLSR 協(xié)議中的MPR 選擇問(wèn)題，令源節(jié)點(diǎn)的一跳鄰居集合為N1，二跳鄰居集合為N2，螞蟻數(shù)目為n，MPRi∈{0，1}表示是否將N1i選入MPR 集合，則本文算法的目標(biāo)函數(shù)可表示為：

該目標(biāo)函數(shù)返回MPRi為1 的和的最小值，即被選入MPR 集合中N1 的最小個(gè)數(shù)，因此本文算法的目標(biāo)是不斷優(yōu)化target 以使其取到最小值。算法開始時(shí)N1 中所有節(jié)點(diǎn)信息素被初始化為DEFAULT，記最大迭代次數(shù)為ITER_MAX，Q為N1 中所有信息素大于0 所組成的集合，即：

當(dāng)集合Q中不存在冗余或是已經(jīng)達(dá)到最大迭代次數(shù)時(shí)算法停止，此時(shí)最小MPR 即為Q：

4.2 路徑選擇概率計(jì)算

在MPR 的選擇問(wèn)題中，蟻群算法與傳統(tǒng)算法的區(qū)別在于下一路徑的選擇不是絕對(duì)的，蟻群算法擁有全局探索能力，可以減少局部最優(yōu)解的發(fā)生概率。螞蟻在移動(dòng)過(guò)程中，對(duì)于下一路徑的選擇取決于節(jié)點(diǎn)上的信息素、權(quán)值以及該節(jié)點(diǎn)的移動(dòng)速度等多種因素，這里指該節(jié)點(diǎn)覆蓋但不包括MPR 集合中覆蓋N2 節(jié)點(diǎn)的個(gè)數(shù)。螞蟻i對(duì)于下一城市j的選擇概率公式可以表示為：

其中，μ(k)表示節(jié)點(diǎn)N1k上當(dāng)前存留的信息素濃度，ν(k)表示節(jié)點(diǎn)N1k的權(quán)值，即該節(jié)點(diǎn)當(dāng)前覆蓋的二跳鄰居個(gè)數(shù)，可將其定義為：

s(k)表示節(jié)點(diǎn)N1k移動(dòng)速度對(duì)于概率選擇的影響公式，且可定義為：

其中，speedN1k表示目標(biāo)節(jié)點(diǎn)相較于自身的運(yùn)動(dòng)趨勢(shì)，speedN1k＞0 時(shí)表示節(jié)點(diǎn)在向自身移動(dòng)，節(jié)點(diǎn)速度越快該值越大，該節(jié)點(diǎn)作為MPR 節(jié)點(diǎn)的概率就會(huì)變大，反之該節(jié)點(diǎn)作為MPR 節(jié)點(diǎn)的概率將會(huì)隨移動(dòng)速度的增大而變小。

α表示信息素啟發(fā)式因子，β表示權(quán)值啟發(fā)式因子，γ表示移動(dòng)速度啟發(fā)式因子。其中，0 ＜α＜1，0 ＜β＜1，0 ＜γ＜1，α、β和γ值的大小反映了選取下一路徑時(shí)節(jié)點(diǎn)的信息素、權(quán)值和移動(dòng)速度的重要程度。在算法初期，各路徑上信息素濃度初始相同，設(shè)置較大的β有利于加快算法的收斂速度，應(yīng)注意到當(dāng)β值接近于1 且α與γ值接近于0 時(shí)，該算法則退化成貪心算法。

4.3 狀態(tài)更新計(jì)算

狀態(tài)更新主要指對(duì)于節(jié)點(diǎn)上信息素殘留的更新，為了使算法每次迭代結(jié)果更趨近于最小MPR 集合，并且防止算法出現(xiàn)停滯、局限于局部最優(yōu)解等情況，信息素的更新過(guò)程是蟻群算法中極為關(guān)鍵的過(guò)程。為解決該問(wèn)題，本文提出一種信息素以及全局最優(yōu)解動(dòng)態(tài)更新的方法，設(shè)置全局最優(yōu)解集合為best 并全部初始化為0，besti=1 表示將城市i選入best 集合，螞蟻一次迭代選擇的解集合為res，resi=1表示螞蟻將城市N1i選入res，其初始化全部為0，本文算法的狀態(tài)更新規(guī)則如下：

1）全局最優(yōu)解的更新過(guò)程，且更新規(guī)則如式（8）所示。

2）信息素更新有2 個(gè)過(guò)程，螞蟻留下信息素與信息素的揮發(fā)過(guò)程，為了使本文算法避免出現(xiàn)局部最優(yōu)的情況，根據(jù)螞蟻每次迭代所選取的解與全局最優(yōu)解集合進(jìn)行動(dòng)態(tài)地更新信息素的增加與減少數(shù)量。節(jié)點(diǎn)N1i上的信息素更新規(guī)則可被定義為如式（9）所示。

其中，ρ為信息素?fù)]發(fā)剩余系數(shù)，0 ＜ρ＜1，ADD 為信息素增加常量，DECRE 為信息素?fù)]發(fā)常量。信息素減少過(guò)程由系數(shù)ρ與DECRE 以及全局最優(yōu)解集best確定，當(dāng)best 趨近于最優(yōu)解時(shí)，best 會(huì)變小且收過(guò)程將會(huì)得到加快。息素增加過(guò)程由ADD 以及當(dāng)前解集res 確定，當(dāng)res 過(guò)大時(shí)，則信息素增加會(huì)得到限制，可防止解的集中化并增加全局化節(jié)點(diǎn)搜索的概率，進(jìn)而限制局部最優(yōu)，而當(dāng)res 變小趨近于最優(yōu)解時(shí)，信息素增加幅度變大。

4.4 迭代優(yōu)化機(jī)制

當(dāng)全局最優(yōu)解被更新時(shí)，為防止某個(gè)最優(yōu)節(jié)點(diǎn)被選取時(shí)自身信息素過(guò)小的問(wèn)題，本文亦增加了補(bǔ)償機(jī)制，對(duì)于每次迭代，本文增加以下規(guī)則：

其中，θ為增幅因子，決定了補(bǔ)償幅度。該規(guī)則可以很好地解決了某最優(yōu)節(jié)點(diǎn)自身信息素過(guò)低而難以被選取的問(wèn)題，保證了啟發(fā)式蟻群算法的正反饋機(jī)制。

此外，考慮到蟻群算法可能會(huì)出現(xiàn)某個(gè)非MPR節(jié)點(diǎn)上的信息素濃度大概率被增大而導(dǎo)致算法迭代速度變慢，本文算法也引入了如下懲罰機(jī)制：

其中，σ為懲罰因子，當(dāng)非MPR 節(jié)點(diǎn)上存在過(guò)高信息素濃度時(shí)，本文算法將根據(jù)此節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)中最小的信息素濃度計(jì)算得到懲罰信息素。

本文算法的補(bǔ)償與懲罰機(jī)制主要取決于迭代結(jié)果res 的大小。若res ＞best，則說(shuō)明MPR 節(jié)點(diǎn)被選中，該次迭代完成優(yōu)化，采用補(bǔ)償機(jī)制；若res ＜best，則說(shuō)明非MPR 節(jié)點(diǎn)被選中，該次迭代可能趨于局部最優(yōu)或延長(zhǎng)迭代時(shí)間，即采用懲罰機(jī)制。

4.5 DUACO 算法步驟

利用源節(jié)點(diǎn)的二跳鄰居拓?fù)鋪?lái)構(gòu)建蟻群路徑，每只螞蟻從源節(jié)點(diǎn)出發(fā)，以達(dá)成N2 的全覆蓋為目標(biāo)，在N1 中計(jì)算出各路徑的選擇概率，將所選取的路徑加入res 并更新res 對(duì)N2 中的覆蓋節(jié)點(diǎn)，只有當(dāng)N2 被已選的路徑集合res 全覆蓋時(shí)，該螞蟻結(jié)束本次迭代，利用上述狀態(tài)更新機(jī)制對(duì)信息素進(jìn)行更新。算法設(shè)立最大迭代閾值為ITER_MAX，令Q為N1 中所有μ(i) ＞0 節(jié)點(diǎn)組成的集合。當(dāng)?shù)螖?shù)超過(guò)ITER_MAX 或者集合Q不存在冗余時(shí)，算法結(jié)束迭代，此時(shí)集合Q或者best 即為最小MPR 集合。本文算法的具體步驟如下所示：

算法最終目標(biāo)target 為|best|，所求出的最小MPR集合為best。

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

為了驗(yàn)證本文算法的可行性，實(shí)驗(yàn)在仿真平臺(tái)NS3上進(jìn)行，采用NS3中OLSR協(xié)議并將DUACO算法加入到其MPR選擇過(guò)程中，在不同網(wǎng)絡(luò)密集程度下比較了默認(rèn)MPR算法、蟻群優(yōu)化算法以及DUACO算法的性能。實(shí)驗(yàn)選取仿真區(qū)域?yàn)? km2，每個(gè)節(jié)點(diǎn)都采用NS3自帶的隨機(jī)運(yùn)動(dòng)-停止模型、節(jié)點(diǎn)位置以及移動(dòng)速度隨機(jī)生成。多次實(shí)驗(yàn)后得到性能穩(wěn)定性最佳的參數(shù)如表1所示。

表1 實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Experimental parameter settings

為研究本文算法對(duì)于網(wǎng)絡(luò)性能的變化情況，實(shí)驗(yàn)給出了不同網(wǎng)絡(luò)密度下3 種算法的網(wǎng)絡(luò)性能對(duì)比，結(jié)果如表2 所示。從表2 可以看出，當(dāng)節(jié)點(diǎn)數(shù)目較低時(shí)，網(wǎng)絡(luò)拓?fù)湎∈?，?jié)點(diǎn)分散且存在孤立節(jié)點(diǎn)的概率較大，而通信距離有限，網(wǎng)絡(luò)性能較差。隨著節(jié)點(diǎn)數(shù)目的增多，網(wǎng)絡(luò)性能得到改善，而當(dāng)節(jié)點(diǎn)數(shù)目過(guò)多時(shí)，網(wǎng)絡(luò)分組數(shù)目巨大且網(wǎng)絡(luò)擁塞的概率變高，造成網(wǎng)絡(luò)性能再度降低。

表2 3 種算法的性能對(duì)比Table 2 Performance comparison of three algorithms

當(dāng)網(wǎng)絡(luò)較為稀疏時(shí)，節(jié)點(diǎn)的一跳鄰居集合較小，發(fā)生MPR 選取冗余的概率較小，因此當(dāng)節(jié)點(diǎn)數(shù)目過(guò)低時(shí)，Default、ACO 和DUACO 算法通常性能差異性不大。此時(shí)ACO 和DUACO 算法使用較大的權(quán)值啟發(fā)式因子，算法趨于傳統(tǒng)貪心算法以求加快迭代速度，而隨著節(jié)點(diǎn)數(shù)目的增加，ACO 和DUACO 算法逐漸加大信息素啟發(fā)式因子的大小，以保證路徑選擇時(shí)的隨機(jī)性，防止陷入局部最優(yōu)。蟻群優(yōu)化算法根據(jù)信息素以及權(quán)值確定狀態(tài)轉(zhuǎn)移概率，這種算法僅適用于固定的網(wǎng)絡(luò)拓?fù)?，?dāng)節(jié)點(diǎn)具有移動(dòng)性且網(wǎng)絡(luò)拓?fù)洳粩嘧兓瘯r(shí)，該算法不能取得預(yù)期的效果。

圖2 給出了在不同數(shù)目節(jié)點(diǎn)下，ACO 與DUACO 算法的平均迭代次數(shù)對(duì)比結(jié)果。從圖2 可以看出，DUACO 算法的狀態(tài)信息動(dòng)態(tài)更新機(jī)制有效加快了蟻群優(yōu)化算法的迭代速度，迭代次數(shù)平均降低了8.531 61%，隨著網(wǎng)絡(luò)拓?fù)溆用芗?，DUACO 算法的加快迭代速度愈加明顯，當(dāng)節(jié)點(diǎn)數(shù)目為160 時(shí)，ACO 算法達(dá)到最大迭代次數(shù)。從表2也可以看出，DUACO 算法相較于ACO 算法時(shí)延降低了40.565 8%，MPR 集合的大小減少了1.950 86%，網(wǎng)絡(luò)丟包率降低5.791 26%，網(wǎng)絡(luò)吞吐量提高了6.316%。

圖2 ACO 算法與DUACO 算法的平均迭代次數(shù)對(duì)比Fig.2 Comparison of the average number of iterations between ACO algorithm and DUACO algorithm

為了研究Default、ACO 和DUACO 這3 種算法的能耗關(guān)系，實(shí)驗(yàn)測(cè)試了應(yīng)用不同MPR 算法時(shí)節(jié)點(diǎn)執(zhí)行時(shí)長(zhǎng)與仿真進(jìn)度之間的關(guān)系，結(jié)果如圖3 所示。從圖3 可以看出，DUACO 算法在速度上不及默認(rèn)Default 算法，但相較于ACO 算法節(jié)點(diǎn)計(jì)算時(shí)長(zhǎng)呈降低的趨勢(shì)，這是因?yàn)楸疚脑贒UACO 重新定義了信息素的更新機(jī)制，加快了算法的迭代速度。另外，考慮到某些最優(yōu)節(jié)點(diǎn)上信息素濃度過(guò)低難以被選取和非最優(yōu)節(jié)點(diǎn)信息素濃度過(guò)高的問(wèn)題，本文利用引入信息素補(bǔ)償-懲罰機(jī)制來(lái)降低DUACO 陷入局部最優(yōu)的概率，從而減少M(fèi)PR 集合的冗余，對(duì)于網(wǎng)絡(luò)性能的改善均優(yōu)于ACO 算法與默認(rèn)Default 算法。

圖3 3 種算法的節(jié)點(diǎn)計(jì)算時(shí)間與模擬時(shí)間的關(guān)系Fig.3 The relationship between the node computation time and simulation time of the three algorithms

6 結(jié)束語(yǔ)

針對(duì)OLSR 協(xié)議中貪心MPR 機(jī)制的求解冗余問(wèn)題，本文將蟻群優(yōu)化算法應(yīng)用到MPR 選擇機(jī)制中，并在蟻群優(yōu)化算法基礎(chǔ)上加入了狀態(tài)信息的動(dòng)態(tài)更新以及補(bǔ)償-懲罰機(jī)制。實(shí)驗(yàn)結(jié)果表明，利用ACO 算法求解MPR 問(wèn)題時(shí)，在正確求解MPR 最小集的前提下，該算法可有效提高收斂速度和網(wǎng)絡(luò)性能。蟻群優(yōu)化算法受限于啟發(fā)參數(shù)的選取以及影響因子的設(shè)置，對(duì)其進(jìn)行合理設(shè)置具有很強(qiáng)的經(jīng)驗(yàn)性。下一步將利用深度學(xué)習(xí)技術(shù)分析迭代過(guò)程中狀態(tài)信息的變化情況，并根據(jù)冗余等數(shù)據(jù)信息自學(xué)習(xí)得到最優(yōu)啟發(fā)參數(shù)和影響因子，以進(jìn)一步提升蟻群優(yōu)化算法的迭代速度和求解精度。