工程碩士學(xué)位論文—無(wú)線傳感器網(wǎng)絡(luò)基于移動(dòng)信標(biāo)優(yōu)化路徑的定位算法研究

1、<p>　　廣東工業(yè)大學(xué)碩士學(xué)位論文</p><p><b>　　(工學(xué)碩士)</b></p><p>　　基于移動(dòng)信標(biāo)優(yōu)化路徑的</p><p><b>　　定位算法研究</b></p><p><b>　　謝 曉 松 </b></p><p&g

2、t;<b>　　二零一零年五月</b></p><p>　　分類號(hào)： 學(xué)校代號(hào)：11845</p><p>　　UDC： 密級(jí)： 學(xué)號(hào)：2110704294</p><p>　　廣東工業(yè)大學(xué)碩士學(xué)位論文</p><p><b>　?。ü?/p>

3、學(xué)碩士）</b></p><p>　　基于移動(dòng)信標(biāo)優(yōu)化路徑的</p><p><b>　　定位算法研究</b></p><p><b>　　謝 曉 松</b></p><p>　　指導(dǎo)教師姓名、職稱： 程良倫 教授 </p><p>　　企業(yè)導(dǎo)

4、師姓名、職稱： 無(wú) </p><p>　　專業(yè) 或 領(lǐng)域 名 稱： 控制理論與控制工程 </p><p>　　學(xué) 生 所 屬 學(xué) 院： 自動(dòng)化學(xué)院 </p><p>　　論 文 答 辯 日 期： 2010年5月 </p><p>　　Classified

5、 Index: School Code: 11845</p><p>　　UDC: Security Class: Class No.:2110704294</p><p>　　A Dissertation for Master’s Degree of </p><p>　　Guangdong Uni

6、versity of Technology</p><p>　　（Master of Engineering Science）</p><p>　　Research on Localization Algorithm Based on Mobile Beacon with Optimal path</p><p>　　Candidate: Xie Xiaosong&

7、lt;/p><p>　　Supervisor: Prof. Cheng Lianglun</p><p><b>　　May 2010</b></p><p>　　Faculty of Automation</p><p>　　Guangdong University of Technology</p><

8、;p>　　Guangzhou, Guangdong, P.R.China, 510006</p><p><b>　　摘 要</b></p><p>　　無(wú)線傳感器節(jié)點(diǎn)定位技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，是無(wú)線傳感器網(wǎng)絡(luò)大多數(shù)應(yīng)用的基礎(chǔ)。無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的大多數(shù)領(lǐng)域, 如：目標(biāo)監(jiān)測(cè)與跟蹤、路由位置信息的獲取等，都需要知道節(jié)點(diǎn)的位置信息。為此我們需要研究更為

9、有效的定位算法，降低定位成本，提高定位精度。</p><p>　　針對(duì)這種情況，本論文對(duì)基于移動(dòng)信標(biāo)優(yōu)化路徑的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)算法進(jìn)行了研究，該定位算法能夠?qū)崿F(xiàn)節(jié)點(diǎn)的高效率定位。文章在DV-Hop定位算法中引入移動(dòng)信標(biāo)節(jié)點(diǎn)，并研究信標(biāo)節(jié)點(diǎn)的動(dòng)態(tài)選擇算法及移動(dòng)路徑優(yōu)化算法。本文的主要完成的工作有：</p><p>　　1、分析歸納常用的無(wú)需測(cè)距的定位算法和基于信標(biāo)的定位算法，研究基于信標(biāo)的

10、定位算法的定位機(jī)制，研究利用移動(dòng)信標(biāo)的信息來(lái)進(jìn)行定位計(jì)算。</p><p>　　2、提出基于移動(dòng)信標(biāo)改進(jìn)的DV-Hop定位算法，該算法在DV-Hop定位算法的基礎(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)定位的精度和效率。</p><p>　　3、結(jié)

11、合基于移動(dòng)信標(biāo)改進(jìn)的DV-Hop定位算法，提出了面向無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)信標(biāo)的路徑規(guī)劃方法，把圖論引入信標(biāo)移動(dòng)路徑規(guī)劃，獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化信標(biāo)移動(dòng)路徑，提高算法的定位精度，減少算法定位過(guò)程的通信開銷，提高算法的效率。 </p><p>　　最后在OMNeT++仿真環(huán)境下，仿真基于移動(dòng)信標(biāo)的定位算法，建立包括移動(dòng)智能節(jié)點(diǎn)和普通節(jié)點(diǎn)的仿真模型，通過(guò)定位過(guò)程的通信和數(shù)據(jù)處理計(jì)算未知節(jié)點(diǎn)的位置，仿真表明，基于

12、移動(dòng)信標(biāo)優(yōu)化路徑的定位算法既改善了定位的精度，又減少了定位算法的通信開銷，提高無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位效率。</p><p>　　關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；移動(dòng)信標(biāo)；優(yōu)化路徑；OMNeT++；智能節(jié)點(diǎn) </p><p><b>　　ABSTRACT</b></p><p>　　Wireless sensor node localization is

13、 one of the key technologies for wireless sensor networks. It’s the foundation of most wireless sensor network applications, such as: target surveillance and tracking, routing and other location information acquiring, al

14、l 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.</p><p>　　In response, the paper research the nod

15、es 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 al

16、gorithm, and study the dynamic beacon node selection algorithm and moving path optimal algorithm. These major works are: </p><p>　　1. Summarizes common range-free localization algorithm and the algorithms ba

17、se on beacon, study the positioning mechanism of localization algorithms base on beacon.</p><p>　　2. Improving DV-Hop localization algorithm based on mobile beacon, the algorithm use a mobile beacon node to

18、move in the network according to a predetermined path and broadcast it’s location information that create virtual beacons. We study the weighted average hop distance algorithm and the dynamic beacon node selection algori

19、thm to reduce localization costs and complexity of distribution networks and improve accuracy and efficiency of node localization. </p><p>　　3. Combined with the improved DV-Hop localization algorithm based

20、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

21、 path of mobile beacon. These make increase of positioning accuracy of positioning algorithm and reduce communication costs, improve efficiency of the algorithm. </p><p>　　Finally, we simulate mobile beacon

22、base localization algorithm in OMNeT + + simulation environment by modeling mobile intelligent nodes and ordinary nodes in the network. The network computes the unknown node’s location through the positioning process of

23、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

24、, these improve the effic</p><p>　　Key words: WSN；Mobile anchor；Optimal path；OMNeT++；Smart node</p><p><b>　　目 錄</b></p><p><b>　　摘 要I</b></p><p>

25、;　　ABSTRACTIII</p><p><b>　　目 錄V</b></p><p>　　CONTENTSVII</p><p><b>　　第一章 緒 論1</b></p><p>　　1.1 本論文的研究背景及意義1</p><p>　　1.1.1 研究背

26、景與意義1</p><p>　　1.1.2 課題來(lái)源3</p><p>　　1.2 國(guó)內(nèi)外研究現(xiàn)狀3</p><p>　　1.3 本論文的主要研究?jī)?nèi)容與結(jié)構(gòu)5</p><p>　　第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究7</p><p>　　2.1無(wú)線傳感器網(wǎng)絡(luò)基于信標(biāo)節(jié)點(diǎn)的定位算法7</p>

27、;<p>　　2.1.1相關(guān)工作7</p><p>　　2.1.2基于信標(biāo)定位算法的優(yōu)點(diǎn)9</p><p>　　2.2無(wú)線傳感器網(wǎng)絡(luò)常用的定位方式的實(shí)現(xiàn)10</p><p>　　2.2.1極大似然估計(jì)法10</p><p>　　2.2.2三邊測(cè)量定位法11</p><p>　　2.2.3三角測(cè)量

28、定位法12</p><p>　　2.3常用的節(jié)點(diǎn)定位算法13</p><p>　　2.3.1 常用的Range-base節(jié)點(diǎn)定位算法13</p><p>　　2.3.2常用的Range-free節(jié)點(diǎn)定位算法16</p><p>　　2.4本章小結(jié)18</p><p>　　第三章 基于移動(dòng)信標(biāo)的節(jié)點(diǎn)定位算法1

29、9</p><p>　　3.1 無(wú)線傳感器網(wǎng)絡(luò)基于移動(dòng)信標(biāo)改進(jìn)的DV-Hop定位算法19</p><p>　　3.1.1 DV-Hop定位算法20</p><p>　　3.1.2移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法23</p><p>　　3.1.3 仿真分析26</p><p>　　3.2基于移動(dòng)信標(biāo)動(dòng)態(tài)選擇改進(jìn)DV-Hop

30、定位算法28</p><p>　　3.2.1 DV-Hop定位算法平均跳距離計(jì)算誤差來(lái)源分析29</p><p>　　3.2.2基于移動(dòng)信標(biāo)動(dòng)態(tài)選擇的改進(jìn)型DV-Hop定位算法過(guò)程31</p><p>　　3.2.3仿真分析34</p><p>　　3.3 本章小結(jié)35</p><p>　　第四章 無(wú)線傳感器

31、網(wǎng)絡(luò)移動(dòng)信標(biāo)的路徑優(yōu)化36</p><p>　　4.1無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)信標(biāo)的移動(dòng)模型分析36</p><p>　　4.1.1 隨機(jī)移動(dòng)RWP(Random Way Point)模型36</p><p>　　4.1.2高斯馬爾可夫移動(dòng)Gauss-Markov模型37</p><p>　　4.1.3 螺線移動(dòng)模型38</p>

32、;<p>　　4.2面向無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的移動(dòng)信標(biāo)的路徑優(yōu)化38</p><p>　　4.2.1基于圖論的信標(biāo)移動(dòng)路徑規(guī)劃方法39</p><p>　　4.2.2面向傳感器網(wǎng)絡(luò)的移動(dòng)信標(biāo)路徑規(guī)劃的仿真實(shí)現(xiàn)40</p><p>　　4.3 本章小結(jié)42</p><p>　　第五章 基于移動(dòng)信標(biāo)優(yōu)化路徑定位算法的仿真實(shí)

33、現(xiàn)43</p><p>　　5.1仿真實(shí)驗(yàn)工具和實(shí)驗(yàn)方法簡(jiǎn)述43</p><p>　　5.1.1 OMNeT++仿真實(shí)驗(yàn)平臺(tái)介紹43</p><p>　　5.1.2定位算法性能評(píng)價(jià)指標(biāo)及分析方法44</p><p>　　5.2基于移動(dòng)信標(biāo)的傳感器網(wǎng)絡(luò)定位算法的設(shè)計(jì)45</p><p>　　5.2.1無(wú)線傳感器

34、網(wǎng)絡(luò)仿真程序模型及程序設(shè)計(jì)46</p><p>　　5.2.2定位過(guò)程仿真程序設(shè)計(jì)51</p><p>　　5.3基于移動(dòng)信標(biāo)優(yōu)化路徑的定位算法性能分析52</p><p>　　5.4 本章小結(jié)55</p><p><b>　　結(jié)論與展望56</b></p><p>　　參 考 文 獻(xiàn)

35、57</p><p>　　攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文60</p><p>　　攻讀學(xué)位期間參加的科研項(xiàng)目61</p><p><b>　　獨(dú)創(chuàng)性聲明62</b></p><p><b>　　致 謝63</b></p><p><b>　　CONTENTS&

36、lt;/b></p><p>　　ABSTRACT(Chinese)I</p><p>　　ABSTRACT(English)III</p><p>　　CONTENTS(Chinese)V</p><p>　　CONTENTS(English)VII</p><p>　　Chapter 1 Introd

37、uction1</p><p>　　1.1 Research Background and Meaning of This Subject1</p><p>　　1.1.1 Research Background and Meaning1</p><p>　　1.1.2 Source of This Subject3</p><p>

38、　　1.2 Domestic and Foreign Research Status3</p><p>　　1.3 Main Content and Structure of This Subject5</p><p>　　Chapter 2 Common Nodes Localization for Sensor Network7</p><p>　　2.1

39、 Localization Algorithm Base on Beacon7</p><p>　　2.1.1 Realative work7</p><p>　　2.1.2The Advantage of Localization Algorithm Base on Beacon9</p><p>　　2.2 Implement of Common Loca

40、lization Ways10</p><p>　　2.2.1 Maximum likelihood estimation10</p><p>　　2.2.2 Trilateration Method Localization11</p><p>　　2.2.3 Triangulation Method Localization12</p>&

41、lt;p>　　2.3 Common Nodes Localization Algorithm13</p><p>　　2.3.1 Common Range-base Nodes Localization Algorithm13</p><p>　　2.3.2 Common Range-free Nodes Localization Algorithm16</p>

42、<p>　　2.4 Summary of This Chapter18</p><p>　　Chapter 3 Localization Algorithm based on Mobile Beacon19</p><p>　　3.1 Improving DV-Hop Algorithm base on Mobile Beacon19</p><p>

43、;　　3.1.1 DV-Hop Localization Algorithm20</p><p>　　3.1.2 Nodes Localization Algorithm base on Mobile Beacon23</p><p>　　3.1.3 Simulation Result26</p><p>　　3.2 Improving DV-Hop Algo

44、rithm base on Mobile Beacon Dynamic Selection28</p><p>　　3.2.1 Analysis the Error Resource of DV-Hop Averager Hop Distance29</p><p>　　3.2.2 The Process of the Improving Localization Algorithm

45、31</p><p>　　3.2.3 Simulation Result34</p><p>　　3.3 Summary of This Chapter35</p><p>　　Chapter 4 Mobile Beacon Moving Path Optimization36</p><p>　　4.1 Analysis the Mo

46、ving Model of Mobile Beacon36</p><p>　　4.1.1 RWP(Random Way Point) Moving Model36</p><p>　　4.1.2 Gauss-Markov Moving Model37</p><p>　　4.1.3 Spire Moving Model38</p><p

47、>　　4.2 Mobile Beacon Moving Path Optimization for WSNs38</p><p>　　4.2.1 Mobile Beacon Path Planning base on Graph Theory39</p><p>　　4.2.2 Simulation of the Mobile Beacon Path Planning40<

48、;/p><p>　　4.3 Summary of This Chapter42</p><p>　　Chapter 5 Simulation of Localzaition Algorithm base on Mobile Beacon43</p><p>　　5.1 Introduction of Simulation Tools and Environment

49、43</p><p>　　5.1.1 Introduction of OMNeT++43</p><p>　　5.1.2 Localization Algorithm Performance Evaluation and Analysis44</p><p>　　5.2 Localization Algorithm Design base on Mobile B

50、eacon45</p><p>　　5.2.1 Programming and Modeling Localization Algorithm46</p><p>　　5.2.2 Programming the Process of the Localization Algorithm51</p><p>　　5.3 Performance Evaluatio

51、n and Analysis of the Localization Algrithm base on Optimize Path52</p><p>　　5.4 Summary of This Chapter55</p><p>　　Conclusion and Prospect56</p><p>　　References57</p>&l

52、t;p>　　Published Papers60</p><p>　　Participant Projects61</p><p>　　Original Creative Statement62</p><p>　　Acknowledgements63</p><p><b>　　第一章 緒 論</b>&l

53、t;/p><p>　　1.1 本論文的研究背景及意義</p><p>　　1.1.1 研究背景與意義</p><p>　　無(wú)線傳感器網(wǎng)絡(luò)綜合了傳感器、嵌入式計(jì)算、分布式信息處理和無(wú)線通信等技術(shù)，由許多相同或不同類型傳感器節(jié)點(diǎn)通過(guò)無(wú)線通信實(shí)現(xiàn)自組織，形成分布式自治網(wǎng)絡(luò)。它打破了傳統(tǒng)的點(diǎn)對(duì)點(diǎn)的數(shù)據(jù)信息交互方式，帶來(lái)了一種全新的信息獲取和處理模式[1] 。</p>

54、<p>　　無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由部署在監(jiān)測(cè)區(qū)內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的信息，并傳送給觀察者[2] 。</p><p>　　傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在部署時(shí)往往是不可控制的，比如在大型的無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中，通常將節(jié)點(diǎn)撒播在很廣的區(qū)域里，網(wǎng)絡(luò)中大

55、部分的節(jié)點(diǎn)的位置是未知的，事先不能確定，但無(wú)線傳感器網(wǎng)絡(luò)的大多數(shù)應(yīng)用都需要知道網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，才可能獲取到網(wǎng)絡(luò)中事件的發(fā)生位置和信息來(lái)源位置。因此，定位是無(wú)線傳感器網(wǎng)絡(luò)的主要應(yīng)用領(lǐng)域之一，對(duì)于大多數(shù)應(yīng)用，不知道節(jié)點(diǎn)位置而感知的數(shù)據(jù)是沒(méi)有意義的。只有在傳感器節(jié)點(diǎn)自身正確定位后，才能確定傳感器節(jié)點(diǎn)監(jiān)測(cè)到的事件及信息發(fā)生的具體位置[3] 。節(jié)點(diǎn)必須明確自身位置才能詳細(xì)說(shuō)明“在什么位置或區(qū)域發(fā)生了特定事件”，實(shí)現(xiàn)對(duì)外部目標(biāo)的定位和追蹤。此

56、外，在設(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)的定位問(wèn)題已經(jīng)成為無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要的研究方向。</p><p>　　傳感器節(jié)點(diǎn)自身定位就是一種通過(guò)估計(jì)至鄰居節(jié)點(diǎn)的距離或鄰居數(shù)目，利用節(jié)點(diǎn)間的信息交換來(lái)確定各節(jié)點(diǎn)自身位置的機(jī)制。在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)能夠自主確定位置被認(rèn)為是其基本能力和系統(tǒng)的基

57、本服務(wù)之一。對(duì)于WSN來(lái)說(shuō)，人工部署或?yàn)樗芯W(wǎng)絡(luò)節(jié)點(diǎn)配置GPS裝置都會(huì)受到成本、功耗、拓展性等問(wèn)題的限制，因此，尋求WSN 自身定位機(jī)制成為許多研究機(jī)構(gòu)和學(xué)者共同探討的問(wèn)題[4] 。</p><p>　　無(wú)線傳感器網(wǎng)絡(luò)中，根據(jù)定位過(guò)程中是否實(shí)際測(cè)量節(jié)點(diǎn)間的距離，把定位機(jī)制分為：基于測(cè)距的(range-based)定位和距離無(wú)關(guān)的(range-free)定位方法[5] 。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，然后

58、利用該實(shí)際距離來(lái)確定未知目標(biāo)節(jié)點(diǎn)位置；后者則僅利用節(jié)點(diǎn)間距離關(guān)聯(lián)關(guān)系計(jì)算目標(biāo)節(jié)點(diǎn)位置。Range-based算法通過(guò)測(cè)量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位進(jìn)行定位，測(cè)量距離的具體的方法有Time of Arrival(TOA) [6] ，Time Difference of Arrival(TDOA)[7] ，Radio Signal Strength(RSSI)[8] 和Angle of Arrival(AOA)[9] 等。</p>

59、;<p>　　Range-based算法能夠?qū)崿F(xiàn)精確定位，但由于需要在節(jié)點(diǎn)中加入GPS或其它附加的測(cè)距的硬件設(shè)備，在實(shí)際應(yīng)用中所需的成本較高。而Range-free定位算法由于降低了對(duì)節(jié)點(diǎn)硬件的要求，引起了更多的關(guān)注，典型算法有DV-Hop[10] 算法,基于RSSI的DV-Hop[11] 算法,基于連通性的定位算法[12] 等。</p><p>　　目前基于距離的定位算法都是利用靜態(tài)的幾何關(guān)系來(lái)確

60、定節(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)起來(lái)，通過(guò)帶有GPS的已知位置的移動(dòng)信標(biāo)按某一規(guī)劃好的路徑或運(yùn)動(dòng)模型遍歷未知節(jié)點(diǎn)的區(qū)域，并發(fā)送定位信號(hào)，其它節(jié)點(diǎn)獲取這些信號(hào)來(lái)進(jìn)行定位計(jì)算。</p><p>　　動(dòng)態(tài)算法的研究是最近興起的一個(gè)熱點(diǎn)，理論還不完善，有別于靜

61、態(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)確性。</p><p>　　雖然節(jié)點(diǎn)的移動(dòng)性使定位過(guò)程復(fù)雜

62、化，但是利用節(jié)點(diǎn)的移動(dòng)性可提高定位精度，減少定位代價(jià)。在Bergamo等的研究中，網(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] 。</p><p>　　國(guó)內(nèi)外學(xué)者對(duì)定位問(wèn)題進(jìn)行了大量研究，提出了幾種比較典型的定位算法[17] 。但這些算法普遍存在以下局限[18] ：① 依賴特殊硬件的支持；② 需要特殊的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。而在無(wú)線傳感器網(wǎng)絡(luò)中引入移動(dòng)節(jié)點(diǎn)，可以

63、增強(qiáng)其功能。如文獻(xiàn)[19] 通過(guò)將幾個(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)和RSSI(接收信號(hào)強(qiáng)度指示)方法對(duì)未知節(jié)點(diǎn)進(jìn)行定位，但是在現(xiàn)實(shí)環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得RSSI技術(shù)在實(shí)際應(yīng)用中仍然存在困難。尤其是節(jié)點(diǎn)對(duì)能耗，體積等要求嚴(yán)格時(shí)，更多的時(shí)候并不能應(yīng)用這種基于測(cè)距的定位技術(shù)。</p><p>　　免測(cè)距的定位

64、算法不需要測(cè)量節(jié)點(diǎn)間的距離，而是利用距離矢量路由、網(wǎng)絡(luò)連通情況或者GPS定位等思想提出的一種分布式定位方法，無(wú)需測(cè)距，這無(wú)疑降低了組網(wǎng)成本。但由于沒(méi)有相應(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)方向。</p><p>　　1.1.2 課題來(lái)源</p>

65、;<p>　　本課題來(lái)源于國(guó)家自然科學(xué)基金資助項(xiàng)目（編號(hào)：60673132）；廣東省自然科學(xué)基金重點(diǎn)項(xiàng)目（編號(hào)：07117421）。</p><p>　　1.2 國(guó)內(nèi)外研究現(xiàn)狀</p><p>　　基于移動(dòng)信標(biāo)的定位算法是近年來(lái)的研究熱點(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)通過(guò)引

66、入一個(gè)可在網(wǎng)絡(luò)中漫游移動(dòng)的節(jié)點(diǎn)來(lái)廣播自己的位置信息構(gòu)成虛擬信標(biāo)，從而可以降低定位成本，提高定位效率。所以移動(dòng)信標(biāo)的定位算法近來(lái)成為新的研究熱點(diǎn)，國(guó)內(nèi)外許多學(xué)者進(jìn)行了許多的研究，基于移動(dòng)信標(biāo)的定位算法主要研究問(wèn)題是如何將移動(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ì)心定位算法、APIT定位算法及DV-Hop定位算法等相結(jié)合來(lái)改進(jìn)這些定位算法。而質(zhì)心定位算

67、法及DV-Hop定位算法因?yàn)闊o(wú)需測(cè)距有著更多的優(yōu)勢(shì)也得到更多的研究。</p><p>　　無(wú)需測(cè)距（range-free）的定位算法不需要直接測(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] 。典型的無(wú)需測(cè)距的定位算法有DV-Hop定位算法，APIT定位算法、質(zhì)心定位算法、Amorphous定位算法等，它們所需

68、的網(wǎng)絡(luò)模型都是由參考節(jié)點(diǎn)和未知位置的節(jié)點(diǎn)組成。</p><p>　　通過(guò)移動(dòng)信標(biāo)，或者說(shuō)移動(dòng)信標(biāo)來(lái)對(duì)整個(gè)網(wǎng)絡(luò)的未知節(jié)點(diǎn)進(jìn)行定位的方法是最來(lái)興起的一種新的定位方法，將節(jié)點(diǎn)裝載在移動(dòng)機(jī)器人上或是進(jìn)行節(jié)點(diǎn)撒播的飛行器上，并且該節(jié)點(diǎn)裝有GPS或其他定位裝置，這樣就構(gòu)造了移動(dòng)信標(biāo)[23] 。它可以在移動(dòng)的過(guò)程中實(shí)時(shí)獲得其當(dāng)前的位置信息。</p><p>　　通過(guò)移動(dòng)信標(biāo)來(lái)定位的主要思想是：移動(dòng)信標(biāo)在

69、“感興趣的區(qū)域內(nèi)（Region of interest，簡(jiǎn)稱ROI）”[24] 移動(dòng)的過(guò)程中，不斷的廣播包含其當(dāng)前位置信息的分組，在其通信半徑內(nèi)的節(jié)點(diǎn)將接收到這些廣播分組，當(dāng)未知節(jié)點(diǎn)接收到三個(gè)或者三個(gè)以上的與其距離為R的位置信息時(shí)，就可以利用三邊測(cè)量法或極大似然估計(jì)法[17] 計(jì)算該未知節(jié)點(diǎn)的位置。</p><p>　　國(guó)內(nèi)外對(duì)于移動(dòng)信標(biāo)的定位方法及信標(biāo)的移動(dòng)路徑的規(guī)劃研究處于起步階段，相關(guān)的文獻(xiàn)并不多，提出的算

70、法也不夠成熟，文獻(xiàn)[25] 和[26] 提出的定位方法只需要一個(gè)可以移動(dòng)的信標(biāo)，其中文獻(xiàn)[25] 利用TOA測(cè)距技術(shù)和質(zhì)心法來(lái)計(jì)算待定位節(jié)點(diǎn)位置，文獻(xiàn)[26] 不需要復(fù)雜的測(cè)距技術(shù)，而是通過(guò)信標(biāo)的不斷運(yùn)動(dòng)并利用幾何限制關(guān)系來(lái)計(jì)算待定位節(jié)點(diǎn)位置。</p><p>　　文獻(xiàn)[27] 則在DV-Hop的基礎(chǔ)上引入移動(dòng)的信標(biāo)形成一種新的M-A-DV-Hop算法，實(shí)現(xiàn)在不提高硬件成本的情況下，又能達(dá)到同樣定位效果的構(gòu)想。其

71、定位的主要思想是：當(dāng)移動(dòng)信標(biāo)在定位區(qū)域內(nèi)移動(dòng)時(shí)，移動(dòng)到若干個(gè)新位置，立即在該位置補(bǔ)充一個(gè)普通節(jié)點(diǎn)。根據(jù)信標(biāo)的即時(shí)位置信息，新位置的普通節(jié)點(diǎn)知道自身的位置。它們就等同于信標(biāo)。另外，增加普通節(jié)點(diǎn)的同時(shí)，也提高了隨機(jī)網(wǎng)絡(luò)的連通度。引入移動(dòng)信標(biāo)的優(yōu)勢(shì)是即使只有一個(gè)信標(biāo)也可以實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的定位。</p><p>　　本論文針對(duì)基于信標(biāo)的定位算法需要較高的信標(biāo)節(jié)點(diǎn)密度導(dǎo)致定位成本提高的情況，引入移動(dòng)信標(biāo)在網(wǎng)絡(luò)中移動(dòng)并廣播自

72、己的位置分組信息在網(wǎng)絡(luò)中構(gòu)成虛擬信標(biāo)的方法來(lái)定位未知節(jié)點(diǎn)，在DV-Hop定位算法的基礎(chǔ)上將移動(dòng)信標(biāo)構(gòu)成的虛擬信標(biāo)來(lái)計(jì)算平均跳距離并結(jié)合跳數(shù)信息來(lái)對(duì)未知節(jié)點(diǎn)定位，通過(guò)規(guī)劃優(yōu)化的路徑來(lái)提高定位效率。</p><p>　　對(duì)于移動(dòng)信標(biāo)的移動(dòng)路徑的規(guī)劃也是一個(gè)重要的問(wèn)題，本文進(jìn)行了初步的研究。當(dāng)采用移動(dòng)信標(biāo)在網(wǎng)絡(luò)中移動(dòng)來(lái)廣播定位信息時(shí)，移動(dòng)信標(biāo)的移動(dòng)路徑及廣播時(shí)間的選取，則很大程序上決定了網(wǎng)絡(luò)定位的能量消耗及定位的效率。

73、故研究信標(biāo)的移動(dòng)路徑規(guī)劃，使網(wǎng)絡(luò)中的節(jié)點(diǎn)以最小的代價(jià)獲得足夠多用于自身定位的信息成為一個(gè)重要的研究?jī)?nèi)容。</p><p>　　目前國(guó)內(nèi)外主要的路徑規(guī)劃均為靜態(tài)的路徑，研究如何使移動(dòng)節(jié)點(diǎn)的移動(dòng)軌跡可以盡量覆蓋網(wǎng)絡(luò)區(qū)域。這樣的算法顯然不能最大限度的節(jié)約節(jié)點(diǎn)的能耗，對(duì)于嚴(yán)格要求能源的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)來(lái)說(shuō)，必然需要更為優(yōu)化及適用于當(dāng)前網(wǎng)絡(luò)的路徑規(guī)劃算法來(lái)使節(jié)點(diǎn)移動(dòng)路徑盡可以少，減少?gòu)V播的信息來(lái)減少網(wǎng)絡(luò)節(jié)點(diǎn)的通信消耗。根據(jù)現(xiàn)

74、有的路徑規(guī)劃方法，可以把路徑的規(guī)劃分為靜態(tài)和動(dòng)態(tài)規(guī)劃，靜態(tài)的路徑規(guī)劃與網(wǎng)絡(luò)的連通狀況無(wú)關(guān)，根據(jù)需要定位的ROI區(qū)域，規(guī)劃以盡可能短的路徑覆蓋區(qū)域?yàn)槟繕?biāo)，目前靜態(tài)的路徑主要有隨機(jī)移動(dòng)模型，高斯馬爾可夫移動(dòng)模型，螺線移動(dòng)模型和SCAN移動(dòng)模型。而國(guó)外有根據(jù)網(wǎng)絡(luò)的聯(lián)通狀況來(lái)進(jìn)行路徑規(guī)劃的動(dòng)態(tài)算法，文獻(xiàn)[28] 提出幾條最優(yōu)路徑的選擇原則，本文主要進(jìn)行動(dòng)態(tài)路徑優(yōu)化研究。</p><p>　　1.3 本論文的主要研究?jī)?nèi)容與

75、結(jié)構(gòu)</p><p>　　針對(duì)無(wú)線傳感器網(wǎng)絡(luò)基于信標(biāo)節(jié)點(diǎn)的無(wú)需測(cè)距定位算法精度低，定位效率低的情況，本文提出基于移動(dòng)信標(biāo)優(yōu)化路徑的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法。研究的內(nèi)容主要如下：</p><p>　　1、分析歸納常用的無(wú)需測(cè)距的定位算法和基于信標(biāo)的定位算法，研究基于信標(biāo)的定位算法的定位機(jī)制，研究利用移動(dòng)信標(biāo)的信息來(lái)進(jìn)行定位計(jì)算。</p><p>　　2、提出基于移動(dòng)

76、信標(biāo)改進(jìn)的DV-Hop定位算法，該算法在DV-Hop定位算法的基礎(chǔ)上，利用一個(gè)移動(dòng)的信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中按預(yù)定的路徑移動(dòng)并不斷的廣播自己的位置信息，形成多個(gè)虛擬信標(biāo)，未知節(jié)點(diǎn)采用加權(quán)處理的方法計(jì)算平均跳距及其與各虛擬信標(biāo)的距離，最后利用三邊測(cè)量法計(jì)算未知節(jié)點(diǎn)的位置信息，實(shí)現(xiàn)節(jié)點(diǎn)精確定位。并研究移動(dòng)信標(biāo)的動(dòng)態(tài)選擇算法來(lái)選擇能獲得最大計(jì)算精度的移動(dòng)信標(biāo)節(jié)點(diǎn)進(jìn)行定位計(jì)算。仿真證明，相對(duì)于DV-Hop算法，基于移動(dòng)信標(biāo)改進(jìn)的DV-Hop定位算法降低

77、了定位的成本和布網(wǎng)的復(fù)雜度，提高節(jié)點(diǎn)定位的精度和效率。</p><p>　　3、結(jié)合基于移動(dòng)信標(biāo)改進(jìn)的DV-Hop定位算法，提出了基于ROI(region of interest)的移動(dòng)信標(biāo)的路徑規(guī)劃方法，并把圖論引入信標(biāo)移動(dòng)路徑規(guī)劃，獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化信標(biāo)移動(dòng)路徑，提高算法的定位精度，減少算法定位過(guò)程的通信開銷，提高算法的效率。</p><p>　　文章結(jié)構(gòu)層次安排如下：&l

78、t;/p><p>　　第1章 闡述了本課題的研究背景、研究意義及項(xiàng)目來(lái)源。通過(guò)對(duì)國(guó)內(nèi)外相關(guān)領(lǐng)域的研究現(xiàn)狀進(jìn)行探討，確立傳感器網(wǎng)絡(luò)定位算法的研究的方向。</p><p>　　第2章 介紹了信標(biāo)節(jié)點(diǎn)定位算法的相關(guān)工作，闡述了常用的基于移動(dòng)信標(biāo)的無(wú)線傳感器節(jié)點(diǎn)定位算法，并分析了這幾種常用算法的特點(diǎn)。</p><p>　　第3章 研究基于移動(dòng)信標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法，

79、將移動(dòng)信標(biāo)引入到DV-Hop定位算法中，提出了基于移動(dòng)信標(biāo)的DV-Hop定位算法和基于移動(dòng)信標(biāo)動(dòng)態(tài)選擇的改進(jìn)DV-Hop定位算法，同時(shí)分析了改進(jìn)算法在特定移動(dòng)模型下的定位精度。</p><p>　　第4章 結(jié)合基于移動(dòng)信標(biāo)改進(jìn)的DV-Hop定位算法，提出了面向無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)信標(biāo)的路徑規(guī)劃方法，把圖論引入信標(biāo)移動(dòng)路徑規(guī)劃，獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化信標(biāo)移動(dòng)路徑。</p><p>　

80、　第5章 在OMNeT++仿真平臺(tái)上進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)算法的仿真，設(shè)計(jì)移動(dòng)信標(biāo)節(jié)點(diǎn)的模型和移動(dòng)模型，并通過(guò)仿真論證優(yōu)化路徑對(duì)定位算法的影響。 </p><p>　　第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究</p><p>　　無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法的不同，分成兩種定位類型：基于信標(biāo)節(jié)點(diǎn)和不基于信標(biāo)節(jié)點(diǎn)(也有論著將其分為無(wú)錨節(jié)點(diǎn)和有錨節(jié)點(diǎn)的定位算法，信標(biāo)節(jié)點(diǎn)也可稱為錨節(jié)點(diǎn))。不基于

81、信標(biāo)節(jié)點(diǎn)的定位方法屬于相對(duì)定位，基于信標(biāo)的定位算法可以得出未知節(jié)點(diǎn)的絕對(duì)坐標(biāo)。當(dāng)前絕大多數(shù)節(jié)點(diǎn)定位算法均假設(shè)網(wǎng)絡(luò)中存在少量信標(biāo)節(jié)點(diǎn)，以實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的絕對(duì)定位。</p><p>　　2.1無(wú)線傳感器網(wǎng)絡(luò)基于信標(biāo)節(jié)點(diǎn)的定位算法</p><p><b>　　2.1.1相關(guān)工作</b></p><p>　　基于信標(biāo)節(jié)點(diǎn)的定位算法在研究集中在移動(dòng)信標(biāo)的選

82、擇、移動(dòng)路徑、定位計(jì)算方法及移動(dòng)節(jié)點(diǎn)的研究。由于信標(biāo)節(jié)點(diǎn)需要移動(dòng)，其在網(wǎng)絡(luò)中的作用更為重要，需要根據(jù)傳感器網(wǎng)絡(luò)的特點(diǎn)進(jìn)行移動(dòng)信標(biāo)節(jié)點(diǎn)的設(shè)計(jì)及無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用系統(tǒng)的研究。構(gòu)建無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)，需要考慮網(wǎng)絡(luò)在應(yīng)用中的成本、數(shù)量、通信方面存在的諸多問(wèn)題，主要需要考慮以下幾個(gè)方面：</p><p>　　1、低成本：系統(tǒng)必須是低成本，不僅從節(jié)點(diǎn)硬件、軟件考慮，而且傳感器也必須采用相對(duì)價(jià)格低的產(chǎn)品；</p&g

83、t;<p>　　2、低功耗：系統(tǒng)中采用普通AAA電池供電，所以要求網(wǎng)絡(luò)必須是低功耗的，保證網(wǎng)絡(luò)的生命周期盡量長(zhǎng)；</p><p>　　3、實(shí)時(shí)監(jiān)測(cè)：監(jiān)測(cè)信息需實(shí)時(shí)傳輸?shù)焦芾矸?wù)器，方便用戶實(shí)時(shí)查詢；</p><p>　　4、網(wǎng)關(guān)無(wú)線通信：由于監(jiān)測(cè)區(qū)域的特殊性，不一定存在有線網(wǎng)絡(luò)，例如：Internet、有線局域網(wǎng)等，故網(wǎng)關(guān)具有把采集的環(huán)境信息無(wú)線傳輸?shù)椒?wù)器的功能，不受監(jiān)測(cè)區(qū)

84、域的影響；</p><p>　　5、精度：傳感器決定了采集數(shù)據(jù)的精度，傳感器采集數(shù)據(jù)的精度可以在規(guī)定范圍內(nèi)存在一定程度的誤差；</p><p>　　6、傳感器接口靈活：系統(tǒng)根據(jù)環(huán)境參數(shù)的不同采用不相同的接口，傳感器的類型也需根據(jù)實(shí)際需要而定，因此節(jié)點(diǎn)的傳感器接口需靈活設(shè)定。</p><p>　　傳感器節(jié)點(diǎn)主要由低功耗的單片機(jī)，無(wú)線射頻模塊以及車載平臺(tái)等組成，它首先采

85、集各個(gè)模擬信號(hào)，把模擬信號(hào)轉(zhuǎn)化成數(shù)字信號(hào)，經(jīng)過(guò)單片機(jī)處理后，通過(guò)無(wú)線射頻模塊把數(shù)據(jù)傳送到匯聚節(jié)點(diǎn)。匯聚節(jié)點(diǎn)的處理器采用ARM9 S3C2410，它還包括GPRS模塊，無(wú)線射頻模塊，網(wǎng)絡(luò)接口等，它的功能主要是接收附近所有傳感器節(jié)點(diǎn)發(fā)送過(guò)來(lái)的數(shù)據(jù)，并且通過(guò)Internet或者GPRS模塊上傳到上層監(jiān)控軟件。無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)的硬件系統(tǒng)需要根據(jù)上面所述的要求建立合適的傳感器系統(tǒng)，為此設(shè)計(jì)的傳感器移動(dòng)節(jié)點(diǎn)主要由低功耗的微處理器，射頻

86、模塊，傳感器接口，電源模塊以及車載平臺(tái)5部分組成，如圖2-1所示，普通節(jié)點(diǎn)則沒(méi)有車載平臺(tái)。</p><p>　　圖2-1傳感器移動(dòng)節(jié)點(diǎn)結(jié)構(gòu)</p><p>　　Fig. 2-1 Sensor Network Mobile Nodes Structure</p><p>　　根據(jù)此模型設(shè)計(jì)制作的移動(dòng)節(jié)點(diǎn)如下圖2-2所示。節(jié)點(diǎn)采用MSP430低功耗單片機(jī)，芯片集成SPI

87、，IIC，12位A/D等標(biāo)準(zhǔn)接口，可以通過(guò)SPI接口與射頻模塊CC2420進(jìn)行連接，節(jié)點(diǎn)還設(shè)計(jì)了了標(biāo)準(zhǔn)的傳感器接口，可以通過(guò)接口連接到常用的傳感器模塊。為了實(shí)驗(yàn)方便，節(jié)點(diǎn)集成了DS18B20溫度傳感器，TSL2561光強(qiáng)度傳感器。同時(shí)，把節(jié)點(diǎn)放在車載平臺(tái)上，實(shí)現(xiàn)節(jié)點(diǎn)的移動(dòng)。</p><p>　　圖2-2傳感器網(wǎng)絡(luò)節(jié)點(diǎn)</p><p>　　Fig. 2-2 Sensor Network No

88、des</p><p>　　黎大鵬在文獻(xiàn)[29] 中研究了基于信標(biāo)節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的移動(dòng)節(jié)點(diǎn)的定位算法。對(duì)基于錨節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)進(jìn)行了研究，該系統(tǒng)能夠?qū)崿F(xiàn)移動(dòng)節(jié)點(diǎn)的高效率定位。文章分別從嵌入式硬件平臺(tái)的硬件設(shè)計(jì)，移動(dòng)節(jié)點(diǎn)定位算法，以及定位系統(tǒng)的程序設(shè)計(jì)與實(shí)現(xiàn)三方面來(lái)對(duì)該系統(tǒng)進(jìn)行研究。提出基于VWMC（Voronoi and Weight Monte Carlo Method）的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)

89、點(diǎn)定位算法，該算法在MCL（Monte Carlo Localization）算法的基礎(chǔ)上加入Voronoi圖和權(quán)值分析技術(shù)。仿真證明，相對(duì)于MCL算法，基于VWMC的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法提高了移動(dòng)節(jié)點(diǎn)定位的精度和效率。結(jié)合基于VWMC的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法以及錨節(jié)點(diǎn)動(dòng)態(tài)調(diào)整策略，提出了基于錨節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法，提高了算法對(duì)外界干擾的抵御能力。</p><p>　　2.1.2基于

90、信標(biāo)定位算法的優(yōu)點(diǎn)</p><p>　　相對(duì)定位通常是以網(wǎng)絡(luò)中部分節(jié)點(diǎn)為參考，建立整個(gè)網(wǎng)絡(luò)的相對(duì)坐標(biāo)系統(tǒng)。絕對(duì)定位可為網(wǎng)絡(luò)提供唯一的命名空間，受節(jié)點(diǎn)移動(dòng)性影響較小，有更廣泛的應(yīng)用領(lǐng)域。但研究發(fā)現(xiàn)，在相對(duì)定位的基礎(chǔ)上也能夠?qū)崿F(xiàn)部分路由協(xié)議，尤其是基于地理位置的路由(geo-routing)，而且相對(duì)定位不需要信標(biāo)節(jié)點(diǎn)。在某些無(wú)需網(wǎng)絡(luò)節(jié)點(diǎn)絕對(duì)位置的應(yīng)用中，可以采用無(wú)信標(biāo)節(jié)點(diǎn)的定位算法來(lái)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的相對(duì)定位。典型的無(wú)

91、信標(biāo)節(jié)點(diǎn)的定位算法包含SPA[30] 、SDGPS[31] 、AFL[32] 等定位算法。</p><p>　　SPA算法選擇網(wǎng)絡(luò)中密度最大處的一組節(jié)點(diǎn)作為建立網(wǎng)絡(luò)全局坐標(biāo)系統(tǒng)的參考點(diǎn)，并在其中選擇連通度最大的一個(gè)節(jié)點(diǎn)作為坐標(biāo)系統(tǒng)的原點(diǎn)。首先根據(jù)節(jié)點(diǎn)間的測(cè)距結(jié)果在各個(gè)節(jié)點(diǎn)上建立局部坐標(biāo)系統(tǒng)，通過(guò)節(jié)點(diǎn)間的信息交換與協(xié)調(diào)，以參考點(diǎn)為基準(zhǔn)通過(guò)坐標(biāo)變換逐步建立全局坐標(biāo)系統(tǒng)。SPA算法的主要缺點(diǎn)是網(wǎng)絡(luò)通信開銷太大。<

92、/p><p>　　SDGPSN算法在SPA算法的基礎(chǔ)上，提出了基于聚類的定位思想?；舅枷?網(wǎng)絡(luò)部署完后，每個(gè)傳感器節(jié)點(diǎn)開始運(yùn)行一個(gè)隨機(jī)的定時(shí)器，如果與鄰居節(jié)點(diǎn)相比，節(jié)點(diǎn)i的定時(shí)器最先到期且沒(méi)有收到任何鄰居節(jié)點(diǎn)的消息，則i升級(jí)為主節(jié)點(diǎn)，并向鄰居節(jié)點(diǎn)廣播此消息，所有接收到該消息的鄰居節(jié)點(diǎn)中止其定時(shí)器并成為該主節(jié)點(diǎn)的從節(jié)點(diǎn)。這些節(jié)點(diǎn)構(gòu)成一個(gè)以主節(jié)點(diǎn)i為坐標(biāo)原點(diǎn)的節(jié)點(diǎn)域，并隨掃A擇兩個(gè)與i相鄰的從節(jié)點(diǎn)為輔助節(jié)點(diǎn)對(duì)，構(gòu)建一個(gè)

93、局部坐標(biāo)系。節(jié)點(diǎn)域內(nèi)的所有其他從節(jié)點(diǎn)通過(guò)選擇適當(dāng)?shù)妮o助節(jié)點(diǎn)對(duì)來(lái)計(jì)算其在此局部坐標(biāo)系中的坐標(biāo)。然后相鄰的節(jié)點(diǎn)域依靠?jī)蓚€(gè)域的共同邊際節(jié)點(diǎn)的相關(guān)坐標(biāo)信息，以主節(jié)點(diǎn)ID較小的局部坐標(biāo)系為參照，進(jìn)行相鄰局部坐標(biāo)系間的坐標(biāo)轉(zhuǎn)換，直至建立一個(gè)全局坐標(biāo)系。SDGPSN算法和SPA算法相比，通信開銷明顯降低，這使得它更適于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的部署。</p><p>　　AFL算法是完全分布式的節(jié)點(diǎn)定位方法。利用AMP所有節(jié)點(diǎn)從隨

94、機(jī)初始坐標(biāo)分配開始，只利用局部距離估計(jì)和通過(guò)局部信息交換收斂到一個(gè)與距離估計(jì)一致的坐標(biāo)分配。在給定一個(gè)未知坐標(biāo)的節(jié)點(diǎn)集合和一種節(jié)點(diǎn)可以估測(cè)它到其鄰居節(jié)點(diǎn)距離機(jī)制的條件下，通過(guò)局部節(jié)點(diǎn)間的通信決定每個(gè)節(jié)點(diǎn)的位置坐標(biāo)。</p><p>　　基于信標(biāo)節(jié)點(diǎn)的定位算法依賴于某些已知坐標(biāo)位置的節(jié)點(diǎn)。這種定位算法需要預(yù)先定位信標(biāo)節(jié)點(diǎn)，否則無(wú)法正常運(yùn)行，另外為了減小定位誤差，信標(biāo)節(jié)點(diǎn)的數(shù)目還須足夠多。基于信標(biāo)節(jié)點(diǎn)的定位算法的一個(gè)

95、重要特征是定位精度取決于信標(biāo)點(diǎn)密度。為了解決基于信標(biāo)節(jié)點(diǎn)的定位算法對(duì)信標(biāo)節(jié)點(diǎn)的密度的依賴，近年來(lái)許多學(xué)者進(jìn)行了移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法的研究，通過(guò)在引入移動(dòng)信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中按預(yù)定軌跡漫游并廣播自己的位置分組在構(gòu)成虛擬信標(biāo)節(jié)點(diǎn)，可以大大減少信標(biāo)節(jié)點(diǎn)的投入。因?yàn)樾艠?biāo)節(jié)點(diǎn)造價(jià)往往比普通節(jié)點(diǎn)高，在許多固定的傳感器網(wǎng)絡(luò)中，定位成功后信標(biāo)節(jié)點(diǎn)將轉(zhuǎn)為普通節(jié)點(diǎn)使用，極大的浪費(fèi)了資源。所以基于移動(dòng)信標(biāo)節(jié)點(diǎn)的定位算法成為近年來(lái)研究的一個(gè)熱點(diǎn)。</p>

96、;<p>　　本章首先介紹無(wú)線傳感器網(wǎng)絡(luò)常用的定位方式及其實(shí)現(xiàn)，然后介紹常用的基于測(cè)距和無(wú)需測(cè)距的定位算法，并根據(jù)這些算法的特點(diǎn)，分析其優(yōu)缺點(diǎn)，為下一章提出新的基于移動(dòng)信標(biāo)的定位算法奠定了理論基礎(chǔ)。</p><p>　　2.2無(wú)線傳感器網(wǎng)絡(luò)常用的定位方式的實(shí)現(xiàn)</p><p>　　2.2.1極大似然估計(jì)法</p><p>　　傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)

97、中節(jié)點(diǎn)有可能和多于3個(gè)的不同信標(biāo)相連。因此可以使用更多的節(jié)點(diǎn)以獲得冗余信息來(lái)計(jì)算未知節(jié)點(diǎn)的位置。極大似然估計(jì)多邊測(cè)量[33] 就采用了上面的方法，已知n個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(X1,Y1)，(X2,Y2)，(X3,Y3)，….，(Xn ,Yn )，它們到未知節(jié)點(diǎn) D 的距離分別為dl，d2，d3，….，dn，假設(shè)節(jié)點(diǎn) D的坐標(biāo)為(X，Y)。那么，存在下列公式： </p><p><b>　　∶</b&

98、gt;</p><p><b>　　(2.1)</b></p><p>　　最后，使用標(biāo)準(zhǔn)的最小均方差估計(jì)方法可以得到未知節(jié)點(diǎn) D 的坐標(biāo)。</p><p>　　2.2.2三邊測(cè)量定位法</p><p>　　三邊測(cè)量法是通過(guò) RSSI值得出未知節(jié)點(diǎn)到 3 個(gè)信標(biāo)的距離，通過(guò)這3個(gè)距離值計(jì)算出未知節(jié)點(diǎn)的位置。如下圖2-1所

99、示，當(dāng)節(jié)點(diǎn)P1，P2，P3未知節(jié)點(diǎn)P發(fā)出的定位信號(hào)時(shí)，根據(jù) RSSI值，可以得到 P1到 P，P2到 P，P3到 P的距離d1，d2，d3；分別以 P1，P2，P3為圓心，d1，d2，d3為半徑作圓，通過(guò)這 3個(gè)圓相交區(qū)域定出未知節(jié)點(diǎn)的位置。</p><p>　　圖2-3三邊測(cè)量法原理</p><p>　　Fig. 2-3 Trilateration Method Principle<

100、;/p><p>　　但是在真實(shí)環(huán)境下三邊測(cè)量法存在巨大的缺陷，如圖3-6所示，實(shí)際上測(cè)量得到的3個(gè)距離RP1，RP2，RP3存在著誤差，導(dǎo)致以RP1，RP2，RP3為半徑建立的3個(gè)圓并不是相交于一點(diǎn)，而是相交于一個(gè)區(qū)域。這樣建立起來(lái)的等式方程組沒(méi)有解，根本無(wú)法實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的定位。有些文章提出了以區(qū)域的質(zhì)點(diǎn)作為節(jié)點(diǎn)的位置，這種方法也不好，節(jié)點(diǎn)定位的誤差會(huì)隨著相交區(qū)域的增大而大大地提高。</p><p&

101、gt;　　總的來(lái)說(shuō)，針對(duì)節(jié)點(diǎn)的定位算法都是在理想的仿真環(huán)境下進(jìn)行研究的，當(dāng)節(jié)點(diǎn)處于存在干擾或者移動(dòng)的情況下，這些算法或不能夠?qū)崿F(xiàn)節(jié)點(diǎn)精確的定位，或算法的計(jì)算量太大。</p><p>　　2.2.3三角測(cè)量定位法</p><p>　　三角測(cè)量法原理如圖2-2所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya),(xb,yb)，(xc,yc)，節(jié)點(diǎn)D相對(duì)于節(jié)點(diǎn)A、B、C的角度分別為：ADB，

102、ADC，BDC，假設(shè)節(jié)點(diǎn)D的坐標(biāo)為(x，y)，D為圖2-2中三個(gè)圓的交點(diǎn)。</p><p>　　圖2-4三角測(cè)量法示意圖</p><p>　　Fig. 2-4 Triangulation Method Principle</p><p>　　對(duì)于節(jié)點(diǎn)A，C和角ADC，如果弧段AC在ABC內(nèi)，那么能夠唯一確定一個(gè)圓，設(shè)圓心為，半徑為r1，那么，并存在下列公式：<

103、/p><p><b>　　(2.2)</b></p><p>　　由式(2.2)能夠確定圓心O1點(diǎn)的坐標(biāo)和半徑r1。同理對(duì)A，B，ADB和B，C，BDC分別確定相應(yīng)的圓心、半徑r2、圓心和半徑r3。最后根據(jù)已知的r1，，r2，，r3，，采用三邊測(cè)量法確定D點(diǎn)坐標(biāo)。</p><p>　　2.3常用的節(jié)點(diǎn)定位算法</p><p>

104、;　　2.3.1 常用的Range-base節(jié)點(diǎn)定位算法</p><p>　　根據(jù)定位過(guò)程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，定位算法可分為：基于距離(Range-Based)的定位算法和距離無(wú)關(guān)(Range-Free)的定位算法[34] 。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，然后利用該實(shí)際距離來(lái)確定未知目標(biāo)節(jié)點(diǎn)位置；后者則僅利用節(jié)點(diǎn)間距離關(guān)聯(lián)關(guān)系計(jì)算目標(biāo)節(jié)點(diǎn)位置[35] 。</p><p>

105、　　1、基于信號(hào)強(qiáng)度（RSSI）定位</p><p>　　RSSI(Received Signal Strength Indicator)是接收到的信號(hào)強(qiáng)度指示器，是一種利用信號(hào)衰減推測(cè)距離的測(cè)距技術(shù)[36]。目前很多定位算法都是利用RSSI技術(shù)實(shí)現(xiàn)的。目前，WSN網(wǎng)絡(luò)中無(wú)線通信芯片主要有兩種：CC1000和CC2420。CC1000的工作頻帶為315MHz,868MHz,915MHz，數(shù)據(jù)傳送速率可達(dá)72.8K

106、bit/s，適用于跳頻協(xié)議。CC2420工作頻帶在2.4GHz-2.4835GHz，采用的是O-QPSK調(diào)制方式，數(shù)據(jù)速率在250kbit/s，具有較高的抗干擾能力。對(duì)于CC1000通信芯片，RSSI值是一個(gè)10位的寄存器值，而對(duì)于CC2420，該值卻是一個(gè)8位的寄存器值。它是通過(guò)A/D轉(zhuǎn)換器轉(zhuǎn)換而來(lái)的，芯片不同，RSSI的轉(zhuǎn)換方式也是不同的。若芯片是CC1000：</p><p><b>　?。?.3

107、）</b></p><p><b>　?。?.4）</b></p><p><b>　?。?.5）</b></p><p><b>　?。?.6）</b></p><p>　　其中，RSSI是寄存器值，也就是節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度值，VRSSI是A/D轉(zhuǎn)換前的RSSI

108、電壓值，單位為(V)；Vbat為電源電壓，該值為一個(gè)常數(shù)值3V；Pcurrent是當(dāng)前節(jié)點(diǎn)的發(fā)射功率，單位為dBm；P0為當(dāng)節(jié)點(diǎn)與源節(jié)點(diǎn)足夠遠(yuǎn)時(shí)接收到的功率值，一般來(lái)說(shuō)P0取-80dBm；P為功率衰減值。（2.6）式是由（2.3），（2.4），（2.5）聯(lián)合而得的，表明在當(dāng)前發(fā)射功率下，發(fā)送到最遠(yuǎn)的距離處，接收到的最大RSSI值，若超過(guò)該值的一定范圍，認(rèn)為節(jié)點(diǎn)間通信不合理，丟棄該數(shù)據(jù)包。若芯片為CC2420：</p>&l

109、t;p><b>　?。?.7）</b></p><p><b>　?。?.8）</b></p><p>　　其中，RSSI是一個(gè)8位的寄存器值；RSSI_VAL為轉(zhuǎn)換前RSSI功率值，單位為dBm，RSSI_OFFSET是一個(gè)常數(shù)，約為-45dBm。本文采用的射頻芯片是CC2420，它相對(duì)于CC1000，使用的范圍更廣。同時(shí)為了更好的利用R