摘  要： 对双源双宿两跳级联网络进行了研究，提出了一种TDD模式下可达的网络容量。首先，考虑一个由三个节点级联组成的双源双宿两跳网络模型：首节点是第一信源（S1），其对应信宿为尾节点（D1）；尾节点也作为第二信源（S2）；中间节点既是S2对应的信宿（D2），也是S1到D1的中继。网络工作在时分双工（TDD）模式，中继采用解码转发（DF）策略。其次，利用最大流-最小割原理获得了网络容量的外界，并证明其可达性。对于获得的容量结论，利用线性规划数学方法寻找最佳的时隙分配方案，并通过具体实例进行分析验证。分析表明，调节时隙分配可以优化容量。

　　关键词： 双源双宿；时分双工；最大流-最小割；容量区域；线性规划

0 引言

　　随着无线通信技术的发展，通信系统的容量成为备受关注的重要特性。容量问题最早源于Shannon在1961年发表的双向信道的论文[1]。这篇论文中Shannon定义了多址接入信道，随后Ahlswede对多址接入信道提出了描述[2]。Cover首次提出广播信道模型，而中继信道最初是由Van der Mullen针对三终端模型提出的[3]。Mohammad等人[4]针对一般多终端网络（包括中继网络、级联网络）研究了可达速率。本文作者分析了分层TDD模式下，多跳无线通信系统的自由度，并针对单源单宿多跳级联网络，分别研究了定向和全向传播两种模式下的可达速率[5-6]，但对于在跳数限制下存在源宿重合和双向通信的双源双宿，以至更一般的多源多宿情况还未提及。

　　目前学术界对半双工单源单宿级联网络已有丰富的研究成果，但对于多源多宿级联网络，研究成果仍比较匮乏。由于全双工模式自干扰严重，实际中为降低成本大多采用半双工模式。本文考虑采用时分双工（TDD）通信系统模型，旨在对双源双宿两跳级联网络的容量区域进行研究，重点对不同情况下各个网络状态的调度问题进行分析讨论。

　　该模型针对最简单的两跳级联网络，其研究结论是更复杂的多跳网络的基础。除了可以用于LTE中继模式，该模型还可以应用于车辆或船舶组网。例如，在船舶通信领域中，船舶之间通常会组成链式队列展开海上航行。当队列中船舶之间需要互相传递消息时，消息可以从一艘船接力传递给下一艘船，处于中间位置的船只需要在准确分离接收自己所需要的消息之后，再将其他的消息向下一艘船只传递出去。这种消息的传递方式组成一种单源（或多源）对多宿的链式级联通信网络。

1 系统模型

　　考虑如图1所示的双源双宿单重合单覆盖信道模型：S1、S2分别代表两个源节点，D1、D2分别代表对应的两个宿节点，其中S2和D1节点重合。S1、S2源节点分别有消息x1、x2要发送给宿节点D1、D2。由于是单覆盖模型，每个节点仅能收到相邻节点发出的消息。此外TDD模式限制了中间节点不能同时进行接收与发送。因此D2节点在传输x1时，将作为中继节点，接收到x1后采用解码转发（DF）策略将x1转发给目的节点D1。故当所传消息x1、x2都不为空时，系统完成这两个消息的传输可以由以下四个网络状态组成：

　　状态1：源节点S1将消息x1发送给D2节点；

　　状态2：D2节点将消息x1转发给宿节点D1；

　　状态3：S2节点将消息x2发送给宿节点D2；

　　状态4：源节点S1和S2分别将消息x1、x2同时发送给D2节点，即采用多址接入（MAC）模式。

　　由于采用TDD模式，需要给每个状态分配对应一段时隙。用tm表示第m个网络状态的时隙分配。如图2所示。

　　为便于计算消息速率，设上述四个网络状态的总传输过程在单位时间内完成，共有4个时隙，因此：

　　每个节点都以满功率发送消息，进行消息的无差错传输。为使模型更一般化，假设同一链路在不同状态下具有不同的容量。

2 容量区域分析

　　2.1 网络信息论基础

　　引理1：最大流-最小割定理：在网络流图中，任意一个割把网络中所有节点划分成两个集合S和T，其中源点s∈S，汇t∈T，从s到t的最大流量的值等于最小的割的容量。

　　图论中的最小割定理最先由Ford和Fulkerson给出。参考文献[7]中阐述并证明了该定理的可行性。该定理表明在网络流图中源节点和宿节点之间的最大流量不大于任何一个分割源和宿的边集上的和流量，也就是说任何一个边割集的流量和便是源和宿之间流量的一个上界。

　　2.2 容量区域

　　首先分析容量区域的外界。从网络信息论基础可知，可利用最大流-最小割定理寻找信息网络容量的外界。由于模型采用TDD，割集须考虑链路激活时间。根据割集定理，可将双源双宿两跳级联网络根据其网络状态和链路状态进行切割，然后对两个消息分别进行合并，可得关于两个消息的速率上界。如下所示：

　　关于消息x1在第一跳上的割集：

　　R11≤t1c1+t4c4（2）

　　关于消息x1在第二跳上的割集：

　　R12≤t2c2（3）

　　关于消息x2在第二跳上的割集：

　　R22≤t3c3+t4c5（4）

　　根据引理1，源节点和宿节点之间的最大流量等于其中最小的割集容量。故消息x1的可达速率以min（R11，R12）为上界，消息x2的可达速率以R22为上界，消息x1与消息x2的和速率以min（R11，R12）+R22为上界。

　　综合以上讨论，可得双源双宿无线网络系统的容量区域外界：

　　为便于讨论，进行以下变量替换。定义=c2（c4+c5）/（c2+c4），1=c2c4/（c2+c4），2=c2c5/（c2+c4），则有=1+2。对最优时隙分配进行求解，可得容量区域的外界。同时注意到网络模型中采用无差错满速率传输，故理论上该外界即是可达的。因此有下面的定理。

　　定理1：双源双宿无线网络系统的容量区域为：

　　具体表达式将在后面章节给出。下面给出外界中最优时隙分配的证明。

　　证明：根据式（5）可知，对于消息x1，其速率R1的上界是min（R11，R12）。由于是两跳中继，第二跳的速率必然以第一跳的速率为上界；而为了传输的稳定性，第一跳传到中继节点的所有消息都必须及时被转发，才能避免消息在中继节点不断累积所造成的链路拥塞。所以，两跳链路上所传输关于消息的信息量应该平衡，即有：

　　t1c1+t4c4=t2c2（7）

　　取时隙t1和时隙t3为自由变量，利用平衡式（7）和时间归一化约束（1）解出：

　　代入容量区域式（5）可得式（6）所示的容量区域外界。具体可达性分析在下一小节中讨论。

　　2.3 容量可达性分析

　　根据信息论，点对点（PTP）模型最大的消息传输速率就是信道容量。Khojastepour[4]提出了多跳TDD级联网络的容量为：

　　其中{c1，c2，…，cL}是每一跳的链路容量。对于两跳网络而言，上述公式简化为：

　　下面详细讨论R1，R2，R的可达性。

　　2.3.1 只传输x1的情况

　　假设整个系统仅传输消息x1，系统传输状态数目会减少，具体表现为时隙t3和时隙t4对应的传输状态不再存在。

　　此时R1≤min{t1c1，t2c2}，当时，R1上界为。根据Khojastepour提出的两跳级联速率结论（式（10））可知R1能达到上界。

　　2.3.2 只传输x2的情况

　　假设整个系统仅传输消息x2，时隙t3得到全部的传输时间。此时根据式（6），R2上界为c3。由于c3正好是点对点的容量，因此R2能达到上界。

　　2.3.3 消息x1和x2都传输的情况

　　R1、R2同时受到变量t1、t3的影响，可以调节t1、t3使得R最大。具体分析见下节。

3 分析与讨论

　　从容量表达式（6）中可以看出，容量界与系统具体的时隙分配方案有关，因此通过对时隙分配方案进行优化，可以最大化容量的边界。下面分析该模型在消息x1和x2都传输时，如何调度分配自变量时隙t1和时隙t3以使得系统容量上界最大。

　　3.1 关于总速率R的优化问题

　　在单位传输时间的约束下，上述优化问题可以建模为：

　　在上述问题中定义了一个时间分配变量它是t1和t3分配到的时间资源加和。这是一个线性规划问题，可以用图示法来求解。

　　根据t1，t3的约束条件可知，约束区域就是线段直线t1+t3=下面区域，由于，求目标函数的最大值又可以转化为先求目标函数Z的最大值，即。Z=0的直线为=0，其斜率为。如图3所示。

　　3.2 最优时隙分配的具体分析

　　此处讨论在c3<条件下的情况，对于c3>情况类似进行。根据上面问题转化，先按斜率K与-1的关系讨论Zmax最优解。

　　3.2.1 Case A：c3>

　　在此情况下直线Z=0的斜率K<-1，Zmax在横坐标截距点（t1，t3）=（，0）处取得。把此时的t1，t3值带入琢表达式得到：

　　下面结合一个具体网络实例进行说明。其各跳链路容量的选择应满足：c1≥c4，c3≥c5，ci≥0，Case A分类条件：c3>c1（c2-c5）/（c2+c4）。此处选择c1=18，c2=4，c3=3，c4=2，c5=3。

　　在Case A情况下总速率最大值在横坐标截距点处取得，时隙3的时间为零，相应的去掉了时隙3，消息x1和x2用剩余三个时隙进行传输。变量为时隙1和时隙3的时间和，此时为时隙1的时间分配，调节，各消息速率随变量的关系如图4。消息x1需要两跳传输来完成，并且两跳消息量应该平衡，第二跳所需时间会随第一跳时间分配成正比增加，当增大到一定值时，为满足时间总和为单位1，导致t3会为负值，速率R2从而为负。故应对取值范围添加约束：。

　　对于Case A时的双源双宿网络容量区域为：

　　从式（12）可以看出，合理调度时间分配，容量区域与分时（time-sharing）方案相比有所改善（如图5中由（R1，R2）可达到的散点所构成区域，两个截距相连以内区域对应为分时方案所得的容量区域）。当=0时，容量区域最优。此时，系统省去时隙1和时隙3，在中继天线数足够的情况下，仅用时隙2和时隙4即可完成传输，而不需要时隙1和时隙3辅助传输。

　　上述选取的是c3=c5的情况，对于c3>c5进行容量仿真发现容量区域是没有改善的，所以case A前提下不适用于c3>c5的情况。

　　在Case C情况下总速率最大值在纵坐标截距点处取得，时隙1的时间为零，相应的去掉时隙1，消息x1和x2用剩余三个时隙进行传输。变量为时隙1和时隙3的时间和，此时为时隙3的时间分配，调节，各消息速率随变量的关系如图6。

　　调节得到Case C下最优的容量区域如图7。

　　与Case A类似，上述选取c3=c5的情况，对于c3>c5进行容量仿真发现容量区域是有改善的，所以Case C前提下对所有c3≥c5的情况都适用。

4 总结

　　本文根据最大流-最小割定理研究讨论了双源双宿两跳单重合单覆盖网络的容量问题。割集定理提供了求解无线通信网络容量外界的有效方法，利用该方法找到了该模型的容量区域外界，并对其可达性进行了详细分析。建立了数学优化模型分三种情况分析了时隙的分配调度，进行了实例分析验证。可以看出，进行合理的时隙调度后的容量区域位于分时传输对应的容量区域之上，说明本文提出的处理方案是有效的。本文主要针对的是双源双宿的网络模型，对其研究有助于更一般的多源多宿级联网络容量问题的研究。

参考文献

　　[1] SHANNON C E. Two-way communication channels[C]. In：Proc.berkeley Symp. math Statist Probab， 1961：611-644.

　　[2] RUDOFL A. Multi-way communication channels[C]. In Proc. 2nd Int. Symp. Information Theory， Tsahkadsor， Armenian S.S.R，1971：23-52.

　　[3] MEULEN V D. Three-Terminal communication channels[J].Advances in Applied Probability， 1971（3）：120-154.

　　[4] KHOJASTEPOUR M A， SABHARWAL A. Bounds on achievable rates for general multi-terminal networks with practical constraints[D]. Houston： Rice University， 2003.

　　[5] LIU F， ZENG L S. Achievable DF rate for cascaded undirected wireless networks with TDD and hidden-terminal[C].Proc. IEEE/CIC International Conference on Communications in China， 2014：643-647.

　　[6] LIU F， WANG X F， ZENG L S. Fibonacci sequence and  cascaded directed  relay networks with time- division-duplex constraint[C]. Proc. IEEE International Conference on Communications， Sydney， Australia， 2014：5124-5129.

　　[7] 卢开澄，卢华明.图论及其应用[M].北京：清华大学出版社，2005.