孫建飛，高 媛，王淑敏

(中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院,太原 030051)

0 引言

機(jī)會(huì)網(wǎng)絡(luò)是不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑，利用節(jié)點(diǎn)移動(dòng)帶來的機(jī)會(huì)相遇實(shí)現(xiàn)網(wǎng)絡(luò)通信、時(shí)延和分裂可容忍的自組織網(wǎng)絡(luò)。網(wǎng)絡(luò)編碼是2000年由Ahlswed等提出，2005年之后許多國外學(xué)者開始研究無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼。COPE[1]利用機(jī)會(huì)偵聽和接收?qǐng)?bào)告的方式最大化一次傳輸?shù)臄?shù)據(jù)包數(shù)量，但被動(dòng)的編碼機(jī)制限制了網(wǎng)絡(luò)編碼提升網(wǎng)絡(luò)吞吐量的能力；CORE[2]中提出了轉(zhuǎn)發(fā)集的概念，每個(gè)節(jié)點(diǎn)單獨(dú)計(jì)算數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)先級(jí)，可同時(shí)得到網(wǎng)絡(luò)編碼和機(jī)會(huì)路由對(duì)無線網(wǎng)絡(luò)所帶來的增益；MORE[3]采用隨機(jī)線性編碼的方式提高投遞率，但提升網(wǎng)絡(luò)吞吐量能力有限，網(wǎng)絡(luò)延時(shí)大；PACE[4]中節(jié)點(diǎn)每次都著眼于提升節(jié)點(diǎn)附近區(qū)域中的編碼增益，并增加了轉(zhuǎn)發(fā)延時(shí)有效的控制了碰撞的發(fā)生。王少園[5]等提出COPE改進(jìn)算法，以鏈路質(zhì)量度量作為備選轉(zhuǎn)發(fā)節(jié)點(diǎn)集的選擇標(biāo)準(zhǔn)，在一定程度上提高了整體網(wǎng)絡(luò)的吞吐量，降低了數(shù)據(jù)端到端的時(shí)延。基于上述分析提出了ANCBCR算法。

1 ANCBCR算法

下面是算法的描述。

1.1 主動(dòng)異或編碼

與COPE不同，節(jié)點(diǎn)Vi每次轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)不是立即計(jì)算將符合條件的數(shù)據(jù)編碼后轉(zhuǎn)發(fā)給相應(yīng)的鄰居節(jié)點(diǎn)，而是通過等待一個(gè)時(shí)間段T，若在T內(nèi)偵聽到了新的鄰居節(jié)點(diǎn)，并將此節(jié)點(diǎn)加入本次計(jì)算，知道時(shí)間T到達(dá)將滿足條件數(shù)據(jù)包編碼轉(zhuǎn)發(fā)。編碼包計(jì)算方式如下：

（1）節(jié)點(diǎn)Vi要轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，通過偵聽到的鄰居信息計(jì)算出鄰居Vj的請(qǐng)求矢量Requestji，如式（1）：

假設(shè)Vi的緩存中儲(chǔ)存有n個(gè)數(shù)據(jù)包，且Vi的鄰居個(gè)數(shù)為m個(gè)，則可以得到一個(gè)m行n列請(qǐng)求矢量組成的矩陣M（如式（2）其中列為節(jié)點(diǎn)Vi中數(shù)據(jù)包的ID，行為Vi的鄰居節(jié)點(diǎn)ID）。

（2）計(jì)算符合編碼條件的數(shù)據(jù)包。

將B中值不為0的個(gè)數(shù)記為b，C中值不為0的個(gè)數(shù)記為c，分三種情況：

所以最大編碼包數(shù)為b-max(B)。

接著將B中值大于1的位置對(duì)應(yīng)的列的值全部置為0，重新計(jì)算B、C，利用B、C得到滿足編碼條件的數(shù)據(jù)包進(jìn)行異或編碼后多播給相應(yīng)的鄰居節(jié)點(diǎn)。

1.2 數(shù)據(jù)包發(fā)送順序優(yōu)化

在時(shí)間T到達(dá)之后，轉(zhuǎn)發(fā)節(jié)點(diǎn)Vi首先查找自己緩存中是否存在目的節(jié)點(diǎn)為鄰居的數(shù)據(jù)包，若存在則優(yōu)先轉(zhuǎn)發(fā)；接著將多個(gè)節(jié)點(diǎn)要求轉(zhuǎn)發(fā)的數(shù)據(jù)包多播給相應(yīng)節(jié)點(diǎn)；最后，計(jì)算得到滿足條件的數(shù)據(jù)包編碼后多播給相應(yīng)節(jié)點(diǎn)。至此，一次完整轉(zhuǎn)發(fā)結(jié)束。

1.3 節(jié)點(diǎn)數(shù)據(jù)緩存管理

節(jié)點(diǎn)Vi收到鄰居Vj發(fā)來的SVj后計(jì)算出Vi和鄰居Vj都存在的數(shù)據(jù)分組Commonji，計(jì)算方法如式（6）：

接下來節(jié)點(diǎn)Vi遍歷Commonji，查找目的節(jié)點(diǎn)為Vj的數(shù)據(jù)分組，存在則從本地緩存中將其刪除，并將其寫入已到達(dá)目的節(jié)點(diǎn)數(shù)據(jù)索引中，達(dá)到清理緩存和減少網(wǎng)絡(luò)開銷的目的。

1.4 閾值T的確定

T為延遲編碼計(jì)算的最長時(shí)間，如式（7）：

其中Ti(i=1,2,....m)為Vi的m個(gè)鄰居與Vi處于通信范圍內(nèi)的時(shí)間，如式（8）：

其中R為通信半徑，d為節(jié)點(diǎn)間距，V為節(jié)點(diǎn)速度，m鄰居個(gè)數(shù)，t為發(fā)送單個(gè)數(shù)據(jù)包所用的時(shí)間，如式（9）：

其中M為數(shù)據(jù)包大小，V0為數(shù)據(jù)傳輸速率，t0為傳輸數(shù)據(jù)包Head字段所需的時(shí)間。

2 仿真與分析

2.1 實(shí)驗(yàn)平臺(tái)搭建與參數(shù)設(shè)置

本文采用ONE(Opportunistic Network Environment)仿真軟件平臺(tái)，采用(Shortest Path Map Based Movement)為移動(dòng)模型。

2.2 仿真結(jié)果分析

為了驗(yàn)證本文算法的性能，通過數(shù)據(jù)分組端到端平均時(shí)延和網(wǎng)絡(luò)吞吐量這些指標(biāo)與COPE算法和COPE改進(jìn)算法進(jìn)行比較，通過實(shí)驗(yàn)數(shù)據(jù)對(duì)網(wǎng)絡(luò)性能進(jìn)行分析。

圖1 端到端數(shù)據(jù)傳輸時(shí)延

（1）端到端數(shù)據(jù)傳輸時(shí)延。由圖1可知，隨著網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)的增加，3種算法的時(shí)延均呈現(xiàn)下降趨勢(shì)，這是因?yàn)榫W(wǎng)絡(luò)中數(shù)據(jù)流的增加使網(wǎng)絡(luò)中的數(shù)據(jù)包有了更多的轉(zhuǎn)發(fā)機(jī)會(huì)。尤其，本算法較另外兩種算法的時(shí)延有明顯下降，平均下降1200s，這是因?yàn)閿?shù)據(jù)包發(fā)送順序優(yōu)化機(jī)制有益于增加數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)會(huì)。另外，COPE和COPE的改進(jìn)算法分別在數(shù)據(jù)流個(gè)數(shù)為70和60的時(shí)候端到端時(shí)延有上升趨勢(shì)，而本算法卻保持在了接近2500s的穩(wěn)定狀態(tài)，這是因?yàn)楸舅惴ㄒ肓司彺媲謇頇C(jī)制克服了因緩存資源不足而造成丟包進(jìn)而引發(fā)數(shù)據(jù)分組延遲接收的問題。

圖2 網(wǎng)絡(luò)吞吐量

（2）網(wǎng)絡(luò)吞吐量。網(wǎng)絡(luò)吞吐量是指單位時(shí)間內(nèi)流經(jīng)整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)量。從圖2可以看出，在發(fā)送數(shù)據(jù)流小于60kb/s時(shí)，三種算法的網(wǎng)絡(luò)吞吐量均有所提升，兩種改進(jìn)算法均大于COPE算法，這是因?yàn)镃OPE改進(jìn)算法增加了新的判斷機(jī)制，而本算法引入了主動(dòng)編碼機(jī)制并又花了數(shù)據(jù)的轉(zhuǎn)發(fā)順序，增加了轉(zhuǎn)發(fā)機(jī)會(huì)。在發(fā)送數(shù)據(jù)流大于60kb/s后，由于網(wǎng)絡(luò)擁塞，三種算法的吞吐量均有下降趨勢(shì)，但由于本算法引入了SV緩存清理機(jī)制，所以吞吐量下降趨勢(shì)較另外兩種算法明顯平緩的多，并且在發(fā)送數(shù)據(jù)流為200kb/s時(shí)仍能保持在25kb/s以上。

3 結(jié)束語

本文提出的基于主動(dòng)編碼的機(jī)會(huì)路由算法引入了主動(dòng)異或編碼和多播，充分利用節(jié)點(diǎn)的每次相遇機(jī)會(huì)，提高了整體網(wǎng)絡(luò)吞吐量和數(shù)據(jù)分組平均端到端時(shí)延，同時(shí)增加了緩存清理機(jī)制進(jìn)一步提升了該算法的性能。接下來的工作將致力通過機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)間相互協(xié)作，合理的調(diào)度數(shù)據(jù)的傳輸順序來提升區(qū)域網(wǎng)絡(luò)吞吐量的問題。

[1]KATTI S, RAHUL H, HU W, et al. XORs in the air: Practical wireless network coding [C]. Protocols for Computer Communications , 2006:243-254.

[2]YAN Y, ZHANG B, MOUFLAH H T, et al.Practical codingaware mechanism for oppor- tunistic routing in wireless mesh networks[C]. Proceedings of IEEE International Conference on Communications, 2008: 2871-2876

[3]CHACHULSKI S, JENNINGS M, KATTI S, etal. Trading structure for randomness in wireless opportunistic routing[C].Proceedings of Conference on Applications,2007: 169-180

[4]YAN Y, ZHAO Z, ZHANG B, et al. Mechanism for maximizing area-centric coding gains in wireless multihop networks[C].Proceedings of IEEE International Conference on Commun-ications, 2009, 14-18

[5]王少園，吳蒙.基于COPE協(xié)議改進(jìn)的網(wǎng)絡(luò)編碼感知機(jī)會(huì)路由算法[J].電信快報(bào),2013:41-44.