[發(fā)明專利]基于到達時間的多目標定位外部逼近近似凸優(yōu)化算法

有效

• 申請?zhí)枺?/td>: 201710720839.6
• 申請日: 2017-08-22
• 公開（公告）號: CN107271958B
• 公開（公告）日: 2019-07-12
• 發(fā)明（設(shè)計）人: 羅文洲;蘇文藻
• 申請（專利權(quán)）人: 四川航天系統(tǒng)工程研究所
• 主分類號: G01S5/06
• 分類號: G01S5/06;G01S5/00;G06F17/50
• 代理公司: 四川省成都市天策商標專利事務(wù)所 51213
• 代理人: 劉興亮

本發(fā)明公開了一種基于到達時間的多目標定位外部逼近近似凸優(yōu)化算法，首先構(gòu)造原始問題模型，然后使用松弛方法將原問題松弛為一個混合整數(shù)凸優(yōu)化問題模型，并針對半正定矩陣構(gòu)建新的合適的約束，然后使用外部逼近近似算法子模型和連續(xù)凸優(yōu)化問題模型，使用OAA算法求得待定位的各個目標的坐標值。本發(fā)明利用外部近似逼近算法，對基站的布局和目標所在區(qū)域沒有現(xiàn)有方法如此復(fù)雜的要求，并且能夠確保收斂到全域最優(yōu)解，并且不需要初始估計點。

技術(shù)領(lǐng)域

本發(fā)明屬于基于無線信號定位技術(shù)領(lǐng)域，特別涉及一種多目標定位問題的凸優(yōu)化算法，適用于基于TOA的多目標定位問題。

背景技術(shù)

無線定位技術(shù)，最早用于二戰(zhàn)時期對艦艇和戰(zhàn)斗機等軍事目標的定位問題。隨著科技的發(fā)展，無線定位技術(shù)越來越多的在工業(yè)、民用和國防等領(lǐng)域得到了廣泛的應(yīng)用。比如緊急救援響應(yīng)，危險物品追蹤，手機定位，過程控制。通過數(shù)學(xué)方法來改進無線定位算法的估計速度和精度一直是相關(guān)科技人員關(guān)心的問題。

得益于凸優(yōu)化算法的發(fā)展，高效的凸優(yōu)化松弛技術(shù)能應(yīng)用于目標定位問題。隨著大數(shù)據(jù)、移動互聯(lián)網(wǎng)和物聯(lián)網(wǎng)等技術(shù)的快速發(fā)展，多目標定位問題已成為一個無線定位領(lǐng)域的研究熱點。目前的主要研究關(guān)注于使用最新的凸優(yōu)化算法去完善單目標定位問題，主要使用了半正定松弛，二次錐松弛和分枝界限法等方法來解決單目標定位問題。其中為了提高計算效率，一階加速算法，擬牛頓法和內(nèi)點法等高收斂速度的算法也應(yīng)用在計算以上的松弛后的問題中。

特別地，對于多目標定位問題，因為基站不能識別信號源于哪一個目標，因此該問題是一個NP-hard問題，現(xiàn)有多目標定位算法只能在合理布置基站，然后目標分布在特定范圍的前提下，選擇合適的起始估計點的條件下才能得到一個全局最優(yōu)解。否則，只能確保收斂到一個局部最優(yōu)解。并且為了解決NP-hard問題，計算復(fù)雜度隨著目標數(shù)量的增加而呈現(xiàn)出指數(shù)級的增加，并且容易陷于局部最優(yōu)解。因此設(shè)計一種能提高對基站和目標位置魯棒性、高收斂速度和收斂至全域最優(yōu)的算法具有很大的實際應(yīng)用前景。

發(fā)明內(nèi)容

針對上述現(xiàn)有技術(shù)的不足，本發(fā)明的目的在于提出一種基于到達時間(TOA)的多目標定位外部逼近近似凸優(yōu)化算法(OAA)，該方法基于外部近似逼近凸優(yōu)化算法最突出的優(yōu)勢在于，利用外部近似逼近算法，對基站的布局和目標所在區(qū)域沒有現(xiàn)有方法如此復(fù)雜的要求，并且能夠確保收斂到全域最優(yōu)解，并且不需要初始估計點。

本發(fā)明是這樣實現(xiàn)的：

實現(xiàn)本發(fā)明的技術(shù)思路是首先構(gòu)造原始問題模型(1)，然后使用松弛方法將原問題松弛為一個混合整數(shù)凸優(yōu)化問題模型(2)，并針對半正定矩陣構(gòu)建新的合適的約束，然后使用外部逼近近似算法子模型(3)和連續(xù)凸優(yōu)化問題模型(4)，使用OAA算法求得待定位的各個目標的坐標值。

本發(fā)明更具體的步驟如下：

基于到達時間的多目標定位(time of arrival based multiple sourcelocalization TOA-MSL)外部逼近近似凸優(yōu)化算法(outer approximal approachalgorithm OAA)，，包括通過半正定松弛，二次錐松弛、泰勒松弛和添加SDP約束條件后，根據(jù)最大似然估計(MLE)模型得到一個混合整數(shù)凸優(yōu)化問題，根據(jù)外部逼近近似算法得到精確的多目標坐標。

具體包括以下步驟：

a)通過TOA定義，使用最大似然估計構(gòu)造了一個混合整數(shù)、非凸的原始問題模型(1)；

b)通過采用半正定松弛、泰勒松弛和二次錐松弛等松弛方法以及添加SDP約束條件，將原問題松弛為一個混合整數(shù)凸優(yōu)化問題模型(2)；

c)通過解外部逼近近似算法子模型(3)得到一個整數(shù)部分的解P，對應(yīng)的最優(yōu)函數(shù)值作為整個算法的下界(LB)；