RFID系統(tǒng)中的一種改進的自適應多叉樹標簽防碰撞算法研究

郭榮

摘 要

針對AMSA算法存在的不足，本文提出了IAMSA算法。并通過性能與仿真分析，驗證了IAMSA算法能夠有效地減少空閑時隙，提高檢測速度。

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

1 引言

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

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

2 IAMSA算法

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

3 性能分析

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

假設從o到k層的四叉樹都沒有去除空閑時隙，可以得出

T4-ary= （1）

當采用二叉數(shù)進行搜索是，可以得出

T2-ary = （2）

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

下面，將分別計算四叉樹中的碰撞時隙T4-coll與空閑時隙T4-idle。

假設有m個待識別的標簽，在四叉樹的第l層的任意k個標簽選中同一個節(jié)點響應的概率為：

（3）

其中，p=4-L，這是因為完全四叉樹的第l層有個4L節(jié)點，所以選擇任意一個節(jié)點的概率為4-L。

空閑概率為

（4）

成功識別概率為

（5）

碰撞概率為

（6）

令qLi/m表示第L層的第i個節(jié)點被搜索到的概率。當L=0時，根節(jié)點總是能被訪問到，即q0i/m=q00/m=1。對于其它的節(jié)點，只有其父節(jié)點產生了碰撞，其才能被訪問到，因此

qLi/m=qL/m= （7）

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

（8）

而 等于所有的 之和，因此

（9）

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

（10）

空閑時隙為

（11）

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

， （12）

其中，

（13）

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

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

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

參考文獻

[1]丁治國，古今.自適應多叉樹防碰撞算法研究[J].自動化學報，2010，36（2）：237-241.

作者單位

卡斯柯信號有限公司 上海市 200070endprint

摘 要

針對AMSA算法存在的不足，本文提出了IAMSA算法。并通過性能與仿真分析，驗證了IAMSA算法能夠有效地減少空閑時隙，提高檢測速度。

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

1 引言

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

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

2 IAMSA算法

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

3 性能分析

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

假設從o到k層的四叉樹都沒有去除空閑時隙，可以得出

T4-ary= （1）

當采用二叉數(shù)進行搜索是，可以得出

T2-ary = （2）

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

下面，將分別計算四叉樹中的碰撞時隙T4-coll與空閑時隙T4-idle。

假設有m個待識別的標簽，在四叉樹的第l層的任意k個標簽選中同一個節(jié)點響應的概率為：

（3）

其中，p=4-L，這是因為完全四叉樹的第l層有個4L節(jié)點，所以選擇任意一個節(jié)點的概率為4-L。

空閑概率為

（4）

成功識別概率為

（5）

碰撞概率為

（6）

令qLi/m表示第L層的第i個節(jié)點被搜索到的概率。當L=0時，根節(jié)點總是能被訪問到，即q0i/m=q00/m=1。對于其它的節(jié)點，只有其父節(jié)點產生了碰撞，其才能被訪問到，因此

qLi/m=qL/m= （7）

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

（8）

而 等于所有的 之和，因此

（9）

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

（10）

空閑時隙為

（11）

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

， （12）

其中，

（13）

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

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

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

參考文獻

[1]丁治國，古今.自適應多叉樹防碰撞算法研究[J].自動化學報，2010，36（2）：237-241.

作者單位

卡斯柯信號有限公司 上海市 200070endprint

摘 要

針對AMSA算法存在的不足，本文提出了IAMSA算法。并通過性能與仿真分析，驗證了IAMSA算法能夠有效地減少空閑時隙，提高檢測速度。

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

1 引言

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

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

2 IAMSA算法

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

3 性能分析

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

假設從o到k層的四叉樹都沒有去除空閑時隙，可以得出

T4-ary= （1）

當采用二叉數(shù)進行搜索是，可以得出

T2-ary = （2）

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

下面，將分別計算四叉樹中的碰撞時隙T4-coll與空閑時隙T4-idle。

假設有m個待識別的標簽，在四叉樹的第l層的任意k個標簽選中同一個節(jié)點響應的概率為：

（3）

其中，p=4-L，這是因為完全四叉樹的第l層有個4L節(jié)點，所以選擇任意一個節(jié)點的概率為4-L。

空閑概率為

（4）

成功識別概率為

（5）

碰撞概率為

（6）

令qLi/m表示第L層的第i個節(jié)點被搜索到的概率。當L=0時，根節(jié)點總是能被訪問到，即q0i/m=q00/m=1。對于其它的節(jié)點，只有其父節(jié)點產生了碰撞，其才能被訪問到，因此

qLi/m=qL/m= （7）

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

（8）

而 等于所有的 之和，因此

（9）

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

（10）

空閑時隙為

（11）

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

， （12）

其中，

（13）

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

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

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

參考文獻

[1]丁治國，古今.自適應多叉樹防碰撞算法研究[J].自動化學報，2010，36（2）：237-241.

作者單位

卡斯柯信號有限公司 上海市 200070endprint