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

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

中圖分類號： TN926?34 文獻標識碼： A 文章編號： 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ò)越來越復雜，如何實現(xiàn)地鐵系統(tǒng)中列車的實時和精確定位，對保證地鐵系統(tǒng)中列車的行車安全性、控制行車間距和維護費用最低化以及保證乘客安全到達目的地具有重要的現(xiàn)實意義和理論價值[1?2]。隨著無線傳感技術(shù)的發(fā)展，該技術(shù)已經(jīng)廣泛地應(yīng)用于科學研究和工程應(yīng)用領(lǐng)域，包括地鐵系統(tǒng)中運行列車的定位。傳統(tǒng)的運行定位算法主要是DV?Hop算法，但其存在定位誤差大、能耗大和算法復雜程度高等缺點，針對DV?Hop算法存在的定位缺點，運用修正型果蠅優(yōu)化算法（Modified Fruit Fly Optimization Algorithm，MFOA）改進DV?Hop算法，實現(xiàn)DV?Hop算法的最優(yōu)化定位。

1 DV?Hop算法

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

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

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

4.2 實驗結(jié)果

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

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

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

5 結(jié) 論

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

參考文獻

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

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

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

[4] 于海斌，曾鵬，王中鋒，等.分布式無線傳感器網(wǎng)絡(luò)通信協(xié)議研究[J].通信學報，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] 馬祖長，孫怡寧.無線傳感器網(wǎng)絡(luò)節(jié)點的定位算法[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] 陳鵬，錢徽，朱森良.基于加權(quán)最小二乘的卡爾曼濾波算法[J].計算機科學，2009，36（11）：230?235.