王 鑫，喬少杰，楊國平，林羽豐，翁越男，吳凌淳，陳 琴，高瑞瑋

(成都信息工程大學(xué) 軟件工程學(xué)院，四川 成都 610225)

0 引言

隨著配備通信裝置和感知設(shè)備智能車輛的迅速演進(jìn)，用戶信息的復(fù)雜化導(dǎo)致資源分配必需的高計算力和高準(zhǔn)確率愈發(fā)得不到保證，移動用戶對匹配服務(wù)質(zhì)量的需求成為亟待解決的問題。而車聯(lián)網(wǎng)(Internet of Vehicles，IoV)技術(shù)旨在加速車輛、用戶、基礎(chǔ)設(shè)施以及云端網(wǎng)絡(luò)之間的信息收集與交換[1]，在物理距離以及網(wǎng)絡(luò)距離上更接近用戶，能夠迅速處理用戶在短時間內(nèi)產(chǎn)生的大規(guī)模數(shù)據(jù)。IoV技術(shù)不僅具有較低的通信成本，還可以通過利用高數(shù)據(jù)傳輸性能保證大批量數(shù)據(jù)被實時處理[2]。

與此同時，一種新型眾包技術(shù)應(yīng)運而生——空間眾包(Spatial Crowdsourcing，SC)。在SC場景下，工人被要求親自前往特定地點，完成指定的時空任務(wù)，獲取相應(yīng)的獎勵報酬[3]。SC平臺中有許多應(yīng)用程序，涉及旅游、情報、災(zāi)害響應(yīng)、新聞跟蹤和城市規(guī)劃等多個領(lǐng)域，同時推進(jìn)了一系列行業(yè)的成功，如視頻拍攝、天氣信息收集、城市噪音水平計算和車流量計算等。目前，眾包平臺的主流任務(wù)模式為以平臺服務(wù)器為中心(Server Assigned Tasks, SAT)的模式。在SAT模式下，眾包平臺不會直接將空間任務(wù)分配給眾包工人，而是需要眾包工人將位置上傳到服務(wù)器，當(dāng)服務(wù)器收集到所有在線眾包工人的位置后，再為眾包工人分配合適的任務(wù)[4]。

在SC的一般場景下，待完成的任務(wù)量往往太大以至于不能在短時間內(nèi)找到足夠的專業(yè)工人，并且這些任務(wù)不能利用計算機代替真人來完成。將IoV技術(shù)集成到眾包平臺的任務(wù)分配中，構(gòu)建一個分布式的SC平臺，是實現(xiàn)高效任務(wù)分配的有效措施，也是SC研究的發(fā)展新方向之一。任務(wù)分配問題被描述為最大系統(tǒng)利用率問題(如任務(wù)完成數(shù)量、任務(wù)完成質(zhì)量和任務(wù)完成時間等)，現(xiàn)有研究主要集中在工人或是任務(wù)的時空可用性上，工人的主觀意愿往往很容易被忽視，很大程度上沒有解決工人主觀意愿與高效任務(wù)分配之間平衡的問題。服務(wù)全球化的激烈競爭導(dǎo)致供應(yīng)鏈?zhǔn)袌鲲柡?，工人成本迅速提升，因此，快速感知工人積極性并實現(xiàn)有效任務(wù)分配是眾包平臺至關(guān)重要的任務(wù)之一，利用IoV技術(shù)輔助SC完成任務(wù)分配是提高系統(tǒng)效率的有效手段。

為了解決上述問題，本文提出了一種利用IoV技術(shù)輔助積極性感知的SC任務(wù)分配框架(Task Allocation Framework in Spatial Crowdsourcing Based on Internet of Vehicles Assisted Positivity Sensing，IOV-SCA)。具體來說，該模型分為2個階段：積極性感知階段和任務(wù)分配階段。積極性感知階段旨在實時感知工人對任務(wù)的積極性，本文使用加入注意力機制的雙向長短期記憶網(wǎng)絡(luò)(Bi-directional Long Short-Term Memory，BiLSTM)捕捉工人的潛在狀態(tài)，計算工人的工作停滯時間，并與給定的時間閾值進(jìn)行比較，以此判斷工人的積極性。任務(wù)分配階段在積極性感知的基礎(chǔ)上，將任務(wù)分配問題轉(zhuǎn)換為加權(quán)二部圖最大匹配問題。本文提出了一種基于積極性感知的SC任務(wù)分配算法，旨在高效地將任務(wù)分配給工人，實現(xiàn)系統(tǒng)效益最大化。

綜上所述，本文的主要貢獻(xiàn)包括：

① 利用IoV技術(shù)輔助實現(xiàn)SC任務(wù)分配問題。

② 利用加入注意力機制的BiLSTM模型感知工人的積極性。

③ 提出了一種基于積極性感知的SC任務(wù)分配算法，實現(xiàn)了系統(tǒng)效益與工人主觀感受之間的權(quán)衡。

④ 在大規(guī)模真實數(shù)據(jù)集上評估了IOV-SCA模型，其效率和有效性均優(yōu)于其他代表性方法。

1 相關(guān)工作

與傳統(tǒng)的任務(wù)分配方法不同，本文所提出的框架需要利用IoV技術(shù)輔助計算眾包工人工作期間的積極性，提升上下文感知性能。本文主要涉及IoV技術(shù)和SC兩個方面，下文中將分別介紹這兩方面的研究現(xiàn)狀。

1.1 IoV

近年來，IoV技術(shù)受到了廣泛關(guān)注，通信傳感是IoV技術(shù)的主要組成部分之一，它需要將每個車輛捕獲的移動資源與其他平臺或終端進(jìn)行數(shù)據(jù)傳輸。高紳等[5]提出了一種多信道模型下C-V2X模式4的通信性能分析模型，該方法通過分析C-V2X模式4對不同傳輸功率、不同編碼方案以及不同信道模型中存在的問題進(jìn)行建模，表明車輛在頻繁傳輸資源時，需要完善的資源分配方案以保證數(shù)據(jù)傳輸?shù)耐ㄐ判阅?。王哲等[6]提出了一種混合交通場景下的軌跡預(yù)測算法，用于規(guī)避手動駕駛車輛可能存在的危險行為，該算法在使用去中心化的無線集群學(xué)習(xí)保護(hù)用戶隱私數(shù)據(jù)的同時，還利用車與車之間的無線通信系統(tǒng)感知附近手動駕駛車輛的歷史軌跡信息并預(yù)測軌跡。張勇[7]提出了一種改進(jìn)的VANET路由協(xié)議，該模型用于提升丟包率的計算速度，提高網(wǎng)絡(luò)傳輸?shù)臏?zhǔn)確率，通過提升網(wǎng)絡(luò)傳輸性能可有效縮短預(yù)警系統(tǒng)發(fā)布警告的時間，從而確保駕駛員及時獲取險情信息，降低交通事故的發(fā)生率。

1.2 SC

隨著移動智能設(shè)備的發(fā)展，SC被廣泛應(yīng)用于智慧城市中提供信息資源，利用人群的潛在能力完成計算機不能完成的任務(wù)。Dutta等[8]研究了SC在環(huán)境傳感方面的應(yīng)用，提出人群可以利用便攜式移動環(huán)境傳感器通過藍(lán)牙將其ID和測量的空氣質(zhì)量數(shù)據(jù)發(fā)送到最近的智能設(shè)備中，接收到的數(shù)據(jù)被處理后會上傳到云服務(wù)器。在云服務(wù)器上，服務(wù)提供商會將數(shù)據(jù)聚合、分析并存儲，按照用戶的要求發(fā)送當(dāng)?shù)乜諝赓|(zhì)量指數(shù)。Cianciulli等[9]研究了SC在公共交通系統(tǒng)中的應(yīng)用，提出了一種基于Beacon3技術(shù)的SC應(yīng)用程序，該程序利用安裝在公交車和公交車站上的藍(lán)牙信標(biāo)發(fā)射器，計算公交車的位置以及到達(dá)不同站臺的大致時間。當(dāng)?shù)卿浽摮绦驎r，用戶的智能設(shè)備會接收到最近公交站點ID并上傳至云服務(wù)器，而公交車會定期上傳位置信息到云服務(wù)器。云服務(wù)器會計算公交車到達(dá)指定站點的時間并通知用戶。Huang等[10]提出了一種及時預(yù)測城市異常情況(如噪音污染、城市基礎(chǔ)設(shè)施故障等)的模型，該算法要求用戶將投訴信息上傳至云服務(wù)器，云服務(wù)器根據(jù)異常數(shù)量以及時間向量通過貝葉斯推理模型對城市區(qū)域進(jìn)行聚類。最后，根據(jù)各區(qū)域的相關(guān)性以及目標(biāo)區(qū)域的異常歷史，利用馬爾科夫模型對每個區(qū)域的異常情況進(jìn)行預(yù)測。

IoV技術(shù)和SC都已經(jīng)取得一些研究成果，但是上述方法都需要用戶上傳數(shù)據(jù)至云服務(wù)器，不滿足實時感知工人積極性的低時延性和及時反饋性，如何將IoV技術(shù)的優(yōu)勢應(yīng)用到SC中的任務(wù)分配問題是需要進(jìn)一步研究的內(nèi)容。本文所提模型的創(chuàng)新性在于利用IoV技術(shù)輔助感知工人的積極性，并且在此基礎(chǔ)上提出基于積極性感知的任務(wù)分配算法。與已有研究相比，本文提出的框架響應(yīng)更為迅速，任務(wù)分配結(jié)果更優(yōu)。

1.3 總體框架

模型總體框架如圖1所示。IOV-SCA模型主要包含3個實體單位：云服務(wù)器、路側(cè)單元及車輛。云服務(wù)器負(fù)責(zé)匯總信息并分配任務(wù)；路側(cè)單元是IoV技術(shù)中的基礎(chǔ)設(shè)施，主要負(fù)責(zé)與車輛通信，并利用快速數(shù)據(jù)處理能力計算工作停滯時間；車輛即表示載有眾包工人的工人車輛，主要利用車載移動智能設(shè)備負(fù)責(zé)工人實時數(shù)據(jù)的收發(fā)。模型分為2個階段：第1階段在路側(cè)單元上搭建基于BiLSTM的積極性感知模型(Positivity Sensing Model Based on BiLSTM，Bi-PSM)，旨在根據(jù)工人的實時感知數(shù)據(jù)以及歷史任務(wù)軌跡數(shù)據(jù)計算工作停滯時間，從而判斷工人的積極性。具體來說，Bi-PSM模型需要將車輛收集到的感知數(shù)據(jù)匯總成工人的隱性狀態(tài)，其中包括任務(wù)的報酬、工人到任務(wù)點所需的時間距離和空間距離、2個相鄰任務(wù)點之間的時間距離和空間距離。將工人的隱性狀態(tài)輸入Bi-PSM模型，計算出工作停滯時間，并給定時間閾值，若工作停滯時間超過閾值，則該工人被認(rèn)定為消極工人；反之，若工作停滯時間低于閾值，則該工人被認(rèn)定為積極工人。

圖1 模型總體框架Fig.1 Framework of the proposed model

第2階段在云服務(wù)器上搭建基于積極性感知的SC任務(wù)分配算法(Task Allocation Algorithm Based on Positivity Sensing，PS-TAA)，旨在實現(xiàn)路側(cè)單元與云服務(wù)器之間的交互，保證工人有高積極性、高參與度和高滿意度的工作狀態(tài)，并在云端合理分配任務(wù)。具體來說，PS-TAA算法優(yōu)先考慮消極工人，為消極工人分配價值更高的任務(wù)，如更高收益的任務(wù)、物理距離更近的任務(wù)和匹配度更高的任務(wù)等。

2 問題表述與模型

2.1 基本概念

定義1SC任務(wù)：由以下五元組的形式進(jìn)行定義，t= ，其中l(wèi)t表示眾包任務(wù)t的地理位置，pt表示眾包任務(wù)t的發(fā)布時間，et表示眾包任務(wù)t的截止時間，rt表示完成眾包任務(wù)t后的獎勵報酬，st表示眾包任務(wù)t的技能要求集合。

定義2SC工人：由以下五元組的形式進(jìn)行定義，w=〈lw,dw,mw,tw,sw〉，其中l(wèi)w表示眾包工人w當(dāng)前的地理位置，dw表示眾包工人w能到達(dá)指定任務(wù)地點的范圍半徑，mw表示眾包工人w在同一時刻內(nèi)能接受的最大任務(wù)數(shù)量，tw表示工人w的工作停滯時間，即表示工人完成第i個任務(wù)到接受第(i+1)個任務(wù)的時間間隙，sw表示眾包工人w具備的技能集合。在本文的工作中，云服務(wù)器首先判斷工人是否符合任務(wù)要求，工人只能匹配符合技能要求的任務(wù)，即st∩sw≠?。當(dāng)云服務(wù)器將任務(wù)分配給工人時，該工人將會被視作脫機狀態(tài)，直到該任務(wù)被完成再重新回到聯(lián)機狀態(tài)，即一名眾包工人在同一時刻內(nèi)最多只能接受一項任務(wù)，因此，在本文的模型中mw設(shè)置為1。

定義3消極工人：給定一個時間閾值δ，當(dāng)tw≥δ時，則認(rèn)定該工人為消極工人。

定義4積極工人：給定一個時間閾值δ，當(dāng)tw<δ時，則認(rèn)定該工人為積極工人。

定義5基于積極性感知的任務(wù)分配問題：在SC平臺下，當(dāng)給定一組SC任務(wù)T以及一組SC工人W時，本文的目標(biāo)是找到一組任務(wù)分配A并且滿足以下目標(biāo)：

① 任務(wù)分配A的效益最大化，形式化表達(dá)為：

② 任務(wù)分配A需要以眾包工人為中心，即lt要在以lw為中心、dw為半徑的區(qū)域內(nèi)。

③ 提升眾包工人工作時的積極性，即最小化工作停滯時間tw，為消極工人分配收益更高的任務(wù)。

2.2 基于BiLSTM的積極性感知模型

Bi-PSM模型為本文提出的積極性感知模型，即采用融合注意力機制的BiLSTM混合神經(jīng)網(wǎng)絡(luò)模型來提取工人的工作停滯時間。Bi-PSM模型包含輸入層、BiLSTM層、注意力機制層、全連接層以及輸出層，模型結(jié)構(gòu)如圖2所示。

圖2 Bi-PSM模型結(jié)構(gòu)Fig.2 Structure of Bi-PSM

2.2.1 輸入層

文獻(xiàn)[11]的研究表明，可以利用時空行為數(shù)據(jù)提取到多角度有價值的信息。根據(jù)這一基本原理，將時空行為數(shù)據(jù)轉(zhuǎn)換為一系列行為特征來表示工人的隱性狀態(tài)，通過這些行為特征來計算工作停滯時間。因此，引入狀態(tài)特征向量作為Bi-PSM模型的輸入：對于工人w，狀態(tài)特征向量表示為(r,lo,la,ds,tb,te,ts)，其中r表示當(dāng)前眾包任務(wù)的獎勵報酬，lo表示當(dāng)前眾包任務(wù)的經(jīng)度，la表示當(dāng)前眾包任務(wù)的緯度，ds表示相鄰任務(wù)之間的物理距離，tb表示當(dāng)前眾包任務(wù)的起始時間，te表示當(dāng)前眾包任務(wù)的截止時間，ts表示相鄰任務(wù)之間的時間距離。Bi-PSM模型是基于BiLSTM的模型，本文將時間步長設(shè)置為30，即輸入實例由30個狀態(tài)特征向量組成。

2.2.2 BiLSTM層

文獻(xiàn)[12]的研究表明，LSTM網(wǎng)絡(luò)執(zhí)行連續(xù)數(shù)據(jù)分類任務(wù)的效果是比較出色的，區(qū)別于其他神經(jīng)網(wǎng)絡(luò)，LSTM網(wǎng)絡(luò)可以保存從歷史輸入中獲取的重要信息。本文將工人的狀態(tài)特征向量視為序列數(shù)據(jù)，即工人的潛在狀態(tài)具備連續(xù)性。因此，利用LSTM單元中3個門來執(zhí)行記憶功能和遺忘功能，可以有效捕捉上下文信息應(yīng)用于潛在狀態(tài)分析。計算過程如下：

① 遺忘門ft負(fù)責(zé)過濾工人的過去周期信息，因為并非工人在執(zhí)行任務(wù)期間所采取的每一項行動都會對其積極性產(chǎn)生影響。通過過濾對積極性感知無用的信息，可以減少操作時間和存儲大小，計算如下：

ft=σ(Wf·[ht-1,xt]+bf) ，

(1)

式中，ft表示遺忘門的內(nèi)容，將狀態(tài)特征向量xt和從上一時刻到t-1時刻篩選得到的狀態(tài)特征向量進(jìn)行串聯(lián)作為t時刻的輸入；Wf表示遺忘門中的權(quán)重矩陣；bf表示遺忘門中的偏置項；σ表示Sigmoid函數(shù)作為激活函數(shù)。

it=σ(Wi·[ht-1,xt]+bi) ，

(2)

(3)

(4)

式中，it表示輸入門的內(nèi)容；Wi和Wc表示輸入門中的權(quán)重矩陣；bi和bc表示輸入門中的偏置項；σ表示Sigmoid函數(shù)作為激活函數(shù)。

③ 輸出門ot負(fù)責(zé)篩選對積極性感知有重要影響的隱性狀態(tài)信息，并在時刻t輸出最終隱性狀態(tài)信息ht，用于后續(xù)的工作停滯時間計算：

ot=σ(Wo·[ht-1,xt]+bo) ,

(5)

ht=ot·tanh(ct) ,

(6)

式中，ot表示輸出門的內(nèi)容；Wo表示輸出門中的權(quán)重矩陣；bo表示輸出門中的偏置項；σ表示Sigmoid函數(shù)作為激活函數(shù)。

(7)

H={h1,h2,…,ht,…,hT} ，

(8)

式中，H表示T時刻隱藏層內(nèi)連接向量的集合作為注意力機制層的輸入?；贚STM的工人隱性狀態(tài)獲取單元結(jié)構(gòu)如圖3所示。

圖3 工人隱性狀態(tài)獲取單元結(jié)構(gòu)Fig.3 Structure of recessive state acquisition unit

2.2.3 注意力機制層

由于特定時間段內(nèi)的特定行為對工人積極性變化產(chǎn)生的影響力不同，因此用注意力機制量化這些行為對積極性感知的影響程度[13]。利用注意力機制，可以為不同的特征分配不同的權(quán)重，從而降低無關(guān)部分的作用，可以提升工人隱性狀態(tài)的提取效率，計算如下：

m=tanh(Wm·H+bm) ，

(9)

a=Softmax(m) ，

(10)

R=H·αT，

(11)

式中，m表示每個隱藏層向量的評分，即其對輸出結(jié)果的影響程度；Wm表示注意力機制層的權(quán)重矩陣；bm表示注意力機制層的偏置項；α表示用Softmax函數(shù)對評分m歸一化得到的權(quán)重系數(shù)；R表示權(quán)重分配完成后注意力機制的輸出結(jié)果。

2.2.4 輸出層

經(jīng)上述操作后，將輸出結(jié)果R通過全連接層，輸出為感知到的工作停滯時間tw：

tw=tanh(Wt·R+bt) ，

(12)

式中，Wt表示輸出層的權(quán)重矩陣；bt表示輸出層的偏置項。此時，給定一個時間閾值δ，當(dāng)tw≥δ時，認(rèn)定工人w為消極工人；反之，當(dāng)tw<δ時，認(rèn)定該工人為積極工人。

2.3 基于積極性感知的SC任務(wù)分配算法

在現(xiàn)實生活中，工人的積極性是動態(tài)變化的，這就要求設(shè)置于云服務(wù)器的眾包平臺作出迅速響應(yīng)，因此，找到SC中任務(wù)分配問題的全局最優(yōu)解是具有挑戰(zhàn)性的。本文將任務(wù)分配問題轉(zhuǎn)化為帶權(quán)二部圖中的最優(yōu)匹配問題，旨在最大化當(dāng)前分配權(quán)值，為消極工人提供更高的優(yōu)先級并為其分配價值更高的任務(wù)。

通過一個動態(tài)場景下SC的任務(wù)分配示例來描述工人積極性和系統(tǒng)效用之間的權(quán)衡，該示例包含6名工人(用數(shù)字編號)和6個任務(wù)(用字母編號)，如圖4所示。圖4(a)表示在約束條件下滿足要求的可能性分配結(jié)果；圖4(b)為對應(yīng)的加權(quán)二部圖；圖4(c)表示側(cè)重工人主觀性的任務(wù)分配，但是這種分配方法導(dǎo)致工人2和任務(wù)a未被分配，因此系統(tǒng)效益被降低；圖4(d)表示側(cè)重系統(tǒng)收益的任務(wù)分配，該方法旨在最大化平臺利益，但可能會產(chǎn)生不合適的匹配結(jié)果，持續(xù)對分配任務(wù)不滿意的工人很大幾率會離開平臺，對平臺造成顯著的不利影響[14]?；诖耍疚奶岢龅腜S-TAA算法旨在實現(xiàn)系統(tǒng)效用最大化的同時盡可能為消極工人提供高權(quán)重的配對。

(a) 約束條件下的分配

(b) 對應(yīng)的加權(quán)二部圖

(c) 側(cè)重主觀性的分配

(d) 側(cè)重收益的分配圖4 動態(tài)場景下SC任務(wù)分配示例Fig.4 Example of spatial crowdsourcing task assignment in dynamic scenarios

定義G=(V,E)表示加權(quán)二部圖，其中V表示頂點的集合，E表示邊的集合。給定一組待命工人W={w1,w2,…,wi}和一組可分配任務(wù)A={a1,a2,…,aj}，基于此，頂點集V為工人頂點子集VW和任務(wù)頂點子集VA的并集，且VW∩VA=；頂點V的數(shù)量為(i+j)，邊的數(shù)量為其中mw表示眾包工人w在同一時刻內(nèi)能接受的最大任務(wù)數(shù)量，與工作停滯時間tw呈正相關(guān)。

為了更好地理解本文所提算法，首先介紹增益路徑查找算法，通過增益路徑查找算法進(jìn)行迭代更新，以獲得具有最大系統(tǒng)效用的分配結(jié)果。其中，迭代過程是在工人與任務(wù)的配對中查找增益路徑P={p1,p2,…,pk}，并且增益路徑p的2個端點不能配對，它的邊和已有配對不重復(fù)。當(dāng)找到(2l+1)條增益路徑p時，意味著當(dāng)前配對得分已經(jīng)到達(dá)最大值，即可作為最終結(jié)果返回。從當(dāng)前未被分配任務(wù)的工人wi開始，如果工人wi可以與未分配的任務(wù)tj直接匹配，則立即得到長度為1的增益路徑pk；否則，尋找下一個未分配的任務(wù)給該工人。對于每個這樣的任務(wù)t，通過擴展當(dāng)前路徑來創(chuàng)建一個新的增益路徑，并遞歸地重復(fù)相同的過程，并且遞歸深度不能超過上限λ。

增益路徑P查找算法的詳細(xì)過程如算法1所示。

算法1:增益路徑P查找算法輸入:加權(quán)二部圖G輸出:增益路徑P1. 初始化系統(tǒng)參數(shù);2. Forwi∈Wdo3. If 工人wi未被分配任務(wù)且任務(wù)tj未分配 then4. 將任務(wù)tj設(shè)置為待分配狀態(tài);5. value ←工人節(jié)點wi權(quán)值-任務(wù)節(jié)點tj權(quán)值;6. Ifvalue == 0 then

7. P ← pk;8. If |P| == 2l+1 then9. End If10. ReturnP;

PS-TAA算法的首要目標(biāo)是根據(jù)感知到的工人積極性進(jìn)行任務(wù)分配。首先，利用Gale-Shapley算法[15]中提出的延遲接受機制，在給定的工人和任務(wù)之間找到一個穩(wěn)定的匹配；然后利用增益路徑查找算法進(jìn)行迭代更新；最后獲得滿足系統(tǒng)效益最大化的分配結(jié)果。PS-TAA算法的詳細(xì)過程如算法2所示，給定由工人頂點集W和任務(wù)頂點集T組成的二部圖，根據(jù)wi的工作停滯時間按降序?qū)γ總€任務(wù)的可用工人進(jìn)行排序，通過增益路徑查找算法遞歸查找有效匹配，按照鄰居節(jié)點的積極性排序順序訪問，將任務(wù)分配給消極工人，降低平臺的損失。

算法2:PS-TAA算法輸入:工人集W,任務(wù)集T輸出:任務(wù)分配結(jié)果S1. 初始化系統(tǒng)參數(shù);2. For each wi∈Wdo3. 計算工作停滯時間tw;4. Iftw≥δdo5. 認(rèn)定該工人為消極工人;6. For each aj∈Ado7. 設(shè)置任務(wù)aj為待支配狀態(tài);8. 查找所有可被任務(wù)aj支配的工人;9. For each available wi∈Wdo10. 調(diào)用增益路徑P查找算法進(jìn)行迭代;11. If 增益路徑P被查找到do12. i=i+1,j=j+1;13. 將pk存儲到當(dāng)前wi的分配結(jié)果中;14. Else15. Break16. End For17. End For18. ReturnS;

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

為了評估IOV-SCA模型的性能，在2組真實數(shù)據(jù)集上進(jìn)行對比實驗，分別為包含193 294名用戶在283 298個地點2 427 149條附帶時間戳的簽到記錄的Gowalla數(shù)據(jù)集以及包含來自428 236名用戶在582 362個地點3 829 629次附帶時間戳的簽到記錄的Foursquare數(shù)據(jù)集。為了使用戶數(shù)據(jù)更具有代表性，將簽到記錄少于10次的用戶進(jìn)行過濾處理，并假設(shè)用戶表示眾包工人，簽到位置表示眾包任務(wù)，則簽到記錄表示接受該任務(wù)。為了避免實驗結(jié)果的偶然性，按照時間順序?qū)?shù)據(jù)集劃分為訓(xùn)練集和測試集，其中，80%的簽到記錄用于訓(xùn)練，其余20%用于測試，經(jīng)處理后的實驗數(shù)據(jù)集規(guī)模如表1所示。

表1 實驗數(shù)據(jù)集描述Tab.1 Description of experimental datasets

本文的實驗環(huán)境如下：操作系統(tǒng)為Windows 10，CPU為AMD Ryzen7 5800H，GPU為NVIDIA GeForce RTX3060，系統(tǒng)內(nèi)存為32 GB DDR4@3 200 Hz，Python版本3.6.8，深度學(xué)習(xí)框架使用PyTorch，模型運算在CUDA上進(jìn)行。

本文使用2個指標(biāo)來評估IOV-SCA模型的有效性以及效率：① 總體質(zhì)量分?jǐn)?shù)，用于衡量分配策略的整體質(zhì)量；② 分配消耗的CPU時間，指標(biāo)通過Python記錄的分配算法開始前后時間求差值計算得到。

3.2 基準(zhǔn)方法

為了說明IOV-SCA模型的性能，引入以下基線方法進(jìn)行比較：

① Greedy-SAT模型[16]將任務(wù)根據(jù)價值從高到低排序，每個任務(wù)在可用工人集中選擇距離最近的工人進(jìn)行分配。

② Random-SAT模型[17]隨機從任務(wù)集中選擇一個任務(wù)，并分配給可用工人集中隨機一名工人。

③ D&C-SAT模型[18]基于分治法的任務(wù)分配模型，該模型將一個可用任務(wù)集分割成一系列規(guī)模較小的任務(wù)集，然后分配給距離最近的工人。

3.3 結(jié)果分析

圖5比較了任務(wù)規(guī)模變化下IOV-SCA模型和其他基準(zhǔn)方法的總體質(zhì)量分?jǐn)?shù)差別，其中任務(wù)規(guī)模由1 000增加到6 000。由圖5可以看出，隨著任務(wù)規(guī)模的擴大，4種模型的總體質(zhì)量分?jǐn)?shù)都在提升，本文所提IOV-SCA模型在任務(wù)規(guī)模變化時優(yōu)于其他算法，這是因為IOV-SCA模型考慮了工人的積極性，在有限的任務(wù)內(nèi)尋求最優(yōu)匹配以減少消極怠工的工人并提升總體效益。Greedy-SAT模型總體質(zhì)量分?jǐn)?shù)提升幅度較小，這是因為貪心算法注重局部最優(yōu)，迭代次數(shù)較少，導(dǎo)致其性能低于D&C-SAT模型。D&C-SAT模型的總體質(zhì)量分?jǐn)?shù)較高，這是因為該模型通過分治法在不同區(qū)域內(nèi)尋找到質(zhì)量較高的匹配，但其性能低于本文所提IOV-SCA模型，是因為IOV-SCA模型內(nèi)的工人頂點被賦予積極性特征，即工人頂點與其他任務(wù)頂點匹配的方式更多，從而提升了系統(tǒng)的整體效益。

(a) Gowalla數(shù)據(jù)集

(b) Foursquare數(shù)據(jù)集圖5 不同任務(wù)規(guī)模下總體質(zhì)量分?jǐn)?shù)Fig.5 Overall quality score under different task scales

圖6比較了任務(wù)規(guī)模變化下IOV-SCA模型和其他基準(zhǔn)方法的CPU消耗時間的差別，其中任務(wù)規(guī)模由1 000增加到6 000。由圖6可以看出，隨著任務(wù)規(guī)模的擴大，Greedy-SAT模型和D&C-SAT模型的CPU消耗時間的增長趨勢相對穩(wěn)定，而IOV-SCA模型的CPU消耗時間增長相對明顯，這是因為當(dāng)工人數(shù)量確定時，任務(wù)規(guī)模的擴大會導(dǎo)致工人內(nèi)部競爭的擴大，從而可能會有較多不合適的匹配對產(chǎn)生，造成部分工人的積極性降低，增加了算法的迭代程度。而Gowalla數(shù)據(jù)集和Foursquare數(shù)據(jù)集的主要差別在于數(shù)據(jù)集的規(guī)模上，對于規(guī)模較大的Foursquare數(shù)據(jù)集，所有任務(wù)分配模型消耗的CPU時間都會增長，IOV-SCA模型的增長趨勢更為明顯。舉例來說，當(dāng)IOV-SCA模型檢測到工人甲為消極工人時，此時模型試圖給工人甲分配任務(wù)，而當(dāng)前任務(wù)已經(jīng)被分配給工人乙，則模型會尋找下一個任務(wù)，這種情況增加了模型迭代次數(shù)，從而導(dǎo)致CPU消耗時間的增加。Random-SAT模型的分配時間是最快的，這是因為該模型隨機選擇任務(wù)和工人進(jìn)行匹配，沒有考慮最大化質(zhì)量分?jǐn)?shù)。

(a) Gowalla數(shù)據(jù)集

(b) Foursquare數(shù)據(jù)集圖6 不同任務(wù)規(guī)模下CPU消耗時間Fig.6 CPU consumption time under different task scales

圖7比較了工人規(guī)模變化下IOV-SCA模型和其他基準(zhǔn)方法的總體質(zhì)量分?jǐn)?shù)差距，其中工人規(guī)模由1 000增加到6 000。由圖7可以看出，隨著工人規(guī)模的擴大，所有模型的總體質(zhì)量分?jǐn)?shù)都穩(wěn)定增加，這是因為在任務(wù)數(shù)量確定的情況下，工人數(shù)量越多，工人與任務(wù)的匹配對也越多，與之對應(yīng)的總體質(zhì)量分?jǐn)?shù)也會提高。在數(shù)據(jù)集規(guī)模較大的Foursquare數(shù)據(jù)集上，所有模型的質(zhì)量分?jǐn)?shù)都要高于Gowalla數(shù)據(jù)集的結(jié)果，這是因為工人數(shù)量增加導(dǎo)致可用分配的增加，從而二部圖中任務(wù)頂點所對應(yīng)的邊也會增多，因此總體質(zhì)量分?jǐn)?shù)會有明顯的區(qū)別。IOV-SCA模型較D&C-SAT模型總體提升約5.6%，較Random-SAT模型約提升10.2%，較Greedy-SAT模型約提升18.6%。

(a) Gowalla數(shù)據(jù)集

(b) Foursquare數(shù)據(jù)集圖7 不同工人規(guī)模下總體質(zhì)量分?jǐn)?shù)Fig.7 Overall quality score under different worker scales

圖8比較了工人規(guī)模變化下IOV-SCA模型和其他基準(zhǔn)方法CPU消耗時間的差別，其中工人規(guī)模由1 000增加到6 000。由圖8可以看出，由于工人選擇范圍更廣泛，導(dǎo)致獲得更高質(zhì)量分?jǐn)?shù)的同時也會增加CPU的處理時間。與之前的結(jié)果類似，Greedy-SAT模型和Random-SAT模型所需要的時間開銷更少，同樣是因為這2種算法只能保證獲得局部最優(yōu)，并沒有考慮平臺效益的最大化。雖然IOV-SCA模型的CPU消耗時間高于D&C-SAT模型，但是其總體性能在任何變化下都有更優(yōu)的表現(xiàn)。另外，當(dāng)工人的數(shù)量增加時，工人內(nèi)部的競爭會變激烈，從而增加消極工人出現(xiàn)的可能性，因此IOV-SCA模型在分配任務(wù)時需要多次迭代，增加了CPU消耗時間。

(a) Gowalla數(shù)據(jù)集

(b) Foursquare數(shù)據(jù)集圖8 不同工人規(guī)模下CPU消耗時間Fig.8 CPU consumption time under different worker scales

4 結(jié)束語

本文提出了一種IoV輔助積極性感知的SC任務(wù)分配框架，并且按照功能分為2個階段：第1階段在路側(cè)單元上搭建Bi-PSM積極性感知模型，而Bi-PSM模型旨在根據(jù)工人的歷史任務(wù)軌跡數(shù)據(jù)計算工作停滯時間，從而判斷工人的積極性；第2階段在云服務(wù)器上搭建PS-TAA算法，實現(xiàn)了路側(cè)單元與云服務(wù)器之間的交互，在云端為工人合理分配任務(wù)，確保平臺效益最大化。本文在真實數(shù)據(jù)集上評估了不同模型的性能，實驗結(jié)果表明，IOV-SCA模型的總體質(zhì)量分?jǐn)?shù)均優(yōu)于其他基準(zhǔn)方法。未來將進(jìn)一步利用IoV技術(shù)，通過車車交互的方式感知工人的積極性，并且將消極工人的應(yīng)付式行為納入考慮，進(jìn)一步改進(jìn)任務(wù)分配算法，以提高平臺的整體效益。