WSN室內(nèi)快速指紋匹配的定位算法

趙志信， 李加君， 謝玉鵬

(1.黑龍江科技大學 電子與信息工程學院，哈爾濱 150022； 2.清華大學 電子工程系，北京 100084)

WSN室內(nèi)快速指紋匹配的定位算法

趙志信1,2， 李加君1， 謝玉鵬1

(1.黑龍江科技大學 電子與信息工程學院，哈爾濱 150022； 2.清華大學 電子工程系，北京 100084)

針對現(xiàn)有室內(nèi)指紋定位算法時間復雜度高的問題，設計了基于無線傳感器網(wǎng)絡的快速指紋匹配定位算法。該算法采用二分法的思想，先將未知節(jié)點鎖定在原定位區(qū)域的四分之一區(qū)域內(nèi)，然后通過計算該區(qū)域內(nèi)的主參考點與未知節(jié)點的歐氏距離，找出歐氏距離最小的主參考點所在區(qū)域，最后將該區(qū)域所有次參考點的加權(quán)質(zhì)心作為最終的位置估計。仿真結(jié)果表明：與最近鄰居定位算法和最近K鄰居定位算法相比，快速指紋匹配定位算法的定位精度略高于二者，定位時間約為二者的1/3。該算法在保證定位精度的前提下，減小了算法的時間復雜度。

無線傳感器網(wǎng)絡； 指紋匹配； 二分法； 時間復雜度； 歐式距離

0 引 言

隨著無線傳感器網(wǎng)絡快速發(fā)展，基于位置的服務(LBS)變得越來越重要。基于無線傳感器網(wǎng)絡(WSN)的定位技術(shù)是其中一項重要的應用,它綜合了無線傳感網(wǎng)絡和無線通信、等相關技術(shù)?？梢酝ㄟ^布置在大樓內(nèi)的參考節(jié)點以及消防員身上攜帶的移動節(jié)點,形成一個多跳的、自組織的、具有自愈能力的網(wǎng)絡系統(tǒng),這些節(jié)點之間合作地完成感知、采集和處理網(wǎng)絡覆蓋區(qū)域中可感知對象的位置信息,并通過相應的定位算法精確計算出對象的具體位置。目前，常用的室內(nèi)指紋定位算法有最近鄰居定位算法(NNSS)、加權(quán)最近K鄰居定位算法(WKNN)以及貝葉斯算法等。最近鄰居定位算法[1]將未知節(jié)點采集到的信號強度信息與參考點處的信號強度信息進行比對，選取匹配度最高的參考點作為未知節(jié)點的估計位置；加權(quán)最近K鄰居定位算法[2-3]與前者類似，不同的是選取K個匹配度高的參考點，取這些參考點的加權(quán)質(zhì)心作為最終結(jié)果；貝葉斯算法[4]則是通過有限的已知參考點處信號強度信息，利用貝葉斯定理估算出整個區(qū)域內(nèi)的信號強度走勢，最終得到未知節(jié)點的位置估計。上述算法普遍存在時間復雜度高的問題，因此，筆者設計了快速指紋匹配定位算法。該算法采用二分法的思想，先將未知節(jié)點鎖定在原定位區(qū)域的四分之一區(qū)域內(nèi)，然后通過計算該區(qū)域內(nèi)的主參考點與未知節(jié)點的歐氏距離，找出歐氏距離最小的主參考點所在區(qū)域，將該區(qū)域所有次參考點的加權(quán)質(zhì)心作為最終的位置估計。

1 錨節(jié)點與參考部署模型

室內(nèi)指紋匹配算法定位環(huán)境選定為方形區(qū)域。具體的參考點選取和錨節(jié)點部署模型如圖1所示。

圖1 錨節(jié)點與參考點部署模型

Fig. 1 Anchor node and reference point deployment model

令{p1,p2,p3,p4,p5,p6,p7,p8,p9}為分別位于方形區(qū)域的四個頂點、四條邊長的中點以及方形區(qū)域的中心，共9個錨節(jié)點構(gòu)成的集合。整個方形定位區(qū)域被均勻劃分為16個小方形區(qū)域，參考點分為16個主參考點與25個次參考點，共計41個參考點，其中有9個次參考點與錨節(jié)點重合。在在線定位階段，假設未知節(jié)點J接收到來自錨節(jié)點信號的信號強度構(gòu)成集合為SJ={s1,s2,s3,s4,s5,s6,s7,s8,s9}，首先要根據(jù)9個信號強度值初步判斷未知節(jié)點J位于定位區(qū)域中哪一部分，共分為以下8種情況：

(1)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s1,s2,s8,s9}時，則未知節(jié)點J在方形區(qū)域的左上角的四分之一區(qū)域內(nèi)；

(2)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s2,s3,s4,s9}時，則未知節(jié)點J在方形區(qū)域的右上角的四分之一區(qū)域內(nèi)；

(3)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s4,s5,s6,s9}時，則未知節(jié)點J在方形區(qū)域的右下角的四分之一區(qū)域內(nèi)；

(4)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s6,s7,s8,s9}時，則未知節(jié)點J在方形區(qū)域的左下角的四分之一區(qū)域內(nèi)；

(5)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s1,s2,s3,s9}或{s2,s4,s8,s9}時，則未知節(jié)點J位于以線段p2p9為中線的方形區(qū)域內(nèi)；

(6)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s3,s4,s5,s9}或{s2,s4,s6,s9}時，則未知節(jié)點J位于以線段p4p9為中線的方形區(qū)域內(nèi)；

(7)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s5,s6,s7,s9}或{s4,s6,s8,s9}時，則未知節(jié)點J位于以線段p6p9為中線的方形區(qū)域內(nèi)；

(8)當SJ中信號強度最大的4個元素構(gòu)成的集合為{s2,s6,s8,s9}或{s1,s7,s8,s9}時，則未知節(jié)點J位于以線段p8p9為中線的方形區(qū)域內(nèi)。

2 快速指紋匹配的定位算法

2.1 指紋匹配定位

指紋匹配定位分為離線數(shù)據(jù)采集與在線定位兩個階段。在離線數(shù)據(jù)采集階段，首先確定參考點的位置，然后在此位置接收來自各個錨節(jié)點的信號，將這些錨節(jié)點的信號強度與位置信息存入數(shù)據(jù)庫，從而建立參考點處的位置指紋數(shù)據(jù)庫。 在在線定位階段，將未知節(jié)點接收到的各個錨節(jié)點的信號強度與數(shù)據(jù)庫中已有數(shù)據(jù)進行比對，通過特定的匹配方式和計算方法，得出未知節(jié)點的估計位置。

假設Si={si,1，si,2，…,si,N} 為參考點i接收到來自N錨節(jié)點無線信號強度所構(gòu)成的集合，SJ={sJ,1,sJ,2,…,sJ,N} 未知節(jié)點J接收到來自N錨節(jié)點無線信號強度所構(gòu)成的集合，則參考點i與未知節(jié)點J的歐氏距離為：

(1)

在在線定位階段，得到與未知節(jié)點J歐氏距離最小的K個參考點后，根據(jù)各個參考點與未知節(jié)點J之間距離的遠近，計算每個參考點的權(quán)值，最后將K個參考點的加權(quán)質(zhì)心作為對未知節(jié)點J的位置估計[5]。未知節(jié)點J的位置估計為

(2)

其中，Ii為第i個參考節(jié)點的坐標，第i個參考點的權(quán)值為

(3)

2.2 算法描述

室內(nèi)快速指紋匹配算法共分為兩階段：離線數(shù)據(jù)采集階段和在線匹配定位階段。

(1)離線數(shù)據(jù)采集

依次在各個參考點位置處采集來自9個錨節(jié)點的信號強度，建立指紋庫RSSDB，其數(shù)據(jù)格式：

(4)

數(shù)據(jù)采集過程中，需要對數(shù)據(jù)進行濾波。因為在實際定位過程中，采集到的數(shù)據(jù)會因高斯白噪聲產(chǎn)生波動，因此要進行濾波，使得采集到的數(shù)據(jù)更加準確。文中采用中值濾波[6]，將采集到的數(shù)組數(shù)據(jù)按從小到大排列，選取中間的一組數(shù)據(jù)作為最終結(jié)果錄入指紋庫。文中算法共采集15組數(shù)據(jù)進行中值濾波。

(2)在線匹配定位

由于算法的計算量越大，實際應用中網(wǎng)絡的響應時間就越長，節(jié)點消耗的能量就越高。因此，結(jié)合二分法查找的思想，保證在正確定位的前提下能夠減少算法的計算量，并提出了一種快速指紋匹配定位算法。具體定位步驟如下：

步驟1 (初步定為)： 未知節(jié)點J接收到來自9錨節(jié)點無線信號強度所構(gòu)成的集合為SJ={sJ,1,sJ,2,…,sJ,9}，找出SJ中最大的4個值所對應的4個錨節(jié)點，將未知節(jié)點J初步定位在以此4個錨節(jié)點為頂點的方形區(qū)域內(nèi)。

步驟2 (縮小范圍)： 用式(1)分別計算未知節(jié)點J與步驟1得到的方形區(qū)域內(nèi)4個主參考點的歐式距離，找出歐式距離最小的主參考點對應的方形區(qū)域。這里參與歐氏距離計算的是4個信號最強的錨節(jié)點。

步驟3 (最終定位)：根據(jù)步驟2 得到的方形區(qū)域頂點處的4個次參考點(K=4), 利用式(2)得到未知節(jié)點J的位置估計。

(3)定位算法復雜度

定位算法的誤差和響應速度是判斷一個定位算法性能好壞的重要指標。定位誤差體現(xiàn)了算法的定位精度，響應速度反映了算法的時間復雜度[7]。就定位誤差而言，由小到大分別為最小的是WKNN，然后是貝葉斯定位算法，最后是NNSS。由上述的算法簡介可以得知，當參考點的個數(shù)為N時，最近鄰居定位算法的時間復雜度為O(N)次乘法運算加上KN次的比較運算；加權(quán)最近鄰居定位算法的時間復雜度為O(N)次乘法運算加上N次的比較運算[8]。由于貝葉斯算法的定位復雜度較高，所以這里不做考慮。

3 仿真結(jié)果與分析

定位區(qū)域為50 m×50 m 的方形區(qū)域，錨節(jié)點和參考點的部署如圖1所示，未知節(jié)點在定位區(qū)域內(nèi)隨機生成。陰影效應引起的接收信號強度誤差為均值為0方差為σ2的高斯隨機變量。

陰影效應引起的接收信號強度誤差的均值為0，方差為0.6條件下，圖2給出文中算法對隨機生成10個未知節(jié)點的位置估計。由圖2可知，可以看出算法的誤差較小。

圖3給出了快速指紋匹配算法、最近鄰居算法以及最近K鄰居算法的平均誤差曲線。仿真過程中，分別對10個未知節(jié)點定位1 000次，取平均值得到平均誤差。由圖3可知，文中算法與最近K鄰居算法的誤差很接近，都在1.5 m左右，文中算法略優(yōu)于最近K鄰居定位算法。而最近鄰居定位算法的誤差較大。最近K鄰居定位算法與文中算法接近的原因主要是在查找未知節(jié)點附近的參考點時，文中算法采取了層層縮小的方法查找，這種查找方法雖然省卻了大量的計算，但是沒有最近K鄰居算法通過直接比較歐氏距離查找的方法準確。因此文中算法利用中值濾波以及參考點篩選兩種濾波方式彌補了查找過程中的誤差。

圖2 10個未知節(jié)點的位置估計

圖3 平均誤差曲線

圖4 定位誤差隨方差的變化情況

從圖4可以看出，各種算法的平均定位誤差均隨接收信號強度誤差的方差增大而增大，文中算法的平均誤差小于其他兩種算法。

通過單次定位仿真，比較三種算法的計算時間，發(fā)現(xiàn)最近K鄰居算法的消耗時間約為3.9 ms，要略高于最近鄰居算法的3.7 ms，快速指紋匹配算法的定位消耗時間則為1.4 ms，約為最近K鄰居定位算法的三分之一。原因在于文中算法在查找未知節(jié)點附近的參考點時，通過層層縮小范圍的方式，省去了大量歐氏距離的計算，因此算法消耗時間最少。

4 結(jié)束語

筆者在原有最小鄰居定位算法的基礎上，提出室內(nèi)指紋定位算法結(jié)合了二分查找的思想，減少了許多不必要的計算量，在略微提高定位精度的情況下，大大降低了定位時間。該算法通過將定位區(qū)域劃分為數(shù)個更小的區(qū)域，然后比較信號強度大小，縮小了定位區(qū)域，簡化了查找過程，最終得出了未知節(jié)點的估計位置。仿真結(jié)果表明，快速指紋匹配算法不僅能夠略微提高定位精度，也大幅度降低了算法復雜度，提高了定位效率。

[1] 楊世杰. 無線傳感器網(wǎng)絡節(jié)點定位算法研究[D].杭州： 浙江工業(yè)大學, 2010.

[2] 葛瀟藝. 基于投影尋蹤模型的WSN入侵檢測算法研究[D]. 烏魯木齊： 新疆大學, 2016.

[3] 關 歡, 趙春宇. 一種改進的快速最小K鄰居定位算法[J]. 電子設計工程, 2015(6): 44-48.

[4] 張夢丹, 盧光躍, 王宏剛, 等. 基于指紋算法的無線室內(nèi)定位技術(shù)[J]. 電信科學, 2016(10): 77-86.

[5] Dong Mei, Yang Zeng. Positioning technology of wireless local area network based on signal strength [J]. Computer Application, 2013, 24(12): 49-52.

[6] Zhu Xiuyan, Feng Yuan. RSSI-based algorithm for indoor localization[C]//2013 Spring International Conferernce on Wireless Communications and Networks, New York: Spring, 2013.

[7] 曾龍基. 室內(nèi)無線定位技術(shù)的研究[D]. 北京： 北京交通大學, 2013.

[8] Kavitha K, Teja C R, Gururaj R. Workload-aware tree construction algorithm for wireless sensor networks [J]. International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, 2012, 4(1): 1-14.

(編輯 晁曉筠 校對 李德根)

Fast fingerprint matching algorithm based on WSN for indoor environment

ZhaoZhixin1,2,LiJiajun1,XieYupeng1

(1.School of Electronics & Information Engineering, Heilongjiang University of Science & Technology, Harbin 150022, China； 2.Department of Electronic Engineering, Tsinghua University, Beijing 100084, China)

This paper introduces a fast fingerprint matching algorithm to address the time complexity of the existing fingerprint localization algorithm. This algorithm operates by locking the unknown node in 1/4 regions in the original location using the dichotomy; then finding out the minimum Euclidean distance of the main reference point by calculating the Euclidean master reference points and unknown node distance within the region; and ultimately identifying the weighted centroid area of all time as the final position of the reference point estimate. The simulation results show that the fast fingerprint matching algorithm provides a slightly higher positioning accuracy than both the nearest neighbor algorithm and nearest neighbor K positioning algorithm and uses about 1/3 the positioning time of the two. The algorithm could ensure the positioning accuracy while greatly reducing the time complexity.

wireless sensor networks; fingerprint matching; dichotomy; time complexity; euclidean distance

2017-05-02

黑龍江省自然科學基金項目(F2015019; F2015017);黑龍江省青年科學基金項目(QC2013C064)

趙志信(1979-)，男，黑龍江省依蘭人，副教授，博士，研究方向：無線網(wǎng)絡資源管理，E-mail：zhaozhixin0830@163.com。

10.3969/j.issn.2095-7262.2017.03.021

TN914.5

2095-7262(2017)03-0307-04

A