基于圖論的射頻識別閱讀器防碰撞算法

徐亞峰，崔英花

(北京信息科技大學 信息與通信工程學院，北京 100020)

(*通信作者電子郵箱626751238@qq.com)

基于圖論的射頻識別閱讀器防碰撞算法

徐亞峰*，崔英花

(北京信息科技大學 信息與通信工程學院，北京 100020)

(*通信作者電子郵箱626751238@qq.com)

射頻識別(RFID)系統的運行往往需要多個閱讀器，以保證覆蓋整個目標區域。在密集的閱讀器的環境中，由于閱讀器之間存在相互干擾，會影響整個RFID系統的工作效率，降低識別效率。針對上述問題，提出一種新的基于圖論的閱讀器防碰撞算法。首先把閱讀器網絡看成簡單圖，以時隙對閱讀器分組，同時隙閱讀器為一組，相鄰閱讀器分配不同的時隙，以解決閱讀器因讀取范圍交叉重疊而引起的干擾；同時考慮組內閱讀器的頻率干擾問題，同樣以頻率對組內閱讀器再分組，同頻率閱讀器為一組，相鄰閱讀器分配不同頻率，以解決因干擾范圍過大而引起的頻率碰撞問題；然后根據分組信息，中央服務器通過配置命令將時隙和頻率資源調度分配給每個閱讀器；最后通過時序命令控制每組閱讀器的工作順序。仿真結果顯示，相比鄰近友好型防碰撞(NFRA)算法，該算法平均工作效率提升了6.5個百分點；閱讀器數量為1 000時系統工作效率提升了9.5個百分點。新算法能優化給定時間內工作閱讀器的數量，減少閑置等待的閱讀器數量。

射頻識別；閱讀器；工作效率；圖論；資源調度

0 引言

近年來，隨著物聯網的飛速發展，射頻識別(Radio Frequency IDentification，RFID)技術已經被廣泛應用在多個領域，例如交通，物流，醫療保健，身識別(電子護照、二代身份證) ，圖書館，危險品管理，煙酒，票證防偽，旅游，軍事，智能家居等[1]。然而伴隨著RFID技術的廣泛應用，RFID技術中的碰撞問題也日漸嚴重。理論上，閱讀器能自動識別在其天線信號覆蓋范圍內的不同的標簽，然而單個閱讀器的工作區域是有限的，為了擴展覆蓋區域，就需要多個閱讀器組成閱讀器網絡。由于相鄰閱讀器在其信號交疊區域內會相互產生干擾，因此會發生閱讀器碰撞問題[2]。

當一個閱讀器附近有一個或多個有相同工作頻率的閱讀器時，閱讀器收到的鄰近閱讀器的信號相當于噪聲信號。如果閱讀器與標簽通信時，噪聲功率與標簽反射回的功率的比值超過了接收門限值，那么閱讀器就無法正確識別該標簽的信號。一般來說，閱讀器的碰撞問題可以分為兩類:一類是“閱讀器-閱讀器”(Reader to Reader Interference, RRI)碰撞，另一類是“閱讀器-標簽”(Reader to Tag Interference, RTI)碰撞[3-4]。如圖1(a)所示，由于閱讀器(v)的干擾范圍(I)大于讀取范圍(r)[5-6]，閱讀器v1處在v2的干擾信號范圍內，標簽(T)發送到閱讀器v1的弱信號會受到來自閱讀器v2的強信號的干擾，可能造成閱讀v1與標簽通信的失敗。當某個標簽處在兩個或多個不同閱讀器的閱讀范圍內時，且有一個以上閱讀器同時與該標簽通信，就會產生閱讀器-標簽碰撞。如圖1(b)所示，閱讀器v1和v2的閱讀范圍重疊，標簽T位于重疊區域內，如果閱讀器v1和v2的通信頻率相同，且同時向該標簽發信號時，標簽會無法作出正確的響應。

圖1 閱讀器碰撞類型Fig. 1 Reader collision types

目前解決閱讀碰撞問題的算法很多，這些算法可以被分為兩種：一種是基于有效范圍的算法，另一種是基于調度的算法[7]?；谟行Х秶姆琅鲎菜惴ê诵乃枷胧峭ㄟ^減小閱讀器之間的重疊區域來減少閱讀器之間的碰撞，這類算法只能使閱讀器碰撞最少化，而不能完全消除閱讀器的碰撞；而基于調度的防碰撞算法核心思想是防止閱讀器同時發送信號給標簽,以此避免碰撞發生，該類算法一直是防碰撞算法的主流[7-8]。

Colorwave算法[9]是基于分布式的時分復用型的防碰撞算法，所有閱讀器通過同步機制組成一個閱讀器網絡，每個閱讀器都被分配了對應的時隙(顏色)，對閱讀器網絡的時隙的分配就相當于圖著色問題。但是Colorwave算法要求閱讀器之間有嚴格的時間同步，然而Ad Hoc網絡很難做到時間同步，閱讀器也無法探測到發生在標簽上的碰撞。另外，閱讀器的移動會引起時隙重新分配，使整個系統的效率下降。

基于Q-Learning在線強化學習的防沖突算法HiQ[10]采用多層結構，通過與RFID系統的交流來學習閱讀器層的沖突模式，動態地分配閱讀器頻率和時隙資源，從而實現防碰撞。但算法的多層結構使閱讀器設計復雜，增加了硬件成本；而且移動閱讀器會改變網絡的拓撲結構，降低系統的效率。

文獻[11]在分析Colorwave和HiQ算法后提出了一種鄰近友好型防碰撞(Neighbor-Friendly Reader Anti-Collision，NFRA)算法。該算法采用的是基于服務器調度的時分復用型算法。中央服務器對區域內多個閱讀器進行配置，然后根據排序命令為閱讀器分配操作的優先次序，避免會相互干擾的閱讀器在同一時間段內操作，從而減少整個閱讀器網絡的碰撞情況。但是該算法只考慮了RTI的問題沒有考慮RRI的問題，并且排序機制是系統隨機的機制，并不能最有效地分配每一個閱讀器的工作優先次序，反而會增加系的等待時間，降低整體的效率。

本文在NFRA算法基礎上提出一種基于圖形著色理論的新型防碰撞算法，同時考慮閱讀器兩種類型的碰撞，將整個閱讀器網絡以組來劃分，每個組內閱讀器可以在同一時隙內操作，從而可以給每組分配一個工作時隙；并且盡可能使組內成員數達到最大，減少所用的時隙數。而組內潛在的干擾問題則通過分配不同的頻率來解決。閱讀器操作的優先次序以組為單位，按組內成員數由大到小的順序來分配時隙。該算法能有效提升閱讀器單位時間內的操作數量，減少系統的等待時間，提高閱讀器網絡的整體工作效率。

1 相關工作

本文首先定義下面的一些符號。如圖1所示，用vi表示一個閱讀器，ri表示vi的讀取范圍(即vi所能確定標簽的距離范圍)，Ii表示vi的干擾范圍(即vi的信號能對其他閱讀器信號產生影響的距離范圍)，dij表示閱讀器vi和vj之間的距離。假設所有的閱讀器都具有相同的讀取范圍，當滿足下面的條件時，兩個閱讀器vi和vj之間將會產生RTI 問題，即：

dij

(1)

在這種情況下，閱讀器vi和vj必須在不同的時隙進行操作才能避免發生沖突。

當滿足下面的條件時，RRT和RTI都會發生：

dij

(2)

在這種情況下，閱讀器vi和vj必須以不同的頻率進行操作才能避免發生沖突。

假設在某個固定的區域里放置了大量的閱讀器，中央服務器的信號能到達該區域內的任何閱讀器，并且服務器知道所有閱讀器的位置信息,同時能給閱讀器分配時隙和頻率資源。在給定的時間內，操作的閱讀器數量越多，效率越高。提出的閱讀器防碰撞算法的目的就是在給定時間內盡可能最大化工作的閱讀器數量，最小化碰撞次數。

文獻[11]的NFRA算法開始讓服務器廣播一個配置命令(Arrangement Command，AC)，這個命令包含開始的回合數和隨機數(隨機數從1到N，N的取值取于閱讀器的數量)。當閱讀器接收到配置命令后，各自生成自己1-N的隨機數，隨后服務器發送排序命令(Ordering Command， OC)，當閱讀器自身的隨機數和OC命令的值相同時，閱讀器就向周圍廣播beacon信號，來確定是否會有碰撞發生，如果發現會與相鄰閱讀器產生碰撞，閱讀器將發送覆蓋幀(Overriding Frame，OF)給鄰近閱讀器，使鄰近閱讀器不會接受下一次的OC命令直到本回合結束，繼續等待下一回合的AC命令。那么其他沒有接收到OF的閱讀器，等待本回合下一個OC命令，若有與OC命令值相同的閱讀器，將重復上面的過程。

假設有如圖2所示的一個閱讀器場景，服務器開始向它覆蓋的區域廣播AC命令，閱讀器收到命令后產生的隨機數(本例中隨機數范圍是1到3)。為方便表示，圖2中用i-j表示產生隨機數為i的閱讀器vj，如下面的描述中閱讀器2-1即指產生隨機為2的閱讀器v1。這個過程完成后，服務器廣播值為1的OC命令，生成的隨機數1的閱讀器開始向鄰居閱讀器發送beacon信號，來確定周圍是否有相同隨機數的閱讀器存在。從圖2可以看到所有隨機數為1的閱讀器之間都在各自的干擾范圍之外，不會產生干擾，然后這些閱讀開始工作讀取在它們工作區域里的標簽。同時，服務器開始廣播值為2的OC命令，那么閱讀器2-1和2-2都開始發送beacon信號，發現它們之間會產生相互干擾。產生干擾的閱讀器會放棄本回合的標簽識別過程，直到下回合的AC命令。因為在上一個值為1的OC命令階段，閱讀器2- 4收到來自鄰近閱讀器1-2的OF命令，因此閱讀器2- 4也不會工作。只有閱讀器2-3會嘗試進行標簽的識別工作。服務器又開始廣播值為3的OC命令，生成隨機數3的閱讀器重復上述類似的操作。閱讀器3-1和3-2由于不會發生相互碰撞，也沒有收到任何來自鄰近閱讀器的OF命令，因此可以嘗試識別標簽。類似的閱讀器2- 4，閱讀器3-3也不能對標簽進行識別工作。

圖2 多閱讀器網絡Fig. 2 Multi-reader network

從圖2中可以發現，如果僅僅只考慮時間的問題，第一個OC命令可以同時工作的閱讀器不僅僅只是3個，實際上是5個，它們分別是閱讀器1-1,1-2,1-3,2-1和3-1。由于閱讀器本身的數值是隨機生成的，所以無法保證最大化同一時間段內可操作的閱讀器個數，使得本可以工作的閱讀器不得不閑置等待下一次的OC命令，造成資源的浪費。如果處于密集區域的閱讀器產生的隨機數值越小那么就意味著它在OC命令到來之時就越有優先工作的可能。如果閱讀器的分布如圖3所示，可以看出閱讀器v5和v6處于最密集的區域當中。假設閱讀器v5生成的隨機數是1，那么第一個OC命令到來時，閱讀器v5就要周圍的閱讀器發送beacon信號，鄰近的6個閱讀器都將被禁止在當前AC命令下工作。相反如果處于相對較稀疏區域的閱讀器v4生成的隨機數是1，那么被禁止在當前AC命令下工作的閱讀器只有3個。從圖3中可以知道，最壞的情況是閱讀器v5和v7生成的隨機數是1，周圍其他的8個閱讀器都將被限制工作，直到下個AC命令的到來；而最好的情況是處于邊緣稀疏區域的閱讀器生成的隨機數是1，例如閱讀器v2,v4,v7和v9，這種情況下被限制工作的閱讀器是6個。如果閱讀器的數量是巨大的，那么將能極大地改善整個閱讀器網絡資源的利用，提高系統的工作效率。

圖3 密集閱讀器網絡例子Fig. 3 Example of dense reader network

通過上面的分析，可以知道上述缺陷都是由于隨機這個機制所導致的，并且NFRA算法也沒有考慮到RRI的問題。回到圖2中，當閱讀器2-1和2-2使用相同的頻率同時向周圍發送beacon信號，由于干擾的存在，鄰近閱讀器并不一定能正確接收這個beacon信號，那么閱讀器之間的干擾依然會存在。 因此需要解決潛在的頻率干擾問題，同時最大化每個OC命令可操作的閱讀器數量。這就是本文提出的算法所需要解決的事情。

2 本文算法

對于一個密集的RFID閱讀器網絡，如果把閱讀器vi看成是一個點，那么整個閱讀器網絡就可以看作是由這些點連成的無向圖G=(V,E)。其中：V代表無向圖中點的集合(閱讀器集合)，這些點被稱為頂點；E表示一組不同的無序頂點所組成的邊。本文后面都用G來表示閱讀器網絡。

首先來討論時隙的問題。在密集的閱讀器網絡G中來對閱讀器vi進行分組，閱讀器的分組要滿足下面的條件：

1) 組內閱讀器任意兩個成員vi,vj之間滿足：

dij>ri+rj

(3)

此時任意兩個閱讀器vi,vj之間對于時隙的分配滿足：

|t(vi)-t(vj)|∈T

(4)

其中T是圖著色問題中的T-設置{0}，此處表示組內任意兩個閱讀器成員可以在同一個時隙內工作。

2) 組內閱讀器成員數是極大的。當閱讀器網絡G中任意不屬于該組的閱讀器vk加入該組后，會導致：

|t(vi)-t(vk)|?T

(5)

即組內再增加任何一個閱讀器后都會有干擾產生，不能在同一時隙內工作。

由于組內閱讀器成員可以在同一個時隙內工作，那么每一組就可以代表一個時隙ti，時隙的先后順序要取決于組內閱讀器的成員數，按照數量由大到小的順序進行排序。按顏色對閱讀器網絡分組，每一種顏色代表一個時隙，下面進行詳細分析。

如果兩個閱讀器v1,v2之間滿足式(1)，那么就把這兩個閱讀器看作相鄰的，即(vi,vj)∈E。整個RFID閱讀器網絡就可以看成一個或多個無向圖Gi。閱讀器網絡G的著色，就是分配顏色ci到閱讀器vi，使兩相鄰的閱讀器不會被分配到同一種顏色。顏色被定義為一組非負的整數，用集合來C={c1,c2,…,cN}表示，在這里每一種顏色都可以看作是一個時隙，即C={c1,c2,…,cN}→T′={t1,t2,…,tN}。在分配顏色時，定義最少的顏色為圖形的色度數量，色度用χ(G)來表示，那么N=χ(G)就是所需要的時隙數。

然后來討論頻率干擾的問題，對于已經分好顏色ci的閱讀器之間，雖然可以在同一時隙內工作，但由于閱讀器的干擾范圍遠大于閱讀器的識別范圍，當閱讀器之間不滿足下面的條件：

dij>ri+Ij

(6)

假設服務器知道所有閱讀器的位置信息，每個閱讀器都有自己的ID，剛開始閱讀器都處于靜默狀態，服務器后臺通過程序運算分組(分配時隙)和分配頻率完畢，按照組內成員數由大到小排序分配組號1到N(時隙的順序)；然后開始向其傳輸范圍內的閱讀器廣播分組的配置命令，命令格式如圖4所示。閱讀器收到配置命令后存儲自己的分組信息和頻率信息，然后服務器開始廣播值為1的時序命令，收到時序命令的閱讀器用自己存儲的分組信息與之比較，若兩者相同，那么閱讀器被激活，用指定的頻率開始工作。當所有組號為1的閱讀器都開始工作，系統進入標簽識別時間。完成識別后之后服務器又開始廣播值為2的時序命令，類似組號為2的所有閱讀器接開始識別工作。識別時間過后，廣播值為3的時序命令，重復上述步驟直到所有的閱讀器完成工作。

圖4 服務器配置命令格式

Fig. 4 Server configuration command format

服務器分配資源控制閱讀器步驟如下：

步驟1 服務器根據閱讀器位置信息和式(3)對閱讀器進行分組，此時分配的是時隙資源。

步驟2 服務器根據式(6)對步驟1中已經分好組的閱讀器組內再分組，此時分配的是頻率資源。

步驟3 服務器將分配好的時隙和頻率資源通過如圖4格式的AC命令廣播給閱讀器。

步驟4 閱讀器接收存儲服務分配的資源信息，等待服務器的OC命令。

步驟5 服務器廣播第一個OC命令，閱讀器將收到的OC命令和自己存儲的時隙資源比較，如果兩者值相同，那么開始工作；否則等待下個OC命令，直到所有閱讀器工作完畢。

3 實例說明

假設有如圖5(a)所示的一個相對密集的閱讀器網絡，圖中閱讀器的碰撞情況很嚴重，把每個閱讀器vi看成是無向圖G1的一個頂點，如果兩個閱讀之間的距離滿足式(1)，那么就把這兩個閱讀器看作是相鄰的，這些閱讀器組成的無向圖G1如圖5(b)所示。

前面已經假設服務器知道所有閱讀器的具體位置信息，所以服務器知道閱讀器的分布狀況，如圖5(b)。如果用顏色c1給閱讀器v1涂色，那么閱讀器v2,v3,v4只能用除了顏色c1以外的顏色來涂色。由于閱讀器v4處于相對密集的區域，那么先給閱讀器v2,v3涂色上顏色c2，閱讀器v4與閱讀器v1,v2,v3都相鄰只能選用顏色c1,c2以外的顏色c3。閱讀器v5周圍的閱讀器只有v3和v4被涂上顏色c2和顏色c3，為了使選用的顏色數盡可能最少，用顏色c1給閱讀器v5涂色，類似地，閱讀器v7周圍的閱讀器v4和v5分別被涂上顏色c1和顏色c3，可以用顏色c2給它涂色。由于閱讀器v8處于比較密集的區域，最后考慮給它涂色。同樣，閱讀器v6用顏色c1涂色，閱讀器v9也可以用顏色c1涂色，閱讀器v10用顏色c3涂色，最后剩下閱讀器v8，其周圍閱讀器點分別使用過顏色c1,c2,c3，那么為了防止沖突，用顏色c4給它涂色，這樣整個閱讀器網絡G1的頂點就著色完畢。G1被分為四組c1,c2,c3,c4，即所需時隙數N=χ(G1)=4，各組內閱讀器成員個數分別為4，3，2，1。著色完成后的閱讀器網絡G1如圖5(c)所示。

然后按組內成員大小來分配時隙的順序，在上面的實例中，顏色c1的所有閱讀器被分配t1，顏色c2的所有閱讀器被分配t2，以此類推顏色c3對應時隙t3，顏色c4對應時隙t4。圖5(c)中任意相鄰的閱讀器之間的顏色都不相同，也就是說在RFID閱讀器網絡G1中任意有識別區域相互交叉重疊的閱讀器都被分配不同時隙，從而可以避免RTI的碰撞問題。

圖5 密集閱讀器轉換與著色實例Fig. 5 Example for conversion and coloring of dense readers

在實際的RFID閱讀器網絡中，閱讀器的數量巨大，那么相應的無向圖的頂點也非常多，這種情況下通常采用貪心法來給無向圖的頂點著色[12]，但是基本思想是一致的。

服務器在完成了上述工作后，已經對每個閱讀器分配好了工作的時隙和頻率，只需要向閱讀廣播資源配置命令，其格式如圖4所示，閱讀器接收到命令后存儲被分配的資源信息，然后根據時序命令開始工作。

4 仿真與分析

閱讀器防碰撞算法的目的是在沒有相互干擾的情況下，盡可讓更多的閱讀器能同時工作，因此算法的性能可以用在給定的時間內同時工作的閱讀器數量來評估。定義每毫秒工作的閱讀器的數量為系統的工作效率。下面對本文算法和NFRA算法在同等條件下進行仿真比較。

在實際的倉儲管理系統中，RFID系統需要對每個入庫的產品進行數據的錄入，管理盤點這些產品的數量等信息。為了能覆蓋整個倉庫的產品，系統必須在倉庫中放置多個閱讀器。

實驗條件：假設有一個20 m×20 m的倉庫，為了體現算法的一般性，在這個區域中隨機放置數量不同的閱讀器，閱讀器數量分別為100，200，…，1 000；假設閱讀的讀取范圍為2 m，干擾范圍為6 m；閱讀器識別100個標簽需要的時間是0.46 ms,服務器的AC命令時長為2.83 ms，OC命令時長為1 ms[11]。由于在同等條件下是否考慮路徑損耗都不會影響算法的性能比較，因此實驗環境的路徑損耗設置為理想環境。通過多次實驗仿真取平均值，得到如圖6所示的結果。

實驗仿真結果表明，本文算法的工作效率要優于NFRA算法。當閱讀器數目為100時，本文算法比NFRA算法的工作效率提升了1.5個百分點；閱讀器數目為200時，系統效率提升3.1個百分點；當閱讀器數目達到1 000時系統的效率提升了9.5個百分點；隨著閱讀器數量的增多，本文算法相比NFRA算法體現出更大的優越性，系統的平均工作效率提升了6.5個百分點。而且隨著閱讀器數量的不斷增多，本文算法性能將趨于一個相對平穩的增長狀態。

當閱讀器數目越多，網絡環境越密集，本文算法相比NFRA算法更加有效率，能更快速讀取需被識別物體的信息。在實際龐大的倉儲系統管理中，能夠減少產品入庫信息存儲的時間，提高工作效率。

圖6 算法性能比較Fig. 6 Performance comparison of algorithms

5 結語

本文針對密集環境下的閱讀器碰撞問題進行了探討，基于NFRA提出了一種新的防碰撞算法，利用簡單圖著色理論，同時考慮時隙和頻率的分配問題，解決了NFRA算法由于隨機機制導致的閱讀器閑置和潛在的頻率干擾問題，能在保證閱讀器不產生干擾的情況下，使盡可能多的閱讀器在同一時間工作，減少了閑置的閱讀器數量。仿真結果表明，相比NFRA算法，本文算法的工作效率有不錯的提升，并且工作效率的增量隨著閱讀器數量的增加而增加。但是該方法可能對中央服務器的性能要求比較高，閱讀器的移動性問題還有待進一步研究。整體來說，本文算法能夠解決密集環境下閱讀器的碰撞問題，提高RFID系統的工作效率，具有較好的實際意義和價值。

References)

[1] 吳歡歡,周建平,許燕,等.RFID發展及其應用綜述[J].計算機應用與軟件,2013,30(12):203-206. (WU H H, ZHOU J P, XU Y, et al. A comprehensive review on RFID development and its application [J]. Computer Applications and Software, 2013, 30(12): 203-206.)

[2] 于惠鈞,劉曉燕,朱永祥.RFID標簽閱讀器系統防沖突算法的研究[J]. 包裝工程,2008,29(5):46-48. (YU H J, LIU X Y, ZHU Y X. Study on anti-collision algorithms in RFID reader system [J]. Packaging Engineering, 2008, 29(5): 46-48.)

[3] 劉瑋,吳曉波,張偉偉,等.基于調度方式的閱讀器防碰撞算法[J]. 包裝工程,2014,35(21):127-131. (LIU W, WU X B, ZHANG W W, et al. An anti-collision algorithm based on schedule mode for reader [J]. Packaging Engineering, 2014, 35(21): 127-131.)

[4] 陳穎,張福洪.RFID傳感網絡中多閱讀器碰撞算法的研究[J].傳感技術學報,2010,23(2):265-268. (CHEN Y, ZHANG F H. Study on reader anti-collision algorithm in RFID sensor networks [J]. Chinese Journal of Sensors and Actuators, 2010, 23(2): 265-268.)

[5] 顧成喜,顧才東,龔偉.RFID環境下利用通報機制的分布式閱讀器防沖突算法[J/OL].計算機應用研究, [2017- 06- 15]. http://www.arocmag.com/article/02- 2017- 06- 015.html. (GU C X, GU C D, GONG W. Distributed reader anti-collision algorithm using notification mechanism in RFID environments[J]. Application Research of Computers, [2017- 06- 15]. http://www.arocmag.com/article/02- 2017- 06- 015.html.

[6] 王宇,甘健侯.一種分布式全類型RFID閱讀器碰撞解決方案[J].電子技術應用,2016,42(4):92-94,98. (WANG Y, GAN J H. A distributed anti algorithm for all types of RFID reader collision [J]. Application of Electronic Technique, 2016, 42(4): 92-94,98.)

[7] 郭雷勇,譚洪舟,高守平,等.RFID系統閱讀器反碰撞算法分類與研究[J].計算機技術與發展,2009,19(9):13-16,20. (GUO L Y, TAN H Z, GAO S P，et al. Taxonomy and survey of RFID reader anti-collision protocols[J]. Computer Technology and Development, 2009, 19(9): 13-16, 20.)

[8] 李劍丹. RFID系統中多閱讀器環境下防碰撞問題的研究[D].武漢：武漢理工大學,2014:4-14. (LI J D. Research of anti-collision problem for multiple readers in the RFID system[D].Wuhan: Wuhan University of Technology, 2014: 4-14.)

[9] WALDROP J, ENGLES D W, SARMA S E. Colorwave: an anticollision algorithm for the reader collision problem [C]// ICC 2003: Proceedings of 2003 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2003: 1206-1210.

[10] HO J, ENGELS D W, SARMA S E. HiQ: a hierarchical Q-learning algorithm to solve the reader collision problem [C]// SAINT Workshops 2006: Proceedings of the 2006 International Symposium on Applications and the Internet Workshops. Piscataway, NJ: IEEE, 2006: 88-91．

[11] EOM J-B, YIM S-B, LEE T-J. An efficient reader anticollision algorithm in dense RFID networks with mobile RFID readers [J]. IEEE Transactions on Industrial Electronics, 2009, 56(7): 2326-2336.

[12] 馮珊珊.基于圖著色理論的聚類研究[D].太原:太原理工大學,2013.:14-17. (FENG S S. Research on clustering algorithm based on graph coloring theory [D]. Taiyuan: Taiyuan University of Technology, 2013: 14-17.)

This work is partially supported by the National Natural Science Foundation of China (61340005), the General Program of Beijing Municipal Natural Science Foundation (4132012), the Science and Technology Development Program of Beijing Municipal Education Commission (KM201411232011).

XUYafeng, born in 1990，M. S. candidate. His research interests include radio frequency identification.

CUIYinghua, born in 1973，Ph. D., associate professor. Her research interests include Radio frequency identification.

Anti-collisionalgorithmforreadersinradiofrequencyidentificationbasedongraphtheory

XU Yafeng*，CUI Yinghua

(SchoolofInformationandCommunicationEngineering,BeijingInformationScienceandTechnologyUniversity,Beijing100020，china)

Radio Frequency IDentification (RFID) systems often require multiple readers to ensure coverage of the entire target area. When there are too much readers, because of the mutual interference between the readers, the efficiency of the whole RFID system and the recognition efficiency are reduced. To resolve the problem, a new reader anti-collision algorithm based on graph theory was proposed. Firstly, the reader network was considered as a simple graph with time slot of the reader groups, the readers with the same time slot were regarded as a group, and the adjacent readers were assigned with different time slot, thus avoiding the interference caused by overlapping. At the same time, considering the frequency interference problem within the group of readers, the readers in the group with the same frequency were regarded as a group, and the adjacent readers were assigned with different frequency, thus avoiding the frequency collision caused by too large interference range. Next, according to the grouping information, the time slots and the frequency resources were assigned to each reader by the central server through the arrangement command. Finally, the working order of each group of readers was assigned by the central server through the ordering commands. The simulation results showed that compared with the Neighbor-Friendly Reader Anti-Collision (NFRA) algorithm, the average work efficiency of the proposed scheme was improved by 6.5 percentage points and the efficiency of a system with 1 000 readers was improved by 9.5 percentage points. The results demonstrate that the proposed algorithm based on graph theory can optimize the number of working readers in the given time and reduce the number of idle readers.

Radio Frequency IDentification (RFID)； reader； work efficiency； graph theory； resource scheduling

TP391.45; TN92

A

2017- 01- 24;

2017- 03- 14。

國家自然科學基金資助項目(61340005)；北京市自然科學基金面上項目(4132012)；北京市教委科技發展計劃項目(KM201411232011)。

徐亞峰(1990—)，男，江西進賢人，碩士研究生，主要研究方向：無線射頻識別； 崔英花(1973—)，女，吉林蛟河人，副教授，博士，主要研究方向：無線射頻識別。

1001- 9081(2017)08- 2163- 05

10.11772/j.issn.1001- 9081.2017.08.2163