【正文】 基本術(shù)語 鄰居節(jié)點 (neighbor node)： 無線傳感器網(wǎng)絡(luò) 中， 在傳感器節(jié)點通信半徑內(nèi) ，可直接通信的所有其他 節(jié)點 稱為此傳感器節(jié)點的鄰居節(jié)點。 跳段距 離 (hop distance)： 兩個節(jié)點之間 進行通信所需的各跳段距離之和。 測距誤差 (range error)：節(jié)點間通過測距技術(shù)等估算所得的距離和其實際幾何歐式距離的 差值與節(jié)點 的通信半徑的比值。 網(wǎng)絡(luò)連通 度 (work connection degree)： 所以傳感器節(jié)點的鄰居節(jié)點 數(shù)的平均值 。 基于測距 技術(shù)的定位 基于測距技術(shù) 的定位 (Range Based)[38]是通過 一定的方式或技術(shù)獲得 相鄰節(jié)點之間的 實際距離或方位進行定位，要求節(jié)點 具有測距能力。 基于測距技術(shù)的定位一般分為以下 幾個 階段： (1) 測距階段 未知節(jié)點先采用上面 介紹 的測距方法 獲得 自身與其鄰居節(jié)點之間的距離或者角度 信息 ，然后 通過一定 的方式利用 自身與 其鄰居節(jié)點之間的距離 或角度 ， 計算 出自身 到 離其最近的 信標(biāo)節(jié)點 的距離或者 角度 ，可 以直接 計算其直線距離，也可以 用 兩者間的跳段距離來近似代替其直線距離。 (3) 修正階段 采用迭代或遞歸優(yōu)化等數(shù)值分析中的優(yōu)化方法對求得的節(jié)點坐標(biāo)進行求精，提高 其定位精度 。無需測距的定位算法 的定位性能 幾乎不會 受環(huán)境的影響， 即使其 定位 精度會有所下降 ， 也 可 滿足某些應(yīng)用的需要 。 DVHop 算法 DVHop算法 [39]的基本 思想是未知節(jié)點 先計算到信標(biāo)節(jié)點的最少跳數(shù) ，并 估算出平均 每 一 跳 的 距離， 然后用該值乘以 最少跳數(shù) 就可計算 出 與 信標(biāo)節(jié)點 間的 距離 ， 當(dāng)未知節(jié)點獲得與三個或三個以上信標(biāo)節(jié)點的距離時，則執(zhí)行三邊測量定位 。假設(shè)節(jié)點 A 從 2L 獲得 校正值 ， 則 A 與 1L 、 2L 、3L 之間的距離分別為 1L : 3 ? 。 3L :3 ? ，然后根據(jù)三邊測量法計算得出節(jié)點 A 的位置坐標(biāo)。 Euclidean 定位算法 Euclidean算法 [40]是 一種計算與信標(biāo)節(jié)點 相隔兩跳的未知節(jié)點 位置坐標(biāo)的 方法。 ABCLαβ 圖 24 Euclidean 定位算法示意圖 假設(shè) A ， B ， C 為未知節(jié)點， L 為信標(biāo)節(jié)點。節(jié)點 A 與 B ， C 相鄰。 2 2 2c os 2AB AC BCAC BC? ??? ? (21) 2 2 2c os 2B L B C C LC L B C? ??? ? (22) ? ?2 2 2 2 c o sA L A C C L A C C L ??? ? ? ? ? (23) 使用這種方法， 當(dāng)未知節(jié)點 A 獲得與 三個或三個以上 信標(biāo)節(jié)點距離后就可 計算出 自身 的位置坐標(biāo) 。 第 2 章 無線傳感器網(wǎng)絡(luò)及其定位技術(shù) 13 HopEuclidean 定位 算法 HopEuclidean 算法 [41]是在 Euclidean 定位算法基礎(chǔ)上， 融入距離矢量路由和迭代循環(huán) 的思想，設(shè)計出的一種定位算法 。 雖然 HopEuclidean 算法能夠獲得較準(zhǔn)確的節(jié)點間距，但是由于采用的是最大似然估計 法 進行估算節(jié)點的位置， 而 這種估計方法 本身 存在一定誤差，這樣就會擴大節(jié)點的定位誤差。該算法 采用了一種源自心理測量學(xué) 和精神物理學(xué)的數(shù)據(jù)分析技術(shù) —— 多維 標(biāo)度技術(shù)MDS(Multidimensional scaling)， 這種技術(shù)通常用于探索性的數(shù)據(jù)分析或信息可視化。第一，若傳感器節(jié)點具備測距能力，則直接通過測距技術(shù)所得的傳感器節(jié)點間的距離值。 MDSMAP 算法是一種集中式定位算法， 通常會增加傳感器節(jié)點的計算量與 通信量， 從而會消耗大量的能量，而傳感器節(jié)點的能量有限，這 樣就會造成節(jié)點在中途能量耗盡無法實現(xiàn)最終的定位。 本章小結(jié) 本章主要是 對 無線傳感器網(wǎng)絡(luò) 及其 定位技術(shù)作了介紹。 第 3 章 基于 MDSMAP(D)定位算法的 改進 15 第 3 章 基于 MDSMAP(D)定位算法的改進 引言 隨著信息化時代的到來， 目前 WSN商業(yè)化應(yīng)用也不斷興起，同時 涌現(xiàn)出大量的科研工作者熱衷于對 無線傳感器網(wǎng)絡(luò) 節(jié)點定位技術(shù)的研究，于是現(xiàn)已有許多種定位算法，但是各種不同的定位算法適用的環(huán)境都不盡相同 。所以定位算法的設(shè)計都需要根據(jù)實際應(yīng)用的環(huán)境及硬件條件等要求來進行。此外， MDSMAP算法 是采用 MDS技術(shù)根據(jù)距離矩陣進行求解對應(yīng)節(jié)點的位置坐標(biāo) ， 但通常距離 矩陣 都比較 龐大， 則會 導(dǎo)致 其計算復(fù)雜度較大 ， 且當(dāng)節(jié) 點增加或移動時 ， 需要重新求解 ， 這將會嚴(yán)重阻礙 網(wǎng)絡(luò)的擴展 。 多維標(biāo)度技術(shù)和 MDSMAP 定位算法 多維標(biāo) 度 技術(shù) 基本原理 多維標(biāo)度技術(shù) MDS(Multidimensional scaling)是一種將實體間的相似信息轉(zhuǎn) 換成空間幾何信息的數(shù)據(jù)分析技術(shù) ， 常用于探索性數(shù)據(jù)分析或信息可視化 ，最初應(yīng) 用于心理測驗學(xué)的數(shù)據(jù)分析 ， 現(xiàn)在已作為一種通用的數(shù)據(jù)分析技術(shù)廣泛應(yīng)用于各個領(lǐng)域。 假設(shè)研究對象 i 和 j 之間的相異性用 ijp 表示，各研究對象間的相異性 ijp 構(gòu)成相異性矩陣 ijp????。多維標(biāo)度技術(shù)就是利用各實體間的相異性來構(gòu)造多維空間上點的相對坐標(biāo)圖 ，使 ijp 與 ijd 盡可能地接近， 在多維標(biāo)度中其接近程度用脅強系數(shù) (STRESS)來衡量。 1J E n I??? (32) 式中 E 為 n 階的單位矩陣 ， I 為 n 階的全 1矩陣，雙重中心化后的矩陣 B 見式(33)。 于是 ， 在 研究 無線第 3 章 基于 MDSMAP(D)定位算法的 改進 17 傳感器網(wǎng)絡(luò) 的定位 時引入了 MDS 技術(shù) 。該算法 正是利用 MDS 技術(shù)來生成相對坐標(biāo)系統(tǒng)的， 在 較 小規(guī)模規(guī)則 且分布均勻的 網(wǎng)絡(luò)中 ，可 以獲得較高的定位精度 ， 被廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)的相關(guān)項目中。 否則根據(jù)最短路徑算法 ， 求出最短路徑距離， 生成節(jié)點之間的距離 矩陣。 (3) 將相對坐標(biāo)轉(zhuǎn)換 為 絕對坐標(biāo) 當(dāng) 網(wǎng)絡(luò)中 有足夠的信標(biāo)節(jié)點時， 前一步執(zhí)行完后，可以得到每個信標(biāo)節(jié)點通過MDS 技術(shù)估算出的相對坐標(biāo)，根據(jù)估算出的信標(biāo)節(jié)點坐標(biāo)與原本已知的坐標(biāo)關(guān)系，能夠找到一個線性 變換關(guān)系式，然后利用該線性變換關(guān)系式 將相對坐標(biāo) 系統(tǒng)轉(zhuǎn)化為絕對坐標(biāo)系統(tǒng)。但 是通常 節(jié)點 間 通信 會受到環(huán)境的影響 ， 因而通過信號傳播測出的節(jié)點間的距離值都是有誤差的，最終會導(dǎo)致定位誤差 的出現(xiàn) 。而 經(jīng)典 的 MDSMAP算法 就是 采 用跳數(shù) 與 通信距離 乘 積 來 取代 節(jié)點間 的 實際幾何距離， 從而 擴大了 節(jié)點的定位誤差 。 針對經(jīng)典 MDSMAP定位算法的 上述 問題，本文提出了一種基于 HopEuclidean燕山大學(xué)工學(xué)碩士學(xué)位論文 18 的 MDSMAP(D)定位算法。 (5) 部分節(jié)點 的位置信息已經(jīng) 通過安裝 GPS接收器或人工部署 的方式確定 (即信標(biāo) 節(jié)點 )； (6) 無線傳感器 網(wǎng)絡(luò)的 全局時間 是 統(tǒng)一的， 每個傳感器 節(jié)點都 裝 備著 定時器。 為了 提高本章提出的定位算法的定位性能，在本節(jié) 提出了一種適用于本章定位算法的 分簇算法。 假設(shè)簇頭 節(jié)點的鄰居節(jié)點平均轉(zhuǎn)發(fā)數(shù)據(jù)總流量為 F ，簇頭的 連通度為 cd ， 簇頭 節(jié)點的鄰居 節(jié)點 平均轉(zhuǎn)發(fā)的數(shù)據(jù)流量 cf F d? ： f 與 cd 成反比。 于是本文 把連通度和殘存能量信息作為選擇簇頭的 兩個主要 參數(shù)，首先 根據(jù)實際應(yīng)用預(yù)先設(shè)定節(jié)點能量門限值 為 0E ，連通度門限值為 0d ，假定需要選擇 n 個簇頭節(jié)點，則 具體選擇過程分以下幾種情況： 第一種情況 能量值 iE 大于其門限值 0E ，且連通度 id 大于門限值 0d 作為初選簇第 3 章 基于 MDSMAP(D)定位算法的 改進 19 頭節(jié)點，如果其數(shù)量大于所需的簇頭節(jié)點數(shù)量 n ，則根據(jù)公式 (34)計算出初選簇頭節(jié)點的綜合性能值 iT ， 將初選簇頭節(jié)點 按照其綜合性能值的大小進行從大到小排序。 最后選擇其中的前 n 個節(jié)點作為最終的簇頭節(jié)點。 第三種情況 初選簇頭節(jié)點個數(shù) 為 m 小于所需簇頭節(jié)點數(shù)量 n ， 則 其余的 nm?個簇頭節(jié)點 需則根據(jù)公式 (34)計算出 剩余 節(jié)點的綜合性能值 iT ，將 剩余 節(jié)點按照其綜合性能值的大小進行從大到小排序 ，選擇其中的前 nm? 個節(jié)點作為最終的簇頭節(jié)點。 接下來闡述上述問題的解決方案，為了更直觀些，通過下面例子進行分析。對于剩余的重疊節(jié)點，先比較所屬簇的簇頭節(jié)點的殘余能量的大小，在殘余能量大的簇頭節(jié)點所在簇中進行局部定位即可。 51 19841 311 0761 21 41 51 61 71 8c l u s t e r h e a d c l u s t e r M e m b e r S i n k23 a) 其他兩簇沒有重疊部分 51 19841 33211 0761 21 41 51 61 71 8c l u s t e r h e a d c l u s t e r M e m b e r S i n k b) 其他兩簇有重疊部分 圖 31 一個簇中的節(jié)點 分別 屬于 其他 兩簇 分簇結(jié)束后，同時屬于多個簇的節(jié)點起到了簇頭間的連接 及求解坐標(biāo)轉(zhuǎn)換參數(shù)的 作用 。 局部定位 分簇完成后，先由 成為簇頭的節(jié)點通過執(zhí)行 HopEuclidean算法 (該算法 是 采用距離矢量路由技術(shù)與 Euclidean算法 相結(jié)合的方法求解節(jié)點間的距離 )，獲得簇內(nèi)節(jié)點之間的距離，具體過程 見算法 。 設(shè)節(jié)點的 ID為 i ， 第 3 章 基于 MDSMAP(D)定位算法的 改進 21 輸入： 由信標(biāo)節(jié)點向所有節(jié)點廣播一個四元組的消息 (自身 ID，自身位置信息，初始值為 1的跳數(shù)計數(shù)器，中間節(jié)點 ID)； 輸出： 與 節(jié)點本身 相隔兩跳內(nèi)的所有信標(biāo)節(jié)點的相關(guān)信息 。 /*orphan表示是否為孤立的節(jié)點，如果是設(shè)改標(biāo)記為 true，否則為 false*/ (3) end if (4)if anchor==ture then/* anchor表示是否為信標(biāo)節(jié)點，如果是設(shè)該標(biāo)記位為 true，否則為false*/ (5) Broadcast MSG(ID←i,location←(x 1,x2,…xm),hop←1,MNode← ?,TTL←2)。amp。 (9) Broadcast MSG to neighbour。 (13) end if (14) end if (15)if node accept this MSG amp。 anchor==false then (16) if MNode==? then (17) Mnode←i,hop++。 (19) end if (20) if MNode≠? then (21) if node accept this MSG by MNode then (22) discard M