【正文】 中，Chen引入網(wǎng)絡編碼的概念，經(jīng)過理論推導和實驗仿真，證明了在分布式天線系統(tǒng)中，不論有無輔助天線，網(wǎng)絡編碼都能提高網(wǎng)絡的性能，尤其是減小系統(tǒng)丟包損耗。Chen研究的不足之處在于主要關(guān)注的是小型網(wǎng)絡中線性網(wǎng)絡編碼的應用，沒有考慮分布式隨機網(wǎng)絡編碼和網(wǎng)絡規(guī)模較大的情況。在大規(guī)模的無線網(wǎng)絡中，可以在網(wǎng)絡編碼的基礎上結(jié)合應用分布式信道編碼，進一步提高網(wǎng)絡性能。盡管網(wǎng)絡編碼已經(jīng)確立了它在理論上提高網(wǎng)絡吞吐量的地位，但是很少有研究者把目光投向網(wǎng)絡編碼的具體實現(xiàn)這個領(lǐng)域。Katti 等[32]提出的基于機會的網(wǎng)絡編碼方法(COPE)則是首次研究網(wǎng)絡編碼在無線環(huán)境中的協(xié)議層面上具體實現(xiàn)的問題。在COPE 協(xié)議中,每個節(jié)點對傳輸媒體進行偵聽，獲得它的鄰居節(jié)點的狀態(tài)信息，決定進行編碼的機會，并在本地的先進先出（First Input First Output，F(xiàn)IFO）緩存結(jié)構(gòu)內(nèi)進行編碼，然后進行基于機會的路由。COPE 協(xié)議要求每個節(jié)點利用本地信息各自決定哪些數(shù)據(jù)包需要進行編碼以及如何進行編碼。靈活的設計使得即使在網(wǎng)絡交通需求未知或者網(wǎng)絡流量劇增、或者發(fā)送/接收方動態(tài)變化的情況下，COPE 協(xié)議仍能有效的支持多路單播流。然而該協(xié)議需要節(jié)點存儲數(shù)據(jù)包并進行編碼，如果網(wǎng)絡出現(xiàn)擁塞，可能就會耗費較多的節(jié)點存儲空間。本文后面將基于COPE編碼進行改進。 網(wǎng)絡編碼的性能優(yōu)點Ahlswede等在提出網(wǎng)絡編碼時指出，通過網(wǎng)絡編碼可以提高網(wǎng)絡多播的容量，達到網(wǎng)絡多播的最大流限，這是網(wǎng)絡多播的理論上限。通過對網(wǎng)絡編碼的研究，人們發(fā)現(xiàn)網(wǎng)絡編碼多播較傳統(tǒng)的路由多播的好處不僅僅局限在網(wǎng)絡多播的容量方面。下面我們將具體討論網(wǎng)絡編碼多播的好處。 網(wǎng)絡多播容量的改善網(wǎng)絡編碼最主要的應用就是提高多播系統(tǒng)的信息傳輸速率，即達到網(wǎng)絡拓撲圖的最大流，而傳統(tǒng)的路由方式則無法實現(xiàn)。對于一個單源多播網(wǎng)絡，最大的信息傳輸速率為，其中T是多播接收節(jié)點集合，該值是多播傳輸速率的理論上限值，稱之為多播容量，網(wǎng)絡編碼可以達到該多播容量。，我們通過一個典型的網(wǎng)絡拓撲指出，只有采用網(wǎng)絡編碼才能獲得網(wǎng)絡多播的最大流限，而無法通過傳統(tǒng)的路由多播獲得。但是這并不能完全刻畫基于網(wǎng)絡編碼的多播與傳統(tǒng)的IP多播在多播容量性能上的差異，因為網(wǎng)絡編碼的容量依賴于網(wǎng)絡節(jié)點的連接情況以及網(wǎng)絡中每一條鏈路的容量的變化情況。因此在評價網(wǎng)絡編碼多播的容量時，我們必須考慮多種網(wǎng)絡拓撲結(jié)構(gòu)以及鏈路的容量。文獻[35]對一編碼多播和IP多播的多播容量性能進行了比較。其隨機生成節(jié)點數(shù)為50的網(wǎng)絡拓撲結(jié)構(gòu)，并隨機選取10個接收節(jié)點。對于網(wǎng)絡鏈路的容量，采用兩種模型：一種是鏈路的容量在【l，10】區(qū)間內(nèi)隨機的選取的非均勻模型（Heterogeneous Model），另一種是鏈路容量為常數(shù)5的均勻模型（Homogeneous Model）。因為多會話IP多播更能有效的利用網(wǎng)絡的資源，所以將網(wǎng)絡編碼多播和多會話IP多播的多播容量進行了比較。從圖中我們可以看到，在均勻和非均勻的兩種鏈路容量模型下，基于網(wǎng)絡編碼的多播通常較多會話IP多播獲得更高的多播容量。此外，網(wǎng)絡編碼多播和多會話IP多播的容量差異隨著網(wǎng)絡節(jié)點的平均度數(shù)的增加而增加。 網(wǎng)絡編碼多播和IP多播容量比較 負載均衡現(xiàn)有的IP多播路由經(jīng)常造成網(wǎng)絡流量的不均衡分布，因此在多播通信中，鏈路流量的負載平衡一直是人們關(guān)注的問題?，F(xiàn)有的多播路由協(xié)議主要可分為基于核心的路由協(xié)議和基于信源的多播路由協(xié)議。基于核心的路由協(xié)議經(jīng)常造成流量過分集中于某一節(jié)點。而基于信源的多播路由協(xié)議也會由于多個多播樹的疊加，造成某一鏈路流量的過載，影響網(wǎng)絡的服務質(zhì)量?；诰W(wǎng)絡編碼的多播[35]利用多條路徑進行信息數(shù)據(jù)的傳輸，可以平衡網(wǎng)絡鏈路的負載。，源節(jié)點S將信息多播到接收節(jié)點。假設網(wǎng)絡編碼多播使用一半的鏈路容量，在這種情形下，路由方式與網(wǎng)絡編碼方式多播速率均為2比特/單位時間。但采用路由方式（如（b）所示）時，2比特的信息是通過5條鏈路來傳輸?shù)?，另?條鏈路空閑。當使用網(wǎng)絡編碼方式（如（c）所示）時，1比特的信息是通過9條鏈路來傳輸?shù)?。因此，通過網(wǎng)絡編碼，負載被分配到了整個網(wǎng)絡中。另一方面，在路由方式中，共有10比特的信息量需要傳輸，而使用網(wǎng)絡編碼時，僅需要傳輸9比特，這就意味著網(wǎng)絡編碼可以節(jié)省10%的帶寬。當網(wǎng)絡編碼多播使用鏈路的全部容量時，不但可以獲得4比特/單位時間的多播速率，而且此時的鏈路資源的利用率達到了最佳。 路由方式和網(wǎng)絡編碼方式的負載比較 減少節(jié)點能量消耗在一些無線Mesh網(wǎng)絡中，節(jié)點是通過有限的電池來提供能量的，因此有效能量利用成為衡量一個無線能量受限網(wǎng)絡性能的重要指標。 通過網(wǎng)絡編碼節(jié)省節(jié)點的能量損耗（a）是一個由8個節(jié)點組成的無線網(wǎng)絡，信源節(jié)點多播信息和到接收節(jié)點和，節(jié)點傳輸范圍有限且僅能與周圍的兩個節(jié)點直接通信。假設一次物理層的傳輸要消耗1個單位的能量。如果在接收節(jié)點和分別丟失了數(shù)據(jù)包和。則傳統(tǒng)的路由方式，我們總共用到了4次物理層廣播單位比特信息需要消耗的總能量為4（比如數(shù)據(jù)包和路徑分別為：t1et2，t2et1）。（b）基于網(wǎng)絡編碼則是節(jié)點和再將其傳輸?shù)街虚g節(jié)點，節(jié)點對和做模2運算后，再將其廣播到節(jié)點和處，這樣兩個接收節(jié)點就可以同時恢復出信源的信息比特和。在采用網(wǎng)絡編碼的組播過程中，我們總共用到了3次物理層廣播。因此采用基于網(wǎng)絡編碼方式的組播，可以有效地降低無線網(wǎng)絡信息傳輸過程中的能量消耗，也降低了傳播的時延。另外，無線多播網(wǎng)絡中，通過跨層的設計可以將網(wǎng)絡編碼與物理層無線廣播傳輸特性相結(jié)合，實現(xiàn)網(wǎng)絡的最小能量多播，最大限度的延長網(wǎng)絡的生存期。另外，還可以通過網(wǎng)絡編碼對相關(guān)信源的數(shù)據(jù)進行壓縮[36]，減少網(wǎng)絡中傳輸?shù)男畔⒘浚瑥亩鴾p少節(jié)點能量消耗，延長網(wǎng)絡的生存周期。通過網(wǎng)絡編碼可以抵抗網(wǎng)絡中的鏈路和節(jié)點的非各態(tài)歷經(jīng)失敗[37]對網(wǎng)絡鏈接的影響，提高網(wǎng)絡鏈接的魯棒性，減少網(wǎng)絡管理的開銷。網(wǎng)絡編碼在信息安全領(lǐng)域的應用產(chǎn)生了一種基于數(shù)據(jù)包的隨機網(wǎng)絡編碼檢測策略，對原數(shù)據(jù)進行的簡單多項式函數(shù)哈希變換，然后把得到的結(jié)果添加到原始數(shù)據(jù)包中。接收節(jié)點通過比較解碼后的數(shù)據(jù)和哈希值就可以判斷數(shù)據(jù)包是否被修改過，這樣就可以防止中間人攻擊，提高數(shù)據(jù)的安全系數(shù)。 本章小節(jié)本章首先介紹了組播通信方式，并分析了組播技術(shù)路由實現(xiàn)的局限性；由此引出了網(wǎng)絡編碼的介紹，并大致討論了網(wǎng)絡編碼在有線網(wǎng)絡和無線網(wǎng)絡的發(fā)展；最后具體介紹了網(wǎng)絡編碼組播的性能優(yōu)點。第四章 無線Mesh網(wǎng)絡COPE編碼方法及改進方法 COPE編碼方法的描述 由于無線鏈路低吞吐量等特性，Katti等提出一種可以提高吞吐量的基于機會的網(wǎng)絡編碼（COPE）。COPE[32]編碼方法要求在IP層和MAC層之間插入一個新的編碼層，用于檢測編碼機會，如果可以編碼，并進行編碼以便在一次傳輸中發(fā)送多個數(shù)據(jù)包。節(jié)點1，2要通過中繼節(jié)點0交換一對數(shù)據(jù)包。傳統(tǒng)路由選擇方法需要進行4次傳輸；而使用COPE網(wǎng)絡編碼，節(jié)點1，2各自發(fā)送數(shù)據(jù)包到節(jié)點0，節(jié)點0收到數(shù)據(jù)包后將兩數(shù)據(jù)包編碼（模2和），然后廣播數(shù)據(jù)包給節(jié)點1，2。節(jié)點1收到數(shù)據(jù)包后，根據(jù)數(shù)據(jù)緩沖池的數(shù)據(jù)包進行解碼，由得到所需的數(shù)據(jù)包。同理，節(jié)點2得到所需數(shù)據(jù)包。而這過程只需要進行3次傳輸，編碼增益為：4/3=。根據(jù)吞吐量公式： （41）式中：表示時間；表示時間內(nèi)發(fā)送的原始數(shù)據(jù)包。可知減少的傳輸?shù)拇螖?shù)用以傳輸其他原始的數(shù)據(jù)包，從而可以提高網(wǎng)絡的吞吐量。吞吐量與網(wǎng)絡編碼增益成正比，故在本章中都將以網(wǎng)絡編碼增益來衡量吞吐量。 傳統(tǒng)路由工作方式和COPE工作方式的簡化模型 COPE編碼所需要的前提技術(shù)在詳細介紹各種技術(shù)之前，先定義本文所需的專業(yè)術(shù)語，如表1所示。術(shù)語解釋原始數(shù)據(jù)表示沒編碼的數(shù)據(jù)包編碼數(shù)據(jù)包多個原始數(shù)據(jù)包相與后形成的數(shù)據(jù)包下一跳節(jié)點集所有相與的原始數(shù)據(jù)包的下一跳節(jié)點集合輸出隊列節(jié)點的一個先進先出的隊列，用于存儲要前傳的數(shù)據(jù)包數(shù)據(jù)包池節(jié)點用于存儲T時間內(nèi)收到數(shù)據(jù)包的緩存區(qū)數(shù)據(jù)包ID32bit的數(shù)據(jù)包的IP源地址和IP序列號表1 本章內(nèi)術(shù)語的解釋 監(jiān)聽機會由于無線網(wǎng)絡的物理層廣播特性，只要將節(jié)點配置了全向天線并設置為混雜接收模式，該節(jié)點就有機會監(jiān)聽到一定范圍內(nèi)傳輸?shù)乃袛?shù)據(jù)包。COPE編碼方法要求網(wǎng)絡中所有的節(jié)點接收其能監(jiān)聽的全部數(shù)據(jù)包，并在一定的時間內(nèi)存儲接收到的數(shù)據(jù)包（默認時間T=）。此外，每一個節(jié)點將其存儲的數(shù)據(jù)包以接收報告廣播給鄰居節(jié)點。當節(jié)點沒有數(shù)據(jù)要傳輸時就將接收報告放在特殊的控制數(shù)據(jù)包中發(fā)送。 編碼機會當一個節(jié)點有多個數(shù)據(jù)包需要傳輸時，可以有多種數(shù)據(jù)包組合方式來進行編碼。網(wǎng)絡編碼中最關(guān)鍵的問題也就是如何選擇數(shù)據(jù)包進行編碼傳輸以達到吞吐量的最大化。也就是說要保證一次傳輸能夠傳輸最多的原始數(shù)據(jù)包并且下一跳節(jié)點集有足夠的信息以能夠正確解碼還原原始數(shù)據(jù)包。，節(jié)點B的輸出隊列有，和四個數(shù)據(jù)包等候傳輸，同時它的鄰居節(jié)點A，C和D之前都各自監(jiān)聽到一些數(shù)據(jù)包。傳統(tǒng)條件下，當MAC允許節(jié)點B傳輸數(shù)據(jù)包時，B節(jié)點依次取出輸出隊列的頭一條數(shù)據(jù)包，和進行傳輸；網(wǎng)絡編碼條件下，假設B節(jié)點知道它的鄰居節(jié)點各自擁有的數(shù)據(jù)包時。當節(jié)點B傳輸時，因為節(jié)點C已經(jīng)存儲數(shù)據(jù)包，所以C節(jié)點采用的解碼方式可以獲得原始數(shù)據(jù)包。但節(jié)點A沒有數(shù)據(jù)包，所以A節(jié)點不能夠解碼得到原始數(shù)據(jù)包。這樣，因為有一個鄰居節(jié)點不能在這次傳輸中獲益，對節(jié)點B而言傳輸并不是一個好的選擇。，因為節(jié)點A和C都能解碼獲得一個所需要的原始數(shù)據(jù)，所以這種編碼方式比較好。然而，如果節(jié)點B選擇傳輸時，鄰居節(jié)點A，C和D都能在這次傳輸中解碼獲得一個所需的原始數(shù)據(jù)包，因此這種編碼方式更好。上面這個例子說明了多個單播流的數(shù)據(jù)包有可能在某個中間節(jié)點編碼?？紤]到這多個單播流的路徑在下一跳就可能各自分散傳輸，因此在下一跳節(jié)點集需要解碼。如果下一跳節(jié)點沒有解碼的話，一些不需要的數(shù)據(jù)包就繼續(xù)前傳從而導致浪費了很多容量。編碼機會可以用如下準則表示：一個節(jié)點要傳輸數(shù)據(jù)包到下一跳節(jié)點，當且僅當每一個下一跳節(jié)點存儲了其余個數(shù)據(jù)包時，該節(jié)點能將這個數(shù)據(jù)包相與進行編碼。如上準則保證了下一跳節(jié)點集能夠正確解碼獲得所需的原始數(shù)據(jù)包，并且當一個節(jié)點有傳輸數(shù)據(jù)包機會時，它都會挑選滿足上述準則的最大的來編碼。兩個問題：如果從整個網(wǎng)絡看，兩跳（或者多跳）可以解碼也完全有可能比不編碼要好，是否有研究人員考慮此類情況？（暫時沒有發(fā)現(xiàn)，因為兩跳或是多跳解碼，這個需要非常多的前提條件，討論起來比較麻煩，我就是在一個很特殊的拓撲結(jié)果討論的兩跳解碼的情況）如果傳輸中出現(xiàn)誤碼，是否是一個完全新的課題：整個網(wǎng)絡的誤碼率大大上升？因為誤碼傳輸了。這個問題牽涉到網(wǎng)絡編碼是否具有實際應用價值（下一章節(jié)介紹的就是網(wǎng)絡編碼和物理層編碼結(jié)合的情況，可以看到在存在誤碼率的情況下，采用網(wǎng)絡編碼+ARQ兩種技術(shù)的效果，其實是不如HARQ的，但是還是要比ARQ的效果好）》這個部分是否作為一個研究結(jié)論，單獨介紹 學習鄰居狀態(tài)一個節(jié)點如何知道它的鄰居擁有哪些數(shù)據(jù)包呢？，每一個節(jié)點都會向他的鄰居節(jié)點報告它所存儲的數(shù)據(jù)包。但是，在網(wǎng)絡發(fā)生嚴重阻塞時，節(jié)點發(fā)給鄰居節(jié)點的接收報告可能丟失，即使網(wǎng)絡阻塞不嚴重，接收報告也可能延遲到達，這都會導致該節(jié)點選擇次優(yōu)的編碼組合。因此，節(jié)點編碼選擇的依據(jù)不能單一的依靠接收報告，還需要估計其鄰居節(jié)點存儲的數(shù)據(jù)包。這里介紹一種用路由算法來估計鄰居節(jié)點存儲的數(shù)據(jù)包的方法。無線Mesh網(wǎng)絡路由協(xié)議可以計算一對節(jié)點之間的投遞率，并且依據(jù)投遞率來區(qū)別這對節(jié)點之間的路徑好壞。例如：利用期望傳輸次數(shù)[38]（Expected Transmission Count，ETX）可以周期性的計算每對節(jié)點之間的投遞率，并令該鏈路的權(quán)重為1/投遞率。各鏈路的權(quán)重值廣播給網(wǎng)絡中的所有節(jié)點，因此鏈路狀態(tài)路由協(xié)議可依據(jù)權(quán)重值來計算最短路徑。COPE編碼在缺少確定性的信息時，也會利用投遞率來估計特定鄰居節(jié)點所包含的數(shù)據(jù)包。有時候，節(jié)點可能因為錯誤的估計導致收到編碼數(shù)據(jù)包而不能正確解碼。這種情況，相關(guān)的原始數(shù)據(jù)包會和其他的一些原始數(shù)據(jù)包相與后重傳。 COPE編碼理論為了將COPE編碼技術(shù)更有效的應用于實際網(wǎng)絡，這節(jié)介紹COPE編碼的一些重要理論。 數(shù)據(jù)包編碼算法COPE編碼方法[32]的一個原則就是從不延遲發(fā)送數(shù)據(jù)包。這也就是說，當無線信道有效時，節(jié)點就會從輸出隊列中取出頭原始數(shù)據(jù)包，并檢查頭原始數(shù)據(jù)包能否與隊列中的其他原始數(shù)據(jù)包進行編碼。如果能，則將這些原始數(shù)據(jù)包相與后廣播到各鄰居節(jié)點。如果沒有編碼機會，節(jié)點就會直接廣播該原始數(shù)據(jù)包而不會等待可匹配的原始數(shù)據(jù)包到來。此外，為了確保下一跳節(jié)點集能夠正確解碼還原所需的原始數(shù)據(jù)包，中繼節(jié)點需要知道其鄰居節(jié)點已經(jīng)存儲了哪些原始數(shù)據(jù)包。如上所述，如果中繼節(jié)點沒有收到鄰居節(jié)點發(fā)來的接收報告，那么在缺乏確定信息的情況下，該節(jié)點就會使用路由協(xié)議來計算下一跳節(jié)點間鏈路的投遞率，并依據(jù)投遞率來估計下一跳節(jié)點存儲某原始數(shù)據(jù)包的可能性，并據(jù)此決定是否進行網(wǎng)絡編碼，以提高下一跳節(jié)點集的正確解碼概率。假設，某中繼節(jié)點一次將個數(shù)據(jù)包進行相與的編碼，并假設第個數(shù)據(jù)包的下一跳接收節(jié)點監(jiān)聽到其他某一個數(shù)據(jù)包的概率為，那么該接收節(jié)點能正確解碼的概率等于這節(jié)點能監(jiān)聽參與編碼的其他個原始數(shù)據(jù)包的概率： 現(xiàn)在考慮編碼的中間過程，怎樣搜索可編碼的數(shù)據(jù)包的問題。假設現(xiàn)在已經(jīng)將個原始數(shù)據(jù)包編碼在一起，并考慮編碼相與第個原始數(shù)據(jù)包。這時編碼算法就會判斷這個原始數(shù)據(jù)包的下一跳節(jié)點集可解碼的概率是否滿足大于一個門限值(一般默認G=)。如果滿足上述的門限值，就意味著下一跳節(jié)點集可以正確解碼的概率至少是G，從而進行這樣的網(wǎng)絡編碼就可能有較大的網(wǎng)絡增益。表2 編碼程序當一個節(jié)點的MAC顯示有發(fā)送數(shù)據(jù)包的機會時，該節(jié)點就會執(zhí)行如表2所示的編碼程序。表2描述的這個貪婪算法的計算復雜度與鄰居節(jié)點的數(shù)目成線性比例。 數(shù)據(jù)包解碼數(shù)據(jù)包解碼比較簡單。每一個節(jié)點維護一個數(shù)據(jù)包池，用于存儲一段時間T內(nèi)該節(jié)點發(fā)送或接收到的數(shù)據(jù)包。當節(jié)點接收到一個由個原始數(shù)據(jù)包編碼而成的數(shù)據(jù)