當前位置:首頁 > 通信技術 > 通信技術
[導讀]本文針對RFID技術日益嚴重的標簽沖撞問題,指出對一般沖突情況,可用動態(tài)調(diào)整搜索法進行防沖撞,并通過對比表明該算法能有效應用于ISO/IEC 18000-6B相關協(xié)議的RFID系統(tǒng)中,而當具備一定先驗知識,了解到待識別標簽卡號滿足一定連續(xù)性,且數(shù)量較大時,可用輪詢算法進行有效的防沖撞處理。

射頻識別(RFID)技術是近幾年發(fā)展起來的一種自動識別技術。RFID系統(tǒng)一般通過閱讀器識別帶有唯一電子產(chǎn)品代碼(ID)值的標簽。閱讀器射頻場范圍內(nèi)標簽數(shù)量較多時不同標簽返回數(shù)據(jù)發(fā)生重疊,導致閱讀器對接收信號解碼錯誤,可以將其稱為標簽沖撞。由于TDMA時分多址方式應用簡單,容易實現(xiàn)大量標簽數(shù)據(jù)讀寫,因此被多數(shù)防沖撞算法采用。現(xiàn)有防沖撞算法主要包括ALOHA算法和樹分叉算法兩種。當大量標簽并存時,ALOHA算法[1]的幀沖撞嚴重,易引起性能急劇惡化,不適宜大規(guī)模標簽讀取。所以,主要發(fā)展樹分叉算法。目前樹分叉算法主要有ISO/IEC 18000-6B的類二進制搜索算法[2]、后退式二進制樹形搜索算法[3]。本文設計了一種標簽防沖撞算法。

1 基于標簽卡號無序性的防沖撞算法

  對于如公路收費亭的車輛識別,標簽的卡號是無序的(相互間不關聯(lián)),此時用動態(tài)調(diào)整二進制樹形搜索法,能快速實現(xiàn)標簽數(shù)據(jù)讀寫。該算法用Manchester編碼準確判別位碰撞,并保持后退式二進制樹算法的后退機理。

  1.1 Manchester編碼與防沖撞

  該編碼采用以下規(guī)則:

  (1)邏輯“1”表示下降沿跳變。
  (2)邏輯“0”表示上升沿跳變。
  (3)若無狀態(tài)跳變,作為錯誤被識別。
  當多個標簽同時返回的數(shù)位有不同之值時,上升和下降沿互相抵消,以至無狀態(tài)跳變,閱讀器知該位出現(xiàn)碰撞,產(chǎn)生了錯誤。
      利用Manchester編碼識別碰撞位,如圖1所示。假如有兩個標簽,其ID號為10011111和10111011,利用Manchester可識別出D5和D2位碰撞。
  (a)標簽1的ID為10011111
  (b)標簽2的ID為10111011
  (c)閱讀接收的ID碰撞為10×11×11


  1.2 防碰撞指令規(guī)則

  (1)Request(DATA),請求指令。DATA長度小于或等于標簽ID長度。ID值與DATA匹配的標簽回送其ID值給閱讀器。如Request(10)表示ID開始兩位為10的所有標簽應答。并規(guī)定發(fā)送Request(1)后射頻場內(nèi)所有非“靜默”狀態(tài)下的標簽都應答。

  (2)Select(ID),選擇指令。與Select攜帶ID值相同的標簽被激活,該ID值與標簽ID值長度相同。

  (3)Read-Write,讀寫指令。讀寫被Select激活的標簽。

  (4)Quiet(DATA),靜默指令。對匹配標簽進行靜默操作,使其不對閱讀器任何指令作出反應。當標簽離開閱讀器的作用范圍(等于沒有供應能量)后復位。

  1.3 動態(tài)調(diào)整二進制樹形搜索法

  1.3.1 算法機理

  該算法保持后退式二進制樹形搜索算法[3]的后退機理:

  碰撞發(fā)生時,根據(jù)碰撞的最高位,跳躍式向前搜索;無碰撞時,采取后退策略,實現(xiàn)標簽的有序讀取。但具有以下2個特點:
  (1)指令長度動態(tài)調(diào)整,只發(fā)送位數(shù)高于或等于沖突位的指令位。

  (2)基于一位沖突直接識別,當只探測到一位碰撞位時,可直接識別出2個標簽ID數(shù)據(jù)。如射頻場內(nèi)有兩個標簽10101101, 10100101,閱讀器探測到的返回數(shù)據(jù)為1010x101,因為只有一位沖突位,所以閱讀器可直接確定射頻場存在2個標簽10101101, 10100101。

  1.3.2 算法步驟

  (1)閱讀器發(fā)送Request(1),區(qū)域內(nèi)所有標簽應答。

  (2)檢測是否有1位碰撞發(fā)生。當無碰撞或只有1位碰撞位時,直接識別標簽。若有多位碰撞發(fā)生,將碰撞的最高位置0,高于該位的數(shù)值位不變,低于該位的數(shù)值位忽略,得到下一次Request命令所需的DATA參數(shù)。重復步驟(2)直到識別出兩個標簽。

  (3)識別標簽后,根據(jù)確知的ID值對標簽逐個進行Select激活,然后根據(jù)需要進行Read-Write操作,之后用Quiet指令使該標簽進入靜默狀態(tài)屏蔽掉。并判斷剛才發(fā)送指令是否為Request(1),若為Request(1)則發(fā)送結束。否則,下一次Request命令的DATA參數(shù),采用后退策略,由其相鄰的上次發(fā)送指令確定,繼續(xù)步驟(2)。

  1.3.3 算法實現(xiàn)

  假設ID值為8位,閱讀器作用范圍內(nèi)有8個標簽。開始時,閱讀器對區(qū)域內(nèi)標簽處于未知狀態(tài),發(fā)送Request(1),令區(qū)域內(nèi)所有標簽應答,具體的查詢過程如表1所示。

  表1 動態(tài)調(diào)整搜索法標簽查詢過程


  在表1中,“xx”表示碰撞位;“------”表示標簽不響應;“^^^^”表示標簽已被屏蔽為靜默狀態(tài)。每次查詢出ID值后即對標簽進行屏蔽。當?shù)?次執(zhí)行指令為Request(1)全返回指令,而只有2個標簽應答,可知所有標簽查詢完畢。此時可據(jù)確知的8個標簽ID值,按需進行其他操作。從表1可知用動態(tài)調(diào)整搜索法識別8個標簽只需發(fā)送7次指令,而后退式算法[3]需要2×8-1=15次。可見動態(tài)調(diào)整搜索法的工作效率有了很大改進。

  1.4 算法性能分析

  由于動態(tài)調(diào)整搜索法是基于后退式算法[3],因此在最不理想的情況下,也可保持N個標簽的查詢次數(shù)為S(N)=2N-1 。當射頻場中碰撞的標簽數(shù)量N較大,此時識別出1位碰撞的幾率較大。設在整個識別過程中探測到M次只有1個碰撞位,通過動態(tài)調(diào)整算法的直接識別相當于比后退式算法減少了2M次查詢指令,此時查詢次數(shù)為
      S(N)=2(N-M)-1

  系統(tǒng)的有效服務率即吞吐率為
      K=N/S(N)=N/(2N-2M-1)

  將動態(tài)調(diào)整搜索法與類二進制搜索法[2],后退式算法[3]在ISO/IEC 18000-6B協(xié)議[2]的應用中進行查詢次數(shù)的比較。為保持與協(xié)議規(guī)范一致,將使用協(xié)議相關功能指令GROUP_SELECT_EQ, READ/WRITE, DATA_READ [2] 分別取代第1.2節(jié)的指令Request, Read-Write, Quiet同時用FM0編碼[2]取代Manchester碼。假設標簽ID長度為16,用Matlab編程可得到仿真結果的比較如圖2所示。



圖2 算法的防沖撞性能比較

  由圖2可知,當標簽數(shù)量較少時,探測到一位碰撞幾率不大,動態(tài)調(diào)整算法比后退式算法只有稍微優(yōu)勢,而當標簽數(shù)量明顯增多時,標簽ID值比較接近,探測到一位碰撞的幾率較大,M較大,動態(tài)調(diào)整算法效率明顯優(yōu)于后退式算法。而ISO/IEC 18000-6B協(xié)議的類二進制搜索算法是隨機產(chǎn)生0,1信號進行搜索,不能實現(xiàn)有效的有序性讀取,仿真結果也表明其識別能力顯著低于動態(tài)調(diào)整搜索法。可見,動態(tài)調(diào)整搜索法可被有效用于ISO/IEC 18000-6B協(xié)議的標簽沖突問題解決。

  尤其當2 L 個標簽第1次發(fā)送Request(1)識別指令只探測出L個碰撞位時,可知識別過程中將出現(xiàn)連續(xù)的1位碰撞,此時M=2 L /2=2 L-1 ,S(N)=2(2 L -2 L-1)-1=2 L -1,K=2 L/S(N)=1。對比后退式算法需要發(fā)送S(2 L )=2 L+1-1次查詢指令,而系統(tǒng)吞吐率為K=0.5。動態(tài)調(diào)整算法在最優(yōu)情況下,效率是后退式算法的倍數(shù)。同時,動態(tài)調(diào)整算法對指令長度進行了動態(tài)調(diào)整,可以有效地減小發(fā)送信息量提高發(fā)送速率。

  2 基于標簽卡號連續(xù)性的防沖撞算法

  對于如倉庫的貨物管理,每一批貨物內(nèi)標簽卡號基本上是連續(xù)的,此時可用另一種防沖撞算法基于一位碰撞直接識別的輪詢算法快速識別標簽[4]。

  2.1 輪詢算法

  該算法保持發(fā)送指令和Manchester編碼不變。(1)發(fā)送Request(1),利用Manchester編碼確定碰撞位的具體位置得到L個碰撞位;(2)將除最低碰撞位的L-1個碰撞位看作一個二進制數(shù)H,從0~2 L−1遞增,得DATA;(3)每次發(fā)完Request(DATA)后,H自增"1",得出新的DATA,即實現(xiàn)一個輪詢過程。具體過程如表2所示。

  表2 輪詢算法查詢過程


  對于表2的8個標簽,用輪詢算法只需發(fā)送5次查詢指令,用動態(tài)調(diào)整搜索法要發(fā)送7次指令,而用后退式算法需發(fā)送15次??梢?,對于卡號連續(xù)的情況,輪詢算法能更有效地實現(xiàn)標簽防沖撞。

  2.2 算法性能分析

  對于卡號連續(xù)的N個標簽,探測到L個碰撞位時,發(fā)送的查詢指令次數(shù)為
  S(N)=2 L-1+1

  系統(tǒng)的有效服務率即吞吐率為
  K=N/S(N)=N/(2 L-1+1)

  可知查詢次數(shù)S(N)只與碰撞位數(shù)L有關,而與標簽總數(shù)無關,吞吐率K不僅與碰撞位數(shù)有關還與標簽總數(shù)有關。特別地,令待識別的標簽卡號從0開始,與1.3節(jié)介紹的動態(tài)調(diào)整算法的比較如表3所示。

  表3 算法比較


  從表3可看出在最優(yōu)情況下,輪詢算法可使吞吐率K達到2,而動態(tài)調(diào)整搜索法的最優(yōu)吞吐率K為1,后退式算法[3]的吞吐率K為0.5??梢?,輪詢算法具有很大的應用潛力。

  根據(jù)式(4)可畫出吞吐率K與標簽數(shù)量N和碰撞位數(shù)L的關系曲線,如圖3所示。

  從圖3可看出,標簽數(shù)量較少,而碰撞位數(shù)卻很大時,吞吐率較低,此時不適合用輪詢算法。這種缺陷可稱為Hamming懸崖(Hamming cliffs),相鄰整數(shù)的二進制編碼可能具有較大的Hamming距離。例如2個標簽卡號分別為01111和10000,碰撞位數(shù)為5,要輪詢25-1+1=17次才讀完這兩標簽,可見效率很低。從圖3可看出只有標簽數(shù)量較大時,吞吐率K受碰撞位數(shù)影響不大,能克服Hamming懸崖,此時K基本介于1~2之間,效果比動態(tài)調(diào)整搜索法最優(yōu)吞吐率K=1要好。

  對于卡號連續(xù)的標簽,并不要求嚴格連續(xù),只要大部分標簽卡號滿足一定的連續(xù)性就可有效使用輪詢算法。另外,輪詢算法只需使用一次Manchester編碼識別碰撞位,則只需按照規(guī)則發(fā)送指令,能夠大大降低系統(tǒng)設計的復雜性。

3 結束語

  本文針對RFID技術日益嚴重的標簽沖撞問題,指出對一般沖突情況,可用動態(tài)調(diào)整搜索法進行防沖撞,并通過對比表明該算法能有效應用于ISO/IEC 18000-6B相關協(xié)議的RFID系統(tǒng)中,而當具備一定先驗知識,了解到待識別標簽卡號滿足一定連續(xù)性,且數(shù)量較大時,可用輪詢算法進行有效的防沖撞處理。

本站聲明: 本文章由作者或相關機構授權發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權最終是由生態(tài)的繁榮決定的。

關鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領增長 以科技創(chuàng)新為引領,提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術學會聯(lián)合牽頭組建的NVI技術創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術創(chuàng)新聯(lián)...

關鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關鍵字: BSP 信息技術
關閉
關閉