自適應(yīng)動(dòng)態(tài)時(shí)隙ALOHA防碰撞算法的研究

宋依青,高正中,盛惠興

（1.常州工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213002;2.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 常州 213022;3.江蘇省輸配電裝備技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 常州 213022）

無線射頻識(shí)別技術(shù)RFID(Radio Frequency Identification)是利用射頻信號(hào)和空間耦合(電感或電磁耦合)傳輸特性自動(dòng)識(shí)別目標(biāo)物體的技術(shù)。RFID系統(tǒng)由電子應(yīng)答器和閱讀器組成，閱讀器負(fù)責(zé)發(fā)送廣播并接收標(biāo)簽的標(biāo)識(shí)信息；應(yīng)答器收到廣播命令后將自身標(biāo)識(shí)信息發(fā)送給閱讀器[1]。但在RFID系統(tǒng)工作時(shí)，可能會(huì)有一個(gè)以上的應(yīng)答器同時(shí)處在閱讀器的作用范圍內(nèi)。如果有兩個(gè)或兩個(gè)以上的應(yīng)答器同時(shí)發(fā)送數(shù)據(jù)，則會(huì)出現(xiàn)通信沖突，產(chǎn)生傳輸數(shù)據(jù)相互干擾、發(fā)生碰撞。在RFID系統(tǒng)中，一般采用時(shí)分多址TDMA(Time Division Multiple Access)的方法來解決碰撞問題，這是一種把整個(gè)可供使用的通路容量按時(shí)間分配給多個(gè)用戶的技術(shù)[2]。目前現(xiàn)有的防碰撞算法可以分為基于ALOHA機(jī)制算法和基于二進(jìn)制退避機(jī)制算法。本文提出一種改進(jìn)的自適應(yīng)幀時(shí)隙ALOHA防碰撞算法，以進(jìn)一步提高系統(tǒng)的識(shí)別效率。

1 關(guān)鍵問題解析

通常在幀時(shí)隙ALOHA防碰撞算法中，當(dāng)應(yīng)答器的數(shù)量變得很大時(shí)，系統(tǒng)效率開始降低。由數(shù)學(xué)分析可知,在一個(gè)時(shí)隙中發(fā)生碰撞的概率滿足二項(xiàng)式分布[3,4]：

因此，在一個(gè)讀周期中估計(jì)能正常傳輸數(shù)據(jù)的應(yīng)答器為：

式中,N為幀長度，n為沒有被讀到的應(yīng)答器，r為被讀取到的應(yīng)答器。

由此可以得到系統(tǒng)效率的計(jì)算公式[5-7]：

根據(jù)式(4)推導(dǎo)可知,當(dāng)幀長度為N時(shí)，達(dá)到系統(tǒng)效率最高的應(yīng)答器數(shù)量為：

當(dāng)應(yīng)答器數(shù)為n時(shí)，最佳幀長度為：

當(dāng)n很大時(shí)，式(6)可以根據(jù)泰勒級(jí)數(shù)化簡得到：

根據(jù)推導(dǎo)結(jié)果得到一個(gè)重要的結(jié)論:當(dāng)應(yīng)答器的數(shù)量和幀長度大體相當(dāng)時(shí)，系統(tǒng)效率將達(dá)到最大化。

2 算法流程

時(shí)隙是指應(yīng)答器與閱讀器進(jìn)行數(shù)據(jù)交互的一小段時(shí)間，如果在一個(gè)時(shí)隙中只有唯一的一個(gè)應(yīng)答器與閱讀器進(jìn)行通信，則稱為唯一時(shí)隙；如果在一個(gè)時(shí)隙中沒有應(yīng)答器與閱讀器進(jìn)行通信，則稱為空時(shí)隙；如果在一個(gè)時(shí)隙中有兩個(gè)或兩個(gè)以上應(yīng)答器與閱讀器進(jìn)行通信，則稱為碰撞時(shí)隙。閱讀器完成一輪完整的識(shí)別過程稱為一個(gè)圈周期，圈周期等于唯一時(shí)隙、空時(shí)隙和碰撞時(shí)隙時(shí)間之和[8]。圖1為改進(jìn)的自適應(yīng)幀時(shí)隙ALOHA防碰撞算法流程圖。

在電子應(yīng)答器進(jìn)入閱讀器射頻作用范圍內(nèi)之后，閱讀器先通過預(yù)設(shè)定的幀長度進(jìn)行時(shí)隙分配。當(dāng)判斷當(dāng)前

圖1 改進(jìn)的自適應(yīng)幀時(shí)隙ALOHA防碰撞算法流程圖

防碰撞算法的兩個(gè)關(guān)鍵問題是：(1)精確地計(jì)算出與閱讀器作用范圍內(nèi)的電子標(biāo)簽的數(shù)量；(2)根據(jù)電子標(biāo)簽的數(shù)量合理調(diào)整幀長時(shí)隙為空時(shí)隙時(shí)，即該時(shí)隙沒有應(yīng)答器應(yīng)答則空時(shí)隙計(jì)數(shù)器C碰加1，立即結(jié)束該時(shí)隙；當(dāng)判斷當(dāng)前時(shí)隙為碰撞時(shí)隙時(shí)，即該時(shí)隙內(nèi)有多個(gè)應(yīng)答器要傳輸數(shù)據(jù)則碰撞時(shí)隙計(jì)數(shù)器C空加1，立即結(jié)束該時(shí)隙；當(dāng)判斷當(dāng)前時(shí)隙為唯一時(shí)隙時(shí)，即該時(shí)隙內(nèi)只有一個(gè)應(yīng)答器要傳輸數(shù)據(jù)，閱讀器讀取應(yīng)答器內(nèi)數(shù)據(jù)并存儲(chǔ)該應(yīng)答器ID號(hào)，發(fā)送一個(gè)已讀信號(hào)給應(yīng)答器，當(dāng)下一圈周期詢問到該應(yīng)答器時(shí)，該應(yīng)答器不再響應(yīng)也不再要求發(fā)送數(shù)據(jù)給閱讀器，已讀信號(hào)將在應(yīng)答器離開射頻作用場(chǎng)后消失。當(dāng)圈周期結(jié)束后，通過空時(shí)隙和碰撞時(shí)隙計(jì)數(shù)值估計(jì)射頻作用場(chǎng)內(nèi)的應(yīng)答器數(shù)量并調(diào)整幀長度。

3 算法仿真及結(jié)果分析

在改進(jìn)的自適應(yīng)幀時(shí)隙ALOHA防碰撞算法仿真算法中，采用了128固定時(shí)隙、256固定時(shí)隙以及圈周期估計(jì)法與本文算法進(jìn)行了橫向?qū)Ρ?，結(jié)果如圖2所示。由圖可以看到，128固定時(shí)隙法在應(yīng)答器數(shù)量達(dá)到300時(shí)曲線折線明顯，碰撞概率開始增加，系統(tǒng)效率下降顯著；256固定時(shí)隙法效果同樣不好。很明顯由于圈周期估計(jì)法和本文算法都采用的是動(dòng)態(tài)時(shí)隙調(diào)整所以效果明顯好于固定時(shí)隙方法。但是圈周期估計(jì)法，在圈周期期間無論發(fā)生怎樣的碰撞都必須執(zhí)行完周期操作，系統(tǒng)資源浪費(fèi)嚴(yán)重。本文算法使系統(tǒng)吞吐率達(dá)到了約42.5%，大大提高了系統(tǒng)吞吐率。度。本文提出的自適應(yīng)動(dòng)態(tài)時(shí)隙ALOHA防碰撞算法能夠很好地兼顧以上兩點(diǎn)，利用實(shí)時(shí)調(diào)整幀長度，使得射頻作用場(chǎng)內(nèi)的應(yīng)答器數(shù)與時(shí)隙數(shù)能達(dá)到最佳匹配，來提高時(shí)隙分配效率和系統(tǒng)效率。

圖2 改進(jìn)的自適應(yīng)幀時(shí)隙ALOHA防碰撞算法仿真圖

[1]FINKENZELLER K.射頻識(shí)別(RFID)技 術(shù)(第二版)[M].北京:電子工業(yè)出版社,2001.

[2]單承贛，單玉峰，姚磊等編著.射頻識(shí)別(RFID)原理與應(yīng)用[M].北京:電子工業(yè)出版社,2008.

[3]皮揚(yáng)，劉長江.動(dòng)態(tài)分配時(shí)隙ALOHA的抗碰撞算法[J].計(jì)算機(jī)工程，2009(4):270-272.

[4]吳偉貞.RFID系統(tǒng)的防沖突算法設(shè)計(jì)及其實(shí)現(xiàn)方法研究[D].廈門：廈門大學(xué),2008.

[5]陳濤.基于RFID的防沖突算法的設(shè)計(jì)與實(shí)現(xiàn)[D].武漢：武漢理工大學(xué),2009.

[6]王中祥.基于時(shí)隙ALOHA的RFID多標(biāo)簽防碰撞算法的研究與實(shí)現(xiàn)[D].上海：復(fù)旦大學(xué),2009.

[7]孟淑玲.射頻識(shí)別系統(tǒng)中防沖突算法的研究[D].天津：天津大學(xué),2009.

[8]李瑾.無線射頻識(shí)別(RFID)防碰撞算法的研究和仿真[D].北京：北京交通大學(xué),2007.