基于網(wǎng)絡(luò)編碼的機會網(wǎng)絡(luò)路由綜述

白琳　何欣　何明書

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

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

中圖分類號：TP393 文獻標(biāo)志碼：A 文章編號：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]是指對于在網(wǎng)絡(luò)中傳播的消息，數(shù)據(jù)傳輸節(jié)點對其不再僅僅執(zhí)行存儲轉(zhuǎn)發(fā)，而是可以對接收到的消息進行編碼與譯碼的處理，使得單次傳輸?shù)男畔⒘吭龃螅梢蕴岣哒麄€網(wǎng)絡(luò)的性能，進而提高數(shù)據(jù)傳輸效率。

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

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

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

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

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

2.1 RLC（Random linear coding）-Epidemic機制

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

2.2 HubCode機制

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

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

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

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

2.3 DSNC機制

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

3 展望

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

⑴ 編碼節(jié)點自身的資源消耗問題；

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

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

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

⑸ ACK消息如何及時傳輸給源節(jié)點等這些問題仍需進一步研究。

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

參考文獻（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] 熊永平，孫利民，牛建偉等.機會網(wǎng)絡(luò)[J].軟件學(xué)報，2009.20

（1）：124-137

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

算法[J].通信學(xué)報，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] 陶少國，黃佳慶，楊宗凱等.網(wǎng)絡(luò)編碼研究綜述[J].小型微型

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

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

論文，2013.

[12] 楊軍.網(wǎng)絡(luò)編碼的若干關(guā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