公安巡檢數(shù)據(jù)采集終端中防碰撞算法的研究與應(yīng)用

賈巖巖 陸華 桂林大

【摘要】 主要闡述了RFID系統(tǒng)中電子標(biāo)簽的防碰撞問(wèn)題，分析了常用的防碰撞技術(shù)ALOHA算法。結(jié)合公安巡檢數(shù)據(jù)采集終端的實(shí)際情況，給出了改進(jìn)型ALOHA算法的實(shí)現(xiàn)過(guò)程，該算法簡(jiǎn)單有效，實(shí)用性強(qiáng)，提高了系統(tǒng)數(shù)據(jù)的吞吐率。

【關(guān)鍵詞】 RFID標(biāo)簽 防碰撞 ALOHA算法 改進(jìn)型一、引言

當(dāng)前社會(huì)發(fā)展與經(jīng)濟(jì)建設(shè)進(jìn)入全面提速階段，國(guó)民的生活水平得到進(jìn)一步的提高，社會(huì)公共安全越來(lái)越收到廣泛的關(guān)注，尤其是近幾年來(lái)我國(guó)發(fā)生的暴力恐怖事件， 因此提高對(duì)巡警和巡防隊(duì)員的有效管理，對(duì)于降低犯罪，保障公共安全越來(lái)越重要。

無(wú)線射頻識(shí)別技術(shù)[1] （Radio Frequency Identification， RFID），或稱射頻識(shí)別技術(shù)。作為一種快速、準(zhǔn)確、實(shí)時(shí)采集與處理信息的高新技術(shù)[2]，RFID被列為本世紀(jì)十大重要技術(shù)之一[3]，其在公安巡檢領(lǐng)域也得到了廣泛的應(yīng)用。無(wú)線電技術(shù)中，多路存取的問(wèn)題是眾所周知的。如果有多個(gè)RFID標(biāo)簽接收到電磁波并同時(shí)發(fā)送反饋信息，則標(biāo)簽閱讀器接收到的信號(hào)就會(huì)相互干擾，發(fā)生數(shù)據(jù)碰撞[4]。因此，如何解決數(shù)據(jù)碰撞問(wèn)題成為了RFID系統(tǒng)的關(guān)鍵技術(shù)之一[5]。

目前，應(yīng)用于射頻識(shí)別系統(tǒng)中的防碰撞技術(shù)主要有空分多址（SDMA）、頻分多址（FDMA）、碼分多址（CDMA）和時(shí)分多址（TDMA）等。由于時(shí)分多址法的成本較低，易于實(shí)現(xiàn)，所以是目前最為常用的防碰撞技術(shù)。本文主要描述基于TDMA的RFID ALOHA隨機(jī)延時(shí)防碰撞算法。

二、ALOHA防碰撞算法

ALOHA算法是一種不確定性算法，其檢測(cè)時(shí)間和延遲時(shí)間都是隨機(jī)分布的，主要應(yīng)用于主動(dòng)式標(biāo)簽，包括純ALOHA算法、時(shí)隙ALOHA算法和自適應(yīng)時(shí)隙ALOHA算法。它的基本原理為，當(dāng)信息源標(biāo)簽發(fā)送的數(shù)據(jù)包發(fā)生碰撞時(shí)，標(biāo)簽就會(huì)產(chǎn)生一個(gè)隨機(jī)延時(shí)，然后再次嘗試數(shù)據(jù)包的發(fā)送，重復(fù)此操作，直到發(fā)送成功。

2.1純ALOHA算法

純ALOHA算法是一種最簡(jiǎn)單最基本的防碰撞算法，它不具有碰撞檢測(cè)及恢復(fù)機(jī)制，只是在概率上保證標(biāo)簽發(fā)送的數(shù)據(jù)被閱讀器準(zhǔn)確接收。它采用的是“標(biāo)簽先發(fā)言”（TTF， Tag Talk First）方式。即當(dāng)標(biāo)簽處于閱讀器的作用范圍時(shí)，標(biāo)簽就會(huì)主動(dòng)發(fā)送自身的信息數(shù)據(jù)包，當(dāng)多個(gè)標(biāo)簽的數(shù)據(jù)同時(shí)到達(dá)閱讀器就會(huì)造成數(shù)據(jù)幀的破壞，各個(gè)標(biāo)簽將隨機(jī)延長(zhǎng)一段時(shí)間后進(jìn)行重新發(fā)送。標(biāo)簽1產(chǎn)生了數(shù)據(jù)并立即發(fā)送，接著標(biāo)簽3也開(kāi)始發(fā)送數(shù)據(jù)，這樣標(biāo)簽1和標(biāo)簽3就發(fā)生了部分碰撞，而如果兩個(gè)標(biāo)簽恰巧在同一時(shí)刻發(fā)送數(shù)據(jù)，就將發(fā)送完全碰撞。

該算法的優(yōu)點(diǎn)是，無(wú)需同步，各標(biāo)簽發(fā)送時(shí)間完全隨機(jī)，比較容易實(shí)現(xiàn)，尤其是當(dāng)標(biāo)簽較少時(shí)能夠進(jìn)行很好的工作，但缺點(diǎn)是延時(shí)時(shí)間選擇困難，如果設(shè)置過(guò)大，則閱讀器的識(shí)別時(shí)間就會(huì)變長(zhǎng)，若設(shè)置過(guò)小，系統(tǒng)發(fā)生重復(fù)碰撞的幾率就會(huì)大增，需要退避的次數(shù)也會(huì)過(guò)多。

性能分析：公共信道上在單位時(shí)間T內(nèi)平均發(fā)送的數(shù)據(jù)幀數(shù)G和傳輸通路的吞吐率S的計(jì)算公式見(jiàn)式（1）和式（2）。

（1）

（2）

式中，n為系統(tǒng)中標(biāo)簽的數(shù)量，rn是T時(shí)間內(nèi)由標(biāo)簽n發(fā)送的數(shù)據(jù)幀數(shù)。

由以上公式可以得出S的極大值，即當(dāng)G=0.5時(shí)，吞吐率S的最大值Smax=1/2e（約為0.184），說(shuō)明純ALOHA的最大信道利用率是18.4%。

2.2時(shí)隙ALOHA算法

時(shí)隙ALOHA算法和純ALOHA算法的區(qū)別在于，將時(shí)間分割成了一個(gè)個(gè)等長(zhǎng)離散的時(shí)隙，時(shí)隙Tslot等于或者略大于一個(gè)數(shù)據(jù)包的長(zhǎng)度T0，并且只有當(dāng)時(shí)隙開(kāi)始時(shí)每個(gè)標(biāo)簽才被允許發(fā)送數(shù)據(jù)幀，這樣一來(lái)，一旦發(fā)生了數(shù)據(jù)碰撞，就是完全碰撞，不會(huì)發(fā)生部分碰撞的情況，見(jiàn)圖2。

時(shí)隙ALOHA算法中，S與G的關(guān)系為：

S=Ge-G

2.3動(dòng)態(tài)時(shí)隙ALOHA算法

在時(shí)隙ALOHA算法中，時(shí)間軸被劃分的時(shí)隙數(shù)N是固定不變的，且容易實(shí)現(xiàn)，但是在公安巡檢數(shù)據(jù)采集終端的實(shí)際應(yīng)用環(huán)境中，進(jìn)入閱讀器作用范圍的電子標(biāo)簽的數(shù)量是動(dòng)態(tài)改變的，閱讀器不能主動(dòng)根據(jù)電子標(biāo)簽的數(shù)量調(diào)整時(shí)隙數(shù)的大小，這將導(dǎo)致公安巡檢數(shù)據(jù)采集終端性能不穩(wěn)，甚至造成電子標(biāo)簽的信息漏讀。動(dòng)態(tài)時(shí)隙ALOHA算法能夠根據(jù)標(biāo)簽發(fā)生碰撞的數(shù)量動(dòng)態(tài)地改變時(shí)隙數(shù)N的大小。當(dāng)時(shí)隙數(shù)小于標(biāo)簽數(shù)量時(shí)，閱讀器根據(jù)發(fā)生碰撞的標(biāo)簽數(shù)適當(dāng)增加時(shí)隙數(shù)，反之，當(dāng)時(shí)隙數(shù)大于標(biāo)簽數(shù)量時(shí)，閱讀器能適當(dāng)?shù)販p少數(shù)據(jù)幀的時(shí)隙數(shù)。動(dòng)態(tài)ALOHA算法能保證數(shù)據(jù)幀的時(shí)隙數(shù)與標(biāo)簽數(shù)量基本一致，使系統(tǒng)效率達(dá)到最佳。

2.4 改進(jìn)型ALOHA算法

RFID系統(tǒng)中的標(biāo)簽只能通過(guò)接收閱讀器的指令來(lái)判斷是否發(fā)生了數(shù)據(jù)碰撞，導(dǎo)致系統(tǒng)信道利用率很低。若標(biāo)簽?zāi)軌蜃灾髋袛嗍欠駮?huì)發(fā)生數(shù)據(jù)碰撞，再選擇發(fā)送數(shù)據(jù)，就可以大大降低數(shù)據(jù)發(fā)生碰撞的概率，進(jìn)而使信道利用率增加。改進(jìn)型ALOHA算法是在時(shí)隙ALOHA算法的基礎(chǔ)上增加了數(shù)據(jù)碰撞避免機(jī)制[6]，各標(biāo)簽首先進(jìn)行標(biāo)簽同步，當(dāng)信道被其他標(biāo)簽占用時(shí)繼續(xù)監(jiān)聽(tīng)，直到信道空閑將自身數(shù)據(jù)立即發(fā)送出去，若發(fā)生數(shù)據(jù)碰撞，則隨機(jī)延遲一段時(shí)隙后重新監(jiān)聽(tīng)。由于改進(jìn)型ALOHA算法采用了實(shí)時(shí)信道監(jiān)聽(tīng)，這就要求標(biāo)簽具有主動(dòng)發(fā)送信息的能力，所以改進(jìn)型ALOHA算法僅適用于有源電子標(biāo)簽的防碰撞。公安巡檢數(shù)據(jù)采集終端采用的正是有源電子標(biāo)簽，有源電子標(biāo)簽增加了閱讀器的讀取距離，不僅縮短了閱讀器的讀取時(shí)間，而且提高了讀取效率[7]。

三、公安巡檢數(shù)據(jù)采集終端中防碰撞算法的實(shí)現(xiàn)

公安巡檢數(shù)據(jù)采集終端中閱讀器與標(biāo)簽通信運(yùn)用握手協(xié)議進(jìn)行數(shù)據(jù)交換[8]，標(biāo)簽進(jìn)入閱讀器搜索范圍時(shí)被激活，當(dāng)標(biāo)簽監(jiān)聽(tīng)到信道空閑時(shí)發(fā)送自身數(shù)據(jù)，發(fā)送成功后進(jìn)行滅活處理。

具體實(shí)現(xiàn)步驟如下：

（1）閱讀器發(fā)送廣播信息幀；

（2）處于閱讀器作用范圍內(nèi)的所有標(biāo)簽將接收廣播信息幀，未被識(shí)別的標(biāo)簽（即處于休眠狀態(tài)）自主喚醒，同時(shí)監(jiān)聽(tīng)信道狀態(tài)，等待發(fā)送自身數(shù)據(jù)；

（3）當(dāng)標(biāo)簽監(jiān)聽(tīng)到信道空閑時(shí)，將自身數(shù)據(jù)發(fā)送出去，并繼續(xù)偵聽(tīng)閱讀器返回的數(shù)據(jù)幀；

（4）若標(biāo)簽成功占用了信道，閱讀器接收后會(huì)返回應(yīng)答，標(biāo)簽收到應(yīng)答后進(jìn)入休眠模式（即滅活）。若未能成功占用信道，標(biāo)簽即隨機(jī)延時(shí)一段時(shí)隙，繼續(xù)監(jiān)聽(tīng)信道等待重新發(fā)送。

（5）閱讀器再次發(fā)送廣播信息進(jìn)行下一次通信。

四、結(jié)語(yǔ)

改進(jìn)的ALOHA數(shù)據(jù)防碰撞算法，即在標(biāo)簽發(fā)送數(shù)據(jù)之前先監(jiān)聽(tīng)信道是否被占用，再?zèng)Q定是否發(fā)送數(shù)據(jù)。仿真結(jié)果表明：改進(jìn)型ALOHA算法優(yōu)于動(dòng)態(tài)ALOHA和時(shí)隙ALOHA算法，最大數(shù)據(jù)吞吐率達(dá)到53%。在公安巡檢數(shù)據(jù)采集終端的實(shí)際應(yīng)用中，改進(jìn)型ALOHA算法完全能夠滿足要求，且易于實(shí)現(xiàn)，成本較低，達(dá)到了比較好的效果。

陳業(yè)龍（1973-），男，本科，工程師，主要研究方向：通信技術(shù)及物聯(lián)網(wǎng)應(yīng)用開(kāi)發(fā)

賈巖巖（1987-），通信作者，男，碩士研究生，助理工程師，主要研究方向：無(wú)線通信系統(tǒng)中的信號(hào)處理技術(shù)

陸華（1985-），男，碩士研究生，助理工程師，主要研究方向：信號(hào)處理和傳輸技術(shù)