基于雙焦點離心測距的移動無線傳感網定位算法

趙麗芬，申 毅，田 波，王 中

(1.銅仁學院 大數據學院，貴州 銅仁 554300；2.東南大學 信息科學與工程學院，江蘇 南京 211189)

0 引 言

就移動無線傳感網(mobile wireless sensor network，M-WSN)定位技術而言，可分為直接測距和間接測距兩種定位方法[1-4]。直接測距方法在實踐中一般利用多普勒位移來直接計算定位節點與基準節點的距離及角度，從而獲取節點的定位坐標[5]。但是，直接測距方法需要頻繁進行數據定位及頻率測量。間接測序方法主要借助DV-Hop機制來實現定位，但也存在因頻繁進行鄰域迭代而出現精度不高的問題。

綜合直接測距和間接測距方法的特點，當前國內外研究者提出了一系列的解決方法。如Li等[6]引入信號直測方法來改善DV-Hop算法的錨節點定位精度，特別是采取迭代模式來進一步優化待測角度，可將待定位節點坐標精度提升至1跳鄰域內。但是，該方法在節點移動速度較高時，需要頻繁針對節點距離進行測量，使得節點能量消耗較高。Zou等[7]提出通過設置兩組正交錨節點來實時捕捉節點坐標。然而，該算法的定位過程中雙源節點具有定位對稱效應，定位坐標存在嚴重的漂移現象。Jeba等[8]通過sink節點控制來建立錨節點粒子群移動模型，使用周期遞歸方法來消除移動過程中的錨節點移動性過高帶來的頻率及坐標抖動問題。然而，該算法存在控制機制復雜所帶來的能量消耗較快等難題，運行過程中穩定性較差。

為此，本文提出了一種基于雙焦點離心測距機制的移動傳感網高效定位算法。該算法將多跳定位拓撲鏈路視為弧線鏈路，通過優化最小跳數及定位拓撲獲取定位橢圓橫向半徑和縱向半徑并計算離心率，達到精密化圓周弧線的目的。借助橢圓縱半徑跳數優化方法來設計動態測距模式，擴大定位橢圓的覆蓋范圍，增強對待定位節點的覆蓋能力。最后，采用NS2仿真實驗環境，驗證了本文算法的性能。

1 網絡模型概述

考慮網絡節點分布區域為矩形，面積為m×nm2，區域內按隨機模式來分布A個傳感節點與B個錨節點，如圖1所示。則網絡net可用如下模型表示

net=G(Ai,Bj,E)

(1)

式中：Ai表示傳感節點集，Bj表示錨節點集，E表示節點間的拓撲鏈接鏈路。

圖1 傳感節點分布

若第i個節點與第j個節點之間拓撲距離小于網絡節點最低覆蓋距離l，說明節點間可以建立數據傳輸鏈路。由于各節點在運行過程中覆蓋能力可能存在差異，使得覆蓋距離難以在網絡中進行統一，估計各傳感節點坐標時均需要依賴于式(1)所示的拓撲鏈接鏈路，若節點處于錨節點覆蓋之外，則將會出現失聯現象。因此，對節點進行定位過程中需要關注失聯節點，若某個節點在通信過程中發現自己成為失聯節點，需要使用sink節點對該節點進行能量補充，以便擴大覆蓋范圍，從而降低定位失效現象。

一般而言，無論直接測距算法還是間接測距算法均需要使用圖1所示的錨節點進行定位，其中錨節點位置已知，待定位節點與錨節點進行數據交互，以便利用待定位節點與錨節點之間的鏈路估計相應的拓撲跳數，從而實現定位。

圖2描述了間接測距算法的實現過程。待定位節點獲取網絡中錨節點信息，當待定位節點與3個及以上錨節點同時建立起傳輸鏈路。錨節點B1與錨節點B2、錨節點B3之間距離分別為10 m、20 m，相應跳數分別為3跳和6跳，因此錨節點B1可獲取平均覆蓋距離l1

l1=(10+20)/(3+6)=3.33 m

(2)

圖2 間接測距

當待定位節點i與錨節點B1與錨節點B2、錨節點B3之間的拓撲跳數為1、2、4時，則該節點與錨節點B1與錨節點B2、錨節點B3之間的距離d(i,B1)、d(i,B2)、d(i,B3)滿足

d(i,B1)=1×3.33=3.33 m

(3)

d(i,B2)=2×3.33=6.66 m

(4)

d(i,B3)=4×3.33=13.32 m

(5)

由式(2)～式(5)及圖2可知，間接測距算法需要首先估計錨節點的平均覆蓋距離，并利用平均覆蓋距離估計各錨節點與待定位節點之間的拓撲長度?？紤]到待定位節點覆蓋能力與錨節點相比存在一定的差異，因此需要針對估計過程進行改進，以便提高定位準確度，修正估計過程中存在的誤差。對拓撲路徑進行估計時，應考慮多跳情況下路徑析構過程中存在的裁彎取直現象，用弧度模型替代直線距離，從而更好匹配實際距離，提高算法的對多跳環境的適應能力。

2 本文算法設計

由上文可知，間接測距過程將錨節點與待定位節點間距離看作直線拓撲，由于傳輸鏈路實際存在一定的弧度，采用直線拓撲測距需要將鏈路弧度進行裁彎取直，因此定位過程存在一定的誤差，使得算法定位精度不理想。為此，本文設計了基于雙焦點離心測距機制的移動傳感網高效定位算法(efficient positioning scheme for mobile sensor networks based on double focus centrifugal ranging algorithm)。該算法由兩部分構成：①基于弧度路徑析構的節點橢圓定位。通過采用弧線估測進行定位拓撲優化，結合錨節點來增加定位精度。②基于橢圓縱半徑跳數優化的動態測距。主要針對移動無線傳感網拓撲變動頻繁的特點進一步提升橢圓覆蓋范圍，降低定位漂移現象，從而提高算法定位精度。

2.1 基于弧度路徑析構的節點橢圓定位

由圖2可知，間接測量方法需要計算最小跳數并進行距離估計，但距離估計過程均依賴直線模型，使其具有較大的定位誤差。此外，傳統的間接測距方法在最小跳數計算過程中也存在一定的弊端，特別是采用待定位節點與錨節點交互方式進行直接通信，會導致式(1)所示的拓撲鏈接鏈路E難以建立。因此，本文對最小跳數及距離估計過程進行優化，設計了基于弧度路徑析構的橢圓定位方法。

(1)最小跳數的獲取

首先，錨節點向sink節點進行數據報文發送，將與各節點間的跳數及自身ID通過sink節點進行全網廣播。網絡中除錨節點外的傳感節點(含待定位節點)在接收到sink節點發送的數據報文后，記錄錨節點的ID并將跳數加1，如圖3所示。待定位節點接收到各錨節點發送的數據報文后，可獲取各錨節點的ID及相應跳數，由于一定傳輸周期內待定位節點可能同時接收到若干個錨節點所發送的分組報文，因此可從這些分組報文中過濾出最小跳數對應的錨節點，記最小跳數Hop(min)如下

圖3 最小跳數的獲取

(6)

式中：Bn表示第n個錨節點，hop表示分組報文中所對應的跳數。

(2)確定橢圓定位范圍

考慮到網絡中待定位節點與各錨節點間拓撲鏈路存在多跳特性，由于待定位節點與錨節點間鏈路可能存在斷裂現象，如圖4所示。為保證鏈路的可用性，對鏈路中通信能力較強的節點進行能量補充，擴大覆蓋范圍，以便鏈路保持暢通狀態如圖5所示。

圖4 拓撲鏈路圖(斷裂狀態)

圖5 拓撲鏈路圖(覆蓋范圍擴大)

節點覆蓋區域擴大后，顯然鏈路整體長度與錨節點-待定位節點直線距離存在誤差，如圖5所示。為了精確獲取待定位節點與錨節點間距離，須對鏈路整體長度進行優化。

首先，建立待定位節點與錨節點間的弧度路徑，如圖6所示，且該弧度看作是一個縱半徑2x和橫半徑2y的定位橢圓，并按如下模型獲取定位橢圓的離心率ε

(7)

據此，橢圓定位范圍得以確立，如圖6所示。

圖6 橢圓定位

2.2 基于橢圓縱半徑跳數優化的動態測距

橢圓定位范圍確立后，由于橢圓存在兩個焦點，因此按式(7)計算的橢圓離心率，即可按圖6對橢圓覆蓋范圍進行精確劃分。由于定位橢圓的縱半徑2x和橫半徑2y可能存在變動，因此需要考慮到路徑變化，以實現動態測距，特別是盡量縮減定位橢圓的縱半徑2x，以便能夠對定位拓撲進行動態化評估，以提升測距結果的精度。

(8)

式中：hop(Bi,Ci)表示待定位節點Ci與錨節點Bi間的跳數，Mj表示待定位節點Ci與錨節點Bi間的中間節點。

由式(8)可知，待定位節點Ci與錨節點Bi間鏈路整體長度G可由如下公式獲取

G=G×hop(Bi,Ci)

(9)

隨后，利用圖6所示的橢圓定位方法，結合式(9)及式(7)，即可計算待定位節點Ci與錨節點Bi間的距離P

P=G/πx(1-ε2/4)

(10)

式中：ε為式(7)確定的離心率。

聯立式(7)和式(10)，將待定位節點Ci與錨節點Bi間的跳數hop(Bi,Ci)替換式(7)中的2y，令自變量為x，則定位橢圓的縱半徑方程如下

12πx2+πhop(Bi,Ci)2=G

(11)

式中：G為待定位節點Ci與錨節點Bi間鏈路整體長度。

再根據式(11)來求取x的最小值為

minx=G/2

(12)

通過式(12)獲取定位橢圓的橫半徑x后，令(x,y)表示待定位節點的坐標，(xj,yj)表示錨節點坐標，并設待定位節點坐標與各錨節點坐標間距離為dj。則可建立定位方程Q

(13)

再對式(13)進行系數分離，可得

(14)

(15)

(16)

聯立式(14)～式(16)可得

TZ=J

(17)

顯然，Z滿足

Z=(TTU)-1TJ

(18)

式中：U表示矩陣轉秩。

通過式(18)即可精確獲取待定位節點坐標(x,y)。由于待定位節點與錨節點間鏈路整體長度可通過式(9)來獲取，其相應的最小跳數可通過式(8)進行動態評估，結合定位橢圓弧形邊與待定位節點坐標(x,y)之間的對應關系，即可在定位橢圓上快速通過路徑回溯待定位節點，從而達到動態測距的目的。

3 本文算法的復雜度分析

本文算法主要由基于弧度路徑析構的節點橢圓定位和基于橢圓縱半徑跳數優化的動態測距兩部分構成。不妨設網絡中傳感節點數量為m，錨節點個數為n。在基于弧度路徑析構的節點橢圓定位過程中，所提算法首先需要通過逐個過濾傳感節計算獲取最小跳數，并通過分組報文中過濾出最小跳數對應的錨節點，其復雜度為o(m)。基于橢圓縱半徑跳數優化的動態測距機制在獲取最小跳數的基礎上，按式(13)建立定位方程組，方程組建立過程中將通過錨節點逐個建立定位方程，由于錨節點個數為n，因此復雜度為o(n)。因此，綜合上述2個過程，本文算法的復雜度為o(m)+o(n)。

為了突出所提算法的優勢，將文獻[14]和文獻[15]視為對照組。文獻[14]算法在遍歷網絡錨節點的基礎上，逐項計算各節點間的平均跳數，該過程的復雜度為o(m)，隨后需要對符合要求的信標節點進行迭代，迭代次數為n，考慮到匹配信標節點的過程需要遍歷全部傳感節點，此過程復雜度為o(m×n)，因此文獻[14]算法復雜度為o(m)+o(m×n)，顯然要高于本文所提算法。文獻[15]通過構建罰函數模型來記錄定位過程中性能較差節點坐標，記錄過程中均遍歷全部傳感節點并得到學習樣本，隨后將動態學習該樣本，得到樣本獲取過程對應的算法復雜度為o(m2)，學習過程按照水波算法進行迭代，迭代次數為n，該過程復雜度為o(m×n)。因此，文獻[15]算法復雜度為o(m2)+o(m×n)?？紤]到傳感網絡中錨節點個數一般要少于傳感節點個數，因此，文獻[15]算法的算法復雜度亦要遠遠高于本文算法。綜上所述，本文算法在復雜度方面具有一定的優勢，具有定位過程較為簡單的特點，能夠以較快的速度獲取待定位節點的坐標。

4 仿真實驗

為便于驗證本文算法性能，采取NS2平臺(network simulator version 2)進行仿真實驗。實驗區域為矩形區域，面積為1000×1000 m2。由于移動無線傳感網具有拓撲變動較快的特性，針對待定位節點均將重復進行10次定位過程，將10次定位結束后獲取的坐標平均值視為標準結果，以便降低網絡拓撲頻繁變動所造成的定位誤差。傳感節點制式采用5G移動通信模型，使用64ASP調制方式，其余實驗參數見表1。另外，為了突出所提算法的先進性，將當前移動無線傳感網領域中常用的基于跳數修正和改進粒子群優化DV-Hop定位算法[14](DV-Hop localization algorithm based on hop number modification and improved particle swarm optimization，HNM-IPS算法)、基于罰函數與水波優化的WSN定位算法[15](WSN location algorithm based on penalty function and water wave optimization，PF-WWO算法)和基于三維離散混沌映射的無線傳感器網絡定位算法[16](A WSN positioning algorithm based on 3D discrete chaotic mapping，3D-DCM算法)作為對照組。

表1 仿真參數

實驗開始后，通過統計各算法的定位精度及定位次數來客觀評價。定位精度測試過程中，考慮到多個待定位節點坐標記錄在不同周期內存在一定的變動，因此將待定位節點設置為靜止狀態，sink節點作為測量節點，沿矩形分布區域周圍以10 m/s的速度移動并捕捉待定位節點坐標，最終形成定位精度仿真記錄圖，其中錨節點保持靜止狀態。定位次數測試過程中，sink節點和錨節點均保持靜止，待定位節點按不同速度進行游走，達到某定位精度后即記錄其定位次數。

4.1 定位精度測試

圖7(a)為待定位節點實際分布，圖7(b)～圖7(d)為本文算法、HNM-IPS算法、PF-WWO算法在進行10次定位后所測的坐標分布結果。由圖可知，本文算法所測坐標分布與待定位節點的實際分布契合度最高，而HNM-IPS算法、PF-WWO算法的所測坐標分布均與待定位節點實際分布存在較大的偏離。這是由于本文算法設計了橢圓定位機制，將定位過程中的直線跳距進行橢圓曲線化處理，可將直線架構拓撲修正為精度更高的弧度化曲線拓撲，特別是在處理過程中基于離心模式對橢圓弧邊進行精度修正，可有效平滑待定位節點與錨節點間所測拓撲鏈路，降低測序過程中因弧度誤差而導致定位漂移現象的發生概率，因此具有較高的定位精度。HNM-IPS算法主要通過計算錨節點之間平均拓撲定位跳數，并利用該跳數修正定位過程中出現的鄰域裁定誤差，沒有考慮所測距離存在的直線拓撲測距誤差，雖然采用粒子群方法來修正進行定位誤差，但難以消除多跳環境中的測距誤差，特別是拓撲更迭頻繁時期誤差將更為明顯，因此其定位精度較低。PF-WWO算法采用動態學習策略來優化定位過程，并設計罰函數來記錄定位過程中性能較差節點坐標，從而獲取信號強度較高的錨節點，然而該算法亦對移動無線傳感環境存在的拓撲變動考慮不夠，迭代過程中需要預設次數，難以對節點坐標進行精確匹配，因此所測鏈路在拓撲變動頻繁時存在較高的劇烈變動概率，導致直線拓撲與實際所測鏈路出現匹配困難的問題，因此定位精度難以進一步提升，使得該算法定位精度亦要低于本文方法。3D-DCM算法主要采取最小二乘估計模式估測坐標，從通信半徑及拓撲結構兩個方面優化節點定位精度，且構造三維離散混沌映射，將混沌優化算法引入到定位誤差精度提高之中，一定程度上解決了節點移動過程中出現的定位漂移現象。然而，該算法對節點運動速度方面限制性較高，特別是在三維離散混沌映射過程中嚴重依賴線性映射方法，使其僅能針對已定路徑上的節點進行精度估計，因此，在拓撲出現變動時將因映射失效而導致精度會出現較大幅度下降，降低了節點坐標匹配程度。

4.2 定位次數測試

圖8為本文算法與HNM-IPS算法、PF-WWO算法在達成相同定位精度時所花費的定位次數的測試結果，其中，定位誤差數值越低說明定位精度也就越高。由圖可知，所提算法在達成相同定位精度條件下所耗費的定位次數更短，說明本文算法具有很強的定位能力，對移動無線傳感網高拓撲流動特性適應能力更強。這是由于本文算法在弧度路徑析構的基礎上，針對定位橢圓存在的半徑抖動情形，設計了基于橢圓縱半徑跳數優化的動態測距機制，可迅速捕捉待定位節點，算法運行過程中僅需要針對錨節點與傳感節點進行遍歷并解析最小跳數，無需采用粒子群模式進行多次迭代，因此具有定位次數較低的特點。HNM-IPS算法采用粒子群模式逐次迭代定位坐標，迭代次數與定位精度具有顯著的正相關特性，當定位精度難以滿足需求時需要頻繁迭代坐標，因此達到相同定位精度所耗次數較高。PF-WWO算法所提罰函數機制雖然能夠增強待定位節點在定位過程中對錨節點的搜尋能力，然而由于該算法并未對移動無線傳感環境中存在的多跳路徑進行弧形優化，因此對路徑適應能力較低，使得達到相同定位精度所耗的次數要高于本文算法。3D-DCM算法從通信半徑及拓撲結構兩個方面對節點定位精度進行提升，并采取最小二乘估計模式對坐標進行進一步優化。然而，該算法進行定位過程中需要采集的樣本數較多，在拓撲結構變動頻繁的情況下樣本精確度易出現下降，此外，該算法對網絡資源進行優化時單純依賴于能量因素，頻繁進行映射過程中容易導致定位節點出現能量受限，致使出現重定位現象較為突出，使得在定位次數上要高于本文算法。

圖7 不同算法的定位精度

圖8 定位次數

5 結束語

為解決移動傳感網在拓撲流動性較高情形下存在的定位精度不高、數據傳輸能力較差、抗干擾性較弱等不足，提出了一種基于雙焦點離心測距機制的移動傳感網高效定位算法。通過設計橢圓定位機制，對直線拓撲進行橢圓弧形優化處理，提高測距過程中的首次定位精度。隨后，通過橢圓覆蓋范圍來應對網絡拓撲變動頻繁的情形，從而解決因拓撲測距失真而導致定位精度下降的問題，提高節點頻繁移動情形下的定位效率。

下一步，將針對本文算法對立體傳感網絡適應性不足的問題，擬引入超流體拓撲評估方式，將定位橢圓擴充為基于三維曲面機制的立體定位橢球，以便能夠適用于諸如無人機、戰術數據鏈組網等實際應用場景，進一步提高本文算法的部署價值。