1、中国科学:数学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,殷剑
2、兴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)资助项目摘要近年来,
3、分布式网络环境架构下的诸多新型信息科学问题为经典信息论和编码理论带来了新的挑战.这些问题的研究涉及多种离散模型,组合设计、图论、组合编码和极值组合学等组合学方法在其中发挥了至关重要的作用.本文选取网络编码、索引编码、编码缓存、分布式计算和隐私保护信息检索这5个源于分布式网络环境的信息科学前沿热点问题,简要介绍各问题研究进展,并着重介绍其中涉及的离散模型与组合学思想方法.同时,本文针对上述多个专题分别给出一些新结果.关键词分布式网络网络编码索引编码编码缓存分布式计算隐私保护信息检索MSC(2020)主题分类05B99,68P30,68R051背景简介数字化、网络化和智能化是新一轮科技革命的突出特
4、征,也是新一代信息技术的聚焦点,产业升级换代为这些特征赋予新的内涵.数字化从计算机化向数据化发展,后者的核心是对信息技术革命与经济社会活动交融生成的大数据的深刻认识与深层利用.网络化已从互联网延拓到以工业互联网、车联网、智能家居为代表的物联网,实现人、物、服务之间交叉互联.智能化是信息技术发展的永恒追求,引领人工智能技术一代代发展.新一代信息技术的发展,必然会产生诸多新型信息科学问题,为经典信息论和编码理论带来新挑战.特别地,在当前大数据时代背景下,分布式网络环境架构引领了近20年来的信息科学多个前沿热点方向.本文围绕分布式网络环境架构下的下述5个信息问题展开讨论.韩雪姣等:源于分布式网络的离
5、散模型与组合学方法网络编码:网络通信最基本的目的是将信息从信源节点无差错地传输至信宿节点.在传统路由网络中,中间节点只有接力传输的作用.网络编码通过赋予网络节点一定的计算能力,有效提升了网络吞吐量.网络编码思想对信息论、编码理论、密码学和计算机科学等相关领域产生了深远影响.索引编码:在一个多用户广播网络中,信源通过广播形式将信息发送给用户,以期每个用户得到自己所需信息.若信源知晓每个用户提前掌握的边信息,则可通过编码对其广播内容进行压缩,以减少所需广播数据量.这个问题被称为索引编码,其很多理念与技术源于网络编码思想,旨在提高无线网络的吞吐量、时延和可靠性等性能.无线网络编码缓存:网络环境的普及
6、使大众生活对网络的依赖越来越强.随着移动视频点播等技术的发展,移动通信业务量爆炸增长.无线网络缓存方案旨在利用数据传输低峰期的空闲网络带宽,按一定策略预先将数据分发至网络用户端的缓存之中,以缓解数据传输高峰期的网络堵塞.分布式计算:随着数据量增长和人工智能深入发展,数据处理的规模和复杂度与日俱增,同时人们对数据处理的时间要求更为严苛.许多大型计算任务无法在单个数据处理终端完成,必须利用分布式计算思想,将大型计算任务分拆为多个小型子任务并分发至多个数据处理终端.分布式计算方案的设计需综合考虑来自掉队者、数据安全和算力浪费等多方面的挑战.隐私保护信息检索:分布式网络环境为信息安全领域带来新的挑战与
7、机遇.隐私保护信息检索是信息安全领域经典问题之一,其目的是使用户在检索信息的同时保护其个人行为隐私.这个问题在集中式存储环境中已有一定系统性的研究,主要依赖于密码学思想方法.而在引入到分布式网络环境后,产生了一系列新型信息安全问题.上述问题在某种层面上也展示了“通信”与“计算”这两个信息处理的基本环节之间的交融.网络编码思想及其衍生问题,以一定的计算负荷换取通信效率,而分布式计算则是以一定的通信负荷简化数据计算任务.通信与计算的结合是当前信息科学问题总体趋势,也符合未来“通算一体化网络”新型信息论研究的发展需求.远至经典信息论中图的香农容量,近至分布式存储编码中再生码的割集界,离散模型和组合学
8、方法与信息科学的发展一直密不可分,尤其在近年来分布式网络环境架构下的新型信息科学问题研究中,诸多离散模型层出不穷,组合编码、组合设计、图论和极值组合等组合学领域思想方法扮演着越来越重要的角色.在这些数学工具为信息科学提供理论支撑的同时,信息科学也为离散模型和组合学方法的研究带来新的动力,一定程度上反哺于数学理论发展.基于以上背景,本文围绕上述源于分布式网络环境的信息科学问题展开综述,着重介绍其中涉及的离散模型和组合学方法,期望能吸引组合界同仁关注这一交叉研究方向.第2节阐述网络编码理论的发展及其与子空间设计的关联.第3节介绍索引编码问题及其中基于图论的研究方法.第4和5节的主题分别是无线网络缓
9、存方案和分布式计算,它们都可以用某种与极值图论或组合设计密切相关的组合阵列刻画.第6节讨论隐私保护信息检索方案及其中的组合思想.在其中部分章节,本文利用相关组合方法给出一些新的结果.最后,第7节总结全文,并简要讨论一些以上主题中涉及组合学思想方法的未来研究方向.2网络编码2.1研究现状定义2.1(网络)一个通信网络可以表示为一个有向无圈多重图D=(V,),其中,顶点集V152中国科学:数学第 53 卷第 2 期=S RM,S为若干信源节点,R为若干信宿节点,M为若干中间节点.每条有向边代表从其起点向其终点传输信息的信道,每个信道可传输一个单位大小的信息.对于任意节点P V,记其输入边集和输出边
10、集分别为In(P)和Out(P).一般假设信源节点无输入边,信宿节点无输出边.网络中每个信源节点拥有若干单位大小的独立信息,信源节点将信息组织成数据包,经由通信网络中的信道发送出去.每个中间节点对其接收到的数据包进行必要的复制存储后再按某种规则发送.最终目的是使各信宿节点可通过其收到的所有数据包得到所有信源发送的信息.在传统路由网络中,中间节点P M只有接力传输的作用,即Out(P)中每条边传输的数据只能是来自In(P)中某条边上数据的复制,这严重限制了网络传输性能.2000年,Ahlswede等2在其开创性论文中提出网络编码思想,突破性地赋予中间节点处理数据的功能,并证明利用编码方法可使网络
11、传输容量达到基于最大流最小割定理的理论上限45,48,有效提升了网络吞吐量.网络编码思想对信息论、编码理论、密码学和计算机科学等相关领域产生的深远影响,可参见文献13,40,87及其中的参考文献.定义2.2(网络编码)对于一个给定的网络D=(V,),D上的网络编码指的是其所有边上的一簇编码函数.对于每个信源节点S S,Out(S)中每条边上的数据包即为S所产生的单位信息.对于中间节点P M,Out(P)中每条边上的数据包为In(P)所有边上的数据包的函数.若上述所有函数均为线性函数,则此编码方案称为线性网络编码.若每个信宿节点R R可通过其收到的所有数据包解码得到所有信源发送的信息,则称此网络
12、编码是网络D的一个解,也称网络D可解.显然,一个网络可解的必要条件是每个信宿节点与所有信源节点之间的最小割大于等于全部信源节点产生的单位信息个数.网络编码思想奠基性的贡献是证明上述必要条件同时也是充分条件.Li等77证明在上述条件下,利用有限域上的线性编码即可找到网络的解.Koetter和M edard67给出线性网络编码的局部和全局代数表示,清晰刻画了线性网络编码问题.Jaggi等58给出构造线性网络编码的多项式时间算法,但此算法需预知网络的具体拓扑结构.然而,很多实际应用中并不能预先知晓网络拓扑结构,为此Ho等55进一步提出随机线性网络编码,这一思想使线性网络编码有了真正走向实际应用的可能
13、.在网络编码方案设计中,基域大小会影响各节点运算复杂度,因此人们希望在尽可能小的域上寻找网络的解.Ebrahimi和Fragouli42将早期的标量网络编码推广至矢量网络编码,即将每条边上的数据包从标量(有限域上的一个符号)推广至矢量(有限域上的一个向量),而中间节点的数据处理方式也从对若干标量的线性组合推广至对若干向量的矩阵运算.Etzion和Wachter-Zeh46将秩度量码和子空间码应用到矢量网络编码构造中,显著降低了基域大小.例2.1蝴蝶网络如图1所示,该网络具有一个信源节点S、两个信宿节点R1和R2及四个中间节点M1、M2、M3和M4.其中信源节点拥有两个单位大小的信息x和y,每条
14、有向边表示一条信道,可传输一个单位大小的信息.该网络下每个信宿节点与信源节点之间最小割为2,即理论上信宿节点最多能接收到两个单位大小的信源信息.在传统路由网络中,中间节点仅能存储与转发消息,因此M3指向M4的信道上只能在x或y之中选择一个进行传输,进而两个信宿节点会有其中之一无法得到所有信源信息.网络编码思想赋予中间节点处理数据的能力,节点M3接收到x和y并将x+y传输给M4,从而使得两个信宿节点均可获得所有信源信息.实际网络通信中,信道噪声、链路故障和恶意攻击等因素会给数据带来替换错误或擦除错误,且通信网络中的错误会随着网络传播而逐步积累,比点对点通信中的错误更难分析处理.因此,研究带有纠错
15、性能的网络编码是必要的.Cai和Yeung22于2002年首次提出网络纠错码的概念,作为传统代数纠错码在网络编码理论中的推广.文献23,24将源自点对点网络的代数编码方法推广至网络纠错码中.刻画传统纠错码性能的一些界也被推广至网络纠错码中131,包括球填充界(Hamming界)、153韩雪姣等:源于分布式网络的离散模型与组合学方法图1蝴蝶网络球覆盖界(Gilbert-Varshamov界)和Singleton型界.Zhang143,144提出网络纠错码极小距离的定义,并进一步独立提出改进的Singleton型界.类似传统代数编码,达到改进Singleton型界的网络纠错码被称为线性网络纠错极大
16、距离可分码,简称为网络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,