電子發(fā)燒友App
無線傳感器網(wǎng)絡(luò)的許多應(yīng)用要求節(jié)點知道自身的位置信息，才能向用戶提供有用的檢測服務(wù)。沒有節(jié)點位置信息的監(jiān)測數(shù)據(jù)在很多場合下是沒有意義的。比如，對于森林火災(zāi)檢測、天然氣管道監(jiān)測等應(yīng)用，當(dāng)有事件發(fā)生時，人們關(guān)心的一個首要問題就是事件發(fā)生在哪里，此時如果只知道發(fā)生了火災(zāi)卻不知道火災(zāi)具體的發(fā)生地點，這種監(jiān)測沒有任何實質(zhì)的意義，因此節(jié)點的位置信息對于很多場合是至關(guān)重要的。
在許多場合下，傳感器節(jié)點被隨機(jī)部署在某個區(qū)域，節(jié)點事先無法知道自身的位置，因此需要在部署后通過定位技術(shù)來獲取自身的位置信息。目前最常見的定位技術(shù)就是GPS（Global Positioning System）了，它能夠通過衛(wèi)星對節(jié)點進(jìn)行定位，并且能夠達(dá)到比較高的精度。因此要想對傳感器節(jié)點進(jìn)行定位，最容易想到的方法就是給每個節(jié)點配備一個GPS接收器，但是這種方法不適用于傳感器網(wǎng)絡(luò)，主要原因有以下幾點：
1）GPS接收器通常能耗高，而對于無線傳感器網(wǎng)絡(luò)中的節(jié)點來說，一般能耗很有限，給每個節(jié)點配備一個GPS接收器會大大縮短網(wǎng)絡(luò)壽命；
2）GPS接收器成本比較高，給無線傳感器網(wǎng)絡(luò)中的每個節(jié)點配備一個GPS接收器，需要投入很大成本，尤其對于大規(guī)模的無線傳感器網(wǎng)絡(luò)來說不是很適合；
因此有必要研究適合無線傳感器網(wǎng)絡(luò)的定位技術(shù)。下面分兩個部分來介紹節(jié)點定位的相關(guān)研究：1）節(jié)點定位的基本概念；2）節(jié)點定位的基本思路；3）常見算法。
一.節(jié)點定位的基本概念
無線傳感器網(wǎng)絡(luò)中的節(jié)點定位是指傳感器節(jié)點根據(jù)網(wǎng)絡(luò)中少數(shù)已知節(jié)點的位置信息，通過一定的定位技術(shù)確定網(wǎng)絡(luò)中其他節(jié)點的位置信息的過程。
在無線傳感器網(wǎng)絡(luò)中節(jié)點通?？梢苑譃樾艠?biāo)節(jié)點（beacon node or anchor node）和未知節(jié)點（unknown node），其中信標(biāo)節(jié)點也稱為錨節(jié)點或者參考點，未知節(jié)點也稱為普通節(jié)點。信標(biāo)節(jié)點是位置信息已知的節(jié)點，未知節(jié)點是未知信息未知的節(jié)點。信標(biāo)節(jié)點一般所占比例很小，通常通過手工配置或者配備GPS接收器來獲取自身的位置信息。
除此之外還有一種節(jié)點稱為鄰居節(jié)點（neighbor node），鄰居節(jié)點是指傳感器節(jié)點通信半徑內(nèi)的其他節(jié)點。
以下是幾個常用術(shù)語：
到達(dá)時間（Time of Arrvial，TOA），信號從一個節(jié)點傳播到另一個節(jié)點所需時間
到達(dá)時間差（Time Diffrential of Arrival，TDOA），不同傳播速度的信號從一個節(jié)點到達(dá)另一個基點所需要的時間之差
到達(dá)角度（Angle of Arrival，AOA），節(jié)點接收到的信號相對于自身軸線的角度
接收信號強(qiáng)度（Received Sinnal Strength，RSS），節(jié)點接收到無限信號強(qiáng)度的大小，也有稱Received Sinnal Strength Indicator（RRSI），兩個意思基本是一樣的
視距關(guān)系（Light of Sight，LOS），兩個節(jié)點之間沒有障礙物，能夠直接通信
非視距關(guān)系（Non Light of Sight，NLOS），兩個節(jié)點之間有障礙物，不能直接通信
跳數(shù)（Hop Count），兩個節(jié)點之間的跳段之和
二.節(jié)點定位技術(shù)的基本思路
節(jié)點定位的基本思路主要有兩種：
1.基于測距（Range-based）：假設(shè)在傳感器網(wǎng)絡(luò)中某些節(jié)點位置信息已知，通過某些手段來估算其他節(jié)點的位置信息。在這里面通常有兩個步驟：
測距
位置估算
因為要通過信標(biāo)節(jié)點得到未知節(jié)點的位置信息，必須先確定信標(biāo)節(jié)點到未知節(jié)點的距離，才能得到未知節(jié)點的位置信息。舉個例子說明一下：
假如信標(biāo)節(jié)點A位置已知為（x1，y1），節(jié)點M位置未知，要想求得M的位置，最簡單的想法：假設(shè)B位置為（x，y），A到B的距離為d1，則有
d12=（x-x1）2+（y-y1）2
顯然只根據(jù)一個方程這樣是無法求得x和y的值，假若有兩個信標(biāo)節(jié)點呢？
這樣一來的話又多了一個方程：d22=（x-x2）2+（y-y2）2，此時可以解得方程組得到x和y，但是此時x和y是有兩組解的，無法唯一確定x和y的值，因此需要考慮再假如一個信標(biāo)節(jié)點：
這樣一來的話就可以唯一確定x和y的值了，最基本的定位思想就是這樣。這里舉的例子是采用距離，還可以采用角度。
一般情況最少需要知道未知節(jié)點和信標(biāo)節(jié)點的三組距離或角度值，然后再通過位置估算方法確定位置。
通常測距的方法有4種：
1）基于到達(dá)時間（TOA）的測距
這種方法是根據(jù)已知信號的傳播速度及信號在發(fā)送節(jié)點和接收節(jié)點之間的傳播時間來估算距離，這種方法要求能夠非常精確地獲取發(fā)送節(jié)點和接收節(jié)點之間的傳播時延，這個是比較困難的，難度很大，不太適合無線傳感器網(wǎng)絡(luò)。
2）基于到達(dá)時間差（TDOA）的測距
這種方法中發(fā)送節(jié)點同時發(fā)送兩種不同傳播速度的信號、接收節(jié)點根據(jù)兩種信號到達(dá)的時間差和他們的傳播速度來計算距離。假若兩種信號的傳寶速度為v1和v2，到達(dá)時間分別為t1和t2，發(fā)送節(jié)點到接收節(jié)點的距離為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é)點的坐標(biāo)為（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)絡(luò)連通性或者拓?fù)浣Y(jié)構(gòu)來估算距離，再利用三邊測量法或者極大似然估計來估算位置。
三.常見算法
1.基于測距（range-based）
1）AHLos 算法?
該算法是基于到達(dá)時間差的測距，信標(biāo)節(jié)點首先向鄰居節(jié)點以兩種射頻信號來廣播消息，然后鄰居節(jié)點根據(jù)到達(dá)時間差來估算距離，在接收到三個信標(biāo)節(jié)點的消息之后，則根據(jù)三邊測量法估算位置，鄰居節(jié)點確定自己的位置之后轉(zhuǎn)變?yōu)樾艠?biāo)節(jié)點，也向鄰近節(jié)點廣播消息重復(fù)上述過程直至所有節(jié)點定位完成。
2）RADAR算法
該算法是基于RSS的測距，而基于RSS測距該算法有兩種模型：經(jīng)驗?zāi)Ｐ秃托盘杺鞑ツＰ?/p>
先說一下經(jīng)驗?zāi)Ｐ停?/p>
在經(jīng)驗?zāi)Ｐ椭校?jié)點被分散在一定的區(qū)域內(nèi)，并且保證所有的未知節(jié)點能夠與信標(biāo)節(jié)點直接通信，如圖所示。然后事先在該區(qū)域內(nèi)采集一些位置進(jìn)行RSS強(qiáng)度測試，并以（x，y，RSS）的形式記錄到數(shù)據(jù)庫中。當(dāng)進(jìn)行定位時，未知節(jié)點同數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行比對，選擇差值最小的三個或者三個以上點作為估算位置，然后再采用三邊測量法或者下文的質(zhì)心法來估算位置。
信號傳播模型：
信號傳播模型主要有兩種模型：自由空間模型和shadowing模型
自由空間模型假定信號發(fā)射功率和信號接收功率存在確定的映射關(guān)系：?
其中PR是接收處的功率，PS是發(fā)射處的功率，d是發(fā)射點距接收點的距離，α是傳播因子，視環(huán)境而定。
shadowing模型：
其中P（d）是未知節(jié)點處的信號強(qiáng)度或者信號發(fā)射功率，P（d0）是距信標(biāo)節(jié)點或者基站d0處的信號發(fā)射功率（其中d0是參考距離，一般取1m），n是衰減因子，由于實際環(huán)境中存在噪聲，所以引入了?，比如在室內(nèi)傳播，會有墻壁或者門這些障礙物，就需要計算?。
2.無需測距（range-free）
無需測距的定位算法不需要直接測量節(jié)點之間的距離或者角度，而是根據(jù)網(wǎng)絡(luò)的連通性來實現(xiàn)位置估計得，典型的無需測距的算法主要有以下幾種：
1）質(zhì)心算法
質(zhì)心算法基于兩個假設(shè)條件：射頻信號的傳播遵循理想的圓球模型；節(jié)點的通信半徑相同且不會改變。
該算法利用了計算幾何中質(zhì)心的思想，假設(shè)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é)點周期性地廣播包含自身位置信息的消息，在時間t內(nèi)未知節(jié)點收到來自信標(biāo)節(jié)點i的消息數(shù)目為Nr（i，t），而時間t內(nèi)信標(biāo)節(jié)點i發(fā)出的消息數(shù)目為Ns（i，t），那么未知節(jié)點和信標(biāo)節(jié)點的連通指標(biāo)為：
C=Nr（i，t）/ Ns（i，t）
如果C大于設(shè)定的閾值，則認(rèn)為未知節(jié)點處于信標(biāo)節(jié)點i的覆蓋區(qū)域內(nèi)，即與信標(biāo)節(jié)點i連通。這樣對于每個未知節(jié)點都可以選出與其連通的所有信標(biāo)節(jié)點，然后把這些信標(biāo)節(jié)點的質(zhì)心作為該未知節(jié)點的坐標(biāo)。
質(zhì)心算法是一種完全基于網(wǎng)絡(luò)連通性的定位算法，其計算和實施難度都比較小，但是算法精度不高，并且通常要求信標(biāo)節(jié)點具有較高的密度。
2）DV-HOP（Distance Vector-Hop）算法
DV-HOP算法是為了避免對節(jié)點距離直接測量而提出的一種基于矢量路由的非測距定位算法。該算法的核心思想是通過距離矢量路由方法獲取未知節(jié)點與信標(biāo)節(jié)點之間的最小跳數(shù)，并計算每跳的平均距離，然后以每跳的平均距離與最小跳數(shù)的乘積作為未知節(jié)點與信標(biāo)節(jié)點的估算距離，再使用三邊測量法估算未知節(jié)點的坐標(biāo)位置。舉個例子：
A、B、C為信標(biāo)節(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距離三個信標(biāo)節(jié)點的距離分別為：
3*20m，2*24m，3*22.5m，然后就可以利用三邊測量法估算出M的坐標(biāo)。這種方法實現(xiàn)比較簡單，但是精度較差，不適合稀疏的以及拓?fù)洳灰?guī)則的網(wǎng)絡(luò)。
3）APIT算法
APIT算法的基本思想同質(zhì)心算法的思想類似，它利用由信標(biāo)節(jié)點組成的三角形覆蓋重疊區(qū)域來確定未知節(jié)點的位置。在APIT算法中，未知節(jié)點首先在其鄰居節(jié)點中收集信標(biāo)節(jié)點的信息。然后任意選取3個信標(biāo)節(jié)點，判斷自己是否在這3個信標(biāo)節(jié)點組成的三角形區(qū)域內(nèi)，然后不斷這樣循環(huán)選取3個信標(biāo)節(jié)點進(jìn)行判斷，這樣，未知節(jié)點可以確定多個包含自己的三角形區(qū)域，這些三角形區(qū)域的重疊部分是一個多邊形，它確定了更小的包含未知節(jié)點的區(qū)域，然后以這個多邊形區(qū)域的質(zhì)心作為未知節(jié)點的坐標(biāo)。
4）MAP算法
MAP（Mobile Anchor Point）是一種基于移動信標(biāo)節(jié)點的非測距定位算法，也有稱為MAN（Mobile Anchor Node）。其基本思想是利用可移動的信標(biāo)節(jié)點在監(jiān)測區(qū)域中移動并周期性的廣播其當(dāng)前的位置信息，然后可以確定兩條以未知節(jié)點為圓心的弦，這兩條弦的垂直平分線的交點就是圓心。
如圖所示，S為未知節(jié)點，M為移動的信標(biāo)節(jié)點，在T1時刻M移動到S的通信范圍之內(nèi)，然后在T5時刻移出S的通信范圍，這樣就可以確定了兩條弦 ?T1T5，在T12時刻M又重新移動到S的通信范圍之內(nèi)，然后又在T15時刻移出S的通信范圍，這樣又可以確定一條弦T12T15，這兩條弦的垂直平分線的交點即為圓心S的坐標(biāo)，然后以圓心坐標(biāo)作為未知節(jié)點S的位置。
該算法有與其他非測距定位算法相比有較高的精確度，但是缺點是移動節(jié)點是必須要有足夠能量支持其在監(jiān)測區(qū)域內(nèi)移動，并且當(dāng)未知節(jié)點的位置發(fā)生變化時，該算法有比較大的誤差。
5）Amorphous算法
Amorphous算法與DV-HOP算法類似，其分為三個階段：
第一階段：計算未知節(jié)點與每個信標(biāo)節(jié)點之間的最小跳數(shù)
第二階段：假設(shè)網(wǎng)絡(luò)中的節(jié)點通信半徑相同，并且每跳的平均距離等于節(jié)點的通信半徑，計算未知節(jié)點到每個信標(biāo)節(jié)點的距離
第三階段：采用三邊測量法或者最大似然估計法估算未知節(jié)點的位置
6）凸規(guī)劃定位算法
凸規(guī)劃定位算法的核心思想是：如果兩個節(jié)點能夠直接進(jìn)行通信，則它們之間的距離必定小于節(jié)點的通信半徑。
如圖所示，黑色實心點為信標(biāo)節(jié)點，白色空心點為未知節(jié)點，假若未知節(jié)點能與信標(biāo)節(jié)點通信，則其必在以信標(biāo)節(jié)點為圓心、通信半徑為半徑的圓內(nèi)，這樣的話，多個這樣的圓的相交區(qū)域必然包含了未知節(jié)點，然后以相交區(qū)域構(gòu)成的矩形的質(zhì)心作為未知節(jié)點的坐標(biāo)。
7）Ring-Overlapping算法
該算法利用交疊環(huán)的思想進(jìn)行定位，比如S為未知節(jié)點，A、B、C為信標(biāo)節(jié)點，若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é)點的定位算法，曾有人提出了一些沒有信標(biāo)節(jié)點的定位算法如SPA（Self-positioning Algorithm）算法，這種算法主要是建立全局坐標(biāo)系來估算未知節(jié)點的位置，但是這種算法復(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ù)講解。
工商網(wǎng)監(jiān)
評論