一種基于遺傳算法的無線傳感器網絡定位新算法

摘 要：針對無線傳感器網絡節點自身定位問題，提出一種基于遺傳算法的新定位算法。該算法假設無線傳感器網絡中有一定比例的位置已知的節點，通過分析未知節點及其無線射程范圍內的已知節點之間的通訊約束和幾何關系，建立以未知節點位置為參數的優化設計數學模型，使用遺傳算法求解此模型得出未知節點的位置，并通過修改遺傳算法參數來提高遺傳算法收斂速度。理論分析和試驗結果表明，本算法具有很強的健壯性，未知節點的失效和新節點的加入不會影響算法的性能，并且算法定位精度高，條件簡單，適合各種規模的無線傳感器網絡的節點定位。

關鍵詞：無線傳感器網絡；節點定位；遺傳算法；算法性能

中圖分類號：TP301．6 文獻標識碼：A

1 引言

無線傳感器網絡(WSN)作為上世紀末新興起的一種技術，在軍事國防、工農業、城市管理、生物醫療、環境監測、搶險救災、防恐反恐、危險區域的遠程控制等許多領域都有重要的科研價值和巨大的應用前景，已引起了世界許多國家軍界、學術界和工業界的高度重視，并成為進入21世紀以來公認的新興前沿熱點研究領域，被認為是將對21世紀產生巨大影響的技術之一。

WSN由大量的無線傳感器節點組成，每個節點都被隨機放置，因此很難得知其具體位置。雖然運用GPS可以精確得到每個節點的位置，但高昂的成本使得GPS不能廣泛應用于WSN。現有的WSN定位算法就是依據少量的位置已知的節點(稱為錨節點)以及可靠的節點通信信息來估計整個網絡中每個節點的位置。如美國路特葛斯大學的Dragos Niculescu等人提出的DV-Distance方去，Lance Doherty等人提出的凸規劃求解方去，以及Tian He等人提出的APIT算法等。這些方法都有自身的特點，但是它們的定位精度都不夠理想，并且需要高密度的錨節點。

針對上述的幾個問題，本文提出了一種利用遺傳算法來實現WSN定位的新方法。圍繞如何清楚的闡述此方法，全文組織如下：第二節詳細介紹基于遺傳算法的節點定位算法，并根據定位優化模型，設置合理的遺傳算法參數；第三節介紹算法仿真，確定算法性能指標參數和影響算法性能的全局參數；第四節根據仿真結果，分析全局參數對算法性能的影響；第五節總結全文。

2 基于遺傳算法的無線傳感器網絡節點定位算法

基于遺傳算法的無線傳感器網絡定位算法是，通過分析未知節點與少量錨節點之間的通信約束，建立以未知節點位置為參數的定位優化模型，使用遺傳算法對優化模型進行求解參數，所得結果即為未知節點的估計未知。

無線傳感器網絡有著節點數目多，分布區域廣，通信約束多等特點，由此建立的定位優化模型是一個多目標多約束的非線性方程；而遺傳算法做為目前比較成熟的一種進化算法，應用條件簡單，搜索能力強并且特別適合多目標，多約束的求解，故非常適合無線傳感器網絡節點定位優化模型的求解。下面分別介紹節點定位問題描述，節點通信約束，定位優化模型以及遺傳定位算法。

“注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”