国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

一種快速獲取同頻數(shù)據(jù)的防碰撞算法

2014-09-19 01:32:04凱,李冰,劉勇,趙霞,張
電子與封裝 2014年2期
關(guān)鍵詞:二叉樹閱讀器指針

鄭 凱,李 冰,劉 勇,趙 霞,張 林

(東南大學(xué)集成電路學(xué)院,江蘇 無錫 214035)

1 引言

433 MHz頻段下的標(biāo)簽識(shí)別是一種使用標(biāo)簽進(jìn)行無線數(shù)據(jù)存儲(chǔ)和檢索的自動(dòng)識(shí)別技術(shù)。一旦無線信號(hào)在接收范圍之內(nèi),處在433 MHz頻段下的標(biāo)簽?zāi)軌蝽憫?yīng)來自于閱讀器特定頻段的序列。與早期的二進(jìn)制編碼技術(shù)不同,433 MHz頻段下的標(biāo)簽識(shí)別不需要近距離的接觸。由于該技術(shù)相比二進(jìn)制編碼技術(shù)能夠提供絕對(duì)的靈活度,該靈活度可以很好地對(duì)各類土地的地形分布數(shù)量等特征進(jìn)行測量,因此該技術(shù)被廣泛應(yīng)用于土地測量領(lǐng)域。

在一個(gè)433 MHz的系統(tǒng)中,閱讀器識(shí)別區(qū)域內(nèi)可能存在多個(gè)標(biāo)簽,為了識(shí)別所有的標(biāo)簽,該系統(tǒng)需要一個(gè)通訊協(xié)議。因?yàn)樵陂喿x器和標(biāo)簽之間的數(shù)據(jù)傳輸都是在一個(gè)共享的無線頻段上的,所以當(dāng)不止一個(gè)標(biāo)簽與閱讀器進(jìn)行通訊時(shí)就產(chǎn)生了沖突。這些通訊協(xié)議被統(tǒng)稱為防碰撞算法。目前存在兩種防碰撞算法:確定性算法和隨機(jī)性算法。確定性算法都是基于二叉樹的算法,例如質(zhì)詢二叉樹算法(QT)和防碰撞二叉樹算法(CT)。基于二叉樹的算法通常都是將整個(gè)標(biāo)簽分成兩個(gè)子類別,以此類推,直到把所有的標(biāo)簽都識(shí)別出來。而隨機(jī)算法則是基于時(shí)分復(fù)用的算法的,其主要的思想是強(qiáng)制設(shè)定不同標(biāo)簽的響應(yīng)時(shí)間從而避免了碰撞的發(fā)生。以上這兩種算法都存在著自身的優(yōu)點(diǎn)和缺陷。

由于433 MHz系統(tǒng)的整體性能絕大部分取決于系統(tǒng)中所使用的特定的防碰撞算法,因此對(duì)于433 MHz系統(tǒng)來說,一個(gè)好的碰撞算法是十分重要的。通常來說,判斷一個(gè)防碰撞算法好壞的標(biāo)準(zhǔn)包括這個(gè)算法需要多少個(gè)周期將所有的標(biāo)簽都識(shí)別出來,算法的復(fù)雜程度以及傳輸?shù)臄?shù)據(jù)量的大小。因此,一個(gè)較好的防碰撞算法應(yīng)具備以下特征:較少的識(shí)別周期,計(jì)算簡單,資源消耗少,能耗低,識(shí)別速率快。

本文采用改進(jìn)型碰撞二叉樹(ICT)的快速防碰撞算法。在標(biāo)簽識(shí)別中,ICT算法在每一個(gè)標(biāo)簽中引入了一個(gè)計(jì)數(shù)器和指針,用于記錄閱讀器之前發(fā)送的序列差異。由于存在了計(jì)數(shù)器和指針,因此閱讀器不需要傳輸整個(gè)序列,閱讀器只需要傳輸上次已經(jīng)識(shí)別的后一個(gè)bit位,這樣便大大減少了閱讀器和標(biāo)簽之間的數(shù)據(jù)傳輸量。

2 改進(jìn)型碰撞二叉樹算法

2.1 改進(jìn)型碰撞二叉樹算法簡介

在ICT算法中,曼徹斯特編碼用于查找沖突的比特位。為了能夠精確查找沖突的比特位,假設(shè)所有識(shí)別區(qū)域內(nèi)的標(biāo)簽?zāi)軌蛲瑫r(shí)響應(yīng)閱讀器序列中的質(zhì)詢位。這里所講的序列中的質(zhì)詢位指的是上次已經(jīng)查詢過的前綴的后一個(gè)bit,閱讀器可以通過這一個(gè)質(zhì)詢位來將所有的標(biāo)簽區(qū)別開來,而不需要前面的前綴序列。閱讀器中有一個(gè)用于存儲(chǔ)前綴序列的堆棧,并且在每一個(gè)標(biāo)簽中都有狀態(tài)寄存器(SC)和指針寄存器(Pointer),狀態(tài)寄存器用于分類標(biāo)簽,只有當(dāng)狀態(tài)寄存器為0時(shí)標(biāo)簽才會(huì)響應(yīng);指針用于指向與當(dāng)前bit對(duì)比的那個(gè)標(biāo)簽bit位,只有當(dāng)標(biāo)簽比對(duì)正確的時(shí)候才向閱讀器發(fā)出響應(yīng)信號(hào)。也就是說,標(biāo)簽的響應(yīng)是從當(dāng)前bit位的后一位一直持續(xù)到序列結(jié)束的最后一位為止。當(dāng)閱讀器接收到了標(biāo)簽的響應(yīng)信號(hào)后,會(huì)發(fā)出一個(gè)反饋信號(hào),并且所有的標(biāo)簽根據(jù)這個(gè)反饋信號(hào)自行調(diào)整標(biāo)簽中的狀態(tài)寄存器和指針。

2.2 改進(jìn)型防碰撞二叉樹算法的實(shí)現(xiàn)

在初始化階段中,堆棧中是空的,不存在任何內(nèi)容,而標(biāo)簽中的指針指向了標(biāo)簽ID的最高位,隨著不斷地識(shí)別操作,指針逐漸向后面的bit位移動(dòng);狀態(tài)寄存器中的值為0,即說明所有的ID當(dāng)前bit匹配的標(biāo)簽都應(yīng)當(dāng)響應(yīng)閱讀器的序列。由于在等待周期中不會(huì)有任何的標(biāo)簽響應(yīng)閱讀器,因此ICT可以省略掉等待的周期,所以只存在兩種處理周期:識(shí)別和碰撞周期。

關(guān)于這兩個(gè)周期的定義如下:

(1)識(shí)別周期是指有且只有一個(gè)標(biāo)簽的狀態(tài)寄存器值為0,并且當(dāng)前的bit位與閱讀器序列中的匹配;

(2)碰撞周期是指有不止一個(gè)標(biāo)簽的狀態(tài)寄存器的值為0,并且當(dāng)前的bit位與閱讀器序列中的匹配。

在ICT中,閱讀器需要通過傳輸目前前綴序列的后一個(gè)bit位(當(dāng)前序列的后一個(gè)bit)來區(qū)分所有的標(biāo)簽,只有那些狀態(tài)寄存器為0并且與ID中的前綴序列相同的標(biāo)簽才響應(yīng)閱讀器。當(dāng)那些滿足狀態(tài)寄存器為0并且當(dāng)前指針指向的bit位與前綴序列中的bit相同時(shí)則將ID中余下的bits發(fā)送給閱讀器。而閱讀器則根據(jù)接收到的信號(hào)來判決該返回信號(hào)對(duì)應(yīng)的正確操作。當(dāng)發(fā)生碰撞時(shí),閱讀器則根據(jù)沖突的那個(gè)bit位產(chǎn)生兩個(gè)新的前綴序列并且將其壓入堆棧中。與此同時(shí),閱讀器從堆棧中獲取新的前綴并且反饋相應(yīng)信號(hào)。如果沒有碰撞時(shí),閱讀器則能夠識(shí)別出當(dāng)前的序列對(duì)應(yīng)的標(biāo)簽,其對(duì)應(yīng)的ID就是當(dāng)前的前綴序列和閱讀器收到的剩余ID的bits。在后面時(shí)間里,閱讀器則可以通過這個(gè)ID號(hào)進(jìn)一步和已經(jīng)識(shí)別的標(biāo)簽進(jìn)行數(shù)據(jù)的交換傳輸,在此之后,同樣的,閱讀器從堆棧中獲取新的前綴并且反饋相應(yīng)的信號(hào)。而那些不對(duì)閱讀器進(jìn)行響應(yīng)的標(biāo)簽則相應(yīng)地改動(dòng)內(nèi)部的狀態(tài)寄存器。在這個(gè)過程中,簡單的對(duì)狀態(tài)寄存器進(jìn)行+1操作是遠(yuǎn)遠(yuǎn)不夠的,因?yàn)檫@可能會(huì)導(dǎo)致在處理過程中插入較多的等待周期。為了有效避免等待周期,在每一個(gè)標(biāo)簽中都設(shè)置了一個(gè)Flag標(biāo)記符。Flag用于標(biāo)注上一個(gè)判別周期的狀態(tài),F(xiàn)lag=1意味著上一個(gè)判別周期是識(shí)別周期。如果Flag=1,那么在當(dāng)前的判別狀態(tài)下,狀態(tài)寄存器不變;反之,當(dāng)Flag=0,則將狀態(tài)寄存器中的值加1。當(dāng)標(biāo)簽收到閱讀器的反饋信號(hào)的時(shí)候,則將Flag重新置位。

反饋信號(hào)用于通知所有標(biāo)簽當(dāng)前閱讀器的識(shí)別狀態(tài),由于識(shí)別過程中存在兩種周期,因此閱讀器發(fā)送兩種類型的反饋。根據(jù)不同類型的反饋信號(hào),標(biāo)簽做出如下的響應(yīng):

識(shí)別:所有的標(biāo)簽都將狀態(tài)寄存器中的值-1并且將Flag設(shè)置為1,直到再次將狀態(tài)寄存器-1時(shí)其值變?yōu)?1,則表明,當(dāng)前的標(biāo)簽處于靜默狀態(tài),并且不再繼續(xù)響應(yīng)閱讀器的序列。

碰撞:這一種類型的反饋信號(hào)中包括了一個(gè)參數(shù)k,表明當(dāng)前接收的新的前綴長度(bit)。當(dāng)標(biāo)簽接收到這種類型的反饋信號(hào)時(shí)則設(shè)置狀態(tài)寄存器為0,并且將指針設(shè)置為k-1個(gè)bit的位置,將Flag設(shè)置為0。

圖1所示的是ICT算法流程圖。表1中列舉了一個(gè)使用ICT識(shí)別4個(gè)標(biāo)簽的過程,四個(gè)標(biāo)簽分別為0001、0010、1100和1111。

表1 采用ICT識(shí)別4個(gè)標(biāo)簽

圖1 ICT算法流程

3 性能對(duì)比

將ICT算法和參考文獻(xiàn)[4]中的CT算法就通信開銷和識(shí)別速度兩個(gè)方面進(jìn)行對(duì)比,ICT中的一些性能參數(shù),例如識(shí)別一個(gè)標(biāo)簽消耗的時(shí)間和識(shí)別效率與參考文獻(xiàn)[4]中是一樣的。

通信開銷被定義為單位時(shí)間內(nèi)通過閱讀器的平均bit的數(shù)量和識(shí)別一個(gè)標(biāo)簽耗費(fèi)的時(shí)間,識(shí)別速度定義為識(shí)別標(biāo)簽的平均數(shù)量/s。數(shù)據(jù)信道的數(shù)據(jù)傳輸速率設(shè)置為96 kbps。并且使用一個(gè)bit定義了兩種不同類型的反饋信號(hào)(1表示識(shí)別,0表示沖突),在沖突周期中,變量k的長度不能大于7 bits。

主要從以下三個(gè)不同方面對(duì)提出的算法進(jìn)行了仿真和性能評(píng)估。

初次實(shí)驗(yàn)中,使用ICT和CT算法分別識(shí)別一些標(biāo)簽,標(biāo)簽的數(shù)量從2個(gè)至512個(gè)之間變化,ID的長度設(shè)置為96 bits,并且這些標(biāo)簽的ID都是隨機(jī)產(chǎn)生的,盡管在ICT算法中使用一些技術(shù)避免傳輸不必要的bits,但是其性能并非如同之前所期望的那樣好,ICT只能夠取得與CT算法等同的性能。通過對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析,發(fā)現(xiàn)由于標(biāo)簽ID是完全隨機(jī)離散的,因此每一個(gè)標(biāo)簽都有一個(gè)十分獨(dú)特互不相關(guān)的ID,幾乎所有標(biāo)簽的開始8個(gè)bits都是不一樣的,因此在使用CT算法的時(shí)候并不需要大量傳輸標(biāo)簽的ID。故此,在本次的測試中,并不能完全體現(xiàn)出ICT的優(yōu)越性。

經(jīng)由上述的試驗(yàn)分析,可以看出盡管ICT算法在算法的層面上對(duì)CT進(jìn)行了大量的改進(jìn),但取得的性能卻并不能達(dá)到我們預(yù)期的效果。而導(dǎo)致這一現(xiàn)象主要的原因是隨機(jī)生成的ID在最開始的幾個(gè)bits是高度離散不相關(guān)的,因此ICT算法并沒有得到很高的發(fā)揮。

在接下來的實(shí)驗(yàn)中,每一個(gè)標(biāo)簽都有一個(gè)高度相關(guān)的識(shí)別前綴。在本次實(shí)驗(yàn)中,仍然使用ICT和CT兩種算法識(shí)別256個(gè)標(biāo)簽,每個(gè)標(biāo)簽ID的長度都是96 bits,并且每一個(gè)標(biāo)簽都有一個(gè)彼此相關(guān)的識(shí)別前綴,這個(gè)前綴的長度在4~80 bits之間不等,而ID中其余剩下的bits都是隨機(jī)產(chǎn)生的。如圖2所示是本次實(shí)驗(yàn)的結(jié)果。從圖2(a)我們可以清楚看到ICT的優(yōu)越性,并且隨著識(shí)別前綴的長度的不斷增加,相比CT算法其性能愈加明顯。這是由于在CT算法中閱讀器需要傳輸整個(gè)識(shí)別序列,而在使用ICT算法的時(shí)候,閱讀器只需要傳輸當(dāng)前的bit。圖2(b)所示是兩種算法的識(shí)別速度,ICT能夠明顯獲得快于CT算法的速度,試驗(yàn)說明ICT算法比CT算法更適合前綴相關(guān)的序列的標(biāo)簽識(shí)別。

4 結(jié)論

本文提出了一種用于土地地形分布特征測量的ICT快速獲取同頻數(shù)據(jù)的防碰撞算法。這種算法是從CT算法中衍生而來,通過某些技術(shù)方式避免了傳輸不必要的數(shù)據(jù)。本文的創(chuàng)新點(diǎn)是根據(jù)碰撞原理找到碰撞的具體位置之后,在這些碰撞的位置后面加上一位或者多位比特來增加質(zhì)詢前綴,減少質(zhì)詢位數(shù)而增加質(zhì)詢效率。實(shí)驗(yàn)結(jié)果表明ICT能夠在ID前綴序列相關(guān)的情況下獲得比CT算法更好的性能。ICT算法可以被應(yīng)用到433 MHz土地測量系統(tǒng)中來解決碰撞問題,同時(shí)可以獲得優(yōu)于CT算法的性能。

圖2 前綴序列的仿真結(jié)果

[1]L Zhu,T S P Yum.IEEE Communications Magazine[J].2011,49:214.

[2]M A Bonuccelli,F Lonetti,F Martelli.Ad Hoc Networks[J].2007,5:1220.

[3]J H Choi,D Lee,H Lee.IEEE Communications Letters[J].2007,11:85.

[4]X Jia,Q Feng,C Ma.IEEE Communications Letters[J].2010,14:1014.

[5]J Myung,W Lee,J Srivastava.IEEE Communications Letters[J].2006,10:144.

[6]K Finkenzeller.RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,Second Edition[M].John Wiley & Sons,2003.Chapter 7.

[7]F Schoute.IEEE Transactions on Communications[J].1983,31: 565.

[8]K C Shin,S B Park,G S Jo.Sensors[J].2009,9: 845.

猜你喜歡
二叉樹閱讀器指針
CSP真題——二叉樹
基于反向權(quán)重的閱讀器防碰撞算法
二叉樹創(chuàng)建方法
偷指針的人
一種高效的RFID系統(tǒng)冗余閱讀器消除算法
為什么表的指針都按照順時(shí)針方向轉(zhuǎn)動(dòng)
一種由層次遍歷和其它遍歷構(gòu)造二叉樹的新算法
一種RFID網(wǎng)絡(luò)系統(tǒng)中消除冗余閱讀器的高效算法
基于改進(jìn)Hough變換和BP網(wǎng)絡(luò)的指針儀表識(shí)別
電測與儀表(2015年5期)2015-04-09 11:30:42
ARM Cortex—MO/MO+單片機(jī)的指針變量替換方法
高邮市| 科尔| 丹阳市| 溧阳市| 富平县| 海晏县| 分宜县| 裕民县| 得荣县| 宁城县| 丰台区| 蓬莱市| 佳木斯市| 棋牌| 镇赉县| 玉山县| 茌平县| 师宗县| 密云县| 东城区| 陕西省| 哈密市| 新竹市| 玛沁县| 阳新县| 灵璧县| 满洲里市| 堆龙德庆县| 万全县| 扶绥县| 化德县| 聂拉木县| 宝丰县| 阿克| 阳春市| 北安市| 清新县| 毕节市| 新和县| 陇西县| 靖西县|