RFID多讀寫器自適應加權功率分配算法

王 帥李書芳

(北京郵電大學信息與通信工程學院 北京 100876)

1 引言

有效抑制RFID讀寫器間的干擾是RFID技術應用中亟待解決的重要技術問題之一。當有限空間內分布大量RFID讀寫器時，即使讀寫器識別范圍未發生重疊，由于到達讀寫器端的標簽散射信號比較微弱，仍易受到來自其它讀寫器信號的干擾而導致信噪比降低，從而使其標稱識別半徑減小。

針對讀寫器干擾問題，學界已開展了大量研究，早期研究如 HiQ[1]等多將重點放在減少讀寫器信號的碰撞概率方面，這些算法的缺陷在于將碰撞的結果簡單歸結為讀取失敗，但該假設已被后期的一些實驗結果證明并不嚴謹。文獻[2]基于近期的實驗結果，認為讀寫器間即使產生碰撞也只會降低各自的信噪比，識別半徑相應減少但一般不會減至零，繼而提出了讀寫器間干擾的統計模型，以及與讀寫器數量、功率、信道數有關的信噪比表達式。但該文獻認為各讀寫器功率相等，且位置呈均勻分布，這對實際應用來說只是一種理想假設。文獻[3-5]對多讀寫器的干擾模型進行了研究，分析了讀寫器在干擾環境下的讀寫距離，給出了路徑損耗因子、信噪比和噪聲功率等參數對干擾模型的影響大小。文獻[6]提出了一種分布式功率分配方案，該方案根據識別距離的期望值，通過檢測信噪比不斷更新發射功率。文獻[7]提出通過檢測接收信號強度的方法實時調整發射功率。算法收到標簽返回的信號后，先根據其 RSSI(Received Signal Strength Indication)值估計出讀寫器和標簽間的距離，然后根據所估計的距離將發射功率調整到合適的數值。文獻[8]根據檢測到的信噪比，采用具有回退功能的功率控制算法調整發射功率。與文獻[6]相比，該算法通過引入回退功能，有效避免了因各讀寫器貪婪增大功率導致的功率“死鎖”(各個讀寫器功率已達到最大值，但仍在試圖增大功率以致陷入死鎖)的情況。上述功率控制算法雖然在一定程度上起到了抑制讀寫器間干擾的作用，但本質上都屬于啟發式算法，難以實現多讀寫器識別性能的全局優化和公平性。

本文分析了在讀寫器位置隨機分布條件下如何分配功率以最大程度抑制讀寫器間干擾的問題，首先提出了信噪比估計式，并對估計式的性能進行了評估；根據RFID系統的應用需求，將讀寫器功率分配定義為自適應加權公平問題，并從理論上證明了該問題可以等價為求解指定效用函數的加權優化問題；為使算法在實際應用中更易于實現，設計了分布式功率更新算法，并對其收斂性進行了證明。

2 多讀寫器應用系統模型

以文獻[2]的讀寫器干擾模型為基礎，本文研究的多讀寫器系統應用場景如圖1所示，在半徑為D的區域內隨機分布若干個讀寫器，每個讀寫器功率均可調，且作如下假設和條件設定：

圖1 多讀寫器干擾模型

(1)讀寫器間距離d大于最小距離 rmin,rmin的設定以保證讀寫器識別范圍不發生重疊為原則，避免標簽端讀寫器碰撞的情形發生。

(2)路徑損耗與dγ成比例，其中γ設為2.5。

(3)讀寫器干擾為非相干的加性干擾，即多讀寫器對于某位置的干擾等同于單個讀寫器干擾的疊加。

(4)讀寫器具有兩個狀態：活動狀態和非活動狀態，處于活動狀態的概率為，讀寫器只有處于活動狀態時才會產生干擾。

(5)讀寫器采用跳頻通信模式，每次所用信道可在50個信道中隨機選擇。

(6)每個讀寫器的標稱讀寫半徑均為 Rnom，通過調節發射功率，實際讀寫半徑可以大于或小于Rnom。

讀寫器周期性發出查詢命令，識別處于標稱識別半徑內(如圖 1虛線所示)的標簽。當工作區域內讀寫器數量增加，干擾程度加大時，實際可識別半徑 Rreal將低于標稱值，可通過合理調節每個讀寫器的發射功率抑制讀寫半徑的下降。

3 誤包率與信噪比估計

3.1 誤包率估計

在功率控制算法設計中，設備接收端的信噪比是十分重要的參數，功控算法一般要根據檢測到的信噪比和其它參數進行計算和控制。獲取信噪比除了硬件測量的方式，也可通過接收數據誤包率間接得出，而且，當設備不具備信噪比檢測功能時采用這種方法更為實用，因為不用額外增加檢測硬件。

讀寫器與標簽間通信采用 TDMA幀時隙方式，每一幀被劃分為若干個時隙，讀寫器通過幀頭發出查詢命令后，每個標簽任意選擇一個時隙發送數據，每個時隙有 3種可能狀態：空閑(無標簽)、成功(僅一個標簽)和碰撞(兩個或以上標簽)[912]-。設當前幀長(即時隙數量)為L，檢測到空閑時隙、成功時隙和碰撞時隙的個數分別為1X,2X,3X。由于噪聲和干擾的存在，數據包即使未發生碰撞也可能出現接收錯誤，導致一些成功時隙轉化成碰撞時隙(無法正確解碼，等同于多標簽碰撞的情況)，將處于該時隙的數據包稱為錯誤包。設a為錯誤包個數，則真正的成功時隙和碰撞時隙的個數應為和。對于每一幀，不同類型的時隙個數組成向量，對應的期望值組成向量，其中和可根據文獻[13-15]由式(1)-式(3)給出：

式中n為標簽數量。實際中無法獲得n和a的真實值，但n和a越接近真實值，觀測向量和期望向量E[X']間的相似程度就越高。根據模式識別理論，可以用歐式距離的方法衡量兩個向量的相似程度，即尋找使X'與E[X']的歐式距離最小的n和a作為估計值：

定義 1 已知錯誤包個數a，設誤包率真值為pe，定義誤包率估計子為

下面分析該估計子的統計特性。

定理 1 令sp表示時隙為成功狀態的概率，設各成功時隙誤包與否相互獨立，則按式(5)定義的誤包率估計式為無偏估計。

證明

因此，式(5)定義的估計式無偏。 證畢

3.2 信噪比計算

標簽信號采用 ASK調制，讀寫器接收端誤比特率為

4 功率分配算法

4.1 問題建模

本文研究在多讀寫器環境下如何通過調節各自的功率以保證各讀寫器性能(讀寫半徑或接收信噪比)均能保持在標稱值附近的問題。提出自適應加權功率分配算法，基本思想是在比例公平算法的基礎上，增加自適應權重因子，當某讀寫器性能趨向低于標稱值時，其權重值自動增大，引導資源更多地分配給該讀寫器。以文獻[16]中比例公平問題定義為基礎，將本文的問題建模為自適應比例公平問題。

定義 2 向量*x稱為自適應比例公平解，如果其為可行解并且對于任意向量x，則式(10)成立

4.2 問題求解

可以將定義2的問題轉化為最優化問題以方便求解?？紤]式(11)的最優化問題：

其中。

證明 先證充分性。令*x為問題式(11)的解，通過計算可得到

由式(14)和式(15)可知問題式(11)的漢森矩陣負定，因此目標函數式(11)是嚴格凸函數，存在唯一的最優解。設λ為待定系數，令

問題式(11)最優解*x的Karush-Kuhn-Tucker(KKT)條件為

4.3 分布式功控算法

用讀寫器信噪比取代問題式(11)中的自變量x，可得到讀寫器功率控制問題的最終形式：

問題式(21)對于向量P是非凸問題，一般來說求解較為困難。本文采用分布式算法簡化運算，其基本思想是將問題式(21)的全局求解問題轉化為分布式的局部優化問題，每個讀寫器利用式(21)只更新自己的功率值。為了減輕信道負荷，每個讀寫器采用第3節中的方法，周期性地估計當前的信噪比并與標稱值比較，只有當信噪比低于標稱值時才向外發送功率更新請求及自己的功率值，啟動更新過程。以下是分布式算法的具體步驟(不失一般性，設算法運行在讀寫器s上)：

(1)初始化。將發射功率sP調整為預設值(默認設置在標稱值附近)，啟動讀寫器工作；

(2)標簽識別和時隙狀態采集。發出標簽識別命令 query，在標簽響應幀中收集空閑、成功和碰撞的時隙個數，用式(9)計算和更新信噪比的估計值；

(3)功率控制。根據信噪比的大小選擇相應的控制策略：

上述分布式算法涉及到兩個問題：一是算法是否收斂，二是如果收斂，其收斂點是否為問題式(21)的局部最優解。下面圍繞這兩個問題展開討論。

不失一般性，考慮讀寫器s的局部優化問題。

定理 3 對于讀寫器s，問題式(22)是凸優化問題。

證明 對于讀寫器s，將式(22)重寫為

證畢

每個讀寫器通過求解式(22)的局部目標函數更新自己的功率值，相應地，式(21)的全局目標函數的值也隨之變化。令 ()L t為t時刻式(21)的值，則有：

定理 4 (1)分布式更新算法收斂，即存在*L:；(2)設算法在處取得，則,都不會被更新，且為問題式(21)的KKT點。

證明

5 仿真結果

將本文方案與3個方案進行對比，分別是文獻[2]中基于均勻分布假設的固定功率分配方案，文獻[16]中的比例公平功率分配方案，以及文獻[8]中的功率可回退控制方案 BKPC(BacKoff Power Control)，在比例公平功率分配方案中采用與式(21)類似的形式，并使用相同的效用函數，只是令恒為1。仿真參數按第2節中相應數據設置。

首先將最小信噪比作為衡量算法公平性的指標。從圖2可看出隨著用戶數的增加，讀寫器間距在不斷縮小，相互之間干擾也隨之加大，最小信噪比隨著用戶數的增加有降低的趨勢。均勻分布假設下的功率固定分配算法根據工作區域大小和讀寫器密度參數，功率分配的公平性較差，最小信噪比最低。功率可回退控制方案根據信噪比調節輸出功率，性能要好于固定分配方案。比例公平算法考慮了功率分配的公平性，最小信噪比要大于均勻分配算法和功率可回退控制方案，但采用該算法當讀寫器密度很大時，仍會發生個別讀寫器信噪比遠小于標準信噪比的情況。本文提出的自適應加權算法基于比例公平算法，同時對處于高密度區域的讀寫器自動增加權重，使處于嚴重干擾區域下的讀寫器仍能盡量保證一定的信噪比，最小信噪比高于其它 3種算法。

讀寫器信噪比標準差是衡量算法公平性的另一個指標。如圖3所示，固定功率分配算法以讀寫器位置均勻分布為假設，不考慮干擾程度隨位置變化的因素，方差最大。功率可回退控制方案采用啟發式算法，通過回退僅能實現有限的全局優化能力，信噪比仍有較大的方差。比例公平算法將讀寫器位置信息考慮在內，公平性要比均勻分配和功率回退算法好。本文提出的自適應加權算法除了具有比例公平算法的優點外，還可以根據讀寫器所處環境狀況自動調節權重因子，最大程度地減小讀寫器密度分布差異對功率分配公平性的影響，方差要低于上述3種算法。

在多讀寫器應用場景中，各讀寫器由于所受干擾不同，其數據吞吐量也各不相同。圖4顯示了多讀寫器中平均吞吐量的數值和趨勢比較，通信數率設為100 bit/s。由圖可見，當讀寫器個數增加時，4種算法的最小吞吐量都逐漸減小，且當數量較多時趨于某固定數值，說明4種功率控制算法都只能在一定讀寫器數量下發揮作用。由圖可見，自適應加權算法性能始終優于其它3種算法，其吞吐量隨讀寫器數量增多而下降的速度也最為緩慢。

圖5顯示了本文提出的分布式算法收斂性能，給出了分布式算法求得的局部最優解與全局最優解的相對誤差，并與等比例分配和BKPC算法的收斂性做了比較。從圖中可以看出，隨著迭代次數的增加，自適應加權算法的迭代值穩定地收斂，且與全局最優解的相對誤差逐漸減小，當迭代次數大于150時，相對誤差可控制在3%以內，說明該分布式算法具有良好的收斂性能，且盡管求出的是局部最優解，但滿足一定的迭代次數后非常接近全局最優解。等比例分配由于算法流程與自適應加權相同，因此具有相近的收斂特性。BKPC算法基于啟發式調整策略，在迭代過程中迭代值波動幅度較大，收斂的速度最慢，當迭代次數大于200時才能穩定地使誤差控制在3%以內。

圖6比較了算法在時間復雜度方面的性能，其中BKPC，等比例分配，自適應分配方案中更新周期設為0.1 s, BKPC中的回退周期設為0.1~0.5 s。由圖中可以看出，由于等比例分配和自適應分配方案的收斂迭代次數小于BKPC算法，達到收斂值消耗的時間也明顯少于BKPC。

以上比較了固定場景的算法性能，下面考察移動環境下，即區域內讀寫器數量和位置發生變化時的性能。圖7所示為讀寫器位置和數量每隔30 s變化一次，其中位置做隨機變化，數量變化的方式做如下設定：(1)0~29 s內有 40個讀寫器共存；(2)30~59 s內新加入 20個讀寫器，共有 60個；(3)60~89 s內又加入 20個讀寫器，共有 80個；(4)90 ~120 s內又加入20個讀寫器，共有100個；(5)120 ~150 s內20個讀寫器離開，總數恢復到80個。將固定算法分配方案中讀寫器數量參數設為 70個(因圖7平均數量約為70)，BKPC，等比例分配，自適應分配方案中更新周期設為0.1 s, BKPC中的回退周期設為0.1~0.5 s。由圖6可看出，當讀寫器由于移動而使區域內數量改變時，自適應功率分配算法可以很快收斂到最優值(9 s以內)，而且最小吞吐量始終高于其它3種算法，說明算法在移動場景下具有較好的適應能力。

圖2 4種方法的最小信噪比

圖3 4種方法的信噪比標準方差

圖4 4種方法的平均吞吐量比較

圖5 3種方法的分布式算法收斂性能

圖6 3種算法的時間復雜度比較

圖7 4種功控算法的實時性能

6 結束語

讀寫器間干擾是多讀寫器應用場景中面臨的主要問題。本文提出的自適應權重功率分配算法對低于標稱信噪比的讀寫器自動增加權重因子，使處于不同位置，所受干擾程度不同的讀寫器識別質量均能盡量接近標稱值，滿足RFID系統在應用中的實際需求，提出的分布式實現方法進一步提高了算法的實用性。仿真表明，算法在公平性和收斂性方面均表現出良好的性能，是解決RFID讀寫器干擾問題的有效方法。

[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.