楊 堤 李卓青 楊綠溪 徐琴珍

（東南大學(xué)信息科學(xué)與工程學(xué)院，南京，210096）

引 言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)和應(yīng)用的迅速發(fā)展，移動(dòng)智能終端得到廣泛普及，移動(dòng)智能終端設(shè)備的應(yīng)用也更為廣泛[1-3]。對(duì)于移動(dòng)群智感知系統(tǒng)而言，用戶參與感知任務(wù)伴隨著隱私泄露的風(fēng)險(xiǎn)[4]，同時(shí)也會(huì)付出消耗資源的代價(jià)。因此，為補(bǔ)償用戶的付出，設(shè)計(jì)合理的激勵(lì)機(jī)制是當(dāng)前研究的一個(gè)熱點(diǎn)[5]。早期的研究主要集中在對(duì)用戶離線到達(dá)的場(chǎng)景建模研究[6]，Lee等對(duì)于離線場(chǎng)景的用戶提出了基于反向拍賣的動(dòng)態(tài)定價(jià)機(jī)制RADP[7]，之后又在RADP機(jī)制的基礎(chǔ)上考慮了用戶的虛擬信譽(yù)積分，設(shè)計(jì)了加入虛擬信譽(yù)分的RADP-VPC[8]的機(jī)制。在離線的場(chǎng)景下，有意愿參與感知任務(wù)的用戶，統(tǒng)一將包含其報(bào)價(jià)等資料的信息提交給平臺(tái)處理，平臺(tái)在接受完所有用戶信息之后，離線計(jì)算選擇部分用戶完成任務(wù)，并統(tǒng)一反饋選擇結(jié)果[9]。離線場(chǎng)景下的移動(dòng)群智感知應(yīng)用也受到廣泛關(guān)注。TruCentive[9]利用移動(dòng)群智感知，激勵(lì)用戶參與獲取城市停車位信息，Noisemap[10]是一款利用移動(dòng)群智感知設(shè)計(jì)的測(cè)量城市噪聲污染的軟件，Livecompare[11]為商品比價(jià)設(shè)計(jì)了一個(gè)離線的激勵(lì)機(jī)制系統(tǒng)。以上的理論和應(yīng)用的成果都基于離線的場(chǎng)景，同時(shí)針對(duì)離線問(wèn)題下的用戶提交數(shù)據(jù)質(zhì)量以及用戶信譽(yù)的的研究，也有一定的研究。Albers等[12]提出了一種計(jì)算用戶的信譽(yù)分值去衡量數(shù)據(jù)質(zhì)量的方法；Huang等[13]針對(duì)移動(dòng)群智感知問(wèn)題提出了一種信譽(yù)系統(tǒng)；Wen等[14]提出了一種研究室內(nèi)定位的質(zhì)量驅(qū)動(dòng)的激勵(lì)機(jī)制QDA。然而對(duì)于實(shí)際情況來(lái)說(shuō)，用戶并不是集中到達(dá)統(tǒng)一提交資料，并且給予系統(tǒng)足夠多的時(shí)間做出選擇決策，而是隨機(jī)在線到達(dá)的[15-17]。因此將用戶到達(dá)建模成在線的場(chǎng)景更加符合現(xiàn)實(shí)情況。Zhao等[18,19]提出了一種用戶隨機(jī)到達(dá)的在線激勵(lì)模型。該模型在任務(wù)預(yù)算有限的前提下，最大化平臺(tái)端價(jià)值收益，并首次提出了多階段采樣競(jìng)拍算法(OMZ/OMG)，該算法下，平臺(tái)需要及時(shí)給出是否選擇用戶的決斷。但是現(xiàn)有的很多在線激勵(lì)機(jī)制的設(shè)計(jì)[18,19]，忽略了對(duì)用戶提交數(shù)據(jù)的質(zhì)量的篩選考慮，導(dǎo)致任務(wù)發(fā)布方的價(jià)值收益不能達(dá)到實(shí)際預(yù)期。為此，本文考慮任務(wù)發(fā)布方對(duì)用戶的信譽(yù)評(píng)分反饋以及用戶提交數(shù)據(jù)的質(zhì)量評(píng)判，并綜合用戶的歷史和現(xiàn)實(shí)信譽(yù)情況，建立考慮信譽(yù)更新的移動(dòng)群智感知在線激勵(lì)機(jī)制，從系統(tǒng)建模、信譽(yù)評(píng)價(jià)機(jī)制以及考慮信譽(yù)更新的在線激勵(lì)機(jī)制(Reputation-updated online mechanism,ROM)算法和仿真等方面進(jìn)行闡述。

1 系統(tǒng)建模

移動(dòng)群智感知系統(tǒng)，主要有3種角色：任務(wù)發(fā)布方，平臺(tái)方和用戶。任務(wù)發(fā)布方首先向平臺(tái)方提交需要發(fā)布的一系列公開(kāi)的異構(gòu)感知任務(wù)Q={q1,q2,…,qm}，以及完成任務(wù)的總預(yù)算B和雇傭用戶的截止時(shí)間T以及一些有關(guān)質(zhì)量評(píng)分的要求。平臺(tái)方接受到需要的采集任務(wù)信息之后，向廣大用戶發(fā)布感知任務(wù)以及用戶需要提交的信息內(nèi)容說(shuō)明。對(duì)此次感知任務(wù)感興趣的用戶U={1,2,…,n}在線隨機(jī)到達(dá)，并向平臺(tái)方提交他們參與完成任務(wù)的資料信息[19]。用戶通過(guò)無(wú)線網(wǎng)絡(luò)或蜂窩網(wǎng)絡(luò)與平臺(tái)進(jìn)行通信。

用戶i若初次到達(dá)系統(tǒng)，則會(huì)賦予一個(gè)初始的信譽(yù)值ηi，平臺(tái)唯一化記錄用戶i∈U的ID，如果用戶宣稱完成了任務(wù)，并通過(guò)算法篩選，被平臺(tái)選擇，平臺(tái)方會(huì)接受任務(wù)發(fā)布方對(duì)用戶提供數(shù)據(jù)質(zhì)量的反饋，并以此為依據(jù)，在用戶下一次登錄系統(tǒng)競(jìng)標(biāo)時(shí)更新其信譽(yù)值，作為參與完成任務(wù)的資料信息之一。若用戶非首次參與，系統(tǒng)讀取用戶上一次參與選擇后的信譽(yù)值，并按照更新法則進(jìn)行更新，參與此次競(jìng)標(biāo)。

平臺(tái)所要求的用戶i提交的參與任務(wù)資料是一個(gè)五元函數(shù)θi={ai,di,ci,vi,ηi}，這里ai∈{1,2,…,T}表示到達(dá)時(shí)間，di∈{1,2,…,T}表示離開(kāi)時(shí)間，ci是完成一個(gè)感知任務(wù)真實(shí)的成本，vi表示用戶i可以為任務(wù)發(fā)布方帶來(lái)的價(jià)值，ηi為用戶i當(dāng)前的信譽(yù)值。用戶參與感知任務(wù)以及平臺(tái)選擇用戶子集的過(guò)程可以建模成一個(gè)在線的拍賣過(guò)程。用戶決定參與此次任務(wù)之后，會(huì)向平臺(tái)端提交參與任務(wù)的資料信息。接著，平臺(tái)需要做一個(gè)在線的及時(shí)判斷，決定是否雇傭該用戶。如果該用戶被選擇，平臺(tái)需要支付給用戶的報(bào)酬pi，同時(shí)接受任務(wù)發(fā)布方反饋的用戶提供數(shù)據(jù)質(zhì)量打分，并根據(jù)上傳數(shù)據(jù)的一些屬性計(jì)算客觀評(píng)價(jià)分值，綜合考慮主客觀的分值，以供下次更新信譽(yù)值。注意任務(wù)發(fā)布方有一個(gè)總的預(yù)算B作為可以支付給選擇用戶的最大報(bào)酬。任務(wù)發(fā)布方期望在給定的預(yù)算和得到一定數(shù)據(jù)質(zhì)量保證的前提下，最大化從用戶方得到的總價(jià)值，整個(gè)過(guò)程的信息流如圖1所示。

用戶在線到達(dá)參與競(jìng)標(biāo)的過(guò)程可以看成是一場(chǎng)博弈，用戶會(huì)有策略地提交他們的競(jìng)標(biāo)資料去最大化可能得到的回報(bào)。當(dāng)與任務(wù)發(fā)布方互動(dòng)時(shí)，用戶i真實(shí)的成本和到達(dá)、離開(kāi)時(shí)間是非公開(kāi)的，僅被用戶本身所知。用戶i只能有策略地操作自己的競(jìng)標(biāo)價(jià)格以獲得更高的效用，平臺(tái)端基于用戶的競(jìng)標(biāo)資料通過(guò)激勵(lì)算法選擇獲勝用戶，并通過(guò)計(jì)算，給予獲勝用戶報(bào)酬pi。

圖1 信息流示意圖Fig.1 Schematic of information flow

2 信譽(yù)評(píng)價(jià)機(jī)制

對(duì)于平臺(tái)方而言，存在選擇用戶的信譽(yù)值的閾值標(biāo)準(zhǔn)，對(duì)于初次參與感知任務(wù)的用戶來(lái)說(shuō)，將初始化的信譽(yù)值設(shè)定系統(tǒng)在當(dāng)前時(shí)刻的信譽(yù)值的閾值η?。設(shè)用戶的信譽(yù)值η的取值是有上下界的，即η∈[0,ξ]，ξ為用戶信譽(yù)值的上界，用戶如果更新完信譽(yù)值之后信譽(yù)值為負(fù)數(shù)，認(rèn)為該用戶的信譽(yù)值為最小值0。φ(ηi,Rm)表示更新后用戶的信譽(yù)值η*i，其中ηi為用戶i當(dāng)前的信譽(yù)值,Rm為用戶上一次參與競(jìng)標(biāo)后得到的基于數(shù)據(jù)質(zhì)量的信譽(yù)綜合評(píng)分。用戶參與此次競(jìng)標(biāo)的信譽(yù)值η*i=φ(ηi,Rm)的評(píng)定需要綜合任務(wù)發(fā)布方對(duì)用戶的打分反饋ζi和客觀影響因素等（質(zhì)量評(píng)分的要求）。假定質(zhì)量評(píng)分要求由完成時(shí)間可靠性ωi和圖片收集任務(wù)要求的圖片大小可靠性?i共同決定，考慮主客觀因素綜合，采用分類分級(jí)賦值，建立信譽(yù)評(píng)價(jià)規(guī)則。表1中對(duì)有關(guān)信譽(yù)評(píng)價(jià)機(jī)制的符號(hào)進(jìn)行說(shuō)明。

表1 信譽(yù)評(píng)價(jià)機(jī)制符號(hào)說(shuō)明Tab.1 Description of credit evaluation mechanism symbol

2.1 任務(wù)發(fā)布方打分ζi

ζi為任務(wù)發(fā)布方對(duì)用戶完成質(zhì)量的考量，其中ζi∈[0,1]，ζi越大表示任務(wù)發(fā)布方對(duì)用戶的滿意度越高。由任務(wù)發(fā)布方反饋的打分，作為綜合評(píng)定的主觀因素之一，考慮了任務(wù)發(fā)布方的主觀反饋，對(duì)數(shù)據(jù)質(zhì)量的把控上起到了主觀選擇的作用。在[0,1]中定義3個(gè)集合，其中打分分值落在[0,0.3)表示“低”用L代替；分值落在[0.3,0.7)表示“中”用M代替；分值落在[0.7,1]表示“高”用H代替。

2.2 完成任務(wù)時(shí)間的可靠性ωi

用戶在參與任務(wù)之前會(huì)提交自己相關(guān)參與資料，由于考慮的是在線場(chǎng)景，所以資料中需包含用戶的到達(dá)時(shí)間ai∈{1,2,…,T}和離開(kāi)時(shí)間di∈{1,2,…,T}。時(shí)間的可靠性ωi定義為用戶完成時(shí)間與任務(wù)發(fā)布方要求的總的完成時(shí)長(zhǎng)的重疊時(shí)間的比值。該值越大，表明用戶花費(fèi)了相對(duì)更多的時(shí)間完成任務(wù)，因此可靠性相應(yīng)的也應(yīng)越大。定義客觀的完成任務(wù)時(shí)間可靠性為

式中T表示整個(gè)過(guò)程的截止時(shí)間。顯然ωi的取值范圍在[0,1]。同樣，將ωi的取值范圍定義成3個(gè)集合建模，其中ωi∈ [0,0.3)表示“低”，用L代替；ωi∈[0.3,0.7)表示“中”，用 M 代替；ωi∈ [0.7,1]表示“高”，用H代替。

2.3 圖像大小可靠性?i

針對(duì)一些具體的情況，例如收集圖片的感知任務(wù)，了解收集圖片的質(zhì)量一個(gè)很重要的方面就是圖像的大小以及像素等指標(biāo)。假設(shè)任務(wù)要求上傳的圖片的大小為φi，將實(shí)際用戶的上傳圖片的大小χi與要求的大小的距離占要求大小的比例表示為圖片大小的可靠性

顯然?i的取值范圍在[0,1]。同樣，將?i的取值范圍定義成3個(gè)集合建模，其中?i∈[0,0.3)表示“低”，用L代替；?i∈ [0.3,0.7)表示“中”，用M代替；?i∈[0.7,1]表示“高”，用H代替。則計(jì)算更新的用戶信譽(yù)分?jǐn)?shù)Rm可使用式（3）所示規(guī)則，其中η?為系統(tǒng)當(dāng)前時(shí)間階段的信譽(yù)閾值。

平臺(tái)統(tǒng)計(jì)上述3方面的分?jǐn)?shù)，并根據(jù)取值范圍集合進(jìn)行對(duì)應(yīng)，統(tǒng)計(jì)L和H的個(gè)數(shù)，并根據(jù)規(guī)則計(jì)算信譽(yù)分?jǐn)?shù)。用戶帶著自己的參與資料，參與平臺(tái)的選擇。每次用戶到達(dá)平臺(tái)，提交數(shù)據(jù)的時(shí)候，平臺(tái)會(huì)根據(jù)上一次用戶的信譽(yù)記錄，更新用戶的信譽(yù)值作為參與后續(xù)競(jìng)選的參數(shù)之一。其具體的更新規(guī)則如下

每當(dāng)用戶到達(dá)提交競(jìng)標(biāo)資料，信譽(yù)值η*i作為競(jìng)標(biāo)資料之一，提交給平臺(tái)，若用戶之前參與過(guò)競(jìng)標(biāo)且被任務(wù)發(fā)布方選中，有相應(yīng)信譽(yù)值更新情況，平臺(tái)在競(jìng)標(biāo)前根據(jù)更新法則計(jì)算用戶新的信譽(yù)值η*i參與此次的競(jìng)標(biāo)。若之前無(wú)參與提交資料過(guò)程，則信譽(yù)值設(shè)置為初始值η?;若上一輪的競(jìng)標(biāo)未獲勝，信譽(yù)值維持不變。

3 算法描述

用戶i在線的到達(dá)參與競(jìng)標(biāo)，提交競(jìng)標(biāo)資料θi={ai,di,ci,vi,ηi}，用戶i參與競(jìng)標(biāo)的競(jìng)標(biāo)價(jià)格為bi，這里bi≥ci。平臺(tái)需要在用戶離開(kāi)時(shí)間di之前，根據(jù)用戶提供的競(jìng)標(biāo)資料決定是否雇傭該用戶。獲勝者用戶的集合表示為W，用V(W)表示任務(wù)發(fā)布方選擇用戶子集W的價(jià)值函數(shù)，則

圖2 考慮信譽(yù)的在線激勵(lì)機(jī)制系統(tǒng)流程圖Fig.2 Flowchart of online incentive system considering credibility

對(duì)于任務(wù)發(fā)布方來(lái)說(shuō)，希望在預(yù)算B限制的情況下，通過(guò)選取用戶子集，盡可能獲得最大的價(jià)值，即

為了實(shí)現(xiàn)在線處理用戶的參與資料，參考秘書問(wèn)題的多階段選擇的思想[20],設(shè)計(jì)了一種多階段的采樣-接受過(guò)程[21]。該機(jī)制動(dòng)態(tài)的增加采樣的容量，并且動(dòng)態(tài)的為將來(lái)用戶子集的選擇學(xué)習(xí)效率密度閾值，效率密度閾值結(jié)合之前所述的信譽(yù)更新機(jī)制得出的信譽(yù)分，為平臺(tái)選取用戶提供了標(biāo)準(zhǔn)[19]。該算法需要滿足：（1）計(jì)算有效性，即該算法要在多項(xiàng)式時(shí)間內(nèi)完成；（2）個(gè)體合理性，即被選擇的用戶所得到的報(bào)酬大于等于其成本；（3）預(yù)算可行性，即支付給所有選擇用戶的總報(bào)酬要小于給定的預(yù)算B；（4）策略真實(shí)性,即保證如果用戶謊報(bào)其參與資料的話他不會(huì)獲得更多的報(bào)酬[22]。

3.1 效率密度閾值更新算法

為了給平臺(tái)在選擇用戶時(shí)有提供一個(gè)統(tǒng)一的標(biāo)準(zhǔn)，在每一階段開(kāi)始的時(shí)候需要執(zhí)行閾值更新算法。

算法的核心在于從采樣集合中分析計(jì)算，在每個(gè)時(shí)間階段開(kāi)始的時(shí)候，根據(jù)算法1計(jì)算該階段的密度閾值。平臺(tái)將每個(gè)用戶的效率值與計(jì)算得到的該階段的密度閾值進(jìn)行比較，作為選擇用戶子集的標(biāo)準(zhǔn)。對(duì)于平臺(tái)方來(lái)說(shuō)，目標(biāo)是最大化能獲得的價(jià)值，因此在選擇用戶時(shí)，傾向于選擇有著更高效率值的用戶。具體的效率閾值更新算法如下：

算法1效率閾值更新

輸入：階段-預(yù)算B'，采樣集合S'，當(dāng)前時(shí)間階段Tk

輸出：密度閾值ρ

在密度閾值算法中，輸入的參數(shù)是任務(wù)發(fā)布方提交的預(yù)算B'，采樣的集合S'，還有當(dāng)前階段的開(kāi)始時(shí)間Tk定義用戶的效率為效率越大越有可能被平臺(tái)選中。本文假定每一個(gè)用戶的效率均有上下邊界，現(xiàn)實(shí)情況中也更加符合，同時(shí)也為了后續(xù)的屬性證明。假設(shè)閾值更新算法依次選擇效用值高的用戶將用戶集合放入ETK，在選擇效用值高的用戶需要滿足預(yù)算受限的條件，即

本算法的根本目的是計(jì)算每一階段的閾值，這里定義閾值為和每一階段的平均效用值。

定義1如果按照效率進(jìn)行排列的用戶滿足并且此場(chǎng)拍賣的預(yù)算為B，那么如果對(duì)于2個(gè)用戶x和y，滿足且那么

那么

由定義1可知，在閾值算法中，如果while循環(huán)在用戶i處不再滿足預(yù)算條件，則不需要再考慮其他效用值比用戶i低的用戶j。因?yàn)榭梢酝茢喑?/p>

3.2 信譽(yù)值更新算法

信譽(yù)值的高低不僅是平臺(tái)選擇用戶的重要標(biāo)準(zhǔn)之一，同時(shí)也應(yīng)是用戶獲取報(bào)酬和平臺(tái)獲取價(jià)值的影響因素。信譽(yù)值的提高能夠給用戶帶來(lái)更多的報(bào)酬收益的同時(shí)也為平臺(tái)帶來(lái)更多的價(jià)值收益。因此本模塊將闡述信譽(yù)值與用戶報(bào)酬以及平臺(tái)收益之間的關(guān)聯(lián)。

3.2.1 信譽(yù)值與用戶報(bào)酬

更新用戶信譽(yù)值之后，如果Rm＞0，則說(shuō)明用戶上一次有著優(yōu)秀的信譽(yù)記錄，各項(xiàng)指標(biāo)基本完全符合系統(tǒng)的要求。則如果此次用戶的效率值大于該階段的閾值并且預(yù)算還沒(méi)有用完，即用戶符合被選中的所有條件，系統(tǒng)需要支付一定的報(bào)酬給用戶，該用戶理應(yīng)得到比更加多的報(bào)酬，這里定義對(duì)于此類用戶

式中g(shù)與信譽(yù)值成正比，比例系數(shù)為即義越大，下次用戶參與競(jìng)拍時(shí)會(huì)獲得越多的報(bào)酬。

3.2.2 信譽(yù)值與平臺(tái)價(jià)值收益

與用戶報(bào)酬類似，有著較高信譽(yù)的用戶提供的數(shù)據(jù)，也有更大的可能為平臺(tái)帶來(lái)更多價(jià)值收益。即如果Rm＞0，用戶個(gè)人的競(jìng)標(biāo)資料中的vi根據(jù)信譽(yù)值重新衡量。定義

式中h與信譽(yù)值成正比，比例系數(shù)為即越大，下次用戶參與競(jìng)拍時(shí)會(huì)給平臺(tái)帶來(lái)越多的價(jià)值。

3.2.3 信譽(yù)值閾值的更新

想要參與競(jìng)標(biāo)的用戶的信譽(yù)值更新后，將會(huì)與參與競(jìng)標(biāo)選擇的閾值進(jìn)行比較，只有高于該閾值的用戶才能繼續(xù)參與競(jìng)標(biāo)。由于本論文考慮的是用戶可以多次參與競(jìng)標(biāo)的情況，因此初次來(lái)到系統(tǒng)參與競(jìng)標(biāo)的用戶賦予的初始化信譽(yù)值為系統(tǒng)的信譽(yù)值閾值，當(dāng)選中的集合中，重復(fù)來(lái)到的用戶人數(shù)占用戶總?cè)藬?shù)超過(guò)一半時(shí)，需要更新信譽(yù)值閾值，信譽(yù)值的閾值定義為選中集合中所有用戶信譽(yù)值的平均值，即

3.3 ROM算法

前面介紹了計(jì)算效率閾值的方法，是為了在每個(gè)階段開(kāi)始的時(shí)候，計(jì)算密度閾值，指導(dǎo)平臺(tái)選擇用戶的子集。首先，把時(shí)間T劃分成l個(gè)時(shí)間段每一階段以結(jié)尾。相應(yīng)的，每一個(gè)階段分配的預(yù)算是Bk=2-kB，其中Ti表示在該時(shí)刻之前用戶到達(dá)的概率是2-k。對(duì)于每一個(gè)時(shí)間段Ti，按照上述的閾值更新算法計(jì)算效率閾值。具體的基于質(zhì)量的在線激勵(lì)算法如下：

算法2基于質(zhì)量的在線激勵(lì)算法

輸入：階段預(yù)算B，截止時(shí)間T

(1)(t,Tk,Bk,

(2)fort=1toTdo

(3)if用戶i在t時(shí)刻到達(dá) then

(4)O←O∪{i}

(5)for每一用戶iinOdo

(6)if儲(chǔ)存用戶信譽(yù)值數(shù)據(jù)庫(kù)存在更新記錄

(7)ηi=

(8)ifRm＞0

(9)vi=max(vi+hvi,biQ)

(10)end

(11)elseηi和vi保持不變

(13)ifRm＞0

(14)pi←(1+g)

(15)else

(17)W←W∪{i}

(18)O←OW

(19)若有用戶在時(shí)間t離開(kāi)，從O中移除該用戶，并將該用戶加入采樣集合S'

(20)ift=then

(21)ρ←效率閾值更新(Bk,Tk,S')

(22)Tk=2Tk,Bk=2Bk

(23)ifW集合中重復(fù)到達(dá)的用戶占所有被選中用戶比例≥0.5

在每一個(gè)階段內(nèi)，如果有用戶到達(dá)，將其加入集合O中，這里，集合O中包含的用戶是已經(jīng)到達(dá)但是還沒(méi)有被選擇或者已經(jīng)離開(kāi)此次競(jìng)拍活動(dòng)。并從數(shù)據(jù)庫(kù)中讀取是否存在此用戶上次參與此次感知任務(wù)的信譽(yù)值更新數(shù)據(jù)。若有的話，將新的信譽(yù)值賦值給該用戶之后再進(jìn)行后續(xù)選擇過(guò)程，并增加用戶能夠帶來(lái)的價(jià)值vi為原來(lái)的(1+h)倍，該h值與用戶的信譽(yù)值成正比，但由于前面有設(shè)定，用戶的效率值是由上界的，所以用戶能夠帶來(lái)的價(jià)值vi最大不能超過(guò)biQ。如果沒(méi)有更新信譽(yù)值信息，則以之前不變的信譽(yù)值和價(jià)值參與選擇過(guò)程。如果當(dāng)前用戶滿足效率值高于閾值，并且目前平臺(tái)總的花費(fèi)沒(méi)有超過(guò)預(yù)算B，同時(shí)用戶的信譽(yù)值高于閾值η?，則選擇該用戶，將其加入獲勝者集合W,并給該用戶支付報(bào)酬vi/ρ。如果上述3個(gè)條件中有一項(xiàng)沒(méi)有滿足的話，則該用戶則會(huì)等待下一時(shí)刻的選擇判斷。如果當(dāng)前時(shí)間等于則按照之前所述的閾值更新算法更新密度閾值。如果當(dāng)前已經(jīng)選擇的用戶，即集合W中的重復(fù)到達(dá)用戶占所有被選中用戶的比例≥0.5，則更新信譽(yù)值閾值為重復(fù)該過(guò)程，直到t=T。

4 仿真與分析

為了驗(yàn)證本文提出的考慮信譽(yù)更新的在線激勵(lì)機(jī)制算法的性能，運(yùn)用Eclipse的Java代碼對(duì)提出的基于信譽(yù)更新的在線激勵(lì)機(jī)ROM進(jìn)行了仿真實(shí)驗(yàn)，并分別與離線情況下知曉所有用戶信息的最優(yōu)算法、在線情境下隨機(jī)閾值選擇用戶的算法以及不考慮用戶信譽(yù)的一般在線激勵(lì)機(jī)制算法進(jìn)行比較。

實(shí)驗(yàn)1驗(yàn)證算法的計(jì)算有效性

對(duì)計(jì)算有效性的測(cè)試實(shí)驗(yàn)是在Windows10系統(tǒng)上進(jìn)行，處理器為Intel?Core?i7-6650U CPU@2.20 GHz 2.21 GHz，RAM為16.0 GB。為驗(yàn)證ROM算法的計(jì)算有效性，按表2所示的人數(shù)設(shè)定，每一組都隨機(jī)生成了50個(gè)實(shí)例，并對(duì)這50個(gè)實(shí)例的運(yùn)算時(shí)間取平均數(shù)來(lái)保證結(jié)果的可靠性。實(shí)驗(yàn)設(shè)定及結(jié)果如表2所示。運(yùn)用同樣的方法在預(yù)算變化的情況下，也同樣對(duì)計(jì)算有效性進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果記錄于表3中。

綜合表2、3的實(shí)驗(yàn)結(jié)果可見(jiàn)，ROM算法是符合計(jì)算有效性的。

表2 參與人數(shù)變化運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果Tab.2 Running time with variation of the number of participants

表3 預(yù)算變化運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果Tab.3 Running time with the change of budgets

實(shí)驗(yàn)2研究預(yù)算B與平臺(tái)獲得的總價(jià)值之間的關(guān)系。

設(shè)置截止時(shí)間T=50為,人數(shù)n=500,時(shí)間階段l=4,用戶的效率上下界分別為L(zhǎng)=1,U=2,初始密度閾值為ε=0.9，初始信譽(yù)值閾值μ=0.5。對(duì)每一個(gè)用戶i而言，設(shè)置在T內(nèi)隨機(jī)產(chǎn)生到達(dá)和離開(kāi)時(shí)間。并設(shè)置用戶可以在離開(kāi)之后再次進(jìn)入系統(tǒng)。ci服從均勻分布U[1,10]。平臺(tái)模擬對(duì)已選擇數(shù)據(jù)進(jìn)行[0,1]的隨機(jī)打分，用戶的完成任務(wù)時(shí)間可靠性和圖像大小可靠性也由收集數(shù)據(jù)的平臺(tái)算出，綜合考慮后計(jì)算出新的信譽(yù)值。此次模擬的預(yù)算取值范圍是B∈[0,20000]。將本文提出的基于質(zhì)量的在線激勵(lì)機(jī)制與離線算法，隨機(jī)選擇算法以及不考慮質(zhì)量的在線激勵(lì)算法進(jìn)行了仿真比較，結(jié)果如圖3所示。

仿真結(jié)果說(shuō)明，考慮了用戶提交數(shù)據(jù)質(zhì)量的ROM算法雖然較之于離線情況下最優(yōu)的算法來(lái)說(shuō)，在同樣預(yù)算的情況下，獲得的價(jià)值沒(méi)有最大，但是較之于一般的在線激勵(lì)機(jī)制來(lái)說(shuō)，能獲得更大的價(jià)值增益，而且隨著預(yù)算的增加，價(jià)值的增益差距也越來(lái)越大，這是由于預(yù)算越大，能夠選擇的高質(zhì)量用戶響應(yīng)比例也會(huì)提高。因此能夠?yàn)槠脚_(tái)帶來(lái)更大的價(jià)值。

圖3 預(yù)算與價(jià)值之間關(guān)系仿真結(jié)果Fig.3 Budget versus value

實(shí)驗(yàn)3研究到達(dá)人數(shù)n與平臺(tái)獲得的總價(jià)值之間的關(guān)系。

設(shè)置截止時(shí)間T=500 s,預(yù)算B=1600,時(shí)間階段l=4，用戶的效率上下界分別為L(zhǎng)=1,U=2,初始密度閾值為ε=0.9，初始信譽(yù)值閾值μ=0.5。其余設(shè)置與實(shí)驗(yàn)一相同。此次模擬的參與人數(shù)的取值范圍是n∈[0,600]。將ROM與最優(yōu)的離線算法、隨機(jī)選擇算法以及不考慮質(zhì)量的一般在線激勵(lì)算法進(jìn)行了仿真比較，結(jié)果如圖4所示。

圖4 用戶數(shù)量與平臺(tái)獲得總價(jià)值關(guān)系仿真結(jié)果Fig.4 The number of users versus value

仿真結(jié)果說(shuō)明，隨著參與人數(shù)的增加，平臺(tái)獲得的總價(jià)值也是增加的。單位人數(shù)獲得最大價(jià)值的是離線算法，本文提出的ROM算法因?yàn)閷?duì)參與者的篩選更加嚴(yán)格，所以與一般的在線激勵(lì)機(jī)制相比，單位人數(shù)獲得的效益略低，不過(guò)在可接受范圍之內(nèi)。對(duì)保證平臺(tái)的數(shù)據(jù)質(zhì)量上的貢獻(xiàn)大于此單位人數(shù)的獲得價(jià)值。

5 結(jié)束語(yǔ)

結(jié)合任務(wù)發(fā)布方對(duì)用戶的信譽(yù)評(píng)分反饋以及用戶客觀的時(shí)間可靠性和提供數(shù)據(jù)大小可靠性等因素，提出了用戶信譽(yù)評(píng)價(jià)機(jī)制，綜合考慮用戶歷史和現(xiàn)實(shí)信譽(yù)記錄的更新機(jī)制，建立結(jié)合信譽(yù)更新模型，設(shè)計(jì)了基于信譽(yù)更新的在線激勵(lì)算法，運(yùn)用JAVA開(kāi)發(fā)了仿真程序。仿真結(jié)果表明，該算法通過(guò)對(duì)用戶信譽(yù)進(jìn)行評(píng)分，提高了平臺(tái)收集數(shù)據(jù)的質(zhì)量，在一定程度上減少了平臺(tái)的總花費(fèi)，從而提高了平臺(tái)工作的效率。