陳大偉　錢路雁 　陳詩軍　金玲飛　李俊強

摘要：隨著5G時代的到來，人們對更精確，拓展性更好的定位系統(tǒng)的需求開始變得越來越迫切。本文提出了一種改進的融合定位算法。本文提出了使用模擬退火最優(yōu)化算法對近距離情況下的Chan算法第一次初始值估計做了優(yōu)化，并融合多元Taylor算法，充分利用了定位目標之間的距離關(guān)系，使得定位精度得到提高。

關(guān)鍵詞：Chan算法;模擬退火算法;Taylor算法;室內(nèi)定位算法

中圖分類號：TP399? ? ? ? ?文獻標識碼： A

文章編號：1009-3044（2021）01-0011-05

Abstract： With the advent of 5G， the need for more accurate and scalable positioning systems is becoming more and more urgent. In this paper， we propose an improved fusion positioning algorithm. The simulated annealing optimization algorithm was used to optimize the first initial value estimation of the Chan algorithm in the case of close range， and the multivariable Taylor series expansion algorithm is integrated to make full use of the distance relationship between the positioning targets， so as to improve the positioning accuracy.

Key words： chan algorithm;simulated annealing algorithm;taylor algorithm;indoor location

1引言

隨著5G時代的來臨，以及信息技術(shù)軟硬件的急速發(fā)展，獲得更加精確、更加豐富的位置信息變得越來越容易。而且由于人們一天中大部分的時間都在室內(nèi)，精確的室內(nèi)位置信息對很多領(lǐng)域來說，其價值都是十分巨大的。由于位置信息的重要性，以及近年來對智能家居和類似掃地機器人這樣的需求，室內(nèi)定位領(lǐng)域的研究熱度一直居高不下[1-4]。室外雖然有了GPS提供的高精度LOS（視距）定位，但由于GPS有著一定的局限性，如精度低等等，很多新的室內(nèi)定位技術(shù)被發(fā)明了出來彌補GPS的缺陷，如： RFID（射頻）定位、WiFi定位、基于WiFi指紋庫的定位、藍牙定位、超聲波定位技術(shù)、超寬帶（Ultra Wideband）技術(shù)、可見光定位技術(shù)等等，它們分別于有著各自的優(yōu)點和缺陷[5-9]。

定位算法與最終定位的精確度密切相關(guān)。定位算法本質(zhì)上是在于如何利用現(xiàn)實測量值，根據(jù)具體模型，高效高精度的解決一個超定的非線性方程組，從而獲得較為精準的目標位置。定位基站接收的參數(shù)一般有RSSI（接收信號能量強度），AOA（信號到達的角度），TOA（信號到達的時間），TDOA（信號到達的時間差）。這四種方法各有特點。國內(nèi)外目前應(yīng)用最多的是TDOA以及TOA為基礎(chǔ)的定位算法。

Chan算法是TDOA定位算法的一種[10]。其優(yōu)勢在于當(dāng)測量誤差服從高斯分布時，該算法定位精確，并且算法復(fù)雜度不高。但由于對于實際環(huán)境中的測量值很多時候并不會服從標準的高斯分布，此時Chan算法的性能會有顯著的下降。

在傳統(tǒng)的定位算法中，Taylor展開法是解非線性方程組的最佳解法之一[11]，Taylor算法有著較高的求解精度和較快的迭代速度，這是其成為最常用的定位算法的原因。Taylor算法的缺點主要有兩點，其一是對初始值較敏感，迭代的初始值對Taylor算法的影響較大，第二是可能會出現(xiàn)不收斂的情況。解決方法一般是利用多種算法進行協(xié)同定位。先用一種算法得出定位初始值，再使用該初始值代入Taylor級數(shù)展開法得到精確解。近年來融合比較成功的是Chan算法與傳統(tǒng)Taylor算法的協(xié)同定位算法[12]。最近，基于多元變量的Taylor算法被提出[13]，將定位目標與定位目標之間的位置信息充分地利用起來。

由于Chan算法主要步驟是兩步最小二乘估計，當(dāng)目標距離各個基站距離較近時，第一次最小二乘估算也需要一個估計初始值，才能求解初始解估計矩陣。在實際生活中，如室內(nèi)定位場景，這樣的情況是很常見的。

本文的改進Chan算法思路是通過使用模擬退火算法，搜索優(yōu)質(zhì)的初始解，用來輔助Chan算法來處理目標距離基站距離較近時的初始值估計，并融合多元變量Taylor算法，并根據(jù)幾何位置關(guān)系，去除一些多余錯誤數(shù)據(jù)，進行精確定位。

2 Chan優(yōu)化算法

2.1 Chan算法

TOA/TDOA定位模型是非常常用的高精度定位模型之一，通過基站發(fā)射某種信號（通常是電磁波信號），接收信號時通過時延估計算法得到信號的到達時間或者到達時間差，再通過乘以信號的傳播速度獲得與目標之間的距離，若假設(shè)經(jīng)過時延估計后得到的實際測[ti，i=1，2，...，N]，則距離測量值為[δi=c?ti，i=1，2，...，N]，其中[c=299792458]m/s表示光速。

從而建立基站離目標的距離方程組就可以得到單目標的TOA定位模型，設(shè)[Ri]表示第[i]個定位基站與定位目標之間的距離測量值：

雖然[x0，y0，R0]不是相互獨立的，Chan算法的核心思想是采用的兩步加權(quán)最小二乘方法（WLS），先假設(shè)這兩個中間變量是相互獨立的，將非線性方程線性化，使用加權(quán)最小二乘獲得他們的估計值，求得該估計值后再考慮他們之間的相互關(guān)系，這樣就可以求解得到目標位置。于是，令

假設(shè)系統(tǒng)有著較高的信噪比，可以認為測量值為高斯數(shù)據(jù)，即他們服從近似的正態(tài)分布，由于噪聲向量[n]也服從近似的正態(tài)分布，則可以得到關(guān)于誤差的向量統(tǒng)計的關(guān)系為：

通過Chan算法可以看出，當(dāng)目標距離各個基站距離較近時，第一次估算也需要一個估計初始值，才能求解初始解估計矩陣。在實際生活中，如室內(nèi)定位場景，這樣的情況是很常見的。

2.2基于模擬退火算法改進Chan算法

本文提出了使用模擬退火算法，搜索優(yōu)質(zhì)的初始解，用來輔助Chan算法來處理目標距離基站距離較近時的初始值估計。

常見的最優(yōu)化方法有遺傳算法、模擬退火算法和爬山算法，使用模擬退火算法的原因是其局部搜索能力強，運行時間較短，但由于之后有Taylor算法來加強定位的精度，所以模擬退火算法是平衡和效率和精確的最佳選擇。

假設(shè)場所內(nèi)共有N個基站，M個待測目標，對于每個待測目標，模擬退火算法的目標函數(shù)設(shè)置為：

3 融合多元Taylor算法

雖然Chan算法在測量誤差服從高斯分布時，定位精確，并且算法復(fù)雜度不高，但現(xiàn)實情況下往往誤差不服從標準的高斯分布，此時Chan算法的精度會有顯著的下降，通常使用融合多種算法來實現(xiàn)，常見如Chan與Taylor算法的協(xié)同定位方法[12]。Taylor算法在信道條件較差時擁有較好的性能，并且由于其對初始值敏感，所以需要一個稍好的初始值作為算法的輸入，所以將Chan算法與Taylor算法融合是正確的選擇。近年來，多元Taylor算法被提出[13]，成功地將目標之間的位置信息利用起來，提高了Taylor算法的精度，所以本文提出了改進Chan算法與多元Taylor算法的融合算法。

3.1多元Taylor算法

設(shè)場所內(nèi)共有N個基站，M個待測目標。由于傳統(tǒng)的Taylor級數(shù)展開算法并沒有將待測目標之間的測量距離值考慮在內(nèi)，所以會損失一部分的有用信息，從而為導(dǎo)致定位的精度有所損失。

那么理論上[A，B]的距離測量值因為大圓半徑與小圓半徑之間，由于之前根據(jù)模擬退火的改進Chan算法得到了一個初始值，則代入初始值，計算各個基站距離該初始值的誤差，并計算累積分布函數(shù)，將90%誤差以上的誤差去除，既可以換來一部分的性能提升，并且可以篩除一部分數(shù)據(jù)。

3.2 Taylor算法對初始值的敏感性研究

在100m×100m的室內(nèi)均勻分布5個基站。假設(shè)TODA測量誤差服從均值為零方差的高斯分布N（0，1），然后在平面內(nèi)均勻的選擇10201個不同的初始值，考察其對Taylor算法收斂性的影響。

在圖2中，紅色區(qū)域表示該區(qū)域內(nèi)的初始值不收斂，可以簡單地看出若收斂值選取在基站包圍的凸多邊形區(qū)域內(nèi)，或者靠近真實值的位置，則Taylor算法收斂，否則則不一定收斂。

然后觀察初始值對收斂速度的影響，依然在100m×100m的室內(nèi)均勻分布5個基站，TODA測量誤差服從均值為零方差的高斯分布N（0，1），待測目標的真實坐標為（40，40）。設(shè)[δi]表示Taylor算法在第[i]次迭代后，估計位置與真實位置的絕對距離誤差。

從表1中可以看出，初始值越靠近真實值，則算法的收斂速度越快。

3.3 算法流程

4 仿真分析

在100m×100m的平面內(nèi)隨機放置20個未知位置的待測目標，5個已知位置的節(jié)點。假設(shè)距離測量誤差服從10m，方差為[δ2=1]的指數(shù)分布。

通過仿真分析可以看出，本文提出的算法在信道條件不夠好，并且基站較少但有著多個待測目標時有著更高的定位精度，現(xiàn)實場景中適用性廣泛。

5結(jié)語

由于人們一天中大部分的時間都是在室內(nèi)的，精確的室內(nèi)位置信息對很多領(lǐng)域來說，其價值十分巨大。不僅會給人們生活帶來很大的便利，讓人們再也不會害怕在大型室內(nèi)建筑里迷路，如：商場、醫(yī)院、體育館、博物館等;也會給火災(zāi)、地震等自然災(zāi)害中的救援人員帶來不可估計的價值;同時也會大大增強虛擬現(xiàn)實、增強現(xiàn)實、體感游戲等需要超高精度定位的娛樂設(shè)備的沉浸感。本文提出了使用模擬退火算法來優(yōu)化Chan算法在近距離的情況下第一次最小二乘估計初始值的選擇，并融合了多元Taylor算法，將目標之間的位置信息利用起來，完成高精度的定位方法。但是本算法的局限在假設(shè)測量誤差服從同一分布。未來可以從，若是每個定位基站的誤差參數(shù)不服從同一分布出發(fā)，研究如何從算法層面更進一步的提升該情況下的定位精度。

參考文獻：

[1] Porcino D，Hirt W.Ultra-wideband radio technology：potential and challenges ahead[J].IEEE Communications Magazine，2003，41（7）：66-74.

[2] 李珊，張春明，汪衛(wèi)國.5G商用起步，融合應(yīng)用蓬勃興起[J].中興通訊技術(shù)，2019，25（6）：2-7.

[3] 嚴斌峰，袁曉靜，胡博.5G技術(shù)發(fā)展與行業(yè)應(yīng)用探討[J].中興通訊技術(shù)，2019，25（6）：34-41.

[4] Miyazawa S，SongX，Xia T Q，etal.Integrating GPS trajectory and topics from Twitter stream for human mobility estimation[J].Frontiers of Computer Science，2019，13（3）：460-470.

[5] 趙銳，鐘榜，朱祖禮，等.室內(nèi)定位技術(shù)及應(yīng)用綜述[J].電子科技，2014，27（3）：154-157.

[6] 曹薊光，張健.發(fā)達國家寬帶戰(zhàn)略及我國與其發(fā)展差距分析[J].信息通信技術(shù)，2011，5（1）：18-23.

[7] 李俊.基于RFID的室內(nèi)定位系統(tǒng)的研究和設(shè)計[D].成都：電子科技大學(xué)，2009.

[8] 潘德宇.基于ZigBee的醫(yī)院室內(nèi)定位系統(tǒng)應(yīng)用框架研究與實現(xiàn)[D].上海：上海交通大學(xué)，2011.

[9] Scholtz R A， Weaver R， Homier E， et al. UWB radio deployment challenges[C]. IEEE International Symposium on PersonalIndoor and Mobile Radio Communications. London， UK， 2000： 620-625. doi： 10.1109/PIMRC.2000.881497.

[10] Chan Y T，Ho K C.A simple and efficient estimator for hyperbolic location[J].IEEE Transactions on Signal Processing，1994，42（8）：1905-1915.

[11] 李莉，鄧平，劉林.Taylor級數(shù)展開法定位及其性能分析[J].西南交通大學(xué)學(xué)報，2002，37（6）：684-688.

[12] 劉林，鄧平，范平志.基于Chan氏算法和Taylor級數(shù)展開法的協(xié)同定位方法[J].電子與信息學(xué)報，2004，26（1）：41-46.

[13] 李瑞雪，夏斌，袁文浩，等.基于多元變量Taylor級數(shù)展開模型的定位算法[J].計算機應(yīng)用研究，2016，33（6）：1853-1856，1881.

【通聯(lián)編輯：梁書】