基于貪心算法的無人機純方位無源定位

祁晨彬，蔡依蝶，陳建林，王 潔

（臺州學院電子與信息工程學院，浙江 臨海 317000）

0 引言

無人機的有源定位原理是：由一個終端向外部信號源發射信號，當外部信號源定位后，再將定位信息發送回該終端。無源定位原理是：觀測站不主動發射信號，而是通過接收目標輻射源或散射無線電信號來估計目標的位置［1］。對于靜態目標，常見的無源定位方式是通過測量和計算信號發射與接收到達的時間差［2］來進行定位的；對于移動物體的無源定位，現有研究的主要對象是在海中航行的船只［3］，其信號源靜止、位置信息已知且無偏差。而在無人機的實際運用中，發射信號的無人機位置常常未知或已知但不精確。目前國內外常用的無源定位技術有：到達角定位技術［4］；到達時間定位技術［5］；到達頻差定位技術［6］；到達時間差定位技術［7］。

純方位無源定位是指在不使用向外發射信號設備的情況下，同時發射信號的設備不具備接收信號的能力，僅利用被動接收信號的無人機接收到的角度信息對該無人機進行定位［8］。它具有保密性好、安全性高、距離遠、隱蔽性強、抗干擾能力強、探測距離遠等優點。

由于純方位無源定位技術所用信息單一，對于高精度的定位實現較困難，特別是三維空間中移動物體的定位。徐勇［9］建立了雙站無源定位模型，通過采用最小二乘法的方式來實現對目標距離的有效估計。王本才等［10］在多站純方位無源定位算法的研究進展中指出：最小二乘算法、最大似然算法及擴展卡爾曼濾波算法等經典的算法仍存在不足，雖然其較先前的研究有了一定的進展，但依舊沒有實現發射信號的無人機位置未知或已知但不精確情況下的有效定位。

本文以全國大學生數學建模競賽賽題為背景，考慮由9 架無人機（編號F1～F9）近似均勻分布在某一圓周上，1 架無人機（編號F0）位于圓心的圓形編隊，在該圓上調整9 架無人機的位置直至使其真正均勻分布。已知純方位無源定位條件是：被動接收信號的無人機所接收到的角度信息為該無人機與任意兩架發射信號的無人機的夾角。例如：被動接收信號的無人機F3 接收到F0，F1，F5 發射的角度信息α1，α2，α3，記F0～F9分別表示無人機F0～F9 所在位置，如圖1 所示。本文擬建立基于貪心算法思想的純方位無源定位無人機的模型，調整該模型相應的參數，使其適用于圓形編隊。結果表明，純方位無源定位模型至少使用3 架信號發射無人機才可對多架無人機進行有效定位。

圖1 被觀測無人機接收到的方向信息示意圖

1 模型建立和求解

由于無人機自身可以感應高度信息，即可自動調整所有無人機至同一高度，因此，文中僅考慮二維平面中對被動接收信號的無人機的定位。

1.1 基本假設

假設1：將無人機視為質點，不考慮其朝向、體積等因素對定位準確度的影響。

假設2：忽略無人機在運動過程中產生的擾動對信號接收的影響。

假設3：在運動過程中，不考慮調整所需時間，僅考慮某一時刻各個無人機的位置。

1.2 無人機純方位無源定位模型

無人機純方位無源定位模型是指由編隊中某幾架無人機發射信號，其余無人機被動接收信號，從中提取出方向信息進行定位、調整無人機位置的模型，可分為信息全已知模型和信息部分已知模型。

1.2.1 發射信號的無人機信息全已知模型

全已知表示發射信號的無人機位置無偏差且編號已知。對此我們建立被動接收信號的無人機的定位模型，由位于圓心的無人機（F0）和編隊中另外兩架無人機發射信號，從而調整其余位置略有偏差的被動接收信號的無人機。

設F0 為已知位置的一架無人機，F1 和F5 為另外兩架發射信號的無人機。3 架無人機構成以F0為圓心、R為半徑的圓，且F1，F5均在該圓上。該圓所處平面內有一點P，P指代其余待定位的無人機，將P分別與F0，F1，F5相連接，分別標記∠F0PF1，∠F0PF5，∠F1PF5為α1，α2，α3。若α3>90°，則P在弧F0F1的劣弧附近；反之，P在優弧附近。僅考慮P與F0和F1時，由于線段F0F1及其對應角α1已知，利用虛擬軌跡算法作出P點的運動軌跡（如圖2 所示），不難發現P的運動軌跡為一段圓弧。

圖2 僅考慮點P、F0 和F1 時P 點的運動軌跡圖

設F1和F0之間的直線距離為R，且α1已知。當△F0PF1為以α1為頂角的等腰三角形時，利用等腰三角形三線合一以及同弧所對應的圓心角是圓周角的兩倍的性質得出：

同理，在僅考慮P、F0和F5時，可確定P在以r2為半徑的圓O2上運動。結合阿波羅尼斯圓［11］的思想，計算出兩圓交點坐標，即P和F0的坐標；再結合圓的性質以及余弦公式，則可計算出P的極坐標。

以F0為極點，射線F0F1為極軸，長度單位為m，角度單位為（°），逆時針方向為正方向建立一個極坐標系。F0的極坐標為（0，0），F1的極坐標為（R，0）。由于圓上的9 架無人機是均勻分布且發射信號的無人機位置準確，則無人機F5 的極坐標為（R，160°）。由于圓相對于任意的直徑對稱，可假設P在弧F1F0F5的優弧附近；若P在弧F1F0F5的劣弧附近，只需將最終所求得的位置坐標關于射線F0F1對稱，Fm和Fn（其中m

圖3 被動接收信號的無人機定位圖

為了計算簡便，以F0為坐標原點，直線F0F1方向為x軸，其垂直方向為y軸建立直角坐標系。首先，計算出圓心O1和O2的極坐標：

利用極坐標轉直角坐標公式［12］，計算出圓心O1和O2的直角坐標如下：

利用式（5）和式（6），計算出圓方程如下：

由于（0，0）為無人機F0 的坐標，解得點P的直角坐標為

因此，可以將上述方法推廣到信號發射無人機Fm和Fn，建立被動信號無人機的定位，以F0為極點，射線F0Fm為極軸，長度單位為m，角度單位為（°），逆時針方向為正方向建立一個極坐標系。無人機F0 的極坐標為（0，0），無人機Fm的極坐標為（R，0），無人機Fn的坐標為（R，40°（n-m））。經計算得，點P的極坐標依舊為()。

1.2.2 發射信號的無人機信息部分已知模型

部分已知模型是指若發射信號的無人機位置無偏差，某位置略有偏差的無人機除了接收到編號為F0 和F1 的無人機發射的信號，還接收到編隊中若干編號未知（即位置未知）的無人機發射的信號，需確定發射信號無人機架數以及對位置偏差的無人機進行調整。

已知F0和F1的坐標及其對應角∠F0PF1=α的大小，即可確定點P的運動軌跡是以O1為圓心，r1為半徑的圓弧。由于O1F0=O1F1=r1，則可確定不論角α如何變化，圓心O1始終在線段F0F1的中垂線上。假設編號及位置信息未知的信號發射無人機有i(i≤7)架，則點P處共可以收到i+ 1 個以射線PF0為邊的角度信號。將接收到除了α以外的角，按角度從小到大排列，依次標記為α1,α2,…,αi。令無人機F0所在位置為圓心P0，無人機F1所在位置為P1，逆時針方向標記無偏差時各無人機所對應的位置（如圖4 所示）為Pj(j=2,3,…,9) 關于射線P0P1上下對稱，即P2和P9對稱，P3和P8對稱，P4和P7對稱，P5和P6對稱。

圖4 T 時刻∠P0PPj示意圖

由于發射信號的無人機只能確定F1 和F0 的編號及位置信息，不能確定其余發射信號的無人機的位置，即其余發射信號的無人機可能處于Pj(j= 2,3,…,9)的任意點。假設僅增加一架發射信號的無人機，被動接收信號的無人機接收到3 個方向信號，分別為α,α1,α+α1。此時Pj中任意一點作為信號發射點，都可以在圓O1上找到一點P，使得∠P0PPj=α1。由此可以說明無人機信息部分已知時，僅3 架無人機不能進行有效定位。

保持α不變，即保持點P在圓弧上運動。連接PPj，記錄在點P的運動過程中∠PPjP0實時變化情況。當α= 70.36°時，點P運動過程中∠PPjP0的實時變化情況如表1 所示。

表1 α=70.36°時點P 運動過程中∠PPjP0 實時變化情況表單位：(°)

若在F0 和F1 的基礎上再增加i架無人機，可以對點P進行有效定位。相當于在某時刻T隨機取∠1～∠8 中的i個角度信息A={α1,α2,…,αi}；同樣，在T′ 時刻隨機取∠1～∠8 中的i個角度信息A′ ={α1′,α2′,…,αi′}。當且僅當T=T′時，使得A=A′，那么i個角度信息可以唯一確定圓O1上一點P，也就是說至少還需要增加imin架發射信號的無人機，才可以實現被動接收信號的無人機的有效定位。

為減少運算次數、優化算法，對上述數據進行以下處理：比較1～n時刻中任意兩個時刻的角度數據，記錄下這兩個時刻8 個角中角度相同的個數N；找出任意時刻任意組合下具有最多相同角度的個數Nmax，其中，Nmax+ 1 =imin。具體流程如圖5 所示。

圖5 優化計算流程圖

1.3 基于貪心算法思想建立實時定位跟蹤模型

考慮將無人機調整時的每一時刻分割都視為靜止狀態，從而獨立考慮采用貪心算法進行實時定位且決定接下來的調整方案。

分析表1 的數據，發現編號為F1 的無人機在半徑為100 m 的圓周上，所以假設編號為F1 的無人機位置無偏差。根據表1 的數據我們利用MATLAB 軟件畫出了無人機的初始點坐標，以F0為圓心，100 m 為半徑的圓，以及每一架無人機均勻分布在圓上的最終結果，如圖6 所示。從圖6 可以得出，除了P0和P1外，其余所有的無人機位置都是有偏差的。

圖6 無人機初始位置與目標位置圖

針對無人機的調整方案，在某一時刻時，將除P0和P1外的所有待調整的無人機位置記為P。發射電磁信號的無人機位于點P0和P，接收信號的無人機位于點P1，可以得到α1，要將F3移動到目標位置P3，α1的角度應該為50°，其計算方法如下：

其中：P=P2（或P9）時對應的Pt為1，P=P3（或P8）時對應的Pt為2，以此類推,如圖7 所示。

圖7 點F3 和P0 發射電磁信號

記Δδ=|α1- ∠P0P1P3|為目前夾角與目標夾角的差值，Δδt為t時刻的Δδ，建立實時定位跟蹤模型為

步驟一：將F3這個點分別向四周擴展一次（向四周移動一個小單位），移動一次后退回，觀察α1的變化。如果α1的度數是趨近于目標位置的度數（50°），就向該方向繼續移動，重復以上操作，直到α1= 50°。利用MATLAB 軟件編程分析可得移動后的無人機F3是在射線P1P3上。

將F3通過上述步驟迭代到射線P1P3上后，發射電磁信號的無人機位于點P0和P1，F3作為接收信號的無人機，可以得到α2。要將F3移動到目標位置P3，α2的角度為50°，其計算方法與公式（11）一致，其中：P=P2時對應的Pt為1，P=P3時對應的Pt為2，以此類推，如圖8 所示。

圖8 點P0 和P1 發射電磁信號

步驟二：與步驟一類似，將F3這個點分別向四周擴展一次，移動一次后退回，觀察α2的變化，如果角α2的度數是趨近于目標位置的度數（50°）時就向該方向繼續移動，重復以上操作，直到α2= 50°。分析后可得出，移動后的無人機F3是在以O為圓心的圓上的。

重復步驟一和步驟二，分別以P0、P和P0、P1作為發射電磁信號的無人機，使用貪心算法［13］通過多次迭代之后可以將無人機的位置無限地接近目標位置，對于除P0和P1外的其他點也做以上步驟，最終可以得到均勻分布在一個圓上的9 架無人機。

貪心算法是指求解問題時，總是作出當前最好的選擇，即不從整體最優上加以考慮，算法得到的是在某種意義上的局部最優解［14］?；谪澬乃惴ㄋ枷?，每次在調整無人機位置時都取得當時的局部最優解，找到與目標方向最接近的移動，最終得到完整的移動方案。

2 仿真研究

當α= 46.24°時，將∠PPjO從小到大依次標記為∠1～∠8，點P運動過程中∠PPjO實時變化情況如表2 所示。

表2 α=46.24°時點P 運動過程中∠PPjO 實時變化情況表單位：(°)

利用MATLAB 軟件計算得到α= 46.24°時，Nmax= 2。當α= 37.96°時，將∠PPjO從小到大依次標記為∠1～∠8，點P運動過程中∠PPjO實時變化情況如表3 所示。

表3 α=37.96°時點P 運動過程中∠PPjO 實時變化情況表單位：(°)

利用MATLAB 軟件計算得到：當α= 37.96°時，Nmax= 2，imin=Nmax+ 1 = 3。

經檢驗發現，當角度α改變時，不會使Nmax繼續增大，那么只要再增加3 架發射信號的無人機就可以進行有效定位。定位精度不同，所需要的發射信號的無人機數量也不同。

3 結語

本文采用純方位無源定位的方法確定無人機的位置，利用實時定位跟蹤模型和貪心算法思想，改變該實時定位跟蹤模型相應的參數，實時追蹤定位被動接收信號的無人機，調整位置略有偏差的無人機，使其適用于圓形編隊隊形。