1、井岡山大學(xué)學(xué)報(自然科學(xué)版文章編號：1674-8085(201104-0071-05一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)研究*廖 萍，孔翠香(井岡山大學(xué)電子與信息工程學(xué)院, 江西，吉安 343009摘 要：本文分析了基于誤差的最小二乘估計定位原理，提出一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)。建立所有節(jié)點的定位誤差之和最小的數(shù)學(xué)模型，利用遺傳算法求解模型的最優(yōu)解，從而得到未知節(jié)點的最優(yōu)的估計位置。實驗仿真結(jié)果表明該算法對未知節(jié)點的定位精度高，條件簡單，適合各種規(guī)模的無線傳感網(wǎng)絡(luò)節(jié)點的定位。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；定位；遺傳算法；錨節(jié)點中圖分類號：TP393.02 文獻(xiàn)標(biāo)識碼：A D

2、OI:10.3969/j.issn.1674-8085.2011.04.018STUDY ON A LOCALIZATION TECHNOLOGY OF WIRELESS SENSORNETWORK BASED ON GENETIC ALGORITHM*LIAO Ping，KONG Cui-xiang(School of Electronic and Information Engineering, Jinggangshan University, Jian, Jiangxi 343009,ChinaAbstract: We analyze the shortcomings of the le

3、ast squares estimation localization algorithm in Wireless SensorNetwork. A novel localization Technology based on genetic algorithm for Wireless Sensor Network is proposed. The mathematical model was built with the smallest error for all of nodes, and the genetic algorithm was used to get the optima

4、l solution of the model. Finally, we can get the optimal estimate position of the unknown nodes. The results of the simulation show that the localization accuracy of the algorithm is efficient for the nodes of the Wireless Sensor Network, and its condition is simple so that suitable for all sizes of

5、 wireless sensor networks. Key words: wireless sensor network; localization; genetic algorithm; anchor node0 引言無線傳感器網(wǎng)絡(luò)是由部署在檢測區(qū)域，具有通信與計算能力的傳感器節(jié)點組成的自組織分布式網(wǎng)絡(luò)系統(tǒng)，其作用是協(xié)作式的感知、采集和處理網(wǎng)絡(luò)監(jiān)測區(qū)域內(nèi)的信息并發(fā)送給檢測者1。傳感器節(jié)點采集或感知的數(shù)據(jù)不知道具體的位置信息是毫無意義的2，因此傳感器節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)應(yīng)用中的關(guān)鍵技術(shù)之一3-4。雖然采用GPS 定位系統(tǒng)可以精確得到每個節(jié)點的位置，但高昂的成本使GPS 定位不能廣泛應(yīng)

6、用于傳感器節(jié)點的定位。現(xiàn)有的無線傳感網(wǎng)絡(luò)定位算法大多依據(jù)少量位置已知的錨節(jié)點來估計整個網(wǎng)絡(luò)中未知節(jié)點的位置。常見的無線傳感器網(wǎng)絡(luò)定位算法可分為基于測距5的定位算法以及與距離無關(guān)的定位算法。基于測距的定位算法（如RSSI 6-10、TOA 和TDOA ）在定位過程中需要測量節(jié)點間的距離或角度信息，該定位算法對節(jié)點的硬件要求較高并受測量環(huán)境的影響較大。而無需測距的定位算法在定位過程中無需測量節(jié)點間的距離或角度信息，而是第32卷第4期 V ol.32 No.4 井岡山大學(xué)學(xué)報(自然科學(xué)版2011年 7 月 July 2011 Journal of Jinggangshan University (N

7、atural Science 71收稿日期：2011-04-18；修改日期：2011-06-10基金項目：吉安市重點科技計劃項目(吉市科技字200940號作者簡介：*廖 萍(1980- ，男，湖南衡陽人，講師，主要從事計算機(jī)應(yīng)用、計算機(jī)網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)等研究(Email: jxjgsliaoping;孔翠香(1978- ，女，陜西渭南人，講師，碩士，主要從事無線傳感器網(wǎng)絡(luò)、Ad hoc網(wǎng)絡(luò)等研究(Email: liuyun8888.井岡山大學(xué)學(xué)報(自然科學(xué)版72采用節(jié)點間的估算距離來實現(xiàn)節(jié)點的定位，如Radhika Nagpal等提出Amorphous 11定位算法，以及Dv Hop算法，

8、這類定位算法硬件成本低、功耗小、但定位精度較差。以上定位算法均具有自身的特點，但它們的定位精度都不夠理想，且在定位最后階段均采用最小二乘估計定位算法估算未知節(jié)點的位置。1 基于誤差的最小二乘估計定位原理大多數(shù)定位算法對未知節(jié)點的計算是通過獲知三個或三個以上錨節(jié)點間的距離，運用最小二乘法估計法估計出未知節(jié)點的位置。最小二乘估計的定位原理可描述為：當(dāng)已知k 錨節(jié)點的位置, (11y x ， , (k k y x 以及它們距離待測節(jié)點, (y x 之間的距離為1r ，k r 時，可得方程組222111222( ( ( ( kk k x x y y r x x y y r +=+= （1）該方程組為非

9、線性方程組，不便于求解，用（1）式中的前1k 個方程減去第k 個方程后，可以得到Ax B =形式的線性方程組，其中11112( 2( 2( 2(n n n n n n x x y y A x x y y = （2） 222222111222222111k k k k k k k k k x x y y r r B x x y y r r +=+（3） 用最小二乘法估計求未知節(jié)點的位置(, x y ，但是由于最小二乘法用前1k 個方程減去第k 個方程的思路求解，解的精確程度受最后一個方程誤差的限制，如果最后一個方程誤差較大的話，即使前1k 個方程誤差很小，定位結(jié)果的誤差也會較大。由此引入誤差項，

10、用前1k 個方程減去第k 個方程得1112222221111112222221112( 2( _2( 2( k k k k k k k k k k k kk k k k k k x x x y y y e e x x y y r r x x x y y y e e x x y y r r +=+=+ 即： ( i Ax e e B +=式中( i e e 項為誤差項，其為1k 維隨機(jī)誤差向量，根據(jù)最小二乘原理求解方程使21ki i e e B Ax =取值達(dá)到最小來求x 的估計值，對上式關(guān)于x 求導(dǎo)并令其等于0，可以求解出未知節(jié)點的最小二乘位置估計1( T T X A A A B = （4）該

11、算法依據(jù)節(jié)點的測距信息進(jìn)行定位，測距誤差的存在可能引起較高的定位誤差。本文從最小二乘估計法出發(fā)，引入遺傳算法來完成傳感器節(jié)點定位。2 基于遺傳算法的無線傳感網(wǎng)絡(luò)節(jié)點定位遺傳算法是一種借鑒自然界生物的遺傳和進(jìn)化過程而形成的自適應(yīng)全局隨機(jī)搜索與優(yōu)化算法。它將問題的所有可能解組成一個種群，將每一個可能解視為種群的個體，從選定的初始種群（解）出發(fā)，在整個種群空間內(nèi)隨機(jī)搜索，按照一定的適應(yīng)度函數(shù)評估每一個體，循環(huán)使用選擇、交叉、變異三種遺傳算子，使問題的解不斷進(jìn)化，直至搜索到最優(yōu)解。文獻(xiàn)12在第1階段利用采樣方法對節(jié)點初始位置進(jìn)行初步估計，在第2階段采用遺傳算法對節(jié)點初始位置進(jìn)行求精；文獻(xiàn)13用遺傳算法

12、優(yōu)化定位參數(shù)；文獻(xiàn)14用遺傳算法對無線傳感網(wǎng)絡(luò)節(jié)點定位及求取其路徑；本文提出一種新的無線傳感網(wǎng)絡(luò)節(jié)點定位算法。遺傳算法完成節(jié)點定位的基本步驟如下：(1 個體的編碼編碼是把問題的可行解從解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法。目的是為了隨機(jī)產(chǎn)生一組侯選變量，可以采用多種形式編碼（如二進(jìn)制編碼、符號編碼與符點數(shù)編碼），通常采用二進(jìn)制形式，即用0，1字符串構(gòu)成一定長度的基因鏈，表示個體變量，從遺傳算法解空間轉(zhuǎn)換問題空間稱為解碼。本文對個體的編碼采用二進(jìn)制編碼。二進(jìn)制編井岡山大學(xué)學(xué)報(自然科學(xué)版73碼中我們將每個個體的基因值用 1, 0(區(qū)間均勻分布的隨機(jī)數(shù)來表示，個體位置的縱坐標(biāo)與橫坐標(biāo)的

13、編碼長度均為10位。(2 種群的初始化假設(shè)網(wǎng)絡(luò)中共有K 個未知節(jié)點，坐標(biāo)可表示為11(, , ,(, j j x y x y ，(1,2,3, , j K = ，第j 個未知節(jié)點的坐標(biāo)用向量j X 表示，其中N 個節(jié)點為錨節(jié)點，位置11(, , ,(, i i a b a b ，(1,2,3, , i N = 。第i 個錨節(jié)點的坐標(biāo)用向量j A 表示，j X 可以與3個錨節(jié)點可以通信，設(shè)這三個錨節(jié)點坐標(biāo)分別為(, i i a b ，(1,2,3 i =中的任意三個錨節(jié)點，隨機(jī)產(chǎn)生100M =個個體l M (1,2,3, ,100 l = 作為初始種群，每個個體的位置(, l l m c (1,

14、2,3, ,100 l = 。(3 遺傳定位算法的適應(yīng)度函數(shù)設(shè)置 在遺傳算法中的適應(yīng)度函數(shù)設(shè)為:(, min(Kj j j f x y = (1,2,3, , j K = ，(1,2,3, , i N = 中的任意三個，其中(, j j x y 是第j 個未知節(jié)點的坐標(biāo)，(, i i a b 是第i 個錨節(jié)點的坐標(biāo)，i d 是第i 個未知節(jié)點與錨節(jié)點的距離。這樣就將節(jié)點定位問題轉(zhuǎn)化為模型優(yōu)化問題，即上式的最優(yōu)解即是未知節(jié)點的估計位置。(4 選擇算子的選取選擇也稱為復(fù)制，根據(jù)變量集中每個個體變量的適應(yīng)度值或一定概率值對群體中的個體進(jìn)行選擇和淘汰，其目的是為了避免基因缺失、提高計算效率和全局收斂性

15、，產(chǎn)生最優(yōu)的群體。因此遺傳算法中的優(yōu)良個性可以一直繁殖下去。選擇算子采用基于適應(yīng)度的賭輪選擇法。其基本思想是: 每個個體被選中的概率與其適應(yīng)度大小成正比，設(shè)群體大小為100M =，個體i 的適應(yīng)度為( f i ，那么個體i 被選中的概率p ix 可表示為：1(ix Mi f i p f i =，計算所有個體的適應(yīng)度值，并對它們按照從大到小的順序進(jìn)行排序。具體的選擇方法是依據(jù)每個個體的適應(yīng)度值進(jìn)行選擇：即適應(yīng)度值高的個體被遺傳至下一代群體中的概率大；適應(yīng)度值較低的個體被遺傳至下一代群體中概率較小。(5 交叉率的選取交叉（也叫重組）是在通過較大概率從群體中選擇出來的兩個不同的個體變量之間互換部分代

16、碼（交叉運算或基因重組）。遺傳算法中交叉概率p c 的選擇是影響遺傳算法性能的關(guān)鍵，p c 越大，新個體產(chǎn)生的速度越快，而p c 過大時，遺傳算法被破快的可能性也越大，使得具有高適應(yīng)度的個體結(jié)構(gòu)很快被破壞，但如果p c 過小，會使搜索過程緩慢或者停滯不前，因此需要不停的反復(fù)實驗來確定合適的p c 來找到問題的最佳解， 我們選擇個體以概率0.6c p =進(jìn)行交叉，也就是選擇出來新的個體里面的概率為c p 需要進(jìn)行基因重組，經(jīng)過重新組合產(chǎn)生下一代新個體，在交叉重組的過程中要盡量避免基因代碼差異較小的個體進(jìn)行交叉，防止“近親結(jié)合”，產(chǎn)生不良個體。假設(shè)交叉前兩個選擇出來的兩個較優(yōu)個體的編碼分別為：交叉

17、前個體A 的編碼：01001011001101010 交叉前個體B 的編碼：10011010011001101 從第16開始到第20位的基因值進(jìn)行基因重組，那么產(chǎn)生新的個體 A 和 B ，交叉后它們的編碼分別為：交叉后新的下一代個體 A 的編碼：01001011001001101交叉后新的下一代個體 B 的編碼：10011010011101010(6 變異變異則是從產(chǎn)生新一代的 A 和 B 個體集合中選擇很小一部分的個體(假設(shè)變異概率0.01m p = ，將個體的基因代碼的某一位或者某幾位值做改變（變異運算），將個體 A 第7位與第12位的基因值進(jìn)行基因變異，新的個體 A 變異前后后它的編碼分

18、別為 A 與 A ，在二進(jìn)制編碼中的實現(xiàn)方法一般是將基因鏈中的某些位取反而實現(xiàn)。變異前個體 A 的編碼：01001011001001101 變異后形成新的下一代個體 A 的編碼：01001001001101101進(jìn)行變異的目的是防止某些個體處于不變的狀態(tài)而失去一些較有用的基因，來參加變異的個體井岡山大學(xué)學(xué)報(自然科學(xué)版74的概率應(yīng)該很小，我們?nèi) m 。 (7 這樣循環(huán)迭代，直到迭代次數(shù)達(dá)到預(yù)定次數(shù)，或者群體的解達(dá)到最優(yōu)時，停止迭代。4 仿真實驗及算法性能分析4.1 環(huán)境及參數(shù)設(shè)置為了更好、更準(zhǔn)確的評價遺傳算法定位優(yōu)化的優(yōu)越性，在Matlab7.0環(huán)境下進(jìn)行仿真，遺傳算法的參數(shù)取值為: 種群規(guī)

19、模的初始值為100，交叉概率設(shè)置為6. 0=c p ，變異概率設(shè)置為01. 0=m p ，最大迭代次數(shù)設(shè)為100，編碼長度為10。從最優(yōu)值的變化以及定位誤差幾個方面來觀察遺傳算法的定位性能。4.2 仿真與結(jié)果分析 注：表示錨節(jié)點的位置，表示未知節(jié)點的估計位置，*表示未知節(jié)點的實際位置圖1 遺傳算法的定位結(jié)果Fig.1 The localization result of the Genetic Algorithm從圖1可以看出，遺傳定位算法的定位誤差較小，定位性能很好。從圖2可以看出，每個未知節(jié)點的最優(yōu)值隨迭代次數(shù)的增加而快速衰減，在迭代次數(shù)為30之后最優(yōu)值幾乎衰減為零，故迭代次數(shù)選擇30即滿

20、足定位誤差要求。圖2 五個未知節(jié)點的最優(yōu)值收斂圖Fig.2 The convergence figure of optimal value for fiveunknown nodes圖3 五個未知節(jié)點的定位誤差收斂圖Fig.3 The convergence figure of localization error for fiveunknown nodes從圖3可以看出每個未知節(jié)點的定位誤差隨迭代次數(shù)的增加而快速衰減，在迭代次數(shù)為10之后，定位誤差趨于穩(wěn)定，且定位誤差的值收斂于10%之下，表明遺傳算法的定位誤差很小，定位精度很高，能夠滿足無線傳感器節(jié)點的定位要求。5 結(jié)束語本文以最小二乘估計

21、法為基礎(chǔ)，闡述了一種基于遺傳算法的無線傳感網(wǎng)絡(luò)改進(jìn)定位算法的設(shè)計方案，建立了所有節(jié)點的定位誤差之和最小的數(shù)學(xué)模型，利用遺傳算法求解模型的最優(yōu)解，從而得到未知節(jié)點的最優(yōu)的估計位置。實驗仿真結(jié)果驗證了算法的有效性，表明該算法對未知節(jié)點的定位精度高，因此本算法具有較好的實用性，適合各種無線井岡山大學(xué)學(xué)報(自然科學(xué)版75傳感網(wǎng)絡(luò)節(jié)點的定位。 參考文獻(xiàn)：1 彭愛平, 郭曉松. 基于二次柵格掃描的無線傳感網(wǎng)絡(luò)定位算法J.傳感技術(shù)學(xué)報,2009,22 (11:1650-1654.2 Rabacy J J, Ammer M J, da Silva J r J L, et al PicorodioSupport

22、s Ad Hoc Ultra-low Power Wireless Networking J.Computer, 2000, 33 (7:42-48.3 KIM S, KO J G, YOON J, et alMultiple-objectivemetric for placing multiple base stations in wireless sensor networksA.Proc of the 2rd International Symposium on Wireless Pervasive Computing. Piscataway, USA, 2007:627-631.4 李

23、建中, 高宏. 無線傳感器網(wǎng)絡(luò)的研究進(jìn)展J.計算機(jī)研究與發(fā)展,2008,45(1:1-15.5 呂睿, 陽憲惠. 減少無線傳感器網(wǎng)絡(luò)節(jié)點定位誤差的方法J清華大學(xué)學(xué)報,2008，48(S2：1839-1843.6 X Li，H C Shi，Y Shang A sorted RSSI quantizationbased algorithm for sensor network localization The 11th Intl Conference on Parallel and Distributed Systems,Japan,2005.7 LUTHY K A,E GRANT D,HENDERSON T C.Leveraging RSSI for robotic repair of disconnected wireless sensor networksA.Proceedings of 2007 IEEE International Conference on Robotics and Automation.Rome, Italy, 2007:10-14.8 BENKIC K,MALAJNER M,PLANINSIC P, et al