智能交通系統(tǒng)中的準入控制算法研究

潘海龍　陳世平

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

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

DOIDOI：10.11907/rjdk.151324

中圖分類號：TP311

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

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

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

1 問題提出

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

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

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

2 文獻綜述

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

3 FACP算法

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

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

3.1 路由尋找階段

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

3.2 路由回復階段

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

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

4 模擬與分析

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

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

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

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

5 結語

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

參考文獻：

[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