Abstract: As the radio frequency communication technology gets more mature and the hardware manufacturing cost decreases, Radio Frequency IDentification (RFID) technology has been applied in the domains of real-time object monitoring, tracing and tracking. In supply chain applications, there are usually a great number of RFID objects to be monitored and traced, and objects' locations are changed essentially, so how to query the locations and the histories of location change of the RFID objects, from the huge volume of RFID data, is an urgent problem to be addressed. Concerning the characteristics of mobile RFID objects and the tracing query requirements in supply chain applications, an effective spatio-temporal index, called as CR-L, was put forward, and its structure and maintenance algorithms, including insertion, deletion, bi-splitting, and lazy splitting, were discussed in detail. In order to support object queries effectively, a new calculation principle of Minimum Bounding Rectangle (MBR), considering the three dimensional information including readers, time and objects, was presented to cluster the trajectories by the same reader at close time into the same node or the neighboring nodes. As to trajectory queries, a linked list was designed to link all trajectories belonging to the same object. The experimental results verify that CR-L has better query efficiency and lower space utilization rate than the existing method.

Key words: Radio Frequency IDentification (RFID), moving object, spatio-temporal index, location tracing, Minimum Bounding Rectangle (MBR)

摘要： 随着射频通信技术的不断成熟及硬件制造成本的不断降低,射频识别(RFID)技术已开始应用于物品实时监控、跟踪与追溯领域。在供应链应用中,RFID对象数量繁多而且位置经常发生变化,如何从海量数据中查询标签对象的位置及其变化历史已成为供应链追溯亟须解决的问题。针对RFID移动对象特征及追溯查询需求,提出了一种有效的时空索引机制CR-L，并详细讨论了CR-L的结构及维护算法,包括插入、删除、二分裂及惰性分裂算法等。针对对象查询,CR-L利用读写器、时间及对象等三维信息设计了新的最小外界矩形(MBR)值计算原则,将相同读写器在相近时间内探测到的轨迹尽可能聚集于相同或相邻节点。对于轨迹查询,采用单链表将相同对象的轨迹链接起来。实验结果表明,所提索引机制具有较好的查询效率和较低的空间占用率。

关键词: 射频识别, 移动对象, 时空索引, 位置追溯, 最小外界矩形