曹張華，吉曉東，劉 敏

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

0 引言

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

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

1 基本概念

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

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

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

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

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

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

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

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

2.1 基本思想

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

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

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

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

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

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

2.2 傳輸矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

［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)絡編碼的無線重傳方案綜述［J］.重慶郵電大學學報:自然科學版，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.

(編輯:田海江)