一種基于博弈論的無線網狀網絡信道分配算法

鄭鵬宇，何世彪，張馨月，黃 帥

(1.重慶通信學院，重慶 400035;2.中國煙草總公司重慶市公司石柱分公司，重慶 409100)

無線網狀網(wireless mesh network，WMN)是由組織成網狀的無線節點構成的通信網絡，具有自組織、自配置、低開銷、自愈性以及高帶寬等優點。鑒于這些優點，WMN具有許多重要的商業應用，如“社會無線網絡”“應急通信”等。

現在研究的熱點集中于多天線多信道(multi-radio multi-channel，MRMC)WMN網絡上。多天線多信道無線Mesh網絡是由若干配置了多個IEEE802.11 標準天線［1-3］的網狀節點構成的，在MRMC網絡中節點可以和鄰居同時發送和接收數據。

影響MRMC網絡性能的因素主要是同信道間的干擾。這種干擾產生的主要原因是鄰近節點在同一時間內使用相同的信道傳輸。信道分配的目的就在于通過將可用的正交信道分配至每一條鏈路，在保證鏈接的條件下，使得干擾最小。

本文采用博弈論的方法來解決無線Mesh網絡中信道分配的問題。博弈論主要研究多個自主實體之間為了達到某種目的而相互作用的輸出結果。而無線Mesh是一個分布式、自組織以及自配置的網絡，這些特點就使得每個分布式的節點都可以被視為一個自主實體，這樣博弈論就非常適合于解決無線Mesh網絡中信道分配的問題。

本文提出了一種基于博弈論的無線Mesh網絡信道分配算法。

1 無線傳播和干擾模型

在理論分析當中，通常使用的傳播模型為圓盤傳播模型(two-ray ground模型)，該模型可以描述節點的信號傳輸范圍和載波偵聽的范圍(干擾距離)。用Rt表示數據最大傳輸距離，Ri表示載波偵聽距離，其關系為Ri=qRt(q≥2)。

無線信道的廣播特性導致了同信道鄰近節點之間的干擾。文獻［4］總結出了3種干擾模型:PCA(primary conflict avoidance)、RCA(receiver conflict avoidance)和TRCA(transmitter-receiver conflict avoidance)，其中TRCA是最為嚴格的干擾模型，在干擾范圍內所有的節點都無法通信。

在如圖1所示的圓盤傳播模型(q=2)和TRCA干擾模型中，任意一對接點通信時會對同信道的鄰近節點造成干擾。圖1中，節點A和節點B通信時會對周圍16個節點造成干擾，因此，單信道網絡的通信效率很低。圖1中還顯示，在同一信道下，節點C和節點D通信必須和使用相同信道通信的節點A和B相隔3倍Rt才不會產生干擾。

圖1 TRCA干擾模型和Two-ray Ground傳播模型

2 博弈論建模

2.1 博弈論模型

利用博弈論對無線Mesh網絡進行研究，其中的關鍵是如何將博弈論引入到相應算法的設計與分析之中，找到算法的納什均衡點［5］。因此，在利用博弈論信道分配問題之前，首先將所研究的問題抽象成博弈論問題模型，無線Mesh網絡中的頻譜分配問題是關系到各節點頻譜選擇的博弈過程。假設把頻譜的分配等同于信道的分配，即信道分配問題可以建模成一個博弈輸出。在這個博弈過程中，無線Mesh網絡中的節點可視為參與者，對于傳輸信道的選擇就是行動策略，且參與者的效用與所選擇的信道相關聯。那么，頻譜分配問題的博弈論數學描述的一般形式為

其中:N是參與者(選擇某個信道傳輸數據的無線Mesh節點)的有限集;Si是相對于參與者i的策略集，定義S= ×Si，i∈N是策略空間，則Ui:S→R是效用函數集。在博弈中效用函數Ui是參與者i選擇策略si和其對手所選策略s-i的函數。

博弈論分析的關鍵問題之一是判斷對于自適應的信道分配算法是否存在收斂點，且這個收斂點對于任何用戶都不會偏移，也就是納什均衡。因此，對于參與者的一組策略，S={s1，s2，…，sN}，當且僅當 Ui(S)≥Ui(s'i，s-i)，?i∈N，s'i∈Si時，這組策略是納什均衡。

2.2 效用函數的確定

通過為每條鏈路合理地分配信道來達到最大化網絡信噪比的目的。而鏈路能否成功傳輸數據與網絡中的干擾有著密切的聯系，即與信噪比SINR有關。因此，在接收端j關于發射端i的信噪比記為SINRre，表達式為

式中:pi是發射端i的發射功率;Gij為發射端i到接收端j的鏈路增益;Δ 是背景噪聲［6］;f(k，j)是表示由節點k到接收端j的干擾方程，其表達式為

可見WMN網絡中總干擾最小就是使得網絡中各個節點所受到的干擾最小，但節點之間在相同頻譜上的干擾又是相互的，這也正符合了博弈論研究問題的特征。

在通常情況下，參與者i能夠通過感知在某個特定信道上的干擾來選取最佳的信道傳輸數據。另一方面，由于網絡中參與者之間的干擾是相互的，參與者i所選取的對自身干擾最小的信道并不能保證其對鄰近的參與者也是最小的，同時不能保證整個網絡的總干擾水平最小。因此，還必須保證參與者i所選取的信道對于其他鄰近參與者的干擾最小。定義參與者i效用函數表達式為

干擾方程為

式(4)、(5)中:P={p1，p2，…，pN}是 WMN 網絡中各個節點的發射功率集合(N為節點數);S={s1，s2，…，sM}是策略集(M為正交信道數量)。式(4)中:第1部分是參與者i受到其鄰近參與者在相應信道上的干擾，記為Iid;第2部分為參與者在相應信道上對其他鄰近參與者的干擾，記為Iod。

則效用函數ui的另一種表達方式為

其中:Iid在接收端測量得到;Iod在發射端計算得出。雖然在采用ui的情況下，算法需要在公共信道上使用一個數據包來傳遞參與者對鄰近節點干擾的測量信息，算法的復雜度會增加，但是效用函數的設計的確能滿足最小化系統總干擾水平的目標要求。

位勢博弈的特性是博弈中存在一個位勢函數，該函數可以準確地反映任何參與者的效用函數中產生的單方面變化［7］。這個位勢函數代替了具體的博弈效用函數反映效用的改善信息。一個確定的位勢函數P定義為:

定義1 若存在一個函數，對所有的i和si，si'∈Si有這樣的性質:

則稱該函數為位勢函數。

通過計算，對于效用函數ui的信道分配博弈，一個確定的位勢函數為

即

具體證明參照文獻［8］。

3 算法實現以及算法改進

3.1 算法實現及過程

因為算法的實現需要接收端和發送端在一條公共信道上傳輸信令，因此設計一個3次握手機制的握手協議。

借鑒使用與IEEE802.11協議中的RTS-CTS交換協議相類似的協議，其中規定信令協議包如表1所示。

信令協議中的信令數據包主要起2個方面的作用:①測量各傳輸信道的干擾量，計算效用函數;②廣播節點對于某條信道的使用情況。每個節點的接收端和發射端均保存一個信道狀態表(CST)，用于記錄各信道被其他節點占用的情況和儲存數據流的目的節點和下一跳節點的信息。一旦用戶偵聽到公共信道中相應信道的信令數據包，則更新自身發送端和接收端的CST，以便掌握其他節點的信息。

表1 信令協議中數據包功能

算法的偽代碼見算法1。

算法1資源分配算法

3.2 算法改進

雖然效用函數ui能實現系統的效用函數最大化，但是這種系統級的性能優化沒有考慮到不同節點的業務需求，忽略了個性化的QoS需求和公平性。系統資源可能被少數節點占用，使其超過業務QoS需要的資源，而相當一部分節點占用的資源無法保證其業務最低的QoS要求。因此，需要對效用函數U進行必要的修正。

根據參考文獻［7］的算法，引入功率調整方法，研究一種滿足業務需求的分布式動態分配方案。每個節點根據自己的QoS需求和本地信息進行分布式信道選擇和功率控制。本算法采用SINR來量化業務的QoS需求，既有:

在式(4)的基礎上對系統的目標進行擴展，可表示為

式(13)所示算法分為2個階段來實現:第1階段為信道分配，即每個用戶通過博弈算法選擇信道;第2階段為功率調整，即在第1階段結果的基礎上，根據用戶的QoS需求進行功率調整。

第2階段的具體步驟:

根據第1階段的分配結果，計算業務的信噪比SINR并調整功率，調整策略包括3種:

1)若 SINRi，min≤SINRi≤SINRi，max保持第 1 階段的發射功率不變。

2)若 SINRi＜SINRi，min則用戶需要增加自身發射功率，使得滿足最小SINR要求，有2種情況:①若不存在使得，則關閉節點i的發送;②若存在，則

3)若 SINRi≥SINRi，max，則節點 i需要降低發射功率，使得滿足最大SINR要求，既有SINRi，max，則然后將第2階段的結果返回第1階段進行迭代，直至收斂。

4 算法仿真

在仿真中評估了算法1和其改進算法的性能。網狀節點隨即分布在一個區域為200 mm的場景內。無線Mesh網絡中的節點使用IEEE802.11b天線，設計一個接收接口和一個發送接口，在場景中隨機分布20到50個節點，有一條信道作為公共信道用于傳輸信令數據包，可使用的正交信道數為2到8條，每個節點的發射功率不超過1 W。使用NS2.34作為仿真工具。

首先計算位勢函數值(圖2)，從中看出算法的收斂情況。當節點數為50，可用正交信道為4條重復計算80次得到2種算法的位勢函數。由圖2可以看出2種算法隨著迭代次數的增加逐漸趨于收斂。算法1在迭代40次后進入收斂狀態，而改進算法在迭代67次后才趨于收斂。由圖2可知2種算法在前40次迭代中的位勢函數值是相同的，但改進算法在達到算法1達到收斂之后還將繼續判斷各節點的SINR值是否滿足用戶需求，所以導致改進算法需要更多的迭代次數才能達到收斂。

圖2 2種算法位勢函數收斂狀況比較

從圖3中可以看出:①在不同信道數量的情況下2種算法的收斂速度都是很快的，但是改進算法的收斂速度要慢于算法1。②當信道數量較少時，算法的收斂次數是增加的，這是因為在可用信道數較小的情況下網絡中節點會頻繁的切換信道;而當可用信道比較多時，2種算法的迭代至收斂的次數都會逐漸減小，這是因為在信道較多的情況下節點的信道選擇會較快地達到穩定狀態并保持在這一狀態。

圖3 2種算法的位勢函數在不同信道數量下收斂狀況的比較

圖4和圖5分別描述了2種算法的網絡性能。圖4為2種算法的系統吞吐量隨著節點數量變換的結果，可以看出:系統吞吐量隨著節點數量的增加而增加，且改進算法的系統吞吐量的變化幅度較大;在節點數比較少的情況下，算法1的系統吞吐量較大，但當節點數增多至30個以上是，改進算法的系統吞吐量變大，即節點數越多，改進算法的優勢越明顯。而從圖5中可以看出，算法1的信道接入時延性能要優于改進算法，這是因為改進算法的復雜度要高于算法1。

圖4 2種算法的系統吞吐量隨著節點數量變化的情況比較

圖5 2種算法的信道接入時延在不同信道數量下的變化

5 結束語

綜上所述，利用博弈論設計無線Mesh網絡的信道分配算法是一種行之有效的方法。本文采用博弈論的方法設計了一種效用函數來實現最大化網絡信噪比的目的，并通過改變各節點發射功率的大小來提高個節點的QoS，使得網絡資源能得到更為合理的利用。

［1］Akyildiz I，Wang X.A survey on wireless mesh networks［J］.IEEE Communications Magazine，2005，43(9)：23-30.

［2］Bruno R，Conti M，Gregori E.Mesh networks：commodity multi-hop ad hoc networks［J］.IEEE Communications Magazine，2005，43(3)：123-131.

［3］Audhya G K，Sinha K，Ghosh S C，et al.A survey on the channel assignment problem in wireless networks［J］.Wireless Communications and Mobile Computing，2011，11(5)：583-609.

［4］Kodialam M ，Nandagopai T.The effect of interference on the capacity of multi-hop wireless networks［M］.Chicago，IEEE Symposium on Information Theory，2004：470-479.

［5］Singh M，Saxena A.Secure computation for data privacy［C］//Proc SECCOM 07.Nice：［s.n.］，2007：58-62.

［6］Blough D，Resta G，Santi P.Approximation algorithms for wireless link scheduling with SINR-based interference［J］.IEEE/ACM Transactions on Networking(TON)，2010，18(6)：1701-1712.

［7］Mondere D，Shapley L.Potential Games and Economic［J］.Behavior，1996，14：124-143.

［8］Yu Q，Chen J，Fan Y，et al.Multi-channel assignment in wireless sensor networks：A game theoretic approach［C］//Proc of INFOCOM 10.San Diego：IEEE，2010：1-9.