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

　　關(guān)鍵詞： 雙源雙宿；時(shí)分雙工；最大流-最小割；容量區(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)絡(luò)（包括中繼網(wǎng)絡(luò)、級聯(lián)網(wǎng)絡(luò)）研究了可達(dá)速率。本文作者分析了分層TDD模式下，多跳無線通信系統(tǒng)的自由度，并針對單源單宿多跳級聯(lián)網(wǎng)絡(luò)，分別研究了定向和全向傳播兩種模式下的可達(dá)速率[5-6]，但對于在跳數(shù)限制下存在源宿重合和雙向通信的雙源雙宿，以至更一般的多源多宿情況還未提及。

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

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

1 系統(tǒng)模型

　　考慮如圖1所示的雙源雙宿單重合單覆蓋信道模型：S1、S2分別代表兩個(gè)源節(jié)點(diǎn)，D1、D2分別代表對應(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)分配對應(yīng)一段時(shí)隙。用tm表示第m個(gè)網(wǎng)絡(luò)狀態(tài)的時(shí)隙分配。如圖2所示。

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

　　每個(gè)節(jié)點(diǎn)都以滿功率發(fā)送消息，進(jìn)行消息的無差錯(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è)分割源和宿的邊集上的和流量，也就是說任何一個(gè)邊割集的流量和便是源和宿之間流量的一個(gè)上界。

　　2.2 容量區(qū)域

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

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

　　R11≤t1c1+t4c4（2）

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

　　R12≤t2c2（3）

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

　　R22≤t3c3+t4c5（4）

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

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

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

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

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

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

　　t1c1+t4c4=t2c2（7）

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

　　代入容量區(qū)域式（5）可得式（6）所示的容量區(qū)域外界。具體可達(dá)性分析在下一小節(jié)中討論。

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

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

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

　　下面詳細(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對應(yīng)的傳輸狀態(tài)不再存在。

　　此時(shí)R1≤min{t1c1，t2c2}，當(dāng)時(shí)，R1上界為。根據(jù)Khojastepour提出的兩跳級聯(lián)速率結(jié)論（式（10））可知R1能達(dá)到上界。

　　2.3.2 只傳輸x2的情況

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

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

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

3 分析與討論

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

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

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

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

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

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

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

　　3.2.1 Case A：c3>

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

　　下面結(jié)合一個(gè)具體網(wǎng)絡(luò)實(shí)例進(jìn)行說明。其各跳鏈路容量的選擇應(yī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情況下總速率最大值在橫坐標(biāo)截距點(diǎn)處取得，時(shí)隙3的時(shí)間為零，相應(yīng)的去掉了時(shí)隙3，消息x1和x2用剩余三個(gè)時(shí)隙進(jìn)行傳輸。變量為時(shí)隙1和時(shí)隙3的時(shí)間和，此時(shí)為時(shí)隙1的時(shí)間分配，調(diào)節(jié)，各消息速率隨變量的關(guān)系如圖4。消息x1需要兩跳傳輸來完成，并且兩跳消息量應(yīng)該平衡，第二跳所需時(shí)間會(huì)隨第一跳時(shí)間分配成正比增加，當(dāng)增大到一定值時(shí)，為滿足時(shí)間總和為單位1，導(dǎo)致t3會(huì)為負(fù)值，速率R2從而為負(fù)。故應(yīng)對取值范圍添加約束：。

　　對于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è)截距相連以內(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的情況，對于c3>c5進(jìn)行容量仿真發(fā)現(xiàn)容量區(qū)域是沒有改善的，所以case A前提下不適用于c3>c5的情況。

　　在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。

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

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

4 總結(jié)

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

參考文獻(xià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， 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] 盧開澄，盧華明.圖論及其應(yīng)用[M].北京：清華大學(xué)出版社，2005.