無線傳感器網(wǎng)絡(luò)的許多應(yīng)用要求節(jié)點(diǎn)知道自身的位置信息，才能向用戶提供有用的檢測服務(wù)。沒有節(jié)點(diǎn)位置信息的監(jiān)測數(shù)據(jù)在很多場合下是沒有意義的。比如，對于森林火災(zāi)檢測、天然氣管道監(jiān)測等應(yīng)用，當(dāng)有事件發(fā)生時，人們關(guān)心的一個首要問題就是事件發(fā)生在哪里，此時如果只知道發(fā)生了火災(zāi)卻不知道火災(zāi)具體的發(fā)生地點(diǎn)，這種監(jiān)測沒有任何實(shí)質(zhì)的意義，因此節(jié)點(diǎn)的位置信息對于很多場合是至關(guān)重要的。

在許多場合下，傳感器節(jié)點(diǎn)被隨機(jī)部署在某個區(qū)域，節(jié)點(diǎn)事先無法知道自身的位置，因此需要在部署后通過定位技術(shù)來獲取自身的位置信息。目前最常見的定位技術(shù)就是GPS（Global Positioning System）了，它能夠通過衛(wèi)星對節(jié)點(diǎn)進(jìn)行定位，并且能夠達(dá)到比較高的精度。因此要想對傳感器節(jié)點(diǎn)進(jìn)行定位，最容易想到的方法就是給每個節(jié)點(diǎn)配備一個GPS接收器，但是這種方法不適用于傳感器網(wǎng)絡(luò)，主要原因有以下幾點(diǎn)：

1）GPS接收器通常能耗高，而對于無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)來說，一般能耗很有限，給每個節(jié)點(diǎn)配備一個GPS接收器會大大縮短網(wǎng)絡(luò)壽命；

2）GPS接收器成本比較高，給無線傳感器網(wǎng)絡(luò)中的每個節(jié)點(diǎn)配備一個GPS接收器，需要投入很大成本，尤其對于大規(guī)模的無線傳感器網(wǎng)絡(luò)來說不是很適合；

因此有必要研究適合無線傳感器網(wǎng)絡(luò)的定位技術(shù)。下面分兩個部分來介紹節(jié)點(diǎn)定位的相關(guān)研究：1）節(jié)點(diǎn)定位的基本概念；2）節(jié)點(diǎn)定位的基本思路；3）常見算法。

一.節(jié)點(diǎn)定位的基本概念

無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)定位是指傳感器節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)中少數(shù)已知節(jié)點(diǎn)的位置信息，通過一定的定位技術(shù)確定網(wǎng)絡(luò)中其他節(jié)點(diǎn)的位置信息的過程。

在無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)通?？梢苑譃樾艠?biāo)節(jié)點(diǎn)（beacon node or anchor node）和未知節(jié)點(diǎn)（unknown node），其中信標(biāo)節(jié)點(diǎn)也稱為錨節(jié)點(diǎn)或者參考點(diǎn)，未知節(jié)點(diǎn)也稱為普通節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)是位置信息已知的節(jié)點(diǎn)，未知節(jié)點(diǎn)是未知信息未知的節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)一般所占比例很小，通常通過手工配置或者配備GPS接收器來獲取自身的位置信息。

除此之外還有一種節(jié)點(diǎn)稱為鄰居節(jié)點(diǎn)（neighbor node），鄰居節(jié)點(diǎn)是指傳感器節(jié)點(diǎn)通信半徑內(nèi)的其他節(jié)點(diǎn)。

以下是幾個常用術(shù)語：

到達(dá)時間（Time of Arrvial，TOA），信號從一個節(jié)點(diǎn)傳播到另一個節(jié)點(diǎn)所需時間

到達(dá)時間差（Time Diffrential of Arrival，TDOA），不同傳播速度的信號從一個節(jié)點(diǎn)到達(dá)另一個基點(diǎn)所需要的時間之差

到達(dá)角度（Angle of Arrival，AOA），節(jié)點(diǎn)接收到的信號相對于自身軸線的角度

接收信號強(qiáng)度（Received Sinnal Strength，RSS），節(jié)點(diǎn)接收到無限信號強(qiáng)度的大小，也有稱Received Sinnal Strength Indicator（RRSI），兩個意思基本是一樣的

視距關(guān)系（Light of Sight，LOS），兩個節(jié)點(diǎn)之間沒有障礙物，能夠直接通信

非視距關(guān)系（Non Light of Sight，NLOS），兩個節(jié)點(diǎn)之間有障礙物，不能直接通信

跳數(shù)（Hop Count），兩個節(jié)點(diǎn)之間的跳段之和

二.節(jié)點(diǎn)定位技術(shù)的基本思路

節(jié)點(diǎn)定位的基本思路主要有兩種：

1.基于測距（Range-based）：假設(shè)在傳感器網(wǎng)絡(luò)中某些節(jié)點(diǎn)位置信息已知，通過某些手段來估算其他節(jié)點(diǎn)的位置信息。在這里面通常有兩個步驟：

測距

位置估算

因為要通過信標(biāo)節(jié)點(diǎn)得到未知節(jié)點(diǎn)的位置信息，必須先確定信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離，才能得到未知節(jié)點(diǎn)的位置信息。舉個例子說明一下：

假如信標(biāo)節(jié)點(diǎn)A位置已知為（x1，y1），節(jié)點(diǎn)M位置未知，要想求得M的位置，最簡單的想法：假設(shè)B位置為（x，y），A到B的距離為d1，則有

d12=（x-x1）2+（y-y1）2

顯然只根據(jù)一個方程這樣是無法求得x和y的值，假若有兩個信標(biāo)節(jié)點(diǎn)呢？

這樣一來的話又多了一個方程：d22=（x-x2）2+（y-y2）2，此時可以解得方程組得到x和y，但是此時x和y是有兩組解的，無法唯一確定x和y的值，因此需要考慮再假如一個信標(biāo)節(jié)點(diǎn)：

這樣一來的話就可以唯一確定x和y的值了，最基本的定位思想就是這樣。這里舉的例子是采用距離，還可以采用角度。

一般情況最少需要知道未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)的三組距離或角度值，然后再通過位置估算方法確定位置。

通常測距的方法有4種：

1）基于到達(dá)時間（TOA）的測距

這種方法是根據(jù)已知信號的傳播速度及信號在發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的傳播時間來估算距離，這種方法要求能夠非常精確地獲取發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的傳播時延，這個是比較困難的，難度很大，不太適合無線傳感器網(wǎng)絡(luò)。

2）基于到達(dá)時間差（TDOA）的測距

這種方法中發(fā)送節(jié)點(diǎn)同時發(fā)送兩種不同傳播速度的信號、接收節(jié)點(diǎn)根據(jù)兩種信號到達(dá)的時間差和他們的傳播速度來計算距離。假若兩種信號的傳寶速度為v1和v2，到達(dá)時間分別為t1和t2，發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)的距離為d，則有：

t1-t2=d/v1-d/v2

可得d=（t1-t2）v1v2/（v2-v1）

3）基于到達(dá)角度（AOA）的測距

這種方法根據(jù)接收信號到達(dá)時候與自身軸線的角度來計算，這種方法對硬件成本要求很高，要求配備天線陣列，不太適合無線傳感器網(wǎng)絡(luò)

4）基于接收信號強(qiáng)度（RSS）的測距

信號在傳播過程中會有衰減，無線信號的發(fā)射功率和接收功率存在某種映射關(guān)系，因此可以利用關(guān)系這個來估算距離，

在獲得了距離之后，就可以來估算位置了，常用的位置估算方法有下面兩種：

1）三邊測量法

上面舉的例子中的位置估算方法就是三邊測量法，此處不再贅述。

至于某些文獻(xiàn)上提到的三角測量法個人覺得跟三邊測量法是一回事，就不再介紹了。

3）最大似然估計法

已知n個節(jié)點(diǎn)的坐標(biāo)為（x1，y1），（x2，y2）......（xn，yn），它們到未知節(jié)點(diǎn)M的距離分別為d1，d2......dn，則有：

（x-x1）2+（y-y1）2=d12

（x-x2）2+（y-y2）2=d22

......

（x-xn）2+（y-yn）2=dn2

依次用第一個方程減去最后一個方程，可得：

x12-xn2+y12-yn2+dn2-d12=2x(x1-xn)+2y(y1-yn)

......

xn-12-xn2+yn-12+dn2-dn-12=2x(xn-1-xn)+2y(yn-1-yn)

則可以表示成?AX?=?B

其中A =?

B=

X =（x,y)T

2.無需測距（range-free）

無需測距的方法一般是利用網(wǎng)絡(luò)連通性或者拓?fù)浣Y(jié)構(gòu)來估算距離，再利用三邊測量法或者極大似然估計來估算位置。

三.常見算法

1.基于測距（range-based）

1）AHLos 算法?

該算法是基于到達(dá)時間差的測距，信標(biāo)節(jié)點(diǎn)首先向鄰居節(jié)點(diǎn)以兩種射頻信號來廣播消息，然后鄰居節(jié)點(diǎn)根據(jù)到達(dá)時間差來估算距離，在接收到三個信標(biāo)節(jié)點(diǎn)的消息之后，則根據(jù)三邊測量法估算位置，鄰居節(jié)點(diǎn)確定自己的位置之后轉(zhuǎn)變?yōu)樾艠?biāo)節(jié)點(diǎn)，也向鄰近節(jié)點(diǎn)廣播消息重復(fù)上述過程直至所有節(jié)點(diǎn)定位完成。

2）RADAR算法

該算法是基于RSS的測距，而基于RSS測距該算法有兩種模型：經(jīng)驗?zāi)Ｐ秃托盘杺鞑ツＰ?/p>

先說一下經(jīng)驗?zāi)Ｐ停?/p>

在經(jīng)驗?zāi)Ｐ椭校?jié)點(diǎn)被分散在一定的區(qū)域內(nèi)，并且保證所有的未知節(jié)點(diǎn)能夠與信標(biāo)節(jié)點(diǎn)直接通信，如圖所示。然后事先在該區(qū)域內(nèi)采集一些位置進(jìn)行RSS強(qiáng)度測試，并以（x，y，RSS）的形式記錄到數(shù)據(jù)庫中。當(dāng)進(jìn)行定位時，未知節(jié)點(diǎn)同數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行比對，選擇差值最小的三個或者三個以上點(diǎn)作為估算位置，然后再采用三邊測量法或者下文的質(zhì)心法來估算位置。

信號傳播模型：

信號傳播模型主要有兩種模型：自由空間模型和shadowing模型

自由空間模型假定信號發(fā)射功率和信號接收功率存在確定的映射關(guān)系：?

其中PR是接收處的功率，PS是發(fā)射處的功率，d是發(fā)射點(diǎn)距接收點(diǎn)的距離，α是傳播因子，視環(huán)境而定。

shadowing模型：

其中P（d）是未知節(jié)點(diǎn)處的信號強(qiáng)度或者信號發(fā)射功率，P（d0）是距信標(biāo)節(jié)點(diǎn)或者基站d0處的信號發(fā)射功率（其中d0是參考距離，一般取1m），n是衰減因子，由于實(shí)際環(huán)境中存在噪聲，所以引入了?，比如在室內(nèi)傳播，會有墻壁或者門這些障礙物，就需要計算?。

2.無需測距（range-free）

無需測距的定位算法不需要直接測量節(jié)點(diǎn)之間的距離或者角度，而是根據(jù)網(wǎng)絡(luò)的連通性來實(shí)現(xiàn)位置估計得，典型的無需測距的算法主要有以下幾種：

1）質(zhì)心算法

質(zhì)心算法基于兩個假設(shè)條件：射頻信號的傳播遵循理想的圓球模型；節(jié)點(diǎn)的通信半徑相同且不會改變。

該算法利用了計算幾何中質(zhì)心的思想，假設(shè)n邊形的頂點(diǎn)坐標(biāo)分別為（x1，y1）......（xn，yn），設(shè)其質(zhì)心坐標(biāo)為（x，y），則有

x=（x1+x2....+xn）/ n

y=（y1+y2+....+yn）/ n

算法核心思想為：信標(biāo)節(jié)點(diǎn)周期性地廣播包含自身位置信息的消息，在時間t內(nèi)未知節(jié)點(diǎn)收到來自信標(biāo)節(jié)點(diǎn)i的消息數(shù)目為Nr（i，t），而時間t內(nèi)信標(biāo)節(jié)點(diǎn)i發(fā)出的消息數(shù)目為Ns（i，t），那么未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)的連通指標(biāo)為：

C=Nr（i，t）/ Ns（i，t）

如果C大于設(shè)定的閾值，則認(rèn)為未知節(jié)點(diǎn)處于信標(biāo)節(jié)點(diǎn)i的覆蓋區(qū)域內(nèi)，即與信標(biāo)節(jié)點(diǎn)i連通。這樣對于每個未知節(jié)點(diǎn)都可以選出與其連通的所有信標(biāo)節(jié)點(diǎn)，然后把這些信標(biāo)節(jié)點(diǎn)的質(zhì)心作為該未知節(jié)點(diǎn)的坐標(biāo)。

質(zhì)心算法是一種完全基于網(wǎng)絡(luò)連通性的定位算法，其計算和實(shí)施難度都比較小，但是算法精度不高，并且通常要求信標(biāo)節(jié)點(diǎn)具有較高的密度。

2）DV-HOP（Distance Vector-Hop）算法

DV-HOP算法是為了避免對節(jié)點(diǎn)距離直接測量而提出的一種基于矢量路由的非測距定位算法。該算法的核心思想是通過距離矢量路由方法獲取未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)，并計算每跳的平均距離，然后以每跳的平均距離與最小跳數(shù)的乘積作為未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的估算距離，再使用三邊測量法估算未知節(jié)點(diǎn)的坐標(biāo)位置。舉個例子：

A、B、C為信標(biāo)節(jié)點(diǎn)，M為未知節(jié)點(diǎn)，A到B和C的距離分別為40m和100m，而A到B和C的最小跳數(shù)分別為2和5，則A的平均跳距為：

（40+100）/ （2+5）=20m，同理可以得到B和C的平均跳數(shù)為24m和22.5m，則可以計算M距離三個信標(biāo)節(jié)點(diǎn)的距離分別為：

3*20m，2*24m，3*22.5m，然后就可以利用三邊測量法估算出M的坐標(biāo)。這種方法實(shí)現(xiàn)比較簡單，但是精度較差，不適合稀疏的以及拓?fù)洳灰?guī)則的網(wǎng)絡(luò)。

3）APIT算法

APIT算法的基本思想同質(zhì)心算法的思想類似，它利用由信標(biāo)節(jié)點(diǎn)組成的三角形覆蓋重疊區(qū)域來確定未知節(jié)點(diǎn)的位置。在APIT算法中，未知節(jié)點(diǎn)首先在其鄰居節(jié)點(diǎn)中收集信標(biāo)節(jié)點(diǎn)的信息。然后任意選取3個信標(biāo)節(jié)點(diǎn)，判斷自己是否在這3個信標(biāo)節(jié)點(diǎn)組成的三角形區(qū)域內(nèi)，然后不斷這樣循環(huán)選取3個信標(biāo)節(jié)點(diǎn)進(jìn)行判斷，這樣，未知節(jié)點(diǎn)可以確定多個包含自己的三角形區(qū)域，這些三角形區(qū)域的重疊部分是一個多邊形，它確定了更小的包含未知節(jié)點(diǎn)的區(qū)域，然后以這個多邊形區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。

4）MAP算法

MAP（Mobile Anchor Point）是一種基于移動信標(biāo)節(jié)點(diǎn)的非測距定位算法，也有稱為MAN（Mobile Anchor Node）。其基本思想是利用可移動的信標(biāo)節(jié)點(diǎn)在監(jiān)測區(qū)域中移動并周期性的廣播其當(dāng)前的位置信息，然后可以確定兩條以未知節(jié)點(diǎn)為圓心的弦，這兩條弦的垂直平分線的交點(diǎn)就是圓心。

如圖所示，S為未知節(jié)點(diǎn)，M為移動的信標(biāo)節(jié)點(diǎn)，在T1時刻M移動到S的通信范圍之內(nèi)，然后在T5時刻移出S的通信范圍，這樣就可以確定了兩條弦 ?T1T5，在T12時刻M又重新移動到S的通信范圍之內(nèi)，然后又在T15時刻移出S的通信范圍，這樣又可以確定一條弦T12T15，這兩條弦的垂直平分線的交點(diǎn)即為圓心S的坐標(biāo)，然后以圓心坐標(biāo)作為未知節(jié)點(diǎn)S的位置。

該算法有與其他非測距定位算法相比有較高的精確度，但是缺點(diǎn)是移動節(jié)點(diǎn)是必須要有足夠能量支持其在監(jiān)測區(qū)域內(nèi)移動，并且當(dāng)未知節(jié)點(diǎn)的位置發(fā)生變化時，該算法有比較大的誤差。

5）Amorphous算法

Amorphous算法與DV-HOP算法類似，其分為三個階段：

第一階段：計算未知節(jié)點(diǎn)與每個信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)

第二階段：假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)通信半徑相同，并且每跳的平均距離等于節(jié)點(diǎn)的通信半徑，計算未知節(jié)點(diǎn)到每個信標(biāo)節(jié)點(diǎn)的距離

第三階段：采用三邊測量法或者最大似然估計法估算未知節(jié)點(diǎn)的位置

6）凸規(guī)劃定位算法

凸規(guī)劃定位算法的核心思想是：如果兩個節(jié)點(diǎn)能夠直接進(jìn)行通信，則它們之間的距離必定小于節(jié)點(diǎn)的通信半徑。

如圖所示，黑色實(shí)心點(diǎn)為信標(biāo)節(jié)點(diǎn)，白色空心點(diǎn)為未知節(jié)點(diǎn)，假若未知節(jié)點(diǎn)能與信標(biāo)節(jié)點(diǎn)通信，則其必在以信標(biāo)節(jié)點(diǎn)為圓心、通信半徑為半徑的圓內(nèi)，這樣的話，多個這樣的圓的相交區(qū)域必然包含了未知節(jié)點(diǎn)，然后以相交區(qū)域構(gòu)成的矩形的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。

7）Ring-Overlapping算法

該算法利用交疊環(huán)的思想進(jìn)行定位，比如S為未知節(jié)點(diǎn)，A、B、C為信標(biāo)節(jié)點(diǎn)，若A發(fā)出射頻信號，而S處的信號強(qiáng)度RSS小于B處的信號強(qiáng)度而大于C處的信號強(qiáng)度，則S必在以A-B為內(nèi)半徑、A-C為外半徑的環(huán)形區(qū)域內(nèi)，類似地分別可以得到以B、C為中心的環(huán)形區(qū)域，而S必在這些環(huán)形區(qū)域的交疊區(qū)域內(nèi)，然后以交疊區(qū)域的質(zhì)心作為S的坐標(biāo)。

以上算法都是有信標(biāo)節(jié)點(diǎn)的定位算法，曾有人提出了一些沒有信標(biāo)節(jié)點(diǎn)的定位算法如SPA（Self-positioning Algorithm）算法，這種算法主要是建立全局坐標(biāo)系來估算未知節(jié)點(diǎn)的位置，但是這種算法復(fù)雜度非常高，不適合用于大規(guī)模網(wǎng)絡(luò)，也有人提出針對SPA算法的改進(jìn)算法，如SDGPSN（Scalable and Distributed GPS free Positioning for?Sensor Networks）算法。

還有一部分人提出了一些其他的算法，比如AFL（Anchor-Free Distributed Localization in Sensor Networks）算法，其利用的是局部估算方法。還有人提出了基于分簇的定位算法（Using Clustering Information for Sensor?Network Localization）。

定位算法暫時就介紹這么多了，相關(guān)深入內(nèi)容將在后面繼續(xù)講解。