范佳興， 李　兵， 何怡剛， 章玉珠, 張李明

(合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，安徽 合肥 230009)

?

面向電氣設(shè)備狀態(tài)監(jiān)測(cè)的傳感標(biāo)簽防碰撞算法*

范佳興， 李兵， 何怡剛， 章玉珠, 張李明

(合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，安徽 合肥 230009)

摘要:射頻識(shí)別(RFID)傳感標(biāo)簽是一種新型的融合標(biāo)識(shí)傳感功能的電氣設(shè)備狀態(tài)無(wú)線監(jiān)測(cè)技術(shù)，高效防碰撞算法是提高基于RFID傳感標(biāo)簽技術(shù)的電氣設(shè)備狀態(tài)無(wú)線監(jiān)測(cè)系統(tǒng)實(shí)時(shí)性的主要手段。在改進(jìn)自適應(yīng)多叉樹(shù)搜索(IAMS)防碰撞算法基礎(chǔ)上，通過(guò)碰撞概率模型計(jì)算碰撞傳感標(biāo)簽數(shù)，制定優(yōu)先申請(qǐng)分配專有時(shí)隙原則，提出一種改進(jìn)的自適應(yīng)時(shí)隙多叉樹(shù)防碰撞 (IATMSA) 算法。算法仿真結(jié)果表明：相比IAMS算法和四叉樹(shù)算法，IATMSA算法總時(shí)隙數(shù)更小、識(shí)別速度更快、吞吐率更高。

關(guān)鍵詞:電氣設(shè)備狀態(tài)監(jiān)測(cè)； 傳感標(biāo)簽； 改進(jìn)的自適應(yīng)時(shí)隙多叉樹(shù)防碰撞算法； 專有時(shí)隙

0引言

智能電網(wǎng)是以物聯(lián)網(wǎng)為基礎(chǔ)，集先進(jìn)感知、通信、信息及控制技術(shù)而形成的一種新型電網(wǎng)?，F(xiàn)有國(guó)內(nèi)各種電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)存在測(cè)量數(shù)據(jù)少、測(cè)量信息不全面、系統(tǒng)可靠性低等問(wèn)題[1,2]。將射頻識(shí)別(radio frequency identification，RFID)技術(shù)與傳感器融合應(yīng)用于電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)，可以對(duì)電網(wǎng)設(shè)備進(jìn)行智能化識(shí)別、定位、監(jiān)控和管理，滿足智能電網(wǎng)對(duì)設(shè)備狀態(tài)信息的準(zhǔn)確獲取與網(wǎng)絡(luò)化交互需求[3]。多個(gè)傳感標(biāo)簽同時(shí)向閱讀器發(fā)送信息時(shí)會(huì)造成傳感標(biāo)簽發(fā)生碰撞，導(dǎo)致傳感標(biāo)簽無(wú)法被成功識(shí)別。因此，有必要研究應(yīng)用于電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)的傳感標(biāo)簽防碰撞問(wèn)題，提高系統(tǒng)識(shí)別率和實(shí)時(shí)性[4]。

國(guó)內(nèi)外學(xué)者對(duì)RFID系統(tǒng)防碰撞算法開(kāi)展了大量研究，可分為基于ALOHA[5]與基于樹(shù)[6]的防碰撞算法兩類。前者采用基于運(yùn)行概率的后退機(jī)制，由于標(biāo)簽響應(yīng)時(shí)間的不確定性，易出現(xiàn)標(biāo)簽饑餓問(wèn)題(標(biāo)簽無(wú)法被識(shí)別)[5]。后者可以避免標(biāo)簽饑餓問(wèn)題，主要有二進(jìn)制搜索樹(shù)[6]和查詢樹(shù)[7]兩類。當(dāng)標(biāo)簽數(shù)目較大時(shí)，二進(jìn)制搜索樹(shù)中常用的二叉樹(shù)算法存在讀取時(shí)延長(zhǎng)和識(shí)別效率較低問(wèn)題，文獻(xiàn)[8]提出了一種改進(jìn)型自適應(yīng)多叉樹(shù)搜索(IAMS)防碰撞算法，根據(jù)標(biāo)簽碰撞因子確定采用二叉樹(shù)或四叉樹(shù)，進(jìn)而優(yōu)化閱讀器發(fā)送前綴，減少碰撞時(shí)隙和空閑時(shí)隙，提升了標(biāo)簽識(shí)別效率。文獻(xiàn)[9]針對(duì)二叉樹(shù)算法復(fù)雜和周期長(zhǎng)缺點(diǎn)，提出了一種結(jié)合ALOHA的二叉樹(shù)防碰撞算法，標(biāo)簽存儲(chǔ)閱讀器賦予的幀時(shí)隙和保持標(biāo)簽分裂樹(shù)可變層，跟蹤其識(shí)別過(guò)程狀態(tài)，進(jìn)而保證標(biāo)簽可被成功識(shí)別，同時(shí)在搜索次數(shù)、傳輸時(shí)延和吞吐率等方面得到改善和提升。

本文針對(duì)傳感標(biāo)簽用于電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)的具體環(huán)境，在IAMS算法基礎(chǔ)上，結(jié)合ALOHA算法，提出一種改進(jìn)的自適應(yīng)時(shí)隙多叉樹(shù)搜索防碰撞(improved adaptive time slot and multi-tree search anti-collision,IATMSA)算法，為面向電氣設(shè)備狀態(tài)監(jiān)測(cè)的傳感標(biāo)簽系統(tǒng)性能評(píng)估和系統(tǒng)部署提供參考。

1電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)體系架構(gòu)

電氣設(shè)備運(yùn)行狀態(tài)和故障信息隨著環(huán)境與設(shè)備運(yùn)行狀況不斷變化，直接影響輸變電設(shè)備的安全穩(wěn)定運(yùn)行。近年來(lái)，基于無(wú)線通信網(wǎng)絡(luò)(GPRS/3G)的絕緣子污穢和導(dǎo)線溫度在線監(jiān)測(cè)裝置在國(guó)內(nèi)外電力公司掛網(wǎng)運(yùn)行。但裝置依賴移動(dòng)通信網(wǎng)，存在通信盲區(qū)，運(yùn)行費(fèi)用高，且無(wú)法完全滿足實(shí)時(shí)性、安全性和準(zhǔn)確性等要求。

將標(biāo)簽與傳感器(溫度、濕度、壓力、加速度等)融合構(gòu)成的傳感標(biāo)簽具有感知和自動(dòng)識(shí)別能力。有源標(biāo)簽自帶電源可為傳感器提供穩(wěn)定能量，具有通信距離遠(yuǎn)和信號(hào)穩(wěn)定特點(diǎn)，適用于電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)[3]。以設(shè)備溫度和加速度參數(shù)監(jiān)測(cè)為例，電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)體系架構(gòu)如圖1所示。溫度和加速度傳感標(biāo)簽采集電氣設(shè)備的溫度與運(yùn)動(dòng)加速度信息，向基站閱讀器發(fā)出申請(qǐng)，基站閱讀器讀取傳感標(biāo)簽信息并將信息通過(guò)傳感網(wǎng)絡(luò)發(fā)送至監(jiān)測(cè)中心，監(jiān)測(cè)中心則根據(jù)接收的信息判斷電氣設(shè)備狀態(tài)和采取相應(yīng)措施。

圖1　電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)體系架構(gòu)Fig 1　System architecture of electrical equipment state monitoring system

2IATMSA算法

2.1IAMS防碰撞算法

當(dāng)傳感標(biāo)簽碰撞數(shù)目較大時(shí)，傳統(tǒng)二叉樹(shù)算法存在讀取時(shí)延長(zhǎng)與識(shí)別效率較低問(wèn)題，文獻(xiàn)[8]在傳統(tǒng)二叉樹(shù)算法基礎(chǔ)上，根據(jù)標(biāo)簽碰撞數(shù)目來(lái)確定采用二叉樹(shù)或四叉樹(shù)，提出了一種IAMS防碰撞算法，通過(guò)優(yōu)化閱讀器發(fā)送前綴減少碰撞時(shí)隙和空閑時(shí)隙，提升標(biāo)簽識(shí)別效率。具體步驟如下：

1)閱讀器初始化前綴棧，發(fā)送查詢命令。

2)與閱讀器發(fā)送前綴相符的標(biāo)簽響應(yīng)。

3)判斷時(shí)隙狀態(tài)，若只有一個(gè)標(biāo)簽響應(yīng)，則成功讀取標(biāo)簽跳轉(zhuǎn)到6；若為空時(shí)隙即沒(méi)有標(biāo)簽響應(yīng)跳轉(zhuǎn)到6；若多個(gè)標(biāo)簽響應(yīng)，則發(fā)生標(biāo)簽碰撞。

4)計(jì)算碰撞因子μ=rc/r=1-(1/2)n-1，其中，r為傳感標(biāo)簽ID碼長(zhǎng)度，rc為碰撞比特位數(shù)，n為傳感標(biāo)簽總數(shù)。令n=3為二叉樹(shù)算法與四叉樹(shù)算法臨界值，則μ=0.75。當(dāng)μ<0.75時(shí)，采用二叉樹(shù)算法，閱讀器根據(jù)一位碰撞位生成兩個(gè)前綴;否則，采用四叉樹(shù)算法，閱讀器要求標(biāo)簽返回高兩位碰撞前綴信息。

5)將新生成前綴寫入堆棧，讀取棧首前綴，并發(fā)送給標(biāo)簽，返回到步驟(2)。

6)判斷棧是否為空，若為空，識(shí)別結(jié)束；否則，讀取棧首前綴，并發(fā)送給標(biāo)簽，返回到步驟(2)。

2.2IATMSA算法

圖1監(jiān)測(cè)系統(tǒng)采用有源傳感標(biāo)簽，傳感標(biāo)簽采集信息后向基站閱讀器發(fā)送申請(qǐng)識(shí)別命令，進(jìn)而閱讀器響應(yīng)并讀取傳感標(biāo)簽信息?；谏鲜鐾ㄔ挋C(jī)制，在IAMS算法基礎(chǔ)上，結(jié)合ALOHA算法，提出一種IATMSA算法。

不同傳感標(biāo)簽發(fā)送申請(qǐng)時(shí)，閱讀器根據(jù)申請(qǐng)順序?yàn)閭鞲袠?biāo)簽分配專有時(shí)隙。若無(wú)其它傳感標(biāo)簽同時(shí)發(fā)送申請(qǐng)，基站命令閱讀器為其分配專有時(shí)隙成功讀取測(cè)量信息。一旦確定專有時(shí)隙，其它傳感標(biāo)簽則無(wú)權(quán)占用該時(shí)隙。若在同一時(shí)刻有兩個(gè)及以上的傳感標(biāo)簽同時(shí)發(fā)送申請(qǐng)，基站則通過(guò)碰撞概率模型計(jì)算傳感標(biāo)簽碰撞數(shù)目，然后采用IAMS防碰撞算法進(jìn)行識(shí)別。IATMSA算法流程圖如圖2所示。

圖2　IATMSA算法流程圖Fig 2　Flow chart of IATMSA algorithm

2.3IATMSA算法性能

傳感標(biāo)簽發(fā)送申請(qǐng)識(shí)別命令，會(huì)出現(xiàn)申請(qǐng)成功和申請(qǐng)碰撞情況。前者傳感標(biāo)簽未存在碰撞時(shí)隙，其總時(shí)隙數(shù)為申請(qǐng)成功的傳感標(biāo)簽數(shù)n1。

假設(shè)T時(shí)間內(nèi)，所有n個(gè)傳感標(biāo)簽發(fā)送申請(qǐng)識(shí)別命令結(jié)束。因只存在申請(qǐng)碰撞時(shí)隙和申請(qǐng)成功時(shí)隙情況，則兩者概率均為1/2，則申請(qǐng)碰撞傳感標(biāo)簽數(shù)為

(1)

式中m為碰撞時(shí)隙標(biāo)簽數(shù)。

其總時(shí)隙數(shù)為[8]

4k+1(1-4-(k+1))n2]+

{0.72n2-4k+1[1-(1-4-(k+1))n2-

(2)

式中k為搜索深度，k=[log4(n2/3)],則所有傳感標(biāo)簽總時(shí)隙數(shù)為

T(n)=n1+T(n2).

(3)

吞吐率為

(4)

碰撞跟蹤樹(shù)算法時(shí)隙數(shù)和四叉樹(shù)算法通過(guò)線性擬合近似的總時(shí)隙數(shù)分別為[8]

track=2n-1,

(5)

t(n)≈2.88n.

(6)

由文獻(xiàn)[10]可推導(dǎo)出二叉樹(shù)算法為

n×2-L(1-2-L)n-1],

(7)

式中L為二叉樹(shù)搜索深度。

3算法仿真與分析

IATMSA算法、二叉樹(shù)算法和碰撞跟蹤樹(shù)算法的總時(shí)隙數(shù)仿真結(jié)果如圖3所示。由圖3可知，相比二叉樹(shù)算法和碰撞跟蹤樹(shù)算法，IAMSA算法總時(shí)隙數(shù)最小，且傳感標(biāo)簽數(shù)目越大，IAMSA算法優(yōu)越性越明顯。

圖3　常用算法總時(shí)隙數(shù)比較Fig 3　Comparison of total time slot number of common algorithms

IATMSA算法、IAMS防碰撞算法及四叉樹(shù)算法的總時(shí)隙數(shù)仿真結(jié)果如圖4所示?？倳r(shí)隙數(shù)直接影響鑒別時(shí)延，鑒別時(shí)延越小，識(shí)別速度越快。由圖4可知，IATMSA算法總時(shí)隙數(shù)小于IAMS防碰撞算法和四叉樹(shù)算法總時(shí)隙數(shù)，則IATMSA算法識(shí)別速度優(yōu)于IAMS防碰撞算法和四叉樹(shù)算法。圖4中IATMSA和IAMS防碰撞算法總時(shí)隙數(shù)在某個(gè)點(diǎn)發(fā)生突變，是因?yàn)樗阉魃疃萲取非負(fù)整數(shù)而導(dǎo)致T(n2)出現(xiàn)非連續(xù)而跳變。

圖4　不同算法總時(shí)隙數(shù)比較Fig 4　Comparison of total time slot number of different algorithms

IATMSA算法、IAMS防碰撞算法及四叉樹(shù)算法的吞吐率比較仿真結(jié)果如圖5所示。由圖5可知，將IATMSA算法應(yīng)用于電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)中，吞吐率明顯優(yōu)于IAMS算法和四叉樹(shù)算法，基本維持在60 %～70 %，最高可達(dá)86 %左右。

圖5　不同算法吞吐率比較Fig 5　Comparison of throughput of different algorithms

4結(jié)論

本文基于電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)環(huán)境，在IAMS防碰撞算法基礎(chǔ)上，結(jié)合ALOHA算法，提出一種IATMSA算法。IATMSA算法針對(duì)電氣設(shè)備狀態(tài)監(jiān)測(cè)系統(tǒng)中選用有源標(biāo)簽這一特點(diǎn)，提出優(yōu)先申請(qǐng)分配專有時(shí)隙原則，在一定程度上減少了傳感標(biāo)簽碰撞時(shí)隙。通過(guò)對(duì)申請(qǐng)命令發(fā)生碰撞的傳感標(biāo)簽數(shù)建立碰撞概率模型，計(jì)算出申請(qǐng)碰撞傳感標(biāo)簽數(shù)，然后對(duì)碰撞傳感標(biāo)簽采用IAMS算法進(jìn)行識(shí)別。算法仿真分析表明:IATMSA算法與IAMS防碰撞算法及四叉樹(shù)算法相比，總時(shí)隙數(shù)更小、識(shí)別速度更快、吞吐率更高。

參考文獻(xiàn):

[1]魯東海，孫純軍，王曉虎．智能變電站中在線監(jiān)測(cè)系統(tǒng)設(shè)計(jì)[J]．電力自動(dòng)化設(shè)備,2011,31(1)：134-137．

[2]劉有為，肖燕，許淵．智能高壓設(shè)備技術(shù)策略分析[J]．電網(wǎng)技術(shù),2010,34(1/2)：11-14．

[3]張丹丹，胡建明，崔婷，等.帶傳感器的射頻識(shí)別技術(shù)在變電站電氣設(shè)備狀態(tài)信息采集中的應(yīng)用[J].高電壓技術(shù),2013,39(11):2623-2630.

[4]Yeh K H，Lo N W，Li Y J，et a1．An adaptive n-resolution anti-collision algorithm for RFID tag identification[C]∥IEEE 24th International Conference on Advanced Information Networking and Applications Workshops,2010：335-338．

[5]Finkenzeller K.RFID handbook,fundamentals and applications in contactless smart cards and identification[M].New York:Wiley,2003.

[6]Myung J,Lee W,Srivastava J.Adaptive binary splitting for efficient RFID tag anti-collision[J].IEEE Communications Letters,2006,10(3):144-146.

[7]Ryu J,Lee H,Seok Y,et al.A hybrid query tree protocol for tag collision arbitration in RFID systems[C]∥Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing，Glasgow:IEEE,2007:5981-5986.

[8]張學(xué)軍，蔡文琦，王鎖萍.改進(jìn)型自適應(yīng)多叉樹(shù)防碰撞算法研究[J].電子學(xué)報(bào),2012,40(1):193-198.

[9]梁士利，徐美玲，林青，等.優(yōu)化結(jié)合二叉樹(shù)和幀時(shí)隙ALOHA的防碰撞算法[J].光學(xué)精密工程,2014,22(9):2580-2584.

[10] Hush D R,Wood C.Analysis of tree algorithms for RFID arbitration[C]∥Proceedings of IEEE Symposium on Information Theory,Cambridge,MA,USA,1998:107-116.

范佳興(1989-)，男，蒙古族，遼寧朝陽(yáng)人，碩士研究生，主要研究方向?yàn)橹悄茈娋W(wǎng)、智能交通。

李兵,通訊作者,E—mail:libinghnu@163.com。

Sensing-tag anti-collision algorithm for electrical equipment state monitoring*

FAN Jia-xing， LI Bing， HE Yi-gang, ZHANG Yu-zhu, ZHANG Li-ming

(School of Electrical Engineering and Automation,Hefei University of Technology,Hefei 230009,China)

Abstract:Radio frequency identification(RFID) sensing-tag is a novel technology for electrical equipment wireless monitoring fused with identification and sensing function,and high efficient anti-collision algorithm is the main way to improve the real time performance of electrical equipment state wireless monitoring system based on RFID sensing-tag technology.Based on improved adaptive multi-tree search (IAMS) anti-collision algorithm,collision sensing-tag number are calculated by collision probability model,the specific slot principle of priority application and priority allocation is established,and an improved adaptive timeslot and multi-tree search anti-collision (IATMSA) algorithm is proposed.Algorithm simulation result indicates that total timeslot numbers of IATMSA is less,identification speed is faster and throughput is higher are better than IAMS and quadtree search algorithms.

Key words:electrical equipment state monitoring; sensing-tag; IATMSA algorithm; proprietary time slot

作者簡(jiǎn)介:

中圖分類號(hào):TN 92

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1000—9787(2016)01—0153—03

*基金項(xiàng)目：教育部科學(xué)技術(shù)研究重大項(xiàng)目(313018)；安徽省自然科學(xué)基金面上項(xiàng)目(1508085MF112)；中國(guó)博士后基金面上項(xiàng)目(2014M561820)；湖南省科技計(jì)劃資助項(xiàng)目(2014FJ6017) 國(guó)家自然科學(xué)基金資助項(xiàng)目(61174197); 江蘇省高?！扒嗨{(lán)工程”項(xiàng)目

收稿日期：2015—04—16 2015—04—01

DOI:10.13873/J.1000—9787(2016)01—0153—03