基于K-means 聚類點密度的WSNs 加權質心定位算法*

張乙竹，周禮爭，唐 瑞，余 敏

(1.江西師范大學 計算機信息工程學院，江西 南昌330022;2.江西師范大學 軟件學院，江西 南昌330022)

0 引 言

無線傳感器網絡(WSNs)［1］是由大量的傳感器節點組成，通過無線通信方式形成的自組織多跳網絡，廣泛應用于交通、安全、軍事、醫療等領域，具有很廣闊的應用前景。

目前現有的定位算法根據是否需要測量節點間的距離分為基于測距(range-based)和基于非測距(range-free)兩大類?；跍y距技術主要有RSSI，TOA，TDOA，AOA 等。其中，RSSI 測距技術依據接收信號強度，計算出收發節點間距離，因其成本低廉、能耗低，在無線定位技術中得到廣泛應用。

三邊測量法是目前最容易實現的定位算法之一，它是利用三個錨節點來確定未知節點的位置，然而單次估算的坐標值無法準確反映未知節點真實位置;文獻［2］中提出利用三邊測量法來估計三維點云圖的方法;文獻［3］中提出一種聚類改進多邊定位算法(MLA);文獻［4］結合煤礦井下特征，提出一種自適應RSSI 三角加權質心定位算法(WCLA);文獻［5］采用RSSI 進行測距并使用Zig Bee 進行定位。

由于K-means 聚類算法在處理大數據集時具有相對可伸縮和高效率特點，正好符合WSNs 環境中大量錨節點組成的數據集。據此，本文提出一種基于K-means 聚類點密度的加權質心定位算法(KCPD-WCLA)，首次對各聚類中點的密度加以考慮。理論與仿真結果均表明:改進的算法操作性強，定位誤差更小。

1 三邊測量定位算法原理

三邊測量定位法是以已知的三個錨節點為圓心，以錨節點到未知節點距離為半徑做圓，得到三個圓交點，建立方程組求解出定位結果。定位原理如圖1 所示。

圖1 三邊定位原理Fig 1 Trilateral positioning principle

解方程組(1)即得未知節點的坐標

其中

由于受環境等因素影響，通過Shadowing 經驗模型［6］得到距離存在誤差，從而導致未知節點估計坐標與真實值存在一定誤差，記為

2 KCPD-WCLA 設計

1)n 能被3 整除

即n%3=0(%表示取模)，得到n/3 個接近真實距離的估計位置。

2)n 不能被3 整除且余數為2

即n%3=2，因為與未知節點距離越近的錨節點在傳播過程中受環境影響越小，得到距離值誤差也越小，所以，選取未知節點得到的RSSI 值最大對應距離值，再與剩余的兩個距離值進行分組求解，可在一定程度上減小誤差。如剩余兩個距離值有一個或兩個都是最小距離值，則選取第二或第三小距離值計算，得［n/3］+1(［］表示取不大于n/3的最大整數)個接近真實距離的估計位置。

3)n 不能被3 整除且余數為1

即n%3=1，選取未知節點得到的RSSI 值最大對應距離值與剩余的那個距離值進行計算。如剩余距離值是最小距離值，則選取第二、三小距離值進行計算，得［n/3］+1 個接近真實距離的估計位置。

將上述結果作為K-means 聚類樣本集。KCPD-WCLA設計主要經過二個步驟，步驟1 給出了K-means 聚類［7］具體過程;KCPD-WCLA 實現由步驟2 給出。

步驟1:K-means 聚類

1)數據預處理

因為基于RSSI 測距得到距離值存在誤差，導致得到的聚類樣本誤差累積，須進行處理;否則，會嚴重影響后續定位算法的執行。

首先掃描一次樣本集，計算每一個樣本與其它樣本距離，累加求其距離和，并計算距離和均值。如果某樣本與其它樣本距離和大于距離和均值，則將其舍棄，重復舍棄所有不合規定樣本。最后得到的新數據集就是聚類初始集合。設預處理后得到的m 個聚類樣本集合為M={(xi，yi)|i=1，2，…，m}。

2)K-means 聚類算法執行步驟

a.初始化:輸入初始樣本集合和聚類個數k。隨機選擇k 個樣本作為k 個簇的各自中心，記為C={(cxi，cyi)|i=1，2，…，k}。

b.分配M:計算剩下的m－k 個樣本到k 個聚類中心距離dij(第i 個樣本到第j 個聚類中心距離)，把dij中最小的樣本i 劃分到聚類j。當m－k 個樣本全劃分到聚類，則組成k 個聚類集，記為W={wi|i=1，2，…，k}。

c.修正W:取各聚類中所有元素平均值作為新的聚類中心，重復找到所有聚類中心C'={(c'xi，c'yi) |i=1，2，…，k}。

d.判斷C'是否等于C:若C'=C，則算法結束;否則，令C'=C，返回步驟b。

步驟2:KCPD-WCLA 實現

1)由步驟1 得到k 個聚類，聚類集合記為W，包括各聚類點集合及其點個數ni。

2)K-means 聚類算法具有各聚類內樣本緊密度高、聚類間差異度大、得到的k 個集合包含點個數不盡相同等特點。先選擇各聚類的聚類中心作為質心定位算法中多邊形頂點，即把C 作為多邊形頂點;當第i 個聚類wi中包含點個數ni越大，說明未知節點在wi中出現機率越大，基于此給予該聚類越大權重，則KCPD-WCLA 表達式如下

3 仿真實驗與結果分析

本文采用Matlab 對提出的算法進行仿真實驗，以此來驗證算法的有效性。實驗環境設置在200 m×200 m 的正方形區域內，未知節點布設在中心(100，100)m 處，設置參數k=5。為降低偶然性誤差，在相同環境下進行50 次實驗取平均值。在區域內改變布設的錨節點個數得到一系列未知節點坐標估計值，并與多邊定位算法(MLA)和WCLA 進行比較。

1)算法計算復雜度分析

圖2 計算次數比較Fig 2 Comparison of computation times

2)定位精度比較

隨機布設500 個節點，錨節點數從50 個增到200 個，每次增加25 個。節點部署如圖3 所示，其中正方形代表未知節點真實位置，菱形代表錨節點。仿真如圖4、圖5。

圖3 WSNs 節點部署Fig 3 WSNs node deployment

圖4 平均定位誤差Fig 4 Average localization error

圖5 最大定位誤差Fig 5 The maximum localization error

從圖4、圖5 可得，隨著n 增加，KCPD-WCLA 平均定位誤差和最大定位誤差都有明顯下降，平均定位誤差比MLA小50.1%，比WCLA 小34.9%;最大定位誤差比MLA 小46.7%，比WCLA 小27.8%，且當n=150 時，定位誤差基本穩定。

4 結 論

本文在原始數據分組的基礎上，采用了不重復的三個距離信息進行分組，大大降低了運算量，同時把K-means 聚類算法引入到WSNs 定位中，提出KCPD-WCLA。仿真結果表明:該算法比MLA 和WCLA 在定位精度上有明顯改善，具有可操作性強，定位精度高等優勢，符合WSNs 一般性應用場景，具有普遍適用性。

［1］ Rabindra Bista，Yong-Ki Kim，Jae-Woo Chang.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］ Hyun Chul Roh，Yungeun Choe，Jinyong Jung，et al.Position estimation of land-mark using 3D Point cloud and trilateration method［C］∥The 11th International Conference on Ubiquitous Robots and Ambient Intelligence，Kuala Lumpur，Malaysia:IEEE，2014:298－302.

［3］ 孫大洋，錢志鴻，韓夢飛，等.無線傳感網絡中多邊定位的聚類分析改進算法［J］.電子學報，2014，42(8):1601－1607.

［4］ 曹開來，余 敏.無線傳感器網絡煤礦井下RSSI 自適應定位算法［J］.傳感器與微系統，2014，33(6):129－132.

［5］ Heinemann Anna，Gavriilidis Alexandros，Sablik Thomas，et al.RSSI-based real-time indoor positioning using Zig Bee technology for security applications［C］∥The 7th International Conference on Multimedia Communications Services and Security，Krakow，Poland:IEEE，2014:83－95.

［6］ 朱明輝，張會清.基于RSSI 的室內測距模型的研究［J］.傳感器與微系統，2010，29(8):19－22.

［7］ Reche Cristina，Viana Mar，Brines Mariola，et al.Determinants of aerosol lung-deposited surface area variation in an urban environment［J］.The Science of the Total Environment，2015，517(1):38－47.