移動Ｐ２Ｐ數(shù)據(jù)分發(fā)技術研究

摘 要：移動P2P數(shù)據(jù)分發(fā)技術將P2P模型應用到移動網(wǎng)絡中，通過節(jié)點間的相互配合來提高系統(tǒng)的可靠性、傳輸速度和擴展性，目前已成為無線通信的重點研究領域。但是由于移動網(wǎng)絡的復雜性，現(xiàn)有的移動P2P數(shù)據(jù)分發(fā)技術在實際應用中仍然存在很多問題。對近年來該領域的一些重點技術如Gossip算法、網(wǎng)絡編碼、糾錯碼進行了介紹，并在可靠性、傳輸速度和擴展性方面對它們進行了分析，針對其在網(wǎng)絡動態(tài)適應性、網(wǎng)絡融合、節(jié)點合作度等方面的不足提出了今后的研究方向。

關鍵詞：移動自組織網(wǎng)絡；數(shù)據(jù)分發(fā)；Gossip算法；網(wǎng)絡編碼；糾錯碼

中圖分類號：TP393 文獻標志碼：A

文章編號：1001-3695(2008)09-2586-06



Survey on mobile P2P data dissemination technique



MENG Chun1，SONG Meina1，SONG Junde1，JIA Junmin2

(1.School of Electronic Engineering， Beijing University of Posts Telecommunications， Beijing 100876， China;2.School of Electronic Information Engineering， North China Electric Power University， Baoding Hebei 071000， China)Abstract:Mobile P2P data dissemination technique applies P2P model to mobile networks. It utilizes mutual cooperation between nodes to improve reliability， transmission speed and scalability of the system and has recently become an important area of research in the field of wireless communication. However， due to complexity of mobile networks， the existing mobile P2P data dissemination techniques have many problems when they are applied to practical networks. This paper presented an introduction on some important techniques emerging recently in this area， such as Gossip algorithm， network coding and erasure codes. Then it analyzed these techniques in terms of reliability， transmission speed and scalability. In conclusion， it pointed out the future direction of research considering their insufficiency in adaptation to network dynamics， network convergence and node cooperation degree， etc.

Key words:mobile P2P; data dissemination; Gossip algorithm; network coding; erasure codes

近幾年，移動網(wǎng)絡出現(xiàn)了快速增長的趨勢，涌現(xiàn)了多種網(wǎng)絡技術，如移動自組織網(wǎng)、無線局域網(wǎng)、移動蜂窩網(wǎng)、無線Mesh網(wǎng)絡、無線傳感器網(wǎng)絡等。移動網(wǎng)絡在可靠性、網(wǎng)絡拓撲穩(wěn)定性、節(jié)點能力方面都要比有線網(wǎng)絡差，這使得開發(fā)基于移動網(wǎng)絡的應用要比有線網(wǎng)絡困難得多。P2P作為一種分布式計算模型，在互聯(lián)網(wǎng)中的應用已獲得了成功。在P2P網(wǎng)絡中，所有節(jié)點的地位都是相同的，它們之間通過相互配合來完成資源發(fā)現(xiàn)、數(shù)據(jù)分發(fā)等任務。與傳統(tǒng)的C/S模式相比，它避免了對服務器的依賴，從而具有更好的可靠性、傳輸效率、容錯性和擴展性，這些特點也使得它尤其適合移動網(wǎng)絡。

移動P2P數(shù)據(jù)分發(fā)技術正是在這種背景下發(fā)展起來的。它將P2P模型引入到移動網(wǎng)絡中，通過節(jié)點間的相互配合將數(shù)據(jù)從一個或多個源節(jié)點分發(fā)給目的節(jié)點。由于移動網(wǎng)絡具有許多與有線網(wǎng)絡不同的特點，其數(shù)據(jù)分發(fā)機制與有線網(wǎng)絡有很大不同。例如，有線網(wǎng)絡大多采用TCP協(xié)議，但在移動網(wǎng)絡中，網(wǎng)絡拓撲的頻繁變化將會導致TCP連接經(jīng)常中斷，使TCP的傳輸效率嚴重下降；此外，TCP協(xié)議的慢啟動特性、擁塞控制機制都不能適應移動網(wǎng)絡環(huán)境。因此必須根據(jù)移動網(wǎng)絡的特點，對數(shù)據(jù)分發(fā)涉及的各種技術如路由選擇技術、請求響應機制、擁塞控制機制等進行改進，才能提高系統(tǒng)的整體性能。移動P2P數(shù)據(jù)分發(fā)技術的應用范圍非常廣泛，包括文件共享、流媒體、數(shù)據(jù)聚集、緊急消息發(fā)布等。目前，尚無文獻對當前移動P2P數(shù)據(jù)分發(fā)技術進行總結和研究。

1 概述

1.1 移動P2P數(shù)據(jù)分發(fā)技術的主要組成構件

移動P2P數(shù)據(jù)分發(fā)技術是一門綜合性較強的技術，它通過多種技術來協(xié)調(diào)節(jié)點間的相互配合，以提高系統(tǒng)的可靠性、傳輸速度和擴展性，降低節(jié)點的能耗。從網(wǎng)絡協(xié)議層次上看，移動P2P數(shù)據(jù)分發(fā)技術居于傳輸層之上、應用層之下，一般稱為覆蓋層。圖1顯示了移動P2P數(shù)據(jù)分發(fā)模塊的基本結構。

圖1中，自適應模塊可以根據(jù)網(wǎng)絡變化情況以及節(jié)點自身情況自動調(diào)整協(xié)議參數(shù)，從而減小網(wǎng)絡拓撲動態(tài)變化對系統(tǒng)性能的影響。路由選擇模塊用來選擇下一跳節(jié)點，它可以利用底層路由協(xié)議來優(yōu)化路由選擇。發(fā)送/接收控制模塊則用來控制數(shù)據(jù)的發(fā)送次數(shù)、發(fā)送頻率等，并且可以根據(jù)節(jié)點緩存情況來決定是否接收數(shù)據(jù)包。數(shù)據(jù)編/解碼模塊主要負責對數(shù)據(jù)編碼和解碼。成員管理模塊負責維護成員列表，路由選擇模塊利用該列表中的信息來選擇下一跳節(jié)點。請求響應模塊則用來生成和響應請求消息。

1.2 移動P2P數(shù)據(jù)分發(fā)技術面臨的主要困難

由于移動P2P系統(tǒng)具有許多與有線網(wǎng)絡不同的特點，使得移動P2P數(shù)據(jù)分發(fā)技術面臨著更多的困難。

1）無線信道的物理局限 移動P2P系統(tǒng)中，數(shù)據(jù)大多通過無線信道傳輸。由于無線信道所固有的易受干擾、誤碼率高等缺點，移動P2P數(shù)據(jù)分發(fā)的可靠性要比有線網(wǎng)絡低得多。如何提高數(shù)據(jù)分發(fā)的可靠性一直是移動P2P數(shù)據(jù)分發(fā)技術的一個主要問題。

2）網(wǎng)絡拓撲的動態(tài)變化 移動P2P系統(tǒng)中，節(jié)點不僅可以隨時加入或離開，而且節(jié)點本身還可能在不斷移動。網(wǎng)絡拓撲的動態(tài)變化給成員管理、路由選擇等帶來較大的困難。這就要求節(jié)點具有一定的自適應機制，能夠根據(jù)網(wǎng)絡的具體情況動態(tài)地調(diào)整分發(fā)策略。

3）節(jié)點自身的限制 很多移動終端的計算能力較低，存儲器容量和能量也有限。因此，如何保證數(shù)據(jù)分發(fā)技術的輕量化是移動P2P數(shù)據(jù)分發(fā)技術的一個重要課題。

4）缺少基礎設施的支持 很多移動P2P系統(tǒng)都缺少基礎設施的支持，這就要求移動P2P系統(tǒng)具有一定的自組織能力，通過節(jié)點間的相互配合來保證數(shù)據(jù)分發(fā)的效率和可靠性。

5）移動設備的異構性 移動設備在能量、緩存容量和帶寬上往往存在很大差異，其對數(shù)據(jù)分發(fā)的貢獻度也不同。數(shù)據(jù)分發(fā)技術只有充分考慮這種異構性，才能提高數(shù)據(jù)分發(fā)的效率和可靠性。

1.3 研究進展情況

當前移動P2P數(shù)據(jù)分發(fā)技術研究呈現(xiàn)出如下特點：

a）新的體系結構不斷涌現(xiàn)。當前研究者大多通過設計全新的體系結構來滿足移動網(wǎng)絡發(fā)展的需要，它們在響應機制、緩存管理機制、路由機制等方面都與有線網(wǎng)絡有較大差異。

b）多種技術的綜合應用。影響移動P2P數(shù)據(jù)分發(fā)的因素很多，單純依賴一種技術是無法提高系統(tǒng)整體性能的，因此當前提出的移動P2P數(shù)據(jù)分發(fā)技術都綜合應用了多種技術，如數(shù)據(jù)編碼、路由選擇、擁塞控制等。

c）控制機制簡單化。現(xiàn)有的移動P2P數(shù)據(jù)分發(fā)技術在控制機制上都要比有線網(wǎng)絡簡單，這樣不僅可以降低節(jié)點的負擔，還使節(jié)點能夠快速地適應網(wǎng)絡的動態(tài)變化。

早期移動P2P數(shù)據(jù)分發(fā)技術研究主要集中于移動自組織網(wǎng)和無線傳感器網(wǎng)絡，現(xiàn)在已有研究者開始將它應用到無線Mesh網(wǎng)絡、車輛自組織網(wǎng)等網(wǎng)絡中。由于移動P2P數(shù)據(jù)分發(fā)技術具有廣泛的應用前景，國外許多大學和研究機構如加州大學、普林斯頓大學、微軟研究院、瑞士理工學院等都開展了這方面的研究。我國的浙江大學、華中科技大學也開始了這方面的研究，但總體來講還處于起步階段，與國外還存在很大差距。

2 Gossip算法

2.1 簡介

Gossip算法又稱為傳染病算法，最早由E. A. Demers等人^[1]于1987年提出。由于其實現(xiàn)非常簡單，而且具有良好的可靠性、容錯性和擴展性，引起了很多研究者的興趣。其應用范圍非常廣泛，包括流媒體^[2]、錯誤檢測^[3]、數(shù)據(jù)聚合^[4]等。Gossip算法在移動P2P中的應用還處于初始階段，目前大部分研究主要集中于移動自組織網(wǎng)和無線傳感器網(wǎng)絡，對于移動蜂窩網(wǎng)、無線Mesh網(wǎng)等網(wǎng)絡還鮮有涉及。

在Gossip算法中，數(shù)據(jù)分發(fā)是按照一輪一輪的方式進行的。在每一輪中，每個節(jié)點隨機地選擇f個其他節(jié)點，而后將數(shù)據(jù)包發(fā)送給它們。每個數(shù)據(jù)包都以這種方式發(fā)送t輪。其中f和t是兩個重要的參數(shù)，f又稱為扇出數(shù)（fanout）。這個過程與傳染病的傳播過程很相似。圖2顯示了Gossip算法的工作過程。

Gossip算法主要通過兩條途徑來保證數(shù)據(jù)分發(fā)的可靠性：一條途徑是通過數(shù)據(jù)分發(fā)路徑的多樣性，數(shù)據(jù)包一次分發(fā)給多個節(jié)點，即使有一些節(jié)點失效，其他沒有失效的節(jié)點仍然可以接收到數(shù)據(jù)；另一條途徑是通過數(shù)據(jù)包的重復多次分發(fā)，這樣即使某些節(jié)點在第一輪中沒有接收到數(shù)據(jù)，它們?nèi)匀豢梢栽谝院蟮臄?shù)據(jù)分發(fā)中接收到數(shù)據(jù)。由于采用隨機路由機制，Gossip算法對網(wǎng)絡拓撲的動態(tài)變化具有一定的適應性。

2.2 研究現(xiàn)狀

2.2.1 AG^[7]

AG是較早的一種移動自組織網(wǎng)Gossip算法。它的最大特點是數(shù)據(jù)分發(fā)過程分為兩個階段：第一階段先利用多播協(xié)議MAODV將數(shù)據(jù)分發(fā)給多播組成員；第二階段再使用Gossip算法來保證所有組成員都接收到數(shù)據(jù)。它的第二個特點是在使用Gossip算法時無須知道其他組成員，節(jié)點從鄰居中隨機地選擇一個節(jié)點，而后向該節(jié)點發(fā)送一條Gossip消息。該消息中包含源節(jié)點地址、組地址和節(jié)點所缺少的數(shù)據(jù)包編號等信息。接收到該消息的節(jié)點如果是組成員，它可以選擇響應該消息，也可以選擇將該消息繼續(xù)傳遞給其他節(jié)點。AG還考慮了網(wǎng)絡拓撲的影響。路由表中的每個節(jié)點都有一項nearest_member，它表示該節(jié)點到下一跳節(jié)點的最短距離。當選擇下一跳時，節(jié)點的nearest_member越小，被選中的概率越大，這樣，不僅可以減少網(wǎng)絡流量，還可以提高數(shù)據(jù)分發(fā)的效率。AG的最大缺點是它需要依賴底層多播協(xié)議，而且它只能提供概率可靠的數(shù)據(jù)分發(fā)，這就限制了它在實際網(wǎng)絡中的應用。

2.2.2￣ RDG^[5]

與AG不同，RDG使用單播路由協(xié)議DSR來進行數(shù)據(jù)傳輸，從而避免了對底層多播協(xié)議的依賴。為了減小系統(tǒng)開銷，RDG在每個數(shù)據(jù)包都附加了三條信息：將要離開的一個節(jié)點ID、節(jié)點列表中隨機選取的一個節(jié)點ID、節(jié)點所缺少的數(shù)據(jù)包編號。接收到數(shù)據(jù)包的節(jié)點則根據(jù)數(shù)據(jù)包中附加的信息更新節(jié)點列表與緩存，并響應發(fā)送節(jié)點的數(shù)據(jù)請求。文獻[5]中還提到了TARDG，與AG類似，路由表中的每個節(jié)點都根據(jù)其路徑長度分配一個權值，路徑越長，權值越小，在選擇下一跳時，節(jié)點的權值越大，被選中的概率也越大。RDG的主要缺點是沒有考慮擁塞控制，只適合網(wǎng)絡規(guī)模較小的場合；此外，它需要事先指定f和t，不能適應網(wǎng)絡的動態(tài)變化。

2.2.3 EraMobile^[8]

EraMobile最大的特點是利用廣播分發(fā)數(shù)據(jù)，這樣不僅可以簡化分發(fā)算法，而且不需要維護節(jié)點列表。在EraMobile中，節(jié)點首先將自己的數(shù)據(jù)摘要廣播給附近節(jié)點，接收到數(shù)據(jù)摘要的節(jié)點將該摘要與本地緩存中的內(nèi)容進行比較，并根據(jù)比較結果響應廣播摘要的節(jié)點。EraMobile還能夠根據(jù)節(jié)點密度動態(tài)調(diào)整協(xié)議參數(shù)。它主要有四個參數(shù)：每一輪中可以發(fā)送的最大數(shù)據(jù)包數(shù)N、最大請求消息數(shù)Q、每個數(shù)據(jù)包發(fā)送的最大次數(shù)T、每一輪的時間P。它把節(jié)點密度分為高、中、低三個等級。當節(jié)點密度較低時，它通過增加N、Q和T，同時減少P來提高數(shù)據(jù)分發(fā)的可靠性；而當節(jié)點密度較高時，它則會減小N、Q和T，同時增加P，以減少網(wǎng)絡擁塞對數(shù)據(jù)分發(fā)可靠性的影響。

2.2.4 CREW^[9]

CREW將Gossip算法應用到flash分發(fā)中。所謂flash分發(fā)，即將信息在短時間內(nèi)分發(fā)給很多用戶。CREW通過兩種方法來提高數(shù)據(jù)分發(fā)的速度：a)通過拉的方式減少重復數(shù)據(jù)。首先將包含所有數(shù)據(jù)塊id的元數(shù)據(jù)廣播到整個網(wǎng)絡中，節(jié)點再根據(jù)元數(shù)據(jù)向其他節(jié)點請求數(shù)據(jù)塊。b)通過隨機走動技術來減少維護網(wǎng)絡拓撲的開銷。為了解決節(jié)點帶寬的異構問題，CREW使用節(jié)點的吞吐率來動態(tài)地計算帶寬。當帶寬用盡時，將不再響應其他節(jié)點的請求消息。此外，當節(jié)點沒有多余帶寬時，它會響應一條忙消息來通知請求節(jié)點調(diào)整分發(fā)策略。CREW的不足是使用TCP協(xié)議來維護覆蓋層網(wǎng)絡拓撲，從而限制了它在動態(tài)網(wǎng)絡拓撲中的應用。

2.2.5 Gossip算法在錯誤檢測中的應用^[3]

文獻[3]將Gossip算法應用到無線自組織網(wǎng)及Mesh網(wǎng)絡的錯誤檢測中。每個節(jié)點v周期性地廣播心跳消息，其中包含兩個數(shù)組：Alivev存儲節(jié)點v已接收到的心跳計數(shù)；Hopsv存儲v與其他節(jié)點間的跳數(shù)。節(jié)點u接收到v的心跳消息后，將根據(jù)Alivev和Hopsv估算節(jié)點v的下一個心跳消息到來的時間τ；如果時間τ之后沒有接收到心跳消息，節(jié)點將繼續(xù)等待一段時間Δ；如果仍沒有接收到心跳消息，則認為v已經(jīng)發(fā)生故障。該方法的主要不足是沒有對廣播進行有效控制，容易導致網(wǎng)絡擁塞。

2.3 小結

表1對以上Gossip算法進行了總結。

表1 Gossip算法總結

比較項AGRDGEraMobileCREW錯誤檢測

請求響應機制使用Gossip消息請求數(shù)據(jù)在數(shù)據(jù)包中附加NAK數(shù)據(jù)摘要、拉方式相結合元數(shù)據(jù)、拉方式相結合

底層路由協(xié)議MAODVDSR廣播廣播與單播結合廣播

成員管理由MAODV負責管理成員列表包含系統(tǒng)隨機局部視圖無須維護成員列表采用隨機走動方法維護成員列表

拓撲感知考慮未考慮未考慮未考慮未考慮

自適應機制無無根據(jù)節(jié)點密度調(diào)整協(xié)議參數(shù)根據(jù)節(jié)點剩余帶寬調(diào)整分發(fā)策略無

異構性未考慮未考慮未考慮考慮未考慮

2.3.1 可靠性

從表1可以看出，為了提高數(shù)據(jù)分發(fā)的可靠性，Gossip算法大多采用了請求響應機制。其中EraMobile、CREW在進行請求響應之前都要廣播一個數(shù)據(jù)摘要（元數(shù)據(jù)），這樣就使得節(jié)點請求數(shù)據(jù)時更有針對性。這種方式的一個缺點是會增加節(jié)點的能耗，而且大量的請求消息和數(shù)據(jù)摘要還會造成網(wǎng)絡擁塞，從而降低數(shù)據(jù)分發(fā)的可靠性。

Gossip算法大多使用UDP協(xié)議，這就要求在設計算法時考慮擁塞控制。EraMobile采用被動方式，節(jié)點通過感知周圍環(huán)境來調(diào)整協(xié)議參數(shù)。該方法的缺點是：當網(wǎng)絡拓撲變化頻繁時，節(jié)點可能來不及收集足夠的信息，從而容易造成分發(fā)策略與網(wǎng)絡實際情況的失配。CREW則采用主動方式，由節(jié)點主動通知請求節(jié)點調(diào)整分發(fā)策略，因而實時性較強。

2.3.2 傳輸速度

底層路由協(xié)議對于數(shù)據(jù)傳輸速度具有重要影響。當網(wǎng)絡中的節(jié)點數(shù)目增加時，底層路由協(xié)議的開銷就會增大。另外，節(jié)點的頻繁移動還會導致很多路由錯誤，這些錯誤將會重新啟動路由發(fā)現(xiàn)過程，從而使網(wǎng)絡擁塞情況惡化，對數(shù)據(jù)傳輸速度帶來不利影響。使用廣播傳輸數(shù)據(jù)的最大優(yōu)點是：它充分利用了無線信道的廣播特性，一次分發(fā)就可以使多個節(jié)點接收到數(shù)據(jù)。但是使用廣播也會帶來重復數(shù)據(jù)問題。

AG和TARDG都考慮了網(wǎng)絡拓撲對傳輸速度的影響，它們的共同特點是優(yōu)先選擇距離較近的節(jié)點，于是數(shù)據(jù)分發(fā)將主要集中在節(jié)點附近進行，從而提高了數(shù)據(jù)分發(fā)的效率。但是它們都需要依賴底層路由協(xié)議，這就限制了其應用范圍。

2.3.3 擴展性

成員列表是影響Gossip算法擴展性的重要因素。RDG和CREW都只需要維護系統(tǒng)的部分視圖，這就降低了維護成員列表的開銷，但是這樣無法保證節(jié)點選擇的均勻性。EraMobile采用廣播傳輸數(shù)據(jù)，因此無須維護節(jié)點列表，從而避免了維護節(jié)點列表所帶來的開銷。

3 網(wǎng)絡編碼

3.1 簡介

網(wǎng)絡編碼是21世紀通信領域的一項重要變革。它的主要思想是網(wǎng)絡中的所有節(jié)點都對數(shù)據(jù)進行編碼，如進行異或和線性組合等操作，再將編碼后的結果傳遞給其他節(jié)點。網(wǎng)絡編碼首先由Ahlswede等人^[10]于2000年提出；隨后，Li 等人^[11]證明了使用線性網(wǎng)絡編碼能夠達到網(wǎng)絡多播容量的最優(yōu)值。2003年Tracey Ho等人^[12]提出了隨機網(wǎng)絡編碼，拓寬了網(wǎng)絡編碼的適用性。分析和實驗表明，網(wǎng)絡編碼不僅可以提高網(wǎng)絡吞吐量^[12]，而且可以降低節(jié)點的能耗^[13]；使用隨機網(wǎng)絡編碼還可以提高系統(tǒng)的可靠性。然而，雖然經(jīng)過幾年的發(fā)展，大多數(shù)研究仍然局限在數(shù)學分析和仿真階段，網(wǎng)絡編碼在實際中的應用還面臨著諸多問題。

3.2 研究現(xiàn)狀

3.2.1 實際網(wǎng)絡編碼^[15]

文獻[15]對如何將隨機網(wǎng)絡編碼應用到實際網(wǎng)絡中進行了研究。為了減少收集編碼塊的時間。文獻[15]提出應用優(yōu)先級編碼傳輸技術（PET）^[16]來減少收集編碼包的時間。在PET中，h個數(shù)據(jù)塊按照重要程度被分成h層。當節(jié)點接收到編碼向量組的秩為k時，它就可以恢復前k層的數(shù)據(jù)塊。為了解決大文件的分發(fā)問題，文獻[15]還提出將文件分成若干段，每一段又稱為輩（generation），每一輩都有一個輩編號，再使用隨機網(wǎng)絡編碼分發(fā)每一輩中的數(shù)據(jù)。節(jié)點在接收到編碼包后隨即進行高斯消去，以減少解碼和判斷編碼向量是否線性無關的時間。

3.2.2 隨機網(wǎng)絡編碼與Gossip算法的結合^[17]

文獻[17]分別為基于網(wǎng)絡編碼和存儲轉(zhuǎn)發(fā)的Gossip算法建立了數(shù)學模型，并通過仿真證實了網(wǎng)絡編碼可以大幅度減小傳輸延遲。該文還提出了緩存替代策略。當節(jié)點b接收到一個編碼包xa時，如果緩存中沒有空閑空間，b就會將xa與緩存中的編碼包一起共同編碼：xi′=xi+λxa。其中：xi代表節(jié)點b緩存中的第i個編碼塊；λ是從有限域中隨機選取的元素。此外該文還提出了優(yōu)先級編碼協(xié)議，K個原始數(shù)據(jù)包首先被分成M個優(yōu)先級，再按照優(yōu)先級由高到低的順序分別進行編碼，優(yōu)先級高的數(shù)據(jù)最先被解碼。其不足是假設每次接收到的編碼包都是可用的。事實上，一個擁有n個編碼包的節(jié)點A最多只能為其他節(jié)點貢獻n個線性無關的編碼包，如果某個節(jié)點B已經(jīng)從A接收到n個線性無關的編碼包，那么以后從A接收到的編碼包對B來說都是沒有用的。

3.2.3 CodeTorrent^[18]

CodeTorrent將隨機網(wǎng)絡編碼應用到車輛自組織網(wǎng)中（VANET）。它采用廣播傳輸數(shù)據(jù)，還利用節(jié)點的移動來提高數(shù)據(jù)分發(fā)速度。它采用拉的方式來分發(fā)數(shù)據(jù)。源節(jié)點首先廣播一個文件描述消息，接收到該消息的節(jié)點如果對文件感興趣，就會廣播一條請求消息，接收到請求消息的節(jié)點向請求節(jié)點發(fā)送編碼包。為了幫助節(jié)點選擇編碼包，每條請求消息中還包含一個無效空間向量。

3.3.1 可靠性

緩存管理策略是影響網(wǎng)絡編碼可靠性的重要因素。文獻[15]采用了傳統(tǒng)的FIFO策略，當新的數(shù)據(jù)段到來時就將舊數(shù)據(jù)段清除出緩存，這樣就無法響應其他節(jié)點對舊數(shù)據(jù)段的請求。與文獻[15]不同，文獻[19]采用了逐漸減少編碼向量秩的方法。這樣，當刪除編碼包時，節(jié)點仍然可以響應其他節(jié)點對舊數(shù)據(jù)段的請求。文獻[17]使用了緩存替代策略，它在提高數(shù)據(jù)有用性的同時還提高了緩存的利用效率。

3.3.2 傳輸速度

提高網(wǎng)絡數(shù)據(jù)傳輸速度的方法可分為兩類：

a）對網(wǎng)絡編碼的各階段進行優(yōu)化。文獻[15，17]分別提出利用PET和優(yōu)先級編碼協(xié)議來減小編碼包的收集時間，它們的共同特點是都需要對數(shù)據(jù)進行預處理。PET的主要不足是增加了數(shù)據(jù)的冗余度；優(yōu)先級編碼協(xié)議的主要缺點是不能保證按文件原始順序進行解碼。

b）利用節(jié)點的移動性。節(jié)點的移動不僅造成網(wǎng)絡拓撲的動態(tài)變化，也增加了節(jié)點相遇的機會，因而利用移動性可以提高網(wǎng)絡編碼的傳輸速度。該類方法的最大缺點是傳輸速度受節(jié)點運動速度和運動方向的影響比較大，節(jié)點不能對傳輸速度進行預期。

3.3.3 擴展性

提高網(wǎng)絡編碼擴展性的一個措施是通過請求響應機制來減少無用編碼包的發(fā)送次數(shù)。在文獻[20]中，節(jié)點首先計算可以從其他節(jié)點獲取的編碼包數(shù)目，再根據(jù)該數(shù)值請求編碼包，從而減少了接收到無用編碼包的概率。CodeTorrent則在請求消息中包含了無效空間向量，接收到請求消息的節(jié)點可以通過該向量來判斷是否響應請求消息。兩者的主要不足是它們都需要在發(fā)送請求消息前進行復雜的計算，因而增加了傳輸延遲和節(jié)點負擔。

4 糾錯碼

4.1 簡介

將糾錯碼應用于移動P2P系統(tǒng)，不僅可以提高數(shù)據(jù)傳輸?shù)目煽啃院蛡鬏斔俣龋€能夠減少響應消息的數(shù)目，從而減輕系統(tǒng)的負擔，提高系統(tǒng)的擴展性。糾錯碼的應用領域包括文件共享、流媒體等。近年來，隨著P2P流媒體的日益普及，糾錯碼引起了很多研究者的興趣。

糾錯碼的基本原理是：文件被分成k塊，k個數(shù)據(jù)塊被編碼為n個編碼塊（n>k），節(jié)點將這n個編碼塊發(fā)送給目標節(jié)點，目標節(jié)點只要接收到任意(1+ε)k個編碼塊，就可以通過解碼恢復原始文件。其中：ε是一個與具體編碼有關的參數(shù)（對MDS編碼，ε=0；對其他編碼，ε>0）。常用的糾錯碼包括ReedSolomon編碼、Vander Monde編碼、Tornado編碼、分層編碼和MDC編碼等。其中分層編碼和MDC編碼主要應用于流媒體領域。

糾錯碼只要求接收到n個編碼塊中的任意(1+ε)k個編碼塊就可以恢復原始文件，因此，即使中間丟失了一些編碼塊，仍然可以通過其他編碼塊恢復原始文件。這樣就大大提高了系統(tǒng)的可靠性。一般在使用糾錯碼時，都要求n遠大于k，這樣可以大大減小接收到重復數(shù)據(jù)的概率，從而提高傳輸速度。

4.2 研究現(xiàn)狀

4.2.1 Tornado編碼在移動自組織網(wǎng)中的應用^[21]

文獻[21]將Tornado編碼應用到移動自組織網(wǎng)數(shù)據(jù)分發(fā)中。它的實現(xiàn)方法非常簡單，源節(jié)點將編碼后的數(shù)據(jù)段隨機廣播到網(wǎng)絡中，接收到編碼塊的節(jié)點繼續(xù)將編碼塊廣播給其他節(jié)點。該過程將無限制地進行下去。這種方法只適合所有用戶請求同一個文件的有限場合，但它無須建立任何邏輯網(wǎng)絡和節(jié)點連接，便可在高度移動性的P2P網(wǎng)絡中高效地分發(fā)文件，其路由機制也很簡單。

4.2.2 MDC在P2P流媒體中的應用^[22，23]

近年來，一些研究者將MDC編碼應用在P2P流媒體領域，結合多路徑和多數(shù)據(jù)源的分發(fā)機制，不僅可以提高傳輸速度，還可以提高系統(tǒng)的可靠性。在MDC編碼中，多媒體文件中的幀被分成很多組，每組幀中的位按照其重要程度進行排序；再將新形成的位流進行編碼，生成M個相互獨立的編碼包，接收到的編碼包越多，失真就越小。

CoopNet^[22]采用多個數(shù)據(jù)分發(fā)樹來分發(fā)MDC編碼包，服務器為新加入的節(jié)點分配父親節(jié)點，每個節(jié)點都擁有多個父親節(jié)點，文件經(jīng)過編碼后沿多個分發(fā)樹傳遞給目標節(jié)點。此外，CoopNet還可以根據(jù)編碼包的接收情況對編碼策略進行優(yōu)化，使系統(tǒng)能夠適應網(wǎng)絡的動態(tài)變化。

文獻[23]將MDC編碼應用于無線Mesh網(wǎng)絡。它采用多路徑和多數(shù)據(jù)源的分發(fā)機制，由媒體服務器負責為請求節(jié)點分配源節(jié)點和傳輸路徑。文獻[23]還建立了路徑選擇的數(shù)學模型，并使用遺傳算法來選擇最優(yōu)路徑。

4.2.3 PeerFecT^[24]

PeerFecT將糾錯碼應用在并行文件下載中。文件先被分成k個數(shù)據(jù)塊，然后使用糾錯碼對其進行編碼，生成n個編碼塊，它們隨即被散布到網(wǎng)絡的多個節(jié)點上。下載文件時，節(jié)點利用系統(tǒng)提供的資源發(fā)現(xiàn)服務找到最近存儲編碼塊的節(jié)點，并從這些節(jié)點下載編碼塊。

4.2.4 糾錯碼在機會網(wǎng)絡中的應用^[25]

文獻[25]將糾錯碼應用到節(jié)點移動頻繁的機會網(wǎng)絡中。與文獻[24]類似，文獻[25]將編碼包平均分布在mr個中間節(jié)點上。其中：m為一個常數(shù)；r=n/k。節(jié)點只要從其中m個中間節(jié)點上成功下載了編碼塊，就可以恢復原始文件。通過數(shù)學分析，文獻[25]證明了使用這種方法可以減小最差情況下的傳輸延遲，當m很大時，傳輸延遲的分布接近一個常數(shù)。

4.3 小結

由上可見，在應用糾錯碼時，一般要結合多路徑、多數(shù)據(jù)源的方法來提高系統(tǒng)的可靠性和傳輸速度。CoopNet的主要不足是采用了樹型網(wǎng)絡拓撲，當父親節(jié)點發(fā)生故障或者移動時，它的所有子樹都將無法接收到數(shù)據(jù)，因而CoopNet只能適用于網(wǎng)絡拓撲較為穩(wěn)定的場合。文獻[23]、PeerFecT和文獻[25]都采用了多數(shù)據(jù)源、多路徑相結合的傳輸方式，從而避免了單點故障。

CoopNet和文獻[23]都采用了集中式的控制機制，由中央服務器負責為節(jié)點分配傳輸路徑和數(shù)據(jù)源，當系統(tǒng)規(guī)模增大時，中央服務器的負擔也將增大，因此它們都只適合網(wǎng)絡規(guī)模較小的場合。PeerFecT和文獻[25]則采用了將編碼塊預先分配到多個節(jié)點的方法。這種方法的一個缺點是源節(jié)點必須事先了解整個網(wǎng)絡的拓撲結構，才能保證編碼包在網(wǎng)絡中的合理分布，因而它不能適應網(wǎng)絡拓撲的動態(tài)變化。

5 結束語

移動P2P的網(wǎng)絡環(huán)境與有線網(wǎng)絡有很大不同，不僅可靠性比較差，而且節(jié)點的移動還會造成網(wǎng)絡拓撲的動態(tài)變化，這給數(shù)據(jù)分發(fā)帶來很大困難。因此，在移動P2P數(shù)據(jù)分發(fā)技術發(fā)展初期，研究者的注意力主要集中在如何提高數(shù)據(jù)分發(fā)的可靠性上。隨著通信技術的發(fā)展，許多研究者開始將網(wǎng)絡編碼、糾錯碼等技術應用在移動P2P數(shù)據(jù)分發(fā)中，通過與其他技術如傳染病算法、多路徑多數(shù)據(jù)源的數(shù)據(jù)分發(fā)技術相結合，提高了數(shù)據(jù)分發(fā)的速度和可靠性。雖然經(jīng)過多年的發(fā)展，移動P2P數(shù)據(jù)分發(fā)技術在實際應用中仍然存在很多問題，這也是今后移動P2P數(shù)據(jù)分發(fā)技術的主要研究方向。

1）能夠適應網(wǎng)絡動態(tài)變化和節(jié)點異構性的自適應P2P數(shù)據(jù)分發(fā)技術。在實際的移動P2P系統(tǒng)中，網(wǎng)絡不僅處于動態(tài)變化狀態(tài)，而且每個節(jié)點自身的狀態(tài)也存在很大差異。然而，目前大部分移動P2P數(shù)據(jù)分發(fā)技術都沒有考慮自適應機制和節(jié)點異構性，這就限制了它們在實際網(wǎng)絡中的應用。因此，如何根據(jù)網(wǎng)絡動態(tài)變化和節(jié)點的異構性動態(tài)調(diào)整數(shù)據(jù)分發(fā)策略將是今后研究的重點和難點問題。

2）適應網(wǎng)絡編碼和糾錯碼特點的數(shù)據(jù)分發(fā)技術。網(wǎng)絡編碼和糾錯碼在數(shù)據(jù)分發(fā)機制上與傳統(tǒng)存儲轉(zhuǎn)發(fā)機制存在很大差異，因此，必須對數(shù)據(jù)分發(fā)技術的各個組件如請求響應機制、緩存管理機制、擁塞控制技術等進行改進，使之適應網(wǎng)絡編碼和糾錯碼的特點，才能真正發(fā)揮它們的優(yōu)勢。

3）移動性在數(shù)據(jù)分發(fā)中的應用。移動性不僅可以造成網(wǎng)絡拓撲的動態(tài)變化，也可以加速數(shù)據(jù)分發(fā)的速度。目前，移動性在移動P2P數(shù)據(jù)分發(fā)中的應用還處于開始階段，仍然存在很多問題需要解決，如節(jié)點運動速度的差異對數(shù)據(jù)分發(fā)的影響、如何感知節(jié)點運動速度、如何調(diào)整算法參數(shù)以適應節(jié)點的運動等。

4）適合多種網(wǎng)絡的數(shù)據(jù)分發(fā)技術。目前移動P2P數(shù)據(jù)分發(fā)的研究都局限于單一網(wǎng)絡，不能適應未來多種網(wǎng)絡融合的發(fā)展趨勢。因此，研究適應多種網(wǎng)絡的移動P2P數(shù)據(jù)分發(fā)技術將是一個很有前途的方向。

5）考慮節(jié)點合作度的數(shù)據(jù)分發(fā)技術。當前移動P2P數(shù)據(jù)分發(fā)技術在設計時大多沒有考慮節(jié)點合作度問題，這也是限制其在實際網(wǎng)絡中應用的一個重要因素。因此，如何在數(shù)據(jù)分發(fā)技術中考慮節(jié)點合作度問題將是未來的一個重要研究課題。

參考文獻：

［1］DEMERS E A，GREENE D，HAUSER C，et al.Epidemic algorithms for replicated database maintenance[C]//Proc of the 6th Annual ACM Symposium on Principles.New York:ACM Press，1987:112.

[2]ZHANG Xinyan，LIU Jiangchuan，LI Bo，et al.CoolStreaming/DONet: a datadriven overlay network for peertopeer live media streaming[C]//Proc of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies.2005:2102-2111.

[3]ELHADEF M，BOUKERCHEA.A Gossipstyle crash faults detection protocol for wireless Ad hoc and mesh networks[C]//Proc of Performance， Computing， and Communications Conference.New Orleans:[s.n.]，2007:600-605.

[4]JELASITY M，MONTRESOR A，BABAOGLUO.Gossipbased aggregation in large dynamic networks[J].ACM Trans on Computer Systems，2005，23(3):219-252.

[5]LUO Jun，EUGSTER P T，HUBAUX J.Route driven Gossip: probabilistic reliable multicast in Ad hoc networks[C]//Proc of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.2003:2229-2239.

[6]KERMARREC A，MASSOULIE L，GANESH A J.Probabilistic reliable dissemination in largescale systems[J]. IEEE Trans on Parallel and Distributed Systems，2003，14(3): 248-258.

[7]CHANDRA R， RAMASUBRAMANIAN V， BIRMAN K.Anonymous Gossip:improving multicast reliability in mobile Ad hoc networks[C]//Proc of the 21st International Conference on Distributed Computing Systems.New York:Cornell University，2001:275-283.

[8]ZKASAP ，GENC Z，ATSAN E.Epidemicbased approaches for reliable multicast in mobile Ad hoc networks[J].ACM SIGOPS Operating Systems Review，2006，40(3): 7379. [9]DESHPANDE M，BO Xing，LAZARDIS I，et al.CREW:a Gossipbased flashdissemination system[C]//Proc of the 26th IEEE International Conference on Distributed Computing Systems.2006.

[10]AHLSWEDE R，CAI Ning，LI S Y R，et al.Network information flow[J].IEEE Trans on Information Theory，2000，46(4):12041206.

[11]LI S Y R，YEUNG R W，CAI Ning.Linear network coding[J].IEEE Transon Infomation Theory，2003，49(2):371-381.

[12]HO T，MDARD M，SHI Jun，et al.On randomized network coding[C]//Proc of the 41st Annual Allerton Conference on Communication Control and Computing.2003.

[13]WIDMER J，F(xiàn)RAGOULI C，BOUDEC J L.Lowcomplexity energyefficient broadcasting in wireless Ad hoc networks using network coding[C]//Proc of Workshop on Network Coding， Theory， and Applications.2005.

DEB S，MDARD M，CHOUTE C.Algebraic Gossip:a network coding approach to optimal multiple rumor mongering[J].IEEE/ACM Trans on Networking，2006，49(SI): 2486-2507.

[15]CHOU P A，WU Yunnan，JAIN K.Practical network coding[C]//Proc of Allerton Conference on Communication， Control， and Computing.2003.

[16]ALBANESE A，BLOMER J，EDMONDS J，et al.Priority encoding transmission[J].IEEE Trans on Information Theory，1996，42(6):17371744.

[17]LIN Yunfeng，LIANG Ben，LI Baochun.Performance modeling of network coding in epidemic routing[C]//Proc of the 1st International MobiSys Workshop on Mobile Opportunistic Networking.New York:ACM Press，2007:6774.

[18]LEE U，PARK J S，YEH J，et al.CodeTorrent:content distribution using network coding in VANET[C]//Proc of the 1st International Workshop on Decentralized Resource Sharing in Mobile Computing and Networking.New York:ACM Press，2006:1-5.

[19]WIDMER J，BOUDEC J L.Network coding for efficient communication in extreme networks[C]//Proc of ACM SIGCOMM Workshop on Delaytolerant Networking.New York:ACM Press，2005:284-291.

[20]LIU Yajie，PENG Yuxing，DOU Wenhua，et al.Network coding for peertopeer live media streaming[C]//Proc of the 5th International Conference on Grid and Cooperative Computing.2006:149155.

[21]GOEL S K，SINGH M，XU Dongyan，et al.Efficient peertopeer data dissemination in mobile Ad hoc networks[C]//Proc of International Conference on Parallel Processing Workshops.Washington DC:IEEE Computer Society，2002：152158.

[22]PADMANABHAN V N，WANG H J，CHOU P A.Resilient peertopeer streaming[C]//Proc of the 11th IEEE International Conference on Network Protocols.2003:16-27. [23]LI Danjue，ZHANG Qian，CHUAH C N，et al.Error resilient concurrent video streaming over wireless mesh networks[J].浙江大學學報A:英文版，2006，7(5): 684-695.

[24]DAIRAINE L，LANCRICA L，LACAN J.Enhancing peertopeer parallel data access with PeerFec[C]//Proc of the 5th International Workshop on Networked Group Communications and Charges.2003:254-261.

[25]WANG Yong，JAIN S，MARTONOSI M，et al.Erasure coding based routing for opportunistic networks[C]//Proc of ACM SIGCOMM Workshop on Delaytolerant Networking.New York:ACM Press，2005:229-236.