移動(dòng)眾包環(huán)境下一種多階段質(zhì)量感知的在線激勵(lì)機(jī)制

高麗萍,孫明達(dá),高 麗,陳慶奎

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

2(復(fù)旦大學(xué) 上海數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室,上海 200093)

3(上海理工大學(xué) 圖書(shū)館,上海 200093)

1 引 言

通信技術(shù)和移動(dòng)智能終端的發(fā)展讓移動(dòng)設(shè)備能夠采集到多種傳感數(shù)據(jù),這使得智能手機(jī)用戶能夠輕松發(fā)現(xiàn)并分享數(shù)據(jù).于是移動(dòng)眾包(MCS)成為了一個(gè)熱門話題,其融合了智能手機(jī)和眾包的特點(diǎn),利用廣大的移動(dòng)用戶群體來(lái)分享信息,提高社會(huì)福利.同時(shí),MCS可以結(jié)合云服務(wù),物聯(lián)網(wǎng)等前沿技術(shù),使其在物流運(yùn)輸,環(huán)境監(jiān)控,社交網(wǎng)絡(luò)等各個(gè)領(lǐng)域被廣泛運(yùn)用[1,2].

一個(gè)典型的移動(dòng)眾包應(yīng)用主要基于3類實(shí)體,任務(wù)請(qǐng)求者、任務(wù)參與者(簡(jiǎn)稱工人)和眾包平臺(tái).請(qǐng)求者將一些感知任務(wù)發(fā)布到平臺(tái)上,并設(shè)置一些要求(預(yù)算,截止時(shí)間等).對(duì)任務(wù)感興趣的工人向平臺(tái)提出執(zhí)行任務(wù)的請(qǐng)求,平臺(tái)收集到工人信息后合理地分配任務(wù).最后根據(jù)工人的任務(wù)完成情況,平臺(tái)給予其一些回饋.由于眾包工人來(lái)源于互聯(lián)網(wǎng),存在較多不確定因素,工人持續(xù)提交低質(zhì)量感知數(shù)據(jù)會(huì)影響MCS平臺(tái)的可靠性和精確性,損害請(qǐng)求者的利益.如何有效地激勵(lì)工人參與任務(wù)并且得到高質(zhì)量的傳感數(shù)據(jù)成為MCS的核心問(wèn)題.

因此,一個(gè)可靠的MCS平臺(tái)需要設(shè)計(jì)有效的激勵(lì)機(jī)制[3].許多激勵(lì)機(jī)制建立在金錢激勵(lì)上,即每個(gè)工人對(duì)任務(wù)有一個(gè)報(bào)價(jià),表示他所消耗的物質(zhì)資源或所提供勞動(dòng)力的貨幣價(jià)值,并期望自己的貢獻(xiàn)能夠獲得回報(bào).如果沒(méi)有足夠的獎(jiǎng)勵(lì),工人就沒(méi)有動(dòng)力參與任務(wù).平臺(tái)根據(jù)報(bào)價(jià)和工人其余信息來(lái)決定任務(wù)的分配和報(bào)酬.在離線場(chǎng)景下,平臺(tái)先收集所有工人的信息后再進(jìn)行調(diào)度分配,這使得平臺(tái)比較容易針對(duì)不同的目標(biāo)(如最大化效用[3-6]、最大化社會(huì)福利[7-9]、最小化報(bào)酬[10,11]),配合一些限制條件選擇最優(yōu)的工人集.然而在現(xiàn)實(shí)中,工人是以隨機(jī)動(dòng)態(tài)的方式到達(dá)或離開(kāi)平臺(tái).與離線場(chǎng)景相比,MCS平臺(tái)在在線場(chǎng)景中無(wú)法事先得知工人會(huì)在什么時(shí)間段參與任務(wù).一旦工人上線,需要立即做抉擇,即是否接受或拒絕工人的請(qǐng)求,同時(shí)當(dāng)任務(wù)分配給工人后,還需要根據(jù)已有的信息決定報(bào)酬.

此外,激勵(lì)機(jī)制的設(shè)計(jì)還需考慮質(zhì)量評(píng)估.MCS的任務(wù)大多以提交傳感數(shù)據(jù)為主,如監(jiān)測(cè)某個(gè)地區(qū)的噪聲、溫度、路面狀況等.由于傳感器和動(dòng)態(tài)環(huán)境的不一致,移動(dòng)用戶采集的傳感數(shù)據(jù)通常存在噪聲或不同程度的誤差.在無(wú)法準(zhǔn)確了解每個(gè)工人的感知行為和任務(wù)地點(diǎn)的真實(shí)情況下,平臺(tái)很難去判斷傳感數(shù)據(jù)的質(zhì)量.同時(shí)在MCS應(yīng)用中,獲取真實(shí)的樣本數(shù)據(jù)(Ground Truth)作為其它傳感數(shù)據(jù)的質(zhì)量標(biāo)準(zhǔn)是困難的,在很多情況下甚至是不現(xiàn)實(shí)的[4].這時(shí)候,平臺(tái)可以先發(fā)布一些任務(wù),采集足夠多的歷史數(shù)據(jù)后判斷數(shù)據(jù)質(zhì)量,推測(cè)出每個(gè)工人的可靠程度.但是請(qǐng)求者有固定的預(yù)算,這限制了平臺(tái)不能無(wú)限次分配任務(wù)來(lái)獲取大量歷史數(shù)據(jù).所以MCS的激勵(lì)機(jī)制需要制定一個(gè)有效的質(zhì)量評(píng)估方式.

本文之前的工作[5]提出了一種長(zhǎng)時(shí)間質(zhì)量感知的激勵(lì)機(jī)制策略(QAI),將眾包任務(wù)分配過(guò)程分成多個(gè)階段,同時(shí)把工人的質(zhì)量看作是隱變量,各個(gè)階段的請(qǐng)求者都會(huì)給工人提交的答案進(jìn)行打分,平臺(tái)則根據(jù)這些分?jǐn)?shù)運(yùn)用隱馬爾可夫模型來(lái)預(yù)測(cè)下一階段的工人質(zhì)量.然而,QAI是一個(gè)離線場(chǎng)景下的激勵(lì)機(jī)制,同時(shí)假設(shè)了請(qǐng)求者可以直接評(píng)估工人的任務(wù)結(jié)果,無(wú)法解決前面提到的問(wèn)題.因此,本文在QAI的基礎(chǔ)上進(jìn)一步考慮在線工人選擇問(wèn)題,提出一種多階段質(zhì)量感知的在線激勵(lì)機(jī)制(SQOI).具體的貢獻(xiàn)如下:

·本文考慮了預(yù)算與時(shí)間約束下的在線工人選擇問(wèn)題,將眾包活動(dòng)周期分成多個(gè)階段,設(shè)計(jì)了階段性的系統(tǒng)與質(zhì)量模型,通過(guò)靜態(tài)質(zhì)量和動(dòng)態(tài)質(zhì)量來(lái)評(píng)定各個(gè)階段在線工人的服務(wù)質(zhì)量.

·根據(jù)模型,提出多階段質(zhì)量感知的在線激勵(lì)機(jī)制SQOI,設(shè)計(jì)了具體的框架,集成了階段性工人選擇、質(zhì)量預(yù)估和參數(shù)更新三個(gè)模塊.理論證明了SQOI具有預(yù)算可行性、個(gè)體合理性、真實(shí)性和計(jì)算效率.

·通過(guò)實(shí)驗(yàn)測(cè)試了SQOI在不同參數(shù)下的性能,并且證明了SQOI在提升數(shù)據(jù)質(zhì)量上的有效性.

論文的其余部分組織如下:第2節(jié)對(duì)相關(guān)工作進(jìn)行了介紹.第3節(jié)介紹了系統(tǒng)模型和效用計(jì)算.第4節(jié)給出了多階段質(zhì)量感知的在線激勵(lì)機(jī)制框架和相關(guān)算法設(shè)計(jì).第5節(jié)對(duì)SQOI進(jìn)行了仿真實(shí)驗(yàn).結(jié)論在最后一節(jié)中給出.

2 相關(guān)工作

2.1 激勵(lì)機(jī)制

如今,已有許多關(guān)于MCS的激勵(lì)機(jī)制研究.大多數(shù)的工作是針對(duì)離線場(chǎng)景下的激勵(lì)機(jī)制,即平臺(tái)在分配之前就得到了工人與任務(wù)的所有信息,如工人的能力,偏好,報(bào)價(jià)等.同時(shí)平臺(tái)會(huì)指定某一目標(biāo),這樣工人的選擇問(wèn)題變?yōu)榱嗽谔囟s束下的規(guī)劃問(wèn)題,需要設(shè)計(jì)算法求解該問(wèn)題.如Yang等人[3]運(yùn)用Stackelberg博弈思想設(shè)計(jì)激勵(lì)機(jī)制,最大化用戶的效用.Peng等人[6]從提高傳感數(shù)據(jù)質(zhì)量的角度上設(shè)計(jì)激勵(lì)機(jī)制,并運(yùn)用信息論度量每個(gè)參與者的有效數(shù)據(jù)貢獻(xiàn).Wen等人[7]提出一種基于質(zhì)量驅(qū)動(dòng)的拍賣激勵(lì)機(jī)制,并提出一種概率方案來(lái)評(píng)估數(shù)據(jù)的準(zhǔn)確性.Jin等人[8]則將用戶信息質(zhì)量作為激勵(lì)機(jī)制的一個(gè)重要指標(biāo),同時(shí)將任務(wù)分配問(wèn)題看作一種集合覆蓋問(wèn)題,設(shè)計(jì)了一種組合的反向拍賣模型來(lái)提高社會(huì)福利.以上研究都是基于離線場(chǎng)景下,不適用于工人實(shí)時(shí)到達(dá)的在線場(chǎng)景.

當(dāng)前也有一些關(guān)于眾包的在線場(chǎng)景研究.Singer等人[10]提出了一種競(jìng)價(jià)模型,從預(yù)算范圍內(nèi)最大化任務(wù)數(shù)量和最小化支付報(bào)酬兩種目標(biāo)考慮激勵(lì)相容機(jī)制的實(shí)現(xiàn).Zhao 等人[12]基于在線競(jìng)價(jià)模型,研究在指定預(yù)算下的服務(wù)價(jià)值最大化問(wèn)題.同時(shí)在文獻(xiàn)[11]以最小化MCS的任務(wù)報(bào)酬為目標(biāo)設(shè)計(jì)了節(jié)儉式的在線激勵(lì)機(jī)制.一些研究[9,13-15]將經(jīng)典的多臂賭博機(jī)模型用在移動(dòng)眾包的在線任務(wù)分配中.其主要思想是以在線學(xué)習(xí)的方式權(quán)衡眾包環(huán)境下未知工人的探索與利用,在分配任務(wù)的過(guò)程,逐步對(duì)每個(gè)工人的能力和偏好有全面的認(rèn)知.其中文獻(xiàn)[9,13]在工人選擇上進(jìn)一步考慮其上下文信息,對(duì)工人的服務(wù)質(zhì)量進(jìn)行建模,盡可能地選取高質(zhì)量工人.Han等人[14]提出BLISS框架來(lái)解決有限預(yù)算下的最大化傳感收益問(wèn)題.Gao等人[15]則考慮預(yù)算和覆蓋限制下工人招募問(wèn)題,從招募成本同質(zhì)和異質(zhì)兩種情況進(jìn)行研究.然而以上的研究都假設(shè)了工人的數(shù)據(jù)質(zhì)量或貢獻(xiàn)可以直接得到.

2.2 數(shù)據(jù)質(zhì)量評(píng)估

由于在很多眾包場(chǎng)景下,任務(wù)請(qǐng)求者需要由第三方平臺(tái)為其判斷工人提交的數(shù)據(jù)質(zhì)量,甚至為每個(gè)任務(wù)集成一個(gè)可靠準(zhǔn)確的答案,因此眾包的質(zhì)量評(píng)估成為了研究的熱點(diǎn).Hung 等人[16]采用了多數(shù)投票算法,任務(wù)分配給多個(gè)工人獨(dú)立完成,平臺(tái)將收集的數(shù)據(jù)中的多數(shù)意見(jiàn)作為最終的正確結(jié)果.這個(gè)方法將所有工人的感知數(shù)據(jù)在質(zhì)量和貢獻(xiàn)上視為平等,沒(méi)有考慮工人的多樣性,最終的結(jié)果往往不準(zhǔn)確.Zhang等人[17]則在標(biāo)簽收集任務(wù)中,將工人執(zhí)行不同類別任務(wù)的可靠性作為權(quán)重,設(shè)置加權(quán)多數(shù)投票算法,得到每個(gè)任務(wù)的真實(shí)標(biāo)簽.然而其考慮的任務(wù)是基于二進(jìn)制標(biāo)簽,不適用于連續(xù)性的移動(dòng)傳感數(shù)據(jù).同樣Liu等人[18]采用MAB模型來(lái)提升數(shù)據(jù)集標(biāo)記任務(wù)的質(zhì)量,其評(píng)估結(jié)果是離散的.Li 等人[19]進(jìn)一步使用迭代式加權(quán)多數(shù)投票算法來(lái)減少標(biāo)簽聚合的錯(cuò)誤率.Liu等人[4]研究了感知上下文與數(shù)據(jù)質(zhì)量的關(guān)系,通過(guò)構(gòu)建一個(gè)上下文數(shù)據(jù)質(zhì)量分類器來(lái)實(shí)時(shí)估計(jì)工人數(shù)據(jù)質(zhì)量.Yang等人[20]通過(guò)無(wú)監(jiān)督學(xué)習(xí)的方式,將傳感數(shù)據(jù)聚類成多個(gè)中心,測(cè)量每個(gè)用戶的數(shù)據(jù)與中心的偏離值作為其質(zhì)量.

本文結(jié)合現(xiàn)有研究的優(yōu)缺點(diǎn),針對(duì)移動(dòng)傳感數(shù)據(jù)的特點(diǎn)來(lái)研究MCS在線場(chǎng)景下的激勵(lì)機(jī)制,設(shè)計(jì)了SQOI框架,旨在指定預(yù)算和時(shí)間限制下,為任務(wù)請(qǐng)求者選取能夠提供高質(zhì)量傳感數(shù)據(jù)的工人.

3 系統(tǒng)模型和效用計(jì)算

在本節(jié)中,我們將介紹系統(tǒng)模型和質(zhì)量模型,并且定義了本文所解決的問(wèn)題.為了更清楚、更簡(jiǎn)單地理解不同符號(hào)的含義,表1給出了文中出現(xiàn)的符號(hào)及其描述.

表1 符號(hào)說(shuō)明

3.1 系統(tǒng)模型

首先,考慮一個(gè)在線MCS系統(tǒng),其中包含了一些用戶和一個(gè)中心化平臺(tái).任務(wù)請(qǐng)求者向平臺(tái)發(fā)布了一系列傳感任務(wù)T={1,2,…,|T|},同時(shí)設(shè)置了預(yù)算B和活動(dòng)周期D,前者規(guī)定了支付給工人的報(bào)酬上限,后者規(guī)定任務(wù)需要在指定時(shí)間內(nèi)完成.平臺(tái)擁有一些工人W={1,2,…,|W|},這些工人的移動(dòng)設(shè)備上都安裝了MCS的應(yīng)用程序.每個(gè)工人存在兩種狀態(tài):上線和離線.當(dāng)工人設(shè)備上的MCS程序正在運(yùn)行,其處于上線狀態(tài),準(zhǔn)備參與任務(wù)；反之,當(dāng)程序關(guān)閉后,其處于離線狀態(tài),無(wú)法參與任務(wù).

由于涉及到金錢激勵(lì),本文將任務(wù)與工人的匹配視作一個(gè)在線競(jìng)價(jià)過(guò)程.圖1具體描述了整個(gè)在線MCS系統(tǒng)的執(zhí)行流程.首先MCS平臺(tái)對(duì)外發(fā)布這些傳感任務(wù).當(dāng)工人j上線后,決定是否參與任務(wù),如果選擇參與,向平臺(tái)提交他的請(qǐng)求,包括報(bào)價(jià)bj、上線時(shí)間olj、離線時(shí)間ofj和執(zhí)行的任務(wù)集T(j).接著平臺(tái)根據(jù)工人的請(qǐng)求,在無(wú)法了解工人的情況下,決定是否聘用該工人.為了維護(hù)工人的權(quán)益,該決定是不可撤銷的.最后如果工人被選中,他需要執(zhí)行任務(wù)并提交自己的傳感數(shù)據(jù).平臺(tái)將賦予其一筆報(bào)酬pj.該過(guò)程將不斷重復(fù),直到累計(jì)報(bào)酬超出預(yù)算或任務(wù)過(guò)期為止.

圖1 MCS的執(zhí)行流程

3.2 質(zhì)量模型

工人分配到傳感任務(wù)后,需要在規(guī)定時(shí)間內(nèi)提交傳感數(shù)據(jù).本文考慮一種普遍的場(chǎng)景,即請(qǐng)求者需要第三方平臺(tái)來(lái)判斷任務(wù)的結(jié)果和工人的表現(xiàn).如環(huán)境噪音、溫度檢測(cè)這類傳感任務(wù),請(qǐng)求者需要采集一段時(shí)間內(nèi)不同地點(diǎn)的數(shù)據(jù),且事先無(wú)法得知標(biāo)準(zhǔn)值.在這種情況下,他需要MCS平臺(tái)發(fā)布任務(wù)收集數(shù)據(jù),并為每個(gè)任務(wù)預(yù)估出較為精確的結(jié)果.

(1)

(2)

3.3 效用計(jì)算

本文站在請(qǐng)求者的角度上研究問(wèn)題,即在固定的活動(dòng)周期內(nèi),工人以在線的形式請(qǐng)求執(zhí)行任務(wù),平臺(tái)需要在有限的預(yù)算內(nèi)選擇能夠提供高質(zhì)量傳感數(shù)據(jù)的工人.用Ms表示第s階段平臺(tái)選擇的工人,于是請(qǐng)求者每個(gè)階段的效用為:

(3)

由于Bs是常量,所以目標(biāo)函數(shù)可以轉(zhuǎn)變?yōu)?

(4)

(5)

平臺(tái)制定有效的激勵(lì)機(jī)制來(lái)盡可能地提升請(qǐng)求者的效用,同時(shí)需要滿足以下幾個(gè)性質(zhì):

1)預(yù)算可行性:累計(jì)的任務(wù)報(bào)酬不能超過(guò)預(yù)算限制,如公式(5)所示.

4)計(jì)算效率:提出的激勵(lì)機(jī)制可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算.

4 多階段質(zhì)量感知的在線激勵(lì)機(jī)制框架設(shè)計(jì)

本節(jié)主要介紹SQOI的具體框架設(shè)計(jì).在3.1節(jié),整個(gè)眾包活動(dòng)周期被分成了多個(gè)階段,平臺(tái)需要在每個(gè)階段對(duì)上線的工人進(jìn)行選擇、給予合適的報(bào)酬、評(píng)估數(shù)據(jù)質(zhì)量并更新相關(guān)參數(shù),為下一階段做參考.所以SQOI把每個(gè)階段又分為階段性工人選擇、質(zhì)量預(yù)估和參數(shù)更新3個(gè)模塊.由于各個(gè)階段的處理方式一致,為了簡(jiǎn)化符號(hào),下文統(tǒng)一將上標(biāo)s忽略.

4.1 階段性工人選擇

在離線場(chǎng)景下,所有工人事先提交信息,平臺(tái)計(jì)算這些工人的服務(wù)質(zhì)量后,選取前k個(gè)質(zhì)量最高的工人即可最大化請(qǐng)求者的效用.而在線場(chǎng)景下,工人以隨機(jī)的形式一個(gè)接一個(gè)地上線,平臺(tái)無(wú)法獲得全局信息,這種情況類似于經(jīng)典的秘書(shū)問(wèn)題.本文采用階段性工人選擇算法,每個(gè)階段輸入閾值θ作為工人的選擇標(biāo)準(zhǔn).在當(dāng)前階段結(jié)束后,統(tǒng)計(jì)該階段中所有在線工人的報(bào)價(jià)和預(yù)估的質(zhì)量,計(jì)算后更新θ,作為下一階段的輸入.首階段的閾值由平臺(tái)設(shè)定.

算法1.Phased Worker Selection

輸入:任務(wù)集T,預(yù)算B,活動(dòng)周期D,閾值θ

輸出:分配結(jié)果M,支付報(bào)酬P(guān)

初始化M←φ,M′←φ,d←1

1.whiled≤Ddo

2.ifwjarriving at time stepdthen

5. end if

6.M′←M′∪{j}

7.end if

8.ifd=Dthen

9. obtain all the dataXworkers submit

10.tr,E←Quality_Estimate(M,X)

11.θ←Parameter_Update(tr,X,M,M′)

12.end if

13.t←t+1

14.end while

15.returnM,P,θ

4.2 質(zhì)量預(yù)估

在每個(gè)階段末,平臺(tái)收集完工人提交的數(shù)據(jù)后,如果事先得知每個(gè)任務(wù)的真實(shí)結(jié)果,那么可以判斷工人提交的傳感數(shù)據(jù)是否通過(guò)標(biāo)準(zhǔn),從而評(píng)估工人的服務(wù)質(zhì)量.在本文的場(chǎng)景下,請(qǐng)求者無(wú)法給定每個(gè)任務(wù)的正確答案,即tri是一個(gè)隱藏變量,這導(dǎo)致了工人的效用矩陣無(wú)法直接獲取.因此平臺(tái)需要根據(jù)工人提交的傳感數(shù)據(jù)推測(cè)出最接近的答案.假設(shè)每個(gè)階段平臺(tái)能夠收集到大量的數(shù)據(jù),那么在參數(shù)未知的情況下,可以借助期望最大化(EM)算法的思想求得tri的最大似然估計(jì),從而預(yù)估出真實(shí)數(shù)據(jù)所在的區(qū)間[6].

(6)

(7)

同時(shí),可以得到每個(gè)區(qū)間的先驗(yàn)估計(jì):

(8)

(9)

即:

(10)

由于EM算法是一個(gè)迭代的方法,該模塊會(huì)重復(fù)計(jì)算每個(gè)工人的效用矩陣和每個(gè)任務(wù)的真實(shí)結(jié)果分布,直至參數(shù)收斂,最終得到一個(gè)準(zhǔn)確的結(jié)果.

算法2.Quality Estimate

輸入:匹配集M,數(shù)據(jù)集X

輸出:任務(wù)真實(shí)結(jié)果分布tr,工人的效用矩陣E,

1.fori∈Tdo

2. form∈σdo

4. end for

5.end for

6.whiletr,Edid not converge do

7. for m∈σ

8. calculatetlmaccording to equation (8)

9. end for

10. for j ∈Mdo

12. form,n∈σdo

14. end for

15. end for

16. fori∈Tdo

18. form∈σdo

20. end for

21. end for

22.end while

23.returntr,E

4.3 參數(shù)更新

得到每個(gè)任務(wù)的真實(shí)區(qū)間概率和每個(gè)工人的效用矩陣后,平臺(tái)需要更新相關(guān)參數(shù).具體由算法3所示,主要分為兩部分,第1部分更新了工人的動(dòng)態(tài)質(zhì)量和靜態(tài)質(zhì)量(1-11行).第2部分根據(jù)采樣集M′中工人質(zhì)量和報(bào)價(jià)計(jì)算出一個(gè)新的閾值θ(12-16行).其中參數(shù)δ由平臺(tái)設(shè)置,用來(lái)控制θ的大小,如果δ較小,θ變大,下一階段可以選擇的工人可能變少,導(dǎo)致階段任務(wù)分配率降低.反之δ較大,選擇工人的標(biāo)準(zhǔn)降低,可能造成數(shù)據(jù)質(zhì)量下降,浪費(fèi)了預(yù)算.

算法3.Parameter Update

輸入:真實(shí)結(jié)果分布tr,數(shù)據(jù)集X,匹配集M,采樣集M′

輸出:下一個(gè)階段閾值θ

1. for(T(j),j)∈M,i∈T(j)do

2. get the intervalnofxi,j

4.αj←αj+1

5. else

6.βj←βj+1

7. end if

8. end for

9. forj∈Wdo

10. updatedqj,sqjfor next stage

11. end for

12.J←φ,sum←0,k←argmaxj∈M′(dqjsqj|T(j)|/bj)

13. while ∑j∈J∪{k}bj≤Bdo

14.J←J∪{k},sum←sum+dqksqk|T(k)|

15.k←argmaxj∈M′-J(dqjsqj|T(j)|/bj)

16.end while

17.returnsum/δB

4.4 理論證明

這一部分主要證明SQOI具備預(yù)算可行性、個(gè)體合理性、真實(shí)性以及計(jì)算效率.

定理1.SQOI具備預(yù)算可行性.

證明:SQOI將整個(gè)眾包活動(dòng)周期分為多個(gè)階段.同時(shí)每個(gè)階段都包含有限的預(yù)算(2s-1B/2[log2D]).在算法1的第3行,當(dāng)一個(gè)工人上線并提交他的報(bào)價(jià)后,平臺(tái)會(huì)比較當(dāng)前階段剩余預(yù)算是否高于工人的預(yù)計(jì)報(bào)酬, 如果前者低于后者,即使工人滿足質(zhì)量標(biāo)準(zhǔn)也不會(huì)分配任務(wù).因此框架滿足預(yù)算可行性.

定理2.SQOI具備個(gè)體合理性.

定理3.SQOI具備真實(shí)性.

所以在任何情況下,工人在虛假報(bào)價(jià)下的效用始終不會(huì)超過(guò)真實(shí)報(bào)價(jià)下的效用,即SQOI具備真實(shí)性.

定理4.SQOI具備計(jì)算效率.

證明:由于SQOI框架是在線運(yùn)行的,所以需要考慮每個(gè)階段的復(fù)雜度.假設(shè)平臺(tái)的工人數(shù)為|W|,任務(wù)數(shù)為|T|.算法1的工人選擇階段最多需要執(zhí)行|W|次.在階段末,|σ|表示數(shù)據(jù)區(qū)間總數(shù),則運(yùn)行質(zhì)量評(píng)估模塊(算法2)最多需要|W‖T‖σ|次迭代.|σ|由平臺(tái)設(shè)置,可以將其作為一個(gè)常量來(lái)對(duì)待,則復(fù)雜度為O(|W‖T|).在參數(shù)更新模塊(算法3),1-11行每個(gè)工人需要運(yùn)行|T(j)|次,即最多需要O(|W‖T|).在12-16行的閾值計(jì)算部分,最多需要運(yùn)行|W|log|W|次.因此,每個(gè)階段的時(shí)間復(fù)雜度為O(|W‖T|),SQOI具備計(jì)算效率.

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

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證SQOI在不同參數(shù)下的表現(xiàn)和其在提升請(qǐng)求者效用上的有效性.

5.1 實(shí)驗(yàn)設(shè)置

表2 實(shí)驗(yàn)參數(shù)設(shè)置

本文設(shè)計(jì)了3個(gè)實(shí)驗(yàn).第1個(gè)實(shí)驗(yàn)研究了SQOI在不同工人到達(dá)率下對(duì)效用的影響.第2個(gè)實(shí)驗(yàn)研究了SQOI參數(shù)更新模塊的輸入?yún)?shù)δ對(duì)效用的影響.第3個(gè)實(shí)驗(yàn)將階段離線算法(Offline)和在線隨機(jī)算法(Random)作為基線算法,同SQOI進(jìn)行對(duì)比.在階段離線算法中,平臺(tái)能夠事先得到各個(gè)階段的工人上線時(shí)間、報(bào)價(jià)和服務(wù)質(zhì)量,然后選擇效用最高的k個(gè)工人.在線隨機(jī)算法則是在各個(gè)時(shí)刻隨機(jī)選擇上線的工人.

5.2 實(shí)驗(yàn)結(jié)果

首先本文研究了在相同環(huán)境下,不同到達(dá)率對(duì)效用的影響.由圖2所示,當(dāng)用戶到達(dá)率增加,整體效用增大.同時(shí)當(dāng)?shù)竭_(dá)率在較高的區(qū)間內(nèi),高預(yù)算可以得到更大的效用值.因?yàn)楣と藚⑴c任務(wù)的積極性一旦變高,平臺(tái)可以在初期階段收集充足的傳感數(shù)據(jù)和采樣集,對(duì)每個(gè)在線工人的質(zhì)量有更為準(zhǔn)確的評(píng)估,所以算法1在后期階段可以選擇高質(zhì)量的工人集,提高請(qǐng)求者的效用.

圖2 工人到達(dá)率λ對(duì)效用的影響

接著本文針對(duì)算法3的輸入?yún)?shù)δ進(jìn)行研究.固定預(yù)算為2000,比較到達(dá)率不同時(shí),參數(shù)δ對(duì)算法性能的影響.由圖3所示,隨著δ的增長(zhǎng),整體效用在逐漸降低,同時(shí)λ越大時(shí),效用下降的速率也越快.這是由于每個(gè)階段的篩選工人的閾值θ不斷下降,導(dǎo)致一些低質(zhì)量高報(bào)價(jià)工人可以被選中,最終總效用下降.可見(jiàn)在線場(chǎng)景中,工人參與度較高的情況下,增加δ會(huì)降低請(qǐng)求者的效用.

圖3 參數(shù)δ對(duì)效用的影響

最后本文將SQOI與階段離線算法和在線隨機(jī)算法進(jìn)行比較.從圖4可以看出,隨著請(qǐng)求者預(yù)算的增加,離線算法由于在分配前事先獲取了所有工人的信息,其表現(xiàn)是最優(yōu)的.而SQOI的曲線始終位于離線算法和隨機(jī)算法之間,且遠(yuǎn)高于后者.所以本文提出的方法比起在線隨機(jī)算法在提高請(qǐng)求者效用上有著顯著的優(yōu)勢(shì).

圖4 不同算法的效用對(duì)比

6 總結(jié)與展望

本文考慮了預(yù)算與時(shí)間約束下的移動(dòng)眾包在線激勵(lì)機(jī)制問(wèn)題,提出了一種多階段質(zhì)量感知的在線激勵(lì)機(jī)制SQOI,通過(guò)增量學(xué)習(xí)的方式將整個(gè)眾包活動(dòng)周期分為多個(gè)階段,每個(gè)階段集成了工人選擇、質(zhì)量評(píng)估和參數(shù)更新模塊.在缺少標(biāo)準(zhǔn)數(shù)據(jù)的情況下,為請(qǐng)求者盡可能地提供高質(zhì)量的傳感數(shù)據(jù).同時(shí),本文證明了SQOI具有預(yù)算可行性,個(gè)體合理性,真實(shí)性和計(jì)算效率.最后通過(guò)實(shí)驗(yàn)進(jìn)一步說(shuō)明該機(jī)制在提升數(shù)據(jù)質(zhì)量上的可行性.

然而,SQOI還存在著以下幾點(diǎn)問(wèn)題.首先,本文考慮的是同質(zhì)任務(wù),即任務(wù)類型相同,且所有任務(wù)由請(qǐng)求者同時(shí)發(fā)布,所以SQOI不適用于異質(zhì)任務(wù)的分配.其次,SQOI在工人低參與度的場(chǎng)景下,由于每個(gè)階段平臺(tái)收集的數(shù)據(jù)較少,會(huì)影響到算法的性能.在未來(lái)的工作中,我們會(huì)根據(jù)這些問(wèn)題,進(jìn)一步完善SQOI的模型和算法.