楊勇

?

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

楊勇

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

關(guān)鍵詞：定位；引力搜索算法；消防；無線網(wǎng)絡(luò)

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

由上文中推導(dǎo)的解方程的結(jié)論，得到公式（3）：

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

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

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

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

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

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

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

通常G0直接取100，而α 直接取20，T 表示的是系統(tǒng)的最大迭代次數(shù)。

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

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

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

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

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

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

2 RSSI 定位系統(tǒng)的架構(gòu)

由前面的定位算法可以得知，若需要對一個節(jié)點進(jìn)行定位，需要至少三個參考節(jié)點的位置才可以確定定位節(jié)點的位置，此外還需要一個網(wǎng)關(guān)，主要負(fù)責(zé)網(wǎng)絡(luò)的協(xié)調(diào)和服務(wù)，參考節(jié)點是已知位置信息的固定節(jié)點，而定位節(jié)點表示需要確定位置的節(jié)點。這里以4個參考節(jié)點為例，描繪出整個RSSI定位的系統(tǒng)架構(gòu)如圖1所示：

圖1　RSSI 定位系統(tǒng)架構(gòu)

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

3 RSSI 定位系統(tǒng)在消防中的應(yīng)用

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

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

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

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

表1　本文算法對參數(shù)的估計

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

表2　定位系統(tǒng)的累加均方根誤差

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

[4] 章堅武, 張璐, 應(yīng)瑛, 等. 基于ZigBee 的RSSI 測距研究[J]. 傳感技術(shù)學(xué)報, 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è)技術(shù)學(xué)院，講師，研究方向：網(wǎng)絡(luò)綜合布線和物聯(lián)網(wǎng)，襄陽，441050

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

中圖分類號：TP311

文獻(xiàn)標(biāo)志碼：A