1. 引言
网络编码(network coding, NC)通过中间节点编码,汇点基于编码理论译码提高网络容量,成为“5G+”或“6G”移动网络和类ad hoc带限网络(移动自组网、无线传感器网络)的关键技术 [1] [2] [3] 。但是任意中间节点受到攻击后,恶意信息会随着中间节点编码进入信息分组并转发,引发网络安全问题。文献 [4] 指出,卷积网络编码(Convolutional NC, CNC)为该问题的解决提供了思路和安全保障,成为NC研究的重点。
CNC早期为规避复杂信息流问题,假设传输无时延,保证时延与分组信息的独立性,针对无环网络相关编码算法展开研究,使得无环网络编码在单会话和多会话模式中与传统路由协议“存储–转发”机制所获得的网络容量一致,其值与网络节点数目正相关 [5] [6] [7] 。文献 [4] [8] [9] 指出有环网络为兼顾网络因果性,必须考量时延等参数及独立会话等新特性,“多会话–单播”模式网络编码能够以大概率获得更高的网络容量,使其成为CNC研究的重点。文献 [10] 指出对于单播、多播等无环网络,网络最大吞吐量可达源点和汇点之间的最小割,传统路由机制无法达到该极限值。在此基础上,文献 [11] 针对有环网络提出一种CNC机制,并证明了最小割边界对应最优码的存在性。但上述研究存在的共性问题是节点必须获得网络拓扑先验信息,这对于动态变化的网络而言,感知开销和处理时延将明显增加。文献 [12] 指出,有环网络中对于包含源点的所有子网A,源点速率之和r不大于汇点和A之间的最小割能力且内核资源池足够大时,根据大数定理,所有汇点从中随机选择编码内核可大概率恢复出传输的符号信息,且该随机线性网络编码算法可用于拓扑动态变化的无中心授权(用于分配编码内核)网络。文献 [13] [14] 以此为基础,设计时变译码算法,使得任意节点可以利用网络冲激响应的前n + L段用时n恢复传输的符号,L为译码延时,但其全冲激响应过于依赖全局编码内核,这使得其实现过程必须建立在源点容量区域已知和汇点译码算法已知的两个前提条件上。二者任一个条件不成立时,需要设计优化机制,以确定系统传输函数或特征多项式等参数,便于汇点处的译码操作。文献 [15] 分析现有译码方法的基础上,指出有环网络中的CNC译码算法有待进一步完善。
论文在此基础上,规避以上两个条件的判断环节,提出差异化CNC译码算法以及容量区域参数判定方法。译码算法由汇点执行初始化算法预测传输矩阵,求解差分方程实现,根据节点初始状态是否具备置零功能,差异化设计与之对应的译码机制;容量区域判定算法在假设传输矩阵为满秩矩阵的基础上,分析允许节点执行的最大传输速率。最后仿真分析了时延、吞吐量、丢包率、控制开销等性能指标,证明了设计的CNC译码机制的可行性和有效性。该CNC译码机制的实现为缓解NC网络安全问题提供一定的理论基础。
2. 问题描述
控制理论指出,利用冲激响应(Impulse Response, IR)可识别未知线性时不变(Linear time invariant, LTI)系统,其方法是通过获取参数矩阵M、N、P、Q,建立系统状态空间表达式,使系统输入输出关系满足状态方程
(1)
式中g、o、s分别为输入向量、输出向量和状态向量,且各值为统计方法获得的近似值。状态空间表达式确定后,通过z变换可得系统传输函数
(2)
式中
、
、
分别为矩阵M的特征多项式、系统传输函数的z变换、邻接矩阵。文献 [16] [17] 指出,式(2)对应的状态空间表达式也可用于表征包含CNC对应的有环网络。同时只要确定了
和
,输入输出关系便唯一确定。文献 [18] 提出一种利用冲激响应
构建Hankel矩阵,获得已知LTI系统输入输出关系,并通过奇异值分解(Singular value decomposition, SVD)构建系统传输函数
的方法,但方法为整个实数或复数域,其作用域需作进一步限定。
在此基础上,当
已知时,LTI系统传输函数便唯一确定。系统输出信号通过包含
的有限冲激响应(Finite impulse response, FIR)滤波器后,系统传输函数进一步写为
(3)
对于式(3),文献 [19] 提出通过Hankel矩阵次对角线获得特征多项式
的方法,但该方法依赖系统阶数、状态向量最小实现维度等先验信息,实现复杂度较高。若仅建立边数、最大可达速率等基本参数的关联,将很大程度上可降低算法实现复杂度。同时式(2)、式(3)为优化算法的设计提供了基本思路。
令通信网络由有向图
表示,N为节点集合,E为边/链路集合,且每条链路均用无噪声有向链路表示,每个时间单元均可传输一个符号,各符号从标量域A中选择。假设每条链路任意两个符号传输之间为一个单位时延,且所有链路均已同步。
令S为源点集合,R为汇点集合。任意源点
单位时间内符号发送速率为Vs,汇点
期望接收所有源点发送的符号。对于每条边
,
和
分别为e的两个端点,且符号从u向d传输,于是任意节点发送和接收符号对应的边集合可表示为
和
。任意时刻t链路e传输的符号记为
。基于上述符号定义,链路
上发送的符号为节点j上一时隙接收的符号与产生符号的线性组合,式(1)可写为
(4)
其中
为时刻t节点j产生的第k个符号,
为节点j提前选定的本地编码内核。
定义序列
时移操作符为
那么
(5)
令状态列向量
长度为
,传输的各符号表示为
。输入序列
,其中
为源点
对应输入序列,
列向量维度为
。在系统传输函数已知情况下,
,令
,任意节点状态向量
零状态值大概率为零,即
时,
。当系统无法获得网络拓扑、本地编码内核等先验信息时,算法仍然需要源点和汇点在初始化开始之前获得部分网络参数,如源点集合和传输速率/速率上边界、网络边的数目或上边界等先验参数,那么此时
,经过时延
后,接收符号
。上述两类参数需确定容量区域内的节点传输速率
。
于是有环网络CNC译码机制需解决三个问题:1) 零输入状态时的CNC初始化,相应节点具有重置/清零功能;2) 非零初始状态时的CNC初始化,相应节点无重置/清零功能;3) 各源点的容量区域确值。
3. 方案设计
本节针对以上问题,区分网络节点有、无重置/清零操作,设计算法1 (有重置操作时初始化)和算法2 (无重置操作时初始化)实现域内节点参数及矩阵的初始化,本质是在确定接收矩阵和发送矩阵后,将其与接收向量代入输入输出关系方程,从而获得发送向量。二者区别在于,算法1通过重置操作后,无需计算常数向量,其执行效率优于算法2。而后设计算法3通过汇点检查传输矩阵解决源点容量区域确值问题,用于确定源点所允许的最大可达速率区间,使汇点能够成功接收分组信息,防止数据溢出,而传输矩阵依赖于初始化算法,因此算法3必须在算法1或算法2之后执行。于是优化机制设计如图1所示。算法首先判断区域内节点是否具有清零/重置功能,如果有执行算法1进行初始化,否则执行算法2进行初始化。当初始化完成后,执行算法3完成容量区域确值。最后网络运行相关协议及数据分发,直至完成数据分组传输。初始化算法及容量区域判定算法的执行均为汇点译码提供一定的基础数据支撑。
如前所述,算法目的是对汇点r建立输出序列g和输出序列o之间的关系,以此译码获得发送符号,即算法的本质是使汇点建立如下差分方程
(6)
那么问题的关键在于从接收序列o中确定满足式6的多项式
和矩阵
。下面分别分析算法1~3的求解思路及流程。
3.1. 有重置操作时初始化
令T为网络中的边数。为确保输入输出关系对所有节点适用,T足够大时,在此增加2个虚拟节点和Ve个虚拟边,不影响网络整体性能,且虚拟节点和虚拟边不与原始网络物理互连,不影响实际网络性能分析,此时新网络对应的边数仍用T表征。根据s、g和o的定义,对于任意汇点r,网络状态空间表达式可用式(1)表示。
矩阵M和N维度分别为
和
,二者均由网络结构和本地编码内核决定;矩阵C和
D为二值矩阵(仅包括0和1)。对于任意汇点r,式(1)对应的一般解可写为
(7)
Figure 1. Flow chart of the optimization algorithm
图1. 优化算法流程图
当
时,令输入序列
为单位向量
其中
为基向量,即
那么输出序列可表示为
将输出序列组合为矩阵形式,可表示为
(8)
由于
为矩阵M的特征多项式,令
为多项式系数,则
(9)
那么下式成立
那么此时需要设计满足下式的非零多项式
(10)
线性方程(10)包含无穷多个方程式,由于方程式之间线性相关,那么只需确定部分方程组即可。对于
,
(11)
成立,当确定T个方程组后即可从输出序列中恢复输入序列。由式(6)和式(11)可知,若
成立,即
为满秩矩阵时
(12)
(13)
与之对应的算法流程如图2所示。
3.2. 无重置操作时初始化
无重置操作时CNC初始化思想与2.1节类似,以获得
和
为目的,进而建立s和o之间的关联,使式6恒成立。仍假设
为满秩矩阵,那么
和
表达式为
(14)
(15)
式中
具体推导过程在此不再赘述,对应的算法流程图如图3所示,其中Vs由
非相关向量数确定。
3.3. 容量区域确定算法
从3.1节可知,矩阵
可以获得所有源节点的既定传输速率。如果本地编码内核无法达到该
传输速率时,信息将会丢失,使得从接收序列o中成功恢复发送序列g的概率降低,具体原因如下。
对于任意源点
,矩阵
中存在
个线性独立的列向量
,那么
为当前编码内核条件下汇点r的可达速率,任意源点s能够在向量集合
对应的链路上发送非零序列
,其它链路上发送零序列,即
此时式(6)可简化为
(16)
为
个线性独立向量构成的矩阵,
为除零之外的输入序列。由3.1节可知,式(16)当且仅当
为满秩矩阵时有解。换言之,汇点r可达传输速率为
时,能够从输出序列o中恢复发送序列g。
同时,由可达速率定义可知,任意源点
以速率
发送零值序列,方可确保汇点r能够从接收序列o中恢复发送符号g,则式(16)可解。由于
可解析,那么
包含
中的
个线性独立的列向量。综上对任意给定网络和汇点r,式6表征的输入输出序列之间的关系可写为
(17)
根据式(17)可确定源点s的容量区域。
4. 仿真分析
4.1. 参数设置
算法测试基于Linux进行,包括硬件、软件和算法参数三部分。硬件为算法的测试提供存储和计算功能;软件提供仿真测试平台,包括系统、网络仿真器(Network Simulator, NS)、图形处理软件、内置协议等,协议采用按需距离向量路由(Ad hoc On-demand Distance Vector, AODV)协议;模型参数确保算法顺利运行,其中本地/全局编码内核参照文献 [20] 设定。主要参数设置如表1所示。
Table 1. Parameter set in simulation
表1. 仿真参数设置
4.2. 性能参数
算法性能包括时延、吞吐量、丢包率、控制开销等指标 [21] 。对于有环CNC网络而言,时延(Delay)可侧面反映算法效率问题,主要包括处理时延和传播时延,前者由NC编码译码产生,后者由网络环路导致,其值由trace文件往返时间统计值Dt的1/2确定,在此用归一化值表征,即统计时延平均值与最大时延Dmax比值;吞吐量(Throughput)反映了网络容量的改进程度,其值为单位时间内传输的分组数目Pt;丢包率(Loss)为无量纲参数,反映节点传输速率阈值,与容量区域密切相关,其值为未成功接收分组Pl与总发送分组Ps的比值;开销(Overhead)为有效数据分组以外的其它控制分组及复制分组数目,其值为网络总分组数Pn与实际有效分组Pv的差值。各参数表达式分别为
4.3. 仿真结果
在此对算法增加前(记为改进前)、增加后(记为改进后)与理想(记为理论值)性能分别进行对比分析,结果如图4~7所示。
从图4中不难看出,总体而言,改进前后算法时延均高于理想值,且平稳状态(t > 5 s)改进后时延比改进前低约37%。具体而言,改进前、改进后时延变化趋势略有差别,前者先递增后平稳,后者递减至平稳状态。原因在于:一是初始状态无论是否有数据传输,网络需要等待全局编码内核和本地编码内核启动,产生了高时延;二是节点在初始化过程中,排队和传输时延保持不变的情况下,处理时延略有增加,归一化时延也提高;三是引入CNC后,随着网络容量的提升,传输的实际分组数目减少,碰撞概率降低,时延也随之降低;四是引入了译码算法,避免了有环网络的环路时延,降低了网络时延。
从图5中可以看出,吞吐量随着时间的增加,呈现先递增、后稳定的趋势,而且平稳时间内改进后的吞吐量比改进前高约3.2 Mbps。原因在于:CNC初始阶段更多数据用于处理全局和本地编码内核,实际分组成功传输量较少,而改进前协议在控制分组交互完成后即转发数据分组,因此网络运行初始阶段CNC吞吐量低于改进前。当网络状态趋于稳定后,CNC网络以较少的资源传输更多的分组直至稳定,而改进前网络随着时间增加,参与节点数递增,分组碰撞重传概率增加,并逐步趋于稳定值,因而吞吐量平稳值低于CNC对应值。
从图6中可以看出,网络运行初始阶段,改进后网络丢包率高于改进前,网络平稳后,改进后丢包率比改进前低约25%。原因在于:初始阶段CNC能够正常传输的为本地和全局编码内核,该时期内传输的所有数据分组基本上均被丢弃,前期网络丢包率较高,而传统网络发现路由即转发传输,受通信链路失效性的影响,存在部分分组丢弃的情况,但整体低于CNC网络。随着时间的推移,CNC网络和传统网络均趋于稳定状态,改进前后丢包率也会趋于稳定。CNC由于各数据分组基于内核函数作相关运算,链路负载降低,分组碰撞概率也随之降低,而改进前网络通过路由协议重传机制确保分组成功传输,分组碰撞概率高于CNC,与之对应的网络丢包率相对较高。
从图7中可以看出,改进后控制开销比改进前低约0.9 M bit,原因在于:CNC传输的为编码分组,而改进前传输的为转发分组,编码分组数量明显低于转发分组,其原因与时延、吞吐量、丢包率等原因一致,在此不作赘述。
5. 结论
论文在分析现有CNC译码机制的基础上,指出存在的容量区域确值和汇点初始化问题,并区分节点是否具有重置/清零功能,差异化提出相应的初始化算法。为防止汇点分组溢出,设计了容量区域参数确值算法,并对归一化时延、吞吐量、丢包率和控制开销等性能参数进行仿真测试。但算法仍存在以下不足:一是初始化算法和容量确值算法均假设生成矩阵为满秩,而实际中存在非满秩情形;二是各分组传输时延为一个时间单元,避免了同步开销,未考虑传输速率增加或降低时的情形。后期将针对上述不足作进一步细化研究。
基金项目
重大专项(XX2020F00003-XXX)、省部级课题(20191A010001)、大学基础理论课题(2021043、202121)。
NOTES
*通讯作者。