一種基于子集約束的協(xié)議首部糾錯算法

王曉梅 范 亮 陳 彥 洪先強

?

一種基于子集約束的協(xié)議首部糾錯算法

王曉梅①范 亮*①陳 彥①洪先強①

(解放軍信息工程大學信息系統(tǒng)工程學院 鄭州 450002)

針對無線網(wǎng)絡數(shù)據(jù)的協(xié)議首部容易出錯問題，該文在研究基于循環(huán)冗余校驗的協(xié)議首部糾錯算法的基礎(chǔ)上，提出一種基于子集約束的糾錯算法。該算法利用接收比特的置信度信息以接收向量為中心構(gòu)建約束子集，從而縮小運算搜索范圍，克服此前算法運算復雜度高的缺陷。隨后，結(jié)合無線信號類型與信道模型，對算法的測試長度參數(shù)的取值范圍進行了理論分析和實驗驗證。仿真結(jié)果表明，對于不同信噪比的無線信號，該算法可通過改變測試長度來調(diào)節(jié)約束子集大小，實現(xiàn)在保證較好性能條件下有效地降低運算開銷，具有較強的實際應用價值。

無線通信；無線多媒體；協(xié)議首部糾錯；校驗字段

1 引言

隨著人們對方便、快捷、相對自由的無線通信越來越熱衷，無線技術(shù)也因此取得飛速發(fā)展。但無線通信始終處于開放環(huán)境容易受到各類干擾，傳輸誤比特率相對較高[1]，因而一直制約了它的應用。針對這一問題，文獻[2,3]提出在反饋重傳機制下通過接收端對接收數(shù)據(jù)進行處理實現(xiàn)對含錯的分組數(shù)據(jù)恢復，減少重傳次數(shù)來提高接收效率。然而，對于一些實時要求高或只能單向通信的特殊場合反饋重傳機制無法應用。于是一些學者們另辟蹊徑對網(wǎng)絡協(xié)議的冗余展開研究，提出了針對協(xié)議首部糾錯的容錯接收算法，利用冗余提高系統(tǒng)的容錯能力。

針對無線通信協(xié)議中控制字段的取值存在著冗余特點，文獻[4]提出了在高斯信道背景下基于似然概率的協(xié)議首部糾錯算法(Robust Header Recovery, RHR)，在一定程度上實現(xiàn)了對無線協(xié)議首部的糾錯。無獨有偶，文獻[5,6]出于同樣的想法，并考慮到無線終端的運行成本，給出了在二進制對稱信道條件下基于最小距離的協(xié)議首部糾錯方法(Min DIStance header recovery, Min DIS)。該方法用比特向量的二元域運算代替了RHR算法中的概率運算，具有較強的可實現(xiàn)性，但也造成了糾錯性能的損失。但上述兩種算法只是研究了字段自身的冗余，并沒有涉及字段間所存在的冗余。文獻[79]對協(xié)議中校驗字段攜帶的冗余信息進行了探索，提出了聯(lián)合循環(huán)冗余校驗的協(xié)議首部糾錯算法(Robust Cyclic Redundancy Check header recovery, Robust CRC)，通過字段間的冗余信息提高糾錯性能。該算法的缺點是運算復雜度隨校驗長度成指數(shù)式的增長，糾錯性能也會隨著校驗長度的增加而下降。而實際通信協(xié)議中校驗字段的校驗范圍往往較長，該算法的實現(xiàn)和應用是一個難題。盡管借助維特比格型譯碼形式的計算方法可降低運算復雜度，但復雜度依舊較高，同時也引入存儲空間開銷大的問題。

而且文獻[1,4-9]中提到為了最大限度地保留接收信號的有用信息，所有處理過程都應該以軟信息的形式輸入輸出，如此則會進一步增加糾錯算法的運算成本，限制了其實用性。為此，本文借鑒Chase譯碼算法[10,11]的思想，在Robust CRC糾錯算法基礎(chǔ)上提出了一種約束子集的協(xié)議首部糾錯算法(Bit- Flip subset constraint CRC, BF-CRC)。該算法借助每比特的置信度信息對接收信號進行預先處理, 建立一個以接收向量為中心的約束子集，通過調(diào)整約束子集的大小來維持較好的糾錯性能，最終實現(xiàn)算法的搜索范圍地縮小，有效地降低算法的運算復雜度，解決了Robust CRC算法無法實用的問題。

2 子集約束的協(xié)議首部糾錯算法

2.1 基于校驗關(guān)系協(xié)議首部糾錯算法概述

網(wǎng)絡協(xié)議字段依據(jù)其在通信過程中不同特性可分為[8]：(1)固定字段：實現(xiàn)通信控制、幀同步等功能的取值固定的字段。(2)可推測字段：根據(jù)前后時刻傳輸?shù)姆制瑪?shù)據(jù)或上下層關(guān)系可推測出取值的字段。因為字段和字段在糾錯時都認為是已知的，所以后續(xù)敘述中統(tǒng)一描述為字段。(3)未知字段：在數(shù)據(jù)傳輸過程中對與通信鏈接起到重要作用的字段，其取值空間的大小可以根據(jù)協(xié)議內(nèi)的約束關(guān)系進行有效的壓縮。鑒于其對通信的重要作用，協(xié)議首部糾錯實質(zhì)就是對該部分進行恢復。(4)不關(guān)心字段：該字段的取值無法在當前協(xié)議層中解析，或者其取值對通信的影響不大；(5)校驗字段：在通信協(xié)議中起到差錯控制作用的字段，該部分完全屬于通信時額外引入的冗余信息。當發(fā)送數(shù)據(jù)為，對應的接收數(shù)據(jù)為時，根據(jù)最大后驗概率準則可知，未知字段的最佳估計為

將上述式(2)代入式(1)，則估計算子可以轉(zhuǎn)化為

為此，文獻[8]借鑒線性分組碼的格型譯碼[12]思想展開了相應的研究。設(shè)CRC校驗函數(shù)為，字段和字段分別取值分別為和，其他字段置為0所構(gòu)成的向量經(jīng)過運算后的校驗值記為。依據(jù)校驗函數(shù)分解的特性有式(5)成立。

式(7)可借用格型圖以逐比特迭代的方式實現(xiàn)計算[8]，于是計算復雜度降為。此方法為基于校驗的糾錯算法的實現(xiàn)提供一個解決思路，但卻存在著數(shù)量級的存儲開銷的問題。如果校驗字段長度較長，上述算法的計算復雜度和空間復雜度也會非常高，例如對于實際的校驗字段為4 Byte的情形則需要個double類型的存儲單元(大約為16 GByte)來存儲校驗狀態(tài)概率，這樣的實現(xiàn)壓力對于當前無線終端設(shè)備仍舊是無法承擔的。

2.2子集約束的協(xié)議首部糾錯算法

根據(jù)高斯信道具無記憶性，且式(3)等號右側(cè)的后半部分的條件概率只與錯誤圖樣有關(guān)。因此將式(3)可變換為

圖1 對于發(fā)送為o接收數(shù)據(jù)為yo時，受到不同程度噪聲干擾所對應情形

根據(jù)子集約束的方法可將式(9)近似為

因測試長度通常取值較小，所對應的需遍歷的范圍也會較小，于是算法的運算復雜度下降為，小于Robust CRC算法的，而且該算法不需要同時存儲所有校驗狀態(tài)取值的概率所以存儲的需求也較低，保證了算法的可實現(xiàn)性。最后，將式(10)代入式(4)中可得到對于未知字段的估計。

表1各算法理論上運算消耗

接下來以不關(guān)心字段為5 bit，測試向量長度為2 bit的情形為例子進行說明。設(shè)在接收向量的各個比特對應的置信度(即為接收信號的測量信息[10])分別為｛1.2, 0.2, -0.1, 0.9, -0.8｝，且時，表2給出了對應的約束子集中各個向量的具體取值。最后，將的各個取值代入到式(11)中，實現(xiàn)對未知字段的估計。

表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算法中因所需運算操作得到減少，極大的降低了運算復雜度，提高算法可實現(xiàn)性與實用性。

2.3 子集約束算法性能與相關(guān)參數(shù)的關(guān)系

根據(jù)2.2節(jié)的分析可知，子集約束算法的性能受信道信噪比估計和參數(shù)大小的影響。至于無線通信系統(tǒng)的信噪比估計問題一直以來都是備受大家關(guān)注的問題，當前也已經(jīng)取得許多重要成果。文獻[15]對當前較為經(jīng)典的信噪比估計算法進行了歸納總結(jié)，比較分析了各自的優(yōu)缺點，隨后文獻[16]則提出了一種新型的基于相關(guān)向量機的信噪比估計算法，該方法具有估計范圍大、估計精度高的特點。

圖2 BPSK信號的概率分布圖

3 算法仿真與分析

仿真1 本文通過設(shè)定一種協(xié)議格式并作為實驗對象來驗證BF-CRC算法的有效性，以Matlab 2010b為實驗平臺進行仿真，最后將其性能與Robust CRC算法和Min DIS算法進行比較。設(shè)定協(xié)議中包括8 bits的固定字段, 8 bit的未知字段, 30 bit的不關(guān)心字段以及利用CRC8的校驗字段。設(shè)物理層傳輸?shù)男盘栃问綖镈BPSK，并能提供置信度最低的個比特的對應位置。雖然Robust CRC算法提到利用的軟信息進行糾錯，但考慮到計算量等實際問題則實驗中依舊采取硬判決信息進行處理與分析。在測試向量長度取不同值條件下，實驗結(jié)果如圖3所示。

軍工產(chǎn)品質(zhì)量管理系統(tǒng)建設(shè)以質(zhì)量策劃為基本環(huán)節(jié)，只有高度重視該環(huán)節(jié)，做好質(zhì)量策劃工作，才能更好地促進軍工產(chǎn)品質(zhì)量管理系統(tǒng)的有效運行。軍工企業(yè)應在了解行業(yè)競爭趨勢的基礎(chǔ)上結(jié)合自身實際與IS09000標準制定合理的管理方式來進行活動策劃，在不斷優(yōu)化質(zhì)量管理系統(tǒng)的同時提高質(zhì)量管理系統(tǒng)質(zhì)量。一方面，明確策劃重點，即如何開展質(zhì)量管理系統(tǒng)優(yōu)化活動，在此基礎(chǔ)上策劃質(zhì)量管理系統(tǒng)運行方案，建立符合現(xiàn)實需求的質(zhì)量目標，通過相關(guān)有效對策來進行質(zhì)量評估；另一方面，以質(zhì)量管理系統(tǒng)運行現(xiàn)狀為依據(jù)信息策劃，尤其要針對運行過程中國存在的不確定因素與諸多變更作出預防，最大限度地確保質(zhì)量管理系統(tǒng)與軍工產(chǎn)品要求相符合。

圖3 不同測試長度下BF-CRC與其他算法的性能對比

在信道信噪比在3~8 dB范圍內(nèi)BF-CRC和Robust CRC兩個算法的糾錯性能都比Min DIS算法好，這是由于校驗字段中其實攜有較多的有用信息。由前面分析可知如果算法在信噪比4.8 dB時取得較好果則理應滿足條件，由的曲線可驗證2.3節(jié)的分析的正確性。

仿真2 為了進一步說明BF-CRC算法的在具體情形中的實用性，本文設(shè)置具體的實驗場景如下：無線接入點(Access Point, AP)發(fā)送的數(shù)據(jù)，經(jīng)過加性高斯白噪聲信道(或慢衰落瑞利信道)，最后在用戶端(User)接收。相對加性高斯白噪聲信道而言，在慢衰落瑞利信道條件下應用BF-CRC算法時需要增加考慮相位差異以及衰落因子等對置信度度量造成的影響[17,18]。根據(jù)文獻[4]中提到的協(xié)議壓縮技術(shù)可知，在該場景下WIFI的802.11 MAC和IP協(xié)議可以進行如下冗余分析[19]，如圖4所示。后續(xù)部分將詳細解析無線終端同時開啟多個下載業(yè)務的情形時，網(wǎng)絡協(xié)議中的冗余：

圖4 WIFI的802.11MAC和IP協(xié)議格式

(1)對已經(jīng)建立鏈接的下行數(shù)據(jù)，MAC協(xié)議層中幀控制字段(Frame Control)、目的MAC地址(MAC Addr1), AP的MAC地址(MAC Addr2)、源MAC地址(MAC Addr3)、序號控制(Seq)等字段都可以根據(jù)通信的前后數(shù)據(jù)幀以及下層協(xié)議推測得到。

(2)在IP協(xié)議層中，實際應用時發(fā)現(xiàn)版本號(Version)、服務類型(Service)、分片(Frag)和片偏移(Offset)等字段取值在通用的情形下是固定的，屬于字段。數(shù)據(jù)長度(TotalLen)字段其取值則可通過下層協(xié)議傳輸?shù)姆諗?shù)據(jù)單元長度得到，屬于可推測字段。設(shè)下載業(yè)務都是使用相同的應用協(xié)議，因此可認為協(xié)議類型字段(Type)為已知。對于IP分組中的目的IP地址是在其接入網(wǎng)絡時就已分配，也屬于字段。

(3)其他一些字段取值雖不固定，例如標識字段(ID)、生存周期(TTL)和校驗和(Checksum)，但不會影響到整個鏈接以及傳輸?shù)恼_性，因此定義為不關(guān)心字段(根據(jù)校驗的特性可知Checksum中其實也具有冗余信息，限于時間本文在此暫不予討論)。

綜上所述，對網(wǎng)絡中數(shù)據(jù)首部糾錯最終歸結(jié)為對源IP地址的容錯估計。在同時進行多個下載業(yè)務時，接收數(shù)據(jù)的源IP地址具有標識數(shù)據(jù)流的作用，因此根據(jù)CRC校驗字段(FCS)對源端IP地址進行糾錯具有十分重要的意義。

為了簡便，特對802.11的無線WIFI信號進行簡化，忽略擴頻、信道編碼等技術(shù)，并設(shè)信號的類型為DBPSK信號。在具體協(xié)議中，CRC校驗字段(FCS)長度為4 Byte，因此正如前面舉例提到的如果直接采用Robust CRC算法，則需要個double類型的存儲單元(大約為16 GByte)來存儲校驗狀態(tài)概率，如此的存儲開銷是難以承受的。因此文獻[8]中提出次優(yōu)的Robust CRC算法(sub-Robust CRC)，將FCS字段分成4個8 bit的被認為獨立的校驗字段，此時存儲需求降為個double類型的存儲單元(大約4 kByte)，再利用CRC校驗關(guān)系進行糾錯。本部分主要將BF-CRC算法與可實現(xiàn)的sub-Robust CRC算法和Min DIS算法等進行性能對比。以Microsoft Visual Studio 2008為平臺進行仿真實驗。

由實驗結(jié)果圖5和圖6可知，當測試向量長度較短時，BF-CRC算法的性能需要在高信噪比的情況下才具有效果；當測試長度相應的增加時，如取6 bit, BF-CRC算法糾錯性能明顯改善，對于加性高斯白噪聲信道下在信噪比為7 dB時其協(xié)首部出錯概率約為而sub-Robust CRC算法的約為；對于慢衰落瑞利信道下信噪比20 dB時其協(xié)議首部出錯率約為明顯優(yōu)于sub-Robust CRC算法的。由前面描述知sub-Robust CRC算法中將 FCS字段分解為4個8 bit近似獨立的校驗字段，如此便破壞了校驗字段內(nèi)部的約束關(guān)系造成性能的極大損失。因此當信噪比較高時，BF-CRC算法糾錯效果明顯，且性能顯著優(yōu)于sub- Robust CRC算法。

圖5 在AWGN信道下不同的糾錯算法的性能對比

圖6 在Rayleigh信道下不同的糾錯算法的性能對比

4 結(jié)束語

本文在提出了一種利用置信度信息的子集約束糾錯算法(BF-CRC)，該算法利用每個比特的置信度信息構(gòu)建以接收向量為中心的約束子集，降低計算聯(lián)合后驗概率時需遍歷空間的大小，通過理論分析和實驗驗證得到BF-CRC算法具有算法復雜度低的特點。本文最后分別對抽象協(xié)議和802.11的無線MAC協(xié)議進行了仿真實驗，仿真結(jié)果表明BF-CRC可通過調(diào)節(jié)測試長度保證較好的糾錯性能，減少運算開銷，增強系統(tǒng)可實現(xiàn)性，提高無線通信網(wǎng)絡的抗噪聲性能。值得注意的是BF-CRC僅僅只是利用了置信度信息來鎖定不確定的比特的位置，倘若在計算似然概率時采用軟信息的形式，其糾錯性能將會進一步得到提高。再者，雖然本文只是重點討論了利用CRC校驗進行首部糾錯，而其他協(xié)議層也有類似的校驗關(guān)系，例如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] 施里濤, 李歐, 王曉梅, 等. 一種高能效的無線傳感器網(wǎng)絡自主容錯機制[J]. 電路與系統(tǒng)學報, 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] 韓博, 吳杰, 許華, 等. 基于相關(guān)向量機的信噪比估計算法[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] 馮戰(zhàn), 鄭海昕, 秦銘晨. 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網(wǎng)絡優(yōu)先出版

國家安全重大基礎(chǔ)研究(6131482013)資助課題

王曉梅： 女，1976年生，博士，講師，研究方向為無線自組織網(wǎng)絡和網(wǎng)絡數(shù)據(jù)協(xié)同處理.

范 亮： 男，1989年生，碩士生，研究方向為網(wǎng)絡數(shù)據(jù)協(xié)同處理.

陳 彥： 男，1990年生，碩士生，研究方向為網(wǎng)絡數(shù)據(jù)協(xié)同處理.