【正文】 無需測距的 定位算法 無需測距的定位算法 僅 需依 據(jù)網(wǎng)絡連通性等信 息就可 得到 未知節(jié)點 在網(wǎng)絡中 的位置 坐標 ， 這樣 就會使得 節(jié)點硬件的要求 降低 ， 從而 使 其更加 適 用于 大規(guī)模 WSN。 (2) 定位階段 未知節(jié)點 通過上面的測距階段 計算出 與 其 3個 (或 3個以上 )鄰 居信標節(jié)點間的距離 (或角度 )后，采用三邊 (或三角 )測量法 、 極大似然估計法等方法計算第 2 章 無線傳感器網(wǎng)絡及其定位技術 11 出自身的位置坐標。目前 WSN定位中， 可以使用多種測距技術，如測量無線電、紅外線、激光信號強度， 測量 無線電信號 或超聲波等到達的時間，測量 無線電信號 或超聲波等到達的時間 差 等。 定位 覆蓋率 (coverage rate)： 無線傳感器網(wǎng)絡中， 能確定坐標位置的未知節(jié)點 占總節(jié)點數(shù)的比例 。 定位誤差 (position error)：通過 定位算法計算 出 的坐標 和其 實際坐標的差值與節(jié)點的通信半徑的比值 。 網(wǎng)絡密度 (work density)：一個傳感器節(jié)點通信時所覆蓋區(qū)域內(nèi)的節(jié)點平均數(shù)目，常記為 ? ?R? 。 跳數(shù) (hop count)：兩個節(jié)點之間建立通信需要經(jīng)過的跳段總數(shù)，稱為兩 點 之 間的跳數(shù)。信標節(jié)點是未知節(jié)點定位的參考點 ， 未知節(jié)點是根據(jù)信標節(jié)點的位置信息利用節(jié)點燕山大學工學碩士學位論文 10 間的連通約束等通過一定技術來確定自身位置。在 WSN節(jié)點 的 定位技術中， 根據(jù)節(jié)點是否已知自身的位置 ， 將 傳感器節(jié)點分為兩類：一類是 位置已知的 信標節(jié)點 (beacon node)， 另一類是需要獲取其位置信息的 未知節(jié)點 (unknown node)。此外，傳感器節(jié)點的能力決定著傳感器網(wǎng)絡的壽命，而傳感器節(jié)點通常部署在人們很難抵達的區(qū)域，為其更換電池是很不現(xiàn)實的，故而節(jié)點的能量是非常受限的。 (6) 節(jié)點 資源有 限 傳感器節(jié)點資源包括兩方面：其一是計算能力，其二是節(jié)點的能量。 (5) 網(wǎng)絡可靠性 通常 部署 傳感器節(jié)點 的環(huán)境都比較 惡劣 甚至 人類 無法 抵達 ， 因此， 傳感器節(jié)點 必須 結實耐用 ， 同時能夠 適應各種 各樣 的惡劣環(huán)境。 (4) 尋址以數(shù)據(jù)為中心 WSN只關心數(shù)據(jù)本身，比 如事件發(fā)生的時間、地點即位置，并不關心數(shù)據(jù)是哪個節(jié)點監(jiān)測或采集到的。 第 2 章 無線傳感器網(wǎng)絡及其定位技術 9 (3) 應用相關 WSN的設計有多種多樣，只能根據(jù)其具體的應用場合進行設計比如有的需要獲取非常準確的信息并不關心它所花費的時間，有的則需要對二者折中考慮，這樣一來在設計 WSN時的側重點就不一樣，那么 其網(wǎng)絡協(xié)議和軟、硬件平臺 一定 會 有所不同 。系統(tǒng)的工作質(zhì)量并 不是通過 提升單個設備的能力 提高，而是靠 大量冗余節(jié)點的協(xié)同工作來提高 的 。 除了這些 ， WSN還具有以下一些 與 無線自組網(wǎng)絡不同的特點。而 傳輸數(shù)據(jù) 才是 無線自組網(wǎng)絡 的主要目的，它并不太關注數(shù)據(jù)的處理 。 傳 感 器A C / D C處 理 器存 儲 器網(wǎng) 絡M A C收 發(fā) 器能 量 供 應 模 塊傳 感 器 模 塊 處 理 器 模 塊無 線 通 信 模 塊 圖 22 傳感器節(jié)點體系結構 無線傳感器網(wǎng)絡 的特點 WSN有很多地方 與無線自組網(wǎng)絡 的 很 相似， 同時 也 存在著很多 技術 方面的區(qū)別[37]。 (2)傳感器節(jié)點結構 通常傳感器節(jié)點是 一個 由 采集 模塊 (傳感器， AC/DC轉換器 )、無線通信模塊 (主要有收發(fā)器 )、能量供應模塊 (電池、 DC/DC能量轉換器 )、 控制模塊 (微處理器、存儲器 )以及其它輔助可選功能模塊等部分組成 的 微型的嵌入式系統(tǒng)[35]， 如圖 22所示。 其中的各個傳感器 節(jié)點 都具有 收集 信息及 監(jiān)測數(shù)據(jù) 的功能 ， 而且可以將檢測或收集到的 數(shù)據(jù) 傳播給其他傳感器節(jié)點，這樣在傳播的過程中就會出現(xiàn)“冗余”現(xiàn)象即有可能多個節(jié)點同時處理一個數(shù)據(jù)，因此都應先將燕山大學工學碩士學位論文 8 這些被處理過的數(shù)據(jù)傳輸給匯聚節(jié)點，由匯聚節(jié)點進行相應的處理。 其中，傳感器節(jié)點相對于匯聚節(jié)點，其 通信能力 、 存儲能力和處理能力通常較弱，而且其能量 十分 有限 (通 常 利 用電池供電 )。 WSN作為一個全新 且熱門 的研究 方向， 給科技研究者們 提出了 許多在工程技術等層面的 挑戰(zhàn)性課題。 WSN的發(fā)展將有助于物聯(lián)網(wǎng)等前沿學科全面提升社會生產(chǎn)生活中信息互通性、信息感知能力和智能決策能力等，進而增強整個系統(tǒng)的性能。因而，傳感器技術作為信息獲取最基本且最重要的技術 [32]，也在不斷發(fā)展。 燕山大學工學碩士學位論文 6 最后 對本文的研究工作做了總結和展望。 概述了 加權分布式多維標度定位算法 的特點與定位過程， 同時 主要 針對其 加權機制和自適應 2步鄰居選擇機制的不足做了較全面的分析 ，接下來對改進的鄰居選擇機制與加權機制做了詳細的闡述，并給出了采用最速下降法 對其目標代價函數(shù)進行優(yōu)化求解 的具體過程 。 第 3章 詳細闡述了多維標度技術在無線傳感器網(wǎng)絡定位算法中的應用 及MDSMAP定位算法 ， 著重 對 MDSMAP定位算法的不足之處做了 較全面的分析， 主要針對其有較大的距離誤差及不適用于大規(guī)模密集型網(wǎng)絡兩方面的不足， 提出了 一種 基于 HopEuclidean的 MDSMAP(D)定位算法 ，并 對其 進行了詳細的闡述。 論文結構安排 本文 是圍繞著無線傳感器網(wǎng)絡的 定位 算法 進行的， 論文的結構 安排如下 。經(jīng)過分析 和 仿真結果表明， 改進的 MDSMAP定位算法 在定位精度提高的情況下，對不規(guī)則網(wǎng)絡和大規(guī)模 密集型 網(wǎng)絡有更好的適應性 ；改進的分布式加權多維標度定位算法有效抑制了較大定位誤差在網(wǎng)絡中擴散，而且 對不規(guī)則網(wǎng)絡和 大規(guī)模稀疏型網(wǎng)絡都 有 很 好的適應性 。本文提出的改進算法中采用的加權機制與鄰居選擇機制都綜合考慮了節(jié)點間距離的遠近與參與定位 的鄰居節(jié)點的定位誤差等因素，同時為了加快算法的收斂速度，引入了無約束最優(yōu)化中簡單且收斂速度較快的最速下降法對其目標代價函數(shù)進行優(yōu)化 。 第 1 章 緒 論 5 其次，重點分析研究了 分布式加權多維標度定位算法， 經(jīng)過研究發(fā)現(xiàn)，該算法由于采用的是高斯加權機制和自適應 2步鄰居選擇機制，造成離未知節(jié)點近的節(jié)點定位誤差不斷擴大 ；此外，如果網(wǎng)絡稀疏時，會有部分節(jié)點的 1跳鄰居節(jié)點很少， 這樣就會使得這些節(jié)點無法實現(xiàn)定位。本文主要是針對 MDSMAP 算法這兩 方面的不足 提出了一 種基于 HopEuclidean的MDSMAP(D)定位算法。 首先， 重點 分析 研究了 MDSMAP定位算法 ，經(jīng)過分析發(fā)現(xiàn)，經(jīng)典的 MDSMAP定位算法在節(jié)點間的測量距離沒有誤差的情況下，通過 MDS技術可以計算出準確的節(jié)點位置坐標。因此， WSN的 節(jié)點定位技術 有很大的 研究價值 ，是 WSN中重要的研究方向之一 。 研究內(nèi)容及 主要工作 在 WSN的應用中，絕大多數(shù)情況下需要有節(jié)點位置信息，否則采集到的數(shù)據(jù)將沒有任何意義，尤其是關于環(huán)境監(jiān)測、橋梁結構變化監(jiān)測、管道泄漏監(jiān)測等，發(fā)生地點的地理位置信息非常重要。 然而雖然 經(jīng)過這 些年 學術界、軍界及商業(yè)界 的不斷 努力，目前 無線傳感器網(wǎng)絡節(jié)點的自 身 定位問題 在一定程度上 能夠 解決，但 仍有 許多 問題 沒有得到有效合理的解決 ， 比 如 ， 通過測距技術獲得的節(jié)點間距離仍有一定的誤差 、 在定位過程中 所需的 通信開銷 仍比較大 等 問題 。 但是幾種算法所 改進 的 只是 在 計算規(guī)模 方面 對算法進行 了 改進， 并沒有 解決 MDSMAP所 存在的 全部 問題。 于是， 針對 MDSMAP算法的不足， 引入了“補丁”這一概念，提出了 MDSMAP(P)定位算法 ； 文獻 [30]是 一種基于 非度量多維標度技術的定位算法， 通過 多次 迭代 來 不 斷修正距離和相異性 間的 單調(diào)關系的過程。 本文主要研究 基于多維標度 分布式的定位算法 。 近年來， 隨著科學技 術的發(fā)展與 WSN實用價值的不斷提升， 國內(nèi) 的一些 高校和研究 所 也 開始對有關 WSN的理論和應用的研究工作 [26,27]， 2020年，在有關集成技術的國際會議上提出了一種自適應鄰居選擇的分布式定位算法 [28]。 2020年， 麻省理工學院的 RVSN和 NMS兩個研究小組在“分布式傳感器網(wǎng)絡的定位與追蹤”項目中提出 了 一種 分布式定位算法 ，該算法 是 通過 節(jié)點間 距離的 估計值 獲取節(jié)點的二維坐標 信息 ，有 較高的覆蓋率 [24]。 隨著集中式定位算法的研究趨于成熟 及 WSN規(guī)模的不斷擴大 ， 如今大量的科研工作者們致力于研究 分布式 的 定位算法 。 2020年， Srdjan Capkun等人提出了一種 針對無基礎設施的移動無線網(wǎng)絡的 相對定位算法 [17]； 2020年 8月， Akyildiz等 人 發(fā)表了 以 “ A Survey on Sensor Networks” 為題 的綜述性學術論文 以來 ， 又一 次激發(fā)了學術界對WSN的研究興趣。 2020年， Nimpama Bulusu教授等 人 提出了 一種無需測距的定位算法 —— 質(zhì)心算法 [12]， 此定位算法 是基于網(wǎng)絡連通性 通過節(jié)點之間相互發(fā)送信息獲得節(jié)點間的跳數(shù)信息 進行定位的 ； 適合部署在室內(nèi)的傳感器節(jié)點定位的 RADAR系統(tǒng) 是由 微軟公司的Bahl P等人 開發(fā) 出的 唯一 一種 根據(jù) 的定位系統(tǒng) [13]；加州大學伯克利分校的 Doherty等 人 ， 引入了“凸集” 這一概念 ，將整個網(wǎng)絡模型 看作 一個凸第 1 章 緒 論 3 集， 那么就可以把 傳感器節(jié)點的定位問題 看作一個 凸約束優(yōu)化問題 [14]，其中 的幾何約束 是 傳感器 節(jié)點 間 的 通信連接； 同年， 麻省理工學院的 Priyantha N也開發(fā)出了一種室內(nèi)定位系統(tǒng) —— Cricket系統(tǒng) [15,16]。 進入 21世紀， 軍界 、 學術界 和工業(yè)界 都 極 其 關注 有關 傳感器網(wǎng)絡技術 的研究與發(fā)展 。該技術是指 WSN通過特定 系統(tǒng)或算法來獲取傳感器 節(jié)點 的 位置信息。 近年來隨著無線通信技術、 片上系統(tǒng) 、 MEMS的發(fā)展 與進步 ， WSN的理想藍圖 逐一 實現(xiàn)，其應用越來越廣 泛 ， 從而 得到 了 研究者們 的 極度 關注。 最初受客觀條件的限制 ，傳感器網(wǎng)絡只能 應用于 軍事領域 的一些 重要 項目中， 對其 推廣 與 發(fā)展 是很 困難 的 。 傳感器網(wǎng)絡最初來源于美國先進國防研究項目局 DARPA(Defense Advanced Research Projects Agency)的一個研究項目 [10,11]。 近年來，不少研究者們在 WSN定位技術方面已經(jīng)取得了一定的研究成果，但是目前仍處于初級階段，還有好多問題沒有徹底解決，有一定的局限性。 根據(jù) WSN的特點 ，傳感器節(jié)點的位置信息應該 以最小通信開銷和 最低的 硬件代價來 獲取 。 GPS是 目前使用的最著名 的定位系統(tǒng) [9]， 用 GPS系統(tǒng)獲取傳感器節(jié)點燕山大學工學碩士學位論文 2 位置信息 ，具有 較好的實時性 、 較 強 的 抗干擾能力、 較 高 的 定位精度 等優(yōu)點。 因此， 節(jié)點定位問題已成為 WSN的一個至關重要的研究課題。 其二 ， WSN的 運行和管理 仍 需 有 節(jié)點位置信息的協(xié)助 。 其一 ， 節(jié)點自身位置的缺點是 WSN中的很多特定應用 的基礎 ， 在 傳感器 節(jié)