基于演化博弈模型的群智感知網(wǎng)絡(luò)激勵(lì)機(jī)制*

趙宇紅，包鳳蓮，2

(1.內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010；2.包鋼集團(tuán)第三職工醫(yī)院，內(nèi)蒙古 包頭 014010)

隨著移動群智感知[1]技術(shù)的出現(xiàn)，人們利用智能終端感知周圍環(huán)境信息.在參與者參與感知任務(wù)時(shí)，若由于智能終端設(shè)備自身資源及其持有者的個(gè)人意愿，終端參與者不積極主動參與感知任務(wù)及數(shù)據(jù)內(nèi)容的共享，將導(dǎo)致無法向服務(wù)平臺上傳已經(jīng)整合高質(zhì)量的數(shù)據(jù).為解決上述問題，構(gòu)建有效的激勵(lì)模型[2]，促使盡可能多的用戶參與到感知活動中，確保感知任務(wù)按時(shí)按需完成并分享高質(zhì)量的數(shù)據(jù).本文將演化博弈中“適者生存”的基本思想應(yīng)用到移動群智感知中，激勵(lì)用戶積極參與協(xié)作、分享數(shù)據(jù)，最終達(dá)到均衡及系統(tǒng)穩(wěn)定狀態(tài).

1 相關(guān)工作

目前，常用移動群智感知激勵(lì)機(jī)制主要分為基于報(bào)酬和非報(bào)酬2種形式.基于報(bào)酬激勵(lì)機(jī)制主要通過服務(wù)平臺向提供感知服務(wù)的參與者支付報(bào)酬；非報(bào)酬的激勵(lì)機(jī)制又可分為信譽(yù)值激勵(lì)[3-6]、游戲娛樂形式激勵(lì)[7，8]、虛擬貨幣激勵(lì)[9-11]等.REDDY S等[12]定義了一套指標(biāo)來評估激勵(lì)措施的有效性，通過鼓勵(lì)數(shù)據(jù)收集過程來完成競爭支付，但其在空間和時(shí)間上需要設(shè)計(jì)合理地支付而導(dǎo)致其在具體應(yīng)用中具有一定的局限性.ZHAN Y等[13]利用博弈論的知識將參與者和服務(wù)平臺的交互行為視為博弈過程，求出非對稱博弈納什均衡，收集感知數(shù)據(jù).邢春曉[14]提出一種基于博弈論的群智感知技術(shù)，其利用演化博弈論的基本思想，分析參與者的不同收益，篩選、學(xué)習(xí)參與者行為策略.ZHAO D等[15]提出一種在線拍賣類型的激勵(lì)機(jī)制來鼓勵(lì)移動用戶參與移動人群的感知，使我們能夠有效地收集眾多新穎的數(shù)據(jù)，該激勵(lì)機(jī)制考慮了用戶向平臺競價(jià)的場景，使用戶在各個(gè)時(shí)刻選擇合適子集情況下達(dá)到平臺最大化效用.殷麗華等[16]分別提出以平臺和用戶為中心的激勵(lì)機(jī)制，為最大化平臺效用而計(jì)算斯塔克爾伯格均衡，以用戶為中心的激勵(lì)模型采用逆向拍賣模型，提升用戶主動性.ZHANG X等[17]設(shè)計(jì)眾包激勵(lì)機(jī)制，但需要服務(wù)提供商的合作才能完成工作.方法考慮了單請求單出價(jià)模型和多請求多出價(jià)模型，并為每種模型設(shè)計(jì)了一種激勵(lì)機(jī)制，且驗(yàn)證了這些激勵(lì)機(jī)制的合理性.

現(xiàn)有激勵(lì)機(jī)制研究更多關(guān)注服務(wù)平臺收益而沒有優(yōu)先考慮參與者的收益，在移動群智感知中的激勵(lì)效果不明顯.另外，機(jī)制主要以參與者直接將數(shù)據(jù)提交到服務(wù)器平臺的方式，而沒有考慮參與者之間數(shù)據(jù)集成，提高參與者數(shù)據(jù)間的交互并得到高質(zhì)量的數(shù)據(jù)，進(jìn)而參與者間為獲取更多收益而向服務(wù)平臺上傳高質(zhì)量的集成數(shù)據(jù).基于以上問題，本文提出一種基于演化博弈的移動群智感知激勵(lì)機(jī)制(Incentive Mechanism Based on Evolutionary Game Theory, IMEG).

2 分析博弈模型及收益矩陣

目前，本文設(shè)置如下假設(shè)條件：

(1)有限理性：參與移動群智感知的所有參與人V={i，j，k…}，存在一定程度的理性.

(2)任意參與者i與j之間的博弈策略有{共享(S)，不共享(US)}2種.

(3)在演化博弈模型中，c為參與者的博弈成本，s為無論是共享還是不共享數(shù)據(jù)，參與者從服務(wù)平臺獲得的收益值，Δs為通過信息共享、交互獲得的收益值增量.

下面分析博弈過程中參與者的收益情況.若參與者i與j都選擇共享數(shù)據(jù)，那么i和j都獲得了對方的感知數(shù)據(jù)，參與者間將共享數(shù)據(jù)、融合處理，得到更多精確數(shù)據(jù)，因此，將融合數(shù)據(jù)上傳到服務(wù)平臺可獲得更多的收益s+Δs.若j采取共享策略，而i采用不共享策略，即i得到j(luò)的數(shù)據(jù)，i經(jīng)過數(shù)據(jù)間融合可獲得較高收益s+Δs，但j沒有獲得服務(wù)平臺給與的更多回報(bào)，即j的收益大小為s，此時(shí)i與j的收益分別為(s+Δs-c,s-c).相反，若i采取共享策略，但j采用不共享策略，對應(yīng)收益為(s+Δs-c,s-c).最后，i與j都在博弈中采用不共享策略，收益為(s-c,s-c).參與人在不同策略下收益情況如表1所示.

表1 博弈收益矩陣數(shù)

運(yùn)用博弈論相關(guān)知識對表1分析可知，當(dāng)節(jié)點(diǎn)j選擇數(shù)據(jù)共享時(shí)，節(jié)點(diǎn)i將獲得j的共享數(shù)據(jù)；節(jié)點(diǎn)i會通過j的共享而獲得精確的感知數(shù)據(jù)，此時(shí)，節(jié)點(diǎn)i會獲取更多的收益.相反，節(jié)點(diǎn)j卻消耗資源而沒獲取更多收益；此時(shí)會影響j采取共享策略的積極性.

為解決上述問題，提出了一種基于演化博弈激勵(lì)機(jī)制，利用演化博弈中“適者生存”的基本思想，每個(gè)參與者在博弈過程中更新、學(xué)習(xí)來更改自身的行為策略.根據(jù)不同參與者的合作度來調(diào)節(jié)博弈中不同策略收益值，進(jìn)而調(diào)整下一輪演化中參與者的博弈次數(shù)，服務(wù)平臺調(diào)整參與者收益來控制整個(gè)演化博弈過程，通過更新策略、篩選學(xué)習(xí)對象來完成整個(gè)演化博弈過程，促進(jìn)參與者間進(jìn)行合作、共享數(shù)據(jù).

3 基于演化博弈的激勵(lì)機(jī)制

激勵(lì)機(jī)制的核心構(gòu)建演化博弈模型、更新行為策略，篩選學(xué)習(xí)對象.

3.1 構(gòu)建演化博弈模型

演化博弈模型可表示為一個(gè)三元組，∏={P，S，u}，其中博弈參與人集合為P={i，j}，i，j為網(wǎng)絡(luò)中任意的兩個(gè)參與者；節(jié)點(diǎn)的策略空間為S={Si，Sj}；節(jié)點(diǎn)的效用函數(shù)為u={ui，uj}.

本文將參與者間的合作度[18]引入演化博弈模型，將合作度作為懲戒因子來激勵(lì)參與者行為.合作度的高低會影響參與者間的博弈成本，模型根據(jù)參與者間的不同懲戒因子來動態(tài)調(diào)整博弈成本.假設(shè)當(dāng)前時(shí)間段內(nèi)有w輪博弈過程，則每輪博弈合作度可表示{x1，x2，x3，…，xw}，那么最近一段時(shí)間合作度如式(1)所示：

(1)

式中：y(k)∈[0，1]為衰減函數(shù)；α為博弈成本c的調(diào)整系數(shù)，如式(2)所示：

α=1+η-z.

(2)

式中：η為節(jié)點(diǎn)未來期望的大小，0<η<1；當(dāng)z=1時(shí)，博弈成本αc=ηc；當(dāng)z=0時(shí)，此時(shí)博弈成本最大αc=(1+η)c.

由于參與者的收益值為服務(wù)感知平臺向參與者支付的報(bào)酬，即服務(wù)平臺的總支出即為所有參與者的總收益和.但是實(shí)際應(yīng)用場景中的服務(wù)平臺預(yù)算并不是無限的，所以定義β來調(diào)整收益(s+Δs)并控制平臺支付的收益，收益調(diào)整系數(shù)β為式(3)：

(3)

分析演化博弈模型，可以得到其收益矩陣，如表2所示.

表2 初始化條件方法間的錯(cuò)誤關(guān)聯(lián)系數(shù)

根據(jù)演化博弈論中“適者生存”的基本思想來設(shè)置博弈的基本過程，也就是說應(yīng)鼓勵(lì)數(shù)據(jù)共享的演化行為，而對參與者間不共享數(shù)據(jù)的行為加以懲罰.演化博弈模型在經(jīng)過一輪演化博弈后，計(jì)算各個(gè)參與者收益；節(jié)點(diǎn)是否進(jìn)入下一輪博弈收到平均收益的影響.其計(jì)算方法如式(4)所示.

(4)

式中：fi,m為第m輪博弈中參與者間的博弈次數(shù)；ui,m為第m輪博弈參與者的收益值；um為參與者的平均收益；nm為參與者數(shù)量.其計(jì)算方式為式(5)；

(5)

若群智感知網(wǎng)絡(luò)中的某一參與者長時(shí)間不與其他參與者共享數(shù)據(jù)，導(dǎo)致其無法獲取更多的收益，此時(shí)節(jié)點(diǎn)將會被孤立、參加博弈次數(shù)會減少，那么該參與者將會改變自身行為策略.下面介紹參與者間的策略更新和對象學(xué)習(xí)的過程.

3.2 更新行為策略

在現(xiàn)實(shí)生活中，若當(dāng)前參與者的收益明顯高于鄰居平均收益，則參與者改變自身行為策略的動力較小.相反，參與者則會為獲取更多博弈收益而盡快改變行為策略.參與者可以根據(jù)參加博弈過程獲取收益值的大小來確定是否更新自身策略.本文根據(jù)費(fèi)米規(guī)則[19]定義了參與者更新策略規(guī)則pi，如式(6)所示：

Pi(Si→Sj)=

(6)

我們認(rèn)為當(dāng)前參與者對于其他參與者的不共享數(shù)據(jù)行為具有一定程度的容忍，參與者受博弈收益的影響而改變自身策略的概率為prepi，計(jì)算如式(7)所示.

(7)

式中：ri為參與者i被其他參與者拒絕的次數(shù)；Ni為參與者i對拒絕次數(shù)的容忍程度.γ，ε分別為收益和被拒絕次數(shù)的影響因子，γ∈[0，1]，ε∈[0，1]，在群智感知網(wǎng)絡(luò)中，根據(jù)相關(guān)研究認(rèn)為被拒絕次數(shù)是參與者改變自身策略的主因，在文中根據(jù)群智感知網(wǎng)絡(luò)中參與者和感知平臺的具體情況來設(shè)置相應(yīng)的值.

3.3 學(xué)習(xí)對象篩選方法

當(dāng)參與者確認(rèn)修改策略后，其需要篩選學(xué)習(xí)對象.首先，對所有參與者的合作度進(jìn)行排序，每個(gè)鄰居被選中的概率與其自身的合作度相關(guān)，之后，選擇所有符合要求的參與者作為學(xué)習(xí)對象的集合.在某個(gè)時(shí)刻t參與者i選擇鄰居進(jìn)入其學(xué)習(xí)對象集合{qi(t)}的計(jì)算方法，如式(8)所示.

(8)

假設(shè)系統(tǒng)中參與者的總數(shù)為n；初始收益矩陣中的收入s+Δs和博弈成本c為正整數(shù)；初始博弈次數(shù)為f.基于演化博弈的群智感知激勵(lì)機(jī)制步驟如下：

(1)初始化博弈次數(shù)f，演化博弈輪數(shù)j=1；

(2)在感知平臺中，參與者間博弈f次；

(4)調(diào)整收入s+Δs→β(s+Δs)，c→αc，調(diào)整每個(gè)參與者在下一輪的博弈次數(shù)f→fi,j+1；

(5)確認(rèn)更改行為策略后，根據(jù)式(6)選擇更改對象集合并從中隨機(jī)選擇一個(gè)對象，更新策略集合；

(6)博弈輪數(shù)j=j+1，重復(fù)步驟(3)至(6)，直至系統(tǒng)穩(wěn)定.

4 仿真實(shí)驗(yàn)分析

本實(shí)驗(yàn)采用MATLAB對所提模型進(jìn)行仿真.首先，測試系統(tǒng)的基本性能，其次，將所提出的模型與其他模型在用戶平均效用、任務(wù)覆蓋率和平臺效用[20]這3個(gè)方面進(jìn)行比較.假設(shè)該系統(tǒng)中共有m個(gè)參與者，γ和ε的值分別設(shè)置為0.25和0.75；期望收益因子η=0.3；初始合作度z=0.5；初始博弈次數(shù)f=150.為了驗(yàn)證本文所提IMEG機(jī)制的性能，將其分別與文獻(xiàn)[17]中的TRAC機(jī)制及文獻(xiàn)[19]中的IMC-SS機(jī)制進(jìn)行對比.

4.1 系統(tǒng)穩(wěn)定性

圖1在m=500，uth=1×106和uth=1.5×106的情況下，用戶總收益同迭代次數(shù)的曲線圖.當(dāng)前期平臺的總支出小于預(yù)算值時(shí)，博弈收益值隨著博弈次數(shù)而增加，因此前期總收益也漸增.相反，參與者總收益降低.最終平臺預(yù)算范圍內(nèi)用戶總收益達(dá)到最大值，并趨于穩(wěn)定.

4.2 參與者平均效用

圖2顯示不同激勵(lì)機(jī)制下參與者平均效用對比圖.在圖2(a)中隨著任務(wù)數(shù)的增多，用戶平均效用趨于穩(wěn)定.主要是由于感知平臺初期發(fā)布的任務(wù)數(shù)較少，導(dǎo)致參與者間存在較強(qiáng)的競爭關(guān)系，感知平臺為較少參與者支付報(bào)酬.因此參與者平均效用較高.相反，參與者平均效用降低.在圖2(b)中用戶平均效用隨著任務(wù)總額的增加而升高；用戶平均效用隨著參與者數(shù)量的增加而提高；隨著用戶任務(wù)數(shù)的飽和，用戶平均效用趨于穩(wěn)定.TRAC和IMC-SS收益值受到競價(jià)和任務(wù)數(shù)影響.由于IMEG收益受到支付累加效應(yīng)的影響，所有其積極性相對較高.

4.3 任務(wù)覆蓋率

圖3中顯示群智感知網(wǎng)絡(luò)中，任務(wù)數(shù)和用戶數(shù)對任務(wù)覆蓋率的影響.通過分析圖3(a)，3(b)可以發(fā)現(xiàn)，IMC-SS較IMEG機(jī)制任務(wù)覆蓋率低.而TRAC任務(wù)覆蓋率較低的主要原因是當(dāng)用戶數(shù)接近任務(wù)數(shù)量時(shí)，TRAC只選競價(jià)低、上報(bào)任務(wù)數(shù)多的用戶.綜合分析各種激勵(lì)機(jī)制，IMEG激勵(lì)機(jī)制下任務(wù)覆蓋率較高.

4.4 平臺效用

從圖4(a)中可以看出，IMEG和IMC-SS機(jī)制下的平臺效用呈遞增趨勢.但I(xiàn)MEG平臺效用相對較低，主要原因?yàn)镮MEG動態(tài)調(diào)整平臺的剩余收益.TRAC模型中平臺效用隨任務(wù)數(shù)的增加而先增后減.

在圖4(b)中3種激勵(lì)機(jī)制，群智感知網(wǎng)絡(luò)中的平臺效用均為先遞增后趨于平衡，出現(xiàn)此現(xiàn)象的主要原因?yàn)槠脚_效用是隨著參與者數(shù)量的的增多而提高；當(dāng)參與者完成已經(jīng)發(fā)布的感知任務(wù)時(shí)，其感知平臺效用趨于穩(wěn)定.

5 結(jié)論

針對移動群智感知網(wǎng)絡(luò)中用戶參與感知活動積極性不高及用戶間數(shù)據(jù)共享性問題，提出在群智感知網(wǎng)絡(luò)中基于演化博弈的激勵(lì)機(jī)制.該模型利用演化博弈的理論，對每個(gè)參與者在博弈過程中更新、學(xué)習(xí)來更改策略.根據(jù)參與者合作度調(diào)整用戶收益值；調(diào)整下輪演化博弈的次數(shù)；調(diào)整用戶收益控制演化博弈過程；更新策略、篩選學(xué)習(xí)對象，完成整個(gè)演化博弈過程，促進(jìn)參與者協(xié)作,共享數(shù)據(jù).實(shí)驗(yàn)表明，本文的激勵(lì)機(jī)制可使平臺在一定的成本預(yù)算約束的情況下獲得較高的任務(wù)覆蓋率，有效提高用戶效用和平臺效用，激勵(lì)參與者間合作、數(shù)據(jù)共享.