RFID閱讀器網絡分布式自適應信號覆蓋算法研究*

戴宏躍，廖 慧

（廣州科技貿易職業學院智能制造學院，廣州 511442）

0 引言

近年來，隨著物聯網應用的發展，RFID技術得到了越來越廣泛的應用，特別是物流[1－2]、倉管、圖書管理等相關領域，許多場景需要密集部署RFID閱讀器網絡來探測整個目標區域，因此，必須考慮系統的信號沖撞問題。信號沖突問題比較復雜，學術界在這方面有較多的研究[3－4]。目前解決多閱讀器信號沖突問題的代表算法有基于調度與基于功率控制的防沖突算法，其中基于調度的算法主要是基于時分和頻分多路工作，調度附近閱讀器在不同時間或頻率上工作，以避免信號沖突，這方面已有較深入的研究，王帥[5]針對CTT[6]算法在標簽數量增加而吞吐率降低的情況，提出了基于偽ID碼的樹型防碰撞算法（IDCTT算法）。基于功率控制的防信號沖突算法主要通過調整閱讀器功率大小，減少閱讀器的信號重疊以達到放沖突的目的，主要算法有王紅軍等[7]提出的多重優化的分布式無線覆蓋探測算法。這些算法雖然在一定程度上緩解了沖突情況，但是系統結構復雜，建立和維護網絡時需消耗大量資源。Carbunar B等[8]則針對RFID閱讀器網絡，提出了一種通過消除冗余閱讀器（Redundant Reader Elimination，RRE）算法以提高閱讀器網絡的覆蓋效率，但是RRE算法的實際效果并不理想，如圖1所示，在讀寫區域互相重疊的閱讀器，覆蓋同樣數量的標簽的場景下，打斷如圖所示的連續結變得十分困難，圖中，閱讀器R1~R5覆蓋T1~T8個標簽，最優方案是只需要R2和R4保持活動，如果運行RRE算法，此時R4認為擁有T5~T8，R3認為擁有T3~T6，R2又認為擁有T1~T4，導致R2、R3和R4都需要保持活動。而且隨著區域中閱讀器與標簽的數量增多，系統規模的增大，這種情況將變得更加嚴重，甚至在最壞的情況下需要2r－1個閱讀器保持活動狀態，而實際上只需要r個閱讀器。

圖1 連續結問題Fig.1 The difficulty of interrupting continuous node

從RRE算法的仿真的結果來看，其效果并不理想。基于此，本文提出了一種閱讀器分布式適應性覆蓋（Distributed Adaptive Coverage，DAC）算法。該算法旨在把RFID系統中相關的冗余閱讀器找出來，后續可以使用相關命令關閉這些冗余閱讀器，是整個系統具有最優數量的閱讀器工作。

1 DAC算法設計

在提出本文的算法之前，首先根據實際情況，做如下設定。

（1）DAC算法可以應用與任何數量的RFID閱讀器與標簽，認為閱讀器與標簽的拓撲結構在某一短時間段內是固定的。閱讀器網絡中不存在能夠協調閱讀器之間工作行為的中央控制器。DAC算法不依賴于閱讀器之間的通信能力。

（2）每個閱讀器都有自己唯一的ID，用來作為信息交流的身份識別。

（3）本文僅僅考慮無源標簽，因此，標簽以接收到的信號的能量來應答閱讀器的相關命令。

（4）標簽具有有限的存儲空間，其中一部分是只讀的，用來存儲唯一的標識；一部分是可讀寫的，供閱讀器讀寫。

（5）標簽具有命令匹配能力。根據不同的命令能做出不同的反應，或者根據命令不同的參數做出相應的動作。

（6）當多個標簽應答同一個命令時，閱讀器具有沖突探測能力。

1.1 DAC算法過程

為了提高閱讀器的覆蓋效率，探測出并關閉或休眠RFID閱讀器網絡中的冗余閱讀器，減少覆蓋重數，本文提出了該DAC算法。在閱讀器網絡拓撲中，假設閱讀器之間不能直接通信，但是由于有可讀寫的標簽存在，能夠存儲它所屬閱讀器的請求信息，因此可以利用標簽作中間媒介，閱讀器之間可以間接進行信息傳遞。每個閱讀器具有預先收集其讀寫區域內所有標簽信息，閱讀器網絡中所有閱讀器都能執行該功能。閱讀器在不同的時隙中工作，最大可能地避免沖突情況的發生，然后再執行DAC算法。DAC算法主要由3步組成。

（1）每個閱讀器在隨機時隙中收集它所覆蓋的標簽數目，保證每個閱讀器能盡快獲取本身所覆蓋標簽數。

（2）每個閱讀器嘗試將它所覆蓋的標簽數目以及閱讀器本身的ID寫入其所覆蓋的所有標簽中，但是標簽僅僅存儲最大數目值及相應閱讀器的ID。具體實現過程是每個閱讀器都發送包含閱讀器ID與它所覆蓋標簽數目的寫入標簽命令，命令的格式如圖2所示，處于該閱讀器讀寫區域內的標簽收到命令后，首先進行命令參數匹配，如果命令中包含的標簽數目比標簽已存在的數值大，即認為命令有效，執行寫操作，將標簽內已存儲的標簽數目值與閱讀器ID數據刷新。反之，如果命令中包含的標簽數目比標簽已存在的數值小，則不作響應。

圖2 標簽命令結構Fig.2 The command structure of the tag

（3）閱讀器查詢讀寫區域內的每個標簽，讀取標簽中所存儲的閱讀器ID。對于某一覆蓋較多標簽的閱讀器，其讀寫區域內的多個標簽可能同時具有該閱讀器的ID，因為該閱讀器覆蓋了這些標簽，而且標簽數目較多，因此在前一步的工作中該閱讀器可能已將自己的ID寫入這些標簽，導致該閱讀器在這一步操作中，在多個標簽中獲取到該ID值。至少能獲取一個標簽ID的閱讀器保留活動狀態，而沒有獲取到任何ID的閱讀器可以安全關閉，由于該閱讀器所覆蓋的標簽數目較少，而且該閱讀器所覆蓋的所有標簽同時已被其他的覆蓋標簽數目較多的處于活動狀態的閱讀器所覆蓋，這樣在前一步的操作中，該閱讀器所覆蓋的標簽已將其存儲的ID值更新了。

為了避免沖突情況，提高工作的可靠性，閱讀器對它所覆蓋標簽發送的命令可以在上述設置的隨機時隙內重復發送。

1.2 DAC算法實現

根據前面對標簽命令的設計，定義如圖3所示的描述標簽的主要數據結構，各變量的含義如圖中注釋所示。

圖3 標簽的數據結構Fig.3 Data structure of the tag

圖4所示為讀寫標簽的C語言算法過程的偽代碼，算法描述了在可讀寫標簽中，如果閱讀器發送過來的命令為寫標簽命令，則首先比較命令中的覆蓋標簽數值與標簽內現存的值，如果命令中的覆蓋標簽數目值大于標簽內現存的值，則更新標簽內該值與閱讀器ID（圖中第6~9行）。當接收到的命令為讀命令，則標簽返回一個包含存儲在標簽里的標簽標識符、閱讀器ID與覆蓋值的數據包。

圖4 讀寫標簽算法過程偽代碼Fig.4 The pseudo codeof reading and writing tag

圖5所示為探測冗余閱讀器算法過程偽代碼，概要描述了閱讀器與可讀寫標簽的一般過程。首先，閱讀器獲取覆蓋標簽數目值（第8~14行），在連續的第n個時幀中選擇一個隨機時隙，領用DetectCount（）方法探測閱讀器的覆蓋標簽數，算法中為了避免沖突，保證獲取的是閱讀器覆蓋標簽數目的最大值，算法中循環操作了Frame_cnt次，這里Frame_cnt表示每個幀的時隙數，根據系統設置而定。獲得閱讀器的覆蓋標簽數目值后，接著將獲取的覆蓋標簽數目值試圖寫入閱讀器所覆蓋的標簽中（第16~20行）。同樣，為了保證完全正確寫入所覆蓋區域中的全部標簽，算法也循環操作了Frame_cnt次。接著閱讀器讀取覆蓋區域內標簽數據，獲取標簽的標識碼，以及對應的標簽數目值、閱讀器ID，并將這些數據暫存閱讀器數據列表Tags[]中（第23~28行），供下一步使用。最后閱讀器分析該數據列表，統計數據列表中的閱讀器ID等于讀器本身的ID的個數，然后判斷該閱讀器是否為冗余閱讀器（第29~40行）。

圖5 探測冗余閱讀器算法過程偽代碼Fig.5 The pseudo code detecting redundancy reader

當某一閱讀器確定為冗余閱讀器以后，就可以通過相關命令關閉該閱讀器，減小閱讀器信號的沖撞，提高閱讀器信號的覆蓋效率。因此，對于同一區域，相同標簽情況下，算法能夠探測出的冗余閱讀器數量越多，說明需要開啟的閱讀器數量越少，即只需要少量閱讀器就能實現對整個區域的信號覆蓋。

2 仿真結果與分析

在第一個試驗中，在500 m×500 m的區域，隨機部署了500個閱讀器，標簽的數目從1 000~8 000，為了減小閱讀器信號覆蓋的重數，避免信號沖突，本文重檢測DAC算法與RRE算法找出的冗余閱讀器數目的能力，圖6所示為該試驗的仿真結果。從仿真的結果可以看出，對于小規模部署的標簽數目，兩種算法都比較接近，因為在小規模部署的標簽時，信號沖撞的情況相對較少，兩種算法差別不大。但是隨著區域中標簽數量的增多，兩算法探測到的冗余閱讀器數量也隨之減少。但DAC算法探測出的冗余閱讀器數量一直比RRE算法的數量大，說明同一區域內，DAC算法支撐下，能探測出更多的冗余閱讀器，所需活動閱讀器的數量更少，覆蓋效率更高。

圖6 使用驗證

圖6 冗余閱讀器數量隨標簽數量變化關系Fig.6 The relationship between the number of redundant reader and tags

圖7所示為當標簽數量恒為4 000，隨機部署的閱讀器的數量從50增加到1 000時，DAC與RRE算法探測出冗余閱讀器數量情況。從圖中顯示的結果來看，當閱讀器總數很少的時候，即閱讀器部署稀疏的情況來說，很少有冗余閱讀器問題，隨著閱讀器總數量的增多，閱讀器部署的密度的越來越大，信號沖撞問題加劇，于是出現了越來越多的冗余閱讀器，對比可以看出，DAC的結果一直在RRE之上，說明需要活動的閱讀器相對較少，只需要少量的閱讀器就能完成整個區域的信號覆蓋，從另一方面說了DAC算法的高性能。

圖7 冗余閱讀器數量隨閱讀器總數量變化情況Fig.7 Redundant reader number with the total number of reader

3 結束語

本文分析了RFID系統相關的信號防沖撞算法的優缺點，根據RFID閱讀器網絡的特點，重點研究分析RRE算法存在的問題，提出了一種分布式適應性覆蓋算法（DAC），仿真結果表明，在相同環境下，DAC算法能夠探測到冗余閱讀器的數量更多，在該算法支持下，需要活動的閱讀器數量更少，信號沖撞的情況便隨之降低，驗證了DAC算法能在密集環境下的性能明顯優于RRE算法，具有很好的適應性，可以有效提高閱讀器網絡的覆蓋效率，減小信號沖突，達到了預期的目的。