RFID系统中的一种改进的自适应多叉树标签防碰撞算法研究

郭荣

摘 要

针对AMSA算法存在的不足，本文提出了IAMSA算法。并通过性能与仿真分析，验证了IAMSA算法能够有效地减少空闲时隙，提高检测速度。

【关键词】物联网 RFID 多叉树 防碰撞算法

1 引言

在RFID系统中，阅读器利用标签防碰撞算法来实现覆盖范围内的多个电子产品标签的读取。而基于树的防碰撞算法被广泛地采用。但是多数基于树的算法并没有充分利用碰撞信息，仅仅使用了前几位的信息。通常情况下，分支内标签数越多，碰撞的位数也将会越多，那么在总比特位中，碰撞位占的比例就越大。在识别的过程中，根据碰撞比例，如果能够自适应地选择使用几叉树，就能够提升算法的效率，减少系统用时。AMSA（Adaptive Multi-tree Search Anti-collision，自适应多叉树防碰撞）算法就是基于这一原则。

虽然AMSA算法根据根据碰撞因子u并不能推断出当前碰撞节点下有多少标签。为了解决这个问题，本文提出了一种改进的自适应多叉防碰撞（简称IAMSA）算法。

2 IAMSA算法

IAMSA算法的工作流程如下：（1）阅读器对查询前缀栈进行初始化即清空栈，并发送ε指令；（2）每个标签与此时阅读器发出的查询前缀相比较，只有相同的标签才作出响应；（3）如果此时作出响应的标签数为一时，则识别成功，转到第六步；如果此时没有标签响应，那么就不需要继续对该分支进行搜索，转到第六步；而如果有多个标签作出了响应，则发生碰撞；（4）阅读器计算碰撞因子u。如果u<0.75，使用二叉树，接着依据碰撞比特的首位信息，确定两个新的查询前缀；如果u≥0.75，使用四叉树，阅读器发送查询碰撞位最高两位前缀的指令，而标签则反馈一个含有碰撞位信息的四位码给阅读器，那么阅读器将根据反馈判断已存在于系统中的前缀；（5）新产生的前缀入栈，栈首前缀被取出并发给标签，接着转到第二步；（6）前缀堆栈如果不为空，栈首前缀被取出并发给标签，接着转到第二步，如果为空，识别过程结束。

3 性能分析

假设有m个待识别的标签，并且当搜索深度为k时，每个子节点上的平均标签数为3，那么，当搜索深度小于k时，使用无空闲时隙的四叉树，否则采用二叉树。k=。

假设从o到k层的四叉树都没有去除空闲时隙，可以得出

T4-ary= （1）

当采用二叉数进行搜索是，可以得出

T2-ary = （2）

虽然IAMSA算法使用了无空闲时隙的四叉树，但是当碰撞被阅读器检测到后，其第二次发送指令仍然需要占用一个时隙，而这个指令所使用的时隙数Tcomm与碰撞时隙数T4-coll相等。

下面，将分别计算四叉树中的碰撞时隙T4-coll与空闲时隙T4-idle。

假设有m个待识别的标签，在四叉树的第l层的任意k个标签选中同一个节点响应的概率为：

（3）

其中，p=4-L，这是因为完全四叉树的第l层有个4L节点，所以选择任意一个节点的概率为4-L。

空闲概率为

（4）

成功识别概率为

（5）

碰撞概率为

（6）

令qLi/m表示第L层的第i个节点被搜索到的概率。当L=0时，根节点总是能被访问到，即q0i/m=q00/m=1。对于其它的节点，只有其父节点产生了碰撞，其才能被访问到，因此

qLi/m=qL/m= （7）

其中βLi/m表示第L层的第i个节点发生碰撞的概率。如果同层中的节点发生碰撞的概率是一样的，那么

（8）

而 等于所有的 之和，因此

（9）

平均碰撞总时隙数等于所有βLi/m之和，即

（10）

空闲时隙为

（11）

根据IAMSA算法的工作流程，当子节点上的平均标签数为3时，使用二叉树进行搜索，即原四叉树的最后一层的搜索改用二叉树，那么四叉树中的碰撞时隙数与空闲时隙数就不包含最后一层里可能出现的碰撞与空闲时隙数。

， （12）

其中，

（13）

那么，使用IAMSA算法成功地识别m个标签所需的总时隙数

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

总时隙数随标签总数的变化情况，随着标签总数的增加，IAMSA算法所需的时隙数增加是最慢的，并且当标签总数达到1000时，与IAMSA算法相比，无空闲时隙4叉树算法需要的时间是其1.47倍，AMSA算法需要的时间是其1.17倍。由于IAMSA算法需要的时隙数最少，那么其识别标签的速率也是最快的。此外，AMSA算法与IAMSA算法的仿真曲线是跳跃式的。这是因为AMSA算法与IAMSA算法都能够自适应地调整搜索叉数，根据公式（14）可知，T（m）的值跟搜索深度 有关，由于k是非负整数（当m≤11时，k=0；当12≤m≤47时，k=1；当48≤m≤191时，k=2；……），那么 的值也是非连续变化的整数，因此，AMSA算法与IAMSA算法的仿真曲线是跳跃式的。

参考文献

[1]丁治国，古今.自适应多叉树防碰撞算法研究[J].自动化学报，2010，36（2）：237-241.

作者单位

卡斯柯信号有限公司 上海市 200070endprint

摘 要

针对AMSA算法存在的不足，本文提出了IAMSA算法。并通过性能与仿真分析，验证了IAMSA算法能够有效地减少空闲时隙，提高检测速度。

【关键词】物联网 RFID 多叉树 防碰撞算法

1 引言

在RFID系统中，阅读器利用标签防碰撞算法来实现覆盖范围内的多个电子产品标签的读取。而基于树的防碰撞算法被广泛地采用。但是多数基于树的算法并没有充分利用碰撞信息，仅仅使用了前几位的信息。通常情况下，分支内标签数越多，碰撞的位数也将会越多，那么在总比特位中，碰撞位占的比例就越大。在识别的过程中，根据碰撞比例，如果能够自适应地选择使用几叉树，就能够提升算法的效率，减少系统用时。AMSA（Adaptive Multi-tree Search Anti-collision，自适应多叉树防碰撞）算法就是基于这一原则。

虽然AMSA算法根据根据碰撞因子u并不能推断出当前碰撞节点下有多少标签。为了解决这个问题，本文提出了一种改进的自适应多叉防碰撞（简称IAMSA）算法。

2 IAMSA算法

IAMSA算法的工作流程如下：（1）阅读器对查询前缀栈进行初始化即清空栈，并发送ε指令；（2）每个标签与此时阅读器发出的查询前缀相比较，只有相同的标签才作出响应；（3）如果此时作出响应的标签数为一时，则识别成功，转到第六步；如果此时没有标签响应，那么就不需要继续对该分支进行搜索，转到第六步；而如果有多个标签作出了响应，则发生碰撞；（4）阅读器计算碰撞因子u。如果u<0.75，使用二叉树，接着依据碰撞比特的首位信息，确定两个新的查询前缀；如果u≥0.75，使用四叉树，阅读器发送查询碰撞位最高两位前缀的指令，而标签则反馈一个含有碰撞位信息的四位码给阅读器，那么阅读器将根据反馈判断已存在于系统中的前缀；（5）新产生的前缀入栈，栈首前缀被取出并发给标签，接着转到第二步；（6）前缀堆栈如果不为空，栈首前缀被取出并发给标签，接着转到第二步，如果为空，识别过程结束。

3 性能分析

假设有m个待识别的标签，并且当搜索深度为k时，每个子节点上的平均标签数为3，那么，当搜索深度小于k时，使用无空闲时隙的四叉树，否则采用二叉树。k=。

假设从o到k层的四叉树都没有去除空闲时隙，可以得出

T4-ary= （1）

当采用二叉数进行搜索是，可以得出

T2-ary = （2）

虽然IAMSA算法使用了无空闲时隙的四叉树，但是当碰撞被阅读器检测到后，其第二次发送指令仍然需要占用一个时隙，而这个指令所使用的时隙数Tcomm与碰撞时隙数T4-coll相等。

下面，将分别计算四叉树中的碰撞时隙T4-coll与空闲时隙T4-idle。

假设有m个待识别的标签，在四叉树的第l层的任意k个标签选中同一个节点响应的概率为：

（3）

其中，p=4-L，这是因为完全四叉树的第l层有个4L节点，所以选择任意一个节点的概率为4-L。

空闲概率为

（4）

成功识别概率为

（5）

碰撞概率为

（6）

令qLi/m表示第L层的第i个节点被搜索到的概率。当L=0时，根节点总是能被访问到，即q0i/m=q00/m=1。对于其它的节点，只有其父节点产生了碰撞，其才能被访问到，因此

qLi/m=qL/m= （7）

其中βLi/m表示第L层的第i个节点发生碰撞的概率。如果同层中的节点发生碰撞的概率是一样的，那么

（8）

而 等于所有的 之和，因此

（9）

平均碰撞总时隙数等于所有βLi/m之和，即

（10）

空闲时隙为

（11）

根据IAMSA算法的工作流程，当子节点上的平均标签数为3时，使用二叉树进行搜索，即原四叉树的最后一层的搜索改用二叉树，那么四叉树中的碰撞时隙数与空闲时隙数就不包含最后一层里可能出现的碰撞与空闲时隙数。

， （12）

其中，

（13）

那么，使用IAMSA算法成功地识别m个标签所需的总时隙数

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

总时隙数随标签总数的变化情况，随着标签总数的增加，IAMSA算法所需的时隙数增加是最慢的，并且当标签总数达到1000时，与IAMSA算法相比，无空闲时隙4叉树算法需要的时间是其1.47倍，AMSA算法需要的时间是其1.17倍。由于IAMSA算法需要的时隙数最少，那么其识别标签的速率也是最快的。此外，AMSA算法与IAMSA算法的仿真曲线是跳跃式的。这是因为AMSA算法与IAMSA算法都能够自适应地调整搜索叉数，根据公式（14）可知，T（m）的值跟搜索深度 有关，由于k是非负整数（当m≤11时，k=0；当12≤m≤47时，k=1；当48≤m≤191时，k=2；……），那么 的值也是非连续变化的整数，因此，AMSA算法与IAMSA算法的仿真曲线是跳跃式的。

参考文献

[1]丁治国，古今.自适应多叉树防碰撞算法研究[J].自动化学报，2010，36（2）：237-241.

作者单位

卡斯柯信号有限公司 上海市 200070endprint

摘 要

针对AMSA算法存在的不足，本文提出了IAMSA算法。并通过性能与仿真分析，验证了IAMSA算法能够有效地减少空闲时隙，提高检测速度。

【关键词】物联网 RFID 多叉树 防碰撞算法

1 引言

在RFID系统中，阅读器利用标签防碰撞算法来实现覆盖范围内的多个电子产品标签的读取。而基于树的防碰撞算法被广泛地采用。但是多数基于树的算法并没有充分利用碰撞信息，仅仅使用了前几位的信息。通常情况下，分支内标签数越多，碰撞的位数也将会越多，那么在总比特位中，碰撞位占的比例就越大。在识别的过程中，根据碰撞比例，如果能够自适应地选择使用几叉树，就能够提升算法的效率，减少系统用时。AMSA（Adaptive Multi-tree Search Anti-collision，自适应多叉树防碰撞）算法就是基于这一原则。

虽然AMSA算法根据根据碰撞因子u并不能推断出当前碰撞节点下有多少标签。为了解决这个问题，本文提出了一种改进的自适应多叉防碰撞（简称IAMSA）算法。

2 IAMSA算法

IAMSA算法的工作流程如下：（1）阅读器对查询前缀栈进行初始化即清空栈，并发送ε指令；（2）每个标签与此时阅读器发出的查询前缀相比较，只有相同的标签才作出响应；（3）如果此时作出响应的标签数为一时，则识别成功，转到第六步；如果此时没有标签响应，那么就不需要继续对该分支进行搜索，转到第六步；而如果有多个标签作出了响应，则发生碰撞；（4）阅读器计算碰撞因子u。如果u<0.75，使用二叉树，接着依据碰撞比特的首位信息，确定两个新的查询前缀；如果u≥0.75，使用四叉树，阅读器发送查询碰撞位最高两位前缀的指令，而标签则反馈一个含有碰撞位信息的四位码给阅读器，那么阅读器将根据反馈判断已存在于系统中的前缀；（5）新产生的前缀入栈，栈首前缀被取出并发给标签，接着转到第二步；（6）前缀堆栈如果不为空，栈首前缀被取出并发给标签，接着转到第二步，如果为空，识别过程结束。

3 性能分析

假设有m个待识别的标签，并且当搜索深度为k时，每个子节点上的平均标签数为3，那么，当搜索深度小于k时，使用无空闲时隙的四叉树，否则采用二叉树。k=。

假设从o到k层的四叉树都没有去除空闲时隙，可以得出

T4-ary= （1）

当采用二叉数进行搜索是，可以得出

T2-ary = （2）

虽然IAMSA算法使用了无空闲时隙的四叉树，但是当碰撞被阅读器检测到后，其第二次发送指令仍然需要占用一个时隙，而这个指令所使用的时隙数Tcomm与碰撞时隙数T4-coll相等。

下面，将分别计算四叉树中的碰撞时隙T4-coll与空闲时隙T4-idle。

假设有m个待识别的标签，在四叉树的第l层的任意k个标签选中同一个节点响应的概率为：

（3）

其中，p=4-L，这是因为完全四叉树的第l层有个4L节点，所以选择任意一个节点的概率为4-L。

空闲概率为

（4）

成功识别概率为

（5）

碰撞概率为

（6）

令qLi/m表示第L层的第i个节点被搜索到的概率。当L=0时，根节点总是能被访问到，即q0i/m=q00/m=1。对于其它的节点，只有其父节点产生了碰撞，其才能被访问到，因此

qLi/m=qL/m= （7）

其中βLi/m表示第L层的第i个节点发生碰撞的概率。如果同层中的节点发生碰撞的概率是一样的，那么

（8）

而 等于所有的 之和，因此

（9）

平均碰撞总时隙数等于所有βLi/m之和，即

（10）

空闲时隙为

（11）

根据IAMSA算法的工作流程，当子节点上的平均标签数为3时，使用二叉树进行搜索，即原四叉树的最后一层的搜索改用二叉树，那么四叉树中的碰撞时隙数与空闲时隙数就不包含最后一层里可能出现的碰撞与空闲时隙数。

， （12）

其中，

（13）

那么，使用IAMSA算法成功地识别m个标签所需的总时隙数

（14）

IAMSA算法的吞吐率

SIAMSA= （15）

4 仿真分析

总时隙数随标签总数的变化情况，随着标签总数的增加，IAMSA算法所需的时隙数增加是最慢的，并且当标签总数达到1000时，与IAMSA算法相比，无空闲时隙4叉树算法需要的时间是其1.47倍，AMSA算法需要的时间是其1.17倍。由于IAMSA算法需要的时隙数最少，那么其识别标签的速率也是最快的。此外，AMSA算法与IAMSA算法的仿真曲线是跳跃式的。这是因为AMSA算法与IAMSA算法都能够自适应地调整搜索叉数，根据公式（14）可知，T（m）的值跟搜索深度 有关，由于k是非负整数（当m≤11时，k=0；当12≤m≤47时，k=1；当48≤m≤191时，k=2；……），那么 的值也是非连续变化的整数，因此，AMSA算法与IAMSA算法的仿真曲线是跳跃式的。

参考文献

[1]丁治国，古今.自适应多叉树防碰撞算法研究[J].自动化学报，2010，36（2）：237-241.

作者单位

卡斯柯信号有限公司 上海市 200070endprint