基于遗传算法的三单播网络对齐及优化

张 琴，雷维嘉，谢显中，朱茂娟

(重庆邮电大学移动通信重庆市重点实验室，重庆400065)

0 引言

目前单播是无线和有线网络的主要传播形式，高效利用网络资源的单播传输方法是一个重要的研究内容。对于网络中存在的干扰问题，以往研究的主要任务就是设计并完善会话间网络编码(intersession network coding，INC)方法。在文献［1］中，“干扰”是由一个单播流传输到另一个流的期望目的端，它可以影响每个数据流传输的速度，同时也指出，只要能够满足苛刻的限制条件，“无干扰”传输是可能的。

干扰对齐(interference alignmen，IA)［2－4］技术是为了解决通信系统中干扰和容量问题而提出的，最近的文献［5－12］也将IA技术应用于单播网络中，以实现干扰信号的对齐，提高系统性能。

文献［5］提出了网络对齐(network alignment，NA)技术，一般有2种方法，一种是在网络边缘进行IA，而在网络内部进行随机线性网络编码(random linear network coding，RLNC);另一种是IA和NC都在网络内部进行。预编码基础上的网络对齐(precoding－based network alignment，PBNA)是在发送端设计预编码，在接收端设计干扰抑制矩阵，在网络中进行网络编码。采用PBNA后，每对单播会话能够达到1/2的自由度(degree of freedom，DOF)。

在文献［6］中，应用干扰对齐的思想，并与网络编码相结合，证明了三符号扩展时网络对齐的可能性，构成了三单播渐近网络对齐(3－unicast asymptotic network alignment，3－ANA)方法，给INC方法带来了新的方向。文献［7］重点设计预编码(发送端)和解码(接收端)矩阵，在网络内部，依然可以应用网络编码生成当地编码核(local encoding kernels)。

与无线干扰信道相比，网络的最大不同就是其传输矩阵是相关的，就是说在一些网络中PBNA是不能实现的［8］。文献［8－9］分别在瞬时和延迟单播网络中，联合应用渐近干扰对齐技术与线性网络编码技术，设计特殊的预编码矩阵，并给出实现PBNA的约束条件。但是这些约束条件太多，在实际中还无法检验。对于三单播网络，文献［10－11］在文献［8－9］的基础上把约束条件减少为4个，但是其中有2个条件依然不能检验，还需要进一步简化，以便能用拓扑结构检验。文献［12］研究了在2用户X网络中，设计预编码矩阵和进行网络对齐所要满足的条件。

本文在上述文献［8－11］的基础上，针对三单播有向无延迟非循环网络，应用渐近干扰对齐技术研究各用户发送3个不同数据流m，n，p时的预编码矩阵，并分析网络对齐的可行条件;进一步，联合图论中最短路径遗传算法和网络线性性质计算网络可进行PBNA的约束条件，将网络约束条件简化为2个方程，降低检验的复杂度，并进行实际检验。

1 网络模型

对于一个无延迟非循环的有向图G=(V，E)，这里V表示节点的集合，E表示边的集合，网络中的一条边用(a，b)表示，a，b为网络中的2个节点。入度(指有向图中终止于某点的边的数目)为零的节点称作发送端，出度(指有向图中起始于某点的边的数目)为零的节点称作接收端。用head(e)和end(e)表示一条边的终点和起点，若e=(a，b)，则a=end(e)，b=head(e)。我们研究一个多单播网络，有K个发送端s1，s2，…，sK，K个接收端d1，d2，…，dK，其中，任意di期望收到si发送的信号。网络中每条边的容量为1，每个发送端发送的信息相互独立。

一条路径由一系列相邻的边e1e2…ek组成，其中，head(ei)=end(ei+1)，∀i∈{1，2，…，k－1}，e1和ek是这条路径的起始边和结束边，表示为Pe1ek。当a=end(e1)和b=head(ek)时，也可以把路径Pe1ek表示为Pba。用a≺b表示a是b的上游点，即点a能到达点b。同样地，用ei≺ej表示边ei能到达边ej。对于路径P，用ei∈P来表示路径P经过边ei。用xeiej表示边ei到达边ej的编码系数(当地预编码核)。如果对于图G=(V'，E')和G=(V，E)，有V'⊆V，E'⊆E则称图G'是图G的子图(subgraph)。我们在无延迟非循环网络(DAG)图中，考虑多单播问题，其中，一个源—目的(发送端—接收端)对记为(sk，dk);用ki表示传输的信息符号的数量大小;每个信息符号取自有限域Fp;用变量x表示编码系数，me1:e2(x)表示边e1到边e2的边增益，表示为

(1)式中，Pe1e2表示边e1到e2的路径，边e'，e″相邻。由文献［13］可知，只有当e1≺e2时，me1:e2(x)才是一个非零多项式，特别当e1=e2时其中表示包含2l个元素的有限域，l为随机数)。发送端si与接收端dj的信道增益为

(2)式中:Pji表示所有的从发送点si到接收点dj路径;ℯ(P)表示沿着路径P的每一条边的编码系数乘积。假设mji(x)非零，则mji(x)是一个多项式和。

(3)式中:Mji是一个从发送端si到接收端dj的增益矩阵，为(m+p)×(m+p)的对角矩阵，对角线的(t，t)元素为mji(xt)，其中，xt表示si到dj在t时刻网络的编码核;V1，V2，V3分别为(m+p)×p，(m+p)×m，(m+p)×n的矩阵。

与干扰对齐方法相同，为了在接收端消除干扰，恢复出期望信号，需要在每个接收端dj设计干扰消除矩阵Uj，解码后得到的符号向量为

按照干扰对齐要求［2－3］，为实现预编码网络对齐，达到压缩干扰空间维数的目的，预编码矩阵Vi和干扰抑制矩阵Uj需满足条件

(5)式中，I表示单位矩阵。由于网络传输矩阵Mji的相关性，要满足以上的约束条件，网络拓扑结构需要满足一些必要的条件。

2 预编码网络对齐的可行性条件分析

在无线干扰信道中，信道增益是独立的，并且是服从连续分布的随机变量，干扰对齐一定可行。而网络信道增益取决于网络拓扑结构，导致某些传输矩阵相关。因此，需要新的条件来确定网络对齐可行。

2.1 预编码矩阵设计

由于本文发送数据流大小不同，根据系统网络模型，本文的预编码网络对齐要求满足

(7)式中:A为m×m单位矩阵的前n列;B为p×p单位矩阵的前n列;C为p×p单位矩阵的前m列。

(8)式中，pi(x)，ψ(x)是对角矩阵Pi和T的元素。由TV1B=V1CA可知，预编码矩阵的设计依赖于ψ(x)是否恒定。

当ψ(x)恒定时，即T=Im+p，又因为B=CA，所以任意的V1都满足。

当ψ(x)不恒定时，预编码的选择就不是那么自由了，我们设计的预编码矩阵为

(9)式中，w=(1，1，1，…，1)T是m+p行的列向量。根据以上设计的预编码矩阵，能够满足条件

2.2 网络对齐可行性条件分析

根据文献［10］，以上(10)式的3个条件可以简写成

不幸的是，由于(11)式包含的条件数量太多，在实际中不可能逐一验证，可以将其转化为如下定理。

定理1当且仅当对任意i∈{1，2，3}，条件(12)满足时，网络对齐是可行的。

(12)式中，pi(x)不是一个任意的函数，而是一个跟传输矩阵相关的函数。所以要简化(11)式，首先要引入图论的一个性质。

可以看出，pi(x)具有与h(x)同样的特殊结构，可以表示为

对于 路 径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是一个非零常数。假设(P1，P2)∈Pab×Ppq和(P3，P4)∈Paq×Ppb，设为起点b到不同终点a，p共同边的集合Paq∩Ppq}为起点q到不同终点a，p共同边的集合，为不同起点b，q到终点a共同边的集合Ppq}为不同起点b，q到终点p共同边的集合，分别从集合中选取一条边设为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')。

当l'=0，因为dσ=il=1且i在0－k中取值，i与l只能等于1，所以，当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')。

当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，所以矛盾。

由以上证明可知，当k≥k'，k只能等于1，k≤k'的证明方法和k≥k'时一样。即约束条件缩减到

在之前文献中，为了更好地体现约束条件与网络图结构的关系，αi，βi考虑比较小的常数值，即αi=0，1，βi=0，1。由于本文采用最短路径遗传算法，即选择每个发送端到每个接收端的最短路径，所以从条件(15)的情况下进行再次优化即可。

3 基于最短路径遗传算法的可行性条件优化

以上分析的网络对齐可行性约束条件无法少于4个，并且只能通过随机测试确定其中的2个条件是否满足，不能保证实际检验的精确度。但运用遗传算法，能够减少网络对齐约束条件。遗传算法能够在网络中选择发送端到接收端的最短路径，使信号沿着固定路径传输，传输矩阵的元素都简化为单项式，以上的约束条件可减少为能根据网络拓扑结构检验的2个，并且降低了不同期望信号传输时经过同一条边的概率。

在研究路由问题时，一个网络可表示成一个加权图G=(N，E)，其中，N表示节点集，E表示连接节点的通信链路集。|N|和|E|分别表示该网络中的节点数和链路数，Cij为链路(i，j)的代价，代价矩阵为C=［Cij］。源节点和目的节点分别用S和D表示，每个链路的连接用zij表示，定义为

由元素zij构成的矩阵为Zij，显然，Zij对角线的元素为0且满足条件:若zij=1，且zjk=1，则zik=1。用这种定义，最短路径问题就可转化为求最小值的优化问题，目标函数可表示为

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

根据以上目标函数，在图G中找到一个子图G'，使发送端1，2，3分别到接收端1，2，3都有一条最短路径，如此，在G'中，mij(x)就是关于变量的单项式，即每个发送端到接收端只有单独一条路径。由于遗传算法求出全局最优解时间复杂性很大，可以通过限定遗传代数的方法，求出一个性能较好的次优解来。然而，在每一个发送端选择到3个接收端的最短路径时，由于网络中间节点过多，9个路径很有可能经过相同的边，所以路径之间依然有可能是相关的，如此，对齐约束条件依然需要

在图G'中检验条件(18)的方法如下。

1)pi(x)≠1情况。

由文献［10］中的引理2，当且仅当路径对(P1，P2)∈(Pab，Ppq)和(P3，P4)∈(Paq，Ppb)没有共同边，即P1∩P2=Ø且P3∩P4=Ø时pi(x)=可验证。

2)pi(x)≠ψ(x)情况。文献［8］的引理4，检验这2个条件，判断错误概率的上限为，L为任意发送端到接收端的最大距离。所以判断错误的概率取决于检验测试的次数T。

本文所用的方法，不需要检验以上2个约束条件，因此，不会在判断网络对齐是否可行时出现错误。用本文的方法进行网络对齐，只要满足条件(18)就可行，而检验这个条件也比较简单。

4 结论

本文针对三单播有向无延迟非循环网络，应用渐近干扰对齐技术分析了当发送端发送不同大小的数据流时，采取的网络对齐策略所要满足的约束条件。由于传统约束条件过多，只能用随机测试决定是否可行，使实际检验比较困难。而本文联合图论中最短路径遗传算法和网络线性性质计算网络可进行PBNA的约束条件，将网络对齐约束条件简化为2个方程，降低检验的复杂度，提高系统“无干扰”传输的可能性。

［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］谢显中，熊泽波，白立平.感知蜂窝网中具有多主用户的干扰对齐算法［J］.重庆邮电大学学报:自然科学版，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.