谢晓松–无线传感器网络基于移动信标优化路径的定位算法研究,文献翻译,毕业论文

广东工业大学硕士学位论文

(工学硕士)基于移动信标优化路径的

定位算法研究

谢 晓 松

二零一零年五月分类号： 学校代号：11845

UDC： 密级： 学号：2110704294
广东工业大学硕士学位论文

（工学硕士）基于移动信标优化路径的

定位算法研究
谢 晓 松指导教师姓名、职称： 程良伦 教授

企业导师姓名、职称： 无

专业 或 领域 名 称： 控制理论与控制工程

学 生 所 属 学 院： 自动化学院

论 文 答 辩 日 期： 2010年5月 Classified Index: School Code: 11845

UDC: Security Class: Class No.:2110704294
A Dissertation for Master’s Degree of

Guangdong University of Technology

（Master of Engineering Science）
Research on Localization Algorithm Based on Mobile Beacon with Optimal path
Candidate: Xie Xiaosong

Supervisor: Prof. Cheng LianglunMay 2010

Faculty of Automation

Guangdong University of Technology

Guangzhou, Guangdong, P.R.China, 510006
摘 要

无线传感器节点定位技术是无线传感器网络的关键技术之一，是无线传感器网络大多数应用的基础。无线传感器网络应用的大多数领域, 如：目标监测与跟踪、路由位置信息的获取等，都需要知道节点的位置信息。为此我们需要研究更为有效的定位算法，降低定位成本，提高定位精度。

针对这种情况，本论文对基于移动信标优化路径的无线传感器网络节点算法进行了研究，该定位算法能够实现节点的高效率定位。文章在DV-Hop定位算法中引入移动信标节点，并研究信标节点的动态选择算法及移动路径优化算法。本文的主要完成的工作有：

1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。

2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，研究平均跳距离的加权算法和信标节点的动态选择算法，降低定位的成本和布网的复杂度，提高节点定位的精度和效率。

3、结合基于移动信标改进的DV-Hop定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。

最后在OMNeT++仿真环境下，仿真基于移动信标的定位算法，建立包括移动智能节点和普通节点的仿真模型，通过定位过程的通信和数据处理计算未知节点的位置，仿真表明，基于移动信标优化路径的定位算法既改善了定位的精度，又减少了定位算法的通信开销，提高无线传感器网络节点定位效率。

关键词：无线传感器网络；移动信标；优化路径；OMNeT++；智能节点
ABSTRACT

Wireless sensor node localization is 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, 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 it’s 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 node’s 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目 录

TOC \o "1-3" \u 摘 要 262392800 I

ABSTRACT 262392801 III

目 录 262392802 V

CONTENTS 262392803 VII

第一章 绪 论 262392804 1

1.1 本论文的研究背景及意义 262392805 1

1.1.1 研究背景与意义 262392806 1

1.1.2 课题来源 262392807 3

1.2 国内外研究现状 262392808 3

1.3 本论文的主要研究内容与结构 262392809 5

第二章 传感器网络常用节点定位算法相关研究 262392810 7

2.1无线传感器网络基于信标节点的定位算法 262392811 7

2.1.1相关工作 262392812 7

2.1.2基于信标定位算法的优点 262392813 9

2.2无线传感器网络常用的定位方式的实现 262392814 10

2.2.1极大似然估计法 262392815 10

2.2.2三边测量定位法 262392816 11

2.2.3三角测量定位法 262392817 12

2.3常用的节点定位算法 262392818 13

2.3.1 常用的Range-base节点定位算法 262392819 13

2.3.2常用的Range-free节点定位算法 262392820 16

2.4本章小结 262392821 18

第三章 基于移动信标的节点定位算法 262392822 19

3.1 无线传感器网络基于移动信标改进的DV-Hop定位算法 262392823 19

3.1.1 DV-Hop定位算法 262392824 20

3.1.2移动信标节点定位算法 262392825 23

3.1.3 仿真分析 262392826 26

3.2基于移动信标动态选择改进DV-Hop定位算法 262392827 28

3.2.1 DV-Hop定位算法平均跳距离计算误差来源分析 262392828 29

3.2.2基于移动信标动态选择的改进型DV-Hop定位算法过程 262392829 31

3.2.3仿真分析 262392830 34

3.3 本章小结 262392831 35

第四章 无线传感器网络移动信标的路径优化 262392832 36

4.1无线传感器网络移动信标的移动模型分析 262392833 36

4.1.1 随机移动RWP(Random Way Point)模型 262392834 36

4.1.2高斯马尔可夫移动Gauss-Markov模型 262392835 37

4.1.3 螺线移动模型 262392836 38

4.2面向无线传感器网络节点定位的移动信标的路径优化 262392837 38

4.2.1基于图论的信标移动路径规划方法 262392838 39

4.2.2面向传感器网络的移动信标路径规划的仿真实现 262392839 40

4.3 本章小结 262392840 42

第五章 基于移动信标优化路径定位算法的仿真实现 262392841 43

5.1仿真实验工具和实验方法简述 262392842 43

5.1.1 OMNeT++仿真实验平台介绍 262392843 43

5.1.2定位算法性能评价指标及分析方法 262392844 44

5.2基于移动信标的传感器网络定位算法的设计 262392845 45

5.2.1无线传感器网络仿真程序模型及程序设计 262392846 46

5.2.2定位过程仿真程序设计 262392847 51

5.3基于移动信标优化路径的定位算法性能分析 262392848 52

5.4 本章小结 262392849 55

结论与展望 262392850 56

参 考 文 献 262392851 57

攻读学位期间发表的学术论文 262392852 60

攻读学位期间参加的科研项目 262392853 61

独创性声明 262392854 62

致 谢 262392855 63CONTENTS

TOC \o "1-3" \u ABSTRACT(Chinese) 262128408 I

ABSTRACT(English) 262128409 III

CONTENTS(Chinese) 262128410 V

CONTENTS(English) 262128411 VII

Chapter 1 Introduction 262128412 1

1.1 Research Background and Meaning of This Subject 262128413 1

1.1.1 Research Background and Meaning 262128414 1

1.1.2 Source of This Subject 262128415 3

1.2 Domestic and Foreign Research Status 262128416 3

1.3 Main Content and Structure of This Subject 262128417 5

Chapter 2 Common Nodes Localization for Sensor Network 262128418 7

2.1 Localization Algorithm Base on Beacon 262128419 7

2.1.1 Realative work 262128420 7

2.1.2The Advantage of Localization Algorithm Base on Beacon 262128421 9

2.2 Implement of Common Localization Ways 262128422 10

2.2.1 Maximum likelihood estimation 262128423 10

2.2.2 Trilateration Method Localization 262128424 11

2.2.3 Triangulation Method Localization 262128425 12

2.3 Common Nodes Localization Algorithm 262128426 13

2.3.1 Common Range-base Nodes Localization Algorithm 262128427 13

2.3.2 Common Range-free Nodes Localization Algorithm 262128428 16

2.4 Summary of This Chapter 262128429 18

Chapter 3 Localization Algorithm based on Mobile Beacon 262128430 19

3.1 Improving DV-Hop Algorithm base on Mobile Beacon 262128431 19

3.1.1 DV-Hop Localization Algorithm 262128432 20

3.1.2 Nodes Localization Algorithm base on Mobile Beacon 262128433 23

3.1.3 Simulation Result 262128434 26

3.2 Improving DV-Hop Algorithm base on Mobile Beacon Dynamic Selection 262128435 28

3.2.1 Analysis the Error Resource of DV-Hop Averager Hop Distance 262128436 29

3.2.2 The Process of the Improving Localization Algorithm 262128437 31

3.2.3 Simulation Result 262128438 34

3.3 Summary of This Chapter 262128439 35

Chapter 4 Mobile Beacon Moving Path Optimization 262128440 36

4.1 Analysis the Moving Model of Mobile Beacon 262128441 36

4.1.1 RWP(Random Way Point) Moving Model 262128442 36

4.1.2 Gauss-Markov Moving Model 262128443 37

4.1.3 Spire Moving Model 262128444 38

4.2 Mobile Beacon Moving Path Optimization for WSNs 262128445 38

4.2.1 Mobile Beacon Path Planning base on Graph Theory 262128446 39

4.2.2 Simulation of the Mobile Beacon Path Planning 262128447 40

4.3 Summary of This Chapter 262128448 42

Chapter 5 Simulation of Localzaition Algorithm base on Mobile Beacon 262128449 43

5.1 Introduction of Simulation Tools and Environment 262128450 43

5.1.1 Introduction of OMNeT++ 262128451 43

5.1.2 Localization Algorithm Performance Evaluation and Analysis 262128452 44

5.2 Localization Algorithm Design base on Mobile Beacon 262128453 45

5.2.1 Programming and Modeling Localization Algorithm 262128454 46

5.2.2 Programming the Process of the Localization Algorithm 262128455 51

5.3 Performance Evaluation and Analysis of the Localization Algrithm base on Optimize Path 262128456 52

5.4 Summary of This Chapter 262128457 55

Conclusion and Prospect 262128458 56

References 262128459 57

Published Papers 262128460 60

Participant Projects 262128461 61

Original Creative Statement 262128462 62

Acknowledgements 262128463 63

TOC \o "1-3" \z \u 第一章 绪 论

1.1 本论文的研究背景及意义

1.1.1 研究背景与意义

无线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息获取和处理模式 REF _Ref259216077 \r \* MERGEFORMAT [1] 。

无线传感器网络(Wireless Sensor Networks，WSN)是由部署在监测区内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域内感知对象的信息，并传送给观察者 REF _Ref259472381 \r \* MERGEFORMAT [2] 。

传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络应用中，通常将节点撒播在很广的区域里，网络中大部分的节点的位置是未知的，事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才可能获取到网络中事件的发生位置和信息来源位置。因此，定位是无线传感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件及信息发生的具体位置 REF _Ref259472389 \r \* MERGEFORMAT [3] 。节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。此外，在设计路由协议时利用节点位置信息还可以提高路由效率，为网络提供命名空间，向网络部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置 REF _Ref259472395 \r \* MERGEFORMAT [4] 。因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向。

传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自主确定位置被认为是其基本能力和系统的基本服务之一。对于WSN来说，人工部署或为所有网络节点配置GPS装置都会受到成本、功耗、拓展性等问题的限制，因此，寻求WSN 自身定位机制成为许多研究机构和学者共同探讨的问题 REF _Ref259472395 \r \* MERGEFORMAT [4] 。

无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机制分为：基于测距的(range-based)定位和距离无关的(range-free)定位方法 REF _Ref259472439 \r \* MERGEFORMAT [5] 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置。Range-based算法通过测量相邻节点间的实际距离或方位进行定位，测量距离的具体的方法有Time of Arrival(TOA) REF _Ref259472448 \r \* MERGEFORMAT [6] ，Time Difference of Arrival(TDOA) REF _Ref259472454 \r \* MERGEFORMAT [7] ，Radio Signal Strength(RSSI) REF _Ref259472477 \r \* MERGEFORMAT [8] 和Angle of Arrival(AOA) REF _Ref259472488 \r \* MERGEFORMAT [9] 等。

Range-based算法能够实现精确定位，但由于需要在节点中加入GPS或其它附加的测距的硬件设备，在实际应用中所需的成本较高。而Range-free定位算法由于降低了对节点硬件的要求，引起了更多的关注，典型算法有DV-Hop REF _Ref259472496 \r \* MERGEFORMAT [10] 算法,基于RSSI的DV-Hop REF _Ref259472506 \r \* MERGEFORMAT [11] 算法,基于连通性的定位算法 REF _Ref259472522 \r \* MERGEFORMAT [12] 等。

目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法，都需要移动节点至少获得3个或者3个以上信标节点提供的坐标和距离 REF _Ref259472529 \r \* MERGEFORMAT [13] 。另一种思想则是使信标或者信标运动起来，通过带有GPS的已知位置的移动信标按某一规划好的路径或运动模型遍历未知节点的区域，并发送定位信号，其它节点获取这些信号来进行定位计算。

动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法 REF _Ref259472574 \r \* MERGEFORMAT [14] ，包括待测节点的运动和信标节点的运动。当然从理论上讲，完全可以借鉴静态已有的成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时性要求较高，通常的改进方法是加入对节点运动的预测估计 REF _Ref259473204 \r \* MERGEFORMAT [15] ，或是使定位算法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。

虽然节点的移动性使定位过程复杂化，但是利用节点的移动性可提高定位精度，减少定位代价。在Bergamo等的研究中，网络中有2个固定的信标向全网传送坐标信息，其余处于运动状态的节点根据接收到的信号强度进行自身定位 REF _Ref259473218 \r \* MERGEFORMAT [16] 。

国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法 REF _Ref259473226 \r \* MERGEFORMAT [17] 。但这些算法普遍存在以下局限 REF _Ref259473383 \r \* MERGEFORMAT [18] ：① 依赖特殊硬件的支持；② 需要特殊的网络拓扑结构。而在无线传感器网络中引入移动节点，可以增强其功能。如文献 REF _Ref259473391 \r \* MERGEFORMAT [19] 通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度分布不均匀的不足。文献 REF _Ref259473404 \r \* MERGEFORMAT [20] 提到利用移动参考节点和RSSI(接收信号强度指示)方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得RSSI技术在实际应用中仍然存在困难。尤其是节点对能耗，体积等要求严格时，更多的时候并不能应用这种基于测距的定位技术。

免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络连通情况或者GPS定位等思想提出的一种分布式定位方法，无需测距，这无疑降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差，当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差，精度也相应的降低 REF _Ref259473418 \r \* MERGEFORMAT [21] 。因此如何提高这种免测距定位算法的精度也成为了一个研究的热点方向。

1.1.2 课题来源

本课题来源于国家自然科学基金资助项目（编号：60673132）；广东省自然科学基金重点项目（编号：07117421）。

1.2 国内外研究现状

基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖于信标节点的密度，网络的联通性。而信标节点的造价数倍甚至十几倍于普通节点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游移动的节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效率。所以移动信标的定位算法近来成为新的研究热点，国内外许多学者进行了许多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规划。为此，国内外有许多学者把移动信标与经典的质心定位算法、APIT定位算法及DV-Hop定位算法等相结合来改进这些定位算法。而质心定位算法及DV-Hop定位算法因为无需测距有着更多的优势也得到更多的研究。

无需测距（range-free）的定位算法不需要直接测量距离信息，而是根据网络的连通性确定网络中节点之间的跳数，同时根据已知位置参考节点的位置等信息估计每一跳的大致距离，然后估出节点在网络中的位置 REF _Ref259473434 \r \* MERGEFORMAT [22] 。典型的无需测距的定位算法有DV-Hop定位算法，APIT定位算法、质心定位算法、Amorphous定位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成。

通过移动信标，或者说移动信标来对整个网络的未知节点进行定位的方法是最来兴起的一种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的飞行器上，并且该节点装有GPS或其他定位装置，这样就构造了移动信标 REF _Ref259473444 \r \* MERGEFORMAT [23] 。它可以在移动的过程中实时获得其当前的位置信息。

通过移动信标来定位的主要思想是：移动信标在“感兴趣的区域内（Region of interest，简称ROI）” REF _Ref259473451 \r \* MERGEFORMAT [24] 移动的过程中，不断的广播包含其当前位置信息的分组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者三个以上的与其距离为R的位置信息时，就可以利用三边测量法或极大似然估计法 REF _Ref259473226 \r \* MERGEFORMAT [17] 计算该未知节点的位置。

国内外对于移动信标的定位方法及信标的移动路径的规划研究处于起步阶段，相关的文献并不多，提出的算法也不够成熟，文献 REF _Ref259473468 \r \* MERGEFORMAT [25] 和 REF _Ref259473476 \r \* MERGEFORMAT [26] 提出的定位方法只需要一个可以移动的信标，其中文献 REF _Ref259473468 \r \* MERGEFORMAT [25] 利用TOA测距技术和质心法来计算待定位节点位置，文献 REF _Ref259473476 \r \* MERGEFORMAT [26] 不需要复杂的测距技术，而是通过信标的不断运动并利用几何限制关系来计算待定位节点位置。

文献 REF _Ref259473502 \r \* MERGEFORMAT [27] 则在DV-Hop的基础上引入移动的信标形成一种新的M-A-DV-Hop算法，实现在不提高硬件成本的情况下，又能达到同样定位效果的构想。其定位的主要思想是：当移动信标在定位区域内移动时，移动到若干个新位置，立即在该位置补充一个普通节点。根据信标的即时位置信息，新位置的普通节点知道自身的位置。它们就等同于信标。另外，增加普通节点的同时，也提高了随机网络的连通度。引入移动信标的优势是即使只有一个信标也可以实现对未知节点的定位。

本论文针对基于信标的定位算法需要较高的信标节点密度导致定位成本提高的情况，引入移动信标在网络中移动并广播自己的位置分组信息在网络中构成虚拟信标的方法来定位未知节点，在DV-Hop定位算法的基础上将移动信标构成的虚拟信标来计算平均跳距离并结合跳数信息来对未知节点定位，通过规划优化的路径来提高定位效率。

对于移动信标的移动路径的规划也是一个重要的问题，本文进行了初步的研究。当采用移动信标在网络中移动来广播定位信息时，移动信标的移动路径及广播时间的选取，则很大程序上决定了网络定位的能量消耗及定位的效率。故研究信标的移动路径规划，使网络中的节点以最小的代价获得足够多用于自身定位的信息成为一个重要的研究内容。

目前国内外主要的路径规划均为静态的路径，研究如何使移动节点的移动轨迹可以尽量覆盖网络区域。这样的算法显然不能最大限度的节约节点的能耗，对于严格要求能源的传感器网络节点来说，必然需要更为优化及适用于当前网络的路径规划算法来使节点移动路径尽可以少，减少广播的信息来减少网络节点的通信消耗。根据现有的路径规划方法，可以把路径的规划分为静态和动态规划，静态的路径规划与网络的连通状况无关，根据需要定位的ROI区域，规划以尽可能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可夫移动模型，螺线移动模型和SCAN移动模型。而国外有根据网络的联通状况来进行路径规划的动态算法，文献 REF _Ref262071650 \r [28] 提出几条最优路径的选择原则，本文主要进行动态路径优化研究。

1.3 本论文的主要研究内容与结构

针对无线传感器网络基于信标节点的无需测距定位算法精度低，定位效率低的情况，本文提出基于移动信标优化路径的无线传感器网络节点定位算法。研究的内容主要如下：

1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。

2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，未知节点采用加权处理的方法计算平均跳距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实现节点精确定位。并研究移动信标的动态选择算法来选择能获得最大计算精度的移动信标节点进行定位计算。仿真证明，相对于DV-Hop算法，基于移动信标改进的DV-Hop定位算法降低了定位的成本和布网的复杂度，提高节点定位的精度和效率。

3、结合基于移动信标改进的DV-Hop定位算法，提出了基于ROI(region of interest)的移动信标的路径规划方法，并把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。

文章结构层次安排如下：

第1章 阐述了本课题的研究背景、研究意义及项目来源。通过对国内外相关领域的研究现状进行探讨，确立传感器网络定位算法的研究的方向。

第2章 介绍了信标节点定位算法的相关工作，阐述了常用的基于移动信标的无线传感器节点定位算法，并分析了这几种常用算法的特点。

第3章 研究基于移动信标的无线传感器网络节点的定位算法，将移动信标引入到DV-Hop定位算法中，提出了基于移动信标的DV-Hop定位算法和基于移动信标动态选择的改进DV-Hop定位算法，同时分析了改进算法在特定移动模型下的定位精度。

第4章 结合基于移动信标改进的DV-Hop定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径。

第5章 在OMNeT++仿真平台上进行无线传感器网络节点算法的仿真，设计移动信标节点的模型和移动模型，并通过仿真论证优化路径对定位算法的影响。
第二章 传感器网络常用节点定位算法相关研究

无线传感器网络节点定位方法的不同，分成两种定位类型：基于信标节点和不基于信标节点(也有论著将其分为无锚节点和有锚节点的定位算法，信标节点也可称为锚节点)。不基于信标节点的定位方法属于相对定位，基于信标的定位算法可以得出未知节点的绝对坐标。当前绝大多数节点定位算法均假设网络中存在少量信标节点，以实现整个网络的绝对定位。

2.1无线传感器网络基于信标节点的定位算法

2.1.1相关工作

基于信标节点的定位算法在研究集中在移动信标的选择、移动路径、定位计算方法及移动节点的研究。由于信标节点需要移动，其在网络中的作用更为重要，需要根据传感器网络的特点进行移动信标节点的设计及无线传感器网络的应用系统的研究。构建无线传感器网络应用系统，需要考虑网络在应用中的成本、数量、通信方面存在的诸多问题，主要需要考虑以下几个方面：

1、低成本：系统必须是低成本，不仅从节点硬件、软件考虑，而且传感器也必须采用相对价格低的产品；

2、低功耗：系统中采用普通AAA电池供电，所以要求网络必须是低功耗的，保证网络的生命周期尽量长；

3、实时监测：监测信息需实时传输到管理服务器，方便用户实时查询；

4、网关无线通信：由于监测区域的特殊性，不一定存在有线网络，例如：Internet、有线局域网等，故网关具有把采集的环境信息无线传输到服务器的功能，不受监测区域的影响；

5、精度：传感器决定了采集数据的精度，传感器采集数据的精度可以在规定范围内存在一定程度的误差；

6、传感器接口灵活：系统根据环境参数的不同采用不相同的接口，传感器的类型也需根据实际需要而定，因此节点的传感器接口需灵活设定。

传感器节点主要由低功耗的单片机，无线射频模块以及车载平台等组成，它首先采集各个模拟信号，把模拟信号转化成数字信号，经过单片机处理后，通过无线射频模块把数据传送到汇聚节点。汇聚节点的处理器采用ARM9 S3C2410，它还包括GPRS模块，无线射频模块，网络接口等，它的功能主要是接收附近所有传感器节点发送过来的数据，并且通过Internet或者GPRS模块上传到上层监控软件。无线传感器网络移动节点定位系统的硬件系统需要根据上面所述的要求建立合适的传感器系统，为此设计的传感器移动节点主要由低功耗的微处理器，射频模块，传感器接口，电源模块以及车载平台5部分组成，如图2-1所示，普通节点则没有车载平台。

EMBED Visio.Drawing.11

图2- SEQ 图2- \* ARABIC 1传感器移动节点结构

Fig. 2- SEQ Fig._2- \* ARABIC 1 Sensor Network Mobile Nodes Structure

根据此模型设计制作的移动节点如下图2-2所示。节点采用MSP430低功耗单片机，芯片集成SPI，IIC，12位A/D等标准接口，可以通过SPI接口与射频模块CC2420进行连接，节点还设计了了标准的传感器接口，可以通过接口连接到常用的传感器模块。为了实验方便，节点集成了DS18B20温度传感器，TSL2561光强度传感器。同时，把节点放在车载平台上，实现节点的移动。
图2- SEQ 图2- \* ARABIC 2传感器网络节点

Fig. 2- SEQ Fig._2- \* ARABIC 2 Sensor Network Nodes

黎大鹏在文献 REF _Ref262128072 \r [29] 中研究了基于信标节点动态调整的移动节点的定位算法。对基于锚节点动态调整的传感器网络移动节点定位系统进行了研究，该系统能够实现移动节点的高效率定位。文章分别从嵌入式硬件平台的硬件设计，移动节点定位算法，以及定位系统的程序设计与实现三方面来对该系统进行研究。提出基于VWMC（Voronoi and Weight Monte Carlo Method）的传感器网络移动节点定位算法，该算法在MCL（Monte Carlo Localization）算法的基础上加入Voronoi图和权值分析技术。仿真证明，相对于MCL算法，基于VWMC的传感器网络移动节点定位算法提高了移动节点定位的精度和效率。结合基于VWMC的传感器网络移动节点定位算法以及锚节点动态调整策略，提出了基于锚节点动态调整的传感器网络移动节点定位算法，提高了算法对外界干扰的抵御能力。

2.1.2基于信标定位算法的优点

相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可为网络提供唯一的命名空间，受节点移动性影响较小，有更广泛的应用领域。但研究发现，在相对定位的基础上也能够实现部分路由协议，尤其是基于地理位置的路由(geo-routing)，而且相对定位不需要信标节点。在某些无需网络节点绝对位置的应用中，可以采用无信标节点的定位算法来实现整个网络的相对定位。典型的无信标节点的定位算法包含SPA REF _Ref259517082 \r \* MERGEFORMAT [30] 、SDGPS REF _Ref259517093 \r \* MERGEFORMAT [31] 、AFL REF _Ref259517102 \r \* MERGEFORMAT [32] 等定位算法。

SPA算法选择网络中密度最大处的一组节点作为建立网络全局坐标系统的参考点，并在其中选择连通度最大的一个节点作为坐标系统的原点。首先根据节点间的测距结果在各个节点上建立局部坐标系统，通过节点间的信息交换与协调，以参考点为基准通过坐标变换逐步建立全局坐标系统。SPA算法的主要缺点是网络通信开销太大。

SDGPSN算法在SPA算法的基础上，提出了基于聚类的定位思想。基本思想:网络部署完后，每个传感器节点开始运行一个随机的定时器，如果与邻居节点相比，节点i的定时器最先到期且没有收到任何邻居节点的消息，则i升级为主节点，并向邻居节点广播此消息，所有接收到该消息的邻居节点中止其定时器并成为该主节点的从节点。这些节点构成一个以主节点i为坐标原点的节点域，并随扫A择两个与i相邻的从节点为辅助节点对，构建一个局部坐标系。节点域内的所有其他从节点通过选择适当的辅助节点对来计算其在此局部坐标系中的坐标。然后相邻的节点域依靠两个域的共同边际节点的相关坐标信息，以主节点ID较小的局部坐标系为参照，进行相邻局部坐标系间的坐标转换，直至建立一个全局坐标系。SDGPSN算法和SPA算法相比，通信开销明显降低，这使得它更适于大规模无线传感器网络的部署。

AFL算法是完全分布式的节点定位方法。利用AMP所有节点从随机初始坐标分配开始，只利用局部距离估计和通过局部信息交换收敛到一个与距离估计一致的坐标分配。在给定一个未知坐标的节点集合和一种节点可以估测它到其邻居节点距离机制的条件下，通过局部节点间的通信决定每个节点的位置坐标。

基于信标节点的定位算法依赖于某些已知坐标位置的节点。这种定位算法需要预先定位信标节点，否则无法正常运行，另外为了减小定位误差，信标节点的数目还须足够多。基于信标节点的定位算法的一个重要特征是定位精度取决于信标点密度。为了解决基于信标节点的定位算法对信标节点的密度的依赖，近年来许多学者进行了移动信标节点定位算法的研究，通过在引入移动信标节点在网络中按预定轨迹漫游并广播自己的位置分组在构成虚拟信标节点，可以大大减少信标节点的投入。因为信标节点造价往往比普通节点高，在许多固定的传感器网络中，定位成功后信标节点将转为普通节点使用，极大的浪费了资源。所以基于移动信标节点的定位算法成为近年来研究的一个热点。

本章首先介绍无线传感器网络常用的定位方式及其实现，然后介绍常用的基于测距和无需测距的定位算法，并根据这些算法的特点，分析其优缺点，为下一章提出新的基于移动信标的定位算法奠定了理论基础。

2.2无线传感器网络常用的定位方式的实现

2.2.1极大似然估计法

传感器网络移动节点定位系统中节点有可能和多于3个的不同信标相连。因此可以使用更多的节点以获得冗余信息来计算未知节点的位置。极大似然估计多边测量 REF _Ref260326214 \r \* MERGEFORMAT [33] 就采用了上面的方法，已知n个节点的坐标分别为(X1,Y1)，(X2,Y2)，(X3,Y3)，….，(Xn ,Yn )，它们到未知节点 D 的距离分别为dl，d2，d3，….，dn，假设节点 D的坐标为(X，Y)。那么，存在下列公式：

EMBED Equation.3

EMBED Equation.3

∶

EMBED Equation.3 (2.1)

最后，使用标准的最小均方差估计方法可以得到未知节点 D 的坐标。

2.2.2三边测量定位法

三边测量法是通过 RSSI值得出未知节点到 3 个信标的距离，通过这3个距离值计算出未知节点的位置。如下图2-1所示，当节点P1，P2，P3未知节点P发出的定位信号时，根据 RSSI值，可以得到 P1到 P，P2到 P，P3到 P的距离d1，d2，d3；分别以 P1，P2，P3为圆心，d1，d2，d3为半径作圆，通过这 3个圆相交区域定出未知节点的位置。

EMBED Visio.Drawing.11

图2- SEQ 图2- \* ARABIC 3三边测量法原理

Fig. 2- SEQ Fig._2- \* ARABIC 3 Trilateration Method Principle

但是在真实环境下三边测量法存在巨大的缺陷，如图3-6所示，实际上测量得到的3个距离RP1，RP2，RP3存在着误差，导致以RP1，RP2，RP3为半径建立的3个圆并不是相交于一点，而是相交于一个区域。这样建立起来的等式方程组没有解，根本无法实现对节点的定位。有些文章提出了以区域的质点作为节点的位置，这种方法也不好，节点定位的误差会随着相交区域的增大而大大地提高。

总的来说，针对节点的定位算法都是在理想的仿真环境下进行研究的，当节点处于存在干扰或者移动的情况下，这些算法或不能够实现节点精确的定位，或算法的计算量太大。

2.2.3三角测量定位法

三角测量法原理如图2-2所示，已知A、B、C三个节点的坐标分别为(xa,ya),(xb,yb)，(xc,yc)，节点D相对于节点A、B、C的角度分别为： EMBED Equation.DSMT4 ADB， EMBED Equation.DSMT4 ADC， EMBED Equation.DSMT4 BDC，假设节点D的坐标为(x，y)，D为图2-2中三个圆的交点。
图2- SEQ 图2- \* ARABIC 4三角测量法示意图

Fig. 2- SEQ Fig._2- \* ARABIC 4 Triangulation Method Principle

对于节点A，C和角 EMBED Equation.DSMT4 ADC，如果弧段AC在 EMBED Equation.DSMT4 ABC内，那么能够唯一确定一个圆，设圆心为 EMBED Equation.DSMT4 ，半径为r1，那么 EMBED Equation.DSMT4 ，并存在下列公式：

EMBED Equation.DSMT4 (2.2)

由式(2.2)能够确定圆心O1点的坐标和半径r1。同理对A，B， EMBED Equation.DSMT4 ADB和B，C， EMBED Equation.DSMT4 BDC分别确定相应的圆心 EMBED Equation.DSMT4 、半径r2、圆心 EMBED Equation.DSMT4 和半径r3。最后根据已知的r1， EMBED Equation.DSMT4 ，r2， EMBED Equation.DSMT4 ，r3， EMBED Equation.DSMT4 ，采用三边测量法确定D点坐标。

2.3常用的节点定位算法

2.3.1 常用的Range-base节点定位算法

根据定位过程中是否测量实际节点间的距离，定位算法可分为：基于距离(Range-Based)的定位算法和距离无关(Range-Free)的定位算法 REF _Ref259517686 \r \* MERGEFORMAT [34] 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置 REF _Ref259479173 \r \* MERGEFORMAT [35] 。

1、基于信号强度（RSSI）定位

RSSI(Received Signal Strength Indicator)是接收到的信号强度指示器，是一种利用信号衰减推测距离的测距技术[36]。目前很多定位算法都是利用RSSI技术实现的。目前，WSN网络中无线通信芯片主要有两种：CC1000和CC2420。CC1000的工作频带为315MHz,868MHz,915MHz，数据传送速率可达72.8Kbit/s，适用于跳频协议。CC2420工作频带在2.4GHz-2.4835GHz，采用的是O-QPSK调制方式，数据速率在250kbit/s，具有较高的抗干扰能力。对于CC1000通信芯片，RSSI值是一个10位的寄存器值，而对于CC2420，该值却是一个8位的寄存器值。它是通过A/D转换器转换而来的，芯片不同，RSSI的转换方式也是不同的。若芯片是CC1000：

EMBED Equation.3 （2.3）

EMBED Equation.3 （2.4）

EMBED Equation.3 （2.5）

EMBED Equation.3 （2.6）

其中，RSSI是寄存器值，也就是节点接收到的信号强度值，VRSSI是A/D转换前的RSSI电压值，单位为(V)；Vbat为电源电压，该值为一个常数值3V；Pcurrent是当前节点的发射功率，单位为dBm；P0为当节点与源节点足够远时接收到的功率值，一般来说P0取-80dBm；P为功率衰减值。（2.6）式是由（2.3），（2.4），（2.5）联合而得的，表明在当前发射功率下，发送到最远的距离处，接收到的最大RSSI值，若超过该值的一定范围，认为节点间通信不合理，丢弃该数据包。若芯片为CC2420：

EMBED Equation.3 （2.7）

EMBED Equation.3 （2.8）

其中，RSSI是一个8位的寄存器值；RSSI_VAL为转换前RSSI功率值，单位为dBm，RSSI_OFFSET是一个常数，约为-45dBm。本文采用的射频芯片是CC2420，它相对于CC1000，使用的范围更广。同时为了更好的利用RSSI值估计节点与邻节点之间的距离，需要建立一个RSSI模型。最常用的RSSI有三种：最优模型、线性模型和理论模型。最优模型如式(2.9)，根据给定RSSI的距离值r，对具有相同RSSI测量值的观测数据来计算实际距离的平均值，这个模型可以很好地从收集到的数据中统计出有效的距离估计值。

最简单的RSSI模型就是线性模型，它使用一对参数a和ｂ估计节点之间的距离，如式(2.10)。其中r是RSSI测距值。因为信号强度和距离之间并不是简单的线性关系，因此，线性模型和理论模型之间还有一定的误差。

RSSI的理论模型是根据信号强度随着距离的变化成对数衰减的原理，如式（2.11）,其中r0是1m距离处对应的RSSI测距值，a是信号的衰减率，理论值为2。

EMBED Equation.3 （2.9）

EMBED Equation.3 （2.10）

EMBED Equation.3 （2.11）

大多数情况下，RSSI的测距采用自由空间模型，它是理论模型的一种。因为RSSI在一个真实环境下的信号随着距离的增大而减少。收发器之间各种各样的阻碍影响能量的损失，从而直接影响接收器接收信号的对数分布[37]。所以距离d与接收到的信号强度的关系可以表示为：

EMBED Equation.3 （2.12）

其中P(d0)为参考距离d0接收到的信号。对于所有d0=1米的室内环境下以及距离的信号可以由自由空间路径损耗方程得到，路径的损耗指数n由环境变量和周围的结果决定。根据高斯分布功率表达式，得到的接收功率为：

EMBED Equation.3 （2.13）

其中εdB为零均值及以δ2, N(0,δ2)变化的高斯分布随机变量。基于这个模型，距离估算为：

EMBED Equation.3 （2.14）

总的来说，仅依靠RSSI方法的定位系统，应用在实时系统定位时非常方便。但由于受到地板、墙壁和人体等各种物体等障碍物的阻拦，电磁波会存在着反射及衍射，使得 RSSI值随机变化较大，因此无法准确判断某一个距离对应的RSSI值。理论信号强度与实际信号强度曲线对比如下图2-3所示：

EMBED Visio.Drawing.11

图2- SEQ 图2- \* ARABIC 5 RSSI自由空间模型

Fig. 2- SEQ Fig._2- \* ARABIC 5 RSSI Free Space Model

2、基于TDOA定位

在基于到达时间差(TDOA)的定位机制中，发射节点同时发射两种传播速度不同的信号，接收节点根据两种信号到达的时间差及已知的信号传播速度，计算节点间距。

EMBED Visio.Drawing.11

图2- SEQ 图2- \* ARABIC 6基于TDOA定位

Fig. 2- SEQ Fig._2- \* ARABIC 6 Located Based on TDOA

如图3-3所示，该技术的测距精度可达到厘米级，但前提是需要精确的时钟，同时使用超声波测量需要额外的硬件，增加了成本，而且容易受到非视距误差的影响。计算公式如式（2.15）所示：

D=V1*V2*(T2-T1)/(V1-V2) （2.15）

2.3.2常用的Range-free节点定位算法

无需测距的定位技术不需要额外的硬件，与基于测距的定位算法相比，具有成本低、功耗小、抗测量噪声能力强等优势特点，并能获得一定的定位精度，因此有许多学者进行了大量的研究。距离无关的定位算法通过对节点间的距离进行估计或者确定包含未知节点的可能区域，来确定未知节点的位置 REF _Ref259479571 \r \* MERGEFORMAT [36] 。目前，已有许多的研究者们提出众多的无需测距的定位算法。。本节列出了常用的三种无需测距(Range-free)的定位算法：DV-Hop定位算法，Euclidean定位算法，APIT定位算法。并分析了这三种算法的特点。

1、DV-Hop定位算法

美国路特葛斯大学的Dragos Niculescu等利用距离矢量路由和GPS定位的思想提出了DV-Hop定位算法。该算法由三个阶段组成：首先，使网络中所有节点获得距信标的跳数；其次，当获得其它信标位置和相隔跳距后，信标计算网络平均每跳距离，赋予其生存期，然后将这个带有生存期的校正值在网络广播。未知节点将记录接收到的第一个校正值，转发给邻居节点。这个策略可以保证绝大多数节点从最近的信标接收平均每跳距离。最后未知节点根据记录的跳数，计算到信标的跳段距离。

DV-Hop算法能够计算出离信标很远未知节点的位置。而且它不需要额外信息，然而，误差根据路由的弯曲程度的不同而不同。由于一个未知节点只能通过一条路径得到跳数，所以它需要通过每跳平均距离来计算自身的位置，这样导致计算出位置的误差量很大。假设一个DV-Hop模型，如下图2-5所示：

EMBED Visio.Drawing.11

图2- SEQ 图2- \* ARABIC 7 DV-Hop 算法模型

Fig. 2- SEQ Fig._2- \* ARABIC 7 DV-Hop Algorithm Model

其中L1,L2,L3为信标。A是一个未知节点，L1,L2,L3之间的距离已知，分别为30，30和40。A点到L1点为15，跳帧的数量为1，A点到L2,L3的跳帧的数量为3，平均每跳为10。

首先，信标广播包括位置信息以及开始位为1的标志的数据包，当信号传输到另一个节点，跳帧的数量自动加一，所以每个节点将可以计算出离信标的距离，信标接收到另一信标的信号后可以计算平均每跳的距离。在图2-5中，L1、L2、L3的平均每跳距离如下：

L1: (30+30)/ (4+4) =7.5 （2.16）

L2: (30+40)/ (4+6) =7 （2.17）

L3: (30+40)/ (4+6) =7 （2.18）

在计算出平均距离后，信标将把它广播到其他节点，未知节点得到平均每跳距离后计算出到信标的距离。那就是说，L1、L2、L3将广播7.5、7、7三个距离的值。然后因为A到L1只有一跳，所以A收到的平均每跳的距离是7.5。然后它计算出到L1、L2、L3三点的距离，AL1=7.5、AL2=AL3=7*3=21。然后根据3边测量法来对节点A定位。

实际上的距离是AL1=15。但是使用DV-Hop估算出来的是7.5，误差很大。所以经过三边测量法后，计算出的位置和实际上的位置差别很大 REF _Ref259472506 \r \* MERGEFORMAT [11] 。

2、Euclidean定位算法

MIT的Radhika Nagpal等提出了一种定位算法(Amorphous Localization Algorithm)。该算法采用与DV-Hop类似的方法获得距信标的跳数。节点收集邻居节点的跳数，计算关于某个信标局部跳数的平均值，如(2.19)式，式中hi表示节点i与信标之间的跳数，hj表示邻居节点j与这个信标之间的跳数，nbsr(i)表示节点的邻居节点集合。

EMBED Equation.3 （2.19）

与DV-Hop不同的是，它假设网络平均连通度nlocal已知，使用Kleinrock and Slivers Formula在网络部署前离线计算平均每跳距离，如（2.20）式，式中r表示节点的通信半径，nlocal表示网络平均连通度，即网络中节点的平均邻居节点数。

HopSize EMBED Equation.3 （2.20）

当某未知节点获得与至少3个非直线排列的信标间的距离后，应用多边测量法或极大似然法可计算出自身位置。

3、APIT定位算法

APIT算法的理论基础是最佳三角形内点测试法PIT REF _Ref259472439 \r \* MERGEFORMAT [5] 。PIT测试原理是假设存在一个方向，未知节点沿此方向移动会同时远离或接近三个信标,那么未知节点位于三个信标构成的三角形外部；否则，未知节点位于三角形内。如图2-6所示。

EMBED Visio.Drawing.11

图2- SEQ 图2- \* ARABIC 8 APIT定位算法

Fig. 2- SEQ Fig._2- \* ARABIC 8 APIT Location Algorithm

近似的三角形内点测试利用网络中相对较高的节点密度来模拟节点的移动，利用无线信号的传播特性来判断是否远离或靠近信标，通常在给定方向上，一个节点距离另一个节点越远，接收到信号的强度越弱。邻居节点通过交换各自接收到信号的强度判断距离某一信标的远近，从而模仿PIT中的节点移动。

2.4本章小结

本章主要介绍常用的无需测距的定位算法，介绍了这些算法解决定位误差问题的方法，及其还存在的问题，大多无需测距的定位算法的定位精度依赖于信标节点的密度及网络的连通状况。这些算法的优缺点为基于移动信标优化路径的传感器网络节点定位算法的提出提供良好的基础。第三章 基于移动信标的节点定位算法

本章介绍无线传感器网络改进的DV-Hop定位算法主要包括两个方面：基于移动信标改进的DV-Hop定位算法，以及基于移动信标动态选择的改进DV-Hop定位算法。基于移动信标改进的DV-Hop定位算法主要在DV-Hop定位算法中引进移动信标节点，通过在网络中按预定的轨迹漫游并广播自己的位置信息，通过在几种不同的移动模型中比较其定位精度，可见在更为合理的移动模型下可以提高定位精度，降低了定位的网络成本，提高了定位效率。基于移动信标动态选择的改进DV-Hop定位算法在信标计算网络平均跳距离时采用动态选择算法，获得的计算结果摒弃了导致误差的因素，使网络平均跳距离更接近网络的真实情况。解决传感器网络移动节点定位精度低，定位效率低等问题。

3.1 无线传感器网络基于移动信标改进的DV-Hop定位算法

无线传感器网络节点定位算法的精度多依赖于信标节点的密度，但信标节点成本高，约为普通节点的100倍以上，为了降低定位的成本，提出了一种基于移动信标和DV-Hop的无线传感器网络节点定位算法(MBWDV-Hop)。该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，未知节点记录到每个虚拟信标的跳数，并采用加权处理的方法计算平均跳距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实现节点精确定位。由于只采用一个移动信标，降低了定位的成本和布网的复杂度。最后通过仿真证明此算法可以提高定位精度，降低定位成本，提高了定位的效率。

无线传感器网络由大量部署在监控区域内的传感器节点组成，各节点通过无线通信的方式形成一个多跳自组织网络，协作感知、采集和处理自然界的各种相关的监控信息 REF _Ref259480127 \r \* MERGEFORMAT [37] 。在许多情况下，无线传感器网络中的节点需要知道自身的物理位置。比如，在跟踪目标和检测突发事件中。通常无线传感器节点都被随机地布置在不同的区域中，由于传感器节点受成本，能量和体积的限制，随机布放的节点无法预先知道自身的位置，他们只能根据其它已知位置的节点，按照某种定位的机制来确定自身的位置。

针对无线传感器网络节点的定位，很多学者作了深入的研究。提出了许多的定位机制和算法。根据是否需要测距，定位算法可以分为基于测距的和无需测距的，基于测距的定位算法依赖于硬件条件，在自然环境中，还会受到各种不确定因素的干扰 REF _Ref259480202 \r \* MERGEFORMAT [38] 。无需测距的定位算法主要有质心算法、DV-Hop算法，Amorphous算法、APIT算法等。无需测距的定位算法定位误差较测距的算法要大些，但可以满足大多的工程应用需求，是目前大家普遍重点关注的定位机制 REF _Ref259479571 \r \* MERGEFORMAT [36] 。同时也有许多学者研究了大量的方法来提高无需测距算法的精度，但也导致了无需测距算法复杂度和能量开销的增大。

针对这种情况，本文提出了一种基于移动信标的传感器网络节点定位算法，减少无线传感器网络定位的成本和复杂度，并且提高了定位精度。

该算法在DV-Hop定位算法的基础上，利用一个带有GPS定位装置的移动信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，未知节点记录到每个虚拟信标的跳数，并将移动信标广播的平均跳距离通过加权处理来重新计算适用于其所在区域的网络平均跳距离，再与跳数相乘得出其与各虚拟信标的距离，最后利用改进的三边测量法计算其位置信息，实现节点精确定位。由于只采用一个移动信标，不需要在网络中布置其它的信标节点，降低了定位的成本及组网的复杂度。

最后通过仿真证明此算法可以提高定位精度，减少算法的计算量，提高了定位的效率。

3.1.1 DV-Hop定位算法

1、DV-Hop算法分析

Niculescu D等人提出的DV-Hop定位算法不需要直接测量节点间的距离，该算法具有方法简单，定位精度高等优点，它是利用距离矢量路由和GPS定位思想提出的一系列分布式定位方法之一 REF _Ref259472496 \r \* MERGEFORMAT [10] 。该算法的基本思想是将未知节点到信标节点之间的距离用网络中节点平均每跳距离和到信标节点间的跳数的乘积来计算，再使用三边测量法来得出节点的位置信息。

DV-Hop(Distance Vector-Hop)定位机制非常类似于传统网络中的距离向量路由机制。距离向量定位机制分为以下三个阶段 REF _Ref259479571 \r \* MERGEFORMAT [36] ：

第一阶段：未知节点首先计算与信标节点的最小跳数。信标节点向邻居节点广播自身位置信息的分组，其中包括跳数字段，初始化为1。接收节点记录具有到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳数的分组。然后将跳数值加1，并转发给邻居节点。通过这个方法，网络中的所有节点能够记录下到每个信标节点的最小跳数。

第二阶段：计算未知节点与信标节点的实际跳段距离。每个信标节点根据第一个阶段中记录的其它信标节点的位置信息和相距跳数，利用式(3.l)估算平均每跳的实际距离：

EMBED Equation.DSMT4 (3.1)

其中(xi+yi)、(xj+yj)是信标节点i、j的坐标，hj是信标节点i与j(j≠i)之间的跳段数。然后，信标节点将计算的平均每跳距离用带有生存期字段的分组广播至网络中，未知节点仅记录接收到的第一个平均每跳距离，并转发给邻居节点。未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个信标节点的跳段距离。

第三阶段：未知节点利用第二阶段中记录的到各个信标节点的跳段距离，利用三边测量法或极大似然估计法计算自身坐标。

EMBED Visio.Drawing.11

图3- SEQ 图3- \* ARABIC 1 DV-Hop定位算法举例

Fig.3- SEQ Fig.3- \* ARABIC 1 DV-Hop localization algorithm

2、 DV-Hop定位算法误差分析

1)、 DV-Hop定位算法的假设

在DV-Hop定位算法中，未知节点在通信范围内获得的信标节点数量不多，但通过多跳传播可以获得通信范围外的多个信标节点的估计距离，利用大量的信息获得该节点的位置，在网络平均连通度为8，信标比例为10%时，算法的定位误差大约是节点射频通信距离的1/3左右 REF _Ref259472496 \r \* MERGEFORMAT [10] 。算法有如下的假设：

(1)、网络中每个传感器节点都以相同的固定的通信距离r与其邻居节点通信；

(2)、传感器节点的通信距离r影响定位精度，只有r大小适中才能达到较优的定位精度；

(3)、监测区域中定位精度依赖于网络连通度和信标节点比例。

对于一些环境下的传感器网络，通过人工部署大量位置已知的信标节点是不实际的，而在网络中布置一定比例的带有GPS的信标节点则会提高网络的定位成本。

2)、 DV-Hop定位算法的信标节点比例分析

在传感器网络中，假设某未知节点的坐标记为(xn, yn)，实际的坐标记为(Xn, Yn)，两个位置的距离为：

d= EMBED Equation.DSMT4 (3.2)

平均定位误差的定义与节点的无线传输范围有关 REF _Ref260326770 \r \* MERGEFORMAT [39] ,为：

EMBED Equation.DSMT4 (3.3)

建立实验的仿真环境来分析DV-Hop定位算法的性能，主要分析不同的信标比例对定位精度的影响。在Matlab平台上建立实验仿真环境，在一个边长为50m的正方形区域中分布有100个未知节点，射频通信距离为10m。分析当网络中信标节点个数从3个到10个时的定位误差，如下图3-2所示。

从图中可知，信标节点的比例与定位误差成反正，信标节点越多，平均定位误差和均方差越小。所以为了提高定位的准确性，需要增加信标节点。
EMBED Visio.Drawing.11

图3- SEQ 图3- \* ARABIC 2信标节点个数对定位误差的影响

Fig.3- SEQ Fig.3- \* ARABIC 2 beacon nodes number affecting

3.1.2移动信标节点定位算法

从以上分析可知，为了提高定位精度，需要增加信标节点，但信标节点造价高。为了提高定位精度，降低布网复杂度，本文提出一种基于移动信标的定位方法。带有定位装置的信标节点装载在可移动的平台或移动机器人上，就构造了一个移动信标，移动信标在一定规律的移动过程中，可实时获取自身位置，并周期性的广播自身的位置信息，以帮助未知节点进行定位。

1、信标节点移动模型

移动信标节点采用什么样的方式移动才能尽可能的遍历整个网络，这个本身就是一个研究的热点，网络中传感器节点本身是随机散布的，节点位置本身信息是未知的，为了使这些节点全部进行定位，需要设计出一种运动模型，使移动信标的运动轨迹能在尽少的时间内遍历网络，发送足够的定位信息给未知节点以完成定位算法。目前应用于无线传感器网络的移动模型有S型、RWP(Random Way Point)模型和Gauss-Markov模型等。这些模型是自组织网络中广泛应用的模型，RWP模型对信标的硬件要求小，路径的随机性大，并且随着运动速度逐渐减小，运动轨迹出现在网络中心区域的概率偏大。S模型则对硬件的要求相对较高。

为此本文选择Gauss-Markov运动模型，该模型可以覆盖网络的大部分区域，相对于RWP模型，可以避免运动轨迹的突变和边缘地带概率减少的缺点 REF _Ref259519260 \r \* MERGEFORMAT [40] ，对硬件的要求也不高，其模型表示如下：

EMBED Equation.DSMT4 (3.4)

EMBED Equation.DSMT4 (3.5)

v(k)和d(k)表示运动时刻k移动信标的速度和方向。a是方向随机调节参数，取值为0到1(0<=a<=1)，vmean, dmean为平均速度和平均运动方向, EMBED Equation.DSMT4 ， EMBED Equation.DSMT4 代表高斯随机变量。移动的下一时刻的速度和方向从当前的速度和方向求出：

EMBED Equation.DSMT4 (3.6)

EMBED Equation.DSMT4 (3.7)

信标节点按照Gauss-Markov模型计算每个时刻的运动速度和方向，并由定位装置获取当前运动位置的坐标信息，将其广播到网络中。因为信标节点要周期性的广播坐标信息，还要接收网络中未知节点广播回来的跳数累加的广播分组，故在Gauss-Markov模型中，设置一个计时器，计时周期为信标节点广播坐标的周期，每当计时器时间到，移动暂停，广播当前位置信息，并接收各未知节点返回的跳数广播分组，记录在列表中，再继续移动。

2、基于移动信标节点算法的定位过程

信标节点在网络中移动，周期性地将位置信息广播到网络中，广播的信息格式包括当前运动到第几个点，当前位置坐标，网络跳数(初始化为0)，在移动信标节点通信范围的未知节点都接收到该位置的信标节点的定位数据包。每个节点接收到定位信息后，将其中的跳数值加1后继续广播。每个节点接收到多个邻居节点的广播值都与本身记有的值比较，如果小于自身记有的跳数值，则丢弃这个广播分组。

这一过程与DV-Hop定位算法相似，不同的是，未知节点判断接收到的是第几号位的信标节点广播，如果为第一个就暂不广播，直到接收到第二号位的信标广播时，再把一号位的定位信息包广播出去，并保存接收到的二号位广播，等待下一位的广播后再发送，以此类推。广播定位信息的过程分为以下几步：

步骤1：移动信标在第一个位置取得当前位置信息，封装位置信息广播信息包{LIDi, xi, yi, HOPs}，LIDi表示当前是第几号位置的广播包，xi，yi表示当前位置坐标，HOPs为经历的跳数，初始为0；

步骤2：移动信标在第一个位置的通信范围内所有邻居节点接收到定位信息包，接收到信息包的节点将其与本身的数据包进行比较，取跳数较小的一项，并丢弃较大的，将跳数一项加1，记录下这个跳数值，等待下一个定位信息包；

步骤3：移动信标移动到下一个位置，将位置信息加1并广播这个一新位置的定位信息包，同时接收各节点发回的广播信息，取与前一位置最小跳数的分组，将两位置的距离除以跳数计算出平均每跳距离(Di)并广播到网络中；

步骤4：重复步骤3直到位置号达到预先设定的阈值K，K根据所需的虚拟信标密度而定，如果网络中有N个未知节点，根据精度要求得出虚拟信标比例q，则 EMBED Equation.DSMT4 ；

步骤5：节点根据接收到的各个虚拟信标的平均跳距离按权值进行校正，并根据记录的跳数计算出到各个虚拟信标的距离，挑选出最优的虚拟信标节点距离信息，按优化的三边测量法计算自己的位置。

3、加权值法计算平均跳距离

为了更准确的计算出估计的平均跳距离值，本文引入权值的概念，运用加权值对平均跳距离进行校正是基于网络并非完全的均匀分布，各个节点接收到多个虚拟节点的平均跳距离值，越是靠近未知节点其平均跳距离值更能反映出未知节点所在的网络区域的情况，对其平均跳距离的影响也越大，所以应当占有更大的权值，这样比只计算平均值更接近真实值，计算出来的未知节点位置更精确。

为了方便表达，我们假设网络中的未知节点Nj接收到多个虚拟信标的平均跳距离值，虚拟信标Ai计算的平均跳距离记为Di，节点Nj到信标Ai的跳数为Hi。

加权因子体现的是各个虚拟信标节点计算出来的平均跳距离值对未知节点计算平均跳距离值的影响力，假设未知节点N1接收到三个虚拟信标节点(A1,A2,A3)的平均跳距离值(D1,D2,D3)，而该节点查找表中所记的跳数值知道其距离三个虚拟信标的跳数分别为：H1，H2，H3。那么节点计算其平均距离值如下式：

EMBED Equation.DSMT4 (3.8)

各个平均跳距离的权值相加为1，反映的是各个平均跳距离值对最终计算的跳距离值的影响程度，这样计算节点Nj的平均跳距离值就为：

EMBED Equation.DSMT4 (3.9)

至此，各未知节点已得到与各个虚拟信标的跳数，并可据此求出适合自己网络区域内的平均跳距离值，因此可利用三边测量法计算出未知节点Nj的坐标。

3.1.3 仿真分析

为了验证算法的性能，将提出的算法在OMNeT++平台进行仿真，并用MATLAB进行实验数据的辅助分析，在OMNeT++平台上，将100个传感器节点随机分布在一个50 EMBED Equation.DSMT4 50的区域中，节点通信半径为10。网络中还有一个可获得自身位置的移动信标按Gauss-Markov模型移动，平均速度为5，初始方向角设为90o，在边缘区域时转变系数，即式(4,5)中 EMBED Equation.DSMT4 =0.75，移动信标的广播计算器设置为2秒，即移动信标节点每移动2秒后即在网络中进行定位信息的广播。为了使仿真结果更接近实际的情况，仿真结果是经过20次独立仿真结果平均值获得。

1、定位精度与定位覆盖率分析

移动信标以预定的运动模型运动，并周期性的广播定位信息包， 即虚拟信标的增长速度，虚拟信标越多，定位精度越高，所花的定位时间也越多，他们存在图3-3中的关系。

图中所示的关系是显然的，随着时间的推移，移动信标在网络中移动的距离越远，广播的定位信息越多，虚拟信标也越多，定位的误差也随之减小。同样的，随着移动信标的轨迹覆盖了越多的地方，越来越多的未知节点获得定位信息包而计算自己的位置，定位的覆盖率也不断增加。

EMBED Visio.Drawing.11

图3- SEQ 图3- \* ARABIC 3定位误差与定位覆盖率

Fig.3- SEQ Fig.3- \* ARABIC 3 Localization error and Localization ratio

2、信标节点广播定位信息周期T的影响

当移动信标节点以参数一定的Gauss-Markov模型运动时，广播周期越小，则虚拟信标越密，即单位区域内虚拟信标越多，必然导致节点通信消耗的增大，误差也增大。当周期T增大到一定程序时，再增大，则广播的定位信息大少，用于定位的虚拟信标大少，也会导致定位误差的增大。最优的定位周期的大小由节点由通信半径决定，当通信半径越大时，广播的周期也应相应的增大。在同样的移动模型下，当广播周期T变化时，定位误差与其关系如下图3-4所示：

EMBED Visio.Drawing.11

图3- SEQ 图3- \* ARABIC 4移动信标广播周期T与平均定位误差

Fig.3- SEQ Fig.3- \* ARABIC 4 Broadcast Period T for Mobile Beacon and Average Positioning Error

3、定位误差比较

算法的性能主要以定位的误差来评价，移动信标以2秒的周期广播定位信息包，即在网络中构造一个虚拟信标。仿真结果的比较如图3-5所示。

EMBED Visio.Drawing.11

图3- SEQ 图3- \* ARABIC 5移动信标广播周期T与平均定位误差

Fig.3- SEQ Fig.3- \* ARABIC 5 Relationship between mobile beacon brocasting period and average position error

如图3-5中可见，两种定位算法的误差随着信标节点的增加都会减少，在信标节点越多的时候，本文提出的算法误差减少更明显，这是因为采用了加权处理来求各未知节点的平均跳距离，当一个节点获得越多其周围的虚拟信标计算的平均跳距离，加权处理后的平均跳距离就越接近真实的网络情况。

3.2基于移动信标动态选择改进DV-Hop定位算法

DV-Hop是一种经典的无需测距的定位算法，具有定位算法简单，定位精度较高的优点，但其定位精度依赖于网络连通状况，对于各向同性的网络，可以获得较适当的定位精度，而对于不规则拓扑的网络定位误差则较大 REF _Ref259519859 \r \* MERGEFORMAT [41] 。

DV-Hop算法在获得平均每跳距离的计算过程中，节点之间的通信量过大，将网络作为一个整体考虑，所有节点在计算自己与参考节点的距离时使用同一个平均跳距离，导致平均定位误差较大。DV-Hop算法在网络平均连通度为10，参考节点比例为10%的各向同性网络中定位精度约为33%。该算法的缺点是仅仅在各向同性的密集网络中，才能合理地估算平均每跳的距离 REF _Ref259472496 \r \* MERGEFORMAT [10] 。针对这种情况，提出了一种基于移动信标动态选择的改进DV-Hop定位算法(DSB-DV-Hop)，通过引入移动信标在网络中按预定轨迹漫游，并在每个虚拟信标节点的位置单独计算网络各部位的平均跳距离后广播其位置分组，未知节点记录到每个虚拟信标的跳数，动态选择能获得最高计算精度的信标节点来进行三边测量法计算自己的位置，减少无线传感器网络定位的成本，并且提高了定位精度。最后通过仿真证明此算法可以提高定位精度，减少算法的计算量，提高了定位的效率。

3.2.1 DV-Hop定位算法平均跳距离计算误差来源分析

在运行DV-Hop定位算法时，会先预定在网络中进行洪泛的数据包的跳数，包含信标节点位置信息的数据包只经过预定的跳数。节点每接到一个数据包会在表示其生命周期的跳数加1，当达到预定的跳数时，则不再转发这一数据包。在上述的DV-Hop定位算法的过程中，信标节点会根据他接收到的所有信标节点发来的数据包的信息计算平均每跳距离。当信标节点计算好自身网络的平均跳距离后，把这个跳距离广播到自己的网络中，同样制定了表示其生存周期的预定跳数。即在其指定跳数范围内的未知节点会接收到这个平均跳距离的数据包。未知节点只记录其接收到的第一个信标节点发来的平均跳距离，作为自己计算与信标节点的距离的依据。

如图3-6所示的情况中，我们可以看到：当某未知节点N接收到来自其周围3跳距离内的信标节点的定位信息时，其列表中将有5个信标节点的位置及跳数。由图中所示情况我们可以看到，信标节点A4和A5与未知节点的距离经过中间节点时“弯曲”的比其它信标节点要厉害些。如果按同样的平均跳距离计算时，未知节点N与A4和A5的距离是要小于它到其它节点的距离。

因此，在定位计算中，如果把A1, A2, A3, A4, A5都计算在内，其得到的误差必然会增大，因为A4和A5两个信标节点虽然都在A节点的两跳通信距离内，在其实际距离并没有平均跳距离的两倍，从节点A到这两个节点时传输的分组数据包是“曲折”的，而A1, A2和A3都是近似直线的。在定位计算过程中，当这种节点增多时，对于定位误差的影响显而易见。文献 REF _Ref259520018 \r \* MERGEFORMAT [42] 通过实验发现在这种条件下分析每一个未知节点定位的精度时，有些误差达到200%。

假设从图3-6中得到的5个信标节点的列表中选择三个信标节点的数据包分组来进行三边定位计算，如果选择不同的信标节点，对计算的误差是显而易见的。我们可以从中选取两种组合来比较，如A3，A4和A5的组合和A1，A2和A3的组合。图3-7是两种组合下的计算情况的示意图，从图中我们可以看到，当A4和A5这两个节点参与三边定位计算时，其定位的误差明显增加。因此，设计移动信标的动态选择算法来选择最佳的虚拟信标的数据参与三边定位计算，将直接影响其定位计算的精度。

EMBED Visio.Drawing.11

图3-6 DV-Hop定位算法误差来源分析

Fig.3-6 The resource of Localization error of DV-Hop

EMBED Visio.Drawing.11

(a). 选择A1，A2和A3计算

(a). Select A1, A2 and A3 to run trilateration algorithm

EMBED Visio.Drawing.11

(b) 选择A3，A4和A5计算

(b). Select A3, A4 and A5 to run trilateration algorithm

图3-7 选择不同的信标节点进行三边定位计算示意

Fig.3-7 Select diffirent beacon nodes for trilateration calculating

3.2.2基于移动信标动态选择的改进型DV-Hop定位算法过程

带有定位装置的信标节点装载在可移动的平台或移动机器人上，就构造了一个移动信标，移动信标在一定规律的移动过程中，可实时获取自身位置，并周期性的广播自身的位置信息，以帮助未知节点进行定位。当未知节点获得足够多的虚拟信标的信息时，我们需要动态选择最优的虚拟信标参与三边定位计算来提高计算精度，本文接下从信标节点的移动模型，虚拟信标的动态选择算法来分析如何选择进行基于移动信标动态选择的改进型DV-Hop定位算法。

1、信标节点移动模型

移动信标节点采用什么样的方式移动才能尽可能的遍历整个网络，这个本身就是一个研究的热点，网络中传感器节点本身是随机散布的，节点位置本身信息是未知的，为了使这些节点全部进行定位，需要设计出一种运动模型，使移动信标的运动轨迹能在尽少的时间内遍历网络，发送足够的定位信息给未知节点以完成定位算法。目前应用于无线传感器网络的移动模型有S型、RWP(Random Way Point)模型和Gauss-Markov模型等。这些模型是自组织网络中广泛应用的模型，RWP模型对信标的硬件要求小，路径的随机性大，并且随着运动速度逐渐减小，运动轨迹出现在网络中心区域的概率偏大。S模型则对硬件的要求相对较高。

为此此处选用3.1节中的Gauss-Markov运动模型，该模型可以覆盖网络的大部分区域，相对于RWP模型，可以避免运动轨迹的突变和边缘地带概率减少的缺点[6]，对硬件的要求也不高。

信标节点按照Gauss-Markov模型计算每个时刻的运动速度和方向，并由定位装置获取当前运动位置的坐标信息，将其广播到网络中。因为信标节点要周期性的广播坐标信息，还要接收网络中未知节点广播回来的跳数累加的广播分组，故在Gauss-Markov模型中，设置一个计时器，计时周期为信标节点广播坐标的周期，每当计时器时间到，移动暂停，广播当前位置信息，并接收各未知节点返回的跳数广播分组，记录在列表中，再继续移动

2、定位算法过程

信标节点在网络中移动，周期性地将位置信息广播到网络中，广播的信息格式包括当前运动到第几个点，当前位置坐标，网络跳数(初始化为0)，在移动信标节点通信范围的未知节点都接收到该位置的信标节点的定位数据包。每个节点接收到定信息后，将其中的跳数值加1后继续广播。每个节点接收到多个邻居节点的广播值都与本身记有的值比较，如果小于自身记有的跳数值，则丢弃这个广播分组。

这一过程与DV-Hop定位算法相似，不同的是，未知节点判断接收到的是第几号位的信标节点广播，如果为第1个就暂不广播，直到接收到第二号位的信标广播时，再把一号位的定位信息包广播出去，并保存接收到的二号位广播，等待下一位的广播后再发送，以此类推。广播定位信息的过程分为以下几步：

步骤1：移动信标在第一个位置取得当前位置信息，封装位置信息广播信息包{LIDi, xi, yi, HOPs}，LIDi表示当前是第几号位置的广播包，xi，yi表示当前位置坐标，HOPs为经历的跳数，初始为0；

步骤2：移动信标在第一个位置的通信范围内所有邻居节点接收到定位信息包，接收到信息包的节点将其与本身的数据包进行比较，取跳数较小的一项，并丢弃较大的，将跳数一项加1，记录下这个个跳数值，等待下一个定位信息包；

步骤3：移动信标移动到下一个位置，将位置信息加1并广播这个一新位置的定位信息包，同时接收各节点发回的广播信息，取与前一位置最小跳数的分组，将两位置的距离除以跳数计算出平均每跳距离(Di)并广播到网络中；

步骤4：重复步骤3直到位置号达到预先设定的阈值K，K根据所需的虚拟信标密度而定，如果网络中有N个未知节点，根据精度要求得出虚拟信标比例q，则： EMBED Equation.DSMT4 ；

步骤5：未知节点选择接收到的第1个虚拟信标的平均跳距离，并运行动态选择算法选择最优的虚拟信标节点，根据记录的跳数计算出到所选择的虚拟信标的距离，用三边测量法计算自己的位置。

3、虚拟信标动态选择算法

通过前文的分析，我们知道在未知节点的列表中要合理的选择最优的信标节点的定位信息来进行三边定位计算。在2.2节中未知节点获得虚拟信标节点列表，第5个步骤需要未知节点运行动态选择算法来选择能获得最高计算精度的最优三个信标节点。

动态选择算法的是思想是首先确定选用获得的第1个接收到的虚拟信标的平均跳距离值来进行定位计算，并将些虚拟信标作为标准节点，其它所有虚拟信标均以其为标准参考来计算和比较定位的精度。我们通过反演推算来计算怎样的虚拟信标组合可以得出最高计算精度。除去标准节点外，我们从未知节点的列表中按两两组合来选择，并与标准节点组成三个节点的组合，假设未知节点列表中有M个虚拟信标的分组信息，那么除去选定的标准节点，还有 EMBED Equation.DSMT4 个组合，用这些组合计算出未知节点的位置，然后将这个未知节点作为已知节点，与之前的组合加在一起来运行三边计算法，计算标准节点的位置，比较哪一种组合下，计算出的标准节点位置与其真实位置最接近，则这一组合即为能获得最高计算精度的最优三个虚拟信标节点。

动态选择算法的运算过程可以表述如下：

首先运行上文提出的移动信标的DV-Hop定位算法的步骤，未知节点获得虚拟信标定位信息列表，假设未知节点N的虚拟信标分组列表中有n个虚拟信标节点的位置信息，如前文图2中所示。未知节点N首先确定第1个接收到的虚拟信标A3作为标准节点。并将A3广播的平均跳距离DA3作为自己定位计算的值。未知节点从虚拟信标定位信息列表中除A3外的其它节点中任意选择p个虚拟信标来计算，此处为了说明方便，我们选择p=4，即有(A1,A2,A4,A5)，共5个虚拟信标进行动态选择算法：

步骤1：从4个挑选出的虚拟信标中按两两组合后与A3构成三边定位计算的三个信标节点，共有C42=6个组合，即：(A3,A1,A2)、(A3,A1,A4)、(A3,A1,A5)、(A3,A2,A4)、(A3,A2,A5)、(A3,A4,A5)，将这6种组合分别用三边测量法计算出未知节点N的位置，分别记为：N1、N2、N3、N4、N5和N6；

步骤2：将这6个计算的未知节点N的位置作为已知节点，将其取代之前的6个组合中的标准节点A3，得到另外6种组合，即：(N1,A1,A2)、(N2,A1,A4)、(N3,A1,A5)、(N4,A2,A4)、(N5,A2,A5)、(N6,A4,A5)，将这6种组合分别再用三边测量法计算标准节点A3的位置，获得6个值，即A31、A32、A33、A34、A35和A36；

步骤3：比较得到的标准节点A3的位置与A3的实际位置， 计算步骤1中的6种组合中哪一组合可得到最接近A3实际位置，假设A3的实际位置坐标为(XA3,YA3)，计算得到的A3位置坐标为(Xn,Yn)，那么误差公式计算公式如下：

EMBED Equation.DSMT4 (3.10)

步骤4：选择误差最小，即d的值最小的一组组合即为可以获得最高计算精度的虚拟信标。

经过上述动态选择算法后，未知节点按最优的三个虚拟信标组合进行三边定位计算，获得最高的定位计算精度。

3.2.3仿真分析

为了验证本文提出的移动信标动态选择算法对定位精度的影响，我们采用OMNeT++平台进行定位过程的仿真，并用MATLAB进行实验数据的辅助分析，在OMNeT++平台上，将100个传感器节点随机分布在一个50 EMBED Equation.DSMT4 50的区域中，节点通信半径为10。网络中还有一个可获得自身位置的移动信标按Gauss-Markov模型移动。为了使仿真结果更接近实际的情况，仿真结果是经过20次独立仿真结果平均值获得。

1、仿真实验条件设定

为了验证在不同的信标节点比例下的动态选择算法效果，我们在实验过程中根据不同的定位精度设定5个虚拟信标的比例q1=0.1，q2=0.15，q3=0.2，q4=0.25，q5=0.3，那么在两种情况下虚拟信标阈值分别为K1=10，K2=15，K3=20，K4=25，K5=30。移动节点在网络中漫游，随着时间的推移，在网络中形成的虚拟信标越来越多，所以越大的虚拟信标节点密度需要越长的定位时间，当然其对定位计算的消耗和通信开销也将增大。

同时设置信标分组数据包跳数为3，即所有信标节点的定位信息在网络中经过3跳则自动丢弃。

2、定位误差分析

移动信标在网络中以预定的运动模型移动，并周期性的广播定位信息包，在不同的虚拟信标阈值下获得的定位精度的关系表如下图3-8所示：

图中所示的关系是显然的，在DV-Hop定位算法中，信标节点的密度越大，获得的定位精度越高。而本文提出的定位算法在对节点进行三边定位计算前先用动态选择算法选出能获得最大计算精度的定位信息，在虚拟信标密度越大时，定位计算的精度也越大。在信标节点密度不大时，未知节点获得的可选定位信息也较少，其在计算精度上的优势并不明显，随着虚拟信标越来越多，通过动态选择后获得的计算精度也会越来越高，因为它摒弃了定位信息列表中“弯曲”路径上的信标节点，避免其带来的计算误差。

EMBED Visio.Drawing.11

图3-8 虚拟信标密度对定位精度的影响

Fig.3-8 Density of virtual beacon affecting the positioning error

3、定位计算量及通信开销分析

本文提出的算法其计算量主要在虚拟信标的动态选择上的计算，即进行多次三边定位计算来选择最高精度的信标节点组合，在动态选择算法中决定计算量的就是从虚拟信标节点列表中选择的信标数p，进行三边定位计算及反演推算的次数R的计算方法如下：

EMBED Equation.DSMT4 (3.11)

而节点的通信开销主要是网络初始定位数据包的洪泛，并没有额外增加另外的通信开销，由于采用可控的的洪泛在网络中传送数据，每个数据包只可控的跳数后就被丢弃，其通信的开销取决于每个数据包的可传送跳数。

3.3 本章小结

本章主要介绍基于移动信标动态选择的无线传感器网络定位算法，将移动信标引入到DV-Hop定位算法中，并通过加权处理和动态选择算法来对平均跳距离的计算进行求精，提高定位算法的精度，最后通过仿真从定位的精度和定位覆盖率来分析定位算法的性能和优越性，并分析了移动信标移动时广播周期对定位性能的影响。第四章 无线传感器网络移动信标的路径优化

无线传感器网络基于信标节点定位的核心问题是，信标节点在网络中的密度及其分布，多数的基于信标节点的定位算法的定位精度及定位效率都依赖于信标在网络中的分布及分布密度。而基于移动信标的定位算法则需要研究信标节点的移动模型及移动路径，即使网络中的节点以最小的代价获得足够多用于自身定位的信息。对于移动信标节点，需要研究针对网络状况获取移动路径的算法，使移动信标可以在网络中以最短的时间将定位信息广播到网络中，而由于无线传感器网络能源有限的特点，还应考虑在不同的路径时，各节点的通信开销。这样将移动信标引入定位算法的做法才能体现其经济性。通常的算法通过提高信标节点的密度来提高定位算法的精度，基于移动信标的节点以信标节点在网络中漫游构造虚拟信标来代替实际的信标节点。所以移动信标的路径获取问题可以看作是如何在网络中快速有效地布置信标节点。

4.1无线传感器网络移动信标的移动模型分析

由于基于移动信标的定位算法通过引入移动信标节点在网络中漫游并广播定位信息来构造虚拟信标节点，所以信标节点在网络中的移动轨迹和广播信息的机制将影响到网络中的虚拟信标节点的分布。所以信标节点按照怎样的移动模型或路径进行移动？在什么位置上以怎样的时间间隔广播定位信息的无线电信号不仅影响到移动信标节点的能耗、工作时效，还将影响到网络节点的定位精度和通信的开销。对此，许多学者进行了相关的研究。主要可以把路径的规划分为静态和动态规划，静态的路径规划与网络的连通状况无关，根据需要定位的ROI区域，规划以尽可能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可夫移动模型，螺线移动模型和SCAN移动模型。

4.1.1 随机移动RWP(Random Way Point)模型

随机走动模型 REF _Ref260831658 \r \* MERGEFORMAT [43] 早在1926年爱因斯坦在模拟粒子的布朗运动时就曾采用过。在该模型中，一个移动节点从它当前的位置随机选择一个方向和速度运动到一个新的位置。它以一种随机的方式移动，其中节点移动速度和方向均不相关联。由于其随机性，该模型实际上是一种不太现实的节点移动模型。对Random Walk节点移动模型的一般假定如下：节点在[0，2 EMBED Equation.DSMT4 ]范围内随机选择一个方向，移动速度为[最小速度，最大速度]间的均匀分布。节点每次所确定的移动速度和方向维持的时间间隔为L如果节点移动至仿真区域的边界，它就以一个由来时的方向所确定的角度反弹回仿真区域内，然后再继续以这个新路径移动下去。Random Walk节点移动模型应用简单，在模型的初始化和特殊环境的测试中是值得借鉴的 REF _Ref260831796 \r \* MERGEFORMAT [44] 。Polya曾证明了Random walk节点移动模型在一维或二维情况下，节点返回初始位置的概率是确定的，该特性确保了RandomWalk在其初始位置周围移动，不用担心节点移走后不返回。随机走动移动模型是一种无记忆的运动方式，是完全的随机走动方式的基础。由于节点当前的移动速度和方向完全独立于先前的移动速度和方向，因而会使网络中的节点在移动的过程产生不切实际的运动如突然的停止或急转，不符合实际的应用情况，不利于对其他性能的研究 REF _Ref260831931 \r \* MERGEFORMAT [45] 。

4.1.2高斯马尔可夫移动Gauss-Markov模型

高斯马尔可夫移动模型可以覆盖网络的大部分区域，相对于RWP模型，可以避免运动轨迹的突变和边缘地带概率减少的缺点 REF _Ref259519260 \r \* MERGEFORMAT [40] ，对硬件的要求也不高，其模型表示如下：

EMBED Equation.DSMT4 (4.1)

EMBED Equation.DSMT4 (4.2)

v(k)和d(k)表示运动时刻k移动信标的速度和方向。a 是方向随机调节参数，取值为0到1(0<=a<=1)，vmean, dmean为平均速度和平均运动方向, EMBED Equation.DSMT4 ， EMBED Equation.DSMT4 代表高斯随机变量。移动的下一时刻的速度和方向从当前的速度和方向求出：

EMBED Equation.DSMT4 (4.3)

EMBED Equation.DSMT4 (4.4)

该节点移动模式是一种较为实际的随机模式，节点在整个过程的运动速度和方向的改变是很平滑的，但其中最优参数的选取应该根据实际的无线传感器网络规模和定位精度来合理确定。由于高斯马尔可夫移动模型的可调参数多，灵活性很大，这种模型具有广阔的应用前景。

4.1.3 螺线移动模型

螺线是文献 REF _Ref260839763 \r \* MERGEFORMAT [46] 给出的一种典型的信标路径，其主要特点是各发射点可构成一条螺旋线，信标节点在螺线上移动并发射信号，即可对传感器实现定位．我们在实验中采用的螺线方程如下：

EMBED Equation.DSMT4 (4.5)

该螺线的特点是，相邻内旋和外旋间距为 EMBED Equation.DSMT4 。信标发射点选择方式为：以ROI中心(即螺线起点)为第1个发射点，每个发射点与螺线上前一发射点的间距为信标发射半径r，这样可以充分利用信标信号覆盖ROI区域。

文献 REF _Ref260831169 \r \* MERGEFORMAT [46] 提出的螺线式的信标移动路径，是一种简单可行的方案，但这种路径无法充分而高效地覆盖ROI，容易出现信标覆盖盲区，降低了定位精度。文献 REF _Ref260831229 \r \* MERGEFORMAT [47] 提出一种基于改进蚁群算法的信标移动路径获取算法，该算法在蚁群算法的基础上使用了三重优化覆盖的方法来选取最少的发射位置，获得移动信标的路径，该路径一定程度上提高了定位的效率同时降低了定位过程的功耗。但其对于分布不规则的传感器网络存在同样的问题而限制了其应用。

4.2面向无线传感器网络节点定位的移动信标的路径优化

在未进行节点的定位前，无线传感器网络的全局信息是未知的。为了提高网络节点的定位精度，降低网络定位的通信的开销，通过引入图论的方法来分析信标的路径规划问题。信标节点按照怎样的移动模型或路径进行移动？在什么位置上以怎样的时间间隔广播定位信息的无线电信号？把一个传感器网络中的节点看做图的顶点，网络中能够互相通信的节点间的无线链路作为图的边，就可以把整个传感器网络描述为一个连通的无向图G=(V(G)，E(G))。移动信标的路径规划问题可以通过连通无向图的生成树以及树的遍历问题来求解。对于处于网络边缘无法与其它节点连通的节点，我们称其为坏节点，是无法实现定位的，因为这样的节点无法归结到图中。

4.2.1基于图论的信标移动路径规划方法

首先，我们对网络的情况进行描述，作出如下的假设。

1)无线传感器网络节点使用全向天线，每个节点的无线通信范围是以节点为圆心、半径为R 的圆形区域；

2)无线传感器网络中所有的节点是连通的，也就是说网络中的任意节点至少可以和一个邻居节点互相通信；

3)网络同构，即无线传感器网络的每个节点拥有相同的通信半径Rc，初始能量E0，位置未知．移动信标安装有GPS接收器和无线信号接收阵列，移动信标的通信半径Rm为无线传感器网络其它节点通信半径Rc的1.5倍，不需要考虑移动信标的能量。

为了把传感器网络的移动信标节点的路径规划问题描述为图的问题，我们需要先明确几个概念。

1.邻居节点：在移动信标访问WSN节点Vi时，如果节点Vn到移动信标MBecon的距离d( Vn，MBecon)
2.内部节点：在移动信标访问WSN节点Vi时，如果节点Vn到移动信标MBecon的距离d( Vn，MBecon)<2Rm/3 ，称节点Vn为节点Vi的内部节点。

3. 边缘节点：在移动信标访问WSN节点Vi时，如果节点Vn在移动信标的通信范围内，但是到移动信标MBecon的距离大于MBecon的通信半径的2/3，即2Rm/3< d ( Vn，MBecon)
4．节点无向图顶点权值：设节点无向图中顶点Vi的位置未知的邻居顶点个数为n，定义顶点Vi的权值为1/n。

我们在引入图论后，移动信标的路径获取方法就可以通过图的生成树的遍历问题来求解，为此，我们提出反演式贪婪算法，其步骤如下：

步骤1．以节点无向图G=(V(G)，E(G))中任意在移动信标的内部节点的顶点V∈V(G)为树的顶点，令i=1．移动信标首先开始访问顶点Vd。

步骤2．对于当前被访问顶点Vd

For(顶点Vd的所有邻居节点)

{If(邻居节点Vn是顶点Vd的内部节点)

{删除顶点Vn}；

Else If(邻居顶点Vn是顶点Vd的边缘节点)

{计算顶点Vn的权值；}；

}；

If(顶点Vn的权值最小)

{扩展顶点Vn为顶点Vd的子节点，标记已访问的节点V；}

以顶点Vn为当前被访问顶点，重复步骤2

步骤3．If(节点无向图G=(V(G)，E(G))还有未被访问节点)

{

计算未被扩展顶点中距离当前顶点最小的顶点V；

以顶点V为起始点；

返回步骤2；

}；

结束

以上描述的算法计算过程，我们采用反演式贪婪算法来进行无向图的生成树的遍历。其中引入的节点无向图顶点的权值，其实就是根据网络的连通状况来不断改变移动信标的路径，使其运动轨迹能遍历网络。

4.2.2面向传感器网络的移动信标路径规划的仿真实现

为了分析我们提出的路径规划方法在网络中的移动路线的情况，我们用Matlab仿真语言对规划路径的算法进行仿真。假设系统随机部署50个WSN节点，分布于50m×50m的区域内。如图4-1和4-22所示，圆点为内部节点，正方形为移动信标访问过的节点，即其广播自己定位信息的点，线段为移动信标在传感器网络的节点定位过程中的规划路径。

反演式贪婪算法争取访问最少的节点。当移动信标通信半径分别为10m和15m时，按照反演式贪婪算法，规划的路径分别如图4-1和图4-2所示。

EMBED Visio.Drawing.11

图4-1 反演式贪婪算法的规划路径，节点通信半径R=10m

Fig.4-1 Mobile beacon moving target, R=10m

EMBED Visio.Drawing.11

图4-2 反演式贪婪算法的规划路径，节点通信半径R=15m

Fig.4-2 Mobile beacon moving target, R=15m

移动信标距离网络节点越近则距离测量误差越小，定位精度越高。系统通信、能量等开销也和移动信标的移动路径有很大关系，在网络节点完全能够计算出位置信息的情况下，移动信标访问网络中的节点越少，即在越少的地方广播自己的部署分组，系统的开销越小。

在上面的仿真图中，当移动信标的通信半径增大时，访问网络中的节点也会相应减少，即在网络中广播的位置减少了，构成的虚拟信标也减少了，这是因为移动信标的通信距离增大，在每次广播分组后，能参与定位的节点增多了，在同样大小的网络中，虚拟信标的需求量就减少了。移动信标的每次移动距离也增加了。

4.3 本章小结

本章主要介绍了无线传感器网络移动信标的路径优化，分析常见的几种静态路径规划方法，分析其特点，并通过引入图论的方法来分析信标的路径规划问题，提出反演式贪婪算法，并进行仿真分析，研究规划路径在网络区域中的覆盖问题，为下一章进行基于移动信标的无线传感器网络节点定位算法的仿真实验提供基础。
第五章 基于移动信标优化路径定位算法的仿真实现

5.1仿真实验工具和实验方法简述

5.1.1 OMNeT++仿真实验平台介绍

OMNeT++是一个基于C++的面向对象的模块化离散事件仿真工具，主要面向OSI模型，用于模拟计算机网络通信协议、多处理器、排队网络、分布式系统及并行系统，应用领域包括移动、无线到ATM和光网络的仿真，从硬件仿真到排队系统，可以仿真执行上千个节点，主要目标是提供可灵活配置仿真的组件体系。仿真环境采用自定义的拓扑描述语言NED定义模型结构，用c++语言描述并发进程模型的活动构件 REF _Ref260840390 \r \* MERGEFORMAT [48] 。

OMNeT++构建的模型由分级嵌套模块组成，如图5-1所示，最高层的模块称为系统模块或网络，该模块包含一个或多个子模块，而子模块也可以有自己的子模块。由于嵌套模块的深度没有限制，因此可以在OMNerr++中构建复杂的系统模型。在NED中定义了两种模块：普通模块和复合模块，模块间通过门或链接进行消息传输。

EMBED Visio.Drawing.11

图5- SEQ 图5- \* ARABIC 1 OMNeT++分组嵌套模型

Fig.5- SEQ Fig.5- \* ARABIC 1 OMNeT++ Modle

OMNeT++内核采用c++语言编写，使用NED实现网络拓扑描述，同时提供了图形化的用户界面，可以动态地观察仿真程序的运行情况。面向对象的设计易于根据需要进行功能扩展，使用参量方式，可以在不修改源代码和重新编译的情况下，对不同条件的网络模型进行仿真，提高了仿真效率。通过PVM支持，可以同时在多台机器上并行运行仿真程序。

OMNeT++仿真模型用两种不同的语言编写：NED和C++.NED(NEtwork Description)语言描述仿真的拓扑设计，其中可以定义模块、链路、网络。C++执行NED语言定义的模块，OMNeT++仿真库可以模拟模型中的任何方法，其中包括进度表及取消的事件进程，还包括图形工具“Plove”(用于绘制统计数据和生成数据)。

OMNeT++仿真有两种运行方式：视图和文本。视图仿真特别适用于初次运行或对网络协议很熟悉的模拟，它以动画的形式显示两个模块间传递信息的过程，对于更大规模的仿真可进一步显示每个模块间的信息传递。

5.1.2定位算法性能评价指标及分析方法

WSN自身定位系统和算法的性能直接影响其可用性,如何评价它们是一个需要深入研究的问题.下面定性地讨论几个常用的评价标准 REF _Ref260840454 \r \* MERGEFORMAT [49] 。

(1)定位精度：定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程的比例表示，例如，定位精度为20%表示定位误差相当于节点无线射程的20%。也有部分定位系统将二维网络部署区域划分为网格,其定位结果的精度也就是网格的大小，如微软的RADAR REF _Ref259472477 \r \* MERGEFORMAT [8] ，Wireless Corporation的RadioCamera等。

(2)规模：不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内，一种技术可以定位多少目标也是一个重要的评价指标。例如，RADAR[2]系统仅可在建筑物的一层内实现目标定位,剑桥的Active Office定位系统每200ms定位一个节点。

(3)信标节点密度：信标节点定位通常依赖人工部署或GPS实现，人工部署信标的方式不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展性.而使用GPS定位，信标的费用会比普通节点高两个数量级，这意味着即使仅有10%的节点是信标，整个网络的价格也将增加10倍。因此,信标密度也是评价定位系统和算法性能的重要指标之一。

(4)节点密度：在WSN中,节点密度增大不仅意味着网络部署费用的增加,而且会因为节点间的通信冲突问题带来有限带宽的阻塞.节点密度通常以网络的平均连通度来表示.许多定位算法的精度受节点密度的影响,如DV-Hop算法仅可在节点密集部署的情况下合理地估算节点位置。

(5)容错性和自适应性：通常,定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设备.但在真实应用场合中常会有诸如以下的问题:外界环境中存在严重的多径传播、衰减、非视距(non-line-of-sight,简称NLOS)、通信盲点等问题;网络节点由于周围环境或自身原因(如电池耗尽、物理损伤)而出现失效的问题;外界影响和节点硬件精度限制造成节点间点到点的距离或角度测量误差增大的问题.由于环境、能耗和其他原因,物理地维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难或不可行的.因此,定位系统和算法的软、硬件必须具有很强的容错性和自适应性,能够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响,以提高定位精度。

(6)功耗：功耗是对WSN的设计和实现影响最大的因素之一.由于传感器节点电池能量有限,因此在保证定位精度的前提下,与功耗密切相关的定位所需的计算量、通信开销、存储开销、时间复杂性是一组关键性指标。

(7)代价：定位系统或算法的代价可从几个不同方面来评价.时间代价包括一个系统的安装时间、配置时间、定位所需时间.空间代价包括一个定位系统或算法所需的基础设施和网络节点的数量、硬件尺寸等.资金代价则包括实现一种定位系统或算法的基础设施、节点设备的总费用。

上述7个性能指标不仅是评价WSN自身定位系统和算法的标准,也是其设计和实现的优化目标.为了实现这些目标的优化,有大量的研究工作需要完成.同时,这些性能指标是相互关联的,必须根据应用的具体需求做出权衡，以选择和设计合适的定位技术。

5.2基于移动信标的传感器网络定位算法的设计

为了验证我们提出的基于移动信标优化路径的定位算法的性能，本章将在OMNeT++平台上通过建立移动信标节点的模型，并让其按第四章中规划的路径移动广播信息。网络中的未知节点按我们前文提出的改进DV-Hop定位算法计算自己的位置。通过将DV-Hop定位算法，第四章中在高斯马尔可夫移动模型下的改进DV-Hop算法及基于优化路径的DV-Hop定位算法的定位精度，定位覆盖率进行比较，来分析各算法的性能，比较在两种不同移动路径下的改进DV-Hop定位算法的定位通信开销，计算量及定位响应时间来分析比较两种不同的路径对网络节点定位的影响。

为了便于比较，我们在OMNeT++上建立网络模型，在同样的大小的50 EMBED Equation.DSMT4 50的区域内随机分布了30个传感器节点，对于DV-Hop定位算法，我们将其中的6个节点作为信标节点来对其它24个未知节点定位，即信标节点的比例占到20%。对于本文提出的改进DV-Hop算法，只选用一个可获得自身位置的移动信标节点在网络中按两种不同的规划路径来移动，并进行网络节点的定位。

首先我们需要对网络的环境进行一些假定，网络中所有的未知节点的通信半径均为10，移动信标的通信半径同样也为10。按高斯马尔可夫模型移动的DV-Hop定位算法设置网络虚拟信标比例的阈值为0.2，也就是说在我们建立的网络模型中，虚拟信标达到6个时，即结束在网络中的漫游和广播。为了减少网络洪泛的通信量及尽量避免通信的阻塞，同时设置DV-Hop及改进DV-Hop定位算法广播信标分组的跳数为3，即所有信标节点的定位信息在网络中经过3跳则自动丢弃。对于两种移动模型下的改进DV-Hop算法，我们都采用3.1节中提出的平均跳距离的加权值计算方法来计算。并采用3.2节中提出的移动信标动态选择算法来进行虚拟信标的优化筛选，得出可获得最高定位精度的节点来进行定位运算。

5.2.1无线传感器网络仿真程序模型及程序设计

在OMNeT++仿真平台上建立网络拓扑有两个步骤：建立网络节点的描述文件(.ned 文件)和建立网络的描述文件。首先建立移动信标的网络描述文件。



(a) 移动信标节点模型 (b)网络未知节点模型

(a) Mobile beacon nodes model (b) Network’s unknown nodes model

图5- SEQ 图5- \* ARABIC 2网络节点的模型拓扑图

Fig.5- SEQ Fig.5- \* ARABIC 2 Nodes model of network

移动信标有三个模块：Comm、Mobility、Position。Comm 实现节点间的通信连接，Mobility 实现节点的按路径的移动，Position按定位算法计算节点位置。未知节点静止安装在网络中则没有Mobility这一模块，通过与网络中节点的通信后计算实现定位，所以只有Comm和Position两个模块。两种节点的拓扑图如上图5-2所示。相应的移动信标的节点描述文件的三个模块如下：

1．Comm模块

simple Comm

parameters:

mBean_r: numeric const, // 信标节点的通信半径

node_r: numeric const, // 待定位节点的通信半径

isBeacon: numeric const; // 是否是信标节点

gates:

in: fromMobility;

in: fromPosition;

out: toPosition;

endsimple

2．Mobilility模块

Simple Mobilility

parameters:

max_Speed: numeric const, //最大速度

min_Speed: numeric const, // 最小速度

move_Toward: numeric const,//下一步运动的方向

mov_edge: numeric const, //节点运动到边界时的处理方式

XRange: numeric const, // 节点布置区域的宽度

YRange: numeric const, //节点布置区域的长度

Pause_Time: numeric const, //到达一个目标后的等待时间

move_Interval: numeric const, //两步之间的时间

gates:

out: out;

endsimple

3．Positioning模块

simple Positioning

parameters:

isBeacon: numeric const, // 是否是信标节点

announceInterval: numeric const, // 信标节点广播自身位置的时间间隔

updateInterval: numeric const, // 待定位节点两次定位间的时间间隔

beacon_r: numeric const, // 信标节点的通信半径

node_r: numeric const, // 待定位节点的通信半径

max_v: numeric const, // 最大速度

delta: numeric const; //抽样点可能的误差

gates:

in: fromBottom;

out: toBottom;

endsimple

4．移动信标模型文件

module Mobile_Host

parameters:

num_Host: numeric const, // 总的结点数

x: numeric, // 真实位置的x 坐标

y: numeric, // 真实位置的y 坐标

Xbound: numeric, // 布置区域的宽度

Ybound: numeric, // 布置区域的长度

mBean_r: numeric const, // 信标的通信半径

node_r: numeric const, // 待定位节点的通信半径

mobility_Model: string, // 移动模型

position_Algorithm: string; // 定位算法

submodules:

mobility: mobilityModel;

parameters:

XRange = Xbound,

YRange = Ybound;

display: "p=260,64;b=24,26";

Comm: Comm;

parameters:

ismBean = ismBean,

mBean_r = mBean_r,

node_r = node_r;

display: "p=148,62;b=104,10";

position: position_Algorithm;

parameters:

max_v = input,

delta = input,

announceInterval = input,

updateInterval = input;

display: "p=148,171;b=104,10";

connections:

mobility.out --> Comm.fromMobility;

position.toBottom --> Comm.fromPosition;

Comm.toPosition --> position.fromBottom;

display: "p=10,10;b=287,250";

endmodule

然后建立网络。网络中有MobileBeacon 和UnknownNode 两种节点，seed 是信标节点，node 是待定位节点。网络中节点数为numHost，信标节点的比率为anchorFraction。网络的拓扑图如下：
图5- SEQ 图5- \* ARABIC 3网络拓扑结构图

Fig.5- SEQ Fig.5- \* ARABIC 3 Network topology

相应的网络模型描述文件network.ned 文件为：

import "mobileHost.ned";

module MobileSensorNet

parameters:

numHost: numeric const,

anchorFraction: numeric const,

playgroundSizeX: numeric const,

playgroundSizeY: numeric const;

submodules:

mBean: MobileHost[numHost * anchorFraction];

parameters:

ismBean = 1,

numHost = numHost,

Xbound = playgroundSizeX,

Ybound = playgroundSizeY,

x = intuniform(0,playgroundSizeX),

y = intuniform(0,playgroundSizeY);

node: MobileHost[numHost - numHost * anchorFraction];

parameters:

ismBean = 0,

numHost = numHost,

Xbound = playgroundSizeX,

Ybound = playgroundSizeY,

x = intuniform(0,playgroundSizeX),

y = intuniform(0,playgroundSizeY);

endmodule

network mobilesensornet : MobileSensorNet

endnetwork

5.2.2定位过程仿真程序设计

仿真中，我们要用 C++代码定义simple 模块的行为。这个仿真包含三个简单模块：Mobility，Comm 和Positioning。Mobility 定义节点的移动方式，Comm 定义节点间物理层，Positioning 定义改进的DV-Hop定位算法。这里主要介绍改进的DV-Hop定位算法的仿真实现。

根据本文3.1.2节中改进DV-Hop定位算法的过程，移动信标在网络中广播自己的位置分组并接收网络中各节点发回来的数据包，计算网络平均跳距离。未知节点接收这些平均跳距离的数据包，并将其与自己已经接收到的移动信标的位置信息来计算到各信标节点的距离，列表后，再采用动态选择算法来选择参与三边定位计算的虚拟信标节点。

在两种不同的移动模型下，信标节点广播位置分组的方式也不一样，在高斯马尔可夫模型下，节点周期性定时发送，而按第四章中规划路径移动时，则按每移动到定位未知节点时广播。其广播的时间驱动和事件驱动分别如下。

周期性广播需要按计时器周期进行：

cMessage *anu_Msg = new cMessage("Annouce");

anu_Msg->setedg(DVHOP_MSG_ANNOUNCE_LOCATION);

schAt(simTime()+anu_Interval, anu_Msg);

到达预定位置广播按事件驱动进行：

cMessage *anu_Msg = new cMessage("Annouce");

anu_Msg->setedg(DVHOP_MSG_ANNOUNCE_LOCATION);

schAt(simArrive()+anu_PosAt, anu_Msg);

根据3.1.2规定的广播格式，广播的信息包括当前运动到第几个点，当前位置坐标，网络跳数(初始化为0)，广播的位置信息格式为：

message LocAnnounce

{

fields:

int id;

double x=0;

double y=0;

int hops=0;

};

未知节点在获得平均跳距离和到信标节点的跳数后运行改进的DV-Hop定位算法。

5.3基于移动信标优化路径的定位算法性能分析

基于移动信标优化路径的定位算法的定位误差分析通过与DV-Hop定位算法来进行比较，为了分析提出的规划路径的优异性，比较在两种不同的移动模型下的改过DV-Hop定位算法的定位误差。

由于DV-Hop定位算法本身不基于移动信标节点，信标节点在网络中是预先固定安装好，信标在网络中的密度及分布都会影响定位的误差。我们仿真分析同样的网络模型下，信标节点从10个增加到20个时的定位误差及定位覆盖率。

在本文限定的条件下可以看到DV-Hop定位算法在信标节点的密度达到0.2时，其定位的误差约23%，定位覆盖率93%左右，当信标节点密度达到0.3时，定位的误差、定位覆盖率分别可以达到21%和97%。而本文提出的基于移动信标优化路径的定位算法在虚拟信标节点的密度为0.2时，定位的误差、定位覆盖率分别为16%和97%。当虚拟信标节点密度达到0.3时，定位的误差、定位覆盖率分别可以达到14%和98%。以上的数据均为经过20次独立仿真结果平均值获得。即使是基于高斯马尔可夫移动模型下进行移动和广播的定位方法，其定位误差和定位的覆盖率也优于DV-Hop定位算法。同样的信标个数其定位的性能都优于DV-Hop定位算法，而更为重要的是，在本文提出的定位算法的虚拟信标的密度是通过单个移动信标在网络中移动来形成的，相较于要通过人工布置的固定信标节点，无疑将更加有效，并可降低网络的成本，减少定位的成本，提高定位的效率。

EMBED Visio.Drawing.11

图5- SEQ 图5- \* ARABIC 4 定位算法的误差分析

Fig.5- SEQ Fig.5- \* ARABIC 4 Localization algorithm error analysis

EMBED Visio.Drawing.11

图5- SEQ 图5- \* ARABIC 5定位算法的覆盖率分析

Fig.5- SEQ Fig.5- \* ARABIC 5 Localization covering ratio analysis

在OMNeT++仿真平台上运行两种移动模型下的改进DV-Hop算法，其在网络中的移动路径及定位的节点的网络图如下图5-5所示。节点[5]、[23]、[13]、[12]、[17]、[28]、[2]、[10]是移动信标节点及在其移动路径中访问过的位置形成的移动信标。除节点[21]由于定位信息不足无法定位，其它节点均已定位。在网络中，网络未定位前共有30个未知节点，移动信标节点在网络中移动形成9个虚拟信标节点，虚拟信标的密度达到0.3，其定位的误差经过多次测量求平均值可以达到14%，定位覆盖率也可达到98%。

EMBED Visio.Drawing.11

图5- SEQ 图5- \* ARABIC 6节点分布及定位示意图

Fig.5- SEQ Fig.5- \* ARABIC 6 Nodes distributed and localization sketch map

图5-6是其中的一次节点定位图。从图中我们看到，定位覆盖率除个别偏远的节点因信标节点无法到达不能定位外，其余节点均可定位，其定位覆盖率高于一般的DV-Hop定位算法，定位的性能分析可见图5-4和图5-5的分析。

基于移动信标的定位算法，是一种分布式的定位计算方法，各节点接收移动信标的定位信息进行自身定位计算。

5.4 本章小结

本章主要介绍了信标动态调整的传感器网移动节点定位系统的实验环境、定位仿真平台的模型建立及相关程序设计，设计了移动信标的移动模型，将第四章的优化路径算法应用于仿真环境中的移动信标节点，并在网络仿真环境中进行定位过程仿真及数据分析，定位结果证明了基于移动信标优化路径的定位算法具有良好的定位效果。结论与展望

1、 文章总结

为了提高无线传感器网络节点定位精度，降低网络定位的成本，提高定位效率，本文提出了基于移动信标优化路径的无线传感器网络节点定位算法，该算法在无线传感器网络中引入移动信标节点在网络中漫游并广播自己位置信息来帮助网络中的未知节点进行定位，结合经典的无需测距的定位算法DV-Hop定位算法，通过动态的选择移动信标节点在网络中构造的虚拟信标节点来计算网络平均 跳距离，从而实现网络的定位。为了进一步提高网络的定位精度，本文还研究了移动信标在网络中的移动模型和移动路径的规划，并研究其在网络中广播信息的周期对定位效果的影响，实现移动节点高效定位。本文的完成的工作有：

（1）阐述了无线传感器网络节点定位算法的研究背景与国内外研究现状，并根据研究的情况，针对无线传感器网络无需测距的定位算法在定位成本及定位精度上的问题，对无线传感器网络节点定位算法进行研究。

（2）研究常用的基于信标节点定位算法和无需测距的定位算法，提出基于移动信标优化路径的定位算法，算法在DV-Hop定位算法的基础上引入移动信标节点，并研究网络中移动信标构造的虚拟信标的动态选择算法，仿真证明，算法有效提高了无线传感器网络节点的定位算法的精度和降低了网络的定位成本，提高了定位的效率。

（3）结合移动信标在网络中的移动模型，研究了移动信标节点在网络中的优化路径的获取，研究信标节点的最优路径及广播信息周期。提高定位算法的定位精度，算法对随机网络的适应性。最后通过在OMNeT++的仿真实验平台上建立网络及节点的模型，通过仿真实验证明基于移动信标节点优化路径的定位算法具有更好的定位效果。

2、未来工作展望

下一步传感器移动节点定位算法需要进一步研究的问题主要包括：

（1）实现基于三维空间的节点定位，扩展基于移动信标定位的应用范围。

（2）研究更合理的移动信标路径获取方法，通过规划移动信标的路径轨迹，使其也能适应于随机稀疏的无线传感器网络，进一步提高了定位的效率。
参 考 文 献

任丰原，黄海宁，林闯．无线传感器网络[J]．软件学报，2003，14(7)：1282-1291

邱岩．无线传感器网络节点定位技术研究[J]．计算机科学，2008，35(5)：47-50

段渭军，王建刚，王福豹．无线传感器网络节点定位系统与算法的研究和发展[J]．信息与控制，2006，35(2)：239-245

王福豹，史龙，任丰原．无线传感器网络中的自身定位系统和算法[J]．软件学报, 2005. 16(5): p. 857-868.

He T, Huang CD, Blum BM, Stankovic JA, Abdelzaher T. Range-Free localization schemes in large scale sensor networks[C]. In: Proc. of the 9th Annual Int’l Conf. on Mo-bile computing and Networking. San Diego: ACM Press, 2003. 81-95.

B, W.H., L. H, C. J, Global positioning system. 1997.

Savvides A, Han C, Srivastava M B, Dynamic fine-grained localization in ad-Hoe networks of sensors [J]. Proceedings of ACM MobiCom, 2001.

Paramvir Bahl, Venkata N. Padmanabhan RADAR：An inbuilding RF-based user location and tracking system [C]. In Proceedings of IEEE Infocom 2000, Tel-Aviv, Israel. 2000.2: 775-784.

Niculescu D, Nath B. Ad Hoe positioning system (APS) using AOA[C]. In: Proc.of the IEEE INFOCOM.San Francisco: IEEE Computer and Communications Societies, 2003:1734-1743.

Niculescu D, Nath B. DV-base positioning in AD Hoc networks [J]. Kluwer Journal of Telecommunication System, 2003. 22(1):267-280.

Shuang Tian, Xinming Zhang, Pengxi Liu.A RSSI-Based DV-Hop Algorithm for Wireless Sensor Networks.Wireless Communications[C]. Networking and Mobile Computing, 2007, WiCom 2007.International Conference on. 21-25 Sept.2007:2555-2558.

李善亮，黄刘生，吴俊敏．基于连通性的传感器节点定位算法研究[J]．计算机工程，2008.34.7:115-117.

Changhua W, Weihua S, Ying Z.Mobile sensor networks self localization based on multi-dimensional scaling [C]. In Proceedings of ICRA'2007. p.4038~4043.

Bin Xiao, Hekang Chen, Shuigeng Zhou. A walking beacon-assisted localization in wireless sensor networks[C]. In Proc. 2007 IEEE International Conference on Communications (ICC 2007), Glasgow UK, June 2007:3070-3075.

Stevens-Navarro, E Vivekanandan, V Wong. Dual and Mixture Monte Carlo Localization Algorithms for Mobile Wireless Sensor Networks[C]. In: Wireless Communications and Networking Conference, 2007.WCNC2007[C]. IEEE11-15, 2007:4024-4028.

Bergamo P, Mazzimi G. Localization in Sensor Networks with Fading and Mobility [J]. 2007, IEEE Press: 750-754.

孙利民等. 无线传感器网络[M]. 北京: 清华大学出版社. 2005.

Lingxuan Hu, David Evans. Localization for Mobile Sensor Networks [J]. 2004, ACM Press: New York: 45-57.

Terence Chung Hsin SIT, Zheng LIU, Marcelo H ANG Jr. Multi-Robot Mobility Enhanced Hop-Count Based Localization in Ad Hoc Network[J]. Robotics and Autonomous Systems, 2007. 55(3): 244-252.

杨旸. 传感器网络节点定位技术研究[D]. 浙江: 浙江大学, 2006.

史庭俊, 桑霞, 徐力杰. 一种基于信任度的DV-Hop改进定位算法[J]. 微电子学与计算机2008,25,10: 100-102.

李晓维. 无线传感器网络技术[M]. 北京: 北京理工大学出版社. 2007.

董齐芬, 冯远静, 俞立. 基于移动信标节点的无线传感器网络定位算法的研究[J]. 传感器技术学报, 2008. 21(5): 823-827.

李石坚, 徐从富, 杨旸. 面向传感器节点定位的移动信标路径获取[J]. 软件学报, 2008. 19(2): 455-467.

Guolin Sun, G.uo Wei. Comparison of distributed localization algorithms for sensor network with a mobile beacon[C]. In: Proc.of the IEEE Int'l Conf.on Networking, Sensing and Control.2004.536-540.

Galstyan A, Krishnamachari B, Lerman K, Pattem S. Distributed online localization in sensor networks using a mobile target[C]. In Proc. ACM/IEEE IPSN, Berkeley, USA, April 26-27, 2002: 61-70.

汪丽华, 张国煊, 申兴发. 移动锚节点辅助的DV-Hop定位方法研究[J]. 杭州电子科技大学学报, 2008. 28(5): 131-134.

Sichitiu M L, Ramadurai V. Localization of wireless sensor networks with a mobile beacon [C]. Proc of MASS．Piscataway, NJ: IEEE, 2004:174-183.

黎大鹏. 基于锚节点动态调整的传感器网络移动节点定位系统的研究[D]. 广州: 广东工业大学, 2009.

Srdan Capkun, Maher Hamdi, Jean-Pierre Hubaux. GPS-free positioning in mobile Ad-Hoc networks[C]. Proceeding of the 34th Hawaii International Conference on System Sciences-2001.

Rajagopal Iyengar, Biplab Sikdar. Scalable and Distributed GPS free Positioning for Sensor Networks[C]. In Proc. of IEEE Int'I Conf. on Communications 2003. Vol.l, Anchorage: IEEE Communications Society, 2003.338-342.

Nisanka B, Priyantha, Hari Balakrishnan, Erik Demaine. Anchor-Free Distributed Localization in Sensor Networks [R]. Technical Report MIT-LCS-Tr-892, MIT Lab for computer Science, April 2003.

Neal Patwari, Robert J, Yanwei Wang. Relative location in wireless networks [J], IEEE Vehicular Technology Conference 2,n 53ND,2001:1149-1153.

陈维克, 李维峰. 基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报. 2006, 30 (2): 265-268.

冯浩然,袁睿翕, 慕春棣.无线网络中基于信号强度的定位及算法比较[J].计算机工程与应用. 2006, 42(32): 1-3, 11.

王海东, 孙利民. 无线传感器网络的定位机制[J]. 计算机科学, 2006Vol. 33 No. 4. 36-49.

L. Akyildiz, W.Su, Y. Sankarasubramaniam, E. Cayirci. A Survey on Sensor Network [J]. IEEE Communication Magazine, Aug. 2002: 102-114.

Stankovic J A, Abdelzaher T F, Lu Chenyang. Real-Time Communication and Coordination in Embedded Sensor Networks [J]. Proceedings of the IEEE, 2003, 91(7).

Min Yin, Jian Shu. The Infltmenee of Beacon On DV-hop in Wireless Sensor Networks[C]. Hunan: Proceedings of the Fifth International Conference on Grid and Cooperative Computing Workshops, 2006: 118-122.

Camp T, Boleng J, Davies V. A Survey of Mobile Models for Ad Hoc Network Research [J], Trends and Applications, 2002, 2 (5):483-502.

Niculescu D, Nath B. Ad-hoc positioning system (APS) [J].Prco.of the IEEE GIOBECOM, San Antonio, 2001:2926-2931.

Tian Shuang, Zhang Xinming, Wang Xinguo. A Selective Anchor Node Localization Algorithm for Wireless Sensor Networks[C].2007 International Conference on Convergence Information Technology, 2007.145:358-362.

Jabbari B, Zhou Y, Hillier F. Random Walk Modeling of Mobility in Wireless Networks [J]. In Proc.of IEEE VTC’98, 1998, 5(20)：639-643.

Akyildiz I F, Lin Y B, Lai W R. A new random walk model for PCS networks [J].IEEE Journal of Selected Areas in Communications, 2000, 18(7):1254-1260.

Christian Bettstetter. Smooth is better than shape：A Radom mobility model for simulation of wireless networks [J]. In proc. of ACM MSWIM, 2001, 5 (7):19-27.

Sun GL，Guo W. Comparison of distributed localization algorithms for sensor network with a mobile beacon[C].Proc of the IEEE Intel conf on Networking，Sensing and Control, 2004:536-540.

徐云剑, 彭沛夫, 郭艾寅, 张桂芳. 基于蚁群算法的WSN移动信标路径获取研究[J].计算机工程与应用,2008,44(28):109-112.

林惠君, 吴秀锦. 无线传感器网络仿真模拟技术[J].中国新通信(技术版). 2008.6:10-14.

王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法[J].软件学报, 2005. Vol.16, No.5:856-859,866.攻读学位期间发表的学术论文

[1] 谢晓松,程良伦. 传感器网络基于移动信标改进的DV-Hop定位算法. 计算机应用与软件, 已录用，拟在 2010 年 11月刊发表，稿件编号：A09110257，文章应用于论文的第三章的第一节。

[2] 谢晓松,程良伦. 传感器网络基于移动信标动态选择的定位算法. 传感器与微系统, 已录用，稿件编号：0917，文章应用于论文的第三章第二节。
攻读学位期间参加的科研项目

2009/01～至今 RFID传感器网络关键问题研究

(国家自然科学基金资助项目，编号：60673132)

RFID传感器网络及其应用技术研究

(广东省自然科学基金重点项目编号：07117421)

2008/08～2008/010 夹层玻璃生产成套设备智能控制系统的研究

(广东省教育部产学研联合项目，编号：2008071)

2008/04～2008/08 基于嵌入式运动控制器的水火弯板机数控系统设计及开发

(横向项目，编号：2007301)

独创性声明

秉承学校严谨的学风与优良的的科学道德，本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包含本人或其它用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明，并表示了谢意。

本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论文成果归广东工业大学所有。

申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。

指导教师签字：
论文作者签字：
年 月 日
致 谢

本文从选题、开题到撰写都是在我尊敬的导师程良伦教授的悉心指导下完成的。值此论文付梓之际，谨向我的导师程良伦教授致以诚挚的感谢和崇高的敬意。程老师渊博的专业知识、深厚的学术造诣、严谨的治学态度和忘我的工作精神，以及谦和开明的长者风范，深深感染和激励着我在今后的学习和工作中不断的进步。尤为让我感动和难忘的是，程老师非常注重研究生的培养工作，每周都会百忙之中抽出许多宝贵的时间来与我们一道进行学术专题探讨，指导我们科研。

在这三年的硕士学习期间，我得到了很多人给予的关心、鼓励和支持，正是由于有了他们热情的帮助，我才能克服求学路上的各种困难并顺利地完成学业。在此谨向他们表示我真挚的感谢！我要感谢实验室的每一位成员，他们为我提供了优良的设施和自由开放的治学环境，使我不仅学会了科学的思考方式，掌握了通用的研究方法，而且还明白了许多待人接物与为人处世的道理，这些都将使我受益终生。

同时还要感谢陪伴我度过充实三年的实验室同学。感谢陈伟、陈聪传、邓洁、林观康、李少春、潘健华、汤子隆和衷柳生在三年里的关心和帮助，与他们的讨论和学习让我既懂得了丰富的技术知识，又学到了如何相互体谅，相互支持。感谢江伟欢、胡晓文和黎大鹏等师兄在实验室科研项目及学习生活中给予的帮助。感谢林钟楷、程伟和彭蓓雷等师弟师妹们在课题上的帮助。

感谢担任本论文评审和评阅的各位专家教授，谢谢你们对本文提出宝贵的建议和意见！

谢晓松

2010年5月20日于广州
PAGE 61


广东工业大学硕士学位论文
STYLEREF "标题 1" \* MERGEFORMAT 摘 要
PAGE 60

STYLEREF "标题 1" \* MERGEFORMAT 参 考 文 献
攻读学位期间发表的学术论文
广东工业大学工学硕士论文
攻读学位期间参加的科研项目
独创性声明
广东工业大学工学硕士学位论文
致谢