基于節點關聯強度預測和GPSR-R的混合路由算法

倪紅彪，李 卓

(1.吉林警察學院 信息工程系，吉林 長春 130117；2.吉林大學 計算機科學與技術學院，吉林 長春 130117)

0 引 言

在車輛自組織網絡系統[1]中，每臺車輛都可以發送、接收、存儲和計算信息。車輛自組織網絡提供許多類型的應用，如互聯網接入、媒體下載、安全系統等[2-4]。許多汽車生產公司(如寶馬、福特等)都使用車輛自組織網絡技術為用戶提供智能交通系統應用服務。為了提供快捷、可靠、穩定的數據傳輸服務，提出了許多面向車輛自組織網絡的路由協議[5-9]。GSR(geographic source routing)是一種常用的基于地理源的路由協議，通過向最接近目的地的車輛發送數據，尋找將數據發送到目的地的最短路徑來進行數據傳輸。但是由于缺乏關于前方交通的信息，該路由協議可能會增加延遲[10]?；谖恢玫穆酚蓞f議(greedy perimeter stateless routing，GPSR)是一種基于貪婪轉發策略的無狀態路由協議，該協議在車輛自組織網絡領域應用非常廣泛。該路由協議也是通過更接近目的地的車輛發送數據，但如果出現局部最優問題，則會進入周邊模式。在這種模式下，可以使用平面圖模塊來恢復這個問題。但是如果定期發生網絡跳轉，則該協議有可能始終保持在周邊模式，此種狀態下路由協議的性能會下降[11]?？紤]到路由在長距離通信時多跳鏈路易發生中斷，而實際上通信鏈路只需滿足從源節點到目的節點的通信需求即可，因此文獻[12]提出了一種改進的GPSR路由協議，稱之為GPSR-R(改進的GPSR路由協議)路由協議。該路由協議根據車輛之間具體的網絡需求進行綜合考慮，降低移動節點維護數據的數據量，自適應選擇滿足通信需求且對鏈路穩定性要求不高的路由，在快速傳輸數據的過程中降低丟包率現象。然而，該路由協議選擇的路由的穩定性較差，在某些狀態下可能由于鏈路的不穩定而造成數據包丟失的現象。為解決這一問題，本文提出了一種結合節點關聯強度預測和GPSR-R的混合路由協議，該混合路由協議是以GPSR-R路由協議為基礎的，主要創新點是在中繼節點的選擇方面，加入節點關聯準則，通過遺傳算法學習和預測節點之間的關聯強度，在選擇下一跳節點時不僅考慮節點的位置信息，還要考慮節點之間的關聯信息，這樣有助于增強鏈路的穩定性，進一步降低丟包率和提高數據包傳遞率。

1 基于遺傳算法的節點關聯強度預測

一般地，在路由發現階段，節點之間在相互傳遞握手數據包的過程中可以從握手數據包中獲取時間和節點身份等信息，數據包格式記為：{tc,n,sn}。其中，tc表示當前時間，這里的時間以秒為單位。在路由發現階段，握手數據包的發送時間間隔為20 s。n表示發送節點。sn表示發送節點n的鄰居節點集合，也即當前時間tc在發送節點n的通信范圍內的所有節點組成的集合，換言之，指發送節點n的一跳鄰居節點集合。在每一次握手過程中，網絡中的每個節點都以文件方式獨立存儲這些數據。譬如，節點n將每一次握手過程中獲取的這些數據單獨存儲在一個文件中，與其它節點所存儲的文件相互獨立。

在進行節點關聯強度預測時，從各個節點的數據文件中讀取相應數據，構建一個節點關聯矩陣，記為M=[mtij]T×N×N。也即，該矩陣是一個三維數組，維數為T×N×N。其中，T表示時間片段數量，在本文中，每一個分鐘進行一次節點關聯強度預測，那么每小時可以進行60次檢測，故時間片段數量T=60。N表示網絡中節點的數量。mtij表示第t個時間片段網絡中第i個節點與第j個節點的關聯強度。具體地，當某一時刻τ節點j處于節點i個鄰居節點集合之內(也即j∈si)時，我們認為該時刻下節點j和節點i是相互關聯的，對應該時刻兩者的關聯強度為1，否則為0。記ητij表示時刻τ節點i和節點j之間的關聯強度，于是有

(1)

在本文中，每一分鐘進行一次節點關聯強度預測，每20 s進行一次握手，那么在一分鐘內共有3個時刻，將這些時刻上各個節點之間的關聯強度進行累加，即可得到時間片段t上各個節點之間的關聯強度。于是，第t個時間片段網絡中第i個節點與第j個節點的關聯強度可以表示為

(2)

本文以節點關聯矩陣為依據，采用遺傳算法預測車輛節點之間的關聯強度。詳細描述如下。

1.1 適應度函數

本文以節點之間的關聯強度來構建節點的適應度函數?？紤]到每一次節點關聯強度都會統計當前時間片段各個節點之間的關聯強度，因此，適應度函數也應當與時間片段有關。本文定義第t個時間片段節點i的適應度函數為

(3)

1.2 染色體

本文將網絡中的節點組合看作染色體，記為x=(x1,x2,…,xN)。該染色體是一個二進制染色體，1表示節點存在，0表示節點不存在。這樣，一個染色體中為1的節點之間的關聯強度大，適合作為中繼節點進行數據傳輸。

對于每一個節點，在某一時間片段其適應度值越大，說明在該時間片段網絡中與該節點關聯的節點數量越多，那么該節點被選為路由的概率越大。因此，通過最大化適應度函數，可以選擇最優的節點。本文采用遺傳算法來解決這一最優化問題，將節點組合構成的二進制染色體進行選擇和交叉操作，經過繁衍之后選擇最優的后代。該后代所代表的節點組合描述了節點之間的最優關聯關系。需要說明的是，遺傳算法常使用變異操作來避免最優化求解陷入局部最小現象。在本文中，考慮到節點數量有限，時間片段也有限，變異操作的意義不大，因此本文的遺傳算法只使用選擇和交叉操作，這樣收斂速度更快。

考慮到染色體是二進制格式，那么對應的雙親也應當是二進制格式。因此，需要將適應度矩陣轉換為二值矩陣。本文采用的方法是，首先統計適應度矩陣的元素累加和，即

(4)

然后，計算適應度矩陣中每一個元素與的比值∑，如果比值超過一定閾值ε，則該元素置為1，否則置為0，也即

(5)

閾值ε可以通過大量的實驗來確定，本文取ε=0.02。

1.3 交 叉

在繁衍后代時，從雙親集合(也即適應度矩陣)中選擇元素送入交配池，通過交叉生成新的染色體(用字符串表示)。對于交叉操作，交配池中重新生成的字符串的成員隨機配對。每對字符串配對過程如下：沿著字符串的整數位置k在1和串長度d之間隨機均勻地選擇，通過交換位置k+1和1之間的所有字符來創建兩個新的字符串。任意一點i的交叉過程是：對于兩個雙親字符串，隨機選擇一個交叉點d，1

(6)

1.4 選 擇

在交叉操作過程中，每對父母創建兩個孩子，從而使下一代的交配池的尺寸倍增。因此，應該進行選擇操作來降低交配池的尺寸。選擇過程遵循的基本原則是：具有較高適應度值的染色體被選入交配池的概率必須比具有較低適應度的染色體的概率大。加權輪盤賭是常用的選擇策略，該策略保證具有較高權重(也即較大適應度值)的元素將具有較高的概率被選擇為下一代的雙親。

交叉和選擇操作重復進行，直至達到最大迭代次數。在本文中，最大迭代次數設置為10。

2 結合GPSR-R和節點關聯強度的混合路由

在介紹本文提出的結合GPSR-R和節點關聯強度的混合路由協議之前，首先需要介紹車輛自組織網絡的假設條件。通常，我們假定車輛自組織網絡滿足以下條件：

(1)通常忽略車輛的高度信息，假定構建的車輛自組織網絡是一個平面網絡。

(2)車輛可以通過自身安裝的定位裝置(如GPS、北斗模塊)，獲知自身的速度、加速度、位置和方位角等信息。

(3)假定網絡中通信節點(也即車輛)的能量是不會耗盡的，在設計路由時可以不考慮能量的消耗問題。

(4)車輛可以通過周期性的廣播交互信息，感知其它車輛的位置、速度、加速度和方位角等狀態信息。

(5)假定車輛自組織網絡中所有車輛的通信距離是相同的。

以上假設條件構建了車輛自組織網絡的一般模型。在設計車輛自組織網絡的路由時，需要考慮以上假設條件。

在車輛自組織網絡領域，常用的路由協議是GPSR路由協議。該路由協議采用貪婪轉發策略構建路由。實現流程如圖1所示。其核心思想是選擇距離目的節點最近的鄰居節點作為中繼節點來轉發數據。

圖1 GPSR路由協議實現流程

在此基礎上，文獻[12]提出了一種GPSR-R路由協議，該協議依據網絡的實際需求來選擇路由，具體是在GPSR路由協議的基礎上，降低移動節點維護數據的數據量，僅依據網絡需要維護移動節點通信范圍之內的節點的信息，包括節點的位置、行駛速度、方位角等信息，并通過網絡收斂、貪婪轉發和路徑優化操作，篩選數據。同時將移動節點的通信時間與路由的維護時間相比較，自適應選擇滿足通信需求且對鏈路穩定性要求不高的路由。該協議與GPSR路由協議的主要區別在于，在路由發現過程中，節點在接收到周圍節點的路由請求數據包之后，首先辨別數據包內容，如果當前節點沒有轉發過該數據包，則將該節點所維護的鏈路堆棧信息添加到路由請求數據包，并依據GPS提供的節點位置信息，查找處于當前節點通信范圍內的鄰居節點，將新生成的路由請求數據包轉發給其鄰居節點。同時，路由請求數據包中還記錄一個數據項，即路由請求數據包從源節點發出到目的節點接收所需要的通信時間。當路由發現完成后，對比通信時間和路由維護時間，如果通信時間小于路由維護時間，才選擇發現的路由。否則，需要重新發現路由。

本文將前一節所述的節點關聯強度與GPSR-R路由協議相結合，在依據GPSR-R路由協議發現路由的基礎上，加入節點關聯強度的選擇標準，目標是在發現路由時選擇關聯強度大的節點作為中繼節點，提高鏈路的穩定性。主要實現步驟是：

(1)定時啟動節點關聯強度計算模塊，采用前一節所述的遺傳算法生成最優的關聯節點組合。在本文中，每隔一分鐘啟動一次節點關聯強度計算模塊。

(2)依據GPSR-R路由協議發現路由，當前節點在選擇鄰居節點時，首先像GPSR-R路由協議一樣，依據GPS提供的節點位置信息查找處于當前節點通信范圍內的鄰居節點。然后結合當前節點的關聯節點組合，判斷鄰居節點是否為當前節點的關聯節點(也即字符串x中對應的節點位置的字符是否為1)。如果是，則將其作為當前節點的鄰居節點；否則，將其剔除當前節點的鄰居節點集合。后續，繼續依據GPSR-R路由協議，發送路由請求表給鄰居節點，直至完成路由構建。

與GPSR-R路由協議相比，本文的混合路由協議主要是在鄰居節點選擇方面進行了優化，通過關聯節點來對鄰居節點進行進一步的篩選，剔除關聯強度小的鄰居節點，增強鏈路的穩定性。

3 仿真與分析

與文獻[12]一樣，本文也采用臺灣交通大學研制的NCTUns軟件進行車輛自組織網絡的仿真實驗。該軟件為車輛自組織網絡提供了一個單一的網絡環境，在單一模塊上實現了交通和網絡兩類仿真，非常適合車輛自組織網絡的仿真實驗。在仿真實驗時，通過人工配置實驗參數，可以滿足多種網絡仿真的需求。本文基于車輛自組織網絡路由協議的性能評價目標，使用如表1所述的實驗參數。

表1 實驗相關參數

為了評價本文所述的混合路由協議對于車輛自組織網絡數據通信的性能，本文選擇與文獻[12]相同的路由協議性能評價指標，即數據包傳遞率和丟包率。這兩個指標可以反映路由性能的優劣，數據包傳遞率越高、丟包率越少，路由性能越好。

在仿真實驗時，將本文所述的混合路由協議與文獻[11]所述的GPSR路由協議以及文獻[12]所述的GPSR-R路由協議進行實驗對比和分析，評價本文所述路由協議的性能。同時，為了更全面地分析不同路由協議的性能指標，本文針對不同的車輛移動速度和數據傳輸距離統計3個測試指標的變化情況，詳細描述如下。

3.1 數據包傳遞率對比

圖2展示了不同路由協議的數據包傳遞率的仿真實驗結果。其中，圖2(a)展示了車輛移動速度不同時不同路由協議的數據包傳遞率的對比情況，圖2(b)展示了數據傳輸距離不同時不同路由協議的數據包傳遞率的對比情況。一般地，車輛移動速度越快，網絡的拓撲結構變化越大，路由的穩定性越差。因此，數據包傳遞率會隨著車輛移動速度的增加而下降，這一現象可以從圖2(a)中明顯看出。由圖2(a)可見，本文路由協議的數據包傳遞率曲線在其它兩種路由協議的上方，與GPSR-R路由協議的數據包傳遞率曲線相距不是很大，但明顯高于GPSR路由協議的數據包傳遞率曲線。這一現象表明，從數據包傳遞率指標來講，針對不同的車輛移動速度，本文的混合路由協議的性能要優于GPSR-R路由協議和GPSR路由協議。而且本文的混合路由協議和文獻[12]所述的GPSR-R路由協議的性能要明顯優于文獻[11]所述的GPSR路由協議。同樣地，數據傳輸距離越遠，中繼節點的數量越多，由于中繼節點故障而造成的鏈路中斷頻率就越大。因此，數據包傳遞率會隨著數據傳輸距離的增加而下降，這一現象也可以從圖2(b)中明顯看出。由圖2(b)可見，本文路由協議的數據包傳遞率曲線仍然在其它兩種路由協議的上方，類似地，本文路由協議和GPSR-R路由協議的數據包傳遞率曲線明顯高于GPSR路由協議的數據包傳遞率曲線。綜合分析圖2(a)和圖2(b)可以得知，在不同的車輛移動速度和不同的數據傳輸距離條件下，本文的混合路由協議的數據包傳遞率性能都要優于GPSR-R路由協議和GPSR路由協議，尤其是明顯優于GPSR路由協議。原因主要是，本文的混合路由協議在GPSR-R路由協議的基礎上，又增加了節點的關聯強度選擇準則，這樣在路由選擇時可以選擇關聯強度大的節點作為中繼節點，增強了鏈路的穩定性，從而間接提高了數據包的傳遞率指標。

圖2 數據包傳遞率實驗對比

3.2 丟包率對比

圖3展示了不同路由協議的丟包率的仿真實驗結果。其中，圖3(a)展示了車輛移動速度不同時不同路由協議的丟包率的對比情況，圖3(b)展示了數據傳輸距離不同時不同路由協議的丟包率的對比情況。由圖3(a)可見，本文路由協議的丟包率曲線處于3種路由協議的最下方，GPSR-R路由協議的丟包率曲線次之，GPSR路由協議的丟包率曲線處于最上方。這一現象表明，從丟包率指標來講，針對不同的車輛移動速度，本文的混合路由協議丟包率最小，GPSR-R路由協議的丟包率次之，而GPSR路由協議的丟包率最大。換言之，本文的混合路由協議的丟包率性能優于GPSR-R路由協議和GPSR路由協議。同樣地，由圖3(b)可見，本文路由協議的丟包率曲線仍然處于最下方，GPSR-R路由協議的丟包率曲線次之，GPSR路由協議的丟包率曲線處于最上方。綜合分析圖3(a)和圖3(b)可以得知，不管車輛移動速度和數據傳輸距離怎么變化，本文的混合路由協議的丟包率性能都要優于GPSR-R路由協議和GPSR路由協議，尤其是明顯優于GPSR路由協議。

圖3 丟包率實驗對比

4 結束語

本文提出了一種面向車輛自組織網絡的混合路由協議，本質上是對GPSR-R路由協議的改進。該路由協議設計的出發點源于GPSR-R路由協議建立的鏈路穩定性較差，容易由于鏈路斷裂而造成數據包丟失等問題。為了提高GPSR-R路由協議所建立的鏈路的穩定性，本文在GPSR-R路由協議的基礎上引入了節點關聯強度選擇準則，通過選擇關聯強度大的節點作為中繼節點來增強鏈路的穩定性。在節點關聯強度計算方面，本文采用遺傳算法，定時預測節點之間的關聯強度，為中繼節點的選擇提供依據。實驗結果表明，本文結合節點關聯強度預測和GPSR-R的混合路由協議提高了GPSR-R路由協議的數據包傳遞率，降低了丟包率，取得了較好的實驗結果。