二进制树算法

2024-10-12

二进制树算法（精选8篇）

二进制树算法篇1

引言

RFID技术是物联网系统的基础, RFID系统硬件主要由阅读器和RFID标签构成。阅读器通过无线信号与RFID标签进行信息联系, 阅读器对进入自身识别区域的RFID所发出的无线电波产生反应, 识别出对应标识, 并进行能量传递和信息交互等工作。在RFID应用中存在着阅读器和RFID标签目标识别的问题, 如果在一个有效识别区域内出现多个阅读器或多个RFID就会出现相互干扰的问题, 被称为RFID系统碰撞, 解决多个目标的识别问题也就是RFID系统防碰撞算法。[1]目前主要有两种类型的RFID防碰撞算法, 其一是ALOHA算法, 它采用的是退避原则, 是一种不确定算法;而另一种则是树型分解算法, 其具有稳定的识别次数, 二进制树搜索算法就是其最基本算法之一。[2]

一、二进制树防碰撞算法

1二进制树型搜索算法

(1) 工作状态的标签进入读写器有效识别范围时, 读写器广播一个所有位数全为1的最大识别号, 标签的序列号都会小于该最大识别号, 由此全部标签均产生应答并把序列号发送给读写器。

(2) 标签返回的序列号是唯一的, 当应签的标签大于二个时, 就会产生碰撞, 在曼彻斯特编码时表现为无法区别0或1, 碰撞区域内的最低位数取为0, 位数低者不变, 高于其位的取1。

(3) 读写器将上述重新编制的识别号发送给标签, 标签接收到后将序列号和新的识别号进行对比, 如果小于或等于该识别号, 则产生应答将序列号发送给读写器。

(4) 重复运行以上过程, 最终将确定一个最小序列号的标签, 读写器就可以和该标签进行正常的信息交互。在完成信息交互后, 读写器会发出一个指令使标签进入休眠状态, 不再响应读写器的任何请求 (除非重新上电) , 这样就不会对继续搜索其它标签产生影响。

(5) 继续循环以上过程, 就可以将各标签按序列号由小至大逐个识别出来。

2实例

假设阅读器范围内有四个标签:

标签A:10100111;

标签B:10110101;

标签C:10101111;

标签D:10111101。

3性能分析

对二进制搜索算法的搜索过程进行模拟可以得到, 防碰撞算法是明确发生碰撞的情况下, 对碰撞区域内的各数位逐个进行识别号比较排查以确定某一个序列号, 这样就存在一个较难克服的问题:识别区域中的标签越多, 防碰撞算法的识别时间将越大。经过上述模拟过程我们可以用一个计算式来表示单次执行的时间长度:

其中C是读写器识别范围内有效标签的个数。

对于所有标签, 由上我们可以把总搜索次数通过下式来表示:

从上式可以看出该算法搜索次数与C的大小存在发散的关系, 随着C增大搜索次数增长更快。

二、改进型算法

1基本思路

在基本二进制树搜索算法的基础上, 我们可以进行一定的改进。分析上面算法总搜索次数的计算式, 我们可以了解到基本二进制树搜索算法的性能由两个参数来决定, 一个是二进制树的节点个数, 另一个是单次执行的时间。这两个参数中二进制树节点个数主要与标签划分相关, 就是说如何用较好的树型来减少同样数量的叶子结点构成的树中的节点个数;而单次搜索执行时间主要是与读写器发出的识别码的数据位数的长短有关, 减小位数将有益于执行时间的缩短。由此, 如何将节点个数和数据位数进行优化是现在对基本二进制树搜索算法进行改造的主要出发点, 也形成了不少有效的、先进的新算法。由此, 我们改进的主要思路就是:

(1) 优化每次传送的数据位数;

(2) 减少标签分组的节点数目。

2改进算法描述

在改进算法中, 我们引入一个堆栈S来存放标签信息;建一个寄存器L用作查询队列指针;用一队列Q作为PrefixQuery (前缀查询) 存放识别码;标签中再建一个Counter存放碰撞位数。

算法如下:

(1) 读写器对有效识别范围内的所有标签发出上电复位指令, 将堆栈信息清空, 队列Q清空, Conter清0。

(2) 读写器发送查询前缀请求信息, 所有标签响应。响应的情况有三种:

●只有一个标签响应, 响应位为“0”, 二叉树生成一个左节点;堆栈S中存入读写器接收到的标签信息, 队列Q中填写入左子树的查询识别码。

●只有一个标签响应, 响应位为“1”, 二叉树生成一个右节点;堆栈S中存入读写器接收到的标签信息, 队列Q中填写入右子树的查询识别码。

●多于一个标签发生响应 (碰撞) , 二叉树当前的节点将存在左子树和右子树, 在二叉树中添加左右子树节点。堆栈S中压入新生成的搜索位数所组成的识别码, 并用寄存器M指引到当前节点位置中, 下一次查询时将发送寄存器M所指引的识别码。发生碰撞后的碰撞位为“1”的Counter值加1, 该标签对读写器下一次的查询将不应答。

(3) 持续重复执行上步, 确定出一个叶子节点后, 说明有一个标签被读写器成功识别, 将回到节点重新下一步查询。信息交互完成后, 标签进入休眠状态, 不再响应读写器。将堆栈顶部信息出栈, 接下来将构造二叉树的右子树, 然后将Couter值不为“0”的标签Couter值减1, 只有Couter值为“0”的标签将响应读写器后一步的识别码。

重复执行上述步骤, 直到读写器识别出所有标签。

3改进算法性能分析

通过模拟上述算法过程可以看出:

(1) 通过引入队列, 阅读器可以准确地确定查询前缀, 以便于减少查询次数。

(2) 由于堆栈的引入, 阅读器识别出第一个标签后, 并不是重复第一步的回溯搜索, 而是通过从堆栈中取出前一次碰撞的位数, 一步实现下一个识别码, 避免了重复搜索, 这样在改善算法复杂度和传输效率上都有很大帮助。

(3) 在每个标签上加入一个Counter后, 读写器发出识别码时只有Counter为“0”的标签才能响应, 减少了节点响应处理时间。

在改进型二叉树搜索算法中, 加入了几个数据结构存储元素, 对任一个标签建一个唯一的二叉树, 读写器在发送识别码时, 发送的次数和标签序列号的位数是正比的。[3]设在识别系统中共有C个待识别标签, 每个标签的序列号位数为m, 那么有效识别任一个标签的次数最大为m, 最坏情况下, 我们认为发送m次可确定一个标签。搜索中发送识别码位数次数要有:

每个标签搜索要发送识别码次数的平均值为:

可以证明成功识别N个标签所需要的总搜索次数

三、小结

目前, RFID标签识别系统中防碰撞技术是其一个最为核心的技术。一般采用二进制树型搜索的算法来解决碰撞问题, 其优点是识别时间确定, 属稳定的算法。[4]但该算法的不足之处在于标签识别时间大, 算法循环和回溯频次较多, 因而识别全部标签的总用时较长。如何减少算法的重复次数和减少节点搜索个数对于算法复杂度的改善要求有较大帮助作用的。文中探索了一种改进型二进制算法, 利用存储队列、指针和计数器的方法减少节点搜索次数, 从而使算法的效率得到了提高。 (下转第69页)

参考文献

[1]Finkenzeller K.射频识别技术.清华大学出版社, 2000, 103-119

[2]日本NTT COMWARE株式会社著, 郑维强译.RFID的现状和发展趋势.人民邮电出版社, 2007, 62-82

[3]希玉九.电子标签 (RFID) 技术及其使用的频率.中国无线电, 2004, (12) :21-23

[4]游战清, 李苏剑.无线射频识别技术 (RFID) 理论与应用.电子工业出版社, 2004, 105-116

二进制树算法篇2

(青海师范大学数学系，青海 810000)

摘要：本文讲述了几种求解最小生成树的算法(Kruskal算法、Prim算法、破圈法和DNA算法)，重点介绍了一种求解最小生成树问题的DNA 算法，进而比较这几种算法的优缺点以及介绍最小生成树的几个实际应用。

关键字：最小生成树 Kruskal算法 Prim算法破圈法 DNA 算法

Several algorithm of solving minimum spanning tree and its application Xiangnan-kong

(Mathematics Department of Qinghai Normal University, Qinghai 810000) Abstract: This paper describes several algorithm of solving minimum spanning tree(Kruskal algorithm、Prim algorithm、Broken circle method and DNA algorithm), and focuses on discussing the DNA algorithm. Then it compares the advantages and disadvantages of several algorithms and introduces several practical applications of the minimum spanning tree . Keyword: Minimum spanning tree;Kruskal algorithm;Prim algorithm; Broken circle method ;DNA algorithm.

1 引言

最小生成树是网络最优化中一个重要的图论问题，它在交通网、电力网、电话网、管道网等设计中均有广泛的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。

求图的最小生成树有两种常见的算法，一种是Kruskal(克鲁斯卡尔)算法，另一种是Prim(普里姆)算法。这两个算法的基本思想均是基于避圈法，而从相反的角度，破圈法也可构造最小生成树算法。

本文讲述Kruskal算法、Prim算法和破圈法的同时，也着重介绍了一种求解最小生成树问题的DNA 算法。

2 有关最小生成树的理论基础

2.1 有关最小生成树的概念

2.1.1 定义一(图)

一个图G定义为一个偶对(V,E),记作G=(V,E)，其中

(1)

(2) V是一个集合，其中的元素称为顶点; E是无序积VDV中的一个子集合，其元素称为边;

2.1.2 定义二(树)：不含圈的连通图称为树。

2.1.3 定义三(生成树)：如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵生成树。

2.1.4 定义四(最小树)：设T?是赋权图G的一颗生成树，若对G的任意生成树T都有l T?

2.2 有关最小生成树的定理

2.2.1 定理一(最小树充要条件)

设T是G的一棵生成树，则下列条件都是T为最小树的充要条件

(1) 对任意连枝e′∈GT,有l (e′)=maxe∈CT(e′){(l(e))}

(2) 对图G中任意圈C,存在e′∈CT，有l (e′)=maxe∈C{l(e)}

(3)对任意树枝e∈T,有l (e)=mine∈ST(e){(l(e′))}

(4)对G的任意割集S，在T∩S中存在一条边e，l(e)=mine′∈S

2.2.2 定理二(唯一最小树充要条件)

设T?是G的一棵生成树，则下列条件都是T?是G的唯一最小树的充要条件是下列两个条件中的任一个成立：

(1)对任意e∈GT?，e是CT?(e)的唯一权最大的边。

(2)对任意e?∈T?，e?是ST?(e?)的唯一权最小的边。

3 Kruskal(克鲁斯卡尔)算法

3.1 Kruskal算法介绍

Kruskal算法是1956年首次提出的求最小生成树的算法。后来Edmonds把这个算法称为贪心算法。其基本思路是从G的m条边中选取n-1条权尽量小的边，并且使得不构成回路，从而构成一个最小树。下面我们就来叙述这个算法.

第1步开始把图的边按权的大小由小到大地排列起来，即将图的边排序为a1,a2,…,am,使W a1 ≤W a2 ≤?≤W am 置S=?，i=0,j=1.

第2步若|S|= i=n?1,则停止。这时G [S]=T即为所求;否则，转向第3步。

第3步若G [S? aj ]不构成回路，则置e i+1=aj,S=S?{e i+1}, i?i+1,j：=j+1,转向第2步;否则，置j：=j+1，转向第2步。

MST-KRUSKAL(G,w)

T(e){l(e′)}

1 A→?

2 for each vertex ?∈V G

3 do Make-Set(v)

4 sort the edge of E into nondecreasing order by weight w

5 for each edge μ,? ∈E,taken in nondecreasing order by weight 6 do if Find-Set(u)≠Find-Set(v)

7 then A←A∪ u,v

8 Union(u,v)

9 retuen A

3.2 Kruskal算法的复杂性

首先在第1步中把边按权的大小由小到大地排列起来，这约需mqlog2m次比较;其次第2步最多循环n次;在第3步中判断G [S? aj ]是否构成回路，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较。所以总的计算量为mqlog2m+n+m+ n(n-1)~O n2log2n 由定理一(1)易见上述算法的正确性。

3.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图2所示

图1

图2

4 Prim(普里姆)算法

4.1 Prim算法介绍

Prim算法的基本思想：首先，选择带权最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。下面我们来介绍这个算法：

设G是n+1个顶点的连通的赋权图。

第1步取T0为n+1个顶点的空图，T0有n+1个分支(即孤立点)，没有圈。

i，则E(Vi× V i)是一个断第2步把Ti的n+1-i个分支分成两个子集Vi和V

集。

i)中权最小的边，令T i+1=T i+e i+1,显然，第3步取e i+1为断集E(Vi× V

T i+1没有圈且分支数为 n+1 ? i+1 =n?i.

第4步当i=n?1时算法停止，Tn中已有n条边，构成G的一棵生成树，当i≠n?1时，令e′= i+1返回第2步。

MST-PRIM(G,w,r)

1 for each u∈V G

2 do key[u] ←∞

3 π[μ]←NIL

4 key[r] ←0

5 Q ←V G

6 while Q≠?

7 do u ←Extract?Min Q

8 for each v∈Adj u

9 do if v∈Q and w(u,v)< key[v]

10 then π v ←u

11 key[v] ←w(u,v)

4.2 Prim算法的复杂性

下面简单分析一下Prim算法的复杂性。第一次执行第2步是n-2次比较，第二次为n-3次比较，第三次是n-4比较，?，因此总的比较为2 n?2 (n?

1)次。在执行第3步时，第一次是n-2次比较，第二次n-3次比较，?，因此总的比较为(n-2)(n-1)次。由此算法的总计算量约为O n2 .

4.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图3所示

图3

5 破圈法

5.1 破圈法介绍

该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图G 中没有回路，那么G 本身就是一棵生成树，若G 中只有一个回路，则删去G 的回路上的一条边(不删除结点)，则产生的图仍是连通的，且没有回路，则得到的子图就是图G 的一棵生成树，若G 的回路不止一个，只要删去每一个回路上的一条边，直到G 的子图是连通没有回路且与图G 有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样(即删去的边不一样)所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权W(T)最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边组成的图即为最小生成树。破圈法的`复杂程度为O n3 .

5.2 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图4所示

二进制树算法篇3

RFID系统在客观应用时,读写器范围内出现多个标签同时识读的现象是很普遍的。这就会导致多个标签同时向读写器传输数据而产生碰撞,进而致使读写器接收数据失败。因此,多标签碰撞问题[1]是RFID系统进行广泛应用的难点和瓶颈所在,应当给予重点研究。

2. RFI D系统防碰撞算法分析

2.1 算法分类

目前,解决多标签碰撞问题的方法有多种。在无线电技术中,通常有四种:时分多址(TDMA)法、码分多址(CDMA)法、空分多址(SDMA)法、频分多路(FDMA)法。而对RFID系统来说,时分多址法是目前应用最为广泛的方法。时分多址[2]法从形式上又分为标签控制法和读写器控制法两类。这两类方法又包含多种防碰撞算法,如表1所示。

2.2 典型读写器控制法分析

从应用的角度考虑,对于存在大量待读标签的情况,二进制搜索算法比Aloha算法识别的准确性和效率要高。下面对读写器控制法中的各类二进制算法加以分析比较。

(1)二进制搜索算法

二进制防碰撞算法[3]的基本思想是将发生碰撞的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集01分成00和01两个子集,依次类推,直到识别出子集0中的所有标签,再按此步骤查询子集1。

该算法实现的关键在于:(1)要RFID系统同步,对于每个标签,都需要一个附加机制以产生随机数。(2)须有合适的位编码法(如曼彻斯特编码),以能识别出读写器中数据碰撞的比特的准确位置。(3)用标签序列号(EPC ID)唯一的特性[4]。(4)计一组有效的指令规则,高效、迅速地达到选择标签的目的[4]。

(2)动态二进制搜索算法

该算法是在二进制搜索算法基础上对数据传送时间进行缩短改进以提高效率的一种算法。其算法原理[5]是把数据分成两部分,收发双方各自传送其中一部分数据,当标签ID与查询前缀相符时,标签响应只发送其余的比特位,把传输的数据量减小到一半,达到缩短数据传送时间的目的来提高读取效率。

(3)跳跃式动态树形防碰撞算法

该算法在性能上均优于二进制搜索算法与动态二进制搜索算法。根据碰撞时的特点,跳跃式前后搜寻。识别N个标签,共需要问询2N-1次[6]。与二进制搜索算法主要有三点区别:

(1)在一个标签的EPC被识别后,跳跃式反碰撞算法的过程不是二进制搜索算法的重复[4]。阅读器发送的下一个代码所识别标签所在节点的父节点代码。

(2)在阅读器开始发送问询命令时,只发送代码“1”而不是发送与标签EPC等长的全1代码[4]。

(3)在下一个问询命令中,阅读器只发送若干位,而不像二进制搜索算法那样发送全位EPC值。

2.3 文献[4]算法分析

文献[4]中,提出了一种反碰撞改进算法。该算法在基于二进制搜索算法与跳跃式动态树形反碰撞算法约定的基础上,增添了两点不同的约定。其中一点约定是:由于二进制位上的取值具有相互排斥特性(非1即0),所以假如只有一位二进制位发生碰撞,则阅读器不需要发送请求命令而能够自动识别出这两个标签。但是,从技术实现的角度来讲,识别时还是需要对这两个标签进行一次辨别。否则,读写器本身是无法识读的。为此,该算法对文献中8个标签识读重复搜索的次数应当是9次。不过,该算法较其它典型的二进制算法性能优越很多。其最大优越性在于,由0与1的反复置换中,增大了与问询标签序列号相吻合的几率,从而大大缩短了查询的时间,减少了查询的次数,提高了检测效率。但由于该改进算法的目标是当碰撞连续发生时提高标签的识别速度,故其局限性在于,只适合标签碰撞位连续的情况。

3. 基于跳跃式动态树的二进制搜索改进算法

改进算法是受文献[4]中算法约定思维的启迪,在融合二进制搜索算法、跳跃式动态树形反碰撞算法、轮询法三种算法的思想和原理的前提下,提出的一种算法。与动态二进制搜索算法分两部分传输数据的原理不同。较文献[4]中算法在碰撞位状态上有所扩展。

3.1 算法提出

与二进制搜索算法和跳跃式动态树形防碰撞算法相同。需存在以下约定:(1)使用曼彻斯特编码。目的使读写器能够准确发现碰撞的比特位置。(2)要求所有标签能够在同一时刻响应阅读器的问询,以便标签能够同步发送它们的EPC值给读写器。(3)引入以下四个命令:第一个是请求命令。读写器发送一序列号(EPC值)作为请求命令进行询问。当标签序列号小于或等于请求命令序列号时,则回送其序列号给读写器。第二个是选择命令。读写器收到标签的EPC值后,若无碰撞发生,读写器就会选择这个标签,进行数据的传送。第三个是读写命令。根据读写命令来处理存储在标签内部的数据信息[4]。第四个是屏蔽命令。将已经读取到的标签进行屏蔽,使标签不在回应读写器的请求命令。

算法原理:首先,读写器发送问询代码“1”进行询问,让所有标签响应以确定所有碰撞位。而后,将所有碰撞位置0,将此EPC值作为下一步请求命令。无碰撞读标签并将其屏蔽。若存在碰撞,按照比特位由低到高的顺序,对碰撞位进行X个“1”(这里,X值由1-N,N为发生碰撞的位数)的全排列轮询,每一个排列序列号(EPC值)就是下一次的请求命令。在执行置0或置1全排列轮询的过程中,无碰撞读标签并将其屏蔽。若发生一位碰撞,在保持该排列序列号不变的基础上,将碰撞为置1,作为下一次的请求命令,即可读取标签并将其屏蔽。随后,继续执行碰撞位置1的全排列轮询,直至读取识读范围内的所有标签为止。

3.2 算法工作流程

(1)标签进入读写器的识读范围后,读写器发出发送问询代码“1”进行询问,让所有标签响应以确定所有碰撞位。将所有碰撞位置0,将此序列号作为下一个请求命令。(2)置0后,执行请求命令,无碰撞,依次执行选择命令、读写命令、屏蔽命令。(3)有一位碰撞,碰撞位置1,将此序列号作为请求命令。而后对标签依次执行选择命令、读写命令、屏蔽命令。(4)对碰撞位按照比特位由低到高的顺序,执行置1全排列。首先,将一位“1”在碰撞为做全排列轮询。无碰撞,读取标签。发生一位碰撞,碰撞位置1读取标签。一位置1全排列完成后,将“11”在碰撞位进行全排列。如此循环,一直完成N位(N为发生碰撞的位数)置1全排列,直至读取读写器范围内的所有待读标签为止。

4. 性能比较

防碰撞算法的最终目的是为了提高识读标签的速度与准确性,以完成读写器与标签之间数据的传送。下面通过具体的示例来进行算法性能的比较分析。

示例一:碰撞位连续的情况

有8张标签卡[4],序列号分别是:卡1:10000010;卡2:10001010;卡3:10010010;卡4:10011010;卡5:10100010;卡6:10101010;卡7:10110010;卡8:10111010。

改进算法识读过程:

第1次,读写器发出发送问询代码“1”进行询问,标签响应后读写器收到碰撞序列号为:10★★★010,可知第3、4、5位发生连续碰撞。将其均置为0,并将序列号(10000010)作为下一次请求命令。

第2次,读写器发出发送问询代码“10000010”进行询问。这时只有卡1响应,读写器对卡1完成选择、读写、屏蔽的过程。而后,对碰撞位按照比特位由低到高的顺序进行一位置1全排列轮询。首先得序列号(10001010),将其作为下一次请求命令。

第3次,读写器发出发送问询代码“10001010”进行询问。这时只有卡2响应,读写器对卡2完成选择、读写、屏蔽的过程。这时,继续执行一位置1全排列轮询。得序列号(10010010),将其作为下一次请求命令。

第4次,读写器发出发送问询代码“10010010”进行询问。这时只有卡3响应,读写器对卡3完成选择、读写、屏蔽的过程。这时,继续执行一位置1全排列轮询。得序列号(10100010),将其作为下一次请求命令。

第5次,读写器发出发送问询代码“10100010”进行询问。这时只有卡5响应,读写器对卡5完成选择、读写、屏蔽的过程。至此,一位置1全排列结束,读写器将按照比特位由低到高的顺序进行二位置1全排列轮询。得到序列号(10011010),将其作为下一次请求命令。

第6次,读写器发出发送问询代码“10011010”进行询问。这时只有卡4响应,读写器对卡4完成选择、读写、屏蔽的过程。这时,继续执行二位置1全排列轮询。得序列号(10110010),将其作为下一次请求命令。

第7次,读写器发出发送问询代码“10110010”进行询问。这时只有卡7响应,读写器对卡7完成选择、读写、屏蔽的过程。这时,继续执行二位置1全排列轮询。得序列号(10101010),将其作为下一次请求命令。

第8次,读写器发出发送问询代码“10101010”进行询问。这时只有卡6响应,读写器对卡6完成选择、读写、屏蔽的过程。至此,二位置1全排列结束,读写器将按照比特位由低到高的顺序进行三位置1全排列轮询。得到序列号(10111010),将其作为下一次请求命令。

第9次,读写器发出发送问询代码“10111010”进行询问。这时只有卡8响应,读写器对卡8完成选择、读写、屏蔽的过程。至此,所有标签识读完毕。

其它算法识读:跳跃式动态树形防碰撞算法根据其算法规律可知识读次数为15次。动态二进制搜索算法识读次数为28次。二进制搜索算法将会更多。文献[4]改进算法识读次数为9次。

示例二:碰撞位不连续的情况

有3张标签卡,序列号分别是:卡1:11010111;卡2:11010101;卡3:11111101。

改进算法识读过程详见表2所示。

其它算法识读:跳跃式动态树形防碰撞算法根据其算法规律可知识读次数为5次。动态二进制搜索算法与二进制搜索算法识读次数分别为7次和9次。

由上述示例可知,不同标签数各种算法对两个示例的识读次数比较见表3所示。

由表中显示的数据可以看出:对于相同数量的标签在识读时,改进算法的识读性能比上述四种算法均优越。当标签数量增大时,改进算法的识读次数增加幅度不大,而其它算法的增加幅度都比较大。并且改进算法识读次数相对于标签数量的增加幅度也是最少的。同时,改进算法对于标签碰撞位连续和不连续的情况都适合。

5. 结束语

本文提出的改进算法是基于二进制搜索、跳跃式动态数形防碰撞算法基础上改进的一种多标签识别防碰撞算法。它是将二进制的分群(0和1)、跳跃式的初始碰撞位检测及序列号轮询进行融合,并渗入数学中的全排列方法原理,提出的一种算法实现。

该算法的最大优越性在于:一次性检测碰撞,以后一直进行序列号置1的全排列轮询,不用重复进行碰撞位检测,从而大大缩减了防碰撞检测的时间;对标签碰撞位连续与不连续情况均适用,实际应用性强;更适宜对大量的标签进行读取识别,并能够有效的缩短识读时间;不仅可应用于多标签防碰撞的识别上,而且由于其识读次数与与标签数相差不大,识别速度快,还有望应用于检测标签(物体)的数量上。这些对提高RFID系统的防碰撞性能显得尤为重要。

参考文献

[1]Klaus Finkenzeller,RFID-Handbook Fundamentals and Applications in Contactless Smart Cards Identification[M](2nd Edition),2003.

[2]L.Burdet,RFID multiple access methods[A],Technical Report ETH Zurich,2004.

[3]Vogt H,Mutiple Objet Identification with Passive RFID Tags Systems,Man and Cybernetics[A].2002IEE International Conference,2002:6-9.

[4]王亚奇,一种改进的RFI D系统反碰撞算法[J].单片机与嵌入式系统应用,2007,(9):16—17.

[5]李兴鹤,胡咏梅,王华莲等,基于动态二进制的二叉树搜索结构RFI D反碰撞算法[J].山东科学,2006,19(2):51—55.

一种改进的二进制防碰撞算法篇4

近年来, 随着物联网概念的提出, 相关的理论研究得到迅速发展[1]。RFID作为物联网的一项核心技术, 成为近年来的研究热点。而标签碰撞是制约射频技术发展的一个关键问题。随着阅读器范围内标签数量的增加, 碰撞问题将导致阅读器范围内标签的吞吐率急速下降、识别速度和识别率降低。多标签防碰撞算法使得阅读器能同时识别其范围内的多个标签, 对RFID系统的运行速度和可靠性至关重要, 因此对防碰撞算法的研究是必须的。

目前, 常用的防碰撞算法都是基于时分多路算法[2]。时分多路法又分为基于时隙的ALOHA算法及其改进算法和基于树的二进制防碰撞算法及其改进算法两大类。ALOHA算法属于不确定算法, 优点是系统实现相对简单。缺点是存在无法识别某个或者某些标签的可能[3], 特别是在标签数量很大时算法效率迅速降低。改进的ALOHA算法主要通过对标签进行分流[4]以及估计阅读器范围内标签个数并以此来动态调整帧长[5]来提高标签的识别效率。改进的ALOHA算法的优点是:标签漏读率有所降低, 吞吐率增加, 但是始终没从根本上解决标签漏读的情况。二进制防碰撞算法是一种确定性的算法, 能100%地识别阅读器范围内的所有标签。缺点是系统设计相对复杂。大部分二进制防碰撞算法的文章主要从以下几方面进行改进:1) 减少阅读器的寻呼次数[4,5];2) 减少标签和阅读器每次通信传输的字节数[5,6,7,8,9], 从而减少算法的识别时间。二进制树算法识别率相比ALOHA算法较高。并且适用于有大量标签需要准确读取的情况。

本文提出的改进算法基于二进制树算法。现存的几种比较常用的改进的二进制树算法有如下两种:1) 返回二进制搜索算法[4], 该算法相对于传统二进制树算法的优势在于阅读器成功识别一个标签后返回到父节点, 而不是返回到根节点。从而减少了阅读器的寻呼次数, 但是需要以标签的UID作为搜寻索引, 搜寻时间相比于二进制树算法有所降低, 但是仍存在可以改进的地方;2) 改进的类二进制数算法[5]—跳跃式类二进制数算法[6]做分析, 该算法采用在标签上设置一个计数器来实现不用发送标签UID的方式实现防碰撞, 该算法虽然减少了每次标签发送的数据量, 但却是以阅读器的寻呼次数增加为代价的。

本文提出了一种改进的二进制树算法。改进的算法规定发生碰撞时, 阅读器发送一个Call (m, n) 命令, 使得标签UID从最高碰撞位开始的3bit UID被通过一种计算规则生成1字节的数据返回给阅读器。该数据包含了标签这3bit UID的具体值, 该值具有唯一性 (即标签当前3bit UID不同返回值不同) , 即便碰撞后阅读器依然能正确识别出该值, 并以此为索引寻呼, 这样就减少了阅读器的寻呼次数。随后, 通过仿真与其他改进二进制树算法对比, 证明了改进的算法在搜寻次数以及搜寻时间上相较另外两种改进二进制树算法的优势。

1 几种常用改进的二进制树算法

在二进制算法中, 为了能使阅读器准确识别标签碰撞位的位置, 通常采用Manchester编码。普通的类二进制搜索算法, 例如返回类二进制树算法, 通过标签的计数器来获取标签位的准确信息, 虽然让编码方式更加自由, 但是增加了软硬件的负担, 因此改进算法采用Manchester编码识别碰撞位的准确位置[7]。

根据标签的标准通信协议规定的传输速度为12.5μs/bit, 则算法的识别时间T与搜寻过程中需要传送的比特位呈正比。在信号传输过程中, 为了便于互相区分, 必须在信息的头部和尾部各加上一个“NULL” (占用5个比特位) 。当标签返回信息时, 阅读器需要占用1个bit周期来校验接收到的数据是否存在错误。如果收到的数据没有出现碰撞, 则阅读器还需要2个bit周期的时间记录标签的UID信息。下面对常见的两种改进的二进制防碰撞算法进行分析。

1.1 返回二进制树算法

返回二进制树算法特点是:在进行搜索的过程中阅读器依次记录下标签发生冲突节点即父节点, 直到完成一个标签的识别。然后返回上一级父节点继续识别其他的标签, 而不是像二进制树算法返回到根节点重新进行识别。因此返回二进制树算法主要是通过减少阅读器对标签的搜寻次数来减少阅读器的搜寻时间。

对返回二进制树算法[4], 根据文献[4]可知, 假设阅读器范围内有m个UID长为n bit的标签。

则阅读器的寻呼次数为CDBS=2×m-1。

由于返回二进制树算法的命令只有Rq () 则寻呼时间为:

1.2 跳跃类二进制树算法

使用跳跃类二进制树算法阅读器每次只接收l bit的数据, 阅读器就不需要对所有标签进行同步, 因此编码方式更加自由, 实现起来更加容易。跳跃式二进制防碰撞算法的搜寻时间与阅读器范围的标签个数和标签的位数成正比, 假设阅读器范围内存在n个UID为m bit的标签时此算法的搜寻次数C=0.65×m×n次。寻呼次数太高, 导致算法的识别效率较低。

对跳跃式类二进制树算法[6], 由文献[6]可知, 搜寻时间为:

1.3 返回式类二进制算法

该算法是基于类二进制算法的基础上提出需要标签内部的一个碰撞计数器collion_count[]用于记录碰撞位父节点的位置。将冲突位1的标签的collion_count[]值加1, 并以collion_count[]和标签位数作为寻呼标准, 相对于类二进制算法成功地减少寻呼次数。

由文献[1]可知, 该算法的阅读器寻呼次数为:

寻呼时间为

2 改进的二进制树算法

改进的二进制树算法, 如返回二进制树算法每次都需要传送标签的UID, 因此冗余信息比较多。从而使得算法的搜寻时间比较长。改进的类二进制树算法, 如跳跃式类二进制算法虽然减少了标签与阅读器每次交互需传输的数据量, 但却是以增加阅读器的寻呼次数为代价的。

2.1 改进算法思想简介

改进的防碰撞算法, 都是基于两方面的事实来提高算法的性能, 即一是减少标签和阅读器每次交互所需传输的数据, 二是减少第一次寻呼以后搜寻标签所需寻呼的次数。本算法主要是从不增加每个时隙传输数据的前提下, 减少阅读器对标签的寻呼次数。

本算法根据碰撞后Call (m, n) 命令要求计算的uid位数k (2位、3位或者4位) , 让标签预留2k字节的寄存器buffer[], 用来暂存标签通过计算生成的将要发送给阅读器的数据。本文以n=4为例 (具体原因见2.3节) , 首先对改进算法需要用到的一些命令做简介。命令的具体用法参见2.2节。

Rq (u) —UID前几位与u相同的标签将其剩余部分的UID发送该阅读器。

Call (m, n) —UID前几位与m相同的标签将其n～n+3位UID做运算, 运算方法见标签的程序执行要点, 将运算所得值存入Buffer[]中, 并发送给阅读器。

C语言应用在单片机编程时具有易于移植、维护等优点, 因此在实际应用中, 需要实现二进制防碰撞算法时, 一般都采用C语言编程。所以, 本文采用C语言的伪代码对算法执行过程中的核心程序做简要说明。

为了方便表述本算法, 首先对本文用到的一些C语言运算符以及运算目的做简介。

<< (>>) 表示:按位左移 (右移) , 移位后空余的最低 (高) 位由0补足。

规定:当发生碰撞时标签接收到Call (m, n) 命令时, 需要计算的uid位数为k位 (k=2, 3, 4) , 并且标签需要预留2k字节给寄存器buffer。且根据k取值不同, buffer长度及初值如表1所示。

规定:标签UID高位到低位依次为1—s位, 如图1所示。

运算目的如下:将标签的n～n+2位UID变成“不会碰撞”的值, “不会碰撞”就是在标签发生碰撞时, 阅读器也能正确识别出接收到的数据。标签通过如下计算得到的buffer值, buffer值的二进制表示形式有且仅有一位为1 (其余位都为0) 。

在算法的识别过程中标签需要执行操作的程序要点如下:

如果k=4则buffer初值为0x0001, 当n～n+3位值不同时标签计算得出的buffer值不同, 如表2所示。

在算法的识别过程中当发生碰撞时, 阅读器需要执行的操作的程序要点如下:

所以当发生碰撞时, 标签向阅读器发buffer值, 而不直接发送uid。如果有大于一个标签向阅读器发送其buffer的值, 则阅读器记录下收到的buffer值, 每个碰撞位对应一个Buffer值。将每个碰撞位依次分别置1, 其余位补0, 还原buffer值。下面举例说明这样计算的优势:假设阅读器范围内存在三张标签, 前3位uid分别为:1000, 1100, 1111。那么做运算后, 三个标签分别将buffer值为0x0100, 0x1000, 0x8000发送给阅读器, 曼彻斯特编码解码后阅读器将收到的数据为x00x 000x 0000 0000, 有三个碰撞位第1、4和第8位, 首先将第八位置1其余位补0则可得0000 0001 0000 0000, 同理得到第四位碰撞位对应的buffer值为0001 0000 0000 0000。第一位碰撞位对应的buffer值为1000 0000 0000 0000这样就还原了碰撞前的buffer值。阅读器知道了其范围内标签前4位uid值存在如下3中情况:1000, 1100, 1111, 并以此为索引依次寻呼。

2.2 改进算法流程

本文提出的改进算法的处理流程如图2所示。

为了清楚地介绍本算法, 假设阅读器范围内有10张uid长度为8 bit的标签, 标签uid值如表3所示。

根据图2所示算法流程, 表3所列10张标签的识别过程概述如下:

1) 所有进入阅读器范围内的标签都处于Unselect状态。阅读器发送Active () 命令激活阅读器范围内的所有标签, 使标签处于Ready状态。

2) 阅读器发送Request (all) 命令, 处于Ready状态的标签向阅读器发送其完整的UID, 此时阅读器接收到的数据为xxxx xxxx。

3) 由于接收到数据的最高碰撞在首位, 因此阅读器下发命令Call (, 1) , 所有收到命令的标签1～4 (1+3) 位做计算, 并向阅读器发送标签计算所得值。

4) 阅读器分析收到的数据x00x x0xx 0xx0 0x00, 分析知此时标签前三位UID值有8种情况, 0010 (0000 0000 0000 0100) , 0101 (00000000 0010 0000) , 0110 (0000 0000 0100 0000) , 1000 (0000 0001 00000000) , 1001 (0000 0010 0000 0000) , 1011 (0000 1000 0000 0000) , 1100 (0001 0000 0000 0000) , 1111 (1000 0000 0000 0000) 。阅读器发送Rq (0010) , 此时只有Tag6回复, 无碰撞, 正确识别Tag6。

5) 阅读器发送Rq (0101) , 此时只有Tag9回复, 无碰撞, 正确识别Tag9。

6) 阅读器发送Rq (0110) , 此时只有Tag8回复, 无碰撞, 正确识别Tag8。

7) 阅读器发送Rq (1000) , 此时只有Tag1回复, 无碰撞, 正确识别Tag1。

8) 阅读器发送Rq (1001) , 此时Tag4, Tag7, Tag10响应, 阅读器收到xxxx, 发生碰撞, 表示uid前4位为1001的标签不止一张, 需要继续寻呼标签的接下来的4位uid, 即5～8位uid才能识别本组标签。

9) 阅读器向标签发送Call (1001, 5) 表示:UID前4位为1001的标签将5～8 (5+3) 位做计算, 然后向阅读器发送标签计算所得值。

10) 阅读器分析收到的数据00x0 000x 0000 x000, 分析知此时前四位为1001的标签5～8位值有如下3种情况:0011 (0000 0000 0000 1000) , 1000 (0000 0001 0000 0000) , 1101 (00100000 0000 0000) 。阅读器发送Rq (1001 0011) , 此时只有Tag4回复, 无碰撞, 正确识别Tag4。

11) 阅读器发送Rq (1001 1000) , 此时只有Tag10回复, 无碰撞, 正确识别Tag10。

12) 阅读器发送Rq (1001 1101) , 此时只有Tag7回复, 无碰撞, 正确识别Tag7。

13) 阅读器发送Rq (1011) , 此时只有Tag5回复, 无碰撞, 正确识别Tag5。

14) 返回上一级阅读器发送Rq (1100) , 此时只有Tag2回复, 无碰撞, 正确识别Tag2。

15) 阅读器发送Rq (1111) , 此时只有Tag3回复, 无碰撞, 正确识别Tag3, 阅读器范围内所有标签识别完毕, 本次识别结束。

16) 使用Active () 命令激活标签进入下次识别。

改进算法具体实现标签的识别过程与结果如表4所示。

2.3 仿真结果以及分析

假设阅读器范围内有m个uid长度为n bit的标签。当标签收到Call命令时, 标签每次用k bit做计算, 存到长度为2kbi的buffer中。

由文献[4]可知, 对于返回二进制树算法, 要识别m (m>2) 个标签, 则阅读器需要寻呼次数为2×m-1次, 其中m-1次寻呼后收到的数据发生碰撞, m次寻呼后正确识别标签。

本文提出的算法, 根据每次碰撞时标签最高碰撞位接下来的k bit作为一组运算后, 发送阅读器, 阅读器按k位来寻呼, 而不是像返回二进制树算法以最高碰撞位 (即一位) 做寻呼。因此, 发生碰撞次数概率为返回二进制树算法的1/k, 但是改进的算法当发生碰撞时会产生一次额外的Call命令, 因此改进算法的寻呼次数为:

{根据上式可以得出rk与k成反比, 因此可以得出k越大, 算法在阅读器寻呼次数上优势越大。

下面针对改进算法的寻呼时间与返回二进制树算法的识别时间做推导, 算法的识别时间T与搜寻过程中需要传送的比特位呈正比, 因此此处仅对算法识别过程中传输的总bit位做推导, 而不考虑校验记录uid所需要的时间。假设改进的算法以及返回二进制树算法在一次搜寻过程中需要传输的总比特位分别为bitNBBS和bitBBS。

{根据上式可知bitNBBS与k (k≥2) 成正比因此, 虽然随着k的增加阅读器总寻呼次数减少, 但是需要传输的字节数却在增加。这是由于随着k的增加阅读器每次发送Call命令需要传输的字节数呈指数增加。不仅如此, 随着k的增加标签需要预留的buffer字节数也增加, 同时就增加了标签的硬件负担。给实际应用造成了困难, 因此, k值并不是越大越好。

结合实际考虑:由于标签uid长度普遍为2nbyte=8×2nbi (n≥0) , 如基于14443-A协议的标签uid长度为4 byte。在标签预留可供用户使用的寄存器大于两个字节时, 标签建议k值取4。因为, 当k=4时, 只需要使用标签的2字节的寄存器, 并且运算都是以移位运算为主, 不会给标签造成太大的负担, 同时效率也得到提高。但是, 当k>4时, 标签则要预留2k/8字节的寄存器, 例如k=5时, 则需要预留4字节;k=6时, 则需要预留8字节, 对标签负担就加重了。因此, 本文建议k取值为4。

以阅读器范围内标签个数为m个 (x轴) , 阅读器寻呼次数为y次 (y轴) , 标签长度n=8 bit, k=2, 3, 4反复运行10次求平均值。阅读器搜寻时间标签个数关系如图3所示。

注: (1) 返回二进制树算法; (2) k=2, 时改进算法; (3) k=3时, 改进算法; (4) k=4时, 改进算法

阅读器的搜寻时间直接决定算法的优劣, 从图3可以直观地看出随着标签个数的增加改进算法在识别时间上, 相对于其他两种改进的二进制树算法优势更加明显。由表5改进算法与其它两种二进制树算法搜寻时间比较表可以定量地看出改进算法在搜寻时间上的优势, 例如:在标签个数为250个时改进算法在k=4时相对于返回二进制树算法时间节省率将达到29.86%。

3 结语

本文首先对常用的改进二进制树简介, 然后提出了一种改进的二进制树算法, 该算法在动态二进制树算法的基础上通过阅读器发送命令让标签做计算, 并将计算所得值发送给阅读器, 通过标签返回的值, 阅读器清楚地知道标签的当前k (k=2, 3, 4, 在实际应用中建议取值为4) 位uid值, 从而减少阅读器的寻呼次数, 并最终减少了阅读器的搜寻时间。并通过仿真证明了, 改进算法相比于动态二进制树算法在阅读器寻呼次数上有所减少。相比于动态二进制树算法和跳跃类二进制树算法在阅读器寻呼时间上的优势。特别在标签数越多时算法的优势越明显, 但是本算法需要标签支持一个可供用户使用的一个字节的寄存器Buffer[], 相对来说就增加了标签的硬件负担。因此, 本算法适用于对算法识别速度要求高, 并且标签支持一个可供用户使用的一个字节的寄存器适的情况下的RFID系统下大规模标签的识别。

参考文献

[1]张航, 唐明浩, 程晖.改进的返回二进制防碰撞算法[J].计算机工程与应用, 2011, 47 (25) :208-211.

[2]夏志国, 何怡刚, 侯周国.一种二进制树位检测的标签防碰撞算法[J].计算机工程与应用, 2010, 46 (20) :245-248.

[3]Lee Suryun, Joo Sungdon, Lee Chaewoo.An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification[C]//Proceeding of the 2nd Annual International Conference on Mobile and Ubiquitous Systems, 2005.

[4]徐圆圆, 曾隽芳, 刘禹.基于A loha算法的帧长及分组数改进研究[J].计算机应用, 2008, 28 (3) :588-590.

[5]Joe I, Lee J.A novel anti-collision algorithm with optimal frame size for RFID system[C]//Proc.of 5th IEEE International Conference on Software Engineering Research, Management and Applications, 2007:424-428.

[6]陶云聪.RFID系统多标签防碰撞算法研究[D].重庆:重庆大学, 2010.

[7]何晓桃, 郑文丰.RFID中基于二分叠加的二进制防碰撞算法[J].华南师范大学学报:自然科学版, 2011 (3) .

[8]张琦.基于TDMA的阅读器控制防碰撞算法研究[D].合肥:合肥工业大学, 2007.

二进制树算法篇5

无线局域网协议是以IEEE 802.11[1]标准为基础的。该标准定义了一个信道接入控制 (MAC) 子层和3个物理 (PHY) 层。IEEE 802.11协议的目标是构建一个能够提供与有线网络类似服务的无线网络。但因带宽的有限性, 提高信道利用率就成为关键。

网络仿真技术[2], 即网络行为的模拟, 通过数学和统计方法建立模型 (包括网络设备、协议和链路) , 模拟网络中传输的数据, 获得网络优化设计时其性能数据的一种新技术。通过该技术可发现网络行为中出现的异常情况, 并对网络优化的可行性等进行验证。

相对于有线网络, WLAN中较高的误码率和“隐藏终端“ (Hidden Terminal) 等问题[7]是WLAN中常见的问题。此外, 一个站点为了能检测到冲突而不能够监听到它自己的传输, 在无限网络中, 难以进行载波监听[3]。本文在OPNET模拟仿真的基础上深入分析得出:利用RTS/CTS访问方式来解决“隐藏终端”问题;在活动节点数多且误码率高的情况下启用拆分门限功能。由于在在二进制退避算法 (binary backoff algorithm) 中, 竞争窗口在初始化时为一固定值。本文对二进制退避算法进行改进, 即计算时隙利用率来评估共享信道的竞争状况来动态调整竞争窗口的大小。通过仿真实验, 结果表明, 该算法能够有效降低网络负载和冲突, 并提高网络接入率。

1 DCF模式简介

DCF是IEEE 802.11M AC层协议中最重要与最基本的接入模式, 它采用CSMA/CA与二进指数退避机制来支持用户终端的异步数据通信。它试图让各个终端通过竞争来公平和高效的利用无线信道资源。RTS/CTS访问方式和基本访问方式是DCF的两种接入方式。

1.1 DCF的基本访问方式

在DCF方式中, 发送节点侦听到无线信道连续空闲时间达到DIFS后, 发送数据帧, 为了增强对异步业务传输的可靠性, DCF使用MAC层确认机制, 接收节点检验所收到的数据帧的循环冗余校验码 (CRC, Cyclic Redundancy Code) , 如果正确, 则在等待SIFS间隔后向发送节点发送一个ACK帧, 以表明已经成功的接收到该数据帧。如果在一定的时间内, 没有收到返回ACK帧, 发送节点就认为本次传输失败, 需要重传该数据帧。

1.2 DCF的RTS/CTS访问方式

“隐藏终端“ (Hidden Terminal) 在WLAN中经常出现, 为了解决这个问题, DCF利用RTS和CTS两个控制帧进行信道预留。RTS/CTS访问模式的具体过程可描述如下:

1) 在等待了DIFS (再加上随机退避时间) 后, 发送节点首先发送RTS控制帧。收到RTS的每个节点都根据持续时间域 (Duration Field) 来设置它的NAV (Network Allocation Vector) 。NAV制定了节点可以试图访问介质的最早时间点。

2) 如果传输数据的接收节点收到RTS, 在等待SIFS后, 需要进行应答, 通过CTS帧来实现。CTS帧也包括持续时间域, 而且所有接到这个CTS的节点必须再次调整他们的NAV。

3) 最后, 在SIFS间隔后, 发送节点可发送数据帧。接收节点在接收到数据帧后再等待SIFS间隔, 用ACK确认。

1.3 二进制退避算法

在MAC层协议中, 将重点考虑退避算法, 该算法在以下几方面具有重要作用:节点数据发送冲突分解效果较好;节点公平的接入到网络以及信道利用率的提高等等。网络中任一节点在发送数据过程中发生冲突, 将等待一定的时延后继续发送, 其中时延通常是指数增长, 一直增加到退避时间间隔的最大值CWmax;相反, 若节点数据顺利发送, 未发生冲突, 退避时间间隔将达到最小CWmin。二进制退避算法描述如下:

Step 1网络中节点先要确定信道的状态 (忙或闲) , 在进行发送数据, 通过调用载波监听机制进行判断, 在信道状态闲时, 发送数据;若为忙状态, 将继续监听, 直到闲状态才继续发送数据。

Step 2信道为闲状态时, 同时满足以下条件, 即连续空闲时间为DIFS长度, 进行向目的节点发生数据。节点数据发送过程中, 并不马上发生, 而是增加一个退避过程, 起到避免冲突发生的作用。

退避时间 (Backoff Time) 随机产生, 在退避计数器中存入产生得随机Backoff Time。Backoff Time由下面的公式1计算得到。Backoff Time产生的过程与计数器中是否有值相关, 若存在一个非零值, 将不会产生随机退避时间。

其中, Random () 是随机整数, 均匀分布在

[0, CW]范围内, CW (Contention Window) 竞争窗口为一整数值, 满足条件CWmin<=CW<=CWmax, CWmin为最小竞争窗口, CWmax最大竞争窗口, aSlotTime[3]表示一个时隙的实际长度。

Step 3网络中一个节点执行退避过程时, 如果侦听到信道空闲时间达到一个时隙, 则将Backoff Time计数器减1;若信道处于忙状态, Backoff Time计数器将处于冻结状态, 退避过程因而将会停止, 等到侦听信道状态再次为空闲, 进行进行退避过程, 计数器继续-1。该节点在计数器值递减到零时, 进行数据发送。标准IEEE802.11协议的实现详见4.3节的进程模型。

2 自适应二进制退避算法[4,5]

由上面的分析可以得出:

1) 网络中的节点发送数据产生冲突的概率随着节点数的增加而增加, 随之也会影响CW, 也会增大。在DCF的协议中, CW一般都是从由物理层决定的CWmin, 并且增加方式按照指数形式增加。当网络节点数多的情况下发送数据帧时, 冲突次数增加, 将会在一定程度上浪费无线信道, 造成节点所在网络性能的降低。因此, 需要对上述提到的指数增长方式进行适当修改。

2) 同时, 根据标准DCF协议, 网络节点数据重发次数达到上限或成功后, 设置CW=CWmin。因为网络节点数据的成功发送并不能认为网络节点间的冲突概率已经最小, 或者冲突概率减小, CW重置为最小的机制将不在适用。鉴于此, 提出了CW的慢递减机制, 即网络节点数据发送成功后修改CW的重置机制。此外, 还可以通过对不同等级的业务, CW按不同的算法增长或递减, 从而能够实现提供不同优先级的服务, 将会提高网络运行的性能。

3) CW介于CWmin和CWmax之间, 节点发送数据发生冲突时, CW将一直朝着CWmax以指数形式增加。标准DCF中是CW固定的, 跳频方式CWmin为15, 直接序列扩频方式为31。

网络中节点少, 需要进行长时间的等待过程, 而当节点数增加时, 节点发送数据产生传统的概率也随着增多, 进而影响WLAN的性能。可以得出CW与网络中的节点数存在一定的关系。因而, 为了使WLAN的性能达到最优, 初始化CW值的设置需要针对网络中的节点数的多少进行适当调整。

基于上述分析, 本文提出了自适应退避机制, 其核心思想是:利用计算时隙利用率来评估共享信道的竞争状况, 从而解决上面提到的问题。当检测到竞争水平高时, 这表明如果一个站点发送一个数据包就会产生碰撞。此时, 该算法就会触发一个虚拟碰撞过程并且扮演着退避角色, 以此来代替发送一个数据包。这样, 碰撞就有可能避免, 可以提高无线信道的利用率、网络的吞吐率以及网络的公平性。在标准IEEE802.11协议的基础上, 增加PT_BACKOFF和PT_TEST状态, 改进算法如下:

有限状态机PT_BACKOFF状态:

有限状态机PT_TEST状态:

有限状态机BKOFF_NEEDED状态:

3 自适应退避算法仿真

OPNET[6,7]提供了良好的开发接口, 能够根据网络环境和协议的需要建造不同的仿真模型, 其仿真模型分三层来实现, 从上到下分别为:网络层、节点层和进程模型。网络层, 反映网络拓扑结构;由相应的协议模型构成的节点层, 反映设备特性;进程模型以有限状态机来描述。仿真模型和实际的网络、设备、协议一一对应, 网络相关特性也被全面反映。

3.1 建立网络模型

本文建立了图1的独立基本服务子集[7]的网络模型, 用于比较二进制退避算法和自适应退避算法。

3.2 建立节点模型

Wlan_wkstn节点由source、sink、wlan_mak_intf及wireless_lan_mac四个处理器组成。引用的进程模型分别为bursty_source、sink、wlan_mac_interface、wlan_mac。其中wlan_mac进程对应的源文件是wlan_mac_pr.c。该模块结构简单, 仅包含3层, 顶层的source和sink概括了OSI的网络层以上的部分, 这为单独研究MAC层提供了极大的方便。

3.3 建立进程模型

根据IEEE802.11协议的二进制退避机制, 共设计了9个有限状态机以完成网络架构、DCF模式下的CSMA/CA信道竞争机制以及RTS/CTS的协调功能等, 有限状态机如图2所示。

3.4 自适应退避算法仿真结果及分析

修改wlan_mac.pr.c文件后, 构建自组织网络架构, 站点分别为10、22、60个, 其他参数设置如表1所示。

仿真结果如图3所示。

仿真结果表明:随着活动节点数由10、22到60个的增加, 发送数据的冲突概率在增大, 这时需要较大的初始化活动窗口, 自适应改进算法中CCW=CWmin*2+1, 这是根据信道的利用率来一次调整就可以完成数据的发送, 而DCF规定竞争窗口只能从最小值以指数形式增大, 节点需要几次冲突后才能发送数据, 这样明显的降低了网络负载;标准DCF协议规定, 发送成功或达到重传次数限制后, 将CW重置为CWmin, 然而一次成功传送并不能断定网络中的冲突概率已经减小, 所以不应该将重置为最小, 而自适应改进算法是根据信道利用率以及CCW的大小来判断是否重置CW, 这样可以降低接入延时。

图3 (a) 表明, 自适应退避算法较标准的二进制退避算法在网络负载降低大约20%;活动节点数的增加至22个, 见图3 (b) , 负载降低大约30%;活动节点数的增加至60个, 见图3 (c) , 负载降低大约50%。由此可见自适应退避算法较标准二进制退避算法降低了网络负载。

4 结束语

通过对IEEE802.11协议在OPNET上的仿真实现, 分析对比各种参数对网络性能的影响, 可以得出以下结论:1) 采用自适应退避算法, 能够有效的降低冲突, 具有一定的应用价值;2) OPNET在网络优化、协议验证、设备优化升级等方面为我们提供方便, 当前针对OPNET的研究还较少, 对网络仿真的方法有一定的探索和实践意义。

参考文献

[1]IEEE Standard forW irelessLANMedium Access Control (MAC) and Physical Layer (PHY) Specifications[Z].ANSI/IEEE STD802.11, 1999Edition, New York, 1999.

[2]王文博.OPNETModeler与网络仿真[M].北京:人民邮电出版社, 2003.

[3]L.Bononi, M.Conti, and L.Donatiello, “Design and performance evaluation of a distributed contention control (DCC) mechanism for IEEE802.11wireless local area networks, ”in Proceedings of First ACM International Workshop on Wireless Mobile Multimedia, 1998, 10:59-67.

[4]OPNET Technologies, Inc., “Wireless LAN model deccription, ”http://www.opnet.com/products/library/WLAN_Model_Guide1.pdf.

[5]F.Cali, M.Conti, and E.Gregori, “Dynamic tuning of the IEEE802.11protocol to achieve a theoretical throughput limit, ”IEEE/ACM Transactions on Networking, 2000, 8 (6) :785-799.

[6]陈敏.OPNET网络仿真[M].北京:清华大学出版社, 2004.

二进制树算法篇6

粒子群优化算法是由Kennedy和Eberhart[1,2]在1995年提出的一种新的群体智能计算技术,是在鸟群、鱼群和人类社会行为规律的启发下提出来的,用于复杂优化问题的求解。由于算法收敛的速度快、设置参数少、实现简单,受到了学者和工程技术人员的研究兴趣。现在,粒子群优化算法在函数优化、神经网络训练、模式分类、模糊系统控制以及其它工程领域都得到了广泛的应用。

目前,有关粒子群优化算法的研究主要集中在以下三个方面:粒子群优化算法的运行机理分析[3,4];粒子群优化算法与其它进化算法的融合[5,6];粒子群优化算法在新领域中的应用[7,8]。由于标准粒子群优化算法主要适用于求解连续空间的优化问题,如何将其改进并应用于求解离散空间的优化问题,特别是NP问题中的优化问题,是粒子群优化算法的一个改进与应用研究方向。Kennedy和Eberhart在1997年首先提出了粒子群优化算法的改进形式——二进制粒子群优化算法(Binary Particle Swarm Optimization,BPSO)[9],并成功将其应用于求解离散优化问题。但由于BPSO本身存在一定的缺陷,使种群多样性和全局收敛性大大降低,影响了算法的性能[10]。为克服这一不足,一些专家学者在BPSO的基础上提出了一些改进算法[11,12,13],取得了不错的效果。在以上研究成果的启发下,本文在BPSO的基础上提出一种改进。利用种群个体极值的平均信息和粒子的个体极值来决定粒子当前值的取值概率,使粒子利用更多的信息来调节自身的行为。仿真实验表明本文的改进有利于提高算法的性能,实验结果要优于BPSO和一些改进的二进制粒子群优化算法。

1粒子群优化算法

粒子群优化算法是一种基于种群的优化算法,种群称为粒子群,粒子群中的个体称为粒子。设有N个粒子组成一个群体,其中第i个粒子表示为一个D维的向量xi=(xi1,xi2,…,xiD),i=1,2,…,N,即第i个粒子在D维的搜索空间中的位置是xi。第i个粒子的飞行速度也是一个D维的向量,记为vi=(vi1,vi2,…,viD),记第i个粒子迄今为止搜索到的个体极值为pi=(pi1,pi2,…,piD),整个种群迄今为止搜索到的全局极值为pg=(pg1,pg2,…,pgD),粒子群优化算法采用下列公式对粒子操作:

vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid) (1)

$x_{i d} = x_{i d} + v_{i d} (2)$

其中i=1,2,…,N,d=1,2,…,D,w表示惯性权重,c1和c2表示学习因子,r1和r2是[0,1]上均匀分布的随机数,每一维粒子的速度都被限制在一个最大速度vmax(vmax>0)之间,若vi>vmax时,vi=vmax;若vi<-vmax时,vi=-vmax。

2二进制粒子群优化算法

由于粒子群优化算法主要适用于求解连续空间的优化问题,对于一些采用二进制编码的问题,例如0—1整数规划,粒子群优化算法在粒子进行速度和位置更新后产生的位置分量xid不一定是0或1,使得粒子群优化算法无法对其进行求解。Kennedy和Eberhart在1997年专门针对0—1整数规划问题给出BPSO,在BPSO中,每个位置分量xid要么取1,要么取0,因此速度分量vid不再表示位置变化的大小,它反映的是xid取1的概率。为了使概率值在[0,1]之间,BPSO采用logistic变换对vid进行处理。BPSO采用下列公式对粒子操作:

$\begin{array}{l} v_{i d} = w v_{i d} + c_{1} r_{1} (p_{i d} - x_{i d}) + c_{2} r_{2} (p_{g d} - x_{i d}) (3) \\ x_{i d} = {\begin{cases} 0 ‚ r \geq 1 / (1 + \exp (- v_{i d})) \\ 1 ‚ r < 1 / (1 + \exp (- v_{i d})) \end{cases} (4) \end{array}$

式(4)中r为[0,1]上均匀分布的随机数。

3利用种群平均信息的二进制粒子群优化算法

文献[4]指出,BPSO继续沿用标准粒子群优化算法的表达形式来求取值概率的必要性并不是很强,而且采用的logistic函数的主要功能是限界,并没用充分的理由。为此,文献[12]提出了一个改进的二进制粒子群优化算法版本(IBPSO),利用种群极值和个体极值来决定粒子当前值的取值概率,取消粒子当前值对下一步迭代的影响,仿真实验取得了比BPSO好的效果。然而,在IBPSO中,每个粒子获得的是个体极值和种群极值的信息,忽略了种群中其它粒子的个体极值信息。E. O. Wilson[14]论证:至少在理论上,在群体搜索食物的过程中,群体中的每个个体可以从群体的新发现和群体中所有其它个体的经验中受益。受此启发,在BPSO和文献[12]的基础上本文提出一种利用种群平均信息的二进制粒子群优化算法,算法利用种群个体极值的平均信息 $p_{v d} = \frac{1}{Ν} \sum_{i = 1}^{Ν} p_{i d}$ 和粒子的个体极值来决定粒子当前值的取值概率。本文这样做的理由是种群个体极值的平均信息和粒子的个体极值本身包含了历次迭代中粒子的遗传信息,可以使粒子利用更多的信息来调节自身的行为。为了避免因为过度参考而使算法陷入局部极值,可以通过设定pid和pvd判断的可信度来解决。在此,我们采用文献[12]提出的两个假定:

1)用xid表示优化的极值点,由于优化过程中xid的真值是未知的,故假定先验概率:

$Ρ (x_{i d} = 0) = Ρ (x_{i d} = 1) = 0.5 。$

2)在寻找最优值的过程中,假定pid和pvd对最佳值的判定是相互独立的。

由pvd的计算公式可知,pvd未必取0或1,我们可以先做如下转换:

$p^{'}_{v d} = {\begin{cases} 0 ‚ p_{v d} < 0.5 \\ 1 ‚ p_{v d} \geq 0.5 。 \end{cases}$

这样做的理由是如果种群中有一半以上粒子的个体极值pid取1,则pvd≥0.5,此时令p′vd=1;如果种群中有不足一半以上粒子的个体极值pid取1,则pvd<0.5,此时令p′vd=0,这符合日常生活中人们做决策时采用的“少数服从多数”原则。

记pid作出正确判定的概率为P1,p′vd作出正确判定的概率为P2,利用Bayes公式可得

$\begin{array}{l} Ρ (x_{i d} = 1 | p^{'}_{v d} = 1, p_{i d} = 1) = \\ \frac{Ρ_{1} Ρ_{2}}{Ρ_{1} Ρ_{2} + (1 - Ρ_{1}) (1 - Ρ_{2})} = α ‚ \\ Ρ (x_{i d} = 1 | p^{'}_{v d} = 0, p_{i d} = 0) = \\ \frac{(1 - Ρ_{1}) (1 - Ρ_{2})}{Ρ_{1} Ρ_{2} + (1 - Ρ_{1}) (1 - Ρ_{2})} = 1 - α ‚ \end{array}$

$\begin{array}{l} Ρ (x_{i d} = 1 | p^{'}_{v d} = 1, p_{i d} = 0) = \\ \frac{(1 - Ρ_{2}) Ρ_{1}}{(1 - Ρ_{1}) Ρ_{2} + (1 - Ρ_{2}) Ρ_{1}} = β ‚ \end{array}$

$\begin{array}{l} Ρ (x_{i d} = 1 | p^{'}_{v d} = 0, p_{i d} = 1) = \\ \frac{(1 - Ρ_{1}) Ρ_{2}}{(1 - Ρ_{1}) Ρ_{2} + (1 - Ρ_{2}) Ρ_{1}} = 1 - β ‚ \end{array}$

这是粒子决策的依据。

在本文中,由于pid和pvd的特殊性,假定它们发现最优值的概率应该超过平均值,即P1>0.5,P2>0.5。其次,为了鼓励粒子进行分散搜索,避免算法陷入局部极小,令P1>P2。下面以求函数最大值为例给出利用种群平均信息的二进制粒子群优化算法的形式化描述:

4函数优化问题的仿真实验

为了验证本文提出算法的性能,将本文算法与BPSO和IBPSO进行对比实验,实验采用文献[12]引用的De Jong精心设计的一个专门用于测试演化算法性能的测试集中的4个函数来求其最大值,在每个函数上各运行20次,3种算法的粒子数目都设为20,迭代次数均为2 000,在本文算法中,P1=0.9,P2=0.6。表1给出算法在4个测试函数上的计算结果,包括4个函数的理论最优值,3种算法分别发现的平均值以及在20次运算中达到理论最优值的次数。

从表1可以看出,3种算法在4个测试函数上都能找到理论最优值,但本文算法相对于BPSO和IBPSO找到理论最优值的次数要多,且20次测试的平均值也要优于BPSO和IBPSO,表明本文算法在函数优化问题上的性能较BPSO和IBPSO有了较大程度的提高。

50—1背包问题上的仿真实验

5.10—1背包问题描述

已知n个重量和价值分别为wj>0和cj>0(j=1,2…n)的物品,背包的容量假设为C>0,如何选择哪些物品装入背包可使在背包的容量限制之内所装物品的价值最大。引入变量xj,当物品j被选择装入时,xj=1;否则,xj=0。则该问题的数学模型为:

$\begin{array}{l} m a x f (x_{1}, x_{2}, \dots, x_{n}) = \sum_{j = 1}^{n} x_{j} c_{j}, (5) \\ s . t . {\begin{cases} \sum_{j = 1}^{n} w_{j} x_{j} \leq C \\ x_{j} \in {0, 1} j = 1, 2, \dots, n \end{cases} (6) \end{array}$

5.2求解0—1背包问题的二进制差异演化算法

采用本文提出的算法求解背包问题与对函数优化问题的求解过程类似,唯一的不同在于求解背包问题时在迭代过程中形成的新粒子未必满足约束条件,因此需要对其进行调整,在这里我们引入了局部搜索机制—贪婪算法,使用启发式修正算子,用来保证粒子满足约束条件,同时在保证粒子满足约束条件的前提下尽量增加其适应值。若粒子不满足约束条件,按物品j的价值密度ρj=cj/wj,(j=1,2,…,n)由小到大的方向将xj=1变为xj=0,直到将不满足约束条件的粒子变成满足约束条件;若粒子满足约束条件,在保证满足约束条件的前提下,按ρj由大到小的方向将xj=0变成xj=1,尽量增加其适应值,这是对个体质量的改良。虽然增加了计算开销,但考虑到它使得搜索有一定的导向,而不再盲目,这点开销还是值得的。

5.3测试结果

我们选用文献[11]、[12]和[13]共同采用的一个算例来进行测试,该算例共有50个物体,最优值为3 103,其原始数据见文献[15]。实验时,本文算法粒子个数为50,最大迭代次数为50,P1=0.9,P2=0.6,我们一共计算1 000次,并将求解结果与上述文献进行对比,其中文献[11]对此算例计算50次,文献[12]对此算例计算1 000次,文献[13]对此算例从迭代100代到1 000代各运行50次,为方便比较,本文仅选取其迭代200代的情况。计算结果如表2所示,本文算法的平均收敛情况如图1所示。

从表2可以看出,本文算法相对于一些二进制粒子群优化算法的改进形式要优秀的多,虽然文献[11]每次迭代都可以找到最优值,但其平均进化代数为166,而本文算法在种群规模不及其1/3的情况下每次迭代页都可以找到最优值,且平均进化代数仅为16,不及文献[11]的1/10,充分表明了本文算法的优越性。此外,从图1也可以看出,本文算法拥有较快的收敛速度,可以很快找到问题的最优解。

6结束语

为解决应用粒子群优化算法求解二进制编码的问题,在BPSO的基础上提出了利用种群平均信息的二进制粒子群优化算法,新算法继承了标准粒子群优化算法收敛速度快的特点,同时算法仅含有两个参数,形式简单,易于实现。仿真实验表明,相对于BPSO和其它一些二进制粒子群优化算法的改进形式,在相同条件下本文算法可以取得更好的效果。

二进制树算法篇7

多址访问 (multi-access) 技术是一种多用户共享公共信道的接入控制协议, 它主要遵循固定分配、按需分配和随机争用三种通信协议模型。其中随机争用模型在一定条件下作为有效利用信道资源、减小转接时延的技术而被广泛应用[1,2]。而时隙ALOHA是其典型的随机争用系统模型。在时隙式ALOHA系统中, 公共信道被离散为若干固定长度的时间片, 称为时隙 (slot) 。用户终端在每个时隙的起始处开始发送数据包, 且一个时隙内仅可以传输一个数据包。如果在某个时隙两个及两个以上用户同时申请发送信息时, 冲突就产生了。卷入冲突的用户终端需要按照一定的冲突分解规则在后续的时隙中重发信息, 直到所有冲突用户终端数据发送成功。

截断二进制指数后退冲突分解基本算法[3]描述:若用τ表示终端的退避延时值, 算法可用公式 (1) 所描述:

公式 (1) 中, τ是与系统有关的时间常数, R是以其地址为初始值产生的一个随机数。当系统发生冲突时, 发生冲突的终端必须在算法每次提供的时隙窗口范围内随机地选择一个值, 这个随机值就是该终端在重发信息前必须“放过”的时隙数。为了提高冲突分解效率, 本文提出了一种基于初始冲突终端数的多少动态设置初始窗口大小的理论, 但由于它无法准确知道冲突终端数, 还有就是它所设定的初始窗口大小导致开始分解时很容易产生冲突。

2 截断二进制指数后退冲突分解算法的改进:

针对以上问题, 本文提出了用概率的方法预测在某个时间片的冲突终端数, 以及根据预测冲突终端数确定所需的初始窗口数。

2.1 预测冲突终端数

由于一个多址访问公共信道中很难知道冲突时的冲突终端数, 本文采用该信道的在线终端数和终端的平均通信概率来预测在某一时隙的可能冲突终端数。实验中我们分别取发送信号概率p为0.005、0.01和0.015, 在计算机上对不同的在线终端数N下进行10000次实验, 设M代表在某个时间片中N个在线终端数所产生的平均冲突终端数。本实验结果取10000次实验的平均值。

2.2 动态冲突分解算法

根据上小节预测出冲突端口数M后, 本文针对冲突分解可能次数多的问题, 提出了一种动态的冲突分解算法, 此算法与基本算法的主要区别在于改进算法是根据预测冲突终端数M动态地设置初始窗口数W。而不像基本算法那样, 无论冲突终端数为多少, 初始窗口数始终为2。根据改进算法的规则, 该算法的初

始窗口数如公式 (2) 所示:

其中M为预测冲突终端数, W为在M个冲突终端数下设定的初始窗口数。根据公式 (2) , 我们可以得出预测冲突终端数M和初始窗口数W的关系如表1所示:

即假设公共信道在线终端数为180时, 每个终端发送信号的概率为0.005时, 则可以根据实验结果预测出约有107个冲突终端, 因此我们可以根据表1取初始窗口数为128个时隙。

3 仿真分析

为了验证本文提出的动态设置初始窗口数的算法的有效性, 我们进行了仿真实验。实验中基于两个参数进行, 即冲突分解成功时的分解次数和冲突分解成功所需的时隙值。本实验结果为取10000次仿真的平均值。实验结果如表2所示:

通过实验我们可以清晰的知道当在线终端数不同且发送信号概率相同的情况下, 本文提出的改进算法所用的冲突分解成功所需次数全都小于基本算法的, 基本算法的参数随着在线终端数的增加而不断变大, 而改进算法所用的分解次数却变化很小, 基本在4次范围内都能成功分解;从分解成功所需的最大时隙值来看, 一开始, 两种算法所需的时隙值基本相等, 而随着在线终端数的不断增加, 改进算法的分解成功所需的时隙值越来越比基本算法的少, 对于不同的发送信号概率下有类似的结果。

这说明本文提出的改进的动态冲突分解算法更行之有效。

4 结束语

本文主要介绍了截断二进制指数后退冲突分解基本算法的改进方式与用概率的方法预测在某个时间片下在线终端数所产生的冲突终端数。基本算法的改进方式主要是根据冲突端口数来动态的设置初始窗口的大小。此种改进算法大大的减少了冲突分解成功所需的最大时隙值并且提高了冲突分解的效率。

参考文献

[1]RomR, SidiM.Multiple access protocols[M].Springer-Verlag, 1989.5-30.

[2]GULKOE.Tree-Based multi-access protocols where collision mul-tiplicities are known[J].IEEE Trans Commun, 1985, 33:999.

二进制树算法篇8

RFID系统主要由标签、阅读器及计算机系统三部分组成。每个标签拥有唯一的序列号ID。RFID系统中多个标签可能会处于同一阅读器识别范围内,当多个标签同时响应阅读器时会产生信号干扰,致使阅读器无法正确识别标签,也即发生了标签碰撞。碰撞导致了标签被漏读,因此必须采用防碰撞策略来避免碰撞发生,识别全部标签。

1 基于二进制RFID防碰撞算法

二进制防碰撞算法是将碰撞的标签分成左右两个子集,先查询左子集0,若没有碰撞,则正确识别标签,如若仍有碰撞就再继续进行分裂,分成00和01两个子集,依次类推,直到识别出左子集0中的全部标签,再按此步骤查询右子集1。

1.1 二进制树搜索(BS)算法

在BS算法中,阅读器查询的不是一个比特,而是一个比特前缀,只有标签与这个查询前缀相符的标签才能响应阅读器的命令。当只有一个标签响应的时候,阅读器可以成功识别标签,但有多个标签响应的时,发生碰撞。为了最简捷地实现二进制搜索算法,数据编码选用Machenster编码,依据其编码特点可以检测出碰撞位。

要从大量的标签中识别出唯一的标签,需要重复搜索操作。其识别的平均操作次数由阅读器范围内的标签总数n决定[1]:

利用BS算法可以较简单地解决碰撞问题,但随着标签数量的增多,重复操作的平均值很快增加。完成n个标签识别需要的总问询次数如下公式所示:

所有标签都需要发送完整的序列号来响应阅读器的问询。识别n个序列号为k位的标签,阅读器需要传输的总比特数为标签序列号长度与算法总搜索次数的乘积

1.2 动态二进制搜索(DBS)算法

上述BS算法虽然简单,但其不仅搜索范围较大,而且在阅读器问询和标签回应时序列号要全部传输。标签序列号可能长达12个字节,为了选择一个标签,所以数据传输量较大。因而DBS算法被提出。

如果研究阅读器和单个标签之间传输的数据,就可以得出以下结果。假设H为最高碰撞位,标签序列号长度为K。

⑴请求命令(H-1)~0位中不包含任何给标签的补充信息,因为各位总是被置为“1”。

⑵标签应答的序列号的K~H位不包含任何给阅读器的补充信息,因为这些位是阅读器已经给定的。

由于DBS与BS使用相似的搜索过程,故可以得出的DBS算法总搜索次数。

DBS算法识别标签时,首先要求作用范围内的所有标签都上传各自的序列号,n个标签的序列号总长度就是第一次上传的数据长度,即整个序列号长度作为传输比特数。阅读器识别搜索一次传输平均数据量为[2]

当阅读器使用DBS算法时,识别n个标签所需要传输的序列号总长度为

1.3 基于后退索引的二进制搜索(BBS)算法

BBS算法中,阅读器完成一个标签的识别后,返回上一次发生碰撞的节点[3],识别该节点的另外一个分枝,不断重复操作,直到把上一节点碰撞的标签识别完。其识别n个标签,阅读器共需问询2*n-1次。假设标签序列号长度为kbit,则在阅读器的发送的数据量为(2*n-1)*kbit。BBS的优点是减少了问询次数,而DBS的优点是减少了问询中参数长度,如果能将两者的优势结合,必能提高性能。该文提出了以下改进算法。

1.4 返回式动态二进制算法BDBS

下面以4个标签为例(10110011、10100011、10110010、11100011),首先引一条命令REQUEST命令,即REQUEST(ID(K~X),X),X为碰撞的最高位,其作用是让阅读器发送一个参数(标签的第K-H位)给区域内标签,序列号K~H位与之一致标签传输剩余的(H-1)~0位信息作为应答。阅读器完成一个标签的识别后,返回上一次发生碰撞的节点,识别该节点的另外一个分枝,不断重复操作,直到把上一节点碰撞的标签识别完。算法的执行过程如下:

第①步,阅读器发送REQUEST(NUL,8),处于阅读器作用范围的所有标签都返回其ID给阅读器,解码数据为1X1X001X,碰撞最高位是D6,将D6置“0”,高位不变,得到ID(K~H)取10,H取6作为下一次命令所需的两个参数。

第②步,阅读器发送REQUEST(10,6),序列号前缀为10的标签响应,即标签10110010、10100011和10110011响应。各自返回后6位的信息110010、100011、110011。阅读器得到解码数据为1X001X,将碰撞最高位D4置为“0”。

第③步,阅读器发送REQUEST(1010,4),序列号前缀为1010的标签响应,只有标签10100011响应,无碰撞发生,读写器处理完该标签后对它进行屏蔽。

第④步:从该节点的父节点获得下一次REQUEST指令参数,阅读器发送REQUEST(1011,4)。标签1和标签3应答,阅读器解码数据为001X。

第⑤步:阅读器发送REQUEST(10110010,0)指令,标签3应答。阅读器对标签3进行处理后使其进入“无声”状态。

第⑥步:阅读器发送REQUEST(10110011,0)指令,只有标签1应答。阅读器对标签1进行处理后使其进入“无声”状态。采用返回策略,返回到最上一个父节点11。

第⑦步:阅读器发送REQUEST(11,6)指令,标签4应答,阅读器读取标签4的数据,识别过程结束。

在BDBS算法中,阅读器的搜索次数为2n-1,阅读器传输每次搜索平均传输的数据量为(k+1)/2,所以阅读器识别所有标签所需要发送的数据量为

对于BDBS搜索算法,当标签数量较多时,比BBS通信量减少近50%,比DBS减少约67%,比BS减少达到80%。如仿真图1所示。

1.5 改进的BDBS

在标签碰撞位只有一位时,说明只有两个标签发生碰撞,则认为没有发生碰撞。一个标签的碰撞位为“0”。另一个标签的碰撞位为“1”,直接识别标签。则阅读器的搜索次数减少为(2n-1)-[n/2]([]为向上取整),则完成n个标签问询,阅读器所需发送的数据量为

对阅读器的问询通信数据量进行比较。如图2所示,数据量较BDBS减少了约25%,性能得到了提高。