RFID定位系統(tǒng)中內(nèi)存點(diǎn)位置信息傳輸算法

葉志祥， 張渭樂

(1.廣東科學(xué)技術(shù)職業(yè)學(xué)院 經(jīng)濟(jì)管理學(xué)院，廣東 珠海 519090;2.西安交通大學(xué) 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710061)

?

·計(jì)算機(jī)技術(shù)應(yīng)用·

RFID定位系統(tǒng)中內(nèi)存點(diǎn)位置信息傳輸算法

葉志祥1， 張渭樂2

(1.廣東科學(xué)技術(shù)職業(yè)學(xué)院 經(jīng)濟(jì)管理學(xué)院，廣東 珠海 519090;2.西安交通大學(xué) 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710061)

當(dāng)前的RFID定位系統(tǒng)往往以固定式集中式基礎(chǔ)設(shè)施為基礎(chǔ)進(jìn)行位置估計(jì)，系統(tǒng)的延時(shí)較大、可擴(kuò)展性有限，往往難以應(yīng)用在物聯(lián)網(wǎng)大規(guī)模動(dòng)態(tài)場景中。為此，提出一種內(nèi)存點(diǎn)的位置信息傳輸算法。首先，各個(gè)異構(gòu)非協(xié)調(diào)性移動(dòng)RFID閱讀器通過間接合作對(duì)移動(dòng)或固定式RFID貼標(biāo)對(duì)象進(jìn)行定位，然后利用已知智能環(huán)境中的可用內(nèi)存點(diǎn)來傳輸位置信息，最后移動(dòng)RFID利用這些內(nèi)存點(diǎn)來存儲(chǔ)標(biāo)簽位置和實(shí)現(xiàn)檢索，使得RFID互相之間不進(jìn)行直接通信就可以交換位置信息。基于ns-3的全面仿真實(shí)驗(yàn)結(jié)果表明，在多種環(huán)境配置下，本文算法的定位延時(shí)和平均開銷均優(yōu)于典型的拉引式傳輸算法。

無線射頻識(shí)別技術(shù); 定位系統(tǒng)； 內(nèi)存點(diǎn)； 閱讀器； 延時(shí)； 平均開銷

0 引 言

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

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

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

1 位置信息傳輸算法

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

圖1 算法的總體框架

1.1 算法組成和假設(shè)

算法的運(yùn)行依賴于3種實(shí)體：

(1) 標(biāo)簽(Tags)。表示將被定位的對(duì)象，包括移動(dòng)式對(duì)象和固定式對(duì)象，由被動(dòng)式RFID標(biāo)簽識(shí)別;

(2) 內(nèi)存點(diǎn)(Memory Spots)。表示可以利用藍(lán)牙、WiFi、ZigBee和RFID技術(shù)的支持信息存儲(chǔ)和檢索的有限存儲(chǔ)處理設(shè)備；

(3) 閱讀器(Readers)。表示ad hoc非協(xié)調(diào)性、動(dòng)態(tài)、異構(gòu)RFID閱讀器，可定位周圍標(biāo)簽，相應(yīng)更新內(nèi)存點(diǎn)。

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

1.2 方案的運(yùn)行

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

圖2 內(nèi)存點(diǎn)和閱讀器的位置信息及位置查詢示意圖

1.2.1 標(biāo)簽定位

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

1.2.2 位置查詢

當(dāng)閱讀器定位其當(dāng)前查詢范圍之外的標(biāo)簽時(shí)，需要執(zhí)行這一過程。如算法1所示，希望查詢標(biāo)簽位置的閱讀器，首先查詢其本地位置信息是否存在目標(biāo)標(biāo)簽。如果需要的位置信息不存在，則閱讀器開始與它路過的內(nèi)存點(diǎn)進(jìn)行通信，以便提取需要的位置信息，或者登記一次位置查詢。當(dāng)?shù)怯浺淮挝恢貌樵儠r(shí)，閱讀器生成一個(gè)隨機(jī)ID(query_ID)及閱讀器ID(r_ID)，以便對(duì)該次查詢進(jìn)行標(biāo)識(shí)，然后分配一個(gè)定時(shí)時(shí)間，表示在該時(shí)間之后，閱讀器可能不再需要定位這些標(biāo)簽。

算法1:位置查詢請(qǐng)求算法—由閱讀器運(yùn)行。

輸入:標(biāo)簽ID 輸出:標(biāo)簽的位置信息

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

聯(lián)系Memory Spots

for每個(gè)被聯(lián)系的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 同步過程

位置信息傳播算法的主要步驟就是利用過往的閱讀器不斷地對(duì)分布式內(nèi)存點(diǎn)進(jìn)行位置信息的同步。當(dāng)閱讀器執(zhí)行同步事件并相應(yīng)地與內(nèi)存點(diǎn)通信時(shí)，將會(huì)進(jìn)行如下操作：

(1) 閱讀器更新內(nèi)存點(diǎn)的位置信息，獲得它可能感興趣的標(biāo)簽的位置信息。

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

(3) 內(nèi)存點(diǎn)對(duì)其位置查詢進(jìn)行過濾，拋棄已經(jīng)被回復(fù)過或者已經(jīng)過期的所有查詢請(qǐng)求。相應(yīng)地，內(nèi)存點(diǎn)將其位置信息中的“to_carry”標(biāo)簽更換為被回復(fù)查詢中將由過往閱讀器傳遞的標(biāo)簽。

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

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

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

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距離現(xiàn)在最近 then

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

loc(Memory Spot_ID)

end if

end for

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

將(qiquery_ID, Reader_ID, qitimeout)加到

query(Memory Spot_ID)

end for

運(yùn)行算法2后，將會(huì)生成關(guān)于內(nèi)存點(diǎn)的位置請(qǐng)求信息，包含需要處理的被回復(fù)、未被回復(fù)及已經(jīng)過期的查詢請(qǐng)求。此外，為了滿足其他閱讀器的要求，不論當(dāng)前閱讀器的興趣如何，均需要針對(duì)已經(jīng)被回復(fù)將被攜帶和傳輸?shù)恼?qǐng)求，利用內(nèi)存點(diǎn)來標(biāo)記這些請(qǐng)求的位置信息。通過將這些標(biāo)簽的to-carry標(biāo)記更換為數(shù)值1即可實(shí)現(xiàn)這一點(diǎn)。算法3表示同步過程的第3個(gè)操作，描述了內(nèi)存點(diǎn)對(duì)上述步驟的總體運(yùn)行過程。

算法3:查詢過濾算法—由內(nèi)存點(diǎn)運(yùn)行。

輸入:位置查詢請(qǐng)求輸出:經(jīng)過過濾的位置查詢

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)中的每個(gè)查詢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

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

算法4：位置查詢攜帶算法—由閱讀器運(yùn)行。

輸入：位置查詢請(qǐng)求輸出：經(jīng)過更新的位置查詢請(qǐng)求

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)中的每個(gè)查詢qido

if (qir_ID≠Reader_ID) then

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

qurey(Reader_ID)

end if

end for

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

2 仿真實(shí)驗(yàn)

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

2.1 仿真配置

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

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

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

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

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

圖3 位置信息傳輸算法運(yùn)行過程示例圖

2.2 仿真結(jié)果

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

2.2.1 定位延時(shí)

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

2.2.2 平均開銷

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

圖4 閱讀器數(shù)量對(duì)定位延時(shí)的影響(15個(gè)內(nèi)存點(diǎn))

圖5 內(nèi)存點(diǎn)數(shù)量對(duì)定位延時(shí)的影響(75個(gè)閱讀器)

圖6 閱讀器數(shù)量對(duì)平均開銷的影響(15個(gè)內(nèi)存點(diǎn))

圖7 內(nèi)存點(diǎn)數(shù)量對(duì)平均開銷的影響(75個(gè)閱讀器)

3 結(jié) 語

針對(duì)典型的IoT大規(guī)模動(dòng)態(tài)場景的一種分布式定位和位置信息傳輸算法貢獻(xiàn)如下：① 利用異構(gòu)非協(xié)調(diào)性移動(dòng)RFID閱讀器來實(shí)現(xiàn)周圍標(biāo)簽的定位；② 利用內(nèi)存點(diǎn)來維護(hù)位置信息的可用性；③ 設(shè)計(jì)一種分布式位置信息傳輸協(xié)議，通過使用內(nèi)存點(diǎn)在RFID閱讀器中傳輸位置信息。我們通過全面的基于ns-3的仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。在下一步工作中，我們計(jì)劃對(duì)已知的環(huán)境和應(yīng)用中可以控制內(nèi)存點(diǎn)最佳部署的參數(shù)進(jìn)行研究，并考察移動(dòng)閱讀器按照事先確定好的路徑移動(dòng)時(shí)的系統(tǒng)性能。

[1] 侯陳達(dá), 李 棟, 邱杰凡, 等. EasiDEF: 一種水平化輕量級(jí)物聯(lián)網(wǎng)數(shù)據(jù)交換協(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(3): 602-613.

[2] 孫其博, 劉 杰, 黎 葬, 等. 物聯(lián)網(wǎng) 概念, 架構(gòu)與關(guān)鍵技術(shù)研究綜述 [J]. 北京郵電大學(xué)學(xué)報(bào), 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

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

葉志祥(1980-)，男，碩士，實(shí)驗(yàn)師，研究方向：云計(jì)算、內(nèi)容中心網(wǎng)絡(luò)。E-mail:tmzhuange_mail@sina.com

TP 391

A

1006-7167(2016)09-0120-06