基于動(dòng)態(tài)幀時(shí)隙Aloha的防碰撞算法研究

陳昊+高勤+安錫文

摘 要：在RFID系統(tǒng)中，多標(biāo)簽同時(shí)存在會(huì)引發(fā)標(biāo)簽碰撞問題，文章首先分析已識(shí)別標(biāo)簽的情況，對(duì)剩余標(biāo)簽的個(gè)數(shù)進(jìn)行了估計(jì)，并依此動(dòng)態(tài)匹配最佳幀長。為了進(jìn)一步提高系統(tǒng)的識(shí)別效率，構(gòu)造了合適的哈希函數(shù)，將標(biāo)簽集合均勻地映射到幀時(shí)隙集合，降低了標(biāo)簽的沖突率。仿真表明，該算法提高了系統(tǒng)的吞吐率和穩(wěn)定性，對(duì)Aloha算法的后續(xù)研究工作以及工程實(shí)踐應(yīng)用具有一定的參考價(jià)值。

關(guān)鍵字：動(dòng)態(tài)幀時(shí)隙；Aloha算法；防碰撞；哈希函數(shù)；標(biāo)簽估計(jì)

1 RFID概述

無線射頻識(shí)別（Radio Frequency Identification，RFID）作為新型無線非接觸式自動(dòng)識(shí)別技術(shù)[1]，具有存儲(chǔ)容量大、識(shí)別速度快和安全系數(shù)高等優(yōu)點(diǎn)，被作為感知層的關(guān)鍵技術(shù)廣泛應(yīng)用于物流、銷售和定位等領(lǐng)域，并作為物聯(lián)網(wǎng)領(lǐng)域的核心技術(shù)之一，得到極大關(guān)注[2]。

RFID系統(tǒng)一般由讀寫器、電子標(biāo)簽以及應(yīng)用軟件系統(tǒng)組成。系統(tǒng)在工作的時(shí)候，讀寫器與標(biāo)簽之間利用電磁信號(hào)進(jìn)行數(shù)據(jù)交換。當(dāng)多個(gè)標(biāo)簽共用相同的信道時(shí)，信號(hào)在空中媒介發(fā)生干擾，就會(huì)引發(fā)碰撞，導(dǎo)致標(biāo)簽識(shí)別和數(shù)據(jù)傳送失敗。為了減小和消除這種碰撞問題，保證數(shù)據(jù)在傳輸過程中的完整性，許多科研工作者對(duì)RFID中的防碰撞機(jī)制進(jìn)行了大量深入的研究。

目前，應(yīng)用較廣泛的防碰撞算法大多基于時(shí)分多址接入（Time Division Multiple Access，TDMA），主要有如下兩類：基于二叉樹的確定性算法和基于Aloha的概率性算法[3-5]。前者優(yōu)點(diǎn)是能識(shí)別出所有標(biāo)簽，沒有遺漏現(xiàn)象，但是對(duì)讀寫器硬件要求較高且算法的空間和時(shí)間復(fù)雜度較高。后者是Aloha及其改進(jìn)算法，標(biāo)簽隨機(jī)選擇時(shí)隙與讀寫器通信，復(fù)雜度小且容易實(shí)現(xiàn)，但存在一定概率的某一標(biāo)簽長時(shí)間內(nèi)所選擇的時(shí)隙均發(fā)生碰撞，在有效時(shí)間內(nèi)無法被讀寫器識(shí)別，存在標(biāo)簽“饑餓”問題?；贏loha的防碰撞算法主要包括純Aloha（Pure Aloha，PA）、時(shí)隙Aloha（ Slotted Aloha，SA）、幀時(shí)隙Aloha（Framed Slotted Aloha，F(xiàn)SA）、動(dòng)態(tài)幀時(shí)隙Aloha（Dynamic Frame Slotted Aloha，DFSA）等。其中，DFSA算法可以根據(jù)實(shí)際的標(biāo)簽數(shù)目動(dòng)態(tài)地調(diào)整幀長度，其識(shí)別速度快，可使信道吞吐率達(dá)到最大，所以應(yīng)用也最為廣泛。由于在實(shí)際情況下，標(biāo)簽數(shù)量通常是未知的，所以如何估計(jì)標(biāo)簽數(shù)目是決定系統(tǒng)吞吐率的關(guān)鍵。本文在此基礎(chǔ)上，首先統(tǒng)計(jì)已識(shí)別標(biāo)簽的數(shù)據(jù)情況，通過對(duì)剩余標(biāo)簽的數(shù)目進(jìn)行估計(jì)，并構(gòu)造合適的哈希函數(shù)對(duì)標(biāo)簽進(jìn)行時(shí)隙分配，減少了標(biāo)簽隨機(jī)選擇時(shí)隙帶來的誤差，直到所有的標(biāo)簽被正確識(shí)別。

2 時(shí)隙基本定義

在基于Aloha的算法中，將時(shí)間分成很多小時(shí)間段，每一段稱為時(shí)隙，多個(gè)時(shí)隙組成一幀，每幀包含的時(shí)隙個(gè)數(shù)稱為幀長度。對(duì)于一個(gè)給定的時(shí)隙，存在以下3種結(jié)果：空閑時(shí)隙（Idle Slot，IS），即沒有任何標(biāo)簽選擇在該時(shí)隙進(jìn)行回復(fù)；成功時(shí)隙，當(dāng)前時(shí)隙中僅有一個(gè)標(biāo)簽參與回復(fù)，讀寫器成功識(shí)別該標(biāo)簽；碰撞時(shí)隙，存在兩個(gè)及兩個(gè)以上標(biāo)簽在該時(shí)隙進(jìn)行回復(fù)，

此時(shí)會(huì)產(chǎn)生數(shù)據(jù)碰撞。如圖1所示。

假設(shè)讀寫器范圍內(nèi)有8個(gè)標(biāo)簽，幀長為8，即每幀中含有8個(gè)時(shí)隙，各標(biāo)簽在每幀中隨機(jī)選取一個(gè)時(shí)隙發(fā)送信息。通過讀寫器和標(biāo)簽的一系列命令和回應(yīng)之后，出現(xiàn)如圖1所示情況，根據(jù)定義，可知時(shí)隙1，4，7為成功時(shí)隙，時(shí)隙2，6為碰撞時(shí)隙，時(shí)隙3，5，8為空閑時(shí)隙，也即標(biāo)簽1，3，7被成功識(shí)別；標(biāo)簽2，5發(fā)生碰撞，標(biāo)簽4，6，8發(fā)生碰撞，并且由此可知，標(biāo)簽識(shí)別過程中，空閑時(shí)隙和碰撞時(shí)隙出現(xiàn)的概率很高。

3 時(shí)隙算法說明

3.1 標(biāo)簽選擇時(shí)隙方法

在RFID系統(tǒng)中，標(biāo)簽數(shù)目一般很多，在幾十至幾千個(gè)之間，由于標(biāo)簽選擇時(shí)隙具有一定的隨機(jī)性，如果不能合理地安排時(shí)隙，那么由于效率低而造成的時(shí)間開銷損失會(huì)非常嚴(yán)重。防碰撞算法的實(shí)質(zhì)是減少時(shí)隙的碰撞。通過構(gòu)造合適的函數(shù)，確定標(biāo)簽選擇時(shí)隙的基準(zhǔn)，使得標(biāo)簽?zāi)芨鶕?jù)一定的算法均勻地分布到各個(gè)時(shí)隙，降低標(biāo)簽空閑及碰撞情況。

每個(gè)標(biāo)簽都有唯一的識(shí)別碼（UID），其包含了標(biāo)簽的基本信息，文中采用計(jì)算量較小的除留余數(shù)法構(gòu)造的哈希函數(shù)[6]，滿足了簡單均勻的要求，具體計(jì)算公式為：

Hash（ID）=[ID/w] mod p ，H（ID）∈[0，p-1]

其中，除數(shù)p稱作模，一般取值為小于幀長L的素?cái)?shù)，[ ]為取整符號(hào)，即取該數(shù)的整數(shù)部分，這里的w為讀寫器發(fā)給標(biāo)簽的正整數(shù)，其數(shù)值是根據(jù)碰撞情況變動(dòng)的。當(dāng)標(biāo)簽收到讀寫器發(fā)送的幀長時(shí)，對(duì)相應(yīng)的標(biāo)簽ID取余，然后該標(biāo)簽在[0，p-1]中根據(jù)所得的余數(shù)值選擇對(duì)應(yīng)的時(shí)隙發(fā)送數(shù)據(jù)，即通過Hash運(yùn)算將標(biāo)簽集合映射到幀時(shí)隙對(duì)應(yīng)的集合。比如：標(biāo)簽ID=（10001101）2=141，取 w=1，L=17，經(jīng)計(jì)算得：H（141）=5，即標(biāo)簽選擇時(shí)隙5發(fā)送數(shù)據(jù)，完成識(shí)別。

但是，我們需要明確，均勻的哈希函數(shù)可以減少?zèng)_突，但是不能完全避免沖突，比如，在讀寫器的可讀范圍內(nèi)，其中有3個(gè)標(biāo)簽ID分別為：ID1=（10001101）2=141，ID2=（11000000）2=192，ID3=（11110011）2=243，經(jīng)簡單計(jì)算可得，H（ID1）=H（ID2）=H（ID3）=5，即3個(gè)標(biāo)簽都選擇了5號(hào)時(shí)隙發(fā)送數(shù)據(jù)，導(dǎo)致沖突，標(biāo)簽無法被正確識(shí)別。經(jīng)過對(duì)上述3個(gè)ID相關(guān)整數(shù)值進(jìn)行分解可得，ID1=141=8×17+5，ID2=192=11×17+5，ID3=243=14×17+5，通過比較得，3個(gè)整數(shù)含有不同的w×L值（即w×L=17），故可選擇w=17，L=19，經(jīng)計(jì)算得，H（ID1）=8，H（ID2）=11，H（ID3）=14，即標(biāo)簽ID1選擇了時(shí)隙8發(fā)送數(shù)據(jù)，同理，ID2選擇時(shí)隙11發(fā)送數(shù)據(jù)，ID3選擇時(shí)隙14發(fā)送數(shù)據(jù)，標(biāo)簽被分配到了下一幀的不同時(shí)隙，大幅度地減少了碰撞情況。Hash函數(shù)是通過遞歸搜索碰撞時(shí)隙進(jìn)而識(shí)別碰撞標(biāo)簽的，所以在算法中，必須適當(dāng)改變參數(shù)，改變的原則可設(shè)為：下一幀的w值可選為當(dāng)前幀w與L的乘積，此時(shí)Hash運(yùn)算可以將碰撞降低到最小，使當(dāng)前幀中碰撞的標(biāo)簽盡可能映射到下一幀的不同時(shí)隙。endprint

3.2 標(biāo)簽估計(jì)與幀長調(diào)整

信息是用來消除不確定性的東西，要解決識(shí)別過程中的多標(biāo)簽碰撞問題，首先需要對(duì)標(biāo)簽數(shù)進(jìn)行預(yù)測，了解更多的標(biāo)簽信息。假設(shè)一幀內(nèi)有L個(gè)時(shí)隙，即幀長為L，共有n個(gè)待檢測的標(biāo)簽，由于標(biāo)簽選擇各個(gè)時(shí)隙數(shù)是等概率的，從數(shù)學(xué)原理上來講，時(shí)隙Aloha的碰撞是一個(gè)多重伯努利試驗(yàn)問題[7]，每個(gè)標(biāo)簽以1/L來隨機(jī)選擇一幀中的某個(gè)時(shí)隙發(fā)送數(shù)據(jù)。假定各個(gè)時(shí)隙的時(shí)間間隔相等，并且不考慮捕獲效應(yīng)[8]（兩個(gè)或兩個(gè)以上標(biāo)簽同時(shí)產(chǎn)生成功時(shí)隙）和環(huán)境噪聲等其他因素對(duì)系統(tǒng)的影響，那么可以得到同一時(shí)隙里有r個(gè)標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)的概率為：

由上述公式可以得到，空閑時(shí)隙P（i）、成功時(shí)隙P（s）、碰撞時(shí)隙P（c）的概率情況如下：

P（i）=P（0）；P（s）=P（1） ；P（c）=1-P（0） -P（1） （2）

由于RFID系統(tǒng)的識(shí)別效率為讀寫器在一個(gè)識(shí)別幀長的時(shí)間內(nèi)成功傳輸信息的時(shí)隙數(shù)目所占的比例，可用P（s）表示。那么，通過P（s）對(duì)標(biāo)簽數(shù)n求導(dǎo)可得：

（3）

令上述結(jié)果（3）等于0，再利用泰勒公式進(jìn)行展開計(jì)算，可以得到，當(dāng)幀長度L與待識(shí)別的標(biāo)簽數(shù)目n滿足L≈n+1時(shí)，理論信道的最大吞吐率為36.8%，圖2為不同幀長條件下，標(biāo)簽數(shù)與系統(tǒng)吞吐率的曲線關(guān)系。

因此盡量設(shè)置幀長滿足上述關(guān)系，但是由于硬件的條件限制及標(biāo)簽的成本問題，幀長不能隨著標(biāo)簽數(shù)的增大一直變大，為減少標(biāo)簽的碰撞，按照構(gòu)造的Hash函數(shù)進(jìn)行時(shí)隙的分配，提高時(shí)隙的利用率。對(duì)應(yīng)的流程如圖3所示。

目前已經(jīng)提出了多種標(biāo)簽數(shù)目估計(jì)方法，其中Vogt算法可以做出誤差相對(duì)較為小且穩(wěn)定的估計(jì)，其主要思想是采用切比雪夫不等式：一個(gè)涉及隨機(jī)變量的隨機(jī)試驗(yàn)過程其輸出很可能在該變量的期望值附近，即使得下式中差值最小的n為標(biāo)簽數(shù)目估計(jì)值。

其中，Ci，Cs，Cc分別為實(shí)驗(yàn)讀取的空閑時(shí)隙數(shù)，成功時(shí)隙數(shù)，碰撞時(shí)隙數(shù)，E（i），E（s），E（c）為空閑時(shí)隙的期望值、成功時(shí)隙的期望值以及碰撞時(shí)隙的期望值。具體計(jì)算方式為：

E（i）=L×P（i）；E（s）=L×P（s） ；E（c）=L×P（c）

一個(gè)讀周期結(jié)束后，讀寫器通過Ci，Cs和Cc值所提供的信息，使用切比雪夫估計(jì)方法估計(jì)系統(tǒng)中存在的標(biāo)簽數(shù)量，在此基礎(chǔ)上設(shè)置下一個(gè)讀周期的幀長。要找到使ε最小的標(biāo)簽數(shù)n，需根據(jù)實(shí)際情況設(shè)定n的范圍。經(jīng)多次實(shí)驗(yàn)，設(shè)定n在[Cs+2Cc， 2（Cs+2Cc）]范圍內(nèi)變化，計(jì)算量也將大大減少。

4 仿真結(jié)果

通過Matlab仿真，DFSA算法在最佳情況時(shí)，識(shí)別效率為36.8%。相比DFSA算法，文中改進(jìn)算法的吞吐率有大幅的提高，最高可達(dá)54%左右，并且當(dāng)標(biāo)簽數(shù)目很大時(shí)（比如標(biāo)簽數(shù)大于1 500個(gè)），本文算法仍能將系統(tǒng)識(shí)別效率維持在較高水平，達(dá)到40%以上，結(jié)果如圖4所示。

5 結(jié)語

防碰撞算法是提高RFID系統(tǒng)識(shí)別效率的關(guān)鍵，標(biāo)簽估計(jì)和幀長度調(diào)整方法是動(dòng)態(tài)幀時(shí)隙Aloha算法中改進(jìn)的主要方面。本文通過對(duì)二項(xiàng)分布和Hash函數(shù)的研究與分析，將兩者相結(jié)合，克服了標(biāo)簽隨機(jī)選擇時(shí)隙的隨機(jī)性誤差，采用精準(zhǔn)的標(biāo)簽估算方法，加快了讀寫器識(shí)別標(biāo)簽的速度。仿真表明，算法能夠有效減少識(shí)別過程所需的總時(shí)隙數(shù)、空時(shí)隙數(shù)和碰撞時(shí)隙數(shù)，從而提高系統(tǒng)的識(shí)別效率，具有較大的實(shí)際應(yīng)用價(jià)值。

[參考文獻(xiàn)]

[1]游戰(zhàn)清，李蘇劍.無線射頻技術(shù)（RFID）理論與應(yīng)用[M].北京：電子工業(yè)出版社，2004.

[2]謝磊，殷亞鳳，陳曦，等.RFID數(shù)據(jù)管理：算法、協(xié)議與性能評(píng)測[J].計(jì)算機(jī)學(xué)報(bào)，2013（36）：457-470.

[3]王雪，錢志鴻，胡正超，等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報(bào)，2010（31）：49-57.

[4]徐圓圓，曾雋芳，劉禹.基于ALOHA算法的幀長及分組數(shù)改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用，2008（28）：588-590.

[5]梁彪，鄭勇鑫，王玉瑩，等.基于模運(yùn)算標(biāo)簽分類的RFID標(biāo)簽防碰撞識(shí)別方法[J].無線互聯(lián)科技，2014（2）：56-58.

[6]張虹，韓磊，馬海波.Hash-tree反碰撞算法[J].計(jì)算機(jī)工程，2007（33）：67-69.

[7]陸端，王剛，閆述.改進(jìn)ALOHA算法在RFID多目標(biāo)識(shí)別中的應(yīng)用[J].微計(jì)算機(jī)信息，2006（22）：231-233.

[8]陳毅紅，馮全源.基于捕獲效應(yīng)的預(yù)約時(shí)隙分配RFID防碰撞協(xié)議研究[J].計(jì)算機(jī)學(xué)報(bào)，2015（38）：2375-2389.endprint