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

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

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

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

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

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

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

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

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

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

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

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

作者簡(jiǎn)介：

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

參 考 文 獻(xiàn)

[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] 陶少國(guó)，黃佳慶，楊宗凱， “網(wǎng)絡(luò)編碼研究綜述”.通信技術(shù).2010.

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

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