ALOHA類(lèi)RFID防碰撞算法OPNET建模與優(yōu)化

1、    ALOHA類(lèi)RFID防碰撞算法OPNET建模與優(yōu)化        舒 琳， 李 波， 劉震宇， 謝 時(shí)間:2008年07月16日     字 體: 大 中 小        關(guān)鍵詞:        ? 摘 要：關(guān)鍵詞： RFID? ALOHA? OPNET? 防碰撞算法?

2、 ISO18000-6? ? 當(dāng)前，無(wú)線射頻識(shí)別RFID(Radio Frequency Identification)技術(shù)發(fā)展迅速。在RFID技術(shù)中，防碰撞算法直接影響電子標(biāo)簽的識(shí)別速率，成為當(dāng)前研究熱點(diǎn)之一。主流RFID防碰撞算法包括ALOHA和二進(jìn)制樹(shù)型搜索兩類(lèi)，其中以ALOHA類(lèi)防碰撞算法在工程中應(yīng)用最廣。對(duì)此類(lèi)算法，較多文獻(xiàn)提出了改進(jìn)，典型的有標(biāo)簽數(shù)目估計(jì)法1，EDFSA21 ALOHA類(lèi)防碰撞算法? ISO18000-6標(biāo)準(zhǔn)中Type A協(xié)議3的防碰撞算法是基于時(shí)隙ALOHA原理的。Type A協(xié)議的標(biāo)簽?zāi)軌蜻M(jìn)入下列狀態(tài)的任何一種：離場(chǎng)掉電、準(zhǔn)備、靜默、選中、識(shí)別、掛起。進(jìn)入識(shí)別狀

3、態(tài)的標(biāo)簽將進(jìn)行沖突檢測(cè)，此時(shí)防碰撞算法開(kāi)始工作。? 讀寫(xiě)器發(fā)送Init_round（開(kāi)始識(shí)別）命令，設(shè)定Round_size參數(shù)（長(zhǎng)度3bit）。該參數(shù)規(guī)定：?jiǎn)未巫R(shí)讀循環(huán)的時(shí)隙總數(shù)為1、8、16、32、64、128和256中任一值，即單次識(shí)讀循環(huán)最多可識(shí)別256個(gè)標(biāo)簽。處于準(zhǔn)備態(tài)的標(biāo)簽接收此命令后進(jìn)入識(shí)別態(tài)，標(biāo)簽隨機(jī)數(shù)發(fā)生器隨機(jī)選擇時(shí)隙數(shù)，并將時(shí)隙計(jì)數(shù)器置1。如果標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)等于時(shí)隙計(jì)數(shù)器數(shù)，標(biāo)簽將回發(fā)ID數(shù)據(jù)包。讀寫(xiě)器發(fā)送完命令后，若沒(méi)有標(biāo)簽回答，則發(fā)送Close_slot（結(jié)束時(shí)隙）命令，處于識(shí)別態(tài)而未回答的標(biāo)簽收到此命令其時(shí)隙計(jì)數(shù)器加1；若讀寫(xiě)器檢測(cè)到多個(gè)標(biāo)簽回答沖突或CRC碼錯(cuò)

4、誤，則發(fā)送Close_slot命令，處于識(shí)別態(tài)而未回答的標(biāo)簽收到此命令后時(shí)隙計(jì)數(shù)器加1；若讀寫(xiě)器接收到一個(gè)標(biāo)簽的正確回答，則發(fā)送Next_slot（下一時(shí)隙）命令，該命令包含剛讀到的標(biāo)簽ID，處于識(shí)別態(tài)的所有標(biāo)簽收到此命令后時(shí)隙計(jì)數(shù)器都加1，剛回發(fā)過(guò)ID的標(biāo)簽確認(rèn)命令中的ID與自己一致后進(jìn)入靜默狀態(tài)，否則標(biāo)簽將繼續(xù)停留在識(shí)別狀態(tài)。一組命令過(guò)后，若讀寫(xiě)器檢測(cè)到時(shí)隙數(shù)等于最初設(shè)定的Round_size，則本次循環(huán)結(jié)束。讀寫(xiě)器可以通過(guò)發(fā)送Init_round命令或New_round（新識(shí)別）命令開(kāi)始新的循環(huán)，新循環(huán)中的Round_size可以固定使用原值，也可以根據(jù)碰撞次數(shù)動(dòng)態(tài)調(diào)整，或者由用戶設(shè)置。

5、? Type C協(xié)議4來(lái)源于EPC Class-1 Generation-2 UHF RFID標(biāo)準(zhǔn)5（第1類(lèi)第2代UHF RFID射頻識(shí)別協(xié)議通訊協(xié)議），其防碰撞算法也是基于時(shí)隙ALOHA原理，主要過(guò)程與Type A類(lèi)似。讀寫(xiě)器發(fā)送Query（查詢）命令開(kāi)始識(shí)別循環(huán)，該命令里有一個(gè)參數(shù)Q（長(zhǎng)度4bit，取值范圍為015），規(guī)定單次識(shí)讀循環(huán)的時(shí)隙總數(shù)為02Q-1，即單次識(shí)讀循環(huán)最多可以識(shí)別65 536個(gè)標(biāo)簽。Q值的作用相當(dāng)于Type A協(xié)議中的Round_size，新循環(huán)中的Q值可以固定使用原值、動(dòng)態(tài)調(diào)整或用戶設(shè)置。? ALOHA類(lèi)防碰撞算法中一個(gè)很重要的參數(shù)就是單次識(shí)讀循環(huán)的時(shí)隙總數(shù)，協(xié)議中由

6、Round_size和Q值規(guī)定。實(shí)際工程中往往固定該參數(shù)或者根據(jù)碰撞次數(shù)由自適應(yīng)算法自動(dòng)調(diào)整該參數(shù)。前者的缺陷在于標(biāo)簽數(shù)量過(guò)小或者過(guò)大時(shí)，固定的參數(shù)會(huì)減慢識(shí)別速率。后者的缺陷在于自適應(yīng)算法的調(diào)整速率很慢，而且標(biāo)準(zhǔn)中并未給出Round_size和Q值的設(shè)置依據(jù)。在工程應(yīng)用中需要尋求單次識(shí)讀循環(huán)時(shí)隙總數(shù)的最優(yōu)化取值，盡可能提高標(biāo)簽識(shí)別速率。下文將針對(duì)這個(gè)目標(biāo)進(jìn)行建模和測(cè)試。2 OPNET建模? OPNET（Optimized Network Engineering Tools）使用有限狀態(tài)機(jī)對(duì)協(xié)議和其他過(guò)程建模，提供核心庫(kù)函數(shù)全面支持協(xié)議編程，采用基于數(shù)據(jù)包的通信機(jī)制、離散事件驅(qū)動(dòng)機(jī)制和面向?qū)ο蟮?/p>

7、仿真方法，是系統(tǒng)和網(wǎng)絡(luò)算法仿真的理想工具62.1 創(chuàng)建RFID網(wǎng)絡(luò)模型? 首先在Project編輯器中建立RFID網(wǎng)絡(luò)級(jí)模型。圖1為一個(gè)RFID網(wǎng)絡(luò)級(jí)模型，它包含兩類(lèi)節(jié)點(diǎn)，中心節(jié)點(diǎn)是讀寫(xiě)器（reader），周?chē)?jié)點(diǎn)（tag_0tag_14）是標(biāo)簽節(jié)點(diǎn)，標(biāo)簽節(jié)點(diǎn)處于讀寫(xiě)器節(jié)點(diǎn)射頻場(chǎng)范圍內(nèi)，采用無(wú)線信道。讀寫(xiě)器節(jié)點(diǎn)和標(biāo)簽節(jié)點(diǎn)分別用于模擬實(shí)際系統(tǒng)中的讀寫(xiě)器和電子標(biāo)簽。通過(guò)調(diào)整讀寫(xiě)器節(jié)點(diǎn)天線模塊的方向角和發(fā)射功率來(lái)設(shè)定讀寫(xiě)器射頻場(chǎng)范圍，用于模擬實(shí)際應(yīng)用中標(biāo)簽進(jìn)入射頻場(chǎng)的情況，如超市、門(mén)禁等場(chǎng)合。? 2.2 創(chuàng)建節(jié)點(diǎn)模型? RFID網(wǎng)絡(luò)對(duì)象的節(jié)點(diǎn)內(nèi)部模型是在Node編輯器中創(chuàng)建的。圖2是標(biāo)簽節(jié)點(diǎn)內(nèi)部模型

8、。讀寫(xiě)器節(jié)點(diǎn)與之相同。讀寫(xiě)器和標(biāo)簽節(jié)點(diǎn)都包含幾個(gè)處理器模塊，一個(gè)無(wú)線發(fā)送機(jī)模塊，一個(gè)無(wú)線接收機(jī)模塊，一個(gè)天線模塊。其中sink處理器模塊從無(wú)線接收機(jī)模塊接收對(duì)方節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包并產(chǎn)生響應(yīng)代碼發(fā)送給proc處理器，proc處理器根據(jù)相應(yīng)代碼產(chǎn)生命令或者ID數(shù)據(jù)包并發(fā)送給無(wú)線發(fā)送機(jī)模塊。? ? 對(duì)于讀寫(xiě)器節(jié)點(diǎn)和標(biāo)簽節(jié)點(diǎn)之間的無(wú)線信道建模，根據(jù)Type A協(xié)議無(wú)線通信物理接口參數(shù)的定義，進(jìn)行無(wú)線信道屬性設(shè)置。OPNET無(wú)線仿真用14個(gè)首尾相接的管道階段（Pipeline Stage）來(lái)盡量真實(shí)地模仿數(shù)據(jù)幀在信道中的傳輸6。天線模塊采用isotropic模型，理想全向天線。讀寫(xiě)器和標(biāo)簽節(jié)點(diǎn)內(nèi)部的無(wú)線發(fā)

9、送機(jī)和接收機(jī)模塊的屬性設(shè)置為:數(shù)據(jù)傳輸速率標(biāo)簽到讀寫(xiě)器40kb/s，讀寫(xiě)器到標(biāo)簽33kb/s，頻率范圍860MHz930MHz，采用高斯信道。2.3 創(chuàng)建進(jìn)程模型? 讀寫(xiě)器和標(biāo)簽的處理器模塊都需要Process編輯器創(chuàng)建進(jìn)程模型。讀寫(xiě)器節(jié)點(diǎn)的proc處理器進(jìn)程模型如圖3所示，其作用是根據(jù)標(biāo)簽回答情況產(chǎn)生Init_round、Close_slot、Next_slot、New_round命令數(shù)據(jù)包，并將這些數(shù)據(jù)包傳給無(wú)線發(fā)送模塊，發(fā)送給標(biāo)簽。標(biāo)簽節(jié)點(diǎn)的處理器進(jìn)程模型主要是產(chǎn)生和發(fā)送ID數(shù)據(jù)包，并讓本標(biāo)簽進(jìn)入靜默狀態(tài)。? ? 網(wǎng)絡(luò)級(jí)、節(jié)點(diǎn)級(jí)和進(jìn)程級(jí)模型建立好，逐層將這些模型封裝起來(lái)成為最終的符合IS

10、O18000-6標(biāo)準(zhǔn)的RFID網(wǎng)絡(luò)系統(tǒng)模型。上文所建的是Type A協(xié)議模型，建立符合Type B或Type C協(xié)議的模型只需將處理器進(jìn)程模型、無(wú)線發(fā)送機(jī)和無(wú)線接收機(jī)模塊的設(shè)置根據(jù)不同標(biāo)準(zhǔn)做相應(yīng)調(diào)整即可。同理，建立符合其他協(xié)議和標(biāo)準(zhǔn)的模型，只需要按照標(biāo)準(zhǔn)調(diào)整天線、無(wú)線發(fā)送機(jī)和接收機(jī)模塊的屬性設(shè)置以及改動(dòng)進(jìn)程模型即可。? 采用圖1的網(wǎng)絡(luò)結(jié)構(gòu)驗(yàn)證建模的準(zhǔn)確性。驗(yàn)證過(guò)程采用ODB調(diào)試和VC聯(lián)調(diào)相結(jié)合的方法。ODB調(diào)試用于追蹤顯示整個(gè)通信過(guò)程，VC聯(lián)合調(diào)試用于觀察內(nèi)部關(guān)鍵變量的變化情況。本文所建RFID網(wǎng)絡(luò)模型調(diào)試結(jié)果符合ISO18000-6標(biāo)準(zhǔn)的防碰撞機(jī)制，驗(yàn)證了建模的準(zhǔn)確性。3 算法優(yōu)化與分析?

11、ALOHA算法使用吞吐量衡量系統(tǒng)性能，吞吐量定義為一幀的發(fā)送時(shí)間內(nèi)成功發(fā)送的平均幀數(shù)。定義S為吞吐量，G為網(wǎng)絡(luò)負(fù)載即一幀的發(fā)送時(shí)間內(nèi)總共發(fā)送的平均幀數(shù)，則時(shí)隙ALOHA算法的吞吐量公式為：? 而RFID防碰撞算法優(yōu)劣的主要判別依據(jù)是標(biāo)簽識(shí)別速率。與吞吐量類(lèi)似，在RFID系統(tǒng)中，定義標(biāo)簽識(shí)別速率為V, T為成功識(shí)別的標(biāo)簽總數(shù)，N為成功識(shí)別這些標(biāo)簽所用的時(shí)間,則標(biāo)簽識(shí)別速率的公式為:?例如工程中某款讀寫(xiě)器的標(biāo)簽識(shí)別速率為300個(gè)標(biāo)簽/秒，是指它每秒能成功識(shí)別300個(gè)標(biāo)簽。為簡(jiǎn)化測(cè)試，定義t為單位時(shí)隙，即讀寫(xiě)器連續(xù)兩條命令之間的時(shí)間間隔，n為成功識(shí)別所有標(biāo)簽所用的時(shí)隙總數(shù)，則式(2)可推導(dǎo)為:? ?

12、 由于單位時(shí)隙t在同等硬件條件下可近似為固定的，故仿真測(cè)試用的標(biāo)簽識(shí)別速率可近一步簡(jiǎn)化為式(4)，即單位時(shí)隙內(nèi)成功識(shí)別的標(biāo)簽數(shù)目。? ? ? ? ? 具體應(yīng)用方法：目前工程中常固定Round_size或者Q值，標(biāo)簽識(shí)別速率受限。要采用圖4和圖5的曲線優(yōu)化設(shè)置，只需將這兩條曲線設(shè)置數(shù)據(jù)寫(xiě)入讀寫(xiě)器程序中。凡是支持ISO18000-6 Type A和Type C協(xié)議的讀寫(xiě)器，一旦獲得當(dāng)前標(biāo)簽射頻場(chǎng)內(nèi)標(biāo)簽數(shù)目，即可自動(dòng)查詢圖4和圖5的曲線，將Round_size和Q值調(diào)整到最優(yōu)取值。例如：在倉(cāng)儲(chǔ)應(yīng)用中，若入倉(cāng)的一批貨物有500件，貼有Type A型標(biāo)簽，則讀寫(xiě)器查詢圖4曲線，將Round_size自動(dòng)設(shè)置為256的最優(yōu)取值。在超市應(yīng)用中，若顧客一次購(gòu)買(mǎi)商品20件，貼有Type C型標(biāo)簽，則讀寫(xiě)器自動(dòng)查詢圖5曲線，設(shè)置Q4。而標(biāo)簽數(shù)目的獲取，可以采用估計(jì)算法1，或者由管理員通過(guò)用戶控制界面輸入，例如倉(cāng)儲(chǔ)應(yīng)用中，管理員是知道每批貨物的數(shù)目的；而超市環(huán)境中，可由顧客輸入所購(gòu)商品數(shù)目或在購(gòu)物車(chē)上安裝簡(jiǎn)易裝置計(jì)算出商品數(shù)目。4 實(shí)驗(yàn)結(jié)果及討論? 利用OPNET所建模型對(duì)算法優(yōu)化前后比較，得到的統(tǒng)計(jì)數(shù)據(jù)如圖6所示。從圖中明顯看到，優(yōu)化后算法的標(biāo)簽識(shí)別速率遠(yuǎn)遠(yuǎn)高于Round_size固定設(shè)置為8、16、32、64、128、256的情形。仿真證明，Roun