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

趙云飛，陳志剛，曾鋒

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2.1 網(wǎng)絡模型

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

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

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

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

2.2 問題描述

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

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

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

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

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

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

3.1 算法描述

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

饑餓算法Hungry_Placement，算法如下。

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

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

算法步驟如下。

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

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

步驟 3：把沒有重復的節(jié)點直接分在相應的確定簇集合中CCi。

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

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

3.2 算法圖示

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

圖1 原網(wǎng)絡拓撲圖Fig.1 Original network topology

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

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

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

4 實驗仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

[1] 王玉磊. 無線Mesh網(wǎng)關鍵技術分析[J]. 網(wǎ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)絡公平性研究[J]. 中國科學技術大學學報, 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].軟件學報, 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)中實現(xiàn)網(wǎng)關負載均衡部署的混合算法[J]. 系統(tǒng)仿真學報, 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.

(編輯 何運斌)

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

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

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