基于魚群優化的車載自組織網絡路由算法

羅 龍，胡凱文，盛 麗，孫 罡*，曹可建，虞紅芳

(1. 電子科技大學光纖傳感與通信教育部重點實驗室 成都 611731；2. 國家計算機網絡應急技術處理協調中心 北京 海淀區 100089)

車載自組織網絡(vehicular Ad Hoc networks,VANET)是由車輛和路邊基礎設備(road side units,RSU)組成的新一代移動多跳自組織網絡。VANET[1]中的各節點通過信息交互，為系統提供包括道路狀況(車禍、道路損壞、車輛擁堵等)、可用資源(可充電電源、空閑停車位等)、周期信標(車輛節點基本必要通信消息)等在內的多種消息。近年來，車載自組織網絡得到了快速發展，已成為智能交通系統的關鍵技術之一[2]。

VANET在安全、運輸效率和信息娛樂方面都存在大量潛在的應用[3]。VANET的早期應用大多是為了提高交通安全。近年來，在專用短程通信技術[4](dedicated short range communication, DSRC)頻譜上，美國聯邦通信委員會(federal communications commission, FCC)預留的頻段在被交通安全相關應用使用后仍有大量剩余，于是許多其他應用相繼出現[5]。如VANET在交通控制和道路維護系統中的實時數據收集[6]、自動化控制、智能收費、增強導航[7]以及一些特定的位置服務、音視頻傳輸、各種移動端的娛樂服務[5]等各方面都發揮了至關重要的作用。因此，優化VANET通信技術對更安全、更方便智能的交通具有重要意義。

然而，VANET中的節點具有高速移動的特性，網絡拓撲時變性強，使用傳統路由方法將導致極低的數據包傳輸成功率[8-9]。如文獻[10]已經證實在車輛通信半徑為250 m、平均速度為100 km/h的道路上，節點間的通信鏈路存在15 s的概率僅為57%。此外，在發生交通事故、路面損壞等緊急情況時，消息無法及時傳輸將帶來非常嚴重的后果[11]。因此，研究適用于VANET的可靠高效路由算法很有必要。

針對VANET中對時延敏感的消息的傳輸需求，本文提出一種基于魚群優化的車載自組織網絡路由算法。面對VANET動態變化的網絡拓撲和網絡擁塞情況，節點通過及時感知鄰居節點當前發送隊列是否擁塞、鄰居節點是否可靠、鄰居節點位置等周圍環境的變化進行判斷，選擇消息傳輸的最優中繼。

1 相關工作

隨著萬物智聯的發展，VANET的需求越來越多[12]，其路由算法研究成為了近年來網絡領域的熱點話題。在早期的移動自組織網絡(mobile Ad Hoc network, MANET)研究中，研究者們提出了基于位置的路由算法GPSR[13]、動態源路由算法DSR[14]、源驅動路由算法AODV[15]等經典協議。近年來，越來越多的研究者將仿生學模型應用到VANET中，提出了基于蛛網模型的路由算法[16-17]、基于蟻群優化模型的路由算法[18]、基于微生物的啟發式路由算法[19]等很多性能優越的算法。

文獻[16]提出以源節點所在路口為中心建立蛛網模型，在消息傳輸前發送探測消息探索蛛網，找到通往目的地的最優路徑。在此基礎上，文獻[17]使用路邊停駐車輛作為輔助進一步優化了蛛網模型的性能。文獻[18]利用蟻群優化模型，通過蟻群探測消息讓網絡中的節點能夠及時感知到周圍路段情況，從而選出到達目的地的最優路徑。文獻[19]基于微生物模型對傳輸的歷史反饋消息進行學習。文獻[13]提出了VANET中一種經典的路由算法，該算法主要以貪心思想讓當前節點在選擇下一跳中繼時總是選擇距離目的節點最近的鄰居節點作為中繼。目前，很多研究工作仍以該算法為基準進行對比和參考。

在最近的研究中，研究者們考慮了VANET拓撲動態變化的特征，并針對該特征設計出了許多模型來提升路由性能。本文基于魚群優化這一仿生模型，面向VANET中時延敏感類消息的傳輸提出一種新穎的路由算法，能夠在保證消息傳輸成功率的同時，進一步優化傳輸時延，提升VANET的路由性能。

2 魚群優化模型

人工魚群算法(artificial fish swarm algorithm，AFSA)[20]是通過模仿魚類覓食、跟隨、聚集行為的智能優化算法，具有收斂速度快、效率高等優點。

覓食行為(prey)：如圖1所示，魚類通過視覺感知水中食物濃度決定移動方向進行覓食行為。

圖1 魚類覓食示意圖

在覓食行為中，假設某條魚所在環境當前狀態為Xi，食物濃度為F(Xi)，在其視野范圍(Di,j＜Visual)內隨機尋找環境狀態為Xj：

如果F(Xi)＜F(Xj)，則按照式(2)朝Xj的方向前進一步。

否則，重新隨機選擇狀態Xj，并判斷是否滿足前進條件。如果多次搜索后仍未找到合適的Xj，則按照式(3)隨機移動一步。

跟隨行為(follow)：在魚類覓食的過程中，當一條魚或者幾條魚找到食物時，其他伙伴會跟隨而來。假設當前一條魚所在環境狀態為Xi，在其視野范圍內(Di,j＜Visual)探索鄰域伙伴所在位置Xj的食物濃度F(Xj)，尋找使得F(Xj)最大的Xj(即該伙伴已找到食物濃度較高的區域)。如果F(Xj)＜F(Xi)且Nj/Ni＜δ(Nj為Xj區域內魚的數量，N為魚的總數，δ為擁擠因子)，表示Xj食物濃度較高且不太擁擠，魚將按照式(2)向位置Xj前進一步；否則找尋次優的Xj，多次嘗試后仍無法找到時，執行覓食行為。

聚集行為(swarm)：描述了魚群會聚集在食物附近的現象。設魚當前所在環境為Xi，在其視野范圍內(Di,j＜Visual)探索伙伴數量Nc及其中心位置Xc。如果Xc所在位置的食物濃度F(Xc)＜F(Xi)且Nc/Ni＜δ，表示該伙伴群中心食物濃度較高且不太擁擠，魚將按照式(4)向位置Xc前進一步；否則找尋次優的Xc，當多次嘗試后仍無法找到時，執行覓食行為。

隨機行為(random)：當魚群無法找到食物濃度較高的鄰域時會在視野內隨機移動，是覓食行為的一個缺省行為。

3 系統模型及路由算法設計

3.1 VANET系統建模

本模型將一片區域內由車輛組成的自組織網絡類比作一片水域，并將負載較輕、傳輸成功率高的車輛視為食物。網絡中車輛會定時產生包含通信范圍的消息，這些消息看作魚群輔助消息 (fish message, FM)。魚類前進的每一步視作FM從當前節點到下一個節點之間的一跳傳輸。每輛車有設備負載狀態θ和傳輸成功率μ兩個狀態參數。食物濃度可以由式(5)計算得到，其中α和β分別為設備負載情況和設備傳輸成功率的權重。

當F(Si)大于閾值γ時，車輛Si為食物車輛。

3.1.1 覓食行為

當網絡中各車輛設備狀態空閑、傳輸成功率高時，如圖2所示，以S1為例，根據魚群算法，FM在S1處執行覓食行為。根據其鄰居狀態表1：θ2=θ3，μ2=μ3。在S1處，根 據 式(5)得 到F(S2)=F(S3)＞γ，S2和S3均為食物節點。S1處的FM認為找到了兩個食物節點，將S2和S3添加到優先集合P當中。

圖2 網絡空閑時道路車輛情況

表1 S1鄰居狀態表

此時，FM會以式(6)給出的概率游向找到的某一食物節點：

式中，N為所有滿足F(Sj)＞γ的鄰居車輛組成的集合；Np為優先集合；δi為Si對應的擁擠因子，δi由式(7)計算得到：

FM在到達食物節點后會判斷當前區域是否擁擠。若不擁擠，則停留在此處；反之，執行隨機行為，并攜帶當前車輛是食物節點的消息，隨機游向任意鄰居。概率由均勻分布的概率密度函數式給出：

式中，Nnei為鄰居數量。

擁擠因子有助于避免所有FM聚集在一個食物節點上。如果車輛周邊有多個食物節點，受擁擠因子的影響，FM會平衡地流向這些食物節點，為正常消息的傳輸提供更多選擇，避免正常消息全部流向同一個食物節點，浪費其他食物節點的資源，造成算法的局限性。同時，在聚集了一定的FM后，食物節點會將后續FM攜帶其相關信息后隨機轉發出去，從而使周圍的鄰居都能感知到該食物節點，并將后續的業務消息交由該食物節點轉發。

當網絡發生擁塞時，如圖3所示，假定車輛S3設備負載較高，FM在執行覓食行為時發現θ3＜θ2，F(S3)＜γ＜F(S2)。S1更新優先集合，S2仍為食物節點，S3退出優先集合。此時S1處的FM會游向S2。為了提升模型容錯率，如果S1還有其他鄰居的食物濃度比較高且大于γ，那么FM會以式(6)的概率來選擇前進方向。

圖3 網絡擁塞時道路車輛情況

在網絡拓撲發生變化時，如圖4所示，車輛S5在行駛過程中導致S3-＞S5鏈路中斷，S3的丟包率增加，此時μ2＞μ3，F(S2)＞γ＞F(S3)。更新優先集合，S2仍為食物節點，S3退出優先集合。如果在S1處還有其他鄰居處的食物濃度大于γ，FM仍以式(6)的概率選擇前進方向。

圖4 網絡拓撲變化時情況

算法1：FM的覓食行為

車輛S0、魚群消息FM、優先集合P、S0鄰居集合N(S1,S2,···,Sj)、擁擠因子δ、食物濃度和擁擠因子閾值γ、σ

3.1.2 跟隨行為和聚集行為

跟隨行為描述的是魚類會跟隨已找到食物的伙伴的軌跡的現象。聚集行為則是指魚類會聚集在食物濃度較高的區域，其本質也是跟隨行為導致的。因此，本模型將兩種行為統一稱作跟隨行為。

如前文所述，FM在S1處通過覓食行為成功找到一個或多個食物節點后，會將食物節點添加到優先集合中并為其設置擁擠因子δ。對于后續到達S1處的FM，直接根據優先集合判斷前進方向。在優先集合中，元素是伙伴已選擇的方向，往往食物濃度比較高，且元素數量遠小于鄰居表，因此，跟隨行為在提高搜索效率的同時，可以讓后續FM更快地發現食物節點。如算法2所示，如果優先集合里有一個或者多個方向可供選擇，FM會根據式(6)給出的概率來選擇前進方向。如果優先集合中沒有元素，表示之前沒有伙伴找到食物，無法跟隨，此時執行覓食行為。

算法2：FM的跟隨行為

車輛S0、魚群消息FM、優先集合P、S0鄰居集合N(S1,S2,···,Sj)

if(P≠φ)

FM以式(6)給出的概率游向某一鄰居Sj

else

執行覓食行為

end if

3.1.3 擴散行為

為更好地適應VANET動態變化的網絡環境，本模型在魚群優化的基礎上增加一個仿生學行為：擴散行為。該行為描述的是在食物濃度較高的區域內，食物由于魚群的聚集很快被消耗殆盡后，魚群擴散并重新尋找食物的行為。本模型中，食物節點在未來一段時間內會承載當前區域內大部分的中繼任務，導致設備負載增加和傳輸效率降低。另外，當網絡拓撲改變時(鄰居車輛駛離食物節點的通信范圍)，食物節點在接收消息后無法轉發，也會導致傳輸成功率降低。在這些情況下，聚集的FM認為食物被消耗殆盡，執行擴散行為并重新尋找食物。周圍節點收到擴散的FM后獲知該食物節點已失效，將更新自身優先集合并重新選擇業務消息的中繼。

算法3：FM的擴散行為

車輛S0、魚群消息FM、優先集合P、食物濃度閾值γ

if(F(S0)＜γ)

聚集在S0處的所有FM攜帶S0的狀態執行覓食行為并擴散

end if

3.2 路由算法描述

基于3.1節中的VANET系統模型，本文的路由算法的主要步驟如下：當通信需求產生時，源車輛S0首先判斷目的車輛D是否在通信范圍內，若是，則直接將消息發給目的點，路由結束；反之，執行以下步驟進行路由。

1)選擇第一代候選節點：為使消息每一跳傳輸都在向目的節點靠近的方向上進行，當某鄰居節點Sj與目的節點之間的距離 d isSjD小于源節點和目的節點之間的距離disSD時，將Sj添加到第一代候選節點集合Q(S1,S2,···)中。若Q為空，為避免消息向遠離目的節點的方向傳輸而出現回傳和成環的問題，將直接丟棄數據包；若Q不為空，執行步驟2)。

2)選擇第二代候選節點：為使消息傳輸經過的跳數盡量小，每次選擇時應滿足以下兩個原則：1)鄰居節點Sj和目的節點D之間的距離 d isSjD盡量小。如圖5所示，S0向D發送消息時將選擇S2以避免增加不必要的跳數；2)源節點S0往鄰居節點Sj的方向S0→Sj與源節點S0往目的節點D的方向S0→SD之間的夾角ω盡量小。如圖6所示，S0在向目的車輛D發送消息時，將在通信半徑范圍內選擇S2或者S3，從而避免傳輸方向擴散和偏離目標車輛。

圖5 原則1示意圖

圖6 原則2示意圖

本文綜合考慮d isSjD和ω兩個因素，使用TOPSIS方法[21]從集合Q(S1,S2,···,Sm)中選出第二代候選節點集合T(S1,S2,···,Sn)(n＜m)。TOPSIS是一種通過對現有的對象進行相對優劣評價而逼近理想解的排序法。假設集合Q中有m輛車，各車輛的距離夾角參數如表2所示。

表2 距離夾角參數表

對于 disSjD和ω兩個評價指標，建立如下特征矩陣：

對特征矩陣進行規范化處理，利用式(9)計算得到規范化矩陣元素rij：

為以上兩個評價指標分別設置權重τ1和τ2，由式(10)計算權重規范化矩陣元素：

式中，i=1,2,···,m；j=1,2。

根據權重規范化矩陣，計算每個指標的最優解和最劣解。由于距離更短和夾角更小的目標更優，因此，權重規范化矩陣中各列的最小值即為最優解：

式中，i=1,2,···,m。

可以根據式(12)計算出集合Q中車輛的兩個評價指標與其對應的最優解和最劣解的距離：

集合Q中每輛車的最終得分為：

將選擇得分較大的前n位加入到第二代候選集合T(S1,S2,···,Sn)中。這些候選節點能夠較好地避免消息傳輸中的無意義傳輸，同時保證每一次傳輸都盡量向目的節點靠近。

3)選擇最優中繼：引入魚群優化模型后，算法得到優先集合P，通過選擇T∩P中的元素可找到通往目的節點方向上的食物節點，將消息交給負載較輕、傳輸成功率高的食物節點進行中繼，從而提升路由性能。若T∩P=φ，查詢鄰居狀態表，根據式(5)計算鄰居食物濃度，選出當前非食物節點中食物濃度最大的節點。若T∩P≠φ，計算Si∈T∩P，根據式(5)選出Si中食物濃度最大的節點。最后，將業務消息交給選出的鄰居Sj，Sj收到消息后執行新一輪路由算法選擇下一跳中繼。

算法4：消息路由算法

車輛S0收到需要轉發業務消息MSG

目的車輛D、優先集合P

S0鄰居集合N(S1,S2,···,Sj)

if(D不在S0的通信半徑內)

4 仿真實驗與結果分析

4.1 仿真實驗設計

本文在SUMO[16,22-23]上建立道路車輛模型，使用Veins[22-23]框架在網絡仿真平臺OMNET[22-23]上搭建實驗環境。表3給出了實驗中使用的主要參數。仿真實驗采用圖7中所示的2 km × 2 km地圖[15]。

圖7 仿真地圖

表3 仿真實驗參數設置

4.2 結果分析

為了評估算法性能，實驗將本文算法FSR與基于仿生學的VANET路由算法PASRP[17]、URAS[19]及經典的VANET路由算法GPSR[13]進行了對比。

4.2.1 消息平均到達時延

圖8展示了消息平均到達時延隨車輛密度變化的結果。這部分實驗中的控制業務消息產生速率為10(個/s)。仿真結果顯示，本文算法FSR優于其他3種對比算法?？傮w而言，隨著車輛密度增加，時延呈上升趨勢。這是因為更多的消息能夠到達目的點，不會在中途被丟棄。另外，在車輛密度低時，PASRP的平均到達時延略高于GPSR，這是因為PASRP需要等待探測消息的回饋才能為業務消息規劃路由。

圖8 消息平均到達時延對比

圖9展示了消息平均到達時延隨業務消息產生速率變化的結果。這部分實驗中的控制車輛密度為75輛/km2。仿真結果顯示，本文算法FSR優于其他3種對比算法。隨著業務消息的增多，時延呈遞增趨勢。

圖9 消息平均到達時延對比

以上兩組實驗結果都展示了FSR在降低VANET的消息傳輸時延方面的性能最優，這得益于基于魚群優化的設計。

4.2.2 消息到達率

圖10展示了控制業務消息產生速率為10個/s時，消息到達率隨車輛密度改變的實驗結果。FSR的消息到達率略高于其他對比算法。這是因為FSR引入了魚群優化模型，節點可以動態找到周圍傳輸成功率高的節點轉發消息，從而更有效地保證了消息到達率。當車輛密度足夠大的時候，FSR的性能略差于PASRP，這是因為PASRP建立了完整路由，能夠更好地保證消息到達率。

圖10 消息到達率對比

圖11展示的是控制車輛密度為75輛/km2時，消息到達率隨業務消息產生速率變化的實驗結果。以上兩組仿真實驗結果顯示，FSR能夠保證較高的消息傳輸成功率。

圖11 消息到達率對比

4.2.3 通信開銷

通信開銷定義為傳輸一個業務消息所需輔助控制消息的平均字節數。圖12展示了控制業務消息產生速率為10個/s時，通信開銷隨車輛密度變化的情況?？偟膩碚f，FSR和PASRP的通信開銷高于GPSR和URAS。這是因為FSR需要網絡中存在一定數量的魚群消息，而PASRP則需要發送一定的蛛網探測消息以建立完備的路由。當車輛密度較低時，產生的輔助控制消息較少，成功到達的業務消息也較少。隨著車輛密度增加，周期消息與輔助消息增加，成功到達的業務消息增加，此時通信開銷會短暫上升。但隨著車輛數量進一步增加，成功傳輸的業務消息增長速率將高于輔助控制消息的增長速率，此時通信開銷會呈現遞減趨勢。

圖12 通信開銷對比

圖13展示了控制車輛密度為75輛/km2時，通信開銷隨業務消息產生速率變化的情況。實驗結果顯示，FSR與PASRP的開銷大致相當。當業務消息數量較少時，FSR的通信開銷低于GPSR和PASRP，這是由于此時網絡擁塞情況較少，需要的魚群輔助消息較少。當業務消息數量增多時，網絡擁塞情況隨之變嚴重，為了保持傳輸性能需要的魚群輔助消息也會增加，此時FSR的通信開銷會高于GPSR和PASRP。

圖13 通信開銷對比

以上實驗結果表明，本文所提的FSR算法能夠在增加少量通信開銷的前提下，顯著改善VANET中消息到達的平均時延和消息到達率。

5 結 束 語

本文將魚群優化模型嵌入到車載自組織網絡當中，提出了基于魚群優化的VANET路由算法FSR。FSR通過魚群快速搜索到節點附近區域內傳輸性能較好的鄰居，在正常業務消息傳輸時及時利用這些節點提高傳輸性能。同時，在VANET網絡情況和拓撲頻繁改變下，魚群優化模型也能夠以較快的速度再次搜索到新的食物節點。本文提出的方案能夠契合車載自組織網絡的特點，提升路由性能。