映射－編碼－分發(fā)構(gòu)架在DTN中的應(yīng)用*

錢景輝，謝開源

（南京工業(yè)大學(xué)，江蘇 南京 211816）

0 引言

機(jī)會網(wǎng)絡(luò)是延遲容忍網(wǎng)絡(luò)（delay tolerant networks，DTN）中的一個(gè)重要的分支［1］，在DTN中通信時(shí)間是隨機(jī)而且未知的，幾個(gè)典型的應(yīng)用如SMANETs（sparse mobile Ad-Hoc networks），ZebraNet［2］，UWSNs（underwater sensor networks）［3］，PSNs（pocket switched networks）［4］等。它們在無線范圍限制下可能并不存在一條終端到終端的路徑，在這樣的網(wǎng)絡(luò)環(huán)境下路由變得很困難，而當(dāng)今流行的無線通信機(jī)制在這些網(wǎng)絡(luò)中無法確保網(wǎng)絡(luò)的連接。現(xiàn)有方案旨在解決特定的機(jī)會網(wǎng)絡(luò)環(huán)境下的路由問題。

本文提出一種新的映射—編碼—分發(fā)（MCR）機(jī)會網(wǎng)絡(luò)構(gòu)架，將機(jī)會網(wǎng)絡(luò)傳輸分成上層網(wǎng)絡(luò)與下層網(wǎng)絡(luò)來簡化移動模型，并將網(wǎng)絡(luò)編碼引入機(jī)會網(wǎng)絡(luò)之中，保持網(wǎng)絡(luò)負(fù)載基本不變的情況下可以大幅提高網(wǎng)絡(luò)傳輸效率;同時(shí)，整合網(wǎng)絡(luò)傳輸算法，在缺乏網(wǎng)絡(luò)全局拓?fù)浣Y(jié)構(gòu)和全局信息的情況下能夠依據(jù)帶寬、存儲等限制有效傳輸信息。

1 相關(guān)理論

本文的工作同時(shí)涉及機(jī)會網(wǎng)絡(luò)傳輸構(gòu)架、網(wǎng)絡(luò)編碼以及機(jī)會網(wǎng)絡(luò)傳輸。

1．1 機(jī)會傳輸

根據(jù)機(jī)會網(wǎng)絡(luò)傳輸所使用的機(jī)制，可以將網(wǎng)絡(luò)傳輸分為兩大類:基于復(fù)制分發(fā)［5～7］和基于編碼［8］。

基于復(fù)制分發(fā)的方案在已有的方案中應(yīng)用非常廣泛。它的基本思路是將多個(gè)可識別的數(shù)據(jù)副本注入網(wǎng)絡(luò)之中，然后依靠節(jié)點(diǎn)的移動將數(shù)據(jù)傳輸至目的地。若信息成功傳輸，目標(biāo)至少需要收到一份數(shù)據(jù)副本。在網(wǎng)絡(luò)非常大的情況下，基于復(fù)制的方案可以獲得較好的網(wǎng)絡(luò)延遲特性，然而這些方案的主要不足便是造成數(shù)據(jù)阻塞。當(dāng)網(wǎng)絡(luò)資源有限的時(shí)候（比如:緩存、網(wǎng)絡(luò)帶寬），基于復(fù)制分發(fā)的方案會明顯地降低性能（比如傳輸率）。

基于編碼的方案其基本思路是將單個(gè)數(shù)據(jù)格式化成k個(gè)子數(shù)據(jù)包進(jìn)行傳輸。與基于復(fù)制分發(fā)的方案不同的是，當(dāng)目標(biāo)收集到k+ε個(gè)子數(shù)據(jù)包時(shí)便可以重建原始信息。在網(wǎng)絡(luò)極其差的情況下，基于編碼的方案比基于復(fù)制分發(fā)的方案更加健全。然而，當(dāng)網(wǎng)絡(luò)連接非常好時(shí)，基于編碼的方案表現(xiàn)并不盡人意，這主要是收集附加的子數(shù)據(jù)包造成的。

然而，機(jī)會網(wǎng)絡(luò)中成功的路由技術(shù)必須同時(shí)考慮到性能與可靠性。一個(gè)有效的路由方案需要同時(shí)適應(yīng)最差與最好延遲性能情況。

1．2 網(wǎng)絡(luò)編碼

當(dāng)數(shù)據(jù)包提升了節(jié)點(diǎn)中組的級別時(shí)，認(rèn)為節(jié)點(diǎn)收到了一個(gè)新數(shù)據(jù)包。數(shù)據(jù)傳輸算法中，會根據(jù)一些參數(shù)在決定哪些包需要被發(fā)送，哪些包需要被丟棄。在緩存有限的情況下，需要討論怎樣才能有效地進(jìn)行網(wǎng)絡(luò)編碼和高效率的解碼。在MCR構(gòu)架中本文提出了一種維護(hù)算法，這將有助于減少重復(fù)編碼信息，在移除舊信息的同時(shí)仍然具有很高的可解碼性。

1．3 傳輸機(jī)制

網(wǎng)絡(luò)傳輸中，本文使用一種考慮資源分配的傳輸算法—RAPID（resource allocation protocolforintentional DTN）［7］。

算法考慮了資源的限制、路由方案以及移動特性等。許多算法只考慮了節(jié)點(diǎn)存儲的限制，然而對傳輸帶寬卻沒有限制，比如:PRoPHET［6］等。當(dāng)網(wǎng)絡(luò)通信傳輸時(shí)所傳輸數(shù)據(jù)允許比節(jié)點(diǎn)存儲的數(shù)據(jù)還要多時(shí)，上述這種情況才可能發(fā)生。然而在目前存儲比較便宜且能源充足的情況下這種情況并不常見。數(shù)據(jù)顯示高比特率傳輸將比能源和存儲貴得多。

在每個(gè)機(jī)會傳遞時(shí)，算法將路由環(huán)境解釋為每個(gè)數(shù)據(jù)包的效用參數(shù)并不斷通過控制頻道（control channel）來同步全局網(wǎng)絡(luò)狀態(tài)的局部視圖。算法通過內(nèi)置的控制頻道使用小部分傳輸帶寬來交換節(jié)點(diǎn)之間的網(wǎng)絡(luò)狀態(tài)，如數(shù)據(jù)包副本的位置數(shù)量、過往的平均傳輸量等附加元數(shù)據(jù)（metadata）。雖然這些信息是有延遲的和不準(zhǔn)確的，但這些信息在傳輸中對性能的提高卻起到了非常重要的作用。

2 MCR構(gòu)架

2．1 概 述

本文采用了一種新的構(gòu)架，將網(wǎng)絡(luò)層分為上下兩層。上層主要負(fù)責(zé)選取最優(yōu)路徑，而下層則專注于機(jī)會傳輸。

MCR構(gòu)架相對于單純的編碼和復(fù)制分發(fā)策略優(yōu)勢在于:

1）整合編碼與分發(fā)，集合了編碼低丟包率和復(fù)制分發(fā)策略對網(wǎng)絡(luò)資源的控制的特點(diǎn);

2）對于上層網(wǎng)絡(luò)是透明的，避免了純粹的機(jī)會傳輸所造成的資源浪費(fèi)和性能下降;

3）在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變時(shí)，MCR只需要調(diào)整對應(yīng)的部分，而不需要對整個(gè)構(gòu)架進(jìn)行重新設(shè)計(jì)。

MCR構(gòu)架主要作用在以下幾方面:1）選擇上層網(wǎng)絡(luò)基站構(gòu)成最優(yōu)傳輸路徑;2）將上層網(wǎng)絡(luò)路徑映射到一條或多條物理傳輸路徑上;3）整合網(wǎng)絡(luò)編碼與機(jī)會傳輸，依據(jù)物理傳輸路徑的帶寬、容量等限制配合編碼將數(shù)據(jù)包以最優(yōu)化的方式傳遞給目標(biāo)節(jié)點(diǎn)。MCR構(gòu)架如圖1所示。

圖1 MCR構(gòu)架Fig 1 MCR framework

2．2 上層網(wǎng)絡(luò):路徑選擇與映射

在上層網(wǎng)絡(luò)中由于不需要考慮丟包率，算法可以對網(wǎng)絡(luò)狀態(tài)有很好的認(rèn)識。在以下理論中，設(shè)區(qū)域內(nèi)存在零散的與廣域網(wǎng)相通的固定基站。這些基站是互相連通的，可以通過廣域網(wǎng)無限制地互相傳遞信息。為了區(qū)別于現(xiàn)有蜂窩網(wǎng)絡(luò)，區(qū)域內(nèi)所有基站并不能將整個(gè)區(qū)域覆蓋，相反只能覆蓋很小一部分的區(qū)域。

如圖2，有兩塊區(qū)域P1和P2，A，B，C，D為與廣域網(wǎng)相連的固定基站，a，b，c，d，e為移動節(jié)點(diǎn)。在某一時(shí)刻，假設(shè)a，b，c在P1區(qū)域內(nèi)活動，d，e在P2區(qū)域內(nèi)活動。若a想要傳遞信息給d，上層網(wǎng)絡(luò)首先獲取到d的路徑，在本例中最優(yōu)路徑為a→B→C→d。然后算法將路徑映射到下層網(wǎng)絡(luò)中，并使用機(jī)會傳輸將信息編碼傳送至目標(biāo)（節(jié)點(diǎn)a和基站B之間可能不存在完整的路徑，機(jī)會傳輸便利用a和B之間的其他移動節(jié)點(diǎn)，這里為b，將信息編碼后傳遞過去）。

圖2 上層信息傳輸Fig 2 Upper layer information transmission

上層網(wǎng)絡(luò)的作用在于:

1）選擇一條只包含途經(jīng)的固定基站的從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑。

2）將路徑映射到下層網(wǎng)絡(luò)以便下層網(wǎng)絡(luò)能有效地執(zhí)行機(jī)會傳輸。

上層網(wǎng)絡(luò)的路徑選擇能夠大大地簡化機(jī)會傳輸時(shí)的移動模型，并提高傳輸效率。例如:社交模型中，人們會在不同的子區(qū)域內(nèi)停留聚集，整個(gè)移動模型十分復(fù)雜。在本文中，社交模型可以按照聚集場所劃分為若干個(gè)子區(qū)域，而子區(qū)域中便可以使用簡單得多的移動模型替代原有模型。信息在子區(qū)域內(nèi)通過機(jī)會傳輸傳送至基站;基站通過廣域網(wǎng)與目標(biāo)區(qū)域的基站通信;目標(biāo)基站再將信息再次通過機(jī)會傳輸在目標(biāo)子區(qū)域內(nèi)傳遞，直到達(dá)到目標(biāo)。

2．3 下層網(wǎng)絡(luò):網(wǎng)絡(luò)編碼

在下層網(wǎng)絡(luò)中，為了能減少丟包率，首先將信息進(jìn)行編碼。

設(shè)V為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，S為數(shù)據(jù)源節(jié)點(diǎn)數(shù)，S?V，m=|S|。設(shè)每個(gè)節(jié)點(diǎn)v∈V在物理層有鄰居節(jié)點(diǎn)N（v），設(shè)xi是源節(jié)點(diǎn)si（i=1，…，m）產(chǎn)生的信息向量，每個(gè)向量值都在限定的域F2k中。為了使編碼更具效率，這里設(shè)域?yàn)镕28，這樣所涉及的加法和乘法可以使用xor和2個(gè)255字節(jié)的查找表來解決。每一個(gè)信息向量xi都與一個(gè)系數(shù)相關(guān)，此處簡記做ei。設(shè)M=|xi|為xi中所包含的信息數(shù)，信息向量總是與編碼向量同時(shí)發(fā)送出。節(jié)點(diǎn)v在矩陣Gv中保存了接收到的信息向量和解碼向量，新接收到的向量會被添加到矩陣中。對于節(jié)點(diǎn)中已經(jīng)存在的信息則不會再次添加進(jìn)去。矩陣Gv通過高斯消去法可以持續(xù)的減少矩陣的階數(shù)，當(dāng)矩陣存在一行為（ei，xi）的時(shí)候節(jié)點(diǎn)便可以解碼出原信息xi。因此，要解碼源信息，至少需要m個(gè)獨(dú)立的信息。

2．4 下層網(wǎng)絡(luò):機(jī)會傳輸

本文中使用的機(jī)會傳輸算法為RAPID，它基于效用的機(jī)制來解決資源分配的問題。數(shù)據(jù)包將被復(fù)制分發(fā)直到達(dá)到目標(biāo)。算法的關(guān)鍵在于在給定帶寬和存儲下優(yōu)化數(shù)據(jù)包的分發(fā)。假設(shè)路由需要實(shí)現(xiàn)最小平均延遲，設(shè)Ui為發(fā)送數(shù)據(jù)包i的理想時(shí)間的負(fù)值。設(shè)δUi為發(fā)送數(shù)據(jù)包i時(shí)Ui的增加量，si為i的大小。RAPID會分發(fā)緩存中δUi/si最高的數(shù)據(jù)包，換言之，算法將發(fā)送最小效用的數(shù)據(jù)包。RAPID在分發(fā)中同樣考慮到了存儲的限制，若節(jié)點(diǎn)耗盡了所有存儲容量，則最低效用的數(shù)據(jù)包將會被刪除。然而，源節(jié)點(diǎn)在收到通知前不會刪除其自己的消息。

本文前面講到，節(jié)點(diǎn)的信息傳遞效率將從全局系統(tǒng)狀態(tài)信息中獲益。為實(shí)現(xiàn)這個(gè)目標(biāo)，RAPID利用少量的帶寬散布全局系統(tǒng)狀態(tài)信息。其使用內(nèi)置的控制頻道在每次機(jī)會傳輸時(shí)交換數(shù)據(jù)包信息和包含過去所有交換記錄的元數(shù)據(jù)信息。

RAPID在相遇節(jié)點(diǎn)時(shí)交換以下信息:

1）過去的平均機(jī)會傳輸次數(shù);

2）節(jié)點(diǎn)相遇期望時(shí)間;

3）過去所發(fā)送的全部消息列表;

4）對于每個(gè)自己的數(shù)據(jù)包，期望估計(jì)時(shí)間將根據(jù)目前緩存中的狀態(tài)來計(jì)算;

5）其他節(jié)點(diǎn)在上次相遇后改變的信息。

當(dāng)算法使用控制頻道時(shí)，對于全局系統(tǒng)狀態(tài)也只是一個(gè)概覽。這些狀態(tài)在節(jié)點(diǎn)運(yùn)動時(shí)可能改變或延遲，即使這些消息不是很精確，但依舊可以給算法帶來性能的提高，而元數(shù)據(jù)本身的負(fù)載卻很少。

2．5 舊信息維護(hù)

當(dāng)節(jié)點(diǎn)解碼信息后，整個(gè)矩陣中的信息對于該節(jié)點(diǎn)就不再有用了，但是對于其他節(jié)點(diǎn)，這些信息可能依舊會在解碼時(shí)使用到。節(jié)點(diǎn)需要保存矩陣中的信息，然而卻不需要保存整個(gè)矩陣。在存儲容量有限的情況下，節(jié)點(diǎn)可以減少已經(jīng)解碼的矩陣的階數(shù)。例如:可以將第rn－1行和第rn行線性相加得到一個(gè)新行rn－1。這種方式不會減少解碼的幾率，只要重要的向量至少存在一個(gè)，那么，新節(jié)點(diǎn)將仍然可以解碼出所有的數(shù)據(jù)。

3 仿真與評估

在上文中已經(jīng)提到，MCR構(gòu)架將整個(gè)DTN劃分成若干個(gè)子區(qū)域，而每個(gè)子區(qū)域內(nèi)的節(jié)點(diǎn)移動模型將比整個(gè)區(qū)域的模型簡單得多。如何在上層網(wǎng)絡(luò)中選取合適的最優(yōu)路徑已經(jīng)不屬于DTN機(jī)會傳輸?shù)姆懂?，下文的仿真將針對機(jī)會網(wǎng)絡(luò)來進(jìn)行。

在網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)之間的相遇是未知的。本文將MCR 與 RAPID，PRoPHET，Spray and Wait，Epidemic 進(jìn)行了對比，同時(shí)展示了網(wǎng)絡(luò)編碼對數(shù)據(jù)的影響。在所有仿真中，都使用了RAPID的內(nèi)置控制頻道來傳輸元數(shù)據(jù)。

Epidemic隨機(jī)地向節(jié)點(diǎn)分發(fā)數(shù)據(jù);Spray and Wait限制了分發(fā)數(shù)L，其中，L由網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)計(jì)算而得［5］，在仿真中使用了binary Spray and Wait，同時(shí)設(shè)L為12;在 PRoPHET中Pinit=0．75，β =0．25，γ =0．98;MCR（1）中沒有冗余，即源節(jié)點(diǎn)產(chǎn)生的線性和個(gè)數(shù)m與數(shù)據(jù)包個(gè)數(shù)n相同，MCR（2）中有20%的冗余編碼，即m=1．2n;全局消息 TTL（time to live）為 1800 s。

仿真實(shí)驗(yàn)證明，MCR的表現(xiàn)比 RAPID，PRoPHET，Spray and Wait和Epidemic都要好。當(dāng)消息產(chǎn)生速率相同時(shí)，Epidemic的網(wǎng)絡(luò)負(fù)載已經(jīng)接近MCR的2倍。

從表1可以看出:MCR在傳輸率、平均延遲、平均緩沖時(shí)間等方面與其他算法比較都有著很大優(yōu)勢。算法的傳輸比率=傳輸成功數(shù)/消息數(shù)，而MCR由于使用了網(wǎng)絡(luò)編碼，因此，在解碼過程中會有一些消息無法解碼。在數(shù)據(jù)中看出:雖然有消息無法被解出，但傳輸比率依舊比其他算法要高。

表1 各算法性能Tab 1 Performances of different algorithms

圖3為元數(shù)據(jù)在帶寬中占有不同百分比的情況下對傳輸性能的影響。數(shù)據(jù)顯示，隨著限制的放寬，傳輸性能也在不斷提高。當(dāng)對元數(shù)據(jù)不加限制時(shí)，算法可以得到最佳的性能。在有元數(shù)據(jù)的情況下MCR可以得到約20%的提升。

圖4中為互補(bǔ)累計(jì)分布函數(shù)（CCDF）曲線，顯示的是網(wǎng)絡(luò)編碼對傳輸性能的影響。從圖中看出在TTL為1800時(shí)，沒有網(wǎng)絡(luò)編碼的情況下的丟包率約為25%，而在無冗余網(wǎng)絡(luò)編碼參與時(shí)丟包率約為29%。本文對原始數(shù)據(jù)經(jīng)行編碼時(shí)引入20%的冗余，即矩陣Gv大小增加20%，表1與圖4中MCR（1）為沒有冗余時(shí)的數(shù)據(jù)，MCR（2）為添加冗余后的數(shù)據(jù)。從對比看出:雖然網(wǎng)絡(luò)負(fù)載與平均延遲有所增加（網(wǎng)絡(luò)負(fù)載增加3．6%，平均延遲增加56 s），但在TTL不變的情況下丟包率已經(jīng)降低到21%，比無網(wǎng)絡(luò)編碼時(shí)高出4%。

綜上，MCR在沒有冗余數(shù)據(jù)時(shí)，無編碼MCR比有編碼MCR性能要好，而當(dāng)引入少量冗余后有編碼MCR的表現(xiàn)比無編碼MCR要好。在現(xiàn)實(shí)環(huán)境中，增加少量的網(wǎng)絡(luò)帶寬來換取更少的丟包率是完全可行的。

圖3 控制頻道對性能的影響Fig 3 Effect of control channel on character

4 結(jié)論

機(jī)會網(wǎng)絡(luò)是一個(gè)新興的研究領(lǐng)域。在機(jī)會網(wǎng)絡(luò)中傳輸有別于傳統(tǒng)的網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中可能并不存在一條完整的傳輸路徑，因此，節(jié)點(diǎn)的移動在傳輸中起到了至關(guān)重要的作用。目前，已有的一些機(jī)會網(wǎng)絡(luò)傳輸策略僅在特定的環(huán)境下有很好的效果，而在多變的現(xiàn)實(shí)環(huán)境中并不適用。本文提出了一種新的機(jī)會傳輸構(gòu)架，它簡化了移動模型，完善了對網(wǎng)絡(luò)資源的控制，在整合現(xiàn)有策略的基礎(chǔ)上能夠適應(yīng)多變的現(xiàn)實(shí)環(huán)境并保持很高的傳輸效率。

圖4 網(wǎng)絡(luò)編碼對性能的影響Fig 4 Effect of network coding on character

本文提出的構(gòu)架主要著眼于離散無線網(wǎng)絡(luò)，例如:車載網(wǎng)絡(luò)、無線手持網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)等。在一些網(wǎng)絡(luò)不發(fā)達(dá)的區(qū)域或者軍事限制區(qū)域中，有望得到很好的應(yīng)用。

［1］ Xiong Y P，Sun L M，Niu J W，et al．Opportunistic networks［J］．Journal of Software，2009，20（1）:124 －137．

［2］ Juang P，Oki H，Wang Y，et al．Energy-efficient computing for wildlife tracking:Design tradeoffs and early experiences with ZebraNet［C］∥Proc of the 10th Int’l Conf on Architectural Support for Programming Languages and Operating Systems，New York:ACM，2002:96 －107．

［3］ Cui J H，Kong J，Gerla M，et al．Challenges:Building scalable mobile underwater wireless sensor networks for aquatic applications［J］．IEEE Network，Special Issue on Wireless Sensor Networking，2006，20（3）:12 －18．

［4］ Chaintreau A，Hui P，Crowcroft J，et al．Impact of human mobility on the design of opportunistic forwarding algorithms［J］IEEE Trans on Mobile Computing，2007，6（6）:606 －620．

［5］ Spyropoulos T，Psounis K，Raghavendra C S．Spray and wait:An efficient routing scheme for intermittently connected mobile network-s［C］∥Proc of 2005 ACM SIGCOMM，2007，Workshop on Delay-Tolerant Networking，Philadelphia:ACM，2005:252 －259．

［6］ Lindgren A，Doria A，Schel’en O．Probabilistic routing in intermittently connected networks［C］∥Proc of SAPIR Workshop，2004:239－254．

［7］ Balasubramanian A，Levine B N，Venkataramani A．DTN routing as a resource allocation problem［C］∥SIGCOMM 2007，2007:373－384．

［8］ Wang Y，Jain S，Martonosi M，et al．Erasure-Coding based routing for opportunistic networks［C］∥Proc of 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking，Philadelphia:ACM，2005:229-236．

［9］ Widmer J，Boudec J L．Network coding for efficient communication in extreme networks［C］∥Proc of 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking，Philadelphia:ACM，2005:284－291．