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

楊勇

?

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

楊勇

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

對(duì)于上述方程組若分別令：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

[4] 章堅(jiān)武, 張璐, 應(yīng)瑛, 等. 基于ZigBee 的RSSI 測(cè)距研究[J]. 傳感技術(shù)學(xué)報(bào), 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）

作者簡(jiǎn)介：楊 勇（1971-），男，湖北省襄陽職業(yè)技術(shù)學(xué)院，講師，研究方向：網(wǎng)絡(luò)綜合布線和物聯(lián)網(wǎng)，襄陽，441050

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

中圖分類號(hào)：TP311

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