基于Wright-Fisher過程的WSNs節點信任隨機演化策略

王 丁 曹奇英* 許洪云 沈士根

1(東華大學計算機科學與技術學院 上海 201620) 2(東華大學信息科學與技術學院 上海 201620)3(紹興文理學院計算機科學與工程系 浙江 紹興 312000)4(嘉興學院數理與信息工程學院 浙江 嘉興 314001)

基于Wright-Fisher過程的WSNs節點信任隨機演化策略

王 丁1曹奇英1*許洪云2沈士根3,4

1(東華大學計算機科學與技術學院 上海 201620)2(東華大學信息科學與技術學院 上海 201620)3(紹興文理學院計算機科學與工程系 浙江 紹興 312000)4(嘉興學院數理與信息工程學院 浙江 嘉興 314001)

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

無線傳感器網絡 信任 Wright-Fisher過程 隨機演化博弈 懲罰機制

0 引 言

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

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

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

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

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

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

演化博弈論在經典博弈的基礎之上，結合博弈分析理論和生物種群的演化過程，形成了一個新的博弈論分支。在演化博弈論中，博弈個體都是有限理性[14]的，它把所有博弈個體的總體視為一個種群，將種群作為基本的研究對象，研究博弈個體在多次動態博弈中的策略演化狀況。演化博弈有兩個核心概念：演化穩定策略ESS(Evolutionary Stable Strategy)和復制子動態RD(Replicator Dynamic)。演化穩定策略反映了博弈均衡解的穩定性狀態，復制子動態則描述了博弈過程向演化穩定狀態收斂的變化動態。復制子動態可以由式(1)表示：

(1)

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

在Wright-Fisher過程中，總體中的每個個體在進行策略更新時，會依據策略的適應性強弱不同分別選擇適合自身的策略。之后每個個體都會產生多個與自身選擇的策略相同的后代個體，得到一個總數大于總體數量的后代集合，再從這個集合中隨機選出等于總體數量的新個體取代當前個體。Wright-Fisher過程可描述如下[16]：

假設在一個總體中，個體數量為N,策略集合為{S1,S2}，每個個體之間進行兩人兩策略對稱性博弈，收益矩陣如式(2)所示：

(2)

(3)

2 WSNs節點信任演化策略

2.1 博弈模型

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

記GT表示當前節點信任交互的對方節點而成功幫助對方轉發數據包帶來的收益；GC表示因對方節點信任當前節點，幫助轉發了當前節點的數據包，當前節點所獲得的收益；GD表示當前節點因選擇不信任策略，不幫助對方轉發數據包，節省了能量，從而延長了節點的生存周期所獲得的收益；C表示當前節點向對方節點發送自身的數據包或幫助轉發對方節點的數據包所產生的傳輸成本；L表示當前節點所發送的源數據包未能成功到達目的地而造成的損耗；β表示當前節點因選擇了不信任策略而受到的懲罰損耗。

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

(1) 兩個節點在進行交互時均選擇了信任策略

此時雙方節點均會轉發對方的數據包并向對方發送自身的數據包，獲得收益GT+GC，并消耗了發送兩次數據包的成本2C，因此雙方節點的收益均為:GT+GC-2C。

(2) 兩個節點在進行交互時有一個節點選擇了信任策略，而另一個節點選擇了不信任策略

此時選擇了信任策略的節點會幫助對方節點轉發數據包，從而獲得收益GT，同時消耗了轉發成本C，但由于對方節點選擇了不信任策略而導致自身的數據包無法被對方成功轉發，會造成L的損失，因此選擇信任策略的節點收益為GT-C-L。選擇不信任策略的節點會向選擇信任策略的節點發送數據包并被成功轉發而獲得收益GC，消耗了成本C。又因它不會轉發對方的數據包節省了能量從而延長了自身的生存周期，獲得收益GD，但由于它選擇了不信任策略而受到懲罰損失了β，因此選擇了不信任策略的節點收益為：GC+GD-C-β。

(3) 兩個節點在進行交互時均選擇了不信任策略

由于兩個節點都不信任對方節點，因此節點之間不會向對方節點發送數據包或轉發對方數據包，兩個節點都節省能量獲得收益GD，但受到選擇不信任策略的懲罰從而均損失了β，因此兩個節點的收益均為：GD-β。

定義1 WSNs節點信任博弈是一個由四元組(P,N,S,F)表示的對稱博弈。其中參與者P為WSNs中所有節點的集合；N為參與者的總體數量；策略集合為S={S1,S2}，S1為信任策略，S2為不信任策略；F為WSNs節點在一次兩人兩策略對稱博弈時的收益函數，如表1所示。

表1 一次博弈收益矩陣

2.2 引入Wright-Fisher過程

在經典的演化博弈中，演化穩定策略和復制子動態方程都是基于博弈個體的數量是無限多且不同策略的個體均勻分布的假設。但對于參與者數量有限的博弈，整個系統的狀態將成為離散點的集合，因此微分方程將不再適用于離散狀態的隨機演化博弈。

由于WSNs的節點數量是有限的，進行博弈的節點可以看作出自一個種群的有限總體，因此在WSNs節點信任博弈中引入Wright-Fisher過程，該模型能滿足WSNs節點信任博弈的總體有限性、離散性和隨機性等特征。

假設在WSNs節點信任博弈中，節點的總數為N，有i個節點選擇信任策略，則有N-i個節點選擇不信任策略。在進行節點信任博弈時，需剔除自己和自己博弈的情況，因此可得：任一節點選擇信任策略的期望收益為：

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

假設在演化博弈中，收益函數對該策略適應度的影響因子為ω，ω∈[0,1]，則在WSNs節點信任博弈中，信任策略的適應度為：

由于適應度要求收益函數為非負數，因此對策略的收益函數還應加以修正，使其滿足適應度的條件。

在無限總體的確定性復制子模型和Fudenberg及Harris的隨機復制子模型[18]中，總體的動態演化過程是由每個策略的適應度和平均適應度之差決定的。因此對這些模型來說，只要ω>0，參數ω只會影響演化的速度而不會影響長期的策略選擇。而對于有限總體來說，參數ω卻會影響長期的策略選擇。當0<ω≤1時，策略的收益對適應度的影響較小，因此節點在選擇策略時策略的收益對選擇影響較小，稱為弱選擇；當ω=0時，節點在選擇策略時完全不考慮收益，此時節點完全隨機選擇策略，稱為中性選擇；當ω=1時，節點在選擇策略時只考慮收益，對應于經典博弈的完全理性，稱為強選擇，也稱完全選擇。選擇強度ω的引入，使得Wright-Fisher過程具有了有限理性的特性。

定義2 在不考慮自身博弈情況的WSNs節點信任博弈中，信任策略的適應度為fi=1-ω+ωFi，不信任策略的適應度為gi=1-ω+ωGi，其中i為選擇信任策略的節點數量，Fi為WSNs節點在博弈時選擇信任策略的收益且：

Gi為WSNs節點在博弈時選擇不信任策略的收益且：

ω∈[0,1]為收益對適應度的選擇強度，z為常數使得收益函數為非負數。

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

1) 每個節點都會生成相同數量的多個選擇相同策略的后代，這些后代完全繼承父代節點選擇的策略，構成一個數量為N的整數倍個后代的集合；

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

記X(n)為選擇信任策略的節點在第n代時的數量，則X(n)是一個狀態空間為{0,1,…,N}的馬爾可夫鏈，其中狀態{1,…,N-1}為轉移態，狀態0和狀態N為吸收態。對于任意初始狀態的WSNs節點，在經過有限次博弈后，一定會達到某一吸收態并不再改變博弈策略。

定義3 WSNs節點信任博弈中，在一次博弈后的策略更新時，選擇信任策略的節點數量從i變化到j的概率為：

(4)

2.3 隨機動力學分析

由于Wright-Fisher過程是在總體數量有限情況下的隨機過程，因此在N較大時，假設t時刻時選擇信任策略的節點在總體的比例為x，x∈[0,1]，又因演化博弈的更新時間步長為Δt，所以可通過Langevin方程[19]來近似代替表示x關于時間t的變化率，有：

(5)

由定義1-定義3有：

(6)

(7)

(8)

v(x)→0

(9)

其中f=1-ω+ω[x(z+GT+GC-2C)+(1-x)(z+GT-C-L)]，g=1-ω+ω[x(z+GC+GD-C-β)+(1-x)(z+GD-β)]。

將式(6)和式(7)代入式(5)可得選擇信任策略節點比例的動態方程：

(10)

其中f=1-ω+ω[x(z+GT+GC-2C)+(1-x)(z+GT-C-L)]，g=1-ω+ω[x(z+GC+GD-C-β)+(1-x)(z+GD-β)]。

演化博弈的演化穩定狀態x*具有穩定性，能夠對微小的擾動具有健壯性，這個性質對應于微分方程的穩定性定理，因此以上兩個解還需滿足F′(x)<0才能成為演化穩定狀態。

F′(x)= {[(1-x)H(x)-xH(x)+x(1-x)H′(x)]K(x)-

x(1-x)H(x)K′(x)}/[Δt·K2(x)]

將F(x)=0的兩個解代入可得：

=(GD-GT+C+β)/(1-ω+ω(z+GT+GC-2C))

定理1表明：WSNs中的節點在進行信任博弈時，若滿足定理1的條件，那么對于兩個進行博弈的節點來說，選擇不信任策略的收益總是大于選擇信任策略的收益，因此節點在進行下一次博弈的策略更新時，均會更趨向于選擇不信任策略。也就是說，不信任策略是嚴格占優且演化穩定的，無論WSNs的節點選擇兩個策略的初始比例如何，經過一定次數的博弈，絕大部分節點最終都會選擇不信任策略且保持不變。

定理2表明：WSNs中的節點在進行信任博弈時，若滿足定理2的條件，那么對于兩個進行博弈的節點來說，選擇信任策略的收益總是大于選擇不信任策略的收益，因此節點在進行下一次博弈的策略更新時，均會更趨向于選擇信任策略。也就是說，信任策略是嚴格占優且演化穩定的，無論WSNs的節點選擇兩個策略的初始比例如何，經過一定次數的博弈，絕大部分節點最終都會選擇信任策略且保持不變。

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

3 實驗分析

3.1 定理驗證實驗

本文的實驗環境為Matlab R2012b。實驗設定WSNs節點信任博弈中的不同參數，分別滿足定理1和定理2的條件，來驗證WSNs節點信任博弈中的演化穩定策略。實驗共設定兩組參數，在第一組中，GT=8，Gc=6，GD=3，C=8，L=4，β=2，z=4，ω=0.9；在第二組中，GT=18，Gc=6，GD=3，C=8，L=4，β=2，z=4，ω=0.9。實驗結果如圖1所示。

圖1 信任演化曲線

3.2 影響因子驗證實驗

實驗中分別使用不同數值的懲罰因子β和選擇強度ω來觀察其對WSNs節點信任博弈的影響，并根據實驗結果給出優化WSNs節點信任博弈的對策。本實驗共設2組，第1組分析懲罰因子β對定理2的影響，第2組分析選擇強度ω對定理2的影響。

1) 懲罰因子β的影響

實驗設定：GT=18，Gc=6，GD=3，C=8，L=4，z=4，ω=0.9，β分別設定為3和2。兩組數據均滿足定理2，實驗結果如圖2所示。

圖2 懲罰因子對定理2的影響

2) 選擇強度ω的影響

實驗設定：GT=18，Gc=6，GD=3，C=8，L=4，β=2，z=4，ω分別設定為0.4和0.9。兩組數據均滿足定理2，實驗結果如圖3所示。

圖3 選擇強度對定理2的影響

4 結 語

節點間的信任問題是WSNs節點進行相互協作的重要基礎，促進WSNs節點互相信任能夠促使整個WSNs網絡快速、穩健地達到穩定狀態。本文根據WSNs中節點數量有限等特點，引入與節點信任相關的懲罰機制，提出了基于Wright-Fisher過程的WSNs節點信任隨機演化策略，彌補了復制子動態不適用于節點數量有限的WSNs中的缺陷，使WSNs節點信任博弈策略更符合實際情況。在此基礎之上，對隨機演化博弈模型進行了動力學分析，得出并證明了WSNs節點信任博弈達到演化穩定狀態的定理。經過分析與實驗驗證了結論：提高節點選擇不信任策略的懲罰力度和節點選擇信任策略的選擇強度均能有效促進WSNs節點的互信程度，實現網絡的安全與穩定。本文提出的基于Wright-Fisher過程的WSNs節點信任隨機演化策略，為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,Pellegrini F D,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,1535.

[7] Li Y,Xu H,Cao Q,et al.Evolutionary Game-Based Trust Strategy Adjustment among Nodes in Wireless Sensor Networks[J].International Journal of Distributed Sensor Networks,2015,2015:818903.

[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] Yin G,Wang Y,Dong Y,et al.Wright-Fisher multi-strategy trust evolution model with white noise for Internetware[J].Expert Systems with Applications,2013,40(18):7367-7380.

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

[12] 王元卓,于建業,邱雯,等.網絡群體行為的演化博弈模型與分析方法[J].計算機學報,2015,38(2):282-300.

[13] Fudenberg D,Tirole J.博弈論[M].姚洋校,等,譯.北京：中國人民大學出版社,2010.

[14] Weibull J W.演化博弈論[M].王永欽,譯.上海：上海人民出版社,2006:40-86.

[15] Moran P A P.The Statistical Processes of Evolutionary Theory[M].Oxford:Clarendon Press,1962.

[16] Traulsen A,Claussen J C,Hauert C.Coevolutionary dynamics:from finite to infinite populations[J].Physical Review Letters,2005,95(23):238701.

[17] 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.

[18] Fudenberg D,Harris C.Evolutionary dynamics with aggregate shocks[J].Journal of Economic Theory,1992,57(2):420-441.

[19] 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.

STOCHASTIC EVOLUTIONARY TRUST STRATEGY OF WSNS NODES BASED ON WRIGHT-FISHER PROCESS

Wang Ding1Cao Qiying1*Xu Hongyun2Shen Shigen3,4

1(CollegeofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620,China)2(CollegeofInformationScienceandTechnology,DonghuaUniversity,Shanghai201620,China)3(DepartmentofComputerScienceandEngineering,ShaoxingUniversity,Shaoxing312000,Zhejiang,China)4(CollegeofMathematics,PhysicsandInformationEngineering,JiaxingUniversity,Jiaxing314001,Zhejiang,China)

To solve the problem of trust decisions among WSNs nodes which affects the cooperation between nodes,considering limited numbers of nodes and individual stochastic effect,a stochastic evolutionary trust strategy of WSNs nodes based on Wright-Fisher process is proposed,and a punishment mechanism related to the trust level of nodes is also introduced.The strategy remedied the defect that replicator dynamics was inapplicable to the WSNs due to the limited numbers of nodes.Theorems of arriving at the evolutionary stable state were deduced and proved through the analysis of stochastic dynamics.Experiments verified the conclusions and analyzed the impacts of punishment levels and selection intensities.

Wireless sensor networks(WSNs) Trust Wright-Fisher process Stochastic evolutionary game Punishment mechanism

2015-10-28。國家自然科學基金項目(61272034)。王丁，碩士生，主研領域：無線傳感器網絡，博弈論。曹奇英，教授。許洪云，博士生。沈士根，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.01.020