融合正余弦優化與跳距優化的DV-Hop定位算法*

張 晶，賀媛媛

(1.昆明理工大學信息工程與自動化學院，云南 昆明 650500；2.云南梟潤科技服務有限公司，云南 昆明 650500；3.昆明理工大學云南省人工智能重點實驗室，云南 昆明 650500；4.昆明理工大學云南省計算機技術應用重點實驗室，云南 昆明 650500)

1 引言

無線傳感器網絡WSN(Wireless Sensor Network)是由無規律散落的節點組成的不規則監測區域，大多應用于動態追蹤、環境監測和森林火災預警等多種學科交叉的相關領域[1]。在整個網絡區域中，各個節點采用無線通信技術進行數據處理和傳輸，實現節點之間的信息交互并達到對目標空間范圍的監測。

隨著無線傳感器網絡定位研究的不斷深入，節點不僅需要進行數據收集，更需要精確獲知節點的位置信息。因此，準確獲取事件發生的位置是無線傳感器網絡最主要的功能之一，未知節點的定位研究具有不可或缺的重要性。但是，在實際環境中，節點部署[2]不均勻、復雜的傳播環境等相關問題隨時存在，因此對定位算法的性能提出了更高的要求。

在當前規模化通信網絡中，存在隨身配置GPS的錨節點和無法明確位置的未知節點，但由于高輸入高輸出的成本與能耗，相比于未知節點而言，錨節點的數量[3]非常有限，因此無法將錨節點大量應用于功耗小、成本低的網絡中。

目前的定位算法根據節點是否需要實際測量其之間的距離分為2種類別：一種是需要給傳感器附加額外裝置[4]來獲取節點之間的間距，這種算法被稱為測距算法，其定位結果相對來說更精準。但是，由于需要添加額外[5]的硬件設備，使得算法的部署對節點成本的要求較高,不適合大型區域的監測[6]。另一種類別是不需要添加任何其他硬件設備，只需要網絡之間能夠通信即可的非測距算法[7]。這種算法定位精度低，但由于其相對測距算法而言節點造價低，適合大型傳感網絡監測，成為近些年研究的熱點。本文要探討的就是無需測距算法中的典型算法DV-Hop。

DV-Hop定位算法是一種較為傳統的傳感器節點定位算法，該算法的測距原理為：首先由網絡中各錨節點通過洪泛方式廣播自身路由信息，直至其通信范圍內各未知節點均獲取自身到錨節點的最小跳數信息[8]；之后再得出平均跳距信息，將二者相乘得到兩點之間的距離，再用極大似然或三邊測量估算目標節點的位置。但是，該算法存在一個缺陷，即當最小跳數大于1跳時，由于錨節點的平均跳距本身在計算的時候就存在誤差，所以導致未知和已知節點之間的距離存在更大的誤差。

針對DV-Hop定位算法中跳距計算不精確以及最小二乘法求解不能達到最優無偏狀態導致對無線傳感器網絡中未知節點定位不準確，本文提出了一種融合正余弦優化與跳距優化的DV-Hop定位算法。基本思想是：首先選取每個未知節點周圍所有錨節點中平均跳距最小的錨節點作為最優化錨節點；然后選取其余任一錨節點與未知節點構成三角形，將最優化錨節點到未知節點的邊作為三角形中的最優化邊；其次利用余弦定理計算其余錨節點到未知節點的距離達到優化跳距的目的；最后利用正余弦優化算法改進最小二乘法，利用正余弦函數的波動性尋找未知節點的最優位置。

2 DV-Hop定位算法及改進算法

2.1 DV-Hop定位算法

傳統的DV-Hop定位算法依賴于網絡連通性，首先由網絡中各錨節點通過洪泛方式廣播自身路由信息，直至其通信范圍內各未知節點均獲取自身到錨節點的最小跳數信息；之后再得出平均跳距，將二者相乘得到兩點之間的距離，再用極大似然或三邊測量估算目標節點的位置。DV-Hop定位算法步驟如下所示：

(1)獲取最小跳數。

整個網絡中的錨節點通過洪泛的方式廣播自己的分組信息，每個未知節點會收到來自多個錨節點廣播的數據包，數據包Xdatai包含第i個(1≤i≤n)錨節點的ID、自身到未知節點的跳數Hop及其位置坐標，如式(1)所示，多個數據包組成一個更大的集合{Xdata1,Xdata2,…,Xdatan}。

Xdatai={ID,Hop,(xi,yi)}，i=1,2,…,n

(1)

其中，Hop初始值為0。當接收方接收錨節點信息時，優先選擇相比之下較小跳數的分組，忽略其他分組，依次繼續轉發并將跳數值按規律加1。

(2)記錄未知節點與錨節點的跳距值。

將所有錨節點的位置坐標對應相減再開平方后的總和與所有錨節點的跳數之和相除得到如式(2)所示的平均跳距，再將錨節點到未知節點的跳數與平均跳距相乘得到跳距值，如式(3)所示：

(2)

di=HopDistancei×hopi

(3)

(3)估計目標節點位置。

當錨節點數大于或等于3時，使用最小二乘法估計目標節點位置，計算方法如式(4)～式(9)所示：

(4)

其中，(x,y)為未知節點位置坐標，所有錨節點(x1,y1),…,(xn,yn)到未知節點的跳距用d1，d2，…，dn表示。

然后用前n-1個方程減去最后一個方程，得到如式(5)所示的方程組：

(5)

再將式(5)進行拆分，轉化為矩陣A、B和X，得到AX=B的形式，如式(6)～式(9)所示：

(6)

(7)

(8)

(9)

2.2 DV-Hop改進算法

針對傳統DV-Hop定位算法存在的不足，文獻[9]提出了一種增強DV-Hop定位算法，通過加權系數[9]設定閾值賦予錨節點權重值的方式降低定位誤差。但是，如果錨節點與未知節點間存在多跳時，距離較遠會導致錨節點被忽略，通過加權系數也無法降低誤差值。文獻[10]提出一種基于修正平均跳數的DV-Hop定位算法，該算法在修正分數跳數和錨節點的平均跳距得到的跳距值的基礎上使用改進后的差分進化算法DE(Differential Evolution)估計目標節點位置。但是，DE算法類似于遺傳算法，需要的參數較多，增加了算法計算復雜度，同時受到縮放因子和交叉概率的制約，收斂速度變慢，不利于收斂到全局最優[10]。文獻[11]在求最值的過程中利用梯度算法進行求解,通過多邊定位獲取目標節點估計位置，將該估計位置作為L-M(Levenberg-Marquard)優化算法的初始值，之后進行迭代求精,但受到相關函數復雜性和參數個數的條件限制，定位精度也會變低[11]。文獻[12]提出的優化算法是設置跳數閾值，根據錨節點的位置信息修正跳距，采用質心算法和最小二乘法[12]估計位置坐標。文獻[13]提出一種基于跳距重估算法，該算法首先對跳距進行評估，然后通過計算修正系數來修正最小跳數，最后使用最小二乘法估計節點位置[13]。但是，現有的改進算法并沒有很好地修正跳距值和降低定位誤差，因此本文在修正跳距以及最小二乘法求解上進行優化。

3 本文改進算法

上述改進的DV-Hop定位算法雖然在一定程度上能夠提高定位精度，但在現實情況中，錨節點和未知節點之間的距離仍然存在誤差。在最小二乘法中，未知節點與各錨節點間距離的計算方法均會產生一個誤差值，所有誤差值之和構成該未知節點定位誤差值，結合函數求導規則計算得出該未知節點定位誤差極小值，而并非其最小值，從而使得該計算結果陷入局部最優，導致節點定位[14]精度低。為此，本文提出一種融合正余弦優化與跳距優化的DV-Hop定位算法。其基本思想是：首先選取每個未知節點周圍所有錨節點中平均跳距最小的錨節點作為最優化錨節點；然后選取其余任一錨節點與未知節點構成三角形，將最優化錨節點到未知節點的邊作為三角形中的最優化邊；其次利用余弦定理計算其余錨節點到未知節點的距離達到優化跳距的目的；最后利用正余弦優化算法改進最小二乘法，利用正余弦函數的波動性尋找未知節點的最優位置。正余弦優化算法僅需設定1個參數，無需額外調參，從而降低了算法計算復雜度，且內置隨機因子可靈活控制粒子的移動范圍，避免使其陷入局部最優。相比其他改進算法而言，該算法有效提高了定位精度。

3.1 選取最優化錨節點

由于未知節點到錨節點之間的距離存在誤差，因此本文提出最優化錨節點的概念。最優化錨節點為每個未知節點到錨節點的距離[15]能夠達到最優且使得兩點之間的距離誤差最小的錨節點，即平均跳距最小的錨節點。由于每個未知節點最近的錨節點的跳距信息是通過所有錨節點計算出來的，所以最近錨節點的平均跳距信息有可能不是最小平均跳距，因此選取最優化錨節點的優勢如下：

如圖1所示，A是未知節點，L1,L2和L3是錨節點，由DV-Hop算法可知，L1L2和L1L3長度分別為40 m和100 m，最小跳數分別為2和5，根據式(2)，得L1,L2和L3的平均跳距分別為20 m,24 m和22.5 m，AL1,AL2和AL3的長度分別為：3*20=60 m，2*24=48 m，3*22.5=67.5 m。按照選取最近的錨節點的平均跳距來優化其他錨節點與未知節點的距離，得到如下結果：根據A到各個錨節點的距離可知，L2是最近的錨節點，用L2到A的距離作為A與其他錨節點構成的三角形中的最優化邊，使用余弦定理修正得到L1到A的距離為66.2 m，L3到A的距離為98.6 m。按照選取的最優化錨節點得到如下結果：根據A到各個錨節點的距離可知，L1是最短平均跳距的錨節點，用L1到A的距離作為A與其他錨節點構成的三角形中的最優化邊，使用余弦定理修正得到L2到A的距離約為40.0 m，L3到A的距離約為80.0 m。通過比較AL1,AL2和AL3可以明顯看出,改進錨節點選取方式后，優化了錨節點與未知節點間的距離。

Figure 1 DV-Hop schematic diagram

如圖2所示，選取最優化錨節點后使用余弦定理修正的基本思想如下所示：

(1)首先在MA1,A1A2和MA2各邊跳數已知的情況下，使用3邊的跳數信息近似代替距離信息，得到角度θ1：

(10)

其中，Hop1是最優化錨節點與未知節點的跳數，Hop2是最優化錨節點和其余錨節點中任意一個錨節點的跳數，Hop3是未知節點和其余錨節點中任意一個錨節點的跳數。

Figure 2 Schematic of anchor node using minimum hop

(2)錨節點A2、A3之間的距離dA2A3可以通過位置坐標對應相減再開平方計算得到。使用最優化錨節點的最短跳距乘以M到A2的跳數得到dMA2，再利用式(10)得到的θ1可以計算出dMA3：

dMA2≈Hop1×HopDistanceA2

(11)

(12)

HopDistanceA2是根據式(2)得出的平均跳距。當3條邊無法構成三角形時，即Hop1+Hop2≤Hop3或Hop1-Hop2≥Hop3時，

dMA3≈Hop1×HopDistanceA3

(13)

就使用傳統DV-Hop算法中錨節點平均跳距與對應跳數相乘的計算方式，但此時基于最優化錨節點自身的優勢，因此用每個最優化錨節點的平均跳距[16]代替每個未知節點周圍其余錨節點的平均跳距，再利用余弦定理進行修正，達到優化跳距的目的，降低對未知節點的定位誤差。

3.2 正余弦優化算法

(14)

(15)

(1)r1表示下一個解所在區域，位于最優解和當前解的內部或者外部，迭代次數的多少決定了r1的大小，為了使局部開發能力和全局探索能力達到平衡，r1會隨迭代次數逐漸減小。

(2)r2是[0,2π]的隨機數，其定義了正余弦波動范圍，決定個體的移動方向，同時表明當前解是靠近或遠離目標解。

(3)r3是[0,2]的隨機數，決定目標位置的隨機權重，若r3>1，表明需要增強目標解[18]對當前解的牽引影響;若r3<1表明需要削弱目標解對當前解的牽引影響，防止陷入局部最優。

(4)r4是[0,1]的隨機數，決定選擇正弦函數還是余弦函數。

以圖3為例說明正弦函數和余弦函數對式(14)中個體位置更新的影響，正弦函數和余弦函數的循環模式允許將一個解重新定位到另一個解的范圍內，這樣可以充分利用2個函數計算結果之間的空白區域。為了探索搜索空間，本文通過改變正弦函數和余弦函數的范圍來實現。正弦函數和余弦函數的值域是[-1,1]，但是在函數搜索過程中，為了加大尋優能力，增加了一個乘子2來調大振幅，使得當余弦函數變量取值為π時以及正弦函數變量取值為3π/2時,函數返回值為-2; 當余弦函數變量取值在[0,2π]以及正弦函數變量取值為π/2時,函數返回值為2，這樣可以更加有效地進行波動搜索。圖3所示是SCA尋優過程，改變正弦函數和余弦函數變量的取值，可以更新解的位置，當正弦函數或余弦函數返回值在[-1,1]時，候選解可以較好地搜索具備前景的空間；當正弦函數或余弦函數返回一個大于1或小于-1的值時，候選解可以在探索所定義的搜索空間之外的區域進行全局搜索。SCA使用特定空間區域范圍中的余弦函數和正弦函數，可以順利地從探索階段過渡[19]到開發階段；優化過程中,由于最優解的多可能性和不缺失性,候選解在當前最優解周邊更新其位置，并繼續搜索整個空間中的最優區域。

Figure 3 Optimization process of sine and cosine optimization algorithm

3.3 本文改進算法步驟

Step1首先根據傳統DV-Hop定位算法已經得到的跳數和平均跳距，找出每個未知節點周圍所有錨節點中平均跳距最小的錨節點，即最優化錨節點。

Step2根據最優化錨節點、未知節點、其余任一錨節點相互之間的跳數信息，利用余弦定理得到最優化錨節點和其余任一錨節點之間的角度。

Step3根據步驟2得到的角度信息，重新利用余弦定理得到其余任一錨節點與對應未知節點修正后的距離。

Step4考慮特殊情況，即構不成三角形的情況，利用式(13)代替要修正的邊的距離。

Step5利用正余弦優化算法(SCA)進一步優化。

(1)初始化種群規模N，在[0,100]內隨機生成N個解，并且隨機設定各個解的初始位置。

(2)根據初始解位置，計算相應的f(x)值。

(3)在每一代更新位置信息，重新計算每個解和本次全局的f(x)值。

(4)比較更新后所有解的f(x)值，若當前解大于最優解，就更新全局最優解位置。

(5)判斷是否滿足終止條件，是則輸出當前最優解，即未知節點最優估計位置坐標，否則重復步驟(2)～步驟(4)。

4 仿真模擬

為了驗證本文算法的可行性和有效性，在Matlab 2019a上對本文改進算法、文獻[12]算法、文獻[13]算法和DV-Hop定位算法進行仿真模擬，得到以下4幅圖：圖4是網絡節點分布圖,圖5是錨節點均勻變化下的平均誤差圖，圖6是通信半徑均勻變化下的平均誤差圖,圖7是節點總數均勻變化下的平均誤差圖。實驗過程和結果分析如下所示：

所有節點無規律地散落在100 m*100 m的區域內,節點的平均定位精度用式(16)來計算：

(16)

其中，(x,y)表示未知節點真實位置坐標，(xg,yg)表示未知節點的估計位置坐標，n表示節點總數。

Figure 4 Network node distribution

首先，在100 m*100 m的區域內，通信半徑R為40 m，節點總數為200個，錨節點在節點總數中所占比例由0.1到0.5間隔0.05進行變化，循環100次取平均值,得到如圖5所示的結果。分別選取錨節點比例為0.1，0.3，0.5進行對比。當錨節點比例為0.1時，Error_accuracy：本文改進算法為6.037，文獻[13]算法為7.659,文獻[12]算法為9.714,DV-Hop定位算法為11.03，本文改進算法相比其他對比算法分別優化提升了1.288,3.343和4.659；當錨節點比例為0.3時，Error_accuracy：本文改進算法為3.405,文獻[13]算法為5.032,文獻[12]算法為7.281,DV-Hop定位算法為10.220，本文改進算法相比其他對比算法分別優化提升了1.627,3.876和6.815；當錨節點比例為0.5時，Error_accuracy：本文改進算法為2.774，文獻[13]算法為3.825,文獻[12]算法為6.144,DV-Hop定位算法為10.570，本文改進算法相比其他對比算法分別優化提升了 1.051,3.370和7.796。由此可見在錨節點數均勻變化的過程中，相比于其他3種算法，本文改進算法平均定位誤差最小，定位精度最高。

Figure 5 Average positioning error under uniform change of anchor nodes

其次，在100 m*100 m的區域內,節點總數為200，錨節點數為50，通信半徑R由30 m到60 m間隔5進行變化，循環100次取平均值，得到如圖6所示的結果。分別選取R為30 m,45 m,60 m進行對比。當R=30 m時，Error_accuracy：本文改進算法為3.382,文獻[13]算法為4.819,文獻[12]算法為6.552,DV-Hop定位算法為8.567，本文改進算法相比其他對比算法分別優化提升了1.437,3.170和5.185；當R=45 m時，Error_accuracy：本文改進算法為3.708,文獻[13]算法為5.523,文獻[12]算法為7.700,DV-Hop定位算法為12.09，本文改進算法相比其他算法分別優化提升了1.815,3.992和8.382；當R=60 m時，Error_accuracy：本文改進算法為4.754,文獻[13]算法為6.636,文獻[12]算法為8.823,DV-Hop定位算法為15.100，本文改進算法相比其他算法分別優化提升了1.882,4.069和10.346。觀察4種定位算法，通信半徑在均勻變化的過程中，隨著通信半徑的增大，整個網絡中的節點跳數也在增加，導致每種算法的距離誤差呈現增長趨勢。由此可見，雖然4種算法誤差都普遍增長，但是本文改進算法的平均定位誤差最小，增長幅度也最小，定位精度最高。

Figure 6 Average positioning error under uniform change of communication radius

最后，在100 m*100 m的區域內，固定通信半徑R為40 m，錨節點數為50，節點總數由100到400間隔50進行變化，循環100次取平均值，得到如圖7所示結果。分別選取節點總數為100,250,400進行對比。當節點總數為100時，Error_accuracy：本文改進算法為4.510,文獻[13]算法為6.373,文獻[12]算法為8.568,DV-Hop定位算法為10.870，本文改進算法相比其他對比算法分別優化提升了1.863,4.508和6.360；當節點總數為250時，Error_accuracy：本文改進算法為2.975,文獻[13]算法為4.495,文獻[12]算法為6.963,DV-Hop定位算法為10.880，本文改進算法相比其他算法分別優化提升了1.520,3.988和7.905；當節點總數為400時，Error_accuracy：本文改進算法為2.433,文獻[13]算法為3.769,文獻[12]算法為5.759,DV-Hop定位算法為11.110，本文改進算法相比其他對比算法分別優化提升了 1.336,3.326和8.677。觀察4種定位算法，在固定錨節點數和通信半徑的情況下，當錨節點數不斷增加時，與其他算法相比，本文改進算法平均定位誤差最小，定位精度最高。

Figure 7 Average positioning error under uniform change of total number of nodes

5 算法復雜度分析與評估

本文所提算法的復雜度與網絡區域中節點總數的變化以及算法內部循環語句迭代次數有關。傳統DV-Hop定位算法和文獻[12，13]所提出的改進算法中，在均未使用智能優化算法的情況下，其算法復雜度均為O(n2)，而本文使用正余弦優化算法，在計算算法復雜度時需要一定的參數支撐，其中節點總數為n，錨節點所占比例為p，最大迭代次數為TMAX，種群規模為N，設置頻度函數T(n)=(1-p)·n·TMAX·N,可以得到本文算法的復雜度為O(n3)。在本節中代入實際的數值來計算復雜度，規定節點的通信半徑為40 m，錨節點比例為0.2，迭代次數為100次，種群規模為100，節點總數為100，此時各算法的復雜度與定位精度如表1所示。

從表1可以看出,傳統DV-Hop定位算法和文獻[12,13]算法，在沒有使用智能優化算法的前提下，算法的復雜度均為O(n2)，且文獻[12,13]算法的定位精度比傳統DV-Hop定位算法分別提高了2.302和4.497，而本文算法的復雜度為O(n3)，算法復雜度雖不占優勢，但定位精度比傳統DV-Hop定位算法和文獻[12,13]算法分別提高了6.360，4.058和1.863。綜上，本文雖使用了正余弦優化算法，導致算法復雜度在一定程度上有所增加，但是在定位精度上比其他對比算法都有所提高，定位誤差相對較小，效果明顯。

Table 1 Comparison of algorithm complexity and positioning accuracy of four algorithms

6 結束語

本文改進算法中定義了最優化錨節點的概念，利用余弦定理修正錨節點和未知節點之間的距離，之后再用正余弦優化算法(SCA)改進最小二乘法來估計目標節點位置。正余弦優化算法(SCA)由于僅需要1個參數，很大程度上避免了調參的繁瑣,提升了算法的性能且易達到全局最優，在設置隨機參數和遞減參數的過程中，使得算法中探索和開發2個階段的能力能夠達到很好的平衡，有效降低了定位誤差。實驗結果顯示，不論錨節點、通信半徑和錨節點數等限制條件如何變化，本文提出的融合正余弦優化與跳距優化的DV-Hop定位算法都比傳統DV-Hop及其改進算法的定位誤差更小。但是，正余弦優化算法(SCA)局部搜索能力較弱且只能迭代尋優，是該算法的缺陷，因此應該對其進行改進，例如通過使用混沌算子策略提高初始種群的質量以達到減少迭代次數的效果；隨后采用高斯震蕩算子提升算法的局部尋優能力，以提高算法的整體效率。基于對本文算法優缺點的整體分析，在今后的研究中會著重研究如何進一步提升算法的性能與效率。