基于遺傳算法的三單播網(wǎng)絡(luò)對(duì)齊及優(yōu)化

張 琴，雷維嘉，謝顯中，朱茂娟

(重慶郵電大學(xué)移動(dòng)通信重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065)

0 引言

目前單播是無(wú)線和有線網(wǎng)絡(luò)的主要傳播形式，高效利用網(wǎng)絡(luò)資源的單播傳輸方法是一個(gè)重要的研究?jī)?nèi)容。對(duì)于網(wǎng)絡(luò)中存在的干擾問(wèn)題，以往研究的主要任務(wù)就是設(shè)計(jì)并完善會(huì)話間網(wǎng)絡(luò)編碼(intersession network coding，INC)方法。在文獻(xiàn)［1］中，“干擾”是由一個(gè)單播流傳輸?shù)搅硪粋€(gè)流的期望目的端，它可以影響每個(gè)數(shù)據(jù)流傳輸?shù)乃俣?，同時(shí)也指出，只要能夠滿足苛刻的限制條件，“無(wú)干擾”傳輸是可能的。

干擾對(duì)齊(interference alignmen，IA)［2－4］技術(shù)是為了解決通信系統(tǒng)中干擾和容量問(wèn)題而提出的，最近的文獻(xiàn)［5－12］也將IA技術(shù)應(yīng)用于單播網(wǎng)絡(luò)中，以實(shí)現(xiàn)干擾信號(hào)的對(duì)齊，提高系統(tǒng)性能。

文獻(xiàn)［5］提出了網(wǎng)絡(luò)對(duì)齊(network alignment，NA)技術(shù)，一般有2種方法，一種是在網(wǎng)絡(luò)邊緣進(jìn)行IA，而在網(wǎng)絡(luò)內(nèi)部進(jìn)行隨機(jī)線性網(wǎng)絡(luò)編碼(random linear network coding，RLNC);另一種是IA和NC都在網(wǎng)絡(luò)內(nèi)部進(jìn)行。預(yù)編碼基礎(chǔ)上的網(wǎng)絡(luò)對(duì)齊(precoding－based network alignment，PBNA)是在發(fā)送端設(shè)計(jì)預(yù)編碼，在接收端設(shè)計(jì)干擾抑制矩陣，在網(wǎng)絡(luò)中進(jìn)行網(wǎng)絡(luò)編碼。采用PBNA后，每對(duì)單播會(huì)話能夠達(dá)到1/2的自由度(degree of freedom，DOF)。

在文獻(xiàn)［6］中，應(yīng)用干擾對(duì)齊的思想，并與網(wǎng)絡(luò)編碼相結(jié)合，證明了三符號(hào)擴(kuò)展時(shí)網(wǎng)絡(luò)對(duì)齊的可能性，構(gòu)成了三單播漸近網(wǎng)絡(luò)對(duì)齊(3－unicast asymptotic network alignment，3－ANA)方法，給INC方法帶來(lái)了新的方向。文獻(xiàn)［7］重點(diǎn)設(shè)計(jì)預(yù)編碼(發(fā)送端)和解碼(接收端)矩陣，在網(wǎng)絡(luò)內(nèi)部，依然可以應(yīng)用網(wǎng)絡(luò)編碼生成當(dāng)?shù)鼐幋a核(local encoding kernels)。

與無(wú)線干擾信道相比，網(wǎng)絡(luò)的最大不同就是其傳輸矩陣是相關(guān)的，就是說(shuō)在一些網(wǎng)絡(luò)中PBNA是不能實(shí)現(xiàn)的［8］。文獻(xiàn)［8－9］分別在瞬時(shí)和延遲單播網(wǎng)絡(luò)中，聯(lián)合應(yīng)用漸近干擾對(duì)齊技術(shù)與線性網(wǎng)絡(luò)編碼技術(shù)，設(shè)計(jì)特殊的預(yù)編碼矩陣，并給出實(shí)現(xiàn)PBNA的約束條件。但是這些約束條件太多，在實(shí)際中還無(wú)法檢驗(yàn)。對(duì)于三單播網(wǎng)絡(luò)，文獻(xiàn)［10－11］在文獻(xiàn)［8－9］的基礎(chǔ)上把約束條件減少為4個(gè)，但是其中有2個(gè)條件依然不能檢驗(yàn)，還需要進(jìn)一步簡(jiǎn)化，以便能用拓?fù)浣Y(jié)構(gòu)檢驗(yàn)。文獻(xiàn)［12］研究了在2用戶X網(wǎng)絡(luò)中，設(shè)計(jì)預(yù)編碼矩陣和進(jìn)行網(wǎng)絡(luò)對(duì)齊所要滿足的條件。

本文在上述文獻(xiàn)［8－11］的基礎(chǔ)上，針對(duì)三單播有向無(wú)延遲非循環(huán)網(wǎng)絡(luò)，應(yīng)用漸近干擾對(duì)齊技術(shù)研究各用戶發(fā)送3個(gè)不同數(shù)據(jù)流m，n，p時(shí)的預(yù)編碼矩陣，并分析網(wǎng)絡(luò)對(duì)齊的可行條件;進(jìn)一步，聯(lián)合圖論中最短路徑遺傳算法和網(wǎng)絡(luò)線性性質(zhì)計(jì)算網(wǎng)絡(luò)可進(jìn)行PBNA的約束條件，將網(wǎng)絡(luò)約束條件簡(jiǎn)化為2個(gè)方程，降低檢驗(yàn)的復(fù)雜度，并進(jìn)行實(shí)際檢驗(yàn)。

1 網(wǎng)絡(luò)模型

對(duì)于一個(gè)無(wú)延遲非循環(huán)的有向圖G=(V，E)，這里V表示節(jié)點(diǎn)的集合，E表示邊的集合，網(wǎng)絡(luò)中的一條邊用(a，b)表示，a，b為網(wǎng)絡(luò)中的2個(gè)節(jié)點(diǎn)。入度(指有向圖中終止于某點(diǎn)的邊的數(shù)目)為零的節(jié)點(diǎn)稱作發(fā)送端，出度(指有向圖中起始于某點(diǎn)的邊的數(shù)目)為零的節(jié)點(diǎn)稱作接收端。用head(e)和end(e)表示一條邊的終點(diǎn)和起點(diǎn)，若e=(a，b)，則a=end(e)，b=head(e)。我們研究一個(gè)多單播網(wǎng)絡(luò)，有K個(gè)發(fā)送端s1，s2，…，sK，K個(gè)接收端d1，d2，…，dK，其中，任意di期望收到si發(fā)送的信號(hào)。網(wǎng)絡(luò)中每條邊的容量為1，每個(gè)發(fā)送端發(fā)送的信息相互獨(dú)立。

一條路徑由一系列相鄰的邊e1e2…ek組成，其中，head(ei)=end(ei+1)，?i∈{1，2，…，k－1}，e1和ek是這條路徑的起始邊和結(jié)束邊，表示為Pe1ek。當(dāng)a=end(e1)和b=head(ek)時(shí)，也可以把路徑Pe1ek表示為Pba。用a?b表示a是b的上游點(diǎn)，即點(diǎn)a能到達(dá)點(diǎn)b。同樣地，用ei?ej表示邊ei能到達(dá)邊ej。對(duì)于路徑P，用ei∈P來(lái)表示路徑P經(jīng)過(guò)邊ei。用xeiej表示邊ei到達(dá)邊ej的編碼系數(shù)(當(dāng)?shù)仡A(yù)編碼核)。如果對(duì)于圖G=(V'，E')和G=(V，E)，有V'?V，E'?E則稱圖G'是圖G的子圖(subgraph)。我們?cè)跓o(wú)延遲非循環(huán)網(wǎng)絡(luò)(DAG)圖中，考慮多單播問(wèn)題，其中，一個(gè)源—目的(發(fā)送端—接收端)對(duì)記為(sk，dk);用ki表示傳輸?shù)男畔⒎?hào)的數(shù)量大小;每個(gè)信息符號(hào)取自有限域Fp;用變量x表示編碼系數(shù)，me1:e2(x)表示邊e1到邊e2的邊增益，表示為

(1)式中，Pe1e2表示邊e1到e2的路徑，邊e'，e″相鄰。由文獻(xiàn)［13］可知，只有當(dāng)e1?e2時(shí)，me1:e2(x)才是一個(gè)非零多項(xiàng)式，特別當(dāng)e1=e2時(shí)其中表示包含2l個(gè)元素的有限域，l為隨機(jī)數(shù))。發(fā)送端si與接收端dj的信道增益為

(2)式中:Pji表示所有的從發(fā)送點(diǎn)si到接收點(diǎn)dj路徑;?(P)表示沿著路徑P的每一條邊的編碼系數(shù)乘積。假設(shè)mji(x)非零，則mji(x)是一個(gè)多項(xiàng)式和。

(3)式中:Mji是一個(gè)從發(fā)送端si到接收端dj的增益矩陣，為(m+p)×(m+p)的對(duì)角矩陣，對(duì)角線的(t，t)元素為mji(xt)，其中，xt表示si到dj在t時(shí)刻網(wǎng)絡(luò)的編碼核;V1，V2，V3分別為(m+p)×p，(m+p)×m，(m+p)×n的矩陣。

與干擾對(duì)齊方法相同，為了在接收端消除干擾，恢復(fù)出期望信號(hào)，需要在每個(gè)接收端dj設(shè)計(jì)干擾消除矩陣Uj，解碼后得到的符號(hào)向量為

按照干擾對(duì)齊要求［2－3］，為實(shí)現(xiàn)預(yù)編碼網(wǎng)絡(luò)對(duì)齊，達(dá)到壓縮干擾空間維數(shù)的目的，預(yù)編碼矩陣Vi和干擾抑制矩陣Uj需滿足條件

(5)式中，I表示單位矩陣。由于網(wǎng)絡(luò)傳輸矩陣Mji的相關(guān)性，要滿足以上的約束條件，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)需要滿足一些必要的條件。

2 預(yù)編碼網(wǎng)絡(luò)對(duì)齊的可行性條件分析

在無(wú)線干擾信道中，信道增益是獨(dú)立的，并且是服從連續(xù)分布的隨機(jī)變量，干擾對(duì)齊一定可行。而網(wǎng)絡(luò)信道增益取決于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，導(dǎo)致某些傳輸矩陣相關(guān)。因此，需要新的條件來(lái)確定網(wǎng)絡(luò)對(duì)齊可行。

2.1 預(yù)編碼矩陣設(shè)計(jì)

由于本文發(fā)送數(shù)據(jù)流大小不同，根據(jù)系統(tǒng)網(wǎng)絡(luò)模型，本文的預(yù)編碼網(wǎng)絡(luò)對(duì)齊要求滿足

(7)式中:A為m×m單位矩陣的前n列;B為p×p單位矩陣的前n列;C為p×p單位矩陣的前m列。

(8)式中，pi(x)，ψ(x)是對(duì)角矩陣Pi和T的元素。由TV1B=V1CA可知，預(yù)編碼矩陣的設(shè)計(jì)依賴于ψ(x)是否恒定。

當(dāng)ψ(x)恒定時(shí)，即T=Im+p，又因?yàn)锽=CA，所以任意的V1都滿足。

當(dāng)ψ(x)不恒定時(shí)，預(yù)編碼的選擇就不是那么自由了，我們?cè)O(shè)計(jì)的預(yù)編碼矩陣為

(9)式中，w=(1，1，1，…，1)T是m+p行的列向量。根據(jù)以上設(shè)計(jì)的預(yù)編碼矩陣，能夠滿足條件

2.2 網(wǎng)絡(luò)對(duì)齊可行性條件分析

根據(jù)文獻(xiàn)［10］，以上(10)式的3個(gè)條件可以簡(jiǎn)寫成

不幸的是，由于(11)式包含的條件數(shù)量太多，在實(shí)際中不可能逐一驗(yàn)證，可以將其轉(zhuǎn)化為如下定理。

定理1當(dāng)且僅當(dāng)對(duì)任意i∈{1，2，3}，條件(12)滿足時(shí)，網(wǎng)絡(luò)對(duì)齊是可行的。

(12)式中，pi(x)不是一個(gè)任意的函數(shù)，而是一個(gè)跟傳輸矩陣相關(guān)的函數(shù)。所以要簡(jiǎn)化(11)式，首先要引入圖論的一個(gè)性質(zhì)。

可以看出，pi(x)具有與h(x)同樣的特殊結(jié)構(gòu)，可以表示為

對(duì)于 路 徑P，且e，e'∈P，令h1(x)=mab(x)mpq(x)=s1(x)d(x)，h2(x)=maq(x)mpb(x)=s2(x)d(x)，其中，d(x)=gcd(h1(x)，h2(x))為h1(x)，h2(x)的最大公因式，則gcd(s1(x)，s2(x))=1。令u(x)=cs1(x)，v(x)=cs2(x)，c是一個(gè)非零常數(shù)。假設(shè)(P1，P2)∈Pab×Ppq和(P3，P4)∈Paq×Ppb，設(shè)為起點(diǎn)b到不同終點(diǎn)a，p共同邊的集合Paq∩Ppq}為起點(diǎn)q到不同終點(diǎn)a，p共同邊的集合，為不同起點(diǎn)b，q到終點(diǎn)a共同邊的集合Ppq}為不同起點(diǎn)b，q到終點(diǎn)p共同邊的集合，分別從集合中選取一條邊設(shè)為e1，e3，e4，e2。其中，e1與e2，e3與e4之間的路徑都不屬于P1∪P2。

因此，若e3?e2，選擇e3與e2之間的路徑為xee'，則u(xee')=c1xee'+c0，v(xee')=c2。

若e2?e3，選擇e4與e1之間的路徑為xee'，則u(xee')=c2，v(xee')=c1xee'+c0。

證明 只要證明了p1(x)，則p2(x)，p3(x)的

1)l≠l'的情況。

① 若l＞l'，則dσ=il+(k－i)l'=kl'+i(l－l')。

當(dāng)l'=0，因?yàn)閐σ=il=1且i在0－k中取值，i與l只能等于1，所以，當(dāng)l'＞0，即l'≥1，并且d=k≥2，l＞l'，所以dσ≥2，與dσ=1矛盾。

② 若l＜l'，則dσ=il+(k－i)l'=kl'+i(ll')，dτ=i'l+(k－i')l'=kl'+i'(l－l')。

當(dāng)l=0，dσ=(k－i)l'=1，dτ=(k－i')l'=0，有k=i'，l'=1，k=i+1，則，如此，f(z)與g(z)存在了公因式，所以矛盾。

2)l=l'，則dσ=kl，dτ=kl，但是dσ=1，dτ=0，所以矛盾。

由以上證明可知，當(dāng)k≥k'，k只能等于1，k≤k'的證明方法和k≥k'時(shí)一樣。即約束條件縮減到

在之前文獻(xiàn)中，為了更好地體現(xiàn)約束條件與網(wǎng)絡(luò)圖結(jié)構(gòu)的關(guān)系，αi，βi考慮比較小的常數(shù)值，即αi=0，1，βi=0，1。由于本文采用最短路徑遺傳算法，即選擇每個(gè)發(fā)送端到每個(gè)接收端的最短路徑，所以從條件(15)的情況下進(jìn)行再次優(yōu)化即可。

3 基于最短路徑遺傳算法的可行性條件優(yōu)化

以上分析的網(wǎng)絡(luò)對(duì)齊可行性約束條件無(wú)法少于4個(gè)，并且只能通過(guò)隨機(jī)測(cè)試確定其中的2個(gè)條件是否滿足，不能保證實(shí)際檢驗(yàn)的精確度。但運(yùn)用遺傳算法，能夠減少網(wǎng)絡(luò)對(duì)齊約束條件。遺傳算法能夠在網(wǎng)絡(luò)中選擇發(fā)送端到接收端的最短路徑，使信號(hào)沿著固定路徑傳輸，傳輸矩陣的元素都簡(jiǎn)化為單項(xiàng)式，以上的約束條件可減少為能根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)檢驗(yàn)的2個(gè)，并且降低了不同期望信號(hào)傳輸時(shí)經(jīng)過(guò)同一條邊的概率。

在研究路由問(wèn)題時(shí)，一個(gè)網(wǎng)絡(luò)可表示成一個(gè)加權(quán)圖G=(N，E)，其中，N表示節(jié)點(diǎn)集，E表示連接節(jié)點(diǎn)的通信鏈路集。|N|和|E|分別表示該網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和鏈路數(shù)，Cij為鏈路(i，j)的代價(jià)，代價(jià)矩陣為C=［Cij］。源節(jié)點(diǎn)和目的節(jié)點(diǎn)分別用S和D表示，每個(gè)鏈路的連接用zij表示，定義為

由元素zij構(gòu)成的矩陣為Zij，顯然，Zij對(duì)角線的元素為0且滿足條件:若zij=1，且zjk=1，則zik=1。用這種定義，最短路徑問(wèn)題就可轉(zhuǎn)化為求最小值的優(yōu)化問(wèn)題，目標(biāo)函數(shù)可表示為

(17)式中，對(duì)所有i，zij∈{0，1}。

根據(jù)以上目標(biāo)函數(shù)，在圖G中找到一個(gè)子圖G'，使發(fā)送端1，2，3分別到接收端1，2，3都有一條最短路徑，如此，在G'中，mij(x)就是關(guān)于變量的單項(xiàng)式，即每個(gè)發(fā)送端到接收端只有單獨(dú)一條路徑。由于遺傳算法求出全局最優(yōu)解時(shí)間復(fù)雜性很大，可以通過(guò)限定遺傳代數(shù)的方法，求出一個(gè)性能較好的次優(yōu)解來(lái)。然而，在每一個(gè)發(fā)送端選擇到3個(gè)接收端的最短路徑時(shí)，由于網(wǎng)絡(luò)中間節(jié)點(diǎn)過(guò)多，9個(gè)路徑很有可能經(jīng)過(guò)相同的邊，所以路徑之間依然有可能是相關(guān)的，如此，對(duì)齊約束條件依然需要

在圖G'中檢驗(yàn)條件(18)的方法如下。

1)pi(x)≠1情況。

由文獻(xiàn)［10］中的引理2，當(dāng)且僅當(dāng)路徑對(duì)(P1，P2)∈(Pab，Ppq)和(P3，P4)∈(Paq，Ppb)沒(méi)有共同邊，即P1∩P2=?且P3∩P4=?時(shí)pi(x)=可驗(yàn)證。

2)pi(x)≠ψ(x)情況。文獻(xiàn)［8］的引理4，檢驗(yàn)這2個(gè)條件，判斷錯(cuò)誤概率的上限為，L為任意發(fā)送端到接收端的最大距離。所以判斷錯(cuò)誤的概率取決于檢驗(yàn)測(cè)試的次數(shù)T。

本文所用的方法，不需要檢驗(yàn)以上2個(gè)約束條件，因此，不會(huì)在判斷網(wǎng)絡(luò)對(duì)齊是否可行時(shí)出現(xiàn)錯(cuò)誤。用本文的方法進(jìn)行網(wǎng)絡(luò)對(duì)齊，只要滿足條件(18)就可行，而檢驗(yàn)這個(gè)條件也比較簡(jiǎn)單。

4 結(jié)論

本文針對(duì)三單播有向無(wú)延遲非循環(huán)網(wǎng)絡(luò)，應(yīng)用漸近干擾對(duì)齊技術(shù)分析了當(dāng)發(fā)送端發(fā)送不同大小的數(shù)據(jù)流時(shí)，采取的網(wǎng)絡(luò)對(duì)齊策略所要滿足的約束條件。由于傳統(tǒng)約束條件過(guò)多，只能用隨機(jī)測(cè)試決定是否可行，使實(shí)際檢驗(yàn)比較困難。而本文聯(lián)合圖論中最短路徑遺傳算法和網(wǎng)絡(luò)線性性質(zhì)計(jì)算網(wǎng)絡(luò)可進(jìn)行PBNA的約束條件，將網(wǎng)絡(luò)對(duì)齊約束條件簡(jiǎn)化為2個(gè)方程，降低檢驗(yàn)的復(fù)雜度，提高系統(tǒng)“無(wú)干擾”傳輸?shù)目赡苄浴?/p>

［1］KOETTER R，MEDARD M.An algebraic approach to network coding［J］.IEEE/ACM Transaction on Networking，2003，11(5):782－795.

［2］CADAMBE V，JAFAR S.Interference alignment and the degrees of freedom of the k user interference channel［J］.IEEE Transaction on Information Theory，2008，54(8):3425－3441.

［3］JAFAR S，SHAMAI S.Degrees of freedom region for the MIMO X channel［J］.IEEE Transaction on Information Theory，2008，54(1):151－170.

［4］謝顯中，熊澤波，白立平.感知蜂窩網(wǎng)中具有多主用戶的干擾對(duì)齊算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2014，26(1):1－7.

XIE Xianzhong，XIONG Zebo，BAI Liping.Interference alignment algorithm with multiple primary users in cognitive cellular networks［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2014，26(1):1－7.

［5］RAMAKRISHNAN A，DAS A，MALEKI H，et al.Network coding for three unicast sessions:Interference alignment approaches［C］//IEEE.48thAnnual Allerton Conference on Communication，Control，and Computing.Allerton IL:IEEE Press，2010:1054－1061.

［6］HAN Jaemin，WANG Chihchun，SHROFF N B.Analysis of precoding－based intersession network coding and the corresponding 3－unicast interference alignment scheme［C］//IEEE 49thAnnual Allerton Conference on Communication，Control，and Computing(Allerton).Monticello:IEEE Press，2011:1033－1040.

［7］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.

［8］DAS A，VISHWANATH S，JAFAR S，et al.Network coding for multiple unicasts:An interference alignment approach［C］//IEEE.IEEE International Symposium Information Theory Proceedings(ISIT).Texas:IEEE Press，2010:1878－1882.

［9］GANESAN A，BAVIRISETTI T D，PRASAD K，et al.A generalized network alignment for three－source three－destination multiple unicast networks with delays［J］.IEEE Information Theory Workshop(ITW)，2011，16(20):573－577.

［10］CHUN Meng，RAMAKRISHNAN A，MARKOPOULOU A，et al.On the feasibility of precoding－based network alignment for three unicast sessions［C］//IEEE.IEEE International Symposium Information Theory Proceedings(ISIT).Cambridge:IEEE Press，2012:1907－1911.

［11］GANESAN A，BAVIRISETTI T D，RAJAN B S.On the feasibility of Network Alignment for three－source threedestination multiple unicast networks with delays［C］//IEEE.IEEE Global Communications Conference(GLOBECOM).Anaheim CA:IEEE Press，2012，3(7):2274－2279.

［12］KRISHNAMURTHY S R，JAFAR S A.Precoding based network Alignment and the capacity of a finite field X channel［J］.IEEE International Symposium on Information Theory Proceedings(ISIT)，2013，7(12):2701－2705.

［13］KOETTER R，MEDARD M.Beyond routing:an algebraic approach to network coding［C］//IEEE.IEEE Computer and Communications Societies，Twenty－First Annual Joint Conference of the Proceedings(INFOCOM).Washington:IEEE Computer Society Press，2002:122－130.