信息采集协议的时效性分析

李雪竹,宋子东

宿州学院信息工程学院，安徽宿州，234000

射频识别(RFID)系统已经被应用于各类程序，比如库存控制、目标跟踪和仓库管理等。一个典型的RFID系统由一个或多个读写器和大量的标签组成，每个标签都有一个唯一的ID身份标识，并且被连接到一个物理对象上。读写器能够识别或通过相应的标签跟踪到这个对象。实际上，RFID标签在距离上的操作是有限的。因此，在仓库或者超市这样大范围的RFID部署中，为了确保覆盖整个区域，则需要安装多路的读写器[1]。

本文分析了两种解决多读写器信息采集的问题，一种是直接从已有的单一读写器RFID系统的信息采集协议上扩展，这种方案在执行时间上并不是高效的，在有冲突的地方要花费很多费用。另一种是基于布鲁姆过滤器的信息采集协议(BIC)。布鲁姆过滤器被网络建构并且被传输给读写器，为了高效地识别讯问标签，也为了信息传输时减少碰撞，读写器使用一个哈希函数为每一个讯问标签分配一个唯一的时间空挡[2]。

1 研究背景

关于RFID系统的ID信息采集协议，已有的能够被分为三大类：基于ALOHA的、基于树的和混合的。在多读写器环境中的ID采集问题有标签和读写器的传输碰撞。

文献[2]中设计了两个协议，分别称为单一的哈希信息采集协议(SIC)和多哈希信息采集协议(MIC)，为了用最优化的执行时间从大量的标签中阅读传感器产生的数据。文献[3]从能源效率的各个方面研究了信息采集协议。轮询协议The Tag-Ordering (TOP)及其加强版提出的读写器，能用最小的能量消耗从标签系统的子集收集传感信息。以上协议都是单一读写器的RFID系统，并且假设读写器从它采集到的信息里已经识别了标签的ID。但是在有多读写器的大范围的RFID系统中，由于有限的访问区域和标签的流动性，在RFID读写器之间的一些信息是无效的，因此，以上协议不能有效地处理多读写器的信息采集问题，如何为多读写器的RFID系统设计信息采集协议的时效性仍在探索中[1]。

2 系统分析研究的准备工作

在多个读写器的大范围的RFID系统中，尽管读写器互相之间能够从数据库里获取所有标签的ID，但是，由于访问区域的限制和标签的移动性，仍会有一些未知的信息，比如当前哪些标签在什么区域或者从哪里采集它的传感信息等[4]。因此，读写器为了收集信息就首先需要确定标签所在的区域，这使得对多读写器的信息采集协议的分析更加复杂。

在RFID系统中，用M表示标签的集合，并且m=|M|,用N表示在某个读写器的访问区域内的标签的集合，并且n=|N|,显然N⊆M，并且n≤m。用p代表n/m，假设所有的传感信息包含相同的位数，用Tinf表示一个标签发送信息的时间槽的长度，那么读写器为了从它所有的访问标签上采集信息，任何一个协议执行时间的下限在N集合中是n×Tinf，这个下限是无法达到的，因为它为了识别区域内的访问标签发送的控制信息要花费额外时间，而且还要协调传送冲突[5]。

3 传统的解决方案

根据读写器识别讯问标签的方法，所有的标签都可以被分成以下两类：第一类是IDPS，基于协议的ID采集。IDPS执行时间的下限是n×T，这是所有的讯问标签在发送他们的信息和ID号所需要时间的集合(aggregation)。第二类被称为SIPS。PIC和MIC是SIPS的两种实例。SIPS执行时间的下限是(m-n)×Tdet+n×tinf。以上是不同的多读写器信息采集协议的时间性能分析[8]。

4 基于信息采集协议的布鲁姆过滤器

布鲁姆过滤器是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合[9-10]。因此，如果在N集合内，能够以布鲁姆过滤器的形式传送给读写器，对访问标签的标识和信息采集协议的执行时间会有很大程度的减少[1]。

5 用不同数量的标签的执行时间比较

首先分析BIC在不同的m值下,比如从10 000到100 000不等，对于每个m值,假设n=0.1m,这样比率ρ在一系列模拟中保持一个常数。当信息是1位时，表1演示了不同的多读写器信息收集协议的执行时间[7]，结果表明，BIC优于其他所有协议。例如,当m=50 000和n=5 000,它花费读写器约212.4 s来收集所有的信息，用PIC,大约是1.6 s,是下限的133倍。AIC的工作比PIC要好些,它只是需要29.0 s。MIC进一步减少了执行时间到25.8 s。BIC有最小的执行时间4.0 s,这仅仅是下界的2.5倍[1](以s为单位)。

表1 当传感器信息是1位时执行时间比较

表2 当传感器信息是8位时执行时间比较

表3 当传感器信息是16位时执行时间比较

表2和3显示了信息长度分别是8位和16位的实验结果。可以看出，BIC仍能达到所有协议中最高的时间效率。例如，当m=30 000,n=3 000和信息是8位长时，BIC的执行时间是1.4 s,MIC的执行时间大约20.1 s，AIC的执行时间是18.5 s,PIC执行时间是127.8 s；当m=75 000,n=7 500和信息是16位时,BIC的执行时间是4.5 s，MIC的执行时间是63.3 s，AIC的执行时间是49.3 s，PIC的执行时间是320.7 s。

6 结束语

大范围RFID系统中，在安装多读写器情况下，采集传感信息的时效性不同于单一读写器的RFID系统。直接从单一读写器信息采集协议中延伸出来的方案，由于要识别访问标签的高负荷，所以，在执行时间上效率是不高的；而基于布鲁姆过滤器的信息采集协议BIC，其过滤器访问标签的集合表现为分布式的构建和传输给读写器，这在降低访问标签的标识费用和改进多读写器信息采集协议的执行性能上有很大意义。

参考文献：

[1]Hao Yue,Chi Zhang,Miao Pan, et al.A Time-efficient Information Collection Protocol for Large-scale RFID Systems[J].Proceedings IEEE INFOCOM，2012,23(11):2094-2106

[2]Shigang Chen,Ming Zhang,Bin Xiao.Efficient Information Collection Protocols for Sensor-augmented RFID Networks[C]//Shanghai，China:Proc of Info Com，2011:3101-3109

[3]Y Qiao,S Chen,T Li,et al.Energy-efficient Polling Protocols in RFID Systems[C]//Las Vegas:Proc of Mobi Hoc，2011:2094-2106

[4]Sun,Junqing，Peterson,Gregory D.An Effective Execution Time Approximation Method for Parallel Computing[J].IEEE Journals & Magazines，2012,23(11):2024-2032

[5]M Liao,X L Zhong,Y Qiao,et al.Effects of film thickness on microstructure and properties of Bi3.15Nd0.85Ti3O12thin films fabricated by chemical solution deposition[J].Journal of Alloys and Compounds-J ALLOYS COMPOUNDS，2009,48(7):331-334

[6]熊春如.基于RFID的智能数据采集终端的研究与设计[J].电气自动化，2008,30(5):54-56

[7]Wen Luo,Shigang Chen,Tao Li,et al.Efficient missing tag detection in RFID systems[C]//Shanghai，China:INFOCOM，2011:356-360

[8]Amir A,Efrat A,Myllymaki J,et al.Buddy tracking:efficient proximity detection among mobile friends[C].Hong Kong:Proceedings of IEEE INFOCOM IEEE,2004:7-11

[9]Thomas B.Generating network-based moving objects[C]// Proceedings of International Conference on Scientific and Statistical Database Management. Berlin:IEEE,2000:253-256

[10]Kai Bu,Bin Xiao,Qingjun Xiao,et al.Efficient Misplaced-Tag Pinpointing in Large RFID Systems[J].Proceedings IEEE INFOCOM，2012,11(23):2094-2106