基于改進(jìn)TLBO的DV-Hop定位算法

陳慧琴，王振飛

(1.山西機(jī)電職業(yè)技術(shù)學(xué)院，山西 長(zhǎng)治 046000；2.太原理工大學(xué) 機(jī)械工程學(xué)院，太原 030024)

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

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

1 DV-Hop算法

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

每個(gè)錨節(jié)點(diǎn)Ai以多跳的方式向網(wǎng)絡(luò)中廣播包含Ai的位置以及從0開(kāi)始的跳數(shù)字段的報(bào)文信息。在這個(gè)過(guò)程中，每經(jīng)過(guò)一跳，跳數(shù)都會(huì)增加1。網(wǎng)絡(luò)中的節(jié)點(diǎn)J(錨節(jié)點(diǎn)或未知節(jié)點(diǎn))記錄Ai的位置并初始化它和Ai之間的最小跳數(shù)，記為hopi,J。當(dāng)節(jié)點(diǎn)J接收到的跳數(shù)值低于先前存儲(chǔ)的跳數(shù)hopi,J時(shí)，則J將根據(jù)該較小跳數(shù)計(jì)數(shù)值更新hopi,J；否則忽略該跳數(shù)值。

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

(1)

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

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

dit=HopSizei×hopit

(2)

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

DV-Hop算法誤差分析如下：1)在DV-Hop算法中，節(jié)點(diǎn)間的距離表示為平均跳距與最小跳數(shù)的乘積。由于網(wǎng)絡(luò)拓?fù)涞挠绊?，?jié)點(diǎn)間的實(shí)際每跳距離誤差較大，當(dāng)計(jì)算出的節(jié)點(diǎn)間平均跳距沒(méi)有達(dá)到理想值，且節(jié)點(diǎn)在拓?fù)渲羞M(jìn)行連續(xù)多跳時(shí)，節(jié)點(diǎn)間的實(shí)際距離和計(jì)算距離就會(huì)產(chǎn)生較大偏差，從而導(dǎo)致定位結(jié)果不精確。2)由于網(wǎng)絡(luò)拓?fù)涞牟煌?，?jié)點(diǎn)在網(wǎng)絡(luò)中的分布是無(wú)規(guī)律的。當(dāng)未知節(jié)點(diǎn)周?chē)腻^節(jié)點(diǎn)大于等于三個(gè)時(shí)，未知節(jié)點(diǎn)的定位坐標(biāo)可以很快的計(jì)算得到。但是，如果參與定位的錨節(jié)點(diǎn)在一條直線(xiàn)上，未知節(jié)點(diǎn)的坐標(biāo)就有可能無(wú)法確定，出現(xiàn)定位盲區(qū)，使得算法的定位精度有所降低。3)在DV-Hop算法中，通常利用最小二乘估計(jì)計(jì)算得到未知節(jié)點(diǎn)的坐標(biāo)。但利用最小二乘估計(jì)計(jì)算未知節(jié)點(diǎn)的坐標(biāo)會(huì)導(dǎo)致誤差積累，嚴(yán)重影響定位結(jié)果的精確度。

2 改進(jìn)的教與學(xué)優(yōu)化算法

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

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

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

Difference_Mean=rand(Xteacher-TF×meanstudent)

(3)

且：

TF=round(1+rand)

(4)

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

Xnew,i=Xold,i+Difference_Mean

(5)

式(5)中:Xnew,i表示第i個(gè)學(xué)員學(xué)習(xí)后的狀態(tài)值；Xold,i表示原來(lái)的狀態(tài)值。如果Xnew,i比Xold,i優(yōu)秀，那么用Xnew,i代替Xold,i。

在“學(xué)”階段中，學(xué)員從班級(jí)里選擇另外一個(gè)學(xué)員進(jìn)行學(xué)習(xí)。假設(shè)Xi和Xj為兩個(gè)不同的學(xué)員，則他們之間的學(xué)習(xí)過(guò)程為：

(6)

式(6)中：ri表示[0,1]之間的隨機(jī)數(shù)；f(X)表示學(xué)員的適應(yīng)度值。

2.2 TLBO的改進(jìn)

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

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

(7)

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

在TLBO中，學(xué)員通過(guò)教師的教學(xué)和學(xué)員間的交流學(xué)習(xí)兩種方式提高自身成績(jī)。在實(shí)際應(yīng)用中，學(xué)員還可以通過(guò)自學(xué)習(xí)的方式主動(dòng)向教師詢(xún)問(wèn)問(wèn)題以提高成績(jī)?；谧詫W(xué)習(xí)的學(xué)習(xí)過(guò)程為：

(8)

式(8)中：Xnew,i表示第i個(gè)學(xué)員學(xué)習(xí)后的狀態(tài)值；Xold,i表示原來(lái)的狀態(tài)值；r1、r2、r3、r4表示[0,1]之間的隨機(jī)數(shù)。

Levy飛行是一種Markov隨機(jī)游走過(guò)程，可以用來(lái)描述行人的行走分步軌跡、動(dòng)物的覓食軌跡等隨機(jī)運(yùn)動(dòng)[14]。在Levy飛行中，步長(zhǎng)滿(mǎn)足式(9)所示的重尾Levy分步，即：

(9)

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

(10)

(11)

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

(12)

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

3 基于改進(jìn)TLBO的DV-Hop定位算法

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

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

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

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

(13)

式(13)中：(xi,yi)和(xj,yj)分別是錨節(jié)點(diǎn)i、j的坐標(biāo)；是兩個(gè)錨節(jié)點(diǎn)i、j之間的實(shí)際距離。

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

Dij=HopSizei×hopij,i≠j

(14)

(15)

(16)

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

(17)

3.2 基于共線(xiàn)性的錨節(jié)點(diǎn)選擇

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

(18)

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

DCL可以表示為：

(19)

根據(jù)DCL來(lái)選擇錨節(jié)點(diǎn)以計(jì)算未知節(jié)點(diǎn)坐標(biāo)。如果3個(gè)錨節(jié)點(diǎn)共線(xiàn)，則它們不參與到未知節(jié)點(diǎn)的定位中。

3.3 基于改進(jìn)TLBO的定位坐標(biāo)優(yōu)化

定位的實(shí)質(zhì)是誤差的最小化問(wèn)題，本節(jié)將改進(jìn)TLBO算法應(yīng)用到DV-Hop算法中，以減少定位誤差。假設(shè)WSN中一共有N個(gè)傳感器節(jié)點(diǎn)，其中錨節(jié)點(diǎn)數(shù)量為k，未知節(jié)點(diǎn)數(shù)量為n=N-k。定位問(wèn)題的目標(biāo)函數(shù)可以表示為：

(20)

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

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

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

(21)

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

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

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

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

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

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

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

步驟6尋找最優(yōu)的初始種群數(shù)量，并根據(jù)目標(biāo)函數(shù)計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。對(duì)于所有的未知節(jié)點(diǎn)，重復(fù)上述過(guò)程，直至滿(mǎn)足停止條件。

4 仿真結(jié)果分析

4.1 參數(shù)設(shè)置

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

(22)

式(22)中：(xt,yt)表示未知節(jié)點(diǎn)的估計(jì)坐標(biāo)；(xa,ya)表示未知節(jié)點(diǎn)的實(shí)際坐標(biāo)。

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

(23)

4.2 仿真結(jié)果分析

4.2.1定位誤差比較

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

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

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

表1 定位誤差

4.2.2錨節(jié)點(diǎn)比值對(duì)定位結(jié)果的影響

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

4.2.3通信半徑對(duì)定位結(jié)果的影響

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

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

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

4.2.4節(jié)點(diǎn)密度對(duì)定位結(jié)果的影響

在WSN中，定位精度還與節(jié)點(diǎn)密度有關(guān)。圖5為在不同節(jié)點(diǎn)密度時(shí)的ALE。在100 m×100 m的區(qū)域內(nèi)隨機(jī)部署節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)從50增加到400，節(jié)點(diǎn)的通信半徑為25 m，且錨節(jié)點(diǎn)比例為30%。從圖5可知，節(jié)點(diǎn)密度增加時(shí)，4種算法的ALE逐漸減小。因?yàn)殡S著節(jié)點(diǎn)密度的增加，網(wǎng)絡(luò)連通性也在增加，WSN中能夠收集到的用于節(jié)點(diǎn)定位的信息也越來(lái)越多，定位精度會(huì)提高。當(dāng)WSN中的節(jié)點(diǎn)數(shù)量達(dá)到一定的值后，網(wǎng)絡(luò)連通性的加強(qiáng)對(duì)定位結(jié)果的影響就會(huì)很小。與其他算法相比，本文算法在定位精度方面表現(xiàn)出更好的性能。因?yàn)榫W(wǎng)絡(luò)連通性的增強(qiáng)使得算法可以找到多組不共線(xiàn)的錨節(jié)點(diǎn)來(lái)定位同一個(gè)未知節(jié)點(diǎn)，這樣，該未知節(jié)點(diǎn)的定位精度會(huì)提高很多。圖5中，當(dāng)節(jié)點(diǎn)總數(shù)為300時(shí)，本文算法的ALE為4.72 m，DV-Hop算法、文獻(xiàn)[7]算法、文獻(xiàn)[9]算法的ALE分別為6.97 m、6.25 m、5.61 m，相比之下，本文算法的ALE分別提高了32.28%、24.48%、15.86%。

圖5 4種算法的ALE隨節(jié)點(diǎn)密度的變化曲線(xiàn)

5 結(jié)論

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

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

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

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