基于粒子群算法的車載自組網GPSR協議優化

龔 凱，陳 志，岳文靜

(1.南京郵電大學 計算機學院，江蘇 南京 210023； 2.南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著智能城市和物聯網應用技術的快速發展，車載自組網(VANET)等技術變得越來越重要[1]。VANET提供數據收集和傳送的功能，如何最大限度地提高其通信質量，盡可能地減少數據收發時延，同時降低其能量消耗，一直是廣泛關注的研究熱點。

基于地理位置的VANET路由協議相比其他路由協議具有較高的數據包傳送比率和低時延，更適應動態的車輛通信環境[2]，但下一跳節點選擇策略仍存在不足。有些策略為了降低時延卻忽略了節點的能量利用率，導致局部節點過早死亡，有些策略考慮到了節約能量卻嚴重犧牲了數據傳輸時延。文獻[3]提出利用粒子群算法生成一個能量利用率高的分簇路由協議，該協議通過平衡能量消耗，以提高節點的生命周期。文獻[4]提出基于車輛密度、行駛方向和速度的路由優化策略，該策略在包傳輸率和路由開銷上均優于已存在的GPSR協議。文獻[5]利用緩存轉發機制在貪婪轉發模式中引入緩沖區域消除不可靠節點，解決節點在高密度環境下易受干擾的問題。這些已有的優化方法在解決路徑問題上單調考慮一面判決因素，忽略網絡內包含的多面可利用信息，在解決貪婪轉發模式所存在的問題上還有繼續優化的可能。

粒子群優化算法是一種群智能優化技術[6]，在每次迭代過程中，利用粒子通過當前所找的個體極值和全局極值來不斷更新自己的位置和速度，慢慢地向目標位置靠近，最終找到最優解[7]。為盡量考慮到節點下一跳選擇時的多方面因素，文中優化了GPSR協議，利用粒子群算法來均衡處理，通過迭代尋優找出最優下一跳節點，以有效提高VANET路由質量。

1 車載自組網模型

1.1 網絡模型

為了將問題模型切合實際，對所研究的車載自組網(VANET)作如下假設：

(1)VANET所有節點隨機部署在M×M矩形區域內，每個節點在該區域內隨機運動。

(2)VANET所有節點的初始能量相同、能量有限、地位平等，是一個同構型網絡。

(3)VANET每個節點都有一個唯一的標識ID，且都能感知自己的位置和剩余能量，相鄰節點之間的距離采用歐氏距離計算公式:

(1)

其中，xi,yi,xj,yj分別為GPSR節點i與j的橫坐標與縱坐標；d(i,j)為兩節點之間的歐氏距離。

(4)VANET每個節點的數據傳輸率相同，且所有節點的傳輸半徑都為R。

1.2 能耗模型

在VANET傳輸數據時，除了數據包的發送與接收需要消耗能量外，其他能量消耗都忽略不計，并且發射器發送數據包的能耗隨著傳輸距離的增大而呈指數級增長。因此，傳輸kbit數據所消耗的總能量可表示為[8]：

Econ(k,d)=ETx(k,d)+ERx(k)

(2)

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=

(3)

ERx(k)=ERx-elec(k)=k×Eelec

(4)

1.3 粒子與GPSR節點位置映射模型

由于GPSR協議中節點的位置分布是隨機并且離散的，而粒子群算法是對離散空間求解最優解。根據粒子群算法的位置和速度公式進行更新后，粒子的位置與監測區域內當前節點的所有鄰居節點位置不一定一一映射。

定義粒子與當前節點的所有鄰居節點之間的位置映射函數為[9]：

f(Xi)={Xn|min[d(Xi,Xn)],1≤i≤M,

0≤n≤Nneighbor}

(5)

其中，Xi為粒子的位置；Xn為GPSR節點的位置；M為粒子的數量；Nneighbor為當前節點的鄰居節點總數。由于VANET節點部署在平面區域，則解空間的維數為2，d(Xi,Xn)為粒子Xi與GPSR節點Xn之間的歐氏距離。

根據上面的位置映射函數對每個粒子的位置進行調整，使得調整后的粒子對應到具體的VANET節點，滿足Xix∈{X1x,X2x,…,XNneighborx}，Xiy∈{X1y,X2y,…,XNneighbory}。其中，XNneighborx為當前節點的第N個鄰居節點位置坐標的x分量，XNneighbory為當前節點的第N個鄰居節點位置坐標的y分量。假設f(Xi)=Xk，即d(Xi,Xk)最小，表示第i個粒子與當前節點的第k個鄰居節點之間的距離最近，計算后的位置為：Xix≈Xkx,Xiy≈Xky，即粒子i映射到當前節點的第k個鄰居節點。

2 GPSR協議優化

傳統GPSR協議使用地理位置信息和貪婪算法實現VANET路由。在GPSR協議中，當源節點向目的節點轉發數據分組時，首先在自己的所有鄰居節點中選擇一個距離目的節點最近的節點作為數據分組的下一跳，然后將數據分組傳送給它；上述過程一直重復，直到數據分組到達目的節點或者某個最佳主機[10]。在發生最佳主機問題時，數據分組采用邊界轉發策略來實現路由。目前的貪婪選擇下一跳節點策略所選擇的節點并不一定滿足數據傳輸的QoS要求，同時能量的消耗也不平衡，文中在貪婪轉發的基礎上利用粒子群算法對貪婪轉發下一跳節點選擇策略進行優化，通過適應值函數來評估粒子的質量，為下一跳節點的最優選擇提供可靠的依據，建立GPSR優化協議P-GPSR。

2.1 適應值函數

適應值函數用來評估粒子的優劣，通常取決于具體優化的問題，是系統算法與實際優化問題的接口[11]。為了在提高GPSR協議的能量利用率的同時，滿足數據傳輸的QoS要求[12]，P-GPSR所采用的適應值函數主要考慮以下四個因素：

(1)下一跳節點的能耗與剩余能量。當前節點在選擇下一跳節點時，需考慮下一跳節點的能耗和剩余能量，優先選擇下一跳節點能耗占剩余能量比例小的節點，防止下一跳節點因能量不足導致路由中斷，保證數據的有效路由傳輸。

(2)當前節點距下一跳節點的距離與其距所有鄰居節點的平均距離。由于節點的能耗與包傳輸距離有關，因此需考慮當前節點距下一跳節點與其距所有鄰居節點的平均距離的比值，比值越小，節點傳輸數據包的能耗越少，節點剩余能量也就越多。

(3)當前節點距下一跳節點的距離與當前節點距目的節點的距離。若下一跳節點處于當前節點的傳輸邊界，其因邊界信號強度弱和網絡拓撲變化頻繁而造成其能量消耗大、轉發忙碌和丟包問題。因此，優先選擇當前節點距下一跳節點距離與當前節點距目的節點距離的比值較小的節點作為下一跳節點。

(4)下一跳節點和目的節點分別與當前節點所構成的偏轉角。為確保數據包的正向傳輸，使下一跳節點與當前節點的連線和目的節點與當前節點的連線所構成的偏轉角盡可能最小，以達到減少路由跳數的目的。

綜上所述，P-GPSR的適應值函數定義為：

F=a·f1+b·f2+c·f3+d·f4

(6)

f1=Econ(Ni)/Eresidual(Ni)

(7)

(8)

f3=d(Ni,last,Ni)/d(Ni,last,D)

(9)

f4=θ(Ni,last,Ni,D)/2Π

(10)

根據以上適應值函數的定義，每輪迭代的全局最優解取全部個體最優解中的最小值，較小的f1、f2、f3、f4均能保證最優下一跳節點的選取。粒子的適應值越小，說明相應節點的能耗越少，剩余能量越多，數據包傳輸的距離越小，下一跳節點受邊界干擾程度越小，而且保證了數據包的正向傳輸。較小的適應值改善了節點的負載均衡程度，提高了整個VANET網絡的使用壽命和數據傳輸效率。因此粒子群算法的優化目標是利用適應值函數來評估每個粒子的質量，搜索適應值最小的粒子作為本輪最優下一跳節點。

2.2 改進的下一跳節點選擇過程

P-GPSR采用以下步驟對GPSR協議下一跳節點選擇過程進行改進。

Step1：判斷當前節點的鄰居節點集中是否有距目的節點的距離比當前節點距目的節點距離小的節點，如果有則轉到Step2，否則進入周邊轉發模式。

Step2：初始化粒子群。首先，從當前節點的鄰居節點集中隨機選擇M個節點作為初始粒子群X{X1,X2,…,XM}。然后，初始化每個粒子的速度Vi和位置Xi。將每個粒子的初始位置作為個體最優解(pBest)，根據適應值函數計算每個粒子的適應值，選擇適應值最小的粒子作為整個粒子群的全局最優解(gBest)。

Step3：速度和位置的更新。由于優化空間為二維，所以將每個粒子的速度和位置坐標分解成Vix，Viy，Xix，Xiy的形式。然后根據以下的粒子群速度和位置更新公式對每個粒子的速度和位置進行更新。同時，將更新后的粒子根據粒子與節點間的位置映射公式映射到具體的GPSR節點上。

Xix(t+1)=Xix(t)+Vix(t+1)

(11)

Xiy(t+1)=Xiy(t)+Viy(t+1)

(12)

Vix(t+1)=Vix(t)+c1·rand·(pBest-Xix(t))+c2·rand·(gBest-Xix(t))

(13)

Viy(t+1)=Viy(t)+c1·rand·(pBest-Xiy(t))+c2·rand·(gBest-Xiy(t))

(14)

其中，c1、c2為學習因子，通常取值為c1=c2=2；rand為[0,1]之間的隨機數；t為迭代次數。

Step4：個體最優解(pBest)和全局最優解(gBest)的更新。比較每個粒子的適應值f(Xi)與上一次迭代的個體最優解f(pBesti)的大小，若f(Xi)

Step5：如果沒有找到gBest或者沒有達到設定的最大迭代次數，則轉到Step3；否則，算法終止，將其中具有最小適應值的粒子作為最優下一跳節點。

3 仿真實驗與結果分析

下面采用網絡仿真模擬器NS2[13]進行仿真實驗，模擬GPSR協議的通信過程，其主要的仿真場景參數配置如下：實驗是運行在1 200 m×1 200 m的區域內，VANET節點數目50個，節點的通信范圍為250 m，節點的偵聽范圍為550 m，節點的運動速度為10～100 m/s，信道帶寬為5 Mbps，建立3條CBR數據流，每個數據包的大小為512 Byte，仿真時間為250 s。節點的運動模型是利用NS2自帶的setdest程序生成，在不同的運動速度下，分別運行GPSR協議、O-GPSR協議和P-GPSR協議，其中GPSR協議是原始協議，O-GPSR協議是基于機會轉發的優化協議，P-GPSR協議是提出的基于粒子群算法的優化協議。通過端到端時延、丟包率、能耗來分析比較各個協議的優劣。

(1)端到端時延。

數據包的端到端時延表示數據包從源節點開始，到目的節點接收數據包時的累積時間，其包含了數據包在傳輸過程中的全部時延，如發送緩沖器的發送時延、接口隊列發生阻塞時的排隊時延、數據包在傳輸過程中的傳輸時延、MAC層重傳時延[14]等。

圖1顯示了在不同時間段內，原GPSR協議與兩種改進的GPSR協議的端到端時延的數據對比。

從圖1可以看出，在0～150 s之間，總體上P-GPSR的端到端時延要比另兩種GPSR協議小，但是150 s之后三種協議的時延都為零，是因為實驗設置在0～150 s之內傳輸cbr數據流，150 s后沒有進行數據流傳輸。在數據包傳輸階段內，由于節點位置變化，導致網絡拓撲結構跟著變化，形成不同程度的時延。O-GPSR協議雖然在端到端時延相對于原協議較小，但與P-GPSR協議相比，仍有不足，這是由于其在選擇下一跳節點時雖然考慮到邊界轉發易受干擾導致數據包擁塞，但在貪婪轉發選取下一跳節點時，缺乏考慮節點因剩余能量不足導致傳輸質量不高的問題。而P-GPSR協議利用粒子群算法不但考慮了邊界轉發干擾，而且還能根據節點剩余能量多少來選擇下一跳，減少了數據包的傳輸時間和排隊時間，進而減少了數據包的端到端時延。

(2)網絡能耗。

網絡能耗的多少直接影響著VANET整個網絡的運行周期和節點的使用壽命[15]。P-GPSR協議在選擇下一跳節點時依據下一跳節點與目的節點分別和當前節點連線所構成的偏轉角和下一跳的距離與一跳平均距離的比值等影響因子，保證數據包的正向傳輸，減短路徑長度，減少能耗。

圖2為網絡發送相同數量cbr數據流(500個)時，P-GPSR協議與另外兩種GPSR協議在節點速度不同時的能量消耗比較。

圖2 網絡能量消耗

由圖2可知，三種協議的能耗隨著節點速度的增加都在上升，是因為網絡節點的速度越大，節點自身運動消耗的能量越多，同時也加快了網絡拓撲結構的變化。P-GPSR協議的上升幅度較另兩種協議緩慢，是因為P-GPSR協議利用粒子群算法對節點的各方面因素迭代判斷，下一跳節點有較低概率因網絡拓撲變化加快而變化，減少額外的路由消耗。還可以看出，在節點速度相同的情況下，P-GPSR算法消耗更少的能量。所以，相比于另外兩種GPSR協議，P-GPSR協議能量消耗少，能耗上升幅度緩，保證了整個VANET網絡的使用壽命。

(3)網絡丟包率。

網絡丟包率是目的節點沒有收到的數據包個數與源節點發出的數據包個數之比，大小反映了VANET網絡傳輸的可靠性，比值越小表明協議性能越好。

圖3為在不同節點運動速度下，三種協議的丟包率的對比。

圖3 丟包率

從圖中可以看出，三種協議的丟包率隨著速度的增加而增加，是由于VANET節點速度的變快導致網絡拓撲結構的變化頻率增加，路由斷裂的概率增大，導致數據包丟失的概率變大。另外還可以看出，在相同節點速度的情況下，P-GPSR協議的丟包率比另外兩種GPSR協議要小，是因為P-GPSR協議在貪婪轉發下一跳節點選擇時，沒有一味地選擇離目的節點最近的節點，而是綜合考慮了節點剩余能量大小、邊界節點易受干擾和數據包的正向傳輸等問題，防止因節點剩余能量不足而導致路由斷裂出現路由空洞，以及數據包因一直偏離目的節點方向使傳輸時延增加，導致數據包沒有在規定時間內送達而被丟棄。綜上，改進的P-GPSR協議在丟包率上優于另外兩種協議。

4 結束語

GPSR協議在貪婪轉發選擇下一跳節點時，選擇距離目的節點最近的節點作為下一跳節點，忽略了VANET有時出現的邊界節點易受干擾、損耗大、節點剩余能量不足、網絡整體能耗高和數據包偏向傳輸等問題。對此，提出了基于粒子群算法的VANET協議P-GPSR。該協議利用粒子群算法來解決上述問題，選擇具有最小的全局適應度值的節點作為下一跳節點。仿真實驗與結果分析說明，相比于GPSR協議及其他優化協議，該協議能夠有效降低端到端時延和丟包率，對VANET路由空洞問題也產生了一定作用，同時降低了VANET網絡數據包傳輸的能量消耗，延長了VANET使用壽命。