动定位装置协助感测器定位的经济

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

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

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

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

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

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

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

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

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

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

11、性的廣播含有位置和時間訊息的訊號，然後選定一個目的地，往目的地方向前進，當到達目的地時，在選定另一個目的地，繼續斷的移動即可協助一個散佈著許多感測器的範圍上所有感測器做到準確的定位。 但是同時也衍生出一個問題，動定位裝置只需要一面移動一面週期性的廣播含有位置和時間訊息的訊號，然後選定一個目的地，往目的地方向前進，當到達目的地時，在隨機選定另一個目的地，假設動定位裝置選定的目的地選的好，將能使得能較快速的協助範圍內所有感測器做到準確的定位，但是相對的如果動定位裝置選定的目的地選的好時，將可能造成範圍內可能有某一個區域的感測器已經被定位，但動定位裝置卻一直在該區域移動 如果有感測器發送訊號的範圍大

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

13、，我們可以用感測器回應一些資訊估算發送訊號的範圍半徑使用信標點訊息估算半徑 假設感測器收到動定位裝置的訊號後，感測器回覆的訊息動定位裝置可以接收到時，感測器回覆其信標點的位置資訊給動定位裝置，個信標點可以形成動定位裝置發送範圍的一條弦，由於弦的一半長一定介於0和發送範圍的半徑大小，因此動定位裝置收到感測器的回覆訊號後，計算弦的長，如果其長比目前所知道的半徑長長的話，則取代掉原所知道的半徑長，如果其長比目前所知道的半徑長短的話，則保原的半徑長。感測器計算半徑 當感測器收到動定位裝置的訊 號後，每隔一段時間會繼續週期性的收到動定位裝置的訊號，當在該收到動定位裝置發送的訊號時，卻沒有收到訊號時，代表

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

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

16、寫的，環境的大小設為一個1000 1000正方形區域，假設為一個1000(公尺) 1000(公尺)的環境。 環境內的一些變設定: 感測器發送訊號的範圍半徑大小 動定位裝置發送訊號的範圍半徑大小 初始設定的動定位裝置發送訊號的範圍半徑大小 環境範圍內感測器的個 在Random的模擬，動定位裝置的座標為(X, Y)，我們從八個方向隨機選一個方向，此八個方向我們用(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)表示，所在的位置為範圍的邊界時則有些方向能選，接著在會超出範圍的距內，隨機選一個長

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