一種利用最佳路徑搜索的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