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

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

群智感知技術(shù)作為物聯(lián)網(wǎng)應(yīng)用的重要外延，旨在通過智能手機(jī)、可穿戴設(shè)備等附著在人身上的各類移動終端設(shè)備在一個更加廣泛的感知區(qū)域內(nèi)實(shí)時獲取用戶感興趣的信息[1].群智感知應(yīng)用系統(tǒng)往往需要采集大量的數(shù)據(jù)以支撐系統(tǒng)的正常運(yùn)行.與傳統(tǒng)的無線傳感網(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í)行時間和采集成本的基礎(chǔ)上，大幅提高數(shù)據(jù)的采集規(guī)模，從而更容易通過分析得到可信的結(jié)果，進(jìn)而為系統(tǒng)用戶提供優(yōu)質(zhì)的服務(wù)[7].

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

為了解決上述問題，論文假設(shè)每個用戶針對不同類型的任務(wù)具有不同的可靠性，旨在綜合考慮用戶分類可靠性的報價的基礎(chǔ)上，選擇一組最合適的用戶完成感知任務(wù).為了使所設(shè)計(jì)的機(jī)制更具通用性，論文還假設(shè)群智感知系統(tǒng)中存在著多個數(shù)據(jù)消費(fèi)者.由于不同數(shù)據(jù)消費(fèi)者之間還存在著競爭關(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ù)據(jù)質(zhì)量較高的用戶.最后，通過仿真實(shí)驗(yàn)對所設(shè)計(jì)機(jī)制的性能進(jìn)行了驗(yàn)證.

1 問題模型

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

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

1.2 問題描述

由于群智感知系統(tǒng)中存在多個數(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ī)制：如果一個群智感知任務(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í)時更新機(jī)制.其中，任務(wù)與用戶的匹配機(jī)制是要結(jié)合用戶的分類可靠性和報價，以滿足數(shù)據(jù)消費(fèi)者的最大最小公平為優(yōu)化目標(biāo)，將任務(wù)分配給最合適的一組用戶完成.而用戶分類可靠性的實(shí)時更新機(jī)制則要根據(jù)用戶每輪實(shí)際提交的數(shù)據(jù)質(zhì)量，更新分類用戶的可靠性，促使用戶更好地完成任務(wù).

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

任務(wù)與用戶之間的匹配機(jī)制迭代進(jìn)行.每次迭代，群智感知平臺會選擇一個任務(wù)和用戶完成匹配.由于所設(shè)計(jì)的機(jī)制以實(shí)現(xiàn)數(shù)據(jù)消費(fèi)者的最大最小公平為優(yōu)化目標(biāo)，所以平臺在每次迭代開始會首先尋找當(dāng)前收益最低的數(shù)據(jù)消費(fèi)者，并期望完成該數(shù)據(jù)消費(fèi)者的一個任務(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 (每個sj∈S′)

7) {

9) {

10) 計(jì)算將任務(wù)ti,k分配給用戶sj所能帶來的收益增量Δ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})的值時，首先Si,k或Si,k∪{sj}中的用戶按照可靠性從高到低排序.若sj是排序后Si,k或Si,k∪{sj}中的第l個用戶，那么sj所能為消費(fèi)者i帶來的收益為

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

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

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

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

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

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

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

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

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

3.1 仿真模擬建立

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

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

3.2 性能分析

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

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

在圖3、4中,設(shè)α=0.5,并通過變化用戶數(shù)目n的大小來檢驗(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é)束語

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

參考文獻(xiàn)：

[1] 劉云浩. 群智感知計(jì)算[J]. 中國計(jì)算機(jī)學(xué)會通訊, 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)移動感知系統(tǒng)任務(wù)分配問題研究[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.