基于DBSCAN的無線傳感網定位方法

湖南科技學院 現代教育技術中心，湖南 永州 425100

湖南科技學院 現代教育技術中心，湖南 永州 425100

1 引言

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

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

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

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

2 定位模型與分組計算

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

圖1 網絡布局模型圖

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

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

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

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

式中：

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

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

則構造總的誤差矢量ξi的協方差矩陣為：

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

于是得到了Qi的加權最小二乘法的估計值：

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

式中：

得其加權最小二乘解為：

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

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

3 DBSCAN定位處理

3.1 DBSCAN算法模型

定義1（密度）空間中任意一點的密度是以該點為圓心，以Eps為半徑的圓區域內包含點數目。

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

定義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）數據庫D的非空集合C是一個類，當且僅當C滿足以下條件：（1）對于 p，q，若 p∈C，且從p密度可達到 q，則 q∈C ；（2）對于 p，q，有 p∈C 和q∈C，則 p和q是密度連接的。

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

DBSCAN算法是基于密度來進行聚類，通過判斷數據點是否是核心點來發現類。

3.2 算法描述

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

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

（2）根據該聚類中的核對象，循環收集密度可達的核對象加入該聚類直到沒有新的核對象加入為止。

（3）若不存在不在任何聚類內的核對象則結束，否則執行（1）。

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

圖2 DBSCAN算法流程圖

3.3 定位處理步驟

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

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

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

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

步驟4搜索所有與P密度可達的對象，將它們的類號賦值為ClusterID，考察下一個該聚類中的核心點，循環收集密度可達的核心點加入該聚類直到沒有新的核心點加入為止，否則轉至步驟2直至遍歷完數據集合。

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

4 計算機仿真分析

參與定位的已知傳感器節點個數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的高斯分布，個數因子 β=0.7。定位性能以均值定位誤差ALE（Average Location Errors）vs.累計概率密度CDF（Cumulative Distribution Function）性能作參照。RMSE為均方根定位誤差的均值。

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

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

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

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

表1 NLOS服從高斯分布時的RMSE數據

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

表2 NLOS服從均勻分布時的RMSE數據

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

表3 NLOS服從高斯分布時的CEP數據

表4 NLOS服從高斯分布時的RMSE數據

5 結束語

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

[1]李建中，高宏.無線傳感器網絡的研究進展[J].計算機研究與發展，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]張令文，談振輝.基于泰勒級數展開的蜂窩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]朱曉娟.煤礦井下無線傳感器網絡節點三維定位算法[J].計算機應用，2012，32（4）：927-931.

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

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

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

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

基于DBSCAN的無線傳感網定位方法

朱烜璋

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

無線傳感網；定位；傳感器節點；基于密度的加噪空間聚類應用算法（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會員，研究方向：計算機仿真技術、通信網絡。E-mail：hellozhuxz@163.com

2012-10-18

2013-01-10

1002-8331（2013）11-0080-04