基于混沌粒子群的WSN定位算法研究與matlab仿真

程 慶，張水鋒，陳 帥

（1.淮南師范學(xué)院 計算機學(xué)院；2.淮南師范學(xué)院 電子工程學(xué)院，安徽 淮南 232001）

無線傳感器網(wǎng)絡(luò)簡稱WSN，它是一個分布式傳感網(wǎng)絡(luò)，也是一個很多學(xué)科高度交叉的研究領(lǐng)域，更是目前最熱的研究領(lǐng)域之一，它的主要特點是動態(tài)性、可靠性、自組織和大規(guī)模等.現(xiàn)代無線傳感器網(wǎng)絡(luò)的發(fā)展離不開片上系統(tǒng)和傳感器技術(shù)的發(fā)展進步.人們信息獲取能力的提高離不開無線傳感器網(wǎng)絡(luò)的發(fā)展，通過無線傳感器網(wǎng)絡(luò)人們可以獲得最直接、最真實、最有效的信息.因此，無線傳感器網(wǎng)絡(luò)具有廣闊的應(yīng)用前景，在城市管理、軍事國防、生物醫(yī)療、工業(yè)控制、搶險救災(zāi)、環(huán)境監(jiān)測以及危險區(qū)域遠程控制等領(lǐng)域都得到廣泛的應(yīng)用.無線傳感器網(wǎng)絡(luò)由大量節(jié)點組成，它的三個要素是傳感器、感知對象和觀察者，它是一種由大量小型傳感器所組成的網(wǎng)絡(luò).這些小型傳感器一般稱作傳感器節(jié)點，這些節(jié)點通過一個或者幾個基站來收集數(shù)據(jù)[1].

1 無線傳感器網(wǎng)絡(luò)定位原理及基本概念

檢測、定位和通告是無線傳感器網(wǎng)絡(luò)進行目標跟蹤的三個階段.確定位置稱為定位，它是無線傳感器網(wǎng)絡(luò)的重要支撐技術(shù).自組織的網(wǎng)絡(luò)通過一些方式方法來確定節(jié)點的位置信息就是無線傳感器網(wǎng)絡(luò)定位.確定目標在系統(tǒng)中的位置與確定自己在系統(tǒng)中的位置是定位的兩個實際意義，也就是通常所說的節(jié)點自身定位與目標定位.確定節(jié)點的坐標位置的過程稱為節(jié)點自身定位，確定網(wǎng)絡(luò)覆蓋范圍內(nèi)目標的坐標位置的過程稱為目標定位[2].

在傳感器網(wǎng)絡(luò)定位中，可以把節(jié)點分為未知節(jié)點和信標節(jié)點，這種劃分的依據(jù)是節(jié)點自身的位置是否已經(jīng)知道.通過攜帶GPS定位設(shè)備等手段可以確定節(jié)點自身的位置，這種節(jié)點我們稱為信標節(jié)點beacon node or anchor node，它是未知節(jié)點的參考節(jié)點，在無線傳感器網(wǎng)絡(luò)中占的比例很小.沒有攜帶定位設(shè)備的節(jié)點我們稱為未知節(jié)點unknown node，也就是除了信標節(jié)點剩下的都是未知節(jié)點,通信半徑內(nèi)的其他節(jié)點是鄰居節(jié)點neighbor node.介紹了未知節(jié)點、信標節(jié)點和鄰居節(jié)點的概念，我們來看下跳數(shù)及距離的概念.兩個節(jié)點之間間隔的跳段總數(shù)稱為跳數(shù)Hop Count.兩個節(jié)點之間間隔的各跳段距離之和稱為跳段距離.協(xié)助傳感器節(jié)點定位的已知自身位置的固定設(shè)備稱為基礎(chǔ)設(shè)施.

2 無線傳感器網(wǎng)絡(luò)定位方法及分類

無線傳感器網(wǎng)絡(luò)常用的定位方法主要有：

2.1 三邊測量法

已知 A、B、C 三點的坐標為(xa,ya)、(xb,yb)、(xc,yc),未知節(jié)點D到它們的距離為da,db,dc,設(shè)D點坐標為（x，y）.可列出如下公式：

由公式1可以解出D節(jié)點的坐標為：

2.2 三角測量法

已知 A、B、C 三點的坐標為(xa,ya)、(xb,yb)、(xc,yc),未知節(jié)點D相對于它們的角度為∠ADB,∠ADC,∠BDC,設(shè)D點坐標為（x，y）.對于節(jié)點 A，C 和角∠ADC，如果弧段 AC 在△ABC內(nèi)，那么能夠唯一確定一個圓，設(shè)圓心為O1(xo1,yo1)，半徑為r1，那么 a=∠AO1C=(2π-2∠ADC),并可列出如下公式：

由公式2可以確定圓心O1點的坐標和半徑r1.同理對A,B,∠ADB和B,C,∠BDC分別確定相應(yīng)的圓心O2點的坐標、半徑r2、圓心O3點的坐標和半徑r3.最后利用三邊測量法，由點O1、O2、O3的坐標確定D點的坐標.

2.3 極大似然估計法

已知1,2,3,……,n等n個節(jié)點的坐標分別為(x1,y1),(x2,y2),(x3,y3), ……,(xn,yn),節(jié)點 D 到它們的距離分別為 d1，d2，d3，……，dn,設(shè) D 點坐標為（x，y）.可列出如下公式：

從第一個方程開始分別減去最后一個方程，得：

上式的線性方程表示方式為：AX=b,其中

使用標準的最小均方差估計方法可以得到X=(ATA)-1ATb即為節(jié)點D的坐標為[1].

無線傳感器網(wǎng)絡(luò)定位算法的分類方法有三種.第一種是基于測距Range-based和基于非測距range-free，第二種是遞增式和并發(fā)式，第三種是信標節(jié)點和無信標節(jié)點.第一種算法的劃分主要是根據(jù)是否測量距離，第二種算法的劃分是根據(jù)節(jié)點的測量發(fā)生，第三種算法的劃分是根據(jù)是否需要新標節(jié)點.

由于不需要額外配備測距設(shè)備，定位是通過計算跳數(shù)實現(xiàn)的，所以非測距定位更適合大規(guī)模的網(wǎng)絡(luò)部署.非測距定位的優(yōu)點是不需要額外的硬件設(shè)備，實現(xiàn)也相對容易；其缺點是比較依賴網(wǎng)絡(luò)連通度和節(jié)點部署密度，對于較大規(guī)模的網(wǎng)絡(luò)如果節(jié)點密度稀疏或分布不均，那么定位精度就會很低.非測距的定位算法，本文主要介紹三種，分別是質(zhì)心算法、DV-hop算法和APIT算法.

基于測距的定位算法主要有TOA，TDOA，AOA和RSSI算法等，通過這些算法可以得到距離信息或者角度信息.依據(jù)這些信息，再結(jié)合前面提到的質(zhì)心算法、三角測量法或者最大似然估計法來估計未知節(jié)點的位置.基于測距的定位算法的優(yōu)點是具有較高的定位精度，缺點是節(jié)點需要攜帶額外的測距設(shè)備，因此對于規(guī)模小且定位精度要求高的網(wǎng)絡(luò)比較適合這種算法.

3 混沌粒子群WSN定位算法原理

粒子群算法簡稱PSO算法，它是一種模擬鳥群隨機搜尋食物的方式，依據(jù)個體經(jīng)驗和群體經(jīng)驗進行的群體智能算法.粒子群算法的優(yōu)點是實現(xiàn)簡單，收斂速度快.所以在模擬識別、多目標優(yōu)化、神經(jīng)網(wǎng)絡(luò)以及控制決策等方向得到廣泛的應(yīng)用.PSO算法的原理是把網(wǎng)絡(luò)節(jié)點作為一組隨機粒子，再通過迭代方法求出最優(yōu)解.在每一次迭代中，粒子通過個體最優(yōu)解和全局最優(yōu)解更新其速度和位置[3].

設(shè)Ha=(ha1,ha2,……,haD)是第 a個粒子(a=1,2,……,s)的 D維位置，Va=(va1,va2,……,vab,……,vaD)是粒子a的飛行速度，Pa=(pa1,pa2,……,pab,……,paD)是粒子a的個體最優(yōu)解，Pg=(pg1,pg2,……,pgb,……,pgD)是整個種群的全局最優(yōu)解.在每次迭代中粒子的速度和位置用下面兩個式子來更新.

傳統(tǒng)PSO算法的缺點是易陷入局部極值點易早熟收斂，把混沌思想引入粒子群算法可以解決這個問題，基于混沌的粒子群算法又稱為CPSO算法.混沌理論是科學(xué)家在1975年提出來的，它在電路系統(tǒng)、保密通信及工程研究領(lǐng)域都得到了廣泛的應(yīng)用.混沌系統(tǒng)是一種復(fù)雜的非線性系統(tǒng)，它具有遍歷性、混合性及隨機性的特點.在物理學(xué)研究中經(jīng)常提到遍歷性的概念，在動力學(xué)系統(tǒng)中軌道具有回歸性就認為它具有遍歷性；若兩個子集A、B，他們出現(xiàn)的概率成績等于他們交集出現(xiàn)的概率，認為系統(tǒng)的混合的；隨機性比較復(fù)雜，一是系統(tǒng)時域的隨機混亂現(xiàn)象，二是系統(tǒng)長期不可預(yù)測性，三是系統(tǒng)頻域的寬帶白噪聲，四是自相關(guān)性隨著距離迅速衰減.混沌粒子群定位算法的原理如下.設(shè)在二維環(huán)境下未知節(jié)點i的估計坐標為 (xi,yi)與其鄰居瞄節(jié)點j通過RSSI測距技術(shù)得到的距離為di,j，適應(yīng)度函數(shù)表示式為f(xi,yi)，其中Bi為節(jié)點i鄰居瞄節(jié)點數(shù)目，(xi,j,yi,j)為節(jié)點i鄰居瞄節(jié)點j的坐標.算法的核心思想是求解使適應(yīng)度函數(shù)f值最小的解，并以此作為未知節(jié)點的最優(yōu)估計位置.

4 混沌粒子群定位算法的matlab仿真

對于混沌粒子群算法（CPSO）的定位算法，本文進行了仿真，結(jié)果如下.

5 小結(jié)

本文介紹了無線傳感器網(wǎng)絡(luò)定位的意義及混沌理論的原理，定位原理及基本概念，定位方法及分類，重點介紹了混沌粒子群算法的原理.由仿真結(jié)果可知混沌粒子群算法定位精度較高.傳統(tǒng)三邊測距法在錨節(jié)點較少時存在較大的平均定位誤差，而本文研究的CPSO定位算法有效降低了定位誤差.