基于改進TLBO的DV-Hop定位算法

陳慧琴，王振飛

(1.山西機電職業技術學院，山西 長治 046000；2.太原理工大學 機械工程學院，太原 030024)

無線傳感器網絡(Wireless Sensor Network,WSN)是一個由多個傳感節點通過多跳方式組成的自組織網絡，它對環境的適應性很強，現在已被廣泛應用于醫療保健、空間探索、工業控制等多種場景中[1]。大多數情況下，我們需要根據收集到的數據來確定傳感器節點的確切位置，以便進行目標檢測和跟蹤，制定應對策略，節點定位已成為WSN中的研究熱點[2]。

節點定位算法通常分為基于測距和非測距兩種。基于測距的算法是在距離或角度等測量值的基礎上利用定位算法估算未知節點的位置坐標[3]。該類算法有著較高的定位精度，但需要額外的硬件來測量節點間的距離，且距離的測量容易受到多徑衰落的影響[4]?；诜菧y距的算法根據WSN中節點之間的連接信息估計未知節點的坐標。DV-Hop算法[5]是一種廣泛使用的非測距定位算法，科研人員對其做了大量研究，提出許多改進的DV-Hop算法。文獻[6]提出一種基于移動節點的DV-Hop優化算法，將移動節點添加到算法中，并利用雙半徑廣播節點的位置坐標以優化節點間的跳數，提高定位精度。文獻[7]提出了基于遺傳算法(Genetic algorithm,GA)的DV-Hop算法，利用GA算法的交叉、選擇、變異來優化定位結果。文獻[8]提出一種基于最優輔助距離估計錨節點的DV-Hop定位算法，根據不同的估距類型計算節點間的估計距離，并將加權因子的概念引入到三邊定位法中，以提高定位精度。文獻[9]提出一種基于粒子群優化算法(Particle swarm optimization,PSO)的改進DV-Hop算法，利用二維雙曲線定位算法估計未知節點的位置[10]后，再使用PSO算法提高定位準確性。本文提出一種基于改進教與學優化算法(Teaching-Learning-Based Optimization,TLBO)的DV-Hop定位算法來提高定位精度。

1 DV-Hop算法

DV-Hop算法定位步驟如下[11]。

每個錨節點Ai以多跳的方式向網絡中廣播包含Ai的位置以及從0開始的跳數字段的報文信息。在這個過程中，每經過一跳，跳數都會增加1。網絡中的節點J(錨節點或未知節點)記錄Ai的位置并初始化它和Ai之間的最小跳數，記為hopi,J。當節點J接收到的跳數值低于先前存儲的跳數hopi,J時，則J將根據該較小跳數計數值更新hopi,J；否則忽略該跳數值。

用HopSizei表示錨節點的平均每跳距離為：

(1)

式(1)中：(xi,yi)和(xj,yj)分別表示錨節點i和j的坐標；hopij表示錨節點i和j之間的最小跳數。錨節點在網絡中廣播它的平均每跳距離，未知節點接收并保存距離最近錨節點的平均每跳距離并將其轉發。

接收到平均每跳距離后，未知節點t通過式(2)計算它和錨節點i之間的距離dit，然后使用最小二乘估計就能得到未知節點的坐標。

dit=HopSizei×hopit

(2)

式(2)中：dit和hopit分別表示錨節點i和未知節點t之間的距離和最小跳數。

DV-Hop算法誤差分析如下：1)在DV-Hop算法中，節點間的距離表示為平均跳距與最小跳數的乘積。由于網絡拓撲的影響，節點間的實際每跳距離誤差較大，當計算出的節點間平均跳距沒有達到理想值，且節點在拓撲中進行連續多跳時，節點間的實際距離和計算距離就會產生較大偏差，從而導致定位結果不精確。2)由于網絡拓撲的不同，節點在網絡中的分布是無規律的。當未知節點周圍的錨節點大于等于三個時，未知節點的定位坐標可以很快的計算得到。但是，如果參與定位的錨節點在一條直線上，未知節點的坐標就有可能無法確定，出現定位盲區，使得算法的定位精度有所降低。3)在DV-Hop算法中，通常利用最小二乘估計計算得到未知節點的坐標。但利用最小二乘估計計算未知節點的坐標會導致誤差積累，嚴重影響定位結果的精確度。

2 改進的教與學優化算法

2.1 教與學優化算法

教與學優化算法(TLBO)[12-13]通過模擬班級中教師和學員間的教學過程尋找最優解。該算法分為兩個階段，分別是“教”階段和“學”階段。在“教”階段中，學員跟隨教師學習，在“學”階段中，學員之間互相學習。

在“教”階段中，學員跟隨教師學習，獲得知識，教師希望將學員的平均成績meanstudent提高到他的水平Xteacher。學員的平均成績和期望的平均成績之間的差值表示為：

Difference_Mean=rand(Xteacher-TF×meanstudent)

(3)

且：

TF=round(1+rand)

(4)

式(4)中:rand表示[0,1]之間的隨機數；round(x)表示對x進行四舍五入；TF表示改變平均值程度的教學因子，它的值可以設為1或2。每個學員根據式(5)進行學習，即：

Xnew,i=Xold,i+Difference_Mean

(5)

式(5)中:Xnew,i表示第i個學員學習后的狀態值；Xold,i表示原來的狀態值。如果Xnew,i比Xold,i優秀，那么用Xnew,i代替Xold,i。

在“學”階段中，學員從班級里選擇另外一個學員進行學習。假設Xi和Xj為兩個不同的學員，則他們之間的學習過程為：

(6)

式(6)中：ri表示[0,1]之間的隨機數；f(X)表示學員的適應度值。

2.2 TLBO的改進

TLBO根據貪婪算法選擇最優個體，容易出現收斂速度慢、種群多樣性丟失等問題。本文對傳統的TLBO進行改進以增強其尋優能力和可靠性。

TLBO中的教學因子TF影響算法的尋優能力。在尋優的初期階段，所有學員均向教師靠攏以便快速收斂至最優值。TF越大，算法的收斂速度越快，但其局部檢測能力越弱。由于TF的值只能設為1或2，如果學員的適應度值比平均水平低，則種群趨向于靠近最優個體，此時若TF的值取2，算法的收斂速度就會加快；如果學員的適應度值比平均水平高，TF無論取1還是2，種群都會遠離最優個體，算法的收斂速度也會降低。因此，本文對TF進行優化使其能夠在每次迭代中自適應改變自身的值，以增強收斂速度和局部檢測能力。TF表示為：

(7)

式(7)中：itermax表示最大迭代次數；iter表示當前迭代次數。

在TLBO中，學員通過教師的教學和學員間的交流學習兩種方式提高自身成績。在實際應用中，學員還可以通過自學習的方式主動向教師詢問問題以提高成績?；谧詫W習的學習過程為：

(8)

式(8)中：Xnew,i表示第i個學員學習后的狀態值；Xold,i表示原來的狀態值；r1、r2、r3、r4表示[0,1]之間的隨機數。

Levy飛行是一種Markov隨機游走過程，可以用來描述行人的行走分步軌跡、動物的覓食軌跡等隨機運動[14]。在Levy飛行中，步長滿足式(9)所示的重尾Levy分步，即：

(9)

式(9)中，s表示Levy飛行的步長。

(10)

(11)

在Levy飛行中，限定范圍內的局部搜索和長距離下的隨機行走是相間的，因此在尋優時，部分解可以在當前最優解附近搜索，使得局部搜索能力加強；其余解則在距離當前最優解較遠的范圍內搜索，以確保跳出局部最優，加強全局搜索能力。將Levy飛行融入到TLBO算法中，能夠在種群中產生方向劇烈變化的隨機游走，擴大搜索范圍，使得種群多樣性增加，避免TLBO算法陷入局部最優。在基于Levy飛行的TLBO算法中，學習過程為：

(12)

式(12)中：s表示Levy飛行的步長；r1、r2、r3、r4表示[0,1]之間的隨機數。

3 基于改進TLBO的DV-Hop定位算法

在基于改進TLBO的DV-Hop定位算法中，針對錨節點平均每跳距離的不準確問題，利用修正因子來修正錨節點的平均每跳距離，引入共線性概念，選擇合適的錨節點進行定位以減少誤差，最后，利用改進TLBO計算定位結果。

3.1 利用修正因子優化錨節點的平均每跳距離

在DV-Hop算法中，節點間距離估計的不準確性主要取決于錨節點的平均每跳距離。因此我們引入修正因子，以修正錨節點的平均每跳距離。

在DV-Hop算法的本文1.1.1節中，錨節點間的實際距離表示為：

(13)

式(13)中：(xi,yi)和(xj,yj)分別是錨節點i、j的坐標；是兩個錨節點i、j之間的實際距離。

兩個錨節點之間的距離還可以表示為它們之間的跳數和任一錨節點的平均每跳距離的乘積。令Dij為錨節點i、j之間的計算距離，則有：

Dij=HopSizei×hopij,i≠j

(14)

(15)

(16)

將修正因子添加到式(1)中來修正平均每跳距離，則修正后的錨節點與未知節點之間的距離為：

(17)

3.2 基于共線性的錨節點選擇

在二維平面定位中，至少需要3個錨節點才能夠確定未知節點的坐標。當參與定位的錨節點共線時，未知節點的位置有可能無法確定[15]。為了解決這個問題，本文引入共線度(DCL)的概念。如果三個錨節點組成的區域面積為零，則這三點共線，該區域可表示為：

(18)

式(18)中：a表示連接三個錨節點形成的區域大?。?x1,y1)、(x2,y2)和(x3,y3)表示3個錨節點的坐標。

DCL可以表示為：

(19)

根據DCL來選擇錨節點以計算未知節點坐標。如果3個錨節點共線，則它們不參與到未知節點的定位中。

3.3 基于改進TLBO的定位坐標優化

定位的實質是誤差的最小化問題，本節將改進TLBO算法應用到DV-Hop算法中，以減少定位誤差。假設WSN中一共有N個傳感器節點，其中錨節點數量為k，未知節點數量為n=N-k。定位問題的目標函數可以表示為：

(20)

利用改進TLBO算法進行坐標計算時，為了使定位誤差最小，創建一個種群可行區域，并在該區域中部署WSN節點，如圖1所示。假設所有節點的通信半徑均為R，Nt是坐標為(xt,yt)的未知節點，A1、A2和A3是未知節點Nt的鄰居錨節點，它們的坐標分別為(x1,y1)、(x2,y2)和(x3,y3)，h1,Nt、h2,Nt和h3,Nt分別是未知節點Nt與錨節點A1，A2和A3之間的最小跳數。

圖1 種群可行區域

由于該未知節點有3個相鄰錨節點，因此，分別以錨節點A1，A2和A3為圓心，R×hi,Nt(i=1,2,3)為半徑構造3個圓，并給出他們的外接正方形。圖中陰影區域表示3個正方形的重疊區域，即種群可行區域，未知節點Nt就處在該區域中。在該區域內隨機生成種群，未知節點Nt(xt,yt)的坐標處在該可行區域內時有最小誤差。隨機生成的種群根據設定的上界和下界搜索未知節點的精確坐標，上界和下界可以表示為：

(21)

初始種群的最佳值設定要達到種群規模最小值和最大值間的平衡。當種群規模較小時，定位結果較差；當種群規模較大時，算法需要更多的執行時間尋找最佳方案。通過多次仿真實驗可知，最優的初始種群數量為50。將隨機生成的初始種群看作是學員，計算每個學員的適應度，并隨機選擇兩個學員。這些學員是在一個未知節點的種群可行區域內隨機生成的坐標，根據目標函數計算坐標值。對所有生成的坐標進行類似的處理，并根據目標函數選擇具有最小誤差的坐標作為未知節點的最終坐標。對于所有的未知節點，重復上述過程，直至滿足停止條件。

綜上所述，基于改進TLBO的DV-Hop定位算法的步驟為：

步驟1計算未知節點和錨節點之間的最小跳數以及錨節點的平均每跳距離；

步驟2利用修正因子修正每個錨節點的平均每跳距離，根據式(17)并計算未知節點和錨節點之間的距離；

步驟3根據式(18)、式(19)，利用共線度選擇合適的定位錨節點；

步驟4找出每個未知節點的種群可行區域，并在可行區域中生成初始種群；

步驟5在可行區域內，根據式(21)確定每個未知節點的上界和下界的值；

步驟6尋找最優的初始種群數量，并根據目標函數計算未知節點的坐標。對于所有的未知節點，重復上述過程，直至滿足停止條件。

4 仿真結果分析

4.1 參數設置

使用Matlab 2014仿真軟件驗證本文算法的性能，并與傳統的DV-Hop算法、文獻[7]提出的基于遺傳算法的DV-Hop改進算法、文獻[9]提出的基于粒子群優化的改進DV-Hop算法進行比較。在100 m×100 m的仿真區域內，隨機生成k個錨節點和n個未知節點，所有節點的通信半徑為R。在改進TLBO算法中，設置初始種群大小為50，最大迭代次數為500。為了減小算法的偶然性帶來的誤差，將各個算法重復運行50次，取平均值作為最終的結果。本文中，利用定位誤差(Localization Error,LE)和平均定位誤差(Average Localization Error,ALE)衡量算法性能。節點的實際坐標和估計坐標之間的差值LE為：

(22)

式(22)中：(xt,yt)表示未知節點的估計坐標；(xa,ya)表示未知節點的實際坐標。

ALE指總定位誤差與未知節點數量的比值，可以表示為：

(23)

4.2 仿真結果分析

4.2.1定位誤差比較

在100 m×100 m的仿真區域內隨機部署100個節點，每個節點的通信半徑為25 m，其中錨節點個數為60，未知節點個數為40。圖2所示為4種算法的定位誤差結果，與其他算法相比，本文算法的效果更好。在文獻[7]算法中，需要設置遺傳算法的最佳控制參數以獲得更精確的定位結果，但遺傳算法可能無法達到全局最優和局部最優之間的完美平衡。本文算法利用修正因子提高了錨節點平均每跳距離的準確性，并且根據共線性選擇，處在非同一直線上的錨節點參與定位，提高了定位精度。

圖2 利用不同算法得到的未知節點定位誤差曲線

表1所示為利用4種算法獲得的定位誤差的最大值、最小值和平均值。從表1可以看出，本文算法在定位精度方面與其他定位算法相比性能更好，最大定位誤差和最小定位誤差都有明顯的下降，平均定位誤差為4.18m，定位精度提高很多。

表1 定位誤差

4.2.2錨節點比值對定位結果的影響

錨節點比值會影響算法的定位精度。在100 m×100 m的仿真區域內隨機部署100個節點，每個節點的通信半徑為30 m，錨節點比值從20%增加到70%。圖3為四種算法的ALE隨錨節點比值變化圖。在錨節點比值逐漸增大的過程中，4種算法的ALE均在減小。這是因為未知節點和錨節點之間的跳數值隨著錨節點數量的增加而下降，并且錨節點的平均每跳距離和跳數值有著密切關系，即當跳數值較小時，平均每跳距離越精確，所以，當錨節點的個數越多時，其平均每跳距離的值也就越精確。因此，4種算法的ALE都隨著節點密度的增加而降低。對比4種算法的ALE，本文算法的ALE是最小的，當錨節點比值為70%時，本文算法的ALE可以達到3.17 m

4.2.3通信半徑對定位結果的影響

節點的通信半徑同樣影響算法的定位精度。在100 m×100 m的區域內隨機部署100個節點，其中錨節點比值為30%，節點的通信半徑從15 m增加到40 m。圖4為不同通信半徑情況下4種算法的ALE。仿真結果表明，隨著通信半徑的增大，4種算法的ALE先減小，當通信半徑大于35 m時，ALE基本維持不變。然而，本文算法的ALE始終是最小的。通信半徑的增加會使節點周圍能夠通信的節點數量變多，錨節點的平均每跳距離更加精確，并且本文算法還根據修正因子進一步修正平均每跳距離，這樣錨節點和未知節點間的距離就會更精確，再根據改進TLBO算法，就能得到未知節點精確的坐標。

圖3 4種算法的ALE隨錨節點比值的變化

圖4 4種算法的ALE隨通信半徑的變化

4.2.4節點密度對定位結果的影響

在WSN中，定位精度還與節點密度有關。圖5為在不同節點密度時的ALE。在100 m×100 m的區域內隨機部署節點，節點總數從50增加到400，節點的通信半徑為25 m，且錨節點比例為30%。從圖5可知，節點密度增加時，4種算法的ALE逐漸減小。因為隨著節點密度的增加，網絡連通性也在增加，WSN中能夠收集到的用于節點定位的信息也越來越多，定位精度會提高。當WSN中的節點數量達到一定的值后，網絡連通性的加強對定位結果的影響就會很小。與其他算法相比，本文算法在定位精度方面表現出更好的性能。因為網絡連通性的增強使得算法可以找到多組不共線的錨節點來定位同一個未知節點，這樣，該未知節點的定位精度會提高很多。圖5中，當節點總數為300時，本文算法的ALE為4.72 m，DV-Hop算法、文獻[7]算法、文獻[9]算法的ALE分別為6.97 m、6.25 m、5.61 m，相比之下，本文算法的ALE分別提高了32.28%、24.48%、15.86%。

圖5 4種算法的ALE隨節點密度的變化曲線

5 結論

1)基于改進TLBO的DV-Hop定位算法，使用修正因子修正錨節點的平均每跳距離，利用修正后的平均每跳距離計算未知節點和錨節點之間的距離。

2)引入DCL,減少了由錨節點共線引起的定位誤差。

3)利用Levy飛行優化TLBO算法，避免TLBO算法陷入局部最優，并根據優化后的TLBO計算定位坐標，進一步提高定位精度。

4)仿真結果表明，本文提出的算法收斂速度快，具有很高的定位精度。