無線傳感器網絡中三邊定位的聚類分析改進算法

朱齊媛,馬興灶

?

無線傳感器網絡中三邊定位的聚類分析改進算法

朱齊媛1,馬興灶2*

1. 嶺南師范學院 信息工程學院, 廣東 湛江 524048 2. 嶺南師范學院 機電工程學院, 廣東 湛江 524048

為提高無線傳感器網絡(WSN)節點定位精度，本文提出一種基于RSSI三邊定位聚類改進算法。該算法基于RSSI向量在三邊測量定位的結果中引入聚類優化算法，最后得到未知節點的定位結果。數據表明，該算法在無線傳感器網絡未知節點的定位中定位精度和定位誤差都有改進。

無線傳感器網路; RSSI; 聚類分析

無線傳感器網絡（Wireless Sensor Network, WSN）[1]中使用一定數量的無線傳感器，用特定的網絡形態，傳達網絡覆蓋區域內的被感知對象的指定信息并傳輸到指定目的地。通常情況下，那些低成本的、低功耗的無線傳感器節點被隨機拋灑到預設地監控區域，通過無線傳感器網絡，人們即可實時獲取事件位置或信息節點位置，完成對該區域的監控。在無線傳感器網絡中如果不知道位置信息，那么即使是獲取到了準確的傳感數據，對于系統而言，分析這些數據也是無意義的[2]。由此可見，節點定位就成為無線傳感器網絡中對所感知的數據或者事件進行跟蹤或分析的重要要求之一。

在諸多的無線傳感器網絡中節點定位算法中，大致分為兩類，以TOA、TDOA、AOA以及RSSI為代表的與距離相關的；另一類是與距離無關，以物聯網的連通性為必要條件，算法包括有質心算法、DV-Hop等[3]。目前，大部分無線傳感器模塊自帶RSSI值，無須額外硬件，精度高、簡單可靠。在實際應用的環境中卻會因為系統內部（硬件物理噪聲、測量參數設置）和系統外部（自然環境中的對無線電信號的散射與干涉）等因素，致使實際的測量結果與理論結果存在一定程度的誤差，文獻[4]就針對傳輸模型提出了對RSSI數據通過求其平均值和粒子濾波，獲取到相對準確的RSSI值減小定位誤差。

三邊定位算法是目前應用最為廣泛的算法之一[5]，在已知的三個信標節點位置信息，通過幾何關系得到未知節點的位置。關于定位誤差，很多學者提出了自己的觀點，例如文獻[6]提出基于聚類的多邊定位算法，[7]提出基于聚類密度點的質心加權算法等。

聚類是一種源于分類學的數據分析方法，因其自由伸縮性以及高效性被廣泛地應用在多個領域。在無線傳感器網絡中，信標節點不斷接收著大量的未知節點發送過來的數據，這些數據大量并且極大可能是多元性的，如此構成的數據集恰好符合聚類算法應用的場景。本文將三邊定位算法與聚類算法聯合應用到無線傳感器網絡的節點定位，提出了基于RSSI三邊的聚類改進分析定位算法，提高節點定位精度，降低節點定位誤差。

1 系統模型

1.1 無線電信道模型

對數ㄧ常態分布模型是無線信號傳播模型中最常用的一種。傳播距離以RSSI表示接收到的以dBm為單位的無線電信號的強度。通過對數距離路徑損耗模型獲取節點的RSSI，式(1)為轉化模型。

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

式中發射點處接收到的信號強度值為RSSI(d)，表示信號在0的信號強度值用RSSI(0)；表示無線電信號傳輸路徑的衰減因子，見表1；表示正態隨機變量，該變量平均值為0同時標準差為。一般情況下，對測量結果影響很小。

表1說明在不同場景下值的選擇范圍，同時也說明即使在同一場景下，由于節點所處的具體位置可能也會有所不同，因此測距結果里就會存在一定比例的異常數據。

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

1.2 三邊定位算法

未知節點U通過諸如RSSI測量方法獲得信標節點1、2和3到未知節點U的對應距離1、2和3。以1、2和3為圓心，距離1、2和3為半徑畫圓，得到三個圓之間的交點，聯立方程組即可獲得未知節點U的定位。定位原理簡圖如圖1所示。

圖 1 三邊定位原理圖

圖1中信標節分別為1(1,1)，2(2,2)和3(3,3)，到未知節點的RSSI距離分別為1、2和3，根據比達格斯定理，列出方程組：

未知節點U的估計坐標值為：=[AA]-1Ab (4)

定義誤差以表示，設未知節點估計坐標值為則

2 KMC+_TLA算法的過程

三邊定位算法是這個算法的基礎，首先在二維平面上，任選三個距離信息使三邊定位算法得到接近真實位置的定位結果。圖2表示的是信標節點和未知節點的分布部署，在實驗場景設置為100 m×100 m的正方形區域中，如果未知節點設置在該區域的中心位置（50,50），設置參數=3，信標節點和未知節點之間的距離都滿足正態分布，取=0.05。

圖 2 信標節點與未知節點部署

2.1 基于RSSI源數據預處理

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

2.2 改進的聚類算法KMC+以及在三邊定位算法中的應用過程

聚類算法-Means(MacQueen:1967)是解決眾所周知的關于聚類問題的非監督學習算法。它針對指定的數據集，按照要求將其分類為預定義的數據集，適用于大數據集；缺點是值的確定，一般情況下值是隨機的，然而卻可能致使最后是不同的聚類結果，甚至沒有解。

KMC+[9]是-Means算法一種改進，在延續經典算法優勢的同時，優化對異常數據敏感問題。無線傳感器網絡中大量信標節點數據集中，其中由于外界環境或硬件等因素會存在一些異常數據，定位結果因此就會出現誤差[8]。

具體的算法過程為：

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

（2）計算除該點之外數據點相對這個中心點的Euclidean距離1j|=1,2,…,；

（4）計算所有其他數據點到這個兩個中心的距離1j，2j|=1,2,…,，再次選出距離最遠的那個點作為下一個聚類的中心點C+2；

（5）重復過程（3）和過程（4）直到第個聚類被選擇出來，，確定各個聚類中心，應用經典聚類算法得到聚類結果{1,2,…,W}。

（6）對每個聚類內對聚類中心求取平均值，結果即為定位結果。

3 仿 真

本文的實驗的仿真平臺采用Matlab2016b，系統配置win10，64位系統，i7處理器，內存為16 G。設置100 m×100 m的檢測區域，設置參數=5。避免偶然性的誤差，數據測量取50次以上的平均值。隨機部署節點200個（信標節點從5到50個逐步遞增，遞增單位5個/次），通信半徑45 m，仿真結果如圖3、圖4所示。

圖 3 平均定位誤差

圖 4 最大定位誤差

4 討 論

定位仿真的指標考核的目標即為定位誤差。參與算法對比的數據為文獻[10]提出的聚類定位法在和文獻[11]提出的基于坐標修正的改進型三邊定位算法。

圖3、圖4分別是文獻[10]、文獻[11]算法與本文算法的平均定位誤差比較圖和最大誤差對比圖。從圖3中可以看出隨著信標節點的個數的不斷增加，平均定位誤差在快速降低，從8.9 m~0.6 m，圖4表明最大定位誤差從9 m~0.9 m，比較文獻[10]和[11]無論是平均定位誤差還是最大定位誤差均有減小20%以上。

隨著信標節點的增加，顯然無論從平均定位誤差角度還是最大定位誤差角度來看，誤差變化也都基本趨向于穩定。這點說明聚類算法中值的優化選擇在無線傳感器網絡定位中表現良好，值得借鑒。

5 結 論

針對-Means聚類算法在無線傳感的定位算法的應用過程中，中心點的選擇對于異常數據的敏感性問題，本文提出了一種將改進的聚類算法引入到基于RSSI的三邊定位算法中。通過仿真數據表明，新的三邊定位算法中改進的聚類算法里聚類中心值得選擇的優秀特性有效地提高了未知節點地定位精度，降低定位誤差。

[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] 谷洪亮,史元春.一種用于智能空間的多目標跟蹤室內定位系統[J].計算機學報,2007,30(9):1603-1611

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

[4] 趙珊,付敬奇.基于粒子濾波模型的RSSI測距優化研究[J].電子測量技術,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] 孫大洋,錢志鴻,韓夢飛,等.無線傳感器網絡中多邊定位的聚類分析改進算法[J].電子學報,2014,42(8):1601-1608

[7] 張乙竹,周禮爭,唐瑞,等.基于K-means聚類點密度的WSNs加權質心定位算法[J].傳感器與微系統,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均值聚類的無線傳感器網絡節點定位算法[J].武漢大學學報:信息科學 版,2013,38(10):1257-1260

[11] 郭世俊,雷虎,何淋,等.基于坐標修正的改進型三邊定位算法[J].上海海事大學學報,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

超聲波輔助熱風干燥龍眼能效評價與品質控制系統研究(2017KQNCX123);緊湊型多模帶通濾波器的設計(2014B01131)

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

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