王 帥李書芳
(北京郵電大學(xué)信息與通信工程學(xué)院 北京 100876)
有效抑制RFID讀寫器間的干擾是RFID技術(shù)應(yīng)用中亟待解決的重要技術(shù)問(wèn)題之一。當(dāng)有限空間內(nèi)分布大量RFID讀寫器時(shí),即使讀寫器識(shí)別范圍未發(fā)生重疊,由于到達(dá)讀寫器端的標(biāo)簽散射信號(hào)比較微弱,仍易受到來(lái)自其它讀寫器信號(hào)的干擾而導(dǎo)致信噪比降低,從而使其標(biāo)稱識(shí)別半徑減小。
針對(duì)讀寫器干擾問(wèn)題,學(xué)界已開展了大量研究,早期研究如 HiQ[1]等多將重點(diǎn)放在減少讀寫器信號(hào)的碰撞概率方面,這些算法的缺陷在于將碰撞的結(jié)果簡(jiǎn)單歸結(jié)為讀取失敗,但該假設(shè)已被后期的一些實(shí)驗(yàn)結(jié)果證明并不嚴(yán)謹(jǐn)。文獻(xiàn)[2]基于近期的實(shí)驗(yàn)結(jié)果,認(rèn)為讀寫器間即使產(chǎn)生碰撞也只會(huì)降低各自的信噪比,識(shí)別半徑相應(yīng)減少但一般不會(huì)減至零,繼而提出了讀寫器間干擾的統(tǒng)計(jì)模型,以及與讀寫器數(shù)量、功率、信道數(shù)有關(guān)的信噪比表達(dá)式。但該文獻(xiàn)認(rèn)為各讀寫器功率相等,且位置呈均勻分布,這對(duì)實(shí)際應(yīng)用來(lái)說(shuō)只是一種理想假設(shè)。文獻(xiàn)[3-5]對(duì)多讀寫器的干擾模型進(jìn)行了研究,分析了讀寫器在干擾環(huán)境下的讀寫距離,給出了路徑損耗因子、信噪比和噪聲功率等參數(shù)對(duì)干擾模型的影響大小。文獻(xiàn)[6]提出了一種分布式功率分配方案,該方案根據(jù)識(shí)別距離的期望值,通過(guò)檢測(cè)信噪比不斷更新發(fā)射功率。文獻(xiàn)[7]提出通過(guò)檢測(cè)接收信號(hào)強(qiáng)度的方法實(shí)時(shí)調(diào)整發(fā)射功率。算法收到標(biāo)簽返回的信號(hào)后,先根據(jù)其 RSSI(Received Signal Strength Indication)值估計(jì)出讀寫器和標(biāo)簽間的距離,然后根據(jù)所估計(jì)的距離將發(fā)射功率調(diào)整到合適的數(shù)值。文獻(xiàn)[8]根據(jù)檢測(cè)到的信噪比,采用具有回退功能的功率控制算法調(diào)整發(fā)射功率。與文獻(xiàn)[6]相比,該算法通過(guò)引入回退功能,有效避免了因各讀寫器貪婪增大功率導(dǎo)致的功率“死鎖”(各個(gè)讀寫器功率已達(dá)到最大值,但仍在試圖增大功率以致陷入死鎖)的情況。上述功率控制算法雖然在一定程度上起到了抑制讀寫器間干擾的作用,但本質(zhì)上都屬于啟發(fā)式算法,難以實(shí)現(xiàn)多讀寫器識(shí)別性能的全局優(yōu)化和公平性。
本文分析了在讀寫器位置隨機(jī)分布條件下如何分配功率以最大程度抑制讀寫器間干擾的問(wèn)題,首先提出了信噪比估計(jì)式,并對(duì)估計(jì)式的性能進(jìn)行了評(píng)估;根據(jù)RFID系統(tǒng)的應(yīng)用需求,將讀寫器功率分配定義為自適應(yīng)加權(quán)公平問(wèn)題,并從理論上證明了該問(wèn)題可以等價(jià)為求解指定效用函數(shù)的加權(quán)優(yōu)化問(wèn)題;為使算法在實(shí)際應(yīng)用中更易于實(shí)現(xiàn),設(shè)計(jì)了分布式功率更新算法,并對(duì)其收斂性進(jìn)行了證明。
以文獻(xiàn)[2]的讀寫器干擾模型為基礎(chǔ),本文研究的多讀寫器系統(tǒng)應(yīng)用場(chǎng)景如圖1所示,在半徑為D的區(qū)域內(nèi)隨機(jī)分布若干個(gè)讀寫器,每個(gè)讀寫器功率均可調(diào),且作如下假設(shè)和條件設(shè)定:
圖1 多讀寫器干擾模型
(1)讀寫器間距離d大于最小距離 rmin,rmin的設(shè)定以保證讀寫器識(shí)別范圍不發(fā)生重疊為原則,避免標(biāo)簽端讀寫器碰撞的情形發(fā)生。
(2)路徑損耗與dγ成比例,其中γ設(shè)為2.5。
(3)讀寫器干擾為非相干的加性干擾,即多讀寫器對(duì)于某位置的干擾等同于單個(gè)讀寫器干擾的疊加。
(4)讀寫器具有兩個(gè)狀態(tài):活動(dòng)狀態(tài)和非活動(dòng)狀態(tài),處于活動(dòng)狀態(tài)的概率為,讀寫器只有處于活動(dòng)狀態(tài)時(shí)才會(huì)產(chǎn)生干擾。
(5)讀寫器采用跳頻通信模式,每次所用信道可在50個(gè)信道中隨機(jī)選擇。
(6)每個(gè)讀寫器的標(biāo)稱讀寫半徑均為 Rnom,通過(guò)調(diào)節(jié)發(fā)射功率,實(shí)際讀寫半徑可以大于或小于Rnom。
讀寫器周期性發(fā)出查詢命令,識(shí)別處于標(biāo)稱識(shí)別半徑內(nèi)(如圖 1虛線所示)的標(biāo)簽。當(dāng)工作區(qū)域內(nèi)讀寫器數(shù)量增加,干擾程度加大時(shí),實(shí)際可識(shí)別半徑 Rreal將低于標(biāo)稱值,可通過(guò)合理調(diào)節(jié)每個(gè)讀寫器的發(fā)射功率抑制讀寫半徑的下降。
在功率控制算法設(shè)計(jì)中,設(shè)備接收端的信噪比是十分重要的參數(shù),功控算法一般要根據(jù)檢測(cè)到的信噪比和其它參數(shù)進(jìn)行計(jì)算和控制。獲取信噪比除了硬件測(cè)量的方式,也可通過(guò)接收數(shù)據(jù)誤包率間接得出,而且,當(dāng)設(shè)備不具備信噪比檢測(cè)功能時(shí)采用這種方法更為實(shí)用,因?yàn)椴挥妙~外增加檢測(cè)硬件。
讀寫器與標(biāo)簽間通信采用 TDMA幀時(shí)隙方式,每一幀被劃分為若干個(gè)時(shí)隙,讀寫器通過(guò)幀頭發(fā)出查詢命令后,每個(gè)標(biāo)簽任意選擇一個(gè)時(shí)隙發(fā)送數(shù)據(jù),每個(gè)時(shí)隙有 3種可能狀態(tài):空閑(無(wú)標(biāo)簽)、成功(僅一個(gè)標(biāo)簽)和碰撞(兩個(gè)或以上標(biāo)簽)[912]-。設(shè)當(dāng)前幀長(zhǎng)(即時(shí)隙數(shù)量)為L(zhǎng),檢測(cè)到空閑時(shí)隙、成功時(shí)隙和碰撞時(shí)隙的個(gè)數(shù)分別為1X,2X,3X。由于噪聲和干擾的存在,數(shù)據(jù)包即使未發(fā)生碰撞也可能出現(xiàn)接收錯(cuò)誤,導(dǎo)致一些成功時(shí)隙轉(zhuǎn)化成碰撞時(shí)隙(無(wú)法正確解碼,等同于多標(biāo)簽碰撞的情況),將處于該時(shí)隙的數(shù)據(jù)包稱為錯(cuò)誤包。設(shè)a為錯(cuò)誤包個(gè)數(shù),則真正的成功時(shí)隙和碰撞時(shí)隙的個(gè)數(shù)應(yīng)為和。對(duì)于每一幀,不同類型的時(shí)隙個(gè)數(shù)組成向量,對(duì)應(yīng)的期望值組成向量,其中和可根據(jù)文獻(xiàn)[13-15]由式(1)-式(3)給出:
式中n為標(biāo)簽數(shù)量。實(shí)際中無(wú)法獲得n和a的真實(shí)值,但n和a越接近真實(shí)值,觀測(cè)向量和期望向量E[X']間的相似程度就越高。根據(jù)模式識(shí)別理論,可以用歐式距離的方法衡量?jī)蓚€(gè)向量的相似程度,即尋找使X'與E[X']的歐式距離最小的n和a作為估計(jì)值:
定義 1 已知錯(cuò)誤包個(gè)數(shù)a,設(shè)誤包率真值為pe,定義誤包率估計(jì)子為
下面分析該估計(jì)子的統(tǒng)計(jì)特性。
定理 1 令sp表示時(shí)隙為成功狀態(tài)的概率,設(shè)各成功時(shí)隙誤包與否相互獨(dú)立,則按式(5)定義的誤包率估計(jì)式為無(wú)偏估計(jì)。
證明
因此,式(5)定義的估計(jì)式無(wú)偏。 證畢
標(biāo)簽信號(hào)采用 ASK調(diào)制,讀寫器接收端誤比特率為
本文研究在多讀寫器環(huán)境下如何通過(guò)調(diào)節(jié)各自的功率以保證各讀寫器性能(讀寫半徑或接收信噪比)均能保持在標(biāo)稱值附近的問(wèn)題。提出自適應(yīng)加權(quán)功率分配算法,基本思想是在比例公平算法的基礎(chǔ)上,增加自適應(yīng)權(quán)重因子,當(dāng)某讀寫器性能趨向低于標(biāo)稱值時(shí),其權(quán)重值自動(dòng)增大,引導(dǎo)資源更多地分配給該讀寫器。以文獻(xiàn)[16]中比例公平問(wèn)題定義為基礎(chǔ),將本文的問(wèn)題建模為自適應(yīng)比例公平問(wèn)題。
定義 2 向量*x稱為自適應(yīng)比例公平解,如果其為可行解并且對(duì)于任意向量x,則式(10)成立
可以將定義2的問(wèn)題轉(zhuǎn)化為最優(yōu)化問(wèn)題以方便求解??紤]式(11)的最優(yōu)化問(wèn)題:
其中。
證明 先證充分性。令*x為問(wèn)題式(11)的解,通過(guò)計(jì)算可得到
由式(14)和式(15)可知問(wèn)題式(11)的漢森矩陣負(fù)定,因此目標(biāo)函數(shù)式(11)是嚴(yán)格凸函數(shù),存在唯一的最優(yōu)解。設(shè)λ為待定系數(shù),令
問(wèn)題式(11)最優(yōu)解*x的Karush-Kuhn-Tucker(KKT)條件為
用讀寫器信噪比取代問(wèn)題式(11)中的自變量x,可得到讀寫器功率控制問(wèn)題的最終形式:
問(wèn)題式(21)對(duì)于向量P是非凸問(wèn)題,一般來(lái)說(shuō)求解較為困難。本文采用分布式算法簡(jiǎn)化運(yùn)算,其基本思想是將問(wèn)題式(21)的全局求解問(wèn)題轉(zhuǎn)化為分布式的局部?jī)?yōu)化問(wèn)題,每個(gè)讀寫器利用式(21)只更新自己的功率值。為了減輕信道負(fù)荷,每個(gè)讀寫器采用第3節(jié)中的方法,周期性地估計(jì)當(dāng)前的信噪比并與標(biāo)稱值比較,只有當(dāng)信噪比低于標(biāo)稱值時(shí)才向外發(fā)送功率更新請(qǐng)求及自己的功率值,啟動(dòng)更新過(guò)程。以下是分布式算法的具體步驟(不失一般性,設(shè)算法運(yùn)行在讀寫器s上):
(1)初始化。將發(fā)射功率sP調(diào)整為預(yù)設(shè)值(默認(rèn)設(shè)置在標(biāo)稱值附近),啟動(dòng)讀寫器工作;
(2)標(biāo)簽識(shí)別和時(shí)隙狀態(tài)采集。發(fā)出標(biāo)簽識(shí)別命令 query,在標(biāo)簽響應(yīng)幀中收集空閑、成功和碰撞的時(shí)隙個(gè)數(shù),用式(9)計(jì)算和更新信噪比的估計(jì)值;
(3)功率控制。根據(jù)信噪比的大小選擇相應(yīng)的控制策略:
上述分布式算法涉及到兩個(gè)問(wèn)題:一是算法是否收斂,二是如果收斂,其收斂點(diǎn)是否為問(wèn)題式(21)的局部最優(yōu)解。下面圍繞這兩個(gè)問(wèn)題展開討論。
不失一般性,考慮讀寫器s的局部?jī)?yōu)化問(wèn)題。
定理 3 對(duì)于讀寫器s,問(wèn)題式(22)是凸優(yōu)化問(wèn)題。
證明 對(duì)于讀寫器s,將式(22)重寫為
證畢
每個(gè)讀寫器通過(guò)求解式(22)的局部目標(biāo)函數(shù)更新自己的功率值,相應(yīng)地,式(21)的全局目標(biāo)函數(shù)的值也隨之變化。令 ()L t為t時(shí)刻式(21)的值,則有:
定理 4 (1)分布式更新算法收斂,即存在*L:;(2)設(shè)算法在處取得,則,都不會(huì)被更新,且為問(wèn)題式(21)的KKT點(diǎn)。
證明
將本文方案與3個(gè)方案進(jìn)行對(duì)比,分別是文獻(xiàn)[2]中基于均勻分布假設(shè)的固定功率分配方案,文獻(xiàn)[16]中的比例公平功率分配方案,以及文獻(xiàn)[8]中的功率可回退控制方案 BKPC(BacKoff Power Control),在比例公平功率分配方案中采用與式(21)類似的形式,并使用相同的效用函數(shù),只是令恒為1。仿真參數(shù)按第2節(jié)中相應(yīng)數(shù)據(jù)設(shè)置。
首先將最小信噪比作為衡量算法公平性的指標(biāo)。從圖2可看出隨著用戶數(shù)的增加,讀寫器間距在不斷縮小,相互之間干擾也隨之加大,最小信噪比隨著用戶數(shù)的增加有降低的趨勢(shì)。均勻分布假設(shè)下的功率固定分配算法根據(jù)工作區(qū)域大小和讀寫器密度參數(shù),功率分配的公平性較差,最小信噪比最低。功率可回退控制方案根據(jù)信噪比調(diào)節(jié)輸出功率,性能要好于固定分配方案。比例公平算法考慮了功率分配的公平性,最小信噪比要大于均勻分配算法和功率可回退控制方案,但采用該算法當(dāng)讀寫器密度很大時(shí),仍會(huì)發(fā)生個(gè)別讀寫器信噪比遠(yuǎn)小于標(biāo)準(zhǔn)信噪比的情況。本文提出的自適應(yīng)加權(quán)算法基于比例公平算法,同時(shí)對(duì)處于高密度區(qū)域的讀寫器自動(dòng)增加權(quán)重,使處于嚴(yán)重干擾區(qū)域下的讀寫器仍能盡量保證一定的信噪比,最小信噪比高于其它 3種算法。
讀寫器信噪比標(biāo)準(zhǔn)差是衡量算法公平性的另一個(gè)指標(biāo)。如圖3所示,固定功率分配算法以讀寫器位置均勻分布為假設(shè),不考慮干擾程度隨位置變化的因素,方差最大。功率可回退控制方案采用啟發(fā)式算法,通過(guò)回退僅能實(shí)現(xiàn)有限的全局優(yōu)化能力,信噪比仍有較大的方差。比例公平算法將讀寫器位置信息考慮在內(nèi),公平性要比均勻分配和功率回退算法好。本文提出的自適應(yīng)加權(quán)算法除了具有比例公平算法的優(yōu)點(diǎn)外,還可以根據(jù)讀寫器所處環(huán)境狀況自動(dòng)調(diào)節(jié)權(quán)重因子,最大程度地減小讀寫器密度分布差異對(duì)功率分配公平性的影響,方差要低于上述3種算法。
在多讀寫器應(yīng)用場(chǎng)景中,各讀寫器由于所受干擾不同,其數(shù)據(jù)吞吐量也各不相同。圖4顯示了多讀寫器中平均吞吐量的數(shù)值和趨勢(shì)比較,通信數(shù)率設(shè)為100 bit/s。由圖可見(jiàn),當(dāng)讀寫器個(gè)數(shù)增加時(shí),4種算法的最小吞吐量都逐漸減小,且當(dāng)數(shù)量較多時(shí)趨于某固定數(shù)值,說(shuō)明4種功率控制算法都只能在一定讀寫器數(shù)量下發(fā)揮作用。由圖可見(jiàn),自適應(yīng)加權(quán)算法性能始終優(yōu)于其它3種算法,其吞吐量隨讀寫器數(shù)量增多而下降的速度也最為緩慢。
圖5顯示了本文提出的分布式算法收斂性能,給出了分布式算法求得的局部最優(yōu)解與全局最優(yōu)解的相對(duì)誤差,并與等比例分配和BKPC算法的收斂性做了比較。從圖中可以看出,隨著迭代次數(shù)的增加,自適應(yīng)加權(quán)算法的迭代值穩(wěn)定地收斂,且與全局最優(yōu)解的相對(duì)誤差逐漸減小,當(dāng)?shù)螖?shù)大于150時(shí),相對(duì)誤差可控制在3%以內(nèi),說(shuō)明該分布式算法具有良好的收斂性能,且盡管求出的是局部最優(yōu)解,但滿足一定的迭代次數(shù)后非常接近全局最優(yōu)解。等比例分配由于算法流程與自適應(yīng)加權(quán)相同,因此具有相近的收斂特性。BKPC算法基于啟發(fā)式調(diào)整策略,在迭代過(guò)程中迭代值波動(dòng)幅度較大,收斂的速度最慢,當(dāng)?shù)螖?shù)大于200時(shí)才能穩(wěn)定地使誤差控制在3%以內(nèi)。
圖6比較了算法在時(shí)間復(fù)雜度方面的性能,其中BKPC,等比例分配,自適應(yīng)分配方案中更新周期設(shè)為0.1 s, BKPC中的回退周期設(shè)為0.1~0.5 s。由圖中可以看出,由于等比例分配和自適應(yīng)分配方案的收斂迭代次數(shù)小于BKPC算法,達(dá)到收斂值消耗的時(shí)間也明顯少于BKPC。
以上比較了固定場(chǎng)景的算法性能,下面考察移動(dòng)環(huán)境下,即區(qū)域內(nèi)讀寫器數(shù)量和位置發(fā)生變化時(shí)的性能。圖7所示為讀寫器位置和數(shù)量每隔30 s變化一次,其中位置做隨機(jī)變化,數(shù)量變化的方式做如下設(shè)定:(1)0~29 s內(nèi)有 40個(gè)讀寫器共存;(2)30~59 s內(nèi)新加入 20個(gè)讀寫器,共有 60個(gè);(3)60~89 s內(nèi)又加入 20個(gè)讀寫器,共有 80個(gè);(4)90 ~120 s內(nèi)又加入20個(gè)讀寫器,共有100個(gè);(5)120 ~150 s內(nèi)20個(gè)讀寫器離開,總數(shù)恢復(fù)到80個(gè)。將固定算法分配方案中讀寫器數(shù)量參數(shù)設(shè)為 70個(gè)(因圖7平均數(shù)量約為70),BKPC,等比例分配,自適應(yīng)分配方案中更新周期設(shè)為0.1 s, BKPC中的回退周期設(shè)為0.1~0.5 s。由圖6可看出,當(dāng)讀寫器由于移動(dòng)而使區(qū)域內(nèi)數(shù)量改變時(shí),自適應(yīng)功率分配算法可以很快收斂到最優(yōu)值(9 s以內(nèi)),而且最小吞吐量始終高于其它3種算法,說(shuō)明算法在移動(dòng)場(chǎng)景下具有較好的適應(yīng)能力。
圖2 4種方法的最小信噪比
圖3 4種方法的信噪比標(biāo)準(zhǔn)方差
圖4 4種方法的平均吞吐量比較
圖5 3種方法的分布式算法收斂性能
圖6 3種算法的時(shí)間復(fù)雜度比較
圖7 4種功控算法的實(shí)時(shí)性能
讀寫器間干擾是多讀寫器應(yīng)用場(chǎng)景中面臨的主要問(wèn)題。本文提出的自適應(yīng)權(quán)重功率分配算法對(duì)低于標(biāo)稱信噪比的讀寫器自動(dòng)增加權(quán)重因子,使處于不同位置,所受干擾程度不同的讀寫器識(shí)別質(zhì)量均能盡量接近標(biāo)稱值,滿足RFID系統(tǒng)在應(yīng)用中的實(shí)際需求,提出的分布式實(shí)現(xiàn)方法進(jìn)一步提高了算法的實(shí)用性。仿真表明,算法在公平性和收斂性方面均表現(xiàn)出良好的性能,是解決RFID讀寫器干擾問(wèn)題的有效方法。
[1] Ho J, Engels W, and Sarma S. HiQ: a hierarchical Q-learning algorithm to solve the reader collision problem[C].Proceedings of 2006 International Symposium on Applications and the Internet Workshops, Phoenix, 2006: 88-91.
[2] Kim Do-Yun, Yoon Hyun-Goo, and Jang Byung-Jun. Effects of reader-to-reader interference on the UHF RFID interrogation range[J]. IEEE Transactions on Industrial Electronics, 2009, 56(7): 2337-2346.
[3] Zhang Lin-chao, Ferrero Renato, and Gandino Filippo.Evaluation of single and additive interference models for RFID collisions[J]. Mathematical and Computer Modelling,2013, 52(3): 901-909.
[4] Yojima Hiroyuki, Tanaka Yu, and Umeda Yohtaro. Analysis of read range for UHF passive RFID tags in close proximity with dynamic impedance measurement of tag ICs[C]. IEEE Radio and Wireless Week, Phoenix, 2011: 110-113.
[5] Zhang Lin-chao, Ferrero Renato, and Gandino Filippo. A comparison between single and additive contribution in RFID reader-to-reader interference models[C]. Proceedings of 6th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Palermo, 2012: 177-184.
[6] Dai Hongyue. Research on the distributed power control algorithm for RFID readers[C]. 2010 6th International Conference on Wireless Communications, Networking and Mobile Computing, Chengdu, 2010: 1-4.
[7] Boaventura A S and Carvalho N B. A proposal for dynamic power control in RFID and passive sensor systems based on RSSI[C]. Proceedings of 6th European Conference on Antennas and Propagation, Prague, 2011: 3473-3475.
[8] Wu Li-ming, Chen Tai-wai, and Xiang Ying. RFID anticollision for internet of things based on power control and backoff algorithm[J]. International Journal of Advancements in Computing Technology, 2012, 4(22): 560-566.
[9] Zhen B, Kobayashi M, and Shimizu M. Framed Aloha for multiple RFID objects identi?cation[J]. IEICETransactions on Communications, 2005, 57(8): 991-999.
[10] Kodialam M and Nandagopal T. Fast and reliable estimation schemesin RFID systems[C]. Proceedings of the Annual International Conference on Mobile Computing and Networking, California, 2006: 322-333.
[11] Harald Vogt. Efficient object identification with passive RFID tags[C]. Pervasive Computing, Zürich, Switzerland,2002: 98-113.
[12] Yu Zeng and Yuan Tan. A low-complexity tag number estimate in EFSA protocol for RFID tag anti-collision[J].Lecture Notes in Electrical Engineering, 2011, 102(3):495-502.
[13] Zhou Lin, Li Zhen, and Chen Ying-mei. The research on electronic tag quantity estimate arithmetic based on probability statistics[J]. Communications in Computer and Information Science, 2012, 59(4): 254-261.
[14] Liu Jing and Wu Hai-feng. The tag estimation and frame length determination with capture effect in dynamic frame slotted ALOHA about RFID[J]. Advances in Intelligent and Soft Computing, 2012, 32(6): 117-123.
[15] Deng Der-jiunn. Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J]. Wireless Personal Communications, 2011, 59(1): 109-122.
[16] Kelly Frank. Charging and rate control for elastic traffic[J]. European Transactions on Telecommunications, 1997,8(1): 33-37.