基于最大化網絡吞吐量的WMN信道分配算法

鄭鵬宇，何世彪，戴昊峰，張 暉

(重慶通信學院，重慶 400035)

無線Mesh網絡(Wireless Mesh Networks，WMN)是一種新型的Internet無線接入解決方案，被認為是一種很有前途的技術，是一種多跳、具有自組織和自愈特點的寬帶無線網絡結構，即高容量、高速率的分布式網絡［1］。它融合了無線局域網(WLAN)和Ad Hoc網絡的優勢，支持用戶節點和無線接入點(AP)之間的多跳通信，即在WMN中，任何用戶節點都可以收發自己的數據分組。WMN作為最后一英里寬帶接入的解決方案，有效解決了傳統WLAN中存在的可伸縮性差和健壯性差等問題。

而多天線多信道(Multi-Radio Multi-Channel，MRMC)WMN是當前的研究熱點，一個多天線多信道WMN［2］是指一個WMN網絡中的若干節點配置了多個IEEE802.11標準天線［3-5］，因此這些節點可以同時和其鄰居節點發送、接收數據。在WMN中，影響網絡吞吐量的主要因素是鏈路間同信道干擾，這種干擾是因為相鄰節點在同一時刻使用相同信道而產生的。信道分配的目的就是將可用的正交信道分配給每條鏈路，以減小鏈路間的干擾。由此可見信道分配對于提高網絡吞吐量起到關鍵作用。

目前，對于無線Mesh網絡的信道分配機制主要分為集中式和分布式分兩種，本文主要研究了分布式的信道分配機制。文獻［6］采用對每個節點分配同樣信道集合的方式來進行信道分配，這種方式雖然易于實現且也能保證網絡連通性，但是對于復雜網絡的適應性不夠;在文獻［7］中提出基于負載感知的信道分配策略，但其依附于路由協議聯合設計，信道分配前只基于虛鏈路容量進行評估，考慮相對簡單;在文獻［8-9］中提出了一種基于CHYA的準靜態信道分配方案，但是該方案沒有考慮信道干擾，增加了Mesh網絡自身的競爭性;文獻［10］提出了基于干擾沖突的貪婪信道分配策略，但鏈路評估時沒有考慮網絡負載，降低了網絡性能。文獻［11］提出的SICA分配機制是一種基于干擾感知的分布式分配算法，采用一種在線學習算法，且各節點不需要完備的策略信息。其不足在于算法執行到穩定狀態所耗費的時間較長，以及在網絡負載較大時需要頻繁切換信道來傳輸數據流的數據包，增加了端到端延時。

針對以上算法中的不足，本文提出了一種基于博弈論的信道分配算法(Game Based Channel Assignment，GBCA)，GBCA算法采用聯合博弈，能以更快的速度達到收斂狀態。通過仿真分析，證明GBCA算法能夠很好地避免無線Mesh網絡中節點之間和鏈路之間的干擾，可以較好地改善系統性能(如系統吞吐量、收斂性、丟包率等)。

1 系統模型構建

1.1 網絡模型

GBCA算法的目標是最大化網絡的吞吐量，系統的吞吐量和系統中的干擾有密切的關系。把WMN模型簡化為一個有向圖G(V，E)，其中V是節點集合，E是網絡中的鏈路集合。節點的通信半徑記為rc，偵聽半徑(干擾半徑)記為ri，其中ri=q×rc(q＞1)。則當且僅當節點i，j在彼此的通信范圍內才存在鏈路(i，j)。當且僅當兩條鏈路使用同一條信道，且至少有一條鏈路的一個端點在另一條鏈路的一個或兩個端點的干擾范圍內時，兩條鏈路彼此干擾。如圖1所示，鏈路(A，B)使用信道c通信時如果鏈路(C，D)也同時使用信道c通信，則兩條鏈路彼此之間存在干擾。

圖1 WMN網絡干擾模型

WMN中的每個節點都有N個無線收發天線，每個天線都可以被調至某個正交信道上用于接收發送數據，可用正交信道數為M。在傳輸和接收數據時，每個天線都必須分配一個唯一的正交信道，即一個節點的不同天線必須分配不同的信道，所以N＜M。

1.2 算法模型

從式(1)所示的香農公式可得，信道容量與帶寬和信噪比有關，當帶寬一定時，信噪比越大則信道容量越大。所以利用這個特性，可以構建出最大化網絡吞吐量的資源分配算法。

對于網絡中的一個節點i而言，其傳輸時是否受到干擾取決于在其傳輸數據時干擾范圍內有無其他節點同時使用相同信道進行數據傳輸。如果有，節點i的傳輸就不會成功。假設Ii為節點i干擾范圍內的節點集合，=n為集合中結點的個數。令C為可用正交信道的集合，則=M。

通過為每條鏈路分配合理的流量和信道來最大化網絡的吞吐量，也即傳輸成功的總流量。而成功傳輸的概率與網絡中的干擾有關。對于一條鏈路(i，j)而言，網絡對其造成的干擾主要由接收端j所受到的干擾引起，即Ij中存在與鏈路(i，j)使用相同信道的節點。如圖1所示，對與鏈路(A，B)使用信道c通信，如果節點A的干擾范圍內的節點(節點C，E，F，G，H)有使用信道c通信則會對A造成干擾，同理接收端同樣可能收到其干擾范圍內節點的干擾。

那么數據成功傳輸的概率則與信噪比(SNR)有著密切的關系，SNR的表達式為

式中:Gij為鏈路增益;Δ 為背景噪聲［12］;f(k，j)是指節點k是否使用和節點j相同的信道，其定義為

對于發送節點i，首先查看其有無到達目的節點的路徑，如果有則通過公共信道與下一跳節點通信以確定鏈路的信道分配;如果沒有，則將感知到的各節點在每條信道上的干擾值Δk(c)利用文獻［13］中的CMAODV路由協議進行路由發現。

從而可以看出，一條鏈路成功傳輸的概率不僅依靠接收端，同樣也會受到發送端路徑選擇的影響。但從式(4)可以看出一條鏈路成功傳輸的比特概率與接收端的SNR有關，所以定義鏈路(i，j)的成功傳輸概率為

從式(2)～式(5)中可知，鏈路是否能夠成功傳輸依賴于信道的分配。定義一個鏈路流量需求矩陣，記為F，其中包含了WMN網絡中各條數據流從其源節點到目的節點所經過鏈路的流量需求，如fab(fab∈F)為一條鏈路的流量需求，則表示從節點a到節點b的鏈路的流量需求。令pathab為節點a到節點b的路徑，則對于所需要構建的效用函數而言，效用函數的策略集S就是網絡的可用正交信道，那么效用函數U(s)的物理意義則可以定義為:在給定流量需求矩陣F的情況下，能成功傳輸的流量。其表達式為

效用函數的目標就是最大化WMN網絡的吞吐量。

1.3 收斂性

定義1(納什均衡)［14］:如果策略s∈S是一個納什均衡點，當且僅當對于每一個博弈者i，?si(δ)∈i的策略空間，都滿足

GBCA的納什均衡意味著網絡中沒有弈者可以通過單獨改變自身的策略使得效用函數U(s)得到改進。

定理1(納什定理)［14］:每一個有限策略式博弈有一個混合策略或純策略納什均衡點。

具體證明請參照文獻［14］中的證明。從定理1可以看出，GBCA算法至少存在一個納什均衡點，在下一部分將會進行具體證明。

1.4 算法執行過程

為了使得網絡中的吞吐量最大化，采用GBCA算法的WMN網絡中的每一個節點都試圖最小化網絡的總干擾。這樣每一個節點的信道分配問題就可以被視為一個聯合博弈。弈者為每個節點，而信道則是每個弈者的可選策略。在GBCA中，每個弈者都存有一個如表1所示的狀態表。表中的αi為數據流的目的節點，βi為數據流的下一跳節點(如果沒有則進行路由發現)，ci為所分配的信道。

表1 節點狀態信息表

在GBCA中，每個弈者都使用整個網絡的效用函數作為自己的效用，這是一種協同博弈，由于弈者的目標相同，所以GBCA算法的收斂速度要快于傳統的博弈信道分配算法。可以看出，GBCA是一個重復博弈，在每次循環中弈者通過s-i來選擇自身的策略以達到改善U(s)的目的。但是為了防止網絡中的震蕩，每個循環中只有一個弈者可以做出改變。因此，每個節點還包含有一個二進制表，此表標示出了該節點的行動次序。此外，還包含一個用于計數的標志K，標示還有幾個節點可以通過改變自身策略以改善效用函數。在開始階段，由于每個弈者都是隨機采用的策略，所以可以改變策略使得效用函數得以改善，所以K=N。

GBCA的執行過程可以分為以下幾個階段:

1)起始階段:各個節點隨機分配信道，并形成狀態表，此時的策略記為s0。

2)改進階段:各個節點依照自己在二進制順序表中的順序，依次改變自己的策略。如當輪到節點i選擇策略時，首先感知鄰近節點在各信道上對自身造成的干擾，然后通過公共信道發送干擾值到下一跳節點，下一跳節點通過感知干擾值以及發送端所測量得到的干擾值來計算概率。如果存在一個策略si(δ)使得U(s)得到改善，則令sk+1=si(δ)，同時保持K，廣播K值，進入下一輪循環;如果沒有策略使得U(s)得到改善，則令K=K－1，并將K進行廣播，停留在這一輪循環，讓下一個節點選擇策略。

3)結束階段:當K的值減小到0時，則整個網絡進入到收斂狀態，也即最佳狀態，各節點將保持自身的策略。

從GBCA算法的3階段可以得到定理2和定理3。

定理2:GBCA算法至少存在一個可達到的納什均衡點。

證明:假設K不能夠在有限的循環次數中減小到0，那就意味著總是存在至少一個節點和一個策略si(δ)使得效用函數得到改善，從而使得效用函數無U(s)一直增加。但是由于可用策略是有限的，那么U(s)必然不會無限制地增加，因此假設不成立。

定理3:GBCA算法可以收斂至一個納什均衡點。

證明:整個算法中K遞減至0的過程就是GBCA的收斂過程，當K=0時，算法即收斂至博弈中的一個納什均衡點。

2 仿真與分析

在仿真中評估了GBCA算法和文獻［7］中的SICA算法的性能。20～50個網狀節點隨機分布在一個1000 m×1000 m范圍內，其中有1～3個節點作為網關節點，無線網狀網在設置中配置3條天線，且節點的傳輸半徑為200 m，干擾半徑為400 m。場景中有8條可用正交信道，其中一條信道設為公共信道用于傳輸公共數據包。隨機將2～10條CBR數據流隨機分配給網絡中的節點，使用NS2.34作為仿真工具。

首先比較GBCA算法和SICA算法的收斂速度。圖2展示的是在網絡節點數為20個時，以丟包率來衡量的收斂性。從圖2中可以看出GBCA算法的收斂速度要比SICA算法的收斂速度快，GBCA算法在循環了40次以后進入收斂狀態，而SICA算法則是要執行69次循環后才進入收斂狀態。這是因為GBCA算法的效用函數是針對全局最優的，而不是局部優化的。

圖3顯示了當網絡節點數量為20時，不同數據流情況下GBCA算法和SICA算法的丟包率比較，可以看出GBCA算法的傳輸性能要高于SICA算法。因為在SICA算法中只有1個發送天線和1個接收天線，在傳輸時需要不停地切換信道來實現多條數據流的傳輸，一部分數據因信道切換時造成的擾動而丟失，并隨著數據流的增加而不斷增大。GBCA算法中存在多個天線，無需頻繁切換信道，且能夠將干擾小的信道分配給鏈路，以保證數據流的成功傳輸。

圖4展示了網絡中有7條數據流時丟包率和網絡中節點數的關系，從圖中可以看到GBCA算法的丟包率明顯低于SICA算法的丟包率。同樣是因為SICA算法只有兩個天線隨著節點數目的增多，需要切換信道的次數也隨之增大，并且其算法中并沒有重點優化網絡數據流間的干擾，所以導致丟包率較高。

圖4 不同Mesh節點數對丟包率的影響

圖5和圖6分別對兩種算法在不同條件下的平均端到端時延進行了仿真分析。圖5是從不同Mesh節點數目的情況下對兩種算法的時延進行了分析，而圖6則是對不同數據流的流量進行了分析。圖5所示的仿真實驗的設置為:網絡中隨機分配了7條數據流，數據流量為500 kbit/s。由圖5可以看出SICA算法的端到端時延要略微低于GBCA算法，造成這種結果的原因是在于SICA算法不需要一條公共信道來進行公共信令的傳輸，從而省去了信令交換的時間。圖6的仿真設置為網絡中有20個節點，隨機分配了7條數據流。圖6表示在數據流流量較小時SICA算法的信道切換頻率較低，切換所造成的時延也較小。但是隨著數據流流量的增大，SICA算法的信道切換頻率也隨之增加，則造成了較高的切換時延。

圖7所代表的仿真設置是當網絡中有20個節點，其中有一個作為網關節點，并且有2～10條隨機分布流量為1000 kbit/s的數據流。圖7中給出了兩種算法的吞吐量隨著網絡負載變化的情況，可以看出當負載較低時兩種算法的網絡吞吐相差不大。但是隨著網絡負載的增加，GBCA算法的網絡吞吐量逐漸優于SICA算法，這是因為GBCA算法是采用全局最優的方法，使得整個網絡的吞吐量最大化。

3 總結

眾所周知，WMN網絡中的信道分配問題一直是一個NP難的問題，本文根據無線Mesh網絡分布式的特點，引入博弈論方法來解決這個問題，將問題模型化為整個網絡的聯合博弈。并提出了GBCA算法，算法執行過程中通過公共信道傳輸公共信令包，使得收發節點協同選擇出使得效用函數最大的策略，最終達到最大化網絡吞吐量的目標。

在文中給出了GBCA算法的具體實現，并且證明了算法的收斂性。本文通過NS2仿真工具，將GBCA算法和SICA算法進行了比較，結果表明GBCA算法有更快的收斂速度、較低的丟包率、較低的端到端時延以及比較大的網絡吞吐量等特點。

［1］方旭明.下一代無線英特網技術:無線Mesh網絡［M］.北京:人民郵電出版社，2006.

［2］AKYILDIZ I，WANG X.A survey on wireless mesh networks［J］.IEEE Communications Magazine，2005，43(9):23-30.

［3］KODIALAM M，NANDAGOPAI T.The effect of interference on the capacity of multi-hop wireless networks［C］//Proc.IEEE Symposium on Information Theory.Chicago，USA:IEEE Press，2004:470-479.

［4］BRUNO R，CONTI M，GREGORI E.Mesh networks:commodity multihop ad hoc networks［J］.IEEE Communications Magazine，2005，43(3):123-131.

［5］陳美飛，趙新建.無線Mesh網絡安全路由算法研究［J］.電視技術，2009，33(S1):116-118.

［6］DRAVES R，PADHYE J，ZILL B.Routing in multi-radio，multi-hop wireless mesh network［C］//Proc.ACM l0th Annual International Conference10th Mobile Computing and Networking.Pennsylvania，USA:ACM Press，2004:114-128.

［7］RANIWALA A，GOPALAN K，CHIUEH T.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks［J］.ACM SIGMOBILE Mobile Computing and Communications Reviews，2004，8(2):50-65.

［8］REN J，QIU Z D.Centralized quasi-static channel assignment in multi-radio wireless mesh networks［C］//Proc.IEEE International Conference on Communications Systems.Guangzhou，China:IEEE Press，2008:1149-1154.

［9］REN J，QIU Z D.Centralized quasi-static channel assignment for multiradio wireless mesh networks［J］.Wireless Sensor Network，2009(2):104-111.

［10］SUBRAMANIAN A P，GUPTA H，DAS S R.Minimum-interference channel assignment in multi-radio wireless mesh networks［C］//Proc.4th Annual IEEE Communications Society Conference on Sensor mesh and Ad Hoc Communications and Networks.California，USA:IEEE Press，2007:481-490.

［11］MARYAM A N，LLORENC C A.Adaptive channel assignment for wireless Mesh networks using game theory［C］//Proc.8th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems.［S.l.］:IEEE Press，2011:746-751.

［12］BLOUGH D，RESTA G，SANTI P.Approximation algorithms for wireless link scheduling with SINR-based interference［J］.IEEE/ACM Trans.Networking，2010，18(6):1701-1712.

［13］吳濤.基于跨層設計的無線Mesh網絡資源分配與QoS優化研究［D］.重慶:重慶郵電大學，2011.

［14］MACKENZIE A B，DASILVA L A.Game theory for wireless engineers［M］.New York:Morgan and Claypool，2006.