射频识别(radio frequency identification, RFID)技术是物联网应用的关键技术之一。RFID被广泛应用于工业自动化、商业自动化、交通运输等众多领域。RFID研究的主要目的是快速有效地读取标签存储的信息。现有基于时槽、基于树的方法，以及结合时槽和树的混合方法可以有效地读取标签信息，但RFID标签存储的信息长度固定，且容量较小，限制了RFID应用范围^[1-3]。

无线传感器网络由大量传感器节点组成，具备感知能力、数据处理能力和无线通信能力^[4]。基于物联网的应用需要节点采集信息并返回到基站进行及时处理。现有协议因为协调传感器节点之间通信、发送控制信息等会消耗大量能量^[5-6]，因此如何在最短时间内准确有效的采集传感器节点信息是研究的关键^[7-8]。

目前，有研究者将RFID和传感器节点相结合做了一些工作，但相关研究还比较少。文献[8]是最先提出将主动式标签与传感器节点进行结合的协议，该协议在已知所有标签的条件下，利用7个哈希函数的方法(MIC)收集与主动式标签绑定的传感器节点信息。文献[9]提出一种基于采样的信息收集协议-SIC。SIC根据感知数据的相关性，估计相邻两次数据误差范围，以此降低传输负载和协议执行时间。同时，标签丢失和未知标签加入会造成收集的信息可靠性降低，因此检测丢失标签和收集未知标签势在必行。文献[10]提出的TRP协议虽能够保证以较高的概率检测出一个标签集合是否完整，但时间复杂度较高。文献[11]对基于ALOHA协议进行了改进，提出了检测丢失的标签算法DM和收集未知的标签算法CU，两者虽然准确率较高，但耗时过长。

本文提出了一种基于被动式的数据收集协议(protocol using passive tag to collect information, PTC)，它将每个帧分割为若干个不同大小的时槽，从而缩短执行时间。也提出一种主动式的数据收集协议(protocol using active tag to collect information, ATC)，能够进一步缩减执行时间。同时，ATC协议能够收集远距离标签信息，可以采用预先分配时槽的方法，减少空时槽和冲突时槽的分配，以保证执行时间与时间下界基本相同。此外，本文提出一种用来检测丢失标签和收集未知标签的算法(algorithm to detect missing tags and collect unknown tags，ADMCU)能够保证收集信息的准确性。

1 基于被动式标签的信息收集协议PTC 1.1 PTC协议概述

如果仅有一个标签哈希到时槽i中，将i称为单时槽。如果没有标签哈希到时槽i中，将i称为空时槽。单时槽和空时槽以外的时槽统称为冲突时槽。若j个标签同时哈希到时槽i中，将i称为j冲突时槽。

在协议中，当第i帧结束和开始时未收集标签数之比ε_i不小于剩余标签数与要收集标签总数n_i之比β时，开始信息收集过程。首先，读数器向所有标签发送帧长f(每帧包含f个时槽)和第i帧上的随机数r_i。标签根据f_i(第i个帧的时槽长度)、r_i和标签id，通过哈希函数h_f(id, r_i)计算自己在当前帧中回复信息的时槽位置l。将标签传送的传感器节点的信息简称为标签的信息。每个标签有一个计数器，初始值为l。如果是单时槽，则读数器收集信息, 回复信息的标签进入睡眠状态，读数器在该时槽结束时向所有标签发送结束信息0；否则在该时槽的前一个时槽结束时发送0。标签收到结束信息后，将l减一并判断l是否为0，如果l为0，则向读数器发送自己的信息。哈希到单时槽的标签恰好在l减为0时回复信息，然后标签进入睡眠状态，避免该标签参与下一个帧。哈希到其它时槽的标签则保持活跃，等待下一帧哈希到单时槽时回复信息。当第i帧结束时，如果ε_i小于β，则信息收集结束，如果此时如果还有未收集的标签，采用PIC^[8]协议去收集余下的标签。

1.2 协议性能分析

在PTC协议中，当剩余标签数是n′，帧长为f′时，k个标签哈希到某个时槽(S_n值相同)的概率为:

$ C_{n'}^k\frac{1}{{f'}}{\left( {1 - \frac{1}{{f'}}} \right)^{n' - k}} $

(1)

设在第i帧开始时，未收集到的标签数为n_i，第i个帧有f_i个时槽，则根据式(1)可知，单时槽的概率q₁为$ C_{{n_i}}^1\frac{1}{{f_i}}{\left( {1 - \frac{1}{{f_i}}} \right)^{{n_i} - 1}}$。在第i个帧结束时，读数器读取了q₁f_i个标签，则未读取标签数量为n_i-q₁f_i，则剩余标签例ε_i为$ \frac{{\left( {{n_i} - {f_i}{q_1}} \right)}}{{{n_i}}} = 1 - \frac{{{f_i}{q_1}}}{{{n_i}}} = 1 - {\left( {1 - \frac{1}{{{f_i}}}} \right)^{{n_i} - 1}} \approx 1 - {e^{ - \frac{{{n_i}}}{{{f_i}}}}}$, 即${f_i} = - \frac{{{n_i}}}{{\ln \left( {1 - {\varepsilon _i}} \right)}} $。

因为第f_i帧结束时未读取的标签总数与第f_i+1帧开始时未读取的标签数相同，所以n_i+1=n_iε_i，且n₁=n，m个帧执行完毕后，剩余标签数变为n_m+1=n_mε_m=n_m-1ε_m-1ε_m=nε₁ε₂…ε_m，理论上每一帧中剩余标签的比例均相同，即ε₁=ε₂=…=ε_m，设ε₁=ε，则m个帧执行完毕剩余标签数为ε^m+1。为保证剩余标签比例小于β，则

$ {\varepsilon ^{m + 1}} < \beta $

(2)

协议执行的总时槽数F为：

$ \begin{array}{l} F = \left( {{f_1} + {f_2} + {f_3} + \cdots + {f_m}} \right) = \\ \left( { - \frac{n}{{\ln \left( {1 - \varepsilon } \right)}}} \right) + \left( { - \frac{{n\varepsilon }}{{\ln \left( {1 - \varepsilon } \right)}}} \right) + \cdots \left( { - \frac{{n{\varepsilon ^m}}}{{\ln \left( {1 - \varepsilon } \right)}}} \right) \end{array} $

(3)

为了保证F最小，则：

$ \frac{{\partial F}}{{\partial \varepsilon }} = 0 $

(4)

β很小可忽略，则由式(2)~(4)得：m=31，ε=1-e^-1。

如图 1所示，T₁为读数器广播结束时刻到标签回复开始时刻的等待时延。T₂为标签回复结束时刻到读数器再次广播开始时刻的等待时延，根据文献[13]可知，T₁=T₂。设τ为发送1比特数据的时间，当标签回复的信息为x比特时，Tg=xτ。因为Tf₁+Tf₂+…+Tf_m=Fτ，则协议执行总时间T为:

$ \begin{array}{l} T = nxt + n\left( {{T_1} + {T_1}} \right) + \left( {\left( { - \frac{n}{{\ln \left( {1 - \varepsilon } \right)}}} \right)} \right. + \\ \left( { - \frac{{n\varepsilon }}{{\ln \left( {1 - \varepsilon } \right)}}} \right) + \left( { - \frac{{n{\varepsilon ^2}}}{{\ln \left( {1 - \varepsilon } \right)}}} \right) + \cdots + \\ \left. {\left( { - \frac{{n{\varepsilon ^{m - 1}}}}{{\ln \left( {1 - \varepsilon } \right)}}} \right)} \right)\tau {\rm{ = }}\mathit{nx}\tau \mathit{ + 2n}{\mathit{T}_1} + \tau \left( {\frac{n}{{1 - \varepsilon }}} \right) \end{array} $

(5)

如果将PTC直接用在主动式标签上，所有的标签必须一直保持active，需要重新设计协议。

2 基于主动式标签的协议ATC 2.1 ATC协议

读数器初始化数组V_c，V_c的长度等于帧长f，V_c每一位对应f的一个时槽。f等于未收集标签总数，则在第一帧中，f=n。读数器从第一个时槽开始判断当前时槽是否为单时槽，如果是，就将V_c的第一位置1，否则置0，以此类推，直到第f个时槽。然后读数器依次向所有标签发送f、r和V_c。因为每次发送96 bit，则一个V_c需传送$ ⌊\frac{{\left| {{V_{\rm{c}}}} \right|}}{{96}}⌉$次。

标签收到f和r后计算自己的在当前帧中回复信息的时槽位置S_n，并存在计数器中。标签只需要接收V_c[k](1≤k≤S_n)的值。并检查V_c[S_n]是否为1，如果是，计算V_c的前S_n位中0的总数(记为c)，并使S_n=S_n-c；否则标签进入睡眠状态，下一帧开始时再醒来。在该帧中，未睡眠的标签在S_n时槽位置向读数器回复信息，然后进入睡眠状态以保证不参与下一帧。下一个帧也执行相同操作，以此类推，直到所有标签信息都被收集完毕，或者当剩余标签的概率小于β时算法结束。如果剩余标签的比率小于β，则采用PIC收集剩余的标签。

2.2 ATC性能分析

由于t_inf是标签向读数器发送回复信息所消耗的时间，并且共有n个标签进行回复，因此这n个标签回复的总时间下界为nt_inf。

ATC的期望时间是t_inf的n倍与读数器发送V_c的时间之和，其它时间可忽略不计^[1]。由于t_id是读数器广播一个标签id及其CRC校验码所消耗的时间，根据文献[14]可知，一个标签id长度是64位，其CRC校验码长度是32位，所以t_id是广播96 bit数据所消耗时间。由3.2中分析可知:

$ \begin{array}{l} \mathit{{\rm T} = n}{\mathit{t}_{{\rm{inf}}}} + \frac{{n{t_{{\rm{id}}}}}}{{96}}\left( {n + n\varepsilon + n{\varepsilon ^2} + \cdots + n{\varepsilon ^m}} \right) = \\ \mathit{n}{\mathit{t}_{{\rm{inf}}}} + \frac{{n{t_{{\rm{id}}}}}}{{96}}\left( {\frac{1}{{1 - \varepsilon }}} \right) \end{array} $

(6)

当t_inf=t_id/12和t_inf=t_id时，ATC的执行时间分别是下界的1.34倍和1.04倍。

2.3 ATC与MIC执行时间比较

在MIC^[8]协议中，标签需要存储7个哈希函数，且需要多次计算。而本文提出的ATC协议只需一个哈希函数，存储量是MIC协议的1/7。

MIC执行时间为$\mathit{{\rm T}}' = \frac{n}{{{p_k}}}{\mathit{t}_{{\rm{inf}}}} + \frac{n}{{32{p_k}}}{t_{{\rm{id}}}} $，其中p_k=86.1%。当t_inf=t_id/12时，MIC和ATC执行时间分别为下界的1.61倍、1.34倍。当t_inf=t_id时，MIC和ATC执行时间分别是下界的1.2倍、1.04倍。随着t_inf增大，MIC执行时间最少是下界的1.16倍，而ATC执行时间与下界时间相等。

由于PTC和ATC需要知道所有标签id才能进行信息收集，并且这些标签id的准确性决定信息收集的准确率，因此及时获取准确的标签id信息至关重要。又因为标签集合随时会发生改变，所以为检测丢失标签并收集未知标签，保证标签id信息的准确性，本文提出了耗时短且准确率高的ADMCU算法。

3 ADMCU算法

在ADMCU协议中，读数器向所有标签发送帧长f和随机数r，标签根据f，r和自己的id，通过哈希函数计算自己在当前帧中回复信息的时槽位置S_n，并保存在计数器中。当时槽结束时，读数器向标签发送0结束该时槽。标签收到0后，将S_n减1并判断S_n是否为0。如果S_n为0，则标签发送其id给读数器证明其存在。标签id的长度是64位，回复全部id非常耗时，如果回复id的第0、9、18、27、36、45、54、63位，则可降低标签回复信息时间消耗、减少标签能量消耗。由于2个标签回复相同信息的概率为(1/2)⁸，所以读数器判断出错的概率仅有1/64。如果一个时槽内有多于一个标签回复信息，则该时槽发生冲突。如果一个帧中存在时槽冲突，那么读数器再发送另一个f和r，重复上述过程，直到没有冲突时槽的帧为止。

当剩余标签数是n_i，帧长为f_i时，k个标签哈希到某个时槽的概率为$ {q_1} = C_{{n_i}}^1\frac{1}{{{f_i}}}{\left( {1 - \frac{1}{{{f_i}}}} \right)^{{n_i} - 1}}$，当n=f时，$ \frac{{\partial {q_1}}}{{\partial f}} = 0$，因此当n=f时单时槽的概率最大，此时$ {q_1} = {\left( {1 - \frac{1}{{{f_i}}}} \right)^{{n_i} - 1}} \approx {{\rm{e}}^{ - 1}} \approx 36.8{\rm{\% }}$，所以f设置为未收集的标签总数。

每个标签都有一个标志寄存器，存储标志位flag，初始值为0。由于读数器已知所有标签的id以及哈希函数，因此读数器能够计算出所有时槽的类型。设在第i个帧开始前读数器计算得到的结果和第i个帧的结果如图 2所示。

读数器在第i个帧的每个时槽执行操作如下：

1) 读数器发送0结束该时槽；

2) 哈希到该时槽标签丢失，读数器将这些标签加入到丢失标签集合中，并发送0结束该时槽；

3) 有未知的标签哈希到该时槽内，读数器广播2，哈希到这个时槽的标签收到信息后将自己的flag置1。读数器发送0结束该时槽；

4) 可能有未知的标签哈希到该时槽内，本应哈希到这个时槽的唯一的标签可能丢失，将这个标签的id加入到集合S_wait中。读数器广播2，哈希到这个时槽的标签收到信息后将自己的flag置1。读数器发送0结束该时槽；

5) 一种情况是回复信息的标签就是本该哈希到该时槽的标签，另一种情况是本该哈希到这个时槽的标签丢失，并且一个与丢失标签回复相同信息的未知标签哈希到该时槽。当该时槽只有一个标签回复，且回复的信息与读数器计算得到的信息不同时，由于读数器无法判断出有几个标签哈希到这个时槽中，所以读数器认为该时槽是冲突时槽，本文将这种情况归结为4)。读数器广播1，使得哈希到该时槽的标签进入睡眠状态，以保证标签不参与下一帧，读数器发送0结束该时槽。当第二种情况发生时，读数器无法检测当前丢失的标签和未知的标签，但由于两个标签回复信息相同的概率是(1/2)⁸，所以读数器判断出错的概率仅为(1/2)⁸；

6) 可能有标签丢失，也可能有标签加入，但是由于读数器无法判断出当前时槽是否为单时槽，并认为该时槽是冲突时槽，将6)归结为7)；

7) 可能有标签丢失，可能有未知的标签哈希到该时槽，也可能既没有丢失的标签也没有未知的标签。读数器发送0结束该时槽，哈希到该时槽的标签等待在下一帧中被收集。

如没有flag为1的标签，读数器发送f_i+1和r_i+1重新开始一个帧，其中f_i+1等于当前剩余标签的总数，否则读数器首先广播3通知所有flag为0的标签进入睡眠状态，并采用基于时槽的ALOHA来收集所有未睡眠的标签的id，将收集到的结果放入集合S_un中，并将集合S_un、S_wait中除去集合S_wait和S_un相交的部分分别加入集合U和M中。

4 模拟试验

为了验证本文协议的有效性，本文构建一个模拟平台：若干个节点随机地部署在200 m×200 m网络中，并根据文献[8]设置相关实验参数和条件。

4.1 ATC的时间性能

根据文献[8]，等待时槽T₁为302 us，读数器向标签发送数据速率是26.5 kb，则传送1 bit需37.76 μs，标签向读数器回复信息的速率是53 kbit/s，则传输1 bit数据需18.88 μs。如果标签需要向读数器发送1比特信息，那么t_inf等于312 μs(不含CRC)。因为t_id是发送64 bit的id和32 bit的CRC时间之和，所以读数器向标签发送96 bit的信息所需要的时间t_id等于3 927 μs(含等待时槽)。

为了验证ATC和PTC的时间性能，将ATC、PTC与MIC^[8]协议以及PIC进行对比。当ATC和PTC算法的结束条件β=10^-6时，表 1给出了n=1 000时，4个协议的执行时间以及执行时间下界，B表示每个标签需要回复信息的数据量(bit)。

由表 1可知，当比特数较小时，PTC比MIC执行时间长。随着B的增大PTC和MIC执行时间逐渐接近，当B大于64时，PTC协议的执行时间低于MIC，这是由于随着比特数的增大，读数器发送结束信息的总时间对整个执行时间影响变小(根据式(5))。无论比特数如何变化，ATC执行时间都小于MIC、PTC和PIC，并与下界非常接近，这是因为ATC发送的数组更小，发送时间比PTC中读数器发送结束信息时间更短。

将比率定义为协议执行时间与下界时间的差比上下界时间。图 3分别表示n=100和n=900时，比率的变化情况。不难发现，随着B的增加，3个协议的比率的值不断减少，这是因为3个协议中发送数组的大小对整个执行时间的影响变小。当B增大到128后，MIC执行时间与下界之差趋于稳定，但ATC和PTC与下界的差距仍然不断减少，其中ATC与下界的差距最小。

表 2给出了B=128时，PIC、MIC、PTC、ATC和SIC^[9]五个协议的执行时间以及执行时间的下界。由于n的增加使得传输数据量增大，协议的执行时间就会随之增加。无论n取何值，MIC和PIC执行时间的比值都介于43%和50%之间；PTC和ATC的执行时间均比MIC和PIC短，其中ATC执行时间始终最短，并且与下界时间几乎相同, 这与式(6)的结论吻合。SIC的执行时间比ATC执行时间略短，但SIC是一种近似算法，要以降低数据收集的精度为代价来减少执行时间。

4.2 PTC的低能耗性

根据文献[15]，主动式标签接收200 bit信息耗能57 mW，发送200 bit信息耗能43 mW。图 4分别为n=100和n=600时，每个标签平均能量消耗。帧的个数的增加会导致接收信息能耗增大，而ATC帧的个数大于MIC，所以ATC中标签接收信息的能耗大于MIC。在MIC中，有些标签需多次给读数器回复信息，而ATC每个标签只需回复一次信息，所以ATC标签发送信息的能量小于MIC。当标签较小时，标签发送信息的能耗在整个能量消耗中影响较大，所以在图 4(a)中，ATC中每个标签的平均能耗小于MIC。当标签较大时，标签接收信息的能耗在整个能耗中影响较大，所以ATC中每个标签的平均能耗大于MIC。而无论n如何变化，PTC中标签的能耗都为0。

4.3 ADMCU的时间性能

为了验证ADMCU的时间性能，本文将TRP和ADMCU的执行时间进行比较。当w=1，a=0.9时，图 5分别给出了s=5和10时，TRP和ADMCU协议执行时间。当n增大时，由于传输数据量的增大，执行时间增加。但是无论n如何变化，ADMCU的执行时间都小于TRP。

当w=1时，图 6分别给出了s=20、n=3k和s=15、n=4k时TRP和ADMCU的准确率变化情况。当协议执行时间增大时，由于帧长的增加，准确率提高。但是无论执行时间如何变化，ADMCU的准确率都大于TRP。

在图 7和图 8中，假设没有未知的标签并且丢失的标签数为1，将ADMCU与基于时槽的ALOHA和文献[11]提出检测丢失标签算法DM、收集未知标签算法CU进行比较。在不同的丢失率和未知率下，本文的ADMCU明显低于其他2种算法。

5 结论

1) PTC可以在标签无需电池的前提下有效收集信息。

2) ATC采用预先分配时槽方法，减少空时槽和冲突时槽的分配，使得执行时间与下界时间几乎相同。

3) ADMCU有效地检测丢失标签和未知标签，保证了PTC和ATC的正确执行。

4) 相比于MIC和PIC，在传送信息总量较多的情况下，PTC与ATC的执行时间更短，且无论信息总量如何变化，ATC的执行时间始终最短；相比于TRP和DM、CU，在相同的准确率的情况下，ADMCU的执行时间更短。