水聲定位算法學(xué)習(xí)總結(jié)

1、定位算法學(xué)習(xí)總結(jié)一、無(wú)線傳感器定位技術(shù)分類目前定位技術(shù)廣泛地應(yīng)用到各個(gè)領(lǐng)域，而且出現(xiàn)了很多定位算法， 常用的定位方法有： 到達(dá)角（angel of arrival，aoa ）定位、到達(dá)時(shí)間（time of arrival，toa ）定位、到達(dá)時(shí)間差（ time difference of arrival，tdoa ）定位以及aoatoa 、aoa tdoa等混合定位的方法。選擇哪種定位方法要根據(jù)定位精度、硬件條件等因素來(lái)確定， 但是最終目的是要用優(yōu)化的方法得到滿意的定位精度。在沒(méi)有時(shí)間同步信號(hào)時(shí)，往往采用tdoa 定位方法， tdoa 定位法可消除對(duì)移動(dòng)臺(tái)時(shí)間基準(zhǔn)的依賴性， 因而可以降低成本并

2、仍然保證較高的定位精度，但是需要有較好的延時(shí)估計(jì)方法，才能保證較高的時(shí)延估計(jì)精度。（1） 基于測(cè)距的定位技術(shù)基于測(cè)距的定位方法依靠測(cè)量相鄰節(jié)點(diǎn)之間的距離或者方向信息。現(xiàn)在有很多成熟的算法被用于基于測(cè)距的定位。例如toa 算法通過(guò)信號(hào)傳播時(shí)間獲取距離，tdoa算法利用接收從多個(gè)節(jié)點(diǎn)發(fā)出信號(hào)的時(shí)間差估測(cè)位置，而 aoa算法則通過(guò)為每個(gè)節(jié)點(diǎn)設(shè)置天線陣列來(lái)測(cè)量節(jié)點(diǎn)間的相對(duì)方向角度值。（2） 無(wú)需測(cè)距的定位技術(shù)無(wú)需測(cè)距的定位方法不要求距離信息，只依靠有關(guān)待定位傳感器與種子節(jié)點(diǎn)之間連通性的測(cè)量數(shù)據(jù)。 這種定位方法對(duì)硬件要求低， 但是測(cè)量的準(zhǔn)確度容易被節(jié)點(diǎn)的密度和網(wǎng)絡(luò)條件所影響，因此不能被對(duì)精度要求高的基于

3、wsn的應(yīng)用采用。二、三邊定位和多變定位（1） 信號(hào)強(qiáng)度（ rss ，received signal strength ）通過(guò)信號(hào)在傳播中的衰減來(lái)估計(jì)節(jié)點(diǎn)之間的距離，無(wú)線信道的數(shù)學(xué)模型。盡管這種方法易于實(shí)施， 但卻面臨很多挑戰(zhàn)。首先信道由于受到信道噪聲、 多徑衰減 （multi-path fading） 和非視距阻擋（non-of- sight blockage ）的影響1，具有時(shí)變特性，嚴(yán)重偏離上訴模型；其次衰減率會(huì)隨外界環(huán)境的不同而發(fā)生相應(yīng)改變。 根據(jù)接收到的信號(hào)估計(jì)出的距離d 將有很大誤差。（2） 信號(hào)傳播時(shí)間 /時(shí)間差往返時(shí)間（ toa/tdoa/rtof ）a)到達(dá)時(shí)間（ toa ，

4、time of arrival）使用發(fā)射機(jī)到接收機(jī)之間往返的時(shí)間來(lái)計(jì)算收發(fā)機(jī)之間的距離，要求發(fā)射機(jī)和接收機(jī)嚴(yán)格時(shí)間同步。b)往返傳播時(shí)間（ rtof ，roundtrip-time-of-flight）發(fā)射機(jī)和接收機(jī)可屬于不同的時(shí)鐘域，基于信號(hào)傳播時(shí)間的測(cè)距精度由時(shí)間差的測(cè)量精度決定。時(shí)間差的精度由參考時(shí)鐘決定。c)到達(dá)時(shí)間差（ tdoa,time difference of arrival ）使用兩種不同傳播速度的信號(hào)，向同一個(gè)方向發(fā)送即可。圖 1 示意圖（3） 接收信號(hào)相位差（ pdoa,phase difference of arrival ）通 過(guò) 測(cè) 量 相 位差 ， 求 出 信 號(hào)

5、 往 返 的 傳 播 時(shí) 間 2 ， 計(jì) 算 出 往 返 距 離，其中，是信號(hào)頻率，是信號(hào)的波長(zhǎng)，是發(fā)送信號(hào)和反射信號(hào)的相位差， 由上式可知 d 的范圍是 0， 。 不同的距離如果相差倍，則測(cè)量獲得的相位相同。 通過(guò)相位差的方式測(cè)量距離， 需要知道距離 d 范圍，才能夠確定出 n 的值，估算出距離。（4） 近場(chǎng)電磁測(cè)距（ nfer ，near field em ranging ）利用近場(chǎng)與磁場(chǎng)的相位差來(lái)測(cè)量距離，射頻信號(hào)包括電場(chǎng)和磁場(chǎng)兩部分。例如，當(dāng)目標(biāo)距離接近發(fā)射天線時(shí)相位相差90o； 在距離相差 1/2 波長(zhǎng)時(shí)， 相位差接近 0。由此可以通過(guò)電場(chǎng)與磁場(chǎng)的相位差，估計(jì)到天線的距離。 近場(chǎng)電磁

6、測(cè)距方法的測(cè)距范圍在 0.05之間，最佳測(cè)量范圍0.08之間。該方法由于距離限制，現(xiàn)有的定位系統(tǒng)很少采用。三、 tdoa算法研究1. 基于測(cè)距的定位技術(shù)算法對(duì)比分析算法種類rss toa rtof tdoa pdoa nfer 條件需求信號(hào)衰減量發(fā)射和接收機(jī)之間的往返時(shí)間往返傳播時(shí)間目標(biāo)發(fā)射信號(hào)到達(dá)各個(gè)節(jié)點(diǎn)的時(shí)間差接收信號(hào)相位差相位差與距離的準(zhǔn)確關(guān)系優(yōu)點(diǎn)易 于 實(shí)施，對(duì)硬件要求較低發(fā)射機(jī)和接收機(jī)可屬于不同的時(shí)鐘域?qū)Υ郎y(cè)節(jié)點(diǎn)沒(méi)有時(shí)間同步要求缺點(diǎn)算法模型受環(huán)境影響大，精度較低要求發(fā)射機(jī)和接收機(jī)嚴(yán)格時(shí)間同步使用射頻信號(hào)時(shí)要求高精度時(shí)鐘需要首先知道往返距離范圍對(duì)測(cè)量距離有限制2. tdoa 算法特性(

7、1) 對(duì)目標(biāo)時(shí)間基準(zhǔn)無(wú)依賴性選用 tdoa 算法對(duì)待測(cè)節(jié)點(diǎn)沒(méi)有時(shí)間同步要求。在無(wú)線傳感器網(wǎng)絡(luò)中，實(shí)現(xiàn)節(jié)點(diǎn)之間的時(shí)間同步較為困難。而且考慮在實(shí)際應(yīng)用中， 一般情況下， 我們無(wú)法獲取待測(cè)目標(biāo)的準(zhǔn)確時(shí)間信息。tdoa算法只需獲取目標(biāo)發(fā)射信號(hào)到達(dá)各個(gè)節(jié)點(diǎn)的時(shí)間差。根據(jù)一個(gè)時(shí)間差信息即可將目標(biāo)定位在一個(gè)雙曲面上（如圖3 所示） ，那么假如有三個(gè)時(shí)間差信息，則三個(gè)雙曲面可交與一點(diǎn)， 這一點(diǎn)即為目標(biāo)位置。 由此消除了對(duì)目標(biāo)時(shí)間基準(zhǔn)的依賴性 3，應(yīng)用場(chǎng)合得以拓展。圖 3 tdoa雙曲面模型(2) 適合水下環(huán)境要求對(duì)于水聲定位系統(tǒng)， 如果采用電磁波傳遞信息， 則在水下將很快衰減。 因此只能夠使用聲波進(jìn)行通信。由

8、上述分析可知，tdoa算法必須依靠高精度的參考時(shí)鐘來(lái)保證其精確度。 對(duì)于低成本、低帶寬、無(wú)參考時(shí)鐘的無(wú)線傳感器網(wǎng)絡(luò)來(lái)說(shuō)，獲得高精度的時(shí)鐘本身就是一個(gè)挑戰(zhàn)。如果用射頻信號(hào)進(jìn)行測(cè)距，的時(shí)鐘精度就有 300m的誤差。但使用超聲波等低傳播速率信號(hào)進(jìn)行測(cè)距時(shí)，1ms的時(shí)鐘精度便可達(dá)到 30cm的精度?？梢?jiàn)，用超聲波信號(hào)實(shí)現(xiàn)的tdoa 算法不僅可滿足水下環(huán)境的要求，而且能保證足夠的定位精度。3. tdoa 算法分析在對(duì)目標(biāo)信源進(jìn)行定位時(shí)， 因?yàn)闊o(wú)法獲得時(shí)間同步信號(hào)而沒(méi)有時(shí)間基準(zhǔn)，常采用 tdoa技術(shù)得到時(shí)延估計(jì)值，進(jìn)而得到目標(biāo)信源到兩個(gè)基站之間的距離差，多個(gè) tdoa測(cè)量值就可以構(gòu)成一組關(guān)于目標(biāo)信源位置的

9、雙曲線方程組，求解該方程組就可以得到目標(biāo)信源的估計(jì)位置4。圖 4 tdoa算法模型設(shè)目標(biāo)節(jié)點(diǎn)的坐標(biāo) e為 e=(x,y,z)， 其余 n+1個(gè)已知位置的節(jié)點(diǎn)為p0, p1, ., pm, ., pn，它們的坐標(biāo)分別為pm= (xm, ym, zm)，0 m n。則目標(biāo)與任一節(jié)點(diǎn)的距離為(1) 為了簡(jiǎn)化計(jì)算可設(shè)主節(jié)點(diǎn)的坐標(biāo)為 (0,0,0)，那么為(2) 距離是水中聲速 v 與傳播時(shí)間的乘積，tdoa 算法需要波面到達(dá)每個(gè)副節(jié)點(diǎn)p1, ., pm, ., pn與到達(dá)主節(jié)點(diǎn) p0的時(shí)間差值，即v=v-v(3) v=-(4) 圖 5 為了更好地說(shuō)明這一過(guò)程，如圖5 所示。 p0和 p1分別是節(jié)點(diǎn) p

10、0, p1接收到e的發(fā)射波形，可見(jiàn)p1接收到信號(hào)要比p0延遲 5ms左右，相當(dāng)于的值。對(duì) p0和 p1的波形求互相關(guān)函數(shù)可得cross-correlation波形。其峰值時(shí)刻對(duì)應(yīng)的時(shí)間值即為時(shí)間差。上述仿真分析針對(duì)的是連續(xù)時(shí)間信號(hào)，對(duì)于離散時(shí)間信號(hào)可根據(jù)式(f*g)n進(jìn)行計(jì)算。1)非線性定位算法通過(guò)以上分析知要得到目標(biāo)的坐標(biāo)值，至少需要三個(gè)時(shí)間差信息， 因此至少需要 p0, p1, p2, p3 四個(gè)已知位置的節(jié)點(diǎn) 5。設(shè)目標(biāo)到達(dá)主站 p0(0,0,0) 與各副站的距離差為，則化簡(jiǎn)可得(5)(6) 其中：，。對(duì)于 3 個(gè)距離差測(cè)量值可以組成如下非線性方程組(7) 先 把r作 為 常 量 ， 求

11、 出x,y,z關(guān) 于r的 代 數(shù) 式 ， 然 后 代 入中解出 r 的值。 r 的值確定后， x、y、z 的值便可確定。由整個(gè)計(jì)算過(guò)程可知這種非線性算法得到的解可能不唯一，需要解模糊。 此外計(jì)算量過(guò)大也是其缺點(diǎn)之一。針對(duì)上述非線性算法存在的問(wèn)題， 我們?cè)谠O(shè)計(jì)中采用基于最小二乘法的牛頓迭代定位算法對(duì)數(shù)據(jù)進(jìn)行處理。 最小二乘法定位精度不是很高， 但可對(duì)目標(biāo)信源的位置作初始估計(jì)。有了這一估計(jì)值，再使用牛頓迭代法對(duì)初始結(jié)果進(jìn)行修正，則不但可以提高定位精度，而且可以加快計(jì)算速度，節(jié)省時(shí)間。 最小二乘法估計(jì)初始位置由（8）可得矩陣形式的線性方程組hx=l (8) 其中 h=，x=，l=要求解 x，必須使殘

12、差 r=hxl 的平方和最小，即f(x)= (9) 對(duì)上面的方程求導(dǎo)并令其為零，得 (10) 若為非奇異陣，則得到 (11) 的最小二乘法估計(jì)為 (11) 牛頓迭代法修正(1) 將用最小二乘法解得的信源位置x設(shè)為初始值， 代入牛頓迭代法的關(guān)系式 3，求解迭代后的位置為(k=0,1,2,n-1) ；(2) 分 別 將和代 入n-4個(gè) 冗 余 函 數(shù) 表 達(dá) 式(i=5, ,n),利 用 最 優(yōu) 化 方 法 ，(i=5, ,n),為根據(jù)測(cè)距精度要求給定的值， 為給定的精度要求；(3) 判斷是否滿足條件或，如果滿足其中的一個(gè)條件，則迭代過(guò)程結(jié)束， 輸出，否則將結(jié)果作為初始值，即，繼續(xù)上面的步驟，直到

13、滿足條件為止。2)線性定位算法以上的非線性算法采用一個(gè)主節(jié)點(diǎn)和三個(gè)副節(jié)點(diǎn)，可測(cè)得三個(gè)時(shí)間差信息，即三個(gè)方程。 雖然這樣可用最少的節(jié)點(diǎn)數(shù)目完成定位任務(wù)，節(jié)約成本， 但是有著需解模糊、計(jì)算量大、定位實(shí)時(shí)性較低等缺點(diǎn)。此時(shí)如果增加一個(gè)副節(jié)點(diǎn)p4，則線性方程組變?yōu)?(12) 此時(shí)可把 r 作為求解變量，直接求解四元一次線性方程組。由（13）可得矩陣形式的線性方程組hx=l (13) 其中 h=，x=，l=可得 x=hl，由此可得出目標(biāo)信源的位置。由求解過(guò)程可以看出，線性定位算法相比非線性算法解法簡(jiǎn)單，無(wú)模糊，求解精度高。該方法就是常用的五元十字tdoa 定位算法。4. 仿真與分析基于上述算法分析， 我

14、們對(duì)基于最小二乘法的牛頓迭代算法和五元十字定位算法進(jìn)行了 matlab 仿真實(shí)驗(yàn)。4.1 仿真實(shí)驗(yàn)(1) 基于最小二乘法的牛頓迭代算法圖 6 仿真實(shí)驗(yàn)傳感器布陣圖如圖 6 所示，主節(jié)點(diǎn)坐標(biāo)為=0,0,0，三個(gè)副節(jié)點(diǎn)坐標(biāo)分別為=2,0,1、=0,2,0、=2,2,0。假設(shè)待測(cè)目標(biāo) s的位置是 s=3,4,5。計(jì)算可得h=，l=最小二乘法估計(jì)= ，可見(jiàn)最小二乘法的估計(jì)值與目標(biāo)的實(shí)際位置相差較大。但通過(guò)牛頓迭代可提高精確度。 下面給出牛頓迭代法的部分matlab 代碼：% 牛頓迭代法解非線性方程組% 輸入?yún)?shù)：迭代初值，迭代方程，精度要求function h=newton(start_newton,

15、f_newton,p_newton) f_temp=start_newton; temp=0;0;0; while sum(abs(temp-f_temp)p_newton temp=f_temp; f_temp=f_temp-subs(f_newton,x, y, z,f_temp(1),f_temp(2),f_temp(3); endh=f_temp; 將 最 小 二 乘 法 的 估 計(jì) 值 代 入 ， 通 過(guò) 迭 代 后 可 得 最 終 定 位 結(jié) 果s =2.9998,3.9998,4.9997 ，s與 s 的誤差間距為 3.9123e-004。(2) 五元十字定位算法圖 7 仿真實(shí)驗(yàn)

16、傳感器布陣圖如圖 7 所示，主節(jié)點(diǎn)坐標(biāo)為=0,0,0，四個(gè)副節(jié)點(diǎn)坐標(biāo)分別為=0,2,1、=-2,0,0、=0,-2,0、=2,0,0。仍假設(shè)待測(cè)目標(biāo) s的位置是 s=3,4,5。計(jì)算可得h=，l=所以 x=hl=，可得最終定位結(jié)果s =2.9997,3.9993,4.9999 ，計(jì)算可得 s與 s 的誤差間距為 7.6811e-004。(3) 算法性能比較通過(guò)多組上述算法測(cè)試實(shí)驗(yàn)可列出以下性能參數(shù)比較: 定位算法傳 感 器 節(jié)點(diǎn)數(shù)目(n) 相 對(duì) 誤 差(x) 相 對(duì) 誤 差(y) 相 對(duì) 誤 差(z) 程 序 執(zhí) 行時(shí)間(t) /s均 方 根 誤差 (rmse) 最 小 二 乘法4 7.84

17、% 7.76% 8.75% 0.563 0.586 基 于 最 小二 乘 的 牛4 6.67e-005 5.00e-005 6.00e-005 5.432 3.91e-004 頓 迭 代 算法五 元 十 字定位算法5 1.00e-004 1.75e-004 2.00e-005 0.498 7.68e-004 注：程序執(zhí)行時(shí)間在intel(r) core(tm)2 duo cpu t6400 2.00ghz處理器下測(cè)得，不同硬件平臺(tái)結(jié)果可能不同。4.2 實(shí)驗(yàn)結(jié)論在仿真實(shí)驗(yàn)中我們分別對(duì)采用四個(gè)傳感器節(jié)點(diǎn)的非線性tdoa算法和采用五個(gè)傳感器節(jié)點(diǎn)的線性tdoa定位算法在 matlab 環(huán)境下進(jìn)行了測(cè)試

18、。由實(shí)驗(yàn)結(jié)果可知五元十字定位法和經(jīng)牛頓迭代法修正的最小二乘算法可達(dá)到同等高的精度數(shù)量級(jí)。對(duì)比兩者的程序執(zhí)行時(shí)間可知五元十字定位法因?yàn)橛?jì)算量較小運(yùn)行快，定位實(shí)時(shí)性高， 但所需節(jié)點(diǎn)至少為五個(gè)。 因此在水聲換能器成本較高且對(duì)定位實(shí)時(shí)性要求不高時(shí)可采用基于最小二乘的牛頓定位算法。四、 參考文獻(xiàn)1 zhong wen guo.perpendicular intersection:locatingwireless sensors with mobile beacon. ocean university of china,hong kong university of science and technology 2 李曉維 .無(wú)線傳感器網(wǎng)絡(luò)技術(shù) .北京:北京理工大學(xué)出版社 ,2007.08 3