陳昊+高勤+安錫文
摘 要:在RFID系統(tǒng)中,多標簽同時存在會引發(fā)標簽碰撞問題,文章首先分析已識別標簽的情況,對剩余標簽的個數(shù)進行了估計,并依此動態(tài)匹配最佳幀長。為了進一步提高系統(tǒng)的識別效率,構造了合適的哈希函數(shù),將標簽集合均勻地映射到幀時隙集合,降低了標簽的沖突率。仿真表明,該算法提高了系統(tǒng)的吞吐率和穩(wěn)定性,對Aloha算法的后續(xù)研究工作以及工程實踐應用具有一定的參考價值。
關鍵字:動態(tài)幀時隙;Aloha算法;防碰撞;哈希函數(shù);標簽估計
1 RFID概述
無線射頻識別(Radio Frequency Identification,RFID)作為新型無線非接觸式自動識別技術[1],具有存儲容量大、識別速度快和安全系數(shù)高等優(yōu)點,被作為感知層的關鍵技術廣泛應用于物流、銷售和定位等領域,并作為物聯(lián)網(wǎng)領域的核心技術之一,得到極大關注[2]。
RFID系統(tǒng)一般由讀寫器、電子標簽以及應用軟件系統(tǒng)組成。系統(tǒng)在工作的時候,讀寫器與標簽之間利用電磁信號進行數(shù)據(jù)交換。當多個標簽共用相同的信道時,信號在空中媒介發(fā)生干擾,就會引發(fā)碰撞,導致標簽識別和數(shù)據(jù)傳送失敗。為了減小和消除這種碰撞問題,保證數(shù)據(jù)在傳輸過程中的完整性,許多科研工作者對RFID中的防碰撞機制進行了大量深入的研究。
目前,應用較廣泛的防碰撞算法大多基于時分多址接入(Time Division Multiple Access,TDMA),主要有如下兩類:基于二叉樹的確定性算法和基于Aloha的概率性算法[3-5]。前者優(yōu)點是能識別出所有標簽,沒有遺漏現(xiàn)象,但是對讀寫器硬件要求較高且算法的空間和時間復雜度較高。后者是Aloha及其改進算法,標簽隨機選擇時隙與讀寫器通信,復雜度小且容易實現(xiàn),但存在一定概率的某一標簽長時間內所選擇的時隙均發(fā)生碰撞,在有效時間內無法被讀寫器識別,存在標簽“饑餓”問題?;贏loha的防碰撞算法主要包括純Aloha(Pure Aloha,PA)、時隙Aloha( Slotted Aloha,SA)、幀時隙Aloha(Framed Slotted Aloha,F(xiàn)SA)、動態(tài)幀時隙Aloha(Dynamic Frame Slotted Aloha,DFSA)等。其中,DFSA算法可以根據(jù)實際的標簽數(shù)目動態(tài)地調整幀長度,其識別速度快,可使信道吞吐率達到最大,所以應用也最為廣泛。由于在實際情況下,標簽數(shù)量通常是未知的,所以如何估計標簽數(shù)目是決定系統(tǒng)吞吐率的關鍵。本文在此基礎上,首先統(tǒng)計已識別標簽的數(shù)據(jù)情況,通過對剩余標簽的數(shù)目進行估計,并構造合適的哈希函數(shù)對標簽進行時隙分配,減少了標簽隨機選擇時隙帶來的誤差,直到所有的標簽被正確識別。
2 時隙基本定義
在基于Aloha的算法中,將時間分成很多小時間段,每一段稱為時隙,多個時隙組成一幀,每幀包含的時隙個數(shù)稱為幀長度。對于一個給定的時隙,存在以下3種結果:空閑時隙(Idle Slot,IS),即沒有任何標簽選擇在該時隙進行回復;成功時隙,當前時隙中僅有一個標簽參與回復,讀寫器成功識別該標簽;碰撞時隙,存在兩個及兩個以上標簽在該時隙進行回復,
此時會產(chǎn)生數(shù)據(jù)碰撞。如圖1所示。
假設讀寫器范圍內有8個標簽,幀長為8,即每幀中含有8個時隙,各標簽在每幀中隨機選取一個時隙發(fā)送信息。通過讀寫器和標簽的一系列命令和回應之后,出現(xiàn)如圖1所示情況,根據(jù)定義,可知時隙1,4,7為成功時隙,時隙2,6為碰撞時隙,時隙3,5,8為空閑時隙,也即標簽1,3,7被成功識別;標簽2,5發(fā)生碰撞,標簽4,6,8發(fā)生碰撞,并且由此可知,標簽識別過程中,空閑時隙和碰撞時隙出現(xiàn)的概率很高。
3 時隙算法說明
3.1 標簽選擇時隙方法
在RFID系統(tǒng)中,標簽數(shù)目一般很多,在幾十至幾千個之間,由于標簽選擇時隙具有一定的隨機性,如果不能合理地安排時隙,那么由于效率低而造成的時間開銷損失會非常嚴重。防碰撞算法的實質是減少時隙的碰撞。通過構造合適的函數(shù),確定標簽選擇時隙的基準,使得標簽能根據(jù)一定的算法均勻地分布到各個時隙,降低標簽空閑及碰撞情況。
每個標簽都有唯一的識別碼(UID),其包含了標簽的基本信息,文中采用計算量較小的除留余數(shù)法構造的哈希函數(shù)[6],滿足了簡單均勻的要求,具體計算公式為:
Hash(ID)=[ID/w] mod p ,H(ID)∈[0,p-1]
其中,除數(shù)p稱作模,一般取值為小于幀長L的素數(shù),[ ]為取整符號,即取該數(shù)的整數(shù)部分,這里的w為讀寫器發(fā)給標簽的正整數(shù),其數(shù)值是根據(jù)碰撞情況變動的。當標簽收到讀寫器發(fā)送的幀長時,對相應的標簽ID取余,然后該標簽在[0,p-1]中根據(jù)所得的余數(shù)值選擇對應的時隙發(fā)送數(shù)據(jù),即通過Hash運算將標簽集合映射到幀時隙對應的集合。比如:標簽ID=(10001101)2=141,取 w=1,L=17,經(jīng)計算得:H(141)=5,即標簽選擇時隙5發(fā)送數(shù)據(jù),完成識別。
但是,我們需要明確,均勻的哈希函數(shù)可以減少沖突,但是不能完全避免沖突,比如,在讀寫器的可讀范圍內,其中有3個標簽ID分別為:ID1=(10001101)2=141,ID2=(11000000)2=192,ID3=(11110011)2=243,經(jīng)簡單計算可得,H(ID1)=H(ID2)=H(ID3)=5,即3個標簽都選擇了5號時隙發(fā)送數(shù)據(jù),導致沖突,標簽無法被正確識別。經(jīng)過對上述3個ID相關整數(shù)值進行分解可得,ID1=141=8×17+5,ID2=192=11×17+5,ID3=243=14×17+5,通過比較得,3個整數(shù)含有不同的w×L值(即w×L=17),故可選擇w=17,L=19,經(jīng)計算得,H(ID1)=8,H(ID2)=11,H(ID3)=14,即標簽ID1選擇了時隙8發(fā)送數(shù)據(jù),同理,ID2選擇時隙11發(fā)送數(shù)據(jù),ID3選擇時隙14發(fā)送數(shù)據(jù),標簽被分配到了下一幀的不同時隙,大幅度地減少了碰撞情況。Hash函數(shù)是通過遞歸搜索碰撞時隙進而識別碰撞標簽的,所以在算法中,必須適當改變參數(shù),改變的原則可設為:下一幀的w值可選為當前幀w與L的乘積,此時Hash運算可以將碰撞降低到最小,使當前幀中碰撞的標簽盡可能映射到下一幀的不同時隙。endprint
3.2 標簽估計與幀長調整
信息是用來消除不確定性的東西,要解決識別過程中的多標簽碰撞問題,首先需要對標簽數(shù)進行預測,了解更多的標簽信息。假設一幀內有L個時隙,即幀長為L,共有n個待檢測的標簽,由于標簽選擇各個時隙數(shù)是等概率的,從數(shù)學原理上來講,時隙Aloha的碰撞是一個多重伯努利試驗問題[7],每個標簽以1/L來隨機選擇一幀中的某個時隙發(fā)送數(shù)據(jù)。假定各個時隙的時間間隔相等,并且不考慮捕獲效應[8](兩個或兩個以上標簽同時產(chǎn)生成功時隙)和環(huán)境噪聲等其他因素對系統(tǒng)的影響,那么可以得到同一時隙里有r個標簽同時發(fā)送數(shù)據(jù)的概率為:
由上述公式可以得到,空閑時隙P(i)、成功時隙P(s)、碰撞時隙P(c)的概率情況如下:
P(i)=P(0);P(s)=P(1) ;P(c)=1-P(0) -P(1) (2)
由于RFID系統(tǒng)的識別效率為讀寫器在一個識別幀長的時間內成功傳輸信息的時隙數(shù)目所占的比例,可用P(s)表示。那么,通過P(s)對標簽數(shù)n求導可得:
(3)
令上述結果(3)等于0,再利用泰勒公式進行展開計算,可以得到,當幀長度L與待識別的標簽數(shù)目n滿足L≈n+1時,理論信道的最大吞吐率為36.8%,圖2為不同幀長條件下,標簽數(shù)與系統(tǒng)吞吐率的曲線關系。
因此盡量設置幀長滿足上述關系,但是由于硬件的條件限制及標簽的成本問題,幀長不能隨著標簽數(shù)的增大一直變大,為減少標簽的碰撞,按照構造的Hash函數(shù)進行時隙的分配,提高時隙的利用率。對應的流程如圖3所示。
目前已經(jīng)提出了多種標簽數(shù)目估計方法,其中Vogt算法可以做出誤差相對較為小且穩(wěn)定的估計,其主要思想是采用切比雪夫不等式:一個涉及隨機變量的隨機試驗過程其輸出很可能在該變量的期望值附近,即使得下式中差值最小的n為標簽數(shù)目估計值。
其中,Ci,Cs,Cc分別為實驗讀取的空閑時隙數(shù),成功時隙數(shù),碰撞時隙數(shù),E(i),E(s),E(c)為空閑時隙的期望值、成功時隙的期望值以及碰撞時隙的期望值。具體計算方式為:
E(i)=L×P(i);E(s)=L×P(s) ;E(c)=L×P(c)
一個讀周期結束后,讀寫器通過Ci,Cs和Cc值所提供的信息,使用切比雪夫估計方法估計系統(tǒng)中存在的標簽數(shù)量,在此基礎上設置下一個讀周期的幀長。要找到使ε最小的標簽數(shù)n,需根據(jù)實際情況設定n的范圍。經(jīng)多次實驗,設定n在[Cs+2Cc, 2(Cs+2Cc)]范圍內變化,計算量也將大大減少。
4 仿真結果
通過Matlab仿真,DFSA算法在最佳情況時,識別效率為36.8%。相比DFSA算法,文中改進算法的吞吐率有大幅的提高,最高可達54%左右,并且當標簽數(shù)目很大時(比如標簽數(shù)大于1 500個),本文算法仍能將系統(tǒng)識別效率維持在較高水平,達到40%以上,結果如圖4所示。
5 結語
防碰撞算法是提高RFID系統(tǒng)識別效率的關鍵,標簽估計和幀長度調整方法是動態(tài)幀時隙Aloha算法中改進的主要方面。本文通過對二項分布和Hash函數(shù)的研究與分析,將兩者相結合,克服了標簽隨機選擇時隙的隨機性誤差,采用精準的標簽估算方法,加快了讀寫器識別標簽的速度。仿真表明,算法能夠有效減少識別過程所需的總時隙數(shù)、空時隙數(shù)和碰撞時隙數(shù),從而提高系統(tǒng)的識別效率,具有較大的實際應用價值。
[參考文獻]
[1]游戰(zhàn)清,李蘇劍.無線射頻技術(RFID)理論與應用[M].北京:電子工業(yè)出版社,2004.
[2]謝磊,殷亞鳳,陳曦,等.RFID數(shù)據(jù)管理:算法、協(xié)議與性能評測[J].計算機學報,2013(36):457-470.
[3]王雪,錢志鴻,胡正超,等.基于二叉樹的RFID防碰撞算法的研究[J].通信學報,2010(31):49-57.
[4]徐圓圓,曾雋芳,劉禹.基于ALOHA算法的幀長及分組數(shù)改進研究[J].計算機應用,2008(28):588-590.
[5]梁彪,鄭勇鑫,王玉瑩,等.基于模運算標簽分類的RFID標簽防碰撞識別方法[J].無線互聯(lián)科技,2014(2):56-58.
[6]張虹,韓磊,馬海波.Hash-tree反碰撞算法[J].計算機工程,2007(33):67-69.
[7]陸端,王剛,閆述.改進ALOHA算法在RFID多目標識別中的應用[J].微計算機信息,2006(22):231-233.
[8]陳毅紅,馮全源.基于捕獲效應的預約時隙分配RFID防碰撞協(xié)議研究[J].計算機學報,2015(38):2375-2389.endprint