車載自組網信息服務與動態交通誘導算法研究

彭康華，楊軍，黃裕鋒

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

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

1 基礎硬體配置

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

2 組網設計技術

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

表1 IEEE802.11p數據幀構成

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

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

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

3 車聯網交通信息服務

3.1 車輛定位交通信息傳輸的實現

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

3.2 改進蟻群算法動態交通誘導實時服務

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

3.2.1 基本蟻群算法模型

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

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

3.2.2 修正的蟻群算法

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

①改進的轉移概率方法

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

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

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

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

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

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

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

③改進的啟發函數

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

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

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

圖1 改進的螞蟻算法步驟

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

3.2.3 動態交通誘導服務的并行計算法

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

①并行計算模型

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

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

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

③改進并行蟻群算法模型實現

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

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

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

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

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

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

圖2 平行螞蟻算法步驟

3.2.4 數據試驗

①改進蟻群算法試驗

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

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

圖4 最優路徑的求解

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

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

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

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

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

4 結束語

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