無線傳感器網絡定位研究綜述

陳俊逸　陳琳

摘要：節點定位技術是無線傳感器網絡的關鍵技術之一，而定位算法則是定位技術中的核心。在節點定位的過程中，由于節點數目、節點距離以及環境等因素，會對節點的定位精確度造成影響，基于此，提出了各種對定位算法的改進以提高節點定位的精確度。本文基于測距以及非測距兩方面介紹了各種節點定位算法，并詳細介紹了幾種比較經典和新穎的改進方法。

關鍵詞：無線傳感器網絡;節點定位技術;定位算法;質心定位算法;定位精度

中圖分類號：TP393? ? ?文獻標識碼： A

文章編號：1009-3044（2021）01-0041-02

Abstract： Node localization technology is one of the key technologies in wireless sensor networks， and localization algorithm is the core of localization technology.In the process of node localization， due to the number of nodes， the distance between nodes and the environment and other factors， the accuracy of node location will be affected. Based on this， a variety of improvements to the positioning algorithm are proposed to improve the accuracy of node positioning.This paper introduces various node localization algorithms based on ranging and non ranging， and introduces several improved methods for Centroid Localization Algorithm in detail.

Key words： wireless sensor network; node positioning technology; location algorithm; centroid localization algorithm; positioning accuracy

1 引言

無線傳感器網絡（wireless sensor network）是由大量能量、功耗有限制的傳感器節點在環境中分布組成的。這些節點可以感知周圍環境，并將這些物理信息轉換成為數字信息，進行各種計算并存儲。但是如果傳感器的位置是未知的，那么從中得到的數據基本是沒有任何實際意義的，只有在知道了自身的位置信息后，才能夠通過接收到的數據信息來了解外部的環境以及發生的事件。如果采用人工去部署傳感其網絡節點或者為每一個節點都安裝GPS，那么花費的成本將是非常龐大的，由此，就需要研究出一定的算法或措施來使傳感其網絡對其自身的節點進行定位。

1992 年 ，室內定位系統 Active Badge由AT&T Laboratories Cambridge 開發出來，后來無數的定位算法開始被研究開發出來，目前已經有大量的節點定位算法可以實現節點的自定位。每一種定位算法適用于不同的應用，在各種應用環境下都有不同的精確度。故本文以基于測距和非測距兩種前提條件來總結了近年來的一些經典定位算法，并對目前幾種與機器學習算法結合的質心定位算法的改進進行研究總結。

2 定位技術介紹

2.1? 定位技術的相關概念

一些相關概念如下：

錨節點：WSN中的已知位置信息的傳感器節點，又可稱為信標節點。

未知節點：WSN中錨節點之外的位置未知的所有節點。

通信半徑：傳感器節點可以對數據進行接收、存儲以及傳送，由于節點的傳輸距離有限，故節點的通信半徑就是節點能夠傳輸信息的最大距離。

跳數：在WSN中，當兩個無法直接通信的節點通信時所經過的中間節點的數目加1就是這兩個節點之間的跳數。

測距：測距就是通過一定的手段來獲取兩個節點之間的大致物理距離。

RSSI：一個節點發射信號，另一個節點會收到這個節點所發射的信號，這個接收信號的節點所接收到的信號強度就稱為RSSI。

2.2? 定位算法的分類

目前已經存在的定位算法分類有很多，現在介紹三種主要的分類方法[1]。

2.2.1 集中式算法和分布式算法

集中式定位算法是在傳感器網絡中設置一個中心節點，其他節點都將信息傳輸給中心節點來進行處理。此算法適用于監測和控制的應用場景，該算法精確度高，但要求中心節點有較強的計算能力和對信息的處理能力，對能量消耗較大。

分布式算法則是傳感器網絡中的各個節點互相交換信息，并自己對信息進行處理，計算出自己的位置。此算法降低了網絡的通信度，但對于節點有較高的計算能力要求和能量要求。

2.2.2 單跳算法和多跳算法

單跳算法是未知節點與錨節點直接進行數據信息的交流，計算出自身的位置，該算法簡單易行，但對錨節點的數量有要求，并且其密度需要偏高。

多跳算法則是未知節點通過一系列的節點與錨節點進行通信，從而計算出自身位置，此種算法解決了測量范圍小的問題，但是容易形成誤差的累積。

2.2.3 基于測距的算法和基于非測距的算法

基于測距的算法由測距和位置估算兩步組成。首先通過算法來測量錨節點與未知節點之間的距離，再使用三邊測量等方法來進行估算得到未知節點的估計位置。

此類算法定位精確度高，但傳感器節點需要有比較高的硬件性能。

基于非測距的算法根據網絡連通度來估計節點之間的距離。常用的基于非測距的方法有質心定位算法、Dv-Hop算法等。

3 定位算法分析

目前學者們研究的定位算法主要是分為基于測距的定位算法和基于非測距的定位算法。對于定位精確度不夠高這個問題，國內外的學者們都做了大量的研究以及對于算法的改進。接下來就介紹一些比較經典和新穎的改進算法。

3.1 基于測距的定位算法

目前，大多數學者對于基于測距的定位算法的研究都集中在基于RSSI的定位算法上，因該種算法對于節點的硬件要求以及能耗要求都比較低，但同樣的定位精確度比較低，故對其進行研究改進可以大大提升傳感器網絡節點定位的精確度。

基于RSSI測距是通過傳感器網絡中的未知節點接收到的錨節點發射的信號強度來計算路徑傳播損耗，再估算出未知節點與錨節點之間的距離。但是此種測距方法很容易受到如障礙物、反射等外界因素的干擾，從而造成定位的誤差。

楊穎輝等人提出了一種基于優化RSS測距的算法[2]。第一步先改進RSSI測距過程，選取了多個錨節點，得到它們之間的距離以及接受功率，然后將其作為參考數值，代入傳統的RSSI測距模型公式中，計算出距離的估計值，以此來降低測距誤差，之后將定位問題轉換成數學求解問題，并使用拉格朗日算法對其求解。此算法降低了定位誤差，但略微增加了算法復雜度。

龍海燕等人[3]提出的算法首先對未知節點收到的信號強度通過高斯濾波進行預處理，再通過一個小區域內的錨節點的位置信息來估計該區域的路徑損耗模型參數，即一個未知節點與三個或更多相鄰的錨節點通信，然后比較收到的RSSI值，選擇其中RSSI值最大的節點參與定位，并得到該未知節點區域內的路徑損耗模型參數，并建立經驗庫。該算法提高了定位的精確度，并且增強了測距的抗干擾性。

3.2 基于非測距的定位算法

3.2.1 質心定位算法

質心定位算法是由美國加州大學的學者研究提出來的，其原理是錨節點定期向網絡廣播自身的信息，當網絡中的未知節點收到一定數量的信息后，就用未知節點收到信息的錨節點作為多邊形頂點，由此組成的多邊形的質心就是未知節點的預估坐標。質心定位算法的優點是簡單易行。但是傳統的質心定位算法對各組數據的處理采用的權值是相等的，由于各個錨節點本身帶有的能量不同，以此估算的未知節點坐標很容易造成誤差。基于此，很多學者對其進行了研究改進，并有不錯的效果。

張維[4]等人改進的算法，就是用權值來對具有誤差的數據進行加權處理，以估算的節點坐標的誤差倒數作為權值，較小誤差的倒數對應的權值較大。此算法提高了定位的精確度。

張乙竹[5]結合k-means聚類算法對質心定位算法進行了改進。其大致思路是首先利用k-means算法對傳感器網絡中的節點進行分簇，并得到k個聚類以及每個聚類包含的節點數目n，然后將聚類中心點作為質心定位算法中的多邊形頂點，包含節點數目越多的聚類對應的權值就越大，然后再計算得到未知節點的位置。

3.2.2 DV-Hop定位算法

DV-Hop算法主要是由以下三步組成。第一步，錨節點會通過泛洪的方式將自己的信息傳輸到整個無線傳感器網絡中，網絡中的節點收到信息后會得到一個跳數就是距離錨節點距離。第二步，當錨節點獲得跳距后，會計算出一個平均跳距，然后將這個數據同樣采用泛洪的方式傳播到無線傳感器網絡中。第三步，使用一定的方法進行定位計算得到未知節點的坐標。DV-Hop算法的優點時對硬件性能的要求不是很高，缺點是對傳感器網絡中的節點分布要求比較均勻地分布，不然定位的精確度會比較差。

劉燕等人[6]將改進的蜂群算法與定位算法相結合。此算法首先改進了蜂群算法，對區域進行了限定，然后將改進優化后的蜂群算法應用到DV-Hop算法的第三步節點定位中，優化了多邊定位的執行。

朱曉娟等人[7]基于灰狼算法提出了一種改進的方式。此算法是錨節點在計算網絡的平均跳距時采用灰狼算法，并計算與其他所有錨節點之間距離，細化平均跳距。最后使用最大似然估計法對未知節點的估算坐標和真實坐標進行一個誤差的校正。

4 結論

由于在不同的環境和應用中，具體應用的傳感器網絡節點定位算法也不同，故研究出適用于普遍場景的定位算法一直是國內外學者的研究重點。本文對目前存在的定位算法做了一個比較簡單的介紹，并對其中的一種分類方法進行了較為詳細的介紹，結合一些參考文獻對于幾種改進的定位算法進行了分析和總結。并且從中我們可以發現，現在很多學者開始結合機器算法來對定位算法進行改進，并且都具有不錯的改進效果，并且都具有不錯的普遍適用性。隨著定位技術的發展以及我們生活中的需要，研究出能夠通用的定位算法是必需的，也是一定能夠成功的。

參考文獻：

[1] 呂淑芳.無線傳感器網絡節點定位研究綜述[J].傳感器與微系統，2016，35（5）：1-3，8.

[2] 楊穎輝，楊群亭，高鐵杠.基于改進RSS測距的拉格朗日優化定位算法[J].火力與指揮控制，2019，44（12）：30-34.

[3] 龍海燕，張天飛，丁嬌，等.基于RSSI的測距技術的自動修正定位算法[J].東莞理工學院學報，2019，26（1）：23-27.

[4] 張維，趙亮.基于加權質心算法的無線網絡節點定位方法[J/OL].沈陽工業大學學報：1-4[2020-09-12].http：//kns.cnki.net/kcms/detail/21.1189.T.20200909.2048.041.html.

[5] 張乙竹，周禮爭，唐瑞，等.基于K-means聚類點密度的WSNs加權質心定位算法[J].傳感器與微系統，2015，34（7）：125-127，131.

[6] 劉燕，高麗.改進人工蜂群優化的DV-Hop定位算法[J/OL].激光與光電子學進展：1-13[2020-09-12].http：//kns.cnki.net/kcms/detail/31.1690.TN.20200601.1723.131.html.

[7] 朱曉娟，陳智麗.基于灰狼算法和極大似然估計的改進DV-HOP算法[J].物聯網技術，2020，10（5）：38-42.

【通聯編輯：梁書】