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

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

?

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

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

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

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

關鍵詞:電氣設備狀態(tài)監(jiān)測； 傳感標簽； 改進的自適應時隙多叉樹防碰撞算法； 專有時隙

0引言

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

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

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

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

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

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

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

2IATMSA算法

2.1IAMS防碰撞算法

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

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

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

3)判斷時隙狀態(tài)，若只有一個標簽響應，則成功讀取標簽跳轉到6；若為空時隙即沒有標簽響應跳轉到6；若多個標簽響應，則發(fā)生標簽碰撞。

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

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

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

2.2IATMSA算法

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

不同傳感標簽發(fā)送申請時，閱讀器根據申請順序為傳感標簽分配專有時隙。若無其它傳感標簽同時發(fā)送申請，基站命令閱讀器為其分配專有時隙成功讀取測量信息。一旦確定專有時隙，其它傳感標簽則無權占用該時隙。若在同一時刻有兩個及以上的傳感標簽同時發(fā)送申請，基站則通過碰撞概率模型計算傳感標簽碰撞數目，然后采用IAMS防碰撞算法進行識別。IATMSA算法流程圖如圖2所示。

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

2.3IATMSA算法性能

傳感標簽發(fā)送申請識別命令，會出現申請成功和申請碰撞情況。前者傳感標簽未存在碰撞時隙，其總時隙數為申請成功的傳感標簽數n1。

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

(1)

式中m為碰撞時隙標簽數。

其總時隙數為[8]

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

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

(2)

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

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

(3)

吞吐率為

(4)

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

track=2n-1,

(5)

t(n)≈2.88n.

(6)

由文獻[10]可推導出二叉樹算法為

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

(7)

式中L為二叉樹搜索深度。

3算法仿真與分析

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

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

IATMSA算法、IAMS防碰撞算法及四叉樹算法的總時隙數仿真結果如圖4所示。總時隙數直接影響鑒別時延，鑒別時延越小，識別速度越快。由圖4可知，IATMSA算法總時隙數小于IAMS防碰撞算法和四叉樹算法總時隙數，則IATMSA算法識別速度優(yōu)于IAMS防碰撞算法和四叉樹算法。圖4中IATMSA和IAMS防碰撞算法總時隙數在某個點發(fā)生突變，是因為搜索深度k取非負整數而導致T(n2)出現非連續(xù)而跳變。

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

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

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

4結論

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

參考文獻:

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

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

[3]張丹丹，胡建明，崔婷，等.帶傳感器的射頻識別技術在變電站電氣設備狀態(tài)信息采集中的應用[J].高電壓技術,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]張學軍，蔡文琦，王鎖萍.改進型自適應多叉樹防碰撞算法研究[J].電子學報,2012,40(1):193-198.

[9]梁士利，徐美玲，林青，等.優(yōu)化結合二叉樹和幀時隙ALOHA的防碰撞算法[J].光學精密工程,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-)，男，蒙古族，遼寧朝陽人，碩士研究生，主要研究方向為智能電網、智能交通。

李兵,通訊作者,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

作者簡介:

中圖分類號:TN 92

文獻標識碼:A

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

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

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

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