随机网络编码

随机网络编码（共6篇）

随机网络编码 篇1

0 引言

网络编码技术[1,2]是由路由传输技术扩展而来的, 就路由传输技术来说, 中间节点只负责复制和转发接收到的信息, 而对于网络编码技术而言, 中间节点不仅具有直接复制和转发信息的功能, 还可以对接收到的信息进行编码后再进行转发。

采用网络编码技术实现数据传输的关键是构造网络编码方案。随机网络编码构造算法[3]由于事先不需要获知网络的全局拓扑知识, 也不需要事先确定节点各链路的编码向量, 从而具有较好的可扩展性和可实施性, 备受人们青睐。

在对网络编码进行教学与科研的过程中, 常常需要有实验环节或仿真计算, 可以采用自编模拟程序的方式[4], 但这种方式需要编制大量的程序, 同时存在不直观、不利于对实验结果进行分析和比较的缺点;文献[5]提出了一种基于Window套接字编程的网络编码仿真实现方法, 但只涉及最简单的有限域的异或运算, 也只能适应于最简单的“蝴蝶网络”;还有一些学者选择NS和OPNET等仿真软件来实现[6], 但这些软件的优势在于对高层协议的支持, 而要实现网络编码数据传输的模拟, 必须对其进行扩展, 由于这些软件使用起来较为复杂, 扩展具有一定的难度;此外, 还可以采用硬件的方法构造实验平台[7,8], 但必须采用特殊的硬件, 实现起来较麻烦。本文提出了一种简便的随机网络编码数据传输的仿真实现方法, 它不需要特定的软、硬件支持, 在一般的实验室内就可以实现, 同时又不同于软件仿真, 具有一定的直观性。在局域网内选取相互连接的若干终端来模拟网络节点, 以套接字 (IP地址+端口号) 代表节点间的有向链路, 采用UDP数据传输来模拟有向链路的数据流动, 从而实现了对单源组播网络的模拟。在节点上运用Java编程[9]实现了有限域的算术运算, 根据网络编码数据传输策略, 各节点采用Java套接字编程方法实现数据的接收与发送, 中间节点调用有限域的算术运算方法对输出信道进行编码, 形成了编码数据包, 宿点接收数据包, 调用有限域的算术运算方法, 对接收的数据进行解码而恢复出源点播出的信息。采用Java编程实现各部分的功能, 形成了一个完整的软件系统, 各节点只需要依次运行该系统并输入相关的信息便可以工作, 各节点的相互作用便实现随机网络编码的数据传输。仿真结果表明提出的方法是有效的, 且该方法具有软硬件要求低、操作方便的特点, 并易于掌握和实现。提出的方法适用于在一般的单源组播网络上实现随机网络编码的数据传输仿真, 为网络编码的实验环节与仿真计算提供了有效的方法。

1 随机网络编码数据传输策略

一个单源组播网络可以用一个有向无环图表示, 其中有一个源点、若干宿点以及若干中间节点, 节点间存在有向链路, 为了描述方便, 各链路的容量均为1个单位, 称之为信道。源点产生数据, 各节点采用网络编码技术进行数据传输, 宿点接收信息后通过解码恢复出源点产生的信息。

对于一个节点v, 记In (v) 为输入信道集, Out (v) 为输出信道集。

在一个单源组播网络上采用随机网络编码方法实现数据传输, 设源点至宿点集的组播容量为C, 选定正整数n (n≤C) 作为组播率, 则在每一代 (或称每一轮) , 源点产生n个数据包, 记为 (X1, X2, …, Xn) , 每一个数据包对应一个全局编码向量。

源点产生的数据包对应的全局编码向量是一个n维向量, 每一个分量是有限域F上的一个字符, 记第i个数据包对应的全局编码向量为Vi, Vi为单位向量, 它除了第i个分量为1外, 其余分量全为0。

一般来说, 对于源点或中间节点, 设其接收到 (若为中间节点) 或产生 (若为源点) 的数据包为Y1, Y2, …, Yp, 当节点为源点时, 则p=n, 当节点为中间节点v时, p=|In (v) |。各个数据包对应的全局编码向量为 (T1, T2, …, Tp) , 每个全局编码向量也是n维的。若该节点需要传输信息至m (m=|Out (v) |) 条输出信道, 则对于第i (1≤i≤m) 条输出信道, 节点在有限域F上分别随机产生p个随机数 (xi, 1, xi, 2, ..., xi, p) , 分别与 (Y1, Y2, …, Yp) 相对应。节点为第i条输出信道进行编码, 产生输出数据包为。

节点向第i条输出信道发送全局编码向量TOi和数据包Zi, 记为TOi||Zi。

对于宿点, 至少需要从n条输入信道中接收数据包和相应的全局编码向量, 利用全局编码向量和数据包构成一个n维线性方程组, 采用高斯消元法求解线性方程组就可以恢复出源点播出的数据包 (X1, X2, …, Xn) 。

2 有限域的算术运算

网络编码操作在有限域上, 在编码过程中, 涉及到有限域字符之间的加、乘运算, 在解码过程中, 涉及到有限域字符之间的加、减 (有限域的字符的相减运算与相加运算一致) 、乘、除运算, 因此, 在实现随机网络编码数据传输过程, 节点必须能实现有限域的算术运算[10]。

选定有限域的阶和相应的本源多项式, 本文选定有限域为GF (28) , 相应的本原多项式为x8+x4+x3+x+1, 从而本文中有限域中的字符为8位二进制数, 可以用一个字节 (byte) 表示。根据有限域的运算规则, 两个字符的算术运算的结果仍为8位二进制数。运用Java编程构造一个类, 记为GF.class, 类中以静态方法给出了有限域GF (28) 中两个字符的加、乘、除运算, 三个主要方法如下:

节点在进行编码或解码时, 如要实现有限域的运算, 只需把GF.class类包含进来, 同时在需要实现相应运算的地方调用该类中相应的静态方法即可。

3 随机网络编码数据传输技术的仿真实现

本文以一个典型的单源组播网络为例 (如图1所示) 来说明如何在实验室构造随机网络编码数据传输的仿真实现模型, 只要根据单源组播网络拓扑的节点和链路情况对模型的参数进行修改, 构造出的模型也适合一般的单源组播网络。

3.1 单源组播网络的仿真

在图1所示的单源组播网络中, 节点S是数据源点, 节点1、节点2、节点3、节点4、节点5均为中间节点, 节点T1和T2为宿点, 源点产生信息经过网络编码后由输出信道传输至网络, 中间结点把接收到信息进行网络编码后再由其输出信道进行转发, 宿点通过输入信道接收数据包后, 由各输入信道的全局编码向量和数据包的内容构造线性方程组, 通过求解线性方程组恢复出源点产生的信息。

为了对图1的网络拓扑进行模拟, 在局域网内选择8个网络终端, 它们同处在一个C类地址 (172.16.101) 的网段内, 各网络终端采用集线器或交换机相连接, 其IP地址的分配如图2所示。

用网络终端来代表单源组播网络的节点, 用网络套接字 (IP地址+端口号) 来代表节点间的有向信道, 采用UDP数据通信来表示有向信道上的数据传输, 并运用Java套接字编程来实现。由图1可以看出, 源点S至宿点集的组播容量为3, 因此选定整数3为组播率, 源点每一代产生3个数据包, 相当于源点分别从3条虚拟单位信道中接收到3个数据包。

有向信道与套接字的对应关系如图3所示。在图3中, 单源组播网络的每一条有向信道对应一个套接字, 例如:源点至节点1的单位有向信道与套接字 (172.16.101.11:10011) 对应, 从而源点向节点1传输数据相当于源点向该套接字发送一个UDP数据包;同理, 节点2至节点5的有向信道与套接字 (172.16.101.15:1022) 对应, 节点2向节点5发送数据相当于节点2向该套接字发送一个UDP数据包。因此, 采用套接字来模拟有向信道, 就可以在局域网内实现对图1的单源组播网络的仿真。

3.2 源点S的工作流程

源点需要确定每代产生的数据包个数n, 也称之为组播率;同时需要确定输出信道数, 每一个输出数据包对应一条输出信道, 而每一条输出信道与一个套接字相联系, 因此需要确定每个输出数据包送往的IP地址和端口号。当以上工作完成后, 把每代传输的数据等成n等分, 每一等分构成一个输入数据包, 本文中采用人工的办法, 为每一个数据包输入等长的数据内容。然后为每一个输出数据包产生一个局部编码向量, 并求出全局编码向量和编码后的数据包, 再通过Java套接字编程把编码后的数据包传输至指定的套接字。

源点的工作主要包括以下5个部分内容:

(1) 键入组播率和输出信道数;

(2) 键入输出信道对应的套接字;

(3) 输入每一代要传输的数据;

(4) 为每一输出信道运用随机网络编码方法生成数据编码并生成相应的全局网络编码向量, 形成数据包;

(5) 根据给定的套接字发送UDP数据包。

运行我们开发的系统, 源点的运行界面如图4和图5所示, 通过图4的界面, 可以输入源点的组播率 (输入信道数) , 源点的输出信道数以及各输出信道对应的套接字;通过图5的界面输入每一代发送的数据包内容, 在本例中, 源点每一代发送3个数据包, 3个数据包应等长。

3.3 中间节点的工作流程

中间节点分别从上游节点接收数据, 然后分别转发至下游节点, 根据网络拓扑确定输入信道数, 以及每一输入信道对应的端口号;还需要确定输出信道数, 以及每输出信道对应的套接字。例如, 对于节点5来说, 其输入信道数为4, 对应的端口号分别为10021, 10022, 10023, 10024。而输出信道数为2, 对应的套接字分别为 (172.16.101.10033) 和 (172.16.101.17:10041) 。

中间节点的工作流程如下:

(1) 键入输入信道数以及各信道对应的端口号;

(2) 键入输出信道数及各信道对应的套接字;

(3) 从各输入信道对应的端口中接收数据包;

(4) 根据接收到的数据包, 采用随机网络编码方法为每一输出信道产生输出数据包;

(5) 根据给定的套接字发送UDP数据包。

中间节点的运行界面如图6所示, 通过这一界面, 可以输入中间节点的输入信道数以及每条输入信道对应的套接字, 由于每条输入信道的IP地址均为本机地址, 故只需输入相应的端口号;通过这一界面, 还需键入输出信道数以及每条输出信道对应的套接字。图6是节点5的运行界面, 从中可以看出, 节点的输入信道有4条, 对应的端口号分别为:10021、10022、10023、10024;而输出信道有2条, 对应的套接字为: (172.16.101.16:10033) 、 (172.16.101.17:10041) 。

3.4 宿点的工作流程

宿点需要从输入信道接收数据, 然后进行解码运算, 再恢复出源点播出的信息, 宿点的工作过程如下:

(1) 键入输入信道数以及各信道对应的端口号;

(2) 从各输入信道对应的端口中接收数据包;

(3) 根据接收到的数据包, 析出每一数据包的全局编码向量, 形成一个n维线性方程组, 通过高斯消元法, 求解该线性方程组, 恢复出源点播出的信息。

宿点的运行界面如图7和图8所示, 其中通过图7的界面输入宿点的输入信道的信息, 而图8的界面显示宿点恢复出源点产生的信息。

3.5 程序的执行

当上述各节的程序录入后, 则必须按一定的顺序运行各节点的程序, 即按T1, T2, 5, 4, 3, 2, 1, S的顺序启动程序运行, 当节点S的程序运行后, 每一代输入三个数据包的数据内容, 见图5, 然后点击“发送数据”按钮, 于是宿点T1和T2收到源点S播出的信息, 见图8。

4 结论

在实验室内构造出了一个随机网络编码数据传输的仿真实现模型, 在局域网内选择若干相互连接的网络终端代表网络节点, 以套接字代表节点间的有向信道, 以UDP数据通信表示有向信道的数据传输, 从而对单源组播网络进行了仿真, 采用Java编程实现了有限域的算术运算, 根据随机网络编码数据传输的算法分别编写源点、中间节点、宿点的编码和解码程序, 形成了一个完整的软件系统, 每一节点运行该系统并输入相应的信息, 各节点相互作用便可以实现随机线性网络编码的数据传输。

本文给出了一个实例, 仿真结果表明了方法的有效性, 只要根据单源组播网络的链路情况修改本模型的参数, 模型可以应用于一般的单源组播网络, 给出的方法具有软硬件要求低、操作方便的特点, 并易于掌握和实现。提出的方法为网络编码的实验环节与仿真计算提供了有效的方法。

参考文献

[1]陶少国, 黄佳庆, 杨宗凯等.网络编码研究综述[J].小型微型计算机系统, 2008, 29 (4) :583-592.

[2]范宇.基于RS码的网络编码层设计[J].软件, 2013, 34 (5) :92-95.

[3]Ho T, Medard M, Koetter R, et al.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory, 2006, 52 (10) :4413-4430.

[4]蒲保兴, 王伟平.线性网络编码运算代价的估算与分析[J].通信学报, 2011, 32 (5) :47-55.

[5]沈明, 蒲保兴, 唐彬.基于Windows套接字编程的网络编码仿真实现[J].软件, 2012, 33[2]:11-14.

[6]李令雄, 洪江守, 龙冬阳.NS仿真器的一个网络编码扩展[J].计算机科学, 2009, 36 (7) :71-73.

[7]Gibb G, Lockwood J, Naous J et al.Net FPGA-an open platform for teaching how to build gigabit-rate network switches and routers[J].IEEE Transactions on Education, 2008, 51 (3) :364–369.

[8]张明龙, 李挥, 李亦宁等.基于网络编码多信源组播通信系统[J].电子产品世界, 2011.3:23-25.

[9]梁宏涛.基于Java的设备故障诊断系统的设计与应用[J].软件, 2013, 34 (7) :5-6.

[10]Pu Baoxing, Chen Jiye.Implementation of arithmetic operation of finite field GF (2n) [C].Proceedings 2013 International Conference on Mechatronic Sciences, Electric Engineering and Computer (MEC) , 2013:1710-1714.

随机网络编码 篇2

Ad hoc网络是一种分布式的多跳网络系统, 该网络中不需要中心节点, 具有自组织、自愈的能力。当前Ad hoc多播协议主要有两大类型:基于树形拓扑 (tree) 的协议 (比如MADOV) 和基于网格拓扑 (mesh) 的协议 (比如ODMRP) 。学术界普遍认为基于网格的多播协议性能更好[1], 因此对于ODMRP协议的研究具有重要意义。

1、ODMRP协议路由机制

ODMRP (On-Demand Multicast Routing Protocol) 是一种按照信源的需求建立并维护组成员和多跳路由的基于mesh的路由协议。它包括路由请求阶段和应答阶段。它使用了转发组的概念来建立多播路由, 并通过"软状态"的方法来维护多播组的成员, 节点要脱离多播组时不需要明确的控制报文。

当信源需要路由时, 先广播一个Join Query包。当一个节点收到了一个Join Query包后, 把该包的源地址和ID加入自己的消息缓冲区 (Message Cache) 用来鉴别是否已收到过该包。若没有收到过则将包加入消息缓冲并重新广播该包。当加入请求包到达多播接收节点时, 接收节点产生一个Join Reply包并广播给其邻节点。节点收到Join Reply包后, 检查自己是否是包的下一跳。若是, 则节点把自己置转发组成员, 产生新的Join Reply包并广播。每个转发组成员产生并发送自己的加入应答包直到到达信源节点。这样从信源到接收者的路径就建立起来了。

2、基于随即网络编码的ODMRP协议

ODMRP协议能够提供较好的性能, 但它在建立多播组时采用洪泛的方式, 极大地浪费了带宽和增加了路由的控制开销。因此, 逼着对ODMRP协议进行了改进, 提出了基于网络编码的ODMRP协议———NC-ODMRP (Network Coding–ODMRP) , 有效地降低了网络通信的开销。

2.1 随机网络编码概述

通过研究人们发现在多播网络中, 通常采用的的把多播信息看做是一个仅仅能被路由和复制的“流体”的做法并不是最优的, 可以通过网络编码的方法对传统多播进行改进, 极大地节约带宽, 提高网络流量。中继节点从输入链路获得信息, 对接收到的符合编码条件的多个信息进行编码得到一个编码后的信息, 再把经过编码后的信息发送到输出链路[2], 这样既可有效地节约了网络带宽, 增大网络吞吐量。之后Ho, Medard等人提出了随机网络编码[3], 它的提出将网络编码拓展到了无线网络并不再局限于确定的网络拓扑结构。

2.2 随机网络编码算法

线性网络编码能够有效地构造编码向量, 确保信宿节点成功译码, 但它使用的是集中式算法需对整个网络的拓扑结构有全面的了解。因此线性网络编码算法对并不适用于拓扑结构动态变化或规模较大的网络。随机网络编码算法较好的解决了这个问题, 这种算法采用随机选择编码向量的策略:对于除了信宿节点外的所有中间节点, 只要在一个足够大的有限域Fq上随机选择它们输入链路到输出链路的映射, 而且各节点映射关系的选取是相互独立的, 就能以较高概率使各个信宿节点对应的系统转移矩阵Mt满秩, 即各信宿节点能以较高的概率成功译码。设G= (V, E) 表示无环有向图, 其中V是顶点集, E=V x V是边集且各边均为单位容量。S∈V为信源节点 (发送节点) , T∈V为信宿节点集 (接收节点集) , 网络的最大流为h。信源节点将原始信息分成h个向量x1, …xh, 中继节点进行编码操作:y=g1x1+g2x2+…+ghxh, g= (g1, …, gh) 是全局编码向量, 初值为h维单位向量, 是和编码后的信息向量y一起传输, 记为 (g, y) 。中继节点随机的在有限域GF (q) 生成h维局部编码向量对收到的h个 (g, y) 进行线性编码, 得到一个编码后的 (g, y) , 再发送给邻节点。当信宿节点收到h个线性无关的 (g, y) 后, 则根据高斯消元法即可解码。由此可见是否能够解码取决于在有限域GF (q) 上随机选取的局部编码向量必须线性无关。理论上可证明:当符号域大小为q=216时, 任何接收节点均可以至少以概率99.6%成功译码[3], 文献[4]指出, 在实际应用环境中, 符号域的大小为q=28就足够了, 这极大的降低了网络节点译码的开销。

2.3 NC-ODMRP协议

NC-ODMRP协议的基本思想即通过对ODMRP协议的JoinQuery和Join Reply包进行扩展, 实现在ODMRP协议建立路由阶段, 采用网络编码算法来代替简单的洪泛, 从而减少带宽的浪费、降低协议开销的目的。并且无需改变ODMRP协议的流程, 仅在节点处理报文时采用线性随机网络编码算法, 加入编码解码步骤即可实现。NC-ODMRP协议的报文格式如下:

Type:NC-ODMRP协议报文的类型, 分别为NC-ODMRP的Join Query和Join Reply报文。

Offset:包头的大小。

Prevhop:上一跳节点地址。

Daddr:目的节点地址, 即多播组地址。

NoP:参与编码的报文数量计数。

Vector:随机编码向量, 未编码报文该项为空。

Packet ID list:报文中参加编码的报文标识 (Packet ID) 列表。

ODMRP:NC-ODMRP封装的原ODMRP报文。

3、结束语

Ad hoc的研究和应用是当前学术界的热点。ad hoc路由协议在建立路由时普遍采用洪泛的方式, 这样极大地占用了网络带宽, 增加了路由的控制开销, 浪费了ad hoc节点有限的能量。网络编码算法的出现为解决这一问题提供了较好的方法。本文针对ODMRP协议的缺点进行了改进, 将ODMRP和网络编码结合起来, 提出了NC-ODM-RP协议, 可有效地降低路由时节点的转发次数, 从而减少带宽的占用和路由控制开销, 降低了节点能量的消耗, 对ad hoc路由协议的研究进行了一次有益的尝试。

参考文献

[1]Thomas Kunz and Ed Cheng.On-demand multicastingin ad-hoc networks:comparing AODV and ODMRP.Pro-ceedings of 22nd International Conference on DistributedComputing Systems, 2002:453-454

[2]Taku Noguchi, Takahiro Matsuda, Miki Yamamoto.Performance Evaluation of New Multicast Architecture withNetwork Coding[A].IEICE Trans.comm[C], 2003, E86–B (06) :1788-1795.

[3]Ho T, Medard M, Shi J.On Randomized NetworkCoding[A].Proceedings of 41st Annual Allerton Conferenceon Communication Control and Computing[C], 2003, Pages:442-445.

随机网络编码 篇3

1.1 定义

随机网络编码理论源自于信息论的线性编码理论,它能得到如今这样的重视和发展要得益于R.Ahlswede和N.Cai等人所做出的富有原创性的研究工作[1]。以前的编码理论都是用于物理层的比特编码,但是当它用于链路层和网络层时,产生了一些独有的特点和优势,而这些特点和优势在以前的网络理论和应用中是很难得到的。假设在一个多投网络中某一个节点的输入和输出数据包的关系如图1所示:

输出数据包和输入数据包满足线性关系:

b=[b1,b2,b3]T=undefinedSi ai (1)

Si是对应输入数据包ai的块码,T表示矩阵的转置,b1,b2和b3为组成输出数据包b的各个比特分量。由这个基本的关系式可以得到对于一个非循环的多投网络而言,某一个端点接收的数据包yi与发送的数据包xi之间的关系满足:

yi=S xi (2)

因此,若能从接收的数据包yi恢复发送端的数据包xi ,要求从发送端到接收端的所有中间节点提供的编码矩阵S必须可逆。要满足这个条件要求编码矩阵S必须是非奇异矩阵,如果各个节点提供的编码矩阵是分布式且随机的,就能使编码矩阵S的各个行向量或者列向量相互独立,因而能满足S是非奇异矩阵这个条件。

局部编码核(Local encoding kernel)的定义。令F是一个有限域,ω是一个正整数。对每一个节点T和每一个信道e∈Out(T)(Out(T)表示输出节点的集合),在一个非循环网络中由ω维F个取值范围的网络码组成的局部编码映射可以表示成:

在一个非循环网络中由ω维F个取值范围的网络码组成的标量kd,e定义为局部编码核,d表示输入节点中的某一条信道d∈In(T),(In(T)表示输入节点的集合)。

全局编码核(global encoding kernel)的定义。全局编码核定义为一个ω维的列向量fe,即接收节点接收的一个数据包。它可以表示为:

fd表示发送节点的某一条信道发送的数据包,它组成向量空间Fw的基。这个定义也说明了全局编码核和局部编码核的关系。

1.2 独有的特点和优势

这里的特点和优势是与以前传统的以路由为基础的网络理论相比较而言。

1.2.1 提高了网络的通过量

假设有两个数据包都是以每秒B个比特的比特率到达某一个节点,对于输出链路的容量为每秒B个比特。通过网络编码,将这两个数据包同时加到这个节点的输入端来提高网络的通过量是可行的。例如,节点通过将这两个数据包逐个比特进行异或运算,来将这两个数据包在这个节点的输出的链路进行混合,如果这两个数据包在到达接收端时能够区分开,那么网络的通过量就增加了。因为在这个节点以后的各条链路中都是有两个数据包的流量在传输,而采用从前的以路由为基础的网络理论在某一条链路中最多同一时刻只有一个数据包在传输。

1.2.2 减少了每个比特的发送能量

除了上面介绍的优点外,随机网络编码还可以减少无线多投网络中发送每个数据包(或者每个比特)需要的能量。下面举例说明随机网络编码的这个优点。用下面的图2a和图2b将随机网络编码方案和路由方案进行了对比来说明随机网络编码方案节省发送能量的特点。这个优点对于无线网络尤其重要。这两个图是两个无线网络的拓扑结构图,s表示发送节点,r1和r2表示两个接收节点,假定在相邻的两个节点间发送一个数据包均需要1个单位的能量,由于在图2a中只采用路由方案,多投网络的发送点在s,所以将1个数据包发送到s点的相邻两个节点需要1个单位的能量,而这个数据包到达r1和r2两个接收点还得需要4个单位的能量,这样1个数据包从发送点s到达r1和r2两个接收点共需要5个单位的能量。而在图2b中采用了随机网络编码方案,编码节点位于r1和r2之间,从发送点s发送两个不同的数据包p1和p2,这两个数据包到达s点的两个相邻的节点需要2个单位的能量,到达r1和r2时,共需要6个单位的能量,这两个数据包到达r1和r2中间的节点时,又需要2个单位的能量,这两个数据包混合后再需要1个单位的能量才能将混合后的数据包返回r1和r2两个节点,这样采用随机网络编码后,两个不同的数据包共需要9个单位的能量将这两个数据包从发送节点发到两个接收节点,因此将1个数据包从发送节点s发到两个接收节点r1和r2需要4.5个单位的能量。因此采用随机网络编码后,发送数据包到同样的距离,所需要的发送能量要比采用路由方案低。采用随机网络编码方案后,发送每一个数据包需要的最小能量对应的编码系数可以通过多项式得到,而多投网络若采用路由方案,发送一个数据包需要的最小能量则难以计算,而且无法得到最小的发送能量。

1.2.3 网络传输延迟得到最小化

为了阐述这个优势,这里采用从网络中某个发送节点发送一个数据包到达某个接收节点所需要的最大跳跃级数来衡量。假设某个网络中共存在4个节点,这4个节点排列成空间四面体结构,如下图3a和3b所示。发送节点s位于四面体的最上方端点,四面体下方的三个端点均为接收节点。假设图中每一条边的容量均为单位容量,p1和p2表示各条边通过的数据包。很容易证明,采用这样的网络拓扑结构,网络的最小边割数是2。因此,根据Edmons定理,可以知道图中边不相连的有方向的扩展树的最大数目也是2。从图3a可以看出,承载数据包p2的实线扩展树的深度是3,即从发送节点s到达接收节点t2的最大跳跃级数是3跳,即最小延迟是3。而在采用随机网络编码方案后的图3b中,虚线边承载数据包p1,点划线的边承载数据包p2,实线的边承载数据包p1+p2。这样从发送节点s到达任何一个接收节点的最大跳跃级数只有2跳,最小延迟是2。

1.2.4 得到了网络编码增益

以前采用路由方案的网络,接收信号只能取得信源编码和信道编码带来的增益,而采用随机网络编码方案后,接收信号除了得到上面提到的两个增益后,还得到了网络编码带来的增益,因此接收信号的质量比只采用路由方案的网络更好。

1.2.5 提高了网络的鲁棒性和可靠性

由于采用了随机网络编码的网络,同一个数据包可在多条链路中同时传输,中间某条链路或者某几条链路出现故障不会引起信号传输的中断,这是以前的路由网络所不具备的。

1.2.6 提高了对网络数据的纠错能力

这种纠错能力取决于编码码字的长度,编码码字的长度越长,纠错能力就越强。

1.3 研究方向

随机网络编码的研究方向大致可以概括为:编码;性能分析;网络容量;网络成本;物理层实现方法;实用性;网络安全;网络拓扑结构;内容分配;应用等。

1.3.1 编码

编码的研究方向是寻找各种编码(包括最优码、卷积码、分布式擦除码、嵌套格码、群码、可变速率线性码等),降低编码的复杂度,分析编码增益,编码码字取值范围的紧界,编码方程的寻找,分布式编码的构建、编码优化、码字构建快速算法、信源码和网络码的分离等[2,3,4,5,6,7,8]。

1.3.2 性能分析

性能分析是就网络性能指标进行分析,它包括:最大通过量、通过量的提升、平均通过量、网络资源消耗、易管理性、鲁棒性、网络延迟、网络编码在Epidemic路由中的性能模型、ad-hoc网络的编码性能、排队模型和延迟分析、带缓冲的随机编码的Trellis连通性分析、饱和的空数据包对tandem类型的无线网络编码的影响、非循环网络的零误差编码的内界和外界以及信息流的分解等[9,10,11,12,13,14]。

1.3.3 网络容量

网络容量的分析实际上是要得到信息流速率的上界。这个上界可以是紧的,也可以是非紧的。分析时要结合具体的网络类型。从得到的资料来看,主要针对ad-hoc网[15]、无方向的由多个单投网组成的网络[16]、单个信源多个信宿的网络[17]、无线多投网络[18]和无线多跳网络[19]等进行容量研究。

1.3.4 网络成本

网络成本关系到所进行的网络研究是否具有实际意义。有的学者将它和距离熵联系起来,距离熵是最优成本的下界,通过研究距离熵来间接研究网络成本[20];可以通过联合控制功率和拥挤的方案来优化网络编码从而实现最低成本[21];也可以就单信源多投网络的最小成本进行探讨[22];可以就如何建立最小成本的多投连接进行研究[23];也可以将最小成本作为一个约束条件来研究多源多池网络编码的外界[24]。

1.3.5 物理层实现方法

这个研究方向是考虑将网络编码技术应用于无线通信网络的物理层,将无线信道的多径劣势转变成提升容量的优势[25]。要实现这样的想法需要解决节点间的同步等问题[26]。

1.3.6 实用性

将随机网络编码技术应用于实际需要考虑的问题较多,包括网络资源的自适应节约分配[27]、算法的复杂程度、软件的实现[28]和硬件的实现[29]等。

1.3.7 网络安全

由于随机网络编码技术鼓励多个数据包混合传输,它的理论基础是和以路由为基础的网络理论截然不同的,因而它所带来的安全问题有些也是以前的网络安全所不具有的。有些学者已经在这方面做了一些前期的工作,例如:Qiming Li 和Dah-Ming Chiu等人研究了如何利用网络编码实现文件的安全分发[30];而Ning Cai和R.W. Yeung提出了将网络编码和信息安全合并考虑的数学模型[31];J.L.Tan和M. Medard提出了将网络成本和网络安全综合加以考虑的方法[32]。

1.3.8 网络拓扑结构

随机网络编码的基本思想是要在未来的通信系统中支持大量的多投信息流,然而如何设计能够高效支持多投信息流的网络拓扑非常重要。因为以前的网络拓扑是支持点对点的单投网络,这样的拓扑结构不能直接用来高效设计多投网络的拓扑。K.K.Chi和S.Horiguchi 等人对能够支持多投网络的拓扑结构设计进行了专门的研究和探讨[33]。

1.3.9 内容分配

随机网络编码的研究还包括大量文件的分发上。研究证实,采用随机网络编码方案下载文件的时间比只在服务器采用编码的方案减少了20%到30%;而比没采用网络编码的方案下载文件的速度提高了2到3倍[34]。

1.3.10 应用

随机网络编码技术的应用如果按照网络的类型来分可分为在有线网络的应用和无线网络的应用。在无线网络的应用包括:在Ad hoc网络的应用;在蜂窝网络的应用;在MAC层的应用;在交叠网络的应用;在传感器网络的应用;在DTN(Delay Tolerant Networks)网络的应用。按照节点和终端在网络中的位置来分可分为在服务器/客户端网络的应用;在P2P网络的应用;在mesh网络的应用。

2 随机网络编码理论在无线通信网络中的应用

2.1 几种典型的无线网络应用

由于随机网络编码理论开始是以有线网络为研究对象,因此它的许多研究成果应用于有线网络较为简单,但是无线网络的信道特点比有线网络复杂得多,因而如果将随机网络编码理论应用于无线网络,有许多问题需要解决,而且很多问题极具挑战性,解决起来难度很大。

上面已经就随机网络编码理论在无线网络中的应用作了介绍,其中在Ad hoc网络、蜂窝网络、传感器网络、mesh网络和P2P网络的应用是比较典型的应用。

2.2 需要解决的关键问题及面临的挑战

由于随机网络编码理论在许多类型的无线网络中都有应用,而且对于不同的应用需要考虑的问题也不完全相同。因而这里讨论的问题是在许多无线网络中都必须面对的,是在无线网络应用中的共性问题。

数据包的标记问题。从前面图1可以看出,如果能够在节点正确实现随机网络编码,必须首先能够对来自不同链路的数据包加以区分。这个区分的过程就是对不同链路数据包的标记过程。这在有线网络中容易解决,因为不同的线路就对应不同的链路。但是,对于无线网络,由于它的广播特性,来自不同节点的数据包如果不进行标记,则在进行编码的节点无法区分来自不同链路的数据包。因此在无线网络每个节点的输出必须在输出的数据包的包头加上一个特征标记,以便让下面的节点能够知道接收的数据包来自这个节点。

节能问题。能量受限是许多无线网络的共性问题,尤其是对于传感器网络更是如此。因此对于以随机网络编码为基础的无线网络必须要研究能量高效使用算法。有些学者已经在这方面做了一些前期的探索性研究工作。

带宽问题。带宽受限是许多无线网络面临的又一个共性问题。因此必须对要传输的数据进行压缩。尽管随机网络编码本身已经具有数据压缩功能,但对许多应用而言还远远不够,因而需要研究在随机网络编码基础上的数据压缩方法。将随机网络编码和信源编码相结合将会成为一种解决问题的有效途径。

动态网络问题。在一个无线网络中,如果终端或者节点或者二者都可以移动,它所带来的问题要比一般的静态无线网络更复杂,需要解决的问题更多。其中一个很重要的问题是衰落,由于衰落的存在使得接收的数据出现错误。因此需要研究抗衰落的随机网络编码方法,这需要从随机网络编码的定义入手,有大量艰巨并且具有挑战性的基础工作要做。目前,在国际上还没有这方面的研究报道。

3 发展展望

随机网络编码理论是近些年刚刚出现的崭新的网络理论,是对信息论的丰富和发展。因为它有坚实的严密的理论作为基础,发展前景一定会越来越广阔,这是从前的以路由为基础的网络理论所无法比拟的。总的来看,今后的发展将会沿着两个大的方向进行:一个是基础理论方面;一个是在应用方面。在基础理论方面虽然已经作了很多卓有成效的工作,但是距离完备的理论体系的要求还相差很远,还有大量基础性的工作要做。在应用方面不断探讨新的应用领域和应用场合,为基础理论的实际应用创造条件,另外还可以反过来推动和促进基础理论的发展。如果将理论应用于实际还要研究和现有网络的兼容性问题。

4 结束语

随机网络编码 篇4

近年来,基于光学理论与方法的数据加密技术已愈加引起研究者的兴趣和关注,成为信息安全研究领域的热点[1,2,3,4,5]。由于光学技术具备二维成像与并行处理能力,光学加密方法被公认为是新一代信息安全理论与技术。该领域内的开拓性成果是1995年由Refregier和Javidi提出的双随机相位编码光学加密系统(Double Random Phase Encoding,DRPE)[6],该系统在光学4-f系统的输入面和频谱面各放置一块随机相位板,先后对原始图像的空间信息和频谱信息做随机扰乱,从而使系统的输出信息的复振幅为平稳随机的白噪声。DRPE被提出后,其安全特性及由其衍生出来的光学加密系统被广泛研究。例如,彭翔小组针对于该系统的安全性能问题进行了深入的分析,指出该系统对于已知明文攻击、唯密文攻击及选择性明文攻击的脆弱性[7,8,9],G.Unnikrishnan和Guohai Situ则分别将该方法推广到分数傅里叶域及菲涅尔域[10,11];Xianyu Su等将该方法应用于彩色图像、多幅图像加密及隐藏[12,13],L.Z.Cai等还将此技术与数字全息术结合起来对光学图像进行加密,取得了较好的效果[14]。这说明,作为光学信息加密的经典结构,双随机相位编码的光学加密系统具有巨大的研究空间和应用潜力。

本文中,我们对双随机相位编码系统中的空域随机相位板进行置换,而代之以随机振幅板,提出随机振幅-相位编码虚拟光学加密系统(Random Amplitude-Phase Encoding,RAPE)。首先研究了该系统的统计学性质,指出该系统同样可以将图像加密成平稳随机白噪声,从而理论上具有无限大的密钥空间,可以抵抗暴力攻击。并且,该系统对空域密钥的要求较双随机相位加密系统更低,因此空域密钥更加容易获取。此外,由于直接对图像的振幅进行编码,因此在频域密钥泄露的情况下攻击者依然不能获得原始图像信息,较双随机相位编码系统在加密图像数据时有更强的鲁棒性。

1 理论分析

随机振幅-相位编码光学加密系统利用标准4-f系统来实现,如图1所示。f(x,y)是被加密的图像,加密时,首先将输入信号f(x,y)在空域乘以随机振幅函数n(x,y),之后经过傅里叶变换,在频域被随机相位函数exp[i2πb(μ,ν)]滤波,再经傅里叶逆变换,在输出面上得到密文ψ(x,y),即加密结果。

在本系统中,对于空域振幅密钥n(x,y),要求其为数学期望为零的白噪声信号;对于频域相位密钥exp[i2πb(μ,ν)],要求b(μ,ν)为在[0,1]上均匀分布的白噪声。且空域密钥与频域密钥统计独立。后面的论述中将证实这些要求的必要性。整个加密过程可用公式表示为

其中:*表示卷积运算且h(x,y)被定义为

其中FT-1表示傅里叶逆变换。下面将证明,加密后的密文ψ(x,y)为平稳复随机白噪声,而且,使用单随机模板则不能实现这种效果。

首先考虑f(x,y)被n(x,y)调制后所得函数r(x,y)=f(x,y)n(x,y)的平稳性。容易看出,其均值为零。然后计算其自相关函数,有

因为已经要求n(x,y)为零均值的白噪声,根据白噪声的定义,有

其中δ表示二维冲击函数。因此式(3)可进一步化简为

式(5)说明f(x,y)被n(x,y)调制后所得函数并非平稳信号,并且等于被加密对象f(x,y)模的二次方与二维冲击函数的乘积,不具备加密的功能。因此需要引入第二个随机调制板,即频域内的随机相位板exp[i2πb(μ,ν)]。下面证明,在引入随机相位函数exp[i2πb(μ,ν)]后,系统的输出密文ψ(x,y)为平稳随机白噪声。根据式(1)和二维离散卷积的定义,可得

这里假设信号f(x,y),n(x,y)以及h(x,y)为大小为M×N的矩阵。为了研究二维随机过程ψ(x,y)的统计性质,计算ψ(x,y)的自相关函数。根据自相关函数的定义可知

因为n(x,y)和b(μ,ν)互相独立,同时考虑式(2),有

由于n(x,y)为均值为零的白噪声信号,在式(3)中已经得到

同时,也容易证明

根据二维离散傅里叶变换的定义,有

进而可以计算出来:

参照式(10),(11)将式(12)化简得到

综合式(7),式(8),式(9),式(13)可以得到:

式(14)意味着密文ψ(x,y)的自相关函数为二维冲击函数,表明其为平稳的二维随机白噪声。在这种情况下,作为密钥的随机振幅板及随机相位板分辨率很高,因而密钥空间很大,在不知道密钥信息的情况下,很难通过盲反卷积运算恢复图像,具有较高的安全性。关于平稳白噪声对于盲反卷积攻击以及暴力攻击的鲁棒性,文献[6]中给出了详细的论述。

解密方法是加密方法的逆过程。首先,对密文ψ(x,y)傅里叶变换后,在频谱平面上除以频域密钥exp[i2πb(μ,ν)],再经傅里叶逆变换并除以空域密钥n(x,y)调制,即可恢复出f(x,y)。

2 计算机模拟结果

为了验证所提方法的有效性,在PC机上使用MATLAB7.0进行了实验。用来进行加密的是一幅灰度图peppers(512×512×8 bit),在图2(a)中给出。用本文提出的随机振幅-相位编码虚拟光学系统进行加密,所采用的空域振幅密钥服从参数为(0,1)的高斯分布,频域相位密钥为均匀分布。图2(b),图2(c)是加密后图像的实部和虚部,可以看出,加密后的信号为白噪声信号,与原始图像无任何相关性,这证实了第1部分的理论分析。

下面证实该方法对暴力攻击的有效抵抗性。为了便于比较,采用相关系数(Correlation Coefficient,CC)来描述恢复出来的图像fr与原始图像之间f的符合程度。相关系数被定义为[15]

其中E表示求数学期望,这里省略了函数坐标。在对密码系统进行密码分析时,通常认为攻击者已经知晓密码算法的工作过程,即满足Kerekboffs假设[16]。图3(a)给出了在密文被截获的情况下,攻击者使用随机选取的错误的密钥得到的解密结果,此时相关系数cCC=0.004 7,可见这种解密结果与原始明文无任何相关性。图3(b)给出了使用正确密钥得到的解密结果,此时相关系数cCC=1.000 0,恢复出来的原始明文与真正的原始明文完全一致,同时证实了本方法的无损性。

3 几点讨论

3.1 系统对随机振幅板的要求

在Refregier和Javidi的文献中指出,用于加密的双随机相位板的相位分布应该是位于[0,2π]之间的均匀分布的二维白噪声矩阵[6],这个要求限制了随机相位板的可选择空间,使得攻击者清楚的知道密钥的统计特性,这对系统的安全性来说是一个潜在的威胁。而本文提出的随机振幅-相位加密系统,对于空域随机振幅板,只要求是期望为零的白噪声,对其概率密度函数没有要求,可以选择为高斯分布、均匀分布等等。这样会使得随机振幅板有充分的选择空间,从而会对攻击者破解系统造成极大的困难。在第2部分的模拟中使用的随机振幅板为满足高斯分布的零均值随机矩阵,在图4中给出了使用随机振幅板为均匀分布的零均值随机矩阵的加密结果。比较图4和图2可以看出,使用两种随机振幅板的加密效果相同,这进一步证实了上述分析。这种由于附加参数的多样性从而增加攻击困难的分析可参考文献[17],这是其对于双随机相位编码系统的优越性之一。

3.2 频域密钥泄露情况下系统鲁棒性讨论

对于双随机相位编码系统来说,其频域密钥一旦泄露,在加密的对象为实值图像的情况下,攻击者在不需要获取空域密钥的情况下可以获取完整的原始明文信息,这是其致命弱点之一。相比之下,由于本文提出的系统首先对原始图像的振幅进行调制,因此即使在频域密钥exp[i2πb(μ,ν)]泄露的情况下,攻击者依然不能获得原始明文信息。我们对此性质进行了计算机模拟,其结果在图5中给出。图5(a)是双随机相位加密系统频域密钥泄露情况下攻击者所获取的明文信息,此时相关系数cCC=1.000,可见其与原始明文完全一致,这显示了其对于部分密钥泄露攻击的脆弱性。图5(b)是随机振幅-相位编码系统频域密钥泄露情况下攻击者所获取的明文信息,此时相关系数cCC=0.007 7,这表明其与原始明文几乎没有相关性。这是本方法对于双随机相位编码系统的优点之二。

3.3 系统的物理实现问题

由于在系统的设计中假设随机振幅板为期望为零的白噪声,则振幅调制数值必然存在负数的情况,由于负幅度在物理上无法实现,因此该系统只能用计算机模拟的虚拟光学系统来实现,这是其局限性之一。

4 结论

本文提出了一种新的虚拟光学加密系统,即随机振幅-相位编码加密系统。使用统计学理论证实了该方法与双随机相位加密系统具有相同的加密效果,可以把实值图像或者复矩阵加密成平稳的复随机白噪声。其特点在于不知密钥的情况下,不能通过暴力攻击的方法破解系统。特别需要指出的是,该系统相比于双随机相位加密系统具备一些突出的优越性,即其对加密密钥的统计学要求更低,同时抵抗攻击的能力更强。其局限性是该系统只能用数字模拟的虚拟光学系统实现,不能够使用物理元件实现。

摘要：通过对双随机相位编码光学加密系统中空域的随机相位模板进行置换,提出采用随机振幅-相位模板对图像进行加密的新方法。理论分析表明,当随机振幅板为零均值白噪声且与频域相位板统计独立时,被加密图像的自相关函数为二维冲击函数,表明原始图像被加密为平稳的复随机白噪声,因而可以抵御盲反卷积攻击。采用计算机进行模拟,证实了所提方法的有效性。最后讨论了该方法相对于双随机相位编码系统的优越性:对空域密钥的统计学要求更低、在频域密钥泄露情况下系统鲁棒性更强。但是,由于物理上不存在幅度为负值的光波,因此该系统只能使用数字虚拟的方法来实现。

随机网络编码 篇5

我们期望能够通过数字指纹从合谋攻击中检测出至少一个非法用户。为了这个目的, 指纹编码必须配备一个跟踪算法。第一个提出C-安全码的Boneh和Shaw[1]。Tardos而后提出了一个以概率方式构造的编码长度渐近最优的C-安全随机码[2], 编码长度达到了理论最小值O (c2log (nε) ) 。并证明了这种算法是ε-安全并能抵抗c个共谋者。Tardos提出的基于嵌入假设的c-安全码具有高度的随机概率码字生成算法。其追踪算法是计算每个码字的相关性, 如果相关性值大于给定的阈值, 则认定该码字出自合谋者集合。在这之后, Hagiwara使用一个不同的概率分布代码生成tardos码[3], 提出了指纹长度较短的编码。Isogai关注于在Tardos码中的参数并重新评估以缩短它的代码长度[4]。Skoric等人构造了一种新的随机产生的指纹编码[5], 将二进制的Tardos码推广至任意进制, 是Tardos码的码长降低, 带来了性能上的提升。然而这些基于Tardos码的c-安全码都由于其计算成本高并且存储开销大, 使其不适用于实际。该文提出了一种基于Tardos编码和HHI06的2-安全随机指纹编码, 来减小编码的长度。并改进了Tardos码的追踪算法, Tardos编码能够根据谁超过了阈值判定非法用户;改进的算法能够根据谁的值最高而判断非法用户, 不用对比阈值。这种不同降低了非法用户逃脱的可能性 (完美犯罪) 。第二, 合作搜索, 例如如果有用户能够从他们的所获得的拷贝中伪造出一个非法拷贝, 得分最高的可疑用户并不会被指控为非法用户。这个附加的过程减少了无辜用户被错误指定的可能。另外, 拥有最高分的用户没有被指定, 然后继续追踪第二高得分者, 以此类推。这种重复结果在将来能够减少完美犯罪的可能性。

1 随机指纹编码

指纹嵌入算法:对于各个用户的指纹, 其嵌入方法是相同的, 而仅是嵌入的内容不同。设用户u的码字为au=au, 1, …, au, l∈F2l, c个用户u1, u2, …, uc合谋。如果在第i个比特处有au1, i=au2, i=…=auc, i, 则称比特i处为不可侦查位。如果上述等式中有一个等号不成立, 则称比特i处为可侦查位。另外, 假设存在一个“安全”的嵌入方法。 (参见文献[1]中提出的“嵌入假设”) 。

设合谋用户所伪造出的码字为ap, 则根据嵌入假设, ap满足ap, i∈{au1, i, au2, i, …, auc, i}, i=1, …, l。

每一个用户被分配一个长为m的随机二进制码字。随机产生用户编码wi, 概率Prob (wi, j=0) =概率Prob (wi, j=1) =1/2, 对于编码wi, j所有位置上的比特位j与用户i互不相关。码字的选择根据二进制编码统一的分布 (范围N×m) 。将这个码字wi= (wi, w1, ..., wi, m) 通过数字水印技术嵌入到载体当中, 发送给第i个使用者ui。有l个非法用户尝试从他们所获得的l份文件发现并修改嵌入的编码, 并制造出一份非法文件, 其中被嵌入修改过的y= (y1, ..., ym) 编码。在y中的二进制没有没有损坏和解码的情况下, 我们引入一个符号“?”并假设yj∈{0, 1, ?}, 1≤j≤m。系统将wi和y作为输入, 输出一个使用者名单, 通过追踪算法来确定一个非法文件。

定义以下追踪结果:

完美犯罪 (perfect crime) :输出结果没有非法用户;

虚假指控 (false-charge) :输出结果出现一些无辜用户;

追踪错误 (tracing error) :出现完美犯罪或虚假指控。

输出如果为空, 意为“没有足够证据”。如果一个追踪算法在提供的c个用户中检测出l个非法用户的错误的概率下界小于ε, 这个编码为合谋安全。关于非法用户攻击模型, 这里给出以下引理:

引理1:如果非法用户ui1, ..., uit在同一位置码字wi1, j=...=wit, j, 则第j位的码字也和它们相等 (yj=wi1, j) 。

引理2:非法用户制造的码字与无辜用户是使用的码字相比没有特定的信息。

假设1第一次出现是在[2]并在以后被接受。另外, 假设2认为如果所有用户的码字独立生成, 则非法用户的码字对于无辜用户的码字来说也是独立的。

2 追踪算法

原算法

1) y中所有bit位上的‘?’由‘0’代替。

2) 对于每个用户ui, 计算ui的得分Si:

即Si=m- (y和wi的汉明距离) 。

3) 选择拥有最高分的用户uh。如果有多个最高分用户, 随机选择其中的一个 (我们的安全性证明不决定于特殊的选择算法) 。

4) 如果PS (uh) 返回值为YES, 则输出用户uh并停止搜索。如果PS (uh) 返回值为NO, 则输出为空并停止搜索。

改进算法

1) y中所有bit位上的‘?’由‘0’代替。

2) 对于每个用户ui, 计算ui的得分Si:

3) 将所有用户得分降序排列, 为ui1, ui2, …, uin。如果有多个用户得分相同, 则他们的顺序可能是任意的 (作为基础代码, 我们的安全性证明不决定于特殊的排序方法) 。

4) 集合h←1。

5) 如果PS (uh) 返回值为YES, 则输出用户uh并停止搜索。如果PS (uh) 返回值为NO, 则h←h+1并重复这一步走直到h=N;并输出为空并停止搜索。

改进算法与原算法的不同之处在于, 当得分最高的用户没有被输出时, 算法在原算法中立即停止, 在改进算法中, 算法会继续进行并可能会输出其他的用户。因此, 改进的算法与原算法相比, 完美犯罪的可能性没有改变, 另一方面, 虚假指控的可能性也没有改变。

3 理论分析

在编码中, 如果只有一个非法用户ui (l=1) , 即标志假设意为y=wi, 当用户ui'≠ui且wi'=y时会出现追踪错误。根据假设2, y与每一个wi'不相关, 因此这种可能性的界限在1- (1- (1/2) m) N-1≤ (N-1) (1/2) m。则假设非法用户l=2

首先, 给定m和N, 引入以下公式:

然后我们有下面的定理:

定理1:对于任何满足引理1和引理2生成策略的非法用户编码, 完美犯罪的概率Ppc满足于

虚假指控的概率ppc满足于

另外, 表1中使用最短长度编码给出了完美犯罪和虚假指控的概率。表明了所设计的编码在编码长度较短时具有很高的安全性。

假定l=2。

引入以下公式:

定理2:对于任何满足假设1和假设2生成策略的非法用户编码, 追踪错误的概率Perr满足于

为了减少计算理论范围值的计算时间, 根据定义简单推导出以下内容:

考虑追踪错误的计算成本, 跟踪算法主要包括以下两个阶段:

1) 分值计算。通过粗略的估计, 最终大约需要Nm个操作。

2) 对于1≤h≤N, 对用户第h高分值进行合作搜索。将需要N个操作来选出第h个用户, 对于合作搜索需要Nm个操作, 因此对于每一个h最终需要Nm个操作。

因此最差计算复杂度为N2m, 最坏情况下我们需要N次合作搜索。

理论分析可知, 改进算法与原算法相比, 追踪错误的概率减小。

5 实验分析

1) 仿真程序

计算机仿真实验步骤如下:

1) 设置计数器counterc←0 (追踪错误计数器) ;

2) 对所有用户生成编码wi= (wi, 1, …, wi, m) (1≤i≤N) ;

3) 根据以下方法从w1和w2中生成非法用户编码yi= (y1, …, ym) ;使两个编码在每个位置都不同, 从两个编码中平均选择一点为y;

4) 运行算法;

5) 计数事件的数量如下:

●输出非法用户, 无操作

●输出无辜用户, 改变计数器为counterc←counterc+1

6) 重复上述步骤2-5次;

7) 计算追踪错误概率probc=counterc/T。

对于改进算法, 追踪错误与虚假指控和完美犯罪性质相同。因此, 追踪错误概率继承了追踪错误与虚假指控的属性。追踪错误概率应该低于完美犯罪概率而高于虚假指控概率。改进算法有助于完美犯罪概率的减小并且追踪错误的概率与虚假指控的概率基本相同。且对于减小完美犯罪概率的效率高于其对虚假指控概率的增加。综上所述, 我们所设计的编码方案效率更高。

结果显示我们的编码与NHKWOFI07、HHI06编码拥有相同错误概率的情况下, 编码长度更短。

6 结论

我们提出了一个拥有较短编码长度的2-安全指纹编码。通过理论分析及仿真实验评估了它的特性。从结果来看, 我们的编码出现追踪错误的概率非常小。在对更多非法用户进行追踪是下一步所要研究的方向。

参考文献

[1]Boneh D, Shaw J.Collusion-secure fingerprinting for digital data[J].IEEE Trans on Information Theory, 1998, 44 (5) :1897-1905.

[2]Tardos G.Optimal probabilistic fingerprint codes[C]//Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC) , 2003:116–125.

[3]Hagiwara M, Hanaoka G, Imai H.A Short Random Finger-printing Code Against a Small Number of Pirates[C]//ser.Lecture Notes inComputer Science.Fossorier M..Berlin, Germany:Springer-Verlag, 2006, 3857:193-202.

[4]Isogai T, MurataniH.Tardos's fingerprint code shortened by optimizing code generation probabilities and improving tracing algorithm[R].IEICE Technical Report, ISEC2007-85, 2007.

[5]Skoric B., Katzenbeisser S, Celik M.Symmetric tardos fingerprinting for arbitrary alphabet sizes[J].Designs, Codes and Cryptography, 2008, 46 (2) :137-166.

[6]王彦, 吕述望, 徐汉良.一种二进制数字指纹编码算法[J].软件学报, 2003, 14 (6) .

随机网络编码 篇6

齿轮箱作为一种具有结构紧凑、传动转矩大、传动效率高等诸多优点的动力传动装置,被广泛应用于交通运输、能源化工、起重机械等领域。然而,由于齿轮箱结构复杂、承受负载大、工作环境恶劣等原因,使得齿轮箱易于发生磨损、剥落、点蚀、裂纹等故障。但由于齿轮箱复杂的振动传递路径、强背景噪声以及多振动源激励的影响,使得振动信号信噪比小,故障特征被噪声淹没,增加了特征提取难度。因此,实现强背景噪声中齿轮振动特征的有效提取是齿轮故障检测的关键。

齿轮运行过程中,当损伤轮齿与正常轮齿啮合接触时,会使得轮齿滑动接触表面间的润滑油膜破裂,从而产生冲击,而在齿轮旋转运动下,冲击会按一定的时间间隔规律重复性出现,所以,振动信号中周期性或准周期性冲击成分的出现是齿轮局部损伤的一个关键征兆[1]。因此,选取适当方法将周期性瞬态冲击成分从被强噪声污染的齿轮振动信号中提取出来,对实现齿轮故障诊断具有重要意义。文献[2]针对齿轮局部故障产生的动态响应特点,将信号共振稀疏分解和包络解调相结合,实现了振动信号中瞬态冲击分量的有效识别;文献[3]将双树复小波和局部投影算法相结合,提取齿轮振动信号中的周期冲击分量,实现齿轮故障诊断。此外,局部均值分解[4]、最大相关峭度解卷[5]、局部特征尺度分解[6]等多种现代信号处理方法也被应用于齿轮故障诊断中,并取得了较好的效果。

随机共振是Benzi等[7]在解释地球古气象“冰川期”和“暖气候期”周期性变化规律时提出的。随机共振作为一种利用噪声增强微弱信号特征的处理方法,通过构建评价随机共振效果的测度函数,控制调整噪声或系统参数实现信号、噪声与系统三者间的最佳匹配,从而将噪声能量转移给目标信号,实现目标信号特征的增强提取,为微弱信号检测与特征提取提供了有效的解决途径[8,9,10,11]。虽然随机共振可以在一定程度上实现信号中冲击特征的有效提取[12,13],但对于信号中周期性冲击分量的检测效果不佳,其原因主要是:缺乏有效的随机共振测度函数对其检测效果进行有效合理的评价;峭度指标作为一种量纲一指标,可定量表征信号中的冲击成分,但对初期损伤敏感,对不同冲击幅值、多冲击分量特征的整体定量刻画效果不理想;互相关系数可定量地表征两个信号的相似性,但容易受到噪声的影响;此外随机共振系统参数的合理选取也缺乏有效的理论依据。因此,本文针对随机共振在周期性冲击分量检测中存在的问题,提出了基于自适应随机共振和稀疏编码收缩算法的齿轮故障诊断方法,利用相关峭度对信号中周期性冲击分量的良好评价能力,将其作为随机共振提取周期性冲击特征的测度函数,并借助遗传算法[14]实现系统参数的自适应优化选取,同时,为使得检测结果中的冲击特征更加突出,借助稀疏编码收缩算法的稀疏降噪能力,对随机共振检测结果作进一步消噪处理,从而提高故障识别精度。仿真和工程应用验证了本方法的有效性和实用性。

1 理论基础

1.1 随机共振

随机共振是随着非线性动力学和统计物理理论飞速发展而出现的一种利用噪声来增强微弱信号特征的信号处理方法,强调的是非线性系统、周期信号和噪声间的积极协同效应,它为微弱信号检测提供了有效的解决途径。

过阻尼双稳系统随机共振模型用非线性朗之万方程描述如下:

式中,x(t)为系统输出;s(t)为输入信号;n(t)为均值为0、方差为D的高斯白噪声;U(x)为双稳态势函数;a和b为双稳态势函数的系统参数,均为正实数。

令,可得到一个非稳态解x=0和两个稳态解。势垒高度为ΔU=U(0)-U(x±)=a2/(4b),势间距为

由式(1)可以看出,随机共振的系统输出实际上是布朗粒子在双稳势函数中的运动轨迹。当布朗粒子仅在周期信号作用下时,没有足够的能量跃迁势垒,只能在单势阱内移动;但在适量噪声协助下,布朗粒子可以逐渐积累能量,从而按照周期信号的振荡频率在两势阱间实现周期跃迁,达到“共振”状态,进而将布朗粒子在单势阱内的小范围移动放大为两势阱间的大范围跃迁,达到凸显周期信号特征的效果。因此,随机共振检测微弱信号的过程就是调整系统参数或噪声强度实现信号、噪声与非线性系统三者间最佳匹配的过程。

1.2 相关峭度

相关峭度是Geoff等在峭度指标的基础上,综合考虑冲击成分的周期性而提出的用于定量描述信号中周期冲击成分的评价指标[15]。该指标综合体现了相关系数和峭度指标的双重思想,既考虑了各周期内冲击成分间的相关性,又继承了峭度指标对冲击成分的敏感性。在利用随机共振提取信号中的周期性冲击特征时,既要考虑检测结果的整体效果,即周期冲击特征全部有效提取,又要凸显检测结果的个性特征,即各周期内冲击特征实现最大化提取。而相关峭度没有考虑各周期内信号峭度对整体检测结果的影响。所以,本文在相关峭度的基础上,引入了各周期内的信号峭度指标,并将完善后的相关峭度作为随机共振检测冲击信号的测度函数,依据测度函数最大化选取最优的系统参数,实现周期冲击特征的最佳提取。

设y(n)为均值为零、含有周期冲击成分的原始信号序列,引入各周期内信号峭度指标影响的相关峭度计算公式为

式中,T为冲击周期,单位为数据点数;N为原始信号长度;M为周期偏移数。

对于旋转机械中齿轮、轴承等关键部件的振动监测,由其局部损伤导致的冲击响应周期一般与相应轴的转频成倍数关系,因此,冲击周期T可由分析对象的转频信息和采样频率计算得到。此外,选取的冲击周期T与原始数据长度N不一定满足整数倍关系,因此,当原始数据长度N与选取的冲击周期T不满足整数倍关系时,则采用重采样技术对原始信号进行重采样处理,使得重采样后的数据长度与冲击周期T满足整数倍关系。对于周期偏移数M的确定,为了充分利用各周期内的冲击信息,本文选取

1.3 稀疏编码收缩

稀疏编码收缩算法是Hyvarinen[16]基于稀疏编码理论提出的一种利用数据统计特性从背景噪声中预估非高斯成分的消噪方法。该算法利用非高斯成分的稀疏概率密度函数,借助最大似然估计理论得到阈值收缩函数,从而对观测信号进行稀疏阈值降噪处理,凸显信号中的非高斯分量。在本文中,齿轮故障信号中的冲击分量是典型的非高斯成分,因此,采用该算法对随机共振检测结果做进一步处理,使得冲击特征更加明显,提高故障识别精度。

Hyvarinen[16]提出的非高斯成分的稀疏概率密度函数如下:

式中,x为原始信号,其统计特性表现出非高斯性质;d为原始信号x的标准差;α为控制概率密度函数稀疏性的参数,α取值越大,概率密度函数越稀疏,本文α取值在0.1~0.5之间[17]。

基于上述稀疏概率密度函数模型,利用最大似然估计方法给出稀疏阈值收缩函数,从而可以从观测信号y中估算得到原始信号x的估计值

式1中N,σ为观测信号中的噪声标准差,由公式估计得到;为观测信号y的平均值;d由公式估算得到;σy为观测信号y的标准差[18]。

当式(4)中的平方根为虚数时,取值为零。

2 算法流程

由随机共振原理可知,随机共振检测微弱信号的过程就是通过调整系统参数,使得随机共振测度指标实现最大化的过程。因此,随机共振系统参数调整规则和随机共振现象发生与否的判断标准是利用随机共振实现微弱特征提取的两大关键问题。而目前,随机共振控制参数的合理选取缺乏有效的理论依据,经验法或试验法选取具有一定的人为主观盲目性,因此本文利用遗传算法的多参数同步优化能力实现系统最优参数的自适应选取;同时,利用相关峭度可以定量评价信号中周期冲击成分的优良特性,将其作为随机共振检测冲击信号的测度指标,构造遗传算法的适应度函数,实现齿轮故障信号中冲击特征的自适应提取。同时,由于齿轮故障冲击成分通常具有非高斯性质,而噪声成分则呈现出高斯分布特性,稀疏编码收缩算法可实现高斯信号和非高斯信号的有效分离,因此利用该算法对随机共振的检测结果做进一步消噪处理,凸显信号中的冲击特征。综上所述,本文提出的基于自适应随机共振和稀疏编码收缩算法的齿轮故障诊断方法可以有效实现齿轮冲击故障特征的增强提取,提高诊断精度。该算法的流程如图1所示,具体实现如下:

(1)相关峭度参数设置和数据预处理。根据被测对象的转频等信息选取相关峭度计算公式中冲击周期T和周期偏移数M的初始值,若原始数据长度与冲击周期T不满足整数倍关系,则需对原始信号按照T的整数倍关系进行重采样处理。

(2)遗传算法参数初始化。设置初始种群数量、随机共振系统参数a和b的搜索范围、最大迭代次数、迭代精度等,并利用相关峭度构造遗传算法适应度函数,基于适应度函数的最大化实现系统参数的优化选取。

(3)变尺度随机共振处理。根据信号特征设置变尺度压缩率,将原始信号输入到变尺度随机共振系统[13],利用遗传算法实现系统参数的最优选取,并利用得到的最优参数重构共振系统,从而进一步得到随机共振的最佳检测结果。

(4)稀疏编码收缩处理。利用稀疏编码收缩算法对随机共振的检测结果作进一步的降噪处理,凸显信号中的冲击特征。

(5)故障诊断。依据齿轮故障信号的最终处理结果实现齿轮故障的有效识别和诊断。

3 应用实例

3.1 试验台齿轮裂纹故障检测

齿轮箱作为旋转机械的常用传动装置,长期在低速、重载等恶劣环境中运行,难以避免发生各种损伤或故障。齿轮裂纹作为齿轮箱常见的早期故障之一,具有危害大、隐蔽性强、检测识别难等特点。而且,随着裂纹的逐渐扩展,若未能及时发现,则会导致后续一系列从属故障的发生,成为很多重大事故的潜在诱因。因此,利用齿轮裂纹故障的信号响应特征,实现齿轮裂纹故障的有效检测具有重要意义。

利用齿轮箱故障模拟试验台进行齿轮裂纹故障试验,齿轮箱采用一级传动,其中主动轮齿数为55,从动轮齿数为75。在从动轮齿轮齿根处用线切割加工裂纹,宽度为0.1mm,深度为2mm,如图2所示。用安装在齿轮箱顶盖上的振动加速度传感器采集振动信号,采样频率为12 800Hz,输入转速为780r/min,计算得到从动轮转速为572r/min,数据长度为6144点。

图3a给出了原始信号的时域波形,可以看出波形较为杂乱,没有明显的与齿轮故障特征相符的特征信息;而在图3b所示的频谱图中,频率成分复杂,也没有出现相应的有价值的频率特征信息。对该信号采用本文所提方法进行处理,选取相关峭度的计算参数:周期T由从动齿轮转频和采样频率计算得到,即T=1343;原始数据长度6144与冲击周期1343不满足整数倍关系,重采样处理后数据长度为5372点,采样频率变为11191.67Hz,从而周期偏移数M=3;遗传算法初始参数中的初始种群数量为50,系统参数a和b的搜索范围为[0.1,30],最大迭代次数为25,迭代精度为10-8等;变尺度压缩率R=700;得到的最终处理结果如图3c所示。从图3c中可以清晰地看到一组以近似0.106s为周期的冲击序列,冲击间隔与从动轮/故障齿轮的转频9.533Hz相符。诊断结果验证了所提方法的有效性。

此外,还给出了两组对比分析结果,图4a所示为随机共振方法以峭度指标作为评价函数得到的最优检测结果,图4b所示为以加权峭度指标[12]作为评价函数得到的随机共振处理结果,其中算法参数除随机共振测度函数不同外,其余参数设置与前文相同。由图4a、图4b可以看出,二者均未能有效提取出原始信号中的周期冲击特征。可见,本文所提方法借助随机共振的噪声利用特性和稀疏编码收缩算法可以实现齿轮故障冲击特征的增强提取。

3.2 机车走行部齿轮箱故障诊断

铁路运输作为国民经济的大动脉,正朝着高速方向发展,从而对机车的安全性、可靠性等提出了越来越高的要求。而电力机车作为一种重要的铁路运输工具,其安全可靠性运行是铁路运输的重要保障。齿轮箱作为电力机车的重要动力传递装置,工作环境恶劣,容易发生齿轮的胶合、磨损、裂纹甚至断齿等损伤,严重影响机车的正常运行。为保证机车的行车安全,缩短故障维修时间,实现齿轮早期故障的识别与诊断具有重要意义和实用价值。同时,由于机车运行环境复杂,所采集到的振动信号的信噪比往往很小,大量随机噪声掩盖了齿轮故障特征信息。因此,引入本文所提出的方法分析电力机车走行部齿轮箱振动信号,实现齿轮故障的有效诊断。

某型号机车走行部齿轮箱为一级斜齿轮减速传动,齿轮齿数分别为20和87,机车运行速度为63km/h,车轮直径为1.25m,计算得到大齿轮的转频为4.47Hz,小齿轮的转频为19.44Hz,齿轮啮合频率为388.9Hz。采样频率为12 800Hz,数据点数为13 500点。图5a所示为齿轮箱振动信号时域波形,可以看出,原始信号中含有不太明显的冲击成分,但由于背景噪声的影响,故障征兆不明显。而在其频谱图(图5b)中,频率成分较为复杂,有用信息也被噪声淹没,未能发现与齿轮故障相关的频率特征信息。采用本文所提方法对该信号进行处理,选取相关峭度的计算参数如下:周期T=2864,重采样后数据长度为14 320点,采样频率变为13 577Hz,周期偏移数M=4;遗传算法初始参数与前文相同,变尺度压缩率R=400,处理结果如图5c所示。从图5c中可以发现,信号中出现了明显的一组等间隔冲击序列,冲击周期近似为0.22s,与大齿轮的旋转频率4.47Hz相符,说明在大齿轮的某个齿上存在局部损伤。

图6所示为随机共振方法结合峭度指标和加权峭度指标得到的检测结果。由图6a和图6b可以看出,除了较为明显的前两个强冲击特征被提取出来,其余的弱冲击特征依然被噪声淹没,未能有效识别。因此,依据图6的处理结果难以给出明确的诊断结论。在之后的检修中发现机车走行部齿轮箱大齿轮某一齿的齿根存在裂纹损伤,与本文所提方法分析结果相符,验证了本文方法的有效性和优越性。大齿轮齿根裂纹故障图片见图7。

4 结语

本文针对随机共振在周期性冲击分量检测中存在的问题和不足,提出了基于自适应随机共振和稀疏编码收缩算法的齿轮箱故障诊断方法。该方法选用相关峭度作为随机共振检测周期性冲击分量的测度函数,并采用遗传算法优选随机共振系统参数,实现齿轮故障冲击特征的自适应随机共振检测;在此基础上,利用稀疏编码收缩算法对信号中非高斯分量的稀疏降噪能力,对随机共振检测结果做进一步降噪处理,凸显冲击特征,提高齿轮故障诊断精度。试验和工程实例结果表明,该方法对齿轮故障振动信号中的周期性冲击成分具有良好的提取效果,从而为齿轮故障诊断提供了一种有效解决途径。

摘要：针对强背景噪声下齿轮故障冲击特征提取问题,提出了一种基于自适应随机共振和稀疏编码收缩算法的齿轮故障诊断方法。该方法选用相关峭度作为随机共振检测周期性冲击分量的测度函数,借助遗传算法实现信号中周期性冲击特征的自适应提取;在此基础上,利用稀疏编码收缩算法对随机共振检测结果做进一步降噪处理,从而凸显冲击特征,提高故障识别精度。试验和工程实例分析结果表明,该方法可实现齿轮故障冲击特征的增强提取,为齿轮故障诊断提供依据。