无线感测网路中的定位技术研究.doc

无线感测网路中的定位技术研究 粘浩挺大華技術學院電腦與通訊工程系新竹縣芎?鄉大華?一號nianhtthit.tw隨著電子通訊技術的發展以及無線傳輸科技之普遍，?測系統趨向無線化、小型化、模組化、網?化及經濟與?電化發展，透過802. 11、?芽、ZigBee或GSM之無線傳輸方式，架設分散式多頻道遠端監控與即時分析之資?擷取系統，可建構無線感測器網?（Wireless sensorwork,WSN）。 在相關的應用中，位置資訊（Location Information）佔有很重要地位，每一個裝置在傳送資訊時，常需要在資?中通伴隨著位置資訊。 常用的方法是?用手動設定，或是在感測器上安裝GPS接收器。 其中前者常耗費龐大的時間以及人?資源，甚至會產生人為疏失，導致輸入錯誤的位置資訊。 後者雖可以取得?確的位置資訊，但GPS接收器會大幅提升感測器的造價，加上GPS接收器本身有無法在室內使用的缺點，所以無線感測網?在需要取得位置資訊時，通常是?用定位演算法。 在這篇?文中，我們將討?定位的基本原?，整?多種?同的研究，並將重點放在多元尺?法（Multi-Dimensional MDS），只需要相鄰的資訊（connectivity）或估測的距?資訊，即可推算出所有感測器的相對位置。 由模擬實驗中可以發現，以多元尺?演算法?定位相較於其他的定位法，可以有效的?低運算時間，並提高定位的?確?。 Scaling,關鍵字:感測器、定位、多元尺?法1.1無線感測網?一個無線感測網?是由大?的感測器所組成，感測器的散佈通常是?用隨機散佈的方式，?如?用飛?器將大?的感測器散佈於森?之中。 感測器的位置甚至可能是?斷移動的，?如將感測器散佈在洋?中，以偵測魚群的?。 這也意味著，一個無線感測網?的協定或演算法必須擁有自我組織的能?。 無線感測網?的另一個特點是合作（cooperative）運算，?如一個感測器可以透過無線傳輸，收集附近感測器內的資?，再經運算、篩選過的資?傳送至使用者。 一個完整的感測器網?，如圖1所示，使用者會將感測器散佈於所需要監測的區域，稱為Sensor field。 感測器會將收集到的資?進?整合，必將有用的資?萃取出?，再?用繞徑的方式，將資?傳回至基地台，基地台將資?收集完成後，透過網際網?或衛星將資?傳送至位於遠端的使用者。 圖1無線感測器網?架構1.2無線感測網?定位法對於大多?無線感測網?的應用?，如何取感測器的位置是一個主要的問題。 由感測器所收集的資?，通常會被要求在資?中放入位置資訊，使得使用者可以從眾多的資?中萃取有效的資訊並增加資?的可?用?。 假使在一個偵測森?火災的感測器網?中，各感測器皆未取得位置資訊，當火災發生時，火源附近的感測器測得溫?常升高，將未包含位置資訊的資?迅速的回傳至基地台，當基地台接收到這筆資?後，雖然得知森?中有火災發生，但卻無法得知發生火災的地點，也無法作進一步的處?，使得這筆資?的?用?大幅?低。 ?這個無線感測網?在開始監測前，事先取得每一個感測器的位置資訊，當火災發生時，偵測到溫?變化的感測器會將警告訊息包含著感測器所在的位置資訊?即傳送給基地台，再由基地台通知消防隊至該地進?滅火，如此一?可減少因災害所帶?的損失5。 無線感測網?的定位問題可以?用全球定位系統（Global PositioningSystem,GPS）解決，將GPS安裝於感測器之上，而感測器?可以透過接收訊號取得所在的絕對位置。 然而，?用GPS進?定位會造成感測器體積增大、製造成本大幅提高、加速電?消耗以及容?遭到障礙物阻礙衛星訊號等缺點。 較佳的方法是?用定位演算法取得所有感測器的位置資訊。 部份的方法中提出在網?中散佈少?配有全球定位系統的感測器或擁有位置資訊的裝置稱為地標（anchor nodeor landmark），用以提供位置資訊，並?用每一個感測器的?接（connectivity）資訊，再配合定位演算法估測未定位裝置（regular node）的位置資訊，這是感測器在整個網?的相對位置。 當網?中存在三個以上的地標時，運算結束後，每一個地標會同時擁有一組相對位置和一組絕對位置，我們可以?用線性轉換（linear transformation）將網?上所有感測器原本估測的相對位置轉換成絕對位置。 在佈滿感測器的感測網?中，我們假設各感測器之間有夠高的?線密?，經由信息的傳送能以信號強?決定彼此間的距?，且網?中存在三個以上的地標。 如此，常用的定位程序大體分成以下?種。 2.1以Hop-count為基礎的定位演算法1)地標位置廣播由擔任地標的感測點將自己的絕對位置資訊廣播到隣近的感測點，如此逐步廣播直到整個網?的感測點都清楚知道地標的位置，而各地標之間的幾何距?也可掌握。 2)估算各地標之間最少的Hop-count在廣播的過程中，各感測點與地標之間依據最短?徑法則，經比較估算得知與各地標之間最少的Hop-count。 3)推算感測點之間的平均距?根據前?項結果，可估算出各地標之間感測點的平均距?。 jihyyxxcjjjjijii?,)()(22其中分子是?地標之間的幾何距?，分母則是?地標之間的Hop-count。 4)推算各感測點與地標之間的距?根據各感測點之間的平均距?與距地標的Hop-count，可求得各感測點與地標之間的距?。 5)根據三點定位法，求出各感測點的絕對位置1。 2.2以MDS為基礎的定位演算法多元次尺?構成法簡寫為MDS（Multi-Dimensional Scaling），屬資?分析的工具，依資?彼此間的相似?或相?，決定所有資?的空間組態，而各資?以點座標?表示。 所謂相似?，是指相似的資?被賦予較大的值，而所謂相?則是指相?的資?被賦予較大的值。 當MDS被應用在定位的?域，通常是採用相?，而所賦予的值被視為感測點之間的距?。 當有個感測點時，可得到n距?值，如此可以構成一個距?矩陣。 由於距?的對等性質，這個矩陣形成?對稱矩陣。 MDS根據這個對稱的距?矩陣，試圖導出一群點座標，這些點彼此間的距?合乎原始的距?資?，而這些點是分佈在低維?的空間，就大多?的應用而言，以二維或三維空間較常使用。 換言之，MDS可以將高維?的資?轉為低為維?的資?，並保持原有資?間的相對距?。 MDS可大?區分為以距?當作?據的計?MDS（metric MDS），以及以順序尺?加以衡?解析親近性?據的非計?MDS（nonmetric MDS）。 我們將?用計?MDS的解析方法?估測群組內各感測器的相對位置。 (n-1)/2對MDS的基本精神在於座標矩陣X可從內積矩陣B=XX經由特微值分解法導出，而內積矩陣B可根據距?平方矩陣P (2)乘上一個乘?nIJ11?而得。 這個程序稱為雙中心演算法(double centering)。 以下是MDS的主要步驟1)產生距?平方矩陣P (2)?用集中式的運算，先收集網?中所有感測器與鄰居之間的估測距?，並?用最短?徑演算法，計算整個網?中，任?個感測器之間的最短?徑，並產生距?矩陣P，所花費的時間複雜?為O(n)，n為整個網?所包含的感測器?目。 接著將各距?予以平方，產生距?平方矩陣P3 (2)。 2)雙中心演算法(double centering)計算內積矩陣JJPB)2(21?，其中nIJ11?，所得的將是各點座標向?的內積矩陣，又稱為雙中心矩陣，其原?如下回顧餘弦定?，三點i,j,k其三邊為,假設則的夾角為ikijjkikijjikddddd2/)(cos222?今定義2/)jk(22ik2ijjikdddb?（以矩陣表示，相當於JJPB)2(21?），則jikikikjikddb?cos?而此即為與的內積6。 3)解出B矩陣的特微值，取其中最大的m個，1m，找出相對應的m個特微向?e1em。 4)由於mEE?Bmm?，而且B=XX，?5。 2/1mmE?X?，可得各點座標X矩陣在我們的實驗當中，我們以台灣各大城市之間的距?為原始資?，計算各大城市的相對座標。 下表以矩陣P表示台灣各大城市之間的距?，單位為公?。 台?台中台南高雄花?台東台?0x中2000221340165272台南4132210123259167高雄5233401230340176花?2211652593400194台東4082721671761940距?平方距陣為?03763630976278897398416646437636011560067081272254884130976115600015129115600273529278896708115129048841170569739842722511560048841040000166464488412735291705694000000P (2)由於有?個城市，n=6，故矩陣J為?8333.01667.01667.01667.01667.01667.01667.08333.01667.01667.01667.01667.01667.01667.08333.01667.01667.01667.01667.01667.01667.08333.01667.01667.01667.01667.01667.01667.08333.01667.01667.01667.01667.01667.01667.08333.0111111111111111111111111111111111111*6110000001000000100000010000001000000111nIJ將矩陣J應用於P中心的內積矩陣B (2)矩陣，以轉換成雙?21176?19936?1023235126611184243158210231441522181163651575235792351222181568233081521409-67560661116365308156743-34524-1842415752140964731595928772318522357967560345242877281585J*P*J*21-B (2)由於?個城市是位於二維平面上，我們將B矩陣?個特微值中取最大的?個，並取其相對應的特微向?如下?.0?.0?5767.05011.01345.04106.04758.00569.0,2541xx.05569.028902298.06700.0,2843,1816422121ee?最後應用市之點座標2/1mmE?X?，可得?個城?108?123?285?.0?.0?2533.973153.4911.843809.856864.223358.2372448.691792.2241.809225.975892.95269.284300181640*5767.025415001.0xx.01345.05569.04106.028904758.02298.00569.06700.0X圖2顯示各城市所在之位置。 由於此圖僅由各點間的距?而得，故可任意旋轉或鏡射，仍符合距?的條件。 圖2使用MDS模擬結果經過適當的旋轉和鏡射，得到正確的相對位置。 圖3經線性轉換之結果應用以上的方法，當得知感測器距?資訊後，經過MDS演算法可得整個網?的相對座標位置。 我們還需要具有絕對位置資訊的地標（對二維平面而言需要三點），以?將未定位裝置的相對位置，?用線性轉換轉成絕對位置，其方法如下當網?中存在三個以上的地標時，運算結束後，每一個地標會同時擁有一組相對位置和一組絕對位置。 這時我們可使用最小平方法，使地標的絕對位置與經過線性轉換（旋轉和鏡射）後的相對位置的平方差為最小。 如此即可得整個網?的絕對位置。 本篇?文介紹一個在感測器網?環境中的定位演算法MDS，由感測器在彼此交換資訊後，可得各感測器間的距?矩陣，經過MDS演算法可得整個網?的相對座標位置，再由地標點的資訊即可獲得絕對位置。 此一方法的優點在於避免手動設定所耗費龐大的時間以及人?資源，甚至人為疏失；另一面也避免在每個感測器上安裝GPS接收器導致大幅提升感測器的造價，以及無法在室內使用的缺點。 本演算法在模擬的結果中，呈現?好的效果。 1D.Niculescu andB.Nath,“Ppositioning inAd Hocsensor works”,IEEE Network,xx.2Y.Shang,W.Ruml andY.Zhang,Localization fromMere Connectivity,Proceedings ofthe10th annualinternational conferenceon Mobileputing andworking,xx.3Y.Shang andW.Ruml,Improved MDS-based Localization,In IEEEInfoxx,Hong Kong,Marchxx.4Florian Wickelmaier,“an introductionto MDS”,perception.inrialpe