RFID標簽沖突分離的最大后驗概率聚類

郭佳雯，吳海鋒，2，桂妮霞，吳曉剛，曾 玉，2，陳躍斌

（1.云南民族大學電氣信息工程學院，昆明 650500；2.云南省高校智能傳感網絡及信息系統科技創新團隊，昆明 650500）

引 言

無線射頻識別（Radio frequency identification，RFID）技術興起于20世紀80年代，目前已成為“物物互通”的物聯網核心技術之一。由于RFID采用無線射頻通信，數據交換無需物體間接觸和人工參與，因此在物聯網信息采集層發揮了重要作用。

物聯網中，當RFID閱讀器同時識別多個附有標簽的物品時，各標簽信號在共享信道中難免發生沖突。標簽沖突一般在介質接入控制（Media access control，MAC）層［1?4］中解決，其基本原理為：標簽和閱讀器隨機通信，若發生沖突則再隨機選擇時間重發，直到發送成功。然而，該方式在標簽過多時，重發次數增多，通信效率不高。沖突信號實質為各標簽信號的疊加，對沖突信號分離后可被成功解碼。此時，沖突信號不會被視作無效信號，因此可降低重發次數，從而提高通信效率。

在傳統的分離方法中，無監督聚類［5?8］是一種常用方法，由聚類結果對沖突信號進行判決即可完成分離，其主要步驟則是確定聚類中心［9］。K均值［10］是應用較為廣泛的無監督聚類算法，該算法通過不斷迭代獲得聚類中心。為獲得準確的聚類中心，K均值通常需較多的迭代次數，當樣本數量較大時，該算法的運行時間較長，且其還需預知聚類數才能有較好的聚類效果。為減少運算時間，可采用一維投影圖法［11］進行聚類，將原二維平面聚類投影至實軸或虛軸上，計算沖突信號采樣點落在實軸或虛軸區間上的點數，通過尋找點數的局部最大值確定聚類中心坐標。相比K均值，一維投影圖法可顯著降低算法復雜度，但由于信號簇分布隨機，因此該方法的穩定性不高。例如，當多個信號簇中心的某一軸的坐標比較接近時，該軸方向上多個局部最大值會退化為單個值。

本文提出一種蒙特卡羅最大后驗概率（Monte Carlo?maximum posteriori probability，MC_MAP）聚類方法來完成沖突信號分離。首先，將沖突信號的采樣點映射至一個具有若干網格的二維平面中。然后，計算落在各網格中采樣點數。最后，利用窗口法計算點數的局部最大值，該值對應的網格坐標即是聚類中心點。與上述兩種傳統算法不同，本文算法無需預知聚類數和不斷迭代，算法復雜度較低。二維平面窗口法可防止一維投影法局部最大值退化引起的算法穩定性不高的問題，繼而實現較準確的信號分離。實驗中，分別采用仿真和軟件無線電的FM 0碼［12］信號來測試本文方法的分離性能，并對分離后信號用匹配濾波器和相位跳變［13］進行解碼。實驗結果表明，本文算法的誤碼率、分離效率能達到與K均值近似的性能，但運行時間可大幅減少。另外，在某些特定的信號衰減系數下，本文算法聚類準確度優于一維投影圖算法，可達到較好的分離效果。

1 研究背景

當多個RFID標簽發送信號，對于同一閱讀器，將接收到多個標簽信號的疊加。通常，標簽信號為單極性碼，則經同相正交（Inphase quadrature，IQ）解調后，其采樣點映射到復平面上會出現M=2N個簇［14］，即聚類的類別數，其中N為沖突標簽數。圖1（a）給出了兩個標簽的沖突信號，圖1（b）為沖突信號映射至復平面。由該簇中心點構成的集合可表示為H=｛0，h1，h2，h1+h2｝［11］，其中h1、h2分別為兩個標簽的衰減復系數。經聚類后，任何一個采樣點均可根據式（1）中的中心點分離成兩個標簽信號采樣點構成的矢量，分離結果構成的集合表示為D=｛[0，0]，[1，0]，[0，1]，[1，1]｝，其中D和H的每一元素構成［15］一一映射關系，表示為

圖1 兩個標簽沖突信號示意圖Fig.1 Schematic diagrams of conflict signal be?tween two tags

式中：d m（m=1，2，…，4∈H）分別為元素[0，0]，[1，0]，[0，1]和[1，1]；δm（m=1，2，…，4∈H）分別為0，h1，h2和h1+h2。

上述分離過程中，核心步驟是聚類，即尋找各簇中心點。由于信道衰減系數h1和h2未知，因此上述聚類是無監督聚類，可采用K均值實現。K均值首先需要預知聚類數，選取與聚類數相等的一些隨機點作為初始聚類中心［16］后，計算每個數據點與初始聚類中心的距離，再將這些數據歸類至與其距離最近的類，由歸類的點重新獲得新的聚類中心［16］，然后計算新聚類中心下的距離值，重復迭代，使得計算的距離值逐漸減小直至收斂，則算法結束。近年來，對初始中心的選擇和預先確定確切聚類數有一些相關研究實驗結果表明所提方法的有效性［17］，并對迭代次數作出改進，其實驗結果表明在不降低聚類效果的前提下［18］，迭代次數有所降低。為進一步減少復雜度，在RFID沖突信號的分離中，目前，還可采用一維投影圖法［11］來尋找聚類中心坐標，不僅聚類效果更好，且計算復雜度更低［19?20］。將沖突信號映射至二維復平面后，在實軸和虛軸上劃分若干等距離區間，計算沖突信號采樣點在實或虛軸上的投影落在各區間的點數，各點數的局部最大值所對應區間位置即是中心點坐標，如圖2所示。

圖2 一維實軸和虛軸方向投影示意圖Fig.2 One?dimensional projections on real axis and imaginary axis

2 問題提出

在K均值算法中，調整一次聚類中心需迭代一次，準確的聚類中心與迭代次數相關，較多的迭代次數可保證較準確的中心點，但計算復雜度會隨之增加，該計算復雜度O可表示為

式中：s為數據樣本的數目為調整數據樣本與聚類中心距離的復雜度；x a、x c分別為數據樣本點和聚類中心點的位置，其與維度有關，例如，當投影到一維平面時，其為標量，l為迭代的次數。另外，較多的數據樣本點數也會增加迭代次數，延長計算時間。在RFID沖突分離中，若采用復雜度較高的聚類算法會增加分離時間，從而降低了閱讀器與標簽的通信效率。

一維投影法在一維坐標軸上尋找峰值，其優點是無需迭代，因此計算復雜度可大幅下降。然而，沖突信號的聚類中心分布是隨機的，該方法在某些分布情況下并不適用。圖3給出了一個例子，圓圈中兩個簇的位置在其中一個投影方向上較為接近，因此在該方向的投影上形成了峰值重疊，最終只能得到3個局部最大值。

圖3 一維投影法聚類點缺失情況示意圖Fig.3 Missing clustering points by one?dimensional pro?jection method

3 算 法

3.1 系統框圖和模型

圖4給出RFID沖突信號分離和解碼的系統框圖。當一個閱讀器的電磁場范圍內存在多個標簽時，閱讀器采用隨機多址方式與標簽通信，如ALOHA方法［21］，即標簽隨機選擇時隙與閱讀器通信，當一個時隙內有兩個或兩個以上的標簽發射信號則發生沖突。此時，沖突信號是多個標簽信號的疊加信號，采用聚類方法對其分離。對該疊加信號進行IQ解調，然后映射至二維復平面，經聚類后得到聚類中心，再由聚類中心進行分離，分離的信號經解碼后即可得到標簽ID。

圖4 系統框圖Fig.4 System block diagram

假定在一個時隙內有N個標簽發送信號，則閱讀器接收的將是這些信號的疊加，經IQ解調后得到的信號y(t)可表示為

式中：L為載波泄露［22］；hn為第n個標簽信號的復衰落系數，該衰落系數在很短的一個通信時間內可視為平坦性衰落的線性時不變信道［23］；為第n個標簽信號；sn，k∈{0，1}為二進制數序列；K為序列長度；g(t)為矩形脈沖波形，當0≤t

3.2 MC_MAP聚類

MC_MAP聚類過程如圖5所示，先將解調后的沖突信號采樣點映射至一個二維復平面中，該平面被劃分為若干個正方形網格，然后統計落在每個網格中的點數，根據統計的點數畫出柱狀圖，各局部峰值就可視為每個簇的聚類中心點。

圖5 算法聚類示意圖Fig.5 Clustering process

設yi=y(iΔt)，i=1，2，…，I為沖突信號y(t)采樣后的I個采樣點，其中Δt為采樣周期，將yi投射至一具有J個正方形網格的復平面上。令p(j|y i∈Cm)為采樣點yi屬于第m個簇時落在第j個網格的概率，其中Cm表示第m簇點的集合，那么第m個聚類中心點所在網格的位置j?m可通過最大后驗概率估計得到，表示為

該式表明，若屬于第m簇的采樣點落在第個網格的概率最大，那么該網格就為第m簇中心所在網格。

為求解（4），可采用蒙特卡羅方法［24］。對式（4）中的后驗概率有

式中：為第m簇的點落在第j個網格中的數目，|·|為集合勢。原后驗概率可以用某簇的采樣點落在網格內的數目來表示，若I足夠大。將式（5）代入式（4）中，最后的蒙特卡羅最大后驗概率估計可以表示為

因此，求解式（5）只需在二維平面上找到網格內采樣點數的峰值。設cj表示第j個網格的中心，則將峰值對應網格的中心點cj?m近似作為第m簇的聚類中心點。

3.3 信號分離

得到聚類中心點后，應確定中心點對應于式（1）集合H的何元素，以此完成分解。例如，若對應0，則屬于該類的采樣點y i分解為［0，0］；若對應元素h1+h2，則y i分解為［1，1］。將確定兩個沖突標簽中4個聚類中心，m=1，2，…，4與集合H的各元素的對應關系。

標簽在發射信號前會出現一段靜默期［25］，此時閱讀器接收的信號僅含有載波泄露L，因此該時刻的信號幅值應與集合H的0元素的幅值相等。據此，與L最近的聚類中心將對應元素0。另外，在EPC C1 Gen2標準中，每個標簽在發射RN16之前均有一段前綴信號［12］，由于每個標簽的前綴信號均相同，因此對于兩個標簽的沖突情況，在該段時間內的兩個聚類中心將對應元素0和h1+h2。由于對應0元素的聚類中心已經確定，因此剩下的聚類中心將為h1+h2，如圖6所示。最后，對于兩個沖突標簽，剩余的兩個聚類中心將分別對應于元素h1和h2，或h2和h1，如圖6所示。由于此時的沖突標簽只有兩個，以上兩種對應的情形所得到的分離結果只會導致標簽的分離順序不同，并不改變分離結果，因此任選一種對應關系即可。

圖6 確定中心點對應關系圖Fig.6 Determination of correspondencediagram of the center point

確定對應關系后，通過計算距離對采樣點yi判決以確定其對應何類，表示為

式中為通過判決所估計的類別。然后，由式（1）可對采樣點yi進行分離，表示為

信號分離后，本文中采用FM 0編碼［26］方式對標簽信號進行編碼，解碼采用匹配濾波器和傳統的相位跳變，得到標簽ID。算法步驟如下。

輸入：

沖突信號數據采樣點［yi］［i=1，2，…，I］

輸出：

聚類分離矢量［d m|yi］

已知條件：

正方形網格［j］的中心坐標［cj］［j=1，2，…，J］

步驟：

（1）由式（2～5）得到聚類中心點坐標[cjm]；

（2）由式（6）判決確定其類［δm］；

（3）由式（7）得到分離信號［d m|yi］。

4 實驗設置

實驗中，采用動態幀時隙ALOHA［21］和物理層分離聯合解決標簽沖突問題，由于動態幀時隙ALOHA中，幀長將近似設置為標簽數目，因此平均一個沖突時隙中，沖突標簽為2.33［27］，大部分沖突時隙內的標簽為2～3個。據此，本文算法主要解決一個沖突時隙中存在兩個沖突標簽的分類情形，此時，聚類簇的數目為4，當沖突標簽大于2時將視為無法分離。

4.1 數據來源

RFID系統參數設置參照EPC C1 Gen2標準［12］，數據采用模擬數據和實測數據。仿真實驗中，沖突信號由式（3）得到，為兩個RFID標簽的基帶信號與高斯白噪聲的疊加，主要參數設置如表1所示。不同的信道衰落系數會產生不同的沖突信號簇類圖，從而影響聚類結果，因此表2給出了兩組衰落系數，其映射至復平面的信號簇如圖7所示。信道衰落系數為組1時，信號簇如圖7（a），各簇中心在實軸或虛軸上均未有重合現象。信道衰落系數為組2時，信號簇如圖7（b），此時有兩個簇中心在實軸方向相近。

表1 仿真數據參數設置表Table 1 Simulation data par ameter setting

表2 信道系數衰落設置Table 2 Channel coefficient fading setting

圖7 兩組信道系數產生的信號簇Fig.7 Signal clusters generated by two sets of channel coefficients

實測數據由USRP軟件無線電產生，依據EPC C1 Gen2標準構建超高頻RFID系統，軟件采用GNU Radio實現，詳細參數參見表3，代碼下載地址為https：//github.com/nkargas/Gen2?UHF?RFID?Reader［28］。

表3 USRP系統設置Table 3 USRP system setting

4.2 實驗算法

為評判本文算法性能，實驗對蒙特卡羅最大后驗概率法、K均值和一維投影圖法進行性能對比，3種算法分別用MC_MAP、K?means和One?Pro來表示。另外，由于劃分的網格大小對算法的性能指標有影響，因此實驗中對比了4組大小網格結果。以上算法參數設置詳見表4。表4中4組網格大小數據為實測數據實驗網格大小的參數設置。由于仿真數據樣本取值范圍受信噪比影響不斷變化，因此表里固定了網格的數量。A、B、C、D點為取實部和虛部的最大值和最小值兩兩組合得到。確定初始中心點后使之不斷迭代調整，直至中心點收斂，因此不限制迭代次數。

表4 各算法描述Table 4 Description of each algorithm

4.3 性能指標

實驗中，采用如下指標對算法的性能進行對比。誤碼率re定義為解碼有誤的碼元數Ne與標簽總碼元數Nt的比值，表示為

式中分離效率ηs定義為成功解碼標簽個數ns與總標簽個數nt之比，表示為

式中只有當標簽一次發送的所有碼元均被成功解碼才視為該次標簽被成功解碼。吞吐量γ定義為平均一個幀中成功解碼［15］的標簽數Ls與該幀長Lt的比值，可表示為

實際聚類中心點與期望中心點的誤差值ε用來衡量各算法的準確度，計算第m簇中心點第w次的實驗結果與第m簇期望中心點cm的誤差，可表示為

式中W為算法重復次數。

5 實驗結果與分析

5.1 仿真數據

圖8 K均值聚類初始中心點選取圖Fig.8 Initial center selection of K?means clustering

當信噪比取值為-10～30 d B時，圖9～14給出了在不同信道系數下3種算法的誤碼率曲線圖、分離效率曲線圖以及吞吐量曲線圖來驗證各算法的性能。另外，為了說明各算法的準確度和復雜度，還給出了在第1組信道系數下各算法計算得出的聚類中心點坐標與期望中心點坐標的誤差和各算法計算中心點所需的平均運行時間。

圖9給出了第1組信道系數下各算法的誤碼率，從圖9中可以看出，MC_MAP算法的誤碼率低于One?Pro算法，但高于K?means算法。圖10為第2組信道系數下各算法的誤碼率曲線，在信道系數第2組中，實軸方向有兩簇信號位置相近，信號簇分布示意圖見圖7（b），One?Pro算法在該情況下實軸方向無法計算出完整的聚類中心點，在虛軸方向得到的實驗結果曲線圖與第1組時類似，誤碼率仍高于本文算法。MC_MAP算法與K?means算法受到信道系數的影響誤碼率都有升高，但是MC_MAP算法受信道系數影響程度高于K?means算法4 dB，此時MC_MAP算法的抗衰落性能強于K?means算法。

圖9 第1組信道系數下各算法誤碼率Fig.9 Bit error rates of the three algorithms under the first group of channel coefficients

圖10 第2組信道系數下各算法誤碼率Fig.10 Bit error rates of the three algorithms under the second group of channel coefficients

圖11，12給出了兩組信道系數下的分離效率。從圖11，12可得，在高信噪比時3種算法的分離效率都能達到100%。圖12中，受到信道系數的影響，信噪比在-8～8 d B時，3種算法的分離效率都較低，且分離效率達到100%的速度也落后于第1組。然而，MC_MAP算法曲線可以保持上升趨勢，并沒有因信道系數的影響與K?means算法和One?Pro算法曲線在分離效率上升過程中發生類似波動。

圖11 第1組信道系數下各算法分離效率Fig.11 Separation efficiencies of the three algo?rithms under the first group of channel coef?ficients

圖12 第2組信道系數下各算法分離效率Fig.12 Separation efficiencies of the three algo?rithms under the second group of channel co?efficients

圖13，14給出了將各算法嵌入到ALOHA隨機多址所得到的吞吐量，其中在ALOHA中幀長和標簽數均設為128，當標簽發生沖突時則執行沖突分離解碼算法。此外，圖13，14中還給出了未采用分離型沖突分解的純ALOHA系統吞吐量，其吞吐量接近理論值0.367［21］。由圖13，14中顯示，當信噪比逐漸增大時，各分離型沖突分解算法的吞吐量均大于純ALOHA系統吞吐量［15］。即使在兩組不同信道系數的影響下，系統吞吐量也大于純ALOHA吞吐量，且MC_MAP算法吞吐量同樣高于One?Pro算法，但低于K?means算法。與分離效率曲線圖類似，在信道系數的影響下，曲線仍然可以保持上升趨勢。

圖13 第1組信道系數下各算法的吞吐量Fig.13 Throughputs of each algorithms under the first group of channel coefficients

圖14 第2組信道系數下各算法的吞吐量Fig.14 Throughputs of each algorithm under the sec?ond group of channel coefficients

圖15給出了在第1組信道系數下各算法計算得出的各簇中心點與期望中心點的誤差，該誤差值可反映算法的聚類準確度。從圖15中可以看出，MC_MAP算法的誤差跟隨信噪比的增加逐漸接近于零，準確度在高信噪比時比較高。K?means算法的準確度在低信噪比下優于MC_MAP算法，但在高信噪比時二者相似。One?Pro算法由于只是一維坐標，誤差值起點有起伏，22 dB后才逐漸趨于零，算法準確度較低。綜合各算法四簇誤差來說，MC_MAP算法的誤差范圍波動是最小的，可得到較準確的聚類準確度。

圖15 各算法計算出的各中心點與期望中心點的誤差Fig.15 Errors between the center point calculated by the three algorithms and the expected center point

表5給出了同一信噪比下各算法計算1次中心坐標點所需的平均運行時間，從表5中可以看出，One?Pro算法平均運行時間在三者中最短，MC_MAP算法比K?means算法平均運行時間少1 ms。因此在相同信噪比下，MC_MAP算法的時間復雜度高于One?Pro算法，但低于K?means算法。

表5 各算法運行時間Table 5 Running time of each algorithm ms

5.2 實測數據

本部分的實測數據由USRP平臺產生，圖16給出了當閱讀器與標簽通信時截取一段RN16作為沖突信號，其信號幅值為計算實部和虛部構成復數的模［15］。由于實測數據中信道系數未知，因此實驗結果中未給出各算法實際中心點與期望值中心點的誤差。圖17給出了實測數據下本文算法在不同網格大小下的性能指標，運行時間T f定義為各算法計算一次聚類中心點平均運行時間以衡量算法的復雜度。從圖17中可以看出，網格越大，算法平均運行時間越少，但算法的準確度會降低，誤碼率也會隨之增大，最終影響系統吞吐量。需要注意的是，當網格為0.02×0.02，步長為3個方格時，此時網格過大，MC_MAP算法無法找到正確聚類中心點。綜合各個性能指標來看，網格為0.01×0.01，步長為兩個方格時，MC_MAP算法計算得出聚類中心點為最佳，此時，該算法可使系統吞吐量達到0.55，相比達到相同解碼性能的K?means算法，性能指標見表6，本文算法運行時間節約了1 ms。One?Pro算法雖運行時間最短，但聚類準確性低，吞吐量只有0.366，接近于純ALOHA系統吞吐量理論值。

圖16 雙向通信下閱讀器捕獲的波形Fig.16 Waveform captured by reader in bidi?rectional communication

圖17 實測數據下MC_MAP算法不同網格大小的性能Fig.17 Performance of MC_MAP algorithm with different mesh sizes based on measured data

表6 實測數據下各算法的性能指標Table 6 Perfor mance indexes of the two algorithms under the measured data

6 結束語

針對RFID標簽沖突問題，本文研究了聚類對沖突標簽分離和解碼的影響，提出了MC_MAP聚類方法。在仿真實驗中，設置了兩組不同的信道系數，其中一組信道系數所得到的聚類中心在實軸或虛軸方向有投影重疊。實驗結果表明，無論何組信道系數，本文算法均有較準確的聚類準確度，相反，一維投影算法在有重疊的一組信道系數中無法得到所有聚類中心。K?means算法也能計算出準確的聚類中心點，并且在低信噪比時就能達到較好的聚類性能，但是該算法復雜度較高，運行時間較長。此外，本文算法雖然在高信噪比下才能達到與K?means算法相近的聚類性能，但算法的時間復雜度低于K?means算法，這點從實測數據實驗結果中能得到反映。因為所用的實測數據信噪比較高，所以本文算法達到了與K?means算法相似聚類性能，但運行時間遠低于K?means算法，最終可使系統吞吐量到達0.55。另外，網格大小對本文算法的性能指標也有所影響，適當的網格大小可提高算法的準確度，減少算法運行時間。

本文算法雖在低信噪比下聚類性能有所減弱，但實驗結果表明，信噪比在12 dB以后，本文算法的適用性和時間復雜度將是兩種傳統算法的折衷，因此在信噪比較高情形下，本文MC_MAP算法可成為標簽沖突中聚類分離的候選方案。另外，在實測數據中把從USRP平臺所采集的數據送至MATLAB軟件中進行處理，以此評判各算法性能，更完整的工作應是將算法直接嵌入至USRP平臺，完成測試，這將在未來中進一步完善此工作。