2 2 2 2 2 　第 23 卷 　第 5 期 　2005 年 9 月 应 用 科 学 学 报 JOURNAL OF APPLIED SCIENCES Vol. 23 , No. 5 　 Sep. 2005 　 　　文章编号 : 0255 8297 (2005) 05 0489 04 时隙 ALO HA 法在 RFID 系统防碰撞问题中的应用 胡建　 , 　李 　强 , 　闵 　昊 (复旦大学 专用集成电路与系统国家重点实验室 , 上海 200433) 摘 　要 : 时隙 ALOHA 法是射频识别 (RFID) 系统中常用的防碰撞算法 ,该文在分析 RFID 系统识别过程后引进马尔 可夫链来为时隙 ALOHA 法建模 ,并根据此模型对时隙 ALOHA 法的性能进行分析 ,得到时隙数 、RFID 系统中所含的 应答器数与识别成功率的关系 ,从而对实际应用提供理论指导. 关键词 : 时隙 ALOHA ; 射频识别 ; 防碰撞 ; 马尔可夫链 中图分类号 : TN45 　　　文献标识码 : A Application of Slotted ALO HA to Anti collision of RFID System HU Jian yun , 　LI Qiang , 　MIN Hao ( State Key Laboratory of ASIC and System , Fudan University , Shanghai 200433 , China) Abstract : Slotted ALOHA is a commonly used protocol in anti collision of RFID system. Having analyzed RFID system’s identification process , Markov chain is introduced to model the slotted ALOHA. The model is used to analyze performance of the slotted ALOHA , and find the relationship between success probability and number of slots and tags in the RFID system , providing a guide for practical applications. Key words : slotted ALOHA ; RFID ; anti collision ; Markov chain 　　射频识别 (radio frequency identification , RFID) 技 术是近年来兴起的一门自动识别技术. 与传统的条 形码系统 、接触式 IC 卡等不同 ,射频识别系统是利 用无线射频方式非接触供电 ,并进行非接触双向数 据通信 ,以达到识别并交换数据的目的. 同其他识别 系统相比 ,射频识别系统具有许多优点 ,随着集成电 路技术的发展与成熟 ,射频识别技术有着更广阔的 市场. 一般来说 ,一个 RFID 系统由 3 部分组成 ,分别 是应答器 、阅读器和数据处理子系统. 应答器放置在 要被识别的对象上 ,并且应答器是 RFID 系统中的 数据载体. 通常应答器由耦合元件以及微电子芯片 组成. 在阅读器的响应范围之外 ,应答器处于无源状 态. 通常 ,应答器没有自己的供电电源. 只是在阅读 器的响应范围之内 ,应答器才是有源的. 应答器工作 所需的能量 ,如同时钟脉冲和数据一样 ,是通过耦合 单元 (非接触的) 传输给应答器的. 而阅读器可以从 应答器上读数据 ,也可以向应答器写数据. 一台典型 的阅读器包含有高频模块 (发送器和接受器) 、控制 单元以及与应答器连接的耦合元件. 此外 ,许多阅读 器还都有附加的接口 ,以便将所获得的数据进一步 传输给另外的系统 (个人计算机等) ,即数据处理子 系统. 在 RFID 系统工作的时候 ,可能会有 1 个以上的 应答器同时处于阅读器的作用范围内 ,这样当有 2 个或 2 个以上的应答器同时发送数据的时候就会出 现数据的干扰 ,这个干扰被称为碰撞 (collision) ,其 结果将会导致一次传输的失败 ,因此必须制定适当 的通信方式. 一般在 RFID 系统中存在两种基本的 通信方式. 第一种通信形式 :从阅读器到应答器的数 06 25 ; 　修订日期 :2004 收稿日期 :2004 基金项目 :国家“863”高技术研究发展计划资助项目 (2003AA1Z1280) 作者简介 :胡建　 (1981 - ) ,男 ,上海人 ,硕士生 ,E 09 09 mail :hujy @fudan. edu. cn ;闵昊 (1965 - ) ,男 ,上海人 ,教授 ,博导 ,hmin @fudan. edu. cn 

094 　　　　应 　用 　科 　学 　学 　报 23 卷 　 据传输为第一种通信方式 ,发送的数据流同时被所 有的应答器接受 ,这种通信方式被称为“无线电广 播”. 第二种通信形式 :在阅读器的作用范围有多个 应答器的数据同时传输给阅读器 ,这种形式就称作 多路存取 1 . 在 RFID 系统中存取记录的技术方法 (该方法 能够使多路存取无故障地进行) 被称为防碰撞法 collision) . 一般防碰撞算法可以根据在防碰撞 (anti 算法过程中应答器如何响应阅读器而分为随机的和 决定性的防碰撞算法. 本文研究的是随机防碰撞算 法中常用的时隙 ALOHA 法 2 . 1 　时隙 ALOHA 法描述 在详细描述时隙 ALOHA 防碰撞算法之前 ,先简 单介绍一下应答器的识别特征. 每个应答器 i ∈{1 , 2 , …, n}都有一个唯一的 ID 串{0 ,1} k ,是由 0 、1 组 成的 ,其中 k 是 ID 串的长度. 阅读器就是根据这个 唯一的 ID 串来识别应答器的. 在一开始 ,阅读器并 不知道任何关于应答器的信息. 无碰撞是指几个应 答器同时响应 1 个阅读器的激励却不造成信息的损 失 ,即当多于 1 个应答器在同一时间回应阅读器时 , 阅读器将会检测到一个冲突 ,而不是接受信息. 这里 讨 论 的 是 有 固 定 读 应 答 器 时 间 的 时 隙 ALOHA 法 (framed slotted ALOHA) ,如图 1 所示. 图 1 　固定读应答器时间的时隙 ALOHA 算法 Fig. 1 　Framed slotted ALOHA 　　如图 1 所示上面的一个个椭圆代表了一个个的 应答器 ,而下面的方形代表了固定的时隙 ,如同实际 情况一样 ,系统中可能遇到时隙数比应答器数少 、相 等和多几种情况. 应答器在这段固定的时间内被随 机地分配到一个个的时隙中 ,在这个时隙中 ,应答器 与阅读器通信 ,接到阅读器的指令后把自己的 ID 串 传输给阅读器 ,因此有的时隙里面被分配到 1 个或 1 个以上的应答器 ,有的时隙里面还是空的. 而当 1 个时隙里面被分配到 1 个以上的应答器的时候就会 导致数据传输的失败 ,即导致碰撞 ,这样阅读器在这 个时隙里面就无法接受到应答器的信息. 在此我们假设 :每个应答器向阅读器传送数据 的长度是固定的 ,且恰好在 1 个时隙中传送完毕 ;信 道的延迟为 0 ,且不考虑传输错误 ;在这段固定长度 里时隙的数量为 N ,应答器的数量为 n. 2 　时隙 ALOHA 法分析 对于时隙 ALOHA 算法而言 ,下一个时隙之后被 识别出的应答器的数量是由当前时隙过后所识别出 的应答器的数量决定的 ,与前面的时隙过后所识别 出的应答器的数量无关. 因此 ,我们可以通过引进马 尔可夫过程中的马尔可夫链 (Markov chain) 来分析 这个算法 3 . 所谓马尔可夫过程 ,就是指具有将来与 过去无关 (条件独立) 的性质的过程. 而马尔可夫链 是指时间 、状态都是离散的马尔可夫过程. 这里的马 尔可夫链的离散 、无限状态空间是{1 ,2 , …, n} ,设 其转移概率矩阵为 P = ( pij ) ,其中 pij = Q ( Xn + 1 = j| Xn = i) 是一步转移概率 4 . 下面要做的就是用马尔 可夫链来为时隙 ALOHA 算法建模 ,即推导出时隙 ALOHA 算法的转移概率矩阵. 阅读器在下一个时隙之后所识别出的应答器数 量与前一个时隙相比 ,共有 3 种情况 ,分别是比前一 个时隙之后识所别出的应答器数量少 ,与前一个时 隙之后识所别出的应答器数量相等和比前一个时隙 之后识所别出的应答器数量多 ;于是可以分 3 种情 况来建立转移概率矩阵 ,分别是 j < i 、j = i 和 j > i , 这里 j 和 i 分别代表了阅读器在下一个时隙之后所 识别出的应答器数量和在前一个时隙之后所识别出 的应答器数量. 首先来看 j < i 的情况 ,由于阅读器在下一个时 隙之后所识别出的应答器数量不可能比前一个时隙 之后所识别出的应答器数量少 ,即不可能进入一种 状态其识别出的应答其数量比前一次识别出的应答 其数量少 ,故在这种情况下 ,即 j < i 时 , pij = 0. 当 j = i 时 ,可以用 Cr i n 表示选中原先已经识 Cr i Q ( a1 = r) 表示考虑到从 别出的应答器的概率. 用 ∑ 没有应答器是被单独分配给 1 个时隙的情况到有 i 个应答器被分别分配到 1 个时隙中的情况. 从而得 r = 0 到在 j = i 的情况下 , pij = ∑ Q ( a1 = r) i r = 0 i Cr Cr n . 下面着重分析 Q ( a1 = r) 的意义. 这里 a1 为随 机变量 ,表示在一个固定的时间段内恰好有 1 个应 答器的时隙的数量 ,那么 a1 = r 就表示在这个固定 的时间段内恰好有 1 个应答器的时隙的数量为 r , 

　5 期 胡建　等 :时隙 ALOHA 法在 RFID 系统防碰撞问题中的应用 194 其中 r = 0 ,1 , …, n. a1 = r 的概率 ,即 Q ( a1 = r) 为 当 j > i 时 , Q ( a1 = r) = NΠr- 1 Cr k = 0 C1 n- k H( N - N n r , n - r) (1) k = 0 C1 　　式 (1) 表示的是在这个固定的时间段内恰好有 1 个应答器的时隙的数量为 r 的概率 ,这其实是一 个排列组合问题. 我们看到式 (1) 中 N n 表示 n 个应 答器被分配到 N 个时隙的所有分配方式的数量. 对 于分子上 , Cr N 表示从 N 个总的时隙中选出 r 个时隙 来提供给应答器供其成功传输数据 ,即这 r 个时隙 中每个时隙都只有 1 个应答器 ;Πr - 1 n - k 表示从 n 个系统中所包含的应答器中一个一个地选出来分配 到前面已经选出的 r 个时隙中 ,选出第 1 个应答器 有 C1 n - 1种选法 ,如 此类推 ,直到选出 r 个应答器. 到此为止 ,已经选出 了 r 个时隙 ,并且把 r 个应答器分配给了这 r 个时 隙 ,接下来就是要解决剩下的 n - r 个应答器是如 何分配到 N - r 个时隙的问题 ,在式 (1) 中用 H( N - r , n - r) 表示. 在 H( M , m) 的推导过程中 ,要注意一 点 ,就是要排除恰好有 1 个应答器被分配到 1 个时 隙中的情况 ,因为这种情况就是前面所讨论的内容 , 这里要排除 ,否则会重复计算. 可以得到下式 n 种选法 ,选出第 2 个应答器有 C1 H( M , m) = Mm + m ∑ k = 1 ( - 1) kΠk - 1 j = 0 [ C1 m - j C1 M- j ] ( M - k) ( m - k) 1 k ! m - j j = 0 [ C1 M - j ] ,其表示从剩余的 M - (2) 式 (2) 中 M 表示剩余的阅读器数量 , m 表示剩余的 应答器数量. 先来看 Mm ,这表示 m 个应答器被分配 到 M 个阅读器的所有分配方法. 对于 Πk - 1 C1 j 个时隙中选出 1 个 来 ,然后再从剩余的 m - j 个应答器中选出 1 个来 , 将这个应答器分配到这个时隙中 ,这个过程不断重 复. 再来看 ( M - k) m - k ,其表示 ( m - k) 个剩余的未 分配好的应答器再分配到 ( M - k) 个剩余的时隙的 所有排列. 对于 1 k ! ,表示对于前面的情况而言有 多余的排列 ,因为这里的排列其实是与顺序无关的. 对于 ( - 1) k ,由于前面用到了 ( M - k) ( m - k) ,故这里 又包含了在式 (1) 中分析过的重复计算的因素 ,因此 ,表 后一次要把前一次多计算的部分减去. 对于 ∑ 示从只有 1 个应答器被分配到 1 个时隙里的情况到 有 m 个 (即剩下所有的应答器) 被分别分配到 1 个 时隙里的情况. k = 1 m n Qij = ∑ r = j- i Q ( a1 = r) Cj- i n- i Cr- j+ i i Cr n n 　　这里 ∑ r = j - i Q ( a1 = r) 表示的意义如前所述 ,不过 要注意的是这里与第 2 种情况有区别的是这里的 r 是从 j - i 到 n ,因为这里被识别出的最少情况就是 j - i 的时候 ,而最大的情况就是新识别出来的加上 原先被识别出来的应答器总数为 n 的时候. 对于 Cj - i n - i Cr - j + i i ,表示的就是从 n - i 个应答器中选出 j Cr n - i 个应答器 ,以及从已经被识别出的应答器中选 出剩余的 r - j + i 个应答器的概率. 根据以上分析 ,可以得到时隙 ALOHA 算法的转 移概率矩阵为 0 　　　　　　　　 i ∑ r = 0 Q ( a1 = r) qij = n ∑ r = j - i Q ( a1 = r) i Cr Cr Cj- i n- i Cr- j+ i n i Cr n j < i ; j = i ; j > i . (3) 　　至此 ,通过引进马尔可夫链 ,根据时隙 ALOHA 法的 3 种具体情况 ,推导出了时隙 ALOHA 法的数学 模型表述. 3 　时隙 ALOHA 法性能分析 在分析以上引进马尔可夫链所建的模型时 ,不 考虑阅读器捕捉率的问题 ,假设阅读器能识别出应 答器就能成功地获得应答器中所包含的数据. 对于离散 、无限的马尔可夫链 ,存在一个稳态概 率分布的向量 ,Π = [π0 ,π1 , …,πM ] ,其中 πn 代表 在状态 n 时的稳态概率 ,πn 定义为 lim Pr ( nt = n}. t →∞ 这个稳态概率分布的向量可以通过下面的 M + 1 个 线性联立的方程来计算 Π = PTΠ 其中 Π 要满足 M ∑ i = 0 πi = 1 (4) (5) 　　可以用线性代数来求 Π ,因为式 (4) 表示的 Π 是对应于特征值的特征向量 ,我们只需要求出这个 特征向量 Π 并且将其归一化使其满足公式 (5) . 求 出了 Π 之后 ,由于 πn 代表在状态 n 时的稳态概率 , 

294 　　　　应 　用 　科 　学 　学 　报 23 卷 　 i πi 来求出系统中识别出 故我们可以用公式 L = ∑ 的应答器数量的期望值. 可以用 MATLAB 来解决这 个问题. i 我们来分析固定时隙数量时 ,不同数量应答器 的情况. 这里将时隙的数量固定在 25 个 ,应答器的 最大数量设为 30 个. 可以得到在 25 个时隙数时 ,系 统中应答器数量增加时的识别成功率变化情况 ,如 图 2 所示. 图 2 　固定时隙时应答器数量增加时的 识别成功率变化图 Fig. 2 　Change of successful identification ratio with increase of tags in framed slot 　　从图中我们可以发现 ,当系统中只有 1 个应答 器时 ,阅读器的识别率是 100 %. 随着应答器数量的 增加 ,阅读器的识别率以较大的幅度下降 ,到了 10 个应答器左右时 ,下降的幅度渐渐减小 ,稳定在 55 %附近 ,直到当应答器的数量为 25 个时 ,即开始 超过给定的时隙数量时 ,阅读器的识别率开始以较 大的幅度下降. 4 　总 　结 本文分析了射频识别 ( RFID) 系统的防碰撞算 法中常用的时隙 ALOHA 法 ,通过对其识别过程的分 析而引进马尔可夫链来对其识别过程建立模型 ,再 结合数学工具对其性能进行分析 ,得出系统识别成 功率和系统所提供的时隙数与系统中包括的应答器 数量之间的关系 ,从而在实际应用时可根据实际情 况来调节时隙数以求得最佳效果. 参考文献 : 1 　Klaus Finkenzeller 著. 射频识别 (RFID) 技术 ———无线电 感应的应答器和非接触 IC 卡的原理与应用 M . 陈大 才译. 北京 :电子工业出版社 ,2001. 132 - 150. 2 　Alvin Lin , Kui Mok. A study on the design of large scale mobile recording and tracking systems A . System Sciences , 1998 Proceedings of Conference on C . 1998. 701 International the Thirty First Hawaii 710. 3 　Imrich Chlamtac , CHiara Petrioli , Jason Redi. Energy conserving acess procols for identification networksJ . IEEE ACM Transactions on Networks ,1999 ,7(1) ,51 59. 4 　林元烈. 应用随机过程 M . 北京 :清华大学出版社 , 2002. 78 - 124. (编辑 :秦 　巍)