李 彬, 施 泱

(山西大學,數(shù)學科學學院,山西 太原 030006)

?

室內(nèi)無線傳感器網(wǎng)絡中移動節(jié)點的改進質(zhì)心定位算法

李 彬, 施 泱

(山西大學,數(shù)學科學學院,山西 太原 030006)

目前室內(nèi)定位方法往往精度不高，價格也較為昂貴.文章介紹一種傳統(tǒng)的質(zhì)心定位算法，并且提出一種基于參考點計算質(zhì)心的改進室內(nèi)移動節(jié)點質(zhì)心定位算法.仿真結(jié)果表明，該方法能夠有效提高節(jié)點的定位精度.

移動節(jié)點；質(zhì)心算法；室內(nèi)無線傳感器網(wǎng)絡；節(jié)點定位

1 概述

無線傳感器網(wǎng)絡(WSN)中的節(jié)點定位是傳感器網(wǎng)絡最基本的功能之一,對傳感器網(wǎng)絡應用有著重要作用.定位算法從定位手段上分為:基于距離的(Range-Based)定位算法和距離無關(Range-Free)的定位算法[1].在無線傳感器網(wǎng)絡的實際應用中,很多情形都需要對某些移動節(jié)點進行快速準確定位,如軍事、交通、反恐等場景中節(jié)點位置伴隨著被監(jiān)控對象的移動而變化.由于未知節(jié)點的移動特性,其相應的定位算法通常也要求快速準確.如何能快速準確地定位未知節(jié)點,成為了無線傳感器網(wǎng)絡中移動節(jié)點的定位問題研究的熱點之一[2].文獻[3]提出了一種基于RSSI的加權質(zhì)心定位算法,定位精度有了一定的提升.但由于節(jié)點要將RSSI值轉(zhuǎn)化為距離信息,同時定位過程中要進行質(zhì)心的加權運算,當節(jié)點快速移動時該算法較難滿足定位的實時性要求.文獻[4]較好的解決了節(jié)點分布不均對傳統(tǒng)定位算法的影響,但算法中對RSSI的可信選取方案還有進一步討論的必要.

之前的定位算法主要依賴于可通信節(jié)點對未知節(jié)點的位置約束來定位節(jié)點.與其不同的是,本文針對室內(nèi)傳感器網(wǎng)絡,通過同時考慮與未知節(jié)點可通信的和不可通信的錨節(jié)點的位置信息,在定位區(qū)域內(nèi)引入比對點來計算質(zhì)心,保證定位的快速性的同時,提高了定位精度.

2 算法模型

2.1 一種傳統(tǒng)的定位算法

傳統(tǒng)的質(zhì)心算法(Centroid Algorithm)是一種基于連通性且無需距離信息的簡單定位算法.其核心思想是把在未知節(jié)點通信范圍之內(nèi)的信標節(jié)點所構(gòu)成的幾何圖形的質(zhì)心作為未知節(jié)點的估計位置[5].

如圖1,設O1,O2,O3為錨節(jié)點,且有相同的通信半徑,每一個錨節(jié)點的通信覆蓋范圍為一個以錨節(jié)點為圓心的圓.A,B,C分別為三個圓的交點.若未知節(jié)點能與它們相互通信,則未知節(jié)點應處于三個錨節(jié)點所覆蓋的公共區(qū)域內(nèi),質(zhì)心定位算法取A,B,C三點形成的三角形的質(zhì)心作為未知節(jié)點的位置估計.

2.2 改進的質(zhì)心定位算法

2.2.1 定位范圍的改進

在室內(nèi)無線傳感器網(wǎng)絡節(jié)點的定位過程中,錨節(jié)點可以一定范圍內(nèi)較為自由的部署,且相對部署密度較大,如何充分利用錨節(jié)點位置已知的條件是提高未知節(jié)點定位精度的關鍵.然而以往的定位算法只關心可通信的錨節(jié)點對未知節(jié)點定位起到的作用,忽略了不可通信的錨節(jié)點在未知節(jié)點定位中的作用.不可通信的錨節(jié)點同樣可以用來縮小定位范圍,提高定位精度.如圖2所示,在圖1的基礎上增加一個與O1,O2,O3有相同的通信半徑的錨節(jié)點O4.若未知節(jié)點不能與O4節(jié)點通信,那么未知節(jié)點的位置只能在C,D,E所形成的陰影區(qū)域內(nèi),記此區(qū)域為SCDE.再利用質(zhì)心定位算法取C,D,E三點形成的三角形的質(zhì)心作為未知節(jié)點的位置估計.

可以看出相對于一般質(zhì)心算法,此方法有效的縮小了未知節(jié)點的定位范圍.

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

圖2 改進質(zhì)心定位算法

2.2.2 質(zhì)心計算方法的改進

由于此算法對于未知節(jié)點定位范圍的質(zhì)心計算只選取了很少的邊界點,計算過程依然很粗糙.若能夠知道區(qū)域內(nèi)更多的點的坐標,在計算區(qū)域質(zhì)心時將更為準確.因此,我們在未知節(jié)點定位范圍內(nèi)選取出更多的比對點,利用這些比對點與錨節(jié)點的通信情況將之分類,有相同通信情況的比對點歸為一類.如圖2中,SCDE中的所有點只能與O1，O2，O3相互通信,與其他錨節(jié)點均不能通信.反之,能與O1，O2，O3相互通信的所有可能節(jié)點也都含在SCDE中.我們將此區(qū)域稱為定位劃分區(qū),定位劃分區(qū)內(nèi)的比對點有相同的通信信息.在SCDE中引入更多的比對點,將使得質(zhì)心的計算更為準確.

我們在監(jiān)測區(qū)域內(nèi)引入比對點,將比對點與錨節(jié)點的距離信息轉(zhuǎn)化為通信信息,建立通信矩陣C=(cij)k1×k2，m.若第i個比對點可以與第j個錨節(jié)點通信,則cij=1,否則cij=0.然后將移動節(jié)點的通信信息與比對點的通信信息進行比對.若通信信息相同,則比對點與移動節(jié)點在相同的定位劃分區(qū)內(nèi).然后利用比對點的質(zhì)心作為定位劃分區(qū)的質(zhì)心,估計出移動節(jié)點的位置.

2.3 算法步驟

錨節(jié)點通過泛洪方式周期性的廣播自己的位置信息,未知節(jié)點接收到此信息則認為二者可相互通信,同時也意味著二者的距離小于錨節(jié)點的通信半徑R.對于分布著m個錨節(jié)點的矩形監(jiān)測區(qū)域[0，a]×[0，b],我們采用以下步驟求出未知節(jié)點的存在區(qū)域.

Step1 建立坐標系,在[0，a]×[0，b]內(nèi)等距插入節(jié)點,間距為λ,則

其中x=n,xn=b,y=0,yn=b,λ稱為分割細度.將{xi},{yi}做笛卡爾集,這樣就可在X+Y平面內(nèi)插入k1+k2個比對點,我們將這些插入點稱為比對點.定位時要求比對點的數(shù)量足夠多.

Step2 將比對點與錨節(jié)點的距離信息轉(zhuǎn)化為通信信息,建立通信矩陣C=(cij)k1×k2,m.若第i個比對點可以與第j個錨節(jié)點通信,則cij=1,否則cij=0.

Step4 求出與移動節(jié)點同類的比對點的質(zhì)心作為移動節(jié)點(x，y)的位置估計.

3 實驗結(jié)果

3.1 定位誤差

實驗在MATLAB環(huán)境下進行.在40 m×40 m的感知區(qū)域內(nèi)均勻分布25個傳感器節(jié)點,設傳感器節(jié)點的通信半徑R=10 m，移動節(jié)點在40 s內(nèi)非均速通過感知區(qū)域.

從圖3中可以看出,改進質(zhì)心算法與傳統(tǒng)質(zhì)心算法相比有著較好的定位效果.而且由于改進質(zhì)心算法不需要測距信息,所以能夠保證定位的實時性要求.

從圖4中可以看出,整個定位過程中改進質(zhì)心算法對移動節(jié)點的定位誤差不超過2.5 m,平均定位誤差為0.943 9 m.相較于質(zhì)心定位算法,平均定位誤差提高約50%.

圖3 改進質(zhì)心算法定位誤差

圖4 定位誤差曲線

4 結(jié)論

本文提出一種在室內(nèi)存在部分信標節(jié)點情形下的移動節(jié)點改進質(zhì)心定位算法.該算法充分考慮了通信信息對移動節(jié)點定位的作用,而且不需要測距信息,設計簡單.另外,對比傳統(tǒng)質(zhì)心算法可知我們的方法定位誤差更小,此方法更適用于實際.

對于此算法,考慮到實際中錨節(jié)點的部署情況將直接影響定位精度,因此討論錨節(jié)點的部署形式將進一步提高測距精度.參考文獻：

[1] G.Blumrosen,B.Hod,T.Anker,D.Dolev,and B.Rubinsky,Enhanced calibration technique for rssi-based ranging in body area networks[J].Journal on Ad Hoc Networks,2013,11(1):555-569

[2] 梅 舉,陳 滌,辛 玲.基于蒙特卡羅的移動傳感器網(wǎng)節(jié)點定位優(yōu)化算法[J].傳感技術學報,2013,5(26):689-694

[3] 劉運杰,金明錄,崔承毅.基于RSSI的無線傳感器網(wǎng)絡修正加權質(zhì)心定位算法[J].傳感技術學報,2010,23(5):717-720

[4] 陳維克,李文鋒,首 珩,等.基于RSSI的無線傳感器網(wǎng)絡加權質(zhì)心定位算法[J].武漢理工大學學報,2006,30(2):256-268

[5] 楊新宇,孔慶茹,戴湘軍.一種改進的加權質(zhì)心定位算法[J].西安交通大學學報,2010,44(8):1-4

Localization for Indoor WSN

LI Bin，SHI Yang

(School of Mathematical Sciences，Shanxi University, Taiyuan 030006, China)

The positioning accuracy of the indoor positioning method is not high at present. In this paper, a traditional centroid localization algorithm is analyzed, and an improved algorithm based on the centroid of reference point is proposed. Simulation results show that the location precision can be improved effectively.

mobile node; centroid algorithm; indoor WSN; node localization

2016-05-09

李 彬(1980-),男,山東威海人,碩士,山西大學講師,主要從事無線傳感器網(wǎng)絡與控制工程研究.

1672-2027(2016)03-0057-03

TP393

A