引 言

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

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

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

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

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

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

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

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

1、 定位原理

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

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

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

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

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

給定k個錨點，可得k-1個線性方程。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中j是除i之外的所有其它信標節(jié)點。

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

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

2.1.2 節(jié)點定位

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

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

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

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

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

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

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

2.2 誤差及障礙物分析

2.2.1 障礙物引起的誤差及障礙物預測方法

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

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

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

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

在a，b，c 3個節(jié)點之間預測其中間有無障礙物，測得信號強度：

RSSab（a接收到b信號的強度），RSSac（a接收到c信號的強度），RSSbc（b接收到c信號的強度）。

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é)點，相互靠的比較近，滿足三角形兩邊邊長之和大于第三邊的定理。這里通過計算發(fā)現(xiàn)l1》l2+l3，即兩邊之和小于第三邊。則可預測a和b之間可能存在障礙物。

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

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

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

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

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

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

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

3 、仿真結(jié)果

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

4、 結(jié) 論

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

責任編輯：gt