基于隨機演化博弈的WSNs節點協作演化模型

王丁　曹奇英　許洪云　沈士根

摘 要：為解決無線傳感器網絡節點協作策略的選擇影響協作效果的問題，考慮到節點數量有限及個體隨機性，基于模仿突變Wright-Fisher過程的隨機演化博弈，提出了WSNs節點協作隨機演化模型，并加入了與節點協作程度相關的懲罰機制。該模型彌補了復制子動態不適用于節點數量有限的WSNs節點協作演化建模問題。經過隨機動力學分析，推導并證明了達到演化穩定狀態的定理。最后通過實驗驗證定理并分析了選擇強度和懲罰力度對WSNs節點協作演化穩定狀態的影響。

關鍵詞：無線傳感器網絡；協作；Wright-Fisher過程；隨機演化博弈；模仿突變

中圖分類號： TP393 文獻標志碼： A 文章編號：2095-2163（2016）01-

Abstract： To solve the problem of coordination decisions among WSNs nodes which affects the cooperation between nodes， considering limited numbers of nodes and individual stochastic effect， this paper constructs a stochastic evolutionary trust model of WSNs nodes based on imitated mutation Wright-Fisher process， and introduces a punishment mechanism related to the coordination level of nodes. The model compensated for the shortcoming of replicator dynamics where it was inapplicable to the WSNs having limited numbers of nodes. Theorems of arriving at the evolutionary stable state， through stochastic dynamics analysis， are deduced and proved. Experiments verify the conclusions and analyze the impacts of punishment levels and selection intensities toward the WSNs nodes coordination evolutionary stable state.

Keywords： Wireless Sensor Networks（WSNs）； Coordination； Wright-Fisher Process； Stochastic Evolutionary Game； Imitated Mutation

0 引言

無線傳感器網絡（Wireless Sensor Networks， WSNs） [1]是由數量眾多的傳感器節點以自組織和多跳等方式組成的無線網絡。WSNs中傳感器節點采集的數據需要被多個節點連續轉發后才能到達目標節點。如果一個節點與其他節點協作，那么將會幫助其他節點轉發數據包，使協作任務的成功率提高，可認為該節點獲得收益；但在轉發數據包的同時，節點本身需要付出一定的成本，如消耗能量、自身任務延時傳輸等。由于獲得收益和付出成本是一個矛盾，因此若存在較多節點不和其他節點協作的情況，就會導致WSNs節點無法正常協作。因此，節點之間協作與否會直接影響到WSNs的穩定性和協作任務的成功率。

近幾年來，已有許多學者使用演化博弈論的方法來分析網絡中的一些矛盾問題。文獻[2]分析了無限總體演化博弈的演化穩定策略，并與復雜網絡博弈的演化穩定策略進行了比較，提出了一種適用于網絡演化博弈的演化穩定策略新定義；文獻[3]將演化博弈應用于延遲容忍網絡的非合作轉發控制方面，并分析了交互次數對演化均衡的影響。在WSNs研究領域，文獻[4]提出了一種基于演化博弈的資源控制協議，用于緩解WSNs內部資源競爭矛盾。文獻[5]將演化博弈與WSNs節點信任決策結合，建立了WSNs節點信任博弈模型，提出并證明了在不同的參數條件下達到演化穩定策略的定理。文獻[6]和文獻[7]在文獻[5]的基礎上分別引入了節點的反思機制和模仿機制，并考慮了網絡不可靠因素對模型的影響。

上述文獻所用的演化博弈模型大都是針對無限總體的對象，而實際情況中的研究對象一般都是有限總體。針對這個問題，學者們將隨機過程應用到演化博弈中，形成了以有限總體為研究對象的隨機演化博弈。文獻[8]研究了服務提供商面對軟硬件服務攻擊時的安全和可信機制，提出了一種適用于虛擬傳感器服務（Virtual Sensor Services）的安全、可信的隨機演化聯合博弈防御框架。文獻[9]針對網構軟件中存在的服務問題，將網構軟件的服務差異化，并把基于Wright-Fisher過程的兩策略博弈拓展到多策略，提出了一種博弈參與者具有多個策略的信任演化博弈模型。文獻[10]把Moran過程應用到無線網絡的接入選擇中，并從多策略的角度改進了局部更新機制。隨機演化博弈雖然在其他領域已有較廣的應用，但是目前在WSNs中應用還較少。

本文使用基于兩策略頻率相關、帶模仿突變的Wright-Fisher過程隨機演化博弈模型來分析無線傳感器網絡中存在的節點協作問題。數量有限的WSNs節點在選擇協作與否時體現出了重復性、有限理性等特征，而對于整個WSNs來說，其目標是在達到總體收益較高狀態的同時也能夠保持足夠的穩健性，這些特征恰好滿足隨機演化博弈的要求。據此，本文建立了WSNs節點協作演化模型，使節點在無外界干預的情況下動態演化，各個節點根據模仿突變Wright-Fisher機制自行調整下一次博弈的策略，使WSNs逐漸演化到穩定狀態。在到達演化穩定狀態之后，WSNs中的絕大部分節點將會選擇協作策略并保持不變。在信任演化[5]的基礎上，通過考慮WSNs中有限節點數量的情況，引入懲罰因子和模仿機制來構造協作博弈模型，并利用帶突變的Wright-Fisher過程來分析節點協作演化動態，使WSNs節點協作模型更趨近真實狀況，并得出到達演化穩定狀態的定理，分析影響到達演化穩定狀態的影響因子。

1 基于突變Wright-Fisher過程的隨機演化博弈模型

博弈論是分析博弈個體在進行博弈時表現出的行為并研究博弈個體的博弈最優策略的理論。一個標準的博弈由3個要素組成：博弈個體，策略集合和收益函數[11]。博弈個體是參與博弈的主觀個體，每個博弈個體分別從策略集合中選取一種策略與另一個博弈個體進行博弈，收益函數是博弈個體依據其策略與對手博弈所獲得的收益。收益函數可由收益矩陣的形式給出。經典博弈的博弈個體總是完全理性[11]的，也就是說，博弈個體總是選擇收益最大的策略與對手進行博弈。

演化博弈論在經典博弈的基礎之上，結合博弈分析理論和生物種群的演化過程，形成了一個新的博弈論分支。在演化博弈論中，博弈個體都是有限理性[12]的，它把所有博弈個體的總體視為一個種群，將種群作為基本的研究對象，研究博弈個體在多次動態博弈中的策略演化狀況。

經典的演化博弈的研究對象一般是無限總體，但在實際情況中，研究對象都是總體數量有限的，并且個體的隨機性在有限總體的博弈過程中起著非常重要的作用，因此基于隨機過程的隨機演化博弈成為了研究有限總體演化博弈的重要途徑，當中較重要的三種模型是Moran過程[13]、Wright-Fisher過程[14]和隨機配對過程[15]。其中Wright-Fisher過程由于能夠在一次迭代內進行同步更新，相較于只能異步更新的其他兩種過程更具現實意義。

在Wright-Fisher過程中，總體中的個體在進行策略更新時，會依據策略的適應性選擇適合自身的策略，之后每一個體都會產生多個后代個體，得到一個總數大于總體數量的后代集合，再從這個集合中隨機選出等于總體數量的新個體取代當前個體。

在文獻[14]描述的Wright-Fisher過程博弈模型的基礎上引入模仿突變概率 ， ， 表示選擇 策略的個體在下一次博弈時依然選擇 策略的概率， 表示選擇 策略的個體在下一次博弈時突變為 策略的概率， 表示選擇 策略的個體在下一次博弈時突變為 策略的概率， 表示選擇 策略的個體在下一次博弈時依然選擇 策略的概率。易知，突變概率 存在如下關系：

， （1）

每個博弈個體在進行策略更新時，策略的選擇過程相當于在個體后代的集合中進行 次獨立的二項分布試驗，因此產生選擇 策略個體的過程就是概率為 的 重伯努利試驗，所以帶突變的Wright-Fisher過程是一個狀態空間為 的馬爾可夫鏈，系統從狀態 轉變到狀態 的轉移概率為：

（2）

2 WSNs節點協作演化模型

2.1 博弈模型

基于文獻[5]的研究，本文在WSNs節點協作博弈時加入了與節點協作程度相關的懲罰機制。在WSNs中，節點可以與鄰居節點進行主動式的交互，選擇協作策略與對方協作，或選擇不協作策略不與對方協作。在本文中并不涉及節點協作程度的計算或量化過程，而是在節點選擇不協作策略時給予一定的懲罰。

考慮兩個節點在交互時的協作狀況，記 表示當前節點數據被協作節點成功轉發傳輸而帶來的收益； 表示當前節點選擇與其他節點協作，成功轉發其他節點數據使任務的成功率提高帶來的收益； 表示當前節點因選擇協作策略提升了自身在對方節點的信任度收益或因選擇不協作策略而降低自身在對方節點的信任度損失； 表示當前節點選擇協作策略使路由可靠度提升而帶來的收益或因選擇不協作策略而使路由可靠度降低所帶來的收益損失； 表示因對方節點不協作而導致自身數據傳輸失敗帶來的收益損失； 表示因選擇不協作策略節省能量從而延長自身的生存周期所獲得的收益； 表示當前節點向對方節點發送自身的數據或轉發對方數據所產生的傳輸成本， 表示當前節點因選擇了不協作策略而受到的懲罰損耗。

下面對各種可能發生的交互狀態分別進行討論：

1）兩個節點在進行交互時均選擇了協作策略。雙方節點的收益均為 。

2）兩個節點在進行交互時有一個節點選擇了協作策略，而另一個節點選擇了不協作策略。此時選擇了協作策略的節點會幫助對方節點轉發傳輸數據，而選擇不協作策略的節點則不會幫助對方轉發數據，因此選擇協作策略的節點收益為 ，選擇不協作策略的節點收益為 。

3）兩個節點在進行交互時均選擇了不協作策略。兩個節點的收益均為 。

定義1 無線傳感器網絡節點協作博弈是一個由四元組 表示的對稱博弈。其中參與者 為無線傳感器網絡中所有節點的集合； 為參與者的總體數量；策略集合為 ， 為協作策略， 為不協作策略； 為無線傳感器網絡節點在一次兩人兩策略對稱博弈時的收益函數，如表1所示。

2.2 模仿突變因子的確定

本文提出一種基于模仿策略的策略調整機制，使傳感器節點在協作博弈時若發現對方策略的收益大于自己的收益，就會模仿其策略或行為。模仿機制體現在博弈過程中具體表現為博弈個體在產生后代的過程中引入模仿突變因子，產生后代的過程中有一定的突變概率，將后代個體的策略調整為博弈對手的策略。

邏輯斯蒂方程（Logistic Equation）是研究生物學、社會學中種群增長的一種模型，在生態學中，一個種群內個體數量的變化動態可以用邏輯斯蒂方程的微分形式表示：

（3）

其中， 為種群的瞬時增長量， 為種群的個體增長率， 為特定時間內種群內的個體數量， 為環境容納量，也就是該生態環境所能維持的種群內個體最大數量。 為邏輯斯蒂系數。

在演化博弈過程中，突變因子在演化前期由于博弈次數較少或穩定性的可信度不高，因此模仿突變因子具有較大的變化趨勢，而隨著演化過程的演進，系統穩定性的可信度逐漸增強，因此模仿突變因子在演化后期的變化范圍較小，這個特性恰與邏輯斯蒂方程的增長趨勢相符，因此本文使用基于邏輯斯蒂方程的變形微分方程來表示模仿突變因子。

令 ，則邏輯斯蒂方程變形為：

（4）

記 表示博弈總體內每個個體可選的博弈策略集，向量 表示總體狀況，其中 表示選擇策略 的個體比例； 表示選擇策略 的個體和選擇策略 的個體在博弈時相遇，兩個個體在經過博弈后，互相學習，觀察對方的策略和收益，對自己當前的策略和收益進行調整，使個體產生的后代有一定概率突變為其他策略，記 表示選擇 策略的后代個體突變為 策略的概率，由于模仿突變概率與各策略的收益和選擇該策略的個體在總體中的比例有關，引入邏輯斯蒂變形方程可得模仿突變概率為：

（5）

其中， 表示策略 與策略 在博弈過程中期望收益之差。

2.3 引入模仿突變Wright-Fisher過程

由于WSNs的節點數量是有限的，進行博弈的節點可以看作出自一個種群的有限總體，因此在WSNs節點協作博弈中引入模仿突變Wright-Fisher過程，該模型既能體現WSNs節點協作博弈的總體有限性、離散性和隨機性等特征，也能體現出節點在博弈時的策略調整過程。

假設在WSNs節點協作博弈中，節點的總數為 ，有數量為 的節點選擇協作策略，則有 個節點選擇不協作策略。在進行節點協作博弈時，需剔除自己和自己博弈的情況，因此可得：

任選一個節點選擇協作策略的期望收益為： （6）

任選一個節點選擇不協作策略的期望收益為：

（7）

假設在演化博弈中，收益函數對該策略適應度的影響因子為 ， ，則在WSNs節點協作博弈中，協作策略的適應度為： （8）

不協作策略的適應度為： （9）

由于適應度要求收益函數為非負數，因此對策略的收益函數還應加以修正，使其滿足適應度的條件。選擇強度參數 的引入，使得Wright-Fisher過程具有了有限理性的特性。

定義2 在不考慮自身博弈情況的無線傳感器網絡節點協作博弈中，協作策略的適應度為 ，不協作策略的適應度為 ，其中 為選擇協作策略的節點數量， 為無線傳感器網絡節點在博弈時選擇協作策略的收益且：

（10）

為無線傳感器網絡節點在博弈時選擇不協作策略的收益且：

（11）

為收益對適應度的選擇強度， 為常數使得收益函數為非負數。

定義3 在不考慮自身博弈情況的無線傳感器網絡節點協作博弈中，個體在每次博弈之后，產生的后代個體中，有一定的突變概率 使個體改變博弈的策略，個體的博弈策略從協作策略突變為不協作策略的概率為：

（12）

則個體的博弈策略依然保持協作策略的概率為 ；個體的博弈策略從不協作策略突變為協作策略的概率為： （13）

則個體的博弈策略依然保持不協作策略的概率為 ，其中 ， ， ， 為常數使得 ， 。

在定義3中， 和 作為策略突變的概率，保證其大小與當前節點的自身收益呈反向變化，與對方的收益呈正向變化。

WSNs的節點在進行下一次博弈之前，會進行以下步驟更新策略：

1）每個節點都會生成相同數量的多個選擇相同策略的后代，這些后代中，有一部分后代會以突變概率 突變，選擇對手策略，剩下的后代依然完全繼承父代個體選擇的策略，構成一個數量為 的整數倍個后代的集合；

2）從這個后代集合里選出與總體數量相同的 個新一代后代，由于后代節點只有協作和不協作兩種策略，選擇每個節點的過程都是一次獨立伯努利試驗過程，由定義2可得，選出一個信任策略的后代節點的概率為 ，因此新一代博弈后代節點的產生過程就是一個概率為 的 重伯努利試驗；

3）新一代后代完全替換上一代，完成節點的一代更新。

由定理1和定理2可知，要使整個無線傳感器網絡具有良好的穩定性和節點協作性，需促使無線傳感器網絡的節點在協作博弈時選擇協作策略，因此在設計無線傳感器網絡協作機制時應使其盡量符合定理2的條件。懲罰因子 的引入會使無線傳感器網絡節點在選擇不協作策略時受到一定的懲罰，產生更多的損失，當 逐漸增大，懲罰力度也逐漸變大時，會使無線傳感器網絡逐漸滿足定理2的條件，而逐漸偏離定理1的條件。當 增大到一定程度，使得無線傳感器網絡節點信任博弈不滿足定理1，但是滿足定理2的條件時，無線傳感器網絡將處于比較理想的穩定狀態，此時網絡內的所有節點在經過有限次博弈之后都會最終選擇協作策略。

3 實驗分析

3.1 定理驗證實驗

在圖1中，當WSNs節點協作博弈的條件滿足定理1時，設定選擇協作策略的節點初始比例為0.999 9，經過140次博弈，絕大部分節點都選擇不協作策略，達到了 的演化穩定狀態；當WSNs節點協作博弈的條件滿足定理2時，設定選擇協作策略的節點初始比例為0.000 1時，經過78次博弈，絕大部分節點都選擇協作策略，達到了 的演化穩定狀態。此實驗驗證了定理1和定理2成立。

3.2 影響因子驗證實驗

實驗中分別使用不同數值的懲罰因子 和選擇強度 來觀察其對無線傳感器網絡節點協作博弈的影響，并根據實驗結果給出優化無線傳感器網絡節點協作博弈的對策。本實驗共設2組，第1組分析懲罰因子 對定理2的影響，第2組分析選擇強度 對定理2的影響。

3.2.1 懲罰因子 的影響

實驗設定： ， ， ， ， ， ， ， ， ； 分別設定為16和15。兩組數據均滿足定理2，實驗結果如圖2所示。

在圖2中，當選擇協作策略的節點初始比例為0.000 1時，兩組數據均使得WSNs節點經過一定次數的協作博弈達到了 的演化穩定狀態。在其他參數相同的情況下， 的一組節點只需78次博弈即可達到演化穩定狀態，比 的另一組節點收斂速度更快。由此可知，在滿足定理2的條件下，提高懲罰因子 能有效促進WSNs節點在進行協作博弈時更快地達到演化穩定狀態。

在圖3中，當選擇協作策略的節點初始比例為0.0001時，三組數據均使得無線傳感器網絡節點經過一定次數的協作博弈后達到了 的演化穩定狀態。在其他參數相同的情況下， 的一組節點需要212次博弈才能達到穩定狀態， 的一組節點需要130次博弈才能達到穩定狀態，而 的一組節點只需78次即可達到穩定狀態。由此可知，在滿足定理2的條件下，提高選擇強度 能有效促進無線傳感器網絡節點在進行協作博弈時更快地達到演化穩定狀態。

4 結束語

節點間的協作問題是WSNs穩定運行的重要基礎，促進WSNs節點互相協作能夠促使整個無線傳感器網絡達到穩定狀態。本文根據無線傳感器網絡中節點數量有限等特點，引入與節點協作相關的懲罰機制，提出了基于模仿突變Wright-Fisher過程的無線傳感器網絡節點協作隨機演化模型，彌補了復制子動態不適用于節點數量有限的無線傳感器網絡中的缺陷，使無線傳感器網絡節點協作博弈模型更符合實際情況。在此基礎之上，對隨機演化博弈模型進行了動力學分析，得出并證明了WSNs節點協作博弈達到演化穩定狀態的定理。經過分析與實驗驗證了結論：提高節點選擇不協作策略的懲罰力度和節點選擇協作策略的選擇強度均能有效促進WSNs節點的協作程度，實現網絡的安全與穩定。本文提出的基于模仿突變Wright-Fisher過程的WSNs節點協作隨機演化博弈模型，為無線傳感器網絡節點協作問題研究提供了理論依據。

參考文獻：

[1] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey[J]. Computer networks， 2008， 52（12）： 2292-2330.

[2] CHENG D， XU T， QI H. Evolutionarily Stable Strategy of Networked Evolutionary Games[J]. IEEE transactions on neural networks and learning systems， 2014， 25（7）： 1335-1345.

[3] EL-AZOUZI R， De PELLEGRINI F， SIDI H B A， et al. Evolutionary forwarding games in delay tolerant networks： Equilibria， mechanism design and stochastic approximation[J]. Computer Networks， 2013， 57（4）： 1003-1018.

[4] FARZANEH N， YAGHMAEE M H. An adaptive competitive resource control protocol for alleviating congestion in Wireless Sensor Networks： An evolutionary Game Theory approach[J]. Wireless Personal Communications， 2015，82（1）： 123-142.

[5] 沈士根， 馬絢， 蔣華， 等. 基于演化博弈論的 WSNs 信任決策模型與動力學分析[J]. 控制與決策， 2012， 27（8）： 1133-1138.

[6] 李紫川， 沈士根， 曹奇英. 基于反思機制的 WSNs 節點信任演化模型[J]. 計算機應用研究， 2014， 31（5）： 1528-1531.

[7] LI Yuan-jie， XU Hong-yun， CAO Qi-ying， et al. Evolutionary game-based trust strategy adjustment among nodes in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks， 2015，2015（818903）：1-12.

[8] LIU J， SHEN S， YUE G， et al. A stochastic evolutionary coalition game model of secure and dependable virtual service in Sensor-Cloud[J]. Applied Soft Computing， 2015， 30： 123-135.

[9] 印桂生， 王瑩潔， 董宇欣， 等. 網構軟件的 Wright-Fisher 多策略信任演化模型[J]. 軟件學報， 2012， 23（8）： 1978-1991.

[10] 馮光升， 王慧強， 周沫， 等. 基于 Moran 過程的無線網絡接入選擇方法[J]. 北京郵電大學學報， 2014， 37（4）： 10-14.

[11] FUDENBERG D， TIROLE J. 博弈論[M].北京： 中國人民大學出版社，2002.

[12] 喬根 W.威布爾. 演化博弈論[M]. 王永欽，譯.上海：上海人民出版社，2006： 40-86.

[13] MORAN P. A. P. The Statistical Processes of Evolutionary Theory[M]. Oxford： Clarendon Press， 1962.

[14] TRAULSEN A， CLAUSSEN J C， HAUERT C. Coevolutionary dynamics： from finite to infinite populations[J]. Physical review letters， 2005， 95（23）： 238701.

[15] TRAULSEN A， PACHECO J M， NOWAK M A. Pairwise comparison and selection temperature in evolutionary game dynamics[J]. Journal of theoretical biology， 2007， 246（3）： 522-529.

[16] OHTSUKI H， PACHECO J M， NOWAK M A. Evolutionary graph theory： breaking the symmetry between interaction and replacement[J]. Journal of Theoretical Biology， 2007， 246（4）： 681-694.