預(yù)測障礙物的算法解決方案提高節(jié)點(diǎn)定位的精度

引 言

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

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

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

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

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

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

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

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

1、 定位原理

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

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

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

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

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

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

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

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

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

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

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

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

在集中式中，中心計算機(jī)負(fù)責(zé)計算每個節(jié)點(diǎn)位置，每個節(jié)點(diǎn)把自己的信息都統(tǒng)一發(fā)到某一中心節(jié)點(diǎn)，最后由這個中心節(jié)點(diǎn)傳到一計算機(jī)集中處理數(shù)據(jù)并給這些未知節(jié)點(diǎ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)過程如下。

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

分為2個階段，即2次廣播過程。

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

經(jīng)過第一階段的廣播過程后，信標(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ù)距離。這樣，每個信標(biāo)節(jié)點(diǎn)即可用式（8）計算出信標(biāo)節(jié)點(diǎn)i到其他信標(biāo)節(jié)點(diǎn)j的每跳平均間隔距離：

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

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

式中：n為所有信標(biāo)節(jié)點(diǎn)的個數(shù)。由此得到了全網(wǎng)所有信標(biāo)節(jié)點(diǎn)之間的每跳平均距離。各個節(jié)點(diǎn)也得到各個信標(biāo)節(jié)點(diǎn)的跳數(shù)。由此可計算出該節(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個錨點(diǎn)距離已算出；

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

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

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

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

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

2.2 誤差及障礙物分析

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

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

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

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

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

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

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

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

這樣可以估算出ab，ac，bc的長度l1，l2，l3。

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

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

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

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

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

第一步，在取得i點(diǎn)與錨點(diǎn)j距離后，做循環(huán)搜索是否有m點(diǎn)同時與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個以上錨點(diǎn)距離信息，則直接丟棄該j錨點(diǎn)的距離信息；（2）若i僅有3個及以下（包括該j節(jié)點(diǎn)）錨點(diǎn)距離信息，則i和j的距離取一個經(jīng)驗(yàn)值代替由于障礙物所得的距離值。

3 、仿真結(jié)果

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

4、 結(jié) 論

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

責(zé)任編輯：gt