（计算机应用技术专业论文）uhf+rfid防碰撞算法的研究.pdf

内蒙古科技大学硕士学位论文 论文题目：u h f 掣翌些碰撞算法的研究 作者：罗春青 指导教师： 协助指导教师： 李宝山教授 单位：笪垦王程笔堕 论文提交日期：2 0 1 0 年0 6 月l2 日 学位授予单位：内蒙古科技大学 单位： 单位： u h fr f i d 防碰撞算法的研究 s t u d i e so na n t i - c o l l i s i o na l g o r i t h m su s e di nu h fr f i d 研究生姓名：罗春青 指导教师姓名：李宝山 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e ：l u oc h u n - q i n g s u p e r v i s o r ：l ib a o - s h a n s c h o o lo f i n f o r m a t i o ne n g i n e e r i n g i n n e rm o n g o f i au n i v e r s i t yo f s c i e n c 宅a n dt e c h n o l o g y b a o t o u0 1 4 0 1 0 ，p r c h m i k ， l 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 签名：妥盔盔日期：丛应：么：! 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵循此规定) 签名：矍左查导师签名：纽日轴：近。 t 喜a 同步码 t i f- j 2 5 t i n s r l r c a l s3 0 t a 4 r t l 一 1 1 r t c a d 墨豫叫53 时酬 附。i 刚!“ 叫叫 卜 i 二 i 抛k 据一舡l t 舡t 校准僻t i 校准1 1 1 髓- l ， l 定界符 舡 t 蝴司步 一 1 - t i f f1 一 乞s t i f s r t c m l s3 0 t i f 1 2 ，5 雌+ 1 - s i p wp w 和- _ 刊 _ _ 一- 扣一 lr 1ll 定界符 l 数据- olm 校准( r t c * a ) 图2 1 5r 产 t 前同步码和帧同步 i s 0 i e c1 8 0 0 0 6 c 标准具有较高的读取速率，最高能达到1 5 0 0 标签秒，具 有更好的加密技术，提高了数据的安全性能，减轻了人们对隐私问题的担忧，提供 了更大的内存读写空间，可更好的满足多元化应用的需求。提供了更多的功能，可 适应在高密度多个识读器环境下工作，标签在晶片内加上了防碰撞机制，确保标签 在大量被读取时读取率的完整，提供了达成共识的一项通用标准，从而提高了读取 的准确性和数据的可靠性。允许用户对同一个标签进行多次读写( g e n1 允许多次识 读，但只能写一次) ，g e n 2 支持1 6 位到2 5 6 位的唯一物品识别码u i d ( 例如f p c ) ， 而g e n l 支持最多9 6 位的电子产品编码，i s 0 i e c1 8 0 0 0 - 6 a 和i s 0 i e c1 8 0 0 0 - 6 b 的唯一识别码u i d 均为6 4 b i t 。该标准吸收了其他r f i d 相关标准的最新成果，在射 频频段选择、调制方式及物理层数据编码技术、标签访问控制、防碰撞算法和隐私 保护等关键技术方面进行了改进，以适应标签低处理能力、低功耗和低成本的要 求，这使得i s 0 e c1 8 0 0 0 - 6 c ( g e n 2 ) 标准在性能上比第一代e p cr f i d 标准有了明 显提高【2 。 2 3 3 中国u 腰r f i d ( 试行) 规定 2 0 0 7 年我国信息产业部对u h fr f i d 发布了试行规定，规定中指出8 0 0 9 0 0 姗z 频 段r f i d 技术的具体使用频率为8 4 0 8 4 5 m h z 和9 2 0 9 2 5 m h z 。该频段r f i d 技术无 线电发射设备射频指标圈： ( 1 ) 载波频率容限：2 0 x1 0 e - 6 ； ( 2 ) 信道带宽及信道占用带宽( 9 9 能量) ：2 5 0 k h z ； ( 3 ) 信道中心频率：f c ( m h z ) = 8 4 0 1 2 5 + n 0 2 5 和f c ( m h z ) = 9 2 0 1 2 5 + m x 0 2 5 ( n 、m 为整数，取值为0 _ 1 9 ) ； 内蒙古科技大学硕士学位论文 ( 4 ) 邻道功率泄漏比：4 0 d b ( 第一邻道) ，6 0 d b ( 第二邻道) ； ( 5 ) 发射功率：2 w ( e i r p ) ； ( 6 ) 工作模式为跳频扩频方式，每跳频信道最大驻留时间2 秒； ( 7 ) 杂散发射限值( 在两频段的中间载波频率1 m h z 范围以外) ：天线端口、机箱端 口( 含一体化天线) ； ( 8 ) 电源端口和电信端口的传导骚扰发射应满足国标g b 9 2 5 4 - 1 9 9 8 中b 类设备的限 值要求； ( 9 ) 在制造商声明的极限工作电压、极限温度条件下，设备的发射功率和频率容限应 满足相应技术指标。 2 3 内蒙古科技大学硕士学位论文 3u h fr f i d 防碰撞算法 3 1 碰撞的产生与解决 当在读写器的天线作用范围内有多个标签时，面对读写器发出的指令，每个标签都会 响应，如果它们同时发送信号，信号互相干扰，就会产生信道冲突问题，这种现象被称为 碰撞问题。 r f i d 系统会采用一定的策略或算法来避免冲突现象的发生，控制标签的响应信息逐 个通过射频信道被读写器接收。为了防止这些冲突的产生，射频识别系统中通过设置相 关命令的方法来解决碰撞问题，这些方法称为防碰撞算法。 u h fr f i d 防碰撞算法的工作过程是这样的，读写器检测到其识别场内有标签时， 读写器先发送q u e r y 指令规定帧长( 时隙的个数) ，然后标签在帧长范围内随机选择一个 时隙反馈自己的i d 编码信息，发生碰撞的标签会在下一帧继续尝试。以i s 0 1 8 0 0 0 - 6 c 的 时隙a l o h a 算法为例，具体的防碰撞过程：读写器先发送q u e r y 指令规定帧的长度( 时 隙的个数) ，然后每个标签随机选择其中一个时隙来反馈一个随机数r n l 6 。读写器收到 r n l 6 后会发送包含r n l 6 的确认指令a c k 然后，标签比较接收到的a c k 指令和刚才发 送的r n l 6 是否相同；如果相同，就反馈标签编码e p c 码( 物品编码) ；反之则不反馈 e p c 耐1 8 】。大多数基于a l o h a 的防碰撞算法先根据前一帧的反馈值( 碰撞时隙数c ，空 时隙数b 和成功时隙数s ) 使用某一种标签估算方法来估算出待识别标签的数量n ，然后 据此选择一个合适的帧长度。现有理论认为帧长l 等于标签数量n 时，吞吐率( 成功时隙 数量占总时隙数量的比例) 最高四1 3 2 1 a l o h a 算法 a l o h a 算法是最简单最基本的一种防碰撞算法，它是基于t d m a 的思想，是一种基 于概率的算法。该算法是指标签在进入读写器的读取范围会随即向读写器发送其消息， 当读写器准确分辨出唯一的标签时与该标签开始通信，否则，读写器发送命令让标签等 待随机时间再向读写器发送消息在标签发送数据的过程中，若有其他标签也在发送数 据，那么发生信号重叠从而导致完全冲突或部分冲突【2 4 】。图3 1 为a l o h a 算法冲突形 式。 图3 1m o h a 算冲突形式 3 2 2 时隙a l o h a 算法 时隙a l o h a 算法是a l o h a 算法的改进算法。这种算法在a l o h a 算法的基础上把时间 分成多个离散时隙( s l o t ) ，并且每个时隙长度要大于标签回复的数据长度，标签只能 在每个时隙内发送数据。每个时隙存在下面3 种情况： ( 1 ) 无标签响应：在此时隙内没有标签发送； ( 2 ) 一个标签响应：在此时隙内只有一个标签发送，标签能够被正确识别； ( 3 ) 多个标签响应：在此时隙内多个标签发送，产生冲突。 标签1 标签2 标签3 标签4 共享通 时隙时隙 i i lii i ll i 广 i l i 三ll l l 1 l 量 l 道ll1 冲突 图3 2 时隙a l o h a 算法 3 2 3 帧时隙a l o h a 算法 帧时隙a l o h a 算法( f r a m e ds l o t t e da l o h a 算法，简称f s a 算法) ，它是在时隙 a l o h a 算法的基础上把n 个时隙组成一帧，每个时隙的长度要足够让一个标签回答完， 具体时间由读写器定义。在读写器发送读取命令后，要等待一定时间等待标签的回答。 内蒙古科技大学硕士学位论文 标签在每个帧内随机选择一个时隙发送数据，在一个时隙中只有一个标签回答时，读写 器可以分辨出标签；在一个时隙中没有标签回答时，跳过此时隙；当在一个时隙中有多 个标签回答时，发生冲突，需要重新开始读取过程。 这种算法适于传输信息量较大的场合，与时隙a l o h a 算法相同，f s a 算法也需要一 个同步开销。f s a 算法存在一个缺点，当标签数量远大于时隙个数时，读取标签的时间 将会大大增加，而在标签个数远小于时隙个数时，会造成时隙的浪费。 3 2 4 动态帧时隙a l o h a 算法 这是一种改进的f r a m es l o t t e da l o h a 算法，该算法中读写器能动态改变( 增加或 减少) 下一次阅读循环中每帧的时隙个数n ，这种算法称为动态f s a 算法，简称为d f s a 算法。一个帧内的时隙的数目n 能随阅读区域中的标签的数目而动态改变，或通过增加 时隙数以减少帧中的冲突数目，或若有很多空时隙就减小n 以节省时间。在动态f s a 算 法中，每帧中的时隙个数n 是动态产生的，因此解决了f s a 算法中时隙的浪费问题。标 签估计算法的好坏在一定程度上决定了动态帧时隙a l o h a 算法的性能。 3 2 5 基于分组的动态帧时隙a l o h a 算法 动态帧时隙a l o h a 算法的帧是由多个时隙组成的，但每一帧的时隙数是变化的，通 过上一帧识别的情况估计出未读的标签数，从而确定下一帧所需的时隙数，帧的时隙数 通常为4 、8 、1 6 、3 2 、6 4 、1 2 8 、2 5 6 【2 5 1 ，在实际标签数小于帧时隙数时会出现很多空 时隙，而在标签数远远大于帧时隙时则会出现大量的碰撞，标签数在大于2 5 6 时，随着 标签数的增加，识读出所有标签所需要的总时隙数呈指数增长，它的识别性能下降非常 快。因此，后来有人提出了基于分组的动态帧时隙a l o h a 算法，简称e d f s a 算法【2 6 】，此 算法就是针对d f s a 算法处理较多标签数量性能急剧下降提出来的改进算法，算法中规 定标签小于3 5 5 时分成1 组，3 5 5 ，- - - 6 2 2 时分成2 组，6 2 3 ，- - - 8 8 3 时分成3 组，8 8 4 - - 11 4 1 时分成4 组，随着标签数的增加分成更多组，但组数不能超过8 组吲j 。 3 2 6 二进制树搜索算法 二进制树搜索算法( b i n a r yt r e es e a r c h ，简称b t s 算法) ，算法约定： ( 1 ) 标签之间要严格同步，以便准确地监测碰撞位的发生； ( 2 ) 要求能辨认出读写器中数据碰撞的比特位的准确位置，一般采用m a n c h e s t e r 编码。 该算法基本思想是将处于冲突的标签分成左右2 个子集0 和l ，先查询子集0 ，若 没有冲突，则j 下确识别标签，若仍有冲突则再分裂，把子集0 分成0 0 和0 l 两个子集。 内蒙古科技大学硕士学位论文 依次类推，直到识别出子集0 中的所有标签，再按此步骤查询子集l 2 s l 。二进制树搜索 算法原理图见图3 3 。 图3 3 二进制树搜索算法原理图 二进制树搜索算法是利用逐步减少发生冲突的位的方法来完成对标签的识别的。读 写器必须能够准确地发现发生冲突的位是该算法的前提条件。因此，在该算法中，标签 的返回信号的编码方式使用了m a n c h e s t e r 编码。在m a n c h e s t e r 编码方式中，每个信号 比特中间引入跳变来同时代表不同数值和同步信息。一个负电平到正电平的跳变代表逻 辑“0 ”，而一个正电平到负电平的跳变则代表逻辑“l 在数据传输过程中“没有变 化”的状态是不允许的。因此，当个读写器收到标签的返回信号后，如果发现某些位 信号的状态没有发生改变，那么读写器就能够判断这些位一定发生了相互之间的冲突。 z7 动态二进制树搜索算法 动态二进制树算法的思想有两种：一种是发送数据量冗余。在二进制树算法中，需 要对所有序列号的标签进行搜索，而且标签的序列号总是一次次完整的传输，序列号往 往是很长的，在一定程度上影响了防碰撞的速度。根据序列号编码规律，可以去掉部分 冗余信息，只传输其中有用的部分，这样可以极大地减少需要传输的信息位数，提高传 输效率另一种是查询次数冗余在二进制数搜索算法中往往有很多不必要的搜索，可 以根据读写器接收到的信息分析出没有的分支，从而跳过或忽略这些节点。后来有人这 些原理提出了减少搜索次数的改进的动态二进制树算法，如后退式索引的二进制树算 法、跳跃式二进制树算法、基于修剪枝的二进制树算法。 后退式索引的二进制树算法的思想是：当一个标签被识别出之后，该算法的重复过 程和二迸制算法不同。读写器在下一过程开始所发送请求命令中的参数和上一过程的倒 内蒙古科技大学硕士学位论文 数第二个请求命令的参数相同。然后是倒数第三个，第四个等等。该过程一直反复，直 到所有的标签都被识别。在第一次请求命令中，读写器发送“n u l l ，而不是最大的识 别码。在下一个请求命令中，读写器发送已知的位，而不是所有的位。和二进制搜索算 法相同，读写器也是从高位到低位开始搜索。如果标签的识别码的高位和读写器发送的 已知位相同，则标签响应读写器例。算法的执行过程见图3 4 。 t a g l ：0 1 0 0 1 0 0 1 t a 9 2 ：0 111 0 0 0 0 t a 9 3 ：0 10 0 1 0 0 0 t a 9 4 ：0 11 1 1 0 0 0 t a g s ：0 1 0 0 0 0 0 1 - - - - - 卜f o r w a r d 一一b a c k w a r d i 1 衫, r 罗e q u e 蝌u 太之 r e q u e s t ( 0 1 0 4 r e q u e s t ( 0 1i1 0 ，3 ) 6 、 r e q u e s t ( 0 1 0 0 0 , 3 ) r e q u e s t s 0 1 0 0 1 0 0 0 ，0 ) 图3 a 后退式索引的二进制树算法 跳跃式二进制树算法根据标签碰撞的特点，跳跃式前后搜索。识别n 个标签，需 要查询2 n - 1 次。与二进制树搜索算法有三点区别刚： ( 1 ) 在一个标签的i d 被识别后，跳跃式反碰撞算法的过程不是二进制搜索算法的重 复。读写器发送的下一个代码所识别标签所在节点的父节点代码。 ( 2 ) 读写器发送问询命令时，只发送代码l 而不发送与标签e p c 等长的全l 代码 ( 3 ) 在下一个问询命令中，读写器只发送若干位，而不像二进制搜索算法那样发送全位 i d 值。 基于修剪枝的二迸制树算法的主要思想是所有标签的i d 号构成一个完全二叉树， 但在读写器有限的作用区域内，标签所形成的二进制树将存在许多空闲结点。搜索时， 忽略掉这些空闲结点，能快速、有效的识别区域内的所有标签【3 。 图4 2 二进制树搜索算法吞吐率 内蒙古科技大学硕士学位论文 4 1 2f s a 算法与d f s a 算法的对比分析 帧时隙a l o h a 算法，又称为固定帧时隙a l o h a 算法，它的固定帧数通常设为1 6 或 者3 2 ，本论文对其做的算法仿真固定帧时隙数为1 6 ，图4 3 为帧时隙a l o h a 算法和动态 帧时隙a l o h a 算法的识读总时隙对比图，图4 4 为帧时隙a l o h a 算法和动态帧时隙 a l o h a 算法的吞吐率对比图，其中动态帧时隙a l o h a 算法的初始帧时隙数为1 6 ，标签d 位数为1 6 ，标签估计算法采用2 3 9 2 2 乘以上帧识读的碰撞时隙数。 图4 3f s 算与d f s 算法识读总时隙对比图 图4 4f s 算与d f s a 算法识读吞吐率对比图 内蒙古科技大学硕士学位论文 从以上两图可以看出，帧时隙a l o h a 算法识读总时隙随标签的增加上升非常快，对 应的吞吐率也下降很快，最好用于标签数低于5 0 的场合。而动态帧时隙a l o h a 算法则 改善了不少，使标签的识读时隙下降了很多，而且吞吐率在6 0 0 张标签内基本上能维持 在2 5 以上，但标签数量超过6 0 0 以上后，其性能也下降得很快。 4 1 3d f s a 算法与e d f s a 算法的对比分析 动态帧时隙a l o h a 算法在标签数大于2 5 6 后其识读总时隙会呈指数增长，吞吐率也 急剧下降，基于分组的动态帧时隙a l o h a 算法解决了此问题。图4 5 为d f s a 算与e d f s a 算法识读时隙对比图，图4 6 为d f s a 算与e d f s a 算法识读吞吐率对比图。 图4 5d f s a 算与e d f s a 算法识读时隙对比图 图4 6d f s a 算与e d f s a 算法识读吞吐率对比图 内蒙古科技大学硕士学位论文 从图4 5 和图4 6 中可以看出，e d f s a 算法在标签数量较多时识读效率有了明显改 善，在读取2 0 0 0 张标签内吞吐率基本上能保持在2 0 以上，但在处理数量较多的标签 时总时隙数还是很多，等待的时间让人很难接受，而且由于标签估计算法的不足导致吞 吐率在标签数2 0 0 至6 0 0 区间还有所下降。 4 2 基于随机数传送的动态帧时隙a l o h a 算法 4 2 1 算法的思想 基于随机数传送的动态帧时隙a l o h a 算法( d y n a m i cf r a m e ds l o t t e da l o h a a l g o r i t h mb a s e do nt r a n s f e r r i n gr a n d o mn u m b e r ，简称r d f s a 算法) ，是本论文对 d f s a 算法的改进算法奎算法要求在标签上增加一个随机数，标签数据结构为 表1r d f s a 算法标签数据结构 i d 臀引8嚣姒8 时隙计数和随机数均由标签的随机数生成器( 或算法) 产生，但要求在两个不同的 阶段，也即要求两者之间无关。若用r a n d n 表示随机数生成器( 或算法) 产生的随机 数，则标签的随机数为1 ( r a n d n o x 0 7 ) ，也就得到了八个随机数( - - 进制) ： 0 0 0 0 0 0 0 1 ，0 0 0 0 0 0 1 0 ，0 0 0 0 0 1 0 0 ，0 0 0 0 1 0 0 0 ，0 0 0 1 0 0 0 0 ，0 0 1 0 0 0 0 0 ，0 1 0 0 0 0 0 0 ， 1 0 0 0 0 0 0 0 ，此组随机数的特点是任何两个不相同的随机数进行“逻辑或运算都不会相 互干扰，而相同时隙下的两个相同随机数则对应为两标签碰撞，随机数起着动态分离多 标签的作用，相当于一个分离器。读写器用于接收随机数的时隙在一帧中是固定的，在 不同帧时则按照d f s a 算法动态调整所需的帧时隙数，而用于接收的标签i d 时隙则是变 化的，它是根据接收到的数据来动态增加时隙。例如，在某一时隙读写器接收到的八位 二进制数为0 1 0 0 1 0 1 0 ，可以将其分解为0 1 0 0 0 0 0 0 、0 0 0 0 1 0 0 0 、0 0 0 0 0 0 1 0 三个随机数， 则至少有三个标签向其发送了随机数，因此需要增加3 个用于接收标签i d 时隙。 本算法的主要思想是通过时隙计数和随机数两个无关的随机量来确定单个标签，从 概率的角度看两个标签选择同一时隙、同一随机数比两个标签选择同一时隙的可能性小 很多，从而减少了碰撞、提高识别效率。 对此，算法要求读写器命令和标签的响应做相应调整，请求标签发送随机数命令 r e q u e s t r a n d n u n l ，无参数，请求当前时隙的标签发送其随机数，标签接收到此命令时检 查其时隙计数是否为o ，若为o ，则向读写器发送其随机数；不为0 ，则其时隙计数自 减l 。请求标签发送i d 命令r e q u e s t i d ( r a n d n u m ) ，请求当前时隙且随机为r a n d n u m 的 内蒙古科技大学硕士学位论文 标签发送其i d ，当前时隙的标签接收到此命令时比较其随机数是否等于r a n d n u m ，若相 等，则向读写器发送其i d ，不相等，则不响应。图4 7 描述了本算法具体操作过程。 图4 7r d f s a 算法流程 内蒙古科技人学硕士学位论文 4 2 2 算法分析 本论文所提出的基于随机数传送的动态帧时隙a l o h a 算法可以用以下伪代码来描述 算法的整个执行过程。 读写器监听( 按一定时间问隔发送某特定命令) ； 读写器检测到射频场内有标签， w h i l e ( 1 ) 未被读取的标签初始化； f o r ( 时隙为0 ；时隙 帧大小；时隙自增1 ) 读写器请求当前时隙的标签发送其随机数；r e q u e s t r a n d n u m ( 时隙) 标签发送其随机数； 如果读写器没接收的数据，继续； 否则，保存当前读写器接收到得数据到t e m p ： w h i l e ( t e m p ! ：o ) 如t e m p = l o o l o l o o b 读写器请求随机数为t e m p 对应l 最高位的随机数的标签发送其i d ： t e m p 自减此随机数； 相应标签发送其i d ： 读写器分析接收到得数据，若无碰撞，选择读取相应标签；否则，继续； 如果没有标签，返回； 如果还有标签，估计帧大小； 4 3 基于随机数传送的动态帧时隙a l o h a 算法测试与性能比较 通常用在固定标签数下的识别时间、总轮询次数、吞吐量来衡量防碰撞算法的优 劣，其中总轮询次数在a l o h a 算法中表现为总时隙数，而在b t s 算法中为总查询次数， 吞吐量反映是整个识别过程的识别率，用“正确识读出标签的轮询数总轮询数”表 示。识别时间与总轮询次数成正比，与吞吐量成反比。以下是采用v i s u a lc + + 6 0 对 内蒙古科技大学硕士学位论文 d f s a 、e d f s a 和r d f s a 算法的仿真，得到的数据经i v l a t l a b 作图得出各算法的性能图， 仿真程序关键代码见附录a 。图4 8 为r d f s a 算法识读时隙图，图4 9 为r d f s a 算法吞 吐率图，图4 1 0 为d f s a 、e d f s a 和r d f s a 算法的识读时隙对比图，图4 1 1 为d f s a 、 e d f s a 和r d f s a 算法吞吐率对比图。 图4 8r d f s 算法标签数一时隙数图 图4 9r i ) f s a 算法标签数吞吐率图 3 6 内蒙古科技大学硕士学位论文 5 影响u h fr f i d 读写器识读性能的因素 5 1 标签估计算法 ( 1 ) 二项分布估计方法 二进制树搜索算法是确定性的算法，而a l o h a 算法是概率性的算法，所以在每一帧 ( 除了第一帧) 读取之前都要对现有标签数进行估计，标签估计的准确性也极大得影响 了读写器识读标签的效率。 假设时隙数s ，标签总数为n ，根据统计学的原理，有r 个标签选择1 个时隙的 概率为圆 p n , l $ = q 7 ( 1 - 1 s 广7 ( 式5 1 ) 对应的只有一个标签的时隙数( 成功识别) 、没有标签的时隙数( 空时隙) 、产生碰 撞的时隙数( 碰撞时隙) 的概率分别为 i ，s ( o ) = ( 1 1 s ) 一 只1 ，s ( 1 ) = s o i s ) 川 ( 式5 2 ) ( 式5 3 ) 兰r - - 2 只，：c ，= 窆r = 2 c ：( 专) ，( 1 一s ，俨7 = 一只s c 。，一川s c ，c 式5 4 ) 以上三式对应的期望值就是n 与概率相乘，与实际识别的三个值相等，便可计算出 n 的值，但这三个方程并不易解，所以这种方法很少被采用。 ( 2 ) s c h o u t c 估算方法 现在应用得最多的是s c h o u t e 估算方法。根据s c h o u t e 提出的估计多址接入设备数 目的方法【3 2 】，在一帧中标签符合泊松分布，在一帧中有k 个标签处于第i 个时隙的概率 为 p k 个标签在第t 个时隙) 印f p l 石1 ( 式5 5 ) 如果第i 个时隙发生了冲突，则说明第i 个时隙中的标签数至少是2 。因此，条件 概率分布为 内蒙古科技大学硕士学位论文 雌个标狮嗍发生蝴= 露= 1 三一a 妻茎罗( 一 如果第i 个时隙只有一个标签( 成功时隙s ) ，或没有标签( 空白时隙b ) ，那么在该 时隙的标签数条件期望值分别为l 或0 。在第i 个时隙中发生冲突的标签数的条件概率 期望值为 yp 一1 1 薹磁= 警k - - z ( k - 1 ) ! = 五e - 1 娩3 咙 c 赴7 ， 再次考虑整个标签阅读过程，可以得知在当前读写器请求命令帧之后，系统中未被 读写器识别的标签数目期望值n 为 n - - 2 3 9 2 2 c ( 式5 8 ) 式5 8 中，c 为发生标签冲突的时隙的数目。n i 作为下一轮读写器请求命令帧的调 整后时隙数。 ( 3 ) e - p e 估算方法 当某一帧长度为f 识别完后，可以统计出空时隙数目f o 、已读取时隙f l 以及碰撞 时隙f c ，这些时隙所占的比例与标签数目1 1 具有一定的概率统计关系【3 3 1 。设空时隙的 概率为p o 、识别时隙的概率为p l 、碰撞时隙的概率为p c 。则某一时隙为空时隙、 识 别时隙、碰撞时隙的概率分别为 = l 一昂一日 ( 式5 9 ) ( 式5 1 0 ) ( 式5 1 1 ) 文献 3 3 】中提出用p c ( p c = f c f ) 做横坐标，用每个碰撞时隙中的平均标签数e 做 纵坐标， c 和p c 之间的关系几乎与帧长度无关，是固定不变的未识别的标签数即为 广一 譬掣 内蒙古科技大学硕士学位论文 n = e * f e ，并作出了“e - p cc u l v c 曲线图，见图5 1 。对曲线分三段进行拟合，建立了e 和p c 的数学表达式： l1 5 + 2 0 6 p = 1 2 e c - - o 石+ 1 90 6 e 0 8 l6 孤( 只一n 6 ) + 2 5 3e 0 8 图5 1e _ p cc u m 曲线图 ( 式5 1 2 ) 由于二项分布估计方法计算比较复杂，会给r h d 系统带来太多额外的计算，所以 本论文仅对后两种标签估计方法作了d f s a 算法计算机仿真，见图5 2 和图5 3 。 3 9 内蒙古科技大学硕士学位论文 貌砒。赫赫勰南赫m ；绷滋南。勰。蹴赫赢a 赫一 图5 2 标签估计方法识读总时隙对比图 图5 3 标签估计方法吞吐率对比图 从图5 2 中可以看出，在d f s a 算法中e - p c 估计方法在识读总时隙上略优于 s c h o u t e 估算方法。从图5 3 中可以看出，标签数低于1 0 0 0 时，e - p c 估计方法优势比较 明显。 5 2 随机数生成算法 r f i d 中认证加密和防碰撞算法都需要用到( 伪) 随机数生成算法，其随机性的高低 直接影响至i r f i d 系统的性能。随机序列至少应该满足：随机序列的循环周期要足够 。蒡；。；移；链蛰嬷黪器 。纂；磐鼯黟； 内蒙古科技大学硕士学位论文 大、随机序列应具有良好的统计特性( 如均匀性) 以及随机序列生成的可行性。常 用的( 伪) 随机数生成算法有：取中法、移位法、同余法、混合法。 ( 1 ) 取中法 取中法是将位数为s 的十进制随机数平方后得到2 s 位数十进制数，然后将此数 去头截尾取中间的的s 位作为一个随机数，再重复上述过程就能得到一随机数序 列。取中法的优点是在计算机上容易实现，计算量小，但产生的数均匀性不好，数 列的周期难以确定。后来有人对平方取中法进行了改进，提出了乘积取中法。乘积 取中法是将两个s 位的随机数相乘，取其乘积的中间s 位，此种方法产生的随机数 序列均匀性有所改善0 4 1 。 ( 2 ) 移位法 计算机、单片机以及其他电子m c u 器件一般都集成了移位逻辑运算器，它的价格比 较低廉，而且运算速度也比较快，用此器件来产生随机数的方法称为移位法。如果字长 为3 2 位的计算机，取一初始值，将而左移7 位得n x o 。，右移7 位得n x o ：。将x o 。和 进行指令相加得到五，再对毛重复上述运算过程得到而，这样进行多次可得正整数序 列矗。移位法对初始值的依赖性很大，而且不能太d , t 3 4 1 。 ( 3 ) 伺余法 在生成单组随机数的情况下，同余法是一种比较好的( 伪) 随机数生成算法，其中 有加同余法、乘同余法和混合同余澍3 5 】。 h l = 名毛+ c ( m o d m ) ，0 “ m 产生伪随机数列= 毛m 其中入，c ，m 以及初值而都是正整数。容易看出，：i 满足o l 若c ：0 且入1 ，则称这种方法为混合同余法。 当c = 0 时， h l = i x , ( m o d m ) ，0 s + l o l u n s i g n e di n td d - - i n p u t ； _ i n t 6 4t e m p = o ； i n t 6 4 i - l ； 一 -， f o r ( i n t 瑚；i 1 ) i f ( ( d d & l 户1 ) t e r n p = t e r n pf ( j 2 ； ) r e t u r nt e m p ； i l | | | | l 嘶| | | l | | | | l | l l l | | | | | l | l | l | l | | 1 l | l | l l | | l | l l l | | | | | l l l | | l | | | l l l l l l l l l l | l | | l | l | | | 砌能：标签发送d 给读写器 参数说明：t a g s ：标签数组首地址t a g n u m ：标签数 返 回：0 没有标签；l 一发送成功 1 | | l | | | | l | l | l | | l l | | | l l | l | l | i | | i l