基于鏈路連通時(shí)間的移動(dòng)Ad Hoc網(wǎng)絡(luò)路由

林 勇，宋三華

(1.重慶電子工程職業(yè)學(xué)院 通信工程學(xué)院，重慶 401331；2. 黃淮學(xué)院 信息工程學(xué)院，河南 駐馬店 463000;)

0 引 言

移動(dòng)Ad Hoc網(wǎng)絡(luò)是一種無(wú)中心、自組織的、由多個(gè)具有通信能力的移動(dòng)節(jié)點(diǎn)組成的無(wú)線網(wǎng)絡(luò)架構(gòu)。這些移動(dòng)節(jié)點(diǎn)可自行組建網(wǎng)絡(luò)[2]，既可獨(dú)立運(yùn)行，也可轉(zhuǎn)發(fā)數(shù)據(jù)，扮演路由器的角色。由于無(wú)線Ad Hoc網(wǎng)絡(luò)具有靈活、自行組織特點(diǎn)，它廣泛應(yīng)用于救援、軍事行動(dòng)等靈活的通信系統(tǒng)應(yīng)用場(chǎng)合。然而，節(jié)點(diǎn)移動(dòng)是無(wú)線Ad Hoc網(wǎng)絡(luò)典型特性，加大了網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，這使得無(wú)線Ad Hoc網(wǎng)絡(luò)的數(shù)據(jù)傳輸成為挑戰(zhàn)。

目前，針對(duì)無(wú)線Ad Hoc網(wǎng)絡(luò)，研究人員提出不同的路由協(xié)議，比如DSR、OLSR[3]、AODV和DSDV[4]路由。按需距離矢量(Ad Hoc On-demand Distance Vector，AODV)是典型的無(wú)線Ad Hoc網(wǎng)絡(luò)路由，但是AODV路由仍存在一些不足。這些路由并沒有考慮了節(jié)點(diǎn)移動(dòng)性。為此，研究人員提出了AODV的改進(jìn)路由。

曹文君等[5]提出基于鏈路連通壽命的AODV的改進(jìn)路由。它先計(jì)算節(jié)點(diǎn)間的速度差，再構(gòu)建速度差最低的穩(wěn)定的路徑傳輸數(shù)據(jù)。而劉大勇等[6]從時(shí)延角度選擇路由，降低端到端傳輸時(shí)延。此外，蔡菁等[7]也對(duì)AODV路由進(jìn)行優(yōu)化，利用單播和廣播的混合方式傳輸控制包，再減少?gòu)V播幀數(shù)量，最后提高路由穩(wěn)定性。

然而，這些路由只從節(jié)點(diǎn)移動(dòng)信息方面決策路由，并沒有考慮到信道衰減信息。而實(shí)際上，無(wú)線網(wǎng)絡(luò)鏈路容易受到外界環(huán)境影響，這更加劇了網(wǎng)絡(luò)拓?fù)涞淖兓?，最終影響了路由的穩(wěn)定性。

為此，本文針對(duì)無(wú)線Ad Hoc網(wǎng)絡(luò)的數(shù)據(jù)傳輸問題，展開分析，提出基于LET-RP路由。LET-RP路由首先了計(jì)算鏈路連通時(shí)間，然后從選擇連通時(shí)間長(zhǎng)的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而構(gòu)建穩(wěn)定的路由，克服無(wú)線Ad Hoc網(wǎng)絡(luò)的拓?fù)鋭?dòng)態(tài)性。在估計(jì)鏈路連通時(shí)間時(shí)，不僅考慮了節(jié)點(diǎn)的移動(dòng)信息，還考慮了信道衰減統(tǒng)計(jì)信息，這有利于提高路由穩(wěn)定性。實(shí)驗(yàn)數(shù)據(jù)表明，提出的LET-RP路由有效地降低了端到端傳輸時(shí)延，并提高了吞吐量。

1 LET-RP路由算法

LET-RP路由是從穩(wěn)定鏈路角度選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。為此，先利用節(jié)點(diǎn)的移動(dòng)參數(shù)和信道衰落統(tǒng)計(jì)信息計(jì)算鏈路的連通時(shí)間，然后選擇連通時(shí)間最長(zhǎng)的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

1.1 鏈路連通時(shí)間

鏈路的連通時(shí)間受到節(jié)點(diǎn)移動(dòng)和信道衰落兩方面影響。為此，先利用節(jié)點(diǎn)移動(dòng)信息估計(jì)鏈路的連通期望時(shí)間。

假定車輛i與j的鏈路表示為ij，它們的位置坐標(biāo)分別為(xi,yi)、(xj,yj)。結(jié)合文獻(xiàn)[8]，鏈路ij的連通期望時(shí)間LETij：

(1)

其中θi、θj分別表示車輛i和j的移動(dòng)方向。而?i、?j分別表示車輛?i和?j的瞬時(shí)移動(dòng)速度。同時(shí)，a=?icosθi-?jcosθj、b=xi-xj、c=?isinθi-?jsinθj、d=yi-yj。

接下來(lái)，分析引用反映信道衰落的變量ε，其定義如式(2)所示。在無(wú)衰落的理想傳輸環(huán)境，ε=0。而在含有建筑物的都市環(huán)境，ε一般較大。

ε=1-E[φ]

(2)

其中φ表示鏈路ij連通概率。通常認(rèn)為，接收到的信號(hào)功率大于預(yù)定的閾值，就可認(rèn)為鏈路是連通的。而E[φ]表示φ的期望。

最后，依據(jù)LETij和變量ε估計(jì)鏈路的連通時(shí)間ELLTij，如式(3)所示：

ELLTij=LETij×(1-ε)

(3)

1.2 基于信道統(tǒng)計(jì)的E[φ]估計(jì)

首先，引用基于Nakagami-m的無(wú)線信道模型[9]。若所接收的信號(hào)功率表示為p，信號(hào)功率閾值表示為Rth。因此，連通概率φ可表示為p和Rth的函數(shù)，如式(4)所示：

(4)

結(jié)合文獻(xiàn)[9]，也可用車輛間距離d和車輛傳輸距離R表示連通概率φ，如式(5)所示：

(5)

然而，車輛i、j不斷移動(dòng)，它們間的距離d是不斷變化的。據(jù)此，概率φ也是動(dòng)態(tài)變化的。為此，先引用連續(xù)隨機(jī)變量Z替換式(5)中的距離d，然后，再結(jié)合文獻(xiàn)[10]，可計(jì)算φ的期望，如式(6)所示：

(6)

其中fZ(z)為概率密度函數(shù)。

由于E[φ]與車輛間距離d相關(guān)，依據(jù)車輛相對(duì)移動(dòng)方向，分三種情況討論E[φ]。

(1)車輛i與j以等速，同向移動(dòng)。在這種情況下，它們間的距離dij為常數(shù)。據(jù)此，E[φ]可表示為：

(7)

(2)當(dāng)車輛i與j反向移動(dòng)。此時(shí)，它們間距離逐漸增加，如圖1所示。在這種情況下，先計(jì)算Z的概率密度函數(shù)：

圖1 反向移動(dòng)的通信鏈路

(8)

最后，利用式(8)計(jì)算E[φ]：

(9)

(3)當(dāng)車輛同向移動(dòng)，且車速不同，如圖2所示。在這種情況下，變量Z的概率密度函數(shù)如式(10)所示：

(10)

圖2 同向通信連接

類似地，再利用式(10)計(jì)算E[φ]，如式(11)所示：

(11)

1.3 轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇策略

LET-RP算法引用基于競(jìng)爭(zhēng)轉(zhuǎn)發(fā)(Contention-based Forwarding, CBF)[8]的策略，選擇下一跳節(jié)點(diǎn)。基于CBF的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇方案是屬分布，即每輛車依據(jù)移動(dòng)參數(shù)和鏈路的多徑衰落參數(shù)自己選擇下一跳的轉(zhuǎn)發(fā)節(jié)點(diǎn)。這種策略提高了消息的分發(fā)效率。

LET-RP算法引用鏈路穩(wěn)定函數(shù)(Link Stability, LS)作為選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的度量指標(biāo)，其定義如式(13)所示：

(12)

其中k是一個(gè)常數(shù)，其決定了函數(shù)的增長(zhǎng)率。

為此，每個(gè)車輛依據(jù)LS設(shè)置定時(shí)器，如式(13)所示：

t(LS)=T×(1-LS)

(13)

其中T表示最大的轉(zhuǎn)發(fā)時(shí)延。

依據(jù)式(13)可知，車輛定時(shí)時(shí)間取決于LS。如果，當(dāng)兩個(gè)或多個(gè)車輛的LS相近，則可能會(huì)產(chǎn)生數(shù)據(jù)包冗余。為此，需要采取策略抑制冗余。為此，在利用LS設(shè)置定時(shí)器時(shí)，再引用另一參數(shù)，進(jìn)而降低發(fā)生數(shù)據(jù)包冗余的概率[11-12]。

眾所周知，路徑長(zhǎng)度是路由性能的一個(gè)重要指標(biāo)。路徑越長(zhǎng)，參數(shù)的節(jié)點(diǎn)越多，競(jìng)爭(zhēng)越激烈。為此，引用衡量路徑長(zhǎng)度的變量P，其定義如式(14)所示：

(14)

再結(jié)合LS和P參數(shù)，并引用權(quán)重均值構(gòu)造函數(shù)f：

f=α×LS+(1-α)×P

(15)

最后，依據(jù)函數(shù)f設(shè)置定時(shí)器，如式(16)所示：

t(f)=T×(1-f)

(16)

2 下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇流程

當(dāng)節(jié)點(diǎn)(假定為節(jié)點(diǎn)i)需要轉(zhuǎn)發(fā)數(shù)據(jù)包，就將先廣播路由請(qǐng)求控制包RREQ。鄰居節(jié)點(diǎn)(假定為節(jié)點(diǎn)j)一旦接收了RREQ包，首先檢測(cè)是否接收過此包，若已接收了，就丟棄，否則就依據(jù)式(13)設(shè)置定時(shí)器，并開始計(jì)時(shí)。一旦定時(shí)完畢，并且在定時(shí)過程無(wú)監(jiān)聽到其他節(jié)點(diǎn)向節(jié)點(diǎn)i回復(fù)RREP包時(shí)，節(jié)點(diǎn)j就立即回復(fù)RREP。

一旦接收RREP包，節(jié)點(diǎn)i就將此節(jié)點(diǎn)作為數(shù)據(jù)包的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。從式(13)可知，鏈路的連通時(shí)間越長(zhǎng)，定時(shí)時(shí)間越短，此節(jié)點(diǎn)就第一時(shí)間回復(fù)RREP包。下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇過程如圖3所示。

圖3 選擇下一跳節(jié)點(diǎn)的流程圖

通過圖3所示的策略，選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而形成連通時(shí)間長(zhǎng)的路由傳輸數(shù)據(jù)包。若從一條路由角度分析，整條路由連通時(shí)間等于構(gòu)建這條路由的多條鏈路中的最短的連通時(shí)間。

具體而言，令Rn-1表示由n-1條鏈路構(gòu)成的路由，并且這n-1條鏈路由n個(gè)車輛構(gòu)成。因此，路由Rn-1的有效壽命(Effective Route Life Time, ERLT)就是這n-1條鏈路壽命的最小值，如式(17)所示：

(17)

如圖4所示，車輛(移動(dòng)節(jié)點(diǎn))L、M被選為轉(zhuǎn)發(fā)節(jié)點(diǎn)，進(jìn)而構(gòu)成從RSU至車輛S的路由。從圖5可知，從RSU至車輛S的路由三條鏈路構(gòu)成，并且這三條鏈路的ELLT值分別為12 s、8 s和10 s，最小值為8 s。因此，路由連通時(shí)間為8 s。

圖4 路由示意圖

3 實(shí)驗(yàn)仿真

3.1 實(shí)驗(yàn)環(huán)境

為了更好地分析LET-RP路由性能，利用NS-2.35軟件建立仿真平臺(tái)。網(wǎng)絡(luò)仿真參數(shù)如表1所示。

表1 網(wǎng)絡(luò)仿真參數(shù)

此外，移動(dòng)節(jié)點(diǎn)在750 m×750 m區(qū)域內(nèi)移動(dòng)，并且每個(gè)節(jié)點(diǎn)以Random Way Point 模型移動(dòng)。具有而言，節(jié)點(diǎn)隨機(jī)移動(dòng)至一個(gè)目的地，再暫停一段時(shí)間后，又隨機(jī)選擇一個(gè)目的地再移動(dòng)。具體的移動(dòng)參數(shù)如表2所示。

表2 移動(dòng)參數(shù)

每次實(shí)驗(yàn)獨(dú)立重復(fù)50次，取平均值作為最終數(shù)據(jù)。同時(shí)選擇AODV和AODV-P[13]作為參照，同時(shí)比較它們的路由開銷、吞吐量和端到端傳輸時(shí)延性能。

3.2 數(shù)值分析

首先分析三個(gè)路由協(xié)議的路由開銷。實(shí)驗(yàn)數(shù)據(jù)如圖5所示，其中路由開銷是指每成功接收一個(gè)數(shù)據(jù)包，所產(chǎn)生的控制包。

圖5描繪了節(jié)點(diǎn)數(shù)對(duì)路由開銷率的影響。從圖5可知，節(jié)點(diǎn)數(shù)的增加，提高了路由開銷率。原因在于：節(jié)點(diǎn)數(shù)越多，信道競(jìng)爭(zhēng)越激烈，增加了冗余包。

圖5 路由開銷隨節(jié)點(diǎn)數(shù)的變化情況

從圖5可知，提出的LET-RP路由的路由開銷低于AODV和AODV-P。原因在于：AODV采用泛洪方式傳輸數(shù)據(jù)，而AODV-P采用固定概率傳輸控制包，它們并沒有考慮到節(jié)點(diǎn)的移動(dòng)信息和信道衰減情況，這必然加大了建立路由的控制包數(shù)量。

接下來(lái)分析三個(gè)路由協(xié)議的吞吐量隨節(jié)點(diǎn)數(shù)的變化情況，實(shí)驗(yàn)數(shù)據(jù)如圖6所示。從圖6可知，節(jié)點(diǎn)數(shù)的增加，降低了網(wǎng)絡(luò)的平均吞吐量。這主要是因?yàn)椋汗?jié)點(diǎn)數(shù)的增加，加劇了信道資源的競(jìng)爭(zhēng)，激發(fā)了網(wǎng)絡(luò)擁塞，進(jìn)而降低了網(wǎng)絡(luò)吞吐量。從圖6可知，提出的LET-RP的平均吞吐量高于AODV和AODV-P。這要?dú)w功于LET-RP路由通過選擇穩(wěn)定路由傳輸數(shù)據(jù)，提高了數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

圖6 平均吞吐量隨節(jié)點(diǎn)數(shù)的變化情況

最后，分析三個(gè)協(xié)議的平均端到端時(shí)延，其是指將數(shù)據(jù)包傳輸至目的節(jié)點(diǎn)所需的平均時(shí)間。實(shí)驗(yàn)數(shù)據(jù)如圖7所示。

圖7 端到端傳輸時(shí)延隨節(jié)點(diǎn)數(shù)的變化情況

從圖7可知，端到端傳輸時(shí)延隨節(jié)點(diǎn)數(shù)的增加而增大。原因在于：節(jié)點(diǎn)數(shù)越多，信道資源越激烈，降低了數(shù)據(jù)傳輸?shù)牧鲿承?，這必然加大了傳輸時(shí)延。同時(shí)，也增加排隊(duì)時(shí)延。與AODV和AODV-P相比，提出的LET-RP路由的時(shí)延得到有效控制。這要?dú)w功于LET-RP通過融合移動(dòng)信息和信道衰減信息，建立連通時(shí)間長(zhǎng)的路由，減少了頻繁建立路由的概率，提高了數(shù)據(jù)傳輸?shù)牧鲿承裕M(jìn)而控制了時(shí)延。

4 結(jié) 語(yǔ)

本文針對(duì)移動(dòng)Ad Hoc網(wǎng)絡(luò)的數(shù)據(jù)傳輸問題，提出基于鏈路連通時(shí)間的移動(dòng)Ad Hoc網(wǎng)絡(luò)路由LET-RP。與傳統(tǒng)的移動(dòng)Ad Hoc網(wǎng)絡(luò)路由不同，LET-RP路由只不僅考慮節(jié)點(diǎn)的移動(dòng)信息，還考慮了信道衰減信息，從而建立穩(wěn)定鏈路。實(shí)驗(yàn)數(shù)據(jù)表明，提出的LET-RP路由有效地降低。