基于并行匹配的RFID自適應碰撞樹算法

賀曉霞，賈小林

(西南科技大學 計算機科學與技術學院，四川 綿陽 621000)

0 引 言

射頻識別(radio frequency identification，RFID)技術是實現物聯網(IoT)對象感知的關鍵。在RFID系統(tǒng)中當多個標簽試圖同時響應閱讀器的詢問時，就會發(fā)生標簽碰撞，即閱讀器無法識別任何標簽[1]。這種碰撞不僅延長了標簽識別的時間，而且增加了閱讀器的能耗。因此有效地解決標簽碰撞的防碰撞算法對于大規(guī)模物聯網RFID系統(tǒng)的開發(fā)具有重要意義。標簽防碰撞算法主要可以分為3大類：基于ALOHA的算法[2]、基于樹的算法[3]和混合算法[4]。基于ALOHA的算法在標簽數量相對較少的情況下表現較好的性能，但是隨機機制又會導致“標簽饑餓”[5]。基于樹的算法的優(yōu)點是即使在標簽密集的RFID系統(tǒng)中也能成功識別出所有的標簽。

基于Manchester code的位跟蹤技術在基于樹的算法中得到了廣泛的應用，如碰撞樹算法(CT)[6]、雙時隙碰撞跟蹤樹算法(BSCTTA)[7]、雙前綴探針算法(DPPS)[8]等。BSCTTA的設計使得前綴開銷和迭代開銷可以通過時間分割響應[7]來減少，但標簽數量非常大時，該算法性能會降低，因為它只會在發(fā)生碰撞時分成兩個子組來避免標簽沖突[9]。自適應碰撞樹算法(ACT)[10]是一種基于碰撞樹算法(CT)和改進的碰撞樹算法(ICT)[11]的防碰撞算法。ACT在一定程度上縮短了標簽識別時間，提高了系統(tǒng)性能，但在使用四叉樹搜索時，它增加了空閑周期的數量，對系統(tǒng)性能產生了影響。類似，AdATSA[12]和OBTT[13]在識別過程中仍然存在空閑時隙，不可避免地也降低了系統(tǒng)性能。

基于上述問題，本文提出了一種基于并行匹配方案的自適應碰撞樹(PACT)算法，通過引入并行匹配機制來減少空閑的查詢周期，同時利用碰撞標簽的數量自適應地選擇搜索模式(2-branchCT還是8-branchCT)，大大降低搜索深度，減少碰撞周期和延遲。

1 PACT算法

(1)并行匹配與系統(tǒng)傳輸模型

在查詢樹算法(QT)中，當閱讀器在識別過程中檢測到了碰撞時，通過將0和1附加到之前的前綴生成一個新的前綴并入棧，然后逐個發(fā)送兩個查詢。具有與前綴匹配的ID的標簽將響應除了其ID的匹配部分之外的完整部分。在本文中，將這種查詢類型稱為串行匹配查詢，指定為SMQ(sequential matching query)。與之相比，本文提出的算法只需要發(fā)送一個查詢，但是并行執(zhí)行標簽匹配。這種沖突仲裁稱為并行匹配方案，使用的查詢稱為并行匹配查詢，簡稱PMQ(parallel matching query)。具體來講，由于標簽ID的二元確定性原則[11]，與前綴匹配的標簽肯定會在兩個時隙中的一個中響應。在識別過程中，與前綴匹配的標簽將在兩個連續(xù)時隙之一中發(fā)送它們的ID，標簽通過其ID的第(L+1)位的值是0還是1來確定應響應的時隙數量，其中L是所接收的前綴的長度。在第一個時隙中分配的標簽先發(fā)送其ID，然后在第二個時隙中分配的標簽將在第一個時隙上的傳輸完成后再發(fā)送其ID。使用這種機制不僅有效地減少了查詢周期的數量，而且減少了閱讀器發(fā)送的查詢前綴的長度。如圖1所示，是傳統(tǒng)基于樹的算法和并行匹配方案的鏈路時序。閱讀器在時間TR中發(fā)送CW信號和查詢命令。標簽從射頻信號中獲取工作能量并傳輸信息。在接收到閱讀器的命令之后，標簽在時間T1中生成它們的響應。

圖1 基于傳統(tǒng)的樹算法和并行匹配方案的鏈路時序

根據上述傳輸模型，時間模型描述如式(1)所示。在詢問區(qū)中識別n個標簽所花費的總時間為每個循環(huán)中閱讀器發(fā)送查詢的時間加上標簽響應所需的時間。令CPMQ和CSMQ分別表示PMQ和SMQ的個數。識別時間可以表示為下式：其中TRi和Ttagi分別表示在第i個周期中閱讀器傳輸查詢和標簽響應所花費的時間

(1)

(2)自適應分割機制

所提出的算法采用自適應分割機制來根據碰撞條件決定CT的選擇為8分支碰撞樹或2分支碰撞樹。假設在系統(tǒng)中有N個標簽待識別，分布的子分支的數量是L，搜索深度是k。則識別概率可以計算為

p(k)=p(1)*(1-p(1))k-1

(2)

p(1)=(1-1/L)N-1

(3)

然后我們可以得到搜索深度的數學期望，即

(4)

因此，標簽識別所需的平均時隙數是

(5)

對于式(5)中的L進行部分推導，可以得到

(6)

從式(6)可以觀察到，當分布的子分支的數量L等于標簽的數量N時，系統(tǒng)所需的時隙數最少。因此，當標簽數量很多時，為了減少識別所需的時隙，可以分配更多子分支。

根據式(5)，將L=2代入到式中，則2-branch樹中識別過程所需的平均時隙數可以表示為

T2branch=2/(1-1/2)N-1=2N

(7)

在8-branch樹中，所需的平均時隙數為

T8branch=8/(1-1/8)N-1=8N/7N-1

(8)

通過等式(7)和式(8)可以看到，當N≥4時，T8branchT2branch。 總而言之，當識別范圍內存在的標簽數量大于等于4時，使用8分支碰撞樹更有效。當標簽數量小于4時，2-branch CT比8-branch CT具有更好的性能。因此，當N≥4時，PACT算法選擇使用8-branch CT，在N<4時使用2-branch CT。

(3)識別過程

PACT算法使用兩種類型的查詢，SMQ和PMQ，初始化查詢類型為PMQ，前綴為‘ε’。標簽響應的長度由查詢類型決定，其中k為標簽ID的長度，L為接收前綴的長度，如式(9)

(9)

PACT算法描述如下：具體來說，Prefix是前綴堆棧。M和N分別是碰撞比特的數量和碰撞標簽的數量。Request(ε)要求所有在閱讀器查詢范圍內的標簽響應。Request(prefix)要求標簽將自己的ID與閱讀器發(fā)送的前綴進行比較，如果滿足查詢條件(假設前綴和標簽ID的長度分別為L和k)，則將剩余的(k-L)位返回給閱讀器。PACT算法詳細過程的偽代碼見表1。

表1 PACT算法詳細描述

2 性能分析

在本節(jié)中，通過理論分析，從時間復雜度和系統(tǒng)效率兩個方面對PACT的性能進行了評估，通過測量所需的時隙來評估系統(tǒng)的時間復雜度。

設n是讀取器天線范圍內的標簽數量，d是標簽ID的長度。C8branch(n) 表示在8-branch樹搜索中產生的碰撞時隙的數量，C2branch(n) 表示在2-branch樹搜索中產生的碰撞時隙的數量。考慮到自動識別的思想，當一個比特發(fā)生N1次碰撞時，系統(tǒng)可以減少2N1時隙。

因此，總時隙數可以計算為

T(n)=C8branch(n)+C2branch(n)+n-2N1

(10)

在文獻[14]中，給出了完全二進制樹中碰撞時隙數的理論期望

(11)

其中，L為樹的搜索深度，B為樹的維數。因此，當L=k+1時，8分支樹搜索的碰撞時隙為

(12)

根據文獻[4]，2分支樹搜索中的碰撞時隙數與B分支樹搜索中的碰撞時隙數之比約為1/log2B。 由于2-branch CT中的碰撞節(jié)點數是(n-1)[11]，完全8-branch CT中的碰撞節(jié)點數應該是 (n-1)/3， 假設要識別的系統(tǒng)中有n個標簽。可以得到在PACT中8-branch樹搜索中產生的碰撞周期的數量為

(13)

綜上所述，當搜索深度等于k+1時，每個2-branch CT中剩余的碰撞時隙中只有兩個或3個標簽1

(14)

因此，PACT中所需的總時隙數可以計算為

(15)

系統(tǒng)效率定義為標簽數量與在系統(tǒng)中識別它們所需的總時隙數量之比。因此，我們可以獲得系統(tǒng)效率為

(16)

3 仿真結果

本文利用MATLAB仿真平臺，選擇理想信道，將本文提出的PACT算法與自適應碰撞樹算法(ACT)、改進的碰撞樹算法(ICT)以及最優(yōu)的跟蹤樹算法(OBTT)分別在所需時隙的數量、碰撞時隙的數量以及系統(tǒng)效率方面進行分析比較。假設系統(tǒng)內標簽均勻分布，遵循ISO18000-6標準，隨機生成編號長度為96位的電子標簽，標簽數量從100增加到2000。

圖2顯示了標簽數量與識別過程中所需的總時隙數之間的關系。可以看出，在相同數量的標簽下，本文提出的PACT算法所需的時隙數小于其它3種算法(ACT，ICT和OBTT)所需的時隙數。

圖2 總時隙數與標簽數關系

圖3描繪了碰撞時隙數與標簽的關系圖。當標簽的數量小于200時，OBTT和PACT生成的碰撞時隙的數量是相似的，但是隨著標簽數量增加，PACT生成的碰撞時隙的數量明顯低于其它3種算法。主要是因為在PACT中使用了并行匹配方案使得8分支樹搜索階段減少了大量的碰撞時隙。

圖3 碰撞時隙數與標簽數關系

圖4為4種算法的系統(tǒng)效率對比。很明顯，PACT的系統(tǒng)效率約為0.609，高于其它3種算法。ICT，ACT和OBTT的平均系統(tǒng)效率分別為0.521,0.559和0.601。

圖4 系統(tǒng)效率與標簽數關系

4 結束語

本文提出一種基于并行匹配方案的RFID自適應碰撞樹算法(PACT)，該算法使用并行匹配方案來減少查詢周期的數量，同時利用沖突標簽的數量來自適應地選擇搜索模式，當標簽數大于等于4時，PACT算法選擇使用8-branch CT，在標簽數小于4時則使用2-branch CT。PACT的系統(tǒng)效率約為0.6092，也表現出了較好的穩(wěn)定性。仿真結果表明，所提出的算法與現有的基于樹的算法相比，不僅提高了系統(tǒng)的效率和標簽識別的速度，而且降低了時間復雜度，特別是在大規(guī)模標簽情況下。