彭 鐸楊雅文高玉蔚王嬋飛

(蘭州理工大學計算機與通信學院，甘肅 蘭州 730050)

無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)是由低成本、低功耗、可自重構(gòu)的傳感器節(jié)點組成。并且無線傳感器網(wǎng)絡在軍事、環(huán)境監(jiān)測、工農(nóng)業(yè)生產(chǎn)、醫(yī)療健康、建筑物監(jiān)測、空間探測等領(lǐng)域有著廣闊的應用前景和巨大的應用價值[1-2]。能夠準確得知無線傳感器網(wǎng)絡的節(jié)點位置是將無線傳感器網(wǎng)絡技術(shù)應用于實際的前提，因此，如何提高無線傳感器網(wǎng)絡的定位精度是近年來的熱點研究領(lǐng)域之一。現(xiàn)有的無線傳感器網(wǎng)絡定位算法主要分為距離相關(guān)算法和距離無關(guān)算法[3]。常見的距離相關(guān)算法有到達時間算法(ToA)、到達角度(AoA)、接收信號強度(RSS)等[4-5]。但由于距離相關(guān)算法需要額外的硬件支持，因此距離無關(guān)算法應用更為廣泛。

1 概述

DV-hop算法作為距離無關(guān)算法，具有易實現(xiàn)，成本低，不需要額外硬件設(shè)備等優(yōu)點被廣泛應用。近年來許多學者將與自然相關(guān)的進化算法應用于提高DV-hop算法定位精度中，如粒子群算法(PSO)，鯨魚優(yōu)化算法(WOA)，螢火蟲算法(FA)等。以下文獻采用了智能優(yōu)化算法的思想:文獻[6]提出了基于改進的布谷鳥算法，采用Levy飛行策略和柯西分布對布谷鳥算法進行改進，增強其尋優(yōu)性能并應用于DV-hop算法中有效地提高了定位精度。文獻[7]對跳距進行了修正，并且采用新型智能優(yōu)化算法runner-root算法優(yōu)化傳統(tǒng)DV-hop算法，得到更加精確的未知節(jié)點坐標。文獻[8]將定位問題抽象為函數(shù)尋優(yōu)問題，采用并行鯨魚優(yōu)化算法提升了原算法定位精度。本文所采用的麻雀搜索算法(SSA)是新型智能優(yōu)化算法，相比于其他優(yōu)化算法有更強的尋優(yōu)性以及收斂更快的優(yōu)點；使用多種通信半徑細化節(jié)點跳數(shù)以降低平均跳距誤差的思想也被廣泛應用。文獻[9]采用雙通信半徑進行廣播，使節(jié)點間的跳數(shù)不再為整數(shù)，使計算出的平均跳距更加精確，達到提高定位精度的目的。文獻[10]利用多級通信半徑修正錨節(jié)點到信鄰節(jié)點的跳數(shù)信息。再根據(jù)信標節(jié)點與未知節(jié)點的距離，對平均跳距加權(quán)處理，并將每個加權(quán)后的平均跳距參與未知節(jié)點平均跳距的計算，使未知節(jié)點的平均跳距更符合實際網(wǎng)絡情況。以上改進針對傳統(tǒng)算法中使用平均跳距誤差較大的問題對跳距進行了修正，或使用智能優(yōu)化算法改善采用最小二乘法估計坐標存在的對初值敏感的問題。但以上改進僅單一的考慮了DV-hop算法在傳播階段或在坐標估計階段產(chǎn)生誤差的原因，因此本文提出了一種基于多通信半徑和麻雀搜索算法的WSN定位方法，對算法在估計平均跳距階段因為網(wǎng)絡拓撲分布不均，節(jié)點間跳距誤差較大的問題采用了多通信半徑進行修正；以及對計算節(jié)點坐標階段，使用最小二乘法對初值敏感、受測量誤差較大的問題采用了LSSA智能優(yōu)化算法進行修正，以此達到提高算法定位精度的目的。

1.1 DV-hop算法

DV-hop算法主要分為3個步驟[11]:

①計算最小跳數(shù)

各錨節(jié)點向整個網(wǎng)絡廣播發(fā)送包含其位置坐標的信息，節(jié)點間跳數(shù)初始化為0，接收到信息的節(jié)點將跳數(shù)記為1跳，并將其轉(zhuǎn)發(fā)。每轉(zhuǎn)發(fā)一次跳數(shù)值加1，每個節(jié)點記錄其接收到的最小跳數(shù)值。對于接收到跳數(shù)較高的錨節(jié)點信息記為無用信息并忽略。

②估計到各錨節(jié)點的平均跳距

每個錨節(jié)點根據(jù)上一步中記錄的與其他錨節(jié)點的位置信息和相距跳數(shù)，利用式(1)估算平均每跳的距離:

式中:(x i，y i)和(x j，y j)是錨節(jié)點i和j的坐標，h i j是錨節(jié)點i與j(i≠j)之間的跳數(shù)。獲得各錨節(jié)點平均跳數(shù)Hopsizei后，各錨節(jié)點向整個網(wǎng)絡廣播其平均跳距。未知節(jié)點保留接收到的第一個跳距信息并轉(zhuǎn)發(fā)給鄰居節(jié)點。

③未知節(jié)點位置估計

未知節(jié)點通過②獲得到每個錨節(jié)點的信息，通過平均跳數(shù)和跳距計算到每個錨節(jié)點間的距離。再采用三邊測量法或最大似然估計法計算其自身位置坐標。

式中:d im和hopi m為錨節(jié)點i和未知節(jié)點m之間的距離和最小跳數(shù)。

2 基于動態(tài)自適應Levy步長的麻雀搜索算法(LSSA)

2.1 麻雀搜索算法[12]

SSA是一種受麻雀覓食行為和反捕食行為啟發(fā)而提出的一種新型群體智能優(yōu)化算法，SSA算法相比于已有優(yōu)化算法如:灰狼優(yōu)化算法、粒子群優(yōu)化算法、引力算法等，對單峰值函數(shù)、多峰值函數(shù)以及固定維度函數(shù)都有更好的尋優(yōu)效果，即尋優(yōu)精度更高，在同等迭代次數(shù)下能更快的收斂到最優(yōu)解；SSA算法相對于其他算法而言具有更好的魯棒性和收斂速度，可以作為解決優(yōu)化問題的有效工具。

SSA算法將整個過程抽象為發(fā)現(xiàn)者和加入者模型，并且加入了偵查預警機制。在整個群體中，發(fā)現(xiàn)者搜索范圍更廣擁有較強的全局搜索能力，加入者為了獲得更好的適應度向發(fā)現(xiàn)者靠近。當整個種群意識到危險時將會進行反捕食行為。

發(fā)現(xiàn)者數(shù)量為20%，在迭代過程中發(fā)現(xiàn)者的位置更新定義為:

式中:t為當前迭代次數(shù)；item為最大迭代次數(shù)；α∈(0，1]為隨機數(shù)；R2∈[0，1]，ST∈[0.5，1]分別表示安全值和預警值，Q為服從正態(tài)分布的隨機數(shù)，L表示1×d的元素全為1的矩陣。當R2

除發(fā)現(xiàn)者外其余麻雀為加入者，根據(jù)下式進行位置更新:

種群中負責偵查預警的麻雀占種群總數(shù)的10%～20%，其位置按照下式進行更新:

式中:β表示步長控制參數(shù)，且β～N(0，1)為一隨機數(shù)；K為[-1，1]之間的一個隨機數(shù)，控制麻雀的移動方向及步長；ε為一最小常數(shù)；f i表示第i只麻雀的適應度值；f g和f w分別為當前最優(yōu)適應度和最差適應度值。

2.2 基于動態(tài)自適應levy步長的麻雀搜索算法

SSA算法在搜索最優(yōu)解時依然存在容易陷入局部最優(yōu)解以及過早收斂的問題，因此提出采用動態(tài)自適應Levy步長改進SSA算法。

Levy分布是由是由法國數(shù)學家萊維(Levy)提出的一種概率分布，Levy飛行服從Levy分布，Levy飛行可以擴大搜索空間，因此把Levy飛行引入智能優(yōu)化算法中更容易使算法避免過早收斂。Levy飛行位置更新式為

式中:為第t代的位置；⊕為點對點乘法；Levy(λ)

為隨機搜索路徑，并且滿足:Levy～u＝t-λ，1<λ≤3，在實驗中由于Levy分布較難實現(xiàn)，所以Levy分布通常由Mantegna算法來實現(xiàn)。其中的α為一固定常數(shù)，因此在搜索過程中可能存在搜尋能力較差以及精度不夠高的問題，因此引入自適應動態(tài)步長α1來代替α。尋優(yōu)初期粒子位置更新變化較大，需要較大步長，使粒子個體能快速尋找到最優(yōu)解，尋優(yōu)后期，需要較小步長來提高最優(yōu)解的精度，因此需使步長的變化呈遞減趨勢，即α1值越大則搜索步長較大，使算法更趨向于全局搜索；α1值越小則步長越小，使算法更趨向于局部尋優(yōu)。步長改進如下式[13]:

則改進后的自適應Levy步長為

式中:t為當前迭代數(shù)；tmax為最大迭代次數(shù)，exp為動態(tài)遞減因子，即隨迭代次數(shù)t的增加而減小，在尋優(yōu)過程中α值較大或較小會導致整體步長增大或減小，此時添加動態(tài)因子的作用相應削弱，當α取值足夠大或足夠小時動態(tài)因子的作用則可以忽略不計，則使得在整個尋優(yōu)過程中無法準確實現(xiàn)算法前期增大步長加強全局搜索能力，而在算法后期減小步長增強局部尋優(yōu)的目的，因此本文取α＝1，對動態(tài)因子影響最小，使成為控制步長的決定參數(shù)；

定義權(quán)重因子f:

SSA算法較其他算法本身具有更好的尋優(yōu)能力，因此在采用Levy飛行策略改進SSA算法時對種群中的部分個體進行擾動。對變異麻雀個體的選擇，采用輪盤選擇的思想，產(chǎn)生[0，1]之間的一個隨機數(shù)rand，定義慣性權(quán)重遞減因子f如式(9)，若rand>f則對當前最優(yōu)解進行動態(tài)自適應Levy飛行變異。隨迭代次數(shù)t的增加f逐漸減小，則產(chǎn)生隨機[0，1]之間的數(shù)rand大于f的可能性就越小，即上述規(guī)則可使尋優(yōu)前期對麻雀個體變異可能較大，更加有效的搜索到可能存在最優(yōu)解的區(qū)域；算法后期對個體位置變異可能較小，主要在最優(yōu)解可能存在的區(qū)域內(nèi)進行局部搜索最優(yōu)解，最大迭代次數(shù)過小可能導致算法尋優(yōu)效果變差，過大會導致算法整體運行時間變長，因此本文設(shè)置最大迭代次數(shù)tmax為50。

算法流程為:

Step 1 初始化，種群規(guī)模為N，發(fā)現(xiàn)者個數(shù)為p，偵查預警麻雀數(shù)為s，目標函數(shù)維度D，以及迭代次數(shù)。

Step 2 計算每只麻雀的適應度值f i，并對f i進行排序，選出當前最優(yōu)適應度f g和其對應位置xb，以及最差適應度值f w和其對應位置xw。

Step 3 選取適應度優(yōu)的前p個作為發(fā)現(xiàn)者，根據(jù)式(3)更新其位置。

Step 4 除發(fā)現(xiàn)者以外其余麻雀作為加入者，根據(jù)式(4)更新其位置。

Step 5 在種群中隨機選取s只麻雀作為警戒者，并根據(jù)式(5)更新其位置。

Step 6 一次迭代完成后重新計算每只麻雀的適應度值f i。

Step 7 根據(jù)判斷是否rand>f成立，選擇采用式(8)進行Levy飛行變異，產(chǎn)生新解。

Step 8 是否滿足停止條件，滿足則退出，輸出結(jié)果，否則，重復執(zhí)行Step 2～7；

3 基于多通信半徑和LSSA的節(jié)點定位算法

3.1 多通信半徑

在DV-hop算法中，只要在錨節(jié)點廣播半徑范圍內(nèi)的節(jié)點跳數(shù)均記為一跳。如圖1所示，圖中錨節(jié)點A與未知節(jié)點B、C、D間跳數(shù)均記為一跳，但AB、AC、AD的距離相差較大，采用原傳播方式記錄跳數(shù)存在較大誤差，因此引入多通信半徑進行傳播。

圖1 最大通信半徑內(nèi)節(jié)點通信圖

在算法的第一階段，錨節(jié)點傳播半徑為:

式中:R為最大通信半徑，r為廣播半徑。

3.2 多跳跳數(shù)修正

多跳傳播時，已劃分的單跳會影響多跳的值，減少多跳的誤差，但是多跳的跳數(shù)值與實際的最優(yōu)跳數(shù)依舊存在較大偏差。單一的錨節(jié)點估算出的平均跳距不能完全代表整個網(wǎng)絡的跳距情況，并且多跳情況下，未知節(jié)點與錨節(jié)點的估算距離并不是按照直線計算，節(jié)點密度低的區(qū)域節(jié)點的折線率增大，距離誤差將進一步累積，對定位效果產(chǎn)生影響[14]。

因此引入跳數(shù)修正因子[14]，將錨節(jié)點i，j之間的距離定義為d i j，節(jié)點i，j之間的真實距離與最大傳播半徑R的比值定義為相對最佳跳數(shù)H ij:

比較估算出的跳數(shù)h ij和相對最佳跳數(shù)H ij的差值，定義偏差系數(shù)σij:

σi j能夠體現(xiàn)互相通信的錨節(jié)點間估算跳數(shù)h i j與相對最佳跳數(shù)Hi j存在的差異情況。σi j越大，標志著二者之間存在更大的偏差。在通信半徑不變的情況下，估算跳數(shù)將大于或等于相對最佳跳數(shù)，利用式(13)定義差值修正系數(shù)ωi j，以優(yōu)化跳數(shù)信息減少誤差的累積。

將ωij應用于全網(wǎng)跳數(shù)估計:

式中:h xj為未知節(jié)點x到錨節(jié)點j的估計跳數(shù)，h′xj為修正后的跳數(shù)，且修正后跳數(shù)更接近于相對最佳跳數(shù)，跳數(shù)值誤差將會更小。

3.3 坐標優(yōu)化

無線傳感器網(wǎng)絡的定位問題可以抽象為求解函數(shù)最優(yōu)值問題，確定適應度函數(shù)為:

式中:(x p，y p)為已知錨節(jié)點p的坐標，d pu為未知節(jié)點u與錨節(jié)點p之間的距離。使用本文提出的LSSA算法尋求適應度函數(shù)最小值，得到的函數(shù)最小值坐標點即為優(yōu)化后的未知節(jié)點坐標。

4 仿真結(jié)果分析

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

為驗證本文算法有效性，采用MATLAB2014a進行仿真實驗。并將本文提出算法與傳統(tǒng)DV-hop算法、PSO-DV-hop算法以及文獻[9]提出的雙通信半徑算法進行比較。設(shè)定仿真范圍為100 m×100 m正方形區(qū)域，并在試驗區(qū)域內(nèi)隨機生成100個節(jié)點，具體試驗參數(shù)如表1所示。

表1 網(wǎng)絡環(huán)境及參數(shù)配置

本實驗通過改變錨節(jié)點數(shù)量、節(jié)點通信半徑以及節(jié)點總數(shù)進行實驗，驗證本文提出算法性能，并使用所有節(jié)點的歸一化平均定位誤差作為衡量定位效果的標準，計算公式如下:

式中:(x，y)為所求得未知節(jié)點坐標，(x i，y i)為未知節(jié)點實際坐標。R為通信半徑，N為未知節(jié)點個數(shù)。

4.2 實驗分析

設(shè)置節(jié)點總數(shù)為100，錨節(jié)點數(shù)量為25，節(jié)點通信半徑為30 m。本文提出算法與傳統(tǒng)DV-hop算法定位效果如圖2所示，可以看出本文提出算法估計節(jié)點位置相對傳統(tǒng)算法更加精確，本文算法估計的部分節(jié)點位置與實際節(jié)點位置重合，個別節(jié)點仍存在誤差，但整體定位誤差較小。

圖2 LSSA-DV-hop定位效果

4.2.1 定位誤差分析

在100m×100m的檢測區(qū)域內(nèi)隨機分布100個節(jié)點，設(shè)置錨節(jié)點數(shù)為20個，通信半徑為30 m，四種算法誤差如圖3所示。

圖3 各未知節(jié)點定位誤差

可以看出各節(jié)點定位誤差相比于經(jīng)典DV-hop算法、雙通信半徑算大以及PSO-DV-hop算法均為最低。DV-hop算法定位誤差平均值為9.417 8 m，雙通信半徑算法定位誤差平均值為6.736 1 m，POSDV-hop算法定位誤差平均為5.189 4 m，本文算法LSSA-DV-hop定位誤差平均值為3.462 1 m。與其他三種算法相比，LSSA-DV-hop算法定位誤差分別降低了63.23%、48.60%和12.92%。本文所提出算法的定位精度有了明顯提高。

4.2.2 錨節(jié)點數(shù)對平均定位誤差影響

在檢測區(qū)域隨機分布100個傳感器節(jié)點，通信半徑為30 m，錨節(jié)點數(shù)從5到35時，對比四種算法的定位精度，如圖4所示。

圖4 錨節(jié)點數(shù)對定位性能影響

隨著錨節(jié)點數(shù)量的增加四種算法的定位誤差整體呈下降趨勢，這是由于隨錨節(jié)點數(shù)量增加，各節(jié)點的平均跳距誤差減小，未知節(jié)點和錨節(jié)點間的距離估計更加準確。相比于其余三種算法，在同等條件LSSA-DV-hop算法誤差始終最小，并且PSO-DV-hop算法在錨節(jié)點數(shù)為5時誤差為0.322 9誤差較大。在錨節(jié)點數(shù)量為15以上時，誤差率在8%～12%之間，當錨節(jié)點個數(shù)為35時誤差最小為8.22%，此時DV-hop算法誤差、雙通信半徑算法及PSO-DV-hop算法誤差分別為27.98%、18.90%和9.42%，本文算法平均定位誤差分別降低了70.62%、56.50%和12.74%。在錨節(jié)點個數(shù)為5個～35個時算法的定位精度均有了明顯提高。

4.2.3 通信半徑對平均定位誤差影響

在檢測區(qū)域隨機分布100個傳感器節(jié)點，錨節(jié)點數(shù)量設(shè)置為30個。改變節(jié)點通信半徑由20 m到50 m，結(jié)果如圖5所示。

圖5 通信半徑對定位性能影響

隨通信半徑增加定位誤差總體呈下降趨勢，這是因為通信半徑較小時未知節(jié)點可通信區(qū)域存在錨節(jié)點數(shù)量較少，未知節(jié)點無法準確獲得自身位置。在同等條件下可以看出LSSA-DV-hop算法定位誤差始終低于其余三種算法。平均誤差在5%～29%之間，在通信半徑為50m時，平均誤差最小為5.38%，此時DV-hop算法誤差、雙通信半徑算法和POS-DV-hop算法誤差分別為27.43%、15.77%和7.52%，LSSA-DV-hop算法平均定位誤差分別降低了80.39%、65.88%和28.46%，定位誤差有了明顯的下降。

4.2.4 節(jié)點總數(shù)對平均定位誤差影響

設(shè)置通信半徑為30 m，錨節(jié)點數(shù)量為總節(jié)點數(shù)的20%，節(jié)點總數(shù)為80到160時比較三種算法定位誤差，如圖6所示。

圖6 節(jié)點總數(shù)對定位性能影響

可以看出四種算法隨節(jié)點總數(shù)增加定位誤差呈下降趨勢，這是因為隨節(jié)點總數(shù)增加網(wǎng)絡連通度提高，未知節(jié)點可以獲取更多輔助定位的信息。相同條件下本文算法誤差始終最低。LSSA-DV-hop算法定位誤差在6%～14%，在節(jié)點總數(shù)為200時，平均誤差最小為6.51%，此時DV-hop算法誤差、雙通信半徑算法和POS-DV-hop算法誤差分別為28.87%、17.56%和9.89%，本文算法平均定位誤差分別降低了77.45%、62.92%和34.18%。說明本文所提算法在各情況下定位誤差明顯小于DV-hop算法、雙通信半徑算法以及PSO-DV-hop算法。

4.2.4 算法復雜度分析

由于無線傳感器網(wǎng)絡通常資源有限的因此在設(shè)計定位算法時不能只考慮提升算法定位精度的問題，算法的復雜度也是重要因素之一。設(shè)節(jié)點總數(shù)為n，錨節(jié)點數(shù)為m，則DV-hop算法中計算節(jié)點間最小跳數(shù)的復雜度為o(n3)，計算平均跳距的復雜度為o(n)，計算錨節(jié)點與未知節(jié)點間距離的復雜度為o(m×n)。[15]文獻[9]中，在原始DV-hop算法上增加復雜度o(m×n)；PSO-DV-hop算法相較于DVhop算法復雜度增加o(n2)。本文所提算法在多通信半徑階段復雜度為o(m×n)，麻雀搜索算法階段復雜度為o(n2)。因此本文所提算法復雜度相較于DV-hop算法復雜度增加了o(n2)+o(m×n)；相較于文獻[9]算法復雜度增加了o(n2)；相較于PSO-DVhop算法復雜度增加o(m×n)，但本文所算法定位誤差降低明顯，在各情況下定位性能穩(wěn)定，明顯優(yōu)于DV-hop算法、文獻[9]所提出算法的雙通信半徑算法以及PSO-DV-hop算法。

5 總結(jié)

本文通過分析現(xiàn)有定位算法定位精度低的原因，對產(chǎn)生誤差的定位步驟進行優(yōu)化，提出了基于多通信半徑和麻雀搜索的節(jié)點定位算法。首先，在廣播階段采用多通信半徑的形式細化節(jié)點間跳數(shù)，并對多跳情況產(chǎn)生的偏差使用跳數(shù)修正因子進行修正，使平均跳距更加精確。然后，引入了尋優(yōu)能力更強的LSSA優(yōu)化算法對未知節(jié)點定位過程進行改進，使定位算法計算出的未知節(jié)點坐標更精確，仿真結(jié)果表明本文提出的LSSA-DV-hop算法定位精度明顯提高，具有良好的定位性能。