摘 要： 通過對網絡編碼理論和現有P2P文件共享系統的深入研究，設計了一種基于線性網絡編碼的P2P文件共享系統。該系統的優點是解決了現有P2P文件共享系統中存在的不能充分利用網絡資源、“種子”節點突然退出造成文件下載不完等問題。實驗結果表明，該系統克服了現有系統中存在的問題，同時也提高了整個系統的吞吐量并增強了系統的穩定性。
關鍵詞： 對等網絡；網絡編碼；比特洪流
對等網絡P2P（Peer-to-Peer Network）是分布式系統與計算機結合的產物，是采用對等模式工作的計算機網絡，它開發了網絡中每個節點的網絡能力?；赑2P的文件共享系統擺脫了原有基于客戶/服務器（C/S）體系結構集中式訪問模式的束縛，通過匯集網絡邊緣可用資源提供服務，現已成為Internet上下載大文件的主流模型。但是現有的P2P文件共享系統也存在一些問題：
?。?）如果“種子”節點突然離開P2P網絡，可能造成網絡中其余計算機不能完整地下載源文件。
?。?）一個好的數據塊調度算法時間復雜度高，執行效率低，這將影響到客戶端的下載時間。
?。?）在現有的P2P通信網絡中，信息的傳輸都是從源節點出發，經過中間節點的存儲轉發到目的節點。在這個過程中，中間節點起著中繼作用，其并未對收到的信息做任何處理，這種傳統的通信模式很難達到網絡的最大吞吐量。
本文在對網絡編碼和現有的P2P文件共享系統工作原理研究的基礎上，提出了一種基于線性網絡編碼的文件共享系統實現方案。利用網絡編碼的優勢，來解決現有P2P文件共享系統中存在的問題，完善和增強系統的性能。
1.3 線性網絡編譯碼器實現算法說明及性能分析
在實際工作中，P2P網絡的拓撲結構經常會隨著節點的加入或退出發生變化，所以網絡編碼采用隨機線性網絡編碼[4]，即網絡節點對編碼系數是隨機選取的，并且對輸入數據包進行線性操作，其具有良好的拓撲適應性。但從網絡編碼原理分析可知，網絡編碼算法時間復雜度較高，因此，本文在編譯碼器的實現程序中采取了一些優化策略，以盡可能降低計算量，提高編譯碼的速度。策略如下：
?。?）有限域運算。編譯碼過程中需要有大量的有限域乘除運算，本程序采用離散對數方法來減少運算量。利用有限域中特殊元素生成元，將有限域中任何非零元素唯一的表示為生成元的指數形式，因此有限域元素相乘除的運算都可轉化為指數運算。
?。?）對源文件采用“代”（Generation）劃分[3]。P2P網絡中等待下載的文件通常都在百兆以上，數量龐大的源文件分組使相應的編碼矩陣和解碼矩陣維數很大，加劇了編譯碼運算過程中的運算量。本文對源文件采用“代”劃分的方法，以達到有效降低編譯碼矩陣維數、簡化運算量的目的。
（3）稀疏矩陣。網絡編碼的編碼系數是隨機選擇的，隨機選擇的編碼系數是均勻分布的，編碼系數中零的個數很少，所以程序的編碼矩陣選擇使用稀疏矩陣[5]，這樣可以有效降低編譯碼計算量。
基于隨機線性網絡編碼的原理和上述算法優化策略，本文采用C++在Linux環境下實現了傳統的線性網絡編碼編譯碼器和隨機線性網絡編碼編譯碼器（采用上述優化策略）。用100 MB的文件在兩種編譯碼器上分別測試了分組大小從64 KB到2 MB的編譯碼運行速率。通過分析圖2的編譯碼器性能圖可以得到，經過優化策略的編譯碼器性能明顯優于傳統網絡編碼的編譯碼器。實驗結果證明，將上述策略應用于網絡編碼的編譯碼器是有效的，所以選擇合適大小的分組可以充分發揮編譯碼器的性能。
2 線性網絡編碼在P2P文件共享系統中的應用
當前，BitTorrent是使用最為廣泛的P2P文件共享系統之一[6]。通過對BitTorrent系統工作原理、線性網絡編碼理論的研究和分析，將本文提出的線性網絡編譯碼器應用到BitTorrent客戶端系統中，實現基于線性網絡編碼的P2P文件共享系統。圖3是基于線性網絡編碼的BitTorrent系統框架圖。該系統主要由5個模塊組成：（1）傳輸機制模塊：提供Socket的通信，收發消息。（2）編碼器模塊：對數據進行編碼。如果當前的節點是種子節點，就對原始數據進行編碼；如果是非種子節點，就對當前收到的同一“代”的編碼過的數據進行再次編碼。（3）線性檢測模塊：對收到數據包的編碼向量進行線性相關性的檢測。如果線性無關，將該數據包存放在臨時文件中；如果線性相關，將該數據包拋棄；如果臨時文件存放的線性無關的數據包達到一定數量，就可以進行譯碼。（4）譯碼器模塊：對收到編碼過的數據包進行譯碼，恢復源文件。（5）成員管理模塊：讓當前客戶端能夠與系統中一定數目的其他客戶端建立連接，并在運行過程中實現對與其連接的其他客戶端進行淘汰和更新。
將基于線性網絡編碼的BitTorrent文件共享系統運行在實驗室實際的網絡環境中（12臺PC）。在實驗過程中，將種子節點中途退出。實驗最終結果表明，其余客戶端都可以正確地下載完源文件。通過對實驗結果進一步分析得到一些結論：（1）該系統可以解決P2P網絡中“種子”突然退出可能造成的文件下載不完的問題；（2）基于網絡編碼的BitTorrent并沒有比普通的BitTorrent性能快很多，這是由于編碼和譯碼時間復雜度比較高，從而影響系統的整體性能。
P2P文件共享系統已經成為了Internet的主要應用之一。本文實現了一種基于線性網絡編碼的P2P文件共享系統。該系統可以提高網絡的吞吐量、增強系統的可靠性并提高下載成功率。由于網絡編碼存在著計算復雜度高的問題，雖然在編譯碼器的實現方法中結合了一些有效策略，可以降低部分計算量，但是編譯碼器的計算量開銷依然很大，因此研究降低網絡編碼的復雜性，實現最小代價的網絡編碼，具有重要的理論意義和使用應用價值。
參考文獻
[1] AHLSWEDE R， CAI N， LI S Y R， et al. Network information flow[J]. IEEE Transactions on Information Theory， 2000， 46（4）：1204-1216.
[2] LI S Y R， YEUNG R W， Ning Cai. Linear network coding[J]. IEEE Transactions on Information Theory， 2003，49（2）：371-381.
[3] CHOU P A， WU Y N， JAIN K. Practical network coding[C]. The 41st Allerton Conference on Communication， Control and Computing Monticello， Kluwer，2003.
[4] HO T， MEDARD M， KOETTER R， et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory， 2006，52（10）：4413-4430.
[5] MA G， XU Y， LIN M， et al. A content distribution system based on sparse linear network coding[C]. Proceedings of the 3rd Workshop on Network Coding， Theory， and Applications （NETCOD 2007）， 2007.
[6] GKANTSIDIS C， RODRIGOUE Z. Network coding for large scale content distribution[C]. INFOCOM 2005， 2005（4）：2235-2245.