城域級視頻智能卡口規(guī)劃布局方法

程峰 潘飛 劉純 陳瀟 湖北省武漢市公安局

一、視頻卡口規(guī)劃關(guān)鍵問題

經(jīng)過多年建設(shè)，各地視頻卡口基礎(chǔ)設(shè)施不斷完善，但是，當(dāng)前仍然面臨兩個方面的問題。一是建多少，二是建在哪（或如何優(yōu)化、如何更新升級）。傳統(tǒng)的“圈、塊、格、點(diǎn)”布局思路雖然給出了定性的原則，但經(jīng)驗(yàn)、主觀性較強(qiáng)，無法定量給出答案。

不同于文獻(xiàn)[1]所述的過程覆蓋方法，本文所述規(guī)劃布局的目標(biāo)是在最大限度消除偵查對象軌跡不確定性的前提下，最小化視頻卡口的部署數(shù)量。鑒于軌跡不確定性主要來源于道路分叉，本文以道路分叉口作為基本節(jié)點(diǎn)，以路網(wǎng)為基礎(chǔ)分析網(wǎng)絡(luò)。偵查對象每次被智能卡口捕獲，其軌跡不確定性即被消除，故已部署智能卡口的節(jié)點(diǎn)可視為路網(wǎng)上的陷阱節(jié)點(diǎn)。在含有陷阱節(jié)點(diǎn)的網(wǎng)絡(luò)上，從任意一點(diǎn)出發(fā)，首次抵達(dá)任一陷阱節(jié)點(diǎn)的時間期望稱為平均首達(dá)時間（MFPT）[2]，為便于理解，本文中后續(xù)部分統(tǒng)稱為平均捕獲時間。顯然，網(wǎng)絡(luò)中的陷阱節(jié)點(diǎn)越多，偵查目標(biāo)不確定性越小。同時，陷阱節(jié)點(diǎn)布局越合理（處于對象大概率經(jīng)過的路徑上），平均捕獲時間也越小。因此本文以平均捕獲時間作為點(diǎn)位布局的主要評價指標(biāo)。

綜上所述，規(guī)劃布局可抽象為如下目標(biāo)優(yōu)化問題，即：

給定網(wǎng)絡(luò)平均捕獲時間，求點(diǎn)位規(guī)劃，使得網(wǎng)絡(luò)布點(diǎn)總數(shù)最少。或者給定點(diǎn)位總數(shù)量，求點(diǎn)位規(guī)劃，使得網(wǎng)絡(luò)平均捕獲時間最小。

由于上述兩個問題互為對偶問題，本文下述部分將著重闡述問題1的求解方法。

具體來說，以道路分叉點(diǎn)為候選部署節(jié)點(diǎn)，記為ci，二元決策變量xi表示候選節(jié)點(diǎn)是否被選中為卡口部署點(diǎn)，即陷阱節(jié)點(diǎn)。當(dāng)候選節(jié)點(diǎn)被選中為卡口部署點(diǎn)時，xi=1，否則xi= 0。以Tmfpt表 示網(wǎng)絡(luò)平均捕獲時間，Tc表 示網(wǎng)絡(luò)平均捕獲時間的設(shè)計(jì)目標(biāo)值，則優(yōu)化目標(biāo)函數(shù)為：

求解上述問題，需明確網(wǎng)絡(luò)的基本性質(zhì)以及偵查對象的普遍動力學(xué)規(guī)律。為此，本文接下來內(nèi)容組織如下：第2章分析視頻偵查視角下城市路網(wǎng)的基本性質(zhì)，揭示其高度的非均勻性，具備對其進(jìn)行“切塊分格”的基礎(chǔ)條件；第3章證明了在復(fù)雜城域級路網(wǎng)條件下，無偏隨機(jī)游走與Levy flight模型具有相似性，具備對一般運(yùn)動目標(biāo)的普適描述能力，并以無偏隨機(jī)游走作為本文的目標(biāo)運(yùn)動動力學(xué)模型；第4章以馬爾可夫無偏隨機(jī)游走步數(shù)為尺度，對不同尺度網(wǎng)絡(luò)社團(tuán)進(jìn)行分割，并以穩(wěn)定性為條件，給出優(yōu)選穩(wěn)定分割的方法；第5章在前述基礎(chǔ)上，基于網(wǎng)絡(luò)多陷阱吸收模型，提出具體關(guān)鍵節(jié)點(diǎn)的定位思路及具體求解方法；第6章以某市為例，進(jìn)行布點(diǎn)規(guī)劃，并通過模擬計(jì)算實(shí)驗(yàn)驗(yàn)證了前述模型、算法的可行性和有效性。

二、視頻偵查視角下的路網(wǎng)性質(zhì)

文獻(xiàn)[3]指出波士頓公交網(wǎng)絡(luò)存在小世界特性，文獻(xiàn)[4]對城市路網(wǎng)進(jìn)行分析，指出其具備小世界特性，在此基礎(chǔ)上，文獻(xiàn)[5-7]分別研究了國內(nèi)部分城市的路網(wǎng)結(jié)構(gòu)。但是均是以道路本身作為路網(wǎng)的基本結(jié)構(gòu)單元，以道路之間的關(guān)聯(lián)關(guān)系為邊，與本文研究方向不符。因此，本文以導(dǎo)致目標(biāo)軌跡發(fā)散的道路交叉口為網(wǎng)絡(luò)節(jié)點(diǎn)，以交叉口之間的道路連接為邊，構(gòu)建路網(wǎng)拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[8]中指出，現(xiàn)已成型的城市道路體系可歸納為四種形式，分別是方格網(wǎng)式、自由式、環(huán)形放射式和混合式，其中又以方格網(wǎng)式最為常見。整體來看，網(wǎng)絡(luò)接近于規(guī)則網(wǎng)絡(luò)。圖1為某市路網(wǎng)圖，其中左圖為路網(wǎng)拓?fù)?，可以看到整體具備明顯的規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)，右圖為網(wǎng)絡(luò)節(jié)點(diǎn)度分布圖，具備高斯分布的特性，網(wǎng)絡(luò)節(jié)點(diǎn)的平均度為2.84，大量節(jié)點(diǎn)的度為2~4之間，即常見的路口拐彎處、丁字路口和十字路口。

對于規(guī)則網(wǎng)絡(luò)，節(jié)點(diǎn)分布均勻，網(wǎng)絡(luò)聚類系數(shù)低，平均最短路徑長度大。圖1所示的某市路網(wǎng)，具備顯著的規(guī)則網(wǎng)絡(luò)特性，聚類系數(shù)為0.06，網(wǎng)絡(luò)直徑為175，平均路徑長度為46.6，內(nèi)部連接稠密、邊界連接稀疏的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)特征整體不明顯。

但同時應(yīng)注意到，偵查目標(biāo)一旦搭乘巴士、地鐵等公共交通工具，會發(fā)生目標(biāo)直接從起點(diǎn)，在不被任何卡口捕獲的條件下，直接出現(xiàn)在另一任意站點(diǎn)的現(xiàn)象。從而導(dǎo)致在路網(wǎng)中本無關(guān)聯(lián)的節(jié)點(diǎn)對成為鄰居節(jié)點(diǎn)，直接改變原網(wǎng)絡(luò)中的網(wǎng)絡(luò)鄰接和距離關(guān)系。

因此，本文將公共交通數(shù)據(jù)以space P方法[9]加入路網(wǎng)中，形成視頻偵查視角下的路網(wǎng)拓?fù)浣Y(jié)構(gòu)。由于公共交通網(wǎng)絡(luò)本身具備小世界特性，加入路網(wǎng)后，等價于為規(guī)則網(wǎng)絡(luò)增加了長程鏈接，根據(jù)文獻(xiàn)[10]，合并后的路網(wǎng)將具備小世界特性。圖2所示為合并后的路網(wǎng)及其節(jié)點(diǎn)度分布，可以觀察到冪律分布特性。融合前后網(wǎng)絡(luò)關(guān)鍵指標(biāo)對比如表1所示，與之前相比，網(wǎng)絡(luò)聚類系數(shù)明顯提升，平均路徑長度顯著減小，具備形成網(wǎng)絡(luò)社團(tuán)并進(jìn)而對其網(wǎng)絡(luò)進(jìn)行分格切塊的基礎(chǔ)。

?

三、復(fù)雜路網(wǎng)中的目標(biāo)運(yùn)動模型

無偏隨機(jī)游走是在任意維度的空間中，一個點(diǎn)隨機(jī)地向任意方向前進(jìn)任意長度的矩離，然后反復(fù)這個過程。Levy flight是隨機(jī)游走的一種，它的每一步方向完全隨機(jī)而各向同性，但步長的分布是重尾分布。近年來，有相當(dāng)多的研究表明很多動物的移動模式可以用Levy flight來描述，甚至人類的移動模式也和Levy flight高度吻合[11,12]。圖3所示為布朗隨機(jī)游走與Levy flight隨機(jī)游走的軌跡[13]，其中Levy flight隨機(jī)游走表現(xiàn)為目標(biāo)在一個局域范圍內(nèi)進(jìn)行反復(fù)徘徊后，往往伴隨一個長距離的跳躍，然后再度進(jìn)入一個局域范圍內(nèi)的徘徊，與平時偵查工作經(jīng)驗(yàn)基本一致。

由文中第2章路網(wǎng)構(gòu)造方式可知，在每一步隨機(jī)游走過程中，下一步跳躍步長為s的概率與節(jié)點(diǎn)本身的度密切相關(guān)。當(dāng)節(jié)點(diǎn)的度為1~4之間時，為網(wǎng)絡(luò)的普通路口節(jié)點(diǎn)，只可能游走到下一個路口，不存在遠(yuǎn)距離跳躍的情況。當(dāng)節(jié)點(diǎn)的度較大時，節(jié)點(diǎn)為車站等中樞節(jié)點(diǎn)，可以在站點(diǎn)之間進(jìn)行遠(yuǎn)距離跳躍。根據(jù)城市交通一般規(guī)劃，站點(diǎn)呈線性或者環(huán)形、網(wǎng)狀分布。給定站點(diǎn)數(shù)量，在線性分布條件下，跳躍距離最遠(yuǎn)，網(wǎng)狀分布條件下，跳躍距離最近。則復(fù)雜路網(wǎng)上無偏隨機(jī)游走下一步行走步長為s的概率滿足：

其中，

Pd為網(wǎng)絡(luò)節(jié)點(diǎn)的度分布概率。由第2章可知，網(wǎng)絡(luò)節(jié)點(diǎn)度滿足冪律分布，即：

式（4）、（5）均為p級數(shù)，無法求取顯式表達(dá)式，但是根據(jù)式（3）、（4）、（6）可知：

根據(jù)式（3）、（5）、（6）可知：

因此，根據(jù)式（3）、（7）、（8），有：

由此可知P(s)具備重尾分布特征，復(fù)雜路網(wǎng)上的無偏隨機(jī)游走具備Levy flight類似的特性。圖4(a)所示為某市復(fù)雜路網(wǎng)上無偏隨機(jī)游走軌跡，可以看到軌跡具備明顯的Levy flight軌跡特征，圖4(b)、(c)分別為在該網(wǎng)絡(luò)上隨機(jī)游走1000次、每次5000步的步長分布，最長單次跳躍步長超過21km，圖4(b)顯示步長分布具備重尾特性，更進(jìn)一步，圖4(c)顯示，對數(shù)坐標(biāo)系下，步長分布呈負(fù)斜率直線分布，具備冪律特性。因此，本文在復(fù)雜路網(wǎng)上采用無偏隨機(jī)游走作為偵查對象的一般運(yùn)動學(xué)模型。

四、無偏隨機(jī)游走視角下多尺度社團(tuán)分割

網(wǎng)絡(luò)社團(tuán)是指由網(wǎng)絡(luò)節(jié)點(diǎn)所構(gòu)成的團(tuán)塊組織，其內(nèi)部節(jié)點(diǎn)之間連接致密，內(nèi)部節(jié)點(diǎn)與外部節(jié)點(diǎn)連接稀疏，因此，其社團(tuán)邊界節(jié)點(diǎn)天然成為區(qū)域封控的關(guān)鍵節(jié)點(diǎn)。當(dāng)前，已經(jīng)有大量的研究聚焦于如何發(fā)現(xiàn)網(wǎng)絡(luò)社團(tuán)及其層級結(jié)構(gòu)，主要是應(yīng)用圖的組合屬性，包括平衡切割、歸一化切割、模塊度及其各種拓展和優(yōu)化算法[14,15]，但是此類方法關(guān)注的是圖本身的拓?fù)湫再|(zhì)，在社團(tuán)尺度選擇上與偵查業(yè)務(wù)無明確關(guān)聯(lián)。

文獻(xiàn)[16]指出，復(fù)雜網(wǎng)絡(luò)上的馬爾可夫隨機(jī)游走過程提供了一種在各種尺度上動態(tài)揭示網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的機(jī)制，隨機(jī)游走的時間尺度（對于離散時間系統(tǒng)，時間尺度即對應(yīng)游走步數(shù)）即對應(yīng)了社團(tuán)分割過程的分辨率。直觀理解即是在馬爾可夫游走條件下，偵查對象以更大的概率在社團(tuán)內(nèi)部徘徊，更小的概率進(jìn)行跨社團(tuán)轉(zhuǎn)移。偵查對象隨機(jī)游走的步數(shù)即對應(yīng)了不同分辨率下的社團(tuán)結(jié)構(gòu)，也就是“圈、塊、格”逐層嵌套的層級結(jié)構(gòu)。

對于網(wǎng)絡(luò)上的無偏隨機(jī)游走過程，記A為網(wǎng)絡(luò)鄰接矩陣，M為隨機(jī)游走的狀態(tài)轉(zhuǎn)移矩陣，d為各節(jié)點(diǎn)度組成的列向量，矩陣H為網(wǎng)絡(luò)的社團(tuán)分割矩陣，對于H的每一個元素，若節(jié)點(diǎn)i劃歸為社團(tuán)j，則Hij= 1，否則，Hij=0，那么在時刻t的聚類自協(xié)方差矩陣為：

定義社團(tuán)劃分H的馬爾可夫穩(wěn)定性為：

式（12）反映了經(jīng)過t步隨機(jī)游走之后，目標(biāo)仍然留在社團(tuán)內(nèi)的概率大小，因此網(wǎng)絡(luò)社團(tuán)劃分問題轉(zhuǎn)化為求解使式（12）最大化的矩陣H，即：

上述優(yōu)化為NP-hard問題，無法直接求解，因此需轉(zhuǎn)而尋求其他啟發(fā)式優(yōu)化方法。根據(jù)式（10）、（12）、（13）可知：

注意到式（14）與無向帶權(quán)圖的模塊度表達(dá)式等價，對應(yīng)的等價無向帶權(quán)圖的鄰接矩陣為：

故對時刻為t的離散隨機(jī)游走條件下的網(wǎng)絡(luò)社團(tuán)劃分，可以等價為鄰接矩陣為式（15）所述無向帶權(quán)圖的社團(tuán)網(wǎng)絡(luò)劃分，劃分依據(jù)為等價圖的模塊度。本文采用Louvain算法[17]分別在1~50步隨機(jī)游走條件下對復(fù)雜路網(wǎng)進(jìn)行社團(tuán)劃分，結(jié)果如圖5所示?？梢钥吹?，不同的隨機(jī)游走尺度對應(yīng)了不同的社團(tuán)分割分辨率，更大的隨機(jī)游走步數(shù)對應(yīng)了更大的社團(tuán)結(jié)構(gòu)。

站在建設(shè)規(guī)劃的角度，將所有分辨尺度全部實(shí)現(xiàn)是一種理想極端情況，實(shí)際規(guī)劃中難以實(shí)現(xiàn)，同時也失去了切塊分格的意義。在尺度的選擇上，一個好的網(wǎng)絡(luò)分割應(yīng)該在不同的分割尺度上具有較好的穩(wěn)定性，即應(yīng)挑選出隨著隨機(jī)游走步長變化，分割結(jié)果相對平穩(wěn)的方案。圖5（a）所示為隨尺度變化，網(wǎng)絡(luò)社團(tuán)劃分的嵌套結(jié)構(gòu)，整體上，隨著觀察尺度的增大，網(wǎng)絡(luò)社團(tuán)呈現(xiàn)合并的趨勢。圖5（b）所示為2~50步隨機(jī)游走尺度下分別進(jìn)行社團(tuán)分割所得的網(wǎng)絡(luò)社團(tuán)數(shù)量，可以看到社團(tuán)劃分的數(shù)量整體隨尺度的增加而減少。為度量網(wǎng)絡(luò)社團(tuán)劃分的穩(wěn)定性，引入網(wǎng)絡(luò)分割的歸一化信息差異指標(biāo)[18]：

其中，P1、P2為兩種不同的網(wǎng)絡(luò)分割，H(P1|P2)表示給定分割P2條件下，選定分割P1的條件熵。V(P1,P2)取值在0到1之間，反映了兩種網(wǎng)絡(luò)分割的差異度，V的值越大，則兩種分割的差異性越大。圖6（c）所示為對2~50步隨機(jī)游走尺度分別進(jìn)行社團(tuán)分割，并對分割穩(wěn)定性進(jìn)行計(jì)算所得結(jié)果?？梢钥吹皆?7、35、43步等尺度上，分別出現(xiàn)相對穩(wěn)定區(qū)域。這些相對穩(wěn)定的、不同尺度的社團(tuán)結(jié)構(gòu)即構(gòu)成了逐層嵌套的封圈、切塊、分格基本布局框架。

五、基于平均捕獲時間的定點(diǎn)模型

根據(jù)前文構(gòu)建的復(fù)雜路網(wǎng)模型和目標(biāo)運(yùn)動模型，式（1）（2）所描述的布點(diǎn)計(jì)算問題可進(jìn)一步進(jìn)行求解。

記A為網(wǎng)絡(luò)鄰接矩陣，Z為前文所述復(fù)雜路網(wǎng)的對角度矩陣，即：

記I為N×N階單位矩陣，則網(wǎng)絡(luò)的歸一化拉普拉斯矩陣表示為：

記Г為網(wǎng)絡(luò)中卡口（即陷阱）節(jié)點(diǎn)的集合，根據(jù)文獻(xiàn)[19]易知，從非卡口節(jié)點(diǎn)出發(fā)，以無偏隨機(jī)游走方式，首次到達(dá)任意卡口節(jié)點(diǎn)的時間T'可表示為：

其中，L'為歸一化拉普拉斯矩陣去掉卡口節(jié)點(diǎn)對應(yīng)的行與列之后剩余的子矩陣，e為N-|Γ|維單位向量。

則從網(wǎng)絡(luò)任意一點(diǎn)出發(fā)，經(jīng)過無偏隨機(jī)游走，直至被網(wǎng)絡(luò)卡口節(jié)點(diǎn)首次捕獲的平均時間（步數(shù)）表示為：

其中l(wèi)-1

ij為L'的逆矩陣中對應(yīng)i行j列的元素。

盡管式（21）給出了網(wǎng)絡(luò)平均捕獲時間的計(jì)算方法，但必須注意到，在整個計(jì)算過程中，涉及大量高階矩陣運(yùn)算，難以操作，甚至不具備可行性。因此，前述章節(jié)中，對網(wǎng)絡(luò)進(jìn)行分割切塊成為計(jì)算的客觀需求。同時，式（21）難以求解其顯示表達(dá)式，近年來的相關(guān)研究也主要集中在特定網(wǎng)絡(luò)模型[20,21]，對本文所述主題，難以應(yīng)用更多的啟發(fā)信息進(jìn)行優(yōu)化求解。綜合上述因素，本文提出基于貪心策略的點(diǎn)位布局策略，即對每一個社團(tuán)，每一步將能最小化網(wǎng)絡(luò)平均捕獲時間的節(jié)點(diǎn)納入陷阱節(jié)點(diǎn)，直至社團(tuán)的平均捕獲時間達(dá)到設(shè)計(jì)規(guī)劃要求。針對某一個社團(tuán)發(fā)現(xiàn)分辨率下，捕獲點(diǎn)位的計(jì)算流程如圖7（a）所示。對于給定規(guī)劃區(qū)域，整體的點(diǎn)位布局策略流程如圖7（b）所示。

六、實(shí)驗(yàn)與分析

以某市為例，其融合復(fù)雜路網(wǎng)節(jié)點(diǎn)超過3萬個，根據(jù)多尺度社團(tuán)分割，對復(fù)雜路網(wǎng)進(jìn)行網(wǎng)格化劃分。在步長為10以下的尺度上，劃分的網(wǎng)格在40~50個，反映出小型街道、大型公園景區(qū)、大型單位等網(wǎng)格；在步長為10~30的尺度上，劃分網(wǎng)格數(shù)為30個左右，網(wǎng)格尺度介于大型街道、小型街道聯(lián)合體、行政區(qū)之間；在步長為40~50的尺度上，劃分網(wǎng)格為20個左右，已接近實(shí)際區(qū)級行政區(qū)劃數(shù)量。圖8顯示了不同尺度社團(tuán)分割實(shí)例。實(shí)際上，網(wǎng)格劃分與實(shí)際行政邊界雖然存在一定的關(guān)聯(lián)性，但并非嚴(yán)格對應(yīng)關(guān)系，實(shí)質(zhì)反映的是節(jié)點(diǎn)之間的密集關(guān)系。如學(xué)校W、D和景區(qū)F分屬不同的三個行政區(qū)，但實(shí)際上他們之間的連接更為緊密，與周邊的連接更為稀疏，更適合作為一個布局圈塊結(jié)構(gòu)。

選定網(wǎng)格劃分后，每個網(wǎng)格節(jié)點(diǎn)數(shù)處于數(shù)百至數(shù)千之間，與原網(wǎng)絡(luò)數(shù)萬節(jié)點(diǎn)下降1~2個數(shù)量級，使得第5章所述定點(diǎn)模型具備計(jì)算可行性。以某網(wǎng)格為例，該網(wǎng)格具備節(jié)點(diǎn)866個，以28個網(wǎng)格邊界節(jié)點(diǎn)為初始捕獲點(diǎn)，以平均4步捕獲為優(yōu)化目標(biāo)，經(jīng)過130輪迭代，平均捕獲時間從175降低至4以下，如圖9（b）所示，即偵查對象從任意一點(diǎn)出發(fā)，以無偏隨機(jī)游走的方式進(jìn)行運(yùn)動，平均經(jīng)過4個路口即會被智能卡口捕捉到影像。通過對該布點(diǎn)規(guī)劃進(jìn)行5000次模擬，平均捕獲時間為3.84，標(biāo)準(zhǔn)差為5.05，模擬目標(biāo)平均每經(jīng)過3.84個路口即被智能卡口捕獲到影像。在經(jīng)過5個、10個路口的距離內(nèi)被智能卡口捕獲的概率分別為76%和90.5%，如圖9（c）所示。圖9（a）所示為貪心策略下點(diǎn)位布局，其中綠色節(jié)點(diǎn)為網(wǎng)格邊界節(jié)點(diǎn)，即初始捕獲節(jié)點(diǎn)，橙色節(jié)點(diǎn)為擬部署點(diǎn)位。總擬部署點(diǎn)位占全部節(jié)點(diǎn)的18.2%。圖9（b）顯示，初期，部署少量節(jié)點(diǎn)即能快速降低平均捕獲時間，前30.7%的點(diǎn)位使得平均捕獲時間降低了85.7%，側(cè)面反應(yīng)出相關(guān)建設(shè)上的效能邊際遞減效應(yīng)。

七、結(jié)語

本文提出的規(guī)劃布局方法，對傳統(tǒng)“圈塊格點(diǎn)”布局經(jīng)驗(yàn)給出了一般化、普適性的數(shù)學(xué)計(jì)算框架，可以作為新建點(diǎn)位設(shè)計(jì)規(guī)劃、已建點(diǎn)位調(diào)整優(yōu)化、分級分類智能運(yùn)維的重要參考，也為今后全網(wǎng)統(tǒng)一資源智能調(diào)度、智能分析算力動態(tài)分配提供了研究路徑。

同時也應(yīng)注意到，本文所述算法，對基礎(chǔ)數(shù)據(jù)的準(zhǔn)確性依賴度較高。在整體網(wǎng)絡(luò)構(gòu)建上，考慮到的復(fù)雜因素仍然有限。下一步，擬進(jìn)一步融匯各部門相關(guān)基礎(chǔ)數(shù)據(jù)作為先驗(yàn)知識，結(jié)合實(shí)戰(zhàn)應(yīng)用數(shù)據(jù)和運(yùn)維數(shù)據(jù)，進(jìn)行優(yōu)化和改進(jìn)。