基于蟻群優(yōu)化的大規(guī)模自組網(wǎng)MPR選擇算法

朱天林，王傲，楊錦彬，李大鵬

（南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003）

0 引言

近些年來，在民用領(lǐng)域和軍用領(lǐng)域，移動自組網(wǎng)的發(fā)展變得越來越引人注目，其中無人機(jī)（UAV,Unmanned Aerial Vehicle）憑借其體積小、成本低、便于部署等優(yōu)勢[1]在實時監(jiān)控、搜尋救援、中繼傳輸、戰(zhàn)略打擊等方面都得到了廣泛的應(yīng)用[2-3]。然而無人機(jī)自組織網(wǎng)絡(luò)具有節(jié)點移動性強(qiáng)、網(wǎng)絡(luò)拓?fù)渥兓?、?shù)據(jù)交互頻繁、能量消耗大等特點[4]，傳統(tǒng)的路由算法已經(jīng)無法滿足其對網(wǎng)絡(luò)傳輸延遲、丟包率、路由開銷等方面的要求。

最優(yōu)鏈路狀態(tài)路由（OLSR,Optimized Link State Routing）協(xié)議是一種經(jīng)典的鏈路狀態(tài)協(xié)議，通過在節(jié)點間廣播Hello 分組來完成鏈路探測、鄰居發(fā)現(xiàn)以及多點中繼（MPR,Multi-Point Relay）節(jié)點的選擇[5]。利用拓?fù)淇刂疲═C,Topology Control）分組在獲取MPR 節(jié)點信息后建立和維護(hù)網(wǎng)絡(luò)的整個拓?fù)?，并最終運用Dijkrastra 算法計算路徑，生成路由[6]。其中MPR 節(jié)點的選擇至關(guān)重要[7]，每個節(jié)點都只會將其TC 分組發(fā)送至其對應(yīng)的MPR 節(jié)點，以減少網(wǎng)絡(luò)間的控制包數(shù)量。文獻(xiàn)[8]提及，選擇最優(yōu)的MPR 集是NP 難問題。傳統(tǒng)方式往往采用貪心算法對MPR 集進(jìn)行選擇，優(yōu)先選取覆蓋源節(jié)點二跳鄰居最多的一跳節(jié)點。這樣會造成很大的冗余，進(jìn)而導(dǎo)致協(xié)議的開銷增大、網(wǎng)絡(luò)間的延遲上升。很多學(xué)者都從不同角度上對MPR 的選取算法進(jìn)行了改進(jìn)。文獻(xiàn)[9-10]采用最小最大算法，以減少每個節(jié)點上的TC 分組數(shù)量。文獻(xiàn)[11]提出一種基于集合的MPR 選擇算法，通過結(jié)合循環(huán)和集合操作，可以有效地消除無效的冗余節(jié)點。在文獻(xiàn)[12]中提出了基于擴(kuò)展為三跳的相鄰節(jié)點的本地數(shù)據(jù)庫的MPR 選擇，MPR 的選擇使用OLSR 中現(xiàn)有的算法，結(jié)果表明，其在TC 數(shù)據(jù)包數(shù)量和能源效率方面優(yōu)于標(biāo)準(zhǔn)OLSR。

蟻群算法（ACO,Ant Colony Optimization）是對現(xiàn)實世界中真實的蟻群覓食行為的抽象和改進(jìn)，是一種智能優(yōu)化的啟發(fā)式算法[13]。螞蟻通過在覓食過程移動時所留下的信息素來向其他螞蟻傳遞信息，其他螞蟻根據(jù)不同路徑信息素的濃度來決定其下一步路徑。該算法的優(yōu)勢在于其搜索具有全局性，而傳統(tǒng)的貪心算法無法考慮到全局的情況，往往陷入局部最優(yōu)[14-15]。蟻群算法利用隨機(jī)概率選擇下一跳路徑，當(dāng)信息素積累，概率增加到1 時，算法便會退化為貪心算法。單一的蟻群算法雖然在貪心算法的基礎(chǔ)上有所改進(jìn)，但仍然存在迭代時間過長而陷入局部最優(yōu)的問題[16]。

本文結(jié)合蟻群算法的全局搜索能力，考慮到無人機(jī)自組網(wǎng)的特性，將本地節(jié)點三跳鄰居數(shù)據(jù)庫引入到蟻群的路徑選擇函數(shù)中。同時考慮節(jié)點的速度，對ACO 算法原有的路徑選擇以及狀態(tài)更新機(jī)制進(jìn)行了改進(jìn)，將蟻群優(yōu)化應(yīng)用于求解MPR 集合問題中，達(dá)到了優(yōu)化MPR 集合的目的，最后將其集成于Qualnet 網(wǎng)絡(luò)仿真軟件系統(tǒng)中，很好地驗證了本文所提出算法的性能。

1 系統(tǒng)模型與問題分析

MPR 多點中繼的原理是在轉(zhuǎn)發(fā)廣播信令包時，只有被選為MPR 的節(jié)點才具有轉(zhuǎn)發(fā)的權(quán)利，其余節(jié)點對收到的消息進(jìn)行處理但并不轉(zhuǎn)發(fā)。每個節(jié)點都會從自己的一跳鄰居中選取若干節(jié)點作為自己的MPR 節(jié)點，該節(jié)點為其轉(zhuǎn)發(fā)協(xié)議的TC 分組[17]。下面是傳統(tǒng)MPR 集合選取問題的數(shù)學(xué)描述。

貪心算法求解步驟為：

步驟1：從源節(jié)點出發(fā)，將所有一跳鄰居納入集合S1，將所有二跳鄰居納入集合S2；

步驟2：計算S1 集合中每一個節(jié)點的一跳節(jié)點的鄰居個數(shù)n（不包含源節(jié)點及S1 集合中的點）；

步驟3：選取n數(shù)目最大的一跳鄰居，添入MPR 集合，從源節(jié)點一跳鄰居集合S1 中移除，并將其對應(yīng)源節(jié)點的二跳鄰居從S2 中移除；

步驟4：重復(fù)S2～S3 直到S2 集合為空，所選的MPR集合即為所求。

貪心算法的優(yōu)點在于計算與實現(xiàn)簡單，但是其結(jié)果往往會產(chǎn)生冗余。當(dāng)考慮圖1 的拓?fù)鋾r，針對源節(jié)點1，其S1 集合={2,3,4,5,6}，其S2 集合為{A,B,C,D,E,F,G}。經(jīng)由貪心算法所得的MPR 集為{2,3,4,6}，而實際最優(yōu)的MPR 集為{3,4,5}，這就導(dǎo)致了選取節(jié)點的冗余。

圖1 貪心算法計算冗余的示例

此外貪心算法求解的MPR 集合僅僅考慮源節(jié)點一跳鄰居對二跳鄰居的覆蓋度，對節(jié)點的移動性、鏈路的狀態(tài)質(zhì)量等都沒有考慮，已經(jīng)無法適應(yīng)越來越多變的自組網(wǎng)環(huán)境。鑒于上述所提出的傳統(tǒng)貪心算法的各種不足，本文采取了蟻群優(yōu)化算法對MPR 問題進(jìn)行建模并求解。

2 基于節(jié)點狀態(tài)的動態(tài)更新蟻群算法

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

在當(dāng)前的MPR 選取問題中，假設(shè)共有m個節(jié)點，其中源節(jié)點為A，定義源節(jié)點的一跳集合S1，且|S1|=n，源節(jié)點的嚴(yán)格二跳鄰居集合S2，源節(jié)點的嚴(yán)格三跳鄰居集合S3，其中|S1|+|S2|+|S3|+1=m。假設(shè)共有k只螞蟻，resk代表第k只螞蟻在當(dāng)前迭代中所得到的MPR 解集合中的元素個數(shù)。targetj∈{0,1}(j=1,2,...,n)代表對當(dāng)前螞蟻是否將S1j選入MPR 集合。對于每只螞蟻，其最優(yōu)解。對于該問題，全局的最優(yōu)解bestSolu=min|resk|。本算法的目標(biāo)是在考慮無人機(jī)網(wǎng)絡(luò)節(jié)點移動性的同時，不斷優(yōu)化resk的取值，使得最后所得的bestSolu取得理想的最小值，以適應(yīng)當(dāng)前復(fù)雜的無人機(jī)自組網(wǎng)的需要。

2.2 節(jié)點路徑選擇

蟻群算法的全局搜索能力就在于其下一跳路徑的選擇不是絕對的，螞蟻在移動過程中，會動態(tài)更新信息素、權(quán)值等關(guān)鍵信息，并依據(jù)這些因素選取最符合的路徑。令表示螞蟻k選擇節(jié)點i(i=1,2,...,n)作為下一個選入MPR 集合的節(jié)點的概率，可得：

其中，α表示信息素的啟發(fā)式因子，β表示兩跳權(quán)重的啟發(fā)因子，γ表示三跳權(quán)重的啟發(fā)因子，ε表示節(jié)點相對速度的啟發(fā)因子，且α∈(0,1),β∈(0,1)，γ∈(0,1)，ε∈(0,1)。α的值越大，當(dāng)前螞蟻收到其他螞蟻遺留信息素的影響就越大，β、γ、ε代表了對應(yīng)啟發(fā)因子的重要程度。當(dāng)α為1，β、γ、ε為0 時，蟻群算法就退化成了傳統(tǒng)的貪心算法。

τ(i)表示節(jié)點i上持有的信息素的濃度，μ(i)表示節(jié)點i所覆蓋源節(jié)點二跳鄰居的權(quán)重，η(i)表示節(jié)點i所覆蓋源節(jié)點三跳鄰居的權(quán)重，υ(i)表示目標(biāo)節(jié)點i移動速度對概率選擇的影響公式，allowed(S1)k表示螞蟻k允許加入其MPR 集的節(jié)點集合。

對于η(i)，引入三跳鄰居的本地數(shù)據(jù)庫加入MPR 的附加決策函數(shù)中，可以達(dá)到進(jìn)一步優(yōu)化MPR 的目的[10]。

2.3 信息素的更新

蟻群算法中，路徑上的信息素會隨著所經(jīng)過螞蟻的增加而不斷累積，往往大量已走過的非最優(yōu)路徑上的信息素濃度不斷累積，而未被選擇過的路徑上信息素濃度不斷降低，真正可能的最優(yōu)路徑或許就存在于未被選擇過的路徑中，這時算法就陷入了局部最優(yōu)解中。

為防止算法收斂于局部最優(yōu)解或者收斂過慢，本文采取了全局信息素更新規(guī)則對路徑上的信息素進(jìn)行更新。相較于傳統(tǒng)ACO 算法對所有到達(dá)目的節(jié)點的螞蟻所經(jīng)過的路徑上的信息素進(jìn)行更新，本文對當(dāng)前迭代過程中的最優(yōu)路徑進(jìn)行進(jìn)一步的信息素積累，對最差路徑進(jìn)行進(jìn)一步地?fù)]發(fā)來予以懲罰。這樣有利于更快地排除相對較差的路徑，同時突出較好的路徑，從而加快算法的收斂，減少算法陷入局部最優(yōu)的概率。

信息素的更新公式如下：

其中ρ為階段性的信息素的揮發(fā)率，τi(t)為更新前節(jié)點i上的信息素增量，τ(t+i)為更新后節(jié)點i上的信息素增量，具體定義如下：

其中itecur代表當(dāng)前的迭代次數(shù)，itemax代表設(shè)置的最大迭代次數(shù)。

其次，由于每輪迭代的結(jié)果可能不同，這使得更多路徑上的信息素將會得到積累，并且就階段性的信息素?fù)]發(fā)系數(shù)來說，揮發(fā)率的初值較高，有利于螞蟻對所有路徑進(jìn)行更加全面的搜索，避免陷入局部最優(yōu)。隨著迭代次數(shù)的增多，揮發(fā)率不斷降低，可以讓螞蟻逐漸匯集到最優(yōu)路徑上。

當(dāng)信息素更新時，為防止某個最優(yōu)節(jié)點被選取自身時，因為信息素過小而難以被選取，或者某個節(jié)點上的信息素濃度過大，導(dǎo)致路徑搜索過程過早停滯從而錯過更優(yōu)的路徑，為每個節(jié)點的信息素設(shè)置上限phemax，同時設(shè)置下限phemin，使得節(jié)點的信息素恒在[phemin,phemax]之內(nèi)。

2.4 DNACO算法流程

整個算法的框架如下：螞蟻的數(shù)目num_Ants、當(dāng)前迭代次數(shù)ite、總的迭代次數(shù)total_iteration、每只螞蟻訪問過的節(jié)點數(shù)組visit、當(dāng)前未被覆蓋的二跳鄰居節(jié)點個數(shù)Uncover_S2、當(dāng)前螞蟻選擇MPR 集合大小cur_Solu和歷史最優(yōu)的MPR 集大小best_Solu，算法流程如下：

3 仿真結(jié)果與分析

為驗證本文算法的可行性，實驗使用qualnet 網(wǎng)絡(luò)仿真平臺進(jìn)行仿真。該仿真平臺基于PASREC 并行仿真內(nèi)核，對于大規(guī)模自組網(wǎng)絡(luò)，其仿真速度是其他仿真器的幾十倍，并且包含的協(xié)議棧完備，能適應(yīng)不同場景下的網(wǎng)絡(luò)仿真[19-20]。

實驗采用了qualnet 中的OLSR 協(xié)議，并將動態(tài)更新蟻群優(yōu)化（DNACO,Dynamic Updating Ant Colony Optimization）算法加入到MPR 選擇的過程中。在不同的網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)密集度下比較了采用貪心策略的MPR算法、ACO 算法以及DNACO 的性能，每個節(jié)點都采用qualnet 自帶的Random Waypoint 移動模型，整個場景規(guī)模為1 500 m×1 500 m。整體實驗的參數(shù)如表1 所示。

表2 給出了在不同數(shù)目節(jié)點下，三種算法求取MPR節(jié)點后對于網(wǎng)絡(luò)性能的改善。

從圖2 可以看出，當(dāng)節(jié)點數(shù)目比較少的時候，三種算法選擇出的MPR 集合近似相同，算法的性能差異不大。此時ACO 和DNACO 使用較大的權(quán)值啟發(fā)因子，算法趨近于傳統(tǒng)的貪心算法以加快迭代速度。隨著節(jié)點數(shù)目的增加，DNACO 及ACO 較傳統(tǒng)的貪心算法有了明顯的改進(jìn)。可以看出，DNACO 算法相較于ACO 算法時延降低了8.7%、網(wǎng)絡(luò)丟包率降低了7.9%、吞吐量提高了5.7%。

表1 三種算法的仿真參數(shù)

表2 三種算法的性能對比

圖2 三種算法時延、丟包率對比情況

4 結(jié)束語

傳統(tǒng)OLSR 協(xié)議采用貪心算法求解MPR 從而造成冗余，無法適應(yīng)現(xiàn)今大規(guī)模自組網(wǎng)絡(luò)場景，針對這個問題，本文將蟻群優(yōu)化算法應(yīng)用于MPR 選擇機(jī)制中，并且在蟻群算法的基礎(chǔ)上，將節(jié)點的三跳鄰居信息及移動信息添加進(jìn)節(jié)點選擇考量中，將動態(tài)更新添加入信息素更新機(jī)制中，提出了DNACO 算法。實驗結(jié)果表明，當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)較多時，DNACO 選取的MPR 集合可能不是最小的MPR 集，但是其在降低網(wǎng)絡(luò)延時和提高網(wǎng)絡(luò)吞吐量時較傳統(tǒng)的算法有明顯的提高。因此，采用本文提出的DNACO 算法可以有效提高無人機(jī)自組網(wǎng)絡(luò)的網(wǎng)絡(luò)性能，降低開銷。