RFID定位系统中内存点位置信息传输算法

叶志祥， 张渭乐

(1.广东科学技术职业学院 经济管理学院，广东 珠海 519090;2.西安交通大学 智能网络与网络安全教育部重点实验室，陕西 西安 710061)



·计算机技术应用·

RFID定位系统中内存点位置信息传输算法

叶志祥1， 张渭乐2

(1.广东科学技术职业学院 经济管理学院，广东 珠海 519090;2.西安交通大学 智能网络与网络安全教育部重点实验室，陕西 西安 710061)

当前的RFID定位系统往往以固定式集中式基础设施为基础进行位置估计，系统的延时较大、可扩展性有限，往往难以应用在物联网大规模动态场景中。为此，提出一种内存点的位置信息传输算法。首先，各个异构非协调性移动RFID阅读器通过间接合作对移动或固定式RFID贴标对象进行定位，然后利用已知智能环境中的可用内存点来传输位置信息，最后移动RFID利用这些内存点来存储标签位置和实现检索，使得RFID互相之间不进行直接通信就可以交换位置信息。基于ns-3的全面仿真实验结果表明，在多种环境配置下，本文算法的定位延时和平均开销均优于典型的拉引式传输算法。

无线射频识别技术; 定位系统； 内存点； 阅读器； 延时； 平均开销

0 引 言

物联网 (Internet of Things,IoT)[1-2]可定义为一个由智能对象构成的分布式系统，这些对象被无缝集成到信息网络中，通过英特网提供各种智能服务。IoT的原理是利用空间分散布置的智能对象，为用户提供更为方便的背景感知和位置感知服务。确定智能对象的位置以及位置信息的可用性，是IoT应用的重要需求。无线射频识别技术(Radio Frequency Identification,RFID)技术是IoT的支撑技术[3-4]，它具有多种独特属性，使其有能力提供高性价比、可靠、灵活、高扩展性的定位服务。一般而言，RFID系统由一组标签(主动式、被动式、半被动式)和一组阅读器构成。人们已经为移动式/固定式贴标对象和移动式阅读器开发了多种RFID定位系统[5-6]。然而这些系统往往以固定式集中式基础设施为基础进行位置估计，系统的可扩展性有限，往往难以应用在IoT大规模动态场景中。为此，本文提出一种分布式RFID定位和位置信息传输算法，利用异构非协调式移动RFID阅读器，可高效确定RFID贴标对象的位置，从而为推广IoT中位置感知服务的应用提供技术支撑。

人们已经提出了多种基于RFID技术的定位系统。文献[7]将标签安装于地板上，并呈正方形排列。当阅读器检测到这些标签上的部分标签时，由于已经知道了它们的位置，所以通过使用加权平均方法可以估计出它的位置。然而，为了提高精度，必须要降低标签间的距离。因此，需要大量标签，增加了系统成本。文献[8]给出了另一种类似系统，在提高定位精度的同时，通过将大量标签部署为三角形，降低了标签使用量。为了避免参考标签密集部署，文献[9]中的SLAC-RF提出一种称为超级标签的专用标签。每个超级标签是多个RFID标签的集合，这些标签通过一定排列来模拟虚拟天线阵列。探测一定区域的移动阅读器利用接收信号相对于超级标签的相位差以及惯性导航系统测量值来估计位置。虽然该系统的性价比和精度较高，而且基础设施部署起来比较简单，但是它们只能支持自主式移动机器人应用。

另外，文献[10]中的SpotON系统利用聚合算法来定位标签位置，忽略了环境动态变化导致的测量不确定性。文献[11]中的LANDMARC系统以指纹技术为基础，为了降低RSS测量的不确定性影响，提升精度，引入了参考标签概念以校准环境的动态性。文献[12-13]等系统与LANDMARC类似，通过使用虚拟参考标签降低了参考标签的部署密度。在这些系统中，根据周围真实参考标签的读数来计算每个阅读器每个虚拟参考标签的RSS读数。标签定位系统可满足多种应用需求。然而，它们以昂贵而又定点部署的基础设施为基础，稳定性和可扩展性有限，不适用于物联网领域。为了提高系统的可扩展性，文献[14]提出GOSSIPY系统，它利用一组异构移动RFID阅读器，采取端对端拉引式(pull)传输策略，协调确定贴标对象的位置。同时引入位置信息传输协议，使位置信息在移动RFID阅读器中及时传播。然而该策略需要阅读器之间直接通信，因此通信开销和延时较大。针对以上不足，本文为分布式RFID定位系统设计一种分布式位置信息传输算法，利用内存点来传输被动RFID贴标对象的位置，交换位置请求，只使用少量开销便提高了位置信息的可用性。

1 位置信息传输算法

内存点位置信息传输算法的目的是在少量性价比高、灵活性强的基础设施支持下，提高RFID分布式定位系统位置信息可用性。该算法以内存点为基础，内存点往往分布于由ad hoc阅读器使用的智能环境中，这些阅读器是移动式阅读器，在传输标签位置和交换标签位置请求时无需协调。在该算法中，阅读器周期性地询问周围的标签，对标签的位置信息和可能经过的内存点进行同步。在同步过程中，阅读器需要执行如下操作：①利用被询问的标签更新内存点；②获得其询问区域外的标签的位置；③对可能存在的位置请求，做出回复、携带或者传播处理。如果携带请求，则可迅速地将请求发送给其他内存点。对某个标签的位置感兴趣的阅读器，可以询问距离最近的内存点，获得其他阅读器获得的位置信息，或者登记一次位置请求。图1给出了算法的总体框架。

图1 算法的总体框架

1.1 算法组成和假设

算法的运行依赖于3种实体：

(1) 标签(Tags)。表示将被定位的对象，包括移动式对象和固定式对象，由被动式RFID标签识别;

(2) 内存点(Memory Spots)。表示可以利用蓝牙、WiFi、ZigBee和RFID技术的支持信息存储和检索的有限存储处理设备；

(3) 阅读器(Readers)。表示ad hoc非协调性、动态、异构RFID阅读器，可定位周围标签，相应更新内存点。

每个内存点存储两种信息：位置信息和位置查询。位置信息包含被询问标签的估计位置。由过往阅读器创建和周期性更新位置信息。位置查询包含关于人们感兴趣且需要被定位的标签查询。位置查询信息的更新有两种方式：①阅读器和内存点通信，获得当前不可用的位置信息；②过往阅读器携带来自其他内存点的位置查询。假设阅读器作为移动设备，可通过移动设备定位方法确定自己的位置。阅读器可询问周围标签，可与所有共享内存点通信，并且更新这些内存点。

1.2 方案的运行

定义两个事件：定位事件和同步事件，这两个事件均由阅读器完成，每个同步事件可以目睹多个定位事件。在每个定位事件期间，阅读器询问周围的标签，生成关于周围标签的带有时间标记的位置信息。在每个同步事件期间，阅读器与它可能经过的各个内存点进行通信，更新这些内存点的位置信息，携带其他感兴趣的阅读器需要的位置信息。除了上述两种事件外，还定义另外一种事件，称为查询事件，且根据需要执行这种事件。当阅读器需要定位其查询范围之外的某个或某些标签时，它可以检查可能经过的各个内存点，以便获得需要的位置信息，或者递交一次位置查询请求，以便在之后的同步事件期间进行位置查询。图2阐述了阅读器和内存点的位置信息及位置请求含义。下面用一个示例从阅读器和内存点角度描述标签定位、位置查询和同步过程。

图2 内存点和阅读器的位置信息及位置查询示意图

1.2.1 标签定位

在该过程中，阅读器通过一系列定位事件来维护其查询区域内标签的位置信息。这些信息可能是简单的邻近位置信息，也可能是更为准确的位置信息，具体视阅读器性能而定。出于简便考虑，只包含时间、标签ID及阅读器位置的邻近位置信息。这将在每个阅读器内生成需要汇集、传输并可被及时使用的位置信息。

1.2.2 位置查询

当阅读器定位其当前查询范围之外的标签时，需要执行这一过程。如算法1所示，希望查询标签位置的阅读器，首先查询其本地位置信息是否存在目标标签。如果需要的位置信息不存在，则阅读器开始与它路过的内存点进行通信，以便提取需要的位置信息，或者登记一次位置查询。当登记一次位置查询时，阅读器生成一个随机ID(query_ID)及阅读器ID(r_ID)，以便对该次查询进行标识，然后分配一个定时时间，表示在该时间之后，阅读器可能不再需要定位这些标签。

算法1:位置查询请求算法—由阅读器运行。

输入:标签ID 输出:标签的位置信息

set loc(Reader_ID)=Reader_ID.location in formation

set loc(Memory Spot_ID)=Memory Spot_ID.location in formation

set query(Memory Spot_ID)=Memory Spot_ID.location queries

if loc(Reader_ID)中存在tag_ID then

set not localized=Fake

return tag_ID.position

else

set not_localized=True

while not_localized do

联系Memory Spots

for每个被联系的Memory Spot do

if loc(Memory Spot_ID)中存在tag_ID then

set not localized=False

return tag_ID position

else

生成Q(query_ID,Reader_ID,Tag_ID,timeout)

将Q添加到query(Memory Spot_ID)

end if

end for

end if

1.2.3 同步过程

位置信息传播算法的主要步骤就是利用过往的阅读器不断地对分布式内存点进行位置信息的同步。当阅读器执行同步事件并相应地与内存点通信时，将会进行如下操作：

(1) 阅读器更新内存点的位置信息，获得它可能感兴趣的标签的位置信息。

(2) 阅读器将其位置查询推入内存点，其他内存点通过先前的同步事件而携这些位置查询。

(3) 内存点对其位置查询进行过滤，抛弃已经被回复过或者已经过期的所有查询请求。相应地，内存点将其位置信息中的“to_carry”标签更换为被回复查询中将由过往阅读器传递的标签。

(4) 阅读器携带“to_carry”位置信息以及内存点中的其他剩余查询请求，将它们传递给它可能经过的其他内存点。

算法2详细描述了过往阅读器如何对联系到的内存点更新位置信息(即操作1)，同时描述了阅读器如何将它所携带的查询请求放置到将由其他任意过往阅读器回复的内存点中(即操作2)。在更新过程中，如果发生冲突，则考虑最新的位置信息。然而，如果存在某种位置估计方法，其精度高于邻近方法，则在决定使用哪个位置信息时必须考虑位置精度。

算法2:位置/查询信息更新算法—由阅读器运行。

set loc(Reader_ID)=Reader_ID.location information

set query(Reader_ID)=Reader_ID.location queries

set loc(Memory Spot_ID)=Memory Spot_ID.location in formation

set query(Memory Spot_ID)=Memory Spot_ID.location queries

for loc(Reader_ID)中的每条记录rido

if(ri.tag_ID不存在于loc(Memroy Spot_ID) or ritime距离现在最近 then

将(ri.time,Reader_ID,r1tag_ID,ri.r_position)添加到

loc(Memory Spot_ID)

end if

end for

for query(Reader_ID)中的每个查询qido

将(qiquery_ID, Reader_ID, qitimeout)加到

query(Memory Spot_ID)

end for

运行算法2后，将会生成关于内存点的位置请求信息，包含需要处理的被回复、未被回复及已经过期的查询请求。此外，为了满足其他阅读器的要求，不论当前阅读器的兴趣如何，均需要针对已经被回复将被携带和传输的请求，利用内存点来标记这些请求的位置信息。通过将这些标签的to-carry标记更换为数值1即可实现这一点。算法3表示同步过程的第3个操作，描述了内存点对上述步骤的总体运行过程。

算法3:查询过滤算法—由内存点运行。

输入:位置查询请求输出:经过过滤的位置查询

set loc(Memory Spot_ID)=Memory Spot_ID.location information

set query(Memory Spot_ID)=Memory Spot_ID.location queries

for query(Memory Spot_ID)中的每个查询q1do

if qj.tag_ID存在于loc(Memory Spot_ID) then

set loc(Memory Spot_ID)→qj.tag_ID.to_carry=1

删除qj

else if qj.timeout<0 then删除qj

end if

end for

运行算法3有助于释放内存点资源以及过往阅读器的通信开销，以便只处理未被回复的查询请求，并停止传输无用查询请求。算法4描述了过往阅读器为了信息传输而执行的同步过程中的最后一个操作(即操作4)。在该算法中，阅读器既携带剩余未被回复的查询请求，还携带了下个同步过程需要考虑的“to-carry”位置信息。为了避免出现回环，忽略该阅读器开始时创建的查询请求。当阅读器更新其位置信息时，它只考虑带有时间标记的标签位置，而不考虑对这些标签进行定位的阅读器。

算法4：位置查询携带算法—由阅读器运行。

输入：位置查询请求输出：经过更新的位置查询请求

set loc(Reader_ID)=Reader_ID.location information

set query(Reader_ID)=Reader_ID.location queries

set loc(Memory Spot_ID)=Memory Spot_ID.location information

set query(Memory Spot_ID)=Memory Spot_ID.location queries

for loc(Memory Spot_ID)中的每记录msjdo

if msj.to_carry=I then

将(msj.time,msj.tag_ID,msj.tag_position)加入

loc(Reader_ID)

end if

end for

for query(Memory Spot_ID)中的每个查询qido

if (qir_ID≠Reader_ID) then

将(qi.query_ID,qi.r_ID qi.tag_ID)加入

qurey(Reader_ID)

end if

end for

图3用一个例子阐述了本文算法的运行过程。在图3(a)中，阅读器R1定位了标签t1,t2,t3，且打算定位t4。然后，R1与最近的内存点ms1通信，更新t1,t2,t3的位置，并且登记一次关于t4的查询请求。阅读器R2也在ms1周围(见图3(b))。因此，R2用t5,t6的位置来更新ms1，携带R1生成的关于t4的查询请求。如图3(c)所示，当R2移动时，与内存点ms2通信，并且执行如下操作：用t5,t6的位置来更新ms2，将关于t4的查询请求递交给ms2。ms2具有之前其他过往阅读器更新的关于t4的位置信息。因此，ms2将t4的to_carry标记更改为1。相应地，R2携带该位置信息，通过其他内存点进行传输。如图3(d)所示，在ms2处，另一个阅读器R3对R2更新的位置感兴趣，因此它不需要登记查询请求便获得了这样的位置信息(t5的位置)。此外，R3用t7,t8的位置来更新ms2，且携带t4的位置。R1在移动时，与经过R2或R3更新过的内存点进行通信，进而获得t4的位置。

2 仿真实验

采用ns-3进行全面的仿真实验来评估本文算法和文献[14]中端对端拉引式(pull)传输策略的性能。采用文献[14]中的方案作为比较对象的主要原因是该方案也是通过使用一组异构移动式RFID阅读器来定位移动RFID标签(与本文类似)，且它具有较高的稳定性和可扩展性，与其对比更能体现本文方案的优越性。仿真中考虑两种性能评估指标：① 定位延时，表示算法对一次位置查询请求做出响应的平均时间；② 平均开销，表示算法参与方对一次位置查询请求做出响应需要的报文平均数量。在本文评估中研究两个主要参数的影响：内存点的数量和阅读器的数量。

2.1 仿真配置

利用ns-3技术和基于图形的ad hoc网络机动模型，仿真一个包含14个目标点的200 m×200 m区域。各点间通过宽度为8 m的路径相连，阅读器以0.75～1.25 m/s的速度在这些路径上移动。在仿真期间，阅读器在移动过程中可在每个目标点处逗留一段时间(比如说10 s)。每个阅读器在询问周围标签时阅读范围为4 m，在与内存点通信时阅读范围为30 m。我们部署足够数量的固定式标签(1 000个)，只随机选择100个标签在生成查询请求时使用。此外，在目标点和路径上部署不同数量的内存点，内存点的阅读范围为30 m，且不同内存点的阅读范围可能部分重叠。我们在阅读器数量和内存点数量不同的仿真环境下进行实验。在仿真期间，周期性地设置各个阅读器对某个随机标签感兴趣，并相应生成一个位置查询请求(每60 s)。在计算定位延时时，计算阅读器获得一次回复所需要的时间，并对生成的所有查询请求计算均值。在计算平均开销时，统计为了满足一次查询请求，阅读器和内存点间交换的报文数量，并对生成的所有查询请求计算均值。仿真总时间为5 000 s，所有数值均是采用不同的随机种子，独立运行10次所获得的数值。

(a)R1更新ms1并登记一次关于t4的查询

(b)R2更新ms1并携带R1生成的查询

(c)R2更新ms2并传输R1生成的查询，相应地ms2将t4标记为“to_carry”，因此R2携带t4

(d)R3更新ms2，寻找t5，携带t4

图3 位置信息传输算法运行过程示例图

2.2 仿真结果

考察两种传输策略下的仿真结果：① 端到端拉引式策略[14]，阅读器之间直接进行通信，以便获得需要的位置信息；② 本文策略，阅读器利用内存点传输位置信息，阅读器之间不直接通信。

2.2.1 定位延时

图4和图5分别描述了3种不同同步间隔条件下(60、90和120 s)，阅读器数量和内存点数量对定位延时的影响。如图4所示，增加阅读器数量后，有助于本文算法迅速传输针对内存点的位置查询请求，因此可在较短延时内对更多查询做出回复。采取拉引式策略时，定位延时显著下降，但是平均开销如图6所示。增加内存点数量对定位延时只有少量影响(平均3%，如图5所示)。这是因为内存点数量较高但同步频率较低时，位置信息请求或回复的传输时间可能变长，导致平均开销增大，如图7所示。

2.2.2 平均开销

图6和图7分别给出了阅读器数量和内存点数量对平均开销的影响。如图6所示，对于拉引式策略，增加阅读器数量后，由于需要在阅读器间广播位置查询请求和回复，因此平均开销较大。在本文算法中，当阅读器数量上升2倍时，即使同步频率较低，平均开销性能仍平均提升70%。原因是被及时更新的阅读器和内存点数量上升，于是利用较少的携带和转发报文，即可满足位置查询请求。当内存点数量翻倍时(如图7所示)，需要位置查询请求和回复来遍历更多个内存点，于是报文数量上升，开销增加。同步频率较低时，平均开销较少，此时阅读器在更新内存点之前维护位置信息及携带查询请求的时间变长。

图4 阅读器数量对定位延时的影响(15个内存点)

图5 内存点数量对定位延时的影响(75个阅读器)

图6 阅读器数量对平均开销的影响(15个内存点)

图7 内存点数量对平均开销的影响(75个阅读器)

3 结 语

针对典型的IoT大规模动态场景的一种分布式定位和位置信息传输算法贡献如下：① 利用异构非协调性移动RFID阅读器来实现周围标签的定位；② 利用内存点来维护位置信息的可用性；③ 设计一种分布式位置信息传输协议，通过使用内存点在RFID阅读器中传输位置信息。我们通过全面的基于ns-3的仿真实验验证了该算法的有效性。在下一步工作中，我们计划对已知的环境和应用中可以控制内存点最佳部署的参数进行研究，并考察移动阅读器按照事先确定好的路径移动时的系统性能。

[1] 侯陈达, 李 栋, 邱杰凡, 等. EasiDEF: 一种水平化轻量级物联网数据交换协议[J]. 计算机学报, 2015, 38(3): 602-613.

[2] 孙其博, 刘 杰, 黎 葬, 等. 物联网 概念, 架构与关键技术研究综述 [J]. 北京邮电大学学报, 2010, 33(3): 1-9.

[3] Ruiz A R J, Granja F S, Honorato J C P,etal. Accurate pedestrian indoor navigation by tightly coupling foot-mounted IMU and RFID measurements[J]. IEEE Transactions on Instrumentation and Measurement, 2012, 61(1): 178-189.

[4] Qian C, Ngan H, Liu Y,etal. Cardinality estimation for large-scale RFID systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(9): 1441-1454.

[5] Yang P, Wu W, Moniri M,etal. Efficient object localization using sparsely distributed passive RFID tags [J]. IEEE Transactions on Industrial Electronics, 2013, 60(12): 5914-5924.

[6] Oh H, An B, Smith A L,etal. An RFID localization algorithm for a plug-in electric vehicle recharging robot[C]// 2015 IEEE International Conference on Consumer Electronics (ICCE). London, UK: IEEE Press, 2015: 176-177.

[7] Choi B S, Lee J W, Lee J J,etal. A hierarchical algorithm for indoor mobile robot localization using RFID sensor fusion [J]. IEEE Transactions on Industrial Electronics, 2011, 58(6): 2226-2235.

[8] Han S, Lim H S, Lee J M. An efficient localization scheme for a differential-driving mobile robot based on RFID system [J]. IEEE Transactions on Industrial Electronics, 2014, 54(6): 3362-3369.

[9] Ekambaram V, Ramchandran K. SLAC-RF: Simultaneous 3D Localization of mobile readers and Calibration of RFID supertags [J]. EECS Department, University of California, Technical Report UCB/EECS-2012-188, 2012.

[10] Papapostolou A, Chaouchi H. RFID-assisted indoor localization and the impact of interference on its performance [J]. Journal of Network and Computer Applications, 2011, 34(3): 902-913.

[11] Ni W, Xiao W, Toh Y K,etal. Fingerprint-MDS based algorithm for indoor wireless localization[C]. 2010 IEEE 21st International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC). Istanbul, Turkey: IEEE Press, 2010: 1972-1977.

[12] Zhao Y, Liu Y, Ni L M. VIRE: Active RFID-based localization using virtual reference elimination[C]. 2014 IEE International Conference on Parallel Processing (ICPP). Minneapolis, USA: IEEE Press, 2014: 56-66.

[13] Bouet M, Pujolle G. L-VIRT: Range-free 3-D localization of RFID tags based on topological constraints [J]. Computer Communications, 2014, 32(13): 1485-1494.

[14] Eslim L M, Ibrahim W M, Hassanein H S. GOSSIPY: A distributed localization system for Internet of Things using RFID technology[C]//2013 IEEE Global Communications Conference (GLOBECOM). Atlanta, GA, USA: IEEE Press, 2013: 140-145.

Location Information Transmission Algorithm Based on Memory Spots in RFID Localization Systems

YEZhi-xiang1,ZHANGWei-le2

(1. The Economics and Management College, Guangdong Institute of Science and Technology, Zhuhai 519090, China; 2. The Ministry of Education Key Laboratory of Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China)

The existing RFID localization system is based on the centralized and fixed infrastructure which provides limited scalability and may not be plausible in typical IoT large-scale dynamic scenarios. To solve this problem, a distributed location information transmission algorithm based on memory spots is proposed in this paper. Firstly, heterogeneous uncoordinated mobile RFID readers localize the mobile or stationary passive RFID tagged-objects through indirect cooperation, and then the location information is disseminated by using the available memory spots in a given smart environment. Finally, mobile RFID readers use such memory spots to store tag locations and queries enabling exchange location information without the need for direct communication among readers. The results of comprehensive simulation experiment based on ns-3 indicate that the proposed algorithm outperforms the typical pull dissemination strategy in terms of localization delay and average overhead under different dynamicity settings.

RFID; localization systems; memory spots; readers; delay; average overhead

2015-10-19

国家自然科学基金(61302069/F010202)资助

叶志祥(1980-)，男，硕士，实验师，研究方向：云计算、内容中心网络。E-mail:tmzhuange_mail@sina.com

TP 391

A

1006-7167(2016)09-0120-06