雙單播網(wǎng)絡(luò)編碼的構(gòu)造方法

蒲保興，莫智懿

（梧州學(xué)院大數(shù)據(jù)與軟件工程學(xué)院，廣西 梧州 543002）

1 引言

單源網(wǎng)絡(luò)編碼[1-3]已經(jīng)得到了深入廣泛的研究，并獲得了較好的研究成果。對于多源網(wǎng)絡(luò)編碼[4]而言，盡管其已被學(xué)術(shù)界長期關(guān)注并被持續(xù)地研究，但仍沒有獲得突破性的進(jìn)展。雖然多源網(wǎng)絡(luò)編碼是一個相當(dāng)困難的問題，但多單播網(wǎng)絡(luò)編碼[5]是多源網(wǎng)絡(luò)編碼中一種比較容易的情形。文獻(xiàn)[6]的研究表明，任意一個多源有向無環(huán)網(wǎng)絡(luò)必定存在一個相應(yīng)的多單播網(wǎng)絡(luò)，兩者具有等價的網(wǎng)絡(luò)編碼可解性。即如果在其中一個網(wǎng)絡(luò)上存在可行的線性網(wǎng)絡(luò)編碼傳輸方案，則在另一個網(wǎng)絡(luò)上必定存在相應(yīng)的可行線性的網(wǎng)絡(luò)編碼傳輸方案。因此，研究多單播網(wǎng)絡(luò)編碼不僅是網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于多單播網(wǎng)絡(luò)的需要，也是解決一般多源網(wǎng)絡(luò)編碼問題的有效途徑。據(jù)此，學(xué)術(shù)界的研究重點(diǎn)已轉(zhuǎn)移到了多單播網(wǎng)絡(luò)編碼的層面上。在多單播網(wǎng)絡(luò)編碼中，最簡單的情形是雙單播網(wǎng)絡(luò)編碼[7-9]。在已有的研究中，許多學(xué)者試圖運(yùn)用信息論技術(shù)及圖論的工具來探索雙單播網(wǎng)絡(luò)編碼的可達(dá)信息率區(qū)域。文獻(xiàn)[10]的研究表明，2個嵌套信息的容量區(qū)域是可以描述的，這2個信息中一個被稱為公有消息，另一個被稱為私有消息，其中，公有消息可擁有3個接收者，私有消息可擁有無數(shù)個接收者。文獻(xiàn)[11]的研究表明，關(guān)于信息的描述，線性網(wǎng)絡(luò)編碼對多源網(wǎng)絡(luò)是不充分的。文獻(xiàn)[12]推導(dǎo)了雙單播網(wǎng)絡(luò)在實(shí)現(xiàn)發(fā)送速率向量(1,1)的充要條件。文獻(xiàn)[13]提出了雙單播網(wǎng)絡(luò)的廣義網(wǎng)絡(luò)共享界（generalized network sharing outer bound）。文獻(xiàn)[14]分析了廣義的網(wǎng)絡(luò)共享界在某些特殊的雙單播網(wǎng)絡(luò)中的緊致性。文獻(xiàn)[15]和文獻(xiàn)[16]針對雙單播網(wǎng)絡(luò)編碼的廣義網(wǎng)絡(luò)共享界分別給出了代數(shù)解析和網(wǎng)絡(luò)級聯(lián)解析。但文獻(xiàn)[7]已經(jīng)證明，求解多單播網(wǎng)絡(luò)編碼的可達(dá)信息率區(qū)域是一個NPC問題（non-deterministic polynomial complete problem），即使求解最簡單的雙單播網(wǎng)絡(luò)編碼，也是NPC問題。該文還表明，雙單播網(wǎng)絡(luò)編碼并不比k（k>2，k是網(wǎng)絡(luò)中存在的源-宿對的數(shù)目）單播網(wǎng)絡(luò)編碼來得容易，即雙單播網(wǎng)絡(luò)編碼完全體現(xiàn)了多單播網(wǎng)絡(luò)編碼的困難度。在實(shí)際應(yīng)用中，一方面，需要對雙單播網(wǎng)絡(luò)編碼進(jìn)行求解，另一方面，求出其精確解又是一個NPC問題，從而探索出近似的、較優(yōu)的可行解技術(shù)是解決這一問題的有效途徑。

已有的研究盡管關(guān)注雙單播網(wǎng)絡(luò)編碼的可達(dá)信息率區(qū)域的計算，但忽略了網(wǎng)絡(luò)編碼的構(gòu)造。由于多源問題的困難性，即使運(yùn)用信息論或圖論的相關(guān)技術(shù)能求出近似的可達(dá)信息率區(qū)域，但針對可達(dá)信息率區(qū)域中的某一個點(diǎn)（即選定一個特定可行的源點(diǎn)數(shù)據(jù)發(fā)送速率向量），構(gòu)造相應(yīng)的可行的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案仍然相當(dāng)困難。換句話說，若僅估算出了可達(dá)信息率區(qū)域，針對該區(qū)域中的二維向量仍然難以構(gòu)造相應(yīng)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。這與單源網(wǎng)絡(luò)編碼完全不同，對于單源網(wǎng)絡(luò)編碼而言，只要源點(diǎn)的數(shù)據(jù)發(fā)送速率不超過最大流-最小割界，則存在有效的算法來構(gòu)造可行的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。其主要原因是單源網(wǎng)絡(luò)編碼只有一個源點(diǎn)，不存在消息干擾；但對于具有多個源點(diǎn)的網(wǎng)絡(luò)而言，宿點(diǎn)接收到的信息是各源點(diǎn)消息的線性組合，即存在消息干擾。若只求出了近似的可達(dá)信息率區(qū)域，而沒有給出構(gòu)造傳輸方案的方法，則該方法僅有理論價值，沒有實(shí)際應(yīng)用的價值。因此，從實(shí)際應(yīng)用的角度出發(fā)，應(yīng)該把這2個問題給合起來進(jìn)行研究，不僅要給出近似的可達(dá)信息率區(qū)域，還要給出可達(dá)信息率區(qū)域中各發(fā)送速率向量對應(yīng)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。

解決雙單播網(wǎng)絡(luò)編碼問題的關(guān)鍵是讓宿點(diǎn)消除干擾，文獻(xiàn)[9]運(yùn)用源點(diǎn)預(yù)編碼策略作用于雙單播網(wǎng)絡(luò)的信息不等式提出了求解雙單播網(wǎng)絡(luò)編碼近似可達(dá)信息率區(qū)域的方法，但該方法僅對文獻(xiàn)[17]提出的雙單播網(wǎng)絡(luò)的可達(dá)信息率區(qū)域所滿足的信息不等式實(shí)現(xiàn)了可計算化，未涉及網(wǎng)絡(luò)編碼的構(gòu)造。

本文的貢獻(xiàn)如下?；谖墨I(xiàn)[9]的思想，即在源點(diǎn)進(jìn)行預(yù)編碼，使宿點(diǎn)接收到的全局編碼矩陣的某些列強(qiáng)迫為全零列，把文獻(xiàn)[18]提出的線性網(wǎng)絡(luò)編碼的導(dǎo)出技術(shù)由單源情形擴(kuò)展到了雙單播網(wǎng)絡(luò)情形，并從源點(diǎn)預(yù)編碼和信息熵的角度嚴(yán)格證明了導(dǎo)出技術(shù)的正確性。在此基礎(chǔ)上，本文采用多目標(biāo)優(yōu)化進(jìn)化算法并結(jié)合隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)來形成傳輸方案，提出了選擇預(yù)編碼矩陣的策略：用宿點(diǎn)的信息轉(zhuǎn)換矩陣的零向量空間的基向量和行向量空間的基向量共同來確定預(yù)編碼矩陣的列向量，從而使宿點(diǎn)的全局編碼矩陣的某些列變?yōu)槿懔?，在宿點(diǎn)消除了部分信息干擾。根據(jù)雙單播情形下的網(wǎng)絡(luò)編碼的導(dǎo)出技術(shù)，運(yùn)用二級預(yù)編碼策略來控制源點(diǎn)的發(fā)送速率。結(jié)合以上策略，本文提出了雙單播網(wǎng)絡(luò)編碼的構(gòu)造方法。所提方法不僅能求出雙單播網(wǎng)絡(luò)編碼的近似可達(dá)的信息率區(qū)域，同時針對求出的可達(dá)信息率區(qū)域中的任何一個整數(shù)坐標(biāo)點(diǎn)，還提供了構(gòu)造可行的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案的具體方法。

2 預(yù)備知識

雙單播網(wǎng)絡(luò)編碼[8]。在一個有向無環(huán)網(wǎng)絡(luò)G=(V,E)中，V為節(jié)點(diǎn)集，E為有向邊集。假設(shè)網(wǎng)絡(luò)中有向邊的容量為整數(shù)，單位容量的有向邊稱為信道，若有向邊的容量大于1，則被看作多條單位容量的信道。網(wǎng)絡(luò)中有2個源點(diǎn){s1,s2}?V，2個宿點(diǎn){t1,t2}?V，宿點(diǎn)ti(i=1,2)只需要接收來自源點(diǎn)si的信息，在數(shù)據(jù)傳輸過程中共享網(wǎng)絡(luò)的傳輸資源，網(wǎng)絡(luò)的中間節(jié)點(diǎn)運(yùn)用網(wǎng)絡(luò)編碼技術(shù)來轉(zhuǎn)發(fā)數(shù)據(jù)。雙單播網(wǎng)絡(luò)編碼如圖1所示，其中，Xi(i=1,2)表示源點(diǎn)si發(fā)送的字符向量，Yi=M1iX1+M2iX2表示宿點(diǎn)ti接收到的字符向量，其具體的含義見后續(xù)的說明。

圖1 雙單播網(wǎng)絡(luò)編碼

網(wǎng)絡(luò)編碼的工作機(jī)理[1]如下。選定有限域GF(q)（其中q為2的冪），在一次數(shù)據(jù)傳輸過程中，源點(diǎn)s1發(fā)送了有限域GF(q)中的u個字符至網(wǎng)絡(luò)，這u個字符形成一個字符向量，記為X1，如式(1)所示。

源點(diǎn)s2發(fā)送有限域GF(q)中的v個的字符至網(wǎng)絡(luò)，這v個字符形成一個字符向量，記為X2，如式(2)所示。

把2個源點(diǎn)發(fā)送的字符看作一個u+v維的列向量，如式(3)所示。

為了描述方便，本文認(rèn)為源點(diǎn)s1發(fā)送的u個字符由源點(diǎn)s1的u條虛擬輸入信道分別輸入；源點(diǎn)s2發(fā)送的v個字符由源點(diǎn)s2的v條虛擬輸入信道分別輸入。由此可知每一個節(jié)點(diǎn)（包括源點(diǎn)）均具有輸入信道，如圖1所示。在數(shù)據(jù)傳輸過程中，各中間節(jié)點(diǎn)（不包括宿點(diǎn)）把從其輸入信道接收到的字符經(jīng)線性組合后再轉(zhuǎn)發(fā)至該節(jié)點(diǎn)的輸出信道。對于每一條信道ei∈E（記信道的尾節(jié)點(diǎn)tail(ei)=k，信道的頭節(jié)點(diǎn)head(ei)=l，其中，k,l∈V），該信道上傳輸?shù)淖址洖椋瑒t根據(jù)文獻(xiàn)[1]，通過式(4)計算，稱為信道ei的局部編碼向量。

定義1對于雙單播網(wǎng)絡(luò)編碼，所有節(jié)點(diǎn)的輸出信道的局部編碼向量組成一個集合，稱為網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。

在本文中，網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案用符號θ表示，為了敘述簡潔，簡稱為“傳輸方案θ”。

由于有向無環(huán)圖的拓?fù)涮卣鳎凑站W(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)漤樞?，?jié)點(diǎn)輸出信道傳輸?shù)淖址词?4)進(jìn)行遞歸與迭代運(yùn)算，則每一信道所傳輸?shù)淖址囟鼙硎境稍袋c(diǎn)所發(fā)送的信息字符的線性組合，如式(5)所示。

其向量形式如式(6)所示。

其中，X是源點(diǎn)發(fā)送的字符向量，如式(3)所示。稱為信道ei的全局編碼向量。對于網(wǎng)絡(luò)中的任意一個節(jié)點(diǎn)，把其每一條輸入信道的全局編碼向量作為矩陣的一行，形成一個矩陣，則這個矩陣為該節(jié)點(diǎn)的全局編碼矩陣。

由前文可知，式(5)或式(6)描述了信道ei傳輸?shù)淖址?、信道的全局編碼向量和源點(diǎn)發(fā)送的字符向量X三者之間的數(shù)學(xué)關(guān)系。類似于計算信道傳輸?shù)淖址?，信道的全局編碼向量可以按式(7)進(jìn)行計算。

如果采用隨機(jī)線性網(wǎng)絡(luò)編碼方法傳輸數(shù)據(jù)，則信道ei傳輸?shù)男畔▋煞矫娴膬?nèi)容：信道傳輸?shù)淖址托诺赖娜志幋a向量，它們分別通過式(4)和式(7)進(jìn)行計算。

在按式(4)和式(7)所示的遞歸與迭代計算過程中，根據(jù)網(wǎng)絡(luò)的拓?fù)漤樞?，首先需要計算源點(diǎn)輸出信道的全局編碼向量和傳輸?shù)淖址袋c(diǎn)s1的u條虛擬輸入信道攜帶的字符分別為x11,x12,…,x1u，則它們的全局編碼向量分別為u+v維的單位向量，其中第i(i=1,2,…,u)條虛擬輸入信道的全局編碼向量的第i個分量為1，其余分量為0。則源點(diǎn)s1的全局編碼矩陣為(Iu×u0u×v)，其中，Iu×u是u階的單位矩陣，0u×v是u行v列的零矩陣。

同理，源點(diǎn)s2的全局編碼矩陣為(0v×uIv×v)。

對于某一個宿點(diǎn)ti，選定δi條輸入信道，根據(jù)式(6)的對應(yīng)關(guān)系，把輸入信道的全局編碼向量、信道傳輸?shù)淖址?、源點(diǎn)發(fā)送的字符進(jìn)行關(guān)聯(lián)，將形成一個線性方程組。宿點(diǎn)ti的δi條輸入信道的全局編碼矩陣的分塊矩陣形式為(Mi1M2i)，宿點(diǎn)ti的δi條輸入信道所傳輸?shù)淖址纬傻南蛄繛閅i，則Yi可以通過式(8)進(jìn)行計算。

其中，Yi是一個δi維的列向量；(Mi1Mi2)是一個δi行u+v列的矩陣，M1i是源點(diǎn)s1的虛擬輸入信道至宿點(diǎn)ti的消息轉(zhuǎn)換矩陣，M2i是源點(diǎn)s2的虛擬輸入信道至宿點(diǎn)ti的消息轉(zhuǎn)換矩陣。Yi、M1i和M2i中的元素均為有限域GF(q)中的字符。

如前所述，由于源點(diǎn)s1的全局編碼矩陣為(Iu×u0u×v)，源點(diǎn)s2的虛擬輸入信道的全局編碼矩陣為(0v×uIv×v)，在傳輸方案θ指引下，各信道的全局編碼向量按式(7)進(jìn)行計算。注意到，式(7)與式(4)的形式相同，式(7)是在式(4)的基礎(chǔ)上把信道上傳輸?shù)淖址鹹ej換成信道的全局編碼向量，從而宿點(diǎn)ti的全局編碼矩陣的計算為

這就表明，分別按式(4)和式(7)計算信道攜帶的字符和全局編碼向量能夠滿足式(5)的對應(yīng)關(guān)系，因此可得式(8)即為宿點(diǎn)ti所析出的線性方程組。

性質(zhì)1選擇雙單播網(wǎng)絡(luò)的傳輸方案θ，則宿點(diǎn)ti(i=1,2)的全局編碼矩陣(M1iM2i)由傳輸方案θ唯一確定。

采用網(wǎng)絡(luò)編碼技術(shù)傳輸數(shù)據(jù)必須要構(gòu)造網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案θ，即確定各信道的局部編碼向量，也稱為網(wǎng)絡(luò)編碼構(gòu)造。構(gòu)造傳輸方案包括2個任務(wù)：首先要確定源點(diǎn)的數(shù)據(jù)發(fā)送速率，然后針對選定的源點(diǎn)數(shù)據(jù)發(fā)送速率來確定各信道的局部編碼向量。對于雙單播網(wǎng)絡(luò)，因有2個源點(diǎn)，2個源點(diǎn)的數(shù)據(jù)發(fā)送速率形成了一個二維向量，稱之為源點(diǎn)數(shù)據(jù)發(fā)送速率向量。選定了源點(diǎn)數(shù)據(jù)發(fā)送速率向量后，接下來的任務(wù)是如何確定傳輸方案θ，按照傳輸方案θ中指定的局部編碼向量進(jìn)行數(shù)據(jù)傳輸后，使宿點(diǎn)能夠通過求解線性方程組來恢復(fù)源點(diǎn)發(fā)送的消息。

定義2針對雙單播網(wǎng)絡(luò)，對于給定的源點(diǎn)數(shù)據(jù)發(fā)送速率向量(u,v)，若存在相應(yīng)的傳輸方案，使宿點(diǎn)通過解碼能獲得所需的消息，則稱(u,v)是可達(dá)的，該傳輸方案是可行的，所有可達(dá)的源點(diǎn)數(shù)據(jù)發(fā)送速率向量組成的集合稱為可達(dá)信息率區(qū)域[4]。

解決雙單播網(wǎng)絡(luò)編碼的構(gòu)造問題首先需要確定可達(dá)信息率區(qū)域，然后針對可達(dá)信息率區(qū)域中的每一點(diǎn)，再構(gòu)造相應(yīng)的可行的傳輸方案。因?yàn)榇嬖趕1—t1和s2—t2這2個會話，它們共享網(wǎng)絡(luò)資源，形成了一種競爭的態(tài)勢，從而求解雙單播網(wǎng)絡(luò)編碼的可達(dá)信息率區(qū)域的問題是一個雙目標(biāo)優(yōu)化問題，可達(dá)信息率區(qū)域是雙目標(biāo)優(yōu)化問題的Pareto集。

設(shè)源點(diǎn)si至宿點(diǎn)ti的最大流為min-cut(si,ti)（i=1,2），記k1-1=min-cut(s1,t1)，k2-2=min-cut(s2,t2)。記{s1,s2}至t1的最大流為k12-1,｛s1,s2｝至t2的最大流為k12-2。由最大流最小割定理，可限制源點(diǎn)s1的數(shù)據(jù)發(fā)送速率的取值范圍為[0,k1-1]。同理，可限制源點(diǎn)s2的數(shù)據(jù)發(fā)送速率的取值范圍為[0,k2-2]。本文只考慮源點(diǎn)發(fā)送速率為整數(shù)的情況。

本文采用以下策略來尋求可達(dá)信息率區(qū)域：選定(u,v)∈([0,k1-1]×[0,k2-2])，其中，u和v均為整數(shù)。針對源點(diǎn)數(shù)據(jù)發(fā)送率向量(u,v)尋找可行的數(shù)據(jù)傳輸方案，如能找到，則(u,v)是可達(dá)的，記下相應(yīng)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。對所有(u,v)∈([0,k1-1]×[0,k2-2])進(jìn)行判斷，則可以獲得可達(dá)信息率區(qū)域。

宿點(diǎn)需要通過解碼獲得源點(diǎn)發(fā)送的消息，則必須求解式(8)所示的線性方程組。將式(8)表示為AX=B的形式，其中系數(shù)矩陣A=(M1iM2i)為m行n列矩陣，n=u+v。

若系數(shù)矩陣A中某一列的元素全為零，則稱之為全零列，表明該列對應(yīng)的未知量不存在，其含義為該列所對應(yīng)的由源點(diǎn)發(fā)送的字符沒有傳輸至宿點(diǎn)，只有系數(shù)矩陣的非全零列才對應(yīng)一個未知量。關(guān)于線性方程組求解，文獻(xiàn)[20]給出了如下定理。

定理1記rank(A)為矩陣A的秩，對于線性方程組AX=B，若系數(shù)矩陣不存在全零列，則線性方程組有解的充要條件為rank(A)等于系數(shù)矩陣的列數(shù)。

針對系數(shù)矩陣存在全零列的情況，有如下推論。

推論1對于線性方程組AX=B，記π(A)為矩陣A中非全零列的列數(shù)，則線性方程組有解的充要條件為rank(A)=π(A)。

推論1的成立是明顯的，因?yàn)橹灰サ粝禂?shù)矩陣的全零列，同時去掉全零列所對應(yīng)的未知量，則可以滿足定理1的條件。

下面，敘述矩陣的行空間與零空間的概念[20]。矩陣A的列空間就是由矩陣A的列向量所張成的m維向量空間的一個線性子空間，記為R(A)；矩陣A的行空間就是由矩陣A的所有行向量所張成的n維向量空間的一個線性子空間，記為R(AT)。

矩陣A的零空間是由齊次線性方程組AX=0的所有解張成的n維向量空間的一個線性子空間，記為N(A)。由零空間的定義可得，對于任意的y∈N(A)，滿足AY=0。

根據(jù)線性代數(shù)的理論可知，矩陣A的行空間與零空間互為正交補(bǔ)，矩陣A的行空間與零空間的和構(gòu)成了n維的向量空間。

3 源點(diǎn)預(yù)編碼技術(shù)及網(wǎng)絡(luò)編碼的導(dǎo)出

3.1 源點(diǎn)的預(yù)編碼

如圖1所示，選擇傳輸方案θ，宿點(diǎn)t1選定其k12-1條輸入信道，宿點(diǎn)t2選定其k12-2條輸入信道（即根據(jù)式(8)可知，宿點(diǎn)t1和t2對應(yīng)的線性方程組分別為

如前所述，Mij(i,j=1,2)是源點(diǎn)i至宿點(diǎn)j的信息轉(zhuǎn)換矩陣。其中，M11是k12-1行u列矩陣，M21是k12-1行v列矩陣。M12是k12-2行u列矩陣，M22是k12-2行v列矩陣，Y1和Y2分別是k12-1維和k12-2維的列向量。由性質(zhì)1，Mij(i,j=1,2)由傳輸方案θ唯一確定。

傳輸方案θ中是在源點(diǎn)實(shí)施預(yù)編碼。源點(diǎn)的預(yù)編碼不是直接把消息字符分別注入源點(diǎn)的虛擬輸入信道，而是把消息字符經(jīng)過線性組合后再分別注入源點(diǎn)的虛擬輸入信道，如圖2所示。

圖2 雙單播網(wǎng)絡(luò)編碼的源點(diǎn)預(yù)編碼

對于源點(diǎn)s1，假設(shè)要傳輸?shù)南⒆址蛄咳缡?1)所示，先對這u個字符進(jìn)行預(yù)編碼，其編碼方式如下。

其中，U表示一個u階方陣，每一個系數(shù)均為有限域GF(q)的元素，也稱為預(yù)編碼矩陣。

同理，可以在源點(diǎn)s2實(shí)施預(yù)編碼，設(shè)預(yù)編碼矩陣為v階方陣V，經(jīng)預(yù)編碼后形成的字符向量如式(12)所示。

3.2 網(wǎng)絡(luò)編碼的導(dǎo)出

文獻(xiàn)[18]提出了單源多播網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼的導(dǎo)出與擴(kuò)展技術(shù)，本文利用源點(diǎn)的預(yù)編碼技術(shù)提出雙單播網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼的導(dǎo)出技術(shù)。

定義3若u,v,u1,v1均為整數(shù)，且滿足u1≤u，v1≤v，則稱(u1,v1)受控于(u,v)，也稱(u,v)控制(u1,v1)，記為(u1,v1)?(u,v)。

定義4對于雙單播網(wǎng)絡(luò)的一個源點(diǎn)發(fā)送速率向量為(u,v)的傳輸方案，在源點(diǎn)s1和s2分別實(shí)施式(11)和式(12)所示的預(yù)編碼，則從傳輸方案θ中導(dǎo)出了一個新的傳輸方案，本文稱前者為原始方案，后者為導(dǎo)出方案。

定理2線性網(wǎng)絡(luò)編碼的導(dǎo)出。若一個雙單播網(wǎng)絡(luò)編碼的源點(diǎn)發(fā)送率向量(u,v)是可達(dá)的，則對于任意(u1,v1)，且(u1,v1) ?(u,v)，(u1,v1)也是可達(dá)的，且從源點(diǎn)可達(dá)的發(fā)送速率向量(u,v)的任何一個可行的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案可以導(dǎo)出(u1,v1)的一個可行的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。

證明由于(u,v)是可達(dá)的，必存在一個可行的傳輸方案θ。在其指引下，宿點(diǎn)t1和t2對應(yīng)的線性方程組分別如式(9)和式(10)所示。在此基礎(chǔ)上，分別對源點(diǎn)s1和s2實(shí)施如式(11)和式(12)所示的預(yù)編碼，預(yù)編碼矩陣U和V表示如下。

則宿點(diǎn)t1和t2分別得到如式(13)與式(14)所示的線性方程組。由于θ是關(guān)于(u,v)的一個可行傳輸方案，則式(9)和式(10)能解出X1和X2。

比較式(9)和式(13)所代表的線性方程組，兩者具有相同的系數(shù)矩陣，只是未知量與常數(shù)項(xiàng)不同，由推論1，則式(9)和式(13)代表的線性方程組具有相同的可解性，同理，式(10)與式(14)表示的線性方程組也具有相同的可解性。因此，式(13)和式(14)能解出這說明了源點(diǎn)s1實(shí)際上僅向網(wǎng)絡(luò)傳輸了字符向量且宿點(diǎn)t1能解碼出同理，源點(diǎn)s2實(shí)際上僅向網(wǎng)絡(luò)傳輸了字符向量且宿點(diǎn)t2可以解碼出由此說明，源點(diǎn)發(fā)送速率向量(u1,v1)是可達(dá)的，而且通過源點(diǎn)的預(yù)編碼，可從可達(dá)信息率向量(u,v)的一個可行的傳輸方案θ導(dǎo)出關(guān)于(u1,v1)的一個可行的傳輸方案，且導(dǎo)出的傳輸方案僅在源點(diǎn)實(shí)施預(yù)編碼，其余信道的局部編碼向量與傳輸方案θ相同。證畢。

假設(shè)源點(diǎn)產(chǎn)生的消息字符是隨機(jī)變量，且相互獨(dú)立，每個字符均勻地在有限域GF(q)上選取，若向量X1的維數(shù)為u、向量X2的維數(shù)為v，根據(jù)信息論可知，H(X1)=uq，H(X2)=vq（注：H(·)表示隨機(jī)變量的香農(nóng)信息熵，I(·;·)表示2個隨機(jī)變量的互熵）。

定理3對于一個源點(diǎn)的發(fā)送速率向量為(u,v)的可行傳輸方案，可以導(dǎo)出一個源點(diǎn)發(fā)送速率向量為(u1,v1)的可行傳輸方案，其中(u1,v1)?(u,v)。導(dǎo)出的傳輸方案只需在源點(diǎn)實(shí)施預(yù)編碼，其他信道的局部編碼向量保持不變，且源點(diǎn)s1的預(yù)編碼矩陣U為u階方陣，U的后u～u1列均為全零列，且滿足rank(U1)=u1；由對稱性，源點(diǎn)s2的預(yù)編碼矩陣V為v階方陣，V的后v～v1列均為全零列，且滿足rank(V)=v1。

證明源點(diǎn)經(jīng)過預(yù)編碼后，2個源點(diǎn)實(shí)際上是分別把傳送到網(wǎng)絡(luò)中，首先證明經(jīng)過預(yù)編碼后源點(diǎn)的實(shí)際發(fā)送率向量為(u1,v1)。為證明這一結(jié)論，只需計算的熵。由于U的后u～u1列為全零列，則

另一方面，由于U的秩為u1，根據(jù)矩陣代數(shù)的理論，則可以從U中的行向量中找到u1行，成為U的行向量的極大無關(guān)組，本文記它們的行下標(biāo)分別為則這u1行對應(yīng)于的u1個分量，這u1個分量按式(15)所示的對應(yīng)關(guān)系的矩陣形式為

由于極大無關(guān)組對應(yīng)行向量是線性無關(guān)的，式(17)中的u1階矩陣是可逆的。求解式(17)所示的線性方程組，可得的每個分量可以被線性表示，因此Z1也是的函數(shù)，與上述證明類似，可以得到

由于式(9)和式(13)具有相同的可解性，經(jīng)源點(diǎn)預(yù)編碼后，宿點(diǎn)t1可以求解式(13)所示的線性方程組得到，利用式(17)，宿點(diǎn)可以恢復(fù)出字符向量Z1；同理，宿點(diǎn)t2可以恢復(fù)出字符向量從而通過源點(diǎn)的預(yù)編碼技術(shù)導(dǎo)出了一個源點(diǎn)發(fā)送率向量為(u1,v1)的可行的傳輸方案。證畢。

4 基于源點(diǎn)預(yù)編碼的宿點(diǎn)干擾消除

在源點(diǎn)實(shí)施預(yù)編碼后，宿點(diǎn)t1和t2分別得到式(13)和式(14)所示的線性方程組。把式(11)和式(12)分別代入式(13)和式(14)，則得到

要使式(19)和式(20)能求解，則需要滿足推論1，必須讓系數(shù)矩陣的非全零列的數(shù)目π(A)與矩陣的秩相等。根據(jù)秩的性質(zhì)，有rank(A)≤π(A)；當(dāng)rank(A)<π(A)時，因矩陣的秩不會增加，則應(yīng)減小π(A)的值。如果適當(dāng)?shù)剡x取預(yù)編碼矩陣的元素，使式(19)和式(20)的系數(shù)矩陣出現(xiàn)全零列，從而達(dá)到了減小π()A的目標(biāo)。

宿點(diǎn)t1對應(yīng)的系數(shù)矩陣為其中，M11U和向量X1對應(yīng)，而X1中的分量是宿點(diǎn)t1所需要的消息；和向量X2對應(yīng)，X2是宿點(diǎn)t1不需要的，可以看作信息干擾。因此，要使矩陣A出現(xiàn)全零列，應(yīng)在中出現(xiàn)，且U應(yīng)為滿秩矩陣；同理，對于宿點(diǎn)t2，應(yīng)讓M12U出現(xiàn)全零列，且V應(yīng)為滿秩矩陣。

基于以上分析，預(yù)編矩陣U的選取方法如下。首先求M21的行空間再求矩陣M21的零空間注意這2個子空間互為正交補(bǔ)，因M21的列數(shù)為v，從而的一組基向量，的一組基向量，則構(gòu)成了GF(q)域上v維線性空間的一組基向量，令預(yù)編碼矩陣V的列向量分別取上述的基向量，如式(21)所示。

同理，求出u維向量空間的子空間N(M12)的一組基向量{β1,β2,…,βλ}，記λ=rank(N(M12))，再求出的一組基向量則預(yù)編矩陣U的列向量如式(22)所示。

由于U和V的列向量分別由u維向量空間和v維向量空間的基向量構(gòu)成，從而U和V均為滿秩矩陣。

把U和V分別代入式(19)和式(20)，則式(19)中的分塊矩陣至少有前τ列為全零列，式(20)中的分塊矩陣M12U至少有λ列為全零列。

5 基于干擾消除的網(wǎng)絡(luò)編碼優(yōu)化構(gòu)造

5.1 二級預(yù)編碼策略

本文采用二級預(yù)編碼策略，具體如圖3所示，其中，預(yù)編碼1用于控制源點(diǎn)的實(shí)際發(fā)送速率，預(yù)編碼2用于消除宿點(diǎn)的干擾。

圖3 二級編碼策略示意

源點(diǎn)的數(shù)據(jù)發(fā)送速率假設(shè)為(u,v)，選取傳輸方案θ，在此基礎(chǔ)上，在源點(diǎn)實(shí)施如式(23)所示的預(yù)編碼1。

U[1]為u階方陣，如式(24)所示。

V[1]為v階方陣，如式(25)所示。

其中，wi(i=1,2,…,u)和zj(j=1,2,…,v)均為GF(q)中的元素，其值為1或0。

在實(shí)施了預(yù)編碼1的基礎(chǔ)上，再在源點(diǎn)實(shí)施如式(26)所示的預(yù)編碼2。

把式(23)和式(26)代入式(27)，則宿點(diǎn)t1和t2得到的線性方程組分別如式(28)和式(29)所示。

把式(28)寫成如式(30)所示形式。

把式(29)寫成如式(31)所示形式。

記式(30)的系數(shù)矩陣為C，式(31)的系數(shù)矩陣為B。

記式(22)所示的列向量為U[2]，式(21)所示的列向量為V[2]，現(xiàn)在來計算和因?yàn)閂[2]的前τ列是N(M21)的基向量，則分塊矩陣的前τ列必為全零列；同理，分塊矩陣的前λ列必定為全零列。注意到，矩陣C和B均是2個矩陣的乘積，在相乘的2個矩陣中，后者是對角矩陣，因此，根據(jù)對角矩陣相乘的特點(diǎn)，若τ≠0，則矩陣C的第u+1,u+2,…,u+τ列必定為全零列；同理，矩陣B的前λ列必定為全零列。

盡管系數(shù)矩陣C和B中出現(xiàn)了一些全零列，但不一定能滿足推論1的條件，接下來，通過選取合適的U[1]和V[1]中的對角線元素來增加全零列的數(shù)目，使式(30)和式(31)能滿足推論1。

根據(jù)矩陣相乘的性質(zhì)，若wi=0，則矩陣C和B的第i列必定為全零列；若zj=0，則矩陣C和B的第u+j列必定為全零列。

置零規(guī)則：在需要置wi（i=1,2,…,u)，zj（j=1,2,…,v）的值為零時，應(yīng)優(yōu)先選取下標(biāo)大者的元素。例如，若需設(shè)置wi中的一個元素為0，則應(yīng)讓下標(biāo)最大的元素wu為0，其余元素均為1；若需設(shè)置wi中的2個元素為0，則應(yīng)讓下標(biāo)最大的2個元素wu和wu-1為0，其余元素均為1。

5.2 可達(dá)信息率區(qū)域邊界點(diǎn)及其相應(yīng)的傳輸方案

由定理2可知，可達(dá)信息率區(qū)域內(nèi)部節(jié)點(diǎn)的可行傳輸方案可以由邊界點(diǎn)的可行傳輸方案導(dǎo)出。為了減少計算量，只需要找出可達(dá)信息率區(qū)域的邊界點(diǎn)，并保存相應(yīng)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案。

可達(dá)信息率區(qū)域邊界點(diǎn)集合的定義具體如下。

設(shè)P為可達(dá)信息率區(qū)域，Q為可達(dá)信息率區(qū)域的邊界點(diǎn)形成的集合，R為可達(dá)信息率區(qū)域內(nèi)部點(diǎn)形成的集合。R的定義如下：?(u1,v1)∈R，則?(u2,v2)∈P，有(u2,v2)控 制 (u1,v1)，即(u1,v1)?(u2,v2)，且(u1,v1) ≠ (u2,v2)。則Q=P-R就是邊界點(diǎn)形成的集合。

為了保存邊界點(diǎn)的傳輸方案，現(xiàn)定義一個二元組<(x,y),θ>，其中第一個元素是邊界點(diǎn)的二維坐標(biāo)，第二個元素是這個邊界點(diǎn)所依賴的傳輸方案。記這些二元組形成的集合為Q′，其定義為Q′={<(x,y),θ>:(x,y)∈Q}。求邊界點(diǎn)集合Q′的遞歸算法如算法1所示。

5.3 傳輸方案的優(yōu)化

本文采用隨機(jī)線性網(wǎng)絡(luò)編碼方法得到傳輸方案θ，則能唯一地確定(M11M21)和(M12M22)，進(jìn)而唯一確定從而它們的全零列的列數(shù)τ和λ可唯一確定，因此，τ和λ是θ的函數(shù)，分別記為τ(θ)、λ(θ)。當(dāng)τ(θ)和λ(θ)的值較大時，則在預(yù)編碼1中只需讓wi、zi中較少項(xiàng)置0，就能使式(30)和式(31)滿足推論1，則源點(diǎn)的實(shí)際發(fā)送速率較大。因此，需要尋找較優(yōu)的傳輸方案θ，使τ(θ)和λ(θ)的值盡可能大，這是一個雙目標(biāo)優(yōu)化問題。

記Ω為所有傳輸方案的集合，則該雙目標(biāo)優(yōu)化問題描述如式(32)所示。

式(32)所示的雙目標(biāo)優(yōu)化問題可以通過多目標(biāo)進(jìn)化算法來求解。文獻(xiàn)[21-22]運(yùn)用多目標(biāo)進(jìn)化算法求最優(yōu)的網(wǎng)絡(luò)傳輸方案的近似解，也可以采用蒙特卡羅法來求式(32)的近似最優(yōu)解。本文采用文獻(xiàn)[22]類似的方法，運(yùn)用了相同的遺傳表示，只是適應(yīng)度函數(shù)與文獻(xiàn)[22]不相同，求出的最優(yōu)解是一個Pareto邊界。

5.4 算法描述

算法2雙單播網(wǎng)絡(luò)的構(gòu)造算法

步驟1利用Ford-Fulkerson算法[23]，分別求雙單播網(wǎng)絡(luò)的k1-1、k2-2、k12-1、k12-2。令u=k1-1、v=k2-2，針對源點(diǎn)的數(shù)據(jù)發(fā)送速率向量(u,v)，運(yùn)用類似文獻(xiàn)[22]的方法求出式(32)的近似最優(yōu)解，記為Γ。

步驟2選定近似最優(yōu)解中的一個傳輸方案θ∈Γ，并置Γ=Γ-{θ}。則由θ唯一確定M11、M21、M12、M22、U[2]、V[2]、和并得出τ和λ值。

步驟3針對θ，調(diào)用算法1。

步驟4判斷Γ是否為空集，若不為空集，則轉(zhuǎn)到步驟2，否則算法結(jié)束。

算法結(jié)束后，Q′為可達(dá)信息率區(qū)域的邊界點(diǎn)及其相應(yīng)的傳輸方案的二元組形成的集合。下面說明這一事實(shí)：若通過算法2求出了Q′，則①通過Q′可以獲得可達(dá)信息率區(qū)域P；② 對于?(x,y)∈P，可以找出以(x,y)為數(shù)據(jù)發(fā)送速率向量的可行傳輸方案。

首先，由Q′的定義，可以從集合Q′中得到Q，進(jìn)而獲得R，從而得到P=R∪Q。

對于?(u1,v1)∈Q，必存在<(u1,v1),θ1>∈Q′，其中θ1表示發(fā)送速率向量(u1,v1)所依賴的傳輸方案。從算法1的求解過程可知，由傳輸方案θ1可以唯一確定M11、M21、M12、M22，進(jìn)而唯一確定U[2]和V[2]，由(u1,v1)可以得出在U[1]和V[1]需要置零的項(xiàng)數(shù)，再按照置零規(guī)則，則矩陣U[1]和V[1]唯一確定，因此，由傳輸方案θ1導(dǎo)出的傳輸方案唯一確定。

對于? (u2,v2)∈R，由R的定義，必定存在(u1,v1)∈Q，滿足(u2,v2)?(u1,v1)，由此可知，(u1,v1)導(dǎo)出傳輸方案唯一確定，再根據(jù)定理2，則能夠以(u1,v1)的導(dǎo)出傳輸方案為基礎(chǔ)，在源點(diǎn)再次進(jìn)行預(yù)編碼，導(dǎo)出關(guān)于(u2,v2)的可行傳輸方案。由于P=R∪Q，則上述結(jié)論成立。

綜上，算法2特別適用于實(shí)際應(yīng)用場景。從算法的結(jié)果Q′中不僅能得出可達(dá)信息率區(qū)域，且對于區(qū)域中的每一點(diǎn)，能容易地得到相應(yīng)的可行傳輸方案。

值得說明的是，由于本文只能求出式(32)的近似最優(yōu)解，故求出的可達(dá)信息率區(qū)域也是近似最優(yōu)的。

6 算例

圖4表示一個雙單播網(wǎng)絡(luò)，容易求出k1-1=k1-2=k12-1=k12-2=3。選擇伽羅華域GF(23)，其不可約多項(xiàng)式為x3+x+1，寫成二進(jìn)制形式為(1011)2。選定源點(diǎn)數(shù)據(jù)發(fā)送率向量為(u,v)=(3,3)，現(xiàn)運(yùn)用隨機(jī)線性網(wǎng)絡(luò)編碼方法并結(jié)合多目標(biāo)優(yōu)化的進(jìn)化策略來確定較優(yōu)的傳輸方案，本例只求出了一個傳輸方案，在該傳輸方案下，宿點(diǎn)t1和宿點(diǎn)t2的全局編碼向量形成的矩陣分別如式(33)和式(34)所示。

圖4 一個雙單播網(wǎng)絡(luò)實(shí)例

求出預(yù)編碼2的預(yù)編碼矩陣，如式(35)所示。

從而可得

可以看出，無論是宿點(diǎn)t1還是宿點(diǎn)t2，均不能求解線性方程組，因?yàn)檫@2個系數(shù)矩陣的非全零列數(shù)均為4，而矩陣的秩均為3，所以必須在源點(diǎn)利用預(yù)編碼1來控制源點(diǎn)的實(shí)際發(fā)送速率。

源點(diǎn)實(shí)施二級預(yù)編碼后，宿點(diǎn)t1得到的線性方程組的系數(shù)矩陣為

宿點(diǎn)t2得到的線性方程組的系數(shù)矩陣為

在式(37)和式(38)中，系數(shù)矩陣均為3行6列的矩陣，每個矩陣均有1個全零列，要使系數(shù)矩陣滿足推論1的條件，至少還要讓每個矩陣的另外2列為全零列，則必須讓wi和zi（i=1,2,3）中的其中2項(xiàng)置零，根據(jù)置零規(guī)則，有以下3種置零方式，具體如下。

1)w1=1，w2=w3=0，zi=1（i=1,2,3）。

2)z1=1，z2=z3=0，wi=1（i=1,2,3）。

3)w1=w2=1，w3=0，z1=z2=1，z3=0。

從而得到預(yù)編碼1的3組矩陣，如式(39)所示。

它們對應(yīng)的實(shí)際發(fā)送速率向量分別為(1,3)、(3,1)、(2,2)。

現(xiàn)分析第3種情況，其余2種情況類似。因?qū)嶋H的發(fā)送速率向量為(2,2)，在一次數(shù)據(jù)傳輸中，假設(shè)源點(diǎn)s1傳輸?shù)淖址蛄繛閄1=(111,110,?)*為了所提的方法具有統(tǒng)一性，盡管實(shí)際上只發(fā)送2個字符，但采用發(fā)送3個字符的格式，最后一個字符沒有傳輸至網(wǎng)絡(luò)，因此，該字符的選取隨意，本文用“?”表示。，源點(diǎn)s2傳輸?shù)淖址蛄繛閄2=(100,010,?)，則源點(diǎn)s1的預(yù)編碼矩陣為

經(jīng)預(yù)編碼后得到的字符向量為

源點(diǎn)s2的預(yù)編碼矩陣為

源點(diǎn)經(jīng)預(yù)編碼后，分別把預(yù)編碼矩陣對應(yīng)的全局編碼向量和預(yù)編碼后的字符采用已定的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案進(jìn)行傳輸。則宿點(diǎn)t1把得到的全局編碼矩陣和接收到的字符進(jìn)行聯(lián)立形成線性方程組，如式(44)所示。

宿點(diǎn)t2把得到的全局編碼矩陣和接收到的字符進(jìn)行聯(lián)立形成線性方程組，如式(45)所示。

式(44)和式(45)顯然滿足推論1的條件，從而可以求解。式(44)可以解出x11、x12、x22，其結(jié)果為(x11,x12,x22)=(111,110,010)；式(45)可以解出x12、x21、x22，其結(jié)果為(x12,x21,x22)=(110,100,010)。

綜上，宿點(diǎn)t1能解碼出源點(diǎn)s1的2個字符，宿點(diǎn)t2能解碼出源點(diǎn)s2的2個字符，即源點(diǎn)的發(fā)送率向量為(2,2)。

其他2種情況可以類似地進(jìn)行討論。

綜合這3種情況，可以得到源點(diǎn)的可達(dá)信息率區(qū)域，如圖5所示，其中，橫坐標(biāo)的單位是字符/單位時間。

圖5 雙單播網(wǎng)絡(luò)的可達(dá)信息率區(qū)域

以上給出了可達(dá)信息率區(qū)域邊界點(diǎn)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案，對于可達(dá)信息率區(qū)域的坐標(biāo)為整數(shù)的內(nèi)部點(diǎn)，由定理2可知，可以從邊界點(diǎn)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案中導(dǎo)出。例如，對于坐標(biāo)為(2,1)的點(diǎn)，可以從邊界點(diǎn)(2,2)或(3,1)的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案中導(dǎo)出。

7 結(jié)束語

本文提出了一種雙單播網(wǎng)絡(luò)編碼的構(gòu)造方法，采用源點(diǎn)預(yù)編碼技術(shù)，中間節(jié)點(diǎn)采用隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)，并結(jié)合多目標(biāo)優(yōu)化進(jìn)化策略來確定傳輸方案，利用源點(diǎn)至宿點(diǎn)的信息轉(zhuǎn)換矩陣的零向量空間的基向量和行向量空間的基向量共同來確定源點(diǎn)的預(yù)編碼矩陣的列向量，實(shí)現(xiàn)了在宿點(diǎn)消除信息干擾的目標(biāo)。由雙單播情形下的網(wǎng)絡(luò)編碼導(dǎo)出技術(shù)，提出了二級預(yù)編碼策略來控制源點(diǎn)的發(fā)送速率，從而能夠得到可行的網(wǎng)絡(luò)傳輸方案。由多目標(biāo)進(jìn)化策略，可以求出雙單播網(wǎng)絡(luò)編碼的近似的可達(dá)信息率區(qū)域的邊界點(diǎn)及相應(yīng)的可行傳輸方案。本文還論證了如下結(jié)論：只需要求出可達(dá)信息率區(qū)域邊界點(diǎn)的可行傳輸方案，內(nèi)部點(diǎn)的傳輸方案可以從相應(yīng)邊界點(diǎn)的傳輸方案中導(dǎo)出。因此，所提方法不僅可以求出雙單播網(wǎng)絡(luò)編碼的近似可達(dá)信息率區(qū)域，還為求出的可達(dá)信息率區(qū)域的每一個整數(shù)坐標(biāo)點(diǎn)提供了構(gòu)造可行傳輸方案的方法，適合于網(wǎng)絡(luò)編碼技術(shù)的實(shí)際應(yīng)用。

多單播網(wǎng)絡(luò)是一個比較困難的問題，能否把這一方法推廣到三單播網(wǎng)絡(luò)乃至源點(diǎn)數(shù)更多的多單播網(wǎng)絡(luò)，將是下一步需要進(jìn)行的研究工作。