徐亞峰，崔英花

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

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

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

徐亞峰*，崔英花

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

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

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

射頻識(shí)別；閱讀器；工作效率；圖論；資源調(diào)度

0 引言

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

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

圖1 閱讀器碰撞類(lèi)型Fig. 1 Reader collision types

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

Colorwave算法[9]是基于分布式的時(shí)分復(fù)用型的防碰撞算法，所有閱讀器通過(guò)同步機(jī)制組成一個(gè)閱讀器網(wǎng)絡(luò)，每個(gè)閱讀器都被分配了對(duì)應(yīng)的時(shí)隙(顏色)，對(duì)閱讀器網(wǎng)絡(luò)的時(shí)隙的分配就相當(dāng)于圖著色問(wèn)題。但是Colorwave算法要求閱讀器之間有嚴(yán)格的時(shí)間同步，然而Ad Hoc網(wǎng)絡(luò)很難做到時(shí)間同步，閱讀器也無(wú)法探測(cè)到發(fā)生在標(biāo)簽上的碰撞。另外，閱讀器的移動(dòng)會(huì)引起時(shí)隙重新分配，使整個(gè)系統(tǒng)的效率下降。

基于Q-Learning在線強(qiáng)化學(xué)習(xí)的防沖突算法HiQ[10]采用多層結(jié)構(gòu)，通過(guò)與RFID系統(tǒng)的交流來(lái)學(xué)習(xí)閱讀器層的沖突模式，動(dòng)態(tài)地分配閱讀器頻率和時(shí)隙資源，從而實(shí)現(xiàn)防碰撞。但算法的多層結(jié)構(gòu)使閱讀器設(shè)計(jì)復(fù)雜，增加了硬件成本；而且移動(dòng)閱讀器會(huì)改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，降低系統(tǒng)的效率。

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

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

1 相關(guān)工作

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

dij

(1)

在這種情況下，閱讀器vi和vj必須在不同的時(shí)隙進(jìn)行操作才能避免發(fā)生沖突。

當(dāng)滿(mǎn)足下面的條件時(shí)，RRT和RTI都會(huì)發(fā)生：

dij

(2)

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

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

文獻(xiàn)[11]的NFRA算法開(kāi)始讓服務(wù)器廣播一個(gè)配置命令(Arrangement Command，AC)，這個(gè)命令包含開(kāi)始的回合數(shù)和隨機(jī)數(shù)(隨機(jī)數(shù)從1到N，N的取值取于閱讀器的數(shù)量)。當(dāng)閱讀器接收到配置命令后，各自生成自己1-N的隨機(jī)數(shù)，隨后服務(wù)器發(fā)送排序命令(Ordering Command， OC)，當(dāng)閱讀器自身的隨機(jī)數(shù)和OC命令的值相同時(shí)，閱讀器就向周?chē)鷱V播beacon信號(hào)，來(lái)確定是否會(huì)有碰撞發(fā)生，如果發(fā)現(xiàn)會(huì)與相鄰閱讀器產(chǎn)生碰撞，閱讀器將發(fā)送覆蓋幀(Overriding Frame，OF)給鄰近閱讀器，使鄰近閱讀器不會(huì)接受下一次的OC命令直到本回合結(jié)束，繼續(xù)等待下一回合的AC命令。那么其他沒(méi)有接收到OF的閱讀器，等待本回合下一個(gè)OC命令，若有與OC命令值相同的閱讀器，將重復(fù)上面的過(guò)程。

假設(shè)有如圖2所示的一個(gè)閱讀器場(chǎng)景，服務(wù)器開(kāi)始向它覆蓋的區(qū)域廣播AC命令，閱讀器收到命令后產(chǎn)生的隨機(jī)數(shù)(本例中隨機(jī)數(shù)范圍是1到3)。為方便表示，圖2中用i-j表示產(chǎn)生隨機(jī)數(shù)為i的閱讀器vj，如下面的描述中閱讀器2-1即指產(chǎn)生隨機(jī)為2的閱讀器v1。這個(gè)過(guò)程完成后，服務(wù)器廣播值為1的OC命令，生成的隨機(jī)數(shù)1的閱讀器開(kāi)始向鄰居閱讀器發(fā)送beacon信號(hào)，來(lái)確定周?chē)欠裼邢嗤S機(jī)數(shù)的閱讀器存在。從圖2可以看到所有隨機(jī)數(shù)為1的閱讀器之間都在各自的干擾范圍之外，不會(huì)產(chǎn)生干擾，然后這些閱讀開(kāi)始工作讀取在它們工作區(qū)域里的標(biāo)簽。同時(shí)，服務(wù)器開(kāi)始廣播值為2的OC命令，那么閱讀器2-1和2-2都開(kāi)始發(fā)送beacon信號(hào)，發(fā)現(xiàn)它們之間會(huì)產(chǎn)生相互干擾。產(chǎn)生干擾的閱讀器會(huì)放棄本回合的標(biāo)簽識(shí)別過(guò)程，直到下回合的AC命令。因?yàn)樵谏弦粋€(gè)值為1的OC命令階段，閱讀器2- 4收到來(lái)自鄰近閱讀器1-2的OF命令，因此閱讀器2- 4也不會(huì)工作。只有閱讀器2-3會(huì)嘗試進(jìn)行標(biāo)簽的識(shí)別工作。服務(wù)器又開(kāi)始廣播值為3的OC命令，生成隨機(jī)數(shù)3的閱讀器重復(fù)上述類(lèi)似的操作。閱讀器3-1和3-2由于不會(huì)發(fā)生相互碰撞，也沒(méi)有收到任何來(lái)自鄰近閱讀器的OF命令，因此可以嘗試識(shí)別標(biāo)簽。類(lèi)似的閱讀器2- 4，閱讀器3-3也不能對(duì)標(biāo)簽進(jìn)行識(shí)別工作。

圖2 多閱讀器網(wǎng)絡(luò)Fig. 2 Multi-reader network

從圖2中可以發(fā)現(xiàn)，如果僅僅只考慮時(shí)間的問(wèn)題，第一個(gè)OC命令可以同時(shí)工作的閱讀器不僅僅只是3個(gè)，實(shí)際上是5個(gè)，它們分別是閱讀器1-1,1-2,1-3,2-1和3-1。由于閱讀器本身的數(shù)值是隨機(jī)生成的，所以無(wú)法保證最大化同一時(shí)間段內(nèi)可操作的閱讀器個(gè)數(shù)，使得本可以工作的閱讀器不得不閑置等待下一次的OC命令，造成資源的浪費(fèi)。如果處于密集區(qū)域的閱讀器產(chǎn)生的隨機(jī)數(shù)值越小那么就意味著它在OC命令到來(lái)之時(shí)就越有優(yōu)先工作的可能。如果閱讀器的分布如圖3所示，可以看出閱讀器v5和v6處于最密集的區(qū)域當(dāng)中。假設(shè)閱讀器v5生成的隨機(jī)數(shù)是1，那么第一個(gè)OC命令到來(lái)時(shí)，閱讀器v5就要周?chē)拈喿x器發(fā)送beacon信號(hào)，鄰近的6個(gè)閱讀器都將被禁止在當(dāng)前AC命令下工作。相反如果處于相對(duì)較稀疏區(qū)域的閱讀器v4生成的隨機(jī)數(shù)是1，那么被禁止在當(dāng)前AC命令下工作的閱讀器只有3個(gè)。從圖3中可以知道，最壞的情況是閱讀器v5和v7生成的隨機(jī)數(shù)是1，周?chē)渌?個(gè)閱讀器都將被限制工作，直到下個(gè)AC命令的到來(lái)；而最好的情況是處于邊緣稀疏區(qū)域的閱讀器生成的隨機(jī)數(shù)是1，例如閱讀器v2,v4,v7和v9，這種情況下被限制工作的閱讀器是6個(gè)。如果閱讀器的數(shù)量是巨大的，那么將能極大地改善整個(gè)閱讀器網(wǎng)絡(luò)資源的利用，提高系統(tǒng)的工作效率。

圖3 密集閱讀器網(wǎng)絡(luò)例子Fig. 3 Example of dense reader network

通過(guò)上面的分析，可以知道上述缺陷都是由于隨機(jī)這個(gè)機(jī)制所導(dǎo)致的，并且NFRA算法也沒(méi)有考慮到RRI的問(wèn)題?；氐綀D2中，當(dāng)閱讀器2-1和2-2使用相同的頻率同時(shí)向周?chē)l(fā)送beacon信號(hào)，由于干擾的存在，鄰近閱讀器并不一定能正確接收這個(gè)beacon信號(hào)，那么閱讀器之間的干擾依然會(huì)存在。 因此需要解決潛在的頻率干擾問(wèn)題，同時(shí)最大化每個(gè)OC命令可操作的閱讀器數(shù)量。這就是本文提出的算法所需要解決的事情。

2 本文算法

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

首先來(lái)討論時(shí)隙的問(wèn)題。在密集的閱讀器網(wǎng)絡(luò)G中來(lái)對(duì)閱讀器vi進(jìn)行分組，閱讀器的分組要滿(mǎn)足下面的條件：

1) 組內(nèi)閱讀器任意兩個(gè)成員vi,vj之間滿(mǎn)足：

dij>ri+rj

(3)

此時(shí)任意兩個(gè)閱讀器vi,vj之間對(duì)于時(shí)隙的分配滿(mǎn)足：

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

(4)

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

2) 組內(nèi)閱讀器成員數(shù)是極大的。當(dāng)閱讀器網(wǎng)絡(luò)G中任意不屬于該組的閱讀器vk加入該組后，會(huì)導(dǎo)致：

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

(5)

即組內(nèi)再增加任何一個(gè)閱讀器后都會(huì)有干擾產(chǎn)生，不能在同一時(shí)隙內(nèi)工作。

由于組內(nèi)閱讀器成員可以在同一個(gè)時(shí)隙內(nèi)工作，那么每一組就可以代表一個(gè)時(shí)隙ti，時(shí)隙的先后順序要取決于組內(nèi)閱讀器的成員數(shù)，按照數(shù)量由大到小的順序進(jìn)行排序。按顏色對(duì)閱讀器網(wǎng)絡(luò)分組，每一種顏色代表一個(gè)時(shí)隙，下面進(jìn)行詳細(xì)分析。

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

然后來(lái)討論頻率干擾的問(wèn)題，對(duì)于已經(jīng)分好顏色ci的閱讀器之間，雖然可以在同一時(shí)隙內(nèi)工作，但由于閱讀器的干擾范圍遠(yuǎn)大于閱讀器的識(shí)別范圍，當(dāng)閱讀器之間不滿(mǎn)足下面的條件：

dij>ri+Ij

(6)

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

圖4 服務(wù)器配置命令格式

Fig. 4 Server configuration command format

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

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

步驟2 服務(wù)器根據(jù)式(6)對(duì)步驟1中已經(jīng)分好組的閱讀器組內(nèi)再分組，此時(shí)分配的是頻率資源。

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

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

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

3 實(shí)例說(shuō)明

假設(shè)有如圖5(a)所示的一個(gè)相對(duì)密集的閱讀器網(wǎng)絡(luò)，圖中閱讀器的碰撞情況很?chē)?yán)重，把每個(gè)閱讀器vi看成是無(wú)向圖G1的一個(gè)頂點(diǎn)，如果兩個(gè)閱讀之間的距離滿(mǎn)足式(1)，那么就把這兩個(gè)閱讀器看作是相鄰的，這些閱讀器組成的無(wú)向圖G1如圖5(b)所示。

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

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

圖5 密集閱讀器轉(zhuǎn)換與著色實(shí)例Fig. 5 Example for conversion and coloring of dense readers

在實(shí)際的RFID閱讀器網(wǎng)絡(luò)中，閱讀器的數(shù)量巨大，那么相應(yīng)的無(wú)向圖的頂點(diǎn)也非常多，這種情況下通常采用貪心法來(lái)給無(wú)向圖的頂點(diǎn)著色[12]，但是基本思想是一致的。

服務(wù)器在完成了上述工作后，已經(jīng)對(duì)每個(gè)閱讀器分配好了工作的時(shí)隙和頻率，只需要向閱讀廣播資源配置命令，其格式如圖4所示，閱讀器接收到命令后存儲(chǔ)被分配的資源信息，然后根據(jù)時(shí)序命令開(kāi)始工作。

4 仿真與分析

閱讀器防碰撞算法的目的是在沒(méi)有相互干擾的情況下，盡可讓更多的閱讀器能同時(shí)工作，因此算法的性能可以用在給定的時(shí)間內(nèi)同時(shí)工作的閱讀器數(shù)量來(lái)評(píng)估。定義每毫秒工作的閱讀器的數(shù)量為系統(tǒng)的工作效率。下面對(duì)本文算法和NFRA算法在同等條件下進(jìn)行仿真比較。

在實(shí)際的倉(cāng)儲(chǔ)管理系統(tǒng)中，RFID系統(tǒng)需要對(duì)每個(gè)入庫(kù)的產(chǎn)品進(jìn)行數(shù)據(jù)的錄入，管理盤(pán)點(diǎn)這些產(chǎn)品的數(shù)量等信息。為了能覆蓋整個(gè)倉(cāng)庫(kù)的產(chǎn)品，系統(tǒng)必須在倉(cāng)庫(kù)中放置多個(gè)閱讀器。

實(shí)驗(yàn)條件：假設(shè)有一個(gè)20 m×20 m的倉(cāng)庫(kù)，為了體現(xiàn)算法的一般性，在這個(gè)區(qū)域中隨機(jī)放置數(shù)量不同的閱讀器，閱讀器數(shù)量分別為100，200，…，1 000；假設(shè)閱讀的讀取范圍為2 m，干擾范圍為6 m；閱讀器識(shí)別100個(gè)標(biāo)簽需要的時(shí)間是0.46 ms,服務(wù)器的AC命令時(shí)長(zhǎng)為2.83 ms，OC命令時(shí)長(zhǎng)為1 ms[11]。由于在同等條件下是否考慮路徑損耗都不會(huì)影響算法的性能比較，因此實(shí)驗(yàn)環(huán)境的路徑損耗設(shè)置為理想環(huán)境。通過(guò)多次實(shí)驗(yàn)仿真取平均值，得到如圖6所示的結(jié)果。

實(shí)驗(yàn)仿真結(jié)果表明，本文算法的工作效率要優(yōu)于NFRA算法。當(dāng)閱讀器數(shù)目為100時(shí)，本文算法比NFRA算法的工作效率提升了1.5個(gè)百分點(diǎn)；閱讀器數(shù)目為200時(shí)，系統(tǒng)效率提升3.1個(gè)百分點(diǎn)；當(dāng)閱讀器數(shù)目達(dá)到1 000時(shí)系統(tǒng)的效率提升了9.5個(gè)百分點(diǎn)；隨著閱讀器數(shù)量的增多，本文算法相比NFRA算法體現(xiàn)出更大的優(yōu)越性，系統(tǒng)的平均工作效率提升了6.5個(gè)百分點(diǎn)。而且隨著閱讀器數(shù)量的不斷增多，本文算法性能將趨于一個(gè)相對(duì)平穩(wěn)的增長(zhǎng)狀態(tài)。

當(dāng)閱讀器數(shù)目越多，網(wǎng)絡(luò)環(huán)境越密集，本文算法相比NFRA算法更加有效率，能更快速讀取需被識(shí)別物體的信息。在實(shí)際龐大的倉(cāng)儲(chǔ)系統(tǒng)管理中，能夠減少產(chǎn)品入庫(kù)信息存儲(chǔ)的時(shí)間，提高工作效率。

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

5 結(jié)語(yǔ)

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

References)

[1] 吳歡歡,周建平,許燕,等.RFID發(fā)展及其應(yīng)用綜述[J].計(jì)算機(jī)應(yīng)用與軟件,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標(biāo)簽閱讀器系統(tǒng)防沖突算法的研究[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] 劉瑋,吳曉波,張偉偉,等.基于調(diào)度方式的閱讀器防碰撞算法[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傳感網(wǎng)絡(luò)中多閱讀器碰撞算法的研究[J].傳感技術(shù)學(xué)報(bào),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環(huán)境下利用通報(bào)機(jī)制的分布式閱讀器防沖突算法[J/OL].計(jì)算機(jī)應(yīng)用研究, [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] 王宇,甘健侯.一種分布式全類(lèi)型RFID閱讀器碰撞解決方案[J].電子技術(shù)應(yīng)用,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系統(tǒng)閱讀器反碰撞算法分類(lèi)與研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,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系統(tǒng)中多閱讀器環(huán)境下防碰撞問(wèn)題的研究[D].武漢：武漢理工大學(xué),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] 馮珊珊.基于圖著色理論的聚類(lèi)研究[D].太原:太原理工大學(xué),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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61340005)；北京市自然科學(xué)基金面上項(xiàng)目(4132012)；北京市教委科技發(fā)展計(jì)劃項(xiàng)目(KM201411232011)。

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

1001- 9081(2017)08- 2163- 05

10.11772/j.issn.1001- 9081.2017.08.2163