WSN中三維算法的綜述-專業(yè)文獻(xiàn)綜述

PAGEPAGE１１專業(yè)文獻(xiàn)綜述題目：WSN中三維算法的綜述姓名：學(xué)院：信息科學(xué)技術(shù)學(xué)院專業(yè)：網(wǎng)絡(luò)工程班級：學(xué)號：導(dǎo)教師：職稱：講師年12月15日南京農(nóng)業(yè)大學(xué)教務(wù)處制WSN中三維算法的綜述作者：指導(dǎo)教師：摘要：WSN是21世紀(jì)極具發(fā)展前景的技術(shù)，隨著技術(shù)的不斷成熟和進(jìn)步，各行各業(yè)對WSN的應(yīng)用需求正在與日俱增。特別是近些年來，隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，WSN已經(jīng)成為當(dāng)今生活中不可或缺的一部分。在WSN的眾多應(yīng)用中，涉及網(wǎng)絡(luò)節(jié)點(diǎn)的定位及其應(yīng)用已成為業(yè)界的一個(gè)研究重點(diǎn)。當(dāng)前，針對傳感器網(wǎng)絡(luò)的定位算法主要集中在二維的應(yīng)用，涉及三維空間定位的算法研究較少，而在WSN的實(shí)際應(yīng)用中，諸如人員和目標(biāo)定位、環(huán)境與氣候檢測等問題，必須要解決傳感器網(wǎng)絡(luò)的三維定位問題[1]。本文首先介紹了WSN網(wǎng)絡(luò)節(jié)點(diǎn)定位基本原理，然后以此為基礎(chǔ)對幾種定位算法進(jìn)行了詳細(xì)的介紹，最后總結(jié)了WSN中三維算法的發(fā)展前景及所面臨的問題。關(guān)鍵詞：WSN；空間定位；網(wǎng)絡(luò)節(jié)點(diǎn)；三維算法Theoverviewof3DAlgorithminWSNAuthor：ZHUSheng-keAdviser：WANGHao-yunAbstract：Intwenty-firstCentury，WSNisthemostpromisingtechnology，astechnologycontinuestomatureandprogress，allwalksoflifetotheWSNapplicationdemandisIncreasing.Especiallyinrecentyears，withthedevelopmentofInternettechnology，WSNhasbecometheindispensablepartinthelife.InWSNnumerousapplication，relatingtothenetworknodepositioninganditsapplicationintheindustryhasbecomearesearchfocus.Atpresent，thelocalizationalgorithmforsensornetworksarefocusedontheapplicationof2D，theviewabout3Dpositioningalgorithmisless，andinWSNapplications，suchaspersonnelandtargetlocation，climateandenvironmentdetectionissues，wemustsolvethesensornetworklocalizationproblem.ThisarticlefirstintroducesthebasicprincipleofWSNnetworknodelocation，andthenintroducessomelocationalgorithmsindetail，finallysummarizestheWSN3Dalgorithmsdevelopmentprospectsandproblems.Keywords：WSN；Spatialorientation；Networknode；3DAlgorithm引言：物理世界的信息中，位置信息是一個(gè)十分重要的屬性，有些信息如何采集時(shí)不包含有位置屬性，那么這一信息可能將毫無意義。有數(shù)據(jù)統(tǒng)計(jì)顯示，無線傳感器網(wǎng)絡(luò)中用戶所需的數(shù)據(jù)服務(wù)與位置有關(guān)的信息約占80%，因此，無線傳感器網(wǎng)絡(luò)要想取得更廣泛的應(yīng)用，如何實(shí)現(xiàn)節(jié)點(diǎn)位置的精確定位是其必然要解決的重要挑戰(zhàn)之一。在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)中，根據(jù)節(jié)點(diǎn)是否已知自身的位置，把傳感器節(jié)點(diǎn)分為信標(biāo)節(jié)點(diǎn)(或錨節(jié)點(diǎn))和未知節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)節(jié)點(diǎn)中所占比例往往比較小，它們一般通過攜帶GPS定位設(shè)備等手段獲得自身的精確位置。信標(biāo)節(jié)點(diǎn)是未知節(jié)點(diǎn)進(jìn)行定位的參考點(diǎn)。傳感器網(wǎng)絡(luò)中，除了信標(biāo)節(jié)點(diǎn)外，其它節(jié)點(diǎn)都是未知節(jié)點(diǎn)，未知節(jié)點(diǎn)可以通過一些定位算法，利用信標(biāo)節(jié)點(diǎn)的位置信息來確定自身的位置[7]。1無線傳感器網(wǎng)絡(luò)定位的基本原理1.1無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)圖1.1圖1.1是一個(gè)典型的無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)。網(wǎng)絡(luò)由(sensornode)、匯聚節(jié)點(diǎn)(sink)、Internet或通信衛(wèi)星、任務(wù)管分構(gòu)成[9]。大量的傳感器節(jié)點(diǎn)隨機(jī)散布在傳感器區(qū)域(SenSOrfield)近，通過自組織方式構(gòu)成網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)監(jiān)測的數(shù)據(jù)沿著其它傳感地進(jìn)行傳輸，在傳輸過程中監(jiān)測數(shù)據(jù)可能被多個(gè)節(jié)點(diǎn)處理，經(jīng)過多跳聚節(jié)點(diǎn)，最后通過互聯(lián)網(wǎng)或衛(wèi)星到達(dá)管理節(jié)點(diǎn)。用戶通過管理節(jié)點(diǎn)對網(wǎng)絡(luò)進(jìn)行配置和管理，發(fā)布監(jiān)測任務(wù)以及收集監(jiān)測數(shù)據(jù)。1.2無線傳感器網(wǎng)絡(luò)的功能結(jié)構(gòu)圖1.2圖1.2在一個(gè)比較抽象的級別上討論傳感器網(wǎng)絡(luò)的功能結(jié)構(gòu)，其中共分為五層：(1)物理層，提供簡單但健壯的信號調(diào)制和無線收發(fā)技術(shù)；(2)數(shù)據(jù)鏈路層，負(fù)責(zé)數(shù)據(jù)成幀，幀監(jiān)測，媒體訪問和差錯(cuò)控制；(3)網(wǎng)絡(luò)層，主要負(fù)責(zé)路由生成與路由選擇；(4)傳輸層，負(fù)責(zé)數(shù)據(jù)流的傳輸控制，是保證通信服務(wù)質(zhì)量的重要部分[3]；(5)應(yīng)用層，包括一系列基于監(jiān)測任務(wù)的應(yīng)用層軟件。能量管理平臺管理傳感器節(jié)點(diǎn)如何使用能源，在各個(gè)協(xié)議層都需要考慮節(jié)省能量；移動管理平臺監(jiān)測并注冊傳感器節(jié)點(diǎn)的移動，維護(hù)到匯聚節(jié)點(diǎn)的路由，使得傳感器節(jié)點(diǎn)能夠動態(tài)跟蹤其鄰居的位置；任務(wù)管理平臺在一個(gè)給定的區(qū)域內(nèi)平衡和調(diào)度監(jiān)測任務(wù)。1.3無線傳感器網(wǎng)絡(luò)定位的基本原理在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)中，根據(jù)節(jié)點(diǎn)是否已知自身的位置，把傳感器節(jié)點(diǎn)分為信標(biāo)節(jié)點(diǎn)(或錨節(jié)點(diǎn))和未知節(jié)點(diǎn)。信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)節(jié)點(diǎn)中所占比例往往比較小，它們一般通過攜帶GPS定位設(shè)備等手段獲得自身的精確位置。信標(biāo)節(jié)點(diǎn)是未知節(jié)點(diǎn)進(jìn)行定位的參考點(diǎn)。傳感器網(wǎng)絡(luò)中，除了信標(biāo)節(jié)點(diǎn)外，其它節(jié)點(diǎn)都是未知節(jié)點(diǎn)，未知節(jié)點(diǎn)可以通過一些定位算法，利用信標(biāo)節(jié)點(diǎn)的位置信息來確定自身的位置[4]。定位算法的基本原理是直接或間接測量節(jié)點(diǎn)之間的距離、方位或者其它連接性信息，然后再根據(jù)這些信息計(jì)算網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的位置，最后對得到的位置值進(jìn)行修正，提高定位精度減小誤差。2無線傳感器節(jié)點(diǎn)定位算法分析2.1無線傳感器節(jié)點(diǎn)定位算法分類對于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位的研究，國內(nèi)外學(xué)者獲得了豐富的研究成果，提出了許多定位解決方案和算法。盡管無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法的分類還未有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)，但定位算法通常有以下幾種分類[5]：1．分布式的定位算法和集中式的定位算法對基礎(chǔ)設(shè)施的依賴程度可把定位方法分為集中定位方式和分布定位方式。分布式的定位算法，通常指定位算法在本地節(jié)點(diǎn)工作，節(jié)點(diǎn)與節(jié)點(diǎn)之間無直接干擾，所有節(jié)點(diǎn)可以并發(fā)的計(jì)算自己的位置。集中式的定位算法中，通常有一個(gè)計(jì)算能力和存儲能力相對較高的中心節(jié)點(diǎn)，所有節(jié)點(diǎn)將所有定位信息傳遞給該中心節(jié)點(diǎn)，中心節(jié)點(diǎn)集中計(jì)算網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)的位置，然后再通知每一個(gè)節(jié)點(diǎn)。2．基于測距技術(shù)的定位和非基于測距技術(shù)的定位算法根據(jù)定位過程中，定位算法是否測量實(shí)際節(jié)點(diǎn)之間的距離，把定位算法分為：基于測距的(range-based)定位算法和非基于測距(range-free)的定位算法。基于測距的定位算法是通過測量相鄰節(jié)點(diǎn)間的實(shí)際距離或角度來確定未知位置節(jié)點(diǎn)的位置，通常分為三步：測量距離或角度，定位和修正。非基于測距技術(shù)的定位算法則無需距離或角度信息，僅根據(jù)網(wǎng)絡(luò)連通性等信息即可實(shí)現(xiàn)。3．遞增式的定位算法和并發(fā)式的定位算法根據(jù)節(jié)點(diǎn)定位的先后次序不同，把定位算法分為：遞增式的定位算法和并發(fā)式的定位算法。遞增式的定位算法通常從錨節(jié)點(diǎn)開始，錨節(jié)點(diǎn)附近的節(jié)點(diǎn)首先開始定位，依次向外延伸，各節(jié)點(diǎn)逐次進(jìn)行定位，這類算法的主要缺點(diǎn)是定位過程中累積和傳播測量誤差；并發(fā)式的定位算法中所有的節(jié)點(diǎn)同時(shí)進(jìn)行位置估算。4．基于錨節(jié)點(diǎn)的定位算法和非基于錨節(jié)點(diǎn)的定位算法根據(jù)定位過程中是否使用錨節(jié)點(diǎn)，把定位算法分為：基于錨節(jié)點(diǎn)的定位算法和非基于錨節(jié)點(diǎn)的定位算法。前者在定位過程中，以錨節(jié)點(diǎn)作為定位中的參考點(diǎn)，各節(jié)點(diǎn)定位后產(chǎn)生整個(gè)絕對坐標(biāo)系統(tǒng)；后者則在無預(yù)先位置信息情況下，僅根據(jù)局部距離值來定位，關(guān)心節(jié)點(diǎn)間的相對位置。5．絕對定位與相對定位絕對定位是讓所有的待定位節(jié)點(diǎn)使用共同的參照系，其定位結(jié)果是一個(gè)全局性的標(biāo)準(zhǔn)坐標(biāo)位置，比如用經(jīng)度和緯度表示出來。對同一地理位置的節(jié)點(diǎn)進(jìn)行多次絕對定位，其定位結(jié)果將是一樣的。相對定位可以讓每個(gè)定位節(jié)點(diǎn)使用不同的參照系，通常是以網(wǎng)絡(luò)中的部分節(jié)點(diǎn)為參考，建立整個(gè)網(wǎng)絡(luò)的相對坐標(biāo)系統(tǒng)。在一定條件下，絕對定位結(jié)果可以轉(zhuǎn)換為相對定位結(jié)果。6．粗粒度與細(xì)粒度依據(jù)定位所需信息的粒度可將定位算法和系統(tǒng)分為兩類：根據(jù)信號強(qiáng)度或時(shí)間等來度量與錨節(jié)點(diǎn)距離的稱為細(xì)粒度定位技術(shù)；根據(jù)與錨節(jié)點(diǎn)的接近度來度量的稱為粗粒度定位技術(shù)。其中細(xì)粒度又可細(xì)分為基于距離和基于方向性測量兩類。7．三角測量、場景分析和接近度定位定位技術(shù)也可分為三角測量、場景分析和接近度三類，其中三角測量和接近度定位分別與粗粒度和細(xì)粒度定位相似。而場景分析定位是根據(jù)場景特點(diǎn)來推斷目標(biāo)位置。通常被觀測的場景都有易于獲得、表示和對比的特點(diǎn)，如信號強(qiáng)度和圖像。2.2定位算法的性能評價(jià)指標(biāo)無線傳感器網(wǎng)絡(luò)定位算法的性能直接影響其可用性，如何評價(jià)它們是一個(gè)需要深入研究的問題。下面定性地討論幾個(gè)常用的評價(jià)定位系統(tǒng)和算法的標(biāo)準(zhǔn)[6]。定位精度：定位技術(shù)首要的評價(jià)指標(biāo)就是定位精度，一般用誤差值與節(jié)點(diǎn)無線射程的比例來表示，也有部分定位系統(tǒng)將網(wǎng)絡(luò)部署區(qū)域劃分為網(wǎng)格，其定位結(jié)果的精度也就是網(wǎng)格的大小。規(guī)模：不同定位系統(tǒng)或算法也可以在園區(qū)內(nèi)、建筑物內(nèi)、一層建筑物或僅一個(gè)房間內(nèi)實(shí)現(xiàn)定位。另外，給定一定數(shù)量的基礎(chǔ)設(shè)施或在一段時(shí)間內(nèi)，一種技術(shù)可以定位多少目標(biāo)也是一個(gè)重要的評價(jià)指標(biāo)。覆蓋率：覆蓋率是指可實(shí)現(xiàn)定位的未知節(jié)點(diǎn)與未知節(jié)點(diǎn)總數(shù)的比例。盡管密集部署是無線傳感器網(wǎng)絡(luò)的特點(diǎn)之一，但總會有一些不可達(dá)或連通度極低的未知節(jié)點(diǎn)存在，除這些節(jié)點(diǎn)，實(shí)現(xiàn)盡可能多的未知節(jié)點(diǎn)的精確定位也是自身定位算法和系統(tǒng)追求的目標(biāo)之一。容錯(cuò)性和自適應(yīng)性：通常定位系統(tǒng)和算法都需要比較理想的無線通信環(huán)境和可靠的網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)備，定位算法和系統(tǒng)的軟硬件必須具有很強(qiáng)的容錯(cuò)性和自適應(yīng)性，能夠通過自動調(diào)整或重構(gòu)糾正錯(cuò)誤、適應(yīng)環(huán)境、減小各種誤差的影響，提高定位精度。節(jié)點(diǎn)密度：在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)密度增大不僅意味著網(wǎng)絡(luò)部署費(fèi)用的增加，而且會因?yàn)楣?jié)點(diǎn)間的通信沖突問題帶來有限帶寬的阻塞。節(jié)點(diǎn)密度通常以網(wǎng)絡(luò)的平均連通度來表示。功耗：功耗是對WSN的設(shè)計(jì)和實(shí)現(xiàn)影響最大的因素之一。由于傳感器節(jié)點(diǎn)電池能量有限，因此在保證定位精度前提下，與功耗密切相關(guān)的定位所需的計(jì)算量、通信開銷、存儲開銷、時(shí)間復(fù)雜性是一組關(guān)鍵性指標(biāo)。代價(jià)：定位算法或系統(tǒng)的代價(jià)可以從幾個(gè)不同方面來評價(jià)。時(shí)間代價(jià)包括一個(gè)系統(tǒng)的安裝時(shí)間、配置時(shí)間、定位所需時(shí)間?？臻g代價(jià)包括一個(gè)定位算法或系統(tǒng)所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量、硬件尺寸等。資金代價(jià)則包括實(shí)現(xiàn)一種定位算法或系統(tǒng)的基礎(chǔ)設(shè)施、節(jié)點(diǎn)設(shè)備的總費(fèi)用。上述八項(xiàng)性能指標(biāo)不僅是評價(jià)無線傳感器網(wǎng)絡(luò)自身定位算法和系統(tǒng)的標(biāo)準(zhǔn)，也是其設(shè)計(jì)和實(shí)現(xiàn)的優(yōu)化目標(biāo)。為了達(dá)到這些目標(biāo)的優(yōu)化，有大量的研究工作需要完成。同時(shí)這些性能指標(biāo)又是相互關(guān)聯(lián)的，必須根據(jù)應(yīng)用的具體需要做出權(quán)衡，選擇和設(shè)計(jì)合適的定位算法或系統(tǒng)。2.3無線傳感器節(jié)點(diǎn)定位算法分析2.3.1距離無關(guān)三維定位算法在二維平面上，傳感器節(jié)點(diǎn)分布不均勻的情況下，經(jīng)典的Dv-Hop定位算法選擇距離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)的網(wǎng)絡(luò)平均每跳距離進(jìn)行定位計(jì)算，但這并不是該節(jié)點(diǎn)的最佳網(wǎng)絡(luò)平均每跳距離，例如一個(gè)未知節(jié)點(diǎn)一跳范圍內(nèi)有3個(gè)信標(biāo)節(jié)點(diǎn)，每個(gè)信標(biāo)節(jié)點(diǎn)所計(jì)算的網(wǎng)絡(luò)平均每跳距離都是不一樣的，而采用不同的網(wǎng)絡(luò)平均每跳距離所計(jì)算出來的坐標(biāo)跟實(shí)際坐標(biāo)的誤差大小不同，但肯定有一個(gè)誤差最小。在三維空間中，如圖2.3.1所示，傳感器網(wǎng)絡(luò)節(jié)點(diǎn)之間的關(guān)系更復(fù)雜，由于測距和定位計(jì)算誤差的增大，在三維空間直接應(yīng)用傳統(tǒng)的距離矢量定位算法將會導(dǎo)致更大的誤差。由于在Dv-Hop定位算法中，未知節(jié)點(diǎn)選擇的網(wǎng)絡(luò)平均每跳距離是其計(jì)算到信標(biāo)節(jié)點(diǎn)距離的基礎(chǔ)，因此網(wǎng)絡(luò)平均每跳距離選擇的好壞直接影響到節(jié)點(diǎn)定位誤差的大小[2]。本節(jié)所設(shè)計(jì)的距離無關(guān)三維定位算法可以為未知節(jié)點(diǎn)找到對于自身來說最佳的網(wǎng)絡(luò)平均每跳距離，從而有效地降低了測距誤差和定位計(jì)算誤差。極大地提高了算法的定位精度。距離無關(guān)三維定位算法主要分為兩步：第一步，網(wǎng)絡(luò)中每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)距離矢量算法，計(jì)算自己的網(wǎng)絡(luò)平均每跳距離，然后向網(wǎng)絡(luò)中的未知節(jié)點(diǎn)廣播。未知節(jié)點(diǎn)把收到的每一個(gè)網(wǎng)絡(luò)平均每跳距離保存到數(shù)組中；第二步，未知節(jié)點(diǎn)根據(jù)誤差的大小，在收到的所有網(wǎng)絡(luò)平均每跳距離中選擇一個(gè)最佳網(wǎng)絡(luò)平均每跳距離，然后根據(jù)此值來計(jì)算到信標(biāo)節(jié)點(diǎn)的距離，并進(jìn)行定位計(jì)算，從而使定位誤差降到最低。圖2.3.11．信標(biāo)節(jié)點(diǎn)計(jì)算平均每跳距離在網(wǎng)絡(luò)初始，每個(gè)信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播數(shù)據(jù)包，包含坐標(biāo)信息(xi，yi，zi)和初始跳數(shù)1，鄰居節(jié)點(diǎn)收到消息后把跳數(shù)加1后發(fā)給除接收節(jié)點(diǎn)之外的其它鄰居節(jié)點(diǎn)。未知節(jié)點(diǎn)收到消息后直接轉(zhuǎn)發(fā)，信標(biāo)節(jié)點(diǎn)收到消息后保存消息后在轉(zhuǎn)發(fā)，信標(biāo)節(jié)點(diǎn)某收到來自同一信標(biāo)節(jié)點(diǎn)的多個(gè)消息，則保留跳數(shù)最小的，丟棄其它消息。每個(gè)信標(biāo)節(jié)點(diǎn)計(jì)算平均每跳距離：di=（1）公式(1)中心表示信標(biāo)節(jié)點(diǎn)i與信標(biāo)節(jié)點(diǎn)j之間的最小跳數(shù)。信標(biāo)節(jié)點(diǎn)計(jì)算好di后以廣播的形式向未知節(jié)點(diǎn)發(fā)送。未知節(jié)點(diǎn)建立一個(gè)網(wǎng)絡(luò)平均每跳距離數(shù)組，在收到信標(biāo)節(jié)點(diǎn)發(fā)送的消息以后，把di值保存到網(wǎng)絡(luò)平均每跳距離數(shù)組中。2．求最佳網(wǎng)絡(luò)平均每跳距離未知節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)平均每跳距離和距離各個(gè)信標(biāo)節(jié)點(diǎn)的跳數(shù)，就可以算出距各信標(biāo)節(jié)點(diǎn)的距離，然后根據(jù)極大似然估計(jì)法可以算出自己的坐標(biāo)。當(dāng)然，未知節(jié)點(diǎn)選擇不同的網(wǎng)絡(luò)平均每跳距離后計(jì)算出來的坐標(biāo)值是不一樣的。哪個(gè)坐標(biāo)值更接近于其實(shí)際坐標(biāo)，無法直接得到結(jié)果。然而，該已定位的未知節(jié)點(diǎn)可以把自己的坐標(biāo)估計(jì)值發(fā)送給鄰近的信標(biāo)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)收到未知節(jié)點(diǎn)的坐標(biāo)后，把自己當(dāng)作未知節(jié)點(diǎn)，把該已定位未知節(jié)點(diǎn)當(dāng)作參與自己定位的一個(gè)參考信標(biāo)節(jié)點(diǎn)，來計(jì)算自己的估算坐標(biāo)，然后算出自己的實(shí)際坐標(biāo)和估算坐標(biāo)之間的誤差，并把誤差發(fā)送給已定位的未知節(jié)點(diǎn)[10]。未知節(jié)點(diǎn)根據(jù)多個(gè)信標(biāo)節(jié)點(diǎn)發(fā)送來的誤差值，利用加權(quán)計(jì)算公式算出最終誤差，并以此誤差為標(biāo)準(zhǔn)，選擇一個(gè)最佳網(wǎng)絡(luò)平均每跳距離。2.3.2基于聚類的三維定位算法當(dāng)網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)個(gè)數(shù)較少，或者分布不均勻時(shí)，網(wǎng)絡(luò)中的很多未知節(jié)點(diǎn)因無法獲得足夠的信標(biāo)節(jié)點(diǎn)參與其定位計(jì)算，而無法實(shí)現(xiàn)定位。針對這一問題，本節(jié)設(shè)計(jì)了基于聚類的三維定位算法，該算法使用距離無關(guān)的測距技術(shù)，通過把傳感器網(wǎng)絡(luò)劃分為若干簇，對簇內(nèi)節(jié)點(diǎn)實(shí)現(xiàn)相對定位，然后利用三維坐標(biāo)轉(zhuǎn)換，對相鄰簇進(jìn)行合并，最終形成一個(gè)全局坐標(biāo)系。當(dāng)網(wǎng)絡(luò)中有3個(gè)以上信標(biāo)節(jié)點(diǎn)時(shí)，可以對未知節(jié)點(diǎn)實(shí)現(xiàn)絕對定位。算法的主要思想：(1)首先通過分簇過程把網(wǎng)絡(luò)劃分為若干簇；(2)然后在各簇內(nèi)建立局部坐標(biāo)系，對未知節(jié)點(diǎn)進(jìn)行局部相對定位；(3)最后以第一簇為核心，把其它簇逐步合并到第一簇中，建立全局坐標(biāo)系，并在需要的時(shí)候進(jìn)行三維坐標(biāo)轉(zhuǎn)換，對未知節(jié)點(diǎn)進(jìn)行絕對定位。1．初始化與分簇過程分簇過程主要包括：(1)網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)計(jì)算網(wǎng)絡(luò)平均每跳距離，然該值發(fā)送給未知節(jié)點(diǎn)，這樣做便于分簇以后計(jì)算簇內(nèi)各節(jié)點(diǎn)之間的距離；(2)網(wǎng)絡(luò)中選擇第一個(gè)簇的簇頭節(jié)點(diǎn)，并建立第一個(gè)簇；(3)第一簇的簇頭節(jié)點(diǎn)其它簇的簇頭選舉。收到選舉消息的節(jié)點(diǎn)進(jìn)行選舉，選舉結(jié)束后啟動三跳以節(jié)點(diǎn)進(jìn)行新的簇頭節(jié)點(diǎn)的選舉，直至網(wǎng)絡(luò)被劃分為若干簇后終止。2．簇內(nèi)建立局部坐標(biāo)系在上述分簇過程結(jié)束以后，傳感器網(wǎng)絡(luò)中的各個(gè)簇便可以開始建立自己的局部坐標(biāo)系。在局部坐標(biāo)系的建立過程中，采用MDS-MDP技術(shù)，該技術(shù)在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中已被廣泛采用，其默認(rèn)情況下是多維的，在本文中默認(rèn)為三維情況下。選擇MDS-MDP技術(shù)的主要原因是：由于信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中分布不均勻，分簇算法不能保證每個(gè)簇內(nèi)有足夠多的信標(biāo)節(jié)點(diǎn)。在某些簇中，由于信標(biāo)節(jié)點(diǎn)較少或者根本沒有信標(biāo)節(jié)點(diǎn)，導(dǎo)致無法使用四邊測量法和極大似然估計(jì)法對未知節(jié)點(diǎn)進(jìn)行定位。而MDS-MDP技術(shù)對信標(biāo)節(jié)點(diǎn)數(shù)量要求不高，只需要知道每個(gè)簇中節(jié)點(diǎn)之間的相互距離，就可以計(jì)算出簇內(nèi)節(jié)點(diǎn)的相對坐標(biāo)，而這個(gè)要求是很容易達(dá)到的，因?yàn)樵诜执仉A段之前，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都已經(jīng)獲取了網(wǎng)絡(luò)平均每跳距離，通過最短路徑算法，如Dijkstra算法，簇中的每個(gè)節(jié)點(diǎn)都可以求出到簇內(nèi)其它節(jié)點(diǎn)的最短跳段距離。局部坐標(biāo)系建立的具體做法是：利用Dijkstra算法，簇中每個(gè)節(jié)點(diǎn)可以獲得到簇內(nèi)其它節(jié)點(diǎn)的最小跳數(shù)，然后利用平均每跳距離，求出到簇中其它節(jié)點(diǎn)的距離。然后把這些數(shù)據(jù)都發(fā)送給自己的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)收到所有簇成員發(fā)送的消息后，建立簇內(nèi)的距離矩陣。距離矩陣建立以后，根據(jù)MDS-MDP技術(shù)，對該矩陣進(jìn)行求解，便可以得到簇中各節(jié)點(diǎn)的相對坐標(biāo)。3．建立全局坐標(biāo)系各簇建立局部坐標(biāo)系以后，可以從第一簇開始，逐步合并相鄰的簇，以建立全局坐標(biāo)系，由于上述的分簇過程保證了任一簇至少與一個(gè)相鄰的簇有3個(gè)以上的公共節(jié)點(diǎn)，從而使任一簇均能歸并到第一簇中。簇之間的合并主要通過它們之間的公共節(jié)點(diǎn)，利用公共節(jié)點(diǎn)的兩個(gè)坐標(biāo)值(分屬于不同的簇的坐標(biāo)值)，求出三維坐標(biāo)轉(zhuǎn)換公式的幾個(gè)參數(shù)值，然后利用這些參數(shù)，可以使一個(gè)簇內(nèi)的所有節(jié)點(diǎn)坐標(biāo)轉(zhuǎn)換成另一個(gè)簇的局部坐標(biāo)。2.3.3一種基于粒子群算法的三維無線傳感器網(wǎng)定位方法粒子群優(yōu)化算法(PSO，particleswarmoptimiza-tion)具有收斂速度快、實(shí)現(xiàn)簡單的特點(diǎn)，是一種高效實(shí)用的搜索算法。PSO算法首先初始化N個(gè)隨機(jī)粒子(三維空間的隨機(jī)坐標(biāo))，每個(gè)粒子都被看作是沒有體積沒有質(zhì)量的微粒，但是有自己的位置且以一定的速度飛行，算法根據(jù)粒子本身和同伴的飛行經(jīng)驗(yàn)來動態(tài)地調(diào)整參數(shù)，通過迭代得到最優(yōu)解[2]。假設(shè)D維搜索空間中的第i個(gè)粒子的位置和速度分別為Xi=(xi1xi2，xiD)和Vi=(vi1vi2…viD)，在每一次迭代中，粒子通過追蹤個(gè)體最優(yōu)值pbest和全局最優(yōu)值gbest來更新自己。在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下公式來更新自己的速度和新的位置。Vij(t+1)=wvij(t)+c1rand1[pij-xij(t)]+c2rand2[pij-xij(t)](1)Xij(t+1)=xij(t)+vi+j(t+1)，j=1，2，，，D(2)式中，w為慣性權(quán)重；c1和c2為學(xué)習(xí)因子；rand1和rand2表示為0~1之間的隨機(jī)數(shù)。粒子群算法的性能很大程度上取決于算法的慣性權(quán)重、學(xué)習(xí)因子和粒子個(gè)數(shù)等參數(shù)，特別是在優(yōu)化復(fù)雜函數(shù)時(shí)，PSO算法很容易陷入局部最優(yōu)，并出現(xiàn)早熟收斂現(xiàn)象。為此，對粒子群算法進(jìn)行了以下改進(jìn)。在粒子群算法中，選取較大的慣性權(quán)重w有利于提高算法的全局搜索能力，但會降低算法的局部搜索能力；相反，選取較小的w會增強(qiáng)算法的局部搜索能力，降低算法的全局搜索能力。為此，采用自適應(yīng)權(quán)重的方法來平衡收斂的全局性和收斂速度。(3)式中，wmax、wmin分別表示權(quán)值的最大值和最小值；f表示粒子當(dāng)前的目標(biāo)函數(shù)值；fa和fmin分別表示當(dāng)前所有粒子的平均目標(biāo)函數(shù)值和最小目標(biāo)函數(shù)值。為了提高算法的搜索速度和收斂性能，引入優(yōu)勝劣汰思想，將所有粒子的目標(biāo)函數(shù)值按優(yōu)劣性排序fsort(1：N)，選擇函數(shù)s[fsort(1：N)]為(4)式中，xsort和vsort為排序后的粒子位置和速度集合。s作為選擇函數(shù)，每次迭代結(jié)束后，按照粒子的目標(biāo)函數(shù)值性能，淘汰掉一半性能較差的粒子，保持性能優(yōu)良的粒子進(jìn)入下一輪迭代。結(jié)論：在國內(nèi)，無線傳感器網(wǎng)絡(luò)正在引起越來越多研究者的興趣，國家自然科學(xué)基金也開始資助這方面的研究，特別是進(jìn)入本世紀(jì)以來，對無線傳感器網(wǎng)絡(luò)自身定位問題有了許多新穎的解決方案和思想，許多技術(shù)方案都能夠解決無線傳感器網(wǎng)絡(luò)的自身定位問題，每一種系統(tǒng)和算法都是用來解決不同的問題或支持不同的應(yīng)用[8]。隨著傳感器網(wǎng)絡(luò)應(yīng)用的不斷發(fā)展，定位算法向三維擴(kuò)展是必然的趨勢，現(xiàn)在大部分的二維定位算法可以擴(kuò)展到三維情況下，但是三維空間比二維平面的情況要復(fù)雜的多，對現(xiàn)有的算法進(jìn)行三維擴(kuò)展，不斷豐富三維定位算法是一項(xiàng)艱巨的任務(wù)，同時(shí)如何針對三維空間的特點(diǎn)，設(shè)計(jì)出新的精度更高的三維定位算法也是需要進(jìn)一步研究的課題。希望本文的研究能起到拋磚引玉的作用，在不遠(yuǎn)的將來，能有更多的研究者