基于GAPSO-ANFIS的VANET路由性能推理系統

師亞莉，黃 楠，楊軍華，楊 志

(西安郵電大學 電子工程學院，陜西 西安 710121)

車輛自組織網絡(Vehicular Ad-Hoc Network，VANET)是智能交通體系中車間通信的一種移動性自組織網絡，具有無中心、自組織及多跳等特點[1]。作為VANET網絡關鍵技術之一的路由技術，主要負責信息傳輸通道的優化，而VANET通信的拓撲結構變化頻繁、節點移動性高和鏈路生存時間短等特點，使得車輛節點在市區和郊區來回切換時對VANET路由性能的質量影響較大[2]，VANET應用的多樣性和場景的多變性使得單一路由機制不再適用。因此，良好的路由協議可以保障網絡互通性和通信的穩健性[3]。

VANET中有很多路由協議用來穩定和高效地傳遞消息。文獻[4]對VANET路由協議在不同網絡場景中的性能表現進行了研究，結果顯示，主動式路由協議和被動式路由協議在不同場景下性能差異較大，表明了選取最優路由機制的必要性，但文獻中并沒有對選取最優路由協議進一步研究。為了使不同機制的VANET路由協議能在適用的場景中發揮最大性能，路由機制選擇中引入了自適應策略，試圖通過推理為當前網絡環境匹配最適合的路由機制，從而增強網絡通信質量。

文獻[5]提出了一種自適應的路由算法。該算法可以根據網絡的移動性推理當前適配的路由機制，然后根據推理的結果在主動式路由機制和被動式路由機制中進行切換，這種方式有利于同時結合兩種路由機制的優點，提高網絡效率。在文獻[6]中提出的一種自適應路由機制中，由基站基于網絡能量和負載對當前的路由機制進行管理，實現了自適應路由機制的切換。呂雙玥[7]提出了自適應組播路由協議選擇算法，該算法在自適應模糊神經推理算法(Adaptive Neuro-Fuzzy Inference System，ANFIS)的基礎上提出了一種改進型算法，并將其用于路由協議選擇策略庫中，實現了不同場景中最優組播路由協議的選取。文獻[8]將ANFIS應用于VANET網絡中交叉路口場景下的路由選擇，利用網絡特征對最優路由進行推導，進一步提高了網絡的整體性能，但僅考慮了車輛在交叉路口時的路由選擇情況，無法滿足車輛在實際場景中面臨的多種場景。

在以上車聯網場景自適應路由的研究中，通過自適應模糊神經推理算法進行最優路由協議選擇的方法，由于其參數學習的復雜性與易陷入局部最優等缺點并不能滿足客觀需要[9]。因此，基于遺傳粒子群算法的自適應模糊推理系統(Genetic Algorithm Particle Swarm Optimization Adaptive Neuro-Fuzzy Inference System，GAPSO-ANFIS)，擬提出一種VANET路由性能推理系統。該系統通過研究ANFIS的參數優化問題，結合遺傳算法(Genetic Algorithm，GA)進行粒子群全局尋優，從而搭建最優路由機制推理系統。同時，對該系統在節點密度和節點速度變化時幾種典型路由協議的性能建模進行分析。最后，為了進一步驗證所提的改進型VANET路由性能推理系統的有效性，在按需距離矢量路由協議(Ad hoc On-Demand Distance Vector Routing，AODV)、目的序列距離矢量路由協議(Destination Sequenced Distance-Vector，DSDV)及動態源路由協議(Dynamic Source Routing，DSR)等3種典型VANET路由協議仿真數據集下，利用所提系統進行最優路由協議推理驗證。

1 基于ANFIS的路由策略推理

VANET網絡的場景因素對路由協議的性能具有重要影響。在不同的網絡場景中，路由協議往往會表現出截然不同的性能[10]。因此，根據路由協議在不同網絡場景中的性能表現，可以推理得到不同用戶需求下的最優路由協議。在VANET網絡中，影響路由協議性能的主要參數有網絡節點的移動性和網絡節點規模[11]，通過對這兩個參數進行設計可以得到最優的路由選擇。考慮ANFIS中的參數結構太過復雜，同時其參數調整過程中采用的最小二乘法和梯度下降法很容易得到局部最優解[12-14]。因此，針對ANFIS中的參數復雜、運算量大等問題，提出了改進后的ANFIS算法。該算法在改進過程中通過粒子群算法對ANFIS參數進行了尋優，同時還結合遺傳算法中的交叉、變異等操作，進一步避免了粒子群算法早熟的問題。以該算法為基礎提出的路由策略推理系統如圖1所示。

圖1 路由策略推理系統

由圖1可以看出，路由策略推理方案主要包含網絡情景感知、模糊神經網絡推理算法和最優路由協議選擇等3部分。首先，由網絡情景感知模塊對當前VANET網絡中的節點移動速度和網絡規模進行感知，并將感知結果以及備選路由協議的性能數據集作為改進后的模糊神經網絡推理算法的輸入。其次，由改進后的GAPSO-ANFIS分別對不同路由協議下的性能指標進行推理,得到吞吐量、時延和丟包率等性能指標，再通過效用值函數得到各性能指標的效用值，將效用值和不同用戶需求下的目標函數相結合，可以得到各備選路由協議的總效用值。最后，選擇效用值最大的備選路由協議，就可以實現最優路由協議的選擇。

2 自適應模糊神經推理算法的優化

2.1 粒子群遺傳算法

綜合兩種算法的優勢，將GA中的遺傳、交叉和變異等操作引入到PSO算法中，提出了GAPSO-ANFIS，粒子群算法和遺傳算法的結合原理如圖2所示。在PSO算法每一次迭代生成粒子群后，GAPSO-ANFIS都會按照粒子的適應度值對粒子群中每個粒子進行優劣性排序，將排序屬于前半部分的粒子作為優質粒子，直接用于下一代。然后對剩下的一半粒子進行遺傳算法中的選擇、交叉和變異操作。將操作后的粒子與操作前的粒子進行排序，再次選出較優粒子與優質粒子結合起來形成新一代種群，并繼續下一步運算。

圖2 粒子群遺傳算法結合原理

2.2 ANFIS優化

智能算法適合用于解決那些無法建立有效模型的問題[18]。為了改善ANFIS算法參數學習復雜、運算量大等問題，提出了GAPSO-ANFIS，首先，在PSO算法中，各粒子都具有記憶存儲能力，能對個體和種群的最優粒子位置信息進行保留，局部的尋優能力更強，收斂速度更快，利用PSO調整ANFIS參數，可以獲得最優參數值。GA擁有全局搜索能力，其交叉和變異操作既能進行信息交換又能增加粒子種群的多樣性，避免迭代過程中出現局部最優解。GAPSO-ANFIS流程如圖3所示。

圖3 GAPSO-ANFIS流程

GAPSO-ANFIS具體的步驟如下。

步驟1首先，對種群的規模m、粒子運動的最大速度vmax和最大迭代次數參數T等參數進行初始化。

步驟3按照該優化問題對應的目標函數計算每個粒子的適應度值，采用均方根誤差(Root-Mean-Square Error，RMSE)作為目標函數，表達式為[19]

大家都知道一講到底的授課方式效果不好，卻難以改變。我們曾做過調查，課堂講授的方式，教師教得太辛苦，學生也不愿意聽，想讓學生參與到課堂中來，學生礙于情面和習慣，參與意愿不強。學生對這樣一種教學方式也不滿意，認為這樣的教學方式剝奪了自己的學習自主權，而且長時間聽講做到一直集中精力幾乎不可能，再生動的講解聽久了也會讓人疲勞。學生希望教師能夠設計一些讓他們參與其中的教學環節。既然教師與學生都有交流互動的需要，那為什么交流互動難以實施呢？

(1)

式中：yi和ydi分別表示網絡的輸出值和輸出期望值；N為數據總量。

步驟4判斷當前適應度值是否小于之前的個體最優解Pbest，若小于之前的Pbest，則表示該粒子更優，可以使用該粒子對之前的個體最優值進行替換。同時，對將該粒子的Pbest與其他粒子的Pbest進行對比，選出全局最優解Gbest。

步驟5對粒子當前的位置以及速度進行修正，并對每個粒子的最大移動范圍pmax和最大移動速度vmax進行限制。

步驟6計算當前粒子所對應的適應度值，并根據所得到的數值對粒子種群進行排序。

步驟7通過對粒子種群進行篩選，從中選出較優的前一半粒子作為優質粒子進入下一代，然后再對后一半粒子執行GA中的選擇、交叉及變異等操作。

步驟8在GA操作之后，得到較優的粒子，將其與上一步選出的優質粒子進行合并，產生新的粒子群。

步驟9分別重新計算當前粒子群中的Pbest和Gbest。

步驟10判斷當前得到的最優解是否達到目標，或是否達到最大迭代次數：若達到，則轉到步驟11；否則，對其迭代次數加1并轉至步驟5。

步驟11通過步驟10得到全局最優值Gbest，將其作為ANFIS最優參數值，并使用測試數據集進行測試。

在對算法進行對比時，常用的評價指標分別是RMSE、平均絕對誤差(Mean Absolute Error，MAE)和判定系數R2等指標。通?？梢愿鶕2的值判斷模型的好壞：如果其結果為0，則說明該模型的擬合效果很差；如果其結果接近于1，則說明模型幾乎沒有錯誤。MAE[20]和R2[21]的表達式分別為

(2)

(3)

3 數值分析

3.1 最優路由策略庫構建

采用交通仿真軟件(Simulation of Urban Mobility，SUMO)和網絡仿真軟件(Network Simulator version 2，NS 2)進行聯合仿真，所使用的實際道路場景移動模型如圖4所示。

圖4 實際道路場景移動模型

由圖4可以看出，改變圖4中的車輛數量以及車輛移動速度，可以構建出VANET網絡中的多個網絡場景，記錄不同場景下的按需距離矢量路由協議(Ad-hoc On-Demand Distance Vector Routing，AODV)、目的序列距離矢量路由協議(Destination Sequenced Distance-Vector，DSDV)及動態源路由協議(Dynamic Source Routing，DSR)等3種備用路由協議的性能表現，構成策略知識庫。網絡中的數據業務特性通常可以使用吞吐量、時延和丟包率刻畫，在不同網絡場景下得到的數據集屬性如表1所示。

表1 數據集屬性

以數據集中的吞吐量為例，VANET網絡中各協議的吞吐量在AODV、DSDV及DSR等不同場景下的變化情況如圖5(a)到圖5(c)所示。

圖5 吞吐量變化情況

由圖5可以看出，圖5(a)展示了 AODV在不同場景下的吞吐量變化情況。該協議在節點速度較低、節點數目中等的情況下吞吐量性能值約為510 Kb·s-1，表現較好，這是由于AODV是被動式路由協議，維護的路由信息較少，并且會周期性地進行路由發現以確保當前路由信息的更新。圖5(b)展示了DSDV的吞吐量變化情況，該協議在節點數目較多、節點速度較低時表現最好，吞吐量性能值約為 550 Kb·s-1，原因在于DSDV是主動式路由協議，在連接數變化時路由開銷幾乎不會增加，而另外兩種被動式路由協議在通信密度增加時，頻繁進行路由發現，導致吞吐量降低。圖5(c)是DSR的吞吐量變化情況，該協議在節點數目較少、節點速度較低時，性能表現最好，約為530 Kb·s-1，主要原因在于DSR對路由信息進行緩存，使得源節點保存了多條通往目的節點的路由路徑，減少了路由發現的次數，從而減少了路由發現的開銷。

由以上分析可以看出，不同的路由協議在不同網絡場景下的性能表現差別明顯，每種路由協議都有其適用的場景。因此，通過所提的自適應最優路由協議選擇方法，選出與目前的網絡場景最適配的路由協議，就可以進一步保障該場景下的路由性能。

3.2 實驗參數設置

將均方根誤差RMSE設為適應度函數，使用得到的數據集進行仿真，對所提出的模糊推理模型的準確性進行驗證。對數據集采用隨機劃分的方式，選出80%的數據作為GAPSO-ANFIS網絡的訓練數據，其余數據用于網絡測試。GAPSO-ANFIS網絡建模過程中所用到的一些參數初始值如表2所示。仿真過程中為了測試誤差是否滿足精度要求，分別對每個數據集進行了100次實驗，進而計算出對應評價指標的均值。

表2 GAPSO-ANFIS參數

首先，需要對種群規模進行設定，該數值的大小直接影響到粒子的全局搜索能力。該數值越大，種群中各個體的搜索能力就越強。但是，搜索能力強的同時，也存在著一定問題，種群規模大就會導致整體搜索的時間更長，無法快速得到最優解。因此，種群規模M一般取值范圍為[20,40]。其次，還需要對學習因子的大小進行設定。該數值的大小與種群進行局部搜索的能力相關，該值越大，種群進行局部搜索的能力就會越強，c1，c2的取值范圍一般為[0,4]。另外，還需要對慣性權重進行設置，該值的大小決定了種群對解的探索能力，該值越大，種群對于全局的搜索能力就越強，ω的取值范圍一般為[0.9,1.2]。交叉概率Pc的取值范圍一般為0.40～0.99，變異概率Pm的取值范圍一般為0.000 1～0.1。文獻[19]通過對比驗證給出了Pc和Pm更準確的取值范圍，據此將交叉概率Pc和變異概率Pm分別設為0.90和0.01，在保證個體種群多樣性的同時，也避免了搜索過程過于緩慢。

3.3 性能對比

為驗證所提的GAPSO-ANFIS的可靠性，對表1給出的數據集進行分析，參照其中的節點數目和節點移動性，將其作為初始參數值并輸入算法程序，基于初始化函數視角對網絡進行初始化操作。同時，GAPSO算法使用遺傳運算符選擇初始群體，使用適度函數確定遺傳過程的質量，獲得全局優化位置。進而完成ANFIS算法的參數尋優，并由此模型進行吞吐量預測?；谝陨蟽煞N算法的VANET路由性能推理系統得到的預測數據與實際數據對比情況如圖6所示。由圖6可以看出，通過與實際輸出比較，實際輸出結果與基于改進型ANFIS的推理系統結果更加貼合，推理誤差更小，直觀地說明了所提系統的合理性和有效性。

圖6 預測數據與實際數據對比情況

為進一步驗證所提系統的準確性，還將其與基于ANFIS、PSO-ANFIS的推理系統就相對誤差指標進行了對比，結果如圖7所示。

圖7 相對誤差對比

由圖7可以看出，從誤差對比情況看，所提系統的相對誤差明顯較ANFIS和PSO-ANFIS更接近于0，其預測性能能夠滿足路由性能參數推理的準確性要求。

采用式(1)至式(3)對基于ANFIS、PSO-ANFIS和GAPSO-ANFIS的VANET推理系統性能進行了對比，對比結果如表3所示。

表3 算法性能對比

由表3可以看出，GAPSO-ANFIS經過改進后能夠自適應得到最優參數，整體性能穩定。與基于ANFIS(RMSE為12.751 4，MAE為10.377 9，R2為0.826 4)的推理系統相比，基于GAPSO-ANFIS(RMSE為6.061 8，MAE為4.847 2，R2為0.909 7)的推理系統性能更優。同時，基于GAPSO-ANFIS的推理系統性能還優于僅使用粒子群算法優化的PSO-ANFIS(RMSE為8.542 7，MAE為6.942 9，R2為0.886 2)。

4 結語

以車聯網城市場景為背景，針對VANET網絡不同場景中路由機制的適配問題，提出了在參數尋優過程中采用粒子群遺傳融合算法的VANET路由性能推理系統。該系統通過引進粒子群算法和遺傳算法，在改進型ANFIS的基礎上，設計了VANET最優路由機制推理系統，可以改善ANFIS所面臨的參數復雜、運算量大等問題。

通過效用函數對網絡最優路由機制進行推理，在AODV、DSDV和DSR等3種典型的VANET路由協議仿真數據集下，對基于改進型ANFIS的VANET路由性能推理系統進行了最優路由協議推理驗證。驗證結果顯示，基于改進型ANFIS的系統R2值為0.909 7，基于ANFIS的系統R2值為0.826 4，證明改進后的VANET路由性能推理系統擬合效果更優。同時，基于改進型ANFIS的VANET路由性能推理系統的RMSE為6.061 8，MAE為6.942 9，均低于基于ANFIS算法的推理系統，也說明該改進算法在準確性方面表現更優。以上分析結果表明，改進型ANFIS的VANET最優路由推理系統具有可靠性高、誤差小等特點，在VANET網絡最優路由協議選擇方面具有更高的準確性。