基于終端協同的并行多流速率分配算法研究

耿瑞芳，張 暉，楊龍祥，朱洪波

（南京郵電大學 江蘇省無線通信重點實驗室，江蘇 南京 210003）

新興多媒體業務和無線應用需求的不斷增長，極大地促進了移動終端的發展。在泛在環境下，用戶將處于多個終端以及多個網絡中，為充分利用用戶周圍的網絡和終端資源，基于終端協同的通信技術應運而生[1-2]。多終端協同是指利用用戶側的多個終端間的協同關系，即多個終端可通過短距離通信技術連接以便共享其廣域通信能力，從而實現無線網絡及終端資源的高效利用以及提高用戶業務體驗[3]。目前，多數終端可通過短距離無線通信技術轉發業務數據，如藍牙、IEEE802.11、ZigBee等，為終端協同提供了可能[4]。

在數據流形式上，基于終端協同的多流并行傳輸即將業務數據劃分為不同的子流，在若干終端間通過短距離傳輸能力為某個終端轉發，并最后在此終端匯聚。業務數據的多路徑分流傳輸是多終端協同的研究重點，而由文獻[5]的多終端協同分流傳輸的研究可知，接入信道的終端數目將會極大影響WLAN系統容量和服務率，從而影響協同傳輸系統的性能（時延、吞吐量）。因此，在終端協同分流算法中，要綜合考慮終端以及其接入網的特性。

文獻[6]研究了在蜂窩網中對下載文件通過終端協同進行分流傳輸的算法，但算法未考慮網絡的異構性。文獻[7]研究了視頻流在無線網絡中基于終端協同的分流傳輸算法，但此算法未考慮各終端以及其接入網絡的特性，將視頻流在各協同終端中平均分配傳輸。文獻[8]對終端協同中的能耗問題進行了研究，但對于各終端間的分流也只是簡單地平均分配，未體現終端性能的不同。文獻[9]提出了異構網絡下基于傳輸時間以及基于層次分析的終端協同分流算法，但由于層次分析法的判斷矩陣受決策者判斷水平及個人喜好主觀因素影響，使分流算法具有主觀隨意性。因此，本文提出一種多屬性決策的終端協同分流算法。在該算法中，在考慮終端用戶主觀喜好的基礎上，同時考慮各終端及其接入網絡之間的客觀差異。由于目前綠色通信、節能環保受到越來越多的關注[10]，在本文提出的終端協同分流算法中還考慮了終端的能耗問題。

1 系統模型

1.1 應用場景

圖1為多終端協同分流傳輸的應用場景。在圖1中，處于泛在環境下的用戶終端兩類無線接口，一種用于用戶短距離通信（Short Range，SR），另外一種用于長距離通信（Long Range，LR），并假設SR通信的數據速率將遠遠大于LR通信鏈路之間的速率。其中有一個稱為主終端Master，其周圍存在著一些可被選擇進行協同分流傳輸的終端即從終端Sla?ver。Master與Slaver之間通過短距離通信技術進行通信，終端通過廣域網接口與應用服務器連接。當主終端發起業務時，依據各終端以及其接入網的特性，以實現效用函數最大為目標，確定協同分流傳輸方案，服務器對數據進行分流，分別通過不同的路徑到達從終端，最后分流數據通過短距離無線通信技術在主終端匯聚，完成整個業務的傳輸。令MT0表示主終端，M={1,2,…,M}表示泛在環境下候選的從終端集合。令N={1,2,…},N 表示接入網絡。接入到網絡n中的終端MTm稱為虛擬終端(m,n)。假設終端只能同時接入到一個網絡中，則從終端以及其接入網絡共有M×N種組合。用M×N階矩陣S表示表示虛擬終端的可用性。若(m,n)可用，則Smn=1，否則，Smn=0。即

其中，1≤ m≤ M，1≤ n≤ N 。

對可用的虛擬終端集合，即Smn=1的虛擬終端，用子集aS表示。

圖1 終端協同分流傳輸應用場景

1.2 系統模型

此處只研究無線鏈路部分，對有線鏈路不做研究，則可得系統模型如圖2所示。

圖2 終端協同分流傳輸示意圖

2 基于終端協同的分流優化算法

本文提出的多屬性決策的終端協同分流傳輸速率分配算法通過計算終端接入網的下載速率、鏈路時延、用戶代價以及終端能耗4個因子的權重，得到協同終端及其接入網的性能值，從而進行速率分配。

2.1 權重確定

2.1.1 層次分析法

在層次分析法中，權重的確定可體現用戶的主觀喜好以及業務要求。權重可通過以下3個過程確定。

1）標準化終端及其接入網絡屬性

在本文所提算法中，考慮終端的下載速率、鏈路時延、用戶代價以及終端能耗4個因子，其權重表示為

并有

將測量到的屬性值用矩陣Fi來表示

對于屬于越小越好型的鏈路時延屬性、代價屬性以及終端能耗屬性，標準化公式為

從而可得一個新的標準化屬性矩陣如

2）建立判斷矩陣

將終端接入網的下載速率、鏈路時延、用戶代價以及終端能耗4個屬性進行兩兩比較，并按照重要程度排列等級。比較結果用判斷矩陣為

3）權重確定

此處，權重的確定采用文獻[13]中的方法，即通過對判斷矩陣中的元素求幾何平均值來得到各因子的權重

進行歸一化，可得

2.1.2 熵值分析法

由于層次分析法的判斷矩陣受決策者判斷水平及個人喜好主觀因素的影響，使分流算法具有主觀隨意性。因此，在本文提出的多屬性決策的終端協同分流算法中，在考慮終端用戶主觀喜好的基礎上，也考慮各終端及其接入網絡之間的客觀差異，即基于信息熵理論，求解各因子所占的權重。

由信息論知識可知，某一屬性在不同終端及接入網絡間的差異越大，則信息熵越小，此時此因子的權重就越大。

用Di表示因子i在不同終端及接入網絡間的差異，則有

則可得因子i的權重為

為綜合考慮終端用戶主觀喜好以及各終端及其接入網絡之間的客觀差異，需將上述兩個方法得到的權重進行分配，即得綜合權重

其中，0＜α＜1。

2.2 終端選擇

為評估所選終端及其接入網的性能，構造效用函數如

在終端協同中，設候選終端的個數為y，但網絡并不一定有y個，因為可能有多個終端接入到同一個網絡中。協同終端算法主要分為兩部分，即終端選擇和速率分流。

終端選擇的具體步驟為：

1）列出所有虛擬終端的組合，從而得到虛擬終端組合矩陣S；

2）測量得到所有虛擬終端的4個屬性值，即矩陣Fi；

3）更新所有可用虛擬終端矩陣aS；

4）由式（15）計算所有可用終端的效用函數值Umn；

5）對終端m接入到不同網絡的效用值從大到小進行排列，最大值對應的終端及其接入網記為MaxUmn，同時令Smt=0,1≤ t≤ N ，且t≠ n，以防止相同的終端進行重復選擇；

6）MaxUmn對應的所有可用虛擬終端即進入候選終端集合。

2.3 速率分配

此時，候選終端在前文已經選出。設選出的協同終端的個數為c，則1≤ c≤ y。

速率分配的具體步驟為：

2）初始化協同終端數目，即令c=1；

4）更新可用帶寬RBm；

5）判斷PreRatem≤RBm是否成立。若成立，再判斷m=c是否成立；否則，令c=c+1；

6）判斷1≤ c≤ y是否成立。若成立，跳轉到步驟2）；否則更新候選終端集合，重新進行速率分配；

7）若m=c成立，速率分配結束；否則，跳轉到步驟3）繼續。

多流速率分配算法流程如圖3所示。

3 算法性能分析

在此部分，通過假設一些網絡參數以及終端參數，根據系統模型進行仿真，從而對所提算法進行性能分析，并與其他算法進行性能比較。

圖3 速率分配流程圖

3.1 仿真參數設定

假設系統網絡環境由UMTS、WLAN1、WLAN2三種網絡組成，其編號為1～3，終端個數為10，并進行編號1～10。假設有4個終端只分布在UMTS網絡中，3個終端可同時接入到UMTS和WLAN1中，剩余3個終端可同時接入到UMTS和WLAN2中，具體網絡參數如表1所示。另外，假設終端在UMTS中下載速率在0～200 kbit/s隨機分配，在WLAN1中下載速率在300～600 kbit/s隨機分配，在WLAN2中下載速率在500～800 kbit/s隨機分配。

表1 網絡參數

為了驗證所提算法的性能，與如下兩種算法進行性能比較：

DOS（Delay-only Selection）算法，進行從終端選擇時以系統時延最小為目標來進行選擇。

AHP算法，進行從終端的選擇時只考慮用戶喜好，并不考慮網絡以及終端間的客觀差異。

根據前文描述，本文在進行仿真驗證時以實時業務為例進行算法性能分析，并建立實時業務的網絡屬性判斷矩陣

由此判斷矩陣可得實時業務在AHP算法中的權重因子為 ω'=（0.250 7，0.598 1，0.096 8，0.054 4）。本文算法中計算所得的權重因子為 ω =（0.390 6，0.438 0，0.103 1，0.068 3）。

由式（9）、（13）、（14）可計算得出AHP方法的權重以及本文提出算法的權重，然后由式（15）得到所有可用終端的效用值，并進行從大到小的排列。

3.2 性能分析

在進行業務傳輸時，利用多終端協同對系統性能的影響就是可提高資源整合能力，從而提供系統的吞吐量，降低系統時延。此部分通過此算法的系統效用、系統時延、系統能耗以及系統負載4個方面進行分析。

本文算法以系統效用最大為目標，對選出候選終端效用由大到小進行排列，即得候選終端組合（（8，3），（6，2），（7，2），（10，3），（9，3），（1，1），（5，2），（2，1），（3，1），（4，1））。AHP算法只考慮用戶主觀喜好，其候選終端組合順序為（（10，3），（6，2），（8，3），（9，3），（5，2），（1，1），（2，1），（7，2），（4，1），（3，1））。DOS算法以系統時延最小為目標，其選出的候選終端組合順序為（（9，3），（10，3），（8，3），（10，3），（6，2），（7，2），（5，2），（2，1），（4，1），（4，1），（3，1））。

由圖4可知，隨著從終端數目的增加，系統效用并未增加。因為本文算法中候選終端組合的效用是從大到小進行排列的，在進行終端協同時，優先選用效用最大的終端進入虛擬終端系統，因此，隨著從終端數目的增加，系統效用反而是下降的。由于在系統效用的表示中，本文算法綜合考慮了終端的下載速率、網絡的時延、用戶代價以及能耗等因素，而AHP算法僅考慮用戶主觀喜好，剛開始選擇的從終端并非效用最大，因此，當效用值較大的從終端進入虛擬終端系統時，其系統效用會增加。DOS算法也是同樣原理，由于WLAN2網絡中終端時延相同，其在終端8～10中隨機選擇，因此DOS算法的系統效用先增大后減小。由圖3可知與AHP算法以及DOS算法相比，在從終端數目較少時，本文算法具有很大優勢。但隨著從終端數目的增加，3種算法的差距并不明顯。但本文算法的系統效用仍然是最大的。

圖4 不同從終端數目下的系統效用

由圖5可知，隨著從終端數目的增加，系統時延是減少的。此處的時延考慮的是業務請求的接入等到時延。但隨著協同終端的增加，時延的下降變得平緩。在圖5中，DOS算法的時延最小，因為此算法只關心時延，并不考慮能耗等其他性能，優先選擇時延小的終端進入虛擬終端系統。但由圖6可知，其能耗最大。

圖5 不同從終端數目下的系統時延

圖6 不同從終端數目下的系統能耗

圖6給出了采用不同協同終端數目下的協同能耗。與不采用多流傳輸的方式相比，基于終端協同的多流傳輸將會極大地減少能耗，但隨著協同終端數目的增加，SR通信接口所需的能耗增加，將導致整個系統的能耗也隨著增加，但仍低于傳統的傳輸方式的能耗。

通過圖5的時延以及圖6的能耗的比較可知，在進行終端選擇時，不能只根據網絡或終端性能的某一項指標實現局部最優選擇，要綜合權衡多方面的因素，才能使得系統效用最大。

以業務速率R=15 Mbit/s為例，分析各網絡采用不同終端數目時其負載狀況，由圖7所示。在本文算法中，通過比較終端所分配速率以及網絡可用帶寬，進行速率調整。假設在此業務請求之前各網絡為空載狀態，則由圖7可知，在M=1時無法響應業務請求，故通過速率調整，令M=2再進行速率分配。由圖7還可知，當M=3時也需要進行速率調整方可滿足網絡帶寬約束以及用戶需求。

圖7 R=15 Mbit/s時不同終端數目下的各網絡負載

圖8給出了R=15 Mbit/s時采用不同協同終端數目時各終端所分配的速率。由圖8的走勢可知，隨著協同終端數目的增多，各終端間分配的速率差異越來越小。這樣并不能充分發揮出效用值較大的終端的優勢，因此，隨著協同終端數目的增加，圖5中時延的減少越來越不明顯。在圖8的速率分配中可看出，當由多個終端進行協同多流傳輸時，是根據選擇的虛擬終端的性能按比例進行速率分配的，并非根據接入網絡的可用帶寬進行階梯分配。此種分配方式保證了不同用戶間的公平性，讓所有用戶都有機會利用最優的虛擬終端。

圖8 R=15 Mbit/s時不同終端數目下各終端所分配速率

由上面的仿真圖4～8可知，采用本文所提出的從終端選擇算法以及本文的速率分配算法時，在滿足用戶需求的前提下，所選擇的從終端越少，系統效用越好。同時，終端的干擾范圍會隨著協同終端個數按比例擴大，有可能會影響到無線網絡的空間頻分復用。因此，在滿足業務QoS要求的同時，應盡量減少協同終端的數目以減少干擾范圍。

4 結論

為充分利用用戶周圍的網絡資源以及終端資源，為用戶提供更優質的用戶體驗，終端協同成為研究熱點。本文針對終端協同時的多流并行傳輸問題，提出了一種多流速率分配算法。此算法在實現從終端選擇的同時完成了各協同終端之間的速率分配。通過仿真所做出的性能分析表明，在算法中所提出的速率調整，不僅能夠充分利用優勢網絡的資源，還可滿足網絡資源的約束，同時也能滿足用戶業務體驗。

[1] YIPING C，YUHANG Y.A new 4G architecture providing multi?mode terminals always best connected services[J].IEEE Wireless Communications，2007，14（2）：36-41.

[2] 李若翩，阮雅端，陳啟美.基于協同技術的智能車載系統[J].電視技術，2014，38（13）：158-161.

[3] ALKANJ L，SAAD W，DAWY Z.A game theoretic approach for content distribution over wireless networks with mobile-to-mo?bile cooperation[C]//Proc.Personal Indoor and Mobile Radio Com?munications(PIMRC)，2011 IEEE 22nd International Symposium on.[S.l.]：IEEE Press，2011：1567-1572.

[4] STOLARZ D.Peer-to-peer streaming media delivery[C]//Proc.First International Conference on Peer-to-Peer Computing.[S.l.]：IEEE Press，2001：48-52.

[5] 胡陶軍.異構網絡下多終端協同的網絡控制技術研究[D].北京：北京郵電大學，2013.

[6] POPOVA L，HERPEL T，GERSTACKER W，et al.Cooperative mobile-to-mobile file dissemination in cellular networks within a unified radio interface[J].Computer Networks，2008，52（6）：1153-1165.

[7] ALCHIKHANI S，ALKANJ L，DAWY Z.Video distribution over wireless networks with mobile-to-mobile cooperation[C]//Proc.International Conference on Advances in Computational Tools for Engineering Applications.ACTEA'09.[S.l.]：IEEE Press，2009：519-522.

[8]ALKANJ L，ABDALLAH M，DAWY Z.On optimal mobile termi?nal grouping in energy aware cooperative content distribution net?works[C]//Proc.Wireless Communications and Networking Confer?ence.[S.l.]：IEEE Press，2012：2367-2372.

[9] REN S，LIU Y，YANG X，et al.Two traffic distribution approach?es in terminal cooperation over heterogeneous wireless networks[C]//Proc.19th IEEE International Conference on Networks.[S.l.]：IEEE Press，2013：1-6.

[10] HE A，AMANNA A，TSOU T，et al.Green communications:A call for power efficient wireless systems[J].Journal of Communi?cations，2011，6（4）：340-351.

[11] SUN L，TIAN H，SUN Q，et al.Traffic allocation scheme with co?operation of WWAN and WPAN[J].IEEE Communications Let?ters，2010，14（6）：551-553.

[12]KANNO I，YAMAZAKI K，IKEDA Y，et al.Adaptive energy cen?tric radio access selection for vertical handover in heterogeneous networks[C]//Proc.Wireless Communications and Networking Conference.[S.l.]：IEEE Press，2010：1-6.

[13]LAHBY M，CHERKAOUI L，ADIB A.Hybrid network selection strategy by using M-AHP/E-TOPSIS for heterogeneous networks[C]//Proc.8th International Conference on Intelligent Systems:Theories and Applications.[S.l.]：IEEE Press，2013：1-6.