采用分集技术的改进型二进制搜索算法的研究

沈 虹

哈尔滨铁道职业技术学院，黑龙江 哈尔滨 150081

1 问题的提出与改进思路

现在RFID技术已经在很多领域得到了广泛的应用，但是在某些场合电子标签的分布很过于密集，如果采用应用比较的二进制搜索算法，算法的搜索次数多，传输时延大。这主要因为在电子标签的数量多或位数长，发生碰撞的电子标签数量和比特位数增加，因此，在二进制搜索算法的基础上提出分集的二进制搜索算法。即把电子标签分成若干个集，每个集里面的电子标签都可以被阅读器单独地识别出来，各个集互不影响，电子标签之间发生碰撞的次数就会减少。由阅读器发射的信号到达电子标签的功率密度S和阅读器与电子标签间的距离R表示为：

其中P代表阅读器的发射功率，λ代表信号的波长，σ代表散射的横截面积，G代表天线的增益，Pback代表阅读器接收的从电子标签所发射的信号的功率。

由公式1、2可知，可以通过调节阅读器的发射信号的功率和发射天线的增益方式来改变阅读器和电子标签之间的距离。

如图1所示，为这种分集思想的一个例子，阅读器工作区域被分为三个集：d，d1，d2。首先，阅读器调节天线使集d内的所有电子标签运行改进的二进制搜索算法，当集d内的所有电子标签都被识别出来后，阅读器调节天线使作用范围扩大到集d1，当集d1内的所有电子标签被识别出来后，再识别集d2中的电子标签。各集间是互相独立、互不干扰的，在各集内运用的是改进的二进制搜索算法。阅读器对集的处理的次序是由近及远，不存在交集，因此避免了集间的冲突。

图1 电子标签分集示意图

2 改进的二进制搜索算法的描述

首先我们来介绍几个命令：

在改进的二进制搜索算法中用到一个REQUEST（EPC，NULL）命令，该命令的含义是：在阅读器发送REQUEST（11…11）命令后，根据译码结果发送REQUEST（EPC，NULL）命令，电子标签只锁位不回送EPC。

SELECT（EPC）：选择（序列号）命令，用于事先被确定的序列号作为参数传送给电子标签，也就是选中了这个电子标签。

READ-DATA：数据读取命令，将被选中的电子标签中的数据传送给阅读器。

UNSELECT：取消命令，取消事先已选中的电子标签，使其进入“静默”状态。处于该状态下的电子标签是非激活的，对接收到的REQUEST命令不作应答。

算法的工作过程如下：

1）阅读器发送REQUEST（11…11）命令，所有EPC值小于或者等于（11…11）的电子标签作出响应，然后所有电子标签将自己的EPC码发送出去；

2）阅读器根据接收到的信号进行判断，如果为空，表示阅读器附近不存在电子标签，则转到步骤1，否则转到步骤3；

3）阅读器对所有电子标签作出的响应信号进行译码，根据译码结果判断碰撞是否发生及碰撞发生的位置。如果没有发生碰撞，阅读器发送SELECT和READ-DATA命令，对标签进行读写操作之后，阅读器发出UNSELECT命令，使该电子标签进入静默状态。发送如果有碰撞，则转到步骤4；

4）阅读器将这几个碰撞的比特的值置为1，未发生碰撞的比特位置0，接着阅读器发送REQUEST（EPC，NULL）命令，所有电子标签均对此命令作出响应，然后将自身的EPC与阅读器发出的序列号进行比较，与阅读器发出的EPC位中1对应的数据位进行锁定，在接下来各集内的防碰撞处理中，参与数据发送和比较的仅仅是被锁定的数据；

5）阅读器根据电子标签的数量来确定集的数量，集的数量的取值范围在[1，n]之间，根据实际情况来确定具体的取值；

6）阅读器调节天线工作距离，由近及远在各个集内执行改进的二进制搜索算法。当所有的电子标签都被识别出来后跳转到步骤7；

7）识别过程结束。

3 采用分集技术的二进制搜索算法的性能分析

3.1 阅读器搜索次数分析

在采用分集技术的二进制搜索算法中，如果阅读器作用范围内有n个标签，并且阅读器的作用范围被分为n个具有相同大小的集，则采用分集技术的二进制搜索算法来识别m个电子标签需要的搜索次数为：

S代表空集的数目，即集内没有电子标签的数量。

证明：如果空集的数量为s，则非空集的数目为n-s，假设ni代表第i个非空集内的电子标签的个数，则第i个非空集内执行改进的二进制搜索算法的搜索次数为S（m，i）=2mi-1，则在所有非空集内运行改进的二进制算法所需要的搜索次数为：

因为第一次阅读器发出REQUEST（11…11）命令和REQUEST（EPC，NULL）命令，所以得到识别m个电子标签需要的搜索次数为：

选取集的数量是否合适对本算法的性能有着重大的影响，对于选取集的数目，有下面的结论：

如果m个电子标签的EPC是均匀分布的，那么理想的集的数量n的最优取值在区间[1，m]内。

3.2 传输时延分析

如果在阅读器的工作区域存在m个电子标签。再将这m个电子标签分为n个集，则可以得到：

1.第t（1 ≤t≤m）个集为空集的概率为：

2.第t个集仅存在1个电子标签的概率为：

3.第t个集内电子标签数量为i的概率为：

空集内传输的总数据为x+10，只有一个电子标签的集内传输的总数据为2 x+23，电子标签个数超过1的集内传输的总数据为3x-2xi-21+（2xi+44）mi，另外阅读器开始有一次搜索需要传输的数据量为2k+21，其中为k代表电子标签EPC的长度，由此可以得到：

1）所有空集传输的数据长度为：

2）电子标签数量为1的传输的数据长度为：

3）电子标签个数为i的传输的数据长度为：

这里xh代表第h个电子标签个数为i的集发生碰撞的数据长度。

由式（9）、（10）、（11）可以得到，分集的二进制搜索算法传输这些数据的时延为：

其中v代表数据传输速率。

4 结论

本文详细研究了分集的二进制搜索算法，主要适用于在电子标签分布密集的场合下。分集的二进制搜索算法是在二进制搜索算法的基础上进行分集处理，将电子标签分成若干个集，在各个集内继续运行改进的二进制算法，同时，对阅读器的搜索次数、传输时延两个重要的性能指标对分集的二进制搜索算法的性能进行了分析，分析表明：在电子标签密集分布的情况下，分集的二进制算法优越于二进制搜索算法，当然更优越于动态二进制搜索算法和返回式二进制搜索算法。

[1]刘冬生，邹雪城，泳生，李孝煌，等.射频识别系统中的防碰撞算法[J].华中科技：大然科学版，2006，34(9).

[2]刘舒棋，牟志刚，等.非接触式R助的读写器系统设计[J].单片机与嵌入式系统.

[3]陈冬萍.射频识别技术(RFID)应用研究[D].华中师范大学硕士毕业论文，2006.

[4]王洪菊.RFID的系统设计与碰撞算法研究[D].西北工业大学硕士毕业论文，2007.

[5]金允霖.主动式RFID在集装箱应用中关键技术的研究和设计[D].上海交通大学，2007.