精华内容
下载资源
问答
  • 二进制树型搜索算法由读写器控制。基本思想是不断将导致碰撞电子标签进行划分,缩小下一步搜索标签数量,直到只有一个电子标签进行回应,即没有碰撞发生。具体方法是将处于冲突标签分为左右两个子集0和1,先...
    展开全文
  • 二进制树搜索算法的基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,直到识别出子集0中的所有标签,再按此步骤查询...

    二进制树形搜索算法的基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,直到识别出子集0中的所有标签,再按此步骤查询子集1.

    算法实列:
    电子标签1: 10110010
    电子标签2: 10100011
    电子标签3: 10110011
    电子标签4: 11100011
    ①读写器第一次发送REQUEST(<=11111111)命令。序列号11111111是本例中系统最大可能的8位序列号,因此读写器作用范围内的所有电子标签都对该命令做出应答。由于序列号的0,4,6位重叠响应而造成了冲突(1X1X001X)

    ②第六位最高是X位,因此在该位上出现了冲突,意味着不仅在序列号(>=11000000)的范围内,而且在序列号(<=10111111)的范围内,至少各有1个电子标签存在。为了能选择到一个单独的电子标签,必须根据已有的信息来限制下一次迭代的搜索范围。例如,在<=10111111的范围内进一步搜索。为此,将第6位置0(有冲突位的最高位),将所有低位置1,暂时对所有低位的值不予处理
    (一会在程序实现的时候就相当于不判断低位,只判断冲突位之前的位数)。

    ③若在第二次迭代的过程中还发现有冲突,则进一步缩小范围,方法类似②步骤

    在这里插入图片描述

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    struct card
    {
    	string code;  //序列号
    	bool is_correct;  //卡是否能读取(错误卡或已读的卡不能读)
    	card(){}
    	card(string code)
    		:code(code)
    		, is_correct(true)
    	{}
    };
    
    class RFID_Read
    {
    public:
    	//找出冲突位 arr代表一组卡 ,max_code代表最大序列号, conflict_bit用于存储冲突位
    	void first_request(vector<card>& arr, string& max_code, vector<int>& conflict_bit)
    	{
    		int max_code_length = max_code.size();
    		int arr_length = arr.size();
    		for (int i = 0; i < arr_length; ++i) {     //标记非法卡,一会搜索时就忽略它
    			if (arr[i].code.size() != max_code_length) {
    				arr[i].is_correct = false;
    			}
    			else {
    				cout << arr[i].code << endl;  //打印所有正确的卡
    			}
    		}
    		int k = 0;
    		for (int i = 0; i < arr_length; ++i) {  //找出第一张正确的卡
    			if (arr[i].is_correct == true) {
    				k = i;
    				break;
    			}
    		}
    		for (int i = 0; i < max_code_length; ++i) {  //找冲突位
    			max_code[i] = arr[k].code[i];            //将第一张正确卡的序列号赋给max_code
    			for (int j = 0; j < arr_length; ++j) {
    				if (arr[k].code[i] != arr[j].code[i] && arr[j].is_correct == true) { //遇到冲突位时
    					conflict_bit.push_back(i);                       //将冲突位的位数记录
    					max_code[i] = 'X';                              //并将冲突位标记位X后退出判断下一位
    					break;
    				}
    			}
    		}
    	}
    	//找出某一张卡
    	void find_card(vector<card>& arr, vector<int>& conflict_bit, string& s)
    	{
    		request(arr, conflict_bit, 0, '0', s);
    		request(arr, conflict_bit, 0, '1', s);
    	}
    
    private:
    	//二进制树型搜索算法   k代表conflict_bit数组的第k位, flag代表冲突位将被置位0或1, s代表当前读写器发出的序列号
    	void request(vector<card>& arr, vector<int>& conflict_bit,int k, char flag, string& s)
    	{
    		int count = 0;
    		s[conflict_bit[k]] = flag;  //将最高冲突位置为0或1
    		for (int i = 0; i < arr.size(); ++i) {
    			if (arr[i].code[conflict_bit[k]] == flag && arr[i].is_correct == true) { //找出与冲突位相同的序列号,count++
    				++count;
    				for (int j = 0; j <= conflict_bit[k]; ++j) {          //找出与当前冲突位之前位数不相同的序列号,count--
    					if (arr[i].code[j] != s[j]) {                  
    						--count;
    						break;
    					}
    				}
    			}
    		}
    		if (count < 2) {                                   //当找到的卡的数量等于1或0时,就打印该序列号并将该卡置为不可读,后退出循环
    			int f = 0;
    			for (int i = 0; i < arr.size(); ++i){
    				if (arr[i].code[conflict_bit[k]] == flag && arr[i].is_correct == true) {
    					for (int j = 0; j <= conflict_bit[k]; ++j) {
    						if (arr[i].code[j] != s[j]) {
    							break;
    						}
    						f = j;
    					}
    					if (f == conflict_bit[k]) {  
    						arr[i].is_correct = false;
    						cout << "第 " << i + 1 << " 个标签: " << arr[i].code << endl;
    					}
    				}
    			}
    			return;
    		}
    		else {  //继续下一个冲突位的判断
    			request(arr, conflict_bit, k + 1, '0', s);
    			request(arr, conflict_bit, k + 1, '1', s);
    		}
    	}
    };
    
    int main()
    {
    	RFID_Read r;
    	vector<card> arr;
    	string str;
    	int k;
    	cout << "请输入标签个数:" << endl;
    	cin >> k;
    	for (int i = 0; i < k; ++i) {
    		cin >> str;
    		arr.push_back({ str });
    	}
    	string s = "11111111";
    	vector<int> conflict_bit;
    	r.first_request(arr, s, conflict_bit);
    	r.find_card(arr, conflict_bit, s);
    	return 0;
    }
    
    展开全文
  • 在RFID防碰撞算法中,二进制树算法是目前应用最广泛的一种。因为在算法执行过程中,读写器要多次发送命令给应答器,每次命令都把应答器分成两组,多次分组后最终得到唯一的一个应答器,在这个...二进制树型搜索算法的

    在RFID防碰撞算法中,二进制树算法是目前应用最广泛的一种。因为在算法执行过程中,读写器要多次发送命令给应答器,每次命令都把应答器分成两组,多次分组后最终得到唯一的一个应答器,在这个分组过程中,将对应的命令参数以节点的形式存储起来,就可以得到一个数据的分叉树,而所有的这些数据节点又是以二进制的形式出现的,所以称为“二进制树”。

    二进制树型搜索算法模型图如下图所示:


    二进制树型搜索算法的实现步骤如下:

    (1)应答器进入读写器工作范围,读写器发出一个最大序列号,所有应答器在同一时刻将自身序列号返回给读写器;

    (2)由于应答器序列号的唯一性,当应答器数目大于或等于两个时,必然发生碰撞。发生碰撞时,将最大序列号中对应的碰撞起始位设置为0,低于该位者不变,高于该位者设置为1;

    (3)读写器将会把序列号发给应答器,应答器序列号与其进行比较,若小于或等于该值者,则返回自身序列号给读写器;

    (4)识别出序列号最小的标签后,对其进行操作,使其进入休眠状态,即除非重新上电,否则不再响应读写器请求命令。也就是说,下一次读写器再发最大序列号时,该应答器不再响应;

    (5)重复上述步骤,选出序列号倒数第二的标签;

    (6)多次重复循环,依次完成对各个应答器的识别。

    展开全文
  • 8-4 RFID系统二进制树搜索算法是如何解决碰撞?简述其实现步骤。  将处于冲突标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,依次类...

    8-4 RFID系统二进制树形搜索算法是如何解决碰撞的?简述其实现步骤。

        将处于冲突的标签分成左右两个子集01,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成0001两个子集,依次类推,直到识别出子集0中所有标签,再按此步骤查询子集1


          二进制搜索算法的基本思路是:多个标签进入读写器工作场后,读写器发送带限制条件的询问命令,满足限制条件的标签回答,如果发生碰撞,则根据发生错误的位修改限制条件,再一次发送询问命令,直到找到一个正确的回答,并完成对该标签的读写操作。对剩余的标签重复以上操作,直到完成对所有标签的读写操作。      

        为了实现二进制搜索算法,就要选用曼彻斯特编码,因为这种编码可以检测出碰撞位。   

    二进制树型搜索算法的实现步骤如下:


    展开全文
  • (1)普通二进制树搜索: 设计一个1、11、21…标签数目 ①先设计一个GUI界面,得到8位二进制数随机序列,分成256份。 ②先对每一次都找出碰撞最高位; ③选择比碰撞位小二进制数,然后继续进行第②步骤,直至...
  • 二进制树搜索算法(如下图所示)基本思想是将处于冲突标签分成左右两个子集0和1,先查询子集0,如果没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,以此类推,直到识别出子集0中...
  • RFID第四次作业[8-4]

    2015-04-21 23:35:32
    [8-4]RFID系统二进制树搜索算法是如何解决碰撞?简述其实现步骤   二进制树搜索算法过程: 1.将处于冲突标签分成左右两个子集0和1 2.先查询子集0,若没有冲突则正确识别标签 3.若仍有冲突则再分裂,...
  • RFID第八章作业

    2015-04-19 13:25:07
    8-3 简要说明RFID系统的时隙ALOHA算法的工作过程 时隙ALOHA算法把时间分成多个...8-4 RFID系统二进制树搜索算法是如何解决碰撞的?简述其实现步骤。  (1)将处于冲突的标签分成左右两个子集0和1,先查询子集
  • LeetCode解题总结

    2018-10-09 16:02:19
    3.4 二进制树相加 3.5 最长回文字符串 3.6 正则表达式匹配[hard] 3.7 正则匹配 3.8 最长公共前缀 3.9 验证字符串是否为数字 3.10 数字转为罗马数字 3.11 罗马数字到数字 3.12 Count and Say 3.13 变位词 3.14 简化...
  • vc++ 应用源码包_1

    热门讨论 2012-09-15 14:22:12
    电子钟的实现,自绘Button、Static的实现,其中自定了一个辅助主题风格类。 CctryLog(web拦截网页帐号密码) 实现了一个控件去获得IHTMLDocument2接口,然后读取内容,匹配用户名与密码等。 CFile64_src 操作大...
  • vc++ 应用源码包_6

    热门讨论 2012-09-15 14:59:46
    电子钟的实现,自绘Button、Static的实现,其中自定了一个辅助主题风格类。 CctryLog(web拦截网页帐号密码) 实现了一个控件去获得IHTMLDocument2接口,然后读取内容,匹配用户名与密码等。 CFile64_src 操作大...
  • vc++ 应用源码包_2

    热门讨论 2012-09-15 14:27:40
    电子钟的实现,自绘Button、Static的实现,其中自定了一个辅助主题风格类。 CctryLog(web拦截网页帐号密码) 实现了一个控件去获得IHTMLDocument2接口,然后读取内容,匹配用户名与密码等。 CFile64_src 操作大...
  • vc++ 应用源码包_5

    热门讨论 2012-09-15 14:45:16
    电子钟的实现,自绘Button、Static的实现,其中自定了一个辅助主题风格类。 CctryLog(web拦截网页帐号密码) 实现了一个控件去获得IHTMLDocument2接口,然后读取内容,匹配用户名与密码等。 CFile64_src 操作大...
  • vc++ 应用源码包_4

    热门讨论 2012-09-15 14:38:35
    电子钟的实现,自绘Button、Static的实现,其中自定了一个辅助主题风格类。 CctryLog(web拦截网页帐号密码) 实现了一个控件去获得IHTMLDocument2接口,然后读取内容,匹配用户名与密码等。 CFile64_src 操作大...
  • vc++ 应用源码包_3

    热门讨论 2012-09-15 14:33:15
    电子钟的实现,自绘Button、Static的实现,其中自定了一个辅助主题风格类。 CctryLog(web拦截网页帐号密码) 实现了一个控件去获得IHTMLDocument2接口,然后读取内容,匹配用户名与密码等。 CFile64_src 操作大...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象的方法设计代码; 2、一个图是一个类的实例; 3、类...
  • 面试题10:二进制中1个数:注意到每个非零整数n和n-1进行按位与运算,整数n的二进制数中最右边1就会变成0,那么二进制数中1个数就会减少一个,因此可以利用一个循环,使得 n = n&(n-1) ,计算经过几次...
  • 03.返回一个数二进制中1个数 04.只出现一次数字 05.只出现一次数字Ⅱ 06.缺失数字(268) 二分法 01.爱吃香蕉珂珂(875) 02.x平方根(69) 03.x平方根(69) 04.旋转排序数组中最小值Ⅰ(153) 05....
  • java源码包---java 源码 大量 实例

    千次下载 热门讨论 2013-04-18 23:15:26
     Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系,这些代码面向初级、中级Java程序员。 Java访问权限控制源代码 1个目标文件 摘要:Java源码,...
  • antlr4权威指南

    2017-09-30 10:47:22
    ANTLR是一款强大语法分析器生成工具,可用于读取、处理、执行和翻译结构化文本或二进制文件。它被广泛应用于学术领域和工业生产实践,是众多语言、工具和框架基石。Twitter搜索使用ANTLR进行语法分析,每天...
  • Java二进制IO类与文件复制操作实例 16个目标文件 内容索引:Java源码,初学实例,二进制,文件复制 Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系...
  • JAVA上百实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系,这些代码面向初级、中级Java程序员。 Java访问权限控制源代码 1个目标文件 摘要:Java源码,...
  • java源码包2

    千次下载 热门讨论 2013-04-20 11:28:17
     Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系,这些代码面向初级、中级Java程序员。 Java访问权限控制源代码 1个目标文件 摘要:Java源码...
  • java源码包3

    千次下载 热门讨论 2013-04-20 11:30:13
     Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系,这些代码面向初级、中级Java程序员。 Java访问权限控制源代码 1个目标文件 摘要:Java源码...
  • asp.net知识库

    2015-06-18 08:45:45
    使用.ashx文件处理IHttpHandler实现发送文本及二进制数据方法 制作一个简单多页Tab功能 一完美关于请求目录不存在而需要url重写解决方案! 在C#中实现MSN消息框功能 XmlHttp实现无刷新三联动ListBox 鼠标...
  • Java二进制IO类与文件复制操作实例 16个目标文件 内容索引:Java源码,初学实例,二进制,文件复制 Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系...
  • Java二进制IO类与文件复制操作实例 16个目标文件 内容索引:Java源码,初学实例,二进制,文件复制 Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系...
  • java源码包

    2015-12-01 16:29:37
     Java二进制IO类与文件复制操作实例,好像是一本书例子,源代码有是独立运行,与同目录下其它代码文件互不联系,这些代码面向初级、中级Java程序员。 Java访问权限控制源代码 1个目标文件 摘要:Java源码,...

空空如也

空空如也

1 2
收藏数 35
精华内容 14
关键字:

二进制树搜索算法的实现步骤