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

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

0 引 言

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

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

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

1 混合無線Mesh架構(gòu)

Mesh傳感器網(wǎng)絡(luò)通過網(wǎng)狀拓?fù)浣Y(jié)構(gòu)實現(xiàn)網(wǎng)絡(luò)的全覆蓋,網(wǎng)狀拓?fù)淙缦拢?)由稱為Mesh基站(無線傳感器基站)的中心節(jié)點(可以與網(wǎng)絡(luò))控制；2)基站作為連接到外網(wǎng)的接口；3)無線Mesh網(wǎng)絡(luò)通過點到多點的無線接入系統(tǒng)802.15.4接入網(wǎng)絡(luò)[6]。

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

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

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

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

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

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

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

2 模型與算法

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

圖2 向前貪婪Fig.2 Greedy forward

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

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

圖4 全局?jǐn)?shù)據(jù)結(jié)構(gòu)Fig.4 Globe data structure

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

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

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

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

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

路由算法基本公式為：

(1)

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

(2)

表1MRCAG-Local算法偽代碼

Table1PseudocodefortheMRCAG-Localalgorithm

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

2：do

3： {repeat

4：獲取當(dāng)前信道分配方案

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

6： if 退避計算器=0

7： {

8：對于所有接口do

9： e=接口當(dāng)前使用的信道

11： {

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

13: }

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

15： else退避計算器-1

16： }

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

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

(3)

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

(4)

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

在線性關(guān)系下，基本方程為：

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

(5)

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

(6)

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

(7)

本文在研究了基于基站調(diào)度、隨機和基于優(yōu)先級調(diào)度方法中的服務(wù)節(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)絡(luò)拓?fù)浣Y(jié)構(gòu);

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)先權(quán);

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

3 結(jié)束語

為了提高混合式無線Mesh網(wǎng)絡(luò)的有效性和可靠性，本文提出了BSS-MRCAG-Local算法。本文所使用的GDSTR路由在相同節(jié)點數(shù)情況下與CGR、GPSR比較連接展度最低。采用了不完全信息動態(tài)博弈，即在動態(tài)博弈中，行動有先后次序。本文所使用的具有不完全信息的博弈模型，是在當(dāng)前信道分配過程中，對于每一個參與競爭的節(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)絡(luò)負(fù)載與干擾感知傳輸時間路由度量[J]. 吉林大學(xué)學(xué)報: 工學(xué)版, 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.