基于最優(yōu)化的廣域雷場空間多節(jié)點(diǎn)坐標(biāo)修正算法*

趙建新，張宏映，陳 兵，魏玉龍

（北方自動控制技術(shù)研究所，太原 030006）

0 引言

智能雷場是在傳統(tǒng)雷場基礎(chǔ)上的新型信息化地雷武器系統(tǒng)，將傳統(tǒng)不動雷提升為具有按照指令布局、通道自動封鎖等信息處理能力的活動雷［1］。針對室外活動節(jié)點(diǎn)，傳統(tǒng)方法采用GPS進(jìn)行定位，而在野外環(huán)境下，普通GPS模塊的定位精度在10 m～15 m。在廣域雷場空間中，為實(shí)現(xiàn)有效區(qū)域封鎖，活動雷投放密度較高，各活動雷間距離小于3 m?；诔杀竞投ㄎ痪瓤紤]，在每個活動雷中集成了UWB測距模塊，其價格較為低廉，測距精度為米級。只在部分活動雷內(nèi)部集成了GPS模塊，包含了GPS模塊的活動雷稱為錨節(jié)點(diǎn)，其余活動雷稱為普通節(jié)點(diǎn)，錨節(jié)點(diǎn)為普通節(jié)點(diǎn)提供基準(zhǔn)坐標(biāo)，普通節(jié)點(diǎn)利用錨節(jié)點(diǎn)坐標(biāo)通過三邊定位法完成定位。在進(jìn)行活動雷布局時，根據(jù)各錨節(jié)點(diǎn)的GPS坐標(biāo)得到的錨節(jié)點(diǎn)分布態(tài)勢與錨節(jié)點(diǎn)實(shí)際物理分布情況差距過大，導(dǎo)致所有活動雷間的坐標(biāo)相對誤差過大，不能滿足精度要求。因此，需要對各節(jié)點(diǎn)坐標(biāo)進(jìn)行修正，較大限度降低坐標(biāo)相對誤差。

1 基于最優(yōu)化的廣域雷場空間多節(jié)點(diǎn)坐標(biāo)修正方法描述

GPS的誤差包含了公共誤差、傳播延遲誤差等，其誤差具有隨機(jī)性［2］。針對廣域雷場空間中GPS坐標(biāo)相對誤差較大的問題，采用了GPS與精準(zhǔn)測距相結(jié)合的方法，利用UWB測距的高精度［3］，提高節(jié)點(diǎn)之間的相對坐標(biāo)精度。

多節(jié)點(diǎn)坐標(biāo)的修正過程分為4個步驟：

1）劃分區(qū)域并確定點(diǎn)集；

2）尋找凸多邊形；

3）頂點(diǎn)坐標(biāo)修正；

4）其余節(jié)點(diǎn)坐標(biāo)修正。

1.1 劃分區(qū)域并確定點(diǎn)集

利用錨節(jié)點(diǎn)的GPS坐標(biāo)，對雷場區(qū)域中的各錨節(jié)點(diǎn)進(jìn)行劃分，得到多個節(jié)點(diǎn)點(diǎn)集。該步驟實(shí)質(zhì)為一個聚類過程，借鑒K-均值聚類算法并結(jié)合實(shí)際情況完成對錨節(jié)點(diǎn)的聚類。已知雷場區(qū)域大小，雷場區(qū)域中存在m個錨節(jié)點(diǎn)（其中m＞9，若m≤9，直接尋找凸多邊形），根據(jù)錨節(jié)點(diǎn)的GPS坐標(biāo)獲得錨節(jié)點(diǎn)的分布情況，劃分過程如下：

1）為保證劃分的每個區(qū)域中存在6個左右的錨節(jié)點(diǎn)，將初始劃分區(qū)域數(shù)量設(shè)為n=m/6。

2）將雷場區(qū)域平均劃分為n個區(qū)域，得到各區(qū)域中分布的錨節(jié)點(diǎn)，選取與各區(qū)域錨節(jié)點(diǎn)平均位置距離最近的錨節(jié)點(diǎn)作為聚類中心；若該區(qū)域中無錨節(jié)點(diǎn)，則將該區(qū)域歸入鄰近區(qū)域；最終得到n個聚類中心。

3）利用GPS坐標(biāo)計算各錨節(jié)點(diǎn)到各聚類中心的距離，若某個錨節(jié)點(diǎn)距離第i個聚類中心更近，則將其歸入i中心的點(diǎn)集中；若存在聚類中心的點(diǎn)集為空，則淘汰該聚類中心，將其作為錨節(jié)點(diǎn)參與劃分；最終得到n個點(diǎn)集。

4）分別計算各點(diǎn)集中的平均位置，選取與平均位置距離最近的點(diǎn)作為新的聚類中心。

5）遞歸執(zhí)行步驟3）～步驟4），直到聚類中心不再變化；各聚類中心的點(diǎn)集即為得到的點(diǎn)集。

雷場示意圖及聚類過程如圖1所示，雷場中存在22個錨節(jié)點(diǎn)，將雷場分為4個區(qū)域；得到4個初始聚類中心，圖1中的星形即為各聚類中心；執(zhí)行步驟3），淘汰聚類中心4，區(qū)域4并入?yún)^(qū)域3；執(zhí)行算法，最終得到的聚類結(jié)果如圖1所示，得到3個點(diǎn)集。

圖1 雷場示意圖及聚類過程

1.2 尋找凸多邊形

分別在每個點(diǎn)集中遞歸尋找m個錨節(jié)點(diǎn)（其中m≥3），各錨節(jié)點(diǎn)可以組成一個凸多邊形。

以點(diǎn)集M中最靠近中心位置的點(diǎn)作為原點(diǎn)O，建立高斯坐標(biāo)系，將剩余點(diǎn)分配到各象限中，將集合中M的點(diǎn)按照與原點(diǎn)的距離遠(yuǎn)近重新排序。

推理得到，已知凸多邊形N，其邊數(shù)為n，判斷某一點(diǎn)B能否與其組成凸n+1邊形的條件為：

1）B點(diǎn)不在多邊形N內(nèi)；

2）多邊形各相鄰邊反向延伸得到n個區(qū)域，B點(diǎn)不在這些區(qū)域內(nèi)。

以四邊形為例，如圖2所示，若點(diǎn)B不在四邊形 N 內(nèi)，且不在區(qū)域 P1、P2、P3、P4內(nèi)，則 B 可與四邊形N組成凸五邊形。

圖2 四邊形與點(diǎn)B組成凸五邊形條件示意圖

采用直接法尋找凸多邊形，如圖3所示，步驟如下：

圖3 直接法尋找凸多邊形

1）以原點(diǎn)O為圓心，將集合M中與原點(diǎn)距離小于0.2 m的節(jié)點(diǎn)剔除，遍歷尋找M中與原點(diǎn)距離最近的點(diǎn)A1。

2）在集合M中尋找點(diǎn)A2，使得A2與A1、O點(diǎn)可以組成三角形。

3）遍歷尋找A3點(diǎn)，A3可與找到的點(diǎn)組成凸多邊形，過程中對不滿足條件的點(diǎn)進(jìn)行剔除。

4）遞歸執(zhí)行步驟3），直至完成遍歷。

1.3 頂點(diǎn)坐標(biāo)修正

得到凸多邊形后，利用節(jié)點(diǎn)坐標(biāo)修正模型對各頂點(diǎn)進(jìn)行修正，得到修正坐標(biāo)。

1.4 其余節(jié)點(diǎn)坐標(biāo)修正

分別利用各點(diǎn)集中的凸多邊形頂點(diǎn)坐標(biāo)，通過三邊定位方法計算各點(diǎn)集中其余錨節(jié)點(diǎn)坐標(biāo)，再利用測距結(jié)合三邊定位方法得到各普通節(jié)點(diǎn)坐標(biāo)。

2 節(jié)點(diǎn)坐標(biāo)修正模型

從某一點(diǎn)集中獲取凸多邊形后，利用UWB測距值結(jié)合GPS坐標(biāo)對頂點(diǎn)坐標(biāo)進(jìn)行修正。

2.1 模型建立

假設(shè)獲取的凸多邊形為M，其邊數(shù)為k，已知M中k個頂點(diǎn)的GPS坐標(biāo)，利用GPS坐標(biāo)可以確定M的形狀和位置；利用UWB測距可以得到各頂點(diǎn)間兩兩距離。通過三角形穩(wěn)定性原理，在得到了多邊形M的所有邊和對角線的精準(zhǔn)長度后，可以確定一個新的多邊形N。由于UWB的精度遠(yuǎn)高于GPS，故多邊形N的形狀比M更符合各頂點(diǎn)的實(shí)際分布形狀。當(dāng)多邊形邊數(shù)為6時的M和N的示意圖，如圖4所示。

圖4 六邊形示意圖

已知多邊形M中各頂點(diǎn)坐標(biāo)，得到M的中心O，將多邊形N的中心與O重合，M不動，以O(shè)為圓心旋轉(zhuǎn)多邊形N，當(dāng)N的各頂點(diǎn)距離與M的各頂點(diǎn)的距離和最小時，多邊形N的各頂點(diǎn)坐標(biāo)即為修正后的坐標(biāo)。當(dāng)多邊形邊數(shù)為6時的修正示意圖如圖5所示，圖中要求（AA1+BB1+CC1+DD1+EE1+FF1）最小。

算法轉(zhuǎn)化為最優(yōu)化問題［4］，假設(shè)多邊形邊數(shù)為k，則 k 邊形 M 中各頂點(diǎn)的坐標(biāo)為（α1，β1），…，（αk，βk），k 邊形 N 中各頂點(diǎn)的坐標(biāo)為（x1，y1），…，（xk，yk），約束條件如下：

圖5 修正示意圖

1）k邊形N和k邊形M的中心O重合；

2）k邊形N各邊距離和對角線距離dij（其中i≠j）已知；

求k邊形N各頂點(diǎn)與k邊形M各頂點(diǎn)距離和最小，得到目標(biāo)函數(shù)如下：

最優(yōu)化問題通常采用拉格朗日乘子法將帶約束條件的最優(yōu)化問題轉(zhuǎn)化為解方程組問題，當(dāng)方程組維度超過8時，求得最優(yōu)解的方法較為復(fù)雜且費(fèi)時［5］，模型通過對多邊形進(jìn)行順時針旋轉(zhuǎn)，將多維問題優(yōu)化為一維問題。

2.2 模型優(yōu)化

以k邊形M的中心O為原點(diǎn)建立高斯坐標(biāo)系，k邊形N的中心與O重合，已知M中頂點(diǎn)坐標(biāo)分別為（α1，β1），…，（αk，βk），N 中各邊長度和各對角線長度dij（其中i＝1，…k；j=1，…k；i≠j），推導(dǎo)得出原點(diǎn)O與某一頂點(diǎn)長度為：

其中，j≠i，m≠n≠i。

以五邊形為例，O與A1之間的距離為：

將N中的頂點(diǎn)A1的橫坐標(biāo)設(shè)為X1，通過式（2）得到，結(jié)合X1得到A1的縱坐標(biāo)Y1，進(jìn)而得到k邊形N中其余各頂點(diǎn)的初始坐標(biāo)。

以O(shè)為圓心，k邊形N以順時針進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)角度為θ，旋轉(zhuǎn)過程中k邊形N各頂點(diǎn)坐標(biāo)為：

其中，i=1，…k；Xj≠Yj為各項點(diǎn)初始坐標(biāo)。

旋轉(zhuǎn)模型示意圖如圖6所示。

圖6 旋轉(zhuǎn)模型示意圖

通過旋轉(zhuǎn)使得N的各頂點(diǎn)距離與M的各頂點(diǎn)的距離和最小，結(jié)合式（3）得到目標(biāo)函數(shù)為：

其中，Xj，Yj為各項點(diǎn)初始坐標(biāo)。

模型最終轉(zhuǎn)化為求單變量θ使f（θ）值最小的問題，通過極值法得到θ值后，將θ帶入式（3）中，得到各頂點(diǎn)的修正坐標(biāo)。

3 算法實(shí)驗測試

實(shí)驗選擇90*90 m的區(qū)域作為雷場區(qū)域，選取總共40顆活動雷，其中錨節(jié)點(diǎn)15個，其余為普通節(jié)點(diǎn)，各活動雷在雷場區(qū)域隨機(jī)分布，節(jié)點(diǎn)實(shí)際分布示意圖如圖7所示。其中，用圓圈表示的節(jié)點(diǎn)為錨節(jié)點(diǎn)，雪花表示的節(jié)點(diǎn)為普通節(jié)點(diǎn)。

圖7 節(jié)點(diǎn)分布圖

對區(qū)域所有節(jié)點(diǎn)執(zhí)行修正算法，將雷場區(qū)域劃分為圖8中虛線分割的3個區(qū)域，每個區(qū)域中的節(jié)點(diǎn)組成一個點(diǎn)集，各點(diǎn)集中分別尋找出六邊形、四邊形和三角形。

分別對3個多邊形執(zhí)行坐標(biāo)修正，以六邊形為例，各頂點(diǎn)的修正結(jié)果如圖7所示。圖中短劃線組成的六邊形的6個頂點(diǎn)為錨節(jié)點(diǎn)實(shí)際分布位置，點(diǎn)虛線組成的六邊形的6個頂點(diǎn)為錨節(jié)點(diǎn)利用GPS得到的坐標(biāo)分布位置，實(shí)線組成的六邊形的6個頂點(diǎn)為經(jīng)過校準(zhǔn)后的坐標(biāo)分布位置。

圖8 校準(zhǔn)結(jié)果

最終修正過后的所有節(jié)點(diǎn)態(tài)勢分布圖與實(shí)際分布圖對比，如圖9所示。

圖9 修正后的態(tài)勢分布與實(shí)際分布對比

4 結(jié)論

從實(shí)驗結(jié)果來看，利用GPS得到的坐標(biāo)與錨節(jié)點(diǎn)實(shí)際分布存在較大偏差，通過節(jié)點(diǎn)修正模型以提高錨節(jié)點(diǎn)坐標(biāo)與實(shí)際分布的一致性，降低各節(jié)點(diǎn)之間坐標(biāo)的相對誤差。在實(shí)際應(yīng)用中，算法還有很多地方需要改善，如穩(wěn)定性方面需要進(jìn)一步提高。