基于改進(jìn)質(zhì)心算法的無線傳感器網(wǎng)絡(luò)定位研究

李 昊，柏 植，由 佳，郝保明

(宿州學(xué)院 機(jī)械與電子工程學(xué)院，安徽 宿州 234000)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)是由大量的無線傳感器組成的，采用單跳或者多跳的方式完成數(shù)據(jù)的傳輸.WSNs可以工作在條件比較惡劣的環(huán)境，代替人工進(jìn)行數(shù)據(jù)的采集.由于傳感器的數(shù)量比較多，投放的位置比較復(fù)雜，傳感器節(jié)點(diǎn)的位置確定尤為重要.因此，無線傳感器網(wǎng)絡(luò)定位研究是當(dāng)今研究的熱點(diǎn)問題[1].

無線傳感器網(wǎng)絡(luò)定位算法一般分為兩類：基于距離的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位和基于能量的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位.基于距離的節(jié)點(diǎn)定位算法需要知道兩個(gè)節(jié)點(diǎn)之間的相對(duì)方向和相對(duì)距離來確定節(jié)點(diǎn)坐標(biāo).基于能量的節(jié)點(diǎn)定位算法是通過節(jié)點(diǎn)的位置移動(dòng)接收到的相鄰節(jié)點(diǎn)的能量大小來確定節(jié)點(diǎn)的位置[2].其中，基于能量的節(jié)點(diǎn)定位算法由于能夠減少網(wǎng)絡(luò)的能量消耗從而達(dá)到延長(zhǎng)整個(gè)網(wǎng)絡(luò)生命周期的目的而得到了廣泛的研究.目前已有的典型算法有：質(zhì)心法、凸規(guī)則定位法、DV-Hop算法、APIT算法和MAP定位算法等.

本文對(duì)傳統(tǒng)的質(zhì)心算法進(jìn)行了改進(jìn)，提出了一種基于RSSI的改進(jìn)加權(quán)質(zhì)心定位算法，提高了節(jié)點(diǎn)的定位精度.

1 無線傳感器網(wǎng)絡(luò)

無線傳感器網(wǎng)絡(luò)是一種新生的不需設(shè)備支持的網(wǎng)絡(luò)系統(tǒng)，一般由許多匯聚在監(jiān)測(cè)區(qū)域的傳感器節(jié)點(diǎn)和在區(qū)域附近的匯聚節(jié)點(diǎn)構(gòu)成[3].雖然傳感器節(jié)點(diǎn)所占空間小，但是它在這里擔(dān)著重要角色，例如數(shù)據(jù)收集器、數(shù)據(jù)傳輸站或簇頭節(jié)點(diǎn).它們身上配有傳感器、處理器和收發(fā)器，可以接收信息、處理信息以及向匯聚節(jié)點(diǎn)傳送信息.互聯(lián)網(wǎng)將收到的信息整合后發(fā)送到用戶終端[4].無線傳感器網(wǎng)絡(luò)基本結(jié)構(gòu)圖如圖1所示.

圖1 無線傳感器網(wǎng)絡(luò)基本結(jié)構(gòu)圖

無線傳感器節(jié)點(diǎn)的四個(gè)部分如圖2所示.感知模塊中的傳感器根據(jù)接收的現(xiàn)象產(chǎn)生信號(hào)，模/數(shù)轉(zhuǎn)換器將信號(hào)轉(zhuǎn)為僅表示大小的信號(hào)傳到處理模塊.信息處理模塊負(fù)責(zé)處理傳來的信號(hào)，并保存到存儲(chǔ)器中.無線通訊模塊將信號(hào)轉(zhuǎn)為模擬信號(hào)再發(fā)送出去，與其他傳感器節(jié)點(diǎn)取得通信[5].電源模塊是為整個(gè)節(jié)點(diǎn)供電的模塊.另外，針對(duì)實(shí)際問題中不同的需求，傳感器節(jié)點(diǎn)還可以添加其他所需的模塊.

圖2 無線傳感器節(jié)點(diǎn)的構(gòu)成

無線傳感器網(wǎng)絡(luò)一般采用單跳或者多跳的方式完成數(shù)據(jù)的發(fā)送.單跳網(wǎng)絡(luò)結(jié)構(gòu)是指每一個(gè)傳感器的節(jié)點(diǎn)都可以直接將信息傳送給匯聚節(jié)點(diǎn)，如圖3所示.但是，節(jié)點(diǎn)用于通信所耗費(fèi)的能量太多，為了不浪費(fèi)能量、最大限度提高網(wǎng)絡(luò)壽命，務(wù)必要降低傳送的數(shù)據(jù)量，并且發(fā)射距離也要進(jìn)行相應(yīng)的縮短[6].多跳的傳輸方式可以有效地解決能量消耗過多的問題，傳感器節(jié)點(diǎn)不再單獨(dú)直接將信息傳給匯聚節(jié)點(diǎn)，而是發(fā)送給彼此連接的網(wǎng)絡(luò)中間節(jié)點(diǎn)，由它們?cè)賹⑿畔鹘o匯聚節(jié)點(diǎn)，多跳網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示.

圖3 單跳網(wǎng)絡(luò)結(jié)構(gòu)

圖4 多跳網(wǎng)絡(luò)結(jié)構(gòu)

2 傳統(tǒng)質(zhì)心定位算法

2.1 傳統(tǒng)質(zhì)心定位算法概述

基于距離無關(guān)的定位是根據(jù)網(wǎng)絡(luò)連通性來完成定位估量，無需額外配備設(shè)備.本文以質(zhì)心定位算法為論述重點(diǎn).

質(zhì)心算法原理圖如圖5所示，盲節(jié)點(diǎn)P(x,y)可以接收并記錄來自錨節(jié)點(diǎn)A(x1,y1)、B(x2,y2)、C(x3,y3)、D(x4,y4)、E(x5,y5)發(fā)送的信息，通過式(1)求解可得盲節(jié)點(diǎn)坐標(biāo).

圖5 質(zhì)心算法原理圖

(1)

由以上內(nèi)容可知，質(zhì)心法有優(yōu)點(diǎn)也有缺點(diǎn)，優(yōu)點(diǎn)是算法簡(jiǎn)易，延展性好，但定位精度低，取決于錨節(jié)點(diǎn)在范圍內(nèi)的分布數(shù)目，并不是十分的精確.未知節(jié)點(diǎn)獲取位置信息，將高度連接的信標(biāo)節(jié)點(diǎn)添加到集合中，所有連通的信標(biāo)節(jié)點(diǎn)都以其位置作為圓心，距離為半徑作圓，則需要知道位置信息的節(jié)點(diǎn)就在圓的交集中.質(zhì)心法只用到信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)，所以它的復(fù)雜度是由信標(biāo)節(jié)點(diǎn)的密度決定的，具有可擴(kuò)展性[7].

在遇到實(shí)際定位問題時(shí)，參考節(jié)點(diǎn)存在著分布不均的問題，那么如果采用質(zhì)心法，誤差是肯定存在的.當(dāng)節(jié)點(diǎn)均勻分布或者信標(biāo)節(jié)點(diǎn)數(shù)量足夠多時(shí)，定位的精度好，消耗也相對(duì)較高[8].相反，定位精度低，成本也低.因此，本文的研究重點(diǎn)是在不增加大量消耗的前提下提高定位的精度.

2.2 傳統(tǒng)質(zhì)心定位算法仿真與分析

研究給出一個(gè)固定的區(qū)域，然后保持通信半徑或者節(jié)點(diǎn)數(shù)其中一個(gè)指標(biāo)不變，另一個(gè)指標(biāo)進(jìn)行變化，根據(jù)仿真圖分析定位誤差的變化情況.

首先，給定了一個(gè)100*100 m2的監(jiān)測(cè)范圍里節(jié)點(diǎn)隨機(jī)分布，其中有部分錨節(jié)點(diǎn)以及一個(gè)未知節(jié)點(diǎn)，且未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的通信半徑一樣，均為R.

(1)半徑為20 m時(shí)，由圖6可看出，信標(biāo)節(jié)點(diǎn)與總節(jié)點(diǎn)的比例增加，定位誤差隨之降低，后變化緩慢.節(jié)點(diǎn)總數(shù)為500的定位誤差比節(jié)點(diǎn)總數(shù)為100和300的定位誤差要小，說明半徑為一定值時(shí)，節(jié)點(diǎn)數(shù)遞增，精確度更高.

圖6 平均定位誤差與節(jié)點(diǎn)總數(shù)關(guān)系圖

(2)當(dāng)節(jié)點(diǎn)總數(shù)為100個(gè)，半徑分別為10 m、30 m、50 m時(shí).由圖7可得出，半徑愈大，其定位誤差愈小，在本次仿真中半徑為50 m的定位誤差最小.錨節(jié)點(diǎn)的數(shù)目增加，其與總節(jié)點(diǎn)數(shù)比例越大，定位誤差則越小.

圖7 平均定位誤差與節(jié)點(diǎn)通信半徑關(guān)系圖

3 基于RSSI的改進(jìn)加權(quán)質(zhì)心定位算法

質(zhì)心定位算法由于其信標(biāo)節(jié)點(diǎn)數(shù)量的不同和分布不均，定位產(chǎn)生的誤差是不可規(guī)避的，相比之下，成本高的測(cè)距算法就有較高的定位精度[9].針對(duì)這兩種算法的優(yōu)缺點(diǎn)，本文提出了一種基于RSSI測(cè)距的加權(quán)質(zhì)心算法，定位精度得到提高的同時(shí)，成本不會(huì)超出預(yù)算.

3.1 RSSI的測(cè)距模型

在節(jié)點(diǎn)定位中，通過三邊測(cè)量法，未知節(jié)點(diǎn)能通過接收到與其通信的錨節(jié)點(diǎn)傳來的位置信息算出自己的坐標(biāo).三邊測(cè)量法示意圖如圖8所示.

圖8 三邊測(cè)量法示意圖

假設(shè)未知節(jié)點(diǎn)M的位置為(x,y)，令已知的三個(gè)信標(biāo)節(jié)點(diǎn)A、B、C的坐標(biāo)分別為(x1,y1)、(x2,y2)和(x3,y3)，它們距離能夠通信的未知節(jié)點(diǎn)M的間距為d1、d2和d3.由已知信息可得：

(2)

由下式可算出節(jié)點(diǎn)M的坐標(biāo)：

(3)

但是，非理想情況下，由于環(huán)境因素的影響，導(dǎo)致誤差的存在，以三個(gè)錨節(jié)點(diǎn)為圓心、距離為半徑畫的三個(gè)圓不一定交于一點(diǎn)，例如圖9，這時(shí)候上述方程組在陰影區(qū)內(nèi)能求得出解，且三個(gè)圓相交部分的面積越大，定位精度就越低，所以這個(gè)方法不是很常使用.

圖9 非理想情況下的三邊測(cè)量法示意圖

基于RSSI測(cè)距定位的流程圖如圖10所示.

圖10 基于RSSI測(cè)距定位流程圖

接收的信號(hào)強(qiáng)度指示，即RSSI，是依據(jù)能進(jìn)行通信的信號(hào)能量的強(qiáng)度來判斷間距[10].RSSI值的大小依賴于距離，節(jié)點(diǎn)之間的距離可以使用信號(hào)和距離之間的衰減模型來計(jì)算.在信號(hào)發(fā)送過程中，若距離過大或者存在障礙物等影響，RSSI值會(huì)有誤差.所以，從相同的時(shí)間間隔內(nèi)采樣得出七組數(shù)據(jù)，并計(jì)算出其算術(shù)平均值.

(4)

當(dāng)應(yīng)用于現(xiàn)實(shí)時(shí)，電磁波傳輸過程中會(huì)有損耗，其實(shí)際值與理論值會(huì)產(chǎn)生偏差.其損耗公式為：

(5)

(6)

其中d0為確定距離；d為接收端和發(fā)射端的間距；RSSI(d)指從接收端到發(fā)射端這段距離能產(chǎn)生的信號(hào)強(qiáng)弱值；RSSI(d0)指離發(fā)射端的距離為已知間距時(shí)獲取的RSSI值；ε和k是系數(shù)，為一定值.

3.2 基于RSSI的加權(quán)質(zhì)心定位算法基本思想

由于傳統(tǒng)的質(zhì)心算法只能對(duì)與未知節(jié)點(diǎn)產(chǎn)生通信的節(jié)點(diǎn)坐標(biāo)進(jìn)行平均，與未知節(jié)點(diǎn)不能產(chǎn)生通信的信標(biāo)節(jié)點(diǎn)的位置信息考慮不到，并且從節(jié)點(diǎn)接收到的信息不能得到完全的利用.因此，在改進(jìn)的時(shí)候，注意信標(biāo)節(jié)點(diǎn)在不同點(diǎn)上對(duì)未知節(jié)點(diǎn)坐標(biāo)的影響.

將接收信號(hào)強(qiáng)弱的值轉(zhuǎn)變?yōu)榫嚯x，對(duì)節(jié)點(diǎn)的影響和距離是一對(duì)相反的參數(shù)，距離增加，對(duì)未知節(jié)點(diǎn)的作用減小，反之亦然.因此，在傳統(tǒng)質(zhì)心定位算法中加入1/d的權(quán)值，形成一種加權(quán)的定位算法.

基于RSSI的加權(quán)質(zhì)心定位算法流程圖如圖11所示.

圖11 基于RSSI測(cè)距的加權(quán)質(zhì)心定位算法

改進(jìn)后的加權(quán)質(zhì)心定位算法的公式如下：

(7)

3.3 仿真環(huán)境步驟及結(jié)果分析

仿真給出100*100 m2的固定監(jiān)測(cè)區(qū)域，分別改變節(jié)點(diǎn)的通信半徑或錨節(jié)點(diǎn)數(shù)目來觀察改進(jìn)后的質(zhì)心定位算法隨著指標(biāo)變化而變化的情況.

(1)當(dāng)節(jié)點(diǎn)總數(shù)為100時(shí)，對(duì)信標(biāo)節(jié)點(diǎn)數(shù)為8、14和20分別進(jìn)行仿真.仿真圖12表明，當(dāng)通信半徑取一定值、信標(biāo)節(jié)點(diǎn)n=8時(shí)，其平均誤差為8.16，比信標(biāo)節(jié)點(diǎn)為14和20時(shí)分別高出1.56和2.26.說明錨節(jié)點(diǎn)數(shù)多其定位誤差小，通信半徑增大，定位誤差也逐漸增大.

圖12 節(jié)點(diǎn)通信半徑不同的定位誤差

(2)節(jié)點(diǎn)總數(shù)為100，對(duì)通信半徑分別為10 m、30 m和50 m時(shí)進(jìn)行仿真.如圖13，錨節(jié)點(diǎn)的數(shù)目增多，誤差減小并趨于水平.當(dāng)通信半徑為10 m時(shí)，其平均定位誤差為9.6 m，比通信半徑為30 m和50 m要高.可得半徑越大，定位精度依賴于錨節(jié)點(diǎn)數(shù)目增多而提高.

圖13 錨節(jié)點(diǎn)數(shù)目不同的定位誤差

單獨(dú)對(duì)基于RSSI加權(quán)的質(zhì)心法進(jìn)行Matlab仿真，結(jié)果如圖14所示.可以看出當(dāng)參考節(jié)點(diǎn)之間的距離比較近時(shí)，它的平均誤差率隨著距離的增加降低幅度顯著,距離逐漸增加時(shí)，誤差也跟著增加.從圖15可以看出間距較小時(shí)，預(yù)測(cè)位置與實(shí)際位置相差無幾.但是，當(dāng)間距超過一定值時(shí)，平均誤差率隨著間距的增加而增加，預(yù)測(cè)的位置和實(shí)際位置偏差變大.

圖14 改變距離對(duì)平均誤差率的影響

圖15 改變距離對(duì)預(yù)測(cè)位置的影響

此外，還將傳統(tǒng)的質(zhì)心法和改進(jìn)后的算法放在一起比較，如圖16所示.可以看出兩種定位算法在信標(biāo)節(jié)點(diǎn)總數(shù)增加到一定值時(shí)，其定位誤差變化逐漸穩(wěn)定，是由于信標(biāo)節(jié)點(diǎn)數(shù)增多系統(tǒng)達(dá)到飽和狀態(tài).雖然兩者的變化趨向大體相同，但RSSI質(zhì)心定位算法的定位誤差顯著低于傳統(tǒng)質(zhì)心算法，證明所提出改進(jìn)后的算法確實(shí)可行.

圖16 傳統(tǒng)質(zhì)心法與改進(jìn)之后比較

4 結(jié)語(yǔ)

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位采用傳統(tǒng)質(zhì)心算法定位精度不高，為了提高節(jié)點(diǎn)定位精度，本文提出了一種基于RSSI的改進(jìn)加權(quán)質(zhì)心定位算法.改進(jìn)算法在測(cè)距階段利用高斯濾波對(duì)信號(hào)進(jìn)行平滑處理，將值加權(quán)平均處理，將所得的值轉(zhuǎn)變?yōu)榫嚯x，定位階段通過改正其權(quán)值增加了有效數(shù)據(jù)的利用率.通過仿真可知，改進(jìn)的算法節(jié)點(diǎn)定位誤差更低，定位精度更高.