車載自組網中一種自適應粒子群算法的研究

周杰英，彭石，劉映淋，許楊鵬

（中山大學電子與信息工程學院，廣州 510006）

車載自組網中一種自適應粒子群算法的研究

周杰英，彭石，劉映淋，許楊鵬

（中山大學電子與信息工程學院，廣州 510006）

車載自組網又稱VANET，具有車輛節點高速移動、拓撲變化快、通信鏈路不穩定等特點。傳統路由協議不能很好適應動態多變的車載環境，所提出的自適應路由協議方法在相鄰網絡節點間建立馬爾科夫鏈路信息表RLM，然后利用改進的粒子群路由算法選擇數據包傳遞經過的下一跳節點；實驗仿真表明，采用RLM監控機制有效解決VANET網絡中傳輸鏈路不穩定的問題，減少數據包丟包的發生概率，而使用粒子群路由算法有效降低數據包傳輸時出錯的概率，降低時延，從而提高分組投遞率。

VANET；粒子群算法；時延；連通性

0 引言

車載自組織網絡VANET（Vehicular Ad Hoc Network）是一種由若干個移動的具有接收和發送功能的無線節點構成的自適應網絡，其便捷、靈活、自組織的特性彌補了固定網絡的不足，因此VANET通信網絡在軍事和民用領域具有廣泛的用途。由于VANET之中的節點需要在沒有任何預設的基礎設施的情況下完成通信，不僅需要充當信源和信宿節點，還需要充當路由器對其他節點發送的分組進行轉發，因此需要有合適的路由協議實現這些功能[1-2]。

現有的路由協議如AODV[3]，GPSR[4]，DSR[5]通過特定的策略動態選擇一條從源節點到目的節點的路徑，具有簡單、可靠性高、易于實現等特點。但由于VANET之中的節點隨著車輛高速移動，網絡拓撲結構變化頻繁，通信鏈路割裂嚴重，此外復雜多變的城市環境等特點使傳統的Ad Hoc路由協議直接運用在VANET上的效果很不理想[6]，所以，目前提出了很多改進的路由算法。文獻[7]針對車載自組網之中現有的GPSR協議存在網絡擁塞的問題，提出了一個改進的GPSR協議，利用節點的緩沖區來控制網絡擁塞；文獻[8]針對AODV路由算法存在控制開銷大、路由發現和修復時間長等不足，為此，對AODV算法進行局部優化，提出一種改進的路由算法，利用節點位置、運動速度等信息預測鏈路失效時間；此外，針對路由網絡之中的難題，提出了許多基于仿生學和群體智能的路由協議。例如，文獻[9]提出了一種利用不同螞蟻群搜索最短路徑而啟發得出的蟻群優化算法。文獻[10]針對在高移動性的的Ad Hoc網絡之中，存在高時延，能量消耗，丟包的問題，提出一個結合粒子群的路由優化算法。文獻[11]在定義了包含鄰居節點信息的粒子適應度函數的基礎上，提出了一種基于離散粒子群（DPSO）的單跳路由分簇協議（DPSOCA）。

本文根據城市交通下VANET的路由特點，提出的APSO路由協議方法通過馬爾科夫鏈模型（Route Link Model，RLM）在相鄰網絡節點間建立網絡狀態概率轉移矩陣，然后利用改進的粒子群優化算法選擇數據包傳遞經過的最佳節點；理論和實驗表明采用該監控機制不僅有效解決了VANET網絡中通信鏈路不穩定的問題，減少了數據包沖突的發生概率，還為數據流量模型預測提供了一個很好的途徑，而使用粒子群路由算法有效降低了數據包傳輸時出錯的概率，降低了時延，從而提高了分組投遞率。

1 相關數學模型研究

1.1 VANET的QoS模型

為方便數學分析，本文將VANET網絡表示為一個無向帶權圖。假設，G=（V，E）代表一個VANET網絡，其中V代表網絡中節點集合，E代表聯系兩個節點路徑的集合。對于每條路徑e∈E，傳輸時延表示為delay（e），對于每一個節點n∈V，處理時延表示為delay（n）；給定一個i∈V和一個j∈V，可以假設path（i，j）代表從i到j的路徑，則路徑上QoS參數可以通過式（1）～式（2）計算。路徑時延delay（path（i，j））等于每個節點的處理時延和每條鏈路的傳播時延總和。參數d（i，j）等于路徑中節點i和j的距離，數據包從源節點傳到目的節點需要經過多跳，通常希望找到一個距離最短的路徑，時延少，路徑節點更加穩定。

1.2 VANET路由鏈路模型RLM

為了在網絡之中維護鏈路信息表，需要當前節點和網絡的若干外圍節點之間保持鏈路聯系。在本文，采用貝葉斯網絡的方法來確定鏈路表的大小。首先，將VANET網絡的拓撲結構表示為一個有向無環圖（DAG），有向無環圖中的節點用隨機變量{x1，x2，…，xn}表示；為了選擇符合要求的路由路徑，需要滿足按照特定順序排列的節點子集{，，…，x}（在本文中n≤5），并要求當n〈m，距離d（x，x）〈d（x，x），這樣一來，REQ包每向外傳輸一次，下一跳節點就離初始節點越遠，初始節點就能夠掌握更多的外圍節點信息。

令G=（I，V）表示實際VANET網絡，其中I代表圖形中所有的節點的集合，而V代表有數據包傳遞的邊集合；設E、H∈I為其有向無環圖中的某兩個隨機節點，將鏈路中節點之間的發包概率看做一個狀態空間，將狀態空間之中任意相鄰的節點E發送數據包到達節點H的聯合概率看作是一個貝葉斯過程：

其中NHE表示E向H節點的發包數量，NH表示經過節點H的發包數量，p（H|E）表示節點E向節點H發送數據包占經過H的數據包總數的概率；為了連接一定范圍之內的節點，因此需要計算若干相連節點的傳輸概率。本文將此表示為一個馬爾科夫過程，利用此模型，就會產生一個路由序列{xi1，xi2，…，xik}。

其中，xik表示當前節點連接的最外層節點xi1表示當前節點，p（xi1，xi2，…，xik）表示節點xi1至xik組成一條鏈路的概率，其由式（4）推導出來。當某個鏈路的概率p（xi1，xi2，…，xik）大于一定的閾值，就會認為該鏈路是穩定可靠的，否則認為該鏈路容易發生斷裂。通過以上方式，VANET網絡中的各個節點動態維護自身的多條鏈路信息，從而實現對外圍節點的監控。

1.3 路徑選擇模型

本文中，VANET網絡采用粒子群算法（PSO）來計算各個節點的相對適應值，并且根據計算結果選擇最佳的下一跳節點。其中各個鄰居節點的相對適應值的計算方式如下：

其中，k表示當前節點的第k個鄰居節點，ΔFk表示第k個鄰居節點和當前節點的相對適應值；慣性權重μ0為常數，μ1和μ2為學習系數；μk定義為vk=1/Nk，Nk是鄰居節點k維護的有效鏈路數目；源節點F初始適應值為0，pbestk代表局部最優值，gbestk全局最優值，定義如下：

其中i代表當前節點，Dt（i，k）代表鄰居節點k和當前節點之間的傳輸時延，Lt（i，k）代表節點k和目的節點之間的空間距離，從式（5）可以看出，vk，pbestk，gbestk越小，ΔFk就越小，代表該節點作為下一跳節點的可能性越大。反之，ΔFk越大，意味著該節點屬于孤立節點，高時延，遠距離。

2 APSO協議實現

在本節給出了自適應粒子群算法APSO的具體設計方案，在該路由協議之中，運動的節點通過維護一條條鏈路信息表來獲知周圍節點的位置速度方向等信息。當源節點需要傳輸數據的時候，如果鏈路信息表中不存在到達目的節點的路由，源節點就會利用APSO算法來查找到達目的節點的最優路徑。所述APSO協議方法包含如下步驟：

（1）監控步驟

A1：網絡中的節點周期性發送包括當前節點信息的路由請求包REQ，鄰居節點收到請求包后利用上文提到的路由鏈路模型RLM計算當前節點和上一跳節點之間的發包概率，建立網絡狀態概率轉移矩陣。該路由請求包的格式如下所示：

其中，Nk為經過的節點數組，Dk為經過的節點位置數組，Vk為經過的節點速度數組，Fk為經過的節點方向數組，Tk為經過的節點時間戳數組，Pk為經過的節點跳數數組，Hk是經過的節點的概率數組；REQ請求包每經過一個節點，都會更新本次傳輸的相關參數到對應數組之中。當最后一次計算的Hk小于某個閾值的時候，當前節點就會將數據包反向發送到起始節點，起始節點就會更新自己的RLM鏈路信息表。本文中REQ包跳數值設置為不大于5，所以默認源節點發送和接收REQ包的傳輸是在瞬時完成的，傳輸時延和處理時延可以忽略不計。

A2：當中間節點收到REQ數據包時，中間節點提取數據包的信息，計算和上一跳節點的聯系概率P，判斷當前的馬爾科夫鏈路概率是否小于預設的閾值，若是則停止轉發數據包，并反向發送REQ數據包到達源節點；否則，中間節點繼續檢查當前數據包是否已經到達本節點，若是則丟棄該數據包，否則中間節點更新自身信息到REQ數據包中，接著選擇符合要求的鄰居節點，繼續向外轉發REQ包；

A3：若源節點收到自外層網絡發來的REQ數據包，源節點提取數據包中的信息，將鏈路信息保存在自身的路由信息表中，并檢查路由表之中是否包含相同的鏈路信息，若包含則更新該鏈路信息；否則將該馬爾科夫鏈保存到路由表之中；若某條鏈路信息過了預定時間沒有更新，則將該鏈路從路由表中刪除。

本文提出的APSO協議通過路由節點網絡和馬爾科夫鏈路在相鄰網絡節點間建立網絡狀態概率轉移矩陣，該監控機制不僅有效解決了VANET網絡中通信鏈路不穩定的問題，減少了數據包沖突的發生概率，還為數據流量模型預測提供了一個很好的途徑。

（2）數據包轉發步驟

B1：需要發送數據的源節點，通過GPS等輔助定位設備得到目的節點的物理位置，然后封裝自己的物理位置，節點地址，唯一性標志號以及目的節點等信息到待發送的數據包之中，并且從自身的鏈路信息表之中，采用自適應粒子群路由算法計算獲得鄰居節點的適應值，選擇適應值最小的節點作為最佳的下一跳節點，并將數據包發送到該節點。

B2：中間節點收到數據包之后，提取數據包內的路由信息。判斷自身是否是目的節點，若是就停止發送數據包，并且發送應答包沿著鏈路路由節點返回到源節點；否則，更新自身節點信息到數據包之內，然后按照上面的方法發送數據包到下一跳節點，直到到達目的節點。

APSO進行分組轉發時，在鏈路信息表的基礎之上，利用自適應粒子群算法來選擇下一跳的路由節點，由于綜合考慮全局和局部的特性，使得所選擇的下一跳更加準確，大大提高了分組投遞率，降低了鏈路之中的時延。

（3）路由修復步驟

C1.當監控步驟中的尋址過程發生丟包時，發生丟包的源節點發送新的REQ請求包到下一跳節點，通過計算新的鏈路狀態概率得到可用的馬爾科夫鏈路；當前節點將新的鏈路信息封裝到路由請求REQ包發送到相鄰的節點，相鄰節點收到路由請求包并重新評估網絡狀態，然后重發尋址數據包。

C2.當數據傳輸過程發生丟包時，若中間節點收不到成功傳輸的應答包，其會更新自身的鏈路信息表，然后從自身的緩存之中提取數據包信息，按照計算得到的結果選擇最佳的下一跳節點，直到數據包到達目的節點。

3 APSO協議仿真

為驗證文中提出的APSO算法的有效性和性能，本節在NS2仿真環境下，通過改變VANET之中的節點數目來觀察APSO，GPSR，AODV協議的延時性能和分組投遞率。節點數目用來模擬VANET網絡的拓撲結構，節點數目越大，表示貝葉斯網絡狀態空間的鏈路數目越多，鏈路斷裂的可能性越小。

仿真環境：Ad Hoc節點隨機放置在1500m×1500m的矩形區域中，節點可以根據IDMIM模型隨機進行移動，最大移動速度為40m/s。節點的最大傳輸范圍為250m，MAC層使用IEEE802.11DCF。數據包大小為512 bytes，數據源為CBR。每次仿真運行900s。算法中的一些參數設置如下：μ0=0.3，μ1=0.3，μ2=0.4，REQ代理發送周期0.5s，路徑更新定時器為1s。仿真結果如下圖所示。

圖1 分組投遞率隨節點數目變化性能仿真結果

圖1，2，是本文的仿真結果圖。從圖1可以看出，當節點數較小的時候，由于車輛的運動，造成路由鏈路經常發生斷裂，因此三者的分組投遞率較低，丟包率較高；但隨著節點數目變大，相對于AODV和GPSR，本文提出的APSO協議的分組投遞率明顯優于前者，因為本文的馬爾科夫鏈路監控機制和APSO算法在VANET大大降低了鏈路斷裂的概率和丟包的概率。從圖2可以看出，隨著節點數目增多，端到端時延逐步降低；當節點數較小的時候，三個協議的端到端時延都較高，這是因為網絡中各個節點的鄰居節點數目很少，導致數據包無法及時傳輸到下一跳節點，造成時延增加；但是APSO的性能依然優于另外兩個，因為APSO綜合考慮了全局和局部的特性，使數據包錯誤發送的概率降低，大大增加了路由的有效性。

4 結語

本文在深入研究已有VANET網絡路由算法的基礎上，建立VANET網絡的鏈路狀態監控機制，通過馬爾科夫鏈路在相鄰的網絡節點之間建立網絡狀態概率轉移矩陣，該監控機制增強了鏈路的穩定性和有效性；在進行分組轉發過程中，采用APSO算法進行下一跳的節點選擇，綜合考慮了全局和局部的特性，使選擇得下一跳更加準確，大大提高了分組投遞率，降低了鏈路之中的時延。

圖2 端到端時延隨節點數目變化性能仿真結果

[1]Zeadally S，Hunt R，Chen Y S，et al.Vehicular Ad Hoc Networks（VANETS）:Status，Results，and Challenges[J].Telecommunication Systems，2012，50（4）:217-241.

[2]Martin-Campillo A，Crowcroft J，Yoneki E，et al.Evaluating Opportunistic Networks in Disaster Scenarios[J].Journal of Network& Computer Applications，2012，36（2）:870-880.

[3]Verma V K，Singh S，Pathak N P.Analysis of Scalability for AODV Routing Protocol in Wireless Sensor Networks[J].Optik-International Journal for Light and Electron Optics，2014，125（2）:748-750.

[4]Karp B.Greedy Perimeter Stateless Routing for Wireless Networks[J]，2000.

[5]Johnson D B，Maltz D A.Dynamic Source Routing in Ad Hoc Wireless Networks[C].Mobile Computing.1996:153-181.

[6]Viriyasitavat W，Bai F，Tonguz O K.Dynamics of Network Connectivity in Urban Vehicular Networks[J].IEEE Journal on Selected Areas in Communications，2011，29（3）:515-533.

[7]Hu T，Liwang M，Huang L，et al.An Enhanced GPSR Routing Protocol Based on the Buffer Length of Nodes for the Congestion Problem in VANETs[C].International Conference on Computer Science&Education,2015:416-419.

[8]夏梓峻，劉春鳳，趙增華，等.基于鏈路預測的VANET路由算法[J].計算機工程，2012，38（4）:110-111.

[9]Nishitha T，Reddy P C.Performance Evaluation of AntHocNet Routing Algorithm in Ad Hoc Networks[C].International Conference on Computing Sciences，2012:207-211.

[10]K.D.Kalambe，A.R.Deshmukh，S.S.Dorle.Particle Swarm Optimization Based Routing Protocol for Vehicular Ad Hoc Network International Journal of Engineering Research and General Science Volume 3，Issue 1，January-February，2015 ISSN 2091-2730

[11]鄒學玉，曹陽，劉徐迅，等.基于離散粒子群的WSN分簇路由算法[J].武漢大學學報理學版，2008，54（1）:99-103.

周杰英，女，博士，副教授，研究方向為無線自組織網絡、Mesh網絡

彭石（1988-），男，湖北人，研究生，研究方向是網絡協議

劉映淋（1991-），男，廣東人，研究生，研究方向為Ad Hoc

許楊鵬（1993-），男，湖南人，研究生，研究方向為軟件、網絡

Research on an Adaptive Particle Swarm Optimization Algorithm in VANET

ZHOU Jie-ying，PENG Shi，LIU Ying-lin，XU Yang-peng

（School of Electronics and Information Technology，SYSU，Guangzhou 510006）

Characteristics such as high speed,changing network topology and unstable communication link exist in the design of VANET routing protocols.Traditional protocols cannot adapt to the dynamic environment of VANET.Proposes a routing protocol based on Markoff route link model between adjacent nodes and uses a novel particle swarm optimization algorithm to select the optimum node that the packet passes through.Simulation results show that the monitoring mechanism solves the problem of unstable communication link in VANET,reduces the probability of packet loss.And the improved particle swarm optimization algorithm can effectively reduce the probability of transmission error.The delay is reduced and packet delivery ratio of the network is improved.

VANET;APSO;Delay;Connectivity

1007-1423（2017）11-0026-05

10.3969/j.issn.1007-1423.2017.11.005

2017-01-20

2017-03-12

廣東省省級科技計劃項目（No.2015A010103007）