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