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

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

1 引言

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

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

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

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

2 定位模型與分組計(jì)算

無(wú)線傳感網(wǎng)中有N個(gè)已知傳感器節(jié)點(diǎn)參與定位，設(shè)各已知傳感器節(jié)點(diǎn)坐標(biāo)為(xj，yj)，未知節(jié)點(diǎn)坐標(biāo)為(x，y)。第 j個(gè)傳感器節(jié)點(diǎn)通過(guò)對(duì)未知節(jié)點(diǎn)發(fā)射信號(hào)的測(cè)量，得到TOAτj，轉(zhuǎn)換為T(mén)OA距離值為 Lj，則有：

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

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

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

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

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

式中：

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

式中 Wi為對(duì)角矩陣，且為 Wi=diag(，…，)， σi，j為無(wú)線傳感網(wǎng)的TOA測(cè)量誤差標(biāo)準(zhǔn)差。

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

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

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

由于 R=x2+y2，以 γi=[x2，y2]T為未知矢量，則其對(duì)應(yīng)的誤差矢量為：

式中：

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

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

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

3 DBSCAN定位處理

3.1 DBSCAN算法模型

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

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

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

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

定義5（直接密度可達(dá)）點(diǎn) p從點(diǎn)q直接密度可達(dá)，需要滿足：

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

定義7（密度連接）點(diǎn) p和點(diǎn)q是密度連接的，若對(duì)任意的o，使 p和q都從o密度可達(dá)。

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

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

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

3.2 算法描述

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

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

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

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

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

圖2 DBSCAN算法流程圖

3.3 定位處理步驟

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

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

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

步驟3如果P是核心點(diǎn)，半徑為Eps的P的領(lǐng)域中包含的對(duì)象不少于MinPts，點(diǎn)P的類(lèi)號(hào)賦值為ClusterID；如果P是一個(gè)邊界點(diǎn)，則半徑為Eps的鄰域包含的點(diǎn)數(shù)小于MinPts則沒(méi)有點(diǎn)從P密度可達(dá)。

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

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

4 計(jì)算機(jī)仿真分析

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

圖3為本文定位方法利用DBSCAN對(duì)定位結(jié)果的一個(gè)聚類(lèi)點(diǎn)圖實(shí)例，黃點(diǎn)為某一次的定位結(jié)果點(diǎn)，紅星點(diǎn)是利用DBSCAN提取的定位中心點(diǎn)，圖3反應(yīng)出DBSCAN能夠很好地獲取定位結(jié)果中心點(diǎn)。

圖3 DBSCAN對(duì)定位結(jié)果的一個(gè)聚類(lèi)點(diǎn)圖實(shí)例

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

[1]李建中，高宏.無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(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]張令文，談?wù)褫x.基于泰勒級(jí)數(shù)展開(kāi)的蜂窩TDOA定位算法[J].通信學(xué)報(bào)，2007，28（6）：7-11.

[6]王建輝，陳樂(lè)然，胡捍英.一種新的NLOS誤差抑制算法[J].電子與信息學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)三維定位算法[J].計(jì)算機(jī)應(yīng)用，2012，32（4）：927-931.

[9]劉衛(wèi)寧，曾嬋娟，孫棣華.基于DBSCAN算法的營(yíng)運(yùn)車(chē)輛超速點(diǎn)聚類(lèi)分析[J].計(jì)算機(jī)工程，2009，35（5）：268-270.

[10]榮秋生，顏君彪，郭國(guó)強(qiáng).基于DBSCAN聚類(lèi)算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2004，24（4）：45-46.

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

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

基于DBSCAN的無(wú)線傳感網(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)境下，為了獲得更好的定位性能，由多個(gè)已知傳感器節(jié)點(diǎn)測(cè)量來(lái)自未知節(jié)點(diǎn)的電波到達(dá)時(shí)間TOA，對(duì)TOA測(cè)量數(shù)據(jù)進(jìn)行分組處理和加權(quán)最小二乘估計(jì)進(jìn)而獲得未知節(jié)點(diǎn)的初步定位結(jié)果，依據(jù)多次測(cè)量和估計(jì)并采用DBSCAN進(jìn)行聚類(lèi)處理從而剔除壞點(diǎn)獲得較小的定位誤差，實(shí)現(xiàn)了對(duì)未知節(jié)點(diǎn)的精確定位，最后進(jìn)行實(shí)驗(yàn)仿真。計(jì)算機(jī)仿真結(jié)果表明所提出的定位方法能有效地抑制NLOS誤差，具有較小的定位誤差，魯棒性較強(qiáng)，并較其他傳統(tǒng)定位法進(jìn)一步提高了定位精度。

無(wú)線傳感網(wǎng)；定位；傳感器節(jié)點(diǎn)；基于密度的加噪空間聚類(lèi)應(yīng)用算法（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.

湖南省科技廳科技計(jì)劃項(xiàng)目（No.2011GK3164）。

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

2012-10-18

2013-01-10

1002-8331（2013）11-0080-04