張石， 張百海， 王飛帆， 關(guān)子霄

(北京理工大學(xué) 自動化學(xué)院, 北京 100081)

?

基于跳數(shù)量化的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法

張石， 張百海， 王飛帆， 關(guān)子霄

(北京理工大學(xué) 自動化學(xué)院, 北京 100081)

為提高無線傳感器網(wǎng)絡(luò)節(jié)點定位精度，提出一種基于跳數(shù)量化的定位(MDS-HE)算法。將網(wǎng)絡(luò)中節(jié)點的一跳鄰居節(jié)點集合分割成3個不相交的子集，根據(jù)跳環(huán)分割的相交區(qū)域面積來估算節(jié)點間的距離，從而將整數(shù)跳數(shù)轉(zhuǎn)換成實數(shù)跳數(shù)，轉(zhuǎn)換后節(jié)點間實數(shù)跳數(shù)更能準(zhǔn)確地表示節(jié)點間的距離；將實數(shù)跳數(shù)矩陣應(yīng)用于多維定標(biāo)(MDS)算法中，并且引入擴(kuò)展卡爾曼濾波算法對節(jié)點坐標(biāo)進(jìn)行準(zhǔn)確定位。在節(jié)點隨機(jī)布撒的網(wǎng)絡(luò)中，對提出的算法進(jìn)行了仿真和實驗分析。仿真和實驗結(jié)果表明：在不同節(jié)點數(shù)量情況下，MDS-HE算法的性能優(yōu)于距離向量定位算法和經(jīng)典MDS算法，而且在錨節(jié)點足夠多的條件下，MDS-HE算法定位更加準(zhǔn)確。

信息處理技術(shù)； 無線傳感器網(wǎng)絡(luò)； 定位； 多維定標(biāo)算法； 跳數(shù)量化； 擴(kuò)展卡爾曼濾波

0 引言

無線傳感器網(wǎng)絡(luò)(WSNs)是由大量的具有感知性能，處理和發(fā)送環(huán)境信息的傳感裝置組成。無線傳感器網(wǎng)絡(luò)的發(fā)展引起了全世界的廣泛關(guān)注，它在戰(zhàn)場監(jiān)視、環(huán)境監(jiān)測、生物檢測、智能空間、產(chǎn)業(yè)診斷等領(lǐng)域得到廣泛的應(yīng)用[1-4]。

節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)中一個重要的研究課題[5-7]。節(jié)點定位就是準(zhǔn)確地確定傳感器節(jié)點在網(wǎng)絡(luò)中的坐標(biāo)。根據(jù)是否使用測量節(jié)點間的距離，節(jié)點定位方法分為基于距離定位方法和距離無關(guān)定位方法[8]?；诰嚯x定位方法使用硬件來測量節(jié)點間的距離，并利用距離信息計算節(jié)點的坐標(biāo)。距離無關(guān)定位方法只使用跳數(shù)或者連通性信息來估計距離和定位節(jié)點。雖然后者得到的定位精度不高，但是其成本效益已使它們在大規(guī)模和資源受限的傳感器網(wǎng)絡(luò)中得到廣泛的應(yīng)用。

近年來，國內(nèi)外研究學(xué)者提出了很多針對傳感器網(wǎng)絡(luò)節(jié)點定位的方法。張新平等[9]提出了一種改進(jìn)的距離向量定位(DV-Hop)算法，該算法對鄰居節(jié)點進(jìn)行分類，將節(jié)點的通信范圍劃分不同的區(qū)域，通過幾何分析計算出節(jié)點到錨節(jié)點間距離，提高節(jié)點定位的精度，但增加了網(wǎng)絡(luò)計算量，提升了網(wǎng)絡(luò)的能量損耗。吳光等[10]提出了一種基于歸一化鄰居距離的定位算法，該算法的實現(xiàn)僅依賴于節(jié)點間的連接性和少量的鄰居列表交換，無需增加額外測距硬件，但實際應(yīng)用中需要大量的節(jié)點，增加了節(jié)點定位成本。夏少波等[11]提出一種基于跳數(shù)區(qū)域劃分的DV-Hop改進(jìn)算法，該算法優(yōu)化了參與定位的錨節(jié)點組合，采用質(zhì)心法確定節(jié)點坐標(biāo)，但節(jié)點定位誤差沒有顯著提高。Chen等[12]提出一種單跳距校正節(jié)點定位算法，該算法使用節(jié)點的鄰居節(jié)點個數(shù)估計節(jié)點間距離，但該算法在節(jié)點密度低的環(huán)境下，定位準(zhǔn)確率比較低。Han等[13]提出一種基于節(jié)點分布定位算法，該算法假設(shè)單位區(qū)域內(nèi)節(jié)點的個數(shù)是相同的，節(jié)點通過優(yōu)化目標(biāo)函數(shù)估計鄰居節(jié)點位置，通過鄰居節(jié)點分布估計節(jié)點位置，但該算法需要大量測距硬件，增加定位成本。Sarita等[14]提出一種距離無關(guān)定位算法，該算法利用跳數(shù)估計節(jié)點和錨節(jié)點間的距離，從而進(jìn)行節(jié)點定位，但該算法只有在節(jié)點密度較高情況下定位效果較好。在基于跳數(shù)的定位算法中，大都采用整數(shù)跳數(shù)進(jìn)行節(jié)點定位，由于整數(shù)跳數(shù)不能準(zhǔn)確描述節(jié)點間距離信息，所以導(dǎo)致定位效果較差。

為了提高節(jié)點定位精度，本文提出了一種基于跳數(shù)量化的節(jié)點定位(MDS-HE)算法。算法根據(jù)節(jié)點的一跳鄰居節(jié)點的分布進(jìn)一步量化整數(shù)跳數(shù)，利用跳環(huán)分割相交區(qū)域面積來估計節(jié)點間的距離，將整數(shù)跳數(shù)轉(zhuǎn)換成實數(shù)跳數(shù)。對轉(zhuǎn)換后的實數(shù)跳數(shù)應(yīng)用多維定標(biāo)(MDS)算法[15]，并且引入擴(kuò)展卡爾曼濾波(EKF)算法對節(jié)點坐標(biāo)進(jìn)行準(zhǔn)確定位。通過Matlab軟件進(jìn)行仿真和節(jié)點定位實驗，并與其他定位算法進(jìn)行性能對比，結(jié)果表明，MDS-HE定位算法在定位精度上得到明顯提高。

1 系統(tǒng)模型

本文假設(shè)節(jié)點可以與其通信半徑r范圍內(nèi)的所有節(jié)點通信，不能與其通信范圍之外的節(jié)點通信，所有節(jié)點和錨節(jié)點具有相同的通信范圍，并且隨機(jī)分布在一個相互連通的網(wǎng)絡(luò)中[16]。設(shè)N表示節(jié)點的個數(shù)，M表示錨節(jié)點的個數(shù)，它們隨機(jī)分布在面積為A的任意形狀網(wǎng)絡(luò)中。假設(shè)網(wǎng)絡(luò)區(qū)域的面積遠(yuǎn)遠(yuǎn)大于節(jié)點通信范圍面積，即A≥πr2. 這里不考慮邊界影響[17]，假設(shè)所有的錨節(jié)點間，節(jié)點和錨節(jié)點間的跳數(shù)h是已知的。

圖1 不同跳數(shù)的節(jié)點分布Fig.1 Node distribution of different hop-counts

圖1描繪了一個1 000個節(jié)點隨機(jī)分布在一個100 m×100 m正方形區(qū)域，假設(shè)錨節(jié)點j位于區(qū)域中心，相對于錨節(jié)點j，不同跳數(shù)的節(jié)點用不同符號表示。dij和dkj分別表示節(jié)點i和k到錨節(jié)點j的估計距離。從圖1中看出，節(jié)點i和k有相同的跳數(shù)h=2. 在傳統(tǒng)的基于跳數(shù)的定位算法中，由于節(jié)點i和節(jié)點k到錨節(jié)點j有相同的跳數(shù)，所以dij=dkj. 然而從圖1中可以明顯看出dij

圖2 跳環(huán)示意圖Fig.2 Illustration of hop rings

圖3 理想跳躍模型Fig.3 Perfect hopping scenario

2 基于鄰域劃分的跳數(shù)量化

基于鄰域劃分的跳數(shù)量化是通過計算相交區(qū)域面積，得到節(jié)點到錨節(jié)點間的距離，然后將所有整數(shù)跳數(shù)轉(zhuǎn)變成實數(shù)跳數(shù)。

2.1 基于跳數(shù)和鄰居節(jié)點分布的節(jié)點到錨節(jié)點間距離計算

2.1.1 計算相交區(qū)域面積

(1)

(2)

(3)

(4)

圖4 相交區(qū)域面積估算Fig.4 Intersection area estimation

(5)

(6)

(7)

2.1.2 計算節(jié)點到錨節(jié)點間距離

設(shè)di表示節(jié)點i到錨節(jié)點間距離，3個相交區(qū)域真實面積計算方程為

(8)

(9)

(10)

利用相交區(qū)域的估計面積可以計算得到節(jié)點到錨節(jié)點的距離。設(shè)di=f(Ai)表示上述等式中的非線性函數(shù)，使用正割法[18]可以得到：

(11)

(12)

2.2 跳數(shù)量化

(13)

(14)

3 基于跳數(shù)量化的MDS定位算法

無線傳感器網(wǎng)絡(luò)定位算法中最基本的兩個步驟是測量幾何關(guān)系和優(yōu)化：1)得到節(jié)點和錨節(jié)點間的幾何關(guān)系；2)通過幾何關(guān)系，應(yīng)用各類優(yōu)化算法計算節(jié)點坐標(biāo)?；谔鴶?shù)量化的MDS定位算法將轉(zhuǎn)換后的實數(shù)跳數(shù)矩陣HR應(yīng)用到MDS算法中，解決節(jié)點定位問題。

3.1 計算相對坐標(biāo)

多維定標(biāo)技術(shù)的目的就是利用各實體間的相異性來構(gòu)造多維空間上點的相對坐標(biāo)圖，構(gòu)造的多維空間上點與各實體相對應(yīng)，如果兩個實體越相似，它們對應(yīng)于空間上點之間的距離就越接近。其接近程度用脅強(qiáng)系數(shù)J來衡量：

(15)

式中：f(hij)=ahij+c是跳數(shù)的線性標(biāo)度，a和c是兩個常數(shù)。應(yīng)用MDS算法，可以得到節(jié)點的相對坐標(biāo)。

3.2 計算絕對坐標(biāo)

(16)

通過(17)式可以得到參數(shù)向量x：

Bx=c，

(17)

4 EKF算法

EKF算法的基本思想是將非線性系統(tǒng)線性化，然后進(jìn)行卡爾曼濾波。它將MDS算法和線性變換定位所得的節(jié)點坐標(biāo)作為初始值，利用節(jié)點的所有鄰居節(jié)點信息進(jìn)行迭代計算，逐步減小定位誤差，提高定位精度。EKF算法過程：

1)建立狀態(tài)方程

X(k+1)=PX(k)+V(k)，

(18)

(19)

2)建立量測方程，將節(jié)點與鄰居節(jié)點間距離的量測值作為觀測量，得到量測方程：

z(k)=h(k,X(k))+W(k)，

(20)

式中：h(·)是一個非線性量測函數(shù)；W(k)是節(jié)點在k時刻的量測噪聲。

假設(shè)節(jié)點i的初始位置估計為(xi,yi)，節(jié)點o、p、q是節(jié)點i的鄰居節(jié)點，它們的坐標(biāo)由MDS算法和線性變換得到，分別為(xo,yo)、(xp,yp)和(xq,yq). 迭代的初始值為

H0=

(21)

(22)

(23)

式中：Δ為預(yù)設(shè)的容錯值，本文取值Δ=0.01；Xk為第k次迭代所得的定位結(jié)果；Xk-1為第k-1次迭代所得的定位結(jié)果。

5 仿真分析

(24)

在Matlab環(huán)境下對算法進(jìn)行仿真，并將MDS-HE算法與DV-Hop算法和MDS算法進(jìn)行比較。

節(jié)點個數(shù)N從400個增加到1 000個，定位誤差仿真結(jié)果如圖5所示。隨著節(jié)點數(shù)量的增加，3種算法的定位誤差隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的增加均減小，這是因為對于這3種算法，節(jié)點數(shù)量的增加使得錨節(jié)點到節(jié)點間估計距離和節(jié)點間估計距離更加準(zhǔn)確，因此使得定位誤差減小。在相同參數(shù)情況下，MDS-HE算法的定位精度比DV-Hop算法和MDS算法都要高，這是因為DV-Hop算法和MDS算法僅僅應(yīng)用整數(shù)跳數(shù)估計錨節(jié)點和節(jié)點間的距離和節(jié)點間的距離，相對于同一個錨節(jié)點具有相同跳數(shù)的不同節(jié)點，它們與同一個錨節(jié)點間的估計距離相同，但是它們實際距離是不同的，因此導(dǎo)致這兩種算法定位誤差較大。MDS-HE算法將整數(shù)跳數(shù)轉(zhuǎn)變成實數(shù)跳數(shù)，實數(shù)跳數(shù)矩陣得以優(yōu)化，因此利用實數(shù)跳數(shù)得到的節(jié)點間估計距離更加精確。通過MDS算法，得到的節(jié)點的坐標(biāo)更加精確，并且利用EKF算法對節(jié)點位置進(jìn)行優(yōu)化，提高了節(jié)點的定位精度，減少了定位誤差。

圖5 不同節(jié)點數(shù)量下定位誤差比較Fig.5 Comparison of localization errors in the case of different number of nodes

節(jié)點數(shù)量為500個，錨節(jié)點數(shù)量為5個，整個MDS-HE算法的定位過程如圖6～圖8所示，節(jié)點隨機(jī)分布如圖6所示，通過MDS算法得到節(jié)點相對坐標(biāo)如圖7所示，通過線性變換得到節(jié)點絕對坐標(biāo)如圖8所示。

圖6 節(jié)點隨機(jī)分布Fig.6 Randomly deployed nodes

圖7 節(jié)點相對坐標(biāo)Fig.7 Relative coordinates of nodes

圖8 節(jié)點絕對坐標(biāo)Fig.8 Absolute coordinates of nodes

節(jié)點數(shù)量為500個，錨節(jié)點數(shù)量為5個，最終定位結(jié)果如圖9所示，綠色星形代表節(jié)點真實位置，紅色圓圈代表節(jié)點估計位置，藍(lán)線代表節(jié)點定位誤差。可以看出，MDS-HE算法在部分區(qū)域定位效果不是十分理想，這是因為錨節(jié)點數(shù)與節(jié)點數(shù)比例相對較小，錨節(jié)點分布不均勻。節(jié)點數(shù)量不變，錨節(jié)點數(shù)量增加到10個，MDS-HE算法最終定位效果如圖10所示，節(jié)點的定位效果得到顯著提高。

圖10 10個錨節(jié)點MDS-HE算法定位誤差效果Fig.10 Localization error of MDS-HE algorithm for M=10

6 節(jié)點定位實驗

為了進(jìn)一步驗證MDS-HE算法的有效性，采用美國Crossbow公司生產(chǎn)的IRIS-XM2110和MIB520網(wǎng)關(guān)進(jìn)行定位實驗。

本次實驗在相對空曠的區(qū)域進(jìn)行。針對MDS-HE算法的特性，實驗整體設(shè)計為：將基站視為未知節(jié)點并與筆記本電腦相連，IRIS節(jié)點視為錨節(jié)點，可以人工部署到區(qū)域中；基站收集IRIS節(jié)點的信息，并且將信息傳輸?shù)焦P記本電腦中，再利用MDS-HE算法進(jìn)行計算分析從而實現(xiàn)定位。本次實驗的部署區(qū)域為20 m×20 m的區(qū)域，其中一次的節(jié)點部署如圖11所示。

圖11 節(jié)點分布Fig.11 Nodes distribution

6.1 不同定位算法誤差對比實驗

任意部署5個錨節(jié)點位置，分別對3種算法進(jìn)行10次實驗，定位結(jié)果如表1所示，表中定位誤差為未知節(jié)點實際坐標(biāo)與定位坐標(biāo)間的距離值。從表1中可以看出，MDS-HE算法的定位誤差相對于DV-Hop算法和MDS算法有了一定程度的降低。其中幾次實驗定位效果與DV-Hop算法和MDS算法差別不大，這是因為錨節(jié)點個數(shù)較少。

表1 不同算法定位誤差比較Tab.1 Comparison of localization errors of different algorithms

6.2 不同錨節(jié)點數(shù)量MDS-HE定位算法實驗

不同錨節(jié)點個數(shù)的MDS-HE算法的實驗結(jié)果如表2所示，隨著錨節(jié)點個數(shù)從5個增加到10個，節(jié)點間估計距離更加準(zhǔn)確。應(yīng)用MDS算法，得到節(jié)點坐標(biāo)，并引入EKF算法使得節(jié)點實際坐標(biāo)更加準(zhǔn)確，定位精度得以提高，實驗結(jié)果驗證了仿真的結(jié)論。

表2 不同錨節(jié)點數(shù)量下MDS-HE算法定位誤差Tab.2 Localization errors of MDS-HE algorithm against anchor node number

7 結(jié)論

本文針對節(jié)點隨機(jī)分布的無線傳感器網(wǎng)絡(luò)提出了一種MDS-HE定位算法。該算法利用節(jié)點1跳鄰居節(jié)點分布，將整數(shù)跳數(shù)轉(zhuǎn)換成實數(shù)跳數(shù)，構(gòu)造實數(shù)跳數(shù)矩陣，應(yīng)用MDS算法，并且引入EKF算法對節(jié)點坐標(biāo)準(zhǔn)確定位，并分別研究了該算法在仿真環(huán)境下和實際應(yīng)用中的定位效果。

仿真結(jié)果表明：在節(jié)點個數(shù)相同條件下，MDS-HE算法的定位誤差明顯低于DV-Hop算法和MDS算法；隨著錨節(jié)點個數(shù)的增加，MDS-HE算法的定位精度提高。

實驗結(jié)果表明，在錨節(jié)點個數(shù)相對較多的情況下，MDS-HE算法表現(xiàn)出的定位精度更高。

References)

[1] 朱明強(qiáng), 侯建軍, 劉穎, 等. 基于自適應(yīng)比例修正無跡卡爾曼濾波的目標(biāo)定位估計算法[J]. 兵工學(xué)報, 2013, 34(5): 561-566. ZHU Ming-qiang, HOU Jian-jun, LIU Ying, et al. Target locating estimation algorithm based on adaptive scaled unscented kalman filter [J]. Acta Armamentarii, 2013, 34(5): 561-566. (in Chinese)

[2] Zhang J, Wu C D, Zhang Y Z, et al. Energy-efficient adaptive dynamic sensor scheduling for target monitoring in wireless sensor networks[J]. ETRI Journal, 2011, 33(6): 857-863.

[3] Yan X Y, Zhong Y, Song A, et al. A novel multihop range-free localization based on kernel learning approach for the internet of things[J]. Wireless Personal Communications, 2015, 87(1): 269-292.

[4] Forrest S B, Pang Y L, Zhou W J, et al. Coverage-based lossy node localization for wireless sensor networks[J]. IEEE Sensor Journal, 2016, 16(11): 4648-4656.

[5] 溫龍飛, 崔靈果, 張百海, 等. 不均勻布置傳感器網(wǎng)絡(luò)定位優(yōu)化算法[J]．兵工學(xué)報, 2013, 34(5): 639-643. WEN Long-fei, CUI Ling-guo, ZHANG Bai-hai, et al. Research on location algorithm for nonuniformly deployed sensor networks[J]. Acta Armamentarii, 2013, 34(5): 639-643. (in Chinese)

[6] Chen Z P, Li D Q, Huang Y R, et al.Event-triggered communication for time synchronization in WSNs[J]. Neurocomputing, 2016, 177: 416-426.

[7] Mohamadi H, Salleh S, Razali M N, et al.A new learning automata-based approach for maximizing network lifetime in wireless sensor networks with adjustable sensing ranges[J]. Neurocomputing, 2015, 153: 11-19.

[8] Liu X, Zhang S G, Bu K. A locality-based range-free localization algorithm for anisotropic wireless sensor networks[J]. Telecommunication Systems, 2016, 62(1): 3-13.

[9] Zhang X P, Hu B J. An improved DV-Hop algorithm using hop-count information and geometric constraint[C]∥2011 7th International Conference on Wireless Communications, Networking and Mobile Computing. Guangzhou, China: IEEE, 2011.

[10] Wu G, Wang S, Wang B, et al. A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks[J]. Computer Networks, 2012, 56(16): 3581-3593.

[11] 夏少波, 鄒建梅, 朱曉麗, 等. 基于跳數(shù)區(qū)域劃分的DV-Hop改進(jìn)算法[J].傳感技術(shù)學(xué)報, 2014, 27(7): 964-969. XIA Shao-bo, ZOU Jian-mei, ZHU Xiao-li, et al. Improved DV-Hop algorithm based on regional division of hop count[J]. Chinese Journal of Sensor and Actuators, 2014, 27(7): 964-969. (in Chinese)

[12] Chen G N, Chu Y L, Sun M T. Neighbor-based hop size estimation for dense sensor networks[J]. Journal of Information Science and Engineering, 2015, 31(3): 879-896.

[13] Han S J, Lee S J, Lee S H, et al. Node distribution-based localization for large-scale wireless sensor networks[J]. Wireless Networks, 2010, 16(5): 1389-1406.

[14] Sarita G, Hossain A K M M, Kanchana K. A hop-count based positioning algorithm for wireless ad-hoc networks[J]. Wireless Networks, 2014, 20(6): 1431-1444.

[15] Shang Y, Ruml W. Improved MDS-based localization[C]∥Proceedings of the Conference on Computer Communication. Hong Kong, China: IEEE, 2004: 2640-2651.

[16] Kuo J C, Liao W J.Hop count distribution of multihop paths in wireless networks with arbitrary node density: modeling and its applications[J]. IEEE Transactions on Vehicular Technology, 2007, 56(4): 2321-2331.

[17] Bettstetter C, Eberspacher J.Hop distances in homogeneous ad hoc networks[C]∥57th IEEE Semiannual Vehicular Technology Conference. Jeju, Korea: IEEE, 2003: 2286-2290.

[18] Heath M T. Scientific computing-an introductory survey [M].Boston: McGraw-Hill Press, 2005.

Node Localization Algorithm Based on Hop-countQuantization in Wireless Sensor Networks

ZHANG Shi， ZHANG Bai-hai， WANG Fei-fan， GUAN Zi-xiao

( School of Automation, Beijing Institute of Technology, Beijing 100081, China)

A novel algorithm based on hop-count quantization and extended Kalman filter based on multidimensional scaling (MDS-HE) is proposed to improve the localization accuracy of nodes in wireless sensor networks. The integer hop-count can be transformed into a real number hop-count by partitioning a node’s one-hop neighbor set into three disjoint subsets and estimating the distance between nodes by the areas of the intersection regions of hop ring segmentation. The transformed real number hop-count is a more accurate representation of distance between nodes. The real number hop-count matrix is applied to the multidimensional scaling (MDS) method, and the extended Kalman filter is applied to refine accurately the coordinates of nodes. The localization performance of MDS-HE algorithm is simulated and analyzed in WSNs which is composed of nodes deploying randomly over a region. Simulated and experimental results show that the performance of the MDS-HE algorithm outperforms the DV-Hop method and the classical MDS method in the case of different number of nodes. The MDS-HE algorithm is exceedingly accurate in case of the enough anchor nodes.

information processing technology; wireless sensor network; localization; multidimensional scaling; hop-count quantization; extended Kalman filter

2016-08-16

國家自然科學(xué)基金項目(61573061)

張石(1985—)， 男， 博士研究生。 E-mail: zhangshi1985@126.com

張百海(1966—)， 男， 教授， 博士生導(dǎo)師。 E-mail: smczhang@bit.edu.cn

TP393.032

A

1000-1093(2017)05-0932-08

10.3969/j.issn.1000-1093.2017.05.013