覃泓銘 王 玫，2 羅麗燕* 韋金泉

1(桂林電子科技大學(xué)認(rèn)知無線電與信息處理教育部重點(diǎn)實(shí)驗(yàn)室 廣西 桂林 541004) 2(桂林理工大學(xué)信息科學(xué)與工程學(xué)院 廣西 桂林 541007)

0 引 言

聲源定位技術(shù)由于廣泛應(yīng)用于智能交通[1]、安防監(jiān)控[2]、電話會(huì)議[3]、人機(jī)交互[4]、導(dǎo)航[5]等而備受關(guān)注。傳統(tǒng)的聲源定位方法可分為三類：基于可控波束形成的方法、基于高分辨率譜估計(jì)的方法和基于到達(dá)時(shí)間差的方法。其中,基于可控波束形成的定位方法[6-7]需要做全局搜索,計(jì)算量大,并且依賴于聲源信號(hào)和噪聲信號(hào)的先驗(yàn)知識(shí)?；诟叻直媛首V估計(jì)的定位方法[8-9]需要在空間中搜索目標(biāo)聲源位置,這種方法的定位精度高但計(jì)算復(fù)雜度非常高。相比前兩種定位技術(shù),基于到達(dá)時(shí)間差(TDOA)的定位方法[10-11]計(jì)算復(fù)雜度較低、定位速度較快性好且硬件成本低,因此成為聲源定位領(lǐng)域中的研究熱點(diǎn)。

基于TDOA的定位方法的中心思想是求解由幾何關(guān)系構(gòu)成的方程組,求解方程組的復(fù)雜度會(huì)隨著接收節(jié)點(diǎn)/基站數(shù)量的增加而加大,并且設(shè)備誤差與時(shí)延估計(jì)誤差可能會(huì)導(dǎo)致方程組無解,因此基于該方法的聲源定位問題往往被表述為一個(gè)非線性優(yōu)化問題。已經(jīng)存在很多方法用于解決優(yōu)化問題,例如最大似然法、非線性最小二乘法和加權(quán)最小二乘法,但這些方法具有計(jì)算復(fù)雜度高、需要估計(jì)初始位置的缺點(diǎn)。Chan算法、Fang算法、Taylor級(jí)數(shù)展開法與最小二乘法的結(jié)合[12-14]解決了確定初始位置與聲源位置最優(yōu)估計(jì)的問題,但仍存在計(jì)算復(fù)雜度高、對(duì)初始位置敏感的問題。為了解決這一問題,相關(guān)研究者從幾何分析的角度出發(fā),提出了利用圓的幾何關(guān)系搜索聲源位置的定位算法[15-17]。文獻(xiàn)[15]提出了基于收縮圓的定位方法，其思想是以恒定的步長收縮所有圓的半徑,直到相交區(qū)域的面積達(dá)到較小的閾值。文獻(xiàn)[16]中提出一種基于GCC-PHAT與收縮圓的優(yōu)化方法,相比于收縮圓方法,定位精度與速度得到了改善。文獻(xiàn)[17]中提出了多圓聯(lián)動(dòng)搜索目標(biāo)的定位算法,其思想是：首先計(jì)算初始搜索半徑,根據(jù)TDOA的測(cè)量值計(jì)算每個(gè)接收節(jié)點(diǎn)相對(duì)于搜索半徑的聯(lián)動(dòng)半徑,并根據(jù)搜索步長改變搜索半徑進(jìn)行搜索,找到具有最大步長的最佳半徑,然后減小步長進(jìn)行搜索以獲得更準(zhǔn)確的估計(jì)位置。該方法將傳統(tǒng)的多維搜索轉(zhuǎn)換為一維搜索,并且初始值的計(jì)算簡(jiǎn)單,降低了計(jì)算復(fù)雜度。相比于傳統(tǒng)的搜索算法,該方法有效提高了搜索速度和定位精度,但該方法通過逐步提高步長的精度來提升定位精度,在搜索過程中存在重復(fù)搜索的問題。本文提出一種利用三分法進(jìn)行多圓聯(lián)動(dòng)搜索的聲源定位算法，優(yōu)化了文獻(xiàn)[17]中減小搜索步長進(jìn)行重復(fù)搜索的問題。此外,本文對(duì)于初始值的設(shè)定進(jìn)行了改進(jìn),減少了搜索迭代次數(shù)。較于文獻(xiàn)[17],本文算法不僅減少了迭代次數(shù),還降低了每次迭代搜索時(shí)的計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果表明,本文方法在提高定位速度的同時(shí),有效提升了定位精度。

1 基于TDOA的聲源定位方法

基于TDOA的聲源定位基本思想[18]是：通過測(cè)量聲源到各個(gè)接收節(jié)點(diǎn)的到達(dá)時(shí)間差，得到至少兩個(gè)距離差，通過距離差可以獲得雙曲線方程，求解雙曲線的交點(diǎn)即可得到聲源的位置?？紤]如圖1所示的二維聲源定位系統(tǒng)，假設(shè)聲源位置為S(x,y)，接收節(jié)點(diǎn)位置為Ni(xi,yi)，聲源到各個(gè)接收節(jié)點(diǎn)的距離為ri，到各接收節(jié)點(diǎn)之間的距離差為dij，以節(jié)點(diǎn)0為參考節(jié)點(diǎn)，聲源到各傳感節(jié)點(diǎn)與參考節(jié)點(diǎn)的時(shí)間差為τi0，c為聲速，則有：

(1)

di0=r0-ri=cτi0

(2)

(i=0,1,2,…,n-1)

(3)

圖1 聲源定位系統(tǒng)示意圖

聲源位置就是由式(4)構(gòu)成的方程組的解,該方程組是基于雙曲線的非線性方程組,在理想條件下,通過聯(lián)立方程組即可求出解,即雙曲線的交點(diǎn)。但由于設(shè)備誤差、時(shí)延估計(jì)誤差的存在,這個(gè)交集往往是空集,因此求解該方程組的重點(diǎn)是如何采用搜索算法估計(jì)聲源位置。聲源定位中,兩種廣泛使用的聲源定位算法是Chan算法和Taylor算法。Chan算法將如上所述的非線性方程組轉(zhuǎn)化為線性方程組,然后采用最小二乘法(LS)獲得最佳解。Taylor算法將非線性方程組通過Taylor級(jí)數(shù)展開的方法整理成線性方程組,選擇一個(gè)初始值后進(jìn)行迭代搜索,直到坐標(biāo)精度滿足搜索的終止條件，即可獲得最佳解。

1.1 Chan算法

Chan算法[19]是非遞歸雙曲線方程組解法,具有解析表達(dá)式解。其主要的特點(diǎn)為在測(cè)量誤差服從理想高斯分布時(shí)定位精度高,并且可以通過增加基站數(shù)量來提高算法精度。該算法的核心思想如下：

將式(1)展開并將其線性化得：

(x0-xi)x+(y0-yi)y=ki+r0di0

(4)

(5)

由此可得到矩陣表達(dá)式：

AX=F

(6)

(7)

由此可求出聲源的估計(jì)位置：

X=(ATA)-1ATF

(8)

1.2 Taylor算法

Taylor級(jí)數(shù)展開法[20]是一種需要初始估計(jì)位置的遞歸算法,在每一次遞歸中通過求解TDOA測(cè)量誤差的局部線性最小二乘(LS)解來改進(jìn)估計(jì)位置。該算法的核心思想如下：

將式(3)根據(jù)Taylor級(jí)數(shù)展開得：

ht=Gtδ+ε

(9)

(10)

式中：Rm，1表示由聲源到傳感節(jié)點(diǎn)m與傳感節(jié)點(diǎn)1的時(shí)延差計(jì)算出來的距離差；Rm-R1為聲源到傳感節(jié)點(diǎn)m與到傳感節(jié)點(diǎn)1的真實(shí)距離差。

(11)

其加權(quán)最小二乘解為：

(12)

式中：Q為TDOA測(cè)量值的協(xié)方差矩陣。初始迭代時(shí),令x=x0，y=y0,在下一次迭代中，則有：

x(1)=x0+Δxy(1)=y0+Δy

(13)

重復(fù)以上過程,直到Δx、Δy足夠小,并滿足一定的閾值ε,使得：

|Δx|+|Δy|<ε

(14)

經(jīng)過k次迭代,得到的解(xk,yk)即為聲源的估計(jì)位置。

2 算法簡(jiǎn)介

2.1 算法的基本原理

算法基于TDOA測(cè)量值,通過構(gòu)建幾何關(guān)系將非線性問題轉(zhuǎn)化為線性問題,將多維搜索轉(zhuǎn)化為一維搜索。算法的基本原理可由下描述：

假設(shè)聲源位置為S(x,y),參考節(jié)點(diǎn)位置為N0(x0,y0),其他參考節(jié)點(diǎn)位置為Ni(xi,yi),聲源到各個(gè)接收節(jié)點(diǎn)的距離為ri,聲源到各接收節(jié)點(diǎn)與到參考節(jié)點(diǎn)的時(shí)間差為τi0,則有：

(15)

(16)

易知,式(3)可由式(15)、式(16)聯(lián)立得到。對(duì)于式(15)、式(16)的求解,考慮如圖2所示的定位系統(tǒng),假設(shè)估計(jì)的聲源到參考節(jié)點(diǎn)的距離為Rk,到其他接收節(jié)點(diǎn)的距離為Ri,則有：

(17)

(18)

聯(lián)立式(17)、式(18)可得：

(19)

令：

(20)

則式(19)的解為：

(21)

(22)

圖2 接收節(jié)點(diǎn)部署示意圖

由方程可知,若改變參考圓半徑Rk,其他圓的半徑Ri也會(huì)隨著改變,即不同的Rk對(duì)應(yīng)不同的解(估計(jì)聲源位置)。如圖3所示(★：聲源位置；●：接收節(jié)點(diǎn)；-‥-：Rk為初始值時(shí)的幾何關(guān)系；---：Rk改變一次時(shí)的幾何關(guān)系；—：Rk改變N次時(shí)的幾何關(guān)系)，不斷地搜索Rk,直到Rk=r0,此時(shí)的估計(jì)聲源位置即為真實(shí)聲源位置。

圖3 多圓聯(lián)動(dòng)搜索的基本思想

在搜索Rk的過程中,初始值的設(shè)定以及搜索算法直接影響到算法收斂速度,即聲源搜索速度。文獻(xiàn)[17]根據(jù)參考圓B0與各個(gè)參考圓Bi相交時(shí),方程具有解的條件設(shè)定了Rk的初始搜索半徑,并以初始搜索半徑為最小值,通過改變搜索步長來尋找最優(yōu)半徑,最后根據(jù)最優(yōu)半徑估計(jì)出聲源位置。由于只設(shè)定了初始搜索半徑的最小值,該搜索過程為由小往大的單向搜索。為了進(jìn)一步加快搜索速度,本文根據(jù)接收節(jié)點(diǎn)位置的幾何關(guān)系設(shè)定了Rk的初始搜索半徑的最小值與最大值,即搜索半徑區(qū)間,并同時(shí)改變最小值與最大值進(jìn)行雙向搜索,不斷地縮小Rk的搜索區(qū)間。此外,文獻(xiàn)[17]首先采用較大的搜索步長來估計(jì)聲源的粗略位置,然后通過減小步長進(jìn)行精確搜索。當(dāng)搜索步長較大時(shí),算法收斂速度較快,但定位精度相應(yīng)較低,當(dāng)搜索步長較小時(shí),定位精度得到有效的提高,但重復(fù)搜索加長了搜索時(shí)間,整個(gè)搜索過程速度較慢。本文將三分法運(yùn)用到雙向搜索過程中,改善了文獻(xiàn)[17]中重復(fù)搜索的問題,進(jìn)一步加快了搜索速度。同時(shí),利用三分法進(jìn)行搜索,最終搜索區(qū)間的下限值無限逼近于上限值,有效提高了定位精度。

2.2 搜索半徑的初始值

設(shè)Lij為接收節(jié)點(diǎn)i到參考節(jié)點(diǎn)j之間的距離,則：

(23)

由聲源、節(jié)點(diǎn)Ni、節(jié)點(diǎn)Nj構(gòu)成的三角形滿足三角形三邊關(guān)系：

Rk+Rk-cτij≥Lij

(24)

即：

(25)

聲源應(yīng)該位于由4個(gè)節(jié)點(diǎn)形成的矩形區(qū)域中，則Rk應(yīng)滿足：

Rk≤max{Lij}

(26)

所以Rk應(yīng)滿足：

min{(L1j-d1j)/2}≤Rk≤max{Lij}

(27)

以式(27)確定的搜索區(qū)間進(jìn)行搜索,在搜索過程中,每改變一次搜索區(qū)間,誤差函數(shù)的值都會(huì)隨著改變。當(dāng)誤差函數(shù)為最小值時(shí)即停止搜索,此時(shí)的Rk為全局最優(yōu)解,即最佳半徑。

2.3 搜索的停止條件

根據(jù)式(7)，可定義誤差函數(shù)：

(28)

式中：第一項(xiàng)為真實(shí)聲源到各接收節(jié)點(diǎn)的距離差，第二項(xiàng)為根據(jù)Rk估計(jì)的聲源到各接收節(jié)點(diǎn)的距離差。

(29)

在理想情況下，εi(x,y)=0，但由于設(shè)備誤差、時(shí)延估計(jì)誤差的存在，εi(x,y)≠0，所以當(dāng)誤差滿足式(29)時(shí)，即停止搜索。

圖4 三分法的基本思想

文獻(xiàn)[17]中,改變步長進(jìn)行迭代搜索的算法計(jì)算復(fù)雜度為O(mn),其中m為改變步長精度的次數(shù)。由三分法的基本思想可知,利用三分法進(jìn)行搜索算法的計(jì)算復(fù)雜度為O(2log3n),易知O(2log3n)

利用三分法搜索Rk從而搜索誤差的最小值,即可獲得估計(jì)聲源的最佳位置,該過程由以下步驟完成：

步驟1計(jì)算搜索半徑Rk的初始值：

(30)

(31)

步驟2進(jìn)行第i次迭代搜索(可見算法1)：

(32)

則

(33)

反之

(34)

算法1基于三分法的半徑搜索算法

3) fori=1;i<100;i++

9) else

12) end

14) break

15) end

16) end

3 實(shí)驗(yàn)及分析

為了驗(yàn)證本文方法的定位性能,采用文獻(xiàn)[17]提出的多圓聯(lián)動(dòng)搜索目標(biāo)定位算法與本文算法進(jìn)行比較。實(shí)驗(yàn)選用Behringer ECM 8000全向型麥克風(fēng)4個(gè)、哈曼卡頓aura studio音響1個(gè)、M-AUDIO M-TRACK QUAD 4通道外置聲卡1個(gè),另外使用1臺(tái)聯(lián)想筆記本控制收發(fā)信號(hào)及數(shù)據(jù)處理。如圖5所示,實(shí)驗(yàn)場(chǎng)景較為空曠,其中一面為墻面。受麥克風(fēng)信號(hào)線長限制,麥克風(fēng)以矩形(6.5 m×6.5 m)陣型進(jìn)行擺放,坐標(biāo)分別為N0(0,0)、N1(6.5,0)、N2(6.5,6.5)、N3(0,6.5)。麥克風(fēng)與音響高度均為1.3 m,聲源信號(hào)為0至16 k chirp信號(hào),采樣頻率為32 kHz。選取3個(gè)聲源位置S1(2,2)、S2(3,4)、S3(5.5,3),在每個(gè)聲源位置分別采集20組獨(dú)立數(shù)據(jù)。每組定位結(jié)果如圖6-圖8所示,平均誤差如表1所示。

圖5 實(shí)驗(yàn)場(chǎng)景

圖6 聲源位于(2,2)處的誤差對(duì)比結(jié)果

圖7 聲源位于(3,4)處的誤差對(duì)比結(jié)果

圖8 聲源位于(5.5,3)處的誤差對(duì)比結(jié)果

表1 兩種方法的聲源定位平均誤差

從表1可以看出,從位置1到位置3的平均誤差在增大,原因在于聲源越靠近墻面(見圖5),麥克風(fēng)接收到的反射波干擾越大,時(shí)延估計(jì)的誤差則越大,導(dǎo)致定位誤差增大,本文暫不討論時(shí)延估計(jì)誤差對(duì)定位的影響。在定位精度方面,本文方法的定位精度與文獻(xiàn)[17]方法的定位精度相差不大,但略微優(yōu)于文獻(xiàn)[17]方法。為證明本文方法在計(jì)算復(fù)雜度方面的優(yōu)越性,取聲源位置為(3,4)時(shí)的數(shù)據(jù)進(jìn)行計(jì)算復(fù)雜度的對(duì)比,結(jié)果如表2、表3所示。

表2 文獻(xiàn)[17]方法的Rk搜索過程 單位：m

表3 本文方法的Rk搜索過程 單位：m

從表2可以看出,文獻(xiàn)[17]的方法首先以3.08 m為初始半徑、1 m為步長進(jìn)行搜索,找到最佳半徑位于[5.80,6.08]區(qū)間。然后將步長減小為0.1 m進(jìn)行搜索,找到最佳半徑位于[5.18,5.28]區(qū)間。最后將步長減小為0.01 m進(jìn)行搜索,直到誤差滿足搜索結(jié)束條件。搜索結(jié)束時(shí),Rk為5.21 m,對(duì)應(yīng)的估計(jì)聲源坐標(biāo)為(3.135,4.170),經(jīng)過10次迭代搜索找到聲源最佳估計(jì)位置。而從表3可以看出,本文方法首先確定最佳半徑位于[3.080,9.192]區(qū)間,然后通過三分法不斷改變區(qū)間的左右界限,并結(jié)合誤差判斷是否結(jié)束搜索。搜索結(jié)束時(shí),Rk為5.17 m,對(duì)應(yīng)的估計(jì)聲源坐標(biāo)為(3.105,4.146),僅經(jīng)過5次迭代搜索便可找到聲源最佳估計(jì)位置。對(duì)于文獻(xiàn)[17]的方法,通過改變?nèi)尾介L進(jìn)行迭代搜索,易知其計(jì)算復(fù)雜度為O(3n),而對(duì)于本文方法,通過將n/3處的元素與2n/3處的元素比較,將搜索范圍縮小為原來的n/3,其計(jì)算復(fù)雜度為O(2log3n)。

綜上所述,相比于文獻(xiàn)[17]提出的多圓聯(lián)動(dòng)搜索聲源定位算法,本文算法不僅減小了迭代搜索的次數(shù),并且減小了每次搜索時(shí)的計(jì)算復(fù)雜度。在加快定位速度的同時(shí),有效提升了定位精度。

4 結(jié) 語

對(duì)于TDOA聲源定位系統(tǒng)中的定位估計(jì)階段,定位方程求解速度與定位精度是關(guān)鍵問題。較傳統(tǒng)的迭代搜索定位算法,多圓聯(lián)動(dòng)搜索聲源定位算法有效提高了搜索速度和定位精度。本文提出利用三分法進(jìn)行多圓聯(lián)動(dòng)搜索的聲源定位算法,將非線性方程組轉(zhuǎn)化為線性方程組,并在迭代搜索的過程中引入三分法進(jìn)行搜索,進(jìn)一步提高了定位求解速度與定位精度。理論分析和實(shí)驗(yàn)結(jié)果均證明了本文算法的優(yōu)越性。未來的工作將研究減小時(shí)延估計(jì)誤差的方法并與本文算法相結(jié)合,進(jìn)一步提高該算法的定位精度。