一種基于FCM的DV-HOP定位算法

孫愛晶,李益佳

(西安郵電大學 通信與信息工程學院,陜西 西安 710121)

無線傳感器網絡(Wireless Sensor Network,WSN)現在已經廣泛應用于各個領域。在WSN中,傳感器節點對覆蓋范圍內的對象進行信息的采集和傳播[1-2]。如果傳感器節點的位置不明確,得到的信息價值將會降低。因此,WSN中節點的定位問題尤為重要,其中距離矢量跳數定位[3](Distance Vector Hop,DV-HOP)算法因其成本低、且易于部署等優點得到廣泛應用,但DV-HOP算法定位誤差較大。

很多研究者對DV-HOP定位算法進行了相關改進以減小定位誤差。文獻[4]通過對數據分組結構的改進降低了平均每跳距離的誤差,但該方法容易受節點分布的影響。文獻[5]通過多通信半徑廣播錨節點位置信息,并結合節點遠近度修正待定位節點與錨節點的測距值減小定位誤差,但該方法需要較高的錨節點密度。文獻[6]利用機器學習中極限學習機計算未知節點的位置,訓練的數據只能適用于當前部署的定位環境且需要大量的錨節點。文獻[7]在未知節點定位之前對錨節點進行安全檢測以減少定位干擾,并沒有充分利用錨節點的信息。

大多數的改進算法都是以節點部署較為均勻為前提,通過各種方法降低定位誤差。但是,在實際應用中,定位區域內節點的分布受環境、地形及氣候等因素的影響,往往是不均勻的。為了降低DV-HOP算法在錨節點密度低且節點分布不均勻的定位環境下的定位誤差,擬提出一種用模糊C-均值算法(Fuzzy C-Means,FCM)改進的DV-HOP定位算法。該算法提出了相似度與關聯度的概念,通過FCM算法對錨節點進行分簇并提出了分簇策略,未知節點根據所提入簇策略進行簇內定位,然后進行簇間坐標的融合以實現全局定位。最后,將所提算法與DV-HOP定位算法、基于粒子群改進的DV-HOP[8](DV-HOP for Particle Swarm Optimization,PSODV-HOP)定位算法以及基于幾何改進的DV-HOP[9](Improved DV-HOP,IDV-HOP)定位算法進行了定位誤差的對比仿真實驗,從而驗證所提算法的有效性。

1 基本問題描述

目前的定位算法根據是否基于測距分為基于測距的定位算法與無需測距的定位算法[10]?；跍y距的定位算法包括接收信號強度指示 (Receiver Signal Strength Indicator,RSSI)、到達時間差[11](Time Difference of Arrival,TDOA)及到達角度[12]( Angle of Arrival,AOA)等算法。與距離有關的定位算法通常需要額外的硬件進行信號參數的測量,因而成本高且不適宜大面積部署。無需測距的定位算法包括DV-HOP定位算法[4]、多維定標(Multidimen-Sional Scaling,MDS)算法[13]及質心定位算法[14]等。在無需測距的定位算法中,通常給少量的節點配備全球定位系統(Global Positioning System,GPS)使之成為位置已知的錨節點。然后未知節點根據其與錨節點之間的位置關系與拓撲關系計算自身位置,因此無需測距的定位算法成本低且適合大規模的WSN部署應用。其中,DV-HOP定位算法因實施簡單且易于擴充等優點而受到關注。

DV-HOP定位算法容易受到錨節點數目以及節點分布的影響,導致平均跳距與最小跳數有較大的誤差,從而在后續的計算中造成較大的定位誤差。在實際應用中因環境等因素出現網絡中的節點分布不均勻的情況,會進一步加劇網絡中平均跳距與最小跳數的誤差。為了改善在節點分布不均勻環境下定位誤差較大的問題,在現有研究的基礎上,提出在DV-HOP定位算法的基礎上引入FCM對節點進行分簇定位的算法。所提算法在分簇階段使用FCM算法對錨節點進行分簇,為了防止分簇后簇內錨節點數目不能滿足定位的需求,提出了與相似度相關的分簇策略,而未知節點則根據與各簇錨節點的關聯度進行入簇定位,以期通過所提算法中分簇定位的思想減少節點分布不均勻對平均跳距和最小跳數影響,進而降低定位誤差。

2 DV-HOP定位算法原理及誤差分析

2.1 DV-HOP定位算法原理

DV-HOP定位算法是由D.Niculescu和B.Nath提出的基于分布式無需測距原理的定位算法[15],類似于傳統網絡中的距離向量路由機制。假設在定位環境中有n個錨節點、m個未知節點(n≥3且m?n)。一個未知節點至少要與3個錨節點產生距離關系才能建立可解方程組求解其位置。因此,n≥3是必要條件。而m?n是要確保通過少量錨節點定位未知節點,從而保證算法實際應用上的合理性。

DV-HOP定位算法在定位時,首先計算節點之間的最小跳數,然后計算錨節點平均每跳的距離,利用最小跳數與平均跳距估算未知節點與錨節點之間的距離,最后用最小二乘法計算未知節點的坐標。DV-HOP定位算法具體包括計算節點間的最小跳數、計算錨節點的平均跳距、計算未知節點到錨節點的距離和最小二乘法計算未知節點的坐標等4個步驟。

步驟1計算節點間的最小跳數。首先,錨節點通過泛洪廣播的方式向網絡中的鄰居節點發送數據包。數據包中包括節點的位置信息和跳數初始值,即初始跳數設為0跳。節點每收到一個數據包,都會將跳值增加1,并將數據保存在其位置信息表中。然后,該節點會將跳值增加的數據包轉發到其鄰居節點,并丟棄來自同一節點的跳值更大的數據包。從節點的位置信息表可以得到節點之間的最小跳數。

步驟2計算錨節點的平均跳距。得到節點之間的最小跳數之后,錨節點用接收到的其他錨節點的位置數據和最小跳數計算該錨節點的平均跳距,其表達式為

(1)

式中：(xi,yi)與(xj,yj)分別表示錨節點i與錨節點j的坐標;hij表示錨節點i與錨節點j之間的最小跳數。此時,得到每個錨節點的平均跳距。

步驟3計算未知節點到錨節點的距離。當錨節點向網絡發送其平均跳距時,未知節點在第一次接收到錨節點的平均跳距之后,用該錨節點的平均跳距計算從未知節點到各個錨節點的直線距離,即未知節點u到錨節點i之間的計算距離,其表達式為

dui=Sihui

(2)

式中,hui表示未知節點u到錨節點i的跳數。

步驟4最小二乘法計算未知節點的坐標,其原理是通過各個錨節點到未知節點的距離計算出未知節點的坐標。在DV-HOP定位算法中,所有的錨節點都參與未知節點的定位,未知節點按照式(2)計算到各個錨節點的距離并與錨節點建立距離方程組,其表達式為

(3)

式中：(x1,y1),(x1,y1),…,(xn,yn)分別表示n個錨節點的坐標;(xu,yu)表示未知節點u的坐標。

用最小二乘法對式(3)的方程組進行求解,將式(3)的前(n-1)個方程分別與第n方程進行線性變換后得到的線性矩陣為

AX=B

(4)

其中,

式中：A表示錨節點的信息矩陣;X表示未知節點的坐標矩陣;B表示錨節點的距離矩陣。

(5)

2.2 DV-HOP定位算法的誤差分析

2.2.1 錨節點對DV-HOP定位算法的影響

DV-HOP定位算法通常使用定位環境內的所有錨節點參與未知節點的定位,具體的錨節點對DV-HOP定位算法的影響如圖1所示,圖1中的圓點為未知節點,五角星為錨節點。

圖1 錨節點對DV-HOP算法的影響

圖1中DV-HOP定位算法會用全部的4個錨節點定位未知節點,但錨節點a距離未知節點較遠,此時盲目地使用所有錨節點會帶來較大的定位誤差。因此,在定位未知節點時要根據錨節點與未知節點的關系有選擇地使用錨節點?？紤]對錨節點按照距離關系進行分簇,將圓內的錨節點分為一簇。未知節點進入該簇定位,避免了錨節點a帶來的定位誤差。因此,采用分簇錨節點的方法對錨節點進行選擇,可以避免DV-HOP定位算法中盲目使用所有錨節點帶來的定位誤差。

2.2.2 節點分布對DV-HOP定位算法的影響

通常在DV-HOP定位算法應用的定位環境中,將節點的分布默認為是一種較為均勻的分布,節點分布較均勻的定位環境如圖2所示,定位環境內無較大的無節點空白區域。但是,受地形、氣候及氣候等因素的影響,部署節點時節點的分布有可能是不均勻的。當與圖2同樣數目的節點分布不均勻時,節點分布不均勻定位環境如圖3所示,定位環境內出現較大的無節點空白區域。所提算法大都是在節點分布較均勻的定位環境情況下提出的,在節點分布不均勻定位環境中定位效果往往不太好。因此,所提算法能更好地適應節點分布不均勻的定位環境。

圖2 節點分布較均勻的定位環境

圖3 節點分布不均勻定位環境

由圖2和圖3可以看出,在圖2較為均勻的定位環境中,錨節點a1到未知節點u1的跳數為4跳。在圖3中由于節點的不均勻分布,在定位環環境內存在大塊無節點的空白區域,此時用最小跳數與平均跳距得到的距離會出現嚴重的誤差。當節點分布不均勻時,由于空白區域的影響產生了多余的曲折路徑,此時錨節點a1到未知節點u1的跳數為8跳,而實際上兩點之間的距離并沒有這么大。在節點分布不均勻的環境下與分布較為均勻的環境下跳數相差4跳,此時根據式(2)得到的估算距離誤差很大,從而導致存在較大的定位誤差。

3 FCM算法

為了避免所有的錨節點參與定位帶來的定位誤差,考慮引入FCM算法[16]對DV-HOP算法進行改進,即根據距離分簇錨節點實現對未知節點的分簇定位。FCM算法是基于劃分聚類的算法,廣泛應用于圖像分割中。FCM的思想是使得被劃分到同一簇的對象之間盡可能相似,而不同簇之間的差異盡可能大。在無線傳感器網絡中可以表現為節點對某一聚類中心的隸屬度是模糊的,隸屬度可以表示為

(6)

式中：pij表示節點i對聚類中心j的隸屬度;q表示聚類的數目。點i對所有的聚類中心的隸屬度總和為1。

如果存在n個錨節點被隨機分布在定位環境內,網絡的聚類中心數為q。此時,FCM算法可以通過將目標函數最小化,使得整個網絡的錨節點按地理相似度分為q類,則FCM算法的目標函數為

(7)

式中：?為模糊系數;dij為第個i錨節點與第j個聚類中心的歐氏距離。

隸屬度pij可以表示為

(8)

式中,dik為第個i錨節點與第k個聚類中心的歐氏距離。

聚類中心cj可以表示為

(9)

式中,xj表示第j個錨節點。

當迭代停止時,輸出錨節點的聚類結果。此時,FCM算法對錨節點進行分簇之后,就會把分布最緊密的錨節點分為一簇。

4 基于FCM的DV-HOP定位算法

所提算法在DV-HOP算法的基礎上引入FCM算法進行分簇定位,并定義了相似度與關聯度,提出錨節點的分簇策略與未知節點的入簇策略。

4.1 錨節點分簇策略

DV-HOP算法在網絡中廣播得到節點之間的最小跳數和平均跳距之后,引入FCM算法將位置已知的錨節點按照節點之間的距離分簇。

假設將定位環境中的n個錨節點分為l簇,r1為第一簇,r1內的所有錨節點數為a。一般l的取值根據網絡中的錨節點數及其分布情況進行設定?？紤]到實際情況,l取值不應過大,在仿真環境中經過驗證,將l設為3是比較合理的。此外,還要保證每一個簇內的錨節點數不少于3,才能與未知節點建立可解方程組(3)求解未知節點的坐標。如果簇內的錨節點數目大于等于3,那么該簇可以進行簇內定位;如果簇內錨節點的數目小于3,那么要將與該簇相似度最小的非本簇錨節點依次納入該簇,直到該簇的錨節點數目大于等于3。

定義錨節點的相似度為D,若r1內的錨節點數小于3,對r1進行非本簇錨節點的入簇,則第j個不屬于r1簇的錨節點對r1的相似度的表達式為

(10)

當Djr1值越大,說明錨節點j與r1簇的距離就越大,值越小則說明錨節點j與r1簇的距離越小。

每次選擇相似度最小的錨節點,才能使得入簇之后的錨節點與簇內原本的錨節點距離最小。分簇錨節點減小了傳統算法中使用全部的錨節點參與定位帶來的定位誤差。

4.2 未知節點入簇策略

將錨節點分簇且保證每一個簇都滿足定位要求之后,未知節點根據關聯度進行入簇定位。

假設此時r1簇內的錨節點為b(b≥3),未知節點的關聯度為H。此時未知節點u對r1簇的關聯度的表達式為

(11)

式中,hui表示未知節點u與錨節點i之間的跳數。關聯度Hur1值越大,說明錨節點i與r1簇的跳數越大;關聯度Hur1值越小,則說明錨節點i與r1簇的跳數越小。

考慮跳數的大小在一定程度上反映了距離的大小,因此要選擇與簇r1關聯度最小的未知節點入簇。此時,入簇之后的未知節點與該簇的跳數最小,從而降低了定位誤差。

4.3 簇間坐標的整合

將定位環境中的n個錨節點分為l簇,若每一簇定位v個未知節點,則第l個簇求得的未知節點坐標信息為

(12)

將l個簇的未知節點坐標進行融合,得到的全局未知節點的坐標矩陣為

(13)

此時,經過FCM算法改進的DV-HOP定位算法完成定位環境內所有未知節點的定位。

4.4 改進算法流程

通過引入FCM算法對DV-HOP定位算法進行優化,設計了錨節點的分簇策略以及未知節點的入簇策略,得到了一種基于FCM算法的DV-HOP定位算法,其具體的流程如圖4所示?；贔CM算法的DV-HOP定位算法是一種分簇定位的思想,其在DV-HOP定位算法中定義了相似度與關聯度的概念并引入FCM算法制定了分簇策略與入簇策略。首先,通過FCM算法將所有的錨節點根據歐氏距離進行分簇。然后,錨節點根據分簇策略確保每一簇都能完成對未知節點的定位,而未知節點則通過入簇策略分別進入不同的錨節點簇進行定位。最后,各個簇進行簇間坐標的融合以實現全局未知節點的定位。所提算法將全局定位轉化為分簇定位,增強了算法對節點分布的適應性。

圖4 基于FCM的DV-HOP定位算法流程

5 實驗與仿真

5.1 仿真環境

為了驗證所提算法的有效性,在100 m×100 m的定位區域內,部署100個無線傳感器節點,分別在節點分布較為均勻和節點分布不均勻的定位環境中進行兩組實驗。

對定位算法評價的指標是節點的平均定位誤差e,其表達式為

(14)

5.2 仿真結果及分析

5.2.1 節點分布較為均勻的定位環境

在如圖5所示的節點分布較為均勻的定位環境內,保持節點總數為100個、錨節點比例為8%及節點的通信半徑為25.0 m。DV-HOP定位算法與所提算法分別對各個節點的定位誤差進行仿真,各個節點定位誤差仿真結果分別如圖6和圖7所示。

圖5 節點較為均勻分布環境

圖7 基于FCM的DV-HOP定位算法的節點定位誤差

由圖5、圖6及圖7可以看出：在節點分布較為均勻的定位環境下,DV-HOP定位算法各個節點的定位誤差主要集中在20.0～60.0 m內,其平均定位誤差為42.4 m;所提算法各個節點的定位誤差主要集中在10.0～30.0 m內,而其平均定位誤差為24.9 m。在節點分布較為均勻的稀疏錨節點定位環境中,所提算法的平均定位誤差較DV-HOP定位算法降低41.2%,這說明提出的改進算法在稀疏錨節點且節點分布較為均勻的定位環境下有明顯效果。

在圖5所示的定位環境下保持節點總數為100個、節點的通信半徑為25.0 m,將錨節點的密度依次設為5%、10%、15%、20%、25%、30%,分別對所提算法、DV-HOP定位算法、PSODV-HOP定位算法[15]與IDV-HOP定位算法[16]的平均定位誤差進行仿真,具體的均勻分布下錨節點比例對平均定位誤差的影響結果如圖8所示。

圖8 錨節點比例對平均定位誤差的影響

由圖8可以看出,所提算法、DV-HOP定位算法、PSODV-HOP定位算法以及IDV-HOP定位算法等4種算法在節點分布較為均勻環境下,當錨節點比例變化時平均定位誤差的變化情況。由于錨節點數目越多和有效信息越多,平均定位誤差越小,各種算法的平均定位誤差均隨著錨節點數目的增加而降低,因此平均定位誤差均隨著錨節點數目的增加而降低。當錨節點為5個時,DV-HOP定位算法的平均定位誤差為51.2 m,PSODV-HOP定位算法的定位誤差為43.3 m,IDV-HOP定位算法的定位誤差為35.2 m,所提算法的平均定位誤差為37.7 m。此時,所提算法的平均定位誤差略高于IDV-HOP定位算法。當錨節點大于10個之后,所提算法的平均定位誤差迅速下降并明顯低于其他3種算法。由此可見,所提算法是有效的。

5.2.2 節點分布不均勻的定位環境

節點分布不均勻的定位環境即存在大塊無節點的空白區域中保持節點總數為100個、錨節點比例為8%、節點通信半徑為25.0 m,如圖9所示。用DV-HOP定位算法與所提算法分別對各個節點的定位誤差進行仿真,節點定位誤差仿真結果分別如圖10和圖11所示。

圖9 節點不均勻分布環境

圖10 DV-HOP定位算法的節點定位誤差

圖11 基于FCM的DV-HOP定位算法的節點定位誤差

由圖9、圖10和圖11可以看出：在節點分不均勻的定位環境下,由于節點的不均勻分布且定位時未對錨節點進行選擇,導致部分未知節點的定位誤差較小,而大部分未知節點的定位誤差較大,DV-HOP定位算法的平均定位誤差為47.8 m;各個節點的定位誤差主要集中在20.0 m附近,與DV-HOP定位算法相比,所提算法節點定位誤差大于 40.0 m的節點顯著減少,而其平均定位誤差為20.5 m。所提算法與DV-HOP定位算法相比,平均定位誤差降低57.1%,這說明所提算法在稀疏錨節點且節點分布不均勻定位環境下效果明顯。

在圖9所示的定位環境下保持節點總數為100個、節點的通信半徑為25.0 m,將錨節點的密度依次設為5%、10%、15%、20%、25%、30%,分別對所提算法、DV-HOP定位算法、PSODV-HOP定位算法和IDV-HOP定位算法的平均定位誤差進行仿真,不均勻分布下錨節點比例對平均定位誤差的影響結果如圖12所示。

圖12 錨節點比例對平均定位誤差的影響

由圖12可以看出,所提算法、DV-HOP定位算法、PSODV-HOP定位算法以及IDV-HOP定位算法等4種算法在節點分布不均勻定位環境下當錨節點比例變化時的平均定位誤差。當錨節點為20時,所提算法的平均定位誤差與另外3種定位算法相比,分別降低52%、45%與31%。仿真結果表明,隨著錨節點的比例增加,4種算法的平均定位誤差都在逐漸降低,但在不均勻分布下的定位環境中,所提算法的定位誤差顯著低于其他的3種算法,這說明所提算法能夠更好地適應不均勻的定位環境。

6 結語

針對DV-HOP定位算法在錨節點稀疏且未知節點分布不均勻的定位環境下存在的定位誤差較大的問題,提出了基于FCM算法的DV-HOP算法。所提算法定義了錨節點的相似度與未知節點的關聯度,并基于此提出了錨節點的分簇策略與未知節點的入簇策略。首先,引入FCM算法,對錨節點按照距離進行分簇后采用分簇策略,以減少所有錨節點參與定位所帶來的定位誤差。其次,未知節點根據入簇策略進行簇內定位,從而減少了未知節點分布不均勻帶來的定位誤差。最后,為了驗證所提算法的有效性,將其與DV-HOP定位算法、PSODV-HOP定位算法及IDV-HOP定位算法等3種算法分別在節點分布較為均勻和節點分布不均勻的定位環境下進行對比。在節點分布較為均勻的定位環境下,當錨節點為5個時,所提算法的平均定位誤差略高于IDV-HOP定位算法;當錨節點大于10個之后,所提算法平均定位誤差迅速下降并明顯低于其他3種算法。在節點分布不均勻的定位環境下,4種算法的平均定位誤差雖然都在逐漸降低,但所提算法的定位誤差顯著低于其他3種算法。仿真結果表明,所提算法不僅有較低的定位誤差,還能夠更好地適應不均勻的節點分布環境。