基于亞線性MG替換策略-網絡流的動態車流量檢測方式

沈智勇 蘇 翀* 沈智威 孫厚權 周 揚

1(江蘇科技大學 江蘇 張家港 215600)2(蘇州大學 江蘇 蘇州 215000)

0 引 言

隨著時代的發展，交通情況越發不確定，出行的安全度和舒適度逐漸受到重視。隨著私家車日益增加，人們出行更為便捷的同時，所造成的交通擁堵往往帶來諸多不便。用戶往往只想知道自己出行中起點到終點之間的道路情況，而對其他路上的道路情況不感興趣。

已有的交通路況檢測大多基于圖像處理與識別，這種方法不但耗資巨大，對于圖片信息的儲存數據量也是一個問題，若只在少數路口安置攝像頭進行分析車流量，圖像分析大多適應于相對靜態的情況或者車速較慢的情況，對于整條道路的動態車流量精度不能有明確保證。對于動態車流量的檢測，本文提出了一種基于亞線性MG算法的替換策略。

本文的主要貢獻如下：

(1) 提出一種基于亞線性的替換策略；

(2) 提出的亞線性算法能較好地應用于路況檢測；

(3) 選擇出一種高效的能與替換策略相結合的基數桶數據結構，保證了空間的亞線性。

實驗結果表明，該算法對于車流量的檢測與計算具有一定的可行性，相對于基于圖像處理的檢測方式降低了數據的緯度，提高了計算的速度，同時保護了個人的隱私。對于基于紅外方式的檢測方式本文提出的算法能大大提高數據的可信度，提高結果的正確性。

1 相關工作

1.1 ViBe算法檢測路況

ViBe算法利用視覺背景提取改進車流量估計，對靜止目標有非常良好的計算效果。ViBe算法能很好地抑制假影現象，將檢測器安裝至道路交通口，利用紅燈效應可對車流量進行準確檢測，提高了車形清晰度，提高了檢測的正確性[4,8]。但ViBe算法本身仍存在運動目標不完整等問題。

1.2 紅外檢測路況

當前普通的基于紅外的道路檢測系統，利用脈沖進行簡單計數，由采集模塊、交通燈控制模塊和模擬控制中心。基本上完成了車流量檢測的功能，但并未對其中收獲的數據進行簡化和計算，難以保證數據的準確性，失去了數據的意義。

2 亞線性MG替換策略-網絡流檢測方式

基于亞線性MG替換策略-網絡流的動態車流量檢測方式通過利用自制道路檢測器安置紅外對管，利用每個數據收集器收集的車輛通行數目。對道路情況進行算法分析與研究[2-4,6,10-11]。

本算法先求解出單條路徑的動態車流量，將此條路徑的車流量抽象成圖中的一條邊，根據大數定理構建圖，根據段流量求解出最大流，根據相關知識得出交通狀況。

算法總體設計流程如圖1所示。

圖1 算法總體設計流程

3 亞線性替換算法

3.1 基數桶

道路上存放N個檢測器，分別檢測到的數據將依次存放至基數桶中。根據Zipf定理，可以確定基數桶結構[1]是有效的。本文根據Zipf定理確定基數桶中的容量是全部數據值的10%。

基數是集合論中的一個概念，將相似的數據放入一個基數桶，并保證基數桶中各集合各自保證非遞減有序。

建立9個的基數桶，桶狀結構樣例如圖2所示。

圖2 基數桶數據結構圖

數據i進入基數桶中只需進入該對應集合，數據i進入基數桶時對數據的最高位進行劃分，如：12最高位是1，則進入1號基數桶，29的最高位是2，則進入2號基數桶，其優勢在于與其他數據保持獨立性。當有新的數據進入基數桶，如41進入基數桶，只需考慮基數4中集合所存在的元素，由于非遞減有序特性，利用插入排序對數據進行增加或者更新。

同時設置隊頭游標和隊尾游標分別指向各個集合的隊頭和隊尾。隨機算法替換數據時只需比較每個基數集合中的隊頭游標與隊尾游標中所指向的數據。

同時基數桶中的元素可利用塊狀鏈表[13]的形式對數據進行初始化、更新和插入，此時數據運算時的時間復雜度可大大降低。

當進行數據處理是空間復雜度顯然只與基數桶容量有關，是空間亞線性的。

3.2 隨機化與改進MG替換算法

本文利用紅外檢測器檢測道路流動車流量，并做出如下假設：

(1) 道路是單向的。

(2) 道路沒有交叉口。

根據上述假設可以得出：在單向無交叉口的一段連續道路上的檢測器在單位時間內測定的數據值大部分是相同的或是相似連續的(車流量并不能突變)。圖3表示在以上假設下檢測器檢測結果模型圖。

圖3 檢測器檢測結果模型圖

當a測出值為5，那么b測出的值應與a的檢測值相同或相差車道數m的倍數，且a、b檢測值差值不大。

根據以上假設推論：如果道路擁有交叉口，那在兩條交叉口之間的檢測器中的數據大部分是相同的。

利用Zipf定律可以得到一個大致的模型，90%的道路情況數據占所有道路情況數據值的10%(10%的數據值分布在不同的路口，有岔路等地)，我們可以稱這90%的數據是有效數據，剩下10%的數據是無效數據。但這90%的數據中不同的數字只占全部數據的10%，根據以上論述可以得出隨機化的合理性和有效性，亞線性替換算法描述如下：

Input：檢測器檢測到各個數值in[]；

Output：替換算法返回結果，基數桶中的有效數據out[][]；

1 While in[]!=empty:

2 i=0;

3 s←取[0,9]之間的任意一個隨機數；

4 i++;

5 cardinal←in[i*9+s]所對應的基數

6 Size←基數桶容量

7 If Size !=full:

8 If s?out[][];

9 s放入基數桶;

10 Out[ cardinal][].count++;

11 End If

12 End If

13 If Size==full:

14 If s∈out[][]:

15 s.Count++;

16 Else

17 For each out[ cardinal][]:

18 Out[ cardinal][].count--;

19 If out[ cardinal][].count==0

20 Flag=1;

21 移出基數桶;

22 End If

23 If flag==1

24 s放入基數桶

25 End If

26 End If

27 End While

算法有效性分析如下:

(1) 對于上述算法，由于關鍵在于隨機選取的間隔d應對于具體問題具體分析，由于隨機化，算法的時間復雜度嚴格小于數據量n，計算復雜度只與基數桶中的數量有關，故替換算法是時間亞線性的。

(2) Misra Gries算法步驟表明：在數據流中到達的項i進行如下的步驟：如果項i在數組T中，則其對應的計數器++c；如果項i不在數組T中，且數組T中的元素個數小于k-1，將項i加入數組T，并為其分配計數器ci=1；其他情況，將數組T中所有元素的計數器減1，此時如果數組T中存在元素的計數器值為0，則從數組T移除這個元素。MG算法保證了亞線性，本文將計數器的計算由全部數據縮小至基數桶的各個基數所對應的基數項的計數器計算此數，基數桶結構也將計算復雜度大大降低，滿足亞線性。

(3) 替換算法替換出的是最不頻繁出現的數字，也就是說當替換次數越多，出現無效數據的概率就越低。因為根據Zipf定律，有效的數據占了90%，無效的數字只有10%，這些數據肯定是最不頻繁的數字，那優先替換的是這些數字，故替換算法具有有效性。

(4) 關于隨機間隔d的選取：根據zipf定理，最少有90%的數據是有效數據，這些數據的數據值占所有數據值的10%(數據與數據值的概念如圖3所示，其他情況的比例可由實驗大致得出)，那么剩下10%的數據是無效數據，這些數據的數據值占所有數據值的90%，這90%的數據值基本上是與10%的無效數據一一對應。即若某數據值只出現一到兩次，那么這個數據值很有可能是無效數據，否則多次出現的數據值便不能稱之為無效數據。而對于有效數據，多個有效數據對應一個數據值，難以定量計算，故假設數據量為n，數據值為m，有如下等式：

0.1n=0.9m

(1)

則：

n=9m

(2)

推論：每9個數據中擁有1個數據值，根據上述證明，數據值一般為集中存在于交叉口與交叉口之間，故可確定連續的間隔，并確定隨機間隔為9。

對于上述選擇的間隔d=9,選取有效數據的概率為：

即當你用隨機選取數據時，選擇有效數據的概率有90%。當數據進行替換時有效性將大大高于90%。

4 多路徑問題

4.1 圓形限定數據點

上文介紹了對于單路徑數據的數據，以下給出多路徑的數據處理，根據起點至終點選擇哪部分數據進行計算。本文利用余弦定理篩選數據，具體篩選過程如下：只選取在源點與終點間圓形區域內的數據，將源點與終點連線構成直徑，當輸入數據時只需判斷三條邊長度平方之間的關系，當a2+b2-c2<0，那么該點在圓形內，當a2+b2-c2>0，那么該點不在圓形內，如圖4所示。之所以利用圓進行數據選擇，是根據等周不等式在相同周長情況下，圓形面積最大，選擇數據更多，效果更好。

圖4 圓角度圖

4.2 大數定理與最大流

圖5 岔路模型圖

其公式為：

(3)

又可根據總流量與出入流量xi、yi的關系得出：

(4)

證得：

故有：

(5)

圖6 多道路徑模擬圖

輸入起點與終點，利用余弦定理選擇數據，分別求出各個節點之間的段流量，求出該圖的最大流[5]。

5 實驗與討論

5.1 實驗設置

實驗將所提出的的MG算法與純紅外檢測算法分別在計算復雜度、空間復雜度兩個方面做比較。數據量分別選擇容易計算的100的倍數進行計算，分別為100、500、1 000、5 000、10 000。

實驗平臺是64位Windows10操作系統筆記本計算機，內存4 GB，CPU 2.5 GHz，實驗語言C++。

本文使用http://www.cs.unibo.it/projects/bolognaringway/所提供的數據，對數據進行整理，所需數據樣表如表1所示。

表1 實驗數據樣表

5.2 實驗結果

對于空間復雜度，純紅外復雜度為數據集數據個數N，對于本文空間復雜度為基數桶容量V。

表2 計算量對比

根據表2可知，未優化的檢測方式與本文方式從計算復雜度上有較大差距。

5.3 實驗結果與分析

當數據流中的數據進行判斷的時候可以說它們服從二項分布(有效數據和遠離數據)。隨機變量x～B(n,p)，對于任意的實數x，當數據量很大時[10]，有：

(6)

即，在大數情況下二項分布近似服從泊松分布，分布樣圖如圖7所示。

圖7 分布樣圖

在泊松分布的最左端是基數桶中基數為[1,2,3,…,9]中的head中最小游標指向的數，最右端是基數桶中基數為[1,2,3,…,9]中的rear中最大游標指向的數。

本文利用基數桶中的數據計算泊松分布的估計值，利用這個估計值代表這條路徑的動態流量，X(1),X(2),…,X(N)為服從泊松分布P(λ)的獨立樣本。則：

Ex(k)=λ,k=1,2,3,…,N

(7)

(8)

道路擁堵參數JAM，即能導致道路擁擠的最大的動態流量，由城市道路情況設定。顯然，在一定程度內最大流動車流量max_flow越大，道路情況越好，但當max_flow達到某個限制，道路車輛陡增會導致道路擁擠。當max_flow

圖8 變化循環圖

由此可得出以下實驗結論：只需比較上一時間段的數據即可判斷道路情況，若流量陡降則發生擁堵；若與上文流量保持均衡，流量平穩則不擁堵；若流量均勻下降或者均勻上升道路,情況穩定不發生擁堵；若流量陡增則道路動態車流量大，則也沒有發生擁堵。

本文利用基數桶中所得的期望作為數據點計算標準差，利用標準差表示車流量突變情況。

(9)

根據數據的處理，可得如下結論：

(1) 在數據范圍很小的情況下，亦或是在極端情況下，即當線路是一條直線時，最大流接近于紅外接收信息的計數均值，計算速率快。

(2) 當數據范圍很大的情況下，本文數據結構保證了數據的可靠性，使用的算法在時間亞線性計算速率相比于普通的替換策略算法有明顯優勢。

6 結 語

本文提出的基于亞線性MG-網絡流算法應用于檢測道路路況，對檢測高速動態車輛有比較好的效果。實驗證明，該算法能夠很好地達到檢測目的，并且對于數據，選擇了計算度最低的點數據，能夠很好地降低數據處理的難度和復雜度。但不足之處在于：當交通路線過于復雜，其桶容量不足會導致系統誤差，因此算法在道路錯綜復雜度過高的情況下，精度不高。