一種基于離群點(diǎn)檢測(cè)的定位算法

劉廣聰　郝艷茹　劉　錚

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院　廣東 廣州 510006)

0　引　言

無(wú)線傳感器網(wǎng)絡(luò)WSN作為國(guó)際上備受關(guān)注的研究熱點(diǎn)，已被廣泛應(yīng)用于農(nóng)業(yè)、醫(yī)療、軍事等多個(gè)領(lǐng)域[1]。在各應(yīng)用領(lǐng)域中，傳感器節(jié)點(diǎn)搜集數(shù)據(jù)并將這些數(shù)據(jù)和自身的位置信息上傳到服務(wù)器進(jìn)行分析處理，使無(wú)線傳感器網(wǎng)絡(luò)完成對(duì)周?chē)h(huán)境的感知、探測(cè)和監(jiān)視的功能。無(wú)線傳感器網(wǎng)絡(luò)的定位技術(shù)是實(shí)現(xiàn)上述應(yīng)用的重要基礎(chǔ)，因此傳感器定位技術(shù)至關(guān)重要[2]。

定位技術(shù)分為基于距離的定位算法和距離無(wú)關(guān)的定位算法[3]。前者的定位精度高，但需測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離和角度，對(duì)網(wǎng)絡(luò)中硬件的要求較高[4]。后者根據(jù)網(wǎng)絡(luò)的連通性等信息實(shí)現(xiàn)定位、功耗小、成本低、應(yīng)用范圍較廣，主要包含有質(zhì)心算法、APIT算法和DV-Hop算法等[5]。本文主要研究基于距離無(wú)關(guān)的DV-Hop定位算法。目前已有一些提高DV-Hop定位精度的改進(jìn)方法，如肖少波等在文獻(xiàn)[6]中對(duì)信標(biāo)節(jié)點(diǎn)間跳數(shù)修正，有效地減少了跳距估算帶來(lái)的定位誤差，提高平均定位精度。顧亦然等在文獻(xiàn)[7]中引入信標(biāo)節(jié)點(diǎn)的平均跳距誤差并對(duì)測(cè)距誤差進(jìn)行加權(quán)處理，改進(jìn)后的DV-Hop算法定位誤差減小。李娟等在文獻(xiàn)[8]中采用兩個(gè)通信半徑廣播自身位置信息，從而獲得未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間更精確的跳數(shù)，得到未知節(jié)點(diǎn)更精確的坐標(biāo)。譚博等在文獻(xiàn)[9]采用最小二乘法優(yōu)化信標(biāo)節(jié)點(diǎn)的平均單跳距離進(jìn)而提高DV-Hop算法定位精度?？傮w來(lái)看，上述方法都是分別針對(duì)測(cè)距誤差以及定位求解方法進(jìn)行研究，主要考察如何減小測(cè)距誤差對(duì)定位結(jié)果的影響。雖然對(duì)測(cè)距誤差引起的定位誤差有所改進(jìn)，但對(duì)于具有較大誤差的測(cè)量值，以上方法不能有效減小其對(duì)定位結(jié)果的影響。基于此，本文提出一種基于離群點(diǎn)檢測(cè)算法LOF的多邊定位算法。該算法減小了較大測(cè)距誤差產(chǎn)生的對(duì)定位精度的影響，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證本文算法提高了DV-Hop算法的定位精度。

1　DV-Hop定位算法

DV-Hop定位過(guò)程分為以下三個(gè)階段：

第一階段信標(biāo)節(jié)點(diǎn)不斷向整個(gè)網(wǎng)絡(luò)廣播信息分組{hi,Xi,Yi}，其中hi為跳數(shù)且其初始值為0、Xi、Yi表示該信標(biāo)節(jié)點(diǎn)的橫縱坐標(biāo)。未知節(jié)點(diǎn)記錄來(lái)自各個(gè)信標(biāo)節(jié)點(diǎn)的位置信息和它與每個(gè)信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)值hi，然后將hi值加1后轉(zhuǎn)發(fā)到鄰居節(jié)點(diǎn)。以這種方式，未知節(jié)點(diǎn)得到與每個(gè)信標(biāo)節(jié)點(diǎn)間的最小跳數(shù)和信標(biāo)節(jié)點(diǎn)的位置信息[10]。

第二階段根據(jù)式(1)計(jì)算網(wǎng)絡(luò)中所有信標(biāo)節(jié)點(diǎn)的平均單跳距離Ci。設(shè)信標(biāo)節(jié)點(diǎn)Bi、Bj的坐標(biāo)為(Xi，Yi)、(Xj，Yj)，hij為Bi、Bj間的最小跳數(shù)。

(1)

信標(biāo)節(jié)點(diǎn)將自身的平均單跳距離廣播到傳感器網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅記錄收到的第一個(gè)信標(biāo)節(jié)點(diǎn)的平均單跳距離。然后未知節(jié)點(diǎn)利用記錄的跳數(shù)信息和接收到的平均單跳距離計(jì)算出與各個(gè)信標(biāo)節(jié)點(diǎn)的估計(jì)距離：

dj=Ci×huj

(2)

式中：Ci為未知節(jié)點(diǎn)u收到的第一個(gè)的信標(biāo)節(jié)點(diǎn)的平均單跳距離，huj為未知節(jié)點(diǎn)u與信標(biāo)節(jié)點(diǎn)Bj間的跳數(shù)值，dj為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)Bj間的距離。

第三階段未知節(jié)點(diǎn)根據(jù)到各個(gè)信標(biāo)節(jié)點(diǎn)的估計(jì)距離dj，采用三邊測(cè)量法或極大似然估計(jì)法計(jì)算自身坐標(biāo)位置[11]。

式(3)中(X1，Y1),(X2,Y2),…,(Xn，Yn)為信標(biāo)節(jié)點(diǎn)坐標(biāo)，(X，Y)為未知節(jié)點(diǎn)坐標(biāo)。

(3)

式(3)可以表示成線性方程式AX=B求解。

最后使用最小均方差估計(jì)法得到未知節(jié)點(diǎn)的坐標(biāo)，如下式所示：

(4)

2　改進(jìn)的DV-Hop定位算法

2.1　用加權(quán)方式求得信標(biāo)節(jié)點(diǎn)的平均單跳距離

設(shè)Bi、Bj為信標(biāo)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)Bi的平均單跳距離受到Bi與其余信標(biāo)節(jié)點(diǎn)間的距離影響。若Bi、Bj間的距離較小，則Bj對(duì)Bi的平均單跳距離影響大；若Bi、Bj間的距離較大，則Bj對(duì)Bi的平均單跳距離影響小。據(jù)此提出用加權(quán)系數(shù)ω對(duì)Bi與不同信標(biāo)節(jié)點(diǎn)間的單跳距離加權(quán)來(lái)求得信標(biāo)節(jié)點(diǎn)Bi的平均單跳距離。

信標(biāo)節(jié)點(diǎn)Bi、Bj間的單跳距離用HopSizeij表示，如下式所示：

(5)

(6)

信標(biāo)節(jié)點(diǎn)Bi的平均跳距用式(7)求得：

(7)

最后未知節(jié)點(diǎn)利用最近信標(biāo)節(jié)點(diǎn)修正后的單跳距離HopSizei和與各個(gè)信標(biāo)節(jié)點(diǎn)跳數(shù)值估計(jì)出該未知節(jié)點(diǎn)與各個(gè)信標(biāo)節(jié)點(diǎn)的距離。

2.2　計(jì)算未知節(jié)點(diǎn)坐標(biāo)位置

2.2.1LOF檢測(cè)法的相關(guān)概念

k距離：數(shù)據(jù)集中的任一點(diǎn)o與其第k個(gè)最近鄰節(jié)點(diǎn)之間的距離被稱(chēng)為點(diǎn)o的k距離，記為k-distance(o)。

k距離鄰域：設(shè)o為數(shù)據(jù)集中的任意點(diǎn)，則數(shù)據(jù)集中所有到點(diǎn)o的距離小于o的k距離的點(diǎn)所形成的鄰域稱(chēng)之為k距離鄰域[13]。

Nk(o)：數(shù)據(jù)集中的任意點(diǎn)o的k距離鄰域內(nèi)所包含的所有點(diǎn)的個(gè)數(shù)。

Nk(o)={o′|o′∈D,distance(o,o′)≤distance(o)}

distance(p，q)：對(duì)象p與q間的歐式距離。

可達(dá)距離(reachdistk(q←p))：設(shè)p、q為數(shù)據(jù)集中的任意對(duì)象,點(diǎn)p到點(diǎn)q的可達(dá)距離為p、q點(diǎn)間的歐式距離和q點(diǎn)k距離的最大值即max{k-distance(q)，distance(p，q)}。

局部可達(dá)密度:數(shù)據(jù)點(diǎn)o的局部可達(dá)密度是o點(diǎn)到其鄰域內(nèi)的最大的前k個(gè)距離的平均值的倒數(shù)。lrdk(o)衡量了數(shù)據(jù)點(diǎn)o在其最近的k個(gè)最近點(diǎn)集合內(nèi)的稀疏程度。

(8)

局部離群因子LOFk(q):局部離群因子表示數(shù)據(jù)點(diǎn)q與整體的一種密度差異。若局部離群因子值遠(yuǎn)大于1，則q點(diǎn)周?chē)木植棵芏扰c整體的密度差異較大，認(rèn)為q為離群點(diǎn)。若局部離群因子的值接近1，則q點(diǎn)周?chē)木植棵芏扰c整體密度的差異較小，認(rèn)為q為正常點(diǎn)[14]。

(9)

2.2.2基于離群點(diǎn)檢測(cè)的多邊測(cè)量算法

設(shè)未知節(jié)點(diǎn)能夠感受到的信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)為N,即未知節(jié)點(diǎn)能夠接收到N個(gè)信標(biāo)節(jié)點(diǎn)的距離信息，該距離信息為{d1,d2,…,dN}。處理步驟如下:

1) 對(duì)N的值進(jìn)行判斷，如果N<3則無(wú)法使用多邊測(cè)量法，定位結(jié)束；如果N≥3,則執(zhí)行下一步。

3) 輸入步驟2)中的集合U，按照以下步驟處理集合U中的數(shù)據(jù)。

(1) 在集合U中隨機(jī)選取K個(gè)點(diǎn)作為初始化中心點(diǎn)，記為Ui={(Uix,Uiy)|i=1,2,…,K}，各個(gè)中心點(diǎn)所對(duì)應(yīng)的聚類(lèi)為Ui聚類(lèi)。

(2) 計(jì)算集合U中其余點(diǎn)到Ui聚類(lèi)中各個(gè)中心點(diǎn)的距離，根據(jù)距離最小原則指派各個(gè)數(shù)據(jù)點(diǎn)到距離最近的聚類(lèi)中，重新計(jì)算每個(gè)聚類(lèi)的均值作為聚類(lèi)中心點(diǎn)。

(3) 重復(fù)步驟(2)直至K個(gè)聚類(lèi)的中心點(diǎn)的坐標(biāo)不再改變，分別計(jì)算K個(gè)聚類(lèi)的中心點(diǎn)坐標(biāo)，聚類(lèi)半徑，如下式所示：

(10)

(11)

式中：Xi為Ui聚類(lèi)中的數(shù)據(jù)對(duì)象，ni為Ui聚類(lèi)中數(shù)據(jù)對(duì)象的個(gè)數(shù)。

(4) 計(jì)算各個(gè)Ui聚類(lèi)中的點(diǎn)到Ui聚類(lèi)中心點(diǎn)Ci的歐式距離dij，比較dij與對(duì)應(yīng)聚類(lèi)的聚類(lèi)半徑Ri的大小，若dij大于Ri則將該點(diǎn)標(biāo)記為離群點(diǎn)的候選集中的點(diǎn)。設(shè)候選離群點(diǎn)集為hij。

(12)

Ri為Ui聚類(lèi)的聚類(lèi)半徑，hij屬于Ui聚類(lèi),ni為Ui聚類(lèi)中的數(shù)據(jù)點(diǎn)的個(gè)數(shù)，m為預(yù)設(shè)定的離群點(diǎn)個(gè)數(shù)。

(5) 計(jì)算hij中每個(gè)數(shù)據(jù)對(duì)象的利群因子LOF值，然后根據(jù)各個(gè)數(shù)據(jù)對(duì)象的LOF值對(duì)hij中的數(shù)據(jù)對(duì)象排序，選出LOF最大的前m個(gè)點(diǎn)作為離群點(diǎn), 將m個(gè)離群點(diǎn)去掉重新計(jì)算K個(gè)聚類(lèi)的中心點(diǎn)的坐標(biāo)(Cix,Ciy)其中i=1,2,…,K。

(6)K個(gè)聚類(lèi)中所含數(shù)據(jù)點(diǎn)的個(gè)數(shù)不同，當(dāng)?shù)趇個(gè)聚類(lèi)Ui中所含點(diǎn)的個(gè)數(shù)越大，未知節(jié)點(diǎn)在Ui聚類(lèi)中出現(xiàn)的幾率越大，因此給該聚類(lèi)越大的權(quán)重，未知節(jié)點(diǎn)的坐標(biāo)如下式所示：

(13)

式中：ni為第i個(gè)聚類(lèi)中所含數(shù)據(jù)點(diǎn)的個(gè)數(shù);K為聚類(lèi)個(gè)數(shù)。

3　仿真測(cè)試與結(jié)果分析

為了驗(yàn)證算法的有效性，本文采用MATLAB分別對(duì)傳統(tǒng)的DV-Hop算法和本算法進(jìn)行仿真。假設(shè)所有的仿真實(shí)驗(yàn)所需的環(huán)境都在同一網(wǎng)絡(luò)場(chǎng)景下進(jìn)行的，節(jié)點(diǎn)隨機(jī)部署在二維監(jiān)測(cè)區(qū)域內(nèi)，所有節(jié)點(diǎn)具有一致的通信半徑且通信半徑為R。

定位精度是衡量定位算法優(yōu)劣的一個(gè)主要指標(biāo)[15]如下式所示：

(14)

式中：Eav為平均定位誤差；(xrel，yrel)和(xest，yest)分別是未知節(jié)點(diǎn)的估計(jì)坐標(biāo)和真實(shí)坐標(biāo)；N為總節(jié)點(diǎn)數(shù)量；n為信標(biāo)節(jié)點(diǎn)的數(shù)量；R為節(jié)點(diǎn)的通信半徑。

如圖1是無(wú)線傳感器節(jié)點(diǎn)隨機(jī)分布圖，節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的正方形區(qū)域內(nèi)，其中節(jié)點(diǎn)總數(shù)設(shè)置為100，信標(biāo)節(jié)點(diǎn)數(shù)設(shè)置為10，未知節(jié)點(diǎn)所占比例為90%。

圖1　節(jié)點(diǎn)分布圖

圖2顯示了某個(gè)未知節(jié)點(diǎn)定位結(jié)果，是通過(guò)離群點(diǎn)算法LOF對(duì)未知節(jié)點(diǎn)的估計(jì)坐標(biāo)進(jìn)行分析的一個(gè)實(shí)例圖?！啊痢贝砦粗?jié)點(diǎn)的坐標(biāo)，黑色的點(diǎn)代表聚類(lèi)中的離群點(diǎn)，三角形、圓形、正方形、五角星分別代表密度不同的聚類(lèi)。從圖可以看出，LOF算法能夠很好地識(shí)別離群點(diǎn)，提高未知節(jié)點(diǎn)的定位精度。

圖2　聚類(lèi)優(yōu)化實(shí)例圖

圖3展現(xiàn)了各未知節(jié)點(diǎn)采用本文算法和DH-Hop算法定位后的定位誤差連線圖。單個(gè)節(jié)點(diǎn)的定位誤差為該節(jié)點(diǎn)偏差距離與節(jié)點(diǎn)通信半徑的比值, 使用本文算法和DV-Hop算法定位后的平均定位誤差分別為26.54%、40.13%。本組實(shí)驗(yàn)在100 m×100 m的區(qū)域中隨機(jī)分布100個(gè)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)20個(gè)，未知節(jié)點(diǎn)80個(gè)，節(jié)點(diǎn)通信半徑為20 m，信標(biāo)節(jié)點(diǎn)所占的比例為20%。從圖中可以看出，本文算法的定位精度明顯優(yōu)于DV-Hop算法。

圖3　未知節(jié)點(diǎn)定位誤差對(duì)比圖

圖4表示傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)與定位誤差之間的關(guān)系。本組實(shí)驗(yàn)設(shè)置信標(biāo)節(jié)點(diǎn)所占比例為10%不變，通信半徑為20 m。從圖4中可以看出傳統(tǒng)DV-Hop算法和本文算法在節(jié)點(diǎn)總數(shù)增加的情況下，定位誤差都有所下降，這是因?yàn)樵谕粎^(qū)域內(nèi)節(jié)點(diǎn)密度增加進(jìn)而提高了定位精度。但本文算法平均定位誤差率與 DV-Hop 相比降低了約15.73 %。

圖4　網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)對(duì)定位誤差的影響

圖5反映了信標(biāo)節(jié)點(diǎn)所占比例與定位誤差之間的關(guān)系。本組實(shí)驗(yàn)中，設(shè)置節(jié)點(diǎn)總數(shù)設(shè)為100，節(jié)點(diǎn)通信半徑R為20 m，信標(biāo)節(jié)點(diǎn)所占比例范圍在5%～35%之間變化。從圖中可以看出，兩種定位算法的平均定位誤差都呈遞減趨勢(shì)，都是隨著信標(biāo)節(jié)點(diǎn)的增加平均定位誤差減小。這是因?yàn)殡S著信標(biāo)節(jié)點(diǎn)數(shù)的增加，網(wǎng)絡(luò)連通度增強(qiáng)，定位精度提高。本文算法平均定位誤差率與 DV-Hop 相比降低了約14.65%。

圖5　信標(biāo)節(jié)點(diǎn)所占比例對(duì)定位誤差的影響

圖6反映了網(wǎng)絡(luò)中節(jié)點(diǎn)的通信半徑與定位誤差之間的關(guān)系。本組實(shí)驗(yàn)設(shè)置節(jié)點(diǎn)總數(shù)為100，信標(biāo)節(jié)點(diǎn)總數(shù)為30，節(jié)點(diǎn)的通信半徑在20～50 m之間遞增變化。實(shí)驗(yàn)結(jié)果顯示，隨著通信半徑的增大，平均定位誤差先下降后又有上升的趨勢(shì)。這是因?yàn)楫?dāng)通信半徑很小時(shí)隨著通信半徑的增大節(jié)點(diǎn)間的連通性增強(qiáng)，整體產(chǎn)生的誤差小，所以定位精度提高。當(dāng)通信半徑大于某一臨界值時(shí)會(huì)因?yàn)橥ㄐ虐霃捷^大使得節(jié)點(diǎn)間跳數(shù)太少而導(dǎo)致節(jié)點(diǎn)間估計(jì)距離產(chǎn)生較大的誤差從而導(dǎo)致定位誤差有所增高?？傮w而言，本文算法較傳統(tǒng)DV-Hop算法降低了平均定位誤差。

圖6　通信半徑對(duì)定位誤差的影響

4　結(jié)　語(yǔ)

本文利用離群點(diǎn)多邊測(cè)距算法對(duì)DV-Hop算法進(jìn)行改進(jìn)。在不增加額外硬件設(shè)備的條件下，本算法相比傳統(tǒng)的定位算法能夠有效提高定位精度，減小定位誤差，其定位誤差能夠維持在一個(gè)較小的范圍內(nèi)。本算法增加了傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的計(jì)算量，下一步我們將研究進(jìn)一步提高定位精度的同時(shí)如何降低節(jié)點(diǎn)的計(jì)算量。

[1] 錢(qián)志鴻,王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào),2013,35(1):215-227.

[2] 孫利民,李建中,陳渝,等.無(wú)線傳感器網(wǎng)絡(luò)[M].清華大學(xué)出版社,2005.

[3] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//International Conference on Mobile Computing and NETWORKING.ACM,2005:81-95.

[4] Müller C,Alves D I,Ucha-Filho B F,et al.Improved solution for node location multilateration algorithms in wireless sensor networks[J].Electronics Letters,2016,52(13):1179-1181.

[5] Nicolescu D,Nath B.Ad-Hoc positioning systems(ASP)[C]//Proc.of the 2001 IEEE Global Telecommunications Conference Vol.5,San Antonio:IEEE Communications Society,2001:2926-2931.

[6] 肖少波,朱曉麗,鄒建梅.基于跳數(shù)修正的DV-Hop改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào),2015,28(5):757-762.

[7] 顧亦然,蔣璐璐.一種改進(jìn)無(wú)線傳感器網(wǎng)絡(luò)的DV-Hop定位算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(10):109-112.

[8] 李娟,劉禹,錢(qián)志鴻,等.基于雙通信半徑的傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].吉林大學(xué)學(xué)報(bào),2014,44(2):502-507.

[9] 譚博,車(chē)進(jìn),張成.基于最小二乘法優(yōu)化的加權(quán)DV-Hop改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(2):82-86.

[10] 曹欲曉,嚴(yán)奎,徐金寶.一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2015,28(3):424-429.

[11] Cenedese A,Ortolan G,Bertinato M.Low-Density Wireless Sensor Networks for Localization and Tracking in Critical Environments[J].IEEE Transactions on Vehicular Technology,2010,59(6):2951-2962.

[12] 喬欣,常飛,丁恩杰,等.基于跳距修正的WSN擬牛頓迭代定位算法[J].傳感技術(shù)學(xué)報(bào),2014,27(6):797-801.

[13] 王敬華,趙新想,張國(guó)燕,等.NLOF:一種新的基于密度的局部離群點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)科學(xué),2013,40(8):181-185.

[14] 王習(xí)特,申德榮,白梅.BOD:一種高效的分布式離群點(diǎn)檢測(cè)算法[J].計(jì)算機(jī)學(xué)報(bào),2016,39(1):36-51.

[15] 朱敏,劉昊霖,張志宏,等.一種基于DV-HOP改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2012,44(1):93-98.