【導(dǎo)讀】感器技術(shù)、嵌入式計算、低功耗電子技術(shù)和無線通信技術(shù)。通管理、反恐抗災(zāi)等領(lǐng)域具有廣闊的應(yīng)用前景。傳感器網(wǎng)絡(luò)研究中的共性支撐技術(shù)之一。提下還要求定位算法必須是易實現(xiàn)、低復(fù)雜性、低能耗的。線傳感器網(wǎng)絡(luò)中的節(jié)點定位技術(shù)展開深入探討和研究。論述了無線傳感器網(wǎng)絡(luò)的特點。在查閱大量相關(guān)文獻(xiàn)的?；A(chǔ)上，全面地探討了節(jié)點定位問題及其在國內(nèi)外的研究現(xiàn)狀；描述了無線傳感器網(wǎng)。定位效果、實現(xiàn)成本等方面考慮，總結(jié)了節(jié)點定位算法的分類方法；致的研究和分析，以此為后續(xù)的研究工作提供良好的基礎(chǔ)和借鑒；計出一種新的定位算法，稱為ＥＬＭ定位算法。跳距誤差對節(jié)點最終位置的影響。在ＥＬＭ定位算法中加入了一種驗證方法以提高節(jié)點定位的精度。給出了無線傳感器網(wǎng)絡(luò)節(jié)點定位系統(tǒng)總體設(shè)。ａｎｄｓｙｓｔｅｍａｒｅｄｅｓｃｒｉｂｅｄｃｏｍｐｒｅｈｅｎｓｉｖｅｌｙ．Ａｎｄｔｈｅｔａｘｏｎｏｍｙ

　　

【正文】 要：喜：要：委：墨：墨］ ｃｔ一４， 三邊 測量法的缺點是：若在測距過程中存在誤差，上述三個圓就無法交于一 點，用存在誤差的西、如、吃去解上述方程時便無法得到正確解。因此，在實 際計算坐標(biāo)時，一般不采用上述解方程的方法，而采用極大似然估計法或其他數(shù) 值解法。 １７ 浙江工業(yè)大學(xué)碩士學(xué)位論文 １．５．３．３極大似然估計法 如果未知節(jié)點可以找到三個以上信標(biāo)節(jié)點作為參考節(jié)點，則可利用冗余的信 標(biāo)節(jié)點信息使用極大似然估計法（ＭａｘｉｍｕｍＬｉｋｅｌｉｈｏｏｄＥｓｔｉｍａｔｉｏｎ，ＭＬＥ）來提高 定位精度。極大似然估計 法的原理如圖１ — ５所示。 圖１－５極大似然估計祛定位示恿圖 已知號、Ｅ、己、 ? 、弓等ｎ個信標(biāo)節(jié)點的坐標(biāo)分別為 “ ，Ｍ）、（而，Ｙ２）、 （而，乃）、 ? 、（而，兒），它們到未知節(jié)點Ｄ的距離分別為４、吐、毛、 ? 、以， 假設(shè)未知節(jié)點Ｄ的坐標(biāo)為（ｘ，ｙ），那么存在下列公式： Ｉ（ ‘ 一ｚ）２＋（乃一ｙ）２＝砰 ｛ｉ（１ ? ５） 【 “ 一ｚ）２＋ ∽ 一ｙ）２＝刃 求解，從第一個方程開始分別減去最后一個方程，得： ｆ＃一Ｋ２ — ２（＾一矗）工＋拜一Ｚ－２（ｙ．－ｙ．）ｙ－－ｄ，２一《 ｛ｉ（１－６） Ｉ靠。一Ｚ一２（鉑－－Ｘｎ）Ｘ ＋丘。一Ｚ－２（ｙ．一。－ｙ，）ｙ－－砟，一砰 方程組（１－６）用線性方程組表示為：ＡＸ＝ｂ，其中 ｆｂ一矗）（Ｙｌ－炸）１ 肚ｌ㈡Ｉ（１－７） ｌ（ ‘ ．１－毛）（咋一一只）Ｊ ｂ＝ ＃一《十開一Ｚ＋露一彳 ｉ 靠。一《＋ｙ：。一Ｚ＋露一Ｚ：。 ｘ＝圈 （１．８） （１－９） １８ 浙江工業(yè)大學(xué)碩士學(xué)位論文 使用標(biāo)準(zhǔn)的最小均方差估計法可以得到節(jié)點Ｄ的坐標(biāo)為： 皇＝（４７彳）～Ａｂ（１－１０） 此方法的缺點在于需要進(jìn)行較多的浮點運算，其計算開銷帶來的能量消耗仍 不容 忽視。 １．５．４節(jié)點定位算法性能評價標(biāo)準(zhǔn) 國外的大學(xué)和研究機(jī)構(gòu)提出了許多專用于無線傳感器網(wǎng)絡(luò)的定位系統(tǒng)。無線 傳感器網(wǎng)絡(luò)的節(jié)點定位系統(tǒng)和算法的性能直接影響其可用性和應(yīng)用范圍，需要滿 足自組織性、健壯性、能量有效性等需求，下面定性地討論幾個常用的評價標(biāo)準(zhǔn)。 １、定位精度。定位技術(shù)首要的評價指標(biāo)就是定位精度，一般用誤差值與節(jié) 點通信半徑的比例表示。例如，定位精度為２０％表示定位誤差相當(dāng)于節(jié)點通信半 徑的２０％。目前最常用的指標(biāo)是定位解的均方誤差（ＭｓＥ）、均方根誤差（ＲＭＳＥ）、 克拉美一羅下界（ＣＲＬＢ）、 圓誤差概率（ＣＥＰ）、幾何精度因子（ＧＤＯＰ）等。然而， 由于傳感器節(jié)點大量部署的特性，對于許多應(yīng)用，定位的精度反而并不顯得十分 重要，當(dāng)定位誤差小于傳感器節(jié)點無線通信半徑的４０％時，定位誤差對路由性能 和目標(biāo)追蹤精確度的影響不會很大Ｉ刪。也有部分定位系統(tǒng)［３４，６１１將二維網(wǎng)絡(luò)部署區(qū) 域劃分為網(wǎng)格，其定位結(jié)果的精度也就是網(wǎng)格的大小。 ２、信標(biāo)節(jié)點密度。信標(biāo)節(jié)點的定位通常依賴人工部署或ＧＰＳ實現(xiàn)，人工部 署信標(biāo)節(jié)點的方式不僅受網(wǎng)絡(luò)部署環(huán)境的限制，還嚴(yán)重制約了網(wǎng)絡(luò)和應(yīng)用的可擴(kuò) 展性；而使用ＧＰＳ定位，信標(biāo)節(jié)點 的費用會比普通節(jié)點高兩個數(shù)量級【６２】，這意 味著假如信標(biāo)節(jié)點比例增加１０％，整個網(wǎng)絡(luò)的價格將增加１０倍。因此，信標(biāo)節(jié) 點密度也是評價定位系統(tǒng)和算法性能的重要指標(biāo)之一。 ３、功耗。功耗問題始終是無線傳感器網(wǎng)絡(luò)設(shè)計和實現(xiàn)首要的考慮因素。由 于傳感器節(jié)點電池能量有限，因此在保證定位精度的前提下，必須盡可能減小定 位過程中的能量消耗。與功耗密切相關(guān)的因素主要有：計算量、通信開銷、存儲 開銷、時間復(fù)雜性等。 ４、節(jié)點密度。在無線傳感器網(wǎng)絡(luò)中，節(jié)點密度增大不僅意味著網(wǎng)絡(luò)部署費 用的增加，而且會因為節(jié)點間的通信沖突問題 帶來有限帶寬的阻塞。節(jié)點密度通 常以網(wǎng)絡(luò)的平均連通度來表示。許多定位算法的精度受節(jié)點密度的影響，如 ＤＶ．Ｈｏｐ［４８＂４９］，蛔ｈｏｕｓ州等算法僅可在節(jié)點密集部署的情況下合理估算節(jié)點 位置。 ５、定位覆蓋率（ｃｏｖｅｒａｇｅ）。覆蓋率定義為可實現(xiàn)定位的未知節(jié)點與未知節(jié)點 總數(shù)的比例。盡管密集部署是無線傳感器網(wǎng)絡(luò)的特點之一。但總會有一些不可達(dá) 或連通度極低（小于３）的未知節(jié)點存在，除這些節(jié)點，實現(xiàn)盡可能多的未知節(jié) Ｊ９ 浙江工業(yè)大學(xué)碩士學(xué)位論文 點的精確定位也是自身 定位算法和系統(tǒng)的追求目標(biāo)之一。 ６、代價：定位系統(tǒng)或算法的代價可從幾個不同方面來評價。時間代價包括 一個系統(tǒng)的安裝時間、配置時間、定位所需時間。空間代價包括一個定位系統(tǒng)或 算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點的數(shù)量、硬件尺寸等。資金代價則包括實現(xiàn)一種 定位系統(tǒng)或算法的基礎(chǔ)設(shè)施、節(jié)點設(shè)備的總費用。 ７、適用環(huán)境與規(guī)模。不同的定位系統(tǒng)或算法的適用環(huán)境可以是在園區(qū)內(nèi)、 建筑物內(nèi)、一層建筑物或僅僅是一個房間內(nèi)實現(xiàn)定位。另外，在給定的基礎(chǔ)設(shè)施 或時間內(nèi)，一種技術(shù)可以定位多少目標(biāo)也是一個重要的評價指標(biāo)。例如，ＲＡＤＡＲ 系統(tǒng)唧 僅能在建筑物的一層內(nèi)實現(xiàn)目標(biāo)定位。 ８、容錯性和自適應(yīng)性。通常，定位系統(tǒng)和算法都需要比較理想的無線通信 環(huán)境和可靠的網(wǎng)絡(luò)節(jié)點設(shè)備。但在真實應(yīng)用場合下，測距和通信常會受到外界環(huán) 境的干擾，存在嚴(yán)重的多徑傳播、衰減、非視距、通信盲點等問題；傳感器節(jié)點 由于周圍環(huán)境或自身原因（如電池耗盡、物理損傷）而出現(xiàn)失效的問題；外界影 響和節(jié)點硬件精度限制造成節(jié)點間點到點的距離或角度測量誤差增大的問題。由 于環(huán)境、能耗和其他原因，物理的維護(hù)或替換傳感器節(jié)點或使用其他高精度的測 量手段常常是十分困難或不可行的。因此，定位系統(tǒng)和 算法的軟、硬件必須具有 很強的容錯性和自適應(yīng)性，能夠通過自動調(diào)整或重構(gòu)糾正錯誤、適應(yīng)環(huán)境、減小 各種誤差的影響，不會因為個另１Ｊ節(jié)點的失效而導(dǎo)致其他節(jié)點出現(xiàn)無法定位或誤差 很大的情況。 ９、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)適應(yīng)性。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)會對定位的精度產(chǎn)生一定的影響， 某些定位機(jī)制對其有一定的要求，如節(jié)點需要以高密度部署，網(wǎng)絡(luò)必須是各向同 性，信標(biāo)節(jié)點需要部署在網(wǎng)絡(luò)周圍等。 上述９個性能指標(biāo)不僅是評價無線傳感器網(wǎng)絡(luò)節(jié)點定位算法的標(biāo)準(zhǔn)，也是其 設(shè)計和實現(xiàn)的優(yōu)化目標(biāo)。為了達(dá)到這些目標(biāo)的優(yōu)化，有大量的研究工作需要完成。 同時這些 性能指標(biāo)是相互關(guān)聯(lián)的，必須根據(jù)應(yīng)用的具體需求做出權(quán)衡，以選擇和 設(shè)計合適的定位技術(shù)。 １．５．５節(jié)點定位算法的分類方法 盡管無線傳感器網(wǎng)絡(luò)自身定位系統(tǒng)和算法的分類還沒有一個統(tǒng)一的標(biāo)準(zhǔn)，一 個分類標(biāo)準(zhǔn)也不可能適用于所有定位系統(tǒng)和算法，但下面這些分類方法能從側(cè)面 反應(yīng)出不同定位技術(shù)的特點。在無線傳感器網(wǎng)絡(luò)中，從測量技術(shù)、定位形式、定 位效果、實現(xiàn)成本等方面考慮，節(jié)點定位算法可以用以下幾種方法進(jìn)行分類。 （一）基于測距技術(shù)的定位和無需測距技術(shù)的定位 根據(jù)定位過程中是否測量實際節(jié)點間的距離，把定位算法分為：基于測距 技 術(shù)限ａｎｇｅ．Ｂ船ｅｄ）的定位和無需測距技術(shù)＠觚ｇｃ－ＦＤ ∞ ）的定位岬Ｊ． 浙江工業(yè)大學(xué)碩士學(xué)位論文 Ｒａｎｇｅ．Ｂａｓｅｄ定位算法利用一定的測距技術(shù)得到節(jié)點間的距離或角度等信 息，再使用三邊測量法、三角測量法或極大似然估計法計算出未知節(jié)點的位置。 Ｒａｎｇｇ．Ｂａｓｅｄ定位常用的測距技術(shù)有接收信號強度０ ≈ ＳＳＬ）技術(shù)、信號傳輸時間 （ＴＯＡ）技術(shù)、信號到達(dá)時間差（ＴＤＯＡ）技術(shù)和信號到達(dá)角度（ＡＯＡ）技術(shù)。ＲＳＳＩ技 術(shù)雖然符合低功率、低成本的要求，但有可能產(chǎn) 生土５０％的測距誤差；ＴＯＡ技術(shù) 需要節(jié)點問精確的時間同步；ＴＤＯＡ技術(shù)受限于超聲波傳播距離有限和ＭＤＳ 問題對超聲波信號傳播的影響；ＡＯＡ也受外界環(huán)境影響，而且需要額外硬件， 在硬件尺寸和功耗上可能無法用于傳感器節(jié)點。除上述測距技術(shù)的局限性以外， Ｒａｎｇｅ — Ｂａｓｅｄ定位機(jī)制使用各種算法來減小測距誤差對定位的影響，包括多次測 量州，循環(huán)定位求精［６５１，這些都要產(chǎn)生大量計算和通信開銷。所以，Ｒ皿ａｇｅ．Ｂａｓｅｄ 定位機(jī)制雖然在定位精度上有可取之處，但并不適用于要求低功耗、低成本的無 線傳感器網(wǎng)絡(luò)應(yīng)用領(lǐng) 域。 Ｒａｎｇｅ．Ｆｒｅｅ定位技術(shù)則無需距離和角度信息，僅根據(jù)網(wǎng)絡(luò)連通性等信息即可 實現(xiàn)。無需測距技術(shù)一般采用的是節(jié)點平均每跳距離和跳數(shù)的乘積來計算節(jié)點間 的距離，然后再利用三邊定位技術(shù)來進(jìn)行節(jié)點定位。信標(biāo)節(jié)點ｊ的平均每跳距離 的計算公式如下： ｃＪ＝ 其中．，為其他信標(biāo)節(jié)點，％為節(jié)點ｆ和節(jié)點，之間的跳數(shù)。 由于功耗和成本等因素，再加上粗精度定位能夠滿足大多數(shù)的應(yīng)用，所以 Ｒａｎｇｅ．Ｆｒｅｅ定位技術(shù)是最有潛力的定位技術(shù)之一。ＤＶ－Ｈｏｐ算法Ｄ８－４９］、凸規(guī)劃算 法【ｓ，５１】和ＭＤＳ．ＭＡＰ算法【５３ｌ 等都是典型的Ｒａ／ｌｇｃ．Ｆｒｅｅ定位算法。距離無關(guān)定位算 法從各指標(biāo)來看，都很適合無線傳感器網(wǎng)絡(luò)低成本、低功耗的要求。 （二）絕對定位與相對定位 絕對定位的定位結(jié)果是一個標(biāo)準(zhǔn)的坐標(biāo)位置，如經(jīng)緯度。而相對定位通常是 以網(wǎng)絡(luò)中部分節(jié)點為參考，建立整個網(wǎng)絡(luò)的相對坐標(biāo)系統(tǒng)１１４１。絕對定位可為網(wǎng) 絡(luò)提供唯一的命名空間，受節(jié)點移動性影響較小，有更廣泛的應(yīng)用領(lǐng)域。但研究 發(fā)現(xiàn)【的Ｊ，在相對定位的基礎(chǔ)上也能夠?qū)崿F(xiàn)部分路由協(xié)議，尤其是基于地理位置 的路由，而且相對定位不需要信標(biāo)節(jié)點。大多數(shù)定位系統(tǒng)和算法都可以實現(xiàn)絕對 定 位服務(wù)，典型的相對定位算法和系統(tǒng)有ＳＰＡ（Ｓｅｌｆ－ＰｏｓｉｔｉｏｎｉｎｇＡｌｇｏｒｉｔｈｍ）定位算 法ＤＴｌ、ＬＰＳ（ＬｏｃａｌＰｏｓｉｔｉｏｎｉｎｇＳｙｓｔ如）定位算法Ｍ和ＳｐｏｔＯＮ定位算法１５明等，而 ＭＤＳ－ＭＡＰ定位算法【５３】可以根據(jù)網(wǎng)絡(luò)配置的不同分別實現(xiàn)兩種定位。 （三）精粒度定位方法與粗粒度定位方法 依據(jù)定位技術(shù)所需信息的粒度可將定位算法和系統(tǒng)分為精粒度定位方法與 粗粒度定位方法【４５１兩類。 ２ｌ 浙江工業(yè)大學(xué)碩士學(xué)位論文 精粒度定位方法是指基于 時間或是接收信號強弱的一些方法。一般而言，精 粒度的定位技術(shù)大部分是Ｒａｎｇｅ．Ｂａｓｅｄ，根據(jù)依賴信標(biāo)節(jié)點所推斷出的距離或是 相關(guān)角度，精粒度定位方法又可以進(jìn)一步細(xì)分為基于距離和基于方向兩種。 粗粒度定位方法就是指根據(jù)一些粗粒度信息如通過與信標(biāo)節(jié)點的接近程度 等來推斷節(jié)點位置的方法。粗粒度定位技術(shù)一般是Ｒａｎｇｅ．Ｆｒｅｅ定位技術(shù)，其原 理是利用某種物理現(xiàn)象來感應(yīng)是否有目標(biāo)接近一個已知的位置。 （四）基于信標(biāo)節(jié)點的定位算法和無信標(biāo)節(jié)點的定位算法 根據(jù)定位過程中是否使用信標(biāo)節(jié)點，可以把定位算法分為：基于信標(biāo) 節(jié)點的 （ｂｅａｃｏｎ－ｂａｓｅｄ）定位算法和無信標(biāo)節(jié)點的（ｂｅａｒ．ｏｎ．ｆＴｅｅ）定位算法。前者在定位過程 中，以信標(biāo)節(jié)點作為定位中的參考節(jié)點，各節(jié)點定位后產(chǎn)生整體絕對坐標(biāo)系統(tǒng)； 后者只關(guān)心節(jié)點間的相對位置，在定位過程中無需信標(biāo)節(jié)點，各節(jié)點先以自身作 為信標(biāo)點，將臨近的節(jié)點納入自己定義的坐標(biāo)系中，相鄰的坐標(biāo)系統(tǒng)依次轉(zhuǎn)換合 并，最后產(chǎn)生整體相對坐標(biāo)系統(tǒng)。 （五）集中式算法與分布式算法 集中式計算ｐｌ】是指把所需信息傳送到某個中心節(jié)點（例如，一臺服務(wù)器），并 在中心節(jié)點處進(jìn)行節(jié)點定位計算的方式；分布式計算是 指依賴節(jié)點間的信息交換 和協(xié)調(diào)，由節(jié)點自行計算的定位方式。 集中式計算的優(yōu)點在于從全局角度統(tǒng)籌規(guī)劃，計算量和存儲量幾乎沒有限 制，可以獲得相對精確的位置估算。它的缺點包括與中心節(jié)點位置較近的節(jié)點會 因為通信開銷大而過早地消耗完電能，導(dǎo)致整個網(wǎng)絡(luò)與中心節(jié)點信息交流的中 斷，無法實時定位等㈣。集中式定位算法包括凸規(guī)劃（ｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎ）定位 算法【＆５ ” ，ＭＤＳ．ＭＡＰ定位算法１５３１等。Ｎ．ｈｏｐｍｕｌｔｉｌａｔｅｒａｔｉｏｎｐｒｉｍｉｔｉｖｅ定位算法【醴】 可以根據(jù)應(yīng)用需求采用兩種不同的 計算模式。 分布式定位算法將計算工作分布到各個節(jié)點處，節(jié)點的位置估計在本地完 成。這種算法的優(yōu)點是：通過使用信標(biāo)節(jié)點，可以實現(xiàn)分布式計算，便于系統(tǒng)擴(kuò) 展：如果系統(tǒng)允許采用集中計算方式，使用信標(biāo)節(jié)點可以為定位算法提供更多的 信息，從而提高定位準(zhǔn)確度。分布式定位算法的缺點是需要大量的信標(biāo)節(jié)點支持。 定位技術(shù)的研究與發(fā)展在很大程度上決定了無線傳感器網(wǎng)絡(luò)應(yīng)用的步伐，盡 管目前提出了很多研究方法，但一般都是在特定條件下來進(jìn)行相關(guān)定位，真正實 現(xiàn)定位技術(shù)的發(fā)展還要進(jìn)一步的深入研究。 １．６本文研究內(nèi)容與結(jié)構(gòu)安排 在無線 傳感器網(wǎng)絡(luò)中，定位問題是一個亟待解決的問題，因為很多無線傳感 器網(wǎng)絡(luò)的具體應(yīng)用都要涉及到各節(jié)點的位置問題，作為無線傳感器網(wǎng)絡(luò)的支撐技 浙江工業(yè)大學(xué)碩士學(xué)位論文 術(shù)之一，定位技術(shù)向國內(nèi)外學(xué)者提出了許多挑戰(zhàn)，目前成為研究和討論的熱點。 本文對己有的無線傳感器網(wǎng)絡(luò)無需測距技術(shù)節(jié)點定位算法進(jìn)行了深入的研 究，跟蹤了國內(nèi)外在該領(lǐng)域的研究進(jìn)展，并在此基礎(chǔ)上提出了一種新的無需測距 節(jié)點定位算法，最后設(shè)計了無線傳感器網(wǎng)絡(luò)定位實驗節(jié)點并在實驗節(jié)點上實現(xiàn)定 位算法。論文的研究內(nèi)容安排如 下： 第一章闡述了本課題的研究背景及意義，介紹了無線傳感器網(wǎng)絡(luò)的特點和體 系結(jié)構(gòu)，分析了無線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)，并總結(jié)了無線傳感器網(wǎng)絡(luò)的應(yīng)用 領(lǐng)域，重點綜述了無線傳感器網(wǎng)絡(luò)節(jié)點定位問題及其在國內(nèi)外的研究現(xiàn)狀。進(jìn)而 論述了無線傳感器網(wǎng)絡(luò)節(jié)