汪科，陳家慧，吳幼龍

(1 上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201210；2 中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；3 中國科學(xué)院大學(xué)，北京 100049)(2020年2月12日收稿；2020年4月8日收修改稿)

移動智能終端的普及與5G、物聯(lián)網(wǎng)等技術(shù)的井噴式發(fā)展，讓移動網(wǎng)絡(luò)數(shù)據(jù)的發(fā)送與接收達(dá)到了一個前所未有的數(shù)量級。僅2014年，全球的移動數(shù)據(jù)流量總量是2000年整個國際互聯(lián)網(wǎng)數(shù)據(jù)總量的30倍[1]。緩存技術(shù)能夠有效降低網(wǎng)絡(luò)高峰期數(shù)據(jù)傳輸時延，一直以來都是國內(nèi)外計(jì)算機(jī)、通信等信息科學(xué)領(lǐng)域的研究人員所關(guān)注的重要熱點(diǎn)，傳統(tǒng)緩存方案直接將用戶所需要的部分文件存儲在本地，當(dāng)用戶向所連接的服務(wù)器發(fā)出該文件的請求后，由服務(wù)器將未存儲的另一部分發(fā)送到用戶，從而滿足用戶需求。該方案對用戶本地的存儲空間要求較高，且當(dāng)多個用戶請求不同的文件時，服務(wù)器需進(jìn)行多次發(fā)送，傳輸效率較低。2014年，Maddah-Ali和Niesen[2]針對服務(wù)器與多個用戶無噪相連的系統(tǒng)模型，提出中心化的編碼緩存方案。該方案將傳統(tǒng)緩存和編碼技術(shù)相結(jié)合，合理設(shè)計(jì)緩存問題中的2個階段：Placement和Delivery，使得服務(wù)器發(fā)送的信號能同時滿足多個用戶的請求，從而獲得傳統(tǒng)緩存方案所不具有的多播增益，有效降低總的傳輸時延。

目前關(guān)于編碼緩存的研究已經(jīng)拓展到多個方向和應(yīng)用場景。Maddah-Ali和Niesen[3]提出了支持用戶數(shù)量變化和網(wǎng)絡(luò)環(huán)境切換的去中心化緩存算法。去中心化緩存算法以犧牲少量性能為代價，具有更好的靈活性。在此基礎(chǔ)上，國內(nèi)外許多研究者也開始研究更實(shí)際更復(fù)雜的系統(tǒng)模型，為編碼緩存方案的應(yīng)用，做出了許多突破性的工作。例如，Karamchandani等[4]考慮服務(wù)器與用戶之間存在中繼輔助連接的多層模型。其中服務(wù)器與中繼層為第1層網(wǎng)絡(luò)，中繼與所連接的用戶為第2層網(wǎng)絡(luò)。針對該模型，他們提出基于單層網(wǎng)絡(luò)的多級編碼緩存算法，并得到了最優(yōu)傳輸時延上下界。更多的關(guān)于編碼緩存的研究還包括：用戶對文件的需求服從非均勻分布的編碼緩存問題[5]；多個服務(wù)器向用戶提供服務(wù)的編碼緩存問題[6]；將編碼緩存與分布式計(jì)算結(jié)合，在通信負(fù)載、節(jié)點(diǎn)計(jì)算量和緩存大小之間尋求一個折衷關(guān)系[7]；以PDA(placement delivery array)的特殊結(jié)構(gòu)來描述編碼緩存過程中的2個階段，同時減小文件劃分?jǐn)?shù)量級[8]；將圖論中的超圖和二分圖用于研究編碼緩存[9-10]；保持文件完整性同時降低傳輸時延的編碼緩存技術(shù)[11]；將編碼緩存技術(shù)應(yīng)用到信息安全與私人信息檢索領(lǐng)域[12-14]等。

本文針對包含服務(wù)器、中繼和用戶的多層級聯(lián)網(wǎng)絡(luò)模型，提出去中心化和中心化的編碼緩存方案，并從理論上推導(dǎo)出這2種方案的傳輸時延上界。該方案利用中繼的緩存資源，實(shí)現(xiàn)了服務(wù)器與中繼的并行傳輸，并通過合理設(shè)計(jì)Placement和Delivery階段，使得服務(wù)器和中繼能夠根據(jù)自身和用戶存儲的文件內(nèi)容，高效地選擇發(fā)送時機(jī)和發(fā)送內(nèi)容。通過數(shù)學(xué)推導(dǎo)和仿真結(jié)果表明，本文所提出的2種緩存方案均嚴(yán)格優(yōu)于之前針對分層網(wǎng)絡(luò)所提出的緩存方案，能夠明顯地降低系統(tǒng)的通信延遲。

1 分層網(wǎng)絡(luò)緩存模型

圖1 分層網(wǎng)絡(luò)編碼緩存模型

在Placement階段，所有的中繼和用戶可以預(yù)先存儲N個文件的部分內(nèi)容，用以填充其本地緩存空間，這個階段通常發(fā)生在網(wǎng)絡(luò)流量較低的時段。

本文研究的重點(diǎn)和難點(diǎn)在于，如何在Placement階段合理地對文件進(jìn)行分塊和存儲，以及服務(wù)器在知道用戶的所有請求之后，如何在Delivery階段對用戶需要的內(nèi)容進(jìn)行編碼和發(fā)送，使得用戶在完美解出所需要內(nèi)容的同時，盡可能降低系統(tǒng)的傳輸時延。

2 中心化編碼緩存方案

|Q|=t1,|T|=t2).

根據(jù)Placement階段的緩存情況，每個用戶需要的子文件可以分為2類：

第1類子文件存儲在用戶所連接的中繼中，表示為

需滿足條件Q?[K1],|Q|=t1,S?[K2],|S|=t2,i?Q。

第2類子文件存儲在不與該用戶連接的中繼中，表示為

需滿足條件Q?[K1],|Q|=t1,S?[K2],|S|=t2,i∈Q。

第1類子文件可以由該用戶所連接的中繼編碼后直接進(jìn)行發(fā)送，且所有中繼可以同時工作，即對于所有的用戶子集S?[K2],|S|=t2+1以及任意j∈[K2]，中繼i發(fā)送編碼信息

(1)

到所連接的用戶，其中⊕代表異或操作。

由于不同的中繼和所連接的用戶之間沒有有效通信，第2類子文件由服務(wù)器編碼后發(fā)送到中繼，對于任意的R?[K1],|R|=t1+1,S?[K2],|S|=t2+1，服務(wù)器發(fā)送編碼子文件

(2)

到所有的中繼，再由中繼根據(jù)自身存儲文件解出所連接用戶需要的部分，分別發(fā)送給對應(yīng)的用戶。由于中繼并不需要等服務(wù)器將第2類子文件發(fā)送完畢后再發(fā)送給用戶，所以發(fā)送第1類和第2類子文件的過程可以實(shí)現(xiàn)并行發(fā)送。

定理1考慮圖1所示的分層網(wǎng)絡(luò)，在中心化編碼緩存的設(shè)定下，其傳輸時延上界為

(3)

下面以一個例子來說明中心化方案的Placement和Delivery階段。

例1考慮K1=2,K2=2,N=4,M1=2,M2=2的多層網(wǎng)絡(luò)模型。以A,B,C,D分別表示服務(wù)器中的4個文件，用戶所需要的文件均不相同但可以是任意的。不失一般性，假設(shè)4個用戶需要文件分別是A,B,C,D。

表1給出了2個中繼連接的4個用戶需求和緩存的基本情況，可以看出，用戶1和用戶3，用戶2和用戶4所緩存的內(nèi)容是完全相同的，這是由于它們在不同中繼上的相對位置是一樣的，即不同中繼所連接用戶的緩存內(nèi)容具有對稱性。

表1 中心化方案用戶文件緩存與需求

根據(jù)2類子文件發(fā)送的算法式(1)和式(2)，圖2給出中心化方案的發(fā)送過程。

圖2 中心化方案發(fā)送過程

3 去中心化編碼緩存方案

在Placement階段對文件進(jìn)行分割及緩存時，中心化方案將文件等分成固定數(shù)目的子文件，每個中繼或用戶存儲每個文件的比例是相同的。而去中心化方案從概率統(tǒng)計(jì)的角度來考慮文件分割以及存儲。假設(shè)所有文件獨(dú)立且滿足均勻分布，中繼以隨機(jī)選取的方式對文件進(jìn)行緩存，那么對于任意一個文件所含的任意一個比特，能夠被某一中繼緩存的概率是M1/N，反之，不能夠被某一中繼緩存的概率是1-M1/N。同理，能夠被某一用戶緩存的概率是M2/N，不能夠被某一用戶緩存的概率是1-M2/N。根據(jù)存儲位置的不同，文件Wn可被分為多個子文件，表示為

(4)

與中心化方案子文件不同的是，這里表示存儲中繼集合的Q和表示存儲用戶集合的S均可以為空集??？占硎驹摬糠肿游募⑽创鎯υ谌魏我粋€中繼或用戶當(dāng)中。

在Delivery階段，對于任意一個中繼i所連接的用戶，所需要的子文件可以分為以下3類：

第1類 被除中繼i之外的其他中繼所存儲的子文件，表示為

第2類 沒有被任何中繼存儲的子文件，表示為

第3類 被中繼i所存儲的子文件，表示為

因此，整個Delivery階段發(fā)送3類子文件的過程也可以分為以下3步。

第1個發(fā)送階段主要針對第1類子文件。由于中繼之間并沒有任何直接或間接的通信，因此第1類子文件將由服務(wù)器直接進(jìn)行編碼多播發(fā)送，對于任意的j∈[K2]，服務(wù)器向所有的中繼發(fā)送編碼信息

(5)

考慮到并行發(fā)送的網(wǎng)絡(luò)屬性，此階段中繼i在解出需要的子文件之后，直接發(fā)送給所連接的用戶，以R1表示此階段的傳輸時延。

第2個發(fā)送階段主要針對第2類子文件和部分第3類子文件。第2類子文件即上標(biāo)為?且被用戶所需要的部分，由服務(wù)器編碼多播發(fā)送到所有中繼，遍歷所有用戶子集S?U:|S|=s,s∈[K1K2]，服務(wù)器發(fā)送

(6)

到所有中繼，同時中繼將接收到的子文件選擇性地發(fā)送到自己所連接的用戶。因?yàn)榉?wù)器發(fā)送的是針對所有用戶的第2類子文件，而每個中繼只需要發(fā)送其連接用戶所需要的第2類子文件，所以服務(wù)器所發(fā)送第2類子文件中有一部分對于某些中繼是冗余的信息，此時這些中繼可以再將自身緩存的第3類文件發(fā)送給用戶，即中繼i發(fā)送

(7)

也就是本身存儲在中繼中被下面所連接的用戶需要的子文件，其中

R′?[K1]:i∈R,

S′i?Ui:|Si|=s,s∈[K2],

T′?UUi:|T′|=t,t=K1K2-K2,…,0.

以R2表示此階段的傳輸時延。

在第3個發(fā)送階段，中繼發(fā)送剩余的第3類子文件。如果第3類子文件在第2個發(fā)送階段已全部發(fā)送給到用戶，那么所有發(fā)送過程均已完成，即第3個階段不存在。因此此階段存在的前提是，在服務(wù)器發(fā)送到中繼的第2類子文件中，中繼不需要的那部分子文件大小小于第3類子文件的大小，以R3表示此階段的傳輸時延。

總結(jié)來說，表2給出了去中心化方案中3類子文件的發(fā)送過程，第1類子文件由服務(wù)器和中繼直接進(jìn)行并行傳輸，傳輸時延即為第1類子文件的標(biāo)準(zhǔn)化大小R1；在第2個發(fā)送步驟，服務(wù)器向中繼發(fā)送所有的第2類子文件，中繼利用并行傳輸發(fā)送第2類子文件中必要的部分信息以及部分第3類子文件，總的傳輸時延為R2；若第3類子文件總的大小小于第2類子文件中冗余信息的大小，則整個發(fā)送過程結(jié)束，反之，則中繼繼續(xù)發(fā)送剩下的第3類子文件。

表2 第1、2、3類子文件的發(fā)送

定理2考慮圖1所示的分層網(wǎng)絡(luò)，在去中心化編碼緩存的設(shè)定下，令

(8)

則整個過程的傳輸時延上界為

ROUR_d=R1+R2+R3.

其中

(9)

(10)

(11)

下面以一個例子來說明去中心化方案的Placement和Delivery階段

例2考慮N=4,K1=K2=2,M1=M2=2的多層網(wǎng)絡(luò)模型。以A,B,C,D表示服務(wù)器中的4個文件，用戶所需要的文件均不相同但可以是任意的。不失一般性，假設(shè)4個用戶需要的訪問文件分別為A,B,C,D。

在Placement階段，去中心化方案將文件A劃分為多個子文件

其中：S?{1,2,3,4}，所以A被分成了2K1·2K1K2=64個子文件。其余文件B,C,D類似。由式(4)可得，分割之后的子文件大小為

在第1個發(fā)送階段，根據(jù)第1類子文件的發(fā)送算法式(6)，服務(wù)器向中繼發(fā)送第1類子文件

中繼1可以將上標(biāo)為2的子文件解出來，中繼2也可以將上標(biāo)為1的子文件解出來，然后直接發(fā)送到所連接的用戶，用戶可以根據(jù)存儲內(nèi)容進(jìn)一步解出所需要的子文件，這個過程的傳輸時延R1=3/16。

第2個發(fā)送階段，根據(jù)第2類子文件的發(fā)送算法式(7)，服務(wù)器向中繼繼續(xù)發(fā)送第2類子文件

第3個發(fā)送階段，即服務(wù)器需要發(fā)送的內(nèi)容已發(fā)送完畢，由中繼將自身存儲內(nèi)容進(jìn)行編碼發(fā)送，根據(jù)第3類子文件的發(fā)送算法式(8)，中繼1發(fā)送的第3類子文件為

其中：Q1?{1,2}并且包含元素1，此處為{1}或{1,2}。中繼2發(fā)送的第3類子文件為

其中：Q2?{1,2}并且包含元素2，此處為{2}或{1,2}，取部分文件補(bǔ)上第2階段的空缺后，這個過程的傳輸時延為R3=21/64。

由此，可計(jì)算出總的傳輸時延ROUR_d=3/4。

4 性能分析

本節(jié)將通過理論推導(dǎo)與仿真結(jié)果，從中心化和去中心化的角度，對本文所提出的2種方案與文獻(xiàn)[4]的方案進(jìn)行分析與比較。

在文獻(xiàn)[4]的方案中服務(wù)器和中繼連接的一層被看作第1層網(wǎng)絡(luò)，中繼和用戶連接的一層被看作第2層網(wǎng)絡(luò)。第1層網(wǎng)絡(luò)使用單層的中心化或去中心化編碼緩存算法，使得中繼能夠重建出所連接用戶需要的文件，之后第2層網(wǎng)絡(luò)將每個中繼看作服務(wù)器，再次使用單層的編碼緩存算法，通過發(fā)送編碼多播子文件，滿足其連接用戶的文件訪問請求。其中心化和去中心化方案的傳輸時延分別為

(12)

(13)

首先比較本文和文獻(xiàn)[4]的中心化編碼緩存方案。從式(3)和式(12)可以看出，ROUR_c加號左右兩邊的2項(xiàng)，均是在RAN_c2項(xiàng)的基礎(chǔ)上乘上小于1的因子，因此ROUR_c≤RAN_c，從理論上證明本文所提出的中心化方案能夠獲得更低的傳輸延遲。在例1中，若使用文獻(xiàn)[4]的方案，將參數(shù)帶入計(jì)算可得RAN_c=3/2，而本文提出的方案ROUR_c=1/2，與代入?yún)?shù)后式(3)的結(jié)果相同，性能提升了3倍，效果十分顯著。

比較本文和文獻(xiàn)[4]的去中心化編碼緩存方案。由于r(M2/N,K2)≤K2，且

因此

即ROUR_d=R1+R2+R3≤RAN_d，在理論上證明了本文所提出的去中心化方案仍然嚴(yán)格優(yōu)于文獻(xiàn)[4]的方案。在例2中，總的傳輸時延ROUR_d=3/4，而將參數(shù)代入式(13)，計(jì)算出文獻(xiàn)[4]去中心化方案的傳輸時延為RAN_d=9/4，顯然，本文所提出的方案傳輸時延明顯降低。

圖3(a)和(b)設(shè)定K1=40,K2=20,M2/N=0.2，以M1/N作為橫坐標(biāo)，傳輸時延R作為縱坐標(biāo)。可以明顯看出：中心化方案和去中心化方案的傳輸時延R均隨著M1/N的增大而減小。這是當(dāng)M1/N的增大時，中繼緩存能力提升，因此服務(wù)器所需要發(fā)送的內(nèi)容會減少，傳輸時延也隨之降低；在中心化和去中心化的設(shè)定上，本文所提出的2種方案與文獻(xiàn)[4]的方案相比，均體現(xiàn)出非常明顯的性能優(yōu)勢，特別是在M1/N取值較小的時候；同樣的參數(shù)設(shè)置，由于中心化的存儲要求更嚴(yán)格，去中心化對文件進(jìn)行分割存儲的自由度更高，所以中心化方案的傳輸時延要略好于去中心化方案。

圖3(c)和(d)設(shè)定M1/N=0.2,M2/N=0.01,K1=20，以每個中繼連接的用戶數(shù)量K2作為橫坐標(biāo)，整個系統(tǒng)的傳輸時延R作為縱坐標(biāo)。可以看出：隨著用戶數(shù)目K2的增加，整個網(wǎng)絡(luò)的負(fù)載增大，傳輸時延也增大；本文提出的中心化和去中心化方案均明顯優(yōu)于文獻(xiàn)[4]的方案；在文獻(xiàn)[4]的2種方案中，傳輸時延與用戶數(shù)目基本都保持線性增長關(guān)系，而本文提出來的2種方案，傳輸時延隨用戶數(shù)目的增長速率相對來說較為緩慢，遠(yuǎn)遠(yuǎn)低于線性增長，意味著本文提出的方案具有更強(qiáng)的魯棒性和可延展性。

圖3 中心化和去中心化方案性能對比

5 總結(jié)

本文針對包含服務(wù)器、中繼和用戶的分層網(wǎng)絡(luò)模型，提出了中心化和去中心化的2種編碼緩存方案。2種方案充分利用中繼的緩存資源，合理設(shè)計(jì)Placement和 Delivery階段，在滿足用戶文件請求的同時，實(shí)現(xiàn)了數(shù)據(jù)的高效傳輸。通過理論推導(dǎo)和仿真驗(yàn)證，與文獻(xiàn)[4]的編碼緩存方案相比，本文提出的方案顯著地降低系統(tǒng)的傳輸延遲，同時具有更強(qiáng)的魯棒性以及可延展性。