溫度傳感器DS18B20序列號批量搜索算法

陳錫華,賈磊磊

(桂林航天工業高等專科學校,桂林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.