基于遺傳算法的井下無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究

1、收稿日期:2010-01-08作者簡(jiǎn)介:陳 坤(1985- , 男, 安徽阜陽(yáng)人, 2008年畢業(yè)于安徽理工大學(xué)電氣與信息工程學(xué)院電子信息工程專(zhuān)業(yè)?；谶z傳算法的井下無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究陳 坤, 李 莉, 李繼云, 梁美玉(安徽理工大學(xué)電氣與信息工程學(xué)院, 安徽 淮南 232001摘 要:為了進(jìn)一步提高井下無(wú)線(xiàn)傳感器網(wǎng)絡(luò)待測(cè)節(jié)點(diǎn)定位精度, 文章提出了將節(jié)點(diǎn)定位算法和遺傳算法結(jié)合在一起的基于遺傳算法的節(jié)點(diǎn)定位算法, 通過(guò)迭代尋優(yōu), 提高定位精度。該算法是一種基于距離的三邊測(cè)量定位算法, 根據(jù)待測(cè)節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離推測(cè)出待測(cè)節(jié)點(diǎn)的坐標(biāo)。實(shí)驗(yàn)結(jié)果表明, 該算法具有更高的定位精度。關(guān)鍵詞:無(wú)線(xiàn)

2、傳感器網(wǎng)絡(luò); 節(jié)點(diǎn)定位; 遺傳算法中圖分類(lèi)號(hào):TD655 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1671-0959(2010 10-0120-03W ireless Sensor Net work Nodes LocalizationM ethodof Underground CoalM ines based on G enetic A lgorith mL I L , i L I J i -yun , CHEN Kun , L I ANG M e i-yu(S chool of E lectrical and I n for m ation Eng i neeri ng , Anhu iUn ivers

3、 i ty of S ci en ce and Technol ogy , H uai n an Anhu i 232001Abstrac t :T o f urther enhance the l ocation prec isi on of unknown nodes i n w ireless sensor net w orks , a locati on m e t hodbased on genetic a l gor it hm i s presented :the comb i nation o fw ire less senso r net wo rk and genetic

4、a l gor ith m 1It can i m provepositi on i ng accuracy t hrough iterative opti m izati on 1T he m et hod is dependent on d i stance , wh i ch can g et the coo rdina tes of the unkno w n node t hrough the d i stance o f unknown node and known node 1F i na ll y, the resu lt is better 1K eywords :W S N

5、 s , N ode l o ca ti on , GA 由于礦井作業(yè)工作環(huán)境惡劣, 為了確保井下人員的安全, 在出現(xiàn)安全事故時(shí)實(shí)施及時(shí)有效的撤退搜救, 對(duì)井下人員的定位無(wú)疑成為重要的研究議題。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(W i re l ess Sensor N et wo rks , W S N s 就是由部署在監(jiān)測(cè)區(qū)內(nèi)大量的廉價(jià)傳感器節(jié)點(diǎn)組成的集傳感器技術(shù)、嵌入式計(jì)算技術(shù)、分布式信息處理技術(shù)和無(wú)線(xiàn)通信技術(shù)于一體, 通過(guò)傳感器與外界交互, 完成數(shù)據(jù)采集、處理及通信等功能, 具有分布協(xié)作性, 測(cè)量精度高, 范圍廣, 操作靈活和智能性的優(yōu)點(diǎn)1, 2, 而定位作為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一應(yīng)用于井下人員定

6、位、跟蹤, 即在井下人員身上攜帶有效的傳感器節(jié)點(diǎn), 通過(guò)對(duì)節(jié)點(diǎn)的定位確定人員位置, 從而實(shí)現(xiàn)對(duì)井下作業(yè)人員的監(jiān)控。目前, 低成本、高能效、高精度的距離測(cè)量技術(shù)已成為節(jié)點(diǎn)定位技術(shù)的重要研究方向之一。1 井下無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位描述根據(jù)有限個(gè)已知位置的節(jié)點(diǎn)來(lái)確定部署區(qū)中其他位置節(jié)點(diǎn)的位置。在部署區(qū)內(nèi)的所有傳感器節(jié)點(diǎn)分為兩類(lèi):一類(lèi)是已知位置的參考節(jié)點(diǎn), 稱(chēng)為信標(biāo)節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)的數(shù)量很少, 由于信標(biāo)節(jié)點(diǎn)位置既定, 可作為參考節(jié)點(diǎn)通過(guò)一定的定位算法協(xié)助確定未知節(jié)點(diǎn)的位置; 另一類(lèi)則是待測(cè)的未知節(jié)點(diǎn)。在定位算法中, 根據(jù)定位的機(jī)制不同一般可分為:基于測(cè)距的定位算法和非基于測(cè)距的定位算法。非基于定位算法是

7、利用節(jié)點(diǎn)的連通性和多跳路由信息交換等方法估算節(jié)點(diǎn)的距離或角度, 完成位置估計(jì)。該算法雖然成本低效率高但其對(duì)節(jié)點(diǎn)密度的要求高, 而且定位精度相對(duì)較低, 因此本文選擇基于測(cè)距的定位方法?；跍y(cè)距的定位算法是通過(guò)對(duì)節(jié)點(diǎn)間的距離或角度的測(cè)量信息實(shí)現(xiàn)定位, 包括測(cè)距和定位兩個(gè)階段, 而測(cè)距常用的方法有測(cè)量到達(dá)時(shí)間(TOA 、到達(dá)時(shí)間差(TDOA 、接收信號(hào)強(qiáng)度指示器(RSS I 以及相位和編碼測(cè)量等, 前兩種方法定位精度較高, 是利用信號(hào)傳輸?shù)暮臅r(shí)測(cè)量信標(biāo)節(jié)點(diǎn)和待測(cè)節(jié)點(diǎn)的距離。三邊測(cè)量法2, 3是待測(cè)節(jié)點(diǎn)接收到3個(gè)以上信標(biāo)節(jié)點(diǎn)發(fā)送的信息即可獲得到各個(gè)信標(biāo)節(jié)點(diǎn)之間的距離, 從而實(shí)現(xiàn)對(duì)自身的定位。該算法實(shí)現(xiàn)

8、了基于測(cè)距定位的第二個(gè)階段:定位。算法要求部署的定位系統(tǒng)內(nèi)包含多個(gè)已知參考節(jié)點(diǎn),3信息工程 煤 炭 工 程 2010年第10期個(gè)節(jié)點(diǎn)即可確定待測(cè)節(jié)點(diǎn)的位置, 如圖1a 所示, A 、B 、C 是已知位置的信標(biāo)節(jié)點(diǎn), 由A 發(fā)出的信號(hào)可知:待測(cè)節(jié)點(diǎn)位于以A 為圓心測(cè)量距離為半徑的圓周上, 同理, 待測(cè)節(jié)點(diǎn)也應(yīng)在以B 、C 為圓心測(cè)量距離為半徑的圓周上, 故理論上3個(gè)圓的交點(diǎn)即為待測(cè)節(jié)點(diǎn)的預(yù)測(cè)位置。然而實(shí)際的定位系統(tǒng)中3個(gè)圓并不一定相交于同一點(diǎn), 進(jìn)而出現(xiàn)了如圖1b 的定位效果, 為了獲得更精確的位置定位, 將采用遺傳算法應(yīng)用 于定位算法中縮小陰影區(qū)以求獲得更精確的定位。圖1 三邊測(cè)量情況綜上所述

9、, 為獲得較精確的監(jiān)控井下人員的位置, 以確保事故時(shí)井下人員的快速撤離和搜救, 本文選擇基于TOA 的測(cè)距算法并采用基于遺傳算法優(yōu)化的三邊測(cè)量法定位獲得較精確的待測(cè)節(jié)點(diǎn)位置。2 遺傳優(yōu)化算法簡(jiǎn)介遺傳算法簡(jiǎn)稱(chēng)GA (G ene ti c A lgor it h m 是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法4, 5。遺傳算法一般由編碼、適應(yīng)值函數(shù)、遺傳算子、參數(shù)控制等四個(gè)部分組成。遺傳算法首先選取一個(gè)由N 個(gè)編碼過(guò)的個(gè)體組成的種群, 對(duì)種群進(jìn)行初始化; 種群根據(jù)適應(yīng)度函數(shù)選擇選擇適應(yīng)度大的個(gè)體, 并借助遺傳算子進(jìn)行選擇、交叉和變異, 逐代進(jìn)化以產(chǎn)生新的個(gè)體。再反

10、復(fù)進(jìn)化, 得到基因型的最優(yōu)解。遺傳算法中的控制參數(shù):基因編碼長(zhǎng)度、種群個(gè)數(shù)、交叉概率、變異概率、最大遺傳代數(shù)等6。1 基因編碼采用二進(jìn)制或?qū)崝?shù)編碼, 本文選用10位二進(jìn)制數(shù)編碼。2 種群個(gè)數(shù)越多越利于求的全局最優(yōu)解, 但要兼顧考慮計(jì)算效率適當(dāng)選擇。3 交叉概率要大些, 尋優(yōu)搜索過(guò)程主要通過(guò)它來(lái)實(shí)現(xiàn), 一般選取014019之間。4 變異概率發(fā)生的概率比較小, 取01001011之間。遺傳算法應(yīng)用在井下定位的優(yōu)越性:無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)多, 分布區(qū)域廣; 井下環(huán)境復(fù)雜, 節(jié)點(diǎn)布設(shè)隨機(jī), 通信約束多, 由此建立的定位函數(shù)將會(huì)是多目標(biāo)的多約束的復(fù)雜非線(xiàn)性方程, 而遺傳算法的應(yīng)用條件簡(jiǎn)單, 與問(wèn)題無(wú)關(guān),

11、并行搜索計(jì)算能力強(qiáng)的特點(diǎn)特別適合無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位優(yōu)化函數(shù)的求解要求7。3 定位算法實(shí)現(xiàn)本文基于TOA 的測(cè)距:信號(hào)從發(fā)送節(jié)點(diǎn)傳遞到接收節(jié)點(diǎn), 而后接收節(jié)點(diǎn)回發(fā)送信號(hào)作為響應(yīng), 通過(guò)/握手0, 如圖2所示, 發(fā)送節(jié)點(diǎn)即能從時(shí)間延遲中推斷出距離:(T3-T 0 -(T2-T 1 V 2(1式中, V 代表信號(hào)的傳遞速度。這種測(cè)量方法的誤差主要來(lái)源于信號(hào)處理的時(shí)間(即T 2-T 1, 所以此方法對(duì)硬件的要求較高4 。圖2 TOA 測(cè)量圖三邊測(cè)量法定位:假設(shè)3個(gè)信標(biāo)節(jié)點(diǎn)A 、B 、C 分別位于(X A , Y A , (X B ,Y B ,(X C , Y C , 則誤差函數(shù)如下所示:D x,

12、y=|(x -x A +(y -y A -r A |(x -x B +(y -y B -r B |C C -r C |(2式中, 當(dāng)誤差函數(shù)D x, y 取最小值時(shí), 其對(duì)應(yīng)的待測(cè)節(jié)點(diǎn)(x, y 越接近真實(shí)值,r A 、r B 、r C 為信標(biāo)節(jié)點(diǎn)到待測(cè)節(jié)點(diǎn)的距離。理想的三邊測(cè)量法可將待測(cè)節(jié)點(diǎn)定位于一點(diǎn), 但是實(shí)際測(cè)量結(jié)果卻是如圖1b 所示的陰影部分, 為了提高定位精度, 盡可能縮小陰影部分甚至于收斂于一點(diǎn), 采用遺傳迭代算法優(yōu)化誤差函數(shù)獲取誤差的最小值, 從而得到待測(cè)節(jié)點(diǎn)更精確的位置。4 實(shí)驗(yàn)仿真為了檢驗(yàn)改進(jìn)后算法的性能, 利用M ATLA B710進(jìn)行仿真驗(yàn)證。定義3個(gè)已知的信標(biāo)節(jié)點(diǎn)A (

13、200, 0 、B (0, 0 、C(0, 200 三點(diǎn)坐標(biāo), 將未知節(jié)點(diǎn)的位置設(shè)在(100,100處, 則r A =14114,r B =14114,r C =14114。遺傳算法中參數(shù)設(shè)定迭代次數(shù)n =200, 交叉概率p c =016, 變異概率p m =01001, 算法程序中變量采用10位二進(jìn)制編碼串表示69。同時(shí), 為了提高個(gè)體的進(jìn)化速度, 對(duì)遺傳優(yōu)化算法進(jìn)行了一定的改進(jìn), 即采用最優(yōu)個(gè)體保優(yōu)原則, 將每一代的所有個(gè)體按序排列后, 最優(yōu)的5個(gè)個(gè)體不再經(jīng)歷交叉、變異運(yùn)算, 而是直接遺傳到下一代, 進(jìn)而減少了迭代次數(shù), 節(jié)省了算法運(yùn)行時(shí)間, 實(shí)現(xiàn)更快速的迭代尋優(yōu)。試驗(yàn)中, 信標(biāo)節(jié)點(diǎn)A

14、、B 、C 均向待測(cè)節(jié)點(diǎn)發(fā)送信號(hào), 記錄時(shí)間T 0; 待測(cè)節(jié)點(diǎn)接收信號(hào)后分別回發(fā)送信號(hào), 待3個(gè)信標(biāo)節(jié)點(diǎn)接收到待測(cè)節(jié)點(diǎn)回發(fā)的信號(hào)后, 記錄時(shí)間T 3; 信號(hào)處理時(shí)間忽略不計(jì)。利用式(1 處理計(jì)算后獲得與待測(cè)節(jié)點(diǎn)的距離, 然后通過(guò)三邊測(cè)量法計(jì)算并由遺傳算法優(yōu)化2010年第10期 煤 炭 工 程 信息工程后得到待測(cè)節(jié)點(diǎn)的定位位置。對(duì)比已設(shè)定的待測(cè)節(jié)點(diǎn)實(shí)際位置, 觀(guān)察基于遺傳優(yōu)化算法的定位精度效果。如圖3、4所示為迭代200次的待測(cè)節(jié)點(diǎn)的x, y 軌跡, 最終循環(huán)迭代終止后x =10012933, y =10110753, 與預(yù)先設(shè)定的坐標(biāo)(100, 100 比較可知基于遺傳算法的節(jié)點(diǎn)定位方法具有較

15、好的定位效果。同時(shí), 為了評(píng)價(jià)算法性能, 給出了誤差函數(shù)的仿真結(jié)果圖, 如圖5所示, 迭代終止后Dx, y=010468。另外, 為了更好的說(shuō)明該定位算法的性能, 在不同的測(cè)距誤差、節(jié)點(diǎn)密度條件下進(jìn)行多次仿真實(shí)驗(yàn)。選取二維區(qū)域100100內(nèi)隨機(jī)設(shè)置信標(biāo)節(jié)點(diǎn)和待測(cè)節(jié)點(diǎn), 在測(cè)距誤差分別為5%, 10%, 15%, 20%, 25%, 30%條件下, 測(cè)定信標(biāo)節(jié)點(diǎn)密度分別為10%, 20%, 30%時(shí)7, 依據(jù)數(shù)據(jù)得出節(jié)點(diǎn)的定位誤差的變化趨勢(shì)如圖6 所示。圖6定位誤差分析圖5結(jié)語(yǔ)本文采用了基于遺傳算法的井下無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法, 即用遺傳算法優(yōu)化三邊測(cè)量法, 文中詳細(xì)說(shuō)明了優(yōu)化的理論思想,

16、 給出了MAT LAB710仿真出的定位效果圖及誤差分析圖, 可以看出該定位方法的可靠性和有效性。由于此定位方法是基于TOA 測(cè)距的, 一般的方法是采用超聲波信號(hào)傳送, 節(jié)點(diǎn)上還需裝有超聲波發(fā)送、接收裝置, 且由于井下環(huán)境復(fù)雜, 而超聲波信號(hào)易被障礙物阻擋, 以至于會(huì)產(chǎn)生較大的誤差, 為了更有效的降低誤差, 節(jié)點(diǎn)可采用射頻發(fā)送, 射頻信號(hào)在一定頻率下可穿透障礙物, 依據(jù)傳感器節(jié)點(diǎn)功耗低、成本低、體積小等硬件限制條件, 應(yīng)用中硬件可選用Chipcon 公司的射頻收發(fā)器CC2430芯片, 該芯片集成有射頻發(fā)生器, 還有增強(qiáng)型的8051M C U, 具有強(qiáng)大的魯棒射頻和數(shù)據(jù)處理功能, 其優(yōu)良的無(wú)線(xiàn)接收靈敏度和強(qiáng)大的抗干擾性有利于井下復(fù)雜環(huán)境的應(yīng)用。另外, CC2430的休眠模式和主動(dòng)模式時(shí)的短時(shí)間有效的降低了功耗, 保證了電池的較長(zhǎng)壽命, 從而實(shí)現(xiàn)簡(jiǎn)單、快速、長(zhǎng)時(shí)間的井下定位方案8。參考文獻(xiàn):1王曉樂(lè), 徐家品. 基于粒子群優(yōu)化算法的W SN s 節(jié)點(diǎn)定位研究J.計(jì)算機(jī)應(yīng)用, 2009, 29(2:494499.2王雪. 無(wú)線(xiàn)傳感網(wǎng)絡(luò)測(cè)量系統(tǒng)M.北京:機(jī)械工業(yè)出版社, 2007.3熊小華, 何通能, 徐中勝, 等. 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究綜述J.機(jī)電工程, 2009, 26(2:1317. 4陳國(guó)良, 王