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

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

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

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

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