一种利用最佳路径搜索的PDU容错定界算法

范 亮,王晓梅,杨东煜

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

一种利用最佳路径搜索的PDU容错定界算法

范 亮,王晓梅,杨东煜

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

针对在无线网络中因高误比特率而使协议数据单元定界易出错的问题,提出一种基于最佳路径搜索的协议数据单元容错定界算法.通过针对两类与协议数据单元定界相关的协议冗余的分析,在提出粗定界算法的基础上,将协议数据单元定界问题转化为路径搜索问题,给出了一种基于最佳路径搜索的协议数据单元容错定界算法.以无线异步传输模式网络中AAL5/IP网络协议为例进行仿真分析,仿真结果表明,该算法能有效降低协议数据单元的定界错误率,能克服常规定界方法对差错敏感的缺陷,具有良好的容错定界能力.

无线网络;协议数据单元;定界;路径搜索;容错

无线通信技术以其方便、快捷的优点在人们的日常生活中扮演着越来越重要的角色,但较高的信道误比特率特性却也广受诟病.针对这一问题,当前普遍采用基于通信双方协作的反馈重传机制(Auto Repeat reQuest,ARQ)来实现网络数据的差错控制.如,文献[1-4]提出将网络数据分解为若干个数据块,通过少量数据块的重传来提高传输的可靠性.ARQ机制具有控制和实现相对简单等优点,但是面对流媒体等实时性要求严格的业务和无线数字视频广播(Digital Video Broadcasting,DVB)等单向广播业务时,却难以有效应用.

针对上述问题,学者们从接收用户的角度出发,提出了针对差错数据的前向容错处理的解决思路.文献[5-8]通过对视频和语音等业务中信源数据的冗余分析,采用纠错和错误隐藏等技术实现了对差错业务数据的利用.另一方面,文献[9-12]讨论了当前网络协议所携带的冗余,提出了面向差错的无线网络数据容错接收方法.上述研究成果分别有效解决了差错数据在底层协议接收和上层协议应用中所面临的困难.然而,各协议层间严格的访问机制却使差错数据难以在协议层间有效传输,因而极大制约了差错数据的利用.

其中,协议数据单元(Protocol Data Unit,PDU)的定界问题尤为突出,因此,文中旨在探索对差错具有较好鲁棒性的容错定界方法.当前协议中采用的定界机制主要包括以下几种:字节计数法、字符填充的首尾定界符法、比特填充的首尾标识法和违法编码法[13].例如,在网络间互联协议(Internet Protocol,IP)中通过IP数据包首部的长度字段来实现整个分组的定界;在高级数据链路控制(High-level Data Link Control,HDLC)协议和点对点协议(Point to Point Protocol,PPP)中则通过特殊字符(0x7E)来标识数据帧的开始与结束.但在接收数据含错的条件下,传统定界机制变得不可靠,无法正确还原出相应的PDU,造成接收数据不可用.为此,笔者提出了一种基于路径搜索的PDU容错定界算法.通过对无线网络数据的协议格式的分析,给出了基于固定字段相似匹配的PDU粗定界算法.为克服在相似匹配时因载荷数据引入的“虚警”概率,在此方法的基础上进一步将PDU定界问题转换为路径搜索问题,提出了基于最优路径搜索的容错定界算法[14],提高了面向差错数据的PDU容错定界正确率.

1　协议数据定界问题

为实现资源复用和方便数据交换,无线网络数据通常以特定的形式进行封装,再通过协议接口递交给指定的协议层,形成相应的数据流,再由相应的通信链路进行传输.例如,数据链路层会将多路访问控制(Multiple Access Control,MAC)的协议数据单元转化为比特数据流;在异步传输模式(Asynchronous Transfer Mode,ATM)网络中,ATM适配层(ATM Adaptation Layer,AAL)协议数据单元则被转换为信元数据流.多个PDU进行传输则会经历如下过程:发送端将每个PDU按照特定的传输单位进行封装(分片),形成对应的数据集;为每个数据集设置用以区分的定界标识,将各个数据集依次聚合到特定通信链路上形成数据流;经信道传输后,接收端依据链路标识完成传输数据流的接收与重组;通过对数据流中PDU的定界,提取相应数据单元递交给上层协议.图1为无线网络PDU的传输示意图.

图1　无线网络PDU的传输示意图

根据上面的描述可知,PDU的定界对整个数据的正确传输具有重要作用.在通信资源有限的无线通信条件下接收的数据往往含错,因此,研究面向差错数据流的PDU的容错定界方法具有重要意义.

2　协议单元容错定界算法

2.1协议单元中协议字段的分类基于PDU定界的考虑,各协议字段可按照其功能归纳为如图2所示的几种类型,每个字段对应为一组比特向量:固定字段K,该字段在PDU中的偏移位置固定,并且具有固定取值;长度字段L,该字段直接或者间接指示了PDU的大小,其能涵盖多个协议层中指示数据长度的字段;数据字段D,该字段对PDU的定界不具有明显作用,包括协议首部中部分控制字段以及载荷数据;填充字段P,该字段用以调整PDU的大小,使其能够满足特定格式规范,通常为可选内容.

图2　协议数据单元中协议字段的分类

根据上述分析可知,字段K、字段L和字段P都在一定程度上携有关于PDU起始(结束)位置的冗余信息,表现为以下两点:

(1)对PDU起始(结束)位置具有标识作用:由于字段K和字段P为事先已知,并且在PDU中的偏移位置固定,因此,由该类型字段可实现对PDU的起始(终止)位置的粗略定位.由于字段P的长度通常具有很强的随机性,因此,后续工作主要围绕字段K展开.

(2)对PDU的大小具有约束作用:字段L的取值在一定程度上指示了PDU的大小,为方便表示,用符号R表示这类约束关系.因此,约束关系R在一定程度上反映了PDU定界的正确性,约束关系R的合理利用,可以有效提高PDU的定界性能.

2.2基于路径搜索的容错定界算法

面向差错数据流的PDU容错定界问题的本质是:基于各类协议冗余关系,实现对每个PDU起始(或终止)位置的最佳估计.

由于网络数据传输具有短时突发的特性,因此,可利用时间约束条件确定1次突发数据流的起始和结束时刻,即能够正确得到数据流中第1个PDU的起始位置和最后一个PDU的结束位置,如图3所示.

图3　协议数据单元组成的数据流结构示意图

设第i个PDU的起始位置在数据流中的偏移位置为xi,PDU定界问题进一步可描述为:在差错数据流中PDU个数N未知的条件下,基于协议冗余实现对位置序列x=(x0,x1,x2,x3,…,xN)的最佳估计.

由固定字段的相似匹配方法可得到一组由PDU可能的起始位置构成的位置序列g=(g0,g1,g2,…,gM),称为候选位置序列,其中,M是满足匹配条件位置的个数,从而实现对PDU的粗定界.由于数据部分具有随机特性,在粗定界的过程中会出现数据部分被误判为PDU的起始位置的“虚警”情形,造成PDU定界错误.

现假设通过适当宽松匹配条件,可使得每个PDU的起始位置xi都包含于候选位置序列g中,即P(xi∈g|i=1,2,…,N)≈1成立.此时,PDU的容错定界问题变为如何有效剔除“虚警”情形,在序列g的子序列集合2g中找到与x最为相近的序列=(0,1,…,).由于约束关系R可度量PDU定界的正确性,因此,利用约束关系R构建搜索度量建立目标函数,可为最佳序列的搜索提供有效的指引.

根据定义可知,2g的大小与M成指数关系,依靠遍历的方式对序列进行搜索,则会因运算复杂度太高而难以实现.若将每个候选位置gi理解为一个路径节点,则g的每个子序列都能由如图4所示的拓扑结构中的一条路径惟一表示,于是,最佳子序列的搜索问题转变为最佳路径的搜索问题.此时,结合搜索度量与高效的搜索策略,则可有效降低运算复杂度,最终实现对最佳子序列的搜索.

设节点gi处对应的固定字段K和长度字段L的观测值分别为和,为实现最佳子序列的有效搜索,对分支度量L和路径度量M分别进行如下定义.

图4　基于路径搜索的容错定界模型

定义1 设由节点gi跳转到节点gj的分支度量记为Lij,其中,,表示固定字段取值为k、第i个PDU的长度Δ=gj-gi以及约束关系为R的条件下,固定字段和长度字段的观测值分别为和的概率.

定义2 设到达节点gj的第k路径gk=(g0,gr,…,gi,gj)的路径度量记为,其中,T表示路径gk中所包含的PDU个数,r和t表示为在路径gk中前后相邻的候选节点的序号.为了描述方便,称gr为gt的上游节点,对应的gt则为gr的下游节点.根据上述定义可知,路径度量表征了路径gk中 PDU的平均接收似然概率.设表示到达节点gi的路径gs=(g0,gr,…,gi)的路径度量,则所满足迭代方程为

正如前面描述的遍历所有可行路径会因为存储和运算消耗过高而十分困难,为此,文中借助路径度量淘汰性能恶劣的路径借以缩小遍历空间,即在路径更新时最多保留nmax条性能最优的路径(Top-N准则).

根据上述定义可知,基于最佳路径搜索的容错定界算法的实现步骤如下:

(1)候选位置序列的构建:依据固定字段对接收的数据进行相似匹配形成候选位置节点序列.初始化候选序列g0={g0},搜索指针指向起始位置,并设定判决门限Pth;

(2)最佳路径的搜索:由候选位置序列g=(g0,g1,g2,…,gM),根据搜索策略得到最佳路径.

3　应用实例与仿真

ATM通信网络能够兼具分组交换和电路交换的优点,同时无线ATM通信系统以其机动、灵活的特点在一些抢险、救灾等应急场景具有重要应用,因此,这里以无线ATM通信系统中的AAL5/IP协议为例,对所提出的容错定界算法进行验证.

3.1ATM/AAL5/IP协议格式分析

在ATM网络协议中,IP分组通过逻辑链路控制(Logical Link Control,LLC)和虚电路(Virtual Circuits,VC)复用两种形式封装[15].由于LLC形式下AAL5/IPv4的PDU中含有较长的固定字段(如图5所示至少含有6 B),此时利用粗定界的方法即可取得较好的容错定界效果.因此,为对比性能,接下来仅以VC复用形式进行相应研究.图5给出了两种形式下AAL5协议层对应的服务数据单元(Service Data Unit,SDU)的协议格式.

图5　两种IP分线对应的AAL5-SDU格式

为了使得整个数据在ATM网络中传输,AAL5-SDU还需要经过如下处理:AAL5协议的公共部分汇聚子层(Common Part Convergence Sublayer,CPCS)在AAL5-SDU的尾部添加上填充字段(PADding,PAD)、用户信息字段(User to User,UU)、预留字段(Common Part Indication,CPI)、长度字段(LENgth,LEN)和校验字段(Cyclic Redundancy Check,CRC),并使CPCS-PDU的长度满足48 B的整数倍.由于对于数据业务,AAL5协议中的SSCS协议子层通常并不使用,因此这里也不予讨论.然后,拆装(Segmentation And Reassembly,SAR)协议子层将CPCS-PDU分成若干个ATM的载荷,并根据预先建立的链接添加上ATM首部,为最后一个信元首部的信元载体类型(Payload Type,PT)字段中的结束标志比特置1.整个封装协议过程如图6所示.

图6　AAL5-SDU的封装流程示意图

根据上述解析可知,对于无线ATM网络中的AAL5-PDU的定界即是对CPCS-PDU的定界.接下来对提出两种协议冗余的具体表现形式进行分析.

由实际通信中IP版本广泛采用IPv4,并且首部长度通常为20 B以及服务类型也被设为默认类型(即0x00),因此这些字段可归纳为固定字段K.

CPCS-PDU中的长度字段包含有IP分组中总长度(Total Length,TL)字段和CPCS尾部的LEN字段,两者在本质上是一致的.但文中在此仅选择IP分组中的TL字段作为研究对象.根据协议规范可知,CPCS-PDU的长度必须为48 B的整数倍,同时在实际通信中每个PDU的长度λ都处于一定范围内,因此,可用

来描述约束关系R,其中,σ为CPCS协议封装的协议尾部的长度.

3.2仿真实验结果与分析

为了验证所提算法的有效性,以Matlab 2010b为实验平台进行了如下仿真实验.根据上节的分析内容可知,固定字段K为k=(4 500)H,lk=16 bit,以及TL字段的长度ll=16 bit.由于数据部分具有随机型,因此设数据中的每比特都满足独立同分布条件,且P(dj=0)=P(dj=1)=0.5.为简化仿真实验,此处将式(2)所示的依概率匹配准则简化为汉明距离准则,因此,阈值Pth对应为距离门限Dth.设定界错误率为在差错数据流中无法正确还原的PDU占总PDU的比率,则仿真结果如表1和表2所示,其中,p为信道误比特率,p0为粗定界方法的漏检率,P1为粗定界方法的定界错误率,P2为依据协议的常规定界方法的定界错误率,P3为基于最佳路径搜索的定界算法的定界错误率.

表1　在信元流中含有20个PDU,Top-N为8条件下的仿真结果

表2　在信元流中含有100个PDU,Dth为2 bit条件下的仿真结果

根据表1可知,三者的定界性能都随着误比特率的降低而提高,而在误比特率低于10-4时,基于路径搜索的定界算法定界错误率接近于0,明显优于粗定界算法和常规定界算法.但此时粗定界算法的定界错误率却趋于稳定,甚至低于常规定界算法的性能,原因在于固定字段的相似匹配时数据部分会引入较大的“虚警”概率.如果降低判决阈值Pth(即将距离门限Dth由2 bit降低为1 bit),则可有效降低“虚警”概率,提高粗定界性能;但基于路径搜索的容错定界算法的前提为每个PDU的起始位置都包含于候选序列中,因此,降低判决阈值时会引入“漏警”情形,从而影响基于路径搜索的容错算法的定界性能,造成错误率升高.根据上述分析,为保证基于路径搜索的容错定界算法的性能,在选择判决阈值Pth(或Dth)时,需综合考虑信道误比特率p和固定字段长度lk等因素影响,保证固定字段K的检测概率,使得每个PDU的起始位置都能以接近于1的概率包含于候选位置序列g中.

由表2的仿真结果可知,在最佳路径搜索时,当Top-N准则保留路径个数nmax满足一定条件时,其容错定界的性能不会随nmax的增多而有明显变化.比较表1和表2可知,基于路径搜索的容错定界算法的性能会随着数据流中PDU个数的增加而下降,原因在于路径度量表征了PDU的平均接收概率,因此,当PDU个数较多时,平均接收概率会掩盖路径间的细小差异,造成性能的丢失.

4　结束语

因无线网络误比特率相对较高,传输的网络数据极易含错,造成基于传统协议规范的PDU定界算法不再可靠.针对上述问题,笔者通过对网络协议冗余的研究,提出一种面向差错数据流的PDU容错定界算法.依据各字段在定界时的作用将PDU中各个字段划分为4种类型,利用PDU中固定字段的冗余给出了基于相似匹配的粗定界算法.为克服粗定界时出现“虚警”情形,在粗定界的基础上将PDU定界问题转化为路径搜索问题,借助PDU中长度字段所携带的冗余建立搜索度量,给出了一种基于最佳路径搜索的PDU容错定界算法.最后,以ATM网络中AAL5/IP协议数据单元的定界问题为例,进行了仿真实验.仿真结果表明,所提算法能够克服常规定界算法对差错敏感的缺陷,有效提高了PDU定界的正确率.

[1]XIE J,HU W,ZHANG Z H.Efficient Software Partial Packet Recovery in 802.11 Wireless LANs[J].IEEE Transactions on Computers,2014,63(10):2402-2415.

[2]AMAN M N,SIKDAR B,CHAN W K.Efficient Packet Recovery in Wireless Networks[C]//2014 IEEE Wireless Communications and Networking Conference.Piscataway:IEEE,2014:1791-1796.

[3]WANG S S,SHEU S T,LEE H Y,et al.CPR:a CRC-based Packet Recovery Mechanism for Wireless Networks [C]//2013 IEEE Proceedings of Wireless Communications and Networking Conference.New York:IEEE,2013: 321-326.

[4]JAMES A,MADHUKUMAR A S,KURNIAWAN E,et al.Spectrally Efficient Packet Recovery in Delay Constrained Rateless Coded Multi-hop Networks[J].IEEE Transactions on Communications,2013,61(11):4462-4474.

[5]PASIYAWALA P,PATEL M,PATEL Y,et al.Performance Analysis of Error Concealment Algorithm During Image Recovery[C]//Proceedings of 2014 International Conference on Green Computing Communication and Electrical Engineering.Piscataway:IEEE,2014:1-6.

[6]张仪云,高文华,王海东.视频传输的错误隐藏技术综述[J].计算机应用研究,2015,32(2):330-335. ZHANG Yiyun,GAO Wenhua,WANG Haidong.Survey of Error Concealment for Video Transmission[J]. Application Research of Computers,2015,32(2):330-335.

[7]冯宾,朱光喜,刘予文.基于H.264/AVC的时空域差错隐藏方案[J].通信学报,2007,28(4):72-79. FENG Bin,ZHU Guangxi,LIU Yuwen.Spatio-temporal Error Concealment Scheme Based on H.264/AVC[J]. Journal on Communications,2007,28(4):72-79.

[8]张建龙,吴成柯,石迎波,等.一种基于混合域牛顿插值的视频错误隐藏方法[J].西安电子科技大学学报,2006,33 (5):687-690. ZHANG Jianlong,WU Chengke,SHI Yingbo,et al.An Error Concealment Algorithm Based on Newton Interpolation in the Hybrid Field[J].Journal of Xidian University,2006,33(5):687-690.

[9]施里涛,李欧,王晓梅,等.一种高能效的无线传感器网络自主容错机制[J].电路与系统学报,2013,18(2):102-107. SHI Litao,LI Ou,WANG Xiaomei,et al.An Active Fault-tolerant Scheme with High Energy Efficiency in Wireless Sensor Networks[J].Journal of Circuits and Systems,2013,18(2):102-107.

[10]MARIN C,LEPROVOST Y,KIEFFER M,et al.Robust MAC-lite and Soft Header Recovery for Packetized Multimedia Transmission[J].IEEE Transactions on Communications,2010,58(3):775-784.

[11]陈越新,郑辉,赵艳秋,等.针对IPv4协议的容错解码算法研究[J].电子科技大学学报,2010,39(1):29-32. CHEN Yuexin,ZHENG Hui,ZHAO Yanqiu,et al.Algorithmic Research on Error Resilient Decoding for IPv4 Protocol[J].Journal of University of Electronic Science and Technology of China,2010,39(1):29-32.

[12]SCHMIDT F,ORLEA D,WEHRLE K.A Heuristic Header Error Recovery Scheme for RTP[C]//Proceedings of 2013 10th Annual Conference on Wireless On-demand Network Systems and Services.Piscataway:IEEE,2013: 186-190.

[13]HEYCARE.帧定界的基本方法[EB/OL].[2015-05-17].http://blog.csdn.net/fzu_dianzi/article/details/7358238.

[14]宋青,江小帆.最短路径算法加速技术研究综述[J].电子科技大学学报,2012,41(2):176-184. SONG Qing,JIANG Xiaofan.Survey of Speedup Techniques for Shortest Path Algorithms[J].Journal of University of Electronic Science and Technology of China,2012,41(2):176-184.

[15]郑俊飞.基于SDH帧数据的ATM信元提取与解析技术研究[D].长沙:国防科技大学,2008:43-45.

(编辑:齐淑娟)

Algorithm for error-tolerant delimitation for the protocol data unit based on best path searching

FAN Liang,WANG Xiaomei,YANG Dongyu
(College of Information Engineering,The PLA Information Engineering Univ.,Zhengzhou 450002,China)

Aiming at the error delimitation caused by the high bit error rate in a wireless network,an algorithm for error-tolerant delimitation for the Protocol Data Unit(PDU)based on best path searching is proposed.With the analysis of the protocol redundancy in delimitation,the PDU delimitating is treated as a path searching problem exploiting the rough delimitation result,then an algorithm based on best path searching is provided.Simulation and analysis of the ATM Adaption Layer 5(AAL5)and Internet Protocol (IP)protocols in the Asynchronous Transfer Mode(ATM)network show that this method can decrease the rate of error delimitation,overcoming the conventional one’s sensitivity to error and achieving a better errortolerant performance.

wireless network;protocol data unit;delimitation;path searching;error-tolerant

TP393

A

1001-2400(2016)05-0160-07

10.3969/j.issn.1001-2400.2016.05.028

2015-06-11 网络出版时间:2015-12-10

西南电子电信技术研究所预研资助项目(2014024)

范 亮(1989-),男,解放军信息工程大学硕士研究生,E-mail:fanlya6@163.com.

网络出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.056.html