洪放 呂洪杰

摘要：本文介紹了RFID標簽防碰撞算法，確定了一種改進的鎖位—八叉樹搜索算法，該算法實現(xiàn)了消除空閑時隙、避免了查詢?nèi)哂?，大幅度提高系統(tǒng)吞吐率和識別性能，減少識別時延。結果表明這種改進算法提高了結算的速率，節(jié)省了成本。

關鍵詞：物聯(lián)網(wǎng);RFID;防碰撞算法;無人超市

隨著物聯(lián)網(wǎng)技術在智慧化城市各領域的廣泛應用。RFID技術被大量使用在無人超市中，當多個標簽同時向閱讀器發(fā)送請求時，閱讀器出現(xiàn)誤判或是失效結論，這就是碰撞問題。它嚴重影響了物聯(lián)網(wǎng)系統(tǒng)正常運轉。因此多標簽碰撞問題是無人超市結賬系統(tǒng)中亟待解決的問題。

1 防碰撞簡介

射頻識別RFID始于1973年，用以取代傳統(tǒng)條形碼的使用，它通過非接觸式電磁感應實現(xiàn)電子標簽和讀寫器之間的信息交互，完成標簽信息的傳遞。在這個RFID環(huán)境中，數(shù)以百計的顧客可能被放置在同一區(qū)域通過掃描大量的標簽以達到所需的覆蓋范圍。這種密集的網(wǎng)絡表現(xiàn)出大量的碰撞。這種碰撞導致數(shù)據(jù)收集吞吐量降低，增加識別延遲和網(wǎng)絡效率下降。RFID系統(tǒng)中碰撞問題分為兩種，標簽碰撞和閱讀器碰撞。

2 防碰撞算法

防碰撞算法分為非確定性防碰撞算法和確定性防碰撞算法，非確定性防碰撞算法具有低復雜度，工程容易實現(xiàn)等優(yōu)點;但是存在標簽餓死的情況。而確定性防碰撞算法識別率高，算法穩(wěn)定且不存在標簽餓死等現(xiàn)象，因此對于無人超市這類安全性要求較高的系統(tǒng)，大都采用確定性算法。

2.1 鎖位后退式二進制樹搜索算法

鎖位后退式二進制樹搜索算法在成功識別出第一個標簽后，閱讀器不需要重新發(fā)送Request命令，而是直接鎖位分組退回到上一層繼續(xù)搜索，也就是返回到根節(jié)點，這就會降低搜索查詢的次數(shù)。

Step1：閱讀器像識別范圍發(fā)送Request（11111111）命令，范圍內(nèi)標簽接到指令后將自身ID發(fā)送給閱讀器。

Step2：將標簽的ID與命令比較，如果發(fā)生碰撞，就用曼徹斯特編碼分析，按碰撞位的具體情況修改命令，將最高位置“0”，其余為設置為“1”，這樣就得到了新的Request命令，因此能減少數(shù)據(jù)位冗余，從而減少傳輸量。

Step3：根據(jù)新生成的命令序列號，成功限制了一些標簽應答，如果還發(fā)生碰撞，則重復第二步，直到選出下一個標簽。

Step4：讀寫出選中的標簽后，閱讀器發(fā)送UNselect命令，則該標簽不再響應。然后后退，從根節(jié)點讀取下一個序列號。循環(huán)執(zhí)行，一直到成功識別出所有標簽。

鎖位后退式二進制樹搜索算法極大地減少了問詢次數(shù)，提高了系統(tǒng)搜索效率。但是該算法并不像DBS算法那樣能夠減少每次識別所需傳輸量。鎖位后退式二進制樹搜索算法實現(xiàn)過程見表1。

2.2 一種改進的鎖位-八叉樹搜索算法

改進的鎖位-八叉樹搜索算法是在確定碰撞序列后，采用每三位為一組識別無空閑時隙的搜索方式，結合碰撞前綴和堆棧的使用，來達到降低查詢次數(shù)，減少傳輸?shù)臄?shù)據(jù)量和時延，提高了系統(tǒng)的整體性能。具體操作步驟：

Step1：發(fā)送指令，判斷碰撞。

閱讀器發(fā)送長度與標簽ID號位數(shù)相同的Request（11111..1）指令，收到該命令后所有標簽向閱讀器返回自身ID，且同步回復。如果無標簽響應，則閱讀器再次發(fā)送此指令等待;若只一個標簽響應，則立即與該標簽通信，讀寫相關信息，并在通信結束后令其靜默，不再參與后續(xù)識別過程;如果發(fā)生碰撞，則閱讀器可知有多個標簽在其閱讀范圍內(nèi)。

Step2：發(fā)生碰撞，發(fā)送鎖位與碰撞前綴預測指令。

閱讀器發(fā)現(xiàn)碰撞后，發(fā)送鎖位與碰撞前綴預測指令，即Request（0101…001，111）指令，其中第一部分為根據(jù)每輪碰撞標簽回復序列的清況，并將所有發(fā)生碰撞的比特位置1，未發(fā)生碰撞的比特位置0，形成的查詢指令，這樣當標簽接收到此命令后即可將本輪識別中的碰撞位提取出來，在以后的防碰撞識別過程中均使用這個純碰撞位序列來進行后續(xù)的識別，以減少傳輸過程中的數(shù)據(jù)量（每輪碰撞后均是這樣操作，將進一步減少傳輸數(shù)據(jù)量）;在第一次碰撞后發(fā)送的此命令的第一部分長度為標簽ID長度L，之后其長度為每輪標簽回復序列的長度。第二部分為3位1，即為碰撞前綴預測命令，其作用為令標簽返回本輪確定的碰撞序列的最高3位碰撞位，當標簽收到此命令后，會將本輪確定出的碰撞序列的最高3位序列進行二一十進制轉換后向閱讀器發(fā)送，其發(fā)送規(guī)則采用之前所述的碰撞前綴預測規(guī)則，所有在此輪識別中發(fā)生碰撞的標簽均如此回復。

Step3：判斷碰撞前3位。

閱讀器在收到所有返回信號后，即可判斷出此輪發(fā)生碰撞的所有標簽的前3位碰撞情況，因此確定出來的碰撞前綴即為存在的碰撞標簽前綴，然后將此確定出來的碰撞前綴壓入碰撞堆棧中保存。

Step4：取出棧首進行依次查詢。

閱讀器依次從碰撞堆棧中取出棧首的碰撞前綴進行查詢，若僅有一個標簽響應，即表明無碰撞發(fā)生，則此標簽被閱讀器成功識別，讀寫其相關信息，在與其通信結束后，發(fā)送Unselect指令令其靜默，使其不再參與后續(xù)的標簽識別過程;若仍有碰撞發(fā)生，則轉至Step2，繼續(xù)發(fā)送鎖位與碰撞前綴預測指令，繼續(xù)在此3位碰撞位之后的碰撞序列基礎上確定新的碰撞序列，進行下一輪的3位碰撞位識別過程，若剩余的碰撞序列位數(shù)不足3位，則標簽自動補充0至3位再向閱讀器發(fā)送。如此操作，直至將此碰撞前綴分支中的標簽全部識別出。

Step5：繼續(xù)取棧首前綴查詢，直至堆棧為空。

閱讀器在識別完一個碰撞前綴下的所有標簽后，會繼續(xù)從碰撞堆棧中取出棧首前綴來進行此碰撞前綴分支下的標簽查詢，如此進行下去，直至將堆棧中的碰撞前綴均查詢完，即碰撞堆棧為空后，則表示己將閱讀器閱讀范圍內(nèi)的所有標簽識別完畢，算法結束。

設在閱讀器工作范圍內(nèi)存在四個標簽，分別為Tag1（ID：10001100）;Tag2（ID：10101010）;Tag3（ID：10101100）;Tag4（ID：10001110）。

閱讀器首先發(fā)送Request（11111111） 指令，四個標簽在接收到此命令后，均響應閱讀器向其發(fā)送自身ID。閱讀器經(jīng)曼徹斯特譯碼后發(fā)現(xiàn)碰撞，譯碼結果為10x01xx0，即在第1， 2， 5位發(fā)生碰撞，于是發(fā)送鎖位與碰撞前綴預測指令Request（00100110， 111），鎖定標簽碰撞序列并進行碰撞前綴預測。

閱讀器端接收到的信號譯碼結果為000xx00x，即第0，3，4位發(fā)生碰撞，將碰撞位的位置信息進行相反過程的十一二進制轉換后，得到000，011， 100，即為確定存在的碰撞前綴，將其壓入碰撞堆棧中保存。在后續(xù)的識別中，閱讀器依次從碰撞堆棧中取出棧首前綴查詢，再需四次查詢即可將此四個標簽識別出來。

通過以上的改進，使得這種改進的鎖位-八叉樹搜索算法在大規(guī)模標簽識別范圍內(nèi)，有效降低碰撞時隙，減少傳輸數(shù)據(jù)量，提高了系統(tǒng)吞吐率和整體識讀性能，本改進算法的與原來的鎖位后退算法的查詢次數(shù)比減少了16.5%，系統(tǒng)吞吐率提高了10%，傳輸數(shù)據(jù)量減少47%，提高了識別性能。適合應用到無人超市中。

3 結語

本文針對鎖位后退式二進制樹搜索算法在應用到大規(guī)模標簽時所需傳輸能量大、碰撞時詢問次數(shù)過多的問題，提出了一種新的改進的鎖位-八叉樹搜索算法。這種算法在確定碰撞序列后，采用每三位為一組識別無空閑時隙的搜索方式，結合碰撞前綴和堆棧的使用，來達到降低查詢次數(shù)，減少傳輸?shù)臄?shù)據(jù)量和時延，提高了系統(tǒng)的整體性能的目的。

參考文獻：

[1] 尹鵬，吳連軍，張望泉.物聯(lián)網(wǎng)在生活當中的應用[J].中國戰(zhàn)略新興產(chǎn)業(yè)，2018（06）.

[2] 吳宏偉，李釗，沈雪.基于物聯(lián)網(wǎng)技術的智能超市系統(tǒng)的開發(fā)與研究[J].福建電腦，2017（02）.

[3] 李堯.基于Zigbee的電子標簽系統(tǒng)的設計與實現(xiàn)[J].電子設計工程，2016（02）.

[4] 吳必造，楊曉嬌.RFID中的不確定性標簽防碰撞算法簡介[J].微型機與應用，2017（06）.

[5] ?Wang H， Xiao S， Lin F， et al. Group improved enhanced dynamic frame slotted ALOHA anti-collision algorithm[J].The Journal of ?Supercomputing，2014（03）.

[6] Duan L，Wang Z J，Duan F.An optimal dynamic frame slot-segment algorithm[C].InProceedings of the 2015 Workshop on Mobile Big Data. ACM， 2015.

[7] 潘思丞，王慧琴，張小紅.靜態(tài)環(huán)境中分組ALOHA防碰撞算法研究[[J].計算機工程與應用，2016（20）.

（作者單位：阜新市第一中等職業(yè)技術專業(yè)學校）