摘 要：精確的位置信息在無(wú)線傳感網(wǎng)絡(luò)（WSNs）中扮演著重要地位，基于用戶節(jié)點(diǎn)之間信息交互的協(xié)同定位可以提供高精度定位，是目前非常有前景的研究方向。傳統(tǒng)的協(xié)同定位模型，例如最小二乘（LS）模型，依賴于從先驗(yàn)測(cè)量信息中得到粗略的位置估計(jì)作為迭代初值。由于代價(jià)函數(shù)一般為非凸，該模型對(duì)迭代初值的選取十分敏感，計(jì)算結(jié)果容易陷入局部極值。為了深入解釋這一現(xiàn)象，文中通過(guò)求取最小二乘代價(jià)函數(shù)的二階導(dǎo)數(shù)，同時(shí)對(duì)相應(yīng)的 Hessian 矩陣進(jìn)行相似變換，分析了最小二乘代價(jià)函數(shù)的凸性，得出最小二乘代價(jià)函數(shù)為凸的一個(gè)充分不必要條件。同時(shí)利用數(shù)值仿真驗(yàn)證了當(dāng)用戶節(jié)點(diǎn)測(cè)距偏差全部為負(fù)數(shù)時(shí)，最小二乘代價(jià)函數(shù)在全局范圍內(nèi)為凸函數(shù)，這一結(jié)論為后續(xù)研究奠定了理論基礎(chǔ)。

0 引 言

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

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

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

1 無(wú)約束最小二乘定位模型

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

在基于TOA方法的定位場(chǎng)景中，設(shè)用戶節(jié)點(diǎn)個(gè)數(shù)為M，用Fc={T1 ， T2 ，?， TM}表示其編號(hào)的集合，用戶節(jié)點(diǎn)真實(shí)坐標(biāo)為xj∈Rη，1≤j≤M，j∈N+，η∈N+為定位場(chǎng)景歐幾里得空間維度。錨節(jié)點(diǎn)的個(gè)數(shù)為N，其編號(hào)的集合為Fa={A1，A2，?，AN}，錨節(jié)點(diǎn)真實(shí)坐標(biāo)為si ∈Rη，1≤i≤N ，i∈N+。設(shè)所有節(jié)點(diǎn)的集合記為Ft，則Ft =Fa?Fc。在定位場(chǎng)景中，定義任意兩點(diǎn)之間的距離觀測(cè)為一條測(cè)距鏈路，假設(shè)某個(gè)場(chǎng)景中共有 L 條測(cè)距鏈路，記各個(gè)鏈路編號(hào)的集合為L(zhǎng)={l1 ， l2 ，?， lL}。定位場(chǎng)景中的測(cè)距鏈路可以分為兩類：一類為用戶與錨節(jié)點(diǎn)之間的測(cè)距鏈路（以下簡(jiǎn)記為 AT 鏈路）；另一類為協(xié)同測(cè)距鏈路（以下簡(jiǎn)記為 TT 鏈路）。設(shè)所有鏈路距離觀測(cè)值的集合記為 Dt，其中 AT鏈路距離觀測(cè)值的集合記為 Da，TT鏈路距離觀測(cè)值集合記為Dc，易知Dt=Da?Dc，Da?Dc=?，并且有|Dt=L|，|Da=N|，|Dc= L - N|。令dK1K2是節(jié)點(diǎn)編號(hào) K1到 K2點(diǎn)的真實(shí)距離，dK1K2為兩點(diǎn)之間距離的估計(jì)值，其中 K1 ，K2 ∈ Ft。

1.2 測(cè)距偏差定義

由于信號(hào)在傳播過(guò)程中會(huì)受到觀測(cè)噪聲、多徑效應(yīng)以及非視距（Non?Line of Sight，NLOS）傳播的影響，觀測(cè)值不等于節(jié)點(diǎn)之間的真實(shí)距離，存在測(cè)距偏差。設(shè)偏差向量為ε=［ε1，ε2，?，εL］T∈RL，其中εi表示第i條鏈路上的測(cè)距偏差。在視距（Line of Sight，LOS）傳播環(huán)境中，測(cè)距偏差完全由觀測(cè)噪聲引起，其通常滿足均值為零、方差為常數(shù)的高斯分布，用εLOS表示。在NLOS環(huán)境中，除了噪聲以外還存在一個(gè)正偏差，假設(shè)此正偏差滿足均值和方差都為常數(shù)的高斯分布，用εNLOS表示。基于以上假設(shè)，可以對(duì)測(cè)距偏差建模如下：

式中：

1.3 最小二乘模型定義

在非協(xié)同定位場(chǎng)景中，假設(shè)有M個(gè)用戶節(jié)點(diǎn)，且任意兩個(gè)用戶節(jié)點(diǎn)之間無(wú)測(cè)距和數(shù)據(jù)交互?？紤]某一用戶節(jié)點(diǎn)Tj，其位置的真實(shí)值為xj，令xj表示Tj節(jié)點(diǎn)坐標(biāo)的估計(jì)值，則有：

式中2表示兩點(diǎn)之間的歐幾里得距離。

若測(cè)距鏈路個(gè)數(shù)為N，分別記為l1 ， l2 ，?， lN，令與之相對(duì)應(yīng)的距離真實(shí)值與估計(jì)值分別為di和di，且有：

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

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

在非協(xié)同場(chǎng)景中，設(shè)Tj節(jié)點(diǎn)真實(shí)坐標(biāo)和坐標(biāo)估計(jì)值分別為xj和xj，那么有：

設(shè)測(cè)距鏈路有L條，分別記為l1 ， l2 ，?，lN，與之相對(duì)應(yīng)的距離真實(shí)值與估計(jì)值分別記為di和di 。若1≤i≤N，li為AT鏈路，按照式（3）對(duì)di和di 進(jìn)行賦值。若N《i≤L，li為T(mén)T鏈路，按照式（7）進(jìn)行賦值：

式中：qjc是鏈路端點(diǎn)為T(mén)j Tk且滿足k》j的TT鏈路個(gè)數(shù)，Tk∈Uj，k》j，j≥2，Uj為與Tj之間存在測(cè)距鏈路的用戶節(jié)點(diǎn)的集合，其元素下標(biāo)按由小到大的順序進(jìn)行排列。令Tk為 Uj中第g個(gè)元素，且 g的值按照式（8）進(jìn)行計(jì)算：

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

在本文中統(tǒng)一稱Fs和Fc為L(zhǎng)S定位代價(jià)函數(shù)并且將其記為F。

2 模型的非凸性分析

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

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

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

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

運(yùn)用定理1可以得出以下推論：推論1：當(dāng)LS代價(jià)函數(shù)的dom Fs為R2時(shí)，其定義域?yàn)橥辜Ａ?2x1?0，設(shè)滿足此條件的所有x1的集合為A，則當(dāng)x1∈A時(shí)，F(xiàn)s為凸函數(shù)。

上述推論給出了LS代價(jià)函數(shù)為凸的一個(gè)充分必要條件。?2x1為實(shí)對(duì)稱矩陣，關(guān)于實(shí)對(duì)稱矩陣有以下兩個(gè)引理成立：

引理 1［10］：實(shí)對(duì)稱矩陣的特征值均為實(shí)數(shù)。

引理 2［10］：實(shí)對(duì)稱矩陣是半正定矩陣的充要條件為其所有特征值非負(fù)。

由引理2可知，對(duì)?2x1半正定的判斷可以轉(zhuǎn)化為對(duì)其特征值正負(fù)的判斷。設(shè)J=?2x1，J∈R2 × 2，令Jij 為J 中各個(gè)元素，設(shè)J的特征值為λ，其特征多項(xiàng)式為：

令G=0，可以得到特征多項(xiàng)式方程為：

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

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

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

命題1：存在一個(gè)集合C，若該集合中所有估計(jì)值x1均滿足di-ρi ≥ 0，則在此集合中最小二乘代價(jià)函數(shù)Fs為凸，且滿足C?A。

引理3：有限個(gè)半正定矩陣的和仍為半正定矩陣。即若Ri?0， 1≤i≤N， i∈N+，則有W=∑i=1N，Ri ? 0。

考慮對(duì)J進(jìn)行分解，并且令J =∑i =1NQi

其中：

對(duì)Qi求特征值，令：

化簡(jiǎn)得：

因式分解可求得λ的2個(gè)根分別為：

從式（18）中可以看出，矩陣Qi有2個(gè)特征向量，其中λ1》0 恒成立，所以當(dāng)λ2=di-ρi ≥0時(shí)，Qi ?0。由引理3易知，當(dāng)di-ρi≥0， 1≤i≤N， i∈N+ 成立時(shí)，J?0。所有滿足此條件的估計(jì)值x1的集合即為C。

命題1實(shí)際上是Fs局部為凸的一個(gè)充分不必要條件，F(xiàn)s的非凸區(qū)間會(huì)隨著εi 的增大而減小，且當(dāng)滿足εi》0的測(cè)距鏈路數(shù)量增多時(shí)，F(xiàn)s的非凸性也會(huì)增強(qiáng)。

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

在協(xié)同場(chǎng)景中，測(cè)距鏈路由AT鏈路和TT鏈路兩部分組成。受引理3的啟發(fā)，將Fc的 Hessian矩陣J分解為若干個(gè)子矩陣Qi，每一個(gè)Qi 實(shí)際上是一個(gè)與估計(jì)值相關(guān)的函數(shù)f（di）=（di-ρi2），子矩陣中的各個(gè)元素為f（di）對(duì)用戶節(jié)點(diǎn)坐標(biāo)的二階偏導(dǎo)。在2.1節(jié)中，證明了當(dāng)li為AT鏈路時(shí)滿足命題1，接下來(lái)說(shuō)明當(dāng)li為T(mén)T鏈路也具有類似于命題1的性質(zhì)。為了便于分析，選取協(xié)同場(chǎng)景中的某一條TT鏈路lk，記此鏈路兩端的用戶節(jié)點(diǎn)為T(mén)m，Tn。其估計(jì)值分別為（xm，ym），（xn，yn），測(cè)距觀測(cè)值為ρk，此時(shí)LS代價(jià)函數(shù)為：

分別對(duì)xm，xn，ym，yn求偏導(dǎo)，可得梯度向量（一階微分）為：

則Hessian矩陣為：

求取J 的特征值，通過(guò)計(jì)算可以求得其特征多項(xiàng)式為：

可以解得其4個(gè)特征值分別為：

由式（23）可知，當(dāng)dk-ρk≥0時(shí)，J?0。接下來(lái)做進(jìn)一步地推廣，證明當(dāng)LS代價(jià)函數(shù)中同時(shí)具有兩種測(cè)距鏈路時(shí)，這一性質(zhì)仍然不變。

設(shè)協(xié)同場(chǎng)景中有M個(gè)用戶節(jié)點(diǎn)，記Fc的Hessian矩陣為J ，易知J∈R2M×2M 。對(duì)J進(jìn) 行分解，并且令J=∑i=1LQi。其中，Qi 為每一個(gè)測(cè)距鏈路對(duì)應(yīng)的Hessian矩陣。

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

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

式中：中第k行l(wèi)列元素。

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

令|Gi′|=0，由非協(xié)同場(chǎng)景分析可知，|G11|=0的2個(gè)解分別為λ=1和λ=di-ρidi，|Gi′| 0的剩余（2M-2）個(gè)解均為 0。因此，當(dāng)di -ρi≥0時(shí)，Qi?0。

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

式中：

gkl為Gi′中第k行l(wèi)列元素。

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

令|Gi |=0。由協(xié)同鏈路分析可知，|G11|的特征值有4個(gè)，分別為λ1=λ2=0，λ3=4以及 λ4=4di-ρidi，|Gk′|=0 剩余（2M-4）個(gè)解均為0。因此，當(dāng)di-ρi≥0時(shí)，Qi?0。

命題1指出，在滿足di-ρi≥0這一條件時(shí)，總可以找到合適的區(qū)間，在區(qū)間中LS代價(jià)函F為凸。

命題2：對(duì)于?i ， 若di-ρi≥0在x?=［x1，x2，?， xM ］T∈R2M上恒成立，則F在R2M上為凸函數(shù)。

命題2是LS代價(jià)函數(shù)全局為凸的一個(gè)充分不必要條件。在實(shí)際場(chǎng)景中，當(dāng)測(cè)距偏差大于 0時(shí)，距離觀測(cè)值ρi為正，在此情況下不滿足全局為凸的條件，若εi≤-di，則ρi≤0，此時(shí)di-ρi≥0恒成立，F(xiàn)s在全局范圍內(nèi)為凸。

3 仿真驗(yàn)證

3.1 仿真場(chǎng)景設(shè)定

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

3.2 凸性驗(yàn)證

首先對(duì)Fs作全局仿真?？紤]測(cè)距誤差不同的情況下代價(jià)函數(shù)Fs的凸性，作出其函數(shù)圖像、Hessian矩陣J的正定圖像以及選取不同初值的迭代情況，仿真結(jié)果如圖1~圖3所示。

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

圖2分別顯示了二維平面中各個(gè)點(diǎn)Hessian矩陣J的半正定情況，其中紅色部分表示J?0，藍(lán)色部分表示J?0，綠色部分表示不定。

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

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

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

4 結(jié) 語(yǔ)

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

審核編輯 ：李倩