【文章內容簡介】 信的保密性和安全性也是至關重要的，故而要想設計一個好的無線傳感器網絡的必須考慮其魯棒性和容錯性。(6) 節(jié)點資源有限 傳感器節(jié)點資源包括兩方面：其一是計算能力，其二是節(jié)點的能量。傳感器節(jié)點由于受體積、價格及功耗的制約，其計算能力和內存空間是非常有限，與普通計算機相比會差的多，由于受這些因素的約束，因而為其設計的程序等都不能太復雜。此外，傳感器節(jié)點的能力決定著傳感器網絡的壽命，而傳感器節(jié)點通常部署在人們很難抵達的區(qū)域，為其更換電池是很不現實的，故而節(jié)點的能量是非常受限的。 定位技術的相關概念及術語(1) WSN定位的基本概念在WSN中，節(jié)點定位(node localization)是指根據若干個位置已知的節(jié)點和節(jié)點間的連通性采用一定的方式獲取WSN中其余節(jié)點的絕對(相對于地理經緯度)或相對位置信息。在WSN節(jié)點的定位技術中，根據節(jié)點是否已知自身的位置，將傳感器節(jié)點分為兩類：一類是位置已知的信標節(jié)點(beacon node)，另一類是需要獲取其位置信息的未知節(jié)點(unknown node)。信標節(jié)點是指通過手動設置或攜帶GPS定位設備等手段獲得自身的精確位置信息的傳感器節(jié)點，其在WSN的節(jié)點中所占的比例是很低的。信標節(jié)點是未知節(jié)點定位的參考點，未知節(jié)點是根據信標節(jié)點的位置信息利用節(jié)點間的連通約束等通過一定技術來確定自身位置。(2) 基本術語鄰居節(jié)點(neighbor node)：無線傳感器網絡中，在傳感器節(jié)點通信半徑內，可直接通信的所有其他節(jié)點稱為此傳感器節(jié)點的鄰居節(jié)點。跳數(hop count)：兩個節(jié)點之間建立通信需要經過的跳段總數，稱為兩點之間的跳數。跳段距離(hop distance)：兩個節(jié)點之間進行通信所需的各跳段距離之和。網絡密度(network density)：一個傳感器節(jié)點通信時所覆蓋區(qū)域內的節(jié)點平均數目，常記為。測距誤差(range error)：節(jié)點間通過測距技術等估算所得的距離和其實際幾何歐式距離的差值與節(jié)點的通信半徑的比值。定位誤差(position error)：通過定位算法計算出的坐標和其實際坐標的差值與節(jié)點的通信半徑的比值。網絡連通度(network connection degree)：所以傳感器節(jié)點的鄰居節(jié)點數的平均值。定位覆蓋率(coverage rate)：無線傳感器網絡中，能確定坐標位置的未知節(jié)點占總節(jié)點數的比例。 基于測距技術的定位基于測距技術的定位(Range Based)[38]是通過一定的方式或技術獲得相鄰節(jié)點之間的實際距離或方位進行定位，要求節(jié)點具有測距能力。目前WSN定位中，可以使用多種測距技術，如測量無線電、紅外線、激光信號強度，測量無線電信號或超聲波等到達的時間，測量無線電信號或超聲波等到達的時間差等?；跍y距技術的定位一般分為以下幾個階段：(1) 測距階段 未知節(jié)點先采用上面介紹的測距方法獲得自身與其鄰居節(jié)點之間的距離或者角度信息，然后通過一定的方式利用自身與其鄰居節(jié)點之間的距離或角度，計算出自身到離其最近的信標節(jié)點的距離或者角度，可以直接計算其直線距離，也可以用兩者間的跳段距離來近似代替其直線距離。(2) 定位階段 未知節(jié)點通過上面的測距階段計算出與其3個(或3個以上)鄰居信標節(jié)點間的距離(或角度)后，采用三邊(或三角)測量法、極大似然估計法等方法計算出自身的位置坐標。(3) 修正階段 采用迭代或遞歸優(yōu)化等數值分析中的優(yōu)化方法對求得的節(jié)點坐標進行求精，提高其定位精度。 無需測距的定位算法無需測距的定位算法僅需依據網絡連通性等信息就可得到未知節(jié)點在網絡中的位置坐標，這樣就會使得節(jié)點硬件的要求降低，從而使其更加適用于大規(guī)模WSN。無需測距的定位算法的定位性能幾乎不會受環(huán)境的影響，即使其定位精度會有所下降，也可滿足某些應用的需要。基于本文的研究重點與三種無需測距定位算法：DVHop算法、Euclidean定位算法和MDSMAP算法有關，接下來具體介紹這三種經典的定位算法。 DVHop算法DVHop算法[39]的基本思想是未知節(jié)點先計算到信標節(jié)點的最少跳數，并估算出平均每一跳的距離，然后用該值乘以最少跳數就可計算出與信標節(jié)點間的距離，當未知節(jié)點獲得與三個或三個以上信標節(jié)點的距離時，則執(zhí)行三邊測量定位。如圖23所示，已知信標節(jié)點與、之間的距離和跳數，計算得到校正值(即平均每跳距離)。假設節(jié)點從獲得校正值，則與、之間的距離分別為:。:。:，然后根據三邊測量法計算得出節(jié)點的位置坐標。圖23 DVHop定位算法舉例DVHop算法對節(jié)點硬件要求低，實現簡單，其不足是以節(jié)點間最小跳段距離替代節(jié)點間的直線距離，由于通常節(jié)點間的最小跳段距離與其間的直線距離是有差別的，因而最終會有一定的定位誤差。 Euclidean定位算法Euclidean算法[40]是一種計算與信標節(jié)點相隔兩跳的未知節(jié)點位置坐標的方法。該算法核心思想如圖24所示。圖24 Euclidean定位算法示意圖假設，為未知節(jié)點，為信標節(jié)點。通過RSSI技術直接測得節(jié)點間距，和。節(jié)點與，相鄰。在四邊形中，己知所有邊的長度與對角線的長度，則由三角形中的余弦定理即可通過式(21)、式(22)、式(23)計算出的長度(未知節(jié)點與信標節(jié)點間的距離)。 (21) (22) (23)使用這種方法，當未知節(jié)點獲得與三個或三個以上信標節(jié)點距離后就可計算出自身的位置坐標。Euclidean定位算法的優(yōu)點是與信標節(jié)點相隔兩跳的未知節(jié)點均可實現定位，但其條件比較苛刻，從而該算法的可用性會受到一定的約束，此外該算法受環(huán)境影響大，這樣會導致其定位誤差增加。 HopEuclidean定位算法HopEuclidean算法[41]是在Euclidean定位算法基礎上，融入距離矢量路由和迭代循環(huán)的思想，設計出的一種定位算法。該算法針對Euclidean定位算法只有未知節(jié)點擁有三個以上鄰居節(jié)點且這些鄰居節(jié)點都必須彼此相鄰才能統計出到信標節(jié)點的跳數的問題，通過融入距離矢量路由的思想，并且有選擇性地把已定位節(jié)點逐漸升級為信標節(jié)點，以此來提高算法的定位精度的同時也擴展了算法的可用性。雖然HopEuclidean算法能夠獲得較準確的節(jié)點間距，但是由于采用的是最大似然估計法進行估算節(jié)點的位置，而這種估計方法本身存在一定誤差，這樣就會擴大節(jié)點的定位誤差。 MDSMAP算法MDSMAP算法[42]是一種不論傳感器節(jié)點是否具有測距能力都可以實現定位的集中式定位算法，而且依據實際情況既可以實現相對定位，也能夠實現絕對定位。該算法采用了一種源自心理測量學和精神物理學的數據分析技術——多維標度技術MDS(Multidimensional scaling)，這種技術通常用于探索性的數據分析或信息可視化。該算法可分為3個步驟。第一，若傳感器節(jié)點具備測距能力，則直接通過測距技術所得的傳感器節(jié)點間的距離值。否則使用最短路徑算法，生成多維標度技術MDS所需節(jié)點間距矩陣；第二，對節(jié)點間距矩陣利用多維標度技術計算出各個節(jié)點在整個網絡中位置的相對坐標；第三，如果擁有足夠數量的信標節(jié)點，則可將相對坐標系統經過線性變換轉換成相應的絕對坐標系統。MDSMAP算法是一種集中式定位算法，通常會增加傳感器節(jié)點的計算量與通信量，從而會消耗大量的能量，而傳感器節(jié)點的能量有限，這樣就會造成節(jié)點在中途能量耗盡無法實現最終的定位。此外，當傳感器網絡中的節(jié)點密度減小或網絡拓撲結構不規(guī)則時，其節(jié)點的定位誤差會增大，甚至會有大量的傳感器節(jié)點無法實現定位。 本章小結本章主要是對無線傳感器網絡及其定位技術作了介紹。首先，主要從無線傳感器網絡體系結構和傳感器節(jié)點結構兩方面闡述了無線傳感器網絡的體系結構；第二，介紹了無線傳感器網絡的特點；第三，闡述了無線傳感器網絡定位技術的基礎知識，其中包括節(jié)點定位的基本概念、術語及定位算法的分類；最后，重點介紹了現有的幾種與本文研究相關的經典定位算法：DVHop算法、Euclidean定位算法、MDSMAP算法，同時對這三種算法的優(yōu)缺點作了分析。第3章 基于MDSMAP(D)定位算法的改進第3章 基于MDSMAP(D)定位算法的改進 引言隨著信息化時代的到來，目前WSN商業(yè)化應用也不斷興起，同時涌現出大量的科研工作者熱衷于對無線傳感器網絡節(jié)點定位技術的研究，于是現已有許多種定位算法，但是各種不同的定位算法適用的環(huán)境都不盡相同。比如，DVHop算法是適合于硬件配置較低、對節(jié)點定位精度要求不太高的應用；而Euclidean定位算法是適合于節(jié)點具有測距能力的、且環(huán)境中的噪聲相對較小的應用場合下使用；MDSMAP算法是適合于網絡連通度相對比較大、且傳感器節(jié)點的能量充足、計算能力較強的小規(guī)模拓撲規(guī)則的無線傳感器網絡。所以定位算法的設計都需要根據實際應用的環(huán)境及硬件條件等要求來進行。通過研究分析發(fā)現，MDSMAP算法是使用節(jié)點間的最短路徑距離替換其實際幾何距離，但通常最短路徑距離比實際幾何距離小，這樣就會擴大節(jié)點間的幾何距離，最終會導致較大定位誤差。此外，MDSMAP算法是采用MDS技術根據距離矩陣進行求解對應節(jié)點的位置坐標，但通常距離矩陣都比較龐大，則會導致其計算復雜度較大，且當節(jié)點增加或移動時，需要重新求解，這將會嚴重阻礙網絡的擴展。為了實現大規(guī)模無線傳感器網絡中節(jié)點的定位，本文采用分簇算法將大規(guī)模網絡劃分為多個區(qū)域同時在各個區(qū)域中選出各自的簇頭節(jié)點，然后采用HopEuclidean算法計算出每個區(qū)域內節(jié)點之間的距離，再讓各個簇頭節(jié)點采用多維標度技術通過簇內節(jié)點之間的距離矩陣計算出各個區(qū)域內傳感器節(jié)點的局部相對坐標，最后通過融合算法將其融合為全局相對坐標并根據信標節(jié)點信息通過線性轉換將器相對坐標轉變?yōu)榻^對坐標。 多維標度技術和MDSMAP定位算法 多維標度技術基本原理多維標度技術MDS(Multidimensional scaling)是一種將實體間的相似信息轉換成空間幾何信息的數據分析技術，常用于探索性數據分析或信息可視化，最初應用于心理測驗學的數據分析，現在已作為一種通用的數據分析技術廣泛應用于各個領域。本章算法的基礎是多維標度定位算法，下面具體介紹一下多維標度定位算法。假設研究對象和之間的相異性用表示，各研究對象間的相異性構成相異性矩陣。構造多維空間上點的坐標矩陣用表示，其中為坐標點的個數，為坐標點的維數，實體對象和的坐標分別為，多維空間上和之間的歐式距離用表示。多維標度技術就是利用各實體間的相異性來構造多維空間上點的相對坐標圖，使與盡可能地接近，在多維標度中其接近程度用脅強系數(STRESS)來衡量。定義脅強系數為： (31)其具體實現分為四步：(1) 構造相異性矩陣；(2) 將矩陣中的各元素乘方，得到；(3) 將雙重中心化,即的兩邊同時乘以中心矩陣,的計算公式見(32)。 (32)式中為階的單位矩陣，為階的全1矩陣，雙重中心化后的矩陣見式(33)。 (33)(4) 將進行奇異值分解，求最大的個正特征值和對應的個特征向量，個向量組成維對角矩陣，個特征向量組成維矩陣,所有節(jié)點的相對坐標為 (34) MDSMAP定位算法無線傳感器網絡中節(jié)點定位的實質是未知節(jié)點通過與少量位置已知的信標節(jié)點之間的連通性信息來確定自身在相應空間中的位置坐標,而MDS技術就是根據各個對象(或實體)間的相異(似)信息構建多維空間上點的相對坐標圖。于是，在研究無線傳感器網絡的定位時引入了MDS技術。傳統的MDSMAP算法，由美國密蘇里哥倫比亞大學Yi等人提出。該算法正是利用MDS技術來生成相對坐標系統的，在較小規(guī)模規(guī)則且分布均勻的網絡中，可以獲得較高的定位精度，被廣泛應用于無線傳感器網絡的相關項目中。MDSMAP算法分為三步：(1) 生成距離矩陣首先從全局角度生成網絡拓撲連通圖，如果節(jié)點具備測距能力，則通過測距技術獲得的節(jié)點間的距離值。否則根據最短路徑算法，求出最短路徑距離，生成節(jié)點之間的距離矩陣。(2) 估算相對位置對上一步生成的節(jié)點之間的距離矩陣采用MDS技術，估算出整個網絡中所有未知節(jié)點在多維空間上的相對位置的坐標。(3) 將相對坐標轉換為絕對坐標當網絡中有足夠的信標節(jié)點時，前一步執(zhí)行完后，可以得到每個信標節(jié)點通過MDS技術估算出的相對坐標，根據估算出的信標節(jié)點坐標與原本已知的坐標關系，能夠找到一個線性變換關系式，然后利用該線性變換關系式將相對坐標系統轉化為絕對坐標系統。 基于HopEuclidean的MDSMAP(D)定位算法 改進算法的相關研究工作如果所有節(jié)點之間的歐幾里德距離沒有誤差，則采用經典的MDS定位算法求出的節(jié)點位置坐標是精確的。但是通常節(jié)點間通信會受到環(huán)境的影響，因而通過信號傳播測出的節(jié)點間的距離值都是有誤差的，最終會導致定位誤差的出現。在實際的WSN應用中，求解全網絡節(jié)點間的距離只能依據相鄰節(jié)點之間的距離信息進行估計。而經典的MDSMAP算法就是采用跳數與通信距離乘積來取代節(jié)點間的實際幾何距離，從而擴大了節(jié)點的定位誤差。MDSMAP算法是采用MDS技術根據距離矩陣進行求解對應節(jié)點的位置坐標，但通常距離矩陣都比較龐大，則會導致其計算復雜度較大，且當節(jié)點增加或移動時，需要重新求解，這將會嚴重阻礙網絡的擴展。針對經典MDSMAP定位算法的上述問題，本文提出了一種基于HopEuclidean的MDSMAP(D)定位算法。在采用基于HopEuclidean的MDSMAP(D)算法定位之前，需做以下假設：(1) 為了計算方便，設定部署傳感器節(jié)點的區(qū)域是二維的，且部署后位置靜止；(2) 傳感器節(jié)點的ID是唯一的；(3) 節(jié)點具有測距能力；(4) 采用的是