潘海龍　陳世平

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

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

DOIDOI：10.11907/rjdk.151324

中圖分類號(hào)：TP311

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

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

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

1 問題提出

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

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

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

2 文獻(xiàn)綜述

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

3 FACP算法

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

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

3.1 路由尋找階段

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

3.2 路由回復(fù)階段

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

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

4 模擬與分析

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

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

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

實(shí)驗(yàn)三：通過與MPARC[10]和CACP算法[11]進(jìn)行對(duì)比，考察相同時(shí)刻數(shù)據(jù)流突發(fā)程度變化對(duì)PDR影響的程度。由圖4可以看出，網(wǎng)絡(luò)中同時(shí)產(chǎn)生的數(shù)據(jù)流條數(shù)為0～40時(shí)，CACP、MPARC和FACP的數(shù)據(jù)到達(dá)率都是相同的，這是因?yàn)榫W(wǎng)絡(luò)未飽和時(shí)準(zhǔn)入控制的效果未顯現(xiàn)。而到40條數(shù)據(jù)流以后，網(wǎng)絡(luò)開始出現(xiàn)一定擁塞，CACP數(shù)據(jù)到達(dá)率下降最快，這是因?yàn)镃ACP估算信道時(shí)對(duì)數(shù)據(jù)流優(yōu)先級(jí)一視同仁，這時(shí)FACP與MPRARC數(shù)據(jù)到達(dá)率一樣，因?yàn)檫@時(shí)數(shù)據(jù)流并未足夠的多。而到60條數(shù)據(jù)流時(shí)，數(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)用時(shí)所面臨的難題。本文通過在路由尋找階段增加初級(jí)準(zhǔn)入控制，致使不滿足初級(jí)數(shù)據(jù)流要求的結(jié)點(diǎn)淘汰，以此解決拓?fù)浞秶鷱V引起的控制開銷大的問題。本文還通過路由回復(fù)階段將資源預(yù)留淘汰功能放入準(zhǔn)入控制中，使數(shù)據(jù)突發(fā)情況下節(jié)點(diǎn)的可用帶寬被低優(yōu)先級(jí)數(shù)據(jù)流預(yù)留的情況得以解決。實(shí)驗(yàn)表明，采用控制開銷比率、控制信息數(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