宋 磊，杜 彬

(山西職業(yè)技術(shù)學(xué)院, 山西 太原 030006)

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展與普及，各類智能家居應(yīng)用系統(tǒng)也逐漸被大眾所認(rèn)可并廣泛普及。RFID技術(shù)作為智能家居系統(tǒng)中實(shí)現(xiàn)對(duì)各類進(jìn)行物品自動(dòng)識(shí)別的關(guān)鍵技術(shù)，具備了標(biāo)簽信息容量大(最高為4GBit)、識(shí)別率高(準(zhǔn)確率>98%)、信號(hào)穿透性好以及數(shù)據(jù)可讀寫(xiě)等優(yōu)勢(shì)[1]。但在實(shí)際應(yīng)用場(chǎng)景中，由于受控設(shè)備數(shù)量增加而引發(fā)的標(biāo)簽檢測(cè)沖突會(huì)導(dǎo)致RFID系統(tǒng)性能和處理速度發(fā)生嚴(yán)重下降進(jìn)而造成物聯(lián)網(wǎng)系統(tǒng)的響應(yīng)遲緩。因此研究更高效的標(biāo)簽防碰撞算法對(duì)RFID技術(shù)的應(yīng)用與發(fā)展具有重要的意義。

1 RTID工作原理與標(biāo)簽碰撞現(xiàn)象

RFID技術(shù)的原理為：嵌入了電子芯片的標(biāo)簽(Tag)在寫(xiě)入數(shù)據(jù)后被部署在不同的物體上等待接收由閱讀器(Reader)發(fā)送的射頻信號(hào)，在接收到信號(hào)后標(biāo)簽被激活并向閱讀器反饋信息；閱讀器對(duì)信息進(jìn)行譯碼并將數(shù)據(jù)上傳至智能家居系統(tǒng)核心模塊(當(dāng)前以Raspberry Pi為主)，核心模塊中的程序根據(jù)數(shù)據(jù)內(nèi)容進(jìn)行判斷并向系統(tǒng)中的各執(zhí)行模塊發(fā)出相應(yīng)的控制指令。

由于受到體積與功率的限制，單一閱讀器的信號(hào)強(qiáng)度和覆蓋范圍有限。因此智能家居系統(tǒng)中往往會(huì)部署多個(gè)閱讀器以實(shí)現(xiàn)對(duì)全部標(biāo)簽的數(shù)據(jù)訪問(wèn)，而RFID系統(tǒng)的碰撞問(wèn)題也由此被引發(fā)。碰撞現(xiàn)象如圖1所示。

圖1 RFID系統(tǒng)的碰撞現(xiàn)象

當(dāng)出現(xiàn)圖1(a)中所描述的某個(gè)標(biāo)簽同時(shí)處于多個(gè)閱讀器作用域內(nèi)，同時(shí)收到它們的訪問(wèn)請(qǐng)求時(shí)，就會(huì)發(fā)送數(shù)據(jù)訪問(wèn)沖突。當(dāng)出現(xiàn)圖1(b)中所述的多個(gè)標(biāo)簽同時(shí)向某個(gè)閱讀器發(fā)送數(shù)據(jù)時(shí)，也會(huì)引發(fā)沖突。

2 智能家居環(huán)境下的標(biāo)簽識(shí)別特點(diǎn)

在智能家居的應(yīng)用場(chǎng)景中，需要識(shí)別的物品數(shù)量多、體積大小不一，并且分布在不同的房間、角落里，墻壁與大體積物品的遮擋會(huì)導(dǎo)致射頻信號(hào)的傳輸受到很大影響，因而單一閱讀器的有效作用域變得非常有限，系統(tǒng)中需要部署多個(gè)閱讀器設(shè)備才能夠正常運(yùn)行。同時(shí)，在系統(tǒng)實(shí)際運(yùn)行過(guò)程中還會(huì)遇到物品的擺放位置經(jīng)常被移動(dòng)的情況。這些特點(diǎn)使閱讀器與標(biāo)簽的作用范圍出現(xiàn)重復(fù)的情況增加，進(jìn)而導(dǎo)致發(fā)生標(biāo)簽碰撞沖突的概率明顯增加，嚴(yán)重影響智能家居系統(tǒng)的運(yùn)行效率。

3 RFID防碰撞算法的改進(jìn)

3.1 經(jīng)典RFID防碰撞算法的基本思路與局限

在經(jīng)典的RFID防碰撞算法中，采用了類似建立二叉樹(shù)模型并進(jìn)行遍歷的模式來(lái)進(jìn)行處理，其具體過(guò)程為：將需要處理的所有碰撞標(biāo)簽劃分為標(biāo)簽子集0與標(biāo)簽子集1，首先檢索標(biāo)簽子集0中的各個(gè)標(biāo)簽，如果無(wú)沖突現(xiàn)象存在，即完成識(shí)別；否則，就繼續(xù)將標(biāo)簽子集0劃分為子集00和子集01，并繼續(xù)檢索序號(hào)較小的00子集的內(nèi)容；若碰撞依舊存在，則將劃分過(guò)程繼續(xù)下去，當(dāng)子集0中的全部標(biāo)簽識(shí)都被正確識(shí)別之后，再對(duì)子集1的內(nèi)容進(jìn)行同樣的劃分與檢索[2]。

該算法的局限在于，當(dāng)存在大于兩位的標(biāo)簽碰撞的情況時(shí)，當(dāng)首次檢索到所有碰撞位后，并未對(duì)信息進(jìn)行預(yù)處理，從而導(dǎo)致信息傳輸產(chǎn)生嚴(yán)重的冗余；而對(duì)于兩個(gè)標(biāo)簽只出現(xiàn)一位碰撞的情況，也未做優(yōu)化處理以進(jìn)一步提高程序的運(yùn)行效率。

3.2 二進(jìn)制防碰撞算法改進(jìn)

本文針對(duì)經(jīng)典RFID防碰撞算法的不足，設(shè)計(jì)了基于信息預(yù)處理的防碰撞改進(jìn)算法，其基本原理是在標(biāo)簽分組處理時(shí)先僅對(duì)沖突位進(jìn)行識(shí)別，獲取到當(dāng)前標(biāo)簽集合中的全部沖突位來(lái)組成新的ID，然后基于獲取到的新ID來(lái)與閱讀器通信并創(chuàng)建相應(yīng)的二叉樹(shù)，并遵循后續(xù)訪問(wèn)原則對(duì)標(biāo)簽的信息進(jìn)行處理。算法流程說(shuō)明如下：

步驟一：閱讀器發(fā)送全1指令獲取所有標(biāo)簽的序列號(hào)信息，并檢測(cè)到當(dāng)前的全部沖突位?；跊_突位設(shè)置為1、未沖突則為0的原則，創(chuàng)建一組用于記錄碰撞位置的二進(jìn)制序列，并將此序列重新發(fā)送給全體標(biāo)簽。

步驟二：標(biāo)簽獲取到記錄碰撞位置的二進(jìn)制序列后，將其與自身ID對(duì)比后，獲取碰撞位組成一個(gè)新的標(biāo)簽ID用于和閱讀器之間通信。

步驟三：構(gòu)造二叉樹(shù)，并以當(dāng)前結(jié)點(diǎn)為根，左葉子結(jié)點(diǎn)為0，右葉子結(jié)點(diǎn)為1。

步驟四：閱讀器檢測(cè)左葉子節(jié)點(diǎn)是否存在沖突，如未檢測(cè)到則對(duì)標(biāo)簽內(nèi)容進(jìn)行識(shí)別并轉(zhuǎn)向步驟六；若檢測(cè)到兩個(gè)標(biāo)簽僅存在一個(gè)碰撞位時(shí)，對(duì)它們同時(shí)進(jìn)行識(shí)別并轉(zhuǎn)向步驟六；若它們的碰撞位超過(guò)兩位時(shí)，則轉(zhuǎn)向步驟五。

步驟五：繼續(xù)創(chuàng)建二叉樹(shù)，根節(jié)點(diǎn)即為當(dāng)前節(jié)點(diǎn)，左葉子節(jié)點(diǎn)以最高碰撞位左側(cè)內(nèi)容+0構(gòu)成；右葉子結(jié)點(diǎn)由最高碰撞位左側(cè)內(nèi)容+ 1+相鄰碰撞位之間無(wú)碰撞數(shù)據(jù)構(gòu)成，二叉樹(shù)構(gòu)成完成后轉(zhuǎn)向步驟四。

步驟六：閱讀器檢測(cè)右葉子節(jié)點(diǎn)是否存在沖突，若未檢測(cè)到碰撞沖突則對(duì)標(biāo)簽內(nèi)容進(jìn)行識(shí)別；若檢測(cè)到兩個(gè)標(biāo)簽僅存在一個(gè)碰撞位時(shí)，對(duì)它們同時(shí)進(jìn)行識(shí)別；若它們的碰撞位超過(guò)兩位時(shí)，則轉(zhuǎn)向步驟五。

3.3 算法運(yùn)行示例

假設(shè)某閱讀器的識(shí)別范圍涵蓋了4個(gè)標(biāo)簽，其編碼內(nèi)容如表1所示。

表1閱讀器的內(nèi)容編碼表

算法運(yùn)行過(guò)程說(shuō)明如下：

1) 閱讀器向所有標(biāo)簽發(fā)送全1命令(8位均為1)，各標(biāo)簽響應(yīng)后，獲取到的結(jié)果為10XXXX11，獲取到各個(gè)碰撞位，并生成4個(gè)新的標(biāo)簽。

2) 閱讀器與4個(gè)新標(biāo)簽通信并創(chuàng)建二叉樹(shù)，以0作為左葉子節(jié)點(diǎn)，1作為右葉子節(jié)點(diǎn)，根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。

3) 閱讀器對(duì)左葉子節(jié)點(diǎn)(A1、B1)進(jìn)行碰撞沖突檢測(cè)，ID從高位開(kāi)始與參數(shù)0進(jìn)行比較，獲取結(jié)果為0X1X，由于發(fā)生2位以上的碰撞，則以當(dāng)前節(jié)點(diǎn)為根來(lái)構(gòu)建二叉樹(shù)，左葉子節(jié)點(diǎn)為最高碰撞位左側(cè)內(nèi)容+0，即00；右葉子節(jié)點(diǎn)為最高碰撞位左側(cè)內(nèi)容+1+相鄰碰撞為中間的正常數(shù)據(jù)，即011。

4) 閱讀器對(duì)左葉子節(jié)點(diǎn)進(jìn)行碰撞沖突檢測(cè)，ID從高位開(kāi)始與參數(shù)00進(jìn)行比較，獲取結(jié)果為0010，未檢測(cè)到碰撞，則直接識(shí)別標(biāo)簽A1的內(nèi)容。

5) 閱讀器繼續(xù)對(duì)右葉子節(jié)點(diǎn)進(jìn)行碰撞沖突檢測(cè)，ID從高位開(kāi)始與參數(shù)011進(jìn)行比較，獲取結(jié)果為0111，未檢測(cè)到碰撞，則直接識(shí)別標(biāo)簽A2的內(nèi)容。

6) 閱讀器對(duì)C1、D1進(jìn)行碰撞沖突檢測(cè)，ID從高位開(kāi)始與參數(shù)1進(jìn)行比較，譯碼結(jié)果為110X，即僅發(fā)生了一位碰撞，為提升執(zhí)行效率，僅需要將兩個(gè)標(biāo)簽的第三位數(shù)據(jù)設(shè)置為0、1，即可完成對(duì)標(biāo)簽的碰撞位的處理。進(jìn)而閱讀器即可完成對(duì)標(biāo)簽C1、D1的識(shí)別操作。

至此，4個(gè)標(biāo)簽的識(shí)別操作全部完成，在實(shí)際應(yīng)用場(chǎng)景中，閱讀器檢測(cè)范圍內(nèi)的標(biāo)簽的數(shù)量與ID位數(shù)都多于本示例，因此根據(jù)該算法創(chuàng)建的二叉樹(shù)層級(jí)也會(huì)相應(yīng)的增加，該算法的效率優(yōu)勢(shì)也會(huì)體現(xiàn)的更加明顯。

4 結(jié)論

本文針對(duì)現(xiàn)有RFID系統(tǒng)中常用的經(jīng)典碰撞檢測(cè)算法中存在的問(wèn)題，設(shè)計(jì)了一種基于信息預(yù)處理的防碰撞改進(jìn)算法。經(jīng)過(guò)對(duì)算法流程的分析與典型示例的模擬可以證明，本文提出的算法在有效提升標(biāo)簽識(shí)別效率的同時(shí)，還大幅降低了通信過(guò)程中的冗余信息。為有效解決RFID系統(tǒng)中的標(biāo)簽碰撞現(xiàn)象提供了有效的解決方案。

[1] 敖志剛.智能家庭網(wǎng)絡(luò)及其控制技術(shù)[M].北京:人民郵電出版社,2013.

[2] 郭愛(ài)煌.移動(dòng)RFID技術(shù)應(yīng)用與設(shè)計(jì)[J].現(xiàn)代電子技術(shù),2014(15):15-17.