碩士學位論文_無線傳感器網(wǎng)絡基于移動信標優(yōu)化路徑的定位算法研究.doc

廣東工業(yè)大學碩士學位論文(工學碩士)基于移動信標優(yōu)化路徑的定位算法研究classified index: school code: 11845udc: security class: class no.:2110704294a dissertation for masters degree of guangdong university of technology（master of engineering science）research on localization algorithm based on mobile beacon with optimal pathcandidate: xie xiaosongsupervisor: prof. cheng lianglunmay 2010faculty of automationguangdong university of technologyguangzhou, guangdong, p.r.china, 51000665 摘 要摘 要無線傳感器節(jié)點定位技術是無線傳感器網(wǎng)絡的關鍵技術之一，是無線傳感器網(wǎng)絡大多數(shù)應用的基礎。無線傳感器網(wǎng)絡應用的大多數(shù)領域, 如：目標監(jiān)測與跟蹤、路由位置信息的獲取等，都需要知道節(jié)點的位置信息。為此我們需要研究更為有效的定位算法，降低定位成本，提高定位精度。針對這種情況，本論文對基于移動信標優(yōu)化路徑的無線傳感器網(wǎng)絡節(jié)點算法進行了研究，該定位算法能夠實現(xiàn)節(jié)點的高效率定位。文章在dv-hop定位算法中引入移動信標節(jié)點，并研究信標節(jié)點的動態(tài)選擇算法及移動路徑優(yōu)化算法。本文的主要完成的工作有：1、分析歸納常用的無需測距的定位算法和基于信標的定位算法，研究基于信標的定位算法的定位機制，研究利用移動信標的信息來進行定位計算。2、提出基于移動信標改進的dv-hop定位算法，該算法在dv-hop定位算法的基礎上，利用一個移動的信標節(jié)點在網(wǎng)絡中按預定的路徑移動并不斷的廣播自己的位置信息，形成多個虛擬信標，研究平均跳距離的加權算法和信標節(jié)點的動態(tài)選擇算法，降低定位的成本和布網(wǎng)的復雜度，提高節(jié)點定位的精度和效率。3、結合基于移動信標改進的dv-hop定位算法，提出了面向無線傳感器網(wǎng)絡的移動信標的路徑規(guī)劃方法，把圖論引入信標移動路徑規(guī)劃，獲取針對所處網(wǎng)絡連通狀況的優(yōu)化信標移動路徑，提高算法的定位精度，減少算法定位過程的通信開銷，提高算法的效率。 最后在omnet+仿真環(huán)境下，仿真基于移動信標的定位算法，建立包括移動智能節(jié)點和普通節(jié)點的仿真模型，通過定位過程的通信和數(shù)據(jù)處理計算未知節(jié)點的位置，仿真表明，基于移動信標優(yōu)化路徑的定位算法既改善了定位的精度，又減少了定位算法的通信開銷，提高無線傳感器網(wǎng)絡節(jié)點定位效率。關鍵詞：無線傳感器網(wǎng)絡；移動信標；優(yōu)化路徑；omnet+；智能節(jié)點 參 考 文 獻abstractwireless sensor node localization is one of the key technologies for wireless sensor networks. its the foundation of most wireless sensor network applications, such as: target surveillance and tracking, routing and other location information acquiring, all of these need to know the location information of the nodes. so we need more effective localization algorithm to reduce the cost and increase the precision.in response, the paper research the nodes localization algorithm for wireless sensor network base on mobile beacon with optimal path. this algorithm can achieve high efficiency of positioning nodes. we introduced mobile beacon node into dv-hop localization algorithm, and study the dynamic beacon node selection algorithm and moving path optimal algorithm. these major works are: 1. summarizes common range-free localization algorithm and the algorithms base on beacon, study the positioning mechanism of localization algorithms base on beacon.2. improving dv-hop localization algorithm based on mobile beacon, the algorithm use a mobile beacon node to move in the network according to a predetermined path and broadcast its location information that create virtual beacons. we study the weighted average hop distance algorithm and the dynamic beacon node selection algorithm to reduce localization costs and complexity of distribution networks and improve accuracy and efficiency of node localization. 3. combined with the improved dv-hop localization algorithm based on mobile beacon, we proposed mobile beacon path planning method for wireless sensor networks. graph theory is introduced into the mobile path planning; by acquiring connectivity conditions of the network we optimize the path of mobile beacon. these make increase of positioning accuracy of positioning algorithm and reduce communication costs, improve efficiency of the algorithm. finally, we simulate mobile beacon base localization algorithm in omnet + + simulation environment by modeling mobile intelligent nodes and ordinary nodes in the network. the network computes the unknown nodes location through the positioning process of communication and data processing. the simulation results show that the algorithm base on mobile beacon with optimal path not only improves the positioning accuracy but also reduce the communication overhead of locatingm, these improve the efficiency of wireless sensor nodes localization.key words: wsn；mobile anchor；optimal path；omnet+；smart node目 錄摘 要iabstractiii目 錄vcontentsvii第一章 緒 論11.1 本論文的研究背景及意義11.1.1 研究背景與意義11.1.2 課題來源31.2 國內外研究現(xiàn)狀31.3 本論文的主要研究內容與結構5第二章 傳感器網(wǎng)絡常用節(jié)點定位算法相關研究72.1無線傳感器網(wǎng)絡基于信標節(jié)點的定位算法72.1.1相關工作72.1.2基于信標定位算法的優(yōu)點92.2無線傳感器網(wǎng)絡常用的定位方式的實現(xiàn)102.2.1極大似然估計法102.2.2三邊測量定位法112.2.3三角測量定位法122.3常用的節(jié)點定位算法132.3.1 常用的range-base節(jié)點定位算法132.3.2常用的range-free節(jié)點定位算法162.4本章小結18第三章 基于移動信標的節(jié)點定位算法193.1 無線傳感器網(wǎng)絡基于移動信標改進的dv-hop定位算法193.1.1 dv-hop定位算法203.1.2移動信標節(jié)點定位算法233.1.3 仿真分析263.2基于移動信標動態(tài)選擇改進dv-hop定位算法283.2.1 dv-hop定位算法平均跳距離計算誤差來源分析293.2.2基于移動信標動態(tài)選擇的改進型dv-hop定位算法過程313.2.3仿真分析343.3 本章小結35第四章 無線傳感器網(wǎng)絡移動信標的路徑優(yōu)化364.1無線傳感器網(wǎng)絡移動信標的移動模型分析364.1.1 隨機移動rwp(random way point)模型364.1.2高斯馬爾可夫移動gauss-markov模型374.1.3 螺線移動模型384.2面向無線傳感器網(wǎng)絡節(jié)點定位的移動信標的路徑優(yōu)化384.2.1基于圖論的信標移動路徑規(guī)劃方法394.2.2面向傳感器網(wǎng)絡的移動信標路徑規(guī)劃的仿真實現(xiàn)404.3 本章小結42第五章 基于移動信標優(yōu)化路徑定位算法的仿真實現(xiàn)435.1仿真實驗工具和實驗方法簡述435.1.1 omnet+仿真實驗平臺介紹435.1.2定位算法性能評價指標及分析方法445.2基于移動信標的傳感器網(wǎng)絡定位算法的設計455.2.1無線傳感器網(wǎng)絡仿真程序模型及程序設計465.2.2定位過程仿真程序設計515.3基于移動信標優(yōu)化路徑的定位算法性能分析525.4 本章小結55結論與展望56參 考 文 獻57攻讀學位期間發(fā)表的學術論文60攻讀學位期間參加的科研項目61獨創(chuàng)性聲明62致 謝63contentsabstract(chinese)iabstract(english)iiicontents(chinese)vcontents(english)viichapter 1 introduction11.1 research background and meaning of this subject11.1.1 research background and meaning11.1.2 source of this subject31.2 domestic and foreign research status31.3 main content and structure of this subject5chapter 2 common nodes localization for sensor network72.1 localization algorithm base on beacon72.1.1 realative work72.1.2the advantage of localization algorithm base on beacon92.2 implement of common localization ways102.2.1 maximum likelihood estimation102.2.2 trilateration method localization112.2.3 triangulation method localization122.3 common nodes localization algorithm132.3.1 common range-base nodes localization algorithm132.3.2 common range-free nodes localization algorithm162.4 summary of this chapter18chapter 3 localization algorithm based on mobile beacon193.1 improving dv-hop algorithm base on mobile beacon193.1.1 dv-hop localization algorithm203.1.2 nodes localization algorithm base on mobile beacon233.1.3 simulation result263.2 improving dv-hop algorithm base on mobile beacon dynamic selection283.2.1 analysis the error resource of dv-hop averager hop distance293.2.2 the process of the improving localization algorithm313.2.3 simulation result343.3 summary of this chapter35chapter 4 mobile beacon moving path optimization364.1 analysis the moving model of mobile beacon364.1.1 rwp(random way point) moving model364.1.2 gauss-markov moving model374.1.3 spire moving model384.2 mobile beacon moving path optimization for wsns384.2.1 mobile beacon path planning base on graph theory394.2.2 simulation of the mobile beacon path planning404.3 summary of this chapter42chapter 5 simulation of localzaition algorithm base on mobile beacon435.1 introduction of simulation tools and environment435.1.1 introduction of omnet+435.1.2 localization algorithm performance evaluation and analysis445.2 localization algorithm design base on mobile beacon455.2.1 programming and modeling localization algorithm465.2.2 programming the process of the localization algorithm515.3 performance evaluation and analysis of the localization algrithm base on optimize path525.4 summary of this chapter55conclusion and prospect56references57published papers60participant projects61original creative statement62acknowledgements63第一章 緒 論1.1 本論文的研究背景及意義1.1.1 研究背景與意義無線傳感器網(wǎng)絡綜合了傳感器、嵌入式計算、分布式信息處理和無線通信等技術，由許多相同或不同類型傳感器節(jié)點通過無線通信實現(xiàn)自組織，形成分布式自治網(wǎng)絡。它打破了傳統(tǒng)的點對點的數(shù)據(jù)信息交互方式，帶來了一種全新的信息獲取和處理模式1 。無線傳感器網(wǎng)絡(wireless sensor networks，wsn)是由部署在監(jiān)測區(qū)內大量的廉價微型傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡覆蓋區(qū)域內感知對象的信息，并傳送給觀察者2 。傳感器網(wǎng)絡節(jié)點在部署時往往是不可控制的，比如在大型的無線傳感器網(wǎng)絡應用中，通常將節(jié)點撒播在很廣的區(qū)域里，網(wǎng)絡中大部分的節(jié)點的位置是未知的，事先不能確定，但無線傳感器網(wǎng)絡的大多數(shù)應用都需要知道網(wǎng)絡中節(jié)點的位置信息，才可能獲取到網(wǎng)絡中事件的發(fā)生位置和信息來源位置。因此，定位是無線傳感器網(wǎng)絡的主要應用領域之一，對于大多數(shù)應用，不知道節(jié)點位置而感知的數(shù)據(jù)是沒有意義的。只有在傳感器節(jié)點自身正確定位后，才能確定傳感器節(jié)點監(jiān)測到的事件及信息發(fā)生的具體位置3 。節(jié)點必須明確自身位置才能詳細說明“在什么位置或區(qū)域發(fā)生了特定事件”，實現(xiàn)對外部目標的定位和追蹤。此外，在設計路由協(xié)議時利用節(jié)點位置信息還可以提高路由效率，為網(wǎng)絡提供命名空間，向網(wǎng)絡部署者報告網(wǎng)絡的覆蓋質量，實現(xiàn)網(wǎng)絡的負載均衡以及網(wǎng)絡拓撲的自配置4 。因此，節(jié)點的定位問題已經成為無線傳感器網(wǎng)絡的一個重要的研究方向。傳感器節(jié)點自身定位就是一種通過估計至鄰居節(jié)點的距離或鄰居數(shù)目，利用節(jié)點間的信息交換來確定各節(jié)點自身位置的機制。在傳感器網(wǎng)絡中，節(jié)點能夠自主確定位置被認為是其基本能力和系統(tǒng)的基本服務之一。對于wsn來說，人工部署或為所有網(wǎng)絡節(jié)點配置gps裝置都會受到成本、功耗、拓展性等問題的限制，因此，尋求wsn 自身定位機制成為許多研究機構和學者共同探討的問題4 。無線傳感器網(wǎng)絡中，根據(jù)定位過程中是否實際測量節(jié)點間的距離，把定位機制分為：基于測距的(range-based)定位和距離無關的(range-free)定位方法5 。前者需要測量相鄰節(jié)點間的絕對距離或方位，然后利用該實際距離來確定未知目標節(jié)點位置；后者則僅利用節(jié)點間距離關聯(lián)關系計算目標節(jié)點位置。range-based算法通過測量相鄰節(jié)點間的實際距離或方位進行定位，測量距離的具體的方法有time of arrival(toa) 6 ，time difference of arrival(tdoa)7 ，radio signal strength(rssi)8 和angle of arrival(aoa)9 等。range-based算法能夠實現(xiàn)精確定位，但由于需要在節(jié)點中加入gps或其它附加的測距的硬件設備，在實際應用中所需的成本較高。而range-free定位算法由于降低了對節(jié)點硬件的要求，引起了更多的關注，典型算法有dv-hop10 算法,基于rssi的dv-hop11 算法,基于連通性的定位算法12 等。目前基于距離的定位算法都是利用靜態(tài)的幾何關系來確定節(jié)點位置，且對信標節(jié)點的布置和密度要求高，如三邊、多邊測量定位、基于角度測量定位等算法，都需要移動節(jié)點至少獲得3個或者3個以上信標節(jié)點提供的坐標和距離13 。另一種思想則是使信標或者信標運動起來，通過帶有gps的已知位置的移動信標按某一規(guī)劃好的路徑或運動模型遍歷未知節(jié)點的區(qū)域，并發(fā)送定位信號，其它節(jié)點獲取這些信號來進行定位計算。動態(tài)算法的研究是最近興起的一個熱點，理論還不完善，有別于靜態(tài)算法所涉及的都是固定節(jié)點，其主要是討論對傳感網(wǎng)中移動節(jié)點定位的方法14 ，包括待測節(jié)點的運動和信標節(jié)點的運動。當然從理論上講，完全可以借鑒靜態(tài)已有的成熟算法，計算出特定時刻的節(jié)點位置，但因為節(jié)點的運動，對定位算法的實時性要求較高，通常的改進方法是加入對節(jié)點運動的預測估計15 ，或是使定位算法能自動適應不同節(jié)點運動的方式，從而提高對運動節(jié)點的定位準確性。雖然節(jié)點的移動性使定位過程復雜化，但是利用節(jié)點的移動性可提高定位精度，減少定位代價。在bergamo等的研究中，網(wǎng)絡中有2個固定的信標向全網(wǎng)傳送坐標信息，其余處于運動狀態(tài)的節(jié)點根據(jù)接收到的信號強度進行自身定位16 。國內外學者對定位問題進行了大量研究，提出了幾種比較典型的定位算法17 。但這些算法普遍存在以下局限18 ： 依賴特殊硬件的支持； 需要特殊的網(wǎng)絡拓撲結構。而在無線傳感器網(wǎng)絡中引入移動節(jié)點，可以增強其功能。如文獻19 通過將幾個未知節(jié)點移動到網(wǎng)絡節(jié)點密度相對稀疏的區(qū)域以彌補節(jié)點密度分布不均勻的不足。文獻20 提到利用移動參考節(jié)點和rssi(接收信號強度指示)方法對未知節(jié)點進行定位，但是在現(xiàn)實環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得rssi技術在實際應用中仍然存在困難。尤其是節(jié)點對能耗，體積等要求嚴格時，更多的時候并不能應用這種基于測距的定位技術。免測距的定位算法不需要測量節(jié)點間的距離，而是利用距離矢量路由、網(wǎng)絡連通情況或者gps定位等思想提出的一種分布式定位方法，無需測距，這無疑降低了組網(wǎng)成本。但由于沒有相應的硬件測距支持，定位存在一定程序的誤差，當網(wǎng)絡中存在障礙物時，節(jié)點間的歐氏距離會因為彎曲路徑而產生較大的誤差，精度也相應的降低21 。因此如何提高這種免測距定位算法的精度也成為了一個研究的熱點方向。1.1.2 課題來源本課題來源于國家自然科學基金資助項目（編號：60673132）；廣東省自然科學基金重點項目（編號：07117421）。1.2 國內外研究現(xiàn)狀基于移動信標的定位算法是近年來的研究熱點。由于網(wǎng)絡定位算法大多依賴于信標節(jié)點的密度，網(wǎng)絡的聯(lián)通性。而信標節(jié)點的造價數(shù)倍甚至十幾倍于普通節(jié)點，所以其定位成本較高。而移動信標節(jié)點通過引入一個可在網(wǎng)絡中漫游移動的節(jié)點來廣播自己的位置信息構成虛擬信標，從而可以降低定位成本，提高定位效率。所以移動信標的定位算法近來成為新的研究熱點，國內外許多學者進行了許多的研究，基于移動信標的定位算法主要研究問題是如何將移動信標與現(xiàn)在的定位算法結合，研究構造的虛擬信標的動態(tài)選擇算法及移動信標的移動路徑的規(guī)劃。為此，國內外有許多學者把移動信標與經典的質心定位算法、apit定位算法及dv-hop定位算法等相結合來改進這些定位算法。而質心定位算法及dv-hop定位算法因為無需測距有著更多的優(yōu)勢也得到更多的研究。無需測距（range-free）的定位算法不需要直接測量距離信息，而是根據(jù)網(wǎng)絡的連通性確定網(wǎng)絡中節(jié)點之間的跳數(shù)，同時根據(jù)已知位置參考節(jié)點的位置等信息估計每一跳的大致距離，然后估出節(jié)點在網(wǎng)絡中的位置22 。典型的無需測距的定位算法有dv-hop定位算法，apit定位算法、質心定位算法、amorphous定位算法等，它們所需的網(wǎng)絡模型都是由參考節(jié)點和未知位置的節(jié)點組成。通過移動信標，或者說移動信標來對整個網(wǎng)絡的未知節(jié)點進行定位的方法是最來興起的一種新的定位方法，將節(jié)點裝載在移動機器人上或是進行節(jié)點撒播的飛行器上，并且該節(jié)點裝有gps或其他定位裝置，這樣就構造了移動信標23 。它可以在移動的過程中實時獲得其當前的位置信息。通過移動信標來定位的主要思想是：移動信標在“感興趣的區(qū)域內（region of interest，簡稱roi）”24 移動的過程中，不斷的廣播包含其當前位置信息的分組，在其通信半徑內的節(jié)點將接收到這些廣播分組，當未知節(jié)點接收到三個或者三個以上的與其距離為r的位置信息時，就可以利用三邊測量法或極大似然估計法17 計算該未知節(jié)點的位置。國內外對于移動信標的定位方法及信標的移動路徑的規(guī)劃研究處于起步階段，相關的文獻并不多，提出的算法也不夠成熟，文獻25 和26 提出的定位方法只需要一個可以移動的信標，其中文獻25 利用toa測距技術和質心法來計算待定位節(jié)點位置，文獻26 不需要復雜的測距技術，而是通過信標的不斷運動并利用幾何限制關系來計算待定位節(jié)點位置。文獻27 則在dv-hop的基礎上引入移動的信標形成一種新的m-a-dv-hop算法，實現(xiàn)在不提高硬件成本的情況下，又能達到同樣定位效果的構想。其定位的主要思想是：當移動信標在定位區(qū)域內移動時，移動到若干個新位置，立即在該位置補充一個普通節(jié)點。根據(jù)信標的即時位置信息，新位置的普通節(jié)點知道自身的位置。它們就等同于信標。另外，增加普通節(jié)點的同時，也提高了隨機網(wǎng)絡的連通度。引入移動信標的優(yōu)勢是即使只有一個信標也可以實現(xiàn)對未知節(jié)點的定位。本論文針對基于信標的定位算法需要較高的信標節(jié)點密度導致定位成本提高的情況，引入移動信標在網(wǎng)絡中移動并廣播自己的位置分組信息在網(wǎng)絡中構成虛擬信標的方法來定位未知節(jié)點，在dv-hop定位算法的基礎上將移動信標構成的虛擬信標來計算平均跳距離并結合跳數(shù)信息來對未知節(jié)點定位，通過規(guī)劃優(yōu)化的路徑來提高定位效率。對于移動信標的移動路徑的規(guī)劃也是一個重要的問題，本文進行了初步的研究。當采用移動信標在網(wǎng)絡中移動來廣播定位信息時，移動信標的移動路徑及廣播時間的選取，則很大程序上決定了網(wǎng)絡定位的能量消耗及定位的效率。故研究信標的移動路徑規(guī)劃，使網(wǎng)絡中的節(jié)點以最小的代價獲得足夠多用于自身定位的信息成為一個重要的研究內容。目前國內外主要的路徑規(guī)劃均為靜態(tài)的路徑，研究如何使移動節(jié)點的移動軌跡可以盡量覆蓋網(wǎng)絡區(qū)域。這樣的算法顯然不能最大限度的節(jié)約節(jié)點的能耗，對于嚴格要求能源的傳感器網(wǎng)絡節(jié)點來說，必然需要更為優(yōu)化及適用于當前網(wǎng)絡的路徑規(guī)劃算法來使節(jié)點移動路徑盡可以少，減少廣播的信息來減少網(wǎng)絡節(jié)點的通信消耗。根據(jù)現(xiàn)有的路徑規(guī)劃方法，可以把路徑的規(guī)劃分為靜態(tài)和動態(tài)規(guī)劃，靜態(tài)的路徑規(guī)劃與網(wǎng)絡的連通狀況無關，根據(jù)需要定位的roi區(qū)域，規(guī)劃以盡可能短的路徑覆蓋區(qū)域為目標，目前靜態(tài)的路徑主要有隨機移動模型，高斯馬爾可夫移動模型，螺線移動模型和scan移動模型。而國外有根據(jù)網(wǎng)絡的聯(lián)通狀況來進行路徑規(guī)劃的動態(tài)算法，文獻28 提出幾條最優(yōu)路徑的選擇原則，本文主要進行動態(tài)路徑優(yōu)化研究。1.3 本論文的主要研究內容與結構針對無線傳感器網(wǎng)絡基于信標節(jié)點的無需測距定位算法精度低，定位效率低的情況，本文提出基于移動信標優(yōu)化路徑的無線傳感器網(wǎng)絡節(jié)點定位算法。研究的內容主要如下：1、分析歸納常用的無需測距的定位算法和基于信標的定位算法，研究基于信標的定位算法的定位機制，研究利用移動信標的信息來進行定位計算。2、提出基于移動信標改進的dv-hop定位算法，該算法在dv-hop定位算法的基礎上，利用一個移動的信標節(jié)點在網(wǎng)絡中按預定的路徑移動并不斷的廣播自己的位置信息，形成多個虛擬信標，未知節(jié)點采用加權處理的方法計算平均跳距及其與各虛擬信標的距離，最后利用三邊測量法計算未知節(jié)點的位置信息，實現(xiàn)節(jié)點精確定位。并研究移動信標的動態(tài)選擇算法來選擇能獲得最大計算精度的移動信標節(jié)點進行定位計算。仿真證明，相對于dv-hop算法，基于移動信標改進的dv-hop定位算法降低了定位的成本和布網(wǎng)的復雜度，提高節(jié)點定位的精度和效率。3、結合基于移動信標改進的dv-hop定位算法，提出了基于roi(region of interest)的移動信標的路徑規(guī)劃方法，并把圖論引入信標移動路徑規(guī)劃，獲取針對所處網(wǎng)絡連通狀況的優(yōu)化信標移動路徑，提高算法的定位精度，減少算法定位過程的通信開銷，提高算法的效率。文章結構層次安排如下：第1章 闡述了本課題的研究背景、研究意義及項目來源。通過對國內外相關領域的研究現(xiàn)狀進行探討，確立傳感器網(wǎng)絡定位算法的研究的方向。第2章 介紹了信標節(jié)點定位算法的相關工作，闡述了常用的基于移動信標的無線傳感器節(jié)點定位算法，并分析了這幾種常用算法的特點。第3章 研究基于移動信標的無線傳感器網(wǎng)絡節(jié)點的定位算法，將移動信標引入到dv-hop定位算法中，提出了基于移動信標的dv-hop定位算法和基于移動信標動態(tài)選擇的改進dv-hop定位算法，同時分析了改進算法在特定移動模型下的定位精度。第4章 結合基于移動信標改進的dv-hop定位算法，提出了面向無線傳感器網(wǎng)絡的移動信標的路徑規(guī)劃方法，把圖論引入信標移動路徑規(guī)劃，獲取針對所處網(wǎng)絡連通狀況的優(yōu)化信標移動路徑。第5章 在omnet+仿真平臺上進行無線傳感器網(wǎng)絡節(jié)點算法的仿真，設計移動信標節(jié)點的模型和移動模型，并通過仿真論證優(yōu)化路徑對定位算法的影響。 第二章 傳感器網(wǎng)絡常用節(jié)點定位算法相關研究無線傳感器網(wǎng)絡節(jié)點定位方法的不同，分成兩種定位類型：基于信標節(jié)點和不基于信標節(jié)點(也有論著將其分為無錨節(jié)點和有錨節(jié)點的定位算法，信標節(jié)點也可稱為錨節(jié)點)。不基于信標節(jié)點的定位方法屬于相對定位，基于信標的定位算法可以得出未知節(jié)點的絕對坐標。當前絕大多數(shù)節(jié)點定位算法均假設網(wǎng)絡中存在少量信標節(jié)點，以實現(xiàn)整個網(wǎng)絡的絕對定位。2.1無線傳感器網(wǎng)絡基于信標節(jié)點的定位算法2.1.1相關工作基于信標節(jié)點的定位算法在研究集中在移動信標的選擇、移動路徑、定位計算方法及移動節(jié)點的研究。由于信標節(jié)點需要移動，其在網(wǎng)絡中的作用更為重要，需要根據(jù)傳感器網(wǎng)絡的特點進行移動信標節(jié)點的設計及無線傳感器網(wǎng)絡的應用系統(tǒng)的研究。構建無線傳感器網(wǎng)絡應用系統(tǒng)，需要考慮網(wǎng)絡在應用中的成本、數(shù)量、通信方面存在的諸多問題，主要需要考慮以下幾個方面：1、低成本：系統(tǒng)必須是低成本，不僅從節(jié)點硬件、軟件考慮，而且傳感器也必須采用相對價格低的產品；2、低功耗：系統(tǒng)中采用普通aaa電池供電，所以要求網(wǎng)絡必須是低功耗的，保證網(wǎng)絡的生命周期盡量長；3、實時監(jiān)測：監(jiān)測信息需實時傳輸?shù)焦芾矸掌?，方便用戶實時查詢；4、網(wǎng)關無線通信：由于監(jiān)測區(qū)域的特殊性，不一定存在有線網(wǎng)絡，例如：internet、有線局域網(wǎng)等，故網(wǎng)關具有把采集的環(huán)境信息無線傳輸?shù)椒掌鞯墓δ?，不受監(jiān)測區(qū)域的影響；5、精度：傳感器決定了采集數(shù)據(jù)的精度，傳感器采集數(shù)據(jù)的精度可以在規(guī)定范圍內存在一定程度的誤差；6、傳感器接口靈活：系統(tǒng)根據(jù)環(huán)境參數(shù)的不同采用不相同的接口，傳感器的類型也需根據(jù)實際需要而定，因此節(jié)點的傳感器接口需靈活設定。傳感器節(jié)點主要由低功耗的單片機，無線射頻模塊以及車載平臺等組成，它首先采集各個模擬信號，把模擬信號轉化成數(shù)字信號，經過單片機處理后，通過無線射頻模塊把數(shù)據(jù)傳送到匯聚節(jié)點。匯聚節(jié)點的處理器采用arm9 s3c2410，它還包括gprs模塊，無線射頻模塊，網(wǎng)絡接口等，它的功能主要是接收附近所有傳感器節(jié)點發(fā)送過來的數(shù)據(jù)，并且通過internet或者gprs模塊上傳到上層監(jiān)控軟件。無線傳感器網(wǎng)絡移動節(jié)點定位系統(tǒng)的硬件系統(tǒng)需要根據(jù)上面所述的要求建立合適的傳感器系統(tǒng)，為此設計的傳感器移動節(jié)點主要由低功耗的微處理器，射頻模塊，傳感器接口，電源模塊以及車載平臺5部分組成，如圖2-1所示，普通節(jié)點則沒有車載平臺。圖2-1傳感器移動節(jié)點結構fig. 2-1 sensor network mobile nodes structure根據(jù)此模型設計制作的移動節(jié)點如下圖2-2所示。節(jié)點采用msp430低功耗單片機，芯片集成spi，iic，12位a/d等標準接口，可以通過spi接口與射頻模塊cc2420進行連接，節(jié)點還設計了了標準的傳感器接口，可以通過接口連接到常用的傳感器模塊。為了實驗方便，節(jié)點集成了ds18b20溫度傳感器，tsl2561光強度傳感器。同時，把節(jié)點放在車載平臺上，實現(xiàn)節(jié)點的移動。圖2-2傳感器網(wǎng)絡節(jié)點fig. 2-2 sensor network nodes 黎大鵬在文獻29 中研究了基于信標節(jié)點動態(tài)調整的移動節(jié)點的定位算法。對基于錨節(jié)點動態(tài)調整的傳感器網(wǎng)絡移動節(jié)點定位系統(tǒng)進行了研究，該系統(tǒng)能夠實現(xiàn)移動節(jié)點的高效率定位。文章分別從嵌入式硬件平臺的硬件設計，移動節(jié)點定位算法，以及定位系統(tǒng)的程序設計與實現(xiàn)三方面來對該系統(tǒng)進行研究。提出基于vwmc（voronoi and weight monte carlo method）的傳感器網(wǎng)絡移動節(jié)點定位算法，該算法在mcl（monte carlo localization）算法的基礎上加入voronoi圖和權值分析技術。仿真證明，相對于mcl算法，基于vwmc的傳感器網(wǎng)絡移動節(jié)點定位算法提高了移動節(jié)點定位的精度和效率。結合基于vwmc的傳感器網(wǎng)絡移動節(jié)點定位算法以及錨節(jié)點動態(tài)調整策略，提出了基于錨節(jié)點動態(tài)調整的傳感器網(wǎng)絡移動節(jié)點定位算法，提高了算法對外界干擾的抵御能力。2.1.2基于信標定位算法的優(yōu)點相對定位通常是以網(wǎng)絡中部分節(jié)點為參考，建立整個網(wǎng)絡的相對坐標系統(tǒng)。絕對定位可為網(wǎng)絡提供唯一的命名空間，受節(jié)點移動性影響較小，有更廣泛的應用領域。但研究發(fā)現(xiàn)，在相對定位的基礎上也能夠實現(xiàn)部分路由協(xié)議，尤其是基于地理位置的路由(geo-routing)，而且相對定位不需要信標節(jié)點。在某些無需網(wǎng)絡節(jié)點絕對位置的應用中，可以采用無信標節(jié)點的定位算法來實現(xiàn)整個網(wǎng)絡的相對定位。典型的無信標節(jié)點的定位算法包含spa30 、sdgps31 、afl32 等定位算法。spa算法選擇網(wǎng)絡中密度最大處的一組節(jié)點作為建立網(wǎng)絡全局坐標系統(tǒng)的參考點，并在其中選擇連通度最大的一個節(jié)點作為坐標系統(tǒng)的原點。首先根據(jù)節(jié)點間的測距結果在各個節(jié)點上建立局部坐標系統(tǒng)，通過節(jié)點間的信息交換與協(xié)調，以參考點為基準通過坐標變換逐步建立全局坐標系統(tǒng)。spa算法的主要缺點是網(wǎng)絡通信開銷太大。sdgpsn算法在spa算法的基礎上，提出了基于聚類的定位思想?；舅枷?網(wǎng)絡部署完后，每個傳感器節(jié)點開始運行一個隨機的定時器，如果與鄰居節(jié)點相比，節(jié)點i的定時器最先到期且沒有收到任何鄰居節(jié)點的消息，則i升級為主節(jié)點，并向鄰居節(jié)點廣播此消息，所有接收到該消息的鄰居節(jié)點中止其定時器并成為該主節(jié)點的從節(jié)點。這些節(jié)點構成一個以主節(jié)點i為坐標原點的節(jié)點域，并隨掃a擇兩個與i相鄰的從節(jié)點為輔助節(jié)點對，構建一個局部坐標系。節(jié)點域內的所有其他從節(jié)點通過選擇適當?shù)妮o助節(jié)點對來計算其在此局部坐標系中的坐標。然后相鄰的節(jié)點域依靠兩個域的共同邊際節(jié)點的相關坐標信息，以主節(jié)點id較小的局部坐標系為參照，進行相鄰局部坐標系間的坐標轉換，直至建立一個全局坐標系。sdgpsn算法和spa算法相比，通信開銷明顯降低，這使得它更適于大規(guī)模無線傳感器網(wǎng)絡的部署。afl算法是完全分布式的節(jié)點定位方法。利用amp所有節(jié)點從隨機初始坐標分配開始，只利用局部距離估計和通過局部信息交換收斂到一個與距離估計一致的坐標分配。在給定一個未知坐標的節(jié)點集合和一種節(jié)點可以估測它到其鄰居節(jié)點距離機制的條件下，通過局部節(jié)點間的通信決定每個節(jié)點的位置坐標?；谛艠斯?jié)點的定位算法依賴于某些已知坐標位置的節(jié)點。這種定位算法需要預先定位信標節(jié)點，否則無法正常運行，另外為了減小定位誤差，信標節(jié)點的數(shù)目還須足夠多。基于信標節(jié)點的定位算法的一個重要特征是定位精度取決于信標點密度。為了解決基于信標節(jié)點的定位算法對信標節(jié)點的密度的依賴，近年來許多學者進行了移動信標節(jié)點定位算法的研究，通過在引入移動信標節(jié)點在網(wǎng)絡中按預定軌跡漫游并廣播自己的位置分組在構成虛擬信標節(jié)點，可以大大減少信標節(jié)點的投入。因為信標節(jié)點造價往往比普通節(jié)點高，在許多固定的傳感器網(wǎng)絡中，定位成功后信標節(jié)點將轉為普通節(jié)點使用，極大的浪費了資源。所以基于移動信標節(jié)點的定位算法成為近年來研究的一個熱點。本章首先介紹無線傳感器網(wǎng)絡常用的定位方式及其實現(xiàn)，然后介紹常用的基于測距和無需測距的定位算法，并根據(jù)這些算法的特點，分析其優(yōu)缺點，為下一章提出新的基于移動信標的定位算法奠定了理論基礎。2.2無線傳感器網(wǎng)絡常用的定位方式的實現(xiàn)2.2.1極大似然估計法傳感器網(wǎng)絡移動節(jié)點定位系統(tǒng)中節(jié)點有可能和多于3個的不同信標相連。因此可以使用更多的節(jié)點以獲得冗余信息來計算未知節(jié)點的位置。極大似然估計多邊測量33 就采用了上面的方法，已知n個節(jié)點的坐標分別為(x1,y1)，(x2,y2)，(x3,y3)，.，(xn ,yn )，它們到未知節(jié)點 d 的距離分別為dl，d2，d3，.，dn，假設節(jié)點 d的坐標為(x，y)。那么，存在下列公式： (2.1)最后，使用標準的最小均方差估計方法可以得到未知節(jié)點 d 的坐標。2.2.2三邊測量定位法三邊測量法是通過 rssi值得出未知節(jié)點到 3 個信標的距離，通過這3個距離值計算出未知節(jié)點的位置。如下圖2-1所示，當節(jié)點p1，p2，p3未知節(jié)點p發(fā)出的定位信號時，根據(jù) rssi值，可以得到 p1到 p，p2到 p，p3到 p的距離d1，d2，d3；分別以 p1，p2，p3為圓心，d1，d2，d3為半徑作圓，通過這 3個圓相交區(qū)域定出未知節(jié)點的位置。圖2-3三邊測量法原理fig. 2-3 trilateration method principle但是在真實環(huán)境下三邊測量法存在巨大的缺陷，如圖3-6所示，實際上測量得到的3個距離rp1，rp2，rp3存在著誤差，導致以rp1，rp2，rp3為半徑建立的3個圓并不是相交于一點，而是相交于一個區(qū)域。這樣建立起來的等式方程組沒有解，根本無法實現(xiàn)對節(jié)點的定位。有些文章提出了以區(qū)域的質點作為節(jié)點的位置，這種方法也不好，節(jié)點定位的誤差會隨著相交區(qū)域的增大而大大地提高?？偟膩碚f，針對節(jié)點的定位算法都是在理想的仿真環(huán)境下進行研究的，當節(jié)點處于存在干擾或者移動的情況下，這些算法或不能夠實現(xiàn)節(jié)點精確的定位，或算法的計算量太大。2.2.3三角測量定位法三角測量法原理如圖2-2所示，已知a、b、c三個節(jié)點的坐標分別為(xa,ya),(xb,yb)，(xc,yc)，節(jié)點d相對于節(jié)點a、b、c的角度分別為：adb，adc，bdc，假設節(jié)點d的坐標為(x，y)，d為圖2-2中三個圓的交點。圖2-4三角測量法示意圖fig. 2-4 triangulation method principle對于節(jié)點a，c和角adc，如果弧段ac在abc內，那么能夠唯一確定一個圓，設圓心為，半徑為r1，那么，并存在下列公式： (2.2)由式(2.2)能夠確定圓心o1點的坐標和半徑r1。同理對a，b，adb和b，c，bdc分別確定相應的圓心、半徑r2、圓心和半徑r3。最后根據(jù)已知的r1，r2，r3，采用三邊測量法確定d點坐標。2.3常用的節(jié)點定位算法2.3.1 常用的range-base節(jié)點定位算法根據(jù)定位過程中是否測量實際節(jié)點間的距離，定位算法可分為：基于距離(range-based)的定位算法和距離無關(range-free)的定位算法34 。前者需要測量相鄰節(jié)點間的絕對距離或方位，然后利用該實際距離來確定未知目標節(jié)點位置；后者則僅利用節(jié)點間距離關聯(lián)關系計算目標節(jié)點位置35 。1、基于信號強度（rssi）定位rssi(received signal strength indicator)是接收到的信號強度指示器，是一種利用信號衰減推測距離的測距技術36。目前很多定位算法都是利用rssi技術實現(xiàn)的。目前，wsn網(wǎng)絡中無線通信芯片主要有兩種：cc1000和cc2420。cc1000的工作頻帶為315mhz,868mhz,915mhz，數(shù)據(jù)傳送速率可達72.8kbit/s，適用于跳頻協(xié)議。cc2420工作頻帶在2.4ghz-2.4835ghz，采用的是o-qpsk調制方式，數(shù)據(jù)速率在250kbit/s，具有較高的抗干擾能力。對于cc1000通信芯片，rssi值是一個10位的寄存器值，而對于cc2420，該值卻是一個8位的寄存器值。它是通過a/d轉換器轉換而來的，芯片不同，rssi的轉換方式也是不同的。若芯片是cc1000： （2.3） （2.4） （2.5） （2.6）其中，rssi是寄存器值，也就是節(jié)點接收到的信號強度值，vrssi是a/d轉換前的rssi電壓值，單位為(v)；vbat為電源電壓，該值為一個常數(shù)值3v；pcurrent是當前節(jié)點的發(fā)射功率，單位為dbm；p0為當節(jié)點與源節(jié)點足夠遠時接收到的功率值，一般來說p0取-80dbm；p為功率衰減值。（2.6）式是由（2.3），（2.4）