RFID二進位搜索法防碰撞的實現

2020-12-12 電子產品世界

摘要 探索一種解決RFID系統中碰撞問題的方法,具體討論防碰撞算法中的二進位搜索算法及其改進方法一一動態二進位搜索算法。動態二進位搜索算法考慮的是在UID位數不變的情況下,把數據分成兩部分,收發雙方各自傳送其中一部分數據,可把傳輸的數據量減小到一半,縮短傳送時間,提高RFID系統的效率。
關鍵詞 射頻識剮 讀寫器射頻卡碰撞二進位搜索法

1 RFID技術概述
射頻識別技術RFID(Radio Frequeilcy Identification)是一種非接觸式的自動識別技術。目前的RFID系統有很多工作頻段:低頻、高頻和超高頻段。工作原理也不盡相同,有的是利用近場的電磁感應(所以有人把射頻卡稱為「感應卡」)}有的是利用電磁波發射來實現非接觸雙向通信,以達到識別目的並交換數據。RFID技術由於可實現非接觸目標識別、多目標識別和運動目標識別,具有防水、防磁、耐高溫、使用壽命長、讀取距離大、標籤上數據可以加密、存儲數據容量更大以及存儲信息更改自如等優點,廣泛應用於工業自動化、商業自動化和交通運輸控制管理等眾多領域。

RFID系統,如圖1所示,主要由射頻卡(又稱為「電子標籤」)、讀寫器和計算機網絡組成。其中最重要的是讀寫器(Reader Writer Device)和射頻卡(Transponder)。讀寫器和射頻卡之間採用無線通信方式,因此它們都有無線收發模塊及天線(或感應線圈)。射頻卡晶片上有內存部分用來存儲序列號(識別號碼)或其他數據。

2 防碰撞方法綜述
早期的系統中,1次只能讀/寫1個射頻卡。射頻卡之間要保持一定距離,確保一次只有一個卡在讀寫區域內,應用起來很不方便。很多時候不可避免地會出現多個射頻卡進入識別區域時信號互相干擾的情況,即碰撞。具有防碰撞性能的系統可以同時識別進人識別距離的所有射頻卡,其並行工作方式大大提高了系統的效率。

2.1 防碰撞方法的設計要求

防碰撞技術主要解決RFID系統一次可以完成對多個射頻卡的識別問題。假設同時進入讀寫器天線區域的射頻卡共有n個,防碰撞設計要求如下:
①當1≤n≤N時,其中N為讀寫器一次可識別射頻卡數量的上限,則在碰撞發生(n>1)的情況下,能識別n個射頻卡並依次與它們完成通信。
②平均響應時聞τ足夠短,τ為某一時段內完成通信的所有射頻卡在系統內的平均停留時間。τ與算法有關,允許τ≤τ0。τ0為不同應用中所允許的最大時延。

2.2 RFID中防碰撞的基本原理

由於射頻卡含有可被識別的唯一信息(序列號),RFID系統的目的就是要讀出這些信息。如果只有一個射頻卡位於閱讀器的可讀範圍內,則無需其他的命令形式即可直接進行閱讀。如果有多個射頻卡同時位於一個閱讀器的可讀範圍內,則射頻卡的應答信號就會相互幹擾形成所謂的數據衝突,從而造成閱讀器和射頻卡之間的通信失敗。為了防止這些衝突的產生,RFID系統中需要設置一定的相關命令,解決衝突問題,這些命令被稱為「防衝突命令或算法(anti-collision algorithms)」。

在無線電技術中,實現防碰撞基本上有4種不同的方法:時分多路法、頻分多路法、空分多路法以及碼分多路法。時分多路(TDMA)法是把整個可供使用的通路容量按時間分配給多個用戶的技術。TDMA在數字移動無線電系統中得到廣泛應用。考慮到RFID系統通信形式、功耗、系統的複雜性及成本等因素,選擇TCMA來實現射頻識別系統的防碰撞機制是最普遍的方法。

TDMA法通常被分為兩大類:讀寫器控制防碰撞法和射頻卡控制防碰撞法。
讀寫器控制防碰撞法是以讀寫器為主動控制器,進入射頻場的所有射頻卡同時由讀寫器進行控制和檢查。閱讀器依據射頻卡的ID號(Identification number)首先向射頻卡發射不同的詢問信號或指令,閱讀器依據選舉方法或二進位樹尋找方法,在同一時間內總是建立起一個通信關係,並且可以快速地按時間順序操作射頻卡。

射頻卡控制法以射頻卡為主控制器,讀寫器對數據傳輸沒有控制。讀寫器發出指令後,由射頻卡依據自己的ID號(每個射頻卡的ID號是唯一的)隨機產生應答時間。這時閱讀器發送信息如果有衝突,則射頻卡要等到下一個時隙到來時再重新產生響應時間(即自動排隊),使射頻卡在不同的時間段發回數據,讀寫器只是被動的接收數據。若有兩張以上的射頻卡同時反應,則讀寫器認為該數據無效,會重發指令,直到識別出場中的所有射頻卡。IS015693標準就採用了這種時隙方法。

本文主要針對射頻卡控制法,即基於TDMA的二進位搜索防碰撞算法進行分析和研究,並分別在性能上作分析。二進位搜索算法的思路是:通過定義讀寫器與多個射頻卡之間一組規定的指令序列,從中選出一張卡,並完成二者的數據交換。

3 二進位搜索算法
二進位搜索算法的方法類似於在天平中採用的逐次比較方法。通過多次比較,不斷篩選出不同的序列號,時分復用地進行讀寫器和射頻卡之問的信號交換,以一個獨特的序列號來識別射頻卡為基礎。為了從一組射頻卡中選擇其中之一,讀寫器發出一個請求命令有意識地將射頻卡序列號傳輸時的數據碰撞引導到讀寫器上,即通過讀寫器判斷是否有碰撞發生。如果有碰撞,則縮小範圍進行進一步的搜索。

二進位搜索算法由一個讀寫器和多個射頻卡之間規定的一組命令和應答規則構成,目的在於從多卡中選出任一個實現數據通信。

該算法有3個關鍵要素:①選用適當的基帶編碼(易於識別碰撞)。②利用射頻卡卡序列號唯一的特性。③設計一組有效的指令規則,高效、迅速地實現選卡。

3.1 曼徹斯特編碼

在二進位搜索算法的實現中,起決定作用的是讀寫器所使用的信號編碼必須能夠確定碰撞的準確比特位置。曼徹斯特碼(Mancherster)可在多卡同時響應時,譯出錯誤碼字,可以按位識別出碰撞。這樣可以根據碰撞的位置,按一定法則重新搜索射頻卡。

3.2 防碰撞指令規則
典型指令規則:
①REQuEST――請求(序列號)。此命令發送一序列號作為參數給射頻卡。應答規則是,射頻卡把自己的序列號與接收到的序列號比較,如果自身序列號小於或等於REQUEST指令序列號參數,則此射頻卡回送其序列號給讀寫器。這樣可以縮小預選的射頻卡的範圍;如果大於,則不響應。
②SELECT――選擇(序列號)。用某個(事先確定的)序列號作為參數發送給射頻卡。具有相同序列號的射頻卡將以此作為執行其他命令(例如讀出和寫入數據)的切入開關,即選擇這個射頻卡。具有其他序列號的射頻卡只對REQUEST命令應答。
③READ-DATA――讀出數據。選中的射頻卡將存儲的數據發送給讀寫器。
④UNSELECT ――去選擇。取消一個事先選中的射頻卡,射頻卡進入「無聲」狀態,在這種狀態下射頻卡完全是非激活的,對收到的REQUEST命令不作應答。為了重新話化射頻卡,必須先將射頻卡移出讀寫器的作用範圍再進入,以實行復位。

3.3 工作流程

在二進位搜索算法中,要能夠檢測出多張卡的存在,卡片的返回數據必須具有唯一性,且卡片在傳輸其UID(Ubiquitous IDentifications,身份識別標籤)時必須準確、同步。這樣終端才能在位級上檢測出多張卡片的存在,這是防碰撞檢測的關鍵。

射頻卡工作的特點是,當讀到讀寫器發出的序列號大於自身序列號時,則對系統作出響應。根據這一特點,二進位搜索算法的工作流程是:

①射頻卡進入讀寫器的工作範圍,讀寫器發出一個最大序列號讓所有射頻卡響應;同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。
②讀寫器對比射頻卡響應的序列號的相同位數上的數,如果出現不一致的現象(即有的序列號該位為0,而有的序列號該位為1),則可判斷出有碰撞。
③確定有碰撞後,把有不一致位的數從最高位到次低次依次置O再輸出系列號,即依次排除序列號大的數,至讀寫器對比射頻卡響應的序列號的相同位數上的數完全一致時,說明無碰撞。這時就選出序列號最小的數。
④選出序列號最小的數後,對該}進行數據交換,然後使該卡進入「無聲」狀態,則在讀出器範圍也不再響應(移動該範圍後移入可再次響應)。
⑤重複流程①,選出序列號倒數第二的射頻卡進行數據交換。
⑥多次循環後可完成所有射頻卡的讀取。

4 二進位搜索算法的改進分析
4.1 二進位搜索算法的傳輸時間

由二進位搜索算法的工作流程可知,防碰撞處理是在確認有碰撞的情況下,根據高低位不斷降值的序列號一次次進行篩選出某一射頻卡,從而可知射頻卡的數量越多,防碰撞執行時間就將越長。搜索的次數N可用下式來計算:
N=Integ(1Og M/log2)+1
式中:M是終端作用範圍內射頻卡片數日;Integ表示數值取整。

UID的位數越多(如ICODE達64位),每次傳送的時間加長,數據傳送的時間就會增大。如每次都傳輸完整的UID,每次時間為T,則用於傳輸UID的通信時間為:
t=TN
即終端作用範圍內射頻卡片數越多,UID位數越多,傳送時間越長,總的防碰撞執行時問肯定也就越長。

4.2 動態二進位搜索算法
動態二進位搜索算法考慮的是在UID位數不變的情況下,儘量減少傳輸的數據量,使傳送時間縮短,提高RFID系統的效率。其改進思路是把數據分成兩部分,收發雙方各自傳送其中一部分數據,可把傳輸的數據量減小到一半,達到縮短傳送時間的目的。

通常序列號的規模在8位元組以上。為選擇一個單獨的射頻卡,每次都不得不傳輸大量的數據,效率非常低。根據二進位搜索算法的思路進行改良,可以減少每次傳送的位數,也可縮短傳送的時間,從而縮短防碰撞執行時間。下面分析動態二進位搜索算法的工作過程。在例子中,射頻卡有3張,序列號分別是:卡1,11010111;卡2,11010101;卡3,11111101。

(1)動態二進位搜索算法的工作步驟

①讀寫器第一次發出一個完整的UID位數碼N,每個位上的碼全為l,讓所有射頻卡都發迴響應。
②讀寫器判斷有碰撞的最高位數X,把該位置O。然後傳輸N~X位的數據後即中斷傳輸。射頻卡接到這些數據後馬上響應,回傳的信號位是X一1~1。即讀寫器和射頻卡以最高碰撞位為界分別傳送前後信號。傳遞的總數據量可減小一半。
③讀寫器檢測第二次返回的最高碰撞位數X』是否小於前一次檢測回傳的次高碰撞位數。若不是,則直接把該位置「O」;若是,則要把前一次檢測的次高位也填「O」。然後向射頻卡發出信號。發出信號的位數為N~X』,射頻卡接收到信號這一級信號出現小於或等於相應數據時後馬上響應,回傳的信號只是序列號中最高碰撞位後的數。即X―l~l位。若射頻卡返回信號表示無碰撞,則對該序列號的射頻卡進行讀/寫處理,然後使其進入「不響應狀態」。
④重複步驟①,多次重複後可完成射頻卡的交換數據工作。

(2)動態二進位搜索算法與工作步驟相對應的示例

①例如N=8,傳送數據為11111111b。最高位為第8位,最低位為l位。根據響應可判斷第6位、第4位、第2位有碰撞。
②X=6,即第6位有碰撞,則傳送數據變為11011111b。傳送時,只傳送前面3位數11Ob。這時卡1和卡2響應,其序列號的前3位與射頻卡相同,不回傳,只回傳各自的後5位數據。卡1為lOlllb,卡2為10101b。可判斷第2位有碰撞。
③X』=2,根據要求第4位也要補零,則傳送數據變為110101O1b,傳送時只傳送110101Ob。這時只有卡2響應,並返回1b,表明無碰撞。讀寫器選中卡2進行數據交換,讀/寫完畢後卡2進行「休眠」。
④重複步驟①,按序可讀/寫卡1、卡3。
在動態二進位搜索算法的工作過程中,要注意通過附加參數把有效位的編號發送到射頻卡,從而保證每次響應的位置是正確的。

5 總 結
防碰撞是RFID技術中的一項重要技術。二進位搜索算法是基於TDMA的一種適用於閱讀區內射頻卡數量不多的情況。根據這一算法進行編程,結構比較簡單,容易實現防碰撞功能。採用動態二進位搜索方法可提高執行防碰撞的速度,實現高效率的控制。


相關焦點

  • 基於二進位搜索的RFID標籤防碰撞算法研究
    FDMA法的一個缺點是閱讀器的成本高,因為每個接收通路必須有自己的單獨接收器供使用,射頻標籤的差異更為麻煩。因此,這種防碰撞方法也限制在少數幾個特殊的應用上。  時分多路(TDMA)法是個整個可供使用的通路容量按時間分配給多個用戶的技術。TDMA法由於應用簡單,容易實現大量標籤的讀寫,所以一般的防碰撞算法主要以TDMA方式實現。對RFID系統來說,TDMA構成了防碰撞算法最大的一類。
  • 基於RFID的二進位防碰撞算法的改進
    2 傳統二進位算法   2.1 傳統二進位算法的基本原理   在二進位搜索算法中,要能夠檢測出多張卡的存在,卡片的返回數據必須具有唯一性,且卡片在傳輸其UID(Ubiquitous Identifications,身份識別標籤)時必須準確、快速、同步,這是防碰撞檢測的關鍵。
  • 如何在Python中進行二進位搜索?搜索算法,中級python技術點
    您將頁碼上限移動到新位置並更新中間索引:限制要搜索的頁面範圍的頁碼稱為下限和上限。在二進位搜索中,通常以第一頁作為下界,最後一頁作為上限。必須在運行時更新兩個邊界。例如,如果您所翻的頁面低於您要查找的頁面,則這是您的新下限。
  • 超高頻rfid技術的關鍵知識點分享
    下面我們就來簡要介紹下關於超高頻RFID的那些專利技術吧!該發明實現了超高頻射頻識別晶片的解調電路低功耗和低成本的並存。  防碰撞算法(Anti-Collision Algorithm)  1、2007年2月,深圳市當代通信技術有限公司申請的中國發明專利涉及一種超高頻遠距離自動識別系統中的多標籤防碰撞算法。
  • 最古老的記數法-二進位
    當人們開始用語言來表述一定的數目時,二進位被認為是最古老的記數法。它出現在人們還沒有用手指進行計數的時候,也就是在一隻手是低級單位,一雙手和一雙腳是高級單位之前的時候。今天,我們還可以找到二進位的痕跡。如我們用雙、對來計量。
  • 一道 LeetCode 題帶我們深入二進位表示、搜索策略和剪枝
    如果去掉這個條件就方便多了,因為每個元素只剩下了兩個狀態,要麼拿要麼不拿,我們可以用一個二進位的數來表示。這就引出了一個常用的表示狀態的方法——二進位表示法。二進位表示法舉個例子,假如當下我們有3個數字,這3個數字都有兩個狀態選或者不選,我們想要枚舉這3個數字的所有狀態,應該怎麼辦?我們當然可以用遞歸來實現,在每層遞歸當中做決策當前元素選或者不選,分別遞歸。
  • 如何實現二進位轉十進位的設計
    設計背景: 二進位轉十進位在設計應用中十分的廣泛。尤其在AD轉化中是必須所用到的一個小知識點,學習二進位轉十進位的方法顯的非常的重要。今天就和筆者來學習二進位轉十進位的方法,通過簡單的學習來掌握這麼一門知識。
  • 【二進位】----十進位數轉換成二進位數
    這樣由0--9十個數字來表示並且進位規則是「逢十進一」,借位規則是「借一當十」就是我們常說的十進位的數。你知道嗎?除了我們常見的十進位的數,還有二進位、五進位、八進位、十六進位和六十進位的數。今天我們來說說二進位。
  • 二進位、八進位、十進位、十六進位數的轉換方法
    一)、數制計算機中採用的是二進位,因為二進位具有運算簡單,易實現且可靠,為邏輯設計提供了有利的途徑、節省設備等優點,為了便於描述
  • 二進位與八進位互相轉換
    上節課我們學習了二進位轉換十進位,那二進位與常用的八進位之間是如何互相轉換的呢?下面我們先看看二進位與八進位的轉換方法。
  • scratch+程小奔機器人實現「進位轉換」(十進位轉二進位)
    也就說滿十進一;而在計算機的世界裡,基礎電路只有「開/關(通/斷)」(即0/1)兩種情況,這與誕生幾千年的二進位不謀而合;例如:二進位數字110,表達的就是十進位中的6;二進位數字1111,表達的就是十進位中的15。
  • 二進位與位運算
    二進位二進位(binary)在數學和數字電路中指以2為基數的記數系統,以2為基數代表系統是二進位制的。這一系統中,通常用兩個不同的符號0(代表零)和1(代表一)來表示 [1] 。數字電子電路中,邏輯門的實現直接應用了二進位,因此現代的計算機和依賴計算機的設備裡都用到二進位。每個數字稱為一個比特(Bit,Binary digit的縮寫)進位轉換十進位轉換為二進位一個十進位整數轉換為二進位數採用 "除2取餘,逆序排列"法。
  • 計算機基礎進位轉換(二進位、八進位、十進位、十六進位)
    1.十進位轉R進位1.1 十進位轉二進位十進位整數轉二進位十進位整數轉換成二進位採用「除2倒取餘」,十進位小數轉換成二進位小數採用
  • 二進位轉換為十進位和十進位轉換為二進位的方法
    各位小夥伴們大家好,在之前的文章中小編也介紹了關於二進位轉十進位的方法,這次小編知道了一個更簡單的方法,具體如下:比如我們要把28轉為二進位:28的二進位了。11100轉十進位還是從左到右,第一個數字1後面有4個數字,那麼就是2的4次方,之後一次類推知道2的0次方,再用相對應的次方乘以相對應的二進位數字就可以了,所以11100得到的十進位數字就是
  • 二進位與十六進位之間互相轉換
    通過上節課的學習,我們掌握了二進位與八進位互相轉換的方法(我們介紹的是421法),我們進行知識遷移,二進位數轉換成十六進位數的方法我們用
  • 二進位上的明文算法
    二、二進位表示法上面我們了解到了二進位在文本中的缺點,於是就需要想辦法把這個二進位轉換為可以明文儲存的字符。二進位在計算機中實際上就是01串, 所以我們自然可以想到使用01串來標示二進位。不過這裡具體的公式不好算,因為10進位和二進位不對等,所以一般我們都是使用二的整倍數來換算。四、經典的十六進位我們把二進位打入log中時,常用的就是十六進位表示法。我們使用二進位編輯器打開二進位文件時,也是使用十六進位表示法。
  • 二進位與兩元顛倒訣
    所以不需要背什麼口訣, 只要手上直接掐先天八卦, 像小六壬那樣的數法,很容易就記住了. 用先天八卦數, 乾一兌二離三震四巽五坎六艮七坤八, 如果將這些數進行爻間碰撞從而求取卦間的關係又如何? 兩個卦的碰撞, 雖然說是兩個卦間的關係, 但是可以分成體用來看待, 所以可以定義, 當兩個卦相歸藏時, 前面的一卦為, 後面的一卦客, 那麼就看客對主的關係, 會產生什麼樣的結果.
  • 二進位-八進位-十進位-十六進位之間的相互轉換
    -進位轉換,三個方面的知識,重新拿起書本,再查找資料,匯總信息如下:01:二進位-轉為-八進位//方法://每3位為一組,因為8進位數,需要3bit數據表示0~7,逢八進一;案例1:(1100 1110)2=(11 001 110)2=(316)802:二進位
  • 計算機為什麼用二進位?
    熟悉編程的人都知道二進位總是一個讓人晦澀難懂的詞彙,只有大神級的程式設計師才有資格把玩它。 我們今天來重新認識一下二進位,了解編程中的數學知識和計算機為什麼使用二進位?上面的規則我們在小學數學都學過了,日常生活中也一直在用,是眾所周知的常識。 在此權當複習,下面我們將通過實例來了解一下10進位計數法。分解1024首先,我們以 1024 這個數為例。
  • 【S7-200】二進位、八進位、十進位、十六進位數的轉換方法
    S7-300 QQ群: 385453109 EPLAN QQ群: 239317903 一 、數制 計算機中採用的是二進位,因為二進位具有運算簡單,易實現且可靠,為邏輯設計提供了有利的途徑、節省設備等優點,為了便於描述,又常用八、十六進位作為二進位的縮寫。