【正文】 的節(jié)點會增多，這樣不僅會降低算法的定位效率，還會消耗更多珍貴的能量。第二種情況 初選簇頭節(jié)點個數(shù)等于所需的簇頭節(jié)點數(shù)量，則無需再計算其綜合性能值，初選簇頭節(jié)點都是最終的簇頭節(jié)點。 (34)式中 、——權(quán)值，具體怎么取根據(jù)實際情況設(shè)定，只要滿足即可。由于簇頭節(jié)點既要將簇內(nèi)節(jié)點的相關(guān)信息存儲起來，又要管理其簇內(nèi)節(jié)點，因此，其通信量及計算量都會遠大于其簇內(nèi)節(jié)點，故簇頭節(jié)點應(yīng)比簇內(nèi)節(jié)點具有更高的能量。分簇算法分為以下兩大步：第一步 選擇簇頭節(jié)點假定簇內(nèi)各節(jié)點與簇頭節(jié)點間的通信是選擇最短的路徑進行的，然而距離簇頭節(jié)點近的節(jié)點除了要將自身的相關(guān)信息傳播給簇頭節(jié)點，點信息轉(zhuǎn)發(fā)給簇頭節(jié)點。 分簇算法分簇算法可將一個大型的WSN劃分成多個區(qū)域并選出各個區(qū)域中負責(zé)數(shù)據(jù)的路由轉(zhuǎn)發(fā)同時管理其簇內(nèi)節(jié)點的簇頭節(jié)點，這樣既能夠保證原有覆蓋范圍內(nèi)的書籍通信，又在很大程度上節(jié)省了節(jié)點的能量。在采用基于HopEuclidean的MDSMAP(D)算法定位之前，需做以下假設(shè)：(1) 為了計算方便，設(shè)定部署傳感器節(jié)點的區(qū)域是二維的，且部署后位置靜止；(2) 傳感器節(jié)點的ID是唯一的；(3) 節(jié)點具有測距能力；(4) 采用的是自由空間電波傳播模型，節(jié)點之間的通信能力是對稱的，而且所有的消息都可以被正確接收。MDSMAP算法是采用MDS技術(shù)根據(jù)距離矩陣進行求解對應(yīng)節(jié)點的位置坐標，但通常距離矩陣都比較龐大，則會導(dǎo)致其計算復(fù)雜度較大，且當節(jié)點增加或移動時，需要重新求解，這將會嚴重阻礙網(wǎng)絡(luò)的擴展。在實際的WSN應(yīng)用中，求解全網(wǎng)絡(luò)節(jié)點間的距離只能依據(jù)相鄰節(jié)點之間的距離信息進行估計。 基于HopEuclidean的MDSMAP(D)定位算法 改進算法的相關(guān)研究工作如果所有節(jié)點之間的歐幾里德距離沒有誤差，則采用經(jīng)典的MDS定位算法求出的節(jié)點位置坐標是精確的。(2) 估算相對位置對上一步生成的節(jié)點之間的距離矩陣采用MDS技術(shù)，估算出整個網(wǎng)絡(luò)中所有未知節(jié)點在多維空間上的相對位置的坐標。MDSMAP算法分為三步：(1) 生成距離矩陣首先從全局角度生成網(wǎng)絡(luò)拓撲連通圖，如果節(jié)點具備測距能力，則通過測距技術(shù)獲得的節(jié)點間的距離值。傳統(tǒng)的MDSMAP算法，由美國密蘇里哥倫比亞大學(xué)Yi等人提出。 (33)(4) 將進行奇異值分解，求最大的個正特征值和對應(yīng)的個特征向量，個向量組成維對角矩陣，個特征向量組成維矩陣,所有節(jié)點的相對坐標為 (34) MDSMAP定位算法無線傳感器網(wǎng)絡(luò)中節(jié)點定位的實質(zhì)是未知節(jié)點通過與少量位置已知的信標節(jié)點之間的連通性信息來確定自身在相應(yīng)空間中的位置坐標,而MDS技術(shù)就是根據(jù)各個對象(或?qū)嶓w)間的相異(似)信息構(gòu)建多維空間上點的相對坐標圖。定義脅強系數(shù)為： (31)其具體實現(xiàn)分為四步：(1) 構(gòu)造相異性矩陣；(2) 將矩陣中的各元素乘方，得到；(3) 將雙重中心化,即的兩邊同時乘以中心矩陣,的計算公式見(32)。構(gòu)造多維空間上點的坐標矩陣用表示，其中為坐標點的個數(shù)，為坐標點的維數(shù)，實體對象和的坐標分別為，多維空間上和之間的歐式距離用表示。本章算法的基礎(chǔ)是多維標度定位算法，下面具體介紹一下多維標度定位算法。為了實現(xiàn)大規(guī)模無線傳感器網(wǎng)絡(luò)中節(jié)點的定位，本文采用分簇算法將大規(guī)模網(wǎng)絡(luò)劃分為多個區(qū)域同時在各個區(qū)域中選出各自的簇頭節(jié)點，然后采用HopEuclidean算法計算出每個區(qū)域內(nèi)節(jié)點之間的距離，再讓各個簇頭節(jié)點采用多維標度技術(shù)通過簇內(nèi)節(jié)點之間的距離矩陣計算出各個區(qū)域內(nèi)傳感器節(jié)點的局部相對坐標，最后通過融合算法將其融合為全局相對坐標并根據(jù)信標節(jié)點信息通過線性轉(zhuǎn)換將器相對坐標轉(zhuǎn)變?yōu)榻^對坐標。通過研究分析發(fā)現(xiàn)，MDSMAP算法是使用節(jié)點間的最短路徑距離替換其實際幾何距離，但通常最短路徑距離比實際幾何距離小，這樣就會擴大節(jié)點間的幾何距離，最終會導(dǎo)致較大定位誤差。比如，DVHop算法是適合于硬件配置較低、對節(jié)點定位精度要求不太高的應(yīng)用；而Euclidean定位算法是適合于節(jié)點具有測距能力的、且環(huán)境中的噪聲相對較小的應(yīng)用場合下使用；MDSMAP算法是適合于網(wǎng)絡(luò)連通度相對比較大、且傳感器節(jié)點的能量充足、計算能力較強的小規(guī)模拓撲規(guī)則的無線傳感器網(wǎng)絡(luò)。首先，主要從無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)和傳感器節(jié)點結(jié)構(gòu)兩方面闡述了無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)；第二，介紹了無線傳感器網(wǎng)絡(luò)的特點；第三，闡述了無線傳感器網(wǎng)絡(luò)定位技術(shù)的基礎(chǔ)知識，其中包括節(jié)點定位的基本概念、術(shù)語及定位算法的分類；最后，重點介紹了現(xiàn)有的幾種與本文研究相關(guān)的經(jīng)典定位算法：DVHop算法、Euclidean定位算法、MDSMAP算法，同時對這三種算法的優(yōu)缺點作了分析。此外，當傳感器網(wǎng)絡(luò)中的節(jié)點密度減小或網(wǎng)絡(luò)拓撲結(jié)構(gòu)不規(guī)則時，其節(jié)點的定位誤差會增大，甚至?xí)写罅康膫鞲衅鞴?jié)點無法實現(xiàn)定位。否則使用最短路徑算法，生成多維標度技術(shù)MDS所需節(jié)點間距矩陣；第二，對節(jié)點間距矩陣利用多維標度技術(shù)計算出各個節(jié)點在整個網(wǎng)絡(luò)中位置的相對坐標；第三，如果擁有足夠數(shù)量的信標節(jié)點，則可將相對坐標系統(tǒng)經(jīng)過線性變換轉(zhuǎn)換成相應(yīng)的絕對坐標系統(tǒng)。該算法可分為3個步驟。 MDSMAP算法MDSMAP算法[42]是一種不論傳感器節(jié)點是否具有測距能力都可以實現(xiàn)定位的集中式定位算法，而且依據(jù)實際情況既可以實現(xiàn)相對定位，也能夠?qū)崿F(xiàn)絕對定位。該算法針對Euclidean定位算法只有未知節(jié)點擁有三個以上鄰居節(jié)點且這些鄰居節(jié)點都必須彼此相鄰才能統(tǒng)計出到信標節(jié)點的跳數(shù)的問題，通過融入距離矢量路由的思想，并且有選擇性地把已定位節(jié)點逐漸升級為信標節(jié)點，以此來提高算法的定位精度的同時也擴展了算法的可用性。Euclidean定位算法的優(yōu)點是與信標節(jié)點相隔兩跳的未知節(jié)點均可實現(xiàn)定位，但其條件比較苛刻，從而該算法的可用性會受到一定的約束，此外該算法受環(huán)境影響大，這樣會導(dǎo)致其定位誤差增加。在四邊形中，己知所有邊的長度與對角線的長度，則由三角形中的余弦定理即可通過式(21)、式(22)、式(23)計算出的長度(未知節(jié)點與信標節(jié)點間的距離)。通過RSSI技術(shù)直接測得節(jié)點間距，和。該算法核心思想如圖24所示。圖23 DVHop定位算法舉例DVHop算法對節(jié)點硬件要求低，實現(xiàn)簡單，其不足是以節(jié)點間最小跳段距離替代節(jié)點間的直線距離，由于通常節(jié)點間的最小跳段距離與其間的直線距離是有差別的，因而最終會有一定的定位誤差。:。如圖23所示，已知信標節(jié)點與、之間的距離和跳數(shù)，計算得到校正值(即平均每跳距離)。基于本文的研究重點與三種無需測距定位算法：DVHop算法、Euclidean定位算法和MDSMAP算法有關(guān)，接下來具體介紹這三種經(jīng)典的定位算法。 無需測距的定位算法無需測距的定位算法僅需依據(jù)網(wǎng)絡(luò)連通性等信息就可得到未知節(jié)點在網(wǎng)絡(luò)中的位置坐標，這樣就會使得節(jié)點硬件的要求降低，從而使其更加適用于大規(guī)模WSN。(2) 定位階段 未知節(jié)點通過上面的測距階段計算出與其3個(或3個以上)鄰居信標節(jié)點間的距離(或角度)后，采用三邊(或三角)測量法、極大似然估計法等方法計算出自身的位置坐標。目前WSN定位中，可以使用多種測距技術(shù)，如測量無線電、紅外線、激光信號強度，測量無線電信號或超聲波等到達的時間，測量無線電信號或超聲波等到達的時間差等。定位覆蓋率(coverage rate)：無線傳感器網(wǎng)絡(luò)中，能確定坐標位置的未知節(jié)點占總節(jié)點數(shù)的比例。定位誤差(position error)：通過定位算法計算出的坐標和其實際坐標的差值與節(jié)點的通信半徑的比值。網(wǎng)絡(luò)密度(network density)：一個傳感器節(jié)點通信時所覆蓋區(qū)域內(nèi)的節(jié)點平均數(shù)目，常記為。跳數(shù)(hop count)：兩個節(jié)點之間建立通信需要經(jīng)過的跳段總數(shù)，稱為兩點之間的跳數(shù)。信標節(jié)點是未知節(jié)點定位的參考點，未知節(jié)點是根據(jù)信標節(jié)點的位置信息利用節(jié)點間的連通約束等通過一定技術(shù)來確定自身位置。在WSN節(jié)點的定位技術(shù)中，根據(jù)節(jié)點是否已知自身的位置，將傳感器節(jié)點分為兩類：一類是位置已知的信標節(jié)點(beacon node)，另一類是需要獲取其位置信息的未知節(jié)點(unknown node)。此外，傳感器節(jié)點的能力決定著傳感器網(wǎng)絡(luò)的壽命，而傳感器節(jié)點通常部署在人們很難抵達的區(qū)域，為其更換電池是很不現(xiàn)實的，故而節(jié)點的能量是非常受限的。(6) 節(jié)點資源有限 傳感器節(jié)點資源包括兩方面：其一是計算能力，其二是節(jié)點的能量。(5) 網(wǎng)絡(luò)可靠性 通常部署傳感器節(jié)點的環(huán)境都比較惡劣甚至人類無法抵達，因此，傳感器節(jié)點必須結(jié)實耐用，同時能夠適應(yīng)各種各樣的惡劣環(huán)境。(4) 尋址以數(shù)據(jù)為中心 WSN只關(guān)心數(shù)據(jù)本身，比如事件發(fā)生的時間、地點即位置，并不關(guān)心數(shù)據(jù)是哪個節(jié)點監(jiān)測或采集到的。(3) 應(yīng)用相關(guān) WSN的設(shè)計有多種多樣，只能根據(jù)其具體的應(yīng)用場合進行設(shè)計比如有的需要獲取非常準確的信息并不關(guān)心它所花費的時間，有的則需要對二者折中考慮，這樣一來在設(shè)計WSN時的側(cè)重點就不一樣，那么其網(wǎng)絡(luò)協(xié)議和軟、硬件平臺一定會有所不同。系統(tǒng)的工作質(zhì)量并不是通過提升單個設(shè)備的能力提高，而是靠大量冗余節(jié)點的協(xié)同工作來提高的。除了這些，WSN還具有以下一些與無線自組網(wǎng)絡(luò)不同的特點。而傳輸數(shù)據(jù)才是無線自組網(wǎng)絡(luò)的主要目的，它并不太關(guān)注數(shù)據(jù)的處理。圖22 傳感器節(jié)點體系結(jié)構(gòu) 無線傳感器網(wǎng)絡(luò)的特點WSN有很多地方與無線自組網(wǎng)絡(luò)的很相似，同時也存在著很多技術(shù)方面的區(qū)別[37]。(2)傳感器節(jié)點結(jié)構(gòu) 通常傳感器節(jié)點是一個由采集模塊(傳感器，AC/DC轉(zhuǎn)換器)、無線通信模塊(主要有收發(fā)器)、能量供應(yīng)模塊(電池、DC/DC能量轉(zhuǎn)換器)、控制模塊(微處理器、存儲器)以及其它輔助可選功能模塊等部分組成的微型的嵌入式系統(tǒng)[35]，如圖22所示。其中的各個傳感器節(jié)點都具有收集信息及監(jiān)測數(shù)據(jù)的功能，而且可以將檢測或收集到的數(shù)據(jù)傳播給其他傳感器節(jié)點，這樣在傳播的過程中就會出現(xiàn)“冗余”現(xiàn)象即有可能多個節(jié)點同時處理一個數(shù)據(jù)，因此都應(yīng)先將這些被處理過的數(shù)據(jù)傳輸給匯聚節(jié)點，由匯聚節(jié)點進行相應(yīng)的處理。其中，傳感器節(jié)點相對于匯聚節(jié)點，其通信能力、存儲能力和處理能力通常較弱，而且其能量十分有限(通常利用電池供電)。WSN作為一個全新且熱門的研究方向，給科技研究者們提出了許多在工程技術(shù)等層面的挑戰(zhàn)性課題。WSN的發(fā)展將有助于物聯(lián)網(wǎng)等前沿學(xué)科全面提升社會生產(chǎn)生活中信息互通性、信息感知能力和智能決策能力等，進而增強整個系統(tǒng)的性能。因而，傳感器技術(shù)作為信息獲取最基本且最重要的技術(shù)[32]，也在不斷發(fā)展。最后對本文的研究工作做了總結(jié)和展望。概述了加權(quán)分布式多維標度定位算法的特點與定位過程，同時主要針對其加權(quán)機制和自適應(yīng)2步鄰居選擇機制的不足做了較全面的分析，接下來對改進的鄰居選擇機制與加權(quán)機制做了詳細的闡述，并給出了采用最速下降法對其目標代價函數(shù)進行優(yōu)化求解的具體過程。第3章詳細闡述了多維標度技術(shù)在無線傳感器網(wǎng)絡(luò)定位算法中的應(yīng)用及MDSMAP定位算法，著重對MDSMAP定位算法的不足之處做了較全面的分析，主要針對其有較大的距離誤差及不適用于大規(guī)模密集型網(wǎng)絡(luò)兩方面的不足，提出了一種基于HopEuclidean的MDSMAP(D)定位算法，并對其進行了詳細的闡述。 論文結(jié)構(gòu)安排本文是圍繞著無線傳感器網(wǎng)絡(luò)的定位算法進行的，論文的結(jié)構(gòu)安排如下。經(jīng)過分析和仿真結(jié)果表明，改進的MDSMAP定位算法在定位精度提高的情況下，對不規(guī)則網(wǎng)絡(luò)和大規(guī)模密集型網(wǎng)絡(luò)有更好的適應(yīng)性；改進的分布式加權(quán)多維標度定位算法有效抑制了較大定位誤差在網(wǎng)絡(luò)中擴散，而且對不規(guī)則網(wǎng)絡(luò)和大規(guī)模稀疏型網(wǎng)絡(luò)都有很好的適應(yīng)性。本文提出的改進算法中采用的加權(quán)機制與鄰居選擇機制都綜合考慮了節(jié)點間距離的遠近與參與定位的鄰居節(jié)點的定位誤差等因素，同時為了加快算法的收斂速度，引入了無約束最優(yōu)化中簡單且收斂速度較快的最速下降法對其目標代價函數(shù)進行優(yōu)化。其次，重點分析研究了分布式加權(quán)多維標度定位算法，經(jīng)過研究發(fā)現(xiàn)，該算法由于采用的是高斯加權(quán)機制和自適應(yīng)2步鄰居選擇機制，造成離未知節(jié)點近的節(jié)點定位誤差不斷擴大；此外，如果網(wǎng)絡(luò)稀疏時，會有部分節(jié)點的1跳鄰居節(jié)點很少，這樣就會使得這些節(jié)點無法實現(xiàn)定位。本文主要是針對MDSMAP算法這兩方面的不足提出了一種基于HopEuclidean的MDSMAP(D)定位算法。首先，重點分析研究了MDSMAP定位算法，經(jīng)過分析發(fā)現(xiàn)，經(jīng)典的MDSMAP定位算法在節(jié)點間的測量距離沒有誤差的情況下，通過MDS技術(shù)可以計算出準確的節(jié)點位置坐標。因此，WSN的節(jié)點定位技術(shù)有很大的研究價值，是WSN中重要的研究方向之一。 研究內(nèi)容及主要工作在WSN的應(yīng)用中，絕大多數(shù)情況下需要有節(jié)點位置信息，否則采集到的數(shù)據(jù)將沒有任何意義，尤其是關(guān)于環(huán)境監(jiān)測、橋梁結(jié)構(gòu)變化監(jiān)測、管道泄漏監(jiān)測等，發(fā)生地點的地理位置信息非常重要。然而雖然經(jīng)過這些年學(xué)術(shù)界、軍界及商業(yè)界的不斷努力，目前無線傳感器網(wǎng)絡(luò)節(jié)點的自身定位問題在一定程度上能夠解決，但仍有許多問題沒有得到有效合理的解決，比如，通過測距技術(shù)獲得的節(jié)點間距離仍有一定的誤差、在定位過程中所需的通信開銷仍比較大等問題。但是幾種算法所改進的只是在計算規(guī)模方面對算法進行了改進，并沒有解決MDSMAP所存在的全部問題。于是，針對MDSMAP算法的不足，引入了“補丁”這一概念，提出了MDSMAP(P)定位算法；文獻[30]是一種基于非度量多維標度技術(shù)的定位算法，通過多次迭代來不斷修正距離和相異性間的單調(diào)關(guān)系的過程。本文主要研究基于多維標度分布式的定位算法。近年來，隨著科學(xué)技術(shù)的發(fā)展與WSN實用價值的不斷提升，國內(nèi)的一些高校和研究所也開始對有關(guān)WSN的理論和應(yīng)用的研究工作[26,27]，2007年，在有關(guān)集成技術(shù)的國際會議上提出了一種自適應(yīng)鄰居選擇的分布式定位算法[28]。2004年，麻省理工學(xué)院的RVSN和NMS兩個研究小組在“分布式傳感器網(wǎng)絡(luò)的定位與追蹤”項目中提出了一種分布式定位算