雙源雙宿單源宿重合TDD兩跳級聯(lián)網(wǎng)絡容量研究*

童少康，劉 鋒，曾連蓀（上海海事大學 信息工程學院，上海 201306）

雙源雙宿單源宿重合TDD兩跳級聯(lián)網(wǎng)絡容量研究*

童少康，劉 鋒，曾連蓀
（上海海事大學 信息工程學院，上海 201306）

對雙源雙宿兩跳級聯(lián)網(wǎng)絡進行了研究，提出了一種TDD模式下可達的網(wǎng)絡容量。首先，考慮一個由三個節(jié)點級聯(lián)組成的雙源雙宿兩跳網(wǎng)絡模型：首節(jié)點是第一信源（S1），其對應信宿為尾節(jié)點（D1）；尾節(jié)點也作為第二信源（S2）；中間節(jié)點既是S2對應的信宿（D2），也是 S1到 D1的中繼。網(wǎng)絡工作在時分雙工（TDD）模式，中繼采用解碼轉(zhuǎn)發(fā)（DF）策略。其次，利用最大流-最小割原理獲得了網(wǎng)絡容量的外界，并證明其可達性。對于獲得的容量結(jié)論，利用線性規(guī)劃數(shù)學方法尋找最佳的時隙分配方案，并通過具體實例進行分析驗證。分析表明，調(diào)節(jié)時隙分配可以優(yōu)化容量。

雙源雙宿；時分雙工；最大流-最小割；容量區(qū)域；線性規(guī)劃

0　引言

隨著無線通信技術(shù)的發(fā)展，通信系統(tǒng)的容量成為備受關(guān)注的重要特性。容量問題最早源于Shannon在1961年發(fā)表的雙向信道的論文［1］。這篇論文中 Shannon定義了多址接入信道，隨后Ahlswede對多址接入信道提出了描述［2］。Cover首次提出廣播信道模型，而中繼信道最初是由Van der Mullen針對三終端模型提出的［3］。Mohammad等人［4］針對一般多終端網(wǎng)絡（包括中繼網(wǎng)絡、級聯(lián)網(wǎng)絡）研究了可達速率。本文作者分析了分層TDD模式下，多跳無線通信系統(tǒng)的自由度，并針對單源單宿多跳級聯(lián)網(wǎng)絡，分別研究了定向和全向傳播兩種模式下的可達速率［5-6］，但對于在跳數(shù)限制下存在源宿重合和雙向通信的雙源雙宿，以至更一般的多源多宿情況還未提及。

目前學術(shù)界對半雙工單源單宿級聯(lián)網(wǎng)絡已有豐富的研究成果，但對于多源多宿級聯(lián)網(wǎng)絡，研究成果仍比較匱乏。由于全雙工模式自干擾嚴重，實際中為降低成本大多采用半雙工模式。本文考慮采用時分雙工（TDD）通信系統(tǒng)模型，旨在對雙源雙宿兩跳級聯(lián)網(wǎng)絡的容量區(qū)域進行研究，重點對不同情況下各個網(wǎng)絡狀態(tài)的調(diào)度問題進行分析討論。

該模型針對最簡單的兩跳級聯(lián)網(wǎng)絡，其研究結(jié)論是更復雜的多跳網(wǎng)絡的基礎(chǔ)。除了可以用于LTE中繼模式，該模型還可以應用于車輛或船舶組網(wǎng)。例如，在船舶通信領(lǐng)域中，船舶之間通常會組成鏈式隊列展開海上航行。當隊列中船舶之間需要互相傳遞消息時，消息可以從一艘船接力傳遞給下一艘船，處于中間位置的船只需要在準確分離接收自己所需要的消息之后，再將其他的消息向下一艘船只傳遞出去。這種消息的傳遞方式組成一種單源（或多源）對多宿的鏈式級聯(lián)通信網(wǎng)絡。

1　系統(tǒng)模型

考慮如圖1所示的雙源雙宿單重合單覆蓋信道模型：S1、S2分別代表兩個源節(jié)點，D1、D2分別代表對應的兩個宿節(jié)點，其中 S2和D1節(jié)點重合。S1、S2源節(jié)點分別有消息 x1、x2要發(fā)送給宿節(jié)點 D1、D2。由于是單覆蓋模型，每個節(jié)點僅能收到相鄰節(jié)點發(fā)出的消息。此外TDD模式限制了中間節(jié)點不能同時進行接收與發(fā)送。因此D2節(jié)點在傳輸 x1時，將作為中繼節(jié)點，接收到 x1后采用解碼轉(zhuǎn)發(fā)（DF）策略將 x1轉(zhuǎn)發(fā)給目的節(jié)點 D1。故當所傳消息 x1、x2都不為空時，系統(tǒng)完成這兩個消息的傳輸可以由以下四個網(wǎng)絡狀態(tài)組成：

狀態(tài)1：源節(jié)點S1將消息x1發(fā)送給D2節(jié)點；

狀態(tài) 2：D2節(jié)點將消息 x1轉(zhuǎn)發(fā)給宿節(jié)點 D1；

狀態(tài) 3：S2節(jié)點將消息x2發(fā)送給宿節(jié)點D2；

狀態(tài)4：源節(jié)點S1和S2分別將消息x1、x2同時發(fā)送給D2節(jié)點，即采用多址接入（MAC）模式。

由于采用TDD模式，需要給每個狀態(tài)分配對應一段時隙。用tm表示第m個網(wǎng)絡狀態(tài)的時隙分配。如圖2所示。

圖2　四種網(wǎng)絡狀態(tài)及時隙分配

為便于計算消息速率，設(shè)上述四個網(wǎng)絡狀態(tài)的總傳輸過程在單位時間內(nèi)完成，共有4個時隙，因此：

每個節(jié)點都以滿功率發(fā)送消息，進行消息的無差錯傳輸。為使模型更一般化，假設(shè)同一鏈路在不同狀態(tài)下具有不同的容量。

2　容量區(qū)域分析

2.1網(wǎng)絡信息論基礎(chǔ)

引理1：最大流-最小割定理：在網(wǎng)絡流圖中，任意一個割把網(wǎng)絡中所有節(jié)點劃分成兩個集合S和T，其中源點 s∈S，匯 t∈T，從 s到 t的最大流量的值等于最小的割的容量。

圖論中的最小割定理最先由Ford和Fulkerson給出。參考文獻［7］中闡述并證明了該定理的可行性。該定理表明在網(wǎng)絡流圖中源節(jié)點和宿節(jié)點之間的最大流量不大于任何一個分割源和宿的邊集上的和流量，也就是說任何一個邊割集的流量和便是源和宿之間流量的一個上界。

2.2容量區(qū)域

首先分析容量區(qū)域的外界。從網(wǎng)絡信息論基礎(chǔ)可知，可利用最大流-最小割定理尋找信息網(wǎng)絡容量的外界。由于模型采用TDD，割集須考慮鏈路激活時間。根據(jù)割集定理，可將雙源雙宿兩跳級聯(lián)網(wǎng)絡根據(jù)其網(wǎng)絡狀態(tài)和鏈路狀態(tài)進行切割，然后對兩個消息分別進行合并，可得關(guān)于兩個消息的速率上界。如下所示：

關(guān)于消息x1在第一跳上的割集：

關(guān)于消息x1在第二跳上的割集：

關(guān)于消息x2在第二跳上的割集：

根據(jù)引理1，源節(jié)點和宿節(jié)點之間的最大流量等于其中最小的割集容量。故消息 x1的可達速率以min（，）為上界，消息 x2的可達速率以為上界，消息 x1與消息 x2的和速率以 min（，）+為上界。

綜合以上討論，可得雙源雙宿無線網(wǎng)絡系統(tǒng)的容量區(qū)域外界：

為便于討論，進行以下變量替換。定義 α=c2（c4+c5）/ （c2+c4），α1=c2c4/（c2+c4），α2=c2c5/（c2+c4），則有 α=α1+α2。對最優(yōu)時隙分配進行求解，可得容量區(qū)域的外界。同時注意到網(wǎng)絡模型中采用無差錯滿速率傳輸，故理論上該外界即是可達的。因此有下面的定理。

定理1：雙源雙宿無線網(wǎng)絡系統(tǒng)的容量區(qū)域為：

具體表達式將在后面章節(jié)給出。下面給出外界中最優(yōu)時隙分配的證明。

證明：根據(jù)式（5）可知，對于消息x1，其速率R1的上界是 min（R11，R12）。由于是兩跳中繼，第二跳的速率必然以第一跳的速率為上界；而為了傳輸?shù)姆€(wěn)定性，第一跳傳到中繼節(jié)點的所有消息都必須及時被轉(zhuǎn)發(fā)，才能避免消息在中繼節(jié)點不斷累積所造成的鏈路擁塞。所以，兩跳鏈路上所傳輸關(guān)于消息的信息量應該平衡，即有：

取時隙t1和時隙t3為自由變量，利用平衡式（7）和時間歸一化約束（1）解出：

代入容量區(qū)域式（5）可得式（6）所示的容量區(qū)域外界。

具體可達性分析在下一小節(jié)中討論。

2.3容量可達性分析

根據(jù)信息論，點對點（PTP）模型最大的消息傳輸速率就是信道容量。Khojastepour［4］提出了多跳TDD級聯(lián)網(wǎng)絡的容量為：

其中｛c1，c2，…，cL｝是每一跳的鏈路容量。對于兩跳網(wǎng)絡而言，上述公式簡化為：

下面詳細討論 R1，R2，R的可達性。

2.3.1只傳輸 x1的情況

假設(shè)整個系統(tǒng)僅傳輸消息x1，系統(tǒng)傳輸狀態(tài)數(shù)目會減少，具體表現(xiàn)為時隙t3和時隙t4對應的傳輸狀態(tài)不再存在。

2.3.2只傳輸x2的情況

假設(shè)整個系統(tǒng)僅傳輸消息 x2，時隙 t3得到全部的傳輸時間。此時根據(jù)式（6），R2上界為c3。由于 c3正好是點對點的容量，因此R2能達到上界。

2.3.3消息x1和x2都傳輸?shù)那闆r

R1、R2同時受到變量 t1、t3的影響，可以調(diào)節(jié) t1、t3使得R最大。具體分析見下節(jié)。

3　分析與討論

從容量表達式（6）中可以看出，容量界與系統(tǒng)具體的時隙分配方案有關(guān)，因此通過對時隙分配方案進行優(yōu)化，可以最大化容量的邊界。下面分析該模型在消息x1和x2都傳輸時，如何調(diào)度分配自變量時隙t1和時隙t3以使得系統(tǒng)容量上界最大。

3.1關(guān)于總速率R的優(yōu)化問題

在繼續(xù)討論之前，簡要介紹幾個本文所用表述符號：式（6）中總速率 R的外界用 Rob表示，則 Rob=α+（c3-α）t3+［c1（c2-c5）/（c2+c4）-α］t1，其最大值用表示；使用Z代表 Rob-α，則 Zmax=-α，同樣速率 R1的外界用表示；速率 R2的外界用 Ro2b表示，并有關(guān)系 Rob=+。

在單位傳輸時間的約束下，上述優(yōu)化問題可以建模為：

在上述問題中定義了一個時間分配變量β，它是t1和t3分配到的時間資源加和。這是一個線性規(guī)劃問題，可以用圖示法來求解。

根據(jù)t1，t3的約束條件可知，約束區(qū)域就是線段直線t1+t3=β下面區(qū)域，由于 Z=Rob-α，求目標函數(shù)+的最大值又可以轉(zhuǎn)化為先求目標函數(shù)Z的最大值，即=Zmax+α。Z=0的直線為（c3-α）t3+［c1（c2-c5）/（c2+c4）-α］t1= 0，其斜率為如圖3所示。

圖3　約束區(qū)域

3.2最優(yōu)時隙分配的具體分析

此處討論在 c3＜α條件下的情況，對于 c3〉α情況類似進行。根據(jù)上面問題轉(zhuǎn)化，先按斜率K與-1的關(guān)系討論Zmax最優(yōu)解。

在此情況下直線Z=0的斜率K＜-1，Zmax在橫坐標截距點（t1，t3）=（β，0）處取得。把此時的 t1，t3值帶入= Zmax+α表達式得到：

下面結(jié)合一個具體網(wǎng)絡實例進行說明。其各跳鏈路容量的選擇應滿足：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時的雙源雙宿網(wǎng)絡容量區(qū)域為：

從式（12）可以看出，合理調(diào)度時間分配β，容量區(qū)域與分時（time-sharing）方案相比有所改善（如圖 5中由（R1，R2）可達到的散點所構(gòu)成區(qū)域，兩個截距相連以內(nèi)區(qū)域?qū)獮榉謺r方案所得的容量區(qū)域）。當β=0時，容量區(qū)域最優(yōu)。此時，系統(tǒng)省去時隙1和時隙3，在中繼天線數(shù)足夠的情況下，僅用時隙2和時隙4即可完成傳輸，而不需要時隙1和時隙3輔助傳輸。

上述選取的是 c3=c5的情況，對于 c3〉c5進行容量仿真發(fā)現(xiàn)容量區(qū)域是沒有改善的，所以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的時間分配，調(diào)節(jié)β，各消息速率隨變量β的關(guān)系如圖6。

圖6　Case C：速率與β關(guān)系

調(diào)節(jié)β得到Case C下最優(yōu)的容量區(qū)域如圖7。

圖7　Case C：最優(yōu)容量區(qū)域

與 Case A類似，上述選取 c3=c5的情況，對于 c3〉c5進行容量仿真發(fā)現(xiàn)容量區(qū)域是有改善的，所以 Case C前提下對所有 c3≥c5的情況都適用。

4　總結(jié)

本文根據(jù)最大流-最小割定理研究討論了雙源雙宿兩跳單重合單覆蓋網(wǎng)絡的容量問題。割集定理提供了求解無線通信網(wǎng)絡容量外界的有效方法，利用該方法找到了該模型的容量區(qū)域外界，并對其可達性進行了詳細分析。建立了數(shù)學優(yōu)化模型分三種情況分析了時隙的分配調(diào)度，進行了實例分析驗證。可以看出，進行合理的時隙調(diào)度后的容量區(qū)域位于分時傳輸對應的容量區(qū)域之上，說明本文提出的處理方案是有效的。本文主要針對的是雙源雙宿的網(wǎng)絡模型，對其研究有助于更一般的多源多宿級聯(lián)網(wǎng)絡容量問題的研究。

［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兩跳級聯(lián)網(wǎng)絡容量研究 ［J］.微型機與應用，2015，34（15）：59-62，66.

2015-04-06）

童少康（1990-），男，碩士研究生，主要研究方向：通信與信息系統(tǒng)。

劉鋒（1976-），通信作者，男，博士，講師，主要研究方向：基礎(chǔ)網(wǎng)絡及無線通信、海洋互聯(lián)網(wǎng)及水聲通信、納米網(wǎng)絡及分子通信。E-mail：liufeng@shmtu.edu.cn。

曾連蓀（1962-），男，在讀博士，教授，主要研究方向：定位導航系統(tǒng)、無線測控系統(tǒng)、汽車電子系統(tǒng)。

國家自然科學基金（61271283）；上海教委科研創(chuàng)新項目（14YZ113）；上海海事大學科研基金（20120107）