張　潔　王亞芳　王　妍

[摘要]提出基于P2P技術(shù)RFID網(wǎng)絡(luò)數(shù)據(jù)清理模型能夠通過在相鄰節(jié)點(diǎn)間互換信息來判別和清除錯誤的RFID信息，在保證了較高的信息準(zhǔn)確性的同時，降低對單個節(jié)點(diǎn)信息讀取正確性的要求，減少整個網(wǎng)絡(luò)的開銷。

[關(guān)鍵詞]射頻識別 P2P 數(shù)據(jù)清理

中圖分類號：TP7文獻(xiàn)標(biāo)識碼：A文章編號：1671－7597（2009）0510042－01

一、引言

數(shù)據(jù)量是RFID網(wǎng)絡(luò)面臨的最大挑戰(zhàn)。其解決途徑之一是將需集中處理的信息分散到各本地節(jié)點(diǎn)中，在每個節(jié)點(diǎn)中

完成信息的分析和處理。本文討論了一種用于識別和清除節(jié)點(diǎn)閱讀信息錯誤的新算法，通過統(tǒng)計(jì)成功閱讀、錯誤閱讀（False Positive）和丟失閱讀（False Negative）的數(shù)目來衡量節(jié)點(diǎn)工作情況。定義TP（true positive）為成功閱讀的事例；FN與FP分別為錯誤閱讀和丟失閱讀的事例，精確率P=TP/（TP+FP），召回率R=TP/（TP+FN）.R衡量每個節(jié)點(diǎn)成功讀取標(biāo)簽原始信息的能力；P衡量每個節(jié)點(diǎn)避免錯誤閱讀的能力。定義F1為：F1=2PR/（P+R），考慮精確率和召回率綜合評定節(jié)點(diǎn)的性能。在理想的零錯誤的情況下，這三個值均為100%。

二、基于p2p技術(shù)的RFID網(wǎng)絡(luò)數(shù)據(jù)清理模型

此方案用邊界的檢測節(jié)點(diǎn)表明了標(biāo)簽可能運(yùn)動的路線，定義RFID數(shù)據(jù)交換網(wǎng)絡(luò)（RDEN）。RDEN將檢測節(jié)點(diǎn)網(wǎng)絡(luò)層的每個節(jié)點(diǎn)看作中心點(diǎn)，信息在節(jié)點(diǎn)和邊界之間進(jìn)行交換。REDN可建模成無向圖G（V，E）。V指檢測節(jié)點(diǎn)，表示為V（v1，v2，v3…）。e表示當(dāng)節(jié)點(diǎn)v1與節(jié)點(diǎn)v2之間有信息傳輸時節(jié)點(diǎn)之間的連接，并且e∈E，（E表示各個節(jié)點(diǎn)之間連接的集合）。若干個網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)成數(shù)據(jù)清理簇（DCC），節(jié)點(diǎn)之間的聯(lián)系由業(yè)務(wù)處理邏輯（BPL）決定。建立DCC的方法類似于文獻(xiàn)[1]中所提到的方法，構(gòu)造了處于同路徑中的相鄰節(jié)點(diǎn)之間通過互換信息更新各自信息表的網(wǎng)絡(luò)。實(shí)際上，每個標(biāo)簽按時間順序在網(wǎng)絡(luò)中只有唯一路徑，因此在DDC中能構(gòu)造出有標(biāo)向的數(shù)據(jù)清理路徑（DDCP）。假設(shè)DCCP在每個標(biāo)簽進(jìn)入網(wǎng)絡(luò)之前就已確定，對于更為雜的情況采用“分割解決”[2]的方法，即把DCC分別劃入較為簡單的子網(wǎng)絡(luò)中，再應(yīng)用基于BPL或路由選擇算法的數(shù)據(jù)聚合技術(shù)。

DDCP可以定義為一組有序的節(jié)點(diǎn)，n表示節(jié)點(diǎn)總數(shù)，vi表示標(biāo)簽經(jīng)過的第i個節(jié)點(diǎn). Vi-1表示前一節(jié)點(diǎn)；vi表示當(dāng)前節(jié)點(diǎn)；vi+1表示后一節(jié)點(diǎn)。當(dāng)標(biāo)簽在本節(jié)點(diǎn)中沒有識別，但在前一節(jié)點(diǎn)和后一節(jié)點(diǎn)中有記錄，F(xiàn)P將會告知本節(jié)點(diǎn)。通過在節(jié)點(diǎn)之間交換信息，節(jié)點(diǎn)中發(fā)生的FP和FN可被檢測到，并能及時糾錯。含有4個節(jié)點(diǎn)的DDCP。標(biāo)簽由a0經(jīng)過a1'或a1''到達(dá)a2。通過節(jié)點(diǎn)之間互換信息，可知標(biāo)簽分別出現(xiàn)在a0和a2中，那么根據(jù)BPL的定義，從邏輯上將a1'和a1''看作是同一節(jié)點(diǎn)a1，并且與a0和a2共同組成DDCP。當(dāng)標(biāo)簽沿DDCP從固定節(jié)點(diǎn)a0向最終節(jié)點(diǎn)an運(yùn)動，標(biāo)簽通過節(jié)點(diǎn)時閱讀器以某個特定的成功閱讀速率ri讀取標(biāo)簽信息。節(jié)點(diǎn)中，除了RFID傳統(tǒng)的信息格式Ti，還采用另一種信息格式：Tci.TagID記錄了標(biāo)簽的RFID信息；PRE，CURRENT，NEXT表示標(biāo)簽在前一節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)、后一節(jié)點(diǎn)是否被識別，其值為二進(jìn)制的：‘1表示識別，‘0表示不被識別，STATUS表示標(biāo)簽經(jīng)過數(shù)據(jù)清理后的結(jié)果。

過程分為三個階段：初始化階段、局部校正階段、點(diǎn)對點(diǎn)校正階段。在初始化階段，節(jié)點(diǎn)檢測到標(biāo)簽把TagID中的信息存入到Tci的TagID中，CURRENT置為‘1表明標(biāo)簽被節(jié)點(diǎn)識別，然后此節(jié)點(diǎn)的信息被傳送到前一節(jié)點(diǎn)和后一節(jié)點(diǎn)把Tci-1和Tci+1中對應(yīng)的RFID信息更新為當(dāng)前信息。

局部校驗(yàn)階段，節(jié)點(diǎn)ai首先查驗(yàn)Tci中的PRE，CURRENT，NEXT的值，更新STATUS信息，將對應(yīng)的信息傳給ai-1和ai+1。當(dāng)PRE，CURRENT，NEXT值為‘1，0，1，表示ai中發(fā)生了FN，此時把CURRENT值校正為1，將STATUS置為C1。不同模式下STATUS的更新和隨之的動作見表1。

點(diǎn)對點(diǎn)校驗(yàn)階段，“PRE，CURRENT，NEXT”中的信息與從前一節(jié)點(diǎn)和后一節(jié)點(diǎn)接收到的信息共同決定了糾錯的產(chǎn)生。不同節(jié)點(diǎn)內(nèi)的具體動作如圖1。當(dāng)節(jié)點(diǎn)接收到信息R（‘message'）時就觸發(fā)狀態(tài)轉(zhuǎn)移。‘message

信息有四種：FN（RFID標(biāo)簽被發(fā)送信息的節(jié)點(diǎn)判定為丟失閱讀），F(xiàn)P（RF

ID標(biāo)簽被發(fā)送信息的節(jié)點(diǎn)判定為錯誤閱讀），C1（發(fā)送信息節(jié)點(diǎn)‘CURRENT

值已變?yōu)?），C0（發(fā)送信息節(jié)點(diǎn)‘CURRENT值已變?yōu)?），‘+表示信息是由下一節(jié)點(diǎn)發(fā)出，‘-表示信息由前一節(jié)點(diǎn)發(fā)出。定義函數(shù)C（v1，v2），表示當(dāng)前節(jié)點(diǎn)的CURRENT'值從‘v1變成‘v2'，STATUS的信息根據(jù)v2變成‘C0'或‘C1'。函數(shù)S（‘message'）表示信息發(fā)送到前一節(jié)點(diǎn)（‘+）或下一節(jié)點(diǎn)（‘-）如圖2所示。

三、仿真和結(jié)果

節(jié)點(diǎn)數(shù)目n，成功閱讀概率ri及標(biāo)簽數(shù)目m是預(yù)先確定的參數(shù)。由系統(tǒng)產(chǎn)生m個標(biāo)簽的初始信息表，表的格式為T0＜TagID，LOCATION，TIMESTAMP>，節(jié)點(diǎn)讀取的信息在Ti表格中。由于ri不為1，所以Ti表格中的信息與T0的不同。每個節(jié)點(diǎn)的成功閱讀率都同一設(shè)為r。整個處理過程從初始化Tci表開始，通過收發(fā)信息來改變Tci表，由新信息更新Ti表（如圖3）。隨機(jī)產(chǎn)生1000個標(biāo)簽來測試含有3個、5個和7個節(jié)點(diǎn)的DDCP的網(wǎng)絡(luò)模型。每輪測試，同樣的DDCP在r為60%、70%、80%和90%的四種情況下分別測試，測算出每個節(jié)點(diǎn)的P、R及F1的值。用平均精確率P-avg、平均召回率R-avg和平均F1-avgc從總體上反映網(wǎng)絡(luò)模型在每次測試中的性能。（如表2所示）。

結(jié)果顯示，網(wǎng)絡(luò)在r為60%時，性能提高的效果最為顯著。由此看出，當(dāng)r較低時網(wǎng)絡(luò)能有效的消除錯誤。另外，基于同樣的r，隨著節(jié)點(diǎn)數(shù)目的增加，R有微小的改進(jìn)，這是與通常人們認(rèn)為的在RFID網(wǎng)絡(luò)中，節(jié)點(diǎn)越多給數(shù)據(jù)清理造成越大的混亂的想法相反，也正是由于這種特性，所提出的模型更加適合與實(shí)際應(yīng)用。同時，在成功閱讀率r為90%的情況下，F(xiàn)1會有5%-8%的增加，這也表明這種數(shù)據(jù)清理模型也適合于能夠進(jìn)一步改進(jìn)的RFID網(wǎng)絡(luò)。

表2數(shù)據(jù)清理模型的平均性能值

rnP_avg R_avgF1_avg

60 3 89.71% 76.30%82.14%

60 5 89.30% 78.06%83.04%

60 7 89.73% 78.21%83.39%

70 3 92.88% 82.58%87.27%

70 5 92.66% 84.92%88.49%

70 7 92.79% 85.10%88.69%

rnP_avg R_avgF1_avg

80 3 95.74% 88.40%91.82%

80 5 95.23% 89.70%92.32%

80 7 96.46% 90.12%93.15%

90 3 98.16% 94.61%96.33%

90 5 97.91% 95.08%96.45%

90 7 98.40% 94.83%96.57%

（注：本文為譯文

原著：Xiaogang Peng,Zhen Ji Zongwei Luo,Edward C.Wong,C.J.Tan

譯：張潔王妍）

參考文獻(xiàn)：

[1]“Interconnected RFID Reader Collision Model and its Application in Reader Anti-collision”,IEEE RFID 2007,Texas,USA,2007.

[2]Ram Swaminathan“Divide-and-conquer algorithms for graph layout problems”Networks 28(2):6985,1996.

[3]薛小平、張思東、王小平、曹曉寧，RFID網(wǎng)絡(luò)的數(shù)據(jù)清理技術(shù)[J].網(wǎng)絡(luò)與通信，第34卷，第7期.

[4]Engels D.W.Sarma S.E,“The reader collision problem”,IEEE International Conference on Systems,Man and Cybernetics,Hammamet,Tunisia,2002.

[5]包從劍，數(shù)據(jù)清洗的若干關(guān)鍵技術(shù)的研究[D].江蘇大學(xué)，2007.

《A P2P Collaborative RFID Data Cleaning Model》

作者簡介：

張潔，女，河北省石家莊市人，碩士研究生，研究方向?yàn)閿?shù)字交換與傳輸。