卜霄菲，吳文江，辛 煜，黃 河，吳曉燦，楊雪華

(1. 中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所有限公司，遼寧 沈陽(yáng)110168；2. 沈陽(yáng)師范大學(xué) 軟件學(xué)院，遼寧 沈陽(yáng) 110034；3. 北京遙感信息研究所，北京 100011；4. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；5. 中國(guó)科學(xué)技術(shù)大學(xué) 蘇州研究院, 江蘇 蘇州 215123)

群智感知技術(shù)作為物聯(lián)網(wǎng)應(yīng)用的重要外延，旨在通過(guò)智能手機(jī)、可穿戴設(shè)備等附著在人身上的各類移動(dòng)終端設(shè)備在一個(gè)更加廣泛的感知區(qū)域內(nèi)實(shí)時(shí)獲取用戶感興趣的信息[1].群智感知應(yīng)用系統(tǒng)往往需要采集大量的數(shù)據(jù)以支撐系統(tǒng)的正常運(yùn)行.與傳統(tǒng)的無(wú)線傳感網(wǎng)絡(luò)采集數(shù)據(jù)方式不同，群智感知系統(tǒng)中的數(shù)據(jù)采集工作并非由固定員工完成，而是由系統(tǒng)將這些數(shù)據(jù)采集任務(wù)拆分成若干子任務(wù)[2-6]，然后分配給大量感興趣的匿名智能終端用戶完成.這種方式與傳統(tǒng)的數(shù)據(jù)采集方式相比，可以在降低數(shù)據(jù)采集任務(wù)的執(zhí)行時(shí)間和采集成本的基礎(chǔ)上，大幅提高數(shù)據(jù)的采集規(guī)模，從而更容易通過(guò)分析得到可信的結(jié)果，進(jìn)而為系統(tǒng)用戶提供優(yōu)質(zhì)的服務(wù)[7].

在群智感知系統(tǒng)中，不同用戶提交的數(shù)據(jù)質(zhì)量可能是存在差異的.由于不同用戶所持有的設(shè)備性能、對(duì)數(shù)據(jù)收集任務(wù)的理解程度以及對(duì)待任務(wù)的認(rèn)真程度等方面存在差異，導(dǎo)致感知數(shù)據(jù)的質(zhì)量也存在一定的差異.針對(duì)這一問(wèn)題，部分研究選擇多個(gè)用戶來(lái)完成同一任務(wù)，然后再通過(guò)多數(shù)選舉或加權(quán)多數(shù)選舉的方式選出最終的可信數(shù)據(jù)[8-11].例如，文[8]中限定每個(gè)任務(wù)最多分配給l個(gè)用戶來(lái)完成，并在此基礎(chǔ)上設(shè)計(jì)出誠(chéng)實(shí)的群智感知任務(wù)拍賣機(jī)制.然而，上述研究在僅僅是增加了完成任務(wù)的用戶數(shù)量，然后通過(guò)冗余數(shù)據(jù)的方式來(lái)保證任務(wù)的完成質(zhì)量，并未真正地考慮用戶的可靠性對(duì)任務(wù)分配過(guò)程的影響.為了解決該問(wèn)題，上海交通大學(xué)的吳帆研究團(tuán)隊(duì)提出在任務(wù)分配時(shí)首先預(yù)測(cè)用戶的期望任務(wù)完成質(zhì)量來(lái)選擇高可靠性的用戶，并根據(jù)用戶實(shí)際提交的數(shù)據(jù)質(zhì)量來(lái)決定用戶的最終支付，從而促使用戶提交高質(zhì)量的數(shù)據(jù)[12].文[13]以任務(wù)完成質(zhì)量最大化為優(yōu)化目標(biāo)，在任務(wù)分配時(shí)盡可能地選擇了可靠性較高的一組用戶來(lái)完成任務(wù).然而，群智感知中的任務(wù)是異質(zhì)的，用戶完成不同類型任務(wù)的可靠性也應(yīng)該是異質(zhì)的，上述研究均假設(shè)用戶完成不同任務(wù)的可靠性是相同的，沒(méi)有考慮到群智感知中存在的用戶分類可靠性問(wèn)題.文[14]在考慮任務(wù)多樣性的基礎(chǔ)上，研究如何對(duì)用戶在各類不同任務(wù)上的可靠性進(jìn)行評(píng)估.然而，該研究是針對(duì)眾包系統(tǒng)所設(shè)計(jì)的，無(wú)法直接應(yīng)用到群智感知系統(tǒng)中.

為了解決上述問(wèn)題，論文假設(shè)每個(gè)用戶針對(duì)不同類型的任務(wù)具有不同的可靠性，旨在綜合考慮用戶分類可靠性的報(bào)價(jià)的基礎(chǔ)上，選擇一組最合適的用戶完成感知任務(wù).為了使所設(shè)計(jì)的機(jī)制更具通用性，論文還假設(shè)群智感知系統(tǒng)中存在著多個(gè)數(shù)據(jù)消費(fèi)者.由于不同數(shù)據(jù)消費(fèi)者之間還存在著競(jìng)爭(zhēng)關(guān)系，所以論文以最大化收益最小的數(shù)據(jù)消費(fèi)者的收益作為優(yōu)化目標(biāo)，采用貪心技術(shù)，設(shè)計(jì)了一種高效的群智感知任務(wù)分配機(jī)制，以保證數(shù)據(jù)消費(fèi)者之間的公平性.除此之外，論文還設(shè)計(jì)了一種用戶分類可靠性的更新技術(shù)，以保證任務(wù)分配機(jī)制選擇最近一段時(shí)間提交數(shù)據(jù)質(zhì)量較高的用戶.最后，通過(guò)仿真實(shí)驗(yàn)對(duì)所設(shè)計(jì)機(jī)制的性能進(jìn)行了驗(yàn)證.

1 問(wèn)題模型

1.1 群智感知系統(tǒng)模型

平臺(tái)在收到所有用戶的任務(wù)請(qǐng)求后，會(huì)根據(jù)設(shè)定的用戶與任務(wù)之間的匹配原則，將任務(wù)分配給用戶完成.由于用戶所提交的數(shù)據(jù)可能是不可靠的，所以所研究的模型允許一個(gè)任務(wù)同時(shí)分配給多個(gè)用戶完成，以提高任務(wù)的期望完成質(zhì)量.但是，在每個(gè)分配周期，每個(gè)用戶最多只會(huì)分配到一個(gè)任務(wù).最后，平臺(tái)會(huì)發(fā)布任務(wù)分配結(jié)果，并在用戶完成任務(wù)后根據(jù)其完成任務(wù)的質(zhì)量更新用戶的分類可靠性，作為下一次任務(wù)分配的依據(jù).至此，一個(gè)群智感知任務(wù)分配周期結(jié)束.

1.2 問(wèn)題描述

由于群智感知系統(tǒng)中存在多個(gè)數(shù)據(jù)消費(fèi)者，且這些數(shù)據(jù)消費(fèi)者之間的利益是沖突的.所以，論文在考慮用戶分類可靠性的基礎(chǔ)上，設(shè)計(jì)了一種群智感知系統(tǒng)的任務(wù)分配機(jī)制，以數(shù)據(jù)消費(fèi)者的最大最小公平作為優(yōu)化目標(biāo)，實(shí)現(xiàn)用戶與群智感知任務(wù)的最優(yōu)匹配.

定義1滿足最大最小公平的任務(wù)分配機(jī)制：如果一個(gè)群智感知任務(wù)分配機(jī)制最大化了收益最小的數(shù)據(jù)消費(fèi)者的收益，那么該分配機(jī)制滿足數(shù)據(jù)消費(fèi)者的最大最小公平.

作者的優(yōu)化目標(biāo)是要實(shí)現(xiàn)數(shù)據(jù)消費(fèi)者之間的最大最小公平，即在滿足約束的條件下maxminui.

2 基于用戶分類可靠性的群智感知系統(tǒng)任務(wù)分配機(jī)制

所設(shè)計(jì)的機(jī)制主要包含兩部分：任務(wù)與用戶的最優(yōu)匹配機(jī)制和用戶分類可靠性的實(shí)時(shí)更新機(jī)制.其中，任務(wù)與用戶的匹配機(jī)制是要結(jié)合用戶的分類可靠性和報(bào)價(jià)，以滿足數(shù)據(jù)消費(fèi)者的最大最小公平為優(yōu)化目標(biāo)，將任務(wù)分配給最合適的一組用戶完成.而用戶分類可靠性的實(shí)時(shí)更新機(jī)制則要根據(jù)用戶每輪實(shí)際提交的數(shù)據(jù)質(zhì)量，更新分類用戶的可靠性，促使用戶更好地完成任務(wù).

2.1 任務(wù)與用戶的匹配機(jī)制

任務(wù)與用戶之間的匹配機(jī)制迭代進(jìn)行.每次迭代，群智感知平臺(tái)會(huì)選擇一個(gè)任務(wù)和用戶完成匹配.由于所設(shè)計(jì)的機(jī)制以實(shí)現(xiàn)數(shù)據(jù)消費(fèi)者的最大最小公平為優(yōu)化目標(biāo)，所以平臺(tái)在每次迭代開始會(huì)首先尋找當(dāng)前收益最低的數(shù)據(jù)消費(fèi)者，并期望完成該數(shù)據(jù)消費(fèi)者的一個(gè)任務(wù)與用戶之間的匹配，以提高該數(shù)據(jù)消費(fèi)者的收益.具體的實(shí)現(xiàn)細(xì)節(jié)如算法1所示.

算法1任務(wù)與用戶的匹配機(jī)制

1) 設(shè)置D′=D,S′=S；

2) While (數(shù)據(jù)消費(fèi)者集合D′≠φ)

3) {

4) 找到D′中具有最小收益的數(shù)據(jù)消費(fèi)者i；

6) for (每個(gè)sj∈S′)

7) {

9) {

10) 計(jì)算將任務(wù)ti,k分配給用戶sj所能帶來(lái)的收益增量Δui；

12) {

14) 設(shè)置maxs=sj；

15) 設(shè)置maxt=ti,k；

16) }

17) }

18) }

20) {

21) 將任務(wù)ti,k分配給用戶sj；

22) 將用戶sj從集合S′中刪除；

23) }

24) else

25) 將數(shù)據(jù)消費(fèi)者i從集合D′中刪除；

26) }

Δui=ui(Si,k∪{sj})-ui(Si,k).

在求Δui(Si,k)或Δui(Si,k∪{sj})的值時(shí)，首先Si,k或Si,k∪{sj}中的用戶按照可靠性從高到低排序.若sj是排序后Si,k或Si,k∪{sj}中的第l個(gè)用戶，那么sj所能為消費(fèi)者i帶來(lái)的收益為

αl-1rj,h*vi,k-pj,i,k，

其中:pj,i,k等于sj對(duì)任務(wù)ti,k的實(shí)際報(bào)價(jià).

在求得Si,k或Si,k∪{sj}中所有用戶的收益后，Δui(Si,k)或Δui(Si,k∪{sj})的值即為這些收益的總和.

2.2 用戶分類可靠性的更新機(jī)制

隱馬爾可夫模型作為一種統(tǒng)計(jì)模型，被用于描述一個(gè)包含隱含未知參數(shù)的馬爾可夫過(guò)程.隱馬爾可夫模型著重解決了如下問(wèn)題:在了解模型存在若干種隱含狀態(tài)后，可以根據(jù)可見狀態(tài)連鏈的具體情況，反推出隱含狀態(tài)間的轉(zhuǎn)換概率;在了解模型存在若干種隱含狀態(tài)和隱含狀態(tài)間的轉(zhuǎn)換概率后，也可以根據(jù)見狀態(tài)連鏈的具體情況，知道隱含狀態(tài)鏈的情況以及每一個(gè)隱含狀態(tài)產(chǎn)生的概率.這正與所需要解決的問(wèn)題相吻合.

在基于用戶可靠性的眾包系統(tǒng)分配機(jī)制中，需要用到用戶的可靠性信息來(lái)計(jì)算任務(wù)分配所能帶來(lái)的收益以及最終給用戶的報(bào)酬.為了能使用戶的可靠性信息能真實(shí)地反映用戶近期完成任務(wù)的質(zhì)量，每次任務(wù)分配結(jié)束后還應(yīng)該根據(jù)該輪用戶的任務(wù)完成質(zhì)量更新該用戶的可靠性信息.

由于用戶的工作狀態(tài)不可能始終保持一致，任務(wù)完成的質(zhì)量會(huì)受到或好或壞影響，因此對(duì)于用戶可靠性的評(píng)價(jià)，主要是依照用戶最近一次完成任務(wù)的質(zhì)量來(lái)完成的.再者，用戶在完成任務(wù)時(shí)往往會(huì)受到諸多外在因素的影響，同類型的任務(wù)完成質(zhì)量并不可能相同，而用戶完成多個(gè)同類任務(wù)的質(zhì)量序列反映了諸多未知的外在因素對(duì)用戶的影響程度.因此可以以用戶過(guò)去的任務(wù)質(zhì)量序列為輸入，建立一個(gè)隱馬爾可夫模型，來(lái)反映用戶在完成某一類型任務(wù)時(shí)，諸多未知的外在因素對(duì)用戶的影響程度，然后以所得對(duì)用戶下次完成此類任務(wù)時(shí)的表現(xiàn)進(jìn)行預(yù)測(cè).

在每次任務(wù)分配結(jié)束后，根據(jù)用戶的任務(wù)完成質(zhì)量以及此前該用戶完成同類型任務(wù)的完成質(zhì)量，建立隱馬爾可夫模型，通過(guò)Baum-Welch算法對(duì)模型進(jìn)行學(xué)習(xí)，反推出隱含狀態(tài)間的轉(zhuǎn)換概率.再根據(jù)所得的模型和任務(wù)完成質(zhì)量序列，得出用戶下次完成此類任務(wù)時(shí)最可能出現(xiàn)的表現(xiàn).

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

3.1 仿真模擬建立

在仿真模擬部分，假設(shè)在每一輪任務(wù)分配中有m個(gè)數(shù)據(jù)消費(fèi)者和n個(gè)用戶.設(shè)m=15，用戶的報(bào)價(jià)均勻分布于[0.7,1)，每個(gè)用戶任意從平臺(tái)發(fā)布的任務(wù)中選取1或2個(gè)任務(wù)作為自己感興趣的任務(wù).假定每一個(gè)任務(wù)實(shí)際價(jià)值與對(duì)應(yīng)的數(shù)據(jù)消費(fèi)者的預(yù)算相同,分別在兩個(gè)環(huán)境下進(jìn)行仿真實(shí)驗(yàn).在第一個(gè)環(huán)境中，假定數(shù)據(jù)消費(fèi)者i所要完成的任務(wù)數(shù)目|Ti|均勻分布于[5,8]范圍中，每一個(gè)任務(wù)預(yù)算均勻分布于[1.75,2)內(nèi).在第二個(gè)環(huán)境中，假定數(shù)據(jù)消費(fèi)者i所要完成的任務(wù)數(shù)目|Ti|為5，每一個(gè)任務(wù)預(yù)算為1.75.通過(guò)變換用戶數(shù)目n的大小來(lái)檢驗(yàn)在不同情形下機(jī)制的表性能.

對(duì)于每一個(gè)實(shí)驗(yàn)，重復(fù)進(jìn)行500次，再取其平均值作為實(shí)驗(yàn)結(jié)果.

3.2 性能分析

在圖1、2中，設(shè)α=0.5,并通過(guò)變化用戶數(shù)目n的大小來(lái)檢驗(yàn)機(jī)制的表性能.圖中的最大收益和最小收益依次是算法結(jié)果下收益最大和最小的數(shù)據(jù)消費(fèi)者所獲的收益.圖1是在第二個(gè)環(huán)境下機(jī)制產(chǎn)生的結(jié)果.由于每一個(gè)任務(wù)的預(yù)算、每一個(gè)數(shù)據(jù)消費(fèi)者所要完成的任務(wù)數(shù)目是相同的，如果機(jī)制滿足最大最小公平性，理論上來(lái)說(shuō)，最大效益的曲線應(yīng)該與最小效益的曲線十分接近.而從圖1上看，實(shí)驗(yàn)結(jié)果與上述分析是一致的.此外，也發(fā)現(xiàn)圖1的兩條曲線開始時(shí)斜率都較大，而隨著用戶數(shù)目的增加，曲線斜率趨于平穩(wěn).這是因?yàn)楫?dāng)用戶數(shù)目足夠大時(shí)，任務(wù)的預(yù)算不足或其收益已經(jīng)無(wú)法繼續(xù)增長(zhǎng)，平臺(tái)無(wú)法將任務(wù)分配給更多用戶了.

圖2是平臺(tái)在第一個(gè)環(huán)境下進(jìn)行任務(wù)分配得到的結(jié)果.由于任務(wù)的預(yù)算、數(shù)據(jù)消費(fèi)者所要完成的任務(wù)數(shù)目不完全相同，但用戶足夠多時(shí)，那些要完成的任務(wù)數(shù)目較多、任務(wù)預(yù)算較大的數(shù)據(jù)消費(fèi)者會(huì)獲得更大的收益.而對(duì)于要完成的任務(wù)數(shù)目較少的數(shù)據(jù)消費(fèi)者，分配給他們的用戶數(shù)目達(dá)到一定的值時(shí)，他們的收益便會(huì)固定不再增長(zhǎng).正如圖2所示，最大收益與最小收益的差是隨著用戶數(shù)目的增加而增大的.

在圖3、4中,設(shè)α=0.5,并通過(guò)變化用戶數(shù)目n的大小來(lái)檢驗(yàn)機(jī)制的表性能.可以發(fā)現(xiàn)，圖3、4的實(shí)驗(yàn)結(jié)果依次與圖1、2相似.因此，盡管α值越大，數(shù)據(jù)消費(fèi)者能獲得更多的收益，但所提機(jī)制的性能是不受α值的大小影響的.

圖1 α=0.5，環(huán)境2下數(shù)據(jù)消費(fèi)者的收益 圖2 α=0.5，環(huán)境1下數(shù)據(jù)消費(fèi)者的收益

圖3 α=0.67，環(huán)境2下數(shù)據(jù)消費(fèi)者的收益 圖4 α=0.67，環(huán)境1下數(shù)據(jù)消費(fèi)者的收益

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

針對(duì)群智感知系統(tǒng)中的任務(wù)分配問(wèn)題，研究了多數(shù)據(jù)消費(fèi)者模型下如何實(shí)現(xiàn)數(shù)據(jù)消費(fèi)者之間的最大最小公平，并在綜合考慮用戶的分類可靠性以及報(bào)價(jià)的基礎(chǔ)上，實(shí)現(xiàn)任務(wù)與用戶之間的最佳匹配;研究首先采用貪心技術(shù)，以實(shí)現(xiàn)數(shù)據(jù)消費(fèi)者的最大最小公平為優(yōu)化目標(biāo)，提出一種基于用戶分類可靠性的任務(wù)與用戶的匹配機(jī)制;提出一種用戶分類可靠性的更新機(jī)制，為下一輪任務(wù)分配提供依據(jù)，并激勵(lì)用戶高質(zhì)量地完成任務(wù);最后，通過(guò)仿真實(shí)驗(yàn)證明，所設(shè)計(jì)任務(wù)分配機(jī)制較好地實(shí)現(xiàn)了數(shù)據(jù)消費(fèi)者之間的最大最小公平，并保證了較高的任務(wù)完成質(zhì)量.

參考文獻(xiàn)：

[1] 劉云浩. 群智感知計(jì)算[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 2012, 8 (10): 38-41.

[2] BOUTSIS I, KALOGERAKI V. On task assignment for real-time reliable crowdsourcing[C]// IEEE 34th ICDCS, 2014: 1-10.

[3] GOEL G, NIKZAD A, SINGLA A. Mechanism design for crowdsourcing markets with heterogeneous tasks[C]// Second AAAI Conference on Human Computation and Crowdsourcing, 2014： 1-12.

[4] HE S, SHIN D H, ZHANG J, et al. Toward optimal allocation of location dependent tasks in crowdsensing[C]// IEEE INFOCOM , 2014, 5 (11): 745-753.

[5] JIN H, SU L, CHEN D, et al. Quality of information aware incentive mechanisms for mobile crowd sensing systems[C]// ACM MobiHoc, 2015: 167-176.

[6] XU W, HUANG H, SUN Y E, et al. DATA: a double auction based task assignment mechanism in crowdsourcing systems[C]// 8th International ICST Conference on Communications and Networking in China, 2014: 172-177.

[7] BI R, ZHENG X, TAN G. Optimal assignment for deadline aware tasks in the crowdsourcing[C]// IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom) (BDCloud-Social Com-SustainCom), 2016: 178-184.

[8] ZHAO D, MA H, LIU L. Frugal online incentive mechanisms for crowdsourcing tasks truthfully[J]. Computer Science, 2014, 37 (3): 103-122.

[9] ZHAO D, LI X Y, MA H. How to crowdsource tasks truthfully without sacrificing utility: online incentive mechanisms with budget constraint[C]// Proceedings of IEEE INFOCOM, 2014: 1213-1221.

[10] SONG Z, NGAI E, MA J, et al. A novel incentive negotiation mechanism for participatory sensing under budget constraints[C]// Proceedings of IEEE/ACM IWQoS, 2014: 326-331.

[11] DUAN L, KUBO T, SUGIYAMA K, et al. Incentive mechanisms for smartphone collaboration in data acquisition and distributed computing[C]// Proceedings of IEEE INFOCOM, 2012: 1701-1709.

[12] PENG D, WU F, CHEN G H. Pay as how well you do: A quality based incentive mechanism for crowdsensing[C]// Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2015), 2015: 177-186.

[13] 杜揚(yáng), 黃河, 孫玉娥, 等. 地理位置相關(guān)移動(dòng)感知系統(tǒng)任務(wù)分配問(wèn)題研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51 (11): 2374-2381.

[14] MA F, LI Y, LI Q, et al. Faitcrowd: fine grained truth discovery for crowdsourced data aggregation[C]// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2015), 2015: 745-754.