趙云飛，陳志剛，曾鋒

(1. 中南大學(xué) 軟件學(xué)院，湖南 長沙，410075；2. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

WMN中基于網(wǎng)關(guān)饑餓度的部署算法優(yōu)化

趙云飛1,2，陳志剛1,2，曾鋒1

(1. 中南大學(xué) 軟件學(xué)院，湖南 長沙，410075；2. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

研究滿足QoS約束條件的網(wǎng)關(guān)負(fù)載均衡部署優(yōu)化問題，定義網(wǎng)關(guān)饑餓度衡量網(wǎng)關(guān)負(fù)載均衡性，并提出網(wǎng)關(guān)部署的饑餓算法，在為每一簇分配網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)，都盡量使其簇頭(網(wǎng)關(guān))饑餓度最大程度接近網(wǎng)絡(luò)總的平均值，最終實(shí)現(xiàn)網(wǎng)關(guān)間負(fù)載均衡，同時(shí)滿足QoS約束。仿真實(shí)驗(yàn)結(jié)果表明：饑餓算法得到的網(wǎng)關(guān)數(shù)量與其他傳統(tǒng)算法得到的結(jié)果非常接近，甚至更優(yōu)；而在網(wǎng)關(guān)負(fù)載均衡方面，饑餓算法優(yōu)勢較明顯，與 Greedy_Partition算法相比，網(wǎng)關(guān)饑餓度樣本標(biāo)準(zhǔn)方差約減少54%。

無線Mesh網(wǎng)；網(wǎng)關(guān)部署；負(fù)載均衡；饑餓算法；饑餓度

無線Mesh網(wǎng)絡(luò)(wireless mesh network, WMN)是一種高速率、高容量的分布式網(wǎng)絡(luò)，具有組網(wǎng)方便、簡單和可擴(kuò)展等優(yōu)點(diǎn)，是解決“最后1 km”問題的網(wǎng)絡(luò)結(jié)構(gòu)[1]。無線 Mesh網(wǎng)絡(luò)是一種多跳傳輸網(wǎng)絡(luò)，由Mesh路由器節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)和客戶端節(jié)點(diǎn)3種類型的節(jié)點(diǎn)組成。其中，網(wǎng)關(guān)節(jié)點(diǎn)是一種特殊的 Mesh路由器節(jié)點(diǎn)，不單是具有 Mesh路由器節(jié)點(diǎn)的功能，還通過有線電纜與Internet直接相連。全部的Mesh路由器節(jié)點(diǎn)構(gòu)成了無線 Mesh網(wǎng)的骨干網(wǎng)，客戶節(jié)點(diǎn)的數(shù)據(jù)經(jīng)由多個(gè) Mesh路由器轉(zhuǎn)發(fā)匯聚到網(wǎng)關(guān)，再通過網(wǎng)關(guān)實(shí)現(xiàn)客戶端對Internet的訪問。除了節(jié)點(diǎn)偶爾發(fā)生(部署)失敗或增加外，無線Mesh網(wǎng)有相對固定的拓?fù)浣Y(jié)構(gòu)。幾乎全部的流量匯聚到或者來自網(wǎng)關(guān)節(jié)點(diǎn)，而不像Ad hoc網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)直接可以進(jìn)行流量傳輸。網(wǎng)關(guān)節(jié)點(diǎn)將直接連接固定網(wǎng)絡(luò)，從而構(gòu)成了無線Mesh網(wǎng)的流量匯聚地和流量源頭，這樣在實(shí)際的網(wǎng)絡(luò)運(yùn)行中，合理部署網(wǎng)關(guān)可以提升無線 Mesh網(wǎng)的性能[2]，反之就很容易形成網(wǎng)關(guān)流量負(fù)載不均衡的現(xiàn)象。網(wǎng)關(guān)流量負(fù)載不均衡將會導(dǎo)致以下問題：(1) 負(fù)載過大(饑餓度過小)的網(wǎng)關(guān)不能保證全部客戶端節(jié)點(diǎn)的QoS(服務(wù)質(zhì)量)。由于無線Mesh網(wǎng)中存在QoS的不公平[3?5]，離網(wǎng)關(guān)較近的客戶端節(jié)點(diǎn)能夠得到較優(yōu)的服務(wù)。對離網(wǎng)關(guān)較遠(yuǎn)的客戶端節(jié)點(diǎn)，網(wǎng)關(guān)負(fù)載過大導(dǎo)致QoS難于保證；(2) 負(fù)載較小(饑餓度較大)的網(wǎng)關(guān)不能充分利用其資源為更多的客戶端節(jié)點(diǎn)提供服務(wù)。為提升性能并降低路由復(fù)雜性，無線 Mesh網(wǎng)常常劃分為互不相交的若干簇，每個(gè)簇由一網(wǎng)關(guān)擔(dān)當(dāng)簇首，并為簇內(nèi)的節(jié)點(diǎn)提供服務(wù)，因此每一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)所服務(wù)的客戶端節(jié)點(diǎn)數(shù)量是相對固定的，負(fù)載較輕的網(wǎng)關(guān)節(jié)點(diǎn)不能充分利用其剩余的資源為更多的客戶端提供服務(wù)；(3) 由于網(wǎng)關(guān)節(jié)點(diǎn)是無線Mesh網(wǎng)性能的瓶頸[6]，即使網(wǎng)絡(luò)匯聚的流量遠(yuǎn)遠(yuǎn)低于其最大容量，網(wǎng)關(guān)負(fù)載的不均衡也會導(dǎo)致較差的網(wǎng)絡(luò) QoS。解決無線 Mesh網(wǎng)中網(wǎng)關(guān)部署問題，主要是達(dá)到最小化網(wǎng)關(guān)數(shù)量和網(wǎng)關(guān)之間的負(fù)載均衡的目標(biāo)，同時(shí)能確保滿足QoS約束。定義網(wǎng)關(guān)饑餓度來衡量網(wǎng)關(guān)間負(fù)載均衡性，并提出饑餓算法來把無線Mesh網(wǎng)劃分成滿足QoS約束的若干簇。針對無線 Mesh網(wǎng)中網(wǎng)關(guān)部署問題，設(shè)計(jì)一個(gè)較優(yōu)的分簇算法，盡可能地實(shí)現(xiàn)網(wǎng)關(guān)之間的負(fù)載均衡，同時(shí)保證滿足QoS要求。

1 相關(guān)工作

網(wǎng)關(guān)部署問題可被視為在運(yùn)籌學(xué)和近似算法領(lǐng)域研究中更為一般的容量設(shè)備選址問題的一個(gè)實(shí)例。在過去的幾年中，研究者已經(jīng)做了大量關(guān)于設(shè)備選址問題的近似算法[7]的設(shè)計(jì)和分析的工作，如非固定容量設(shè)備選址問題[8]和 K中心聚類問題[9]。其他的研究工作提出了K跳分簇算法，但都不能滿足分簇問題的所有要求，并且?guī)缀醵疾荒茉谛阅軆?yōu)化方面得到保證。

針對無線 Mesh網(wǎng)中網(wǎng)關(guān)部署問題，有些學(xué)者把它模型化為線性規(guī)劃優(yōu)化問題，并針對不同的約束條件提出了許多網(wǎng)關(guān)部署算法[10?14]。Chandra等[10]研究部署網(wǎng)關(guān)數(shù)量優(yōu)化的問題，部署中考慮到各節(jié)點(diǎn)的帶寬要求，提出了具有容錯(cuò)能力的貪婪分簇算法。Wong等[11]考慮網(wǎng)關(guān)部署中通信代價(jià)最小化及通信時(shí)延最小化2個(gè)獨(dú)立的問題，并把問題歸結(jié)成整數(shù)線性規(guī)劃優(yōu)化問題，提出了基于統(tǒng)計(jì)方法的啟發(fā)式算法。曾鋒等[12]等提出了利用遺傳算法在多目標(biāo)優(yōu)化方面的優(yōu)勢，并與貪婪算法相結(jié)合來求解達(dá)到網(wǎng)關(guān)數(shù)量最小和網(wǎng)關(guān)負(fù)載均衡的網(wǎng)關(guān)部署策略。Aoun等[13]提出 QoS約束下的網(wǎng)關(guān)部署貪婪算法 Recursive_DS。Bejerano等[14]在研究網(wǎng)關(guān)部署問題中，考慮各種無線鏈路模型，并提出了相關(guān)的貪婪算法。

上述算法都試圖在確保滿足QoS的條件下，盡可能地使部署的網(wǎng)關(guān)數(shù)量減少，在各自的網(wǎng)絡(luò)模型下也都收到了較好的效果。但是，仍有一些方面需要改善，如減少網(wǎng)關(guān)數(shù)量的同時(shí)應(yīng)考慮網(wǎng)關(guān)間的負(fù)載均衡情況，以及在實(shí)際的無線 Mesh網(wǎng)絡(luò)應(yīng)用場景中，各網(wǎng)關(guān)的最大容量不同，那么此時(shí)用網(wǎng)關(guān)流量的平均值及方差來衡量負(fù)載均衡性，就顯的不盡合理，例如，假設(shè)2網(wǎng)關(guān)G1和G2，最大容量分別是100和30，若流量負(fù)載平均值太小(＜30)，則G1的網(wǎng)關(guān)的利用率太低，反之太大(＞30)，已超過G2的最大容量，都會引起網(wǎng)關(guān)負(fù)載失衡現(xiàn)象。

本文在分析以上算法的基礎(chǔ)上，研究滿足QoS約束條件下的網(wǎng)關(guān)部署問題，與以上研究不同的是：本文以網(wǎng)關(guān)數(shù)量最小化和網(wǎng)關(guān)之間的負(fù)載均衡的雙重優(yōu)化為目標(biāo)，用網(wǎng)關(guān)資源(容量)的實(shí)際利用比例來衡量網(wǎng)關(guān)間負(fù)載均衡性，即本文定義的網(wǎng)關(guān)饑餓度，并提出了網(wǎng)關(guān)部署饑餓算法來求解達(dá)到網(wǎng)關(guān)數(shù)量最小化和網(wǎng)關(guān)負(fù)載均衡的部署策略。

2 網(wǎng)絡(luò)模型及問題描述

在無線 Mesh網(wǎng)中考慮網(wǎng)關(guān)部署的問題。WMN的骨干網(wǎng)可用1個(gè)無向連通圖G(V,E)表示。每個(gè)節(jié)點(diǎn)v∈V表示1個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，可以是WMN中的路由器節(jié)點(diǎn)或網(wǎng)關(guān)節(jié)點(diǎn)，并具有若干個(gè)單位的圓形傳輸范圍，在該傳輸范圍內(nèi)的相鄰節(jié)點(diǎn)都可以直接通信。v的鄰居節(jié)點(diǎn)集，定義為N(v)，是在它的傳輸范圍內(nèi)的節(jié)點(diǎn)集合。在節(jié)點(diǎn)v和其任一鄰居節(jié)點(diǎn)u∈N(v)之間存在一條雙向無線鏈路，并用邊 (u,v)∈E表示。頂點(diǎn)v的鄰居節(jié)點(diǎn)數(shù)稱為v的度，定義為δ(v)。圖G中最大度數(shù)成為圖的度數(shù)Δ(G)=Δ。

2.1 網(wǎng)絡(luò)模型

節(jié)點(diǎn)u和v之間的距離定義為d(u,v)，是它們之間最小的跳數(shù)值。圖G(V,E)中v的半徑是v和其他任一節(jié)點(diǎn)之間的最大距離。圖中最小的半徑值定義為圖半徑。另外，圖直徑是任意2個(gè)節(jié)點(diǎn)間的最大距離(或最大半徑)。

在集合V中，有一些節(jié)點(diǎn)通過有線電纜直接與Internet相連，稱為網(wǎng)關(guān)，WMN中的流量經(jīng)過網(wǎng)關(guān)節(jié)點(diǎn)到達(dá)Internet，用G={g1,g2, …,gc}表示網(wǎng)關(guān)的集合。剩下的節(jié)點(diǎn)v∈=V?G為普通的路由器節(jié)點(diǎn)，主要作用是匯聚轉(zhuǎn)發(fā)客戶端的流量至各自的網(wǎng)關(guān)節(jié)點(diǎn)。為研究方便，用權(quán)值W(v)表示Mesh路由器v匯集的客戶端流量。對任意網(wǎng)關(guān)gi∈G，假設(shè)網(wǎng)關(guān)的容量為C(gi)，實(shí)際負(fù)載量為L(gi)，相關(guān)計(jì)算公式如下：

其中：L(gi)為網(wǎng)關(guān)負(fù)載量； 為網(wǎng)關(guān)飽和度； 為網(wǎng)關(guān)饑餓度；為網(wǎng)關(guān)饑餓度均值。

另外，用1個(gè)鄰接矩陣來表示連通圖。圖G(V,E)的鄰接矩陣是1個(gè)用行和列標(biāo)記頂點(diǎn)V的矩陣，根據(jù)Vm和Vn是否是直接相連接，來判定(m,n)位置是1或0(直接相連為 1，反之則為 0)。對于無向圖G，鄰接矩陣是對稱的。

2.2 問題描述

在本文中，要達(dá)到無線 Mesh網(wǎng)和有線網(wǎng)絡(luò)的高效融合，同時(shí)確保滿足QoS要求。這包括在邏輯上把WMN分成不相交的若干個(gè)簇，覆蓋網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。在每個(gè)簇中，1個(gè)節(jié)點(diǎn)會擔(dān)當(dāng)網(wǎng)關(guān)，直接與有線網(wǎng)連接，并為簇內(nèi)節(jié)點(diǎn)提供服務(wù)。

基于運(yùn)作的原因，網(wǎng)關(guān)部署或分簇問題是服從QoS約束的。網(wǎng)關(guān)部署問題要考慮 QoS(服務(wù)質(zhì)量)約束，如延時(shí)和帶寬問題。在1個(gè)多跳網(wǎng)絡(luò)中，由于存在無線信道的競爭、包處理和排隊(duì)延遲等問題，顯著延時(shí)發(fā)生在每一跳中。延遲是一個(gè)與源端和網(wǎng)關(guān)之間的通信跳數(shù)相關(guān)的函數(shù)。延遲約束可以轉(zhuǎn)化為一個(gè)有上界的簇半徑R，或者是以網(wǎng)關(guān)為根的生成樹的最大深度R；通過鏈路干擾模型[15]分析網(wǎng)絡(luò)性能，可以了解到瓶頸干擾域決定端到端的帶寬，而節(jié)點(diǎn)的度數(shù)越大，其受到干擾的可能性越大，其干擾域的權(quán)值就會越大，因此，為確保端到端的帶寬，節(jié)點(diǎn)在簇中的度數(shù)不能超過有上界的節(jié)點(diǎn)度數(shù)D；同時(shí)，給簇規(guī)模一個(gè)上界S，以確保網(wǎng)絡(luò)的各項(xiàng)性能。因此，網(wǎng)關(guān)部署問題轉(zhuǎn)化為在邏輯上把WMN劃分成覆蓋全部節(jié)點(diǎn)的不相交簇集合，并全部滿足3個(gè)QoS約束。

本文研究的網(wǎng)關(guān)部署問題，就是盡量保持網(wǎng)關(guān)數(shù)量最少和網(wǎng)關(guān)負(fù)載間均衡，同時(shí)，各簇的規(guī)模、節(jié)點(diǎn)的度及節(jié)點(diǎn)與網(wǎng)關(guān)間的距離滿足上界S，D和R，則該問題可以抽象為整數(shù)線性規(guī)劃優(yōu)化問題，定義N=V為網(wǎng)絡(luò)節(jié)點(diǎn)集合，G?V為網(wǎng)關(guān)集合，G是V的子集。定義yi∈{0,1}，對于節(jié)點(diǎn)vi∈V，若vi∈G(G為網(wǎng)關(guān)集合)，則yi=1；否則yi=0。定義xij∈{0, 1}，若節(jié)點(diǎn)vj的指定網(wǎng)關(guān)為gi，則xij=1；否則xij=0。定義hij為節(jié)點(diǎn)vj與網(wǎng)關(guān)vi之間的最短距離，單位為跳。定義δ(v)為節(jié)點(diǎn)v在簇內(nèi)的度數(shù)。目標(biāo)函數(shù)如下：

這樣，優(yōu)化部署問題化為2個(gè)總體目標(biāo)：即最小化網(wǎng)關(guān)數(shù)量K和網(wǎng)關(guān)負(fù)載均衡，其中Evar為網(wǎng)關(guān)饑餓度的樣本標(biāo)準(zhǔn)差。同時(shí)，條件(a)表示V中任一節(jié)點(diǎn)有且僅有1個(gè)指定網(wǎng)關(guān)；條件(b)表示網(wǎng)關(guān)在做為簇頭前需要先建立；條件(c)表示在節(jié)點(diǎn)和指定網(wǎng)關(guān)間存在一條路徑并且最短距離不大于R跳；條件(d)和(e)提供了簇規(guī)模和簇內(nèi)度數(shù)的上界約束；最后一個(gè)條件(f)表示yi和xij是二進(jìn)制變量。

據(jù)上所述，本文研究的網(wǎng)關(guān)負(fù)載均衡的部署問題抽象為整數(shù)線性規(guī)劃優(yōu)化問題，該問題是 NP難問題[10]。因此，本文提出饑餓算法，根據(jù)給定網(wǎng)關(guān)進(jìn)行WMN分簇，利用饑餓算法Hungry_ Placement來求問題的較優(yōu)解。

3 網(wǎng)關(guān)部署優(yōu)化的饑餓算法

3.1 算法描述

在實(shí)際的無線 Mesh網(wǎng)絡(luò)應(yīng)用場景中，各網(wǎng)關(guān)的最大容量不相同(容量足夠大)，本文提出網(wǎng)關(guān)饑餓度來度量網(wǎng)關(guān)間負(fù)載均衡性，并設(shè)計(jì)了饑餓算法來對WMN分簇，更好地提高網(wǎng)關(guān)間的負(fù)載均衡程度。

饑餓算法Hungry_Placement，算法如下。

輸入：初始的網(wǎng)關(guān)節(jié)點(diǎn)序列；

輸出：完整的網(wǎng)關(guān)節(jié)點(diǎn)序列和分簇方案。

算法步驟如下。

步驟1：gi∈G為根QoS約束廣度遍歷，建立可能簇集合ICi(各簇間可含重復(fù)節(jié)點(diǎn))；

步驟 2：若有節(jié)點(diǎn)沒被可能簇集合簇覆蓋，在未覆蓋的節(jié)點(diǎn)中隨機(jī)(按概率)選擇一節(jié)點(diǎn)，假設(shè)為vu，G=G+{vu}，并以vu為根QoS約束廣度遍歷建可能簇集合ICi，若所有節(jié)點(diǎn)都被可能簇集合簇覆蓋，則繼續(xù)下一步；否則，轉(zhuǎn)步驟2。

步驟 3：把沒有重復(fù)的節(jié)點(diǎn)直接分在相應(yīng)的確定簇集合中CCi。

步驟 4：把網(wǎng)關(guān)集合G按負(fù)載均衡排序(插入排序)， (gi)≤β(gj)≤…≤ (k)，求出網(wǎng)關(guān)饑餓度的均值，在gk可能簇集合ICk中尋找合適的節(jié)點(diǎn)，該節(jié)點(diǎn)負(fù)載流量可以使網(wǎng)關(guān)gk的饑餓度最大程度的接近網(wǎng)絡(luò)平均“饑餓”水平，并把該節(jié)點(diǎn)加入gk的確定簇集合CCk，并在所有可能簇集合中剔除該節(jié)點(diǎn)。

步驟 5：若所有節(jié)點(diǎn)都被確定簇集合簇覆蓋，則算法結(jié)束；否則轉(zhuǎn)步驟4。

3.2 算法圖示

饑餓算法簡單示例如下圖1～4所示，圖1所示為無線Mesh網(wǎng)拓?fù)浣Y(jié)構(gòu)，其中隨機(jī)選取R1和R22節(jié)點(diǎn)為網(wǎng)關(guān)節(jié)點(diǎn)，網(wǎng)關(guān)節(jié)點(diǎn)R1和R2的最大容量分別為60和80，其余節(jié)點(diǎn)為普通路由節(jié)點(diǎn)；利用饑餓算法建立可能簇集合，由于不能覆蓋所有節(jié)點(diǎn)，在未覆蓋的節(jié)點(diǎn)中按概率選擇一節(jié)點(diǎn)(假設(shè)R9，容量為55)為網(wǎng)關(guān)，并建立第3個(gè)可能簇，如圖2中不同的虛線所圈表示，IC1={R3,R4,R5,R7}，IC2={R4,R5,R6,R8}，IC9={R8,R10}，由3個(gè)可能簇集合可知：節(jié)點(diǎn)R2被網(wǎng)關(guān)R1唯一覆蓋，所以直接把R2加到網(wǎng)關(guān)R1的確定簇中，即CC1={R1}，以此類推，CC2={R6}，CC9={R10}，網(wǎng)關(guān)集合G={R1,R2,R9}；按照饑餓算法的定義公式計(jì)算可得：各網(wǎng)關(guān)饑餓度分別為β(R1)=80.0%，β(R2)=90.0%，β(R9)=72.0%，網(wǎng)關(guān)的饑餓均值為=80.9%，由此可知網(wǎng)關(guān)R2的饑餓度最大，那么在可能簇IC2中選擇一個(gè)合適節(jié)點(diǎn)，其節(jié)點(diǎn)流量可以使網(wǎng)關(guān)R2的饑餓度最大程度的接近網(wǎng)絡(luò)平均“饑餓”水平，經(jīng)計(jì)算得到，該合適節(jié)點(diǎn)為R5，則將節(jié)點(diǎn)R5加入網(wǎng)關(guān)R2的確定簇中，即CC2={R5，R6}，并把R5從所有可能簇集合中剔除；以此類推，最終計(jì)算得到如圖 4所示的分簇結(jié)果及網(wǎng)關(guān)節(jié)點(diǎn)信息，CC1={R1,R3,R4,R7}，CC2={R5,R6,R8},CC9={R9,R10}，最終各網(wǎng)關(guān)饑餓度分別為β(R1)=68.3%，β(R2)=71.2%，β(R9)=70.0%，總的網(wǎng)關(guān)饑餓度均值為=69.8%，由以上數(shù)據(jù)可知：各網(wǎng)關(guān)的流量負(fù)載較均衡(網(wǎng)關(guān)資源利用率較高)，因而得到的網(wǎng)絡(luò)分簇方案較優(yōu)。該算法結(jié)束條件是所有的可能簇集合均為空。

圖1 原網(wǎng)絡(luò)拓?fù)鋱DFig.1 Original network topology

圖2 以網(wǎng)關(guān)節(jié)點(diǎn)為簇頭的可能簇集合ICiFig.2 Gateways with head node of possible cluster collections ICi

圖3 對節(jié)點(diǎn)R5的選擇與分簇Fig.3 Selecting and clustering for node R5

圖4 最終分簇結(jié)果及網(wǎng)關(guān)節(jié)點(diǎn)信息Fig.4 Last clustering result and information of gateways

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

為驗(yàn)證本文提出算法的正確和有效性，進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)使用Microsoft Visual C++ 6.0在PC上編程實(shí)現(xiàn)，主機(jī)配置：CPU為Intel Core2 ?2.93 GHz，內(nèi)存為1.96 G，操作系統(tǒng)為Windows Xp。

首先實(shí)驗(yàn)隨機(jī)生成一定數(shù)量的網(wǎng)絡(luò)拓?fù)鋱D，圖中節(jié)點(diǎn)權(quán)值在[1, 20]隨機(jī)取值，然后，分別應(yīng)用Greedy_Partition算法[12](圖中略為Greedy)、本文提出的 Hungry_ Placement算法(圖中略為 Hungry)對隨機(jī)圖構(gòu)造滿足節(jié)點(diǎn)度數(shù)上限D(zhuǎn)、跳數(shù)上限R以及簇規(guī)模上限S的網(wǎng)關(guān)部署方案，并從網(wǎng)關(guān)數(shù)量K比較和網(wǎng)關(guān)負(fù)載均衡度Var的比較對實(shí)驗(yàn)結(jié)果平均值進(jìn)行分析。

4.1 網(wǎng)關(guān)數(shù)量和負(fù)載均衡的綜合比較

實(shí)驗(yàn)在15×15的區(qū)域隨機(jī)放置150個(gè)節(jié)點(diǎn)，隨機(jī)生成500個(gè)網(wǎng)絡(luò)拓?fù)鋱D，并對節(jié)點(diǎn)度數(shù)上限D(zhuǎn)、跳數(shù)上限R以及簇規(guī)模上限S取不同值，求各種情況下Hungry_ Placement算法與Greedy_Partition算法構(gòu)造得到的網(wǎng)關(guān)數(shù)量平均值K和網(wǎng)關(guān)負(fù)載均衡度Evar的情況，結(jié)果如圖5～11所示。

圖5 R取值對網(wǎng)關(guān)數(shù)量的影響(D=6, S=20)Fig.5 Impact of hop R value on number of gateways

圖6 R取值對網(wǎng)關(guān)負(fù)載均衡的影響(D=6, S=20)Fig.6 Impact of hop R value on load balance of gateways

由圖5和圖6可見：在QOS約束下，節(jié)點(diǎn)度數(shù)上限D(zhuǎn)和簇規(guī)模上限S固定不變，隨著跳數(shù)上限R的逐漸增大，Hungry_Placement算法與Greedy_Partition算法構(gòu)造得到的K值逐漸減少，但兩者非常接近；2種算法得到的Evar在R由2跳逐漸變?yōu)?跳間直線增加，當(dāng)R＞4后，呈現(xiàn)緩慢增加的走勢，但Hungry_Placemen算法取得的Evar遠(yuǎn)低于 Greedy_Partition算法取得的值。

由圖7和圖8可見：在QOS約束下，節(jié)點(diǎn)跳數(shù)上限R和簇規(guī)模上限S固定不變，隨著度數(shù)上限D(zhuǎn)的逐漸增大，Hungry_Placement算法與Greedy_Partition算法構(gòu)造得到的K逐漸減少，但兩者非常接近，前者甚至更優(yōu)；Greedy_Partition算法得到的Evar隨著D的加大而急速增大，并在D=8時(shí)Evar最大，而 Hungry_Placemen算法取得的Evar隨著D的加大變化不大，較平穩(wěn)，在R=4時(shí)取得最小值。同時(shí)，Hungry_Placemen算法取得的Evar遠(yuǎn)低于 Greedy_ Partition算法取得的值。

圖7 D取值對網(wǎng)關(guān)數(shù)量的影響(R=4, S=20)Fig.7 Impact of degree D value on number of gateways

圖8 D取值對網(wǎng)關(guān)負(fù)載均衡的影響(R=4, S=20)Fig.8 Impact of degree D value on load balance of gateways

圖9 S取值對網(wǎng)關(guān)數(shù)量的影響(D=6, R=4)Fig.9 Impact of cluster size S value on number of gateways

圖10 S取值對網(wǎng)關(guān)負(fù)載均衡影響(D=6, R=4)Fig.10 Impact of cluster size S value on load balance of gateways

由圖9和圖10可見：在QOS約束下，節(jié)點(diǎn)跳數(shù)上限R和度數(shù)上限D(zhuǎn)固定不變，隨著簇規(guī)模上限S的增大，Hungry_ Placement算法與Greedy_Partition算法構(gòu)造得到的K值逐漸減少，但兩者非常接近；2種算法得到的Evar也隨著D的加大而呈直線走勢增大，但 Hungry_Placemen算法取得的Evar遠(yuǎn)低于 Greedy_Partition算法取得的值。

圖11 10次試驗(yàn)數(shù)據(jù)平均值對比分析(D=6, R=4, S=20)Fig.11 Var’ average value of 10 times experiments

由圖11可見：在QOS約束下，節(jié)點(diǎn)跳數(shù)上限R=4，度數(shù)上限D(zhuǎn)=6，簇規(guī)模上限S=20，進(jìn)行的10次試驗(yàn)所得Evar的平均值顯示，與Greedy_Partition算法相比，Hungry_ Placement算法網(wǎng)關(guān)取得的Evar約減少54%，表現(xiàn)較好。

綜上分析可得：Hungry_ Placement算法得到的K值與Greedy_Partition算法得到的數(shù)據(jù)非常接近，甚至更優(yōu)，但取得的Evar值遠(yuǎn)遠(yuǎn)低于Greedy_Partition算法取得的值。因此，饑餓算法實(shí)現(xiàn)了網(wǎng)關(guān)部署的網(wǎng)關(guān)負(fù)載均衡。

5 結(jié)論

(1) 無線 Mesh網(wǎng)網(wǎng)關(guān)部署問題是影響網(wǎng)絡(luò)性能的瓶頸。本文在分析已有算法的基礎(chǔ)上，以網(wǎng)關(guān)數(shù)量最小化和網(wǎng)關(guān)間負(fù)載均衡為雙重優(yōu)化目標(biāo)，研究滿足QoS約束下的網(wǎng)關(guān)部署問題。提出饑餓算法，定義網(wǎng)關(guān)“饑餓”度來度量網(wǎng)關(guān)間負(fù)載均衡性，并用算法實(shí)現(xiàn)對WMN分簇，得到較優(yōu)的解，更好地提高了網(wǎng)關(guān)間的負(fù)載均衡程度。

(2) 饑餓算法得到的網(wǎng)關(guān)數(shù)量與其他算法得到的結(jié)果非常相近，甚至更小；而在網(wǎng)關(guān)負(fù)載均衡方面，饑餓算法優(yōu)勢明顯，達(dá)到了網(wǎng)關(guān)數(shù)量最小化與負(fù)載均衡的雙重優(yōu)化目標(biāo)。

(3) 下一步將繼續(xù)展開在無線 Mesh網(wǎng)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化下的網(wǎng)關(guān)負(fù)載均衡部署策略方面的研究。

[1] 王玉磊. 無線Mesh網(wǎng)關(guān)鍵技術(shù)分析[J]. 網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2007(4): 92?94.

WANG Yulei. Analysis of the key technology of wireless mesh networks[J]. Network Security Technology & Application,2007(4): 92?94.

[2] Robinson J, Knightly E W. A performance study of deployment factors in wireless mesh networks proc[C]// INFOCOM 2007.26th IEEE Int. Conf. Computer Communications. Anchorage:IEEE, 2007: 2054?2062.

[3] 張勇, 蔡杰, 宋梅, 等. 無線mesh網(wǎng)絡(luò)公平性研究[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2007, 37(2): 164?170.

ZHANG Yong, CAI Jie, SONG Mei, et al. Study on the fairness of wireless mesh networks[J]. Journal of University of Science and Technology of China, 2007, 37(2): 164?170.

[4] 楊盤隆, 陳貴海. 無線網(wǎng)狀網(wǎng)容量分析與優(yōu)化理論研究[J].軟件學(xué)報(bào), 2008, 19(1): 111?125.

YANG Panlong, CHEN Guihai. Research paradigm of capacity analysis and optimizing theory on wireless mesh network[J].Journal of Software, 2008, 19(1): 111?125.

[5] Jun J, Sichitiu M L. Fairness and QoS in multihop wireless networks[C]// Proc VTC 2003-Fall Vehicular Technology Conf.2003 IEEE 58th. Orlando: IEEE, 2003: 2936?2940.

[6] WU Xiaobing, LIU Jiangchuan, CHEN Guihai. Analysis of bottleneck delay and throughput in wireless mesh networks[C]//Proc IEEE Int Mobile Adhoc and Sensor Systems (MASS) Conf,2006: 765?770.

[7] David B S. Approximation algorithms for facility location problems[J]. APPROX, 2000(9): 27?32.

[8] Kuehn A, Hamburger M J. A heuristic program for locating warehouses[J]. Management Science, 1963, 9: 643?666.

[9] Arora S, Raghavan P, Rao S. Approximation schemes for Euclideank-medians and related problems[J]. ACM Symposium on Theory of Computing, 1998: 106?113.

[10] Chandra R, Qiu L, Jain K, et al. Optimizing the placement of Internet TAPs in wireless neighborhood networks[C]// Proc 12th IEEE Int. Conf. Network Protocols ICNP 2004. Washington:IEEE, 2004: 271?282.

[11] Wong J L, Jafari R, Potkonjak M. Gateway placement for latency and energy efficient data aggregation[C]// Proc 29th Annual IEEE Int Local Computer Networks Conf. Tampa: IEEE, 2004:490?497.

[12] 曾鋒, 陳志剛, 趙明, 等. 無線 Mesh網(wǎng)中實(shí)現(xiàn)網(wǎng)關(guān)負(fù)載均衡部署的混合算法[J]. 系統(tǒng)仿真學(xué)報(bào), 2009, 21(10): 3029?3034.

ZENG Feng, CHEN Zhigang, ZHAO Ming, et a1. Hybrid algorithm for load-balance placement of gateways in wireless mesh network[J]. Journal of System Simulation, 2009, 21(10):3029?3034.

[13] Aoun B, Boutaba R, Iraqi Y, et al. Gateway placement optimization in wireless mesh networks with QoS constraints[J].IEEE Journal Selected Areas in Communications: 2127?2136.

[14] Bejerano Y. Efficient integration of multihop wireless and wired networks with QoS constraints[J]. Networking, IEEE/ACM Transactions, 2004, 12(6): 1064?1078.

[15] Jun J, Sichitiu M L. The nominal capacity of wireless mesh networks[J]. Wireless Communications, IEEE, 2003, 10: 8?14.

(編輯 何運(yùn)斌)

Placement algorithm optimization in
wireless mesh networks based on gateways’ hungry-value

ZHAO Yunfei1,2, CHEN Zhigang1,2, ZENG Feng1

(1. School of Software, Central South University, Changsha 410075, China;2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

The problem of gateways deployment was addressed to achieve the goal of load balance in gateway placement with QoS requirements being satisfied, the gateways’ hungry-value was defined to measure the load-balance of gateways,and a hungry algorithm was presented for network clustering. When network nodes was assigned for each cluster, the hungry value of gateway should become close to their average of hungry value as much as possible and achieve load balance placement of gateways in the end. At the same time, it always meets the QoS constraints during the entire clustering process. The results show that the number of gateways generated by the hungry algorithm is nearly equal to those from other gateway placement algorithms, and as far as the load balance of gateways is concerned, the hungry algorithm performs much better than the others. Specially, compared with Greedy_Partition algorithm, the hungry algorithm improves the load balance of gateways with the standard deviation of the gateways’ hungry value decreased by 54%.

wireless mesh network; gateway placement; load balance; hungry algorithm; hungry-value

TP393

A

1672?7207(2013)11?4492?07

2012?08?20；

2012?10?10

國家自然科學(xué)基金資助項(xiàng)目(61103202，61073186)；教育部優(yōu)先資助領(lǐng)域項(xiàng)目資助(20120162130008)

陳志剛(1964?)，男，湖南益陽人，博士，教授，從事網(wǎng)絡(luò)計(jì)算與分布式處理研究；電話：13787249417；E-mail: zyf@csu.edu.cn