無(wú)線傳感器網(wǎng)絡(luò)633Amorphous

1、6.3.3 Amorphous6.3.3 Amorphous算法算法宿舍：513概念傳感器節(jié)點(diǎn)是無(wú)線傳感器網(wǎng)絡(luò)中的基本組成單位。在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的位置信息至關(guān)重要，沒(méi)有位置的信息，監(jiān)測(cè)信息就毫無(wú)意義。節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)布設(shè)完成后面臨的首要問(wèn)題。節(jié)點(diǎn)定位指根據(jù)有限的位置已知的節(jié)點(diǎn)來(lái)確定無(wú)線傳感器網(wǎng)絡(luò)中其他節(jié)點(diǎn)的位置，在無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)之間建立起位置關(guān)聯(lián)關(guān)系的定位機(jī)制。3 在不定形計(jì)算機(jī)(Amorphous Computer)上實(shí)現(xiàn)的定位算法。 不定形計(jì)算機(jī)是一種并行計(jì)算結(jié)構(gòu)，和智能群（蟻群、鳥(niǎo)群、粒子群等）很相似。 本質(zhì)上，Amorphous算法是DV-Hop算法的增強(qiáng)，引

2、入了多參考點(diǎn)測(cè)量進(jìn)行估計(jì)求精的步驟。Amorphous定位算法4 Amorphous算法思想是利用兩節(jié)點(diǎn)之間跳段距離代表二者之間的直線距離。分為三個(gè)階段： 第一個(gè)階段，與DV-Hop定位算法相同，未知節(jié)點(diǎn)計(jì)算與每個(gè)信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)； 第二個(gè)階段，假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)的通信半徑相同，平均每跳距離為節(jié)點(diǎn)的通信半徑，未知節(jié)點(diǎn)計(jì)算到每個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離； 第三階段，利用三邊測(cè)量法或極大似然算法，計(jì)算未知節(jié)點(diǎn)的位置。 Amorphous算法將節(jié)點(diǎn)的通信半徑作為平均每跳段距離，定位誤差大。Amorphous定位算法重新計(jì)算平均每跳距離 由于節(jié)點(diǎn)隨機(jī)部署，未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的跳段距離通常不是二者之間的

3、直線距離，采用節(jié)點(diǎn)的通信半徑作為平均每跳距離，過(guò)大估計(jì)了跳段距離。利用下式計(jì)算平均每跳距離： 其中，r表示節(jié)點(diǎn)的通信半徑；nlocal表示網(wǎng)絡(luò)平均連通度，即網(wǎng)絡(luò)中節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)。Amorphous定位算法利用局部跳數(shù)平均值代替跳數(shù) 未知節(jié)點(diǎn)計(jì)算與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)時(shí)，結(jié)果都是整數(shù)，實(shí)驗(yàn)表明這大約增加了0.5個(gè)平均跳數(shù)的誤差。未知節(jié)點(diǎn)利用下式計(jì)算局部跳數(shù)平均值，代替它與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)： 其中，nbrs(i)表示未知節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合；hi表示節(jié)點(diǎn)i與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)；hj表示鄰居節(jié)點(diǎn)j與這個(gè)信標(biāo)節(jié)點(diǎn)之間的跳數(shù)。Amorphous定位算法Amorphous定位算法 根據(jù)平均每跳距離及

4、距各信標(biāo)節(jié)點(diǎn)的局部跳數(shù)，計(jì)算未知節(jié)點(diǎn)距各信標(biāo)節(jié)點(diǎn)的距離： 其中， 為未知節(jié)點(diǎn)i獲得的平均每跳距離， 則代表未知節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)j的最小跳數(shù)。Amorphous定位算法采用三邊測(cè)量法或極大似然估計(jì)法進(jìn)行定位 當(dāng)未知節(jié)點(diǎn)獲得了距三個(gè)或三個(gè)以上信標(biāo)節(jié)點(diǎn)的估算距離，便可以采用三邊測(cè)量法或極大似然法計(jì)算自身位置。 利用最小二乘法對(duì)上述方程進(jìn)行求解，可求得未知節(jié)點(diǎn)位置 其中，(x1,y1),(x2,y2),(x3,y3),(xn,yn)對(duì)應(yīng)n個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)，(x,y)為未知節(jié)點(diǎn)的坐標(biāo)，未知節(jié)點(diǎn)到各信標(biāo)節(jié)點(diǎn)的距離依次為d1,d2,d3,dn。Amorphous定位算法 這個(gè)算法基于經(jīng)驗(yàn)?zāi)Ｐ停谠囼?yàn)環(huán)境中可

5、以取得較好的效果。 但這個(gè)算法假設(shè)網(wǎng)絡(luò)平均連通度nlocal已知，要求在網(wǎng)絡(luò)部署前離線計(jì)算平均每跳距離，網(wǎng)絡(luò)的擴(kuò)展性差，而且對(duì)信標(biāo)節(jié)點(diǎn)的密度要求高。 累積誤差 圖一為傳感器節(jié)點(diǎn)個(gè)數(shù)為150，隨機(jī)分布區(qū)域?yàn)?00300(m2)，信標(biāo)節(jié)點(diǎn)比例為17.2%，平均網(wǎng)絡(luò)連通度為15.3%時(shí)，Amorphous定位算法所對(duì)應(yīng)的跳數(shù)值與累積誤差關(guān)系圖。 由圖1可以看出，隨著未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)值的增大，二者間估算距離與真實(shí)距離的誤差也隨之增大。未知節(jié)點(diǎn)到達(dá)信標(biāo)節(jié)點(diǎn)每增加一跳，便引入不同程度的累積誤差。如何減少由于跳數(shù)值過(guò)大而引起的累積誤差，是Amorphous算法要解決的一個(gè)問(wèn)題。缺點(diǎn)分析缺點(diǎn)分析缺

6、點(diǎn)分析缺點(diǎn)分析不良參考節(jié)點(diǎn)的引入 在無(wú)線傳感器網(wǎng)絡(luò)的定位算法中，有這樣一個(gè)結(jié)論：在未知節(jié)點(diǎn)的定位過(guò)程中，參與定位的信標(biāo)節(jié)點(diǎn)數(shù)目越多，未知節(jié)點(diǎn)的定位精度越高。但是在基于跳段距離的定位算法中，這個(gè)結(jié)論并不總是正確的。缺點(diǎn)分析缺點(diǎn)分析 不良參考節(jié)點(diǎn)的引入 圖二為信標(biāo)節(jié)點(diǎn)比例為10%，平均網(wǎng)絡(luò)連通度為10時(shí)，Amorphous算法分別采用三邊測(cè)量法與極大似然測(cè)量法的定位性能比較圖。其中，橫坐標(biāo)對(duì)應(yīng)節(jié)點(diǎn)定位精度，縱坐標(biāo)為各定位精度以內(nèi)的節(jié)點(diǎn)比例。由圖二可知，定位精度在40%（絕大多數(shù)應(yīng)用已滿足）以內(nèi)時(shí)，三邊測(cè)量法對(duì)應(yīng)的未知節(jié)點(diǎn)比例大于極大似然法。這說(shuō)明采用極大似然法進(jìn)行定位會(huì)引入不良信標(biāo)節(jié)點(diǎn)可降低未知節(jié)點(diǎn)定位精度。缺點(diǎn)分析缺點(diǎn)分析需要較大信標(biāo)節(jié)點(diǎn)比例 在基于跳段距離的定位算法中，需要較高的信標(biāo)節(jié)點(diǎn)比例，才能獲得較高的定位精度。但若信標(biāo)節(jié)點(diǎn)比例太高，又大大增加無(wú)線傳感器網(wǎng)絡(luò)的成本。AHLos4算法中將定位成功的未知節(jié)點(diǎn)全部轉(zhuǎn)化為信標(biāo)節(jié)點(diǎn)，雖然在一定程度上緩解了該問(wèn)題，但同時(shí)也引入了更大的定位誤差。 總總 結(jié)結(jié) 總的來(lái)說(shuō)，Amorphous定位算法定位精度較好，通信開(kāi)銷、存儲(chǔ)開(kāi)銷、計(jì)算量和時(shí)間復(fù)雜性相對(duì)較小，并且具有相對(duì)好的容錯(cuò)性和自適性，但是該算法仍有些地方需要改進(jìn)，如它需要預(yù)知網(wǎng)絡(luò)的連通性，網(wǎng)絡(luò)擴(kuò)展性差，定位效果受錨節(jié)點(diǎn)密