曹張華，吉曉東，劉 敏

(南通大學(xué)電子信息學(xué)院，南通 226019)

0 引言

網(wǎng)絡(luò)編碼這一思想由Yeung等在文獻(xiàn)［1］中首先應(yīng)用于對衛(wèi)星通信系統(tǒng)的研究，隨后Ahlshede等在文獻(xiàn)［2］中明確提出了網(wǎng)絡(luò)編碼這一概念，并證明了使用網(wǎng)絡(luò)編碼可以有效提高網(wǎng)絡(luò)容量利用率。文獻(xiàn)［3－4］給出了構(gòu)造適用于組播網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼，接著Ho等在文獻(xiàn)［5］中研究了隨機線性網(wǎng)絡(luò)編碼這一實用的數(shù)據(jù)傳輸技術(shù)。文獻(xiàn)［1－5］討論了網(wǎng)絡(luò)編碼和線性網(wǎng)絡(luò)編碼，但他們研究網(wǎng)絡(luò)編碼時均假定網(wǎng)絡(luò)的信息率固定，然而在實際應(yīng)用中，信源在不同的時刻需要給不同的節(jié)點發(fā)送不同數(shù)量的消息分組，這就是變信息率網(wǎng)絡(luò)通信問題，該問題可視為文獻(xiàn)［6］中變信息率信道問題的網(wǎng)絡(luò)化。

Jaggi等在文獻(xiàn)［7］中提出的解決變信息率網(wǎng)絡(luò)通信問題的方法是為每一個信息率建立一線性網(wǎng)絡(luò)編碼，然后將相應(yīng)的局部網(wǎng)絡(luò)編碼核存儲起來，顯然，這會耗費網(wǎng)絡(luò)中繼節(jié)點的大量存儲資源。Fong和Yeung在文獻(xiàn)［8－9］中用降維法構(gòu)造的線性網(wǎng)絡(luò)編碼能實現(xiàn)變信息率網(wǎng)絡(luò)的有效通信，但對每一信息率，都需要根據(jù)最高維線性網(wǎng)絡(luò)編碼進(jìn)行迭代計算，才能獲得一合適的低維線性網(wǎng)絡(luò)編碼。Goseling等在文獻(xiàn)［10］中研究了變信息率網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼構(gòu)造和網(wǎng)絡(luò)費用之間的平衡問題。文獻(xiàn)［11］從跨層設(shè)計的角度研究了變信息率網(wǎng)絡(luò)編碼的實現(xiàn)問題。文獻(xiàn)［12－13］研究了無線變信息率網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼，通過在網(wǎng)絡(luò)中繼節(jié)點尋找更多的網(wǎng)絡(luò)編碼機會，自適應(yīng)地調(diào)整網(wǎng)絡(luò)編碼策略，來實現(xiàn)高效的變信息率通信。Mar等在文獻(xiàn)［14］中將中繼協(xié)作和網(wǎng)絡(luò)編碼相結(jié)合，提高了變信息率網(wǎng)絡(luò)的通信效率。但文獻(xiàn)［11－14］只使用仿真結(jié)果驗證了所提出方法的有效性，沒有給出顯式解。文獻(xiàn)［15］對網(wǎng)絡(luò)編碼在數(shù)據(jù)傳輸中的積極作用進(jìn)行了綜述。針對已有的變信息率網(wǎng)絡(luò)編碼方法的缺點，該文構(gòu)造了一種新的、能在變信息率網(wǎng)絡(luò)中實現(xiàn)有效通信的線性網(wǎng)絡(luò)編碼。該方法無需為適應(yīng)不同的信息率而頻繁地重新計算出新網(wǎng)絡(luò)編碼。

1 基本概念

通信網(wǎng)絡(luò)用有向、無圈圖G=(V，E)表示。其中，V是節(jié)點集，E是信道集，顯然E?V×V。網(wǎng)絡(luò)G=(V，E)中的信道用有向邊 e=(u，v)表示，且設(shè)每一信道的容量均為單位容量。對有向邊e=(u，v)，節(jié)點u稱為e的尾節(jié)點，v稱為e的頭節(jié)點，分別記為u=t(e)和v=h(e)。對任意節(jié)點v∈V，其入邊集和出邊集分別記為

通信網(wǎng)絡(luò)G=(V，E)中的信源節(jié)點s到任一非源節(jié)點v的最大流記為maxflow(s，v)，信源s發(fā)送的消息用有限域Fq上的等長的數(shù)據(jù)組表示，設(shè)信源s發(fā)送的消息數(shù)據(jù)組為(Fq)N中的向量x1，x2，…，xn。在通信網(wǎng)絡(luò)G=(V，E)中使用線性網(wǎng)絡(luò)編碼這一數(shù)據(jù)傳輸技術(shù)時，網(wǎng)絡(luò)中任一節(jié)點v∈V的任一輸出邊所傳輸?shù)臄?shù)據(jù)組是輸入邊所傳輸?shù)臄?shù)據(jù)組的線性組合。即對任意的信道e∈E，記其傳輸?shù)臄?shù)據(jù)組為向量fe稱為e的全局網(wǎng)絡(luò)編碼核，e∈ΓI(s)時，稱fe為虛擬全局網(wǎng)絡(luò)編碼核。

定義1 有向無圈圖G=(V，E)表示一單信源通信網(wǎng)絡(luò)，F(xiàn)q為一有限域，設(shè)信源s發(fā)出的消息數(shù)據(jù)組為 x1，x2，…，xn∈，使用線性網(wǎng)絡(luò)編碼進(jìn)行數(shù)據(jù)傳輸時，對任意的 el∈ΓO(s)，有對非源節(jié)點v∈V及任意的邊ej∈ΓO(v)，有

(4)式和(5)式中，αi，el，βei，ej稱為局部網(wǎng)絡(luò)編碼核。

對任意的非源節(jié)點v，其局部網(wǎng)絡(luò)編碼核構(gòu)成|ΓI(v)|× |ΓO(v)|的矩陣 Kv;對源節(jié)點 s，其局部網(wǎng)絡(luò)編碼核構(gòu)成n×|ΓO(s)|的矩陣Ks。顯然全局網(wǎng)絡(luò)編碼核由局部網(wǎng)絡(luò)編碼核決定。此處的定義綜合了文獻(xiàn)［3－4］中的基本概念。

2 變信息率網(wǎng)線性絡(luò)編碼的構(gòu)造

有向無圈圖G=(V，E)表示單信源通信網(wǎng)絡(luò)，且信源s在不同時刻發(fā)送的消息數(shù)不一樣。記信源s的M個不同的信息率為正整數(shù)r1＞r2＞…＞rM，為討論的方便起見，設(shè)

對信息率 ri和非信源節(jié)點 v，若有 ri≤maxflow(s，v)，則要求非源節(jié)點v能夠恢復(fù)出ri個信源消息，這樣的網(wǎng)絡(luò)稱為變信息率線性廣播網(wǎng)絡(luò)。若有線性網(wǎng)絡(luò)編碼在變信息率線性廣播網(wǎng)絡(luò)中實現(xiàn)上述目標(biāo)，則稱該網(wǎng)絡(luò)編碼能實現(xiàn)變信息率線性廣播網(wǎng)絡(luò)的有效通信。

2.1 基本思想

實現(xiàn)單信源、多信息率網(wǎng)絡(luò)G=(V，E)有效通信的基本思路如下。首先建立變信息率通信網(wǎng)絡(luò)G=(V，E)中Fq上的r1維線性網(wǎng)絡(luò)編碼，該線性網(wǎng)絡(luò)編碼能使得滿足條件maxflow(s，u)≥r1的節(jié)點u恢復(fù)出信源發(fā)送的消息。對其他的非源節(jié)點v，當(dāng)信息率 r≤maxflow(s，v)，且 r＜r1時，記信源發(fā)送的消息分組為 x1，…，xr∈(Fq)N，而 xr+1，…，xr1為(Fq)N中的零向量。這樣，對于信息率r，仍設(shè)信源s發(fā)送的消息數(shù)據(jù)組構(gòu)成的消息向量為x=(x1，…，xr，xr+1，…，xr1)，只是其中的 xr+1，…，xr1為零向量。仍使用上面給出線性網(wǎng)絡(luò)編碼，不改變通信網(wǎng)絡(luò)中的各節(jié)點的局部網(wǎng)絡(luò)編碼核，只是要求ΓI(v)中存在r條信道ei1，…，eir，這r條信道所對應(yīng)的全局網(wǎng)絡(luò)編碼核fei1，…，feir的前r個分量構(gòu)成的短向量組f'ei1，…，f'eir是線性無關(guān)的。下面舉一個例子來說明上述想法。

例1 單信源通信網(wǎng)絡(luò)G=(V，E)如圖1所示，信道的容量為單位容量，信源到非源節(jié)點的信息率分別為1，2，3。當(dāng)信息率為3時，充當(dāng)字母表的有限域為F5，設(shè)信源發(fā)送的消息為(F5)N中的向量x1，x2，x3，記信源消息分組構(gòu)成的向量為 x=(x1，x2，x3)。

圖1 信息率為1，2，3的網(wǎng)絡(luò)Fig.1 Network G=(V，E)with rates 1，2 and 3

由定義1，通信網(wǎng)絡(luò)中各信道傳輸?shù)臄?shù)據(jù)組為

系數(shù) αi，el和 βei，ej為通信網(wǎng)絡(luò)的局部網(wǎng)絡(luò)編碼核。對圖1中的通信網(wǎng)絡(luò)進(jìn)行如下的網(wǎng)絡(luò)編碼，局部網(wǎng)絡(luò)編碼核為

對于如圖1所示的通信網(wǎng)絡(luò)，信源s的信息率為1時，令x2=x3= 0;信源信息率為2時，令x3=0。使用如上的線性網(wǎng)絡(luò)編碼，對任一信息率，無需改變通信網(wǎng)絡(luò)中的局部網(wǎng)絡(luò)編碼核，只需在解碼過程中，將非源節(jié)點輸入邊的全局網(wǎng)絡(luò)編碼核中與零消息分組相對應(yīng)的分量去除。顯然，使用如上的方法可實現(xiàn)如圖1所示的變信息率網(wǎng)絡(luò)的有效通信。

2.2 傳輸矩陣

記單信源，變信息率通信網(wǎng)絡(luò)為G=(V，E)，對網(wǎng)絡(luò)中的信道進(jìn)行編號時，要求任一中繼節(jié)點v的入邊集ΓI(v)中的信道編號小于ΓO(v)中的信道編號。

對于如圖1所示的變信息率通信網(wǎng)絡(luò)G=(V，E)，記信道集E所傳輸?shù)臄?shù)據(jù)組為

顯然，K(I－F)－1是3×10矩陣，對于網(wǎng)絡(luò)中的任一非源節(jié)點v。此時ΓI(v)中的邊所對應(yīng)的全局網(wǎng)絡(luò)編碼核與矩陣K(I－F)－1中的部分列向量相對應(yīng)，將相應(yīng)的列選出，構(gòu)成一局部傳輸矩陣。當(dāng)信源的信息率r≤maxflow(s，v)，只需局部傳輸矩陣前r行構(gòu)成的子矩陣的秩為r。

對一般的單信源，變信息率通信網(wǎng)絡(luò)G=(V，E)，如前面所述，信源s的最大信息率為r1，其發(fā)送的信源消息分組記為 x1，x2，…，xr1∈FNq，則矩陣 K中的單項Kil定義為

(24)式中，Kil的下標(biāo)i對應(yīng)信源消息xi，這樣得到的矩陣K是r1×|E|的。

而矩陣F中的單項Fij定義為由此得到|E|×|E|矩陣F。對有向無圈通信網(wǎng)絡(luò)G=(V，E)中的信道編號，任一節(jié)點v的輸出邊的編號大于輸入邊的編號。因此，矩陣F是一主對角線元素全為0的上三角矩陣，從而可得det(I－F)=1，即矩陣I－F是|E|×|E|的可逆矩陣。

與例1相似，任一單信源通信網(wǎng)絡(luò)G=(V，E)都對應(yīng)了一矩陣K(I－F)－1，該矩陣定義了信源輸入消息與網(wǎng)絡(luò)中各信道所傳輸?shù)臄?shù)據(jù)組之間的關(guān)系，稱這樣的矩陣為全局傳輸矩陣。事實上，對任一單信源，變信息率的通信網(wǎng)絡(luò)G=(V，E)，結(jié)合定義1，有如下的結(jié)論成立。

2.3 變信息率線性網(wǎng)絡(luò)編碼的構(gòu)造

對任一單信源，變信息率通信網(wǎng)絡(luò)G=(V，E)，設(shè)其信息率為r1＞r2＞…＞rM，通信網(wǎng)絡(luò)G=(V，E)的傳輸矩陣記為T=K(I－F)－1。對網(wǎng)絡(luò)中的任意的節(jié)點v，其入邊集ΓI(v)中的邊所對應(yīng)的全局網(wǎng)絡(luò)編碼核與全局傳輸矩陣T=K(I－F)－1中的部分列向量相對應(yīng)?？傻霉?jié)點v∈V的局部傳輸矩陣為

易知，如圖1所示的變信息率通信網(wǎng)絡(luò)中的非源節(jié)點v1，...，v5，u的局部傳輸矩陣分別為

顯然，使用(28)式所示的局部傳輸矩陣，信源發(fā)送一個消息數(shù)據(jù)組x1時，網(wǎng)絡(luò)中所有非源節(jié)點均可獲得x1;當(dāng)信源發(fā)送2個消息分組x1，x2時，節(jié)點v2，v4，u 能獲得 x1，x2;信源發(fā)送分組為 x1，x2，x3時，節(jié)點u能獲得x1，x2，x3。由此，可得關(guān)于變信息率線性網(wǎng)絡(luò)編碼構(gòu)造的一般性結(jié)論。

定理2 對于一個有向、單信源無圈變信息率網(wǎng)絡(luò)G=(V，E)，可能的信息率為r1＞r2＞…＞rM。如上，任一非源節(jié)點v∈V{s}的局部傳輸矩陣為T(v)，信源s到節(jié)點 v的最大流為 maxflow(s，v)，記T(v)的前maxflow(s，v)行構(gòu)成的矩陣為(v)。若對任意的非源節(jié)點v∈V{s}，有r1維線性網(wǎng)絡(luò)編碼使得

成立，則此網(wǎng)絡(luò)編碼能實現(xiàn)變信息率網(wǎng)絡(luò)的有效通信。

每周二下午的社團(tuán)課，岳舒愷老師都會帶領(lǐng)社團(tuán)的小“刀客”們走進(jìn)篆刻的世界。從簡單、有趣的肖形?。ㄐは衲撤N物體形狀的印章，只有圖像，沒有文字）開始，鍛煉孩子們手上的刀功，刻出平穩(wěn)均勻的直線；有趣的卡通形象和深厚的傳統(tǒng)文化碰撞在一起，讓孩子們產(chǎn)生了濃厚的興趣。

定理2從局部傳輸矩陣出發(fā)，給出了實現(xiàn)變信息率網(wǎng)絡(luò)有效通信的線性網(wǎng)絡(luò)編碼應(yīng)滿足的條件，而沒有說明此線性網(wǎng)絡(luò)編碼是否存在，下面給出此類線性網(wǎng)絡(luò)編碼存在的條件。

定理3 對于一個有向、單信源無圈變信息率網(wǎng)絡(luò)G=(V，E)，可能的信息率為r1＞r2＞…＞rM。充當(dāng)字母表的有限域Fq滿足條件|Fq|＞r1(|V|－1)時，則變信息率網(wǎng)絡(luò)中一定存在滿足定理2中式(29)的變信息率線性網(wǎng)絡(luò)編碼。

定理2和定理3給出了在變信息率網(wǎng)絡(luò)中構(gòu)造實現(xiàn)有效通信的線性網(wǎng)絡(luò)編碼的條件和方法。根據(jù)所得到的結(jié)論，下面給出一個尋找變信息率線性網(wǎng)絡(luò)編碼的簡單算法。

3 鏈路故障網(wǎng)絡(luò)中變信息率網(wǎng)絡(luò)編碼的構(gòu)造

上文討論了怎樣在拓?fù)浣Y(jié)構(gòu)確定的變信息率廣播網(wǎng)絡(luò)中實現(xiàn)有效通信。但是，在現(xiàn)實的生活中，網(wǎng)絡(luò)中的數(shù)據(jù)傳輸會發(fā)生擁塞，鏈路也會發(fā)生故障，從而導(dǎo)致鏈路無法正常工作。由此可知，網(wǎng)絡(luò)中的鏈路狀態(tài)是隨時間而改變的。鏈路故障對網(wǎng)絡(luò)通信的危害極大，既可導(dǎo)致網(wǎng)絡(luò)無法通信，也可使得數(shù)據(jù)大量的丟失。因此，怎樣在有鏈路故障的變信息率網(wǎng)絡(luò)中實現(xiàn)有效通信是一個更加現(xiàn)實的問題。

對于鏈路會發(fā)生故障的變信息率線性廣播網(wǎng)絡(luò)G=(V，E)，定義信道集 E到{0，1}的映射 ε。對任意的信道e∈E，ε(e)=1表示信道e可以正常使用，而ε(e)=0表示信道e發(fā)生了故障。這樣，映射ε對應(yīng)了網(wǎng)絡(luò)G=(V，E)的一個新的構(gòu)造，記新得到的網(wǎng)絡(luò)為Gε。相應(yīng)的，對于任意的信道e，全局網(wǎng)絡(luò)編碼核記為。網(wǎng)絡(luò)Gε中的信源s到各非源節(jié)點v的最大流記為 maxflowε(s，v)。

和上文中一樣，在單信源無圈變信息率通信網(wǎng)絡(luò)G=(V，E)中，信源s的M個互不相同的信息率記為r1＞r2＞…＞rM，且存在一非源節(jié)點v∈V{s}，使得maxflow(s，v)≥r1。下面，考慮怎樣在有鏈路故障的網(wǎng)絡(luò)中實現(xiàn)有效的通信。即要構(gòu)造合適的線性網(wǎng)絡(luò)編碼，對于可能的構(gòu)造ε和任意的非源節(jié)點v，若信源的信息率 ri≤maxflowε(s，v)，則要求節(jié)點 v能恢復(fù)信源發(fā)送的消息分組x1，…，xri。使用和上文相似的方法，可以構(gòu)造有效的線性網(wǎng)絡(luò)編碼來實現(xiàn)有鏈路故障的變信息率網(wǎng)絡(luò)的有效通信。此類線性網(wǎng)絡(luò)編碼應(yīng)滿足的條件如下。

注意到定理4和定理2的證明類似，實際上，定理2只是對任意的e∈E，有ε(e)=1的情形進(jìn)行了證明。

與定理3類似，只要充當(dāng)網(wǎng)絡(luò)編碼字母表的有限域Fq足夠的大，此類線性網(wǎng)絡(luò)編碼存在，具體如下。

定理5 在有向單信源，有鏈路故障變信息率網(wǎng)絡(luò)G=(V，E)中，可能的信息率為r1＞r2＞… ＞rM。網(wǎng)絡(luò)的構(gòu)造共有ω種，則充當(dāng)網(wǎng)絡(luò)編碼字母表的有限域Fq的基數(shù)|Fq|＞ωr1(|V|－1)時，有鏈路故障的變信息率網(wǎng)絡(luò)中一定存在滿足式(31)的r1維線性網(wǎng)絡(luò)編碼。

在鏈路會發(fā)生故障的通信網(wǎng)絡(luò)中，同樣可以使用算法1獲得變信息率線性網(wǎng)絡(luò)編碼，只是要求有限域Fq更大。同時，由定理4和定理5可知，使用此處給出的方法所構(gòu)造出的變信息率線性網(wǎng)絡(luò)編碼可以有效應(yīng)對網(wǎng)絡(luò)中的鏈路故障，使得網(wǎng)絡(luò)擁有良好的穩(wěn)健性。

4 結(jié)束語

長久以來，變信息率網(wǎng)絡(luò)的有效通信問題一直受到人們的關(guān)注，該文從全局角度研究了變信息率網(wǎng)絡(luò)中的數(shù)據(jù)傳輸，構(gòu)造了變信息率線性網(wǎng)絡(luò)編碼，并得到了全局傳輸矩陣和局部傳輸矩陣。然后使用代數(shù)學(xué)方法對全局傳輸矩陣和局部傳輸矩陣進(jìn)行了分析，由此獲得了實現(xiàn)變信息率網(wǎng)絡(luò)有效通信的局部網(wǎng)絡(luò)編碼核和全局網(wǎng)絡(luò)編碼核應(yīng)滿足的條件。而且，該方法還適用于鏈路會發(fā)生故障的變信息率網(wǎng)絡(luò)，結(jié)論表明，使用此方法構(gòu)造出的線性網(wǎng)絡(luò)編碼能適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的變信息率網(wǎng)絡(luò)，從而提高網(wǎng)絡(luò)的穩(wěn)健性。與已有的方法相比，該文提出的方法不要求網(wǎng)絡(luò)節(jié)點存儲多個信息率對應(yīng)的局部網(wǎng)絡(luò)編碼核，也無需對不同信息率進(jìn)行迭代計算來獲得相應(yīng)的網(wǎng)絡(luò)編碼。

［1］YEUNG RW，ZHANG Z.Distributed Source Coding for Satellite Communication［J］.IEEE Transaction on Infor mation Theory，1999，45(4):1111－1120.

［2］AHLSWEDE R，CAIN，LISY R.Network Information flow［J］.IEEE Transaction on Information Theory，2000，46(4):1204－1216.

［3］LISY R，CAIN.Linear Network Coding［J］.IEEE Transaction on Information Theory，2003，49(2):371－381.

［4］KOETTER R，MEDARD M.An Algebraic Approach to Network Coding［J］.IEEE/ACM Transaction on Networking，2003，11(5):782－795.

［5］HO T，MEDARD M，KOETTER R，et al.A Random Linear Network Coding Approach to Multicast［J］.IEEE Transaction on Information Theory，2006，52(10):4413－4430.

［6］HARSINI J，MICHELE Z.Effictive Capacity for Multi－Rate Relay Channels with delay Constraint Exploiting A－daptive Cooperativer Diversity［J］.IEEE Transaction on Wireless Communication，2012，11(9):3136－3147.

［7］JAGGIS，SANDERS P，CHOU P A.Polynomial Time Algorithms for Multicast Network Code Construction［J］.IEEE Transaction on Information Theory，2005，51(6):1973－1982.

［8］FONG S L，YEUNG RW.Variable－rate Linear Network Coding［C］//IEEE Information Theory workshop(IEEE ITW).USA:Conference Publications，2006:409－412.

［9］FONG S L，YEUNG RW.Variable－rate Linear Network Coding［J］.IEEE Transaction on Information Theory，2010，56(6):2618－2625.

［10］GOSELING J，WEBER J H.Multi－rate network coding for minimum－cost multicasting［C］//IEEE International Sy－mposium on Information Theory(ISIT).USA:Conference Publications，2008:36－40.

［11］LAKSHMINARAYANA S，ERYILMAZA.Multirate Multicasting with Intralayer Network Coding［J］.IEEE/ACM Transaction on Networking，2013，21(4)1256－1269.

［12］HUANG Meng，F(xiàn)ENG Gang，ZHANG Yide.Network Coding with Relay Assistance in Multi－rate Wireless Networks［C］//IEEE 6th International ICST Conference on Cmmunications and Networking in China(CHINACOM).USA:Conference Publications，2011:1120－1125.

［13］WANG Fanzhao，WANG Shiqiang，SONG Qingyang.A－daptive Relaying Method Selection for Multi－Rate Wireless Networks with Network Coding［J］.IEEE Communications Letters，2012，16(12):2004－2007.

［14］MAR C H，KONG P Y.Cooperative MAC Relaying with Multi－Rate Transmissions and Network Coding［C］//IEEE Wireless Communication and Networking Conference(WCNC).USA:Conference Publications，2012:1602－1607.

［15］王練，雷芳.基于網(wǎng)絡(luò)編碼的無線重傳方案綜述［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2012，24(5):664－668.

WANG Lian，LEI Fang.Survey of Network Code Retransmission in Wireless Network［J］. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2012，24(5):664－668.

(編輯:田海江)