一種改進(jìn)的基于RSSI最小二乘法和擬牛頓法的WSN節(jié)點(diǎn)定位算法

王堅(jiān)+程星晶+劉繼乾+文永江

摘要：針對受周圍環(huán)境影響的無線傳感器網(wǎng)絡(luò)定位精度等因素引起的測量誤差問題，提出一種改進(jìn)的基于RSSI最小二乘法和擬牛頓法的定位算法。本文首先利用最小二乘法預(yù)估未知節(jié)點(diǎn)的初步位置，再將節(jié)點(diǎn)位置作為擬牛頓算法的初始值進(jìn)行迭代計(jì)算，得到更為精確的節(jié)點(diǎn)位置。仿真結(jié)果證明，該算法能有效地抑制測距傳播誤差，提高傳感節(jié)點(diǎn)的定位精度。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位算法；最小二乘法；擬牛頓法

中圖分類號(hào)：TN929 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）27-0222-04

Abstract： In order to reduce the measurement error by the surrounding environment influence when the signal is transmitting to improve the positioning accuracy， this paper proposes a kind of the localization algorithm that is the least squares method combined with the quasi Newton method. First， using the least square method to estimates the unknown node， and get the initial position of the unknown node， then putting the node position as a quasi Newton algorithm of the initial value to iterative calculation， getting more exact node location. Simulation outcomes display that the algorithm can impactfully decrease the influence of the error in propagation process and improve the accuracy of the sensor node localization， and the algorithm needs no any additional hardware equipment， so it is achieved likely.

Key words： wireless sensor networks； the node localization Algorithm； the least square method； quasi Newton method

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)WSN（wireless sensor network）關(guān)鍵支撐技術(shù)，具有非常重要意義的研究價(jià)值。

基于距離（接收信號(hào)強(qiáng)度指示）的RSSI（Received Signal Strength Indicator）算法，因其勿需新增額外硬件設(shè)備、能耗低和易實(shí)現(xiàn)等優(yōu)勢成為WSN節(jié)點(diǎn)定位技術(shù)的研究熱點(diǎn)[1]。

在現(xiàn)有研究的基礎(chǔ)上[7] [8] [9] [10]，本文提出了一種改進(jìn)的基于RSSI最小二乘法和擬牛頓法的WSN節(jié)點(diǎn)定位算法。首先利用最小二乘法預(yù)估未知節(jié)點(diǎn)的初步位置，再將節(jié)點(diǎn)位置作為擬牛頓算法的初始值進(jìn)行迭代計(jì)算，得到更為精確的節(jié)點(diǎn)位置。仿真結(jié)果證明，該算法能有效地抑制測距傳播誤差，提高了傳感節(jié)點(diǎn)的定位精度。

1 最小二乘法和擬牛頓法

1.1 無線電傳播路徑損耗模型

RSSI定位算法定位精度受無線電傳播路徑損耗的影響很大。綜合考慮到實(shí)際應(yīng)用環(huán)境中多徑、繞射、障礙物等因素影響[2]，對數(shù)-常態(tài)分布模型[4]將更加趨近實(shí)際無線環(huán)境，通過信號(hào)強(qiáng)度的路徑損耗，可以計(jì)算出節(jié)點(diǎn)到所收到信標(biāo)節(jié)點(diǎn)的預(yù)估位置。

可求解出，因存在測距誤差，值盡可能使誤差模型達(dá)到最小值，最后利用最小均方預(yù)估可得未知節(jié)點(diǎn)坐標(biāo)為。

1.3 擬牛頓法

擬牛頓法[3]主要有DFP和BFGS兩種形式，其原理是通過引入牛頓條件在試探點(diǎn)附近的二次逼近從而確定線搜索方向。本改進(jìn)算法選用BFGS算法。

2 一種改進(jìn)的基于RSSI最小二乘法和擬牛頓法的WSN節(jié)點(diǎn)定位算法

2.1 算法流程

Step 1 布置錨節(jié)點(diǎn)。先把n個(gè)錨節(jié)點(diǎn)分別布置到指定的位置，錨節(jié)點(diǎn)的坐標(biāo)為，標(biāo)志位為“1”。

Step 2 建立和更新鄰居表。當(dāng)未知節(jié)點(diǎn)加入到無線傳感器網(wǎng)絡(luò)中，未知節(jié)點(diǎn)使用接收到的錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的信號(hào)強(qiáng)度，建立自己的鄰居表，鄰居表中存儲(chǔ)著一跳范圍內(nèi)的所有節(jié)點(diǎn)的RSSI、距離（利用信號(hào)傳播損耗公式進(jìn)行換算得出）和一跳范圍內(nèi)的錨節(jié)點(diǎn)的坐標(biāo)信息，并把自己的標(biāo)志位，標(biāo)志為“0”。

Step 3 利用最小二乘法計(jì)算未知節(jié)點(diǎn)的位置。當(dāng)未知節(jié)點(diǎn)收到3個(gè)或者3個(gè)以上的錨節(jié)點(diǎn)信號(hào)強(qiáng)度時(shí)，對錨節(jié)點(diǎn)的RSSI從強(qiáng)到弱進(jìn)行排序，篩查出超過閾值信號(hào)強(qiáng)度的錨節(jié)點(diǎn)，運(yùn)用最小二乘法計(jì)算未知節(jié)點(diǎn)位置。

Step 4 更新未知節(jié)點(diǎn)的標(biāo)志位。把能夠利用最小二乘法成功定位的未知節(jié)點(diǎn)的標(biāo)志位更新為“2”。

Step 5 選取BFGS的初始數(shù)據(jù)。把經(jīng)過最小二乘法計(jì)算出來的坐標(biāo)信息作為BFGS的初始值，和初始矩陣，給定允許誤差；

Step 6 核對是否滿足終止準(zhǔn)則條件。計(jì)算，如果，迭代終止，則是問題的近似最優(yōu)解；否則轉(zhuǎn)Step 3。

Step 7 構(gòu)造初始方向。取，且令。

Step 8 進(jìn)行一維搜索。求出和，使得

Step 9 核對是否滿足終止準(zhǔn)則條件。計(jì)算，若，迭代終止，則是問題的近似最優(yōu)解；否則轉(zhuǎn)Step 6。

Step 10 檢查迭代次數(shù)。若，令，轉(zhuǎn)Step 3；否則轉(zhuǎn)Step 7。

Step 11構(gòu)造初始方向。用公式

計(jì)算出，取，令，返回Step 4。

其中：

Step 12 更新能未知節(jié)點(diǎn)的信息。把經(jīng)過BFGS進(jìn)行計(jì)算過的坐標(biāo)信息作為最終計(jì)算結(jié)果，并把消息以廣播的方式告訴周圍的節(jié)點(diǎn)。

Step 13 特殊情況處理情況。當(dāng)未知節(jié)點(diǎn)收到三個(gè)或者三個(gè)以上的錨節(jié)點(diǎn)在同一直線上時(shí)，如圖1所示，黃色圓為錨節(jié)點(diǎn)，淺藍(lán)色為未知節(jié)點(diǎn)的真實(shí)坐標(biāo)。在這種情況下，未知節(jié)點(diǎn)通過最小二乘法是無法計(jì)算出未知節(jié)點(diǎn)的具體位置時(shí)。本文中提出中的最小二乘法和結(jié)合法可以大大的改進(jìn)此特殊情況。

2. 2目標(biāo)函數(shù)

假設(shè)在一個(gè)邊長為的正方形區(qū)域，共有個(gè)傳感器節(jié)點(diǎn)，其中有個(gè)未知節(jié)點(diǎn)，編號(hào)是，個(gè)錨節(jié)點(diǎn)，編號(hào)是。個(gè)節(jié)點(diǎn)的坐標(biāo)向量為，其中。，表示未知節(jié)點(diǎn)的估計(jì)位置與鄰居錨節(jié)點(diǎn)之間的距離；是未知節(jié)點(diǎn)與鄰居錨節(jié)點(diǎn)之間的測量距離，如果信號(hào)傳播的時(shí)候沒有損耗，則應(yīng)該等于。綜合考慮到實(shí)際應(yīng)用環(huán)境中多徑、繞射、障礙物等因素影響，無線電傳播路徑損耗與理論值存在差異，所以我們對進(jìn)行定義：，是未知節(jié)點(diǎn)收到的任意兩錨節(jié)點(diǎn)間的信號(hào)強(qiáng)度，為信號(hào)損耗系數(shù)。更好的反映未知節(jié)點(diǎn)周圍的環(huán)境情況。

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

利用Matlab，對本文提出的改進(jìn)算法與最小二乘法在二維空間內(nèi)無線網(wǎng)絡(luò)節(jié)點(diǎn)定位的三方面性能（定位精度、測距誤差對定位精度的影響和節(jié)點(diǎn)通信半徑對定位精度的影響）進(jìn)行仿真比較。

設(shè)定為成功定位的未知節(jié)點(diǎn)的最終計(jì)算結(jié)果，為成功定位的未知節(jié)點(diǎn)的真實(shí)位置。

3.1 定位精度的仿真對比

設(shè)定節(jié)點(diǎn)隨機(jī)分布在邊長為80米范圍內(nèi)，測距誤差為2米，節(jié)點(diǎn)通信半徑為25米，用兩種算法計(jì)算能定位的節(jié)點(diǎn)的均方根誤差如圖3、圖4和圖5所示：

3.2 測距誤差對定位精度影響的仿真比較

假設(shè)在80米的正方形范圍內(nèi)隨機(jī)分布50個(gè)未知節(jié)點(diǎn)，節(jié)點(diǎn)最大通信范圍為25米，測距誤差分別為0.5、1、1.5、1.75、2、2.5、3、3.5、4米，測量誤差取20次計(jì)算結(jié)果的平均值。

如圖6和圖7所示，兩種算法的定位誤差值和最大誤差值隨著測距誤差的增大而增大，但本文提出的改進(jìn)算法比最小二乘法的平均誤差值和最大誤差值分別減小0.8m和1m。

3.3 通信半徑對定位精度影響的仿真比較

設(shè)定有在80米的正方形內(nèi)隨機(jī)分布80個(gè)未知節(jié)點(diǎn)，通信半徑分別為23、24、25、26、27、28、29、30、31、32、33、34、35、36、37、38、39米，測量誤差取20次計(jì)算結(jié)果的平均值。

如圖8所示，最小二乘法的均方根誤差的平均值約為1.5米，而本文提出的改進(jìn)算法均方根誤差的平均值約為0.8米；如圖9所示，本文提出的改進(jìn)算法的最大誤差比最小二乘法減少1米，定位精度提高了40%。

4 總結(jié)

本文提出了一種改進(jìn)的基于RSSI最小二乘法和擬牛頓法相結(jié)合的定位算法。此改進(jìn)算法首先運(yùn)用最小二乘法預(yù)估未知節(jié)點(diǎn)的初步位置，其次運(yùn)用將節(jié)點(diǎn)位置作為擬牛頓算法的初始值進(jìn)行迭代計(jì)算，得到更為精確的節(jié)點(diǎn)位置。實(shí)驗(yàn)結(jié)果表明，本文提出的算法平均誤差在1 米左右，最大誤差在4米左右，更有效地抑制測距傳播誤差，提高傳感節(jié)點(diǎn)的定位精度，同時(shí)該算法保留了設(shè)備簡單、低能耗和易實(shí)現(xiàn)等優(yōu)點(diǎn)。

參考文獻(xiàn)：

[1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社. 2005.5.

[2] 張宏君，毛永毅.改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)應(yīng)用，2012.32（8）： 2103-2105.

[3] 謝政，李建平，湯澤瀅.非線性最優(yōu)化[M].長沙：國防科技大學(xué)出版社.2003.9.

[4] 張潔穎，孫懋珩，王俠.基于RSSI和LQI的動(dòng)態(tài)距離估計(jì)算法[J].電子測量技術(shù)， 2007.30（2）：142-145.

[5] Jungang Zheng， Chengdong Wu， Hao Chu， et al. Localization algorithm based on RSSI and distance geometry constrain for wireless sensor network. In 2010 International Conference on Electrical and Control Engineering.

[6] Wen-Hsing Kuo， Yun-Shen Chen， Gwei-Tai Jen， et al. An Intelligent Positioning Approach： RSSI-Based Indoor And Outdoor Localization Scheme In ZigBee Networks. Proceedings of the Ninth International Conference on Machine Learning and Cybernetics， Qingdao， 11-14 July 2010.

[7] Yuanqing Qin， Chunjie Zhou， Shuang-Hua Yang， et al. A Distributed Newton Iteration Based Localization Scheme in Underground Tunnels. UKACC International Conference on Control 2012 Cardiff， UK， 3-5 September 2012.

[8] Qingguo Zhang， Jinghua Wang， and Cong Jin. A Distributed Node Localization Algorithm for WSNs Based on the Newton Method. In Wireless Communications， Networking and Mobile Computing （WiCOM）， 2011 7th International Conference.

[9]陶為戈，朱昳華，賈子彥.基于RSSI混合濾波和最小二乘參數(shù)估計(jì)的測距算法[J].傳感技術(shù)學(xué)報(bào)，2012，25（ 12） ： 1748-1753.

[10]王新芳，張冰，馮友兵.基于粒子群優(yōu)化的改進(jìn)加權(quán)質(zhì)心定位算法[J].計(jì)算機(jī)工程，2012（1） ： 90-92.