基于ｐ２ｐ技術的ＲＦＩＤ網絡數據清理模型

張　潔　王亞芳　王　妍

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

[關鍵詞]射頻識別 P2P 數據清理

中圖分類號：TP7文獻標識碼：A文章編號：1671－7597（2009）0510042－01

一、引言

數據量是RFID網絡面臨的最大挑戰。其解決途徑之一是將需集中處理的信息分散到各本地節點中，在每個節點中

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

二、基于p2p技術的RFID網絡數據清理模型

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

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

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

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

點對點校驗階段，“PRE，CURRENT，NEXT”中的信息與從前一節點和后一節點接收到的信息共同決定了糾錯的產生。不同節點內的具體動作如圖1。當節點接收到信息R（‘message'）時就觸發狀態轉移?！甿essage

信息有四種：FN（RFID標簽被發送信息的節點判定為丟失閱讀），FP（RF

ID標簽被發送信息的節點判定為錯誤閱讀），C1（發送信息節點‘CURRENT

值已變為1），C0（發送信息節點‘CURRENT值已變為0），‘+表示信息是由下一節點發出，‘-表示信息由前一節點發出。定義函數C（v1，v2），表示當前節點的CURRENT'值從‘v1變成‘v2'，STATUS的信息根據v2變成‘C0'或‘C1'。函數S（‘message'）表示信息發送到前一節點（‘+）或下一節點（‘-）如圖2所示。

三、仿真和結果

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

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

表2數據清理模型的平均性能值

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

譯：張潔王妍）

參考文獻：

[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網絡的數據清理技術[J].網絡與通信，第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]包從劍，數據清洗的若干關鍵技術的研究[D].江蘇大學，2007.

《A P2P Collaborative RFID Data Cleaning Model》

作者簡介：

張潔，女，河北省石家莊市人，碩士研究生，研究方向為數字交換與傳輸。