《基于網(wǎng)絡(luò)編碼的機(jī)會網(wǎng)絡(luò)數(shù)據(jù)分發(fā)研究與仿真畢業(yè)設(shè)計說明書》由會員分享，可在線閱讀，更多相關(guān)《基于網(wǎng)絡(luò)編碼的機(jī)會網(wǎng)絡(luò)數(shù)據(jù)分發(fā)研究與仿真畢業(yè)設(shè)計說明書（57頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 1 引言1.1 研究問題現(xiàn)狀近年來，無線通信技術(shù)得到了飛速的發(fā)展，新技術(shù)不斷出現(xiàn)，其中移動通信系統(tǒng)的3G技術(shù)已經(jīng)進(jìn)入應(yīng)用普及階段，并朝第四代通信系統(tǒng)方向演進(jìn)。國家中長期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要(2006一2020)中已經(jīng)明確提出了未來通信領(lǐng)域的競爭將集中反映在特殊環(huán)境和新興應(yīng)用領(lǐng)域中的通信網(wǎng)絡(luò)能力及通信技術(shù)的競爭上1。其中新興應(yīng)用領(lǐng)域涉及到的移動網(wǎng)絡(luò)技術(shù)更是被作為前沿技術(shù)中的重點。目前,移動通信的快速發(fā)展使得移動網(wǎng)絡(luò)帶寬逐漸增大，移動應(yīng)用不斷豐富，移動終端的處理能力越來越強(qiáng)。為了適應(yīng)不同的應(yīng)用需求,各具特色的網(wǎng)絡(luò)結(jié)構(gòu)和無線網(wǎng)絡(luò)技術(shù)不斷涌現(xiàn),包括無線個域網(wǎng)(如IEEE802.15)、無線局域網(wǎng)(

2、如IEEE802.lla/b/g/i/n)、無線城域網(wǎng)(如802.16、802.20)、無線移動廣域網(wǎng)(如2G、3G)、衛(wèi)星網(wǎng)絡(luò)，以及無線自組織(Ad Hoc)網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)等等。而WIFi、WIMax、UWB等無線接入網(wǎng)絡(luò)和GPRS、B3G、UMTS等蜂窩移動網(wǎng)絡(luò)等基礎(chǔ)設(shè)施與技術(shù)的完善為移動應(yīng)用提供了在任何時間、任何地點訪問所有網(wǎng)絡(luò)服務(wù)的可能性。在上述的各種網(wǎng)絡(luò)發(fā)展后，一種節(jié)點移動范圍更大，網(wǎng)絡(luò)大多數(shù)都是不連通的新型網(wǎng)絡(luò)出現(xiàn)了，這種類型的網(wǎng)絡(luò)被稱為機(jī)會網(wǎng)絡(luò)，機(jī)會網(wǎng)絡(luò)是一種不需要源節(jié)點和目的節(jié)點之間存在完整路徑，利用節(jié)點移動帶來的

3、相遇機(jī)會實現(xiàn)網(wǎng)絡(luò)通信的自組織網(wǎng)絡(luò)。經(jīng)過近幾年的發(fā)展，機(jī)會網(wǎng)絡(luò)技術(shù)研究與應(yīng)用已經(jīng)取得了一定的進(jìn)展，但是，總體而言目前相關(guān)研究還處于一個剛起步的初級階段。隨著移動應(yīng)用業(yè)務(wù)的增加以及機(jī)會網(wǎng)絡(luò)商業(yè)化，機(jī)會網(wǎng)絡(luò)技術(shù)的全面應(yīng)用與深入仍然要解決很多極具挑戰(zhàn)性的問題，如復(fù)雜環(huán)境下的路由、數(shù)據(jù)時延與網(wǎng)絡(luò)開銷均衡問題、移動狀態(tài)下網(wǎng)絡(luò)可靠性以及安全問題等等。同時在一些領(lǐng)域，機(jī)會網(wǎng)絡(luò)的相關(guān)技術(shù)標(biāo)準(zhǔn)尚未形成，尤其在國內(nèi)對于這類高延遲的特殊通信網(wǎng)絡(luò)的研究才剛剛起步。規(guī)劃信息化發(fā)展戰(zhàn)略中不僅強(qiáng)調(diào)了信息產(chǎn)業(yè)以及信息技術(shù)的發(fā)展，同時也提出了將寬帶無線移動通信、新興及特殊應(yīng)用領(lǐng)域的網(wǎng)絡(luò)通信等核心關(guān)鍵技術(shù)研究作為我國信息技術(shù)的主要

4、發(fā)展方向之一。因此，對機(jī)會網(wǎng)絡(luò)數(shù)據(jù)分發(fā)展開研究將為正確理解機(jī)會網(wǎng)絡(luò)拓?fù)渑c數(shù)據(jù)傳輸特點提供可行性依據(jù)，有助于推進(jìn)現(xiàn)有關(guān)鍵技術(shù)的可擴(kuò)展性，并對提高機(jī)會網(wǎng)絡(luò)數(shù)據(jù)傳輸可靠性，探索節(jié)點移動模型對機(jī)會網(wǎng)絡(luò)服務(wù)性能保障的影響，推動相關(guān)技術(shù)的深入研究有重要現(xiàn)實的意義。2000年,R.Ahlswede等人基于網(wǎng)絡(luò)信息流的概念提出了網(wǎng)絡(luò)編碼的思想，通過允許中間節(jié)點既實現(xiàn)路由功能又實現(xiàn)編碼功能，達(dá)到組播的最大流量2。為使得網(wǎng)絡(luò)編碼具有實際可用性，Li等人提出了線性網(wǎng)絡(luò)編碼的概念，證實節(jié)點進(jìn)行線性網(wǎng)絡(luò)編碼運算，具有可行性，能夠達(dá)到最大流傳輸理論極限3。Ho等人推廣了這一概念，提出了有限域下隨機(jī)線性網(wǎng)絡(luò)編碼的思想，并證

5、實其有效性4。之后，隨機(jī)線性網(wǎng)絡(luò)編碼被應(yīng)用于各個方面的研究，用于提高網(wǎng)絡(luò)吞吐量、能量利用效率。網(wǎng)絡(luò)編碼徹底改變了通信網(wǎng)絡(luò)中信息處理和信息傳輸?shù)姆绞?，被認(rèn)為是進(jìn)入 21世紀(jì)后信息處理和信息傳輸研究領(lǐng)域上最重要的理論成果之一。網(wǎng)絡(luò)編碼的核心思想是允許通信網(wǎng)絡(luò)中的節(jié)點對傳輸?shù)男畔⑦M(jìn)行操作和處理（如有限域中的運算等），而不再局限于存儲與轉(zhuǎn)發(fā)。與傳統(tǒng)的基于存儲和轉(zhuǎn)發(fā)的路由傳輸機(jī)制相比，網(wǎng)絡(luò)編碼能顯著改善數(shù)據(jù)分發(fā)系統(tǒng)性能，如提升網(wǎng)絡(luò)吞吐量，節(jié)約傳輸帶寬和均衡網(wǎng)絡(luò)負(fù)載等。網(wǎng)絡(luò)編碼具有重要的理論價值和廣泛的應(yīng)用前景，其研究已經(jīng)引起了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注和高度重視。國際知名大學(xué)、科研機(jī)構(gòu)和公司，如普林斯頓大

6、學(xué)、麻省理工學(xué)院（MIT）、貝爾實驗室（Bell Lab）、AT&T 的香農(nóng)信息實驗室和微軟公司（Microsoft）等都積極投入對網(wǎng)絡(luò)編碼的研究，并取得了一些重要的研究成果。我國的香港中文大學(xué)（CUHK）、清華大學(xué)、中國科學(xué)技術(shù)大學(xué)、西安電子科技大學(xué)和南京大學(xué)等也對網(wǎng)絡(luò)編碼展開了研究，并取得一定的進(jìn)展。機(jī)會網(wǎng)絡(luò)經(jīng)常出現(xiàn)鏈路斷裂，網(wǎng)絡(luò)不連通的狀況，在這種情況下，節(jié)點一般并不丟棄數(shù)據(jù)包，相反節(jié)點傳輸數(shù)據(jù)一般采用“存儲一攜帶一轉(zhuǎn)發(fā)”的模式，傳統(tǒng)的機(jī)會網(wǎng)絡(luò)中，中間節(jié)點只進(jìn)行數(shù)據(jù)的存儲與轉(zhuǎn)發(fā)操作，但是運用網(wǎng)絡(luò)編碼的機(jī)會網(wǎng)絡(luò)中，中間節(jié)點可以對接收到的數(shù)據(jù)塊進(jìn)行隨機(jī)線性組合編碼，可以增大單次傳輸?shù)臄?shù)據(jù)量。

7、隨著網(wǎng)絡(luò)規(guī)模的日趨龐大、各種網(wǎng)絡(luò)方案和協(xié)議日趨復(fù)雜，分析、實驗和仿真等方法成為了當(dāng)前進(jìn)行網(wǎng)絡(luò)技術(shù)研究的有效手段。研究網(wǎng)絡(luò)仿真技術(shù)成為了現(xiàn)代通信網(wǎng)絡(luò)設(shè)計的重要環(huán)節(jié)，在通信網(wǎng)絡(luò)性能研究中起關(guān)鍵性作用。在眾多網(wǎng)絡(luò)仿真軟件中NS2具有免費、源代碼開放、易擴(kuò)展等等優(yōu)點而備受研究人員的青睞。NS2是一個開源的網(wǎng)絡(luò)仿真軟件，可以再windows/unix上運行，且所有源代碼公開，對于進(jìn)行網(wǎng)絡(luò)的研究和擴(kuò)展非常方便。本課題研究的內(nèi)容就是在仿真平臺NS2下設(shè)計并建立機(jī)會網(wǎng)絡(luò)模型，理解網(wǎng)絡(luò)編碼的原理，在NS2中編程實現(xiàn)基于分簇的隨機(jī)線性網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)的仿真并與一般的網(wǎng)絡(luò)編碼比較其網(wǎng)絡(luò)吞吐量和時延性能。1.2 本文

8、的內(nèi)容組織本文內(nèi)容組織如下：先分別介紹了機(jī)會網(wǎng)絡(luò)、網(wǎng)絡(luò)編碼原理及仿真平臺NS2的各種知識，然后使用NS2構(gòu)建機(jī)會網(wǎng)絡(luò)拓?fù)?，編出各個代碼腳本，在NS2上仿真實驗，得出數(shù)據(jù)并畫圖進(jìn)行說明驗證。2 機(jī)會網(wǎng)絡(luò)及網(wǎng)絡(luò)編碼相關(guān)知識2.1 機(jī)會網(wǎng)絡(luò)的概念機(jī)會網(wǎng)絡(luò)是一種特殊的自組織網(wǎng)絡(luò)，它不需要存在端到端的完整路徑，充分利用了節(jié)點移動帶來的相遇機(jī)會（contact），實現(xiàn)數(shù)據(jù)逐跳轉(zhuǎn)發(fā)，并最終傳送到目的節(jié)點5。從本質(zhì)上來看，機(jī)會網(wǎng)絡(luò)否定了傳統(tǒng)網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)囊粋€根本前提在路由期間或者數(shù)據(jù)傳遞期間，存在一條或者多條源端到目的端的路徑。機(jī)會網(wǎng)絡(luò)中的相遇（contact）概念是指節(jié)點之間發(fā)生的一次聯(lián)系。當(dāng)節(jié)點（如：車

9、輛、移動用戶）進(jìn)入彼此的通信范圍之內(nèi)時，則發(fā)生通信，當(dāng)兩者離開彼此通信范圍時，則鏈路斷開，停止通信。在機(jī)會網(wǎng)絡(luò)中，contact是機(jī)會性的，而非確定性的。圖2.1是一個機(jī)會網(wǎng)絡(luò)示意圖，t1時刻源節(jié)點S希望將數(shù)據(jù)傳輸給目標(biāo)節(jié)點D，但S 和D 位于不同的連通域而沒有通信路徑，因此，S 首先將數(shù)據(jù)打包成消息發(fā)送給鄰居節(jié)點3，由于3并沒有合適的機(jī)會轉(zhuǎn)發(fā)下一跳節(jié)點，它將消息在本地存儲并等待傳輸機(jī)會，經(jīng)過一段時間到達(dá)t2 時刻，節(jié)點3運動到節(jié)點4的通信范圍并轉(zhuǎn)發(fā)給節(jié)點4，在t3時刻，節(jié)點4將消息傳輸給目標(biāo)節(jié)點D，完成數(shù)據(jù)傳輸。圖2.1 機(jī)會網(wǎng)絡(luò)示意圖機(jī)會網(wǎng)絡(luò)的部分概念來源于早期的延遲容忍網(wǎng)絡(luò)DTN(del

10、ay tolerant network)6研究。DTN最初是容遲網(wǎng)絡(luò)研究組(DTNRG)為星際網(wǎng)絡(luò)IPN(interplanetary network)7通信而提出來的，其主要目標(biāo)是支持具有間歇性連通、延遲大、錯誤率高等通信特征的不同網(wǎng)絡(luò)的互聯(lián)和互操作，如互聯(lián)Internet和傳感器網(wǎng)絡(luò)、移動自組織網(wǎng)絡(luò)等。DTN網(wǎng)絡(luò)體系由多個底層運行獨立通信協(xié)議的DTN域組成。域間網(wǎng)關(guān)利用“存儲-轉(zhuǎn)發(fā)”的模式工作，當(dāng)去往目標(biāo)DTN域的鏈路存在時轉(zhuǎn)發(fā)消息，否則，將消息存儲在本地持久存儲器中等待可用鏈路。機(jī)會網(wǎng)絡(luò)可以看成是具有一般DTN 網(wǎng)絡(luò)特征的無線自組網(wǎng)。2.2 機(jī)會網(wǎng)絡(luò)的構(gòu)架機(jī)會網(wǎng)絡(luò)的體系結(jié)構(gòu)與傳統(tǒng)Inte

11、rnet傳輸結(jié)構(gòu)的最大區(qū)別在于束層（BundleLayer），它位于傳輸層和應(yīng)用層之間，它跟底層協(xié)議相互配合，使得應(yīng)用程序可以跨過多個區(qū)域?qū)崿F(xiàn)通信。機(jī)會網(wǎng)絡(luò)節(jié)點使用束層來發(fā)送和接受數(shù)據(jù)，并保證逐跳轉(zhuǎn)發(fā)的可靠性以及端到端的確認(rèn)。該架構(gòu)非常靈活，既保證了各層的共性，又避免非法使用其他層。1、束層為了實現(xiàn)“存儲-攜帶-轉(zhuǎn)發(fā)”的消息交換機(jī)制，機(jī)會網(wǎng)絡(luò)在節(jié)點的應(yīng)用層和傳輸層之間插入了一個新的協(xié)議層束層。使用束層的一個主要原因是在機(jī)會網(wǎng)絡(luò)中，傳輸延時差異很大，當(dāng)一個數(shù)據(jù)包丟失時，整個傳輸?shù)臄?shù)據(jù)成為無用數(shù)據(jù)。因此為了避免這樣的事情發(fā)生，將數(shù)據(jù)打包成一個較大的消息，稱之為束，并使之不能輕易分割成更小的片段。機(jī)

12、會網(wǎng)絡(luò)中一般不存在從源節(jié)點到目的節(jié)點的端到端的連接，因此束會存儲在中繼節(jié)點上并等待合適機(jī)會進(jìn)行傳輸。一個束必須包含的信息有：源端地址、目的端地址、起始時間、束的生存時間、數(shù)據(jù)長度及服務(wù)類型等。此外，對于具體的應(yīng)用，可能還需要一些狀態(tài)域和認(rèn)證消息，例如，監(jiān)管傳送請求等。2、監(jiān)管傳送束層提供了一種簡單的并且不需要應(yīng)答的投遞機(jī)制，但框架本身提供了兩種可能的方法來提高可靠性：端到端的應(yīng)答和監(jiān)管傳送。通過監(jiān)管傳送，可以保證端到端的可靠性。在特定的環(huán)境下，這種機(jī)制可以更好地利用資源，例如源節(jié)點可以將已經(jīng)投遞成功的束在緩存中釋放掉。3、機(jī)會網(wǎng)絡(luò)中的節(jié)點一個束的源端和目的端是由端點號EID（Endpoint-

13、Identifier）來標(biāo)識的。EID中包含一個或多個機(jī)會網(wǎng)絡(luò)節(jié)點。當(dāng)目的地收到該束時，認(rèn)為該束傳遞成功。EID可以類比于DNS（Domain Name System）中的統(tǒng)一資源標(biāo)識（URI，Uniform Resource Identifier），并且與路由或拓?fù)浣M織結(jié)構(gòu)沒有必然聯(lián)系。區(qū)域名是早先提出的一個概念，一個完整的地址由區(qū)域號和節(jié)點號組成?；谶@種區(qū)域的概念，束首先投遞到目的節(jié)點所在的區(qū)域，然后再投遞到目的節(jié)點。4、服務(wù)分類按重要性不同，束層引入了三類服務(wù)：1、大塊束（bulk bundles），只需要較小的投入，當(dāng)有資源可用時就可以提供這種服務(wù)；2、正常束（normal clas

14、s bundles），比大塊束優(yōu)先級要高，但比“加快束”（expedited bundles）優(yōu)先級要低；3、加快束，這類服務(wù)只是針對來自同一個端點的束而言，例如：當(dāng)大塊束與加快束來自不同的端點時，即使加快束比大塊束優(yōu)先級高，但大塊束仍有可能比加快束先傳遞。5、安全機(jī)會網(wǎng)絡(luò)框架提供了一個可選的安全構(gòu)架，使用逐跳、端到端的授權(quán)和誠信機(jī)制，主要的困難是如何對網(wǎng)絡(luò)進(jìn)行控制和如何轉(zhuǎn)發(fā)控制消息。沒有進(jìn)行認(rèn)證的節(jié)點不能夠通過機(jī)會網(wǎng)絡(luò)發(fā)送數(shù)據(jù)，并且不能利用該網(wǎng)絡(luò)以外的節(jié)點進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。2.3 機(jī)會網(wǎng)絡(luò)拓?fù)涮攸c1、多跳網(wǎng)由于無線通信的距離受限制，機(jī)會網(wǎng)絡(luò)中節(jié)點之間的通信通常需要借助其他節(jié)點的中繼轉(zhuǎn)發(fā)才能實現(xiàn)，

15、便形成了多跳通信路徑。2、動態(tài)的網(wǎng)絡(luò)拓?fù)錂C(jī)會網(wǎng)絡(luò)中節(jié)點間的相互連通性構(gòu)成了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。由于機(jī)會網(wǎng)絡(luò)中的節(jié)點可以以隨機(jī)的速度和方式移動，加上發(fā)射功率的變化，以及無線信道的干擾大小不斷變化等因素，節(jié)點間通過無線通信形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能隨時發(fā)生變化，而且變化的方式和速度都是難以預(yù)料的。3、分布式控制在機(jī)會網(wǎng)絡(luò)中，為了實現(xiàn)網(wǎng)內(nèi)節(jié)點之間的通信，需要解決無線資源使用、路由發(fā)現(xiàn)等控制問題。由于機(jī)會網(wǎng)絡(luò)沒有預(yù)設(shè)的基礎(chǔ)設(shè)施，也就沒有預(yù)設(shè)的中心控制節(jié)點，所以只能采用分布式控制的方式來完成。4、對等性機(jī)會網(wǎng)絡(luò)中節(jié)點與節(jié)點可以直接互通，每個節(jié)點都相同，無主從之分，每個節(jié)點都能夠支持邏輯上的自發(fā)自收，即節(jié)點直接的

16、來去雙向鏈路都相同。因此，無機(jī)會網(wǎng)絡(luò)節(jié)點的無線通信裝置一般采用時分雙工方式（TDD）。5、臨時自組織性若干個無線節(jié)點聚集到一起時，他們便臨時自組織性地形成了一個無線通信網(wǎng)絡(luò)，該臨時性包括：網(wǎng)絡(luò)成員的臨時性，網(wǎng)絡(luò)組織的臨時性，網(wǎng)絡(luò)拓?fù)涞呐R時性，網(wǎng)絡(luò)路由的臨時性，網(wǎng)絡(luò)無線資源分配采用按需臨時分配等。6、鏈路帶寬受限機(jī)會網(wǎng)絡(luò)采用無線傳輸技術(shù)作為其基本通信手段，與有線傳輸技術(shù)相比，它具有較低的傳輸帶寬。并且由于各個節(jié)點分布式競爭使用信道，使得每個移動節(jié)點實際使用的帶寬遠(yuǎn)小于物理層所提供的最大傳輸速率。7、能量受限機(jī)會網(wǎng)絡(luò)內(nèi)的移動節(jié)點一般需要依靠電池來提供能量，因此，節(jié)省功率將使自組網(wǎng)技術(shù)中一個需要高度

17、重視的問題。8、有限的安全性機(jī)會網(wǎng)絡(luò)由于采用分布式控制、無中心、臨時組織等原因，它比一般的無線網(wǎng)絡(luò)更易受到安全方面的威脅。2.4 機(jī)會網(wǎng)絡(luò)節(jié)點移動模型節(jié)點移動模型描述了節(jié)點的移動模式，包括位置、速度等特征的變化，廣泛應(yīng)用于自組網(wǎng)協(xié)議性能的分析和評價，是自組織網(wǎng)絡(luò)的基礎(chǔ)研究之一。傳統(tǒng)的MANET假設(shè)網(wǎng)絡(luò)是全連通的，節(jié)點的移動對路由層以上的協(xié)議是“屏蔽”的。因此一般從網(wǎng)絡(luò)拓?fù)浣嵌热シ治鲆苿幽Ｐ蛯f(xié)議性能的影響，如拓?fù)溥B通率、節(jié)點連通度等，而機(jī)會網(wǎng)絡(luò)中的移動模型研究是以刻畫節(jié)點相遇特征為核心的。這是因為在機(jī)會網(wǎng)絡(luò)中的數(shù)據(jù)傳輸依賴于節(jié)點移動帶來的相遇機(jī)會，而節(jié)點的相遇概率和相遇時間分布是由節(jié)點的移動模

18、型決定的。因此，相比于傳統(tǒng)的MANET，移動模型對機(jī)會網(wǎng)絡(luò)研究更加重要。2.4.1 獨立同分布的理論移動模型許多學(xué)者研究了3個經(jīng)典的獨立同分布移動模：Random Way Point8(RWP) Random Walk(RW)和Random Direction9(RD)。這些模型下的節(jié)點相遇特征可用兩個參數(shù)來刻畫：相遇時間(meeting time，簡稱MT)和相遇間隔時間(inter meeting time，簡稱IMT)。MT 是指兩個節(jié)點從靜止開始到第一次相遇(進(jìn)入通信范圍)經(jīng)過的時間間隔，而IMT 是指兩個節(jié)點前后兩次相遇的時間間隔。文獻(xiàn)9都分別從不同的角度證明了上述3個移動模型的節(jié)點

19、期望相遇時間(expected meeting time)服從指數(shù)分布或其尾部服從指數(shù)分布，并基于此分析了多種路由協(xié)議的延時性能。文獻(xiàn)10推導(dǎo)出RW模型下期望相遇間隔時間的分布也服從指數(shù)分布，而文獻(xiàn)11推導(dǎo)了RD模型和RWP模型下的期望相遇間隔時間分布，并證明了RWP和RD模型下相遇時間和相遇間隔時間的尾部分布是無記憶的。2.4.2 基于統(tǒng)計的實際移動模型除了從理論來推導(dǎo)以外，一些研究人員還利用統(tǒng)計方法，通過收集實際環(huán)境中節(jié)點的運動軌跡來研究節(jié)點的移動特征。MIT 的Reality Mining項目12記錄了MIT校園中100個攜帶藍(lán)牙智能手機(jī)的學(xué)生和職工為期9個月的移動軌跡和相遇數(shù)據(jù)；UCS

20、D 的Wireless Topology Discovery13收集了11周內(nèi)300個無線PDA與Wi-Fi接入點的相遇數(shù)據(jù)；劍橋大學(xué)的Haggle項目14則記錄了若干個帶有藍(lán)牙接口的iMote設(shè)備在校園的相遇情況。此外，他們還在INFOCOM參會期間進(jìn)行了類似的實驗；UMass研究小組15收集并分析了由公交車上的Wi-Fi節(jié)點組成的機(jī)會網(wǎng)絡(luò)DieselNet實際運行中的相遇規(guī)律。文獻(xiàn)2通過分析文獻(xiàn)13中的數(shù)據(jù)集發(fā)現(xiàn)，實際節(jié)點的移動具有社區(qū)特性，節(jié)點相遇時間服從近似的冪律分布，而不是根據(jù)經(jīng)典移動模型推導(dǎo)出的指數(shù)分布，這些成果證實了傳統(tǒng)的移動模型并不一定適用于實際節(jié)點的移動特征，但研究人員在對于

21、使用何種分布的移動模型問題上一直存在爭議。文獻(xiàn)16試圖統(tǒng)一這兩種類型的移動模型，作者從理論上推導(dǎo)出在一個有限邊界的移動空間中，節(jié)點相遇間隔時間服從指數(shù)分布，如果去掉有限邊界的條件，按照RW模型移動的節(jié)點相遇間隔就與統(tǒng)計觀察到的結(jié)果相一致，服從近似冪律分布。2.4.3 基于社區(qū)的移動模型人所攜帶設(shè)備組成的網(wǎng)絡(luò)是機(jī)會網(wǎng)絡(luò)的一個主要應(yīng)用，探索適用于這類場景且便于數(shù)學(xué)分析的移動模型機(jī)會網(wǎng)絡(luò)研究的一個重點?；谟扇私M成的機(jī)會網(wǎng)絡(luò)節(jié)點移動實際表現(xiàn)出的社區(qū)特性，一些研究人員提出了基于社區(qū)的移動模型(community based model)。該模型下的節(jié)點并不是隨機(jī)選取移動位置，而是考慮了3種情況來決策下

22、一步移動位置：1)節(jié)點偏好，節(jié)點比其他節(jié)點更傾向于去往某個特定位置或遇到特定節(jié)點;；2)節(jié)點異構(gòu)性:某些節(jié)點能夠到達(dá)所有位置，遇到所有其他節(jié)點；3)行為時變性:節(jié)點移動隨著時間變化。Musolesi等人17結(jié)合社會網(wǎng)絡(luò)理論提出了一種基于社區(qū)的移動模型。該模型根據(jù)節(jié)點之間聯(lián)系的緊密程度，將節(jié)點分布在多個在不同區(qū)域的社區(qū)，然后計算不同社區(qū)對每個節(jié)點的吸引力，并以此確定節(jié)點是否移動以及朝哪個目標(biāo)區(qū)域移動。Spyropoulos 等人18,19提出了時變的社區(qū)移動模型，每個節(jié)點的工作周期由正常移動周期和集中移動周期組成，每個周期內(nèi)，節(jié)點隨機(jī)選擇一個社區(qū)作為它的本地社區(qū)。節(jié)點在每個周期都有兩種移動狀態(tài)，

23、Local epoch和Roaming epoch。前者是選擇在本地社區(qū)內(nèi)移動，后者是在其他地方漫游。節(jié)點在兩個狀態(tài)之間以一定的概率來切換，形成一個馬爾可夫鏈，概率大小由所處的移動周期來確定。例如，在集中移動周期內(nèi)，節(jié)點訪問本地社區(qū)的概率較高。2.5 網(wǎng)絡(luò)編碼的概念思想在傳統(tǒng)網(wǎng)絡(luò)中，結(jié)點僅對接收的數(shù)據(jù)進(jìn)行存儲和轉(zhuǎn)發(fā)，難以達(dá)到網(wǎng)絡(luò)傳輸?shù)淖畲笸掏铝亢蛶捓寐剩魯?shù)據(jù)傳輸路徑出現(xiàn)瓶頸鏈路，則網(wǎng)絡(luò)數(shù)據(jù)傳輸性能將受限于瓶頸鏈路。對此，在網(wǎng)絡(luò)中引入網(wǎng)絡(luò)編碼技術(shù)，增加結(jié)點對數(shù)據(jù)的編碼運算功能，節(jié)約網(wǎng)絡(luò)鏈路的帶寬資源，減小網(wǎng)絡(luò)數(shù)據(jù)傳輸中瓶頸鏈路的影響。網(wǎng)絡(luò)編碼(network coding)是一種融合編碼和

24、路由的信息交換技術(shù)，在傳統(tǒng)存儲轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過允許對接收的多個數(shù)據(jù)包進(jìn)行編碼信息融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡(luò)整體性能。Ahlswede等人于2000年提出了網(wǎng)絡(luò)編碼概念，指出對組播網(wǎng)絡(luò)中的某些節(jié)點附加額外的編碼操作能使源與組播成員間達(dá)到最大流最小割心的組播速率。網(wǎng)絡(luò)編碼一經(jīng)提出便引起了國際學(xué)術(shù)界的廣泛關(guān)注，其理論和應(yīng)用已成為通信領(lǐng)域研究的新熱點網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量、改善負(fù)載均衡、減小傳輸延遲、節(jié)省節(jié)點能耗、增強(qiáng)網(wǎng)絡(luò)魯棒性等方面均顯示出其優(yōu)越性，可廣泛應(yīng)用于Ad Hoe網(wǎng)絡(luò)，傳感器網(wǎng)絡(luò)、P2P內(nèi)容分發(fā)、分布式文件存儲和網(wǎng)絡(luò)安全等領(lǐng)域。經(jīng)過幾年的發(fā)展，網(wǎng)絡(luò)編碼的理論研究已取得

25、重要進(jìn)展，在應(yīng)用基礎(chǔ)和工程實踐方面的研究正在全方位展開。網(wǎng)絡(luò)編碼已成為一項融合信息論、代數(shù)學(xué)、圖論、網(wǎng)絡(luò)流理論和優(yōu)化理論等多學(xué)科的交叉技術(shù)，且日益引起更多研究者的關(guān)注，其對現(xiàn)有的網(wǎng)絡(luò)體系結(jié)構(gòu)、協(xié)議設(shè)計方法、信息交換方式和網(wǎng)絡(luò)管理模式帶來了革命性的變化。網(wǎng)絡(luò)編碼的基本思想是使網(wǎng)絡(luò)中的節(jié)點不僅具有存儲轉(zhuǎn)發(fā)的功能，他們還能夠打若干個待轉(zhuǎn)發(fā)的數(shù)據(jù)包進(jìn)行編碼壓縮成一個數(shù)據(jù)包，然后轉(zhuǎn)發(fā)給相應(yīng)的接收節(jié)點，并且以足夠大的概率保證它的接收節(jié)點能夠順利地解碼恢復(fù)出原始的數(shù)據(jù)包，從而減少傳輸次數(shù)，提高網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)延遲。以一個簡單的具代表性的蝴蝶網(wǎng)絡(luò)來描述網(wǎng)絡(luò)編碼的思想，一下均假設(shè)每條鏈路單位時間只能傳輸單位

26、bit的數(shù)據(jù)數(shù)據(jù)信息量。圖2.3和圖2.4中分別是利用網(wǎng)絡(luò)編碼前后的網(wǎng)絡(luò)傳輸狀態(tài)，該網(wǎng)絡(luò)有一個源節(jié)點S，兩個端節(jié)點Y，Z以及其余4個T,W,U,X是四個中轉(zhuǎn)節(jié)點。在圖2.2中，b1和b2都是源s向端節(jié)點y和x發(fā)出的兩個單位bit的信息，當(dāng)b1和b2到達(dá)w節(jié)點時，由于一次只能處理一個單位的信息，所以W只能選擇發(fā)送其中之一，而另一個則必須送入等待隊列，因此，要使Y和Z這兩個目的節(jié)點都要收到這兩個信息，則W必須至少傳送兩次；圖2.3表示的是網(wǎng)絡(luò)編碼方法，節(jié)點W對輸入的信息進(jìn)行網(wǎng)絡(luò)編碼操作（“+”表示模二加），然后將操作結(jié)果 b1 + b2（稱為編碼信息）發(fā)送至輸出鏈路(W,X)，然后又通過鏈路(X,

27、Y)和(X,Z)，最終傳送給信宿 Y 和 Z。當(dāng)信宿 Y 收到 b1 和 b1 + b2后，通過逆過程的譯碼操作 b1 + (b 1 + b 2)就能恢復(fù)出信源 S 發(fā)出的 b2，這樣使得信宿 Y 同時收到了 b1 和 b2。按照同樣的方式，信宿 Z 也可恢復(fù)出信源發(fā)出的 b1（通過譯碼操作b 2 + (b 1 + b2)）而同時收到 b1 和 b2。也就是說，基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)模式實現(xiàn)了該組播的理論傳輸容量。可見，與傳統(tǒng)的路由傳輸方式相比，網(wǎng)絡(luò)編碼提升了網(wǎng)絡(luò)的吞吐量。 圖2.2 網(wǎng)絡(luò)結(jié)構(gòu) 圖2.3 普通的存儲轉(zhuǎn)發(fā) 圖2.4 運用網(wǎng)絡(luò)編碼從上述實例可以看出，基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)的具體實施

28、過程是：具備編碼條件的中間節(jié)點（比如該節(jié)點的入度至少為 2，如圖2.4中的節(jié)點 W 就具備編碼條件，節(jié)點 T，U 和 X 等則不具備編碼條件，只能執(zhí)行存儲和轉(zhuǎn)發(fā)操作）對接收到的數(shù)據(jù)信息按照一定方式的處理（編碼），然后傳輸給下一級的網(wǎng)絡(luò)節(jié)點，收到信息的下一級節(jié)點如果具備編碼條件，又對其接收的信息按照同樣的方式進(jìn)行處理和傳輸，如此反復(fù)，直到所有經(jīng)過處理后的信息都匯聚到信宿節(jié)點為止。最后，在信宿節(jié)點，通過逆過程的操作（譯碼），即可譯出信源發(fā)出的原始信息。節(jié)點對傳輸?shù)男畔⑦M(jìn)行如何處理和操作，屬于網(wǎng)絡(luò)編碼的碼構(gòu)造問題。如果節(jié)點對傳輸?shù)男畔⑦M(jìn)行線性操作，則稱為線性網(wǎng)絡(luò)編碼；否則稱為非線性網(wǎng)絡(luò)編碼（Non-

29、linear Network Coding）。如果網(wǎng)絡(luò)節(jié)點對信息進(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)造方式。圖2.4 所示的節(jié)點W對輸入的信息 b1 和 b2 進(jìn)行的模二加操作，就是一種最簡單的線性網(wǎng)絡(luò)編碼操作方式。2.6 網(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）

30、和無線網(wǎng)絡(luò)（Wireless Network）等相結(jié)合的研究取得了重要的進(jìn)展，被認(rèn)為是網(wǎng)絡(luò)編碼最有可能被首先應(yīng)用的領(lǐng)域。1、 數(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ò)編碼付諸實施，構(gòu)建了一個可實用化的網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)系統(tǒng)，并在 Washington 大學(xué)的Rocketfuel 項目所獲得的幾個 ISP 骨干網(wǎng)絡(luò)拓?fù)渖线M(jìn)行了仿真，取得了較好的傳輸性能。CodedStream 也是在網(wǎng)絡(luò)中較早進(jìn)行了基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)的嘗試71，CodedStream 是一個基于P2P模式的，面向高帶

31、寬流媒體的數(shù)據(jù)分發(fā)系統(tǒng)。它按照編碼網(wǎng)絡(luò)分發(fā)數(shù)據(jù)的特性，在覆蓋網(wǎng)絡(luò)上構(gòu)建一個 K-redundant 路徑圖作為網(wǎng)絡(luò)拓?fù)?，網(wǎng)絡(luò)編碼被用于圖中“瓶頸”處的數(shù)據(jù)分發(fā)。最初的 CodedStream 在自己的仿真平臺上進(jìn)行了測試，其后續(xù)研究將整個思想進(jìn)一步擴(kuò)展，并利用 PlanetLab 平臺進(jìn)行了更廣泛的測試。網(wǎng)絡(luò)編碼與應(yīng)用層組播（Application Layer Multicast，ALM）相結(jié)合也取得一定進(jìn)展。應(yīng)用層組播中的數(shù)據(jù)分發(fā)由客戶端主機(jī)實現(xiàn)的，端主機(jī)具有一定的計算能力，這為網(wǎng)絡(luò)編碼提供了良好的應(yīng)用環(huán)境。而且，應(yīng)用層組播利用的覆蓋網(wǎng)絡(luò)拓?fù)淇梢园葱枳兓?，這也恰好可以利用網(wǎng)絡(luò)編碼對動態(tài)網(wǎng)絡(luò)適

32、應(yīng)性強(qiáng)的優(yōu)勢。Y. Zhu 給出了一個基于網(wǎng)絡(luò)編碼的應(yīng)用層組播的完整實現(xiàn)。通過對比測試，證明了基于網(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)一步的實驗證實，由于在執(zhí)行編碼和譯碼操作時需要一定的I/O和CPU消耗，基于網(wǎng)絡(luò)編碼的應(yīng)用層組播的傳輸容量往往無法達(dá)到預(yù)期。2、 無線網(wǎng)絡(luò)由于無線鏈路的不可靠性和物理層廣播特性，應(yīng)用網(wǎng)絡(luò)編碼，可以解決傳統(tǒng)路由、跨層設(shè)計等技術(shù)無法解決的問題。具體來說，網(wǎng)絡(luò)編碼除了提升無線網(wǎng)絡(luò)的網(wǎng)絡(luò)

33、吞吐量，還可以減少數(shù)據(jù)包的傳播次數(shù)，降低無線發(fā)送能耗。采用隨機(jī)網(wǎng)絡(luò)編碼，即使部分網(wǎng)絡(luò)節(jié)點或鏈路失效，最終在目的節(jié)點仍然能恢復(fù)原始數(shù)據(jù)，從而增強(qiáng)網(wǎng)絡(luò)的容錯性和魯棒性。此外，無需復(fù)雜的加密算法，采用網(wǎng)絡(luò)編碼就可以提高無線網(wǎng)絡(luò)的安全性等。文獻(xiàn)20對網(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ò)層和物理

34、層平衡鏈路帶寬供需的跨層優(yōu)化策略。Y.Wu等在Ad Hoc組播方面提出了應(yīng)用網(wǎng)絡(luò)編碼的最小化能量解決方法22，使得傳輸每比特信息消耗的能量最小，以此來節(jié)省Ad Hoc網(wǎng)絡(luò)中數(shù)據(jù)分發(fā)的能耗。此外，還有一些學(xué)者對如何利用網(wǎng)絡(luò)編碼增加Ad Hoc傳輸?shù)聂敯粜詥栴}進(jìn)行了研究，如Chen等研究在分布式天線系統(tǒng)和多入多出系統(tǒng)（DAS-MIMO）中，引入網(wǎng)絡(luò)編碼的概念，經(jīng)過理論推導(dǎo)和實驗仿真，證明了無論有無輔助天線，網(wǎng)絡(luò)編碼都能提高網(wǎng)絡(luò)的性能，尤其是減小系統(tǒng)丟包損耗。相對于Ad Hoc網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)密度較大，移動性不強(qiáng)，通常運行在無人值守的惡劣甚至危險的遠(yuǎn)程環(huán)境中，能源無法替代，設(shè)計有效的策略延長網(wǎng)絡(luò)

35、的生命周期成為無線傳感器網(wǎng)絡(luò)的核心問題。麻省理工學(xué)院的Petrovic等人提出了一種結(jié)合網(wǎng)絡(luò)編碼的對無線信號不進(jìn)行調(diào)制的策略23，并證明：運用分布式隨機(jī)網(wǎng)絡(luò)編碼，未經(jīng)調(diào)制的無線信號能夠達(dá)到與經(jīng)過調(diào)制的無線信號一樣的吞吐量，這樣就能節(jié)省大量因為模擬器件進(jìn)行調(diào)制而消耗的能量和降低節(jié)點的成本。傳感器網(wǎng)絡(luò)需要把節(jié)點資源整合起來，實現(xiàn)一個可靠和健壯的網(wǎng)絡(luò)，基于這種想法，文獻(xiàn)35提出了一種結(jié)合分布式源編碼和網(wǎng)絡(luò)編碼的優(yōu)化算法，目的是用來提高傳感器網(wǎng)絡(luò)的容錯性和可靠性，同時對分布式源編碼的壓縮效率和魯棒性進(jìn)行了折中考慮。Katti等提出的基于機(jī)會的網(wǎng)絡(luò)編碼方法（COPE）首次研究了網(wǎng)絡(luò)編碼在無線環(huán)境協(xié)議層面

36、上的具體實現(xiàn)問題。在COPE協(xié)議中，每個節(jié)點對傳輸媒體進(jìn)行偵聽，獲得它的鄰居節(jié)點的狀態(tài)信息，決定進(jìn)行編碼的機(jī)會，并在本地的FIFO緩存結(jié)構(gòu)內(nèi)進(jìn)行編碼，然后進(jìn)行基于機(jī)會的路由。COPE協(xié)議要求每個節(jié)點利用本地信息各自決定哪些數(shù)據(jù)包需要進(jìn)行編碼以及如何進(jìn)行編碼。靈活的設(shè)計使得即使在網(wǎng)絡(luò)交通需求未知或者網(wǎng)絡(luò)流量劇增、或者發(fā)送/接收方動態(tài)變化的情況下，COPE協(xié)議仍能有效的支持多路單播流。然而該協(xié)議需要節(jié)點存儲數(shù)據(jù)包并進(jìn)行編碼，如果網(wǎng)絡(luò)出現(xiàn)擁塞，可能就會耗費較多的節(jié)點存儲空間。另外，文件共享是無線網(wǎng)狀網(wǎng)的一種典型應(yīng)用，為了評估網(wǎng)絡(luò)編碼對該應(yīng)用的影響，Hamra等64在理想化MAC協(xié)議基礎(chǔ)上開發(fā)了特定的

37、仿真平臺，分別比較了服務(wù)時間等性能在節(jié)點個數(shù)、盲轉(zhuǎn)發(fā)（Blind Forwarding）和選擇性轉(zhuǎn)發(fā)（Selective Forwarding）情況下的表現(xiàn)。實驗結(jié)果表明應(yīng)用網(wǎng)絡(luò)編碼得到的改進(jìn)雖然不如在有線網(wǎng)絡(luò)中顯著，但仍能在很大程度上提高吞吐量、縮短服務(wù)時間。2.7 隨機(jī)線性網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)隨機(jī)線性網(wǎng)絡(luò)編碼方法的核心思想是利用節(jié)點的運算能力，在發(fā)送節(jié)點線性編碼組合不同的信息包，在接收節(jié)點獲得足夠的線性編碼組合后，通過運算得到原始信息包，其可用性推廣了網(wǎng)絡(luò)編碼理論的應(yīng)用范圍。應(yīng)用網(wǎng)絡(luò)編碼的理論成果，Gkantsidis 等給出了基于隨機(jī)網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)系統(tǒng)的原理模型（或稱概念模型），如圖2

38、.5所示。假設(shè)Server節(jié)點（存放原始文件的服務(wù)器）需分發(fā)某文件給 Peer A，首先 Server將該文件分割成 n 個文件塊（Block），即B1，B2，B3.Bn，如果使用網(wǎng)絡(luò)編碼，則 Server節(jié)點從有限域中選擇n個系數(shù)C11,C12.C1n構(gòu)成編碼向量（Encoding Vector)c1 =C11,C12.C1n ，并利用該向量對分割后的文件塊進(jìn)行有限域中的線性運算。隨 后，Server節(jié)點將運算后的編碼信息E1 = B1 c 11+ B2 c12 + .+ Bn c1n，分發(fā)給 Peer A圖2.5 基于隨機(jī)線性網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)系統(tǒng)的原理模型假設(shè) Peer A 又下載了另外

39、一個編碼信息塊E2= B1 c 21+ B2 c22 + .+ Bn c2n，該信息來自Server節(jié)點或其它鄰居節(jié)點，當(dāng)Peer B對PeerA發(fā)出下載請求時，PeerA 按照上述同樣的方式在有限域中選擇系數(shù)c 1 , c 2，并對當(dāng)前緩存的編碼信息塊 E1和 E2進(jìn)行線性組合，將運算結(jié)果E = E 1c1 + E2 c2分發(fā)給Peer B。如果下游節(jié)點向 Peer B 請求數(shù)據(jù)包，則 Peer B按照同樣的規(guī)則將編碼后的數(shù)據(jù)信息分發(fā)給下游節(jié)點。對 Peer B收到的 E 而言，其對應(yīng)的編碼向量為c1 c1 + c2 c2?？梢姡捎镁W(wǎng)絡(luò)編碼，節(jié)點之間不再傳輸原始的文件塊，而是編碼信息（塊）

40、。當(dāng)某 Peer 接收到 n 個已編碼信息E1 ,E2. ,En后，則有： 公式(2.1)如果公式2.1的系統(tǒng)轉(zhuǎn)移矩陣 C 滿秩，即各編碼向量之間線性獨立，則能通過求解矩陣方程B1,B1.Bn =C-1E1,E2.En T譯出各原始文件塊B1,B1.Bn ，并恢復(fù)出原始文件。由于采用隨機(jī)網(wǎng)絡(luò)編碼總能保證矩陣C以接近1的概率滿秩，基于隨機(jī)網(wǎng)絡(luò)編碼和圖2.5所示的原理模型，文獻(xiàn)25構(gòu)建了一種網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)的原型系統(tǒng)：Avalanche。在 Avalanche 系統(tǒng)中，節(jié)點之間傳輸?shù)男畔⑹前凑丈鲜鲈韺υ嘉募K執(zhí)行隨機(jī)網(wǎng)絡(luò)編碼操作后的編碼信息。Avalanche 能克服基于存儲和轉(zhuǎn)發(fā)的數(shù)據(jù)分發(fā)系

41、統(tǒng)（如 BitTorrent 等）的缺陷和不足，可以顯著減少節(jié)點平均下載時間，進(jìn)一步提升數(shù)據(jù)分發(fā)系統(tǒng)的傳輸性能。3 NS2仿真平臺3.1 NS2簡介NS2，即Network Simulator Version 2，是面向?qū)ο蟮?、離散事件驅(qū)動的網(wǎng)絡(luò)環(huán)境模擬器，主要用于解決網(wǎng)絡(luò)研究方面的問題。NS2提供了在無線或有線網(wǎng)絡(luò)上的TCP、路由、多播等多種協(xié)議的模擬。NS2晝以來都在吸收全世界各地研究人員的成果，包括UCB、CMU笏大學(xué)和SUN等公司的無線網(wǎng)絡(luò)方面的代碼。NS2足一個面向?qū)ο蟮木W(wǎng)絡(luò)桟擬工具，對以完整地模擬整個網(wǎng)絡(luò)壞境。NS2使用一整套C+類庫實現(xiàn)了大多數(shù)常見的網(wǎng)絡(luò)協(xié)議以及鏈路層模型，利用這

42、些類的實例可以搭建起整個網(wǎng)絡(luò)的模型，而且包括具體的細(xì)節(jié)實現(xiàn)。NS2使用兩種編程語言，OTcl（具有面向?qū)ο筇匦缘腡cl腳本程序設(shè)計語言）和C+，它底層的模擬引擎主要由C+編寫，同時利用麻省理工學(xué)院的面向?qū)ο蟮墓ぞ呙钫Z言O(shè)Tcl作為模擬時的命令和配置接口語言。一方面，由于C+程序運行速度快，并且可以設(shè)計精確、復(fù)雜的算法，可以用于模擬各種網(wǎng)絡(luò)協(xié)議，適合于底層的實現(xiàn)。另一方面，具有面向?qū)ο筇匦缘腡cl腳本語言通過調(diào)用引擎中各類的屬性、方法定義網(wǎng)絡(luò)的拓?fù)?，配置?shù)據(jù)源，目的端，建立連接，產(chǎn)生所有事件的時刻表，運行并跟蹤模擬結(jié)果，還可以對結(jié)果進(jìn)行相應(yīng)的統(tǒng)計處理或制圖，方便網(wǎng)絡(luò)研究者在短時間內(nèi)快速地開發(fā)和

43、模擬出所需要的網(wǎng)絡(luò)壞境。C+和OTcl兩種語言的對象和變量是通過TclCL關(guān)聯(lián)起來的，C+的類和對象為編譯類和編譯對象，而OTcl的類和對象為解釋類和解釋對象，TclCL是在OTcl基礎(chǔ)上的封裝。圖3.1是NS2架構(gòu)圖，描述了Tcl、OTcl和TclCL之間的關(guān)系。圖3.1 NS2構(gòu)架圖3.2 NS2的特點1、抽象NS模擬器在設(shè)計上能夠滿足網(wǎng)絡(luò)研究界在模擬方面的多種需。抽象NS具備不同程度的抽象級別，不僅可以對細(xì)節(jié)進(jìn)行模擬，也對以對不同層次的總體框架進(jìn)行模擬。2、仿真NS提供了更加接近真實網(wǎng)絡(luò)的仿真環(huán)境，這是其他仿真軟件所不具備的。3、場景生成NS中自帶了流最場景生成文件和運動場景cbrgen

44、生成文件setdest，讓使用更加方便，當(dāng)然也支持用戶按照自己的實際需要編寫場景及運動文件腳本。4、可視化通過其中的網(wǎng)絡(luò)動畫工具Nam,以動畫的方式實現(xiàn)網(wǎng)絡(luò)仿真的全過程，讓整個 運動過程一目了然。5、可擴(kuò)充性可擴(kuò)充性表現(xiàn)在可以方便的添加新協(xié)議，讓使用范圍更加廣泛。3.3 NS2仿真一般流程進(jìn)行網(wǎng)絡(luò)仿真前，首先分析仿真涉及哪個層次，NS仿真分兩個層次：一個是基于 OTcl編程的層次。利用NS已有的網(wǎng)絡(luò)元素實現(xiàn)仿真，無需修改NS本身, 只需編寫OTcl腳本。另一個是基于C+和OTcl編程的層次。如果NS中沒有所需的網(wǎng)絡(luò)元素，則需要對NS進(jìn)行擴(kuò)展，添加所需網(wǎng)絡(luò)元素，即添加新的C+和 OTcl類，編寫

45、新的OTcl腳木。假設(shè)用戶已經(jīng)完成了對NS的擴(kuò)展，或者NS所包含的構(gòu)件已經(jīng)滿足了要求， 那么進(jìn)打一次仿真的步驟大致如下：1、開始編寫OTcl腳本。首先配置模擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，此時可以確定鏈路的基本特性，如延遲、帶寬和丟失策略等。2、建立協(xié)議代理，包栝端設(shè)備的協(xié)議綁定和通信業(yè)務(wù)量模型的建立。3、配置業(yè)務(wù)量模型的參數(shù)，從而確定網(wǎng)絡(luò)上的業(yè)務(wù)量分布。4、設(shè)置Trace對象。NS通過Trace文件來保存整個模擬過程。仿真完后, 用戶可以對Trace文件進(jìn)行分析研究。5、編寫其他的輔助過程，設(shè)定模擬結(jié)束時間，至此OTcl腳本編寫完成。6、用NS解釋執(zhí)行剛才編寫的OTcl腳本。7、對Trace文件進(jìn)行分析，得

46、出有用的數(shù)據(jù)。8、調(diào)整配置拓?fù)浣Y(jié)構(gòu)和業(yè)務(wù)量模型，重新進(jìn)行上述模擬過程。下面是仿真的流程圖：圖3.2 NS2進(jìn)行仿真的基本流程圖3.4 NS2仿真的基本組件和使用3.4.1 節(jié)點的結(jié)構(gòu)和配置無線網(wǎng)絡(luò)中的節(jié)點是可移動的節(jié)點，擁有很多屬性，如果使用NS研究無線網(wǎng)絡(luò)需要在無線節(jié)點創(chuàng)建之前對節(jié)點的各項屬性進(jìn)行配置。節(jié)點的屬性配置使用Simulator 類的noed-config 方法，該方法采用可變的模塊化結(jié)構(gòu)，以實現(xiàn)不同類型的節(jié)點在相同的節(jié)點基類下定義。配置好屬性以后再創(chuàng)建節(jié)點，這是創(chuàng)建節(jié)點的基本方式，如需創(chuàng)建不同的節(jié)點則重新配置屬性以后再創(chuàng)建。下面是使用node-config 配置一個節(jié)點屬性的例子

47、。set ns new Simulator#建立一個模擬實例set topo new Topography #建立一個拓?fù)鋱D對象#配置無線節(jié)點$ns node-config -adhocRouting AODV #無線路由協(xié)議是AODV協(xié)議-llType LL #邏輯鏈路層類型是LL層-macType Mac/802.11 #MAC層協(xié)議采用802.11協(xié)議-ifqType Queue/DropTail/PriQueue #接口隊列類型是IFQ隊列-ifqLen 50 #網(wǎng)絡(luò)接口隊列的大小是50-antType Antenna/QmniAntenna #天線模型是全向天線-propType P

48、ropagation/TwoRayGround #無線傳輸模型是TwoRayGround-phyType Phy/WirelessPhy #網(wǎng)絡(luò)接口類型是無線物理層-channel Channel/WirelessChannel #物理信道類型無線信道-topoInstance $topo #設(shè)置拓?fù)鋵嵗?agentTrace ON #開啟代理層trace-routerTrace ON #開啟路由層trace-macTrace OFF #關(guān)閉mac層的trace-movementTrace OFF#關(guān)閉移動節(jié)點的移動記錄設(shè)置完節(jié)點的屬性之后，使用node-congfig 方法的 -reset

49、選項可以將節(jié)點的所有屬性的參數(shù)值設(shè)置為默認(rèn)值：$ns node-config -reset3.4.2 數(shù)據(jù)流生成工具cbrgenNS2自帶有交通場景生成器，名稱為cbrgen.tcl。數(shù)據(jù)流生成工具cbrgen 用來生成傳輸負(fù)載，可以產(chǎn)生移動節(jié)點之間的TCP 流和CBR 流。該工具所在的目錄為ns/indep-utils/cmu-scen-gen/，使用方法如下：ns cbrgen.tcl -type cbr/tcp -nn nodes -seed seed -mc connections -rate rate其中各種參數(shù)的含義如下：-type：選擇tcp表示生成tcp流，選擇cbr表示生成c

50、br流；-nn：nodes表示節(jié)點數(shù)目；-seed：seed表示指定隨機(jī)種子；-mc：connections表示節(jié)點間的最大連接數(shù)；-rate：rate表示每個連接間的數(shù)據(jù)流的速率；在使用cbrgen設(shè)置節(jié)點數(shù)n時，節(jié)點的編號是從node_(1)到node_(n)。3.4.3 拓?fù)溥\動場景生成工具setdest拓?fù)溥\動場景生成工具setdest是用來隨機(jī)生成無線網(wǎng)所需的節(jié)點運動場景，也即一定數(shù)量的節(jié)點在某一固定大小的矩形區(qū)域中隨機(jī)移動。生成setdest的命令的源代碼文件在ns/indep-utils/cmu-scen-gen/setdest文件夾下，使用前需執(zhí)行make命令以生成可執(zhí)行文件。

51、setdest的使用方法如下：setdest -v -n -p -M -t -x -y 或setdest -v -n -s -m -M -t -P -p -x -y 其中使用到的參數(shù)定義如下：-v：version_of_setdest 指定setdest的版本；-n：nodes指定場景中總節(jié)點數(shù)目；-p：pause_time指定了節(jié)點在運動到一個目的點后停留的時間，如果設(shè)置為0表示節(jié)點不做停留；-s：speed_type為uniform/normal；-m：min_speed指定節(jié)點移動的最小速率；-M: max_speed指定節(jié)點移動的最大速率；-P：pause_type為constant/

52、uniform；-t：simulation_time指定了模擬場景的持續(xù)時間，單位為s；-x：max_x指定了節(jié)點運動區(qū)域的長度，單位為m；-y：max_y指定了節(jié)點運動區(qū)域的寬度，單位為m；版本不用使用的參數(shù)也有區(qū)別，需按要求使用。執(zhí)行make命令生成可執(zhí)行文件以后，若沒有將setdest命令添加到linux系統(tǒng)環(huán)境變量中，則應(yīng)在使用setdest時需要指定路徑全稱或在ns/indep-utils/cmu-scen-gen/setdest目錄下使用，而且要在setdest前面加“./”。cbrgen和setdest產(chǎn)生的文件均可以采用source命令加入另一個Otcl腳本中，注意產(chǎn)生的文件用

53、到了諸如node_數(shù)組變量和god_變量，需要在Otcl腳本中預(yù)先建立。3.4.4 簡單動畫顯示工具NAMNAM（Network Animater）的功能是根據(jù)網(wǎng)絡(luò)模擬軟件或真實環(huán)境的特定格式的Trace輸出文件來運行動畫，以觀測網(wǎng)絡(luò)模擬中的Trace和數(shù)據(jù)分組流向。NAM使用方法如下：nam -g -t -i -j -k -N -c -f -r -a -p -S NAM命令中的參數(shù)意義如下：-g：指明NAM窗口的幾何位置；-t：指定nam使用tkgraph，并為tkgraph確定輸入文件；-i: 指定屏幕刷新率，單位為毫秒（ms），默認(rèn)為50ms；-j：指定nam演示時的仿真時間；-k：初始

54、化socket端口號；-N：為nam實例命名，它可能在此后用于對等的同步；-g：指明NAM窗口的幾何位置；-c：進(jìn)行反向演示（模擬的逆過程）時，緩沖區(qū)所能存儲的活動對象的最大值（size）；-f: 演示啟動時所載入的文件；-r：演示速度，默認(rèn)是2ms（0.002）；-a：創(chuàng)建一個獨立的nam實例；-p：打印Trace的文件格式；-S：開啟X同步以便于圖形的調(diào)試，僅限于有X環(huán)境的UNIX系統(tǒng)。OTcl腳本中可以對節(jié)點、鏈路、隊列、和Agent等對象進(jìn)行動畫顯示方面的屬性控制，nam動畫顯示的命令如下：1、 節(jié)點$node color color#設(shè)定節(jié)點的顏色$node shape shape#

55、設(shè)定節(jié)點的形狀$node label label#設(shè)定節(jié)點的名稱$node label-color color#設(shè)定節(jié)點顯示名稱的顏色$node label-at ldirection#設(shè)定節(jié)點名稱的顯示位置2、鏈路和隊列$ns duplex-link-op 其中attribute的值可以是orient、color、queuePos和label。Orient指定了鏈路的方向，可以是：right、left、down、right-up、right-down、left-up以及l(fā)eft-down。Color指定鏈路的顏色，label定義鏈路顯示的名稱，queuePos定義隊列顯示的方向。3、 Age

56、nt$ns attach-agent $node $Agent$ns add-agent-trace $Agent AgentName使用上面的命令就可以使想要顯示的Agent以Agentname出現(xiàn)在節(jié)點的附近的方框內(nèi)，這樣可以再nam顯示中看出摸個節(jié)點上綁定了哪些Agent。3.4.5 Trace文件格式Trace文件是在模擬過程中生成的記錄模擬每一個分組調(diào)度事件的文件，一次模擬生成的信息基本上全體現(xiàn)在Trace文件中。Trace文件包含了很多有用的可供分析的數(shù)據(jù)，我們需要從中篩選出我們關(guān)注的數(shù)據(jù)進(jìn)行分析。1、 有線網(wǎng)絡(luò)的Trace格式有線網(wǎng)絡(luò)的Trace格式中每條記錄包含了如下截圖顯示1

57、2項內(nèi)容：圖3.3 有線網(wǎng)絡(luò)的Trace部分截圖內(nèi)容現(xiàn)在來分析有線網(wǎng)絡(luò)的Trace格式的一條記錄中每一項的信息：（1） Event：發(fā)生事件的類型有+、-、r和d等4種，分別表示分組進(jìn)入鏈路隊列、分組離開鏈路隊列、目的節(jié)點接收分組以及隊列丟棄分組等含義。（2） Time：事件發(fā)生的時間。（3） From node：發(fā)送分組的源節(jié)點id。（4） To node：接收分組的目的節(jié)點id。（5） Pkt type：分組的類型。（6） Pkt size：分組的大小。（7） Flags：標(biāo)志項。（8） Fid：IPv6定義的流標(biāo)示符。（9） Src addr：表示分組的來源端，例如2.0表示節(jié)點2的0號

58、端口。（10） Dst addr：表示分組的目的端，例如3.0表示節(jié)點3的0號端口。（11） Seq num: 分組的序列號。（12） Pkt id：分組的唯一標(biāo)示符。2、 無線網(wǎng)絡(luò)的Trace格式圖3.4 無線網(wǎng)絡(luò)的Trace部分截圖內(nèi)容無線網(wǎng)絡(luò)的Trace格式的記錄的每一項信息:(1) Event：事件的類型有是s、r、f和d 4種，分別表示分組的發(fā)送、接收、轉(zhuǎn)發(fā)、丟棄事件。(2) Time：事件發(fā)生的時間。(3) Node：事件發(fā)生的節(jié)點id。(4) Layer：發(fā)生事件所在的層。(5) Flags：標(biāo)志項。(6) Pkt id：分組的id。(7) Pkt type：分組的類型。(8)

59、Pkt size：分組的大小。(9) MAC Layer Info: MAC層的信息。(10) -:分隔符。(11) IP Info: IP層的信息。3.5 性能參數(shù)分析模型1、 傳輸時延網(wǎng)絡(luò)的傳輸時延D（End-to-End Delay）定義為源節(jié)點發(fā)送出一個分組到目的節(jié)點接收到該分組之間的時間差，它包括電（或光）信號在物理介質(zhì)中的傳播延時和數(shù)據(jù)在網(wǎng)絡(luò)中的處理延時，也即指網(wǎng)絡(luò)中數(shù)據(jù)傳輸所用的時間。在很多網(wǎng)絡(luò)應(yīng)用中，比較關(guān)注分組的時延大小，要求分組的時延不能太大，例如實時的視頻會議、網(wǎng)絡(luò)電話等。結(jié)合NS的Trace文件，以分組發(fā)送和到達(dá)接收之間的時間間隔來計算傳輸延時，計算方式如下： D（i）

60、=RT（i）-S（i）T公式（3.1）式中，D（i)表示第i個分組的傳輸時延，RT（i）表示第i個分組的接收時間，ST（i）表示第i個分組的發(fā)送時間。在分析網(wǎng)絡(luò)的傳輸時延時，一般都統(tǒng)計平均傳輸時延 公式（3.2）即統(tǒng)計Trace腳本中N個分組的平均傳輸時延。2、 網(wǎng)絡(luò)吞吐量網(wǎng)絡(luò)的吞吐量（Throughput）TH是網(wǎng)絡(luò)性能的一個重要參數(shù)，是指在不丟包的情況下單位時間內(nèi)節(jié)點可以接收的數(shù)據(jù)量，單位是字節(jié)每秒或比特每秒。端到端的吞吐量與網(wǎng)絡(luò)狀況有很大關(guān)系，為了測試端到端的最大吞吐量，應(yīng)該逐漸增大發(fā)送端的數(shù)據(jù)發(fā)送速率，然后計算接收端的吞吐量，直至吞吐量達(dá)到最大。在分析Trace文件時，使用以下的計算方

61、式計算吞吐量： 公式（3.3）上式中：TB（i）是指到底i個分組被目的節(jié)點接收時已經(jīng)傳輸?shù)臄?shù)據(jù)總量，RT（i）是第i個包的接收時間。im，表示計算從第m個分組到底i個分組的吞吐量，特別的，若取m=1 則是計算平均吞吐量。3.6 Trace文件分析處理3.6.1 gawk處理文檔的過程gawk是一種對文檔資料具有很強(qiáng)處理能力的程序語言，簡短的幾句代碼就可以完成對文檔的修改、對比、抽取，相對其他的語言來說，其對文檔資料的處理方面具有很大的優(yōu)勢。gawk語言將說要處理的文檔分解為一條條的記錄（一般一條記錄是數(shù)據(jù)文件的一行數(shù)據(jù)），每條記錄默認(rèn)以空格TAB鍵分隔為一個個字段。例如，Trace文件的每一行作為一個記錄，取實際Ttrace文件的記錄如下：圖3.5 仿真實驗Trace文件部分截圖內(nèi)容在對記錄的處理過程中，一般都要對記錄的字段進(jìn)行操作。對記錄中字段的提取可以采用字段變量“$1，$2，$3.”等，gawk讀入記錄后已自動把字段值存入字段變量。需要注意的是“$0”表示所讀取的整條記錄。表3.1是對圖3.5 Trace文件的記錄進(jìn)行分解和提取的例子。表3.1 對Trace文件記錄的分解和提取一二三四 五六七八九十十一r47.355426347_2_AGT-251cbr532