動(dòng)定位裝置協(xié)助感測器定位的經(jīng)濟(jì)

1、使用動(dòng)定位裝置協(xié)助感測器定位的經(jīng)濟(jì)程策國 中 央 大 學(xué) 資 訊 工 程 研 究 所 研 究 生： 科 鋒 指導(dǎo)教授：曾 明 博士 報(bào)告:資工三乙494512334許楚昀背景 由於近微型製造、通訊和電池技術(shù)的改進(jìn)，用小型感測器(Sensor)形成的無線感測網(wǎng)(Wireless Sensor Network) 1 漸漸於相當(dāng)多方面被廣泛的使用。感測器通常由微型處器(Micro CPU)、無線電接收及發(fā)送器(Radio Frequency，簡稱RF)和感應(yīng)器組成，感應(yīng)器可以用感應(yīng)溫、光線、溼、加速等.變化動(dòng)機(jī) 關(guān)於無線感測網(wǎng)(Wireless Sensor Network)的研究相當(dāng)?shù)膹V泛，其中感

2、測器的定位問題是一個(gè)相當(dāng)重要的議題，因?yàn)楦袦y器的位置資訊在涵蓋範(fàn)圍、繞送、追蹤和救援等問題上相當(dāng)有用 range-based藉由求得距和角的資訊估算位置的方法，其估算出的位置較為準(zhǔn)確但是由於需要一些特殊且昂貴的額外設(shè)備獲得準(zhǔn)確的資訊，使得所要的花費(fèi)比較大 ange-free需要用昂貴和準(zhǔn)確的設(shè)備獲得距和角的資訊就能估算出位置 本文是建在Localization with mobile anchor points in wireless sensor networks 21 這篇由Kuo-Feng Ssu, Chia-Ho Ou, Christine Jiau,提出的文上。假設(shè)感測器接收動(dòng)定位裝

3、置發(fā)出訊號(hào)的範(fàn)圍為一個(gè)圓，其最大接收距為圓的半徑，其圓心為感測器Range-based 訊號(hào)傳播時(shí)間(Time of Arrival，簡稱TOA) 聲波和無線電波訊號(hào)傳播的時(shí)間差(Time Difference of Arrival，簡稱TODA) 點(diǎn)之間的角(Angle of Arrival，簡稱AOA) 接收到的訊號(hào)強(qiáng)(Received Signal Strength Indicator，簡稱RSSI)Cricket 用TDOA估算位置的方法，定位裝置同時(shí)發(fā)送無線電波和超音波，由於超音波的速較慢，用收到種波的時(shí)間差估算與 定位裝置的距，感測器必須要有種波的接收器，並且要有準(zhǔn)的時(shí)間儀器，這樣

4、才能達(dá)到準(zhǔn)的定位。 APS Using AOA(APSAOA) 用AOA估算位置的方法，正常講感測器或是定位裝置，每個(gè)點(diǎn)傳送的無線電範(fàn)圍應(yīng)該為一個(gè)圓，假設(shè)每個(gè)點(diǎn)有一個(gè)主要的方向，此方向一直往順時(shí)針或逆時(shí)針轉(zhuǎn)動(dòng)，求出從初始位置轉(zhuǎn)動(dòng)多少角可以跟另外個(gè)點(diǎn)傳送訊息，則可以用此個(gè)角求出以自己為頂點(diǎn)與這個(gè)點(diǎn)所形成的角，如圖1所示，用此角資訊與一些定位裝置之間的距感測器即可估算出自己的位置。 RADAR 用RSSI估算位置的方法，在一個(gè)區(qū)域放置多個(gè)基地臺(tái)記和處信號(hào)強(qiáng)的資訊，並用過去的測的一些經(jīng)驗(yàn)決定感測器的位置，由於距是完全用訊號(hào)強(qiáng)估算，因此測訊號(hào)強(qiáng)的儀器必須非常的確。RSSI Using Mobile A

5、nchor(RSSIUMA) 是range-based用RSSI估算位置的方法，方法為用定位裝置，斷的在散佈感測器的範(fàn)圍面移動(dòng)，並斷的發(fā)送自己的位置座標(biāo)，當(dāng)感測器接 收到動(dòng)定位裝置所發(fā)送的訊號(hào)時(shí)，藉由收到的訊號(hào)強(qiáng)判斷自己和動(dòng)定位裝置發(fā)送訊號(hào)的位置之間的距，以動(dòng)定位裝置發(fā)送訊號(hào)的位置為圓心，形成一個(gè)圓，動(dòng)定位裝置斷的移動(dòng)則感測器以這些圓的交集區(qū)域的中心位置為自己的位置所在。Range-free 需要用額外昂貴的設(shè)備求得距和角資訊。 Centroid 三個(gè)假設(shè): 無線電的傳播為完美的球體. 所有無線電傳播範(fàn)圍的範(fàn)圍相同 發(fā)送同步的訊號(hào) 在網(wǎng)有著許多能知道自己位置的考點(diǎn)週期性的發(fā)送含有自己位置的訊號(hào)

6、，考點(diǎn)相當(dāng)於定位裝置，感測器收集訊號(hào)資訊超過門檻值的考點(diǎn)，假設(shè)這些考點(diǎn)的座標(biāo)為(Xi1,Yi1)到(Xik,Yik) ，則以這些座標(biāo)的重心當(dāng)作感測器的位置，在單位面積有越多的考點(diǎn)則求出的位置越準(zhǔn)確DV-Hop 用跟考點(diǎn)之間的跳躍(Hop)估算到考點(diǎn)之間的距，考點(diǎn)相當(dāng)於定位裝置 ?？键c(diǎn)會(huì)計(jì)算它們與其他考點(diǎn)之間的距和平均一個(gè)跳躍是多少距，考點(diǎn)廣播此資訊到網(wǎng)中，當(dāng)感測器收到這些訊息後，藉由自己與這些考點(diǎn)的跳躍計(jì)算自己與這些考點(diǎn)的距，當(dāng)有跟三個(gè)考點(diǎn)以上的距資訊時(shí)，感測器即可以估算出自己的位置。 ，A1, A2, A3為三個(gè)考點(diǎn)，而S為感測器，A1距A2, A3分別為40公尺和70公尺，A1到A2, A

7、3的徑長分別為2個(gè)跳躍和4個(gè)跳躍，因此A1求出其一個(gè)跳躍的距為: (40+70)/(2+4) = 18.33A2: (40+55)/(2+3) =19A3: (55+70)/(3+4) = 17.86 由於考點(diǎn)A2感測器比A1和A3近，感測器會(huì)先收到A2算出一個(gè)跳躍的距，感測器估算出自己距A1為2 x 19 = 38 公尺，距A2為1 x 19 = 19 公尺，距A3為2 x 19 = 38 公尺，在加上知道考點(diǎn)A1, A2, A3的座標(biāo)資訊，因此感測器能藉由這些資訊估算出自己的位置。 APIT 要求有一小部分的感測器能夠高功傳送訊號(hào)且可以藉由GPS或其他方法獲得位置資訊，這些裝置即為定位裝置

8、，用這些定位裝置產(chǎn)生的信標(biāo)(Beacon)，感測器判斷是否在這些信標(biāo)為頂點(diǎn)形成的三角形面，用這些三角形形成區(qū)域的交集，估算自己的位置 當(dāng)在三角形時(shí)在相對應(yīng)的計(jì)器加一，當(dāng)在三角形時(shí)在相對應(yīng)的計(jì)器減一，最後計(jì)器字最大的區(qū)域即為感測器估計(jì)自己所在的區(qū)域，此區(qū)域的中心位置即為感測器估計(jì)所在的位置。 判斷是否在三角形的方法: 當(dāng)感測器在三角形面時(shí)，當(dāng)感測器往任意方向移動(dòng)時(shí)，一定至少靠近其中一個(gè)頂點(diǎn) 當(dāng)感測器在三角形外面時(shí)，當(dāng)感測器往任意方向移動(dòng)時(shí)，一定是靠近三個(gè)頂點(diǎn)或是遠(yuǎn)三個(gè)頂點(diǎn)ROCRSSI 基本是用環(huán)的重疊縮小感測器可能所在的區(qū)域 假設(shè)感測器S到定位裝置A1的距介於定位裝置A1到定位裝置A2和A3距

9、之間，則感測器S在圖 10 中灰色的環(huán)上，以此推求得許多環(huán)，而這些環(huán)的重疊區(qū)域即為感測器估計(jì)自己所在的區(qū)域，此區(qū)域的中心位置即為估計(jì)所在的位置。判斷距的方法為用訊號(hào)強(qiáng)，假設(shè)定位裝置A2, A3和感測器S收到定位裝置A1發(fā)送信標(biāo)訊息的訊號(hào)強(qiáng)分別為RSSIA1A2, RSSIA1A3, RSSIA1S，假設(shè)RSSIA1A2 RSSIA1S RSSIA1A3 ，則感測器在圖 10中灰色的環(huán)上。 Perpendicular bisector of a chord conjecture (PBCC) 定位的方法為感測器和動(dòng)定位裝置的最大通訊距為一個(gè)圓的半徑，圓的圓心為感測器，能找到圓上的三個(gè)點(diǎn)的座標(biāo)，即

10、可求得圓上的條平的弦，條弦的中垂線交於圓心即為感測器的位置。動(dòng)定位裝置週期性的發(fā)送含有訊息的訊號(hào)出去，訊號(hào)包含的訊息有: 動(dòng)定位裝置的ID 發(fā)送訊號(hào)時(shí)的位置 發(fā)送訊號(hào)時(shí)的時(shí)間 Range-based和Range free總結(jié) range-based 皆為sensor用發(fā)訊號(hào), 需要比較訊號(hào)強(qiáng), anchor用改變訊號(hào)強(qiáng) 而只有RSSIUMA得anchor會(huì)移動(dòng)。 range-free比較 經(jīng)濟(jì)程策 PBCC 21 的系統(tǒng)環(huán)境中，感測器只需要接收訊號(hào)就好，並需要發(fā)送任何訊號(hào)給動(dòng)定位裝置，只有當(dāng)自己或其他感測器觀察到環(huán)境的變化時(shí)，才需要發(fā)送訊號(hào)將資訊傳到基地臺(tái)，而動(dòng)定位裝置也只需要一面移動(dòng)一面週期

11、性的廣播含有位置和時(shí)間訊息的訊號(hào)，然後選定一個(gè)目的地，往目的地方向前進(jìn)，當(dāng)?shù)竭_(dá)目的地時(shí)，在選定另一個(gè)目的地，繼續(xù)斷的移動(dòng)即可協(xié)助一個(gè)散佈著許多感測器的範(fàn)圍上所有感測器做到準(zhǔn)確的定位。 但是同時(shí)也衍生出一個(gè)問題，動(dòng)定位裝置只需要一面移動(dòng)一面週期性的廣播含有位置和時(shí)間訊息的訊號(hào)，然後選定一個(gè)目的地，往目的地方向前進(jìn)，當(dāng)?shù)竭_(dá)目的地時(shí)，在隨機(jī)選定另一個(gè)目的地，假設(shè)動(dòng)定位裝置選定的目的地選的好，將能使得能較快速的協(xié)助範(fàn)圍內(nèi)所有感測器做到準(zhǔn)確的定位，但是相對的如果動(dòng)定位裝置選定的目的地選的好時(shí)，將可能造成範(fàn)圍內(nèi)可能有某一個(gè)區(qū)域的感測器已經(jīng)被定位，但動(dòng)定位裝置卻一直在該區(qū)域移動(dòng) 如果有感測器發(fā)送訊號(hào)的範(fàn)圍大

12、小、定位裝置發(fā)送訊號(hào)的範(fàn)圍大小、在環(huán)境中感測器的目和一些初始設(shè)定的資訊，我們才有資訊可以判斷怎麼走才能在確保所有感測器找到條平的弦的條件下，知道何時(shí)所有範(fàn)圍內(nèi)的所有 感測器定位且所需要走的徑較短。其中動(dòng)定位裝置發(fā)送的訊號(hào)越大，則相當(dāng)於感測器的接收範(fàn)圍變大。 估算半徑的方法 事先估算半徑 用動(dòng)定位裝置開一個(gè)感測器到保證此感測器收到動(dòng)定位裝置發(fā)送的訊號(hào)時(shí)，動(dòng)定位裝置走回感測器發(fā)送訊號(hào)的範(fàn)圍內(nèi)，藉由感測器告知?jiǎng)佣ㄎ谎b置其最後收到動(dòng)定位裝置的訊號(hào)的位置資訊，動(dòng)定位裝置知道此位置後即可求得自己的發(fā)送訊號(hào)的範(fàn)圍大小 沒有事先估算半徑 假設(shè)感測器收到動(dòng)定位裝置的訊號(hào)後，感測器回覆的訊息動(dòng)定位裝置可以接收到時(shí)

13、，我們可以用感測器回應(yīng)一些資訊估算發(fā)送訊號(hào)的範(fàn)圍半徑使用信標(biāo)點(diǎn)訊息估算半徑 假設(shè)感測器收到動(dòng)定位裝置的訊號(hào)後，感測器回覆的訊息動(dòng)定位裝置可以接收到時(shí)，感測器回覆其信標(biāo)點(diǎn)的位置資訊給動(dòng)定位裝置，個(gè)信標(biāo)點(diǎn)可以形成動(dòng)定位裝置發(fā)送範(fàn)圍的一條弦，由於弦的一半長一定介於0和發(fā)送範(fàn)圍的半徑大小，因此動(dòng)定位裝置收到感測器的回覆訊號(hào)後，計(jì)算弦的長，如果其長比目前所知道的半徑長長的話，則取代掉原所知道的半徑長，如果其長比目前所知道的半徑長短的話，則保原的半徑長。感測器計(jì)算半徑 當(dāng)感測器收到動(dòng)定位裝置的訊 號(hào)後，每隔一段時(shí)間會(huì)繼續(xù)週期性的收到動(dòng)定位裝置的訊號(hào)，當(dāng)在該收到動(dòng)定位裝置發(fā)送的訊號(hào)時(shí)，卻沒有收到訊號(hào)時(shí)，代表

14、感測器已經(jīng)有個(gè)信標(biāo)點(diǎn)，當(dāng)過一段時(shí)間後感測器又收到動(dòng)定位裝置的訊號(hào)，就在此時(shí)感測器有三個(gè)信標(biāo)點(diǎn)，感測器用這三個(gè)信標(biāo)點(diǎn)的位置估算出自己的位置，而估算出自己的位置後，可以藉由信標(biāo)點(diǎn)的位置和自己的位置估算出半徑，估算出半徑後把包含此半徑訊息的訊號(hào)傳送給動(dòng)定位裝置，則動(dòng)定位裝置就知道自己的傳送範(fàn)圍的半徑大小基本程策 PCBB 的系統(tǒng)環(huán)境中，快速的協(xié)助範(fàn)圍內(nèi)所有的感測器藉由同一圓上的三個(gè)信標(biāo)點(diǎn)形成條圓上平的弦，條平弦的中垂線交點(diǎn)即為感測器。經(jīng)濟(jì)程策 用動(dòng)定位裝置垂直於地面的上升與下地平面的距或者是藉由配備能改變訊號(hào)強(qiáng)定的硬體資源，在水平面上產(chǎn)生種同的傳送範(fàn)圍半徑形成外圈和內(nèi)圈圈，因此我們除用同一圓上的三個(gè)

15、信標(biāo)點(diǎn)估算感測器的位置外，我們也可以用內(nèi)圈和外圈各自形成一條弦且這條弦為平的方式定位，因此我們想一個(gè)方法使得內(nèi)圈和外圈各自形成一條弦且這條弦為平的方式。 此方法為假設(shè)動(dòng)定位裝置的座標(biāo)為M公尺為一個(gè)單位，也就是走M(jìn)公尺後動(dòng)定位裝置才能分辨的出個(gè)位置的差，以圖為，箭頭為動(dòng)定位裝置的移動(dòng)線，假設(shè)動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小的距為R時(shí)，我們可以用每次往左或是往右走R的距後，我們就往前走M(jìn)公尺，如果這種方式的話，感測器的大圈和小圈的信標(biāo)點(diǎn)會(huì)成對的分別在同的徑上，這樣的方式一定能形成一條內(nèi)圈的弦和一條外圈的弦且弦會(huì)平，由這條平的弦即可估算出感測器的位置出效能評估 模擬環(huán)境 模擬的程式為使用程式語言C+

16、寫的，環(huán)境的大小設(shè)為一個(gè)1000 1000正方形區(qū)域，假設(shè)為一個(gè)1000(公尺) 1000(公尺)的環(huán)境。 環(huán)境內(nèi)的一些變設(shè)定: 感測器發(fā)送訊號(hào)的範(fàn)圍半徑大小 動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小 初始設(shè)定的動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小 環(huán)境範(fàn)圍內(nèi)感測器的個(gè) 在Random的模擬，動(dòng)定位裝置的座標(biāo)為(X, Y)，我們從八個(gè)方向隨機(jī)選一個(gè)方向，此八個(gè)方向我們用(X+1, Y)、(X+1, Y-1)、(X+1, Y+1)、(X, Y+1)、(X, Y-1)、(X-1, Y)、(X-1, Y-1)、(X-1, Y+1)表示，所在的位置為範(fàn)圍的邊界時(shí)則有些方向能選，接著在會(huì)超出範(fàn)圍的距內(nèi)，隨機(jī)選一個(gè)長

17、的走法，而Sbt和Set往(X+1, Y)、(X-1, Y)、(X, Y+1)三個(gè)方向走，而Set會(huì)多(X, Y-1)這個(gè)方向。動(dòng)定位裝置收到感測器的回應(yīng) 感測器收到動(dòng)定位裝置的訊號(hào)後，感測器回覆的訊息動(dòng)定位裝置沒有收到或是感測器沒有發(fā)送訊號(hào)時(shí)的情況。 圖為環(huán)境範(fàn)圍內(nèi)的感測器個(gè)設(shè)為1000個(gè)，動(dòng)定位裝置發(fā)送訊號(hào)大圈和小圈的範(fàn)圍半徑大小設(shè)為100和80的情況下，改變初始設(shè)定的動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小對走的徑的引響。圖中除顯示我們提出的Set可以走較少的徑外還顯示當(dāng)初始設(shè)定的動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小越接近動(dòng)定位裝置發(fā)送的範(fàn)圍半徑大小時(shí)，所需走的徑會(huì)越少。 動(dòng)定位裝置收到感測器的回應(yīng) 感測器收到動(dòng)定位裝置的訊號(hào)後，感測器回覆的訊息動(dòng)定位裝置收得到的情況。 圖26為環(huán)境範(fàn)圍內(nèi)的感測器個(gè)設(shè)為10個(gè)，動(dòng)定位裝置發(fā)送訊號(hào)大圈和小圈的範(fàn)圍半徑大小設(shè)為50和40的情況下，改變初始設(shè)定的動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小對走的徑的引響。圖中除顯示我們提出的Set可以走較少的徑外還顯示當(dāng)初始設(shè)定的動(dòng)定位裝置發(fā)送訊號(hào)的範(fàn)圍半徑大小越接近動(dòng)定位裝置發(fā)送的範(fàn)圍半徑大小時(shí)，所需走的徑會(huì)越少。 結(jié)及未方向 在P