基于蟻群優化的大規模自組網MPR選擇算法

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

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

0 引言

近些年來，在民用領域和軍用領域，移動自組網的發展變得越來越引人注目，其中無人機（UAV,Unmanned Aerial Vehicle）憑借其體積小、成本低、便于部署等優勢[1]在實時監控、搜尋救援、中繼傳輸、戰略打擊等方面都得到了廣泛的應用[2-3]。然而無人機自組織網絡具有節點移動性強、網絡拓撲變化快、數據交互頻繁、能量消耗大等特點[4]，傳統的路由算法已經無法滿足其對網絡傳輸延遲、丟包率、路由開銷等方面的要求。

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

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

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

1 系統模型與問題分析

MPR 多點中繼的原理是在轉發廣播信令包時，只有被選為MPR 的節點才具有轉發的權利，其余節點對收到的消息進行處理但并不轉發。每個節點都會從自己的一跳鄰居中選取若干節點作為自己的MPR 節點，該節點為其轉發協議的TC 分組[17]。下面是傳統MPR 集合選取問題的數學描述。

貪心算法求解步驟為：

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

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

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

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

貪心算法的優點在于計算與實現簡單，但是其結果往往會產生冗余。當考慮圖1 的拓撲時，針對源節點1，其S1 集合={2,3,4,5,6}，其S2 集合為{A,B,C,D,E,F,G}。經由貪心算法所得的MPR 集為{2,3,4,6}，而實際最優的MPR 集為{3,4,5}，這就導致了選取節點的冗余。

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

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

2 基于節點狀態的動態更新蟻群算法

2.1 目標函數

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

2.2 節點路徑選擇

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

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

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

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

2.3 信息素的更新

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

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

信息素的更新公式如下：

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

其中itecur代表當前的迭代次數，itemax代表設置的最大迭代次數。

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

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

2.4 DNACO算法流程

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

3 仿真結果與分析

為驗證本文算法的可行性，實驗使用qualnet 網絡仿真平臺進行仿真。該仿真平臺基于PASREC 并行仿真內核，對于大規模自組網絡，其仿真速度是其他仿真器的幾十倍，并且包含的協議棧完備，能適應不同場景下的網絡仿真[19-20]。

實驗采用了qualnet 中的OLSR 協議，并將動態更新蟻群優化（DNACO,Dynamic Updating Ant Colony Optimization）算法加入到MPR 選擇的過程中。在不同的網絡拓撲和網絡密集度下比較了采用貪心策略的MPR算法、ACO 算法以及DNACO 的性能，每個節點都采用qualnet 自帶的Random Waypoint 移動模型，整個場景規模為1 500 m×1 500 m。整體實驗的參數如表1 所示。

表2 給出了在不同數目節點下，三種算法求取MPR節點后對于網絡性能的改善。

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

表1 三種算法的仿真參數

表2 三種算法的性能對比

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

4 結束語

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