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

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

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

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

0 引 言

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

近幾年來(lái)，已有許多學(xué)者使用演化博弈論的方法來(lái)分析網(wǎng)絡(luò)中的一些矛盾問(wèn)題。文獻(xiàn)[2]分析了無(wú)限總體演化博弈的演化穩(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ù)對(duì)演化均衡的影響。在WSNs研究領(lǐng)域，文獻(xiàn)[4]提出了一種基于演化博弈的資源控制協(xié)議，用于緩解WSNs內(nèi)資源競(jìng)爭(zhēng)矛盾。文獻(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ò)不可靠因素對(duì)模型的影響。

上述文獻(xiàn)所用的演化博弈模型大都是針對(duì)無(wú)限總體的對(duì)象模型，而實(shí)際情況中的研究對(duì)象一般都是有限總體。針對(duì)這個(gè)問(wèn)題，學(xué)者們將隨機(jī)過(guò)程應(yīng)用到演化博弈，形成了以有限總體為研究對(duì)象的隨機(jī)演化博弈。文獻(xiàn)[8]研究了服務(wù)提供商面對(duì)軟硬件服務(wù)攻擊時(shí)的安全和可信機(jī)制，提出了一種適用于虛擬傳感器服務(wù)的安全、可信的隨機(jī)演化聯(lián)合博弈防御框架。文獻(xiàn)[9]針對(duì)網(wǎng)構(gòu)軟件中存在的服務(wù)問(wèn)題，將網(wǎng)構(gòu)軟件的服務(wù)差異化，并把基于Wright-Fisher過(guò)程的兩策略博弈拓展到多策略，提出了一種博弈參與者具有多個(gè)策略的信任演化博弈模型。文獻(xiàn)[10]針對(duì)網(wǎng)構(gòu)軟件的服務(wù)質(zhì)量QoS問(wèn)題，在文獻(xiàn)[9]的基礎(chǔ)上考慮了白噪聲對(duì)博弈模型的影響，構(gòu)建了帶有白噪聲的多策略Wright-Fisher過(guò)程信任演化博弈模型。文獻(xiàn)[11]把Moran過(guò)程應(yīng)用到無(wú)線網(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過(guò)程的隨機(jī)演化博弈模型來(lái)分析無(wú)線傳感器網(wǎng)絡(luò)中存在的節(jié)點(diǎn)信任問(wèn)題。數(shù)量有限的WSNs節(jié)點(diǎn)在選擇信任與否時(shí)體現(xiàn)出了重復(fù)性、有限理性等特征，而對(duì)于整個(gè)WSNs來(lái)說(shuō)，其目標(biāo)是在達(dá)到總體收益較高狀態(tài)的同時(shí)也能夠保持足夠的穩(wěn)健性，這些特征恰好滿足隨機(jī)演化博弈的要求。據(jù)此，本文建立了WSNs節(jié)點(diǎn)信任演化策略，使節(jié)點(diǎn)在無(wú)外界干預(yù)的情況下動(dòng)態(tài)演化，各個(gè)節(jié)點(diǎn)根據(jù)Wright-Fisher機(jī)制自行調(diào)整下一次博弈的策略，使WSNs逐漸演化到穩(wěn)定狀態(tài)。在到達(dá)演化穩(wěn)定狀態(tài)之后，WSNs中的絕大部分節(jié)點(diǎn)將會(huì)選擇信任策略并保持不變。在信任演化[5]的基礎(chǔ)上，通過(guò)考慮WSNs中有限節(jié)點(diǎn)數(shù)量的情況，引入懲罰機(jī)制來(lái)構(gòu)造信任博弈模型，并利用Wright-Fisher過(guò)程來(lái)分析節(jié)點(diǎn)信任演化動(dòng)態(tài)，使WSNs節(jié)點(diǎn)信任策略更趨近真實(shí)狀況，并得出到達(dá)演化穩(wěn)定狀態(tài)的定理，分析影響到達(dá)演化穩(wěn)定狀態(tài)的影響因子。

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

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

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

(1)

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

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

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

(2)

(3)

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

2.1 博弈模型

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

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

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

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

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

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

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

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

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

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

表1 一次博弈收益矩陣

2.2 引入Wright-Fisher過(guò)程

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

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

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

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

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

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

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

定義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)在博弈時(shí)選擇信任策略的收益且：

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

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

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

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

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

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

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

(4)

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

由于Wright-Fisher過(guò)程是在總體數(shù)量有限情況下的隨機(jī)過(guò)程，因此在N較大時(shí)，假設(shè)t時(shí)刻時(shí)選擇信任策略的節(jié)點(diǎn)在總體的比例為x，x∈[0,1]，又因演化博弈的更新時(shí)間步長(zhǎng)為Δt，所以可通過(guò)Langevin方程[19]來(lái)近似代替表示x關(guān)于時(shí)間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)比例的動(dòng)態(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ū)ξ⑿〉臄_動(dòng)具有健壯性，這個(gè)性質(zhì)對(duì)應(yīng)于微分方程的穩(wěn)定性定理，因此以上兩個(gè)解還需滿足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的兩個(gè)解代入可得：

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

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

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

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

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的條件，來(lái)驗(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)度ω來(lái)觀察其對(duì)WSNs節(jié)點(diǎn)信任博弈的影響，并根據(jù)實(shí)驗(yàn)結(jié)果給出優(yōu)化WSNs節(jié)點(diǎn)信任博弈的對(duì)策。本實(shí)驗(yàn)共設(shè)2組，第1組分析懲罰因子β對(duì)定理2的影響，第2組分析選擇強(qiáng)度ω對(duì)定理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 懲罰因子對(duì)定理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)度對(duì)定理2的影響

4 結(jié) 語(yǔ)

節(jié)點(diǎn)間的信任問(wèn)題是WSNs節(jié)點(diǎn)進(jìn)行相互協(xié)作的重要基礎(chǔ)，促進(jìn)WSNs節(jié)點(diǎn)互相信任能夠促使整個(gè)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過(guò)程的WSNs節(jié)點(diǎn)信任隨機(jī)演化策略，彌補(bǔ)了復(fù)制子動(dòng)態(tài)不適用于節(jié)點(diǎn)數(shù)量有限的WSNs中的缺陷，使WSNs節(jié)點(diǎn)信任博弈策略更符合實(shí)際情況。在此基礎(chǔ)之上，對(duì)隨機(jī)演化博弈模型進(jìn)行了動(dòng)力學(xué)分析，得出并證明了WSNs節(jié)點(diǎn)信任博弈達(dá)到演化穩(wěn)定狀態(tài)的定理。經(jīng)過(guò)分析與實(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過(guò)程的WSNs節(jié)點(diǎn)信任隨機(jī)演化策略，為WSNs節(jié)點(diǎn)信任和協(xié)作問(wèn)題研究提供了理論依據(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信任決策模型與動(dòng)力學(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過(guò)程的無(wú)線網(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].姚洋校,等,譯.北京：中國(guó)人民大學(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。國(guó)家自然科學(xué)基金項(xiàng)目(61272034)。王丁，碩士生，主研領(lǐng)域：無(wú)線傳感器網(wǎng)絡(luò)，博弈論。曹奇英，教授。許洪云，博士生。沈士根，教授。

TP393

A

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