基于RSSI和遺傳算法的無線定位方法及其實現

孫建領+張宏欽

摘 要：隨著無線電技術的發展，無線傳感器網絡在目標跟蹤、環境監測、空間探索等領域得到廣泛應用，節點定位技術在無線傳感器網絡中具有重要地位。文章提出了基于遺傳算法的無線定位算法，解決了基于RSSI信號強度的無線定位方法定位精度較低的問題。該算法采用考慮參考節點RSSI信號波動誤差的質心算法進行種群初始化，使用基于記憶搜索方向的交叉機制和自適應調整搜索半徑的策略，為下一代種群的搜索方向及搜索半徑提供有效的指導信息。實驗結果表明，該算法的定位精度明顯高于典型及改進的極大似然估計定位算法，有效地提高了定位精度。

關鍵詞：無線定位；遺傳算法；接收信號強度

1 無線傳感器研究背景

無線傳感器網絡（Wireless Sensor Network，WSN）是由大量的微型傳感器節點組成的數據網絡系統，主要用于在網絡覆蓋范圍內進行信息的采集、分析和處理，并能夠最終將關鍵數據返回給控制中心。無線傳感器網絡的定位技術就是先通過獲取未知坐標節點與已知坐標的參考節點之間的距離等信息，再通過某種定位算法來計算出未知節點坐標的技術[1]。它可以廣泛應用于災難救援、智能城市、交通管理、環境監測、醫療衛生、國防軍事等諸多領域。

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

遺傳算法是借鑒生物界“適者生存”原則的優化算法[8]，其目標函數的定義域可以為任意集合且不會受到連續可微的約束，這種特點使得遺傳算法非常適合求解定位問題，避免了典型定位算法中值域轉換及從非線性模型轉換為線性模型時產生的定位誤差[9]。

基于RSSI和遺傳算法的無線定位算法采用考慮參考節點RSSI信號波動誤差的質心算法進行種群初始化，具有記憶搜索方向和自適應調整搜索半徑的特點，能為下一代種群的搜索方向及搜索半徑提供有效的指導信息，可以有效地提高無線定位的精度。將WSN中需要定位的節點稱為盲節點，而將已知坐標位置并能協助盲節點進行定位的節點稱為參考節點。

2 典型的定位算法存在的問題

典型的定位應用通常使用改進的質心法或極大似然估計法來確定坐標位置，通過對這兩種定位算法進行分析后發現以下問題。

使用典型或改進的質心算法進行定位坐標計算時，最終計算的定位坐標位置必然限定在由幾個頂點所圍成的凸多邊形內部，這是由質心算法的幾何性質所決定的。當僅有3個頂點時，凸多邊形即為三角形區域，其中一種情況如圖1所示。

雖然根據算法的不同可以選擇不同的頂點作為凸多邊形的頂點，但在使用RSSI信號強度方法進行定位時，由于RSSI信號測距誤差的大小與距離成正比，且經過實測后發現測距誤差是非線性的，因此無論選擇哪些點作為凸多邊形的頂點，其所圍成的凸多邊形區域均不能覆蓋最終定位坐標的全部值域。而由多個參考節點的RSSI信號測距誤差圓環所組成的不規則扇形區域覆蓋了定位坐標的全部值域，如圖2所示。圖中箭頭所指處為在給定的測距誤差條件下定位誤差值最小的坐標點，而該點并不在圖1所示的凸多邊形區域內部。使用質心算法進行定位計算，實際上是將非線性問題轉換為線性問題進行求解，雖然降低了問題求解的難度，但未能完整地覆蓋原始問題模型的值域，因此定位結果的誤差較大。

使用典型的極大似然估計法進行定位坐標計算時，由于未考慮RSSI信號強度波動引起的測距誤差，會將各參考節點置為相同的可信度，忽略不同參考節點的測距誤差值，從而降低了定位的精度。即便使用改進的考慮RSSI測距誤差的極大似然估計法，也存在從非線性模型轉換為線性模型的誤差問題[10]。

使用遺傳算法求解定位問題可以避免上述問題。首先，遺傳算法的目標函數的定義域可以為任意集合且不會受到連續可微的約束，能夠完整地覆蓋原始問題模型的值域，可以通過對待解決的問題進行分析并設計合理的適應度函數對其值域進行有效控制；其次，使用遺傳算法可以避免典型定位算法中從非線性模型轉換為線性模型時產生的定位誤差[9]。上述特點使得遺傳算法非常適合求解定位問題，將使用遺傳算法對定位結果進行全局優化。

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

采用RSSI方法進行定位需要獲取盲節點與多個參考節點之間的實測距離，由于RSSI信號在實際傳播過程中受環境影響會造成信號衰減，與理論或經驗模型有一定偏差，導致以各參考節點為圓心、以各自測距為半徑的圓，并未相交于同一交點。為了降低定位誤差，需要對已獲得的多個帶有誤差的RSSI距離值進行全局優化計算，再計算出定位結果。因此，基于RSSI測距的無線定位方法是多約束條件下的優化問題。

由于遺傳算法在求解多約束條件下的組合優化問題有其獨特優勢，具有文章前面所述的諸多優點，將使用改進的遺傳算法來求解待定位結點的坐標。

3.1 種群初始化

先使用考慮參考節點RSSI信號波動誤差的加權質心算法對種群進行初始化，再使用記憶搜索方向并自適應調整搜索半徑的向量交叉機制進行交叉操作。

在室內辦公環境下使用基于CC2500無線通信模塊的收發設備經過多次實測后，使用極大似然估計法計算出RSSI信號波動引起的測距誤差與實測距離的關系為：

其中efi（error of fluctuation）為參考節點i的RSSI信號波動引起的測距誤差，disti為未知位點與參考節點i的實測距離，reliabilityi為參考節點i的測距可信度，可信度越高表明該參考節點的測距精度越高。

優秀的初始種群可以加快整個群體向最優解的進化速度，這就需要在考慮算法關鍵因素的情況下使用較小的時間復雜度進行計算。此處采用考慮參考節點RSSI信號波動誤差的質心算法來初始化種群。種群初始化的步驟如下：

（1）從多個參考節點中按測距可信度從高至低選出不在同一直線上的3個參考節點。

（2）以3個參考節點坐標為圓心，以各自的實測距離為半徑獲得各圓之間的交點。當有兩個交點時，選擇與另一個參考節點距離較近的交點作為待加權坐標點，3個參考節點共可獲得3個待加權坐標點。此時可能會出現兩種兩圓無交點的情況：

其中ri為參考節點i的實測距離。此時需要對兩個參考節點的RSSI信號波動誤差按可信度進行等比縮放，以使兩圓有唯一交點，將該交點作為待加權坐標點。縮放率rate按公式（3）計算獲得：

經過上述操作后已獲得3個待加權坐標點，再按公式（4）計算其權值：

其中i，j表示不同的參考節點，weightij表示由參考節點i和參考節點j的測距值為半徑所得到的待加權坐標點的權重。

（3）按公式（5）和（6）計算考慮參考節點RSSI信號波動誤差的質心點坐標：

其中Δv為對質心坐標增加的微幅隨機擾動參數，以此來保證初始種群的多樣性。accurate為用戶要求的定位精度，nodeSize為參考節點的數量。重復上述步驟popSize次，即完成了個體數量為popSize的種群初始化。還需計算出公式（5）和（6）中的不包含Δv參數時的一組基準質心坐標，用于保存對后續的向量交叉操作進行指導的初始化信息。

3.2 適應度函數

適應度函數是用來衡量群體中的個體優秀與否的標準，它必須能夠反映出個體的優秀程度：優秀的個體其適應度值較大，而性能差的個體則適應度值較小。此處采用基于信標可信度的加權質心原理，將適應度函數按如下公式進行定義：

在種群的每一代進化過程中，先使用公式（8）計算個體的適應度值，再將種群中的個體按照適應度值由高到低進行排序。當兩個不同個體的適應度值相同時，再通過公式（9）計算附加適應度值并進行比較。公式（8）是坐標點在測距誤差區域外部時的適應度值，公式（9）是坐標點在測距誤差區域內部時的適應度值。

3.3 選擇、交叉、變異

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

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

在二維空間條件下，為了增加個體搜索到適應度更高的坐標點的概率，文章采用了記憶搜索方向的向量交叉機制。每一個個體都包含一個記憶搜索方向的向量，該向量始終由某個父個體的坐標點指向當前個體的坐標點，用于記錄當前個體在進化過程中的搜索方向及步長信息。在種群初始化時將該向量設為由基準質心坐標點指向當前個體的坐標點。對于父個體Ta，Tb，交叉操作的主要步驟如下：

將兩個父個體的記憶搜索方向的向量，分別以自身向量為基準，以與另一向量的最小角度差為限制范圍，按與旋轉度數成反比的概率對自身向量進行旋轉，以此增大在記憶搜索方向上搜索的概率，再將向量的模型以兩個向量的差為限制范圍進行隨機縮放，以此對搜索半徑進行自適應調整，如圖3所示。此時將兩個父個體的坐標與新生成的兩個向量進行累加產生兩個新的子個體，然后計算這兩個子個體的適應度值并與兩個父個體進行比較，將適應度較大的兩個個體復制到新的種群中去，以確保整個群體的平均適應度呈非遞減狀態。變異采用與交叉類似的機制，通過對個體自身的記憶搜索方向的向量進行偏角旋轉來實現。

可以采用以下3種方式中的一種來決定算法何時停止運行。

（1）最優個體的適應度值連續指定代數未更新。此時說明種群的進化已趨于穩定。

（2）限定算法運行指定的時間，例如限定算法只運行200 ms。該方法可通過限定算法的運行時間來為系統提供額外的休眠時間，以達到節省設備電能、延長設備使用時間的目的。

（3）指定算法中群體進化的代數。

最后，選出最優個體的坐標值作為最終的定位坐標。

4 實驗結果與分析

考慮到后續功能及協議擴展的靈活性，采用可定制通信協議的CC2500芯片和STM32處理器，并自行設計并實現了相關的通信協議。

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

為了驗證提出的無線定位算法及定位系統的實際應用效果，在本市消防中隊與某公司聯合舉辦的消防演習中，消防員配備基于CC2500芯片的定位設備后，進入已布置參考結點的辦公樓內對被困人員進行搜救及疏散。基于無線傳感器網絡的消防員室內定位系統結構如圖4所示，其中黑色方塊為布置的參考節點，可以對消防員攜帶的接收設備發射RSSI信號。接收設備接收到多個RSSI信號后使用算法進行定位坐標計算，并將定位結果通過無線信號發送給中心節點，中心節點再將消防員的位置等信息發送至消防員定位系統監控端，指揮中心可以在監控端屏幕上實時掌握消防員的位置等信息，再進行統一指揮部署。

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

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

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

5 結語

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

[參考文獻]

[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的無線傳感器網絡加權質心定位算法[J]. 武漢理工大學學報，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].計算機應用研究，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.