Research of WSN Node Localization Technology Based on Six-Element Array for Ultrasonic Ranging*

ZHAO Qingqing，HUANG Liang，FU Xianfeng，LI Mingyuan，DUAN Weijun

(School of Electronics and Information，Northwestern Polytechnical University，Xi’an 710072，China)

Research of WSN Node Localization Technology Based on Six-Element Array for Ultrasonic Ranging*

ZHAO Qingqing，HUANG Liang，FU Xianfeng，LI Mingyuan，DUAN Weijun*

(School of Electronics and Information，Northwestern Polytechnical University，Xi’an 710072，China)

For the high accuracy，wide range and stable performance，the ultrasonic positioning technology is becoming an important research point in wireless sensor networks.This paper presents and implements a six-element array ultrasonic sensor and a TDOA ranging experiment。It analysis the ranging error and realizes node localization using geodesic distance based multidimensional scaling positioning algorithm.The MATLAB simulate results show that the geodesic distance MDS algorithm can achieve higher accuracy than Trilateration and Multilateration.

wireless sensor networks;six-element array of ultrasonic ranging;multi-dimensional scaling;time difference of arrival;node self-localization

近些年來，隨著物聯網技術的迅猛發展和應用，無線傳感器網絡WSN(Wireless Sensor Networks)已經成為當今生活中不可或缺的一部分。無線傳感器網絡的眾多應用場合如戰場監控、環境監測、室內定位與跟蹤、智能倉儲和物流管理等，不知道來源位置的傳感器感知數據往往是沒有意義的，因而無線傳感器網絡節點的自身定位技術就顯得非常重要［1］。

傳感器網絡定位技術是一項復雜的技術，涉及的節點數量眾多，覆蓋范圍廣泛。根據網絡中是否存在錨節點可以將算法分為節點自定位算法和基于錨節點輔助的定位算法，無錨節點的節點自定位算法的研究剛剛興起，而且在實際應用中對硬件要求較高，操作復雜度也較大，因此本文只對基于錨節點的定位技術進行研究。

在特定的網絡環境下，基于錨節點的WSN定位算法在定位精度、定位時間及定位可靠性等方面仍存在巨大的挑戰［2］:①網絡環境多樣性。在某些應用中，傳感器節點隨機分布于無人值守的區域中，網絡環境復雜多樣，因而算法能在各種環境中保證定位精度則尤為重要。②節點移動性。動態網絡節點定位不但面臨成本、能耗、環境多樣性的挑戰，還應更多的考慮位置信息的時效性以及由于網絡形狀改變而帶來的拓撲結構變化。③可靠性。由于網絡的開放性，節點常常受到攻擊，例如在常受到攻擊的軍用領域，事件發生的位置信息的可靠性是決定戰爭勝利的關鍵因素之一，因此可靠性尤為重要。

目前的定位方法主要分為基于距離的(Range-Based)和非基于距離的(Range-Free)兩種定位方法。基于距離的定位方法主要有:基于接收信號強度衰減RSSI(Received Signal Strength Indication)定位［3］、基于到達時間TOA(Time of Arrival)定位［4］、基于到達時間差TDOA(Time Difference of Arrival)定位［5］和TOF(Time of Flight)定位［6］等;非基于距離的定位方法則主要有質心算法、MDS-MAP［7］算法、距離向量-跳段DV-HOP(Distance Vector-HOP)算法［8］等。馬震等提出一種基于MDS-MAP分布式傳感器網絡定位算法MDS-MAP(D)［9］。該算法將傳感器網絡劃分為簇，由簇頭節點執行次序多維定標算法得到局部網絡中各節點的絕對坐標。相比于MDS-MAP算法，MDS-MAP(D)可有效降低節點定位的計算復雜度，但在定位精度上的優勢并不明顯。

基于TDOA的定位算法通常利用超聲波與RF信號的傳播速度差異計算信號到達時間差進行測距，然后采用三邊定位算法進行位置估計。基于超聲波的TDOA技術測距精度高，系統具有較高的定位精度，因此獲得廣泛應用。

目前典型的基于超聲波測距的定位系統主要有Cricket［10］、AHLos［11］和SpiderBat［12］等。Cricket定位系統采用基于最小二乘法和卡爾曼濾波的三邊定位算法逐個節點迭代定位;AHLoS系統采用原子式、協作式和迭代式的最大似然估計方法定位。這兩類系統均采用基于超聲波和RF到達時間差的TDOA方法測距，系統定位精度在20～30cm，但由于測距范圍較短(通常在10m以內)，限制了該類系統的應用范圍。SpiderBat則采用超聲波傳播時間測距，超聲波測距節點由四組獨立可控的超聲波收發傳感器和一個數字羅盤組成，采用四組超聲波收發傳感器解決了超聲波波束角有限的問題，增加了測距范圍并提高了測距精度，每個節點配備了一個數字羅盤，這樣收發雙方兩個節點就能分別獲得它們之間的絕對角度。SpiderBat的定位過程與Cricket系統相類似。

本文在自主研發的超聲波六元陣測距平臺上，研究并提出一種基于超聲波TDOA測距的WSN節點定位技術，采用基于測地距離的多維定標(Geodesic Distance Based Multi Dimensional Scaling)［13］定位算法，可有效實現網絡高精度相對定位和絕對定位，從而為WSN提供更好地節點自身定位服務支持。

1 超聲波測距

本文采用基于超聲波的TDOA測距技術，利用超聲波信號和射頻信號獲取TDOA所需的時間差，同時改進超聲波收發電路，設計實現了超聲波六元測距陣列，為無線傳感器網絡定位算法提供高精度測距。

1.1 TDOA測距原理

TDOA測距技術是超聲波測距系統中最常用的技術之一，主要有回波測距和非反射式測距兩種方法［14］。與回波測距法相比，非反射式測距過程中的超聲波發送信號不經反射直接到達接收端，避免了多徑反射以及信號反射時的能量損耗和波形失真。因此，無線傳感器網絡中利用超聲波信號進行測距時，更多的是采用非反射式測距方法。本文同樣采用非反射式的測距方法實現節點間測距。非反射式測距方法要求收、發節點之間保持時間同步，時間同步的精度將直接影響測距精度。測距過程如圖1所示。

圖1 非反射式測距示意圖

發送節點同時發送一個RF信號與超聲波信號，以RF信號作為時間同步信號標記測距的開始時刻，接收節點只需測出RF信號與超聲波信號的到達時間差Δt即可利用式(1)計算出收發節點之間的距離d:

其中vr為RF信號在空氣中的傳播速度，vu為超聲波信號在空氣中的傳播速度。由于vr?vu，所以可將式(1)簡化為:

1.2 超聲波六元陣

由于超聲波發射器存在一定的波束角，當超聲波接收器不在超聲波發射器的波束角范圍內或者偏離超聲波發射器的角度較大時，接收端很難檢測到超聲波信號;同樣的，單個超聲波發射器只能向某個固定方向的一定角度范圍發射超聲波信號，偏離這個方向的接收節點也很難檢測到該發射器發送的超聲波信號。為了保證較高的測距精度和定位精度，同時為了提高測距范圍，本文設計完成了一種超聲波六元陣測距節點，其實物圖如圖2所示。節點分別利用六組不同方向的超聲波收發器實現超聲波測距，每組可實現最大15 m距離的測量。這種基于六元陣的設計可以增大信號的覆蓋面，有利于超聲波信號的接收檢測，從而實現二維全向精確測距。

圖2 超聲波六元陣收發模塊實物圖

1.3 超聲波TDOA測距

TDOA測距模塊以超聲波六元陣收發模塊與JN5148射頻模塊為硬件平臺。超聲波接收模塊采用閾值檢測法對超聲波信號進行接收檢測。為了彌補環境溫度變化對超聲波測距精度的影響，本文利用溫度傳感器采集環境溫度對超聲波的傳播速度進行補償:

其中Vu為補償后的速度，t為環境溫度(℃);對于軟件延時和同步精度差等誤差，則利用參量補償的方式來減小誤差。

本文在教學樓走廊對超聲波節點進行TDOA測距實驗以驗證其測距精度。實驗中，節點的設計最遠測量距離為15 m，測距距離從1 m開始測量并逐漸增加到15 m，每隔1 m進行一組測距實驗，共計15組測試數據。為了減小樣本測量誤差，每組實驗測量50次，取多次測量的樣本平均值進行比較。測距實驗結果如圖3所示，樣本數據平均誤差8 cm，最小誤差近似為0，最大誤差為26.7 cm，相對測距誤差范圍為0%到1.335%，平均相對測距誤差約為0.4%。

圖3 超聲波六元陣測距結果

以測距實驗取得的平均相對測距誤差和最大相對測距誤差作為參考，度量系統的定位精度，在算法仿真實驗中，所有節點的相對測距誤差設為0.4%和1.5%。

2 基于超聲波陣列測距的定位算法

為了實現對WSN進行精確定位，本文提出一種基于超聲波六元陣進行節點間測距，并采用多維定標進行網絡自身定位的WSN定位算法。考慮在一個L×L的二維正方形平面區域中，部署一個包含N個節點的傳感器網絡，其中有M個錨節點(M≥3)，網絡中每個節點都包含一個同構的超聲波六元陣列傳感器節點，可以與其他鄰節點互相進行測距，如圖4所示。

圖4 超聲波六元陣定位系統示意圖

定位算法采用改進的多維定標算法計算網絡坐標，其基本思想是:首先利用節點間的距離信息建立距離矩陣，然后應用MDS算法生成節點相對坐標，當有足夠數量的(二維空間3個、三維空間4個)錨節點時，最后通過線性變換將網絡相對坐標轉化成絕對坐標。定位算法的定位過程主要分成3個階段:

2.1 構建測地距離矩陣

網絡部署完成之后，從全局角度生成網絡拓撲連通圖，并為圖中每條邊賦予一個距離值dij。對于在通信范圍之內的節點對，利用超聲波六元陣進行TDOA測距可以直接測得距離值，從而可構造信息不完全的距離矩陣DN=［dij］N×N。利用節點間的歐式距離dij作為測地距離的替代，對已知距離值令dG(i，j)=d (i，j)，用min{dG(i，j)，dG(i，k)+dG(k，j)}替換dG(i，j)，獲得信息不完全的測地距離矩陣;然后，對于不在彼此通信范圍之內的節點對，則通過最短路徑算法(Dijkstra或Floyd算法)獲得節點對之間的最短路徑測地距離。收集所有節點對之間的距離值構成測地距離矩陣DG，然后就可以進一步計算網絡相對坐標。

2.2 計算相對坐標

基于測地距離矩陣DG，對其應用古典MDS算法，即可構建網絡相對坐標。這個過程如下:

(1)根據測地距離矩陣DG的數據，按照式(4)計算出bij:

(2)根據bij構造出X的中心化內積矩陣B:

(3)記r為空間維度(此處默認為2維)λ1≥λ2≥…≥λr為B的正特征根，λ1，λ2，…，λr對應的單位特征向量為e1，e2，…，er，Γ=(e1，e2，…，er)是單位特征向量為列組成的矩陣，則，X矩陣中每一行對應空間中的一個點，第i行即為Xi。令Λ=diag(λ1，λ2，…，λr)，那么式(5)可變為式((6):

(4)計算內積矩陣B的特征值λ1≥λ2≥…≥λn和r個最大特征值λ1≥λ2≥…≥λr＞0對應的單位特征向量Γ。

(5)根據式(7)計算^X，得到網絡相對坐標圖。

2.3 計算絕對坐標

經過前面兩步得到全網相對坐標，給出了每個節點的相對位置。雖然這些節點之間的相對位置關系是準確的，但是整個網絡的坐標相對于真實位置則可能經過了縮放、旋轉和翻轉。為了獲得網絡絕對坐標，本文利用已知的錨節點構造坐標轉換函數，將相對坐標圖進行線性變換，使經過變換計算得到的坐標與錨節點的真實位置之間的誤差平方總和最小，即更接近真實位置。

設坐標變換函數Q的系數矩陣為α，常數矩陣為β，則有:

在2維空間中已知錨節點條件下，僅需選擇3個錨節點M(b1，b2，b3)，將其相對坐標上式求解齊次線性方程組，可得方程(8)的系數矩陣及常數矩陣β=(β1β2)，從而得到坐標變換函數Q。利用上面獲得的坐標轉換函數，即可將相對坐標矩陣轉換為絕對坐標矩陣。

3 仿真實驗與分析

為了驗證算法的有效性，本文在MATLAB仿真平臺下，在30 m×30 m的二維場景中隨機部署20個節點進行仿真實驗，將本文提出的基于超聲波六元陣列測距的測地距離多維定標定位算法(Geodesic Distance MDS)與Cricket所采用的迭代三邊定位算法(Trilateration)以及AHLoS的迭代多點定位算法(Multilateration)進行仿真實驗對比。由于本文設計的超聲波六元陣最大可實現15 m范圍內的測距，因此在MATLAB下定義節點間的測距范圍為15 m，在測試結果中加入均值為零的高斯白噪聲:

其中δij為真實距離，N(0，σ2)表示均值為0、方差為σ2的獨立正態隨機變量。仿真實驗中以超聲波六元陣TDOA測距實驗得到的平均相對測距誤差作為參考，將平均相對測距誤差σ設為0.4%和1.5%分別進行實驗。

定位算法的性能通過平均定位估計誤差計算:

其中xri，yri表示i的真實坐標，xei，yei表示算法估計坐標。通常該誤差越低定位算法性能越好。

在σ設為0.4%和1.5%時分別進行實驗，按照不同節點規模將3種定位算法進行實驗，計算定位誤差并進行對比，其結果分別如圖5和圖6所示。

圖5 不同節點數量下定位結果誤差對比(σ=0.4%)

圖6 不同節點數量下定位結果誤差對比(σ=1.5%)

仿真實驗表明，3種算法的定位誤差隨著測距誤差的降低和節點密度的增加而有所降低。但與三邊定位(Trilateration)和多點定位(Multilateration)算法相比，Geodesic Distance MDS算法能夠準確構建距離矩陣，獲得精確的相對關系，從而獲得更高的定位精度，定位誤差分別降低50%和30%以上，定位誤差可降低到10 cm以內。在測距誤差較小，節點數量多，網絡平均連通度較高的情況下，算法能夠獲得更為準確的距離矩陣，從而獲得較高的定位精度;而當節點數量較少，網絡連通度不高時，部分距離信息采用最短路徑替代，因而也會存在一定誤差，但相比其他兩種算法其誤差則小得多。

4 結論

本文研究了基于超聲波六元陣列TDOA測距的WSN網絡節點定位技術。超聲波測距系統采用RF信號實現收發節點同步，用溫度補償和軟件處理延遲的方法有效減少誤差，提高測距精度。在15 m范圍內，室內測距的平均誤差為8 cm，最大誤差為26.7 cm。在此基礎上提出一種測地距離的多維定標定位算法實現WSN精確定位。本文以超聲波六元陣測距實驗取得的測距精度作為依據，在MATLAB平臺下對定位算法進行了仿真實驗，結果表明Geodesic Distance MDS算法比迭代三邊定位和迭代多點定位等方法定位精度更高，定位誤差分別降低50%和30%以上，可滿足較大范圍定位需求。

［1］吳凌飛，孟慶虎，梁華為，等.一種基于共線度的無線傳感器網絡定位算法［J］.傳感技術學報，2009，22(5):722-727.

［2］唐弢.基于錨節點的無線傳感器網絡定位技術研究［D］.哈爾濱:哈爾濱工業大學，2013.

［3］方震，趙湛，郭鵬，等.基于RSSI測距分析［J］.傳感技術學報，2007，20(11):2526-2530.

［4］劉世森，湯朝明，吳畏.無線傳感器網絡中的TOA測距方法研究［J］.工礦自動化，2012.192(38):36-39.

［5］趙海，張寬，朱劍，等.基于TDOA的超聲波測距誤差分析與改進［J］.東北大學學報(自然科學版)，2011(6):802-805.

［6］常華偉，王福豹，嚴國強，等.無線傳感器網絡的TOF測距方法研究［J］.現代電子技術，2011，34(1):35-38.

［7］Shang Y，Ruml W，Zhang Y.Localization from Connectivity in Sensor Networks［J］.IEEE Trans on Parallel and Distributed Systems，2004，15(11):961-973.

［8］Liu K Z，Yan X P，Hu F P.A Modified DV-Hop Localization Algorithm for Wireless Sensor Networks［C］//IEEE International Conference on Intelligent Computing and Intelligent Systems.Shanghai，China，2009:511-514.

［9］陳歲生，盧建剛，樓曉春.基于MDS-MAP和非線性濾波的WSN定位算法［J］.浙江大學學報(工學版)，2012，46(5):866-872.

［10］Nissanka Bodhi Priyantha.The Cricket Indoor Location System［D］.Massachusetts Institute of Technology，2005.

［11］Andreas Savvides，Chih-Chieh Han，Mani B Strivastava.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［J］.Proceedings of the 7th Annual International Conference on Mobile Computing and Networking，2001:166-179.

［12］Georg Oberholzer，Philipp Sommer，Roger Wattenhofer.SpiderBat: Augmenting Wireless Sensor Networks with Distance and Angle Information［C］//IPSN’11，April 12-14，2011，Chicago，Illinois.

［13］Shang Y，Ruml W，Zhang Y，et al.Localization from Mere Connectivity in Sensor Networks［C］//Proc of the 4th ACM Int’l Symp on Mobile Ad Hoc Networking and Computing.New York:ACM Press，2003:201-212.

［14］黃潔，王福豹，段渭軍.WSN節點超聲波測距技術研究［J］.電子設計工程，2013，21(6):120-122.

趙晴晴(1989-)，女，山東德州人，碩士生，主要研究方向為無線傳感器網絡，zhaoqingqing0413@163.com;

黃亮(1985-)，男，湖北孝感人，博士生，主要研究方向為傳感器網絡、無線adhoc網絡等，huangliangnumber1 @163.com;

段渭軍(1962-)，男，陜西渭南人，研究員，碩士生導師，主要研究方向為無線傳感器網絡、信號處理，duanwj@nwpu. edu.cn。

基于超聲波六元陣列測距的WSN節點定位技術研究*

趙晴晴，黃亮，傅賢鋒，李明遠，段渭軍*
(西北工業大學電子信息學院，西安710072)

基于超聲波測距的定位技術以其精度高、范圍廣和性能穩定等優點，在無線傳感器網絡中廣泛應用。為了實現較大范圍的高精度定位，利用自主實現的超聲波六元傳感器陣列進行TDOA測距，并進行測距誤差分析，然后采用基于測地距離的多維定標算法(Geodesic Distance MDS)進行無線傳感器網絡節點定位。在MATLAB平臺下與Cricket采用的迭代式三邊定位和AHLoS采用的多點定位算法進行對比仿真實驗，結果表明Geodesic Distance MDS算法在不同網絡規模和測距誤差條件下均能夠獲得更高的定位精度和較小的定位誤差。

無線傳感器網絡;超聲波六元陣測距;多維定標;到達時間差;節點自定位

TP393

A

1004－1699(2014)03－0368－05

2014-01-20修改日期:2014-03-07

C:6150P

10.3969/j.issn.1004－1699.2014.03.018

項目來源:西安市科技計劃項目(CX1255①)