基于博弈論的無線Mesh網絡路由與信道分配聯合優化算法

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

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

0 引 言

無線Mesh網(Wireless Mesh networks，WMN)結合了無線局域網(Wireless LAN,WLAN)和無線移動自組織網絡(Ad-hoc網絡)的優點，是針對特定業務需求而出現的一種新型無線網絡技術[1]。其應用包括了家庭寬帶網絡(Home network)、區域和城網絡(WMAN)、公共緊急通信、戰場通信等[2]。由于具有傳輸速率高、架設方便、覆蓋范圍靈活以及較強的容錯能力等優點，無線Mesh網絡被認為是自組織無線網和自動可配置無線網中最有發展潛力的組網技術之一[3]。

由美國麻省理工學院成立的較早啟動的WMN實驗研究項目的實驗數據表明，對于超過4跳的路徑，基于TCP協議的端到端吞吐量在達到47.3 kB/s時，其端到端延遲為43 ms[4]。德國柏林洪德寶大學(HumboldtUniversity)的計算機科學學院的學生志愿者組建了名為Berlin Roof Net的WMN測試環境(Duarte et al. 2012)[5]。國內也對WMN進行了研究，比如天津技術開發區已采用無線Mesh解決方案在全區范圍內進行部署，日后將實現達到200個監控點的分布式網絡[6]。

著名科學家von Neuma和Morgenstern于20世紀中期提出了博弈論(也被稱為對策論或賽局理論)，主要研究某一博弈中決策者根據實時或者非實時的環境變化做出的決策對于最終收益的影響[7]。博弈論自出現之日起就在經濟學領域得到了廣泛應用，據統計，研究博弈論的學者們自博弈論誕生到2015年期間已經獲得了8次諾貝爾經濟學獎，其中在2012年時，更是以當時的獲獎者Lloyd Shapley的名字命名了著名的Shapley值，在2014年時，諾貝爾經濟學獎頒獎委員會將獎項頒發給了著有《博弈論》一書的法國作家——Jean Tirole[8]。

本文提出了一種新的基于博弈論的合作算法來解決聯合路由與信道分配的最優化問題。提出了兩個博弈策略：極大極小策略給所有節點分配最優極大極小路徑，提供給納什均衡策略一個常數向量；納什均衡策略應用向量l計算最優發射功率來達到均衡的信道分配。納什均衡點如果存在，解是唯一的。最后，通過數值仿真驗證了聯合簇間公平路由與信道分配算法的性能。

1 相關工作

在無線Mesh網絡中，如果節點被允許絕對自私地管理，節點在低質量鏈路上可能選擇轉發包(因此發生一個更低的機會花銷)，而不是占據一種合作形式，在合作形式下節點轉發通信在一條高質量鏈路上，在合作形式下可能得到公平的鏈接[8]。處理過程如下：假定每個資源節點(或是自私的或是合作的)是理性的。如果節點知道權力低將會受到網絡的懲罰，一個自私節點不會所有時間在一個低質量鏈路上轉發數據[9]。在另一方面，需要目標節點(收到流量)監測服務水平檢測到部分源節點壞的行為，監測對硬件和軟件都是一種需要很大能量花銷的活動。因此，源節點考慮范圍內合作而不是自私，與此同時，目標節點考慮監測來自于源節點的服務范圍[10]。用貝葉斯博弈理論找到Nash均衡點確保源節點的最優合作范圍和目的節點的最優監測率。本文的博弈理論公式是基于價格模型，為了確?？煽康逆溄?，每個目標節點收益一定量的“虛擬貨幣”給源節點(基于預算)[11]。虛擬貨幣被執行作為可用網絡經濟的有限的令牌集合。源節點用貨幣購買鏈接目的節點的鏈接。假定源節點通過指令通信控制中間節點。

信道對競爭和節點自身之間的信道分配方案影響越來越大，是導致無線網絡性能下降的最主要原因之一。雖然無線網絡中的所有節點都設置有多個射頻通信接口，但只有當連接的接口和信道保持通信時，每個接口才對應不同的信道。

為了適合節點自私自利的特性，幾個新的基于博弈論的機制被設計在Mesh傳感器網絡的路由算法中。帶有參數(V,T)的重復博弈方案被解釋如下：每一個節點的效用U與閾值V比較。如果U

博弈論廣泛應用于經濟學領域，從最初的經濟學領域建模發展到網絡問題，用于仿真自私節點的合作。每個循環的進程從匯聚節點或基站重新調度基于最高的能量級別簇頭，以應答信息到新的簇頭的方式。該方法是基于實用動態源路由協議。協議的另一個重要方法是收益計算的閾值，閾值是0或者1。0代表取決于閾值的收益縮減，1代表取決于閾值的收益增加。與之前的Leach協議比較，基于閾值條件下收益用于發送能量數據，避免整個網絡中的自大化攻擊者。博弈論是簇間能效優化的網絡性能優化方法。

2 吞吐量分析及模型構建

2.1 預備知識

解決相鄰信道傳輸之間的干擾引起的約束問題，利用聯合信道分配和路由器接口分配，將該問題看作是一種跨層網絡效用最大化問題。在一個多信道無線Mesh網絡中，兩個邏輯鏈路(m,n),(m,p)∈L被定義為相互干擾，必須同時滿足如下條件：

(2)一個信道的發送/接收接口是在其他信道的發送/接收接口的干涉范圍內。

2.2 不可轉移收益合作博弈方法

通過建模，博弈了理論有效的改善路由協議性能。兩個參與者的初始狀態是最小化參與者和最大化參與者。定義博弈的每一個參與者和收益函數，量化最小參與者的結果；最小化參與者選擇最小化函數，最大化參與者選擇最大化函數。在使用博弈模型中，兩個參與者是同樣的。所有的路由器聚集到一起形成一個參與者，是路由器參與者的集合;另一個參與者是鏈路的集合，是網絡參與者。路由器參與者集合的博弈移動是執行路由協議。網絡參與者博弈移動是改變網絡拓撲。極大極小策略搜索博弈樹找到極大極小路徑；極大極小值(極大極小結果)是應用到路徑上的代價函數。極大極小值是在博弈的約束內，如果路由器已經被優化，那么，在網絡內無論發生什么，路由器確保不會低于極小極大值。

不可轉移收益合作博弈模型包括4個基本要素：局中人、結果集合、特征函數、以及收益函數。其中，局中人(參與者)是博弈過程中的決策主體，結果集是X，將N的每個非空子集S(即一合作)賦一個集合V(S) ?X的特征函數V。收益函數是局中人從各種策略中能夠獲取的收益。其中，N={1,2,…,n}為全部博弈局中人的集合，S=S1×S2×…×Sn為所有參與者的策略的集合，×為笛卡爾乘積。參與者i的收益是一個測量函數，用ui來表示。U表示所有局中人獲得的收益集合，其中U={u1,u2,…,un}。不可轉移收益模型是一種靜態的博弈模型，在這個模型中，一些參與者合作達到高的收益率。本文采用極大極小合作納什均衡，目標是最大化通信線路的收益，分析極大極小合作納什均衡的存在，證明極大極小合作納什均衡的必要條件。仿真結果顯示，根據合作收益得到的多跳鏈路數據速率，極大極小合作納什均衡優于合作納什均衡方案和納什均衡方案。

2.3 基于合作博弈的聯合簇間公平路由與信道分配模型

聯合簇間公平路由與信道分配對隨機博弈網絡定義如下：

SGN= (N,T,P,F,π,λ,R,U,M0)

每個參與者采用一個統一的隨機分布策略，比如以0.5 的概率選擇一個信道將本文采用的信道分配與隨機分配信道相比較，5個參與者的節點的滿意度明顯高于隨機分配。

剩余能量越小，成為簇頭的概率越?。?/p>

(1)

式中：fi為節點i當前的剩余能量，取值范圍為[0,1]；Ei為節點i在初始狀態時所具有的能量；Ei0為剩余能量因子。

令簇頭間的距離為最佳距離，就可以使得周圍節點密度較大的節點更有可能成為簇頭節點。

Leach協議不考慮節點是否曾經擔任過簇頭，對節點的任務分配極為不公平。對比分析節點的狀態函數，增加節點的節點需求帶寬等參數，構建節點的狀態描述模型：定義ci,j為節點i在某一時刻j的貢獻值衡量函數，Δc為不同的貢獻變化值，而如何選擇最終的簇頭節點，就需要通過博弈論來解決問題。

(2)

(3)

式中：b∈(0,1]為Ui函數中可調的參數，表示節點的帶寬需求的滿意程度,Ui為效用函數；Lw為節點在帶寬w下傳輸數據幀(不包含控制信息)的長度為L；節點i在發送功率p下傳輸數據幀的長度為M；0≤s1≤s2≤…≤s,Si={0,s1，s2，…，s}為參與者i的策略空間。

對于任何兩個節點m，n∈N，存在一條邏輯鏈路(m,n)∈L，定義一個C×1的信道分配向量Xmn，如果節點m與n在第i條頻道進行通信，那么向量Xmn中的第i個元素就被設置為1；否則，將被設置為0。例如，假設C=5，節點m與n在第2條頻道上進行通信，則Xmn=[0 1 0 0 0]T。

為了建立邏輯鏈路(m,n)∈L，路由器節點m與n應該分配通用的信道，即：

Xmn=Xnm,?m,n∈N, (m,n)∈L

(4)

lTXmn=1,?m,n∈N, (m,n)∈L

(5)

式中：l表示一個C×1的信道分配向量，其所有的向量元素均為1?？紤]兩個邏輯鏈路(m,n)，(m,p)∈L，有如下公式：

(6)

對于任何兩個節點m，n∈N，存在一條邏輯鏈路(m,n)∈L，定義一個I×1的接口分配向量Ymn，如果節點m的第i個接口與節點n進行通信，那么向量Ymn中的第i個元素就被設置為1；否則，將被設置為0。例如，假設I=3，節點m使用其第1個接口與節點n進行通信，則Ymn=[1 0 0]T。

為了建立邏輯鏈路(m,n)∈L，路由器節點m與n應該使用它們的一個接口。需要特別注意的是，Ymn≠Ynm。然而，其仍然需要滿足：

lTYmn=1,?m,n∈N,(m,n)∈L

(7)

(8)

?m,n,p∈N;(m,n),(m,p)∈L

信道和接口聯合分配模型可以表示為〈X,Y〉，在模型由信道分配向量Xmn和接口分配向量Ymn共同決定了所有邏輯鏈路(m,n)∈L的分配。

為Mesh傳感器網絡構造收益函數，通過并行迭代的方式獲得網絡信道分配的納什均衡策略，使所有節點的收益函數達到最優化，節點i的收益函數Ui=M是節點i占用帶寬進行直接傳輸所獲得的吞吐量與節點i所獲得的吞吐量之和除以節點i對所占用的協作帶寬wi的支付。

對于聯合合作博弈的模型，由于尋求模型(3)最優解的問題是一個NP難題，本文嘗試用貪婪算法尋求近似最優解。

貪婪算法：設I表示當前帶寬需求低的節點(參與者)構成的集合，若當前最大收益為Ui(j)=maxk∈N,l∈jrl(k)則說明參與者i的帶寬需求高，則將參與者i放入表示帶寬需求高的節點構成的集合j。

每個Mesh節點根據策略Si來選擇效用Us,如果效用函數提高，則博弈過程再次進入循環。同時所有節點依次進行次操作從而達到納什均衡。本文博弈基本算法步驟如下：

(1)初始化，為N個Mesh節點分配信道，所有節點的策略組合記為S0。

(2)迭代過程，節點按照接入網絡的順序依次進行博弈，依次選擇使得效用函數最大的策略，更新所有節點的策略組合為S*。

(3)終止過程，重復迭代過程，直至算法收斂。

3 仿真和性能分析

在前文提出的基于不可轉移收益合作博弈的簇間公平性路由聯合信道分配的基礎上進行仿真實驗，使用仿真工具NS3作為仿真平臺，驗證路由協議的有效性，并對比簇間公平路由、所有Leach路由的吞吐量，對比不同的信道分配策略。設定邊長為800 m的方形監測區域內，隨機放置100個點。假設仿真場景中的無線路由器也是固定不動的，整個仿真網絡參數設置如表1所示。為了方便計算，路由度量參數設定為跳數。算法求解合作博弈函數的最大值。

表1 仿真參數Table 1 Simulation parameters

實驗設定目的地址是由路由器隨機選擇的，隨后通過發送數據分組不斷擴展整個無線網絡的大小，圖1為基于兩種不同路由協議網絡總吞吐量的對比值。其中，網絡吞吐量定義為從源節點發送的在正確的接收時間內目的節點接收到的數據總量。由圖1可以發現，2種路由協議的網絡吞吐量隨著節點數目的增多而發生變化，可以發現簇間公平路由協議的網絡吞吐量明顯高于LEACH協議的網絡吞吐量。

圖2中顯示的是在9個節點的情景中對使用2種不同路由協議的無線路由網絡中每個節點的吞吐量進行對比的結果。在這9個節點中，將第5個節點配置為網關節點，將第7個節點配置為與網關節點相距最遠的節點。每個節點的吞吐量差別在簇間公平路由協議下基本保持相近的狀態。這就說明簇間公平路由協議對于各個節點的公平性考慮得比較全面，每個節點通過簇間公平路由協議都可以得到相應的帶寬，其公平性原則在分配帶寬時顯得尤為重要。

圖2 節點的吞吐量對比Fig.2 Comparing nodes throughput

如圖3所示，在節點(參與者)帶寬需求相同時，比較基于博弈論的算法和基于貪婪算法的系統吞吐量，在參與者的平均帶寬需求大于56 Mbit/s時，存在相互干擾，從而導致網絡的吞吐量呈下降趨勢，基于博弈算法的吞吐量明顯大于基于貪婪算法的吞吐量。

圖3 系統吞吐量與節點平均帶寬需求之間的關系Fig. 3 Relationship of participants’ average business requirements and system throughput

4 結束語

本文根據無線Mesh網絡中路由器分布的公平性原則，使用博弈論方法進行分析后將協議進行了路由協議。實驗結果表明，基于博弈論的無線Mesh網絡路由協議增加了網絡吞吐量，并使得網絡中各個無線節點占有的信道資源基本相近，滿足公平性原則。這些研究可以很好地解決當前Mesh網絡接入協議的問題，為Mesh網絡的普及和應用提供非常重要的作用。

參考文獻：

[1]叢犁,張海林,劉毅,等.基于粒子群優化的協作網絡資源分配的博弈策略[J].吉林大學學報:工學版, 2012, 42(1): 207-212.

Cong Li,Zhang Hai-lin, Liu Yi,et al.Particle swarm optimized game theory for resource allocation in cooperative networks[J].Journal of Jilin University(Engineering and Technology Edition),2012,42(1):207-212.

[2]魯智,顧學邁,李世忠,等.新的速率與功率聯合博弈的分布式控制算法[J].吉林大學學報:工學版, 2008, 38(2): 231-235.

Lu Zhi,Gu Xue-mai, Li Shi-zhong,et al.Novel distributed rate and power on control algorithm based on joint game theoretic approach [J]. Journal of Jilin University(Engineering and Technology Edition), 2008, 38(2): 231-235.

[3]Duarte P B F, Fadlullah Z M, Vasilakos A V, et al. On the partially overlapped channel assignment on wireless mesh network backbone: a game theoretic approach[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(1): 119-127.

[4]Gabale V,Raman B,Dutta P,et al.A classification framework for scheduling algorithms in wireless Mesh networks[J]. IEEE Communications Surveys & Tutorials, 2013, 15(1): 199-222.

[5]Vural S, Wei D, Moessner K. Survey of experimental evaluation studies for wireless Mesh network deployments in urban areas towards ubiquitous internet[J]. IEEE Communications Surveys & Tutorials, 2013, 15(1): 223-239.

[6]Jahanshahi M, Dehghan M, Meybodi M R. LAMR: learning automata based multicast routing protocol for multi-channel multi-radio wireless Mesh networks[J]. Applied Intelligence, 2013, 38(1): 58-77.

[7]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.

[8]Zhang Z, Long K, Wang J. Self-organization paradigms and optimization approaches for cognitive radio technologies: a survey[J]. IEEE Wireless Communications, 2013, 20(2): 36-42.

[9]Wang B, Liu K J. Advances in cognitive radio networks: asurvey[J].IEEE Journal of Selected Topics in Signal Processing, 2011, 5(1):5-23.

[10]Kaabi F, Ghannay S, Filali F. Channel allocation and routing in wireless Mesh networks: a survey and qualitative comparison between schemes[J]. International Journal of Wireless and Mobile Network, 2010, 2(1): 132-151.

[11]de Domenico A, Strinati E C, di Benedetto M G. A survey on MAC strategies for cognitive radio networks[J].Communications Surveys & Tutorials,2012, 14(1): 21-44.

[12]Rezgui J, Hafid A，Gendreau M. Distributed admission control in wireless mesh networks:models,algorithms,and evaluation[J].IEEE Transactions on Vehicular Technology,2010,59(3):1459-1473.