考慮信譽更新的移動群智感知在線激勵機制

楊 堤 李卓青 楊綠溪 徐琴珍

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

引 言

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

1 系統(tǒng)建模

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

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

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

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

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

2 信譽評價機制

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

表1 信譽評價機制符號說明Tab.1 Description of credit evaluation mechanism symbol

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

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

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

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

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

2.3 圖像大小可靠性?i

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

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

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

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

3 算法描述

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

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

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

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

3.1 效率密度閾值更新算法

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

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

算法1效率閾值更新

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

輸出：密度閾值ρ

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

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

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

那么

由定義1可知，在閾值算法中，如果while循環(huán)在用戶i處不再滿足預(yù)算條件，則不需要再考慮其他效用值比用戶i低的用戶j。因為可以推斷出

3.2 信譽值更新算法

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

3.2.1 信譽值與用戶報酬

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

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

3.2.2 信譽值與平臺價值收益

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

式中h與信譽值成正比，比例系數(shù)為即越大，下次用戶參與競拍時會給平臺帶來越多的價值。

3.2.3 信譽值閾值的更新

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

3.3 ROM算法

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

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

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

(1)(t,Tk,Bk,

(2)fort=1toTdo

(3)if用戶i在t時刻到達 then

(4)O←O∪{i}

(5)for每一用戶iinOdo

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

(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)若有用戶在時間t離開，從O中移除該用戶，并將該用戶加入采樣集合S'

(20)ift=then

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

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

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

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

4 仿真與分析

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

實驗1驗證算法的計算有效性

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

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

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

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

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

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

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

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

實驗3研究到達人數(shù)n與平臺獲得的總價值之間的關(guān)系。

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

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

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

5 結(jié)束語

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