衰減信道下具有嚴格時延的P2P實時通信傳輸策略

田世坤,唐勝達

(廣西師范大學 數學與統(tǒng)計學院，廣西 桂林 541006)

無線網絡發(fā)展的主要方向是寬帶數據通信和數據實時交互，互聯網和蜂窩通信的增加，對高速通信鏈接的需求也日益增多[1-2]。網絡信息時代的高速發(fā)展，導致網絡信息種類越來越來復雜，網絡安全性挑戰(zhàn)亦不容樂觀[3]。數據交互的爆炸式增長為基站的宏觀調控帶來巨大挑戰(zhàn)。為解決通信調度相關問題，學者們做了很多努力，相關可用技術包括數字用戶線路轉換(DSL)[4]、點對點(P2P)無線通信[5-6]、電纜混合系統(tǒng)[7-8]以及衛(wèi)星鏈路[9-10]等。由于低成本、易實現、高安全性，P2P通信已變得越來越普及。

P2P無線通信使得網絡上的溝通、共享和交互變得更容易、更直接。在P2P無線通信中，利用信道狀態(tài)信息(CSI)對網絡進行跨層優(yōu)化，并提高信道利用率是無線通信優(yōu)化的一個重要問題。近年來，電信工程中基于P2P無線通信網絡的研究有很大發(fā)展,例如，針對長距離P2P鏈路，文獻[11]提出一種滿足遠程點對點密集波分多路復用(DWDM)鏈路需求的網絡設計方法，降低P2P無線通信的錯誤率和Q-Factor；在技術應用上，文獻[12]提出一種基于CSI的物聯網設備的身份認證機制，在衰落信道下考慮數據的實時傳輸；文獻[13]研究在CSI無法觀測時的P2P無線傳輸問題，將調度模型建模為部分可觀測的MDP(POMDP)進行研究；文獻[14]考慮D2D通信調度問題，研究在隨機數據包到達、數據包丟失和異構截止日期等制約下的實時通信策略；基于有限狀態(tài)的Markov信道模型及ARQ重傳協議,文獻[15]考慮數據包從用戶到基站的實時傳輸策略，給出了傳輸策略的閾值結構。

本文提出衰減信道下P2P實時通信模型，與上述文獻相比，本文的主要貢獻如下：1)提出P2P實時通信模型，具體地，在系統(tǒng)模型中加入CSI，彌補了文獻[14]對于CSI相關影響的忽略?？紤]CSI對于P2P實時通信系統(tǒng)的影響，將無線傳輸系統(tǒng)建模為一個有限狀態(tài)的Markov決策過程(FSMDP)。2)引入拉格朗日數乘因子，基于RBP理論證明無線調度問題的可索引性，為設計衰減信道下P2P基于Whittle索引的實時傳輸策略提供理論支持。3)基于衰減信道下P2P實時通信系統(tǒng)，給出P2P的實時通信Whittle索引傳輸策略的封閉表達式，推廣了文獻[15]最優(yōu)傳輸調度策略閾值結構的閾值表達式。

本文其余部分結構如下：第1章描述實時P2P通信模型；第2章構建調度問題的MDP模型；第3章證明P2P實時通信系統(tǒng)的可索引性，并給出Whittle索引封閉解；第4章給出算法分析以及仿真結果；第5章是結語。

1 模型和問題

本文主要考慮衰落信道下P2P實時通信的傳輸調度問題,下面給出P2P實時通信模型。

1.1 模型

考慮離散時間的通信系統(tǒng)，將時間劃分為大小相等的時隙，將時隙集合記為H={0，1，2，…}。由于陰影、多路徑傳播、多用戶干擾和移動性等影響，無線通信信道通常是相關衰落的，類似文獻[16-19]，設衰減信道模型為X={Xt,t∈H}，將衰減信道狀態(tài)分為M個不重疊區(qū)間，每個區(qū)間都映射為一個信道狀態(tài)，記信道狀態(tài)空間為Γ={γ1,γ2,…,γM}，其中M<+∞。假設每個時隙間信道狀態(tài)不發(fā)生改變，不同時隙間信道狀態(tài)可以發(fā)生變化。設信道狀態(tài)轉移概率矩陣為Pc=[pc(γn|γm)]M×M，其中，pc(γn|γm)表示信道狀態(tài)從γm轉移到γn的概率，即

pc(γn|γm)=P(Xt+1=γn|Xt=γm),γm,γn∈Γ。

稱X為Markov衰減信道模型,其中，轉移概率矩陣可通過觀測擬合得到。

本文考慮P2P實時通信，系統(tǒng)將需要傳輸的數據存儲在緩存器中，由發(fā)射器在嚴格時延要求下發(fā)送給接收端。在最大容忍時延內，發(fā)射器必須完成數據傳輸，否則將強制結束該數據傳輸任務，即丟包。設發(fā)射端的傳輸任務(數據)大小為L，最大容忍時延為N, 即發(fā)射端需要在N個時隙內完成L個數據包的傳輸，超過時延的數據包因延時而被丟失。本文假定傳輸任務中的數據包大小給定，且每個時隙內至多只能發(fā)射一個數據包。

如圖1所示，在每個時隙內，系統(tǒng)根據當前狀態(tài)確定是否傳輸數據包，當系統(tǒng)決定傳輸數據包時，發(fā)射端則將數據包發(fā)送給用戶。數據包傳輸受信道狀態(tài)影響，設p(γm)表示信道狀態(tài)為γm時數據包傳輸成功的概率，若傳輸失敗，數據包可允許重傳。當N個傳輸時隙結束時，仍在緩沖區(qū)中等待傳輸的數據包被丟棄，同時，新的傳輸任務以一定概率到達發(fā)射端并開始傳輸。設Q為新的傳輸任務到達發(fā)射端的概率，不失一般性，設每個到達的傳輸任務都具有相同的大小和時延。

圖1 P2P傳輸模型Fig. 1 P2P transmission model

在時刻t，記當前正在傳輸的任務中剩余數據包個數為Bt∈{0,1,…,L}，剩余傳輸時間為Tt∈{0,1,…,N}，記st=(Xt,Tt,Bt)為系統(tǒng)t時刻的狀態(tài)，稱為衰減信道下傳輸任務隨機到達的實時P2P通信模型，st為系統(tǒng)在t∈H時刻的狀態(tài)。本文P2P通信模型是對文獻[14]中模型的推廣。

S={st,t∈H}

(1)

1.2 問題描述

設at表示在時刻t系統(tǒng)采取的動作，具體地，at=1表示在時刻t發(fā)射器傳輸數據包，at=0表示在時刻t發(fā)射器不傳輸數據包。記A={0,1}，稱A為系統(tǒng)的動作空間。設每個數據包傳輸成功時系統(tǒng)可獲得收益r>0，否則收益為0。設時刻t信道狀態(tài)為Xt=γm時的傳輸成本為c(γm)。對P2P通信模型(1)，設g={at(st)|at(st)∈A,st∈S,t∈H}為系統(tǒng)采取的傳輸策略，用R(st,at)表示在時刻t系統(tǒng)獲得的收益，則系統(tǒng)在策略g下的貼現總期望收益為

Vg(st)=

(2)

式中：β∈(0,1)表示貼現因子；[·|st]表示初始狀態(tài)為st時的條件期望。

(3a)

BtI{Tt-=0}=0，

(3b)

則稱g*為系統(tǒng)的最優(yōu)傳輸策略，其中，I{·}表示示性函數。約束條件(3b)表示在傳輸時間截止時刻，傳輸任務中未傳數據包個數為0，即在傳輸截止時刻，系統(tǒng)需完成所有數據包的傳輸。

本文主要目標是求最優(yōu)傳輸策略g*，使得系統(tǒng)在滿足時延約束條件(3b)下，貼現總期望收益(2)最大。

2 調度問題的MDP框架

本章將P2P通信的傳輸調度問題在MDP構架內重構，同時基于MDP理論給出相應最優(yōu)傳輸策略和最大貼現總期望收益算法。

為了在MDP框架下討論P2P通信問題，首先要將帶約束條件(3b)的傳輸調度問題轉換成無約束條件的Markov決策問題。本文采用文獻[20]的思想，引入懲罰函數，當任務在給定傳輸時間內完成時，設懲罰函數為0，而當任務沒有在設定的時限內完成時，則系統(tǒng)會得到一個很大懲罰(負收益)。為了獲得最大收益，系統(tǒng)將規(guī)避那些無法在給定時間內完成傳輸任務的傳輸策略，從而保證時延約束條件(3b) 成立?；谶@一思想，本文分別從狀態(tài)空間、動作空間、轉移概率及收益函數來重構MDP。

① 狀態(tài)空間： S={st=(Xt,Tt,Bt),t∈H}。

② 動作空間： A={0,1}。

③ 轉移概率： 記P(st+1|st,at)表示采用動作at時，系統(tǒng)狀態(tài)從st轉移到st+1的概率。設當前系統(tǒng)狀態(tài)st=(Xt,Tt,Bt)，其中Xt=γm。考慮如下3種情形：

a)當動作at=1，Tt>1時，設Xt+1=γn,?γn∈Γ，系統(tǒng)狀態(tài)轉移到st+1=(Xt+1,Tt-1,(Bt-at)+)的概率為pc(γn|γm)p(γm)，即數據包傳輸成功的概率，其中，(x)+=max{0,x}；系統(tǒng)狀態(tài)轉移到st+1=(Xt+1,Tt-1,Bt)的概率為pc(γn|γm)(1-p(γm))，即數據包傳輸不成功的概率。

b)當動作at=0，Tt>1時，則狀態(tài)以概率pc(γn|γm)轉移到st+1=(Xt+1,Tt-1,Bt)。

c)當Tt<1時，數據包不論傳輸是否完成都會被丟包，即系統(tǒng)以概率Q進入狀態(tài)(N,L)，以(1-Q)進入狀態(tài)(0,0)。

④ 收益函數：引入懲罰函數f(b)，其中b為截止時刻剩余數據包的個數，當b=0時，令f(0)=0，當b≠0時，令f(b)是b的遞增凹函數，即剩余數據包越多，產生的懲罰越大，則系統(tǒng)收益Rt(st,at)為

于是，具有約束條件的P2P 通信調度問題轉換成了無約束條件的無限時間的貼現MDP模型。V(st)滿足如下Bellman方程基于MDP理論可知式(4)存在最優(yōu)平穩(wěn)傳輸策略[21]，利用策略迭代(PI)、值迭代(VI)等算法可求解最優(yōu)策略及最大期望總收益。

(4)

本文研究的P2P實時無線傳輸模型的狀態(tài)空間為|S|=|Γ||N||L|，傳輸任務的增大，或傳輸任務最大容忍時延的增大，將導致系統(tǒng)狀態(tài)空間呈指數增長，從而導致求解過程中需要極大計算力和計算時間，這意味著MDP模型遭受了維數災難。顯然在狀態(tài)空間很大的模型中，值迭代或策略迭代算法的計算難度很大，求解最優(yōu)策略的成本高。

針對上述問題，本文引入拉格朗日數乘因子，將MDP模型轉化為RBP模型，并證明RBP模型的可索引性，進而得出P2P實時通信系統(tǒng)的Whittle索引的封閉表達式，并給出一種時間復雜度低的基于Whittle索引的調度算法?；赪hittle索引的調度算法可以在極少計算成本下得到P2P實時通信系統(tǒng)的調度策略。

3 調度問題的RBP框架

本章基于RBP框架求解近似最優(yōu)傳輸策略。

3.1 基于Whittle索引的RBP框架

記Rw(st,at)=R(st,at)+wI{at=0}，稱Rw為w-補貼收益函數，w為引入的拉格朗日數乘因子，可理解為采取動作0時系統(tǒng)得到的額外補貼。

基于w-補貼收益的最大貼現總期望收益函數Vw(st)可表示為

(5)

為方便表述，給定st∈S ，記

定義2[23]給定狀態(tài)st∈S ，記w*(st)=inf{w|J0(st)≥J1(st)},稱w*(st)是狀態(tài)st的Whittle索引。

定義3[23]若Πw關于w遞增，即對于任意w1、w2∈R，當w1≤w2時，有Πw1?Πw2，則稱P2P實時通信系統(tǒng)具有可索引性。

3.2 基于Whittle索引的調度策略

對任意st=(xt,Tt,Bt)∈S ，令

J(st)=J0(st)-J1(st)。

(6)

顯然，當w=-∞時，J(st)=J(xt,Tt,Bt)=-∞；當w=+∞時，J(st)=+∞。注意到J(st)關于w的連續(xù)性，則存在w，使得J(st)=0。因此，證明狀態(tài)st的Whittle索引唯一存在性，即證方程(6)零解的唯一存在性。

類似文獻[15]中定理1和定理2的證明，可得如下引理1。引理1描述了w*(st)的單調性。

引理1若狀態(tài)st=(Xt,Tt,Bt)∈S ，其中，Xt=γm∈Γ，存在Whittle索引w*(st)，則

①w*(st)關于Tt非增；

②w*(st)關于Bt非減。

引理2給定狀態(tài)st=(Xt,Tt,Bt)∈S ，其中，Xt=γm∈Γ，則

① 當Tt=0時，狀態(tài)st的Whittle索引存在；

② 當Tt≠0,Bt=0時，狀態(tài)st的Whittle索引存在；

③ 當Tt=1時，狀態(tài)st的Whittle索引存在。

證明先證明①。當Tt=0時，必有Bt=0時， 此時

Vw(Xt,0,0)=max{w+βUw,-c(γm)+βUw}，

式中Uw=[QVw(Xt+1,N,L)+(1-Q)Vw(Xt+1,0,0)]。故J(Xt,0,0)=w+c(γm)，從而

w*(Xt,0,0)=-c(γm)。

(7)

再證明②。當st=(Xt,k,0)時，類似①的證明，有

w*(Xt,k,0)=-c(γm)。

(8)

最后證明③。當Tt=1時，分如下2種情況討論：

a)當Bt=0時，同①可得

w*(Xt,1,0)=-c(γm)。

(9)

b)當Bt≠0時，有J(Xt,1,Bt)=w-rp(γm)+c(γm)+p(γm)f(Bt-1)-p(γm)f(Bt),從而

w*(Xt,1,Bt)=rp(γm)-c(γm)-p(γm)f(Bt-1)+p(γm)f(Bt)。

(10)

于是Tt=1時命題得證。綜上，引理得證。

引理3若狀態(tài)st=(Xt,Tt,Bt)∈S ，Xt=γm∈Γ存在Whittle索引w*(st)，其中，Tt≥2，令

g(st)=Vw(Xt,Tt,Bt+1)-Vw(Xt,Tt,Bt),

則

(11)

證明當Bt=0時，由引理2，命題顯然成立。

當Bt≥1時，有

J(Xt,Tt,Bt)=w-rp(γm)+c(γm)+βp(γm)[g(Xt+1,Tt-1,Bt-1)]。

對J(xt,Tt,Bt)關于w求導，有

又因(Xt,Tt,Bt)存在Whittle索引，故引理得證。

下面給出本文的第1個主要結論(定理1)。

定理1基于RBP框架的P2P傳輸問題存在Whittle索引。

證明本定理即證任意給定狀態(tài)st=(Xt,Tt,Bt)∈S ，Xt=γm∈Γ，存在Whittle索引w*(st)。下面用數學歸納法證明。

由引理2知，當Tt=0，1時，命題成立。

假設Tt=k時命題成立，由引理3，有

(12)

下面證明當Tt=k+1時，w*(st)存在。

當Bt=0時，由J(Xt,k+1,0)=w+c(γm)，可得w*(Xt,k+1,0)=-c(γm)。

當Bt≥1時，J(Xt,k+1,Bt)=w-rp(γm)+c(γm)+βp(γm)[g(Xt+1,k,Bt-1)]，由式(12)，得

故當Tt=k+1時，w*(st)存在。綜上，對于任意st∈S 都存在Whittle索引。命題得證。

下面給出本文的第2個主要結論(定理2)，該結論給出各個狀態(tài)Whittle索引的封閉表達式。

定理2系統(tǒng)狀態(tài)st=(Xt,Tt,Bt)∈S 的Whittle索引可表示為

(13)

式中：

同時，對?γn∈Γ，有ρ=[p(γn)]，ζ=[c(γn)]。

證明式(13)前2式由式(7)～(10)可得，接下來只需證明式(13)中第3式，即Tt>1,Bt≠0時狀態(tài)st的Whittle索引表達式。

由引理1，當Bt=0時，有w*(Xt,Tt,1)≥w≥w*(Xt,Tt,0)=-c(γm)，

g(Xt,Tt,0)=rp(γm)-c(γm)+β(1-p(γm))[g(Xt+1,Tt-1,0)]-w。

(14)

當Bt≠0時，有w*(Xt,Tt,Bt+1)≥w≥w*(Xt,Tt,Bt)，以及

g(Xt,Tt,Bt)=rp(γm)-c(γm)+β(1-p(γm))[g(Xt+1,Tt-1,Bt)]-w。

(15)

由此可得

g(Xt,1,0)=rp(γm)-c(γm)-(1-p(γm))δ(0)-w，

(16)

g(Xt,1,Bt)=rp(γm)-c(γm)-(1-p(γm))δ(Bt)-w。

(17)

1)當Tt>1,Bt=1時

J(Xt,Tt,1)=w-rp(γm)+c(γm)+βp(γm)[g(Xt+1,Tt-1,0)]，

(18)

對?γn,γn′,…,γnTt-3∈Γ，將式(14)代入式(18)進行Tt-1次替換可得

J(Xt,Tt,1)=w-rp(γm)+c(γm)+βp(γm)[rp(γn)-c(γn)+β(1-p(γn))[rp(γn′)-c(γn′)+…+

β(1-p(γnTt-3))[g(Xt+Tt-1,1,0)]-w]…-w]-w],

代入式(16)，并取J(xt,Tt,Bt)=0即可得到定理2。

2)當Tt>1,Bt>1時

J(Xt,Tt,Bt)=w-rp(γm)+c(γm)+βp(γm)[g(Xt+1,Tt-1,Bt-1)]。

(19)

將式(15)代入式(19)進行Tt-1次替換可得

β(1-p(γnTt-3))[g(Xt+Tt-1,1,Bt-1)]-w]…-w]-w],

代入式(17)，并取J(Xt,Tt,Bt)=0即可得到定理2。命題得證。

注在P2P實時通信的MDP模型中，w=0。由定理2可計算出所有狀態(tài)所對應的Whittle索引w*(st)，并由此得到基于Whittle索引的調度算法，具體地，當w*(st)>0時，采取動作at=1；否則采取動作at=0。

4 數值模擬

4.1 數值設置

設信道狀態(tài)空間為Γ={1,2,3},分別表示差、一般、好3種情況，對應的成功傳輸概率為P=[0.45,0.7,0.85]。設信道狀態(tài)具有平穩(wěn)分布Pc=[0.2,0.5,0.3]。對任意信道狀態(tài)γm∈Γ，令數據包的發(fā)送成本函數為：c(γm)=2/γm，貼現因子β=0.85。假設傳輸任務的大小為L=5，傳輸任務的最大容忍時延N=10。成功傳輸一個數據包的收益為r=3，剩余數據包對應的懲罰函數為f(b)=b2I{b≠0}。

4.2 仿真結果及分析

表1給出3個信道狀態(tài)、不同剩余數據包個數下，剩余傳輸時間不同時對應狀態(tài)所采取的動作，其中(a,b,c)這3個分量分別對應3個信道狀態(tài)下的策略。由表1所給出的策略可以得到最大貼現總收益。圖2為基于Whittle索引實時傳輸算法和基于VI算法的最大貼現總收益的對比。通過對比可以看出，在信道狀態(tài)較差時，基于Whittle索引的最優(yōu)調度算法的最大貼現總收益與值迭代算法(VI)相比有些不足，信道狀態(tài)一般或較好的情況下與值迭代算法相等，由此可得基于Whittle索引的最優(yōu)調度算法的最大貼現總收益近似于最優(yōu)。通過仿真實驗可得，基于Whittle索引實時傳輸策略的計算成本是VI算法的0.585 8。同時，由圖2可見，通過Whittle索引得到的調度策略與最優(yōu)調度策略幾乎沒有區(qū)別。

表1 基于Whittle索引的最優(yōu)調度策略下所有系統(tǒng)狀態(tài)的動作Tab. 1 Actions of all system states under the optimal scheduling policy based on Whittle index

圖2 值迭代算法與基于Whittle索引的最優(yōu)調度算法的最大貼現總收益Fig. 2 Maximum discounted total return of value iterative algorithm and the Whittle indexbased scheduling algorithm

5 結語

本文研究在分組隨機到達、嚴格時延等約束時衰減信道下P2P的實時通信問題。引入拉格朗日數乘因子將P2P實時傳輸調度模型建模為RBP模型，證明P2P實時傳輸調度問題的可索引性，并給出基于Whittle索引的實時傳輸策略，極大減少了求解最優(yōu)策略的計算成本。在多用戶通信系統(tǒng)中，隨著用戶狀態(tài)的增多，狀態(tài)空間呈指數形式增長,因此，本文提出的傳輸模型以及處理方式，可以進一步推廣到多用戶P2P實時傳輸調度問題中，在多用戶情況下仍然有運用價值。