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

（南京理工大學計算機科學與工程學院，南京 210094）

0 概述

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

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

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

1 相關(guān)工作

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

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

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

2 MPR 問題描述

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

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

3 傳統(tǒng)MPR 算法

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

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

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

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

步驟4對于二跳鄰居中被多個一跳鄰居覆蓋的節(jié)點，應該按照以下優(yōu)先級進行考慮：

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

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

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

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

圖1 MPR 冗余網(wǎng)絡拓撲狀態(tài)示意圖Fig.1 Schematic diagram of MPR redundant network topology status

4 改進MPR 算法

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

4.1 目標函數(shù)

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

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

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

4.2 路徑選擇概率計算

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

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

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

其中，speedN1k表示目標節(jié)點相較于自身的運動趨勢，speedN1k＞0 時表示節(jié)點在向自身移動，節(jié)點速度越快該值越大，該節(jié)點作為MPR 節(jié)點的概率就會變大，反之該節(jié)點作為MPR 節(jié)點的概率將會隨移動速度的增大而變小。

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

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

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

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

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

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

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

當全局最優(yōu)解被更新時，為防止某個最優(yōu)節(jié)點被選取時自身信息素過小的問題，本文亦增加了補償機制，對于每次迭代，本文增加以下規(guī)則：

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

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

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

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

4.5 DUACO 算法步驟

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

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

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

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

表1 實驗參數(shù)設置Table 1 Experimental parameter settings

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

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

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

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

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

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

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

6 結(jié)束語

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