论文部分内容阅读
【摘 要】对物联网关键技术之一的射频识别技术RFID的防碰撞算法进行了研究和分析，并在已有随机算法的基础上加以改进，提出了一种改进的动态帧时隙ALOHA算法，从而大大减少了RFID的标签碰撞，适用于物联网应用背景下大量标签的识别和海量数据的处理，具有实际意义和工程价值。
【关键词】物联网；RFID；防碰撞算法
1.物联网及其关键技术
物联网（Internet of Things，IoT）是通过各种信息传感设备，如射频识别RFID装置、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，将任何物品与互联网相连接起来形成的一个巨大的网络。进而可以进行信息交换和通讯，以实现智能化识别、定位、追踪、监控和管理。
“物联网”这个概念最早于1999年由麻省理工学院Auto-ID研究中心提出，2005年国际电信联盟在突尼斯举行的信息社会世界峰会上正式确定了“物联网”的概念。
物联网实施、应用、研究與发展中涉及的关键技术主要在感知层、网络层和应用层中，其中感知层的主要关键技术有射频识别（RFID）技术、传感器技术、智能嵌入式技术和纳米技术。本文主要对物联网关键技术之一的RFID防碰撞算法进行研究和分析。
2.RFID技术及应用
RFID是从二十世纪九十年代兴起的一项非接触式自动识别技术，利用无线射频方式在阅读器和标签之间进行非接触双向数据传输，以达到自动识别目标对象和数据交换的目的。与传统的识别方式相比，RFID技术无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处理，具有操作方便快捷、存储数据量大、保密性好、反应时间短等优点。现已广泛应用于物流系统、医疗管理、煤炭安全管理、城市公共设施管理、农产品管理、供应链管理等领域，成为当前研究的热点技术之一。
RFID系统包括阅读器、电子标签和后台数据处理软件。电子标签放置在被识别的对象上，由芯片和天线组成，每个标签具有唯一的电子编码，通常电子标签处于休眠状态，一旦进入到阅读器的作用范围之内就会被激活，并与阅读器进行无线射频方式的非接触式双向数据通信。阅读器的主要任务是在作用范围内，以无接触的方式将电子标签信息读取出来，并将标签的相关信息传输到数据管理和处理系统进行处理，从而达到识别的目的。
3.RFID防碰撞算法
当RFID系统工作时，如果有多个电子标签同时处于同一个阅读器作用范围内，同一时刻有两个或多个电子标签向阅读器发送数据时就会产生信号干扰，出现信道争用即发生标签碰撞，从而使电子标签无法将信息正确地发送给阅读器。所以，需要采用适当的技术避免或减少碰撞的发生。
从多个电子标签到一个阅读器的通信称为多路存取，在无线电技术中，解决多路存取目前常用的方法有四种，包括空分多路法（SDMA）、频分多路法（FDMA ）、时分多路法（TDMA）和码分多路法（CDMA），在RFID系统中使用最广泛的是TDMA法。TDMA是把整个可供使用的通路容量按时间分配给多个用户的技术，基于TDMA的标签防碰撞算法大致可分为两类：基于ALOHA协议的随机算法和基于二进制搜索树的确定算法。
3.1 ALOHA算法
ALOHA算法是一种信号随机接入的方法，采用电子标签控制方式，即电子标签一进入阅读器作用范围内，就自动向阅读器发送自身的序列号，随即与阅读器开始通信。在一个电子标签发送数据的过程中，如果其他电子标签也在发送数据即发生碰撞。阅读器一旦检测到碰撞，就会发生命令让其中一个标签暂停发送，随机等待一段时间后再重新发送。这种方法简单但不适用于标签数量多的场合，该算法的效率很低，理论最大的吞吐率为18.4%。
为了提高ALOHA算法的吞吐率，研究了改进的时隙ALOHA算法。在该算法中，时间被分成若干离散时隙，要求标签随机选择其中一个时隙，在时隙的分界处发送数据。实现防碰撞的过程为：在每次清点过程开始时，阅读器通知所有标签一个可选时隙的范围，标签从中随机选择一个时隙回复，标签或成功发送或完全碰撞，若发生碰撞则重新选择时隙并发送，直至所有标签全部成功发送。时隙ALOHA算法的吞吐率可达到36.8%。
3.2 二进制搜索算法
二进制搜索算法也叫二叉树法，其基本思想是将处于碰撞的标签分裂成左右两个子集0和1，先查询子集0，若没有冲突，则正确识别标签，若仍有冲突则再分裂，把子集0分为00和01两个子集，依次类推，直到识别出子集0中的所有标签，再按此步骤查询子集1。实现防碰撞的过程为：阅读器不断地将标签二分裂，直到最左边分支上的标签为1个或0个，此时阅读器唯一清点左分支的标签，完成之后按照前面的过程依次清点后续分支上的标签，如此循环，直到所有的标签清点完成。
与ALOHA算法相比，二进制搜索算法识别率较高，但算法实现的延时长，泄露的信息较多，安全性差。
3.3 改进的动态帧时隙ALOHA算法
对于帧长固定的ALOHA算法，时隙过多会增加阅读时间，时隙过少会使碰撞冲突严重，效率下降。为此，本文提出了一种改进的动态帧时隙ALOHA算法。动态帧时隙ALOHA算法是基于帧时隙ALOHA算法的，根据需要动态地调整帧长。由于阅读范围内的标签数量是未知的，而且在识别过程中未被识别的标签数目是改变的，因此怎样估算标签数量、合理地调整帧长度成为动态帧时隙ALOHA算法的关键。
改进后的动态帧时隙ALOHA算法的基本思想是RFID阅读器以某个初始的帧 长（固定的）发送请求命令，根据正确识别的帧长和标签数或系统碰撞率和碰撞时隙数分别估算出现场标签数或未识别标签数，如果出现了未识别的标签数，需要相应地调整帧长。若系统吞吐率达到最大值时，而未识别标签数小于此数值时，则相应地减少帧长，若大于此数值则相应地增加帧长。如果在识别范围内，未能识别的标签数量远远大于系统设计的数据量时，用分组的方法把未识别的标签分成多个子集，系统再用同样的方法在各组中读取标签。在每一个读取周期里，阅读器都估计现场的未识别标签数与调整帧长，以保证系统能以最大的吞吐率进行工作 。
经仿真验证，改进后的帧时隙ALOHA算法能较好地解决数据碰撞问题，使其 在标签数目较大时发挥优势。
4.总结
本文主要针对物联网中RFID的标签防碰撞算法进行了研究和分析，并提出了改进算法。改进的动态时隙ALOHA算法相对于固定帧时隙的ALOHA算法做了一定的改进和调整，但缺乏相关理论依据，还有待于今后进一步的研究。此外，RFID中阅读器碰撞算法也有待进行研究和学习。
参考文献：
[1] 陈大才.射频识别技术（第2版）[M].北京：清华大学出版社，2000.
[2] 王保云.物联网技术 研究综述[J].电子测量与仪器学报，2009，23（12）：1-7.
[3] 沈宇超，沈树群等.射频识别系统中防碰撞算法设计[J].电子科学学刊，1999，21（5）702-705.
[4] 王闯等.RFID防碰撞算法研究[J].微处理机，2009，6：：4-50.
【关键词】物联网；RFID；防碰撞算法
1.物联网及其关键技术
物联网（Internet of Things，IoT）是通过各种信息传感设备，如射频识别RFID装置、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，将任何物品与互联网相连接起来形成的一个巨大的网络。进而可以进行信息交换和通讯，以实现智能化识别、定位、追踪、监控和管理。
“物联网”这个概念最早于1999年由麻省理工学院Auto-ID研究中心提出，2005年国际电信联盟在突尼斯举行的信息社会世界峰会上正式确定了“物联网”的概念。
物联网实施、应用、研究與发展中涉及的关键技术主要在感知层、网络层和应用层中，其中感知层的主要关键技术有射频识别（RFID）技术、传感器技术、智能嵌入式技术和纳米技术。本文主要对物联网关键技术之一的RFID防碰撞算法进行研究和分析。
2.RFID技术及应用
RFID是从二十世纪九十年代兴起的一项非接触式自动识别技术，利用无线射频方式在阅读器和标签之间进行非接触双向数据传输，以达到自动识别目标对象和数据交换的目的。与传统的识别方式相比，RFID技术无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处理，具有操作方便快捷、存储数据量大、保密性好、反应时间短等优点。现已广泛应用于物流系统、医疗管理、煤炭安全管理、城市公共设施管理、农产品管理、供应链管理等领域，成为当前研究的热点技术之一。
RFID系统包括阅读器、电子标签和后台数据处理软件。电子标签放置在被识别的对象上，由芯片和天线组成，每个标签具有唯一的电子编码，通常电子标签处于休眠状态，一旦进入到阅读器的作用范围之内就会被激活，并与阅读器进行无线射频方式的非接触式双向数据通信。阅读器的主要任务是在作用范围内，以无接触的方式将电子标签信息读取出来，并将标签的相关信息传输到数据管理和处理系统进行处理，从而达到识别的目的。
3.RFID防碰撞算法
当RFID系统工作时，如果有多个电子标签同时处于同一个阅读器作用范围内，同一时刻有两个或多个电子标签向阅读器发送数据时就会产生信号干扰，出现信道争用即发生标签碰撞，从而使电子标签无法将信息正确地发送给阅读器。所以，需要采用适当的技术避免或减少碰撞的发生。
从多个电子标签到一个阅读器的通信称为多路存取，在无线电技术中，解决多路存取目前常用的方法有四种，包括空分多路法（SDMA）、频分多路法（FDMA ）、时分多路法（TDMA）和码分多路法（CDMA），在RFID系统中使用最广泛的是TDMA法。TDMA是把整个可供使用的通路容量按时间分配给多个用户的技术，基于TDMA的标签防碰撞算法大致可分为两类：基于ALOHA协议的随机算法和基于二进制搜索树的确定算法。
3.1 ALOHA算法
ALOHA算法是一种信号随机接入的方法，采用电子标签控制方式，即电子标签一进入阅读器作用范围内，就自动向阅读器发送自身的序列号，随即与阅读器开始通信。在一个电子标签发送数据的过程中，如果其他电子标签也在发送数据即发生碰撞。阅读器一旦检测到碰撞，就会发生命令让其中一个标签暂停发送，随机等待一段时间后再重新发送。这种方法简单但不适用于标签数量多的场合，该算法的效率很低，理论最大的吞吐率为18.4%。
为了提高ALOHA算法的吞吐率，研究了改进的时隙ALOHA算法。在该算法中，时间被分成若干离散时隙，要求标签随机选择其中一个时隙，在时隙的分界处发送数据。实现防碰撞的过程为：在每次清点过程开始时，阅读器通知所有标签一个可选时隙的范围，标签从中随机选择一个时隙回复，标签或成功发送或完全碰撞，若发生碰撞则重新选择时隙并发送，直至所有标签全部成功发送。时隙ALOHA算法的吞吐率可达到36.8%。
3.2 二进制搜索算法
二进制搜索算法也叫二叉树法，其基本思想是将处于碰撞的标签分裂成左右两个子集0和1，先查询子集0，若没有冲突，则正确识别标签，若仍有冲突则再分裂，把子集0分为00和01两个子集，依次类推，直到识别出子集0中的所有标签，再按此步骤查询子集1。实现防碰撞的过程为：阅读器不断地将标签二分裂，直到最左边分支上的标签为1个或0个，此时阅读器唯一清点左分支的标签，完成之后按照前面的过程依次清点后续分支上的标签，如此循环，直到所有的标签清点完成。
与ALOHA算法相比，二进制搜索算法识别率较高，但算法实现的延时长，泄露的信息较多，安全性差。
3.3 改进的动态帧时隙ALOHA算法
对于帧长固定的ALOHA算法，时隙过多会增加阅读时间，时隙过少会使碰撞冲突严重，效率下降。为此，本文提出了一种改进的动态帧时隙ALOHA算法。动态帧时隙ALOHA算法是基于帧时隙ALOHA算法的，根据需要动态地调整帧长。由于阅读范围内的标签数量是未知的，而且在识别过程中未被识别的标签数目是改变的，因此怎样估算标签数量、合理地调整帧长度成为动态帧时隙ALOHA算法的关键。
改进后的动态帧时隙ALOHA算法的基本思想是RFID阅读器以某个初始的帧 长（固定的）发送请求命令，根据正确识别的帧长和标签数或系统碰撞率和碰撞时隙数分别估算出现场标签数或未识别标签数，如果出现了未识别的标签数，需要相应地调整帧长。若系统吞吐率达到最大值时，而未识别标签数小于此数值时，则相应地减少帧长，若大于此数值则相应地增加帧长。如果在识别范围内，未能识别的标签数量远远大于系统设计的数据量时，用分组的方法把未识别的标签分成多个子集，系统再用同样的方法在各组中读取标签。在每一个读取周期里，阅读器都估计现场的未识别标签数与调整帧长，以保证系统能以最大的吞吐率进行工作 。
经仿真验证，改进后的帧时隙ALOHA算法能较好地解决数据碰撞问题，使其 在标签数目较大时发挥优势。
4.总结
本文主要针对物联网中RFID的标签防碰撞算法进行了研究和分析，并提出了改进算法。改进的动态时隙ALOHA算法相对于固定帧时隙的ALOHA算法做了一定的改进和调整，但缺乏相关理论依据，还有待于今后进一步的研究。此外，RFID中阅读器碰撞算法也有待进行研究和学习。
参考文献：
[1] 陈大才.射频识别技术（第2版）[M].北京：清华大学出版社，2000.
[2] 王保云.物联网技术 研究综述[J].电子测量与仪器学报，2009，23（12）：1-7.
[3] 沈宇超，沈树群等.射频识别系统中防碰撞算法设计[J].电子科学学刊，1999，21（5）702-705.
[4] 王闯等.RFID防碰撞算法研究[J].微处理机，2009，6：：4-50.