双源双宿单源宿重合TDD两跳级联网络容量研究*

童少康，刘 锋，曾连荪（上海海事大学 信息工程学院，上海 201306）

双源双宿单源宿重合TDD两跳级联网络容量研究*

童少康，刘 锋，曾连荪
（上海海事大学 信息工程学院，上海 201306）

对双源双宿两跳级联网络进行了研究，提出了一种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所示。

图2　四种网络状态及时隙分配

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

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

2　容量区域分析

2.1网络信息论基础

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

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

2.2容量区域

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

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

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

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

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

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

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

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

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

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

取时隙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对应的传输状态不再存在。

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的优化问题

在继续讨论之前，简要介绍几个本文所用表述符号：式（6）中总速率 R的外界用 Rob表示，则 Rob=α+（c3-α）t3+［c1（c2-c5）/（c2+c4）-α］t1，其最大值用表示；使用Z代表 Rob-α，则 Zmax=-α，同样速率 R1的外界用表示；速率 R2的外界用 Ro2b表示，并有关系 Rob=+。

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

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

根据t1，t3的约束条件可知，约束区域就是线段直线t1+t3=β下面区域，由于 Z=Rob-α，求目标函数+的最大值又可以转化为先求目标函数Z的最大值，即=Zmax+α。Z=0的直线为（c3-α）t3+［c1（c2-c5）/（c2+c4）-α］t1= 0，其斜率为如图3所示。

图3　约束区域

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

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

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

下面结合一个具体网络实例进行说明。其各跳链路容量的选择应满足：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时的双源双宿网络容量区域为：

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

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

此情况下直线Z=0的斜率K=-1，Zmax亦可以在横坐标截距点（t1，t3）=（β，0）处取得，与 case A类似。

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

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

图6　Case C：速率与β关系

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

图7　Case C：最优容量区域

与 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，SABHARWALA.Boundson 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.

Capacity of single overlapping two-hop TDD cascaded network with dual sources and dual sinks

Tong Shaokang，Liu Feng，Zeng Liansun
（Information Engineering College，Shanghai Maritime University，Shanghai 201306，China）

The research of two hop cascaded network with dual-sources and dual-sinks had been done and an achievable capacity under TDD constraint was proposed.Firstly，considering a two-hop network model which had dual sources and dual sinks and consisted of three nodes，the head node was the first source（S1）， whose corresponding destination was the tail node（D1），the tail node was also the second source（S2），and the intermediate node was not only a sink related to S2 but also a relay for forwarding message to D1.The network worked at the time division duplex（TDD）mode，and the relay used decode and forward （DF）strategy.Secondly，by using the max-flow-min-cut theory，we found the outbound of network capacity region，and then proved its achievability.We obtained the optimal time allocation for all feasible network state by using the mathematical method of linear programming and analysis and discussion was given by some examples.According to analysis，scheduling time slot allocation can optimized the capacity.

dual sources dual sinks；time division duplexing（TDD）；max-flow min-cut；capacity region；linear programming

TN92

A

1674-7720（2015）15-0059-04

童少康，刘锋，曾连荪.双源双宿单源宿重合TDD两跳级联网络容量研究 ［J］.微型机与应用，2015，34（15）：59-62，66.

2015-04-06）

童少康（1990-），男，硕士研究生，主要研究方向：通信与信息系统。

刘锋（1976-），通信作者，男，博士，讲师，主要研究方向：基础网络及无线通信、海洋互联网及水声通信、纳米网络及分子通信。E-mail：liufeng@shmtu.edu.cn。

曾连荪（1962-），男，在读博士，教授，主要研究方向：定位导航系统、无线测控系统、汽车电子系统。

国家自然科学基金（61271283）；上海教委科研创新项目（14YZ113）；上海海事大学科研基金（20120107）