Mesh網絡中基于粒子群優化的最優路徑算法

趙宏偉

(蘇州工業園區服務外包職業學院，江蘇蘇州 215123)

Mesh網絡中基于粒子群優化的最優路徑算法

趙宏偉

(蘇州工業園區服務外包職業學院，江蘇蘇州 215123)

在以往的無線Mesh網絡的最優路由設計中，往往僅考慮吞吐率和長度等單一因素。針對此問題，本文提出了一種基于量子粒子群優化的最優路徑算法。首先，對網絡中考慮的性能指標進行了詳細描述，然后設計了路由協議，即路由發現、路由維護和路由修復。在此基礎上，基于量子粒子群對路由進行優化，在路由優化過程中全面考慮網絡總吞吐率、網絡平均丟包率、網絡端到端的延遲。在NS-2環境下進行仿真實驗，在仿真實驗中對網絡總吞吐率、網絡平均丟包率和網絡端到端的延遲均進行了驗證，結果證明，本文方法與其他方法相比具有較大的網絡總吞吐率、較小的網絡平均丟包率和網絡端到端的延遲。

最優路徑；路由協議；Mesh網絡；通信

近年來，無線Mesh網絡(wireless mesh network，WMN)即無線網狀網，得到了廣泛關注，其以靜態無線中繼Mesh節點，為移動的客戶節點提供分布式網絡。無線Mesh網絡主要包括Mesh路由和Mesh用戶。其中Mesh路由主要起到中繼器的作用，通過無線方式連接上層網關同時為下層的MC提供網絡服務。

為了實現Mesh網絡的負載平衡和最大程度地提高整個網絡的資源利用率，一些路由協議開始基于跨層的思想以提高網絡的整體性能。如采用源節點到目標節點的最小跳數來設計路由協議(DSR，dynamic source routing)和AODV(Ad Hoc on Demand distance vector routing)。這些協議由于節點的移動性以及拓撲結構的動態變化，無法實現網絡的最優。OLSR(Optimized link state routing)協議[2]基于DSR，是一種實現多點中繼驅動的路由協議，能在多點中繼的情況下通過選擇性的泛洪機制，來減少某一分區控制分組的重復轉發次數。閆茜[3]對無線Mesh網絡中的多接口多信道進行了優化，提出了一種混合式信道分配相結合的多路徑路由協議，實現了網絡中多條路徑的并行傳輸，以提高網絡的吞吐率。鄧曉衡[4]提出了一種新的路由判斷依據EPBW，并在此基礎上設計了路由協議EPBWR，同時在NS-2環境下在多種網絡環境中進行了仿真。石文孝[5]在INX的基礎上提出了無線Mesh網絡干擾和區域負載的度量方法，并通過平均競爭度來描述干擾鏈路和離散程度來判斷網絡是否負載均衡。潘琢金[6]設計了一種支持多路徑路由的先驗式路由協議，通過先驗式多樹和比較累積傳播的鏈路質量，來進行傳輸過程中的路由選擇。何凌[7]提出了一種混合無線網狀網協議的改進算法來解決AODV協議中的一些問題，如擴展性差、效率低，實驗表明了改進的協議能快速計算出從源節點到目標節點的最優路徑。

本文在上述工作的基礎上，設計了一種基于量子粒子群的路由算法，該算法通過量子粒子群搜索出從任意節點到目標節點的最優路徑，是一種Mesh網絡中最優路由設計的有效方法。

1 網絡性能評價

在設計路由協議時，最優路由的目標函數需要考慮的主要性能指標有網絡總吞吐率、網絡平均丟包率和端到端的平均時延。

1.1 網絡總吞吐率

網絡總吞吐率是網絡中所有接收端在單位時間內正確接收的數據量，單位為kbit/s，表達式為：

(1)

其中，M是網絡中所有運行的數據流組成的集合，Reci表示第i個接收端在數據流運行期間接收到的數據總量，Δt是網絡中最后一個數據包傳輸完成減去第一個數據開始數據傳輸的開始時間，即整個網絡中數據流進行運行的總時間。

網絡吞吐率越高，網絡能負載能力就越強，網絡的性能就越好。

1.2 網絡平均丟包率

網絡的平均丟包率是網絡中所有接收端接受到的正確的數據包與網絡中所有輸入端發出的所有的數據包的總量的比值，其計算方法為：

(2)

其中，N是網絡中接收端接收到的所有正確的數據包的集合，|N|為網絡中的所有接收端接收的正確的數據包數，Nsum表示網絡中發送端發送的所有數據包的總和。

網絡丟包率反應了網絡的可靠性，網絡的丟包率越低，網絡越可靠，網絡的性能越好。

1.3 網絡端到端延遲

網絡的端到端數據延遲是指數據包從開始發送到被網絡的接收端正確接收所需要的總時間。平均的端到端延遲是網絡中所有發送端發送的數據包的端到端時間延遲的平均值，表達式為：

(3)

其中，τj表示數據包j對應的端到端的時間延遲。

網絡端到端延遲反應了數據在網絡中傳輸的快慢。網絡端到端的延遲越小，網絡性能越好。

2 路由協議

2.1 路由發現

為了減少路由發現的開銷，采用按需方式進行路由發現。當源節點S要向目標節點D發送數據時，就在全網中廣播路由請求包，啟動路由發現過程。路由請求包為RREQ(routing request packet)，每個RREQ包含單一的序列號ID和鄰居節點列表，鄰居列表記錄是屬于當前路徑的節點。

當鄰居節點在收到由源節點或由轉發節點發送過來的RREQ后，首先查看是否曾經收到過該數據包，如果收到就丟棄該數據包；如果沒有收到過該數據包，就寫入RREQ消息中，并建立從該節點到源節點S的反向路由。同時判斷是否自己存在著到RREQ中目標節點的路由，如果存在，則直接回復路由回應信息包給源節點；如果不存在則轉發該RREQ；源節點S在收到來自多個中間節點或目標節點返回的路由回復信息包應答數據包RREP(routing reply packet)時，選擇具有最小長度的路徑存入路由表中，如果多個路由回復信息包中均具有最輕負載值，將新序列號存入到路由表中。

2.2 路由維護

路由發現用于建立源節點到目標節點之間的有效路由，通過該過程建立有效路由并進行數據傳輸。然而，由于無線網絡的動態性，當前路由的吞吐量可能下降甚至路由可能失效。網絡中可能由于動態性的變化，存在著更好的路徑。

當目標節點發現其與源節點之間的路徑吞吐率下降時，向源節點發送路由請求觸發消息TREQ(triggering request message)。源節點在收到該信息后，就啟動路由發現過程，并在全網中廣播路由更新包UREQ(update routing request packet)。如果發現有更短路由和吞吐率更大的路徑，則采用此路由作為首要路由。當網絡進行動態性變化時，若數據傳輸有兩條以上的可選相似路徑，則選擇一條較空閑的路由進行數據傳輸，由此不斷重復。

2.3 路由修復

當建立的路由由于網絡動態拓撲的變化而失效時，原因可能是由于目的節點到源節點返回的路由信息丟失或者數據傳輸過程中的鏈路斷開。當RREQ從源節點出發，經過若干中間節點，最后到達目標節點后，目標節點會根據反向路由發送RREQ數據包。在數據傳輸的過程中，如果路徑發生中斷，傳輸失敗的中間節點向源節點發送錯誤信息RERR(routing error packet)，而源節點在收到錯誤信息RERR后，會重啟路由發現過程以找到新的路徑。

3 基于量子粒子群的最優路徑

3.1 量子粒子群概述

量子粒子群算法(Quantum-behaved Particle Swarm optimization，QPSO)是在粒子群算法的基礎上發展而來的一種全局優化算法。

量子粒子群算法能在整個解空間中進行搜索，同時量子空間具有與普通粒子不一樣的集聚態性，因此較粒子群算法具有更好的全局尋優能力。粒子位置向量采用ψ(x)表示，在時刻t或第t次迭代時，粒子的位置可以計算為：

(4)

其中，pl(t)、pg(t)和pr(t)分別表示粒子個體最優位置、粒子的全局最優位置和個體最優pl(t)。α為服從[0,1]上均勻分布的隨機數，則有：

(5)

其中，pa(t)為第t次迭代所有粒子的位置均值，β為取值固定的慣性權重。粒子在時刻t+1或第t+1次迭代時的位置可以表示為：

(6)

3.2 基于改進量子粒子群的模型參數優化算法

在路由發現、路由維護和路由修復過程中尋找路由的過程往往僅考慮路徑長度或吞吐率等因素，為了實現一個更優的最優路徑，在最優路徑的求解過程中充分考慮性能參數，即最優考慮最大化網絡總吞吐率、最小化網絡平均丟包率，最小化網絡端到端的延遲。

算法1 基于量子粒子群的最優路由算法

初始化：粒子種群規模M，當前迭代次數i，迭代次數最大值；

①以路由發現生成的路由作為初始解，隨機生成規模為M的粒子群P={p1,p2,…,pM}，每個粒子pi長度為路由的長度；

②根據公式(1)(2)(3)計算每個粒子的網絡總吞吐率、網絡平均丟包率、網絡端到端的延遲；

③計算粒子的適應度：

(7)

④對所有粒子判斷其適應度是否小于個體最優位置的適應度J(pl(t))：

如果小于，則采用p(t)作為新的個體最優位置pl(t)；

判斷其是否小于J(pg(t))：

如果小于，則采用粒子的當前位置作為全局最優值pg(t)；

⑤根據公式(4)計算個體平均最優位置；

⑥根據公式(6)對粒子個體位置更新；

⑦更新迭代次數：t=t+1；判斷當前迭代次數t達到最大值：

如果達到，輸出最優路由；

否則轉入②進行繼續迭代。

4 仿真實驗

在NS-2仿真工具下對文中設計的基于粒子群算法的最優路由進行仿真。在500×500 d區域中進行部署，每個節點有3個網絡接口，節點的傳輸范圍為300 m，干擾范圍為500 m，傳送數據包的大小為512 B。將文中方法與文獻[7]方法在網絡總吞吐率、網絡平均丟包率、網絡端到端的延遲等3個方面進行對比，如圖1、圖2和圖3所示。

圖1 網絡總吞吐率比較

圖2 網絡平均丟包率對比

圖3 平均端到端延遲對比

可以看出，本文方法在網絡總吞吐率、網絡平均丟包率、網絡端到端的延遲方面均優于文獻[7]方法。

5 結語

為了對Mesh網絡的路由進行優化，本文提出了一種量子粒子群的最優路徑算法。首先，設計了路由發現、路由維護和路由修復過程；然后基于量子粒子群對路由進行優化，在路由優化過程中全面考慮網絡總吞吐率、網絡平均丟包率、網絡端到端的延遲。在NS-2環境下進行仿真實驗，仿真實驗證明了文中方法與其他方法相比具有較大的網絡總吞吐率、較小的網絡平均丟包率和網絡端到端的延遲。

[1]王嵚琦,何新貴,徐明.無線Mesh網絡路由協議的研究進展[J].計算機工程與設計,2009(10):2341-2349.

[2]A Laouiti,P Muhlethaler,A Najid,et al.Simulation results of the OLSR routing protocol for wireless network[C].Italy,Sardegna,1stMediterranean Ad-Hoc Networks Workshop,2002.

[3]閆茜,楊金程.結合混合式信道分配的Mesh多路徑路由協議[J].計算機應用,2010(30):2505-2508.

[4]鄧曉衡,劉強,李旭,等.鏈路質量與負載敏感的無線Mesh網絡路由協議[J].計算機學報,2013(36):2009-2118.

[5]石文孝,許銀龍,王繼紅,等.無線Mesh網絡干擾與區域負載感知路由度量[J].北京郵電大學學報,2014(37):41-44.

[6]潘琢金,吳昊,羅振,等.無線Mesh網絡先驗式多樹路由協議的研究與NS-3仿真[J].微電子學與計算機,2016(33):45-49.

[7]何凌,黃俊.基于混合無線網狀網協議的改進算法研究[J].計算機應用研究,2011(28):1846-1849.

DesignforOptimalRouteofMeshNetworkBasedonParticleSwarmAlgorithm

ZHAO Hong-wei

(Suzhou Industrial Park, Service Outsourcing, Career Academy, Suzhou Jiangsu 215123, China)

The design for the optimal route design only considers the output and length. Aiming at this problem, an optimal route algorithm based on particle swarm algorithm is proposed. Firstly, the performance indexes are considered in detail, then the route protocol including route finding, route maintaining and route repairing are designed. The quantum particle swarm algorithm is used to optimize the route, on the basis of the total output, average packet loss rate and the delay between two ports. The simulation in NS-2 has verified the total output, average packet loss rate and the delay between two ports comprehensively. The result shows that the method in this paper has the high total output and low average packet loss rate and the delay between two ports.

optimal route; route protocol; Mesh network; communication

TP393

A

2095-7602(2017)12-0038-05

2017-05-03

趙宏偉(1980- )，男，工程師，碩士研究生，從事計算機應用、軟件工程研究。