群智感知任務(wù)分配中的用戶類型轉(zhuǎn)換問題研究

黃丹鐳，黃 河，，孫玉娥，陸 樂，吳曉燦，杜 揚(yáng)

1(蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006) 2(蘇州大學(xué) 軌道交通學(xué)院，江蘇 蘇州 215137) 3(中國科學(xué)技術(shù)大學(xué) 蘇州研究院，江蘇 蘇州 215123)

1 引 言

群智感知技術(shù)利用配置在智能移動(dòng)終端上的各類傳感器(如加速度計(jì)、GPS、陀螺儀、相機(jī)等)，隨時(shí)隨地收集物理世界中感興趣的數(shù)據(jù)，并進(jìn)一步分析形成應(yīng)用為我們的日常生活以及商業(yè)活動(dòng)提供有效的服務(wù)與支持.作為一種新興的大規(guī)模數(shù)據(jù)收集系統(tǒng)，群智感知系統(tǒng)大幅降低了數(shù)據(jù)收集所需的時(shí)間與成本、提高數(shù)據(jù)的采集規(guī)模，從而更容易通過分析得到大量的可信數(shù)據(jù)，進(jìn)而為系統(tǒng)用戶提供優(yōu)質(zhì)的服務(wù).

智能移動(dòng)終端用戶完成數(shù)據(jù)采集任務(wù)需要付出相應(yīng)的成本開銷，例如電能損耗、網(wǎng)絡(luò)流量損耗等，并會(huì)對(duì)設(shè)備的使用產(chǎn)生一定的影響.因此，大多數(shù)群智感知系統(tǒng)所能吸引到的用戶數(shù)量是有限的，且不同的用戶完成任務(wù)的質(zhì)量是不同的.為了盡可能通過有限的用戶收集到更多高可靠性的數(shù)據(jù)，需要設(shè)計(jì)合理的任務(wù)分配和激勵(lì)機(jī)制，保證參與任務(wù)的用戶均能高質(zhì)量地完成任務(wù).針對(duì)這一問題，已有大量研究提出了一系列高效的群智感知任務(wù)分配機(jī)制.例如，部分文獻(xiàn)設(shè)計(jì)的任務(wù)分配機(jī)制將每個(gè)感知任務(wù)分配給多個(gè)用戶完成，以保證任務(wù)能到得到高質(zhì)量的感知數(shù)據(jù)[1-4].然而用戶完成數(shù)據(jù)采集任務(wù)會(huì)花費(fèi)一定的成本，因此群智感知系統(tǒng)需要對(duì)每個(gè)參與任務(wù)的用戶支付一定的報(bào)酬.上述文獻(xiàn)并未考慮用戶完成質(zhì)量之間的差異，而每個(gè)任務(wù)分配的用戶越多，所需要支付的報(bào)酬也越多.為了減少群智感知系統(tǒng)的成本，應(yīng)該盡可能地將任務(wù)分配給高質(zhì)量的用戶完成，而不是簡單地分配給多個(gè)人完成.因此，在考慮用戶可靠性的基礎(chǔ)上，一些研究者設(shè)計(jì)了一系列高效的群智感知任務(wù)分配機(jī)制，以盡可能地將任務(wù)分配給高質(zhì)量的用戶完成[5-11].在上述研究的基礎(chǔ)上，現(xiàn)有的一些研究還將用戶的報(bào)酬與任務(wù)的實(shí)際完成質(zhì)量相結(jié)合，以激勵(lì)用戶更好地完成任務(wù)[12，13].然而，在群智感知中用戶完成任務(wù)的質(zhì)量不光受到主觀意愿(例如：做事的認(rèn)真程度)的影響，還受到當(dāng)前所處的狀態(tài)、環(huán)境以及所持有的智能終端設(shè)備等客觀因素的影響.對(duì)于任務(wù)完成質(zhì)量不受主觀意愿決定的用戶來說，給予獎(jiǎng)勵(lì)或其他激勵(lì)方式也無法使其變成高質(zhì)量用戶；反之，如果用戶所提交的數(shù)據(jù)質(zhì)量是由主觀因素決定的，則可以通過給予額外的獎(jiǎng)勵(lì)來激勵(lì)用戶更好地參與任務(wù).據(jù)我們的調(diào)研發(fā)現(xiàn)，現(xiàn)在還沒有機(jī)制研究在任務(wù)分配之前，通過設(shè)置額外獎(jiǎng)勵(lì)的方式，激勵(lì)低質(zhì)量用戶轉(zhuǎn)換為高質(zhì)量用戶，從而利用有限的獎(jiǎng)勵(lì)最大化地提高任務(wù)的整體完成質(zhì)量.

為了解決現(xiàn)有研究的不足，本文設(shè)計(jì)了一種群智感知用戶類型轉(zhuǎn)換方法，以實(shí)現(xiàn)任務(wù)間完成質(zhì)量的最大最小公平為優(yōu)化目標(biāo)，研究在任務(wù)分配過程中如何分配有限的獎(jiǎng)勵(lì)給低質(zhì)量用戶，才能促使提交低質(zhì)量感知數(shù)據(jù)的用戶轉(zhuǎn)變成為提交高質(zhì)量感知數(shù)據(jù)的用戶，從提高所收集數(shù)據(jù)的質(zhì)量.首先，所設(shè)計(jì)的機(jī)制對(duì)用戶進(jìn)行分類，并擬合低質(zhì)量用戶的任務(wù)完成質(zhì)量提升與獎(jiǎng)勵(lì)之間的關(guān)系曲線.然后，設(shè)計(jì)了一種最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配機(jī)制，在每輪任務(wù)分配時(shí)決定將任務(wù)和獎(jiǎng)勵(lì)分配給哪些用戶以及為每個(gè)分到任務(wù)的低質(zhì)量用戶分配多少獎(jiǎng)勵(lì)，從而最大化任務(wù)的最低完成質(zhì)量.最后，通過仿真實(shí)驗(yàn)對(duì)所設(shè)計(jì)的機(jī)制性能進(jìn)行了驗(yàn)證.

2 問題建模

本章首先給出所研究的群智感知系統(tǒng)模型，并對(duì)所研究用戶類型轉(zhuǎn)換問題給出形式化的描述.

2.1 系統(tǒng)模型

本文所研究的群智感知系統(tǒng)由一個(gè)任務(wù)發(fā)布者、一個(gè)群智感知平臺(tái)和若干移動(dòng)終端用戶(后面簡稱用戶)組成.用U={1，2，…，m}來表示用戶集合，T={t1，t2，…，tn}來表示任務(wù)發(fā)布者發(fā)布的任務(wù)集合.所研究的群智感知系統(tǒng)的任務(wù)分配分周期進(jìn)行.如圖1所示，每個(gè)任務(wù)周期開始時(shí)首先由任務(wù)發(fā)布者將需要完成的任務(wù)發(fā)布在群智感知平臺(tái)上.每個(gè)發(fā)布的群智感知任務(wù)包含一個(gè)任務(wù)描述，包含任務(wù)對(duì)用戶技能以及感知設(shè)備性能等方面的要求.除此之外，每個(gè)任務(wù)還包含一個(gè)任務(wù)報(bào)價(jià)bj，即當(dāng)用戶完成任務(wù)后的實(shí)際支付.在本文所研究的模型中bj是一個(gè)固定值，不管將該任務(wù)分配給哪個(gè)用戶完成所支付的除獎(jiǎng)勵(lì)之外的金額均等于bj.本文所研究的群智感知任務(wù)是異質(zhì)的，即不同任務(wù)對(duì)用戶的要求不同.在這里，我們將要求類似的任務(wù)認(rèn)為是同一類任務(wù)，并將群智感知系統(tǒng)中的所有任務(wù)劃分為e種不同的類型.我們用Tk來表示所有屬于第k類的任務(wù)集合，且tj∈Tk.除此之外，參與群智感知任務(wù)的用戶也是異質(zhì)的.由于用戶自身的技能、所持設(shè)備等方面的不同，不同用戶完成同一任務(wù)的質(zhì)量是不同的，即使是同一用戶完成不同類型任務(wù)的質(zhì)量也是不同的.用qi，k表示用戶i完成類型為k的任務(wù)的期望完成質(zhì)量.

圖1 基于用戶分類的最優(yōu)獎(jiǎng)勵(lì)任務(wù)分配模型Fig.1 Structure of the allocation and reward system with user classification in crowdsensing system

每個(gè)用戶在閱讀任務(wù)描述之后，會(huì)向群智感知平臺(tái)提交一組感興趣的任務(wù)集合.然后，群智感知平臺(tái)根據(jù)一定的規(guī)則將每個(gè)任務(wù)分配給一個(gè)用戶完成.除此之外，每個(gè)用戶在一個(gè)分配周期最多參與一個(gè)任務(wù)的完成.在實(shí)際的群智感知系統(tǒng)中，并不是每一個(gè)任務(wù)都能找到高質(zhì)量的用戶.在這種情況下，本文為候選用戶集合中僅有低質(zhì)量用戶的任務(wù)提供一定的獎(jiǎng)勵(lì)，以激勵(lì)這些任務(wù)的候選低質(zhì)量用戶更好地完成任務(wù)，進(jìn)而轉(zhuǎn)換為高質(zhì)量用戶，從而達(dá)到提高整體任務(wù)完成質(zhì)量的目標(biāo).當(dāng)用戶完成任務(wù)后，群智感知平臺(tái)還會(huì)評(píng)估每個(gè)用戶在本輪的實(shí)際任務(wù)完成質(zhì)量，并據(jù)此計(jì)算低質(zhì)量用戶的實(shí)際獎(jiǎng)勵(lì)金額完成支付.

2.2 問題描述

本文的設(shè)計(jì)目標(biāo)是要使任務(wù)整體完成質(zhì)量最大化.為了實(shí)現(xiàn)這一點(diǎn)，我們希望將任務(wù)分配給完成質(zhì)量盡可能高的用戶.如果用戶i對(duì)任務(wù)tj感興趣，那么就稱用戶i是任務(wù)tj的候選用戶.但是，部分任務(wù)可能不存在高質(zhì)量的候選用戶.在這種情況下，就需要設(shè)計(jì)合理的激勵(lì)機(jī)制，使得這些任務(wù)的候選低質(zhì)量用戶更加認(rèn)真的完成任務(wù)，進(jìn)而轉(zhuǎn)換為高質(zhì)量用戶.任務(wù)發(fā)布者的總獎(jiǎng)勵(lì)金額預(yù)算用B來表示.群智感知平臺(tái)分配給所有用戶的總獎(jiǎng)勵(lì)金額應(yīng)該不超過預(yù)算B.

用yi，j={0，1}表示用戶i是否為任務(wù)tj的候選用戶，其中yi，j=1表示用戶i是任務(wù)tj的候選用戶，而yi，j=0則表示用戶i不是任務(wù)tj的候選用戶.用xi，j={0，1}表示任務(wù)tj是否被分配給了用戶i，其中xi，j=1表示群智感知平臺(tái)將任務(wù)tj分配給了用戶i；否則，xi，j=0.任務(wù)tj的完成質(zhì)量用Qj表示，而任務(wù)完成質(zhì)量的劃分閾值用Th表示.若Qj≥Th，那我們稱任務(wù)tj被高質(zhì)量地完成；否則，稱任務(wù)tj被低質(zhì)量地完成.同樣，若用戶i完成任務(wù)tj的質(zhì)量小于Th，則稱用戶i是任務(wù)tj的低質(zhì)量用戶；反之，用戶i是任務(wù)tj的高質(zhì)量用戶.為了激勵(lì)低質(zhì)量用戶更好地完成任務(wù)，群智感知平臺(tái)會(huì)給部分用戶分配額外的獎(jiǎng)勵(lì).用ri來表示群智感知平臺(tái)給用戶i分配的獎(jiǎng)勵(lì).對(duì)于分配了任務(wù)的低質(zhì)量用戶，若該用戶最終高質(zhì)量地完成了任務(wù)，即提交的感知數(shù)據(jù)的質(zhì)量超過閾值Th，那么群智感知平臺(tái)會(huì)在收到數(shù)據(jù)后支付額外的獎(jiǎng)勵(lì)ri；反之，若該用戶并未提交高質(zhì)量的感知數(shù)據(jù)，那么群智感知平臺(tái)并不會(huì)向該用戶支付獎(jiǎng)勵(lì).本文的設(shè)計(jì)目標(biāo)是要實(shí)現(xiàn)任務(wù)間完成質(zhì)量的最大最小公平，也就是說要在滿足約束的前提下使得max minQj.

3 基于用戶類型轉(zhuǎn)換的最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配機(jī)制

為了最大化地提高所有任務(wù)的最低完成質(zhì)量，基于用戶類型轉(zhuǎn)換的最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配機(jī)制主要需要解決的問題是如何在感知任務(wù)分配過程中計(jì)算為哪些用戶提供額外的獎(jiǎng)勵(lì)，以及獎(jiǎng)勵(lì)的金額是多少的問題.而要解決上述問題，我們首先需要對(duì)用戶進(jìn)行分類，找到每類任務(wù)的高質(zhì)量用戶和低質(zhì)量用戶.對(duì)于每一類任務(wù)，我們還需要構(gòu)建出用戶任務(wù)完成質(zhì)量提升與獎(jiǎng)勵(lì)之間的關(guān)系曲線，為最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配提供依據(jù).因此，所設(shè)計(jì)的基于用戶類型轉(zhuǎn)換的最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配機(jī)制包括兩部分：用戶任務(wù)完成質(zhì)量提升與獎(jiǎng)勵(lì)關(guān)系曲線擬合以及最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配.

3.1 用戶任務(wù)完成質(zhì)量提升與獎(jiǎng)勵(lì)關(guān)系擬合

不同類型的任務(wù)對(duì)設(shè)備和用戶專業(yè)知識(shí)的要求不同，因此同一用戶對(duì)不同任務(wù)所提交數(shù)據(jù)的質(zhì)量可能也是不同的.群智感知平臺(tái)在每次任務(wù)分配之前會(huì)首先按照采集數(shù)據(jù)的屬性對(duì)任務(wù)進(jìn)行分類，且在用戶完成任務(wù)后會(huì)更新其所完成類型任務(wù)的期望完成質(zhì)量.對(duì)于給定的閾值Th，若qi，k≥Th，則稱用戶i是類型為k的任務(wù)的高質(zhì)量用戶；否則，用戶i是類型為k的任務(wù)的低質(zhì)量用戶.當(dāng)發(fā)現(xiàn)一個(gè)用戶為低質(zhì)量用戶時(shí)，需要首先擬合用戶的歷史任務(wù)完成質(zhì)量提升與獎(jiǎng)勵(lì)之間的關(guān)系曲線，為接下來的獎(jiǎng)勵(lì)分配提供依據(jù).需要說明的是，本文主要研究的是如何通過獎(jiǎng)勵(lì)機(jī)制促使用戶提交高質(zhì)量的感知數(shù)據(jù)，而根據(jù)收集到的數(shù)據(jù)估計(jì)出任務(wù)的真值并不在本文的研究范圍之內(nèi).用Trj表示任務(wù)tj的真值，di，j表示用戶i所提交的感知數(shù)據(jù)與真值之間的偏差.在這里，我們假設(shè)Trj是已知的，可以直接根據(jù)已有研究成果得到，例如：有的研究者通過使用最大期望算法(EM)對(duì)眾包工人的質(zhì)量進(jìn)行了估計(jì)[14-16].Li等人[17]研究了一種增量真值發(fā)現(xiàn)框架，該框架可以在新數(shù)據(jù)到達(dá)時(shí)動(dòng)態(tài)更新對(duì)象真值和源權(quán)重.一些研究則使用了貝葉斯方法來發(fā)現(xiàn)真值[18-22].根據(jù)任務(wù)的真值Trj和di，j偏差，可以進(jìn)一步得到本輪用戶i的任務(wù)完成質(zhì)量為：

(1)

假設(shè)任務(wù)tj所屬的類型為k.群智感知平臺(tái)利用q′i，j可以進(jìn)一步計(jì)算得到更新后的用戶i完成類型為k的任務(wù)的期望完成質(zhì)量：

qi，k=αq′i，k+(1-α)q′i，j

(2)

其中α是一個(gè)常數(shù)，滿足0<α<1，并且q′i，k為上一個(gè)周期用戶i完成類型為k的任務(wù)的期望完成質(zhì)量.

(3)

pi，k表示為單位獎(jiǎng)勵(lì)所能帶來的類型為k的任務(wù)的平均期望任務(wù)完成質(zhì)量提升，由公式(4)求得：

(4)

我們可以進(jìn)一步地得到任務(wù)完成質(zhì)量提升值Δqi，k與獎(jiǎng)勵(lì)金額ri，k之間擬合后的關(guān)系式H(Δqi，k).據(jù)此可以求得任務(wù)完成質(zhì)量提升值pi，k：

(5)

對(duì)于每個(gè)低質(zhì)量用戶，取最近l個(gè)提交低質(zhì)量數(shù)據(jù)的周期的獎(jiǎng)勵(lì)與實(shí)際數(shù)據(jù)質(zhì)量提升信息，將實(shí)際數(shù)據(jù)質(zhì)量提升與獎(jiǎng)勵(lì)間關(guān)系用最小二乘法擬合為一條二次曲線；若該用戶提交低質(zhì)量數(shù)據(jù)的周期小于l，則取所有提交低質(zhì)量數(shù)據(jù)的周期來擬合實(shí)際數(shù)據(jù)質(zhì)量提升與獎(jiǎng)勵(lì)之間的關(guān)系曲線.因?yàn)橥挥脩粼诓煌愋腿蝿?wù)上的完成質(zhì)量是不同的，所以需要為用戶提交低質(zhì)量數(shù)據(jù)的任務(wù)分類并分別擬合實(shí)際數(shù)據(jù)質(zhì)量提升與獎(jiǎng)勵(lì)之間的關(guān)系曲線.用最小二乘法利用用戶i最近l次數(shù)據(jù)進(jìn)行二次曲線擬合的步驟如下：

1)構(gòu)建向量

本文對(duì)數(shù)據(jù)進(jìn)行二次曲線擬合，假設(shè)每個(gè)用戶i在任務(wù)類型為k有l(wèi)個(gè)歷史記錄，即有l(wèi)個(gè)只有一個(gè)特征的樣本.表示為(Δqi，k(1)，ri，k(1))，(Δqi，k(2)，ri，k(2))，…，(Δqi，k(l)，ri，k(l)).

首先，我們所構(gòu)建的擬合函數(shù)由公式(6)所示：

HΘ(Δqi，k)=θ0+θ1Δqi，k+θ2Δqi，k2

(6)

其次，所構(gòu)建的擬合函數(shù)的矩陣表達(dá)形式如公式(7)所示：

=ΘTΔQi，k

(7)

最后構(gòu)建了3個(gè)向量.一個(gè)1×l的向量HΘ(Δqi，k)，一個(gè)3×1的參數(shù)向量Θ，以及一個(gè)3×l的向量ΔQi，k.

2)目標(biāo)函數(shù)

為了選取的最合適的參數(shù)向量Θ，定義誤差函數(shù)如公式(8)所示：

J(Θ)=(ΘTΔQi，k-Ri，k)T(ΘTΔQi，k-Ri，k)

(8)

求得擬合函數(shù)的關(guān)鍵是使得J(Θ)最小，并求出J(Θ)最小時(shí)擬合函數(shù)Θ的參數(shù)向量.

3)優(yōu)化方法

將所定義的誤差函數(shù)進(jìn)行求解，誤差函數(shù)展開如公式(9)：

=(ΘTΔQi，k-Ri，k)T(ΘTΔQi，k-Ri，k)

=ΘΔQi，kTΔQi，kΘT-2ΘΔQi，kTRi，k-Ri，kTRi，k

(9)

J(Θ)是關(guān)于Θ的二次函數(shù)，并且非負(fù)，因此存在最小值.最小化J(Θ)等價(jià)于梯度為零：

=-2ΔQi，kTRi，k+2ΔQi，kTΔQi，kΘT=0

(10)

最后求解：

ΔQi，kTΔQi，kΘT=ΔQi，kTRi，k

(11)

ΘT=(ΔQi，kTΔQi，k)-1ΔQi，kTRi，k

(12)

根據(jù)公式(12)可求得最終解，并可得到所需要的二次擬合曲線.

(13)

(14)

其中Uk為參與過類型任務(wù)為k的任務(wù)的用戶集合且這些用戶完成該類任務(wù)的次數(shù)大于f，用戶集合中的用戶數(shù)量為m′.

(15)

3.2 群智感知最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配機(jī)制

假設(shè)群智感知系統(tǒng)對(duì)任務(wù)的總獎(jiǎng)勵(lì)預(yù)算為B.具體的任務(wù)及獎(jiǎng)勵(lì)分配流程如算法1所示.為了激勵(lì)用戶更好地完成任務(wù)并保證任務(wù)的完成質(zhì)量，任務(wù)應(yīng)該分配給期望完成質(zhì)量最高的用戶.因此，算法1首先遍歷所有的任務(wù)以及每個(gè)任務(wù)的候選用戶集合，找到期望任務(wù)完成質(zhì)量最高的用戶.當(dāng)遍歷到類型為k的任務(wù)tj時(shí)，若期望任務(wù)完成質(zhì)量最高的用戶i是高質(zhì)量用戶，即qi，k≥Th，那么直接將任務(wù)tj分配給用戶i，并將用戶i從其他任務(wù)的候選用戶集中刪除；否則，開始處理下一個(gè)任務(wù).

算法1.預(yù)算充足下的任務(wù)與獎(jiǎng)勵(lì)分配算法

輸入：未分配任務(wù)集合T，總獎(jiǎng)勵(lì)預(yù)算B

輸出：分配向量與獎(jiǎng)勵(lì)集合

1.while(T≠φ){

2.設(shè)置rTh=B；

3. for(每一個(gè)任務(wù)tj∈T)

5. for(tj的每個(gè)候選用戶i)

9. end if

10. end for

13. end if

14. end for

15. 將任務(wù)t′分配給需要獎(jiǎng)勵(lì)最少的候選用戶，并將該候選用戶從所有其他未分配任務(wù)的候選用戶集合中刪除；

17. 將任務(wù)t′從未分配任務(wù)集合T中刪除；

18.}end while

然而，群智感知平臺(tái)給出的總預(yù)算并不總能保證所有任務(wù)均可以被高質(zhì)量地完成.當(dāng)算法1計(jì)算得到的所有任務(wù)需要的獎(jiǎng)勵(lì)金額之和大于預(yù)算B時(shí)，則需要根據(jù)算法2來實(shí)現(xiàn)任務(wù)與獎(jiǎng)勵(lì)的最優(yōu)分配.本文的優(yōu)化目標(biāo)是要實(shí)現(xiàn)任務(wù)完成質(zhì)量之間的最大最小公平，也就是說要使min{Qj}tj∈T達(dá)到最大.為了實(shí)現(xiàn)這一目標(biāo)，我們采用二分法來計(jì)算得到給定預(yù)算B下的min{Qj}tj∈T最大值.對(duì)于這種情況，具體的任務(wù)和獎(jiǎng)勵(lì)分配方法如算法2所示.

算法2.預(yù)算不足下的最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配算法

輸入：未分配任務(wù)集合T，總獎(jiǎng)勵(lì)預(yù)算B

輸出：分配向量與獎(jiǎng)勵(lì)集合

1.設(shè)置Thmin=Th，qmax=Th，qmin=min{qj}tj∈T；

2.Flag=1

3.while TRUE {

5. ifFlag=1

7. return；

8. else

9.Flag=0；

11. end if

13. return；

16. else

18. end if

19.}end while

令qj表示任務(wù)tj在不設(shè)置獎(jiǎng)勵(lì)時(shí)的候選用戶的最大期望任務(wù)完成質(zhì)量.在此Thmin表示獎(jiǎng)勵(lì)預(yù)算受限時(shí)所有任務(wù)的期望完成質(zhì)量的下界，即Thmin=min{Qj}tj∈T，那么很容易得到獎(jiǎng)勵(lì)預(yù)算不足時(shí)Thmin滿足min{qj}tj∈T≤Thmin

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

對(duì)于本文所提出的用戶分類以及任務(wù)匹配兩個(gè)階段，本章將構(gòu)造一個(gè)模擬實(shí)驗(yàn)?zāi)Ｐ?，并以此來分析和?yàn)證所研究的機(jī)制的性能.

4.1 任務(wù)數(shù)量與申請(qǐng)用戶數(shù)對(duì)任務(wù)期望完成質(zhì)量下界的影響

圖2 任務(wù)數(shù)量與任務(wù)期望完成質(zhì)量下界之間的關(guān)系Fig.2 Relationship between number of tasks and task expected completion quality

4.2 獎(jiǎng)勵(lì)預(yù)算與實(shí)際獎(jiǎng)勵(lì)之間的關(guān)系

圖3 獎(jiǎng)勵(lì)預(yù)算與實(shí)際獎(jiǎng)勵(lì)之間的關(guān)系圖Fig.3 Reward budget and actual reward comparison chart

圖3(a)以及圖3(b)顯示了在閾值分別為ThB=2，ThB=0.8時(shí)，獎(jiǎng)勵(lì)預(yù)算金額與實(shí)際獎(jiǎng)勵(lì)金額之間的關(guān)系.我們?cè)O(shè)置閾值ThB的目的是使得實(shí)際獎(jiǎng)勵(lì)金額盡可能地靠近獎(jiǎng)勵(lì)預(yù)算B，以確保任務(wù)的完成質(zhì)量盡可能高.可以看到與閾值ThB=2時(shí)相比，在閾值ThB=0.8的情況下，實(shí)際的獎(jiǎng)勵(lì)金額會(huì)更接近獎(jiǎng)勵(lì)預(yù)算.因此，在相同的獎(jiǎng)勵(lì)預(yù)算限制下，其任務(wù)期望完成質(zhì)量下界Thmin也更高.

4.3 高質(zhì)量用戶以及低質(zhì)量用戶劃分結(jié)果

圖4是根據(jù)高質(zhì)量用戶和低質(zhì)量用戶的完成類型為k的任務(wù)期望完成質(zhì)量和平均獲得的獎(jiǎng)勵(lì)來表示他們的分布.我們通過公式(2)對(duì)用戶在該類任務(wù)中的期望完成質(zhì)量qi，k進(jìn)行計(jì)算，并與閾值Th進(jìn)行比較.將qi，k≥Th的用戶劃分為高質(zhì)量用戶，qi，k

圖4 高質(zhì)量用戶以及低質(zhì)量用戶劃分結(jié)果Fig.4 Result of user category division

4.4 低質(zhì)量用戶劃分結(jié)果

表1 低質(zhì)量用戶劃分結(jié)果Table 1 Result of low-quality user category division

將我們的劃分法與標(biāo)準(zhǔn)劃分方法相比較可以看到，在參與任務(wù)的低質(zhì)量用戶數(shù)量相同時(shí)，我們的劃分方法劃分出的不可轉(zhuǎn)換低質(zhì)量用戶數(shù)量遠(yuǎn)大于標(biāo)準(zhǔn)方法劃分出的不可轉(zhuǎn)換的低質(zhì)量用戶數(shù)量.同時(shí)，當(dāng)期望完成質(zhì)量相同時(shí)，我們的劃分方法總的獎(jiǎng)勵(lì)金額、可轉(zhuǎn)換的低質(zhì)量用戶平均所獲得的獎(jiǎng)勵(lì)金額以及不可轉(zhuǎn)換用戶平均所獲得的獎(jiǎng)勵(lì)金額均低于標(biāo)準(zhǔn)劃分方法對(duì)應(yīng)的各項(xiàng)獎(jiǎng)勵(lì)金額.因此，實(shí)驗(yàn)證實(shí)了我們所用的劃分方法更能有效的劃分低質(zhì)量用戶的類型.

5 總 結(jié)

本文研究了基于激勵(lì)機(jī)制的用戶分類任務(wù)分配問題.為了促進(jìn)將低質(zhì)用戶轉(zhuǎn)變?yōu)楦哔|(zhì)量用戶，本文首先提出一種用戶類型轉(zhuǎn)換機(jī)制，以便在任務(wù)分配過程中盡可能將任務(wù)分配給具有較高歷史完成質(zhì)量的用戶.通過合理的激勵(lì)機(jī)制，促進(jìn)了低質(zhì)量群智感知用戶的轉(zhuǎn)化.此外，提出了一種最優(yōu)任務(wù)及獎(jiǎng)勵(lì)分配算法，以最大化任務(wù)的最低完成質(zhì)量為優(yōu)化目標(biāo)，保證了所有任務(wù)間完成質(zhì)量的最大最小公平，使得在預(yù)算有限的情況下最大化任務(wù)完成的質(zhì)量.最后，通過仿真驗(yàn)證了所提機(jī)制的有效性.