混合式無線Mesh網絡路由與信道分配聯合優化

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

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

0 引 言

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

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

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

1 混合無線Mesh架構

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

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

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

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

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

圖1 混合無線Mesh網絡架構Fig.1 Hybrid wireless Mesh architecture

混合Mesh網絡由靜態Mesh路由器形成Level2骨干網絡，其中一些Mesh路由器具有Level1網關功能和提供internet或其他網絡的認知功能。此外，Level3的移動客戶端能夠實行靜態網絡基礎設施部分的動態擴充，移動客戶端實行路由和包轉發功能。混合Mesh結構是最可行的因為Mesh客戶端不僅能與別的Mesh客戶端直接通信，而且通過Mesh路由器獲得internet服務。本文中使用的是混合無線Mesh網絡，Mesh客戶端通過網關節點獲得internet服務[11]。

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

2 模型與算法

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

圖2 向前貪婪Fig.2 Greedy forward

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

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

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

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

圖4 全局數據結構Fig.4 Globe data structure

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

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

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

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

模型的數學描述如下：

路由算法基本公式為：

(1)

基本函數方程為：

(2)

表1MRCAG-Local算法偽代碼

Table1PseudocodefortheMRCAG-Localalgorithm

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

2：do

3： {repeat

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

5：對于每一個參與競爭節點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(未收斂至滿足條件的信道分配方案)

隱藏層節點輸出為：

(3)

輸出節點的輸出為：

(4)

其中，θ為輸出節點閾值，wij為權值。

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

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

(5)

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

(6)

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

(7)

本文在研究了基于基站調度、隨機和基于優先級調度方法中的服務節點的總數和延遲時間。在隨機方法中，所有節點被隨機排序，并且首先發送請求的節點將被首先調度。基于上述算法描述，將前述的MRCAG-Local算法聯合基站調度算法綜合分析后,研究了基站調度聯合多接口路由信道分配算法(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<—第一層節點數,Mi <—通過節點i傳遞數據的節點數,a<—網絡拓撲結構;

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為第一層的節點分配優先權;

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

3 結束語

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

[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網絡負載與干擾感知傳輸時間路由度量[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.