郭誠(chéng)欣，李陶深，葛志輝

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 南寧 530004）

1 引言

作為下一代無(wú)線網(wǎng)絡(luò)的核心技術(shù)之一，無(wú)線mesh網(wǎng)絡(luò)（wireless mesh network，WMN）擁有組網(wǎng)靈活、動(dòng)態(tài)自組織自愈、維護(hù)方便、覆蓋范圍廣、能滿足人們高容量和高速率的上網(wǎng)要求等優(yōu)點(diǎn)，已成為眾多研究者關(guān)注的熱點(diǎn)之一[1]。無(wú)線mesh網(wǎng)絡(luò)是一種通過(guò)無(wú)線介質(zhì)進(jìn)行多跳傳輸?shù)木W(wǎng)絡(luò)，主要包括3類節(jié)點(diǎn)：網(wǎng)關(guān)（gateway，GW）、mesh路由器（mesh router，MR）、mesh終端，其中網(wǎng)關(guān)和mesh路由器組成了無(wú)線mesh網(wǎng)絡(luò)的骨干網(wǎng)絡(luò)，負(fù)責(zé)給終端提供網(wǎng)絡(luò)服務(wù)。作為大部分網(wǎng)絡(luò)流量匯聚的節(jié)點(diǎn)，網(wǎng)關(guān)是整個(gè)網(wǎng)絡(luò)的瓶頸所在，網(wǎng)關(guān)部署的好壞制約著整個(gè)無(wú)線mesh網(wǎng)絡(luò)的性能。

多目標(biāo)優(yōu)化的網(wǎng)關(guān)部署問(wèn)題是一個(gè)NP難的問(wèn)題[2]，在以往的研究中，研究者將網(wǎng)關(guān)部署問(wèn)題形式化為線性規(guī)劃問(wèn)題，根據(jù)不同的目標(biāo)提出相應(yīng)的網(wǎng)關(guān)部署算法。參考文獻(xiàn)[2]根據(jù)網(wǎng)絡(luò)的R跳連通圖提出了兩種啟發(fā)式算法，達(dá)到最小化網(wǎng)關(guān)數(shù)量和最小化MR-GW路徑跳數(shù)的目的。參考文獻(xiàn)[3]和參考文獻(xiàn)[4]則把最小化網(wǎng)關(guān)部署費(fèi)用且受到一定的QoS約束問(wèn)題歸結(jié)為求解圖的最小支配集問(wèn)題，其中，參考文獻(xiàn)[3]提出了基于貪心算法的GREEDY_LDS算法和基于粒子群算法的PSO_LDS算法，前者能在較短時(shí)間內(nèi)獲得局部的最優(yōu)部署方案，后者則通過(guò)增加運(yùn)算時(shí)間，獲得全局的最優(yōu)解。參考文獻(xiàn)[4]在GREEDY_LDS算法的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了GREEDY_LDSC算法和GREEDY_LDSI算法，分別提高了網(wǎng)關(guān)部署的性價(jià)比和部署費(fèi)用。參考文獻(xiàn)[5]提出了基于負(fù)載權(quán)重的貪心式網(wǎng)關(guān)部署算法，在最小化網(wǎng)關(guān)數(shù)量的同時(shí)消減鏈路干擾，實(shí)現(xiàn)網(wǎng)關(guān)間的負(fù)載均衡。上述的網(wǎng)關(guān)部署算法都是基于全向天線的環(huán)境，不可避免地要考慮通信干擾等問(wèn)題。相對(duì)于全向天線，定向天線的使用能提高整個(gè)無(wú)線mesh網(wǎng)絡(luò)的性能，包括降低節(jié)點(diǎn)間的干擾、提高空間復(fù)用率、增加網(wǎng)絡(luò)吞吐量[6,7]等。

近年來(lái)，越來(lái)越多的學(xué)者開(kāi)始研究將定向天線應(yīng)用于無(wú)線mesh網(wǎng)絡(luò)的問(wèn)題，以達(dá)到提高網(wǎng)絡(luò)整體性能的目的。參考文獻(xiàn)[8]介紹了使用定向天線對(duì)于整個(gè)網(wǎng)絡(luò)性能的提升程度，將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)設(shè)定為一個(gè)網(wǎng)格結(jié)構(gòu)，其中每一個(gè)節(jié)點(diǎn)裝備一條4陣列的波束天線，分析了網(wǎng)絡(luò)在吞吐量、時(shí)延、公平性上獲得的增益大小。參考文獻(xiàn)[9]介紹了在WMN中使用三扇天線系統(tǒng)的性能，指出使用三扇天線能解決以往使用定向天線后出現(xiàn)的許多問(wèn)題，如隱藏終端和暴露終端、“盲點(diǎn)（deafness）”等。參考文獻(xiàn)[10]在IEEE 802.11s標(biāo)準(zhǔn)下提出了類似的結(jié)構(gòu)，在不同的方向上使用不同的固定波束天線，每一條天線覆蓋一個(gè)固定區(qū)域，能達(dá)到覆蓋全角度的目的，同時(shí)減少了路由開(kāi)銷。上述的研究工作主要集中于MAC層，網(wǎng)絡(luò)部署方面的研究仍不多，參考文獻(xiàn)[11]將Delaunay圖應(yīng)用于定向天線下WMN骨干網(wǎng)的部署優(yōu)化，通過(guò)刪除三角形的多余邊，達(dá)到簡(jiǎn)化網(wǎng)絡(luò)拓?fù)?、降低部署的定向天線數(shù)量、減少部署花費(fèi)的目的。參考文獻(xiàn)[12]則研究定向天線下無(wú)線mesh骨干網(wǎng)的網(wǎng)關(guān)部署問(wèn)題，提出了基于節(jié)點(diǎn)通信量的啟發(fā)式算法，達(dá)到最小化網(wǎng)關(guān)數(shù)量以及最小化路由器到最近網(wǎng)關(guān)的平均跳數(shù)和最大跳數(shù)的目的，但文中研究的網(wǎng)關(guān)部署是在隨機(jī)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上進(jìn)行的，而隨機(jī)的拓?fù)浣Y(jié)構(gòu)并不利于充分發(fā)揮定向天線的優(yōu)勢(shì)，如某些鏈路間的夾角過(guò)小、節(jié)點(diǎn)間的距離過(guò)小，均會(huì)導(dǎo)致定向天線間過(guò)大的干擾出現(xiàn)。

Delaunay三角因其良好的數(shù)學(xué)特性被廣泛應(yīng)用于無(wú)線網(wǎng)絡(luò)的部署中，如無(wú)線傳感器網(wǎng)絡(luò)部署[13,14]，可增加網(wǎng)絡(luò)的覆蓋率，最小化網(wǎng)絡(luò)部署成本。本文將研究定向天線下無(wú)線mesh骨干網(wǎng)的網(wǎng)關(guān)部署問(wèn)題，以Delaunay三角作為網(wǎng)絡(luò)的部署拓?fù)浣Y(jié)構(gòu)，綜合考慮網(wǎng)絡(luò)部署成本和通信時(shí)延等因素，根據(jù)圖論的緊密中心性理論，將MR-GW總距離最短問(wèn)題歸結(jié)為尋找圖的中心點(diǎn)問(wèn)題，同時(shí)在滿足一定的QoS約束下，使得網(wǎng)關(guān)數(shù)量最小。

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

2.1 問(wèn)題描述

網(wǎng)關(guān)節(jié)點(diǎn)是整個(gè)WMN與互聯(lián)網(wǎng)相連的關(guān)鍵節(jié)點(diǎn)，WMN中任何節(jié)點(diǎn)對(duì)于互聯(lián)網(wǎng)的服務(wù)請(qǐng)求都要經(jīng)過(guò)網(wǎng)關(guān)節(jié)點(diǎn)，相對(duì)于其他只負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)或提供接入服務(wù)的路由節(jié)點(diǎn)，網(wǎng)關(guān)節(jié)點(diǎn)需要有更高的性能與可靠性，以保證網(wǎng)絡(luò)的正常運(yùn)行。除此之外，網(wǎng)關(guān)節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置也影響著整個(gè)網(wǎng)絡(luò)的性能，網(wǎng)關(guān)節(jié)點(diǎn)的位置關(guān)系著網(wǎng)絡(luò)時(shí)延、網(wǎng)絡(luò)吞吐量等網(wǎng)絡(luò)性能指標(biāo)，需要在多個(gè)約束條件下進(jìn)行部署。本文研究WMN骨干網(wǎng)的優(yōu)化，每個(gè)節(jié)點(diǎn)上部署適當(dāng)數(shù)目的定向天線，在滿足用戶帶寬需求和網(wǎng)絡(luò)性能的基礎(chǔ)上，把WMN邏輯上劃分為互不相交的簇，根據(jù)算法合理地選擇節(jié)點(diǎn)作為網(wǎng)關(guān)，以降低部署成本和MR到網(wǎng)關(guān)的時(shí)延，同時(shí)兼顧網(wǎng)關(guān)的負(fù)載均衡和控制節(jié)點(diǎn)的介質(zhì)競(jìng)爭(zhēng)，即對(duì)MR的總流通量進(jìn)行合理的劃分以及對(duì)每個(gè)網(wǎng)關(guān)所服務(wù)的節(jié)點(diǎn)總數(shù)進(jìn)行約束。由于網(wǎng)關(guān)的成本遠(yuǎn)大于普通的MR，所以可通過(guò)網(wǎng)關(guān)的數(shù)量反映網(wǎng)關(guān)部署的成本，MR到網(wǎng)關(guān)的時(shí)延則反映在MR-GW的路徑長(zhǎng)度，因此本文研究的問(wèn)題有兩個(gè)優(yōu)化目標(biāo)：最小化網(wǎng)關(guān)數(shù)量和最小化MR-GW的路徑長(zhǎng)度。

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

本文將整個(gè)無(wú)線mesh網(wǎng)絡(luò)的骨干網(wǎng)建模為一個(gè)無(wú)向連通Delaunay圖G(V,E)，V={v1,v2,…,vn}代表節(jié)點(diǎn)集合，n為網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)，E為邊的集合，即無(wú)線鏈路集合。節(jié)點(diǎn)的位置坐標(biāo)可用二元組(x,y)表示，則節(jié)點(diǎn)vi與vj之間的歐氏距離為假設(shè)定向天線的最大傳輸距離為L(zhǎng)max，為了減少定向天線存在的干擾，設(shè)定節(jié)點(diǎn)間的最小傳輸距離為L(zhǎng)min。因此無(wú)線鏈路集合E={(vi,vj)|Lmin≤Lmin(i,j)≤Lmax,i≠j}，則圖G的鄰接矩陣為：

其中，ai,j表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間是否存在無(wú)線鏈路，若(vi,vj)∈E，則ai,j=1；否則，ai,j=0。節(jié)點(diǎn)間的鏈路距離表示為ω，大小等于兩節(jié)點(diǎn)間的歐幾里德距離，網(wǎng)關(guān)節(jié)點(diǎn)集合表示為VG，則非網(wǎng)關(guān)節(jié)點(diǎn)集合表示為VNG。

向量Z={z1,z2,…,zn}表示網(wǎng)關(guān)的選取情況，當(dāng)節(jié)點(diǎn)vi被選為網(wǎng)關(guān)節(jié)點(diǎn)時(shí)，zi=1；否則，zi=0。Ti表示節(jié)點(diǎn)vi的最大流通量。分簇C是G的一個(gè)子圖，即C(V′,E′)哿G(V,E),V′哿V,E′哿E,Cg表示以網(wǎng)關(guān)vg為根節(jié)點(diǎn)的分簇，|Cg|表示以網(wǎng)關(guān)vg為根節(jié)點(diǎn)的分簇的節(jié)點(diǎn)數(shù)量。λ(i,j)表示節(jié)點(diǎn)vi通過(guò)單跳或多跳的方式連接到網(wǎng)關(guān)vj，δ(i,j)表示節(jié)點(diǎn)vi通過(guò)單跳或多跳與節(jié)點(diǎn)vj間的最短距離，Tg表示網(wǎng)關(guān)vg的最大流通量，S表示分簇的節(jié)點(diǎn)數(shù)量上限。根據(jù)以上的設(shè)定，本文研究的網(wǎng)絡(luò)數(shù)學(xué)模型表示如下。

優(yōu)化目標(biāo)：

約束條件：

式（2）表示最小化網(wǎng)關(guān)的數(shù)量，式（3）表示MR到網(wǎng)關(guān)的總距離最短，式（4）表示每個(gè)非網(wǎng)關(guān)節(jié)點(diǎn)僅與1個(gè)網(wǎng)關(guān)節(jié)點(diǎn)相連，式（5）表示每個(gè)以網(wǎng)關(guān)節(jié)點(diǎn)為根的分簇節(jié)點(diǎn)數(shù)量不超過(guò)S，式（6）表示分簇中的MR總流通量不超過(guò)網(wǎng)關(guān)的最大流通量。

3 基于緊密中心性的網(wǎng)關(guān)部署算法

3.1 算法描述

本文將網(wǎng)關(guān)優(yōu)化部署問(wèn)題歸結(jié)為線性規(guī)劃問(wèn)題，根據(jù)圖的緊密中心性（closeness centrality）理論，提出了一種基于緊密中心性的網(wǎng)關(guān)部署（gateway deployment based on closeness centrality，GDCC）算法。根據(jù)圖論的緊密中心性理論，緊密度是圖中一個(gè)節(jié)點(diǎn)的中心性度量，而在網(wǎng)絡(luò)分析中，節(jié)點(diǎn)的緊密度定義為節(jié)點(diǎn)到其他節(jié)點(diǎn)的總路徑和的倒數(shù)，因此，如果一個(gè)節(jié)點(diǎn)越靠近中心，該節(jié)點(diǎn)到其他節(jié)點(diǎn)的總路徑和越小。GDCC算法的設(shè)計(jì)思想是：在滿足流通量或網(wǎng)關(guān)服務(wù)節(jié)點(diǎn)數(shù)量約束的子圖中，以貪心算法找出圖的中心節(jié)點(diǎn)或是靠近中心的節(jié)點(diǎn)，達(dá)到子圖中MR到網(wǎng)關(guān)總路徑最短的目標(biāo)，從而使得MR-GW總距離最短。GDCC算法的另外一個(gè)目標(biāo)則是根據(jù)網(wǎng)絡(luò)流通量進(jìn)行合理的網(wǎng)絡(luò)劃分，使之實(shí)現(xiàn)在滿足QoS約束條件下，網(wǎng)關(guān)數(shù)量最小的目標(biāo)。GDCC算法的步驟如下。

步驟1收集網(wǎng)絡(luò)的信息（包括節(jié)點(diǎn)最大流通量、坐標(biāo)等），形成Delaunay圖，計(jì)算網(wǎng)絡(luò)的總流通量，決定是否進(jìn)行劃分。

步驟2從左下角的節(jié)點(diǎn)開(kāi)始進(jìn)行寬度優(yōu)先的節(jié)點(diǎn)遍歷，當(dāng)所遍歷的節(jié)點(diǎn)總流通量達(dá)到網(wǎng)關(guān)的最大流通量或達(dá)到上限S時(shí)，形成Delaunay子圖。

步驟3根據(jù)子圖中的節(jié)點(diǎn)坐標(biāo)求出圖的中心點(diǎn)坐標(biāo)，求出圖中各節(jié)點(diǎn)到中心坐標(biāo)的歐式距離，選出距離最短的3個(gè)節(jié)點(diǎn)，分別計(jì)算到各個(gè)節(jié)點(diǎn)的總距離，總距離最短的節(jié)點(diǎn)作為網(wǎng)關(guān)的部署節(jié)點(diǎn)。將所遍歷的節(jié)點(diǎn)從鄰接矩陣中刪除。

步驟4在剩余的鄰接矩陣中重復(fù)步驟2和步驟3，直到遍歷所有的節(jié)點(diǎn)，選出所需的網(wǎng)關(guān)。

步驟5輸出所選的網(wǎng)關(guān)節(jié)點(diǎn)坐標(biāo)。

3.2 算法過(guò)程的實(shí)例說(shuō)明

本節(jié)通過(guò)一個(gè)實(shí)例，說(shuō)明GDCC算法的執(zhí)行過(guò)程。為了簡(jiǎn)化演示過(guò)程，以下使用一個(gè)包含25個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)作為一次遍歷后形成的Delaunay子圖，拓?fù)浣Y(jié)構(gòu)如圖1所示。

首先計(jì)算圖1網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的中點(diǎn)坐標(biāo)，求出子網(wǎng)絡(luò)中各節(jié)點(diǎn)到中點(diǎn)的歐幾里德距離，得到距離最小的3個(gè)節(jié)點(diǎn)作為候選網(wǎng)關(guān)集，如圖2所示。

然后算法分別計(jì)算3個(gè)候選網(wǎng)關(guān)到其他節(jié)點(diǎn)的總距離，總距離最小的節(jié)點(diǎn)作為最后的網(wǎng)關(guān)節(jié)點(diǎn)。經(jīng)過(guò)計(jì)算，節(jié)點(diǎn)2到其他節(jié)點(diǎn)的總距離最小，則選該節(jié)點(diǎn)為此子網(wǎng)絡(luò)的網(wǎng)關(guān)節(jié)點(diǎn)，如圖3所示，六角星表示網(wǎng)關(guān)節(jié)點(diǎn)。

圖1 遍歷后得到Delaunay子圖

圖2 獲得候選網(wǎng)關(guān)集

圖3 完成網(wǎng)關(guān)部署

4 實(shí)驗(yàn)結(jié)果和算法性能分析

本文利用MATLAB工具對(duì)提出的算法進(jìn)行仿真實(shí)驗(yàn)。對(duì)比分析本文的GDCC算法、Degree based GDTSP[2]算法和隨機(jī)算法的實(shí)驗(yàn)結(jié)果，進(jìn)而對(duì)GDCC算法的有效性和可行性進(jìn)行評(píng)價(jià)。

在實(shí)驗(yàn)中，各節(jié)點(diǎn)按照最短路徑與網(wǎng)關(guān)進(jìn)行連接通信，節(jié)點(diǎn)隨機(jī)均勻分布，節(jié)點(diǎn)間的距離近似相等，因此實(shí)驗(yàn)中使用MR-GW的總跳數(shù)表示MR-GW的總距離。為了方便計(jì)算，設(shè)定所有MR節(jié)點(diǎn)的本地流通量為單位1，網(wǎng)關(guān)vg的最大流通量Tg為25，此時(shí)網(wǎng)關(guān)的最大流通量相當(dāng)于服務(wù)的節(jié)點(diǎn)數(shù)，即分簇節(jié)點(diǎn)數(shù)量的上限S也為25個(gè)。

實(shí)驗(yàn)一將GDCC算法與Degree based GDTSP算法進(jìn)行網(wǎng)關(guān)數(shù)量的比較，分析兩種算法在相同情況下網(wǎng)關(guān)數(shù)量的差異以及原因，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 網(wǎng)關(guān)數(shù)量與網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的關(guān)系

為了更好地進(jìn)行比較實(shí)驗(yàn)，實(shí)驗(yàn)二將網(wǎng)絡(luò)的網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量限制為1個(gè)，比較GDCC算法、Degree based GDTSP算法和隨機(jī)算法所得的MR-GW總跳數(shù)，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 單網(wǎng)關(guān)下各算法的MR-GW總跳數(shù)比較

從圖5中可以看出，在網(wǎng)絡(luò)節(jié)點(diǎn)較少時(shí)，3種算法得到的MR-GW總跳數(shù)幾乎沒(méi)有差別，這是因?yàn)榇藭r(shí)3種算法得到的網(wǎng)關(guān)節(jié)點(diǎn)位置大致相同且節(jié)點(diǎn)數(shù)量較少，不同網(wǎng)關(guān)位置帶來(lái)的總跳數(shù)的增加并不明顯。隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量增加到15個(gè)以后，GDCC算法的優(yōu)勢(shì)開(kāi)始體現(xiàn)，MR-GW總跳數(shù)明顯較少。這是由于Degree based GDTSP算法在多跳鄰接圖中選擇的是鄰居節(jié)點(diǎn)最多的節(jié)點(diǎn)，隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加，相同情況下鄰居節(jié)點(diǎn)數(shù)量相同的節(jié)點(diǎn)數(shù)會(huì)增加，從這些節(jié)點(diǎn)中選擇網(wǎng)關(guān)位置時(shí)則會(huì)出現(xiàn)所選網(wǎng)關(guān)位置并不總能使網(wǎng)絡(luò)的MR-GW總跳數(shù)最小的情況，最后的結(jié)果略優(yōu)于隨機(jī)算法。

實(shí)驗(yàn)三是根據(jù)節(jié)點(diǎn)的位置生成Delaunay圖，分別計(jì)算出GDCC算法和隨機(jī)算法的網(wǎng)關(guān)節(jié)點(diǎn)位置，考察兩個(gè)算法的MR-GW總跳數(shù)變化情況，實(shí)驗(yàn)結(jié)果如圖6所示。從圖6中可以看出，當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，GDCC算法的MR-GW總跳數(shù)小于隨機(jī)算法，而且隨著節(jié)點(diǎn)數(shù)量的增加，這種差距變得更為明顯，因此在最小化MR-GW總跳數(shù)上，GDCC算法通過(guò)計(jì)算選取的網(wǎng)關(guān)節(jié)點(diǎn)比隨機(jī)網(wǎng)關(guān)節(jié)點(diǎn)更有優(yōu)勢(shì)。

不同的網(wǎng)關(guān)最大流通量對(duì)MR-GW總跳數(shù)也有一定的影響。實(shí)驗(yàn)三主要是研究分析網(wǎng)關(guān)最大流通量與MR-GW總跳數(shù)的關(guān)系。在實(shí)驗(yàn)中，假定實(shí)驗(yàn)骨干網(wǎng)包含100個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)保持不變，實(shí)驗(yàn)結(jié)果如圖7所示。從圖7中可以看出，在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量和拓?fù)浣Y(jié)構(gòu)相同的情況下，隨著網(wǎng)關(guān)vg最大流通量Tg的增大，MR-GW總跳數(shù)也隨之增加。原因在于GDCC算法從網(wǎng)關(guān)的最大流通量Tg出發(fā)，以Tg限制分簇節(jié)點(diǎn)數(shù)量，當(dāng)Tg較小時(shí)，分簇內(nèi)的節(jié)點(diǎn)數(shù)量較少，以網(wǎng)關(guān)為根的分簇?cái)?shù)量增加，使得MR-GW總跳數(shù)減少；當(dāng)Tg增大時(shí)，分簇內(nèi)的節(jié)點(diǎn)數(shù)增加，以網(wǎng)關(guān)為根的分簇?cái)?shù)量減少，使得MR-GW總跳數(shù)增加。另外，圖6中顯示，當(dāng)Tg從25增加到30時(shí)，MR-GW的總跳數(shù)卻沒(méi)有明顯增加，原因在于GDCC算法從網(wǎng)關(guān)的最大流通量Tg出發(fā)對(duì)網(wǎng)絡(luò)進(jìn)行劃分，將網(wǎng)關(guān)的數(shù)量控制為 ，這是在網(wǎng)關(guān)的負(fù)載能力之內(nèi)能滿足用戶需求的最小網(wǎng)關(guān)數(shù)量，因此，當(dāng)Tg分別為25和30時(shí)，網(wǎng)關(guān)數(shù)量皆為4個(gè)，MR-GW總跳數(shù)沒(méi)有明顯增加。

圖6 不同節(jié)點(diǎn)數(shù)量對(duì)MR-GW總跳數(shù)的影響

圖7 不同的網(wǎng)關(guān)最大流通量對(duì)MR-GW總跳數(shù)的影響

綜上所述，GDCC算法依據(jù)網(wǎng)關(guān)最大流通量的不同對(duì)網(wǎng)絡(luò)進(jìn)行合理劃分，在一定的QoS約束下，保證在網(wǎng)關(guān)的負(fù)載能力之內(nèi)滿足用戶的需求，獲得最少的網(wǎng)關(guān)數(shù)量，同時(shí)MR-GW的總距離最短。

5 結(jié)束語(yǔ)

本文研究定向天線下無(wú)線mesh骨干網(wǎng)絡(luò)的網(wǎng)關(guān)部署問(wèn)題，將Delaunay圖應(yīng)用于網(wǎng)關(guān)部署中，提出了基于中心性理論的無(wú)線mesh骨干網(wǎng)絡(luò)網(wǎng)關(guān)部署算法GDCC。該算法先根據(jù)網(wǎng)絡(luò)流通量進(jìn)行網(wǎng)絡(luò)劃分，再利用圖的緊密中心性理論，找出到各節(jié)點(diǎn)總距離最短的網(wǎng)關(guān)節(jié)點(diǎn)。仿真實(shí)驗(yàn)結(jié)果表明，在一定的QoS約束下，GDCC算法得到的網(wǎng)關(guān)數(shù)量最少，MR-GW總距離最短。

下一步工作是研究整個(gè)無(wú)線mesh網(wǎng)絡(luò)的優(yōu)化部署，通過(guò)限制每個(gè)節(jié)點(diǎn)的度來(lái)簡(jiǎn)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，在保持網(wǎng)絡(luò)連通性的前提下，減少定向天線的使用數(shù)量，進(jìn)一步降低網(wǎng)絡(luò)的部署費(fèi)用。

1 Akyildiz I F,Wang X D,Wang W L.Wireless mesh networks:a survey.Computer Networks,2005,47(4):445～487

2 He B,Xie B,Agrawal D P.Optimizing deployment of internet gateway in wireless mesh networks.Computer Communications,2008,31(7):1259～1275

3 曾鋒,陳志剛,鄧曉衡.無(wú)線mesh網(wǎng)中費(fèi)用最小且QoS約束的網(wǎng)關(guān)部署算法研究.通信學(xué)報(bào),2009,30(6):80～88 Zeng F,Chen Z G,Deng X H.Minimum-cost gateway placement in wireless mesh networks with QoS constraints.Journal on Communications,2009,30(6):80～88

4 翦鵬,漆華妹,陳志剛.無(wú)線mesh網(wǎng)絡(luò)中基于最小權(quán)有限支配集的網(wǎng)關(guān)部署算法研究.計(jì)算機(jī)工程與科學(xué),2011,33(8):14～18 Jian P,Qi H M,Chen Z G.Research of a gateway deployment algorithm for wireless mesh networks based on the limited dominating set.Computer Engineering＆Science,2011,33(8):14～18

5 吳文甲,楊明,羅軍舟等.干擾約束和負(fù)載均衡的無(wú)線mesh網(wǎng)絡(luò)網(wǎng)關(guān)部署策略.計(jì)算機(jī)學(xué)報(bào),2012,35(5):883～897 Wu W J,Yang M,Luo J D,et al.A gateway placement scheme with interference constraints and load balance in wireless mesh networks.Chinese Journal of Computers,2012,35(5):883～897

6 Dai H N,Ng K W,Wu M Y,et al.On the capacity of multichannel wireless networks using directional antennas.Proceedings of INFOCOM,Phoenix,AZ,USA,2008

7 Yeh P C,Stark W E,Zummo S A.Performance analysis of wireless networks with directional antennas.IEEE Transactions on Vehicular Technology,2008,57(5):3187～3199

8 Kandasamy S,Campos R,Morla R,et al.Using directional antennas on stub wireless mesh networks:impact on throughput,delay,and fairness.Proceedings of 19th International Conference on Computer Communications and Networks,Zurich,Switzerland,2010:1～6

9 Okada H,Mase K.Performance analysis of wireless mesh networks with three sector antennas.Proceedings of the 6th International Wireless Communications and Mobile Computing Conference,Caen,France,2010

10 Ben-Othman J,Mokdad L,Cheikh M O.A new architecture of wireless mesh networks based IEEE 802.11s directional antennas.Proceedings of IEEE International Conference on Communications,Kyoto,Japan,2011:1～5

11 Li W G,Li T S,Ge Z H.A delaunay triangulation based method for optimizing backbone wireless mesh networks.Proceedings of International Conference on Computer Science and Service System,Nanjing,China,2011:959～962

12 Hu Z P,Verma P K.Gateway placement in backbone wireless mesh networks using directional antennas.Proceedings of the 9th Annual Communication Networks and Services Research Conference,Ottawa,ON,Canada,2011:175～180

13 Wu C H,Lee K C,Chung Y C.A Delaunay triangulation based method for wireless sensor network deployment.Proceedings of the 12th International Conference on Parallel and Distributed Systems,Minneapolis,MN,USA,2006

14 Gao J J,Zhou J P.Delaunay-based heterogeneous wireless sensor network deployment.Proceedings of the 8th International Conference on Wireless Communications,Networking and Mobile Computing,Shanghai,China,2012:1～5