錢景輝，謝開源

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

0 引言

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

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

1 相關理論

本文的工作同時涉及機會網(wǎng)絡傳輸構架、網(wǎng)絡編碼以及機會網(wǎng)絡傳輸。

1．1 機會傳輸

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

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

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

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

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

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

1．3 傳輸機制

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

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

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

2 MCR構架

2．1 概 述

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

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

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

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

3）在網(wǎng)絡拓撲結構改變時，MCR只需要調(diào)整對應的部分，而不需要對整個構架進行重新設計。

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

圖1 MCR構架Fig 1 MCR framework

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RAPID在相遇節(jié)點時交換以下信息:

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

2）節(jié)點相遇期望時間;

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

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

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

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

2．5 舊信息維護

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

3 仿真與評估

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

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

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

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

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

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

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

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

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

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

4 結論

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

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

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

［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．