基于RSSI和遺傳算法的無(wú)線(xiàn)定位方法及其實(shí)現(xiàn)

孫建領(lǐng)+張宏欽

摘 要：隨著無(wú)線(xiàn)電技術(shù)的發(fā)展，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)在目標(biāo)跟蹤、環(huán)境監(jiān)測(cè)、空間探索等領(lǐng)域得到廣泛應(yīng)用，節(jié)點(diǎn)定位技術(shù)在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中具有重要地位。文章提出了基于遺傳算法的無(wú)線(xiàn)定位算法，解決了基于RSSI信號(hào)強(qiáng)度的無(wú)線(xiàn)定位方法定位精度較低的問(wèn)題。該算法采用考慮參考節(jié)點(diǎn)RSSI信號(hào)波動(dòng)誤差的質(zhì)心算法進(jìn)行種群初始化，使用基于記憶搜索方向的交叉機(jī)制和自適應(yīng)調(diào)整搜索半徑的策略，為下一代種群的搜索方向及搜索半徑提供有效的指導(dǎo)信息。實(shí)驗(yàn)結(jié)果表明，該算法的定位精度明顯高于典型及改進(jìn)的極大似然估計(jì)定位算法，有效地提高了定位精度。

關(guān)鍵詞：無(wú)線(xiàn)定位；遺傳算法；接收信號(hào)強(qiáng)度

1 無(wú)線(xiàn)傳感器研究背景

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量的微型傳感器節(jié)點(diǎn)組成的數(shù)據(jù)網(wǎng)絡(luò)系統(tǒng)，主要用于在網(wǎng)絡(luò)覆蓋范圍內(nèi)進(jìn)行信息的采集、分析和處理，并能夠最終將關(guān)鍵數(shù)據(jù)返回給控制中心。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的定位技術(shù)就是先通過(guò)獲取未知坐標(biāo)節(jié)點(diǎn)與已知坐標(biāo)的參考節(jié)點(diǎn)之間的距離等信息，再通過(guò)某種定位算法來(lái)計(jì)算出未知節(jié)點(diǎn)坐標(biāo)的技術(shù)[1]。它可以廣泛應(yīng)用于災(zāi)難救援、智能城市、交通管理、環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生、國(guó)防軍事等諸多領(lǐng)域。

WSN的定位方法主要有基于信號(hào)到達(dá)時(shí)間（Time of Arrival， TOA）、到達(dá)時(shí)間差（Time Difference of Arrival， TDOA）和基于接收信號(hào)強(qiáng)度指示（Received Signal Strength Indicator， RSSI）的定位方法。TOA和TDOA 測(cè)距技術(shù)利用信號(hào)的傳播速度和傳輸時(shí)間作為輸入來(lái)計(jì)算距離，其定位準(zhǔn)確度高，要求高精度的時(shí)鐘實(shí)現(xiàn)同步，成本較高；RSSI測(cè)距技術(shù)利用理論或經(jīng)驗(yàn)?zāi)Ｐ?，將信?hào)傳播損耗映射為傳播距離，從而實(shí)現(xiàn)定位，具有低功耗、低成本等優(yōu)點(diǎn)[2]。RSSI信號(hào)易受反射、多徑、障礙物等因素的影響，易于產(chǎn)生信號(hào)強(qiáng)度的波動(dòng)[3]，在非視距環(huán)境下會(huì)出現(xiàn)較大的定位誤差[4-5]，因此該定位方法目前多應(yīng)用在區(qū)域級(jí)別的定位領(lǐng)域，定位精度相對(duì)較低。為了提高定位精度，文獻(xiàn)[6]提出了基于RSSI信號(hào)強(qiáng)度的質(zhì)心定位方法，該方法根據(jù)參考節(jié)點(diǎn)對(duì)盲節(jié)點(diǎn)的不同影響力來(lái)確定加權(quán)因子，存在將非線(xiàn)性問(wèn)題轉(zhuǎn)換為線(xiàn)性問(wèn)題后定位的值域未能完整地覆蓋原始定位問(wèn)題模型值域的問(wèn)題。文獻(xiàn)[7]提出了改進(jìn)的極大似然估計(jì)定位方法，該方法使用最速下降算法對(duì)極大似然估計(jì)算法所得的節(jié)點(diǎn)定位值進(jìn)行優(yōu)化，存在將非線(xiàn)性模型轉(zhuǎn)換為線(xiàn)性模型的誤差問(wèn)題。

遺傳算法是借鑒生物界“適者生存”原則的優(yōu)化算法[8]，其目標(biāo)函數(shù)的定義域可以為任意集合且不會(huì)受到連續(xù)可微的約束，這種特點(diǎn)使得遺傳算法非常適合求解定位問(wèn)題，避免了典型定位算法中值域轉(zhuǎn)換及從非線(xiàn)性模型轉(zhuǎn)換為線(xiàn)性模型時(shí)產(chǎn)生的定位誤差[9]。

基于RSSI和遺傳算法的無(wú)線(xiàn)定位算法采用考慮參考節(jié)點(diǎn)RSSI信號(hào)波動(dòng)誤差的質(zhì)心算法進(jìn)行種群初始化，具有記憶搜索方向和自適應(yīng)調(diào)整搜索半徑的特點(diǎn)，能為下一代種群的搜索方向及搜索半徑提供有效的指導(dǎo)信息，可以有效地提高無(wú)線(xiàn)定位的精度。將WSN中需要定位的節(jié)點(diǎn)稱(chēng)為盲節(jié)點(diǎn)，而將已知坐標(biāo)位置并能協(xié)助盲節(jié)點(diǎn)進(jìn)行定位的節(jié)點(diǎn)稱(chēng)為參考節(jié)點(diǎn)。

2 典型的定位算法存在的問(wèn)題

典型的定位應(yīng)用通常使用改進(jìn)的質(zhì)心法或極大似然估計(jì)法來(lái)確定坐標(biāo)位置，通過(guò)對(duì)這兩種定位算法進(jìn)行分析后發(fā)現(xiàn)以下問(wèn)題。

使用典型或改進(jìn)的質(zhì)心算法進(jìn)行定位坐標(biāo)計(jì)算時(shí)，最終計(jì)算的定位坐標(biāo)位置必然限定在由幾個(gè)頂點(diǎn)所圍成的凸多邊形內(nèi)部，這是由質(zhì)心算法的幾何性質(zhì)所決定的。當(dāng)僅有3個(gè)頂點(diǎn)時(shí)，凸多邊形即為三角形區(qū)域，其中一種情況如圖1所示。

雖然根據(jù)算法的不同可以選擇不同的頂點(diǎn)作為凸多邊形的頂點(diǎn)，但在使用RSSI信號(hào)強(qiáng)度方法進(jìn)行定位時(shí)，由于RSSI信號(hào)測(cè)距誤差的大小與距離成正比，且經(jīng)過(guò)實(shí)測(cè)后發(fā)現(xiàn)測(cè)距誤差是非線(xiàn)性的，因此無(wú)論選擇哪些點(diǎn)作為凸多邊形的頂點(diǎn)，其所圍成的凸多邊形區(qū)域均不能覆蓋最終定位坐標(biāo)的全部值域。而由多個(gè)參考節(jié)點(diǎn)的RSSI信號(hào)測(cè)距誤差圓環(huán)所組成的不規(guī)則扇形區(qū)域覆蓋了定位坐標(biāo)的全部值域，如圖2所示。圖中箭頭所指處為在給定的測(cè)距誤差條件下定位誤差值最小的坐標(biāo)點(diǎn)，而該點(diǎn)并不在圖1所示的凸多邊形區(qū)域內(nèi)部。使用質(zhì)心算法進(jìn)行定位計(jì)算，實(shí)際上是將非線(xiàn)性問(wèn)題轉(zhuǎn)換為線(xiàn)性問(wèn)題進(jìn)行求解，雖然降低了問(wèn)題求解的難度，但未能完整地覆蓋原始問(wèn)題模型的值域，因此定位結(jié)果的誤差較大。

使用典型的極大似然估計(jì)法進(jìn)行定位坐標(biāo)計(jì)算時(shí)，由于未考慮RSSI信號(hào)強(qiáng)度波動(dòng)引起的測(cè)距誤差，會(huì)將各參考節(jié)點(diǎn)置為相同的可信度，忽略不同參考節(jié)點(diǎn)的測(cè)距誤差值，從而降低了定位的精度。即便使用改進(jìn)的考慮RSSI測(cè)距誤差的極大似然估計(jì)法，也存在從非線(xiàn)性模型轉(zhuǎn)換為線(xiàn)性模型的誤差問(wèn)題[10]。

使用遺傳算法求解定位問(wèn)題可以避免上述問(wèn)題。首先，遺傳算法的目標(biāo)函數(shù)的定義域可以為任意集合且不會(huì)受到連續(xù)可微的約束，能夠完整地覆蓋原始問(wèn)題模型的值域，可以通過(guò)對(duì)待解決的問(wèn)題進(jìn)行分析并設(shè)計(jì)合理的適應(yīng)度函數(shù)對(duì)其值域進(jìn)行有效控制；其次，使用遺傳算法可以避免典型定位算法中從非線(xiàn)性模型轉(zhuǎn)換為線(xiàn)性模型時(shí)產(chǎn)生的定位誤差[9]。上述特點(diǎn)使得遺傳算法非常適合求解定位問(wèn)題，將使用遺傳算法對(duì)定位結(jié)果進(jìn)行全局優(yōu)化。

3 基于遺傳算法的定位算法

采用RSSI方法進(jìn)行定位需要獲取盲節(jié)點(diǎn)與多個(gè)參考節(jié)點(diǎn)之間的實(shí)測(cè)距離，由于RSSI信號(hào)在實(shí)際傳播過(guò)程中受環(huán)境影響會(huì)造成信號(hào)衰減，與理論或經(jīng)驗(yàn)?zāi)Ｐ陀幸欢ㄆ?，?dǎo)致以各參考節(jié)點(diǎn)為圓心、以各自測(cè)距為半徑的圓，并未相交于同一交點(diǎn)。為了降低定位誤差，需要對(duì)已獲得的多個(gè)帶有誤差的RSSI距離值進(jìn)行全局優(yōu)化計(jì)算，再計(jì)算出定位結(jié)果。因此，基于RSSI測(cè)距的無(wú)線(xiàn)定位方法是多約束條件下的優(yōu)化問(wèn)題。

由于遺傳算法在求解多約束條件下的組合優(yōu)化問(wèn)題有其獨(dú)特優(yōu)勢(shì)，具有文章前面所述的諸多優(yōu)點(diǎn)，將使用改進(jìn)的遺傳算法來(lái)求解待定位結(jié)點(diǎn)的坐標(biāo)。

3.1 種群初始化

先使用考慮參考節(jié)點(diǎn)RSSI信號(hào)波動(dòng)誤差的加權(quán)質(zhì)心算法對(duì)種群進(jìn)行初始化，再使用記憶搜索方向并自適應(yīng)調(diào)整搜索半徑的向量交叉機(jī)制進(jìn)行交叉操作。

在室內(nèi)辦公環(huán)境下使用基于CC2500無(wú)線(xiàn)通信模塊的收發(fā)設(shè)備經(jīng)過(guò)多次實(shí)測(cè)后，使用極大似然估計(jì)法計(jì)算出RSSI信號(hào)波動(dòng)引起的測(cè)距誤差與實(shí)測(cè)距離的關(guān)系為：

其中efi（error of fluctuation）為參考節(jié)點(diǎn)i的RSSI信號(hào)波動(dòng)引起的測(cè)距誤差，disti為未知位點(diǎn)與參考節(jié)點(diǎn)i的實(shí)測(cè)距離，reliabilityi為參考節(jié)點(diǎn)i的測(cè)距可信度，可信度越高表明該參考節(jié)點(diǎn)的測(cè)距精度越高。

優(yōu)秀的初始種群可以加快整個(gè)群體向最優(yōu)解的進(jìn)化速度，這就需要在考慮算法關(guān)鍵因素的情況下使用較小的時(shí)間復(fù)雜度進(jìn)行計(jì)算。此處采用考慮參考節(jié)點(diǎn)RSSI信號(hào)波動(dòng)誤差的質(zhì)心算法來(lái)初始化種群。種群初始化的步驟如下：

（1）從多個(gè)參考節(jié)點(diǎn)中按測(cè)距可信度從高至低選出不在同一直線(xiàn)上的3個(gè)參考節(jié)點(diǎn)。

（2）以3個(gè)參考節(jié)點(diǎn)坐標(biāo)為圓心，以各自的實(shí)測(cè)距離為半徑獲得各圓之間的交點(diǎn)。當(dāng)有兩個(gè)交點(diǎn)時(shí)，選擇與另一個(gè)參考節(jié)點(diǎn)距離較近的交點(diǎn)作為待加權(quán)坐標(biāo)點(diǎn)，3個(gè)參考節(jié)點(diǎn)共可獲得3個(gè)待加權(quán)坐標(biāo)點(diǎn)。此時(shí)可能會(huì)出現(xiàn)兩種兩圓無(wú)交點(diǎn)的情況：

其中ri為參考節(jié)點(diǎn)i的實(shí)測(cè)距離。此時(shí)需要對(duì)兩個(gè)參考節(jié)點(diǎn)的RSSI信號(hào)波動(dòng)誤差按可信度進(jìn)行等比縮放，以使兩圓有唯一交點(diǎn)，將該交點(diǎn)作為待加權(quán)坐標(biāo)點(diǎn)。縮放率rate按公式（3）計(jì)算獲得：

經(jīng)過(guò)上述操作后已獲得3個(gè)待加權(quán)坐標(biāo)點(diǎn)，再按公式（4）計(jì)算其權(quán)值：

其中i，j表示不同的參考節(jié)點(diǎn)，weightij表示由參考節(jié)點(diǎn)i和參考節(jié)點(diǎn)j的測(cè)距值為半徑所得到的待加權(quán)坐標(biāo)點(diǎn)的權(quán)重。

（3）按公式（5）和（6）計(jì)算考慮參考節(jié)點(diǎn)RSSI信號(hào)波動(dòng)誤差的質(zhì)心點(diǎn)坐標(biāo)：

其中Δv為對(duì)質(zhì)心坐標(biāo)增加的微幅隨機(jī)擾動(dòng)參數(shù)，以此來(lái)保證初始種群的多樣性。accurate為用戶(hù)要求的定位精度，nodeSize為參考節(jié)點(diǎn)的數(shù)量。重復(fù)上述步驟popSize次，即完成了個(gè)體數(shù)量為popSize的種群初始化。還需計(jì)算出公式（5）和（6）中的不包含Δv參數(shù)時(shí)的一組基準(zhǔn)質(zhì)心坐標(biāo)，用于保存對(duì)后續(xù)的向量交叉操作進(jìn)行指導(dǎo)的初始化信息。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來(lái)衡量群體中的個(gè)體優(yōu)秀與否的標(biāo)準(zhǔn)，它必須能夠反映出個(gè)體的優(yōu)秀程度：優(yōu)秀的個(gè)體其適應(yīng)度值較大，而性能差的個(gè)體則適應(yīng)度值較小。此處采用基于信標(biāo)可信度的加權(quán)質(zhì)心原理，將適應(yīng)度函數(shù)按如下公式進(jìn)行定義：

在種群的每一代進(jìn)化過(guò)程中，先使用公式（8）計(jì)算個(gè)體的適應(yīng)度值，再將種群中的個(gè)體按照適應(yīng)度值由高到低進(jìn)行排序。當(dāng)兩個(gè)不同個(gè)體的適應(yīng)度值相同時(shí)，再通過(guò)公式（9）計(jì)算附加適應(yīng)度值并進(jìn)行比較。公式（8）是坐標(biāo)點(diǎn)在測(cè)距誤差區(qū)域外部時(shí)的適應(yīng)度值，公式（9）是坐標(biāo)點(diǎn)在測(cè)距誤差區(qū)域內(nèi)部時(shí)的適應(yīng)度值。

3.3 選擇、交叉、變異

首先從群體中選出Nbest個(gè)適應(yīng)度最高的個(gè)體，將這些個(gè)體直接遺傳到下一代群體中，以此來(lái)保證進(jìn)化過(guò)程中某一代的最優(yōu)解不被交叉和變異操作所破壞。其余的個(gè)體則由交叉操作生成。考慮到適應(yīng)度較高的兩個(gè)個(gè)體交叉后生成優(yōu)秀個(gè)體的概率較大，此處先以個(gè)體適應(yīng)度占種群適應(yīng)度的百分比為概率選出兩個(gè)父?jìng)€(gè)體Ta，Tb，再進(jìn)行交叉操作。個(gè)體Ti被選中的概率Pi按公式（10）計(jì)算。

其中概率Pi反映了個(gè)體i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例，即第i個(gè)個(gè)體被選中的概率與其適應(yīng)度的值成正比。

在二維空間條件下，為了增加個(gè)體搜索到適應(yīng)度更高的坐標(biāo)點(diǎn)的概率，文章采用了記憶搜索方向的向量交叉機(jī)制。每一個(gè)個(gè)體都包含一個(gè)記憶搜索方向的向量，該向量始終由某個(gè)父?jìng)€(gè)體的坐標(biāo)點(diǎn)指向當(dāng)前個(gè)體的坐標(biāo)點(diǎn)，用于記錄當(dāng)前個(gè)體在進(jìn)化過(guò)程中的搜索方向及步長(zhǎng)信息。在種群初始化時(shí)將該向量設(shè)為由基準(zhǔn)質(zhì)心坐標(biāo)點(diǎn)指向當(dāng)前個(gè)體的坐標(biāo)點(diǎn)。對(duì)于父?jìng)€(gè)體Ta，Tb，交叉操作的主要步驟如下：

將兩個(gè)父?jìng)€(gè)體的記憶搜索方向的向量，分別以自身向量為基準(zhǔn)，以與另一向量的最小角度差為限制范圍，按與旋轉(zhuǎn)度數(shù)成反比的概率對(duì)自身向量進(jìn)行旋轉(zhuǎn)，以此增大在記憶搜索方向上搜索的概率，再將向量的模型以?xún)蓚€(gè)向量的差為限制范圍進(jìn)行隨機(jī)縮放，以此對(duì)搜索半徑進(jìn)行自適應(yīng)調(diào)整，如圖3所示。此時(shí)將兩個(gè)父?jìng)€(gè)體的坐標(biāo)與新生成的兩個(gè)向量進(jìn)行累加產(chǎn)生兩個(gè)新的子個(gè)體，然后計(jì)算這兩個(gè)子個(gè)體的適應(yīng)度值并與兩個(gè)父?jìng)€(gè)體進(jìn)行比較，將適應(yīng)度較大的兩個(gè)個(gè)體復(fù)制到新的種群中去，以確保整個(gè)群體的平均適應(yīng)度呈非遞減狀態(tài)。變異采用與交叉類(lèi)似的機(jī)制，通過(guò)對(duì)個(gè)體自身的記憶搜索方向的向量進(jìn)行偏角旋轉(zhuǎn)來(lái)實(shí)現(xiàn)。

可以采用以下3種方式中的一種來(lái)決定算法何時(shí)停止運(yùn)行。

（1）最優(yōu)個(gè)體的適應(yīng)度值連續(xù)指定代數(shù)未更新。此時(shí)說(shuō)明種群的進(jìn)化已趨于穩(wěn)定。

（2）限定算法運(yùn)行指定的時(shí)間，例如限定算法只運(yùn)行200 ms。該方法可通過(guò)限定算法的運(yùn)行時(shí)間來(lái)為系統(tǒng)提供額外的休眠時(shí)間，以達(dá)到節(jié)省設(shè)備電能、延長(zhǎng)設(shè)備使用時(shí)間的目的。

（3）指定算法中群體進(jìn)化的代數(shù)。

最后，選出最優(yōu)個(gè)體的坐標(biāo)值作為最終的定位坐標(biāo)。

4 實(shí)驗(yàn)結(jié)果與分析

考慮到后續(xù)功能及協(xié)議擴(kuò)展的靈活性，采用可定制通信協(xié)議的CC2500芯片和STM32處理器，并自行設(shè)計(jì)并實(shí)現(xiàn)了相關(guān)的通信協(xié)議。

CC2500是低成本真正單片的2.4 GHz收發(fā)器，為低功耗無(wú)線(xiàn)應(yīng)用而設(shè)計(jì)。電路設(shè)定為2 400～2 483.5 MHz的ISM（工業(yè)、科學(xué)和醫(yī)學(xué)）和SRD（短距離設(shè)備）頻率波段。RF收發(fā)器集成了一個(gè)數(shù)據(jù)傳輸率可達(dá)500 kbps的高度可配置的調(diào)制解調(diào)器。具有高靈敏度（10 kbps下-98 dBm，1%數(shù)據(jù)包誤差率）、可編程控制的輸出功率（可達(dá)+1 dBm）、數(shù)字RSSI 輸出等特性。通過(guò)向基于CC2500芯片的無(wú)線(xiàn)收發(fā)設(shè)備寫(xiě)入不同的代碼，可以在不改變硬件設(shè)備的條件下分別實(shí)現(xiàn)參考節(jié)點(diǎn)、盲節(jié)點(diǎn)和中心節(jié)點(diǎn)的各自功能。

為了驗(yàn)證提出的無(wú)線(xiàn)定位算法及定位系統(tǒng)的實(shí)際應(yīng)用效果，在本市消防中隊(duì)與某公司聯(lián)合舉辦的消防演習(xí)中，消防員配備基于CC2500芯片的定位設(shè)備后，進(jìn)入已布置參考結(jié)點(diǎn)的辦公樓內(nèi)對(duì)被困人員進(jìn)行搜救及疏散。基于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的消防員室內(nèi)定位系統(tǒng)結(jié)構(gòu)如圖4所示，其中黑色方塊為布置的參考節(jié)點(diǎn)，可以對(duì)消防員攜帶的接收設(shè)備發(fā)射RSSI信號(hào)。接收設(shè)備接收到多個(gè)RSSI信號(hào)后使用算法進(jìn)行定位坐標(biāo)計(jì)算，并將定位結(jié)果通過(guò)無(wú)線(xiàn)信號(hào)發(fā)送給中心節(jié)點(diǎn)，中心節(jié)點(diǎn)再將消防員的位置等信息發(fā)送至消防員定位系統(tǒng)監(jiān)控端，指揮中心可以在監(jiān)控端屏幕上實(shí)時(shí)掌握消防員的位置等信息，再進(jìn)行統(tǒng)一指揮部署。

實(shí)驗(yàn)背景和參數(shù)如下：每個(gè)房間內(nèi)需要布置4～8個(gè)參考節(jié)點(diǎn)，參考節(jié)點(diǎn)的具體數(shù)量視房間大小而定，走廊以5米間隔布置參考節(jié)點(diǎn)，辦公樓內(nèi)的走廊及房間內(nèi)均有桌椅、電腦、柜子等物品。大廳較為空曠，可以將參考節(jié)點(diǎn)布置的間隔設(shè)為8～12米。中心節(jié)點(diǎn)布置在指揮中心，使用串口線(xiàn)與消防員室內(nèi)定位系統(tǒng)監(jiān)控端進(jìn)行連接。在消防員隨身攜帶的定位設(shè)備中，將遺傳算法中的各參數(shù)進(jìn)行如下設(shè)置：初始種群數(shù)量為30，交叉概率為0.5，變異概率為0.02。算法并未設(shè)置指定的遺傳代數(shù)，而是限定算法運(yùn)行的總時(shí)間為300 ms，同時(shí)將定位頻率設(shè)為500 ms，為系統(tǒng)保留了200 ms的休眠時(shí)間，以達(dá)到節(jié)省設(shè)備電能、延長(zhǎng)設(shè)備使用時(shí)間的目的。上述參數(shù)均可以在指揮中心的監(jiān)控端軟件實(shí)時(shí)進(jìn)行遠(yuǎn)程設(shè)置。

為了與改進(jìn)的極大似然估計(jì)定位算法進(jìn)行定位精度的比較，先通過(guò)監(jiān)控端的遠(yuǎn)程參數(shù)設(shè)置功能，將消防員隨身攜帶的定位設(shè)備中的定位算法設(shè)為改進(jìn)的極大似然估計(jì)定位算法，運(yùn)行15分鐘后，再將定位算法設(shè)為改進(jìn)的遺傳算法，并運(yùn)行相同的時(shí)間。消防員隨身攜帶的定位設(shè)備將每次計(jì)算出的定位結(jié)果發(fā)送給中心節(jié)點(diǎn)，中心節(jié)點(diǎn)再將每次的定位結(jié)果通過(guò)RS232串口發(fā)送給指揮中心監(jiān)控端，監(jiān)控端將遺傳算法與改進(jìn)的極大似然估計(jì)定位算法運(yùn)行的結(jié)果各取平均值后進(jìn)行數(shù)據(jù)對(duì)比，結(jié)果如表1和圖5所示。

從實(shí)驗(yàn)結(jié)果可以看出，在與參考節(jié)點(diǎn)的最近距離為2～12米范圍內(nèi)時(shí)，基于遺傳算法的定位算法比改進(jìn)的極大似然定位算法的平均定位誤差降低了約10% ～ 30%，有效地提高了定位精度。其中在4米處左右，因障礙物較多造成了在該點(diǎn)處的RSSI信號(hào)波動(dòng)較為明顯，使用改進(jìn)的算法后平均定位誤差仍比改進(jìn)的極大似然定位算法降低了約20.55%。

5 結(jié)語(yǔ)

本文針對(duì)典型的極大似然定位算法、質(zhì)心定位算法及改進(jìn)的相關(guān)算法的不足之處進(jìn)行了分析，文章提出了基于遺傳算法的定位算法。該算法采用考慮參考節(jié)點(diǎn)RSSI信號(hào)波動(dòng)誤差的質(zhì)心算法進(jìn)行種群初始化，充分考慮了參考節(jié)點(diǎn)的測(cè)距可信度。在參考節(jié)點(diǎn)的測(cè)距誤差區(qū)域內(nèi)部與外部使用不同的適應(yīng)度函數(shù)進(jìn)行度量，既可以增加搜索初期的搜索范圍，又可以在搜索后期進(jìn)行更精確的優(yōu)化。結(jié)合基于記憶搜索方向的交叉機(jī)制和自適應(yīng)調(diào)整搜索半徑的策略，為下一代種群的搜索方向及搜索半徑提供了指導(dǎo)信息，有效地提高了種群進(jìn)化的速度并提高了定位精度。

[參考文獻(xiàn)]

[1]MUNOZ D， BOUCHEREAU F， VARGAS C， et al.Position location techniques and applications[M]. Burlington：Academic Press， 2009.

[2]MERAT S， ALMUHTADI W. Wireless network channel quality estimation inside reactor building using RSSI measurement of wireless sensor network[A].Proceeding in Electrical and Computer Engineering， 2009[C]. Canada：Canadian Conference on Electrical and Computer Engineering， 2009：339-341.

[3]WASSI G I， DESPINS C， GRENIER D， et al. Indoor location using received signal strength of IEEE 802.11b access point[C]. Canada：Canadian Conference Electrical and Computer Engineering， 2005：1371-1374.

[4]CHEN P C. A non-line-of-sight error mitigation algorithm in location estimation[J].IEEE Wireless Communication and Network， 1999（1）：316-320.

[5]WYLIE M P， HOLTZMAN J. The non-line of sight problem in mobile location estimation[C].Boston：5th IEEE International Conference on Universal Personal Communications， 1996：827-831.

[6]陳維克，李文鋒，首珩，等. 基于RSSI的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J]. 武漢理工大學(xué)學(xué)報(bào)，2006（2）：265-268.

[7]WEIKE C， WENFENG L， HENG S， et al. Weighted centroid localization algorithm based on RSSI for wireless sensor networks[J]. Journal of WuHan University of Technology， 2006（2）：265-268.

[8]石琴琴，霍宏，方濤，等.使用最速下降算法提高極大似然估計(jì)算法的節(jié)點(diǎn)定位精度[J].計(jì)算機(jī)應(yīng)用研究，2008（7）：2038-2040.

[9]QINQIN S， HONG H， TAO F， et al. Using steepest descent method to improve node localization[J]. Application Research of Computers， 2008（7）：2038-2040.

[9]MICHALEWICZ Z， JANIKOW C Z， KRAWCZYK J B. A modified genetic algorithm for optimal control problems[J]. Computers and Mathematics with Applications， 1992（12）：83-94.

[10]GREFENSTELLE J J， GOPAL R， ROSMAITA B， et al. Genetic algorithms for the traveling salesman[C]. USA：Proceeding of International Conference of genetic algorithm and their applications， 1985（7）：359-371.

[11]KUSHKI A， PLATANIOTIS K， VENETSANOPOULOS A.Intelligent dynamic radio tracking in indoor wireless local area networks[J]. IEEE Transactions on Mobile Computing， 2010（3）：405-419.