張乙竹，周禮爭(zhēng)，唐 瑞，余 敏

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

0 引 言

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

目前現(xiàn)有的定位算法根據(jù)是否需要測(cè)量節(jié)點(diǎn)間的距離分為基于測(cè)距(range-based)和基于非測(cè)距(range-free)兩大類。基于測(cè)距技術(shù)主要有RSSI，TOA，TDOA，AOA 等。其中，RSSI 測(cè)距技術(shù)依據(jù)接收信號(hào)強(qiáng)度，計(jì)算出收發(fā)節(jié)點(diǎn)間距離，因其成本低廉、能耗低，在無線定位技術(shù)中得到廣泛應(yīng)用。

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

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

1 三邊測(cè)量定位算法原理

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

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

解方程組(1)即得未知節(jié)點(diǎn)的坐標(biāo)

其中

由于受環(huán)境等因素影響，通過Shadowing 經(jīng)驗(yàn)?zāi)Ｐ停?］得到距離存在誤差，從而導(dǎo)致未知節(jié)點(diǎn)估計(jì)坐標(biāo)與真實(shí)值存在一定誤差，記為

2 KCPD-WCLA 設(shè)計(jì)

1)n 能被3 整除

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

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

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

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

即n%3=1，選取未知節(jié)點(diǎn)得到的RSSI 值最大對(duì)應(yīng)距離值與剩余的那個(gè)距離值進(jìn)行計(jì)算。如剩余距離值是最小距離值，則選取第二、三小距離值進(jìn)行計(jì)算，得［n/3］+1 個(gè)接近真實(shí)距離的估計(jì)位置。

將上述結(jié)果作為K-means 聚類樣本集。KCPD-WCLA設(shè)計(jì)主要經(jīng)過二個(gè)步驟，步驟1 給出了K-means 聚類［7］具體過程;KCPD-WCLA 實(shí)現(xiàn)由步驟2 給出。

步驟1:K-means 聚類

1)數(shù)據(jù)預(yù)處理

因?yàn)榛赗SSI 測(cè)距得到距離值存在誤差，導(dǎo)致得到的聚類樣本誤差累積，須進(jìn)行處理;否則，會(huì)嚴(yán)重影響后續(xù)定位算法的執(zhí)行。

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

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

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

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

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

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

步驟2:KCPD-WCLA 實(shí)現(xiàn)

1)由步驟1 得到k 個(gè)聚類，聚類集合記為W，包括各聚類點(diǎn)集合及其點(diǎn)個(gè)數(shù)ni。

2)K-means 聚類算法具有各聚類內(nèi)樣本緊密度高、聚類間差異度大、得到的k 個(gè)集合包含點(diǎn)個(gè)數(shù)不盡相同等特點(diǎn)。先選擇各聚類的聚類中心作為質(zhì)心定位算法中多邊形頂點(diǎn)，即把C 作為多邊形頂點(diǎn);當(dāng)?shù)趇 個(gè)聚類wi中包含點(diǎn)個(gè)數(shù)ni越大，說明未知節(jié)點(diǎn)在wi中出現(xiàn)機(jī)率越大，基于此給予該聚類越大權(quán)重，則KCPD-WCLA 表達(dá)式如下

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

1)算法計(jì)算復(fù)雜度分析

圖2 計(jì)算次數(shù)比較Fig 2 Comparison of computation times

2)定位精度比較

隨機(jī)布設(shè)500 個(gè)節(jié)點(diǎn)，錨節(jié)點(diǎn)數(shù)從50 個(gè)增到200 個(gè)，每次增加25 個(gè)。節(jié)點(diǎn)部署如圖3 所示，其中正方形代表未知節(jié)點(diǎn)真實(shí)位置，菱形代表錨節(jié)點(diǎn)。仿真如圖4、圖5。

圖3 WSNs 節(jié)點(diǎn)部署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%，且當(dāng)n=150 時(shí)，定位誤差基本穩(wěn)定。

4 結(jié) 論

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

［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］ 孫大洋，錢志鴻，韓夢(mèng)飛，等.無線傳感網(wǎng)絡(luò)中多邊定位的聚類分析改進(jìn)算法［J］.電子學(xué)報(bào)，2014，42(8):1601－1607.

［4］ 曹開來，余 敏.無線傳感器網(wǎng)絡(luò)煤礦井下RSSI 自適應(yīng)定位算法［J］.傳感器與微系統(tǒng)，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］ 朱明輝，張會(huì)清.基于RSSI 的室內(nèi)測(cè)距模型的研究［J］.傳感器與微系統(tǒng)，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.