陳慧琴，王振飛

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

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

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

1 DV-Hop算法

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

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

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

(1)

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

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

dit=HopSizei×hopit

(2)

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

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

2 改進的教與學優(yōu)化算法

2.1 教與學優(yōu)化算法

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

在“教”階段中，學員跟隨教師學習，獲得知識，教師希望將學員的平均成績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個學員學習后的狀態(tài)值；Xold,i表示原來的狀態(tài)值。如果Xnew,i比Xold,i優(yōu)秀，那么用Xnew,i代替Xold,i。

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

(6)

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

2.2 TLBO的改進

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

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

(7)

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

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

(8)

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

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

(9)

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

(10)

(11)

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

(12)

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

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

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

3.1 利用修正因子優(yōu)化錨節(jié)點的平均每跳距離

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

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

(13)

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

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

Dij=HopSizei×hopij,i≠j

(14)

(15)

(16)

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

(17)

3.2 基于共線性的錨節(jié)點選擇

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

(18)

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

DCL可以表示為：

(19)

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

3.3 基于改進TLBO的定位坐標優(yōu)化

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

(20)

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

圖1 種群可行區(qū)域

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

(21)

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

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

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

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

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

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

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

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

4 仿真結果分析

4.1 參數設置

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

(22)

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

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

(23)

4.2 仿真結果分析

4.2.1定位誤差比較

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

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

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

表1 定位誤差

4.2.2錨節(jié)點比值對定位結果的影響

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

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

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

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

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

4.2.4節(jié)點密度對定位結果的影響

在WSN中，定位精度還與節(jié)點密度有關。圖5為在不同節(jié)點密度時的ALE。在100 m×100 m的區(qū)域內隨機部署節(jié)點，節(jié)點總數從50增加到400，節(jié)點的通信半徑為25 m，且錨節(jié)點比例為30%。從圖5可知，節(jié)點密度增加時，4種算法的ALE逐漸減小。因為隨著節(jié)點密度的增加，網絡連通性也在增加，WSN中能夠收集到的用于節(jié)點定位的信息也越來越多，定位精度會提高。當WSN中的節(jié)點數量達到一定的值后，網絡連通性的加強對定位結果的影響就會很小。與其他算法相比，本文算法在定位精度方面表現出更好的性能。因為網絡連通性的增強使得算法可以找到多組不共線的錨節(jié)點來定位同一個未知節(jié)點，這樣，該未知節(jié)點的定位精度會提高很多。圖5中，當節(jié)點總數為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隨節(jié)點密度的變化曲線

5 結論

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

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

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

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