無線M esh網(wǎng)絡(luò)中骨干節(jié)點(diǎn)部署算法研究

凌 權(quán)，李枚毅

（湘潭大學(xué)信息工程學(xué)院，湖南湘潭411105）

無線M esh網(wǎng)絡(luò)中骨干節(jié)點(diǎn)部署算法研究

凌 權(quán)，李枚毅

（湘潭大學(xué)信息工程學(xué)院，湖南湘潭411105）

無線Mesh網(wǎng)絡(luò)是下一代無線網(wǎng)絡(luò)的關(guān)鍵技術(shù)，其骨干網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是實(shí)現(xiàn)網(wǎng)絡(luò)連接和網(wǎng)絡(luò)覆蓋率的決定性因素。針對無線Mesh網(wǎng)絡(luò)骨干網(wǎng)絡(luò)的部署優(yōu)化問題，在滿足用戶帶寬需求和網(wǎng)絡(luò)連接的前提下，以最小化M esh路由器（MR）數(shù)量為目標(biāo)提出一種有效的MR部署算法。使用粒子群算法確定網(wǎng)關(guān)的位置，之后不斷往骨干網(wǎng)絡(luò)添加權(quán)重最大的相鄰節(jié)點(diǎn)直至覆蓋所有需求。實(shí)驗(yàn)結(jié)果表明，該算法在均勻分布和正態(tài)分布場景下所部署MR的數(shù)量均少于NF-Greedy和ILSearch算法，能有效減少部署成本。

無線Mesh網(wǎng)絡(luò)；Mesh路由器部署；骨干節(jié)點(diǎn)；貪心算法；啟發(fā)式算法；粒子群

1 概述

隨著互聯(lián)網(wǎng)的普及，無線Mesh網(wǎng)絡(luò)作為一個(gè)高性能、低成本的寬帶互聯(lián)網(wǎng)接入解決方案，吸引了越來越多的人關(guān)注［1］。無線Mesh網(wǎng)絡(luò)（Wireless Mesh Network，WMN）［2］是一種動態(tài)自組織和自配置的多跳無線網(wǎng)絡(luò)，其帶寬高、可靠性好、覆蓋范圍廣、部署成本低、可擴(kuò)展性好，具有較好的發(fā)展前景。

無線M esh網(wǎng)絡(luò)基礎(chǔ)框架由3個(gè)不同類型的節(jié)點(diǎn)組成：M esh路由器（M esh Router，MR），網(wǎng)關(guān)（M esh Gatew ay，MG）以及M esh終端（Mesh Client，MC）。在WMN中，MR給其覆蓋范圍內(nèi)的M esh終端提供互聯(lián)網(wǎng)訪問，并以多跳的方式轉(zhuǎn)發(fā)網(wǎng)絡(luò)中其他Mesh路由器的數(shù)據(jù)到網(wǎng)關(guān)；MG是一種特殊的MR，它不僅具有MR的所有功能，還是連接WMN和Internet的橋梁，MG通過有線的方式與Internet連接，WMN網(wǎng)絡(luò)中的所有節(jié)點(diǎn)通過MG與Internet通信；M esh終端通常筆記本電腦、移動電話和其他無線設(shè)備，其通過MC連接到Internet。

WMN的核心部分是骨干網(wǎng)絡(luò)，骨干網(wǎng)絡(luò)由MR和MG組成，WMN的性能主要由骨干網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)（MR和MG的地理位置）所決定，合理的網(wǎng)絡(luò)部署方案可以在滿足用戶流量需求和網(wǎng)絡(luò)連通性（任何一個(gè)M esh路由器都能通過一個(gè)或多個(gè)多跳網(wǎng)絡(luò)連接到網(wǎng)關(guān)）的前提下，有效提高網(wǎng)絡(luò)性能，減少部署費(fèi)用（部署節(jié)點(diǎn)個(gè)數(shù)最?。?。關(guān)于WMN骨干網(wǎng)絡(luò)的部署優(yōu)化是當(dāng)前的研究熱點(diǎn)，Mesh路由器是骨干網(wǎng)絡(luò)的重要組成部分，M esh路由器的部署合理性對提高WMN網(wǎng)絡(luò)性能具有重要意義。M esh路由器的部署問題與設(shè)施選址問題和覆蓋集問題一樣都屬于NP-hard問題，目前已有很多學(xué)者針對M esh路由器的部署優(yōu)化問題提出了許多解決算法［3-6］，但是還存在如下問題：（1）不能完全滿足某些約束條件，如用戶帶寬需求；（2）分開考慮了MR和MG的部署優(yōu)化問題。因此，本文以無線Mesh骨干網(wǎng)絡(luò)部署為研究背景，以滿足用戶帶寬需求和MR接入容量為前提，將覆蓋和連通相結(jié)合進(jìn)行考慮，研究如何部署MR和MG。

2 相關(guān)工作

文獻(xiàn)［7］使用模擬退火算法（Simulated Annealing，SA）和遺傳算法（Genetic A lgorithm，GA）進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明SA在覆蓋方面有很好的表現(xiàn)，但是部署的節(jié)點(diǎn)數(shù)量比較多；而GA部署節(jié)點(diǎn)數(shù)量比較少，但在大多數(shù)情況下不能完全覆蓋所有需求。文獻(xiàn)［8］給出了一種動態(tài)環(huán)境下的Mesh路由部署方法。針對這種場景，他們以最大化網(wǎng)絡(luò)連接和客戶覆蓋為目標(biāo)，提出了一種粒子群優(yōu)化方法，該方法允許Mesh路由器在連續(xù)的區(qū)域高度靈活的放置在移動位置。文獻(xiàn)［9］提出一種啟發(fā)式部署算法ILSearch，通過添加節(jié)點(diǎn)先滿足網(wǎng)絡(luò)的覆蓋性，然后滿足網(wǎng)絡(luò)的連通性。文獻(xiàn)［10］提出了一種基于網(wǎng)絡(luò)流的MR部署貪心算法NFGreedy。該算法在滿足網(wǎng)絡(luò)連通和覆蓋的前提下以最小化節(jié)點(diǎn)數(shù)量為目標(biāo)，按照貪心策略，以迭代的方式進(jìn)行MR選擇，直到網(wǎng)絡(luò)能夠滿足所有用戶的帶寬需求。每次迭代首先計(jì)算可部署MRC的權(quán)重值；然后從其中選擇權(quán)重值（節(jié)點(diǎn)可覆蓋的流量）最大的節(jié)點(diǎn)，使其擴(kuò)展路徑中的所有節(jié)點(diǎn)成為MR。最后對可部署MR候選位置集合及其擴(kuò)展路徑進(jìn)行更新，除去一些不再符合部署條件的MR。

MR部署優(yōu)化是具有NP-hard難度的問題，其問題的求解復(fù)雜度隨著問題規(guī)模的增加而成幾何倍數(shù)增長，在一定的花費(fèi)內(nèi)很難求出問題的最優(yōu)解，因此，學(xué)者們嘗試引入各種方法進(jìn)行求解。如上所述，目前針對MR部署優(yōu)化問題的算法主要分為2類：（1）基于數(shù)學(xué)模型的優(yōu)化方法［5］，如數(shù)學(xué)規(guī)劃法；（2）基于智能算法的優(yōu)化方法［3-4，6，11］，如啟發(fā)式算法、遺傳算法和模擬退火算法等。使用常規(guī)算法進(jìn)行求解具有求解精度高、運(yùn)行結(jié)果好等優(yōu)點(diǎn)，但其計(jì)算復(fù)雜度高，對較大規(guī)模的問題無法求出可行解?；谥悄芩惴ǖ膬?yōu)化方法是目前研究的熱點(diǎn)，智能算法是一種全局搜索算法，具有很好的全局優(yōu)化能力，但其容易陷入局部最優(yōu)。文獻(xiàn)［10］提出的基于網(wǎng)絡(luò)流的MR部署貪心算法在保證網(wǎng)絡(luò)連通和需求覆蓋的前提下，考慮了MR接入帶寬等約束條件，部署結(jié)果比以往算法有很大提高，但該算法還有以下不足：（1）算法是在假定網(wǎng)關(guān)已部署的前提下研究如何部署MR，而網(wǎng)關(guān)位置與MR位置是相互影響、密切關(guān)聯(lián)；（2）該算法通過添加可覆蓋流量最大的節(jié)點(diǎn)擴(kuò)展骨干網(wǎng)絡(luò)以滿足需求覆蓋約束，在部署前期性能很好，但是在后期可能會產(chǎn)生大量的零碎流量，導(dǎo)致部署MR的數(shù)量增加。因此，本文在該算法的模型基礎(chǔ)上，使用粒子群算法對網(wǎng)關(guān)位置優(yōu)化，并使用啟發(fā)策略減少零碎流量的產(chǎn)生。

3 問題描述及模型

MR部署問題可以簡化為在二維平面上的MR部署問題，假設(shè)在開始階段已經(jīng)選擇了足夠多的可部署MR的位置，并已把連續(xù)的用戶需求離散化成需求點(diǎn)［7］。本文借鑒文獻(xiàn)［10］所建立的數(shù)學(xué)模型并加以改進(jìn)。

3.1 相關(guān)定義與符號說明

無線M esh網(wǎng)絡(luò)對應(yīng)著一個(gè)復(fù)雜的網(wǎng)絡(luò)拓?fù)鋱D，該拓?fù)鋱D可以用G（V，E）表示，V=｛v1，v2，…，vn｝表示網(wǎng)絡(luò)中的路由器節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)，其中網(wǎng)關(guān)數(shù)量為L；鄰接矩陣E=｛ei，j|i，j∈｛1，2，…，n｝｝表示節(jié)點(diǎn)之間的關(guān)系，假設(shè)每一個(gè)節(jié)點(diǎn)的通信半徑都相等且為Rt，則當(dāng)拓?fù)鋱D中的兩節(jié)點(diǎn)i與j之間的距離小于節(jié)點(diǎn)之間的通信半徑Rt時(shí)，即dist（vi，vj）≤Rt，eij= 1，否則eij=0。

在拓?fù)鋱D中路由節(jié)點(diǎn)通過一跳或者多跳的方式連接到網(wǎng)關(guān)，但是每增加一跳都會大大的降低通信時(shí)延。為了保證服務(wù)質(zhì)量，限制骨干節(jié)點(diǎn)到網(wǎng)關(guān)的最大跳數(shù)為H。

假設(shè)骨干節(jié)點(diǎn)采用多頻通信技術(shù)，即骨干節(jié)點(diǎn)之間的通信和對覆蓋范圍內(nèi)的終端所提供的服務(wù)采用不同的頻率互不干擾，骨干節(jié)點(diǎn)還具有以下屬性：

Rc：節(jié)點(diǎn)覆蓋范圍，是指以節(jié)點(diǎn)為中心的圓形區(qū)域，該節(jié)點(diǎn)可以對在這個(gè)范圍內(nèi)的終端提供服務(wù)。

Rt：節(jié)點(diǎn)通信半徑，是指以節(jié)點(diǎn)為中心的圓形區(qū)域，該節(jié)點(diǎn)可以與在這個(gè)范圍內(nèi)的其他節(jié)點(diǎn)進(jìn)行通信。

Cap：節(jié)點(diǎn)接入容量，是指節(jié)點(diǎn)能提供的最大接入帶寬。

根據(jù)上述定義，該問題可以描述為給定MRC集合C、UDN集合U和網(wǎng)關(guān)數(shù)量L，在滿足所有UDN帶寬需求、保證所有MR到網(wǎng)關(guān)的連通性和骨干節(jié)點(diǎn)實(shí)際接入流量小于最大接入流量的前提下，從MRC中選擇最少數(shù)量的節(jié)點(diǎn)作為MR，同時(shí)還要確定網(wǎng)關(guān)的位置。

為了更好地量化模型，下面給出一系列算法過程中需要的變量：

UDN帶寬需求B=｛b1，b2，…，bm｝，bj表示第j個(gè)帶寬需求點(diǎn)的帶寬需求值。其中，m表示需求點(diǎn)的數(shù)量。

網(wǎng)關(guān)Gw=｛g1，g2，…，gn｝，gi=1表示候選位置ci被選做網(wǎng)關(guān)，gi=0表示ci沒有被選做網(wǎng)關(guān)，n為MRC個(gè)數(shù)。

已部署MRC X=｛x1，x2，…，xn｝，表示已部署的MR集合，xi=1表示在MRC集合中的vi點(diǎn)放置MR；xi=0表示MRC集合中的vi點(diǎn)沒有放置MR，n為MRC個(gè)數(shù)。

節(jié)點(diǎn)剩余帶寬R=｛r1，r2，…，rn｝，表示已放置的節(jié)點(diǎn)可分配的帶寬集合，其初始值為Cap。

節(jié)點(diǎn)最小跳數(shù)H=｛h1，h2，…，hn｝，表示骨干節(jié)點(diǎn)到網(wǎng)關(guān)的最小跳數(shù)，n為MRC個(gè)數(shù)。

3.2 數(shù)學(xué)模型

按照3.1節(jié)說明，該問題的數(shù)學(xué)模型如下：優(yōu)化目標(biāo)：

優(yōu)化目標(biāo)函數(shù)式（1）計(jì)算布置WMN骨干網(wǎng)絡(luò)需要的MR的數(shù)量。約束條件式（2）和約束條件式（3）表明只有當(dāng)該節(jié)點(diǎn)能夠連接到網(wǎng)關(guān)和該節(jié)點(diǎn)覆蓋范圍內(nèi)存在UDN，該節(jié)點(diǎn)才會被選作MR。條件式（4）和條件式（5）表明某個(gè)UDN被MRC承擔(dān)，當(dāng)且只當(dāng)該MRC已被選擇部署MR且該UDN在該MRC覆蓋范圍內(nèi)。條件式（6）表明所有的用戶帶寬需求都必須被滿足。條件式（7）表明每個(gè)節(jié)點(diǎn)承擔(dān)的UDN之和不能超過其接入容量Cap。條件式（8）表明每個(gè)節(jié)點(diǎn)到達(dá)網(wǎng)關(guān)的最小跳數(shù)不能超過H。條件式（9）～條件式（11）表明節(jié)點(diǎn)i和j都被選作MR且兩者之間的距離小于通信距離是節(jié)點(diǎn)k通過該路徑連接到網(wǎng)關(guān)的前提。條件式（12）～條件式（15）給出了節(jié)點(diǎn)k存在多跳MR路徑到達(dá)網(wǎng)關(guān)所需要滿足的條件。

4 MR部署算法

MR部署算法的基本設(shè)計(jì)思想如下：在確定網(wǎng)關(guān)的位置之后，然后使用迭代的方式從可部署MRC集合中選擇節(jié)點(diǎn)的添加到骨干網(wǎng)絡(luò)集合并更新部署狀態(tài)直到每一個(gè)UDN的帶寬需求都被滿足。

4.1 節(jié)點(diǎn)選擇

上述部署算法最關(guān)鍵的問題是如何從可部署MRC中選擇節(jié)點(diǎn)部署MR，其具體過程如下：在每次迭代的過程中，從剩余MRC集合中（未部署MR的候選位置）篩選出現(xiàn)有骨干網(wǎng)絡(luò)的相鄰候選位置，按照可覆蓋流量最大、實(shí)際覆蓋半徑最小的優(yōu)先法則選擇節(jié)點(diǎn)添加到骨干網(wǎng)絡(luò)；若當(dāng)前網(wǎng)絡(luò)不存在相鄰候選位置，則按照上述優(yōu)先法則添加滿足符合條件的路徑到骨干網(wǎng)絡(luò)。該方法能有效避免產(chǎn)生零碎流量，減少部署節(jié)點(diǎn)的個(gè)數(shù)。如圖1所示，節(jié)點(diǎn)vi和vj是已經(jīng)部署的MR，編號為1～9的候選節(jié)點(diǎn)是當(dāng)前部署狀態(tài)下的相鄰候選位置，圓表示節(jié)點(diǎn)的實(shí)際覆蓋半徑，假設(shè)MR的接入容量為54 M b/s，每個(gè)用戶需求點(diǎn)的需求值為25 M b/s，顯然編號為1，4，6，8的節(jié)點(diǎn)其最大覆蓋流量為節(jié)點(diǎn)接入流量，而其他節(jié)點(diǎn)的最大覆蓋流量小于節(jié)點(diǎn)接入流量，在確定下一個(gè)放置位置時(shí)，優(yōu)先選擇可覆蓋流量最大的節(jié)點(diǎn)，若有幾個(gè)節(jié)點(diǎn)的最大覆蓋流量相等且都為最大值，則從這些節(jié)點(diǎn)中選擇實(shí)際覆蓋半徑最小節(jié)點(diǎn)。因此，從1，4，6，8節(jié)點(diǎn)中選擇節(jié)點(diǎn)1添加到網(wǎng)絡(luò)。

圖1 節(jié)點(diǎn)選擇示意圖

定義3 實(shí)際覆蓋半徑是指節(jié)點(diǎn)與其最遠(yuǎn)能夠提供接入服務(wù)的UDN之間的距離，若節(jié)點(diǎn)vi的節(jié)點(diǎn)覆蓋范圍Rc內(nèi)的UDN帶寬需求總和小于等于節(jié)點(diǎn)剩余帶寬ri時(shí)，實(shí)際覆蓋半徑為Rc；若節(jié)點(diǎn)vi的節(jié)點(diǎn)覆蓋半徑Rc內(nèi)的UDN帶寬需求總和大于節(jié)點(diǎn)剩余帶寬ri時(shí)，實(shí)際覆蓋半徑為dist（vi，uk），其中uk滿足把節(jié)點(diǎn)可覆蓋需求表中節(jié)點(diǎn)vi所在行按從小到大排序，cur-b為節(jié)點(diǎn)uk前面所有節(jié)點(diǎn)的流量和，cur-b≤ri且cur-b+bk＞ri。

定義4 相鄰候選位置是指距離骨干網(wǎng)絡(luò)跳數(shù)為1且與骨干網(wǎng)絡(luò)中間不存在未覆蓋用戶需求點(diǎn)的可部署候選位置。相鄰候選位置存在2種情況，如圖2所示。已部署節(jié)點(diǎn)vi是在骨干網(wǎng)絡(luò)中與可部署節(jié)點(diǎn)vj距離最近的節(jié)點(diǎn)，Ri和Rj是節(jié)點(diǎn)vi和vj的實(shí)際覆蓋半徑，若2個(gè)節(jié)點(diǎn)實(shí)際覆蓋半徑有疊加，即dist（vi，vj）≤Ri+Rj，則vj稱為相鄰候選節(jié)點(diǎn)，如圖2（a）所示；若2個(gè)節(jié)點(diǎn)實(shí)際覆蓋范圍沒有疊加但是其連接線vivj的鄰域Ω內(nèi)不存在未覆蓋UDN，則vj稱為相鄰候選節(jié)點(diǎn)，本文取鄰域?qū)挾圈?m in（Ri，Rj）/2，如圖2（b）所示。

圖2 相鄰候選位置示意圖

4.2 算法步驟

為提高算法運(yùn)行效率，本文采用十字鏈表存儲數(shù)據(jù)，算法步驟如下：

（1）初始化已部署MR、已覆蓋UDN和其他放置變量，根據(jù)UDN和MRC的坐標(biāo)計(jì)算需求覆蓋表，更新網(wǎng)關(guān)集合。

（2）更新已部署MR、已覆蓋UDN和需求關(guān)聯(lián)表，計(jì)算當(dāng)前網(wǎng)絡(luò)可滿足的最大帶寬需求，判斷當(dāng)前網(wǎng)絡(luò)可滿足流量是否等于總流量，如等于則轉(zhuǎn)步驟（5）。

（3）計(jì)算節(jié)點(diǎn)剩余帶寬、已部署MR到網(wǎng)關(guān)的最小跳數(shù)并更新骨干層節(jié)點(diǎn)最短路徑，更新節(jié)點(diǎn)可覆蓋需求表，根據(jù)4.1節(jié)所述方法更新可用MRC集合。

（4）從相鄰MRC集合中選擇一個(gè)權(quán)重最大的節(jié)點(diǎn)添加到已部署路由節(jié)點(diǎn)集中，若不存在可用的相鄰MRC，擇選擇權(quán)重最大的路徑，轉(zhuǎn)步驟（2）。

（5）評估部署結(jié)果，算法結(jié)束。

4.3 算法分析

在算法初始化階段，需要構(gòu)建覆蓋關(guān)系矩陣，時(shí)間復(fù)雜度為O（nm）；需要構(gòu)建候選節(jié)點(diǎn)之間連接關(guān)系的無向圖，時(shí)間復(fù)雜度為O（n2）；需計(jì)算UDN到MRC的距離，時(shí)間復(fù)雜度為O（nm）；還需要初始化MRC的擴(kuò)展路徑，時(shí)間復(fù)雜度為O（n2）。在放置節(jié)點(diǎn)階段，每次放置分為2個(gè)階段：（1）選擇節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O（n2）；（2）更新流量及覆蓋信息，時(shí)間復(fù)雜度為O（nm）。由于每一次放置都會去掉一個(gè)節(jié)點(diǎn)，因此放置最多執(zhí)行n次。綜上，算法的時(shí)間復(fù)雜度為O（2nm+2n2+n（n2+nm）），即O（n2m）。

5 基于離散粒子群的網(wǎng)關(guān)優(yōu)化部署算法

上一節(jié)所述的MR部署算法是在預(yù)先確定網(wǎng)關(guān)的前提下進(jìn)行部署的，但是網(wǎng)關(guān)位置與MR位置是相互影響、密切關(guān)聯(lián)的。

5.1 粒子群算法

粒子群算法是文獻(xiàn)［12］提出的一種進(jìn)化優(yōu)化算法，其思想是對鳥群和魚群的模擬。粒子群算法一個(gè)并行算法，能夠模擬粒子群體在解空間搜索極值的各種飛行狀態(tài)。由于基本粒子群優(yōu)化算法主要針對連續(xù)函數(shù)進(jìn)行搜索計(jì)算，但許多實(shí)際工程問題都描述為離散的組合優(yōu)化問題，為此Kennedy和Eberhart于1997年提出了一種離散二進(jìn)制粒子群優(yōu)化算法（Binary Particle Swarm Optim ization，BPSO）。BPSO算法具有很強(qiáng)全局搜索能力且由于其搜索空間的二進(jìn)制特性該算法適合求解只包含2種狀態(tài)的問題。BPSO的粒子搜索空間是D維的二進(jìn)制空間，記為BD，PopSize個(gè)粒子在D維的目標(biāo)空間進(jìn)行搜索，為了將粒子群優(yōu)化算法用于離散變量優(yōu)化，將該算法中每個(gè)粒子的位置矢量屬于二進(jìn)制空間（由0和1組成的二進(jìn)制字符串），記為Z=［z1，z2，…，zD］，其中，zi為0或1，但是其速度矢量仍然屬于實(shí)數(shù)空間RD，即有v∈［-vmax，vmax］。這樣，算法可以保留基本粒子群算法中的速度公式，而只對其位置更新公式進(jìn)行修改得到，每個(gè)粒子的速度和位置更新公式為：

其中，i=1，2，…，PopSize；d=1，2，…，D；k是迭代次數(shù)；ρ，r1，r2是［0，1］之間的隨機(jī)數(shù)；w為慣性因子；c1，c2為學(xué)習(xí)因子。由式（17）可知，vk+1i越靠近vmax，候選位置ci被選作網(wǎng)關(guān)的可能性越大。

5.2 網(wǎng)關(guān)優(yōu)化部署算法

一個(gè)由PopSize個(gè)粒子組成的粒子群，在D維二進(jìn)制空間搜索極值，第i個(gè)例子表示為，其中，zj為0或1，在網(wǎng)關(guān)部署問題中，zj=1表示第j個(gè)候選位置被選作網(wǎng)關(guān)，粒子根據(jù)歷史最優(yōu)解和全局最優(yōu)解不斷修正搜索位置，從而獲得最優(yōu)解。

按照式（16）和式（17）更新計(jì)算速度和位置，產(chǎn)生的結(jié)果可能會不滿足網(wǎng)關(guān)數(shù)量的約束，為此做一點(diǎn)改進(jìn)，更新位置的時(shí)候按照位置穩(wěn)定性進(jìn)行排序，從最不穩(wěn)定的候選位置i開始更新，若位置狀態(tài)改變，則從序列中刪除該候選位置；否則跳過該候選位置；然后重復(fù)上面的操作，直到網(wǎng)關(guān)數(shù)量滿足條件要求為止，本文取vmax=4，w=0.25，c1=0.4，c2= 0.6。粒子適度值根據(jù)式（19）計(jì)算：

算法步驟如下：

（1）隨機(jī)產(chǎn)生規(guī)模為PopSize的粒子群，初始化離散粒子的位置和速度。

（2）根據(jù)第4節(jié)所述的MR部署算法放置MR，根據(jù)式（19）計(jì)算粒子群適度值。

（3）若有更好的適度值，更新歷史最佳位置和全局最佳位置。

（4）根據(jù)式（16）更新粒子的速度和位置。

（5）判斷是否達(dá)到最大迭代次數(shù)或輸出結(jié)果滿足要求，否則轉(zhuǎn)步驟（2）。

（6）輸出粒子群最優(yōu)結(jié)果（網(wǎng)關(guān)和MR位置及數(shù)量）。

6 實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)在Visual Studio 2012開發(fā)環(huán)境中采用VC++編碼，其硬件環(huán)境是Intel酷睿i3 3220 3.3 GHz，4 GB DDR3，操作系統(tǒng)為W indows 7 Ultimate。

本文依據(jù)麻省理工學(xué)院（M IT）搭建的Roofnet實(shí)驗(yàn)網(wǎng)絡(luò)平臺設(shè)置實(shí)驗(yàn)參數(shù)，取節(jié)點(diǎn)覆蓋范圍Rc為150 m，節(jié)點(diǎn)通信半徑Rt為250 m，節(jié)點(diǎn)接入容量Cap為54 M b/s，骨干節(jié)點(diǎn)到網(wǎng)關(guān)的最大跳數(shù)H為4跳。在實(shí)際場景中人口群落的分布并非均勻分布而更接近正態(tài)分布，本文模擬現(xiàn)實(shí)人口分布產(chǎn)生符合正態(tài)分布的用戶需求點(diǎn)集，然后在該正態(tài)分布的包羅圓內(nèi)隨機(jī)產(chǎn)生MR候選位置。

在不同的部署場景下測試本文算法與現(xiàn)有部署算法ILSearch［9］和NF-Greedy［10］的優(yōu)化效果，部署場景包括場景大小、MRC數(shù)量、網(wǎng)關(guān)數(shù)量和UDN數(shù)量4個(gè)因素，實(shí)驗(yàn)設(shè)定UDN的帶寬需求值為10 M b/s，其部署場景為（200 m×200 m，10，1，15），（300 m× 300 m，20，1，25），（400 m×400 m，40，2，45），（600 m× 600 m，80，3，80），（800 m×800 m，150，4，110），（1 000 m×1 000 m，200，8，140），（1 500 m×1 500，300，12，120）、（2 000 m×2 000 m，450，16，360）。表1給出了3種算法在不同部署場景下部署MR個(gè)數(shù)的平均值，從中可以看出，當(dāng)部署規(guī)模較小的時(shí)本文算法能找到最佳部署方案，當(dāng)規(guī)模較大時(shí)部署MR的數(shù)量遠(yuǎn)小于ILSearch算法，比NF-Greedy算法部署的MR數(shù)量少8%左右。

表1 3種算法在正態(tài)分布場景下的部署結(jié)果

表2給出了3種算法在均勻分布場景下部署MR的個(gè)數(shù)。

表2 3種算法在均勻分布場景下的部署結(jié)果

通過上述實(shí)驗(yàn)結(jié)果可以得知，本文算法不論是在均勻分布或者正態(tài)分布情況下，部署的MR個(gè)數(shù)均少于ILSearch算法和NF-Greedy算法，證明了本文算法的有效性。

7 結(jié)束語

為解決無線M esh網(wǎng)絡(luò)中決定網(wǎng)絡(luò)性能的骨干網(wǎng)絡(luò)部署優(yōu)化問題，本文提出一種網(wǎng)關(guān)與M esh路由器同時(shí)部署的優(yōu)化算法，使用二進(jìn)制離散粒子群算法優(yōu)化網(wǎng)關(guān)位置，在滿足用戶帶寬需求和網(wǎng)絡(luò)連通性的前提下，利用啟發(fā)策略迭代擴(kuò)展骨干網(wǎng)絡(luò)，直到所有帶寬需求都被滿足，根據(jù)部署MR的數(shù)量評估網(wǎng)關(guān)布置結(jié)果。實(shí)驗(yàn)結(jié)果表明，該算法部署MR的數(shù)量少于NF-Greedy和ILSearch算法。

無線Mesh網(wǎng)絡(luò)是一種新興的無線網(wǎng)絡(luò)結(jié)構(gòu)，具有很好的發(fā)展前途，但是關(guān)于無線Mesh網(wǎng)絡(luò)優(yōu)化問題的研究才剛剛起步。本文使用啟發(fā)算法結(jié)合粒子群算法部署MR，啟發(fā)算法不具備全局搜索能力，其部署結(jié)果可能是局部最優(yōu)，使用的粒子群算法也有改進(jìn)的空間。此外，本文算法沒有考慮到無線網(wǎng)絡(luò)的可靠性以及節(jié)點(diǎn)之間的干擾。因此，下一步工作計(jì)劃使用智能算法優(yōu)化MR部署問題。

［1］ Rezgui J，Hafid A，Gendreau M.Distributed Admission Control in Wireless Mesh Networks：Models，Algorithm s，and Evaluation［J］.IEEE Transactions on Vehicular Technology，2010，59（3）：1459-1473.

［2］ Benyam ina D，Hafid A，Gendreau M.Wireless Mesh Networks Design——A Survey［J］.IEEE Communications Surveys&Tutorials，2012，14（2）：299-310.

［3］ 黃書強(qiáng)，王高才，單志廣，等.智慧城市中無線網(wǎng)絡(luò)節(jié)點(diǎn)部署優(yōu)化方案研究［J］.計(jì)算機(jī)研究與發(fā)展，2014，51（2）：278-289.

［4］ Xhafa F，Sanchez C，Barolli L.Ad Hoc and Neighborhood Search Methods for Placement of Mesh Routers in Wireless Mesh Networks［C］//Proceedings of the 29th IEEE International Conference on Distributed Computing System s Workshops.Montreal，Canada：IEEE Press，2009：400-405.

［5］ Xhafa F，Sánchez C，Barolli L.Local Search Methods for Efficient Router Nodes Placement in Wireless Mesh Networks［J］.Journal of Intelligent Manufacturing，2012，23（4）：1293-1303.

［6］ Wang Junfang，Xie Bin，Cai Kan，et al.Efficient Mesh Router Placement in Wireless Mesh Networks［C］// Proceedings of IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems.Pisa，Italy：IEEE Press，2007：1-9.

［7］ Sakam oto S，Kulla E，Oda T，et al.A Comparison Study of Simulated Annealing and Genetic Algorithm for Node Placement Problem in Wireless Mesh Networks［J］. Journal of Mobile Multimedia，2013，9（1/2）：101-110.

［8］ Lin Chuncheng.Dynam ic Router Node Placement in Wireless Mesh Networks：A PSO Approach with Constriction Coefficient and Its Convergence Analysis［J］. Information Sciences，2013，232：294-308.

［9］ Wang Junfang，Cai Kan，Agrawal D R.A Multi-rate Based Router Placement Scheme for Wireless Mesh Networks［C］//Proceedings of the 6th IEEE International Conference on Mobile Adhoc and Sensor System s. Washington D.C.，USA：IEEE Press，2009：100-109.

［10］ 吳文甲，楊 明，羅 軍.無線M esh網(wǎng)絡(luò)中滿足帶寬需求的路由器部署方法［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37（2）：344-355.

［11］ Xhafa F，Sánchez C，Barolli L.Genetic Algorithm s for Efficient Placement of Router Nodes in Wireless Mesh Networks［C］//Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications.Perth，Australia：IEEE Press，2010：465-472.

［12］ Kennedy J，Eberhart R.Particle Swarm Optimization［C］// Proceedings of IEEE International Conference on Neural Networks.Perth，Australia：IEEE Press，1995：1942-1948.

編輯 金胡考

Research on Backbone Nodes Deployment Algorithm in Wireless Mesh Network

LING Quan，LI Meiyi
（College of Information Engineering，Xiangtan University，Xiangtan 411105，China）

Wireless Mesh Network（WMN）is a key technology of new generation Wireless networks，and the structure of the backbone network is a decisive factor in achieving the connectivity and coverage of the network.Aiming at optimizing the deployment of WMN's backbone network，an effective Mesh Router（MR）deployment algorithm for minimizing the number of MR under the premise of network connection and meeting the user's demand of the bandwidth is proposed.Particle swarm algorithm is used to determine the location of the gateway.Then it adds nodes to the backbone network constantly until covers all requirements.Experimental results prove that the number of MR deployed of the proposed algorithm is less than NF-Greedy algorithm and ILSearch algorithm under uniform distribution and normal distribution，it can reduce the deployment cost effectively.

Wireless Mesh Network（WMN）；Mesh Router（MR）deployment；backbone node；greedy algorithm；heuristic algorithm；particle swarm

凌 權(quán)，李枚毅.無線Mesh網(wǎng)絡(luò)中骨干節(jié)點(diǎn)部署算法研究［J］.計(jì)算機(jī)工程，2015，41（11）：147-152.

英文引用格式：Ling Quan，Li Meiyi.Research on Backbone Nodes Deployment Algorithm in Wireless Mesh Network［J］. Computer Engineering，2015，41（11）：147-152.

1000-3428（2015）11-0147-06

A

TP393

10.3969/j.issn.1000-3428.2015.11.026

凌 權(quán)（1990-），男，碩士，主研方向：移動互聯(lián)網(wǎng)，智能計(jì)算；李枚毅，教授、博士。

2014-09-17

2014-12-12 E-m ail：lingquan-1990@126.com