RFID閱讀器網(wǎng)絡(luò)分布式自適應(yīng)信號(hào)覆蓋算法研究*

戴宏躍，廖 慧

（廣州科技貿(mào)易職業(yè)學(xué)院智能制造學(xué)院，廣州 511442）

0 引言

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

圖1 連續(xù)結(jié)問(wèn)題Fig.1 The difficulty of interrupting continuous node

從RRE算法的仿真的結(jié)果來(lái)看，其效果并不理想?；诖?，本文提出了一種閱讀器分布式適應(yīng)性覆蓋（Distributed Adaptive Coverage，DAC）算法。該算法旨在把RFID系統(tǒng)中相關(guān)的冗余閱讀器找出來(lái)，后續(xù)可以使用相關(guān)命令關(guān)閉這些冗余閱讀器，是整個(gè)系統(tǒng)具有最優(yōu)數(shù)量的閱讀器工作。

1 DAC算法設(shè)計(jì)

在提出本文的算法之前，首先根據(jù)實(shí)際情況，做如下設(shè)定。

（1）DAC算法可以應(yīng)用與任何數(shù)量的RFID閱讀器與標(biāo)簽，認(rèn)為閱讀器與標(biāo)簽的拓?fù)浣Y(jié)構(gòu)在某一短時(shí)間段內(nèi)是固定的。閱讀器網(wǎng)絡(luò)中不存在能夠協(xié)調(diào)閱讀器之間工作行為的中央控制器。DAC算法不依賴于閱讀器之間的通信能力。

（2）每個(gè)閱讀器都有自己唯一的ID，用來(lái)作為信息交流的身份識(shí)別。

（3）本文僅僅考慮無(wú)源標(biāo)簽，因此，標(biāo)簽以接收到的信號(hào)的能量來(lái)應(yīng)答閱讀器的相關(guān)命令。

（4）標(biāo)簽具有有限的存儲(chǔ)空間，其中一部分是只讀的，用來(lái)存儲(chǔ)唯一的標(biāo)識(shí)；一部分是可讀寫的，供閱讀器讀寫。

（5）標(biāo)簽具有命令匹配能力。根據(jù)不同的命令能做出不同的反應(yīng)，或者根據(jù)命令不同的參數(shù)做出相應(yīng)的動(dòng)作。

（6）當(dāng)多個(gè)標(biāo)簽應(yīng)答同一個(gè)命令時(shí)，閱讀器具有沖突探測(cè)能力。

1.1 DAC算法過(guò)程

為了提高閱讀器的覆蓋效率，探測(cè)出并關(guān)閉或休眠RFID閱讀器網(wǎng)絡(luò)中的冗余閱讀器，減少覆蓋重?cái)?shù)，本文提出了該DAC算法。在閱讀器網(wǎng)絡(luò)拓?fù)渲?，假設(shè)閱讀器之間不能直接通信，但是由于有可讀寫的標(biāo)簽存在，能夠存儲(chǔ)它所屬閱讀器的請(qǐng)求信息，因此可以利用標(biāo)簽作中間媒介，閱讀器之間可以間接進(jìn)行信息傳遞。每個(gè)閱讀器具有預(yù)先收集其讀寫區(qū)域內(nèi)所有標(biāo)簽信息，閱讀器網(wǎng)絡(luò)中所有閱讀器都能執(zhí)行該功能。閱讀器在不同的時(shí)隙中工作，最大可能地避免沖突情況的發(fā)生，然后再執(zhí)行DAC算法。DAC算法主要由3步組成。

（1）每個(gè)閱讀器在隨機(jī)時(shí)隙中收集它所覆蓋的標(biāo)簽數(shù)目，保證每個(gè)閱讀器能盡快獲取本身所覆蓋標(biāo)簽數(shù)。

（2）每個(gè)閱讀器嘗試將它所覆蓋的標(biāo)簽數(shù)目以及閱讀器本身的ID寫入其所覆蓋的所有標(biāo)簽中，但是標(biāo)簽僅僅存儲(chǔ)最大數(shù)目值及相應(yīng)閱讀器的ID。具體實(shí)現(xiàn)過(guò)程是每個(gè)閱讀器都發(fā)送包含閱讀器ID與它所覆蓋標(biāo)簽數(shù)目的寫入標(biāo)簽命令，命令的格式如圖2所示，處于該閱讀器讀寫區(qū)域內(nèi)的標(biāo)簽收到命令后，首先進(jìn)行命令參數(shù)匹配，如果命令中包含的標(biāo)簽數(shù)目比標(biāo)簽已存在的數(shù)值大，即認(rèn)為命令有效，執(zhí)行寫操作，將標(biāo)簽內(nèi)已存儲(chǔ)的標(biāo)簽數(shù)目值與閱讀器ID數(shù)據(jù)刷新。反之，如果命令中包含的標(biāo)簽數(shù)目比標(biāo)簽已存在的數(shù)值小，則不作響應(yīng)。

圖2 標(biāo)簽命令結(jié)構(gòu)Fig.2 The command structure of the tag

（3）閱讀器查詢讀寫區(qū)域內(nèi)的每個(gè)標(biāo)簽，讀取標(biāo)簽中所存儲(chǔ)的閱讀器ID。對(duì)于某一覆蓋較多標(biāo)簽的閱讀器，其讀寫區(qū)域內(nèi)的多個(gè)標(biāo)簽可能同時(shí)具有該閱讀器的ID，因?yàn)樵撻喿x器覆蓋了這些標(biāo)簽，而且標(biāo)簽數(shù)目較多，因此在前一步的工作中該閱讀器可能已將自己的ID寫入這些標(biāo)簽，導(dǎo)致該閱讀器在這一步操作中，在多個(gè)標(biāo)簽中獲取到該ID值。至少能獲取一個(gè)標(biāo)簽ID的閱讀器保留活動(dòng)狀態(tài)，而沒(méi)有獲取到任何ID的閱讀器可以安全關(guān)閉，由于該閱讀器所覆蓋的標(biāo)簽數(shù)目較少，而且該閱讀器所覆蓋的所有標(biāo)簽同時(shí)已被其他的覆蓋標(biāo)簽數(shù)目較多的處于活動(dòng)狀態(tài)的閱讀器所覆蓋，這樣在前一步的操作中，該閱讀器所覆蓋的標(biāo)簽已將其存儲(chǔ)的ID值更新了。

為了避免沖突情況，提高工作的可靠性，閱讀器對(duì)它所覆蓋標(biāo)簽發(fā)送的命令可以在上述設(shè)置的隨機(jī)時(shí)隙內(nèi)重復(fù)發(fā)送。

1.2 DAC算法實(shí)現(xiàn)

根據(jù)前面對(duì)標(biāo)簽命令的設(shè)計(jì)，定義如圖3所示的描述標(biāo)簽的主要數(shù)據(jù)結(jié)構(gòu)，各變量的含義如圖中注釋所示。

圖3 標(biāo)簽的數(shù)據(jù)結(jié)構(gòu)Fig.3 Data structure of the tag

圖4所示為讀寫標(biāo)簽的C語(yǔ)言算法過(guò)程的偽代碼，算法描述了在可讀寫標(biāo)簽中，如果閱讀器發(fā)送過(guò)來(lái)的命令為寫標(biāo)簽命令，則首先比較命令中的覆蓋標(biāo)簽數(shù)值與標(biāo)簽內(nèi)現(xiàn)存的值，如果命令中的覆蓋標(biāo)簽數(shù)目值大于標(biāo)簽內(nèi)現(xiàn)存的值，則更新標(biāo)簽內(nèi)該值與閱讀器ID（圖中第6~9行）。當(dāng)接收到的命令為讀命令，則標(biāo)簽返回一個(gè)包含存儲(chǔ)在標(biāo)簽里的標(biāo)簽標(biāo)識(shí)符、閱讀器ID與覆蓋值的數(shù)據(jù)包。

圖4 讀寫標(biāo)簽算法過(guò)程偽代碼Fig.4 The pseudo codeof reading and writing tag

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

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

當(dāng)某一閱讀器確定為冗余閱讀器以后，就可以通過(guò)相關(guān)命令關(guān)閉該閱讀器，減小閱讀器信號(hào)的沖撞，提高閱讀器信號(hào)的覆蓋效率。因此，對(duì)于同一區(qū)域，相同標(biāo)簽情況下，算法能夠探測(cè)出的冗余閱讀器數(shù)量越多，說(shuō)明需要開(kāi)啟的閱讀器數(shù)量越少，即只需要少量閱讀器就能實(shí)現(xiàn)對(duì)整個(gè)區(qū)域的信號(hào)覆蓋。

2 仿真結(jié)果與分析

在第一個(gè)試驗(yàn)中，在500 m×500 m的區(qū)域，隨機(jī)部署了500個(gè)閱讀器，標(biāo)簽的數(shù)目從1 000~8 000，為了減小閱讀器信號(hào)覆蓋的重?cái)?shù)，避免信號(hào)沖突，本文重檢測(cè)DAC算法與RRE算法找出的冗余閱讀器數(shù)目的能力，圖6所示為該試驗(yàn)的仿真結(jié)果。從仿真的結(jié)果可以看出，對(duì)于小規(guī)模部署的標(biāo)簽數(shù)目，兩種算法都比較接近，因?yàn)樵谛∫?guī)模部署的標(biāo)簽時(shí)，信號(hào)沖撞的情況相對(duì)較少，兩種算法差別不大。但是隨著區(qū)域中標(biāo)簽數(shù)量的增多，兩算法探測(cè)到的冗余閱讀器數(shù)量也隨之減少。但DAC算法探測(cè)出的冗余閱讀器數(shù)量一直比RRE算法的數(shù)量大，說(shuō)明同一區(qū)域內(nèi)，DAC算法支撐下，能探測(cè)出更多的冗余閱讀器，所需活動(dòng)閱讀器的數(shù)量更少，覆蓋效率更高。

圖6 使用驗(yàn)證

圖6 冗余閱讀器數(shù)量隨標(biāo)簽數(shù)量變化關(guān)系Fig.6 The relationship between the number of redundant reader and tags

圖7所示為當(dāng)標(biāo)簽數(shù)量恒為4 000，隨機(jī)部署的閱讀器的數(shù)量從50增加到1 000時(shí)，DAC與RRE算法探測(cè)出冗余閱讀器數(shù)量情況。從圖中顯示的結(jié)果來(lái)看，當(dāng)閱讀器總數(shù)很少的時(shí)候，即閱讀器部署稀疏的情況來(lái)說(shuō)，很少有冗余閱讀器問(wèn)題，隨著閱讀器總數(shù)量的增多，閱讀器部署的密度的越來(lái)越大，信號(hào)沖撞問(wèn)題加劇，于是出現(xiàn)了越來(lái)越多的冗余閱讀器，對(duì)比可以看出，DAC的結(jié)果一直在RRE之上，說(shuō)明需要活動(dòng)的閱讀器相對(duì)較少，只需要少量的閱讀器就能完成整個(gè)區(qū)域的信號(hào)覆蓋，從另一方面說(shuō)了DAC算法的高性能。

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

3 結(jié)束語(yǔ)

本文分析了RFID系統(tǒng)相關(guān)的信號(hào)防沖撞算法的優(yōu)缺點(diǎn)，根據(jù)RFID閱讀器網(wǎng)絡(luò)的特點(diǎn)，重點(diǎn)研究分析RRE算法存在的問(wèn)題，提出了一種分布式適應(yīng)性覆蓋算法（DAC），仿真結(jié)果表明，在相同環(huán)境下，DAC算法能夠探測(cè)到冗余閱讀器的數(shù)量更多，在該算法支持下，需要活動(dòng)的閱讀器數(shù)量更少，信號(hào)沖撞的情況便隨之降低，驗(yàn)證了DAC算法能在密集環(huán)境下的性能明顯優(yōu)于RRE算法，具有很好的適應(yīng)性，可以有效提高閱讀器網(wǎng)絡(luò)的覆蓋效率，減小信號(hào)沖突，達(dá)到了預(yù)期的目的。