郭榮

摘 要

針對(duì)AMSA算法存在的不足，本文提出了IAMSA算法。并通過(guò)性能與仿真分析，驗(yàn)證了IAMSA算法能夠有效地減少空閑時(shí)隙，提高檢測(cè)速度。

【關(guān)鍵詞】物聯(lián)網(wǎng) RFID 多叉樹(shù) 防碰撞算法

1 引言

在RFID系統(tǒng)中，閱讀器利用標(biāo)簽防碰撞算法來(lái)實(shí)現(xiàn)覆蓋范圍內(nèi)的多個(gè)電子產(chǎn)品標(biāo)簽的讀取。而基于樹(shù)的防碰撞算法被廣泛地采用。但是多數(shù)基于樹(shù)的算法并沒(méi)有充分利用碰撞信息，僅僅使用了前幾位的信息。通常情況下，分支內(nèi)標(biāo)簽數(shù)越多，碰撞的位數(shù)也將會(huì)越多，那么在總比特位中，碰撞位占的比例就越大。在識(shí)別的過(guò)程中，根據(jù)碰撞比例，如果能夠自適應(yīng)地選擇使用幾叉樹(shù)，就能夠提升算法的效率，減少系統(tǒng)用時(shí)。AMSA（Adaptive Multi-tree Search Anti-collision，自適應(yīng)多叉樹(shù)防碰撞）算法就是基于這一原則。

雖然AMSA算法根據(jù)根據(jù)碰撞因子u并不能推斷出當(dāng)前碰撞節(jié)點(diǎn)下有多少標(biāo)簽。為了解決這個(gè)問(wèn)題，本文提出了一種改進(jìn)的自適應(yīng)多叉防碰撞（簡(jiǎn)稱IAMSA）算法。

2 IAMSA算法

IAMSA算法的工作流程如下：（1）閱讀器對(duì)查詢前綴棧進(jìn)行初始化即清空棧，并發(fā)送ε指令；（2）每個(gè)標(biāo)簽與此時(shí)閱讀器發(fā)出的查詢前綴相比較，只有相同的標(biāo)簽才作出響應(yīng)；（3）如果此時(shí)作出響應(yīng)的標(biāo)簽數(shù)為一時(shí)，則識(shí)別成功，轉(zhuǎn)到第六步；如果此時(shí)沒(méi)有標(biāo)簽響應(yīng)，那么就不需要繼續(xù)對(duì)該分支進(jìn)行搜索，轉(zhuǎn)到第六步；而如果有多個(gè)標(biāo)簽作出了響應(yīng)，則發(fā)生碰撞；（4）閱讀器計(jì)算碰撞因子u。如果u<0.75，使用二叉樹(shù)，接著依據(jù)碰撞比特的首位信息，確定兩個(gè)新的查詢前綴；如果u≥0.75，使用四叉樹(shù)，閱讀器發(fā)送查詢碰撞位最高兩位前綴的指令，而標(biāo)簽則反饋一個(gè)含有碰撞位信息的四位碼給閱讀器，那么閱讀器將根據(jù)反饋判斷已存在于系統(tǒng)中的前綴；（5）新產(chǎn)生的前綴入棧，棧首前綴被取出并發(fā)給標(biāo)簽，接著轉(zhuǎn)到第二步；（6）前綴堆棧如果不為空，棧首前綴被取出并發(fā)給標(biāo)簽，接著轉(zhuǎn)到第二步，如果為空，識(shí)別過(guò)程結(jié)束。

3 性能分析

假設(shè)有m個(gè)待識(shí)別的標(biāo)簽，并且當(dāng)搜索深度為k時(shí)，每個(gè)子節(jié)點(diǎn)上的平均標(biāo)簽數(shù)為3，那么，當(dāng)搜索深度小于k時(shí)，使用無(wú)空閑時(shí)隙的四叉樹(shù)，否則采用二叉樹(shù)。k=。

假設(shè)從o到k層的四叉樹(shù)都沒(méi)有去除空閑時(shí)隙，可以得出

T4-ary= （1）

當(dāng)采用二叉數(shù)進(jìn)行搜索是，可以得出

T2-ary = （2）

雖然IAMSA算法使用了無(wú)空閑時(shí)隙的四叉樹(shù)，但是當(dāng)碰撞被閱讀器檢測(cè)到后，其第二次發(fā)送指令仍然需要占用一個(gè)時(shí)隙，而這個(gè)指令所使用的時(shí)隙數(shù)Tcomm與碰撞時(shí)隙數(shù)T4-coll相等。

下面，將分別計(jì)算四叉樹(shù)中的碰撞時(shí)隙T4-coll與空閑時(shí)隙T4-idle。

假設(shè)有m個(gè)待識(shí)別的標(biāo)簽，在四叉樹(shù)的第l層的任意k個(gè)標(biāo)簽選中同一個(gè)節(jié)點(diǎn)響應(yīng)的概率為：

（3）

其中，p=4-L，這是因?yàn)橥耆牟鏄?shù)的第l層有個(gè)4L節(jié)點(diǎn)，所以選擇任意一個(gè)節(jié)點(diǎn)的概率為4-L。

空閑概率為

（4）

成功識(shí)別概率為

（5）

碰撞概率為

（6）

令qLi/m表示第L層的第i個(gè)節(jié)點(diǎn)被搜索到的概率。當(dāng)L=0時(shí)，根節(jié)點(diǎn)總是能被訪問(wèn)到，即q0i/m=q00/m=1。對(duì)于其它的節(jié)點(diǎn)，只有其父節(jié)點(diǎn)產(chǎn)生了碰撞，其才能被訪問(wèn)到，因此

qLi/m=qL/m= （7）

其中βLi/m表示第L層的第i個(gè)節(jié)點(diǎn)發(fā)生碰撞的概率。如果同層中的節(jié)點(diǎn)發(fā)生碰撞的概率是一樣的，那么

（8）

而 等于所有的 之和，因此

（9）

平均碰撞總時(shí)隙數(shù)等于所有βLi/m之和，即

（10）

空閑時(shí)隙為

（11）

根據(jù)IAMSA算法的工作流程，當(dāng)子節(jié)點(diǎn)上的平均標(biāo)簽數(shù)為3時(shí)，使用二叉樹(shù)進(jìn)行搜索，即原四叉樹(shù)的最后一層的搜索改用二叉樹(shù)，那么四叉樹(shù)中的碰撞時(shí)隙數(shù)與空閑時(shí)隙數(shù)就不包含最后一層里可能出現(xiàn)的碰撞與空閑時(shí)隙數(shù)。

， （12）

其中，

（13）

那么，使用IAMSA算法成功地識(shí)別m個(gè)標(biāo)簽所需的總時(shí)隙數(shù)

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

總時(shí)隙數(shù)隨標(biāo)簽總數(shù)的變化情況，隨著標(biāo)簽總數(shù)的增加，IAMSA算法所需的時(shí)隙數(shù)增加是最慢的，并且當(dāng)標(biāo)簽總數(shù)達(dá)到1000時(shí)，與IAMSA算法相比，無(wú)空閑時(shí)隙4叉樹(shù)算法需要的時(shí)間是其1.47倍，AMSA算法需要的時(shí)間是其1.17倍。由于IAMSA算法需要的時(shí)隙數(shù)最少，那么其識(shí)別標(biāo)簽的速率也是最快的。此外，AMSA算法與IAMSA算法的仿真曲線是跳躍式的。這是因?yàn)锳MSA算法與IAMSA算法都能夠自適應(yīng)地調(diào)整搜索叉數(shù)，根據(jù)公式（14）可知，T（m）的值跟搜索深度 有關(guān)，由于k是非負(fù)整數(shù)（當(dāng)m≤11時(shí)，k=0；當(dāng)12≤m≤47時(shí)，k=1；當(dāng)48≤m≤191時(shí)，k=2；……），那么 的值也是非連續(xù)變化的整數(shù)，因此，AMSA算法與IAMSA算法的仿真曲線是跳躍式的。

參考文獻(xiàn)

[1]丁治國(guó)，古今.自適應(yīng)多叉樹(shù)防碰撞算法研究[J].自動(dòng)化學(xué)報(bào)，2010，36（2）：237-241.

作者單位

卡斯柯信號(hào)有限公司 上海市 200070endprint

摘 要

針對(duì)AMSA算法存在的不足，本文提出了IAMSA算法。并通過(guò)性能與仿真分析，驗(yàn)證了IAMSA算法能夠有效地減少空閑時(shí)隙，提高檢測(cè)速度。

【關(guān)鍵詞】物聯(lián)網(wǎng) RFID 多叉樹(shù) 防碰撞算法

1 引言

在RFID系統(tǒng)中，閱讀器利用標(biāo)簽防碰撞算法來(lái)實(shí)現(xiàn)覆蓋范圍內(nèi)的多個(gè)電子產(chǎn)品標(biāo)簽的讀取。而基于樹(shù)的防碰撞算法被廣泛地采用。但是多數(shù)基于樹(shù)的算法并沒(méi)有充分利用碰撞信息，僅僅使用了前幾位的信息。通常情況下，分支內(nèi)標(biāo)簽數(shù)越多，碰撞的位數(shù)也將會(huì)越多，那么在總比特位中，碰撞位占的比例就越大。在識(shí)別的過(guò)程中，根據(jù)碰撞比例，如果能夠自適應(yīng)地選擇使用幾叉樹(shù)，就能夠提升算法的效率，減少系統(tǒng)用時(shí)。AMSA（Adaptive Multi-tree Search Anti-collision，自適應(yīng)多叉樹(shù)防碰撞）算法就是基于這一原則。

雖然AMSA算法根據(jù)根據(jù)碰撞因子u并不能推斷出當(dāng)前碰撞節(jié)點(diǎn)下有多少標(biāo)簽。為了解決這個(gè)問(wèn)題，本文提出了一種改進(jìn)的自適應(yīng)多叉防碰撞（簡(jiǎn)稱IAMSA）算法。

2 IAMSA算法

IAMSA算法的工作流程如下：（1）閱讀器對(duì)查詢前綴棧進(jìn)行初始化即清空棧，并發(fā)送ε指令；（2）每個(gè)標(biāo)簽與此時(shí)閱讀器發(fā)出的查詢前綴相比較，只有相同的標(biāo)簽才作出響應(yīng)；（3）如果此時(shí)作出響應(yīng)的標(biāo)簽數(shù)為一時(shí)，則識(shí)別成功，轉(zhuǎn)到第六步；如果此時(shí)沒(méi)有標(biāo)簽響應(yīng)，那么就不需要繼續(xù)對(duì)該分支進(jìn)行搜索，轉(zhuǎn)到第六步；而如果有多個(gè)標(biāo)簽作出了響應(yīng)，則發(fā)生碰撞；（4）閱讀器計(jì)算碰撞因子u。如果u<0.75，使用二叉樹(shù)，接著依據(jù)碰撞比特的首位信息，確定兩個(gè)新的查詢前綴；如果u≥0.75，使用四叉樹(shù)，閱讀器發(fā)送查詢碰撞位最高兩位前綴的指令，而標(biāo)簽則反饋一個(gè)含有碰撞位信息的四位碼給閱讀器，那么閱讀器將根據(jù)反饋判斷已存在于系統(tǒng)中的前綴；（5）新產(chǎn)生的前綴入棧，棧首前綴被取出并發(fā)給標(biāo)簽，接著轉(zhuǎn)到第二步；（6）前綴堆棧如果不為空，棧首前綴被取出并發(fā)給標(biāo)簽，接著轉(zhuǎn)到第二步，如果為空，識(shí)別過(guò)程結(jié)束。

3 性能分析

假設(shè)有m個(gè)待識(shí)別的標(biāo)簽，并且當(dāng)搜索深度為k時(shí)，每個(gè)子節(jié)點(diǎn)上的平均標(biāo)簽數(shù)為3，那么，當(dāng)搜索深度小于k時(shí)，使用無(wú)空閑時(shí)隙的四叉樹(shù)，否則采用二叉樹(shù)。k=。

假設(shè)從o到k層的四叉樹(shù)都沒(méi)有去除空閑時(shí)隙，可以得出

T4-ary= （1）

當(dāng)采用二叉數(shù)進(jìn)行搜索是，可以得出

T2-ary = （2）

雖然IAMSA算法使用了無(wú)空閑時(shí)隙的四叉樹(shù)，但是當(dāng)碰撞被閱讀器檢測(cè)到后，其第二次發(fā)送指令仍然需要占用一個(gè)時(shí)隙，而這個(gè)指令所使用的時(shí)隙數(shù)Tcomm與碰撞時(shí)隙數(shù)T4-coll相等。

下面，將分別計(jì)算四叉樹(shù)中的碰撞時(shí)隙T4-coll與空閑時(shí)隙T4-idle。

假設(shè)有m個(gè)待識(shí)別的標(biāo)簽，在四叉樹(shù)的第l層的任意k個(gè)標(biāo)簽選中同一個(gè)節(jié)點(diǎn)響應(yīng)的概率為：

（3）

其中，p=4-L，這是因?yàn)橥耆牟鏄?shù)的第l層有個(gè)4L節(jié)點(diǎn)，所以選擇任意一個(gè)節(jié)點(diǎn)的概率為4-L。

空閑概率為

（4）

成功識(shí)別概率為

（5）

碰撞概率為

（6）

令qLi/m表示第L層的第i個(gè)節(jié)點(diǎn)被搜索到的概率。當(dāng)L=0時(shí)，根節(jié)點(diǎn)總是能被訪問(wèn)到，即q0i/m=q00/m=1。對(duì)于其它的節(jié)點(diǎn)，只有其父節(jié)點(diǎn)產(chǎn)生了碰撞，其才能被訪問(wèn)到，因此

qLi/m=qL/m= （7）

其中βLi/m表示第L層的第i個(gè)節(jié)點(diǎn)發(fā)生碰撞的概率。如果同層中的節(jié)點(diǎn)發(fā)生碰撞的概率是一樣的，那么

（8）

而 等于所有的 之和，因此

（9）

平均碰撞總時(shí)隙數(shù)等于所有βLi/m之和，即

（10）

空閑時(shí)隙為

（11）

根據(jù)IAMSA算法的工作流程，當(dāng)子節(jié)點(diǎn)上的平均標(biāo)簽數(shù)為3時(shí)，使用二叉樹(shù)進(jìn)行搜索，即原四叉樹(shù)的最后一層的搜索改用二叉樹(shù)，那么四叉樹(shù)中的碰撞時(shí)隙數(shù)與空閑時(shí)隙數(shù)就不包含最后一層里可能出現(xiàn)的碰撞與空閑時(shí)隙數(shù)。

， （12）

其中，

（13）

那么，使用IAMSA算法成功地識(shí)別m個(gè)標(biāo)簽所需的總時(shí)隙數(shù)

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

總時(shí)隙數(shù)隨標(biāo)簽總數(shù)的變化情況，隨著標(biāo)簽總數(shù)的增加，IAMSA算法所需的時(shí)隙數(shù)增加是最慢的，并且當(dāng)標(biāo)簽總數(shù)達(dá)到1000時(shí)，與IAMSA算法相比，無(wú)空閑時(shí)隙4叉樹(shù)算法需要的時(shí)間是其1.47倍，AMSA算法需要的時(shí)間是其1.17倍。由于IAMSA算法需要的時(shí)隙數(shù)最少，那么其識(shí)別標(biāo)簽的速率也是最快的。此外，AMSA算法與IAMSA算法的仿真曲線是跳躍式的。這是因?yàn)锳MSA算法與IAMSA算法都能夠自適應(yīng)地調(diào)整搜索叉數(shù)，根據(jù)公式（14）可知，T（m）的值跟搜索深度 有關(guān)，由于k是非負(fù)整數(shù)（當(dāng)m≤11時(shí)，k=0；當(dāng)12≤m≤47時(shí)，k=1；當(dāng)48≤m≤191時(shí)，k=2；……），那么 的值也是非連續(xù)變化的整數(shù)，因此，AMSA算法與IAMSA算法的仿真曲線是跳躍式的。

參考文獻(xiàn)

[1]丁治國(guó)，古今.自適應(yīng)多叉樹(shù)防碰撞算法研究[J].自動(dòng)化學(xué)報(bào)，2010，36（2）：237-241.

作者單位

卡斯柯信號(hào)有限公司 上海市 200070endprint

摘 要

針對(duì)AMSA算法存在的不足，本文提出了IAMSA算法。并通過(guò)性能與仿真分析，驗(yàn)證了IAMSA算法能夠有效地減少空閑時(shí)隙，提高檢測(cè)速度。

【關(guān)鍵詞】物聯(lián)網(wǎng) RFID 多叉樹(shù) 防碰撞算法

1 引言

在RFID系統(tǒng)中，閱讀器利用標(biāo)簽防碰撞算法來(lái)實(shí)現(xiàn)覆蓋范圍內(nèi)的多個(gè)電子產(chǎn)品標(biāo)簽的讀取。而基于樹(shù)的防碰撞算法被廣泛地采用。但是多數(shù)基于樹(shù)的算法并沒(méi)有充分利用碰撞信息，僅僅使用了前幾位的信息。通常情況下，分支內(nèi)標(biāo)簽數(shù)越多，碰撞的位數(shù)也將會(huì)越多，那么在總比特位中，碰撞位占的比例就越大。在識(shí)別的過(guò)程中，根據(jù)碰撞比例，如果能夠自適應(yīng)地選擇使用幾叉樹(shù)，就能夠提升算法的效率，減少系統(tǒng)用時(shí)。AMSA（Adaptive Multi-tree Search Anti-collision，自適應(yīng)多叉樹(shù)防碰撞）算法就是基于這一原則。

雖然AMSA算法根據(jù)根據(jù)碰撞因子u并不能推斷出當(dāng)前碰撞節(jié)點(diǎn)下有多少標(biāo)簽。為了解決這個(gè)問(wèn)題，本文提出了一種改進(jìn)的自適應(yīng)多叉防碰撞（簡(jiǎn)稱IAMSA）算法。

2 IAMSA算法

IAMSA算法的工作流程如下：（1）閱讀器對(duì)查詢前綴棧進(jìn)行初始化即清空棧，并發(fā)送ε指令；（2）每個(gè)標(biāo)簽與此時(shí)閱讀器發(fā)出的查詢前綴相比較，只有相同的標(biāo)簽才作出響應(yīng)；（3）如果此時(shí)作出響應(yīng)的標(biāo)簽數(shù)為一時(shí)，則識(shí)別成功，轉(zhuǎn)到第六步；如果此時(shí)沒(méi)有標(biāo)簽響應(yīng)，那么就不需要繼續(xù)對(duì)該分支進(jìn)行搜索，轉(zhuǎn)到第六步；而如果有多個(gè)標(biāo)簽作出了響應(yīng)，則發(fā)生碰撞；（4）閱讀器計(jì)算碰撞因子u。如果u<0.75，使用二叉樹(shù)，接著依據(jù)碰撞比特的首位信息，確定兩個(gè)新的查詢前綴；如果u≥0.75，使用四叉樹(shù)，閱讀器發(fā)送查詢碰撞位最高兩位前綴的指令，而標(biāo)簽則反饋一個(gè)含有碰撞位信息的四位碼給閱讀器，那么閱讀器將根據(jù)反饋判斷已存在于系統(tǒng)中的前綴；（5）新產(chǎn)生的前綴入棧，棧首前綴被取出并發(fā)給標(biāo)簽，接著轉(zhuǎn)到第二步；（6）前綴堆棧如果不為空，棧首前綴被取出并發(fā)給標(biāo)簽，接著轉(zhuǎn)到第二步，如果為空，識(shí)別過(guò)程結(jié)束。

3 性能分析

假設(shè)有m個(gè)待識(shí)別的標(biāo)簽，并且當(dāng)搜索深度為k時(shí)，每個(gè)子節(jié)點(diǎn)上的平均標(biāo)簽數(shù)為3，那么，當(dāng)搜索深度小于k時(shí)，使用無(wú)空閑時(shí)隙的四叉樹(shù)，否則采用二叉樹(shù)。k=。

假設(shè)從o到k層的四叉樹(shù)都沒(méi)有去除空閑時(shí)隙，可以得出

T4-ary= （1）

當(dāng)采用二叉數(shù)進(jìn)行搜索是，可以得出

T2-ary = （2）

雖然IAMSA算法使用了無(wú)空閑時(shí)隙的四叉樹(shù)，但是當(dāng)碰撞被閱讀器檢測(cè)到后，其第二次發(fā)送指令仍然需要占用一個(gè)時(shí)隙，而這個(gè)指令所使用的時(shí)隙數(shù)Tcomm與碰撞時(shí)隙數(shù)T4-coll相等。

下面，將分別計(jì)算四叉樹(shù)中的碰撞時(shí)隙T4-coll與空閑時(shí)隙T4-idle。

假設(shè)有m個(gè)待識(shí)別的標(biāo)簽，在四叉樹(shù)的第l層的任意k個(gè)標(biāo)簽選中同一個(gè)節(jié)點(diǎn)響應(yīng)的概率為：

（3）

其中，p=4-L，這是因?yàn)橥耆牟鏄?shù)的第l層有個(gè)4L節(jié)點(diǎn)，所以選擇任意一個(gè)節(jié)點(diǎn)的概率為4-L。

空閑概率為

（4）

成功識(shí)別概率為

（5）

碰撞概率為

（6）

令qLi/m表示第L層的第i個(gè)節(jié)點(diǎn)被搜索到的概率。當(dāng)L=0時(shí)，根節(jié)點(diǎn)總是能被訪問(wèn)到，即q0i/m=q00/m=1。對(duì)于其它的節(jié)點(diǎn)，只有其父節(jié)點(diǎn)產(chǎn)生了碰撞，其才能被訪問(wèn)到，因此

qLi/m=qL/m= （7）

其中βLi/m表示第L層的第i個(gè)節(jié)點(diǎn)發(fā)生碰撞的概率。如果同層中的節(jié)點(diǎn)發(fā)生碰撞的概率是一樣的，那么

（8）

而 等于所有的 之和，因此

（9）

平均碰撞總時(shí)隙數(shù)等于所有βLi/m之和，即

（10）

空閑時(shí)隙為

（11）

根據(jù)IAMSA算法的工作流程，當(dāng)子節(jié)點(diǎn)上的平均標(biāo)簽數(shù)為3時(shí)，使用二叉樹(shù)進(jìn)行搜索，即原四叉樹(shù)的最后一層的搜索改用二叉樹(shù)，那么四叉樹(shù)中的碰撞時(shí)隙數(shù)與空閑時(shí)隙數(shù)就不包含最后一層里可能出現(xiàn)的碰撞與空閑時(shí)隙數(shù)。

， （12）

其中，

（13）

那么，使用IAMSA算法成功地識(shí)別m個(gè)標(biāo)簽所需的總時(shí)隙數(shù)

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

總時(shí)隙數(shù)隨標(biāo)簽總數(shù)的變化情況，隨著標(biāo)簽總數(shù)的增加，IAMSA算法所需的時(shí)隙數(shù)增加是最慢的，并且當(dāng)標(biāo)簽總數(shù)達(dá)到1000時(shí)，與IAMSA算法相比，無(wú)空閑時(shí)隙4叉樹(shù)算法需要的時(shí)間是其1.47倍，AMSA算法需要的時(shí)間是其1.17倍。由于IAMSA算法需要的時(shí)隙數(shù)最少，那么其識(shí)別標(biāo)簽的速率也是最快的。此外，AMSA算法與IAMSA算法的仿真曲線是跳躍式的。這是因?yàn)锳MSA算法與IAMSA算法都能夠自適應(yīng)地調(diào)整搜索叉數(shù)，根據(jù)公式（14）可知，T（m）的值跟搜索深度 有關(guān)，由于k是非負(fù)整數(shù)（當(dāng)m≤11時(shí)，k=0；當(dāng)12≤m≤47時(shí)，k=1；當(dāng)48≤m≤191時(shí)，k=2；……），那么 的值也是非連續(xù)變化的整數(shù)，因此，AMSA算法與IAMSA算法的仿真曲線是跳躍式的。

參考文獻(xiàn)

[1]丁治國(guó)，古今.自適應(yīng)多叉樹(shù)防碰撞算法研究[J].自動(dòng)化學(xué)報(bào)，2010，36（2）：237-241.

作者單位

卡斯柯信號(hào)有限公司 上海市 200070endprint