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

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

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

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

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

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

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

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

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

以下是幾個常用術語：

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

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

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

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

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

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

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

二.節(jié)點定位技術的基本思路

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

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

測距

位置估算

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

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

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

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

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

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

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

通常測距的方法有4種：

1）基于到達時間（TOA）的測距

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

2）基于到達時間差（TDOA）的測距

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

t1-t2=d/v1-d/v2

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

3）基于到達角度（AOA）的測距

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

4）基于接收信號強度（RSS）的測距

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

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

1）三邊測量法

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

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

3）最大似然估計法

已知n個節(jié)點的坐標為（x1，y1），（x2，y2）......（xn，yn），它們到未知節(jié)點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)絡連通性或者拓撲結(jié)構(gòu)來估算距離，再利用三邊測量法或者極大似然估計來估算位置。

三.常見算法

1.基于測距（range-based）

1）AHLos 算法?

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

2）RADAR算法

該算法是基于RSS的測距，而基于RSS測距該算法有兩種模型：經(jīng)驗模型和信號傳播模型

先說一下經(jīng)驗模型：

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

信號傳播模型：

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

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

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

shadowing模型：

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

2.無需測距（range-free）

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

1）質(zhì)心算法

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

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

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

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

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

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

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

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

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

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

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

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

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

3）APIT算法

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

4）MAP算法

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

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

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

5）Amorphous算法

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

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

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

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

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

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

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

7）Ring-Overlapping算法

該算法利用交疊環(huán)的思想進行定位，比如S為未知節(jié)點，A、B、C為信標節(jié)點，若A發(fā)出射頻信號，而S處的信號強度RSS小于B處的信號強度而大于C處的信號強度，則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的坐標。

以上算法都是有信標節(jié)點的定位算法，曾有人提出了一些沒有信標節(jié)點的定位算法如SPA（Self-positioning Algorithm）算法，這種算法主要是建立全局坐標系來估算未知節(jié)點的位置，但是這種算法復雜度非常高，不適合用于大規(guī)模網(wǎng)絡，也有人提出針對SPA算法的改進算法，如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）。

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