程 慶，張水鋒，陳 帥

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

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

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

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

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

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

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

2.1 三邊測(cè)量法

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

由公式1可以解出D節(jié)點(diǎn)的坐標(biāo)為：

2.2 三角測(cè)量法

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

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

2.3 極大似然估計(jì)法

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

從第一個(gè)方程開(kāi)始分別減去最后一個(gè)方程，得：

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

使用標(biāo)準(zhǔn)的最小均方差估計(jì)方法可以得到X=(ATA)-1ATb即為節(jié)點(diǎn)D的坐標(biāo)為[1].

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

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

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

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

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

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

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

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

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

5 小結(jié)

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