RFID读写器防冲突问题的混沌神经网络建模与求解

0 引言  

　　无线射频识别(radio frequency identification，RFID)系统中读写器和标签通信具有空间受限的特性。在某些RFID系统应用中，需要RFID读写器能在一个大的范围内的任何地方都能阅读标签，因此必须在整个范围内配置很多读写器。RFID系统的不断增多增加了读写器冲突的概率。随着RFID应用的不断增长，人们逐渐对RFID读写器冲突的问题重视起来，并做了一些研究。Daniel及Engels等最早提出了RFID读写器冲突问题，他们指出，读写器冲突是一种类似于简单图着色的问题。随后WMdmp和Engels等提出了一种读写器防冲突算法Colorwave 。Colorwave是一种基于时分多址(TD．MA)原理的分布式防冲突算法，当网络中的读写器数量比较小时该方法是有效的和可行的。欧洲电信 标准协会(ETSI)发布的EN 302 208标准采用一种 基于载波侦听多路访问(carrier sense multi．access，CSMA)原理的先侦听后发言的方法(1isten before talk，LBT )来减少读写器冲突的情况。该方法尽管实现简单，但是可能导致某些读写器长时间无法获得信道。EPC Class I Gen2标准阐述了采用频分多址(FDMA)原理来避免读写器冲突的算法。但是由于大部分的标签不具备频率分辨能力，因此在该标准中仍然存在读写器冲突的情况。互联RFID读写器冲突模型(interconnected RFID reader collision model，IRCM)是一种基于P2P结构的无需中央服务器参与的读写器信息交互模型。读写器之间通过协商和调整读取速度、读取时间等参数来减少冲突发生的概率。尽管不需要中央服务器，但是IRCM使得读写器经常陷于互相交互与协商的过程，显然会大大减少读写器的标签扫描时间和工作效率。 
  
　　针对上述情况，本文提出了通过中央服务器集中控制读写器分时隙操作来实现避免读写器冲突的方法，并建立了一种基于模拟退火策略的混沌神经网络进行读写器时隙分配问题求解的模型。这是一种基于TDMA原理的集中控制式防冲突方法，可以根据读写器冲突关系的变化在线进行读写器的时隙分配求解与控制，在不影响读写器工作效率的同时，旨在消除密集读写器环境下的读写器冲突问题。 
  
1 RFID读写器冲突及解决途径  

1．1 密集读写器环境中的读写器冲突  

　　密集读写器环境就是指在RFID系统应用中，在预定区域内部署多个RFID读写器，以满足对区域内的所有标签进行完全的高可靠的读取。读写器网络的拓扑结构通常如图1所示。网络中包含多个读写器和一个中央计算机，读写器与中央计算机之间一般采用局域网(LAN)或无线局域网(WLAN)方式进行通讯连接。网络中每个读写器通常具有不同范围的识读区域，各读写器的识读区域可能有交集，即识读区域有相互重叠的部分。为了便于说明，用图2近似地描绘了密集读写器环境下的读写器冲突。每个圆圈代表一个读写器的识读区域(实际应用中识读区域可能为不规则形状)，圆点代表相应的读写器。如果两个读写器的识读区域有相互重叠，如图2中的R1和R2，则当R1、R2同时工作时，如果不采取防冲突措施，就会产生读写器冲突，甚至使整个RFID系统无法正常工作。 

1．2 分时传输解决读写器冲突  

　　标签通过电磁耦合的方式从读写器获得能量，由于获得的能量非常有限，无源标签只具备简单的功能而不具备区分不同频率信号的能力，所以RFID读写器的防冲突无法通过FDMA来实现，而只能靠TDMA的方法解决。因此可以将读写器的防冲突看成读写器时隙分配问题。  

　　时隙分配可能的实现方法可分为分布式时隙控制与集中式时隙控制两种。第一种方法以防冲突算  
法Colorwave和IRCM为代表，时隙分配过程以网络中的每个读写器为中心，各读写器之间相互反复通讯协商来确定各自的工作时隙，发生冲突时往往通过增加新的时隙来解决，结果是时隙分配过程较长且需要的总时隙数目多；集中式时隙控制方法几乎不占用读写器的资源，通过中央计算机或服务器运行优化算法进行时隙分配问题的求解。这种方法求解速度快且不占用读写器资源。  

　　因此，本文采用集中式时隙控制的方法，根据读写器之间的冲突关系，由中央计算机执行时隙分配的优化算法。在得到时隙分配结果解后，中央计算机指定各个读写器在分配到的时隙内进行读写操作，从而消除读写器冲突情况。  

1．3 平面图着色与读写器防冲突  

　　文献[1,2]指出，RFID读写器冲突问题类似于一个简单的平面图G= (R，E)。顶点集合R是  RFID读写器集合，即R={r1，r2，﹍，r )。边集合E 描述了RFID系统中读写器之间的冲突关系。也就 是说，如果读写器Ri 和读写器Rj 的识读区域之间存在交集，我们就将顶点ri和rj用一个无向线段连接起来。据此建立图2中的读写器冲突问题的平面图G＝(R，E)(见图3)。

　　文献[8]已经证明了任意一个平面图均可用4种颜色来进行着色。因此，一个读写器网络的防冲突问题即类似于一个平面图的四色着色问题。因此，读写器防冲突问题可以看作读写器网络的四时隙分配问题。在本文中，采用基于退火策略的混沌神经网络模型来进行读写器四时隙分配问题的求解。 

2 读写器防冲突问题的混沌神经网络模型 

　　采用神经网络方法求解读写器网络防冲突问题前需要确定网络中读写器之间可能存在冲突的关系，即获得平面图G=(R，E)的边集E。本文采用文献[7]中的算法IRCD来获得读写器的冲突关系矩阵，关于IRCD这里不再详述。 

2．1 Hopfieid神经网络模型 

　　本文采用二维Hopfield神经网络(HNN)模型对读写器防冲突问题进行建模。 

　　首先，为了获得读写器防冲突神经网络的能量函数，需要建立一个二维Hopfield神经网络，构造一个n×4阶的矩阵 。其中，n为网络中的读写器的 数目，矩阵的每一行包括4个神经元，代表一种时隙，4个时隙 ， ， ， 分别表示为‘1000’，‘0100’，‘0010’，‘0001’。那么n个读写器的四时隙分配结果就可以由n×4个神经元表示出来。对于图3所示的读写器网络，矩阵

是一种可行的四时隙分配结果。 

　　设n×n阶对称矩阵d为读写器冲突关系矩阵，它描述网络中读写器之间是否存在的冲突，当读写器i和读写器． 之间具有冲突关系时，dij= 1，否则dij =0。对于图3所示的读写器网络，可以构造读写器冲突关系矩阵如下：

　　为了消除网络中的读写器冲突问题，必须使网络中存在冲突关系的读写器工作在不同的时隙。根据这样的约束要求，建立如下的读写器防冲突神经网络的能量函数：

　　其中，A， B，C是常数，n×n阶对称矩阵d为读写器冲突关系矩阵，矩阵v是神经网络的输出矩阵。在式(3)的能量函数中，第一项是行约束，在矩阵v的每一行的4个神经元当中，只有一个神经元的值为‘1’，其余3个神经元的值全部为0。也就是说，当每个读写器都分配了T1,T2,T3,T4,4个时隙中的任意一个的时候，该项的值为 
0。第二项是一个全局约束，它有助于神经网络收敛于有效解。即当神经网络收敛于有效解时，输出矩阵v中每行只有一个神经元的值为1，对n×4神经元矩阵v来说，所有值为‘1’的神经元的个数是n，这时式(3)中的第二项的值为0。最后一项为边界惩罚函数，只有当任意两个存在冲突关系的读写器被分配了不同的工作时隙的情况下，该项的值为0。因此，当神经网络的能量函数E的值等于‘0’时，当前的输出矩阵v的值就是读写器防冲突神经网络的可行解。

　　根据文献[9]中的二维Hopfield神经网络能量函数的一般表达形式：

　　其中，Vxi,yj 表示神经元Vxi 和Vyj 订之间的连接权重，厶 表示神经元％ 的外部输入偏差。比较式(3)和式(4)，可以得到：

　　因此，读写器防冲突神经网络的微分方程为：

　　其中f为神经元的输入输出函数，u为神经元的内部输入，t为时间常数。解这个微分方程组就可以得到读写器防冲突神经网络的有效解。根据输出矩阵 的每行各个元素的值就可以确定分配给每个读写器的时隙。 

2．2 基于退火策略的混沌神经网络模型 

　　Hopfield神经网络模型可以收敛到一个稳定的平衡解，但会经常陷入局部最优 。因此，在2．1节所建立的Hopfield神经网络模型基础上，本文通过引入混沌机制和模拟退火策略，为读写器防冲突建立基于退火策略的混沌神经网络模型如下：

　　其中Vxi，Uxi和Ixi 分别为神经元的输出、输入和外部输入偏差Vxi，yj 为神经元连接权重系统，Io是一个正的常数，a为比例系数，k是神经元的退火速度系数，z(t)自反馈权重系数， 是z(t)的衰减系数。式(12)中的z(t)(％ 一Io)项起自抑制反馈作用，从而为系统带来混沌状态。而混沌具有随机搜索的特质，因此可以避免算法陷入局部最优。同时为了有效地控制混沌行为，引入模拟温度z(t)，z(t) 在算法搜索过程中按照式(13)逐渐衰减，这样使神经网络经过一个倒分岔过程而逐渐趋于稳定的平衡点。当模拟温度衰减至趋近于‘0’时，混沌状态消失，此后算法获得一个较好的初值，并按照Hopfield神经网络算法继续进行搜索并逐渐收敛于有效解。

3 仿真实验 
3．1 仿真流程 
　　采用MATLAB对基于退火策略的混沌神经网络读写器时隙分配算法进行仿真。仿真流程如下：
 
　　步骤1：设置A，B，C，，0，￡，k，a，z(0)， ，／Z (0) 等参数的值，如表1。实验中， (0)取[0，1]区间 
的随机数。 
　　步骤2：根据式(10)和(11)计算 (t)。 
　　步骤3：根据式(3)计算能量函数 。 
　　步骤4：根据式(12)计算／Z (t+1)。 
　　步骤5：判断能量函数 是否满足稳定条件。如果满足进行步骤6，否则进行步骤2。能量函数的稳定判据为：1) 的值在连续l0次迭代中的变化量小于0．01；2)如果E≤10～，则停止迭代；3)如果算法在1000次迭代中无法收敛到有效解，则停止仿真。 
　　步骤6：输出仿真结果，即输出V and E。

3．2 仿真实验结果 

　　对于图2和图3所示的读写器冲突网络，用基于退火策略的混沌神经网络算法在经过162次迭代后，得到了读写器防冲突的时隙分配有效解。输出矩阵 的值为：

　　图4表示当参数卢=0．02时神经元 的演变过程。从图4中可以看出， 1逐渐地完成由混沌过程到稳定输出的转变过程，当混沌状态消失后，基于退火策略的混沌神经网络的动态响应就退化为普通的Hopfield神经网络。

　　根据 中的每行元素，得到各读写器的时隙分配结果如表2所示。

　　若以4种形状分别代表时隙 T1, T2, T3, T4,对图2所示的读写器网络按照表2的结果进行着色填充的结果如图5所示。

　　从图5中可以看出，任意两个识读区域存在交集的读写器(即存在冲突约束的读写器)的识读区域分别采用不同的填充方式，表明了求解结果的正确性。 尽管与式(1)的 的值不同，但仍然是读写器防冲突时隙分配问题的可行解。 

　　为了验证算法可靠性和效率，对不同的读写器网络规模(读写器数目)n=10，15，20，25，30进行了50次实验，所有的50次实验均得到了读写器防冲突问题的有效解。对于不同网络规模，算法求解的平均迭代次数分别为171次、236次、282次、314次及375次。实验结果表明了算法的可靠及高效。 

3．3 算法性能分析 

　　首先，基于退火策略的混沌神经网络读写器防冲突算法是基于TDMA原理的，因此运用该算法来解决读写器冲突问题原理上是可行的。 

　　其次，本算法属于集中式控制算法，算法的执行过程在中央计算机上实现，几乎不占用读写器的扫描时间(只在确定读写器之间冲突关系时占用极少的时间)。而分布式算法在执行的全过程中，所有的读写器要相互通讯来协调时隙分配，在时隙分配完成前无法扫描标签。因此，从应用的角度来说，本文提出的方法更具有合理性和实用性。

　　最后，在密集读写器环境中，Colorwave和IRCM算法大概需要10个时隙数量才能得到96％ 以上的传输成功率，而本文提出的新算法仅需4个时隙即可完成几乎100％的传输成功率(除去算法执行时间都可以成功传输)，显然本文提出的新算法使得每个读写器具有更大的标签吞吐能力。

4 结论

　　本文提出了一种读写器冲突问题的集中控制方法。该方法根据平面图着色理论，将密集读写器网络的读写器防冲突问题等效为读写器网络的四时隙分配问题，并建立了解决读写器冲突问题的神经网络模型，并引入了模拟退火策略及混沌思想对读写器防冲突神经网络模型进行求解，仿真实验结果表明该算法是可靠的、高效的。与现有的Colorwave和IRCM等分布式算法相比较，本文提出的方法可以保证RFID网络中的读写器具有更大的对标签的吞吐能力和实时响应能力。 

　　本文提出的RFID读写器防冲突方法是通过读写器分时隙操作实现的。因此，读写器网络的时间同步问题将是下一步研究工作的重点。此外，结合具体应用的业务流程特点，如何合理地确定时隙长度也是下一步研究的内容。

　　点击下载完整版本PDF文档：RFID读写器防冲突问题的混沌神经网络建模与求解.rar