国内防碰撞算法研究调研：优化方案

1.标签防碰撞方面

我国也有不少学者对RFID标签碰撞问题进行了相关的研究，对一些系统防碰撞算法作了原理阐述并完成了算法的实现。

北京航空航天大学的赵曦等针对特定场合提出了先到先服务（FCFS）的算法，并将该算法的基本思想分别放入TYPE B和TYPE C两个协议内实现，使得该算法具有理论和现实意义。刘佳提出的基于时隙的RFID防碰撞算法（SR）的最大特点是能使标签在一个识别周期内（而不是在一个识别周期后），随时更改时隙数。随着标签数量的增加，该算法虽然能保持稳定的系统效率，但效率不是很高。

北京邮电大学沈宇超的随机推迟算法，张明的标签随机分群及群间随机避让算法，浙江大学吴春华的动态ALOHA算法等都属于纯ALOHA算法，存在“部分碰撞”的问题，导致系统效率较低，理论最大值约为18.4%。复旦大学的胡建赞把SA算法的时间离散化，数据在这些离散的时间间隔里传送，解决了“部分碰撞”的问题，使系统效率提高了一倍，达到了36.8%。

帧时隙ALOHA（FSA）算法解决了在一段时间内可能出现的标签应答不均的问题，使每个标签在一个帧周期内都可以响应一次。北京航空航天大学的吴晶提出的利用动态时间槽分配的多目标防冲突识别算法和华中科技大学的程文青提出的改进的动态帧时隙ALOHA（DFSA）算法，都是在FSA算法基础上的改进。它们可以动态的调整帧的长度，以适应标签数量的变化。因此，可以解决RFID系统效率因标签数量急剧增加而大幅下降的问题。北京邮电大学的王晓华提出了一种基于序列号对时隙运算的排序算法，但该算法存在两个主要问题：一是算法要求标签根据其序列号对时隙进行运算，并且要求标签能统计其自身的发送顺序，这无疑将增加标签的计算量；二是规定争用周期的时隙数M要满M≥2^L（其中L为标签ID长度），如果标签ID长度为16，甚至为64或96时，M的值将非常巨大，算法很难实现。

广东工业大学的余松森提出了一种新颖稳定的算法，就是通过动态改变标签应答概率的方法来改善RFID的多标签识别性能，使系统效率在标签增加时能稳定保持在2.2%附近，但这个值相对较低。广东工业大学的林伟勇在DFSA算法的基础上，提出了一种结合倍乘因子和分组思想的改进算法，该算法通过判断系统效率的大小以及比较空闲时隙数量和碰撞时隙数量的多少，决定是否采用倍乘因子动态调整帧长度，当标签数量超过一定量时，采用分组识别的方法。据称，在标签数量急剧增加的情况下，该算法的效率也能稳定的保持在35%以上。其提出的分组动态ID预测算法能提高系统的有效服务率，降低系统的通信量。

东南大学的梁彪提出了一种基于码分多址思想的时隙ALOHA（CS-ALOHA）算法，并得出结论：当选用的扩频码组阶数为N时，算法的最大吞吐量可达原时隙ALOHA的N倍。然而考虑到CDMA协议的复杂性，对多数无源低成本RFID标签来说，该算法应用起来可能会有一定难度。

2.读写器防碰撞方面

华中师范大学的徐雪慧提出了一种自适应图着色算法，该算法在CSMA协议的基础上，结合图论中的图着色方法，提出了自适应的图着色算法来解决RFID系统中读写器的冲突。该算法采用分布式的图着色方法给读写器分配通信时隙，并在读写器与标签进行通信时，读写器周期性地在独立的控制信道上广播读写器当前时隙和网络所用总时隙数，还通过统计通信成功率动态地调整所使用的时隙数。该算法可以减少读写器冲突，优化通信时隙数，提高系统效率，增加系统阅读速率。该算法还适用于静态和移动的读写器网络。(www.xing528.com)

北京航空航天大学的杜万针对读写器到读写器的干扰和读写器到标签的干扰进行了数学建模分析，找到了影响这两个干扰的主要因素。他主张运用图形着色理论来解决时间和频率分配的问题，从而消除读写器之间的干扰。针对RFID系统的特点，他还提出了一种新的图形着色方法，该方法更适合于T-coloring的情况。

此外，上海交通大学的张闽军等提出了分时与色波相结合的算法。分时算法不要求读写器采用多套接收机，也不要求标签采用更为复杂的电路，相对于频分复用和码分复用的成本更低。色波算法可以灵活有效地适应各种读写器拓扑网络。分时与色波相结合的算法能较好地降低网络的重传指数。

天津大学的白煜等提出了基于神经网络图着色的算法。该算法把问题映射成神经网络问题，利用神经网络良好的非线性逼近能力来解决图着色的NP-完全问题。

广东工业大学的旷金华等提出了PLUSE的改进算法。在原来算法的基础上，通过增加控制命令来降低读写器在控制通道里的碰撞概率。与CSMA相比，它不仅可以降低读写器冲突，提高读写器阅读速率，而且实现起来简单，需要的读写器费用也较少。

中科院沈阳自动化所Jinghe Tian等提出了基于热处理（annealing）策略的嘈杂神经网络算法（RAC-ACNN）。该算法给有可能碰撞的两个读写器安排两个时隙，具有随机搜索遍历能力。此外，它还可以通过退出策略退出嘈杂状态，具有较高的速率和成功率。

复旦大学Liu Dan等提出了一种基于图着色的算法（TFDMA）。该算法融合时分和频分的优点，通过图着色解决标签干扰和频率干扰，从而提高系统吞吐率和系统效率。

北京大学的Dong Wang等提出了中心合作（Central Cooperator）CC-RFID算法。该算法通过在RFID网络中的相邻读写器之间共享标签信息，来减少读写器碰撞率。该算法能够显著改善读写速率和效率。

Shijie Zhou等提出了协同对等网络的RFID读写器碰撞模型（IRCD）。该模型适用于密集读写器环境，在读写器之间直接交换相关碰撞信息，而不用控制或者仲裁，拓宽了防碰撞算法的研究思路。