基于DBSCAN的無線傳感網(wǎng)定位方法

湖南科技學院 現(xiàn)代教育技術(shù)中心，湖南 永州 425100

湖南科技學院 現(xiàn)代教育技術(shù)中心，湖南 永州 425100

1 引言

隨著傳感感知技術(shù)和無線通信網(wǎng)絡傳輸技術(shù)的飛速發(fā)展，無線傳感網(wǎng)（Wireless Sensor Network，WSN）以其低功耗、低成本、分布式和自組織的特點帶來了信息科學的一場變革，也使無線傳感網(wǎng)在許多領域有著巨大的科研和應用價值。由于無線傳感器網(wǎng)絡中各傳感器節(jié)點所采集到的數(shù)據(jù)必須結(jié)合其在測量坐標系內(nèi)的位置信息才有意義，而且用戶關(guān)心的不僅是傳輸數(shù)據(jù)本身的內(nèi)容還包括節(jié)點的精確位置信息，于是定位技術(shù)作為無線傳感網(wǎng)中的關(guān)鍵技術(shù)具有十分重要的地位[1]。

對于基于測距的定位方法，無線傳感網(wǎng)中可用于定位的參數(shù)測量量主要有：無線電波的傳播時間、信號場強、相位、入射角度等參數(shù)實現(xiàn)移動目標的定位?，F(xiàn)有定位方案由多個已知節(jié)點同時接收檢測到未知節(jié)點發(fā)射的信號，根據(jù)測量到的參數(shù)由網(wǎng)絡對未知節(jié)點進行定位估計。各種誤差的影響使得定位性能受到嚴重的影響[2-8]。由于無線信道環(huán)境的影響，信號的折射或者反射等非直達傳播就會引起非視距傳播（Non-Line-Of-Sight propagation，NLOS）誤差，它帶來的傳輸時延增加會導致距離測量的不準確。同時，非視距傳播誤差作為無線傳感網(wǎng)定位時最主要的誤差來源，很多學術(shù)文獻提出的定位算法都是研究抑制和消除非視距傳播誤差來提高定位精度。因此，如何有效地提高定位精度成為無線傳感網(wǎng)定位技術(shù)中最關(guān)鍵的問題。傳統(tǒng)的直接矩陣求解定位法[2]，Taylor級數(shù)展開法[5]，LLOP定位法[4]等定位算法在NLOS傳播環(huán)境下定位誤差較大，算法的估計精度較低。

同時，聚類技術(shù)是數(shù)據(jù)挖掘中用來發(fā)現(xiàn)數(shù)據(jù)分布和隱含模式的一項關(guān)鍵技術(shù)。聚類是把大量數(shù)據(jù)點的集合分成若干類，使得每個類中的數(shù)據(jù)之間最大程度地相似，而不同類中的數(shù)據(jù)最大程度地不同。DBSCAN就是其中一種基于密度的聚類算法，通過不斷地搜索鄰近點來使該對象周圍的密度逐漸增加，尋找到一個區(qū)域內(nèi)所查找點或?qū)ο竺芏却蟮牡胤絒9-12]。DBSCAN算法的顯著特點是聚類速度快，且能夠有效處理噪聲點和發(fā)現(xiàn)任意形狀的空間聚類，具有較強的聚類能力。

本文利用已知多個傳感器節(jié)點測量得到的電波到達時間（Time Of Arrival，TOA），然后將這些數(shù)據(jù)進行分組，通過應用加權(quán)最小二乘算法，每組都可以得到一個未知節(jié)點的估計值。在短時間內(nèi)利用已知傳感網(wǎng)節(jié)點網(wǎng)絡對未知節(jié)點進行多次抽樣測量，然后對多次多組估計得到的未知節(jié)點位置進行聚類處理，利用DBSCAN良好的抗噪性和最大程度相似性來減小誤差對定位性能的影響，最終得到未知節(jié)點的精確位置。

2 定位模型與分組計算

無線傳感網(wǎng)中有N個已知傳感器節(jié)點參與定位，設各已知傳感器節(jié)點坐標為(xj，yj)，未知節(jié)點坐標為(x，y)。第 j個傳感器節(jié)點通過對未知節(jié)點發(fā)射信號的測量，得到TOAτj，轉(zhuǎn)換為TOA距離值為 Lj，則有：

圖1 網(wǎng)絡布局模型圖

式中 kj=(xj)2+(yj)2，R=x2+y2。

實際無線傳感網(wǎng)中，由于成本、布局條件等限制，傳感器節(jié)點在距離上比較分散，距離相隔也較遠。未知節(jié)點附近的已知傳感器節(jié)點數(shù)目不會很多，同時由于無線信號在傳輸信道中的衰減，就決定了可以參與該未知節(jié)點定位的已知傳感器節(jié)點不會很多。

將這些已知傳感器測量得到的TOA值進行分組，對于TOA矩陣計算，該組矩陣的秩大于等于3才能獲得解，考慮不滿秩因素，故按照每四個一組進行重復分配，于是共得到組。在第 i組中，原有 Lj、(xj，yj)、kj等參數(shù)分別用Li，j、(xi，j，yi，j)、ki，j符號表示，數(shù)值不變。對于第 i組，以 Qi= [x ，y，R]T為未知矢量，其對應的誤差矢量為：

由于存在距離約束，均可得到以下測距方程：

式中：

采用加權(quán)最小二乘估計，用測量值的協(xié)方差矩陣Wi近似替代誤差矢量ξi的協(xié)方差矩陣，可得：

式中 Wi為對角矩陣，且為 Wi=diag(，…，)， σi，j為無線傳感網(wǎng)的TOA測量誤差標準差。

則構(gòu)造總的誤差矢量ξi的協(xié)方差矩陣為：

式中矩陣 Pi=diag(Li，1，Li，2，…，Li，4)。

于是得到了Qi的加權(quán)最小二乘法的估計值：

由于 R=x2+y2，以 γi=[x2，y2]T為未知矢量，則其對應的誤差矢量為：

式中：

得其加權(quán)最小二乘解為：

最終得到第i組估計得到的未知節(jié)點位置為：

由于在短時間內(nèi)未知節(jié)點靜止，則通過快速多次抽樣測量，即可得到多次多組估計估計得到的未知節(jié)點位置，然后將所有結(jié)果進行DBSCAN聚類處理。

3 DBSCAN定位處理

3.1 DBSCAN算法模型

定義1（密度）空間中任意一點的密度是以該點為圓心，以Eps為半徑的圓區(qū)域內(nèi)包含點數(shù)目。

定義2（Neighborhood，鄰域）空間中任意一點的鄰域是以該點為圓心，以Eps為半徑的圓區(qū)域內(nèi)包含的點集合。記：

定義3（Core Points，核心點）空間中某一點的密度如果大于某一給定閾值MinPts，則稱該點為核心點。

定義4（Border Points，邊界點）空間中某一點的密度如果小于某一給定閾值MinPts，則稱該點為邊界點。

定義5（直接密度可達）點 p從點q直接密度可達，需要滿足：

定義6（密度可達到）點 p從點q密度可達，若(p1，p2，…，pn，其中 p1=p，pn=q)且有 pi從 pi+1直接密度可達。

定義7（密度連接）點 p和點q是密度連接的，若對任意的o，使 p和q都從o密度可達。

定義8（聚類Cluster）數(shù)據(jù)庫D的非空集合C是一個類，當且僅當C滿足以下條件：（1）對于 p，q，若 p∈C，且從p密度可達到 q，則 q∈C ；（2）對于 p，q，有 p∈C 和q∈C，則 p和q是密度連接的。

定義9（噪聲Noise）數(shù)據(jù)庫D中不屬于任何類的點為噪聲。

DBSCAN算法是基于密度來進行聚類，通過判斷數(shù)據(jù)點是否是核心點來發(fā)現(xiàn)類。

3.2 算法描述

假設有一個數(shù)據(jù)對象集，對于給定的Minpts和Eps，DBSCAN算法描述如下：

（1）選擇數(shù)據(jù)對象集中任意一個不屬于任何聚類且滿足核條件的對象p，創(chuàng)建一個新的聚類。

（2）根據(jù)該聚類中的核對象，循環(huán)收集密度可達的核對象加入該聚類直到?jīng)]有新的核對象加入為止。

（3）若不存在不在任何聚類內(nèi)的核對象則結(jié)束，否則執(zhí)行（1）。

DBSCAN算法可以發(fā)現(xiàn)任意形狀的聚類，具有較強的聚類能力。在DBSCAN算法中參數(shù)Eps的值在很大程度上影響最終的聚類結(jié)果。其流程圖如圖2所示。

圖2 DBSCAN算法流程圖

3.3 定位處理步驟

步驟1將已經(jīng)通過定位分組計算得到的二維空間的n個位置點形成一個原始數(shù)據(jù)集合S={s1，s2，…，sn}，設置類號ClusterID用于存貯聚類個數(shù)結(jié)果，初始化最小對象數(shù)MinPts=βn，其中 β(0＜β≤1)為設計的個數(shù)因子，設置密度半徑：

其中Smax為集合S里面的最大值，Smin為集合S里面的最小值，Prod(*)表示返回向量*的乘積，gamma(*)為伽馬分布。

步驟2利用DBSCAN算法，從集合S中選擇一個未標記的點P，并查找集合中關(guān)于Eps和MinPts的從P密度可達的所有點。

步驟3如果P是核心點，半徑為Eps的P的領域中包含的對象不少于MinPts，點P的類號賦值為ClusterID；如果P是一個邊界點，則半徑為Eps的鄰域包含的點數(shù)小于MinPts則沒有點從P密度可達。

步驟4搜索所有與P密度可達的對象，將它們的類號賦值為ClusterID，考察下一個該聚類中的核心點，循環(huán)收集密度可達的核心點加入該聚類直到?jīng)]有新的核心點加入為止，否則轉(zhuǎn)至步驟2直至遍歷完數(shù)據(jù)集合。

步驟5將擁有最多數(shù)據(jù)點的ClusterID聚類的邊界點去除，將該聚類的所有核心點取出成另外一個集合S'，該集合剔除了邊界點和“噪聲壞點”，故將集合S'的值取平均，最終得到的數(shù)據(jù)值便作為對未知節(jié)點的最終估計位置。

4 計算機仿真分析

參與定位的已知傳感器節(jié)點個數(shù)N=10，坐標分別為(0，0)、(0，2)、(0，5)、(1，2)、(1，4)、(3，1)、(3，3)、(3，6)、(5，2)、(5，5)（單位：km）。TOA測量誤差服從均值為0，標準差為20 m的高斯分布，個數(shù)因子 β=0.7。定位性能以均值定位誤差ALE（Average Location Errors）vs.累計概率密度CDF（Cumulative Distribution Function）性能作參照。RMSE為均方根定位誤差的均值。

圖3為本文定位方法利用DBSCAN對定位結(jié)果的一個聚類點圖實例，黃點為某一次的定位結(jié)果點，紅星點是利用DBSCAN提取的定位中心點，圖3反應出DBSCAN能夠很好地獲取定位結(jié)果中心點。

圖3 DBSCAN對定位結(jié)果的一個聚類點圖實例

圖4和表1是NLOS誤差服從均值為300 m，方差為80 m的高斯分布時的CDF性能比較圖。圖5和表2為NLOS誤差服從[0，300]（單位：m）的均勻分布時的CDF性能比較圖。從以上仿真結(jié)果可以看出在具有相同均值定位誤差時本文方法的CDF最高，同時在相同條件下其RMSE定位誤差最小，也就是說本文方法較傳統(tǒng)定位方法性能優(yōu)越，能有效地抑制誤差影響，具有較高的定位精度。

圖4 CDF性能比較圖（NLOS服從高斯分布）

表1 NLOS服從高斯分布時的RMSE數(shù)據(jù)

圖5 CDF性能比較圖（NLOS服從均勻分布）

表2 NLOS服從均勻分布時的RMSE數(shù)據(jù)

改變β取值，考慮反應定位誤差特征的CEP值（Circular Error Probable，圓誤差半徑性能）[7]作為準則，不同 β值對本文所提出方法的影響見表3和表4，NLOS為服從圖4和表1相同的高斯分布。從表3和表4可以看出，本文方法在不同β值時性能變化不大，CEP和RMSE變化不大，對定位結(jié)果的影響不明顯，由于本文定位方法創(chuàng)新設計的個數(shù)因子 β控制了DBSCAN算法的Eps和MinPts兩個核心參數(shù)，故本文設計的個數(shù)因子 β可以有效地處理定位應用，具有較強的魯棒性，定位結(jié)果不依賴于影響密度半徑和最小對象數(shù)，具有靈活實用性。

表3 NLOS服從高斯分布時的CEP數(shù)據(jù)

表4 NLOS服從高斯分布時的RMSE數(shù)據(jù)

5 結(jié)束語

無線傳感網(wǎng)定位技術(shù)的發(fā)展對定位性能和定位精度提出了越來越高的要求。本文提出了一種結(jié)合DBSCAN算法來進行未知節(jié)點定位的新思想，與現(xiàn)有方法相比具有很好的定位效果，在NLOS誤差環(huán)境下定位精度較高，魯棒性較強，性能穩(wěn)定。

[1]李建中，高宏.無線傳感器網(wǎng)絡的研究進展[J].計算機研究與發(fā)展，2008，45（1）：1-15.

[2]Chan E C L，Bacieu G.Wireless tracking analysis in location fingerprinting[C]//Proc of IEEE International Conference on Wireless and Mobile Computing.Greece：IEEE Press，2008.

[3]Seow C K.Non-line-of-sight localization in multipath environments[J].IEEE Transactions on Mobile Computing，2008，7（5）：647-660.

[4]Caffery J J.A new approach to the geometry of TOA location[C]//IEEE VTC，2000，4：1943-1949.

[5]張令文，談振輝.基于泰勒級數(shù)展開的蜂窩TDOA定位算法[J].通信學報，2007，28（6）：7-11.

[6]王建輝，陳樂然，胡捍英.一種新的NLOS誤差抑制算法[J].電子與信息學報，2008，30（6）：1424-1427.

[7]Cheung K W，So H C，Ma W K，et al.Least squares algorithms fortime-of-arrival-based mobile location[J].IEEE Trans on Signal Processing，2004，52（4）：1121-1128.

[8]朱曉娟.煤礦井下無線傳感器網(wǎng)絡節(jié)點三維定位算法[J].計算機應用，2012，32（4）：927-931.

[9]劉衛(wèi)寧，曾嬋娟，孫棣華.基于DBSCAN算法的營運車輛超速點聚類分析[J].計算機工程，2009，35（5）：268-270.

[10]榮秋生，顏君彪，郭國強.基于DBSCAN聚類算法的研究與實現(xiàn)[J].計算機應用，2004，24（4）：45-46.

[11]于亞飛，周愛武.一種改進的DBSCAN密度算法[J].計算機技術(shù)與發(fā)展，2011，21（2）：30-33.

[12]歐陽佳，林丕源.基于DBSCAN算法的網(wǎng)頁正文提取[J].計算機工程，2011，37（3）：64-66.

基于DBSCAN的無線傳感網(wǎng)定位方法

朱烜璋

ZHU Xuanzhang

Center of Educational Technology,Hunan University of Science and Engineering,Yongzhou,Hunan 425100,China

Under the NLOS（Non-Line-Of-Sight）propagation environments,in order to achieve better location performance,a localization method based on DBSCAN in wireless sensor networks is proposed in this paper.The TOA（Time Of Arrival）from the unknown node is measured by many sensor nodes,then the weighted least squares estimation algorithm is used after data packet processing.According to multiple measurements and estimations,the DBSCAN（Density-Based Spatial Clustering of Applications with Noise）is used to tick off the bad location results to mitigate the location error.The experimental simulations have done.Simulation results show that the proposed location method can restrain the location error effectively and get the precise position of the unknown node,can improve the location accuracy than traditional methods.

wireless sensor networks;location;sensor node;Density-Based Spatial Clustering of Applications with Noise（DBSCAN）; Non-Line-Of-Sight（NLOS）

在NLOS傳播環(huán)境下，為了獲得更好的定位性能，由多個已知傳感器節(jié)點測量來自未知節(jié)點的電波到達時間TOA，對TOA測量數(shù)據(jù)進行分組處理和加權(quán)最小二乘估計進而獲得未知節(jié)點的初步定位結(jié)果，依據(jù)多次測量和估計并采用DBSCAN進行聚類處理從而剔除壞點獲得較小的定位誤差，實現(xiàn)了對未知節(jié)點的精確定位，最后進行實驗仿真。計算機仿真結(jié)果表明所提出的定位方法能有效地抑制NLOS誤差，具有較小的定位誤差，魯棒性較強，并較其他傳統(tǒng)定位法進一步提高了定位精度。

無線傳感網(wǎng)；定位；傳感器節(jié)點；基于密度的加噪空間聚類應用算法（DBSCAN）；非視距傳播

A

TP393.1

10.3778/j.issn.1002-8331.1210-0189

ZHU Xuanzhang.Location method based on DBSCAN in wireless sensor networks.Computer Engineering and Applications,2013,49（11）：80-83.

湖南省科技廳科技計劃項目（No.2011GK3164）。

朱烜璋（1981—），男，講師，CCF會員，研究方向：計算機仿真技術(shù)、通信網(wǎng)絡。E-mail：hellozhuxz@163.com

2012-10-18

2013-01-10

1002-8331（2013）11-0080-04