基于多通信半徑和麻雀搜索的節點定位算法*

彭 鐸楊雅文高玉蔚王嬋飛

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

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

1 概述

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

1.1 DV-hop算法

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

①計算最小跳數

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

②估計到各錨節點的平均跳距

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

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

③未知節點位置估計

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

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

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

2.1 麻雀搜索算法[12]

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

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

發現者數量為20%，在迭代過程中發現者的位置更新定義為:

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

除發現者外其余麻雀為加入者，根據下式進行位置更新:

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

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

2.2 基于動態自適應levy步長的麻雀搜索算法

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

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

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

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

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

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

定義權重因子f:

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

算法流程為:

Step 1 初始化，種群規模為N，發現者個數為p，偵查預警麻雀數為s，目標函數維度D，以及迭代次數。

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

Step 3 選取適應度優的前p個作為發現者，根據式(3)更新其位置。

Step 4 除發現者以外其余麻雀作為加入者，根據式(4)更新其位置。

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

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

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

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

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

3.1 多通信半徑

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

圖1 最大通信半徑內節點通信圖

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

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

3.2 多跳跳數修正

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

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

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

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

將ωij應用于全網跳數估計:

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

3.3 坐標優化

無線傳感器網絡的定位問題可以抽象為求解函數最優值問題，確定適應度函數為:

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

4 仿真結果分析

4.1 實驗參數設置

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

表1 網絡環境及參數配置

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

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

4.2 實驗分析

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

圖2 LSSA-DV-hop定位效果

4.2.1 定位誤差分析

在100m×100m的檢測區域內隨機分布100個節點，設置錨節點數為20個，通信半徑為30 m，四種算法誤差如圖3所示。

圖3 各未知節點定位誤差

可以看出各節點定位誤差相比于經典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 錨節點數對平均定位誤差影響

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

圖4 錨節點數對定位性能影響

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

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

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

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

隨通信半徑增加定位誤差總體呈下降趨勢，這是因為通信半徑較小時未知節點可通信區域存在錨節點數量較少，未知節點無法準確獲得自身位置。在同等條件下可以看出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 節點總數對平均定位誤差影響

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

圖6 節點總數對定位性能影響

可以看出四種算法隨節點總數增加定位誤差呈下降趨勢，這是因為隨節點總數增加網絡連通度提高，未知節點可以獲取更多輔助定位的信息。相同條件下本文算法誤差始終最低。LSSA-DV-hop算法定位誤差在6%～14%，在節點總數為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 算法復雜度分析

由于無線傳感器網絡通常資源有限的因此在設計定位算法時不能只考慮提升算法定位精度的問題，算法的復雜度也是重要因素之一。設節點總數為n，錨節點數為m，則DV-hop算法中計算節點間最小跳數的復雜度為o(n3)，計算平均跳距的復雜度為o(n)，計算錨節點與未知節點間距離的復雜度為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)，但本文所算法定位誤差降低明顯，在各情況下定位性能穩定，明顯優于DV-hop算法、文獻[9]所提出算法的雙通信半徑算法以及PSO-DV-hop算法。

5 總結

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