摘要：針對(duì)編碼機(jī)會(huì)對(duì)數(shù)據(jù)流傳輸相對(duì)集中的要求，而數(shù)據(jù)流集中可能會(huì)造成傳輸干擾增大的問(wèn)題，提出一種新的考慮干擾感知的編碼意識(shí)路由判據(jù)ECXWI，結(jié)合一定的路由發(fā)現(xiàn)、路由維護(hù)機(jī)制，形成一種新的編碼意識(shí)路由算法CARWI，該算法綜合考慮了編碼機(jī)會(huì)以及無(wú)線傳輸干擾等因素。仿真證明，并與采用最短路徑路由的網(wǎng)絡(luò)編碼機(jī)會(huì)路由傳輸機(jī)制COPE相比，CARWI在網(wǎng)絡(luò)吞吐量、端到端時(shí)延指標(biāo)上有更優(yōu)的表現(xiàn)。

關(guān)鍵詞：無(wú)線Ad Hoc網(wǎng)絡(luò)；網(wǎng)絡(luò)編碼；編碼意識(shí)；干擾；

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）04-0726-05

Network Coding-aware Routing Based on the Interference-aware

TAO Yang， ZHAO Jun-nan，

（Chongqing University of Posts and Telecommunications， Chongqing 400065， China）

Abstract： For the transmission of data stream required by network coding is relatively concentrated， there may cause the increasing interferences，a new routing metric ECXWI is proposed in this paper. Combined with the route discovery and the route maintenance mechanism， a new coding-aware routing algorithm CARWI is also proposed. Simulation shows that compared with network coding opportunities routing transmission mechanism COPE based on the shortest path route， CARWI has a better performance of network average throughput， average end to end delays .

Key words： wireless ad hoc network； network coding； coding-aware； interference

無(wú)線Ad Hoc網(wǎng)絡(luò)在廣泛的應(yīng)用的同時(shí)，也暴露出無(wú)法避免的缺陷，由于網(wǎng)絡(luò)無(wú)中心、自組織等特點(diǎn)，各節(jié)點(diǎn)間需不斷交換信息以了解網(wǎng)絡(luò)狀態(tài)，從而實(shí)現(xiàn)通信功能，這就造成網(wǎng)絡(luò)開(kāi)銷(xiāo)較大、帶寬有限、承載能力有限等問(wèn)題。2000年，Rudolf Ahlswede、Ning Cai[1]等人基于網(wǎng)絡(luò)信息流的概念，提出網(wǎng)絡(luò)編碼的概念，在此概念提出之前，傳統(tǒng)的路由協(xié)議中節(jié)點(diǎn)的工作模式為存儲(chǔ)轉(zhuǎn)發(fā)，這種機(jī)制無(wú)法達(dá)到多播容量中最大流最小割定理[2-4]吞吐量的上限，而網(wǎng)絡(luò)編碼允許節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行操作和處理，并證明了在理論情況下，利用網(wǎng)絡(luò)編碼可以達(dá)到通信網(wǎng)絡(luò)的最大傳輸容量，因此網(wǎng)絡(luò)編碼得到國(guó)際學(xué)術(shù)界的廣泛關(guān)注和重視。

本文對(duì)現(xiàn)有的網(wǎng)絡(luò)編碼路由算法的現(xiàn)狀進(jìn)行深入的了解和總結(jié)，重點(diǎn)研究現(xiàn)有的編碼意識(shí)路由，對(duì)現(xiàn)有的編碼意識(shí)路由判據(jù)進(jìn)行對(duì)比，找到目前基于網(wǎng)絡(luò)編碼的路由算法在實(shí)際應(yīng)用中可能存在的主要缺陷，考慮提出一種新的編碼意識(shí)路由度量，應(yīng)用于具體的無(wú)線Ad Hoc網(wǎng)絡(luò)路由協(xié)議中，形成一種新的編碼意識(shí)路由算法。

1 相關(guān)工作

從06年開(kāi)始，國(guó)內(nèi)外學(xué)者開(kāi)始研究編碼意識(shí)路由，將編碼機(jī)會(huì)與其他路由參數(shù)相結(jié)合形成新的路由判據(jù)，最大的發(fā)揮網(wǎng)絡(luò)編碼對(duì)整體網(wǎng)絡(luò)性能的提升能力。

Ni[5]等人提出了基于網(wǎng)絡(luò)編碼的期望傳輸次數(shù)ECX作為路由判據(jù)，并應(yīng)用于具體路由協(xié)議中，形成了ROCX，文中定義了兩個(gè)節(jié)點(diǎn)通過(guò)中間節(jié)點(diǎn)經(jīng)過(guò)網(wǎng)絡(luò)編碼成功交換報(bào)文所需的傳輸次數(shù)，并將編碼感知的路由問(wèn)題轉(zhuǎn)化為一個(gè)線性優(yōu)化問(wèn)題。另外，文獻(xiàn)[6]考慮了速率不同的流直接的網(wǎng)絡(luò)編碼問(wèn)題，提出了速率匹配的編碼感知路由協(xié)議RCR，該協(xié)議講一個(gè)數(shù)據(jù)流分割成多個(gè)流便于有效地實(shí)現(xiàn)流之間的速率匹配，從而降低不同數(shù)據(jù)流的速率不同對(duì)網(wǎng)絡(luò)時(shí)延造成的負(fù)面影響，有效提升網(wǎng)絡(luò)編碼的效率。文獻(xiàn)[7]提出的PEAC方案以區(qū)域編碼增益作為路由度量，它的每次轉(zhuǎn)發(fā)

感知機(jī)會(huì)路由CORE結(jié)合了流間網(wǎng)絡(luò)編碼與機(jī)會(huì)路由。

但是06年S.S在文獻(xiàn)[5]中指出，增加編碼機(jī)會(huì)的整體都著眼于提升節(jié)點(diǎn)附近區(qū)域中的編碼增益，同時(shí)使用編碼感知的傳輸調(diào)度來(lái)保證編碼機(jī)會(huì)的出現(xiàn)。文獻(xiàn)[9]提出的編碼趨勢(shì)是需要多個(gè)數(shù)據(jù)流在發(fā)送時(shí)盡量集中，而無(wú)線網(wǎng)絡(luò)在傳輸時(shí)為避免干擾應(yīng)使數(shù)據(jù)流之間盡量的遠(yuǎn)離，如何在網(wǎng)絡(luò)編碼機(jī)會(huì)增多及干擾避免兩者進(jìn)行折中成為一個(gè)問(wèn)題。

因此本文在前人對(duì)干擾和考慮編碼的路由判據(jù)的基礎(chǔ)上，提出了路由判據(jù)ECXWI，描述如下：

[ECXWI=i，j=1Nxi，jri，j-i，j，k=1Nck，i，jri，k+ri，j-ri，kri，j?Il] （1）

其中[Il]表示鏈路[l]上的干擾率，[0

[Il（v）=SIN Rl（v）SN Rl（v）=NN+w∈η（u）-vτ（w）Pu（w）]

[Il=min（Il（u），Il（v））] （2）

其中，[N]為背景噪聲，[η（v）]表示節(jié)點(diǎn)可以偵聽(tīng)到數(shù)據(jù)包的節(jié)點(diǎn)集，[τ（w）]表示歸一化的數(shù)據(jù)速率，代表節(jié)點(diǎn)[w]在一段時(shí)間內(nèi)發(fā)包的平均速率，是節(jié)點(diǎn)[w]占用信道的時(shí)間比率，當(dāng)節(jié)點(diǎn)以全速率發(fā)包時(shí)，[τ（w）]為1。

2 基于干擾感知的網(wǎng)絡(luò)編碼意識(shí)路由CARWI

2.1 路由信息格式

CARWI協(xié)議擴(kuò)展了在AODV協(xié)議的基礎(chǔ)上更改了路由信息格式，下面對(duì)這些路由控制信息格式的更改進(jìn)行描述：

1） RREQ信息格式

其中J組播預(yù)留的加入標(biāo)識(shí)。

R是為組播預(yù)留的修復(fù)標(biāo)識(shí)。

G用于指示RREP。

D標(biāo)識(shí)只有目節(jié)點(diǎn)才能反饋該信息包。

U標(biāo)識(shí)目的節(jié)點(diǎn)序列號(hào)未知。

ECXWI代表本文的考慮干擾的編碼意識(shí)路由判據(jù)，用于路由的選擇。

2） RREP信息格式

R用于表示組播的情況。

A應(yīng)答：用于表示中間節(jié)點(diǎn)有到達(dá)目的節(jié)點(diǎn)路徑，或者目的節(jié)點(diǎn)本身受到路由請(qǐng)求信息時(shí)，返回的一個(gè)值。

LIFE TIME表示一定時(shí)間后，如果反向路由項(xiàng)沒(méi)有使用，則對(duì)應(yīng)的路由項(xiàng)變?yōu)闊o(wú)效。

其他項(xiàng)與RREP一致。

2.2 路由發(fā)現(xiàn)與路由維護(hù)

2.2.1 路由發(fā)現(xiàn)

當(dāng)源節(jié)點(diǎn)需向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，首先檢查路由表中沒(méi)有所需的路徑時(shí)，源節(jié)點(diǎn)觸動(dòng)路由發(fā)現(xiàn)過(guò)程：

步驟1 源節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播路由請(qǐng)求信息包RREQ，并在廣播RREQ前，源節(jié)點(diǎn)對(duì)以下域進(jìn)行初始化：

1）源節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)及其相應(yīng)參數(shù)，包括數(shù)據(jù)包投遞率、歸一化數(shù)據(jù)速率、鏈路干擾率等，用于目的節(jié)點(diǎn)計(jì)算路徑代價(jià)。

2）路徑記錄，RREQ所經(jīng)過(guò)的節(jié)點(diǎn)記錄中初始化為僅有源節(jié)點(diǎn)。

3）已存在流的路徑記錄，保存該節(jié)點(diǎn)處已存在流的路徑記錄。

4）已存在流的一跳節(jié)點(diǎn)，保存該節(jié)點(diǎn)處已存在流的一跳（偵聽(tīng)）節(jié)點(diǎn)。

步驟2 中間節(jié)點(diǎn)接收到一個(gè)RREQ后，首先檢查其自身是否已包含在RREQ的路徑記錄中，若已包含在內(nèi)，則丟棄該RREQ以防止環(huán)路；若未包含在內(nèi)，節(jié)點(diǎn)對(duì)路由請(qǐng)求信息包其做如下處理：

1）更新一跳節(jié)點(diǎn)列表，將本節(jié)點(diǎn)的一跳節(jié)點(diǎn)及其相應(yīng)的參數(shù)添加到列表。

2）更新路徑記錄，將本節(jié)點(diǎn)添加至節(jié)點(diǎn)記錄中。

3）更新已存在流的路徑記錄，將本節(jié)點(diǎn)已存在流的路徑添加至記錄中。

4）更新已存在流的一跳節(jié)點(diǎn)列表，將本節(jié)點(diǎn)已存在流的偵聽(tīng)節(jié)點(diǎn)添加至記錄中。

5）廣播更新后的路由請(qǐng)求信息包RREQ。

步驟3 目的節(jié)點(diǎn)接收到RREQ后，目的節(jié)點(diǎn)根據(jù)本文公式（1）定義的考慮干擾的編碼意識(shí)路由判據(jù)計(jì)算路徑代價(jià)。這種判據(jù)首先考慮了每條路徑中由于網(wǎng)絡(luò)編碼機(jī)會(huì)的存在而帶來(lái)的增益，然后利用干擾率對(duì)這種增益進(jìn)行加權(quán)，最后在這兩種因素的基礎(chǔ)上，計(jì)算出同時(shí)考慮網(wǎng)絡(luò)編碼和干擾的期望傳輸次數(shù)，通過(guò)對(duì)每條路徑期望傳輸次數(shù)的比較，從而做出路由選擇。同時(shí)，在路由請(qǐng)求緩存表中，針對(duì)每個(gè)源節(jié)點(diǎn)設(shè)置關(guān)于RREQ的重復(fù)計(jì)數(shù)器和定時(shí)器，若在規(guī)定時(shí)間內(nèi)收到多個(gè)來(lái)自同一源節(jié)點(diǎn)的RREQ，并且數(shù)量超過(guò)重復(fù)計(jì)數(shù)器的設(shè)定值，則選擇路徑度量值最小的路徑，回復(fù)路由應(yīng)答信息包RREP。定時(shí)器中設(shè)定時(shí)間到后，目的節(jié)點(diǎn)從當(dāng)前收到的RREQ中選擇路徑度量值最小的路徑，回復(fù)路由應(yīng)答信息包RREP。

當(dāng)目的節(jié)點(diǎn)選定路徑后，更新域，然后沿反向路徑將RREQ包送回源節(jié)點(diǎn)。

步驟4 中間節(jié)點(diǎn)接收到RREP后，進(jìn)行以下操作：

1）存儲(chǔ)RREP中當(dāng)前流的路徑及一跳鄰居節(jié)點(diǎn)信息。

2）存儲(chǔ)對(duì)應(yīng)于本節(jié)點(diǎn)的編碼記錄，以便數(shù)據(jù)包發(fā)送時(shí)進(jìn)行編碼操作。

步驟5 源節(jié)點(diǎn)收到RREP后，根據(jù)選定的路徑開(kāi)始發(fā)送數(shù)據(jù)包。

2.2.2 路由維護(hù)

本協(xié)議的路由維護(hù)機(jī)制與AODV類(lèi)似，每個(gè)節(jié)點(diǎn)定期廣播hello包，當(dāng)一個(gè)節(jié)點(diǎn)收到其一跳節(jié)點(diǎn)hello消息時(shí)，該節(jié)點(diǎn)創(chuàng)建或更新至此鄰居節(jié)點(diǎn)的路徑；當(dāng)節(jié)點(diǎn)檢測(cè)到路徑斷裂時(shí)，將本身路由表中包含該路徑的路由刪除，并發(fā)送RRER通知該路徑上的其他節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)收到RRER包后也將刪除本身路由表中相應(yīng)的路徑信息。

3 評(píng)估

3.1 仿真環(huán)境

本文采用NS-2仿真環(huán)境，設(shè)計(jì)以下兩種兩種場(chǎng)景對(duì)CARWI進(jìn)行仿真：1、不同數(shù)據(jù)發(fā)送速率2、不同數(shù)據(jù)量的數(shù)目下，該文三種協(xié)議進(jìn)行比較。設(shè)定64個(gè)節(jié)點(diǎn)隨機(jī)分布在1200m*1200m的區(qū)域內(nèi)，所有數(shù)據(jù)流為CBR數(shù)據(jù)流，包長(zhǎng)度為512B。仿真時(shí)間為600s，仿真結(jié)果為10次仿真的平均值。

3.2 仿真結(jié)果分析

場(chǎng)景一：不同數(shù)據(jù)流發(fā)送速率下路由算法的表現(xiàn)

10條數(shù)據(jù)流每間隔5s隨機(jī)產(chǎn)生，數(shù)據(jù)發(fā)送速率變化范圍為5kbps～120kbps。

如圖4中可知，當(dāng)數(shù)據(jù)發(fā)送速率較低時(shí)，例如35kbps以下，三種算法平均吞吐量比較接近，原因是網(wǎng)絡(luò)中編碼機(jī)會(huì)較少，基于網(wǎng)絡(luò)編碼的兩種算法對(duì)網(wǎng)絡(luò)性能的改善表現(xiàn)的并不明顯。但隨著數(shù)據(jù)發(fā)送速率的增加，編碼機(jī)會(huì)也相應(yīng)的增加，使用AODV算法的網(wǎng)絡(luò)平均吞吐量在數(shù)據(jù)發(fā)送速率達(dá)到40kbps時(shí)達(dá)到最大值，隨后起伏不大。這是由于網(wǎng)絡(luò)負(fù)載增加到一定程度時(shí)，造成數(shù)據(jù)包丟失率的增加，限制了平均吞吐量的增加上限。但AODV+COPE方案相對(duì)于AODV有一定優(yōu)勢(shì)，吞吐量的最大值有一定的增加，并且在數(shù)據(jù)發(fā)送速率為50kbps時(shí)才達(dá)到上限，這是由于網(wǎng)絡(luò)編碼一定程度上緩解了網(wǎng)絡(luò)擁塞，帶來(lái)了網(wǎng)絡(luò)性能改善。但由于被動(dòng)編碼的特點(diǎn)，編碼機(jī)會(huì)有限，因此這種改善并不明顯。而CARWI相對(duì)于其他兩種方案有較優(yōu)異表現(xiàn)，平均吞吐量增幅較大。

由圖5中可看出，隨著數(shù)據(jù)流發(fā)送速率的增加，三種路由方案的平均端到端時(shí)延都呈上升趨勢(shì)，這是由于數(shù)據(jù)流發(fā)送速率的增加會(huì)使網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)不斷增加，導(dǎo)致了數(shù)據(jù)包不同程度的擁塞，引起丟包，從而時(shí)延增大。而在數(shù)據(jù)發(fā)送速率較?。ㄐ∨c20kbps）時(shí)，三種路由方案的平均端到端時(shí)延差別不大，當(dāng)數(shù)據(jù)發(fā)送速率變大，網(wǎng)絡(luò)中傳輸數(shù)據(jù)量增大，基于網(wǎng)絡(luò)編碼的路由方案的時(shí)延方面的優(yōu)勢(shì)展現(xiàn)出來(lái)。另外，CARWI較之其他兩種方案在延時(shí)增加較少，表現(xiàn)最為優(yōu)異。

場(chǎng)景二：不同數(shù)據(jù)流數(shù)目下路由算法的表現(xiàn)

數(shù)據(jù)流發(fā)送速率固定為50kbps，數(shù)據(jù)流個(gè)數(shù)變化范圍為5～20，分別選取5，7，9，10，13，15，17，19個(gè)數(shù)據(jù)流對(duì)三種方案進(jìn)行仿真。

由圖6中可看出，當(dāng)數(shù)據(jù)流的數(shù)量較?。?個(gè)左右）時(shí)，三種路由方案的平均端到端吞吐量比較接近，隨著數(shù)據(jù)流個(gè)數(shù)的增加，三種路由方案都呈上升趨勢(shì)，但AODV方案在數(shù)據(jù)流增加至9個(gè)時(shí)吞吐量達(dá)到峰值，隨后由于數(shù)據(jù)流數(shù)據(jù)的繼續(xù)增加導(dǎo)致網(wǎng)絡(luò)擁塞和信道競(jìng)爭(zhēng)，吞吐量呈遞減趨勢(shì)。而AODV+COPE在數(shù)據(jù)流個(gè)數(shù)為10的時(shí)候吞吐量才達(dá)到峰值，CARWI在數(shù)據(jù)流個(gè)數(shù)為11時(shí)才達(dá)到峰值?；诰W(wǎng)絡(luò)編碼的路由方案的平均端到端吞吐量一直優(yōu)于傳統(tǒng)路由方案，CARWI方案的性能表現(xiàn)相對(duì)于被動(dòng)編碼的COPE來(lái)說(shuō)更優(yōu)。

由圖7可看出，三種路由方案的平均端到端延時(shí)隨著數(shù)據(jù)流個(gè)數(shù)的增加都呈上升趨勢(shì)。但基于網(wǎng)絡(luò)編碼的路由方案CARWI和COPE+AODV的平均端到端延時(shí)一直小于傳統(tǒng)路由方案，其中網(wǎng)絡(luò)編碼的路由方案比較中，的時(shí)延一直低于COPE，證明本文的考慮干擾的編碼意識(shí)在此指標(biāo)的仿真中表現(xiàn)最優(yōu)。

由兩個(gè)仿真場(chǎng)景中兩個(gè)性能指標(biāo)的仿真圖可看出，CARWI性能最優(yōu)

4 結(jié)論

無(wú)線Ad Hoc網(wǎng)絡(luò)由于其廣闊的發(fā)展前景得到了大量研究和應(yīng)用，但如何在隨時(shí)變化的網(wǎng)絡(luò)拓?fù)渲型瓿筛鞣N高要求的應(yīng)用一直是核心問(wèn)題。該文利用網(wǎng)絡(luò)編碼技術(shù)，應(yīng)用于路由協(xié)議中和重傳策略中，希望提高網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)可靠性。該文在編碼意識(shí)路由的基礎(chǔ)上考慮干擾因素的影響，提出了新的編碼意識(shí)路由判據(jù)ECXWI，在此基礎(chǔ)上提出了相應(yīng)的路由協(xié)議CARWI，仿真結(jié)果證明，與AODV及AODV+COPE相比，CARWI能夠有效提升網(wǎng)絡(luò)吞吐量，減少端到端時(shí)延。

參考文獻(xiàn)：

[1] Ahlswede R， Cai Ning. Network information flow[J].IEEE Transactions on Information Theory， 2000， 46（4）：1204-1216.

[2] Ramanathan hgSNAGnKQE38fBmwibKJSg==S.Multicast tree generation in networks with asymmetric links[J].IEEE/ACM Transactions on Networking， 1996， 4（4）：558-568.

[3] Moses Charikar， Chandra Chekuri， To-yat Cheung， et al. Approximation algorithms for directed Steiner problems[C]. Ninth Annual ACM-SIAM Symposium on Discrete Algorithms （SO-DA 1998）， 1998：192-200.

[4] Leonid Zosin， Samir Khuller. On directed Steiner trees[C]. 13th Annual ACM-SIAM Symposium on Discrete Algorithms， 2002：59-63.

[5] Wu Y， Das S M，Chandra R.Routing with a Markovian metric to promote local mixing[C]//Proc.of 26th IEEE International Conference on Computer Communications， Anchorage， AK， USA： IEEE press，2007：2381～2385.

[6] Ni B， Santhapuri N， Zhong Z， et al. Routing with Opportunistically Coded Exchanges in Wireless Mesh Networks[C]//Proc of SECON’06.Reston，VA：IEEE Press，2006：157～159.

[7] Yan Y， Zhao Z， Zhang B，et al. Rate-adaptive coding-aware multiple path routing for wireless mesh networks[C]//In Proc. of IEEE Global Telecommunications Conference， New Orleans， LA，USA：IEEE press，2008：543～547.

[8] Yan Y， Zhao z， Zhang B， et al. Mechanism for maximizing area-centric coding gains in wireless multi-hop networks[C]// Proc ICC 2009， Dresden， Germany. Jun.2009.

[9] Yan Y， Zhang B X， Hussein M， Ma J， CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J].IEEE Wireless Communications， 2010， 17（3）： 96-103.