RFID定位系統中內存點位置信息傳輸算法

葉志祥， 張渭樂

(1.廣東科學技術職業學院 經濟管理學院，廣東 珠海 519090;2.西安交通大學 智能網絡與網絡安全教育部重點實驗室，陜西 西安 710061)

?

·計算機技術應用·

RFID定位系統中內存點位置信息傳輸算法

葉志祥1， 張渭樂2

(1.廣東科學技術職業學院 經濟管理學院，廣東 珠海 519090;2.西安交通大學 智能網絡與網絡安全教育部重點實驗室，陜西 西安 710061)

當前的RFID定位系統往往以固定式集中式基礎設施為基礎進行位置估計，系統的延時較大、可擴展性有限，往往難以應用在物聯網大規模動態場景中。為此，提出一種內存點的位置信息傳輸算法。首先，各個異構非協調性移動RFID閱讀器通過間接合作對移動或固定式RFID貼標對象進行定位，然后利用已知智能環境中的可用內存點來傳輸位置信息，最后移動RFID利用這些內存點來存儲標簽位置和實現檢索，使得RFID互相之間不進行直接通信就可以交換位置信息?；趎s-3的全面仿真實驗結果表明，在多種環境配置下，本文算法的定位延時和平均開銷均優于典型的拉引式傳輸算法。

無線射頻識別技術; 定位系統； 內存點； 閱讀器； 延時； 平均開銷

0 引 言

物聯網 (Internet of Things,IoT)[1-2]可定義為一個由智能對象構成的分布式系統，這些對象被無縫集成到信息網絡中，通過英特網提供各種智能服務。IoT的原理是利用空間分散布置的智能對象，為用戶提供更為方便的背景感知和位置感知服務。確定智能對象的位置以及位置信息的可用性，是IoT應用的重要需求。無線射頻識別技術(Radio Frequency Identification,RFID)技術是IoT的支撐技術[3-4]，它具有多種獨特屬性，使其有能力提供高性價比、可靠、靈活、高擴展性的定位服務。一般而言，RFID系統由一組標簽(主動式、被動式、半被動式)和一組閱讀器構成。人們已經為移動式/固定式貼標對象和移動式閱讀器開發了多種RFID定位系統[5-6]。然而這些系統往往以固定式集中式基礎設施為基礎進行位置估計，系統的可擴展性有限，往往難以應用在IoT大規模動態場景中。為此，本文提出一種分布式RFID定位和位置信息傳輸算法，利用異構非協調式移動RFID閱讀器，可高效確定RFID貼標對象的位置，從而為推廣IoT中位置感知服務的應用提供技術支撐。

人們已經提出了多種基于RFID技術的定位系統。文獻[7]將標簽安裝于地板上，并呈正方形排列。當閱讀器檢測到這些標簽上的部分標簽時，由于已經知道了它們的位置，所以通過使用加權平均方法可以估計出它的位置。然而，為了提高精度，必須要降低標簽間的距離。因此，需要大量標簽，增加了系統成本。文獻[8]給出了另一種類似系統，在提高定位精度的同時，通過將大量標簽部署為三角形，降低了標簽使用量。為了避免參考標簽密集部署，文獻[9]中的SLAC-RF提出一種稱為超級標簽的專用標簽。每個超級標簽是多個RFID標簽的集合，這些標簽通過一定排列來模擬虛擬天線陣列。探測一定區域的移動閱讀器利用接收信號相對于超級標簽的相位差以及慣性導航系統測量值來估計位置。雖然該系統的性價比和精度較高，而且基礎設施部署起來比較簡單，但是它們只能支持自主式移動機器人應用。

另外，文獻[10]中的SpotON系統利用聚合算法來定位標簽位置，忽略了環境動態變化導致的測量不確定性。文獻[11]中的LANDMARC系統以指紋技術為基礎，為了降低RSS測量的不確定性影響，提升精度，引入了參考標簽概念以校準環境的動態性。文獻[12-13]等系統與LANDMARC類似，通過使用虛擬參考標簽降低了參考標簽的部署密度。在這些系統中，根據周圍真實參考標簽的讀數來計算每個閱讀器每個虛擬參考標簽的RSS讀數。標簽定位系統可滿足多種應用需求。然而，它們以昂貴而又定點部署的基礎設施為基礎，穩定性和可擴展性有限，不適用于物聯網領域。為了提高系統的可擴展性，文獻[14]提出GOSSIPY系統，它利用一組異構移動RFID閱讀器，采取端對端拉引式(pull)傳輸策略，協調確定貼標對象的位置。同時引入位置信息傳輸協議，使位置信息在移動RFID閱讀器中及時傳播。然而該策略需要閱讀器之間直接通信，因此通信開銷和延時較大。針對以上不足，本文為分布式RFID定位系統設計一種分布式位置信息傳輸算法，利用內存點來傳輸被動RFID貼標對象的位置，交換位置請求，只使用少量開銷便提高了位置信息的可用性。

1 位置信息傳輸算法

內存點位置信息傳輸算法的目的是在少量性價比高、靈活性強的基礎設施支持下，提高RFID分布式定位系統位置信息可用性。該算法以內存點為基礎，內存點往往分布于由ad hoc閱讀器使用的智能環境中，這些閱讀器是移動式閱讀器，在傳輸標簽位置和交換標簽位置請求時無需協調。在該算法中，閱讀器周期性地詢問周圍的標簽，對標簽的位置信息和可能經過的內存點進行同步。在同步過程中，閱讀器需要執行如下操作：①利用被詢問的標簽更新內存點；②獲得其詢問區域外的標簽的位置；③對可能存在的位置請求，做出回復、攜帶或者傳播處理。如果攜帶請求，則可迅速地將請求發送給其他內存點。對某個標簽的位置感興趣的閱讀器，可以詢問距離最近的內存點，獲得其他閱讀器獲得的位置信息，或者登記一次位置請求。圖1給出了算法的總體框架。

圖1 算法的總體框架

1.1 算法組成和假設

算法的運行依賴于3種實體：

(1) 標簽(Tags)。表示將被定位的對象，包括移動式對象和固定式對象，由被動式RFID標簽識別;

(2) 內存點(Memory Spots)。表示可以利用藍牙、WiFi、ZigBee和RFID技術的支持信息存儲和檢索的有限存儲處理設備；

(3) 閱讀器(Readers)。表示ad hoc非協調性、動態、異構RFID閱讀器，可定位周圍標簽，相應更新內存點。

每個內存點存儲兩種信息：位置信息和位置查詢。位置信息包含被詢問標簽的估計位置。由過往閱讀器創建和周期性更新位置信息。位置查詢包含關于人們感興趣且需要被定位的標簽查詢。位置查詢信息的更新有兩種方式：①閱讀器和內存點通信，獲得當前不可用的位置信息；②過往閱讀器攜帶來自其他內存點的位置查詢。假設閱讀器作為移動設備，可通過移動設備定位方法確定自己的位置。閱讀器可詢問周圍標簽，可與所有共享內存點通信，并且更新這些內存點。

1.2 方案的運行

定義兩個事件：定位事件和同步事件，這兩個事件均由閱讀器完成，每個同步事件可以目睹多個定位事件。在每個定位事件期間，閱讀器詢問周圍的標簽，生成關于周圍標簽的帶有時間標記的位置信息。在每個同步事件期間，閱讀器與它可能經過的各個內存點進行通信，更新這些內存點的位置信息，攜帶其他感興趣的閱讀器需要的位置信息。除了上述兩種事件外，還定義另外一種事件，稱為查詢事件，且根據需要執行這種事件。當閱讀器需要定位其查詢范圍之外的某個或某些標簽時，它可以檢查可能經過的各個內存點，以便獲得需要的位置信息，或者遞交一次位置查詢請求，以便在之后的同步事件期間進行位置查詢。圖2闡述了閱讀器和內存點的位置信息及位置請求含義。下面用一個示例從閱讀器和內存點角度描述標簽定位、位置查詢和同步過程。

圖2 內存點和閱讀器的位置信息及位置查詢示意圖

1.2.1 標簽定位

在該過程中，閱讀器通過一系列定位事件來維護其查詢區域內標簽的位置信息。這些信息可能是簡單的鄰近位置信息，也可能是更為準確的位置信息，具體視閱讀器性能而定。出于簡便考慮，只包含時間、標簽ID及閱讀器位置的鄰近位置信息。這將在每個閱讀器內生成需要匯集、傳輸并可被及時使用的位置信息。

1.2.2 位置查詢

當閱讀器定位其當前查詢范圍之外的標簽時，需要執行這一過程。如算法1所示，希望查詢標簽位置的閱讀器，首先查詢其本地位置信息是否存在目標標簽。如果需要的位置信息不存在，則閱讀器開始與它路過的內存點進行通信，以便提取需要的位置信息，或者登記一次位置查詢。當登記一次位置查詢時，閱讀器生成一個隨機ID(query_ID)及閱讀器ID(r_ID)，以便對該次查詢進行標識，然后分配一個定時時間，表示在該時間之后，閱讀器可能不再需要定位這些標簽。

算法1:位置查詢請求算法—由閱讀器運行。

輸入:標簽ID 輸出:標簽的位置信息

set loc(Reader_ID)=Reader_ID.location in formation

set loc(Memory Spot_ID)=Memory Spot_ID.location in formation

set query(Memory Spot_ID)=Memory Spot_ID.location queries

if loc(Reader_ID)中存在tag_ID then

set not localized=Fake

return tag_ID.position

else

set not_localized=True

while not_localized do

聯系Memory Spots

for每個被聯系的Memory Spot do

if loc(Memory Spot_ID)中存在tag_ID then

set not localized=False

return tag_ID position

else

生成Q(query_ID,Reader_ID,Tag_ID,timeout)

將Q添加到query(Memory Spot_ID)

end if

end for

end if

1.2.3 同步過程

位置信息傳播算法的主要步驟就是利用過往的閱讀器不斷地對分布式內存點進行位置信息的同步。當閱讀器執行同步事件并相應地與內存點通信時，將會進行如下操作：

(1) 閱讀器更新內存點的位置信息，獲得它可能感興趣的標簽的位置信息。

(2) 閱讀器將其位置查詢推入內存點，其他內存點通過先前的同步事件而攜這些位置查詢。

(3) 內存點對其位置查詢進行過濾，拋棄已經被回復過或者已經過期的所有查詢請求。相應地，內存點將其位置信息中的“to_carry”標簽更換為被回復查詢中將由過往閱讀器傳遞的標簽。

(4) 閱讀器攜帶“to_carry”位置信息以及內存點中的其他剩余查詢請求，將它們傳遞給它可能經過的其他內存點。

算法2詳細描述了過往閱讀器如何對聯系到的內存點更新位置信息(即操作1)，同時描述了閱讀器如何將它所攜帶的查詢請求放置到將由其他任意過往閱讀器回復的內存點中(即操作2)。在更新過程中，如果發生沖突，則考慮最新的位置信息。然而，如果存在某種位置估計方法，其精度高于鄰近方法，則在決定使用哪個位置信息時必須考慮位置精度。

算法2:位置/查詢信息更新算法—由閱讀器運行。

set loc(Reader_ID)=Reader_ID.location information

set query(Reader_ID)=Reader_ID.location queries

set loc(Memory Spot_ID)=Memory Spot_ID.location in formation

set query(Memory Spot_ID)=Memory Spot_ID.location queries

for loc(Reader_ID)中的每條記錄rido

if(ri.tag_ID不存在于loc(Memroy Spot_ID) or ritime距離現在最近 then

將(ri.time,Reader_ID,r1tag_ID,ri.r_position)添加到

loc(Memory Spot_ID)

end if

end for

for query(Reader_ID)中的每個查詢qido

將(qiquery_ID, Reader_ID, qitimeout)加到

query(Memory Spot_ID)

end for

運行算法2后，將會生成關于內存點的位置請求信息，包含需要處理的被回復、未被回復及已經過期的查詢請求。此外，為了滿足其他閱讀器的要求，不論當前閱讀器的興趣如何，均需要針對已經被回復將被攜帶和傳輸的請求，利用內存點來標記這些請求的位置信息。通過將這些標簽的to-carry標記更換為數值1即可實現這一點。算法3表示同步過程的第3個操作，描述了內存點對上述步驟的總體運行過程。

算法3:查詢過濾算法—由內存點運行。

輸入:位置查詢請求輸出:經過過濾的位置查詢

set loc(Memory Spot_ID)=Memory Spot_ID.location information

set query(Memory Spot_ID)=Memory Spot_ID.location queries

for query(Memory Spot_ID)中的每個查詢q1do

if qj.tag_ID存在于loc(Memory Spot_ID) then

set loc(Memory Spot_ID)→qj.tag_ID.to_carry=1

刪除qj

else if qj.timeout<0 then刪除qj

end if

end for

運行算法3有助于釋放內存點資源以及過往閱讀器的通信開銷，以便只處理未被回復的查詢請求，并停止傳輸無用查詢請求。算法4描述了過往閱讀器為了信息傳輸而執行的同步過程中的最后一個操作(即操作4)。在該算法中，閱讀器既攜帶剩余未被回復的查詢請求，還攜帶了下個同步過程需要考慮的“to-carry”位置信息。為了避免出現回環，忽略該閱讀器開始時創建的查詢請求。當閱讀器更新其位置信息時，它只考慮帶有時間標記的標簽位置，而不考慮對這些標簽進行定位的閱讀器。

算法4：位置查詢攜帶算法—由閱讀器運行。

輸入：位置查詢請求輸出：經過更新的位置查詢請求

set loc(Reader_ID)=Reader_ID.location information

set query(Reader_ID)=Reader_ID.location queries

set loc(Memory Spot_ID)=Memory Spot_ID.location information

set query(Memory Spot_ID)=Memory Spot_ID.location queries

for loc(Memory Spot_ID)中的每記錄msjdo

if msj.to_carry=I then

將(msj.time,msj.tag_ID,msj.tag_position)加入

loc(Reader_ID)

end if

end for

for query(Memory Spot_ID)中的每個查詢qido

if (qir_ID≠Reader_ID) then

將(qi.query_ID,qi.r_ID qi.tag_ID)加入

qurey(Reader_ID)

end if

end for

圖3用一個例子闡述了本文算法的運行過程。在圖3(a)中，閱讀器R1定位了標簽t1,t2,t3，且打算定位t4。然后，R1與最近的內存點ms1通信，更新t1,t2,t3的位置，并且登記一次關于t4的查詢請求。閱讀器R2也在ms1周圍(見圖3(b))。因此，R2用t5,t6的位置來更新ms1，攜帶R1生成的關于t4的查詢請求。如圖3(c)所示，當R2移動時，與內存點ms2通信，并且執行如下操作：用t5,t6的位置來更新ms2，將關于t4的查詢請求遞交給ms2。ms2具有之前其他過往閱讀器更新的關于t4的位置信息。因此，ms2將t4的to_carry標記更改為1。相應地，R2攜帶該位置信息，通過其他內存點進行傳輸。如圖3(d)所示，在ms2處，另一個閱讀器R3對R2更新的位置感興趣，因此它不需要登記查詢請求便獲得了這樣的位置信息(t5的位置)。此外，R3用t7,t8的位置來更新ms2，且攜帶t4的位置。R1在移動時，與經過R2或R3更新過的內存點進行通信，進而獲得t4的位置。

2 仿真實驗

采用ns-3進行全面的仿真實驗來評估本文算法和文獻[14]中端對端拉引式(pull)傳輸策略的性能。采用文獻[14]中的方案作為比較對象的主要原因是該方案也是通過使用一組異構移動式RFID閱讀器來定位移動RFID標簽(與本文類似)，且它具有較高的穩定性和可擴展性，與其對比更能體現本文方案的優越性。仿真中考慮兩種性能評估指標：① 定位延時，表示算法對一次位置查詢請求做出響應的平均時間；② 平均開銷，表示算法參與方對一次位置查詢請求做出響應需要的報文平均數量。在本文評估中研究兩個主要參數的影響：內存點的數量和閱讀器的數量。

2.1 仿真配置

利用ns-3技術和基于圖形的ad hoc網絡機動模型，仿真一個包含14個目標點的200 m×200 m區域。各點間通過寬度為8 m的路徑相連，閱讀器以0.75～1.25 m/s的速度在這些路徑上移動。在仿真期間，閱讀器在移動過程中可在每個目標點處逗留一段時間(比如說10 s)。每個閱讀器在詢問周圍標簽時閱讀范圍為4 m，在與內存點通信時閱讀范圍為30 m。我們部署足夠數量的固定式標簽(1 000個)，只隨機選擇100個標簽在生成查詢請求時使用。此外，在目標點和路徑上部署不同數量的內存點，內存點的閱讀范圍為30 m，且不同內存點的閱讀范圍可能部分重疊。我們在閱讀器數量和內存點數量不同的仿真環境下進行實驗。在仿真期間，周期性地設置各個閱讀器對某個隨機標簽感興趣，并相應生成一個位置查詢請求(每60 s)。在計算定位延時時，計算閱讀器獲得一次回復所需要的時間，并對生成的所有查詢請求計算均值。在計算平均開銷時，統計為了滿足一次查詢請求，閱讀器和內存點間交換的報文數量，并對生成的所有查詢請求計算均值。仿真總時間為5 000 s，所有數值均是采用不同的隨機種子，獨立運行10次所獲得的數值。

(a)R1更新ms1并登記一次關于t4的查詢

(b)R2更新ms1并攜帶R1生成的查詢

(c)R2更新ms2并傳輸R1生成的查詢，相應地ms2將t4標記為“to_carry”，因此R2攜帶t4

(d)R3更新ms2，尋找t5，攜帶t4

圖3 位置信息傳輸算法運行過程示例圖

2.2 仿真結果

考察兩種傳輸策略下的仿真結果：① 端到端拉引式策略[14]，閱讀器之間直接進行通信，以便獲得需要的位置信息；② 本文策略，閱讀器利用內存點傳輸位置信息，閱讀器之間不直接通信。

2.2.1 定位延時

圖4和圖5分別描述了3種不同同步間隔條件下(60、90和120 s)，閱讀器數量和內存點數量對定位延時的影響。如圖4所示，增加閱讀器數量后，有助于本文算法迅速傳輸針對內存點的位置查詢請求，因此可在較短延時內對更多查詢做出回復。采取拉引式策略時，定位延時顯著下降，但是平均開銷如圖6所示。增加內存點數量對定位延時只有少量影響(平均3%，如圖5所示)。這是因為內存點數量較高但同步頻率較低時，位置信息請求或回復的傳輸時間可能變長，導致平均開銷增大，如圖7所示。

2.2.2 平均開銷

圖6和圖7分別給出了閱讀器數量和內存點數量對平均開銷的影響。如圖6所示，對于拉引式策略，增加閱讀器數量后，由于需要在閱讀器間廣播位置查詢請求和回復，因此平均開銷較大。在本文算法中，當閱讀器數量上升2倍時，即使同步頻率較低，平均開銷性能仍平均提升70%。原因是被及時更新的閱讀器和內存點數量上升，于是利用較少的攜帶和轉發報文，即可滿足位置查詢請求。當內存點數量翻倍時(如圖7所示)，需要位置查詢請求和回復來遍歷更多個內存點，于是報文數量上升，開銷增加。同步頻率較低時，平均開銷較少，此時閱讀器在更新內存點之前維護位置信息及攜帶查詢請求的時間變長。

圖4 閱讀器數量對定位延時的影響(15個內存點)

圖5 內存點數量對定位延時的影響(75個閱讀器)

圖6 閱讀器數量對平均開銷的影響(15個內存點)

圖7 內存點數量對平均開銷的影響(75個閱讀器)

3 結 語

針對典型的IoT大規模動態場景的一種分布式定位和位置信息傳輸算法貢獻如下：① 利用異構非協調性移動RFID閱讀器來實現周圍標簽的定位；② 利用內存點來維護位置信息的可用性；③ 設計一種分布式位置信息傳輸協議，通過使用內存點在RFID閱讀器中傳輸位置信息。我們通過全面的基于ns-3的仿真實驗驗證了該算法的有效性。在下一步工作中，我們計劃對已知的環境和應用中可以控制內存點最佳部署的參數進行研究，并考察移動閱讀器按照事先確定好的路徑移動時的系統性能。

[1] 侯陳達, 李 棟, 邱杰凡, 等. EasiDEF: 一種水平化輕量級物聯網數據交換協議[J]. 計算機學報, 2015, 38(3): 602-613.

[2] 孫其博, 劉 杰, 黎 葬, 等. 物聯網 概念, 架構與關鍵技術研究綜述 [J]. 北京郵電大學學報, 2010, 33(3): 1-9.

[3] Ruiz A R J, Granja F S, Honorato J C P,etal. Accurate pedestrian indoor navigation by tightly coupling foot-mounted IMU and RFID measurements[J]. IEEE Transactions on Instrumentation and Measurement, 2012, 61(1): 178-189.

[4] Qian C, Ngan H, Liu Y,etal. Cardinality estimation for large-scale RFID systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(9): 1441-1454.

[5] Yang P, Wu W, Moniri M,etal. Efficient object localization using sparsely distributed passive RFID tags [J]. IEEE Transactions on Industrial Electronics, 2013, 60(12): 5914-5924.

[6] Oh H, An B, Smith A L,etal. An RFID localization algorithm for a plug-in electric vehicle recharging robot[C]// 2015 IEEE International Conference on Consumer Electronics (ICCE). London, UK: IEEE Press, 2015: 176-177.

[7] Choi B S, Lee J W, Lee J J,etal. A hierarchical algorithm for indoor mobile robot localization using RFID sensor fusion [J]. IEEE Transactions on Industrial Electronics, 2011, 58(6): 2226-2235.

[8] Han S, Lim H S, Lee J M. An efficient localization scheme for a differential-driving mobile robot based on RFID system [J]. IEEE Transactions on Industrial Electronics, 2014, 54(6): 3362-3369.

[9] Ekambaram V, Ramchandran K. SLAC-RF: Simultaneous 3D Localization of mobile readers and Calibration of RFID supertags [J]. EECS Department, University of California, Technical Report UCB/EECS-2012-188, 2012.

[10] Papapostolou A, Chaouchi H. RFID-assisted indoor localization and the impact of interference on its performance [J]. Journal of Network and Computer Applications, 2011, 34(3): 902-913.

[11] Ni W, Xiao W, Toh Y K,etal. Fingerprint-MDS based algorithm for indoor wireless localization[C]. 2010 IEEE 21st International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC). Istanbul, Turkey: IEEE Press, 2010: 1972-1977.

[12] Zhao Y, Liu Y, Ni L M. VIRE: Active RFID-based localization using virtual reference elimination[C]. 2014 IEE International Conference on Parallel Processing (ICPP). Minneapolis, USA: IEEE Press, 2014: 56-66.

[13] Bouet M, Pujolle G. L-VIRT: Range-free 3-D localization of RFID tags based on topological constraints [J]. Computer Communications, 2014, 32(13): 1485-1494.

[14] Eslim L M, Ibrahim W M, Hassanein H S. GOSSIPY: A distributed localization system for Internet of Things using RFID technology[C]//2013 IEEE Global Communications Conference (GLOBECOM). Atlanta, GA, USA: IEEE Press, 2013: 140-145.

Location Information Transmission Algorithm Based on Memory Spots in RFID Localization Systems

YEZhi-xiang1,ZHANGWei-le2

(1. The Economics and Management College, Guangdong Institute of Science and Technology, Zhuhai 519090, China; 2. The Ministry of Education Key Laboratory of Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China)

The existing RFID localization system is based on the centralized and fixed infrastructure which provides limited scalability and may not be plausible in typical IoT large-scale dynamic scenarios. To solve this problem, a distributed location information transmission algorithm based on memory spots is proposed in this paper. Firstly, heterogeneous uncoordinated mobile RFID readers localize the mobile or stationary passive RFID tagged-objects through indirect cooperation, and then the location information is disseminated by using the available memory spots in a given smart environment. Finally, mobile RFID readers use such memory spots to store tag locations and queries enabling exchange location information without the need for direct communication among readers. The results of comprehensive simulation experiment based on ns-3 indicate that the proposed algorithm outperforms the typical pull dissemination strategy in terms of localization delay and average overhead under different dynamicity settings.

RFID; localization systems; memory spots; readers; delay; average overhead

2015-10-19

國家自然科學基金(61302069/F010202)資助

葉志祥(1980-)，男，碩士，實驗師，研究方向：云計算、內容中心網絡。E-mail:tmzhuange_mail@sina.com

TP 391

A

1006-7167(2016)09-0120-06