車(chē)載自組網(wǎng)信息服務(wù)與動(dòng)態(tài)交通誘導(dǎo)算法研究

彭康華，楊軍，黃裕鋒

（廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，廣東廣州510520）

據(jù)統(tǒng)計(jì)，我國(guó)的交通意外發(fā)生率排在世界前列，車(chē)載自組網(wǎng)是未來(lái)有效解決安全出行的關(guān)鍵途徑。Dedicated Short Range Communication（DSRC），即車(chē)載專(zhuān)用短程無(wú)線通信，在減少交通事故、降低交通擁堵和提高交通效率方面有較好作用[1，2]。基于車(chē)載專(zhuān)用短程無(wú)線通信網(wǎng)絡(luò)可用于車(chē)聯(lián)網(wǎng)[3]，能夠?qū)?chē)輛的運(yùn)行狀態(tài)實(shí)現(xiàn)實(shí)時(shí)監(jiān)測(cè)及綜合分析，進(jìn)而為駕駛員提供更高效的服務(wù)，同時(shí)緩解目前積重難返的城市交通擁堵及減少交通事故的發(fā)生。車(chē)輛接入DSRC，就可將車(chē)輛操作信息傳送至周?chē)能?chē)輛，使得收發(fā)信息、執(zhí)行速度和反應(yīng)得以提高，各類(lèi)信息都能得到即時(shí)的共享或預(yù)警[4，5]。為達(dá)到上述條件，提出了一個(gè)研究方案，其主要特征是研究IEEE802.11p的車(chē)載自組網(wǎng)（VANET，Vehicular adhoc network），提供交通信息服務(wù)與基于并行蟻群算法的動(dòng)態(tài)交通誘導(dǎo)服務(wù)，確保行車(chē)安全及通行效率。

1 基礎(chǔ)硬體配置

在目前條件下，聯(lián)網(wǎng)的汽車(chē)均安裝有IEEE802.11p全雙工無(wú)線模塊的無(wú)線網(wǎng)卡，用于聯(lián)網(wǎng)汽車(chē)間的通信，由車(chē)載系統(tǒng)進(jìn)行控制。在IEEE802.11p發(fā)布前，不少研究學(xué)者已做了模擬實(shí)驗(yàn)，結(jié)論是IEEE802.11p在高速運(yùn)行情況下，能為汽車(chē)提供正常的移動(dòng)信息收發(fā)[6，7]。在我國(guó)的標(biāo)準(zhǔn)中，DSRC支持的是5.8 GHz，在5.725 GHz到5.875 GHz的共用頻段內(nèi)。更有學(xué)者研究表明，使用IEEE 802.11a驅(qū)動(dòng)為基礎(chǔ)，基于 DCMA86 P2、Atheros5414B等芯片的無(wú)線網(wǎng)卡，通過(guò)實(shí)驗(yàn)實(shí)現(xiàn)了IEEE 802.11p的驅(qū)動(dòng)。車(chē)聯(lián)網(wǎng)的車(chē)載系統(tǒng)可以智能的識(shí)別和收發(fā)語(yǔ)音，通過(guò)10英寸的液晶顯示屏來(lái)對(duì)車(chē)輛相關(guān)信息及道路相關(guān)信息的輸出輸入，傳送交通服務(wù)信息及預(yù)警信息。

2 組網(wǎng)設(shè)計(jì)技術(shù)

研究方案的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)使用基于IBSS，即獨(dú)立基本服務(wù)集（Independent BSS）網(wǎng)絡(luò)，也被稱(chēng)作ad-hoc網(wǎng)絡(luò)、無(wú)線自組網(wǎng)、對(duì)等網(wǎng)等[8-10]，該網(wǎng)絡(luò)的主要特征是有較強(qiáng)的抗毀壞性，無(wú)論是需組網(wǎng)還是需解除，均較為方便，并且費(fèi)用相對(duì)低廉。數(shù)據(jù)幀主要構(gòu)成如表1所示。

表1 IEEE802.11p數(shù)據(jù)幀構(gòu)成

上述的數(shù)據(jù)幀構(gòu)成，附帶車(chē)輛身份認(rèn)證信息、幀頭和幀尾、校驗(yàn)位等，每幀總共設(shè)定為300bit。在實(shí)際應(yīng)用中，與每輛車(chē)發(fā)送幀相關(guān)的汽車(chē)，通常為附近的接收車(chē)輛，設(shè)定附近車(chē)輛為30輛，根據(jù)該車(chē)輛密度控制發(fā)射功率，以IEEE802.11p為基礎(chǔ)，假設(shè)每車(chē)發(fā)送10幀/秒，可以通過(guò)統(tǒng)計(jì)和計(jì)算，計(jì)算出數(shù)據(jù)幀所使用的總數(shù)據(jù)量。每秒為:

300Byte×8bit/Byte×Byte×30輛車(chē)×10幀=720kbit。

通常，IEEE802.11p在120公里每小時(shí)下，一般可以執(zhí)行18 Mbps左右的接入速率，以此來(lái)計(jì)算，已經(jīng)有足夠的冗余，能充分滿(mǎn)足車(chē)聯(lián)網(wǎng)需求。

3 車(chē)聯(lián)網(wǎng)交通信息服務(wù)

3.1 車(chē)輛定位交通信息傳輸?shù)膶?shí)現(xiàn)

現(xiàn)階段常用的是GPS絕對(duì)定位技術(shù)，配合使用DSRC，每輛車(chē)輛都可以發(fā)送本身的定位信息，同時(shí)能接收附近的車(chē)輛定位等信息，建立車(chē)聯(lián)網(wǎng)的位置關(guān)系圖。為得到更精確的定位，同時(shí)配合使用了相對(duì)定位。相對(duì)定位使用超聲定位，當(dāng)車(chē)輛在十米以?xún)?nèi)，或無(wú)衛(wèi)星信號(hào)，比如隧道，車(chē)庫(kù)內(nèi)，該場(chǎng)合可以使用相對(duì)定位來(lái)構(gòu)建以本車(chē)為中心的位置關(guān)系圖。在應(yīng)用超聲定位時(shí)，每一輛車(chē)上安裝一個(gè)廣角超聲發(fā)射裝置，三個(gè)超聲接收裝置。車(chē)輛在IEEE802.11p無(wú)線網(wǎng)卡發(fā)送完一數(shù)據(jù)幀后，隨之發(fā)送超聲波信號(hào)，按照接收的無(wú)線電信號(hào)與超聲信號(hào)所到達(dá)的時(shí)間差，可以計(jì)算發(fā)送信號(hào)車(chē)與接收信號(hào)車(chē)的間距。而車(chē)輛的方向確認(rèn)通過(guò)不同方向設(shè)置的三個(gè)超聲波接收器來(lái)確定。車(chē)載系統(tǒng)根據(jù)接收的數(shù)據(jù)幀內(nèi)容及相對(duì)定位計(jì)算數(shù)據(jù)，通過(guò)分析和計(jì)算，可以在人機(jī)界面獲得附近車(chē)輛的ID、車(chē)輛狀況、位置關(guān)系等相關(guān)數(shù)據(jù)。

3.2 改進(jìn)蟻群算法動(dòng)態(tài)交通誘導(dǎo)實(shí)時(shí)服務(wù)

通過(guò)將上述的交通信息服務(wù)采集或通過(guò)DSRC接收的路面實(shí)況，實(shí)時(shí)發(fā)送到車(chē)聯(lián)網(wǎng)中，車(chē)輛收到誘導(dǎo)信息后，能夠根據(jù)路面情況來(lái)選擇或避開(kāi)堵塞路段，從而提高出行效率及道路的使用率，降低交通事故發(fā)生率，使得路面資源得到有效的優(yōu)化和配置。

3.2.1 基本蟻群算法模型

蟻群在覓食時(shí)能分泌信息素，所走的路程越短，信息素越濃，趨于選擇該路徑的螞蟻越多，這就是蟻群算法的正反饋機(jī)制。建模時(shí)，第t次迭代網(wǎng)點(diǎn)上的信息素描述為τij（t），信息素初始化為零，即τij（0）=const，螞蟻k歷遍的途徑點(diǎn)描述為禁忌表tabuk（k=1…r），歷經(jīng)途徑 i、j的啟發(fā)信息描述為ηij（t）。在求解時(shí)，以信息素為依據(jù)，系統(tǒng)選取隨機(jī)概率來(lái)歷遍節(jié)點(diǎn)，由此可知，系統(tǒng)在第t次循環(huán)時(shí)，螞蟻k選擇節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移概率如公式（1）所示。

公式（1）的allowedk=neighborsi-tabuk，代表螞蟻k接下來(lái)爬行的下一路徑，是鄰居節(jié)點(diǎn)排除禁忌表爬過(guò)的節(jié)點(diǎn)，neighborsi指的是鄰居路徑節(jié)點(diǎn)集。α、β描述為各啟發(fā)因子。ηij（t）表達(dá)的是啟發(fā)函數(shù)值。

3.2.2 修正的蟻群算法

修正的蟻群算法中，對(duì)轉(zhuǎn)移概率、信息素濃度更新方法和啟發(fā)函數(shù)等關(guān)鍵影響指標(biāo)進(jìn)行改進(jìn)。

①改進(jìn)的轉(zhuǎn)移概率方法

隨著路網(wǎng)成倍增長(zhǎng)，節(jié)點(diǎn)數(shù)量急劇增大，求解時(shí)收斂所耗費(fèi)時(shí)間更長(zhǎng)。通過(guò)改進(jìn)傳統(tǒng)算法，提出模仿最大最小蟻群系統(tǒng)方法，改良為偽隨機(jī)轉(zhuǎn)移概率，以求解決收斂效率低的問(wèn)題。具體實(shí)現(xiàn)方法見(jiàn)公式（2）。

公式（2）的R值是0到1間的隨機(jī)值，R0表達(dá)為概率選擇因子，如果R≤R0，螞蟻即可以依據(jù)相鄰節(jié)點(diǎn)轉(zhuǎn)移概率最大的搜尋；如果R＞R0，依據(jù)輪盤(pán)決定隨機(jī)節(jié)點(diǎn)。偽隨機(jī)概率既可以滿(mǎn)足傳統(tǒng)算法的多變性，同時(shí)實(shí)現(xiàn)了可靠的收斂性，改進(jìn)了算法的收斂效率，使得算法更加的智能化。

②改進(jìn)的信息素濃度更新方法

每個(gè)螞蟻以出發(fā)點(diǎn)至終點(diǎn)為一次爬行，使用局部更新方法。當(dāng)r個(gè)螞蟻完成一次迭代，路徑實(shí)行全局更新方法。為使得下一個(gè)螞蟻搜尋到上一個(gè)螞蟻爬行的路經(jīng)以增加多樣性而采取了局部更新，以此對(duì)之前爬行過(guò)路經(jīng)上的信息素濃度實(shí)施弱化處理，具體操作方法見(jiàn)公示（3）所示。

而全局的更新方法見(jiàn)公式（4）所示。

公式（5）中，Lz表達(dá)的是已搜尋的全局最佳路經(jīng)。

這種全局更新方法更便于全局最短路徑的搜索。

③改進(jìn)的啟發(fā)函數(shù)

改進(jìn)的動(dòng)態(tài)交通誘導(dǎo)啟發(fā)函數(shù)中，設(shè)置了路網(wǎng)的加權(quán)值，為時(shí)間的函數(shù)。按照實(shí)時(shí)接收的交通服務(wù)信息來(lái)計(jì)算路面狀況并預(yù)測(cè)，同時(shí)參考過(guò)去數(shù)據(jù)，計(jì)算路面在不同時(shí)間的行程時(shí)間t對(duì)應(yīng)的函數(shù)f（t），如公式（6）所示。

時(shí)間函數(shù)f（t）、啟發(fā)函數(shù)ηij與轉(zhuǎn)移概率（t）的關(guān)系為f（t）↓?ηij（t′）↑?（t）↑，體現(xiàn)了動(dòng)態(tài)交通變化特征，適用于實(shí)際出行交通信息服務(wù)。同時(shí)Lk代表螞蟻k搜尋路徑上行程花費(fèi)總時(shí)間。

根據(jù)以上分析，歸納總結(jié)經(jīng)過(guò)改進(jìn)的螞蟻算法步驟如圖1所示。

圖1 改進(jìn)的螞蟻算法步驟

通過(guò)改進(jìn)的轉(zhuǎn)移概率、信息素濃度更新方法和啟發(fā)函數(shù)等關(guān)鍵影響指標(biāo)，得到修正后的蟻群算法模型，并按上述步驟進(jìn)行后節(jié)的算法實(shí)驗(yàn)。

3.2.3 動(dòng)態(tài)交通誘導(dǎo)服務(wù)的并行計(jì)算法

隨著人口及車(chē)輛的快速增加，交通壓力日益增大，串行計(jì)算的最優(yōu)路徑誘導(dǎo)現(xiàn)已跟不上大規(guī)模的繁忙交通誘導(dǎo)的步伐。為了解決該瓶頸，并行動(dòng)態(tài)交通誘導(dǎo)應(yīng)運(yùn)而生，保證了大規(guī)模交通誘導(dǎo)的實(shí)時(shí)性，并行計(jì)算的車(chē)聯(lián)網(wǎng)動(dòng)態(tài)交通誘導(dǎo)對(duì)用戶(hù)快速出行需求作用巨大。

①并行計(jì)算模型

對(duì)于蟻群算法的特征而言，比較方便和適用的是信息傳遞模型 Message Passing Interface（MPI），該軟件平臺(tái)無(wú)關(guān)于編程語(yǔ)言，進(jìn)行并行計(jì)算只需調(diào)用MPI的可移植性編程接口即可實(shí)現(xiàn)，也可進(jìn)行異步通信，能應(yīng)用于目前流行的各大操作系統(tǒng)，易于操作和實(shí)現(xiàn)。設(shè)定有r只螞蟻，劃分q為個(gè)子蟻群，在各處理器中各子任務(wù)分別執(zhí)行串行蟻群算法。

②改進(jìn)并行蟻群算法模型設(shè)計(jì)

在實(shí)際運(yùn)用過(guò)程中，子任務(wù)求得解后需與其他處理器交換數(shù)據(jù)，但這種屢屢的數(shù)據(jù)交換可能是無(wú)用的或低效的。因此，需改進(jìn)和設(shè)置固定交換周期，達(dá)到減少無(wú)用交換頻率的目的。處理器通信采用主從式消息傳遞機(jī)制，主伺候器將匯總從伺候器在固定周期內(nèi)達(dá)到的局部解，實(shí)施雜交算法來(lái)運(yùn)算并反饋結(jié)果。在改進(jìn)算法實(shí)施時(shí)，對(duì)求得最優(yōu)解的收斂速度起關(guān)鍵作用的是雜交算子，雜交算子的作用在于預(yù)防局部收斂，提升求得全局最優(yōu)解的概率。使用主從式通信機(jī)制時(shí)，當(dāng)螞蟻迭代次數(shù)等于所建立的固定交互周期值，主節(jié)點(diǎn)得到其它次節(jié)點(diǎn)在交互周期傳遞的最優(yōu)解，并使用雜交算子機(jī)制來(lái)分析與處理。

③改進(jìn)并行蟻群算法模型實(shí)現(xiàn)

設(shè)定有m個(gè)處理器，主處理器已接收來(lái)自從處理器的最優(yōu)解，S={S1，S2，…，Sm}，其中 Sm代表第m個(gè)處理器求得的最優(yōu)解，接下來(lái)是使用雜交算子方法來(lái)分析和處理該最優(yōu)解。上述的算法中，結(jié)合路網(wǎng)的實(shí)際，使用了啟發(fā)式雜交算子，通過(guò)實(shí)驗(yàn)案例來(lái)表達(dá)如下所示。

設(shè)定路徑 S1={5，4，10，6，9，16，26，20，19}，路徑 S2={5，7，8，10，12，14，16，23，20，19}，為被選中父體實(shí)施雜交，S1，S2括號(hào)里的數(shù)字為路徑的節(jié)點(diǎn)。如去除首末節(jié)點(diǎn)后，相同節(jié)點(diǎn)有2個(gè)以上時(shí)，則將頭2個(gè)相同節(jié)點(diǎn)來(lái)雜交，雜交點(diǎn)間的節(jié)點(diǎn)交換，生成雜交段。從S1，S2路徑可以看出，除起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)相同外，相同節(jié)點(diǎn)為10、16和20，再選擇起始于終點(diǎn)實(shí)施雜交，最終得到交換后的路徑表達(dá)如下所示。

路徑 S1′={5，4，10，12，14，16，26，20，19}，路徑S2′={5，7，8，10，6，9，16，23，20，19}。

以上使用的雜交規(guī)則不但與復(fù)雜路面邏輯連接性相一致，更是應(yīng)用了雜交運(yùn)算，因此，具有很好的操作性和現(xiàn)實(shí)意義。在雜交后，將前后的路徑長(zhǎng)度做對(duì)比，可以發(fā)現(xiàn)，S1′，S2′代表雜交后路徑，若有S1′≤ Min（S1，S2），或 S2′≤ Min（S1，S2），即可對(duì) S1′或S2′依據(jù)公式（5）來(lái)更新信息素濃度，將更新后的結(jié)果來(lái)替代對(duì)應(yīng)子節(jié)點(diǎn)的最優(yōu)解S1，S2，同時(shí)更新S集，在S集的全部項(xiàng)均完成雜交運(yùn)算后，返回結(jié)果到各自處理器，并完成更新路徑的信息素濃度操作。

根據(jù)上述研究，歸納并行蟻群算法步驟如圖2所示。

以上就是基于改進(jìn)蟻群算法基礎(chǔ)上的平行蟻群算法步驟，不同于串行蟻群算法的是將更新后的結(jié)果來(lái)替代對(duì)應(yīng)子節(jié)點(diǎn)的最優(yōu)解S1，S2，同時(shí)更新S集，在S集的全部項(xiàng)均完成雜交運(yùn)算后，返回結(jié)果到各自處理器，并完成更新路徑的信息素濃度操作。

圖2 平行螞蟻算法步驟

3.2.4 數(shù)據(jù)試驗(yàn)

①改進(jìn)蟻群算法試驗(yàn)

基于人工智能的蟻群算法在動(dòng)態(tài)交通誘導(dǎo)中應(yīng)用廣泛，根據(jù)修正的蟻群算法，采用改進(jìn)的轉(zhuǎn)移概率、信息素濃度更新方法和啟發(fā)函數(shù)等關(guān)鍵影響指標(biāo)，使用較有代表性的廣佛交界的地圖路網(wǎng)實(shí)行規(guī)劃和進(jìn)行仿真動(dòng)態(tài)交通誘導(dǎo)試驗(yàn)并實(shí)證。該路網(wǎng)有20478個(gè)路徑節(jié)點(diǎn)，21795條路段，具有較強(qiáng)的代表性。仿真規(guī)劃路段為節(jié)點(diǎn)編號(hào)949的蘿崗開(kāi)泰大道到節(jié)點(diǎn)編號(hào)5943的廣佛公路，最優(yōu)路徑求解的編程語(yǔ)言使用C語(yǔ)言，基于super map軟件平臺(tái)下進(jìn)行仿真實(shí)驗(yàn)。算法模型中，螞蟻數(shù)r=60，迭代次數(shù) Nmax=50，啟發(fā)因子 α =1，β =3，信息素總濃度Q=30。經(jīng)改進(jìn)蟻群算法計(jì)算，大量試驗(yàn)表明最小路徑收斂曲線見(jiàn)圖3，最佳路徑見(jiàn)圖4。通過(guò)分析和結(jié)果對(duì)比，改進(jìn)后的蟻群算法對(duì)全局最優(yōu)解的搜尋效率更高，可靠性得到很大的提升。

圖3 求得最小路徑的收斂曲線

圖4 最優(yōu)路徑的求解

②蟻群并行算法應(yīng)用實(shí)例分析

本文建立了多個(gè)處理器的試驗(yàn)環(huán)境，對(duì)并行算法的效果進(jìn)行實(shí)證。試驗(yàn)中，路徑初始化參數(shù)、路網(wǎng)出發(fā)點(diǎn)、目標(biāo)點(diǎn)的設(shè)置采用上述串行蟻群算法的設(shè)定，基于多處理器環(huán)境下執(zhí)行并行運(yùn)算。設(shè)置不同數(shù)量的處理器，多次試驗(yàn)和記錄，分析不同數(shù)量處理器下的算法收斂值、計(jì)算所花費(fèi)的時(shí)間。將不同數(shù)量處理器下的算法收斂值、計(jì)算所花費(fèi)的時(shí)間作圖分析，直觀顯示如圖5和圖6所示。

圖5 不同數(shù)量處理器下的算法收斂值

圖6 不同數(shù)量處理器下的算法所花費(fèi)時(shí)間

通過(guò)不同數(shù)量處理器的反復(fù)試驗(yàn)數(shù)據(jù)分析，得到的結(jié)論是處理器的數(shù)目從少到多的遞增，對(duì)應(yīng)的收斂值越小，但計(jì)算時(shí)間是先減少，后增加。在試驗(yàn)中，當(dāng)處理器的數(shù)量為4時(shí)，收斂值時(shí)間花費(fèi)是最少的。處理器的數(shù)量再遞增到6，所花費(fèi)的時(shí)間并非減少，反而是增加，原因是處理器數(shù)量增加，并行蟻群算法的處理器間進(jìn)程信息傳遞及通訊時(shí)間花費(fèi)增大，因而使得總的計(jì)算花費(fèi)時(shí)間增加。對(duì)于收斂值隨著處理器的增加而減少的結(jié)果，原因是處理器數(shù)量增加，算法的搜尋區(qū)域更大，盡管花費(fèi)在搜尋的時(shí)間更多，但最優(yōu)解卻容易得到，可靠性更好。

4 結(jié)束語(yǔ)

并行蟻群算法的動(dòng)態(tài)交通誘導(dǎo)技術(shù)通過(guò)實(shí)驗(yàn)表明，處理器數(shù)量的遞增，實(shí)驗(yàn)結(jié)果的收斂值越小，計(jì)算時(shí)間先減少后增加。收斂值減少證實(shí)并行算法更易于對(duì)解空間進(jìn)一步搜索，發(fā)現(xiàn)全局更佳的最優(yōu)解。計(jì)算時(shí)間先減后增表明，在并行蟻群算法中，處理器增多，處理器間進(jìn)程通信消耗時(shí)間極速增大。在實(shí)際應(yīng)用中，面對(duì)的可能都是跨城市跨省的規(guī)模大和復(fù)雜的路網(wǎng)及狀況，因此，并行蟻群算法的并行處理最優(yōu)值和計(jì)算時(shí)間都有不同程度的提升，但處理器數(shù)量太大就會(huì)以花費(fèi)更多計(jì)算時(shí)間為代價(jià)，故需設(shè)定達(dá)到平衡值的處理器，以提高并行蟻群算法的效率。使得在車(chē)輛間更好實(shí)現(xiàn)組網(wǎng)和傳遞交通誘導(dǎo)信息、安全預(yù)警等，讓駕駛員更早得到預(yù)見(jiàn)并及時(shí)做好安排，使得安全出行更有保障。