基于分層網(wǎng)絡(luò)的中心化和去中心化編碼緩存方案*

汪科，陳家慧，吳幼龍

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

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

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

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

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

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

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

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

2 中心化編碼緩存方案

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

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

第1類(lèi)子文件存儲(chǔ)在用戶(hù)所連接的中繼中，表示為

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

第2類(lèi)子文件存儲(chǔ)在不與該用戶(hù)連接的中繼中，表示為

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

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

(1)

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

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

(2)

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

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

(3)

下面以一個(gè)例子來(lái)說(shuō)明中心化方案的Placement和Delivery階段。

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

表1給出了2個(gè)中繼連接的4個(gè)用戶(hù)需求和緩存的基本情況，可以看出，用戶(hù)1和用戶(hù)3，用戶(hù)2和用戶(hù)4所緩存的內(nèi)容是完全相同的，這是由于它們?cè)诓煌欣^上的相對(duì)位置是一樣的，即不同中繼所連接用戶(hù)的緩存內(nèi)容具有對(duì)稱(chēng)性。

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

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

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

3 去中心化編碼緩存方案

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

(4)

與中心化方案子文件不同的是，這里表示存儲(chǔ)中繼集合的Q和表示存儲(chǔ)用戶(hù)集合的S均可以為空集??？占硎驹摬糠肿游募⑽创鎯?chǔ)在任何一個(gè)中繼或用戶(hù)當(dāng)中。

在Delivery階段，對(duì)于任意一個(gè)中繼i所連接的用戶(hù)，所需要的子文件可以分為以下3類(lèi)：

第1類(lèi) 被除中繼i之外的其他中繼所存儲(chǔ)的子文件，表示為

第2類(lèi) 沒(méi)有被任何中繼存儲(chǔ)的子文件，表示為

第3類(lèi) 被中繼i所存儲(chǔ)的子文件，表示為

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

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

(5)

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

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

(6)

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

(7)

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

R′?[K1]:i∈R,

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

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

以R2表示此階段的傳輸時(shí)延。

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

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

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

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

(8)

則整個(gè)過(guò)程的傳輸時(shí)延上界為

ROUR_d=R1+R2+R3.

其中

(9)

(10)

(11)

下面以一個(gè)例子來(lái)說(shuō)明去中心化方案的Placement和Delivery階段

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

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

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

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

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

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

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

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

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

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

4 性能分析

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

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

(12)

(13)

首先比較本文和文獻(xiàn)[4]的中心化編碼緩存方案。從式(3)和式(12)可以看出，ROUR_c加號(hào)左右兩邊的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中，總的傳輸時(shí)延ROUR_d=3/4，而將參數(shù)代入式(13)，計(jì)算出文獻(xiàn)[4]去中心化方案的傳輸時(shí)延為RAN_d=9/4，顯然，本文所提出的方案?jìng)鬏敃r(shí)延明顯降低。

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

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

圖3 中心化和去中心化方案性能對(duì)比

5 總結(jié)

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