引 言

節(jié)點(diǎn)的定位是無(wú)線傳感網(wǎng)應(yīng)用中的一個(gè)重要問(wèn)題，位置信息的引入使得WSN的輸出從單一的{數(shù)據(jù)}變?yōu)閧數(shù)據(jù)，位置}形式，使得使用者可以更有效的獲取特定位置和區(qū)域而不是特定傳感器結(jié)點(diǎn)的數(shù)據(jù)，從而為許多新型應(yīng)用如基于位置的路由、跟蹤、建筑物形變測(cè)量等應(yīng)用打開(kāi)了途徑。

無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位算法實(shí)現(xiàn)具備兩類輸入：已知錨點(diǎn)及其位置信息，結(jié)點(diǎn)之間的測(cè)量間距。

已知定位信息的節(jié)點(diǎn)被稱為錨點(diǎn)。未知節(jié)點(diǎn)與錨點(diǎn)之間的距離，按照實(shí)現(xiàn)方式不同，節(jié)點(diǎn)定位算法分為分布式和集中式兩類，前者的算法是通過(guò)分布式的各個(gè)節(jié)點(diǎn)實(shí)現(xiàn)的；后者的算法是通過(guò)一個(gè)集中式的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)的。本文采用集中式算法。

無(wú)線傳感網(wǎng)節(jié)點(diǎn)擺放完后就確定了錨點(diǎn)的信息，實(shí)現(xiàn)定位的另外一個(gè)輸入是各個(gè)節(jié)點(diǎn)距離信息。目前采用的測(cè)距方法有：測(cè)量無(wú)線電信號(hào)強(qiáng)度（RSSI），測(cè)量無(wú)線電信號(hào)覆蓋關(guān)系（Radio Connectivity），測(cè)量普通聲波與無(wú)線電到達(dá)時(shí)間差（TDOA），測(cè)量超聲波信號(hào)與無(wú)線電到達(dá)時(shí)間差。

本文采用RSSI方法來(lái)進(jìn)行節(jié)點(diǎn)之間的測(cè)距，實(shí)現(xiàn)簡(jiǎn)單，模型成熟，比TDOA等方法容易實(shí)現(xiàn)。

利用三角定位的原理，分析了定位與錨節(jié)點(diǎn)數(shù)量的關(guān)系，錨節(jié)點(diǎn)數(shù)量不足時(shí)，利用DV-hop算法計(jì)算多跳距離。錨點(diǎn)信息足夠時(shí)則采用最小二乘法對(duì)數(shù)據(jù)進(jìn)行處理以獲得平均意義上的節(jié)點(diǎn)位置。

無(wú)線傳感網(wǎng)中節(jié)點(diǎn)定位與實(shí)際節(jié)點(diǎn)定位信息存在一定誤差，產(chǎn)生誤差的原因有兩個(gè)：無(wú)線電信號(hào)傳播模型的不夠準(zhǔn)確，節(jié)點(diǎn)之間存在障礙物，節(jié)點(diǎn)擺放等環(huán)境因素影響。針對(duì)后者，本文提出了一個(gè)方法來(lái)預(yù)測(cè)節(jié)點(diǎn)之間是否存在障礙物，來(lái)改善節(jié)點(diǎn)定位精度。

最后用C語(yǔ)言進(jìn)行仿真，驗(yàn)證了考慮障礙物影響后，節(jié)點(diǎn)定位精度相比于沒(méi)有采用障礙物分析時(shí)提高了30％左右。

1、 定位原理

采用無(wú)線信號(hào)刪減模型進(jìn)行測(cè)距，其數(shù)學(xué)表達(dá)式為（1）：

式中：precieve為接收無(wú)線信號(hào)的強(qiáng)度，psend為無(wú)線節(jié)點(diǎn)發(fā)出信號(hào)的強(qiáng)度。

在信號(hào)強(qiáng)度刪減模型中，其指數(shù)a設(shè)定為2，忽略干擾，可得矩陣方程：

式中：X∈R2，是未知節(jié)點(diǎn)位置，ei∈R2是已知第i個(gè)錨點(diǎn)的位置，Zi是接收信號(hào)的強(qiáng)度，ai為常數(shù)。把式（2）展開(kāi)可得：

給定第i個(gè)錨點(diǎn)信息，X是一個(gè)二次未知數(shù)，這對(duì)解方程有一定難度，把其線性化，第i個(gè)方程減掉第1個(gè)方程可得：

給定k個(gè)錨點(diǎn)，可得k-1個(gè)線性方程。

通過(guò)上面的k-1個(gè)方程組可知，當(dāng)X有3個(gè)變量時(shí)，如X表示三維坐標(biāo)，k=4即k-1=3，可以得到唯一解；k《3時(shí)有多解；k》3時(shí)無(wú)解。當(dāng)X有2個(gè)變量，X代表二維坐標(biāo)，k=3有唯一解。

在無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位中，以二維定位為例，若未知節(jié)點(diǎn)知道3個(gè)錨點(diǎn)距離，可唯一定出該節(jié)點(diǎn)位置；若僅知道2個(gè)或更少錨點(diǎn)信息，可利用算法一定程度上定出位置范圍；若錨點(diǎn)距離信息多于3個(gè)，可用優(yōu)化算法來(lái)優(yōu)化定位精度。

本文以二維信息為例說(shuō)明無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位問(wèn)題。

2、 節(jié)點(diǎn)定位系統(tǒng)架構(gòu)與障礙物分析

無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位系統(tǒng)分為分布式和集中式兩種：

分布式算法將計(jì)算工作分布到各個(gè)節(jié)點(diǎn)中，節(jié)點(diǎn)的位置估計(jì)在本地完成。在非多跳方式中，算法使用的距離參數(shù)在節(jié)點(diǎn)一跳范圍內(nèi)取得；在多跳方式中，這個(gè)參數(shù)由節(jié)點(diǎn)間協(xié)作、多跳取得。

在集中式中，中心計(jì)算機(jī)負(fù)責(zé)計(jì)算每個(gè)節(jié)點(diǎn)位置，每個(gè)節(jié)點(diǎn)把自己的信息都統(tǒng)一發(fā)到某一中心節(jié)點(diǎn)，最后由這個(gè)中心節(jié)點(diǎn)傳到一計(jì)算機(jī)集中處理數(shù)據(jù)并給這些未知節(jié)點(diǎn)定位。見(jiàn)圖1。

集中式方法實(shí)現(xiàn)容易，考慮全局信息后能優(yōu)化節(jié)點(diǎn)定位。本文采用集中式定位算法。

2.1 集中式定位算法實(shí)現(xiàn)

采用集中式算法后，多跳范圍的節(jié)點(diǎn)與節(jié)點(diǎn)距離采用DV-hop算法，即平均每跳距離×跳數(shù)的方式。其實(shí)現(xiàn)過(guò)程如下。

2.1.1 平均每跳距離及錨點(diǎn)到未知節(jié)點(diǎn)跳數(shù)計(jì)算

分為2個(gè)階段，即2次廣播過(guò)程。

第一個(gè)階段，每個(gè)信標(biāo)節(jié)點(diǎn)采用廣播方式將其位置信息傳遞給其它的信標(biāo)節(jié)點(diǎn)。廣播的信息包格式為：{IDi，xi，yi，Hopsi}，其中包含了該節(jié)點(diǎn)的標(biāo)識(shí)位置坐標(biāo)IDi以及跳數(shù)Hopsi信息。初始Hopsi為1，接收到此數(shù)據(jù)的每個(gè)節(jié)點(diǎn)，將此信息記錄到一張表中。然后繼續(xù)向新的鄰居節(jié)點(diǎn)廣播，每廣播一次就將Hopsi加1。當(dāng)節(jié)點(diǎn)接收到一個(gè)相同ID的數(shù)據(jù)包時(shí)，便要與原來(lái)的Hopsi進(jìn)行比較，如果新的跳數(shù)小于原表中的跳數(shù)，就用新的跳數(shù)更新表中的跳數(shù)信息，意味著找到了一條更短的到達(dá)該信標(biāo)節(jié)點(diǎn)的路徑。如果新的跳數(shù)大于原表中的跳數(shù)，就丟棄該數(shù)據(jù)包，也不再進(jìn)行轉(zhuǎn)發(fā)。

經(jīng)過(guò)第一階段的廣播過(guò)程后，信標(biāo)節(jié)點(diǎn)也獲得其它所有信標(biāo)節(jié)點(diǎn)的坐標(biāo)及跳數(shù)距離，而且所有傳感器節(jié)點(diǎn)都已經(jīng)得到所有信標(biāo)節(jié)點(diǎn)的坐標(biāo)和跳數(shù)距離。這樣，每個(gè)信標(biāo)節(jié)點(diǎn)即可用式（8）計(jì)算出信標(biāo)節(jié)點(diǎn)i到其他信標(biāo)節(jié)點(diǎn)j的每跳平均間隔距離：

其中j是除i之外的所有其它信標(biāo)節(jié)點(diǎn)。

第二個(gè)階段，每個(gè)信標(biāo)節(jié)點(diǎn)將每跳平均距離傳送至中心計(jì)算機(jī)，數(shù)據(jù)包的格式為：{IDi，Ci}，Ci是該信標(biāo)節(jié)點(diǎn)到所有其它信標(biāo)節(jié)點(diǎn)的每跳平均距離。中心計(jì)算機(jī)就將所有信標(biāo)節(jié)點(diǎn)平均每跳距離相加取平均：

式中：n為所有信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。由此得到了全網(wǎng)所有信標(biāo)節(jié)點(diǎn)之間的每跳平均距離。各個(gè)節(jié)點(diǎn)也得到各個(gè)信標(biāo)節(jié)點(diǎn)的跳數(shù)。由此可計(jì)算出該節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離：Di=hops×cc。在圖2的示例中，節(jié)點(diǎn)0和5之間的距離，等于跳數(shù)5乘以cc。

2.1.2 節(jié)點(diǎn)定位

所有未知節(jié)點(diǎn)到錨點(diǎn)的距離算出后即可定位，分為3種情況：

（1） 未知節(jié)點(diǎn)與3個(gè)錨點(diǎn)距離已算出；

直接采用式（6），式（7）三角定位原理算出該節(jié)點(diǎn)位置。

（2） 未知節(jié)點(diǎn)與小于3個(gè)錨點(diǎn)距離已算出；

若有2個(gè)錨點(diǎn)距離算出，取該兩點(diǎn)線段中心作為該未知節(jié)點(diǎn)位置；若只有一個(gè)錨點(diǎn)距離算出，則以該錨點(diǎn)位置作為未知節(jié)點(diǎn)位置；若無(wú)錨點(diǎn)距離算出，以隨機(jī)經(jīng)驗(yàn)值分配該節(jié)點(diǎn)位置。

（3） 未知節(jié)點(diǎn)與大于3個(gè)錨點(diǎn)距離已算出；

利用最小二乘取這組錨點(diǎn)信息來(lái)估算未知節(jié)點(diǎn)位置，把式（5）化為式（10）：

2.2 誤差及障礙物分析

2.2.1 障礙物引起的誤差及障礙物預(yù)測(cè)方法

無(wú)線傳感網(wǎng)節(jié)點(diǎn)估算定位與實(shí)際節(jié)點(diǎn)位置之間存在誤差，產(chǎn)生誤差的原因有2個(gè)：（1）Rssi方法進(jìn)行測(cè)距時(shí)，無(wú)線信號(hào)刪減模型隨環(huán)境變化有所不同，這種模型不能很好的適應(yīng)實(shí)際情況，在對(duì)節(jié)點(diǎn)定位時(shí)會(huì)產(chǎn)生誤差；（2）實(shí)際環(huán)境中，節(jié)點(diǎn)與節(jié)點(diǎn)之間可能存在障礙物，導(dǎo)致此兩節(jié)點(diǎn)運(yùn)用RSSI測(cè)距得出的信號(hào)強(qiáng)度大大小于無(wú)障礙物時(shí)的情況。

本文采用RSSI方法來(lái)進(jìn)行節(jié)點(diǎn)之間的測(cè)距，節(jié)點(diǎn)間若存在障礙物，則測(cè)出的信號(hào)強(qiáng)度與實(shí)際節(jié)點(diǎn)之間的距離有很大偏差。

用算法預(yù)測(cè)障礙物的存在位置，把障礙物的影響考慮到節(jié)點(diǎn)定位中有助于節(jié)點(diǎn)定位精度。

本文提出一種預(yù)測(cè)障礙物的三角預(yù)測(cè)法，改進(jìn)由于節(jié)點(diǎn)之間存在障礙物引起的定位誤差（見(jiàn)圖3）。

在a，b，c 3個(gè)節(jié)點(diǎn)之間預(yù)測(cè)其中間有無(wú)障礙物，測(cè)得信號(hào)強(qiáng)度：

RSSab（a接收到b信號(hào)的強(qiáng)度），RSSac（a接收到c信號(hào)的強(qiáng)度），RSSbc（b接收到c信號(hào)的強(qiáng)度）。

l1=f（RSSab），a到b的距離；l2=f（RSSac），a到c的距離；l3=f（RSSbc），b到c的距離。

這樣可以估算出ab，ac，bc的長(zhǎng)度l1，l2，l3。

a，b，c都為一跳鄰居節(jié)點(diǎn)，相互靠的比較近，滿足三角形兩邊邊長(zhǎng)之和大于第三邊的定理。這里通過(guò)計(jì)算發(fā)現(xiàn)l1》l2+l3，即兩邊之和小于第三邊。則可預(yù)測(cè)a和b之間可能存在障礙物。

定位算法是一個(gè)需要迭代比較復(fù)雜的過(guò)程，運(yùn)用障礙物分析會(huì)使定位算法程序變得很復(fù)雜，一種好的解決方法是取少量可能存在障礙物的鄰居節(jié)點(diǎn)進(jìn)行障礙物分析，大多數(shù)都無(wú)需分析，這樣的節(jié)點(diǎn)對(duì)有以下特征：信號(hào)強(qiáng)度低于某一域值。

障礙物導(dǎo)致無(wú)線信號(hào)信息不可得，這種情況看作錨點(diǎn)與未知節(jié)點(diǎn)距離太遠(yuǎn)無(wú)法通信，本文考慮引入障礙物后無(wú)線信號(hào)強(qiáng)度減弱，仍可得到無(wú)線信號(hào)。

2.2.2 障礙物分析算法實(shí)現(xiàn)

本文的定位基本算法如3.1所述，在3.1的算法中，取得了未知節(jié)點(diǎn)到錨點(diǎn)的距離和計(jì)算未知之間插入障礙物分析，見(jiàn)圖3。

第一步，在取得i點(diǎn)與錨點(diǎn)j距離后，做循環(huán)搜索是否有m點(diǎn)同時(shí)與i和j點(diǎn)有距離信息，若有則進(jìn)入障礙物分析，否則退出。

第二步，根據(jù)i，j，m三點(diǎn)距離信息，利用3.2.1所述的障礙物分析算法判斷i和j之間是否有障礙物。

第三步，如有障礙物，則根據(jù)i節(jié)點(diǎn)信息作如下處理：（1）若i有3個(gè)以上錨點(diǎn)距離信息，則直接丟棄該j錨點(diǎn)的距離信息；（2）若i僅有3個(gè)及以下（包括該j節(jié)點(diǎn)）錨點(diǎn)距離信息，則i和j的距離取一個(gè)經(jīng)驗(yàn)值代替由于障礙物所得的距離值。

3 、仿真結(jié)果

采用C語(yǔ)言仿真，按照前面的算法進(jìn)行仿真。論證引入障礙物分析后定位精度的提高，仿真在50 m×50 m的區(qū)域內(nèi)進(jìn)行，錨節(jié)點(diǎn)為4～16個(gè)不等，節(jié)點(diǎn)通信距離為10 m，放置忽略厚度的障礙板8塊，每塊長(zhǎng)5 m。比較在有障礙物的情況下一般算法和引入障礙物分析算法后定位的精度（見(jiàn)圖4）。

4、 結(jié) 論

本文分析了定位算法理論，提出了定位算法需要解決的幾個(gè)關(guān)鍵問(wèn)題，提出了一個(gè)新的預(yù)測(cè)障礙物的算法，提高了節(jié)點(diǎn)定位的精度。采用C語(yǔ)言，通過(guò)仿真結(jié)果來(lái)論證引進(jìn)障礙物分析后定位精度的提高。

責(zé)任編輯：gt