基于約束總體最小二乘的泰勒級(jí)數(shù)定位算法

陸劍鋒 謝勝東

1(泰州職業(yè)技術(shù)學(xué)院信息技術(shù)學(xué)院 江蘇 泰州 225300)2(南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院 江蘇 南京 210044)

0 引 言

無線定位是指利用無線信號(hào)的物理參數(shù)估計(jì)目標(biāo)節(jié)點(diǎn)在某一坐標(biāo)系統(tǒng)中的位置，最初是為了滿足航海導(dǎo)航以及精確制導(dǎo)等方面要求，其典型代表為20世紀(jì)70年代的全球定位系統(tǒng)(GPS)。自1996年美國(guó)聯(lián)邦通信委員會(huì)要求無線蜂窩系統(tǒng)必須能夠?qū)Πl(fā)出緊急呼叫的移動(dòng)用戶實(shí)現(xiàn)準(zhǔn)確定位后，無線定位便引起了眾多學(xué)者的廣泛關(guān)注[1]。目前，無線定位除了應(yīng)用于蜂窩網(wǎng)絡(luò)中的緊急呼叫外，還可以用于智能交通、數(shù)字城市以及現(xiàn)代化農(nóng)業(yè)、醫(yī)療等領(lǐng)域中，以實(shí)現(xiàn)目標(biāo)跟蹤、資源調(diào)度和導(dǎo)航等為目的，因此具有廣泛的應(yīng)用范圍。

根據(jù)物理量的不同，現(xiàn)有定位算法可以分為基于信號(hào)強(qiáng)度(Received Signal Strength，RSS)的定位[2]、基于信號(hào)到達(dá)時(shí)間(Time of Arrival，TOA)的定位[3]、基于信號(hào)到達(dá)時(shí)間差(Time Difference of Arrival，TDOA)的定位[4]以及基于信號(hào)到達(dá)角度(Angle of Arrival，AOA)的定位[5]四種基本類型。由于RSS定位精度低、AOA實(shí)現(xiàn)復(fù)雜以及TOA需要目標(biāo)節(jié)點(diǎn)與源節(jié)點(diǎn)之間時(shí)間同步[6]，在無線定位系統(tǒng)中，現(xiàn)階段使用最為廣泛的就是TDOA算法。例如，在GSM和LTE系統(tǒng)中，均采用該類算法進(jìn)行位置估計(jì)。

目前關(guān)于如何提高TDOA算法定位精度的研究主要可以分為三大類：(1) 最小二乘類定位算法。這類算法基于目標(biāo)節(jié)點(diǎn)到達(dá)不同錨節(jié)點(diǎn)距離平方之差的誤差2-范數(shù)最小原則，將位置估計(jì)描述為一個(gè)空間的向量仿射變換問題，基于普通最小二乘(Least Square，LS)準(zhǔn)則，使用拉格朗日算子法[7]、廣義信任域法[8]或半正定規(guī)劃法[9]即可求得該準(zhǔn)則下的全局最優(yōu)解。然而，使用LS準(zhǔn)則求解原問題本身就是存在偏差[10]，因此，上述全局最優(yōu)解未必是原問題的全局最優(yōu)解。(2) 凸規(guī)劃類定位算法[11]。這類算法基于目標(biāo)節(jié)點(diǎn)到達(dá)不同錨節(jié)點(diǎn)距離之差的誤差2-范數(shù)最小原則，將估計(jì)量的最優(yōu)值表示成求解一個(gè)非凸非線性函數(shù)的最小值問題，進(jìn)而通過松弛技術(shù)，將原問題轉(zhuǎn)化成一個(gè)非線性凸函數(shù)最小化問題，以該問題的最優(yōu)解作為目標(biāo)節(jié)點(diǎn)坐標(biāo)的最優(yōu)估計(jì)值。然而，原問題與轉(zhuǎn)換后的問題之間并不等價(jià)，因此，轉(zhuǎn)換后問題的最優(yōu)值未必是原問題的最優(yōu)值。(3) 泰勒級(jí)數(shù)類定位算法[12]。與第二類算法的準(zhǔn)則相同，這類算法也是基于目標(biāo)節(jié)點(diǎn)到達(dá)不同錨節(jié)點(diǎn)距離之差的誤差2-范數(shù)最小原則，將估計(jì)量的最優(yōu)值描述成求解一個(gè)非線性最小二乘函數(shù)的最小值問題，進(jìn)而使用泰勒級(jí)數(shù)展開法，將到達(dá)時(shí)間差函數(shù)用某個(gè)初始坐標(biāo)點(diǎn)的一階泰勒級(jí)數(shù)近似，實(shí)現(xiàn)了非線性最小二乘函數(shù)到線性最小二乘函數(shù)的轉(zhuǎn)變。在獲得修正步長(zhǎng)的最小二乘解后，更新原初始坐標(biāo)點(diǎn)。如此不斷迭代，從而逐漸逼近真實(shí)坐標(biāo)點(diǎn)。由于忽略了泰勒級(jí)數(shù)的高次項(xiàng)，因此迭代解未必是原始非線性最小二乘問題的最優(yōu)解。很顯然，上述三類算法均無法獲得各自所對(duì)應(yīng)的原始問題的全局最優(yōu)解。

本文主要研究第三類，即泰勒級(jí)數(shù)類定位算法。對(duì)于該類算法，初始坐標(biāo)點(diǎn)的選擇是一個(gè)重要環(huán)節(jié)，它直接決定了此類算法的性能?，F(xiàn)有算法中，常見的初始點(diǎn)選擇方法主要包括最小二乘法[4]、最速下降法[13]、殘差加權(quán)法[14]以及二階錐松弛法[15]等。事實(shí)上，幾乎所有最小二乘類和凸規(guī)劃類定位算法所獲得的位置估計(jì)值均可以作為泰勒級(jí)數(shù)類算法的初始坐標(biāo)點(diǎn)，區(qū)別主要在于算法的收斂性、迭代次數(shù)以及估計(jì)精度的不同。當(dāng)初始坐標(biāo)點(diǎn)與實(shí)際位置值越接近時(shí)，算法的收斂性越能得到保障，迭代次數(shù)也將越少，定位精度也將越高。

1 定位模型

考慮到二維坐標(biāo)系統(tǒng)中的定位算法經(jīng)簡(jiǎn)單擴(kuò)展后便可適用于三維坐標(biāo)系統(tǒng)，因此本文以二維坐標(biāo)系統(tǒng)為研究環(huán)境。假設(shè)在二維坐標(biāo)系統(tǒng)中，存在某個(gè)位置未知的目標(biāo)節(jié)點(diǎn)，其坐標(biāo)記為(x,y)，同時(shí)還存在N個(gè)不在同一條直線上位置已知的普通錨節(jié)點(diǎn)，它們的坐標(biāo)分別記為(xi,yi),i=1,2，…,N，以及一個(gè)位于坐標(biāo)系統(tǒng)原點(diǎn)的參考錨節(jié)點(diǎn)。

我們可以使用時(shí)延估計(jì)法[16]獲得電磁波或聲波從目標(biāo)節(jié)點(diǎn)到達(dá)普通錨節(jié)點(diǎn)i與參考錨節(jié)點(diǎn)之間的時(shí)間差ti0，然后乘以它們的傳播速度，即可獲得目標(biāo)節(jié)點(diǎn)到達(dá)兩節(jié)點(diǎn)之間的距離差di0。由此可見，TDOA定位算法可以看成是基于距離差的定位算法。因此，在本文中，我們將以距離差來代替時(shí)間差。

目標(biāo)節(jié)點(diǎn)到達(dá)普通錨節(jié)點(diǎn)i與參考錨節(jié)點(diǎn)距離差的真實(shí)值fi0(x,y)可分別表示為：

(1)

i=1,2，…,N

由于我們事先并不知道目標(biāo)節(jié)點(diǎn)的坐標(biāo)值，因此不能通過式(1)來計(jì)算距離差，而只能通過測(cè)量得到距離差di0的值：

di0=fi0(x,y)+ni0i=1,2,…,N

(2)

式中：ni0為測(cè)量誤差，我們假設(shè)它們之間獨(dú)立同分布。

1.4.3 煙葉常規(guī)化學(xué)成分 分析烤后煙葉樣品的常規(guī)化學(xué)成分，包括總氮、煙堿、總糖、還原糖、鉀、氯，并計(jì)算糖堿比、氮堿比和鉀氯比。具體參照文獻(xiàn)[17]的方法進(jìn)行。

(3)

式(3)是求解一個(gè)非線性最小二乘函數(shù)的最小值問題，這類問題因存在多個(gè)極值點(diǎn)，故一般不存在或難以求得其全局最優(yōu)解，而只能通過某種優(yōu)化算法，如牛頓法、最速下降法等方法獲得它的局部最優(yōu)解。

2 定位算法

如果能夠求得式(3)的全局最優(yōu)解，那么該解即可作為節(jié)點(diǎn)的位置坐標(biāo)最優(yōu)估計(jì)值，但如前所述，函數(shù)的非凸性使其成為一件較為困難的事情，牛頓法、最速下降法等搜索算法只能獲得函數(shù)的局部最優(yōu)解。如果我們可以對(duì)非凸函數(shù)進(jìn)行線性近似，那么就能獲得近似后函數(shù)的全局最優(yōu)解，盡管其未必是原函數(shù)的全局最優(yōu)解，但其性能可能會(huì)優(yōu)于原函數(shù)的局部最優(yōu)解。一方面，泰勒級(jí)數(shù)分解使得這種線性近似成為可能，另一方面，CTLS算法利用了牛頓法獲得了SDR模型中的局部最優(yōu)解。因此，我們將這兩種方法結(jié)合，提出一種基于完全約束最小二乘的泰勒級(jí)數(shù)定位算法(CTLS-Taylor)，以期望能夠獲得更好的定位效果。CTLS-Taylor包含兩個(gè)方面的內(nèi)容：(1) 泰勒級(jí)數(shù)的線性近似原理；(2) 利用CTLS算法進(jìn)行目標(biāo)節(jié)點(diǎn)位置坐標(biāo)初始點(diǎn)的選擇。

2.1 泰勒級(jí)數(shù)線性近似原理

(4)

(5)

式(5)等價(jià)于求解如下線性方程式在普通最小二乘準(zhǔn)則下的最優(yōu)解：

AX=b

(6)

2.2 初始點(diǎn)的選擇

很顯然，初始點(diǎn)越接近式(3)的最優(yōu)解，則不僅能夠保證迭代過程的收斂，而且能夠減少迭代的次數(shù)，提高位置估計(jì)的速度。考慮到最小二乘類定位算法中的CTLS算法[10]能夠獲得較高的位置估計(jì)精度，本文采用CTLS算法來獲取目標(biāo)節(jié)點(diǎn)的初始位置。

基于目標(biāo)節(jié)點(diǎn)到達(dá)普通錨節(jié)點(diǎn)與參考錨節(jié)點(diǎn)的距離平方值之差的誤差平方和最小原則，目標(biāo)節(jié)點(diǎn)的坐標(biāo)可以通過下式進(jìn)行描述：

Aθ=b

(7)

對(duì)于式(7)，我們可以求得它在普通最小二乘準(zhǔn)則下的最優(yōu)值[7]。但該準(zhǔn)則是建立在矩陣A中所有元素均不存在誤差的基礎(chǔ)上，而事實(shí)上，A中最后一列的所有元素均為測(cè)量所得，必然存在著測(cè)量誤差，因此采用普通最小二乘準(zhǔn)則獲得的最優(yōu)值顯然是不準(zhǔn)確的。此時(shí)，可以采用總體最小二乘準(zhǔn)則[17]，它不僅考慮了向量b中的誤差，同樣考慮到了矩陣A中元素的誤差，其目的是在最小化所有誤差平方和的情況下，使得式(7)有唯一確定解。于是在該準(zhǔn)則下，式(7)的最優(yōu)值θ等價(jià)于式(8)的最優(yōu)解：

s.t.Aθ-b=Gn

(8)

式中：

利用牛頓迭代法，我們可以很容易地求得式(8)的一個(gè)局部最優(yōu)解θ，并將其中的x和y作為目標(biāo)節(jié)點(diǎn)位置坐標(biāo)的粗估計(jì)值。

2.3 CTLS-Taylor算法

這里，我們給出CTLS-Taylor算法的完整過程：

3 仿真分析

本文的仿真環(huán)境為MATLAB 7.0，仿真參數(shù)來自文獻(xiàn)[18]：在一個(gè)100 m×100 m的2維坐標(biāo)系統(tǒng)中，存在一個(gè)實(shí)際坐標(biāo)(42,12) m的目標(biāo)節(jié)點(diǎn)，同時(shí)存在9個(gè)普通錨節(jié)點(diǎn)，它們的坐標(biāo)依次為(16,42) m、(34,52) m、(58,30) m、(78,18) m、(66,48) m、(30,-12) m、(22,12) m、(57,-3) m、(12,-28)m，另外還存在一個(gè)參考錨節(jié)點(diǎn)，其坐標(biāo)為(0,0) m。TDOA的測(cè)量噪聲服從均值為0，方差為δ2的高斯分布。為了評(píng)價(jià)CTLS-Taylor算法的性能，將其與CTLS算法、QCLS算法以及QCLS-Taylor算法[4]進(jìn)行比較，并從定位誤差和泰勒級(jí)數(shù)迭代次數(shù)兩個(gè)角度進(jìn)行衡量。本文中定位誤差e的計(jì)算公式為：

(9)

式中：N為仿真次數(shù)。

圖1和圖2為普通錨節(jié)點(diǎn)數(shù)目分別為5個(gè)和9個(gè)時(shí)，不同算法的定位誤差。可以看出：(1) 隨著測(cè)量噪聲方差的增加以及普通錨節(jié)點(diǎn)數(shù)目的增多，泰勒級(jí)數(shù)類算法的定位誤差要優(yōu)于非泰勒級(jí)數(shù)類算法，這表明使用泰勒級(jí)數(shù)法有助于提高定位精度。(2) 本文的CTLS-Taylor算法與QCLS-Taylor算法的定位誤差幾乎相等，不受測(cè)量噪聲與普通錨節(jié)點(diǎn)數(shù)目的影響。這意味著單純從定位誤差的角度看，本文算法與QCLS-Taylor算法的性能相當(dāng)。(3) CTLS算法的定位誤差要優(yōu)于QCLS算法，這是因?yàn)镃TLS算法是基于總體最小二乘準(zhǔn)則，而QCLS算法是基于普通最小二乘準(zhǔn)則的原因。

圖1 普通錨節(jié)點(diǎn)數(shù)目5個(gè)的定位誤差

圖2 普通錨節(jié)點(diǎn)數(shù)目9個(gè)的定位誤差

圖3與圖4為普通錨節(jié)點(diǎn)數(shù)目分別為5個(gè)和9個(gè)時(shí)，兩種泰勒級(jí)數(shù)類算法所需要的迭代次數(shù)?？梢钥闯觯?1) 當(dāng)測(cè)量方差較低時(shí)，尤其是當(dāng)信噪比低于-1 dB時(shí)，CTLS-Taylor算法幾乎只要迭代一次即可，且與普通錨節(jié)點(diǎn)的數(shù)目無關(guān)，而QCLS-Taylor算法的平均迭代次數(shù)均大于1.5次，這與CTLS-Taylor算法的初始點(diǎn)更為接近真實(shí)坐標(biāo)點(diǎn)有關(guān)。(2) 當(dāng)測(cè)量方差逐漸增大時(shí)，兩個(gè)泰勒級(jí)數(shù)算法的迭代次數(shù)均出現(xiàn)不同程度的增加，但CTLS-Taylor算法的迭代次數(shù)始終小于QCLS-Taylor算法。

圖3 普通錨節(jié)點(diǎn)數(shù)目5個(gè)的迭代次數(shù)

圖4 普通錨節(jié)點(diǎn)數(shù)目9個(gè)的迭代次數(shù)

上述結(jié)果表明，盡管從定位誤差的角度看，CTLS-Taylor算法的性能與QCLS-Taylor算法相當(dāng)，但前者的迭代次數(shù)卻小于后者，也就意味著前者的定位速度優(yōu)于后者。

4 結(jié) 語

本文將泰勒級(jí)數(shù)法與CTLS算法相結(jié)合，提出了一種基于約束總體最小二乘的泰勒級(jí)數(shù)定位算法。該算法利用CTLS方法獲得目標(biāo)節(jié)點(diǎn)坐標(biāo)位置的粗估計(jì)值，并將該值作為泰勒級(jí)數(shù)展開法的初始點(diǎn)，通過迭代，從而獲得目標(biāo)節(jié)點(diǎn)位置坐標(biāo)的精估計(jì)值。仿真結(jié)果表明，CTLS-Taylor算法不僅能夠獲得與QCLS-Taylor算法相同的定位精度，而且迭代次數(shù)有了明顯減少；同時(shí)與CTLS算法相比，當(dāng)測(cè)量噪聲較高時(shí)，CTLS-Taylor算法的定位精度更高。