一种基于子集约束的协议首部纠错算法

王晓梅 范 亮 陈 彦 洪先强



一种基于子集约束的协议首部纠错算法

王晓梅①范 亮*①陈 彦①洪先强①

(解放军信息工程大学信息系统工程学院 郑州 450002)

针对无线网络数据的协议首部容易出错问题，该文在研究基于循环冗余校验的协议首部纠错算法的基础上，提出一种基于子集约束的纠错算法。该算法利用接收比特的置信度信息以接收向量为中心构建约束子集，从而缩小运算搜索范围，克服此前算法运算复杂度高的缺陷。随后，结合无线信号类型与信道模型，对算法的测试长度参数的取值范围进行了理论分析和实验验证。仿真结果表明，对于不同信噪比的无线信号，该算法可通过改变测试长度来调节约束子集大小，实现在保证较好性能条件下有效地降低运算开销，具有较强的实际应用价值。

无线通信；无线多媒体；协议首部纠错；校验字段

1 引言

随着人们对方便、快捷、相对自由的无线通信越来越热衷，无线技术也因此取得飞速发展。但无线通信始终处于开放环境容易受到各类干扰，传输误比特率相对较高[1]，因而一直制约了它的应用。针对这一问题，文献[2,3]提出在反馈重传机制下通过接收端对接收数据进行处理实现对含错的分组数据恢复，减少重传次数来提高接收效率。然而，对于一些实时要求高或只能单向通信的特殊场合反馈重传机制无法应用。于是一些学者们另辟蹊径对网络协议的冗余展开研究，提出了针对协议首部纠错的容错接收算法，利用冗余提高系统的容错能力。

针对无线通信协议中控制字段的取值存在着冗余特点，文献[4]提出了在高斯信道背景下基于似然概率的协议首部纠错算法(Robust Header Recovery, RHR)，在一定程度上实现了对无线协议首部的纠错。无独有偶，文献[5,6]出于同样的想法，并考虑到无线终端的运行成本，给出了在二进制对称信道条件下基于最小距离的协议首部纠错方法(Min DIStance header recovery, Min DIS)。该方法用比特向量的二元域运算代替了RHR算法中的概率运算，具有较强的可实现性，但也造成了纠错性能的损失。但上述两种算法只是研究了字段自身的冗余，并没有涉及字段间所存在的冗余。文献[79]对协议中校验字段携带的冗余信息进行了探索，提出了联合循环冗余校验的协议首部纠错算法(Robust Cyclic Redundancy Check header recovery, Robust CRC)，通过字段间的冗余信息提高纠错性能。该算法的缺点是运算复杂度随校验长度成指数式的增长，纠错性能也会随着校验长度的增加而下降。而实际通信协议中校验字段的校验范围往往较长，该算法的实现和应用是一个难题。尽管借助维特比格型译码形式的计算方法可降低运算复杂度，但复杂度依旧较高，同时也引入存储空间开销大的问题。

而且文献[1,4-9]中提到为了最大限度地保留接收信号的有用信息，所有处理过程都应该以软信息的形式输入输出，如此则会进一步增加纠错算法的运算成本，限制了其实用性。为此，本文借鉴Chase译码算法[10,11]的思想，在Robust CRC纠错算法基础上提出了一种约束子集的协议首部纠错算法(Bit- Flip subset constraint CRC, BF-CRC)。该算法借助每比特的置信度信息对接收信号进行预先处理, 建立一个以接收向量为中心的约束子集，通过调整约束子集的大小来维持较好的纠错性能，最终实现算法的搜索范围地缩小，有效地降低算法的运算复杂度，解决了Robust CRC算法无法实用的问题。

2 子集约束的协议首部纠错算法

2.1 基于校验关系协议首部纠错算法概述

网络协议字段依据其在通信过程中不同特性可分为[8]：(1)固定字段：实现通信控制、帧同步等功能的取值固定的字段。(2)可推测字段：根据前后时刻传输的分片数据或上下层关系可推测出取值的字段。因为字段和字段在纠错时都认为是已知的，所以后续叙述中统一描述为字段。(3)未知字段：在数据传输过程中对与通信链接起到重要作用的字段，其取值空间的大小可以根据协议内的约束关系进行有效的压缩。鉴于其对通信的重要作用，协议首部纠错实质就是对该部分进行恢复。(4)不关心字段：该字段的取值无法在当前协议层中解析，或者其取值对通信的影响不大；(5)校验字段：在通信协议中起到差错控制作用的字段，该部分完全属于通信时额外引入的冗余信息。当发送数据为，对应的接收数据为时，根据最大后验概率准则可知，未知字段的最佳估计为

将上述式(2)代入式(1)，则估计算子可以转化为

为此，文献[8]借鉴线性分组码的格型译码[12]思想展开了相应的研究。设CRC校验函数为，字段和字段分别取值分别为和，其他字段置为0所构成的向量经过运算后的校验值记为。依据校验函数分解的特性有式(5)成立。

式(7)可借用格型图以逐比特迭代的方式实现计算[8]，于是计算复杂度降为。此方法为基于校验的纠错算法的实现提供一个解决思路，但却存在着数量级的存储开销的问题。如果校验字段长度较长，上述算法的计算复杂度和空间复杂度也会非常高，例如对于实际的校验字段为4 Byte的情形则需要个double类型的存储单元(大约为16 GByte)来存储校验状态概率，这样的实现压力对于当前无线终端设备仍旧是无法承担的。

2.2子集约束的协议首部纠错算法

根据高斯信道具无记忆性，且式(3)等号右侧的后半部分的条件概率只与错误图样有关。因此将式(3)可变换为

图1 对于发送为o接收数据为yo时，受到不同程度噪声干扰所对应情形

根据子集约束的方法可将式(9)近似为

因测试长度通常取值较小，所对应的需遍历的范围也会较小，于是算法的运算复杂度下降为，小于Robust CRC算法的，而且该算法不需要同时存储所有校验状态取值的概率所以存储的需求也较低，保证了算法的可实现性。最后，将式(10)代入式(4)中可得到对于未知字段的估计。

表1各算法理论上运算消耗

接下来以不关心字段为5 bit，测试向量长度为2 bit的情形为例子进行说明。设在接收向量的各个比特对应的置信度(即为接收信号的测量信息[10])分别为｛1.2, 0.2, -0.1, 0.9, -0.8｝，且时，表2给出了对应的约束子集中各个向量的具体取值。最后，将的各个取值代入到式(11)中，实现对未知字段的估计。

表2子集空间计算示意表格

表2子集空间计算示意表格

测试向量当时，中所对应的具体向量的取值 1.20.2-0.10.9-0.8 e0=0011010 e1=0111110 e2=1110110 e3=1010010

由例子可得，子集约束的方法可以将原来大小为25的取值空间的求和降为大小为22的子集求和。倘若上述例子中的校验字段长度为2 bit，那么MAP, Robust CRC以及BF-CRC 3种算法的各自的运算消耗分别为：,,。由此可知BF-CRC算法中因所需运算操作得到减少，极大的降低了运算复杂度，提高算法可实现性与实用性。

2.3 子集约束算法性能与相关参数的关系

根据2.2节的分析可知，子集约束算法的性能受信道信噪比估计和参数大小的影响。至于无线通信系统的信噪比估计问题一直以来都是备受大家关注的问题，当前也已经取得许多重要成果。文献[15]对当前较为经典的信噪比估计算法进行了归纳总结，比较分析了各自的优缺点，随后文献[16]则提出了一种新型的基于相关向量机的信噪比估计算法，该方法具有估计范围大、估计精度高的特点。

图2 BPSK信号的概率分布图

3 算法仿真与分析

仿真1 本文通过设定一种协议格式并作为实验对象来验证BF-CRC算法的有效性，以Matlab 2010b为实验平台进行仿真，最后将其性能与Robust CRC算法和Min DIS算法进行比较。设定协议中包括8 bits的固定字段, 8 bit的未知字段, 30 bit的不关心字段以及利用CRC8的校验字段。设物理层传输的信号形式为DBPSK，并能提供置信度最低的个比特的对应位置。虽然Robust CRC算法提到利用的软信息进行纠错，但考虑到计算量等实际问题则实验中依旧采取硬判决信息进行处理与分析。在测试向量长度取不同值条件下，实验结果如图3所示。

军工产品质量管理系统建设以质量策划为基本环节，只有高度重视该环节，做好质量策划工作，才能更好地促进军工产品质量管理系统的有效运行。军工企业应在了解行业竞争趋势的基础上结合自身实际与IS09000标准制定合理的管理方式来进行活动策划，在不断优化质量管理系统的同时提高质量管理系统质量。一方面，明确策划重点，即如何开展质量管理系统优化活动，在此基础上策划质量管理系统运行方案，建立符合现实需求的质量目标，通过相关有效对策来进行质量评估；另一方面，以质量管理系统运行现状为依据信息策划，尤其要针对运行过程中国存在的不确定因素与诸多变更作出预防，最大限度地确保质量管理系统与军工产品要求相符合。

图3 不同测试长度下BF-CRC与其他算法的性能对比

在信道信噪比在3~8 dB范围内BF-CRC和Robust CRC两个算法的纠错性能都比Min DIS算法好，这是由于校验字段中其实携有较多的有用信息。由前面分析可知如果算法在信噪比4.8 dB时取得较好果则理应满足条件，由的曲线可验证2.3节的分析的正确性。

仿真2 为了进一步说明BF-CRC算法的在具体情形中的实用性，本文设置具体的实验场景如下：无线接入点(Access Point, AP)发送的数据，经过加性高斯白噪声信道(或慢衰落瑞利信道)，最后在用户端(User)接收。相对加性高斯白噪声信道而言，在慢衰落瑞利信道条件下应用BF-CRC算法时需要增加考虑相位差异以及衰落因子等对置信度度量造成的影响[17,18]。根据文献[4]中提到的协议压缩技术可知，在该场景下WIFI的802.11 MAC和IP协议可以进行如下冗余分析[19]，如图4所示。后续部分将详细解析无线终端同时开启多个下载业务的情形时，网络协议中的冗余：

图4 WIFI的802.11MAC和IP协议格式

(1)对已经建立链接的下行数据，MAC协议层中帧控制字段(Frame Control)、目的MAC地址(MAC Addr1), AP的MAC地址(MAC Addr2)、源MAC地址(MAC Addr3)、序号控制(Seq)等字段都可以根据通信的前后数据帧以及下层协议推测得到。

(2)在IP协议层中，实际应用时发现版本号(Version)、服务类型(Service)、分片(Frag)和片偏移(Offset)等字段取值在通用的情形下是固定的，属于字段。数据长度(TotalLen)字段其取值则可通过下层协议传输的服务数据单元长度得到，属于可推测字段。设下载业务都是使用相同的应用协议，因此可认为协议类型字段(Type)为已知。对于IP分组中的目的IP地址是在其接入网络时就已分配，也属于字段。

(3)其他一些字段取值虽不固定，例如标识字段(ID)、生存周期(TTL)和校验和(Checksum)，但不会影响到整个链接以及传输的正确性，因此定义为不关心字段(根据校验的特性可知Checksum中其实也具有冗余信息，限于时间本文在此暂不予讨论)。

综上所述，对网络中数据首部纠错最终归结为对源IP地址的容错估计。在同时进行多个下载业务时，接收数据的源IP地址具有标识数据流的作用，因此根据CRC校验字段(FCS)对源端IP地址进行纠错具有十分重要的意义。

为了简便，特对802.11的无线WIFI信号进行简化，忽略扩频、信道编码等技术，并设信号的类型为DBPSK信号。在具体协议中，CRC校验字段(FCS)长度为4 Byte，因此正如前面举例提到的如果直接采用Robust CRC算法，则需要个double类型的存储单元(大约为16 GByte)来存储校验状态概率，如此的存储开销是难以承受的。因此文献[8]中提出次优的Robust CRC算法(sub-Robust CRC)，将FCS字段分成4个8 bit的被认为独立的校验字段，此时存储需求降为个double类型的存储单元(大约4 kByte)，再利用CRC校验关系进行纠错。本部分主要将BF-CRC算法与可实现的sub-Robust CRC算法和Min DIS算法等进行性能对比。以Microsoft Visual Studio 2008为平台进行仿真实验。

由实验结果图5和图6可知，当测试向量长度较短时，BF-CRC算法的性能需要在高信噪比的情况下才具有效果；当测试长度相应的增加时，如取6 bit, BF-CRC算法纠错性能明显改善，对于加性高斯白噪声信道下在信噪比为7 dB时其协首部出错概率约为而sub-Robust CRC算法的约为；对于慢衰落瑞利信道下信噪比20 dB时其协议首部出错率约为明显优于sub-Robust CRC算法的。由前面描述知sub-Robust CRC算法中将 FCS字段分解为4个8 bit近似独立的校验字段，如此便破坏了校验字段内部的约束关系造成性能的极大损失。因此当信噪比较高时，BF-CRC算法纠错效果明显，且性能显著优于sub- Robust CRC算法。

图5 在AWGN信道下不同的纠错算法的性能对比

图6 在Rayleigh信道下不同的纠错算法的性能对比

4 结束语

本文在提出了一种利用置信度信息的子集约束纠错算法(BF-CRC)，该算法利用每个比特的置信度信息构建以接收向量为中心的约束子集，降低计算联合后验概率时需遍历空间的大小，通过理论分析和实验验证得到BF-CRC算法具有算法复杂度低的特点。本文最后分别对抽象协议和802.11的无线MAC协议进行了仿真实验，仿真结果表明BF-CRC可通过调节测试长度保证较好的纠错性能，减少运算开销，增强系统可实现性，提高无线通信网络的抗噪声性能。值得注意的是BF-CRC仅仅只是利用了置信度信息来锁定不确定的比特的位置，倘若在计算似然概率时采用软信息的形式，其纠错性能将会进一步得到提高。再者，虽然本文只是重点讨论了利用CRC校验进行首部纠错，而其他协议层也有类似的校验关系，例如IP层的Checksum校验，因此对利用这类校验信息进行相应地纠错处理本文仍旧能给出有较好的借鉴效果。

参考文献

[1] Woo G R, Kheradpour P, Shen D,.. Beyond the bits: cooperative packet recovery using physical layer information

[C]. Proceedings of the ACM Internet Conference on Mobile Computing and Network, Quebec,Canada, 2007: 147-158.

[2] Aman M N, Sikdar B, and Chan W K. Efficient packet recovery in wireless networks[C]. Proceedings of the Wireless Communications and Networking Conference (WCNC), Istanbul, Turkey, 2014: 1791-1796.

[3] Wang S S, Sheu S T, Lee Y H,. CPR: a CRC-based packet recovery mechanism for wireless networks[C].Proceedings of the Wireless Communications and Networking Conference (WCNC), Shanghai, China, 2013: 321-326.

[4] Duhamel P and Kiffer M.Joint Source-channel Decoding: a Cross-layer Perspective with Applications in Video Broadcasting[M]. UK, Academic Press, 2009: 193-246.

[5] 施里涛, 李欧, 王晓梅, 等. 一种高能效的无线传感器网络自主容错机制[J]. 电路与系统学报, 2013, 18(2): 102-107.

Shi L T, Li O, Wang X M,. An active fault-tolerant scheme with high energy efficiency in wireless sensor networks[J]., 2013, 18(2): 102-107.

[6] Schmid F, Orlear D, and Wehrle K. A heuristic header error recovery scheme for RTP[C]. Proceedings of the Wireless On-demand Network Systems and Services (WONS), Alberta, Canada, 2013: 186-190.

[7] Kiffer M and Duhamel P. Joint protocol and channel decoding: an overview[C].Proceedings of the Future Network Mobile Summit, Florence, Italy, 2010: 1-16.

[8] Marin C, Leprovost Y, and Kiffer M. Robust MAC-lite and soft header recovery for packetized multimedia transmission [J]., 2010, 58(3): 775-782.

[9] Meriaux F and Kiffer M. Robust IP and UDP-lite header recovery for packetized multimedia transmission[C]. Proceedings of the International Conference on Acoustics, Speech and Signal Processing(ICASSP), Texas, USA, 2010: 2358-2361.

[10] Chase D. Class of algorithms for decoding block codes with channel measurement information[J]., 1972, 18(1): 170-181.

[11] 党小宇, 陶静, 虞湘宾, 等. 一种低复杂度的Turbo乘积码自适应Chase译码算法[J]. 电子与信息学报, 2014, 36(3): 739-743.

Dang X Y, Tao J, Yu X B,. A low-complexity adaptive chase decoding algorithm for turbo product code[J].&,2014, 36(3): 739-743.

[12] Wolf J K. Efficient maximum likelihood decoding of linear block codes using a trellis[J]., 1978, 24(1): 76-80.

[13] Esmaeili M, Alampour A, and Gulliver T A. Decoding binary linear block codes[J]., 2013, 61(6): 2138-2144.

[14] Argon C and McLaughlin S W. An efficient chase decoder for turbo product codes[J]., 2004, 52(6): 896-898.

[15] 张金成, 彭华, 赵国庆. 信噪比估计算法研究[J]. 信息工程大学学报, 2011, 12(5): 535-542.

Zhang J C, Peng H and Zhao G Q. Research on SNR estimation algorithm[J]., 2011, 12(5): 535-542.

[16] 韩博, 吴杰, 许华, 等. 基于相关向量机的信噪比估计算法[J]. 通信学报, 2013, 34(4): 201-206.

Han B, Wu J, Xu H,. New SNR estimation algorithm based on relevance vector machine[J]., 2013, 34(4): 201-206.

[17] 冯战, 郑海昕, 秦铭晨. AWGN 与 Rayleigh 信道下TPC性能仿真研究[J]. 无线电工程, 2013, 43(9): 7-9.

Feng Z, Zheng H X, and Qin M C. Performance simulation and research on turbo product codes over AWGN and Rayleigh channels[J]., 2013, 43(9): 7-9.

[18] 郑贺, 陆佩忠, 胡捍英. 基于二分图的乘积码迭代译码算法[J]. 电子与信息学报. 2006, 28(1): 86-90.

Zheng H, Lu P Z, and Hu H Y. Iterative decoding algorithm for product codes based on bipartite graphs[J].&, 2006, 28(1): 86-90.

[19] IEEE Std 802.11-2007. Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications[S]. 2007.

Header Recovery Algorithm Based on Subset Constraint

Wang Xiao-mei①Fan Liang①Chen Yan①Hong Xian-qiang①

(,,450002,)

For the protocol headers of wireless network data prone to errors, this paper puts forward with a bit-flip subset restriction header recovery algorithm after studying the one based on Cyclic Redundancy Check (CRC). A constraint subset of the received vector centric is set up to narrow the search space by exploiting the confidence information of each bit, overcoming the defect of high complexity of the former header recovery algorithm. Then, the theatrical analysis and experimental verification about the value range of the test vector’s length are done combining the models of wireless signal and wireless channel. The simulation results show that this method can maintain the well performance with a low computing cost, adjusting the test vector’s length towards wireless signals with different Signal to Noise Ratio (SNR).

Wireless communication; Wireless multimedia; Protocol header recovery; Verifying fields

TP393.0

A

1009-5896(2015)08-2014-07

10.11999/JEIT141574

范亮 fanlya6@163.com

2014-12-10收到，2015-04-07改回，2015-06-08网络优先出版

国家安全重大基础研究(6131482013)资助课题

王晓梅： 女，1976年生，博士，讲师，研究方向为无线自组织网络和网络数据协同处理.

范 亮： 男，1989年生，硕士生，研究方向为网络数据协同处理.

陈 彦： 男，1990年生，硕士生，研究方向为网络数据协同处理.