基于修正型果蠅優(yōu)化算法改進(jìn)地鐵運(yùn)行定位系統(tǒng)研究

摘 要： 為實(shí)現(xiàn)地鐵運(yùn)行列車(chē)的精確和實(shí)時(shí)定位，確保列車(chē)運(yùn)行的安全性，針對(duì)傳統(tǒng)定位算法存在定位誤差大、能耗大和復(fù)雜程度高的缺點(diǎn)，提出一種基于修正模型果蠅優(yōu)化算法改進(jìn)DV?Hop算法的列車(chē)定位算法。通過(guò)錨節(jié)點(diǎn)比例、節(jié)點(diǎn)數(shù)和平均定位誤差之間關(guān)系實(shí)驗(yàn)結(jié)果可知，MFOA算法、FOA算法和DV?Hop算法的平均定位誤差隨著節(jié)點(diǎn)數(shù)和錨節(jié)點(diǎn)比例的增加總體呈現(xiàn)下降的趨勢(shì)，MFOA算法的平均定位誤差小于FOA算法和DV?Hop算法的平均定位誤差，定位精度優(yōu)于FOA算法和DV?Hop算法，從而驗(yàn)證了所提算法的優(yōu)越性和可靠性。

關(guān)鍵詞： 果蠅優(yōu)化算法； 修正因子； DV?Hop算法； 平均定位誤差； 地鐵系統(tǒng)

中圖分類(lèi)號(hào)： TN926?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）15?0176?03

Abstract： In order to ensure the safety of train operation， and realize the precise and real?time train positioning while subway running， a train positioning algorithm using modified fruit fly optimization algorithm to improve the DV?Hop algorithm is proposed to overcome the disadvantages of the traditional localization algorithms， such as high positioning error， high energy consumption and high complexity degree. The experiment for the relation among anchor node proportion， node quantity and average localization error was performed. The experimental results show that， with the increase of node quantity and anchor node proportion， the average localization error of MFOA algorithm， FOA algorithm and DV?Hop algorithm is experiencing the overall downward trend， the average localization error of MFOA algorithm is lower than that of FOA algorithm and DV?Hop algorithm， and the positioning accuracy is better than that of FOA algorithm and DV?Hop algorithm. The reliability and superiority of the algorithm were verified.

Keywords： fruit fly optimization algorithm； correction factor； DV?Hop algorithm； average positioning error； subway system

0 引 言

隨著城市規(guī)模的發(fā)展和壯大，城市地鐵系統(tǒng)網(wǎng)絡(luò)越來(lái)越復(fù)雜，如何實(shí)現(xiàn)地鐵系統(tǒng)中列車(chē)的實(shí)時(shí)和精確定位，對(duì)保證地鐵系統(tǒng)中列車(chē)的行車(chē)安全性、控制行車(chē)間距和維護(hù)費(fèi)用最低化以及保證乘客安全到達(dá)目的地具有重要的現(xiàn)實(shí)意義和理論價(jià)值[1?2]。隨著無(wú)線傳感技術(shù)的發(fā)展，該技術(shù)已經(jīng)廣泛地應(yīng)用于科學(xué)研究和工程應(yīng)用領(lǐng)域，包括地鐵系統(tǒng)中運(yùn)行列車(chē)的定位。傳統(tǒng)的運(yùn)行定位算法主要是DV?Hop算法，但其存在定位誤差大、能耗大和算法復(fù)雜程度高等缺點(diǎn)，針對(duì)DV?Hop算法存在的定位缺點(diǎn)，運(yùn)用修正型果蠅優(yōu)化算法（Modified Fruit Fly Optimization Algorithm，MFOA）改進(jìn)DV?Hop算法，實(shí)現(xiàn)DV?Hop算法的最優(yōu)化定位。

1 DV?Hop算法

DV?Hop算法是由美國(guó)Dragos Niculescu等人提出的一種基于跳數(shù)的定位算法[3]，區(qū)別于傳統(tǒng)的基于測(cè)量的定位算法。傳統(tǒng)的DV?Hop算法中，信標(biāo)通過(guò)錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播，信標(biāo)包含錨節(jié)點(diǎn)的位置信息和一個(gè)表示跳數(shù)的參數(shù)。在網(wǎng)絡(luò)中此信標(biāo)通過(guò)泛洪的方式進(jìn)行傳播，其被轉(zhuǎn)發(fā)一次跳數(shù)就相應(yīng)的加1。接收節(jié)點(diǎn)只保留具有最小跳數(shù)值的信標(biāo)，丟棄跳數(shù)值較大的信標(biāo)?；谠摍C(jī)制，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都獲取到了每一個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值。

3 MFOA優(yōu)化DV?Hop算法的定位

由于測(cè)距技術(shù)存在誤差的原因，導(dǎo)致無(wú)線傳感器網(wǎng)絡(luò)必然存在定位誤差，地鐵列車(chē)定位誤差問(wèn)題的實(shí)質(zhì)就是使列車(chē)定位誤差最小化。運(yùn)用MFOA算法優(yōu)化DV?Hop算法實(shí)現(xiàn)節(jié)點(diǎn)位置的校正，本質(zhì)就是將定位最優(yōu)化問(wèn)題轉(zhuǎn)化為定位誤差的最小化問(wèn)題[8]。

4.2 實(shí)驗(yàn)結(jié)果

依據(jù)MFOA優(yōu)化DV?Hop算法的適應(yīng)度函數(shù)，仿真實(shí)驗(yàn)時(shí)，節(jié)點(diǎn)的通信半徑等于10 m，仿真區(qū)域大小為10 m×10 m的正方形平面區(qū)域，換句話(huà)說(shuō)，未知節(jié)點(diǎn)在10 m×10 m的正方形平面區(qū)域內(nèi)。果蠅群體大小為20，最大迭代次數(shù)為100，仿真結(jié)果如圖1～圖3所示。

由圖2平均定位誤差和錨節(jié)點(diǎn)比例關(guān)系圖可知，MFOA算法、FOA算法和DV?Hop算法的平均定位誤差隨著錨節(jié)點(diǎn)比例的增加均呈現(xiàn)下降趨勢(shì)，但MFOA算法的平均定位誤差明顯小于FOA算法和DV?Hop算法的平均定位誤差。

由圖3平均定位誤差和節(jié)點(diǎn)數(shù)關(guān)系圖可知，MFOA算法、FOA算法和DV?Hop算法的平均定位誤差隨著節(jié)點(diǎn)數(shù)的增加，總體呈現(xiàn)下降的趨勢(shì)，且MFOA算法的平均定位誤差小于FOA算法和DV?Hop算法的平均定位誤差，定位精度優(yōu)于FOA算法和DV?Hop算法，從而驗(yàn)證了本文算法的優(yōu)越性和可靠性。

5 結(jié) 論

針對(duì)傳統(tǒng)的地鐵列車(chē)運(yùn)行定位算法存在定位誤差大、能耗大和算法復(fù)雜程度高等缺點(diǎn)，運(yùn)用修正型果蠅優(yōu)化算法改進(jìn)DV?Hop算法，實(shí)現(xiàn)DV?Hop算法的最優(yōu)化定位。實(shí)驗(yàn)結(jié)果表明，隨著錨節(jié)點(diǎn)比例和節(jié)點(diǎn)數(shù)的增加，MFOA算法的平均定位誤差和定位覆蓋率均優(yōu)于FOA算法和DV?Hop算法，具有定位精度高、收斂速度快的優(yōu)點(diǎn)，本文方法可以推廣至相關(guān)工程研究和應(yīng)用中。

參考文獻(xiàn)

[1] 汪煬，黃劉生，肖明軍，等.一種基于RSSI校驗(yàn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，30（1）：59?62.

[2] 王建剛，王福豹，段渭軍.加權(quán)最小二乘估計(jì)在無(wú)線傳感器網(wǎng)絡(luò)定位中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2006，36（9）：41?46.

[3] 劉運(yùn)杰，金明錄，崔承毅.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)修正加權(quán)質(zhì)心定位算法[J].傳感技術(shù)學(xué)報(bào)，2010，23（5）：17?25.

[4] 于海斌，曾鵬，王中鋒，等.分布式無(wú)線傳感器網(wǎng)絡(luò)通信協(xié)議研究[J].通信學(xué)報(bào)，2004，25（10）：102?110.

[5] PAN W T. A new fruit fly optimization algorithm： taking the financial distress model as an example [J]. Knowledge?based systems， 2012， 26： 69?74.

[6] 馬祖長(zhǎng)，孫怡寧.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法[J].計(jì)算機(jī)工程，2004，30（7）：13?17.

[7] WONG K F S， TSANG I W， CHEUNG V， et al. Position estimation for wireless sensor networks [C]// Proceedings of 2005 IEEE Global Telecommunications Conference. St. Louis： IEEE， 2005： 2772?2776.

[8] 陳鵬，錢(qián)徽，朱森良.基于加權(quán)最小二乘的卡爾曼濾波算法[J].計(jì)算機(jī)科學(xué)，2009，36（11）：230?235.