基于分层网络的中心化和去中心化编码缓存方案*

汪科，陈家慧，吴幼龙

(1 上海科技大学信息科学与技术学院，上海 201210；2 中国科学院上海微系统与信息技术研究所，上海 200050；3 中国科学院大学，北京 100049)(2020年2月12日收稿；2020年4月8日收修改稿)

移动智能终端的普及与5G、物联网等技术的井喷式发展，让移动网络数据的发送与接收达到了一个前所未有的数量级。仅2014年，全球的移动数据流量总量是2000年整个国际互联网数据总量的30倍[1]。缓存技术能够有效降低网络高峰期数据传输时延，一直以来都是国内外计算机、通信等信息科学领域的研究人员所关注的重要热点，传统缓存方案直接将用户所需要的部分文件存储在本地，当用户向所连接的服务器发出该文件的请求后，由服务器将未存储的另一部分发送到用户，从而满足用户需求。该方案对用户本地的存储空间要求较高，且当多个用户请求不同的文件时，服务器需进行多次发送，传输效率较低。2014年，Maddah-Ali和Niesen[2]针对服务器与多个用户无噪相连的系统模型，提出中心化的编码缓存方案。该方案将传统缓存和编码技术相结合，合理设计缓存问题中的2个阶段：Placement和Delivery，使得服务器发送的信号能同时满足多个用户的请求，从而获得传统缓存方案所不具有的多播增益，有效降低总的传输时延。

目前关于编码缓存的研究已经拓展到多个方向和应用场景。Maddah-Ali和Niesen[3]提出了支持用户数量变化和网络环境切换的去中心化缓存算法。去中心化缓存算法以牺牲少量性能为代价，具有更好的灵活性。在此基础上，国内外许多研究者也开始研究更实际更复杂的系统模型，为编码缓存方案的应用，做出了许多突破性的工作。例如，Karamchandani等[4]考虑服务器与用户之间存在中继辅助连接的多层模型。其中服务器与中继层为第1层网络，中继与所连接的用户为第2层网络。针对该模型，他们提出基于单层网络的多级编码缓存算法，并得到了最优传输时延上下界。更多的关于编码缓存的研究还包括：用户对文件的需求服从非均匀分布的编码缓存问题[5]；多个服务器向用户提供服务的编码缓存问题[6]；将编码缓存与分布式计算结合，在通信负载、节点计算量和缓存大小之间寻求一个折衷关系[7]；以PDA(placement delivery array)的特殊结构来描述编码缓存过程中的2个阶段，同时减小文件划分数量级[8]；将图论中的超图和二分图用于研究编码缓存[9-10]；保持文件完整性同时降低传输时延的编码缓存技术[11]；将编码缓存技术应用到信息安全与私人信息检索领域[12-14]等。

本文针对包含服务器、中继和用户的多层级联网络模型，提出去中心化和中心化的编码缓存方案，并从理论上推导出这2种方案的传输时延上界。该方案利用中继的缓存资源，实现了服务器与中继的并行传输，并通过合理设计Placement和Delivery阶段，使得服务器和中继能够根据自身和用户存储的文件内容，高效地选择发送时机和发送内容。通过数学推导和仿真结果表明，本文所提出的2种缓存方案均严格优于之前针对分层网络所提出的缓存方案，能够明显地降低系统的通信延迟。

1 分层网络缓存模型

图1 分层网络编码缓存模型

在Placement阶段，所有的中继和用户可以预先存储N个文件的部分内容，用以填充其本地缓存空间，这个阶段通常发生在网络流量较低的时段。

本文研究的重点和难点在于，如何在Placement阶段合理地对文件进行分块和存储，以及服务器在知道用户的所有请求之后，如何在Delivery阶段对用户需要的内容进行编码和发送，使得用户在完美解出所需要内容的同时，尽可能降低系统的传输时延。

2 中心化编码缓存方案

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

根据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类子文件可以由该用户所连接的中继编码后直接进行发送，且所有中继可以同时工作，即对于所有的用户子集S⊂[K2],|S|=t2+1以及任意j∈[K2]，中继i发送编码信息

(1)

到所连接的用户，其中⊕代表异或操作。

由于不同的中继和所连接的用户之间没有有效通信，第2类子文件由服务器编码后发送到中继，对于任意的R⊂[K1],|R|=t1+1,S⊂[K2],|S|=t2+1，服务器发送编码子文件

(2)

到所有的中继，再由中继根据自身存储文件解出所连接用户需要的部分，分别发送给对应的用户。由于中继并不需要等服务器将第2类子文件发送完毕后再发送给用户，所以发送第1类和第2类子文件的过程可以实现并行发送。

定理1考虑图1所示的分层网络，在中心化编码缓存的设定下，其传输时延上界为

(3)

下面以一个例子来说明中心化方案的Placement和Delivery阶段。

例1考虑K1=2,K2=2,N=4,M1=2,M2=2的多层网络模型。以A,B,C,D分别表示服务器中的4个文件，用户所需要的文件均不相同但可以是任意的。不失一般性，假设4个用户需要文件分别是A,B,C,D。

表1给出了2个中继连接的4个用户需求和缓存的基本情况，可以看出，用户1和用户3，用户2和用户4所缓存的内容是完全相同的，这是由于它们在不同中继上的相对位置是一样的，即不同中继所连接用户的缓存内容具有对称性。

表1 中心化方案用户文件缓存与需求

根据2类子文件发送的算法式(1)和式(2)，图2给出中心化方案的发送过程。

图2 中心化方案发送过程

3 去中心化编码缓存方案

在Placement阶段对文件进行分割及缓存时，中心化方案将文件等分成固定数目的子文件，每个中继或用户存储每个文件的比例是相同的。而去中心化方案从概率统计的角度来考虑文件分割以及存储。假设所有文件独立且满足均匀分布，中继以随机选取的方式对文件进行缓存，那么对于任意一个文件所含的任意一个比特，能够被某一中继缓存的概率是M1/N，反之，不能够被某一中继缓存的概率是1-M1/N。同理，能够被某一用户缓存的概率是M2/N，不能够被某一用户缓存的概率是1-M2/N。根据存储位置的不同，文件Wn可被分为多个子文件，表示为

(4)

与中心化方案子文件不同的是，这里表示存储中继集合的Q和表示存储用户集合的S均可以为空集∅。空集表示该部分子文件并未存储在任何一个中继或用户当中。

在Delivery阶段，对于任意一个中继i所连接的用户，所需要的子文件可以分为以下3类：

第1类 被除中继i之外的其他中继所存储的子文件，表示为

第2类 没有被任何中继存储的子文件，表示为

第3类 被中继i所存储的子文件，表示为

因此，整个Delivery阶段发送3类子文件的过程也可以分为以下3步。

第1个发送阶段主要针对第1类子文件。由于中继之间并没有任何直接或间接的通信，因此第1类子文件将由服务器直接进行编码多播发送，对于任意的j∈[K2]，服务器向所有的中继发送编码信息

(5)

考虑到并行发送的网络属性，此阶段中继i在解出需要的子文件之后，直接发送给所连接的用户，以R1表示此阶段的传输时延。

第2个发送阶段主要针对第2类子文件和部分第3类子文件。第2类子文件即上标为∅且被用户所需要的部分，由服务器编码多播发送到所有中继，遍历所有用户子集S⊆U:|S|=s,s∈[K1K2]，服务器发送

(6)

到所有中继，同时中继将接收到的子文件选择性地发送到自己所连接的用户。因为服务器发送的是针对所有用户的第2类子文件，而每个中继只需要发送其连接用户所需要的第2类子文件，所以服务器所发送第2类子文件中有一部分对于某些中继是冗余的信息，此时这些中继可以再将自身缓存的第3类文件发送给用户，即中继i发送

(7)

也就是本身存储在中继中被下面所连接的用户需要的子文件，其中

R′⊆[K1]:i∈R,

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

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

以R2表示此阶段的传输时延。

在第3个发送阶段，中继发送剩余的第3类子文件。如果第3类子文件在第2个发送阶段已全部发送给到用户，那么所有发送过程均已完成，即第3个阶段不存在。因此此阶段存在的前提是，在服务器发送到中继的第2类子文件中，中继不需要的那部分子文件大小小于第3类子文件的大小，以R3表示此阶段的传输时延。

总结来说，表2给出了去中心化方案中3类子文件的发送过程，第1类子文件由服务器和中继直接进行并行传输，传输时延即为第1类子文件的标准化大小R1；在第2个发送步骤，服务器向中继发送所有的第2类子文件，中继利用并行传输发送第2类子文件中必要的部分信息以及部分第3类子文件，总的传输时延为R2；若第3类子文件总的大小小于第2类子文件中冗余信息的大小，则整个发送过程结束，反之，则中继继续发送剩下的第3类子文件。

表2 第1、2、3类子文件的发送

定理2考虑图1所示的分层网络，在去中心化编码缓存的设定下，令

(8)

则整个过程的传输时延上界为

ROUR_d=R1+R2+R3.

其中

(9)

(10)

(11)

下面以一个例子来说明去中心化方案的Placement和Delivery阶段

例2考虑N=4,K1=K2=2,M1=M2=2的多层网络模型。以A,B,C,D表示服务器中的4个文件，用户所需要的文件均不相同但可以是任意的。不失一般性，假设4个用户需要的访问文件分别为A,B,C,D。

在Placement阶段，去中心化方案将文件A划分为多个子文件

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

在第1个发送阶段，根据第1类子文件的发送算法式(6)，服务器向中继发送第1类子文件

中继1可以将上标为2的子文件解出来，中继2也可以将上标为1的子文件解出来，然后直接发送到所连接的用户，用户可以根据存储内容进一步解出所需要的子文件，这个过程的传输时延R1=3/16。

第2个发送阶段，根据第2类子文件的发送算法式(7)，服务器向中继继续发送第2类子文件

第3个发送阶段，即服务器需要发送的内容已发送完毕，由中继将自身存储内容进行编码发送，根据第3类子文件的发送算法式(8)，中继1发送的第3类子文件为

其中：Q1⊂{1,2}并且包含元素1，此处为{1}或{1,2}。中继2发送的第3类子文件为

其中：Q2⊂{1,2}并且包含元素2，此处为{2}或{1,2}，取部分文件补上第2阶段的空缺后，这个过程的传输时延为R3=21/64。

由此，可计算出总的传输时延ROUR_d=3/4。

4 性能分析

本节将通过理论推导与仿真结果，从中心化和去中心化的角度，对本文所提出的2种方案与文献[4]的方案进行分析与比较。

在文献[4]的方案中服务器和中继连接的一层被看作第1层网络，中继和用户连接的一层被看作第2层网络。第1层网络使用单层的中心化或去中心化编码缓存算法，使得中继能够重建出所连接用户需要的文件，之后第2层网络将每个中继看作服务器，再次使用单层的编码缓存算法，通过发送编码多播子文件，满足其连接用户的文件访问请求。其中心化和去中心化方案的传输时延分别为

(12)

(13)

首先比较本文和文献[4]的中心化编码缓存方案。从式(3)和式(12)可以看出，ROUR_c加号左右两边的2项，均是在RAN_c2项的基础上乘上小于1的因子，因此ROUR_c≤RAN_c，从理论上证明本文所提出的中心化方案能够获得更低的传输延迟。在例1中，若使用文献[4]的方案，将参数带入计算可得RAN_c=3/2，而本文提出的方案ROUR_c=1/2，与代入参数后式(3)的结果相同，性能提升了3倍，效果十分显著。

比较本文和文献[4]的去中心化编码缓存方案。由于r(M2/N,K2)≤K2，且

因此

即ROUR_d=R1+R2+R3≤RAN_d，在理论上证明了本文所提出的去中心化方案仍然严格优于文献[4]的方案。在例2中，总的传输时延ROUR_d=3/4，而将参数代入式(13)，计算出文献[4]去中心化方案的传输时延为RAN_d=9/4，显然，本文所提出的方案传输时延明显降低。

图3(a)和(b)设定K1=40,K2=20,M2/N=0.2，以M1/N作为横坐标，传输时延R作为纵坐标。可以明显看出：中心化方案和去中心化方案的传输时延R均随着M1/N的增大而减小。这是当M1/N的增大时，中继缓存能力提升，因此服务器所需要发送的内容会减少，传输时延也随之降低；在中心化和去中心化的设定上，本文所提出的2种方案与文献[4]的方案相比，均体现出非常明显的性能优势，特别是在M1/N取值较小的时候；同样的参数设置，由于中心化的存储要求更严格，去中心化对文件进行分割存储的自由度更高，所以中心化方案的传输时延要略好于去中心化方案。

图3(c)和(d)设定M1/N=0.2,M2/N=0.01,K1=20，以每个中继连接的用户数量K2作为横坐标，整个系统的传输时延R作为纵坐标。可以看出：随着用户数目K2的增加，整个网络的负载增大，传输时延也增大；本文提出的中心化和去中心化方案均明显优于文献[4]的方案；在文献[4]的2种方案中，传输时延与用户数目基本都保持线性增长关系，而本文提出来的2种方案，传输时延随用户数目的增长速率相对来说较为缓慢，远远低于线性增长，意味着本文提出的方案具有更强的鲁棒性和可延展性。

图3 中心化和去中心化方案性能对比

5 总结

本文针对包含服务器、中继和用户的分层网络模型，提出了中心化和去中心化的2种编码缓存方案。2种方案充分利用中继的缓存资源，合理设计Placement和 Delivery阶段，在满足用户文件请求的同时，实现了数据的高效传输。通过理论推导和仿真验证，与文献[4]的编码缓存方案相比，本文提出的方案显著地降低系统的传输延迟，同时具有更强的鲁棒性以及可延展性。