一種提高網(wǎng)絡(luò)編碼在P2P應(yīng)用中效率算法

【摘要】 傳統(tǒng)P2P網(wǎng)絡(luò)中，每個中間節(jié)點都只是存儲轉(zhuǎn)發(fā)，不會對接收到的文件塊做任何處理。在P2P中引入網(wǎng)絡(luò)編號后[3-4]，在入度大于等于二的節(jié)點上進行網(wǎng)絡(luò)編碼，可以提高文件的傳輸效率，而且還能提高網(wǎng)絡(luò)的魯棒性。改進后的網(wǎng)絡(luò)編碼，不是對每個入度大于等于二的中間節(jié)點都進行網(wǎng)絡(luò)編碼，而是只對關(guān)鍵路徑的入度大于等于二的節(jié)點進行編碼，這樣就會節(jié)省了網(wǎng)絡(luò)編碼和解碼消耗的時間，提高了傳輸效率。

【關(guān)鍵詞】 網(wǎng)絡(luò)編碼 P2P網(wǎng)絡(luò) BT系統(tǒng)

一、傳統(tǒng)的P2P方式

在P2P網(wǎng)絡(luò)中，每個節(jié)點都是對等了，既充當服務(wù)器，又充當客戶端。與C/S模式不同。P2P中最流行的是BT系統(tǒng)，它可以把每一個加入進來下載資源的主機變成服務(wù)器。BT系統(tǒng)中有跟蹤服務(wù)器，種子節(jié)點和下載節(jié)點。跟蹤服務(wù)器記錄了每個加入進來的主機的狀態(tài)。假如主機A上有個文件file，主機B、C、D、E分別想下載主機A上的file文件。主機B第一個加入進來下載主機A上的文件，主機B向主機A上的跟蹤服務(wù)器注冊，得到file在主機A上的信息塊，取得主機A的節(jié)點信息，此時主機B與主機A的節(jié)點信息建立了連接，告訴主機A上的跟蹤服務(wù)器要下載的文件信息，然后從種子節(jié)點開始下載，此時如果沒有其他的主機加入進來，這就是典型的C/S模式。當主機C加入進來時，主機C向A上的跟蹤服務(wù)器注冊，由于主機A此時還和主機B連著，這時主機A的跟蹤服務(wù)器會幫助主機B和主機C建立連接，主機C可以從主機A，B上獲取資源，同時也把自己已有的資源向主機B提供。這時主機B和主機C分別既當下載資源的客戶機，也當提供資源給別的主機下載的服務(wù)器。隨著主機D，E的加入進來，這樣就構(gòu)成的對等的局域網(wǎng)絡(luò)。假如主機A的file分成了4個文件塊，主機B，C，D，E分別只得到了文件塊file1，file2，file3，file4，此時主機A由于網(wǎng)絡(luò)故障退出了這個網(wǎng)絡(luò)，要是在C/S模式下，這樣主機B，C，D，E都不能得到原來的文件file。但是在P2P模式下，他們分別可以為其他主機提供自己已有的資源，這樣即使沒有主機A，他們也能從其他主機上得到其余文件塊，最終復(fù)原想要下載的file文件。所以P2P還有很好的魯棒性。

二、引入網(wǎng)絡(luò)編碼后的P2P方式

在傳統(tǒng)的P2P模式下，每個節(jié)點都只是存儲轉(zhuǎn)發(fā)，不會對文件進行任何操作，人們都認為在中間節(jié)點上對文件進行操作完全沒有必要，起不到任何有益作用，然而在2000年，R Ahlswede等人提出了網(wǎng)絡(luò)編碼這一個概念[1]。在網(wǎng)絡(luò)通信中，網(wǎng)絡(luò)中的中間節(jié)點會對要存儲轉(zhuǎn)發(fā)的信息進行一定的線性或者非線性的編碼操作[5]，然后轉(zhuǎn)發(fā)給下一個節(jié)點，這樣會使網(wǎng)絡(luò)中的通信容量達到最大。

如圖1（a）A為信源節(jié)點，E，F(xiàn)為信宿節(jié)點，假設(shè)每條鏈路的容量為1比特/單位時間。A分別向中間節(jié)點B，C發(fā)送兩個比特的信息a，b。在一個單位時間內(nèi)，B接收到一個信息比特a，C接收到一個信息比特b。在下一個單位時間內(nèi)，E，F(xiàn)分別可以得到a，b信息中一個，D點可以同時接收到a，b信息。如果不引入網(wǎng)絡(luò)編碼，而是傳統(tǒng)的存儲轉(zhuǎn)發(fā)，由于每條鏈路容量為1比特/單位時間，G點要接收到信息a，b需要兩個單位時間。但是如果在D點引入網(wǎng)絡(luò)編碼，如圖1（b），信息a，b會通過網(wǎng)絡(luò)編碼，組合成一個信息a+b。這樣，只需一個單位時間就可以把D點的信息傳到G節(jié)點上。這點在現(xiàn)實生活中很重要。S.Y.R. Li進一步證明了在單信源多信宿情況下，應(yīng)用線性網(wǎng)絡(luò)編碼理論[6]，一定能夠達到該上界[2]。G點得到信息a+b。在下一個單位時間，G點把信息分別傳到信宿節(jié)點E，F(xiàn)上。E，F(xiàn)通過解碼，在E上得到信息b，在F上得到信息a。這樣在信宿節(jié)點E，F(xiàn)就分別都獲取到a，b兩比特信息。

數(shù)學(xué)模型，服務(wù)器有一個文件D，分成n份，每個數(shù)據(jù)包為M1，M2，M3，…，Mn，則原數(shù)據(jù)可以表示為D=（gi） （Mi）（其中g(shù)i為Mi數(shù)據(jù)片段隨機產(chǎn)生的編碼系數(shù)），在網(wǎng)絡(luò)中傳輸?shù)臑閿?shù)據(jù)D和編碼系數(shù)gi。數(shù)據(jù)從發(fā)送端到接收端經(jīng)過的每個節(jié)點通過迭代進行編碼。假設(shè)一個節(jié)點收到的數(shù)據(jù)包為（g1，D1），（g2，D2），…，（gj，Dj），（gm，Dm），（gj，Dj）表示第j個數(shù)據(jù)包編碼系數(shù)向量和信息向量，這個節(jié)點的隨機產(chǎn)生的編碼系數(shù)為V1，V2，…， Vm得到的信息向量D=（Vi） （Di），從而得到新的數(shù)據(jù)包（g，Di）， gi=Vjgij。每經(jīng)過一個節(jié)點進行一次編碼迭代，最后在接收端進行譯碼，通過接收到的系數(shù)向量恢復(fù)出原來的信息，接收端的數(shù)據(jù)包至少等于發(fā)送端的數(shù)據(jù)包。

三、改進網(wǎng)絡(luò)編碼后的P2P方式

在網(wǎng)絡(luò)中，并不是對每個節(jié)點都需要進行網(wǎng)絡(luò)編碼的。只需對入度大于等于2的節(jié)點需要進行網(wǎng)絡(luò)編碼。如圖2（a）是傳統(tǒng)的網(wǎng)絡(luò)編碼，在節(jié)點A，B，C的入度均為1，無需進行網(wǎng)絡(luò)編碼，節(jié)點D，E的入度為2，需要進行網(wǎng)絡(luò)編碼。但是進行網(wǎng)絡(luò)編碼和解碼時，也會消耗一定的時間。

如圖2（b）是經(jīng)過改進后的網(wǎng)絡(luò)編碼，在D節(jié)點無需進行網(wǎng)絡(luò)編碼，這樣就節(jié)省了在D節(jié)點的編碼時間和在F節(jié)點的解碼時間。

作者簡介：

刊物郵寄地址：北京市豐臺區(qū)蓮花池東路106號匯融大廈建行開發(fā)中心 張雷 15590264889

參 考 文 獻

[1] R. Ahlswede， N. Cai， S.-Y. R. Li and R. W. Yeung， "Network information flow"， IEEE Transactions on Information Theory，vol.IT-46，NO.4， pp. 1204-1216， July.2000.

[2] S.Y.R. Li， R. W. Yueng， and N. Cai， "Linear network coding"， IEEE-IT， vol.IT-49， no.2，pp.371-381， Feb.2003.

[3] Han Liu，Xiaodong Tu，Jun Xie， "Network Coding For P2P Live Media Streaming". IFIP International Conference Network and Parallel ComPuting.2008.

[4] 陶少國，黃佳慶，楊宗凱， “網(wǎng)絡(luò)編碼研究綜述”.通信技術(shù).2010.

[5] 張璇，張博，慕建軍， “線性網(wǎng)絡(luò)編碼及其在P2P文件共享系統(tǒng)中的應(yīng)用”， 2008年西安電子科技大學(xué)研究生學(xué)術(shù)年會.

[6] 周偉偉，線性網(wǎng)絡(luò)編碼研究.通信技術(shù).2008.