黃丹鐳，黃 河，，孫玉娥，陸 樂，吳曉燦，杜 揚

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

1 引 言

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

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

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

2 問題建模

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

2.1 系統(tǒng)模型

本文所研究的群智感知系統(tǒng)由一個任務(wù)發(fā)布者、一個群智感知平臺和若干移動終端用戶(后面簡稱用戶)組成.用U={1，2，…，m}來表示用戶集合，T={t1，t2，…，tn}來表示任務(wù)發(fā)布者發(fā)布的任務(wù)集合.所研究的群智感知系統(tǒng)的任務(wù)分配分周期進行.如圖1所示，每個任務(wù)周期開始時首先由任務(wù)發(fā)布者將需要完成的任務(wù)發(fā)布在群智感知平臺上.每個發(fā)布的群智感知任務(wù)包含一個任務(wù)描述，包含任務(wù)對用戶技能以及感知設(shè)備性能等方面的要求.除此之外，每個任務(wù)還包含一個任務(wù)報價bj，即當用戶完成任務(wù)后的實際支付.在本文所研究的模型中bj是一個固定值，不管將該任務(wù)分配給哪個用戶完成所支付的除獎勵之外的金額均等于bj.本文所研究的群智感知任務(wù)是異質(zhì)的，即不同任務(wù)對用戶的要求不同.在這里，我們將要求類似的任務(wù)認為是同一類任務(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)獎勵任務(wù)分配模型Fig.1 Structure of the allocation and reward system with user classification in crowdsensing system

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

2.2 問題描述

本文的設(shè)計目標是要使任務(wù)整體完成質(zhì)量最大化.為了實現(xiàn)這一點，我們希望將任務(wù)分配給完成質(zhì)量盡可能高的用戶.如果用戶i對任務(wù)tj感興趣，那么就稱用戶i是任務(wù)tj的候選用戶.但是，部分任務(wù)可能不存在高質(zhì)量的候選用戶.在這種情況下，就需要設(shè)計合理的激勵機制，使得這些任務(wù)的候選低質(zhì)量用戶更加認真的完成任務(wù)，進而轉(zhuǎn)換為高質(zhì)量用戶.任務(wù)發(fā)布者的總獎勵金額預(yù)算用B來表示.群智感知平臺分配給所有用戶的總獎勵金額應(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表示群智感知平臺將任務(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ì)量用戶.為了激勵低質(zhì)量用戶更好地完成任務(wù)，群智感知平臺會給部分用戶分配額外的獎勵.用ri來表示群智感知平臺給用戶i分配的獎勵.對于分配了任務(wù)的低質(zhì)量用戶，若該用戶最終高質(zhì)量地完成了任務(wù)，即提交的感知數(shù)據(jù)的質(zhì)量超過閾值Th，那么群智感知平臺會在收到數(shù)據(jù)后支付額外的獎勵ri；反之，若該用戶并未提交高質(zhì)量的感知數(shù)據(jù)，那么群智感知平臺并不會向該用戶支付獎勵.本文的設(shè)計目標是要實現(xiàn)任務(wù)間完成質(zhì)量的最大最小公平，也就是說要在滿足約束的前提下使得max minQj.

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

對于每個低質(zhì)量用戶，取最近l個提交低質(zhì)量數(shù)據(jù)的周期的獎勵與實際數(shù)據(jù)質(zhì)量提升信息，將實際數(shù)據(jù)質(zhì)量提升與獎勵間關(guān)系用最小二乘法擬合為一條二次曲線；若該用戶提交低質(zhì)量數(shù)據(jù)的周期小于l，則取所有提交低質(zhì)量數(shù)據(jù)的周期來擬合實際數(shù)據(jù)質(zhì)量提升與獎勵之間的關(guān)系曲線.因為同一用戶在不同類型任務(wù)上的完成質(zhì)量是不同的，所以需要為用戶提交低質(zhì)量數(shù)據(jù)的任務(wù)分類并分別擬合實際數(shù)據(jù)質(zhì)量提升與獎勵之間的關(guān)系曲線.用最小二乘法利用用戶i最近l次數(shù)據(jù)進行二次曲線擬合的步驟如下：

1)構(gòu)建向量

本文對數(shù)據(jù)進行二次曲線擬合，假設(shè)每個用戶i在任務(wù)類型為k有l(wèi)個歷史記錄，即有l(wèi)個只有一個特征的樣本.表示為(Δ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ù)的矩陣表達形式如公式(7)所示：

=ΘTΔQi，k

(7)

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

2)目標函數(shù)

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

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

(8)

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

3)優(yōu)化方法

將所定義的誤差函數(shù)進行求解，誤差函數(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ù)，并且非負，因此存在最小值.最小化J(Θ)等價于梯度為零：

=-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ù)及獎勵分配機制

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

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

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

輸出：分配向量與獎勵集合

1.while(T≠φ){

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

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

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

9. end if

10. end for

13. end if

14. end for

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

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

18.}end while

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

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

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

輸出：分配向量與獎勵集合

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è)置獎勵時的候選用戶的最大期望任務(wù)完成質(zhì)量.在此Thmin表示獎勵預(yù)算受限時所有任務(wù)的期望完成質(zhì)量的下界，即Thmin=min{Qj}tj∈T，那么很容易得到獎勵預(yù)算不足時Thmin滿足min{qj}tj∈T≤Thmin

4 實驗分析

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

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

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

4.2 獎勵預(yù)算與實際獎勵之間的關(guān)系

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

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

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

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

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

5 總 結(jié)

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