基于遺傳-擬牛頓混合算法的地下震源定位

宋運(yùn)忠,王仁輝

(河南理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，河南 焦作 454000)

0 引 言

隨著現(xiàn)代無(wú)線網(wǎng)絡(luò)、通信技術(shù)和計(jì)算機(jī)技術(shù)等的快速發(fā)展，人們對(duì)無(wú)線通信技術(shù)的要求也越來(lái)越高。傳統(tǒng)的單一應(yīng)用功能已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足現(xiàn)代社會(huì)的需求，比如在深?？碧?、森林勘探、高山平原勘探、智能醫(yī)療和智能家居等方面。在這些環(huán)境中，無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用得到了迅速的發(fā)展，多功能的傳感器網(wǎng)絡(luò)也隨之而生，比如運(yùn)用傳感器網(wǎng)絡(luò)進(jìn)行動(dòng)植物生活習(xí)性的監(jiān)測(cè)、對(duì)未知聲源和震源的定位、深?？碧降?。

在運(yùn)用無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行定位時(shí)，第一個(gè)重要的環(huán)節(jié)是各個(gè)節(jié)點(diǎn)需要進(jìn)行時(shí)鐘同步，需要用精準(zhǔn)的時(shí)間戳(消息數(shù)據(jù)部分的傳送時(shí)間與當(dāng)前時(shí)間差值)進(jìn)行準(zhǔn)確定位。目前已有參考廣播同步[1]、梯度時(shí)間同步協(xié)議[2]等傳感器網(wǎng)絡(luò)的時(shí)鐘同步算法被用來(lái)進(jìn)行時(shí)鐘同步，且效果非常好。D.Pazo等[3]主要研究了脈沖耦合在生物振子方面的應(yīng)用；O.Simeone等[4]對(duì)一類無(wú)線傳感器網(wǎng)絡(luò)的時(shí)鐘同步進(jìn)行了討論，并分析了同步的魯棒性；R.Gentz等[5]討論了脈沖耦合無(wú)線傳感器網(wǎng)絡(luò)時(shí)鐘同步的可擴(kuò)展性；WANG Y Q等[6]提出了優(yōu)化的相響應(yīng)函數(shù)，該響應(yīng)函數(shù)能快速實(shí)現(xiàn)脈沖耦合。

第二個(gè)重要的環(huán)節(jié)是定位。通常，最簡(jiǎn)單的無(wú)線傳感器網(wǎng)絡(luò)定位方法就是為各個(gè)節(jié)點(diǎn)裝載全球定位系統(tǒng)(global positioning system，GPS)接收器，用以確定節(jié)點(diǎn)位置。但是，由于成本、各個(gè)節(jié)點(diǎn)能量及GPS對(duì)環(huán)境有一定要求等諸多條件的限制，實(shí)際中每個(gè)節(jié)點(diǎn)不可能都裝備GPS接收器，即使都裝備，也不能精確定位到毫米級(jí)別。所以本文使用到達(dá)時(shí)間差(time difference of arrival，TDOA)的定位方法對(duì)地下未知震源進(jìn)行定位。傳統(tǒng)的TDOA定位方法是：兩種不同傳播速度的無(wú)線信號(hào)在發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)之間進(jìn)行傳播，測(cè)得到達(dá)時(shí)間差，隨之計(jì)算信號(hào)點(diǎn)到接收點(diǎn)的距離。常見的無(wú)線傳感器網(wǎng)絡(luò)測(cè)距方法包括：到達(dá)時(shí)間[7-9](time of arrival，TOA)測(cè)距，該法要求硬件之間有較高的時(shí)間同步；到達(dá)角度[10](angle of arrival，AOA)測(cè)距，該法要求傳感器節(jié)點(diǎn)擁有測(cè)量角度的功能。

隨著傳感器網(wǎng)絡(luò)和定位技術(shù)的快速發(fā)展，人們對(duì)定位方法的研究越來(lái)越多，定位精度的要求也越來(lái)越高。迄今為止，陸地上相關(guān)技術(shù)發(fā)展已比較成熟[11-12]，但是對(duì)瓦斯定位及對(duì)未知震源的定位技術(shù)還不夠成熟，為此，本文提出一種基于遺傳-擬牛頓混合算法的遠(yuǎn)場(chǎng)地下震源TDOA定位方法。即利用震源發(fā)出的脈沖信號(hào)到不同傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的到達(dá)時(shí)間差實(shí)現(xiàn)對(duì)地下震源的定位。在使用無(wú)線傳感器網(wǎng)絡(luò)對(duì)地下震源進(jìn)行定位時(shí)，巧妙地將地下震波在接收節(jié)點(diǎn)的計(jì)時(shí)延遲影響定位精度的誤差，用差分誤差抑制的方法消除。首先使用脈沖耦合時(shí)鐘同步算法，同步所有節(jié)點(diǎn)時(shí)鐘，隨之測(cè)得震源到各個(gè)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的TDOA，建立相應(yīng)目標(biāo)函數(shù)，并采用遺傳算法與擬牛頓算法各自的優(yōu)勢(shì)對(duì)目標(biāo)函數(shù)進(jìn)行快速求解。

本文僅采用4個(gè)傳感器組成的網(wǎng)絡(luò)即可對(duì)目標(biāo)進(jìn)行精確定位，而已有結(jié)果如WANG R H等[13]需要8個(gè)傳感器才能解決定位問題。另外，遺傳-擬牛頓混合算法實(shí)現(xiàn)了遺傳算法的全局尋優(yōu)和擬牛頓算法的快速局部尋優(yōu)能力的有機(jī)結(jié)合，從而使得TDOA定位算法精度高、收斂速度快、穩(wěn)定性高。

1 同步和定位算法

1.1 無(wú)線傳感器網(wǎng)絡(luò)脈沖耦合時(shí)鐘同步算法

無(wú)線傳感器網(wǎng)絡(luò)脈沖耦合時(shí)鐘同步算法的最初思想在WANG Y等[14-15]的研究中得以呈現(xiàn)。本文在其基礎(chǔ)上進(jìn)行調(diào)整，把傳感器網(wǎng)絡(luò)節(jié)點(diǎn)看作一個(gè)可以周期性地觸發(fā)脈沖的振蕩器。將相位變量xi與每個(gè)傳感器節(jié)點(diǎn)(振蕩器)i∈V相聯(lián)系。脈沖耦合時(shí)鐘同步算法如下：每個(gè)振蕩器i∈V的脈沖相位以均勻頻率ωi增加，當(dāng)脈沖相位達(dá)到最大值2π時(shí)，振蕩器發(fā)出一個(gè)脈沖并重置其相位為0。當(dāng)振蕩器接收脈沖時(shí)，利用耦合強(qiáng)度l∈(0，1)和相位值Q(xi)函數(shù)更新相位xi，稱為相響應(yīng)函數(shù)，即

(1)

由相響應(yīng)函數(shù)可知，耦合強(qiáng)度l為相響應(yīng)函數(shù)的斜率，在這個(gè)算法中，最佳的時(shí)鐘同步是使用以下相響應(yīng)函數(shù)，

(2)

由式(2)可知，給出不同時(shí)刻計(jì)時(shí)器的值即相位值xi，便可確定唯一的相位值Q(xi)。相位最大值xth=CL，CL是一個(gè)具有適當(dāng)單位的任意值，一旦節(jié)點(diǎn)達(dá)到計(jì)時(shí)最大值，計(jì)時(shí)器溢出中斷即相當(dāng)于Mirollo模型[16]中的振蕩器觸發(fā)，同時(shí)向其他鄰居節(jié)點(diǎn)廣播觸發(fā)信號(hào)，從而產(chǎn)生節(jié)點(diǎn)間的耦合效應(yīng)。對(duì)所有接收到廣播信號(hào)產(chǎn)生耦合效應(yīng)的節(jié)點(diǎn)，本身計(jì)時(shí)器將進(jìn)行清零處理(xi=0)，并重新開始計(jì)數(shù)，根據(jù)系統(tǒng)需求，可以步入下一個(gè)時(shí)鐘同步周期。

1.2 TDOA定位方法

為便于闡述該定位方法的可行性與精確性，本文主要對(duì)二維平面內(nèi)未知目標(biāo)進(jìn)行模擬定位，由二維的定位結(jié)論，可以擴(kuò)展到三維及高維空間定位問題。設(shè)震源位置為(x，y)，(xi，yi)為第i個(gè)傳感器節(jié)點(diǎn)的坐標(biāo)，則震源與第i個(gè)節(jié)點(diǎn)的歐氏距離為

d(x，y)=‖x-y‖2。

(3)

本文先測(cè)得震源到各個(gè)節(jié)點(diǎn)的到達(dá)時(shí)間(TOA)，所發(fā)出的震源位于S∈R2中。如圖1所示，震源發(fā)出一個(gè)球狀的脈沖波。測(cè)得震波的TOA，起源于S，起始時(shí)刻為t0，在傳感器pi處，位于徑向距離r處的震源，有

(4)

式中：v為波速；ηi為誤差。

圖1 震源定位模型

假設(shè)震波在均勻介質(zhì)中傳播。為了準(zhǔn)確確定震源S的位置，一個(gè)傳感器測(cè)量是不夠的，因此，需要結(jié)合整個(gè)傳感器網(wǎng)絡(luò)進(jìn)行綜合定位。由于震源在某個(gè)未知時(shí)刻發(fā)出一段脈沖波，所以時(shí)間的起始量t0為未知，而且是一個(gè)額外的未知數(shù)，定位可以通過(guò)考慮傳感器i和參考傳感器rf∈V的TDOA進(jìn)行計(jì)算，如式(5)所示。

TDOAi=TOAi-TOArf=

[d(S，pi)-d(S，prf)]/v+ηirf，

(5)

式中，ηirf為第i個(gè)節(jié)點(diǎn)與參考節(jié)點(diǎn)之間的誤差。

把傳感器p1作為參考節(jié)點(diǎn)，最大似然估計(jì)[17]震源的位置為

(6)

然而實(shí)際中由于測(cè)量和定位系統(tǒng)存在不可避免的誤差，所以pi的位置不能精確確定。因此，式(6)得出的具體位置只能估計(jì)為

(7)

由式(7)可以設(shè)立所需目標(biāo)函數(shù)，為

(8)

在傳感器網(wǎng)絡(luò)中，一個(gè)給定的傳感器節(jié)點(diǎn)只需計(jì)數(shù)鄰居節(jié)點(diǎn)Ni和收集TOA值，因此，各個(gè)節(jié)點(diǎn)之間的信息交換在傳感器網(wǎng)絡(luò)中起著至關(guān)重要的作用?；谑?7)，每一個(gè)傳感器解決了本節(jié)點(diǎn)對(duì)震源的定位問題，然后與所有節(jié)點(diǎn)的定位結(jié)果相結(jié)合，最后平均化，獲得一個(gè)精確位置。為了定位出未知震源的坐標(biāo)，需要求解式(8)的解，即找到使式(8)最小的向量值(x，y)。本文選用遺傳算法搜索出離精確解最近的坐標(biāo)，將其作為擬牛頓算法的初始值，進(jìn)行快速迭代，收斂至精確坐標(biāo)，定位流程如圖2所示。

圖2 定位流程圖

2 混合算法

2.1 遺傳算法

遺傳算法(genetic algorithm，GA)是一種有效解決最優(yōu)化問題的方法，通過(guò)快速搜索得到接近精確解的近似解。GA是模擬達(dá)爾文的自然選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型，也是近年來(lái)優(yōu)化領(lǐng)域的研究熱點(diǎn)。遺傳算法具有全局搜索的功能，前期尋優(yōu)搜索速度很快，因此，在解決很多復(fù)雜和狀態(tài)多變的優(yōu)化問題方面具有很大優(yōu)勢(shì)。本文將震源定位中的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，具體參數(shù)為：選用雜交概率Pc=0.7，變異概率Pm=0.15，學(xué)習(xí)率eta=0.8，最大迭代次數(shù)kmax=500。首先，需要給定搜索的空間范圍和隨機(jī)產(chǎn)生由400個(gè)個(gè)體組成的一個(gè)群體，GA以此400個(gè)個(gè)體為初始點(diǎn)開始迭代；其次，選擇能夠達(dá)到符合預(yù)期期望的適應(yīng)度函數(shù)，即為本文的目標(biāo)函數(shù)；最后。模擬種群隨機(jī)交配原理，種群間進(jìn)行選擇、交叉和變異，產(chǎn)生子代，變異出新個(gè)體，進(jìn)行自然選擇，逐步選擇適應(yīng)新環(huán)境較強(qiáng)的個(gè)體，淘汰劣勢(shì)個(gè)體，周而復(fù)始，直到滿足所設(shè)迭代條件后，方可終止，具體算法流程見圖3。

圖3 遺傳算法流程圖

2.2 擬牛頓算法

擬牛頓法為牛頓法的改進(jìn)，是屬于局部收斂的算法[18]。遺傳算法具有前期快速收斂尋優(yōu)的功能，能夠快速搜索到離精確值較近的近似解，而擬牛頓法正好利用了局部尋優(yōu)的功能，將GA尋優(yōu)的結(jié)果作為擬牛頓算法尋優(yōu)的初始點(diǎn)，在局部區(qū)間(-200 m，200 m)內(nèi)快速搜索。對(duì)于N維函數(shù)法f(x)在k處的泰勒級(jí)數(shù)展開，可以寫為

f(x)=f(xk)+f(xk)(x-xk)+

(x-xk)T/22f(xk+1)(x-xk+1)+δ，

(9)

從此函數(shù)中可以發(fā)現(xiàn)，經(jīng)過(guò)數(shù)次迭代，有可能會(huì)陷入局部極小值點(diǎn)，所以擬牛頓算法要求初始點(diǎn)離極值點(diǎn)不能太遠(yuǎn)，而遺傳算法剛好彌補(bǔ)了此缺點(diǎn)。選擇精度ε=1.0×10-25及最大迭代次數(shù)為1 000次，擬牛頓算法具體過(guò)程如表1所示。

2.3 遺傳-擬牛頓混合算法

根據(jù)上面的討論可知，擬牛頓算法容易陷入局部最優(yōu)。因此，為了使擬牛頓算法獲得全局最優(yōu)解，必須求解問題的全局最優(yōu)先驗(yàn)信息，這種要求過(guò)于苛刻，有時(shí)是不可能的。因此，將遺傳算法的全局搜索能力嵌入到擬牛頓算法中，使擬牛頓算法不受初始搜索初值假定的約束，具體的流程如圖4所示。

2.4 仿真與分析

對(duì)一個(gè)地下震源所產(chǎn)生的脈沖波進(jìn)行定位，完全取決于震源瞬間產(chǎn)生的脈沖波。震源發(fā)出的脈沖波的起始時(shí)間顯然未知，所以，基于TDOA的定位方法是合理的。如果采用較多的傳感器節(jié)點(diǎn),可以提高定位的精度，但是過(guò)多的傳感器節(jié)點(diǎn)往往會(huì)增加成本和帶來(lái)更多的干擾信號(hào)，所以為了在通信質(zhì)量和定位精度之間達(dá)到良好的折衷，本文選用4個(gè)傳感器組成傳感器網(wǎng)絡(luò)。新建傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的坐標(biāo)分別是(0 m，0 m)，(2 m，0 m)，(4 m，0 m)，(6 m，0 m)，波速v=230 m/s。在假定均勻介質(zhì)中，波速傳播速度一定，分別使用擬牛頓算法和遺傳-擬牛頓混合算法對(duì)同一震源進(jìn)行模擬定位，仿真模擬定位結(jié)果見圖5～7。

表1 擬牛頓算法過(guò)程

圖4 遺傳-擬牛頓混合算法流程圖

由圖5擬牛頓算法x和y坐標(biāo)的定位可知，經(jīng)過(guò)30次左右迭代后，橫坐標(biāo)趨于穩(wěn)定值為19.55 m，縱坐標(biāo)為24.47 m，可得目標(biāo)位置為(19.55 m，24.47 m)，其與標(biāo)準(zhǔn)值(20 m，25 m)誤差約為3%。但是擬牛頓算法對(duì)初始值的要求比較高，如果初始值離精確值較近，則能快速收斂到精確值；如果初始值離精確值較遠(yuǎn)，則擬牛頓算法迭代求解的值很可能發(fā)散，無(wú)法得到精確解。

圖5 擬牛頓算法橫縱坐標(biāo)迭代仿真

如圖6～7所示，通過(guò)使用遺傳-擬牛頓混合算法對(duì)未知震源坐標(biāo)進(jìn)行定位，充分融合了遺傳算法和擬牛頓算法各自的優(yōu)點(diǎn)，即利用遺傳算法前期快速全局尋優(yōu)的優(yōu)點(diǎn)和擬牛頓算法后期局部迅速尋優(yōu)的優(yōu)點(diǎn)。由仿真圖6可知，遺傳-擬牛頓混合算法經(jīng)過(guò)2次迭代就已經(jīng)趨于穩(wěn)定值：最后穩(wěn)定值的橫坐標(biāo)為19.75 m，縱坐標(biāo)為24.51 m，目標(biāo)坐標(biāo)(19.75 m，24.51 m)，與標(biāo)準(zhǔn)值(20 m，25 m)誤差約為1.5%，精度得到大幅提升。產(chǎn)生此誤差的原因是：計(jì)時(shí)器存在計(jì)時(shí)頻率偏移、時(shí)鐘時(shí)延和系統(tǒng)外部干擾信號(hào)。如圖7所示，在尋優(yōu)速度方面，遺傳-擬牛頓混合算法遠(yuǎn)遠(yuǎn)優(yōu)于擬牛頓算法。因此，對(duì)于地下震源的定位，綜合比較擬牛頓算法和遺傳-擬牛頓混合算法的收斂速度及精確度的優(yōu)點(diǎn)，應(yīng)選用遺傳-擬牛頓混合算法對(duì)地下震源進(jìn)行定位。

圖6 遺傳-擬牛頓混合算法橫縱坐標(biāo)迭代仿真圖

3 結(jié) 語(yǔ)

為了提高無(wú)線傳感器網(wǎng)絡(luò)的定位精度及效率，提出一種基于遺傳-擬牛頓混合算法的到達(dá)時(shí)間差定位方法，因?yàn)榈叵抡鹪吹钠鹗紩r(shí)間未知且無(wú)法實(shí)際測(cè)量，所以提出到達(dá)時(shí)間差的定位方法更具優(yōu)勢(shì)。假定波速在均勻介質(zhì)的條件下傳播，建立目標(biāo)函數(shù)，通過(guò)遺傳-擬牛頓混合算法進(jìn)行求解。前期用遺傳算法進(jìn)行全局快速尋優(yōu)，搜索出離精確值較近的坐標(biāo)，然后將其作為擬牛頓算法的初始點(diǎn)，再進(jìn)行局部尋優(yōu)，最終能夠搜尋出比較逼近真實(shí)值的坐標(biāo)，并分析了理論上的誤差。由仿真結(jié)果可知，本文所選基于遺傳-擬牛頓混合算法的TDOA定位方法精度較高，且遺傳-擬牛頓混合算法比擬牛頓算法定位算法收斂速度快、定位穩(wěn)定性好。