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

潘海龍　陳世平

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

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

DOIDOI：10.11907/rjdk.151324

中圖分類號：TP311

文獻(xiàn)標(biāo)識碼：A 文章編號：16727800（2015）006006504

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

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

1 問題提出

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

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

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

2 文獻(xiàn)綜述

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

3 FACP算法

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

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

3.1 路由尋找階段

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

3.2 路由回復(fù)階段

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

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

4 模擬與分析

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[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.

責(zé)任編輯（責(zé)任編輯：杜能鋼）

英文摘要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.

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