基于距離修正及灰狼優化算法對DV-Hop定位的改進?

石琴琴，徐 強，張建平

(1.上海應用技術大學計算機科學與信息工程學院，上海201418；2.蘇州中科先進技術研究院有限公司，江蘇蘇州215123；3.華車科技股份有限公司，上海200127)

DV-Hop[1]是廣泛應用于無線傳感器網絡節點自定位的一種非基于直接測距的定位方法。無線傳感器網絡在物聯網應用的信息采集環節發揮著重要作用，而能量高效和節點可定位則是提供有效數據信息的前提和基礎。無需配備專門設備進行測距的定位方案因其經濟且高效的定位模式，成為當前的研究熱點。DV-Hop是一種開創性的定位方法，基于一定比例錨節點的已知位置信息與距離矢量路由傳遞實現網絡內未知節點的定位，具備了無需測距定位方案的所有優點[2]。網絡中的錨節點根據基站發出的定位需求指令或者既定的時間間隔發起消息傳遞，其余節點根據多跳路由協議獲得距離錨節點的最小跳數。未知節點與錨節點之間的距離通過由最近錨節點提供的平均每跳距離校正值和上述最小跳數相乘獲得，而后采用Lateration算法計算獲得未知節點的坐標。根據傳統DV-Hop方法的算法原理，最終的節點定位精度主要取決于節點密度、錨節點數量和網絡拓撲，因為這些因素都直接影響著未知節點與錨節點之間距離估計值的精度。當網絡具有較高的錨節點比例，節點布設密集均勻，網絡拓撲基本趨于各向同性時，網絡處于一種較為理想的狀態，距離估計值較合理，定位精度較可靠。但是，實際應用中的網絡環境往往會因為區域地形或者布設方法局限等原因，使得網絡拓撲極難達到傳統DVHop方法所需的理想狀態，故而導致算法的適用性較差，定位精度難以保證，實際可行性受限[3-4]。

盡管經典DV-Hop方法存在應用層面的缺點，但因其開創性的無需直接測距的定位思路提供了一種良好的模型設計方向，使得相關的改進策略研究廣泛開展。在保持DV-Hop算法優點的前提下，如何高效利用錨節點資源，提高距離估計精度，進而改善最終的定位精度是值得深究的問題。在國內外文獻匯總的基礎上，可將DV-Hop模型實現節點定位的步驟歸納為兩步:距離估計與位置計算，并根據這一線索對現有改進方法進行分類，大致可分為三類:第一類只針對距離估計步驟進行改進，如文獻[5-7]所述；第二類只針對位置計算步驟進行改進，如文獻[8-10]所述；第三類對兩個步驟都有改進，如文獻[11-13]所述。在第一類的改進中，現有的改進方法企圖通過算法找到一個未知節點到全網所有錨節點都適合的平均每跳距離，這一思路不適用于各向異性的網絡，只有對錨節點比例、節點布設密度等相關參數進行可行性限定后才能達到提高定位精度的效果；第二類改進，假設了所獲得的未知節點至錨節點距離的精確性，以距離為約束條件搜索未知節點的最優坐標值，在理論上可取得優于經典DVHop方法的定位精度，但脫離了距離不可能精確測量的實際；第三類改進方法在思路上較之前面兩類更為合理，在特定的實驗環境下都取得了較好的定位精度，為本文提供了良好的思路借鑒，但在針對距離修正的改進中仍然存在第一類改進的問題，仿真實驗評價了優化所得的定位精度，未對距離估計階段是否真正提高了距離精度進行定量分析。

本文提出的改進策略主要貢獻在于:①針對未知節點與錨節點之間的距離估計，采用在所有錨節點對的多跳路徑中選出與目標錨節點到此未知節點的多跳路徑最相似的一條，獨立確定未知節點與目標錨節點間的平均跳距值，以期使得估計距離盡可能接近真實距離；②在使用傳統DV-Hop方法獲得節點位置坐標后，將參與定位計算的距離與未知節點坐標同時作為待求未知數，進一步采用改進的灰狼算法[14]優化位置坐標，以期獲得提高節點定位精度的效果。

1 DV-Hop方法既有改進策略分析

分析經典DV-Hop方法的定位原理可知，計算未知節點與錨節點間距離的必要參數是平均每跳距離估值與最短路徑跳數。每一錨節點對應一個平均每跳距離估值，是通過網內其余錨節點到該錨節點間的距離和除以跳數和得到的，再轉發臨近的未知節點，據此計算未知節點與目標錨節點之間的距離。如果網絡節點分布不均勻，則采用該方法獲得的平均每跳距離估值不能合理代表未知節點與目標錨節點間的平均跳距，因此導致未知節點與錨節點之間的距離估值存在較大誤差，進而，定位算法Lateration對距離估計誤差極為敏感[15]，最終使得未知節點的坐標不能被精確估計。而無線傳感器網絡的室外應用場景一般為人員難以到達區域，節點通常采用隨機播撒或彈射等非均勻布設的方式，網絡拓撲極易呈現各向異性，降低了經典DV-Hop方法在應用層面的可行性。

針對上述DV-Hop方法的不足之處，文獻[5]提出的改進算法引入多通信半徑策略細化錨節點間的跳數，而后依照式(1)獲得每個錨節點的平均每跳距離估值；針對每一未知節點，通過剔除孤立節點，并對獲得的錨節點平均跳距值進行加權平均作為未知節點到全網錨節點的平均跳距；這一改進方法獲得了一個理論上到全網錨節點都為最優的平均每跳距離值，適用于各向同性網絡，不符合實際應用中各向異性網絡的特點，且多通信半徑發射信號會增加網絡能耗。文獻[6]引入人工蜂群算法來搜索一個適用于全網的平均每跳距離值，定位階段仍沿用經典DV-Hop中的Lateration算法，未能從本質上描述出當網絡拓樸各向異性時，不同多跳路徑平均每跳距離估值應存在的差異，且無法有效地規避人工蜂群算法陷入局部優化而導致的估計偏差。文獻[7]提出了一種改進的無偏距離估計與節點定位算法，分析期望距離和跳數的關系，建立了一種新的期望距離與跳數關系模型，根據節點通信半徑是否已知分別推導了兩種未知節點與錨節點間距離的求解形式，較之原DV-Hop算法提高了距離估計與定位的精度，但距離估計模型的建立是基于網絡各向同性的假設，對網絡布設有條件限制。文獻[8-10]對原DV-Hop方法的距離估計算法未做修正，在得出未知節點的初始坐標后，分別使用非線性共軛梯度法、Steffensen算法以及遺傳算法進行迭代優化；這些算法都可在文獻設定條件下提高未知節點的定位精度，但回避了對距離估計的誤差修正，則不能從根本上保證計算條件的合理性，不符合實際應用場景。文獻[11]針對每個未知節點，對設定跳數閾值內的錨節點的平均每跳距離估值根據相距跳數進行加權平均，以此確定每個未知節點對應的平均每跳距離估值；完成初步定位計算后，利用未知節點位置信息反推錨節點的位置，并計算所有錨節點位置誤差的加權平均值來反向修正未知節點位置。文獻[12]提出一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法，改進算法包括3個改進點:①首先基于誤差與距離生成每個錨節點對應平均每跳距離的權值，而后加權平均確定未知節點的平均每跳距離估值；②根據位置關系是否最近選擇相應的跳段距離計算方法來確定未知節點與錨節點間的跳段距離；③用改進的遺傳算法優化未知節點坐標來確定未知節點坐標的最優解。仿真結果表明，改進定位算法的性能明顯優于原DV-Hop定位算法，達到了提高定位精度的目的。文獻[13]中提出一種基于蝙蝠算法的改進方案，在距離估計階段首先求得所有錨節點對之間的距離誤差均值作為一個修正參數，并將未知節點到錨節點的跳數取倒數并歸一化，取作權值，而后使用所有錨節點保存的平均跳距加權求和作為未知節點對應的平均跳距，以此修正距離估計值；在定位階段，使用改進了適應度函數、搜索速度以及迭代規則的蝙蝠算法對定位結果進行迭代優化。文獻[11]、[12]、[13]算法的共同缺點是在距離估計階段仍然通過數學方法計算未知節點到全網錨節點適用的平均跳距，需要限定網絡拓撲；在位置計算階段以距離為約束條件搜索節點的最優位置，假設了距離估計值的精確性。

2 本文改進策略

針對原DV-Hop方法在距離估計與位置計算步驟中所采用的算法存在的不足，本文進行了如下的改進:①修正平均每跳距離估計策略，提出一種相似路徑搜索算法，為每一未知節點與目標錨節點之間的多跳路徑計算出最匹配平均每跳距離估計值，以期提高距離估計精度；②引入改進的灰狼群體智能算法對未知節點的初始位置進行優化，以期進一步提高定位精度。

2.1 相似路徑搜索算法

在距離估計階段，為未知節點到目標錨節點之間的多跳路徑匹配最相似的錨節點對之間的多跳路徑，由該最相似路徑計算出一個平均每跳距離值，作為未知節點到目標錨節點之間最優的平均每跳距離估值，進而乘以最短路徑跳數即可估計出未知節點到目標錨節點之間距離。詳細的算法步驟描述如下:

首先，將錨節點至全網節點的多跳最短路徑信息記錄為節點編號組成的集合，針對每一未知節點，其相距某個目標錨節點的最短路徑集合和其他錨節點對間的最短路徑集合進行相似度比較運算，選出相似度最高的錨節點對間路徑計算平均每跳距離值，并作為未知節點至目標錨節點的平均每跳距離估值，進而與最小跳數值相乘獲得距離估計值。算法中使用Ochiai系數[16]來衡量路徑集合間的相似度，Ochiai系數的定義如式(1)所示:

此處A和B是集合，n()表示集合包含的元素個數。

上述算法的具體步驟①～⑤如下:

①記錄未知節點至某一目標錨節點的最短路徑節點編號集合A；

②分別記錄其余錨節點至該目標錨節點的最短路徑節點編號集合B；

③分別計算集合A與集合B的Ochiai系數值；

④將Ochiai系數值最大的錨節點對間的平均每跳距離值作為未知節點至該目標錨節點的平均每跳距離估值；

⑤將步驟④獲得的平均每跳距離估值與多跳最短路徑跳數相乘計算出未知節點到該目標錨節點的距離估計值。

以圖1所示拓樸關系為例對上述步驟進行說明。 圖 1 中 a1，a2，a3，a4，a5，a6為錨節點，其余為未知節點。當估計未知節點u1到錨節點a6的距離時，首先，記錄未知節點u1到信標節點a6的最短路徑節點編號集合，其結果為:{u1，a2，u3，u6，u7，a6}；再記錄其余錨節點到錨節點a6的最短路徑節點編號集合，其結果如下:

第一路徑:{a1，u2，u3，u6，u7，a6}；

第二路徑:{a2，u3，u6，u7，a6}；

第三路徑:{a3，u4，u3，u6，u7，a6}；

第四路徑:{a4，u5，u4，u3，u6，u7，a6}；

第五路徑:{a5，u6，u7，a6}。

根據上文對集合相似度Ochiai系數的描述可計算出u1至a6路徑集合與各條錨節點對間路徑集合的相似度值為:與第一路徑集合的相似度為0.667；與第二路徑集合的相似度為0.913；與第三路徑集合的相似度為0.667；與第四路徑集合的相似度為0.617；與第五路徑集合的相似度為0.612。故采用第二路徑a2到a6間的平均每跳距離值來近似u1到a6間的平均每跳距離值，再乘以u1到a6的最小跳數獲得距離估計值。以此類推，可獲得所有未知節點到所有錨節點的距離估計值。

圖1 相似路徑搜索算法說明圖

2.2 改進的灰狼優化算法

灰狼優化算法是一種群體智能優化算法，具有結構簡單、易于實現等特點，可用于無法直接使用數學方法求解的復雜問題的求解[17]。經典DV-Hop方法在估計出未知節點到3個以上錨節點的距離后，使用Lateration算法完成定位計算。本文策略在位置計算階段，首先沿用Lateration算法獲得未知節點的初始定位值，且選擇在距離估計階段路徑相似度參數值最大的4個錨節點參加定位計算；而后列出式(2)所示的非線性方程組，使用改進的灰狼算法迭代求方程組最優解。

文獻[14]提出并分析了灰狼算法，該算法模擬自然界中灰狼的等級制度與狩獵行為，其算法思想為:灰狼是一種群居的頂級掠食者，整個狼群分為四組:α、β、δ、ω，按照等級由高到低排列，前三組引導最低級狼(ω)進行目標搜索；在搜索過程中，狼群依照一定的規律更新α、β、δ、ω的位置，最終輸出的α狼的位置信息即為目標位置。

灰狼算法在本文中用于對未知節點初始位置進行優化，詳細步驟如下:

①初始化狼群個體，將未知節點的坐標、未知節點與4個信標節點之間的距離組成未知數向量，即灰狼個體，可表示為一個 6 維向量[x，y，d1，d2，d3，d4]；每個灰狼個體的分量初始值都設置為既有的距離估計值與未知節點初始坐標值；設定最大迭代次數 max＝300。

②根據式(3)中所列適應度函數公式初始化所有灰狼個體的適應度值，式中，fitnessi為灰狼個體i的適應度值，(xi，yi)為 i的平面位置坐標，(xj，yj)為錨節點j的位置坐標，dj為未知節點到錨節點j的估計距離；選擇適應度函數值最小的3個灰狼個體，依次將它們記為 α、β、δ。

③如果α狼的向量變化已滿足迭代退出條件，或者已達既定迭代次數上限，則算法結束，輸出α狼的坐標信息，即為最終未知節點位置優化結果；否則，進入下一步驟。

④依次根據式(4)～式(7)更新ω狼的當前位置信息Xω(t)。其中，C為搖擺因子；A為收斂因子；a為控制因子，其值隨著迭代次數從2到0線性遞減；r1和r2均為[0，1]區間的隨機數；t是當前迭代次數，X(t)表示迭代t次時灰狼個體位置；max是設定的最大迭代次數。

⑤根據式(3)計算所有灰狼個體的適應度值，選出新的 α、β、δ，回到步驟③。

迭代計算完成后所得解向量中的x，y元素值即為最終求得的未知節點坐標優化值。

文獻[18]也闡述了一種灰狼算法在無線傳感器網絡未知節點位置優化中的應用，相對而言，本文應用在灰狼個體的維度表示與迭代計算過程方面進行了改進。既有應用的灰狼個體表示為僅包含未知節點坐標的二維行向量[x，y]，而本文的灰狼改進算法將未知節點至錨節點之間的距離與未知節點坐標一起看作非線性方程組的未知數，同步迭代優化，因為選擇具有最高路徑相似度的4個錨節點參加定位計算，故而灰狼個體表示為 6 維行向量[x，y，d1，d2，d3，d4]。這一改進基于DV-Hop距離估值為非精確值的考量，忽略距離估值的誤差而將其作為方程組常量會導致誤差的持續傳播，故而本文在灰狼優化步驟中將其作為具有合理初值的未知數進一步優化。

3 仿真實驗

使用MATLAB軟件編程進行算法實驗，通過對比本文算法與經典DV-Hop算法及文獻[13]中所述DV-Hop改進算法(下文簡稱IBDV-Hop)在距離估計精度、定位精度、計算量等評價指標方面的表現，證明其可行性與優越性。

3.1 實驗環境

網絡布設區域為100 m×100 m的二維平面，所有傳感器節點具有相同結構及通信半徑，節點隨機布設，自組成網。網內未知節點個數為N，網內錨節點個數為M，節點通信半徑為R，dij、＾dij分別表示節點間真實距離與估計距離，Pj、＾Pj分別表示未知節點的真實位置與估計位置，式(8)所示為歸一化的網絡距離估計精度，式(9)所示為歸一化的定位精度。

分別變換節點總數、錨節點比例和通信半徑參數值的設置來模擬不同的網絡拓樸結構，分析這些參數變化對距離估計及定位的影響規律，具體可組合為三類實驗場景:場景一固定節點總數為100，通信半徑為15 m，錨節點比例從5%漸次提高到30%；場景二固定通信半徑為15 m，錨節點比例為15%，節點總數改從100漸次提高到225；場景三固定節點總數為100，錨節點比例為15%，通信半徑從15 m提高到35 m。

3.2 實驗結果與分析

在3.1節所述三種實驗場景中，根據距離估計步驟統計的距離精度與位置計算步驟統計的定位精度對算法進行對比分析；另外，還將對比分析迭代次數與定位誤差的關系以及優化算法種群數量與定位誤差的關系；最后，通過平均時耗定量對比算法的復雜度。

3.2.1 距離估計精度

圖2～圖4分別對比了錨節點比例、節點總數及通信半徑參數變化條件下三種算法的測距精度表現。結果顯示:隨著錨節點比例的提高，本文算法較之原DV-Hop測距精度可提高約67%，較之IBDVHop測距精度可提高約35%；隨著網絡節點布設密度的增大，分別可提高約66%和33%；隨著通信半徑的增大，分別可提高約64%和38%。在各類場景下，本文算法的測距精度整體表現較高且穩定。

圖2 測距誤差vs.錨節點比例

圖3 測距誤差vs.節點總數

圖4 測距誤差通信半徑

3.2.2 定位精度

圖5～圖7分別對比了錨節點比例、節點總數及通信半徑參數變化條件下三種算法的定位精度表現。結果顯示:隨著錨節點比例的提高，本文算法較之原DV-Hop方法定位精度可提高約46%，較之IBDV-Hop定位精度可提高約15%；隨著網絡節點布設密度的增大，分別可提高約37%和19%；隨著通信半徑的增大，分別可提高約45%和20%。在各類場景下，本文算法的定位精度整體表現較高且穩定。

圖5 定位誤差vs.錨節點比例

圖6 定位誤差vs.節點總數

圖7 定位誤差vs.通信半徑

圖8 定位誤差vs.種群數量

3.2.3 種群數量與迭代次

節點總數設為100，錨節點的比例設為15%，通信半徑設為15 m。在此場景下，本文算法與IBDVHop算法就種群數量對定位精度影響的對比如圖8所示，結果表明:隨著種群數量的增加定位誤差不斷降低，IBDV-Hop算法在種群數量達到100之后定位誤差即無明顯降低，而本文算法在種群數量達到60之后定位誤差無明顯降低，本文算法相比IBDV-Hop算法在優化定位階段的時耗更低。本文算法與IBDV-Hop算法就迭代次數對定位精度影響的對比如圖9所示，結果表明:隨著迭代次數的增加定位誤差不斷降低，IBDV-Hop算法在迭代次數達到160之后定位誤差即無明顯降低，而本文算法在迭代次數達到120之后定位誤差無明顯降低，本文算法相比IBDV-Hop算法在優化定位階段的收斂速度更快。

圖9 定位誤差vs.迭代次數

3.2.4 時耗

表1比較了本文算法、經典DV-Hop算法以及IBDV-Hop算法的計算量，用以秒為單位的時耗值統計，由所有模擬場景下的時耗平均值獲得。結果顯示:本文算法時耗約為相原DV-Hop算法的1.7倍，約為IBDV-Hop算法的1.3倍。在當前高性能數據處理平臺的支持下，本文算法小幅增加的時耗可忽略不計，但可觀地提高了定位精度。

表1 算法時耗對比

4 結束語

以應用于無線傳感器網絡節點定位的經典DVHop方法為研究對象，提出了一種基于距離修正及灰狼優化算法的改進策略。距離修正采用一種相似路徑搜索算法，實現了未知節點與目標錨節點之間平均每跳距離計算的局部化，改進了原方法使用所有錨節點參與校正值計算存在的全局平均問題；灰狼優化算法起到了進一步校正未知節點初始位置，提高Lateration算法定位精度的作用。仿真實驗表明，本文策略較好地解決了原DV-Hop方法在各向異性網絡拓樸條件下的適用性問題，極大地提高了原方法的定位精度，并且性能優于文獻[13]中提出的典型改進算法。

在后續研究中將進一步深入研究以下問題:①錨節點位置對網絡拓樸的控制規律；②其他群體智能算法在節點位置優化中的應用改進；③更真實的應用場景模擬策略。