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

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

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

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

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

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

1 相關工作

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

1.1 移動群智感知

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

1.2 移動軌跡預測

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

1.3 群智感知任務分配

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

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

2 CrowdTracker系統(tǒng)框架

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

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

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

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

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

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

3.1 預測目標車輛移動模型

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

城市中車輛的移動看似雜亂無序，實則存在潛在的模式.例如上班高峰期的車輛大都由住宅區(qū)流向商業(yè)區(qū)，而下班高峰期的車輛大都由商業(yè)區(qū)流向住宅區(qū).這種規(guī)律對于預測車輛的移動模型具有一定的意義.本文提出了基于移動Markov鏈(mobility Markov chain, MMC)的MPRE方法來預測車輛移動.Markov鏈是數(shù)學中具有Markov性質的離散時間隨機過程.在該過程中，在給定當前知識或信息的情況下，過去(即當前以前的歷史狀態(tài))對于預測將來(即當前以后的未來狀態(tài))是無關的.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鏈是模型化地將用戶或者車輛等的移動行為轉化為一系列離散隨機過程，如圖3所示，也就是Markov鏈中的狀態(tài)序列{n1,n2,…}，每個狀態(tài)節(jié)點對應一個位置區(qū)域.由Markov性質可得，從一個狀態(tài)ni到另一個狀態(tài)nj的轉移概率Pi j是條件概率，只取決于狀態(tài)ni.利用MMC進行下一狀態(tài)預測時，重要的是獲取轉移矩陣的參數(shù)，也就是不同位置狀態(tài)間的移動概率Pi j，式(2)中Ni表示所有包含節(jié)點ni的軌跡數(shù)目,Ni,j表示從節(jié)點ni到nj的軌跡數(shù)目.Ni,j與Ni的商即為轉移概率Pi j的值.

(2)

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

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

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

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

算法1. MPRE.

輸入：軌跡序列集合G、目標位置ni；

輸出：Pmax對應的位置點nj.

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

② 逐行搜索矩陣P，定位到目標位置ni；

③ 在ni對應的行里，查找出轉移概率最大的Pmax對應的下一步位置nj；

④ 輸出Pmax對應的位置點nj,即為目標下一步可能移動的位置；

⑤ 結束.

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

3.2 群智跟蹤任務分配方法

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

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

di=|lti-lci|，

(3)

(4)

滿足

(5)

3.2.1 T-centric任務分配算法

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

算法2. T-centric.

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

輸出：能被覆蓋的任務點集合t以及相應的參與者集合u.

① 隨機選取初始任務ti；

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

④ 在任務集合T中剔除ti，在參與者集合C中剔除ui對應的ci；

⑤ 在剩余任務集合中隨機選取任務ti+1；

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

⑦ 輸出能被覆蓋的所有任務點ti以及相應的參與者ui；

⑧ 結束.

3.2.2 P-centric任務分配算法

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

算法3. P-centric.

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

輸出：能被覆蓋的任務點集合t以及相應的參與者集合c.

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

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

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

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

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

⑦ 輸出能被覆蓋的所有任務點ti以及相應的參與者ci；

⑧ 結束.

4 實驗評估

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

4.1 MPRE方法評估

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

(6)

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

Fig. 5 The result of MPRE圖5 MPRE結果

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

4.2 任務分配的方法評估

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

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

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

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

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

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

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

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

5 總結與展望

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

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