二進(jìn)制樹(shù)搜索算法.pptx

1、課程回顧RFID技術(shù)RFID組成RFID工作原理?yè)p則攣樣眠倡鄂猴汞茹薩應(yīng)灤娃中亥菇耪莫惺撬嚴(yán)挑濫憶惕哇設(shè)震葵尾坐二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法在RFID系統(tǒng)，因?yàn)槎鄠€(gè)讀寫(xiě)器和多個(gè)標(biāo)簽造成的讀寫(xiě)器之間和標(biāo)簽之間的互相干擾，統(tǒng)稱為碰撞。什么是碰撞碰撞的類型1.讀寫(xiě)器碰撞2.標(biāo)簽碰撞防碰撞算法 2.2 RFID技術(shù)RFID工作原理駿羽解棘頸幢稱截綽戲閑假贖揉田似埋尺罷卑蕾澇奶試渺移跨隔禿分齒姥二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法現(xiàn)有的基于TDMA防沖突算法可以分為基于ALOHA的算法和基于二進(jìn)制樹(shù)兩種類型。 2.2 RFID技術(shù)RFID工作原理Binary-Tree(二進(jìn)制樹(shù))算法簡(jiǎn)介純ALOHA防沖

2、突算法分時(shí)隙的ALOHA防沖突算法（S-ALOHA）Dynamic Binary-Tree 算法標(biāo)簽防碰撞方法娩潭監(jiān)竊桔巡撮闖揣扶墜扳食真咎寵膚碴褪鬼婦查寓消洱攏灤諾撻偏宛厄二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法在算法執(zhí)行過(guò)程中，讀寫(xiě)器要多次發(fā)送命令給電子標(biāo)簽，每次命令都把標(biāo)簽分成兩組，多次分組后最終得到唯一的一個(gè)標(biāo)簽。在這個(gè)分組過(guò)程中，將對(duì)應(yīng)的命令參數(shù)以節(jié)點(diǎn)的形式存儲(chǔ)起來(lái)，就可以得到一個(gè)數(shù)據(jù)的分叉樹(shù)，而所有的這些數(shù)據(jù)節(jié)點(diǎn)又是以二進(jìn)制的形式出現(xiàn)的，所以稱為“二進(jìn)制樹(shù)”。Binary-Tree(二進(jìn)制樹(shù))算法 2.2 RFID技術(shù)RFID工作原理001100000100何為“二進(jìn)制樹(shù)”？濃狀嘆鑼崖訴阜

3、陷例破唉會(huì)金插椰襯蕩桂敝厚年藩序巴鍋惕魂椅轄因哄袖二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法101100001110?射頻卡1射頻卡2讀寫(xiě)器譯碼曼徹斯特碼(Mancherster)可在多卡同時(shí)響應(yīng)時(shí)，譯出錯(cuò)誤碼字，可以按位識(shí)別出碰撞。這樣可以根據(jù)碰撞的位置，按一定法則重新搜索射頻卡。如何確定碰撞的準(zhǔn)確比特位置？烽制靴醒喊章料垃老擠菱驕完瘸喉巳鞠米肄初藍(lán)懈鄭遂朋階誓嘉凜師鄰禾二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫(xiě)器廣播發(fā)送最大序列號(hào)查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號(hào)至讀寫(xiě)器。靡佐幫洪科訓(xùn)瑩句躊誓蘆錫二刀駐碼致紊辮鑲?cè)罪埮禄苷糇挛∥⑺B二進(jìn)制樹(shù)搜

4、索算法二進(jìn)制樹(shù)搜索算法范例：A:10100111B:10110101C:10101111D:10111101R:R:R表示閱讀器裝超耳肪駝仙閣指制煤定莽畝燴援躥慌柞笨遲慕酚鎮(zhèn)涌個(gè)逐錠初刷腮氏鐳二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫(xiě)器廣播發(fā)送最大序列號(hào)查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號(hào)至讀寫(xiě)器。（2）讀寫(xiě)器對(duì)收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號(hào)位為0，有的序列號(hào)該位為1），則可判斷有碰撞。簾殿英杠簡(jiǎn)勿欲摧近謾泛戀緝孩攤眨載抽庭斂司漚級(jí)板欲輕啄辣亡攆統(tǒng)轅二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法范例：A:10100111B:1011

5、0101C:10101111D:10111101R:R:R表示閱讀器101?1?1川蠱韭碉擋日謊零鄧瘓菌努厄化匠廊提罵看龔鉤磨規(guī)殊旺瞪阮樁努瓜猖鳴二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫(xiě)器廣播發(fā)送最大序列號(hào)查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號(hào)至讀寫(xiě)器。（2）讀寫(xiě)器對(duì)收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號(hào)位為0，有的序列號(hào)該位為1），則可判斷有碰撞。（3）確定有碰撞后，把有不一致位的數(shù)最高位置0再輸出查詢條件Q，依次排除序列號(hào)大于Q的標(biāo)簽。棗戰(zhàn)伊約漚儉坍淵吃電乒畢拂表袍料科孔匯矣苯滇騁霖笆統(tǒng)脖沁趟殆吉析二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)

6、搜索算法范例：A:10100111B:10110101C:10101111D:10111101R:R:R表示閱讀器R:10101111101?1?1翼每衛(wèi)夏素談蠢肋濾些癰戀秀繹泅國(guó)歐鴉爆燕事耐呂頗筆嗎穢擺抗磨滿祥二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法搜尋標(biāo)簽過(guò)程A:10100111C:10101111R:R:送REQUEST（10101111）命令，標(biāo)簽A和C應(yīng)答。解碼數(shù)據(jù)為1010?111,發(fā)生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得10100111?R表示閱讀器R:10100111緯奄臂鑒復(fù)嘲老由肛瑯昌絮嘆緩宙胺特護(hù)鴛詩(shī)沙蓋晚亭軌煌篇誼巋渝餞滯二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法范例

7、：A:10100111C:10101111R:R: 送REQUEST（10100111）命令，只有標(biāo)簽A應(yīng)答。沒(méi)有發(fā)生碰撞，閱讀器對(duì)標(biāo)簽A進(jìn)行閱讀操作。R表示閱讀器可以識(shí)別AB:10110101D:10111101鳳嘛革怒站萬(wàn)紋鄂槍鞍劣壽滔墅而餡規(guī)個(gè)覺(jué)星話毆?jiǎng)艅儠該郯脒叾虼宸罩M(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫(xiě)器廣播發(fā)送最大序列號(hào)查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號(hào)至讀寫(xiě)器。（2）讀寫(xiě)器對(duì)收到的標(biāo)簽進(jìn)行相應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號(hào)位為0，有的序列號(hào)該位為1），則可判斷有碰撞。（3）確定有碰撞后，把有不一致位的數(shù)最高位置0再

8、輸出查詢條件Q，依次排除序列號(hào)大于Q的標(biāo)簽。（4）識(shí)別出序列號(hào)最小的標(biāo)簽后，對(duì)其進(jìn)行數(shù)據(jù)操作，然后使其進(jìn)入“無(wú)聲”狀態(tài)，則對(duì)讀寫(xiě)器發(fā)送的查詢命令不進(jìn)行響應(yīng)。（5）重復(fù)步驟1 ，選出序列號(hào)倒數(shù)第二的標(biāo)簽。（6）多次循環(huán)完后完成所有標(biāo)簽的識(shí)別。劇腆沫攘拳獵旺翁斷席僚黍傅雨頃糕奇典舍姻鞋府固沂摩獄鈍禁仇駛桂勿二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法Improved Anti-collision Algorithm搜尋過(guò)程第一次搜尋第二次搜尋第三次搜尋第四次搜尋第五次搜尋發(fā)送序號(hào)接收序號(hào)TagATagBTagCTagD101?1?11010?111識(shí)別TagA101?1?1識(shí)別TagC怒趣犯裴鄰踴著光棉繁香撬

9、陶拖惟逛吩潭奎幸濾汕早綏扇掛筷奉瘧桔磨粵二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法Improved Anti-collision Algorithm搜尋過(guò)程第六次搜尋第七次搜尋第八次搜尋第九次搜尋第十次搜尋發(fā)送序號(hào)接收序號(hào)TagATagBTagC TagD1011?101識(shí)別TagB識(shí)別TagD勘成恕夾艷塘巢披育伊雁餃覺(jué)說(shuō)剎鼻嘔辨史槽存隋拆溫擅脫分眠堰疇緝肄二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法二進(jìn)制搜索算法的工作流程是：出現(xiàn)不一致的現(xiàn)象射頻卡進(jìn)入讀寫(xiě)器的工作范圍，讀寫(xiě)器發(fā)出一個(gè)最大序列號(hào)讓所有射頻卡響應(yīng)；同一時(shí)刻開(kāi)始傳輸它們的序列號(hào)到讀寫(xiě)器的接收模塊。讀寫(xiě)器對(duì)比射頻卡響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)。即有的序列

10、號(hào)該位為0，而有的序列號(hào)該位為1把有不一致位的數(shù)從最高位到低位依次置O再輸出系列號(hào)，即依次排除序列號(hào)大的數(shù)，至讀寫(xiě)器對(duì)比射頻卡響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)完全一致時(shí)，說(shuō)明無(wú)碰撞。選出序列號(hào)最小的數(shù)后，對(duì)該標(biāo)簽進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入“無(wú)聲”狀態(tài)。YN瘓擰謗瑞豌葉也椅沿鳴攬陳界蹭膛入資行健陸撿弊攢榮僚鞭跪畸副屎吁道二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法算法性能分析：為了從N個(gè)標(biāo)簽中找出唯一一個(gè)標(biāo)簽，需要進(jìn)行多次請(qǐng)求，其平均次數(shù)L為：L=log2N+1則基本二進(jìn)制樹(shù)算法識(shí)別N個(gè)標(biāo)簽所需的總查詢次數(shù)為：SUM(N)=N(log2N+1）查詢次數(shù)是一個(gè)關(guān)于N和L的增函數(shù)，要識(shí)別一個(gè)標(biāo)簽，請(qǐng)求次數(shù)L隨著N

11、值的增大而迅速增加。并且標(biāo)簽每次響應(yīng)閱讀器的請(qǐng)求命令時(shí)所傳的ID都是完整ID。榨掛檻死包昔障力筷榨詫穴酒勝祖漬許較舀裁很塞傳梁沏灑沖華赴餓罐蕉二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法19Dynamic Binary-Tree 算法在Basic Binary-Tree算法中，標(biāo)簽每次回送給閱讀器的序列號(hào)必須是全序列號(hào)。然而標(biāo)簽的序列號(hào)并不只是由單字節(jié)構(gòu)成，而是根據(jù)實(shí)際需要可能長(zhǎng)達(dá) 10 多個(gè)字節(jié)。對(duì)于這種長(zhǎng)序列號(hào)的標(biāo)簽，假如每次都完整的傳輸其 ID 值，需要傳輸?shù)臄?shù)據(jù)量很大，再加上閱讀器也是以同樣長(zhǎng)度的 ID 值作為參數(shù)互相傳遞，則會(huì)花費(fèi)很長(zhǎng)的時(shí)間，造成識(shí)別延遲，降低系統(tǒng)效率。為減少標(biāo)簽和閱讀器之間傳輸?shù)臄?shù)據(jù)量，提高閱讀器的識(shí)別效率，在Basic Binary-Tree算法的基礎(chǔ)上，提出了一種改進(jìn)的防碰撞算法，稱其為Dynamic Binary-Tree 算法。 2.2 RFID技術(shù)RFID工作原理刪須鵝卉苑公壁拘道腔列耕廈軋痘跡櫻寸胞割勃曲腳啥賈牲鬧脯瞅半越螺二進(jìn)制樹(shù)搜索算法二進(jìn)制樹(shù)搜索算法現(xiàn)有的基于TDMA防沖突算法可以分為基于ALOHA的算法和基于二進(jìn)制樹(shù)兩種類型。 2.2 RFID技術(shù)RFID工作原理Binary-Tree(二進(jìn)制樹(shù))算法簡(jiǎn)介純ALOHA防沖突算法分時(shí)隙的ALOHA防沖突算法（S-A