基于WSN的CRC算法的改進與實現(xiàn)

李冠楠 李強

（順德職業(yè)技術(shù)學(xué)院 電子與信息工程系，廣東 順德 528300）

1.CRC算法介紹

CRC校驗采用多項式編碼方法。利用生成多項式為k個數(shù)據(jù)位產(chǎn)生r個校驗位進行編碼，其編碼長度為n=k+r，所以又稱為（n，k）碼。其編碼格式如下：

1.1 編碼規(guī)則[1]

設(shè)有k個數(shù)據(jù)位，需要添加r個校驗位，n=k+r，其編碼規(guī)則如下：

用W(x)=W W…W表示k個數(shù)據(jù)位，把W(x)左移r位，即相當(dāng)于W(x)×2，給校驗位空出r位來；

給定一個r階的多項式E(x)，可以求出一個校驗位表達式F(x)。E(x)稱為該循環(huán)碼的生成多項式。即如下表達式：

根據(jù)上面公式可知，用W(x)去除生成多項式G(x)，商為H(x)，余數(shù)則為R(x)。據(jù)此可得：

在CRC編碼過程中，四則運算采用模2運算，即不考慮借位和進位。所以有：

M(x)+R(x)即為所求n位CRC碼，它應(yīng)是生成多項式G(x)的倍式，即可以被G(x)整除。

校驗數(shù)據(jù)時用數(shù)據(jù)的n位CRC編碼去除G(x)，若余數(shù)為0則說明數(shù)據(jù)正確，否則根據(jù)余數(shù)的值即可查出差錯位。

1.2 生成多項式特點

生成多項式應(yīng)滿足以下條件：

（1）任何一位發(fā)生錯誤，W(x)×2+R(x)即CRC碼除以G(x)的余數(shù)不能為0；

（2）余數(shù)繼續(xù)作模2除，應(yīng)使余數(shù)循環(huán)；

（3）若要能糾正一位錯，則不同的碼位錯不能有相同的余數(shù)，且當(dāng)給定生成多項式后，余數(shù)與出錯位之間的對應(yīng)關(guān)系應(yīng)保持不變，與編碼無關(guān)。

1.3 原算法實現(xiàn)[2]

/*以CRC-CCITT為例，按位計算CRC算法實現(xiàn)，不使用額外空間*/

從上述代碼可知，直接基于問題的描述和所涉及的概念出發(fā)，利用按位計算CRC，雖然代碼簡單（也可采用模擬硬件電路按位操作加以實現(xiàn)），所占用的內(nèi)存比較少，但其最大的缺點就是一位一位地計算會占用很多的處理器處理時間，尤其在高速通訊的場合，這個缺點更是不可容忍，因而實現(xiàn)對它的改進具有理論和實際的意義。

2.CRC算法改進

2.1 快速算法基本思想[3]

CRC常用的生成多項式如 CRC-16、CRC-CCITT和CRC-32，由它們產(chǎn)生的校驗碼字節(jié)數(shù)均為整數(shù)個字節(jié)。而單片機的操作是以字節(jié)形式進行的，所以，算法應(yīng)以字節(jié)為單位進行運算。顯然，單片機的數(shù)據(jù)序列、校驗序列都是字節(jié)序列。實際上，這種算法所要解決的問題就是如何對多字節(jié)序列進行除法取余式運算的問題，從而達到時空的權(quán)衡。

2.2 多字節(jié)序列運算規(guī)律

設(shè)一個由i個字節(jié)構(gòu)成的字節(jié)序列Wi=[w1w2……wi-1wi]，取其前i-1個字節(jié)構(gòu)成一個新的序列Wi-1=[w1w2……wi-2wi-1]，則兩個序列之間的關(guān)系可以用多項式表示為Wi(x)=x8Wi-1(x)+mi(x)。

其中，mi(x)表示mi的二進制多項式形式，x8Wi-1(x)表示將Wi-1左移一個字節(jié)。

對于序列Wi-1來說，

其中令二字節(jié)序列余數(shù)Ri-1=[hi-1li-1]

而對于序列Wi來說，可得

因此，對x8Ri-1（x）+wi(x)取余式運算就等價于對Wi(x)的取余式運算，即

其中，x8Ri-1（x）+wi(x)表示一個由Ri-1和mi共同組成的三字節(jié)序列[hi-1li-1wi]，故對它取余式運算就等于對Mi序列的取余式運算，其結(jié)果就是Mi序列的余式Ri=[hili]。故以此類推便可得到最終結(jié)果。

2.3 變字節(jié)序列的計算

為了時空的權(quán)衡我們在此引入了查表的思想，對于三字節(jié)序列如果事先計算出一字節(jié)即0x00至0xFF之間的所有的余式并匯制成表，這樣就減少了時間開銷且只需占用512個字節(jié)空間。

設(shè)三字節(jié)序列Tabc=[abc]、Ta00=[a00]和二字節(jié)序列Tbc=[bc]。用多項式表示為Tabc(x)=Ta00(x)+Tbc(x)。

對于序列Ta00來說，

而對于序列Tabc來說，可得

其中，Ra00和Tbc都是二字節(jié)序列，因此Ra00(x)+Tbc（x）仍然是二字節(jié)序列，它是Tabc的余數(shù)Rabc，即

故三字節(jié)序列Tabc可分解為兩個步驟進行計算：

通過查表，獲取Ta00=[a00]的余式Ra00=[ha00la00]

計算 Rabc=[habclabc]，其中 habc=ha00⊕b，labc=la00⊕c

很顯然，對于三字節(jié)序列只需建立一字節(jié)即0x00到0xFF的余式表，即按字節(jié)求CRC的思想，由于采用了查表法，大大提高了計算速度。但對于廣泛運用的8位微處理器，代碼空間有限，對于要求256個CRC余式表（共512字節(jié)的內(nèi)存）已經(jīng)顯得捉襟見肘了，但CRC的計算速度又不可以太慢，故同理我們可以引入按半字節(jié)計算CRC的算法。

3.改進算法實現(xiàn)

在以上CRC原算法和改進算法的基礎(chǔ)上，本文采用C51編碼實現(xiàn)了CRC改進型數(shù)據(jù)校驗算法，并對各改進方案進行了效率分析。

經(jīng)過上述分析，無論是按字節(jié)還是半字節(jié)來計算CRC都采用了一種遞推的思想。一種由小及大，利用一個問題給定實例的解和同樣問題較小實例的解之間的關(guān)系建立起原問題的解。這一算法是基于遞推運算的規(guī)律，并且每一次遞推運算都是對一個三字節(jié)序列的計算（如圖1所示）。

圖1 三字節(jié)序列[abc]計算流程

4.算法效率分析

一個新算法的提出或改進是為了追求更高的效率，而對一個算法好壞的衡量除了最起碼的正確性、易理解性外，其占用的存儲空間和運算時間也是重要的標(biāo)準。下面給出了以上三種計算CRC算法在相同條件、相同問題規(guī)模下的實驗數(shù)據(jù)。以下為相關(guān)說明：

（1）按位計算

—按位計算CRC算法（b_CRC）

— 執(zhí)行時間（b_CRC_t）：-ms

—額外空間：0Byte（恒定）

（2）按字節(jié)計算

—按字節(jié)計算CRC算法（B_CRC）

— 執(zhí)行時間（B_CRC_t）：-ms

—額外空間：512Byte（恒定）

（3）按半字節(jié)計算

—按半字節(jié)計算CRC算法（HB_CRC）

— 執(zhí)行時間（HB_CRC_t）：-ms

—額外空間：32Byte（恒定）

表1列出了三種計算CRC算法的對比（對應(yīng)圖2）。

表1 三種計算CRC算法對比表

圖2 CRC算法效率分析

通過對改進算法的編碼實現(xiàn)，并在大量調(diào)試、統(tǒng)計和比較的基礎(chǔ)上，我們可以得出以下結(jié)論：以上介紹的三種求CRC的程序，按位求法速度較慢，但占用最小的內(nèi)存空間；按字節(jié)查表求CRC的方法速度較快，但占用較大的內(nèi)存；按半字節(jié)查表求CRC的方法是前兩者的均衡，即不會占用太多的內(nèi)存，同時速度又不至于太慢，比較適合8位小內(nèi)存的單片機的應(yīng)用場合。

可見，以上幾種算法從按位計算CRC的思想出發(fā)，并結(jié)合模2運算規(guī)則，在蠻力法的基礎(chǔ)上提出了按字節(jié)、半字節(jié)計算CRC的改進策略，也就是從減治和時空權(quán)衡的角度進行問題的詮釋，以一種空間換時間的思想實現(xiàn)了對原問題的快速、高效求解，從而滿足無線MESH網(wǎng)絡(luò)內(nèi)節(jié)點的通信要求。

[1]王春森.程序員教程[M].北京：清華大學(xué)出版社,2002：75-93.

[2]W.Ye,J.Heidemann,D.Estrin.An energy-efficient MAC protocol for wireless sensor networks[J].The 21st Int'l Annual Joint Conf.on the IEEE Computer and Communications Societies(INFOCOM 2002).New York,USA,2002：1-10.

[3]常曉明.CRC校驗及其軟件實現(xiàn)[J].電子技術(shù)應(yīng)用,1995(6)：67-71.