基于跳數量化的無線傳感器網絡節點定位算法

張石， 張百海， 王飛帆， 關子霄

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

?

基于跳數量化的無線傳感器網絡節點定位算法

張石， 張百海， 王飛帆， 關子霄

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

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

信息處理技術； 無線傳感器網絡； 定位； 多維定標算法； 跳數量化； 擴展卡爾曼濾波

0 引言

無線傳感器網絡(WSNs)是由大量的具有感知性能，處理和發送環境信息的傳感裝置組成。無線傳感器網絡的發展引起了全世界的廣泛關注，它在戰場監視、環境監測、生物檢測、智能空間、產業診斷等領域得到廣泛的應用[1-4]。

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

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

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

1 系統模型

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

圖1 不同跳數的節點分布Fig.1 Node distribution of different hop-counts

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

圖2 跳環示意圖Fig.2 Illustration of hop rings

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

2 基于鄰域劃分的跳數量化

基于鄰域劃分的跳數量化是通過計算相交區域面積，得到節點到錨節點間的距離，然后將所有整數跳數轉變成實數跳數。

2.1 基于跳數和鄰居節點分布的節點到錨節點間距離計算

2.1.1 計算相交區域面積

(1)

(2)

(3)

(4)

圖4 相交區域面積估算Fig.4 Intersection area estimation

(5)

(6)

(7)

2.1.2 計算節點到錨節點間距離

設di表示節點i到錨節點間距離，3個相交區域真實面積計算方程為

(8)

(9)

(10)

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

(11)

(12)

2.2 跳數量化

(13)

(14)

3 基于跳數量化的MDS定位算法

無線傳感器網絡定位算法中最基本的兩個步驟是測量幾何關系和優化：1)得到節點和錨節點間的幾何關系；2)通過幾何關系，應用各類優化算法計算節點坐標?；谔鴶盗炕腗DS定位算法將轉換后的實數跳數矩陣HR應用到MDS算法中，解決節點定位問題。

3.1 計算相對坐標

多維定標技術的目的就是利用各實體間的相異性來構造多維空間上點的相對坐標圖，構造的多維空間上點與各實體相對應，如果兩個實體越相似，它們對應于空間上點之間的距離就越接近。其接近程度用脅強系數J來衡量：

(15)

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

3.2 計算絕對坐標

(16)

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

Bx=c，

(17)

4 EKF算法

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

1)建立狀態方程

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

(18)

(19)

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

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

(20)

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

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

H0=

(21)

(22)

(23)

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

5 仿真分析

(24)

在Matlab環境下對算法進行仿真，并將MDS-HE算法與DV-Hop算法和MDS算法進行比較。

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

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

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

圖6 節點隨機分布Fig.6 Randomly deployed nodes

圖7 節點相對坐標Fig.7 Relative coordinates of nodes

圖8 節點絕對坐標Fig.8 Absolute coordinates of nodes

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

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

6 節點定位實驗

為了進一步驗證MDS-HE算法的有效性，采用美國Crossbow公司生產的IRIS-XM2110和MIB520網關進行定位實驗。

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

圖11 節點分布Fig.11 Nodes distribution

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

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

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

6.2 不同錨節點數量MDS-HE定位算法實驗

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

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

7 結論

本文針對節點隨機分布的無線傳感器網絡提出了一種MDS-HE定位算法。該算法利用節點1跳鄰居節點分布，將整數跳數轉換成實數跳數，構造實數跳數矩陣，應用MDS算法，并且引入EKF算法對節點坐標準確定位，并分別研究了該算法在仿真環境下和實際應用中的定位效果。

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

實驗結果表明，在錨節點個數相對較多的情況下，MDS-HE算法表現出的定位精度更高。

References)

[1] 朱明強, 侯建軍, 劉穎, 等. 基于自適應比例修正無跡卡爾曼濾波的目標定位估計算法[J]. 兵工學報, 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] 溫龍飛, 崔靈果, 張百海, 等. 不均勻布置傳感器網絡定位優化算法[J]．兵工學報, 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] 夏少波, 鄒建梅, 朱曉麗, 等. 基于跳數區域劃分的DV-Hop改進算法[J].傳感技術學報, 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

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

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

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

TP393.032

A

1000-1093(2017)05-0932-08

10.3969/j.issn.1000-1093.2017.05.013