基于質(zhì)點(diǎn)彈簧模型的無(wú)線傳感器網(wǎng)絡(luò)非測(cè)距定位算法*

楊友華,孫麗華,向滿天*

(1.南昌大學(xué)信息工程學(xué)院,南昌 330031;2.南昌大學(xué)軟件學(xué)院,南昌 330029)

?

基于質(zhì)點(diǎn)彈簧模型的無(wú)線傳感器網(wǎng)絡(luò)非測(cè)距定位算法*

楊友華1,孫麗華2,向滿天2*

(1.南昌大學(xué)信息工程學(xué)院,南昌 330031;2.南昌大學(xué)軟件學(xué)院,南昌 330029)

在無(wú)線傳感器網(wǎng)絡(luò)定位中,非測(cè)距定位因功耗低、成本低而備受關(guān)注,但其較低的定位精度限制了其應(yīng)用范圍。提出了一種精度較高的基于質(zhì)點(diǎn)彈簧模型的非測(cè)距定位算法L-MSM(Localization based on Mass Spring Model)。該算法首先使用復(fù)雜度低、通信開(kāi)銷小的質(zhì)心算法進(jìn)行粗定位,然后利用改進(jìn)的質(zhì)點(diǎn)彈簧模型進(jìn)行優(yōu)化,使質(zhì)心算法定位后成簇聚集的節(jié)點(diǎn)分散開(kāi)來(lái)并趨近實(shí)際位置,從而實(shí)現(xiàn)精確定位。仿真結(jié)果表明,在通信半徑較小時(shí),L-MSM算法的定位精度相對(duì)于質(zhì)心算法有顯著的提高。

無(wú)線傳感器網(wǎng)絡(luò);非測(cè)距定位;質(zhì)點(diǎn)彈簧模型;質(zhì)心算法

無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由許多細(xì)小、低成本、資源有限、能夠感受外界特性的無(wú)線傳感器組成[1]。得益于集成電路和無(wú)線通信技術(shù)的發(fā)展,WSN的應(yīng)用越來(lái)越廣泛,它可用于環(huán)境監(jiān)測(cè),災(zāi)害預(yù)警,目標(biāo)追蹤,軍事偵察等方面。在這些用途中,傳感器節(jié)點(diǎn)的位置信息是非常有用或必不可少的[2]。受條件限制,不能給每個(gè)節(jié)點(diǎn)安裝GPS或人工部署,所以利用某些位置已知的節(jié)點(diǎn)去定位位置未知的節(jié)點(diǎn)是WSN定位中研究的重點(diǎn)。

根據(jù)定位中是否用到距離測(cè)量技術(shù),WSN定位分為測(cè)距定位和非測(cè)距定位。測(cè)距定位需要測(cè)量節(jié)點(diǎn)間的距離或角度信息,定位精度較高,但測(cè)距設(shè)備較貴,能耗較大;非測(cè)距定位只利用節(jié)點(diǎn)間的連通信息,不需要特殊的測(cè)距設(shè)備,但定位精度較低[3]。

質(zhì)心算法是由美國(guó)南加州大學(xué)的Bulusu等提出的一種經(jīng)典非測(cè)距定位算法[4]。在該算法中,未知錨節(jié)點(diǎn)每隔一段時(shí)間向鄰居節(jié)點(diǎn)廣播一個(gè)信標(biāo)信號(hào)(Beacon Signal),信號(hào)中包含自身ID和位置信息。當(dāng)未知節(jié)點(diǎn)接收到來(lái)自不同錨節(jié)點(diǎn)的信標(biāo)數(shù)量超過(guò)某一個(gè)預(yù)設(shè)門限或接收一定時(shí)間后,該節(jié)點(diǎn)就確定自身位置為這些錨節(jié)點(diǎn)所組成的多邊行的質(zhì)心[5]。質(zhì)心算法的計(jì)算復(fù)雜度和通信開(kāi)銷都很小,但是定位精度較低。

質(zhì)點(diǎn)彈簧模型將傳感器節(jié)點(diǎn)視為有一定質(zhì)量的質(zhì)點(diǎn),節(jié)點(diǎn)間用虛擬的彈簧相連,節(jié)點(diǎn)在彈簧力的作用下移動(dòng)到估計(jì)位置[6]。它可以利用節(jié)點(diǎn)間的協(xié)作來(lái)減小定位誤差,常被用作一種優(yōu)化方法對(duì)粗定位后的結(jié)果進(jìn)行優(yōu)化[7]。在測(cè)距定位中,文獻(xiàn)[8-11]先利用一種定位算法進(jìn)行粗定位,然后以測(cè)量距離作為彈簧的平衡長(zhǎng)度,使用質(zhì)點(diǎn)彈簧模型對(duì)粗定位后的結(jié)果進(jìn)行優(yōu)化。在非測(cè)距定位中,文獻(xiàn)[12]先利用基于支持向量機(jī)的定位算法進(jìn)行粗定位,然后以通信半徑作為彈簧的平衡長(zhǎng)度,使用質(zhì)點(diǎn)彈簧模型對(duì)粗定位后的結(jié)果進(jìn)行優(yōu)化。文獻(xiàn)[13]先利用類似Bounding Box[14]的定位算法進(jìn)行粗定位,然后以DV-hop算法得到的節(jié)點(diǎn)到錨節(jié)點(diǎn)距離作為彈簧的平衡長(zhǎng)度,使用質(zhì)點(diǎn)彈簧模型對(duì)粗定位后的結(jié)果進(jìn)行優(yōu)化。

針對(duì)質(zhì)心算法定位精度較低的問(wèn)題,本文設(shè)計(jì)了一種基于質(zhì)點(diǎn)彈簧模型的非測(cè)距定位算法L-MSM(Localization based on Mass Spring Model),算法首先使用質(zhì)心算法進(jìn)行粗定位,然后利用改進(jìn)的質(zhì)點(diǎn)彈簧模型對(duì)粗定位后成簇聚集的節(jié)點(diǎn)進(jìn)行優(yōu)化而實(shí)現(xiàn)精確定位。仿真結(jié)果表明,在通信半徑較小時(shí),L-MSM算法的定位精度較質(zhì)心算法有顯著的提高。

1 質(zhì)點(diǎn)彈簧模型

WSN中位置已知的節(jié)點(diǎn)稱為錨節(jié)點(diǎn)或信標(biāo)節(jié)點(diǎn),它們的位置來(lái)自GPS定位或人工部署;其他待定位的節(jié)點(diǎn)稱為未知節(jié)點(diǎn);兩節(jié)點(diǎn)之間若能相互通信,則互為鄰居節(jié)點(diǎn)。

圖1 質(zhì)點(diǎn)彈簧模型

圖1(a)中的WSN包含7個(gè)節(jié)點(diǎn),其中5個(gè)錨節(jié)點(diǎn)用實(shí)心圓圈表示,2個(gè)未知節(jié)點(diǎn)用空心圓圈表示,鄰居節(jié)點(diǎn)之間用直線相連。質(zhì)點(diǎn)彈簧模型將所有節(jié)點(diǎn)視為有一定質(zhì)量的質(zhì)點(diǎn),鄰居節(jié)點(diǎn)間用虛擬的彈簧相連,彈簧的平衡長(zhǎng)度等于節(jié)點(diǎn)間的實(shí)際距離,圖1(a)中WSN的質(zhì)點(diǎn)彈簧模型如圖1(b)所示,此時(shí)的質(zhì)點(diǎn)彈簧模型處于平衡狀態(tài)。但起初,只有錨節(jié)點(diǎn)的位置是已知的,將其視為固定的質(zhì)點(diǎn),未知節(jié)點(diǎn)的位置在使用質(zhì)點(diǎn)彈簧模型優(yōu)化前,只能粗略估計(jì),取如圖1(c)所示的位置,此時(shí)未知節(jié)點(diǎn)偏離實(shí)際位置,彈簧長(zhǎng)度不等于平衡長(zhǎng)度,彈簧處于壓縮或拉伸狀態(tài),將對(duì)未知節(jié)點(diǎn)施加力的作用,未知節(jié)點(diǎn)在合力的作用下進(jìn)行移動(dòng),直到合力為零,彈簧達(dá)到平衡長(zhǎng)度,節(jié)點(diǎn)移動(dòng)到實(shí)際位置,回到圖1(b)的狀態(tài),達(dá)到準(zhǔn)確定位的目的。

有一種特殊情況,當(dāng)未知節(jié)點(diǎn)的初始估計(jì)位置和鄰居節(jié)點(diǎn)在一條直線上,但其實(shí)際位置不在那條直線上,如圖2所示,未知節(jié)點(diǎn)只能在直線上移動(dòng),最后合力為零時(shí),未知節(jié)點(diǎn)也不能回到實(shí)際位置。因此,這種情況下并不能用合力是否為零來(lái)判斷節(jié)點(diǎn)是否回到實(shí)際位置。其實(shí),合力為零時(shí),彈簧勢(shì)能并非也為零,所以可以用彈簧勢(shì)能是否為零來(lái)判斷節(jié)點(diǎn)是否回到實(shí)際位置。

圖2 節(jié)點(diǎn)初始位置和鄰居節(jié)點(diǎn)在同一條直線上的情況

2 L-MSM算法原理

上節(jié)的質(zhì)點(diǎn)彈簧模型中,彈簧的平衡長(zhǎng)度設(shè)為節(jié)點(diǎn)間的實(shí)際距離,但實(shí)際距離一般是未知的。在測(cè)距定位中,節(jié)點(diǎn)可以通過(guò)各種測(cè)距方式得到帶有誤差的測(cè)量距離,以其作為彈簧平衡長(zhǎng)度,但非測(cè)距定位中不測(cè)量距離,只能尋求其他參數(shù)代替。數(shù)學(xué)上有這種概率問(wèn)題,如果一個(gè)未知點(diǎn)可能等概率地處于兩個(gè)端點(diǎn)之間直線段上的任何位置,當(dāng)取其為中點(diǎn)位置時(shí),位置偏差的期望值將最小,這是一維的情況,同樣可以推廣到多維。同理,可以先通過(guò)節(jié)點(diǎn)的估計(jì)位置計(jì)算節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的估計(jì)距離,再以節(jié)點(diǎn)到所有鄰居節(jié)點(diǎn)估計(jì)距離的平均值作為彈簧的平衡長(zhǎng)度,從而通過(guò)質(zhì)點(diǎn)彈簧模型盡量使節(jié)點(diǎn)到所有鄰居節(jié)點(diǎn)的距離相等,減小定位誤差的期望值。而且這樣特別適合使質(zhì)心算法定位后成簇聚集的節(jié)點(diǎn)分散開(kāi)來(lái)并趨近實(shí)際位置。

本文提出的L-MSM算法的過(guò)程為:先利用質(zhì)心算法進(jìn)行粗定位,得到節(jié)點(diǎn)的初始估計(jì)位置,再在此基礎(chǔ)上使用改進(jìn)的質(zhì)點(diǎn)彈簧模型進(jìn)行迭代求精,直到迭代次數(shù)達(dá)到設(shè)定的值為止。

2.1 質(zhì)心算法粗定位

質(zhì)心算法中未知節(jié)點(diǎn)的估計(jì)位置為所有鄰居錨節(jié)點(diǎn)坐標(biāo)的平均值,算法的計(jì)算量和通信開(kāi)銷都很小,很適合進(jìn)行粗定位。

設(shè)未知節(jié)點(diǎn)Si的坐標(biāo)為(xi,yi),它的鄰居錨節(jié)點(diǎn)Sk(k=1,2,…,Nk)的坐標(biāo)為(xik,yik),通過(guò)質(zhì)心算法可得:

(1)

由于質(zhì)心算法中,未知節(jié)點(diǎn)如果沒(méi)有鄰居錨節(jié)點(diǎn)就不能定位,因此對(duì)錨節(jié)點(diǎn)數(shù)量或通信半徑的要求較高。為了降低這些要求,粗定位時(shí)使用改進(jìn)的質(zhì)心算法:有鄰居錨節(jié)點(diǎn)的未知節(jié)點(diǎn)只利用鄰居錨節(jié)點(diǎn)進(jìn)行定位,沒(méi)有鄰居錨節(jié)點(diǎn)的未知節(jié)點(diǎn)利用已經(jīng)定位的鄰居未知節(jié)點(diǎn)進(jìn)行定位。

由質(zhì)心算法的定位原理可知,若兩個(gè)未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)相同,則它們得到的估計(jì)位置也相同;若兩個(gè)未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)大部分相同,則它們得到的估計(jì)位置會(huì)很相近。所以質(zhì)心算法定位后,很多節(jié)點(diǎn)成簇聚集,定位精度較低,而這正好可以利用改進(jìn)的質(zhì)點(diǎn)彈簧模型進(jìn)行優(yōu)化。

2.2 改進(jìn)的質(zhì)點(diǎn)彈簧模型求精

通過(guò)質(zhì)心算法粗定位后,未知節(jié)點(diǎn)得到了鄰居錨節(jié)點(diǎn)的實(shí)際位置和自己的估計(jì)位置。接下來(lái),未知節(jié)點(diǎn)將自己的估計(jì)位置廣播給它的鄰居未知節(jié)點(diǎn),這樣每個(gè)未知節(jié)點(diǎn)便得到了鄰居錨節(jié)點(diǎn)的實(shí)際位置和鄰居未知節(jié)點(diǎn)的估計(jì)位置,然后便可以計(jì)算得到未知節(jié)點(diǎn)到所有鄰居節(jié)點(diǎn)(包括鄰居錨節(jié)點(diǎn)和鄰居未知節(jié)點(diǎn))的估計(jì)距離。設(shè)未知節(jié)點(diǎn)Si的鄰居節(jié)點(diǎn)為Sj(j=1,2,…,Nj),計(jì)算出Si(xi,yi)和Sj(xj,yj)間的估計(jì)距離:

(2)

則Si到所有鄰居節(jié)點(diǎn)估計(jì)距離的平均值為:

(3)

(4)

式中:eij為由Si指向Sj的單位向量,ηj取決于鄰居節(jié)點(diǎn)是錨節(jié)點(diǎn)還是未知節(jié)點(diǎn)。因?yàn)殄^節(jié)點(diǎn)不移動(dòng),所以彈簧施加的力全部用來(lái)移動(dòng)未知節(jié)點(diǎn);而未知節(jié)點(diǎn)自己也會(huì)移動(dòng),彈簧施加的力用來(lái)同時(shí)移動(dòng)兩個(gè)未知節(jié)點(diǎn)。因此,當(dāng)Sj為錨節(jié)點(diǎn)時(shí),ηj=1;當(dāng)Sj為未知節(jié)點(diǎn)時(shí),ηj=0.5。

連接Si的所有彈簧對(duì)Si施加的合力為:

(5)

連接Si的所有彈簧總勢(shì)能為:

(6)

節(jié)點(diǎn)Si在合力作用下按式(7)進(jìn)行移動(dòng),移動(dòng)后的位置若超出WSN的邊界,則保持原估計(jì)位置不變,否則,對(duì)移動(dòng)后的勢(shì)能Ei進(jìn)行判斷。若勢(shì)能減小,則用移動(dòng)后的位置作為節(jié)點(diǎn)新的估計(jì)位置,否則,保持原估計(jì)位置不變。

Xi(t)=Xi(t-1)+δFi

(7)

式中:Xi(t)為節(jié)點(diǎn)Si第t次移動(dòng)后的位置。δ為合力轉(zhuǎn)換為位移的系數(shù),δ取得越大,則移動(dòng)幅度越大,越容易使節(jié)點(diǎn)在實(shí)際位置周圍來(lái)回移動(dòng),產(chǎn)生振蕩;δ取得越小,則達(dá)到平衡狀態(tài)需要迭代的次數(shù)越多。

為加快收斂速度,取δ=λi(t)/mi,mi為Si的鄰居節(jié)點(diǎn)個(gè)數(shù),鄰居節(jié)點(diǎn)越多時(shí),合力可能越大,為保持足夠小的移動(dòng)幅度,讓?duì)呐cmi成反比。λi(t)為自適應(yīng)變量,如果這次位置移動(dòng)后勢(shì)能減小了,下次可以加大移動(dòng)幅度,令λi(t+1)=λi(t)·γ(γ為大于1的常數(shù)),否則,這次移動(dòng)幅度過(guò)大,下次要減小移動(dòng)幅度,令λi(t+1)=λi(t)/γ。

待所有未知節(jié)點(diǎn)完成一次質(zhì)點(diǎn)彈簧模型迭代求精后,更新了估計(jì)位置的未知節(jié)點(diǎn)將新的估計(jì)位置廣播給它的鄰居未知節(jié)點(diǎn),然后各個(gè)未知節(jié)點(diǎn)進(jìn)行下一次迭代求精,直到迭代次數(shù)達(dá)到設(shè)定的次數(shù),結(jié)束求精過(guò)程。L-MSM算法的整個(gè)流程如圖3所示。

圖3 L-MSM算法的流程圖

3 仿真結(jié)果及分析

為了評(píng)價(jià)L-MSM算法的性能,在MATLAB中對(duì)L-MSM算法和質(zhì)心算法進(jìn)行對(duì)比,定位誤差用通信半徑歸一化后的節(jié)點(diǎn)平均定位誤差表示:

(8)

仿真環(huán)境參數(shù)為:100 m×100 m的正方形區(qū)域中,隨機(jī)分布300個(gè)節(jié)點(diǎn),其中錨節(jié)點(diǎn)比例為20%,節(jié)點(diǎn)通信半徑r=15 m。L-MSM算法的求精參數(shù)為:迭代次數(shù)等于10,加快收斂速度的λ初始值為3,γ=1.1。以下所有仿真,未特別說(shuō)明時(shí),參數(shù)默認(rèn)取以上的值。

每次仿真,L-MSM算法和質(zhì)心算法在同一節(jié)點(diǎn)布局下分別進(jìn)行定位。為減小節(jié)點(diǎn)隨機(jī)分布的影響,每種參數(shù)下默認(rèn)進(jìn)行100次節(jié)點(diǎn)隨機(jī)布局的仿真,再求定位誤差的平均值。

3.1 默認(rèn)參數(shù)下的定位誤差

在默認(rèn)參數(shù)下進(jìn)行一次仿真,得到如圖4的定位誤差圖,圖中未知節(jié)點(diǎn)的估計(jì)位置和實(shí)際位置間用直線相連,直線的長(zhǎng)短直觀地表示了定位誤差的大小。圖4(a)是質(zhì)心算法的定位誤差圖,圖4(b)是L-MSM算法的定位誤差圖。

比較圖4(a)和4(b),可以發(fā)現(xiàn)L-MSM算法的大部分節(jié)點(diǎn)的定位誤差比質(zhì)心算法小很多。圖4(a)中很多節(jié)點(diǎn)成簇聚集,圖4(b)中節(jié)點(diǎn)分布較均勻。因?yàn)長(zhǎng)-MSM算法加入了邊界判斷過(guò)程,圖4(b)中沒(méi)有節(jié)點(diǎn)超出WSN邊界。圖4(a)中節(jié)點(diǎn)的平均定位誤差為0.364,圖4(b)中為0.177,L-MSM算法的定位誤差較質(zhì)心算法減小了51%。

圖4 定位誤差圖

圖5 L-MSM算法在不同迭代次數(shù)下的定位誤差

3.2 不同迭代次數(shù)下的定位誤差

在其他參數(shù)不變的情況下,改變L-MSM算法求精的迭代次數(shù),定位誤差的變化如圖5所示。L-MSM算法的迭代次數(shù)為0時(shí),即質(zhì)心算法粗定位的誤差為0.397;迭代次數(shù)為1時(shí),定位誤差為0.285;迭代次數(shù)為3時(shí),定位誤差為0.246。迭代次數(shù)繼續(xù)增加,定位誤差始終在0.24附近,所以迭代次數(shù)為3時(shí),L-MSM算法已經(jīng)收斂了,收斂速度非常快。不過(guò)不同參數(shù)下收斂所需的迭代次數(shù)不一樣,為保證不同參數(shù)下都能收斂,將默認(rèn)迭代次數(shù)設(shè)為10。

3.3 不同錨節(jié)點(diǎn)比例下的定位誤差

在其他參數(shù)不變的情況下,錨節(jié)點(diǎn)比例從5%增大到35%,L-MSM算法和質(zhì)心算法的定位誤差如圖6所示?？梢钥吹?隨著錨節(jié)點(diǎn)比例的增大,L-MSM算法和質(zhì)心算法的定位誤差都在減小,且L-MSM算法的定位誤差始終比質(zhì)心算法小。錨節(jié)點(diǎn)比例為5%時(shí),L-MSM算法的定位誤差較質(zhì)心算法減小了26%;為20%時(shí),減小了39%;為40%時(shí),減小了29%。定位精度的提高始終明顯。不過(guò)同時(shí)可以看到,錨節(jié)點(diǎn)比例較低和較高時(shí),定位精度的提高幅度有所減小,說(shuō)明L-MSM算法更適合在錨節(jié)點(diǎn)比例適中的情況下進(jìn)行定位。

圖6 不同錨節(jié)點(diǎn)比例下的定位誤差

圖7 不同總節(jié)點(diǎn)數(shù)下的定位誤差

3.4 不同總節(jié)點(diǎn)數(shù)下的定位誤差

在其他參數(shù)不變的情況下,總節(jié)點(diǎn)數(shù)從100增大到500,L-MSM算法和質(zhì)心算法的定位誤差如圖7所示?？梢钥吹?隨著總節(jié)點(diǎn)數(shù)的增大,L-MSM算法和質(zhì)心算法的定位誤差都在減小,且L-MSM算法的定位誤差始終比質(zhì)心算法小?？偣?jié)點(diǎn)數(shù)為100時(shí),L-MSM算法的定位誤差較質(zhì)心算法減小了16%;為300時(shí),減小了39%;為500時(shí),減小了35%。定位精度的提高始終明顯。同樣也可以看到,總節(jié)點(diǎn)數(shù)較低和較高時(shí),定位精度的提高幅度有所減小,說(shuō)明L-MSM算法更適合在總節(jié)點(diǎn)數(shù)適中的情況下進(jìn)行定位。

3.5 不同通信半徑下的定位誤差

在其他參數(shù)不變的情況下,通信半徑r從9m增大到39m,L-MSM算法和質(zhì)心算法的定位誤差如圖8所示?？梢钥吹?隨著r的增大,L-MSM算法和質(zhì)心算法的定位誤差都先減小后增大,之所以會(huì)出現(xiàn)增大的轉(zhuǎn)折,是因?yàn)閞過(guò)大時(shí),很多節(jié)點(diǎn)的通信半徑圈超出了邊界,而邊界外沒(méi)有節(jié)點(diǎn),使得節(jié)點(diǎn)的鄰居節(jié)點(diǎn)分布嚴(yán)重不對(duì)稱,以致利用所有鄰居節(jié)點(diǎn)進(jìn)行求精的L-MSM算法和利用鄰居錨節(jié)點(diǎn)進(jìn)行定位的質(zhì)心算法的定位誤差都增大,而且利用更多鄰居節(jié)點(diǎn)的L-MSM算法的定位誤差增大得更快。在r較小時(shí),L-MSM算法的定位誤差比質(zhì)心算法小;在r為27m時(shí),L-MSM算法的定位誤差約等于質(zhì)心算法;r再增大,L-MSM算法的定位誤差反而比質(zhì)心算法大,說(shuō)明L-MSM算法適合在r較小的情況下進(jìn)行定位。

圖8 不同通信半徑下的定位誤差

4 結(jié)論

針對(duì)質(zhì)心算法定位精度較低的問(wèn)題,本文利用改進(jìn)的質(zhì)點(diǎn)彈簧模型對(duì)其進(jìn)行優(yōu)化。優(yōu)化過(guò)程中以節(jié)點(diǎn)到所有鄰居節(jié)點(diǎn)估計(jì)距離的平均值作為彈簧的平衡長(zhǎng)度。對(duì)節(jié)點(diǎn)所受彈簧合力轉(zhuǎn)換為位移的系數(shù)進(jìn)行了設(shè)計(jì),加快了迭代過(guò)程的收斂速度。加入了邊界判斷過(guò)程,防止了估計(jì)位置超出邊界。仿真結(jié)果表明,在通信半徑較小時(shí),L-MSM算法的定位精度較質(zhì)心算法有顯著的提高。不過(guò)通信半徑超過(guò)一定值后,L-MSM算法的定位精度開(kāi)始降低,對(duì)于如何提高L-MSM算法在通信半徑較大情況下的定位精度,是未來(lái)需要進(jìn)一步研究的。

[1] 劉健苗,許新忠,黃書廣,等. 改進(jìn)的分布式無(wú)線傳感器網(wǎng)絡(luò)多維標(biāo)度定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(5):692-697.

[2] Han G,Xu H,Duong T Q,et al. Localization Algorithms of Wireless Sensor Networks:A Survey[J]. Telecommunication Systems,2013,52(4):2419-2436.

[3] 向滿天,羅嗣力,戴美思. 無(wú)線傳感器網(wǎng)絡(luò)中一種改進(jìn)的凸規(guī)劃定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(8):24.

[4] Bulusu N,Heidemann J,Estrin D. GPS-Less Low-Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications,2000,7(5):28-34.

[5] 劉鋒,章登義. 基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J]. 計(jì)算機(jī)科學(xué),2012,39(B6):96-98.

[6] Priyantha N B,Balakrishnan H,Demaine E,et al. Anchor-Free Distributed Localization in Sensor Networks[C]//Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. USA:ACM Press,2003:340-341.

[7] Zhang Q,Foh C H,Seet B C,et al. Location Estimation in Wireless Sensor Networks Using Spring-Relaxation Technique[J]. Sensors,2010,10(5):5171-5192.

[8] Yu J,Kulkarni S R,Poor H V. Dimension Expansion and Customized Spring Potentials for Sensor Localization[J]. EURASIP Journal on Advances in Signal Processing,2013,2013(1):1-14.

[9] Seet B C,Zhang Q,Foh C H,et al. Hybrid RF Mapping and Kalman Filtered Spring Relaxation for Sensor Network Localization[J]. IEEE Sensors Journal,2012,12(5):1427-1435.

[10] Zhang Q,Foh C H,Seet B C,et al. Variable Elasticity Spring-Relaxation:Improving the Accuracy of Localization for WSNs with Unknown Path Loss Exponent[J]. Personal and Ubiquitous Computing,2011,16(7):929-941.

[11] Engel F,Hedley M. A Comparison of Cooperative Localisation Techniques for Wireless Mobile Sensor Networks[C]//2007 International Symposium on Communications and Information Technologies Proceedings. USA:IEEE Press,2007:887-892.

[12] Tran D A,Nguyen T. Localization in Wireless Sensor Networks Based on Support Vector Machines[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(7):981-994.

[13] 田金鵬,施惠昌. 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)算法[J]. 上海大學(xué)學(xué)報(bào):自然科學(xué)版,2009,15(3):225-229.

[14] Simic S N,Sastry S. Distributed Localization in Wireless Ad Hoc Networks[R]. Technical Report UCB/ERL,2002.

楊友華(1990-),男,江西撫州人,碩士研究生,主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、無(wú)線通信等,yyouhua627@163.com;

孫麗華(1955-),女,江西南昌人,南昌大學(xué)教授、碩士生導(dǎo)師,主要研究領(lǐng)域?yàn)樾盘?hào)檢測(cè)與處理,slh52@163.com;

向滿天(1977-),男,湖北恩施人,博士。南昌大學(xué)副教授、碩士生導(dǎo)師、江西省條代碼標(biāo)準(zhǔn)化技術(shù)委員會(huì)委員、南昌市標(biāo)準(zhǔn)化專家。先后主持多項(xiàng)重大課題,擁有授權(quán)發(fā)明專利3項(xiàng),發(fā)表核心、SCI/EI論文30余篇。主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)、短距離無(wú)線通信、嵌入式網(wǎng)絡(luò),sosmt@163.com。

Range-Free Localization Algorithm Based on Mass SpringModel for Wireless Sensor Networks*

YANGYouhua1,SUNLihua2,XIANGMantian2*

(1.School of Information Engineering,Nanchang University,Nanchang 330031,China;2.School of Software,Nanchang University,Nanchang 330029,China)

The range-free localization algorithm has attracted much attention in wireless sensor networks due to its low power consumption and low cost,but its low positioning accuracy has limited its application. This paper proposes a high-accuracy range-free localization algorithm L-MSM(Localization based on Mass Spring Model). The algorithm first uses the centroid algorithm which has low complexity and little communication overhead for coarse positioning,then adopts modified mass spring model for iterative refinement,which makes the nodes in clusters because of the drawback of centroid algorithm spread out and approach the actual position. The simulation results indicate that the L-MSM algorithm can significantly improve the positioning accuracy compared to the centroid algorithm when the communication radius is small.

wireless sensor network;range-free localization;mass spring model;centroid algorithm

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(61362022,61362008);江西省科技計(jì)劃項(xiàng)目(20142BBE50019)

2014-12-09 修改日期:2015-03-07

C:6150P;7230

10.3969/j.issn.1004-1699.2015.06.023

TP393

A

1004-1699(2015)06-0914-06