田宇洋，顧青濤，張任楠，張曉博，李響，戴海亮，李成

（1.北京衛(wèi)星導航中心，北京100094；2.中國人民解放軍75775部隊，廣東 廣州510000）

0 引言

實時高精度位置感知在無人機技術(shù)、醫(yī)療服務(wù)、搜索救援、智能圖書館、自動駕駛等領(lǐng)域中有著廣泛的應(yīng)用。近年來，作為傳統(tǒng)無線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）定位方法的補充，協(xié)同定位受到越來越多的關(guān)注。所謂的協(xié)同定位是指多用戶節(jié)點之間的協(xié)同，與傳統(tǒng)定位方法相比，該方法增加了用戶節(jié)點之間的幾何測量與通信。協(xié)同定位算法有很多，基于到達時間（Time of Arrival，TOA）的極大似然估計模型是應(yīng)用最為廣泛的定位模型之一，當測距誤差服從高斯分布時，極大似然模型與最小二乘估計模型（Least Square，LS）等價。為了求得該模型的最優(yōu)解，比較常見的算法為牛頓迭代法或高斯-牛頓迭代法。文獻[5]給出了這兩種算法的收斂性證明，指出收斂性與代價函數(shù)的凸性緊密相關(guān)，當目標函數(shù)為嚴格凸時（Hessian矩陣正定），由牛頓算法解算LS模型為強整體二階收斂。

劃分一個優(yōu)化問題難易程度的分水嶺在于其代價函數(shù)是凸或者非凸，而LS定位模型的代價函數(shù)一般為非凸，因此求解LS定位模型代價函數(shù)的全局最優(yōu)解是困難的，屬于NP難問題，目前已有相關(guān)研究嘗試對這一個問題進行解決。文獻[7-8]對單用戶定位場景下的LS模型進行了深入分析，提出了代價函數(shù)滿足全局為凸的條件。LS模型基于最小方差準則（這一準則也是其他定位模型的基礎(chǔ)），例如極大似然、加權(quán)最小二乘、遞推最小二乘等。與此同時，相比遞推最小二乘，卡爾曼濾波（Kalman Filtering，KF）模型相當于在兩次迭代之間多了狀態(tài)轉(zhuǎn)移步驟，其核心也是通過最小化方差求得最優(yōu)估計。因此，對LS定位模型的凸性進行分析具有一定的代表性，其相關(guān)結(jié)論可以通過最小方差準則推廣到其他定位模型。

在協(xié)同場景中，當用戶節(jié)點數(shù)量增多時，函數(shù)的局部極值點增多，使得迭代算法對初值更加敏感并導致算法不收斂。本文將對協(xié)同定位LS模型的凸性進行分析，以深入解釋這一現(xiàn)象。

1 無約束最小二乘定位模型

1.1 節(jié)點與鏈路定義

在基于TOA方法的定位場景中，設(shè)用戶節(jié)點個數(shù)為，用F={,,…,T}表示其編號的集合，用戶節(jié)點真實坐標為x∈R，1≤≤，∈N，∈N為定位場景歐幾里得空間維度。錨節(jié)點的個數(shù)為，其編號的集合為F={,,…,A}，錨節(jié)點真實坐標為s∈R，1≤≤，∈N。設(shè)所有節(jié)點的集合記為F，則F=F?F。在定位場景中，定義任意兩點之間的距離觀測為一條測距鏈路，假設(shè)某個場景中共有條測距鏈路，記各個鏈路編號的集合為={,,…,l}。定位場景中的測距鏈路可以分為兩類：一類為用戶與錨節(jié)點之間的測距鏈路（以下簡記為AT鏈路）；另一類為協(xié)同測距鏈路（以下簡記為TT鏈路）。設(shè)所有鏈路距離觀測值的集合記為D，其中AT鏈路距離觀測值的集合記為D，TT鏈路距離觀測值集合記為D，易知D=D?D，D?D=?，并且有|D|=，|D|=，|D|=-。令d是節(jié)點編號到點的真實距離，^為兩點之間距離的估計值，其中,∈F。

1.2 測距偏差定義

由于信號在傳播過程中會受到觀測噪聲、多徑效應(yīng)以及非視距（Non-Line of Sight，NLOS）傳播的影響，觀測值不等于節(jié)點之間的真實距離，存在測距偏差。設(shè)偏差向量為=[,,…,ε]∈R，其中ε表示第條鏈路上的測距偏差。在視距（Line of Sight，LOS）傳播環(huán)境中，測距偏差完全由觀測噪聲引起，其通常滿足均值為零、方差為常數(shù)的高斯分布，用表示。在NLOS環(huán)境中，除了噪聲以外還存在一個正偏差，假設(shè)此正偏差滿足均值和方差都為常數(shù)的高斯分布，用表示?；谝陨霞僭O(shè)，可以對測距偏差建模如下：

1.3 最小二乘模型定義

在非協(xié)同定位場景中，假設(shè)有個用戶節(jié)點，且任意兩個用戶節(jié)點之間無測距和數(shù)據(jù)交互。考慮某一用戶節(jié)點T，其位置的真實值為x，令^表示T節(jié)點坐標的估計值，則有：

式中‖·‖表示兩點之間的歐幾里得距離。

若測距鏈路個數(shù)為，分別記為,,…,l，令與之相對應(yīng)的距離真實值與估計值分別為d和^，且有：

式中：1≤≤,∈N；q是與節(jié)點T相連接的鏈路個數(shù)。設(shè)距離觀測值為ρ∈D,1≤≤,∈N，如果考慮偏差的存在，由定義可知，距離觀測值與真實距離之間的關(guān)系為：

那么非協(xié)同場景中無約束LS估計模型可以表示成如下形式：

式中：q是鏈路端點為T T且滿足＞的TT鏈路個數(shù)，T∈U，＞，≥2，U為與T之間存在測距鏈路的用戶節(jié)點的集合，其元素下標按由小到大的順序進行排列。令T為U中第個元素，且的值按照式（8）進行計算：

設(shè)ρ∈D,1≤≤,∈N為距離觀測值，其與真實距離之間的關(guān)系滿足式（4）。在此基礎(chǔ)上構(gòu)建協(xié)同場景無約束LS模型為：

在本文中統(tǒng)一稱F和F為LS定位代價函數(shù)并且將其記為。

2 模型的非凸性分析

2.1 非協(xié)同定位場景分析

為了便于分析且不失一般性，本文選取=2。由凸分析相關(guān)理論可知，函數(shù)的凸性與其Hessian矩陣密切相關(guān)，并且有如下定理成立：

定理1：函數(shù)為凸的二階條件。假設(shè)的函數(shù)二階可微，定義域dom為凸集且Hessian矩陣存在，則函數(shù)在dom中為凸的充要條件為：對于?∈dom，其Hessian矩陣為半正定矩陣。

首先求取代價函數(shù)F的梯度（一階微分）和Hessian矩陣（二階微分），計算結(jié)果分別如下：

運用定理1可以得出以下推論：

引理1：實對稱矩陣的特征值均為實數(shù)。

引理2：實對稱矩陣是半正定矩陣的充要條件為其所有特征值非負。

令=0，可以得到特征多項式方程為：

式（13）為一元二次方程，由引理1可知，此方程必存在2個實根，即根的判別式≥0恒成立，函數(shù)有2個非負實根的充分必要條件為：

推論2：所有滿足不等式組（14）條件的^的集合為。

推論2是LS代價函數(shù)為凸的一個等價條件。然而，由于不等式組（14）的非線性特征，使得對該不等式組分析變得比較困難。下面將針對一類特殊的情況進行討論，并且作出簡要證明。

命題1：存在一個集合，若該集合中所有估計值^均滿足^-ρ≥0，則在此集合中最小二乘代價函數(shù)F為凸，且滿足?。

其中：

對Q求特征值，令：

化簡得：

因式分解可求得的2個根分別為：

命題1實際上是F局部為凸的一個充分不必要條件，F的非凸區(qū)間會隨著ε的增大而減小，且當滿足ε＞0的測距鏈路數(shù)量增多時，F的非凸性也會增強。

2.2 協(xié)同定位場景分析

則Hessian矩陣為：

求取的特征值，通過計算可以求得其特征多項式為：

可以解得其4個特征值分別為：

由式（23）可知，當^-ρ≥0時，?0。接下來做進一步地推廣，證明當LS代價函數(shù)中同時具有兩種測距鏈路時，這一性質(zhì)仍然不變。

引理4：相似矩陣具有相同的特征值。

若測距鏈路位于錨節(jié)點與待定位節(jié)點之間，則Q的元素位于對角線和與之相鄰的位置上，且元素的個數(shù)為4，將Q中的4個元素全部平移至左上角。設(shè)變換后的矩陣為′，易知Q與′為相似矩陣。由引理4可知Q與′具有相同的特征值。設(shè)′=-′，為了求取′的特征值，對′作如下分塊：

由分塊矩陣行列式定理可知：

若測距鏈路位于兩個待定位節(jié)點之間，易知Q中的元素個數(shù)為16個，將其中各個元素全部平移至左上角，將其記為′，設(shè)′=-′。同樣地，對′進行分塊：

由分塊矩陣行列式定理可知：

3 仿真驗證

3.1 仿真場景設(shè)定

在二維平面內(nèi)建立笛卡爾坐標系，表1給出了非協(xié)同與協(xié)同場景各個錨節(jié)點的平面坐標。本節(jié)將對三種偏差環(huán)境進行仿真，分別為NLOS環(huán)境、LOS環(huán)境以及測距偏差為負的情形。每一個場景在各種情況下的偏差大小如表2和表3所示。

表1 各錨節(jié)點笛卡爾坐標 m

表2 非協(xié)同場景測距偏差 m

表3 協(xié)同場景測距偏差 m

3.2 凸性驗證

首先對F作全局仿真。考慮測距誤差不同的情況下代價函數(shù)F的凸性，作出其函數(shù)圖像、Hessian矩陣的正定圖像以及選取不同初值的迭代情況，仿真結(jié)果如圖1～圖3所示。

圖1分別顯示了NLOS環(huán)境、LOS環(huán)境以及測距偏差為負的環(huán)境下LS代價函數(shù)圖像。

圖1 非協(xié)同各場景代價函數(shù)

圖2分別顯示了二維平面中各個點Hessian矩陣的半正定情況，其中紅色部分表示?0，藍色部分表示?0，綠色部分表示不定。

圖2 非協(xié)同各場景Hessian矩陣正定圖像

由定理1可知，當為半正定時，函數(shù)為凸。從圖2a）中可以看出，當定位環(huán)境為NLOS環(huán)境時，的半正定區(qū)域不連續(xù)，不定與半負定面積總和較大，當定位環(huán)境為LOS環(huán)境時，的半正定區(qū)域連續(xù)，不定與半負定面積總和較小。由命題2可知，當存在正的測距誤差時，則代價函數(shù)F在全局范圍內(nèi)為非凸，因此在上述的兩個定位環(huán)境中，F在全局范圍內(nèi)均為非凸，如圖1a）和圖1b）所示。當測距誤差為負且絕對值較大時，滿足命題2中代價函數(shù)F為凸的全局條件，如圖1c）和圖2c）所示，由的半正定性和F函數(shù)圖像可以看出，在全局范圍內(nèi)半正定且F在全局范圍內(nèi)為凸函數(shù)。

為了說明初值選取對迭代結(jié)果的影響，從各個方向選取不同的初值，用高斯-牛頓迭代法進行位置解算。解算結(jié)果如圖3所示，其中虛線構(gòu)成的圓表示測距半徑為負，其大小為距離觀測值的絕對值。從仿真結(jié)果可知，在NLOS環(huán)境中，LS代價函數(shù)F為非凸函數(shù)，存在多個極值點，當初始值不同時迭代算法會收斂到不同的極小值點；在LOS環(huán)境中測距偏差較小，LS代價函數(shù)在全局范圍內(nèi)為非凸，但其極值點個數(shù)并沒有增加，在這種情況下迭代算法會收斂于同一個位置，說明LS模型在LOS場景中適用；在偏差為負的場景中，迭代結(jié)果與初始位置無關(guān)，驗證了在此情況下F具有全局收斂的特性。

圖3 非協(xié)同各場景仿真迭代結(jié)果

在協(xié)同場景中，選取不同的初值，利用高斯-牛頓迭代算法解算用戶位置，仿真結(jié)果分別如圖4所示。在NLOS定位環(huán)境中，由于存在較大的正測距誤差，使得F在全局范圍內(nèi)非凸并且導致產(chǎn)生了多個極值點，因此不同的初始值會導致算法迭代收斂到不同的極值點上；在LOS定位環(huán)境中，F在全局范圍內(nèi)為非凸，但正測距偏差較小，因此仍然可以收斂到相同的極值點上；在測距偏差為負的情況下，F在全局范圍內(nèi)為凸，因此無論初值如何選取，其必然會收斂到全局最優(yōu)解。此結(jié)果較好地驗證了命題2的正確性。

圖4 協(xié)同各場景仿真迭代結(jié)果

4 結(jié)語

本文對協(xié)同定位無約束LS定位模型進行了凸性分析。通過對代價函數(shù)的Hessian矩陣的分析，得出了無約束LS代價函數(shù)的一個充分不必要條件，該條件指出，當測距偏差全部為負時，無約束LS定位代價函數(shù)全局為凸。在此基礎(chǔ)上，分別對NLOS環(huán)境、LOS環(huán)境以及測距偏差為負環(huán)境下的LS代價函數(shù)凸性進行了仿真分析，驗證了該命題的正確性。除此以外，本文提出影響最小二乘代價函數(shù)非凸性的主要因素為正測距偏差，為后續(xù)研究奠定了理論基礎(chǔ)。