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

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

0 引 言

無線Mesh網(wǎng)(Wireless Mesh networks，WMN)結(jié)合了無線局域網(wǎng)(Wireless LAN,WLAN)和無線移動自組織網(wǎng)絡(luò)(Ad-hoc網(wǎng)絡(luò))的優(yōu)點(diǎn)，是針對特定業(yè)務(wù)需求而出現(xiàn)的一種新型無線網(wǎng)絡(luò)技術(shù)[1]。其應(yīng)用包括了家庭寬帶網(wǎng)絡(luò)(Home network)、區(qū)域和城網(wǎng)絡(luò)(WMAN)、公共緊急通信、戰(zhàn)場通信等[2]。由于具有傳輸速率高、架設(shè)方便、覆蓋范圍靈活以及較強(qiáng)的容錯能力等優(yōu)點(diǎn)，無線Mesh網(wǎng)絡(luò)被認(rèn)為是自組織無線網(wǎng)和自動可配置無線網(wǎng)中最有發(fā)展?jié)摿Φ慕M網(wǎng)技術(shù)之一[3]。

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

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

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

1 相關(guān)工作

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

信道對競爭和節(jié)點(diǎn)自身之間的信道分配方案影響越來越大，是導(dǎo)致無線網(wǎng)絡(luò)性能下降的最主要原因之一。雖然無線網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都設(shè)置有多個射頻通信接口，但只有當(dāng)連接的接口和信道保持通信時，每個接口才對應(yīng)不同的信道。

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

博弈論廣泛應(yīng)用于經(jīng)濟(jì)學(xué)領(lǐng)域，從最初的經(jīng)濟(jì)學(xué)領(lǐng)域建模發(fā)展到網(wǎng)絡(luò)問題，用于仿真自私節(jié)點(diǎn)的合作。每個循環(huán)的進(jìn)程從匯聚節(jié)點(diǎn)或基站重新調(diào)度基于最高的能量級別簇頭，以應(yīng)答信息到新的簇頭的方式。該方法是基于實(shí)用動態(tài)源路由協(xié)議。協(xié)議的另一個重要方法是收益計(jì)算的閾值，閾值是0或者1。0代表取決于閾值的收益縮減，1代表取決于閾值的收益增加。與之前的Leach協(xié)議比較，基于閾值條件下收益用于發(fā)送能量數(shù)據(jù)，避免整個網(wǎng)絡(luò)中的自大化攻擊者。博弈論是簇間能效優(yōu)化的網(wǎng)絡(luò)性能優(yōu)化方法。

2 吞吐量分析及模型構(gòu)建

2.1 預(yù)備知識

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

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

2.2 不可轉(zhuǎn)移收益合作博弈方法

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

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

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

聯(lián)合簇間公平路由與信道分配對隨機(jī)博弈網(wǎng)絡(luò)定義如下：

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

每個參與者采用一個統(tǒng)一的隨機(jī)分布策略，比如以0.5 的概率選擇一個信道將本文采用的信道分配與隨機(jī)分配信道相比較，5個參與者的節(jié)點(diǎn)的滿意度明顯高于隨機(jī)分配。

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

(1)

式中：fi為節(jié)點(diǎn)i當(dāng)前的剩余能量，取值范圍為[0,1]；Ei為節(jié)點(diǎn)i在初始狀態(tài)時所具有的能量；Ei0為剩余能量因子。

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

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

(2)

(3)

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

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

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

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)

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

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

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

(7)

(8)

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

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

為Mesh傳感器網(wǎng)絡(luò)構(gòu)造收益函數(shù)，通過并行迭代的方式獲得網(wǎng)絡(luò)信道分配的納什均衡策略，使所有節(jié)點(diǎn)的收益函數(shù)達(dá)到最優(yōu)化，節(jié)點(diǎn)i的收益函數(shù)Ui=M是節(jié)點(diǎn)i占用帶寬進(jìn)行直接傳輸所獲得的吞吐量與節(jié)點(diǎn)i所獲得的吞吐量之和除以節(jié)點(diǎn)i對所占用的協(xié)作帶寬wi的支付。

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

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

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

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

(2)迭代過程，節(jié)點(diǎn)按照接入網(wǎng)絡(luò)的順序依次進(jìn)行博弈，依次選擇使得效用函數(shù)最大的策略，更新所有節(jié)點(diǎn)的策略組合為S*。

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

3 仿真和性能分析

在前文提出的基于不可轉(zhuǎn)移收益合作博弈的簇間公平性路由聯(lián)合信道分配的基礎(chǔ)上進(jìn)行仿真實(shí)驗(yàn)，使用仿真工具NS3作為仿真平臺，驗(yàn)證路由協(xié)議的有效性，并對比簇間公平路由、所有Leach路由的吞吐量，對比不同的信道分配策略。設(shè)定邊長為800 m的方形監(jiān)測區(qū)域內(nèi)，隨機(jī)放置100個點(diǎn)。假設(shè)仿真場景中的無線路由器也是固定不動的，整個仿真網(wǎng)絡(luò)參數(shù)設(shè)置如表1所示。為了方便計(jì)算，路由度量參數(shù)設(shè)定為跳數(shù)。算法求解合作博弈函數(shù)的最大值。

表1 仿真參數(shù)Table 1 Simulation parameters

實(shí)驗(yàn)設(shè)定目的地址是由路由器隨機(jī)選擇的，隨后通過發(fā)送數(shù)據(jù)分組不斷擴(kuò)展整個無線網(wǎng)絡(luò)的大小，圖1為基于兩種不同路由協(xié)議網(wǎng)絡(luò)總吞吐量的對比值。其中，網(wǎng)絡(luò)吞吐量定義為從源節(jié)點(diǎn)發(fā)送的在正確的接收時間內(nèi)目的節(jié)點(diǎn)接收到的數(shù)據(jù)總量。由圖1可以發(fā)現(xiàn)，2種路由協(xié)議的網(wǎng)絡(luò)吞吐量隨著節(jié)點(diǎn)數(shù)目的增多而發(fā)生變化，可以發(fā)現(xiàn)簇間公平路由協(xié)議的網(wǎng)絡(luò)吞吐量明顯高于LEACH協(xié)議的網(wǎng)絡(luò)吞吐量。

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

圖2 節(jié)點(diǎn)的吞吐量對比Fig.2 Comparing nodes throughput

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

圖3 系統(tǒng)吞吐量與節(jié)點(diǎn)平均帶寬需求之間的關(guān)系Fig. 3 Relationship of participants’ average business requirements and system throughput

4 結(jié)束語

本文根據(jù)無線Mesh網(wǎng)絡(luò)中路由器分布的公平性原則，使用博弈論方法進(jìn)行分析后將協(xié)議進(jìn)行了路由協(xié)議。實(shí)驗(yàn)結(jié)果表明，基于博弈論的無線Mesh網(wǎng)絡(luò)路由協(xié)議增加了網(wǎng)絡(luò)吞吐量，并使得網(wǎng)絡(luò)中各個無線節(jié)點(diǎn)占有的信道資源基本相近，滿足公平性原則。這些研究可以很好地解決當(dāng)前Mesh網(wǎng)絡(luò)接入?yún)f(xié)議的問題，為Mesh網(wǎng)絡(luò)的普及和應(yīng)用提供非常重要的作用。

參考文獻(xiàn)：

[1]叢犁,張海林,劉毅,等.基于粒子群優(yōu)化的協(xié)作網(wǎng)絡(luò)資源分配的博弈策略[J].吉林大學(xué)學(xué)報:工學(xué)版, 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]魯智,顧學(xué)邁,李世忠,等.新的速率與功率聯(lián)合博弈的分布式控制算法[J].吉林大學(xué)學(xué)報:工學(xué)版, 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.