【正文】 士學(xué)位期間獨(dú)立進(jìn)行研究工作所取得的成果。據(jù)本人所知，論文中除已注明部分外不包含他人已發(fā)表或撰寫過的研究成果。本聲明的法律結(jié)果將完全由本人承擔(dān)。本論文的研究成果歸燕山大學(xué)所有，本人如需發(fā)表將署名燕山大學(xué)為第一完成單位及相關(guān)人員。本人授權(quán)燕山大學(xué)，可以采用影印、縮印或其他復(fù)制手段保存論文，可以公布論文的全部或部分內(nèi)容。本學(xué)位論文屬于 不保密□。而取得節(jié)點(diǎn)位置信息較簡便、快捷、精確的方法是通過手動設(shè)定或攜帶GPS定位設(shè)備等手段，但通過這種方式獲取的成本很高。本文將主要研究基于多維標(biāo)度的無線傳感器網(wǎng)絡(luò)定位算法。其次，介紹了多維標(biāo)度技術(shù)及其在無線傳感器網(wǎng)絡(luò)定位算法中的應(yīng)用。該算法先采用分簇的算法，將大規(guī)模網(wǎng)絡(luò)分成多個具有簇首的局部網(wǎng)絡(luò)，在局部網(wǎng)絡(luò)中通過HopEuclidean算法計(jì)算鄰居節(jié)點(diǎn)間的歐氏距離來代替MDSMAP算法中的所使用的最短路徑距離，這樣不僅提高了定位精度，而且有利于網(wǎng)絡(luò)的擴(kuò)展。本文采用的加權(quán)機(jī)制與鄰居選擇機(jī)制綜合考慮1跳鄰居數(shù)目、節(jié)點(diǎn)自身定位精度與測距誤差，并且引入最速下降法優(yōu)化其目標(biāo)代價函數(shù)。仿真結(jié)果表明，提出的算法在定位精度提高的情況下對不規(guī)則、大規(guī)模網(wǎng)絡(luò)有很好的適應(yīng)性。 Multidimensional scaling。 Distribution weighted。因而，作為獲取信息、傳遞信息的最基礎(chǔ)的網(wǎng)絡(luò)——無線傳感器網(wǎng)絡(luò)的研究和應(yīng)用發(fā)展非常迅猛。無線傳感器網(wǎng)絡(luò)WSN(wireless sensor network)[1,2]是指由大量成本低廉的，具有感知能力、無線通信能力、計(jì)算能力的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)。這種網(wǎng)絡(luò)系統(tǒng)在國家安全、國防軍事、醫(yī)療衛(wèi)生、環(huán)境監(jiān)測、制造業(yè)、交通管理、災(zāi)難拯救、空間探索等領(lǐng)域[3,4]有著其他技術(shù)無可比擬的優(yōu)勢，能夠在任何時間、地點(diǎn)、環(huán)境條件下獲取可靠而有用的信息。全球未來的三大高科技產(chǎn)業(yè)中最受重視的也是WSN[5]。其中傳感器節(jié)點(diǎn)的位置信息是采集信息中不可缺少的，確定獲取信息的節(jié)點(diǎn)所在的位置是提供監(jiān)測事件位置信息的前提，在WSN的應(yīng)用中起著至關(guān)重要的作用[6,7]。比如在軍事應(yīng)用中，對敵方軍事目標(biāo)的定位可以決定是否需集中火力進(jìn)行打擊；在森林中發(fā)生火災(zāi)時，監(jiān)測發(fā)生火災(zāi)的具體區(qū)域與火勢情況可以決定是否需要增加軍力救助等等。例如計(jì)算網(wǎng)絡(luò)覆蓋范圍、控制網(wǎng)絡(luò)的負(fù)載均衡、對外部目標(biāo)的定位和追蹤、基于地理信息的路由、資源的有效配置等。毫無疑問，獲得節(jié)點(diǎn)位置信息的直接方法是利用全球定位系統(tǒng)GPS(Global Positioning System)。但是，傳感器節(jié)點(diǎn)成本低、電池供電、計(jì)算能力和通信能力有限，使得GPS不適用于低成本自組織的無線傳感器網(wǎng)絡(luò)，因?yàn)樗鼪]有考慮布網(wǎng)成本和能量消耗問題。所以，實(shí)現(xiàn)WSN節(jié)點(diǎn)定位不能全依賴GPS系統(tǒng)來完成，只能是通過該系統(tǒng)獲取少數(shù)節(jié)點(diǎn)的位置信息再通過其他的定位技術(shù)來實(shí)現(xiàn)其他大量節(jié)點(diǎn)的定位。 國內(nèi)外研究現(xiàn)狀由于WSN的應(yīng)用前景非常廣闊，它作為21世紀(jì)影響力巨大的全新技術(shù)之一，許多國家學(xué)術(shù)界、軍界和工業(yè)界研究者們在其有關(guān)的研究中都注入了大量的人力與物力。WSN的研究是20世紀(jì)90年代開始的，該網(wǎng)絡(luò)最早是由軍事領(lǐng)域的有關(guān)人事提出的。后來隨著相關(guān)學(xué)科的不斷發(fā)展，WSN逐漸轉(zhuǎn)向民用，在許多領(lǐng)域得到了大量研究者們的廣泛而深入的研究。WSN中的定位技術(shù)是大多數(shù)有關(guān)WSN應(yīng)用的支撐技術(shù)和關(guān)鍵技術(shù)之一。這種自組織網(wǎng)絡(luò)定位包括兩種定位，一種是節(jié)點(diǎn)自身定位，另一種是目標(biāo)定位，前者是后者的基礎(chǔ)。從2000年開始，許多有關(guān)WSN節(jié)點(diǎn)定位研究成果的報告開始在國際上陸續(xù)出現(xiàn)。此系統(tǒng)主要是用于獲取移動或靜止的傳感器節(jié)點(diǎn)所在房間的具體位置信息。2003年，Tian He等人提出了一種采用求解約束集合進(jìn)行定位的APIT算法[18]；哥倫比亞大學(xué)的Shang ，提出了MDSMAP，MDSMAP(P)，MDSMAP(C)等幾種集中式定位算法[1922]。2003年，Niculescu教授等人提出了一系列分布式定位算法，包括DVHop，DVDistance，DVCoordinate等算法[23]。2006年，Costa J A, Patwari N等人提出了dwMDS(G)算法[25]，該算法最終是通過優(yōu)化加權(quán)的目標(biāo)代價函數(shù)計(jì)算出節(jié)點(diǎn)的坐標(biāo)。2008年，北京交通大學(xué)的馬震等提出了一種分布式的算法MDSMAP(D)[29]。目前已有不少研究者對這種定位算法作了多方面的改進(jìn)，在分布式的多維標(biāo)度定位算法的改進(jìn)研究中，比如MDSMAP(P)定位算法，是Yi Shang等人通過對經(jīng)典MDSMAP定位算法分析，發(fā)現(xiàn)當(dāng)傳感器節(jié)點(diǎn)不是均勻分布或者WSN的拓?fù)浣Y(jié)構(gòu)不是規(guī)則形狀時(如C形狀)，若節(jié)點(diǎn)之間相隔太遠(yuǎn)，最短路徑長度跟歐氏距離是有很大差異的，且無法用線性關(guān)系來描述它們之間的關(guān)系。文獻(xiàn)[31]是利用Euclidean算法改進(jìn)經(jīng)典MDSMAP算法中估算最短距離的方法，但因?yàn)镋uclidean算法由于直接測量兩節(jié)點(diǎn)之間的距離時，受環(huán)境因素影響較大，所以使得該算法的定位精度降低了?？偠灾?，提高對WSN研究的推廣不僅會對人們未來的生活產(chǎn)生巨大的影響，而且也給研究者們帶來巨大的挑戰(zhàn)。因此，我們?nèi)孕柽M(jìn)一步去探索和研究WSN節(jié)點(diǎn)的定位問題。位置信息不僅可以用于監(jiān)測事件發(fā)生的地點(diǎn)，還可用于跟蹤目標(biāo)、預(yù)測目標(biāo)軌跡、協(xié)助路由及網(wǎng)絡(luò)拓?fù)涔芾淼取１疚闹饕芯康膬?nèi)容是基于多維標(biāo)度技術(shù)的WSN定位算法。但是，由于該算法采用的是節(jié)點(diǎn)間的最短路徑代替節(jié)點(diǎn)間的歐式距離，而很明顯這兩者有很大的差別，尤其是當(dāng)節(jié)點(diǎn)間的連通度較小時，其表現(xiàn)更為明顯；此外，該算法不適用于大規(guī)模密集型網(wǎng)絡(luò)，因?yàn)樵谶@樣的網(wǎng)絡(luò)部署下，節(jié)點(diǎn)間距矩陣會相當(dāng)龐大，而且每當(dāng)有節(jié)點(diǎn)增加或減少的時候，該算法都得重新開始計(jì)算，這樣就會增加其計(jì)算復(fù)雜度，給本來能量就很有限的傳感器節(jié)點(diǎn)增加了很大的負(fù)擔(dān)，最終導(dǎo)致傳感器節(jié)點(diǎn)還沒完成定位就已經(jīng)能量耗盡，無法完成任務(wù)。提出的算法中加入了分簇的思想，先將大規(guī)模WSN采用本文提出的分簇算法劃分為多個局部網(wǎng)絡(luò)，然后各個局部網(wǎng)絡(luò)中采用HopEuclidean算法獲取節(jié)點(diǎn)間的距離，通過MDS方法計(jì)算出節(jié)點(diǎn)的局部坐標(biāo)，最好通過線性轉(zhuǎn)換將局部坐標(biāo)轉(zhuǎn)換為全局坐標(biāo)。本文主要針對分布式加權(quán)多維標(biāo)度定位算法這兩方面的不足，提出了一種改進(jìn)方案。最后，在MATLAB仿真平臺上對改進(jìn)的兩種定位算法進(jìn)行了仿真，并與其原算法做了比較。期望本文的研究工作能夠給無線傳感器網(wǎng)絡(luò)的未來研究帶來一定的幫助。第2章簡述了無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)和特點(diǎn)，介紹了節(jié)點(diǎn)定位中用到的一些基本概念及術(shù)語，并對計(jì)算節(jié)點(diǎn)位置的基礎(chǔ)方法及與本文相關(guān)的經(jīng)典定位算法作了詳細(xì)的闡述和分析。第4章 主要針對加權(quán)分布式多維標(biāo)度定位算法的不足提出了一種改進(jìn)方案。第5章用仿真實(shí)驗(yàn)驗(yàn)證了兩種改進(jìn)算法的有效性和可行性。第2章 無線傳感器網(wǎng)絡(luò)及其定位技術(shù)第2章 無線傳感器網(wǎng)絡(luò)及其定位技術(shù) 無線傳感器網(wǎng)絡(luò)概述隨著科學(xué)技術(shù)的不斷發(fā)展，如今的我們正處于信息時代。傳感器獲取信息的技術(shù)已經(jīng)從過去的單一化模型逐漸趨向集成化、網(wǎng)絡(luò)化及微型化發(fā)展。WSN是環(huán)境感知與監(jiān)控領(lǐng)域的一場革命。 無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)(1)WSN結(jié)構(gòu) WSN的結(jié)構(gòu)[33]如圖21所示，WSN系統(tǒng)通常由傳感器節(jié)點(diǎn)(sensor node)、任務(wù)管理節(jié)點(diǎn)(task manager node)和匯聚節(jié)點(diǎn)(sink node)三部分組成。圖21 無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)在監(jiān)測區(qū)域(sensor field)的內(nèi)部或其附近隨機(jī)部署大量傳感器節(jié)點(diǎn)，這些節(jié)點(diǎn)以自組織方式組建成一個無線網(wǎng)絡(luò)。最后，由匯聚節(jié)點(diǎn)直接通過通信衛(wèi)星或Internet傳達(dá)給管理節(jié)點(diǎn)(即觀察者)[34]。其中，采集監(jiān)測區(qū)域內(nèi)信息和轉(zhuǎn)換其數(shù)據(jù)是由采集模塊完成；與其他節(jié)點(diǎn)進(jìn)行無線通信并接收與轉(zhuǎn)發(fā)所采集的數(shù)據(jù)及控制信息是由無線通信模塊完成；提供傳感器節(jié)點(diǎn)運(yùn)行所需的能量能量供應(yīng)模塊，通常采用微型電池；存儲和處理本身采集的數(shù)據(jù)及其他節(jié)點(diǎn)發(fā)來的數(shù)據(jù)由控制模塊完成[36]。WSN是以數(shù)據(jù)為中心的，為了減少網(wǎng)絡(luò)的流量、降低功耗同時提高系統(tǒng)利用率，其數(shù)據(jù)是盡可能早的由系統(tǒng)按照實(shí)際需要進(jìn)行處理的。因此，為AdHoc網(wǎng)絡(luò)設(shè)計(jì)的一部分協(xié)議和算法是不能夠滿足WSN應(yīng)用的需求。(1) 網(wǎng)絡(luò)規(guī)模大且部署密集 由于WSN主要是用來采集數(shù)據(jù)，而且采集的數(shù)據(jù)越準(zhǔn)確完整越好，因此，一般需要將大量傳感器節(jié)點(diǎn)密集部署在所要監(jiān)測的區(qū)域中。(2) 網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)渥兓l繁 WSN是動態(tài)網(wǎng)絡(luò)，由于在WSN中傳感器節(jié)點(diǎn)的移動性和能量耗盡會使得節(jié)點(diǎn)失效或出現(xiàn)故障，因此WSN中隨時有可能加入新的傳感器節(jié)點(diǎn)進(jìn)行替補(bǔ)，由此看來WSN的拓?fù)浣Y(jié)構(gòu)的改變是不可避免的。因此，針對具體應(yīng)用來研究傳感器網(wǎng)絡(luò)技術(shù)，是WSN設(shè)計(jì)不同于傳統(tǒng)網(wǎng)絡(luò)的顯著特征。除了特殊需要，由于通常部署傳感器節(jié)點(diǎn)的環(huán)境都比較惡劣，人類無法抵達(dá)只能通過飛機(jī)等方式進(jìn)行撒播，而且用戶也不需要知道每個節(jié)點(diǎn)的具體身份號，因此可采用以數(shù)據(jù)為中心的組網(wǎng)方式。除此之外，為了使監(jiān)測到的數(shù)據(jù)不被竊取而且能夠獲取較準(zhǔn)確的而不是被篡改后的數(shù)據(jù)信息，WSN通信的保密性和安全性也是至關(guān)重要的，故而要想設(shè)計(jì)一個好的無線傳感器網(wǎng)絡(luò)的必須考慮其魯棒性和容錯性。傳感器節(jié)點(diǎn)由于受體積、價格及功耗的制約，其計(jì)算能力和內(nèi)存空間是非常有限，與普通計(jì)算機(jī)相比會差的多，由于受這些因素的約束，因而為其設(shè)計(jì)的程序等都不能太復(fù)雜。 定位技術(shù)的相關(guān)概念及術(shù)語(1) WSN定位的基本概念在WSN中，節(jié)點(diǎn)定位(node localization)是指根據(jù)若干個位置已知的節(jié)點(diǎn)和節(jié)點(diǎn)間的連通性采用一定的方式獲取WSN中其余節(jié)點(diǎn)的絕對(相對于地理經(jīng)緯度)或相對位置信息。信標(biāo)節(jié)點(diǎn)是指通過手動設(shè)置或攜帶GPS定位設(shè)備等手段獲得自身的精確位置信息的傳感器節(jié)點(diǎn)，其在WSN的節(jié)點(diǎn)中所占的比例是很低的。(2) 基本術(shù)語鄰居節(jié)點(diǎn)(neighbor node)：無線傳感器網(wǎng)絡(luò)中，在傳感器節(jié)點(diǎn)通信半徑內(nèi)，可直接通信的所有其他節(jié)點(diǎn)稱為此傳感器節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。跳段距離(hop distance)：兩個節(jié)點(diǎn)之間進(jìn)行通信所需的各跳段距離之和。測距誤差(range error)：節(jié)點(diǎn)間通過測距技術(shù)等估算所得的距離和其實(shí)際幾何歐式距離的差值與節(jié)點(diǎn)的通信半徑的比值。網(wǎng)絡(luò)連通度(network connection degree)：所以傳感器節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)的平均值。 基于測距技術(shù)的定位基于測距技術(shù)的定位(Range Based)[38]是通過一定的方式或技術(shù)獲得相鄰節(jié)點(diǎn)之間的實(shí)際距離或方位進(jìn)行定位，要求節(jié)點(diǎn)具有測距能力?；跍y距技術(shù)的定位一般分為以下幾個階段：(1) 測距階段 未知節(jié)點(diǎn)先采用上面介紹的測距方法獲得自身與其鄰居節(jié)點(diǎn)之間的距離或者角度信息，然后通過一定的方式利用自身與其鄰居節(jié)點(diǎn)之間的距離或角度，計(jì)算出自身到離其最近的信標(biāo)節(jié)點(diǎn)的距離或者角度，可以直接計(jì)算其直線距離，也可以用兩者間的跳段距離來近似代替其直線距離。(3) 修正階段 采用迭代或遞歸優(yōu)化等數(shù)值分析中的優(yōu)化方法對求得的節(jié)點(diǎn)坐標(biāo)進(jìn)行求精，提高其定位精度。無需測距的定位算法的定位性能幾乎不會受環(huán)境的影響，即使其定位精度會有所下降，也可滿足某些應(yīng)用的需要。 DVHop算法DVHop算法[39]的基本思想是未知節(jié)點(diǎn)先計(jì)算到信標(biāo)節(jié)點(diǎn)的最少跳數(shù)，并估算出平均每一跳的距離，然后用該值乘以最少跳數(shù)就可計(jì)算出與信標(biāo)節(jié)點(diǎn)間的距離，當(dāng)未知節(jié)點(diǎn)獲得與三個或三個以上信標(biāo)節(jié)點(diǎn)的距離時，則執(zhí)行三邊測量定位。假設(shè)節(jié)點(diǎn)從獲得校正值，則與、之間的距離分別為:。:，然后根據(jù)三邊測量法計(jì)算得出節(jié)點(diǎn)的位置坐標(biāo)。 Euclidean定位算法Euclidean算法[40]是一種計(jì)算與信標(biāo)節(jié)點(diǎn)相隔兩跳的未知節(jié)點(diǎn)位置坐標(biāo)的方法。圖24 Euclidean定位算法示意圖假設(shè)，為未知節(jié)點(diǎn)，為信標(biāo)節(jié)點(diǎn)。節(jié)點(diǎn)與，相鄰。 (21) (22) (23)使用這種方法，當(dāng)未知節(jié)點(diǎn)獲得與三個或三個以上信標(biāo)節(jié)點(diǎn)距離后就可計(jì)算出自身的位置坐標(biāo)。 HopEuclidean定位算法HopEuclidean算法[41]是在Euclidean定位算法基礎(chǔ)上，融入距離矢量路由和迭代循環(huán)的思想，設(shè)計(jì)出的一種定位算法。雖然HopEuclidean算法能夠獲得較準(zhǔn)確的節(jié)點(diǎn)間距，但是由于采用的是最大似然估計(jì)法進(jìn)行估算節(jié)點(diǎn)的位置，而這種估計(jì)方法本身存在一定誤差，這樣就會擴(kuò)大節(jié)點(diǎn)的定位誤差。該算法采用了一種源自心理測量學(xué)和精神物理學(xué)的數(shù)據(jù)分析技術(shù)——多維標(biāo)度技術(shù)MDS(Multidimensional scaling)，這種技術(shù)通常用于探索性的數(shù)據(jù)分析或信息可視化。第一，若傳感器節(jié)點(diǎn)具備測距能力，則直接通過測距技術(shù)所得的傳感器節(jié)點(diǎn)間的距離值。MDSMAP算法是一種集中式定位算法，通常會增加傳感器節(jié)點(diǎn)的計(jì)算量與通信量，從而會消耗大量的能量，而傳感器節(jié)點(diǎn)的能量有限，這樣就會造成節(jié)點(diǎn)在中途能量耗盡無法實(shí)現(xiàn)最終的定位。 本章小結(jié)本章主要是對無線傳感器網(wǎng)絡(luò)及其定位技術(shù)作了介紹。第3章 基于MDSMAP(D)定位算法的改進(jìn)第3章 基于MDSMAP(D)定位算法的改進(jìn) 引言隨著信息化時代的到來，目前WSN商業(yè)化應(yīng)用也不斷興起，同時涌現(xiàn)出大量的科研工作者熱衷于對無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)的研究，于是現(xiàn)已有許多種定位算法，但是各種不同的定位算法適用的環(huán)境都不盡相同。所以定位算法的設(shè)計(jì)都需要根據(jù)實(shí)際應(yīng)用的環(huán)境及硬件條件等要求來進(jìn)行。此外，MDSMAP算法是采用MDS技術(shù)根據(jù)距離矩陣進(jìn)行求解對應(yīng)節(jié)點(diǎn)的位置坐標(biāo)，但通常距離矩陣都比較龐大，則會導(dǎo)致其計(jì)算復(fù)雜度較大，且當(dāng)節(jié)點(diǎn)增加或移動時，需要重新求解，這將會嚴(yán)重阻礙網(wǎng)絡(luò)的擴(kuò)展。 多維標(biāo)度技術(shù)和MDSMAP定位算法 多維標(biāo)度技術(shù)基本原理多維標(biāo)度技術(shù)MDS(Multidimensional scaling)是一種將實(shí)體間的相似信息轉(zhuǎn)換成空間幾何信息的數(shù)據(jù)分析技術(shù)，常用于探索性數(shù)據(jù)分析或信息可視化，最初應(yīng)用于心理測驗(yàn)學(xué)的數(shù)據(jù)分析，現(xiàn)在已