喬晉龍，高 媛，劉亞翃，譚春花

（中北大學(xué)電子與計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山西太原 030051）

機(jī)會(huì)網(wǎng)絡(luò)中高效的數(shù)據(jù)分發(fā)機(jī)制
——CRLNC

喬晉龍，高 媛，劉亞翃，譚春花

（中北大學(xué)電子與計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山西太原 030051）

針對(duì)如何提高機(jī)會(huì)網(wǎng)絡(luò)中數(shù)據(jù)分發(fā)效率的問題，提出了一種數(shù)據(jù)分簇和隨機(jī)線性網(wǎng)絡(luò)編碼結(jié)合的數(shù)據(jù)分發(fā)機(jī)制——CRLNC。其核心思想是先將數(shù)據(jù)分成幾簇，然后在簇內(nèi)分成相同數(shù)量的數(shù)據(jù)塊，源節(jié)點(diǎn)發(fā)送一簇中的數(shù)據(jù)塊，中間節(jié)點(diǎn)運(yùn)用隨機(jī)線性編碼算法將其中的數(shù)據(jù)塊編碼轉(zhuǎn)發(fā)出去，目標(biāo)節(jié)點(diǎn)接收到其中的編碼數(shù)據(jù)塊后采用高斯—約旦消元法將數(shù)據(jù)漸進(jìn)還原。在這種數(shù)據(jù)分發(fā)機(jī)制中，針對(duì)節(jié)點(diǎn)緩存空間的冗余問題提出一種基于簇號(hào)和線性相關(guān)性的節(jié)點(diǎn)緩存策略。理論分析和仿真結(jié)果證明，與傳統(tǒng)的數(shù)據(jù)分發(fā)相比，該算法可以有效地提高網(wǎng)絡(luò)吞吐量，減小端到端的時(shí)延。

機(jī)會(huì)網(wǎng)絡(luò);數(shù)據(jù)分發(fā);隨機(jī)線性網(wǎng)絡(luò)編碼;線性相關(guān)性

【本文獻(xiàn)信息】喬晉龍，高媛，劉亞翃，等.機(jī)會(huì)網(wǎng)絡(luò)中高效的數(shù)據(jù)分發(fā)機(jī)制——CRLNC［J］.電視技術(shù)，2014，38（1）.

機(jī)會(huì)網(wǎng)絡(luò)是一種不需要源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間存在完整的通信鏈路，利用節(jié)點(diǎn)移動(dòng)帶來的相遇機(jī)會(huì)實(shí)現(xiàn)通信的自組織網(wǎng)絡(luò)［1－2］。數(shù)據(jù)分發(fā)指源節(jié)點(diǎn)將數(shù)據(jù)通過某種機(jī)制轉(zhuǎn)發(fā)到目標(biāo)節(jié)點(diǎn)的過程，是機(jī)會(huì)網(wǎng)絡(luò)研究的熱點(diǎn)之一。由于其節(jié)點(diǎn)移動(dòng)劇烈、網(wǎng)絡(luò)鏈路頻繁斷裂等特點(diǎn)使基于存儲(chǔ)轉(zhuǎn)發(fā)的數(shù)據(jù)分發(fā)技術(shù)不能實(shí)現(xiàn)數(shù)據(jù)的理論傳輸容量，且具有高延遲、低數(shù)據(jù)率的特點(diǎn)，為了確保數(shù)據(jù)的可靠傳輸，研究一種適合機(jī)會(huì)網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)機(jī)制很有意義。

網(wǎng)絡(luò)編碼［3］（Network Coding，NC）由R.Alshwede等首次提出，其原理為網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)接收到的多個(gè)數(shù)據(jù)塊進(jìn)行編碼，編碼后的數(shù)據(jù)再由中間節(jié)點(diǎn)轉(zhuǎn)發(fā)，其最直接的應(yīng)用就是數(shù)據(jù)分發(fā)。

針對(duì)上述問題，本文提出一種基于分簇的隨機(jī)線性網(wǎng)絡(luò)編碼（Clustering－Based Random Linear Network Coding，CRLNC）數(shù)據(jù)分發(fā)機(jī)制。目標(biāo)節(jié)點(diǎn)在解碼時(shí)運(yùn)用高斯—約旦消元法，使接收編碼數(shù)據(jù)塊和解碼同時(shí)進(jìn)行來減小時(shí)延。數(shù)據(jù)塊在網(wǎng)絡(luò)中滯留的時(shí)間會(huì)很長(zhǎng)，而節(jié)點(diǎn)緩存區(qū)有限，在數(shù)據(jù)量較大的情況下容易產(chǎn)生節(jié)點(diǎn)緩存區(qū)溢出的情況。因此，本文相繼提出一種基于簇號(hào)及線性相關(guān)性的節(jié)點(diǎn)緩存模型。當(dāng)中間節(jié)點(diǎn)緩存區(qū)滿時(shí)，以“簇號(hào)”為索引優(yōu)先存儲(chǔ)屬于同一簇的數(shù)據(jù)塊進(jìn)行編碼。然后中間節(jié)點(diǎn)對(duì)同一簇的數(shù)據(jù)塊進(jìn)行線性相關(guān)性檢測(cè)，決定數(shù)據(jù)塊的保留與丟棄。

1 研究現(xiàn)狀

通信網(wǎng)絡(luò)端到端的最大數(shù)據(jù)流，是由通信網(wǎng)絡(luò)中有向圖的最小割決定的［4］。傳統(tǒng)的機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)方式大多基于洪泛的傳染擴(kuò)散方法，雖然可以適應(yīng)網(wǎng)絡(luò)的拓?fù)鋭?dòng)態(tài)性，卻幾乎不可能達(dá)到網(wǎng)絡(luò)數(shù)據(jù)流的上界。早期的數(shù)據(jù)分發(fā)策略主要依賴于數(shù)據(jù)發(fā)送者，例如有作者提出了一種Stored－GeoCast分發(fā)策略［5］，在該策略中發(fā)送者為準(zhǔn)備發(fā)送的每個(gè)數(shù)據(jù)指定目標(biāo)區(qū)域和有效期，在目標(biāo)區(qū)域內(nèi)的節(jié)點(diǎn)都可接收到數(shù)據(jù)。這種算法沒有注重?cái)?shù)據(jù)的分類，同一條消息的副本過多，造成網(wǎng)絡(luò)負(fù)載增長(zhǎng)過快從而使帶寬利用率較低。在后來提出的以內(nèi)容為中心的數(shù)據(jù)分發(fā)方法LMDC中［6］，數(shù)據(jù)按內(nèi)容種類進(jìn)行分層，可以使用戶選擇自己感興趣的數(shù)據(jù)。該方法采用HEC，即源節(jié)點(diǎn)結(jié)合復(fù)制技術(shù)和EC處理后將數(shù)據(jù)發(fā)送出去。無論是哪種數(shù)據(jù)分發(fā)方式，中間節(jié)點(diǎn)對(duì)數(shù)據(jù)的操作只是存儲(chǔ)與轉(zhuǎn)發(fā)。

Katti等提出基于機(jī)會(huì)的網(wǎng)絡(luò)編碼方法（COPE）［7］，首次研究了網(wǎng)絡(luò)編碼在無線環(huán)境協(xié)議層面上的具體實(shí)現(xiàn)問題。COPE協(xié)議中每個(gè)節(jié)點(diǎn)對(duì)傳輸媒體進(jìn)行偵聽，獲得它鄰居節(jié)點(diǎn)的狀態(tài)信息，決定編碼機(jī)會(huì)，并在本地的FIFO緩存結(jié)構(gòu)內(nèi)進(jìn)行編碼，然后進(jìn)行基于機(jī)會(huì)的路由。但是該協(xié)議需要節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)包并進(jìn)行編碼，如果網(wǎng)絡(luò)出現(xiàn)擁塞，可能就會(huì)耗費(fèi)較多的節(jié)點(diǎn)存儲(chǔ)空間。

碼構(gòu)造算法是在數(shù)據(jù)分發(fā)系統(tǒng)中部署和實(shí)現(xiàn)網(wǎng)絡(luò)編碼的核心，R.Koeettr和M.Mdeard提出的代數(shù)法碼構(gòu)造方式［8］，以及S.Jaggi等人提出的信息流法［9］，都要求在已知整個(gè)網(wǎng)絡(luò)拓?fù)湫畔⒌那闆r下，用一個(gè)系統(tǒng)轉(zhuǎn)移矩陣來描述源節(jié)點(diǎn)輸出的數(shù)據(jù)和目標(biāo)節(jié)點(diǎn)接收到的數(shù)據(jù)的關(guān)系，通過構(gòu)造符合要求的系統(tǒng)轉(zhuǎn)移矩陣來實(shí)現(xiàn)網(wǎng)絡(luò)編碼。機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)是隨機(jī)高速移動(dòng)的，網(wǎng)絡(luò)的拓?fù)湫畔⒔?jīng)常變化，這種方法代價(jià)很大。為使得網(wǎng)絡(luò)編碼在機(jī)會(huì)網(wǎng)絡(luò)中具有實(shí)際可用性，Li等人提出了線性網(wǎng)絡(luò)編碼的概念，證實(shí)節(jié)點(diǎn)進(jìn)行線性網(wǎng)絡(luò)編碼運(yùn)算，具有可行性，能夠達(dá)到最大流傳輸理論極限［10］。Ho等人提出了有限域下隨機(jī)線性網(wǎng)絡(luò)編碼的思想，并證實(shí)其有效性［11］。之后，隨機(jī)線性網(wǎng)絡(luò)編碼被應(yīng)用于各個(gè)方面的研究，用于提高網(wǎng)絡(luò)吞吐量和能量利用率。

2 相關(guān)研究工作

2.1 CRLNC數(shù)據(jù)分發(fā)機(jī)制的數(shù)學(xué)模型

定義1（網(wǎng)絡(luò)模型）:圖G=（V，E）表示機(jī)會(huì)網(wǎng)絡(luò)，其中V表示所有節(jié)點(diǎn)的集合，源節(jié)點(diǎn)為S，目標(biāo)節(jié)點(diǎn)的集合為R，任一目標(biāo)節(jié)點(diǎn)表示為Ri∈R，E表示此刻所存在的所有鏈路的集合。

定義2（數(shù)據(jù)流向量）:源節(jié)點(diǎn)S發(fā)出的數(shù)據(jù)，鏈路e∈E上傳輸?shù)臄?shù)據(jù)，目標(biāo)節(jié)點(diǎn)Ri∈R接收到的數(shù)據(jù)，均以向量的形式取之于有限域GF，該向量成為數(shù)據(jù)流（Data Flow）。假設(shè)源節(jié)點(diǎn)要發(fā)送的數(shù)據(jù)塊數(shù)目為n，則數(shù)據(jù)流向量為b=（b1，b2，…，bn），每個(gè)目標(biāo)節(jié)點(diǎn)接收到的數(shù)據(jù)塊可用向量 r=（r1，r2，…，rn）表示。

定義3（系數(shù)矩陣）:中間節(jié)點(diǎn)接收到數(shù)據(jù)塊后對(duì)其進(jìn)行線性組合時(shí)隨機(jī)在有限域GF內(nèi)選取的數(shù)稱為隨機(jī)系數(shù)，表示為cij，i，j∈［1，n］。由隨機(jī)系數(shù)cij組合而成的矩陣為系數(shù)矩陣，表示為C。當(dāng)目標(biāo)節(jié)點(diǎn)接收到r時(shí)，若C滿秩（Full Rank），就能通過矩陣逆運(yùn)算bT=C－1r解出源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)流向量b。

定義4（轉(zhuǎn)移矩陣）:系數(shù)矩陣C稱為隨機(jī)線性網(wǎng)絡(luò)編碼相對(duì)于目標(biāo)節(jié)點(diǎn)的轉(zhuǎn)移矩陣（Transfer Matrix）。

機(jī)會(huì)網(wǎng)絡(luò)CRLNC數(shù)據(jù)分發(fā)機(jī)制中各鏈路傳輸?shù)臄?shù)據(jù)、節(jié)點(diǎn)接收的數(shù)據(jù)和節(jié)點(diǎn)發(fā)出的數(shù)據(jù)均可表示為源節(jié)點(diǎn)發(fā)出數(shù)據(jù)流向量b中各元素的線性組合。因此，對(duì)于目標(biāo)節(jié)點(diǎn)收到的任一數(shù)據(jù)塊ri∈r，有ri=ci1b1+ci2b2+…+cinbn，i∈［1，n］，矩陣形式為

2.2 CRLNC數(shù)據(jù)分發(fā)機(jī)制的算法實(shí)現(xiàn)

CRLNC數(shù)據(jù)分發(fā)機(jī)制的核心思想是利用機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的高運(yùn)算能力，源節(jié)點(diǎn)將原始數(shù)據(jù)先分簇再分塊后將一簇內(nèi)的數(shù)據(jù)塊順序發(fā)送出去。中間節(jié)點(diǎn)接收到數(shù)據(jù)塊后將其隨機(jī)線性編碼組合，目標(biāo)節(jié)點(diǎn)收到滿足可解性條件的編碼數(shù)據(jù)塊后運(yùn)用高斯—約旦消元法解碼獲得原始數(shù)據(jù)。目標(biāo)節(jié)點(diǎn)具備可解性的條件是:目標(biāo)節(jié)點(diǎn)接收到的線性編碼組合的編碼向量矩陣（即由編碼參數(shù)組成的矩陣）的秩大于或者等于所含數(shù)據(jù)塊的數(shù)量。

圖1表示了每個(gè)在機(jī)會(huì)網(wǎng)絡(luò)中傳輸?shù)木幋a數(shù)據(jù)塊結(jié)構(gòu)，包含簇號(hào)CID、塊號(hào)ID、編碼向量和編碼信息。其中簇號(hào)CID表示該編碼塊屬于哪一簇，塊號(hào)ID是來標(biāo)識(shí)該數(shù)據(jù)塊屬于某一簇的第幾塊，編碼向量的選取原則是從有限域GF（28）中隨機(jī)選取，編碼信息表示對(duì)原始數(shù)據(jù)或者已編碼數(shù)據(jù)進(jìn)行線性組合的結(jié)果。

圖1 CRLNC數(shù)據(jù)分發(fā)機(jī)制的數(shù)據(jù)塊結(jié)構(gòu)

如圖2所示，源節(jié)點(diǎn)S先將原始數(shù)據(jù)分成若干簇，再在每簇內(nèi)分成大小相等的3個(gè)數(shù)據(jù)塊B1，B2，B3后，將其發(fā)送給目標(biāo)節(jié)點(diǎn)R1和R2。下面描述機(jī)會(huì)網(wǎng)絡(luò)的中間節(jié)點(diǎn)如何運(yùn)用隨機(jī)線性網(wǎng)絡(luò)編碼來完成到目標(biāo)節(jié)點(diǎn)R1和R2的數(shù)據(jù)分發(fā)。其中，一簇?cái)?shù)據(jù)塊傳輸完畢后再進(jìn)行下一簇?cái)?shù)據(jù)的線性組合、傳輸。編碼后的數(shù)據(jù)塊可表示為B'=∑ciBi。其中，ci為中間節(jié)點(diǎn)選擇的隨機(jī)系數(shù)，隨機(jī)系數(shù)的選取原則是從有限域GF（28）中隨機(jī)選取，Bi為原始數(shù)據(jù)塊。

圖2 CRLNC數(shù)據(jù)分發(fā)模型

源節(jié)點(diǎn)S將數(shù)據(jù)塊B1，B2，B3逐一發(fā)送出去，節(jié)點(diǎn)A，B，C，D，E是中間節(jié)點(diǎn)。其中節(jié)點(diǎn)A接收到數(shù)據(jù)塊B1，節(jié)點(diǎn)B接收到數(shù)據(jù)塊B2，節(jié)點(diǎn)C接收到B3。節(jié)點(diǎn)D接收到由節(jié)點(diǎn)A和B發(fā)送來的數(shù)據(jù)塊B1和B2后將其線性組合為c1B1+c2B2;節(jié)點(diǎn)E接收到由節(jié)點(diǎn)B和C發(fā)送來的數(shù)據(jù)塊B2和B3后將其線性組合為c3B1+c4B2，然后分別將編碼數(shù)據(jù)塊發(fā)送出去。目標(biāo)節(jié)點(diǎn)R1只需接收到來自節(jié)點(diǎn)A的數(shù)據(jù)塊B1，來自節(jié)點(diǎn)D的編碼數(shù)據(jù)塊c1B1+c2B2或者來自節(jié)點(diǎn)E的編碼數(shù)據(jù)塊c3B2+c4B3的任意一個(gè)即可運(yùn)用高斯—約旦消元法進(jìn)行漸進(jìn)式解碼來獲得原始數(shù)據(jù)塊B1，B2，B3。對(duì)于目標(biāo)節(jié)點(diǎn)R2來說，同理可解碼出原始數(shù)據(jù)塊。

對(duì)于目標(biāo)節(jié)點(diǎn)R1開說，若某時(shí)刻接收到3個(gè)線性無關(guān)的編碼數(shù)據(jù)塊B1，c1B1+c2B2和c3B2+c4B3，則可以得出三元方程組，即

目標(biāo)節(jié)點(diǎn)接收到3個(gè)編碼數(shù)據(jù)塊后的編碼向量矩陣情況為

目標(biāo)節(jié)點(diǎn)將編碼向量矩陣通過高斯—約旦消元法解碼原始數(shù)據(jù)塊B1，B2，B3。

高斯—約旦消元法屬于逐步解碼，也稱為漸進(jìn)解碼。目的是為了減少解碼時(shí)間對(duì)端到端傳輸總體性能的影響，基本思想是使解碼和接收數(shù)據(jù)塊同時(shí)進(jìn)行，從而節(jié)省時(shí)間。漸進(jìn)解碼的具體方法是:每收到一個(gè)線性組合，使用初等行變換將由系數(shù)和線性組合而成的增廣矩陣化簡(jiǎn)一次，使其變?yōu)樾屑s簡(jiǎn)階梯形矩陣，如

收到第3個(gè)線性組合并成功化簡(jiǎn)后，增廣矩陣的左右兩側(cè)分別為3階單位矩陣和解碼出的原始數(shù)據(jù)分塊，如

式（5）所示增廣矩陣的右側(cè)即是通過高斯—約旦消元法解碼出的原始數(shù)據(jù)塊，結(jié)果為

下列偽碼描述了上述基于分簇的隨機(jī)線性網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)機(jī)制的實(shí)現(xiàn)過程:

2.3 基于簇號(hào)及線性相關(guān)性的混合節(jié)點(diǎn)緩存機(jī)制

在CRLNC數(shù)據(jù)分發(fā)機(jī)制中，由于中間節(jié)點(diǎn)接收到的編碼數(shù)據(jù)塊可能是冗余數(shù)據(jù)，如果經(jīng)常在節(jié)點(diǎn)間傳輸這種冗余數(shù)據(jù)，則會(huì)嚴(yán)重浪費(fèi)帶寬和節(jié)點(diǎn)的計(jì)算資源，而且這種冗余數(shù)據(jù)會(huì)被其他中間節(jié)點(diǎn)重新進(jìn)行隨機(jī)線性網(wǎng)絡(luò)編碼，在機(jī)會(huì)網(wǎng)絡(luò)中進(jìn)行大范圍的傳播，導(dǎo)致整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)效率極低。針對(duì)這個(gè)問題提出一種基于簇號(hào)及線性相關(guān)性的節(jié)點(diǎn)緩存機(jī)制，若接收到的編碼數(shù)據(jù)塊的編碼向量與節(jié)點(diǎn)已有的編碼數(shù)據(jù)塊向量線性相關(guān)，則節(jié)點(diǎn)直接丟棄接收到的編碼數(shù)據(jù)塊;否則，節(jié)點(diǎn)緩存該數(shù)據(jù)塊。機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)執(zhí)行該機(jī)制的偽代碼如下:

中間節(jié)點(diǎn)接收到編碼數(shù)據(jù)塊后，在該編碼塊和之前到達(dá)的編碼塊進(jìn)行比較。如果傳送給中間節(jié)點(diǎn)的數(shù)據(jù)塊的簇號(hào)和該節(jié)點(diǎn)里其他編碼數(shù)據(jù)塊的簇號(hào)相同，那么檢測(cè)接收到的編碼數(shù)據(jù)塊對(duì)應(yīng)的編碼向量是否已經(jīng)存在于該節(jié)點(diǎn)，或者該編碼向量是否與該節(jié)點(diǎn)已經(jīng)存在數(shù)據(jù)塊包含的編碼向量線性相關(guān)。若線性相關(guān)，則說明該數(shù)據(jù)塊是冗余數(shù)據(jù)，節(jié)點(diǎn)直接丟棄該編碼數(shù)據(jù)塊;否則，說明該編碼塊攜帶有新的數(shù)據(jù)，節(jié)點(diǎn)將緩存該編碼數(shù)據(jù)塊并再次進(jìn)行線性編碼并轉(zhuǎn)發(fā)?？偠灾@種緩存機(jī)制能夠有效降低各中間節(jié)點(diǎn)執(zhí)行編碼的計(jì)算消耗，同樣也緩解了機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)緩存矛盾。

3 仿真實(shí)驗(yàn)與性能評(píng)價(jià)分析

實(shí)驗(yàn)將在時(shí)延和網(wǎng)絡(luò)吞吐量性能方面分別對(duì)基于存儲(chǔ)和轉(zhuǎn)發(fā)的傳統(tǒng)的數(shù)據(jù)分發(fā)機(jī)制、一般的網(wǎng)絡(luò)編碼以及CRLNC機(jī)制進(jìn)行性能評(píng)價(jià)，仿真軟件采用事件驅(qū)動(dòng)的NS2仿真平臺(tái)，該軟件可以根據(jù)需要添加相關(guān)協(xié)議來確定節(jié)點(diǎn)的行為和節(jié)點(diǎn)之間數(shù)據(jù)傳輸?shù)姆绞健?/p>

仿真場(chǎng)景為100 m×100 m的區(qū)域，隨機(jī)分布著1個(gè)源節(jié)點(diǎn)、2個(gè)目標(biāo)節(jié)點(diǎn)和50個(gè)中間節(jié)點(diǎn)，原始數(shù)據(jù)長(zhǎng)度L=10 Mbyte，在運(yùn)用隨機(jī)線性網(wǎng)絡(luò)編碼時(shí)將原始數(shù)據(jù)分成10簇。

3.1 時(shí)延性能評(píng)價(jià)

在進(jìn)行3種數(shù)據(jù)分發(fā)機(jī)制的時(shí)延性能分析時(shí)，根據(jù)每簇中的數(shù)據(jù)分塊數(shù)的變化來分析，將每一簇分別分為如圖3所示的數(shù)據(jù)塊數(shù)目。從圖中可以明顯看出，無論采用哪種數(shù)據(jù)分發(fā)機(jī)制，當(dāng)每簇的分塊數(shù)為4時(shí)，即每個(gè)數(shù)據(jù)塊大小為256 kbyte時(shí)數(shù)據(jù)分發(fā)時(shí)延最小。因?yàn)槿裘看氐姆謮K數(shù)較小，則每塊的數(shù)據(jù)量較大，在發(fā)送過程中極可能由于數(shù)據(jù)丟失而重新傳輸;若每簇的分塊數(shù)較大，則每塊的數(shù)據(jù)量較小，這樣會(huì)增加數(shù)據(jù)發(fā)送的次數(shù)。這兩種情況都會(huì)導(dǎo)致高時(shí)延問題。在最開始發(fā)送數(shù)據(jù)量最大時(shí)，3種數(shù)據(jù)分發(fā)的時(shí)延都比較大，但是總體而言，網(wǎng)絡(luò)編碼機(jī)制要優(yōu)于傳統(tǒng)的基于存儲(chǔ)和轉(zhuǎn)發(fā)的數(shù)據(jù)分發(fā)機(jī)制。本文提出的基于分簇的隨機(jī)線性網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)機(jī)制在節(jié)點(diǎn)緩存問題上采用了不同的基于簇號(hào)及線性相關(guān)性的節(jié)點(diǎn)緩存策略，所以不會(huì)由于節(jié)點(diǎn)緩存滿，數(shù)據(jù)丟失后重傳而造成時(shí)延增大;目標(biāo)節(jié)點(diǎn)在解碼時(shí)運(yùn)用高斯—約旦消元法可以將接收數(shù)據(jù)和解碼數(shù)據(jù)并行執(zhí)行，所以在很大程度上縮短了時(shí)延。

3.2 網(wǎng)絡(luò)吞吐量性能評(píng)價(jià)

圖3 數(shù)據(jù)分發(fā)機(jī)制時(shí)延性能評(píng)價(jià)

在進(jìn)行3種數(shù)據(jù)分發(fā)機(jī)制的網(wǎng)絡(luò)吞吐量性能分析時(shí)，將每一簇分為4塊數(shù)據(jù)塊，即每塊大小為256 kbyte來進(jìn)行仿真。如圖4所示的數(shù)據(jù)分發(fā)網(wǎng)絡(luò)吞吐量性能評(píng)價(jià)圖，從圖中可以看出，傳統(tǒng)的基于存儲(chǔ)和轉(zhuǎn)發(fā)的數(shù)據(jù)分發(fā)機(jī)制中，由于各鏈路上傳輸?shù)臄?shù)據(jù)不能被疊加，所以其吞吐量要遠(yuǎn)遠(yuǎn)低于兩種基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)機(jī)制，無法實(shí)現(xiàn)理論上的容量。而一般的網(wǎng)絡(luò)編碼對(duì)原始數(shù)據(jù)進(jìn)行簡(jiǎn)單的編碼操作然后發(fā)送出去，這種數(shù)據(jù)分發(fā)機(jī)制的吞吐量比傳統(tǒng)的數(shù)據(jù)分發(fā)機(jī)制要高很多，但是在數(shù)據(jù)量較大的情況下性能會(huì)降低。而基于分簇的隨機(jī)線性網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)機(jī)制在數(shù)據(jù)量很大的情況下將原始數(shù)據(jù)分簇再分塊，減少了單次要傳輸?shù)臄?shù)據(jù)量，所以可實(shí)現(xiàn)高達(dá)9 Mbit/s的網(wǎng)絡(luò)吞吐量。

圖4 數(shù)據(jù)分發(fā)機(jī)制網(wǎng)絡(luò)吞吐量性能評(píng)價(jià)

由上述仿真結(jié)果分析可知，CRLNC在端到端延遲和網(wǎng)絡(luò)吞吐量性能指標(biāo)上均表現(xiàn)良好，很好地解決了機(jī)會(huì)網(wǎng)絡(luò)中數(shù)據(jù)分發(fā)的問題。

4 小結(jié)

本文提出了一種機(jī)會(huì)網(wǎng)絡(luò)中基于分簇的隨機(jī)線性網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)機(jī)制，理論分析和仿真結(jié)果表明:與傳統(tǒng)的數(shù)據(jù)分發(fā)機(jī)制相比，CRLNC可以弱化甚至消除數(shù)據(jù)分發(fā)效率對(duì)原始數(shù)據(jù)大小的依賴，有效減少了單次要傳輸?shù)臄?shù)據(jù)量，提高了傳輸效率;基于簇號(hào)和線性相關(guān)性的節(jié)點(diǎn)緩存機(jī)制可以保證節(jié)點(diǎn)之間傳輸?shù)木幋a數(shù)據(jù)塊總是有效的，可以提高網(wǎng)絡(luò)帶寬利用率，節(jié)約節(jié)點(diǎn)的計(jì)算資源?？傊?，本文提出的數(shù)據(jù)分發(fā)模型能夠在一定程度上提高網(wǎng)絡(luò)編碼的執(zhí)行效率，降低網(wǎng)絡(luò)編碼所需的計(jì)算消耗，進(jìn)一步提升數(shù)據(jù)分發(fā)的性能。在今后的工作中，在擁有高效率網(wǎng)絡(luò)編碼的同時(shí)要進(jìn)一步針對(duì)低復(fù)雜性的網(wǎng)絡(luò)編碼進(jìn)行更深入的研究。

:

［1］熊永平，孫利民，牛建偉，等.機(jī)會(huì)網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2009，20（1）:124－137.

［2］HU Q，ZHENG J.Weight pick:an efficient packet selection algorithm for network coding based multicast retransmission in mobile communication networks［J］.Wireless Networks，2013，19（3）:363－372.

［3］AHLSWEDE R，CAI N，LI S Y R，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46（4）:1204－1216.

［4］ELIAS P，F(xiàn)EINSTEIN A，SHANNON C E.A note on the maximum flow through a network［J］.IEEE Transactions on Information Theory，1956，2（4）:117－119.

［5］MAIHOFER C，F(xiàn)RANZ W J，EBERHARDT R.Stored geocast［C］∥Proc.Kommunikation in Verteilten Systemen（KiVS）.［S.l.］:Springer Verlag，2003:257－268.

［6］CHEN L J，YU C H，TSENG C L，et al.A content－centric framework for effective data dissemination in opportunistic networks［J］.IEEE Journal on Selected Areas in Communications，2008，26（5）:761－772.

［7］KATTI S，HU W，RAHUL H，The importance of being opportunistic:practical network coding for wireless enviroments［EB/OL］.［2013－01－01］.https://www.cl.cam.ac.uk/research/srg/netos/papers/2005－allerton－netcoding.pdf.

［8］HO T，LUN D S.Network coding:AN Introduction［D］.Cambridge:Cambridge University，2008.

［9］JAGGI S，LANGBERG M，KATTI S，et al.Resilient network coding in the presence of byzantine adversaries［J］.IEEE Transactions on Information Theory，2008，54（6）:2596－2603.

［10］LI S Y R，HO S T.Ring－theoretic foundation of convolutional network coding［C］//Proc.Fourth Workshop on Network Coding，Theory and Applications.Hong Kong:IEEE Press，2008:1－6.

［11］HO T，KOETTER R，MEDARD，M，et al.A random linear network coding approach to multicast.IEEE Trans.Inform.Theory，2006，52（10）:4413－4430.

［12］黃辰，王芙蓉，戴彬，等.基于網(wǎng)絡(luò)編碼的無線自組織網(wǎng)數(shù)據(jù)分發(fā)機(jī)制［J］.電子學(xué)報(bào)，2010（8）:1852－1857.

CRLNC:Efficient Data Dissemination Mechanism For Opportunistic Network

QIAO Jinlong，GAO Yuan，LIU Yahong，TAN Chunhua

（Colleage of Computer Science and Technology，North University of China，Taiyuan 030051，China）

Aiming at improving the efficiency of data dissemination in opportunistic network，an efficient data dissemination mechanism combined with clustering and random linear network coding is proposed.The core idea is dividing the data into several clusters firstly，and then dividing each cluster into the same number of data blocks，the source node sends the data blocks in each cluster，the intermediate node encodes the data blocks with random linear coding algorithm and then forwards the encoded data block，the destination node uses Gauss－Jordan elimination method to restore the data progressively after receiving the encoded data blocks.Aiming at the redundancy of node cache space，this data dissemination mechanism proposes a node caching strategy based on cluster number and linear correlation.Theoretical analysis and simulation results show that CRLNC outperforms the traditional data dissemination mechanism，CRLNC mechanism effectively improves network throughput and reduces the end－to－end delay.

opportunistic network;data dissemination;random liner network coding;linear relevance

TN915;TP393

B

責(zé)任編輯:許 盈

2013－03－12