APP下载

温度传感器DS18B20序列号批量搜索算法

2011-06-22陈锡华贾磊磊

单片机与嵌入式系统应用 2011年9期
关键词:序列号假想搜索算法

陈锡华,贾磊磊

(桂林航天工业高等专科学校,桂林541004)

陈锡华(副教授),主要研究方向为无线通信技术、单片机技术应用。

引 言

单总线温度传感器DS18B20采用单总线接口技术,使系统布设传感器线路少、连接方式简单。每个DS18B20都有唯一的64比特(包括8比特的CRC码)序列号,用以区别单总线上不同的温度传感器,对其访问有特殊的协议和严格的时序[1]。在多点温度检测系统应用中,单总线上连接着批量(多个)传感器,系统必须掌握每个传感器的序列号,以实现对各个传感器的操作。DS18B20温度传感器内置温度报警电路,温度超出设置的上、下限温度时,将置报警标志。对总线进行报警搜索,实际上是对报警传感器序列号的搜索。方便、快速地搜索到传感器的序列号可以提高系统性能。

1 序列号搜索协议

DS18B20数据输出口与总线采用线与方式连接,多个传感器输出响应将会在总线上产生线与的结果。进行一次传感器序列号搜索,是在系统对总线发布序列号搜索命令(0xf0)之后开始的。从第一个比特到最后一个比特逐步进行,每一比特操作按读原码、读反码、回写结果3个步骤完成。系统发出搜索命令之后,立即对第一个比特进行操作,以后的各比特操作不再对总线发布序列号搜索命令,直接重复读原码、读反码、回写结果3个步骤直至完成序列号搜索[1-2]。

每一次回写比特后,读取下一比特的原码和反码时,只有序列号与前面所有回写比特都对应相符的传感器响应总线;不相符的传感器将端口切换为高阻,不再影响后面比特的搜索。搜索过程实际上是序列号排除过程,能对64个比特序列号都响应的仅有一个传感器。搜索过程结束后将获得一个传感器的序列号。DS18B20序列号前一个字节为0x28,搜索第一个字节时,总线上的传感器都会作出响应。

设一次搜索过程中,系统第i次对总线操作获得第i比特ai。从总线读取传感器响应的原码和补码分别为Ai和Bi(i=0,1,2,…,63),其4种可能组合情况如表 1所列。表中AiBi=11的情况可作为搜索结束条件,01和10的情况下比特是确定的,00情况下表明存在多个传感器,对其不同分支方向搜索可得到多个传感器序列号。

表1 DS18B20序列号搜索读取比特含义

2 批量搜索算法

对单总线上连接的批量传感器进行序列号搜索,将会出现AiBi=00的情形,出现序列号分支,该处分支比特称为一个分支点,分支点有取0和取1两个分支方向;不同数量和不同传感器,分支次数和分支的位置不同,搜索次数和搜索路径无法预先确定[3-4]。考虑一个序列号的搜索路径,若遇到分支点任意指定或按一定规律指定,都获得一个序列号。DS18B20序列号的唯一性决定了一个序列号对应一条唯一完整的搜索路径。搜索算法必须考虑两个方面:

①完整性。无遗漏搜索出总线上所有传感器序列号,必须对任意一个分支点的两个分支方向都进行完全搜索。

②有效性。保证搜索不重复,每一个序列号只搜索一次,即每一个序列号搜索都不同于前面的搜索路径。

批量序列号搜索算法基本思想是:每一个序列号搜索只在上一个序列号搜索产生的最后一个有效分支点改变搜索方向,获得新的序列号。有效分支点是在当前搜索路径中出现但未经过改变搜索方向处理的分支点;反之,在当前搜索路径中出现且经过改变搜索方向处理的分支点为无效分支点。每一个完整的序列号搜索过程都会产生一个最后有效分支点,为叙述方便,称为下一个序列号搜索的末点。出于算法规则考虑,假想序列号第0比特的前一比特是一个分支点,该分支点只搜索取0方向。每一个序列号搜索只在末点改变搜索方向,同时末点处的分支点也将变为无效分支点。这样每搜索一个到序列号将去掉一个末点,当末点退回到假想分支点时,标志搜索结束[5]。

对分支点两个搜索方向,可以设定先搜索取0方向,再搜索取1方向。算法设置3个寄存器:

①有效分支点位置寄存器BR_Addr。每一次序列号搜索遇到有效分支点时,将分支点位置寄存器更新为该有效分支点位置值,以便下一个序列号搜索获得末点位置。

②末点寄存器END_Addr。记录每一个序列号搜索产生的最后有效分支点。

③传感器数量累计寄存器CODE_Num。累计搜索到的传感器数量。

算法搜索流程如图1所示。

图1 算法搜索流程

批量搜索算法的具体步骤如下:

①设置末点位置为假想分支点,清除传感器数量累计寄存器。

②一个序列号搜索过程:

(a)分支点位置寄存器指向假想分支点,发布序列号搜索命令。

(b)搜索过程中出现AiBi=11,终止搜索。

(c)搜索过程中出现分支点,分支点与末点位置决定该分支点的取值:

◆分支点为末点位置,ai取1,变为无效分支点。

◆分支点在末点位置之前,ai取上一个报警序列号对应的比特值。

◆分支点在末点位置之后,ai取0。

(d)仅取值0的分支点位置更新有效分支点位置寄存器。

③将分支点位置寄存器值更新末点寄存器,保存搜索到的序列号,累计传感器个数。

④末点指向假想分支点,结束搜索。

⑤重复步骤②~④。

假想分支点在第0比特之前的第-1个比特位置上。第1步末点位置指向假想分支点是为了第一个序列号搜索出现的分支点都是有效分支点,因为搜索中没有分支点能指向假想分支点。如果总线上无传感器,将出现AiBi=11终止搜索。第2步在一个序列号搜索之前,都设置有效分支点位置寄存器指向假想分支点。若只有一个传感器,第一次搜索不会出现分支点,搜索完该传感器序列号后,末点仍指向假想分支点,结束搜索。若总线上连接两个传感器,第一个序列号搜索仅出现一个分支点,也是末点;第二个序列号搜索末点另一个方向,获得另一个序列号。末点变为无效发分支点,搜索结束后,新未点指向假想分支点,搜索结束。

对于总线上连接两个以上的批量传感器情况,第一个序列号搜索出现的分支点取值0,并逐步更新有效分支点位置寄存器,直到有效分支点位置寄存器指向最后一个分支点,产生一个末点。末点表明,末点当前的分支方向已搜索完毕,并获得一个序列号,否则不是最后分支点。第二个序列号按上一个序列号路径搜索到末点,在末点切换另一个方向(分支点取1)搜索,将出现两种情况:

①第一种情况是后面没有分支点,得到一个序列号后,末点已被完全搜索。其取值1不更新有效分支点位置寄存器,新末点将指向前一个分支点。新末点当前方向(分支点取0)已搜索完毕,以后不再搜索。

②第二种情况是后面有分支点,新的末点将在旧的末点后面,该旧末点分支方向按第一种情况递归搜索,直到该方向完全搜索。在此过程中旧末点一直取值1,不会被当作末点。旧末点该分支方向完全搜索后,下一个新末点将指向旧末点前一个分支点。以后的其他分支方向搜索方法相同。

结 语

批量搜索算法除第一个序列号搜索外,以后每搜索一个序列号都在末点改变搜索路径,同时末点变为无效分支点(末点比特由0变为1)。末点每更换搜索方向后,后面的搜索遇到分支点都取值0,保证新出现分支点都是有效分支点,搜索无遗漏。搜索过程中出现的分支点都仅被当作一次末点,每搜索到一个序列号都伴随着一个分支点以末点的方式脱离搜索路径,不会出现重复搜索。搜索次数和传感器数量相同,比分支点数多1,有较高的搜索效率。

该算法还适用于总线上批量传感器的报警搜索。将搜索算法中发布序列号搜索命令改为报警搜索命令(0xec),批量搜索算法将搜索到的是总线上产生报警传感器序列号和报警传感器的数量。在搜索过程中出现意外情况,搜索将会出现读原码和反码的线与值为11的情况,算法终止搜索,系统不会进入死循环状态。

[1]Dallas Semiconductor Corporation1.DS18B20—Programmable Resolution 1-Wire Digital Thermometer,2002.

[2]刘海成,秦进平,韩喜春.MCU-DSP型单片机原理与应用[M].北京:北京航空航天大学出版社,2006:187-197.

[3]刘晓阳,周炎涛.一线总线结构的DS18B20的序列号搜索算法研究[J].计算机与自动化,2010,29(1):38-42.

[4]陈文.DS18B20 ROM编码的一种搜索算法[J].单片机与嵌入式系统应用,2009(8):66-67.

[5]盛磊,葛照君.二叉树算法在 DS18B20地址搜索中的运用[J].计算机系统应用,2010,19(2):143-146.

猜你喜欢

序列号假想搜索算法
改进的和声搜索算法求解凸二次规划及线性规划
一种离线电子钱包交易的双向容错控制方法
Cartoons
关于《国家税务总局 工业和信息化部关于加强车辆配置序列号管理有关事项的公告》的解读
批判与重构:论作为准防卫过当的假想防卫过当
recALL
高中历史教学中的史实与假想
假想防卫过当概念辨析
基于汽车接力的潮流转移快速搜索算法
基于逐维改进的自适应步长布谷鸟搜索算法