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

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

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

1 引言

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

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

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

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

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

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

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