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

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

基于Wright-Fisher過程的WSNs節(jié)點(diǎn)信任隨機(jī)演化策略

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

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

為解決無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間的信任影響節(jié)點(diǎn)協(xié)作的問題，考慮到節(jié)點(diǎn)數(shù)量有限及個體隨機(jī)性，基于Wright-Fisher過程的隨機(jī)演化博弈，提出WSNs節(jié)點(diǎn)信任隨機(jī)演化策略，并加入與節(jié)點(diǎn)信任相關(guān)的懲罰機(jī)制。該策略彌補(bǔ)了復(fù)制子動態(tài)不適用于節(jié)點(diǎn)數(shù)量有限的WSNs節(jié)點(diǎn)信任演化建模問題，經(jīng)過隨機(jī)動力學(xué)分析，推導(dǎo)并證明了達(dá)到演化穩(wěn)定狀態(tài)的定理。最后通過實(shí)驗(yàn)驗(yàn)證定理并分析懲罰力度和選擇強(qiáng)度對演化穩(wěn)定狀態(tài)的影響。

無線傳感器網(wǎng)絡(luò) 信任 Wright-Fisher過程 隨機(jī)演化博弈 懲罰機(jī)制

0 引 言

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

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

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

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

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

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

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

(1)

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

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

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

(2)

(3)

2 WSNs節(jié)點(diǎn)信任演化策略

2.1 博弈模型

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

記GT表示當(dāng)前節(jié)點(diǎn)信任交互的對方節(jié)點(diǎn)而成功幫助對方轉(zhuǎn)發(fā)數(shù)據(jù)包帶來的收益；GC表示因?qū)Ψ焦?jié)點(diǎn)信任當(dāng)前節(jié)點(diǎn)，幫助轉(zhuǎn)發(fā)了當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)包，當(dāng)前節(jié)點(diǎn)所獲得的收益；GD表示當(dāng)前節(jié)點(diǎn)因選擇不信任策略，不幫助對方轉(zhuǎn)發(fā)數(shù)據(jù)包，節(jié)省了能量，從而延長了節(jié)點(diǎn)的生存周期所獲得的收益；C表示當(dāng)前節(jié)點(diǎn)向?qū)Ψ焦?jié)點(diǎn)發(fā)送自身的數(shù)據(jù)包或幫助轉(zhuǎn)發(fā)對方節(jié)點(diǎn)的數(shù)據(jù)包所產(chǎn)生的傳輸成本；L表示當(dāng)前節(jié)點(diǎn)所發(fā)送的源數(shù)據(jù)包未能成功到達(dá)目的地而造成的損耗；β表示當(dāng)前節(jié)點(diǎn)因選擇了不信任策略而受到的懲罰損耗。

下面對各種可能發(fā)生的交互狀態(tài)分別進(jìn)行討論：

(1) 兩個節(jié)點(diǎn)在進(jìn)行交互時均選擇了信任策略

此時雙方節(jié)點(diǎn)均會轉(zhuǎn)發(fā)對方的數(shù)據(jù)包并向?qū)Ψ桨l(fā)送自身的數(shù)據(jù)包，獲得收益GT+GC，并消耗了發(fā)送兩次數(shù)據(jù)包的成本2C，因此雙方節(jié)點(diǎn)的收益均為:GT+GC-2C。

(2) 兩個節(jié)點(diǎn)在進(jìn)行交互時有一個節(jié)點(diǎn)選擇了信任策略，而另一個節(jié)點(diǎn)選擇了不信任策略

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

(3) 兩個節(jié)點(diǎn)在進(jìn)行交互時均選擇了不信任策略

由于兩個節(jié)點(diǎn)都不信任對方節(jié)點(diǎn)，因此節(jié)點(diǎn)之間不會向?qū)Ψ焦?jié)點(diǎn)發(fā)送數(shù)據(jù)包或轉(zhuǎn)發(fā)對方數(shù)據(jù)包，兩個節(jié)點(diǎn)都節(jié)省能量獲得收益GD，但受到選擇不信任策略的懲罰從而均損失了β，因此兩個節(jié)點(diǎn)的收益均為：GD-β。

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

表1 一次博弈收益矩陣

2.2 引入Wright-Fisher過程

在經(jīng)典的演化博弈中，演化穩(wěn)定策略和復(fù)制子動態(tài)方程都是基于博弈個體的數(shù)量是無限多且不同策略的個體均勻分布的假設(shè)。但對于參與者數(shù)量有限的博弈，整個系統(tǒng)的狀態(tài)將成為離散點(diǎn)的集合，因此微分方程將不再適用于離散狀態(tài)的隨機(jī)演化博弈。

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

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

任一節(jié)點(diǎn)選擇不信任策略的期望收益為：

假設(shè)在演化博弈中，收益函數(shù)對該策略適應(yīng)度的影響因子為ω，ω∈[0,1]，則在WSNs節(jié)點(diǎn)信任博弈中，信任策略的適應(yīng)度為：

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

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

定義2 在不考慮自身博弈情況的WSNs節(jié)點(diǎn)信任博弈中，信任策略的適應(yīng)度為fi=1-ω+ωFi，不信任策略的適應(yīng)度為gi=1-ω+ωGi，其中i為選擇信任策略的節(jié)點(diǎn)數(shù)量，F(xiàn)i為WSNs節(jié)點(diǎn)在博弈時選擇信任策略的收益且：

Gi為WSNs節(jié)點(diǎn)在博弈時選擇不信任策略的收益且：

ω∈[0,1]為收益對適應(yīng)度的選擇強(qiáng)度，z為常數(shù)使得收益函數(shù)為非負(fù)數(shù)。

WSNs的節(jié)點(diǎn)在進(jìn)行下一次博弈之前，會進(jìn)行以下步驟更新策略：

1) 每個節(jié)點(diǎn)都會生成相同數(shù)量的多個選擇相同策略的后代，這些后代完全繼承父代節(jié)點(diǎn)選擇的策略，構(gòu)成一個數(shù)量為N的整數(shù)倍個后代的集合；

3) 新一代后代完全替換上一代，完成節(jié)點(diǎn)的一代更新。

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

定義3 WSNs節(jié)點(diǎn)信任博弈中，在一次博弈后的策略更新時，選擇信任策略的節(jié)點(diǎn)數(shù)量從i變化到j(luò)的概率為：

(4)

2.3 隨機(jī)動力學(xué)分析

由于Wright-Fisher過程是在總體數(shù)量有限情況下的隨機(jī)過程，因此在N較大時，假設(shè)t時刻時選擇信任策略的節(jié)點(diǎn)在總體的比例為x，x∈[0,1]，又因演化博弈的更新時間步長為Δt，所以可通過Langevin方程[19]來近似代替表示x關(guān)于時間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)可得選擇信任策略節(jié)點(diǎn)比例的動態(tài)方程：

(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-β)]。

演化博弈的演化穩(wěn)定狀態(tài)x*具有穩(wěn)定性，能夠?qū)ξ⑿〉臄_動具有健壯性，這個性質(zhì)對應(yīng)于微分方程的穩(wěn)定性定理，因此以上兩個解還需滿足F′(x)<0才能成為演化穩(wěn)定狀態(tài)。

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中的節(jié)點(diǎn)在進(jìn)行信任博弈時，若滿足定理1的條件，那么對于兩個進(jìn)行博弈的節(jié)點(diǎn)來說，選擇不信任策略的收益總是大于選擇信任策略的收益，因此節(jié)點(diǎn)在進(jìn)行下一次博弈的策略更新時，均會更趨向于選擇不信任策略。也就是說，不信任策略是嚴(yán)格占優(yōu)且演化穩(wěn)定的，無論WSNs的節(jié)點(diǎn)選擇兩個策略的初始比例如何，經(jīng)過一定次數(shù)的博弈，絕大部分節(jié)點(diǎn)最終都會選擇不信任策略且保持不變。

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

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

3 實(shí)驗(yàn)分析

3.1 定理驗(yàn)證實(shí)驗(yàn)

本文的實(shí)驗(yàn)環(huán)境為Matlab R2012b。實(shí)驗(yàn)設(shè)定WSNs節(jié)點(diǎn)信任博弈中的不同參數(shù)，分別滿足定理1和定理2的條件，來驗(yàn)證WSNs節(jié)點(diǎn)信任博弈中的演化穩(wěn)定策略。實(shí)驗(yàn)共設(shè)定兩組參數(shù)，在第一組中，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。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 信任演化曲線

3.2 影響因子驗(yàn)證實(shí)驗(yàn)

實(shí)驗(yàn)中分別使用不同數(shù)值的懲罰因子β和選擇強(qiáng)度ω來觀察其對WSNs節(jié)點(diǎn)信任博弈的影響，并根據(jù)實(shí)驗(yàn)結(jié)果給出優(yōu)化WSNs節(jié)點(diǎn)信任博弈的對策。本實(shí)驗(yàn)共設(shè)2組，第1組分析懲罰因子β對定理2的影響，第2組分析選擇強(qiáng)度ω對定理2的影響。

1) 懲罰因子β的影響

實(shí)驗(yàn)設(shè)定：GT=18，Gc=6，GD=3，C=8，L=4，z=4，ω=0.9，β分別設(shè)定為3和2。兩組數(shù)據(jù)均滿足定理2，實(shí)驗(yàn)結(jié)果如圖2所示。

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

2) 選擇強(qiáng)度ω的影響

實(shí)驗(yàn)設(shè)定：GT=18，Gc=6，GD=3，C=8，L=4，β=2，z=4，ω分別設(shè)定為0.4和0.9。兩組數(shù)據(jù)均滿足定理2，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 選擇強(qiáng)度對定理2的影響

4 結(jié) 語

節(jié)點(diǎn)間的信任問題是WSNs節(jié)點(diǎn)進(jìn)行相互協(xié)作的重要基礎(chǔ)，促進(jìn)WSNs節(jié)點(diǎn)互相信任能夠促使整個WSNs網(wǎng)絡(luò)快速、穩(wěn)健地達(dá)到穩(wěn)定狀態(tài)。本文根據(jù)WSNs中節(jié)點(diǎn)數(shù)量有限等特點(diǎn)，引入與節(jié)點(diǎn)信任相關(guān)的懲罰機(jī)制，提出了基于Wright-Fisher過程的WSNs節(jié)點(diǎn)信任隨機(jī)演化策略，彌補(bǔ)了復(fù)制子動態(tài)不適用于節(jié)點(diǎn)數(shù)量有限的WSNs中的缺陷，使WSNs節(jié)點(diǎn)信任博弈策略更符合實(shí)際情況。在此基礎(chǔ)之上，對隨機(jī)演化博弈模型進(jìn)行了動力學(xué)分析，得出并證明了WSNs節(jié)點(diǎn)信任博弈達(dá)到演化穩(wěn)定狀態(tài)的定理。經(jīng)過分析與實(shí)驗(yàn)驗(yàn)證了結(jié)論：提高節(jié)點(diǎn)選擇不信任策略的懲罰力度和節(jié)點(diǎn)選擇信任策略的選擇強(qiáng)度均能有效促進(jìn)WSNs節(jié)點(diǎn)的互信程度，實(shí)現(xiàn)網(wǎng)絡(luò)的安全與穩(wěn)定。本文提出的基于Wright-Fisher過程的WSNs節(jié)點(diǎn)信任隨機(jī)演化策略，為WSNs節(jié)點(diǎn)信任和協(xié)作問題研究提供了理論依據(jù)。

[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信任決策模型與動力學(xué)分析[J].控制與決策,2012,27(8):1133-1138.

[6] 李紫川,沈士根,曹奇英.基于反思機(jī)制的WSNs節(jié)點(diǎn)信任演化模型[J].計(jì)算機(jī)應(yīng)用研究,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] 印桂生,王瑩潔,董宇欣,等.網(wǎng)構(gòu)軟件的Wright-Fisher多策略信任演化模型[J].軟件學(xué)報(bào),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] 馮光升,王慧強(qiáng),周沫,等.基于Moran過程的無線網(wǎng)絡(luò)接入選擇方法[J].北京郵電大學(xué)學(xué)報(bào),2014,37(4):10-14.

[12] 王元卓,于建業(yè),邱雯,等.網(wǎng)絡(luò)群體行為的演化博弈模型與分析方法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):282-300.

[13] Fudenberg D,Tirole J.博弈論[M].姚洋校,等,譯.北京：中國人民大學(xué)出版社,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。國家自然科學(xué)基金項(xiàng)目(61272034)。王丁，碩士生，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)，博弈論。曹奇英，教授。許洪云，博士生。沈士根，教授。

TP393

A

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