基于Markov預測模型的ETX路由判據研究

蘇浩明，黃 晞，施文灶，劉一粟

(1.福建師范大學 光電與信息工程學院，福建 福州 350007；2.福建師范大學 地理科學學院，福建 福州 350007)

0 引 言

無線Mesh網絡結合了ad hoc網絡和傳統無線網絡的優點。其核心指導思想是讓網絡中的每個移動或固定節點都可以發送和接收信號，節點間的通信不再需要接入點轉接。通過多跳網絡的構造，數據可以通過相鄰節點間的轉發傳送到目的地，減小了流量擁塞的可能性，大大提高了網絡整體性能[1-2]。

路由判據用來計算源節點到目的節點的開銷最小的路徑，需確保路由穩定、網絡性能良好、算法明確、無路由環路。眾多適合于無線Mesh網絡的路由判據中，ETX(expected transmission count，期望傳輸次數)通過某個鏈路從源節點到目的節點在過去一段時間內發送一個數據包的平均傳輸次數，來預測未來發送一個數據包所需要的傳輸次數。但這樣的路由判據只能反映歷史時間內網絡性能的情況，沒有考慮節點移動引起的網絡拓撲和性能的變化，因此對于網絡節點移動頻繁的場景，該路由判據有很大的局限性[3-4]。因此，文中提出一種改進的基于Markov數學模型的ETX路由判據，通過節點過去一段時間的位置，預測節點未來的位置，判斷在下一時刻源節點和目的節點是否在彼此的通信范圍內，以確定ETX路由判據是否失效，從而選擇出更加合適的路由。

1 ETX判據及其改進

1.1 傳統ETX判據

ETX路由判據的思路是根據歷史時間內成功傳輸到目的節點所需要的平均發送次數來預測未來一段時間成功傳輸到目的節點所需要的發送次數。這一路由判據一般應用于無線Mesh網絡[4]。無線鏈路的ETX是指無線鏈路上成功傳輸一個分組時所需的平均預計傳輸次數[5]。ETX中，每個節點定期廣播一個固定長度的專用鏈路探測包，這個數據包包含最后一段探測時間內從每個相鄰節點接收到的探測分組的數據。

每個節點通過相鄰節點轉發或反向發送的專用鏈路探測包，可以計算出成功遞交率df和dr[6]，然后就可以得到期望傳輸次數了，如下所示：

ETX=1/df×dr

(1)

這種傳統ETX路由判據沒有考慮節點的運動帶來的拓撲變化，無法判斷下一時刻節點是否在彼此的通信范圍內，不能據此做出相應的路由調整，且對拓撲變化的反應速度太慢，存在潛在的不穩定性，難以滿足節點地理位置和網絡拓撲變化頻繁的網絡系統高速率傳輸、高吞吐量和快速收斂的需求。

1.2 改進的ETX判據

改進傳統ETX路由判據的問題，不僅需要預測未來節點之間的平均傳輸次數，還需要預測節點未來的運動軌跡，據此判斷下一時刻節點是否在彼此的通信范圍內，是否需要調整路由。通過在直角坐標系中定位網絡系統中各節點的位置，獲取節點的橫縱坐標，并以時間為自變量，將歷史時間內節點的坐標-時間的關系帶入Markov數學預測模型，來預測節點下一時刻的坐標，從而獲取節點下一時刻的位置。根據對節點下一時刻位置的預測，如果下一時刻節點還在彼此的通信范圍內，則原ETX路由判據不需要修改，如果不在彼此的通信范圍內，那么這條鏈路判定失效[7-9]，選擇ETX次之的路由并同樣判斷下一時刻是否在彼此的通信范圍內，以此類推直至找出最優路由。

2 改進ETX判據的實現

2.1 在專用鏈路探測包中加入地理位置信息

傳統的ETX路由判據的探測包中有探測包生成的時間、歷史時間內接收到的相鄰節點的IP信息及其發出的探測包的數目[10]。改進ETX判據，需在探測包中加入節點地理位置的信息，預測節點下一時刻的位置。文中的路由判據在DSR路由協議內實現，其探測包的格式可以改進為：

struct link_probe{

float now_;

……

double position_x;//①

double position_y;//②

double position_z//③

};

其中，①、②、③三句為探測包中添加的信息，position_x、position_y、position_z為節點的地理位置在三維直角坐標系中的三維坐標。

2.2 利用Markov模型預測節點下一時刻地理位置

Markov鏈是一種離散時間隨機過程，可以根據當前位置，預測下一時刻位置[11]。Markov模型可以很好地預測基于時間序列的各種參數，是一種消耗代價小、準確率較高的地理位置預測方法。其基本思想為：Xn=i表示在n時刻對象處于狀態i，對于每一個狀態i，存在一個固定概率Pij≥0，使其下一時刻處于狀態j[12-13]。其公式為：

Pr(Xn+1=j|Xn=i,Xn-1=in-1,…,X1=i1,

X0=i0)=Pij

(2)

對于上述公式，可以解釋為：任何下一時刻的狀態Xn+1獨立于過去時刻的狀態Xn-1，…，X1，X0，只取決于上一時刻狀態Xn[12-13]，即

Pr(Xn+1=j|Xn=i,Xn-1=in-1,…,X1=i1,

X0=i0)=Pr(Xn+1=j|Xn=i)=Pij

(3)

建立轉移概率矩陣：

(4)

矩陣的行元素表示歷史位置(狀態)，列元素表示下一個位置。矩陣元素表示在行元素代表的歷史位置(狀態)的條件下的下一個位置到達列元素代表的位置的概率。

(5)

在進行移動預測時，根據軌跡定位到轉移概率矩陣中的相應行，該行中最大概率值對應的列所代表的位置為預測結果：

Xp=argmax{p{Xn+1|C}}

(6)

其中，Xp為預測結果；C為當前位置。

對于ETX路由判據，由于其周期性廣播探測包，時間序列為離散的，故文中涉及到的對于地理位置的預測可以使用該方法。根據節點在t-1時刻和t時刻的地理位置信息，利用Markov模型分別預測出t+1時刻節點的位置，再利用最小均方誤差預測，修正計算出節點在t+1的地理位置作為最終預測結果。

2.3 判斷下一時刻節點是否在各自通信范圍內

利用上述方法分別計算出相鄰節點i和j各自在下一時刻的地理位置，并據此計算出兩個相鄰節點下一時刻的距離：

d=

(7)

其中，xi、yi分別指兩個相鄰節點[14-15]。

3 測試與仿真

3.1 仿真環境

基于Ubuntu操作系統的NS-2仿真平臺進行仿真模擬實驗，實驗使用DSR路由協議。NS-2是一種面向對象的網絡模擬器，使用OTCL和C++兩種語言，可用于模擬各種不同的通信網絡和通信協議[16-17]。DSR(dynamic source routing，動態源路由)協議是一種按需更新反應式路由協議[18]。

實驗設計20個節點隨機分布在一個800 m×800 m的區域內，每個節點的通信范圍均為250 m，信道容量2 Mbit/s，如圖1所示。

圖1 仿真環境

仿真流程如圖2所示。

圖2 仿真流程

3.2 仿真結果

首先固定節點移動速度，改變業務速率，分別仿真分析加入改進的ETX路由判據節點的吞吐量、丟包率和時延的變化情況。

固定節點的移動速度為30 m/s，分別改變節點的業務速率進行仿真實驗。每個節點的業務速率從5 kbps增加到30 kbps。隨著節點業務速率的不斷提升，DSR和加入改進ETX路由協議的吞吐量均有提升，且加入改進ETX路由協議的提升更加明顯。當節點速率為5 kbps和10 kbps時，改進ETX路由協議和DSR路由協議的吞吐量大致相同，但是當節點業務速率進一步提升時，DSR路由協議的吞吐量最終維持在280 kbps左右，而改進ETX路由協議可達到390 kbps，改進ETX路由協議的吞吐量提高了約40%。仿真結果如圖3所示。

圖3 吞吐量隨業務速率的變化

從丟包率來看，隨著業務速率的不斷提升，相應的DSR路由協議和改進的ETX路由協議的丟包率均明顯提升，但改進ETX路由協議的丟包率均小于DSR路由協議。當節點業務速率為30 kbps時，丟包率降低約30%。從時延來看，改進的ETX路由協議對于業務時延的保障顯著優于DSR路由算法，業務速率在20 kbps以內，時延基本保持不變，業務速率大于20 kbps，其時延才會提高，但仍然明顯低于DSR路由協議，當節點業務速率為30 kbps時，平均時延降低了約60%，如圖4和圖5所示。

圖4 丟包率隨業務速率的變化

圖5 時延隨業務速率的變化

再固定節點的業務速率，改變移動速度，分別仿真分析加入改進的ETX路由判據前后節點的吞吐量、丟包率和時延的變化情況。

固定節點的業務速率為25 kbps，分別改變節點的移動速度進行仿真實驗。每個節點的移動速度從5 m/s增加到30 m/s。隨著節點移動速度的不斷提升，DSR和加入改進ETX路由協議的吞吐量顯著降低，因為隨著節點的移動網絡拓撲發生變化，DSR需要不斷發送探測包更新路由表。但加入改進ETX路由協議的降低幅度較小。當節點速率為5 kbps和10 kbps時，改進ETX路由協議和DSR路由協議的吞吐量大致相同，但是當節點業務速率進一步提升時，DSR路由協議的吞吐量最終維持在280 kbps左右，而改進的ETX路由協議則可以達到390 kbps，改進ETX路由協議的吞吐量提高了30%，數據變化趨勢與固定節點移動速度、改變業務速率時類似。

從丟包率來看，節點移動速度的不斷提升，相應的DSR路由協議和改進的ETX路由協議的丟包率均有增加，但是ETX路由協議的丟包率始終小于DSR路由協議，當節點業務速率為30 m/s時，丟包率降低約30%。從時延來看，從兩種路由協議在平均時延方面的對比可以看出，當節點業務速率不變、移動速度增加時，ETX路由協議的時延始終保持在DSR路由協議時延的1/3以下，節點移動速度為30 m/s時，此時延比例降低為1/5；改進ETX路由協議時延保持了良好的穩定性，節點移動速度由5 m/s增加到30 m/s時，平均時延比未改進時降低約80%，較為明顯。兩組的數據變化趨勢也均與固定節點移動速度，改變業務速率時類似。再次說明ETX路由協議對于業務的時延具有良好的保障。

綜上，在加入改進ETX路由協議后，當節點業務速率不變時，隨著節點運動速度的增加，其吞吐量比沒有加入改進ETX的DSR路由協議有所提高，時延和丟包率有所降低；當節點的運動速度不變時，隨著節點業務速率的增加，其吞吐量也比沒有加入改進ETX的DSR路由協議有所提高，時延和丟包率有所降低。在節點運動頻率較高的網絡系統中，改進的ETX路由判據明顯提高了網絡整體性能，且隨著節點運動速度和業務速率的提高，這種網絡性能的提高越來越明顯。

4 結束語

傳統ETX路由判據由于缺乏對節點運動引起的網絡變化的預測，存在路由選擇不盡合理、影響網絡整體性能的問題。在傳統ETX路由判據的基礎上，文中提出一種基于Markov地理位置預測模型的ETX路由判據，預測節點下一時刻的地理位置，確定原路由是否失效，從而優化路由的選擇，提高網絡整體性能。在NS-2中的仿真結果表明，在節點運動頻率較高時，改進的路由判據明顯提高了網絡的整體性能。