一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)定位新算法

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；遺傳算法；算法性能

中圖分類號(hào)：TP301．6 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

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

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

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

2 基于遺傳算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法

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

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

“注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”