【正文】 常有限，與普通計(jì)算機(jī)相比會差的多，由于受這些因素的約束，因而為其設(shè)計(jì)的程序等都不能太復(fù)雜。 (2) 網(wǎng)絡(luò)節(jié)點(diǎn) 拓?fù)?變化頻繁 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) 的改變是不可避免的 。 其中， 采集 監(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是 環(huán)境感知與監(jiān)控領(lǐng)域 的一場革命。 第 4章 主要針對加權(quán)分布式多維標(biāo)度定位算法的不足提出了一種改進(jìn)方案 。本文主要 針對 分布式加權(quán)多維標(biāo)度定位算法這兩方 面的不足， 提出了一種改進(jìn)方案。 位置信息 不僅可以 用 于監(jiān)測 事件發(fā)生的 地點(diǎn)，還可用于 跟蹤 目標(biāo)、 預(yù)測 目標(biāo)軌跡、協(xié)助路由及網(wǎng)絡(luò)拓?fù)涔芾淼取Ｄ壳耙延?不少 研究者 對 這種定位算法 作了多方面的改進(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)系。 2020年， Tian He等 人 提出了 一種 采用 求解約束集合 進(jìn)行定位的APIT算法 [18]；哥倫比亞大學(xué)的 Shang Yi等人 在 MDS技術(shù) ， 提出了 MDSMAP， MDSMAP(P)， MDSMAP(C)等幾種集中式定位算法 [1922]。 WSN中的 定位技術(shù)是大多數(shù) 有關(guān) WSN應(yīng)用 的 支撐技術(shù) 和關(guān)鍵技術(shù)之一 。所以 ，實(shí)現(xiàn) WSN節(jié)點(diǎn)定位 不能全依賴 GPS系統(tǒng)來完成，只能是通過該系統(tǒng)獲取少數(shù)節(jié)點(diǎn)的位置信息再通過其他的定位技術(shù)來實(shí)現(xiàn)其他大量節(jié)點(diǎn)的定位 。比如在 軍事應(yīng)用 中 ， 對敵方軍事目標(biāo)的定位可以 決定是否需 集中 火力進(jìn)行打 擊 ；在 森林 中 發(fā)生火災(zāi)時 ， 監(jiān)測發(fā)生火災(zāi)的具體區(qū)域與火勢情況可以決定是否需要增加軍力救助 等等。 無線傳感器網(wǎng)絡(luò) WSN(wireless sensor work)[1,2]是指由大量成本低廉的，具有感知能力 、無線通信能力 、計(jì)算能力的傳感器節(jié)點(diǎn) 構(gòu)成的網(wǎng)絡(luò)。 53 致 謝 36 性能評價指標(biāo) 15 MDSMAP 定位算法 13 第 3 章 基于 MDSMAP(D)定位算法的改進(jìn) 1 研究背景及研究意義 Multidimensional scaling。 其次 ， 介紹了多維標(biāo)度技術(shù)及其在無線傳感器網(wǎng)絡(luò)定位算法中的應(yīng)用。本人授權(quán)燕山大學(xué)，可以采用影印、縮印或其他復(fù)制手段保存論文，可以公布論文的全部或部分內(nèi)容。 碩 士 學(xué) 位 論 文 MASTER’S DISSERTATION 論文題目 無線傳感器網(wǎng)絡(luò)定位算法 的研究 A Dissertation in Computer Application Technology STUDY ON LOCALIZATION ALGORITHM OF WIRELESS SENSOR NETWORK by Hu Yulan Supervisor: Professor Wang Xinsheng Yanshan University 燕山大學(xué)碩士學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：此處所提交的碩士學(xué)位論文《 無線傳感器網(wǎng)絡(luò)定位 算法 的研究 》，是本人在導(dǎo)師指導(dǎo)下，在燕山大學(xué)攻讀碩士學(xué)位期間獨(dú)立進(jìn)行研究工作所取得的成果。 保密□，在 年解密后適用本授權(quán)書。在分析經(jīng)典 MDSMAP 定位算法的基礎(chǔ)上，提出基于 HopEuclidean 的 MDSMAP(D)定位算法 。 HopEuclidean algorithm。 I Abstract 11 DVHop 算法 11 Euclidean 定位算法 12 HopEuclidean 定位算法 23 基于 HopEuclidean 的 MDSMAP(D)算法定位過程 32 本章小結(jié) 它主要針對缺乏或 無法 建立通信基礎(chǔ)設(shè)施的 區(qū) 域，通過大規(guī)模的、具有一定定位能力、通信能力、數(shù)據(jù)處理能力的傳感器節(jié)點(diǎn)建立聯(lián)系，提供 數(shù)據(jù)。 其二 ， WSN的 運(yùn)行和管理 仍 需 有 節(jié)點(diǎn)位置信息的協(xié)助 。 近年來，不少研究者們在 WSN定位技術(shù)方面已經(jīng)取得了一定的研究成果，但是目前仍處于初級階段，還有好多問題沒有徹底解決，有一定的局限性。該技術(shù)是指 WSN通過特定 系統(tǒng)或算法來獲取傳感器 節(jié)點(diǎn) 的 位置信息。 隨著集中式定位算法的研究趨于成熟 及 WSN規(guī)模的不斷擴(kuò)大 ， 如今大量的科研工作者們致力于研究 分布式 的 定位算法 。 于是， 針對 MDSMAP算法的不足， 引入了“補(bǔ)丁”這一概念，提出了 MDSMAP(P)定位算法 ； 文獻(xiàn) [30]是 一種基于 非度量多維標(biāo)度技術(shù)的定位算法， 通過 多次 迭代 來 不 斷修正距離和相異性 間的 單調(diào)關(guān)系的過程。因此， WSN的 節(jié)點(diǎn)定位技術(shù) 有很大的 研究價值 ，是 WSN中重要的研究方向之一 。本文提出的改進(jìn)算法中采用的加權(quán)機(jī)制與鄰居選擇機(jī)制都綜合考慮了節(jié)點(diǎn)間距離的遠(yuǎn)近與參與定位 的鄰居節(jié)點(diǎn)的定位誤差等因素，同時為了加快算法的收斂速度，引入了無約束最優(yōu)化中簡單且收斂速度較快的最速下降法對其目標(biāo)代價函數(shù)進(jìn)行優(yōu)化 。 概述了 加權(quán)分布式多維標(biāo)度定位算法 的特點(diǎn)與定位過程， 同時 主要 針對其 加權(quán)機(jī)制和自適應(yīng) 2步鄰居選擇機(jī)制的不足做了較全面的分析 ，接下來對改進(jìn)的鄰居選擇機(jī)制與加權(quán)機(jī)制做了詳細(xì)的闡述，并給出了采用最速下降法 對其目標(biāo)代價函數(shù)進(jìn)行優(yōu)化求解 的具體過程 。 WSN作為一個全新 且熱門 的研究 方向， 給科技研究者們 提出了 許多在工程技術(shù)等層面的 挑戰(zhàn)性課題。 傳 感 器A C / D C處 理 器存 儲 器網(wǎng) 絡(luò)M A C收 發(fā) 器能 量 供 應(yīng) 模 塊傳 感 器 模 塊 處 理 器 模 塊無 線 通 信 模 塊 圖 22 傳感器節(jié)點(diǎn)體系結(jié)構(gòu) 無線傳感器網(wǎng)絡(luò) 的特點(diǎn) WSN有很多地方 與無線自組網(wǎng)絡(luò) 的 很 相似， 同時 也 存在著很多 技術(shù) 方面的區(qū)別[37]。 第 2 章 無線傳感器網(wǎng)絡(luò)及其定位技術(shù) 9 (3) 應(yīng)用相關(guān) WSN的設(shè)計(jì)有多種多樣，只能根據(jù)其具體的應(yīng)用場合進(jìn)行設(shè)計(jì)比如有的需要獲取非常準(zhǔn)確的信息并不關(guān)心它所花費(fèi)的時間，有的則需要對二者折中考慮，這樣一來在設(shè)計(jì) WSN時的側(cè)重點(diǎn)就不一樣，那么 其網(wǎng)絡(luò)協(xié)議和軟、硬件平臺 一定 會 有所不同 。此外，傳感器節(jié)點(diǎn)的能力決定著傳感器網(wǎng)絡(luò)的壽命，而傳感器節(jié)點(diǎn)通常部署在人們很難抵達(dá)的區(qū)域，為其更換電池是很不現(xiàn)實(shí)的，故而節(jié)點(diǎn)的能量是非常受限的。 網(wǎng)絡(luò)密度 (work density)：一個傳感器節(jié)點(diǎn)通信時所覆蓋區(qū)域內(nèi)的節(jié)點(diǎn)平均數(shù)目，常記為 ? ?R? 。 (2) 定位階段 未知節(jié)點(diǎn) 通過上面的測距階段 計(jì)算出 與 其 3個 (或 3個以上 )鄰 居信標(biāo)節(jié)點(diǎn)間的距離 (或角度 )后，采用三邊 (或三角 )測量法 、 極大似然估計(jì)法等方法計(jì)算第 2 章 無線傳感器網(wǎng)絡(luò)及其定位技術(shù) 11 出自身的位置坐標(biāo)。 2L : 2 ? 。 在 四邊形 ABCL 中， 己知 所有邊的長度與 對角 線 BC的長度 ，則 由三角形中的余弦定理即 可通過式 (21)、式 (22)、式 (23)計(jì)算出 AL 的長度 (未知 節(jié)點(diǎn) A 與 信標(biāo)節(jié)點(diǎn) L 間的 距離 )。該算法可分為 3個步驟。比如， DVHop算法是適合于硬件配置較低、對節(jié)點(diǎn)定位精度要求不太高的 應(yīng)用 ；而 Euclidean定位算法是適合于節(jié)點(diǎn)具有測距能力的、且環(huán)境中的噪聲相對較小的 應(yīng)用場合下使用； MDSMAP算法 是適合于網(wǎng)絡(luò)連通度相對比較大 、且傳感器節(jié)點(diǎn)的能量充足、計(jì)算能力較強(qiáng)的小規(guī)模拓?fù)湟?guī)則的 無線傳感器網(wǎng)絡(luò) 。 構(gòu)造多維空間上點(diǎn)的坐標(biāo)矩陣用 nmX? 表示，其中 n 為坐標(biāo)點(diǎn)的個數(shù)，n 為坐標(biāo)點(diǎn)的維數(shù)， 實(shí)體對象 i 和 j 的坐標(biāo)分別為 ? ?12, , ,i i i imX x x x? ，? ?12, , ,j j j jmX x x x? ，多維空間上 i 和 j 之間的歐式距離用 ijd 表示。 MDSMAP 算法 分為三步 ： (1) 生成距離矩陣 首先從全局角度 生成網(wǎng)絡(luò)拓?fù)溥B通圖， 如果 節(jié)點(diǎn)具 備 測距能力， 則通過測距技術(shù)獲得的節(jié)點(diǎ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ò)展 。由于 簇頭節(jié)點(diǎn) 既 要 將 簇內(nèi)節(jié)點(diǎn)的相關(guān)信息 存儲 起來 ， 又 要 管理 其 簇 內(nèi)節(jié)點(diǎn)， 因此，其 通信 量 及 計(jì)算量 都會 遠(yuǎn) 大于 其 簇內(nèi)節(jié)點(diǎn)， 故簇頭節(jié)點(diǎn)應(yīng)比 簇內(nèi)節(jié)點(diǎn) 具有更高的能量。 如圖 31 a)所示 ， 簇 2中 的所有節(jié)點(diǎn) 都分別屬于簇 1和簇 3，如節(jié)點(diǎn) 113既在簇 1中又在簇 2中，節(jié)點(diǎn) 1 1 15既在簇 2中又在簇 3中，如果按正常的處理方式，這九個節(jié)點(diǎn)都得進(jìn)行兩次定位 ，這樣就會造成的重復(fù)定位，既浪費(fèi)時間又浪費(fèi)能量，從表面上看此時的簇頭節(jié)點(diǎn) 2可以取消，但是由于簇 1與簇 3沒有重疊的部分，所以此時的簇 2還必須保留，只是定位時，如果重疊度大于 5，則從重疊的節(jié)點(diǎn)中選擇 2個在兩個簇中都進(jìn)行局部定位以便最后一步參與融合算法。 Begin (1)if neighbour(i)3 then (2) orphan←ture。amp。 (18) Broadcast MSG to neighbour。 /*ID表示自身 ID， location表示自身位置， hop表示跳計(jì)數(shù)器， Mnode表示中間節(jié)點(diǎn) ID，TTL表示生命周期域 */ (6)if node accept this MSG amp。 如圖 31 b)所示，簇 2中的所有節(jié)點(diǎn)都分別屬于簇 1和簇 3，如節(jié)點(diǎn) 113既在簇 1中又在簇 2中，節(jié)點(diǎn) 1 1 1 1 15既在簇 2中 又在簇 3中，如果按正燕山大學(xué)工學(xué)碩士學(xué)位論文 20 常的處理方式，這 9個節(jié)點(diǎn)都 需 進(jìn)行兩次定位，這樣就會造成的重復(fù)定位，既浪費(fèi)時間又浪費(fèi)能量，像這樣的情況簇 2完全可以取消。 12i i iT w E w d?? (34) 式 中 1w 、 2w —— 權(quán)值，具體怎么取根據(jù)實(shí)際情況設(shè)定，只要滿足 121ww??即可。 在采用 基于 HopEuclidean的 MDSMAP(D)算法定位之前， 需做以下假設(shè) ： (1) 為了計(jì)算方便，設(shè)定 部署 傳感器節(jié)點(diǎn) 的區(qū)域是二維的， 且 部署后位置靜止； (2) 傳感器節(jié)點(diǎn)的 ID是唯