基于網絡編碼的機會網絡路由綜述

白琳　何欣　何明書

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

關鍵詞： 網絡編碼； 機會網絡； 隨機線性編碼； 投遞率

中圖分類號：TP393 文獻標志碼：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 引言

網絡編碼概念起源于R.Ahlswede等人于 2000年發表在IEEE trans-IT上的一篇題為“網絡信息流”的文章。網絡編碼[1]是指對于在網絡中傳播的消息，數據傳輸節點對其不再僅僅執行存儲轉發，而是可以對接收到的消息進行編碼與譯碼的處理，使得單次傳輸的信息量增大，可以提高整個網絡的性能，進而提高數據傳輸效率。

根據節點對消息執行不同的操作處理，網絡編碼可分為兩種：①網絡節點對消息的處理，有線性網絡編碼和非線性網絡編碼；②網絡節點對消息編碼系數的處理，有隨機性網絡編碼和確定性網絡編碼。網絡編碼采用“存儲-編譯碼-轉發”的方式進行數據的傳輸，在機會網絡[2]中，通信節點的存儲、攜帶、轉發消息為網絡編碼的實現提供了極大的便利條件，因此在共享輸出鏈路的網絡環境下，結合適當的網絡編碼方案對機會網絡吞吐量的提升、網絡性能的優化、傳輸效率的提高等，都提供了良好的基礎。本文介紹幾種結合網絡編碼的路由算法在機會網絡中的應用。

1 主動異或創建編碼機制

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

2 隨機線性網絡編碼機制

結合引言的介紹，再針對當前隨機線性網絡編碼技術的應用，本節主要介紹以下幾種編碼機制：RLC（Random linear coding）-Epidemic 機制、HubCode 機制、DSNC 機制。

2.1 RLC（Random linear coding）-Epidemic機制

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

2.2 HubCode機制

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

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

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

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

2.3 DSNC機制

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

3 展望

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

⑴ 編碼節點自身的資源消耗問題；

⑵ 如何將網絡編碼帶來的網絡開銷和改善網絡性能之間找到一個較好結合點；

⑶ 如何進一步降低網絡編碼的復雜度；

⑷ 目標節點接收到的編碼包能否保證立馬解碼；

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

總之，隨著網絡編碼技術與機會網絡的結合，機會網絡路由技術將會邁入新的發展階段。

參考文獻（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].軟件學報，2009.20

（1）：124-137

[3] 任智，劉智虎，姚玉坤等.基于網絡編碼的機會網絡高效路由

算法[J].通信學報，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] 陳曦.基于網絡編碼的延遲容忍網絡路由算法研究[D].重慶

郵電大學碩士學位論文，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] 陶少國，黃佳慶，楊宗凱等.網絡編碼研究綜述[J].小型微型

計算機系統，2008.29（4）：583-592

[11] 唐東明.網絡編碼關鍵問題研究[D].電子科技大學博士學位

論文，2013.

[12] 楊軍.網絡編碼的若干關鍵問題研究[D].華中科技大學博士

學位論文，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