基于Markov預(yù)測模型的ETX路由判據(jù)研究

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

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

0 引 言

無線Mesh網(wǎng)絡(luò)結(jié)合了ad hoc網(wǎng)絡(luò)和傳統(tǒng)無線網(wǎng)絡(luò)的優(yōu)點。其核心指導思想是讓網(wǎng)絡(luò)中的每個移動或固定節(jié)點都可以發(fā)送和接收信號，節(jié)點間的通信不再需要接入點轉(zhuǎn)接。通過多跳網(wǎng)絡(luò)的構(gòu)造，數(shù)據(jù)可以通過相鄰節(jié)點間的轉(zhuǎn)發(fā)傳送到目的地，減小了流量擁塞的可能性，大大提高了網(wǎng)絡(luò)整體性能[1-2]。

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

1 ETX判據(jù)及其改進

1.1 傳統(tǒng)ETX判據(jù)

ETX路由判據(jù)的思路是根據(jù)歷史時間內(nèi)成功傳輸?shù)侥康墓?jié)點所需要的平均發(fā)送次數(shù)來預(yù)測未來一段時間成功傳輸?shù)侥康墓?jié)點所需要的發(fā)送次數(shù)。這一路由判據(jù)一般應(yīng)用于無線Mesh網(wǎng)絡(luò)[4]。無線鏈路的ETX是指無線鏈路上成功傳輸一個分組時所需的平均預(yù)計傳輸次數(shù)[5]。ETX中，每個節(jié)點定期廣播一個固定長度的專用鏈路探測包，這個數(shù)據(jù)包包含最后一段探測時間內(nèi)從每個相鄰節(jié)點接收到的探測分組的數(shù)據(jù)。

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

ETX=1/df×dr

(1)

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

1.2 改進的ETX判據(jù)

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

2 改進ETX判據(jù)的實現(xiàn)

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

傳統(tǒng)的ETX路由判據(jù)的探測包中有探測包生成的時間、歷史時間內(nèi)接收到的相鄰節(jié)點的IP信息及其發(fā)出的探測包的數(shù)目[10]。改進ETX判據(jù)，需在探測包中加入節(jié)點地理位置的信息，預(yù)測節(jié)點下一時刻的位置。文中的路由判據(jù)在DSR路由協(xié)議內(nèi)實現(xiàn)，其探測包的格式可以改進為：

struct link_probe{

float now_;

……

double position_x;//①

double position_y;//②

double position_z//③

};

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

2.2 利用Markov模型預(yù)測節(jié)點下一時刻地理位置

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

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

X0=i0)=Pij

(2)

對于上述公式，可以解釋為：任何下一時刻的狀態(tài)Xn+1獨立于過去時刻的狀態(tài)Xn-1，…，X1，X0，只取決于上一時刻狀態(tài)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)

建立轉(zhuǎn)移概率矩陣：

(4)

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

(5)

在進行移動預(yù)測時，根據(jù)軌跡定位到轉(zhuǎn)移概率矩陣中的相應(yīng)行，該行中最大概率值對應(yīng)的列所代表的位置為預(yù)測結(jié)果：

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

(6)

其中，Xp為預(yù)測結(jié)果；C為當前位置。

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

2.3 判斷下一時刻節(jié)點是否在各自通信范圍內(nèi)

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

d=

(7)

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

3 測試與仿真

3.1 仿真環(huán)境

基于Ubuntu操作系統(tǒng)的NS-2仿真平臺進行仿真模擬實驗，實驗使用DSR路由協(xié)議。NS-2是一種面向?qū)ο蟮木W(wǎng)絡(luò)模擬器，使用OTCL和C++兩種語言，可用于模擬各種不同的通信網(wǎng)絡(luò)和通信協(xié)議[16-17]。DSR(dynamic source routing，動態(tài)源路由)協(xié)議是一種按需更新反應(yīng)式路由協(xié)議[18]。

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

圖1 仿真環(huán)境

仿真流程如圖2所示。

圖2 仿真流程

3.2 仿真結(jié)果

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

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

圖3 吞吐量隨業(yè)務(wù)速率的變化

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

圖4 丟包率隨業(yè)務(wù)速率的變化

圖5 時延隨業(yè)務(wù)速率的變化

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

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

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

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

4 結(jié)束語

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