廣東工業(yè)大學(xué)碩士學(xué)位論文 ( 工 學(xué) 碩 士 ) 基于移動(dòng) 信標(biāo) 優(yōu)化路徑的 定位算法研究 二零 一 零年 五 月 分類號(hào)： 學(xué)校代號(hào)： 11845 密級(jí)： 學(xué)號(hào)： 2110704294 廣東工業(yè)大學(xué)碩士學(xué)位論文 （ 工 學(xué) 碩 士 ） 基于移動(dòng) 信標(biāo) 優(yōu)化路徑的 定位算法研究 指導(dǎo)教師 姓名、職稱 ： 教授 企業(yè) 導(dǎo)師 姓名、職稱 ： 無 專業(yè) 或 領(lǐng)域 名 稱 ： 控制理論與控制工程 學(xué) 生 所 屬 學(xué) 院 ： 自動(dòng)化學(xué)院 論 文 答 辯 日 期 ： 2010 年 5 月 11845 o.:2110704294 A s 010 510006摘 要 I 摘 要 無線傳感器節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò) 的 關(guān)鍵技術(shù)之一， 是無線傳感器網(wǎng)絡(luò)大多數(shù)應(yīng)用的基礎(chǔ)。 無線傳感器網(wǎng)絡(luò)應(yīng)用的 大多數(shù)領(lǐng)域 , 如：目標(biāo)監(jiān) 測(cè)與跟蹤、路由 位置信息的獲取 等 ，都需要知道節(jié)點(diǎn)的位置信息 。 為此我們需要研究更為有效的定位算法，降低定位成本，提高定位精度。 針對(duì)這種情況， 本論文 對(duì) 基于 移動(dòng) 信標(biāo) 優(yōu)化路徑的無線 傳感器網(wǎng)絡(luò)節(jié)點(diǎn) 算法進(jìn)行了研究 ，該 定位算法 能夠?qū)崿F(xiàn) 節(jié)點(diǎn)的高效率定位。文章 在 位算法中引入移動(dòng)信標(biāo)節(jié)點(diǎn) ， 并研究 信標(biāo)節(jié)點(diǎn)的動(dòng)態(tài)選擇算法及 移動(dòng)路徑優(yōu)化算法 。 本文的 主要完成的工作 有： 1、 分析 歸納常用的 無需測(cè)距的定位算法和基于信標(biāo)的定位算法，研究基于信標(biāo)的定位算法的定位機(jī)制 ，研究利用移動(dòng)信標(biāo)的信息來進(jìn)行定位計(jì)算 。 2、提出基于 移動(dòng) 信標(biāo) 改進(jìn)的 位算法 ， 該算法在 位算法的基礎(chǔ)上，利用一個(gè)移動(dòng)的信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中按預(yù)定的路徑移動(dòng)并不斷的廣播自己的位置信息，形成多個(gè)虛擬信標(biāo)， 研究平均跳距離的加權(quán)算法和信標(biāo)節(jié)點(diǎn)的動(dòng)態(tài)選擇算法， 降低定位的成本和布網(wǎng)的復(fù)雜度 ， 提高 節(jié)點(diǎn)定位 的精度和效率。 3、結(jié)合 基于 移動(dòng) 信標(biāo) 改進(jìn)的 位算法 ，提出了面向無線傳感器網(wǎng)絡(luò) 的移動(dòng) 信標(biāo) 的路徑規(guī)劃方法，把圖論引入 信標(biāo) 移動(dòng)路徑規(guī)劃 ， 獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化 信標(biāo) 移動(dòng)路徑，提高算法的定位精度，減少算法定位過程的通信開銷，提高 算法 的效率 。 最后 在 仿真環(huán)境下，仿真基于移動(dòng) 信標(biāo) 的定位算法， 建立包括 移動(dòng)智能節(jié)點(diǎn) 和 普通節(jié)點(diǎn)的仿真模型，通過定位過程的通信和數(shù)據(jù)處理計(jì)算未知節(jié)點(diǎn)的位置，仿真表明 ，基于 移動(dòng) 信標(biāo) 優(yōu)化路徑的定位算法 既改善了定位的精度，又減少了定位 算法 的 通信開銷 ， 提高無線 傳感器網(wǎng)絡(luò)節(jié)點(diǎn) 定位效率 。 關(guān)鍵詞： 無線 傳感器網(wǎng)絡(luò)； 移動(dòng) 信標(biāo) ； 優(yōu)化路徑 ； ； 智能節(jié)點(diǎn) is of Its of of to of So we to In on of We 1. on of on 2. on a to in to a its We to of of 3. on we is by of we of of of of we + 廣東工業(yè)大學(xué)碩士學(xué)位論文 IV by in s of on of of ； 錄 V 目 錄 摘 要 . 錄 . V . 一章 緒 論 . 1 論文的研究背景及意義 . 1 究背景與意義 . 1 題來源 . 3 內(nèi)外研究現(xiàn)狀 . 3 論文的主要研究?jī)?nèi)容與結(jié)構(gòu) . 5 第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究 . 7 線傳感器網(wǎng)絡(luò)基于信標(biāo)節(jié)點(diǎn)的定位算法 . 7 關(guān)工作 . 7 于信標(biāo)定位算法的優(yōu)點(diǎn) . 9 線傳感器網(wǎng)絡(luò)常用的定位方式的實(shí)現(xiàn) . 10 大似然估計(jì)法 . 10 邊測(cè)量定位法 . 11 角測(cè)量定位法 . 12 用的節(jié)點(diǎn)定位算法 . 13 用的 點(diǎn)定位算法 . 13 用的 點(diǎn)定位算法 . 16 章小結(jié) . 18 第三章 基于移動(dòng)信標(biāo)的節(jié)點(diǎn)定位算法 . 19 線傳感器網(wǎng)絡(luò)基于移動(dòng)信標(biāo)改進(jìn)的 位算法 . 19 位算法 . 20 動(dòng)信標(biāo)節(jié)點(diǎn)定位算法 . 23 廣東工業(yè)大學(xué)碩士學(xué)位論文 仿真分析 . 26 于移動(dòng)信標(biāo)動(dòng)態(tài)選擇改進(jìn) 位算法 . 28 位算法平均跳距離計(jì)算誤差來源分析 . 29 于移動(dòng)信標(biāo)動(dòng)態(tài)選擇的改進(jìn)型 位算法過程 . 31 真分析 . 34 章小結(jié) . 35 第四章 無線傳感器 網(wǎng)絡(luò)移動(dòng)信標(biāo)的路徑優(yōu)化 . 36 線傳感器網(wǎng)絡(luò)移動(dòng)信標(biāo)的移動(dòng)模型分析 . 36 機(jī)移動(dòng) 型 . 36 斯馬爾可夫移動(dòng) 型 . 37 線移動(dòng)模型 . 38 向無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的移動(dòng)信標(biāo)的路徑優(yōu)化 . 38 于圖論的信標(biāo)移動(dòng)路徑規(guī)劃方法 . 39 向傳感器網(wǎng)絡(luò)的移動(dòng)信標(biāo)路徑規(guī)劃的仿真實(shí)現(xiàn) . 40 章小結(jié) . 42 第五章 基于移動(dòng)信標(biāo)優(yōu)化路徑定位算法的仿真實(shí) 現(xiàn) . 43 真實(shí)驗(yàn)工具和實(shí)驗(yàn)方法簡(jiǎn)述 . 43 仿真實(shí)驗(yàn)平臺(tái)介紹 . 43 位算法性能評(píng)價(jià)指標(biāo)及分析方法 . 44 于移動(dòng)信標(biāo)的傳感器網(wǎng)絡(luò)定位算法的設(shè)計(jì) . 45 線傳感器網(wǎng)絡(luò)仿真程序模型及程序設(shè)計(jì) . 46 位過程仿真程序設(shè)計(jì) . 51 于移動(dòng)信標(biāo)優(yōu)化路徑的定位算法性能分析 . 52 章小結(jié) . 55 結(jié)論與展望 . 56 參 考 文 獻(xiàn) . 57 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文 . 60 攻讀學(xué)位期間參加的科研項(xiàng)目 . 61 獨(dú)創(chuàng)性聲明 . 62 致 謝 . 63 . . V . . 1 . 1 . 1 . 3 . 3 . 5 . 7 . 7 . 7 . 9 . 10 . 10 . 11 . 12 . 13 . 13 . 16 . 18 . 19 . 19 . 20 . 23 . 26 . 28 . 29 of . 31 . 34 . 35 廣東工業(yè)大學(xué)碩士學(xué)位論文 . 36 . 36 . 36 . 37 . 38 . 38 . 39 of . 40 . 42 . 43 . 43 . 43 . 44 . 45 . 46 of . 51 of . 52 . 55 . 56 . 57 . 60 . 61 . 62 . 63 第一章 緒 論 1 第一章 緒 論 論文的研究背景 及 意義 究背景 與意義 無 線傳感器網(wǎng)絡(luò)綜合了傳感器、嵌入式計(jì)算、分布式信息處理和無線通信等技術(shù)，由許多相同或不同類型傳感器節(jié)點(diǎn)通過無線通信實(shí)現(xiàn)自組織，形成分布式自治網(wǎng)絡(luò)。它打破了傳統(tǒng)的點(diǎn)對(duì)點(diǎn)的數(shù)據(jù)信息交互方式，帶來了一種全新的信息獲取和處理模式 1 。 無線傳感器網(wǎng)絡(luò) (由部署在監(jiān)測(cè)區(qū)內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過無線通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的信息，并傳送給觀察者 2 。 傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在部署時(shí)往往是不可控制的，比如在大型的無線傳感器網(wǎng)絡(luò)應(yīng)用中，通常將節(jié)點(diǎn)撒播在很廣的區(qū)域里，網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)的位置是未知的，事先不能確定，但無線傳感器網(wǎng)絡(luò)的大多數(shù)應(yīng)用都需要知道網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，才可能獲取 到網(wǎng)絡(luò)中事件的發(fā)生位置和信息來源位置 。 因此， 定位是無線傳感器網(wǎng)絡(luò)的主要應(yīng)用領(lǐng)域之一，對(duì)于大多數(shù)應(yīng)用，不知道節(jié)點(diǎn)位置而感知的數(shù)據(jù)是沒有意義的。只有在傳感器節(jié)點(diǎn)自身正確定位后，才能確定傳感器節(jié)點(diǎn)監(jiān)測(cè)到的事件及信息發(fā)生的具體位置 3 。節(jié)點(diǎn)必須明確自身位置才能詳細(xì)說明“在什么位置或區(qū)域發(fā)生了特定事件”，實(shí)現(xiàn)對(duì)外部目標(biāo)的定位和追蹤。 此外，在設(shè)計(jì)路由協(xié)議時(shí)利用 節(jié)點(diǎn)位置信息還可以提高路由效率，為網(wǎng)絡(luò)提供命名空間，向 網(wǎng)絡(luò) 部署者報(bào)告 網(wǎng)絡(luò)的覆蓋質(zhì)量，實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡以及網(wǎng)絡(luò)拓?fù)涞淖耘渲?4 。因此，節(jié)點(diǎn)的定位問題已經(jīng)成為無線傳感器網(wǎng)絡(luò)的一個(gè)重要的研究方向 。 傳感器節(jié)點(diǎn)自身定位就是一種通過估計(jì)至鄰居節(jié)點(diǎn)的距離或鄰居數(shù)目，利用節(jié)點(diǎn)間的信息交換來確定各節(jié)點(diǎn)自身位置的機(jī)制。在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)能夠自主確定位置被認(rèn)為是其基本能力和系統(tǒng)的基本服務(wù)之一。對(duì)于 說，人工廣東工業(yè)大學(xué)碩士學(xué)位論文 2 部署或?yàn)樗芯W(wǎng)絡(luò)節(jié)點(diǎn)配置 置都會(huì)受到成本、功耗、拓展性等問題的限制，因此，尋求 身定位機(jī)制成為許多研究機(jī)構(gòu)和學(xué)者共同探討的問題 4 。 無線傳感器網(wǎng)絡(luò)中，根據(jù)定位過程中是否實(shí)際測(cè)量節(jié)點(diǎn)間的距離，把定位機(jī)制分為：基于測(cè)距的 (位和距離無關(guān)的 (位方法 5 。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，然后利用該實(shí)際距離來確定未知目標(biāo)節(jié)點(diǎn)位置；后者則僅利用節(jié)點(diǎn) 間距離關(guān)聯(lián)關(guān)系計(jì)算目標(biāo)節(jié)點(diǎn)位置。 量距離的具體的方法有6 ， 7 ， 8 和 9 等。 法能夠?qū)崿F(xiàn)精確定位，但由于需要在節(jié)點(diǎn)中加入 其它附加的測(cè)距的硬件設(shè)備，在實(shí)際應(yīng)用中所需的成本較高。而 位算法由于降低了對(duì)節(jié)點(diǎn)硬件的要求，引起了更多的關(guān)注，典型算法有 0 算法 ,基于 1 算法 ,基于連通性的定位算法 12 等。 目前基于距離的定位算法都是利用靜態(tài)的幾何關(guān)系來確定節(jié)點(diǎn)位置，且對(duì)信標(biāo)節(jié)點(diǎn)的布置和密度要求高，如三邊、多邊測(cè)量定位、基于角度測(cè)量定位等算法，都需要移動(dòng)節(jié)點(diǎn)至少獲得 3 個(gè)或者 3 個(gè)以上信標(biāo)節(jié)點(diǎn)提供的坐標(biāo)和距離 13 。另一種思想則是使信標(biāo)或者 信標(biāo) 運(yùn)動(dòng)起來，通過帶有 已知位置的移動(dòng) 信標(biāo)按某一規(guī)劃好的路徑或運(yùn)動(dòng)模型遍歷未知節(jié)點(diǎn)的區(qū)域，并發(fā)送定位信號(hào)，其它節(jié)點(diǎn)獲取這些信號(hào)來進(jìn)行定位計(jì)算。 動(dòng)態(tài)算法的研究是最近興起的一個(gè)熱點(diǎn)，理論還不完善，有別于靜態(tài)算法所涉及的都是固定節(jié)點(diǎn)，其主要是討論對(duì)傳感網(wǎng)中移動(dòng)節(jié)點(diǎn)定位的方法 14 ，包括待測(cè)節(jié)點(diǎn)的運(yùn)動(dòng)和信標(biāo) 節(jié)點(diǎn)的運(yùn)動(dòng)。當(dāng)然從理論上講，完全可以借鑒靜態(tài)已有的成熟算法，計(jì)算出特定時(shí)刻的節(jié)點(diǎn)位置，但因?yàn)楣?jié)點(diǎn)的運(yùn)動(dòng)，對(duì)定位算法的實(shí)時(shí)性要求較高，通常的改進(jìn)方法是加入對(duì)節(jié)點(diǎn)運(yùn)動(dòng)的預(yù)測(cè)估計(jì) 15 ，或是使定位算法能自動(dòng)適應(yīng)不同節(jié)點(diǎn)運(yùn)動(dòng)的方式，從而提高對(duì)運(yùn)動(dòng)節(jié)點(diǎn)的定位準(zhǔn)確性。 雖然節(jié)點(diǎn)的移動(dòng)性使定位過程復(fù)雜化，但是利用節(jié)點(diǎn)的移動(dòng)性可提高定位精度，減少定位代價(jià)。在 的研究中，網(wǎng)絡(luò)中有 2 個(gè)固定的 信標(biāo) 向全網(wǎng)傳送坐標(biāo)信息，其余處 于運(yùn)動(dòng)狀態(tài)的節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度進(jìn)行自身定位16 。 國(guó)內(nèi)外學(xué)者對(duì)定位問題進(jìn)行了大量研究，提出了幾種比較典型的定位算法第一章 緒 論 3 17 。但這些算法普遍存在以下局限 18 ： 依賴特殊硬件的支持； 需要特殊的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。而在無線傳感器 網(wǎng)絡(luò)中引入移動(dòng)節(jié)點(diǎn)，可以增強(qiáng)其功能。如文獻(xiàn) 19 通過將幾個(gè)未知節(jié)點(diǎn)移動(dòng)到網(wǎng)絡(luò)節(jié)點(diǎn)密度相對(duì)稀疏的區(qū)域以彌補(bǔ)節(jié)點(diǎn)密度分布不均勻的不足。文獻(xiàn) 20 提到利用移動(dòng)參考節(jié)點(diǎn)和 收信號(hào)強(qiáng)度指示 )方法對(duì)未知節(jié)點(diǎn)進(jìn)行定位，但是在現(xiàn)實(shí)環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得 術(shù)在實(shí)際應(yīng)用中仍然存在困難。尤其是 節(jié)點(diǎn)對(duì)能耗，體積等要求嚴(yán)格時(shí)，更多的時(shí)候并不能應(yīng)用這種基于測(cè)距的定位技術(shù)。 免測(cè)距的定位算法不需要測(cè)量節(jié)點(diǎn)間的距離，而是利用距離矢量路由、網(wǎng)絡(luò)連通情況或者 位等思想提出的一種分布式定位方法，無需測(cè)距，這無疑降低了組網(wǎng)成本。但由于沒有相應(yīng)的硬件測(cè)距支持，定位存在一定程序的誤差，當(dāng)網(wǎng)絡(luò)中存在障礙物時(shí)，節(jié)點(diǎn)間的歐氏距離會(huì)因?yàn)閺澢窂蕉a(chǎn)生較大的誤差，精度也相應(yīng)的降低 21 。因此如何提高這種免測(cè)距定位算法的精度也成為 了一個(gè)研究的熱點(diǎn)方向。 題來源 本課題來源于國(guó)家自然科學(xué)基金資助項(xiàng)目（編號(hào)： 60673132）；廣東省自然科學(xué)基金重點(diǎn)項(xiàng)目（編號(hào)： 07117421）。 內(nèi)外研究現(xiàn)狀 基于移動(dòng)信標(biāo)的定位算法是近年來的研究熱點(diǎn)。由于網(wǎng)絡(luò)定位算法大多依賴于信標(biāo)節(jié)點(diǎn)的密度，網(wǎng)絡(luò)的聯(lián)通性。而信標(biāo)節(jié)點(diǎn)的造價(jià)數(shù)倍甚至十幾倍于普通節(jié)點(diǎn)，所以其定位成本較高。而移動(dòng)信標(biāo)節(jié)點(diǎn)通過引入一個(gè)可在網(wǎng)絡(luò)中漫游移動(dòng)的節(jié)點(diǎn)來廣播自己的位置信息構(gòu)成虛擬信標(biāo)，從而可以降低定位成本，提高定位效率。所以移動(dòng)信標(biāo)的定位算法近來成為新的研究熱點(diǎn) ，國(guó)內(nèi)外許多學(xué)者進(jìn)行了許多的研究，基于移動(dòng)信標(biāo)的定位算法主要研究問題是如何將移動(dòng)信標(biāo)與現(xiàn)在的定位算法結(jié)合，研究構(gòu)造的虛擬信標(biāo)的動(dòng)態(tài)選擇算法及移動(dòng)信標(biāo)的移動(dòng)路徑的規(guī)劃。為此，國(guó)內(nèi)外有許多學(xué)者把移動(dòng)信標(biāo)與經(jīng)典的質(zhì)心定位算法、 位算法及 位算法等相結(jié)合來改進(jìn)這些定位算法。而質(zhì)心定位算法及廣東工業(yè)大學(xué)碩士學(xué)位論文 4 位算法因?yàn)闊o需測(cè)距有著更多的優(yōu)勢(shì)也得到更多的研究。 無需測(cè)距（ 定位算法不需要直接測(cè)量距離信息，而是根據(jù)網(wǎng)絡(luò)的連通性確定網(wǎng)絡(luò)中節(jié)點(diǎn)之間的跳數(shù)，同時(shí)根據(jù)已知位置參考節(jié)點(diǎn)的位置等 信息估計(jì)每一跳的大致距離，然后估出節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置 22 。典型的無需測(cè)距的定位算法有 位算法， 位算法、質(zhì)心定位算法、 位算法等，它們所需的網(wǎng)絡(luò)模型都是由參考節(jié)點(diǎn)和未知位置的節(jié)點(diǎn)組成 。 通過移動(dòng) 信標(biāo) ，或者說移動(dòng)信標(biāo)來對(duì)整個(gè)網(wǎng)絡(luò)的未知節(jié)點(diǎn)進(jìn)行定位的方法是最來興起的一種新的定位方法，將節(jié)點(diǎn)裝載在移動(dòng)機(jī)器人上或是進(jìn)行節(jié)點(diǎn)撒播的飛行器上，并且該節(jié)點(diǎn)裝有 其他定位裝置，這樣就構(gòu)造 了移動(dòng) 信標(biāo) 23 。它可以在移動(dòng)的過程中實(shí)時(shí)獲得其當(dāng)前的位置信息。 通過移動(dòng) 信標(biāo) 來定位的主要思想是：移動(dòng) 信標(biāo) 在“感興趣的區(qū)域內(nèi)（ of 稱 24 移動(dòng)的過程中，不斷的廣播包含其當(dāng)前位置信息的分組，在其通信半徑內(nèi)的節(jié)點(diǎn)將接收到這些廣播分組，當(dāng)未知節(jié)點(diǎn)接收到三個(gè)或者三個(gè)以上的與其距離為 R 的 位置信息時(shí)，就可以利用三邊測(cè)量法或極大似然估計(jì)法 17 計(jì)算該未知節(jié)點(diǎn)的位置。 國(guó)內(nèi)外對(duì)于移動(dòng) 信標(biāo) 的定位方法及 信標(biāo) 的移動(dòng)路徑的規(guī)劃研究處于起步階段，相關(guān)的文獻(xiàn)并不多，提出的算法也不夠成熟，文獻(xiàn) 25 和 26 提出的定位方法只需要一個(gè)可 以移動(dòng)的 信標(biāo) ，其中文 獻(xiàn) 25 利用 距技術(shù)和質(zhì)心法來計(jì)算待定位節(jié)點(diǎn)位置，文 獻(xiàn) 26 不需要復(fù)雜的測(cè)