摘要
考虑网络函数计算问题,即在一个有向无圈网络上,单信宿节点需要零错误重复计算一个函数,称为目标函数,其输入参数是由一组信源节点生成的独立信源符号.对于该问题,其计算容量被定义为平均使用一次网络时,信宿节点最多可以零错计算目标函数的次数.对于传统的通信-计算分离编码,信宿节点需先接收所有需要的信源符号再单独计算目标函数,这就退化为网络编码问题,其传输速率受网络编码容量约束.而通信-计算联合编码是指网络节点根据函数特性进行实时编码使信宿节点直接解码目标函数值,其性能由计算容量表征.为了刻画二者之间的性能差异,网络函数计算增益被提出,其定义为网络函数计算容量与网络编码容量的比值.通过分析计算容量与编码容量,闭式量化在反向组合网络上计算一类线性函数的计算增益,得到由3个参数所决定的显式表达式.进一步,通过分析这3个参数的渐近性,完全刻画计算增益的渐近特性,证明该计算增益可趋于无穷大,从而说明通信-计算联合编码策略较传统通信-计算分离编码方式在计算效率方面通常具有显著性提升.
The problem for the computation of the network function is considered in this paper,where in a directed acyclic network,a single sink node requires to repeatedly compute a target function of source messages generated by multiple source nodes with zero error.The information-theoretic computing capacity is defined as the maximum average number of times that the function can be computed with zero error per use of the network.For the traditional way of separating communication and computation,the sink node computes the target function after receiving all the needed source messages.This reduces to a problem of network coding,where the transmission rate is con⁃strained by the capacity of network coding.The joint coding of communication and computation allows the nodes to encode based on the properties of the function such that the sink node can compute the target function directly.The performance is characterized by the com⁃puting capacity.In order to quantify the performance gap,we introduce the concept of computing gain,which is defined as the ratio of the computing capacity to the capacity of network coding.In this paper,we consider the model of computing as a class of linear functions over reversed combination networks.For this model,by evaluating the computing capacity and the capacity of network coding,we explic⁃itly quantify the computing gain in a closed form,which is determined by three parameters.Further,based on the asymptotic behavior of these parameters,we fully analyze the asymptotic properties of the computing gain.The obtained results show that the gain of computing capacity over the capacity of network coding can be unbounded.Thus,this implies that the efficiency of integrating communication and computation over the separate way of communication and computation is significant in general.
作者
光炫
李丹
李珊珊
孙秀芳
GUANG Xuan;LI Dan;LI Shanshan;SUN Xiufang(School of Mathematical Sciences,Nankai University,Tianjin 300071;School of Science,Tianjin University of Technology,Tianjin 300384)
出处
《四川师范大学学报(自然科学版)》
2026年第2期170-183,F0002,共15页
Journal of Sichuan Normal University(Natural Science)
基金
国家自然科学基金(62171238和62461160306)
天津市高等学校研究生教育改革研究计划项目、南开大学本科教育教学改革项目(NKJG2025161)。
关键词
网络函数计算
网络编码
计算容量
计算增益
反向组合网络
network function computation
network coding
computing capacity
computing gain
reversed combination network
