MANETs中能量感知-低擁塞的動(dòng)態(tài)源路由

邢靜宇，單平平

(南陽理工學(xué)院，河南 南陽 473000)

0 引 言

移動(dòng)自組織網(wǎng) (Mobile ad hoc Networks，MANETs)[1-2]是無中心控制單元、并由節(jié)點(diǎn)自行構(gòu)建的無線網(wǎng)絡(luò)。由于節(jié)點(diǎn)可自由移動(dòng)，MANETs網(wǎng)絡(luò)拓?fù)渚哂袆?dòng)態(tài)變化特性。而變化的拓?fù)涫沟镁W(wǎng)絡(luò)通信鏈路不穩(wěn)定。此外，節(jié)點(diǎn)通信距離有限，節(jié)點(diǎn)需要通過多跳通信才能將數(shù)據(jù)傳輸更遠(yuǎn)的目的節(jié)點(diǎn)。

多跳通信是由一系列的中間節(jié)點(diǎn)轉(zhuǎn)發(fā)而形成的通信方式[3]。當(dāng)擁有數(shù)據(jù)包的節(jié)點(diǎn)(源節(jié)點(diǎn))需要以多跳通信方式向遠(yuǎn)距離的目的節(jié)點(diǎn)傳輸數(shù)據(jù)包時(shí)，源節(jié)點(diǎn)就需構(gòu)建一條合適的路徑。實(shí)際上，此路徑也是由一系列的中間節(jié)點(diǎn)組成[4]。構(gòu)建合適路徑的過程也稱為路由發(fā)現(xiàn)(Route-discovery)。然而，由于MANETs的拓?fù)鋭?dòng)態(tài)變化、節(jié)點(diǎn)通信距離短等原因，有效地完成路由發(fā)現(xiàn)過程存在挑戰(zhàn)。

針對(duì)MANETs網(wǎng)絡(luò)特性，研究人員提出了許多路由協(xié)議[6-7]。這些協(xié)議可分為三類：按需路由、表格驅(qū)動(dòng)路由以及混合路由。這些路由均需要實(shí)施路由發(fā)現(xiàn)過程。

在表格驅(qū)動(dòng)路由中，節(jié)點(diǎn)得先獲取并維持路由信息，并且移動(dòng)節(jié)點(diǎn)能夠周期地共享路由信息。在按需路由中，僅當(dāng)節(jié)點(diǎn)需要傳輸數(shù)據(jù)包時(shí)，它才建立路徑，節(jié)點(diǎn)無需預(yù)先維護(hù)路由信息，這也是按需路由的由來。而混合路由結(jié)合表格驅(qū)動(dòng)路由和按需路由這兩者特點(diǎn)。通常，混合路由將網(wǎng)絡(luò)劃分多個(gè)區(qū)域，在區(qū)域內(nèi)和區(qū)域間實(shí)施不同的路由發(fā)現(xiàn)策略。在區(qū)域內(nèi)實(shí)施表格驅(qū)動(dòng)路由，而區(qū)域間實(shí)施按需路由，但是這種策略增加了路由開銷。

動(dòng)態(tài)源路由(Dynamic Source Routing, DSR)[8]是工作于TCP/IP協(xié)議簇的網(wǎng)際層的路由協(xié)議。通過發(fā)送路由請(qǐng)求、應(yīng)答和確認(rèn)請(qǐng)求等控制包，建立從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路。DSR是按需路由的代表，被廣泛應(yīng)用于MANETs。

為此，考慮到動(dòng)態(tài)源路由(Dynamic Source Routing, DSR)的廣泛應(yīng)用性，分析了傳統(tǒng)DSR路由的不足，并提出基于能量感知和低擁塞的DSR改進(jìn)路由(Energy-aware and congestion-less -based DSR improved routing, EACL-DSR)。EACL-DSR路由在構(gòu)建路由時(shí)，充分考慮了節(jié)點(diǎn)的擁塞率和能量信息，避免了傳統(tǒng)DSR路由因流量不均衡而引起的擁塞問題。仿真數(shù)據(jù)表明，提出的EACL-DSR路由有效地提高了數(shù)據(jù)包傳遞率和吞吐量。

1 DSR路由及問題描述

DSR路由主要有兩個(gè)階段構(gòu)成。在第一階段，源節(jié)點(diǎn)構(gòu)建通往目的節(jié)點(diǎn)的路由；在第二階段，對(duì)上一階段的構(gòu)建的路由進(jìn)行維護(hù)。當(dāng)節(jié)點(diǎn)需要傳輸數(shù)據(jù)，它首先查詢緩沖區(qū)[9]。此緩沖區(qū)存儲(chǔ)已構(gòu)建的路由。如果已有存在的路由，它就廣播請(qǐng)求包RREQ。當(dāng)鄰居節(jié)點(diǎn)接收RREQ，它也沿著網(wǎng)絡(luò)轉(zhuǎn)播RREQ，直到它傳輸?shù)侥康墓?jié)點(diǎn)。

RREQ包主要包括四項(xiàng)信息：數(shù)據(jù)包ID、源節(jié)點(diǎn)ID、目的節(jié)點(diǎn)ID、源IP地址、目的IP地址和跳數(shù)清單Hop_List，如表格1所示。

表1 DSR路由中RREQ格式

當(dāng)目的節(jié)點(diǎn)接收到RREQ，它就沿傳輸RREQ反向路徑，并以單播方式回復(fù)RREP，直到源節(jié)點(diǎn)接收RREP。當(dāng)源節(jié)點(diǎn)接收RREP后，它就從RREP中提取已建的路由[10]，并存儲(chǔ)于緩沖區(qū)，并選擇最短路徑傳輸數(shù)據(jù)包。RREQ和RREP的傳輸過程如圖1所示。

圖1 DSR路由發(fā)現(xiàn)階段

為了維護(hù)路由，一旦中間節(jié)點(diǎn)數(shù)據(jù)傳輸失敗，它就通過傳輸路由錯(cuò)誤RERR包通知源節(jié)點(diǎn)。源節(jié)點(diǎn)收到RERR包，源節(jié)點(diǎn)就更新路由。如果緩存區(qū)內(nèi)有可選的路由[11]，就直接從緩存區(qū)內(nèi)選擇新的路由。若沒有，就重新構(gòu)建新路由。

然而，DSR路由也存在一些不足。由于節(jié)點(diǎn)頻繁地移動(dòng)，DSR路由導(dǎo)致低的數(shù)據(jù)傳遞率，并提高了鏈路斷裂概率。而鏈路斷裂后，又需重新構(gòu)建路由，這必然會(huì)增加路由開銷，也會(huì)增加節(jié)點(diǎn)能量消耗。這些不足，促使需要對(duì)DSR路由進(jìn)行改進(jìn)。此外，DSR路由在進(jìn)行路由發(fā)現(xiàn)時(shí)，僅轉(zhuǎn)播第一時(shí)間所接收的RREQ，而并沒有考慮到節(jié)點(diǎn)的信息，如能量、節(jié)點(diǎn)負(fù)載，這均不利于路由穩(wěn)定。

2 EACL-DSR

EACL-DSR路由對(duì)DSR路由的發(fā)現(xiàn)階段進(jìn)行修改。傳統(tǒng)的DSR路由總是選擇最短路徑傳輸數(shù)據(jù)，而沒有考慮到能量和擁塞情況。若一直采用最短路徑傳輸，勢(shì)必會(huì)影響部分節(jié)點(diǎn)的負(fù)載過重，這不利于網(wǎng)內(nèi)流量的平衡和路由的穩(wěn)定。

在EACL-DSR路由中，一旦接收到RREQ包，節(jié)點(diǎn)就判斷自己的擁塞率。如果擁塞率低于預(yù)定的閾值[12]，則接收該RREQ包，否則丟棄。一旦接收RREQ包后，節(jié)點(diǎn)就計(jì)算自己的適度因子(Fitness Factor, FF)，其包含了網(wǎng)絡(luò)負(fù)載和節(jié)點(diǎn)剩余能量信息。隨后，將FF值嵌入RREQ包，再繼續(xù)向目的節(jié)點(diǎn)轉(zhuǎn)播。

當(dāng)中間節(jié)點(diǎn)接收RREQ包后，先確認(rèn)是否第一次接收了該數(shù)據(jù)包。隨后，再確認(rèn)自己的擁塞率。如果擁塞率低于閾值，就接收，并從中提取包中的FF值，再判斷FF值是否滿足閾值。如果不滿足，就不轉(zhuǎn)播RREQ。否則，節(jié)點(diǎn)就計(jì)算的FF值，再嵌入RREQ包中，再轉(zhuǎn)播，直至目的節(jié)點(diǎn)接收了該RREQ包。

當(dāng)目的節(jié)點(diǎn)接收RREQ包，目的節(jié)點(diǎn)就依據(jù)傳輸RREQ包的反向路由回復(fù)RREP。當(dāng)源節(jié)點(diǎn)接收RREP包后，就沿著該路徑傳輸數(shù)據(jù)包。

2.1 擁塞率

擁塞率反映了節(jié)點(diǎn)當(dāng)前需要傳輸?shù)臄?shù)據(jù)包數(shù)[13]。具體而言，每個(gè)節(jié)點(diǎn)均有一個(gè)緩存區(qū)，且緩存區(qū)的容量表示Buffer。而進(jìn)入隊(duì)列里的數(shù)據(jù)包，表示節(jié)點(diǎn)即將需要傳輸?shù)臄?shù)據(jù)包。用Numqueue表示進(jìn)入隊(duì)列里的數(shù)據(jù)包數(shù)。Numqueue占Buffer的比例越大，擁塞情況越嚴(yán)重。因此，節(jié)點(diǎn)i擁塞率ρi:

(1)

2.2 適度因子FF

FF在EACL-DSR路由協(xié)議中扮演著重要作用。傳統(tǒng)的DSR路由，只是將第一時(shí)間接收的RREQ轉(zhuǎn)播[14]，后期接收的RREQ并不理睬。而提出的EACL-DSR路由考慮了節(jié)點(diǎn)的擁塞率和適度因子。適度因子FF的定義如式(2)所示：

(2)

2.3 路由發(fā)現(xiàn)過程

EACL-DSR路由在轉(zhuǎn)播RREQ時(shí)，充分考慮了節(jié)點(diǎn)擁塞率和適度因子[15]。路由發(fā)現(xiàn)過程如圖2所示。具體而言，當(dāng)源節(jié)點(diǎn)S需要向目的節(jié)點(diǎn)D傳輸數(shù)據(jù)時(shí)，節(jié)點(diǎn)S先確認(rèn)它的緩存區(qū)內(nèi)是否有通往節(jié)點(diǎn)D的路由，如果有，就依據(jù)此路由傳輸數(shù)據(jù)包。若沒有，則節(jié)點(diǎn)S就開啟路由發(fā)現(xiàn)過程。

圖2 路由框架圖

圖2描述了路由發(fā)現(xiàn)過程。節(jié)點(diǎn)S先廣播RREQ包(記為RREQ_S)，假定節(jié)點(diǎn)N1接收RREQ。然后節(jié)點(diǎn)N1先計(jì)算自己擁塞率ρN1，并判斷ρN1是否小于閾值ρth。如果滿足，則節(jié)點(diǎn)N1就接納此RREQ。然后，節(jié)點(diǎn)N1就依據(jù)式(2)計(jì)算它的適度因子，并將FF插入RREQ包中，并轉(zhuǎn)播RREQ包(記為RREQ_N1)。表2顯示了EACL-DSR路由中的RREQ的格式：

表2 EACL-DSR路由中RREQ格式

假定節(jié)點(diǎn)N2接收了來自節(jié)點(diǎn)i的發(fā)送的RREQ_N1。類似地，節(jié)點(diǎn)N2先檢測(cè)自己的擁塞率ρN2是否小于閾值ρth。如果滿足，則接納RREQ_N1。到目前為止，節(jié)點(diǎn)N2與節(jié)點(diǎn)N1的處理過程相似，但后續(xù)處理過程不同[16]。

隨后，節(jié)點(diǎn)N2就從RREQ_N1提取FF值，并判斷FF值是否大于閾值FFth。如果滿足，則接納RREQ_N1包，也計(jì)算自己FF值，然后插入RREQ_N1包中，再轉(zhuǎn)播RREQ包(記為RREQ_N2)。

重復(fù)上述過程，直到目的節(jié)點(diǎn)D接收到RREQ包。一旦目的節(jié)點(diǎn)D接收了RREQ包，就沿著傳輸RREQ包的路徑回復(fù)RREP包。當(dāng)源節(jié)點(diǎn)接收了RREP，源節(jié)點(diǎn)就沿著此路徑傳輸數(shù)據(jù)。

圖3 RREQ的轉(zhuǎn)播流程

2.4 路由發(fā)現(xiàn)示例

圖4顯示19個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中S、D分別表示源節(jié)點(diǎn)和目的節(jié)點(diǎn)。由于傳統(tǒng)的DSR路由沒有考慮節(jié)點(diǎn)能量和擁塞率信息，它通常只選擇最短路徑作為數(shù)據(jù)傳輸?shù)耐ǖ溃碨→N3→N6→N10→N14→D。

而EACL-DSR路由考慮了每個(gè)節(jié)點(diǎn)的擁塞率和FF值。假定每個(gè)節(jié)點(diǎn)的擁塞率和FF值如表3所示，其中ρth=0.3，F(xiàn)Fth=30，Buffer=10。

圖4 傳統(tǒng)的DSR路由

在EACL-DSR路由中，源節(jié)點(diǎn)S先廣播RREQ包。一旦接收RREQ包，源節(jié)點(diǎn)S的鄰居節(jié)點(diǎn)確認(rèn)是否滿足它們的擁塞率。由于節(jié)點(diǎn)3不滿足擁塞率(它的擁塞率大于閾值)，則節(jié)點(diǎn)3就丟棄RREQ包，而其他節(jié)點(diǎn)1、4滿足要求，就接納RREQ包。隨后，這些節(jié)點(diǎn)將FF加入RREQ，再轉(zhuǎn)播。

當(dāng)節(jié)點(diǎn)5接收了來自節(jié)點(diǎn)4轉(zhuǎn)播的RREQ包后，然后檢測(cè)擁塞率和FF值。隨后，再轉(zhuǎn)播。重復(fù)上述過程，直到RREQ包傳輸至目的節(jié)點(diǎn)D。依據(jù)表3可知，節(jié)點(diǎn)N9、N13、N11、N16不滿足條件，無法構(gòu)建路由，最終形成了S→N1→N5→N6→N10→N14→D路徑，如圖5所示。

圖5 EACL-DSR路由示例

3 數(shù)值分析

3.1 仿真場(chǎng)景

利用NS2.35仿真軟件建立仿真平臺(tái)[17-18]。N個(gè)節(jié)點(diǎn)隨機(jī)分布于1500×1500 m2區(qū)域，節(jié)點(diǎn)的傳輸范圍為250 m。具體的仿真參數(shù)如表4所示。

表4 仿真參數(shù)

為了更充分地分析EACL-DSR協(xié)議性能，建立兩個(gè)仿真場(chǎng)景：密度場(chǎng)景和流量場(chǎng)景。在密度場(chǎng)景中，節(jié)點(diǎn)數(shù)從20～160變化，數(shù)據(jù)率為30 kbps；而在流量場(chǎng)景中，數(shù)據(jù)率從10～40 kbps變化，節(jié)點(diǎn)數(shù)100。

3.2 密度場(chǎng)景

首先分析節(jié)點(diǎn)數(shù)的變化對(duì)平均吞吐量的變化，實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

圖6 平均吞吐量

從圖6可知，當(dāng)節(jié)點(diǎn)數(shù)為50時(shí)，EACL-DSR和DSR路由的吞吐量達(dá)到最高。然而，當(dāng)節(jié)點(diǎn)數(shù)從50增加至150時(shí)，吞吐量也隨之下降。原因在于：當(dāng)節(jié)點(diǎn)數(shù)增加，參與路由的節(jié)點(diǎn)也隨之增加，節(jié)點(diǎn)能耗也增加，加速了節(jié)點(diǎn)能量消耗速度。同時(shí)，節(jié)點(diǎn)數(shù)的增加會(huì)引起節(jié)點(diǎn)對(duì)信道資源的增加。最終，控制吞吐量。此外，與DSR路由相比，提出的EACL-DSR路由提高了網(wǎng)絡(luò)吞吐量。

隨后，分析了節(jié)點(diǎn)數(shù)對(duì)數(shù)據(jù)包傳遞率的變化，實(shí)驗(yàn)數(shù)據(jù)如圖7所示。

圖7 數(shù)據(jù)包傳遞率

圖6的曲線變化與圖6類似。當(dāng)節(jié)點(diǎn)數(shù)大于50時(shí)后，數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的增加而下降。原因在于：當(dāng)節(jié)點(diǎn)數(shù)增加至一定數(shù)量后，再增加節(jié)點(diǎn)數(shù)，會(huì)引用數(shù)據(jù)包傳輸?shù)呐鲎?，最終，降低數(shù)據(jù)包傳遞率。與DSR路由相比，提出的EACL-DSR路由的數(shù)據(jù)包傳遞率得到有效地提升。這主要是因?yàn)椋篍ACL-DSR路由在構(gòu)建路由時(shí)，考慮了節(jié)點(diǎn)能量和擁塞信息，避免了擁塞率高的、低能量節(jié)點(diǎn)構(gòu)建路由。

3.3 流量場(chǎng)景

數(shù)據(jù)率越快，網(wǎng)絡(luò)內(nèi)流量越大。本次實(shí)驗(yàn)分析數(shù)據(jù)率對(duì)吞吐量和數(shù)據(jù)包傳遞率的影響，實(shí)驗(yàn)數(shù)據(jù)分別如圖8、圖9所示。

圖8 平均吞吐量

圖9 平均數(shù)據(jù)包傳遞率

從圖8可知，數(shù)據(jù)率的增加，有利于吞吐量的提升。這主要是因?yàn)椋簲?shù)據(jù)率越大，單位時(shí)間內(nèi)傳輸?shù)臄?shù)據(jù)量就越多。但從圖8可知，吞吐量與數(shù)據(jù)率并不完全呈線性關(guān)系。盡管數(shù)據(jù)率提高，但是只有網(wǎng)絡(luò)能夠成功傳輸數(shù)據(jù)，才能提高吞吐量。而EACL-DSR路由提高了平均吞吐量。這要?dú)w功于：EACL-DSR路由避免了擁塞率高的節(jié)點(diǎn)構(gòu)建路由，增加了網(wǎng)終吞吐量。

圖9顯示了平均數(shù)據(jù)包傳遞率隨數(shù)據(jù)率的變化曲線。從圖9可知，數(shù)據(jù)率的增加降低了平均數(shù)據(jù)包傳遞率。原因在于：數(shù)據(jù)率的增加，加大了節(jié)點(diǎn)負(fù)載，提高了路由斷裂的概率，最終，降低了數(shù)據(jù)包傳遞率。與DSR路由相比，提出的EACL-DSR路由提高了數(shù)據(jù)包傳遞率。

4 結(jié) 語

結(jié)合DSR路由，提出新的路由EACL-DSR。EACL-DSR路由以能量效率方式處理擁塞問題。提出的EACL-DSR路由不僅處理了擁塞，也提高能量利用率，進(jìn)而延長(zhǎng)了網(wǎng)絡(luò)壽命。仿真數(shù)據(jù)表明，提出的EACL-DSR路由提高了網(wǎng)絡(luò)吞吐量和數(shù)據(jù)包傳遞率。后期，將進(jìn)一步優(yōu)化路由算法，并考慮擁塞率和能量在適度因子中權(quán)重比例，并分析它們比例對(duì)路由性能的影響。