基于城市軌道交通的群智感知任務(wù)分發(fā)方法

蔣偉進(jìn) 呂斯健 劉躍華 陳君鵬 張婉清

①(湖南工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院 長(zhǎng)沙 410205)

②(湖南工商大學(xué)大數(shù)據(jù)與互聯(lián)網(wǎng)創(chuàng)新研究院 長(zhǎng)沙 410205)

1 引言

任務(wù)分配作為移動(dòng)群智感知中的關(guān)鍵環(huán)節(jié)之一，分配的合理性將成為任務(wù)完成質(zhì)量和代價(jià)的決定因素之一。為了降低任務(wù)分發(fā)對(duì)移動(dòng)數(shù)據(jù)網(wǎng)絡(luò)的依賴，以降低用戶參與者在接收任務(wù)時(shí)的流量費(fèi)用代價(jià)[1]，以及降低基礎(chǔ)移動(dòng)網(wǎng)絡(luò)質(zhì)量對(duì)系統(tǒng)任務(wù)分發(fā)的影響。許多研究者都會(huì)將弱網(wǎng)絡(luò)傳輸?shù)臋C(jī)會(huì)網(wǎng)絡(luò)(opportunistic networks)[2]引入任務(wù)分發(fā)模型中，即利用參與者在隨機(jī)移動(dòng)過(guò)程中的機(jī)會(huì)接觸，通過(guò)弱連接進(jìn)行任務(wù)分發(fā)以及數(shù)據(jù)的傳輸，例如藍(lán)牙、Wi-Fi局域網(wǎng)等。但是考慮到當(dāng)前感知任務(wù)類型的多樣性，任務(wù)信息內(nèi)容通常含有視頻、音頻等資料。傳統(tǒng)機(jī)會(huì)網(wǎng)絡(luò)傳輸?shù)碾S機(jī)不可靠性以及較低的傳輸速率，通常無(wú)法較好地滿足復(fù)雜任務(wù)的分發(fā)質(zhì)量需求。首先在現(xiàn)有的大多數(shù)研究中，大都是在忽略所傳輸?shù)娜蝿?wù)信息大小的前提下進(jìn)行的，沒(méi)有也無(wú)法對(duì)節(jié)點(diǎn)之間的接觸時(shí)間、距離進(jìn)行考慮和衡量。然而隨著技術(shù)的發(fā)展，圖片、視頻等媒體信息早已融入人們的互聯(lián)網(wǎng)生活，任務(wù)信息中同樣如此。在現(xiàn)有技術(shù)中機(jī)會(huì)網(wǎng)絡(luò)進(jìn)行短距離接觸傳輸時(shí)大多通過(guò)藍(lán)牙等低功耗低速率傳輸手段，當(dāng)面對(duì)傳輸視頻、圖片等較大數(shù)據(jù)時(shí)需要保持較長(zhǎng)的接觸時(shí)間才能保證傳輸質(zhì)量。然而在實(shí)際情況中，機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的接觸時(shí)間是難以估計(jì)的。即使部分研究已經(jīng)開(kāi)始將其作為必要條件之一，但是依然沒(méi)有提出較好的估計(jì)算法。

在任務(wù)分發(fā)過(guò)程中參與者[3]的選擇同樣也是移動(dòng)群智感知的核心問(wèn)題之一，參與者的選擇對(duì)任務(wù)分發(fā)的效率、數(shù)據(jù)收集的質(zhì)量、感知數(shù)據(jù)的全面性都有著關(guān)鍵性的影響。在當(dāng)前的研究中，也有許多學(xué)者對(duì)這一問(wèn)題進(jìn)行了深入的研究。如Ca等人研究了在參與者人數(shù)固定的情況下，如何最大化群智感知面積。但是目前大多數(shù)的研究依然都只是基于單個(gè)群智感知任務(wù)進(jìn)行協(xié)同分配，而在實(shí)際情況中，通常會(huì)在同一時(shí)間段內(nèi)出現(xiàn)大量相近的群智任務(wù)需要完成處理[4]。首先大多移動(dòng)群智任務(wù)之間會(huì)具有一定的相似性，如時(shí)間或空間上可一同完成；其次單個(gè)用戶同時(shí)完成多個(gè)感知任務(wù)也可大大提高用戶在完成任務(wù)時(shí)的主觀能動(dòng)性[5]，比傳統(tǒng)的任務(wù)激勵(lì)方式效果更好；并且為用戶分配地理位置較為相近的一組任務(wù)，也是一種群智協(xié)同資源利用效率的提高。

在這一問(wèn)題中，參與者人數(shù)、移動(dòng)距離等都是多任務(wù)[6]分發(fā)算法需要優(yōu)化的目標(biāo)。但是在現(xiàn)有的研究中，大多數(shù)都是針對(duì)單個(gè)目標(biāo)進(jìn)行優(yōu)化分析的，然而在大多數(shù)情況下同時(shí)考慮多個(gè)影響因素進(jìn)行參與者的選擇可以實(shí)現(xiàn)更好的任務(wù)分發(fā)。

為此，本文充分利用了地鐵交通市區(qū)覆蓋面廣、人口流動(dòng)性大、用戶節(jié)點(diǎn)接觸時(shí)間穩(wěn)定且可控可預(yù)測(cè)[7]等優(yōu)勢(shì)，通過(guò)地鐵軌道交通這種現(xiàn)成的基礎(chǔ)設(shè)施實(shí)現(xiàn)了移動(dòng)群智感知任務(wù)的分發(fā)。在感知任務(wù)分發(fā)過(guò)程中，先在系統(tǒng)中對(duì)數(shù)據(jù)需求者給出的同類任務(wù)進(jìn)行密度聚類(density-based methods)。然后根據(jù)各聚類中心與現(xiàn)有地鐵站點(diǎn)的距離，為每個(gè)子任務(wù)區(qū)域分配[8]所屬的地鐵站點(diǎn)，達(dá)到使用城市地鐵軌道交通實(shí)現(xiàn)對(duì)感知任務(wù)區(qū)域就近覆蓋的目的。然后，通過(guò)多任務(wù)動(dòng)態(tài)分發(fā)方法實(shí)現(xiàn)感知任務(wù)子區(qū)域內(nèi)的任務(wù)并行分發(fā)。針對(duì)任務(wù)分發(fā)的兩個(gè)主要優(yōu)化因素：一是用戶的激勵(lì)成本，一般激勵(lì)策略中動(dòng)態(tài)激勵(lì)主要與用戶為完成任務(wù)所移動(dòng)的距離成正相關(guān)；二是所選擇用戶節(jié)點(diǎn)的數(shù)量，需要的用戶數(shù)量越少服務(wù)器所需要付出的基礎(chǔ)代價(jià)也越低。本文分別提出了基于激勵(lì)成本的任務(wù)分發(fā)模型(Incentive Cost Task Distribution Model,ICTDM)和基于用戶數(shù)量的任務(wù)分發(fā)模型(User Number Task Distribution Model,UNTDM)。

2 相關(guān)工作

移動(dòng)群智感知與傳統(tǒng)群智協(xié)同計(jì)算的不同之處在于其移動(dòng)性，傳統(tǒng)群智計(jì)算通常會(huì)將單個(gè)個(gè)體無(wú)法獨(dú)立處理的任務(wù)劃分為多個(gè)部分分別處理，這些任務(wù)通常與地理位置沒(méi)有太多的關(guān)聯(lián)。移動(dòng)群智感知為了充分發(fā)揮其移動(dòng)性，大多任務(wù)都是直接或間接與地理位置相關(guān)聯(lián)。所以與基于用戶社交關(guān)系的參與者集合選擇方法不同，在移動(dòng)群智感知中參與者將以地理位置信息作為首要的選擇條件[9]，其次才考慮其他和任務(wù)完成質(zhì)量相關(guān)的優(yōu)化因素。Zhang等人[10]認(rèn)為在移動(dòng)群智感知中可以通過(guò)利用參與者的位置信息，對(duì)參與者進(jìn)行游戲競(jìng)賽激勵(lì)以達(dá)到效用最大化的效果。Zhang等人[11]通過(guò)從感知區(qū)域覆蓋質(zhì)量的角度對(duì)分布式人群最佳覆蓋推導(dǎo)，利用子模型中的優(yōu)化屬性提出一種基于貪心思想的時(shí)間復(fù)雜度近似于O(n)的隨機(jī)游動(dòng)算法。Zhang等人[12]提出了一種在滿足限定時(shí)空覆蓋率的情況下，通過(guò)最小化參與者人數(shù)來(lái)最小化總系統(tǒng)群智成本的方法。該方法將首先通過(guò)分析備選參與者的歷史任務(wù)完成情況以及移動(dòng)軌跡，分析預(yù)測(cè)未來(lái)用戶的移動(dòng)軌跡，并通過(guò)此預(yù)測(cè)在滿足任務(wù)完成最小覆蓋率的限制下，最小化參與者人數(shù)。因每位參與者都有系統(tǒng)所分配的固定激勵(lì)成本，所以人數(shù)越少系統(tǒng)所需要付出的固定激勵(lì)成本越少。同時(shí)對(duì)于每位用戶的動(dòng)態(tài)激勵(lì)成本，系統(tǒng)需要通過(guò)歷史移動(dòng)軌跡預(yù)測(cè)未來(lái)移動(dòng)軌跡已到達(dá)最小化任務(wù)移動(dòng)距離的目的，該方法同時(shí)對(duì)用戶數(shù)量和任務(wù)移動(dòng)距離進(jìn)行最小化操作，以達(dá)到最小化系統(tǒng)總激勵(lì)成本(固定成本和動(dòng)態(tài)激勵(lì)成本)的目的。

在移動(dòng)群智感知的參與者選擇中，以上大多數(shù)研究都是基于單個(gè)用戶在一定時(shí)間內(nèi)完成某一個(gè)具體的感知任務(wù)。與此相比，若參與者可以同時(shí)接受多個(gè)位置相關(guān)相近的任務(wù)，一次一起完成，無(wú)論對(duì)于平臺(tái)還是對(duì)于參與者來(lái)說(shuō)都是可以極大地提高任務(wù)完成分發(fā)效率的。同時(shí)還可以增加用戶所得到的獎(jiǎng)勵(lì)，提高用戶完成任務(wù)的主觀積極性，起到激勵(lì)作用。Alswailim等人[13]提出了一種對(duì)參與者進(jìn)行評(píng)估的信譽(yù)系統(tǒng)(Reputation System to Evaluate Participants,RSEP)，通過(guò)對(duì)參與者的共享進(jìn)行分組，過(guò)濾出在貢獻(xiàn)方面具有較高的準(zhǔn)確性的參與者。在這一方面，Guo等人[14]分別基于感知任務(wù)的所需時(shí)間、用戶移動(dòng)軌跡、用戶機(jī)會(huì)網(wǎng)絡(luò)傳輸概率等因素，對(duì)移動(dòng)群智感知任務(wù)執(zhí)行節(jié)點(diǎn)的選擇與分配進(jìn)行了研究。分別提出了兩種基于任務(wù)完成路線優(yōu)先和基于任務(wù)優(yōu)先的參與者選擇算法。Karaliopoulos等人[15]在INFOCOM會(huì)議上提出了基于貪心思想的啟發(fā)式算法，其通過(guò)在機(jī)會(huì)網(wǎng)絡(luò)中利用貪心的啟發(fā)式算法對(duì)任務(wù)傳輸延時(shí)進(jìn)行最小化，以達(dá)到感知任務(wù)的收益最大化的目的。Li等人[16]提出一種基于服務(wù)意識(shí)的多任務(wù)分配策略，其同時(shí)考慮了任務(wù)難度、歷史、感知能力和積極性等方面對(duì)參與者進(jìn)行服務(wù)收益最大化的任務(wù)分發(fā)。

3 數(shù)據(jù)感知任務(wù)分發(fā)方法

3.1 任務(wù)地理位置劃分方法

本多任務(wù)動(dòng)態(tài)分發(fā)模型首先根據(jù)任務(wù)地理位置分布，利用密度聚類算法對(duì)任務(wù)進(jìn)行子區(qū)域劃分，并利用最短路徑算法計(jì)算各地鐵站臺(tái)點(diǎn)距離最近的任務(wù)子區(qū)域聚類中心，進(jìn)行任務(wù)分配。

計(jì)算時(shí)將感知任務(wù)的分布區(qū)域記為A,A的實(shí)際范圍是根據(jù)任務(wù)發(fā)布者所發(fā)布的任務(wù)分布位置所確定的。假設(shè)各類移動(dòng)感知任務(wù)γi在地圖上的位置坐標(biāo)為(xi,yi)，所以在地圖上同類任務(wù)γi的集合可以表示為L(zhǎng)={(xi,yi)。任務(wù)分發(fā)時(shí)使用密度聚類進(jìn)行任務(wù)子區(qū)域劃分，對(duì)全部移動(dòng)群智感知任務(wù)區(qū)域中的同類感知任務(wù)進(jìn)行聚類劃分，得到各聚類子區(qū)域的劃分以及子區(qū)域的聚類中心，各子區(qū)域記為C={c1,c2,...,cm}。對(duì)于某一區(qū)域ci而言，記子區(qū)域核心點(diǎn)為oi=。由此可得在當(dāng)前任務(wù)集合中，本類任務(wù)的核心點(diǎn)集合為O=。

3.2 軌道交通覆蓋模型

在子區(qū)域覆蓋模型中，平臺(tái)任務(wù)將會(huì)先利用寬帶網(wǎng)絡(luò)傳輸至地鐵分發(fā)網(wǎng)絡(luò)中，模型相關(guān)符號(hào)見(jiàn)表1。每輛列車(chē)中都擁有全部需要分發(fā)的任務(wù)，在平臺(tái)中任務(wù)子區(qū)域已通過(guò)最短路徑算法分配至指定站點(diǎn)。地鐵分發(fā)系統(tǒng)會(huì)對(duì)上車(chē)用戶的歷史出行情況進(jìn)行分析，通過(guò)參與者的歷史出行記錄預(yù)測(cè)本次出行可能的下車(chē)站點(diǎn)，根據(jù)預(yù)測(cè)可信度對(duì)參與者分配的任務(wù)進(jìn)行選擇。根據(jù)上車(chē)下車(chē)站點(diǎn)即可計(jì)算在列車(chē)內(nèi)停留時(shí)間，可以得知在站點(diǎn)間隔時(shí)間內(nèi)可完成傳輸?shù)目側(cè)蝿?wù)大小，并為其分配屬于指定站點(diǎn)任務(wù)子區(qū)域的任務(wù)內(nèi)容。相比傳統(tǒng)的通過(guò)機(jī)會(huì)網(wǎng)絡(luò)傳輸任務(wù)模式，任務(wù)分配更完整，任務(wù)傳輸成功率更高。

表1 模型相關(guān)符號(hào)表

對(duì)于列車(chē)內(nèi)的動(dòng)態(tài)分發(fā)過(guò)程，記站點(diǎn)s在任務(wù)聚類區(qū)域ci內(nèi) 進(jìn)行分配的感知任務(wù)數(shù)量為則地鐵線路S在該類型任務(wù)的聚類區(qū)域上ci中進(jìn)行分配的感知任務(wù)數(shù)量為，所以該聚類區(qū)域占整個(gè)地鐵線路的比例為

基于式(1)的定義，本文利用各地鐵站點(diǎn)中各乘客所接收到感知任務(wù)位于全部任務(wù)的比例，以及全部區(qū)域A內(nèi)的所有聚類分區(qū)的任務(wù)比例和感知任務(wù)的相關(guān)性對(duì)算法的實(shí)際分發(fā)效果進(jìn)行表示，見(jiàn)式(2)。并且任務(wù)的分配過(guò)程需要滿足由傳輸速度和乘客停留時(shí)間所決定的時(shí)間限制，如式(3)。為了保障能收集到更多的數(shù)據(jù)，算法優(yōu)先將感知任務(wù)分發(fā)給盡可能多的節(jié)點(diǎn)，所以地鐵線路中所包含的任務(wù)集合需要滿足式(4)

3.3 眾包任務(wù)分發(fā)模型

多任務(wù)動(dòng)態(tài)分發(fā)方法的主要優(yōu)化目標(biāo)是在最小化系統(tǒng)成本的情況下，從待選擇用戶中選擇出可在感知任務(wù)時(shí)間約束條件下完成任務(wù)的參與者集合。在當(dāng)前研究中，感知系統(tǒng)的主要成本來(lái)自任務(wù)的傳輸成本以及系統(tǒng)對(duì)用戶完成任務(wù)的激勵(lì)成本。在本系統(tǒng)中任務(wù)通過(guò)地鐵系統(tǒng)的Wi-Fi內(nèi)網(wǎng)進(jìn)行傳輸，無(wú)需消耗移動(dòng)數(shù)據(jù)流量所以無(wú)需考慮。在系統(tǒng)中用戶的激勵(lì)成本中分為兩部分，分別是任務(wù)的固定成本和用戶完成任務(wù)過(guò)程所產(chǎn)生的動(dòng)態(tài)激勵(lì)成本。固定成本在任務(wù)發(fā)布者發(fā)布之初就隨著任務(wù)的難度、時(shí)間等相關(guān)因素進(jìn)行了設(shè)置。系統(tǒng)的動(dòng)態(tài)激勵(lì)成本主要與用戶完成任務(wù)過(guò)程中所花費(fèi)的代價(jià)相關(guān)。在目前研究中主要以用戶移動(dòng)距離作為評(píng)判標(biāo)準(zhǔn)。

可知在任務(wù)不變的情況下，系統(tǒng)所花費(fèi)的總成本主要與用戶的移動(dòng)距離相關(guān)。同樣調(diào)用較少的參與者可以減少系統(tǒng)需要發(fā)放的固定成本，降低系統(tǒng)管理參與者的成本，提高單個(gè)參與者的激勵(lì)收益，促進(jìn)用戶完成任務(wù)。

假設(shè)在移動(dòng)群智感知系統(tǒng)中具有n個(gè)待完成的任務(wù)T={t1,t2,...,ti,...,tn}。為保證感知結(jié)果的普適性和準(zhǔn)確性，通常對(duì)于每個(gè)任務(wù)都需要由ri個(gè)人完成。并且通過(guò)錄像、錄音、文字等方式對(duì)感知對(duì)象進(jìn)行數(shù)據(jù)的收集。在本研究中，假設(shè)完成每個(gè)任務(wù)需要時(shí)間為hmin。假設(shè)感知系統(tǒng)中有m個(gè)可選參與者U={u1,u2,...,uj,...,um}，并且要求用戶所分配的任務(wù)需要在Hh內(nèi)完成，并且設(shè)參與者的移動(dòng)速度是vm/min。使用U Ti={ui1,ui2,ui3,...}表示任務(wù)集合ti被分配到的用戶集合，完成任務(wù)集合T全部任務(wù)的用戶集合可以用P={p1,p2,p3,...}(P=UT1∪UT2∪...∪UTn)表示。各參與者被分配到的uj任務(wù)集是T Uj={tj1,tj2,tj3,...}，完成這些任務(wù)所需要移動(dòng)的總距離是D(TUj)。

多任務(wù)動(dòng)態(tài)參與者選擇模型的優(yōu)化目標(biāo)分為兩方面：一個(gè)是對(duì)系統(tǒng)全部任務(wù)的移動(dòng)距離進(jìn)行最小化式(5)，因?yàn)橄到y(tǒng)動(dòng)態(tài)激勵(lì)與用戶移動(dòng)距離的相關(guān)性，所以當(dāng)系統(tǒng)對(duì)參與者移動(dòng)距離進(jìn)行最小化時(shí)，可以實(shí)現(xiàn)全局動(dòng)態(tài)激勵(lì)成本的最小化；另一個(gè)是對(duì)用戶的總?cè)藬?shù)進(jìn)行最小化式(6)，當(dāng)出現(xiàn)緊急情況感知平臺(tái)突發(fā)大量群智感知需求時(shí)，需要對(duì)用戶實(shí)現(xiàn)最大化的利用。發(fā)揮多任務(wù)動(dòng)態(tài)分發(fā)方法的特性，為每個(gè)用戶進(jìn)行任務(wù)的最大化分配，使得用戶完成任務(wù)可以獲得更多的報(bào)酬，實(shí)現(xiàn)平臺(tái)與用戶的雙贏。

為保證平臺(tái)信用檢測(cè)機(jī)制的良好運(yùn)行，實(shí)現(xiàn)任務(wù)完成質(zhì)量的把控。任務(wù)需要進(jìn)行冗余分發(fā)，以提高任務(wù)完成率、確定感知準(zhǔn)確度。所以任務(wù)ti需要ri個(gè)人完成，如式(7)。對(duì)于時(shí)間限制較高的任務(wù)，需要在H h內(nèi)完成，如式(8)。通常完成任務(wù)所需要花費(fèi)的時(shí)間分為兩部分，用戶移動(dòng)到任務(wù)地點(diǎn)所花費(fèi)的時(shí)間和用戶在任務(wù)地點(diǎn)完成任務(wù)的時(shí)間

由于該問(wèn)題不是普通的單目標(biāo)優(yōu)化問(wèn)題，本問(wèn)題的主要優(yōu)化目標(biāo)有兩個(gè)：分別是用戶的數(shù)量和完成系統(tǒng)分配任務(wù)需要移動(dòng)的距離。并且各優(yōu)化目標(biāo)范圍較大，這是一個(gè)典型的NP難問(wèn)題。

在多目標(biāo)優(yōu)化問(wèn)題中，由于存在多個(gè)優(yōu)化目標(biāo)，所以可能存在優(yōu)化目標(biāo)之間造成沖突或者無(wú)法比較的問(wèn)題，不一定存在同時(shí)滿足所有優(yōu)化目標(biāo)的最優(yōu)解。所以本文針對(duì)此問(wèn)題的優(yōu)化目標(biāo)有兩個(gè)，一個(gè)是盡可能縮短參與為完成任務(wù)的移動(dòng)距離，另一個(gè)是對(duì)選擇的參與人數(shù)進(jìn)行最小化。因此，本文將以其中一個(gè)因素作為限制，在此限制上對(duì)另一因素進(jìn)行優(yōu)化求解。

4 實(shí)驗(yàn)評(píng)估

4.1 目標(biāo)數(shù)據(jù)

本文主要針對(duì)長(zhǎng)沙市地鐵軌道交通情況的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，獲取了長(zhǎng)沙市內(nèi)的3條地鐵線路以及1條磁懸浮快線的實(shí)際客運(yùn)數(shù)據(jù)。主要包括各運(yùn)營(yíng)線路分布情況、各線路運(yùn)營(yíng)時(shí)間、歷史客運(yùn)流量、沿途站點(diǎn)信息、線路班車(chē)信息、線路市區(qū)覆蓋情況、實(shí)際運(yùn)營(yíng)里程等相關(guān)信息。

地鐵的運(yùn)營(yíng)線路信息可以反映該地鐵系統(tǒng)對(duì)城區(qū)的覆蓋程度和地鐵站點(diǎn)的主要分布區(qū)域，以此推斷地鐵系統(tǒng)對(duì)感知任務(wù)范圍的有效覆蓋。各線路的運(yùn)營(yíng)時(shí)間信息可以用于用戶停留時(shí)間的分析，通過(guò)上下車(chē)站點(diǎn)可以得出在列車(chē)內(nèi)停留時(shí)間，從而得出可用的任務(wù)傳輸時(shí)間。

對(duì)于地鐵乘客的實(shí)際出行行為，本文使用由長(zhǎng)沙市軌道交通運(yùn)營(yíng)公司提供的地鐵IC卡脫敏數(shù)據(jù)進(jìn)行分析，源數(shù)據(jù)字段格式如表2，經(jīng)過(guò)刷卡數(shù)據(jù)的初步分析，發(fā)現(xiàn)原始數(shù)據(jù)中存在與本研究無(wú)關(guān)的數(shù)據(jù)以及無(wú)效數(shù)據(jù)，經(jīng)清洗后抽樣取出本實(shí)驗(yàn)所需的5個(gè)字段，包括卡號(hào)、進(jìn)站站點(diǎn)、進(jìn)站時(shí)間、出站站點(diǎn)和出站時(shí)間，作為實(shí)驗(yàn)中乘客擴(kuò)散的基礎(chǔ)數(shù)據(jù)。

表2 智能卡數(shù)據(jù)格式

對(duì)于感知任務(wù)，將以長(zhǎng)沙市酒店實(shí)際情況信息作為感知目標(biāo)，其中包括酒店的位置、門(mén)面外觀、前臺(tái)外觀、線下實(shí)際報(bào)價(jià)表等等。因此酒店的位置分布就是本次移動(dòng)群智感知的任務(wù)分布范圍。酒店數(shù)據(jù)通過(guò)美團(tuán)網(wǎng)獲取了1120家酒店信息，其中包括酒店在線上公布的圖片、位置、價(jià)格、名稱、類別。

4.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

在該問(wèn)題中，對(duì)于不同任務(wù)分發(fā)方法選擇出的參與者集合。本文通過(guò)4個(gè)參數(shù)對(duì)算法進(jìn)行比較：參與者的人數(shù)、人均任務(wù)數(shù)量、完成任務(wù)總移動(dòng)距離以及距離和人數(shù)的乘積。算法的影響因素包括：總?cè)蝿?wù)個(gè)數(shù)、候選用戶人數(shù)、任務(wù)分布情況、任務(wù)發(fā)布時(shí)間、任務(wù)緊急程度等。通過(guò)以上多個(gè)場(chǎng)景進(jìn)行實(shí)驗(yàn)分析，對(duì)比算法選出參與者集的性能優(yōu)劣。

為了更好地對(duì)提出的兩種算法性能進(jìn)行分析比較，本文在現(xiàn)有的移動(dòng)群智感知任務(wù)分發(fā)算法中，選擇了同類算法Heuristics和SBAMA(Service Benefit Aware Multi-task Assignment)進(jìn)行比較。Heuristics算法是Karaliopoulos等人[15]在INFOCOM會(huì)議上提出的基于貪心思想的啟發(fā)式算法。其通過(guò)在機(jī)會(huì)網(wǎng)絡(luò)中利用貪心的啟發(fā)式算法對(duì)任務(wù)傳輸延時(shí)進(jìn)行最小化，以達(dá)到感知任務(wù)的收益進(jìn)行最大化的目的的算法。而SBAMA算法是Li等人[16]在2019年提出的一種基于服務(wù)意識(shí)的多任務(wù)分配策略。其同時(shí)考慮了任務(wù)難度、歷史、感知能力和積極性等方面對(duì)參與者進(jìn)行服務(wù)收益最大化的任務(wù)分發(fā)。對(duì)于仿真模型的相關(guān)場(chǎng)景參數(shù)，各算法統(tǒng)一進(jìn)行設(shè)置，如表3。

表3 模型參數(shù)設(shè)置

由于已有文獻(xiàn)研究場(chǎng)景與本文的差異，為了保證對(duì)比的合理性和有效性，我們將這兩種的主要參與者選擇策略應(yīng)用到本文的實(shí)驗(yàn)場(chǎng)景中。分別對(duì)比了本文提出的ICTDM,UNTDM,Heuristics以及SBAMA算法在不同影響因素(總?cè)蝿?wù)個(gè)數(shù)、候選用戶人數(shù)、任務(wù)發(fā)布時(shí)間、任務(wù)限制時(shí)間)下的可用性。利用算法選擇出的參與者人數(shù)、移動(dòng)總距離以及兩者的乘積對(duì)算法的綜合性能作出評(píng)定。

4.3 實(shí)驗(yàn)數(shù)據(jù)結(jié)果

(1)任務(wù)區(qū)域劃分

多任務(wù)動(dòng)態(tài)分發(fā)算法首先將根據(jù)地鐵在市區(qū)內(nèi)的分布情況以及具體任務(wù)集的地理位置，通過(guò)密度聚類對(duì)任務(wù)以劃分范圍內(nèi)站點(diǎn)間距為限制進(jìn)行子區(qū)域劃分。對(duì)任務(wù)的主要分布區(qū)域和地鐵分布進(jìn)行結(jié)合，繪制任務(wù)分布聚類圖，如圖1所示。分發(fā)系統(tǒng)將對(duì)地鐵周邊的任務(wù)區(qū)域進(jìn)行多任務(wù)分發(fā)，東北處離地鐵較遠(yuǎn)的區(qū)域采取移動(dòng)網(wǎng)絡(luò)形式進(jìn)行分發(fā)。

圖1 任務(wù)子區(qū)域分布

(2)算法實(shí)際運(yùn)行效率

評(píng)價(jià)一個(gè)算法的好壞除了實(shí)現(xiàn)效果、選擇結(jié)果以外還應(yīng)包括算法的實(shí)際運(yùn)行時(shí)間。因?yàn)檫^(guò)長(zhǎng)的運(yùn)行時(shí)間會(huì)增加用戶等待時(shí)間，占用過(guò)多的計(jì)算資源導(dǎo)致算法的實(shí)用性大大降低。本實(shí)驗(yàn)的運(yùn)行環(huán)境如表4。

表4 實(shí)驗(yàn)軟硬件環(huán)境

從圖2可得出，ICTDM的平均運(yùn)行時(shí)間為1.96 s；UNTDM的平均運(yùn)行時(shí)間為1.09 s；Heuristics算法的平均運(yùn)行時(shí)間為1.47 s；SBAMA則為2.28 s。可知ICTDM和SBAMA算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)大于UNTDM和 Heuristics算法。從算法的時(shí)間復(fù)雜度和算法原理可推測(cè)可能由于前兩種算法需要考慮因素過(guò)多，每次算法迭代都需要遍歷所有候選者并對(duì)用戶周?chē)娜蝿?wù)進(jìn)行篩選。而UNTDM算法只需要從任務(wù)集中進(jìn)行選擇，并將任務(wù)集合分配給用戶即可。在通常場(chǎng)景下，待選擇用戶數(shù)量遠(yuǎn)遠(yuǎn)大于待分發(fā)任務(wù)數(shù)量，所以從用戶角度進(jìn)行處理的算法時(shí)間復(fù)雜度會(huì)有所提高。所以雖然ICTDM的系統(tǒng)成本較低，但在考慮時(shí)間要求、性能較高的應(yīng)用場(chǎng)景時(shí)，UNTDM可以帶來(lái)較好的使用效果。

圖2 任務(wù)數(shù)量與算法運(yùn)行時(shí)間

(3)分發(fā)時(shí)間的影響

對(duì)于任務(wù)分發(fā)算法，重要的影響因素除了任務(wù)數(shù)量，還包括任務(wù)分發(fā)時(shí)間段。在不同時(shí)間段對(duì)任務(wù)的分發(fā)由于用戶狀態(tài)的差異，可能會(huì)選擇出差異較大的參與者集合，造成不同的任務(wù)分發(fā)方案。例如分別在工作日和周末進(jìn)行任務(wù)分發(fā)時(shí)，周末的用戶數(shù)量、用戶靈活度、參與程度都會(huì)更高，兩個(gè)時(shí)間段的用戶特征具有較大的差異。所以本次實(shí)驗(yàn)將對(duì)任務(wù)的分發(fā)時(shí)間段對(duì)用戶選擇的影響進(jìn)行研究，并對(duì)周末與工作日兩種算法的多個(gè)評(píng)定因素進(jìn)行對(duì)比。根據(jù)任務(wù)的不同，將參數(shù)N修改為300進(jìn)行實(shí)驗(yàn)。

從圖3(a)和圖3(c)可得出，4個(gè)算法在工作日選出的平均參與者人數(shù)為160.63人，周末為194.90人，工作日時(shí)的參與者數(shù)量較周末減少了21.33%。移動(dòng)距離相比周末縮短了25.77%。在執(zhí)行相同任務(wù)的情況下，可以看出工作日進(jìn)行任務(wù)分發(fā)選出的參與者數(shù)量較少、人均分配到的任務(wù)數(shù)量較多，系統(tǒng)的總移動(dòng)距離也較小。根據(jù)上述實(shí)驗(yàn)可得出ICTDM和UNTDM算法的區(qū)別與聯(lián)系如表5。

表5 算法應(yīng)用場(chǎng)景對(duì)比

在圖3(d)中，同時(shí)考慮用戶數(shù)量和系統(tǒng)完成任務(wù)的自動(dòng)移動(dòng)距離，可以發(fā)現(xiàn)在工作日時(shí)系統(tǒng)所選擇出的參與者集合性能更優(yōu)。所以在工作日時(shí)，感知系統(tǒng)應(yīng)該適當(dāng)加大任務(wù)的基礎(chǔ)獎(jiǎng)勵(lì)和動(dòng)態(tài)獎(jiǎng)勵(lì)，以保證感知任務(wù)的穩(wěn)定完成。

圖3 任務(wù)分發(fā)時(shí)間的影響

5 結(jié)論與展望

本文主要研究了移動(dòng)群智感知的任務(wù)分發(fā)方法，提出了一種基于地鐵乘客的多任務(wù)動(dòng)態(tài)分發(fā)方法。在該方法中構(gòu)建了基于地鐵系統(tǒng)的任務(wù)擴(kuò)散模型，并分析了針對(duì)不同優(yōu)化目標(biāo)的多任務(wù)分發(fā)問(wèn)題。提出兩種具有一定約束限制的動(dòng)態(tài)任務(wù)分發(fā)算法：以參與者個(gè)數(shù)作為最低約束，將用戶總移動(dòng)距離作為優(yōu)化目標(biāo)的ICTDM算法；以用戶總移動(dòng)距離作為最低約束，將參與任務(wù)用戶數(shù)量作為優(yōu)化目標(biāo)的UNTDM算法。并通過(guò)長(zhǎng)沙市的用戶出行和酒店數(shù)據(jù)集對(duì)兩種算法和傳統(tǒng)算法的多個(gè)影響因素進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明：ICTDM算法可以為感知系統(tǒng)帶來(lái)比傳統(tǒng)算法更低的激勵(lì)成本和基礎(chǔ)成本；UNTDM算法則可以在較短的時(shí)間內(nèi)利用較低的系統(tǒng)資源，對(duì)應(yīng)急情況人員不足時(shí)的感知任務(wù)進(jìn)行合理分配，保證感知質(zhì)量。并得出相比在周末進(jìn)行任務(wù)分發(fā)，在工作日進(jìn)行感知任務(wù)的分發(fā)可以具有更小的用戶數(shù)量和用戶移動(dòng)距離。

文章的重點(diǎn)集中在地鐵乘客的基礎(chǔ)上，進(jìn)行任務(wù)分發(fā)時(shí)參與者和移動(dòng)距離的最優(yōu)化。未考慮到每個(gè)參與者對(duì)不同任務(wù)的不同性，沒(méi)有為每個(gè)用戶分發(fā)其最適合的任務(wù)。下一步工作中將結(jié)合每個(gè)用戶節(jié)點(diǎn)的差異性和具體任務(wù)類別進(jìn)行針對(duì)性的任務(wù)分發(fā)。以達(dá)到增加任務(wù)的適應(yīng)性，提高任務(wù)的完成質(zhì)量和效率的目的。