彭康華，楊軍，黃裕鋒

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

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

1 基礎(chǔ)硬體配置

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

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

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

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

上述的數(shù)據(jù)幀構(gòu)成，附帶車輛身份認(rèn)證信息、幀頭和幀尾、校驗(yàn)位等，每幀總共設(shè)定為300bit。在實(shí)際應(yīng)用中，與每輛車發(fā)送幀相關(guān)的汽車，通常為附近的接收車輛，設(shè)定附近車輛為30輛，根據(jù)該車輛密度控制發(fā)射功率，以IEEE802.11p為基礎(chǔ)，假設(shè)每車發(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)交通信息服務(wù)

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

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

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

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

3.2.1 基本蟻群算法模型

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

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

3.2.2 修正的蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

①并行計算模型

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

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

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

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

設(shè)定有m個處理器，主處理器已接收來自從處理器的最優(yōu)解，S={S1，S2，…，Sm}，其中 Sm代表第m個處理器求得的最優(yōu)解，接下來是使用雜交算子方法來分析和處理該最優(yōu)解。上述的算法中，結(jié)合路網(wǎng)的實(shí)際，使用了啟發(fā)式雜交算子，通過實(shí)驗(yàn)案例來表達(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括號里的數(shù)字為路徑的節(jié)點(diǎn)。如去除首末節(jié)點(diǎn)后，相同節(jié)點(diǎn)有2個以上時，則將頭2個相同節(jié)點(diǎn)來雜交，雜交點(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í)意義。在雜交后，將前后的路徑長度做對比，可以發(fā)現(xiàn)，S1′，S2′代表雜交后路徑，若有S1′≤ Min（S1，S2），或 S2′≤ Min（S1，S2），即可對 S1′或S2′依據(jù)公式（5）來更新信息素濃度，將更新后的結(jié)果來替代對應(yīng)子節(jié)點(diǎn)的最優(yōu)解S1，S2，同時更新S集，在S集的全部項(xiàng)均完成雜交運(yùn)算后，返回結(jié)果到各自處理器，并完成更新路徑的信息素濃度操作。

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

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

圖2 平行螞蟻算法步驟

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

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

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

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

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

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

本文建立了多個處理器的試驗(yàn)環(huán)境，對并行算法的效果進(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ù)量處理器下的算法收斂值、計算所花費(fèi)的時間。將不同數(shù)量處理器下的算法收斂值、計算所花費(fèi)的時間作圖分析，直觀顯示如圖5和圖6所示。

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

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

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

4 結(jié)束語

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