線性網(wǎng)絡(luò)編碼導(dǎo)出擴展軟件學(xué)報

《線性網(wǎng)絡(luò)編碼導(dǎo)出擴展軟件學(xué)報》由會員分享，可在線閱讀，更多相關(guān)《線性網(wǎng)絡(luò)編碼導(dǎo)出擴展軟件學(xué)報（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、- 不同組播率下線性網(wǎng)絡(luò)編碼的導(dǎo)出與擴展*Supported by the National Natural Science Foundation of China under Grant Nos. 60673164, 60873265 (國家自然科學(xué)基金), Provincial Natural Science Foundation of Hunan under Grant No. 06JJ20031(**省自然科學(xué)基金). 作者簡介：蒲保興(1965-),男,****人,博士研究生,副教授,主要研究領(lǐng)域為網(wǎng)絡(luò)編碼,進化計算;楊路明(1947-),男,****人,博士生導(dǎo)師,教授,主要

2、研究領(lǐng)域為數(shù)據(jù)庫信息系統(tǒng);王偉平(1969-),女, ****人,博士,教授,研究方向為網(wǎng)絡(luò)信息平安,網(wǎng)絡(luò)編碼. 蒲保興1,2+,路明1,王偉平1 1(中南大學(xué) 信息科學(xué)與工程學(xué)院,,410083) 2(學(xué)院 信息工程系, ,422001) Generation and E*tension of Linear Network Coding at Different Multicast Rate PU Bao-*ing1,2+,YANG Lu-Ming1,WANG Wei-Ping1 1 (School of Information Science and Engineering

3、, Central South University, Changsha 410083, China) 2(Department of Information Engineering, Shaoyang College, Shaoyang 422001,Hunan, China〕 + Corresponding author: Phn: +86-0739-5432505, :pubook.. Received 2021-10-11; Accepted 2021-00-00 Abstract:Aiming at single-source multicast network,by stu

4、dying the intrinsic mechanism of linear network coding, this paper proposes a concept of generation and e*tension between two coding schemes at different multicast rates. We find out that a coding scheme at lower multicast rate is a generation of one at higher multicast rate, and a coding scheme at

5、higher multicast rate is an e*tension of one at lower multicast rate. Furthermore, we find out a determinate relationship between channels’ global encoding vectors under two generation-e*tension coding schemes. Besides, by bining with random linear network coding, several important properties are de

6、rived, which are helpful to implement linear network coding for single-source multicast network. Several related applications are enumerated, and simulation results validate the conclusions derived by theoretical analysis. Key words:single-source multicast network, random linear network coding, ge

7、neration and e*tension of coding schemes at different multicast rate. 摘要:針對單源組播網(wǎng)絡(luò),通過對線性網(wǎng)絡(luò)編碼方案(編碼系數(shù)的組合)的在機理進展分析,提出了不同組播率下編碼方案的導(dǎo)出與擴展的概念:低組播的編碼方案可以由高組播率的編碼方案導(dǎo)出,高組播率的編碼方案可以由低組播率的編碼方案擴展而成.研究了具有導(dǎo)出與擴展關(guān)系的兩個編碼方案下全局編碼向量間的相互聯(lián)系,結(jié)合隨機線性網(wǎng)絡(luò)編碼,導(dǎo)出了幾個重要的性質(zhì),這些性質(zhì)有助于有效地運用線性網(wǎng)絡(luò)編碼技術(shù)實現(xiàn)單組播連接,具有一定的應(yīng)用價值.列出了幾個方面的應(yīng)用,基于相關(guān)的應(yīng)用給出了仿真

8、實驗,仿真結(jié)果驗證了理論分析的結(jié)論. 關(guān)鍵字:單源組播;隨機線性網(wǎng)絡(luò)編碼;不同組播率下編碼方案的導(dǎo)出與擴展 中圖法:TP911　　　文獻標識碼: A 網(wǎng)絡(luò)編碼[1-4]是一種新型的數(shù)據(jù)傳輸技術(shù),能提高網(wǎng)絡(luò)的吞吐率、魯棒性和平安性.Ahlswede 等人[1]首次提出了網(wǎng)絡(luò)編碼的概念,并指出:通過網(wǎng)絡(luò)中間節(jié)點的編碼可以實現(xiàn)單源組播網(wǎng)絡(luò)的最大流界,而傳統(tǒng)的路由技術(shù)一般情況下不能到達這個極限.碩彥等人[2]提出了線性網(wǎng)絡(luò)編碼技術(shù),并證明了線性網(wǎng)絡(luò)編碼技術(shù)可以充分實現(xiàn)這一功能.Koetter等人[3]給出了線性網(wǎng)絡(luò)編碼的代數(shù)框架.因線性網(wǎng)絡(luò)編碼具有簡單的特點,從而得到了深入廣泛地研究[4,5,6

9、,7,8]. 運用線性網(wǎng)絡(luò)編碼進展數(shù)據(jù)傳輸必須構(gòu)造編碼方案:確定源點的數(shù)據(jù)傳輸速率(組播率)和各信道的編碼系數(shù).已有文獻主要針對同一組播率下的編碼方案進展研究,而對不同的組播率下的編碼方案之間的關(guān)系研究較少.在實際應(yīng)用中,運用線性網(wǎng)絡(luò)編碼技術(shù)面臨以下問題:1)有時需要以不同的組播率進展數(shù)據(jù)傳輸,如采用已有的方法,則針對不同的組播率要設(shè)計不同的編碼方案,且編碼節(jié)點需保存不同組播率下的編碼系數(shù),占用了大量的存貯空間;2)盡管有文獻[9,10,11]基于網(wǎng)絡(luò)編碼提出了分布式構(gòu)造編碼方案或減少編碼代價的方法,但均是針對*一可行的組播率(不超過組播容量)進展研究,且假定組播容量是的或者能運用網(wǎng)絡(luò)的全局

10、拓撲知識采用最大流算法求出組播容量,而在實際應(yīng)用中,假設(shè)源點缺乏全局網(wǎng)絡(luò)拓撲知識,獲知網(wǎng)絡(luò)的組播容量是一件困難的事情,從而選定一個可行的組播率也是困難的;3)文獻[12,13]研究了動態(tài)網(wǎng)絡(luò)拓撲環(huán)境下的線性網(wǎng)絡(luò)編碼問題,均假定組播容量是且不變的,事實上在數(shù)據(jù)傳輸過程中,因接收點的隨機參加或離開,節(jié)點或鏈路的失效會造成網(wǎng)絡(luò)拓撲隨時間動態(tài)變化,從而導(dǎo)致了組播容量的變化,因此數(shù)據(jù)傳輸過程中需要動態(tài)地測試組播容量,以便動態(tài)地更改組播率. 針對單源組播網(wǎng)絡(luò),通過對線性網(wǎng)絡(luò)編碼的在機理進展分析,提出了不同組播率下編碼方案的導(dǎo)出與擴展的概念:一個組播率為h的編碼方案能導(dǎo)出一個組播率為k(k￡h)的編碼方案

11、,而后者僅在源點輸出信道的編碼系數(shù)略有不同,而一個組播為k的編碼方案通過擴展源點輸出信道的編碼系數(shù)便可以得到一個組播率為h的編碼方案.運用線性代數(shù)的相關(guān)理論對互為導(dǎo)出與擴展的兩個編碼方案進展研究,我們發(fā)現(xiàn)信道的全局編碼向量具有確定的關(guān)系.運用這一關(guān)系,結(jié)合隨機線性網(wǎng)絡(luò)編碼方法,推導(dǎo)出了幾個重要的性質(zhì),這些性質(zhì)對于運用線性網(wǎng)絡(luò)編碼技術(shù)具有一定的實用價值,能夠有效地解決上述問題:不同組播率下的編碼方案可共享編碼系數(shù),而不需重新構(gòu)造編碼方案;可以在線測試組播容量,且能把測試組播容量嵌入到數(shù)據(jù)傳輸過程中,而不會中斷數(shù)據(jù)傳輸;能在線構(gòu)造確定的編碼方案.對相關(guān)的應(yīng)用進展了仿真實驗,仿真結(jié)果驗證了理論分析的

12、結(jié)論. 1.相關(guān)知識 以下根據(jù)文獻[5]來表達線性網(wǎng)絡(luò)編碼的相關(guān)定義.一個單源組播網(wǎng)絡(luò)用有向無環(huán)多重圖G=(V,E)表示,其中V為節(jié)點集,E為有向邊集,TìV代表宿點集,s?V是源點,為討論方便,限定鏈路的容量為整數(shù),假設(shè)網(wǎng)絡(luò)節(jié)點之間存在容量大于1的有向鏈路,把它分成多條有向邊,有向邊e=(u,v)E代表節(jié)點u至節(jié)點v的單位容量的有向信道,其中u稱為e的始點,記為u=tail(e),v稱為e的終點,記為v=head(e).記In(v)={dE:head(d)=v}為v的輸入信道集合, 記Out(u)={eE:tail(e)=u}為u的輸出信道集合. 定義1:組播率和組播容量.單源組播網(wǎng)絡(luò)

13、的組播率是指源點的數(shù)據(jù)傳輸速率,記為h;組播容量記為C,等于源點與所有宿點之間的最小割值[1]. 線性網(wǎng)絡(luò)編碼操作在有限域上(本文采用伽羅華域GF(2m))[14],信息的編碼操作對應(yīng)于有限域上的字符運算,在單位時間,假設(shè)源點播出的信息字符為*1,*2,…,*h,每一字符均為m比特,屬于GF(2m)上的字符.信道e?E傳輸?shù)男畔⒂洖閥(e),也屬于GF(2m)上的字符. 定義2:局部編碼向量.采用線性網(wǎng)絡(luò)編碼,每一節(jié)點的輸出信道e傳輸?shù)男畔⑹窃摴?jié)點所有輸入信道傳輸信息的線性組合,這個線性組合的系數(shù)構(gòu)成該信道的局部編碼向量,記為m(e),則有 m(e)={md,e? GF(2m):d?In

14、(tail(e))} (1) (2) 定義3:全局編碼向量和全局編碼矩陣.假設(shè)采用線性網(wǎng)絡(luò)編碼以組播率h傳輸數(shù)據(jù),每一信道e傳輸?shù)男畔⒕梢员硎緸樵袋c播出信息*1,*2,…,*h的線性組合,這個線性組合的系數(shù)構(gòu)成一個向量,記為g(e)=(ge,1,ge,2,…,ge,h),則有 (3) (4) 對于任意節(jié)點vV,該節(jié)點所有輸入信道的全局編碼向量構(gòu)成了一個|In(v)|行,h列的矩陣,稱為該節(jié)點的全局編碼矩陣,每一信道的全局編碼向量構(gòu)成矩陣的一個行向量(注:|.|為集合的元素個數(shù)或向量的分量個數(shù),以

15、下同).由式(3),宿點可以通過其全局編碼矩陣和接收到的信息字符形成一個線性方程組,只有當該線性方程組的系數(shù)矩陣的秩等于h,宿點才能恢復(fù)出源點的信息. 定義4:編碼方案.單源組播網(wǎng)絡(luò)以組播率h采用線性網(wǎng)絡(luò)編碼進展數(shù)據(jù)傳輸,各信道的局部編碼向量的集合稱為一個組播率為h的編碼方案,在該編碼方案下,假設(shè)所有宿點的全局編碼矩陣的秩均為h,則稱為一個可行編碼方案. 一個編碼方案不一定是可行的,其最大組播率為H=|Out(s)|;假設(shè)編碼方案是可行的,由文獻[2],其組播率不能超過組播容量C. 文獻[8]提出了隨機線性網(wǎng)絡(luò)編碼方法,與集中式網(wǎng)絡(luò)編碼構(gòu)造方法[6]相比,該方法不需要獲知全局網(wǎng)絡(luò)拓撲知識

16、,它在數(shù)據(jù)傳輸過程中隨機地產(chǎn)生編碼系數(shù),即所有編碼節(jié)點為其輸出信道隨機生成局部編碼向量,為了使宿點實現(xiàn)解碼,每一編碼節(jié)點不僅需要進展信息編碼運算,同時需要計算輸出信道的全局編碼向量,且把全局編碼向量與傳輸?shù)男畔⒁詳?shù)據(jù)包形式沿輸出信道傳輸至下游節(jié)點.根據(jù)文獻[5],假設(shè)組播率為h,則信道上傳輸?shù)臄?shù)據(jù)包的格式如圖1所示. Fig.1 The structure of a data packet with random linear network coding 圖1 隨機線性網(wǎng)絡(luò)編碼的數(shù)據(jù)包格式 L稱為數(shù)據(jù)塊的長度,一般來說,所傳輸?shù)男畔⒘窟h遠超過L,因而需要進展假設(shè)干批數(shù)據(jù)傳輸才能完成整個

17、數(shù)據(jù)傳輸任務(wù). 2.線性網(wǎng)絡(luò)編碼方案的導(dǎo)出與擴展 以下定義了不同組播率下線性網(wǎng)絡(luò)編碼的導(dǎo)出與擴展的概念. 記一個組播率為h的編碼方案為xh (編碼方案是一個集合,集合的元素是各信道的局部編碼向量;也可以把編碼方案看成是由編碼系數(shù)構(gòu)成的集合,xh是一個集合變量).在編碼方案xh下,對于信道e?E,其局部編碼向量記為m(e,xh),全局編碼向量記為g(e, xh);節(jié)點v的全局編碼矩陣記為M(v, xh).由定義(2)和定義(3),信道e的局部編碼向量的維數(shù)為|In(tail(e))|,全局編碼向量的維數(shù)為h.因組播率為h,源點相當于具有h條虛擬輸入信道,它們把要傳輸?shù)膆個字符以及h維向量空

18、間的h個單位向量分別注入至源點.則對于源點的輸出信道,其局部編碼向量的維數(shù)是h,且全局編碼向量與局部編碼向量相等.而其余信道的局部編碼向量的維數(shù)與組播率h無關(guān),即: (5) 從式(5)可以看出,一個編碼方案xh包含了組播率為k(1kh)的編碼方案(在同一有限域下,以下同). 定義5:編碼方案的導(dǎo)出與擴展.對于一個組播率為 h的編碼方案xh,稱由式(6)確定的一個組播率為k(1kh)的編碼方案zk是由xh導(dǎo)出的,并稱xh是由zk擴展而成. zk={m(e, zk):e?E且m(e, zk)滿足式(7)} (6)

19、 (7) 式(7)的含義為:當e為源點s的輸出信道時,在zk下局部編碼向量由xh下的局部編碼向量的前k個元素構(gòu)成;對于其它信道,在zk下的局部編碼向量與xh下的局部編碼向量一樣.例如,圖2中的z2是由x3導(dǎo)出的. 從定義5可知,對于一個組播率為k的編碼方案,只要對源點輸出信道的局部編碼向量進展擴展,每一個局部編碼向量添加h-k個元素,構(gòu)成維數(shù)為h的向量,而對于其它信道,保持其局部編碼向量不變,則形成了一個組播率為h的編碼方案. 因此,對于一個組播率為k(1kh)的編碼方案,可以由*一個組播率為h的編碼方案導(dǎo)出,反之,一個組播率為h的編碼方案可以由*一個

20、組播率為k的編碼方案擴展而成. 3.幾個重要性質(zhì) 定理1:設(shè)兩個組播率k和h,xh是組播率為h的*一個編碼方案,zk是組播率為k且由xh導(dǎo)出的編碼方案,則在兩個編碼方案下,對于任意信道eE,它的全局編碼向量具有以下性質(zhì):g(e, zk)的k個分量與g(e, xh)的前k個分量對應(yīng)一樣,即假設(shè)g(e,xh )= (g1,g2,…,gk,gk+1,…,gh), 則g(e, zk)=(g1,g2,…,gk). 證明:采用歸納法證明. 1) 當e?out(s)時,由上所述,有g(shù)(e, zk)=m(e, zk) ,g(e, xh)=m(e, xh)成立.根據(jù)定義5,結(jié)論成立. 2)假設(shè)對于編碼

21、節(jié)點v(v1s),假設(shè)d?In(v)時結(jié)論成立,即:g(d, xh)=(g(d, zk) g’),其中g(shù)’是一個含有h-k個分量的向量*這里把向量寫成了矩陣形式,并利用了矩陣分塊的概念,把一個h維的向量看成是一個1行h列的矩陣.例如:(1,2,3,4)=(1 2 3 4)=((1 2) (3 4)). .不妨記節(jié)點v的輸入信道分別為d1,d2,…,d|In(v)|,并注意到定義3,節(jié)點的全局編碼矩陣是由其輸入信道的全局編碼向量組成,則 (8) 其中M’是一個|In(v)|行,h-k列的矩陣. 對于e?Out(v),根據(jù)定義5,有m(e, zk)=m(e, xh).假定m(e, zk)

22、=(m1,m2,…,m|In(v)|),再根據(jù)式(4),則 (9) (10) 結(jié)合式(8),(9),(10),根據(jù)分塊矩陣相乘的性質(zhì),得出:g(e,xh)=m(e,zk)(M(v,zk) M’)=(g(e, zk) m(e,zk)M’). 從而對于節(jié)點v的輸出信道,結(jié)論也成立.因單源組播網(wǎng)絡(luò)是一個有向無環(huán)圖,所有的節(jié)點存在一個偏序,按照這個偏序反復(fù)使用公式(4),可以把所有信道的全局編碼向量求出.由歸納法原理,結(jié)論成立.□ 圖2給出了定理1的一個例如.在圖2中,各鏈路的容量均為1,s為源點,r1和r2為宿點.x3是一個編碼方案,而z2是由x3導(dǎo)出的編碼方案.采用的有限域為GF(22

23、),其極小多項式為*2+*+1.分別在兩個編碼方案下,采用式(4)計算信道的全局編碼向量,所得結(jié)果如圖2所示,顯然滿足定理1的結(jié)論. Fig. 2 An illustration for generation and e*tension of coding schemes 圖2 編碼方案的導(dǎo)出與擴展示意圖 在編碼方案xh下,對于節(jié)點v?V,令N(v,xh,k)是由其全局編碼矩陣M(v,xh)的前k列構(gòu)成的一個矩陣,這里1￡k￡h. 推論1:假設(shè)xh是組播率為h的一個編碼方案,而zk是由xh導(dǎo)出且組播率為k的編碼方案,則對于任一節(jié)點v?T,在編碼方案zk下的全局編碼矩陣是由在編碼方案

24、xh下的全局編碼矩陣的前k列組成,即: M(v, zk)= N(v, xh ,k) 證明:由定理1和定義3,結(jié)論顯然成立.□ 推論2:假設(shè)xh是組播率為h的一個編碼方案,而zk是由xh導(dǎo)出且組播率為k的編碼方案,則zk是可行編碼方案的充分必要條件是對于每一個宿點r?T,有rank(N(r, xh, k) )=k,其中?rank(.)表示矩陣的秩. 證明:根據(jù)推論1,對于每一宿點r?T,它在編碼方案zk下的全局編碼矩陣為N(r, xh ,k),再根據(jù)定義4,結(jié)論成立.□ 性質(zhì)1:假設(shè)xh是組播率為h的一個可行的編碼方案,假設(shè)1￡k￡h,則由xh導(dǎo)出且組播率為k的編碼方案zk一定是可行的

25、. 證明:因xh是可行的,從而任一宿點r?T在xh下的全局編碼矩陣的秩為h,注意到這個矩陣只有h列,且矩陣的行數(shù)不小于h,這個矩陣的h個列向量線性無關(guān),則前k個列向量必定線性無關(guān),從而由這個矩陣的前k列構(gòu)成的矩陣其秩必為k,再由推論1,則任一宿點在編碼方案zk下的全局編碼矩陣的秩必為k,由推論2,結(jié)論成立.□ 源點s能獲知其輸出信道數(shù)H=|Out(s)|,H為源點的最大發(fā)送速率,記Vs={s},則是別離源點s與所有宿點的一個割集,其割值為H,因C為組播容量,由定義1,以下式子成立. C￡H (11) 在單源組播網(wǎng)絡(luò)中,讓ma*flow(s,r)為

26、別離源點s與宿點r的最小割值.假設(shè)以組播率H采用線性網(wǎng)絡(luò)編碼方法組播數(shù)據(jù)至所有宿點,相當于隨機產(chǎn)生了一個編碼方案,不妨記其編碼方案為xH. 引理1:在編碼方案xH下,則每一宿點r?T的全局編碼矩陣的秩不會超過ma*flow(s,r),即 rank(M(r, xH))￡ma*flow(s,r) r?T (12) 證明:由最大流-最小割定理,對于宿點r?T,存在一個別離源點s與宿點r的最小割,該割中有且只有ma*flow(s,r)條信道,這ma*flow(s,r)條信道攜帶的全局編碼向量成了H維向量空間的一個子空間,該子空間的秩不超過ma*flow(s,r),由線性網(wǎng)絡(luò)編碼的特點[2],

27、宿點r的每一輸入信道的全局編碼向量一定可以表示成這個最小割中的信道所攜帶的全局編碼向量的線性組合,由代數(shù)知識,宿點r的全局編碼矩陣的秩不能超過ma*flow(s,r),從而不等式(12)成立. □ 對不等式(12)兩邊取最小值,再由定義1,則 (13) 文獻[5,8]指出:在單源組播網(wǎng)絡(luò)中以組播率C采用隨機線性網(wǎng)絡(luò)編碼方法組播數(shù)據(jù),且采用的有限域的階為q(q>|T|,|T|為宿點個數(shù)),則所有宿點全局編碼矩陣的秩均為C的概率大于0,當有限域的階足夠大時,這個概率接近于1,不妨記這個概率為Pq.注意到當所有宿點的全局編碼矩陣的秩為C時,則對應(yīng)一個組播率為C的可行

28、編碼方案,由于隨機線性網(wǎng)絡(luò)編碼產(chǎn)生編碼系數(shù)的均勻性和隨機性,從而隨機從組播率為C的編碼方案中選擇一個編碼方案,其編碼方案是可行的概率為Pq. 定理2: 在單源組播網(wǎng)絡(luò)中以組播率H采用隨機線性網(wǎng)絡(luò)編碼方法組播數(shù)據(jù),且采用的有限域的階為q(q>|T|),記其編碼方案為xH,宿點r?T的全局編碼矩陣的前C列構(gòu)成的矩陣記為N(r,xH,C),則對于所有宿點,N(r,xH,C)的秩等于C的概率為Pq,即 (14) 證明:在其階為q的有限域下,不妨設(shè)有a個組播率為C的編碼方案,其中有b個是可行的,則Pq=b/a.注意到 CH,由定義5,所有組播率為H的編碼方案均由

29、組播率為C的編碼方案擴展而成.對組播率為C的編碼方案,只需對源點輸出信道的局部編碼向量進展擴展,每一向量擴展H-C個分量,便構(gòu)成了組播率為H的編碼方案,則組播率為H的編碼方案比組播率為C的編碼方案多了 (H-C) |Out(s)|個分量,由隨機線性網(wǎng)絡(luò)編碼方法在q階有限域上取各分量值的均勻和隨機性,再根據(jù)乘法原理,則組播率為H的編碼方案數(shù)為aq|out(s)|(H-C),其中有bq|out(s)|(H-C)個編碼方案是由組播率為C的可行編碼方案擴展而成的,因而隨機構(gòu)造一個組播率為H的編碼方案,它是由組播率為C的可行編碼方案擴展而成的概率為Pq,由推論2,結(jié)論成立.□ 性質(zhì)2:對于單源組播網(wǎng)絡(luò)

30、,以組播率H采用隨機線性網(wǎng)絡(luò)編碼方法傳輸數(shù)據(jù),不妨記其編碼方案為xH,則宿點r?T接收到所有的數(shù)據(jù)包后,析出全局編碼矩陣,并按式(15)計算?h(r,xH)?,源點按式(16)計算f(xH),當采用的有限域足夠大時,f(xH)不超過C且f(xH)=C的概率接近于1. (15) (16) 證明:由矩陣的性質(zhì),當k￡H時,有rank(N(r, xH, k)) ￡ rank(M(r, xH)),再根據(jù)式(13),(15),(16),必定有f(xH) ￡C.根據(jù)定理2,則f(xH) 3C的概率為Pq,從而當有限域較大時,f(xH) =C的概率接近于1.□ 式(15)的含義是:對于任一宿點r,

31、尋找一個最大的h,且滿足全局編碼矩陣M(v,xH)的前h列構(gòu)成的矩陣其秩為h.可以通過對矩陣M(v, xH)作行初等變換,把矩陣化為上三角形式來計算式(15),限于篇幅,不作詳細討論. 4. 應(yīng)用 以上描述的定理、推論與性質(zhì)有助于有效地運用線性網(wǎng)絡(luò)編碼技術(shù),具有一定的實用價值. 4.1 不同組播率下編碼系數(shù)的共享 由性質(zhì)1,假設(shè)單源組播網(wǎng)絡(luò)具有一個組播率為h的可行編碼方案,則可以任意選擇組播率k(k￡h)進展數(shù)據(jù)傳輸,而不用重新構(gòu)造編碼方案. 記原有可行編碼方案為xh,假設(shè)采用組播率k進展數(shù)據(jù)傳輸,則可以采用xh的導(dǎo)出編碼方案.由性質(zhì)1,xh的導(dǎo)出編碼方案必定是可行的.在組播率為k的

32、導(dǎo)出編碼方案下,源點輸出信道的局部編碼向量取其在xh編碼方案下的局部編碼向量的前k個分量,而其余信道的局部編碼向量不變,從而各節(jié)點只要保存組播率為h的可行編碼方案的編碼系數(shù),便可以采用組播率k(k￡h)進展數(shù)據(jù)傳輸. 4.2 測試組播容量及構(gòu)造編碼方案 性質(zhì)2提供了一個測試組播容量的方法,因源點能獲知其輸出信道數(shù)H,則能以組播率H采用隨機線性網(wǎng)絡(luò)編碼方法組播試驗包至所有宿點,由于僅關(guān)心宿點的全局編碼矩陣,則數(shù)據(jù)塊可以為空,從而試驗包的格式如圖3所示. Fig.3 The structure of a trial packet 圖3 試驗包的構(gòu)造 假設(shè)以組播率為H采用隨機線性網(wǎng)絡(luò)編

33、碼方法組播數(shù)據(jù)至網(wǎng)絡(luò),相當于隨機產(chǎn)生了一個編碼方案,不妨記為xH.所有宿點只需按式(15)計算h(r,xH),源點按式(16)計算f(xH).由性質(zhì)2, 當有限域較大時,f(xH)=C的概率接近于1.我們把一次試驗包的傳輸稱為一次測試,當采用的有限域的階不夠大時,為確保找到組播容量,可以采用蒙托卡羅法進展屢次測試.每次測試時,源點記錄最好的結(jié)果.這一策略還可以用于構(gòu)造編碼方案,只需在測試過程中各節(jié)點保存編碼系數(shù),則在測試出組播容量C的同時,構(gòu)造出了組播率為C的可行編碼方案.與文獻[6]提出的LIF法相比,該方法具有操作簡單的特點. 假設(shè)各宿點能反應(yīng)信息至源點,即宿點能把?h(r,xH)的值傳

34、輸至源點,則可以采用分布式方式在線測試組播容量. 對于靜態(tài)網(wǎng)絡(luò)(網(wǎng)絡(luò)拓撲在完成整個數(shù)據(jù)傳輸任務(wù)的過程中不會發(fā)生變化),假設(shè)所有宿點能反應(yīng)信息至源點,則可以在線構(gòu)造確定的網(wǎng)絡(luò)編碼方案,且各編碼系數(shù)保存在相應(yīng)的節(jié)點中,從而可以采用確定的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸策略傳輸數(shù)據(jù). 4.3 動態(tài)環(huán)境下網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸策略 假設(shè)宿點能反應(yīng)信息至源點,則根據(jù)上述理論可以構(gòu)造出網(wǎng)絡(luò)拓撲動態(tài)變化環(huán)境下的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸策略.采用網(wǎng)絡(luò)編碼進展數(shù)據(jù)傳輸?shù)淖顑?yōu)策略是使組播率不超過且貼近組播容量,以便使網(wǎng)絡(luò)的吞吐率盡可能大.如前所述,一個傳輸任務(wù)通過多批數(shù)據(jù)傳輸來完成,因網(wǎng)絡(luò)拓撲的變化會造成組播容量的變化,則在各批數(shù)據(jù)傳輸

35、時需要更改組播率以適應(yīng)組播容量的變化.因此,一方面需進展數(shù)據(jù)傳輸,另一方面要測試組播容量,如把測試組播容量嵌入到每批數(shù)據(jù)傳輸過程中,則不會中斷網(wǎng)絡(luò)的數(shù)據(jù)傳輸.設(shè)當前的組播率為k, 假設(shè)采用隨機線性網(wǎng)絡(luò)編碼方法組播數(shù)據(jù),則對應(yīng)一個組播率為k的編碼方案,不妨記為zk;為測試組播容量,由上所述,需要以組播率為H采用隨機線性網(wǎng)絡(luò)編碼方法組播試驗包至網(wǎng)絡(luò),其編碼方案記為xH.由于兩者均具有隨機性,可以把zk當成是xH的導(dǎo)出編碼方案,由定義5和推論1,可以讓這兩個編碼方案的編碼系數(shù)共享. 實施方法如下:源點相當于具有H條虛擬輸入信道,它們分別注入H維向量空間的單位向量至源點s,記為p1,p2,…,pH,

36、前k條虛擬輸入信道分別把要發(fā)送的字符注入至源點s,記為y1,y2,…,yk,如圖4所示. Fig.4 Testing multicast capacity in data transmission 圖4 數(shù)據(jù)傳輸過程中測試組播容量 對于源點s的輸出信道e?Out(s), 其局部編碼向量m(e)是一個H維的向量,設(shè)m(e)=(me,1,…,me,H),各分量由源點隨機產(chǎn)生,則信道e傳輸?shù)娜志幋a向量與字符分別按式(17)和式(18)計算. (17) (18) 假設(shè)e?Out(v)(v1s), 其局部編碼向量如式(1)所示,各分量由節(jié)點v隨機產(chǎn)生,信道e傳輸?shù)娜志幋a向量和字符分

37、別按式(4)和式(2)計算. 宿點r?T接收到所有的數(shù)據(jù)包后,從中析出全局編碼矩陣M(r, xH),把前k列構(gòu)成的矩陣N(r, xH,k)作為方程組的系數(shù)矩陣,解出源信息字符;再按式(15)求出h(r, xH)并傳輸至源點s,源點s收到所有宿點的反應(yīng)信息后,按式(16)便可以計算出組播容量(當有限域較大時),從而在下一批數(shù)據(jù)傳輸時,可以根據(jù)測試出的組播容量調(diào)整組播率,以便適應(yīng)網(wǎng)絡(luò)拓撲的變化.由性質(zhì)2,因f(xH) ￡C,即使f(xH)達不到C,則源點選取不超過f(xH)的組播率必定為可行的組播率. 盡管采用這種策略測試出的組播容量是傳輸前一批數(shù)據(jù)時的組播容量,但當組播容量的變化具有一定的平

38、穩(wěn)性時,并結(jié)合重傳技術(shù)(當有宿點不能解碼時,要求源點重傳信息),則仍不失為一種較好的策略,它能跟蹤網(wǎng)絡(luò)拓撲的變化,使組播率盡可能地適應(yīng)組播容量的變化,且把測試組播容量嵌入至數(shù)據(jù)傳輸過程中,不會中斷網(wǎng)絡(luò)的數(shù)據(jù)傳輸,與隨機網(wǎng)絡(luò)編碼方法相比,信道傳輸?shù)臄?shù)據(jù)包僅增加了全局編碼向量的維數(shù). 5. 仿真測試 采用5個測試用例,其中測試用例1如圖4所示,其它4測試用例采用文獻[15]的方法隨機產(chǎn)生.測試用例1:|V|=26,|E|=85,|T|=5,H=13,C=6;測試用例2:|V|=40,|E|=174,|T|=10,H=11,C=10;測試用例3:|V|=45,|E|=202,|T|=10,H=1

39、2,C=9;測試用例4: |V|=50,|E|=237,|T|=10,H=13,C=12;測試用例5:|V|=55,|E|=259,|T|=10,H=14,C=11. 測試方法如下,對不同的測試用例,在不同的伽羅華域GF(2m)下,以組播率H采用隨機線性網(wǎng)絡(luò)編碼的方法組播試驗包至網(wǎng)絡(luò),測試次數(shù)為500次,統(tǒng)計出所有宿點全局編碼矩陣的前k(k=k1,C,其中k1C時,第三個編碼方案必定是不可行的,前兩個編碼方案是第三個編碼方案

40、的導(dǎo)出編碼方案,第一個編碼方案也是第二個編碼方案的導(dǎo)出編碼方案,在測試過程中,我們還驗證當?shù)诙€編碼方案是可行時,第一個編碼方案的可行性. Table 1 Simulation results 表1 仿真結(jié)果 m 測試用例1 測試用例2 測試用例3 測試用例4 測試用例5 k=5 k=6 k=9 k=10 k=8 k=9 k=10 k=12 k=10 k=11 4 0.894 0.272 0.846 0.274 0.980 0.702 0.994 0.328 0.998 0.918

41、5 0.980 0.566 0.964 0.612 0.996 0.838 0.998 0.628 1 0.954 6 0.996 0.748 0.996 0.832 0.998 0.918 1 0.782 1 0.990 7 0.998 0.862 0.998 0.896 1 0.962 1 0.900 1 0.992 8 1 0.930 1 0.952 1 0.986 1 0.952 1 1 9 1 0.9

42、70 1 0.972 1 0.990 1 0.978 1 1 10 1 0.988 1 0.980 1 0.992 1 0.986 1 1 11 1 0.986 1 0.994 1 0.998 1 1 1 1 12 1 1 1 1 1 1 1 1 1 1 我們的試驗結(jié)果說明,每當?shù)诙€編碼方案是可行的,第一個編碼方案必定是可行的,從而驗證了性質(zhì)1的正確性. 從表1中可以看出,當有限域較大時(m>10),對于給定的測試用例,在線測試出組播容量是一個

43、大概率事件,從而驗證了性質(zhì)2的正確性;即使當有限域較小時(4￡m￡10),采用蒙托卡羅法,能測試出組播容量也是一個大概率事件. 注意以下事實:采用式(16)求f(xH),則f(xH)3k(k￡C)的充要條件是對于所有的r?T,有rank(N(r, xH, k)) =k成立.因而當有限域較大時,本文給出的動態(tài)環(huán)境下的數(shù)據(jù)傳輸策略是有效的,從表1中可以看出:對于單次測試,能測試出組播容量是一個大概率事件,即使式(16)中的f(xH)達不到C,必定與C接近.例如對于測試用例3,5,當m>6時，每一次測試均使f(xH)的值不低于C-1. 6. 完畢語 針對單源組播網(wǎng)絡(luò),通過對線性網(wǎng)絡(luò)編碼的在機理

44、進展分析,提出了不同組播率下編碼方案的導(dǎo)出與擴展的概念,對具有導(dǎo)出與擴展的兩個編碼方案進展研究,導(dǎo)出了信道全局編碼向量之間確實切關(guān)系,利用這個關(guān)系,結(jié)合隨機線性網(wǎng)絡(luò)編碼方法,得出了幾個重要的性質(zhì),這些性質(zhì)有助于有效地運用線性網(wǎng)絡(luò)編碼技術(shù),具有一定的應(yīng)用價值.仿真結(jié)果驗證了理論分析的結(jié)論. 下一步的工作是在多源組播情況下,如何對這些理論和應(yīng)用進展推廣. References: [1] Ahlswede R,Cai N,Li S R,et al..Network information flow .IEEE Transaction on Information Theory,2000,46(

45、4):1204-1216. [2] Li S-Y R,Yeung R W,Cai N.Linear network coding.IEEE Transaction Information Theory,2003,49(2):371-381. [3] Koetter R,Medard M.An algebraoc approach to network coding.IEEE/ACM Transaction on Networking, 2003,11(5):782-795. [4] Yang Lin, Zheng Gang, Hu *iao-hui. Research on networ

46、k coding:A Survey.Journal of puter Research and Development,2021,45(3):400-407. [5] ChouP A,Wu Y, Jain K. Practical network coding.Allerton Conference on munication, Control and puting, Monticello, 2003:473-482. [6] Jaggi s,Sanders p,Chou A et al.Polynomial time algorithms for multicast network co

47、de construction.IEEE Transaction on Information Theroy,2005:51(6):1973-1982. [7] Fragouli C,Soljanin E.Information flow deposition for network coding.IEEE Transaction on Information Theory ,2006,51(4):1295-1312. [8] Ho T,Medard M,Koetter R,et al.. A random linear network coding approach to multica

48、st.IEEETransaction Information Theory,2006,52(10):4413-4430. [9] Jabbarihagh M,Lahouti F. A decentralized approach to network coding based on learning.Information Theory for Wireless Networks, 2007 IEEE Information Theory Workshop on. [10] Kim M, Medard M, Aggarwal,V et al.A doubly distributed gen

49、etic algorithm for network coding.2007 ACM Genetic and Evolutionary putation Conference (GECCO 2007), July 2007, London, UK.. [11] LunDS,RatnakarN,MedardMet al. Minimum-cost multicast over coded packet networks.IEEE Transactions on Information Theory,2006,52(6):2608-2623. [12] Tracey H, Ben L, Mur

50、iel M et al.On the utility of network coding in dynamic Environments. Informational WorkshoponWireless Ad-hoc Networks (IWWAN) 2004. [13] Zhao F, M′edard M. Online network coding for the dynamic multicast problem. ISIT 2006, Seattle, USA. [14] Wang Beng-shan. Discretemathematics.Changsha: National

51、 University of Defence Technology Press, 2004:263-281. [15] Melancon G,Philippe F. Generating connected acyclic digraphs uniformly at random.Information Processing Letters,2004,90(4):209-213. 附中文參考文獻: [4] 林,剛,胡曉惠.網(wǎng)絡(luò)編碼研究進展.計算機研究與開展,2021,45(3):400-407. [14] 王兵山.離散數(shù)學(xué).:國防科技大學(xué),2004:263-281. 附

52、 錄 為專家審稿方便,特提供這個附錄,如本文能發(fā)表,則附錄局部不必登載. 1 GF(22)運算表(極小多項式為) 圖2中的數(shù)據(jù)按以下表計算. 四進制形式加法運算表 + 0 1 2 3 0 0 1 2 3 1 1 0 3 2 2 2 3 0 1 3 3 2 1 0 四進制形式乘法運算表 * 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 3 1 3 0 3 1 2 二進制形式加法運算表 + 00 01 10 11 00 00 01 10 11

53、01 01 00 11 10 10 10 11 00 01 11 11 10 01 00 二進制形式乘法運算表 * 00 01 10 11 00 00 00 00 00 01 00 01 10 11 10 00 10 11 01 11 00 11 01 10 2 求式(15)中h(r,xH)?的算法 找一個最大的列數(shù)h,使矩陣的前h列構(gòu)成的矩陣的秩為h. 設(shè)矩陣為,其中m為行數(shù),n為列數(shù). 第1步:置i=1,mark=1; 第2步:while mark=1 and i

54、第3步:檢查第i列中自第i行至第m行的元素(ai,i,ai+1,i,…,am,i),假設(shè)所有元素全為零,置mark=0; 否則找出其不為零的元素所在的行號(記為k); 第4步:假設(shè)mark=1,則進展下述工作 4.1 把第i行與第k行交換; 4.2 把第j(ii; 第5步: end while 第6步:輸出結(jié)果為i-1; 第7步:完畢. 該算法的時間復(fù)雜度為O(h2),其中h是滿足條件的最大者. 3 仿真測試中伽羅華域的代數(shù)運算方法

55、 因信息編碼與數(shù)據(jù)通信均以比特流為根底,盡管文獻[1-3]中指出網(wǎng)絡(luò)編碼技術(shù)是在有限域上進展信息編碼,但在實際應(yīng)用中宜采用伽羅華域〔伽羅華域是有限域的特例〕.這是因為同一伽羅華域上的字符均為位數(shù)一樣的二進串,而一般的有限域不具備這個性質(zhì). 定義1[14]:一個F(2)上的不可約多項式叫做一個極小多項式,一個極小多項式可以唯一確定一個伽羅華域. 一個極小多項式?jīng)Q定了其對應(yīng)的伽羅華域的各個元素〔字符〕,同時也確定了該伽羅華域上的運算.在組播網(wǎng)絡(luò)中采用網(wǎng)絡(luò)編碼技術(shù)進展數(shù)據(jù)傳輸時,要使各宿點能正確地解出源點播出的信息字符,各節(jié)點必須在一樣的伽羅華域上進展編碼,即各節(jié)點選定的極小多項式是一樣的.設(shè)一

56、個次數(shù)為m的極小多項式,如式(a)所示,其相應(yīng)的伽羅華域記為GF(2m),其中q=2m稱為伽羅華域的階,m稱為伽羅華域的次. (a) 式(a)中的,即取1或0. 由伽羅華域的性質(zhì),GF(2m)中的每一元素(字符)都是其極小多項式的根,即任意,有 (b) 在已有的文獻中,針對伽羅華域的乘除運算一般采用硬件電路實現(xiàn),或者通過查找乘法表實現(xiàn).由于不同的伽羅華域的乘法運算與不同的硬件電路對應(yīng),也與不同的乘法表對應(yīng),盡管這些方法運算簡便,但對于網(wǎng)絡(luò)編碼技術(shù)是不適合的,主要原因是難以設(shè)計節(jié)點的編碼器/解碼器.網(wǎng)絡(luò)中的節(jié)點可

57、能會參與不同的組播連接,而每一組播連接所采用的伽羅華域的階不一定一樣,即節(jié)點必須具有不同階伽羅華域的計算能力.假設(shè)采用硬件電路實現(xiàn)乘除法運算,編碼器/解碼器上必須具有不同階伽羅華域的乘除法運算電路;假設(shè)采用查表法實現(xiàn),則每一節(jié)點需要保存不同階伽羅華域的乘法表,存開銷將會相當?shù)卮?從而對網(wǎng)絡(luò)編碼來說,只能從伽羅華域的代數(shù)構(gòu)造出發(fā)來構(gòu)造代數(shù)運算方法,這樣,節(jié)點的編碼器/解碼器只需要保存不同階的伽羅華域的極小多項式和代數(shù)運算的算法,從而設(shè)計編碼器/解碼器成為可能. 設(shè)GF(2m)上參與運算的三個字符分別記為: ,, (c) 由文獻[14],伽羅華域的乘除法運算歸結(jié)為其相應(yīng)的多項式的運算,則

58、它們對應(yīng)的多項式分別記為: ,, (d) 接下來表達伽羅華域的代數(shù)運算方法,其中除法運算方法是我們首次提出的. 加法(減法)運算:加法運算就是兩個字符對應(yīng)位的異或運算,假設(shè),則有,在伽羅華域上,減法與加法是同一運算 乘法運算:兩個字符的乘法運算轉(zhuǎn)化它們相應(yīng)的多項式運算,假設(shè)c=ab,則C(*)滿足以下關(guān)系式[14]: (e) 由式(e)可以確定乘法運算的方法:先進展兩個多項式的相乘,在相乘過程中合并同類項時系數(shù)按模2加〔即異或運算〕,得到一個不高于2m-2次的多項式;然后對于次數(shù)大于或等于m的項,用式(b)代入進展降次,最后得

59、到一個次數(shù)低于m的多項式,其系數(shù)便是字符c的相應(yīng)位. 除法運算:我們提出了一種適合網(wǎng)絡(luò)編碼的伽羅華域上的除法運算方法,該方法類似于歐幾里德除法,描述如下: 求c=a/b,則它們對應(yīng)的多項式必須滿足: (f) 由于a,b是的,則它們對應(yīng)的多項式A(*)和B(*)的系數(shù)是的,而C(*)是系數(shù)是未知的,分別用未知數(shù)c0,c1,…,cm-1表示,計算方程〔f〕的右邊局部就是兩個字符的乘法運算,則通過逐位相乘并合并同類項后得到一個次數(shù)不超過2m-2的多項式,它們的系數(shù)中含有未知數(shù),與上所述,再用式(b)進展降次,便得到了一個次數(shù)不超過m且系數(shù)含有求知數(shù)的多項式,由式(f),利用與A(*)相等的關(guān)系,則其系數(shù)對應(yīng)一樣,可以得到一個m階的線性方程組,采用高斯消元法求解這個線性方程組便提出了C(*)的系數(shù),從而求出了商c. 例:取m=3,極小多項式方程為,求伽羅華域GF(23)的兩個字符(101)2與(110)2的商. 解:置,, 則,用代入后,得 ,再用代入得 再根據(jù) 則得到以下線性方程組: 采用高斯消元法求解得到商c=(100)2. . z