摘 要： 通過對網絡編碼理論和現有P2P文件共享系統(tǒng)的深入研究,，設計了一種基于線性網絡編碼的P2P文件共享系統(tǒng),。該系統(tǒng)的優(yōu)點是解決了現有P2P文件共享系統(tǒng)中存在的不能充分利用網絡資源、“種子”節(jié)點突然退出造成文件下載不完等問題,。實驗結果表明,，該系統(tǒng)克服了現有系統(tǒng)中存在的問題，同時也提高了整個系統(tǒng)的吞吐量并增強了系統(tǒng)的穩(wěn)定性,。
關鍵詞： 對等網絡,；網絡編碼；比特洪流
對等網絡P2P（Peer-to-Peer Network）是分布式系統(tǒng)與計算機結合的產物,，是采用對等模式工作的計算機網絡,，它開發(fā)了網絡中每個節(jié)點的網絡能力?；赑2P的文件共享系統(tǒng)擺脫了原有基于客戶/服務器（C/S）體系結構集中式訪問模式的束縛，通過匯集網絡邊緣可用資源提供服務,，現已成為Internet上下載大文件的主流模型,。但是現有的P2P文件共享系統(tǒng)也存在一些問題：
（1）如果“種子”節(jié)點突然離開P2P網絡,，可能造成網絡中其余計算機不能完整地下載源文件,。
（2）一個好的數據塊調度算法時間復雜度高,，執(zhí)行效率低,，這將影響到客戶端的下載時間。
?。?）在現有的P2P通信網絡中,，信息的傳輸都是從源節(jié)點出發(fā)，經過中間節(jié)點的存儲轉發(fā)到目的節(jié)點,。在這個過程中,，中間節(jié)點起著中繼作用，其并未對收到的信息做任何處理,，這種傳統(tǒng)的通信模式很難達到網絡的最大吞吐量,。
本文在對網絡編碼和現有的P2P文件共享系統(tǒng)工作原理研究的基礎上，提出了一種基于線性網絡編碼的文件共享系統(tǒng)實現方案,。利用網絡編碼的優(yōu)勢,，來解決現有P2P文件共享系統(tǒng)中存在的問題，完善和增強系統(tǒng)的性能,。
1.3 線性網絡編譯碼器實現算法說明及性能分析
在實際工作中,，P2P網絡的拓撲結構經常會隨著節(jié)點的加入或退出發(fā)生變化,，所以網絡編碼采用隨機線性網絡編碼[4]，即網絡節(jié)點對編碼系數是隨機選取的,，并且對輸入數據包進行線性操作,，其具有良好的拓撲適應性。但從網絡編碼原理分析可知,，網絡編碼算法時間復雜度較高,，因此，本文在編譯碼器的實現程序中采取了一些優(yōu)化策略,，以盡可能降低計算量,，提高編譯碼的速度。策略如下：
?。?）有限域運算,。編譯碼過程中需要有大量的有限域乘除運算，本程序采用離散對數方法來減少運算量,。利用有限域中特殊元素生成元,，將有限域中任何非零元素唯一的表示為生成元的指數形式，因此有限域元素相乘除的運算都可轉化為指數運算,。
?。?）對源文件采用“代”（Generation）劃分[3]。P2P網絡中等待下載的文件通常都在百兆以上,，數量龐大的源文件分組使相應的編碼矩陣和解碼矩陣維數很大,，加劇了編譯碼運算過程中的運算量。本文對源文件采用“代”劃分的方法,，以達到有效降低編譯碼矩陣維數,、簡化運算量的目的。
?。?）稀疏矩陣,。網絡編碼的編碼系數是隨機選擇的，隨機選擇的編碼系數是均勻分布的,，編碼系數中零的個數很少,，所以程序的編碼矩陣選擇使用稀疏矩陣[5]，這樣可以有效降低編譯碼計算量,。
基于隨機線性網絡編碼的原理和上述算法優(yōu)化策略,，本文采用C++在Linux環(huán)境下實現了傳統(tǒng)的線性網絡編碼編譯碼器和隨機線性網絡編碼編譯碼器（采用上述優(yōu)化策略）。用100 MB的文件在兩種編譯碼器上分別測試了分組大小從64 KB到2 MB的編譯碼運行速率,。通過分析圖2的編譯碼器性能圖可以得到,，經過優(yōu)化策略的編譯碼器性能明顯優(yōu)于傳統(tǒng)網絡編碼的編譯碼器。實驗結果證明,，將上述策略應用于網絡編碼的編譯碼器是有效的,，所以選擇合適大小的分組可以充分發(fā)揮編譯碼器的性能,。
2 線性網絡編碼在P2P文件共享系統(tǒng)中的應用
當前，BitTorrent是使用最為廣泛的P2P文件共享系統(tǒng)之一[6],。通過對BitTorrent系統(tǒng)工作原理,、線性網絡編碼理論的研究和分析，將本文提出的線性網絡編譯碼器應用到BitTorrent客戶端系統(tǒng)中,，實現基于線性網絡編碼的P2P文件共享系統(tǒng),。圖3是基于線性網絡編碼的BitTorrent系統(tǒng)框架圖。該系統(tǒng)主要由5個模塊組成：（1）傳輸機制模塊：提供Socket的通信,，收發(fā)消息,。（2）編碼器模塊：對數據進行編碼。如果當前的節(jié)點是種子節(jié)點,，就對原始數據進行編碼,；如果是非種子節(jié)點，就對當前收到的同一“代”的編碼過的數據進行再次編碼,。（3）線性檢測模塊：對收到數據包的編碼向量進行線性相關性的檢測,。如果線性無關，將該數據包存放在臨時文件中,；如果線性相關,，將該數據包拋棄；如果臨時文件存放的線性無關的數據包達到一定數量,，就可以進行譯碼。（4）譯碼器模塊：對收到編碼過的數據包進行譯碼,，恢復源文件,。（5）成員管理模塊：讓當前客戶端能夠與系統(tǒng)中一定數目的其他客戶端建立連接，并在運行過程中實現對與其連接的其他客戶端進行淘汰和更新,。
將基于線性網絡編碼的BitTorrent文件共享系統(tǒng)運行在實驗室實際的網絡環(huán)境中（12臺PC）,。在實驗過程中，將種子節(jié)點中途退出,。實驗最終結果表明,，其余客戶端都可以正確地下載完源文件。通過對實驗結果進一步分析得到一些結論：（1）該系統(tǒng)可以解決P2P網絡中“種子”突然退出可能造成的文件下載不完的問題,；（2）基于網絡編碼的BitTorrent并沒有比普通的BitTorrent性能快很多,，這是由于編碼和譯碼時間復雜度比較高，從而影響系統(tǒng)的整體性能,。
P2P文件共享系統(tǒng)已經成為了Internet的主要應用之一,。本文實現了一種基于線性網絡編碼的P2P文件共享系統(tǒng)。該系統(tǒng)可以提高網絡的吞吐量,、增強系統(tǒng)的可靠性并提高下載成功率,。由于網絡編碼存在著計算復雜度高的問題,，雖然在編譯碼器的實現方法中結合了一些有效策略，可以降低部分計算量,，但是編譯碼器的計算量開銷依然很大,，因此研究降低網絡編碼的復雜性，實現最小代價的網絡編碼,，具有重要的理論意義和使用應用價值,。
參考文獻
[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.