信息采集協(xié)議的時(shí)效性分析

李雪竹,宋子?xùn)|

宿州學(xué)院信息工程學(xué)院，安徽宿州，234000

射頻識(shí)別(RFID)系統(tǒng)已經(jīng)被應(yīng)用于各類程序，比如庫存控制、目標(biāo)跟蹤和倉庫管理等。一個(gè)典型的RFID系統(tǒng)由一個(gè)或多個(gè)讀寫器和大量的標(biāo)簽組成，每個(gè)標(biāo)簽都有一個(gè)唯一的ID身份標(biāo)識(shí)，并且被連接到一個(gè)物理對(duì)象上。讀寫器能夠識(shí)別或通過相應(yīng)的標(biāo)簽跟蹤到這個(gè)對(duì)象。實(shí)際上，RFID標(biāo)簽在距離上的操作是有限的。因此，在倉庫或者超市這樣大范圍的RFID部署中，為了確保覆蓋整個(gè)區(qū)域，則需要安裝多路的讀寫器[1]。

本文分析了兩種解決多讀寫器信息采集的問題，一種是直接從已有的單一讀寫器RFID系統(tǒng)的信息采集協(xié)議上擴(kuò)展，這種方案在執(zhí)行時(shí)間上并不是高效的，在有沖突的地方要花費(fèi)很多費(fèi)用。另一種是基于布魯姆過濾器的信息采集協(xié)議(BIC)。布魯姆過濾器被網(wǎng)絡(luò)建構(gòu)并且被傳輸給讀寫器，為了高效地識(shí)別訊問標(biāo)簽，也為了信息傳輸時(shí)減少碰撞，讀寫器使用一個(gè)哈希函數(shù)為每一個(gè)訊問標(biāo)簽分配一個(gè)唯一的時(shí)間空擋[2]。

1 研究背景

關(guān)于RFID系統(tǒng)的ID信息采集協(xié)議，已有的能夠被分為三大類：基于ALOHA的、基于樹的和混合的。在多讀寫器環(huán)境中的ID采集問題有標(biāo)簽和讀寫器的傳輸碰撞。

文獻(xiàn)[2]中設(shè)計(jì)了兩個(gè)協(xié)議，分別稱為單一的哈希信息采集協(xié)議(SIC)和多哈希信息采集協(xié)議(MIC)，為了用最優(yōu)化的執(zhí)行時(shí)間從大量的標(biāo)簽中閱讀傳感器產(chǎn)生的數(shù)據(jù)。文獻(xiàn)[3]從能源效率的各個(gè)方面研究了信息采集協(xié)議。輪詢協(xié)議The Tag-Ordering (TOP)及其加強(qiáng)版提出的讀寫器，能用最小的能量消耗從標(biāo)簽系統(tǒng)的子集收集傳感信息。以上協(xié)議都是單一讀寫器的RFID系統(tǒng)，并且假設(shè)讀寫器從它采集到的信息里已經(jīng)識(shí)別了標(biāo)簽的ID。但是在有多讀寫器的大范圍的RFID系統(tǒng)中，由于有限的訪問區(qū)域和標(biāo)簽的流動(dòng)性，在RFID讀寫器之間的一些信息是無效的，因此，以上協(xié)議不能有效地處理多讀寫器的信息采集問題，如何為多讀寫器的RFID系統(tǒng)設(shè)計(jì)信息采集協(xié)議的時(shí)效性仍在探索中[1]。

2 系統(tǒng)分析研究的準(zhǔn)備工作

在多個(gè)讀寫器的大范圍的RFID系統(tǒng)中，盡管讀寫器互相之間能夠從數(shù)據(jù)庫里獲取所有標(biāo)簽的ID，但是，由于訪問區(qū)域的限制和標(biāo)簽的移動(dòng)性，仍會(huì)有一些未知的信息，比如當(dāng)前哪些標(biāo)簽在什么區(qū)域或者從哪里采集它的傳感信息等[4]。因此，讀寫器為了收集信息就首先需要確定標(biāo)簽所在的區(qū)域，這使得對(duì)多讀寫器的信息采集協(xié)議的分析更加復(fù)雜。

在RFID系統(tǒng)中，用M表示標(biāo)簽的集合，并且m=|M|,用N表示在某個(gè)讀寫器的訪問區(qū)域內(nèi)的標(biāo)簽的集合，并且n=|N|,顯然N?M，并且n≤m。用p代表n/m，假設(shè)所有的傳感信息包含相同的位數(shù)，用Tinf表示一個(gè)標(biāo)簽發(fā)送信息的時(shí)間槽的長度，那么讀寫器為了從它所有的訪問標(biāo)簽上采集信息，任何一個(gè)協(xié)議執(zhí)行時(shí)間的下限在N集合中是n×Tinf，這個(gè)下限是無法達(dá)到的，因?yàn)樗鼮榱俗R(shí)別區(qū)域內(nèi)的訪問標(biāo)簽發(fā)送的控制信息要花費(fèi)額外時(shí)間，而且還要協(xié)調(diào)傳送沖突[5]。

3 傳統(tǒng)的解決方案

根據(jù)讀寫器識(shí)別訊問標(biāo)簽的方法，所有的標(biāo)簽都可以被分成以下兩類：第一類是IDPS，基于協(xié)議的ID采集。IDPS執(zhí)行時(shí)間的下限是n×T，這是所有的訊問標(biāo)簽在發(fā)送他們的信息和ID號(hào)所需要時(shí)間的集合(aggregation)。第二類被稱為SIPS。PIC和MIC是SIPS的兩種實(shí)例。SIPS執(zhí)行時(shí)間的下限是(m-n)×Tdet+n×tinf。以上是不同的多讀寫器信息采集協(xié)議的時(shí)間性能分析[8]。

4 基于信息采集協(xié)議的布魯姆過濾器

布魯姆過濾器是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合[9-10]。因此，如果在N集合內(nèi)，能夠以布魯姆過濾器的形式傳送給讀寫器，對(duì)訪問標(biāo)簽的標(biāo)識(shí)和信息采集協(xié)議的執(zhí)行時(shí)間會(huì)有很大程度的減少[1]。

5 用不同數(shù)量的標(biāo)簽的執(zhí)行時(shí)間比較

首先分析BIC在不同的m值下,比如從10 000到100 000不等，對(duì)于每個(gè)m值,假設(shè)n=0.1m,這樣比率ρ在一系列模擬中保持一個(gè)常數(shù)。當(dāng)信息是1位時(shí)，表1演示了不同的多讀寫器信息收集協(xié)議的執(zhí)行時(shí)間[7]，結(jié)果表明，BIC優(yōu)于其他所有協(xié)議。例如,當(dāng)m=50 000和n=5 000,它花費(fèi)讀寫器約212.4 s來收集所有的信息，用PIC,大約是1.6 s,是下限的133倍。AIC的工作比PIC要好些,它只是需要29.0 s。MIC進(jìn)一步減少了執(zhí)行時(shí)間到25.8 s。BIC有最小的執(zhí)行時(shí)間4.0 s,這僅僅是下界的2.5倍[1](以s為單位)。

表1 當(dāng)傳感器信息是1位時(shí)執(zhí)行時(shí)間比較

表2 當(dāng)傳感器信息是8位時(shí)執(zhí)行時(shí)間比較

表3 當(dāng)傳感器信息是16位時(shí)執(zhí)行時(shí)間比較

表2和3顯示了信息長度分別是8位和16位的實(shí)驗(yàn)結(jié)果。可以看出，BIC仍能達(dá)到所有協(xié)議中最高的時(shí)間效率。例如，當(dāng)m=30 000,n=3 000和信息是8位長時(shí)，BIC的執(zhí)行時(shí)間是1.4 s,MIC的執(zhí)行時(shí)間大約20.1 s，AIC的執(zhí)行時(shí)間是18.5 s,PIC執(zhí)行時(shí)間是127.8 s；當(dāng)m=75 000,n=7 500和信息是16位時(shí),BIC的執(zhí)行時(shí)間是4.5 s，MIC的執(zhí)行時(shí)間是63.3 s，AIC的執(zhí)行時(shí)間是49.3 s，PIC的執(zhí)行時(shí)間是320.7 s。

6 結(jié)束語

大范圍RFID系統(tǒng)中，在安裝多讀寫器情況下，采集傳感信息的時(shí)效性不同于單一讀寫器的RFID系統(tǒng)。直接從單一讀寫器信息采集協(xié)議中延伸出來的方案，由于要識(shí)別訪問標(biāo)簽的高負(fù)荷，所以，在執(zhí)行時(shí)間上效率是不高的；而基于布魯姆過濾器的信息采集協(xié)議BIC，其過濾器訪問標(biāo)簽的集合表現(xiàn)為分布式的構(gòu)建和傳輸給讀寫器，這在降低訪問標(biāo)簽的標(biāo)識(shí)費(fèi)用和改進(jìn)多讀寫器信息采集協(xié)議的執(zhí)行性能上有很大意義。

參考文獻(xiàn)：

[1]Hao Yue,Chi Zhang,Miao Pan, et al.A Time-efficient Information Collection Protocol for Large-scale RFID Systems[J].Proceedings IEEE INFOCOM，2012,23(11):2094-2106

[2]Shigang Chen,Ming Zhang,Bin Xiao.Efficient Information Collection Protocols for Sensor-augmented RFID Networks[C]//Shanghai，China:Proc of Info Com，2011:3101-3109

[3]Y Qiao,S Chen,T Li,et al.Energy-efficient Polling Protocols in RFID Systems[C]//Las Vegas:Proc of Mobi Hoc，2011:2094-2106

[4]Sun,Junqing，Peterson,Gregory D.An Effective Execution Time Approximation Method for Parallel Computing[J].IEEE Journals & Magazines，2012,23(11):2024-2032

[5]M Liao,X L Zhong,Y Qiao,et al.Effects of film thickness on microstructure and properties of Bi3.15Nd0.85Ti3O12thin films fabricated by chemical solution deposition[J].Journal of Alloys and Compounds-J ALLOYS COMPOUNDS，2009,48(7):331-334

[6]熊春如.基于RFID的智能數(shù)據(jù)采集終端的研究與設(shè)計(jì)[J].電氣自動(dòng)化，2008,30(5):54-56

[7]Wen Luo,Shigang Chen,Tao Li,et al.Efficient missing tag detection in RFID systems[C]//Shanghai，China:INFOCOM，2011:356-360

[8]Amir A,Efrat A,Myllymaki J,et al.Buddy tracking:efficient proximity detection among mobile friends[C].Hong Kong:Proceedings of IEEE INFOCOM IEEE,2004:7-11

[9]Thomas B.Generating network-based moving objects[C]// Proceedings of International Conference on Scientific and Statistical Database Management. Berlin:IEEE,2000:253-256

[10]Kai Bu,Bin Xiao,Qingjun Xiao,et al.Efficient Misplaced-Tag Pinpointing in Large RFID Systems[J].Proceedings IEEE INFOCOM，2012,11(23):2094-2106