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

徐艷玲

摘 要：針對AMSA算法存在的不足，該章提出了IAMSA算法。仿真分析表明，該章所提出的IAMSA算法有效地較少空閑時隙，提高檢測速度以及系統吞吐率。

關鍵詞：物聯網 RFID 多叉樹 防碰撞算法

中圖分類號：TP3 文獻標識碼：A 文章編號：1674-098X（2014）10（b）-0042-01

在物聯網中，每個物品都需要一個唯一合法的身份以便用于物品的識別，RFID是其中的關鍵。RFID系統中的設備標簽是電子產品編碼，并且該編碼具有唯一性，其可以用來標識現實中的物體以實現物體的識別與區分。RFID系統中的閱讀器利用標簽防碰撞算法來實現覆蓋范圍內的多個電子產品標簽的讀取。而基于樹的防碰撞算法被廣泛地采用。但是多數基于樹的算法并沒有充分利用碰撞信息，僅僅使用了前幾位的信息。通常情況下，分支內標簽數越多，碰撞的位數也將會越多，那么在總比特位中，碰撞位占的比例就越大。如果在識別的過程中，根據碰撞比例，能夠自適應的選擇使用幾叉樹，就能夠提升算法的效率，減少系統用時。AMSA（Adaptive Multi-tree Search Anti-collision，自適應多叉樹防碰撞）算法就是基于這一原則[1]。

雖然AMSA算法根據碰撞因子動態地選取多叉樹，但是根據碰撞因子并不能推斷出當前碰撞節點下有多少標簽。為了解決這個問題，提出了一種改進的自適應多叉防碰撞（Improved AMSA，簡稱IAMSA）算法。IAMSA算法不僅能夠自適應地調整搜索樹的叉數，而且還優化了四叉樹的查詢前綴，使得空閑時隙數大大地減少。

1 IAMSA算法

IAMSA算法的工作流程如下：

（1）閱讀器對查詢前綴棧進行初始化即清空棧，并發送指令。

（2）每個標簽與此時閱讀器發出的查詢前綴相比較，只有相同的標簽才出響應。

（3）如果此時做出響應的標簽數為一時，則識別成功，轉到第六步；如果此時沒有標簽響應，那么就不需要繼續對該分支進行搜索，轉到第六步；而如果有多個標簽做出了響應，則發生碰撞。

（4）閱讀器計算碰撞因子。如果，使用二叉樹，接著依據碰撞比特的首位信息，確定兩個新的查詢前綴；如果≥0.75，使用四叉樹，閱讀器發送查詢碰撞位最高兩位前綴指令，而標簽則反饋一個含有碰撞位信息四位碼給閱讀器，那么閱讀器將根據反饋判斷已存在于系統中的前綴。

（5）新產生的前綴入棧，棧首前綴被取出并發給標簽，接著轉到第二步。

（6）前綴堆棧如果不為空，棧首前綴被取出并發給標簽，接著轉到第二步，如果為空，識別過程結束。將兩個有效的樣本進行交叉分析，得出的數據就是兩個樣本的交叉集合，對兩組數據進行分析比較，得出交叉以后的數據和兩組數據之間的聯系和不同，在不同的數據間進行交叉組合就會得出不一樣的數據，在這些不同的數據中進行數據的分析和整合，對不一樣的數據進行不同的分析，得出的結果然后再交叉分析然后得出最終結果。

2 性能分析

該文將從吞吐率與總時隙數來考察IAMSA算法的性能。從IAMSA算法的流程可以看出，其總時隙數為使用二叉樹與四叉樹兩部分所花時間之和。

如果有個待識別的標簽，并且當搜索深度為時，每個子節點上的平均標簽數為，那么，當搜索深度小于時，使用無空閑時隙的四叉樹，否則采用二叉樹。。

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

（1）

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

（2）

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

采用相似的分析方法，可以得到四叉樹中的碰撞時隙與空閑時隙分別為：

（3）

（4）

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

那么，使用算法成功地識別個標簽所需的總時隙數

（5）

3 仿真分析

下面將從總時隙數這個面來考察算法。

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

參考文獻

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

摘 要：針對AMSA算法存在的不足，該章提出了IAMSA算法。仿真分析表明，該章所提出的IAMSA算法有效地較少空閑時隙，提高檢測速度以及系統吞吐率。

關鍵詞：物聯網 RFID 多叉樹 防碰撞算法

中圖分類號：TP3 文獻標識碼：A 文章編號：1674-098X（2014）10（b）-0042-01

在物聯網中，每個物品都需要一個唯一合法的身份以便用于物品的識別，RFID是其中的關鍵。RFID系統中的設備標簽是電子產品編碼，并且該編碼具有唯一性，其可以用來標識現實中的物體以實現物體的識別與區分。RFID系統中的閱讀器利用標簽防碰撞算法來實現覆蓋范圍內的多個電子產品標簽的讀取。而基于樹的防碰撞算法被廣泛地采用。但是多數基于樹的算法并沒有充分利用碰撞信息，僅僅使用了前幾位的信息。通常情況下，分支內標簽數越多，碰撞的位數也將會越多，那么在總比特位中，碰撞位占的比例就越大。如果在識別的過程中，根據碰撞比例，能夠自適應的選擇使用幾叉樹，就能夠提升算法的效率，減少系統用時。AMSA（Adaptive Multi-tree Search Anti-collision，自適應多叉樹防碰撞）算法就是基于這一原則[1]。

雖然AMSA算法根據碰撞因子動態地選取多叉樹，但是根據碰撞因子并不能推斷出當前碰撞節點下有多少標簽。為了解決這個問題，提出了一種改進的自適應多叉防碰撞（Improved AMSA，簡稱IAMSA）算法。IAMSA算法不僅能夠自適應地調整搜索樹的叉數，而且還優化了四叉樹的查詢前綴，使得空閑時隙數大大地減少。

1 IAMSA算法

IAMSA算法的工作流程如下：

（1）閱讀器對查詢前綴棧進行初始化即清空棧，并發送指令。

（2）每個標簽與此時閱讀器發出的查詢前綴相比較，只有相同的標簽才出響應。

（3）如果此時做出響應的標簽數為一時，則識別成功，轉到第六步；如果此時沒有標簽響應，那么就不需要繼續對該分支進行搜索，轉到第六步；而如果有多個標簽做出了響應，則發生碰撞。

（4）閱讀器計算碰撞因子。如果，使用二叉樹，接著依據碰撞比特的首位信息，確定兩個新的查詢前綴；如果≥0.75，使用四叉樹，閱讀器發送查詢碰撞位最高兩位前綴指令，而標簽則反饋一個含有碰撞位信息四位碼給閱讀器，那么閱讀器將根據反饋判斷已存在于系統中的前綴。

（5）新產生的前綴入棧，棧首前綴被取出并發給標簽，接著轉到第二步。

（6）前綴堆棧如果不為空，棧首前綴被取出并發給標簽，接著轉到第二步，如果為空，識別過程結束。將兩個有效的樣本進行交叉分析，得出的數據就是兩個樣本的交叉集合，對兩組數據進行分析比較，得出交叉以后的數據和兩組數據之間的聯系和不同，在不同的數據間進行交叉組合就會得出不一樣的數據，在這些不同的數據中進行數據的分析和整合，對不一樣的數據進行不同的分析，得出的結果然后再交叉分析然后得出最終結果。

2 性能分析

該文將從吞吐率與總時隙數來考察IAMSA算法的性能。從IAMSA算法的流程可以看出，其總時隙數為使用二叉樹與四叉樹兩部分所花時間之和。

如果有個待識別的標簽，并且當搜索深度為時，每個子節點上的平均標簽數為，那么，當搜索深度小于時，使用無空閑時隙的四叉樹，否則采用二叉樹。。

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

（1）

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

（2）

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

采用相似的分析方法，可以得到四叉樹中的碰撞時隙與空閑時隙分別為：

（3）

（4）

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

那么，使用算法成功地識別個標簽所需的總時隙數

（5）

3 仿真分析

下面將從總時隙數這個面來考察算法。

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

參考文獻

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

摘 要：針對AMSA算法存在的不足，該章提出了IAMSA算法。仿真分析表明，該章所提出的IAMSA算法有效地較少空閑時隙，提高檢測速度以及系統吞吐率。

關鍵詞：物聯網 RFID 多叉樹 防碰撞算法

中圖分類號：TP3 文獻標識碼：A 文章編號：1674-098X（2014）10（b）-0042-01

在物聯網中，每個物品都需要一個唯一合法的身份以便用于物品的識別，RFID是其中的關鍵。RFID系統中的設備標簽是電子產品編碼，并且該編碼具有唯一性，其可以用來標識現實中的物體以實現物體的識別與區分。RFID系統中的閱讀器利用標簽防碰撞算法來實現覆蓋范圍內的多個電子產品標簽的讀取。而基于樹的防碰撞算法被廣泛地采用。但是多數基于樹的算法并沒有充分利用碰撞信息，僅僅使用了前幾位的信息。通常情況下，分支內標簽數越多，碰撞的位數也將會越多，那么在總比特位中，碰撞位占的比例就越大。如果在識別的過程中，根據碰撞比例，能夠自適應的選擇使用幾叉樹，就能夠提升算法的效率，減少系統用時。AMSA（Adaptive Multi-tree Search Anti-collision，自適應多叉樹防碰撞）算法就是基于這一原則[1]。

雖然AMSA算法根據碰撞因子動態地選取多叉樹，但是根據碰撞因子并不能推斷出當前碰撞節點下有多少標簽。為了解決這個問題，提出了一種改進的自適應多叉防碰撞（Improved AMSA，簡稱IAMSA）算法。IAMSA算法不僅能夠自適應地調整搜索樹的叉數，而且還優化了四叉樹的查詢前綴，使得空閑時隙數大大地減少。

1 IAMSA算法

IAMSA算法的工作流程如下：

（1）閱讀器對查詢前綴棧進行初始化即清空棧，并發送指令。

（2）每個標簽與此時閱讀器發出的查詢前綴相比較，只有相同的標簽才出響應。

（3）如果此時做出響應的標簽數為一時，則識別成功，轉到第六步；如果此時沒有標簽響應，那么就不需要繼續對該分支進行搜索，轉到第六步；而如果有多個標簽做出了響應，則發生碰撞。

（4）閱讀器計算碰撞因子。如果，使用二叉樹，接著依據碰撞比特的首位信息，確定兩個新的查詢前綴；如果≥0.75，使用四叉樹，閱讀器發送查詢碰撞位最高兩位前綴指令，而標簽則反饋一個含有碰撞位信息四位碼給閱讀器，那么閱讀器將根據反饋判斷已存在于系統中的前綴。

（5）新產生的前綴入棧，棧首前綴被取出并發給標簽，接著轉到第二步。

（6）前綴堆棧如果不為空，棧首前綴被取出并發給標簽，接著轉到第二步，如果為空，識別過程結束。將兩個有效的樣本進行交叉分析，得出的數據就是兩個樣本的交叉集合，對兩組數據進行分析比較，得出交叉以后的數據和兩組數據之間的聯系和不同，在不同的數據間進行交叉組合就會得出不一樣的數據，在這些不同的數據中進行數據的分析和整合，對不一樣的數據進行不同的分析，得出的結果然后再交叉分析然后得出最終結果。

2 性能分析

該文將從吞吐率與總時隙數來考察IAMSA算法的性能。從IAMSA算法的流程可以看出，其總時隙數為使用二叉樹與四叉樹兩部分所花時間之和。

如果有個待識別的標簽，并且當搜索深度為時，每個子節點上的平均標簽數為，那么，當搜索深度小于時，使用無空閑時隙的四叉樹，否則采用二叉樹。。

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

（1）

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

（2）

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

采用相似的分析方法，可以得到四叉樹中的碰撞時隙與空閑時隙分別為：

（3）

（4）

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

那么，使用算法成功地識別個標簽所需的總時隙數

（5）

3 仿真分析

下面將從總時隙數這個面來考察算法。

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

參考文獻

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