并行傳輸編碼緩存問題研究

林 霄,羅 松,劉 楠

(東南大學 移動通信國家重點實驗室,江蘇 南京 211100)

1 引 言

傳統緩存技術通過提前在本地存儲空間中緩存內容,獲得本地緩存增益。如果本地存儲空間有限,則對網絡傳輸壓力的緩解作用有限。不同于傳統緩存技術,編碼緩存技術[1]通過巧妙創造多播機會,使得服務器的一次廣播傳輸能夠同時滿足多個用戶的不同需求,從而得到了全局緩存增益。以文獻[1]為基礎,文獻[2-8]從多個角度對編碼緩存問題模型進行變形,繼續研究編碼緩存相關問題。除了服務器通過共享鏈路向多個用戶發送信息的形式,用戶之間也可以發送信息,當編碼緩存技術應用在D2D(Device-to-Device)網絡,可以在沒有服務器的情況下,得到幾乎與服務器多播編碼緩存方案相同的增益。許多研究針對D2D網絡中的編碼緩存問題進行了研究[9-18]。

考慮到用戶之間可以互發信息的同時,服務器也能夠向所有用戶發送信息的實際應用場景,有研究提出了并行傳輸的編碼緩存問題模型,并提出一種并行傳輸的緩存與交付方案,得到了用戶協作增益和服務器編碼多播增益,并證明了該方案傳輸速率的可達上界與下界之間存在常數間隔。然而,在實際場景中,更為常見的情況是接入網絡的用戶設備多種多樣,用戶中可能同時存在手機、電腦、服務器等。由于物理條件的限制,它們各自的存儲空間大小也各不相同。同時在實際應用中,信道傳輸能力不同的情況也更為普遍。因此,目前對于并行傳輸編碼緩存問題的研究具有一定的局限性。針對以上問題,有必要開展在更符合實際應用場景的信道傳輸能力不同的場景下,基于服務器與用戶都能夠發送信息的情況,對并行傳輸編碼緩存問題展開研究。

2 并行傳輸編碼緩存問題模型

考慮一個服務器,通過一個無差錯廣播信道連接K個用戶,每個用戶都具有存儲空間。服務器端存儲N個文件,W1,…,WN,每個文件具有F個比特。用戶k的緩存空間大小表示為MkF,k∈[K]。文中考慮所有用戶的緩存空間大小相同的情況,即M1=M2=…=MK,統一用M表示,M∈[0,N]。

整個網絡由服務器和用戶構成,如圖1所示。合作網絡的特征總結如下:① 用戶端可以同時接收來自服務器和其他某個用戶的信息,這是因為兩個傳輸過程發生在不同頻帶,互不影響;② 如果在某一時刻,某個用戶正在發送信息,那么與此同時,他將無法收到來自其他用戶的信息。

圖1 并行傳輸編碼緩存問題模型

連接服務器和K個用戶的廣播信道的信道容量由Cs表示,描述了該信道的最大傳輸能力。同時,用戶之間也具有互相發送信息的能力,用戶之間通信的信道容量由Cu表示,描述了當用戶輪流向其他用戶發送信息時的傳輸能力。Cs和Cu的單位均為比特每秒。當網絡中出現通信任務,需要關注的指標為完成交付任務的傳輸延時,單位為秒。

2.1 函數定義

整個通信過程描述如下:在出現文件請求任務之前,每個用戶都可以接觸到服務器端的所有文件,并用這些文件來填充自己的緩存空間。用戶k,k∈[K]通過緩存函數φk,將W1,…,WN映射到大小為Mk的緩存空間中,緩存內容為Zk,即

Zk=φk(W1,…,WN) ,

(1)

共有K個緩存函數:

(2)

當每個用戶k都存在一個文件請求,即Wdk,所有用戶的請求都會同步到服務器和各個用戶。當服務器和所有用戶都得知文件請求向量d后,會進行文件編碼。首先,服務器根據其擁有的N個文件,編碼得到待傳輸的信息:

Xs=fd(W1,…,WN) ,

(3)

其中,編碼函數為

(4)

每個用戶會基于其預先緩存的內容Zk進行編碼:

Yk=gk,d(Zk) ,

(5)

編碼函數gk,d為

(6)

其中,Rs表示由服務器傳輸的數據量,也稱為服務器的傳輸速率;Ruk表示用戶k傳輸的數據量,即用戶k的傳輸速率,單位均為比特。

傳輸階段結束之后,用戶k分別收到來自服務器和其他用戶的信息,并根據所收到的信息,得到所請求的文件:

(7)

Y1,…,Yk-1,Yk+1,…,YK表示用戶k收到的來自其他用戶的信息,解碼函數為

(8)

定義差錯概率為

(9)

2.2 性能指標

服務器的傳輸和用戶之間的傳輸可以同時進行,因此定義傳輸延時T:

T=max(Ts,Tu) 。

(10)

最優的傳輸延時T*定義為

(11)

3 主要結論

(12)

4 可行方案

4.1 實現方案

(1) 第1階段:預緩存

(13)

(2) 第2階段:分配

(14)

對于此時再次劃分后得到的更小的子文件,用上標l∈[L1+L2]來描述:

(15)

(3) 第3階段:交付

對于用戶k,k∈[K]的請求dk,用戶仍需從外界獲得的子文件為

(16)

其中,由服務器負責傳輸的子文件為

(17)

由用戶負責的子文件為

(18)

(19)

接下來,考慮由服務器進行的傳輸。這一部分的實現使用了與文獻[1]相同的傳輸策略,服務器傳輸

(20)

因此,得到由服務器傳輸得到的傳輸延時為

(21)

整個通信網絡的傳輸延時為T=max{Ts,Tu},由式(14)、式(19)及式(21)可以發現Ts=Tu,此時的傳輸延時T為

(22)

與定理1中所描述的可達上界TC一致。

4.2 性能對比

文獻[1]介紹了由服務器進行傳輸的中心化預存儲編碼緩存方案,文獻[11]介紹了D2D網絡中的編碼緩存交付方案。圖2對比了當Cs=1,Cu=5時,這兩種實現方案與文中方案中用戶緩存M與傳輸延時T之間的關系。可以看出,文中所提出的編碼緩存方案相比于文獻[1]和[11],傳輸延時減少。由于此時D2D網絡信道的傳輸能力強于服務器廣播信道,因此與文獻[1]中可達交付方案相比,文獻[11]中的可達交付方案具有明顯的性能提升,但文中所提出的交付方案依然可以實現比以上兩種已知交付方案更短的傳輸時長,尤其在用戶緩存空間較小的情況下。

圖2 當K=20,N=20,Cs=1,Cu=5時,不同實現方案的性能對比

圖3將文中所提方案與文獻[18]中的緩存交付方案進行對比。對比了當文件數N,用戶數K一定時,使用這兩種方案進行并行傳輸編碼緩存,最終傳輸時長與用戶緩存空間大小M之間的權衡。可以看出,當服務器廣播信道和D2D網絡信道的傳輸能力不同時,與使用了文獻[18]中方案相比,文中提出的緩存交付方案存在明顯性能提升,尤其在用戶緩存空間較小時,性能改進效果明顯。同時兩種信道的傳輸能力差距越大,文中案對性能的提升就越佳,筆者所提緩存交付方案優勢更大。

圖3 當K=N=10時,不同實現方案的性能對比

5 最優性分析

5.1 準備工作

本節對最優性證明過程中需要用到的相關引理進行闡述。

引理1在具有一個中央服務器和K個用戶的并行傳輸編碼緩存網絡中,Xs為服務器多播的信息,Rs表示服務器傳輸信息量大小,Yi表示用戶i發送給其他用戶的信息,i∈[K],Ru為所有用戶組成的合作網絡中所傳輸的總信息量,則有

(23)

其中,[K]/{i}表示K個用戶中除去用戶i以后的用戶集合。引理1描述了為令所有用戶都可以恢復出其所請求文件,服務器多播速率Rs和D2D網絡內部傳輸速率Ru需要滿足的下界條件。

接下來,與文獻[19]類似,定義aj,{1,…,K}表示一個包含了F個比特的文件在用戶集合{1,…,K}中的j個用戶中緩存的比特數量,即

(24)

其中,F為一個文件的大小,單位為比特;Bn表示文件的第n個比特;Kn表示緩存了Bn的用戶集合。

根據aj,{1,…,K}的定義,有以下結論。

引理2考慮N個大小為F比特的文件,將其緩存到K個用戶的緩存空間中,aj,{1,…,K}定義見式(24)。那么有

(25)

(26)

引理3在具有一個中央服務器和K個用戶的并行傳輸編碼緩存系統中,Xs表示由服務器廣播的信息,Yi表示用戶i發送的信息,i∈[K]。aj,{1,…,K}根據式(24)定義,那么有

(27)

引理3描述了除了用戶所請求的Wdi和用戶已緩存內容Zi以外,其收到的來自服務器與其他用戶的信息量的下界。此下界以比特數量aj,[K]的形式表示。

5.2 K=N=3時的最優性分析

為便于理解最優性分析思路,以K=N=3的情況為例,說明最優性的證明過程。文中提出的非編碼預存儲并行傳輸的編碼緩存方案中,服務器會向所有用戶發送信息,信息量以Rs表示,同時用戶之間可以相互發送信息,合作用戶網絡中發送的總信息量為Ru。由于考慮的是兩種信道傳輸能力相同,且Cs=Cu=1的情況,因而此時傳輸時長Ts=Rs/Cs=Rs,Tu=Ru/Cu=Ru。將二者中的最大值作為整個編碼緩存模型的傳輸時長,即T=max{Ts,Tu}。后文將統一使用R、Rs和Ru進行證明。

當考慮M、Rs和Ru三者之間的關系,以點(M,Rs,Ru)表示。定義Conv(ct),t∈{1,…,K}為所有可行解組成的包絡。接下來,如果能夠證明:Conv(ct),t∈{1,…,K}中,存在恰好也是傳輸信息量R的下界的部分,即當給定K和N,存在這樣的用戶緩存空間大小M,使得此時的并行傳輸編碼緩存方案的實現速率滿足:

R≥Conv(ct) ,

(28)

那么就意味著當用戶緩存空間大小M屬于這部分時,所提非編碼預存儲并行傳輸編碼緩存方案的可達速率與速率下界匹配。當用戶緩存空間大小M滿足以上條件時,所提實現方案是最優的。

圖4 K=N=3時,可行解組成的上界包絡Conv(ct)

3Rs+2Ru+M=3 ,

(29)

3Rs+2Ru+2M=5 。

(30)

接下來,證明

3Rs+2Ru+M≥3 ,

(31)

3Rs+2Ru+2M≥5 ,

(32)

就能夠說明在這兩個平面所對應的用戶緩存空間范圍中,定理1對應的非編碼預存儲的并行傳輸方案的最優性。接下來,將針對式(31)和式(32)分別證明。

5.2.1 式(31)的證明

當K=3時,利用引理1得到

(33)

接著,將式(33)中的下界繼續縮小:

(34)

(35)

其中,Wdi表示用戶i的請求,Zi表示用戶i緩存的內容,i∈[K]。

注記1:(a)是由于H(Xs,Y{1,2,3}/{i}|Wdi,Zi)≥0,但此時的下界并不一定總是緊的。已知t代表了每個子文件在用戶緩存空間中重復緩存的次數,當每個子文件都在K或(K-1)個用戶中預緩存,在本例中,即2≤t≤3時,總會存在一個實現方案使H(Xs,Y{1,2,3}/{i}|Wdi,Zi)=0成立。此時,式(35)得到的下界是緊的。

(36)

其中,(b)基于aj,{1,…,K}的定義,(c)是由于

(d)由引理2可以得到。

由式(33),式(35)和式(36),有3Rs+2Ru+M≥3,則式(31)證明完畢。

5.2.2 式(32)的證明

在關于式(31)的證明中,式(33)不等號右側的下界縮小為式(34)后,由于H(Xs,Y{1,2,3}/{i}|Wdi,Zi)≥0且在2≤t≤3時有H(Xs,Y{1,2,3}/{i}|Wdi,Zi)=0,因此式(35)得到的下界是緊的。

(37)

發現

3a0,[K]+a1,[K]=(3a0,[K]+2a1,[K]+a2,[K])-(a1,[K]+a2,[K])=

(38)

由式(34)、式(36)～(38)可以得到

3R1+2R2(3-M)+(2-M)=5-2M,

(39)

式(32)證明完畢。

圖5 K=N=3時最優的上界包絡Conv(ct)

5.3 任意用戶數K和文件數N時的最優性分析

在這一部分,將說明任意用戶數K和文件數N情況下,如何應用節4.2所述證明方法來證明所提非編碼預存儲并行傳輸編碼緩存方案的最優性。

在節4.2K=N=3的情況下,證明了Conv(ct)中,M取值最大的兩個平面的最優性。當任意K、N時,t∈{1,…,K},Conv(ct)由t+1個平面組成。所有可行解組成的包絡Conv(ct)的多個連續平面中,M取值最大的兩個平面表示為

(40)

(41)

同時,在節4.2證明過程中用到的引理1、引理2和引理3都是在任意K、N的條件下成立的,因此在任意K、N的條件下,依然可以利用引理1、引理2和引理3進行證明。

下面將說明任意K、N時,如何證明以上兩個平面所代表的非編碼預存儲并行傳輸方案的可行解的最優性。

5.3.1 式(40)的證明

當M=N時,此時用戶可以在各自緩存空間中緩存完整的數據庫內容,無需進行信息傳遞,R=Rs=Ru=0,即點(N,0,0)是非編碼預存儲并行傳輸方案的可行解。當M=(K-1)N/K時,此時t=K-1,同樣先考慮兩種極端情況:Rs=0與Ru=0,此時點((K-1)N/K,1/K,0)和((K-1)N/K,0,1/(K-1))同樣為非編碼預存儲并行傳輸方案的可行解。以上3點構成了Conv(ct),t∈{1,…,K}包絡中的第一個由可實現點組成的面:

(42)

根據引理1,得

(43)

將式(43)中的下界繼續縮小,得到

(44)

(45)

其中,Wdi表示用戶i的請求,Zi表示用戶i緩存空間中緩存的內容,i∈[K]。

(46)

其中,(a)是由于

(b)根據引理2得到。

根據式(43)、式(45)和式(46),有

(47)

即證明了Conv(ct),t∈{1,…,K}包絡中的第1個由所提方案的可行解組成的式(40)在非編碼預存儲的前提下是最優的。

5.3.2 式(41)的證明

任意K、N時,點((K-1)N/K,1/K,0)、((K-1)N/K,0,1/K-1)、((K-2)N/K,2/(K-1),0)構成了Conv(ct),t∈{1,…,K}包絡中的第2個由所提方案可行解組成的面:

(48)

式(48)還可以寫為

(49)

(50)

因此,如果可以證明式(44)不等式右端第1項:

(51)

那么根據式(44)和式(51)就能夠得到

(52)

也就證明了式(41)所代表的由可行解組成的面的最優性。

接下來將證明式(51)成立。根據引理3,得

(53)

如果能夠證明

(54)

則根據式(53)和式(54),式(51)可證。

下面將證明式(54)成立。式(54)的不等式兩端同時乘以F(K-1),根據引理2,證明式(54)等價于

(55)

(56)

即等價于式(56)左端每一項am,[K]的系數Dm≥0。又因為

(57)

當m≤K-2時,Dm≥0。

因此,證明了式(55)成立,也就證明了式(54)成立,則式(51)證明完畢。

那么根據式(44)和(51),有

成立。因此,式(41)所代表的由所提非編碼預存儲并行傳輸方案的可行解組成的面的最優性證明完畢。

6 結 論