蒲保興，莫智懿

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

1 引言

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

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

解決雙單播網(wǎng)絡(luò)編碼問(wèn)題的關(guān)鍵是讓宿點(diǎn)消除干擾，文獻(xiàn)[9]運(yùn)用源點(diǎn)預(yù)編碼策略作用于雙單播網(wǎng)絡(luò)的信息不等式提出了求解雙單播網(wǎng)絡(luò)編碼近似可達(dá)信息率區(qū)域的方法，但該方法僅對(duì)文獻(xiàn)[17]提出的雙單播網(wǎng)絡(luò)的可達(dá)信息率區(qū)域所滿足的信息不等式實(shí)現(xiàn)了可計(jì)算化，未涉及網(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ù)來(lái)形成傳輸方案，提出了選擇預(yù)編碼矩陣的策略：用宿點(diǎn)的信息轉(zhuǎn)換矩陣的零向量空間的基向量和行向量空間的基向量共同來(lái)確定預(yù)編碼矩陣的列向量，從而使宿點(diǎn)的全局編碼矩陣的某些列變?yōu)槿懔?，在宿點(diǎn)消除了部分信息干擾。根據(jù)雙單播情形下的網(wǎng)絡(luò)編碼的導(dǎo)出技術(shù)，運(yùn)用二級(jí)預(yù)編碼策略來(lái)控制源點(diǎn)的發(fā)送速率。結(jié)合以上策略，本文提出了雙單播網(wǎng)絡(luò)編碼的構(gòu)造方法。所提方法不僅能求出雙單播網(wǎng)絡(luò)編碼的近似可達(dá)的信息率區(qū)域，同時(shí)針對(duì)求出的可達(dá)信息率區(qū)域中的任何一個(gè)整數(shù)坐標(biāo)點(diǎn)，還提供了構(gòu)造可行的網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸方案的具體方法。

2 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

由于有向無(wú)環(huán)圖的拓?fù)涮卣?，按照網(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的全局編碼向量。對(duì)于網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)，把其每一條輸入信道的全局編碼向量作為矩陣的一行，形成一個(gè)矩陣，則這個(gè)矩陣為該節(jié)點(diǎn)的全局編碼矩陣。

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

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

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

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

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

其中，Yi是一個(gè)δi維的列向量；(Mi1Mi2)是一個(gè)δ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)行計(jì)算。注意到，式(7)與式(4)的形式相同，式(7)是在式(4)的基礎(chǔ)上把信道上傳輸?shù)淖址鹹ej換成信道的全局編碼向量，從而宿點(diǎn)ti的全局編碼矩陣的計(jì)算為

這就表明，分別按式(4)和式(7)計(jì)算信道攜帶的字符和全局編碼向量能夠滿足式(5)的對(duì)應(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個(gè)任務(wù)：首先要確定源點(diǎn)的數(shù)據(jù)發(fā)送速率，然后針對(duì)選定的源點(diǎn)數(shù)據(jù)發(fā)送速率來(lái)確定各信道的局部編碼向量。對(duì)于雙單播網(wǎng)絡(luò)，因有2個(gè)源點(diǎn)，2個(gè)源點(diǎn)的數(shù)據(jù)發(fā)送速率形成了一個(gè)二維向量，稱之為源點(diǎn)數(shù)據(jù)發(fā)送速率向量。選定了源點(diǎn)數(shù)據(jù)發(fā)送速率向量后，接下來(lái)的任務(wù)是如何確定傳輸方案θ，按照傳輸方案θ中指定的局部編碼向量進(jìn)行數(shù)據(jù)傳輸后，使宿點(diǎn)能夠通過(guò)求解線性方程組來(lái)恢復(fù)源點(diǎn)發(fā)送的消息。

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

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

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

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

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

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

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

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

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

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

矩陣A的零空間是由齊次線性方程組AX=0的所有解張成的n維向量空間的一個(gè)線性子空間，記為N(A)。由零空間的定義可得，對(duì)于任意的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對(duì)應(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)過(guò)線性組合后再分別注入源點(diǎn)的虛擬輸入信道，如圖2所示。

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

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

其中，U表示一個(gè)u階方陣，每一個(gè)系數(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對(duì)于雙單播網(wǎng)絡(luò)的一個(gè)源點(diǎn)發(fā)送速率向量為(u,v)的傳輸方案，在源點(diǎn)s1和s2分別實(shí)施式(11)和式(12)所示的預(yù)編碼，則從傳輸方案θ中導(dǎo)出了一個(gè)新的傳輸方案，本文稱前者為原始方案，后者為導(dǎo)出方案。

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

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

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

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

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

定理3對(duì)于一個(gè)源點(diǎn)的發(fā)送速率向量為(u,v)的可行傳輸方案，可以導(dǎo)出一個(gè)源點(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；由對(duì)稱性，源點(diǎn)s2的預(yù)編碼矩陣V為v階方陣，V的后v～v1列均為全零列，且滿足rank(V)=v1。

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

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

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

由于式(9)和式(13)具有相同的可解性，經(jīng)源點(diǎn)預(yù)編碼后，宿點(diǎn)t1可以求解式(13)所示的線性方程組得到，利用式(17)，宿點(diǎn)可以恢復(fù)出字符向量Z1；同理，宿點(diǎn)t2可以恢復(fù)出字符向量從而通過(guò)源點(diǎn)的預(yù)編碼技術(shù)導(dǎo)出了一個(gè)源點(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)時(shí)，因矩陣的秩不會(huì)增加，則應(yīng)減小π(A)的值。如果適當(dāng)?shù)剡x取預(yù)編碼矩陣的元素，使式(19)和式(20)的系數(shù)矩陣出現(xiàn)全零列，從而達(dá)到了減小π()A的目標(biāo)。

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

基于以上分析，預(yù)編矩陣U的選取方法如下。首先求M21的行空間再求矩陣M21的零空間注意這2個(gè)子空間互為正交補(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 二級(jí)預(yù)編碼策略

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

圖3 二級(jí)編碼策略示意

源點(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)寫(xiě)成如式(30)所示形式。

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

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

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

盡管系數(shù)矩陣C和B中出現(xiàn)了一些全零列，但不一定能滿足推論1的條件，接下來(lái)，通過(guò)選取合適的U[1]和V[1]中的對(duì)角線元素來(lái)增加全零列的數(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）的值為零時(shí)，應(yīng)優(yōu)先選取下標(biāo)大者的元素。例如，若需設(shè)置wi中的一個(gè)元素為0，則應(yīng)讓下標(biāo)最大的元素wu為0，其余元素均為1；若需設(shè)置wi中的2個(gè)元素為0，則應(yīng)讓下標(biāo)最大的2個(gè)元素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)出。為了減少計(jì)算量，只需要找出可達(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)定義一個(gè)二元組<(x,y),θ>，其中第一個(gè)元素是邊界點(diǎn)的二維坐標(biāo)，第二個(gè)元素是這個(gè)邊界點(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)τ(θ)和λ(θ)的值較大時(shí)，則在預(yù)編碼1中只需讓wi、zi中較少項(xiàng)置0，就能使式(30)和式(31)滿足推論1，則源點(diǎn)的實(shí)際發(fā)送速率較大。因此，需要尋找較優(yōu)的傳輸方案θ，使τ(θ)和λ(θ)的值盡可能大，這是一個(gè)雙目標(biāo)優(yōu)化問(wèn)題。

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

式(32)所示的雙目標(biāo)優(yōu)化問(wèn)題可以通過(guò)多目標(biāo)進(jìn)化算法來(lái)求解。文獻(xiàn)[21-22]運(yùn)用多目標(biāo)進(jìn)化算法求最優(yōu)的網(wǎng)絡(luò)傳輸方案的近似解，也可以采用蒙特卡羅法來(lái)求式(32)的近似最優(yōu)解。本文采用文獻(xiàn)[22]類似的方法，運(yùn)用了相同的遺傳表示，只是適應(yīng)度函數(shù)與文獻(xiàn)[22]不相同，求出的最優(yōu)解是一個(gè)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，針對(duì)源點(diǎn)的數(shù)據(jù)發(fā)送速率向量(u,v)，運(yùn)用類似文獻(xiàn)[22]的方法求出式(32)的近似最優(yōu)解，記為Γ。

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

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

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

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

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

對(duì)于?(u1,v1)∈Q，必存在<(u1,v1),θ1>∈Q′，其中θ1表示發(fā)送速率向量(u1,v1)所依賴的傳輸方案。從算法1的求解過(guò)程可知，由傳輸方案θ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)出的傳輸方案唯一確定。

對(duì)于? (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)用場(chǎng)景。從算法的結(jié)果Q′中不僅能得出可達(dá)信息率區(qū)域，且對(duì)于區(qū)域中的每一點(diǎn)，能容易地得到相應(yīng)的可行傳輸方案。

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

6 算例

圖4表示一個(gè)雙單播網(wǎng)絡(luò)，容易求出k1-1=k1-2=k12-1=k12-2=3。選擇伽羅華域GF(23)，其不可約多項(xiàng)式為x3+x+1，寫(xiě)成二進(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)化策略來(lái)確定較優(yōu)的傳輸方案，本例只求出了一個(gè)傳輸方案，在該傳輸方案下，宿點(diǎn)t1和宿點(diǎn)t2的全局編碼向量形成的矩陣分別如式(33)和式(34)所示。

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

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

從而可得

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

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

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

在式(37)和式(38)中，系數(shù)矩陣均為3行6列的矩陣，每個(gè)矩陣均有1個(gè)全零列，要使系數(shù)矩陣滿足推論1的條件，至少還要讓每個(gè)矩陣的另外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)所示。

它們對(duì)應(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個(gè)字符，但采用發(fā)送3個(gè)字符的格式，最后一個(gè)字符沒(méi)有傳輸至網(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ù)編碼矩陣對(duì)應(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個(gè)字符，宿點(diǎn)t2能解碼出源點(diǎn)s2的2個(gè)字符，即源點(diǎn)的發(fā)送率向量為(2,2)。

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

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

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

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

7 結(jié)束語(yǔ)

本文提出了一種雙單播網(wǎng)絡(luò)編碼的構(gòu)造方法，采用源點(diǎn)預(yù)編碼技術(shù)，中間節(jié)點(diǎn)采用隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)，并結(jié)合多目標(biāo)優(yōu)化進(jìn)化策略來(lái)確定傳輸方案，利用源點(diǎn)至宿點(diǎn)的信息轉(zhuǎn)換矩陣的零向量空間的基向量和行向量空間的基向量共同來(lái)確定源點(diǎn)的預(yù)編碼矩陣的列向量，實(shí)現(xiàn)了在宿點(diǎn)消除信息干擾的目標(biāo)。由雙單播情形下的網(wǎng)絡(luò)編碼導(dǎo)出技術(shù)，提出了二級(jí)預(yù)編碼策略來(lái)控制源點(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ū)域的每一個(gè)整數(shù)坐標(biāo)點(diǎn)提供了構(gòu)造可行傳輸方案的方法，適合于網(wǎng)絡(luò)編碼技術(shù)的實(shí)際應(yīng)用。

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