多跳多接口無線網絡中的協作路由

謝 鯤，王 玲

湖南大學 信息科學與工程學院，長沙 410082

1 引言

協作通信技術利用單天線移動終端之間的相互協作，共享彼此的天線，形成虛擬的MIMO系統，從而獲得空間分集效應。因其能夠抵抗無線信道衰落，提升系統性能，成為近年來通信領域的研究熱點之一。

現有的協作通信研究主要可以分為兩類：一類是在單跳無線網絡中的協作通信，主要研究在兩個無線通信節點之間如何選擇一個或者多個協作中繼節點，進行資源的最優分配以獲得最大性能。如文獻[1-3]研究了單跳無線網絡中協作中繼節點選擇和功率分配問題。另一類是在多跳無線網絡中的協作通信，研究多跳網絡中如何尋找協作路由來增加傳輸可靠性[4-5]，以及如何聯合協作路由和協作中繼選擇提高網絡傳輸容量等[6]。

在多接口無線網絡中，可以為每一個無線節點配備多接口。現有的研究表明，相比于單接口網絡，多接口網絡可以提高傳輸性能和可靠性。然而，現有針對多接口無線網絡中協作通信研究還十分有限，僅文獻[7]考慮了多接口網絡環境下協作傳輸問題。但是，文獻[7]是在給定路由的情況下再進行接口的分配，無法動態為業務流進行路由選擇，并不能為多條數據流提供最優的性能。

多接口協作網絡可以為網絡通信提供更多的資源，使得節點在發送的過程中能夠有更大的空間來選擇下一跳流量轉發節點和協作節點。而且，在多接口協作無線網絡中，節點的多個接口既可以服務某些數據流的直接傳輸，又可以為另外一些數據流提供協作通信服務。如何在多個數據流存在的情況下，合理地在多個數據流中進行接口分配，聯合考慮路由和中繼節點選擇來最大化網絡性能，成為多跳多接口協作無線網絡實現的關鍵和難點。

為解決該問題，本文首先分析在新的網絡場景下聯合路由選擇和中繼分配的問題模型。根據網絡場景建立各個約束條件，將本文中最大化最小數據流速率的路由選擇和中繼分配問題建模為一個混合整數線性規劃問題。然后，提出分支定界（branch and bound）的聯合路由選擇和中繼分配算法，該算法利用分支定界的思想將原問題分解為多個子問題來獲得最優解。在具體實現中，將解空間用上下界來逼近，在算法迭代過程中更新上下界，當上下界之差小于某個給定的小數值時，當前的整數解集則為最優解，該最優解對應了最優的路由和中繼節點分配情況。

2 網絡模型與問題描述

2.1 三個節點的協作通信模型

協作通信技術是適合于單天線用戶的空間分集技術，它利用無線信道的廣播特性，允許單天線終端設備在多用戶環境中共享它們的物理資源來進行通信，形成虛擬天線陣列。

參與協作通信的設備可相互轉發信息，同一信息的多個復本能夠通過相互獨立的無線信道到達接收端。圖1給出了協作通信的三節點通信模型，這里s是源節點，d是目標節點，r是協作中繼節點。圖1中的信源節點s和協作中繼r形成相互獨立的通信信道，這樣信源節點發送的多個信號復本通過相互獨立的信道到達接收端，便可產生分集增益。相比于傳統的直接傳輸，協作通信可達到更高的吞吐量、更低的誤碼率并消耗更少的能量[8-9]。盡管三節點協作通信模型很簡單，但是協作通信的具體實現機制卻并不是唯一的。在文獻[10]中，使用一種時隙模型來傳輸。然而由于正交信道模型比時隙模型更容易分析和處理，并很容易轉為使用頻率分集、時間分集或者碼域分集，所以正交信道的使用已經在協作通信中被廣泛接受[1，4，11-13]。類似于文獻[6]的協作通信協議，本文也采用正交信道來研究協作通信。在多跳多接口網絡環境中，每個節點使用單獨的信道，并能夠在不同信道中同時無自干擾地傳輸和發送數據。

圖1 三節點協作通信模型

在協作傳輸模型中，根據中繼轉發節點處理信號機制的不同，有兩種常用的通信模式：放大轉發和解碼轉發。本文采取放大轉發模式，下面給出在放大轉發模式下源節點s和目的節點d之間可達速率計算公式。

如圖1所示，中繼節點r接收、放大并轉發來自于源節點s的信號到目的節點d。hsd、hsr、hrd分別表示s和d，s和r，r和d之間的路徑損耗、陰影和衰落等影響。zd和zr分表表示在節點d和r上的零均值，且方差分別為、。為了簡便，假設一個節點的背景噪聲在不同的信道上都有相同的隨機特性。Ps和Pr分別表示在節點s和r處的傳輸功率。

根據文獻[6]可知，放大轉發模式下，在s和d之間由r作為協作中繼的情況下可達到的速率為：

如果源節點和目標節點采用直接傳輸方式，即源節點s直接發送數據到目的節點d，則可達速率為：

CD(s，d)=wlb(1+SNRsd)

2.2 數學模型

2.2.1 網絡場景和定義

本文考慮存在多條數據流的多跳多接口協作無線網絡，如圖2所示，每個節點配備兩個網卡，每個網卡使用單獨的信道收發信息，且每個節點可以同時為兩條流服務。

圖2 網絡場景說明圖

網絡中有n個節點，記為集合N；網絡中J條流，記為集合F={f1，f2，…，fJ}。那么節點集合N包含三部分：（1）J個源節點，記為集合Ns={s1，s2，…，sJ}；（2）J個目的節點，記為集合Nd={d1，d2，…，dJ}；（3）L個中間節點，記為集合Nr={r1，r2，…，rL}。因此有n=J+J+L=2J+L。

根據中間節點在數據流傳輸中的作用，可以分為兩類。一類是多跳傳輸中繼（Multi-hop Relay，MR），與傳統路由中多跳轉發節點功能相同，本文中的MR傳輸中繼作為多跳路由的轉發節點來轉發數據包（如圖2中為f1服務的r2、r5、r7和為f2服務的r1、r4、r6和r7），下面定義0-1變量T(i，u，v)來形式化表示多跳傳輸中繼MR：

這里節點u和v都是流fi中的MR。

另一類用于節點之間的協作轉發，即幫助源節點傳輸數據給目的節點的協作者，稱為協作傳輸中繼（Cooperative Relay，CR）（如圖2中為f1服務的r3和r6和為f2服務的r2和r3），發送節點、接收節點和協作傳輸中繼共同組成如圖1所示的協作傳輸模塊。這里同樣定義0-1變量G(i，u，w，v)來表示協作傳輸中繼CR：

這里，節點u和v仍為fi的MR，節點w為CR。

2.2.2 問題的描述和建模

首先根據網絡中各個節點為網絡數據流服務和中繼轉發的功能出發，分析網絡中各個節點在聯合路由選擇和中繼分配問題中的約束條件。

（1）源節點：每條流是從相應的源節點出發，所以源節點必有流出，即

文中假設源節點和目的節點不能作為MR，即除了作為初始節點或者目的節點之外，若為其他流服務只能作為中繼轉發節點，也就是CR，所以有：

（2）目的節點：目的作為本條流的終止節點，其一定有流入，即

類似于源節點，目的節點為其他流做中繼轉發節點，也最多只能為一條流服務，即：

（3）中間節點：

①作為MR，一個中間節點u作為MR為某條流fi服務，則必有流入和流出，所以中間節點u在fi這條流中下一跳之和應該滿足

上一跳之和應該滿足

由于流入和流出是同時存在，所以

②作為CR，為某條流fi服務的另一種方式就是作為協作中繼CR，但是也只能為其中的某一跳作為中繼，則有：

而且中間節點u為fi這條流服務的時候就只能作為MR或者CR，二者只能取其一，則有：

然后就整個網絡來說，由于假設源節點和目的節點為其他流服務時不作為MR，所以源節點是沒有流入的，目的節點是沒有流出的，即：

就整個網絡來講，某個中間節點u最多只能為兩條流服務，也就是：兩個MR或者兩個CR；一個MR一個CR；一個MR或者一個CR。不參與網絡服務，所以有：

若網絡中某條流fi中流經(u，v)，若w為(u，v)的中繼轉發節點應滿足：

假設每條流的速率為ci，那么為了確保路由的可用性，就必須考慮網絡中每一跳的容量限制，所以對fi的每一跳(u，v)都有：

2.2.3 問題的形式化描述

網絡中有n個節點，J條數據流，本文的目標是通過優化多條流路由和協作中繼分配來最大化最小的數據流的速率。若Cmin表示這J條流中最小的流速，即Cmin=min{c1，c2，…，cJ}，那么本文目標就是最大化Cmin。

條件（16）是由兩個變量相乘的非線性限制約束條件。為了簡便求解，需要將該非線性約束轉化成一個線性約束：

根據式（15）可知，當T′=0的時候，G′=0，所以G′T′=G′，當T′=1的時候，G′T′=G′，因此式（16）還可以簡化為：

在上述條件中，式（5）、（7）等價于式（5）、（6）、（7），因此可以忽略條件（6）；式（7）、（9）等價于式（7）、（9）、（10），因此也可以忽略條件（10）。

本文的最大化最小數據流的聯合路由選擇和中繼分配問題可以形式化表示如下：

分析可知式（18）是一個混合整數線性規劃問題（MILP），所有的約束條件都是線性約束，Cmin是目標函數，T(i，u，v)和G(i，u，w，v)是決策變量，一旦所有數據流的T變量和G變量確定后，路由選擇和中繼分配即可確定。通常來說MILP問題是一個NP-hard問題[14-15]。為了求解該問題，本文提出一種啟發式算法。

3 基于分支定界的聯合流路由和中繼節點分配算法JFRBB

分支定界法（Branch and Bound）是一種系統地搜索解空間的方法，它隱式地將所有決策變量組合的解都求出來然后取最優值。通過定界直接刪除一些目標函數值明顯低于當前最優值的某些變量值，不再對其分支，從而減少搜索空間，減少空間復雜度，提高算法效率。因此，分支定界法求出的解通常為優化問題的最優解。

本文基于分支定界思想的聯合流路由和中繼節點分配算法具體步驟，如圖3所示。

圖3 基于分支定界思想的聯合流路由和中繼節點分配算法

如對于一個求最大值的混合整數線性優化問題（18），表示為P，其決策變量（0-1變量）集合為X，分支定界第一步就是先忽略決策變量的整數限制，得到一個非整數解集X0和目標函數值UB0。

然后選擇P的任意整數可行解集X00（如所有變量都取0）代入P得到另一個目標函數值LB0。這時取P得最優目標函數值的上界UB=UB0，下界LB=LB0，用一個整數解集Y=X00，如圖4（a）所示。

接下來從這個非整數解集X0中找出任意一個非整數變量x1開始分支成兩個子問題，P1：x1=0和P2：x1=1。分別對P1和P2進行求松弛解，過程同第一步，則對于P1，可以得到一個非整數解集X1和目標函數值UB1，以及一個整數解集X11和目標函數值LB1。同樣對于P2，也可以得到一個非整數解集X2和對應的目標函數值UB2，以及一個整數解集X22和對應的目標函數值LB2，如圖4中（b）所示。

（1）如果LB1＜LB，LB2＞LB，表明P1這個分支得到的整數解沒有當前整數解好，則刪除P1這個子問題，就是不再對其進行分支，并取UB=UB2，LB=LB2，Y=X22，判斷是否滿足UB≤(1+ε)LB（ε＞0，是一個給定的誤差值），如果上述不等式成立，則分支定界算法結束，LB對應的整數解集Y則為要求的決策變量解集，LB則為目標函數值；否則就從非整數解集X2中再任取一個非整數變量xi分支成兩個新的子問題繼續求解，過程同上述分支一樣。

圖4 分支定界步驟

（2）同理如果LB2＜LB，LB1＞LB，表明P2這個分支得到的整數解沒有當前整數解好，則刪除P2這個子問題，即不再對其進行分支，并取UB=max{UB，UB1}，LB=LB1，Y=X11，同上面一樣判斷是否滿足UB≤(1+ε)LB，如果上述不等式成立，則分支定界算法結束，LB對應的整數解集Y則為要求的決策變量解集，LB則為目標函數值；否則就從非整數解集X1中再任取一個非整數變量xi分支成兩個新的子問題繼續求解。

（3）如果LB1＞LB，LB2＞LB，表明分支后兩個子問題所得到的整數解都優于當前整數解，則取UB=max{UB1，UB2}，LB=max{LB1，LB2} ，同樣判斷是否滿足UB≤(1+ε)LB，如果上述不等式成立，則分支定界算法結束，LB對應的整數解集Y則為要求的決策變量解集，LB則為目標函數值；否則就依次從非整數解集X1和非整數解集X2中任取一個非整數變量來分支成兩個新的子問題繼續求解，如圖4（c）所示為子問題P2的分支。

（4）如果LB1＜LB，LB2＜LB，表明有當前的整數解優于兩個分支所得的整數解，因此對這兩個問題都不在分支。

上述過程結束后的分支求解類似于P問題的分支過程，算法結束的標志都為上UB≤(1+e)LB或者所有分支灰沒有可行解，LB對應的整數解集為當前的最優解集，LB為目標函數值。

4 仿真實驗

4.1 實驗設置

本文通過仿真實驗來驗證提出的聯合優化路由和中繼節點算法的有效性。

在仿真實驗中，沿用文獻[12]的參數設置，假設每個接口帶寬W=22 MHz，每個節點的最大傳輸功率設為1 W。為了方便計算，假設hsd只包含節點s到d的傳播增益，所以|hsd|2=||s-d||-4，這里||s-d||是節點s和d之間的距離，路徑損耗參數設為4，給定的誤差值ε=0.1；并假設所有節點噪音的方差為10-10W。

圖5 JFRBB-Multi-Radio-Cooperative路由

網絡拓撲如圖5所示，在大小為1 000 m×1 000 m的范圍內隨機生成16個節點。其中4個源節點，4個目的節點，8個中繼節點，也就是n=16，J=4，L=8。圖中實線表示節點之間存在直接通信的鏈路，虛線箭頭表示協作通信鏈路。目前多接口協作無線網絡中的研究還十分有限，因此本文對比三種不同的網絡場景和路由算法來分析本文所提算法的性能。

第一種在雙接口協作網絡中，實現本文提出的JFRBB算法，即為每個數據流找到協作路由的同時確定每個接口中繼分配情況（即MR和CR分配情況），表示為JFRBB-Multi-Radio-Cooperative。

第二種在雙接口無協作傳輸的網絡中為每條數據流利用JFRBB算法找出最優路由，表示為JFRBB-Multi-Radio-Noncooperative。在這個場景中，由于沒有協作節點協作轉發，因此，每個節點的兩個接口最多只能同時作為MR為兩條流服務。由于沒有了協作節點轉發，具體實現中，將JFRBB算法中所有的G變量賦值為0，此時的決策變量只有T。

第三種在單接口協作網絡中，利用 JFRBB算法為每個數據流找出最優的協作路由，并進行中繼分配，表示為JFRBB-Single-Radio-Cooperative。由于網絡場景為單接口網絡，每個節點只有一個接口，因此每個節點只能作為MR或者CR為某一條流服務。具體實現中將JFRBB算法所有的接口數目限制設為1，即在問題（19）的數學模型中，約束條件（13）、（14）的接口數目限制改為1。

4.2 實驗結果

圖5給出了JFRBB-Multi-Radio-Cooperative網絡中的路由結果，圖6和圖7分別為JFRBB-Multi-Radio-Noncooperative網絡路由情況和JFRBB-Single-Radio-Cooperative網絡的路由情況。網絡中各條流的速率如表1所示，可以看出在JFRBB-Multi-radio-cooperative網絡路由中，由于每個節點可以為多條流服務，節點既可以作為MR又可以作為CR，所以由此算法得到的網絡性能是最好的。而在JFRBB-Multi-Radio-Noncooperativ網絡中，雖然每個節點也是多個接口，但是網絡節點只能作為MR，沒有了協作分集的優勢，網絡中各條流的速率比JFRBB-Multi-Radio-Cooperative路由的速率要小。在JFRBB-Single-Radio-Cooperative網絡中，雖然有協作節點的轉發，但是網絡中各個節點只有一個接口，只能服務于一條流，使得有些有優勢的節點得不到充分的利用，從而降低了網絡性能。

圖6 JFRBB-Multi-Radio-Noncooperative路由

表1 網絡中各條數據流速率比較 （Mb·s－1）

圖8給出了三種情況下各個網絡中的最小速率，可以看出JFRBB-Multi-Radio-Cooperative路由的最小速率比JFRBB-Multi-Radio-Noncooperative和JFRBB-Single-Radio-Cooperative網絡的最小速率均高出將近43%。圖9給出了各個網絡中的聚合流量，由圖可以看出，在JFRBB-Multi-Radio-Cooperative路由情況下聚合流量比JFRBB-Multi-Radio-Noncooperative網絡和JFRBB-Single-Radio-Cooperative網絡的聚合流量分別高出16.4%和30.7%。

上述實驗結果表明，一方面，由于協作通信帶來的協作分集效應，協作通信可以進一步提高多接口無線網絡的性能；另一方面，多接口為協作傳輸的MR和CR分配帶來了多樣性的選擇，可以為協作通信服務，進一步提高網絡性能。

圖9 網絡中聚合流量比較

5 總結

協作通信可以充分利用網絡中的節點資源，通過節點間的協作來幫助有通信需求的節點進行高速、可靠的無線通信。本文在多接口多跳網絡中，聯合流路由和中繼節點選擇，為各條數據流尋求一條最優路徑，使得各條流之間以較為均衡的速率傳輸數據。由于多接口能夠使一個節點服務于多條流，所以多接口網絡中的節點更能充分地發揮自己的優勢，來最大限度提高網絡吞吐量。仿真實驗結果表明，基于分支定界的聯合流路由和中繼節點分配算法能夠提高網絡傳輸速率，并公平實現各條數據流的帶寬分配。

[1]Cai J，Shen S，Mark J W，et al.Semi-distributed user relaying algorithm for amplify-and-forward wireless relay networks[J].IEEE Transactions on Wireless Communications，2008，7（4）：1348-1357.

[2]Shi Y，Sharma S，Hou Y T，et al.Optimal relay assignment for cooperative communications[C]//Proceeding of ACM MobiHoc，Hongkong，China，May 27-30，2008：3-12.

[3]Zhao Y，Adve R，Lim T J.Improving amplify-and-forward relay networks：optimal power allocation versus selection[C]//Proc IEEE International Symposium on Information Theory，Seattle，USA，July 9-14，2006：1234-1238.

[4]Scaglione A，Goeckel D L，Laneman J N.Cooperative communications in mobile ad hoc networks[J].IEEE Signal Processing Magazine，2006，23（5）：18-29.

[5]Yeh E M，Berry R A.Throughput optimal control of cooperative relay networks[J].IEEE Transactions on Information Theory，2007，53（10）：3827-3833.

[6]Sharma S，Shi Y，Hou Y T，et al.Cooperative communications in multi-hop wireless networks：joint flow routing and relay node assignment[C]//Proc of IEEE Infocom 10，2010.

[7]Li Xiaoguang，Wu Jie.Channel on demand：optimal capacity for cooperative multi-channel multi-interface wireless mesh networks[C]//Proceedings of the Conference on Mobile Adhoc and Sensor Systems（MASS），2010：412-421.

[8]Khandani A E，Abounadi J，Modiano E，et al.Cooperative routing in static wireless networks[J].IEEE Transactions on Communications，2007，55（11）：2185-2192.

[9]Li F，Wu K，Lippman A.Energy-efficient cooperative routing in multi-hop wireless ad hoc networks[C]//Proc of the 25th IEEE International Performance，Computing，and Communications Conference，April 10-12，2006：215-222.

[10]Laneman J N，Tse D N C，Wornell G W.Cooperative diversity in wireless networks：efficient protocols and outage behavior[J].IEEE Transactions on Information Theory，2004，50（12）：3062-3080.

[11]Gurewitz O，de Baynast A，Knightly E W.Cooperative strategies and achievable rate for tree networks with optimal spatial reuse[J].IEEE Transactions on Information Theory，2007，53（10）：3596-3614.

[12]Hunter T E，Nosratinia A.Diversity through coded cooperation[J].IEEE TransactionsonWirelessCommunications，2006，5（2）：283-289.

[13]Savazzi S，Spagnolini U.Energy aware power allocation strategies for multi-hop cooperative transmission schemes[J].IEEE Journal on Selected Areas in Communications，2007，25（2）：318-327.

[14]Garey M R，Johnson D S.Computers and intractability：a guide to the theory of NP-completeness[M].New York：WH Freeman and Company，1979.

[15]Pochet W L A.Production planning by mixed integer programming[M].Now York：Springer-Verlag，2006.