基于卡间通信机制的射频识别传感器网络防碰撞系统及算法

摘要

本发明公开了基于卡间通信机制的射频识别传感器网络防碰撞系统及算法，本发明从现有防碰撞算法中所存在的性能滑坡和饥饿问题出发，根据现有硬件间集成传感器和通信模块的基础上，提出了标签通信时隙，并将其加入传统DFSA识别算法的标签识别过程之前，通过标签间通信，将有用信息集中到更少的标签上，从而减少参与识别过程的标签数。对于大数目标签快速识别情况有着十分显著的效果，可以进一步提高整个系统的吞吐率并降低碰撞率。

说明书

技术领域

本发明涉及射频识别无线传感网中的标签碰撞技术领域，更具体 涉及基于卡间通信机制的射频识别传感器网络防碰撞系统及算法。

背景技术

传统的标签碰撞主要出现在射频识别(RFID)领域。通常的RFID 系统由标签和阅读器构成。当多个标签同时在阅读器范围内需要被识 别时，碰撞问题就会发生。传统的解决办法包括ALOHA算法和基于 树的算法。前者较为常用，但其本身存在标签饥饿问题，同时当较大 数目的标签需要同时被识别的情况下，其性能滑坡也十分明显。 ALOHA算法的原理是通过分离标签的响应时间而降低标签碰撞的概 率，但最初的算法系统的吞吐率并不高。在其基础上提出了帧时隙 ALOHA算法(FSA)和动态帧时隙ALOHA算法(DFSA)。通过将时 间分成多个帧，再将帧分成不同的时隙。在每一帧中标签随机选择一 个时隙去响应阅读器，从而更进一步分离标签的响应时间而减小碰撞 的概率。但在大数目标签情况下，性能下降依旧十分明显。

在射频识别传感器网络中，图1、图2分别表示了其中两种主要的 网络结构，图1为智能标签网络；图2为传感阅读器网络。两种网络 结构分别对应了两种不同的需求：大范围特殊事件监测以及小范围密 集数据(标签)的快速收集(读取)。由于第一种网络结构标签在检测 到特殊事件，如发生火灾时，其通过特定的协议用多跳的方式，将信 息传递给阅读器，因此碰撞问题并不明显。而对于第二种情况而言， 当系统需要对某一阅读器范围内的标签进行快速读取，同时此处的标 签数目又十分大时，碰撞问题就异常突出。

传统DFSA算法及其问题

传统DFSA算法，阅读器读取标签的过程主要分为两大部分：标 签数目估计部分和标签识别阶段。阅读器将时间分为多个帧，而每个 帧又分为多个时隙，时隙的个数取决于需要被识别的标签数。当每一 帧开始时，标签就随机选择帧中的一个时隙，在这个时间段与阅读器 进行通信。

假设初始的一帧内的时隙数为L(帧长度)，总标签数为n，并且 每个标签都有等概率选择帧中的每个时隙，其概率为p＝1/L。根据统计 学原理，r个标签同时选中一个时隙的概率为：

$B_{n,1/L\left(r\right)}=\left(\begin{array}{c}n\\ r\end{array}\right){\left(\frac{1}{L}\right)}^r{(1-\frac{1}{L})}^{n-r}---\left(1\right)$

经过一帧的识别后，成功识别的时隙，空闲时隙和碰撞时隙的数学 期望分别为：

$a_1^{L,n}=L\times B_{n,1/L\left(1\right)}=n{(1-\frac{1}{L})}^{n-1}---\left(2\right)$

$a_0^{L,n}=L\times B_{n,1/L\left(0\right)}=n{(1-\frac{1}{L})}^n---\left(3\right)$

$a_k^{L,n}=L-a_0^{L,n}-a_1^{L,n}---\left(4\right)$

因此，如果标签数目和帧长度已知，我们就可以计算出成功识别 的时隙，碰撞时隙和空闲时隙的数目分别为多少。而反过来，如果每 一帧结束后，通过阅读器的查询可以得到以上三种不同状态时隙的时 隙数[a₀，a₁，a_k]，那么标签数目也可以通过(2)，(3)和(4)估计出来。 与此同时，整个系统的效率也可以通过(5)计算得到。

$S=\frac{a_1^{L,n}}{L}={\frac{n}{L}(1-\frac{1}{L})}^{n-1}---\left(5\right)$

为了得到系统效率的最大值，我们对(5)式进行求导：

$\left(\begin{array}{c}\frac{\mathrm{dS}}{\mathrm{dn}}=\frac{1}{L}{(1-\frac{1}{L})}^{n-1}+\frac{n}{L}{(1-\frac{1}{L})}^{n-1}\ln (1-\frac{1}{L})\\ =\frac{1}{L}{(1-\frac{1}{L})}^{n-1}[1+n\ln (1-\frac{1}{L})]=0\end{array}\right)---\left(6\right)$

$L=\frac{1}{{1-e}^{\frac{1}{n}}}---\left(7\right)$

当标签数n足够大时，我们可以得到：

$L\approx \frac{1+1/n}{1+1/n-1}=n+1---\left(8\right)$

当我们每一轮结束后，都让下一轮的帧长度等于要参与识别过程的 标签数时，系统的效率才能最大化。但对于RFID系统而言，帧长度只 能取L＝2ⁱ,i＝1,2,…8中的值，因此经过每轮对未识别标签数进行估计 后，动态的调整帧的长度使其最接近所估计的标签数就可以使系统效 率最大化。这就是DFSA算法的基本原理和流程。

但对于DFSA算法来说，它本身存在着几个问题。首先，由于最 大帧长度只能取到256，所以当标签数远大于256时，系统就无法让帧 长度趋近于为识别的标签数。对于这种情况来说，随着标签数的增多， 系统的整体吞吐率会下降剧烈，这也就是所谓的性能滑坡问题。与此 同时，DFSA算法还存在着标签饥饿问题。当我们假设帧长度和未识别 的标签数都是2时，两个标签都随机的选择两个时隙中的一个与阅读 器进行通信。然而，当每一轮两个标签都选择同一个时隙时，这两个 标签将长时间无法被识别，这种情况也就是所谓的标签饥饿问题。该 问题是DFSA算法本身的机制不完善造成，对于整个系统的性能也有 着较为严重的影响。

发明内容

(一)要解决的技术问题

本发明要解决的技术问题是如何降低射频识别传感器系统中的标 签碰撞率，提高系统吞吐量。

(二)技术方案

为了解决上述技术问题，本发明提供了基于卡间通信机制的射频 识别传感器网络防碰撞系统，包括智能标签，所述智能标签的硬件结 构包括处理器与内存、ADC、传感器、接收器、调制器、功放以及天 线；

所述传感器的输出端连接所述ADC的信号输入端，进行模数转换， 所述ADC的输出端连接所述处理器与内存，所述处理器和内存存储标 签信息和传感器传送的经ADC转换的数字信息；所述天线的一端连接 功放，所述功放将阅读器电磁波的电磁能经过放大给所述ADC和所述 处理器与内存提供电能；所述天线的另一端连接所述接收器的接收端 和所述调制器发送端；所述接收器的输出端连接所述处理器与内存的 输入端，所述调制器的输入端连接ADC的输出端；接收器接收标签信 息并将其存储到所述处理器与内存中，标签中的信息通过所述ADC将 所述处理器与内存中的数据发送给调制器进行数据调试，在通过天线 将数据发送出去。

基于卡间通信机制的射频识别传感器网络防碰撞算法，所述算法 包括以下步骤：

S1、标签通信时隙包括配对阶段和通讯阶段两个阶段；

所述配对阶段具体为：

S11、初始化，检查标签自身的数据量是否超过阈值，如果超过阈 值，标签退出标签通信时隙；否则进行下一步；

S12、标签通过算法计算自己与邻居标签间的距离，找到与自己距 离最近的邻居标签；

S13、所述标签向自己距离最近的邻居标签发送配对请求信息，并 接收其他标签的请求配对信息，所述标签会通过自己收到的配对请求 信息和从所述最近邻居标签的返回信息来判断自己是否配对成功；如 果配对不成功进入下一轮配对阶段；如果配对成功退出配对阶段，等 待进入所述通讯阶段；

所述通讯阶段具体为：配对成功的两个标签随机确定数据发送方 和数据接收方，所述数据发送方将自身标签内的信息发送给所述数据 接收方并退出所述算法，所述数据接收方则在接收成功后，等待进入 下一阶段；

S2、标签识别阶段；阅读器计算待识别的标签数、阅读器利用DFSA 算法动态的调整下一帧的时隙数使其趋近于所述待识别的标签数，并 通过DFSA算法完成标签识别过程直到所有标签都被识别。

优选地，所述步骤S12中标签通过算法计算自己与邻居标签间的 距离，使用的算法为到达时间算法。

优选地，所述步骤S13中所述标签会通过自己收到的配对请求信 息和从所述最近邻居标签的返回信息来判断自己是否配对成功，所述 返回信息包括成功和失败。

优选地，所述步骤S13中所述标签会通过自己收到的配对请求信息 和从所述最近邻居标签的返回信息来判断自己是否配对成功包括以下 情况：

(1)所述标签收到的配对信息请求中，有来自其最近邻居标签的 请求，二者互发配对“成功”的返回信息，退出配对阶段，等待通讯阶 段的开始；与此同时，若所述标签还收到了来自其他标签发来的配对 请求信息，向其返回“失败”信息；

(2)所述标签收到来自最近邻居标签的“失败”的返回信息，同时 它还收到了来自其他邻居标签的配对请求信息时，在所收到的全部配 对请求信息中选择距离其最近的标签，向其返回“成功”信息，若还有 其他标签配对请求，则向其他返回“失败”信息，并退出配对阶段，等 待进入所述通讯阶段；

(3)所述标签没有收到其最近邻居标签的配对请求信息，收到其 返回的“成功”信息时，则所述标签和其最近邻居标签配对成功；与此 同时，如果所述标签还收到了来自其他标签发来的配对请求信息，向 其返回“失败”信息，退出配对阶段，等待进入所述通讯阶段；

(4)所述标签收到来自最近邻居标签的“失败”返回信息，同时在 规定时间内没有收到来自其他标签的配对请求信息，则所述标签的最 近邻居标签已配对成功，同时其也不是其他标签的最近邻居标签，所 述标签配对失败，等待并进入下一轮配对阶段进行配对。

优选地，所述配对阶段共2轮，如果经过两轮配对阶段均没有配 对成功，则所述标签退出标签通信时隙，等待进入下一阶段。

(三)有益效果

本发明提供了基于卡间通信机制的射频识别传感器网络防碰撞系 统及算法，通过将RFID卡片与传感器节点相融合，产生了一种新的智 能标签的硬件，结合标签的特性，本发明将标签间通信机制引入标签 识别过程中，结合DFSA算法，有效提高了整个体统的吞吐率，降低 了标签碰撞概率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面 将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而 易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域 普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些 附图获得其他的附图。

图1为智能标签网络；

图2为传感阅读器网络；

图3为本发明的基于卡间通信机制的射频识别传感器网络防碰撞 系统的智能标签硬件结构示意图；

图4为标签通信时隙所处位置示意图；

图5为本发明的基于卡间通信机制的射频识别传感器网络防碰撞 算法的流程图。

具体实施方式

下面结合附图和实施例对本发明作进一步详细描述。以下实施例 用于说明本发明，但不能用来限制本发明的范围。

图3为本发明的基于卡间通信机制的射频识别传感器网络防碰撞 系统的智能标签硬件结构示意图；所述智能标签的硬件结构包括处理 器与内存、ADC、传感器、接收器、调制器、功放以及天线；所述传 感器的输出端连接所述ADC的信号输入端，进行模数转换，所述ADC 的输出端连接所述处理器与内存，所述处理器和内存存储标签信息和 传感器传送的经ADC转换的数字信息；所述天线的一端连接功放，所 述功放将阅读器电磁波的电磁能经过放大给所述ADC和所述处理器与 内存提供电能；所述天线的另一端连接所述接收器的接收端和所述调 制器发送端；所述接收器的输出端连接所述处理器与内存的输入端， 所述调制器的输入端连接ADC的输出端；接收器接收标签信息并将其 存储到所述处理器与内存中，标签中的信息通过所述ADC将所述处理 器与内存中的数据发送给调制器进行数据调试，在通过天线将数据发 送出去。

对于硬件结构而言，由于在射频识别传感器网络中，信息传递通 过相关硬件设备的提出而变得便利起来。因此，本发明在硬件结构上 也充分利用了这一特点，智能标签本身集成了相关的传感器，可以时 刻感知周围环境的信息并实时记录下来。标签也具有通信的能力，通 过其硬件上集成了相关微型的接收和发射器，可以完成标签间信息的 交互功能。由于传统的无源RFID标签在阅读器电磁波覆盖范围内，可 以通过阅读器电磁波产生的感应电流给标签进行供电，并完成和阅读 器间通信的功能。因此我们在该原理的基础上提出了一种标签间通信 的节能方式，即当标签在有阅读器电磁波覆盖的情况下，利用功放将 所述电磁波的电磁能进行放大，为标签间通信进行供能，从而进一步 达到节能的目的，同时也可以使标签在不耗费本身的能量的前提下， 完成更多通信功能。本发明的智能标签也可集成电池供电，以半有源 的方式进行供能，当工作在大范围突发事件监测情况下，由于标签间 距离较远且只有靠近阅读器或基站的少部分标签能被电磁波覆盖，标 签的供能由本身集成的电池供电；但当面对小范围内多目标快速识别 的情况时，由于大部分标签都被阅读器的电磁波覆盖，因此其间的通 信可以利用电磁波产生的电磁能，再结合本发明的基于卡间通信机制 的射频识别传感器网络防碰撞算法，就可以进一步提高在射频识别传 感器网络中大数目标签的识别效率。

本发明在RFID领域的基础上结合无线传感网中信息通信的便利 性提出了一种基于标签间通信的防碰撞算法。该算法在传统DFSA的 识别过程中，加入了标签通信时隙概念。传统的DFSA算法在整个过 程中包括标签数目估计和标签识别，当还有待识别的标签时就开启下 一帧直到所有标签识别完毕，这一部分在背景技术中进行了介绍。本 发明所加入的标签通信时隙在标签数目估计和标签识别过程之间，在 标签还没开始被识别之前，让标签间通过配对阶段、通讯阶段的过程， 将大量标签中的有用信息集中在更少的标签数目上，并实时统计最终 成功配对的标签数，从而计算最终进入识别阶段的标签数目，再利用 传统DFSA算法动态的调整帧长度，来确保整个算法的吞吐率最大化， 其具体位置如图4所示。

本发明的算法的流程图如图5所示，包括以下步骤：

S1、标签通信时隙包括配对阶段和通讯阶段两个阶段；

所述配对阶段具体为：

S11、初始化，检查标签自身的数据量是否超过阈值，如果超过阈 值，标签退出标签通信时隙；否则进行下一步；

S12、标签通过到达时间算法计算自己与邻居标签间的距离，找到 与自己距离最近的邻居标签；

S13、所述标签向自己距离最近的邻居标签发送配对请求信息，并 接收其他标签的请求配对信息，由于对于每个标签来说自己的最近邻 居节点不一定是相互的，所以所述标签会通过自己收到的配对请求信 息和从所述最近邻居标签的返回信息来判断自己是否配对成功，所述 返回信息包括成功和失败；判断配对是否成功的过程包括以下四种情 况：

(1)所述标签收到的配对信息请求中，有来自其最近邻居标签的 请求，二者互发配对“成功”的返回信息，退出配对阶段，等待通讯阶 段的开始；与此同时，若所述标签还收到了来自其他标签发来的配对 请求信息，向其返回“失败”信息；

(2)所述标签收到来自最近邻居标签的“失败”的返回信息，同时 它还收到了来自其他邻居标签的配对请求信息时，在所收到的全部配 对请求信息中选择距离其最近的标签，向其返回“成功”信息，若还有 其他标签配对请求，则向其他返回“失败”信息，并退出配对阶段，等 待进入所述通讯阶段；

(3)所述标签没有收到其最近邻居标签的配对请求信息，收到其 返回的“成功”信息时，则所述标签和其最近邻居标签配对成功；与此 同时，如果所述标签还收到了来自其他标签发来的配对请求信息，向 其返回“失败”信息，退出配对阶段，等待进入所述通讯阶段；

(4)所述标签收到来自最近邻居标签的“失败”返回信息，同时在 规定时间内没有收到来自其他标签的配对请求信息，则所述标签的最 近邻居标签已配对成功，同时其也不是其他标签的最近邻居标签，所 述标签配对失败，等待并进入下一轮配对阶段进行配对。

如果配对不成功进入下一轮配对阶段；如果配对成功退出配对阶 段，等待进入所述通讯阶段；为确保大部分标签可以配对成功，且整 个算法又不会持续时间过长，配对过程共两轮。若两轮都没有配对成 功，标签自动退出标签通信时隙，等待下一阶段的开始。

所述通讯阶段具体为：配对成功的两个标签随机确定数据发送方 和数据接收方，所述数据发送方将自身标签内的信息发送给所述数据 接收方，并退出本发明的算法，所述数据接收方则在接收成功后，等 待进入下一阶段；

S2、标签识别阶段；阅读器计算待识别的标签数；阅读器利用DFSA 算法动态的调整下一帧的时隙数使其趋近于待识别的标签数；并通过 DFSA算法完成标签识别过程直到所有标签都被识别。

以上实施方式仅用于说明本发明，而非对本发明的限制。尽管参 照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解， 对本发明的技术方案进行各种组合、修改或者等同替换，都不脱离本 发明技术方案的精神和范围，均应涵盖在本发明的权利要求范围当中。