一種改進(jìn)的鎖位-八叉樹搜索算法

洪放 呂洪杰

摘要：本文介紹了RFID標(biāo)簽防碰撞算法，確定了一種改進(jìn)的鎖位—八叉樹搜索算法，該算法實(shí)現(xiàn)了消除空閑時隙、避免了查詢?nèi)哂啵蠓忍岣呦到y(tǒng)吞吐率和識別性能，減少識別時延。結(jié)果表明這種改進(jìn)算法提高了結(jié)算的速率，節(jié)省了成本。

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

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

1 防碰撞簡介

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

2 防碰撞算法

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

2.1 鎖位后退式二進(jìn)制樹搜索算法

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

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

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

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

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

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

2.2 一種改進(jìn)的鎖位-八叉樹搜索算法

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

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

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

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

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

Step3：判斷碰撞前3位。

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

Step4：取出棧首進(jìn)行依次查詢。

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

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

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

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

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

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

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

3 結(jié)語

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

參考文獻(xiàn)：

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

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

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

[4] 吳必造，楊曉嬌.RFID中的不確定性標(biāo)簽防碰撞算法簡介[J].微型機(jī)與應(yīng)用，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].計(jì)算機(jī)工程與應(yīng)用，2016（20）.

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