论文部分内容阅读
[摘要]提出基于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'）时就触发状态转移。‘message’
信息有四种：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》
作者简介：
张洁，女，河北省石家庄市人，硕士研究生，研究方向为数字交换与传输。
[关键词]射频识别 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可以定义为一组有序的节点
过程分为三个阶段：初始化阶段、局部校正阶段、点对点校正阶段。在初始化阶段，节点检测到标签把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'）时就触发状态转移。‘message’
信息有四种：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》
作者简介：
张洁，女，河北省石家庄市人，硕士研究生，研究方向为数字交换与传输。