基于網絡編碼的機會網絡數據分發(fā)研究與仿真

中北大學20**屆畢業(yè)設計說明書第72頁共72頁1引言1.1研究問題現狀近年來，無線通信技術得到了飛速的發(fā)展，新技術不斷出現，其中移動通信系統(tǒng)的3G技術已經進入應用普及階段，并朝第四代通信系統(tǒng)方向演進?！秶抑虚L期科學和技術發(fā)展規(guī)劃綱要》(2006一2020)中已經明確提出了未來通信領域的競爭將集中反映在特殊環(huán)境和新興應用領域中的通信網絡能力及通信技術的競爭上[1]。其中新興應用領域涉及到的移動網絡技術更是被作為前沿技術中的重點。目前,移動通信的快速發(fā)展使得移動網絡帶寬逐漸增大，移動應用不斷豐富，移動終端的處理能力越來越強。為了適應不同的應用需求,各具特色的網絡結構和無線網絡技術不斷涌現,包括無線個域網(如IEEE802.15)、無線局域網(如IEEE802.lla/b/g/i/n)、無線城域網(如802.16、802.20)、無線移動廣域網(如2G、3G)、衛(wèi)星網絡，以及無線自組織(AdHoc)網絡、無線傳感器網絡(WirelessSensorNetwork,WSN)等等。而WIFi、WIMax、UWB等無線接入網絡和GPRS、B3G、UMTS等蜂窩移動網絡等基礎設施與技術的完善為移動應用提供了在任何時間、任何地點訪問所有網絡服務的可能性。在上述的各種網絡發(fā)展后，一種節(jié)點移動范圍更大，網絡大多數都是不連通的新型網絡出現了，這種類型的網絡被稱為機會網絡，機會網絡是一種不需要源節(jié)點和目的節(jié)點之間存在完整路徑，利用節(jié)點移動帶來的相遇機會實現網絡通信的自組織網絡。經過近幾年的發(fā)展，機會網絡技術研究與應用已經取得了一定的進展，但是，總體而言目前相關研究還處于一個剛起步的初級階段。隨著移動應用業(yè)務的增加以及機會網絡商業(yè)化，機會網絡技術的全面應用與深入仍然要解決很多極具挑戰(zhàn)性的問題，如復雜環(huán)境下的路由、數據時延與網絡開銷均衡問題、移動狀態(tài)下網絡可靠性以及安全問題等等。同時在一些領域，機會網絡的相關技術標準尚未形成，尤其在國內對于這類高延遲的特殊通信網絡的研究才剛剛起步。規(guī)劃信息化發(fā)展戰(zhàn)略中不僅強調了信息產業(yè)以及信息技術的發(fā)展，同時也提出了將寬帶無線移動通信、新興及特殊應用領域的網絡通信等核心關鍵技術研究作為我國信息技術的主要發(fā)展方向之一。因此，對機會網絡數據分發(fā)展開研究將為正確理解機會網絡拓撲與數據傳輸特點提供可行性依據，有助于推進現有關鍵技術的可擴展性，并對提高機會網絡數據傳輸可靠性，探索節(jié)點移動模型對機會網絡服務性能保障的影響，推動相關技術的深入研究有重要現實的意義。2000年,R.Ahlswede等人基于網絡信息流的概念提出了網絡編碼的思想，通過允許中間節(jié)點既實現路由功能又實現編碼功能，達到組播的最大流量[2]。為使得網絡編碼具有實際可用性，Li等人提出了線性網絡編碼的概念，證實節(jié)點進行線性網絡編碼運算，具有可行性，能夠達到最大流傳輸理論極限[3]。Ho等人推廣了這一概念，提出了有限域下隨機線性網絡編碼的思想，并證實其有效性[4]。之后，隨機線性網絡編碼被應用于各個方面的研究，用于提高網絡吞吐量、能量利用效率。網絡編碼徹底改變了通信網絡中信息處理和信息傳輸的方式，被認為是進入21世紀后信息處理和信息傳輸研究領域上最重要的理論成果之一。網絡編碼的核心思想是允許通信網絡中的節(jié)點對傳輸的信息進行操作和處理（如有限域中的運算等），而不再局限于存儲與轉發(fā)。與傳統(tǒng)的基于存儲和轉發(fā)的路由傳輸機制相比，網絡編碼能顯著改善數據分發(fā)系統(tǒng)性能，如提升網絡吞吐量，節(jié)約傳輸帶寬和均衡網絡負載等。網絡編碼具有重要的理論價值和廣泛的應用前景，其研究已經引起了學術界和產業(yè)界的廣泛關注和高度重視。國際知名大學、科研機構和公司，如普林斯頓大學、麻省理工學院（MIT）、貝爾實驗室（BellLab）、AT&T的香農信息實驗室和微軟公司（Microsoft）等都積極投入對網絡編碼的研究，并取得了一些重要的研究成果。我國的香港中文大學（CUHK）、清華大學、中國科學技術大學、西安電子科技大學和南京大學等也對網絡編碼展開了研究，并取得一定的進展。機會網絡經常出現鏈路斷裂，網絡不連通的狀況，在這種情況下，節(jié)點一般并不丟棄數據包，相反節(jié)點傳輸數據一般采用“存儲一攜帶一轉發(fā)”的模式，傳統(tǒng)的機會網絡中，中間節(jié)點只進行數據的存儲與轉發(fā)操作，但是運用網絡編碼的機會網絡中，中間節(jié)點可以對接收到的數據塊進行隨機線性組合編碼，可以增大單次傳輸的數據量。隨著網絡規(guī)模的日趨龐大、各種網絡方案和協議日趨復雜，分析、實驗和仿真等方法成為了當前進行網絡技術研究的有效手段。研究網絡仿真技術成為了現代通信網絡設計的重要環(huán)節(jié)，在通信網絡性能研究中起關鍵性作用。在眾多網絡仿真軟件中NS2具有免費、源代碼開放、易擴展等等優(yōu)點而備受研究人員的青睞。NS2是一個開源的網絡仿真軟件，可以再windows/unix上運行，且所有源代碼公開，對于進行網絡的研究和擴展非常方便。本課題研究的內容就是在仿真平臺NS2下設計并建立機會網絡模型，理解網絡編碼的原理，在NS2中編程實現基于分簇的隨機線性網絡編碼數據分發(fā)的仿真并與一般的網絡編碼比較其網絡吞吐量和時延性能。1.2本文的內容組織本文內容組織如下：先分別介紹了機會網絡、網絡編碼原理及仿真平臺NS2的各種知識，然后使用NS2構建機會網絡拓撲，編出各個代碼腳本，在NS2上仿真實驗，得出數據并畫圖進行說明驗證。2機會網絡及網絡編碼相關知識2.1機會網絡的概念機會網絡是一種特殊的自組織網絡，它不需要存在端到端的完整路徑，充分利用了節(jié)點移動帶來的相遇機會（contact），實現數據逐跳轉發(fā)，并最終傳送到目的節(jié)點[5]。從本質上來看，機會網絡否定了傳統(tǒng)網絡中數據傳輸的一個根本前提——在路由期間或者數據傳遞期間，存在一條或者多條源端到目的端的路徑。機會網絡中的相遇（contact）概念是指節(jié)點之間發(fā)生的一次聯系。當節(jié)點（如：車輛、移動用戶）進入彼此的通信范圍之內時，則發(fā)生通信，當兩者離開彼此通信范圍時，則鏈路斷開，停止通信。在機會網絡中，contact是機會性的，而非確定性的。圖2.1是一個機會網絡示意圖，t1時刻源節(jié)點S希望將數據傳輸給目標節(jié)點D，但S和D位于不同的連通域而沒有通信路徑，因此，S首先將數據打包成消息發(fā)送給鄰居節(jié)點3，由于3并沒有合適的機會轉發(fā)下一跳節(jié)點，它將消息在本地存儲并等待傳輸機會，經過一段時間到達t2時刻，節(jié)點3運動到節(jié)點4的通信范圍并轉發(fā)給節(jié)點4，在t3時刻，節(jié)點4將消息傳輸給目標節(jié)點D，完成數據傳輸。圖2.1機會網絡示意圖機會網絡的部分概念來源于早期的延遲容忍網絡DTN(delaytolerantnetwork)[6]研究。DTN最初是容遲網絡研究組(DTNRG)為星際網絡IPN(interplanetarynetwork)[7]通信而提出來的，其主要目標是支持具有間歇性連通、延遲大、錯誤率高等通信特征的不同網絡的互聯和互操作，如互聯Internet和傳感器網絡、移動自組織網絡等。DTN網絡體系由多個底層運行獨立通信協議的DTN域組成。域間網關利用“存儲-轉發(fā)”的模式工作，當去往目標DTN域的鏈路存在時轉發(fā)消息，否則，將消息存儲在本地持久存儲器中等待可用鏈路。機會網絡可以看成是具有一般DTN網絡特征的無線自組網。2.2機會網絡的構架機會網絡的體系結構與傳統(tǒng)Internet傳輸結構的最大區(qū)別在于束層（BundleLayer），它位于傳輸層和應用層之間，它跟底層協議相互配合，使得應用程序可以跨過多個區(qū)域實現通信。機會網絡節(jié)點使用束層來發(fā)送和接受數據，并保證逐跳轉發(fā)的可靠性以及端到端的確認。該架構非常靈活，既保證了各層的共性，又避免非法使用其他層。1、束層為了實現“存儲-攜帶-轉發(fā)”的消息交換機制，機會網絡在節(jié)點的應用層和傳輸層之間插入了一個新的協議層——束層。使用束層的一個主要原因是在機會網絡中，傳輸延時差異很大，當一個數據包丟失時，整個傳輸的數據成為無用數據。因此為了避免這樣的事情發(fā)生，將數據打包成一個較大的消息，稱之為束，并使之不能輕易分割成更小的片段。機會網絡中一般不存在從源節(jié)點到目的節(jié)點的端到端的連接，因此束會存儲在中繼節(jié)點上并等待合適機會進行傳輸。一個束必須包含的信息有：源端地址、目的端地址、起始時間、束的生存時間、數據長度及服務類型等。此外，對于具體的應用，可能還需要一些狀態(tài)域和認證消息，例如，監(jiān)管傳送請求等。2、監(jiān)管傳送束層提供了一種簡單的并且不需要應答的投遞機制，但框架本身提供了兩種可能的方法來提高可靠性：端到端的應答和監(jiān)管傳送。通過監(jiān)管傳送，可以保證端到端的可靠性。在特定的環(huán)境下，這種機制可以更好地利用資源，例如源節(jié)點可以將已經投遞成功的束在緩存中釋放掉。3、機會網絡中的節(jié)點一個束的源端和目的端是由端點號EID（Endpoint-Identifier）來標識的。EID中包含一個或多個機會網絡節(jié)點。當目的地收到該束時，認為該束傳遞成功。EID可以類比于DNS（DomainNameSystem）中的統(tǒng)一資源標識（URI，UniformResourceIdentifier），并且與路由或拓撲組織結構沒有必然聯系。區(qū)域名是早先提出的一個概念，一個完整的地址由區(qū)域號和節(jié)點號組成?；谶@種區(qū)域的概念，束首先投遞到目的節(jié)點所在的區(qū)域，然后再投遞到目的節(jié)點。4、服務分類按重要性不同，束層引入了三類服務：1、大塊束（bulkbundles），只需要較小的投入，當有資源可用時就可以提供這種服務；2、正常束（normalclassbundles），比大塊束優(yōu)先級要高，但比“加快束”（expeditedbundles）優(yōu)先級要低；3、加快束，這類服務只是針對來自同一個端點的束而言，例如：當大塊束與加快束來自不同的端點時，即使加快束比大塊束優(yōu)先級高，但大塊束仍有可能比加快束先傳遞。5、安全機會網絡框架提供了一個可選的安全構架，使用逐跳、端到端的授權和誠信機制，主要的困難是如何對網絡進行控制和如何轉發(fā)控制消息。沒有進行認證的節(jié)點不能夠通過機會網絡發(fā)送數據，并且不能利用該網絡以外的節(jié)點進行數據轉發(fā)。2.3機會網絡拓撲特點1、多跳網由于無線通信的距離受限制，機會網絡中節(jié)點之間的通信通常需要借助其他節(jié)點的中繼轉發(fā)才能實現，便形成了多跳通信路徑。2、動態(tài)的網絡拓撲機會網絡中節(jié)點間的相互連通性構成了網絡的拓撲結構。由于機會網絡中的節(jié)點可以以隨機的速度和方式移動，加上發(fā)射功率的變化，以及無線信道的干擾大小不斷變化等因素，節(jié)點間通過無線通信形成的網絡拓撲結構可能隨時發(fā)生變化，而且變化的方式和速度都是難以預料的。3、分布式控制在機會網絡中，為了實現網內節(jié)點之間的通信，需要解決無線資源使用、路由發(fā)現等控制問題。由于機會網絡沒有預設的基礎設施，也就沒有預設的中心控制節(jié)點，所以只能采用分布式控制的方式來完成。4、對等性機會網絡中節(jié)點與節(jié)點可以直接互通，每個節(jié)點都相同，無主從之分，每個節(jié)點都能夠支持邏輯上的自發(fā)自收，即節(jié)點直接的來去雙向鏈路都相同。因此，無機會網絡節(jié)點的無線通信裝置一般采用時分雙工方式（TDD）。 5、臨時自組織性若干個無線節(jié)點聚集到一起時，他們便臨時自組織性地形成了一個無線通信網絡，該臨時性包括：網絡成員的臨時性，網絡組織的臨時性，網絡拓撲的臨時性，網絡路由的臨時性，網絡無線資源分配采用按需臨時分配等。6、鏈路帶寬受限機會網絡采用無線傳輸技術作為其基本通信手段，與有線傳輸技術相比，它具有較低的傳輸帶寬。并且由于各個節(jié)點分布式競爭使用信道，使得每個移動節(jié)點實際使用的帶寬遠小于物理層所提供的最大傳輸速率。7、能量受限機會網絡內的移動節(jié)點一般需要依靠電池來提供能量，因此，節(jié)省功率將使自組網技術中一個需要高度重視的問題。8、有限的安全性機會網絡由于采用分布式控制、無中心、臨時組織等原因，它比一般的無線網絡更易受到安全方面的威脅。2.4機會網絡節(jié)點移動模型節(jié)點移動模型描述了節(jié)點的移動模式，包括位置、速度等特征的變化，廣泛應用于自組網協議性能的分析和評價，是自組織網絡的基礎研究之一。傳統(tǒng)的MANET假設網絡是全連通的，節(jié)點的移動對路由層以上的協議是“屏蔽”的。因此一般從網絡拓撲角度去分析移動模型對協議性能的影響，如拓撲連通率、節(jié)點連通度等，而機會網絡中的移動模型研究是以刻畫節(jié)點相遇特征為核心的。這是因為在機會網絡中的數據傳輸依賴于節(jié)點移動帶來的相遇機會，而節(jié)點的相遇概率和相遇時間分布是由節(jié)點的移動模型決定的。因此，相比于傳統(tǒng)的MANET，移動模型對機會網絡研究更加重要。2.4.1獨立同分布的理論移動模型許多學者研究了3個經典的獨立同分布移動模：RandomWayPoint[8](RWP)RandomWalk(RW)和RandomDirection[9](RD)。這些模型下的節(jié)點相遇特征可用兩個參數來刻畫：相遇時間(meetingtime，簡稱MT)和相遇間隔時間(intermeetingtime，簡稱IMT)。MT是指兩個節(jié)點從靜止開始到第一次相遇(進入通信范圍)經過的時間間隔，而IMT是指兩個節(jié)點前后兩次相遇的時間間隔。文獻[9]都分別從不同的角度證明了上述3個移動模型的節(jié)點期望相遇時間(expectedmeetingtime)服從指數分布或其尾部服從指數分布，并基于此分析了多種路由協議的延時性能。文獻[10]推導出RW模型下期望相遇間隔時間的分布也服從指數分布，而文獻[11]推導了RD模型和RWP模型下的期望相遇間隔時間分布，并證明了RWP和RD模型下相遇時間和相遇間隔時間的尾部分布是無記憶的。2.4.2基于統(tǒng)計的實際移動模型除了從理論來推導以外，一些研究人員還利用統(tǒng)計方法，通過收集實際環(huán)境中節(jié)點的運動軌跡來研究節(jié)點的移動特征。MIT的RealityMining項目[12]記錄了MIT校園中100個攜帶藍牙智能手機的學生和職工為期9個月的移動軌跡和相遇數據；UCSD的WirelessTopologyDiscovery[13]收集了11周內300個無線PDA與Wi-Fi接入點的相遇數據；劍橋大學的Haggle項目[14]則記錄了若干個帶有藍牙接口的iMote設備在校園的相遇情況。此外，他們還在INFOCOM參會期間進行了類似的實驗；UMass研究小組[15]收集并分析了由公交車上的Wi-Fi節(jié)點組成的機會網絡DieselNet實際運行中的相遇規(guī)律。文獻[2]通過分析文獻[13]中的數據集發(fā)現，實際節(jié)點的移動具有社區(qū)特性，節(jié)點相遇時間服從近似的冪律分布，而不是根據經典移動模型推導出的指數分布，這些成果證實了傳統(tǒng)的移動模型并不一定適用于實際節(jié)點的移動特征，但研究人員在對于使用何種分布的移動模型問題上一直存在爭議。文獻[16]試圖統(tǒng)一這兩種類型的移動模型，作者從理論上推導出在一個有限邊界的移動空間中，節(jié)點相遇間隔時間服從指數分布，如果去掉有限邊界的條件，按照RW模型移動的節(jié)點相遇間隔就與統(tǒng)計觀察到的結果相一致，服從近似冪律分布。2.4.3基于社區(qū)的移動模型人所攜帶設備組成的網絡是機會網絡的一個主要應用，探索適用于這類場景且便于數學分析的移動模型機會網絡研究的一個重點?；谟扇私M成的機會網絡節(jié)點移動實際表現出的社區(qū)特性，一些研究人員提出了基于社區(qū)的移動模型(communitybasedmodel)。該模型下的節(jié)點并不是隨機選取移動位置，而是考慮了3種情況來決策下一步移動位置：1)節(jié)點偏好，節(jié)點比其他節(jié)點更傾向于去往某個特定位置或遇到特定節(jié)點;；2)節(jié)點異構性:某些節(jié)點能夠到達所有位置，遇到所有其他節(jié)點；3)行為時變性:節(jié)點移動隨著時間變化。Musolesi等人[17]結合社會網絡理論提出了一種基于社區(qū)的移動模型。該模型根據節(jié)點之間聯系的緊密程度，將節(jié)點分布在多個在不同區(qū)域的社區(qū)，然后計算不同社區(qū)對每個節(jié)點的吸引力，并以此確定節(jié)點是否移動以及朝哪個目標區(qū)域移動。Spyropoulos等人[18,19]提出了時變的社區(qū)移動模型，每個節(jié)點的工作周期由正常移動周期和集中移動周期組成，每個周期內，節(jié)點隨機選擇一個社區(qū)作為它的本地社區(qū)。節(jié)點在每個周期都有兩種移動狀態(tài)，Localepoch和Roamingepoch。前者是選擇在本地社區(qū)內移動，后者是在其他地方漫游。節(jié)點在兩個狀態(tài)之間以一定的概率來切換，形成一個馬爾可夫鏈，概率大小由所處的移動周期來確定。例如，在集中移動周期內，節(jié)點訪問本地社區(qū)的概率較高。2.5網絡編碼的概念思想在傳統(tǒng)網絡中，結點僅對接收的數據進行存儲和轉發(fā)，難以達到網絡傳輸的最大吞吐量和帶寬利用率，若數據傳輸路徑出現瓶頸鏈路，則網絡數據傳輸性能將受限于瓶頸鏈路。對此，在網絡中引入網絡編碼技術，增加結點對數據的編碼運算功能，節(jié)約網絡鏈路的帶寬資源，減小網絡數據傳輸中瓶頸鏈路的影響。網絡編碼(networkcoding)是一種融合編碼和路由的信息交換技術，在傳統(tǒng)存儲轉發(fā)的路由方法基礎上，通過允許對接收的多個數據包進行編碼信息融合，增加單次傳輸的信息量，提高網絡整體性能。Ahlswede等人于2000年提出了網絡編碼概念，指出對組播網絡中的某些節(jié)點附加額外的編碼操作能使源與組播成員間達到最大流最小割心的組播速率。網絡編碼一經提出便引起了國際學術界的廣泛關注，其理論和應用已成為通信領域研究的新熱點．網絡編碼在提高網絡吞吐量、改善負載均衡、減小傳輸延遲、節(jié)省節(jié)點能耗、增強網絡魯棒性等方面均顯示出其優(yōu)越性，可廣泛應用于AdHoe網絡，傳感器網絡、P2P內容分發(fā)、分布式文件存儲和網絡安全等領域。經過幾年的發(fā)展，網絡編碼的理論研究已取得重要進展，在應用基礎和工程實踐方面的研究正在全方位展開。網絡編碼已成為一項融合信息論、代數學、圖論、網絡流理論和優(yōu)化理論等多學科的交叉技術，且日益引起更多研究者的關注，其對現有的網絡體系結構、協議設計方法、信息交換方式和網絡管理模式帶來了革命性的變化。網絡編碼的基本思想是使網絡中的節(jié)點不僅具有存儲轉發(fā)的功能，他們還能夠打若干個待轉發(fā)的數據包進行編碼壓縮成一個數據包，然后轉發(fā)給相應的接收節(jié)點，并且以足夠大的概率保證它的接收節(jié)點能夠順利地解碼恢復出原始的數據包，從而減少傳輸次數，提高網絡吞吐量，降低網絡延遲。以一個簡單的具代表性的蝴蝶網絡來描述網絡編碼的思想，一下均假設每條鏈路單位時間只能傳輸單位bit的數據數據信息量。圖2.3和圖2.4中分別是利用網絡編碼前后的網絡傳輸狀態(tài)，該網絡有一個源節(jié)點S，兩個端節(jié)點Y，Z以及其余4個T,W,U,X是四個中轉節(jié)點。在圖2.2中，b1和b2都是源s向端節(jié)點y和x發(fā)出的兩個單位bit的信息，當b1和b2到達w節(jié)點時，由于一次只能處理一個單位的信息，所以W只能選擇發(fā)送其中之一，而另一個則必須送入等待隊列，因此，要使Y和Z這兩個目的節(jié)點都要收到這兩個信息，則W必須至少傳送兩次；圖2.3表示的是網絡編碼方法，節(jié)點W對輸入的信息進行網絡編碼操作（“+”表示模二加），然后將操作結果b1+b2（稱為編碼信息）發(fā)送至輸出鏈路(W,X)，然后又通過鏈路(X,Y)和(X,Z)，最終傳送給信宿Y和Z。當信宿Y收到b1和b1+b2后，通過逆過程的譯碼操作b1+(b1+b2)就能恢復出信源S發(fā)出的b2，這樣使得信宿Y同時收到了b1和b2。按照同樣的方式，信宿Z也可恢復出信源發(fā)出的b1（通過譯碼操作b2+(b1+b2)）而同時收到b1和b2。也就是說，基于網絡編碼的數據分發(fā)模式實現了該組播的理論傳輸容量?？梢?，與傳統(tǒng)的路由傳輸方式相比，網絡編碼提升了網絡的吞吐量。圖2.2網絡結構 圖2.3普通的存儲轉發(fā)圖2.4運用網絡編碼從上述實例可以看出，基于網絡編碼的數據分發(fā)的具體實施過程是：具備編碼條件的中間節(jié)點（比如該節(jié)點的入度至少為2，如圖2.4中的節(jié)點W就具備編碼條件，節(jié)點T，U和X等則不具備編碼條件，只能執(zhí)行存儲和轉發(fā)操作）對接收到的數據信息按照一定方式的處理（編碼），然后傳輸給下一級的網絡節(jié)點，收到信息的下一級節(jié)點如果具備編碼條件，又對其接收的信息按照同樣的方式進行處理和傳輸，如此反復，直到所有經過處理后的信息都匯聚到信宿節(jié)點為止。最后，在信宿節(jié)點，通過逆過程的操作（譯碼），即可譯出信源發(fā)出的原始信息。節(jié)點對傳輸的信息進行如何處理和操作，屬于網絡編碼的碼構造問題。如果節(jié)點對傳輸的信息進行線性操作，則稱為線性網絡編碼；否則稱為非線性網絡編碼（Non-linearNetworkCoding）。如果網絡節(jié)點對信息進行操作的系數是隨機選取的，則稱為隨機網絡編碼；如果是通過算法確定出來的，則稱為確定性網絡編碼。因此，線性網絡編碼是一種有效的網絡編碼碼構造方式，當前具體的基于網絡編碼的數據分發(fā)系統(tǒng)中均采用線性網絡編碼作為其碼構造方式。圖2.4所示的節(jié)點W對輸入的信息b1和b2進行的模二加操作，就是一種最簡單的線性網絡編碼操作方式。2.6網絡編碼的應用雖然網絡編碼提出的初衷是為改善組播傳輸網絡中數據分發(fā)系統(tǒng)的傳輸性能，但隨著研究的不斷深入，網絡編碼表現出了越來越廣泛的應用前景。目前，網絡編碼與覆蓋網絡（OverlayNetwork）和無線網絡（WirelessNetwork）等相結合的研究取得了重要的進展，被認為是網絡編碼最有可能被首先應用的領域。數據分發(fā)網絡編碼最直接的應用就是數據分發(fā)，尤其是大范圍的數據分發(fā)。前面討論的基于組播網絡的數據分發(fā)，均是網絡編碼最典型的應用。Chou等最早將隨機網絡編碼付諸實施，構建了一個可實用化的網絡編碼數據分發(fā)系統(tǒng)，并在Washington大學的Rocketfuel項目所獲得的幾個ISP骨干網絡拓撲上進行了仿真，取得了較好的傳輸性能。CodedStream也是在網絡中較早進行了基于網絡編碼的數據分發(fā)的嘗試[71]，CodedStream是一個基于P2P模式的，面向高帶寬流媒體的數據分發(fā)系統(tǒng)。它按照編碼網絡分發(fā)數據的特性，在覆蓋網絡上構建一個K-redundant路徑圖作為網絡拓撲，網絡編碼被用于圖中“瓶頸”處的數據分發(fā)。最初的CodedStream在自己的仿真平臺上進行了測試，其后續(xù)研究將整個思想進一步擴展，并利用PlanetLab平臺進行了更廣泛的測試。網絡編碼與應用層組播（ApplicationLayerMulticast，ALM）相結合也取得一定進展。應用層組播中的數據分發(fā)由客戶端主機實現的，端主機具有一定的計算能力，這為網絡編碼提供了良好的應用環(huán)境。而且，應用層組播利用的覆蓋網絡拓撲可以按需變化，這也恰好可以利用網絡編碼對動態(tài)網絡適應性強的優(yōu)勢。Y.Zhu給出了一個基于網絡編碼的應用層組播的完整實現。通過對比測試，證明了基于網絡編碼的應用層組播在網絡吞吐量、資源利用率等方面的性能要優(yōu)于網絡層組播和普通的應用層組播。但是在傳輸遲延和信息冗余等方面不夠理想。而且，大多數情況下，網絡編碼能將應用層組播的吞吐量提升一倍以上。但是，T.Nad等通過進一步的實驗證實，由于在執(zhí)行編碼和譯碼操作時需要一定的I/O和CPU消耗，基于網絡編碼的應用層組播的傳輸容量往往無法達到預期。無線網絡由于無線鏈路的不可靠性和物理層廣播特性，應用網絡編碼，可以解決傳統(tǒng)路由、跨層設計等技術無法解決的問題。具體來說，網絡編碼除了提升無線網絡的網絡吞吐量，還可以減少數據包的傳播次數，降低無線發(fā)送能耗。采用隨機網絡編碼，即使部分網絡節(jié)點或鏈路失效，最終在目的節(jié)點仍然能恢復原始數據，從而增強網絡的容錯性和魯棒性。此外，無需復雜的加密算法，采用網絡編碼就可以提高無線網絡的安全性等。文獻[20]對網絡編碼在無線自組織網絡（WirelessAdHocNetworks）、無線傳感器網絡（WirelessSensorNetworks）和無線網狀網(WirelessMeshNetworks)中的應用進行了探討。J.Yuan提出了一種利用網絡編碼來優(yōu)化信息流的路由方法[21]，以此來提升AdHoc網絡中數據分發(fā)的效率。該方法基于一種在網絡層和物理層平衡鏈路帶寬供需的跨層優(yōu)化策略。Y.Wu等在AdHoc組播方面提出了應用網絡編碼的最小化能量解決方法[22]，使得傳輸每比特信息消耗的能量最小，以此來節(jié)省AdHoc網絡中數據分發(fā)的能耗。此外，還有一些學者對如何利用網絡編碼增加AdHoc傳輸的魯棒性問題進行了研究，如Chen等研究在分布式天線系統(tǒng)和多入多出系統(tǒng)（DAS-MIMO）中，引入網絡編碼的概念，經過理論推導和實驗仿真，證明了無論有無輔助天線，網絡編碼都能提高網絡的性能，尤其是減小系統(tǒng)丟包損耗。相對于AdHoc網絡，無線傳感器網絡密度較大，移動性不強，通常運行在無人值守的惡劣甚至危險的遠程環(huán)境中，能源無法替代，設計有效的策略延長網絡的生命周期成為無線傳感器網絡的核心問題。麻省理工學院的Petrovic等人提出了一種結合網絡編碼的對無線信號不進行調制的策略[23]，并證明：運用分布式隨機網絡編碼，未經調制的無線信號能夠達到與經過調制的無線信號一樣的吞吐量，這樣就能節(jié)省大量因為模擬器件進行調制而消耗的能量和降低節(jié)點的成本。傳感器網絡需要把節(jié)點資源整合起來，實現一個可靠和健壯的網絡，基于這種想法，文獻[35]提出了一種結合分布式源編碼和網絡編碼的優(yōu)化算法，目的是用來提高傳感器網絡的容錯性和可靠性，同時對分布式源編碼的壓縮效率和魯棒性進行了折中考慮。Katti等提出的基于機會的網絡編碼方法（COPE）首次研究了網絡編碼在無線環(huán)境協議層面上的具體實現問題。在COPE協議中，每個節(jié)點對傳輸媒體進行偵聽，獲得它的鄰居節(jié)點的狀態(tài)信息，決定進行編碼的機會，并在本地的FIFO緩存結構內進行編碼，然后進行基于機會的路由。COPE協議要求每個節(jié)點利用本地信息各自決定哪些數據包需要進行編碼以及如何進行編碼。靈活的設計使得即使在網絡交通需求未知或者網絡流量劇增、或者發(fā)送/接收方動態(tài)變化的情況下，COPE協議仍能有效的支持多路單播流。然而該協議需要節(jié)點存儲數據包并進行編碼，如果網絡出現擁塞，可能就會耗費較多的節(jié)點存儲空間。另外，文件共享是無線網狀網的一種典型應用，為了評估網絡編碼對該應用的影響，Hamra等[64]在理想化MAC協議基礎上開發(fā)了特定的仿真平臺，分別比較了服務時間等性能在節(jié)點個數、盲轉發(fā)（BlindForwarding）和選擇性轉發(fā)（SelectiveForwarding）情況下的表現。實驗結果表明應用網絡編碼得到的改進雖然不如在有線網絡中顯著，但仍能在很大程度上提高吞吐量、縮短服務時間。2.7隨機線性網絡編碼的數據分發(fā)隨機線性網絡編碼方法的核心思想是利用節(jié)點的運算能力，在發(fā)送節(jié)點線性編碼組合不同的信息包，在接收節(jié)點獲得足夠的線性編碼組合后，通過運算得到原始信息包，其可用性推廣了網絡編碼理論的應用范圍。應用網絡編碼的理論成果，Gkantsidis等給出了基于隨機網絡編碼的數據分發(fā)系統(tǒng)的原理模型（或稱概念模型），如圖2.5所示。假設Server節(jié)點（存放原始文件的服務器）需分發(fā)某文件給PeerA，首先Server將該文件分割成n個文件塊（Block），即B1，B2，B3Bn，如果使用網絡編碼，則Server節(jié)點從有限域中選擇n個系數C11,C12C1n構成編碼向量（EncodingVector)c1=[C11,C12C1n]，并利用該向量對分割后的文件塊進行有限域中的線性運算。隨后，Server節(jié)點將運算后的編碼信息E1=B1c11+B2c12++Bnc1n，分發(fā)給PeerA圖2.5基于隨機線性網絡編碼的數據分發(fā)系統(tǒng)的原理模型假設PeerA又下載了另外一個編碼信息塊E2=B1c21+B2c22++Bnc2n，該信息來自Server節(jié)點或其它鄰居節(jié)點，當PeerB對PeerA發(fā)出下載請求時，PeerA按照上述同樣的方式在有限域中選擇系數c1",c2"，并對當前緩存的編碼信息塊E1和E2進行線性組合，將運算結果E'=E1c1"+E2c2"分發(fā)給PeerB。如果下游節(jié)點向PeerB請求數據包，則PeerB按照同樣的規(guī)則將編碼后的數據信息分發(fā)給下游節(jié)點。對PeerB收到的E'而言，其對應的編碼向量為c1c1"+c2c2"?？梢?，采用網絡編碼，節(jié)點之間不再傳輸原始的文件塊，而是編碼信息（塊）。當某Peer接收到n個已編碼信息E1,E2...,En后，則有：公式(2.1)如果公式2.1的系統(tǒng)轉移矩陣C滿秩，即各編碼向量之間線性獨立，則能通過求解矩陣方程[B1,B1Bn]=C-1[E1,E2En]T譯出各原始文件塊B1,B1Bn，并恢復出原始文件。由于采用隨機網絡編碼總能保證矩陣C以接近1的概率滿秩，基于隨機網絡編碼和圖2.5所示的原理模型，文獻[25]構建了一種網絡編碼數據分發(fā)的原型系統(tǒng)：Avalanche。在Avalanche系統(tǒng)中，節(jié)點之間傳輸的信息是按照上述原理對原始文件塊執(zhí)行隨機網絡編碼操作后的編碼信息。Avalanche能克服基于存儲和轉發(fā)的數據分發(fā)系統(tǒng)（如BitTorrent等）的缺陷和不足，可以顯著減少節(jié)點平均下載時間，進一步提升數據分發(fā)系統(tǒng)的傳輸性能。3NS2仿真平臺3.1NS2簡介NS2，即NetworkSimulatorVersion2，是面向對象的、離散事件驅動的網絡環(huán)境模擬器，主要用于解決網絡研究方面的問題。NS2提供了在無線或有線網絡上的TCP、路由、多播等多種協議的模擬。NS2—晝以來都在吸收全世界各地研究人員的成果，包括UCB、CMU笏大學和SUN等公司的無線網絡方面的代碼。NS2足一個面向對象的網絡桟擬工具，對以完整地模擬整個網絡壞境。NS2使用一整套C++類庫實現了大多數常見的網絡協議以及鏈路層模型，利用這些類的實例可以搭建起整個網絡的模型，而且包括具體的細節(jié)實現。NS2使用兩種編程語言，OTcl（具有面向對象特性的Tcl腳本程序設計語言）和C++，它底層的模擬引擎主要由C++編寫，同時利用麻省理工學院的面向對象的工具命令語言OTcl作為模擬時的命令和配置接口語言。一方面，由于C++程序運行速度快，并且可以設計精確、復雜的算法，可以用于模擬各種網絡協議，適合于底層的實現。另一方面，具有面向對象特性的Tcl腳本語言通過調用引擎中各類的屬性、方法定義網絡的拓撲，配置數據源，目的端，建立連接，產生所有事件的時刻表，運行并跟蹤模擬結果，還可以對結果進行相應的統(tǒng)計處理或制圖，方便網絡研究者在短時間內快速地開發(fā)和模擬出所需要的網絡壞境。和兩種語言的對象和變量是通過關聯起來的，++的類和對象為編譯類和編譯對象，而的類和對象為解釋類和解釋對象，是在基礎上的封裝。圖是架構圖，描述了l、l和之間的關系。圖3.1NS2構架圖3.2NS2的特點1、抽象NS模擬器在設計上能夠滿足網絡研究界在模擬方面的多種需。抽象NS具備不同程度的抽象級別，不僅可以對細節(jié)進行模擬，也對以對不同層次的總體框架進行模擬。2、仿真NS提供了更加接近真實網絡的仿真環(huán)境，這是其他仿真軟件所不具備的。3、場景生成NS中自帶了流最場景生成文件和運動場景cbrgen生成文件setdest，讓使用更加方便，當然也支持用戶按照自己的實際需要編寫場景及運動文件腳本。4、可視化通過其中的網絡動畫工具Nam,以動畫的方式實現網絡仿真的全過程，讓整個運動過程一目了然。5、可擴充性可擴充性表現在可以方便的添加新協議，讓使用范圍更加廣泛。3.3NS2仿真一般流程進行網絡仿真前，首先分析仿真涉及哪個層次，NS仿真分兩個層次：一個是基于OTcl編程的層次。利用NS已有的網絡元素實現仿真，無需修改NS本身,只需編寫OTcl腳本。另一個是基于C++和OTcl編程的層次。如果NS中沒有所需的網絡元素，則需要對NS進行擴展，添加所需網絡元素，即添加新的C++和OTcl類，編寫新的OTcl腳木。假設用戶已經完成了對NS的擴展，或者NS所包含的構件已經滿足了要求，那么進打一次仿真的步驟大致如下：1、開始編寫OTcl腳本。首先配置模擬網絡拓撲結構，此時可以確定鏈路的基本特性，如延遲、帶寬和丟失策略等。2、建立協議代理，包栝端設備的協議綁定和通信業(yè)務量模型的建立。3、配置業(yè)務量模型的參數，從而確定網絡上的業(yè)務量分布。4、設置Trace對象。NS通過Trace文件來保存整個模擬過程。仿真完后,用戶可以對Trace文件進行分析研究。5、編寫其他的輔助過程，設定模擬結束時間，至此OTcl腳本編寫完成。6、用NS解釋執(zhí)行剛才編寫的OTcl腳本。7、對Trace文件進行分析，得出有用的數據。8、調整配置拓撲結構和業(yè)務量模型，重新進行上述模擬過程。下面是仿真的流程圖：圖3.2NS2進行仿真的基本流程圖3.4NS2仿真的基本組件和使用3.4.1節(jié)點的結構和配置無線網絡中的節(jié)點是可移動的節(jié)點，擁有很多屬性，如果使用NS研究無線網絡需要在無線節(jié)點創(chuàng)建之前對節(jié)點的各項屬性進行配置。節(jié)點的屬性配置使用Simulator類的noed-config{}方法，該方法采用可變的模塊化結構，以實現不同類型的節(jié)點在相同的節(jié)點基類下定義。配置好屬性以后再創(chuàng)建節(jié)點，這是創(chuàng)建節(jié)點的基本方式，如需創(chuàng)建不同的節(jié)點則重新配置屬性以后再創(chuàng)建。下面是使用node-config{}配置一個節(jié)點屬性的例子。setns[newSimulator] #建立一個模擬實例settopo[newTopography] #建立一個拓撲圖對象#配置無線節(jié)點$nsnode-config-adhocRoutingAODV\ #無線路由協議是AODV協議 -llTypeLL\ #邏輯鏈路層類型是LL層 -macTypeMac/802.11\ #MAC層協議采用802.11協議 -ifqTypeQueue/DropTail/PriQueue\#接口隊列類型是IFQ隊列 -ifqLen50\ #網絡接口隊列的大小是50 -antTypeAntenna/QmniAntenna\ #天線模型是全向天線 -propTypePropagation/TwoRayGround\ #無線傳輸模型是TwoRayGround -phyTypePhy/WirelessPhy\ #網絡接口類型是無線物理層 -channelChannel/WirelessChannel\ #物理信道類型無線信道 -topoInstance$topo\ #設置拓撲實例 -agentTraceON\ #開啟代理層trace -routerTraceON\ #開啟路由層trace -macTraceOFF\ #關閉mac層的trace -movementTraceOFF #關閉移動節(jié)點的移動記錄設置完節(jié)點的屬性之后，使用node-congfig{}方法的-reset選項可以將節(jié)點的所有屬性的參數值設置為默認值：$nsnode-config-reset3.4.2數據流生成工具cbrgenNS2自帶有交通場景生成器，名稱為cbrgen.tcl。數據流生成工具cbrgen用來生成傳輸負載，可以產生移動節(jié)點之間的TCP流和CBR流。該工具所在的目錄為~ns/indep-utils/cmu-scen-gen/，使用方法如下：nscbrgen.tcl[-typecbr/tcp][-nnnodes][-seedseed][-mcconnections][-raterate]其中各種參數的含義如下：-type：選擇tcp表示生成tcp流，選擇cbr表示生成cbr流；-nn：nodes表示節(jié)點數目；-seed：seed表示指定隨機種子；-mc：connections表示節(jié)點間的最大連接數；-rate：rate表示每個連接間的數據流的速率；在使用cbrgen設置節(jié)點數n時，節(jié)點的編號是從node_(1)到node_(n)。3.4.3拓撲運動場景生成工具setdest拓撲運動場景生成工具setdest是用來隨機生成無線網所需的節(jié)點運動場景，也即一定數量的節(jié)點在某一固定大小的矩形區(qū)域中隨機移動。生成setdest的命令的源代碼文件在~ns/indep-utils/cmu-scen-gen/setdest文件夾下，使用前需執(zhí)行make命令以生成可執(zhí)行文件。setdest的使用方法如下：setdest-v<1>-n<nodes>-p<pause_time>-M<max_speed>-t<simulation_time>-x<max_x>-y<max_y>或setdest-v<2>-n<nodes>-s<speed_type>-m<min_speed>-M <max_speed>-t<simulation_time>-P<pause_type>-p<pause_time>-x <max_x>-y<max_y>其中使用到的參數定義如下：-v：version_of_setdest指定setdest的版本；-n：nodes指定場景中總節(jié)點數目；-p：pause_time指定了節(jié)點在運動到一個目的點后停留的時間，如果設置為0表示節(jié)點不做停留；-s：speed_type為uniform/normal；-m：min_speed指定節(jié)點移動的最小速率；-M:max_speed指定節(jié)點移動的最大速率；-P：pause_type為constant/uniform；-t：simulation_time指定了模擬場景的持續(xù)時間，單位為s；-x：max_x指定了節(jié)點運動區(qū)域的長度，單位為m；-y：max_y指定了節(jié)點運動區(qū)域的寬度，單位為m；版本不用使用的參數也有區(qū)別，需按要求使用。執(zhí)行make命令生成可執(zhí)行文件以后，若沒有將setdest命令添加到linux系統(tǒng)環(huán)境變量中，則應在使用setdest時需要指定路徑全稱或在~ns/indep-utils/cmu-scen-gen/setdest目錄下使用，而且要在setdest前面加“./”。cbrgen和setdest產生的文件均可以采用source命令加入另一個Otcl腳本中，注意產生的文件用到了諸如node_數組變量和god_變量，需要在Otcl腳本中預先建立。3.4.4簡單動畫顯示工具NAMNAM（NetworkAnimater）的功能是根據網絡模擬軟件或真實環(huán)境的特定格式的Trace輸出文件來運行動畫，以觀測網絡模擬中的Trace和數據分組流向。NAM使用方法如下：nam-g<geometry>-t<graphInput>-i<interval>-j<startup_time>-k<initial_socket_port_number>-N<application_name>-c<cache_size>-f<configuration_file>-r<initial_animation_rate>-a-p-S<namfile>NAM命令中的參數意義如下：-g：指明NAM窗口的幾何位置；-t：指定nam使用tkgraph，并為tkgraph確定輸入文件；-i:指定屏幕刷新率，單位為毫秒（ms），默認為50ms；-j：指定nam演示時的仿真時間；-k：初始化socket端口號；-N：為nam實例命名，它可能在此后用于對等的同步；-g：指明NAM窗口的幾何位置；-c：進行反向演示（模擬的逆過程）時，緩沖區(qū)所能存儲的活動對象的最大值（size）；-f:演示啟動時所載入的文件；-r：演示速度，默認是2ms（0.002）；-a：創(chuàng)建一個獨立的nam實例；-p：打印Trace的文件格式；-S：開啟X同步以便于圖形的調試，僅限于有X環(huán)境的UNIX系統(tǒng)。OTcl腳本中可以對節(jié)點、鏈路、隊列、和Agent等對象進行動畫顯示方面的屬性控制，nam動畫顯示的命令如下：節(jié)點$nodecolor[color] #設定節(jié)點的顏色$nodeshape[shape] #設定節(jié)點的形狀$nodelabel[label] #設定節(jié)點的名稱$nodelabel-color[color] #設定節(jié)點顯示名稱的顏色$nodelabel-at[ldirection] #設定節(jié)點名稱的顯示位置2、鏈路和隊列$nsduplex-link-op<attribute><value>其中attribute的值可以是orient、color、queuePos和label。Orient指定了鏈路的方向，可以是：right、left、down、right-up、right-down、left-up以及l(fā)eft-down。Color指定鏈路的顏色，label定義鏈路顯示的名稱，queuePos定義隊列顯示的方向。Agent$nsattach-agent$node$Agent$nsadd-agent-trace$AgentAgentName使用上面的命令就可以使想要顯示的Agent以Agentname出現在節(jié)點的附近的方框內，這樣可以再nam顯示中看出摸個節(jié)點上綁定了哪些Agent。3.4.5Trace文件格式Trace文件是在模擬過程中生成的記錄模擬每一個分組調度事件的文件，一次模擬生成的信息基本上全體現在Trace文件中。Trace文件包含了很多有用的可供分析的數據，我們需要從中篩選出我們關注的數據進行分析。有線網絡的Trace格式有線網絡的Trace格式中每條記錄包含了如下截圖顯示12項內容：圖3.3有線網絡的Trace部分截圖內容現在來分析有線網絡的Trace格式的一條記錄中每一項的信息：Event：發(fā)生事件的類型有+、-、r和d等4種，分別表示分組進入鏈路隊列、分組離開鏈路隊列、目的節(jié)點接收分組以及隊列丟棄分組等含義。Time：事件發(fā)生的時間。Fromnode：發(fā)送分組的源節(jié)點id。Tonode：接收分組的目的節(jié)點id。Pkttype：分組的類型。Pktsize：分組的大小。Flags：標志項。Fid：IPv6定義的流標示符。Srcaddr：表示分組的來源端，例如2.0表示節(jié)點2的0號端口。Dstaddr：表示分組的目的端，例如3.0表示節(jié)點3的0號端口。Seqnum:分組的序列號。Pktid：分組的唯一標示符。無線網絡的Trace格式圖3.4無線網絡的Trace部分截圖內容無線網絡的Trace格式的記錄的每一項信息:(1)Event：事件的類型有是s、r、f和d4種，分別表示分組的發(fā)送、接收、轉發(fā)、丟棄事件。(2)Time：事件發(fā)生的時間。(3)Node：事件發(fā)生的節(jié)點id。(4)Layer：發(fā)生事件所在的層。(5)Flags：標志項。(6)Pktid：分組的id。(7)Pkttype：分組的類型。(8)Pktsize：分組的大小。(9)[MACLayerInfo]:MAC層的信息。(10):分隔符。(11)[IPInfo]:IP層的信息。3.5性能參數分析模型傳輸時延網絡的傳輸時延D（End-to-EndDelay）定義為源節(jié)點發(fā)送出一個分組到目的節(jié)點接收到該分組之間的時間差，它包括電（或光）信號在物理介質中的傳播延時和數據在網絡中的處理延時，也即指網絡中數據傳輸所用的時間。在很多網絡應用中，比較關注分組的時延大小，要求分組的時延不能太大，例如實時的視頻會議、網絡電話等。結合NS的Trace文件，以分組發(fā)送和到達接收之間的時間間隔來計算傳輸延時，計算方式如下：D（i）=RT（i）-S（i）T 公式（3.1）式中，D（i)表示第i個分組的傳輸時延，RT（i）表示第i個分組的接收時間，ST（i）表示第i個分組的發(fā)送時間。在分析網絡的傳輸時延時，一般都統(tǒng)計平均傳輸時延公式（3.2）即統(tǒng)計Trace腳本中N個分組的平均傳輸時延。網絡吞吐量網絡的吞吐量（Throughput）TH是網絡性能的一個重要參數，是指在不丟包的情況下單位時間內節(jié)點可以接收的數據量，單位是字節(jié)每秒或比特每秒。端到端的吞吐量與網絡狀況有很大關系，為了測試端到端的最大吞吐量，應該逐漸增大發(fā)送端的數據發(fā)送速率，然后計算接收端的吞吐量，直至吞吐量達到最大。在分析Trace文件時，使用以下的計算方式計算吞吐量： 公式（3.3）上式中：TB（i）是指到底i個分組被目的節(jié)點接收時已經傳輸的數據總量，RT（i）是第i個包的接收時間。i>m，表示計算從第m個分組到底i個分組的吞吐量，特別的，若取m=1則是計算平均吞吐量。3.6Trace文件分析處理3.6.1gawk處理文檔的過程gawk是一種對文檔資料具有很強處理能力的程序語言，簡短的幾句代碼就可以完成對文檔的修改、對比、抽取，相對其他的語言來說，其對文檔資料的處理方面具有很大的優(yōu)勢。gawk語言將說要處理的文檔分解為一條條的記錄（一般一條記錄是數據文件的一行數據），每條記錄默認以空格TAB鍵分隔為一個個字段。例如，Trace文件的每一行作為一個記錄，取實際Ttrace文件的記錄如下：圖3.5仿真實驗Trace文件部分截圖內容在對記錄的處理過程中，一般都要對記錄的字段進行操作。對記錄中字段的提取可以采用字段變量“$1，$2，$3”等，gawk讀入記錄后已自動把字段值存入字段變量。需要注意的是“$0”表示所讀取的整條記錄。表3.1是對圖3.5Trace文件的記錄進行分解和提取的例子。表3.1對Trace文件記錄的分解和提取一二三四五六七八九十十一r47.355426347_2_AGT251cbr532[13a25800][1:02:0292]$1$2$3$4$5$6$7$8gawk處理文檔的過程是針對檔案的每一條記錄搜尋指定的模式（Pattern），當記錄中有符合指定的模式時，gawk就會在此記錄執(zhí)行被指定的動作（Action）。gawk依照此方式處理輸入檔案的每一條記錄知道輸入檔案結束。gawk程序是由很多的Pattern與Action所組成，Action卸載大括號{}里面，一個pattern后面就跟著一個Action，整個gawk程式的結構如下：Pattern（1） {Action（1）}Pattern（2） {Action（2）}Pattern（n） {Action（n）}當讀取一條記錄時，該記錄會經過程序中所有Pattern的審查，如果滿足某一個Pattern，就執(zhí)行該Pattern后面的Action。執(zhí)行gawk程序有兩種方式，第一，如果gawk程序很短，則可以直接寫在終端命令行，如gawk“program”input-file1[input-file2...]，其中program包括一些Pattern和Action；第二，如果gawk程序較長，較為方便的做法是將gawk程序放在一個文檔中，即Pattern和Action寫在名為program-file的文檔里面，執(zhí)行gawk的格式如下所示：gawk-fprogram-fileinput-file1[input-file2...]gawk程序的文檔不止一個時，執(zhí)行gawk的格式如下所以：gawk-fprogram-file[-fprogram-file2...]input-file1[input-file2...]編寫gawk程序的規(guī)則是：Pattern或Action能夠被省略，但是不能同時被省略；如果Patte被省略，對于輸入文檔里面的每一條記錄，Action都會執(zhí)行；如果Action被省略，內定的Action則會打印出所以符合的Pattern的輸入行。其中BEGIN和END是特別的Pattern，gawk在開始或要結束時分別執(zhí)行相對應于BEGIN或END的Action。3.6.2使用xgraph繪圖Xgraph是NS2自帶的一個小巧的繪圖工具，是一個根據兩列數據生成平面圖形的繪圖工具，它還可以根據數據文件里的數據繪制出相應的圖形。一般數據文件由兩列數據組成，每一列表示圖中的一個點，第一列為x坐標，第二列為y坐標。兩列之間以空格（包括Tab）、逗號、分號、或者句號隔開。使用如下命名畫圖：xgraphfilenam1,filename2<-options>其中，filename1，filename2為數據文件，表明xgra可以將多個數據流的信息圖畫在一張圖上，有利于對數據進行比較。-options可以設定相關參數，包括繪圖的顏色、輸出圖形文件的格式、圖形的標題等。一些命令選型如下：-hpg以非交互的方式，將圖形以hpg文件格式輸出-t 設置圖形名稱-x設置x坐標軸的名稱-y 設置y坐標軸的名稱-bb 為圖形設置邊線-m 數據點加粗顯示-tk 用標記代替網格顯示4仿真實現4.1設計與建立機會網絡仿真模型了解機會網絡的拓撲特點及NS2仿真平臺的功能后，經過一番選擇，在NS2仿真平臺下建立如下的機會網絡拓撲模型，各參數如下表4.1表4.1機會網絡拓撲模型參數無線節(jié)點個數10個節(jié)點顯示大小40仿真拓撲場景大小500m×500m數據流類型cbrcbr分組的大小512字節(jié)每秒發(fā)送分組個數4場景最大數據流連接數5節(jié)點隨機移動最大速度20m/s節(jié)點停留時間0s仿真模型持續(xù)時間100s4.1.1編寫仿真模型腳本代碼選好機會網絡節(jié)點運動模型和路由協議后，就可以按照ns2仿真平臺的知識來編寫腳本代碼了。編好運行成功后的Tcl腳本代碼如下：#無線節(jié)點參數setval(chan) Channel/WirelessChannel #物理信道類型是無線信道setval(prop) Propagation/TwoRayGround #無線傳輸模型是TwoRayGroundsetval(netif) Phy/WirelessPhy #網絡接口層是無線物理層setval(mac) Mac/802_11 #MAC層協議采用802.11setval(ifq) Queue/DropTail/PriQueue #接口隊列模型是IFQ隊列setval(ll) LL #邏輯鏈路層類型是LL層setval(ant) Antenna/OmniAntenna #天線模型是全向天線setval(ifqlen) 50 #網絡接口隊列大小是50setval(rp) AODV #路由協議是AODVsetval(x) 500 #設定拓撲場景范圍-長度-500msetval(y) 500 #設定拓撲場景范圍-寬度-500msetval(stop) 100.0 #設定模擬仿真時間，100ssetval(nn) 10 #設定無線節(jié)點數目為10個setval(cp) "cbr-10-5-4" #流量場景生成文件setval(sc) "scene-10-20-100" #運動場景生成文件#建立一個模擬實例setns[newSimulator] #開啟Trace跟蹤文件和nam顯示文件 settracefd[open3.trw]setnamtrace[open3.namw]$nstrace-all$tracefd$nsnamtrace-all-wireless$namtrace$val(x)$val(y)#建立一個拓撲圖對象，記錄節(jié)點的移動情況settopo[newTopography]$topoload_flatgrid$val(x)$val(y)#創(chuàng)建god對象，存儲網絡狀態(tài)以及節(jié)點間的連接信息setgod_[create-god$val(nn)]#創(chuàng)建物理信道對象setchan_1_[new$val(chan)]#配置無線節(jié)點（包括各種參數）$nsnode-config-adhocRouting$val(rp)\ -llType$val(ll)\ -macType$val(mac)\ -ifqType$val(ifq)\ -ifqLen$val(ifqlen)\ -antType$val(ant)\ -propType$val(prop)\ -phyType$val(netif)\ -channel$chan_1_\ -topoInstance$topo\ -agentTraceON\ -routerTraceON\ -macTraceOFF\ -movementTraceOFF#建立無線節(jié)點for{seti0}{$i<$val(nn)}{incri}{ setnode_($i)[$nsnode] $node_($i)random-motion0; #禁止節(jié)點隨機移動}#調用流量場景生成文件source$val(cp)#調用隨機運動場景生成文件source$val(sc)#設定無線節(jié)點的大小for{seti0}{$i<$val(nn)}{incri}{ $nsinitial_node_pos$node_($i)40}#仿真結束時重置節(jié)點for{seti0}{$i<$val(nn)}{incri}{ $nsat100.0"$node_($i)reset";}#定義結束過程，關閉Trace文件盒NAM顯示文件，模擬結束時調用procfinish{}{ globalnstracefdnamtrace $nsflush-trace close$tracefd close$namtrace exit0}#模擬結束時調用結束過程$nsat$val(stop)"finish"$nsat$val(stop)"puts\"NSEXISTING...\";$nshalt"puts"StartSimulation..." #執(zhí)行模擬$nsrun4.1.2數據流場景文件的生成數據流類型選擇cbr流，包固定大小為512比特，無線節(jié)點數目10個，隨機種子設為1，節(jié)點間的最大連接數設為5且每秒發(fā)送4個分組包，所以數據發(fā)送速率為4×512×8=16kbps。調用數據流生成工具cbrgen生成數據流場景文件cbr-10-5-4：圖4.1數據流場景文件生成執(zhí)行上述命令后，就會生成一個cbr-10-5-4的文件，然后把生成的這個文件放到跟Tcl腳本文件相同的目錄下，就可以在Tcl腳本中用souce命令調用這個文件了。生成的數據流場景文件cbr10-5-4的里面代碼內容如下：#nodes:10,maxconn:5,sendrate:0.25,seed:1#1connectingto2attime2.5568388786897245setudp_(0)[newAgent/UDP]$nsattach-agent$node_(1)$udp_(0)setnull_(0)[newAgent/Null]$nsattach-agent$node_(2)$null_(0)setcbr_(0)[newApplication/Traffic/CBR]$cbr_(0)setpacketSize_512$cbr_(0)setinterval_0.25$cbr_(0)setrandom_1$cbr_(0)setmaxpkts_10000$cbr_(0)attach-agent$udp_(0)$nsconnect$udp_(0)$null_(0)$nsat2.5568388786897245"$cbr_(0)start"#4connectingto5attime56.333118917575632setudp_(1)[newAgent/UDP]$nsattach-agent$node_(4)$udp_(1)setnull_(1)[newAgent/Null]$nsattach-agent$node_(5)$null_(1)setcbr_(1)[newApplication/Traffic/CBR]$cbr_(1)setpacketSize_512$cbr_(1)setinterval_0.25$cbr_(1)setrandom_1$cbr_(1)setmaxpkts_10000$cbr_(1)attach-agent$udp_(1)$nsconnect$udp_(1)$null_(1)$nsat56.333118917575632"$cbr_(1)start"#4connectingto6attime146.96568928983328setudp_(2)[newAgent/UDP]$nsattach-agent$node_(4)$udp_(2)setnull_(2)[newAgent/Null]$nsattach-agent$node_(6)$null_(2)setcbr_(2)[newApplication/Traffic/CBR]$cbr_(2)setpacketSize_512$cbr_(2)setinterval_0.25$cbr_(2)setrandom_1$cbr_(2)setmaxpkts_10000$cbr_(2)attach-agent$udp_(2)$nsconnect$udp_(2)$null_(2)$nsat146.96568928983328"$cbr_(2)start"#6connectingto7attime55.634230382570173setudp_(3)[newAgent/UDP]$nsattach-agent$node_(6)$udp_(3)setnull_(3)[newAgent/Null]$nsattach-agent$node_(7)$null_(3)setcbr_(3)[newApplication/Traffic/CBR]$cbr_(3)setpacketSize_512$cbr_(3)setinterval_0.25$cbr_(3)setrandom_1$cbr_(3)setmaxpkts_10000$cbr_(3)attach-agent$udp_(3)$nsconnect$udp_(3)$null_(3)$nsat55.634230382570173"$cbr_(3)start"#7connectingto8attime29.546173154165118setudp_(4)[newAgent/UDP]$nsattach-agent$node_(7)$udp_(4)setnull_(4)[newAgent/Null]$nsattach-agent$node_(8)$null_(4)setcbr_(4)[newApplication/Traffic/CBR]$cbr_(4)setpacketSize_512$cbr_(4)setinterval_0.25$cbr_(4)setrandom_1$cbr_(4)setmaxpkts_10000$cbr_(4)attach-agent$udp_(4)$nsconnect$udp_(4)$null_(4)$nsat29.546173154165118"$cbr_(4)start"#Totalsources/connections:4/54.1.3隨機運動場景文件的生成指定setdest的版本號為1，場景總節(jié)點數目為10，節(jié)點不停留，最大移動速度設為20m/s，仿真時間為100s，拓撲場景的范圍為500m，500m，由此調用setdest工具生成隨機運動場景文件scene-10-20-100：圖4.2生成隨機運動場景文件如圖4.2執(zhí)行上述命令后得到隨機運動場景文件scene-10-20-100，然后也必須把這個文件放到跟Tcl腳本文件相同的目錄下才能在Tcl腳本文件中用source調用隨機運動場景文件。scene-10-20-100文件的詳細代碼見附錄A。4.2NAM查看運行過程處理好Tcl腳本文件、cargen-10-5-4文件及scene-10-20-100文件后，就可以運行Tcl腳本文件并用NAM來查看整個仿真拓撲的運行變化了。先執(zhí)行Tcl腳本文件后會產生2個分別是.nam文件和.tr文件，再運行.nam文件就可以看到拓撲運行動畫了。執(zhí)行過程如下圖4.3所示：圖4.3nam文件執(zhí)行過程生成的動畫如下：圖4.4time=47.294286時刻的網絡運行狀態(tài)的截圖圖4.5time=29.375975時刻nam動畫放大后的狀態(tài)截圖圖4.6time=29.554319時刻的運行狀態(tài)截圖其中圖4.4中顯示的就是time=47.294286時刻的網絡運行狀態(tài)，各個無線節(jié)點都在隨機運動并發(fā)送數據；圖4.5是time=29.375975時刻的狀態(tài)，圖中的那兩個黑色斑點就是節(jié)點之間發(fā)送的分組包，通過查看Trace文件3.tr內容可知分別表示節(jié)點5接收節(jié)點1發(fā)來的分組和節(jié)點5轉發(fā)由源節(jié)點1發(fā)送給目的節(jié)點2的分組包；圖4.6中圓圈表示發(fā)射功率的范圍，功率越大，范圍越大，功率越小，范圍越小，說明time=29.554319時刻有新的數據流cbr產生，各個節(jié)點開始偵聽新的路由路徑，我們也可以從數據流場景的生成文件cbrgen-10-5-4的內容中得到證明。4.3仿真結果分析當運行nam文件觀看完整個仿真網絡拓撲的運行狀態(tài)后，就可以開始用gawk語言對Trace文件3.tr進行分析得到想要的相關網絡性能參數，然后通過xgraph工具對分析處理得到的數據進行繪圖得到更直觀的表現。4.3.1時延分析根據得到的Trace文件3.tr及第四部分的時延的定義算式編寫出分析時延的gawk程序:3delay.awk,編寫的代碼內容為：BEGIN{highest_pkt_id=0; #保存已處理過的分組中最大的pkt_id值}{ event=$1; #第1個字段$1標識事件的類型 time=$2; #第2個字段$2標識事件的發(fā)生的時間 node_id=$3; #第3個字段$3標識事件發(fā)生所在的節(jié)點 node_=substr(node_id,2,1); #獲取節(jié)點號，從_x_變成xtrace_type=$4; #第4個字段$4標識事件發(fā)生所在的網絡層面flag=$5;pkt_id=$6; #第6個字段$6標識分組的idpkt_type=$7; #第7個字段$7標識分組的類型 pkt_size=$8; #第8個字段$8標識分組的大小 if(pkt_id>highest_pkt_id)#更新highest_pkt_id的值 highest_pkt_id=pkt_id;if(event=="s"&&trace_type=="AGT"&&pkt_type=="cbr") start_time[pkt_id]=time; #滿足條件的話保存發(fā)送分組的時間 if(trace_type=="AGT"&&pkt_type=="cbr"&&event=="r") end_time[pkt_id]=time; #滿足條件保存目的節(jié)點接收分組的時間 }#程序結束時執(zhí)行END的動作 END{ for(pkt_id=0;pkt_id<=highest_pkt_id;pkt_id++){