基于最小約束系統的分布式協作定位研究

章 平，王 炎，王 橋

(1.安徽工程大學計算機與信息學院，蕪湖 241000;2.東南大學信息工程學院，南京 210096)

0 引言

手機定位技術伴隨著移動通信的發展不斷進步。早在20世紀80年代，1G蜂窩移動通信可以根據基站位置和接收信號強度而粗略估計出接收機的位置信息，進而提升通信系統性能或者提供相關應用[1-5]。進入90年代，隨著2G和3G數字通信技術發展，各種定位技術相繼出現，如Cell-ID、TA、OTD、uplink ToA、 enhanced OTD (E-OTD) 以及A-GPS等。1999年，美國聯邦通信委員會(Federal Communications Commission， FCC)在緊急服務E911中對手機定位提出要求：移動端定位要以67%的概率定位在50m以內，95%的概率定位在150m以內；網絡端定位要以67%的概率定位在100m以內，95%的概率定位在300m以內[6]。

2000年5月，美國克林頓政府下令停止執行全球定位系統(Global Positioning System，GPS)中選擇性可用性(Selective Availability，SA)干擾策略，全球的民用GPS接收機的定位精度一夜之間提高了10倍，在室外達到了10m以下的定位精度，初步解決了手機的室外定位問題。此后，隨著基于位置服務的興起，對手機定位的精度以及覆蓋范圍都提出了更高的要求。美國FCC甚至要求手機運營商在2020年將手機定位的精度提升到m級。進入5G時代，各種新興的通信技術和手機應用都需更高精度的定位服務，如信道分配、波束成形和生活協助等，對傳統手機定位技術提出了巨大的挑戰[7]。

在4.5G的研究中，已有相關研究通過已經定位的設備和位置未知設備之間的設備到設備(Device-to-Device，D2D)間通信的測量進行協作定位[9]。協作定位是一種利用位置未知節點間的測量信息獲取節點間的相對位置信息的定位方式，在無線傳感器網絡定位中有著重要的作用，不但可以提升定位精度，更拓展了傳統定位的可定位范圍[8]。

5G條件下，D2D通信作為一種低功耗、自適應和高效率的通信方式，將會得到重要應用。該通信方式將產生大量的設備之間的信號測量，可被用于估計設備之間的距離甚至角度信息，將被用于實現高精度(m級以下)、低時延、大容量和全覆蓋的定位。同時，固定部署的基站或者熱點，現有移動定位技術也提供了各種精度不一的位置信息。如何利用設備之間的信號測量提升位置精度成為迫切需要解決的問題[10]。

本文提出了一種基于最小約束系統的分布式協作定位方法。該方法利用節點的現有位置構造最小約束系統[13]，用來確定網絡中心的位置和網絡的朝向。然后通過極大化由節點間測量決定的似然函數，優化節點間的相對位置。理論上，當用節點的真實位置構造最小約束系統后，可以完全準確給出網絡的位置和朝向，剩下的定位誤差都是由節點間測量誤差造成的。

該定位方法還具有分布式和可擴展的特點。事實上，任意選擇部分節點位置構造最小約束系統，均可通過節點間的測量更新節點間的相對位置，進而通過迭代實現網絡所有節點位置的更新。考慮到極大似然估計要求解非線性最小二乘問題，分布式的實現有助于降低算法復雜度以及節點間的通信次數。

本文安排如下：第1節介紹了定位的場景及節點間距離測量模型；第2節引入了最小約束系統，并討論了如何構造最優的最小約束系統；第3節詳細介紹了基于最小約束系統的協作定位及其分布式實現；第4節進行了仿真驗證；第5節總結全文。

1 定位場景及數學模型

5G移動通信系統中，除了移動終端與基站之間通信外，移動終端之間的D2D通信也產生了大量的節點間信號測量。這些測量包括信號強度、到達時間甚至到達角度等，提供了節點(包括移動終端和基站)之間的相對位置信息。為了方便起見，這里假定從信號測量中獲得距離信息，建模如下：

(1)

通過模型式(1)，可以得到在距離測量下，節點位置向量s=[s1,s2,…,sn]T的對數似然函數：

(2)

其中，Ε為所有距離測量的下標集，c為與位置向量s無關的常數。

極大化對數似然函數式(2)可得節點位置的估計。但是，由于節點間的距離測量無法提供網絡的位置和朝向信息，因此該估計并不唯一。為了唯一定位，通常引入錨節點，即位置已知的節點，提供外部約束信息。

在5G移動通信系統中，基站以及各種無線網絡接入點如WiFi和藍牙熱點等位置相對固定，可以擔任錨節點的角色。具體地，令Α為錨節點下標集合，有：

sk=ak，k∈Α

(3)

其中，ak=[akx,aky]T已知錨節點坐標。

理論上，在約束式(3)下，極大對數似然式(2)得到的估計具有漸進最優性。但在實際應用中卻存在如下問題：

1)無法保證錨節點位置的準確性。無論基站還是各類熱點，其位置精度受各自定位方法限制，精度各異，甚至會由于位置移動，提供錯誤的錨節點位置信息。在等式約束式(3)下，錨節點的位置誤差不僅影響網絡整體的位置和朝向的估計，更會錯誤地約束節點間相對位置信息，影響相對位置估計精度。

2)約束式(3)下極大對數似然式(2)是一中心化算法，需要所有節點間測量及錨節點位置信息，在大規模網絡中通信及計算代價較高。

3)算法擴展性有限。新增移動終端及相應的節點間測量后，需要重新進行全局優化，無法局部更新。

2 最小約束系統及其最優性

在節點間測量可以提供足夠相對位置信息的情況下，只需要將其中1個節點定在坐標原點，另外1個節點定在x軸上，第3個節點的縱坐標的符號為正即可唯一確定其他節點。換言之，3個連續的約束即可實現唯一定位(最多相差一個整體發射變換),稱之為最小約束系統(Minially Constrained System, MCS)[11]。 問題是，如何構造一組最優的約束使得定位誤差最低。

文獻[14]提供了一種利用參考位置構建最小約束系統的方法，并證明了當參考位置恰好是真實位置時，該最小約束系統是最優的。具體地，令r=[r1x,r1y,r2x,r2y,…rnx,rny]T為一個參考位置向量，定義如下線性約束：

(4)

(5)

(6)

其中，式(4)和式(5)分別利用參考位置確定了網絡中心的位置，而式(6)指明了網絡朝向。特別地，這3個線性約束在(定位之前)令r=s時，網絡中心和朝向完全正確，可以提供最優的定位精度。實際應用中，一般選擇節點的初始位置(通過GPS或者其他定位算法獲得)即可。

幾何上，線性約束等價于將位置向量s對應的相對構型通過Partial Procrustes Fit[13]擬合到參考位置向量r上，即：

(7)

式(7)是滿足式(4)、式(5)和式(6)的一組解。其中，T(s)代表網絡整體平移和旋轉變換，即剛性變換，Γ=diag(Γ0，Γ0，…，Γ0)是由n個2×2正交陣構成的2n×2n維塊對角矩陣，代表節點整體的旋轉(包括反射)，1x=[1,0,1,0,…,1,0]T和1y=[0,1,0,1，…，0,1]T分別為2n維向量，與實數x和y構成了x軸方向和y軸方向的平移變換。

本文將以節點已有位置作為參考位置向量，利用節點間的距離約束更新已有位置中的相對位置部分，保留網絡整體位置和朝向不變。

3 算法流程

3.1 參考位置估計

移動通信系統中，基站或者接入點一般都會通過GPS或者人工部署的方式獲得位置信息；手機也可以通過GPS模塊在室外定位，并通過慣性導航或者室內熱點實現室內位置的更新。這些都可以作為節點參考位置估計。特別地，對于沒有參考位置估計的節點，建議采用DV-Hop或者DV-Distance算法獲得位置估計，具體過程參見圖 1。

圖1 參考位置估計算法流程Fig.1 Reference location estimation algorithm flow

3.2 約束極大似然估計

基于最小約束系統的分布協作定位算法的核心是基于參考位置構造最小約束系統，然后在約束下求解極大似然估計，大致流程參見圖 2。

圖2 約束極大似然估計流程Fig.2 Constrained maximum likelihood estimation flow

在線性約束式(4)、式(5)和式(6)下，極大化對數似然式(2)可以通過兩種方法實現：

1)求解線性約束的基礎解系，將約束極大似然重參數化為無約束的極大似然函數，然后使用求解非線性最小二次問題的數學工具迭代求解。

2)直接極大化對數似然式(2)，盡管迭代結果不唯一，但是將最終結果利用Partial Procrustes Fit擬合到參考位置向量上，則獲得一組極大化式(2),又滿足線性約束式(4)、式(5)和式(6)的位置估計。

3.3 算法的擴展與分布式實現

由于任意給定參考位置集合，都可以構造最小約束系統，并對該集合的節點位置進行更新。因此，該定位算法具有很好的擴展性，并可以進行分布式實現。

假設引入新的節點，其參考位置可以通過相鄰(已定位)節點使用DV-Hop或者DV-Distance進行定位。該參考位置可以與相鄰節點的參考位置一起構造最小約束系統，并在該約束系統下，通過節點間測量對應極大似然估計更新該節點及相鄰節點的位置。

此外，網絡也可被劃分成若干部分，在每一個部分構造最小約束系統，通過約束極大似然估計進行分布式定位。注意，僅僅分塊定位的話，分塊之間的測量并沒有用到定位過程中，因此建議通過迭代的手段，將所有節點間的測量引入定位過程，具體參見圖 3。該方法僅僅是一種最簡單的選擇，更多優化策略留待后繼研究。

圖3 分布式協作定位流程Fig.3 Distributed cooperative localization flow

4 仿真分析

為了驗證算法性能，首先利用節點真實位置構造最優最小約束系統，研究算法在不同測量誤差下的定位性能；然后，利用DV-Distance算法獲得節點初始位置，從而構造最小約束系統，并研究在該約束系統下的定位性能；最后，通過隨機分組的方法，研究了算法的分布式實現及其性能。不失一般性，距離單位為m，相應的均方誤差單位為m2。

在10×10的平面上進行仿真。平面上隨機生成50個節點，設置通信半徑為3，得到一個部分連通的網絡，參見圖4。節點間的距離測量由模型式(1)生成，噪聲方差的變化范圍為從-30dB～10dB。

圖4 二維部分連通網絡Fig.4 Two-dimensional partial connected network

4.1 真實位置作為參考位置

將參考位置設置為節點真實位置下，可以得到最優的定位精度。如圖 5所示，定位精度完全由節點間測距精度決定，當測距誤差趨向于0時，定位誤差也趨向于0。

圖5 利用真實位置構造約束系統算法性能Fig.5 Algorithm performance of constrained system constructed by real locations

4.2 基于錨節點估計參考位置

實際中，由于無法得到節點的真實位置，通過將4個節點設置為位置已知的錨節點，引入DV-Distance算法獲得其他節點的初始位置，并進而構造出一個最小約束系統。

圖 6給出了在該約束系統下的定位性能。從圖6中可以看出，相比初始位置，利用約束極大似然估計獲得的定位精度明顯提升。

圖6 利用估計位置構造約束的算法性能Fig.6 Algorithm performance of constrained system constructed by estimated locations

4.3 分布式實現

考慮到約束極大似然本質上是一個中心化的非線性最小二乘問題，需要較高的通信量匯集測量值并實施高維參數迭代優化。提出的分布式實現則是一個降低通信和算法復雜度的有效策略。具體地，在每次實驗中隨機選擇10個節點，基于10個節點的初始位置和節點之間的測量實施該算法，更新節點位置。為了盡可能使用節點間的測量，隨機選擇10次，迭代更新，最終的結果作為定位結果。圖 7展示了定位性能，相對于集中式算法，分布式迭代算法的定位精度有所下降，但仍然提升了參考位置的精度。

圖7 分布式協作定位性能Fig.7 Distributed collaboration location performance

5 結論

5G移動通信系統中，采用D2D的通信方式為協作定位技術的引入提供了技術保證。考慮到現有的GPS、蜂窩定位以及無線局域網定位(如WiFi定位和藍牙定位)等定位技術提供了精度各異的定位結果，本文提出了基于最小約束系統的分布式協作定位方法，該方法：

1)利用D2D測量確定節點間的相對位置信息，而將網絡整體的位置和朝向留給已知參考位置確定；

2)可用GPS、DV-Hop和DV-Distance等多種算法獲得參考位置信息，且無需知道參考位置的精度；

3)具有分布式和可擴展特性，可以為5G網絡中大量終端提供位置信息。