59基于無(wú)線傳感器網(wǎng)絡(luò)的一種可擴(kuò) 展的定位技術(shù)

1、基于無(wú)線傳感器網(wǎng)絡(luò)的一種可擴(kuò)基于無(wú)線傳感器網(wǎng)絡(luò)的一種可擴(kuò) 展的定位技術(shù)展的定位技術(shù) scalable localization in wireless sensor networksmuralidhar medidi, roger a. slaaen, yuanyuan zhou, christopher j. mallery,and sirisha medidischool of electrical engineering and computer sciencewashington state universitypullman, wa 99164-2752logo摘要abstract：

2、localization, an important challenge in wireless sensor networks,is the process of sensor nodes self-determining their position. the diculty encountered is in cost-eectively providing acceptable accuracy in localization. the potential for the deployment of high density networks in the near future ma

3、kes scalability a critical issue in localization.in this paper we propose cluster-based localization , which provides eective localization suitable for large and highly-dense networks. cbl utilizes both a computationally-intensive localization technique( multidimensional scaling (mds) and a less int

4、ensivetrilateration to achieve balance between performance and cost. 定位作為無(wú)線傳感器網(wǎng)絡(luò)的重要技術(shù)挑戰(zhàn)之一，它由傳感器節(jié)點(diǎn)間的自我處理來(lái)定位的。它的難點(diǎn)就是要在低功耗的基礎(chǔ)上實(shí)現(xiàn)準(zhǔn)確定位，可擴(kuò)展的高密度傳感器網(wǎng)絡(luò)的能耗調(diào)節(jié)是未來(lái)研究的重點(diǎn)。在本文中，我們提出了cluster-based localization (cbl)基于簇的定位方法，這種定位方法能夠有效地應(yīng)用于大規(guī)模且高密度的傳感器網(wǎng)絡(luò)。cbl綜合利用了多邊精確測(cè)算技術(shù)（如mds）和三邊側(cè)量技術(shù)兩者的優(yōu)點(diǎn)，來(lái)實(shí)現(xiàn)性能和功耗之間的平衡，它能通過(guò)擴(kuò)展簇類來(lái)克服傳感器網(wǎng)絡(luò)

5、的局部故障。仿真結(jié)果顯示，cbl減少了節(jié)點(diǎn)的計(jì)算量和通信量，但是節(jié)點(diǎn)的位置準(zhǔn)確度卻沒(méi)減少。 logo本文的結(jié)構(gòu)本文的結(jié)構(gòu) 第一部分：引言。第二部分是講目前無(wú)線傳感器網(wǎng)絡(luò)定位的相關(guān)技術(shù)與研究。第三部分主要介紹了本文提出的cbl定位技術(shù)的構(gòu)造和特點(diǎn)。第四部分：對(duì)cbl的性能評(píng)估及與以往定位技術(shù)的比較。第五部分是本文的結(jié)論。 logo引言 無(wú)線傳感器網(wǎng)絡(luò)(wsn)因具有高的魯棒性、準(zhǔn)確性、靈活性及智能化等優(yōu)點(diǎn)，被認(rèn)為是未來(lái)惡劣戰(zhàn)場(chǎng)環(huán)境中監(jiān)控?cái)澄译p方兵力、裝備和物資狀態(tài)以及完成目標(biāo)協(xié)同檢測(cè)等關(guān)鍵應(yīng)用技術(shù)之一，已得到國(guó)內(nèi)外研究者的高度重視。隨著無(wú)線傳感器規(guī)模越來(lái)越大，傳感器網(wǎng)絡(luò)的密度能達(dá)到每平方米有幾百

6、個(gè)節(jié)點(diǎn)，高密度的wsn中的節(jié)點(diǎn)位置需要可擴(kuò)展的定位方法來(lái)實(shí)現(xiàn)。 logo引言v in this paper we propose a scalable hop-based localization technique called cluster-based localization (cbl). cbls use of clustering is motivated by the need for scalability and eciency. scalability is gained by, rst using an expensive but accurate localizatio

7、n technique on a small subset of the nodes in the，this work was supported in part by nsf grant network. the derived position estimates for the chosen subset will be used as referenceswhen localizing the remaining nodes. this approach leads to a signicant reduction in the computation required to loca

8、lize the entire network. 在本文中我們提出了一種基于跳數(shù)的可擴(kuò)展的定位技術(shù)cbl。在cbl中，使用簇類可以使得整個(gè)網(wǎng)絡(luò)可擴(kuò)展且效率高?？蓴U(kuò)展是指，首先在一小塊區(qū)域的節(jié)點(diǎn)里使用一種能耗高但定位精確度高的技術(shù)來(lái)定位，接著其臨近區(qū)域節(jié)點(diǎn)的位置就其已經(jīng)定位好的節(jié)點(diǎn)來(lái)作參考以確定自己的位置，整個(gè)網(wǎng)絡(luò)就是這樣逐層逼近來(lái)定位的。logo2. 相關(guān)的定位技術(shù)相關(guān)的定位技術(shù) 這一部分主要是羅列了目前幾種典型的無(wú)線傳感器網(wǎng)絡(luò)定位的相關(guān)技術(shù)。定位技術(shù)通常分為兩大類：（1）基于測(cè)距的定位技術(shù)：通過(guò)測(cè)量鄰居節(jié)點(diǎn)間的距離來(lái)確定節(jié)點(diǎn)的位置。（2）基于跳數(shù)的定位技術(shù)：無(wú)需用專門的測(cè)量設(shè)備來(lái)測(cè)得節(jié)點(diǎn)間的

9、距離，它認(rèn)為節(jié)點(diǎn)間的距離近似等于其在最短傳輸路徑上的跳數(shù)。 基于測(cè)距的定位技術(shù)有以下幾種：gps全球定位系統(tǒng)、aps定位（一種分布式定位技術(shù)）、loran（long range navigation）是一種地區(qū)導(dǎo)航系統(tǒng)、rss方式定位系統(tǒng)（如radar定位系統(tǒng)利用指紋識(shí)別技術(shù)來(lái)進(jìn)行定位，從而解決了定位移動(dòng)計(jì)算設(shè)備的問(wèn)題），使用toa/tdoa方式定位的系統(tǒng)（bat system和cricket）、混合定位系統(tǒng)（如calamari 和ahlos）。logo3. cbl定位技術(shù)定位技術(shù) to localize all sensor nodes accurately, the localizatio

10、n process usually involves computationally-intensive procedures, e.g., mds that has o(n3) computational complexity .since sensor nodes are expected to be resource-constrained and networks to be large and dense, light-weight localization algorithms that achieve decent accuracy and high scalability ar

11、e desirable. therefore, we attempt to address the trade-os between accuracy and scalability, so as to make our localization algorithm, cbl, a practical solution for sensor network applications. 為了能準(zhǔn)確定位整個(gè)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)，定位過(guò)程通常需要經(jīng)過(guò)精密的計(jì)算。因?yàn)閭鞲衅鞴?jié)點(diǎn)希望被設(shè)計(jì)成資源消耗低且網(wǎng)絡(luò)規(guī)模要求越來(lái)越大且密度也越來(lái)越高，所有具有高定準(zhǔn)確度且高可擴(kuò)展性的低負(fù)載的定位算法值得我們研究。因此，

12、我們?cè)O(shè)計(jì)了cbl算法，這種定位算法能有效應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)中。 logo3. cbl定位技術(shù)定位技術(shù) cbl adopts a hierarchical idea to perform the whole localization procedure,i.e., instead of regarding the whole network as a at topology in which all nodes share the same localization procedure as in most existing localization algorithms,we deliber

13、ately separate the nodes into two types, and apply dierent localization approaches on them to improve scalability as well as ensure accuracy. the rst type of nodes are representatives that account for a small portion of the nodes in the whole network. cbl采用了一種逐級(jí)定位的思想來(lái)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的定位過(guò)程，以代替以往算法的所有節(jié)點(diǎn)都是同一定位過(guò)程

14、。我們把節(jié)點(diǎn)分成兩類，并且運(yùn)用不同的定位逼近法來(lái)改進(jìn)這兩類節(jié)點(diǎn)的可擴(kuò)展性和準(zhǔn)確性。第一種節(jié)點(diǎn)類型是代表一小塊區(qū)域節(jié)點(diǎn)的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)是被選取出來(lái)的能正確反映網(wǎng)絡(luò)性能的節(jié)點(diǎn)，其定位采用復(fù)雜但準(zhǔn)確的定位算法，這種定位算法能從根本上改進(jìn)整個(gè)網(wǎng)絡(luò)定位的準(zhǔn)確性。除了簇頭節(jié)點(diǎn)剩下來(lái)的節(jié)點(diǎn)就是另一種節(jié)點(diǎn)類型，這類大眾節(jié)點(diǎn)以簇頭節(jié)點(diǎn)為參考，采用低負(fù)載的定位過(guò)程。使用這些機(jī)制，cbl定位算法準(zhǔn)確度相當(dāng)好，且計(jì)算量少，通信量也少。 logo3.1 簇頭選取簇頭選取 因?yàn)榇仡^節(jié)點(diǎn)最先被定位并給剩余簇內(nèi)節(jié)點(diǎn)做定位參考，所以它們必須是網(wǎng)絡(luò)中性能好的節(jié)點(diǎn)。還有，簇頭選取過(guò)程要低負(fù)載以確保整個(gè)網(wǎng)絡(luò)的可擴(kuò)展性。因此，cb

15、l算法中，我們應(yīng)用了一種簡(jiǎn)單的單跳的小范圍簇類算法來(lái)選取簇頭。這種算法運(yùn)用單跳確保了算法的低功耗，同時(shí)小范圍性使每一個(gè)簇節(jié)點(diǎn)都能公平地被選取為簇頭。 我們假設(shè)每一個(gè)節(jié)點(diǎn)都有一個(gè)唯一的id號(hào)，為了進(jìn)行簇的分類，開(kāi)始時(shí)每一個(gè)節(jié)點(diǎn)都同鄰居節(jié)點(diǎn)進(jìn)行通信以得到節(jié)點(diǎn)的單跳距離。接著，假定在鄰居節(jié)點(diǎn)中其id號(hào)最大的節(jié)點(diǎn)中的任一節(jié)點(diǎn)為簇頭，或者等待其比較完整個(gè)簇的節(jié)點(diǎn)來(lái)選取id號(hào)最大的那個(gè)節(jié)點(diǎn)為簇頭。只要選取出了簇頭節(jié)點(diǎn)，其將同鄰居節(jié)點(diǎn)通信以建立自己的簇。 logo3.1 簇頭選取簇頭選取 圖1.a描述了隨機(jī)的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，節(jié)點(diǎn)間相互連接。圖1.b表示簇類網(wǎng)絡(luò)結(jié)構(gòu)。圖1.c表示了各簇群之間的網(wǎng)絡(luò)連接

16、。 logo3.2 cluster head localization 簇頭定位簇頭定位 chs are taken as representatives and their localization accuracies have great impact on the overall localization accuracy. since chs usually account for a small portion of the whole network, it is aordable to apply complex localization algorithms to estim

17、ate chs positions. further, we want to apply a hop-based algorithm to localize chs so as to improve cbls applicability. 簇頭能影響整個(gè)網(wǎng)絡(luò)定位的準(zhǔn)確度，因此，簇頭通常是在一小塊區(qū)域網(wǎng)絡(luò)中使用復(fù)雜并精確的定位算法來(lái)確定簇頭的節(jié)點(diǎn)位置。還有，我們想用一種基于單跳的定位算法來(lái)定位簇頭節(jié)點(diǎn)以便能改進(jìn)cbl算法的適用性。基于這些考慮，我們選擇mds技術(shù)來(lái)定位簇頭，因?yàn)榛趩翁膍ds定位算法mds-map被證明它的定位準(zhǔn)確度非常高。cbl使用類似逼近算法的方法來(lái)定位簇頭節(jié)點(diǎn)，然而在cb

18、l算法中，只有簇頭定位才用到mds計(jì)算，因此計(jì)算量不是很大。 logo3.3 cluster member localization 簇成員定位簇成員定位 after determining each chs coordinates, we will take chs as reference nodes to estimate the remaining nodes, or cms, positions. we choose the least-square triangulation technique for cms localization to obtain decent accur

19、acy with low computation overhead. in particular, each ch rst calculates the euclidean distances to the chs in its neighboring clusters, then estimates the average hopdistance by using these euclidean distances and corresponding hop length. 當(dāng)簇頭節(jié)點(diǎn)的位置已經(jīng)確定下來(lái)后，我們就能用簇頭節(jié)點(diǎn)做為簇成員節(jié)點(diǎn)的參考定位點(diǎn)。我們采用最小二乘三邊定位法來(lái)準(zhǔn)確得到簇成

20、員節(jié)點(diǎn)的位置信息。特別要注意的，每一個(gè)簇頭首先要計(jì)算出其與鄰居簇頭節(jié)點(diǎn)的幾何距離，然后計(jì)算其單跳距離。接著，每一個(gè)簇頭廣播一個(gè)定位信息給它的簇內(nèi)成員節(jié)點(diǎn)，這個(gè)定位信息包括個(gè)跳數(shù)（用來(lái)評(píng)價(jià)信息量和定位準(zhǔn)確度之間的平衡關(guān)系），每一個(gè)簇類節(jié)點(diǎn)至少要接到三個(gè)不同簇頭節(jié)點(diǎn)發(fā)來(lái)的定位信息才能通過(guò)三邊定位法來(lái)確定自己的節(jié)點(diǎn)位置。如果一個(gè)簇內(nèi)成員節(jié)點(diǎn)接收到超過(guò)三個(gè)簇頭節(jié)點(diǎn)發(fā)來(lái)的定位信息的話，就使用最小方差法來(lái)定位。 logo4 performance evaluation 性能評(píng)價(jià) cbl was implemented in ns-2 26, and our main goals when evaluati

21、ng its performance were to determine the accuracy, scalability, and how irregularities in a network topology will aect performance. the simulation environment parameters are: area = 100 100m2; 100 nodes; transmission range = 15m and cluster size varied from 1 to 10. 這里，我們主要對(duì)cbl定位算法的準(zhǔn)確度、可擴(kuò)展性和不規(guī)則的網(wǎng)絡(luò)拓?fù)?/p>

22、結(jié)構(gòu)將會(huì)怎樣影響其定位效果這三項(xiàng)性能進(jìn)行評(píng)估。仿真環(huán)境是：網(wǎng)絡(luò)面積是100*100平方米、100個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)發(fā)送信息的范圍為15米、簇的大小從1到10不等。我們使用常見(jiàn)的以米制單位來(lái)衡量定位精確度。logo4.1 隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的性能隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的性能 圖2描述了隨機(jī)拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)的定位準(zhǔn)確度，圖2.a是簇頭的定位準(zhǔn)確度，圖b是整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)定位的準(zhǔn)確度。結(jié)果顯示隨著簇大小的增加，網(wǎng)絡(luò)節(jié)點(diǎn)的定位準(zhǔn)確度并沒(méi)有明顯的減少。logo4.2 基于簇類的網(wǎng)絡(luò)結(jié)構(gòu)基于簇類的網(wǎng)絡(luò)結(jié)構(gòu) 圖3顯示了，同隨機(jī)拓?fù)渚W(wǎng)絡(luò)一樣，改變簇的大小對(duì)定位的準(zhǔn)確性影響不大。另外，和mds-map相比，cbl的準(zhǔn)確度稍微低點(diǎn)，但是其計(jì)算量少。同dv-hop相比，cbl在不規(guī)則的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中定位準(zhǔn)確度比其高。這就是為什么dv-hop通常只應(yīng)用于均勻且規(guī)則的網(wǎng)絡(luò)定位。logo4.3 節(jié)點(diǎn)密度不規(guī)則的網(wǎng)絡(luò)節(jié)點(diǎn)密度不規(guī)則的網(wǎng)絡(luò) 這里我們使用