無線傳感器網(wǎng)絡(luò)定位研究綜述

陳俊逸　陳琳

摘要：節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，而定位算法則是定位技術(shù)中的核心。在節(jié)點(diǎn)定位的過程中，由于節(jié)點(diǎn)數(shù)目、節(jié)點(diǎn)距離以及環(huán)境等因素，會(huì)對(duì)節(jié)點(diǎn)的定位精確度造成影響，基于此，提出了各種對(duì)定位算法的改進(jìn)以提高節(jié)點(diǎn)定位的精確度。本文基于測(cè)距以及非測(cè)距兩方面介紹了各種節(jié)點(diǎn)定位算法，并詳細(xì)介紹了幾種比較經(jīng)典和新穎的改進(jìn)方法。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位技術(shù);定位算法;質(zhì)心定位算法;定位精度

中圖分類號(hào)：TP393? ? ?文獻(xiàn)標(biāo)識(shí)碼： A

文章編號(hào)：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 引言

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

1992 年 ，室內(nèi)定位系統(tǒng) Active Badge由AT&T Laboratories Cambridge 開發(fā)出來，后來無數(shù)的定位算法開始被研究開發(fā)出來，目前已經(jīng)有大量的節(jié)點(diǎn)定位算法可以實(shí)現(xiàn)節(jié)點(diǎn)的自定位。每一種定位算法適用于不同的應(yīng)用，在各種應(yīng)用環(huán)境下都有不同的精確度。故本文以基于測(cè)距和非測(cè)距兩種前提條件來總結(jié)了近年來的一些經(jīng)典定位算法，并對(duì)目前幾種與機(jī)器學(xué)習(xí)算法結(jié)合的質(zhì)心定位算法的改進(jìn)進(jìn)行研究總結(jié)。

2 定位技術(shù)介紹

2.1? 定位技術(shù)的相關(guān)概念

一些相關(guān)概念如下：

錨節(jié)點(diǎn)：WSN中的已知位置信息的傳感器節(jié)點(diǎn)，又可稱為信標(biāo)節(jié)點(diǎn)。

未知節(jié)點(diǎn)：WSN中錨節(jié)點(diǎn)之外的位置未知的所有節(jié)點(diǎn)。

通信半徑：傳感器節(jié)點(diǎn)可以對(duì)數(shù)據(jù)進(jìn)行接收、存儲(chǔ)以及傳送，由于節(jié)點(diǎn)的傳輸距離有限，故節(jié)點(diǎn)的通信半徑就是節(jié)點(diǎn)能夠傳輸信息的最大距離。

跳數(shù)：在WSN中，當(dāng)兩個(gè)無法直接通信的節(jié)點(diǎn)通信時(shí)所經(jīng)過的中間節(jié)點(diǎn)的數(shù)目加1就是這兩個(gè)節(jié)點(diǎn)之間的跳數(shù)。

測(cè)距：測(cè)距就是通過一定的手段來獲取兩個(gè)節(jié)點(diǎn)之間的大致物理距離。

RSSI：一個(gè)節(jié)點(diǎn)發(fā)射信號(hào)，另一個(gè)節(jié)點(diǎn)會(huì)收到這個(gè)節(jié)點(diǎn)所發(fā)射的信號(hào)，這個(gè)接收信號(hào)的節(jié)點(diǎn)所接收到的信號(hào)強(qiáng)度就稱為RSSI。

2.2? 定位算法的分類

目前已經(jīng)存在的定位算法分類有很多，現(xiàn)在介紹三種主要的分類方法[1]。

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

集中式定位算法是在傳感器網(wǎng)絡(luò)中設(shè)置一個(gè)中心節(jié)點(diǎn)，其他節(jié)點(diǎn)都將信息傳輸給中心節(jié)點(diǎn)來進(jìn)行處理。此算法適用于監(jiān)測(cè)和控制的應(yīng)用場(chǎng)景，該算法精確度高，但要求中心節(jié)點(diǎn)有較強(qiáng)的計(jì)算能力和對(duì)信息的處理能力，對(duì)能量消耗較大。

分布式算法則是傳感器網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)互相交換信息，并自己對(duì)信息進(jìn)行處理，計(jì)算出自己的位置。此算法降低了網(wǎng)絡(luò)的通信度，但對(duì)于節(jié)點(diǎn)有較高的計(jì)算能力要求和能量要求。

2.2.2 單跳算法和多跳算法

單跳算法是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)直接進(jìn)行數(shù)據(jù)信息的交流，計(jì)算出自身的位置，該算法簡(jiǎn)單易行，但對(duì)錨節(jié)點(diǎn)的數(shù)量有要求，并且其密度需要偏高。

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

2.2.3 基于測(cè)距的算法和基于非測(cè)距的算法

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

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

基于非測(cè)距的算法根據(jù)網(wǎng)絡(luò)連通度來估計(jì)節(jié)點(diǎn)之間的距離。常用的基于非測(cè)距的方法有質(zhì)心定位算法、Dv-Hop算法等。

3 定位算法分析

目前學(xué)者們研究的定位算法主要是分為基于測(cè)距的定位算法和基于非測(cè)距的定位算法。對(duì)于定位精確度不夠高這個(gè)問題，國(guó)內(nèi)外的學(xué)者們都做了大量的研究以及對(duì)于算法的改進(jìn)。接下來就介紹一些比較經(jīng)典和新穎的改進(jìn)算法。

3.1 基于測(cè)距的定位算法

目前，大多數(shù)學(xué)者對(duì)于基于測(cè)距的定位算法的研究都集中在基于RSSI的定位算法上，因該種算法對(duì)于節(jié)點(diǎn)的硬件要求以及能耗要求都比較低，但同樣的定位精確度比較低，故對(duì)其進(jìn)行研究改進(jìn)可以大大提升傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的精確度。

基于RSSI測(cè)距是通過傳感器網(wǎng)絡(luò)中的未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)發(fā)射的信號(hào)強(qiáng)度來計(jì)算路徑傳播損耗，再估算出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離。但是此種測(cè)距方法很容易受到如障礙物、反射等外界因素的干擾，從而造成定位的誤差。

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

龍海燕等人[3]提出的算法首先對(duì)未知節(jié)點(diǎn)收到的信號(hào)強(qiáng)度通過高斯濾波進(jìn)行預(yù)處理，再通過一個(gè)小區(qū)域內(nèi)的錨節(jié)點(diǎn)的位置信息來估計(jì)該區(qū)域的路徑損耗模型參數(shù)，即一個(gè)未知節(jié)點(diǎn)與三個(gè)或更多相鄰的錨節(jié)點(diǎn)通信，然后比較收到的RSSI值，選擇其中RSSI值最大的節(jié)點(diǎn)參與定位，并得到該未知節(jié)點(diǎn)區(qū)域內(nèi)的路徑損耗模型參數(shù)，并建立經(jīng)驗(yàn)庫。該算法提高了定位的精確度，并且增強(qiáng)了測(cè)距的抗干擾性。

3.2 基于非測(cè)距的定位算法

3.2.1 質(zhì)心定位算法

質(zhì)心定位算法是由美國(guó)加州大學(xué)的學(xué)者研究提出來的，其原理是錨節(jié)點(diǎn)定期向網(wǎng)絡(luò)廣播自身的信息，當(dāng)網(wǎng)絡(luò)中的未知節(jié)點(diǎn)收到一定數(shù)量的信息后，就用未知節(jié)點(diǎn)收到信息的錨節(jié)點(diǎn)作為多邊形頂點(diǎn)，由此組成的多邊形的質(zhì)心就是未知節(jié)點(diǎn)的預(yù)估坐標(biāo)。質(zhì)心定位算法的優(yōu)點(diǎn)是簡(jiǎn)單易行。但是傳統(tǒng)的質(zhì)心定位算法對(duì)各組數(shù)據(jù)的處理采用的權(quán)值是相等的，由于各個(gè)錨節(jié)點(diǎn)本身帶有的能量不同，以此估算的未知節(jié)點(diǎn)坐標(biāo)很容易造成誤差?；诖?，很多學(xué)者對(duì)其進(jìn)行了研究改進(jìn)，并有不錯(cuò)的效果。

張維[4]等人改進(jìn)的算法，就是用權(quán)值來對(duì)具有誤差的數(shù)據(jù)進(jìn)行加權(quán)處理，以估算的節(jié)點(diǎn)坐標(biāo)的誤差倒數(shù)作為權(quán)值，較小誤差的倒數(shù)對(duì)應(yīng)的權(quán)值較大。此算法提高了定位的精確度。

張乙竹[5]結(jié)合k-means聚類算法對(duì)質(zhì)心定位算法進(jìn)行了改進(jìn)。其大致思路是首先利用k-means算法對(duì)傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分簇，并得到k個(gè)聚類以及每個(gè)聚類包含的節(jié)點(diǎn)數(shù)目n，然后將聚類中心點(diǎn)作為質(zhì)心定位算法中的多邊形頂點(diǎn)，包含節(jié)點(diǎn)數(shù)目越多的聚類對(duì)應(yīng)的權(quán)值就越大，然后再計(jì)算得到未知節(jié)點(diǎn)的位置。

3.2.2 DV-Hop定位算法

DV-Hop算法主要是由以下三步組成。第一步，錨節(jié)點(diǎn)會(huì)通過泛洪的方式將自己的信息傳輸?shù)秸麄€(gè)無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的節(jié)點(diǎn)收到信息后會(huì)得到一個(gè)跳數(shù)就是距離錨節(jié)點(diǎn)距離。第二步，當(dāng)錨節(jié)點(diǎn)獲得跳距后，會(huì)計(jì)算出一個(gè)平均跳距，然后將這個(gè)數(shù)據(jù)同樣采用泛洪的方式傳播到無線傳感器網(wǎng)絡(luò)中。第三步，使用一定的方法進(jìn)行定位計(jì)算得到未知節(jié)點(diǎn)的坐標(biāo)。DV-Hop算法的優(yōu)點(diǎn)時(shí)對(duì)硬件性能的要求不是很高，缺點(diǎn)是對(duì)傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)分布要求比較均勻地分布，不然定位的精確度會(huì)比較差。

劉燕等人[6]將改進(jìn)的蜂群算法與定位算法相結(jié)合。此算法首先改進(jìn)了蜂群算法，對(duì)區(qū)域進(jìn)行了限定，然后將改進(jìn)優(yōu)化后的蜂群算法應(yīng)用到DV-Hop算法的第三步節(jié)點(diǎn)定位中，優(yōu)化了多邊定位的執(zhí)行。

朱曉娟等人[7]基于灰狼算法提出了一種改進(jìn)的方式。此算法是錨節(jié)點(diǎn)在計(jì)算網(wǎng)絡(luò)的平均跳距時(shí)采用灰狼算法，并計(jì)算與其他所有錨節(jié)點(diǎn)之間距離，細(xì)化平均跳距。最后使用最大似然估計(jì)法對(duì)未知節(jié)點(diǎn)的估算坐標(biāo)和真實(shí)坐標(biāo)進(jìn)行一個(gè)誤差的校正。

4 結(jié)論

由于在不同的環(huán)境和應(yīng)用中，具體應(yīng)用的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法也不同，故研究出適用于普遍場(chǎng)景的定位算法一直是國(guó)內(nèi)外學(xué)者的研究重點(diǎn)。本文對(duì)目前存在的定位算法做了一個(gè)比較簡(jiǎn)單的介紹，并對(duì)其中的一種分類方法進(jìn)行了較為詳細(xì)的介紹，結(jié)合一些參考文獻(xiàn)對(duì)于幾種改進(jìn)的定位算法進(jìn)行了分析和總結(jié)。并且從中我們可以發(fā)現(xiàn)，現(xiàn)在很多學(xué)者開始結(jié)合機(jī)器算法來對(duì)定位算法進(jìn)行改進(jìn)，并且都具有不錯(cuò)的改進(jìn)效果，并且都具有不錯(cuò)的普遍適用性。隨著定位技術(shù)的發(fā)展以及我們生活中的需要，研究出能夠通用的定位算法是必需的，也是一定能夠成功的。

參考文獻(xiàn)：

[1] 呂淑芳.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究綜述[J].傳感器與微系統(tǒng)，2016，35（5）：1-3，8.

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

[3] 龍海燕，張?zhí)祜w，丁嬌，等.基于RSSI的測(cè)距技術(shù)的自動(dòng)修正定位算法[J].東莞理工學(xué)院學(xué)報(bào)，2019，26（1）：23-27.

[4] 張維，趙亮.基于加權(quán)質(zhì)心算法的無線網(wǎng)絡(luò)節(jié)點(diǎn)定位方法[J/OL].沈陽工業(yè)大學(xué)學(xué)報(bào)：1-4[2020-09-12].http：//kns.cnki.net/kcms/detail/21.1189.T.20200909.2048.041.html.

[5] 張乙竹，周禮爭(zhēng)，唐瑞，等.基于K-means聚類點(diǎn)密度的WSNs加權(quán)質(zhì)心定位算法[J].傳感器與微系統(tǒng)，2015，34（7）：125-127，131.

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

[7] 朱曉娟，陳智麗.基于灰狼算法和極大似然估計(jì)的改進(jìn)DV-HOP算法[J].物聯(lián)網(wǎng)技術(shù)，2020，10（5）：38-42.

【通聯(lián)編輯：梁書】