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