王瑞佳，趙菊敏

（太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600）

在大型場景中，標(biāo)簽密集部署且分布廣泛，需采用多閱讀器識別模式[1]。在多閱讀器識別模式中，為了避免標(biāo)簽漏讀的情況，閱讀器的識別范圍出現(xiàn)大面積重疊，使碰撞可能性增大[2]，導(dǎo)致了標(biāo)簽識別吞吐量的減少及識別延遲的增加，嚴(yán)重影響系統(tǒng)的識別效率[3]。

現(xiàn)研究階段的閱讀器防碰撞算法主要分為基于功率調(diào)節(jié)的閱讀器防碰撞算法、基于調(diào)度的閱讀器防碰撞算法[4]。這兩種調(diào)度方法在閱讀器碰撞較多的大規(guī)模場景[5]中，需要進(jìn)行多輪的調(diào)度，整體系統(tǒng)效率低下，且占用資源較多[6]。因此，迫切需要解決大規(guī)模場景中閱讀器的碰撞問題。

1 基于反向權(quán)重的防碰撞算法

基于反向權(quán)重的閱讀器防碰撞算法提出用反向權(quán)重圖的方法表示閱讀器碰撞關(guān)系；設(shè)置控制通道各個閱讀器共享信息；設(shè)置碰撞閾值，簡化閱讀器碰撞情況；定義閱讀器優(yōu)先級,實(shí)現(xiàn)動態(tài)調(diào)度。

1.1 反向權(quán)重結(jié)構(gòu)圖的概念

在大規(guī)模場景中閱讀器的碰撞情況復(fù)雜，在無向圖中會出現(xiàn)多條連接不直觀的情況。因此該文提出反向權(quán)重結(jié)構(gòu)圖的概念。反向權(quán)重結(jié)構(gòu)是指類似于多個多叉樹的結(jié)構(gòu)，一顆多叉樹代表與其他閱讀器沒有碰撞的集合。兩個節(jié)點(diǎn)之間若有連接關(guān)系，則表示存在碰撞關(guān)系。節(jié)點(diǎn)代表閱讀器，將與父節(jié)點(diǎn)有碰撞的全部閱讀器作為該父節(jié)點(diǎn)的子節(jié)點(diǎn)。閱讀器分布簡圖如圖1 所示,根據(jù)圖1 得到閱讀器的反向權(quán)重結(jié)構(gòu)圖如圖2 所示。

圖1 閱讀器分布簡圖

圖2 反向權(quán)重結(jié)構(gòu)圖

1.2 閱讀器優(yōu)先級定義

文中算法的目的在于將閱讀器集合映射為森林，森林?jǐn)?shù)越多，則代表閱讀器獨(dú)立集越多，可以并行工作的閱讀器數(shù)量就越多，系統(tǒng)的工作效率也就越高。因此該算法采用優(yōu)先級的調(diào)度方式。該文定義閱讀器優(yōu)先級如式（1）所示:

等待時間參數(shù)使短時間的作業(yè)優(yōu)先運(yùn)行，提高了系統(tǒng)的吞吐率；節(jié)點(diǎn)入度可簡化后續(xù)閱讀器的調(diào)度分配；等待時間保證了系統(tǒng)的公平性。每個閱讀器工作完成后，系統(tǒng)會更新反向權(quán)重結(jié)構(gòu)圖，閱讀器的入度會相應(yīng)的改變，因此每個閱讀器的優(yōu)先級也會發(fā)生相應(yīng)的改變，且每個無碰撞的閱讀器會實(shí)時加入識別隊(duì)列中，整個系統(tǒng)以一種動態(tài)的反向權(quán)重結(jié)構(gòu)的調(diào)度方式工作，兼顧了系統(tǒng)的效率和公平性。

為了使以上描述更為清晰，進(jìn)行了舉例說明。假設(shè)閱讀器的碰撞情況如圖1 中重疊部分所示，各個閱讀器的識別時間如表1 所示。

表1 閱讀器識別時間

各個閱讀器開始時等待時間均為0 s，閱讀器優(yōu)先級如表2 所示。

表2 閱讀器優(yōu)先級

第一輪選擇運(yùn)行狀態(tài)的閱讀器集合過程如圖3所示。

圖3 第一次輪選擇閱讀器集合過程

1.3 碰撞隊(duì)列和識別狀態(tài)的設(shè)置

文中算法為了盡量避免消息延時的情況，選擇使用分布式構(gòu)架，并通過設(shè)置控制通道使閱讀器之間可以共享信息。控制通道上發(fā)送閱讀器開始識別（start）和結(jié)束識別（end）的消息。為節(jié)省資源，“start”以“S”代替，“end”以“E”代替。為每個閱讀器建立碰撞隊(duì)列和狀態(tài)信息。

微生物肥料已成為新型肥料中年產(chǎn)量最大、應(yīng)用面積最廣的品種，預(yù)計(jì)到“十三五”結(jié)束時，年總產(chǎn)量比現(xiàn)在翻一番——

碰撞隊(duì)列：存放碰撞閱讀器識別狀態(tài)的隊(duì)列。隊(duì)列的長度為每個閱讀器在樹形結(jié)構(gòu)圖中的入度。一個隊(duì)列長度中存放產(chǎn)生碰撞的閱讀器編號信息。

識別狀態(tài)：用來區(qū)分閱讀器的工作狀態(tài)，以挑選無碰撞的閱讀器獨(dú)立集服務(wù)。分為等待狀態(tài)、就緒狀態(tài)、運(yùn)行狀態(tài)和結(jié)束狀態(tài)。

等待狀態(tài)：所有閱讀器剛開始的識別狀態(tài)為等待狀態(tài)，或者碰撞隊(duì)列中存在閱讀器信息時，該閱讀器為等待狀態(tài)。

就緒狀態(tài)：碰撞隊(duì)列中沒有閱讀器，可以加入識別隊(duì)列的閱讀器的狀態(tài)。

運(yùn)行狀態(tài)：正在識別的閱讀器的狀態(tài)。

結(jié)束狀態(tài)：完成識別的閱讀器的狀態(tài)。

剛開始時，所有的閱讀器都為等待狀態(tài)，在第一輪通過閱讀器優(yōu)先級遍歷反向權(quán)重結(jié)構(gòu)圖后，將選擇出的獨(dú)立集閱讀器改為就緒狀態(tài)，開始識別時各閱讀器的狀態(tài)變?yōu)檫\(yùn)行狀態(tài)。運(yùn)行狀態(tài)中的閱讀器需要向其他閱讀器發(fā)送自己的識別信息，為了避免控制通道信息的碰撞，各閱讀器按照優(yōu)先級的順序在控制通道上廣播帶有自己編號和“S”的信息，周圍閱讀器將廣播中的信息存儲到自己隊(duì)列信息中。閱讀器若監(jiān)聽到一個閱讀器的“E”信息后，檢查自己的隊(duì)列信息，并將該閱讀器的信息從隊(duì)列中清除。若此時隊(duì)列不為空，保持等待狀態(tài)。若此時閱讀器隊(duì)列為空，則轉(zhuǎn)為就緒狀態(tài)。當(dāng)監(jiān)聽到“E”信息后，等待T時間若沒有新的“E”信息，則更新反向權(quán)重結(jié)構(gòu)圖。其中，等待T時間是因?yàn)橥瑫r完成識別的閱讀器根據(jù)優(yōu)先級的大小，先后發(fā)送“E”信息，時間間隔為T。若就緒狀態(tài)中出現(xiàn)與之有碰撞情況的閱讀器，則比較兩個閱讀器的優(yōu)先級，若優(yōu)先級高則進(jìn)入運(yùn)行狀態(tài)，優(yōu)先級低則進(jìn)入等待狀態(tài)。識別完成后的閱讀器將狀態(tài)改為結(jié)束狀態(tài)。

1.4 算法具體步驟

基于反向權(quán)重的閱讀器防碰撞算法的具體實(shí)現(xiàn)步驟為：

1）根據(jù)閱讀器碰撞情況畫出反向權(quán)重結(jié)構(gòu)圖。

2）在每一棵樹上選擇優(yōu)先級最高的閱讀器，將閱讀器的等待狀態(tài)改為就緒狀態(tài)。

3）以就緒狀態(tài)節(jié)點(diǎn)為首節(jié)點(diǎn)，遍歷反向權(quán)重結(jié)構(gòu)圖，挑選無碰撞的閱讀器集合，將其狀態(tài)改變?yōu)榫途w狀態(tài)。

4）遍歷完成后，使所有就緒狀態(tài)的閱讀器開始識別，狀態(tài)變?yōu)檫\(yùn)行狀態(tài)。

5）運(yùn)行狀態(tài)的閱讀器按照優(yōu)先級在控制通道上廣播自己的編號以及“S”信息。

6）等待狀態(tài)的閱讀器不斷監(jiān)聽控制通道的信息。當(dāng)閱讀器監(jiān)聽到某一個閱讀器編號及“S”信息后，將該閱讀器編號放入自己的碰撞隊(duì)列中。當(dāng)閱讀器監(jiān)聽到某一個閱讀器編號及“E”信息，檢查自己的碰撞隊(duì)列，將該編號從隊(duì)列中刪除。

7）等待T時間。更新反向權(quán)重結(jié)構(gòu)圖。將結(jié)束狀態(tài)的閱讀器從結(jié)構(gòu)圖中刪除，重新調(diào)整閱讀器之間的碰撞關(guān)系。

8）判斷反向權(quán)重結(jié)構(gòu)圖中是否還有節(jié)點(diǎn)，若有則繼續(xù)執(zhí)行，若無則直接執(zhí)行步驟11）。

9）等待狀態(tài)的閱讀器檢查碰撞隊(duì)列是否為空，若為空將等待狀態(tài)轉(zhuǎn)為就緒狀態(tài)，若不為空，則繼續(xù)監(jiān)聽控制通道的信息。

10）就緒狀態(tài)的閱讀器根據(jù)反向權(quán)重結(jié)構(gòu)檢查是否存在有碰撞情況的閱讀器，若無，則將就緒狀態(tài)轉(zhuǎn)為運(yùn)行狀態(tài)，開始識別；若有，則根據(jù)反向權(quán)重結(jié)構(gòu)圖計(jì)算閱讀器優(yōu)先級，將優(yōu)先級高的閱讀器加入識別隊(duì)列，狀態(tài)改為運(yùn)行狀態(tài)，將優(yōu)先級低的閱讀器轉(zhuǎn)為等待狀態(tài)，繼續(xù)監(jiān)聽控制通道信息。

11）閱讀器識別完畢，系統(tǒng)工作完成。

2 仿真實(shí)驗(yàn)和性能比較

該節(jié)將通過仿真手段驗(yàn)證文中提出的基于反向權(quán)重的閱讀器防碰撞算法（FLSM），并將其與最小反向權(quán)重的閱讀器防碰撞算法（MRWA）、傳統(tǒng)的極大獨(dú)立集閱讀器防碰撞算法（MISR）以及經(jīng)典的閱讀器調(diào)度算法NFRA++進(jìn)行性能比較。在模擬實(shí)驗(yàn)中，0～500 個閱讀器和200～10 000 個標(biāo)簽均勻分布在長度和寬度都為200 m 的區(qū)域中，將閱讀器識別半徑設(shè)置為7 m。服務(wù)器主要用于時間同步和給閱讀器發(fā)送指令，服務(wù)器半徑R=100 m。

圖4 表示400 個閱讀器均勻分布在識別場景中，各個算法識別標(biāo)簽數(shù)目的對比。從圖中可以看出，各個算法都具有相同的變化趨勢，隨著時隙數(shù)的增加，識別標(biāo)簽的數(shù)目先增加，然后都趨向于穩(wěn)定。從整體效果可以看出，該文提出的算法識別標(biāo)簽個數(shù)最多、算法性能最好。

圖4 各個算法識別標(biāo)簽數(shù)量對比

圖5 是各個算法激活所有閱讀器所用幀數(shù)的對比?；谡{(diào)度的閱讀器防碰撞算法主要目的在于找到最大個數(shù)的無碰撞閱讀器集合，使其并行工作以提高整體識別效率。從圖中可以看出，該文提出的算法激活所有閱讀器所用幀數(shù)最少。因?yàn)樵撐奶岢龅姆琅鲎菜惴ㄔ陂喿x器調(diào)度過程中將閱讀器碰撞入度考慮在內(nèi)，更快地消除了閱讀器之間的碰撞問題，因此該算法激活所有閱讀器所用幀數(shù)最少。

圖5 激活閱讀器所用時隙數(shù)對比

圖6 為各算法在相同識別環(huán)境中吞吐量的比較。從圖中可以看出，該文算法吞吐量呈現(xiàn)穩(wěn)定上升的趨勢。因?yàn)闃?biāo)簽數(shù)量少時，閱讀器碰撞和標(biāo)簽碰撞都相對較少，閱讀器識別個數(shù)并沒有達(dá)到飽和，所以隨著激活閱讀器個數(shù)的增加，系統(tǒng)吞吐量呈現(xiàn)上升的趨勢。隨著標(biāo)簽數(shù)量的增多，閱讀器之間的碰撞和標(biāo)簽之間的碰撞增加，閱讀器識別個數(shù)最終會趨于穩(wěn)定。從圖中可以看出，該文提出的算法吞吐量最高。

圖6 吞吐量對比

3 結(jié)束語

針對大規(guī)模閱讀器碰撞問題，該文提出了基于反向權(quán)重閱讀器防碰撞算法，該算法利用反向權(quán)重結(jié)構(gòu)圖表示閱讀器之間的碰撞信息；根據(jù)閱讀器優(yōu)先級實(shí)現(xiàn)閱讀器之間的動態(tài)調(diào)度。該算法不僅解決了傳統(tǒng)功率調(diào)節(jié)閱讀器防碰撞算法標(biāo)簽漏讀的問題，而且在大規(guī)模射頻識別系統(tǒng)表現(xiàn)出了良好的性能。