基于重復(fù)博弈的Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)發(fā)策略分析

譚冕，何世彪，宋波，朱國慶，張暉

（重慶通信學(xué)院，重慶400035）

基于重復(fù)博弈的Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)發(fā)策略分析

譚冕，何世彪，宋波，朱國慶，張暉

（重慶通信學(xué)院，重慶400035）

在無線Ad Hoc網(wǎng)絡(luò)中，源節(jié)點(diǎn)和目的節(jié)點(diǎn)互相通信需要中繼節(jié)點(diǎn)的支持，但節(jié)點(diǎn)是理性的，所以可能會拒絕轉(zhuǎn)發(fā)請求。這里就節(jié)點(diǎn)之間存在的合作問題，對針鋒相對策略、冷酷策略、完全合作策略、寬恕的針鋒相對策略、嚴(yán)厲針鋒相對策略進(jìn)行了納什均衡分析。理論分析可知，針鋒相對策略相對于其他策略更具優(yōu)勢，因?yàn)樗拈撝递^低。

無線Ad Hoc網(wǎng)絡(luò)；重復(fù)博弈；納什均衡；轉(zhuǎn)發(fā)策略

0 引言

具有無中心、自組織、動態(tài)、多跳等特點(diǎn)的無線Ad Hoc網(wǎng)絡(luò)，由于節(jié)點(diǎn)傳輸距離的有限性，無線Ad Hoc網(wǎng)絡(luò)需要節(jié)點(diǎn)間的合作才能確保數(shù)據(jù)包得到成功傳遞[1]。在很多情況下，理性的參與者受到自身存儲資源和能量資源等的限制，為了增加存活時(shí)間，將采取損害網(wǎng)絡(luò)性能的行為[2]。顯然，即便只存在一些自私節(jié)點(diǎn)的無線自組網(wǎng)的系統(tǒng)，也會極大地降低網(wǎng)絡(luò)的整體性能。

本文首先對系統(tǒng)模型進(jìn)行了分析，具體包括網(wǎng)絡(luò)的基本假設(shè)、博弈模型假設(shè)，再對多種轉(zhuǎn)發(fā)策略的納什均衡和節(jié)點(diǎn)收益進(jìn)行了分析，最后得到了滿足納什均衡的條件。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)基本假設(shè)

本文建立的Ad Hoc網(wǎng)絡(luò)存在如下假設(shè)：

（1）網(wǎng)絡(luò)中存在n個(gè)具有理性的節(jié)點(diǎn)，網(wǎng)絡(luò)模型如圖1所示。

（2）系統(tǒng)時(shí)間是由一系列的協(xié)作時(shí)隙t構(gòu)成，在每個(gè)時(shí)隙，各節(jié)點(diǎn)都有數(shù)據(jù)包發(fā)送。

（3）為分析方便起見，特假設(shè)任意源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間都不能直接通信，必須經(jīng)過中間節(jié)點(diǎn)，且到目的節(jié)點(diǎn)的跳數(shù)基本相同。

（4）所有的數(shù)據(jù)包大小相等，各節(jié)點(diǎn)接收數(shù)據(jù)包消耗的能量相同，轉(zhuǎn)發(fā)數(shù)據(jù)包消耗同等大小的能量。

圖1 網(wǎng)絡(luò)模型

1.2 博弈模型假設(shè)

1.2.1 博弈要素的定義

博弈的三要素是：參與者、策略空間、效用函數(shù)。

參與者：分布在當(dāng)前Ad Hoc網(wǎng)絡(luò)中理性的節(jié)點(diǎn)，都是博弈的參與者，那么它們的集合可以表示為N=(1,2,…,n)。

策略空間：博弈模型中的所有參與者都有一組可供選擇的策略集合。在本文中有兩種具體策略：合作，轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)包；不合作，不轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)包。

效用函數(shù)：即參與者采取某一策略所獲得的收益，下述將定義博弈相關(guān)參數(shù)，并滿足囚徒困境博弈的設(shè)定。

1.2.2 階段博弈假設(shè)

如圖2所示，源節(jié)點(diǎn)A和目的節(jié)點(diǎn)C無法直接通信，故節(jié)點(diǎn)A需要通過中間節(jié)點(diǎn)B的轉(zhuǎn)發(fā)。

圖2 節(jié)點(diǎn)轉(zhuǎn)發(fā)模型

在博弈中，用c代表節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)的能量消耗，用b代表一個(gè)節(jié)點(diǎn)的數(shù)據(jù)包被其他節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)獲得的利益[3]。當(dāng)博弈雙方的策略選擇都是合作的時(shí)候，效益為（b-c）。如果一個(gè)節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)上采取不合作，而其他節(jié)點(diǎn)是合作的話，那么自私節(jié)點(diǎn)能夠得到b的效益而合作節(jié)點(diǎn)的效益為-c。這是因?yàn)樽运焦?jié)點(diǎn)的數(shù)據(jù)包被其他合作節(jié)點(diǎn)轉(zhuǎn)發(fā)，但是自私節(jié)點(diǎn)并沒有轉(zhuǎn)發(fā)合作節(jié)點(diǎn)的數(shù)據(jù)包。如果雙方節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)上都采取不合作的態(tài)度，那么他們的策略收益為（0,0），這是因?yàn)楣?jié)點(diǎn)都沒有收益和消耗能量。

基于上述的收益和消耗，建立如表1所示的囚徒困境收益矩陣[4]。

表1 博弈策略收益

無論節(jié)點(diǎn)j選擇什么策略，對于節(jié)點(diǎn)i而言，選擇不合作策略是最好的，所以階段博弈的納什均衡點(diǎn)是雙方節(jié)點(diǎn)同時(shí)選擇不合作策略。然而雙方都采取合作策略的收益是最高的，所以在這個(gè)收益矩陣中，納什均衡點(diǎn)并不帕累托占優(yōu)。原因就在于網(wǎng)絡(luò)中的節(jié)點(diǎn)都是獨(dú)立和自私的，博弈的雙方不知道對方的策略，如果節(jié)點(diǎn)i選擇了合作，而節(jié)點(diǎn)j選擇了不合作，那么節(jié)點(diǎn)i將會獲得最差的收益。所以，自私的節(jié)點(diǎn)通常會選擇獲得最好結(jié)果的策略而不冒險(xiǎn)獲得最差收益[5]。

在囚徒困境的內(nèi)容設(shè)定上，必須滿足以下兩個(gè)條件：

該囚徒困境的收益矩陣如表1所示。

2 重復(fù)博弈的納什均衡和節(jié)點(diǎn)收益

由于節(jié)點(diǎn)當(dāng)前行為會對后續(xù)的博弈階段造成影響，所以與鄰居節(jié)點(diǎn)間的多次交互將不是相互獨(dú)立的階段博弈，而形成重復(fù)策略博弈[6]。下面研究重復(fù)博弈中的重要概念——納什均衡。

定義1納什均衡（Nash Equilibrium，NE）[7]策略向量為一個(gè)納什均衡向量，假如對于所有的參與者都有以下式子成立：

意味著在一個(gè)已達(dá)到納什均衡的策略中，沒有任何一個(gè)理性的參與者能夠通過單方面的策略改變而獲得收益。如表1的囚徒困境所示，在單次的階段博弈中，對于參與者M(jìn)，N而言，雙方都選擇了不合作策略，盡管是納什均衡解，但并不是全局最優(yōu)點(diǎn)，為了讓理性的參與者合作，通常有兩種辦法：博弈的次數(shù)為無限次；博弈雙方都相信對方不會背叛自己。

其中，P為某節(jié)點(diǎn)階段博弈采取的策略概率；i和j為博弈的節(jié)點(diǎn)；表示的是節(jié)點(diǎn)i在第tn個(gè)時(shí)隙的效用值。

假設(shè)重復(fù)博弈的時(shí)隙總長度為T，節(jié)點(diǎn)在各自時(shí)隙內(nèi)的策略都會被觀察到。根據(jù)重復(fù)博弈的原理，節(jié)點(diǎn)的收益會在每一個(gè)階段有δ（0＜δ＜1）的折扣率，它代表節(jié)點(diǎn)的歷史行為對未來利益的影響，若其值越大則表示節(jié)點(diǎn)更加重視一個(gè)長期的利益，根據(jù)重復(fù)博弈論中基于貼現(xiàn)準(zhǔn)則的收益評估方式，假設(shè)T=∞，用Ui代表節(jié)點(diǎn)的平均收益[8]，則有：

在博弈中，節(jié)點(diǎn)存在的時(shí)間有限，若當(dāng)合作節(jié)點(diǎn)都知道其死亡時(shí)間，最后一次的博弈必定會選擇不合作。當(dāng)節(jié)點(diǎn)都無法預(yù)知博弈何時(shí)終止時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)就必須以無限重復(fù)的方式來評估當(dāng)前策略及其對后來情形的影響。

3 節(jié)點(diǎn)轉(zhuǎn)發(fā)策略的納什均衡分析

3.1 針鋒相對策略的納什均衡分析

針鋒相對策略[9]（Tit-for-Tat，TFT）會根據(jù)博弈對手方的策略來制定自己下一步的策略，策略仿佛“回聲”般出現(xiàn)。

博弈初始時(shí)，所有節(jié)點(diǎn)都具有合作意圖，能積極轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的信息，即，其中j為博弈中對方的節(jié)點(diǎn)，i為做出行為決策的節(jié)點(diǎn)。

TFT策略的概率模型如下：

當(dāng)某個(gè)時(shí)隙t1，節(jié)點(diǎn)i將它的合作概率改為其中0＜m＜1，則在下一個(gè)時(shí)隙t2，節(jié)點(diǎn)j的合作概率，節(jié)點(diǎn)i在t2時(shí)隙的合作概率又會變成1，此時(shí)兩個(gè)節(jié)點(diǎn)的概率序列如下所示：

在之后的每個(gè)博弈階段，節(jié)點(diǎn)i和j都會模仿對方在上一階段的行為。若節(jié)點(diǎn)i采取合作策略，那么節(jié)點(diǎn)j也是合作的，如果節(jié)點(diǎn)i選擇了不合作，那么節(jié)點(diǎn)j的策略也是不合作。

將式（6）代入到式（3）和式（4）中可得節(jié)點(diǎn)i采取TFT策略的收益為：

又因?yàn)楣?jié)點(diǎn)都是理性的，僅當(dāng)Ui≥0時(shí)才會選擇該策略。將其代入式（7）中有：

式（8）即是節(jié)點(diǎn)選擇TFT策略的納什均衡條件。

3.2 冷酷策略的納什均衡分析

冷酷策略[10]（Grim Strategy，GS）是一種在博弈中常用的觸發(fā)策略。初始節(jié)點(diǎn)之間都具有合作性，當(dāng)與節(jié)點(diǎn)i博弈的節(jié)點(diǎn)j在某個(gè)時(shí)隙選擇了不合作，那么節(jié)點(diǎn)i在這個(gè)時(shí)隙之后的所有策略都將會選擇不合作。GS策略將會孤立網(wǎng)絡(luò)中的自私節(jié)點(diǎn)，并且極大地打擊存在的自私行為。其概率模型如下：

其中q是節(jié)點(diǎn)i的一個(gè)觸發(fā)閾值，當(dāng)Pi≥q時(shí)，這個(gè)背叛會被對方節(jié)點(diǎn)忽略；當(dāng)Pi＜q，就會令博弈的節(jié)點(diǎn)選擇永久的不合作策略作為懲戒。如果對方知道你的策略為觸發(fā)策略，那么對方將不敢采取觸發(fā)策略，那么博弈雙方就可以一直合作下去，即使存在無意的錯誤，也會被判定為不合作且永遠(yuǎn)不再合作。本文為方便分析起見，只考慮最差的情況，即Pi＜q，故概率序列如下：

將式（10）代入到式（3）和式（4）中可得節(jié)點(diǎn)i采取GS策略的收益為：

又因?yàn)楣?jié)點(diǎn)都是理性的，僅當(dāng)Ui≥0時(shí)才會選擇該策略。將其代入式（11）中有：

式（12）即是節(jié)點(diǎn)選擇GS策略的納什均衡條件。

3.3 完全合作策略的納什均衡分析

完全合作策略（Full Cooperation Strategy，F(xiàn)CS）基于理想的情況之下，所有節(jié)點(diǎn)在博弈的任意階段都會選擇合作策略，在本文中作為一種對比策略引入。其概率序列如下：

將式（13）代入到式（3）和式（4）中可得節(jié)點(diǎn)i采取完全合作策略的收益為：

又因?yàn)楣?jié)點(diǎn)都是理性的，僅當(dāng)Ui≥0時(shí)才會選擇該策略。將其代入式（14）中有：

式（15）即是節(jié)點(diǎn)選擇FCS策略的納什均衡條件。

3.4 寬恕的針鋒相對策略的納什均衡分析

寬恕的針鋒相對策略（Tit-for-Tat with Forgiveness，TFTF）是在經(jīng)歷對方的一個(gè)不合作行為后，節(jié)點(diǎn)以一個(gè)小概率m()

0＜m＜1去選擇合作，并如同TFT策略一般交替出現(xiàn)。

為方便討論起見，假設(shè)其概率序列如下：

將式（16）代入到式（3）和式（4）中可得節(jié)點(diǎn)i采取完全合作策略的收益為：

又因?yàn)楣?jié)點(diǎn)都是理性的，僅當(dāng)Ui≥0時(shí)才會選擇該策略。將其代入式（17）中有：

3.5 嚴(yán)厲針鋒相對策略的納什均衡分析

嚴(yán)厲針鋒相對策略（Stern Tit-for-Tat，STFT）[11]是指當(dāng)節(jié)點(diǎn)出現(xiàn)不合作行為時(shí)，其所有鄰居節(jié)點(diǎn)對它執(zhí)行若干時(shí)隙的拒絕合作的懲罰，且其本身策略為合作。懲罰期間結(jié)束后鄰居節(jié)點(diǎn)選擇遺忘對方的不合作行為，重新開始合作。

為方便分析起見，令懲罰期為3個(gè)時(shí)隙，且重新合作后又出現(xiàn)不合作行為，設(shè)定其概率序列如下：

將式（20）代入到式（3）和式（4）中可得節(jié)點(diǎn)i采取完全合作策略的收益為：

又因?yàn)楣?jié)點(diǎn)都是理性的，僅當(dāng)Ui≥0時(shí)才會選擇該策略。將其代入式（21）中有：

4 結(jié)語

無線Ad Hoc網(wǎng)絡(luò)起源于軍事運(yùn)用，時(shí)至今日已得到廣泛的關(guān)注，由于其分布式的特點(diǎn)，導(dǎo)致每個(gè)節(jié)點(diǎn)都會對網(wǎng)絡(luò)造成影響，故促進(jìn)節(jié)點(diǎn)之間的合作是有必要的。本文對TFT策略、GS策略、FCS策略、TFTF策略、STFT策略進(jìn)行了滿足納什均衡的條件比較[12-13]，通過對比可以得知TFT策略更易滿足該條件。

[1]KHALILI A，BAZZI W M，RASTEGARNIA A.Cooperation gain in incremental LMS adaptive networks with noisy links [C]//Proceedings of 2012 SPIT Second International Conference.Dubai：SPIT，2012：107-114.

[2]RAMACHANDRAN S，SHANMUGAM V.Performance comparison of routing attacks in manet and WSN[J].International Journal of Ad Hoc，Sensor&Ubiquitous Computing，2012，3（4）：361-369.

[3]BADE S，KUMAR M，KAMAT P.A reactive energy-alert algorithm for MANET and its impact on node energy consumption [J].International Journal of Computer Applications，2013，71（18）：267-272.

[4]JIN Q，WANG Z，WANG Y L.Strategy changing penalty promotes cooperation in spatial prisoner′s dilemma game[J].Chaos，Solitons&Fractals，2012，45（4）：395-401.

[5]ROCA C P，SANCHEZ A，CUESTA J A.Individual strategy update and emergence of cooperation in social networks[J]. The Journal of Mathematical Sociology，2012，36（1）：1-21.

[6]LEI T，XIANG M S.Research of avoid the selfish behavior in mobile Ad Hoc networks based on repeated game[C]//Proceedings of 2012 the Fourth IEEE International Conference on Multimedia Information Networking and Security.Nanjing，China：IEEE，2012：835-838.

[7]WANG Y，XU Q，LIU Z.Fair computation with tit-for-tat strategy[C]//Proceedings of 2013 the 5th IEEE International Conference on Intelligent Networking and Collaborative Systems.[S. l.]：IEEE，2013：309-314.

[8]SRIVASTAVA V，DASILVA L A.Equilibria for node participation in Ad Hoc networks-an imperfect monitoring approach [C]//Proceedings of 2006 IEEE International Conference on Communications.Istanbul：IEEE，2006，8：3850-3855.

[9]BOYER S，ROBERT J M，ROUSSEAU C，et al.A novel reputation-based tit-for-tat strategy for IEEE 802.11 CSMA/CA protocol[C]//Proceedings of 2012 IEEE Consumer Communications and Networking Conference.Las Vegas：IEEE，2012：143-148.

[10]WANG J，CAI Y Q.A rational secret sharing scheme based on repeated game[C]//Proceedings of 2011 the 7th IEEE International Conference on Computational Intelligence and Security.Hainan，China：IEEE，2011：615-619.

[11]聞英友，趙博，趙宏.基于博弈理論的移動自組網(wǎng)激勵機(jī)制研究[J].通信學(xué)報(bào)，2014，35（4）：44-52.

[12]徐許亮，董榮勝，劉亮龍.無線自組網(wǎng)中節(jié)點(diǎn)協(xié)作的納什均衡研究[J].計(jì)算機(jī)工程，2010，36（4）：107-109.

[13]孫玉星，趙燕飛，李婭，等.基于概率博弈的無線自組網(wǎng)信任推薦激勵策略的研究[J].計(jì)算機(jī)科學(xué)，2011，38（4）：65-71.

Analysis for forwarding strategy of Ad Hoc network node based on repeated game

TAN Mian，HE Shibiao，SONG Bo，ZHU Guoqing，ZHANG Hui
（Chongqing Communication Institute，Chongqing 400035，China）

In wireless Ad Hoc network，the intercommunication between the source and destination nodes needs the support of relay node.Since the node is rational，it may refuse the forwarding requests.For the cooperation problem among the nodes，the tit-for-tat strategy，grim strategy，full cooperation strategy，tolerant tit-for-tat strategy and severe tit-for-tat strategy are analyzed with Nash equilibrium.According to the theoretical analysis，the tit-for-tat strategy is more advantageous than other strategies because of its low threshold value.

wireless Ad Hoc network；repeated game；Nash equilibrium；forwarding strategy

TN92-34

A

1004-373X（2015）23-0020-04

10.16652/j.issn.1004-373x.2015.23.006

譚冕（1989—），男，重慶人，碩士研究生。主要研究方向?yàn)榭垢蓴_通信、無線Ad Hoc網(wǎng)絡(luò)的節(jié)點(diǎn)合作研究。

2015-04-04

重慶市自然科學(xué)基金資助項(xiàng)目（cstc2014jcyjA40051）