智能交通系統中的準入控制算法研究

潘海龍　陳世平

摘要：無線網絡傳輸數據因具有低成本高效率的優點，在智能交通領域得到廣泛應用。然而智能交通擁有數據突發性強和拓撲范圍廣的特點，為無線網的準入控制帶來了巨大挑戰。采用FACP 算法（FilteringAware Admission Control Protocol ），在準入控制路由尋找階段增加初級準入控制，以減少數據傳輸范圍，并在路由回復階段將資源預留淘汰功能放入準入控制以解決數據突發問題。與傳統的DSR、CACP準入控制等算法進行對比實驗，結果表明，采用FACP算法較現有的準入控制具有更大的優勢。

關鍵詞：智能交通；無線網；準入控制；路由尋找階段；路由回復階段

DOIDOI：10.11907/rjdk.151324

中圖分類號：TP311

文獻標識碼：A 文章編號：16727800（2015）006006504

基金項目基金項目：國家自然科學基金項目（61170277）；上海市教委科研創新重點項目（12zz137）；上海市一流學科建設項目（S1201YLXK）

作者簡介作者簡介：潘海龍（ 1988- ） ， 男，上海人，上海理工大學光電信息與計算機工程學院碩士研究生，研究方向為無線網絡、P2P；陳世平（1964-），男， 浙江紹興人，博士，上海理工大學光電信息與計算機工程學院教授，研究方向為計算機網絡通信、數據庫與知識庫、信息系統研究和開發。

1 問題提出

隨著科技與經濟的發展，減少交通擁堵是各國政府致力解決的難題之一。智能交通能在多方面增強交通基礎設施，如利用每個交叉路口的傳感器接收信息并建立實時交通圖，駕駛員通過此信息可以找到通往目的地的最佳路徑。智能交通的智慧節點與交通燈結合，通過優化交通燈工作狀態，提高道路車輛吞吐量。因智能交通需在所有交叉路口設置智能節點，如果用有線技術傳輸實時數據需要大規模開挖路面，鋪設通信光纜以及連接交叉路口至控制室的各種設備，成本過大，因此，需在智能交通中采用無線網技術[1]。在無線網技術中任何一個節點發送數據都會競爭信道，從而影響其它節點的正常通信。為防止新的數據流消耗過多資源影響到正常通信，引入了準入控制，然而，智能交通的獨特性給無線網中的準入控制帶來了挑戰。

挑戰一：智能交通因需要覆蓋整個城市，無線拓撲非常廣，無線結點眾多，這對于通過單純廣播方式完成準入控制代價是巨大的。假設結點傳輸范圍R為傳輸范圍內的結點密度，傳統的準入控制規定每一結點收到路由尋找消息后，要將此消息再次轉發給其傳輸范圍內的所有節點，以此類推到經過n跳到達目標結點時會收到路由尋找信息，因此在整個路由尋找階段，路由尋找信息將被發送n次。由此可發現，僅通過單純廣播來實現路由尋找的通信代價是巨大的；挑戰二：早晚高峰時間交通狀況較復雜，數據突發情況多，這時多個發送結點同時分享相同資源節點和目標節點可能性增大，不同數據流在相同結點進行準入控制以及資源預留的時間間隔變短，這時如果較低優先級的數據流通過了準入控制并產生了資源預留，高優先級的卻因資源已被預留而被拒絕準入，這將對服務質量產生極大影響。

為解決上述問題，本文通過改進路由尋找階段和路由回復階段的準入控制，來適應智能交通系統對無線網的新要求。

2 文獻綜述

目前在準入控制算法中最常用的是DSR動態路由尋找，見參考文獻[34]，[6]，[89]，[11]。它采用單純的廣播方法發送路由尋找請求，但是在傳輸范圍廣的情況下傳輸代價很大，這顯然不適合智能交通。在路由回復階段，帶寬預測有3種不同的研究：①用空閑的帶寬作為評估可用帶寬的標準，這個方法不支持優先級[23]。然而在智能交通中，通信數據擁有優先級，比如交通指示燈數據比實時視頻數據重要，需要優先保證其通信[47]；②通過估計信道的訪問時間來估計可用帶寬數，然而在新數據流還沒到達前可用帶寬的預估數是大于實際的[810，12]；③根據本地通信狀況如競爭窗口大小、幀大小以及網絡擁塞忍耐狀況確定可用帶寬[11]。這個方法的好處在于它權衡了本地通信狀況以及對鄰居節點的影響，給出了可用帶寬預估方法。但是，這幾種方法都忽視了數據突發情況下資源預留對可用資源預估的影響，這種缺陷對于具有數據突發特性的智能交通來說是致命的。為解決以上問題，本文提出了FACP算法。

3 FACP算法

無線準入控制由路由尋找和路由回應兩部分組成。傳統的無線準入控制在路由尋找過程中都采用了DSR動態路由算法。此路由算法是：發送者廣播路由尋找請求，傳輸范圍內的所有接受者收到請求信息并檢測自身是否為目標節點，不是則將地址放入路由記錄并再次廣播，直至到達目標節點。由于智能交通智慧節點多且覆蓋范圍廣，僅靠廣播方式尋找路由通信代價是巨大的。

傳統路由在回應階段忽視了數據突發情況下對可用帶寬預估的改變因素，數據突發情況下多個發送節點幾乎同時分享相同資源點和目標節點間的路徑和節點可能性增大，低優先級因比高優先級早到一點點時間通過準入控制并將資源預留，然而早到時間不足以發送完低優先級數據流，此時高優先級數據流卻因資源已被低優先級預留而被大大延遲，降低了服務質量。本文提出的FACP算法在路由尋找和路由回應階段分別采用初級篩選功能和預留淘汰的準入控制方法。

3.1 路由尋找階段

路由尋找的目標是找到發送節點與目標節點間擁有足夠資源的路由提供給數據流。作為拓撲結構復雜且拓撲范圍廣的智能道路，需要查找更準確代價更低的路由尋找方法。FACP在路由尋找階段通過初級準入控制完成了篩選功能，解決了傳統準入控制在路由階段的不足。初級準入控制指為了減少不必要的廣播轉發，淘汰不符合初級準入條件的節點，以達到準確查找節點且代價更低的目的。新數據流對網絡的負載預估Unew與節點數n有關（即Unew=nRnew，Rnew是新數據流要求速率），n為該結點傳輸范圍內滿足路由路徑上的結點數量，公式表示為n=Total△∩Route△。Total△表示△的傳輸范圍內節點總數量，Route△表示△的傳輸范圍內新數據流路由經過的節點數量。因在路由階段路由路徑還未確定，n保守地設為1，即Unew=Rnew，此時對數據流負載的初期預估比實際要小，淘汰那些連初期負載預估都滿足不了的資源節點，以避免這些節點作無謂的廣播，按照這種預估作為準入控制的標準稱為初級準入控制。在路由尋找階段，每個節點通過廣播方式已經收集到鄰居節點通信狀況信息，其中包括WXi競爭窗口大小、LXi幀大小、RXi數據速率、η*r擁塞忍耐狀況等，這些數據都保存在節點的緩存中，當周圍節點通信狀況發生變化時才更新。當收集完鄰居節點的通信后，節點根據這些信息預估出可用資源。參考文獻[11]算法可以在路由尋找信息到達節點之前就完成可用資源預估Anew=C（1-ni=rRXiLXi[]C-1[]η*rr-1i=1LXi[]WXi），發送節點廣播路由尋找信息，信息包括新數據流要求速率、路由信息等，節點收到路由尋找信息后，比較可用資源預測信息是否大于新數據流負載的初期預估，滿足條件則將路由地址加入路由信息并繼續廣播路由尋找信息，以此類推直至達到目標節點。當不能滿足要求時，則直接丟棄路由尋找信息。初級準入控制通過淘汰一些節點來實現減少路由廣播次數、減少數據傳播代價、加快路由尋找速度的目的。

3.2 路由回復階段

路由尋找信息到達目標節點后，標志著路由尋找階段的結束和路由回復階段的開始。目標節點根據先前路由尋找階段確定的路由，發送路由回復信息，其中包含路由信息、新數據流速率、數據流的優先級等。路由結點收到信息后，開始進行準入控制。由于此階段路由已經確定，因此此時新數據流對網絡負載預估是準確的。將可用資源的預估與流量對網絡負載預估進行對比，進行準入控制，使新數據流不影響到比它優先級高的數據流正常通信。

這個關于x的不等式能滿足新數據流的負載預估保留的最低資源預留優先級。當最低資源預留優先級x∈[1，k]，說明新數據流的加入需要淘汰優先級比自己高的資源預留才能通過準入控制，這將導致流經該節點的高優先級數據流阻塞，影響到服務質量，因此該新數據流不滿足準入控制需要，該路由回復信息要丟棄。當最低預留優先級x=k時，表明新數據流的加入需要淘汰該節點預留優先級比它低的k+1至n的數據流。當x∈（k，n），說明只需淘汰x+1至n的數據流預留就能通過準入控制，不需要淘汰所有比新數據流優先級低的資源預留，達到充分利用節點資源的目的。當x∈（n，+∞），說明該節點通過準入控制并且節點有充分的帶寬資源，不需要淘汰任何資源預留。資源預留淘汰機制過程如下：當確定好需要淘汰的預留資源時，節點根據這些數據流的路由信息發送節點撤銷指令，并要求過一段時間之后重新進行準入控制。為保證資源預留的實時準確性，通過準入控制的新數據流，更新該節點的資源預留Uk=Uk+Unew，并繼續根據路由信息進行轉發直至到達發送節點，完成整個準入控制。圖1為整個準入控制的工序流程。

4 模擬與分析

模擬數據如下：有100～300個結點隨意分配在10×10至1 000×1 000的范圍內，通信范圍為300m，載波監聽范圍為600m，信道帶寬為4mbps。本文通過以下3個方面檢測FACP算法的優勢與性能：①通過節點數量固定拓撲范圍變化檢測；②拓撲范圍固定增加節點密度檢測；③通過相同時刻數據流突發變化檢測FACP的優勢。

實驗一：將FACP與傳統的DSR在控制開銷比率上進行對比。控制開銷比例是整個準入控制中通信開銷大小與數據流對網絡的負載大小之比。從圖2可以看出，當節點拓撲范圍10×10時，控制開銷幾乎可以忽略。因為這時發送節點和目標節點距離很近，只需要一跳就能完成，所以此時FACP與傳統DSR尋找路由的準入控制效果是一樣的。然而隨著拓撲范圍越來越大，跳數增加導致轉發次數增加最終引起的控制開銷也明顯增大。FACP在路由尋找過程中篩選不必要跳數的優勢也就愈加明顯。

實驗二：考察不同節點密度下，控制信息的變化數。由圖3可看出，隨著節點密度的增加，控制信息轉發的次數也不斷增多，相較于傳統DSR尋找路由，采用FACP算法的控制信息發送次數則大大減少，這是因為FACP在路由尋找過程中篩選出了不符合初級準入控制的結點，減少了控制信息發送的次數。

實驗三：通過與MPARC[10]和CACP算法[11]進行對比，考察相同時刻數據流突發程度變化對PDR影響的程度。由圖4可以看出，網絡中同時產生的數據流條數為0～40時，CACP、MPARC和FACP的數據到達率都是相同的，這是因為網絡未飽和時準入控制的效果未顯現。而到40條數據流以后，網絡開始出現一定擁塞，CACP數據到達率下降最快，這是因為CACP估算信道時對數據流優先級一視同仁，這時FACP與MPRARC數據到達率一樣，因為這時數據流并未足夠的多。而到60條數據流時，數據突發隨之開始，FACP效果開始顯現，FACP算法的數據到達率具有較好的穩定性。

5 結語

拓撲范圍廣、數據突發性高是目前無線網絡在智能交通應用時所面臨的難題。本文通過在路由尋找階段增加初級準入控制，致使不滿足初級數據流要求的結點淘汰，以此解決拓撲范圍廣引起的控制開銷大的問題。本文還通過路由回復階段將資源預留淘汰功能放入準入控制中，使數據突發情況下節點的可用帶寬被低優先級數據流預留的情況得以解決。實驗表明，采用控制開銷比率、控制信息數量和數據到達率的方式，使FACP在拓撲范圍廣和數據突發情況下表現優異。

參考文獻：

[1]U S. Department of Transportation.ITS Overview[EB/OL]. http：//www.its.dot.gov/its verview.htm， 2008.

[2]MICHAEL G BARRY， ANDREWT.Distributed control algorithm for service differentiation in wireless packet networks[J].IEEE INFOCOM ，2001，26（10）：439502.

[3]D MALTZ. Resource management in multihop Ad hoc networks[J].Technical Report CMU CS 00150，2000，623（8）：123231.

[4]AGRAWAL S，CHAPORKAR P UDWANI .All admission control for realtime applications in wireless network [J]. IEEEINFOCOM，2013，45（7）：330334 .

[5]AIKTUAN LEE，GERLA M.Performance evaluation of wireless network coding in TDMA networks[J].IEEE INFROCOM ，2012 ， 9（3）：1 6 .

[6]BRUHADESHWAR B.A fully dynamic and selfstabilizing TDMA scheme for wireless Adhoc networks advanced information networking and applications （AINA）[C].24th IEEE International Conference ，2010：706812.

[7]QING JIN ZENG.A crosslayer based TDMA protocol for wireless biomedical sensor networks biomedical engineering and informatics （BMEI）[C].5th International Conference ，2012：340456.

[8]MANTHOS KZANTZIDIS， MARIO GERLA， SUNGJU LEE.Permissible network feedback for adaptive multimedia in aodvmanets[C].IEEE Conference ，2001：56123.

[9]HONG PENG WANG.Nodetonode available bandwidth estimation in ad hoc networks computer and electrical engineering[C].International Conference，2008：701705.

[10]CABELLOS APARICIO A.A novel available bandwidth estimation and tracking algorithm[C].IEEE International Conference 2008 ， 8（7）：8794.

[11]YALING YANG.Throughput guarantees for multipriority traffic in Ad hoc networks[J].IEEE International Conference on Mobile Adhoc and Sensor Systems， 2004，30（1）：410500.

[12]PENGZHAO. Rateadaptive admission control for bandwidth assurance in multirate wireless mesh networks[J].IEEE International Conference on， 2010：659663.

責任編輯（責任編輯：杜能鋼）

英文摘要Abstract：Intelligent traffic is of great importance to the development of transport infrastructure modernization. Wireless data transmission network because of its advantages with low cost and high efficiency has been well received by the Intelligent traffic， however intelligent traffic has characteristics of the data of sudden strong and large topological range ，which poses great challenges for wireless network access control. This paper adopts FACP algorithm （FilteringAware Admission Control Protocol）， the admission control protocol is included in the route finding phase to create primary access control， in order to reduce the data transmission range， and in the route reply phase will be the resource reservation elimination function to solve the problem of data burst. Compared with the traditional DSR， CACP admission control algorithm， It is verified the effectiveness of the proposed method. Experiments show that the FACP algorithm compared with the existing admission controlprotocol has more advantages.

英文關鍵詞Key Words： Intelligent Traffic；Wireless Network；Admission Control Protocol；Route Finding Phase；Route Reply Phase