動態環境下無線Mesh網絡骨干節點部署算法

曹圣靈,李枚毅,胡 燦

(湘潭大學 信息工程學院,湖南 湘潭 411105)

0 概述

無線Mesh網絡(Wireless Mesh Network,WMN)[1]是一種多跳無線網絡,是與傳統無線網絡不同的一種無線網絡。相比傳統無線網絡,它具有部署簡單、穩定系強、帶寬高、可擴展性強、應用廣泛、發展前景好等優點。在無線網絡日益發達的時代,無線Mesh網絡已經獲得了國內外大量研究者的關注。Mesh路由器(Mesh Router,MR)、Mesh網關(Mesh Gateway,GW)和Mesh終端(Mesh Client,MC)是組成無線Mesh網絡的基礎框架。MR在網絡中具備接入和轉發功能,為其覆蓋范圍內的MC提供網絡服務,在多跳網絡中為其他MR轉發數據到MG。MG是特殊MR,不僅具有MR在網絡中的功能,還以有線形式與因特網(Internet)連接,承擔與Internet的連接任務。MC是通過MR訪問網絡的終端設備,如筆記本電腦、手機等。

文獻[2]提出貪心算法NF-Greedy,該算法迭代從可部署MR集合中獲取權重最大的節點添加至部署節點集合,建立部署在MR數量最小化的目標上,利用網絡流方法進行求解。文獻[3]將WMN網絡MG布置問題抽象為幾何上的K-中心問題,以最小化MR和MG之間路徑長度為目標,提出自適應的粒子群優化算法來求解網關節點部署問題。文獻[4]針對WMN骨干網絡部署優化問題,以滿足用戶帶寬需求和網絡連接為前提,以最小化MR數量為目標,提出在MG與MR互相影響情況下的解決方法。

目前在靜態環境下WMN骨干網絡節點部署問題尋找最優方案已經比較成熟[5-10],但WMN往往處于動態環境下,MR與MC具有可變性,所以動態環境下的研究更加有意義。當前已經有部分國內外的學者針對動態環境下的部署問題提出了研究。文獻[11]提出一種粒子群優化算法,該算法在動態環境下,以最大化滿足網絡連接和覆蓋需求為前提,實現MR的部署方案。但是該文獻假定MR的部署位置是可以任意移動的,這在現實生活中實現成本太高。本文研究MG與MR組成的WMN骨干網絡,提出一種動態環境下WMN骨干網絡節點的優化部署算法。

1 問題描述

現實生活中WMN是動態變化的,在不同的時間段MC會處于不同的需求狀態和地理位置。用戶發生需求變化后在接下來的一段時間是維持穩定,因此,本文假定檢測到需求變化后,調整骨干節點的部署位置適應需求變化,度過周期后再檢測新環境。在一個恰當的部署候選位置,且已將用戶的需求離散化為需求點的二維平面場景中,骨干節點部署問題將被看作是二維平面節點部署問題。

1.1 定義及變量說明

在研究該問題時,本文假定無線網絡通信可靠,且節點之間通信互不干擾,設定如下變量:

Rc(節點覆蓋半徑),指以MR為中心向MC提供服務區域的半徑。

Rt(節點通信半徑),指以MR為中心能夠與其他MR通信區域的半徑。

Cap(最大接入容量),指MR提供給MC帶寬的最大值。

H(最大跳數),指確保通信質量的前提下,MR至MG通信路徑允許跳數的最大值。

T(周期值),指根據現實情況,假定網絡中用戶需求趨于穩定的時間段值。

在二維平面內,WMN對應著一個拓撲圖G=(V,E),集合V={v1,v2,…,vn}表示網絡中節點集合;鄰接矩陣E={ei,j|i,j∈{1,2,…,n}}表示節點之間的關系,當節點vi和vj之間的通信距離未超過節點的通信半徑,即dist(vi,vj)≤Rt時ei,j=1,否則ei,j=0。根據上文所提出的假設,為方便本文的說明,作出如下定義:

定義1(MR候選位置(MR Candidate,MRC)) 指事先在場景中選取能夠布置MR的位置,用集合C={c1,c2,…,cn}表示,其中MG數量為L。

定義2(用戶需求點(User Demand Node,UDN)) 指場景內用戶的帶寬需求分布被離散化后形成的點,用集合U={u1,u2,…,um}表示。

定義3(實際覆蓋半徑) 指骨干節點為其覆蓋的UDN實際上能夠提供服務的最大距離。

定義4(相鄰候選位置) 指可供部署的MRC,該MRC與骨干網絡之間沒有未提供服務的UDN且與骨干網絡的距離為1。

定義5(環境改變次數) 指當前運行的時間度過了幾個周期值T,即環境改變的次數t。

為更好地量化模型,補充如下變量:

集合B={b1,t,b2,t,…,bm,t}表示當前UDN集合中點的帶寬需求值,bj,t表示UDN集合中uj在當前環境的帶寬需求值。

集合Dct={di,j|i∈{1,2,…,n}∧j∈{1,2,…,m}}表示MRC對流量需求的覆蓋關系,當dist(ci,uj)>Rc時di,j=0,表示用戶需求點uj不在ci覆蓋范圍內;當dist(ci,uj)≤Rc時di,j=1,表示用戶需求點在覆蓋范圍內。

集合G={g1,t,g2,t,…,gn,t}表示在當前環境下MRC是否被選為部署網關,gi,t=0表示ci在當前環境未被選作網關,gi,t=1表示ci被選作網關。

集合X={x1,t,x2,t,…,xn,t}表示當前環境下MRC集合中位置是否部署了骨干節點,xi,t=0表示ci位置未部署節點,xi,t=1表示ci位置部署了節點。

集合Y={yi,j|i∈{1,2,…,n}∧j∈{1,2,…,m}}表示骨干節點vi所承擔用戶需求點uj的帶寬需求情況。

集合R={r1,t,r2,t,…,rn,t}表示當前運行次數骨干節點剩余可分配的帶寬值,值初始化為Cap。

集合H={h1,t,h2,t,…,hn,t}表示當前骨干節點到MG的最小跳數。

1.2 數學模型

基于上文對定義和變量的說明,本文給出問題的形式化描述,優化目標如下:

(1)

每次環境變化后,需要滿足用戶帶寬需求,保證網絡連通性,在此前提下將MR部署數量最小化。

約束條件:

(2)

(3)

di,j=1,?yi,j≠0,?i∈{1,2,…,n},?j∈{1,2,…,m}

(4)

xi,t=1,?yi,j≠0,?i∈{1,2,…,n},?j∈{1,2,…,m}

(5)

(6)

ri,t≥0,?i∈{1,2,…,n}

(7)

hi,t≤H,?i∈{1,2,…,n}∧xi,t=1

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

式(2)表明被選擇MRC必須能夠通過多跳網絡連接到網關。式(3)表明被選擇的MRC覆蓋區域中必須存在可以通信的UDN。式(4)、式(5)表明當且僅當UDN在MRC覆蓋范圍內且MRC已經部署MR時,MRC為UDN提供網絡服務。式(6)表明必須滿足全網絡中所有用戶需求。式(7)表明骨干節點的最大接入容量不能小于其提供的帶寬之和。式(8)表明最大跳數不能小于骨干節點通過多跳網絡連接到MG的最小跳數。式(9)～式(11)表明僅當2個MRC都被選擇部署MR,且兩者能互相通信,該路徑才能連接到MG。式(12)～式(15)表明節點必須滿足當前條件才能存在多跳路徑連接到MG。

2 WMN骨干節點部署問題算法

2.1 骨干節點部署算法

骨干節點的部署思路是,首先確定MG位置,然后迭代從未部署MRC集合中,優先選擇可覆蓋流量最大、實際覆蓋半徑最小的節點,添加至骨干節點集合,直至網絡中用戶需求得到滿足。對于有向圖而言鄰接表有所缺陷,基于存取數據模型的高效性,本文采用十字鏈表存儲數據,同時提升代碼的可讀性,算法步驟如下:

1)初始化場景布置變量,憑借用戶需求點和MR候選位置構建需求覆蓋表。

2)更新已部署MR集合、已覆蓋UDN集合和需求關聯表,得到當前網最多可以提供的帶寬,計算目前網絡中的流量,判斷它是否達到預期總流量,如等于則轉步驟5)。

3)更新所有節點的剩余帶寬、已部署節點的最小跳數、骨干層節點的最短路徑與節點可覆蓋需求表,依照上文方法添加節點至骨干網絡,更新剩余MRC集合。

4)從相鄰候選位置中選取權重最大的位置,添加至已部署MR集合,若不存在則選取權重最大的路徑,轉步驟2)。

5)記錄結果,算法結束。

上述的MR部署方法需要先確定MG位置,但是MG與MR位置的選擇是彼此制約的。本文采用BPSO算法來部署MG,該算法初始化一個由PopSize個粒子組成的粒子群,在D維二進制空間中搜索極值,粒子群依靠歷史最優解和全局最優解不斷改正探尋位置,以此得到最優解。其中,粒子群速度和位置的更新公式為:

(16)

(17)

(18)

(19)

算法步驟如下:

1)生成規模為PopSize的粒子群,初始化粒子。

2)依照上文的算法布置MR,憑借式(19)得到粒子群適應度值,更新歷史最佳位置和全局最佳位置。

3)根據式(16)更新粒子的速度和位置。

4)檢測算法是否運行到最大迭代次數,或檢測結果是否滿足預期,如不滿足則轉步驟2)。

5)記錄輸出值(骨干節點數量及相應坐標)。

2.2 動態環境下的TSDPSO算法

為在動態環境中求解該算法,本文借鑒文獻[12]提出的對稱位移映射的雙子種群PSO算法,檢測當前部署方案是否能夠滿足網絡連通性及用戶需求。在D維度空間中,pbest是粒子當前最優解,gbest是種群中粒子所經歷過的最優解,xi是粒子自身的位置向量,vi是粒子自身的速度向量。在算法開始時,種群等分為主、輔2個子群,主子群選擇標準PSO算法的速度、位置進化方程式(20)、式(21)對粒子更新[13-14]。輔子群選擇差異進化,依照方程式(21)、式(22)對粒子更新[15]。

(20)

(21)

(22)

(23)

在D種群的進化過程中,輔子群粒子采用差異進化策略,以50%的幾率與全局最優粒子實施吸引或排斥,主子群粒子則始終被全局最優粒子所吸引。環境發生變化后,對現有的部署方案進行評估,判斷部署方案能否滿足網絡連通性,計算MR是否能夠滿足用戶帶寬需求量,如不能滿足目標,在原始種群基礎上,對稱性調整主子群粒子的空間位置分布,重新設置部署方案。空間對稱位移映射步驟如下:

1)在所有維度上計算主群粒子的位置與局部最優gbest位置的差。

2)統計每一維度上位置差值的正負值數量,正值數量記為n1d(d=1,2,…,D),負值數量記為n2d(d=1,2,…,D)。

4)將粒子數量較少的一側,按照較多一側的位置使用式(24)變換,更新粒子位置。

(24)

算法步驟如下:

1)隨機初始化粒子群,將粒子群分為主、輔2個子群,初始化粒子的速度與位置。

2)根據2.1節所述方法部署骨干節點,對比主、輔子群的適應度值,評估種群的當前最優解及全局最優解。

3)分別更新主、輔子群的速度與位置。

4)度過周期T后檢測環境是否發生變化,評估當前部署方案能否滿足網絡連通性及用戶需求量,若不滿足,則主子群采取空間對稱位移映射,轉步驟2)。

5)算法是否達到運行次數,不滿足則轉步驟2)。

6)算法結束,記錄輸出值。

3 仿真實驗與結果分析

本文實驗的開發與仿真環境為Visual Studio 2013,使用VC++編寫,參照著名的WMN實驗床Roofnet實驗網絡平臺來設置參數,該實驗平臺由麻省理工大學搭建,取節點覆蓋半徑為150,節點通信半徑為250,節點接入容量為54,UDN的帶寬需求值為10,最大跳數為4。實驗硬件環境為Intel Core i3 M370 2.4 GHz,2.0 GB內存,操作系統為Windows 7 Ultimate。模擬現實情況生成UDN集合及MRC集合,設置周期時間為15 min,每次環境變化中UDN的變化量是一個[0,udn_count/8]之間的隨機整數,每個UDN的坐標可以在場景內隨機移動。按照場景規模、MRC數量、MG數量、UDN數量的順序,依次生成場景1～7為(200×200,10,1,15),(300×300,20,1,25),(400×400,40,2,45),(600×600,80,3,80),(800×800,150,4,110),(1 000×1 000,200,8,140),(2 000×2 000,450,16,360)。正態分布場景下的靜態與動態部署結果見表1,平均分布場景下的靜態與動態部署結果見表2。

表1 正態分布場景下的靜態與動態部署結果

表2 平均分布場景下的靜態與動態部署結果

通過上述實驗結果可知,本文算法在均勻分布和正態分布情況下以及在動態環境的變化中,MR部署方案中的MR部署數量均能接近靜態部署結果,證明了本文算法的有效性。

4 結束語

本文提出一種動態環境下無線Mesh網絡骨干節點部署的優化算法,以滿足用戶帶寬需求和網絡連通性為前提,使用粒子群算法篩選網關位置,并以最小化路由器數量為目標逐步添加權重最大的相鄰節點完成部署。本文研究運用對稱位移映射的TSDPSO算法適應動態環境,從新周期開始,檢測環境變化,調整節點部署位置以適應需求變化。實驗結果表明,該算法能在動態環境中得到有效的部署方案。但本文算法沒有考慮節點之間的干擾以及無線網絡的可靠性,下一步將對此進行改進。

[1] BENYAMINA D,HAFID A,GENDREAU M.Wireless mesh networks design——a survey[J].IEEE Communica-tions Survey & Tutorials,2012,14(2):299-310.

[2] 吳文甲,楊 明,羅 軍.無線Mesh網絡中滿足帶寬需求的路由器部署方法[J].計算機學報,2014,37(2):344-355.

[3] 黃書強,王高才,單志廣,等.智慧城市中無線網絡節點部署優化方案研究[J].計算機研究與發展,2014,51(2):278-289.

[4] 凌 權,李枚毅.無線Mesh網絡中骨干節點部署算法研究[J].計算機工程,2015,41(11):147-152.

[5] XHAFA F,SANCHES C,BAROLLI L.Genetic algorithms for efficient placement of router nodes in wireless mesh network[C]//Proceedings of the 24th EEE International Conference on Advanced Information Net-working and Applications.Perth,Australia:IEEE Press,2010:465-472.

[6] XHAFA F,SANCHES 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.

[7] YANG Shengxiang.A Clustering Particle Swarm optimizer for locating and tracking multiple optima in dynamic environment[J].IEEE Transactions on Evolutionary Computation,2010,14(6):959-974.

[8] REZGUI J,HAFID A,GENDREAU M.Distributed admission control in wireless mesh networks:models,algorithms,and evaluation[J].IEEE Transactions on Vehicular Technology,2010,59(3):1459-1473.

[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 Inter-national Conference on Mobile Ad Hoc and Sensor Systems.Washington D.C.,USA:IEEE Press,2009:100-109.

[10] SAKAMOTO 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.

[11] LIN Chuncheng.Dynamic router node placement in wireless mesh networks:a PSO approach with constriction coefficient and its convergence analysis[J].Information Sciences,2013,232:294-308.

[12] 劉子坤,李枚毅,張 曉.動態環境下運用對稱位移映射的PSO算法[J].計算機工程,2014,40(11):200-204.

[13] EBERHART R C,SHI Yuhui.Tracking and optimizing dynamic systems with particle swarms[C]//Proceedings of Congress on Evolutionary Computation.New York,USA:IEEE Press,2001:94-97.

[14] KENNEDY J,EBERHART R C.Particle swarm optimiza-tion[C]//Proceedings of IEEE International Conference on Neural Networks.Washington D.C.,USA:IEEE Press,1995:1942-1948.

[15] HERNANDEZ P N,CORONA C C,PELTA D A.Efficient multi-swarm PSO algorithms for dynamic environments[J].Memetic Computing,2011(3):163-174.