車載自組網(wǎng)中一種自適應(yīng)粒子群算法的研究

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

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

車載自組網(wǎng)中一種自適應(yīng)粒子群算法的研究

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

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

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

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

0 引言

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

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

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

1 相關(guān)數(shù)學模型研究

1.1 VANET的QoS模型

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

1.2 VANET路由鏈路模型RLM

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

令G=（I，V）表示實際VANET網(wǎng)絡(luò)，其中I代表圖形中所有的節(jié)點的集合，而V代表有數(shù)據(jù)包傳遞的邊集合；設(shè)E、H∈I為其有向無環(huán)圖中的某兩個隨機節(jié)點，將鏈路中節(jié)點之間的發(fā)包概率看做一個狀態(tài)空間，將狀態(tài)空間之中任意相鄰的節(jié)點E發(fā)送數(shù)據(jù)包到達節(jié)點H的聯(lián)合概率看作是一個貝葉斯過程：

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

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

1.3 路徑選擇模型

本文中，VANET網(wǎng)絡(luò)采用粒子群算法（PSO）來計算各個節(jié)點的相對適應(yīng)值，并且根據(jù)計算結(jié)果選擇最佳的下一跳節(jié)點。其中各個鄰居節(jié)點的相對適應(yīng)值的計算方式如下：

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

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

2 APSO協(xié)議實現(xiàn)

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

（1）監(jiān)控步驟

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

其中，Nk為經(jīng)過的節(jié)點數(shù)組，Dk為經(jīng)過的節(jié)點位置數(shù)組，Vk為經(jīng)過的節(jié)點速度數(shù)組，F(xiàn)k為經(jīng)過的節(jié)點方向數(shù)組，Tk為經(jīng)過的節(jié)點時間戳數(shù)組，Pk為經(jīng)過的節(jié)點跳數(shù)數(shù)組，Hk是經(jīng)過的節(jié)點的概率數(shù)組；REQ請求包每經(jīng)過一個節(jié)點，都會更新本次傳輸?shù)南嚓P(guān)參數(shù)到對應(yīng)數(shù)組之中。當最后一次計算的Hk小于某個閾值的時候，當前節(jié)點就會將數(shù)據(jù)包反向發(fā)送到起始節(jié)點，起始節(jié)點就會更新自己的RLM鏈路信息表。本文中REQ包跳數(shù)值設(shè)置為不大于5，所以默認源節(jié)點發(fā)送和接收REQ包的傳輸是在瞬時完成的，傳輸時延和處理時延可以忽略不計。

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

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

本文提出的APSO協(xié)議通過路由節(jié)點網(wǎng)絡(luò)和馬爾科夫鏈路在相鄰網(wǎng)絡(luò)節(jié)點間建立網(wǎng)絡(luò)狀態(tài)概率轉(zhuǎn)移矩陣，該監(jiān)控機制不僅有效解決了VANET網(wǎng)絡(luò)中通信鏈路不穩(wěn)定的問題，減少了數(shù)據(jù)包沖突的發(fā)生概率，還為數(shù)據(jù)流量模型預測提供了一個很好的途徑。

（2）數(shù)據(jù)包轉(zhuǎn)發(fā)步驟

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

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

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

（3）路由修復步驟

C1.當監(jiān)控步驟中的尋址過程發(fā)生丟包時，發(fā)生丟包的源節(jié)點發(fā)送新的REQ請求包到下一跳節(jié)點，通過計算新的鏈路狀態(tài)概率得到可用的馬爾科夫鏈路；當前節(jié)點將新的鏈路信息封裝到路由請求REQ包發(fā)送到相鄰的節(jié)點，相鄰節(jié)點收到路由請求包并重新評估網(wǎng)絡(luò)狀態(tài)，然后重發(fā)尋址數(shù)據(jù)包。

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

3 APSO協(xié)議仿真

為驗證文中提出的APSO算法的有效性和性能，本節(jié)在NS2仿真環(huán)境下，通過改變VANET之中的節(jié)點數(shù)目來觀察APSO，GPSR，AODV協(xié)議的延時性能和分組投遞率。節(jié)點數(shù)目用來模擬VANET網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，節(jié)點數(shù)目越大，表示貝葉斯網(wǎng)絡(luò)狀態(tài)空間的鏈路數(shù)目越多，鏈路斷裂的可能性越小。

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

圖1 分組投遞率隨節(jié)點數(shù)目變化性能仿真結(jié)果

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

4 結(jié)語

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

圖2 端到端時延隨節(jié)點數(shù)目變化性能仿真結(jié)果

[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.

周杰英，女，博士，副教授，研究方向為無線自組織網(wǎng)絡(luò)、Mesh網(wǎng)絡(luò)

彭石（1988-），男，湖北人，研究生，研究方向是網(wǎng)絡(luò)協(xié)議

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

許楊鵬（1993-），男，湖南人，研究生，研究方向為軟件、網(wǎng)絡(luò)

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）