基于入侵雜草算法的水下目標(biāo)TDOA 定位方法*

林云航，張貞凱，江 峰

（江蘇科技大學(xué)電子信息學(xué)院，江蘇 鎮(zhèn)江 212003）

0 引言

水下無線傳感器網(wǎng)絡(luò)（Underwater Wireless Sensor Network，UWSN）是部署在水下一定數(shù)量的傳感器構(gòu)成的網(wǎng)絡(luò)，是當(dāng)今一個(gè)備受關(guān)注的研究熱點(diǎn)［1］；在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)位置信息的獲取與處理就變得尤為重要［2］；作為傳感器網(wǎng)絡(luò)的主要支撐技術(shù)，定位技術(shù)的重要性就顯現(xiàn)出來了。當(dāng)前主要有兩種定位方式：距離相關(guān)與距離無關(guān)［3］。距離相關(guān)的定位方法包括兩個(gè)步驟：測(cè)距與定位算法?；跍y(cè)距的方法一般有利用到達(dá)時(shí)間差（Time Difference of Arrival，TDOA）［4-6］和利用到達(dá)時(shí)間（Time of Arrival，TOA）［7-8］等，定位方法則包含三邊測(cè)量法和最小二乘法等。距離無關(guān)的定位方法也包含兩個(gè)步驟：估計(jì)距離與定位算法。主要使用的是Distance Vector-Hop（DV-HOP）［9-10］算法與質(zhì)心算法［11］。兩類方法各有優(yōu)缺點(diǎn)，可以根據(jù)條件來進(jìn)行選擇。

本文基于TDOA 來實(shí)現(xiàn)水下目標(biāo)的定位，文獻(xiàn)［12］提出了基于泰勒級(jí)數(shù)展開的TDOA 定位方法，泰勒算法需要一個(gè)與實(shí)際位置接近的初值才能夠?qū)崿F(xiàn)算法的收斂。文獻(xiàn)［13］針對(duì)定位問題提出了Chan 算法，該算法在測(cè)量誤差滿足高斯分布時(shí)能夠達(dá)到最好效果，但是實(shí)際誤差并不滿足高斯分布，導(dǎo)致定位效果性能顯著下降。文獻(xiàn)［14］提出了一種兩步加權(quán)最小二乘算法，先引入中間變量建立一組關(guān)于TDOA 的偽線性方程，通過第1 次加權(quán)最小二乘算法，求出中間變量和未知節(jié)點(diǎn)的粗略解，隨后利用中間變量與目標(biāo)之間的關(guān)系進(jìn)行第2 次加權(quán)最小二乘算法來進(jìn)一步提高精度。考慮到這種算法的計(jì)算量大、過程復(fù)雜，可以選擇利用優(yōu)化算法來提高求解的效率。

本文提出了一種基于入侵雜草優(yōu)化（Invasive Weeds Optimization，IWO）算法與加權(quán)最小二乘算法協(xié)同定位的方法，利用IWO 算法求出初值，從而可以得到中間變量；然后將初值與中間變量引入一個(gè)距離干擾參數(shù)，求得粗略解；再通過估計(jì)相關(guān)的誤差取得精確解。

1 算法原理

1.1 基于TDOA 的水下定位算法

TDOA 是通過測(cè)量未知節(jié)點(diǎn)到兩個(gè)已知坐標(biāo)傳感器之間的時(shí)間差來確定未知節(jié)點(diǎn)的位置。假設(shè)在一個(gè)三維空間中，有M 個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布，未知節(jié)點(diǎn)的坐標(biāo)為u=［x，y，z］T，第i 個(gè)傳感器節(jié)點(diǎn)的實(shí)際坐標(biāo)為si=［xi，yi，zi］T，則未知節(jié)點(diǎn)到傳感器節(jié)點(diǎn)的距離為：

將式（3）移項(xiàng)可得：R-Ri+R1=N，理論上，R-Ri+R1應(yīng)該是為零矩陣。但是由于噪聲的存在，它的值不會(huì)等于零，因此，R-Ri+R1的最優(yōu)解就是它的最小值。利用范數(shù)的形式來求取最小值，同時(shí)把范數(shù)平方，可以保證范數(shù)的值在0 的兩邊都可以收斂。所以未知節(jié)點(diǎn)的估計(jì)坐標(biāo)可以這樣來求：

式（4）如果采用解析法來求解的話，過程十分復(fù)雜，因此，在本文采用入侵雜草算法來求解未知節(jié)點(diǎn)的估計(jì)值。

圖1 是水下節(jié)點(diǎn)定位時(shí)示意圖，可以通過以上方法求出水下未知節(jié)點(diǎn)的估計(jì)坐標(biāo)。

圖1 水下節(jié)點(diǎn)示意圖

1.2 入侵雜草算法

入侵雜草算法［15］是在2006 年受雜草繁殖的啟發(fā)提出的一種優(yōu)化算法，通過效仿雜草繁殖時(shí)，種子在空間中擴(kuò)散、生長和繁殖的過程演變而來的。與其他算法相比較，該算法在種子擴(kuò)散的過程中滿足正態(tài)分布，每一株父代雜草均能繁衍出下一代種子。雜草的適應(yīng)度越強(qiáng)，就能繁衍出越多的子代雜草，在整個(gè)算法的過程中既可以保全雜草的多樣性，又可以使其具備一定的競(jìng)爭(zhēng)能力。該算法的基本流程是：

1）根據(jù)要解決的問題，對(duì)種群X=（X1，X2，…，Xpmin）進(jìn)行初始化，其中，確定初始種群數(shù)pmin，并設(shè)定最大種群數(shù)pmax。

2）計(jì)算每個(gè)雜草的適應(yīng)度值，種子的數(shù)量是由其父代雜草的適應(yīng)度數(shù)值所決定，它們之間呈一個(gè)線性關(guān)系。其線性關(guān)系如下所示：

式（5）中，weedt代表種子數(shù)量，f 代表雜草的適應(yīng)度，fmax與fmin則是最大與最小的適應(yīng)值，Smax與Smin分別為可產(chǎn)生的最大與最小種子數(shù)量。

3）種子依照正態(tài)分布的規(guī)律擴(kuò)散在父代雜草產(chǎn)生的周圍，通過公式可表示為：

式（6）中，σ 是標(biāo)準(zhǔn)差。根據(jù)迭代的過程，σ 一直在變化，其變化規(guī)律可以表現(xiàn)為：

式（7）中，σmin、σmax分別表示最終標(biāo)準(zhǔn)差與初始標(biāo)準(zhǔn)差的數(shù)值，itermax、iter 分別表示最大迭代次數(shù)與當(dāng)前迭代次數(shù)，β 代表非線性調(diào)節(jié)因子，一般將它設(shè)置為3。

4）若當(dāng)前的種群數(shù)量比最大種群數(shù)pmax還要大時(shí)，算法就會(huì)開啟競(jìng)爭(zhēng)機(jī)制，將所有的雜草按照適應(yīng)度的數(shù)值從大到小來進(jìn)行排序，將適應(yīng)度好的前pmax個(gè)雜草保留，其余雜草則淘汰，然后進(jìn)入下一次迭代。

5）判斷是否迭代次數(shù)是否大于最大迭代次數(shù)itermax。若是，那么結(jié)束循環(huán)輸出最優(yōu)解；若否，則返回2）繼續(xù)循環(huán)。

2 IWO 算法與加權(quán)最小二乘算法協(xié)同定位

本節(jié)中首先使用IWO 算法求出TDOA 定位的初值。式（4）使用解析法時(shí)計(jì)算量太過巨大，因此，選用IWO 算法來進(jìn)行求解。為了求解式（4），將適應(yīng)度函數(shù)設(shè)置為：式中，f 為雜草的適應(yīng)度函數(shù)，R-Ri+R1表示定位誤差。公式表示當(dāng)適應(yīng)度函數(shù)f 取得最優(yōu)值時(shí)，此時(shí)的坐標(biāo)就是未知節(jié)點(diǎn)的初值uiwo。

第1 階段：利用改進(jìn)的加權(quán)最小二乘算法和初值uiwo來求未知節(jié)點(diǎn)的粗略解。

將式（10）以加權(quán)最小二乘算法的偽線性模型來表示：

通過加權(quán)最小二乘算法，可得到第1 階段未知節(jié)點(diǎn)的粗略解：式中，W=（BQBT）-1，W 的值跟未知節(jié)點(diǎn)的坐標(biāo)有關(guān)；利用uiwo來確定中間變量r1和ri的數(shù)值并求出W的值。Q 為TDOA 測(cè)量值誤差的協(xié)方差矩陣。

第2 階段：得到了粗略解u*之后，要進(jìn)一步來細(xì)化它。設(shè)：

其中，Δu 是估計(jì)的誤差項(xiàng)。

將式（13）帶入到r1中，可得：r1=||u-s1||=||u*-Δu-s1||。當(dāng)估計(jì)誤差較小時(shí)，即||Δu||<<||u-s1||，r1進(jìn)行一階泰勒級(jí)數(shù)展開可變式為：

考慮所有的傳感器，上式可表示為：

式（17）的加權(quán)最小二乘解為：

其中，W=（BQBT）-1，可以利用第1 階段的粗略解求得。

在估計(jì)誤差求出來之后，便可以求出未知節(jié)點(diǎn)的精確解：

3 克拉美羅下界

為了驗(yàn)證所提算法的性能，對(duì)TDOA 定位的克拉美羅下界（Cramer-Rao Lower Bound，CRLB）進(jìn)行分析。

將誤差估計(jì)項(xiàng)Δu 表示為：

其中，δ 是估計(jì)誤差。

將式（13）和式（20）代入式（19），得到u^-u=-δ，可知最終解的期望偏差為-E（δ）。將式（17）進(jìn)行移項(xiàng)變?yōu)椋篽2=BN+AΔu，再將其代入到式（18）可以得到δ 的表達(dá)式：

其中，因?yàn)榫仃嘇 和N 均包含噪聲項(xiàng)，所以期望偏差-E（δ）比較困難。但是在噪聲小的條件下，A 中的測(cè)量值的噪聲可以忽略。

此時(shí)，式（21）表達(dá)成誤差項(xiàng)δ 與關(guān)于噪聲N的線性等式，由于N 服從零均值的高斯噪聲分布，從而-E（δ）=0，即E（u^-u）=0。因此，所提算法在噪聲小的情況下，可以求出未知節(jié)點(diǎn)坐標(biāo)的無偏估計(jì)值。

CRLB 是無偏估計(jì)量的估計(jì)方差的下限，即無偏估計(jì)量的方差只能逼近克拉美羅界，而不可能小于它。由文獻(xiàn)［14，16］可知：對(duì)于TDOA 定位而言，它的CRLB 矩陣可以寫成：

因此，TDOA 定位的克拉美羅下界可以表示為：

4 仿真結(jié)果及分析

本節(jié)中為了驗(yàn)證本方法在水下定位的效果，使用Matlab 平臺(tái)來對(duì)算法進(jìn)行仿真實(shí)驗(yàn)。假設(shè)在水下區(qū)域中布置一個(gè)傳感器網(wǎng)絡(luò)，總共5 個(gè)傳感器。第1個(gè)傳感器為參考傳感器，另外4 個(gè)是坐標(biāo)隨機(jī)的傳感器。實(shí)驗(yàn)過程是使用本方法，在不同坐標(biāo)的傳感器和標(biāo)準(zhǔn)差不同的噪聲下，求出未知節(jié)點(diǎn)的坐標(biāo)。假設(shè)TDOA 測(cè)量值誤差之間是相互獨(dú)立的，則測(cè)量值誤差的協(xié)方差矩陣為Q=delta2IM-1×M-1，其中，delta2是測(cè)量噪聲的方差，I 是對(duì)角線元素為1，其余元素為0.5 的矩陣，下標(biāo)表示它的維度。所有仿真均采用蒙特卡羅隨機(jī)實(shí)驗(yàn)，以均方誤差（MSE）、偏差（BIAS）和累積分布函數(shù)（CDF）為評(píng)價(jià)指標(biāo)，并求出在不同的噪聲中的理論最小方差克拉美羅下界（CRLB）。相同條件下所提算法與傳統(tǒng)的Chan 算法（圖注為TDOA-CHAN）、未進(jìn)行誤差估計(jì)的IWO 算法（圖注為TDOA-IWO）進(jìn)行比較。

MSE 與BIAS 的計(jì)算公式如下所示：

其中，L 是蒙特卡羅實(shí)驗(yàn)次數(shù)，沒有特定的說明，L=100。

累積分布函數(shù)是在某一個(gè)門限誤差下，算法定位誤差低于門限誤差的次數(shù)占仿真總次數(shù)的比例。CDF 在圖中上升的趨勢(shì)越快，表示低于門限誤差的次數(shù)越多。

入侵雜草算法初始化參數(shù)設(shè)置為：初始種群數(shù)pmin=5，最大雜草個(gè)數(shù)pmax=10，最大迭代次數(shù)itermax=350，初始標(biāo)準(zhǔn)差σmax=30，最終標(biāo)準(zhǔn)差σmin=0.005，最大種子數(shù)Smax=20 和最小種子數(shù)Smin=0。

仿真1 5 個(gè)傳感器坐標(biāo)中，參考傳感器坐標(biāo)為［70，30，15］T，4 個(gè)隨機(jī)的傳感器坐標(biāo)分別為［30，0，50］T，［0，40，80］T，［-30，0，50］T和［0，-40，20］T，未知節(jié)點(diǎn)的真實(shí)坐標(biāo)是［-150，100，30］T，單位均為m。

圖2 為3 種算法以及CRLB 之間的均方誤差比較圖，圖3 為3 種算法之間的偏差比較圖，研究的都是算法精確度。仿真結(jié)果所示：在噪聲較小時(shí)，算法之間的性能還是比較接近的。但在噪聲變大之后，所提算法的定位均方誤差與偏差要明顯小于其余兩種算法，即精度會(huì)更準(zhǔn)確一些。

圖2 均方誤差比較結(jié)果

圖3 偏差比較結(jié)果

圖4 是3 種算法在噪聲標(biāo)準(zhǔn)差為3 時(shí)的累積分布函數(shù)，橫坐標(biāo)表示定位誤差平方的對(duì)數(shù)形式。仿真結(jié)果表明，在相同的噪聲中，所提算法的上升趨勢(shì)要明顯優(yōu)于其余兩種，也就是所提算法的性能要好于其余兩種。

圖4 累積分布函數(shù)對(duì)比結(jié)果

仿真2 5 個(gè)傳感器坐標(biāo)中，參考傳感器坐標(biāo)為［70，30，15］T，4 個(gè)隨機(jī)的傳感器坐標(biāo)分別為［130，0，50］T，［0，400，180］T，［-130，0，500］T和［0，-400，80］T，未知節(jié)點(diǎn)的真實(shí)坐標(biāo)是［-150，100，30］T，單位均為m。

圖5 為3 種算法以及CRLB 之間的均方誤差比較圖，圖6 為3 種算法之間的偏差比較圖，研究的都是算法精確度。仿真結(jié)果所示：所提算法的均方誤差與偏差在相同條件之下都更小，說明所提算法精度更高。

圖5 均方誤差比較結(jié)果

圖6 偏差比較結(jié)果

圖7 是3 種算法在噪聲標(biāo)準(zhǔn)差為3 時(shí)的累積分布函數(shù)。仿真結(jié)果表明，在相同的噪聲中，所提算法的誤差低于門限誤差的次數(shù)要少于其余兩種算法，可以看出，所提算法的性能優(yōu)于另外兩種算法。

圖7 累積分布函數(shù)對(duì)比結(jié)果

仿真1 和仿真2 的結(jié)果均表明，所提算法要比其余兩種算法定位更為精確，得出的估計(jì)值更接近于實(shí)際位置。從圖中可以看出，TDOA-IWO 的精度要優(yōu)于TDOA-CHAN，這是因?yàn)镃han 算法在進(jìn)行最小二乘算法時(shí)會(huì)引入誤差的二次項(xiàng)，而TDOA-IWO 是直接對(duì)定位誤差的范數(shù)來進(jìn)行搜索。當(dāng)誤差較小時(shí)，兩算法的性能差別不大，但是誤差變大時(shí)，TDOA-CHAN 二次項(xiàng)不能忽略，而TDOA-IWO 沒有受到二次項(xiàng)誤差的影響，因此，TDOA-IWO 定位效果好于TDOA-CHAN。所提算法是在TDOA-IWO 的基礎(chǔ)上來進(jìn)行誤差項(xiàng)估計(jì)，即所提算法的解會(huì)比TDOA-IWO 的解精度更高，也可以看出，噪聲較大時(shí)，所提算法相比于其余兩種算法要更加接近CRLB，所提算法能更好地適應(yīng)噪聲較大的環(huán)境。

5 結(jié)論

針對(duì)水下定位的要求，本文提出的基于入侵雜草算法的水下TDOA 定位方法，從均方誤差、偏差以及累積分布函數(shù)3 個(gè)方面，與傳統(tǒng)的Chan 算法、未進(jìn)行誤差估計(jì)的IWO 算法進(jìn)行比較。仿真實(shí)驗(yàn)表明，在不同的傳感器位置下，所提算法的定位精度比其余算法更具優(yōu)勢(shì)，為解決水下定位問題奠定了理論基礎(chǔ)。