趙宏偉

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

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

趙宏偉

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

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

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

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

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

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

1 網(wǎng)絡(luò)性能評(píng)價(jià)

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

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

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

(1)

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

網(wǎng)絡(luò)吞吐率越高，網(wǎng)絡(luò)能負(fù)載能力就越強(qiáng)，網(wǎng)絡(luò)的性能就越好。

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

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

(2)

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

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

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

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

(3)

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

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

2 路由協(xié)議

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

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

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

2.2 路由維護(hù)

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

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

2.3 路由修復(fù)

當(dāng)建立的路由由于網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)涞淖兓r(shí)，原因可能是由于目的節(jié)點(diǎn)到源節(jié)點(diǎn)返回的路由信息丟失或者數(shù)據(jù)傳輸過(guò)程中的鏈路斷開(kāi)。當(dāng)RREQ從源節(jié)點(diǎn)出發(fā)，經(jīng)過(guò)若干中間節(jié)點(diǎn)，最后到達(dá)目標(biāo)節(jié)點(diǎn)后，目標(biāo)節(jié)點(diǎn)會(huì)根據(jù)反向路由發(fā)送RREQ數(shù)據(jù)包。在數(shù)據(jù)傳輸?shù)倪^(guò)程中，如果路徑發(fā)生中斷，傳輸失敗的中間節(jié)點(diǎn)向源節(jié)點(diǎn)發(fā)送錯(cuò)誤信息RERR(routing error packet)，而源節(jié)點(diǎn)在收到錯(cuò)誤信息RERR后，會(huì)重啟路由發(fā)現(xiàn)過(guò)程以找到新的路徑。

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

3.1 量子粒子群概述

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

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

(4)

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

(5)

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

(6)

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

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

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

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

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

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

③計(jì)算粒子的適應(yīng)度：

(7)

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

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

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

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

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

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

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

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

否則轉(zhuǎn)入②進(jìn)行繼續(xù)迭代。

4 仿真實(shí)驗(yàn)

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

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

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

圖3 平均端到端延遲對(duì)比

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

5 結(jié)語(yǔ)

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

[1]王嵚琦,何新貴,徐明.無(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議的研究進(jìn)展[J].計(jì)算機(jī)工程與設(shè)計(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]閆茜,楊金程.結(jié)合混合式信道分配的Mesh多路徑路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2010(30):2505-2508.

[4]鄧曉衡,劉強(qiáng),李旭,等.鏈路質(zhì)量與負(fù)載敏感的無(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2013(36):2009-2118.

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

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

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