陳三風(fēng),韓 鑫,湛邵斌,胡 濤,盧 鑫,陳萬明

(1.深圳信息職業(yè)技術(shù)學(xué)院信息技術(shù)研究所,廣東 深圳 518029;2.江西理工大學(xué)機電工程學(xué)院,江西 贛州 341000；3.中國科學(xué)技術(shù)大學(xué)自動化系,合肥 230027)

基于彈簧粒子模型的大規(guī)模WSN定位算法的衍生算法*

陳三風(fēng)1,2*,韓 鑫1,2,湛邵斌1,2,胡 濤1,2,盧 鑫1,2,陳萬明3

(1.深圳信息職業(yè)技術(shù)學(xué)院信息技術(shù)研究所,廣東 深圳 518029;2.江西理工大學(xué)機電工程學(xué)院,江西 贛州 341000；3.中國科學(xué)技術(shù)大學(xué)自動化系,合肥 230027)

為了提高基于彈簧粒子模型的大規(guī)模無線傳感器網(wǎng)絡(luò)定位算法(LASPM定位算法)的魯棒性,將對LASPM基本定位算法進行優(yōu)化及改進,并提出一系列的改進衍生算法。針對弱節(jié)點將設(shè)計簡單的迭代定位方法,提出了3個補丁算法,分別用于處理局部極值、剔除壞節(jié)點和處理節(jié)點動態(tài)變化等問題。仿真實驗結(jié)果表明,新算法的節(jié)點計算復(fù)雜度、通信復(fù)雜度在網(wǎng)絡(luò)規(guī)模增大時仍然保持常量,節(jié)點計算步數(shù)不隨網(wǎng)絡(luò)規(guī)模變化而變化,時間復(fù)雜度也保持常量。實驗研究結(jié)果表明,本文的定位算法具有良好的魯棒性。

定位算法;彈簧粒子模型;大規(guī)模無線傳感器網(wǎng)絡(luò);衍生算法;復(fù)雜度

為了擴大月球車的巡視和探測區(qū)域,需要建立一個包含數(shù)以萬計無線傳感器節(jié)點的大規(guī)模無線傳感器網(wǎng)絡(luò)。大規(guī)模無線傳感器網(wǎng)絡(luò)由大量的傳感器節(jié)點構(gòu)成,每個傳感器節(jié)點的資源都受限,必須和其他傳感器節(jié)點協(xié)同完成工作。目前,大部分無線傳感器網(wǎng)絡(luò)定位算法[1-4]的計算復(fù)雜度、通信復(fù)雜度和時間復(fù)雜度會隨著網(wǎng)絡(luò)規(guī)模的擴大而大大增加,這將導(dǎo)致大規(guī)模傳感器網(wǎng)絡(luò)系統(tǒng)癱瘓。針對以上問題,有關(guān)學(xué)者提出了基于質(zhì)量-彈簧模型的定位算法[5-6],其要求網(wǎng)絡(luò)中每個節(jié)點都具有測距能力,算法比較靈活,但是其計算復(fù)雜度比較高、收斂速度較慢、定位精度也不高。對此,本論文的研究者們提出了一種基于彈簧粒子網(wǎng)絡(luò)模型的定位算法[7]LASPM(Localization Algorithm Based on a Spring Particle model)。LASPM定位算法模擬物理彈簧系統(tǒng)的動態(tài)變化過程,并借此計算出節(jié)點的位置坐標。該定位算法的計算復(fù)雜度比較,不會隨著網(wǎng)絡(luò)規(guī)模的擴大而增加,非常適用于大規(guī)模無線傳感器網(wǎng)絡(luò)。

近年來,相關(guān)研究者針對大規(guī)模無線傳感器網(wǎng)絡(luò)定位問題提出了一系列的分布式定位算法[8-11]。其中,APIT算法[8]要求錨節(jié)點密度較高,Euclidean算法[9],但其測量距離較為復(fù)雜。DV-Hop算法[10]適用于密集部署各向同性的大規(guī)模無線傳感器網(wǎng)絡(luò)。Robust positioning[11]算法的定位精度較高,但是計算復(fù)雜度非常高。MDS-MAP[12]算法需要集中式計算,以上定位算法均不適用于本論文的傳感器網(wǎng)絡(luò)。

鑒于月球車的傳感器網(wǎng)絡(luò)系統(tǒng)非常復(fù)雜,為了提高LASPM定位算法的魯棒性,以適應(yīng)月球的復(fù)雜環(huán)境,本論文將對LASPM定位算法進行改進優(yōu)化并提出一系列的衍生算法。針對那些運算和存儲功能較低的傳感器網(wǎng)絡(luò)節(jié)點,本論文將設(shè)計簡單迭代定位方法。針對LASPM定位過程出現(xiàn)的BUG,本論文提出3個補丁算法,分別用于處理局部極值、剔除壞節(jié)點和處理節(jié)點動態(tài)變化等問題。

1 基于LASPM的簡單迭代定位算法

根據(jù)文獻[7]可知,LASPM定位算法模擬彈簧-粒子系統(tǒng)的運行狀態(tài)過程,并計算出各個傳感器節(jié)點的位置坐標。各傳感器節(jié)點虛擬為具有質(zhì)量的粒子,粒子間由彈簧相連。當(dāng)外力將粒子放置到隨機位置后,粒子間的彈簧將做相應(yīng)的拉伸收縮運動。在彈簧力的作用下,粒子最終運動到它的初始平衡位置。整個過程中,模擬粒子運動的每個狀態(tài)及相應(yīng)的彈力,最終得到各節(jié)點的位置坐標。

各傳感器節(jié)點定位每次迭代需接收眾多相鄰節(jié)點的虛擬坐標,計算該節(jié)點所受的合力、加速度、速度、位移等。然而,傳感器網(wǎng)絡(luò)中可能存在一些運算和存儲功能較低的節(jié)點,對此,本論文將設(shè)計簡單的迭代定位方法,使這些節(jié)點在每次迭代時無需計算節(jié)點受力合力、速度等,每次迭代時僅和一個鄰節(jié)點交換虛擬坐標信息,然后根據(jù)節(jié)點間彈簧原長和現(xiàn)在彈簧長度的差異,這兩個節(jié)點分別向它們連成的直線上相近或遠離該彈簧伸長/收縮量的長度,使得這次迭代后,這兩個節(jié)點間的距離等于它們原始距離。算法具體步驟如下:

首先 各節(jié)點通過各種測距方法[13](如RSSI等)獲得鄰節(jié)點間的初始一跳距離Ri,j;

然后 各節(jié)點向某個匯聚節(jié)點(Sink Node)發(fā)送以下信息:

Ii(IDi,is Anchor,{(IDj,Dij),(IDk,Dik),…})

該信息包含節(jié)點ID,是否為錨節(jié)點,到各個鄰節(jié)點的一跳距離及相應(yīng)鄰節(jié)點ID;

最后 匯聚節(jié)點通過以下迭代算法求解計算該節(jié)點的位置坐標:

①未知位置節(jié)點位置初始化

首先求出所有錨節(jié)點的質(zhì)心,然后確定最遠錨節(jié)點到質(zhì)心的長度,最后以該質(zhì)心為圓心,該長度為半徑作圓,使未知位置節(jié)點的坐標初始化于該圓之中。

②迭代收斂目標

(1)

并使式(2)中的Err最小:

(2)

式(2)Err為所有相鄰節(jié)點間平均一跳距離的絕對誤差平方與相對誤差平方的折衷,i,j為相鄰節(jié)點。

③迭代過程

(3)

當(dāng)l0次迭代結(jié)束后,其迭代增量為:

(4)

(b)當(dāng)i,j中某個節(jié)點為錨節(jié)點時,假設(shè)

為i,其迭代過程如下:

(5)

當(dāng)l0次迭代結(jié)束后,其迭代增量為:

(6)

這將導(dǎo)致迭代步驟增加,但是降低了估計距離和測量距離仍然相差很大時的影響。經(jīng)過一定的迭代次數(shù)后,多數(shù)節(jié)點間的估計距離和測量距離趨于一致,而仍然相差很大的那些節(jié)點可能因為測量距離與實際距離間誤差很大,導(dǎo)致估計距離與測量距離無法一致。

2 基本LASPM定位算法的補丁算法(LASPM(P))

為了使LASPM能適用于不同的場合,提高其魯棒性,本論文將在基本LASPM算法的基礎(chǔ)上提出3個補丁算法(Patch)。當(dāng)某些粒子沒有穩(wěn)定在它們的正確位置上時(如粒子為局部最優(yōu)),使用Patch A來標志這些粒子,重新初始化它們的位置,并再次使用LASPM(B)(即基本LASPM定位算法),把它們拉到各自的正確位置上。當(dāng)某些節(jié)點定位偏差很大(即為壞節(jié)點),使用Patch B標識它們,并給它們設(shè)置不同的置信度,并在后面使用定位信息時盡量選擇置信度較高的節(jié)點,而拋棄或少用置信度低的節(jié)點。當(dāng)網(wǎng)絡(luò)中存在節(jié)點動態(tài)變化時,如有傳感器節(jié)點加入或離開網(wǎng)絡(luò),使用Patch C標識這些節(jié)點。通過這3個補丁算法,使得LASPM算法在各種環(huán)境下會都具有良好的穩(wěn)定性和魯棒性。

2.1 Patch A(處理在不必要位置的粒子)

在有些特殊情況下,一些粒子穩(wěn)定在不必要的位置。所謂不必要位置,即粒子所受鄰居彈簧的合力為0,但是至少所受一個分力不為0;正確位置,即節(jié)點所受所有分力都為0時所處的位置。對于未穩(wěn)定在正確位置的粒子,需對其進行處理。

每一個傳感器節(jié)點都可以獲取鄰節(jié)點和它之間的距離,并把這些距離信息和彈簧的長度做比較,找出那些彈簧長度和距離信息不一致節(jié)點的,即不必要位置的粒子,然后把這些粒子從不必要位置處解救出來。

本論文采用以下兩種方案進行修正。

①當(dāng)發(fā)現(xiàn)這些粒子后,對它們的位置重新初始化,再次使用LASPM(B)算法將它們重新運行到新的位置,粒子可以穩(wěn)定在它們的正確位置上。如果粒子運行到它的正確位置附近,它最終將穩(wěn)定在它的正確位置上。

②因大部分節(jié)點都穩(wěn)定在它們的正確位置上,可使用這些信息提高上述特殊粒子的位置精度。在二維系統(tǒng)中,若有3個及以上鄰粒子穩(wěn)定于它們正確位置上,采用極大似然法重新計算該粒子的位置坐標。

(7)

式中:(xi,yi)是需要求解的位置坐標,(xj,yj),(xk,yk),…,(xn,yn)是它的n個鄰節(jié)點的坐標(n≥3),rij0,rik0,…rin0是它和鄰節(jié)點間的距離。將式(7)線性化可得:

(8)

當(dāng)計算出該粒子的坐標后,若這個位置坐標屬于正確的位置,則通過式(10)可計算其他鄰居節(jié)點位置。

如果沒有粒子可用第2種方法來重新初始化位置,剩下的粒子仍用第1種方案重新初始化。當(dāng)處于不必要位置的節(jié)點被重新初始化后,可以再次使用LASPM(B)算法,重新獲取它們的位置。即使再次使用LASPM(B)后,仍然可能存在很少一部分節(jié)點,它們?nèi)匀粵]有運行到正確的虛擬位置上去,這時再次初始化,并再次使用LASPM(B)來減少這些特殊的節(jié)點。由實驗得知,當(dāng)再次使用LASPM(B)一次后,網(wǎng)絡(luò)中所有節(jié)點的定位誤差較小。

根據(jù)以上分析可知,Patch A算法是重新初始化某些節(jié)點的位置坐標,然后再次使用LASPM(B)算法,因此,LASPM(B)算法的某些性能仍然保持,比如計算復(fù)雜度、通信代價、收斂性以及最小誤差平方和最優(yōu)等。

2.2 Patch B(處理壞的節(jié)點粒子)

為了對月球探測器等目標進行更好的定位、跟蹤和控制,必須將那些定位誤差較大的節(jié)點挑選出來單獨處理。在本論文中對每個節(jié)點的位置信息都設(shè)置一個置信度[0,1],數(shù)值越大表明置信度也越高,在實驗中盡可能使用最高置信度節(jié)點的定位信息。本論文中,“定位誤差較大”節(jié)點為:①該節(jié)點不能被定位;②節(jié)點被定位于不必要的位置上。

定理1在2維系統(tǒng)中,如果一個粒子與3個及以上不在一條直線上的其他粒子相連,那么這個粒子可以被定位。

證明如果2個粒子相連,那么這兩個粒子之間的距離可以獲得。當(dāng)有3個粒子j,k,l知道它們的位置坐標以及它們和待定位粒子i的距離,采用以下三邊函數(shù)計算粒子i的坐標(xi,yi):

(9)

本論文將研究一種快速且簡單的方法來找出這些沒有定位很好的節(jié)點,以供月球車的定位和導(dǎo)航等實驗使用。本論文將用2種方法解決該問題,第1種算法較復(fù)雜,具體如下:

Step 1 選出互相連接的3個粒子,將它們放在一個集合內(nèi)。使用這3個粒子,可以構(gòu)建一個相對坐標系。

Step 2 如果有粒子和這個集合中至少3個粒子相連,那么這個粒子也可以被定位。所以將這個粒子也放入該集合中。這個集合中粒子的數(shù)目將會增加。

Step 3 如果有至少3個錨粒子在這個集合內(nèi),那么這個集合的所有粒子都可以通過坐標轉(zhuǎn)換,進行絕對定位。

Step 4 沒有被放在這個集合中的粒子在很大程度上不能被正確定位。

這個算法較復(fù)雜,并且未使用LASPM(B)的信息,須采用新的算法來尋找那些未成功定位的壞節(jié)點。

第2種算法如下:

Step 1 對于每個粒子,如果它處于不必要位置,將該粒子的置信度設(shè)置為0.5;如果它僅有1個或2個鄰居粒子,則設(shè)置該粒子的置信度為0;其他粒子的置信度為1。

Step 2 對于每個粒子,如果它的置信度不等于1,則剪去和它相連的所有彈簧。它將不再是其他粒子的鄰節(jié)點了。同時通知它以前的鄰節(jié)點,從鄰節(jié)點的表內(nèi)刪除自己。

Step 3 重復(fù)Step 1、Step 2,直到?jīng)]有粒子可以需要更改它們的置信度。

傳感器節(jié)點采用上述定位算法后,被分成了3類不同置信度的節(jié)點。在后續(xù)月球探測器定位和導(dǎo)航等應(yīng)用節(jié)點坐標的場合時,盡可能使用更高置信度節(jié)點的定位信息。

2.3 Patch C(處理節(jié)點動態(tài)變化)

隨著探月工程工作時間的增加、探測區(qū)域的增長,會有越來越多的節(jié)點加入或離開該無線傳感器網(wǎng)絡(luò)。在網(wǎng)絡(luò)已成功定位后,須及時處理這些新變化的節(jié)點。

當(dāng)一個新的盲節(jié)點加入網(wǎng)絡(luò)中,它和它的鄰節(jié)點進行通信,獲取它們的位置和它們之間的距離。首先,將它的鄰節(jié)點位置固定住;然后,新的節(jié)點使用LASPM[B]算法計算它的位置;最后,釋放它的鄰居節(jié)點,讓這些鄰節(jié)點使用LASPM算法做小的虛擬移動,以更新它們的位置坐標。當(dāng)一個新的錨節(jié)點加入網(wǎng)絡(luò)中,它和它的鄰節(jié)點通信,告知它的位置坐標。這些鄰節(jié)點可以使用LASPM算法,重新調(diào)整它們的位置坐標。

在某個節(jié)點正運行LASPM算法時,如有新節(jié)點加入,首先通過式(8)計算新節(jié)點大致位置,然后使用LASPM將該節(jié)點的位置信息廣播給它鄰居。鄰節(jié)點收到該位置信息后,將該節(jié)點也加入到合力計算的成員中。

在LASPM算法完成后,如果有某個節(jié)點離開網(wǎng)絡(luò),若該網(wǎng)絡(luò)是靜止網(wǎng)絡(luò)(傳感器節(jié)點在部署后不再移動),其他節(jié)點的位置不須更新,即其他節(jié)點對該變化不做響應(yīng)。如果網(wǎng)絡(luò)是移動網(wǎng)絡(luò),其他節(jié)點將使用LASPM算法再次計算它們的位置。

在運行LASPM算法的過程中,如果有某個節(jié)點突然離開網(wǎng)絡(luò),它的鄰居節(jié)點不會因為該節(jié)點的離開而陷入死鎖。在LASPM算法過程中,每個傳感器節(jié)點都設(shè)置有一個時間閾值。如果在時間閾值之后,它還沒有收到所有鄰居節(jié)點的位置信息,它將只使用目前收到的信息來計算它的位置、速度和加速度。因此,LASPM算法在節(jié)點快速加入或離開的動態(tài)網(wǎng)絡(luò)中仍具有較好的適應(yīng)性。

3 仿真實驗

在本論文中,先驗證簡單迭代定位算法性能,然后深入對LASPM(B)和LASPM(P)算法進行性能驗證評估,最后將LASPM算法與MDS-MAP算法進行比較。

3.1 簡單迭代定位算法仿真實驗

在規(guī)則的二維平面上,隨機均勻分布200個節(jié)點,圖1為該區(qū)域內(nèi)的節(jié)點真實位置分布與通過本定位算法后估計出的位置分布。其中藍色的圓圈所在處表示節(jié)點的真實位置,紅線伸出去的末端為該節(jié)點的估計位置。

在圖1中,本算法在節(jié)點間平均連接度為20,初始測距誤差為5%,錨節(jié)點為20%時,本簡單迭代定位算法的誤差為5%。

圖1 簡單迭代定位算法的節(jié)點定位分布圖

3.2 LASPM(B)和LASPM(P)算法比較

本論文采用Matl對LASPM(B)和LASPM(P)算法進行比較仿真,仿真環(huán)境設(shè)置如下:在10r×10r的區(qū)域中,隨機部署200個節(jié)點。r=1 是單位長度。如果距離誤差是e,真實距離是d,那么測量距離滿足正態(tài)分布d(1+N(0,e))。位置估計誤差 err為R的倍數(shù),R是節(jié)點的傳輸距離(也稱為射頻距離)。

式中:n是盲節(jié)點的數(shù)目,(xei,yei) 是節(jié)點i的估計位置,(xi,yi) 是該節(jié)點的真實位置。

圖2 LASPM算法定位過程(Tforce=1)

LASPM算法的仿真過程如圖2所示,在該仿真實驗中,網(wǎng)絡(luò)中放置40個錨節(jié)點(占總節(jié)點的20%),射頻距離R為1.5r,測距誤差為5%。所有粒子的質(zhì)量均相等,m=1,所有彈簧的彈性常量k=2,阻尼η=2,計算步數(shù)和合力的閾值分別為:lstep=700,Tforce=1,常量c=0.2。每個粒子的虛擬位置被隨機初始化后,網(wǎng)絡(luò)中初始的位置誤差約為2.4R。然后,每個粒子在它們相連的彈簧的作用下,開始受到相應(yīng)的拉力或壓力。在彈力的作用下,粒子的虛擬位置開始變化很快。經(jīng)過25個計算步數(shù)后,每個粒子所受的合力均小于Tforce,此時的定位誤差是0.223 8。各個節(jié)點的估計位置和真實位置見圖3,藍色圓圈為盲節(jié)點的真實位置,紅色圓圈為錨節(jié)點的真實位置,紅線為節(jié)點的位置誤差,線的兩端分別為真實位置和估計位置。網(wǎng)絡(luò)中大部分節(jié)點都已定位在真實位置附近,僅小部分節(jié)點(約20個)定位誤差較大,這些節(jié)點被定位于不必要的位置上。

圖3 LASPM[B]算法定位結(jié)果(Tforce=1)

將這些不必要位置的節(jié)點重新初始化位置坐標,并再使用LASPM(B)一次,即使用Patch A算法,網(wǎng)絡(luò)中節(jié)點的定位誤差下降到0.101 4。各個節(jié)點的估計位置和真實位置見圖4。其將大部分處于不必要位置上。的節(jié)點定位在正確位置上。若再重新初始化,定位誤差將更小。

圖4 LASPM[P]算法定位結(jié)果(Tforce=1)

3.3LASPM算法的魯棒性論證

為了驗證LASPM算法的抗干擾性,即魯棒性,進行了仿真實驗驗證。在該實驗中隨機產(chǎn)生100 個粒子,在每個粒子中,所有節(jié)點的真實位置和虛擬位置都是隨機部署于既定的網(wǎng)絡(luò)區(qū)域內(nèi),各相鄰節(jié)點間的測量距離也隨機設(shè)置(測量誤差),其他參數(shù)與圖3中設(shè)置一致。

圖5、圖6分別為LASPM(B)和LASPM(P)的計算步數(shù)。在LASPM(B)算法中,粒子的 計算步數(shù)均小于300,平均計算步數(shù)小于100。即網(wǎng)絡(luò)節(jié)點的計算步數(shù)比較穩(wěn)定,它不會隨著初始化而劇烈變化。在LASPM(P)算法中,平均計算步數(shù)為160步,即重新初始化后,再次使用LASPM(B)后的平均計算步數(shù)為160-100=60,算法的收斂速度更快。圖7、圖8分別為LASPM(B)和LASPM(P)的定位誤差。在LASPM(B)算法中,最大定位誤差為0.5,平均定位誤差為0.2。在LASPM(P)算法中,平均定位誤差小于0.1,LASPM(P)算法的定位精度更高。

圖5 LASPM(B)的計算步數(shù)

圖6 LASPM(P)的計算步數(shù)

圖7 LASPM(B)的定位誤差

圖8 LASPM(P)的定位誤差

圖9 LASPM(B)的定位誤差V.S.節(jié)點數(shù)

圖10 LASPM(P)的定位誤差V.S.節(jié)點數(shù)

圖11 規(guī)則網(wǎng)絡(luò)的定位誤差

4 LASPM和MDS-MAP的比較

為了進一步驗證LASPM定位算法性能,本論文將其與經(jīng)典的分布式定位算法MDS-MAP進行仿真比較。首先,在規(guī)則網(wǎng)絡(luò)中進行實驗仿真比較。網(wǎng)絡(luò)中總節(jié)點數(shù)200,錨節(jié)點數(shù)10,部署區(qū)域為10r×10r的2維區(qū)域[1]。射頻距離R從1.25增加到2.5,每次增加0.25。隨機部署節(jié)點,傳感器網(wǎng)絡(luò)定位誤差對比如圖11所示。當(dāng)連通度較小時,LASPM算法的定位精度比MDS-MAP低。當(dāng)連通度較大時,兩者精度類似。

另外,在C形網(wǎng)絡(luò)中進行實驗比較。在該實驗中,網(wǎng)絡(luò)節(jié)點數(shù)160,錨節(jié)點數(shù)10,部署區(qū)域為10r×10r的2維C形狀區(qū)域[1]。射頻距離R從1.25增加到2.5,每次增加0.25。相對應(yīng)的連通度分別為8.197 5,11.293 1,14.640 6,18.856 2,22.113 8和27.627 5。隨機部署節(jié)點,LASPM算法的定位精度和MDS-MAP(P)的相似。從圖12可發(fā)現(xiàn)當(dāng)連通度從小變大時,LASPM法的定位精度一直較MDS-MAP(C)的高。這是因為MDS-MAP(C)算法中兩個距離參數(shù)相差巨大,其導(dǎo)致MDS-MAP(C)算法在不規(guī)則區(qū)域內(nèi)定位精度較低。本論文算法只使用節(jié)點間一跳距離,因而定位精度較高。

圖12 C形網(wǎng)絡(luò)的定位誤差

這兩個算法的相關(guān)性能參數(shù)如表1所示,LASPM算法的計算復(fù)雜度、通信復(fù)雜度均比MDS-MAP(C)小。因此,LASPM算法非常適合于大規(guī)模無線傳感器網(wǎng)絡(luò)中。

表1 LASPM與MDS-MAP算法比較

5 結(jié)論

本論文為基于彈簧粒子模型的LASPM算法的衍生和改進。針對適應(yīng)運算存儲能力更低的無線傳感器網(wǎng)絡(luò)節(jié)點,本論文提出了源于LASPM定位思想的簡單迭代算法;為了處理不同無線傳感器網(wǎng)絡(luò)定位過程的不同情況,本論文提出了基于LASPM(B)的3個補丁算法,用來處理節(jié)點定位過程中陷入局部極值,處理壞節(jié)點和處理無線傳感器網(wǎng)絡(luò)節(jié)點動態(tài)加入離開的問題,并仿真實驗驗證這些衍生算法是可行。

[1] 張會新,陳德沅,彭晴晴,等. 一種改進的TDOA無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J]. 傳感技術(shù)學(xué)報,2015,28(3):412-415.[2] Shang Y,Ruml W,Zhang Y,et al. Localization from Connectivity in Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2004,15(11):961-974.

[3] Wang Y,Wang X,Wang D,et al. Range-Free Localization Using Expected Hop Progress in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2009,20(10):1540-1552.

[4] Kulkarni R V,Forster A,Venayagamoorthy G K. Computational Intelligence in Wireless Sensor Networksy[J]. IEEE Journal Communications Surveys and Tutorials,2011,13(1):68-96.

[5] Pandey S,Prasad P,Sinha P,et.al. Localization of Sensor Networks Considering Energy Accuracy Tradeoffs[C]//International Conference on Collaborative Computing:Networking,2005:1-10.

[6] 楊友華,孫麗華,向滿天. 基于質(zhì)點彈簧模型的無線傳感器網(wǎng)絡(luò)非測距定位算法[J]. 傳感技術(shù)學(xué)報,2015(6):914-919.

[7] 陳三風(fēng),梁永生,陳萬明,等. 基于彈簧粒子模型的大規(guī)模WSN定位算法研究[J]. 小型微型計算機系統(tǒng),2012,33(8):1697-1700.

[8] 吳凡,彭力,董國勇. WSN中基于中位線分割的APIT定位算法[J]. 小型微型計算機系統(tǒng),2015,l36(7):1583-1586.

[9] Nguyen V H,Berder O,Langlais C. Distributed Minimum Euclidean Distance Based Precoding for Wireless Sensor Network[C]//International Conference on Computing,Networking and Communi-cations,2015:918-923.

[10] 張震,閆連山,劉江濤,等. 基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J]. 傳感技術(shù)學(xué)報,2011,24(10):1470-1472.

[11] Savarese C,Rabaey J M,Langendoen K. Robust Positioning Algorithm for Distributed Ad-Hoc Wireless Sensor Networks[C]//Proc of the General Track of the Annual Conference on USENIX Annual Technical Conference,Berkeley,CA,USA,2002:317-327.

[12] 馬震,劉云,沈波. 分布式無線傳感器網(wǎng)絡(luò)定位算法MDS-MAP[J]. 通信學(xué)報,2008,29(6):57-63.

[13] 楊文鉑,邢鵬康,劉彥華. 一種基于自適應(yīng)RSSI測距模型的無線傳感器網(wǎng)絡(luò)定位方法[J]. 傳感技術(shù)學(xué)報,2015,28(1):137-141.

陳三風(fēng)(1979-),女,博士,,副教授,碩士生導(dǎo)師,主要研究方向為無線傳感器網(wǎng)絡(luò),機器人學(xué)等,chensanf@sziit.edu.cn;

盧鑫(1975-),男,工學(xué)博士,教授,主要研究領(lǐng)域為通信技術(shù),物聯(lián)網(wǎng)等。

DerivativeLocalizationAlgorithmsBasedonaSpringParticleModel(LASPM)forLargeScaleWirelessSensorNetworks*

CHENSanfeng1,2*,HANXin1,2,ZHANShaobin1,2,HUTao1,2,LUXin1,2,CHENWanming3

(1.Institute of Information Technology,Shenzhen Institute of Information Technology,Shenzhen Guangdong 518029,China; 2.School of Mechanical and Electrical Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China; 3.Department of Automation,University of Science and Technology of China,Hefei 230027,China)

To improve the robustness of localization algorithm based on a spring particle model(LASPM)for large-scale wireless sensor networks,some derivative algorithms based on basic LASPM algorithm are proposed. A simpler iterative algorithm is proposed for weak particles. Three patches of the basic LASPM algorithm are proposed to avoid local optimization,kick out bad nodes and deal with node variation. Simulation results show that the computational and communication complexity are almost constant despite the increase of the scale of the network. The time consumption has also been proven to remain almost constant since the calculation steps unrelated to the scale of the network. The proposed localization algorithms are shown with sound robustness.

localization algorithm;spring particle model;large scale wireless sensor networks;derivative algorithms;complexity

項目來源:廣東省自然科學(xué)基金項目(2015A030313587;深圳市科技計劃項目(JCY20160307100530069,GRCK20160415111850716)

2017-01-25修改日期:2017-05-12

TP393

:A

:1004-1699(2017)09-1405-07

10.3969/j.issn.1004-1699.2017.09.018