基于改進(jìn)Chan算法和多元Taylor算法的室內(nèi)定位方法

陳大偉　錢路雁 　陳詩(shī)軍　金玲飛　李俊強(qiáng)

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

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

中圖分類號(hào)：TP399? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A

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

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

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

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

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

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

2 Chan優(yōu)化算法

2.1 Chan算法

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

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

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

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

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

2.2基于模擬退火算法改進(jìn)Chan算法

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

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

假設(shè)場(chǎng)所內(nèi)共有N個(gè)基站，M個(gè)待測(cè)目標(biāo)，對(duì)于每個(gè)待測(cè)目標(biāo)，模擬退火算法的目標(biāo)函數(shù)設(shè)置為：

3 融合多元Taylor算法

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

3.1多元Taylor算法

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

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

3.2 Taylor算法對(duì)初始值的敏感性研究

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

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

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

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

3.3 算法流程

4 仿真分析

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

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

5結(jié)語

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

參考文獻(xiàn)：

[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)國(guó).5G商用起步，融合應(yīng)用蓬勃興起[J].中興通訊技術(shù)，2019，25（6）：2-7.

[3] 嚴(yán)斌峰，袁曉靜，胡博.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ā)達(dá)國(guó)家寬帶戰(zhàn)略及我國(guó)與其發(fā)展差距分析[J].信息通信技術(shù)，2011，5（1）：18-23.

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

[8] 潘德宇.基于ZigBee的醫(yī)院室內(nèi)定位系統(tǒng)應(yīng)用框架研究與實(shí)現(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級(jí)數(shù)展開法定位及其性能分析[J].西南交通大學(xué)學(xué)報(bào)，2002，37（6）：684-688.

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

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

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