蘇 華, 吳倩倩

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300387)

隨著移動(dòng)設(shè)備的不斷發(fā)展，移動(dòng)群智感知網(wǎng)絡(luò)也越來(lái)越受到重視.移動(dòng)群智感知網(wǎng)絡(luò)是一種新的模式，它利用無(wú)處不在的智能手機(jī)來(lái)感知、收集和分析數(shù)據(jù)，規(guī)模超出了以往[1].移動(dòng)群智感知網(wǎng)絡(luò)不同于傳統(tǒng)的商業(yè)眾包系統(tǒng).任務(wù)發(fā)布者將任務(wù)提交給移動(dòng)群智感知網(wǎng)絡(luò)平臺(tái)，并告知平臺(tái)完成任務(wù)的報(bào)酬，用戶攜帶智能設(shè)備執(zhí)行任務(wù).任務(wù)發(fā)布者需要確定用戶提供的數(shù)據(jù)是否真實(shí)有效[2].

移動(dòng)設(shè)備，例如手機(jī)、智能手環(huán)等設(shè)備，這些智能設(shè)備內(nèi)置各種傳感器，如溫度計(jì)、麥克風(fēng)和相機(jī)等，不同的傳感器具有不同的功能.因此人們可以通過(guò)移動(dòng)設(shè)備對(duì)數(shù)據(jù)進(jìn)行收集和感知，不需要重新安裝收集數(shù)據(jù)的軟件或工具.移動(dòng)群智感知網(wǎng)絡(luò)已經(jīng)在許多領(lǐng)域得到了成功的應(yīng)用[3].例如，它可以記錄個(gè)體的身體指標(biāo)，進(jìn)行醫(yī)療保健[4]，還可以檢測(cè)環(huán)境，例如噪音污染[5]，道路交通狀況[6]，停車(chē)系統(tǒng)[7]和犯罪情況[8].主要流程是個(gè)人或團(tuán)體將所需的任務(wù)描述信息發(fā)送到移動(dòng)群智感知網(wǎng)絡(luò)服務(wù)器.在這里，希望獲得數(shù)據(jù)的個(gè)人或團(tuán)體稱為任務(wù)發(fā)布者，服務(wù)器稱為平臺(tái).平臺(tái)從任務(wù)發(fā)布者獲得一個(gè)任務(wù)，然后將任務(wù)分解成若干個(gè)子任務(wù).同時(shí)，平臺(tái)選擇部分?jǐn)y帶移動(dòng)智能設(shè)備的用戶進(jìn)行數(shù)據(jù)采集.用戶定期將收集到的數(shù)據(jù)反饋給平臺(tái)，平臺(tái)整理收集到的數(shù)據(jù)并將其返回給任務(wù)發(fā)布者.平臺(tái)獲得獎(jiǎng)勵(lì)，并向用戶支付一定數(shù)額的報(bào)酬.

移動(dòng)群智感知網(wǎng)絡(luò)可以方便快捷地采集數(shù)據(jù)，節(jié)省人力、時(shí)間，給生活帶來(lái)極大的方便，但也面臨著一些問(wèn)題.很多問(wèn)題導(dǎo)致用戶的積極性不高，沒(méi)有足夠的用戶參與到任務(wù)中，有時(shí)用戶提供的數(shù)據(jù)質(zhì)量很差，導(dǎo)致任務(wù)無(wú)法進(jìn)行.

因此，如何選擇合適的用戶是當(dāng)前移動(dòng)群智感知網(wǎng)絡(luò)中最重要的問(wèn)題.用戶的參與是移動(dòng)群智感知網(wǎng)絡(luò)的基礎(chǔ).用戶提供良好的數(shù)據(jù)是移動(dòng)群智感知網(wǎng)絡(luò)正常運(yùn)行的保障.

1 相關(guān)工作

Peng[9]等人提出了一種激勵(lì)機(jī)制來(lái)解決感知數(shù)據(jù)質(zhì)量不均勻的問(wèn)題.他們將數(shù)據(jù)質(zhì)量納入移動(dòng)群智感知網(wǎng)絡(luò)激勵(lì)機(jī)制的設(shè)計(jì)中.為了激勵(lì)用戶有效地感知數(shù)據(jù)，提出了根據(jù)用戶的表現(xiàn)來(lái)獎(jiǎng)勵(lì)用戶.Wang等人[10]通過(guò)改進(jìn)兩階段拍賣(mài)算法，考慮根據(jù)歷史信譽(yù)來(lái)選擇參與者，提出了TATP算法，證明其想法的可行性.L·Jaimes[11]等人提出了一種基于反向拍賣(mài)的激勵(lì)機(jī)制，允許工人對(duì)任務(wù)進(jìn)行投標(biāo)，從而在提高質(zhì)量的同時(shí)節(jié)約成本.這些機(jī)制只考慮了用戶的信譽(yù)，如果用戶失信，將永遠(yuǎn)被拒絕.

Wang等人[12]提出了保證覆蓋的參與者選擇.該方法在保證任務(wù)覆蓋率的前提下，預(yù)測(cè)用戶移動(dòng)軌跡，通過(guò)預(yù)測(cè)結(jié)果將任務(wù)分配給用戶，從而得到任務(wù)分配的最優(yōu)解.然而，隨著任務(wù)數(shù)量的增加，感知數(shù)據(jù)的質(zhì)量無(wú)法得到保證.Yang[13]等人提出了一種新的信用價(jià)值計(jì)算方法.該方法不同于以往的信用價(jià)值計(jì)算方法.考慮了直接信譽(yù)和間接信譽(yù).直接信譽(yù)是平臺(tái)對(duì)用戶歷史行為的衡量，間接信譽(yù)是其他用戶對(duì)用戶的評(píng)價(jià).根據(jù)計(jì)算出的信譽(yù)值，將用戶分為幾個(gè)等級(jí):高度信任、值得信任和不值得信任.平臺(tái)選擇適當(dāng)級(jí)別的參與者參與任務(wù).Zhang[14]等人提出了一個(gè)Crowdemployer系統(tǒng)，該系統(tǒng)滿足了最小覆蓋條件，同時(shí)最小化支付給參與者的金額.招募參與者時(shí)，獲取每個(gè)用戶的歷史信息，預(yù)測(cè)用戶的運(yùn)動(dòng)軌跡和運(yùn)動(dòng)限制區(qū)域.Zhang[15]等人添加了一個(gè)Fog計(jì)算框架，根據(jù)參與者的位置、社交行為和設(shè)備的電池壽命來(lái)作為評(píng)估是否選擇他們的因素.他們考慮了用戶的參與意愿，但忽略了數(shù)據(jù)的可信度.

目前的工作是根據(jù)質(zhì)量和覆蓋面以及節(jié)省預(yù)算來(lái)選擇參與者，其中一些是根據(jù)用戶歷史信息更新的，這需要長(zhǎng)期的溝通.并且僅通過(guò)信譽(yù)值屬性來(lái)選擇參與者，一旦信譽(yù)值不符合條件，就會(huì)被拒絕，從而減少參與者的數(shù)量.因此，提出了一種信譽(yù)值與用戶偏好相結(jié)合的方法.信譽(yù)值根據(jù)歷史信息進(jìn)行更新，用戶偏好是用戶自身的興趣特征.

2 系統(tǒng)模型

任務(wù)發(fā)布者向平臺(tái)發(fā)布任務(wù)，并承諾給予一定報(bào)酬.用集合R表示任務(wù)集，R={R1,R2,R3,…,Rn}.用集合U表示用戶集，U={U1,U2,U3,…,UN}.對(duì)于任務(wù)Rj，平臺(tái)根據(jù)歷史感知任務(wù)經(jīng)驗(yàn)確定任務(wù)預(yù)算Bj，若用戶Ui想?yún)⑴c感知任務(wù)Rj，將對(duì)該任務(wù)投標(biāo)Bi,j，將投標(biāo)報(bào)價(jià)發(fā)送到平臺(tái).平臺(tái)從投標(biāo)用戶中選擇合適的用戶參與任務(wù).用戶Ui完成感知任務(wù)的時(shí)間為感知時(shí)間ti,j，用戶Ui對(duì)平臺(tái)的貢獻(xiàn)值為Vi,j.收集數(shù)據(jù)會(huì)消耗精力、流量等成本，即用戶花費(fèi)為Ci,j，用戶花費(fèi)與感知時(shí)間和單位時(shí)間內(nèi)感知任務(wù)的花費(fèi)有關(guān).

Ci,j=τ*ti,j

(1)

其中:τ是單位時(shí)間內(nèi)感知任務(wù)的花費(fèi).平臺(tái)對(duì)完成任務(wù)的用戶支付報(bào)酬P(guān)i,j，用戶的報(bào)酬受到總?cè)蝿?wù)預(yù)算和個(gè)人感知時(shí)間的影響.

(2)

其中:Tj是被選中的用戶完成感知任務(wù)的總時(shí)間.用戶獲得的利潤(rùn)為Ei,j.

(3)

完成感知任務(wù)后平臺(tái)獲得的報(bào)酬為Ej

(4)

其中:Wj是被選中的參與感知任務(wù)的用戶集，且Wj?U.

感知任務(wù)的數(shù)據(jù)質(zhì)量受到用戶偏好與用戶信譽(yù)值共同的影響，在其他文獻(xiàn)中，沒(méi)有考慮用戶偏好這一因素.如果用戶對(duì)將要感知的數(shù)據(jù)感興趣，他可能更愿意參與感知任務(wù)，用戶對(duì)任務(wù)的偏好程度會(huì)影響平臺(tái)對(duì)用戶的選擇.因此，使用用戶對(duì)任務(wù)的感興趣概率衡量用戶偏好.

集合X(Rj)表示任務(wù)Rj屬性，假設(shè)任務(wù)Rj有K個(gè)屬性，用X(Rj)={A,B,C,…,K}表示.X(Ui)表示用戶偏好的屬性，假設(shè)有k個(gè)，X(Ui)={a,b,c,…,k}.因此，通過(guò)計(jì)算兩者之間的相似比得到用戶Ui對(duì)任務(wù)Rj的感興趣概率.見(jiàn)圖1.

圖1 參與者感興趣的概率

感興趣概率為：

(5)

平臺(tái)為每個(gè)任務(wù)設(shè)置了感興趣閾值Pin，即用戶對(duì)任務(wù)感興趣的概率大于興趣閾值，用戶被選中的可能性越大，反之亦然.用戶興趣得分為INCi.

INCi=

(6)

用戶Ui參與任務(wù)Rj，其信譽(yù)值為T(mén)Ri,j，根據(jù)歷史感知信息更新當(dāng)前信用值，其公式如下:

(7)

TRi,m是用戶Ui參與任務(wù)Rm時(shí)的信譽(yù)值，假設(shè)用戶在參與Rj任務(wù)之前參與了j個(gè)任務(wù)，每個(gè)任務(wù)都有相應(yīng)的信譽(yù)值.距離當(dāng)前任務(wù)感知時(shí)間不同對(duì)當(dāng)前任務(wù)的信譽(yù)值有不同程度的影響，βm是時(shí)間衰減系數(shù)，表示歷史信息對(duì)當(dāng)前信譽(yù)值的影響是逐漸減弱的.時(shí)間衰減系數(shù)定義為：

(8)

TRj是平臺(tái)為任務(wù)指定的信譽(yù)閾值，這是用戶需要滿足的信用要求.如果用戶的信用低于閾值，則參與者之前提供的數(shù)據(jù)可能不準(zhǔn)確，導(dǎo)致質(zhì)量下降.用戶被選中的概率低.用戶的信用評(píng)分為T(mén)RCi

(9)

平臺(tái)計(jì)算興趣分?jǐn)?shù)和信用分?jǐn)?shù)后，計(jì)算用戶的選擇分?jǐn)?shù)SCi.

(10)

最后，平臺(tái)根據(jù)給定的分?jǐn)?shù)閾值SC選擇合適的用戶參與任務(wù).

3 算法設(shè)計(jì)

移動(dòng)群智感知網(wǎng)絡(luò)中，每個(gè)用戶都有自己的特定的信譽(yù)值,感興趣事件的特性.選擇一組用戶,讓用戶的投標(biāo)報(bào)價(jià)小于平臺(tái)給定的預(yù)算,并選擇高信譽(yù)值和高興趣值的用戶.請(qǐng)求參與任務(wù)的每個(gè)用戶,其信譽(yù)值是確定的,而相同信譽(yù)值的用戶,根據(jù)感興趣概率, 感興趣概率越高,其信譽(yù)越高.

因此，UTSA算法如算法1所示.

算法1 update two-stage

auction of participant

selection(UTSA)

Input:

set of usersU,

set of tasksR,

budgetB,

Score thresholdSC

Output:

The winner setWj

i?1；Wj?φ；Pj?0；

The first stage

fori

Pin(Ui,Rj)?calculate the interest percentage

INCi?calculate the interest score

TRCi?calculate the trust score

SCi?calculate the select score

ifSCi≥SCthen

Wj?Wj∪{i}

Pi,j?calculate the reward

Pj?Pj+Pi,j

B?B-Pi,j

end if

end for

The second stage

fori

Pin(Ui,Rj)?calculate the interest percentage

INCi?calculate the interest score

TRCi?calculate the trust score

SCi?calculate the select score

Pi,j?calculate the reward of user i

ifSCi≥SC；Pj+Pi,j≤Bthen

Wj?Wj∪(i)

end if

end for

在算法1中，在第一階段，給定一部分預(yù)算B′，部分預(yù)算的計(jì)算方法參考文獻(xiàn)[9]

(11)

第一階段是確定參與者的投標(biāo)價(jià)格是否小于部分預(yù)算B′.若滿足，則計(jì)算參與者的興趣概率，興趣得分.根據(jù)歷史信息來(lái)更新參與者的信譽(yù)值，計(jì)算參與者的信譽(yù)得分，最終得到參與者的選擇得分.當(dāng)選擇得分大于給定的閾值時(shí)用戶被選中的.循環(huán)執(zhí)行，直到部分預(yù)算耗盡.

第二階段，首先，第一階段支付給參與者的總金額是第二階段的啟動(dòng)預(yù)算，根據(jù)選擇分?jǐn)?shù)選擇合適的參與者.被選中的參與者將加入獲勝者集合.最終被選中的用戶是兩個(gè)階段被選擇的并集.

在原始的TATP算法[9]中，TATP是一種改進(jìn)的基于信任和隱私敏感性的兩階段拍賣(mài)算法.TATP算法考慮了用戶的歷史聲譽(yù)，采用兩階段拍賣(mài)算法，設(shè)定用戶的信用值、執(zhí)行任務(wù)的時(shí)間、隱私，只有滿足條件的用戶才會(huì)被選中.但是，算法只考慮信用值來(lái)提高用戶提供的數(shù)據(jù)的質(zhì)量，一旦用戶一次不可信，將永遠(yuǎn)被拒絕.UTSA算法增加了用戶信譽(yù)值評(píng)分的原則.同時(shí)，通過(guò)比較參與者的興趣特征與任務(wù)特征，形成用戶的興趣得分，作為用戶偏好，并將兩者結(jié)合，最終得到用戶的選擇得分.

4 實(shí)驗(yàn)設(shè)計(jì)

在提出一個(gè)有質(zhì)量保證的解決方案之后，檢查其在真實(shí)環(huán)境中的性能.針對(duì)任務(wù)分配問(wèn)題，提出了基于兩階段拍賣(mài)算法的UTSA(Update Two-stage Auction)算法，考慮了用戶的偏好、信譽(yù)值等因素.為了證明算法的有效性，比較了其與TATP算法在一系列感知任務(wù)中的性能.

4.1 參數(shù)設(shè)置

為了在實(shí)際環(huán)境中測(cè)試所提出的方法，設(shè)置了一些參數(shù).對(duì)于每個(gè)用戶，都有一些固定的參數(shù)，即用戶的信用值，用戶的興趣屬性.

在Python實(shí)驗(yàn)環(huán)境中模擬個(gè)用戶.在每次實(shí)驗(yàn)之前，在[40，100]隨機(jī)選擇用戶的信譽(yù)值，各用戶興趣特征與任務(wù)特征的匹配程度服從均勻分布，通過(guò)改變參數(shù)設(shè)置，得到了不同的實(shí)驗(yàn)結(jié)果.

為了量化提出的用戶偏好，研究了幾種不同類型的任務(wù)特征.如圖2所示，行表示不同類型的事件，列表示不同的屬性.行和列的交集指示此類型的任務(wù)是否具有此屬性.事件的屬性由0和1表示.0表示此類型的任務(wù)不具有此屬性，1表示具有此屬性的任務(wù).例如，交通事故需要使用距離傳感器，光傳感器、環(huán)境溫度傳感器、相機(jī)、壓力傳感器等特征.

對(duì)于每個(gè)用戶，都有感興趣的任務(wù)類型.對(duì)用戶偏好的類型進(jìn)行了量化.選擇了若干用戶和若干類型來(lái)代表用戶偏好.如圖3所示，例如，用戶1對(duì)具有溫度傳感器、光傳感器、距離傳感器、GPS等類型的事件感興趣.該用戶對(duì)雪災(zāi)事故任務(wù)感興趣的概率0.375.用戶5參與雪災(zāi)事故的概率為0.286.對(duì)于相同的任務(wù)，需要計(jì)算每個(gè)用戶感興趣的概率.

圖3 參與者的偏好類型

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

對(duì)于TATP算法和提出的UTSA算法，當(dāng)平臺(tái)的給定預(yù)算為50時(shí)，剩余預(yù)算隨時(shí)間的變化如圖4所示.

圖4 預(yù)算為50時(shí)，剩余預(yù)算隨時(shí)間的示意圖

在其他條件相同的情況下，當(dāng)總預(yù)算為100時(shí)，剩余預(yù)算隨時(shí)間變化如圖5所示.

圖5 預(yù)算為100時(shí)，剩余預(yù)算隨時(shí)間的示意圖

如圖4、5所示，x軸表示時(shí)間，y軸表示預(yù)算.通過(guò)對(duì)比實(shí)驗(yàn)可以看出，雖然UTSA算法和TATP算法在前期的預(yù)算相差不大.然而，隨著時(shí)間的推移，UTSA算法選擇的參與者在同一時(shí)間點(diǎn)上消耗的預(yù)算明顯少于TATP算法.當(dāng)TATP算法的預(yù)算用完后，UTSA算法仍然為后續(xù)的任務(wù)留有大量的預(yù)算.這是因?yàn)閁TSA算法是基于兩個(gè)因素來(lái)選擇參與者，而TATP算法只考慮了信譽(yù)值，一旦參與者的信譽(yù)值不符合條件，就會(huì)被設(shè)置為不值得信任，永遠(yuǎn)被拒絕.在完成相同數(shù)量任務(wù)的情況下，UTSA算法不僅保證了質(zhì)量，而且節(jié)省了預(yù)算.

進(jìn)一步比較了兩種算法完成的任務(wù)數(shù)，實(shí)驗(yàn)結(jié)果如圖6所示.

圖6 完成相同任務(wù)消耗預(yù)算示意圖

x軸表示完成的任務(wù)數(shù)量，y軸表示預(yù)算.從實(shí)驗(yàn)結(jié)果可以看出，對(duì)于相同數(shù)量的任務(wù)，TATP算法比UTSA算法消耗了更大的預(yù)算.在開(kāi)始階段，兩種算法消耗相同的預(yù)算來(lái)完成相同數(shù)量的任務(wù).隨著時(shí)間的推移，TATP算法需要消耗更多的預(yù)算來(lái)完成相同數(shù)量的任務(wù).對(duì)于相同的預(yù)算，TATP算法只能完成少量的任務(wù)，即在預(yù)算耗盡之前只能完成部分任務(wù).UTSA算法有足夠的預(yù)算來(lái)執(zhí)行剩余任務(wù).因此，UTSA算法可以在保證質(zhì)量的同時(shí)，選擇合適的參與者以相同的預(yù)算完成更多的任務(wù).

5 結(jié) 語(yǔ)

本文通過(guò)分析現(xiàn)有移動(dòng)群智感知網(wǎng)絡(luò)中參與者選擇方法的不足，提出了一種基于用戶偏好的參與者選擇方法.將參與者的個(gè)人偏好與任務(wù)的特征相結(jié)合，設(shè)置用戶偏好屬性.同時(shí)結(jié)合可信度模型，使平臺(tái)在選擇參與者時(shí)綜合考慮兩個(gè)因素.本文目標(biāo)是在選擇參與者時(shí)，讓盡可能多的用戶參與到他們感興趣的事件中來(lái).在Python的實(shí)驗(yàn)環(huán)境中，將TATP算法與UTSA算法進(jìn)行比較，通過(guò)修改參數(shù)設(shè)置，證明了算法的可行性.與現(xiàn)有的參與者選擇機(jī)制相比，該機(jī)制確保了數(shù)據(jù)質(zhì)量和節(jié)省預(yù)算.