朱齊媛,馬興灶

?

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中三邊定位的聚類(lèi)分析改進(jìn)算法

朱齊媛1,馬興灶2*

1. 嶺南師范學(xué)院 信息工程學(xué)院, 廣東 湛江 524048 2. 嶺南師范學(xué)院 機(jī)電工程學(xué)院, 廣東 湛江 524048

為提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSN)節(jié)點(diǎn)定位精度，本文提出一種基于RSSI三邊定位聚類(lèi)改進(jìn)算法。該算法基于RSSI向量在三邊測(cè)量定位的結(jié)果中引入聚類(lèi)優(yōu)化算法，最后得到未知節(jié)點(diǎn)的定位結(jié)果。數(shù)據(jù)表明，該算法在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)未知節(jié)點(diǎn)的定位中定位精度和定位誤差都有改進(jìn)。

無(wú)線(xiàn)傳感器網(wǎng)路; RSSI; 聚類(lèi)分析

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（Wireless Sensor Network, WSN）[1]中使用一定數(shù)量的無(wú)線(xiàn)傳感器，用特定的網(wǎng)絡(luò)形態(tài)，傳達(dá)網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)的被感知對(duì)象的指定信息并傳輸?shù)街付康牡?。通常情況下，那些低成本的、低功耗的無(wú)線(xiàn)傳感器節(jié)點(diǎn)被隨機(jī)拋灑到預(yù)設(shè)地監(jiān)控區(qū)域，通過(guò)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，人們即可實(shí)時(shí)獲取事件位置或信息節(jié)點(diǎn)位置，完成對(duì)該區(qū)域的監(jiān)控。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中如果不知道位置信息，那么即使是獲取到了準(zhǔn)確的傳感數(shù)據(jù)，對(duì)于系統(tǒng)而言，分析這些數(shù)據(jù)也是無(wú)意義的[2]。由此可見(jiàn)，節(jié)點(diǎn)定位就成為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中對(duì)所感知的數(shù)據(jù)或者事件進(jìn)行跟蹤或分析的重要要求之一。

在諸多的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)定位算法中，大致分為兩類(lèi)，以TOA、TDOA、AOA以及RSSI為代表的與距離相關(guān)的；另一類(lèi)是與距離無(wú)關(guān)，以物聯(lián)網(wǎng)的連通性為必要條件，算法包括有質(zhì)心算法、DV-Hop等[3]。目前，大部分無(wú)線(xiàn)傳感器模塊自帶RSSI值，無(wú)須額外硬件，精度高、簡(jiǎn)單可靠。在實(shí)際應(yīng)用的環(huán)境中卻會(huì)因?yàn)橄到y(tǒng)內(nèi)部（硬件物理噪聲、測(cè)量參數(shù)設(shè)置）和系統(tǒng)外部（自然環(huán)境中的對(duì)無(wú)線(xiàn)電信號(hào)的散射與干涉）等因素，致使實(shí)際的測(cè)量結(jié)果與理論結(jié)果存在一定程度的誤差，文獻(xiàn)[4]就針對(duì)傳輸模型提出了對(duì)RSSI數(shù)據(jù)通過(guò)求其平均值和粒子濾波，獲取到相對(duì)準(zhǔn)確的RSSI值減小定位誤差。

三邊定位算法是目前應(yīng)用最為廣泛的算法之一[5]，在已知的三個(gè)信標(biāo)節(jié)點(diǎn)位置信息，通過(guò)幾何關(guān)系得到未知節(jié)點(diǎn)的位置。關(guān)于定位誤差，很多學(xué)者提出了自己的觀點(diǎn)，例如文獻(xiàn)[6]提出基于聚類(lèi)的多邊定位算法，[7]提出基于聚類(lèi)密度點(diǎn)的質(zhì)心加權(quán)算法等。

聚類(lèi)是一種源于分類(lèi)學(xué)的數(shù)據(jù)分析方法，因其自由伸縮性以及高效性被廣泛地應(yīng)用在多個(gè)領(lǐng)域。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，信標(biāo)節(jié)點(diǎn)不斷接收著大量的未知節(jié)點(diǎn)發(fā)送過(guò)來(lái)的數(shù)據(jù)，這些數(shù)據(jù)大量并且極大可能是多元性的，如此構(gòu)成的數(shù)據(jù)集恰好符合聚類(lèi)算法應(yīng)用的場(chǎng)景。本文將三邊定位算法與聚類(lèi)算法聯(lián)合應(yīng)用到無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位，提出了基于RSSI三邊的聚類(lèi)改進(jìn)分析定位算法，提高節(jié)點(diǎn)定位精度，降低節(jié)點(diǎn)定位誤差。

1 系統(tǒng)模型

1.1 無(wú)線(xiàn)電信道模型

對(duì)數(shù)ㄧ常態(tài)分布模型是無(wú)線(xiàn)信號(hào)傳播模型中最常用的一種。傳播距離以RSSI表示接收到的以dBm為單位的無(wú)線(xiàn)電信號(hào)的強(qiáng)度。通過(guò)對(duì)數(shù)距離路徑損耗模型獲取節(jié)點(diǎn)的RSSI，式(1)為轉(zhuǎn)化模型。

RSSI(d)=RSSI(0）-10log10d/0+(1)

式中發(fā)射點(diǎn)處接收到的信號(hào)強(qiáng)度值為RSSI(d)，表示信號(hào)在0的信號(hào)強(qiáng)度值用RSSI(0)；表示無(wú)線(xiàn)電信號(hào)傳輸路徑的衰減因子，見(jiàn)表1；表示正態(tài)隨機(jī)變量，該變量平均值為0同時(shí)標(biāo)準(zhǔn)差為。一般情況下，對(duì)測(cè)量結(jié)果影響很小。

表1說(shuō)明在不同場(chǎng)景下值的選擇范圍，同時(shí)也說(shuō)明即使在同一場(chǎng)景下，由于節(jié)點(diǎn)所處的具體位置可能也會(huì)有所不同，因此測(cè)距結(jié)果里就會(huì)存在一定比例的異常數(shù)據(jù)。

表 1 不同區(qū)域下路徑損耗的典型值x

1.2 三邊定位算法

未知節(jié)點(diǎn)U通過(guò)諸如RSSI測(cè)量方法獲得信標(biāo)節(jié)點(diǎn)1、2和3到未知節(jié)點(diǎn)U的對(duì)應(yīng)距離1、2和3。以1、2和3為圓心，距離1、2和3為半徑畫(huà)圓，得到三個(gè)圓之間的交點(diǎn)，聯(lián)立方程組即可獲得未知節(jié)點(diǎn)U的定位。定位原理簡(jiǎn)圖如圖1所示。

圖 1 三邊定位原理圖

圖1中信標(biāo)節(jié)分別為1(1,1)，2(2,2)和3(3,3)，到未知節(jié)點(diǎn)的RSSI距離分別為1、2和3，根據(jù)比達(dá)格斯定理，列出方程組：

未知節(jié)點(diǎn)U的估計(jì)坐標(biāo)值為：=[AA]-1Ab (4)

定義誤差以表示，設(shè)未知節(jié)點(diǎn)估計(jì)坐標(biāo)值為則

2 KMC+_TLA算法的過(guò)程

三邊定位算法是這個(gè)算法的基礎(chǔ)，首先在二維平面上，任選三個(gè)距離信息使三邊定位算法得到接近真實(shí)位置的定位結(jié)果。圖2表示的是信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的分布部署，在實(shí)驗(yàn)場(chǎng)景設(shè)置為100 m×100 m的正方形區(qū)域中，如果未知節(jié)點(diǎn)設(shè)置在該區(qū)域的中心位置（50,50），設(shè)置參數(shù)=3，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的距離都滿(mǎn)足正態(tài)分布，取=0.05。

圖 2 信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)部署

2.1 基于RSSI源數(shù)據(jù)預(yù)處理

在距離數(shù)據(jù)集{1,2,…,d}中任取3個(gè)數(shù)據(jù)通過(guò)三邊定位可得到定位結(jié)果。這些結(jié)果用數(shù)據(jù)集合U表示，記作U={(x,y)|=1.2,…,}。

2.2 改進(jìn)的聚類(lèi)算法KMC+以及在三邊定位算法中的應(yīng)用過(guò)程

聚類(lèi)算法-Means(MacQueen:1967)是解決眾所周知的關(guān)于聚類(lèi)問(wèn)題的非監(jiān)督學(xué)習(xí)算法。它針對(duì)指定的數(shù)據(jù)集，按照要求將其分類(lèi)為預(yù)定義的數(shù)據(jù)集，適用于大數(shù)據(jù)集；缺點(diǎn)是值的確定，一般情況下值是隨機(jī)的，然而卻可能致使最后是不同的聚類(lèi)結(jié)果，甚至沒(méi)有解。

KMC+[9]是-Means算法一種改進(jìn)，在延續(xù)經(jīng)典算法優(yōu)勢(shì)的同時(shí)，優(yōu)化對(duì)異常數(shù)據(jù)敏感問(wèn)題。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中大量信標(biāo)節(jié)點(diǎn)數(shù)據(jù)集中，其中由于外界環(huán)境或硬件等因素會(huì)存在一些異常數(shù)據(jù)，定位結(jié)果因此就會(huì)出現(xiàn)誤差[8]。

具體的算法過(guò)程為：

（1）數(shù)據(jù)集U中的數(shù)據(jù)作為待聚類(lèi)的樣本U={(x,y)|=1.2,…,}，首先選定樣本空間中任意一個(gè)樣本作為第一個(gè)聚類(lèi)的中心點(diǎn)1；

（2）計(jì)算除該點(diǎn)之外數(shù)據(jù)點(diǎn)相對(duì)這個(gè)中心點(diǎn)的Euclidean距離1j|=1,2,…,；

（4）計(jì)算所有其他數(shù)據(jù)點(diǎn)到這個(gè)兩個(gè)中心的距離1j，2j|=1,2,…,，再次選出距離最遠(yuǎn)的那個(gè)點(diǎn)作為下一個(gè)聚類(lèi)的中心點(diǎn)C+2；

（5）重復(fù)過(guò)程（3）和過(guò)程（4）直到第個(gè)聚類(lèi)被選擇出來(lái)，，確定各個(gè)聚類(lèi)中心，應(yīng)用經(jīng)典聚類(lèi)算法得到聚類(lèi)結(jié)果{1,2,…,W}。

（6）對(duì)每個(gè)聚類(lèi)內(nèi)對(duì)聚類(lèi)中心求取平均值，結(jié)果即為定位結(jié)果。

3 仿 真

本文的實(shí)驗(yàn)的仿真平臺(tái)采用Matlab2016b，系統(tǒng)配置win10，64位系統(tǒng)，i7處理器，內(nèi)存為16 G。設(shè)置100 m×100 m的檢測(cè)區(qū)域，設(shè)置參數(shù)=5。避免偶然性的誤差，數(shù)據(jù)測(cè)量取50次以上的平均值。隨機(jī)部署節(jié)點(diǎn)200個(gè)（信標(biāo)節(jié)點(diǎn)從5到50個(gè)逐步遞增，遞增單位5個(gè)/次），通信半徑45 m，仿真結(jié)果如圖3、圖4所示。

圖 3 平均定位誤差

圖 4 最大定位誤差

4 討 論

定位仿真的指標(biāo)考核的目標(biāo)即為定位誤差。參與算法對(duì)比的數(shù)據(jù)為文獻(xiàn)[10]提出的聚類(lèi)定位法在和文獻(xiàn)[11]提出的基于坐標(biāo)修正的改進(jìn)型三邊定位算法。

圖3、圖4分別是文獻(xiàn)[10]、文獻(xiàn)[11]算法與本文算法的平均定位誤差比較圖和最大誤差對(duì)比圖。從圖3中可以看出隨著信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)的不斷增加，平均定位誤差在快速降低，從8.9 m~0.6 m，圖4表明最大定位誤差從9 m~0.9 m，比較文獻(xiàn)[10]和[11]無(wú)論是平均定位誤差還是最大定位誤差均有減小20%以上。

隨著信標(biāo)節(jié)點(diǎn)的增加，顯然無(wú)論從平均定位誤差角度還是最大定位誤差角度來(lái)看，誤差變化也都基本趨向于穩(wěn)定。這點(diǎn)說(shuō)明聚類(lèi)算法中值的優(yōu)化選擇在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位中表現(xiàn)良好，值得借鑒。

5 結(jié) 論

針對(duì)-Means聚類(lèi)算法在無(wú)線(xiàn)傳感的定位算法的應(yīng)用過(guò)程中，中心點(diǎn)的選擇對(duì)于異常數(shù)據(jù)的敏感性問(wèn)題，本文提出了一種將改進(jìn)的聚類(lèi)算法引入到基于RSSI的三邊定位算法中。通過(guò)仿真數(shù)據(jù)表明，新的三邊定位算法中改進(jìn)的聚類(lèi)算法里聚類(lèi)中心值得選擇的優(yōu)秀特性有效地提高了未知節(jié)點(diǎn)地定位精度，降低定位誤差。

[1] Bista R, Kim YK, Chang JW. A new approach for energy-balanced data aggregation in wireless sensor networks[C]//Ninth International Conference on Computer and Information Technology, South Korea: IEEE, 2009:9-15

[2] 谷洪亮,史元春.一種用于智能空間的多目標(biāo)跟蹤室內(nèi)定位系統(tǒng)[J].計(jì)算機(jī)學(xué)報(bào),2007,30(9):1603-1611

[3] 王振朝,張琦,張峰.基于RSSI測(cè)距的改進(jìn)加權(quán)質(zhì)心定位算法[J].電測(cè)與儀表,2014,51(21):63-67

[4] 趙珊,付敬奇.基于粒子濾波模型的RSSI測(cè)距優(yōu)化研究[J].電子測(cè)量技術(shù),2016,39(3):122-126

[5] Shuo S, Sun H, Song Y. Design of an experimental indoor position system based on RSSI[C]//2010 2nd International Conference on Information Science and Engineering Hangzhou, China:IEEE, 2010:1989-1992

[6] 孫大洋,錢(qián)志鴻,韓夢(mèng)飛,等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中多邊定位的聚類(lèi)分析改進(jìn)算法[J].電子學(xué)報(bào),2014,42(8):1601-1608

[7] 張乙竹,周禮爭(zhēng),唐瑞,等.基于K-means聚類(lèi)點(diǎn)密度的WSNs加權(quán)質(zhì)心定位算法[J].傳感器與微系統(tǒng),2015,34(7):125-127,131

[8] Akanksha K, Abhishek S. A comparative study of K-Means, K-Means++ and Fuzzy C-Means clustering algorithms" in Computational[J]. Intelligence and Communication Technology, IEEE, 2017:1-6

[9] Arthur D, Vassilvitskii S. k-Means++: the advantages of careful seeding[C]//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orlean: Society for Industrial and Applied Mathematics, 2007:1027-1035

[10] 馮欣,張鵬,徐亞明,等.一種利用K均值聚類(lèi)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué) 版,2013,38(10):1257-1260

[11] 郭世俊,雷虎,何淋,等.基于坐標(biāo)修正的改進(jìn)型三邊定位算法[J].上海海事大學(xué)學(xué)報(bào),2013,38(10):1257-1260

Improved Algorithm of Trilateral Clustering Analysis in Wireless Sensor Network

ZHU Qi-yuan1, MA Xing-zao2*

1.524048,2.524048,

In order to improve the positioning accuracy of wireless sensor network (WSN) nodes, an improved algorithm of tripartite location clustering based on RSSI（ Received Signal Strength Indicator）was proposed. This algorithm was based on the data set of the spatial RSSI vector. It introduced the clustering improvement algorithm into the results of the trilateral localization method and obtained the positioning results of the unknown nodes. The data showed that the algorithm could improve the positioning accuracy and error of the unknown nodes in WSN.

Wireless Sensor Network (WSN); Received Signal Strength Indicator; clustering analysis

TP393

A

1000-2324(2019)03-0473-04

10.3969/j.issn.1000-2324.2019.03.025

2018-04-12

2018-05-23

超聲波輔助熱風(fēng)干燥龍眼能效評(píng)價(jià)與品質(zhì)控制系統(tǒng)研究(2017KQNCX123);緊湊型多模帶通濾波器的設(shè)計(jì)(2014B01131)

朱齊媛(1979-),女,碩士,講師,主要從事物聯(lián)網(wǎng)技術(shù)工作. E-mail:zhuqy1979@lingnan.edu.cn

Author for correspondence. E-mail:maxz@lingnan.edu.cn