DTN中基于解碼預(yù)判的高效低時(shí)延數(shù)據(jù)傳輸算法

姚玉坤，朱麗青，陳 曦，任 智，徐亞偉，余志龍

?

DTN中基于解碼預(yù)判的高效低時(shí)延數(shù)據(jù)傳輸算法

姚玉坤，朱麗青，陳 曦，任 智，徐亞偉，余志龍

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室 重慶南岸區(qū)400065)

針對(duì)延遲容忍網(wǎng)絡(luò)(DTN)中編碼節(jié)點(diǎn)受限的數(shù)據(jù)傳輸機(jī)制(Hubcode)存在網(wǎng)絡(luò)開(kāi)銷大、解碼時(shí)延長(zhǎng)的問(wèn)題，該文提出一種基于解碼預(yù)判的高效低時(shí)延數(shù)據(jù)傳輸算法(HLDA)予以解決。HLDA算法提出了hub節(jié)點(diǎn)解碼預(yù)判新機(jī)制以減少數(shù)據(jù)包的端到端傳輸時(shí)延。通過(guò)提出單播、廣播混合傳輸新機(jī)制減少beacon信息包的廣播次數(shù)，從而減少網(wǎng)絡(luò)開(kāi)銷；并提出減少編碼系數(shù)矩陣交互機(jī)制，更進(jìn)一步地減少網(wǎng)絡(luò)開(kāi)銷。仿真結(jié)果表明，該算法能夠有效降低網(wǎng)絡(luò)開(kāi)銷，減少端到端的時(shí)延。

延遲容忍網(wǎng)絡(luò); 網(wǎng)絡(luò)編碼; hub中繼; 解碼預(yù)判; 網(wǎng)絡(luò)開(kāi)銷

DTN中通信節(jié)點(diǎn)間的連接具有間斷性，源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間很少存在持久不間斷的端到端路徑。正是由于節(jié)點(diǎn)間這種固有的間歇性連接特征，數(shù)據(jù)轉(zhuǎn)發(fā)成為DTN最具挑戰(zhàn)性的難題之一[1]。研究表明，網(wǎng)絡(luò)編碼能夠有效改善網(wǎng)絡(luò)環(huán)境，提高網(wǎng)絡(luò)的資源利用率[2]，尤其是隨機(jī)網(wǎng)絡(luò)編碼[3]的提出，更是將網(wǎng)絡(luò)編碼帶入到更加實(shí)用的分布式網(wǎng)絡(luò)領(lǐng)域中。因此，將網(wǎng)絡(luò)編碼應(yīng)用到DTN數(shù)據(jù)轉(zhuǎn)發(fā)策略中引起了人們廣泛的關(guān)注。

文獻(xiàn)[4]將隨機(jī)網(wǎng)絡(luò)編碼和傳染路由結(jié)合在一起，提出了基于網(wǎng)絡(luò)編碼的傳染路由算法(network coding based epidemic routing，NCER)，并通過(guò)理論分析和仿真實(shí)驗(yàn)驗(yàn)證了NCER算法對(duì)于網(wǎng)絡(luò)性能的提升。文獻(xiàn)[5]針對(duì)多數(shù)據(jù)流并存情況下的流間編碼問(wèn)題提出在NCER路由協(xié)議的基礎(chǔ)上，根據(jù)數(shù)據(jù)包目的節(jié)點(diǎn)的不同，只對(duì)目的節(jié)點(diǎn)相同的數(shù)據(jù)或編碼包進(jìn)行編碼，有效地解決了多數(shù)據(jù)流并存時(shí)引起的編碼向量長(zhǎng)度增加的問(wèn)題，減少了目的節(jié)點(diǎn)等待解碼的時(shí)間。文獻(xiàn)[6]針對(duì)釆用隨機(jī)網(wǎng)絡(luò)編碼會(huì)存在冗余編碼包而帶來(lái)額外網(wǎng)絡(luò)開(kāi)銷這一問(wèn)題，提出了冗余度的概念，利用冗余度來(lái)控制編碼包的傳輸，降低了冗余的網(wǎng)絡(luò)開(kāi)銷。文獻(xiàn)[7]針對(duì)傳統(tǒng)隨機(jī)網(wǎng)絡(luò)編碼中繼節(jié)點(diǎn)在某些網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下存在編碼無(wú)效的問(wèn)題，提出一種選擇有效信息編碼的算法，在理論上達(dá)到了減少編碼時(shí)間、降低編碼冗余度的目的。文獻(xiàn)[8]針對(duì)編碼包泛洪傳輸過(guò)程中信息冗余大、無(wú)效投遞較多等問(wèn)題，設(shè)計(jì)了基于蟻群算法的編碼包路由策略，降低了編碼投遞過(guò)程中的數(shù)據(jù)冗余，減少投遞時(shí)延。

在諸如會(huì)議場(chǎng)所、校園、智能電話和車(chē)載路由器等以人類活動(dòng)為中心的DTN中，存在小部分中心度高的節(jié)點(diǎn)能夠和大部分節(jié)點(diǎn)進(jìn)行連接[9-11]，即節(jié)點(diǎn)的中心度遵循冪律分布[12]。針對(duì)該場(chǎng)景，文獻(xiàn)[13]利用冪律分布這一特性，并結(jié)合網(wǎng)絡(luò)編碼提出一種新的DTN數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制。該文獻(xiàn)主要闡述了Hubcode V1和Hubcode V2兩種算法。這兩種算法都是只利用中心度高的節(jié)點(diǎn)作為消息的中繼，并在這些節(jié)點(diǎn)上采用隨機(jī)網(wǎng)絡(luò)編碼來(lái)處理到達(dá)同一目的地的多條消息。其中，經(jīng)過(guò)對(duì)Hubcode V1算法研究后發(fā)現(xiàn)，該算法在原理方面仍然存在以下兩個(gè)突出的缺陷：1) beacon信息包中攜帶編碼系數(shù)矩陣進(jìn)行周期性廣播，會(huì)帶來(lái)較大網(wǎng)絡(luò)開(kāi)銷，消耗較多網(wǎng)絡(luò)資源；2)目的節(jié)點(diǎn)接收到編碼包后，必須等到編碼系數(shù)矩陣滿秩后才能進(jìn)行解碼，如果目的節(jié)點(diǎn)后續(xù)接收到的編碼包的長(zhǎng)度比先接收到的編碼包的長(zhǎng)度長(zhǎng)時(shí)，會(huì)影響先前接收到的編碼包不能及時(shí)解碼，從而使得目的節(jié)點(diǎn)不能及時(shí)獲得原始數(shù)據(jù)包。本文為解決上述兩個(gè)問(wèn)題，提出了一種基于解碼預(yù)判的高效低時(shí)延數(shù)據(jù)傳輸算法HLDA。

1 問(wèn)題描述

文獻(xiàn)[13]提出的Hubcode V1算法的主要思想是：每個(gè)節(jié)點(diǎn)周期性廣播含有節(jié)點(diǎn)標(biāo)簽和編碼系數(shù)矩陣的beacon信息包；當(dāng)源節(jié)點(diǎn)與hub節(jié)點(diǎn)相遇時(shí)，將數(shù)據(jù)包進(jìn)行編碼傳輸；當(dāng)兩個(gè)hub節(jié)點(diǎn)相遇時(shí)，將發(fā)往同一目的節(jié)點(diǎn)的編碼包進(jìn)行再編碼，并利用接收到的相遇節(jié)點(diǎn)的編碼系數(shù)矩陣來(lái)判斷新生成的編碼包的線性相關(guān)性，線性無(wú)關(guān)則發(fā)送；當(dāng)hub節(jié)點(diǎn)遇到目的節(jié)點(diǎn)時(shí)，則直接將編碼包進(jìn)行編碼發(fā)送；目的節(jié)點(diǎn)收到足夠多的編碼包后解碼恢復(fù)出原始數(shù)據(jù)包。

Hubcode V1算法有效地提高了投遞率，減少了傳輸開(kāi)銷和端到端時(shí)延，具有較好的數(shù)據(jù)轉(zhuǎn)發(fā)性能，但仍存在以下不足：

1) 網(wǎng)絡(luò)中節(jié)點(diǎn)周期性廣播含有編碼系數(shù)矩陣的beacon信息包，會(huì)帶來(lái)較大的網(wǎng)絡(luò)開(kāi)銷，浪費(fèi)網(wǎng)絡(luò)資源；

2) 目的節(jié)點(diǎn)接收到編碼包后，必須等到編碼系數(shù)矩陣滿秩后才可解碼。在目的節(jié)點(diǎn)等待接收編碼包的過(guò)程中，若目的節(jié)點(diǎn)后續(xù)接收到的編碼包的長(zhǎng)度比緩存中的編碼包的長(zhǎng)度長(zhǎng)時(shí)，會(huì)影響緩存中的編碼包不能及時(shí)解碼，等待被解碼的時(shí)間也隨之延長(zhǎng)，進(jìn)而影響數(shù)據(jù)包的端到端時(shí)延。

2 HLDA算法

為了解決Hubcode V1算法存在的上述問(wèn)題，本文提出HLDA算法。HLDA算法提出了3個(gè)新機(jī)制，分別是單播、廣播混合傳輸機(jī)制、減少編碼系數(shù)矩陣交互機(jī)制和hub節(jié)點(diǎn)解碼預(yù)判機(jī)制，從而可以降低網(wǎng)絡(luò)開(kāi)銷和減少端到端時(shí)延等。

定義1 原始數(shù)據(jù)包序號(hào)ID集合，用來(lái)記錄編碼包中的原始數(shù)據(jù)包序號(hào)ID的集合。hub節(jié)點(diǎn)接收到編碼包后，記錄參與編碼該編碼包的原始數(shù)據(jù)包的序號(hào)ID，將目的節(jié)點(diǎn)相同的原始數(shù)據(jù)包的序號(hào)ID放在同一個(gè)集合中。

定義2 緩存集合，用來(lái)記錄節(jié)點(diǎn)自身緩存中與其相遇的節(jié)點(diǎn)而緩存中沒(méi)有的原始數(shù)據(jù)包序號(hào)ID的集合。當(dāng)兩個(gè)hub節(jié)點(diǎn)、相遇時(shí)，交換彼此beacon信息包中的集合I、I，接收到集合I后，運(yùn)算I與I，得到節(jié)點(diǎn)緩存中沒(méi)有而節(jié)點(diǎn)緩存中有的原始數(shù)據(jù)包序號(hào)ID的緩存集合：

初始化=。

定義3 解碼集合，用來(lái)記錄目的節(jié)點(diǎn)解碼出的原始數(shù)據(jù)包的集合。

定義4 未解碼集合T，用來(lái)記錄第個(gè)編碼包中尚未被解碼出來(lái)的原始數(shù)據(jù)包的集合。當(dāng)hub節(jié)點(diǎn)與目的節(jié)點(diǎn)相遇時(shí)，hub節(jié)點(diǎn)利用接收到目的節(jié)點(diǎn)發(fā)送的解碼集合中的信息來(lái)對(duì)自己緩存中的編碼包進(jìn)行解碼判斷，將不能從編碼包中解碼出來(lái)的原始數(shù)據(jù)包進(jìn)行記錄，初始化T=。用R表示未解碼集合T中元素的個(gè)數(shù)，初始化R=0。

2.1 單播、廣播混合傳輸機(jī)制

為了解決Hubcode V1算法中beacon信息包的冗余發(fā)送帶來(lái)的開(kāi)銷問(wèn)題，本文提出單播、廣播混合傳輸機(jī)制。該機(jī)制將beacon信息包分為必須周期性廣播發(fā)送的beacon_1和需要時(shí)才單播發(fā)送的beacon_2兩部分，通過(guò)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)對(duì)beacon_1和beacon_2的發(fā)送時(shí)機(jī)和發(fā)送方式進(jìn)行額外的判斷和管理，避免了不必要的beacon_2信息包在網(wǎng)絡(luò)上的冗余發(fā)送和傳輸。單播、廣播混合傳輸機(jī)制的具體操作步驟如下：

1) 將beacon信息包分為beacon_1和beacon_2兩部分并在兩種情況下分別進(jìn)行傳輸。其中， beacon_1攜帶節(jié)點(diǎn)標(biāo)簽，beacon_2攜帶集合；

2) 每個(gè)節(jié)點(diǎn)周期性廣播beacon_1，當(dāng)接收節(jié)點(diǎn)接收到beacon_1時(shí)可根據(jù)節(jié)點(diǎn)標(biāo)簽判斷出對(duì)方節(jié)點(diǎn)是否是hub節(jié)點(diǎn)；

3) 當(dāng)對(duì)方節(jié)點(diǎn)是hub節(jié)點(diǎn)時(shí)，則節(jié)點(diǎn)將beacon_2單播給對(duì)方節(jié)點(diǎn)，而不再是廣播的形式。

2.2 減少編碼系數(shù)矩陣交互機(jī)制

為解決Hubcode V1算法中編碼系數(shù)矩陣交互開(kāi)銷問(wèn)題，本文提出減少編碼系數(shù)矩陣交互機(jī)制，當(dāng)兩個(gè)hub節(jié)點(diǎn)相遇后，具體操作步驟如圖1所示。

圖1 減少編碼系數(shù)矩陣交互機(jī)制流程圖

2.3 hub節(jié)點(diǎn)解碼預(yù)判機(jī)制

針對(duì)Hubcode V1算法中目的節(jié)點(diǎn)等待解碼時(shí)延較長(zhǎng)的問(wèn)題，本文提出hub節(jié)點(diǎn)解碼預(yù)判機(jī)制，將越有利于目的節(jié)點(diǎn)解碼的編碼包優(yōu)先發(fā)送給目的節(jié)點(diǎn)，減少數(shù)據(jù)包的端到端時(shí)延。具體步驟如下：

1) 當(dāng)目的節(jié)點(diǎn)與hub節(jié)點(diǎn)相遇時(shí)，目的節(jié)點(diǎn)將含有解碼集合的beacon信息包發(fā)送給hub節(jié)點(diǎn)；

2) hub節(jié)點(diǎn)根據(jù)解碼集合更新目的節(jié)點(diǎn)為對(duì)方節(jié)點(diǎn)的各個(gè)編碼包的未解碼集合T以及R；

3) hub節(jié)點(diǎn)將min{R,R,…,R|R≠0，=1,2,…,}所對(duì)應(yīng)的編碼包發(fā)送給目的節(jié)點(diǎn)；

4) 為了避免將冗余的編碼包發(fā)送給目的節(jié)點(diǎn)，在執(zhí)行完步驟3)后需要進(jìn)行“規(guī)避冗余”操作，即將步驟3)中發(fā)送出去的編碼包中的原始數(shù)據(jù)包序號(hào)ID從未解碼集合T中剔除，并更新R。然后繼續(xù)執(zhí)行步驟3)，直到全部R都為0；

5)目的節(jié)點(diǎn)接收到編碼包后先利用已解碼出的編碼包進(jìn)行初次解碼操作，對(duì)于不能解碼的編碼包進(jìn)行緩存，等待編碼系數(shù)矩陣滿秩后再進(jìn)行解碼。

3 HLDA算法分析

3.1 比特開(kāi)銷

引理 1 HLDA算法beacon信息包的比特開(kāi)銷小于Hubcode V1算法。

證明：設(shè)在網(wǎng)絡(luò)中任意一個(gè)hub節(jié)點(diǎn)緩存中編碼包的目的節(jié)點(diǎn)有個(gè)，其中，到達(dá)相同目的節(jié)點(diǎn)的編碼包有n(1<<)個(gè)。這n個(gè)編碼包是由m個(gè)不同的原始數(shù)據(jù)包參與編碼，編碼系數(shù)從伽羅華域(216)中隨機(jī)選取，可知編碼系數(shù)矩陣為的矩陣。

在Hubcode V1算法中，beacon信息包含節(jié)點(diǎn)標(biāo)簽和編碼系數(shù)矩陣兩部分內(nèi)容。其中，節(jié)點(diǎn)標(biāo)簽的長(zhǎng)度為bits，編碼系數(shù)矩陣的長(zhǎng)度為16bits。

故beacon信息包的總比特開(kāi)銷為：

而在HLDA算法中，beacon信息包攜帶節(jié)點(diǎn)標(biāo)簽和原始數(shù)據(jù)包ID集合。集合可看成是一個(gè)的矩陣，故beacon信息包的總比特開(kāi)銷為：

顯然有：

由式(4)和式(5)可得：

當(dāng)只有一個(gè)編碼包時(shí)，上式中的等號(hào)才成立。

所以，HLDA算法beacon信息包的比特開(kāi)銷小于Hubcode V1算法。證畢。

3.2 HLDA算法的應(yīng)用分析

為了進(jìn)一步闡明HLDA算法解碼預(yù)判的有效性，分別對(duì)Hubcode V1算法和HLDA算法進(jìn)行應(yīng)用分析。簡(jiǎn)述起見(jiàn)，在該分析中只選擇一個(gè)hub節(jié)點(diǎn)作為描述對(duì)象，闡述其與目的節(jié)點(diǎn)相遇后在兩種算法中分別進(jìn)行何種操作。

假設(shè)hub節(jié)點(diǎn)與目的節(jié)點(diǎn)相遇，其中hub節(jié)點(diǎn)緩存中到達(dá)該目的節(jié)點(diǎn)的編碼包的編碼系數(shù)矩陣示例如圖2和圖3所示。圖中P和X分別表示編碼包和編碼包中參與編碼的原始數(shù)據(jù)包。已知目的節(jié)點(diǎn)已解碼獲得了原始數(shù)據(jù)包1和2，緩存中有一編碼包為：

7=11+22+33+44(7)

首先，具體闡述Hubcode V1算法的應(yīng)用過(guò)程，如圖2所示。

圖2 Hubcode算法應(yīng)用舉例

當(dāng)hub節(jié)點(diǎn)與目的節(jié)點(diǎn)相遇后，hub節(jié)點(diǎn)將編碼包1、2、3、4先進(jìn)行再編碼操作：

然后將編碼包5發(fā)送給目的節(jié)點(diǎn)。此時(shí)，目的節(jié)點(diǎn)收到5后，利用已解碼出的1、2并不能將緩存中的編碼包7解碼獲得原始數(shù)據(jù)包，并且因收到hub節(jié)點(diǎn)發(fā)送的編碼包5后，由原來(lái)只需等待接收一個(gè)線性無(wú)關(guān)的編碼包即可解碼變?yōu)樵诮邮盏?這一編碼包后仍需再等待接收一個(gè)線性無(wú)關(guān)的編碼包才能解碼。

下面利用圖3來(lái)分析HLDA算法的應(yīng)用過(guò)程。圖3中用正六邊形和圓形標(biāo)記分別表示hub節(jié)點(diǎn)第1次、第2次選擇發(fā)送的編碼包。

圖3 HLDA算法應(yīng)用舉例

首先，hub節(jié)點(diǎn)根據(jù)自身的編碼系數(shù)矩陣更新編碼包1、2、3和4的未解碼集合為1={1,2}、2={1,2,3}、3={3}、4={1,2,3,4,5}以及1=2、2=3、3=1、4=5。當(dāng)hub節(jié)點(diǎn)接收到目的節(jié)點(diǎn)的解碼集合={1,2}后，更新未解碼集合1=、2={3}、3={3}、4={3,4,5}以及1=0、2=1、3=1、4=3。

其次，hub節(jié)點(diǎn)將非0的最小值所對(duì)應(yīng)的編碼包2發(fā)送給目的節(jié)點(diǎn)，并采取規(guī)避冗余措施，更新1=、2=、3=、4={4,5}；1=0、2=0、3=0、4=2。

然后，hub節(jié)點(diǎn)繼續(xù)選擇非0的最小值所對(duì)應(yīng)的編碼包4發(fā)送給目的節(jié)點(diǎn)，并更新1=、2=、3=、4=；1=0、2=0、3=0、4=0。此時(shí)hub節(jié)點(diǎn)需要發(fā)送的編碼包已全部發(fā)送完畢。

當(dāng)目的節(jié)點(diǎn)接收到編碼包2后，利用已解碼出的原始數(shù)據(jù)包1和2，可將緩存中的7進(jìn)行解碼獲得原始數(shù)據(jù)包3、4；接收到編碼包4后，目的節(jié)點(diǎn)利用原始數(shù)據(jù)包1、2、3和4對(duì)編碼包4進(jìn)行解碼，進(jìn)而獲得原始數(shù)據(jù)包5。顯然，目的節(jié)點(diǎn)第一次接收到編碼包2后，即可解碼獲得原始數(shù)據(jù)包3、4，比Hubcode V1算法更早獲得原始數(shù)據(jù)包，可以減少目的節(jié)點(diǎn)等待解碼的時(shí)間，進(jìn)而減少端到端的時(shí)延。

3.3 HLDA算法復(fù)雜度分析

HLDA算法主要包括編解碼和輔助信息交互兩部分。假設(shè)在網(wǎng)絡(luò)中傳輸個(gè)數(shù)據(jù)包。那么在編解碼部分中，編碼的計(jì)算復(fù)雜度為()。由于編碼系數(shù)矩陣為矩陣，因此解碼的計(jì)算復(fù)雜度為(2)。在輔助信息交互部分，集合和集合的可能最大長(zhǎng)度為，因此總的beacon交互的計(jì)算復(fù)雜度為()。在減少編碼系數(shù)矩陣交互機(jī)制中，最壞的情況下，即hub節(jié)點(diǎn)緩存中沒(méi)有攜帶新信息且編碼系數(shù)矩陣未滿秩，此時(shí)兩個(gè)hub節(jié)點(diǎn)之間不得不交互編碼系數(shù)矩陣，相應(yīng)的計(jì)算復(fù)雜度為(2)。故HLDA算法的計(jì)算復(fù)雜度為(2)。HLDA算法和Hubcode V1算法在空間復(fù)雜度上屬于同一級(jí)別，都為(2)。

4 仿真實(shí)驗(yàn)及結(jié)果

4.1 仿真環(huán)境及參數(shù)設(shè)置

本文使用網(wǎng)絡(luò)仿真軟件OPNET 14.5進(jìn)行建模和仿真，仿真實(shí)驗(yàn)中用到的主要仿真參數(shù)如表1所示。

表1 仿真場(chǎng)景的主要參數(shù)設(shè)置

4.2 仿真結(jié)果分析

4.2.1 歸一化控制開(kāi)銷

歸一化控制開(kāi)銷是指網(wǎng)絡(luò)運(yùn)行時(shí)間內(nèi)累加的所有節(jié)點(diǎn)發(fā)出的beacon信息包的比特總數(shù)與到達(dá)目的節(jié)點(diǎn)的原始數(shù)據(jù)包的比特總數(shù)的比值，表示為：

式中，為歸一化控制開(kāi)銷；N表示第個(gè)beacon信息包的比特?cái)?shù)；D表示第個(gè)到達(dá)目的節(jié)點(diǎn)的原始數(shù)據(jù)包的比特?cái)?shù)。仿真結(jié)果如圖4所示。

圖4 歸一化控制開(kāi)銷比較

圖4表明，與Hubcode V1算法相比，HLDA算法能夠減少歸一化控制開(kāi)銷16.92%以上。開(kāi)銷減少的原因主要有兩點(diǎn)：1) 采用單播、廣播混合傳輸機(jī)制，減少了beacon信息包的廣播次數(shù)；2) 將Hubcode V1算法beacon信息包中攜帶的編碼系數(shù)矩陣變?yōu)樵紨?shù)據(jù)包ID集合，減少了beacon信息包中的比特開(kāi)銷。

4.2.2 平均端到端時(shí)延

數(shù)據(jù)包平均端到端時(shí)延是指所有數(shù)據(jù)包從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的平均時(shí)延。其表達(dá)式為：

式中，avg為數(shù)據(jù)包平均端到端時(shí)延；T為第個(gè)數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)包的時(shí)延；num為已到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)包總個(gè)數(shù)。仿真結(jié)果如圖5所示。

圖5 平均端到端時(shí)延比較

圖5表明，與Epidemic算法和Hubcode V1算法相比，HLDA算法消息的平均端到端時(shí)延至少減少了3.35%，這是因?yàn)楫?dāng)hub節(jié)點(diǎn)與目的節(jié)點(diǎn)相遇時(shí)，HLDA算法采用hub節(jié)點(diǎn)解碼預(yù)判機(jī)制，充分利用目的節(jié)點(diǎn)已經(jīng)解碼出的原始數(shù)據(jù)包，將能夠解碼出全部或者部分原始數(shù)據(jù)包的編碼包優(yōu)先發(fā)送至目的節(jié)點(diǎn)，使得目的節(jié)點(diǎn)盡早獲得原數(shù)據(jù)包，并且縮短目的節(jié)點(diǎn)未解碼的編碼包的長(zhǎng)度，減少了編碼包的傳輸次數(shù)。

4.2.3 接收成功率

在本文采用的網(wǎng)絡(luò)模型中，選取連通度高的節(jié)點(diǎn)作為hub節(jié)點(diǎn)來(lái)?yè)?dān)任全網(wǎng)消息中繼的角色，為闡明hub節(jié)點(diǎn)在全網(wǎng)中的所占比例對(duì)消息接收成功率的影響，現(xiàn)將仿真結(jié)果分析如下。

接收成功率是指消息成功達(dá)到目的節(jié)點(diǎn)的個(gè)數(shù)占全網(wǎng)中源節(jié)點(diǎn)發(fā)送消息總數(shù)的比例，其值為：

式中，表示接收成功率；表示已到達(dá)目的節(jié)點(diǎn)的原始數(shù)據(jù)包的個(gè)數(shù)；表示源節(jié)點(diǎn)發(fā)送的原始數(shù)據(jù)包的個(gè)數(shù)。仿真結(jié)果如圖6所示。

圖6 接收成功率比較

從圖6中可知，當(dāng)hub節(jié)點(diǎn)占到全網(wǎng)20%左右時(shí)，HLDA算法和Hubcode V1算法的接收成功率最高，但超過(guò)20%后接收成功率則隨著hub節(jié)點(diǎn)所占比例的增加反而會(huì)降低。這是因?yàn)樵谌W(wǎng)中hub節(jié)點(diǎn)所占的比例越大，編碼包在各個(gè)hub節(jié)點(diǎn)上分散的越多，hub節(jié)點(diǎn)將編碼包投遞給目的節(jié)點(diǎn)的機(jī)會(huì)隨之減少。

5 結(jié)束語(yǔ)

本文針對(duì)編碼節(jié)點(diǎn)受限的數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制存在的網(wǎng)絡(luò)開(kāi)銷大和解碼時(shí)延較長(zhǎng)等問(wèn)題，提出一種基于解碼預(yù)判的高效低時(shí)延數(shù)據(jù)傳輸算法HLDA。新算法提出3個(gè)新機(jī)制，分別為單播、廣播混合傳輸機(jī)制、減少編碼系數(shù)矩陣交互機(jī)制和hub節(jié)點(diǎn)解碼預(yù)判機(jī)制。仿真結(jié)果表明，該算法能夠有效降低網(wǎng)絡(luò)開(kāi)銷，減少數(shù)據(jù)包的端到端時(shí)延。

參 考 文 獻(xiàn)

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges[J]. Communications Surveys & Tutorials, 2006, 8(1): 24-37.

[2] ZHANG Q, JIN Z, ZHANG Z, et al. Network coding for applications in the delay tolerant network[C]//Proceeding of the 5th International Conference on Mobile Ad Hoc and Sensor Networks.Fujian, China: IEEE, 2009: 376-380.

[3] TRACEY H O, MEDARD M, KOETTER R, et al. A random linear network codig approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10): 4413- 4430.

[4] LIN Y, LIANG B, LI B. Performance modeling of network coding in epidemic routing[C]//Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking. San Juan, Puerto Rico: ACM, 2007: 67-74.

[5] 白云飛. 基于鏈路代價(jià)綜合評(píng)估和網(wǎng)絡(luò)編碼的延遲容忍網(wǎng)絡(luò)路由優(yōu)化研究[D].北京: 北京郵電大學(xué), 2012.

BAI Yun-fei. Research on delay tolerant network routing optimization based on syntheticl estimation of contact metrics and network coding[D]. Beijing: Beijing University of Posts and Telecommunications, 2012.

[6] ZHAO B, PENG W, SONG Z, et al. Towards efficient and practical network coding in delay tolerant networks[J]. Computers & Mathematics with Applications, 2012, 63(2): 588-600.

[7] 王琦, 李佶恒, 赫云祥, 等. 利用線性相關(guān)優(yōu)化隨機(jī)網(wǎng)絡(luò)編碼中繼節(jié)點(diǎn)算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào), 2014, 12(37): 1446-1450.

WANG Qi, LI Ji-heng, HE Yun-xiang, et al. An optimization algorithm of random linear network coding for relay node by linear correlation[J]. Journal of Hefei by University of Technology, 2014, 12(37): 1446-1450.

[8] 鄧廣宏, 曹萬(wàn)華, 張劍, 等. DTN網(wǎng)絡(luò)環(huán)境下基于蟻群算法的數(shù)據(jù)編碼分[J]. 電子學(xué)報(bào), 2014, 8(32): 1636-1641.

DENG Guang-hong, CAO Wan-hua, ZHANG Jian, et al. Data dissemination mechanism with network coding based on ant colony algorithm in DTN environment[J]. Chinese Journal of Electronics, 2014, 8(32): 1636-1641.

[9] HUI P, CHAINTREAU A, SCOTT J, et al. Pocket switched networks and human mobility in conference environments [C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. NewYork, USA: ACM, 2005: 244-251.

[10] ZHANG X, KUROSE J, LEVINE B N, et al. Study of a bus-based disruption-tolerant network: Mobility modeling and impact on routing[C]//Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking. Canada: ACM, 2007: 195-206.

[11] HSU W, HELMY A. On modal encounter patterns in wireless LAN traces[C]//The 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. Boston: IEEE, 2006: 1-10.

[12] HUI P, CHAINTREAU A, SCOTT J, et al. Pocket switched networks and human mobility in conference environments [C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. NewYork, USA: ACM, 2005: 244-251.

[13] AHMED S, KANHERE S S. Hubcode: Hub-based forwarding using network coding in delay tolerant networks[J]. Wireless Communications and Mobile Computing, 2013, 13(9): 828-846.

編 輯 葉 芳

A High-efficiency and Low-Delay Data Transmission Algorithm in DTN Based on Decoding Anticipate

YAO Yu-kun, ZHU Li-qing, CHEN Xi, REN Zhi, XU Ya-wei, and YU Zhi-long

(Chongqing Key Laboratory of Mobile Communication Technology, Chongqing University of Posts and Telecommunications Nan’an Chongqing 400065)

A high-efficiency and low-delay data transmission algorithm based on decoding anticipate (HLDA) is proposed to address the problems that there exist large overhead for broadcasting beacon which carrys coding coefficient matrix and the destination nodes wait a long time to decode in the hub-based forwarding using network coding in delay tolerant networks(DTN). The HLDA proposed a new mechanism of anticipating decoding by hub nodes is presented in HLDA to decrease the end-to-end delay and proposed a unicast and broadcast mixing mechanism to decrease the overhead. By decreasing the coding coefficient matrix interaction mechanism to further reduce overhead. Simulation results show that HLDA can reduce the overhead and average end-to-end delay as compared to the Hubcode.

decoding anticipate; DTN; hub relay; network coding; overhead

TP393

A

10.3969/j.issn.1001-0548.2016.05.002

2015-03-18；

2016-01-11

長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃(IRT1299)；重慶市科委自然科學(xué)基金(cstc2012jjA40040)

姚玉坤(1964-)，女，教授，主要從事網(wǎng)絡(luò)編碼及網(wǎng)絡(luò)管理與應(yīng)用方面的研究.