CrowdTracker：一種基于移動群智感知的目標(biāo)跟蹤方法

景 瑤 郭 斌 陳薈慧 岳超剛 王 柱 於志文

(西北工業(yè)大學(xué)計算機(jī)學(xué)院 西安 710072)

一直以來，公共安全問題是城市生活面臨的一大挑戰(zhàn)，移動目標(biāo)跟蹤技術(shù)作為公共安全領(lǐng)域中的一項重要技術(shù)更是研究者們關(guān)注的熱門課題.城市發(fā)生突發(fā)狀況后，政府和警察常常通過各種數(shù)據(jù)來追蹤可疑車輛和人，其中視頻監(jiān)控是最常用的數(shù)據(jù).現(xiàn)有的對于移動目標(biāo)跟蹤的研究主要基于網(wǎng)絡(luò)視頻監(jiān)控數(shù)據(jù)方式[1-2].該類研究主要針對如何部署攝像頭達(dá)到最大化道路覆蓋以及基于圖像的運動目標(biāo)檢測算法設(shè)計.這種基于網(wǎng)絡(luò)視頻監(jiān)控的方法需要預(yù)先在廣泛的城市區(qū)域內(nèi)部署大量的攝像頭，設(shè)備成本高且覆蓋范圍有限.隨著可內(nèi)嵌多種傳感器的智能手機(jī)的快速普及和應(yīng)用，移動群智感知技術(shù)[3]作為一種新的感知模式逐步發(fā)展起來，它依賴大量普通用戶的移動設(shè)備及其具備的豐富的感知能力來完成大規(guī)模、復(fù)雜的城市與社會感知任務(wù)[4-5].大量的用戶通過智能手機(jī)隨時隨地感知著城市生活的韻律，這為解決城市生活中的公共安全問題帶來了新的思路.人們可以隨時隨地使用智能手機(jī)拍攝視頻、照片，并在一定法律約束范圍內(nèi)作為證據(jù)使用.如果將人們手中的智能手機(jī)看做移動的監(jiān)控攝像頭，那么這就可以實現(xiàn)一種新的基于群智感知的視頻監(jiān)控系統(tǒng).

基于該思路，本文面向目標(biāo)跟蹤問題提出一種基于移動群智感知的解決方案CrowdTracker：通過多人協(xié)作拍照方式實現(xiàn)對移動目標(biāo)的軌跡預(yù)測和跟蹤.本文主要針對移動目標(biāo)中的車輛進(jìn)行群智跟蹤.CrowdTracker的示例如圖1所示.城市發(fā)生公共安全事件后，警察和政府在CrowdTracker平臺上發(fā)布待跟蹤的目標(biāo)車輛信息，包括車輛顏色、型號、車牌號碼等.CrowdTracker平臺上的用戶A在網(wǎng)格區(qū)域n1內(nèi)發(fā)現(xiàn)目標(biāo)車輛，對該車輛拍照并上傳照片信息以及位置信息，啟動對該目標(biāo)的跟蹤任務(wù).CrowdTracker服務(wù)器端通過分析城市中大量的車輛軌跡數(shù)據(jù)，預(yù)測出該目標(biāo)車輛下一步可能往區(qū)域n2移動，并提前在n2內(nèi)通知平臺參與者等待目標(biāo)出現(xiàn).當(dāng)參與者B和C再次發(fā)現(xiàn)目標(biāo)時同樣進(jìn)行拍照并上傳信息，如此循環(huán)，得到目標(biāo)車輛出現(xiàn)過的網(wǎng)格序列n1-n2-n3-n4即為車輛的移動軌跡，最終實現(xiàn)基于群智感知的移動目標(biāo)跟蹤.

Fig. 1 A scenario of CrowdTracker圖1 CrowdTracker示例

為了實現(xiàn)這個目標(biāo)，本文提出了預(yù)測目標(biāo)移動模型的方法MPRE(movement prediction)和任務(wù)分配的方法T-centric，P-centric.MPRE首先通過分析大量的車輛歷史軌跡建立城市里車輛位置的移動概率模型.當(dāng)目標(biāo)出現(xiàn)在城市某位置時，通過該移動模型找到目標(biāo)下一步移動概率最大的位置區(qū)域，進(jìn)而在該區(qū)域內(nèi)預(yù)先安排參與者.本文提出的T-centric和P-centric方法以實現(xiàn)在跟蹤任務(wù)下的參與者優(yōu)選和任務(wù)地點優(yōu)選，要求達(dá)到參與者與任務(wù)地點最佳匹配，使參與者能在一定時間約束內(nèi)到達(dá)指定任務(wù)點的同時，所移動的距離最短，激勵成本最少.T-centric是以任務(wù)為中心的參與者選擇方法，而P-centric是以人為中心的任務(wù)選擇方法.本文通過成都市二環(huán)內(nèi)1個月的出租車軌跡數(shù)據(jù)集對以上3種算法進(jìn)行實驗評估，實驗結(jié)果表明，本文提出的CrowdTracker能有效地實現(xiàn)目標(biāo)實時跟蹤.

1 相關(guān)工作

目前常用的目標(biāo)跟蹤方法主要是通過預(yù)先部署的網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)進(jìn)行[1-2].現(xiàn)有的技術(shù)主要針對如何部署攝像頭達(dá)到最大化道路覆蓋、如何調(diào)用攝像頭來追蹤目標(biāo)以及基于圖像的目標(biāo)檢測算法設(shè)計等[6-8].與傳統(tǒng)的預(yù)先部署固定的網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)不同的是，本文旨在利用群智的思想將人們手中智能手機(jī)的攝像頭看作移動的監(jiān)控攝像頭，提出基于群智的多人協(xié)作拍照的方式對移動目標(biāo)進(jìn)行實時跟蹤.下面就本文的相關(guān)工作進(jìn)行介紹.

1.1 移動群智感知

基于移動群智感知的工作包括數(shù)據(jù)采集、管理、分析到最終提供服務(wù)等.移動群智感知的數(shù)據(jù)包括2種產(chǎn)生方式：移動群智感知和移動社交網(wǎng)絡(luò)數(shù)據(jù).移動群智感知就是利用人們手中的智能手機(jī)感知周邊的信息.比如“哥本哈根車輪”項目在自行車車輪里安裝一些傳感器，并通過用戶手機(jī)將收集的數(shù)據(jù)發(fā)送至后臺服務(wù)器，這樣依靠群體的力量就可以感知整個城市不同角落的溫度、濕度和CO2濃度；利用手機(jī)拍照發(fā)現(xiàn)城市中被污染的河流[9]、損壞的建筑物[10]、感知生活中的社會熱點事件[11]、幫助城市進(jìn)行災(zāi)難救援等[12].與本文工作不同的是，這些感知任務(wù)主要關(guān)注靜態(tài)的目標(biāo).CrowdTracker是利用多人協(xié)作拍照的方式對移動目標(biāo)進(jìn)行實時跟蹤，需要對群智參與者的行為進(jìn)行時間約束，在時間序列下，多個參與者完成拍照任務(wù)的位置序列即為目標(biāo)的移動軌跡.

1.2 移動軌跡預(yù)測

CrowdTracker旨在保證準(zhǔn)確實時地對目標(biāo)進(jìn)行跟蹤的同時盡可能地減少用戶激勵的成本.減少激勵成本首先要縮小跟蹤任務(wù)的范圍，減少參與者數(shù)量.因此需要通過目標(biāo)的當(dāng)前位置信息，預(yù)測目標(biāo)下一步的移動模型.現(xiàn)有的很多研究通過分析城市車輛的軌跡數(shù)據(jù)挖掘車輛移動的規(guī)律，預(yù)測車輛行駛的目的地.Xu等人[13]用純數(shù)據(jù)驅(qū)動的方式分析城市車輛的軌跡數(shù)據(jù)進(jìn)行目的地預(yù)測.與本文工作不同的是，文獻(xiàn)[13]研究的是長距離的最終目的地預(yù)測，本文的移動預(yù)測旨在通過目標(biāo)上一狀態(tài)預(yù)測下一時刻位置狀態(tài).Xue等人[14]和Gambs等人[15]用基于概率模型的Markov鏈進(jìn)行下一站預(yù)測.Xue等人[14]將軌跡序列網(wǎng)格化的思想也為本文工作提供了思路.

1.3 群智感知任務(wù)分配

任務(wù)分配是移動群智感知的關(guān)鍵挑戰(zhàn)之一，如何進(jìn)行任務(wù)分配對數(shù)據(jù)采集的全面性、任務(wù)完成率和數(shù)據(jù)采集質(zhì)量等都具有重要影響.面向移動群智感知的參與者選擇是以物理空間位置為基礎(chǔ)進(jìn)行選擇，任務(wù)的類型分為單個群智感知任務(wù)和多個并發(fā)感知任務(wù)2種.在單任務(wù)分配問題中，Papadias等人[16]研究在已知給定集合點的情況下，尋找其他的點使其到給定集合點的距離最?。籖eddy等人[17]主要研究在考慮空間位置、時間要求以及參與者行為習(xí)慣的情況下，選擇出合適的參與者完成任務(wù)；Cardone等人[18]考慮在參與者個數(shù)一定的情況下，最大限度地提高感知任務(wù)的空間覆蓋范圍.Li等人[19]研究團(tuán)隊形成問題，即尋找一個有特定技能的專家小組，每個人完成一個給定的任務(wù)，同時最小化團(tuán)隊之間的交流成本.Liu等人[20]研究了移動群智感知中面向多任務(wù)并發(fā)的參與者選擇問題，不同于其他參與者選擇問題，該文選擇出的參與者不再局限于只能完成1個任務(wù)，參與者可以在規(guī)定時間內(nèi)盡可能的完成多個任務(wù)，由此降低群智平臺的成本.

本文提出的CrowdTracker首先對目標(biāo)下一步的移動進(jìn)行預(yù)測，然后在預(yù)測的區(qū)域內(nèi)進(jìn)行跟蹤任務(wù)分配.在該區(qū)域內(nèi)的每一個任務(wù)點的任務(wù)是同時進(jìn)行且有時間限制的，每個參與者只能在規(guī)定的時間內(nèi)在1個任務(wù)點等待目標(biāo)的出現(xiàn).因此，本文的任務(wù)分配是一個并發(fā)的單任務(wù)分配問題.針對該問題，CrowdTracker提出了T-centric和P-centric方法實現(xiàn)在跟蹤任務(wù)下的參與者優(yōu)選和任務(wù)地點優(yōu)選，使參與者能在一定時間約束內(nèi)到達(dá)指定任務(wù)點的同時所移動的距離最短.

2 CrowdTracker系統(tǒng)框架

CrowdTracker的系統(tǒng)框架如圖2所示，主要包括客戶端APP和服務(wù)器端2部分.客戶端APP主要用于任務(wù)啟動者和任務(wù)執(zhí)行者采集數(shù)據(jù).服務(wù)器端對客戶端上傳的數(shù)據(jù)進(jìn)行一系列分析處理后通知被選擇的參與者并給出下一步任務(wù)執(zhí)行的指示，保證跟蹤任務(wù)的持續(xù)執(zhí)行.

Fig. 2 The framework of CrowdTracker圖2 CrowdTracker系統(tǒng)框架

圖2中的數(shù)據(jù)采集模塊展示了使用客戶端進(jìn)行數(shù)據(jù)采集的基本流程.城市發(fā)生共公共安全事件后，警察和政府在CrowdTracker平臺上發(fā)布待跟蹤的目標(biāo)車輛信息，包括車輛的顏色、型號和車牌號碼等.CrowdTracker平臺上的用戶在城市某一位置發(fā)現(xiàn)目標(biāo)，立即對其拍攝1張照片用pic來表示.pic中保存了用戶拍照時刻的圖像、GPS位置坐標(biāo)和時間戳等信息，用一個五元組(id,img,lon,lat,t)表示.id是拍照用戶的唯一標(biāo)識,img代表圖像信息，lon和lat分別表示用戶當(dāng)前位置的經(jīng)緯度，也代表了目標(biāo)當(dāng)前的位置信息,t表示拍照時間.上傳該五元組信息至服務(wù)器端，啟動該目標(biāo)的跟蹤任務(wù).服務(wù)器對客戶端發(fā)起的任務(wù)請求分析處理后，給出該跟蹤任務(wù)下一步的計劃，并通知CrowdTracker平臺上被選中執(zhí)行下一步任務(wù)的參與者.參與者按照任務(wù)指示在一定的時間內(nèi)到達(dá)指定任務(wù)地點，等待目標(biāo)出現(xiàn)，在一定時間內(nèi)發(fā)現(xiàn)目標(biāo)后對目標(biāo)進(jìn)行拍照并再次上傳信息，完成該步跟蹤任務(wù).

具體地，CrowdTracker群智跟蹤方法的詳細(xì)內(nèi)容將在第4節(jié)進(jìn)行介紹.

3 群智跟蹤方法實現(xiàn)

圖2中的群智跟蹤方法模塊展示了服務(wù)器端對客戶端上傳的數(shù)據(jù)進(jìn)行分析的基本流程.該模塊主要分為3個部分：目標(biāo)車輛移動預(yù)測模型、群智跟蹤任務(wù)分配以及最終的任務(wù)推送.

3.1 預(yù)測目標(biāo)車輛移動模型

客戶端上傳數(shù)據(jù)中的經(jīng)緯度信息代表了目標(biāo)當(dāng)前的位置.基于該位置信息，預(yù)測目標(biāo)下一步的移動，進(jìn)而有針對性地在預(yù)測的區(qū)域內(nèi)進(jìn)行跟蹤任務(wù)分配，準(zhǔn)確跟蹤目標(biāo)的同時減少平臺的激勵成本.

城市中車輛的移動看似雜亂無序，實則存在潛在的模式.例如上班高峰期的車輛大都由住宅區(qū)流向商業(yè)區(qū)，而下班高峰期的車輛大都由商業(yè)區(qū)流向住宅區(qū).這種規(guī)律對于預(yù)測車輛的移動模型具有一定的意義.本文提出了基于移動Markov鏈(mobility Markov chain, MMC)的MPRE方法來預(yù)測車輛移動.Markov鏈?zhǔn)菙?shù)學(xué)中具有Markov性質(zhì)的離散時間隨機(jī)過程.在該過程中，在給定當(dāng)前知識或信息的情況下，過去(即當(dāng)前以前的歷史狀態(tài))對于預(yù)測將來(即當(dāng)前以后的未來狀態(tài))是無關(guān)的.X1,X2,…描述了Markov鏈中的一種狀態(tài)序列，Xn的值表示在時刻n的狀態(tài)，如果Xn+1對于過去狀態(tài)的條件概率分布僅是Xn的一個函數(shù)，則Xn+1時刻的狀態(tài)見式(1)：

P(Xn+1=x|X1=x1,X2=x2,…,Xn=xn)=
P(Xn+1=x|Xn=xn).

(1)

移動Markov鏈?zhǔn)悄Ｐ突貙⒂脩艋蛘哕囕v等的移動行為轉(zhuǎn)化為一系列離散隨機(jī)過程，如圖3所示，也就是Markov鏈中的狀態(tài)序列{n1,n2,…}，每個狀態(tài)節(jié)點對應(yīng)一個位置區(qū)域.由Markov性質(zhì)可得，從一個狀態(tài)ni到另一個狀態(tài)nj的轉(zhuǎn)移概率Pi j是條件概率，只取決于狀態(tài)ni.利用MMC進(jìn)行下一狀態(tài)預(yù)測時，重要的是獲取轉(zhuǎn)移矩陣的參數(shù)，也就是不同位置狀態(tài)間的移動概率Pi j，式(2)中Ni表示所有包含節(jié)點ni的軌跡數(shù)目,Ni,j表示從節(jié)點ni到nj的軌跡數(shù)目.Ni,j與Ni的商即為轉(zhuǎn)移概率Pi j的值.

(2)

Fig. 3 Mobility Markov chain圖3 移動Markov鏈模型

具體地，基于MMC的思想，本文提出MPRE的方法對車輛的移動進(jìn)行預(yù)測.在進(jìn)行MPRE之前首先對城市區(qū)域進(jìn)行網(wǎng)格化處理，如圖4所示：

Fig. 4 Grid on the example圖4 城市區(qū)域網(wǎng)格化

將城市區(qū)域分為大小為g×g(單位m2)的單元格，每個單元格ni代表MMC中的一個位置狀態(tài).進(jìn)一步，為了更好地發(fā)現(xiàn)城市中車輛的移動規(guī)律，構(gòu)建MMC中各個位置狀態(tài)之間的轉(zhuǎn)移概率矩陣，本文對大量的原始車輛軌跡序列進(jìn)行網(wǎng)格化處理.車輛的原始軌跡信息由一系列時間連續(xù)的GPS點形成，對這些軌跡信息進(jìn)行網(wǎng)格化即判斷每一個GPS點屬于哪一個網(wǎng)格區(qū)域，若連續(xù)時間的GPS點序列在同一網(wǎng)格位置，則記為1個網(wǎng)格位置.最終，網(wǎng)格序列即為軌跡序列Gi={n1,n2,…}.大量軌跡進(jìn)行網(wǎng)格化后得到軌跡序列集合G={G1,G2,…}.同樣地，當(dāng)目標(biāo)出現(xiàn)在城市某位置時，將經(jīng)緯度數(shù)據(jù)轉(zhuǎn)化為網(wǎng)格位置ni.車輛軌跡序列集合G和目標(biāo)位置ni作為MPRE的輸入.MPRE算法具體流程見算法1.

算法1. MPRE.

輸入：軌跡序列集合G、目標(biāo)位置ni；

輸出：Pmax對應(yīng)的位置點nj.

① 基于式(2)，從G中學(xué)習(xí)出各個位置狀態(tài)間的轉(zhuǎn)移矩陣P；

② 逐行搜索矩陣P，定位到目標(biāo)位置ni；

③ 在ni對應(yīng)的行里，查找出轉(zhuǎn)移概率最大的Pmax對應(yīng)的下一步位置nj；

④ 輸出Pmax對應(yīng)的位置點nj,即為目標(biāo)下一步可能移動的位置；

⑤ 結(jié)束.

MPRE通過分析大量的車輛歷史軌跡序列計算出城市各個位置間的的轉(zhuǎn)移概率，遷出位置間的轉(zhuǎn)移概率矩陣P=(Pi j).如圖4所示，當(dāng)目標(biāo)出現(xiàn)在城市某位置n5時，搜索矩陣P，找到目標(biāo)下一步移動概率最大P56對應(yīng)的位置區(qū)域n6，即為目標(biāo)下一步可能移動的位置，進(jìn)而在該區(qū)域內(nèi)預(yù)先安排參與者.

3.2 群智跟蹤任務(wù)分配方法

通過預(yù)測車輛移動模塊中的MPRE方法確定出目標(biāo)下一步移動的位置范圍，在該區(qū)域內(nèi)預(yù)先安排參與者.每一個區(qū)域內(nèi)都有多條路，且1條路覆蓋一定的范圍，如何在1條路上進(jìn)行任務(wù)地點選擇是首先需要思考的問題.分析路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，路網(wǎng)是由多條路連接形成，而每條路是由路網(wǎng)節(jié)點(起始點、終止點)連接形成，路網(wǎng)節(jié)點就是形成整個道路網(wǎng)絡(luò)的關(guān)鍵位置.因此，本文考慮將OpenStreetMap路網(wǎng)數(shù)據(jù)中的節(jié)點數(shù)據(jù)作為1條路上的任務(wù)點，達(dá)到最大化道路覆蓋.在此基礎(chǔ)上，本文提出T-centric和P-centric方法以實現(xiàn)在跟蹤任務(wù)下的參與者優(yōu)選和任務(wù)地點優(yōu)選，使參與者能在一定時間約束內(nèi)到達(dá)指定任務(wù)點的同時所移動的距離最短.T-centric是以任務(wù)為中心的參與者選擇方法，而P-centric是以人為中心的任務(wù)選擇方法.

對于每一步跟蹤任務(wù)T，即1個網(wǎng)格內(nèi)的任務(wù)分配問題定義如下：城市網(wǎng)格化的步長為g(單位m)，每個g×g(單位m2)的網(wǎng)格內(nèi)的路網(wǎng)節(jié)點數(shù)量為s，則設(shè)定s個并發(fā)任務(wù)T={t1,t2,…,ts}.每個任務(wù)ti需要1個人來完成，任務(wù)的位置為lti，每個網(wǎng)格的候選者集合C={c1,c2,…,cj,…}，候選者的位置為lci.ui表示完成任務(wù)ti的參與者，完成任務(wù)ti的參與者ui需要移動的距離為di(見式(3))，完成1步跟蹤任務(wù)T，所有參與者所移動的總距離為DT.假設(shè)每個用戶移動平均速度為Vu(單位mmin)，城市中車輛移動的平均速度為Vc(單位mmin).該問題的目標(biāo)函數(shù)是安排參與者與任務(wù)的最佳匹配，使參與者能在一定時間約束內(nèi)(目標(biāo)進(jìn)入網(wǎng)格區(qū)域之前)到達(dá)指定任務(wù)點的同時所移動的距離di最短，即所有參與者移動的總距離DT最短(見式(4))，時間約束見式(5).具體地，針對該任務(wù)分配問題，考慮系統(tǒng)的2個核心要素任務(wù)和人，分別提出以任務(wù)為中心的參與者選擇方法T-centric和以人為中心的任務(wù)選擇方法P-centric.

di=|lti-lci|，

(3)

(4)

滿足

(5)

3.2.1 T-centric任務(wù)分配算法

T-centric是以任務(wù)為中心的參與者選擇方法，采用貪心啟發(fā)算法的思想.首先在任務(wù)集合T中隨機(jī)選擇1個任務(wù)作為初始任務(wù)，然后從侯選者集合C中選出滿足時間約束的參與者集合.若該參與者集合為空，則表明沒有能夠完成該任務(wù)的參與者；若不為空，則存在能夠完成該任務(wù)的參與者，進(jìn)一步在該參與者集合中選出與任務(wù)點距離最短的參與者，形成1個參與者與任務(wù)點的最佳匹配.在原任務(wù)集合以及候選參與者集合中剔除掉已經(jīng)形成匹配的參與者和任務(wù)，接著對下一個任務(wù)進(jìn)行參與者選擇，以此類推，按照該方法，直到任務(wù)集合中的每一個任務(wù)都找到1個最佳的參與者.詳見算法2.

算法2. T-centric.

輸入：任務(wù)集合T、候選參與者集合C；

輸出：能被覆蓋的任務(wù)點集合t以及相應(yīng)的參與者集合u.

① 隨機(jī)選取初始任務(wù)ti；

③ 若集合ui.為空，則該任務(wù)點無法被覆蓋；若|ui.|≥1,則在該集合中選擇離任務(wù)距離最近的參與者ui覆蓋該任務(wù)點；

④ 在任務(wù)集合T中剔除ti，在參與者集合C中剔除ui對應(yīng)的ci；

⑤ 在剩余任務(wù)集合中隨機(jī)選取任務(wù)ti+1；

⑥ 循環(huán)執(zhí)行②～⑤步，直至所有任務(wù)執(zhí)行完；

⑦ 輸出能被覆蓋的所有任務(wù)點ti以及相應(yīng)的參與者ui；

⑧ 結(jié)束.

3.2.2 P-centric任務(wù)分配算法

P-centric是以人為中心的任務(wù)選擇方法.首先在候選參與者集合C中隨機(jī)選擇1個參與者，然后從任務(wù)集合T中選擇出該參與者能在一定時間約束內(nèi)到達(dá)的任務(wù)集合.若該任務(wù)集合為空，則表明該參與者沒有能力完成任何一個任務(wù)；若不為空，則存在能夠完成的任務(wù)，進(jìn)一步在該任務(wù)集合中選出與參與者距離最短的任務(wù)，形成1個參與者與任務(wù)點的最佳匹配.在原任務(wù)集合以及候選參與者集合中剔除掉已經(jīng)形成匹配的參與者和任務(wù)，接著對下一個參與者進(jìn)行任務(wù)選擇，以此類推，按照該方法，直到對于參與者集合中的每一個人都找到最佳的任務(wù)點，詳見算法3.

算法3. P-centric.

輸入：任務(wù)集合T、候選參與者集合C；

輸出：能被覆蓋的任務(wù)點集合t以及相應(yīng)的參與者集合c.

① 隨機(jī)選取候選參與者集合C中的1個ci；

③ 若集合ti.為空，則該用戶無法覆蓋任何任務(wù)點；若|ti.|≥1,則在該集合中選擇離參與者距離最近的任務(wù)點ti去完成；

④ 在候選參與者集合中剔除ci，在任務(wù)集合T中剔除ti；

⑤ 在剩余的候選參與者集合中隨機(jī)選取參與者ci+1；

⑥ 循環(huán)執(zhí)行②～⑤步，直至所有任務(wù)執(zhí)行完；

⑦ 輸出能被覆蓋的所有任務(wù)點ti以及相應(yīng)的參與者ci；

⑧ 結(jié)束.

4 實驗評估

本文提出的基于群智的多人協(xié)作拍照方式實現(xiàn)對移動目標(biāo)的實時跟蹤，旨在保證準(zhǔn)確實時地對目標(biāo)進(jìn)行跟蹤的同時盡可能地減少用戶激勵的成本.為了實現(xiàn)這個目標(biāo)，提出了預(yù)測目標(biāo)移動模型的方法MPRE和任務(wù)分配的方法T-centric和P-centric.本節(jié)分別對每一個方法進(jìn)行實驗驗證.

4.1 MPRE方法評估

為了驗證MPRE方法的精度，本文對成都市的出租車軌跡數(shù)據(jù)進(jìn)行了分析.表1展示了實驗數(shù)據(jù)集的基本統(tǒng)計信息.本文選取了1個月內(nèi)成都市二環(huán)內(nèi)13 605輛出租車從6點到23點的GPS點序列.原始數(shù)據(jù)中包含車輛ID、經(jīng)緯度、載客狀態(tài)(1表示載客，0表示空車)以及時間戳信息.根據(jù)原始軌跡數(shù)據(jù)中車輛載客狀態(tài)的變化，將每輛車1天內(nèi)連續(xù)的GPS點分割為多條軌跡.當(dāng)車輛狀態(tài)由0變?yōu)?則表明一條軌跡的開始，車輛狀態(tài)由1變?yōu)?則表明這條軌跡結(jié)束.將城市區(qū)域分為大小為g×g(單位m2)的單元格，對每一條原始車輛軌跡進(jìn)行網(wǎng)格化，總共有大約4 010 960條軌跡，其中104條軌跡用于測試集，其余用做組建訓(xùn)練集.從訓(xùn)練集中學(xué)習(xí)出各個位置狀態(tài)間的轉(zhuǎn)移矩陣P.1條測試軌跡Gi={n1,n2,…}總共有|Gi|個位置狀態(tài)，對于除了最后一個位置狀態(tài)外的每一個ni，從轉(zhuǎn)移矩陣中得到概率最高的位置即為MPRE預(yù)測的下一位置.對于這條測試軌跡，預(yù)測正確的位置狀態(tài)數(shù)量mi占軌跡中|Gi|-1個位置數(shù)量的比率即為MPRE對該條軌跡預(yù)測的正確率.所有測試軌跡的正確率求平均得到MPRE預(yù)測的正確率Acc為

(6)

Table 1 Taxi Trajectory Dataset in Chengdu表1 成都市出租車軌跡實驗數(shù)據(jù)集

Fig. 5 The result of MPRE圖5 MPRE結(jié)果

圖5展示了不同測試集、不同網(wǎng)格步長情況下的實驗結(jié)果.由于大量的訓(xùn)練集更能反映整體數(shù)據(jù)的規(guī)律，在同一網(wǎng)格粒度下，訓(xùn)練集數(shù)量越多，可能MPRE的準(zhǔn)確率越高.本文首先設(shè)置了4個不同大小的訓(xùn)練集.訓(xùn)練集1中有106條軌跡數(shù)據(jù)，訓(xùn)練集2有2×106條，訓(xùn)練集3有3×106條，訓(xùn)練集4中有4×106條軌跡數(shù)據(jù).在同一訓(xùn)練集下，改變網(wǎng)格粒度，對104條軌跡數(shù)據(jù)進(jìn)行測試.一方面，1個粗的網(wǎng)格粒度(例如g=500 m)，由于每個網(wǎng)格覆蓋的面積較大，可能會使預(yù)測精度降低.另一方面，由于覆蓋面積大，訓(xùn)練數(shù)據(jù)中更多的原始GPS軌跡點會落入相同的網(wǎng)格區(qū)域，匹配到的軌跡數(shù)目可能更高，從而提高M(jìn)PRE的準(zhǔn)確率.因此，需要找到一個平衡的網(wǎng)格粒度使得MPRE的準(zhǔn)確率達(dá)到最佳.圖5中的實驗結(jié)果表明，隨著數(shù)據(jù)量的增加，MPRE的準(zhǔn)確率越來越高.在訓(xùn)練集4中，網(wǎng)格粒度在g=200 m和g=400 m下表現(xiàn)出較高的預(yù)測準(zhǔn)確率，能達(dá)到70%左右.對比MPRE算法在2種粒度下的運行時間，越細(xì)粒度的網(wǎng)格，網(wǎng)格數(shù)量越多，算法的時間復(fù)雜度越高.因此，綜合考慮下本文選擇g=400 m的網(wǎng)格粒度，以下的實驗如果沒有特別說均在g=400 m的網(wǎng)格粒度下進(jìn)行.

4.2 任務(wù)分配的方法評估

通過預(yù)測車輛移動模塊中的MPRE方法確定出目標(biāo)下一步移動的位置范圍，在該區(qū)域內(nèi)預(yù)先安排參與者.在進(jìn)行任務(wù)分配之前，首先，確定區(qū)域內(nèi)的任務(wù)位置.本文從OpenStreetMap中得到成都市路網(wǎng)數(shù)據(jù)，將路網(wǎng)數(shù)據(jù)中的節(jié)點作為一條路上的任務(wù)點.其次，確定用戶位置.本文有成都市出租車的載客狀態(tài)數(shù)據(jù)，考慮到出租車由載客狀態(tài)1轉(zhuǎn)變?yōu)榭哲嚑顟B(tài)0則表明該位置有乘客下車，即可以認(rèn)為該位置有用戶.因此，本文使用出租車載客狀態(tài)發(fā)生變化時的位置作為候選參與者的位置.本文提出了T-centric和P-centric方法以在網(wǎng)格內(nèi)進(jìn)行參與者和任務(wù)點的優(yōu)選.T-centric是以任務(wù)為中心進(jìn)行參與者選擇，而P-centric是以人為中心進(jìn)行任務(wù)的選擇.2種方法的解決思路不同，選出的參與者與任務(wù)的最佳匹配也不同，因此需要通過實驗驗證2種方法的性能.為了降低CrowdTracker平臺的用戶激勵成本，在任務(wù)分配中要求參與者能在一定時間約束內(nèi)到達(dá)指定任務(wù)點的同時所移動的距離最短.因此對比2種方法所選出的參與者的平均移動距離.在任務(wù)個數(shù)以及參與者人數(shù)一定的情況下，選出的參與者與任務(wù)的最佳匹配數(shù)量越多，說明能夠完成的任務(wù)越多.因此，另一個需要對比的指標(biāo)是任務(wù)的覆蓋率.最后針對該問題選擇出性能較好的算法.

以下的實驗均在400 m×400 m的網(wǎng)格粒度下進(jìn)行(g=400 m).由于該實驗主要研究不同地點的任務(wù)對參與者選擇的影響，所以希望保持每個參與者完成任務(wù)的移動方式相同，即本文認(rèn)為參與者都是通過步行的方式完成任務(wù)，每個參與者移動的速度為60 mmin即Vu=60 mmin，車輛移動的平均速度是30 kmh即Vc=500 mmin，則參與者要在(單位min)的時間約束內(nèi)能到達(dá)任務(wù)地點，即參與者與任務(wù)的距離約束在48 m以內(nèi).考慮到實驗的準(zhǔn)確性，以下的實驗數(shù)據(jù)都是通過多次實驗平均而來.

在任務(wù)分配問題中，有2個因素對分配結(jié)果影響較大.一個是任務(wù)個數(shù)，另一個是候選者人數(shù).由于路網(wǎng)中節(jié)點的數(shù)量和位置是一定的，也就是說任務(wù)的個數(shù)以及任務(wù)地點是一定的，因此本次實驗主要研究不同候選參與者人數(shù)下的2種算法的性能.將成都市二環(huán)內(nèi)10 km×10 km范圍(625個網(wǎng)格)的1 017個路網(wǎng)節(jié)點作為任務(wù)地點.保持其他因素不變，將完成任務(wù)的時間設(shè)為10:00—10:10，對于這625個網(wǎng)格中的每一個網(wǎng)格，以該段時間出現(xiàn)在區(qū)域內(nèi)的用戶為候選者，所有網(wǎng)格總共有40 700個候選者.改變候選者人數(shù)的總量，在每一個網(wǎng)格區(qū)域內(nèi)進(jìn)行任務(wù)分配，最終對每個網(wǎng)格得到一系列參與者與任務(wù)地點的最佳匹配.每個網(wǎng)格內(nèi)任務(wù)的覆蓋率定義為形成最佳匹配的任務(wù)點的個數(shù)與該網(wǎng)格所有任務(wù)點數(shù)量的比值，對所有網(wǎng)格的任務(wù)完成率求均值得到平均任務(wù)完成率.對所有參與者完成任務(wù)所移動的距離DT求均值得到平均移動距離，平均移動距離越小，CrowdTracker平臺用戶激勵成本越小.

Fig. 6 Average task coverage圖6 候選參與者人數(shù)與平均任務(wù)覆蓋率的關(guān)系

圖6展示了候選參與者人數(shù)與平均任務(wù)覆蓋率的關(guān)系.實驗結(jié)果表明，隨著候選參與者人數(shù)的增加，T-centric和P-centric的平均任務(wù)覆蓋率均呈現(xiàn)增長趨勢.該結(jié)果說明了群智任務(wù)中的一個典型問題，在一定程度上，參與者人數(shù)的多少決定了群智任務(wù)的完成率.對比2種算法的結(jié)果，同等參與者人數(shù)下，P-centric比T-centric的任務(wù)覆蓋率相對較高，但差別不是很大.圖7展示了算法對參與者平均移動距離的影響，明顯看出，同等參與者人數(shù)下，P-centric比T-centric的平均移動距離大.本文研究的問題中，候選參與者的人數(shù)比任務(wù)的數(shù)量多，P-centric是以人為中心去選擇在時間約束內(nèi)且距離最近的任務(wù)，對于參與者來說選出的任務(wù)是距離其最近的，但是對于任務(wù)來說選出的參與者不一定是最近的，因此，P-centric的移動距離較大.但是在算法運行時間上如圖8所示，同樣的原因，由于候選參與者的人數(shù)比任務(wù)的數(shù)量要多，T-centric在以任務(wù)為中心選擇參與者時需要計算的參與者數(shù)據(jù)量大，計算時間長.因此，針對本文的問題，為了更好地反映算法的性能，以參與者平均移動距離與計算時間的乘積大小作為衡量算法性能的指標(biāo)，乘積越小，算法性能越好.如圖9所示，P-centric比T-centric的平均乘積小，P-centric以人為中心的方法更適合本文的任務(wù)分配問題.

Fig. 7 Average traveled distance圖7 算法對參與者平均移動距離的影響

Fig. 8 Running time圖8 算法運行時間對比

Fig. 9 The product of average distance traveled and running time圖9 算法參與者平均移動距離與計算時間的乘積對比

5 總結(jié)與展望

本文主要研究了基于移動群智感知的目標(biāo)跟蹤，提出了一種新的解決方案CrowdTracker：通過基于群智的多人協(xié)作拍照方式實現(xiàn)對移動目標(biāo)的實時跟蹤.CrowdTracker在保證準(zhǔn)確實時地對目標(biāo)進(jìn)行跟蹤的同時盡可能地減少用戶激勵的成本.為了實現(xiàn)這個目標(biāo)，本文提出了預(yù)測目標(biāo)移動模型的方法MPRE和任務(wù)分配的方法T-centric，P-centric.T-centric是以任務(wù)為中心的參與者選擇方法，而P-centric是以人為中心的任務(wù)選擇方法.MPRE首先通過分析大量的車輛歷史軌跡建立城市里車輛位置的移動模型，進(jìn)而預(yù)測移動目標(biāo)下一步的位置范圍，在該位置范圍內(nèi)通過T-centric或P-centric方法進(jìn)行跟蹤任務(wù)分配.最后，通過大規(guī)模的真實數(shù)據(jù)集對3種算法進(jìn)行實驗評估，綜合考慮實驗結(jié)果，MPRE在g=400 m的網(wǎng)格粒度下能保證預(yù)測準(zhǔn)確率較高且算法運行時間較短，因此本文選擇在g=400 m的網(wǎng)格粒度下分配跟蹤任務(wù).結(jié)果表明以人為中心的任務(wù)選擇方法P-centric更適合本文提出的跟蹤任務(wù)分配問題，保證任務(wù)覆蓋率的同時用戶激勵成本較小且算法的運行時間更短，能有效地實現(xiàn)目標(biāo)實時跟蹤.

未來的工作主要包括2方面：1)考慮基于固定部署攝像頭與基于移動群智感知的目標(biāo)跟蹤方法相結(jié)合，更好地利用城市中現(xiàn)有的資源，降低目標(biāo)跟蹤的成本；2)要結(jié)合圖像處理方法來輔助用戶快速定位目標(biāo)，降低用戶參與負(fù)擔(dān).