趙宏偉

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

Mesh網(wǎng)絡中基于粒子群優(yōu)化的最優(yōu)路徑算法

趙宏偉

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

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

最優(yōu)路徑；路由協(xié)議；Mesh網(wǎng)絡；通信

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

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

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

1 網(wǎng)絡性能評價

在設計路由協(xié)議時，最優(yōu)路由的目標函數(shù)需要考慮的主要性能指標有網(wǎng)絡總吞吐率、網(wǎng)絡平均丟包率和端到端的平均時延。

1.1 網(wǎng)絡總吞吐率

網(wǎng)絡總吞吐率是網(wǎng)絡中所有接收端在單位時間內(nèi)正確接收的數(shù)據(jù)量，單位為kbit/s，表達式為：

(1)

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

網(wǎng)絡吞吐率越高，網(wǎng)絡能負載能力就越強，網(wǎng)絡的性能就越好。

1.2 網(wǎng)絡平均丟包率

網(wǎng)絡的平均丟包率是網(wǎng)絡中所有接收端接受到的正確的數(shù)據(jù)包與網(wǎng)絡中所有輸入端發(fā)出的所有的數(shù)據(jù)包的總量的比值，其計算方法為：

(2)

其中，N是網(wǎng)絡中接收端接收到的所有正確的數(shù)據(jù)包的集合，|N|為網(wǎng)絡中的所有接收端接收的正確的數(shù)據(jù)包數(shù)，Nsum表示網(wǎng)絡中發(fā)送端發(fā)送的所有數(shù)據(jù)包的總和。

網(wǎng)絡丟包率反應了網(wǎng)絡的可靠性，網(wǎng)絡的丟包率越低，網(wǎng)絡越可靠，網(wǎng)絡的性能越好。

1.3 網(wǎng)絡端到端延遲

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

(3)

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

網(wǎng)絡端到端延遲反應了數(shù)據(jù)在網(wǎng)絡中傳輸?shù)目炻?。網(wǎng)絡端到端的延遲越小，網(wǎng)絡性能越好。

2 路由協(xié)議

2.1 路由發(fā)現(xiàn)

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

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

2.2 路由維護

路由發(fā)現(xiàn)用于建立源節(jié)點到目標節(jié)點之間的有效路由，通過該過程建立有效路由并進行數(shù)據(jù)傳輸。然而，由于無線網(wǎng)絡的動態(tài)性，當前路由的吞吐量可能下降甚至路由可能失效。網(wǎng)絡中可能由于動態(tài)性的變化，存在著更好的路徑。

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

2.3 路由修復

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

3 基于量子粒子群的最優(yōu)路徑

3.1 量子粒子群概述

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

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

(4)

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

(5)

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

(6)

3.2 基于改進量子粒子群的模型參數(shù)優(yōu)化算法

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

算法1 基于量子粒子群的最優(yōu)路由算法

初始化：粒子種群規(guī)模M，當前迭代次數(shù)i，迭代次數(shù)最大值；

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

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

③計算粒子的適應度：

(7)

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

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

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

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

⑤根據(jù)公式(4)計算個體平均最優(yōu)位置；

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

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

如果達到，輸出最優(yōu)路由；

否則轉入②進行繼續(xù)迭代。

4 仿真實驗

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

圖1 網(wǎng)絡總吞吐率比較

圖2 網(wǎng)絡平均丟包率對比

圖3 平均端到端延遲對比

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

5 結語

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

[1]王嵚琦,何新貴,徐明.無線Mesh網(wǎng)絡路由協(xié)議的研究進展[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多路徑路由協(xié)議[J].計算機應用,2010(30):2505-2508.

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

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

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

[7]何凌,黃俊.基于混合無線網(wǎng)狀網(wǎng)協(xié)議的改進算法研究[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- )，男，工程師，碩士研究生，從事計算機應用、軟件工程研究。