楊勇

?

基于引力搜索算法的RSSI 模型優(yōu)化與在消防定位中的應用

楊勇

摘 要：RSSI 定位方法成為近年來研究的熱點問題。用極大似然估計法得到RSSI 測距模型的修正參數，再使用最小二乘法求取所需節(jié)點的估計坐標，再通過引力搜索算法對最小二乘法的初步坐標估計結果和參數進行優(yōu)化和修正，其算法不僅可以提高定位節(jié)點坐標的精度，還可以實現對于定位模型參數的動態(tài)跟蹤變化。將設計的RSSI定位系統的應用程序移植消防定位系統中，通過接收網關節(jié)點從串口傳遞進來的參考節(jié)點的位置信息和參考節(jié)點接收到定位節(jié)點廣播的RSSI 值，通過提出的算法求解出最終的定位節(jié)點的位置。最后，在消防定位的實驗結果中驗證定位模型的參數優(yōu)化結果，設計的RSSI定位系統總體誤差較小，得到的參數反映了環(huán)境的變化，取得了預期的效果。

關鍵詞：定位；引力搜索算法；消防；無線網絡

0 引言

隨著社會的發(fā)展，確定位置信息顯得越來越重要，一些產品諸如手機、平板電腦、汽車等，早已具備了定位的功能。定位技術在消防中同樣可以得到較為廣泛的應用，如消防員位置監(jiān)控、監(jiān)控消防的特殊地點?；赯igBee 無線網絡的接收的信號強度指示（Received Signal Strength Indication，RSSI）測距法由于其低成本，低功耗，無額外硬件，將其應用于消防定位是一種較為良好的選擇。對于定位問題來說，提出一種定位精度高，實時性強，受環(huán)境影響小的算法，無疑具有重要的意義。

1 引力搜索算法對RSSI 模型結果的優(yōu)化

使用無線傳感器網絡來確定位置信息，都是基于接收信號強度RSSI 值與距離之間的數學模型，求出各節(jié)點之間的相對位置，最后使用設定的定位算法求得所需節(jié)點的位置。RSSI 定位的方式雖然實現較為簡單，但由于無線信號的強度往往受到障礙物吸收、反射的影響，而且容易還會發(fā)生多徑效應等，因此，在實際的操作過程中傳統的RSSI 定位精度通常不高。本文提出將引力搜索算法（gravitational search algorithm，GSA）使用到RSSI 定位方法中。主要實現的過程是：

（1）利用極大似然估計法得到RSSI 測距模型的修正參數；

（2）使用最小二乘法（least square method，LSM）初步估計所求的定位節(jié)點的坐標；

（3）使用GSA 對使用LSM 計算出來的定位節(jié)點坐標和參數進行優(yōu)化。此算法能夠提高所求取的定位節(jié)點坐標的精度，而且實現對定位模型的參數的動態(tài)跟蹤，提高系統對環(huán)境的適應性。

在對RSSI 定位進行研究中，一般使用,定位模型，如公式（1）：

其中，A表示距離1m 處的RSSI值， n為路徑的衰減因子，取值通常為1~4之間，ν服從（0，δ2）的高斯分布，用來表示環(huán)境對數學模型的影響程度。為了更加此處令a=10n，b=A，這樣更加明確的體現數學模型中的線性關系，可以得到公式（2）：

RSSI 定位的方法是基于測距的算法，通常使用三邊測距法，其基本原理是當參考節(jié)點與定位節(jié)點的距離已知時，將定位節(jié)點看成是以參考節(jié)點為圓心，半徑為該距離的圓上的一點，定位節(jié)點就是至少3個參考節(jié)點的圓相交的交點，由此推斷出定位節(jié)點的位置。

通過前文的推導，已經將RSSI 定位模型的參數求出，將求解出來的參數代入式（2），就可以通過讀取組網后的第i 個節(jié)點接收到的RSSI 值求得定位節(jié)點和參考節(jié)點的相對距離di ，設現已知n 個參考節(jié)點與定位節(jié)點的相對距離，x i， yi分別代表第i 個節(jié)點參考節(jié)點的橫坐標和縱坐標，x 和y 為需要的定位節(jié)點估計坐標。則有：

為了應用最小二乘法，需要將上述的二次方程組轉換為一次方程組，可以通過將前(n-1)個方程都減去第n個方程的方法實現，得出：

對于上述方程組若分別令：

就可以將方程組寫為最小二乘法的基本方程的形式：

由上文中推導的解方程的結論，得到公式（3）：

這樣就可以將定位節(jié)點的坐標給估計出來。然而，單純的使用最小二乘法得到的估計坐標在環(huán)境影響不大或者環(huán)境條件改變較小時可以得到較好的結果。但實際應用中，環(huán)境是不斷變化的，所以，使用相應的人工智能算法對求取出來的估計結果進行優(yōu)化，提升整個系統模型對環(huán)境的適應能力，還是很有必要的。

若將上述最小二乘法得到的結果用來縮小人工智能算法的搜索范圍，可以為進一步優(yōu)化坐標提供條件，減小因為智能算法由于搜索范圍過大所帶來的誤差，由于引力搜索算法對局部和全局的搜索性能好，速度較快，這里使用引力搜索算法對剛才估算出來的定位結果進行優(yōu)化。

引力搜索算法是由伊朗的克曼大學教授Rashedi 等人提出來的優(yōu)化算法，主要思想是每個粒子都會由于萬有引力相互吸引，引力的大小與粒子的質量成正比，與它們之間的距離成反比。本文使用改進的引力搜索算法優(yōu)化前文中所得到的估計坐標，此處設最終需要的定位節(jié)點坐標為(x，y)，通過公式（3）計算出來的估計值為(x'，y')，其中代表一個給定的正數，此處將其稱為調節(jié)因子，主要用來調節(jié)算法的優(yōu)化范圍。此處可以看出，若調節(jié)相應的調節(jié)因子，可以將x 和y 的取值擴展所有可以取值的區(qū)域，這樣可以避免使用最小二乘法進行初步估計，單純的使用引力搜索算法，但是這樣做無疑大大增加了計算機的負擔，使求解最終結果的效率大為下降。而先使用最小二乘法，再對估計結果進行優(yōu)化盡可以大地縮小求解的優(yōu)化范圍，求解的效率與精確度都得到了較大幅度的改善。

對于一般的 RSSI定位模型，參數的取值范圍為a∈(-40，-10)，b∈(-50，-30)。由于讀取出來的RSSI 值在程序中通常是絕對值，故利用RSSI 絕對值得出的a、b一般均為負數。

在上述x 、y 、a 、b 的取值范圍的條件下隨機產生N個粒子，其中第i個的位置為分別對應于所需要的x 、y 、a 、b 。對于人工智能算法來說，通常選取的粒子數越多所得到的結果就越精確，當然運算量也就越大。選用作為該粒子在第d 維上的位置大小。在t 時刻（也就是第t次的迭代），第d 維上第i 個粒子所受到的總的作用力的大小可看成是其他適應度最大的粒子對其作用力的和，如公式（4）：

上式中kbest表示選出的適應度最大的粒子的集合。randj是[0，1]間的隨機數，表示的是第j個粒子對第i個粒子在t 時刻的作用力，通過公式（4）就可以求得公式（5）：

式中，Mpi（t）、Maj（t）分別代表第i個粒子和第 j個粒子于 t 時刻的慣性質量，R ij（t）表示在此時刻的兩個粒子之間歐氏距離，是一個很小的常量，通常在程序中直接選定一個較小的數，G（t）所表示的是當前時刻的引力常數。使用公（5）得到公式（6）：

通常G0直接取100，而α 直接取20，T 表示的是系統的最大迭代次數。

確定了作用力之后，再依據牛頓第二定律來求解此時的加速度如公式（7）：

然后求取下一時刻的速度和位置信息如公式（8）、（9）：

另外，慣性質量也需要實時更新，它的大小與適應度函數相關，所表達的意思即慣性質量越大，就會產生越大的吸引力，也就越接近于所需要的最優(yōu)值。其計算方法如公式（10）、（11）、（12）：

上式的fitnessi （t）代表的是當前時刻的適應度大小。如果需要求最小值，就可以得到公式（13）、（14）：

由于RSSI 定位的模型已知，就可以通過公式（15）作為它的適應度函數，即公式（15）：

通過上述的 GSA方法訓練出來的最終結果Xm（x，y，a，b），不僅得到了較為精確的定位結果，還實時得出RSSI定位模型中的參數a、b 。對于數學模型來說，環(huán)境所引起的變化正是通過參數a、b 得以表現，使用此方法實現對定位節(jié)點坐標以及模型參數動態(tài)的跟蹤變化。

2 RSSI 定位系統的架構

由前面的定位算法可以得知，若需要對一個節(jié)點進行定位，需要至少三個參考節(jié)點的位置才可以確定定位節(jié)點的位置，此外還需要一個網關，主要負責網絡的協調和服務，參考節(jié)點是已知位置信息的固定節(jié)點，而定位節(jié)點表示需要確定位置的節(jié)點。這里以4個參考節(jié)點為例，描繪出整個RSSI定位的系統架構如圖1所示：

圖1　RSSI 定位系統架構

將ZigBee 協議找下載進入CC2430 開發(fā)板，并且編寫完運行于開發(fā)板上的應用程序，使得它們相互之間可以通信并可以取出相應的RSSI 值，然后將相關的位置信息和RSSI值通過CC2430 網關傳遞給mini2440 開發(fā)板，在開發(fā)板中進行相應的處理和運算并顯示出所需要的節(jié)點信息。

3 RSSI 定位系統在消防中的應用

RSSI 定位系統在消防中可以應用的地方較為廣泛，可以定位消防員，監(jiān)控消防的特殊地點燈，本次定位實驗的節(jié)點如圖2所示：

圖2　參考節(jié)點的位置分布

在某消防的大廳和過道上進行，實驗步驟主要是：在大廳和過道中放置參考節(jié)點，實驗中的各個參考節(jié)點的主要位置如圖2所示；打開網關、參考節(jié)點與定位節(jié)點，是其組成ZigBee的無線網絡；移動定位節(jié)點，記錄定位節(jié)點的位置信息；運行定位系統軟件，記錄該定位節(jié)點的3 次結果；求出本次定位的累加均方根誤差。

上圖節(jié)點放置于消防人流量較大的大廳和過道，可以看成是環(huán)境改變較大的情況，本文的定位系統較為適用。在9點，12 點和16 點分別運行該系統，按照上述的實驗步驟進行定位定位實驗，求出了對模型的參數估計，如表1所示：

表1　本文算法對參數的估計

其累加均方根誤差情況如表2 所示：

表2　定位系統的累加均方根誤差

實驗過程中定位的系統的運行較為穩(wěn)定，能夠實時顯示出定位模型的參數和最終定位結果，說明系統能夠成功地運行。從表1 中可以看出，RSSI 定位的模型參數是變化的，說明設計的定位系統能夠實現參數的動態(tài)跟蹤變化，表2 的數據顯示了各時刻的累加均方根誤差，總體處于較小的水平，基本達到了預期的效果，說明在消防的這種環(huán)境變化的情況下，該定位系統也能達到較為良好的效果。

4 總結

本文提出將引力搜索算法應用于RSSI 定位模型之中，提高了定位的精度，增強了系統對環(huán)境條件的適應能力，設計了相應的應用程序，取得了較為良好的效果。由于RSSI定位系統使用了ZigBee技術，而在物聯網的應用中可以對本文的定位系統進行進一步的開發(fā)與設計，使得功能更加完善。

參考文獻

[1] 謝曉佳,程麗君,王勇.基于ZigBee 網絡平臺的井下人員跟蹤定位系統[J].煤炭學報,2007, 32(8): 884-888.

[2] 倪瑛,戴娟.ZigBee 定位技術的研究[J].南京工業(yè)職業(yè)技術學院學報,2013,13(2): 43-46.

[3] 魏立線,姚武軍,鐘衛(wèi)東,等.基于LQI 的WSN 自適應差錯控制方案[J].計算機工程,2011, 37(21): 64-67.

[4] 章堅武, 張璐, 應瑛, 等. 基于ZigBee 的RSSI 測距研究[J]. 傳感技術學報, 2009, 22(2): 285-288.

[5] Sahu P K, Wu E H-K，Sahoo J. DuRT: Dual RSSI Trend Based Localization forWireless Sensor Networks [J]. IEEE SENSORS JOURNAL, 2013, 13(8): 3115-3123.

[6] Kuo R J, Shieh M C, Zhang J W, et al. The application of an artificial immune system-based back-propagation neural network with feature selection to an RFID positioning system[J]. Robotics and Computer-Integrated Manufacturing,2013, 29:431-438.

[7] Marti J V, Sales J, Marin R, et al. Multi-Sensor Localization and Navigation for Remote Manipulation in Smoky Areas[J]. Int J Adv Robotic Sy, 2013, 10(211): 1-8.

[8] Blumrosen G, Hod B, Anker T, et al. Enhanced calibration technique for RSSI-based ranging in body area networks[J]. Ad Hoc Networks, 2013, 11: 555-569

Application of RSSI Model Optimization Based on Gravitational Search Algorithm in Fire Location

Yang Yong
(Xiangyang Vocational and Technical College, Xiangyang 441050, China)

Abstract:The RSSI positioning method has been a research hot topic in recent years. In this paper, the corrected parameter of RSSI distance measurement model is calculated by using the maximum likelihood method, and the coordinates of the nodes required are calculated by using the least square method, then the coordinates and parameters estimated by using the least square method preliminary are optimized and amended by using the gravitation search algorithm, which can not only improve the precision of the node coordinates, but also track the dynamic variation of the position model parameters. The application program of RSSI positioning system is embedded into the fire protection positioning system, and the position of the reference node coming from the serial port is received by the network node, The RSSI value of the position node in received by the reference node, and the final position of positioning node is calculated by using the presented algorithm. Finally, the parameter optimization results of the positioning model are verified according to the results of the fire protection positioning. The overall error of the RSSI positioning system is less, and the parameter can reflect that the change of the environment and the result is good as expected.

Key words:Positioning; Gravitation Search Algorithm; Fire Protection; Wireless Network

收稿日期：（2015.09.21）

作者簡介：楊 勇（1971-），男，湖北省襄陽職業(yè)技術學院，講師，研究方向：網絡綜合布線和物聯網，襄陽，441050

文章編號：1007-757X(2016)01-0066-04

中圖分類號：TP311

文獻標志碼：A