摘  要： 通過對網(wǎng)絡(luò)編碼理論和現(xiàn)有P2P文件共享系統(tǒng)的深入研究，設(shè)計了一種基于線性網(wǎng)絡(luò)編碼的P2P文件共享系統(tǒng)。該系統(tǒng)的優(yōu)點(diǎn)是解決了現(xiàn)有P2P文件共享系統(tǒng)中存在的不能充分利用網(wǎng)絡(luò)資源、“種子”節(jié)點(diǎn)突然退出造成文件下載不完等問題。實(shí)驗結(jié)果表明，該系統(tǒng)克服了現(xiàn)有系統(tǒng)中存在的問題，同時也提高了整個系統(tǒng)的吞吐量并增強(qiáng)了系統(tǒng)的穩(wěn)定性。
關(guān)鍵詞： 對等網(wǎng)絡(luò)；網(wǎng)絡(luò)編碼；比特洪流

　對等網(wǎng)絡(luò)P2P（Peer-to-Peer Network）是分布式系統(tǒng)與計算機(jī)結(jié)合的產(chǎn)物，是采用對等模式工作的計算機(jī)網(wǎng)絡(luò)，它開發(fā)了網(wǎng)絡(luò)中每個節(jié)點(diǎn)的網(wǎng)絡(luò)能力。基于P2P的文件共享系統(tǒng)擺脫了原有基于客戶/服務(wù)器（C/S）體系結(jié)構(gòu)集中式訪問模式的束縛，通過匯集網(wǎng)絡(luò)邊緣可用資源提供服務(wù)，現(xiàn)已成為Internet上下載大文件的主流模型。但是現(xiàn)有的P2P文件共享系統(tǒng)也存在一些問題：
　（1）如果“種子”節(jié)點(diǎn)突然離開P2P網(wǎng)絡(luò)，可能造成網(wǎng)絡(luò)中其余計算機(jī)不能完整地下載源文件。
　（2）一個好的數(shù)據(jù)塊調(diào)度算法時間復(fù)雜度高，執(zhí)行效率低，這將影響到客戶端的下載時間。
　（3）在現(xiàn)有的P2P通信網(wǎng)絡(luò)中，信息的傳輸都是從源節(jié)點(diǎn)出發(fā)，經(jīng)過中間節(jié)點(diǎn)的存儲轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。在這個過程中，中間節(jié)點(diǎn)起著中繼作用，其并未對收到的信息做任何處理，這種傳統(tǒng)的通信模式很難達(dá)到網(wǎng)絡(luò)的最大吞吐量。
　本文在對網(wǎng)絡(luò)編碼和現(xiàn)有的P2P文件共享系統(tǒng)工作原理研究的基礎(chǔ)上，提出了一種基于線性網(wǎng)絡(luò)編碼的文件共享系統(tǒng)實(shí)現(xiàn)方案。利用網(wǎng)絡(luò)編碼的優(yōu)勢，來解決現(xiàn)有P2P文件共享系統(tǒng)中存在的問題，完善和增強(qiáng)系統(tǒng)的性能。

1.3 線性網(wǎng)絡(luò)編譯碼器實(shí)現(xiàn)算法說明及性能分析
　在實(shí)際工作中，P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)經(jīng)常會隨著節(jié)點(diǎn)的加入或退出發(fā)生變化，所以網(wǎng)絡(luò)編碼采用隨機(jī)線性網(wǎng)絡(luò)編碼[4]，即網(wǎng)絡(luò)節(jié)點(diǎn)對編碼系數(shù)是隨機(jī)選取的，并且對輸入數(shù)據(jù)包進(jìn)行線性操作，其具有良好的拓?fù)溥m應(yīng)性。但從網(wǎng)絡(luò)編碼原理分析可知，網(wǎng)絡(luò)編碼算法時間復(fù)雜度較高，因此，本文在編譯碼器的實(shí)現(xiàn)程序中采取了一些優(yōu)化策略，以盡可能降低計算量，提高編譯碼的速度。策略如下：
　（1）有限域運(yùn)算。編譯碼過程中需要有大量的有限域乘除運(yùn)算，本程序采用離散對數(shù)方法來減少運(yùn)算量。利用有限域中特殊元素生成元，將有限域中任何非零元素唯一的表示為生成元的指數(shù)形式，因此有限域元素相乘除的運(yùn)算都可轉(zhuǎn)化為指數(shù)運(yùn)算。
　（2）對源文件采用“代”（Generation）劃分[3]。P2P網(wǎng)絡(luò)中等待下載的文件通常都在百兆以上，數(shù)量龐大的源文件分組使相應(yīng)的編碼矩陣和解碼矩陣維數(shù)很大，加劇了編譯碼運(yùn)算過程中的運(yùn)算量。本文對源文件采用“代”劃分的方法，以達(dá)到有效降低編譯碼矩陣維數(shù)、簡化運(yùn)算量的目的。
　（3）稀疏矩陣。網(wǎng)絡(luò)編碼的編碼系數(shù)是隨機(jī)選擇的，隨機(jī)選擇的編碼系數(shù)是均勻分布的，編碼系數(shù)中零的個數(shù)很少，所以程序的編碼矩陣選擇使用稀疏矩陣[5]，這樣可以有效降低編譯碼計算量。
　基于隨機(jī)線性網(wǎng)絡(luò)編碼的原理和上述算法優(yōu)化策略，本文采用C++在Linux環(huán)境下實(shí)現(xiàn)了傳統(tǒng)的線性網(wǎng)絡(luò)編碼編譯碼器和隨機(jī)線性網(wǎng)絡(luò)編碼編譯碼器（采用上述優(yōu)化策略）。用100 MB的文件在兩種編譯碼器上分別測試了分組大小從64 KB到2 MB的編譯碼運(yùn)行速率。通過分析圖2的編譯碼器性能圖可以得到，經(jīng)過優(yōu)化策略的編譯碼器性能明顯優(yōu)于傳統(tǒng)網(wǎng)絡(luò)編碼的編譯碼器。實(shí)驗結(jié)果證明，將上述策略應(yīng)用于網(wǎng)絡(luò)編碼的編譯碼器是有效的，所以選擇合適大小的分組可以充分發(fā)揮編譯碼器的性能。

2 線性網(wǎng)絡(luò)編碼在P2P文件共享系統(tǒng)中的應(yīng)用
　當(dāng)前，BitTorrent是使用最為廣泛的P2P文件共享系統(tǒng)之一[6]。通過對BitTorrent系統(tǒng)工作原理、線性網(wǎng)絡(luò)編碼理論的研究和分析，將本文提出的線性網(wǎng)絡(luò)編譯碼器應(yīng)用到BitTorrent客戶端系統(tǒng)中，實(shí)現(xiàn)基于線性網(wǎng)絡(luò)編碼的P2P文件共享系統(tǒng)。圖3是基于線性網(wǎng)絡(luò)編碼的BitTorrent系統(tǒng)框架圖。該系統(tǒng)主要由5個模塊組成：（1）傳輸機(jī)制模塊：提供Socket的通信，收發(fā)消息。（2）編碼器模塊：對數(shù)據(jù)進(jìn)行編碼。如果當(dāng)前的節(jié)點(diǎn)是種子節(jié)點(diǎn)，就對原始數(shù)據(jù)進(jìn)行編碼；如果是非種子節(jié)點(diǎn)，就對當(dāng)前收到的同一“代”的編碼過的數(shù)據(jù)進(jìn)行再次編碼。（3）線性檢測模塊：對收到數(shù)據(jù)包的編碼向量進(jìn)行線性相關(guān)性的檢測。如果線性無關(guān)，將該數(shù)據(jù)包存放在臨時文件中；如果線性相關(guān)，將該數(shù)據(jù)包拋棄；如果臨時文件存放的線性無關(guān)的數(shù)據(jù)包達(dá)到一定數(shù)量，就可以進(jìn)行譯碼。（4）譯碼器模塊：對收到編碼過的數(shù)據(jù)包進(jìn)行譯碼，恢復(fù)源文件。（5）成員管理模塊：讓當(dāng)前客戶端能夠與系統(tǒng)中一定數(shù)目的其他客戶端建立連接，并在運(yùn)行過程中實(shí)現(xiàn)對與其連接的其他客戶端進(jìn)行淘汰和更新。

　將基于線性網(wǎng)絡(luò)編碼的BitTorrent文件共享系統(tǒng)運(yùn)行在實(shí)驗室實(shí)際的網(wǎng)絡(luò)環(huán)境中（12臺PC）。在實(shí)驗過程中，將種子節(jié)點(diǎn)中途退出。實(shí)驗最終結(jié)果表明，其余客戶端都可以正確地下載完源文件。通過對實(shí)驗結(jié)果進(jìn)一步分析得到一些結(jié)論：（1）該系統(tǒng)可以解決P2P網(wǎng)絡(luò)中“種子”突然退出可能造成的文件下載不完的問題；（2）基于網(wǎng)絡(luò)編碼的BitTorrent并沒有比普通的BitTorrent性能快很多，這是由于編碼和譯碼時間復(fù)雜度比較高，從而影響系統(tǒng)的整體性能。
　P2P文件共享系統(tǒng)已經(jīng)成為了Internet的主要應(yīng)用之一。本文實(shí)現(xiàn)了一種基于線性網(wǎng)絡(luò)編碼的P2P文件共享系統(tǒng)。該系統(tǒng)可以提高網(wǎng)絡(luò)的吞吐量、增強(qiáng)系統(tǒng)的可靠性并提高下載成功率。由于網(wǎng)絡(luò)編碼存在著計算復(fù)雜度高的問題，雖然在編譯碼器的實(shí)現(xiàn)方法中結(jié)合了一些有效策略，可以降低部分計算量，但是編譯碼器的計算量開銷依然很大，因此研究降低網(wǎng)絡(luò)編碼的復(fù)雜性，實(shí)現(xiàn)最小代價的網(wǎng)絡(luò)編碼，具有重要的理論意義和使用應(yīng)用價值。
參考文獻(xiàn)
[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.