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

彭康華，楊軍，黃裕鋒

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

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

1 基礎硬體配置

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

2 組網(wǎng)設計技術

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

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

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

300Byte×8bit/Byte×Byte×30輛車×10幀=720kbit。

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

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

3.1 車輛定位交通信息傳輸?shù)膶崿F(xiàn)

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

3.2 改進蟻群算法動態(tài)交通誘導實時服務

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

3.2.1 基本蟻群算法模型

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

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

3.2.2 修正的蟻群算法

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

①改進的轉移概率方法

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

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

②改進的信息素濃度更新方法

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

而全局的更新方法見公式（4）所示。

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

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

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

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

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

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

圖1 改進的螞蟻算法步驟

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

3.2.3 動態(tài)交通誘導服務的并行計算法

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

①并行計算模型

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

②改進并行蟻群算法模型設計

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

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

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

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

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

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

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

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

圖2 平行螞蟻算法步驟

3.2.4 數(shù)據(jù)試驗

①改進蟻群算法試驗

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

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

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

②蟻群并行算法應用實例分析

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

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

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

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

4 結束語

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