【正文】 傳統(tǒng)的 MANET，移動模型對機會網(wǎng)絡研究更加重要。 獨立同分布的理論移動模型 許多學者研究了 3個經(jīng)典的獨立同分布移動模： Random Way Point[8](RWP) Random Walk(RW)和 Random Direction[9](RD)。這些模型下的節(jié)點相遇特征可用兩個參數(shù)來刻畫：相遇時間 (meeting time，簡稱 MT)和相遇間隔時間 (inter meeting time，簡稱 IMT)。 MT 是指兩個節(jié)點從靜止開始到第一次相遇 (進入通信范圍 )經(jīng)過的時間間隔，而 IMT 是指兩個節(jié)點前后兩次相遇的時間間隔。文獻 [9]都分別從不同的角度證明了上述 3個移動模型的節(jié)點期望相遇時間 (expected meeting time)中北大學 2022 屆畢業(yè)設計說明書 第 8 頁 共 57 頁 服從指數(shù)分布或其尾部服從指數(shù)分布，并基于此分析了多種路由協(xié)議的延時性能。文獻 [10]推導出 RW模型下期望相遇間隔時間的分布也服從指數(shù)分布，而文獻 [11]推導了 RD模型和 RWP模型下的期望相遇間隔時 間分布，并證明了 RWP和 RD模型下相遇時間和相遇間隔時間的尾部分布是無記憶的。 基于統(tǒng)計的實際移動模型 除了從理論來推導以外，一些研究人員還利用統(tǒng)計方法，通過收集實際環(huán)境中節(jié)點的運動軌跡來研究節(jié)點的移動特征。 MIT 的 Reality Mining項目 [12]記錄了MIT校園中 100個攜帶藍牙智能手機的學生和職工為期 9個月的移動軌跡和相遇數(shù)據(jù)； UCSD 的 Wireless Topology Discovery[13]收集了 11周內 300個無線 PDA與 WiFi接入點的相遇數(shù)據(jù)；劍橋大學的 Haggle項目 [14]則記錄了若干個帶有藍牙接口的iMote設備在校園的相遇情況。此外，他們還在 INFOCOM參會期間進行了類似的實驗； UMass研究小組 [15]收集并分析了由公交車上的 WiFi節(jié)點組成的機會網(wǎng)絡DieselNet實際運行中的相遇規(guī)律。文獻 [2]通過分析文獻 [13]中的數(shù)據(jù)集發(fā)現(xiàn)，實際節(jié)點的移動具有社區(qū)特性，節(jié)點相遇時間服從近似的冪律分布，而不是根據(jù)經(jīng)典移動模型推導出的指數(shù)分布，這些成果證實了傳統(tǒng)的移動模型并不一定適用于實際節(jié)點的移動特征，但研究人員在對于使用何種分布的移動模型問題上一直存在爭議 。文獻 [16]試圖統(tǒng)一這兩種類型的移動模型，作者從理論上推導出在一個有限邊界的移動空間中，節(jié)點相遇間隔時間服從指數(shù)分布，如果去掉有限邊界的條件，按照 RW模型移動的節(jié)點相遇間隔就與統(tǒng)計觀察到的結果相一致，服從近似冪律分布。 基于社區(qū)的移動模型 人所攜帶設備組成的網(wǎng)絡是機會網(wǎng)絡的一個主要應用，探索適用于這類場景且便于數(shù)學分析的移動模型機會網(wǎng)絡研究的一個重點。基于由人組成的機會網(wǎng)絡節(jié)點移動實際表現(xiàn)出的社區(qū)特性，一些研究人員提出了基于社區(qū)的移動模型(munity based model)。該模型 下的節(jié)點并不是隨機選取移動位置，而是考慮了 3種情況來決策下一步移動位置： 1)節(jié)點偏好，節(jié)點比其他節(jié)點更傾向于去往某個特定位置或遇到特定節(jié)點 。； 2)節(jié)點異構性 :某些節(jié)點能夠到達所有位置，遇到所有其他節(jié)點； 3)行為時變性 :節(jié)點移動隨著時間變化。 Musolesi等人 [17]結合社會網(wǎng)絡理論提出了一種基于社區(qū)的移動模型。該模型根據(jù)節(jié)點之間聯(lián)系的緊密程度，中北大學 2022 屆畢業(yè)設計說明書 第 9 頁 共 57 頁 將節(jié)點分布在多個在不同區(qū)域的社區(qū)，然后計算不同社區(qū)對每個節(jié)點的吸引力，并以此確定節(jié)點是否移動以及朝哪個目標區(qū)域移動。 Spyropoulos 等人 [18,19]提出了時變的社區(qū)移動模型，每個節(jié)點的工作周期由正常移動周期和集中移動周期組成，每個周期內，節(jié)點隨機選擇一個社區(qū)作為它的本地社區(qū)。節(jié)點在每個周期都有兩種移動狀態(tài)， Local epoch和 Roaming epoch。前者是選擇在本地社區(qū)內移動，后者是在其他地方漫游。節(jié)點在兩個狀態(tài)之間以一定的概率來切換，形成一個馬爾可夫鏈，概率大小由所處的移動周期來確定。例如，在集中移動周期內，節(jié)點訪問本地社區(qū)的概率較高。 網(wǎng)絡編碼的概念思想 在傳統(tǒng)網(wǎng)絡中，結點僅對接收的數(shù)據(jù)進行存儲和轉發(fā)，難以達到網(wǎng)絡傳輸?shù)淖畲笸掏铝亢蛶?利用率，若數(shù)據(jù)傳輸路徑出現(xiàn)瓶頸鏈路，則網(wǎng)絡數(shù)據(jù)傳輸性能將受限于瓶頸鏈路。對此，在網(wǎng)絡中引入網(wǎng)絡編碼技術，增加結點對數(shù)據(jù)的編碼運算功能，節(jié)約網(wǎng)絡鏈路的帶寬資源，減小網(wǎng)絡數(shù)據(jù)傳輸中瓶頸鏈路的影響。 網(wǎng)絡編碼 (work coding)是一種融合編碼和路由的信息交換技術，在傳統(tǒng)存儲轉發(fā)的路由方法基礎上，通過允許對接收的多個數(shù)據(jù)包進行編碼信息融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡整體性能。 Ahlswede等人于 2022年提出了網(wǎng)絡編碼概念，指出對組播網(wǎng)絡中的某些節(jié)點附加額外的編碼操作能使源與組播成員間達到最大流最 小割心的組播速率。網(wǎng)絡編碼一經(jīng)提出便引起了國際學術界的廣泛關注，其理論和應用已成為通信領域研究的新熱點．網(wǎng)絡編碼在提高網(wǎng)絡吞吐量、改善負載均衡、減小傳輸延遲、節(jié)省節(jié)點能耗、增強網(wǎng)絡魯棒性等方面均顯示出其優(yōu)越性，可廣泛應用于 Ad Hoe網(wǎng)絡，傳感器網(wǎng)絡、 P2P內容分發(fā)、分布式文件存儲和網(wǎng)絡安全等領域。經(jīng)過幾年的發(fā)展，網(wǎng)絡編碼的理論研究已取得重要進展，在應用基礎和工程實踐方面的研究正在全方位展開。網(wǎng)絡編碼已成為一項融合信息論、代數(shù)學、圖論、網(wǎng)絡流理論和優(yōu)化理論等多學科的交叉技術，且日益引起更多研究者的關注，其對 現(xiàn)有的網(wǎng)絡體系結構、協(xié)議設計方法、信息交換方式和網(wǎng)絡管理模式帶來了革命性的變化。 網(wǎng)絡編碼的基本思想是使網(wǎng)絡中的節(jié)點不僅具有存儲轉發(fā)的功能，他們還能夠打若干個待轉發(fā)的數(shù)據(jù)包進行編碼壓縮成一個數(shù)據(jù)包，然后轉發(fā)給相應的接收節(jié)點，并且以足夠大的概率保證它的接收節(jié)點能夠順利地解碼恢復出原始的數(shù)據(jù)中北大學 2022 屆畢業(yè)設計說明書 第 10 頁 共 57 頁 包，從而減少傳輸次數(shù)，提高網(wǎng)絡吞吐量，降低網(wǎng)絡延遲。 以一個簡單的具代表性的蝴蝶網(wǎng)絡來描述網(wǎng)絡編碼的思想，一下均假設每條鏈路單位時間只能傳輸單位 bit的數(shù)據(jù)數(shù)據(jù)信息量。 圖 態(tài)，該網(wǎng)絡有一個源節(jié)點 S，兩個端節(jié)點 Y， Z以及其余 4個 T,W,U,X是四個中轉節(jié)點。在圖 ， b1和b2都是源 s向端節(jié)點 y和 x發(fā)出的兩個單位 bit的信息，當 b1和 b2到達 w節(jié)點時，由于一次只能處理一個單位的信息，所以 W只能選擇發(fā)送其中之一，而另一個則必須送入等待隊列，因此，要使 Y和 Z這兩個目的節(jié)點都要收到這兩個信息，則 W必須至少傳送兩次；圖 ，節(jié)點 W對輸入的信息進行網(wǎng)絡編碼操作（“ +”表示模二加），然后將操作結果 b1 + b2（稱為編碼信息）發(fā)送至輸出鏈路(W,X)，然后又通過 鏈路 (X,Y)和 (X,Z)，最終傳送給信宿 Y 和 Z。當信宿 Y 收到 b1 和 b1 + b2后，通過逆過程的譯碼操作 b1 + (b 1 + b 2)就能恢復出信源 S 發(fā)出的 b2，這樣使得信宿 Y 同時收到了 b1 和 b2。按照同樣的方式，信宿 Z 也可恢復出信源發(fā)出的 b1（通過譯碼操作 b 2 + (b 1 + b2)）而同時收到 b1 和 b2。也就是說，基于網(wǎng)絡編碼的數(shù)據(jù)分發(fā)模式實現(xiàn)了該組播的理論傳輸容量?？梢姡c傳統(tǒng)的路由傳輸方式相比，網(wǎng)絡編碼提升了網(wǎng)絡的吞吐量。 圖 網(wǎng)絡結構 圖 普通的存儲轉發(fā) 圖 運用網(wǎng)絡編碼 從上述實例可以看出，基于網(wǎng)絡編碼的數(shù)據(jù)分發(fā)的具體實施過程是：具備編碼條件的中間節(jié)點（比如該節(jié)點的入度至少為 2，如圖 W 就具備編碼條件，節(jié)點 T， U 和 X 等則不具備編碼條件，只能執(zhí)行存儲和轉發(fā)操作）對接收到的數(shù)據(jù)信息按照一定方式的處理（編碼），然后傳輸給下一級的網(wǎng)絡節(jié)點，收到信息的下一級節(jié)點如果具備編碼條件，又對其接收的信息按照同樣的方式進行中北大學 2022 屆畢業(yè)設計說明書 第 11 頁 共 57 頁 處理和傳輸，如此反復，直到所有經(jīng)過處理后的信息都匯聚到信宿節(jié)點為止。最后，在 信宿節(jié)點，通過逆過程的操作（譯碼），即可譯出信源發(fā)出的原始信息。 節(jié)點對傳輸?shù)男畔⑦M行如何處理和操作，屬于網(wǎng)絡編碼的碼構造問題。如果節(jié)點對傳輸?shù)男畔⑦M行線性操作，則稱為線性網(wǎng)絡編碼；否則稱為非線性網(wǎng)絡編碼（ Nonlinear Network Coding）。如果網(wǎng)絡節(jié)點對信息進行操作的系數(shù)是隨機選取的，則稱為隨機網(wǎng)絡編碼；如果是通過算法確定出來的，則稱為確定性網(wǎng)絡編碼。因此，線性網(wǎng)絡編碼是一種有效的網(wǎng)絡編碼碼構造方式，當前具體的基于網(wǎng)絡編碼的數(shù)據(jù)分發(fā)系統(tǒng)中均采用線性網(wǎng)絡編碼作為其碼構造方式。圖 所示的節(jié)點 W對輸入的信息 b1 和 b2 進行的模二加操作，就是一種最簡單的線性網(wǎng)絡編碼操作方式。 網(wǎng)絡編碼的應用 雖然網(wǎng)絡編碼提出的初衷是為改善組播傳輸網(wǎng)絡中數(shù)據(jù)分發(fā)系統(tǒng)的傳輸性能，但隨著研究的不斷深入，網(wǎng)絡編碼表現(xiàn)出了越來越廣泛的應用前景。目前，網(wǎng)絡編碼與覆蓋網(wǎng)絡（ Overlay Network）和無線網(wǎng)絡（ Wireless Network）等相結合的研究取得了重要的進展，被認為是網(wǎng)絡編碼最有可能被首先應用的領域。 數(shù)據(jù)分發(fā) 網(wǎng)絡編碼最直接的應用就是數(shù)據(jù)分發(fā)，尤其是大范圍的數(shù)據(jù)分發(fā)。前面討論的基于 組播網(wǎng)絡的數(shù)據(jù)分發(fā)，均是網(wǎng)絡編碼最典型的應用。 Chou 等最早將隨機網(wǎng)絡編碼付諸實施，構建了一個可實用化的網(wǎng)絡編碼數(shù)據(jù)分發(fā)系統(tǒng)，并在 Washington 大學的 Rocketfuel 項目所獲得的幾個 ISP 骨干網(wǎng)絡拓撲上進行了仿真，取得了較好的傳輸性能。 CodedStream 也是在網(wǎng)絡中較早進行了基于網(wǎng)絡編碼的數(shù)據(jù)分發(fā)的嘗試 [71]， CodedStream 是一個基于 P2P 模式的，面向高帶寬流媒體的數(shù)據(jù)分發(fā)系統(tǒng)。它按照編碼網(wǎng)絡分發(fā)數(shù)據(jù)的特性，在覆蓋網(wǎng)絡上構建一個 Kredundant 路徑圖作為網(wǎng)絡 拓撲，網(wǎng)絡編碼被用于圖中“瓶頸”處的數(shù)據(jù)分發(fā)。最初的 CodedStream 在自己的仿真平臺上進行了測試，其后續(xù)研究將整個思想進一步擴展，并利用 PlaLab 平臺進行了更廣泛的測試。 網(wǎng)絡編碼與應用層組播（ Application Layer Multicast， ALM）相結合也取得一定進展。應用層組播中的數(shù)據(jù)分發(fā)由客戶端主機實現(xiàn)的，端主機具有一定的計算能力，這為網(wǎng)絡編碼提供了良好的應用環(huán)境。而且，應用層組播利用的覆蓋中北大學 2022 屆畢業(yè)設計說明書 第 12 頁 共 57 頁 網(wǎng)絡拓撲可以按需變化，這也恰好可以利用網(wǎng)絡編碼對動態(tài)網(wǎng)絡適應性強的優(yōu)勢。Y. Zhu 給出了一個基于網(wǎng)絡編碼的應用層組播的完整實現(xiàn)。通過對比測試，證明了基于網(wǎng)絡編碼的應用層組播在網(wǎng)絡吞吐量、資源利用率等方面的性能要優(yōu)于網(wǎng)絡層組播和普通的應用層組播。但是在傳輸遲延和信息冗余等方面不夠理想。而且，大多數(shù)情況下，網(wǎng)絡編碼能將應用層組播的吞吐量提升一倍以上。但是， T. Nad等通過進一步的實驗證實，由于在執(zhí)行編碼和譯碼操作時需要一定的 I/O 和 CPU消耗，基于網(wǎng)絡編碼的應用層組播的傳輸容量往往無法達到預期。 無線網(wǎng)絡 由于無線鏈路的不可靠性和物理層廣播特性，應用網(wǎng)絡編碼，可以解決傳統(tǒng)路由、跨層設計 等技術無法解決的問題。具體來說，網(wǎng)絡編碼除了提升無線網(wǎng)絡的網(wǎng)絡吞吐量，還可以減少數(shù)據(jù)包的傳播次數(shù)，降低無線發(fā)送能耗。采用隨機網(wǎng)絡編碼，即使部分網(wǎng)絡節(jié)點或鏈路失效，最終在目的節(jié)點仍然能恢復原始數(shù)據(jù)，從而增強網(wǎng)絡的容錯性和魯棒性。此外，無需復雜的加密算法，采用網(wǎng)絡編碼就可以提高無線網(wǎng)絡的安全性等。文獻 [20]對網(wǎng)絡編碼在無線自組織網(wǎng)絡（ WirelessAd Hoc Networks）、無線傳感器網(wǎng)絡（ Wireless Sensor Networks）和無線網(wǎng)狀網(wǎng) (Wireless Mesh Networks)中 的應用進行了探討。 J. Yuan提出了一種利用網(wǎng)絡編碼來優(yōu)化信息流的路由方法 [21]，以此來提升Ad Hoc 網(wǎng)絡中數(shù)據(jù)分發(fā)的效率。該方法基于一種在網(wǎng)絡層和物理層平衡鏈路帶寬供需的跨層優(yōu)化策略。 Ad Hoc組播方面提出了應用網(wǎng)絡編碼的最小化能量解決方法 [22]，使得傳輸每比特信息消耗的能量最小，以此來節(jié)省 Ad Hoc網(wǎng)絡中數(shù)據(jù)分發(fā)的能耗。此外，還有一些學者對如何利用網(wǎng)絡編碼增加 Ad Hoc傳輸?shù)聂敯粜詥栴}進行了研究，如 Chen 等研究在分布式天線系統(tǒng)和多入多出系統(tǒng)（ DASMIMO）中，引入網(wǎng)絡編 碼的概念，經(jīng)過理論推導和實驗仿真，證明了無論有無輔助天線，網(wǎng)絡編碼都能提高網(wǎng)絡的性能，尤其是減小系統(tǒng)丟包損耗。 相對于 Ad Hoc 網(wǎng)絡，無線傳感器網(wǎng)絡密度較大，移動性不強，通常運行在無人值守的惡劣甚至危險的遠程環(huán)境中，能源無法替代，設計有效的策略延長網(wǎng)絡的生命周期成為無線傳感器網(wǎng)絡的核心問題。麻省理工學院的 Petrovic 等人提出了一種結合網(wǎng)絡編碼的對無線信號不進行調制的策略 [23]，并證明：運用分布式隨機網(wǎng)絡編碼，未經(jīng)調制的無線信號能夠達到與經(jīng)過調制的無線信號一樣的吞吐中北大學 2022 屆畢業(yè)設計說明書 第 13 頁 共 57 頁 量，這樣就能節(jié)省大量因為模擬器件進行 調制而消耗的能量和降低節(jié)點的成本。傳感器網(wǎng)絡