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

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

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

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

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

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

1 系統(tǒng)模型

1.1 應(yīng)用場景

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

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

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

圖1 終端協(xié)同分流傳輸應(yīng)用場景

1.2 系統(tǒng)模型

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

圖2 終端協(xié)同分流傳輸示意圖

2 基于終端協(xié)同的分流優(yōu)化算法

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

2.1 權(quán)重確定

2.1.1 層次分析法

在層次分析法中，權(quán)重的確定可體現(xiàn)用戶的主觀喜好以及業(yè)務(wù)要求。權(quán)重可通過以下3個過程確定。

1）標(biāo)準(zhǔn)化終端及其接入網(wǎng)絡(luò)屬性

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

并有

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

對于屬于越小越好型的鏈路時延屬性、代價屬性以及終端能耗屬性，標(biāo)準(zhǔn)化公式為

從而可得一個新的標(biāo)準(zhǔn)化屬性矩陣如

2）建立判斷矩陣

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

3）權(quán)重確定

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

進行歸一化，可得

2.1.2 熵值分析法

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

由信息論知識可知，某一屬性在不同終端及接入網(wǎng)絡(luò)間的差異越大，則信息熵越小，此時此因子的權(quán)重就越大。

用Di表示因子i在不同終端及接入網(wǎng)絡(luò)間的差異，則有

則可得因子i的權(quán)重為

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

其中，0＜α＜1。

2.2 終端選擇

為評估所選終端及其接入網(wǎng)的性能，構(gòu)造效用函數(shù)如

在終端協(xié)同中，設(shè)候選終端的個數(shù)為y，但網(wǎng)絡(luò)并不一定有y個，因為可能有多個終端接入到同一個網(wǎng)絡(luò)中。協(xié)同終端算法主要分為兩部分，即終端選擇和速率分流。

終端選擇的具體步驟為：

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

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

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

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

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

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

2.3 速率分配

此時，候選終端在前文已經(jīng)選出。設(shè)選出的協(xié)同終端的個數(shù)為c，則1≤ c≤ y。

速率分配的具體步驟為：

2）初始化協(xié)同終端數(shù)目，即令c=1；

4）更新可用帶寬RBm；

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

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

7）若m=c成立，速率分配結(jié)束；否則，跳轉(zhuǎn)到步驟3）繼續(xù)。

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

3 算法性能分析

在此部分，通過假設(shè)一些網(wǎng)絡(luò)參數(shù)以及終端參數(shù)，根據(jù)系統(tǒng)模型進行仿真，從而對所提算法進行性能分析，并與其他算法進行性能比較。

圖3 速率分配流程圖

3.1 仿真參數(shù)設(shè)定

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

表1 網(wǎng)絡(luò)參數(shù)

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

DOS（Delay-only Selection）算法，進行從終端選擇時以系統(tǒng)時延最小為目標(biāo)來進行選擇。

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

根據(jù)前文描述，本文在進行仿真驗證時以實時業(yè)務(wù)為例進行算法性能分析，并建立實時業(yè)務(wù)的網(wǎng)絡(luò)屬性判斷矩陣

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

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

3.2 性能分析

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

本文算法以系統(tǒng)效用最大為目標(biāo)，對選出候選終端效用由大到小進行排列，即得候選終端組合（（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算法以系統(tǒng)時延最小為目標(biāo)，其選出的候選終端組合順序為（（9，3），（10，3），（8，3），（10，3），（6，2），（7，2），（5，2），（2，1），（4，1），（4，1），（3，1））。

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

圖4 不同從終端數(shù)目下的系統(tǒng)效用

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

圖5 不同從終端數(shù)目下的系統(tǒng)時延

圖6 不同從終端數(shù)目下的系統(tǒng)能耗

圖6給出了采用不同協(xié)同終端數(shù)目下的協(xié)同能耗。與不采用多流傳輸?shù)姆绞较啾龋诮K端協(xié)同的多流傳輸將會極大地減少能耗，但隨著協(xié)同終端數(shù)目的增加，SR通信接口所需的能耗增加，將導(dǎo)致整個系統(tǒng)的能耗也隨著增加，但仍低于傳統(tǒng)的傳輸方式的能耗。

通過圖5的時延以及圖6的能耗的比較可知，在進行終端選擇時，不能只根據(jù)網(wǎng)絡(luò)或終端性能的某一項指標(biāo)實現(xiàn)局部最優(yōu)選擇，要綜合權(quán)衡多方面的因素，才能使得系統(tǒng)效用最大。

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

圖7 R=15 Mbit/s時不同終端數(shù)目下的各網(wǎng)絡(luò)負(fù)載

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

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

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

4 結(jié)論

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

[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] 李若翩，阮雅端，陳啟美.基于協(xié)同技術(shù)的智能車載系統(tǒng)[J].電視技術(shù)，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] 胡陶軍.異構(gòu)網(wǎng)絡(luò)下多終端協(xié)同的網(wǎng)絡(luò)控制技術(shù)研究[D].北京：北京郵電大學(xué)，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.