基于修正型果蠅優化算法改進地鐵運行定位系統研究

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

關鍵詞： 果蠅優化算法； 修正因子； DV?Hop算法； 平均定位誤差； 地鐵系統

中圖分類號： 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 引 言

隨著城市規模的發展和壯大，城市地鐵系統網絡越來越復雜，如何實現地鐵系統中列車的實時和精確定位，對保證地鐵系統中列車的行車安全性、控制行車間距和維護費用最低化以及保證乘客安全到達目的地具有重要的現實意義和理論價值[1?2]。隨著無線傳感技術的發展，該技術已經廣泛地應用于科學研究和工程應用領域，包括地鐵系統中運行列車的定位。傳統的運行定位算法主要是DV?Hop算法，但其存在定位誤差大、能耗大和算法復雜程度高等缺點，針對DV?Hop算法存在的定位缺點，運用修正型果蠅優化算法（Modified Fruit Fly Optimization Algorithm，MFOA）改進DV?Hop算法，實現DV?Hop算法的最優化定位。

1 DV?Hop算法

DV?Hop算法是由美國Dragos Niculescu等人提出的一種基于跳數的定位算法[3]，區別于傳統的基于測量的定位算法。傳統的DV?Hop算法中，信標通過錨節點向網絡廣播，信標包含錨節點的位置信息和一個表示跳數的參數。在網絡中此信標通過泛洪的方式進行傳播，其被轉發一次跳數就相應的加1。接收節點只保留具有最小跳數值的信標，丟棄跳數值較大的信標。基于該機制，網絡中所有節點都獲取到了每一個錨節點的最小跳數值。

3 MFOA優化DV?Hop算法的定位

由于測距技術存在誤差的原因，導致無線傳感器網絡必然存在定位誤差，地鐵列車定位誤差問題的實質就是使列車定位誤差最小化。運用MFOA算法優化DV?Hop算法實現節點位置的校正，本質就是將定位最優化問題轉化為定位誤差的最小化問題[8]。

4.2 實驗結果

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

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

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

5 結 論

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

參考文獻

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

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

[3] 劉運杰，金明錄，崔承毅.基于RSSI的無線傳感器網絡修正加權質心定位算法[J].傳感技術學報，2010，23（5）：17?25.

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