群智感知中面向移動群體的參與者選擇優(yōu)化模型

蔣偉進(jìn) 呂斯健 陳曉紅

(1.湖南工商大學(xué)計算機(jī)與信息工程學(xué)院,湖南長沙 410205;2.新零售虛擬現(xiàn)實技術(shù)湖南省重點實驗室,湖南長沙 410205)

1 引言

群智協(xié)同計算作為當(dāng)前的研究熱點之一,與多個學(xué)科領(lǐng)域都有所交叉.在這其中,移動群智感知作為協(xié)同計算、普適計算的前期數(shù)據(jù)獲取步驟,更是已經(jīng)成為了普適計算領(lǐng)域的首要研究問題.在移動群智感知(sparse mobile crowdsensing)[1]過程中,其主要依賴當(dāng)前大量用戶所擁有的智能手機(jī)、智能手表等智能設(shè)備上的多元傳感器來完成針對大規(guī)模數(shù)據(jù)[2]的群智感知任務(wù),例如交通情況檢測、自然氣候以及植物生長狀態(tài)的收集等等.因此,一個通用的移動群智感知方法對于感知的實現(xiàn)、數(shù)據(jù)的收集就顯得尤為重要.在當(dāng)前已有的系統(tǒng)平臺中,例如e-Bird、CrowdFlower,即使是在這些用戶量較大的群智計算平臺中,也依然是由數(shù)據(jù)需求者發(fā)布任務(wù)要求,用戶自行在平臺上選擇任務(wù)的模式.依然無法做到平臺根據(jù)任務(wù)屬性以及用戶行為[3]自主進(jìn)行任務(wù)分配.

在城市基礎(chǔ)設(shè)施中,可以發(fā)現(xiàn)地鐵軌道交通網(wǎng)絡(luò)作為一種已經(jīng)規(guī)劃好的城市覆蓋資源,其建立的目的就是為了實現(xiàn)對城市市區(qū)熱點地區(qū)范圍的覆蓋,并且地鐵還是大多數(shù)市民的首選出行通勤方式.完整的城區(qū)覆蓋面積以及長期大量的客流都恰好可以滿足移動群智感知、群智計算的硬性需求.并且地鐵Wi-Fi的覆蓋以及地鐵服務(wù)人群的出行規(guī)律性,也可以滿足任務(wù)分發(fā)的速率、時間需求以及任務(wù)分發(fā)準(zhǔn)確度的保證.Liu[4]等人通過了對部分站臺停留乘客的手機(jī)使用情況以及軌跡跟蹤,實現(xiàn)了針對市區(qū)內(nèi)的城市交通監(jiān)測.在相同或鄰近地鐵車廂中的乘客,大多可以在一段時間內(nèi)維持一個持續(xù)且穩(wěn)定的接觸時間[5],使得任務(wù)信息可以在該車廂內(nèi)用戶之間進(jìn)行傳輸.并且用戶節(jié)點之間的接觸時間也可以通過不同站點之間的已知的停留間隔進(jìn)行預(yù)測.這些特點使得基于地鐵交通的移動群智感知任務(wù)分發(fā)模型具有相比傳統(tǒng)機(jī)會網(wǎng)絡(luò)[6]分發(fā)模型更高的分發(fā)率和傳輸質(zhì)量.地鐵站點任務(wù)分配示例見圖1.

圖1 地鐵站點任務(wù)分配示例Fig.1 Example of task assignment at a subway station

本文針對這兩個用戶選擇的相關(guān)優(yōu)化因素,分別提出:以參與者個數(shù)為約束,將用戶激勵成本(移動距離)作為優(yōu)化目標(biāo)的OCTDM(optimize cost task distribution model)算法;以用戶激勵成本(移動距離)為約束,將參與任務(wù)用戶數(shù)量作為優(yōu)化目標(biāo)的ONPTDM(optimize number of people task distribution model)算法.并且通過長沙市地鐵運營數(shù)據(jù)集、酒店數(shù)據(jù)集對設(shè)計的兩種參與者選擇算法進(jìn)行試驗評估,通過對用戶移動距離、參與者數(shù)量等實驗結(jié)果的比對,選擇出在不同情況下代價最低的算法.

2 相關(guān)工作

人工智能技術(shù)的迅速發(fā)展催使大數(shù)據(jù)需求的日益增長,移動群智感知作為一種更為高效全面的數(shù)據(jù)收集方式[7],可以以多種方式實現(xiàn)大部分多源、異構(gòu)數(shù)據(jù)的主動收集.Wei等人[8]對群體智能這一概念進(jìn)行了深入的說明,并對其中的相關(guān)技術(shù)、工作流程、數(shù)據(jù)分析做出了較為詳細(xì)的介紹.Pietro等人[9]認(rèn)為群智協(xié)同計算這一全新的計算模式是為了更好的通過結(jié)合協(xié)同計算和人工智能[10]技術(shù),解決群智資源的有效管理和協(xié)同利用這一問題而誕生的,通過利用各種形式的群體智能來實現(xiàn)問題的求解.在這其中,多任務(wù)的被動分發(fā)問題也可以看作是用戶、參與者集合的主動選擇問題,即如何通過現(xiàn)有資源(任務(wù)與參與者的時空位置、用戶歷史任務(wù)完成情況、參與者之間的社交關(guān)系等),找出各組任務(wù)中最為適合的參與者集合.所以當(dāng)前移動群智感知的任務(wù)分發(fā)方式大致可以分為:基于用戶社交關(guān)系的任務(wù)分發(fā)方法和基于任務(wù)時空位置的任務(wù)分發(fā)方法兩種.

在移動群智感知參與者的選擇問題中,參與者對任務(wù)的熟悉情況、參與者集合之間的社交關(guān)系以及距離都會對任務(wù)的分發(fā)進(jìn)度、完成質(zhì)量、完成速度造成一定的影響.例如:將某類任務(wù)繼續(xù)分發(fā)給熟悉或曾經(jīng)完成此類任務(wù)質(zhì)量較高的參與者,任務(wù)的完成質(zhì)量會比隨機(jī)分發(fā)給對此類任務(wù)不熟悉的參與者更高.若任務(wù)分發(fā)給一個相互熟悉的團(tuán)體,完成任務(wù)時的參與者集合內(nèi)的信息溝通效率會更高,完成任務(wù)的過程也會對團(tuán)隊產(chǎn)生社交激勵的作用.Hosseini等人[11]對眾包的四個基本概念進(jìn)行了解釋,包括參與者,眾包,眾包任務(wù)以及眾包平臺.Xiong等人[12]針對移動群智感知中的隱私保護(hù)措施進(jìn)行了分析,提出了一種基于布隆過濾器的用戶聯(lián)盟匹配隱私保護(hù)方案.Gionis等人[13]在群智感知任務(wù)分發(fā)過程中,提出了通過在現(xiàn)有社交網(wǎng)絡(luò)關(guān)系的對任務(wù)參與者進(jìn)行查詢,在其中建立密集連通子圖尋找社交關(guān)系權(quán)重較大的、符合任務(wù)完成條件的參與者集合.并且本方法除了對在線社交關(guān)系進(jìn)行了查詢,還考慮了參與者之間的時空位置關(guān)系,曾經(jīng)參與任務(wù)狀態(tài)等信息.使得尋找到的團(tuán)體在關(guān)系密切的基礎(chǔ)上,地理位置距離也相對較近,或在任務(wù)完成范圍內(nèi).

綜上,當(dāng)前大多數(shù)感知任務(wù)分發(fā)方法都是基于部分社交或時空位置的約束條件和激勵方式所實現(xiàn)的.對于多任務(wù)分發(fā)的方法和研究依然較少,對于任務(wù)分配過程中的具體任務(wù)信息、任務(wù)所屬區(qū)域、任務(wù)分發(fā)時間等影響因素[14]依然考慮較少.為此,本文在現(xiàn)有城市地鐵軌道交通的基礎(chǔ)上,提出了面向乘客擴(kuò)散的多任務(wù)動態(tài)分發(fā)方法對參與者選擇問題進(jìn)行優(yōu)化.并基于這一問題提出兩種具有不同側(cè)重點的優(yōu)化約束算法,以期相比傳統(tǒng)算法,進(jìn)一步的優(yōu)化用戶移動距離,最小化完成任務(wù)需要的參與者數(shù)量,降低系統(tǒng)激勵成本.

3 參與者選擇方法

參與者選擇優(yōu)化模型主要由感知任務(wù)的收集、任務(wù)的分發(fā)以及任務(wù)的執(zhí)行3個部分組成.

3.1 群智感知的需求

在移動群智感知平臺中,數(shù)據(jù)收集者所發(fā)布的任務(wù)大概可以分為兩種,一種是時間期限比較寬泛,時效性沒那么強,大致在一周兩周內(nèi)完成都可以,例如查看某地點的商家是否還存在,查看某地區(qū)植物生長狀況是否需要修剪.對于這種任務(wù),參與者只需要方便時,路過任務(wù)地點順便完成任務(wù)即可.這類感知任務(wù)群智平臺在接收到后可在系統(tǒng)壓力較小時進(jìn)行參與者的選擇以及任務(wù)的分發(fā),對應(yīng)的任務(wù)激勵代價和系統(tǒng)資源消耗都較小.另一類任務(wù)會有較短的時間限制,具有所需感知的任務(wù)數(shù)據(jù)具有一定的時效性,過了一段時間數(shù)據(jù)的價值會急劇下降,變?yōu)闊o用數(shù)據(jù).所以需要系統(tǒng)立即在時限內(nèi)對感知任務(wù)進(jìn)行分發(fā),對參與者進(jìn)行選擇.例如時效性較高的路面交通狀況,危機(jī)險情的一線情況等.并且在事件發(fā)生時,這類任務(wù)的數(shù)據(jù)需求可能在短時間內(nèi)大量涌現(xiàn),所以可能會出現(xiàn)系統(tǒng)可調(diào)配參與者供不應(yīng)求的需求場景.所以在此引入多任務(wù)[15]分發(fā)機(jī)制就可以適當(dāng)減緩系統(tǒng)和參與者壓力,當(dāng)系統(tǒng)出現(xiàn)用戶資源不足時,系統(tǒng)可根據(jù)任務(wù)的緊急程度、通過根據(jù)任務(wù)屬性位置分析相似任務(wù)、參與者之間的關(guān)系屬性,對任務(wù)和參與者進(jìn)行一定的組合分發(fā).將類似任務(wù)打包合并分發(fā)處理,以達(dá)到降低系統(tǒng)任務(wù)分發(fā)壓力的效果.

3.2 參與者的選擇

在基于地鐵的多任務(wù)分發(fā)方法中,分發(fā)系統(tǒng)主要包括用戶節(jié)點和列車車廂,在每個站點,乘客會進(jìn)入到列車車廂這一個封閉的載體中.任務(wù)信息將通過列車Wi-Fi或者用戶手機(jī)的藍(lán)牙進(jìn)行傳輸,在這個封閉區(qū)間中任務(wù)可以進(jìn)行穩(wěn)定持續(xù)的傳輸分發(fā).當(dāng)?shù)竭_(dá)站點時,用戶節(jié)點都有可能離開、加入也有可能保持不變,從這個角度看列車內(nèi)節(jié)點又是一個動態(tài)分發(fā)的過程.

3.2.1 移動群體中的參與者選擇

首先,當(dāng)群智感知系統(tǒng)收到數(shù)據(jù)需求者的感知任務(wù)后,會根據(jù)所有感知目標(biāo)的時空位置分布,對其中同類的任務(wù)通過密度聚類算法以劃分范圍內(nèi)站點間距為大小限制進(jìn)行聚類劃分.每個同類任務(wù)區(qū)域都將產(chǎn)生一個任務(wù)聚類中心.其次,系統(tǒng)將會根據(jù)每一地鐵站點和聚類中心的距離,為其分配最近的任務(wù)子區(qū)域,以到達(dá)通過市區(qū)地鐵軌道交通[16]對任務(wù)區(qū)域進(jìn)行覆蓋的目的.并且預(yù)測每一用戶節(jié)點的可能下車站點,在車廂內(nèi)為其分發(fā)該下車站點附近的任務(wù)子區(qū)域的相關(guān)任務(wù)集合.最后,系統(tǒng)將會依此進(jìn)行多任務(wù)分發(fā),通過車廂內(nèi)的移動Wi-Fi或者用戶之間的藍(lán)牙進(jìn)行傳輸擴(kuò)散,如圖2.

圖2 多任務(wù)分發(fā)方法Fig.2 Multi-task distribution method

由于公共交通線路的固定性和穩(wěn)定性,公共交通的出行方式成為了人們?nèi)粘Ｍㄇ诘氖滓x擇,并且由于通勤目的地和出發(fā)地的固定性,使得在工作日公交系統(tǒng)中存在規(guī)律性的用戶出行線路[17-18].所以,用戶節(jié)點的下車位置則可以通過乘客的歷史出行乘車記錄進(jìn)行預(yù)測推斷,以預(yù)測可信度作為選擇參與者的依據(jù).地鐵乘客的日常出行規(guī)劃路徑[19]都是主要集中在幾個習(xí)慣性站點或路線,并且和時間節(jié)日都具有一定的相關(guān)性.所以只需要對參與者的部分歷史出行記錄進(jìn)行分析,以預(yù)測可信度作為權(quán)重,即可對用戶可能的下車站點進(jìn)行覆蓋.例如:可對用戶在一段時間內(nèi)的出行情況進(jìn)行分析,例如早上、下午、反復(fù)出行的周期性路線和站點.通過機(jī)器學(xué)習(xí)等手段均可對此進(jìn)行分析預(yù)測,并且準(zhǔn)確度十分高.當(dāng)用戶出行與先前預(yù)測模型不符的出行情況時,可通過地鐵進(jìn)出站記錄,以及GPS記錄出行軌跡.并且地鐵運營站點停留時間十分穩(wěn)定且精確,通過將用戶的出行模型預(yù)測規(guī)律,與地鐵運營時間相結(jié)合,即可精確的對用戶下車時間、地點、車廂接觸停留時間進(jìn)行預(yù)測跟蹤.

3.2.2 群體區(qū)域的聚類劃分

在傳統(tǒng)的移動群體感知中,通常采用的劃分方法是根據(jù)目標(biāo)地圖的經(jīng)緯度對目標(biāo)區(qū)域進(jìn)行光柵化,即用相互垂直的經(jīng)緯線將任務(wù)感知區(qū)域劃分為若干正方形.當(dāng)用戶出現(xiàn)在其中某個劃分區(qū)域中時,則該區(qū)域被用戶所覆蓋.這種無差別地區(qū)域劃分雖然簡單易行,并且可以覆蓋整個移動感知區(qū)域,但不能反映區(qū)域與任務(wù)分布的關(guān)系.通常任務(wù)的完成類別、數(shù)量和時間限制通常都是不同,這些都與區(qū)域的內(nèi)部特征有關(guān),而傳統(tǒng)的無差別網(wǎng)格劃分方法很難做到.不同的是,基于密度的聚類方法可以在所需要查找的全部數(shù)據(jù)中找到不同類型和大小的聚類.在聚類過程中,將先發(fā)現(xiàn)密度比較高的數(shù)據(jù),然后將這些數(shù)據(jù)繪制為一個統(tǒng)一的整體一個聚類,在這里密度聚類可以對同類任務(wù)在地圖上的分布情況作出較好的聚類劃分,生成不同大小合適的的任務(wù)區(qū)域.

在此基礎(chǔ)上,本文提出了一種基于移動感知類別的區(qū)域劃分方法.本方法從聚類的角度出發(fā),根據(jù)任務(wù)類別的特征屬性和類別的時空位置,對同一類任務(wù)在區(qū)域內(nèi)得到進(jìn)行聚類得出任務(wù)聚類區(qū)域的中心點.根據(jù)任務(wù)請求者給出的具體感知任務(wù)來確定感知目標(biāo)類別,數(shù)據(jù)需求者在發(fā)布任務(wù)時需要進(jìn)行任務(wù)類別的選擇,以此確定與之相應(yīng)的感知對象.

3.2.3 任務(wù)參與者的選擇

在感知平臺中,為了更好的優(yōu)化平臺任務(wù)處理能力,起到激勵用戶的作用.同時,當(dāng)出現(xiàn)應(yīng)急任務(wù)時,希望系統(tǒng)可以在一定時間內(nèi)盡可能完成多的任務(wù).用戶的主要激勵由兩部分組成:其中第1部分是每個任務(wù)發(fā)布時就分配好的固定基本收入,第2部分是動態(tài)激勵收入,用戶在完成任務(wù)時的移動距離越大,該部分激勵收入也就越多.所以,該問題的優(yōu)化目標(biāo)是最小化用戶的數(shù)量和用戶為完成任務(wù)時所需要移動的距離.基于此問題,本文提出兩種參與者選擇算法:以用戶激勵成本(移動距離)為優(yōu)化目標(biāo)的OCTDM(optimize cost task distribution model)算法;以參與任務(wù)用戶數(shù)量作為優(yōu)化目標(biāo)的ONPTDM(optimize number of people task distribution model)算法.

3.3 感知任務(wù)的執(zhí)行

當(dāng)在地鐵中群智感知用戶收到所預(yù)測的下車站點的感知任務(wù)時,若不符合下車位置可重新手動選擇站點,符合可直接接受任務(wù)組合.用戶在相關(guān)地鐵站點下車后,可直接自行前往或跟隨系統(tǒng)分配的導(dǎo)航路徑前往任務(wù)點進(jìn)行感知任務(wù).參與者可直接通過智能手機(jī)進(jìn)行感知、計算、上傳等操作.在不同的任務(wù)之中可能會具有不同的感知方式要求,例如視頻、拍照、錄音、情況說明選擇等等.同時感知任務(wù)完成的質(zhì)量也將影響到參與者的激勵以及日后的感知信用.所以參與者在完成感知任務(wù)時可對同一任務(wù)進(jìn)行多角度多方面的采集以保證數(shù)據(jù)的全面、多樣、真實性、可靠性.用戶完成采集后數(shù)據(jù)將會在移動終端進(jìn)行預(yù)處理操作,提取出感知任務(wù)相關(guān)的有效信息,并通過移動數(shù)據(jù)或者Wi-Fi進(jìn)行數(shù)據(jù)上傳.

3.4 感知任務(wù)實例

通過一個實際的任務(wù)例子,說明基于地鐵的多任務(wù)分發(fā)方法的一些功能:長沙國慶節(jié)當(dāng)天在橘子洲頭有煙花表演,吸引了大量的外地游客以及本地居民的觀賞,欣賞煙花的同時也造成了橘子洲附近人流量的急劇飆升,造成道路癱瘓、地鐵嚴(yán)重?fù)矶碌惹闆r.巨大的人流也引起了事故發(fā)生概率的增加.針對這一緊急情況,實時人流的監(jiān)控,各路口、地鐵口中的擁堵運行情況等信息對于人流的疏導(dǎo)來說就顯得尤為重要.并且這一系列任務(wù)對時間的要求也極高,同時獲取的數(shù)據(jù)量也是越大越有利于人流走勢的分析.任務(wù)的發(fā)布者希望參與者可通過手機(jī)或視頻的方式,加上定位信息記錄當(dāng)前各處的人流狀況.希望在2小時內(nèi)持續(xù)的可以收到相關(guān)任務(wù)的信息,并且每個人都是移動的,可以同時采集多處位置的情況,完成多個任務(wù).為保證數(shù)據(jù)的多樣真實性,且數(shù)據(jù)不需過于冗余,所以每條街道記錄4次足以滿足感知覆蓋的需求.所以,為了降低平臺的激勵成本,參與者選擇方法將會始終不斷刷新任務(wù)完成的覆蓋面積,不斷更新參與者的選擇集合至感知未被覆蓋的區(qū)域.以此保證最小化參與者的移動距離,以降低系統(tǒng)的激勵成本.

4 參與者選擇優(yōu)化模型

4.1 群體區(qū)域聚類劃分模型

密度聚類過程如下圖3,當(dāng)設(shè)定eps為R,MinPts為2時,圖片中的點都是淺黃色的點.選擇其中一個點作為算法的入口點,然后綠色點是被選中的入口.將EPS范圍設(shè)置為圖中圓的半徑R,最小值為2.

圖3 密度聚類過程Fig.3 Density clustering process

這里以綠點為中心,以eps為半徑畫圓.可以發(fā)現(xiàn)這個圓(小于或等于半徑)中有兩個粉色點(邊點),并且點的數(shù)量不小于MinPts(2大于等于2),因此它們成為一個簇.圓中的其他點標(biāo)記為粉色(邊點).這樣,遞歸之后,將得到一個大型集群.在圖中,綠色是中心點,粉色是邊緣點.如果仍有一些點未處理,請選擇其中的另一個點以開始生成新簇.算法過程是一樣的.當(dāng)算法執(zhí)行完成時,可能有一個既不是邊緣點也不是中心點的點,例如圖中的紫色點就是這樣的噪音.

如果一個點P是從一個點P到達(dá)的,那么點Q就是從點P直接到達(dá)的密度.如果一個點Q是從一個點P通過一個特定的跳躍到達(dá)的,那么點Q就是從點P到達(dá)的密度.如果點Q是從點P密度到達(dá)的,從點Q密度可以到達(dá)點P,點P和Q被稱為密度連接.上面提到的“跳躍”是指通過的箭頭的數(shù)量,并且只能沿著箭頭的方向前進(jìn).

任務(wù)分發(fā)模型首先根據(jù)任務(wù)地理位置分布,利用密度聚類算法對任務(wù)進(jìn)行子區(qū)域劃分,并利用最短路徑算法[20]計算各地鐵站臺點距離最近的任務(wù)子區(qū)域聚類中心,進(jìn)行任務(wù)分配.

密度聚類的效果與聚類過程中部分參數(shù)的設(shè)置相關(guān),部分密度聚類相關(guān)參數(shù)說明如下:

密度聚類為感知任務(wù)中的同類任務(wù)集合

核心對象:若γj至少包含MinPts個樣本,即|N ∈(γi)|≥MinPts,則γj是子任務(wù)集合.

4.2 聚類區(qū)域覆蓋模型

設(shè)感知平臺對用戶i預(yù)測的可能下車站點集合為S(s1,s2,···,sm),分別對用戶在每個可能站點sj利用OCTDM 算法和ONPTDM算法進(jìn)行多任務(wù)分發(fā),得出該參與者在站點sj的感知任務(wù)集合Ti(t1,t2,···,tn),所需要傳輸?shù)娜蝿?wù)ri的大小為w(ti),用戶在地鐵系統(tǒng)中通過Wi-Fi進(jìn)行傳輸?shù)臅r間為q(q=φ?w(ti)),其中φ為地鐵系統(tǒng)Wi-Fi系統(tǒng)進(jìn)行任務(wù)傳輸?shù)膫鬏斔俾?由于用戶在車廂內(nèi)停留時間有限,所以需要限制qi在上車下車站點之間的停留時間內(nèi).記用戶停留時間為Qi.在此情況下,用戶i在地鐵中可以通過地鐵系統(tǒng)進(jìn)行任務(wù)分發(fā)的任務(wù)數(shù)量為Ni(Ni=Qi/qi),即用戶i在目的站點下車后可最大任務(wù)執(zhí)行量為Ni條.

定理1站點覆蓋.若在某一子區(qū)域范圍內(nèi),存在地鐵站點,則稱該地鐵站點實現(xiàn)了對本子區(qū)域的的覆蓋.對于某一地鐵站點si ∈S和子區(qū)域cj ∈C而言,子區(qū)域被覆蓋情況需要滿足式(3).

根據(jù)以上定義可知,某條地鐵線路S對感知任務(wù)的子區(qū)域覆蓋情況可以用G(S,cj)來表示,如式(4).

并且,對于用戶i下車站點預(yù)測問題,首先用記錄地鐵乘客上車站點位置,用表示預(yù)測得出的地鐵乘客可能的下車站點位置.在模型中,BS為地鐵線路S中Si站點處的實際上車地鐵乘客數(shù)量,所以BS需要在地鐵實際到達(dá)站點s時才可得出.

4.3 多任務(wù)動態(tài)分發(fā)算法

由上述模型描述可知,本任務(wù)動態(tài)分發(fā)方法是一個同時具有兩個優(yōu)化目標(biāo)[21]的NP難問題.無法通過普通算法在多項式時間內(nèi)找到在所有解中的最優(yōu)解,只能通過隨機(jī)搜索、貪心等方法對最優(yōu)解進(jìn)行不斷逼近.所以本文選擇在以其一目標(biāo)作為約束的條件下,分別針對另一優(yōu)化目標(biāo)進(jìn)行優(yōu)化.以參與者個數(shù)作為約束,以用戶激勵成本(移動距離)為優(yōu)化目標(biāo)的OCTDM算法;以及以用戶激勵成本(移動距離)作為參與者選擇約束,以參與任務(wù)用戶數(shù)量作為優(yōu)化目標(biāo)的ONPTDM算法.

4.3.1 最小化用戶數(shù)量的ONPTDM算法

ONPTDM算法是一個將參與者人數(shù)最小化作為首要優(yōu)化目標(biāo)的算法.算法的主要思路是先進(jìn)行任務(wù)的選擇,再在此基礎(chǔ)上進(jìn)行參與者的選擇.對于任務(wù)的選擇,系統(tǒng)會對候選任務(wù)以所需要的人數(shù)進(jìn)行降序排序,不斷將需要人數(shù)最多的任務(wù)加入任務(wù)集合.此方法可以保證在任務(wù)選擇過程中不會出現(xiàn)孤立任務(wù),不會出現(xiàn)無法被選擇到的任務(wù).可以避免傳統(tǒng)研究所用的隨機(jī)選擇算法中某些任務(wù)一直無法被選中的情況.然后將此任務(wù)集合分配至距離該任務(wù)集合最近的參與者,并且該參與者擁有足夠的時間完成該任務(wù)集.

在本多任務(wù)動態(tài)分發(fā)方法中,需要用戶同時參與多個任務(wù),即用戶的位置會根據(jù)不同任務(wù)位置分布不同而不斷變化.由于用戶位置的不斷變化,若無法預(yù)測用戶位置變化的變化軌跡,則很難繼續(xù)對下一個任務(wù)做出選擇.但由于系統(tǒng)已知所需感知的任務(wù)的地理位置分布,所以系統(tǒng)可以根據(jù)任務(wù)位置的分布進(jìn)行組合.確定合適的參與者,選出用戶在時間限制內(nèi)可以完成的最大任務(wù)集合.同時,為了對移動距離進(jìn)行最小化,算法會對任務(wù)集合周邊的參與者進(jìn)行篩選,選擇出一個距離感知地點距離最短的用戶參與任務(wù).本算法選擇出的參與者集合通過了對各參與者執(zhí)行任務(wù)集的優(yōu)化.當(dāng)出現(xiàn)緊急事件,用戶數(shù)量不足時,可以達(dá)到最小化所需用戶數(shù)量的目的,實現(xiàn)了系統(tǒng)基礎(chǔ)成本的最小化.

4.3.2 最小化用戶移動距離的OCTDM算法

在最小化用戶數(shù)量的ONPTDM算法中,因為無需遍歷所有用戶,只需要從任務(wù)集的角度出發(fā),所以可以大大減少計算量.但同樣因為未考慮全部用戶,所以并不能做到針對每個用戶的任務(wù)集合分配最優(yōu)化.因此為了提升用戶的整體性能降低激勵成本,OCTDM算法從用戶的角度出發(fā)進(jìn)行任務(wù)集合的分配.本算法基于貪心算法的思想,在為用戶分配感知任務(wù)過程中,每次都分配距離用戶當(dāng)前地理位置最近的任務(wù).算法不斷獲取當(dāng)前局部最優(yōu)解,使得最終解不斷逼近最優(yōu)解,能夠以較短的距離完成任務(wù).所以從所擁有任務(wù)集合中數(shù)量最多的用戶開始選擇,直到任務(wù)集覆蓋全部任務(wù).

5 實驗評估

5.1 實驗數(shù)據(jù)

地鐵的運營線路信息可以反映該地鐵系統(tǒng)對城區(qū)的覆蓋程度,地鐵站點的主要分布區(qū)域,以此推斷地鐵系統(tǒng)對感知任務(wù)范圍的有效覆蓋,如表1.

表1 地鐵系統(tǒng)路線分布Table 1 Route distribution of metro system

各線路的運營時間信息可以用于用戶停留時間的分析,通過上下車站點可以得出在列車內(nèi)停留的時間,從而得出可用的任務(wù)傳輸時間,如表2.

表2 線路運營時間Table 2 Line operating time

通過對地鐵系統(tǒng)的歷史客運流量的分析,最高客流的分析,可以得出用戶的大體出行規(guī)律以及出行的歷史變化趨勢,并據(jù)此預(yù)測未來出行走勢,使得多任務(wù)分發(fā)方法可以跟隨出行流量的變化進(jìn)行優(yōu)化,如表3.

表3 歷史客運流量Table 3 Historical passenger traffic

并且根據(jù)各線路各列車在不同期間不同的列車數(shù)量,結(jié)合運營間隔,可以得出車輛每小時的最大運載量,如表4.

表4 列車數(shù)量Table 4 Number of trains

根據(jù)表1可知,長沙軌道交通運營線路共3條,共設(shè)車站46座、換乘站1個,運營里程68.71千米.

以上地鐵系統(tǒng)運營相關(guān)特征,結(jié)合用戶相關(guān)出行數(shù)據(jù),即可對地鐵上的乘客行為進(jìn)行模擬.TaxiSet是一個根據(jù)2011年4月到6月北京29000輛出租車[22]的載客記錄建立的乘客出行模擬平臺,可以通過該平臺生成所需要的不同時間段的用戶出行記錄.每一條出行記錄中包括本次出行的出發(fā)點、目的地、出發(fā)時間等參數(shù),結(jié)合高德地圖API可以得出通過市區(qū)地鐵出行所需要乘坐的地鐵路線.這樣就得出了所需的地鐵乘客出行記錄.

并假設(shè)在實驗中每個感知任務(wù)需要3個參與者完成,并且在完成過程中可能需要使用拍照、視頻、文字等記錄方式,所以本文假設(shè)每個人完成每個任務(wù)的時間為5分鐘.為便于計算下地鐵后參與者的移動距離和時間,本問題假設(shè)用戶下地鐵后統(tǒng)一通過步行移動以80米每秒的速度前往感知任務(wù)地點.

5.2 評價指標(biāo)

本文針對該問題提出的基于地鐵交通的多任務(wù)動態(tài)分發(fā)方法主要從兩個角度設(shè)計了一下兩個算法來實現(xiàn),分別是以參與者個數(shù)為約束,用戶激勵成本(移動距離)為優(yōu)化目標(biāo)的OCTDM(optimize cost task distribution model)算法和以用戶激勵成本(移動距離)作為參與者選擇約束,以參與任務(wù)用戶數(shù)量作為優(yōu)化目標(biāo)的ONPTDM(optimize number of people task distribution model)算法.兩種方法分別從兩個不同的優(yōu)化目的出發(fā),對整體感知任務(wù)的參與者選擇問題進(jìn)行優(yōu)化,因此選擇過程、選擇結(jié)果、結(jié)果的優(yōu)劣都會有所不同.所以需要通過實驗分析從多個角度場景對比兩個算法選出的參與者集的性能優(yōu)劣.在本文的該問題中,參與者集合的優(yōu)劣可以通過兩個參數(shù)進(jìn)行比較:參與者的人數(shù)、完成任務(wù)的總移動距離.因此,兩個算法的優(yōu)劣可以通過他們在不同情況場景下選擇出的用戶集合的總?cè)藬?shù)、平均每人任務(wù)數(shù)、總移動距離進(jìn)行評判.對結(jié)果有所影響的外界因素又可以總結(jié)為:總?cè)蝿?wù)個數(shù)、候選用戶人數(shù)、任務(wù)分布情況、任務(wù)發(fā)布時間、任務(wù)緊急程度(任務(wù)限制時間)等等.

對于該感知任務(wù)的用戶總移動距離,由于任務(wù)數(shù)量固定,所以假設(shè)任務(wù)所屬地理位置也是確定的.由于需要完成的總?cè)蝿?wù)是一定的,所以參與者人數(shù)越少,每個參與者所需要移動的距離就越大,本文的分發(fā)中同樣希望用戶集的總移動距離是最短的,但此時參與者人數(shù)與總移動距離呈反比關(guān)系,所以在本文中利用參與者總?cè)藬?shù)與任務(wù)總移動距離的乘積對兩者進(jìn)行綜合評判,該乘積越小系統(tǒng)總績效越好.所以本文中通過實驗比對兩種算法在不同應(yīng)用場景下的人數(shù)、人平均任務(wù)數(shù)、總距離以及總距離和人數(shù)的乘積,來選擇出在不同情況下兩種算法中最優(yōu)的解集合.

在實際的群智感知任務(wù)中,能夠?qū)θ蝿?wù)完成質(zhì)量造成影響的相關(guān)相關(guān)因素有很多,本實驗的主要目的是通過對算法的各影響因素進(jìn)行觀察,分析出主要的影響因素,達(dá)到在實際任務(wù)發(fā)布時可以提前考慮這些影響因素選擇出最佳的算法進(jìn)行參與者選擇.可能對算法選擇出的參與者集合造成影響的因素有總?cè)蝿?wù)個數(shù)、候選用戶人數(shù)、任務(wù)分布情況、任務(wù)發(fā)布時間、任務(wù)限制時間等等.例如當(dāng)其他條件一定的情況下,待完成感知任務(wù)不同的分布,較為集中或較為分散的的任務(wù)情況下,較為分散的任務(wù)分布中所需要選出的參與者人數(shù)更多,總移動距離也更長.所以對于分散式任務(wù)來說,系統(tǒng)可能需要更多的基礎(chǔ)激勵和動態(tài)激勵吸引用戶完成任務(wù),保證任務(wù)完成質(zhì)量.對于不同的任務(wù)發(fā)布時間,白天相對于晚上可以用更少的用戶人數(shù)就可以完成相同數(shù)量的任務(wù),且用戶總移動距離更短.所以可以讓系統(tǒng)盡量在白天進(jìn)行感知任務(wù)的分發(fā).

5.3 實驗結(jié)果

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

任務(wù)動態(tài)分發(fā)算法首先將根據(jù)地鐵在市區(qū)內(nèi)的分布情況以及具體任務(wù)集的地理位置,通過密度聚類對任務(wù)以劃分范圍內(nèi)站點間距為限制進(jìn)行子區(qū)域劃分.由于部分任務(wù)位置過于偏僻和稀疏,本文截取了以五一廣場為中心17 km范圍內(nèi)的任務(wù)目標(biāo),密度聚類過程中聚類半徑1 km(eps=0.01),聚類范圍內(nèi)最少任務(wù)節(jié)點數(shù)為20(min samples=20).對任務(wù)的主要分布區(qū)域和地鐵分布進(jìn)行結(jié)合,繪制任務(wù)分布聚類圖,如圖4所示.分發(fā)系統(tǒng)將對地鐵周邊的任務(wù)區(qū)域進(jìn)行多任務(wù)分發(fā),東北處離地鐵較遠(yuǎn)的區(qū)域采取移動網(wǎng)絡(luò)形式進(jìn)行分發(fā).

圖4 密度聚類過程Fig.4 Density clustering process

5.3.2 任務(wù)個數(shù)的影響

由于不同的任務(wù)數(shù)量將會對任務(wù)的分布、參與者的選擇、算法的分發(fā)過程造成影響.所以本實驗首先將對參與者選擇算法中的總?cè)蝿?wù)個數(shù)的影響進(jìn)行分析,將同時對四種算法進(jìn)行比對分析.并利用參與者人數(shù)、人平均任務(wù)數(shù)、總距離、以及總距離和人數(shù)的乘積對算法結(jié)果進(jìn)行評價.

從圖5(a)中可以看出隨著待分配任務(wù)數(shù)量的增加,無論是ONPTDM算法還是OCTDM算法,為了完成任務(wù)都需要選擇出更多的參與者用于任務(wù)的完成.并且任務(wù)數(shù)量越多,人數(shù)增加的速度越來越快.可以發(fā)現(xiàn)OCTDM算法較Greedy Algorithm選擇出的參與者平均人數(shù)減少了16.5%;以最小化參與者為優(yōu)化目標(biāo)的ONPTDM則較Greedy Algorithm減少了22.1%的用戶數(shù)量;Li等人在2019年提出的Benefit算法主要優(yōu)化目標(biāo)為最大化用戶獲利,所以在改善系統(tǒng)基礎(chǔ)成本方面表現(xiàn)并不突出,僅較Greedy Algorithm降低了5.82%的基礎(chǔ)成本.

表5 不同算法需要的參與者人數(shù)Table 5 Number of participants for different tasks

圖5 待分配任務(wù)數(shù)的影響Fig.5 The impact of the number of tasks to be allocated

在圖5(b)中隨著待分配任務(wù)數(shù)量的增加,多任務(wù)分發(fā)系統(tǒng)為每個任務(wù)參與者所分配到的任務(wù)先增高再降低.可以推測是因為隨著需要完成任務(wù)數(shù)量的增加任務(wù)的分布也越來越分散,每個用戶所分配到的任務(wù)地理位置也越分散,所以在一定時間內(nèi)每個用戶可以完成的任務(wù)更少.Greedy Algorithm的人均任務(wù)數(shù)可以達(dá)到4.42個,OCTDM算法平均每人完成任務(wù)數(shù)可以達(dá)到5.46個.而以最小化用戶數(shù)量為優(yōu)化目標(biāo)的ONPTDM算法可以達(dá)到每人5.89個的任務(wù)分配效果.Benefit算法較Greedy Algorithm算法提高了8.15%的人均任務(wù)數(shù).

在最小化系統(tǒng)成本過程中,當(dāng)在需要完成的任務(wù)數(shù)量一定時,所選的人數(shù)與總移動距離為反比關(guān)系.若希望可以同時對兩個因素進(jìn)行權(quán)衡,則從圖5(d)中兩者的乘積可以看出OCTDM算法可以擁有更低的乘積系數(shù),任務(wù)分發(fā)系統(tǒng)擁有更低的總代價.OCTDM的平均可達(dá)到25.98,ONPTDM可以達(dá)到28.47.LCPSA相比Greedy Algorithm,提升39.26%的性能.

所以圖5(a)(c)中可以看出,在應(yīng)急情況下出現(xiàn)用戶量不足時,ONPTDM算法可以利用最少的參與者數(shù)量保證任務(wù)的完成;當(dāng)任務(wù)不需要緊急完成,優(yōu)先考慮感知系統(tǒng)總成本最小時,OCTDM算法可以對系統(tǒng)的激勵成本和固定成本進(jìn)行最小化,達(dá)到最小化總成本的目的.

表6 不同算法的參與者與距離乘積情況Table 6 Participants and distance of different tasks

6 結(jié)論與展望

本文主要針對短視頻時代移動群智感知存在的問題,移動群智感知任務(wù)的視頻化程度越來越高,在傳統(tǒng)研究中常利用機(jī)會網(wǎng)絡(luò)和移動網(wǎng)絡(luò)激勵任務(wù)的分發(fā)和數(shù)據(jù)的收集,但機(jī)會網(wǎng)絡(luò)中節(jié)點移動的不可控性,以及視頻任務(wù)內(nèi)容傳輸?shù)母叽鷥r性都使得這些方法的實用性大大降低.針對此問題,利用社會移動群體規(guī)律性的自主聚集、活動范圍大等特點,提出一種面向社會移動群體的群智感知參與者選擇優(yōu)化模型.利用密度聚類算法根據(jù)同類任務(wù)的位置進(jìn)行劃分得出聚類中心,實現(xiàn)任務(wù)子區(qū)域所屬地鐵站點的劃分.包括基于用戶激勵成本的參與者優(yōu)化算法和基于用戶數(shù)量的參與者優(yōu)化算法.仿真結(jié)果表明,與同類算法相比可以消耗更低的系統(tǒng)資源選擇出參與者數(shù)量更少的任務(wù)分發(fā)方案.