吳大鵬，樓芃雯，樊思龍，王汝言

（重慶郵電大學(xué) 寬帶泛在接入技術(shù)研究所，重慶 400065）

1 引言

區(qū)別于傳統(tǒng)移動(dòng)自組織網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制，間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)充分利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)，以“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的模式逐跳實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)，適用于節(jié)點(diǎn)稀疏、移動(dòng)頻繁及連接具有間斷特性的應(yīng)用環(huán)境[1,2]。

與其他無(wú)線(xiàn)網(wǎng)絡(luò)類(lèi)似，間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)也具有資源有限性的特點(diǎn)，因此，數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制是間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。為了充分地利用有限的網(wǎng)絡(luò)資源，研究人員提出了網(wǎng)絡(luò)編碼方法，解決了多源數(shù)據(jù)并行傳輸?shù)膯?wèn)題，能夠有效提高網(wǎng)絡(luò)資源利用率[3]。按照此種方式，網(wǎng)絡(luò)中所傳輸數(shù)據(jù)的總量不隨網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)密度改變而發(fā)生變化，網(wǎng)絡(luò)開(kāi)銷(xiāo)得到了有效的控制[4,5]。

針對(duì)間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)的特點(diǎn)，國(guó)內(nèi)外研究人員提出了多種基于網(wǎng)絡(luò)編碼的數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制。文獻(xiàn)[6,7]提出了基于擦除碼的數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制，此種機(jī)制需要預(yù)先獲知整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)連接次數(shù)以確定轉(zhuǎn)發(fā)塊數(shù)，難以適用于動(dòng)態(tài)性較強(qiáng)的間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)。文獻(xiàn)[8]分析了適用于間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)的隨機(jī)線(xiàn)性網(wǎng)絡(luò)編碼(RLC,random linear coding)機(jī)制，源節(jié)點(diǎn)以隨機(jī)線(xiàn)性編碼對(duì)數(shù)據(jù)進(jìn)行融合后轉(zhuǎn)發(fā)。此種機(jī)制無(wú)需預(yù)先獲知相關(guān)網(wǎng)絡(luò)參數(shù)，但數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程需要所有節(jié)點(diǎn)具有編碼和解碼功能，極大地消耗了節(jié)點(diǎn)緩存和網(wǎng)絡(luò)資源。文獻(xiàn)[9]提出了編碼數(shù)據(jù)冗余控制機(jī)制，源節(jié)點(diǎn)將多個(gè)數(shù)據(jù)融合，并利用二進(jìn)制噴灑的方法轉(zhuǎn)發(fā)，從一定程度上控制了編碼數(shù)據(jù)的冗余程度，但網(wǎng)絡(luò)中編碼節(jié)點(diǎn)的規(guī)模依然較大。文獻(xiàn)[10]提出了優(yōu)先編碼機(jī)制，其假定網(wǎng)絡(luò)中存在多個(gè)優(yōu)先級(jí)數(shù)據(jù)，節(jié)點(diǎn)由高到低逐級(jí)轉(zhuǎn)發(fā)數(shù)據(jù)，并結(jié)合當(dāng)前網(wǎng)絡(luò)狀態(tài)確認(rèn)信息。此種機(jī)制并未對(duì)優(yōu)先級(jí)數(shù)量與控制開(kāi)銷(xiāo)進(jìn)行定量分析，且此種網(wǎng)絡(luò)中的數(shù)據(jù)傳輸延時(shí)較大，確認(rèn)信息所反映的網(wǎng)絡(luò)狀態(tài)準(zhǔn)確程度難以保障。

相關(guān)研究結(jié)果表明，間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)具有“大世界小世界”特性，其中的節(jié)點(diǎn)具有極強(qiáng)的社會(huì)屬性[11,12]。根據(jù)節(jié)點(diǎn)之間社會(huì)關(guān)系的強(qiáng)度，可以將網(wǎng)絡(luò)從邏輯上劃分為多個(gè)社區(qū)，具有相同歸屬社區(qū)的節(jié)點(diǎn)社會(huì)關(guān)系強(qiáng)度較高、相遇頻繁，反之，相遇次數(shù)較少，且網(wǎng)絡(luò)中活躍度較高的節(jié)點(diǎn)經(jīng)常游離在歸屬社區(qū)和其他社區(qū)之間。顯然，上述相關(guān)機(jī)制并未考慮節(jié)點(diǎn)之間的社會(huì)屬性，難以為數(shù)據(jù)合理地選擇中繼節(jié)點(diǎn)；此外，將網(wǎng)絡(luò)編碼方法應(yīng)用于間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)中的數(shù)據(jù)轉(zhuǎn)發(fā)還需要考慮以下4個(gè)方面問(wèn)題：1）除了具有普通節(jié)點(diǎn)的存儲(chǔ)、攜帶、轉(zhuǎn)發(fā)功能外，編碼節(jié)點(diǎn)還需具備編（解）碼功能，導(dǎo)致其成本增加；2）在數(shù)據(jù)處理過(guò)程中，編碼節(jié)點(diǎn)的相關(guān)操作將增加數(shù)據(jù)的傳輸延時(shí)；3）數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中需要攜帶編碼和解碼操作相關(guān)信息，產(chǎn)生了額外的控制開(kāi)銷(xiāo)；4）編碼節(jié)點(diǎn)需要執(zhí)行較多的存儲(chǔ)和計(jì)算操作，節(jié)點(diǎn)資源消耗嚴(yán)重。

針對(duì)節(jié)點(diǎn)的社會(huì)屬性以及編碼節(jié)點(diǎn)受限特性，本文提出一種編碼節(jié)點(diǎn)數(shù)量動(dòng)態(tài)管理的間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)（DMCN,data forwarding mechanism based on coding nodes dynamical managing）機(jī)制。通過(guò)利用各社區(qū)節(jié)點(diǎn)數(shù)量的變化情況來(lái)自適應(yīng)地管理節(jié)點(diǎn)的編碼功能，進(jìn)而，根據(jù)節(jié)點(diǎn)社會(huì)屬性以及可用資源狀態(tài)為所傳輸?shù)臄?shù)據(jù)合理地匹配中繼節(jié)點(diǎn)，從而在有效降低網(wǎng)絡(luò)資源開(kāi)銷(xiāo)的條件下，保障數(shù)據(jù)傳輸?shù)目煽啃?，提高網(wǎng)絡(luò)資源利用率。

2 編碼節(jié)點(diǎn)動(dòng)態(tài)管理方法

從邏輯功能角度來(lái)說(shuō)，間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)中的節(jié)點(diǎn)可以劃分為普通節(jié)點(diǎn)和編碼節(jié)點(diǎn)。編碼節(jié)點(diǎn)除了具有普通節(jié)點(diǎn)的功能外，還具有數(shù)據(jù)處理功能，能夠執(zhí)行編碼、解碼相關(guān)操作。通過(guò)動(dòng)態(tài)地估計(jì)各社區(qū)內(nèi)節(jié)點(diǎn)數(shù)量，本文以最優(yōu)化編碼節(jié)點(diǎn)數(shù)量為原則管理各個(gè)社區(qū)中節(jié)點(diǎn)工作模式。

2.1 最優(yōu)化編碼節(jié)點(diǎn)數(shù)量

相關(guān)理論研究和實(shí)際測(cè)量表明，對(duì)于間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)來(lái)說(shuō)，在所有節(jié)點(diǎn)都執(zhí)行編解碼操作時(shí)，網(wǎng)絡(luò)性能將嚴(yán)重惡化，根據(jù)當(dāng)前網(wǎng)絡(luò)規(guī)模及運(yùn)行狀態(tài)，編碼節(jié)點(diǎn)數(shù)量存在最優(yōu)值[13,14]。

對(duì)于間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)的節(jié)點(diǎn)來(lái)說(shuō)，成為編碼節(jié)點(diǎn)需要具備充要條件如下。

1)節(jié)點(diǎn)所承載的多個(gè)數(shù)據(jù)流至少來(lái)自 2個(gè)或者2個(gè)以上的鏈路，且數(shù)據(jù)流經(jīng)相同鏈路完成轉(zhuǎn)發(fā)。

2)節(jié)點(diǎn)的輸入數(shù)據(jù)流之和大于共享輸出鏈路的傳輸容量 C，如式(1)所示，其中，fi為上一跳節(jié)點(diǎn)經(jīng)不同鏈路所轉(zhuǎn)發(fā)到本節(jié)點(diǎn)的數(shù)據(jù)流。

間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)以分布式方式運(yùn)行，網(wǎng)絡(luò)拓?fù)錉顟B(tài)動(dòng)態(tài)改變，通常采用隨機(jī)圖模型對(duì)網(wǎng)絡(luò)性能進(jìn)行分析，將網(wǎng)絡(luò)中的節(jié)點(diǎn)抽象為隨機(jī)圖中的端點(diǎn)，節(jié)點(diǎn)之間的鏈路抽象為連接隨機(jī)圖中各個(gè)端點(diǎn)的邊。給定隨機(jī)圖模型下，最大網(wǎng)絡(luò)信息流流經(jīng)某條邊的概率如定理1所示[13]，節(jié)點(diǎn)間的當(dāng)前連接為編碼連接的概率如定理2所示，進(jìn)而，可以獲知編碼節(jié)點(diǎn)數(shù)量與當(dāng)前網(wǎng)絡(luò)規(guī)模之間的關(guān)系。

定理1 在隨機(jī)圖 G=(V,E)中，V為網(wǎng)絡(luò)節(jié)點(diǎn)集合，E為所有在網(wǎng)絡(luò)中可能出現(xiàn)的邊集合（即網(wǎng)絡(luò)可能出現(xiàn)的連接情況）。|V|=n為集合中的節(jié)點(diǎn)數(shù)量，當(dāng)n足夠大，且對(duì)于任意滿(mǎn)足條件的ε，存在式(2)所描述的關(guān)系，其中，p(p＞0)為任意兩節(jié)點(diǎn)存在連接的概率。

在滿(mǎn)足式(2)中ε的條件下，最大網(wǎng)絡(luò)信息流流經(jīng)某條邊（即存在連接時(shí)）的概率Pe滿(mǎn)足式(3)關(guān)系，其中，p(p＞0)為任意兩節(jié)點(diǎn)存在連接的概率。

可見(jiàn)，當(dāng)網(wǎng)絡(luò)規(guī)模足夠大時(shí)，任何連接均以較低的概率成為最大網(wǎng)絡(luò)信息流路徑，即當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較多時(shí)，節(jié)點(diǎn)成為編碼節(jié)點(diǎn)的可能性較低，因此，在間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)中，只需要在一部分節(jié)點(diǎn)上執(zhí)行編碼操作，即編碼節(jié)點(diǎn)數(shù)量存在最優(yōu)解。

網(wǎng)絡(luò)中的編碼連接是指多源數(shù)據(jù)在節(jié)點(diǎn)上編碼后的輸出連接，也就是說(shuō)編碼節(jié)點(diǎn)的數(shù)量不會(huì)超過(guò)編碼連接的數(shù)量，因此節(jié)點(diǎn)成為編碼節(jié)點(diǎn)的概率Pen也滿(mǎn)足上式。同時(shí)Pen與當(dāng)前網(wǎng)絡(luò)規(guī)模即該網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)n存在如下關(guān)系

可知，節(jié)點(diǎn)成為編碼節(jié)點(diǎn)的概率 Pen與網(wǎng)絡(luò)規(guī)模呈線(xiàn)性關(guān)系

假設(shè)關(guān)于x的2個(gè)函數(shù)f(x)和g(x)存在如下關(guān)系

那么這2個(gè)函數(shù)f(x)和g(x)存在近似線(xiàn)性關(guān)系

從而，可知當(dāng)前網(wǎng)絡(luò)規(guī)模與所需要的編碼節(jié)點(diǎn)數(shù)量Ncoding之間的關(guān)系如下

綜上所述，根據(jù)定理1和定理2可以獲知最大網(wǎng)絡(luò)信息流流經(jīng)某條邊的概率以及節(jié)點(diǎn)間當(dāng)前連接為編碼連接的概率，通過(guò)對(duì)式(4)求極限，并應(yīng)用無(wú)窮小定理，可以得到如下結(jié)論：網(wǎng)絡(luò)所需編碼節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)規(guī)模呈近似線(xiàn)性關(guān)系；此外，通過(guò)分析及實(shí)際測(cè)量可以驗(yàn)證，網(wǎng)絡(luò)所需編碼節(jié)點(diǎn)數(shù)量可以控制在較小的范圍之內(nèi)，具體的最優(yōu)解情況在后面的仿真部分給出。

2.2 編碼節(jié)點(diǎn)選取

間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)中，節(jié)點(diǎn)按照彼此的關(guān)系強(qiáng)度，從邏輯上組成多個(gè)社區(qū)，社區(qū)內(nèi)部成員節(jié)點(diǎn)關(guān)系相對(duì)穩(wěn)定，且具有冪率特征[14]，即一小部分節(jié)點(diǎn)活躍程度較高，具有較強(qiáng)的連通性?？梢?jiàn)，選擇此類(lèi)節(jié)點(diǎn)作為編碼節(jié)點(diǎn)，執(zhí)行編解碼操作，并為編碼后的數(shù)據(jù)合理地選擇中繼節(jié)點(diǎn)，將有效地提升網(wǎng)絡(luò)性能，降低資源開(kāi)銷(xiāo)。

如前所述，編碼節(jié)點(diǎn)需存儲(chǔ)來(lái)自不同節(jié)點(diǎn)的數(shù)據(jù)，進(jìn)而以相應(yīng)的編碼方式實(shí)現(xiàn)數(shù)據(jù)融合。顯然，相比于普通節(jié)點(diǎn)，編碼節(jié)點(diǎn)的可用資源狀態(tài)至關(guān)重要，因此，節(jié)點(diǎn)可用資源也是編碼節(jié)點(diǎn)選擇過(guò)程中的重要衡量指標(biāo)，其定義如式(11)所示，其中，mi為節(jié)點(diǎn)i的可用緩存，MBi為節(jié)點(diǎn)本地緩存容量。

綜合考慮連通率以及緩存可用率2個(gè)方面的因素，節(jié)點(diǎn)的編碼權(quán)重估計(jì)方法如式(12)所示。

權(quán)重因子滿(mǎn)足式(13)的約束條件

按照上述方法，網(wǎng)絡(luò)中的節(jié)點(diǎn)以分布式的方式估計(jì)自身的編碼權(quán)重。當(dāng)與所歸屬社區(qū)的中心節(jié)點(diǎn)（CN,central node）相遇之后，節(jié)點(diǎn)將編碼權(quán)重?cái)?shù)值估計(jì)結(jié)果發(fā)送給社區(qū)中心節(jié)點(diǎn)，為編碼節(jié)點(diǎn)的動(dòng)態(tài)管理提供依據(jù)。為了使所提出機(jī)制具有較好的可擴(kuò)展性，在充分利用節(jié)點(diǎn)社會(huì)屬性以及可用資源的基礎(chǔ)上，本文采用隨機(jī)線(xiàn)性網(wǎng)絡(luò)編碼方法對(duì)數(shù)據(jù)進(jìn)行融合處理，根據(jù)接收到的數(shù)據(jù)和編碼系數(shù)矩陣，相關(guān)節(jié)點(diǎn)可以完成對(duì)原始數(shù)據(jù)的恢復(fù)。

2.3 動(dòng)態(tài)管理機(jī)制

如前所述，準(zhǔn)確地獲知當(dāng)前網(wǎng)絡(luò)中的節(jié)點(diǎn)狀態(tài)是編碼節(jié)點(diǎn)動(dòng)態(tài)管理機(jī)制的關(guān)鍵。通常，社區(qū)中心節(jié)點(diǎn)在社區(qū)間按一定速率和軌跡進(jìn)行移動(dòng)，且到達(dá)各個(gè)社區(qū)之后隨機(jī)停留一段時(shí)間。此類(lèi)節(jié)點(diǎn)的重要程度較高，其將以較高的概率與各社區(qū)內(nèi)部節(jié)點(diǎn)相遇。在社區(qū)內(nèi)部運(yùn)動(dòng)和停留的時(shí)間段內(nèi)，利用社區(qū)中心節(jié)點(diǎn)的高活躍度可獲得較全面的網(wǎng)絡(luò)狀態(tài)信息，其中包括當(dāng)前社區(qū)節(jié)點(diǎn)數(shù)量、編碼權(quán)重等，將計(jì)算出的節(jié)點(diǎn)權(quán)重值按降序排列，形成編碼節(jié)點(diǎn)備選集合。社區(qū)中心節(jié)點(diǎn)根據(jù)式(9)估計(jì)當(dāng)前網(wǎng)絡(luò)狀態(tài)下的編碼節(jié)點(diǎn)數(shù)量最優(yōu)值，從而在編碼節(jié)點(diǎn)備選集合選取合適數(shù)量的編碼節(jié)點(diǎn)，在社區(qū)編碼節(jié)點(diǎn)列表中保存。中心節(jié)點(diǎn)所需要保存的信息如表1所示。

表1 社區(qū)中心節(jié)點(diǎn)保存的信息

社區(qū)內(nèi)各中心節(jié)點(diǎn)在運(yùn)動(dòng)過(guò)程中不斷感知當(dāng)前網(wǎng)絡(luò)狀態(tài)，并更新信息表中的相關(guān)表項(xiàng)。編碼節(jié)點(diǎn)列表中的相關(guān)信息以權(quán)重值為主要參數(shù)，按照降序進(jìn)行排列，且以標(biāo)志比特Flag表示該節(jié)點(diǎn)在當(dāng)前網(wǎng)絡(luò)狀態(tài)下的工作模式，F(xiàn)lag=1表示節(jié)點(diǎn)當(dāng)前具有編碼功能，F(xiàn)lag=0表示節(jié)點(diǎn)當(dāng)前為普通節(jié)點(diǎn)。

3 數(shù)據(jù)轉(zhuǎn)發(fā)策略

按照所提出的編碼節(jié)點(diǎn)動(dòng)態(tài)管理機(jī)制，中心節(jié)點(diǎn)可根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)以及節(jié)點(diǎn)狀態(tài)確定最優(yōu)編碼節(jié)點(diǎn)數(shù)量，進(jìn)而，利用所選擇的編碼節(jié)點(diǎn)，對(duì)數(shù)據(jù)進(jìn)行融合與轉(zhuǎn)發(fā)處理，可見(jiàn)，為了達(dá)到有效控制開(kāi)銷(xiāo)并可靠傳輸數(shù)據(jù)的目的，數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中的中繼節(jié)點(diǎn)選擇至關(guān)重要。

如前所述，網(wǎng)絡(luò)中的節(jié)點(diǎn)主要包含3種類(lèi)型，分別為普通節(jié)點(diǎn)集合 A={a1,a2,…,an}、社區(qū)中心節(jié)點(diǎn)集合B={b1,b2,…,bn}、編碼節(jié)點(diǎn)集合 C={c1,c2,…,cn}。對(duì)應(yīng)于上述3種類(lèi)型節(jié)點(diǎn)，其攜帶數(shù)據(jù)的轉(zhuǎn)發(fā)策略也需分別進(jìn)行考慮：1)普通數(shù)據(jù)，即普通節(jié)點(diǎn)所攜帶的數(shù)據(jù)；2)編碼融合數(shù)據(jù)，即編碼節(jié)點(diǎn)所攜帶的數(shù)據(jù)；3)切換數(shù)據(jù)，即節(jié)點(diǎn)在當(dāng)前時(shí)刻具有編碼功能，下一時(shí)刻為普通節(jié)點(diǎn)，依然滯留在緩存中的未完成傳輸?shù)木幋a融合數(shù)據(jù)。在社區(qū)中心節(jié)點(diǎn)完成編碼節(jié)點(diǎn)的選取后，普通節(jié)點(diǎn)集合A完成對(duì)普通數(shù)據(jù)的轉(zhuǎn)發(fā)，編碼節(jié)點(diǎn)集合C完成對(duì)收發(fā)數(shù)據(jù)處理和已編碼數(shù)據(jù)的轉(zhuǎn)發(fā)，當(dāng)集合C中部分元素轉(zhuǎn)換到A集合中時(shí)，完成特殊數(shù)據(jù)的轉(zhuǎn)發(fā)，具體轉(zhuǎn)發(fā)步驟如下。

步驟1 更新時(shí)間tupdate內(nèi)，依式（12）所示編碼節(jié)點(diǎn)選取標(biāo)準(zhǔn)，按編碼節(jié)點(diǎn)權(quán)重值iω對(duì)各社區(qū)內(nèi)節(jié)點(diǎn)進(jìn)行排序，構(gòu)建編碼節(jié)點(diǎn)備選集合，同時(shí)根據(jù)社區(qū)中心節(jié)點(diǎn)所獲知的節(jié)點(diǎn)數(shù)量，按式（9）的最優(yōu)編碼節(jié)點(diǎn)數(shù)量原則，選擇備選集合中權(quán)重較大的節(jié)點(diǎn)作為編碼節(jié)點(diǎn)。

步驟2 普通數(shù)據(jù)轉(zhuǎn)發(fā)：若普通節(jié)點(diǎn)ai所攜帶數(shù)據(jù) Mi為原始數(shù)據(jù)，且DgroupId≠ai_groupId，則表明原始數(shù)據(jù)Mi的目的節(jié)點(diǎn)所屬社區(qū)不在當(dāng)前社區(qū)，那么當(dāng)ai在下一時(shí)刻相遇的節(jié)點(diǎn)屬于集合 C={c1,c2,… cn}，則將 Mi轉(zhuǎn)發(fā)給該節(jié)點(diǎn)；若 DgroupId=ai_groupId，則表明原始數(shù)據(jù)已到達(dá)目的節(jié)點(diǎn)所屬社區(qū)，為達(dá)到減小延時(shí)同時(shí)充分利用網(wǎng)絡(luò)資源的目的，該數(shù)據(jù)在本社區(qū)內(nèi)進(jìn)行快速轉(zhuǎn)發(fā)，其中，DgroupId為Mi的目的節(jié)點(diǎn)所屬社區(qū)Id，ai_groupId為ai所屬社區(qū)Id。

步驟3 融合數(shù)據(jù)轉(zhuǎn)發(fā)：按目的節(jié)點(diǎn)所屬社區(qū)的groupId，編碼節(jié)點(diǎn)ci將接收到的Mi進(jìn)行編碼。若在下一時(shí)刻遇到社區(qū)標(biāo)識(shí)groupId相同的編碼節(jié)點(diǎn)ci’，即編碼融合數(shù)據(jù)到達(dá)目的社區(qū)時(shí)，則將該編碼融合數(shù)據(jù)轉(zhuǎn)發(fā)。若ci’存儲(chǔ)足夠數(shù)量的編碼數(shù)據(jù)后就將該批數(shù)據(jù)解碼，然后在本社區(qū)內(nèi)洪泛，直到解碼后數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)。

步驟4 切換數(shù)據(jù)轉(zhuǎn)發(fā)：網(wǎng)絡(luò)狀態(tài)的變化將可能導(dǎo)致部分編碼節(jié)點(diǎn)喪失編碼功能，但編碼融合數(shù)據(jù)依然在節(jié)點(diǎn)本地緩存。當(dāng)狀態(tài)轉(zhuǎn)換的節(jié)點(diǎn)遇到新的編碼節(jié)點(diǎn)之后，優(yōu)先轉(zhuǎn)發(fā)已編碼數(shù)據(jù)，然后再執(zhí)行普通節(jié)點(diǎn)的功能。

步驟5 各節(jié)點(diǎn)依次重復(fù)上述步驟，直至全部數(shù)據(jù)完成轉(zhuǎn)發(fā)。

圖1為所提出機(jī)制的流程，其中，n為社區(qū)節(jié)點(diǎn)數(shù)量，隨著網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)之間的狀態(tài)信息交互，ni和Ncoding的數(shù)值以動(dòng)態(tài)的方式完成更新。

圖1 DMCN機(jī)制流程

4 數(shù)值結(jié)果分析

本部分采用 ONE(opportunistic network environment)仿真平臺(tái)[15]驗(yàn)證所提出機(jī)制的有效性，并與其他經(jīng)典數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制在生存時(shí)間和緩存有限的條件下進(jìn)行比較，其中，性能指標(biāo)包括成功投遞率、平均延時(shí)和路由開(kāi)銷(xiāo) 3個(gè)方面，具體仿真場(chǎng)景的參數(shù)設(shè)置如表2所示。本文選取 α1=0.65、α2=0.35、β=0.3。

此處的α1與α2是編碼節(jié)點(diǎn)選取的影響因子，β是最優(yōu)化編碼節(jié)點(diǎn)數(shù)量的影響因子，本文應(yīng)用的網(wǎng)絡(luò)模型是社區(qū)環(huán)境，如前所述，根據(jù)社區(qū)模型的節(jié)點(diǎn)移動(dòng)特性，在編碼節(jié)點(diǎn)選取時(shí)節(jié)點(diǎn)連通性的重要程度較大，因此對(duì)網(wǎng)絡(luò)性能要求不同的場(chǎng)景下，需根據(jù)節(jié)點(diǎn)活躍程度及自身能耗這兩方面設(shè)定α1與α2的取值。參數(shù)β值的選取是NP完全問(wèn)題，按照本文給出的推導(dǎo)證明過(guò)程，β值的選取受當(dāng)前時(shí)刻網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的影響。在社區(qū)模型下，節(jié)點(diǎn)自由出入各個(gè)社區(qū)，那么根據(jù)一定時(shí)間內(nèi)各社區(qū)節(jié)點(diǎn)數(shù)量變化情況，本文經(jīng)過(guò)多次仿真后最終設(shè)定。因此針對(duì)不同網(wǎng)絡(luò)場(chǎng)景，需依據(jù)網(wǎng)絡(luò)的實(shí)時(shí)情況來(lái)選取理想的β值。

4.1 不同生存時(shí)間下網(wǎng)絡(luò)性能

為了更加全面地分析所提出機(jī)制的有效性，本文所選取的比較對(duì)象分別為基于洪泛的 Epidemic機(jī)制[10]、基于連接預(yù)測(cè)的Prophet機(jī)制[16]以及前面提到的RLC機(jī)制[8]（假設(shè)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)均為編碼節(jié)點(diǎn)）。各種機(jī)制在不同生存時(shí)間（TTL,time to live）下的性能如圖2～圖4所示。

表2 仿真參數(shù)設(shè)置

網(wǎng)絡(luò)負(fù)載率直觀(guān)地反映了數(shù)據(jù)傳輸過(guò)程所消耗的網(wǎng)絡(luò)資源，圖2描述了4種機(jī)制的網(wǎng)絡(luò)負(fù)載率隨TTL的變化情況，可見(jiàn)，網(wǎng)絡(luò)負(fù)載率隨TTL值的增加呈上升趨勢(shì)，其主要原因在于間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)中已成功投遞的數(shù)據(jù)副本依然占用網(wǎng)絡(luò)中的資源。數(shù)據(jù)在網(wǎng)絡(luò)中生存時(shí)間的增加將導(dǎo)致新生成數(shù)據(jù)的可用緩存減少，節(jié)點(diǎn)相遇機(jī)會(huì)無(wú)法充分利用，數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程的負(fù)載率也相應(yīng)增加。DMCN機(jī)制將數(shù)據(jù)分批編碼融合，在選定的編碼節(jié)點(diǎn)間傳遞，減少了不必要的數(shù)據(jù)轉(zhuǎn)發(fā)操作，有效地降低了負(fù)載率。從結(jié)果中可知，DMCN的負(fù)載率一直維持在40～60的較低范圍內(nèi)，且較之于其他3種機(jī)制負(fù)載率分別降低了59.6%、56.8%和64.5%。

圖2 不同TTL下的網(wǎng)絡(luò)負(fù)載率

成功投遞率是衡量數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制的重要指標(biāo)之一。圖3的結(jié)果表明，隨著TTL值的增加，4種機(jī)制的成功投遞率均呈現(xiàn)出逐漸下降的趨勢(shì)。所提出的DMCN機(jī)制成功投遞率始終在75%以上，性能較Epidemic提升8%，較Prophet提升17%，較RLC提高25%。其主要原因在于DMCN機(jī)制采用編碼節(jié)點(diǎn)動(dòng)態(tài)管理機(jī)制，根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)使各社區(qū)始終保持最優(yōu)的編碼節(jié)點(diǎn)數(shù)量，同時(shí)有效地控制了編碼系數(shù)矩陣的大小，即只對(duì)相同目的社區(qū)的數(shù)據(jù)進(jìn)行融合，使得有限的網(wǎng)絡(luò)資源得到了充分利用。

圖3 不同TTL下的成功投遞率

從圖4可以看出，在生存時(shí)間小于220 min的情況下，本文所提出的 DMCN機(jī)制具有較低的傳輸延時(shí)，但此后其傳輸延時(shí)處于中等水平。其主要原因在于，編碼節(jié)點(diǎn)數(shù)量的動(dòng)態(tài)管理過(guò)程需要較多的統(tǒng)計(jì)和估算操作，且當(dāng)編碼節(jié)點(diǎn)變成普通節(jié)點(diǎn)時(shí)，所緩存的數(shù)據(jù)需要重新進(jìn)行處理，需要耗費(fèi)較多的時(shí)間。

圖4 不同TTL下的平均傳輸延時(shí)

4.2 不同緩存下網(wǎng)絡(luò)性能

圖5～圖7描述了不同緩存狀態(tài)下，各種數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制的性能，其中主要包括負(fù)載率、投遞率和傳輸延時(shí)等3個(gè)方面。

圖5 不同緩存下的負(fù)載率

圖6 不同緩存下的成功投遞率

圖7 不同緩存下的平均傳輸延時(shí)

從圖5可知，節(jié)點(diǎn)緩存容量對(duì)負(fù)載率影響較大，隨著緩存容量的增加，各種機(jī)制的負(fù)載率均呈現(xiàn)出明顯的下降趨勢(shì)。顯然，從圖中可以看出 DMCN仍然保持在40～60較低的范圍內(nèi)，與其他3種機(jī)制相比，分別降低了66.3%、34.9%和62.8%。這是因?yàn)镈MCN機(jī)制有效地控制了編碼節(jié)點(diǎn)數(shù)量，進(jìn)而限定融合數(shù)據(jù)在編碼節(jié)點(diǎn)之間進(jìn)行傳遞，此種方式有效地控制了數(shù)據(jù)傳輸過(guò)程的轉(zhuǎn)發(fā)次數(shù)，同時(shí)在中繼節(jié)點(diǎn)選擇過(guò)程中充分地考慮了節(jié)點(diǎn)之間的社會(huì)屬性，使得數(shù)據(jù)能夠以較大的概率到達(dá)目的節(jié)點(diǎn)所屬社區(qū)，減少了數(shù)據(jù)在社區(qū)間的轉(zhuǎn)發(fā)，有效地增強(qiáng)了數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程的針對(duì)性。

不同數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制的投遞率性能如圖6所示，隨著節(jié)點(diǎn)緩存容量的逐漸增加，4種機(jī)制的數(shù)據(jù)成功投遞率也隨之上升。但由于 DMCN機(jī)制所需要存儲(chǔ)的狀態(tài)信息多于其他三者，因此，在緩存小于9 MB時(shí)，其成功投遞率略低，隨著緩存的進(jìn)一步增加，DMCN機(jī)制性能趨于穩(wěn)定并優(yōu)于其他3種機(jī)制，較其他 3種機(jī)制性能分別提升 7%、10%和22.3%。DMCN機(jī)制通過(guò)對(duì)編碼節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)管理，以確定所需編碼節(jié)點(diǎn)及其數(shù)量，同時(shí)，節(jié)點(diǎn)按照本文所提出的規(guī)則對(duì)數(shù)據(jù)分類(lèi)處理，編碼融合數(shù)據(jù)只在編碼節(jié)點(diǎn)間傳輸，部分普通數(shù)據(jù)在社區(qū)內(nèi)快速轉(zhuǎn)發(fā)，數(shù)據(jù)在轉(zhuǎn)發(fā)過(guò)程中的協(xié)作節(jié)點(diǎn)選擇更具有針對(duì)性，有效地提升了數(shù)據(jù)投遞率。

圖7描述了各種機(jī)制的延時(shí)性能。在緩存較小時(shí)，DMCN機(jī)制維持了較低的延時(shí)，但當(dāng)緩存大于11 MB時(shí)，數(shù)據(jù)傳輸延時(shí)也隨之增加。與不同TTL場(chǎng)景下的延時(shí)性能類(lèi)似，DMCN中的編碼節(jié)點(diǎn)需要對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)、編碼和解碼等相關(guān)操作，處理時(shí)間隨數(shù)據(jù)量的增加而逐漸上升；此外，編碼融合數(shù)據(jù)的轉(zhuǎn)發(fā)過(guò)程需要耗費(fèi)時(shí)間等待合適的中繼節(jié)點(diǎn)，上述2個(gè)方面因素均直接導(dǎo)致了傳輸延時(shí)的增加。

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

為了充分利用有限的網(wǎng)絡(luò)資源，本文提出了一種最優(yōu)編碼節(jié)點(diǎn)數(shù)量計(jì)算方法，進(jìn)而設(shè)計(jì)了編碼節(jié)點(diǎn)動(dòng)態(tài)管理的間斷連接無(wú)線(xiàn)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制。充分利用節(jié)點(diǎn)之間的社會(huì)屬性，節(jié)點(diǎn)分布式地獲知當(dāng)前網(wǎng)絡(luò)狀態(tài)，并動(dòng)態(tài)地調(diào)整編碼節(jié)點(diǎn)的數(shù)量，進(jìn)而對(duì)數(shù)據(jù)進(jìn)行分批編碼融合。與傳統(tǒng)的機(jī)制相比，所提出的機(jī)制不僅減少了網(wǎng)絡(luò)資源開(kāi)銷(xiāo)，同時(shí)，有效地提高了數(shù)據(jù)傳輸過(guò)程中的可靠性，改善了網(wǎng)絡(luò)資源利用率。

[1]THRASYVOULOS S,RAO N,BIN R,et al. Routing for disruption tolerant networks: taxonomy and design[J]. Wireless Network,2010,(16):2349-2370.

[2]蘇金樹(shù),胡喬林,趙寶康. 容延容斷網(wǎng)絡(luò)路由技術(shù)[J]. 軟件學(xué)報(bào),2010,21(1):120-124.SU J S,HU Q L,ZHAO B K. Routing techniques on delay/disruption tolerant networks[J]. Journal of Software,2010,21(1): 120-124.

[3]TRACEY H,DESMOND S L. Network Coding: an Introduction[M].Cambridge University Press,2007.

[4]KATTI S,RAHUL H,HU W,et al. XORs in the air: practical wireless network coding[J]. Proceedings of ACM SIGCOMM,2006,36(4):497-510.

[5]鄧文君,楊真,楊震. 一種新的無(wú)線(xiàn)mesh網(wǎng)絡(luò)編碼算法[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,22(2): 156-158.DENG W J,YANG Z,YANG Z. A new algorithm for wireless mesh networks coding[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2010,22(2): 156-158.

[6]WANG Y,JAIN S,MARTONOSI M,et al. Erasure coding based routing for opportunistic networks[A]. Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN)[C]. Philadelphia,USA,2005. 229-236.

[7]LING C,CHEN Y. A hybrid routing approach for opportunistic networks[A]. Proceedings of the SIGCOMM Workshop on Challenged networks [C]. Pisa,Italy,2006. 213-220.

[8]ZHANG X L,NEGLIA G,KUROSE J,et al. On the benefits of random linear coding for unicast applications in disruption tolerant networks[A]. Proceedings of the 4th Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks[C]. Boston,MA,2006. 1-7.

[9]YUNFENG L,BAOCHUN L,BEN L,et al. Efficient network coded data transmissions in disruption tolerant networks[A]. The 27th Conference on Computer Communications[C]. Phoenix AZ,2008. 1508-1516.

[10]YUNFENG L,BAOCHUN L,BEN L,et al. Stochastic analysis of network coding in epidemic routing[J]. IEEE Selected Areas in Communications,2008,26(5): 794-808.

[11]PAN H,JON C,EIKO Y. BUBBLE Rap: socail-based forwarding in delay tolerant networks[A]. The ACM International Symposium on Mobile Ad Hoc Networking and Computing[C]. Hong Kong,China,2008. 241-250.

[12]SHABBIR A,SALIL S,KANHERE,et al. HUBCODE: hub-based forwarding using network coding in delay tolerant networks[A]. Proceedings of the 12th ACM International Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems[C]. Tenerife Canary Islands,Spain,2009. 288-296.

[13]JINGYAO Z,PINGYI F,BEN L. Network coding for efficient multicast routing in wireless ad-hoc networks[J]. IEEE Transactions on Communications,2008,56(4):598-607.

[14]HUI P,CHAINTREAU A,SCOTT J,et al. Packet switched networks and human mobility in conference environments[A]. Proceedings of the 2005 ACM SIGCOMM Workshop on Delay Tolerant Networking[C]. Philadelphia,USA,2005.244-251.

[15]KER?NEN A,OTT J,K?RKK?INEN T. The ONE simulator for DTN protocol evaluation[A]. The 2nd International Conference on Simulation Tools and Techniques[C]. Rome,Italy,2009. 1-10.

[16]JINGFENG X,JIANSHENG L,YUANDA C,et al. Advanced PROPHET routing in delay tolerant network[A]. International Conference on Communication Software and Networks[C]. Macau,China,2009. 411 - 413.