基于自適應蝙蝠算法的室內RFID 定位算法

謝良波，李宇洋，王勇，周牧，聶偉

（重慶郵電大學通信與信息工程學院，重慶 400065）

0 引言

隨著物聯網技術的迅猛發展，實時獲取人員及重要物品位置的需求日益增大。在現有的射頻識別（RFID,radio frequency identification）系統中，實現快速高精度定位是一項巨大的挑戰。目前，室內RFID 定位方法主要包括基于接收信號強度指示（RSSI,received signal strength indication）[1]、基于到達角度（AoA,angle of arrival）[2-3]、基于到達時間（ToA,time of arrival）[4]和基于載波相位[5-6]的定位方法。

基于RSSI 的定位方法主要是利用電磁波在室內環境下的傳輸損耗模型進行測距完成定位。文獻[7]提出的LANDMARC 定位算法采用有源標簽，對比目標標簽與參考標簽的RSSI，采用加權算法完成定位受障礙物影響較大，定位精度不高。文獻[8]在LANDMARC 的基礎上提出了VIRE（virtual reference）算法，通過引入大量虛擬標簽來增加標簽密度，進而提升定位精度，其是在LANDMARC 基礎上改進的較為成功的算法，在降低成本的基礎上提升了定位精度，但是定位精度仍然較低。另一個較成功的改進算法是SpotON[9]，其結合有源標簽，使用聚合函數計算標簽的信號強度，通過傳輸損耗模型計算距離，結合幾何方法實現三維定位，但是系統較復雜，計算量大。以上算法定位精度較低，主要是由于RSSI 受室內環境影響較大，很難實現高精度定位。

基于載波相位的定位算法以前主要應用于衛星定位系統中，由于其易于解算、噪聲容錯高等特點，近年來被引入室內定位。文獻[10]將跳頻與擴展卡爾曼濾波（EKF,extended Kalman filter）算法相結合，實現了高精度快速定位，但其天線為定向天線，輻射范圍有限。文獻[11]通過移動天線構建合成孔徑雷達，實現多點相位信息的收集，大大提升了定位精度。以上方法雖然實現了高精度定位，但計算時間相對較長。文獻[12]將相位與RSSI 相結合，利用RSSI 做粗估計來約束搜索范圍，再利用相位全息圖進一步實現精準定位，但基于全息圖的定位方式計算量大，耗時較長。文獻[13]利用稀疏標簽陣列對信號進行角度估計，結合多個角度實現標簽定位，但標簽陣列之間存在耦合問題，具有一定缺陷。

近年來，許多工作將室內定位與優化算法相結合，大大減少了計算復雜度，縮短了定位時間。文獻[14]將粒子群算法與AoA 相結合，在提升定位精度的同時大大縮短了定位耗時。文獻[15]在合成孔徑雷達的基礎上使用粒子群算法對目標進行搜索，彌補了合成孔徑雷達計算復雜度大的問題，大大縮短了定位時間。文獻[16]將2 個標簽的信號強度與重疊式年輪定位算法相結合，增加了搜索區域，提升了定位精度。文獻[17]通過蝙蝠算法（BA,bat algorithm）優化讀寫器部署位置，將讀寫器部署問題類比于平面坐標點的優化問題，提升了定位的準確性。文獻[18]將模糊聚類與貓群算法相結合，減少了特征匹配的復雜度，實現了穩定快速的區域化位置搜索。以上研究表明，傳統優化算法能夠有效提升定位性能，但迭代時間長，容易陷入局部最優，定位性能仍有待提升。

本文針對傳統定位算法時間復雜度高及傳統優化算法容易陷入局部最優等問題，提出了基于自適應蝙蝠算法（ABA,adaptive bat algorithm）的室內RFID 定位算法，主要研究工作如下。

1)本文將定位問題轉化為優化問題，融合MUSIC（multiple signal classification）測向與聚類測距的原理建立評估函數，結合自適應蝙蝠算法對定位區域內位置進行評估搜索，摒棄了傳統幾何解算的定位思路，最終實現快速厘米級定位。

2)相較于其他優化算法，蝙蝠算法具有收斂速度快、沒有較多參數調整的優點，但容易陷入局部最優，針對這一問題，本文提出一種自適應蝙蝠算法。通過引入2 個自適應權重約束蝙蝠搜索范圍，增強了算法的全局搜索能力，同時也提升了算法收斂性。

3)使用帳篷（Tent）反向學習增加初始種群的多樣性，提升算法初始搜索速度，設置自適應終止條件，在保證定位精度的同時縮短算法耗時。實驗結果表明，與基于中國剩余定理（CRT,Chinese remainder theorem）的傳統定位算法相比，本文算法的實時性提升了12 倍。

1 定位系統結構

1.1 定位平臺組成

定位系統由讀寫器、發射機、接收機、交換機、定位服務器以及標簽組成，結構如圖1 所示。讀寫器用于激活標簽，與標簽建立通信；發射機發射連續跳頻載波信號，標簽利用反向散射特性，將自身調制信息加到載波信號上；接收機對標簽信號進行接收解調；交換機負責定位服務器與定位系統相關設備間的數據交互；定位服務器控制發射機產生跳頻信息，同時從接收機解調的信息中按照標簽的通信協議提取出標簽信號，通過標簽信號計算出接收信號的相位，最終結合ABA 完成定位。

圖1 定位系統結構

1.2 定位算法流程

定位算法流程如圖2 所示。根據定位平臺收集的I/Q 兩路信息，從跳頻信息中提取每個頻率的相位。

圖2 定位算法流程

接收信號的相位信息包含設備誤差和多徑誤差，即

其中，d為標簽到接收機的鏈路距離，l為發射機到標簽的鏈路距離，?e為設備和天線引入的固有誤差，?m為環境造成的多徑誤差。設備誤差通過待測點與參考點的相位相減消除，多徑誤差采用多徑抑制算法進行處理[19]。

利用誤差減小之后的相位建立距離誤差函數與角度誤差函數，將2 個函數代入ABA 中對每次迭代的位置進行評估，找到評估誤差最小的坐標，該坐標即最終的定位結果。

2 位置評估函數建立

根據采集到的相位信息建立位置評估函數，用于評估搜索位置。評估函數的輸入為待評估的位置，由角度誤差函數與距離誤差函數組成，即

其中，P(x,y)是角度誤差函數，表示搜索位置相對于接收天線陣角度與真實位置相對于天線陣角度的誤差；D(x,y)是距離誤差函數，表示搜索位置到接收天線的距離與真實位置到接收天線的距離的誤差。

2.1 角度誤差函數

角度誤差函數是基于MUSIC算法原理建立的。由于信源與天線的距離在數個波長以上，到達天線的信號可以看作遠場信號，天線接收到的信號可以看作平面波，如圖3 所示。

圖3 天線接收到的信號

其中，ni(t)為噪聲信號；ki為信號的方向，表示為

其中，ω0為信號的中心頻率，c為光速。入射信號向量表示為

天線i接收信號的相位為

其中，mod(A,B)表示A對B取余，di表示標簽到天線i的鏈路距離，l表示發射天線到標簽的距離。根據接收信號的相位，信號的方向向量可以表示為

根據式(5)構建信號的協方差矩陣為

其中，RS為信號相關矩陣，σ2為噪聲功率，I為單位矩陣。根據方向矩陣求解噪聲子空間對應的特征向量vi（i∈[1,k]），即

利用特征向量vi組成噪聲子空間U。根據采集到的相位提取出信號的噪聲子空間之后，用其對傳入的評估位置進行角度評估，由于傳入的為位置坐標，構建評估位置到接收天線的方向向量G為

其中，D1i代表評估位置到天線1 的距離與評估位置到天線i的距離之差，可以表示為

其中，(x,y)是評估位置的坐標，(xi,yi)是天線i的坐標。根據信號提取的噪聲子空間和評估位置構建角度誤差函數為

由于構建的信號向量是一個1×N的矩陣，提取的噪聲子空間是M×N的矩陣，因此式(12)計算結果為一個數值。如果評估位置與真實位置處在以接收機為端點的射線上，由于信號空間與噪聲子空間正交，P(x,y)將為0，但是測試中往往存在誤差，因此在每次迭代中，尋找其最小值作為結果。

2.2 距離誤差函數

接收信號相位的范圍為[–π,π]，單根天線接收時，根據相位與距離的關系可得

其中，Nj為頻率j下的整周數，?j為頻率j下接收信號的相位，λj為頻率j對應的波長。由于式(13)是一個欠定方程，直接求解方程組整周數將會得到無數個解，不能直接計算整周數得到鏈路距離，因此本文根據多頻率多天線下傳入位置對應的相位與接收信號相位的差值進行聚類，搜索出差值最小的位置。由于評估函數的輸入是蝙蝠位置，當前蝙蝠位置對應的鏈路距離與標簽的真實鏈路距離的差值可表示為

其中，ej為代表第j個頻率下相位之間的差值。將其擴充到多根天線，提升測距的準確性，結合式(15)建立距離誤差函數為

其中，n為天線數目，m為頻率數目，?i,j為天線i在頻率j下的測量相位，為頻率j下發射天線到評估位置再到天線i的相位，di為標簽與天線i的鏈路距離。當蝙蝠位置坐標與實際位置坐標相同時，距離誤差函數輸出為0。但是，在實際運算過程中，由于誤差的存在不能搜索到真實位置，因此在搜索過程中將誤差最小值對應的評估位置作為最終結果。

結合式(12)與式(16)，組成式(2)對評估位置進行評估，得到該位置的評估值，完成對評估位置的評估，評估函數算法流程如算法1 所示。算法1中將角度誤差函數擴展到了多頻率，同時使用3δ準則對奇異值進行了剔除。

3 ABA 定位算法

傳統的蝙蝠算法通過模擬蝙蝠搜索獵物的方式，在尋找獵物的過程中，每個蝙蝠會發射出不同的聲波頻率、響度和脈沖率，每次飛行都會更新這些信息。在蝙蝠算法實現中，雖然其在搜索最優位置時會具有較快的收斂速度，但是蝙蝠的飛行速度更新方式、位置更新方式和跳出局部最優的方式都會受到隨機值的影響，使搜索過程很容易陷入局部最優，且定位精度較差[20]。本文針對蝙蝠算法易陷入局部最優和定位精度較差等問題，提出了基于Tent 反向學習的自適應蝙蝠算法，降低其陷入局部最優的概率，提升搜索精度。

3.1 Tent 反向學習初始化種群

在搜索過程中，蝙蝠初始位置的多樣性能夠大幅提升搜索的速度與精度。傳統的初始化種群的算法分為隨機算法和確定性算法，隨機算法依賴于初始隨機種子，初始化后的種群可能分布不均，蝙蝠位置的多樣性較差，導致搜索時間增加，搜索精度下降，而確定性算法在種群規模不滿足最低要求時，存在與隨機算法同樣的問題。為了增強蝙蝠種群的多樣性，本文提出了基于Tent 映射和反向學習的種群初始化策略，先使用Tent 映射初始化種群，之后使用反向學習方法對已初始化的種群進行更新，對Tent映射后的種群和反向學習后的種群進行合并選優。Tent 映射表示為[21]

初始化的蝙蝠位置為

其中，locmin和locmax分別為搜索范圍的下界和上界。得到Tent 映射的初始化種群之后，對其進行反向學習[22]，得到

將Tent 映射后的種群和反向學習后的種群作為初始化種群對初始種群各個蝙蝠進行評估，找到最優蝙蝠和最佳評估值。設置種群數為100，隨機位置與Tent 反向學習后的位置的對比如圖4所示。

圖4 中，小圓圈表示生成的蝙蝠位置，大圓圈表示對重疊區域進行突出顯示。可見，隨機產生的種群有較多重疊，而本文算法沒有重疊區域且種群分布較均勻、種群多樣性較豐富。

圖4 隨機位置與Tent 反向學習后的位置的對比

3.2 基于自適應權重的位置搜索

初始化種群后，開始對目標進行搜索。為了降低蝙蝠陷入局部最優的概率，提升搜索速度，本文舍棄了蝙蝠速度這一因素，引入2 個自適應權重（Q1i和Q2i）來更新蝙蝠位置，即

其中，abs(?)表示絕對值函數，Fi表示第i個蝙蝠的評估值，Fbest表示當前的最優評估值。當前蝙蝠位置的評估值越接近最優評估值時，則Q1i越大，Q2i越小，用這2 個自適應權重對蝙蝠位置進行更新，即

其中，tem 為隨機位置；Loci為第i個蝙蝠當前的位置坐標；α為一個固定值，代表搜索范圍；rand為[0,1]的隨機值；tem 為以當前迭代位置為圓心的范圍α內隨機尋找一個位置，再通過自適應權重Q1i與Q2i更新下一次位置；Locbest為當前搜索過程中的最優位置。每次更新位置后，判斷其是否越界，如果越界，則將就近的邊界位置作為更新的位置。位置更新后，對更新后的位置進行評估，即

其中，FI(loc)表示對位置使用評估函數進行評估。如果此次更新后的位置的評估值較Fi更大，則需要對此次迭代位置按照式(23)再次進行更新。

其中，g是一個定值，代表蝙蝠隨機飛行范圍的大小。如果Fnew

同時，如果Fnew

通過不斷迭代更新蝙蝠最優位置，完成對目標位置的搜索，最終完成定位。

3.3 算法優化

在蝙蝠位置迭代的過程中，初始的蝙蝠數量和迭代次數是已設定好的，但是在大量測試中發現，由于算法收斂性較強，找到最優位置后的迭代中，最優位置都不會改變或者位置變化很小；同時在算法搜索過程后期，隨著搜索范圍減小，過多的蝙蝠數目只會增加算法耗時。

為解決此問題，本文提出了迭代提前停止和動態蝙蝠數目更新的方法。假設蝙蝠數目和迭代次數都為W，在后面的迭代中，保存第i次迭代的最優位置 Locbest，形成最優位置的一個數組Locbest,i(i

其中，std(?)表示對值求標準差。式(26)表示在迭代次數大于τ次之后，計算其前20 次到當前次數的標準差，如果標準差小于μ，則迭代提前停止，跳出循環，其中，τ=25，μ=2。動態蝙蝠數目更新指在每次迭代完成后，蝙蝠數目動態縮減，即

其中，β是一個[0,1]內的定值，設定β=0.95。式(27)表示每次迭代對蝙蝠數目進行更新，在縮減到20 個蝙蝠數目時，停止更新。

上述方法大大縮短了定位時間，當蝙蝠數為150 個時，優化前定位一個目標的時間約為1.60 s，優化后定位一個目標的時間能夠縮短到約0.36 s。ABA 搜索目標位置流程如算法2 所示。

4 仿真分析與對比

4.1 仿真分析

為驗證算法的性能，本節首先對整個系統進行仿真。執行算法的計算機 CPU 為 AMD R7 4800HS，RAM 為16 GB，仿真搜索區域大小為4 m×4 m，以區域的中心為坐標原點建立直角坐標系，跳頻范圍為830～960 MHz，跳頻間隔為10 MHz，發射天線的坐標為(0,0)，3 根接收天線的坐標分別為(–10,–200)、(0,–200)和(10,–200)，單位為cm，信號添加信噪比為10 dB 的高斯白噪聲。每次定位迭代次數為100 次，蝙蝠數G分別為50、100、150、200、300 和500，探究不同蝙蝠數對定位的影響。進行500 次定位，每次定位目標在搜索范圍內隨機分布，不同蝙蝠數定位誤差的累積分布函數（CDF,cumulative distribution function）如圖5 所示。仿真統計結果如表1 所示。

圖5 不同蝙蝠數定位誤差的CDF

表1 仿真統計結果

從圖5 可以看出，不同蝙蝠數下，小于10 cm 的定位誤差的占比都能達到55%以上。其中，當蝙蝠數為50、100、150、200、300 和500 時，小于10 cm的定位誤差的占比分別為57.2%、75.8%、80.0%、82.2%、82.8%和85.4%。從表1 中可以看出，當蝙蝠數為50、100、150、200、300 和500 時，平均定位誤差分別為17.75 cm、10.23 cm、8.73 cm、8.23 cm、7.34 cm 和6.54 cm。根據平均耗時和平均定位誤差對蝙蝠數目進行選擇，當G=150 時，平均耗時為0.36 s，定位平均誤差為8.73 cm，具有較低的耗時，且定位精度有較大提升；而當G>150 時，耗時的增長和定位精度的增長收益明顯不成正比。所以在實測時設置定位的蝙蝠數為150。

4.2 算法收斂情況對比

為驗證本文ABA 的搜索速度以及局部搜索能力，在定位平臺仿真的基礎上使用不同的算法進行比較，對比了BA、粒子群優化（PSO,particle swarm optimization)算法[15]和方向性蝙蝠算法[23]（DBA,directional bat algorithm）的收斂情況，所有算法初始種群數都為150，不同算法的收斂情況如圖6 所示。

圖6 不同算法的收斂情況

由圖6 可以看出，4 種算法都可收斂。DBA、BA、PSO 與所提算法收斂時的定位誤差分別為24.06 cm、23.77 cm、5.44 cm 和1.19 cm。傳統蝙蝠算法雖然收斂速度很快，但是定位誤差較大；本文算法在保證較快的收斂速度下，定位誤差較小，具有較高的收斂速度以及定位精度。

5 實測分析

5.1 測試平臺

為驗證本文算法實測性能，搭建了如圖7 所示的測試場景，室內環境為典型的客廳環境，測試范圍為4 m×4 m，接收天線間距為10 cm，選用的跳頻范圍為830～960 MHz，跳頻頻率間隔為10 MHz，跳頻時間間隔為50 ms，標簽反射信號處理過程在GNU Radio 平臺上完成，實驗設備如表2 所示。

圖7 測試場景

表2 實驗設備

5.2 實測定位精度

由于噪聲和和評估函數原理的影響，不同坐標軸的定位精度可能會不同，本節對定位精度進行統計分析。不同坐標軸定位誤差的CDF 如圖8 所示。

圖8 不同坐標軸定位誤差的CDF

從圖8 可以看出，X軸誤差、Y軸誤差和定位誤差10 cm 以下的占比分別為91.3%、73.9%和73.9%。其中，X軸誤差、Y軸誤差和定位誤差的中位數分別為3.08 cm、6.77 cm 和7.74 cm。因此，X軸的定位精度優于Y軸定位精度。主要原因是評估函數是測距與測向相結合的，測距距離是鏈路距離，根據橢圓定位原理，在以發射天線和接收天線為焦點的橢圓上的點都滿足條件，發射天線與接收天線的坐標在Y軸上，形成的橢圓是Y軸上的橢圓，其長軸在Y軸上，短軸在X軸上，如果測向發生偏差，使定位坐標偏差，則Y軸誤差將大于X軸誤差。

5.3 不同算法比較

本節選取不同算法對定位精度進行分析。本節對適用于本文RFID系統的算法和適用于其他RFID系統的算法分別進行了比較。

不同算法定位誤差的CDF 如圖9 所示。DBA、PSO、CRT[19]、EKF[10]和ABA 的定位誤差中值分別為15.95 cm、22.46 cm、9.11 cm、9.35 cm 和7.74 cm。DBA、PSO、CRT、EKF 和ABA 的小于10 cm 的定位誤差占比分別為26.1%、43.5%、52.1%、52.4%和73.9%。因此，本文所提ABA 優于對比算法，可實現更高精度的室內定位。

圖9 不同算法定位誤差的CDF

將本文算法與適用于其他RFID 系統的算法進行對比，結果如表3 所示。與文獻[10]算法相比，本文算法使用天線為全向天線，體積更小，范圍更廣；與文獻[11]算法相比，本文算法天線不需要保持移動，且系統成本較低；與文獻[12]算法相比，本文算法天線不需要互成角度，且定位范圍更大；與文獻[13]算法相比，本文算法不需要定位目標貼附標簽陣列，可實現獨立目標定位。

表3 本文算法與適用于其他RFID 系統的算法對比

5.4 多目標定位分析

為驗證多目標情況下算法的性能，在定位區域內，標簽間隔25 cm 平行放置，并均勻移動測量標簽位置，多目標定位誤差的CDF 如圖10 所示。從圖10 可以看出，X軸誤差、Y軸誤差和定位誤差在10 cm 以下的占比分別為88%、84%和76%。其中，有一個標簽定位誤差較大，主要是因為測量相位與實際相位偏差過大，導致算法的定位結果與實際標簽位置差別過大。從圖10 中可以看出，本文算法在多目標定位時同樣具有較高準確性。

圖10 多目標定位誤差的CDF

5.5 實時性分析

為驗證本文算法的實時性，本節對本文算法、CRT、DBA、PSO 和EKF 進行了實時性對比分析，實時性比較如圖11 所示。從圖11 可以看出，本文算法、EKF、PSO、DBA 和CRT 的耗時分別為0.36 s、0.43 s、0.86 s、3.34 s 和4.35 s。本文算法相較于對比算法實時性更高，其中較CRT 實時性提升了12 倍。

圖11 實時性比較

6 結束語

本文提出了一種基于Tent 反向學習自適應蝙蝠算法的室內RFID 定位算法。首先，將采集的相位進行多徑抑制，在MUSIC 測向與聚類測距的基礎上建立評估函數；然后，將評估函數與自適應蝙蝠算法相結合，用于評估蝙蝠每次更新的位置；最后，通過不斷迭代搜索到目標位置完成定位。實驗結果表明，本文提出的自適應蝙蝠算法具有良好的室內定位效果。