白琳　何欣　何明書

摘 要： 網(wǎng)絡(luò)編碼允許通信節(jié)點(diǎn)對(duì)接收到的消息進(jìn)行編碼處理，能夠在一定程度上提高網(wǎng)絡(luò)吞吐量，增強(qiáng)通信安全性。機(jī)會(huì)網(wǎng)絡(luò)基于移動(dòng)節(jié)點(diǎn)，面向動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)組織、實(shí)現(xiàn)通信的特點(diǎn)，使其成為現(xiàn)代網(wǎng)絡(luò)通信的發(fā)展趨勢(shì)。但是機(jī)會(huì)網(wǎng)絡(luò)投遞率與消息副本數(shù)間的矛盾，嚴(yán)重制約著機(jī)會(huì)網(wǎng)絡(luò)通信技術(shù)的推進(jìn)。將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用到機(jī)會(huì)網(wǎng)絡(luò)路由設(shè)計(jì)中，可以降低機(jī)會(huì)網(wǎng)絡(luò)通信的消息副本數(shù)，提高投遞率。詳細(xì)描述了隨機(jī)線性編碼等幾種網(wǎng)絡(luò)編碼在機(jī)會(huì)網(wǎng)絡(luò)路由設(shè)計(jì)中的典型應(yīng)用，并提出了網(wǎng)絡(luò)編碼在機(jī)會(huì)網(wǎng)絡(luò)中的發(fā)展展望。

關(guān)鍵詞： 網(wǎng)絡(luò)編碼； 機(jī)會(huì)網(wǎng)絡(luò)； 隨機(jī)線性編碼； 投遞率

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）11-25-04

The survey of opportunistic network routing based on network coding

Bai Lin1， He Xin1，2， He Mingshu1

（1. School of Computer and Information Engineering， Henan University， Henan， Kaifeng 475001， China； 2. School of Software， Henan University）

Abstract： Network coding allows the communication nodes to encode the received messages， which can improve the network throughput and enhance the communication security. The opportunistic network is based on the mobile node， and organization and implementation of communication based on dynamic topology， which make it the development trend of the modern network communication. However， the contradiction between the delivery rate and the number of message copies seriously restricts the advance of the opportunistic network communication technology. The application of network coding technology in the routing design of opportunistic network can reduce the number of message copies and improve the delivery rate. This paper describes the typical application of network coding， such as random linear coding and so on， in the routing design of opportunistic network， and puts forward the development prospect of network coding in the opportunistic network.

Key words： network coding； opportunistic network； random linear coding； delivery rate

0 引言

網(wǎng)絡(luò)編碼概念起源于R.Ahlswede等人于 2000年發(fā)表在IEEE trans-IT上的一篇題為“網(wǎng)絡(luò)信息流”的文章。網(wǎng)絡(luò)編碼[1]是指對(duì)于在網(wǎng)絡(luò)中傳播的消息，數(shù)據(jù)傳輸節(jié)點(diǎn)對(duì)其不再僅僅執(zhí)行存儲(chǔ)轉(zhuǎn)發(fā)，而是可以對(duì)接收到的消息進(jìn)行編碼與譯碼的處理，使得單次傳輸?shù)男畔⒘吭龃?，可以提高整個(gè)網(wǎng)絡(luò)的性能，進(jìn)而提高數(shù)據(jù)傳輸效率。

根據(jù)節(jié)點(diǎn)對(duì)消息執(zhí)行不同的操作處理，網(wǎng)絡(luò)編碼可分為兩種：①網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)消息的處理，有線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼；②網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)消息編碼系數(shù)的處理，有隨機(jī)性網(wǎng)絡(luò)編碼和確定性網(wǎng)絡(luò)編碼。網(wǎng)絡(luò)編碼采用“存儲(chǔ)-編譯碼-轉(zhuǎn)發(fā)”的方式進(jìn)行數(shù)據(jù)的傳輸，在機(jī)會(huì)網(wǎng)絡(luò)[2]中，通信節(jié)點(diǎn)的存儲(chǔ)、攜帶、轉(zhuǎn)發(fā)消息為網(wǎng)絡(luò)編碼的實(shí)現(xiàn)提供了極大的便利條件，因此在共享輸出鏈路的網(wǎng)絡(luò)環(huán)境下，結(jié)合適當(dāng)?shù)木W(wǎng)絡(luò)編碼方案對(duì)機(jī)會(huì)網(wǎng)絡(luò)吞吐量的提升、網(wǎng)絡(luò)性能的優(yōu)化、傳輸效率的提高等，都提供了良好的基礎(chǔ)。本文介紹幾種結(jié)合網(wǎng)絡(luò)編碼的路由算法在機(jī)會(huì)網(wǎng)絡(luò)中的應(yīng)用。

1 主動(dòng)異或創(chuàng)建編碼機(jī)制

機(jī)會(huì)網(wǎng)絡(luò)路由傳輸算法中的Epidemic路由機(jī)制在節(jié)點(diǎn)相遇的過(guò)程中操作如圖1所示，網(wǎng)絡(luò)中節(jié)點(diǎn)A、B、C相遇后互相交互維護(hù)概要向量，然后再發(fā)送Request請(qǐng)求，最后進(jìn)行數(shù)據(jù)傳輸?；贓pidemic路由傳輸?shù)幕舅枷胧菑?fù)制轉(zhuǎn)發(fā)，通過(guò)這種傳輸策略會(huì)使網(wǎng)絡(luò)中存在大量消息副本，雖然可以提高消息到達(dá)目標(biāo)節(jié)點(diǎn)的概率，但是這種操作會(huì)增大網(wǎng)絡(luò)負(fù)擔(dān)消耗網(wǎng)絡(luò)資源。在基于網(wǎng)絡(luò)編碼的Epidemic[3]機(jī)制中，為了節(jié)省數(shù)據(jù)傳輸過(guò)程中節(jié)點(diǎn)間的Request請(qǐng)求在節(jié)點(diǎn)B處主動(dòng)設(shè)置異或創(chuàng)建編碼操作。網(wǎng)絡(luò)中的三個(gè)節(jié)點(diǎn)處于同一個(gè)連通域內(nèi)時(shí)如下圖2所示，當(dāng)節(jié)點(diǎn)B收到一個(gè)節(jié)點(diǎn)的SV后并不立馬發(fā)送節(jié)點(diǎn)所需數(shù)據(jù)，而是在設(shè)定的一個(gè)周期T內(nèi)對(duì)相繼到達(dá)的A、C節(jié)點(diǎn)進(jìn)行統(tǒng)一處理。首先發(fā)送統(tǒng)一處理后得到的數(shù)據(jù)分組集合MA、MC，對(duì)A、C都需要的數(shù)據(jù)進(jìn)行多播處理，將A和C中剩余分組逐一提取并進(jìn)行異或編碼，然后將編碼分組多播給A和C，如果數(shù)據(jù)分組集合MA和MC中還有一個(gè)集合存在剩余分組則將這些分組單播給該集合對(duì)應(yīng)的節(jié)點(diǎn)。通過(guò)引入主動(dòng)異或網(wǎng)絡(luò)編碼和多播可有效減少路由開(kāi)銷和傳輸時(shí)延，通過(guò)取消Request控制分組的發(fā)送進(jìn)一步提高了傳統(tǒng)的Epidemic路由投遞率。

2 隨機(jī)線性網(wǎng)絡(luò)編碼機(jī)制

結(jié)合引言的介紹，再針對(duì)當(dāng)前隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)的應(yīng)用，本節(jié)主要介紹以下幾種編碼機(jī)制：RLC（Random linear coding）-Epidemic 機(jī)制、HubCode 機(jī)制、DSNC 機(jī)制。

2.1 RLC（Random linear coding）-Epidemic機(jī)制

RLC-Epidemic機(jī)制[4-5]是一種基于隨機(jī)線性網(wǎng)絡(luò)編碼的數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制[6]。該算法能夠提高機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃?，其原理為：網(wǎng)絡(luò)中的傳輸節(jié)點(diǎn)用其副本消息按照相應(yīng)規(guī)則進(jìn)行編碼處理，產(chǎn)生一組新的編碼數(shù)據(jù)包，接著再次按照同樣的數(shù)據(jù)轉(zhuǎn)發(fā)方式轉(zhuǎn)發(fā)出去。具體操作為：當(dāng)節(jié)點(diǎn)a和節(jié)點(diǎn)b在某一時(shí)刻相遇，節(jié)點(diǎn)a向節(jié)點(diǎn)b傳輸數(shù)據(jù)，在其相互發(fā)送自身攜帶的概要向量中，b收到a發(fā)來(lái)的編碼系數(shù)矩陣，與自身緩存中的編碼系數(shù)矩陣進(jìn)行比較，判定是否線性相關(guān)。若相關(guān)，則終止此次通信。若不相關(guān)，則接收節(jié)點(diǎn)a發(fā)送的編碼后數(shù)據(jù)，并將接收到的編碼后數(shù)據(jù)與自身存儲(chǔ)的數(shù)據(jù)副本重新按照已定的編碼規(guī)則進(jìn)行編碼，形成新的編碼矩陣并存儲(chǔ)。采用這種機(jī)制進(jìn)行編碼傳輸，網(wǎng)絡(luò)中會(huì)存在大量的編碼節(jié)點(diǎn)一定程度上會(huì)耗費(fèi)網(wǎng)絡(luò)資源。

2.2 HubCode機(jī)制

S. Ahmed針對(duì)現(xiàn)有的路由算法在全網(wǎng)泛洪傳輸編碼包中所帶來(lái)的網(wǎng)絡(luò)開(kāi)銷大等問(wèn)題，在2011年提出了Hubcode算法[7]。該算法是在網(wǎng)絡(luò)中選取有限個(gè)數(shù)節(jié)點(diǎn)作為編碼節(jié)點(diǎn)，其核心思想為：利用網(wǎng)絡(luò)中編碼節(jié)點(diǎn)作為網(wǎng)絡(luò)數(shù)據(jù)的傳輸橋梁，使數(shù)據(jù)的轉(zhuǎn)發(fā)具有針對(duì)性，減少節(jié)點(diǎn)的平均轉(zhuǎn)發(fā)次數(shù)，降低了網(wǎng)絡(luò)開(kāi)銷。算法主要傳輸步驟為：①源節(jié)點(diǎn)發(fā)送數(shù)據(jù)到hub節(jié)點(diǎn)（即hub節(jié)點(diǎn)就是編碼節(jié)點(diǎn)，下文用hub表示）；②hub節(jié)點(diǎn)將發(fā)往同一目的節(jié)點(diǎn)的數(shù)據(jù)編碼，并在所有的hub節(jié)點(diǎn)中泛洪編碼后數(shù)據(jù)，直到遇到目的節(jié)點(diǎn)，完成編碼后數(shù)據(jù)的投遞；③目的節(jié)點(diǎn)在收到足夠多的編碼數(shù)據(jù)后恢復(fù)原始數(shù)據(jù)。

Hubcode編碼機(jī)制的主要操作流程如圖3所示，編碼節(jié)點(diǎn)A編碼系數(shù)矩陣中包含有已編碼包F1和接收到新的原始數(shù)據(jù)X3，到達(dá)同一目標(biāo)節(jié)點(diǎn)的編碼節(jié)點(diǎn)A遇到網(wǎng)絡(luò)中的編碼節(jié)點(diǎn)B，B中的編碼系數(shù)矩陣CV={idX1：α3α1，idX2：α3α2，idX3：α4}兩編碼節(jié)點(diǎn)相遇后交互編碼系數(shù)矩陣，線性無(wú)關(guān)時(shí)傳輸給對(duì)方編碼包完成相遇操作繼續(xù)執(zhí)行下一步操作直到遇到目的節(jié)點(diǎn)。

現(xiàn)有的Hubcode編碼還有另外一種編碼傳輸方式這個(gè)編碼傳輸方式不同之處在于：①hub可以進(jìn)行解碼或存儲(chǔ)得到的編碼后數(shù)據(jù)，即hub可以獲得本地?cái)?shù)據(jù)；②其比較的不再是編碼后系數(shù)矩陣，而是本地?cái)?shù)據(jù)列表；③hub遇到目的節(jié)點(diǎn)時(shí)，可以轉(zhuǎn)發(fā)編碼后數(shù)據(jù)，也可以轉(zhuǎn)發(fā)已解碼的一條或多條本地?cái)?shù)據(jù)。

針對(duì)Hubcode編碼機(jī)制中編碼節(jié)點(diǎn)相遇時(shí)廣播編碼系數(shù)矩陣進(jìn)行交互造成資源浪費(fèi)以及目標(biāo)節(jié)點(diǎn)解碼時(shí)可能存在較大延遲，現(xiàn)有文章[8]提出HLDA編碼機(jī)制，該機(jī)制在編碼節(jié)點(diǎn)處設(shè)置一個(gè)存放源數(shù)據(jù)包的集合I和由目的節(jié)點(diǎn)反饋過(guò)來(lái)的解碼集合D，編碼節(jié)點(diǎn)相遇后首先根據(jù)集合I來(lái)判斷是否進(jìn)行交互省去了廣播編碼系數(shù)矩陣的資源消耗。解碼時(shí)，編碼節(jié)點(diǎn)收到后集合D，對(duì)比自身的編碼系數(shù)矩陣優(yōu)先發(fā)送給目標(biāo)節(jié)點(diǎn)缺少的數(shù)據(jù)包，方便目標(biāo)節(jié)點(diǎn)及時(shí)進(jìn)行解碼處理。由此可減少數(shù)據(jù)傳輸延遲。

2.3 DSNC機(jī)制

現(xiàn)有基于網(wǎng)絡(luò)編碼的機(jī)會(huì)網(wǎng)絡(luò)，數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制難以不斷編碼類似流水線形式接收的數(shù)據(jù)，并且數(shù)據(jù)量大會(huì)導(dǎo)致節(jié)點(diǎn)攜帶更復(fù)雜的編碼系數(shù)矩陣，增大網(wǎng)絡(luò)傳輸開(kāi)銷。經(jīng)仿真實(shí)驗(yàn)結(jié)果表明目的節(jié)點(diǎn)解碼的時(shí)間復(fù)雜度為O（n3）。因此，D.Zeng等[9]提出了動(dòng)態(tài)分段式網(wǎng)絡(luò)編碼數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制（Dynamic Segmented Network Coding，DSNC）。該機(jī)制采用雙緩沖數(shù)據(jù)傳輸方式，DSNC機(jī)制的主要思想是對(duì)待傳輸消息進(jìn)行分段編碼傳輸，源節(jié)點(diǎn)發(fā)送完一段編碼數(shù)據(jù)后，待收到目的節(jié)點(diǎn)反饋回來(lái)的確認(rèn)消息包（確認(rèn)消息即ACK（Acknowledgement），下文用ACK表示）后進(jìn)行下一段數(shù)據(jù)的編碼傳輸。以下給出該算法步驟。①準(zhǔn)備階段：源節(jié)點(diǎn)不斷產(chǎn)生分段的數(shù)據(jù)并編碼轉(zhuǎn)發(fā)，直到接收到目的節(jié)點(diǎn)反饋的前一段的ACK。當(dāng)源節(jié)點(diǎn)接收到前一段的ACK，或者當(dāng)前段的大小達(dá)到預(yù)先設(shè)定值M，源節(jié)點(diǎn)將停止發(fā)送當(dāng)前段的數(shù)據(jù)，進(jìn)行下一步操作。②傳輸階段：當(dāng)編碼節(jié)點(diǎn)相遇后，率先交換其數(shù)據(jù)包頭信息，并且按照段的序號(hào)進(jìn)行排列。若當(dāng)前編碼節(jié)點(diǎn)中存在不完全一致的數(shù)據(jù)消息，則先轉(zhuǎn)發(fā)較小號(hào)段的數(shù)據(jù)，以保證目的節(jié)點(diǎn)能夠快速接收到該號(hào)段編碼包并且能夠快速進(jìn)行解碼操作。若編碼節(jié)點(diǎn)的緩存中只存在單個(gè)段的數(shù)據(jù)，則先轉(zhuǎn)發(fā)TTL（Time to live）較大的數(shù)據(jù)。③ACK反饋確認(rèn)階段：如果目的節(jié)點(diǎn)成功解碼并獲得了某個(gè)段的數(shù)據(jù)，則將ACK反饋到源節(jié)點(diǎn)。當(dāng)且僅當(dāng)目的節(jié)點(diǎn)接收到的數(shù)據(jù)包個(gè)數(shù)等于段的大小時(shí)，即可以成功解碼出原始數(shù)據(jù)。采用該機(jī)制可以有效解決大數(shù)據(jù)傳輸問(wèn)題，降低傳輸時(shí)延，提高消息投遞率。

3 展望

本文概述了目前現(xiàn)有的幾種基于網(wǎng)絡(luò)編碼的機(jī)會(huì)網(wǎng)絡(luò)路由算法。實(shí)驗(yàn)結(jié)果表明，采用隨機(jī)線性網(wǎng)絡(luò)編碼方法能有效降低網(wǎng)絡(luò)中數(shù)據(jù)副本的數(shù)量并且能夠提高網(wǎng)絡(luò)投遞率降低傳輸延遲，進(jìn)一步提升機(jī)會(huì)網(wǎng)絡(luò)在實(shí)際應(yīng)用中的優(yōu)勢(shì)。結(jié)合網(wǎng)絡(luò)編碼的機(jī)會(huì)網(wǎng)絡(luò)路由還存在很多亟待解決的問(wèn)題：

⑴ 編碼節(jié)點(diǎn)自身的資源消耗問(wèn)題；

⑵ 如何將網(wǎng)絡(luò)編碼帶來(lái)的網(wǎng)絡(luò)開(kāi)銷和改善網(wǎng)絡(luò)性能之間找到一個(gè)較好結(jié)合點(diǎn)；

⑶ 如何進(jìn)一步降低網(wǎng)絡(luò)編碼的復(fù)雜度；

⑷ 目標(biāo)節(jié)點(diǎn)接收到的編碼包能否保證立馬解碼；

⑸ ACK消息如何及時(shí)傳輸給源節(jié)點(diǎn)等這些問(wèn)題仍需進(jìn)一步研究。

總之，隨著網(wǎng)絡(luò)編碼技術(shù)與機(jī)會(huì)網(wǎng)絡(luò)的結(jié)合，機(jī)會(huì)網(wǎng)絡(luò)路由技術(shù)將會(huì)邁入新的發(fā)展階段。

參考文獻(xiàn)（References）：

[1] Ahlswede R， Cai N， Li S Y R， et al. Network information

flow[J].IEEETransactions on Information Theory，2000.46

（4）：1204-1216

[2] 熊永平，孫利民，牛建偉等.機(jī)會(huì)網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2009.20

（1）：124-137

[3] 任智，劉智虎，姚玉坤等.基于網(wǎng)絡(luò)編碼的機(jī)會(huì)網(wǎng)絡(luò)高效路由

算法[J].通信學(xué)報(bào)，2013.9：16-23

[4] LIN Y， LI B， LIANG B. Efficient network coded data

transmissions in disruptiontolerant networks[A]//The 27thIEEE Conference on ComputerCommunications[C].（INFOCOM 2008）. Phoenix， AZ， USA： [s.n.]，2008：1508-1516

[5] FRAGOULI C， WIDMER J， LE B J Y. Efficient

broadcasting using networkcoding[J].IEEE/ACM Transactions on Networking，2008.16（2）： 450-463

[6] Qin Shuang， Feng Gang. Performance modeling of

network coding based epidemicrouting in DTNs[A].//Wireless Communications and Networking Conference[C].

Shanghai， China： IEEE Press，2013：2057-2062

[7] Ahmed S， Kanhere S S. HUBCODE： hub-based

forwarding using network codingin delay tolerant networks[J]. Wireless Communications and Mobile Computing，2013.

[8] 陳曦.基于網(wǎng)絡(luò)編碼的延遲容忍網(wǎng)絡(luò)路由算法研究[D].重慶

郵電大學(xué)碩士學(xué)位論文，2015.

[9] Zeng Deze， Guo Song， Jin Hai， et al. Dynamic segmented

network coding for reliabledata dissemination in delay tolerant neworks[A].//IEEE International Conference onCommunications[C]. Ottawa， Canada： IEEE Press，2012：63-67

[10] 陶少國(guó)，黃佳慶，楊宗凱等.網(wǎng)絡(luò)編碼研究綜述[J].小型微型

計(jì)算機(jī)系統(tǒng)，2008.29（4）：583-592

[11] 唐東明.網(wǎng)絡(luò)編碼關(guān)鍵問(wèn)題研究[D].電子科技大學(xué)博士學(xué)位

論文，2013.

[12] 楊軍.網(wǎng)絡(luò)編碼的若干關(guān)鍵問(wèn)題研究[D].華中科技大學(xué)博士

學(xué)位論文，2013.

[13] Li S Y R， Yeung R W， Cai N. Linear Network Coding[J].

IEEE Transactions on Information Theory，2003.49（2）：371-381

[14] C.-C. Wang and N. B. Shroff， “Pairwise Intersession

Network Coding on Directed Networks，” IEEE Trans[J]. Inf. Theory，2010.56（8）： 3879-3900

[15] KATTI S， RAHUL H， HU W， et al. Xors in the air：

practical wireless network coding[J]. IEEE/ACM Transactions on Networking，2008.16（3）： 497-510

[16] WEN H， REN F Y， LIU J， et al. A storage-friendly routing

scheme in intermittently connected mobile network[J].IEEE Transactions on Vehicular Technology，2011.60（3）：1138-1149

[17] Zeng D， Guo S， Jin H， et al. Dynamic segmented network

coding for reliable data dissemination in delay tolerant networks[A].// IEEE International Conference on Communications[C]. IEEE，2012：63-67

[18] Zhang X， Neglia G， Kurose J， et al. On the Benefits of

Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[A]// International Symposium on Modeling and Optimization in Mobile， Ad Hoc and Wireless Networks[C]，2006：1-7

[19] Yao J， Ma C， Wu P， et al. An Opportunistic Network

Coding Routing for Opportunistic Networks[J]. International Journal of Parallel Programming， 2015：1-15