源于分布式网络的离散模型与组合学方法_韩雪姣.pdf

中国科学:数学2023年第53卷第2期:151186SCIENTIA SINICA Mathematica综述英文引用格式:Han X J,Zhang Y W,Yin J X,et al.Discrete configurations and combinatorial methods originated fromdistributed network(in Chinese).Sci Sin Math,2023,53:151186,doi:10.1360/SSM-2022-0074c 2022中国科学 杂志社源于分布式网络的离散模型与组合学方法献给朱烈教授80华诞韩雪姣1,张一炜2,3,殷剑兴4,吴佃华51.首都师范大学数学科学学院,北京 100048;2.山东大学教育部密码技术与信息安全重点实验室,青岛 266237;3.山东大学网络空间安全学院,青岛 266237;4.苏州大学数学科学学院,苏州 215006;5.广西师范大学数学与统计学院,桂林 541006E-mail:,收稿日期:2022-04-28;接受日期:2022-06-21;网络出版日期:2022-09-28;*通信作者国家重点研发计划(批准号:2021YFA1001000)、国家自然科学基金(批准号:12001323 和 12161010)和山东省自然科学基金(批准号:ZR2021YQ46)资助项目摘要近年来,分布式网络环境架构下的诸多新型信息科学问题为经典信息论和编码理论带来了新的挑战.这些问题的研究涉及多种离散模型,组合设计、图论、组合编码和极值组合学等组合学方法在其中发挥了至关重要的作用.本文选取网络编码、索引编码、编码缓存、分布式计算和隐私保护信息检索这5个源于分布式网络环境的信息科学前沿热点问题,简要介绍各问题研究进展,并着重介绍其中涉及的离散模型与组合学思想方法.同时,本文针对上述多个专题分别给出一些新结果.关键词分布式网络网络编码索引编码编码缓存分布式计算隐私保护信息检索MSC(2020)主题分类05B99,68P30,68R051背景简介数字化、网络化和智能化是新一轮科技革命的突出特征,也是新一代信息技术的聚焦点,产业升级换代为这些特征赋予新的内涵.数字化从计算机化向数据化发展,后者的核心是对信息技术革命与经济社会活动交融生成的大数据的深刻认识与深层利用.网络化已从互联网延拓到以工业互联网、车联网、智能家居为代表的物联网,实现人、物、服务之间交叉互联.智能化是信息技术发展的永恒追求,引领人工智能技术一代代发展.新一代信息技术的发展,必然会产生诸多新型信息科学问题,为经典信息论和编码理论带来新挑战.特别地,在当前大数据时代背景下,分布式网络环境架构引领了近20年来的信息科学多个前沿热点方向.本文围绕分布式网络环境架构下的下述5个信息问题展开讨论.韩雪姣等:源于分布式网络的离散模型与组合学方法网络编码:网络通信最基本的目的是将信息从信源节点无差错地传输至信宿节点.在传统路由网络中,中间节点只有接力传输的作用.网络编码通过赋予网络节点一定的计算能力,有效提升了网络吞吐量.网络编码思想对信息论、编码理论、密码学和计算机科学等相关领域产生了深远影响.索引编码:在一个多用户广播网络中,信源通过广播形式将信息发送给用户,以期每个用户得到自己所需信息.若信源知晓每个用户提前掌握的边信息,则可通过编码对其广播内容进行压缩,以减少所需广播数据量.这个问题被称为索引编码,其很多理念与技术源于网络编码思想,旨在提高无线网络的吞吐量、时延和可靠性等性能.无线网络编码缓存:网络环境的普及使大众生活对网络的依赖越来越强.随着移动视频点播等技术的发展,移动通信业务量爆炸增长.无线网络缓存方案旨在利用数据传输低峰期的空闲网络带宽,按一定策略预先将数据分发至网络用户端的缓存之中,以缓解数据传输高峰期的网络堵塞.分布式计算:随着数据量增长和人工智能深入发展,数据处理的规模和复杂度与日俱增,同时人们对数据处理的时间要求更为严苛.许多大型计算任务无法在单个数据处理终端完成,必须利用分布式计算思想,将大型计算任务分拆为多个小型子任务并分发至多个数据处理终端.分布式计算方案的设计需综合考虑来自掉队者、数据安全和算力浪费等多方面的挑战.隐私保护信息检索:分布式网络环境为信息安全领域带来新的挑战与机遇.隐私保护信息检索是信息安全领域经典问题之一,其目的是使用户在检索信息的同时保护其个人行为隐私.这个问题在集中式存储环境中已有一定系统性的研究,主要依赖于密码学思想方法.而在引入到分布式网络环境后,产生了一系列新型信息安全问题.上述问题在某种层面上也展示了“通信”与“计算”这两个信息处理的基本环节之间的交融.网络编码思想及其衍生问题,以一定的计算负荷换取通信效率,而分布式计算则是以一定的通信负荷简化数据计算任务.通信与计算的结合是当前信息科学问题总体趋势,也符合未来“通算一体化网络”新型信息论研究的发展需求.远至经典信息论中图的香农容量,近至分布式存储编码中再生码的割集界,离散模型和组合学方法与信息科学的发展一直密不可分,尤其在近年来分布式网络环境架构下的新型信息科学问题研究中,诸多离散模型层出不穷,组合编码、组合设计、图论和极值组合等组合学领域思想方法扮演着越来越重要的角色.在这些数学工具为信息科学提供理论支撑的同时,信息科学也为离散模型和组合学方法的研究带来新的动力,一定程度上反哺于数学理论发展.基于以上背景,本文围绕上述源于分布式网络环境的信息科学问题展开综述,着重介绍其中涉及的离散模型和组合学方法,期望能吸引组合界同仁关注这一交叉研究方向.第2节阐述网络编码理论的发展及其与子空间设计的关联.第3节介绍索引编码问题及其中基于图论的研究方法.第4和5节的主题分别是无线网络缓存方案和分布式计算,它们都可以用某种与极值图论或组合设计密切相关的组合阵列刻画.第6节讨论隐私保护信息检索方案及其中的组合思想.在其中部分章节,本文利用相关组合方法给出一些新的结果.最后,第7节总结全文,并简要讨论一些以上主题中涉及组合学思想方法的未来研究方向.2网络编码2.1研究现状定义2.1(网络)一个通信网络可以表示为一个有向无圈多重图D=(V,),其中,顶点集V152中国科学:数学第 53 卷第 2 期=S RM,S为若干信源节点,R为若干信宿节点,M为若干中间节点.每条有向边代表从其起点向其终点传输信息的信道,每个信道可传输一个单位大小的信息.对于任意节点P V,记其输入边集和输出边集分别为In(P)和Out(P).一般假设信源节点无输入边,信宿节点无输出边.网络中每个信源节点拥有若干单位大小的独立信息,信源节点将信息组织成数据包,经由通信网络中的信道发送出去.每个中间节点对其接收到的数据包进行必要的复制存储后再按某种规则发送.最终目的是使各信宿节点可通过其收到的所有数据包得到所有信源发送的信息.在传统路由网络中,中间节点P M只有接力传输的作用,即Out(P)中每条边传输的数据只能是来自In(P)中某条边上数据的复制,这严重限制了网络传输性能.2000年,Ahlswede等2在其开创性论文中提出网络编码思想,突破性地赋予中间节点处理数据的功能,并证明利用编码方法可使网络传输容量达到基于最大流最小割定理的理论上限45,48,有效提升了网络吞吐量.网络编码思想对信息论、编码理论、密码学和计算机科学等相关领域产生的深远影响,可参见文献13,40,87及其中的参考文献.定义2.2(网络编码)对于一个给定的网络D=(V,),D上的网络编码指的是其所有边上的一簇编码函数.对于每个信源节点S S,Out(S)中每条边上的数据包即为S所产生的单位信息.对于中间节点P M,Out(P)中每条边上的数据包为In(P)所有边上的数据包的函数.若上述所有函数均为线性函数,则此编码方案称为线性网络编码.若每个信宿节点R R可通过其收到的所有数据包解码得到所有信源发送的信息,则称此网络编码是网络D的一个解,也称网络D可解.显然,一个网络可解的必要条件是每个信宿节点与所有信源节点之间的最小割大于等于全部信源节点产生的单位信息个数.网络编码思想奠基性的贡献是证明上述必要条件同时也是充分条件.Li等77证明在上述条件下,利用有限域上的线性编码即可找到网络的解.Koetter和M edard67给出线性网络编码的局部和全局代数表示,清晰刻画了线性网络编码问题.Jaggi等58给出构造线性网络编码的多项式时间算法,但此算法需预知网络的具体拓扑结构.然而,很多实际应用中并不能预先知晓网络拓扑结构,为此Ho等55进一步提出随机线性网络编码,这一思想使线性网络编码有了真正走向实际应用的可能.在网络编码方案设计中,基域大小会影响各节点运算复杂度,因此人们希望在尽可能小的域上寻找网络的解.Ebrahimi和Fragouli42将早期的标量网络编码推广至矢量网络编码,即将每条边上的数据包从标量(有限域上的一个符号)推广至矢量(有限域上的一个向量),而中间节点的数据处理方式也从对若干标量的线性组合推广至对若干向量的矩阵运算.Etzion和Wachter-Zeh46将秩度量码和子空间码应用到矢量网络编码构造中,显著降低了基域大小.例2.1蝴蝶网络如图1所示,该网络具有一个信源节点S、两个信宿节点R1和R2及四个中间节点M1、M2、M3和M4.其中信源节点拥有两个单位大小的信息x和y,每条有向边表示一条信道,可传输一个单位大小的信息.该网络下每个信宿节点与信源节点之间最小割为2,即理论上信宿节点最多能接收到两个单位大小的信源信息.在传统路由网络中,中间节点仅能存储与转发消息,因此M3指向M4的信道上只能在x或y之中选择一个进行传输,进而两个信宿节点会有其中之一无法得到所有信源信息.网络编码思想赋予中间节点处理数据的能力,节点M3接收到x和y并将x+y传输给M4,从而使得两个信宿节点均可获得所有信源信息.实际网络通信中,信道噪声、链路故障和恶意攻击等因素会给数据带来替换错误或擦除错误,且通信网络中的错误会随着网络传播而逐步积累,比点对点通信中的错误更难分析处理.因此,研究带有纠错性能的网络编码是必要的.Cai和Yeung22于2002年首次提出网络纠错码的概念,作为传统代数纠错码在网络编码理论中的推广.文献23,24将源自点对点网络的代数编码方法推广至网络纠错码中.刻画传统纠错码性能的一些界也被推广至网络纠错码中131,包括球填充界(Hamming界)、153韩雪姣等:源于分布式网络的离散模型与组合学方法图1蝴蝶网络球覆盖界(Gilbert-Varshamov界)和Singleton型界.Zhang143,144提出网络纠错码极小距离的定义,并进一步独立提出改进的Singleton型界.类似传统代数编码,达到改进Singleton型界的网络纠错码被称为线性网络纠错极大距离可分码,简称为网络MDS(maximum distance separable)码.网络MDS码的存在性已被证明,文献51,88,131给出了具体构造方法.以上网络纠错码的研究,都需要已知网络拓扑结构.当网络拓扑结构未知时,随机网络编码模型中也可以设计性能良好的纠错码.文献66,103开启这一研究方向,定义了子空间上的距离和子空间码,由此给出随机线性网络纠错码,并给出这类码的球填充界与球覆盖界等理论分析.接下来第2.2小节将重点介绍子空间码及其与组合设计理论中的子空间设计的关联.2.2子空间码和子空间设计Koetter和Kschischang66首先定义了子空间码并将其运用在随机线性网络编码的纠错中.下面首先引入随机线性网络编码模型,然后介绍子空间码如何在其中进行纠错.定义2.3(随机线性网络编码)考虑具有单个信源单个信宿的网络,信源拥有M个单位大小的信息,信宿与信源之间的最小割大于等于M,网络有T条边但拓扑结构未知.每条边传输的数据视为Fnq上的矢量(用行向量表示).信源将M个信息X1,X2,.,XM输入网络,其中Xi F1nq(i=1,2,.,M).对于任意中间节点P M,Out(P)中每条边上的数据包是In(P)中所有边上的数据包的随机线性组合.最终信宿节点通过其接收到的数据包,以一定概率得到全部M个原始信息.在无噪声情形下,假设信宿节点接收到N个数据包Y1,Y2,.,YN(1 6 j 6 N).数据包Yj F1nq可表示为Yj=Mi=1aj,iXi,其中系数aj,i Fq是未知且随机的.在有噪声情形下,记Et F1nq为第t(1 6 t 6 T)条边上出现的错误,此时信宿节点接收到的数据包可表示为Yj=Mi=1aj,iXi+Tt=1bj,tEt,其中bj,t Fq也是未知且随机的.该模型用矩阵形式可表示为Y=AX+BE,其中,YNn的第j行为Yj(j=1,2,.,N),XMn的第i行为Xi(i=1,2,.,M),ETn的第t行为Et(t=1,2,.,T),A=aj,iNM与B=bj,tNT是对应的随机矩阵.首先观察无噪声时的模型Y=AX.由于A是完全随机的,那么信源发送的X与信宿收到的Y之间最大的相通之处是什么?答案是由两者的行向量各自张成的子空间.这两个子空间以极大的概率保持一致.受此启发,在随机线性网络编码模型中,Koetter和Kschischang66提出了子空间码,其核心思想是用子空间来代表所传输的信息.令P(Fnq)代表Fnq上的所有子空间,信源节点发送的信息是154中国科学:数学第 53 卷第 2 期P(Fnq)中的某个空间V,发送方法即选取矩阵X FMnq使得V=,即V是由X的行向量生成的空间.信宿节点收到矩阵Y FNnq,通过分析子空间U=推断原始信息对应的子空间V.在此设定下,回顾一些涉及子空间的常用符号.对两个子空间U和V,U+V=u+v:u U,v V 是同时包含U和V的最小子空间.如果U V=0,则U+V为两个空间的直和,记为U V.定义2.4(擦除算子)对于任意正整数k 0,定义作用在P(Fnq)上的算子Hk:如果dim(V)k,则Hk(V)为V上随机选取的k维子空间,否则Hk(V)=V.Hk称为P(Fnq)上的擦除算子.定义2.5(算子信道)定义C:P(Fnq)P(Fnq)为算子信道,信道的输入V和输出U满足U=Hk(V)E,其中,k=dim(U V),E代表错误空间.在输入V输出U的过程中,称该算子信道发生了=dim(V)k个维度擦除与t=dim(E)个维度错误.接下来定义两个子空间的距离.定义2.6(子空间距离)设V和V是P(Fnq)中的两个子空间,其距离定义为dS(V,V)=dim(V+V)dim(V V)=dim(V)+dim(V)2dim(V V).文献66验证了上述距离是P(Fnq)上的度量.基于子空间距离,可定义如下子空间码.定义2.7(子空间码)非空集合C P(Fnq)为一个子空间码,C中每个子空间称为一个码字,码的极小距离定义为dS(C)=minV,VC,V=VdS(V,V).特别地,若码C各码字维数相同,则称其为常维码(constant dimension code),也称Grassmannian码.上述子空间码的定义可以视为经典Hamming距离下的码在向量空间上的推广.类似地,常维码也是经典常重码在向量空间上的推广.相较于一般的子空间码,常维码更容易刻画与构造,即便如此,构造码率大的常维码仍不是一件容易的事情.若随机线性网络编码的算子信道的输入V取自某个子空间码C,信宿在接收到输出U时,可以寻找C中与U距离最近的子空间V,即V=argminV CdS(V,U).这种最小距离解码方法类似于经典Hamming距离下的码的极大似然译码算法.文献66中的下述定理揭示了子空间码在随机线性网络编码的算子信道下的性能.定理2.166设子空间码C P(Fnq)为算子信道的输入集,输入信息V C经过信道转化为输出U=Hk(V)E,其中dim(E)=t.称信道发生的最大擦除维数为=max0,maxV Cdim(V)k.如果2(t+)7的子空间设计.该构造被文献108,109推广至任意有限域Fq上的2-(v,3,q2+q+1)q.文献21给出了参数为3-(8,4,11)2的子空间设计,这也是第一个t=3的非平凡子空间设计.迄今为止,还没有发现t 4的非平凡子空间设计.特别地,当=1时,t-(v,k,1)q子空间设计也称q-Steiner系(q-Steiner system),记作Sq(t,k,v).利用q-Steiner系可以直接构造如下常维码.定理2.2一个q-Steiner系Sq(t,k,v)可视为P(Fvq)中的常维码,极小距离为d=2k 2t+2.于是,构造常维码的一种方法即是寻找对应的q-Steiner系.易知,若Sq(t,k,v)存在,则对于任意i(1 6 i 6 t 1),Sq(t i,k i,v i)也存在.于是Sq(t,k,v)的存在需要整除性必要条件:对于任意0 6 i 6 t 1,vitiq/kitiq需为整数.记Aq(v,d;k)为Fvq上极小距离为d、码字维数为k的常维码的码字个数最大值.维数k决定了极小距离至多为d=2k,此时对应的常维码中任意两个k维子空间U和V只有平凡交集U V=0.这种码类也称为k-部分展形(partial k-spread).易得Aq(v,2k;k)6qv1qk1,且该上界在k|v时是可达的,取等号时对应的码也称为k-展形(k-spread),本质上即为q-Steiner系Sq(1,k,v).当k v时,记v=tk+r,1 6 r 6 k 1,则Aq(v,2k;k)6 qv1qk1=t1s=0qsk+r.构造达到此上界的k-部分展形是一个困难的问题.文献16给出下述结果.定理2.3设v和k为正整数,v=tk+r,t 2,1 6 r 6 k 1.则存在Fvq上的k-部分展形S,且|S|=1+t1s=1qsk+r.由此可得Aq(v,2k;k)1+t1s=1qsk+r.此下界与理论上界仅相差qr 1.曾有学者猜测这个差距在任何参数下都不会再缩小,但文献44给出了F82上包含34个子空间的3-部分展形,这也是迄今为止唯一能突破qr 1这个差距的例子.此外,目前常维码的已知结果包括m 2和q=2时A2(3m+1,6;3)、A2(3m+2,6;3)、A2(4m+1,8;4)、A2(4m+2,8;4)的值,目前未确定的最小参数是129 6 A2(11,8;4)6 132.已知的非平凡q-Steiner系除了上述展形结构之外仅有S2(2,3,13).在其他参数下寻找q-Steiner系或证明其不存在性是子空间设计中极为重要也极为困难的问题.特别地,S2(2,3,7)(即Fano平面的q-模拟)的存在性仍是一个公开问题.除子空间设计外,通过构造秩度量码和轨迹码等代数编码方法也可以获得子空间码.子空间码的更多内容可参见文献50.3索引编码3.1研究现状索引编码(index coding)由Birk和Kol17提出,本质上是一类信源编码问题,与网络编码思想密切相关.索引编码问题的数学模型如下.单个信源与K个用户之间通过一条无噪广播信道相连.信源拥有N个相互独立的长度为B的文件W=W1,W2,.,WN,Wi FBq(i N,1,2,.,N).对于第k个用户,k K,记Uk=(Kk,Wk),其中Kk W代表用户k已知的文件集(也称为该用户的边信息集),Wk(W Kk)代表用户k需求的文件集,而余下的W(KkWk)称为用户k的干扰集.索引编码问题研究在已知Uk:k K的情形下,信源应如何通过编码方式设计广播内容,使所有用户可由广播内容和自身的边信息集译码得到所需文件.若对于任意两个不同用户k1和k2有Wk1 Wk2=,则称该索引编码问题是单播的,否则称其为组播的.更进一步地,若每个用户只需求单个文件且各用户需求不同,则称其为单一单播索引编码156中国科学:数学第 53 卷第 2 期问题.对于一般单播索引编码问题,可将单个用户k视作|Wk|个拥有同样边信息集但需求信息互不相同的子用户,于是所有单播索引编码问题皆可视作单一单播索引编码问题.本节剩余部分仅讨论单一单播索引编码问题,并不失一般性假设N=K.一个索引码由一个编码函数和N个解码函数组成.编码函数为E:FNBq FRBq,该编码函数将文件W1,W2,.,WN压缩为信源广播内容X=E(W1,W2,.,WN).用户k的解码函数为Dk:FRBqF|Kk|Bq FBq,用户k利用接收到的信源广播内容和自身边信息集译码得到所需文件,即Dk(X,WKk)=Wk.参数R称为索引码的码长.索引编码最基本的问题是在已知Uk:k K的情形下寻找码长最小的索引码,达到码长最小值的索引码即称为最优的.若编码函数E是线性的,则称该索引码为线性索引码.进一步地,如果线性编码函数E只涉及若干完整文件的线性组合,则称其为线性标量索引码;如果编码函数E是以文件的每个符号为单位进行运算,则称其为线性矢量索引码.索引编码问题可由其边信息图刻画.单播问题的边信息图一般由简单有向图表示,基于对此图的分析,文献12给出了索引码的奠基性结果,证明了线性最优标量索引码的码长等于边信息图的最小秩(minrank),并提出了基于边信息图的最大无圈诱导子图点数的(非线性)索引码码长下界.当信息图为有向无圈图、完美图等图类时,上述方法能完整解决索引编码问题,但对一般的边信息图计算最小秩被证明为NP(non-deterministic polynomial)困难.最小秩方法同样适用于组播索引编码问题.文献3,89,101,115,121研究了组播索引编码问题,该问题的边信息图一般由有向二部图或有向超图表示,文献101,115分别借助有向二部图的边信息图提出了文件分区多播和用户分区多播的方法.单播索引编码的设计与图染色之间也密切关联.一方面,索引编码码长上界可由边信息图的团覆盖数控制,在边信息图可转化为无向图时这一数值又等于其补图的染色数.另一方面,由边信息图导出的混淆图,其染色数直接决定了索引码码长的理论极限.因此,图染色的相关结论与方法被自然地引入到索引编码研究中.特别地,基于图染色的方法,文献3,81给出了非线性索引码能够突破线性索引码最小秩码长限制的例子.基于分布式网络背景,假设原始信息分布式存储于多个信源,文献90提出多信源索引编码问题,这是索引编码问题研究的重要分支.虽然多信源模型比单信源复杂,但单信源的某些研究方法可以推广至多信源的情形.例如,文献116将单信源模型的环覆盖界、完全图覆盖界和局部染色界推广到两个信源的单一单播索引编码的研究中,文献117将基于混淆图染色的索引码的构造方法引入到特定信息图下的双信源索引码的设计中,文献75将单信源模型下的最小秩方法推广到多信源情形.索引编码的研究还有许多变种.文献36提出安全索引编码问题,利用随机线性索引码达到一定抵抗窃听的能力.文献63提出索引编码中的隐私保护问题,以防止网络中各用户的边信息集或需求集的泄露.柔性索引编码模型不再预设用户具体需求,只需给每个用户传递一个不在其边信息集中的新文件,这个领域的工作包括NP困难的最优线性码的构造20、多项式时间算法下的次优索引码的构造104和基于图染色手段的最优码长分析69,7880等.3.2索引编码中的图论方法设信源拥有W=W1,W2,.,WN,为方便讨论,只考虑Wi F2.Wi FBq的情形也可自然推广.用户k拥有边信息集Kk W且需求Wk(1 6 k 6 N).定义3.1(边信息图)一个单一单播索引编码问题的边信息图D=(V,E)是简单有向图,其中V=1,2,.,N,顶点k代表需求Wk的用户k.有向边(i,j)E当且仅当Wj Ki,即157韩雪姣等:源于分布式网络的离散模型与组合学方法Wj落在用户i的边信息集中.Out(i)=j V:(i,j)E即为用户i的边信息集Ki的指标集,In(i)=j V:(j,i)E即为边信息集中包含Wi的用户的指标集.文献12定义了边信息图的最小秩,并证明了最小秩的值即为线性最优标量索引码的码长.定义3.2(最小秩)对给定的边信息图D=(V,E),如果矩阵A=(aij)NN满足(1)aii=1;(2)若(i,j)/E,则aij=0,则称这样的矩阵A适配于图D.D的最小秩定义为minrk2(D):=minrk2(A):A适配于D,其中rk2(A)代表矩阵A在F2上的秩.定理3.1对给定的边信息图D,线性最优标量索引码的码长即为minrk2(D).最优线性索引码的构造如下.设矩阵A适配于图D且rk2(A)=minrk2(D).对A做行变换,使得前minrk2(D)行线性无关,记为A,而后N minrk2(D)行全为0.令索引码的编码函数为X=A(W1,W2,.,WN)T.于是码长即为minrk2(D).每个用户收到X即等价于收到Y=A(W1,W2,.,WN)T.用户k的解码只需使用Ak(W1,W2,.,WN)T,其中Ak代表矩阵A的第k行.在这个线性组合中,Wk的系数非零,而用户k干扰集中文件的系数皆为0,于是用户k可以利用其部分边信息求解出所需求的Wk.利用上述方法可以确定n个点的有向圈对应的索引编码问题的线性最优码长为n 1,文献12同时指出,如果边信息图中不存在圈,则最优码长为该图的点数,即只能依次发送每个文件才能满足全部用户的需求.因此最优码长的下界可由边信息图点数最大的无圈诱导子图给出.该下界虽然是从线性编码角度得出的,但同样适用于非线性索引码.定理3.2记MAIS(D)为简单有向图D的最大无圈诱导子图(maximal acyclic induced subgraph,MAIS)的点数,则以D为边信息图的索引码的码长至少为MAIS(D).例3.1单个信源与4个用户之间通过一条无噪广播信道相连.信源拥有4个相互独立的文件W=W1,W2,W3,W4.4个用户分别为U1=(W2,W4,W1),U2=(W1,W2),U3=(W2,W3),U4=(W3,W4).则该问题的边信息图D如图2所示.注意到D是包含有向圈的,但由顶点2、3和4诱导的子图是无圈的,因此该问题的MAIS下界为3.达到最优码长的方案可以是依次广播W1+W2、W3和W4.事实上,最优非线性索引码的码长可由下述混淆图的染色数决定,混淆图的定义如下.定义3.3(混淆图)设有向图D是某索引编码问题的边信息图,构造无向图C(D)如下.点集V=FN2,两个顶点u=(u1,.,uN)与v=(v1,.,vN)之间连边当且仅当存在i N,满足ui=vi且对于任意(i,j)D有uj=vj.称无向图C(D)为D的混淆图.图2索引编码边信息图示例158中国科学:数学第 53 卷第 2 期混淆图中的每个顶点实则对应于W1,W2,.,WN一组可能的取值.若u和v在混淆图中连边,则用户i所拥有的边信息完全一致,而自身需要译码得到的Wi不同,于是索引码的必要条件是一定要将u和v编码为不同的码字,否则将导致用户i的解码失败.因此,编码函数E:FN2 FR2的值域大小至少需为混淆图染色数(C(D),从而码长有下界log2(C(D).达到此界的非线性索引码的构造可基于混淆图C(D)的任意一个使用(C(D)种颜色的染色,编码函数将信息映射为其对应顶点的颜色标号的二进制表示,用户在知晓此染色信息后,从图中所有染此色的点中寻找到唯一的与自身边信息吻合的点,进而通过此点译码得到所需信息.结合上述码长上下界的基本结果可知,若对于信息图G有minrk2(D)=MAIS(D)或minrk2(D)=log2(C(D),则最优码长可确定且线性编码方式即能达到最优.例如,完美图、奇洞及其补图对应的最优索引码长都达到minrk2(D).但在一般情形下,无论求解最小秩或求解混淆图的染色数都是NP困难的,更多做法是利用已知最优码长的特殊图类覆盖边信息图.当确定部分特殊图类对应的最优码长后,对于一般的信息图D,可以考虑用已解决的图类对D做顶点覆盖,即将顶点集划分为V1,V2,.,Vt,再将每个Vi诱导的子图看作一个子问题分别解决.例如,由最小秩方法知n个点完全图对应的线性最优码长为1,编码函数为将这n个点对应的文件进行异或运算.将D的顶点集拆分为若干完全子图(即做D的团覆盖)即可得到最优码长的上界,当D是无向图(即有向边是成对出现的)时,D的补图D的染色数即为D的团覆盖数.更进一步地,对D运用分数染色方法,可以获得更小的上界:对D的每个顶点染b个颜色使相邻的两个顶点无相同颜色,则f(D)b是最优码长上界,其中f(D)为D的分数染色数.对应的编码策略为,将每个顶点对应的文件均匀地分为b份并随机分配给子文件一个该点的颜色,且每个文件的子文件分配的颜色各不相同,编码函数即为将每个颜色下的子文件进行异或运算.分数染色方法是一种矢量线性编码策略,线性编码策略可以视为其特殊情形,因此f(D)b6(D).3.3新的结果基于分布式网络背景,文献90提出了多信源索引编码问题.许多单信源模型下的方法可以推广至多信源模型的研究之中.本小节以双信源为例,将单信源模型中的MAIS下界思想加以推广.考虑两个信源、N个用户的无噪单一单播索引编码问题.假设该索引编码系统中具有N个相互独立的文件W=W1,W2,.,WN,这些文件分布式地存放于两个信源中,两个信源拥有的信息分别记为S1和S2,S1 S2=W.该索引编码问题的边信息图D与单信源模型下的定义相同.仿照单信源模型的MAIS下界,可以证明,对于满足下列性质的边信息图,最优索引编码的码长必须为N,也即不存在比逐个广播所有文件更好的方法.定理3.3在双信源无噪单一单播索引编码问题中,如果边信息图D中不包含以下结构:(A)顶点全部在S1或S2的指标集中的有向圈;(B)S1 S2=的指标集中的某个顶点位于D的某个有向圈中;(C)S1 S2=的指标集中的某个顶点通过一条有向路径指向某个有向圈中的顶点,则该索引编码问题的最优码长为N.证明回顾有向图中强连通的定义.一个有向简单图的两个顶点u与v之间,若既存在从u到v的有向路径,又存在从v到u的有向路径,则称两个点之间强连通.强连通是顶点集上的等价关系,对应的每个等价类称为一个强连通分支.159韩雪姣等:源于分布式网络的离散模型与组合学方法考虑一个不包含定理所述结构的信息图D,设D共有s个强连通分支,1 6 s 6 N.将这s个强连通分支编号为D1,D2,.,Ds,使得该标号下对于任意1 6 i 2,|V(Ds)|2,注意到D的顶点数有限,且没有任何从Ds出发指向其他强连通分支的顶点,即Ds中顶点对应用户的边信息只在Ds中.由上述分析知R(Ds)=R(Ds|U1)+R(Ds|U2)=|V(Ds)|,即每个Ds中顶点代表的信息都只能通过该信源系统发送信息本身来满足用户的需求,且发送完毕后可以在D中直接删掉对应的顶点和与之相连的有向边.设删后的图为D,则D中没有任何从Ds1出发指向其他强连通分支的顶点,按上述分析依次类推得R(D)=N.由此,当边信息图中包含一个无以上三种结构的诱导子图时,对应的最优索引码码长的下界即为该诱导子图的顶点数.这样的子图也可以通过删除边信息图的顶点及其邻边,直到边信息图中不再包含以上三种结构的方式得到.注3.1在定理3.3提到的三种结构均可能在双信源情形下使信源广播量减1,(A)结构可视为单信源情形,自然有向圈结构可带来广播量减1;设(B)和(C)结构中出现的一个S1 S2中文件为Wt,则对应的编码策略为分别将结构中除Wt的点与Wt进行异或运算并由信源S1广播包含U1中文件的内容,信源S2广播其他内容,此时的广播量比结构中的点数少1.4编码缓存4.1研究现状网络中数据需求量具有时变性,数据需求高峰期的网络堵塞影响用户体验,数据需求低峰期的带宽闲置浪费网络资源.Maddah-Ali和Niesen83提出了无线网络缓存方案,旨在利用低峰期闲暇带宽,采取一定策略将数据预分发至网络各用户端缓存中,以减少高峰期通信负荷.定义4.1(编码缓存)考虑由单个服务器和K个用户组成的网络,服务器与用户间通过一条无噪共享链路相连.服务器存储N个相互独立文件W1,W2,.,WN,Wi FB2,i N.用户k K具有独立的缓存,可用来存储Zk FMB2,其中M是给定的实数,M K且非编码放置下(即放置的缓存仅为各文件独立的数据包,无编码处理)达到最优.然而,R并非衡量缓存方案优劣的唯一指标,实现Maddah-Ali和Niesen的方案需要将每个文件等分为F=(KKM/N)份(该数值称为分包数,影响方案实现的复杂度),这一数值随K呈指数增长,这是他们方案的一个缺陷.缓存方案的后续研究中往往给定参数K和MN(与K无关的比例),研究传输率R和分包数F作为K的函数的表现.编码缓存方案与组合数学之间的紧密联系,最初由Yan等127通过一类组合阵列刻画,此阵列称为放置分发阵列(placement and delivery array,PDA),描述了放置阶段和分发阶段的具体规则.Yan等127给出了两类PDA的构造,同Maddah-Ali与Niesen的方案相比,在小幅增加传输率R的代价下显著降低分包数F,但F仍随K呈指数增长.Shangguan等100将PDA的构造与极值超图中的Tur an型问题联系起来,证明了PDA可对应于3一致3部超图且任意6个顶点诱导的子图至多包含3条边(实为极值超图中著名的(6,3)-问题).基于此观察,Shangguan等100给出在传输率R保持常数级别时分包数F达到K的次指数级别的方案,同时证明F不可能达到K的线性级别.沿着类似思路,Shanmugam等102利用Ruzsa-Szem eredi图得到R为K的多项式级别、F为K的线性级别的缓存方案.此外,PDA和对应超图的研究,与其他多种组合结构之间产生了联系.基于正交阵列30、二部图的强边染色129等方法都被应用于PDA的构造中,基于线性分组码114、组合设计1的构造方法虽然没使用PDA语言,但本质上可以转化为PDA.文献28,122讨论了PDA的递归构造.161韩雪姣等:源于分布式网络的离散模型与组合学方法但截至目前,关于传输率R为常数级别而分包数F为K的多项式级别的缓存方案,既没有任何构造,也无法从理论上证明其不存在性.上述工作针对的是缓存问题提出伊始的模型:集权式网络(单个核心服务器统筹规划两个阶段)、非编码放置(缓存内容为单个文件的部分区块)、离线版本(数据库无更新).近年来,缓存问题模型逐步扩展,包括但不限于:线性编码放置:放置阶段的缓存内容可以是文件子数据包的线性组合,在这种模型下文献29给出的方案有更小分包数.非集权式编码缓存:现实中大部分网络并不具备统筹整个编码缓存过程的中央服务器,文献84考虑了随机缓存放置时的编码.无线D2D(device-to-device)网络下的编码缓存:该模型下分发阶段由用户完成,文献59给出该问题在固定缓存大小时最优传输率的上下界刻画.安全编码缓存模型:引入安全需求,防止窃听者通过窃听分发阶段的信息而得到任何原始文件信息,文献98给出该问题在固定缓存大小时最优传输率的上下界刻画.多接入网络的编码缓存:该模型假设网络中有多个缓存单元,用户可按一定规则从一部分缓存单元中获得信息.该模型由文献52提出,交叉可分解设计64、PDA97和对称索引编码95等被用来设计该问题的编码缓存方案.在线编码缓存:服务器中文件动态可变,进而用户的缓存内容也是动态的,每轮的分发阶段可以改变其缓存内容.该模型是文献83提出的未来研究课题之一,其目标为在系统长期运行过程中降低数据传输的平均负载.文献91,128探讨了此模型下缓存更新的相关算法.4.2PDA及其组合构造集权式网络、非编码放置、离线版本下的最初编码缓存模型可由Yan等127提出的放置分发阵列PDA刻画.定义4.3(放置分发阵列PDA)设K、F、Z和S是正整数,阵列P=pj,kFK中每个项取自S=1,2,.,S或者特殊符号.如果P满足以下条件:(1)在每列恰好出现Z次;(2)任意整数s S在每一行、每一列至多出现一次;(3)对于任意j1=j2,k1=k2,若pj1,k1=pj2,k2=s S,则pj1,k2=pj2,k1=,则称阵列P为(K,F,Z,S)-PDA.记gs为s S在PDA中