張　強，閆　斌，楊　蔚，周　輝

(1.電子科技大學 自動化工程學院，四川 成都 611731；2.四川省電力公司，四川 成都 610000)

?

基于預測的混和自動重傳請求算法* 1

張強1，閆斌1，楊蔚2，周輝2

(1.電子科技大學 自動化工程學院，四川 成都 611731；2.四川省電力公司，四川 成都 610000)

摘要：為了解決無線傳輸過程中無線信道易受多徑效應、抖動效應、衰落等因素的影響而使傳輸?shù)挠行院涂煽啃缘貌坏奖Ｕ系膯栴}，提出了一種基于預測的混和自動重傳請求算法。利用隱馬爾科夫模型預測傳輸過程中下一時刻的丟包率，根據(jù)不同時刻丟包率狀態(tài)的比值關系動態(tài)調(diào)節(jié)里德-索洛蒙(Reed-Solomon)碼的監(jiān)督元數(shù)量。仿真結果表明,該算法與傳統(tǒng)Ⅰ型混和自動重傳請求(HARQ)算法和Ⅱ型混和自動重傳請求(HARQ)算法相比，能夠明顯減少重傳次數(shù)，降低誤碼率，通信可靠性明顯提高。

關鍵詞：無線傳輸；混和自動重傳請求算法；隱馬爾科夫模型；預測

0引言

無線通信環(huán)境中，無線信道常常受到噪聲、多徑效應、信號衰減等因素的影響，使得傳輸誤碼率較高，從而影響數(shù)據(jù)傳輸質(zhì)量。因此，無線傳輸系統(tǒng)中采用差錯控制技術具有重要意義。

差錯控制的方式分為三類：前向糾錯(FEC,ForwardErrorCorrection)、檢錯重傳(ARQ,AutomaticRepeatreQuest)、 混合自動重傳請求(HARQ,HybridAutomaticRepeatRequest)。前向糾錯(FEC)方式是發(fā)送端編碼器通過加入冗余信息的方式將所發(fā)信息編碼成糾錯碼[1]，在接收端，若譯碼器有能力糾正接收到錯誤信息，則譯碼器自動對接收到的信息進行糾正。前向糾錯無需將譯碼結果反饋給發(fā)送端，傳輸延遲小，但由于接收端無法完全糾正錯誤時不能反饋，所以其傳輸可靠性得不到保障，且由于糾錯碼冗余量恒定，無法適應時刻變化的信道。檢錯重傳(ARQ)是發(fā)送端編碼器將信息編碼成可檢錯的碼，根據(jù)接收的信息是否有錯誤向發(fā)送端發(fā)送反饋信號。若反饋否定信號，則將該信息重新發(fā)送；反之，則發(fā)送下一組信息。檢錯重傳方式發(fā)送的檢錯碼只需少許多余碼元就可以使信息可靠傳輸，并且能夠適應變化的信道，但由于反饋信道的存在，其傳輸延遲有所增大。Wozencraft在文獻[2]中將FEC和ARQ相結合，闡述了HARQ的基本原理，首次提出HARQ算法，此算法被稱為Ⅰ型HARQ。之后，Lin和Yu在1982年在文獻[3]中提出了對Ⅰ型HARQ算法的改進，采用增量冗余的方式傳輸，被稱為Ⅱ型HARQ。HARQ是FEC和ARQ的結合，信息塊經(jīng)過無線信道到達接收端后，如果信息塊的錯誤數(shù)量在糾錯碼糾錯范圍內(nèi)，則接收端譯碼器對其進行糾錯；如果糾錯碼的糾錯能力不足以糾正信息塊中的錯誤，則通過反饋信號請求發(fā)送端重傳此信息塊。HARQ結合了ARQ和FEC的優(yōu)點，在一定程度上減少了時延，提高了帶寬利用率。但由于無線信道不穩(wěn)定，隨時都有可能變化，產(chǎn)生突發(fā)錯誤。

Gilbert在文獻[4]中首次提出利用兩狀態(tài)的隱馬爾科夫模型(HMM，hiddenMarkovmodel)對無線信道進行建模。目前，常用兩狀態(tài)的HMM即Gilbert模型作為無線傳輸包錯誤的模型[5]。但Gilbert模型不能精確的表示變化劇烈的信道特性。文獻[6]利用三狀態(tài)的HMM預測短波信道可用性，并根據(jù)預測結果選擇接入信道，增大了信道利用時長，同時減少了切換率。Duarte在文獻[7]中，利用HMM提出了一種自適應FEC算法，可以根據(jù)HMM的預測結果選擇不同的FEC方案。文獻[8]對HARQ系統(tǒng)中的自適應編碼調(diào)制技術進行了研究，提出了HARQ和AMC相結合的跨層自適應傳輸方案。Fernando在文獻[9]中提出利用Gilbert模型預測丟包率，并根據(jù)丟包率動態(tài)調(diào)節(jié)FEC參數(shù)。實驗結果表明，預測模塊對傳輸質(zhì)量的提升起著重要作用。文獻[10]在LDPC碼的基礎上提出了針對DSRC系統(tǒng)中IEEE802.11p協(xié)議的AMC和HARQ相結合的跨層設計，提高了頻譜效率和吞吐量。文獻[11]研究了基于分組碼(STBC)的MIMO-HARQ系統(tǒng)，文章指出存在兩類可快速解碼的MIMO-HARQ系統(tǒng)：獨立類型和依賴STBC結構類型。對于獨立類型，提出了固定的和基于閾值的自適應方法。對于依賴STBC結構類，提出了針對HARQ算法的低計算復雜度的快速解碼算法。

為了進一步增加無線傳輸過程中的效率及其可靠性，提出了一種基于預測的HARQ算法，利用HMM預測傳輸過程中下一時刻的丟包率，根據(jù)不同時刻丟包率狀態(tài)的比值關系動態(tài)調(diào)節(jié)RS碼的監(jiān)督元數(shù)量。當下一時刻丟包率所對應的觀測符號增大，則RS碼監(jiān)督元數(shù)隨之增大，反之RS碼監(jiān)督元數(shù)量減小或不變。如果調(diào)整后的RS碼依然不能使譯碼器糾正所有錯誤，則進一步增大監(jiān)督元數(shù)量重新傳輸。

1無線信道丟包率預測模型

1.1隱Markov模型(HMM)

隱Markov模型(HMM)為Markov模型的擴展。HMM的狀態(tài)是隱藏的，每個隱藏狀態(tài)會按照一定概率產(chǎn)生觀測符號。所以，隱含狀態(tài)可以通過觀測符號來反映。

一個HMM可由以下五個元素來表示：

1)隱含狀態(tài)S。隱含狀態(tài)是不可見的，某些情況下無實際的物理意義，但在大多數(shù)實際應用中，是有確切的物理意義的。隱含狀態(tài)集合可以表示為S={S1,S2,…,SN},t時刻的狀態(tài)表示為qt。

2)隱含狀態(tài)所對應的觀測序列O。觀測序列集合可表示為O={O1,O2,…,OM}。

3)狀態(tài)轉移矩陣A={aij}N×N。其中，aij=p{qt+1=Sj|qt=Si},1≤i,j≤N,即從狀態(tài)i轉換到狀態(tài)j的概率。

4)觀測符號概率分布矩陣B={bjk}N×M。其中，bjk={Ok|qt=Sj}，1≤j≤N，1≤k≤M。表示狀態(tài)為Sj時產(chǎn)生觀測狀態(tài)為k的概率。

5)初始狀態(tài)分布π={πi}。其中，πi=p{q1=Si}，1≤i≤N。

一個HMM模型可由集合λ={A,B,π}確定。

1.2隱Markov模型對丟包率的預測

采用六狀態(tài)的HMM，根據(jù)信噪比SNR劃分，隱含狀態(tài)與SNR的對應關系如表1所示。

表1　隱含狀態(tài)與SNR對應關系

觀測序列O={O1,O2,…,O15,O16}根據(jù)每秒的丟包率劃分，劃分標準：[0%,1%)為O1,[1%,2%)為O2，…，[14%,15%)為O15，[15%,100%]為O16。

狀態(tài)轉移矩陣A和觀測符號概率分布矩陣B可由Baum-Welch算法得到。首先通過初始化樣本得到初始時刻隱含狀態(tài)概率分布π={p{q1=Si}},1≤i≤6。

定義前向變量:

αt(i)=p(O1O2…Ot,qt=Si|λ)

(1)

為給定模型λ及t時刻狀態(tài)Si，從開始到t時刻觀測序列為O1,O2,…,Ot的概率。

定義后向變量:

βt(i)=p{Ot+1Ot+2…OT|qt=Si,λ}

(2)

為給定模型λ及t時刻狀態(tài)Si，從t+1時刻到最后時刻觀測序列為Ot+1,Ot+2,…,OT的概率。

給定觀測序列和模型λ，t時刻狀態(tài)為Si，t+1時刻狀態(tài)為Sj的概率為：

ξt(i,j)=p{qt=Si,qt+1=Sj|O,λ}

(3)

由前向變量和后向變量可得：

(4)

于是，

(5)

在時間上對rt(i)求和，得到由狀態(tài)Si轉換的數(shù)學期望。類似的，在時間上對ξt(i,j)求和，可得從狀態(tài)Si轉換到狀態(tài)Sj的數(shù)學期望。于是，得到λ={A,B,π}的重新估計值：

(6)

(7)

(8)

根據(jù)以上步驟，反復的進行重新估計，直到觀測值的概率達到閾值,則得到HMM模型的最佳參數(shù)。通過Viterbi算法，可以得到一個與給定觀測序列O={O1,O2,…,OT}的最佳匹配狀態(tài)序列Q={q1,q2,…,qT}。則下一時刻隱含狀態(tài)為：

qT+1=argmax(aqTj),1≤j≤6

(9)

于是，下一時刻所對應的觀測符號為：

OT+1=argmax(bqT+1k),1≤k≤16

(10)

2基于預測的混和自動重傳請求算法

丟包率為信道狀態(tài)的一種反應，丟包率的變化意味著信道狀態(tài)的變化，同時誤碼率也會隨信道狀態(tài)的變化而變化。所以，誤碼率與丟包率存在正相關關系?；陬A測的HARQ算法利用隱馬爾科夫模型預測傳輸過程中下一時刻的丟包率，根據(jù)不同時刻丟包率所對應觀測符號的比值動態(tài)調(diào)節(jié)監(jiān)督元數(shù)量。RS碼編譯碼簡單，且給定碼長n和糾錯能力m時，能直接確定一個RS碼，適合預先設定碼的糾錯能力。對于RS碼，2m個監(jiān)督元，可以糾正m個錯誤。

第t秒與第t+1秒觀測符號比值為：

(11)

式中，t秒時RS碼監(jiān)督元數(shù)量為ut，則t+1秒時RS碼監(jiān)督元數(shù)量為：

ut+1=Int(ut×dt,t+1)+1

(12)

式中，Int()表示向下取整運算。設定最大及最小監(jiān)督元數(shù)目，如果ut+1超過最大監(jiān)督元數(shù)目，則以最大監(jiān)督元數(shù)目作為編碼方案，如果ut+1小于最小監(jiān)督元數(shù)目則以最小監(jiān)督元數(shù)目作為編碼方案。

同時，設定最大傳輸次數(shù)，若接收端譯碼失敗，則由反饋信道傳輸否定信號，編碼器下一次傳輸則增加一定量的監(jiān)督元數(shù)目。此時，如果監(jiān)督元數(shù)量超過上限，則采用最大監(jiān)督元數(shù)目方案。

基于預測的HARQ算法具體步驟如下：

1)根據(jù)初始樣本初始化HMM參數(shù)A、B、π。

2)通過Viterbi算法根據(jù)已知的觀測序列計算出隱含狀態(tài)序列。

3)根據(jù)式(9)得到下一個隱含狀態(tài)。

4)根據(jù)式(10)得到下一狀態(tài)所對應的觀測符號。

5)通過式(11)和式(12)得到下一秒RS編碼所需的監(jiān)督元數(shù)量，確定編碼方案。如果監(jiān)督元數(shù)量達到上限，則以最大冗余量作為編碼方案；如果監(jiān)督元數(shù)量低于下限，則以最小冗余量作為編碼方案。

6)判斷譯碼是否成功，如果不成功且傳輸次數(shù)小于最大傳輸次數(shù)，則增加冗余量后再次傳輸。如果冗余量高于上限或低于下限，則以最大監(jiān)督元數(shù)或最小監(jiān)督元數(shù)為編碼方案。

7)經(jīng)過一段時間τ，利用Baum-Welch算法重新估計HMM參數(shù)A、B、π。

此算法計算代價主要集中在利用Baum-Welch算法重新估計HMM參數(shù)。文獻[12]對Baum-Welch算法復雜度進行了詳細敘述，利用Baum-Welch算法進行參數(shù)估計的每次迭代運算復雜度為O(N2T)，其中，N為HMM隱含狀態(tài)數(shù)量，T為樣本數(shù)量。其計算復雜度會隨著隱含狀態(tài)數(shù)量的增多而迅速增大。

3實驗結果與分析

利用MATLAB仿真工具對該算法進行仿真，并與Ⅰ型HARQ算法和Ⅱ型HARQ算法進行比較。以前20s觀測序列作為初始樣本對HMM模型進行訓練得到其參數(shù)λ={A,B,π}。RS碼碼長設置為n=26-1=63，由63個碼字組成，每個碼字含6比特數(shù)據(jù)，每個碼組有378比特。設定RS碼冗余度最高為(63，11)編碼方案，最低為(63，51)編碼方案。最大傳輸次數(shù)為5，當接收端譯碼失敗，則由反饋信道傳輸否定信號，編碼器下一次傳輸則增加10個監(jiān)督碼元，如果監(jiān)督碼元數(shù)量超過51則保持(63,11)碼不變。每隔1s統(tǒng)計一次丟包率并計算出相對應的觀測符號，每隔3min利用Baum-Welch算法重新估計HMM參數(shù)。

對于Ⅰ型HARQ算法，RS碼始終采用(63,31)編碼方案，即每個碼組中存在32個監(jiān)督元，可以糾正16個錯誤碼字。最大傳輸次數(shù)為5次且每次重傳監(jiān)督元數(shù)量不變。對于Ⅱ型HARQ算法，RS編碼采用增量冗余的傳輸方案。每次重傳監(jiān)督元都進一步增多，直到成功譯碼或傳輸次數(shù)超過5次。

采用改進HARQ算法與Ⅰ型HARQ算法、Ⅱ型HARQ算法進行傳輸?shù)恼`碼率仿真對比圖如圖1所示。從圖中可以看出改進的HARQ算法能夠使誤碼率急劇下降，在4dB時能使誤碼率降為0；Ⅱ型HARQ算法可以變更RS碼的碼率，其誤碼率降低速度優(yōu)于Ⅰ型HARQ算法，但相對于改進的HARQ算法較差；Ⅰ型HARQ算法，不可變更RS碼碼率，在降低誤碼率方面效果最差。

圖1　改進HARQ算法與Ⅰ型HARQ算法、

三種算法傳輸過程中對于傳輸次數(shù)的仿真如圖2所示。在信噪比較低時，誤碼較多，采用冗余度最高編碼方案也無法完全糾正錯誤，所以SNR在3dB之前傳輸次數(shù)為最大傳輸次數(shù)。在此之后，改進的HARQ算法由于可以通過預測在傳輸之前確定合適的RS碼率策略，所以傳輸次數(shù)迅速降為1次。Ⅰ型HARQ算法始終采用(63,31)編碼方案，而Ⅱ型HARQ算法第一次傳輸采用較少監(jiān)督元的方案，隨著重傳次數(shù)的增加接收端碼率逐漸降低。所以，Ⅰ型HARQ算法傳輸次數(shù)略少于Ⅱ型HARQ算法。

圖2　改進HARQ算法與Ⅰ型HARQ算法、

定義吞吐量為正確接收的信息比特數(shù)除以為了正確傳輸這些信息而發(fā)送的所有比特數(shù)[13]。改進的HARQ算法與Ⅰ型HARQ算法、Ⅱ型HARQ算法傳輸過程中吞吐量仿真對比圖如圖3所示。從圖3可以看出，改進的HARQ算法可以使吞吐量迅速上升，而采用Ⅰ型HARQ算法和Ⅱ型HARQ算法時，吞吐量上升較為緩慢。然而，對于改進的HARQ算法來說，信道狀況較好時的觀測符號1所對應的丟包率為[0%,1%),所以在觀測符號為1時，所采用的RS編碼方案為可以解決狀態(tài)1最壞情況的編碼方案，即丟包率為1%時的方案。所以，在信噪比很高的情況下，改進的HARQ算法吞吐量略低于第一次傳輸監(jiān)督元較少的Ⅱ型HARQ算法。Ⅰ型HARQ算法始終采用編碼方案(63,31)，所以其吞吐量最大為31/63。

圖3　改進HARQ算法與Ⅰ型HARQ算法、

改進的HARQ算法與Ⅰ型HARQ算法、Ⅱ型HARQ算法傳輸過程中單位時間內(nèi)有效比特數(shù)仿真對比圖如圖4所示。

圖4　改進HARQ算法與Ⅰ型HARQ算法、

從圖4中可以看出，改進的HARQ算法有效比特數(shù)上升較快，而傳統(tǒng)HARQ算法有效比特數(shù)上升緩慢。由于改進的HARQ算法吞吐量小于Ⅱ型HARQ算法，所以在信噪比較高傳輸次數(shù)為1時，其有效比特數(shù)略小于Ⅱ型HARQ算法。值得提出的是，代碼編寫方式以及仿真計算機硬件的不同會造成傳輸有效比特數(shù)的差異。

4結語

針對無線信道易受外界干擾而使傳輸質(zhì)量得不到保障的問題，本文提出了一種基于HMM預測的HARQ算法。利用HMM預測傳輸過程中的丟包率，并通過丟包率狀態(tài)的比值關系確定下一時刻所采用的RS編碼方案。仿真實驗表明，通過自適應調(diào)節(jié)RS編碼冗余量，能夠使接收信息擁有較低的誤碼率，信道SNR在4dB時誤碼率即可降為0，提高了無線傳輸系統(tǒng)的傳輸可靠性。并且，能夠使傳輸次數(shù)迅速降為1次，隨著重傳次數(shù)的減少，傳輸效率隨之增高。同時，吞吐量上升速度也迅速增高。對于該算法的進一步研究，可以從丟包率狀態(tài)劃分入手，更精細的丟包率狀態(tài)劃分可以得到更高的最大吞吐量。

參考文獻：

[1]趙琦，劉榮科.編碼理論[M].北京：北京航空航天大學出版社，2009.

ZHAOQi,LIURong-ke.CodingTheory[M].Beijing:BeihangUniversityPress,2009.

[2]Wozencraft,JohnM,Horstein,Michael.CodingforTwo-WayChannels[D].MassachusettsInstituteofTechnology,ResearchLaboratoryofElectronics.1961.

[3]LINS,YUPS.AHybridARQSchemewithParityRetransmissionforErrorControlofSatelliteChannels[J].Communications,IEEETransactionsoncommunications,1982,30(7):1701-1719.

[4]GilbertEN.CapacityofaBurst-NoiseChannel.BellSystemTechnicalJournal[J].1960,Vol.39(5):1253-1265.

[5]張珍明.無線視頻傳輸關鍵技術研究[D].武漢：華中科技大學，2006.

ZHANGZhen-ming.KeyTechnologyofVideoTransmissionoverWirelessChannel[D].Wuhan:HuazhongUniversityofScienceandTechnology,2006.

[6]林剛，程云鵬，江漢.一種基于HMM預測的短波信道接入方法[J].通信技術，48(12):1377-1383.

LINGang,CHENGYun-peng,HANJiang.AShortwaveChannelAccessMethodbasedonHMMPrediction[J].CommunicationsTechnology,48(12):1377-1383

[7]DuarteFP,EAdeSouzaeSilva,DonTowsley.AnAdaptiveFECAlgorithmusingHiddenMarkovChains[J].ACMSIGMETRICSPerformanceEvaluationReview.2003.vol.31(2):11-13

[8]李長春.自適應傳輸關鍵技術與研究應用[D].濟南：山東大學，2011.

LIChang-chun.ResearchonKeyTechnologiesandApplicationsofAdapativeTransmission.Jinan:ShandongUniversity,2011.

[9]FernandoS,Edmundo.PredictingPacketLossStatisticswithHiddenMarkovModelsforFECControl[J].ComputerNetworks.2012,vol.56(2):628-641.

[10]ZHANGGao-yuan,SUNLi-min,WENHong,WUBin,ZHUXi-ping,ZHOULiang-huang,LIUSheng.ACross-LayerDesignCombiningofAMCwithHARQforDSRCSystems[J].InternationalJournalofDistributedSensorNetworks,2013,Vol.15(4):2122-2122.

[11]HosseiniSS,AboueiJ,UysalM.Fast-DecodableMIMOHARQSystems[J].IEEETransactionsonWirelessCommunications,2015,Vol.14(5):2827-2840.

[12]RabinerLR.ATutorialonHiddenMarkovModelsandSelectedApplicationsinSpeechRecognition[J].ProceedingsoftheIEEE,1989,Vol.77(2):257-286.

[13]姜維.混合自動請求重傳技術的性能研究[D].濟南：山東大學，2008.

WEIJiang.HARQTechnologythePerformanceStudy[D].Jinan:ShandongUniversity,2008.

AHybridAutomaticRepeatRequestAlgorithmbasedonPrediction

ZHANGQiang1,YANBin1,YANGWei2,ZHOUHui2

(1.SchoolofAutomationEngineering,UniversityofElectronicScienceandTechnologyofChina,ChengduSichuan611731,China;2.SichuanElectricPowerCompany,ChengduSichuan610000,China)

Abstract：In order to solve the problem of transmission validity and reliability with the influence factors including multipath effect,jitter effect and fading,a hybrid automatic repeat request algorithm based on prediction is proposed.By using the hidden Markov model to predict the packet-loss rate of the next time during the transfer process,and in accordance with the ratio of packet-loss rate at different times,the redundancy in Reed-Solomon codes is tuned.Simulation results indicate that compared with the traditional type-Ⅰhybrid automatic repeat request algorithm and the type-Ⅱhybrid automatic repeat request algorithm,the proposed algorithm could significantly reduce the number of retransmission times,and the bit error rate,and remarkably raise the communication reliability.Key words：wireless transmission;hybrid automatic repeat request algorithm;hidden Markov model;predicting

doi:10.3969/j.issn.1002-0802.2016.05.007

* 收稿日期：2015-12-20；修回日期：2016-04-05Received date:2015-12-20；Revised date：2016-04-05

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1002-0802(2016)05-0544-05

作者簡介：

張強(1990—)，男，碩士研究生，主要研究方向為無線傳輸；

閆斌(1974—)，男，博士，講師，主要研究方向為無線傳感器網(wǎng)絡；

楊蔚(1978—)，男，學士，工程師，主要研究方向為物聯(lián)網(wǎng)技術與智能電網(wǎng)應用；

周輝(1985—)，男，學士，助理工程師，主要研究方向為物聯(lián)網(wǎng)技術與智能電網(wǎng)應用。