混合式無線Mesh網(wǎng)絡路由與信道分配聯(lián)合優(yōu)化

張維維，何家峰,高國旺,任麗莉，申鉉京

(1.吉林大學 計算機科學與技術學院, 長春 130012;2. 長春師范大學 國際交流學院,長春 130032；3.31693部隊, 哈爾濱150062;4.西安石油大學 電子工程學院，西安 710065;5.長春師范大學 網(wǎng)絡中心,長春 130032)

0 引 言

無線Mesh網(wǎng)絡(WMNs)具有容量大、速率高、成本低和擴展性強等優(yōu)點，近年來受到了業(yè)界和學術界的廣泛關注。無線Mesh網(wǎng)絡依靠無線節(jié)點之間的相互協(xié)作，以多跳的方式為終端用戶提供服務。無線Mesh網(wǎng)絡的出現(xiàn)為商業(yè)化的“最后一公里”無線寬帶接入奠定了堅實的基礎。然而，由于無線頻譜受限、同信道干擾等因素，制約了無線Mesh網(wǎng)絡的普及和應用。

Qos感知路由(Qos-aware routing)協(xié)議[1]通過在物理拓撲上構造的多層邏輯拓撲映射，實行兩套路由機制：第一種路由是物理路由機制，這種機制負責路由表的創(chuàng)立和可用帶寬估算任務；另一種機制是邏輯路由控制機制，這種機制在物理路由的基礎上，為實時多媒體業(yè)務分配帶寬最大、跳數(shù)最短的邏輯路徑。

為了提高無線Mesh網(wǎng)絡的吞吐量性能并緩解網(wǎng)絡擁塞程度，Wang等[2]提出了一種基于網(wǎng)絡編碼的干擾感知路由協(xié)議(Coding-and-interference aware routing，CIAR),綜合考慮了拓撲信息、流量模式、無線干擾和編碼增益等因素，該協(xié)議基于實用網(wǎng)絡編碼技術和物理干擾模型，不但能夠在路徑建立過程中主動地探測潛在的編碼機會，而且能夠在路徑選擇階段辨別出編碼增益大、干擾代價小的路由線路，在獲得較大的編碼增益與緩解干擾程度之間取得良好的折中。與傳統(tǒng)的編碼感知路由方案相比，CIAR協(xié)議在付出較小控制報文開銷的代價下，可以有效提高網(wǎng)絡吞吐量性能，同時降低端到端延遲及節(jié)點的緩存溢出概率。Chen[3]提出了基于網(wǎng)絡編碼的差錯容忍路由(Net coding fault-tolerant routing, NCFR)機制,該機制考慮到無線Mesh網(wǎng)絡在某些節(jié)點處功能受限，信道、鏈路易受損傷等缺點，允許中繼節(jié)點進行有限次編碼操作，從而降低隨機線性網(wǎng)絡編碼的計算開銷與算法復雜度[4-5]?；谝陨戏治觯疚奶岢隽艘环N混合式無線Mesh網(wǎng)絡路由與信道分配聯(lián)合優(yōu)化方法。

1 混合無線Mesh架構

Mesh傳感器網(wǎng)絡通過網(wǎng)狀拓撲結構實現(xiàn)網(wǎng)絡的全覆蓋,網(wǎng)狀拓撲如下：1)由稱為Mesh基站(無線傳感器基站)的中心節(jié)點(可以與網(wǎng)絡)控制；2)基站作為連接到外網(wǎng)的接口；3)無線Mesh網(wǎng)絡通過點到多點的無線接入系統(tǒng)802.15.4接入網(wǎng)絡[6]。

某些移動用戶希望在沒有可用網(wǎng)絡基礎設施的情況下通信，例如消防隊員需要在通往緊急站點的途中連接到救護車。在這種情況下，具有無線網(wǎng)絡接口的移動自組織集合可以形成瞬時網(wǎng)絡，而無需任何已建立的網(wǎng)絡基礎設施或集中式管理。在互聯(lián)網(wǎng)工程任務組(IETF)內(nèi)形成的移動自組織網(wǎng)絡(MANET)組主要集中于開發(fā)新的MANET規(guī)范，并將其引入到互聯(lián)網(wǎng)標準軌道。他們的目標是支持移動自組織網(wǎng)絡，通過數(shù)百個移動自組織路由器支持移動自組織網(wǎng)絡，并解決這種網(wǎng)絡面臨的挑戰(zhàn)。然而，移動自組織網(wǎng)絡面臨諸多挑戰(zhàn)，例如，除了引起變遷路徑的移動性和電池限制之外，還限制了根據(jù)傳動誤差的無線傳輸范圍、隱藏節(jié)點問題和分組丟失。根據(jù)所謂的認證因素，對用戶的身份認證方式分為3類：根據(jù)你所知道的信息來證明你的身份；根據(jù)你所擁有的東西來證明你的身份；根據(jù)獨一無二的身體特征來證明你的身份。每個認證因素包括一系列元素，其被用于授予訪問權、批準事務處理請求、簽署文件或其他工作產(chǎn)品、授予他人權限以及建立權限鏈之前的身份認證或驗證中[7]。

無線傳感網(wǎng)絡存在分布的跨區(qū)域性，隨著無線傳感網(wǎng)絡的擴張，傳感器數(shù)目增多，將產(chǎn)生大規(guī)模的傳感數(shù)據(jù)。兩層分布式存儲架構，使用分布式數(shù)據(jù)庫HBase存儲跨區(qū)域的無線傳感網(wǎng)絡數(shù)據(jù)和全局數(shù)據(jù)存儲管理目錄，實現(xiàn)了一個近實時的存儲系統(tǒng)。從研究者的實驗結果[8]可以看出，這種具有可擴展性強、存儲和查詢效率高的系統(tǒng)可以解決大量傳感器數(shù)據(jù)存儲問題。

微處理器和傳感器技術的新進展能夠部署在大規(guī)模無線傳感器網(wǎng)絡中[9]。在某些環(huán)境中，傳感器裝置是一次性的。由于部署傳感器網(wǎng)絡的經(jīng)濟成本，傳感器節(jié)點在通信和計算能力、內(nèi)存和電池供電方面相對有限。傳感器網(wǎng)絡實現(xiàn)了許多應用，如車輛跟蹤、戰(zhàn)場偵察、生態(tài)和習慣監(jiān)測等。

由于無線Mesh網(wǎng)絡的低成本、快速部署的特點，Mesh作為一種新型通信范式被引入。應用場景有無線寬帶互聯(lián)網(wǎng)接入、智能傳輸系統(tǒng)、會議中心和疾病恢復中心即時網(wǎng)絡。WMN被分為3類[10]：基礎設施Mesh網(wǎng)絡、客戶端Mesh網(wǎng)絡、混合Mesh。在基礎設施Mesh網(wǎng)中，Mesh路由器提供一個無線的Mesh骨干基礎設施。與傳統(tǒng)的WLAN不同的是，有線骨干被無線多跳網(wǎng)絡代替。Mesh客戶端通過Mesh路由器簡單、直接存取網(wǎng)絡，客戶端沒有貢獻Mesh網(wǎng)絡基礎設施,起了消極的作用。在客戶端Mesh網(wǎng)絡中，不包括專用的網(wǎng)絡基礎設施，僅由移動Mesh客戶端組成，因此Mesh客戶端需要完成網(wǎng)絡功能，例如路由和包轉(zhuǎn)發(fā)，使得客戶端Mesh網(wǎng)絡基本上與傳統(tǒng)的ad-hoc網(wǎng)絡相同。混合無線Mesh網(wǎng)絡是最常見類型的WMN,結合了基礎設施Mesh網(wǎng)絡和客戶端Mesh網(wǎng)絡的概念，如圖1所示。

圖1 混合無線Mesh網(wǎng)絡架構Fig.1 Hybrid wireless Mesh architecture

混合Mesh網(wǎng)絡由靜態(tài)Mesh路由器形成Level2骨干網(wǎng)絡，其中一些Mesh路由器具有Level1網(wǎng)關功能和提供internet或其他網(wǎng)絡的認知功能。此外，Level3的移動客戶端能夠?qū)嵭徐o態(tài)網(wǎng)絡基礎設施部分的動態(tài)擴充，移動客戶端實行路由和包轉(zhuǎn)發(fā)功能?；旌螹esh結構是最可行的因為Mesh客戶端不僅能與別的Mesh客戶端直接通信，而且通過Mesh路由器獲得internet服務。本文中使用的是混合無線Mesh網(wǎng)絡，Mesh客戶端通過網(wǎng)關節(jié)點獲得internet服務[11]。

混合無線Mesh網(wǎng)絡是一個特殊類型的移動Ad-hoc網(wǎng)絡類型，但是兩者之間有明顯的不同[12]。在混合Mesh網(wǎng)絡中，Mesh路由器是相對強大的靜態(tài)的節(jié)點，能夠獲得裝有高容量電池的動力電源系統(tǒng)的能量[12]。通常Mesh路由器安裝了分配不重疊信道多射頻接口，明顯增加了無線Mesh網(wǎng)絡的傳輸性能。與Mesh路由器相反,Mesh客戶端限制了連接設備，例如筆記本或PDA等客戶端設備。在混合無限Mesh網(wǎng)絡中，當Mesh客戶端通過互聯(lián)網(wǎng)絡或其他網(wǎng)絡的存取服務時，大多數(shù)通信量來源于網(wǎng)關或返回到網(wǎng)關。因此有效的策略需要考慮Mesh節(jié)點和通信量模式的不同。由于混合無線Mesh網(wǎng)絡具有處理動態(tài)環(huán)境的能力，混合無線Mesh網(wǎng)絡已經(jīng)成為Ad-hoc網(wǎng)絡路由協(xié)議的備選。

2 模型與算法

Mesh傳感器網(wǎng)絡通過允許網(wǎng)絡自配置的辦法應付網(wǎng)絡配置問題。小的傳感器通常叫做微塵,收集環(huán)境數(shù)據(jù)或者與附近低能量節(jié)點通信短距離無線接口。如果每個節(jié)點的定位能被決定，基于定位的路由算法可以使用[13]。這些方法中最簡單的被稱作前向貪婪，是因為一個節(jié)點前向包給其任何一個靠近目的節(jié)點的鄰居節(jié)點。向前貪婪的操作如圖2所示：包開始在h被向前到h的任意一個靠近目的節(jié)點g的節(jié)點，在本例中，是節(jié)點e。過程是當包被向前到節(jié)點f,m,d最終是g。向前貪婪不總是發(fā)現(xiàn)最優(yōu)的路徑但是它總是產(chǎn)生向目標節(jié)點的合理有效的路徑。然而通過用這種方法結束節(jié)點堵塞對于包前向是可能的，在一個中間節(jié)點比任何鄰居節(jié)點更靠近目標節(jié)點的地方，因此不能決定在哪里去前向包。例如包旅行從j到g,將被向前沿著路徑j,k,l,當l沒有鄰居節(jié)點更比它本身更靠近g時，將被粘在l。例如(Greedy Perimeter Stateless Routing，GPSR)已經(jīng)成為減輕當貪婪向前失敗時使用的選擇策略。

圖2 向前貪婪Fig.2 Greedy forward

本文所使用的分布式貪婪生成樹路由(Greedy distributed spanning tree routing，GDSTR)是一種新型的地理位置路由算法,該算法能找到更短的路由,生成樹實現(xiàn)節(jié)能[14,15]。由于節(jié)點隨時間不斷發(fā)生變化及其無法實時更新，本文采用信道分配算法直接代替總線數(shù)據(jù)采集。主要目標是通過適當?shù)呐渲么鎯^(qū)域來解決熱點問題，避免多維搜索。人們的生存環(huán)境是真實的，會產(chǎn)生大量的監(jiān)測數(shù)據(jù)，但是只有其中的一小部分會被查詢。假設存在一個傳感器領域，其中傳感器節(jié)點統(tǒng)一部署并且初始過程時間同步。傳感器節(jié)點的位置是固定的，并且可以利用全球定位系統(tǒng)(Global position system，GPS)技術應用設備精準確定自己的位置。本文使用GDSTR進行傳感器網(wǎng)絡中的各個分組傳輸。緊湊幾何路由(Compact Geometric Routing，CGR)，GPSR與GDSTR的不同連接展度比較，如圖3所示。展度(Stretch)指從源點到某一個成員之間在應用層組播樹鏈路上的延時和在直接單播路徑上延時的比值[9]。GPSR使用兩種算法來實現(xiàn)路由過程，首先，傳感器節(jié)點利用貪婪算法逐步向最接近目的地位置的鄰居節(jié)點轉(zhuǎn)發(fā)分組；如果貪婪算法無效，則使用周邊前向算法。

圖3 在相同節(jié)點數(shù)情況下不同連接展度比較Fig.3 Comparison of different connection stretchwith the same numbers of nodes

本文使用CIAR路由判據(jù)，圖4為由G2網(wǎng)格和(G-1)2個交點構成的全局網(wǎng)格結構，即存儲區(qū)域(SA)。

構建全局網(wǎng)格結構后，在傳感器場中生成庫容曲線。圖5為SAi(i=1, 2, … , (G-1)2)標記的交點。庫容曲線被傳感器網(wǎng)絡中的所有傳感器節(jié)點所知。

圖4 全局數(shù)據(jù)結構Fig.4 Globe data structure

圖5 庫容曲線Fig.5 The curve of storage capacity

如圖6所示，定義一個參數(shù)Tp，將其分裂成(G-1)2個部分，其中每個時間段(TP)具有與其相關的存儲區(qū)域(SA)。

圖6 每個時間段與存儲區(qū)域之間的關系Fig.6 The relations between each time periodand storage area

基于不完全信息的博弈模型的Mesh傳感器網(wǎng)絡，本文對路由和信道分配算法進行聯(lián)合，提出了多接口路由與信道分配(Multi-interface routing and channel allocation game-local,MRCAG-Local)算法。僅考慮節(jié)點接口數(shù)量(α×β)大于信道數(shù)量(ω)的情況，即α×β>ω，算法偽代碼如表1所示。

模型的數(shù)學描述如下：

路由算法基本公式為：

(1)

基本函數(shù)方程為：

(2)

表1MRCAG-Local算法偽代碼

Table1PseudocodefortheMRCAG-Localalgorithm

1：隨機為每一個節(jié)點的各個接口分配信道

2：do

3： {repeat

4：獲取當前信道分配方案

5：對于每一個參與競爭節(jié)點wido

6： if 退避計算器=0

7： {

8：對于所有接口do

9： e=接口當前使用的信道

11： {

12：以一定概率將接口換至信道d*∈(D/Di)∩XI

13: }

14：重置退避計算器(從{1,2,…,δ}中選擇初始值)

15： else退避計算器-1

16： }

17：while(未收斂至滿足條件的信道分配方案)

隱藏層節(jié)點輸出為：

(3)

輸出節(jié)點的輸出為：

(4)

其中，θ為輸出節(jié)點閾值，wij為權值。

在線性關系下，基本方程為：

?j(eijkl?kul-ηkij?kφ)=0

(5)

考慮到存在無限的情況，則使用如下公式：

(6)

考慮到存在擴展的情況，則用式(7)代替式(6)：

(7)

本文在研究了基于基站調(diào)度、隨機和基于優(yōu)先級調(diào)度方法中的服務節(jié)點的總數(shù)和延遲時間。在隨機方法中，所有節(jié)點被隨機排序，并且首先發(fā)送請求的節(jié)點將被首先調(diào)度?；谏鲜鏊惴枋?，將前述的MRCAG-Local算法聯(lián)合基站調(diào)度算法綜合分析后,研究了基站調(diào)度聯(lián)合多接口路由信道分配算法(Basic station scheduling -multi-interface routing and channel allocation game-local, BSS-MRCAG-Local)偽代碼如表2所示，MSSd為不同Mesh客戶端(Mesh subscriber stations)。

表2BSS-MRCAG-LOCAL算法偽代碼

Table2PseudocodefortheBSS-MRCAG-LOCAL

algorithm

輸入:N<—MSSd, K<—第一層節(jié)點數(shù),Mi <—通過節(jié)點i傳遞數(shù)據(jù)的節(jié)點數(shù),a<—網(wǎng)絡拓撲結構;

1：for i <—1 to k

2： {

3： Rgi=i/gi

4： μ=μ+rgi

5： Tri=ci*gi

6： }

7：for i<—1 to m

8： {

9： repeat

10： {

11： tri=tri+Traij

12： tri=tri+Tri

13： j=j+1

14： Until j>n

15： }

16： ABWi=tri*rgi

17： Pi=(rgi/μ)*NPi

18： }

輸出: tri*rgi=ABWi分配帶寬給每個客戶端, (rgi/μ)*NPi=Pi為第一層的節(jié)點分配優(yōu)先權;

假設模擬環(huán)境在100 m×100 m的觀測區(qū)域內(nèi)隨機拋出100個傳感器節(jié)點。具體仿真參數(shù)設置如下：節(jié)點初始能量為1 J，隨機部署網(wǎng)絡拓撲，節(jié)點通信傳輸范圍100～200 m，數(shù)據(jù)傳輸能量消耗為45 nJ/bit，接收數(shù)據(jù)消耗為30 nJ/bit，分組大小為64 bit，通道衰落參數(shù)為0.3，仿真時間為300 s。最大迭代次數(shù)是1000次。

3 結束語

為了提高混合式無線Mesh網(wǎng)絡的有效性和可靠性，本文提出了BSS-MRCAG-Local算法。本文所使用的GDSTR路由在相同節(jié)點數(shù)情況下與CGR、GPSR比較連接展度最低。采用了不完全信息動態(tài)博弈，即在動態(tài)博弈中，行動有先后次序。本文所使用的具有不完全信息的博弈模型，是在當前信道分配過程中，對于每一個參與競爭的節(jié)點，全部接口使用情況不全部知曉的情況下，以一定概率將接口切換至信道，并修正自己的初步判斷的過程。

[1] Vieira L F M, Gerla M, Misra A. Fundamental limits on end-to-end throughput of network coding in multi-rate and multicast wireless networks[J]. Computer Networks, 2013, 57(17):3267-3275.

[2] Wang Q, Kim M, Shi Y, et al. Predict brain MR image registration via sparse learning of appearance and transformation[J]. Medical Image Analysis, 2015, 20(1):61-75.

[3] Chen J, He K, Du R, et al. Dominating set and network coding-based routing in wireless Mesh networks[J]. IEEE Transactions on Parallel and Distributed Systems , 2015, 26(2): 423-433.

[4] Zhi Jian, Yin Bao, Wang Jun-hui, et al. Design of a node architecture for logic-calculation nased all-optical network coding scheme[J]. Journal of China Universities of Posts & Telecommunications, 2013, 20(5):110-116.

[5] Li L, Gu R, Ji Y, et al. All-optical OFDM network coding scheme for all-optical virtual private communication in PON[J]. Optical Fiber Technology, 2014, 20(2):61-67.

[6] Chi K, Zhu Y H, Jiang X, et al. Practical throughput analysis for two-hop wireless network coding[J]. Computer Networks, 2014, 60(5):101-114.

[7] Kanagasabapathy A A, Franklin A A, Murthy C S R. An adaptive channel reconfiguration algorithm for multi-channel multi-radio wireless Mesh networks[J]. IEEE Transactions on Wireless Communications, 2010, 9(10):3064-3071.

[8] Saifullah A, Xu Y, Lu C, et al. Distributed channel allocation protocols for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems , 2014, 25(9): 2264-2274.

[9] Jung S, Sung J, Bang Y, et al. Greedy Local Routing Strategy for Autonomous Global Load Balancing Based on Three-Dimensional Potential Field[J]. IEEE Communications Letters, 2010, 14(9):839-841.

[10] Amalia F Foka, Panos E Trahanias. Probabilistic autonomous robot navigation in dynamic environments with human motion prediction[J]. International Journal of Social Robotics, 2010, 2(1):79-94.

[11] Jung S, Sung J, Bang Y, et al. Greedy local routing strategy for autonomous global load balancing based on three-dimensional potential field[J]. IEEE Communications Letters, 2010, 14(9):839-841.

[12] 王繼紅, 石文孝, 尚碩, 等. 無線Mesh網(wǎng)絡負載與干擾感知傳輸時間路由度量[J]. 吉林大學學報: 工學版, 2015,45(1): 297-303.

Wang Ji-hong ,Shi Wen-xiao ,Shang Shuo ,etal .Load and interference-aware transmission time routing metrics for wireless mesh networks[J]. Journal of Jilin University (Engineering and Technology Edition), 2015, 45(1): 297-303.

[13] Liang Q, Yao D, Deng S, et al. Potential field based routing to support QoS in WSN[J].J Comput Inform Syst, 2012, 8(6).

[14] Maamar H R, Pazzi R W, Boukerche A, et al. A supplying partner strategy for mobile networks-based 3D streaming - proof of concept[C]∥ IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum,IEEE, 2010:1-6.

[15] Wu T Y, Chan H L. Integrate airtime metric and geocast over P2P-based VoD streaming cache[J]. Tamkang Journal of Science and Engineering, 2010, 13(1):99-106.