吳 軍,莫偉偉,印新棋,白光偉
南京工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,南京 211816
無線Mesh網(wǎng)絡(luò)(WMNs)是動態(tài)地自組織、自配置的分布式無線接入網(wǎng)絡(luò)。WMNs由Mesh路由器(mesh routers)和客戶端節(jié)點(client nodes)兩種類型節(jié)點組成[1],在混合結(jié)構(gòu)的WMNs中,Mesh路由器移動性較小,構(gòu)成WMNs的骨干結(jié)構(gòu);而無線Mesh客戶端節(jié)點中具有大量移動節(jié)點,其中多數(shù)節(jié)點仍然有能源、帶寬等限制,本文的策略正是針對混合結(jié)構(gòu)無線Mesh網(wǎng)絡(luò)中的移動客戶端節(jié)點,此外,本文的研究前提是面向任意時刻總是連通的無線多跳網(wǎng)絡(luò)[2]。
機會路由[3]利用了無線網(wǎng)絡(luò)的廣播特性。網(wǎng)絡(luò)中節(jié)點覆蓋范圍內(nèi)的鄰居節(jié)點都參與監(jiān)聽接收,均有機會加入轉(zhuǎn)發(fā)候選集,通過多跳轉(zhuǎn)發(fā)完成數(shù)據(jù)傳輸。其中,ExOR是典型機會路由協(xié)議。相對于傳統(tǒng)路由協(xié)議,采用機會路由協(xié)議具有更大的吞吐量。理論上網(wǎng)絡(luò)中的節(jié)點均是理性節(jié)點,愿意參與合作轉(zhuǎn)發(fā)。但是在實際應(yīng)用中,移動節(jié)點可能來自很多方面,由于該節(jié)點性能、能源等原因,節(jié)點表現(xiàn)出自私性,尤其是拒絕為其他節(jié)點轉(zhuǎn)發(fā),但是其仍然使用網(wǎng)絡(luò)發(fā)送與接收數(shù)據(jù)包。這種不參與合作轉(zhuǎn)發(fā)的自私節(jié)點將會極大降低機會路由的性能。
本文針對機會路由中的節(jié)點的自私行為,從能量、成功轉(zhuǎn)發(fā)概率以及收益方面考慮,定義一種度量鄰居節(jié)點合作水平的合作度評估函數(shù),并建立基于合作度評估函數(shù)的寬容針鋒相對策略節(jié)點重復(fù)博弈模型(Cooperation degree Generous Tit-for-Tat,CGTFT)。模擬實驗表明該機制能夠有效抑制節(jié)點自私行為,激勵節(jié)點參與合作轉(zhuǎn)發(fā),提高網(wǎng)絡(luò)性能。
針對機會路由的相關(guān)研究主要有:文獻[3]提出的ExOR以及文獻[4]中SOAR協(xié)議都是將無線信道的廣播特性利用到路由轉(zhuǎn)發(fā)中;Biswas等人文中最早提出機會路由概念,利用轉(zhuǎn)發(fā)候選集來提高網(wǎng)絡(luò)吞吐量。文獻[5]中提出MORE協(xié)議,將網(wǎng)絡(luò)編碼結(jié)合到機會路由中,進一步改善了網(wǎng)絡(luò)吞吐量。本文的路由算法基于ExOR協(xié)議,提出的機會路由重復(fù)博弈激勵機制。
針對機會路由中的節(jié)點不合作與自私行為,當前研究主要有以下幾種解決方法:文獻[6]中采用的基于聲譽的方法激勵自私節(jié)點,聲譽方法需要根據(jù)節(jié)點的歷史交易行為,綜合考慮直接信譽以及第三方信息對節(jié)點行為作出最終判斷,目前聲譽機制中監(jiān)測的不準確性是主要問題。在文獻[7]中運用VGG機制鼓勵節(jié)點匯報轉(zhuǎn)發(fā)所需要的真實成本,還給予一定的額外報酬,實現(xiàn)對自私節(jié)點的激勵,該策略的局限是需要單獨第三方執(zhí)行清算運算。文獻[8]中,提出節(jié)點公平競價激勵機制來激勵網(wǎng)絡(luò)中自私節(jié)點,并且模型化競價過程為一個競價博弈,存在貝葉斯納什均衡使博弈達到平衡。
本文主要針對機會路由中節(jié)點自私問題,設(shè)計鄰居節(jié)點合作度評估函數(shù),并結(jié)合寬容針鋒相對思想[9],建立CGTFT重復(fù)博弈策略,激勵網(wǎng)絡(luò)中節(jié)點參與合作。通過重復(fù)博弈策略,迫使鄰居節(jié)點考慮未來收益,積極參與合作轉(zhuǎn)發(fā),從而提高網(wǎng)絡(luò)的性能。
在機會路由利用廣播特性進行路由發(fā)現(xiàn)階段,網(wǎng)絡(luò)中節(jié)點通過信息交互獲得其鄰居節(jié)點以及相應(yīng)的鏈路情況。此時,自私節(jié)點為了避免轉(zhuǎn)發(fā)鄰居數(shù)據(jù)包,會有多種策略來使自己逃避轉(zhuǎn)發(fā)工作。根據(jù)節(jié)點的行為,自私節(jié)點分為以下幾類[10-11]:(1)節(jié)點參與網(wǎng)絡(luò)服務(wù),但是不愿轉(zhuǎn)發(fā)數(shù)據(jù)包。典型策略是丟棄來自其他節(jié)點的數(shù)據(jù)包或者延遲至空閑期轉(zhuǎn)發(fā)。節(jié)點不參與轉(zhuǎn)發(fā)工作將會節(jié)省大量能量。(2)不參與路由服務(wù),在ExOR路由協(xié)議中,自私節(jié)點阻止網(wǎng)絡(luò)把自己作為中繼節(jié)點,自私節(jié)點可以直接忽視其他節(jié)點的路由請求,不參與鏈路狀態(tài)應(yīng)答。
上述不合作的自私行為將導(dǎo)致機會路由候選集中節(jié)點減少,網(wǎng)絡(luò)吞吐量下降。所以需要一種機制來激勵鄰居節(jié)點參與合作轉(zhuǎn)發(fā)。
首先作如下假設(shè):
(1)網(wǎng)絡(luò)中節(jié)點均為理性自私節(jié)點。
(2)網(wǎng)絡(luò)為離散時間模型,每個時隙t內(nèi)均為一次博弈過程,博弈策略相同。
(3)整個網(wǎng)絡(luò)G有N個節(jié)點隨機分布,且節(jié)點僅有有限能量,初始能量為Ei。
(4)假設(shè)傳輸數(shù)據(jù)包傳輸失敗主要是節(jié)點的自私和不合作所致。
數(shù)據(jù)從源節(jié)點S發(fā)送至目的節(jié)點D,需要一個或多個中間節(jié)點概率性轉(zhuǎn)發(fā)。假設(shè)節(jié)點 j根據(jù)自身情況決定對數(shù)據(jù)包是轉(zhuǎn)發(fā)還是丟棄,節(jié)點i將給予r的獎勵來激勵節(jié)點 j轉(zhuǎn)發(fā)數(shù)據(jù),同時節(jié)點 j付出s能源來完成轉(zhuǎn)發(fā)。上述情況中,時隙博弈相當于囚徒困境,節(jié)點在博弈中追求利益最大化,最終選擇(0,0)策略達到納什均衡。時隙博弈收益和策略見表1。
表1 博弈收益和策略
機會路由中,每個節(jié)點由于能源等限制,趨向于不參與合作,選擇自私,單次博弈無法激勵自私節(jié)點。實際網(wǎng)絡(luò)中,所有節(jié)點都周期性選擇策略,這樣對于所有節(jié)點,形成無限重復(fù)博弈;當博弈結(jié)束時間無法預(yù)期,節(jié)點將評估其采取的策略對其將來收益的影響。
假設(shè)一個節(jié)點接受轉(zhuǎn)發(fā)概率為 f,f=0表示拒絕轉(zhuǎn)發(fā),f=1表示接受所有轉(zhuǎn)發(fā)請求。任意一個節(jié)點用i表示,則-i表示博弈對方節(jié)點。若時隙tn節(jié)點收益為:
則重復(fù)博弈收益函數(shù)為:
當經(jīng)過重復(fù)博弈后,網(wǎng)絡(luò)中節(jié)點都趨向合作,采取合作策略,接受轉(zhuǎn)發(fā)請求,則節(jié)點i重復(fù)博弈后的收益函數(shù)為:
由于機會路由中移動節(jié)點動態(tài)拓撲及鏈路的不確定性,數(shù)據(jù)會傳輸失敗及重傳。定義節(jié)點i成功轉(zhuǎn)發(fā)數(shù)據(jù)包為pis(t),接收數(shù)據(jù)包為 pir(t),則該節(jié)點時隙t時數(shù)據(jù)包成功轉(zhuǎn)發(fā)概率為:
在面對節(jié)點的路由請求時,自私節(jié)點在博弈時有下列傾向:其一,自私節(jié)點更愿意選擇轉(zhuǎn)發(fā)成功率高以及能量高的鄰居節(jié)點作為備選節(jié)點來轉(zhuǎn)發(fā)數(shù)據(jù)包。其二,鄰居節(jié)點的合作水平與其獲得的效益相關(guān),獲得的效益越大,那么其接受請求的概率也越高。為了選出趨向合作的下一跳節(jié)點,本文定義合作度評估函數(shù)(以下簡稱合作度),見公式(5):
針鋒相對TFT[12]是重復(fù)博弈的一個典型策略。思想如下:博弈雙方節(jié)點i和 j,在某一時隙節(jié)點i的策略總是參照上一個時隙對方節(jié)點 j采用的策略;若 j選擇轉(zhuǎn)發(fā),i也選擇轉(zhuǎn)發(fā)策略,若 j拒絕,i亦拒絕。該策略中,節(jié)點一旦進入懲罰期,無法恢復(fù)合作狀態(tài)。而GTFT策略是在TFT策略的基礎(chǔ)上添加遺忘因子g來幫助節(jié)點恢復(fù)合作。
本文結(jié)合合作度評估函數(shù)與GTFT思想,建立CGTFT博弈激勵策略,以鄰居節(jié)點的合作度作為博弈判斷的標準。在博弈中,添加遺忘因子g到策略中,使節(jié)點具有恢復(fù)合作機制,模型化基于合作度評估函數(shù)的CGTFT策略如下所示,其中表示鄰居節(jié)點的合作度評價函數(shù),m=[(1 -p)g]且假定為偶數(shù):
當網(wǎng)絡(luò)中每個節(jié)點均采用CGTFT策略,若節(jié)點i單方面改變其接受請求概率,則其合作度評估函數(shù)也會隨之改變,令節(jié)點合作度評估函數(shù)為 p,那么其對手節(jié)點根據(jù)CGTFT策略做出響應(yīng):(1)對節(jié)點行為輕微程度的偏離,p≥1-g,將會容忍,其正常轉(zhuǎn)發(fā)數(shù)據(jù);(2)對節(jié)點行為偏離程度較大的節(jié)點,p<1-g,定義為不合作,其對手將會調(diào)整合作度至 p+g。表2為單次不合作的博弈策略。
表2 CGTFT單次不合作博弈策略
根據(jù)公式(2)得,CGTFT策略中單次不合作時,節(jié)點i收益函數(shù):
經(jīng)過CGTFT策略激勵后,重復(fù)博弈趨向合作平衡時需滿足:
因為g>0且0<δ<1,上式可轉(zhuǎn)換為:
因為上式兩括號內(nèi)多項式均大于0,所以CGTFT激勵策略激勵節(jié)點達到合作平衡的條件是:
假設(shè)機會路由中所有節(jié)點均遵從CGTFT博弈激勵策略,若符合平衡臨界條件r/s>H,節(jié)點i以任意概率接受請求,0<p<1,那么節(jié)點單方面改變獲得的收益都小于采取合作獲得的收益,最終節(jié)點將趨向于選擇合作,達到納什均衡,起到抑制自私行為的目的。
在CGTFT策略中,在滿足該策略平衡臨界條件下,遺忘因子g的降低以及貼現(xiàn)因子δ的增加都有利于抑制自私行為,從而促使各節(jié)點趨向于合作。證明如下:在公式(8)中,對ECGTFT求g偏導(dǎo),在r,s,p,δ等參數(shù)不變情況下,降低g導(dǎo)致ECGTFT增加,即自私行為受到懲罰將增加;對ECGTFT求δ偏導(dǎo),在r,s,p,g等參數(shù)不變情況下,增加δ導(dǎo)致ECGTFT的增加,即采取自私行為所受懲罰增大。在CGTFT中,除了貼現(xiàn)因子δ外,遺忘因子g對自私行為所受懲罰有重要影響,g的大小影響節(jié)點采取自私行為后恢復(fù)合作狀態(tài)所需要的單階段博弈次數(shù),g越小,恢復(fù)合作所需要的博弈次數(shù)越多,遭受的懲罰期越長。
本文的博弈算法是網(wǎng)絡(luò)中數(shù)據(jù)包發(fā)送節(jié)點與鄰居節(jié)點之間,通過CGTFT策略進行兩兩博弈的過程,博弈的判斷標準是本文提出的鄰居節(jié)點合作度評價函數(shù),網(wǎng)絡(luò)中所有節(jié)點都將周期性地選擇策略,整體上看,形成一個重復(fù)博弈的過程。其算法的具體流程描述如下所示[13-14]:
(1)初始化參數(shù)。
(2)源點向鄰居節(jié)點廣播發(fā)送路由請求,以及評估各鄰居節(jié)點的合作度。
(3)對比ExOR候選集中所有節(jié)點的合作度,將合作度低于閾值 pthreshold節(jié)點排除出候選集,然后選取ETX值最大的節(jié)點為下一跳轉(zhuǎn)發(fā)節(jié)點。
(4)對于該節(jié)點采取何種行為,根據(jù)本文的CGTFT策略可知,該源點即對手在上個時隙合作度是 p,若p≥1-g,則容忍行為偏離,執(zhí)行轉(zhuǎn)發(fā)策略,并跳轉(zhuǎn)(6)。
(5)若 p<1-g,則定義該節(jié)點為自私節(jié)點,下個時隙該節(jié)點的對手節(jié)點將采取 p+g的合作度執(zhí)行策略,后面過程重復(fù)CGTFT策略。
(6)重復(fù)(2)到(6)步驟,直到數(shù)據(jù)到達目的節(jié)點,算法結(jié)束。
本文運用NS2進行仿真實驗,其中MAC層協(xié)議采用IEEE802.11協(xié)議[15]。機會路由ExOR協(xié)議中節(jié)點隨機分布,節(jié)點都遵循相同的博弈策略。網(wǎng)絡(luò)中節(jié)點運動按照Random Waypoint Model方式移動。規(guī)定在網(wǎng)絡(luò)生命周期內(nèi),節(jié)點進入懲罰期,節(jié)點可能由于能量耗盡或者過于自私原因,在本文的CGTFT策略激勵下,節(jié)點仍然無法重建,恢復(fù)合作,定義該節(jié)點死亡。其他仿真參數(shù)如表3所示。
表3 仿真參數(shù)
本文選擇的性能評價指標是網(wǎng)絡(luò)生命周期的節(jié)點數(shù)變化情況、網(wǎng)絡(luò)總能耗變化情況以及不同比例自私節(jié)點情況下的吞吐量變化情況。
為了證實本文提出的CGTFT策略對節(jié)點自私行為的激勵效果,本文仿真了r/s=4,g=0.01,δ=0.6時策略性能比較[16]。圖1說明的是隨著博弈輪數(shù)的增加,網(wǎng)絡(luò)生命周期中的節(jié)點數(shù)變化情況。從圖1可知,隨著博弈輪數(shù)的增加,本文的CGTFT重復(fù)博弈策略的節(jié)點死亡數(shù)低于囚徒困境(TFT)策略,尤其在博弈前期,TFT策略中死亡節(jié)點增速明顯高于本文的CGTFT策略。原因有兩個:其一,本文在合作度評估函數(shù)中具有能量模型,剩余能量對節(jié)點的合作度評估有較大的影響,避免能耗不均衡和部分節(jié)點能量快速耗盡,一定程度上延長了節(jié)點生命時間。其二,本文CGTFT策略中提供合作重建機制,其策略中具有遺忘因子g,節(jié)點進入懲罰期后,經(jīng)過一定周期,節(jié)點會恢復(fù)合作。
圖1 網(wǎng)絡(luò)生命周期
圖2說明的是網(wǎng)絡(luò)總能量消耗情況。從圖2可知,與TFT策略相比,本文CGTFT策略下的能耗增加總體比較平緩,并且總能耗也低于前者。這是因為在本文的鄰居節(jié)點合作度評估函數(shù)的定義中,考慮了成功轉(zhuǎn)發(fā)率以及能量因素,在路由選擇時,節(jié)點會選擇合作度高的節(jié)點轉(zhuǎn)發(fā),一方面其成功轉(zhuǎn)發(fā)率高,減少傳輸失敗再重傳的能耗;另一方面能量模型可以均衡節(jié)點能源消耗,盡量避免節(jié)點能耗過低導(dǎo)致的傳輸失敗,繼而再重傳的耗能。
圖2 網(wǎng)絡(luò)總能耗
圖3給出的是在不同比例自私節(jié)點情況下,網(wǎng)絡(luò)吞吐量累計分布情況。從100個節(jié)點中隨機選取匹配發(fā)送節(jié)點和目的節(jié)點,統(tǒng)計發(fā)送數(shù)據(jù)包100次的結(jié)果,仿真比較以下三種情況的吞吐量累計分布:ExOR協(xié)議沒添加激勵策略時,網(wǎng)絡(luò)中分別存在20%和40%自私節(jié)點的吞吐量分布情況以及添加本文提出的CGTFT激勵策略時的吞吐量分布情況。仿真重復(fù)實驗5次,最終結(jié)果取平均值。如圖3所示,當自私節(jié)點比例增加到40%。曲線左移,吞吐量較低,所占比例明顯增多。而當加入本文的CGTFT激勵機制后,節(jié)點選擇合作度較高的節(jié)點來轉(zhuǎn)發(fā)。CGTFT激勵策略下網(wǎng)絡(luò)吞吐量和20%和40%自私節(jié)點時候相比,較高吞吐量所占比例有明顯提升;其中,在CGTFT激勵策略下,超過90%的鏈路吞吐量達到52數(shù)據(jù)包每秒。而無激勵時吞吐量分別為30和41個包每秒,主要因為合作度高的節(jié)點轉(zhuǎn)發(fā)成功率較高,而且均衡節(jié)點能量消耗,整體上提高了網(wǎng)絡(luò)性能。
圖3 吞吐量累計分布
本文提出了一種基于鄰居節(jié)點合作度評估函數(shù)的CGTFT重復(fù)博弈模型。對于網(wǎng)絡(luò)中的理性節(jié)點,從節(jié)點剩余能量,成功轉(zhuǎn)發(fā)概率角度設(shè)計了合作度評估函數(shù)概念,然后通過CGTFT重復(fù)博弈策略進行博弈,對網(wǎng)絡(luò)中參與合作轉(zhuǎn)發(fā)的節(jié)點給予一定收益,對自私不合作節(jié)點給予一定周期的懲罰,并添加了遺忘因子,對進入懲罰期的節(jié)點進行合作重建。仿真表明,該激勵機制能夠有效迫使網(wǎng)絡(luò)中自私節(jié)點參與合作,提高吞吐量以及網(wǎng)絡(luò)性能。
:
[1]Akyildiz I F,Wang X.A survey on wireless mesh networks[J].IEEE Communications Magazine,2005,43(9).
[2]田克,張寶賢,馬建,等.無線多跳網(wǎng)絡(luò)中的機會路由[J].軟件學(xué)報,2010,21(10):2542-2553.
[3]Biswas S,Morris R.ExOR:opportunistic multi-hop routing for wireless networks[J].ACM Special Interest Group on Data Communication,2005,35(4):133-144.
[4]Rozner E,Seshadri J,Mehta Y,et al.SOAR:Simple Opportunistic Adaptive Routing protocol for Wireless Mesh Networks[J].IEEE TransactionsonMobileComputing,2009,8(12):1622-1635.
[5]Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing[J].ACM Special Interest Group on Data Communication,2007,37(4):169-180.
[6]Chen K,Nahrstedt K.iPass:an incentive compatible auction scheme to enable packet forwarding service in MANET[C]//InternationalConferenceonDistributedComputing Systems,2004:534-542.
[7]Anderegg L,Eidenbenz S.Ad hoc-VCG:a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents[C]//InternationalConference on Mobile Computing and Networking,2003:245-259.
[8]Han Z,Pandana C,Liu K J,et al.A self-learning repeated game framework for optimizing packet forwarding networks[C]//Wireless Communications and Networking Conference,2005:2131-2136.
[9]Wu F,Gong K,Zhang T,et al.COMO:a game-theoretic approach for joint multirate opportunistic routing and forwarding in non-cooperative wireless networks[J].IEEE Transactions on Wireless Communications,2015,14(2):948-959.
[10]Dapeng Q U,Wang X,Huang M,et al.Selfish node detection and incentive mechanism in mobile P2P networks:selfish node detection and incentive mechanism in mobile P2P networks[J].Journal of Software,2014,24(4):887-899.
[11]Zhang K,Wang R,Qian D,et al.AIM:an auction incentive mechanism in wireless networks with opportunistic routing[C]//Computational Science and Engineering,2010:28-33.
[12]Srivastava V,Neel J,Mackenzie A B,et al.Using game theory to analyze wireless ad hoc networks[J].Communications Surveys&Tutorials,2005,7(4):46-56.
[13]Wu F,Chen T,Zhong S,et al.A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks[J].IEEE Transactions on Wireless Communications,2013,12(4):1573-1583.
[14]Froushani M H,Khalaj B H,Vakilinia S,et al.A novel approach to incentive-based cooperation in wireless ad hoc networks[C]//international Conference on Telecommunications,2011:78-83.
[15]Yan L,Hailes S,Capra L,et al.Analysis of packet relaying models and incentive strategies in wireless ad hoc networkswithgametheory[C]//AdvancedInformation Networking and Applications,2008:1062-1069.
[16]Sun Yuxing.On incentive strategies for trust recommendations in wireless ad hoc networks with probability game[J].Computer Science,2011,38(4):65-71.