【正文】 離。 ＡＨＬｏｓ系統(tǒng)是一個迭代的定位算法。這個過程一直重復到所有節(jié)點都計算出自身的位置。孫學 斌唧】等人提出了一種無線傳 感器網(wǎng)中的目標定位算法，用以獲取在無線傳感器網(wǎng)絡監(jiān)視下的地理區(qū)域中移動 目標的位置。王永才［３９１等人介紹了在無線傳感器網(wǎng)絡系統(tǒng)中， 應用ＴＤＯＡ測距技術和基于幾何關系的節(jié)點自身定位算法，并在Ｍｉｃａ２系統(tǒng)上 實現(xiàn)了該算法。楊強１４ｌｌ等人提出一種 適用于大規(guī)模無線傳感器網(wǎng)絡的 通用三階段分布式定位結構體系。 浙江工業(yè)大學碩士學位論文 從對上述ＷＳＮ定位研究成果的比較發(fā)現(xiàn)，沒有一種定位方案能在有效減少 通信開銷、降低功耗、節(jié)省網(wǎng)絡帶寬的同時獲得較高的定位精度。以使得無線傳感器 網(wǎng)絡能夠真正在實際生活中得到廣泛的應用。隨機布撒的傳感器節(jié)點無法事先知道自身位置，因此傳感器節(jié)點必須能夠在 布置之后實時地進行定位。只有在傳感器節(jié)點自身正確定位后，才能確 定傳感器節(jié)點監(jiān)測到的事件發(fā)生的具體位置，這需要監(jiān)測到該事件的多個傳感器 節(jié)點之間相互協(xié)作，并利用它們自身的位置信息，使用特定的定位機制，確定事 件發(fā)生的位置。 １．５．１無線傳感器網(wǎng)絡節(jié)點定位專業(yè)術語 在無線傳感器網(wǎng)絡節(jié)點定位技術中，把需要定位的節(jié)點稱為未知節(jié)點 （ｕｎｋｎｏｗｎｎｏｄｅ）；而通過人工部署或ＧＰＳ定位系統(tǒng)獲知自身位置，并協(xié)助未知節(jié) 點定位的節(jié)點稱為錨節(jié)點（ａｎｃｈ００或參考節(jié)點（ｒｅｆｅｒｅｎｃｅｐｏｉｎｔ），也稱為信標節(jié)點 （ｂｅａｃｏｎ）。信標節(jié)點是未知節(jié)點定位的參考點。 鄰居節(jié)點（ｎｅｉｇｈｂｏｒｎｏｄｅｓ）：在傳感器節(jié)點通信半徑內(nèi)，可直接相互通信的節(jié) 點，稱為該節(jié)點的鄰居節(jié)點。 跳段距離（ｈｏｐｄｉｍｎｃｅ）：兩個節(jié)點之間間隔的各跳段距離之和，稱為兩節(jié)點 間的跳段距離。 到達時間（ＴｕｎｅＯｆＡｒｒｉｖａｌ，ＴＯ Ａ）：信號從一個節(jié)點傳播到另一個節(jié)點所需要 的時間，稱為信號的到達時間。 接收信號強度指示（ＲｅｃｅｉｖｅｄＳｉｇｎａｌＳｔｒｅｎｇｔｈＩｎｄｉｃａｔｏｒ，ＲＳＳＩ）；節(jié)點接收到無 線信號的強度大小，稱為接收信號的強度指示。 網(wǎng)絡的平均連通度：平均鄰居節(jié)點的數(shù)量。 非視線關系（Ｎｏｎ－Ｌｉｎｅ－０ｆ－Ｓｉｇｈｔ，ＮＬＯＳ）：兩個節(jié)點之間有障礙物，不能夠直 接通信。考慮到傳感器節(jié)點的特點，測距方法不 應增 加額外的硬件，同時又需要保證一定的精度。信號衰減模型用公式表示如下： 即）叫磊）－１０．ｎ－ｌｏｇ時｛鬻囂ｍ －， 其中，Ｐ（ａ）、Ｐ（磊）分別表示在距離基站ｄ、噸處的信號強度，ｅ（ｄ）是接 收節(jié)點實際測得的信號強度ＲＳＳＩ，Ｐ（ｄｏ）一般可以距天線蟊米處的路徑衰減來 代替，其典型值為Ｐ（１１＝３０ｄＢ；力稱同層衰減指數(shù)，表示路徑長度和路徑損耗 之間的比例因子，依賴于建筑物的結構和使用的材料，典型值為：辦公樓刀＝３．２５， 一般建筑珂＝２．７６，商場 ” ＝２．１８；ｎＷ表示節(jié)點和基站間墻壁個數(shù)，Ｃ表示信號 穿過墻壁的閾值；ＷＡＦ稱路徑損耗附加值，表示信號穿過墻壁或障礙物的衰減 因子，依賴于建筑的結構和使用的材料，典型 值為：玻璃８ｄＢ，隔墻１０～１５ｄＢ， 預制板２０。 由于傳感器節(jié)點本身具備無線通信能力，通信控制芯片通常會提供測量 ＲＳＳＩ的方法，在信標節(jié)點廣播自身坐標的同時即可完成ＲＳＳＩ的測量，故而是一 浙江工業(yè)大學碩士學位論文 種低功率、低代價的測距技術。因此，基于ＲＳＳＩ的測距應視為一種租糙的測距技術，有可能產(chǎn)生 177。 １．５．２．２ＴＯＡ（ＴｉｍｅｏｆＡｒｄｖａｌ） 該技術是采用信號到達時間【１３］來測量距離的，是一種基于電波傳輸時間的 定位技術。ＴＯＡ測距的基本思想是測量移動臺發(fā)射信 號的到達時間，并且在發(fā)射信號中要包含發(fā)射時間標記以便接收基站確定發(fā)射信 號所傳播的距離 ，該方法要求移動臺和基站的時間精確同步。 ＴＯＡ定位法是一種基于網(wǎng)絡的定位技術。該方法的缺點在于每個基站都必須增加一個位置測量單元 并且要做到時間同步，移動臺也需要與基站同步，整個網(wǎng)絡的初期投資將會很高； 發(fā)射信號中加上發(fā)射時間標記，會增加上 行鏈路的數(shù)據(jù)量，當業(yè)務量增大時網(wǎng)絡 的負擔會加重；即使在位置測量單元時鐘精度很高的情況下，到達時間的測量仍 然會受到多徑效應的影響口１；如果移動臺無法和三個以上的位置測量單元或者 基站取得聯(lián)系，定位將會失??；定位時間較長；由于要向多個基站發(fā)射信號，將 會增加移動臺的功耗。若使用超聲波作為信號 源則可在一定程度上解決這一問題，然而超聲波傳播距離非常有限，同時易受干 擾，需要增加聲學發(fā)射機與接收機，并且兩者需要處于直線可視范圍內(nèi)，易受非 視距傳播的影響。 ＴＤＯＡ定位法【１習的基本思想是在節(jié)點上安裝超聲波收發(fā)器和ＲＦ收發(fā)器，通 過記錄兩種不同信號在兩個節(jié)點中的傳播時間差，再考慮兩種信號的傳播速度， ｌ ● 浙江工業(yè)大學碩士學位論文 由傳播時間差計算得到距離。發(fā)射節(jié)點同時發(fā)出兩種不同的信號，如射 頻信號傳播速度為ｙ１，超聲波信號傳播速度為如，接收節(jié)點收到兩種信號的時間 差為 △ ｒ，則計算得出兩節(jié)點間距離ｄ＝Ａｔｊ二蘭。 １．５．２．４ＡＯＡ（ＡｎｇｌｅｏｆＡｒｒｉｖａｌ） 這是一種估算鄰居節(jié)點發(fā)送信號方向的技術。該測量技術將距 離的測量轉(zhuǎn)換為角度的測量，未知節(jié)點可通過天線陣列或多個接收器結合來感知 信標節(jié)點信號的到達方向，計算兩個節(jié)點之間的相對方位角，最后通過三角測量 法計算未知節(jié)點坐標。通過兩條直線相交從而產(chǎn)生定 位角。另外，ＡＯＡ技術要建立 在智能天線的基礎上才能實現(xiàn)。位置估計的精度依賴于發(fā)送器相對于接收器 的位置。因此通常采用多于兩個的接收器來提供定位精度。在一個導航系統(tǒng)模型 中，也涉及到了類似的概念，它利用了一個光學資源集和一個旋轉(zhuǎn)光學傳感器來 獲取測量角度。除定位外，還能提供節(jié)點的方向信息，如ＭＩＴ的ＴｈｅＣｒｉｃｋｅｔＣｏｍｐａｓｓ 等項目【 ” ｌ中就利用多個接收器提出了基于ＡＯＡ的硬件解決方案，其原型系統(tǒng)可 在 “ ｏ．角內(nèi)以 177。的誤差確定接收信號的方向。同時，ＡＯＡ需要額 外硬件，在硬件尺寸 和功耗上都不適用于傳感器節(jié)點。 除了測距技術的局限性外，還需采用各種算法來減小測距誤差對定位精度的影 響，如多次測量、迭代求精等，進而產(chǎn)生額外的計算和通信開銷。 １．５．３．１三角測量法 三角測量定位方法也稱為信號到達角度（ＡＯＡ）定位法或方位測量定位法口川。在二維平面中，利 用兩個或更多信標節(jié)點的ＡＯＡ測量值，按照ＡＯＡ定位算法確定多條方位線的 交點，即可計算出未知節(jié)點的估計位置。 １．５．３．２三邊測量法 在無線傳感器網(wǎng)絡中，坐標系大多是二維空問，因此，只要知道了一個未知 節(jié)點到三個信標節(jié)點的距離就可以確定該未知節(jié)點的坐標。 如圖ｌ－４所示，三邊測 量定位法的基本原理就是求三個己知半徑和坐標圓心的圓的交點。 如圖ｉ－ ４所示，假設三個信標節(jié)點Ａ、Ｂ、Ｃ的坐標分別為 “ ，乃）、（而，咒）、 （而，乃），到未知節(jié)點Ｄ的距離分別為４、杰、嗚，假設未知節(jié)點Ｄ的坐標為（ｘ，），）， 根據(jù)二維空間距離計算公式，可以獲得方程組： Ｉ √ （ｚ一而）２＋（ｙ一乃）２＝４ ｛ √ ０一而）２＋（ｙ一坎）２＝如（１．３） Ｉ √ （石一而）２＋ ◇ 一乃）２＝以 在方程組（１－３）中，ｘ、ｙ是未知變量，這是一個非線性方程組，采用線性 化的方法就可以求解。因此，在實 際計算坐標時，一般不采用上述解方程的方法，而采用極大似然估計法或其他數(shù) 值解法。極大似然估計 法的原理如圖１ — ５所示。一Ｚ一２（鉑－－Ｘｎ）Ｘ ＋丘。－ｙ，）ｙ－－砟，一砰 方程組（１－６）用線性方程組表示為：ＡＸ＝ｂ，其中 ｆｂ一矗）（Ｙｌ－炸）１ 肚ｌ㈡Ｉ（１－７） ｌ（ ‘ ．１－毛）（咋一一只）Ｊ ｂ＝ ＃一《十開一Ｚ＋露一彳 ｉ 靠。一Ｚ＋露一Ｚ：。 １．５．４節(jié)點定位算法性能評價標準 國外的大學和研究機構提出了許多專用于無線傳感器網(wǎng)絡的定位系統(tǒng)。 １、定位精度。例如，定位精度為２０％表示定位誤差相當于節(jié)點通信半 徑的２０％。然而， 由于傳感器節(jié)點大量部署的特性，對于許多應用，定位的精度反而并不顯得十分 重要，當定位誤差小于傳感器節(jié)點無線通信半徑的４０％時，定位誤差對路由性能 和目標追蹤精確度的影響不會很大Ｉ刪。 ２、信標節(jié)點密度。因此，信標節(jié) 點密度也是評價定位系統(tǒng)和算法性能的重要指標之一。功耗問題始終是無線傳感器網(wǎng)絡設計和實現(xiàn)首要的考慮因素。與功耗密切相關的因素主要有：計算量、通信開銷、存儲 開銷、時間復雜性等。在無線傳感器網(wǎng)絡中，節(jié)點密度增大不僅意味著網(wǎng)絡部署費 用的增加，而且會因為節(jié)點間的通信沖突問題 帶來有限帶寬的阻塞。許多定位算法的精度受節(jié)點密度的影響，如 ＤＶ．Ｈｏｐ［４８＂４９］，蛔ｈｏｕｓ州等算法僅可在節(jié)點密集部署的情況下合理估算節(jié)點 位置。覆蓋率定義為可實現(xiàn)定位的未知節(jié)點與未知節(jié)點 總數(shù)的比例。但總會有一些不可達 或連通度極低（小于３）的未知節(jié)點存在，除這些節(jié)點，實現(xiàn)盡可能多的未知節(jié) Ｊ９ 浙江工業(yè)大學碩士學位論文 點的精確定位也是自身 定位算法和系統(tǒng)的追求目標之一。時間代價包括 一個系統(tǒng)的安裝時間、配置時間、定位所需時間。資金代價則包括實現(xiàn)一種 定位系統(tǒng)或算法的基礎設施、節(jié)點設備的總費用。不同的定位系統(tǒng)或算法的適用環(huán)境可以是在園區(qū)內(nèi)、 建筑物內(nèi)、一層建筑物或僅僅是一個房間內(nèi)實現(xiàn)定位。例如，ＲＡＤＡＲ 系統(tǒng)唧 僅能在建筑物的一層內(nèi)實現(xiàn)目標定位。通常，定位系統(tǒng)和算法都需要比較理想的無線通信 環(huán)境和可靠的網(wǎng)絡節(jié)點設備。由 于環(huán)境、能耗和其他原因，物理的維護或替換傳感器節(jié)點或使用其他高精度的測 量手段常常是十分困難或不可行的。 ９、網(wǎng)絡拓撲結構適應性。 上述９個性能指標不僅是評價無線傳感器網(wǎng)絡節(jié)點定位算法的標準，也是其 設計和實現(xiàn)的優(yōu)化目標。 同時這些 性能指標是相互關聯(lián)的，必須根據(jù)應用的具體需求做出權衡，以選擇和 設計合適的定位技術。在無線傳感器網(wǎng)絡中，從測量技術、定位形式、定 位效果、實現(xiàn)成本等方面考慮，節(jié)點定位算法可以用以下幾種方法進行分類。 Ｒａｎｇｇ．Ｂａｓｅｄ定位常用的測距技術有接收信號強度０ ≈ ＳＳＬ）技術、信號傳輸時間 （ＴＯＡ）技術、信號到達時間差（ＴＤＯＡ）技術和信號到達角度（ＡＯＡ）技術。除上述測距技術的局限性以外， Ｒａｎｇｅ — Ｂａｓｅｄ定位機制使用各種算法來減小測距誤差對定位的影響，包括多次測 量州，循環(huán)定位求精［６５１，這些都要產(chǎn)生大量計算和通信開銷。 Ｒａｎｇｅ．Ｆｒｅｅ定位技術則無需距離和角度信息，僅根據(jù)網(wǎng)絡連通性等信息即可 實現(xiàn)。信標節(jié)點ｊ的平均每跳距離 的計算公式如下： ｃＪ＝ 其中．，為其他信標節(jié)點，％為節(jié)點ｆ和節(jié)點，之間的跳數(shù)。ＤＶ－Ｈｏｐ算法Ｄ８－４９］、凸規(guī)劃算 法【ｓ，５１】和ＭＤＳ．ＭＡＰ算法【５３ｌ 等都是典型的Ｒａ／ｌｇｃ．Ｆｒｅｅ定位算法。 （二）絕對定位與相對定位 絕對定位的定位結果是一個標準的坐標位置，如經(jīng)緯度。絕對定位可為網(wǎng) 絡提供唯一的命名空間，受節(jié)點移動性影響較小，有更廣泛的應用領域。大多數(shù)定位系統(tǒng)和算法都可以實現(xiàn)絕對 定 位服務，典型的相對定位算法和系統(tǒng)有ＳＰＡ（Ｓｅｌｆ－ＰｏｓｉｔｉｏｎｉｎｇＡｌｇｏｒｉｔｈｍ）定位算 法ＤＴｌ、ＬＰＳ（ＬｏｃａｌＰｏｓｉｔｉｏｎｉｎｇＳｙｓｔ如）定位算法Ｍ和ＳｐｏｔＯＮ定位算法１５明等，而 ＭＤＳ－ＭＡＰ定位算法【５３】可以根據(jù)網(wǎng)絡配置的不同分別實現(xiàn)兩種定位。 ２ｌ 浙江工業(yè)大學碩士學位論文 精粒度定位方法是指基于 時間或是接收信號強弱的一些方法。 粗粒度定位方法就是指根據(jù)一些粗粒度信息如通過與信標節(jié)點的接近程度 等來推斷節(jié)點位置的方法。 （四）基于信標節(jié)點的定位算法和無信標節(jié)點的定位算法 根據(jù)定位過程中是否使用信標節(jié)點，可以把定位算法分為：基于信標 節(jié)點的 （ｂｅａｃｏｎ－ｂａｓｅｄ）定位算法和無信標節(jié)點的（ｂｅａｒ．ｏｎ．ｆＴｅｅ）定位算法。 （五）集中式算法與分布式算法 集中式計算ｐｌ】是指把所需信息傳送到某個中心節(jié)點（例如，一臺服務器），并 在中心節(jié)點處進行節(jié)點定位計算的方式；分布式計算是 指依賴節(jié)點間的信息交換 和協(xié)調(diào)，由節(jié)點自行計算的定位方式。它的缺點包括與中心節(jié)點位置較近的節(jié)點會 因為通信開銷大而過早地消耗完電能，導致整個網(wǎng)絡與中心節(jié)點信息交流的中 斷，無法實時定位等㈣。Ｎ．ｈｏｐｍｕｌｔｉｌａｔｅｒａｔｉｏｎｐｒｉｍｉｔｉｖｅ定位算法【醴】 可以根據(jù)應用需求采用兩種不同的 計算模式。這種算法的優(yōu)點是：通過使用信標節(jié)點，可以實現(xiàn)分布式計算，便于系統(tǒng)擴 展：如果系統(tǒng)允許采用集中計算方式，使用信標節(jié)點可以為定位算法提供更多的 信息，從而提高定位準確度。 定位技術的研究與發(fā)展在很大程度上決定了無線傳感器網(wǎng)絡應用的步伐，盡 管目前提出了很多研究方法，但一般都是在特定條件下來進行相關定位，真正實 現(xiàn)定位技術的發(fā)展還要進一步的深入研究。 本文對己有的無線傳感器網(wǎng)絡無需測距技術節(jié)點定位算法進行了深入的研 究，跟蹤了國內(nèi)外在該領域的研究進展，并在此基礎上提出了一種新的無需測距 節(jié)點定位算法，最后設計了無線傳感器網(wǎng)絡定位實驗節(jié)點并在實驗節(jié)點上實現(xiàn)定 位算法。進而 論述了無線傳感器網(wǎng)絡節(jié)點