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

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

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

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

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

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

0　引言

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

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

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

1　系統(tǒng)模型

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

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

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

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

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

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

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

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

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

2　容量區(qū)域分析

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

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

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

2.2容量區(qū)域

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

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

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

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

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

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

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

定理1：雙源雙宿無(wú)線網(wǎng)絡(luò)系統(tǒng)的容量區(qū)域?yàn)椋?/p>

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

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

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

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

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

2.3容量可達(dá)性分析

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

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

下面詳細(xì)討論 R1，R2，R的可達(dá)性。

2.3.1只傳輸 x1的情況

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

2.3.2只傳輸x2的情況

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

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

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

3　分析與討論

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

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

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

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

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

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

圖3　約束區(qū)域

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

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

在此情況下直線Z=0的斜率K＜-1，Zmax在橫坐標(biāo)截距點(diǎn)（t1，t3）=（β，0）處取得。把此時(shí)的 t1，t3值帶入= Zmax+α表達(dá)式得到：

下面結(jié)合一個(gè)具體網(wǎng)絡(luò)實(shí)例進(jìn)行說(shuō)明。其各跳鏈路容量的選擇應(yīng)滿(mǎn)足：c1≥c4，c3≥c5，ci≥0，Case A分類(lèi)條件：c3〉c1（c2-c5）/（c2+c4）。此處選擇 c1=18，c2=4，c3=3，c4=2，c5=3。

對(duì)于Case A時(shí)的雙源雙宿網(wǎng)絡(luò)容量區(qū)域?yàn)椋?/p>

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

上述選取的是 c3=c5的情況，對(duì)于 c3〉c5進(jìn)行容量仿真發(fā)現(xiàn)容量區(qū)域是沒(méi)有改善的，所以case A前提下不適用于c3〉c5的情況。

此情況下直線Z=0的斜率K=-1，Zmax亦可以在橫坐標(biāo)截距點(diǎn)（t1，t3）=（β，0）處取得，與 case A類(lèi)似。

此情況下直線 Z=0的斜率 K〉-1，Zmax在橫坐標(biāo)截距點(diǎn)（t1，t3）=（0，β）處取得。把此時(shí)的 t1，t3值帶入= Zmax+α得到：

在Case C情況下總速率最大值在縱坐標(biāo)截距點(diǎn)處取得，時(shí)隙1的時(shí)間為零，相應(yīng)的去掉時(shí)隙1，消息x1和x2用剩余三個(gè)時(shí)隙進(jìn)行傳輸。變量β為時(shí)隙1和時(shí)隙3的時(shí)間和，此時(shí)為時(shí)隙3的時(shí)間分配，調(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類(lèi)似，上述選取 c3=c5的情況，對(duì)于 c3〉c5進(jìn)行容量仿真發(fā)現(xiàn)容量區(qū)域是有改善的，所以 Case C前提下對(duì)所有 c3≥c5的情況都適用。

4　總結(jié)

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

［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］盧開(kāi)澄，盧華明.圖論及其應(yīng)用［M］.北京：清華大學(xué)出版社，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í)聯(lián)網(wǎng)絡(luò)容量研究 ［J］.微型機(jī)與應(yīng)用，2015，34（15）：59-62，66.

2015-04-06）

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

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

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

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