錢景輝，謝開源

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

0 引言

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

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

1 相關理論

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

1．1 機會傳輸

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

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

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

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

1．2 網絡編碼

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

1．3 傳輸機制

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

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

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

2 MCR構架

2．1 概 述

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

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

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

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

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

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

圖1 MCR構架Fig 1 MCR framework

2．2 上層網絡:路徑選擇與映射

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

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

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

上層網絡的作用在于:

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

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

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

2．3 下層網絡:網絡編碼

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

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

2．4 下層網絡:機會傳輸

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

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

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

1）過去的平均機會傳輸次數;

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

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

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

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

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

2．5 舊信息維護

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

3 仿真與評估

在上文中已經提到，MCR構架將整個DTN劃分成若干個子區(qū)域，而每個子區(qū)域內的節(jié)點移動模型將比整個區(qū)域的模型簡單得多。如何在上層網絡中選取合適的最優(yōu)路徑已經不屬于DTN機會傳輸的范疇，下文的仿真將針對機會網絡來進行。

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

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

仿真實驗證明，MCR的表現比 RAPID，PRoPHET，Spray and Wait和Epidemic都要好。當消息產生速率相同時，Epidemic的網絡負載已經接近MCR的2倍。

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

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

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

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

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

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

4 結論

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

圖4 網絡編碼對性能的影響Fig 4 Effect of network coding on character

本文提出的構架主要著眼于離散無線網絡，例如:車載網絡、無線手持網絡、無線傳感器網絡等。在一些網絡不發(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．