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

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

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

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

9、距離，它認為節(jié)點間的距離近似等于其在最短傳輸路徑上的跳數(shù)。 基于測距的定位技術(shù)有以下幾種：gps全球定位系統(tǒng)、aps定位（一種分布式定位技術(shù)）、loran（long range navigation）是一種地區(qū)導(dǎo)航系統(tǒng)、rss方式定位系統(tǒng)（如radar定位系統(tǒng)利用指紋識別技術(shù)來進行定位，從而解決了定位移動計算設(shè)備的問題），使用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. 為了能準確定位整個傳感器網(wǎng)絡(luò)的節(jié)點，定位過程通常需要經(jīng)過精密的計算。因為傳感器節(jié)點希望被設(shè)計成資源消耗低且網(wǎng)絡(luò)規(guī)模要求越來越大且密度也越來越高，所有具有高定準確度且高可擴展性的低負載的定位算法值得我們研究。因此，

12、我們設(shè)計了cbl算法，這種定位算法能有效應(yīng)用于無線傳感器網(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采用了一種逐級定位的思想來實現(xiàn)整個網(wǎng)絡(luò)的定位過程，以代替以往算法的所有節(jié)點都是同一定位過程

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

15、l算法中，我們應(yīng)用了一種簡單的單跳的小范圍簇類算法來選取簇頭。這種算法運用單跳確保了算法的低功耗，同時小范圍性使每一個簇節(jié)點都能公平地被選取為簇頭。 我們假設(shè)每一個節(jié)點都有一個唯一的id號，為了進行簇的分類，開始時每一個節(jié)點都同鄰居節(jié)點進行通信以得到節(jié)點的單跳距離。接著，假定在鄰居節(jié)點中其id號最大的節(jié)點中的任一節(jié)點為簇頭，或者等待其比較完整個簇的節(jié)點來選取id號最大的那個節(jié)點為簇頭。只要選取出了簇頭節(jié)點，其將同鄰居節(jié)點通信以建立自己的簇。 logo3.1 簇頭選取簇頭選取 圖1.a描述了隨機的無線傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)，節(jié)點間相互連接。圖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. 簇頭能影響整個網(wǎng)絡(luò)定位的準確度，因此，簇頭通常是在一小塊區(qū)域網(wǎng)絡(luò)中使用復(fù)雜并精確的定位算法來確定簇頭的節(jié)點位置。還有，我們想用一種基于單跳的定位算法來定位簇頭節(jié)點以便能改進cbl算法的適用性。基于這些考慮，我們選擇mds技術(shù)來定位簇頭，因為基于單跳的mds定位算法mds-map被證明它的定位準確度非常高。cbl使用類似逼近算法的方法來定位簇頭節(jié)點，然而在cb

18、l算法中，只有簇頭定位才用到mds計算，因此計算量不是很大。 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. 當簇頭節(jié)點的位置已經(jīng)確定下來后，我們就能用簇頭節(jié)點做為簇成員節(jié)點的參考定位點。我們采用最小二乘三邊定位法來準確得到簇成

20、員節(jié)點的位置信息。特別要注意的，每一個簇頭首先要計算出其與鄰居簇頭節(jié)點的幾何距離，然后計算其單跳距離。接著，每一個簇頭廣播一個定位信息給它的簇內(nèi)成員節(jié)點，這個定位信息包括個跳數(shù)（用來評價信息量和定位準確度之間的平衡關(guān)系），每一個簇類節(jié)點至少要接到三個不同簇頭節(jié)點發(fā)來的定位信息才能通過三邊定位法來確定自己的節(jié)點位置。如果一個簇內(nèi)成員節(jié)點接收到超過三個簇頭節(jié)點發(fā)來的定位信息的話，就使用最小方差法來定位。 logo4 performance evaluation 性能評價 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. 這里，我們主要對cbl定位算法的準確度、可擴展性和不規(guī)則的網(wǎng)絡(luò)拓撲

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