一種機會網絡節點重復博弈模型

宋蔓蔓，張振宇，楊文忠，張珍

新疆大學信息科學與工程學院，烏魯木齊 830046

一種機會網絡節點重復博弈模型

宋蔓蔓，張振宇，楊文忠，張珍

新疆大學信息科學與工程學院，烏魯木齊 830046

在資源受限的機會網絡中，節點在轉發過程中所表現出的自私行為將嚴重影響網絡性能。針對這一問題，建立基于認錯機制的“禮尚往來”策略的節點重復博弈模型。節點考慮到將來的利益，迫于對懲罰的恐懼而參與轉發。通過該策略，節點協作可以使網絡性能達到最優。仿真結果表明，節點間的相互協作增強，在自私節點較多時也能保證較好的網絡性能。

機會網絡；節點協作；認錯機制；重復博弈

1 概述

機會網絡[1]是一種不需要源節點和目的節點之間存在完整鏈路，利用節點移動帶來的相遇機會實現通信的自組織網絡。由于節點的移動性，在機會網絡中很難維持端到端的連通，消息從源節點傳遞到目的節點，通常需要中間節點的存儲、攜帶和轉發才能完成消息的傳送。

由于轉發消息會消耗節點有限的資源，如緩存、能量等，節點為了維護自己的資源拒絕與其他節點協作。文獻[2]把機會網絡中只享受信息資源服務而不為系統做貢獻的節點稱為自私節點。節點的自私行為將導致網絡性能嚴重下降[2-4]。因此促進節點間的協作成為機會網絡的一個關鍵問題。

目前，促進節點協作的方法主要分為基于信譽、基于聲譽和博弈論三類方法。基于信譽的方法[5]基本思想是：節點為另一個節點轉發消息將獲取一定的信譽，這些信譽是從發送方（或目的地）扣除。這個方法實現時需要在每個節點上添加防篡改硬件，從而可以正確地增加或扣除一個節點的信譽。基于聲譽的方法[6]記錄節點過去的行為，幫助節點區分和選擇有較高聲譽的、從而愿意幫助其他節點轉發的節點，這樣可以得到較好的網絡性能。現有檢測機制的不準確性是聲譽系統應用的主要障礙。

本文在機會網絡中存在自私節點的情況下，建立了基于認錯機制的“禮尚往來”策略（Adm it-Tit-for-Tat，ATFT）的重復博弈模型，節點會相互協作，可以使網絡性能達到最優。

2 基于ATFT策略的重復博弈模型

重復博弈是指階段博弈重復進行（有限次或無限次）構成的博弈過程，是一種特殊的博弈[7]。由于其他參與人過去行動的歷史是可以觀測的，因此在重復博弈中，每個參與人可以使自己在每個階段的策略選擇依賴于其他參與人過去的行為。

由于網絡節點當前消息轉發策略行為選擇會影響其他節點的策略選擇，在重復博弈理論的基礎上，通過將網絡節點之間交互抽象成重復的多階段動態博弈，并且使用納什均衡這一概念對利益沖突環境中節點理性行為所導致的穩定局勢進行預測。當節點根據其他節點行為始終選擇對自己最有利的協作策略時，便構成了網絡中的一個納什均衡。這一整體網絡狀態的意義在于激勵一致性：此時，任何節點均不會產生自私企圖，因為這將降低節點的整體收益。重復博弈的分析視角為我們從節點自身角度來引入相應的協作促進機制，同時考察耐心因素對其理性響應的影響提供了便利。

ATFT策略的基本思想是節點第一次總是協作，之后節點i根據對方的上次策略進行決策。即如果對方選擇不協作，節點i也選擇不協作來進行懲罰。在經過若干次懲罰之后，對方意識到必須主動轉發來向i認錯，否則懲罰將無限執行下去，對方一旦認錯，i必須原諒。

2.1 階段博弈

為分析方便，本文做出如下假設：

（1）網絡中存在N個節點，N={1，2，…，n}。

（2）所有消息的大小相同，發送、轉發單個消息時每個中繼節點的花費相同。

（3）整個機會網絡運行時間由一系列離散的時隙t構成(t1，t2，…，tn)，并且單一時隙長度足以保證每個消息均能抵達目的節點。

（4）由于本文研究的是消息轉發時節點之間的相互協作，假設消息丟失的主要原因是網絡中節點的不合作行為。

（5）每次博弈都遵循相同的規則和過程。

假設節點i加入到消息傳輸中，節點的一個消息被成功轉發的收益為Bi，轉發一個消息的花費為Coi。根據ATFT策略，綜合考慮對手上一次的策略以及網絡花費，決定節點i下一階段的策略，得出節點i的效用函數為：

其中-i表示節點i的對手；S-i={C-i，NC-i}表示節點-i的策略空間，其中C表示合作，NC表示拒絕合作。節點i的策略選擇可表示為f(S-i)；b-i表示節點i接收到傳輸請求的概率；ai表示節點i轉發消息的概率。

由于資源有限，節點為了減少資源消耗會拒絕轉發消息。如果網絡中所有的節點均選擇這樣的策略，網絡中消息的傳輸成功率將會是0，由式（1）可知此時節點效用值最大，所有的節點達到納什均衡狀態，但是網絡中不存在任何協作轉發。這一穩定狀態顯然并不符合預期。

2.2 重復博弈模型

由2.1可知，如果節點間的交互只進行一次，博弈的結局與囚徒困境相似，所有節點選擇不協作策略形成了單階段博弈唯一的納什均衡。但是在節點的生命周期中很少只有一次博弈過程，它可以在不同的時刻與不同的對手加入不同的博弈過程。在網絡中一個節點在一次博弈中作為消息攜帶者，但是下一刻就可能在另一個博弈中充當消息接收者。因此加強節點間的相互協作需要建立一個重復博弈模型[8]。

假設重復博弈過程已經執行了T次，節點知道過去T-1次對手的行為。通過用貼現因子δ∈（0，1）來描述效用函數的話，節點的總效用值可表示為：

Ui（t）表示節點i在時刻t的效用值。δ表示節點對未來利益的重視程度，δ越大，節點越注重長遠利益，δ越小，節點越注重眼前利益。當T=∞時，以上博弈過程可視為無限次重復博弈過程[9]，記作G(∞)，則節點i的平均效用值為：

2.3 ATFT策略

假設自私節點的自私周期是y，則懲罰周期也為y，每個節點維護一個集合，保存相互交互過的節點i及交互節點拒絕與此節點協作的次數Nui。基本思想是：如果節點-i拒絕幫助節點i轉發消息，節點i將(-i，Nu-i)中Nu-i的值加1；一旦節點-i幫助i轉發，i將(-i，Nu-i)中Nu-i的值清零。以節點i向-i請求轉發為例，ATFT策略的具體步驟：

（1）如果節點-i是自私節點，轉向步驟（2），若不是，轉向步驟（6）。

（2）節點-i查看自己是否在集合中存儲了(i，Nui)，若未存儲（說明兩個節點首次交互），由于節點首次總是協作，-i幫助i轉發，并在集合中添加(i，0)，節點i在集合中添加(-i，0)，轉向（8），否則轉向（3）。

（3）-i查看集合中的Nui是否小于y，若小于轉向（5）。

（4）-i意識到由于自身的自私行為，節點i已經對自己做出y次懲罰，因此主動幫助轉發來認錯。節點i在收到-i的認錯之后，必須原諒，因此將(-i，Nu-i)中Nu-i清零。

（5）節點-i為了自身利益的最大化，仍拒絕轉發，i將(-i，Nu-i)中Nu-i值增加1。

（6）若節點-i不是自私節點，查看是否存儲了(i，Nui)，若未存儲，-i幫助i轉發，節點i在集合中添加(-i，0)，否則轉向（7）。

（7）-i查看集合中保存的Nui是否為零，若為零，幫節點i轉發，i(-i，Nu-i)中Nu-i清零；若不為零，則拒絕為節點i提供轉發服務，i將(-i，Nu-i)中Nu-i加1。

圖1 節點對未來利益重視程度對網絡性能的影響(y=2)

（8）交互結束。

在博弈過程中可以發現，一旦節點-i選擇自私，那么它將采取持續自私的策略。這是因為如果一次自私能夠讓節點-i額外獲益，那么在懲罰結束之后，節點-i會面臨相同的策略選擇。采用ATFT策略時，網絡中節點的效用函數為：

若博弈過程中節點i協作的效用大于自私行為的效用，它將毫不猶豫地選擇協作，并在下一次博弈時采取持續協作的策略。也就是說，為了打消節點i采取自私行為的念頭，必須保證其持續協作時的收益不小于重復自私行為的收益，這一條件可用式（5）表示：

由于節點都是理性的，只有式（5）不成立時才會自私。存在δ滿足上式，使節點避免自私行為，協作是節點的最優策略，而且節點沒有足夠的動機偏離這一決策。因此式（5）即為節點采取ATFT策略時最佳納什均衡的條件。

3 仿真及分析

本文采用仿真工具The ONE 1.4.0[10]分析本文所建立模型的有效性。采用真實城市街區圖，200個節點隨機分布在4 500 m×3 400 m的區域內，移動速度為1～3 m/s；節點間的通信范圍半徑為10 m；節點緩存大小均為10 MB；消息的大小為500 KB。

首先通過實驗分析了節點對未來利益重視程度對協作效果的影響。然后分析了懲罰周期y對協作性的影響。最后與已有的博弈模型對比，并給出了仿真結果。

3.1 節點對未來利益重視程度對協作性的影響

圖1給出了當懲罰周期y=2時，在機會網絡中存在不同比例的自私節點時在不同貼現因子取值下，對Epidem ic算法傳輸成功率和平均延遲的影響。圖1（a）中傳輸成功率隨δ增加而明顯提高，圖1（b）中網絡平均延遲隨δ增加而降低。隨著節點對未來利益重視程度的增長，自私節點會主動選擇認錯，因此整個網絡的協作性隨自私節點對未來利益的重視而得到了改善，進而傳輸成功率會隨之增加，網絡平均延遲相應減少。

3.2 懲罰周期對協作性的影響

圖2表示在貼現因子σ=1時，在機會網絡中存在不同比例的自私節點時在不同懲罰周期取值下，對Epidem ic算法傳輸成功率的影響。在一定范圍內，增加y將有助于提高網絡協作程度。但是如果y過大，即懲罰周期過長，超過了本實驗仿真過程中節點的最大相遇次數，在懲罰周期內自私節點拒不認錯，致使網絡性能下降。所以y值的選取需要根據網絡特定情況而定。

圖2 參數y對傳輸成功率的影響

3.3 自私節點比例對協作性的影響

分別模擬Epidem ic[11]、PROPHET[12]和Spray and Wait[13]三種算法在使用ATFT策略前后自私節點占節點總數的10%，20%，…，80%時對網絡中傳輸成功率的影響，并且與這三種算法使用冷酷策略（Grim Strategy，GS）[14]和GTFT[15]時的傳輸成功率進行對比。仿真結果如圖3所示。

圖3 傳輸成功率

Epidem ic算法復制消息并轉交給所遇到的所有節點，中間節點若不存在自私節點，負責轉發的中繼節點能及時把消息轉交給下一個中繼節點，最大程度上傳遞消息，所以消息遞交率比較高。自私節點比例增加時，中繼節點丟棄消息而不是盡最大努力轉發，因此成功率隨之降低。PROPHET算法是基于概率策略的，由于自私節點聲稱自己不會遇到其他節點，即傳輸概率為0，節點轉發消息時根本不會選擇此類節點，因此隨著網絡中自私節點數目的增多，可用節點的數目隨之減少，消息傳輸成功率隨之降低。網絡中自私節點數目較少時，Spray and Wait算法傳輸成功率最高，但隨著自私節點數目的增加，成功率明顯降低。這是由于Spray階段，源節點中的部分消息被擴散到鄰居節點，若Wait階段并未發現目的節點，那么中繼節點通過直接傳輸的方式把消息傳送到目的節點，因此隨著自私節點數目的增多，Spray階段消息被拋棄的幾率也隨之增加，成功率隨之降低。

使用GS策略之后，由于自私節點首次是合作的，因此當自私節點較少時，傳輸成功率要高于上述情況；但是由于網絡中任何一個節點的一次不協作將會導致永遠的不協作，在自私節點比例增加時，傳輸成功率明顯下降。

使用ATFT策略之后，由于引入了認錯機制，自私節點出于對懲罰的恐懼，每次收到傳輸請求時都會考慮自私行為帶來的后果，因此在自私節點逐漸增多的情況下Epidem ic、PROPHET和Spray and Wait三個算法均能保持平穩的傳輸成功率，優于未使用ATFT策略的情況。GTFT僅考慮了歷史收益對節點決策的影響，沒有考慮其將來獲利的期望。但是使用ATFT策略節點考慮了未來利益，導致節點在博弈過程中進行自我約束，并且提高了傳輸成功率。

4 結束語

本文建立基于認錯機制的“禮尚往來”策略的節點重復博弈模型。利用節點對將來利益的重視來脅迫它參與轉發協作。仿真結果表明，該模型使節點間的相互協作大大增強，網絡性能隨之提高。

[1]Pelusi L，Passarella A，Conti M.Opportunistic networking：data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine，2006，44（11）：134-141.

[2]Chiou C，Chen L.Poster abstract：an evaluation study of routing reliability in opportunistic networks[C]//Proceedings of the 9th ACM International Symposium on Mobile Ad hoc Networking and Computing.Hong Kong：ACM，2008：455-456.

[3]Panagakis A，Vaiosand A，Stavrakakis L.On the effects of cooperation in DTNs[C]//Proceedings of COMSWARE，2007：1-6.

[4]Marti S，Giuli T，Lai K.Mitigating routing misbehavior in mobile Ad hoc networks[C]//Proceedings of ACM MOBICOM’00.New York，USA：ACM Press，2000.

[5]Zhu Haojin，Lin Xiaodong，Lu Rongxing，et al.SMART：A secure multilayer credit-based incentive scheme for delay-tolerant networks[J].IEEE Trans on Vehicular Technology，2009，58（8）：4628-4639.

[6]Zhang Sihai，Qiu Hongyang，Liu Yuan，et al.Evolutionary reputation model for node selfishness resistance in opportunistic networks[C]//Concurrency and Computation：Practice and Experience，Forthcoming，2011.

[7]Osborne M J，Rubinstein A.A course in game theory[M]. Cambridge：M IT Press，1994.

[8]陸音，石進，謝立.基于重復博弈的無線自組網絡協作增強模型[J].軟件學報，2008，19（3）：755-776.

[9]Ratliff J.Sampler F T.Great introductory notes to the Folk Theorem[N/OL]（1996）.http：//www.virtualperfeetion. com/gametheory5.3.FolkTheorem Sampler.1.0.pdf.

[10]TKK/COMNET.Project page of the ONE simulator[EB/OL]. http：//www.netlab.tkk.fi/tutkimus/dtn/theone，2008.

[11]Apoorva J，Konstantinos P.Performance analysis of epidemic routing under contention[C]//Proc of the 2006 International Conference on Wireless Communications and Mobile Computing.[S.l.]：ACM Press，2006.

[12]Lindgren A，Doria A，Schelen O.Probabilistic routing in intermittently connected networks[J].Lecture Notes in Computer Science，2004，3126：239-254.

[13]Spyropoulos P K，Raghavendra C S.Spray and wait：al efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of ACM SIGCOMM Workshop on Delay-tolerant Networking，Philadelphia，New York，2005：252-259.

[14]張維迎.博弈論與信息經濟學[M].上海：上海人民出版社，1996：31-81.

[15]Srinivasan V，Nuggehalli P.Cooperation in wireless ad hoc networks[C]//Proc of the IEEE INFOCOM 2003. Washington：IEEE Computer Society，2003：808-817.

SONG Manman,ZHANG Zhenyu,YANG Wenzhong,ZHANG Zhen

College of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

In opportunistic networks with limited resources,the performance of network is seriously affected by selfish behavior of the nodes during the packet forwarding.To solve this problem,the paper establishes a repeated-game model of node cooperation based on a admit mechanism of“Tit-For-Tat”strategy.The nodes consider the long-term interests and participate in forwarding forced by the fear of punishment.By using the strategy,cooperation of nodes in the network can make the network performance to achieve optimal.The simulation results show that the mutual cooperation of nodes is enhanced and the performance of the network can be guaranteed when more selfish nodes exist in network.

opportunistic networks;node cooperation;admit mechanism;repeated game

A

TP393

10.3778/j.issn.1002-8331.1209-0185

SONG Manman,ZHANG Zhenyu,YANG Wenzhong,et al.Repeated-gam e model of node cooperation in opportunistic networks.Computer Engineering and Applications,2014,50（16）：86-89.

國家自然科學基金（No.61262089）；新疆大學博士科研啟動基金資助項目（No.BS110127）。

宋蔓蔓（1987—），女，主研方向：機會網絡；張振宇（1964—），男，副教授，主研方向：對等網絡，機會網絡；楊文忠（1971—），男，副教授，主研方向：無線網絡組播路由；張珍（1988—），女，主研方向：機會網絡。E-mail：songman0534@126.com

2012-09-18

2012-11-14

1002-8331（2014）16-0086-04