于小民，夏換，楊秀璋，范郁鋒

（1.貴州財(cái)經(jīng)大學(xué)貴州省經(jīng)濟(jì)系統(tǒng)仿真重點(diǎn)實(shí)驗(yàn)室，貴陽550025；2.貴州財(cái)經(jīng)大學(xué)信息學(xué)院，貴陽 550025；3.貴州財(cái)經(jīng)大學(xué)計(jì)劃財(cái)務(wù)處，貴陽 550025）

0 引言

無線Mesh網(wǎng)絡(luò)（Wireless Mesh Network）以其優(yōu)良的特性被廣泛應(yīng)用于區(qū)域局域網(wǎng)之中，如大型車間、庫房、實(shí)驗(yàn)室等，由于其橋接和多跳的特點(diǎn)極大提高了網(wǎng)絡(luò)部署的靈活性和數(shù)據(jù)傳輸質(zhì)量，在以后的物聯(lián)網(wǎng)領(lǐng)域甚至是我們平時(shí)所應(yīng)用的移動網(wǎng)絡(luò)領(lǐng)域，Mesh網(wǎng)絡(luò)都會發(fā)揮出不可估量的作用。

基于無線Mesh網(wǎng)絡(luò)的特性，路由算法對其而言是至關(guān)重要的?，F(xiàn)在關(guān)于Mesh網(wǎng)絡(luò)的路由算法也是不勝其數(shù)如基于遺傳算法和QoS（Quality of Service，服務(wù)質(zhì)量）模型的路由算法等，但是這些算法的評估函數(shù)數(shù)值均是基于所選擇的路徑，自始至終也沒有一個(gè)最佳的評估數(shù)值，在現(xiàn)實(shí)的網(wǎng)絡(luò)架設(shè)中其實(shí)是需要這樣的一個(gè)最佳評估值作為衡量標(biāo)準(zhǔn)的，設(shè)計(jì)師可以以這個(gè)衡量標(biāo)準(zhǔn)作為參考，確定需要選擇Mesh節(jié)點(diǎn)的參數(shù)以及確定各個(gè)節(jié)點(diǎn)安裝位置的方案。

本算法對于灰狼算法（Grey Wolf algorithm）進(jìn)行改進(jìn)，從而能夠在Mesh節(jié)點(diǎn)承受的參數(shù)（帶寬、數(shù)據(jù)處理延遲和傳輸時(shí)間、丟包率）范圍內(nèi)算出節(jié)點(diǎn)之間的最佳性能參數(shù)，也算出在各個(gè)參數(shù)最佳情況下的Mesh網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)淖罴汛鷥r(jià)，然后以最佳代價(jià)為模板在Mesh網(wǎng)絡(luò)中選擇路由方案，當(dāng)方案所產(chǎn)生的路由代價(jià)和最佳路由代價(jià)最接近的時(shí)候可以確定所產(chǎn)生的路由路徑為最佳路徑。

綜上，本研究主要旨在提供一種新的無線Mesh路由算法此算法不僅能夠選擇出路由路徑還能提供最佳路徑參考模板協(xié)助衡量所選的路由路徑質(zhì)量以及網(wǎng)絡(luò)節(jié)點(diǎn)架設(shè)質(zhì)量。

1 無線Mesh網(wǎng)絡(luò)及QoS模型

1.1 無線Mesh網(wǎng)絡(luò)

如圖1所示無線Mesh與傳統(tǒng)網(wǎng)絡(luò)的主要區(qū)別在于它的無線傳輸拓?fù)浣Y(jié)構(gòu)，傳統(tǒng)網(wǎng)絡(luò)中節(jié)點(diǎn)路由之間不能相互連接多采用星型結(jié)構(gòu)，起始節(jié)點(diǎn)要傳輸數(shù)據(jù)的時(shí)候直接將數(shù)據(jù)傳輸給路由節(jié)點(diǎn)，由路由節(jié)點(diǎn)將數(shù)據(jù)傳輸給目標(biāo)節(jié)點(diǎn)，由于這種傳輸結(jié)構(gòu)的限制，目標(biāo)節(jié)點(diǎn)和起始節(jié)點(diǎn)必須連接在一個(gè)路由節(jié)點(diǎn)上，由于網(wǎng)絡(luò)信號傳輸距離是有限的，這樣的傳輸結(jié)構(gòu)大大限制了網(wǎng)絡(luò)。但是，在無線Mesh網(wǎng)絡(luò)中路由節(jié)點(diǎn)之間可以相互連接從而形成骨干網(wǎng)絡(luò)如圖1所示，起始節(jié)點(diǎn)可以跟最近（網(wǎng)絡(luò)信號最強(qiáng)或者是最符合算法要求）的路由節(jié)點(diǎn)相連接，連接之后數(shù)據(jù)通過骨干網(wǎng)絡(luò)中的節(jié)點(diǎn)以多跳的方式一步一步傳輸給目標(biāo)節(jié)點(diǎn)，以這種傳輸方式目標(biāo)節(jié)點(diǎn)不需要和起始節(jié)點(diǎn)連接在一個(gè)路由節(jié)點(diǎn)上。也可以達(dá)到數(shù)據(jù)傳輸給目標(biāo)節(jié)點(diǎn)的目的。

圖1 WNM拓?fù)浣Y(jié)構(gòu)

1.2 QoS約束模型

QoS本身是一種網(wǎng)絡(luò)安全機(jī)制，它主要是通過控制和約束各種基礎(chǔ)技術(shù)的參數(shù)來控制網(wǎng)絡(luò)的傳輸能力，這種參數(shù)配比主要是基于現(xiàn)有技術(shù)的局限性，如果網(wǎng)絡(luò)傳輸?shù)膸捒梢詿o限大、延遲時(shí)間無限小、丟包率為0那么QoS模型就沒有存在的意義了，正因?yàn)檫@三項(xiàng)參數(shù)和網(wǎng)絡(luò)傳輸代價(jià)息息相關(guān)所以需要QoS模型均衡各個(gè)參數(shù)來使網(wǎng)絡(luò)達(dá)到最好的效果。QoS模型參數(shù)定義如下：

（1）時(shí)延：

（2）帶寬：

（3）丟包率：

（4）代價(jià)：

根據(jù)無線Mesh網(wǎng)絡(luò)的特點(diǎn)我們執(zhí)行基于QoS模型的路由算法就是在滿足QoS模型約束（小于最大延遲、大于最小帶寬、小于最大丟包率）的基礎(chǔ)上使產(chǎn)生的傳輸代價(jià)最小或者是最佳的路由路徑。在某些特定的情況下我們可能會把評價(jià)函數(shù)設(shè)置成最符合我們要求的函數(shù)的評估值可能不是最小但是在某種程度上最符合我們對網(wǎng)絡(luò)傳輸?shù)囊?，滿足QoS模型公式表達(dá)為：

其中D為最大延遲時(shí)間，B為最小帶寬，L為最大丟包率。

2 算法原理及其設(shè)計(jì)

2.1 灰狼算法原理

灰狼算法的主要思想是將決定最終結(jié)果值的數(shù)據(jù)轉(zhuǎn)換成多維坐標(biāo)系統(tǒng)中的維度，將我們需要的最佳結(jié)果定義為坐標(biāo)系系中的位置，在坐標(biāo)系中有N頭尋找最佳結(jié)果的坐標(biāo)節(jié)點(diǎn)即所說的捕獲獵物的灰狼，灰狼的位置以及獵物的坐標(biāo)值會根據(jù)評估函數(shù)以及α狼、β狼、γ狼的位置不斷更新，其中α狼、β狼、γ狼分別是第一符合、第二符合、第三符合評估函數(shù)標(biāo)準(zhǔn)的三個(gè)點(diǎn)的坐標(biāo)。其他狼的位置根據(jù)距離三頭狼的位置更新坐標(biāo)，而獵物的位置為三頭狼坐標(biāo)的平均值，算法以這種方式不斷迭代，直到最終尋找到我們需要的最優(yōu)結(jié)果的位置即α狼的位置一直不發(fā)生變化。

2.2 基于灰狼算法QoS最優(yōu)參數(shù)算法

本文提出的Mesh網(wǎng)絡(luò)路由算法，首先需要利用灰狼算法算出最優(yōu)解，在QoS模型中每個(gè)傳輸節(jié)點(diǎn)有三個(gè)變量來決定傳輸代價(jià)，分別為帶寬（Bandwidth）、時(shí)延（Delay）、丟包率（Loss）。所以在本算法中每個(gè)維度的變量由這三部分組成，決定最優(yōu)解的維度為數(shù)據(jù)傳輸經(jīng)過Mesh節(jié)點(diǎn)的個(gè)數(shù)。

利用灰狼算法計(jì)算Mesh網(wǎng)絡(luò)傳輸?shù)淖罴崖窂侥０?，設(shè)尋找最優(yōu)解的灰狼個(gè)數(shù)為N，設(shè)數(shù)據(jù)傳輸經(jīng)過G個(gè)Mesh節(jié)點(diǎn)即灰狼在G維度空間中尋找最優(yōu)解，那么可以表示為Xn=(Xi1,Xi2,…,XiG)。在首次利用評估函數(shù)計(jì)算的時(shí)候計(jì)算數(shù)值最符合要求的前三個(gè)節(jié)點(diǎn)命名為α、β、γ三只頭狼，在下一輪計(jì)算中群狼的位置由α狼、β狼、γ狼決定。

在捕食過程中灰狼首先對獵物采取包圍行動，所以開始要做的灰狼和獵物（最優(yōu)解）之間的距離：

在公式中Xp(t)為第t代時(shí)獵物的位置向量，在本算法對應(yīng)的是第t代G個(gè)節(jié)點(diǎn)帶寬（Bandwidth）、時(shí)延（Delay）、丟包率（Loss）的參數(shù)代入評估函數(shù)后所得到數(shù)值，X(t)代表第t代灰狼的位置，A和C分別代表系數(shù)，a隨著迭代次數(shù)從2線性遞減到0；r1和r2為[0,1]之間的隨機(jī)數(shù)。

從上面的公式可以知道要對獵物進(jìn)行包圍，那么我們首先需要確定獵物的位置，在本算法中獵物的位置由上一代離獵物最近的α狼、β狼、γ狼確定：

在本算法中每個(gè)維度包含三個(gè)變量（帶寬、時(shí)延、丟包率）對于三個(gè)變量均采用上述算法即可找出每個(gè)維度每個(gè)變量最合適的綜合節(jié)點(diǎn)，經(jīng)過多次迭代之后即可得到最符合評估函數(shù)的G個(gè)Mesh節(jié)點(diǎn)的路由路徑。

經(jīng)過上述處理之后函數(shù)可以找出供對比使用的最佳函G跳Mesh數(shù)據(jù)傳輸路由模板，同時(shí)此模板也可以作為衡量網(wǎng)絡(luò)架設(shè)質(zhì)量的參考。

得到最佳模板之后，可以根據(jù)最佳模板Mesh節(jié)點(diǎn)之間的參數(shù)衡量節(jié)點(diǎn)與起始Mesh節(jié)點(diǎn)相連接的參數(shù)衡量函數(shù)為：

Len為兩節(jié)點(diǎn)之間和起始連接所有節(jié)點(diǎn)參數(shù)與此段標(biāo)準(zhǔn)參數(shù)之間的差距，在兩點(diǎn)之間，與起始節(jié)點(diǎn)所有相連節(jié)點(diǎn)中選擇和標(biāo)準(zhǔn)參數(shù)差距最小的參數(shù)作為起始節(jié)點(diǎn)的下一跳節(jié)點(diǎn)以此類推直到找到最終節(jié)點(diǎn)為止。

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

本算法使用Python來分析本算法所選擇的出來的路徑的質(zhì)量，仿真的數(shù)據(jù)傳輸分別通過4跳（5節(jié)點(diǎn)）、5跳（6節(jié)點(diǎn)）、6跳（7節(jié)點(diǎn)）進(jìn)行數(shù)據(jù)傳輸。傳輸所消耗的代價(jià)跟所有路徑之間作對比，然后對對比結(jié)果進(jìn)行從小到大排序，觀察所選路徑在所有路徑之間的占優(yōu)比（比所選路徑代價(jià)大的路徑的個(gè)數(shù)與所有路徑個(gè)數(shù)的比值）。按照標(biāo)準(zhǔn)對結(jié)果進(jìn)行評估。本文規(guī)定平均自占優(yōu)比在90%以上的符合試驗(yàn)要求。

如表1所示為試驗(yàn)中帶寬、時(shí)延、丟包率的取值范圍，算法在能夠滿足路由選擇的要求同時(shí)計(jì)算出最優(yōu)模板，然后以最優(yōu)模板為基礎(chǔ)選擇符合要求的路由路徑，用戶也可以根據(jù)需求進(jìn)行多次迭代直到選出占優(yōu)比為1.0（路由代價(jià)最小）的路由路徑。表2分別是5節(jié)點(diǎn)、6節(jié)點(diǎn)、7節(jié)點(diǎn)、8節(jié)點(diǎn)Mesh網(wǎng)絡(luò)數(shù)據(jù)傳輸500次數(shù)據(jù)傳輸試驗(yàn)的平均占優(yōu)比均在90%以上達(dá)到了預(yù)期實(shí)驗(yàn)?zāi)康摹?/p>

表1 實(shí)驗(yàn)數(shù)據(jù)參數(shù)范圍

表2 各節(jié)點(diǎn)平均占優(yōu)比

如圖2所示5節(jié)點(diǎn)、6節(jié)點(diǎn)、7節(jié)點(diǎn)、8節(jié)點(diǎn)，各500次試驗(yàn)（每次試驗(yàn)迭代10次將離最有模板最近評估值的路徑選為最優(yōu)路徑）所得到的占優(yōu)比分布，占優(yōu)比在0.9-1.0之間的個(gè)數(shù)都遠(yuǎn)遠(yuǎn)高于其他范圍。說明算法達(dá)到預(yù)期效果。

圖2 占優(yōu)比分布圖

3 結(jié)語

本文所提出算法的應(yīng)用除了能夠?qū)ψ罴崖酚陕窂竭M(jìn)行篩選外，還可以計(jì)算出最佳路由代價(jià)，最佳路由代價(jià)的參數(shù)除了可以為選擇路由路徑提供參考外，還可以為網(wǎng)絡(luò)架設(shè)提供標(biāo)準(zhǔn)，這樣就可以大大提高網(wǎng)絡(luò)架設(shè)和路由篩選的靈活性。除此之外用戶還可以根據(jù)選擇Mesh路由節(jié)點(diǎn)的參數(shù)調(diào)節(jié)最適合的當(dāng)前網(wǎng)絡(luò)的參數(shù)如我們網(wǎng)絡(luò)是速度型的那么我們可以將延遲時(shí)間所占的路由代價(jià)比重調(diào)節(jié)地更高那么算法就可以直接根據(jù)需求選出有所傾向的最佳路由代價(jià)，這對于網(wǎng)絡(luò)的靈活性也是非常重要的。