基于OMNeT++的无线传感器网络节点定位方法研究_图文

分类号——
UDC



级.

学校代码

!鳢窆2

武臃理歹大署









目基王塑迢业鲍垂线堡盛墨圈终堇:量塞焦麦洼壁宝

姓名 指导教师
单位名称

墼查堑


职称
..

勤熬撞


学位

亟±

盛婆墨墨盘堂筮堕堂瞳 型盘主


邮编玺QQ鱼圣 学位

姓名
副指导教师

职称


到耋送


谴±

单位名称 申请学位级别 论文提交日期
学位授予单

盛垫堡墨盘堂煎遂堂瞳

邮编垒曼QQ鱼3

巫±

学科专业名称塞通焦:塾墨猩盈蕉剑
2011.5

答辩委员会

201

1年5月

1 1]l IJ IfJl l lf fl Jf J Jl 1 ]l l rl rlf JUl
Y1 880625

独创性声明
本人声明,所呈交的论文是本人在导师指导下进行的研究工作及

取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外, 论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得
武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一

同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说
明并表示了谢意。

期:尘!L』

学位论文使用授权书
本人完全了解武汉理工大学有关保留、使用学位论文的规定,即

;学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,
允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的

全部内容编入有关数据库进行检索,可以采用影印、缩印或其他复制
手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有

关机构或论文数据库使用或收录本学位论文,并向社会公众提供信息
服务。 (保密的论文在解密后应遵守此规定)

研究生(签名):衄导师(签名):窆!趔曼 日期.世
蚕f克冲



武汉理工大学硕士学位论文





近年来,集成了无线通信、分布式处理、微机电系统等技术的无线传感器

网络(Wireless SensorNetworks)得到了迅速发展,并成功应用到了很多领域。
而在大多数应用中,获取传感器节点的位置信息是最基本的要求,节点自定位

技术是无线传感器网络研究的关键问题之一,是无线传感器网络迈向实用化进
程的基础和前提。因此,对无线传感器网络的节点定位技术展开研究,具有十 分重要的理论和现实意义。 本文首先对无线传感器网络特点及研究现状进行了全面深入的分析,进而 对分布式多能量级节点定位算法中导标优化选择策略进行了研究;基于Monte

Carlo方法,研究了无线传感器网络中导标移动下的节点定位问题。最后,提出
的理论及算法均采用离散事件仿真软件OMNeT++进行了仿真验证。具体工作如 下: 1.)为了克服多能量级节点定位算法中计算复杂度高的问题,提出了一种导

标优化选择策略,在降低算法复杂度的同时,有效提高了节点定位精度。其基
本思想是:通过分析节点的物理拓扑结构,从众多用于定位的导标中选择三个 有效导标,并使三个导标节点相互之间的距离尽可能远,最后基于质心算法思 想实现了节点位置的有效估计。 2)针对移动无线传感器网络中节点定位问题,将能量分级思想进一步引入 动态网络中,并对Monte Carlo方法进行改进,提出了一种基于Monte Carlo的 移动无线传感器网络节点定位算法。其主要思想是:移动导标周期性发射不同 能量级的广播信号,未知节点接收感知范围内的导标定位信息,确定自己所处 的限定区域。利用改进的Monte Carlo方法,采用较少样本实现了节点的位置估

计。为避免导标共线时出现节点定位失效情况,引入共线度限制因子(Collineadty
Limiting

Factor,CLF),提出了一种导标共线度约束策略,很好地解决导标共

线问题。

关键词:无线传感器网络;节点定位;多能量级;Monte Carlo;OMNeT++

武汉理工大学硕士学位论文

Abstract Networks(WSNs),which硫e孕at鼯wireless
SO

In recent

years,Wireless

Sensor

communication,distributed

computing,micro-electromechanical system and

on,

has developed rapidly and it has been

expanded

to

many

fields.It is

one

of the most

basic requirements for nodes in WSNs
is
one

to obtain their positions.So node localization

of key

problems

and

is the basis
on

and prerequisite

for practical applications of

WSNs.Therefore,studying
theoretically

node localization

is of great

importance

both

and practically for

WSNs.
on

Firstly,the characteristics and some novel research

WSNs

is

analysed

in

depth.Then
localization

the beacon selection optimization strategy in distributive

multi-energy
node

node localization algorithm is

studied in

this paper.This
on

paper

also

studies the

problem in mobile
paper

WSNs based

Monte Carlo method.Finally,all the

theories and algorithms are
The main work of the

simulated

witll discrete

event

simulator
are

called OMNeT++. summarized as

and research

contributions

briefly

follows: 1)In order to overcome the high

computational complexity anchor

concentric anchor

beacon localization algorithm,an

problem selection scheme

in
is

proposed.The
Based

proposed

scheme

carl

not only

reduce algorithm complexity,but

also

improve the localization accuracy.The main idea of the algorithm is as following:
on

the network physical topology characteristics,only three

anchors selected

among all the neighboring.The

selected

anchors

are

used for

node localization.

What’S more,the three beacons between

should be

selected

SO

tllat the slim of the

distances

any two of thcrn is the farthest among all possible

combinations of neighbor
centroid

beacons.The estimation location can be calculated based on 2)The
which
multi—energy idea is further introduced
to

algorithm.
problem of node
on

address the

localization in mobile

sensor network.A

localization

algorithm based
power
node

Monte Carlo,

is suitable for mobile wireless

sensor

network is proposed in this paper.Each
at

Mobile anchor

emits
or

beacon

information

different

levels.From the determine which
is

information received by each unknown nodes,the particular ring

sensor

Can

inner circle it lies within from the

correspondent anchor,which

lI

武汉理工大学硕士学位论文
called constraint region.The positions of unknown


nodes
on

are

able to be

estimated

by

bunch

of particles which

ale

sampled

based

an

improved Monte

Carlo

Localization
concept

scheme.In order

to

further enhance localization performance,the

called

Collineality Limiting Factor(CLF)is

introduced beacon

to avoid localization
selection

failure
put

caused

by beacon collineation.By using CLF,a
solve the

scheme

is

forwarded to

beacon eollineation problem.

Key Words:Wireless Sensor Netwok;Node localization;Multi—energy;Monte Carlo; oMNeln斗

III

武汉理工大学硕士学位论文





第1章绪论……………………………………1
1.1课题来源………………………………………….1 1.2研究的背景及意义…………………………………..1 1.2.1无线传感器网络概述……………………………..1 1.2.2无线传感器网络的特点……………………………3 1.2.3国内外研究现状…………………………………3 1.2.4节点定位的目的及意义……………………………6 1.3研究内容及论文结构…………………………………7 1.3.1论文的主要研究工作……………………………..7 1.3.2论文的结构安排…………………………………8

第2章仿真软件简介与节点自定位技术……………….9
2.1仿真工具介绍………………………………………9
2.1.1 OMNeT++..............................................9
2.1.2 MATLAB..............................................13

2.2无线传感器网络的自定位技术…………………………13 2.2.1节点定位的基本概念…………………………….14 2.2.2节点间的测距(角度)方法.………………………14 2.2.3节点定位的计算方法…………………………….15 2.2.4节点定位算法的分类…………………………….16 2.2.5定位性能评价………………………………….18 2.3主要应用领域……………………………………..20 2.4本章小结…………………………………………21
第3章

多能量级节点定位性能分析………………….22

3.1多能量级节点定位原理………………………………22 3.2导标选择问题……………………………………..23 3.3算法描述…………………………………………25 3.4算法适应性分析……………………………………28 3.4.1仿真实验设计………………………………….28 3.4.2性能评价……………………………………..32

武汉理‘T大学硕十学位论文

3.5本章小结…………………………………………34
第4章

基于多能量级的移动节点定位算法…………….35

CARLO方法概述…………………………………35 4.2移动模型介绍……………………………………..36
4.1 MONTE

4.2.1随机路点模型………………………………….36 4.2.2随机路径模型………………………………….37 4.2.3随机方向模型………………………………….37 4.3限定区域的确定……………………………………38 4.4算法设计…………………………………………38 4.5精度改善策略……………………………………..39 4.6算法模型…………………………………………40 4.7性能评估…………………………………………43 4.7.1共线度限制因子………………………………..44 4.7.2样本数量……………………………………..44 4.7.3节点数目……………………………………..45 4.7.4导标移动速度………………………………….46 4.7.5导标密度……………………………………..46 4.7.6测距误差……………………………………..47 4.7.7不同移动模型………………………………….48 4.8本章小结…………………………………………49

第5章总结与展望….……….………………….50
5.1全文总结…………………………………………50 5.2未来工作展望……………………………………..5l

谢…….………………………………...53 参考文献……………...……..………………..54 攻读硕士学位期间发表的论文及参与的科研项目…………60




武汉理工大学硕士学位论文

第1章
无线传感器网络(Wireless

绪论

Sensor Networks,WsN)因具有广泛应用前景而

受到国际的普遍关注,被认为是21世纪最具影响力的网络技术之一。它综合了 嵌入式计算、传感器技术、无线通信、分布式处理等技术,利用智能化的微型

传感器协作完成对监控场景的实时监测及监测对象信息的感知与采集,并通过
自组织网络将数据传输到客户终端,实现网络、物理世界及人类社会的有效互 通。由于无线传感器网络的巨大发展潜力,已经引起了各国政府的高度重视, 正在被人们扩展应用到其他重要领域,像典型的“物联网”、海事监控传感网络等。

1.1课题来源
本学位论文的研究工作主要得到国家青年自然科学基金项目“移动无线传 感器网络节点定位方法研究"(60703099)的资助。

1.2研究的背景及意义
1.2.1无线传感器网络概述
无线传感器网络是是--f-j交叉学科,是一种全新的网络技术,是微机电系 统(MEMS,Micro.Electro.Mechanism System)、片上系统(SOC,System
011

Chip)

和无线通信技术高度集成而孕育出的一种新型信息获取和处理方式【lJ。无线传感 器网络是由大量无处不在、具有通信和计算能力的微型传感器节点,以多跳通 信的方式构成的自组织网络系统,能够协作地检测、感知和采集监控区域的各 种环境参数或检测对象信息,由嵌入式计算单元对信息进行处理,并通过无线 通信网络将信息传送至远程用户,为远程用户提供详尽而准确的信息,实现“无 处不在”的计算理念【2】o由于传感器节点的微型化及低成本特性,使得它们可被

放置于大量特殊环境下协同工作,通过构建大规模的自组织网络实现对诸多环
境对象的有效监控。 无线传感器网络实现了物理世界与人类社会之间的互联互通,为人与自然 界丰富多样的信息交互提供了技术条件。利用分布式自组织网络将各种功能的 传感器、便携设备、控制器及处理器连接到Internet,可实现对物理世界中感兴

武汉理工大学硕士学位论文

趣对象的实时监控,最终实现普适计算(Ubiquitous Computing,UC)pJ。 无线传感器网络具有自组织、功耗小、可扩展性强、能适应恶劣环境等优 点,网络内包含不同类型的具有感知、计算、通信功能的传感器,可有效感知 监测环境中温度、湿度、压力及移动物标的各种特性(如:速度、方向、大小) 等对象信息。无线传感器网络扩展了现有网络的功能和人们获取信息的能力, 大量微型传感器节点被嵌入到我们生活的物理世界中,极大地影响了人们的生 活,在众多领域具有极为广泛的应用前景【4】,主要表现在国防军事、工业控制、

农业生产、环境监控、医疗卫生、家庭护理等领域,特别在空间探索和灾难拯
救等特殊的领域有其得天独厚的技术优势。 不同于传统网络,无线传感器网络主要由传感器节点(SensorNode),汇聚 节点(SinkNode),网络或通信卫星、用户终端等部分组成。在许多监控场景中, 传感器节点被随机布撤在监控区域内,节点通过自组织形成感知网络,收集感 兴趣的数据信息,通过“多跳”路由方式将数据传输到汇聚节点,汇聚节点可直接 与网络或通信卫星相连,由网络或通信卫星将数据发送给用户终端,最终实现 用户终端与传感器节点的通信,用户终端也可以以同样的方式与传感器节点进 行信息的传递。
执行器
ADC

数据接口

CP

传感器 感知单元

八 V

CPU

存储器 处理单元

爪 V

无线连接

无线电接收器
传输单元

——\十—/
能量单元

传感器节点

图1.1

无线传感器网络节点结构

在不同应用场景中传感器节点的功能不同,致使传感器节点的结构也不尽 相同,但一般都是由数据感知、数据处理、数据传输及电源等四部分组成【5J,如 图1.1所示。传感单元主要是负责收集外界信息,并通过模/数转换器将其转换 为数字信号。数据处理单元负责信息的处理、存储,协调个单元之间的工作, 而传输单元负责对信息的收发及与其他节点进行无线通信等工作。能量单元则 为以上三个单元提供运行所必需的能量,是传感器节点正常工作的基础和前提。



武汉理工人学硕士学位论文

1.2.2无线传感器网络的特点
与传统的无线网络,如无线局域网、移动通信网、蓝牙网络及Ad hoc网络 等相比,无线传感器网络是一种特殊的自组织网络,虽然在各种应用场合节点

分布情况各异,工作方式也有差别,但无线传感器网络大都具有以下共同特点: (1)节点众多、分布密集:由于节点能量受限,通信距离有限,而监控区
域往往比较广阔,为了有效覆盖监控区域,保证系统的容错性和抗毁性,通常 需要成千上万的节点。 (2)无线自组织:网络内节点的布设和展开无需外界预设网络设备,节点

是自主的、自治的,通过分层协议和分布式算法协调各自行为,通过自组织方
式组网,网络内没有严格的控制中心和骨干网络。 (3)节点能量受限:节点大多依靠电池供电,使用寿命有限,受环境限制,

难以更换电池或对其充电。因此,在设计节点硬件时,应重点考虑系统节能问题。
(4)计算、存储能力有限:由于传感器节点的计算能力和内存空间往往会 受到多种因素的制约和限制,节点通常处理能力和存储能力都很弱。因此,设 计廉价和低功耗的传感器节点是无线传感器网络节点设计的主要目标之一。 (5)拓扑动态变化:无线传感器网络并非一成不变的网络,网络内节点可 随意移动,也会出现节点加入或退出网络的情况,节点还会因能量耗尽而退出 网络,导致网络拓扑结构的随时动态变化。

1.2.3国内外研究现状
早在20世纪70年代美国就着手了无线传感器网络的研究工作,实现了节 点问的点对点通信。1999年9月《商业周刊》【6】将其列为21世纪最重要的21 项技术之一。随后的10余年里,WSN网络技术得到了迅速发展,不仅受到了学 术界和工业界的广泛关注,各国政府部门也对其表现了极大的兴趣,纷纷展开 了该领域的研究工作。 在美国自然科学基金的支持下,麻省理工学院、加州洛杉矶分校、康奈克 大学等许多著名高校对WSN网络的基础理论和关键的科学问题进行了相关研

究。此外,其他各国也对传感器网络表现出了极大的兴趣,投入了大量资金, 并展开了该领域的研究工作,如:日本展开了U.Japan计划、韩国开始了U—Korea
战略、新加坡推动了“下一代1-Hub”计划、欧洲也提出了旨在创建无所不在网络 社会的i2010计划。



武汉理工大学硕士学位论文

我国也十分重视无线传感器网络的研究工作,现代意义的WSN网络及其应 用研究几乎与发达国家同步启动。2001年中国科学院成立了微系统研究与发展 中心,旨在整合中科院内部相关单位,共同推进传感器网络的研究。2002年中 国国家自然科学基金委开始了对传感器网络相关课题研究的部署工作,并逐年 增加了对相关课题的资助力度。2005年,网络传感器中的基础理论和关键技术 列入重点课题计划。2010年远景规划和“十五”计划中,WSN列为重点发展产业 之一。

国内许多高校及科研单位也掀起了无线传感器网络的研究热潮,清华大学、
东南大学、中国科技大学、浙江大学、华中科技大学、天津大学、南开大学、 中国电子科技集团公司第五十二研究所等单位纷纷开展了无线传感器网络方面 的研究工作。浙江大学现代控制工程研究所成立了“无线传感器网络控制实验 室”,联合相关单位专门从事面向传感器网络的分布自治系统关键技术及协调控 制理论方面的研究。中科院电子所和沈阳自动化所分别从传感器技术和控制技 术角度入手开展工作。此外,华为、中兴等通讯公司,也加入了研究行列。 在无线传感器网络中,众多应用场景(军事应用、环境监控、病人护理等) 都是基于位置信息的。若缺少位置信息,传感器获取的数据将会失去意义。而 无线传感器网络的自身定位系统的性能好坏又将影响或制约无线传感器网络在 现实环境中的应用。国内外从不同的角度和应用出发展开了对节点定位技术的 研究工作,提出了大量的节点定位算法和定位系统,并对算法的性能进行了探 讨。 在静态网络中,许多节点定位算法逐渐被提出。近年来,能量分级思想逐 渐得到了人们普遍关注,被应用于无线传感器网络中解决节点定位问题。多能 量级(ConcentricAnchor-Beacons,CAB)节点定位算法是【7J是~种利用多能量级 广播信号实现节点位置估计的免测距分布式节点定位算法,该算法根据节点信 号强度划分能量级,利用不同导标能量环交叉区域对未知节点定位。随后人们 对多能量级节点定位算法进行了改进,蒋志鹏等【8】提出了一种同心圆改进算法, 未知节点首先确定自身所处相应能量环,然后通过重复划分定位圆环的宽度, 使定位圆环宽度逐渐减小,以此实现节点的高精度定位,但此方法增加了过多 的计算量。文献【9】利用包含未知节点的相应能量圆环交叉形成的连接线确定未 知节点的受限区域,然后求解连接线与相应能量环的交点,最后利用质心定位 原理实现未知节点的位置估计。史清江等【lo】提出了一种移动锚节点辅助的分布 式节点定位算法,未知节点接收锚节点发射的不同功率信标信号,将信标信息



武汉理工大学硕+学位论文

转化为一系列二次不等式约束,然后通过凸优化技术求解这些不等式组来逼近 未知节点位置的最佳估计。闰斌等【11】提出了一种基于功率控制的质心定位算法, 采用离散功率控制的方式对目标区域进行虚拟网格划分,从而确定出包含未知 节点的最小区域,最后以区域的质心作为该节点的估计位置。

随着对无线传感器网络节点定位方法研究的深入,基于移动导标的无线传 感器网络节点定位方法以其能量有效、分布式、可扩展性强等优点而得到了广
泛关注。L.Hu和Evans[12】将蒙特卡罗(Monte Carlo)思想引入节点定位中,提出 了适用于移动传感器网络的节点定位跟踪(Monte
Carlo

Localization)算法。为改

善蒙特卡罗算法在低导标密度下定位效果不佳的状况,w.Wangtl3】等人提出了一 种序列蒙特卡罗定位(Sequential Monte Carlo

Localization,SMCL)算法,基于概率

方法,在预先未知网络分布的情况下,利用较少的导标实现了节点准确定位。J. Sheu等【14】对蒙特卡罗算法进行了改进,未知节点利用收集的导标信息及一跳范 围内已定位的未知节点的估计位置信息完成定位,通过预测节点的移动方向进 一步提高了定位精度。此外,也有人采用极大似然估计(Maximum
Likelihood

Estimation,MLE)法t”】对节点进行定位,但需要较多的浮点运算,测距误差增大 时对定位精度影响较大。 随着无线传感器网络技术迅速发展,低成本、低能耗、多功能的无线传感

器节点设计技术逐步走向成熟,为大规模应用在其他领域提供了可能。综合了
传感器网络和互联网的“物联网”【1 6’171技术已成为当前研究的热点,2009年8月 温家宝总理在视察中科院无锡微纳传感网工程技术研究中心时,提出了“尽快建 立中国的‘感知中国’中心”,物联网被正式列入国家五大新兴战略性产业之一【l引。 同年,南京邮电大学率先成立了物联网与传感网研究院、南邮.无锡物联网研究 院、物联网科技园等,并率先实践物联网技术,实施了南京邮电大学智慧校园

项目【19删。2010年7月教育部批准了30余所高校院系建设“物联网工程”、“传
感网技术”、“智能电网信息工程”等物联网相关专业,全国各大高校争先展开了

物联网的相关研究工作。
由于无线传感器网络与海事监控领域的信息需求具有很强的适应性,基于 无线传感器网络的海事监控传感系统(或称为“海事监控传感网络”)具有广泛的 应用前景。Kavelaars等【2l】采用50个节点构建了浮标传感网络监控系统,并将节 点分层部署进出港口船舶的周围实现对水上水下潜在危险物实时监测,这是从 实验角度论证无线传感网络在海事监控中的适应性。Carapezza等对无线浮标传 感网络系统的可行性、系统架构及组成等方面进行了实验性研究,设计出了浮



武汉理工大学硕十学位论文

标节点模型[221。刘克中、Yang等【23埘】从海事监控要素整体需求出发明确提出了 海事监控传感网络(Maritime
Surveillance Sensor

Networks)的概念,并对海事

监控传感网络的系统结构及功能进行了理论研究,并对海事监控传感网络的数 据传输及能耗等方面进行仿真性实验研究。 伴随着无线传感器网络在理论研究方面的不断成熟,无线传感器网络的研 究工作也逐渐向实用化转变。但由于传感器节点的能量、处理能力、存储能力 和通信能力等都十分有限,导致无线传感器网络在网络设计和信息处理等诸多 方面面临巨大挑战。因此,无线传感器网络也给科技工作者提供了巨大的研究 空间。而节点位置信息是无线传感器网络大多数应用的基础和前提,这也是本 文研究的出发点。

1.2.4节点定位的目的及意义
无线传感器网络主要是用来感知、检测网络覆盖区域中的各种环境特性。 节点的位置信息对许多无线传感器网络应用的有效性起着至关重要的作用,节 点自定位技术是无线传感器网络的关键和支撑技术之一【25】。因此,展开对无线 传感器网络节点定位的研究具有十分重要的理论和现实意义。 与一般的计算机网络相比,无线传感器网络使得网络世界与物理世界之间 建立了更为密切的联系,节点收集的数据只有结合位置信息才有实际意义【26】。 许多无线传感器网络的研究成果都表明了节点位置信息的重要性。对于无线传 感器网络的大部分应用场合,诸如水文、火灾、潮汐、生态学研究、飞行器设 计等课题中采用无线传感器网络进行信息收集和处理,传感器节点的位置信息

是不可或缺的【271。无线传感器网络在军事战术通信网的应用中,节点通过自组
织构成网络收集战术信息,而节点的位置信息是作战指挥的关键依据。节点发 回的战术信息与节点当时所处的位置有密切关系,没有位置信息的支持,这些 战术信息将失去意义。在目标跟踪应用中,根据节点的位置信息,可以感知、 检测到监测对象的相关信息,实现目标的跟踪定位【2引。因此,从应用角度来讲, 传感器节点的定位是传感网络中最为重要和传统的问题,研究具有可扩展性的 传感器网络定位系统是该领域的主流问题之一【29】。 此外,节点的位置信息还可以为其他协议层的设计提供帮助,无线传感器 网络的很多通信协议是在已知节点位置的基础上运行的。在应用层,节点位置 信息对基于位置信息选择服务的应用是不可缺少的;在网络层,位置信息与传



武汉理工大学硕士学位论文

输距离的结合,使得基于地理位置的路由算法成为可能。研究表明,基于节点 位置信息的路由策略能够更加有效地通过多跳方式在无线传感器网络中传播信
息【30】。另外,基于节点的已知位置可优化网络运行期间的值守调度机制,使网 络中冗余节点不定期地轮休以延长寿命【3¨。目前,不同应用场景下的节点定位

问题已成为无线传感器网络迈向实用化进程的重要基础和前提,是无线传感器 网络的重要研究方向之一。 当前,无线传感器网络节点定位依然面临着诸多困难,设计节点定位方法
时,需要考虑其内在的特点,如经济性、可扩展性、自适应性及鲁棒性等。如

何有效解决传感器网络中节点位置信息获取问题,依然是一个十分重要且棘手 的具有挑战性的研究课题。

1.3研究内容及论文结构
1.3.1论文的主要研究工作
本文首先对无线传感器网络进行了概述,简单介绍了无线传感器网络的特 点,阐述了研究节点定位技术的目的及重要意义;接着讨论了无线传感器网络 的自定位技术,介绍节点定位的常用测距方法、位置计算方法,对节点定位算 法进行了分类,并对常用的几种网络仿真软件进行了比较分析;对多能量级节 点定位算法进行改进,提出了一种导标选择策略,并利用OMNeT++仿真软件分 析了算法的适应性;基于能量分级思想,提出了一种改进Monte Carlo的移动节 点定位算法,并仿真验证了算法的各种性能。 本文的主要研究工作包括:

1)主要对无线传感器网络进行了概述,分析了无线传感器网络的系统结构
及特点,并对无线传感器网络节点定位技术的研究现状进行了分析,论述了节 点定位技术的研究目的及意义。 2)介绍了多能量级节点定位算法的定位原理,在分析节点信号传播特性的 基础上,提出了一种利用多能量级广播信号实现节点位置估计的分布式节点定 位方法。提出的导标优化选择策略,有效地减小了计算量,并提高了节点的定

位精度。利用离散事件仿真软件OMNeT抖对算法的适应性进行了分析,提出的
定位方法在定位精度及能量有效性等方面均较传统免测距定位方法(Centroid算

法)有明显的优势。



武汉理工大学硕士学位论文

3)基于多能量级节点定位原理,对移动无线传感器网络节点定位算法进行 了研究,提出了一种基于Monte Carlo的多能量级移动节点定位算法。移动导标 周期性发射不同能量级的广播信号,未知节点接收感知范围内的不同定位信息, 确定自己所处的限定区域。利用改进的Monte Carlo方法,采用较少样本实现了 节点的位置估计。另外,提出了一种导标共线度约束策略,引入了共线度限制 因子(Collinearity
Limiting

Factor,eLF},很好地解决导标共线问题。

1.3.2论文的结构安排
本文的组织结构如下: 本章主要对无线传感器网络进行了概述,并对无线传感器网络的发展及节 点定位的研究现状进行了介绍。最后,阐述了节点定位的研究背景、目的及意 义等。 第2章主要对常用的几种仿真工具的特点进行了比较,重点介绍了离散事 件仿真软件OMNeT++。分析了无线传感器网络中各种节点定位技术,对节点定 位的测距方法、节点定位的计算方法、各种定位算法进行了分类描述,并列举 了无线传感器网络的典型应用场景。

第3章介绍了多能量级节点定位的主要思想,对多能量级节点定位机制进
行了分析,提出了一种导标优化策略条件下的多能量级节点定位方法。利用仿 真软件OMNeT++对提出的定位策略的适应性进行了仿真分析。 第4章在多能量级节点定位原理基础上,对Monte Carlo方法进行改进,提 出了一种基于导标选择策略的移动节点定位算法。针对导标共线或接近共线时 易产生定位失效或定位误差很大的情况,引入共线度限制因子概念,提出了一 种导标共线度约束策略。详细描述了OMNeT++的仿真过程,并对算法的可用性 及实用性进行了分析。 第5章总结全文,并讨论了定位研究领域的未来研究方向。



武汉理工大学硕十学位论文

第2章

仿真软件简介与节点自定位技术

2.1仿真工具介绍
随着无线传感器网络的不断发展,网络的规模和结构变得越来越复杂。无 论是用于通信的协议还是网络节点定位用的算法,均需要对网络的性能进行有 效而客观的评价。由于受条件的限制,提出的协议或算法难以直接在现实中得 到检验,大都采用计算机模拟仿真的形式,对算法的优劣进行分析。为了便于 展开对无线传感器网络的研究工作,研究人员设计开发了许多的仿真平台,它 们采用不同的程序设计语言编写仿真代码,适用的研究方向、操作系统也各不

相同。目前,用于网络仿真模拟的工具有很多种,诸如OMNel.抖【32’331,NS.2t341,
OPNETt35],MATLAB[36】,SensorSim[37】等。 NS.2(Network Simulator-2)是著名的用于网络研究的离散事件仿真工具, NS.2是开放源码的自由软件,主要致力于OSI模型的仿真,包括物理层的行为。 由于NS.2对数据包级进行非常详细的仿真,接近于运行时的数据包数量,使得

其无法进行大规模网络的仿真。OPNET和QuaiNet建模工具都是商业化的通信
网络仿真平台。OPNET采用网络、节点和过程三层模型实现对网络行为的仿真, 其本身更注重于网络QoS的性能评价。QualNet是GloMoSim的商业版,功能虽 比较强大,但是主要用于商业开发,价格昂贵,不适用于学术研究。SensorSim 是基于NS.2中一个采用DSR的802.1l网络模型上的,适用于WINS平台,需 要用SensorWare Tel脚本进行设计。但SensorSim已经停止开发和支持,也无法 下载到程序代码。 OMNeT++是基于离散事件的,离散事件指的是状态改变(事件)发生点在 时间域上是离散的,并且事件的发生不需要时间。而计算机网络通常被视为离 散事件系统,因此可采用离散仿真软件对离散事件进行仿真模拟。本文将采用 OMNeT_卜+完成对所提出算法的仿真工作,并借助Matlab强大的数据处理能力对

仿真结果进行分析。下面着重对oMNeT抖的系统框架及Matlab进行介绍。
2.1.1 OMNeT++

OMNeT++是Objective Modular Network

TestBed in

C++的英文缩写,其含义

是在C++中的目标模块网络测试平台,是一款强大的免费网络仿真软件。它是


武汉理t大学硕士学位论文

1992年开发的一个面向对象的模块化离散事件仿真器,它最初由Gyorgy Pongorl38】用类Pascal编写。直到1995年,其第一个正式的版本才发布,随后
Andras

Varga[39舯】对OMNeT++进行进一步的开发,它是一个跨平台、源码开放

的模拟环境。但主要应用于非营利性的学术交流和教育学习,目前最新的版本
是OMNeT++4.2。若利用OMNeT++进行商业开发,则需要从SimulaCrafl公司 获得许可,购买授权的OMNEST版本。 OMNeT++是开源的基于组件的模块化的开放网络仿真平台,是近年来在科

学和工业领域里逐渐流行的一种优秀的网络仿真平台。通常可进行通信系统通 信模型仿真、协议仿真、硬件体系结构验证、复杂软件系统性能评估、任何其 他离散事件驱动应用的建模与仿真。OMNeT++作为离散事件仿真器,具备强大
完善的图形界面接口和可嵌入式仿真内核。同其他的平台相比,它在表达模型

的细节、可利用的协议模型、定义网络拓扑结构、编程模型、调试和跟踪支持、 性能及源代码公开等多方面都显示出了强大的优势。更重要的是,OMNeT++支 持并行仿真,任何类型的同步机制都能够被运用,为人们的研究工作提供了极
大的方便。

隧黝黝黧瑷琵戮黝


■∽u叫—峨州__k∞嘲1.卿∞l"


oh∞b

坐 黢缨趱缓燃燃 帼怒=然q|糍瓣潲渊弱象谶 删j钳嘲蝌‘口l铀蝴】 M酋々』阿
R■呵_岫nppDt●-2 T.0舯
Ev,lof rpa

am







u—J.Jm
”叩贰n即啊目i‘●

隧受唪}tt垒 J

lJ◆措:艇io}展i氛}一g|舞bB嘲|
:E吲#鲫
Sh●,矾ec

Run#1=哪棚州神H—IL

u…●w no尹删o,
r0■

Tm钔,删糟蚱脚lnn}


‘‘…

NeIt㈣H世州kIml哪咖曲

睡Ij■}^i^F』点ⅢI■一_mⅡ?E4L矗_Z强l煳匏‘j

,:嘲再i



塑墅螋!螂!型咛趔唑唑!苎!壁塑

詈嚣篇:裟慈荔易搦瑟簇藏豢笼戮 隧缀笼缀戮缀爱篡缓戮缓黝
l,哆曼世上哒重蔓j r丁一
■■融●硎Heb∞^

~罐9蛔I醴Il酬

一毛 {lReewced¨PD曩q椭蛙堕?口D船3lot o!研辩 舞o∞“粤椭I瓤?出t曲吐峰竺堂!钠神“2

蚓h6姒e椭-∞_
阿Id●e竹de讪砌e辩?22曩01




lII^ub。枷?“嗍咧粤型“ak o¨)舾咖哩



t嘶TdJve-卅 H—e~-“?∞-0
d’●on bod bod

h删邮帕obocd
d∞盯tagneH



一l



17昨l-f晌0T._uDn

moteFI∞rre№I


照艮l

…,r 西
?i


I—O

I臼t鞋kd^d“er虹Io
r一●pl单Erdl"'£vent


huXl

H Ira呻~eH0n∞I

堋啊州妇一晤毹odePo“1

1咖

u f如


r-optlorC.ede-0f]POPTION NO-oPTIONl

t}

●_e.-rrf…

pppE栅IfveH

p: 哥

.国一,国

露——国粤.

?。

育一、
赫:





_
;●i

图2.1

OMNeT++用户开发界面
kernel

OMNeT++主要由六个部分组成:仿真内核库(simulation

library,简

10

武汉理工大学硕士学位论文

称Sire),网络描述语言的编译器(network 形化的网络编辑器(graphical

description

compiler,NEDC),图

network description

editor,GNED),仿真程序的

图形化用户接口一1'kenv,仿真程序的命令行用户接口--Cmd胁v,图形化的输出 工具一PloVe和Scalar。

图2.2

OMNeT++的高层体系结构

图2.2所示为oMN卅的模块化结构,箭头表示了两组件之间的相互关系。
Sim是仿真内核和类库,用户编写的仿真程序要同Sim连接,Sim在OMNeT++ 中占据最为核心重要的地位。执行模型依次调用仿真内核的函数并使用Sim库 中的类。Envir决定创建何种模型,包含了主要的仿真循环,捕捉并处理执行过 程中发生在仿真内核或类库中的错误和异常。OMNeT++的TKENV和CMDENV 两种用户界面主要用于实现仿真程序的人机交互,可满足大型无线传感器网络 对仿真程序的执行、追踪、调试等功能。OMNeT++允许模型内部机制对用户可 视化,也允许用户启动和终止仿真,并更改模型内部的变量。而图形输出工具 主要实现对仿真数据的实时记录和统计。

OMNeT++采用混合式的建模方式,OMNeT++模型主要有简单(Simple)模 块和复合(C0n叩ound)模块组成,简单模块主要负责消息(message)的接收和转

武汉理工大学硕十学位论文

发,复合模块由简单模块组合而成,这些模块之间通过消息传递进行通信。消 息通过复合模块内部的各简单模块相互协调、运算处理。f-j(gate)是模块的输 入/输出接口,消息通过各模块的实现传输,消息在输出门发送,在输入门接收。 链路(connection)负责将各模块的门连接起来,链路有三个属性,包括传播延 迟、数据传输速度率和误码率。OMNeT++的系统结构图如图2.3所示。 一个可执行的仿真程序,~般由以下几部分组成: 1)网络描述(NED)语言,又称NED文件:用以对大量组件的描述,如 通道、简单和复合模块类型;定义网络内的拓扑结构、网络仿真参数及各节点 之间的连接状况等。NED语言可用任何文本编辑器或GNED图形编辑器进行编 辑。 2).clap或.CC文件:用于完成算法中各模块的代码编写,也可以通过代码生 成网络的拓扑结构,实现仿真结果的统计工作。 3)配置(Ini)文件:主要实现对模块参数的配置,便于对仿真参数的更改。 4)消息(.msg)文件:可以模拟传输过程中的事件、消息、包、帧等,消 息体类似于结构体,但并非所有的程序都需要.msg文件。 首先,需要使用NED编译器(nedt001)和消息编译器(opp )cgsm.将
NED

文件和消息文件翻译为C++。这步之后,处理就类似于从源文件构建任何C/CH
程序:所有C++源文件需要被编译为目标文件(Windows中的.obj文件),所有 的目标文件需要链接所需的库来得到一个可执行的文件。需要链接的库主要有: 1)仿真内核和类库,称为sim 图24所示; 2)用户界面,用户界面的公共部分是envi库(1ibenvir.a文件等),具体的 用户界面是tkenv和cmdenv(1ibtkCTIV.a,libcmdenv.a等),必须与envir链接, 外加tkenv或cmdenv。 系统内部各文件的转化问题是一个复杂的问题,难以人工完成。幸好软件 本身提供了相应的自动转化工具,这就为仿真执行省去了大量不必要的麻烦。 图2-4给出了一个构建运行仿真程序处理过程。
std(file libsim std.a,sim

std.1ib,etc),如

12

武汉理工大学硕士学位论文

N吧.塞芋哪咖
(NEDC compiling)

lmpl.ofsimple modules?.CC

Simuliation kernel library ’.1ib/*.he..g.:sim_std.a

Uscr intcrface libraries ‘.1ib/+.ac.g.:envir.a cnadcnv.a



l脚。譬~

c++compling







、 r

、 ,

(1inking I ◆
Simulation program Configuration file omnetpp.ini




execution


Output files+.VCC,
●.sna,etc.

图2-4仿真程序处理过程图
2.1.2

MATLAB

Matlab是Mathworks公司推出的工程应用软件,具有科学计算、符号运算、 图形处理方面的强大功能。Matlab的技术形式是以矩阵为基本单位的矩阵运算, 常用于数值分析、数值和符号计算、工程与科学绘图、图像处理、数字信号分 析与通信、控制设计及金融建模等仿真实验领域。Matlab拥有数量众多、范围 广泛、快速高效的工程计算函数库,这为仿真系统设计人员提供了有力支持。 Matlab支持JAVA,C,C++和FORTRAN等语言,集成了2D和3D图形功能, 便于完成相应的数值可视化工作。Matlab提供了一种交互式的高级编程语言 ——-M语言,利用M语言可以通过编写脚本或函数文件可以实现用户自编的算 法程序。Matlab可方便地绘制图形,这样就方便了对程序运行结果的统计分析。

2.2无线传感器网络的自定位技术
无线传感器网络的应用大多需要掌握节点的位置信息,节点感知数据配以 位置信息才会具有应用价值,节点定位是无线传感器网络配置和运行的一个基 本和关键问题。所谓节点定位是指对于一组未知位置坐标的网络节点,通过估 计至邻居节点的距离或邻居数目,利用节点问交换的信息,确定每个节点位置

13

武汉理工大学硕士学位论文

的机制。通常配置网络时难以对所有节点实施精确控制和人工设置。

2.2.1节点定位的基本概念
在设计节点定位算法获取节点位置信息的过程中,往往会涉及到一些无线 传感器网络相关的概念及专业术语,这里对常用的几个概念进行了总结: 导标节点(Beacon Node):在网络初始化阶段,通过其他方式预先获得位置 坐标的节点,也可称为锚节点(AnchorNode)。这些节点位置信息通常采用GPS 或手工配置等方式获得。由于这类节点的造价相对普通节点来说比较高,为节 约成本,网络内导标节点的数量相对较少。 未知节点(Unknown Node):导标节点以外的节点就称为“未知节点”。这些 节点随机分布在网络内,初始时位置信息未知,但可自组织形成网络,通过与 导标节点进行通信协作获取自身位置,这个过程就是节点定位过程。 邻居节点(Neighboring Node):网络节点通信范围内的所有节点的集合。 节点密度:指导标节点的数量占网络内总节点数量的百分比; 节点连接度:节点可探测发现的邻居节点的个数; 跳数:两个节点之间的跳段总数; 跳距:两个节点之间的各跳段的距离之和。

2.2.2节点间的测距(角度)方法
节点定位算法通常需要通过物理测量预先拥有节点与邻居节点之间的距离 或角度信息,因此测距是算法运行的前提,而定位结果的精度在一定程度上依 赖于这些物理测量本身的精确度。节点间的距离主要利用TOA、TDOA、AOA 及RSSI测距手段实现,下面对常用的几种测距进行简单描述: (1)到达时间TOA[4l】(Time ofArrive):在已知信号的传播速度下,根据 信号在两个目标之间来回传播的时间就可以估计出发送者和接受者之间的距 离。声波频率低、速度慢,对节点硬件成本和复杂性的要求都比较低,但声波 易受外界环境的影响。此外,TOA技术要求节点间保持精确时间同步,这样才 能够得较高的定位精度。 (2)到达时间差TDOA[42](Time
Difference

ofArrive):发射节点同时发射

两种不同传播速度的无线信号,接收节点根据接收到这两种信号的时间差和它 们的速度把时间转化为距离,以此计算节点间的距离。TDOA技术受到超声波

14

武汉理工大学硕士学位论文

传播距离限制,在布置网络时需要大量节点密集布设。此外,非视距关系对TDOA 会造成较大影响。 (3)到达角AOA[431(Angle ofArrive):接收节点利用阵列天线或多个超声 波接收器感知发射节点信号的达到方向,通过计算接收节点与发射节点之间的 相对方位或角度,利用三角测量法即可实现节点的位置估计。由于采用AOA技 术需要额外的硬件,且此技术易受外界环境影响,有时可能难以用于传感器节点。 (4)接收信号强度指示RSSll44](Received
Signal Strength

Indication):已知

节点的发射功率,接收节点根据收到信号的强度,计算信号传播损耗,利用理

论或经验模型将传播损耗转化为距离。RSSI技术虽然易受噪声和障碍物的干扰,
但较少需要额外的硬件设备,相对其他测距技术而言是一种低功率、廉价的测 距技术,尽管测距信息相对不准确,但还是经常被用于无线传感器网络中节点 间距离的测量,是目前常用的测距手段之一。

2.2.3节点定位的计算方法
目前,各种节点定位算法基于不同的节点定位原理,通常节点在通过各种 测距技术或采用网络内多跳通信方式获得距离(角度)的估计值后,一般采用 以下几种方法估算自己的位置: (1)三边测量、法【45】 通过测量未知节点到三个不在同一直线上的参考节点的距离,可得到基于 测量距离的三个等式关系,以此构建一个二元二次方程组,利用此三个等式对 此方程组进行求解,这样就可以确定未知节点的位置。三边测量法的基本原理 是求三个已知半径和坐标圆心的圆的交点,此交点即为未知节点的估计位置, 其不足之处在于三个圆相交并不会只有一个交点。三边测量法是适用于包含多 个导标节点的定位系统的测量方法,也是目前广泛采用的一种定位方法。 (2)三角测量法 三角测量法【46】是一种利用三角形的几何关系进行位置估算的方法。在测量 信号达到角的情况下,利用数学原理,即在一个三角形中,如果已知两边的长 度和两角的大小,就可以唯一的确定第三个点的位置,且这个点是另外两边的 焦点。这样未知节点的位置就利用三边测量法求得。随着测试次数的增加,该 方法的定位精度会随之提高。

(3)极大似然估计法

15

武汉理工大学硕士学位论文

在实际的无线传感器网络中导标节点通常不止三个,因此在计算过程中会 采用多边测量法来提高定位精度。极大似然估计法的基本原理是未知节点分别 接收网络内导标节点的位置信息,测量到各导标节点的距离或角度信息,使用 标准最小均方差估计方法来确定节点坐标。与三边测量法原理相比,它可以减 小距离误差对定位精度的影响H丌。

2.2.4节点定位算法的分类
节点定位【48】是指无线传感器网络通过特定的手段获得节点位置信息的方 法。关于无线传感器网络定位问题可分为两类,一类是无线传感器网络对自身 传感器节点的定位,另一类则是无线传感器网络对外部目标的跟踪定位。节点 自定位是获得网络内节点自身坐标的方法,目标跟踪定位是确定网络内某一事 件或特定目标的坐标位置。而节点自定位是实现目标跟踪定位的前提和基础, 故本文主要对节点自定位技术进行研究。 节点位置信息在无线传感器网络中的各种应用中至关重要,国内外学者对 节点定位的研究取得了一系列的研究成果,提出了许多节点定位方法及解决策 略。尽管目前节点定位算法还没形成统一的分类规范,但通常可以根据定位过 程中是否测量实际节点的距离,将无线传感网络节点自定位技术分为两大类: 基于测距(range-based)【49】算法和免测距(range.free)[50】算法。 基于测距的定位算法主要是通过测量未知节点与导标节点的距离或角度信 息,基于节点间的测算距离,利用极大似然估计法等计算方法实现未知节点的 位置估计。比较典型的算法,如Mrr开发的基于TDOA技术的Cricket室内定 位系统【5l】,美国Rutgers University利用距离矢量路由和GPS定位原理提出的 DV-Distanee算法【52】,基于多边测量法的AHLos(Ad.Hoc 算法【53】,基于AOA的APS算法【矧等。 基于测距(Range-Based)的定位算法主要采用TOA、TDOA及RSSI等测 距(角度)技术手段,对距离进行测量,利用三边测量法、三角测量法或极大 似然估计法计算未知节点的坐标,最后对求得的节点坐标进行多次循环、迭代 求精,可以实现较好的定位精度【551。虽然基于测距的定位方法总体上能够取得 较好的定位精度,但需要专门的硬件设备,环境条件对定位精度的影响较大, 且受到硬件成本和功耗的制约。因此,尽管基于测距的定位机制在定位精度上 有可取之处,却并不适用于许多应用领域。
Localization System)

16

武汉理工大学硕士学位论文

出于对成本、能耗等的考虑,提出了免测距(Range.Free)的定位技术。免 测距的定位算法是利用节点间的连通度和多跳路由信息交换等方法来估计节点 间的距离或角度,以此完成定位的免测距定位方法。诸如质心算法(Centroid Algorithm)[5们,DV-H0p算法【571,凸规划(Convex Optimization)算法【5引,MDS.MAP 算法【跏及移动导标节点(Mobile Anchor Points,MAP)定位算法【删等都是典型 的免测距定位算法。免测距的定位技术不需要测量节点间的距离或方位,仅根 据网络连通性、节点密度等信息即可实现定位,降低了节点对硬件的要求。虽 然定位误差有所增加,但基本能满足大多数应用的要求。 质心定位算法是一种经典的免测距定位方法[61,621,是由加州大学的Nirupam Bulusu等提出的一种典型的在自由室外环境中利用未知节点与导标节点之间的 非连通性的定位算法。该算法的核心思想是:导标节点周期性向周围邻居节点 广播信标信号,信号中包含自身ID和位置信息。未知节点侦听导标节点的周期 性广播的位置信息,当接收到来自某一导标的定位信息超过某一门限时,就确 定此导标位于自己的通信范围内,未知节点以其通信范围内所有导标的几何质 心作为自己的估计位置。质心算法完全利用未知节点与导标节点是否连通进行 定位,定位原理简单,无需节点间的协调工作,算法具有很好的可扩展性。但 质心算法的定位精度并不理想,可满足对位置精度要求不太高的应用,是一种 粗粒度节点定位算法。 DV-Hop是一种利用多跳路由信息进行节点位置估算的定位方法【57,631,此算 法类似于传统网络中的距离向量路由机制,算法可以分为三个阶段:第一阶段, 使用典型的距离矢量交换协议,导标向邻居节点广播导标节点信息,包含位置 信息和跳数。收到这些信息的节点记录位置信息和跳数(数值加1),然后再转 发给其邻居节点,直到网络中所有节点都获得距锚节点的跳数。第二阶段,在 获得其他导标节点位置和相隔跳距之后,导标节点计算它和周围节点的网络平 均每跳距离。然后将此平均跳距值再转给它的邻居节点。为避免重复接收同一

导标节点的平均跳距信息,可采用可控泛洪法。DV.Hoop算法将平均跳距信息
中加入生存周期TTL控制以解决节点收到多个不同导标定位信息的问题。第三 阶段,未知节点利用求得的平均每条距离,根据三边测量法或最大似然估计方 法实现节点的位置估计。DV.Hop算法实现简单,不存在测距误差的影响。但 DV—Hop算法定位精度易受网络拓扑结构的影响,只能在各向同性网络中表现出 良好的性能。

17

武汉理工大学硕士学位论文
APIT(Approximate Point-In.Triangulation

Test)【64’65】是一种基于区域交集的

免测距技术的定位算法,其主要思想是三角形逼近,未知节点处于多个三角形 覆盖区域的重叠部分中。该算法假设未知节点可接收到多个导标信息,导标节 点可形成多个三角形覆盖区域。未知节点从所有邻居导标节点集合中选择3个 节点,测试是否位于这3个节点组成的三角形内,重复这一过程直到穷举所有 的三元组合或者到达期望的精度,然后计算包含目标节点所有三角形的重叠区 域的重心,以重叠区域的质心作为节点的估计位置。APn’算法在无线信号传播 模型不规则、非理想的圆形传播模型时具有较好的定位性能。算法定位精度在 导标节点比例较大时可获得较好的定位精度,但受节点密度的影响较大。

凸规划算法【删是加州大学伯克利分校D0he啊等人将传感器网络中点到点
的通信模型转化为节点位置的一组几何约束,把整个网络模型化为一个凸集,

从而将节点定位问题转化为凸约束优化问题。凸规划是一种集中式定位算法,
首先通过节点间连通性,未知节点获得其邻居导标的信息,计算未知节点的可 能存在区域,并得到包含导标通信范围相交区域的最小矩阵,最后计算矩形的 质心作为未知节点的位置估计,从而实现定位。在锚节点比例为10%的条件下, 定位精度大约为100%。为了高效工作,锚节点必须部署在网络边缘,否则节点 的位置估算会向网络中心偏移。

2.2.5定位性能评价
无线传感器网络节点定位算法的定位性能反映了一个设计算法的好坏,但 目前尚未形成一个统一的算法性能评价标准,如何有效地对算法性能进行评估 也是一个值得深入思考的问题。目前,针对节点定位的性能评价方法有多种, 下面就几个常用的定位性能评价标准进行分析。 (1)定位精度 定位精度是判断一种算法定位性能好坏首要的、也是最直接的评价指标。 一般采用定位误差值与节点通信半径的比值表示,节点定位精度一般包含平均 定位误差,平均距离误差,最大、最小定位误差及误差均方差等方面。 (2)导标节点密度 无线传感器网络内节点位置信息的获取依赖于导标节点,而导标节点一般 配备有GPS定位装置或人工配置,造价远高于普通的传感器节点。受传感器网 络工作环境的影响,难以实现对无线传感器网络的人工布设,往往在应用场景

18

武汉理工大学硕士学位论文

中随机布撒节点使其形成组织网络。若导标节点在网络内分布不均匀,定位效 果将大大降低,势必需要增加导标的密度。但这样又无形中增加整个网络的成 本代价。因此,导标节点密度也是节点定位性能的重要评价指标之一。 (3)网络规模 无线传感器网络的不同应用环境决定了节点不同功能,定位场景有可能是 一个房间、建筑物、园区、森林等,而如何实现对这些地方的有效监控也是需 要深入思考的问题。一种定位技术在不同规模网络内能否实现有效定位也是定 位性能的一个重要评价指标。 (4)节点密度 节点密度通常以网络的平均连通度来表示,节点密度越大意味着网络内节 点数模越多,网络成本越大。节点数量越多,节点间因通信冲突问题带来的带 宽阻塞问题会越发严重。如何实现低密度下节点的有效定位是许多节点定位算 法研究的重点。 (5)容错性和自适应性 在真实场景下,外界环境易存在障碍物、信号衰减、非视距、多路径传播 及通信盲点等问题,网络节点由于自身或外界影响而出现失效的情况。此外, 由于节点自身硬件条件的限制,测距误差有时会增大,导致节点定位误差偏大。 因此,在设计节点定位算法时,应综合考虑算法的软硬件条件,使节点定位算 法具有良好的容错性和自适应性,能够通过自动调整或重构纠正错误、适应环 境、减小各种误差的影响,以提高定位精度。 (6)功耗 无线传感器网络节点一般采用干电池供电,而受外界环境影响难以对节点 电池进行更换或充电,节点在电池电量耗尽时将失效退出网络,这将对影响整 个网络的寿命及定位性能。因此,在设计定位算法时,应在保证定位精度的前 提下,尽可能降低与功耗相关的计算代价、通信开销及时间复杂度等能量消耗。 (7)代价 节点定位代价一般包含:时间代价、空间代价及资金代价。定位代价反映 了一个定位系统的成本开销,是衡量一个定位算法性能的重要评价指标之一。 上述七个性能指标不仅是评价无线传感器网络节点定位算法的标准,也是 其设计和实现的优化目标。同时,这些性能指标是相互关联的,必须根据应用 的具体需求做出权衡,以选择和设计合适的节点定位算法。

19

武汉理工大学硕士学位论文

2.3主要应用领域
无线传感器网络作为一项新兴技术,各国都对其表现了极大的兴趣,在这 一领域做了大量的研究工作,形成了许多重要的理论和方法。在科学研究和实 验方面已经有了很多成功的应用范例,反映了无线传感器网络的巨大应用潜能, 同时也预示了其良好的商业应用前景。无线传感器网络的广泛应用前景主要体

现在:国防军事、医疗监护、精准农业、建筑结构健康监控、地震监测及智能
家居和智能小区等领域。 (1)国防军事

在战场上,如何准确有效地了解敌我兵力、武器装备、通信及军用物资供
给等情况,对战争具有重要的影响作用。对无线传感器网络的研究工作最早就 是基于军事考虑,由于无线传感器网络具有可快速部署、自组织、隐蔽性强和 容错性等特点,能够应用于恶劣的战场环境,完成战场的实时监控、目标定位、 战争效能评估、核生化监测以及国土安全保护、边境监视等任务。无线传感器

网络具有低成本、密集型、随机分布等特点,可及时、准确地为战场指挥系统
提供可靠的军事信息。目前,无线传感器网络已受到了许多国家的极大的重视, 已经成为了军事系统中必不可少的一部分。 (2)精准农业 精准农业(PrecisionAgriculture)是指根据作物生长的土壤性状来调节对作 物的投入,以最少或最节省的投入达到同等收入或更高收入并改善环境。利用 无线传感器网络技术,将各种类型的传感器根据农田需要进行布设,传感器节

点通过Zigbee协议自组织形成网络,可实现对土壤湿度、温度、氮浓度,空气
湿度、温度及气压等信息的检测,并采用GPRS发送信息至远程监控中心。用 户即可根据信息作出判断,及时地采取相应措施,从而实现农田耕种的自动化、 网络化及智能化。 (3)建筑结构监测 将无线传感器网络应用于建筑结构健康监测,可有效降低成本,克服定期 监测的不足,实现长期在线的监测,同时还能解决传统监测布线复杂、线路老 化、易受损坏等问题。结构监测系统主要可实现对载荷、几何结构、结构响应 及重要结构部件的工作状态等的监测。无线传感器网络为建筑结构监测提供了

新的技术,可实现监测的小型化、低功耗、低成本。
(4)智能家居

20

武汉理工大学硕士学位论文

智能家居或家庭自动化是利用家庭网络或家庭总线将家庭中照明、视听、

安全、通信、调温等各种设备连接起来协同工作。智能家居系统具有对家庭中
的各种设备远程控制、远程查询、集中管理功能,为用户提供更为舒适、方便 的生活方式。

2.4本章小结
本章首先对离散事件仿真软件OMNeT++进行了介绍,对其内在的系统结构 进行了详细描述。同时对无线传感器网络中节点自定位技术进行了全面描述,

论述了无线传感器网络节点定位的基本原理。简单概述了现有的几种测距方法,
并进行了对比分析。然后着重介绍了两类典型的节点定位算法,并分析了各自 的优缺点,为进一步研究无线传感器网络节点定位技术打下基础。最后对无线 传感器网络的常用应用领域进行了介绍。

21

武汉理丁大学硕士学位论文

第3章

多能量级节点定位性能分析

近年来,多功率旧或多能量级(ConcentricAnchorBeacon,CAB)【68】的概念
逐渐被提出。能量分级思想是节点发射信号强度以能量级的形式表示,未知节 点接收多个不同能量级水平的导标信号,根据接收信号的能量强度及导标节点 的时空关系,利用导标节点信息采用一定的计算手段,最终实现未知节点的位 置确定。 Vijayanth和V'mcent在2006年最早提出了多能量级概念[-q,多能量级节点 定位算法是一种利用多能量级广播信号实现节点位置估计的分布式节点定位算 法。该算法中导标节点发射不同能量级的信号,未知节点接收多个导标节点定 位信号,通过判断接收信号的强弱,得出自己所处在导标节点的哪个能量环之 间。通过求取相应能量环的交点,最后利用质心定位原理实现节点的位置估计。 多能量级节点定位算法是一种免测距的区域估计方法,其相对定位精度受 节点的空间分布情况、信号不规则度、网络内节点数量及导标节点比例等因素 的影响。理论研究和实验表明,节点的拓扑结构及用于定位的导标节点的选择 策略对定位效果的影响较大。为改进多能量级节点定位方法的相对定位性能, 本章比较了不同导标选择方法下的节点定位精度,并推导了平面内导标优化选 择策略的分析公式,最后仿真比较了提出的导标优化算法与传统免测距算法在 定位精度及稳定性等方面的性能。

3.1多能量级节点定位原理
假设将导标节点的有效通信范围由远到近依次划分为m个不同半径的同心 能量环,各能量环的面积相等。每个能量级的信息能量反馈形成一个圆形区域, 最低能量级的反馈区域最大,它的圆形区域的半径为rmax,在这个最大反馈区域 内能量按照一定的规律被分为多个能量级圆环【68】,如图3.1所示。

武汉理工大学硕士学位论文

?

导标节点

图3-1导标节点的通信范围

则在第i级能量级半径rj与最大通信距离,麟间的关系如下:

‘:‰,×1/三, ‘2‰×、/i,

i:1—2..,m 2一..,m

。1(3-1) )

大距离为‰,未知节点接收信号的门限功率为‰old,k为一固定值,以为路
径损耗指数,则二者之间的关系可以用下式表示:

设导标节点广播信号的最大能量为Pmx,未知节点能接收到信息能量的最

‰谢=面。PErla,(
因此,可以计算出导标节点的有效通信范围为:

(3-2)

公(告]-
身处于导标节点哪两个能量级之间。

@3,

由公式(3.3)可知:当导标广播的最大能量只嗽、门限功率‰old一定时,
导标节点的有效通信距离即可确定。未知节点接收到导标节点的广播信息后, 将接收到信息的功率与导标节点各能量级的功率进行比较,这样就可判断出自

3.2导标选择问题
该定位算法误差的主要影响因素是各导标节点相应能量环组成的交叉区域 的大小,因此利用已知参数来表示交叉区域的面积,可以直观地得出误差的主 要影响因素。在节点定位的过程中,未知节点通常可以接收到多个导标节点的

武汉理工大学硕士学位论文

信号,如果在定位时求所有导标节点相应能量环的交点,虽然能够得到较高的 定位精度,但是计算量会大大增加,不利于快速定位。按照一定的导标选举策 略从未知节点周围的导标节点中选出三个导标节点,使其相应能量环交叉区域 面积最小,既能降低算法的复杂度,又可以得到较高的定位精度。 由于导标节点的位置已知,因而导标之间的距离已知,可以通过探索两个 导标相应能量环交叉区域与两个导标的距离之间的关系来确定导标的选择策 略。为了简化问题的描述,不失一般性,假设两个导标节点的两个能量环的半 径均为R和,,则两导标能量环的交叉区域如图3-2(a)所示。

●导标节点

tI)

(b)

图3.2定位误差示意图 假设导标节点彳l和彳2之间的距离为d,显然d满足2r<d<2R,则两个导标 节点两个能量环之间的交叉区域的面积即为两个导标节点外环交叉区域面积与 其中一个导标节点内环与另一个导标节点外环交叉区域的面积。首先计算两导 标节点外能量环交叉区域的面积为:

s:2R:arccos丢一d
算,区域1的面积为:

R2

d2i

2r<d<2R (3-4)

而图3.2(a)中区域l的面积即为图3.2(b)中两圆的交叉区域, 经过计

‰埘一==二d2+匠R2_r2二,cos鼍竽
一d、/R2(d2+R2-r2)2—
24

协5,

2r<d<2R

武汉理工大学硕士学位论文

‰=S一2‰l (3.6) 为了探索交叉区域随导标节点之间距离的变化关系,下面对‰求关于d
的导数,得到:

‰2——■丽蒸亏萨纛i了一+习雨霉萨i亏万 一瓜砑
a.

6d2R2—2尺2(d2+R2一,2)一4d2(d2+尺2一,.2).4d2,.2—2r2(d2一R2+,.2)

,6d2尺2—2R2(d2+R2一,.2)一4d2(d2+R2一,.2)+4d2,.2—2r2(d2+R2一,.2)

一矗两

:—_2(R2_r2)2_—2d2(2d2_3r2)一再丽
=?----—————-—?——--————--------——————————————---——?—————一一'J‘l“
一,1

d、J/4d2,.2一(d2一R2+,.2)

dx[4d2,.2一(d2一R2+,.2)

(3.7)

由于d>2r,所以2d2.3r2>0,由此可得:

s二<0

(3-8)

因此,可以得出如下结论:两个导标节点相关能量环的交叉区域的面积与 两个导标之间的距离成反比。距离越小,交叉区域的面积越大,误差越大,此 时需要采用第三个导标对交叉区域的面积加以限制,实现未知节点的位置估计。 距离越大,交叉区域的面积越小,误差越小,当d接近2R时,为减小计算量又 不失定位精度,可取此两个导标的坐标平均值作为未知节点的估计位置。此结 论对未知节点处于导标节点不同能量环之间均可适用。至此,就可以得出选择 导标节点的具体策略,即选择相距较远的导标节点用于定位,可以得到较高的 定位精度。 为了能够实现未知节点的有效定位,未知节点应该能够接收到至少三个导 标节点的广播信息。通过增加导标节点的数量,以提高节点的定位率,当导标 节点到达一定比例时,可实现对大多数未知节点的位置估计。

3.3算法描述
为了能够实现未知节点的有效定位,未知节点应该能够接收到至少三个导
标节点的广播信息。现采用图示法说明定位原理:如图3.3所示,假设未知节点 接收到三个导标节点的广播信息,分别判断未知节点位于导标彳l、彳2、彳3的哪 个能量环之间,则未知节点必定位于这三个导标节点组成的公共区域内,通过 计算公共区域的质心即可估计出未知节点的位置。

武汉理工大学硕士学位论文

高效多能量级定位方法基本原理描述如下:

为降低算法的复杂度及提高定位精度,选择三个导标节点来实现对未知节
点的位置估计。为得到三个尽可能有效的导标节点,应使三个导标节点相互之 间的距离尽可能远。为此,计算任意三个导标两两之间的距离和,选择其中最 大的一组,作为定位时采用的导标节点。在下面的仿真结果中可以看到,在此 方法下得到的定位误差比任意选择三个导标计算出的定位误差小,说明此方法 是有效的。 三个导标节点的不同能量级圆环相交,利用其各自参与定位的能量级圆环, 计算环与环的交点,交点围成的公共区域就是质心定位的有效区域。围成这个 区域的可计算交点即为有效交点,根据这些有效交点的坐标,求出质心即为定 位结果。在计算各个能量环的交点坐标时,有些交点是无效的,需要在计算过 程中将其剔除,仅保留有效节点。

★无效交点
‘a) ‘”

图3.3导标节点定位示意图 如图3.3所示,为三个导标节点对未知节点进行定位的情况。将节点的通信

范围分为两个能量环(聊=2),假设三个导标彳l、么2、彳3的坐标分别为@l,Y1)、∞, Y3)、∞,粥),内圆的半径为,.,外环的半径为尺,使环与环之间的面积相等。判
断三个导标各自用于定位的是内圆还是外环,先选择两个导标计算其中的公共 区域,得出两个定位点,然后使用第三个导标判断其中的有效交点。 可以根据下式计算出能量环之间的交点:

l(x—zf)2+(y—J,,)2=厂2

D,.

,i=1,2,3

(3—9)

I(X--Xf)2+(少一yf)2=R2

武汉理工大学硕十学位论文

根据式(3.9)先计算两导标相应能量环交点,求出交点与第三个导标节点 的距离,选择其中小值,即可选择出有效交点。然后重新选取另外两个导标节 点,按照相同的步骤循环进行,提取出对节点定位有用的有效交点,同时可以 去除对定位无用的无效交点。 利用上述方法求取所有对节点定位有用的坐标后,便可利用质心定位的基 本原理,计算出未知节点坐标的估计值,即实现未知节点定位。 根据高效多能量级定位算法的定位原理知,三个导标节点能量环相交可能 出现两个相交区域,且其中一个是有效定位区,另一个为伪定位区,这种情况 会导致很大的定位误差。出现这种情况的主要原因是两圆交点的对称性而出现 伪定位区域,导标节点的位置关系表现在导标节点间距太小或三个导标的位置 处于近似共线状态。

导标节 。未知节 ‘有效交点



图3_4定位区域示意图 如图3-4(a)所示,此时三个导标接近共线,为不失其定位率,此时仅使用导 标4、彳,对未知节点的位置进行估计,取两个导标的坐标平均值作为未知节点 的估计位置。 在对节点进行定位时,可分别判断三个导标用于定位的是内圆还是外环。 先计算第一二导标的公共区域,再判断未知节点处在第三个导标的哪个能量环 之间。因只有两个环,即内圆和外环,判断内圆、外环与公共区域是否相交。 利用公共区域及与公共区域相交的环,对未知节点进行定位。 这种定位方法的主要思想是尽可能减少三个导标节点围成的公共区域,从 而提高定位精度。采用上述判别方式能够解决导标节点共线问题,并在一定程 度上提高了节点的定位率。

27

武汉理工大学硕士学位论文

3.4算法适应性分析
3.4.1仿真实验设计
本节将采用OMNeT++对提出的算法进行仿真分析,为此需要对算法构建仿

真模型。通过建立完善的无线传感器网络仿真模型,可在稳定的仿真环境下评
价定位算法的各种性能。

在一个典型的无线传感器网络中,所有节点随机分布在MxN的矩形区域内, 每个节点都有一个唯一的标识符号(D),所有节点的通信模型相同。由于节点
是一个复合模块,其内部结构包含多个子模块,每个子模块具有特定的功能, 用户也可以根据需要对这些模块进行修改或替换。

图3.5网络节点内部结构 如图3.5所示,节点的各子模块主要有: 1)Physical模块:定义物理层模型,用于建立、维护和拆除物理链路连接, 实现模拟天线在无线信道上信息包的接收和发送,天线一般采用无方向性模式, 同时在信道上可设置信息包的延长、错误率、数据传输速率等。 2)MAC模块:用于仿真链路层随机接入信道协议。在物理层提供比特流 服务的基础上,建立相邻结点之间的数据链路向网络层提供透明的和可靠的数 据传送服务,主要负责数据流的多复用、数据帧检测、媒体接入和差错控制等。 3)Route模块:节点模型的核心,接收来自应用层的数据。主要负责路由的 发现和维护,由于受能量限制,节点之间往往无法直接通信,通常需要借助中 间节点以多跳路由的方式将源数据传送至目的节点

武汉理工大学硕士学位论文

4)Application模块:为应用程序提供服务以保证通信。应用层为操作系统 或网络应用程序提供访问网络服务的接口。 网络拓扑结构图如图3-6所示,网络内存在两种类型的节点,一种是管理 (Manage)节点,另一种是通信节点。管理节点负责网络内拓扑结构控制,实 现节点间的链接,控制程序的执行。通信节点包含导标(Anchor)节点和未知 (Sensor)节点,为减小通信量,导标节点仅与通信范围内的未知节点通信,导标 节点通过感知自己周围的邻居节点,建立网络拓扑结构,并周期性地向未知节

点发射导标信息,未知节点根据接收到的导标信息,利用一定的计算手段实现
自身位置的定位。

其中各节点模块相应的NED文件为:

29

武汉理工大学硕士学位论文

●■薛瑾霜鼎嬲t韬2%《《%※翳强嘲掰啊掰目日■暖嘲

I(Test)te。t F,d-1)时傩F40J

’i塌l愿l映{,_{r独}J l,l
.。”

o{名l团
,。j。j

一一





…f吧=鞠墨鳞嬲≯。壤缸jl



—j

j一;’n。‘”影、





榭|,
.#歌



6l



蔼,:

糕团

辩强

瓣品甚;诩瓣田曼钏二赫刁缈

e匿唧a’争e.枞
。’

翻:

:。烹z刁品眵一爱囊删’e。鼎,品研,熏州甜’
0料蹙日晒3】矧,sal51iil

‰。,椭锶瓣篙渤,m鼎瓣翟魏删鼎
一研罨

h够阻黧霾雾睦碧黧霉:;≥啪州捌国湖荔晒1
湖刚罚韵嗍删w螂啡劲训谰,,7J _』…‘



?,…锄酬’硼

图3.7初始化网络初始结构图 模拟的仿真网络环境和相关参数的设置如下:仿真场景为一个500xSOOm2 的仿真区域,网络内随机分布100个传感器节点,其中导标节点20个,导标节

武汉理工大学硕士学位论文

点和未知节点均随机产生,每个节点的最大通信距离(R)为100 m。采用理想 的无线传播模型,如果未知节点与锚节点的距离小于R,就认为未知节点与锚节 点连通。图3.7所示为初始化网络拓扑结构,采用变化导标节点比例的形式,实 现在各种仿真条件下对算法性能的比较分析。 某时刻的网络内部节点通信图如图3.8所示,其中绿颜色的圆形图标代表导 标节点,灰颜色的图标颜色代表未知节点,红色图标代表节点间传递的数据, 导标节点与未知节点间的连接线为信道,表明未知节点处在导标节点通信范围 内,这时节点间就可以实现数据信息之间的传输了。

图3-8某时刻网络初始结构图

3l

武汉理工大学硕士学位论文

3.4.2性能评价
为了验证改进算法的可用性和有效性,对质心算法和改进算法及文献【8】提 到的CAB.EA算法进行了实验仿真,并对结果进行分析。在实验过程中,传感器 节点分布在500mx500m2的矩形感知区域内。传感器节点的数量为300个,其中导 标节点和未知节点随机产生,所有节点的最大射程(尺)为75m,网络的平均连 通度为9,导标节点数量依次为20、30、…、100。采用理想的无线传播模型,如 果未知节点与锚节点的距离小于尺,就认为未知节点与锚节点连通。 在定位时,未知节点应该能够接收到多个不同导标节点的信号。在改进定 位算法中,仅使用优化的三个导标对节点进行定位。图3.9所示为随机选择导标 与有效选择导标的定位误差的比较。随机选择的三个导标为距离未知节点最近

的三个导标。从图3.9中可以看出优化导标下的定位误差明显小于随机选择导标
的情况。

0.32-

o.3



一叱)J
oJ.10

0勰

\八二---*---An<chors Choice■=Random-

0为

O私

co口∞E;∞o

0.18——一….…
10 20 30 40 50 60 70

number of beacons

图3.9随机选择导标与优化导标定位误差的比较 图3.10所示为在不同导标节点的情况下,三种不同定位方法的定位精度比 较。由图可知:改进的算法相对CAB.EA算法与质心算法,定位精度有明显的改 善。随着导标节点的密度越大,改进定位算法的定位精度越高。当导标节点数 量达至lJl00时,改进定位算法与CAB.EA相比,定位精度可提高11%左右。

32

武汉理T大学硕士学位论文

I一毋Cemoid;
(;.

l——+CAB-EA—

\~‘K。.、s、
、\

?ECAB.:

¨
一芷)Joto

啷 哺 嘣 薹|


co曩罂眷∞o

o。1气矿—面_—右—_方—1矿—咭广—高——亩—1扩—前云—彳o
number of beacons

图3.10不同算法的定位误差比较

8 写
。r-






0.16—

“~协-~艘



0.14


0.12一——一一 10 20

30

40

50

60

70

80

90

100

110

number of beacons

图3.11

不同算法定位方差比较

图3.11所示为三种算法的定位方差比较,由图可知:改进定位算法的方差在 不同导标节点密度情况下均要小于CAB—EA算法,这说明本文提出的算法在定位 的稳定性方面要强于CAB.EA算法。采用改进的定位算法,其定位方差要比 CAB.EA算法要降低1 5%'-'-'28%。

33

武汉理工大学硕士学位论文

3.5本章小结
本章对多能量级的概念进行了介绍,在分析基于多能量级思想的节点定位 基本原理基础上,对多能量级节点定位算法中导标的选择策略进行探讨,提出 了一种改进CAB的分布式节点定位算法,该算法可解决无线传感器网络节点定 位中的计算代价的经济性与节点定位效果的可靠性之间的平衡问题。 采用离散事件仿真工具OMNeT++对提出的算法进行仿真分析,建立了无线 传感器网络仿真模型,详细描述了仿真实验设计过程,并对节点的各模块进行 了说明,最后对算法进行了仿真分析。该算法与其他典型免测距方法相比,主

要区别在于能够选择合适的定位导标以减小定位过程中的计算量,能够满足无
线传感器网络节点资源受限的要求。仿真分析表明,提出的导标选择策略具有 很好的适应性,能够有效降低了节点定位误差,算法具有很好的稳定性。

武汉理T大学硕士学位论文

第4章基于多能量级的移动节点定位算法
多能量级节点定位算法最初是应用在静态网络中,上一章主要介绍了多能 量级节点定位的基本原理,为解决节点定位过程中计算代价偏大的问题,通过 公式推导对导标选择策略进行了分析,最后利用OMNeT++对算法的适应性进行 了验证。结果表明,改进的多能量级节点定位算法具有很好的适应性。

本章在第3章多能量级节点定位算法适应性分析基础上,将多能量级思想 引入动态网络,借助多能量级节点定位原理,并基于Monte Carlo方法【69】,提出
了一种基于多能量级的改进Monte
Carlo(Improved Monte Carlo

based

on

Multi.energy Level,LMCML)的移动节点定位算法。

此外,在节点定位过程中,针对导标共线或接近共线时易产生定位失效或 定位误差很大的情况,引入共线度限制因子(Collinearity Limiting
Factor,CLF)

概念,提出了一种导标共线度约束机制,有效解决了定位失效问题。 4.1

Monte Carlo方法概述
Monte Carlo法提供了一种方便而有效的从非高斯、非线性、高维的观测数

据中计算后验概率的方法。它将所求解的问题同一定的概率模型相联系,用电 子计算机实现统计模拟或抽样,以获得问题的近似解,故又称统计模拟法或统 计试验法【7们。目前该方法已被广泛应用于目标跟踪、导航与定位,故障诊断, 参数估计与系统辨识等领域。 目前Monte Carlo法已被广泛应用在移动无线传感器网络定位中。Monte Carlo定位算法的核心思想是:首先,未知节点接收导标的定位信息,确定样本 可能存在的范围。按照后验概率分布随机抽取一定数量的样本,每个样本即为 未知节点的一个可能位置。通过节点位置的后验概率为每个样本分配权重,对 样本进行重采样滤波更新,使权重小的样本向权重较大的样本收敛。最后得到 满足定位条件的若干样本,通过计算样本均值或按照权重不同对样本坐标累加 计算,实现节点的位置估计。 由于传感器网络的能量大部分消耗在计算和通信上,计算代价是节点定位 的一个重要性能参数指标。对Monte Carlo方法而言,计算代价主要消耗在样本 采样过程中,若使用较多数量的样本,可获得较好的定位效果。但当未知节点

35

武汉理工大学硕士学位论文

可感知的导标节点数量较多时,采用大量的样本数量进行循环迭代,计算代价 将显著增加,势必将消耗大量的能量。 本章对Monte Carlo方法进行了改进,将移动导标发射信号强度划分为多个 能量级,先采样多能量级节点定位思想确定未知节点的受限区域,然后采用改 进Monte Carlo方法估计未知节点的位置,实现了以较低计算代价获得较好定位 效果的目的。

4.2移动模型介绍
移动模型是无线自组织网络仿真研究的重要工具,用以规划节点的移动轨 迹。由于系统移动通信、能量消耗等均与移动导标的移动路径有很大关系,导 标节点的移动路径直接影响无线传感器网络节点定位的性能。因此,有必要对 导标的移动模型进行分析,以选择合适的导标移动模型,达到应用需要的定位 精度。 无线传感器网络中节点彼此相互独立,自行控制自己的运动参数(如速度、 方向和目的地等),此种运动模型为个体移动模型r71】。个体移动模型具有遍历性, 以节点运动的随机性为特征,节点在不同时刻的采样具有相同的分布。个体移 动模型主要有三种移动模型f72】:随机路点模型(Random Waypoint Model,

R帅M)、随机路径模型(Random Walk
Direction Model,RDM)。

Model,删)和随机方向模型(Random

4.2.1随机路点模型
随机路点移动模型【73】是一种简单、适用范围广泛的移动模型,最早由

Johnson和Maltz提出。RWPM节点移动模型主要是在节点移动速度和方向之间
加了一个暂停时间(r),其主要思想是:初始时,所有节点随机分布在仿真区 域内,每个节点在仿真区域内部随机选择~个目的点,节点采样分段移动轨迹,

每一段轨迹被称为~个运动周期。选定目的点后,节点在速度【‰,‰x】区间中
选择一个速度v,此后以速度’,向目的点匀速移动。到达目的点后,节点暂停丁 时间,然后重新选择一个运动速度和目的地,开始下一个周期,重复此过程直 到仿真结束。 由于RWPM节点移动模型加入了暂停时间,避免了随机路径模型中突然转 弯的情况发生,允许不同的速度和临时性的稳定节点。缺点在于节点很可能选

36

武汉理工大学硕+学位论文

择中心结点作为目的地或位于中心区域的目的地会概率较高,节点的移动会出

现聚合——分散——聚合这样的循环过程,形成非均匀现象,有时还会产生节
点瞬时不稳定性移动。但RWPM节点移动模型简单且易于实现,模型与现实节 点移动情况相似,所以在仿真中得到了较多运用,是目前比较流行的一种移动 模型,本文所有的仿真均采用此模型完成。

4.2.2随机路径模型 随机路径移动模型74】最初是为了模拟物理微粒的不可预测随机运动,可追
溯到爱因斯坦在模拟粒子的布朗运动。在无线传感器网络中一般认为导标节点 的移动轨迹具有不可预测性,所以Random Walk移动模型也可用于模拟移动导 标的运动。与RWPM节点移动模型最大的不同在于节点在移动过程中不会暂停, 节点从当前位置选择一个随机方向和运动速度,沿着此方向运动一定的时间或 一段距离,然后变换方向开始下一个运动过程。当节点运动到边界区域时,将 被反弹回区域内,然后以被反弹回时的新路径继续移动。
Random

Walk移动模型一般假设:节点初始时在【0,2兀】内选择一个随机方

向,运动速度为【‰,‰】之间的均匀分布或高斯分布。节点沿某一方向运动一
定时间或一段距离,然后进入下一周期,按照新确定的方向和速度继续移动。 Random Walk移动模型在模型初始化或特殊环境下还是可以借鉴的,它是完全随 机移动模型的基础,采用的是一种无记忆运动方式。与现实应用场景不同的是 此模型中节点在移动时会发生突然转弯或停止的情况,这将不利于采用此模型 对算法的性能进行分析研究。

4.2.3随机方向模型
随机方向移动模型【75】最早由E.M.Royer提出,故此模型也可称为Royer模 型,是随机路点移动模型的变形。该模型移动特点是节点在仿真区域内不能停 留,一个运动周期内只能开始并结束于区域的边界。随机方向移动模型克服了 RWPM节点移动模型的缺陷,避免了节点的聚合分离状况且有效提高了邻居数 目的相对稳定性。随机方向移动模型选择一个确定的移动方向,而非随机的目 的地。移动导标选择运动方向后,将会沿此方向一直运动到模拟区域边界,然 后选择一个[0,兀】之间的方向返回模拟区域继续运动,直至循环结束。

37

武汉理工大学硕士学位论文

4.3限定区域的确定
将多能量级的思想引入动态网络,主要思想是移动导标在网络中随机游

走,移动导标不停地游走,未知节点会接收到许多导标的定位信息。若所有的
定位信息都参与节点的位置估计,计算量将会大大增加。为降低计算的复杂

度,当节点收到至少3个导标定位信息时,将导标分为甩组(c『n3),根据任意
3个导标形成的拓扑结构,从中选择1组导标用于定位,确定未知节点的限定区

域(3个导标相应能量环形成的公共区域,如图4_1(b)所示),即:未知节点 (加的限定区域。然后采样与3.3节类似的判断计算方法,即可实现节点的位置
估计。为便于比较分析,在此约定此种算法为移动多能量级节点
(Mobile-Cencentrie Anchor Beacon,M.CAB)定位算法。由于采样数量过多,

会造成较大的计算量且提高精度幅度不显著,此时约定能量级的数量(m)为
2169]。

图4.1

节点通信范围及限定区域的确定

4.4算法设计
在Monte Carlo方法中为获得足够的有效样本,在重采样滤波阶段抽样次数 过多且易出现粒子退化现象。考虑到Monte Carlo方法的计算负载及抽样耗时, 本文对其进行了改进,提出一种改进Monte Carlo的移动节点定位算法。与Monte Carlo方法不同的是,提出的算法仅利用少量样本即可实现节点的高精度定位, 且无需对样本进行迭代更新,大大减少了计算量。 首先,利用多能量级节点定位思想,确定未知节点的限定区域,以在限定
38

武汉理工大学硕士学位论文

区域投点取样的方式,代替Monte Carlo算法的样本滤波更新阶段。然后,通过 对样本分配权重、权重归一化,最终得到未知节点的估计位置。具体算法设计 如下: 步骤l:利用多能量级节点定位思想,首先确定出未知节点的限定区域,具 体方法如4.3部分所述; 步骤2:在限定区域进行投点采样,得到若干未知节点的估计样本;

步骤3:通过后验概率密度函数(式4.1)为每个样本分配权重:

p(以I

di)=÷e


一!盔二生!!
2矿(4-1)

o~z兀

其中:《表示样本到相应导标节点的距离,di表示未知节点与导标之间的测 距距离,or表示距离测量误差标准差。

步骤4:利用(式4.2)对样本的权重进行归一化:

万=≠L
∑皑’
j=l

(4-2)

步骤5:由于在步骤1中,已对未知节点可能的存在区域进行了限制,此时
省去样本的重采样滤波阶段,直接输出未知节点的估计坐标,即:

(叠,夕)=(∑吒i%i,∑一圮)

(4—3)

除采用上述方法,完成未知节点的位置估计外,本文还分析了一种更为简 便的未知节点估计位置的求取方法,即:在步骤2获得若干样本后,利用质心 定位原理,直接求取样本集的坐标平均值,作为未知节点的估计位置,定义此 方法为限定区域随机采样法(Sampling in
Constraint Region,SCR)。

4.5精度改善策略
基于Monte Carlo的定位算法,有效样本集最终所处的位置都将是多个导标 形成的公共有效区域。公共有效区域越规则,形成的有效样本接近未知节点的 概率越大。文献[76】分析了导标节点的位置拓扑关系对定位结果的影响,分析指

出,当导标节点共线或近似共线时,很容易导致定位失效,文献中采用四种方

39

武汉理工大学硕士学位论文

法对共线问题进行了描述,但并未提出系统化的解决方案。本文提出了一种导 标共线解决策略,引入了共线度限制因子(Collinearity Limiting Factor,CLF),以 约束导标的拓扑结构,从而解决导标共线问题。具体方法如下: 在某二维平面内,假设三点分别为彳、曰、C,且三点不处于同一直线上, 则三点可形成一平面三角形ABC。

定理:假设三角形ABC的最长边为三AB,分别以么、曰为圆心,以£AB为半
径画圆,可得两圆的公共区域(图2所示)。则C点必位于此公共区域内。

证明:反正法。若C点不在此公共区域内,则三Ac、Lac必有一边的长度大
于£AB,与假定条件相悖,故C点必定处在此公共区域内。

过C点作三AB的垂线h,以h与三AB的比值作为共线度限制因子(C∽。由
图4.2可知:

当C点位于顶点时,三角形ABC为等边三角形,此时CLF值最

大为压/2;当C点处在线段AB上时三点共线,此时CLF的值为0。

么惑
通过上述分析,可确定出CLF的取值范围为[0,以/2】。CLF的值越小,3 个导标越接近共线,当CLF值为0时,三点共线。在实际应用中,可通过变化 CLF值,改变导标之间的位置分布,最终通过设定某一阈值约束导标节点之间 的拓扑关系。

4.6算法模型
以上几节对移动无线传感器网络中的节点移动模型进行了比较,介绍了基 于多能量级的移动无线传感器网络节点定位原理,同时对改进的Monte Carlo方 法进行了描述。最后对导标共线约束策略进行了分析。图4.3所示为提出算法的 技术路线图。

武汉理T大学硕士学位论文
节点内部结构模块功能分析l l节点角色类型

网络节点拓扑结构模型

改进Monte Carlo方法

多能量节点定位原理

分布式节点定位模型

导标共线解决策略

节点移动模型

移动无线传感器网络节点定位算法
算 法 算 法 改 进




离散事件仿真建模软件OMNeT++

节点有效定倥

图4.3算法技术路线图 节点定位算法以节点定位的高精度、能量的低消耗、定位的低代价等为目 标,将多能量级节点定位思想引入动态网络中,同时在分析Monte Carlo定位算 法基础上,对其进行了改进,同时针对定位过程中导标节点共线时定位失效情 况,提出了一种导标约束下的精度改善策略,最终形成了基于多能量级的改进
Monte Carlo的节点定位算法。对节点定位算法的研究采用理论分析与仿真实验

相结合的方式,首先分析了节点内部模块的功能及网络节点的不同类型,在此 基础上形成了网络节点拓扑结构模型;然后将多能量级思想与Monte Carlo方法 相结合,构建了分布式节点定位模型;紧接着将导标共线解决策略引入到定位 模型中,通过节点移动模型,形成了分布式移动无线传感器网络节点定位算法。 最后采用OMNeT++对算法的定位性能进行了仿真验证、改进及评估。 利用OMNeT++对提出的算法进行仿真分析,具体的仿真流程如图4.4所示。 第一步:编写NED文件。利用OMNeT++中的子模块、门、参数、链接、网 络等建立网络拓扑结构,并利用编译器NEDC编译成C++文件,得到拓扑结构文件。 第二步:编写C++代码。可动态加载网络拓扑,实现对定位算法、精度改善

4l

武汉理工大学硕士学位论文

策略的编写及修改。 第三步:仿真编译。对编写的算法及协议进行编译和测试。 第四步:配置(Ini)文件的描述。完成对模块参数、仿真时间、仿真场景 等的设置,便于对算法和方案的比较。 第五步:仿真及分析。利用仿真平台提供的图形化输出工具Plove和Scalar, 对仿真结果进行分析,验证算法的优劣。

图钳仿真流程图
图4.5所示为节点仿真界面。在形成网络拓扑前,为便于对仿真条件进行控 制,用户可手动输入各种仿真参数。初始时每个节点都有一个编号,并随机分 布在仿真区域内,导标节点移动规律遵循随机路点移动模型,导标移动过程中 当未知节点处在导标感知范围内时就会建立链接进行通信。同时用户可以通过
42

武汉理工大学硕士学位论文

仿真速度按钮选择合适的仿真速度,也随时暂停运行程序,查看仿真过程。

OMNeT++为用户提供了良好的运行界面,大大方便了用户对仿真过程的控制及
算法程序的修改。
}托 ‰溅

捞4埘々

’:*t

p僻RV

一,h协t.¨

》《一

钿舶们’Ie3I

H掺—渊鹩
圉嘲
盘一麓 ;一豢

堡l璧囊型塞壁癯i塞i堂i丝i筮熊鲤塑!壁翟壅堡... E州救 T电∞∞∞O I喇
≯壤戴,辍擘尝建-j:亟置曼型

M举酬甜№秘删22


N嘲:地t捌dI叫≈睁伯回

豳嘲削l扫娃秘删妇’
奉■ 黔啊 移豳 盎■ 密曩 事曩 宙曩 审一 事瞄 母啊 移嘲 奉豳 审囵
审一

国嚣 零囝 审圈 密圜 毋瞄 国瞄 审瞳 密曝 秘豳 毋曩 审■ 密曩 审盈
毋豳

图4.5

OMNeT++仿真界面

4.7性能评估
为验证导标共线解决策略及算法的有效性,利用Matlab7.4工具,对改进
Monte Carlo的移动节点定位算法(IMCML)与移动多能量级节点定位算法

(M.CAB)及限定区域随机采样法(SCR)在不同环境下分别进行仿真实验,

并对结果进行分析。在实验过程中,300个传感器节点随机分布在10R×10R的 矩形感知区域内,月为节点通信半径,导标密度‰)为O.1,导标随机部署在网络

中,网络的平均连通度(Cp)为10,导标最大移动速度(‰x)为R。为减小计算量
及节省能耗,当未知节点定位后,就向网络广播己定位信息,此后不再接收导

43

武汉理工大学硕士学位论文

标的定位信息。

4.7.1共线度限制因子
为验证共线度限制因子(CLF)对节点定位的有效性,通过改变CLF值,分析

CLF对不同节点定位方法的影响。

O.35

o.3

O.25


冀o.2

删0.15

O.1

O.∞

0 O

O.∞

O.1

0.15

0.2

0.25

0.3

0.∞0.4

0.45

共线度限制因子(CLF)

图4.6共线度限制因子vs定位误差 由图4.6可知,三种定位方法的定位误差都随着CLF值的增大而减小,当 CLF值大于O.24时,IMCML法定位误差趋于稳定。随着CLF值的不断增大, 三种方法的定位误差会继续降低,当CLF值为O.48时,M.CAB、SCR及IMCML 算法的定位误差相比未采用CLF抑制时,分别降低了43%,52%,57%。若CLF 值进一步增大,虽然不同方法的定位精度将会继续提高,但已变化不大,且导 标移动的步数将明显增加,耗时过长,故仿真未对CLF值大于O.48时作进一步 的分析。综合考虑节点的移动能耗及定位效率,在下面的仿真中,约定CLF值
为0.24。

4.7.2样本数量
由于先确定出了未知节点的限定区域,故对样本的投点范围已有了很大的 约束,无需太多的样本即可实现节点的有效定位。相比MCL、粒子滤波等算法, 需要的样本数量明显减少且不需要对样本进行迭代更新。

图4.7分析了样本数量(加对节点定位算法的影响,由于多能量级节点定位

武汉理工大学硕+学位论文

算法无需采样,故只对随机采样法和改进Monte Carlo算法进行了仿真。由图4.7 可以看出,随着样本数量的不断增加,两种方法的定位精度都出现了不同程度 的提高,当Ⅳ大于10时,两种算法的定位误差均已趋于稳定。


jl|】j

略 遥 删

o.05

J———,———————,———————————————————————————————————————————————————一
4 6 8 10 12 14 16 18

样本数量(N)

图4.7样本数量VS定位误差
0.4—

—_∈卜一M乇AB
0.35j

——十一SCR
—_三}一IMCML

髫o.2—

2仉3厂~\一—~。


琶0.25一

0.05…——…——,
100

150∞0

3,50 2∞3∞ 节点数目变化

4∞4∞



图4.8节点数目VS定位误差

4.7.3节点数目
在保持导标密度为O.1,导标最大移动速度为尺不变的条件下,分析不同节 点数目对定位误差的影响,仿真结果如图4.8所示。随着节点数目的增加,三种 算法的定位误差都略有波动,但误差变化不大。当节点数目达到300时,三种
45

武汉理工大学硕士学位论文

算法的定位误差均基本稳定。

4.7.4导标移动速度

为验证算法对导标不同移动速度的适应性,导标的最大移动速度(‰x)从
0.2R到2R变化,保持节点数目为300,导标密度为O.1,图4.9为导标移动速度 对定位误差的影响图。由图4-9可知:随着导标的移动速度不断增大,M.CAB 法相比SCR法和IMCML法,定位误差下降的幅度要大,这是因为随着移动速 度增大,未知节点接收的导标信息,易于形成较好的拓扑结构。相比MCL、MSL 算法,文中三种方法对导标的移动速度更具适应性,不会出现因导标速度的增 大导致定位精度下降的情况【731。

——e—M-CAB

——+一SCR

氅0.25 糕

君。?2,、、、、、、、、---。\.。..。。。+
图4-9导标移动速度VS定位误差

。.,j—、~、5———、E——h一目日日臼日

4.7.5导标密度
导标密度是指导标节点数量占整个网络节点总数的百分比。为了分析导标

密度对节点定位误差的影响,在保持节点总数为300,导标最大移动速度(‰。)
为R的条件下,分析导标密度(鼬)在O.01 ̄o.2变化时,对节点定位误差的影响。 图4.10(a)分析了导标密度变化对定位误差的影响,随着导标密度的不断增大, 节点的定位精度变化不大,基本保持稳定。图4.10(b)为不同导标密度下,定 位步数及数据包数的变化情况。随着导标数量的增加,未知节点在导标一次移 动过程中,能够接收到更多的定位信息,因此导标定位需要的移动步数及数据

武汉理T大学硕士学位论文

包数都出现很大程度的降低。当导标密度为0.1时,需要的移动步数及数据包数
均基本稳定,分别为53,1454。

跚 撇 硼
硼 彻
赫龄,凝回骣凝

j\~二二_
j∑!一—一一,一一
0 2 4 6 8 10 12 14 16 18 20




导标节点密度(%)
(b)

0.9 O.8

0.7

6r,-0.6

锇0.5 巷 掣0.4 趔
0.3

0.2

O.1

0 0.2 O.25 0.3

测距误差

图4.11测距误差VS定位误差

4.7.6测距误差
在实际应用环境中,信号传播易受多路衰减、障碍物、不规则信号的传播

47

武汉理工大学硕士学位论文

特征等因素影响而产生距离估测误差,称为测距误差。在节点总数为300,导标

最大移动速度(‰x)为R,导标密度恤)为0.1的条件下,分析测距误差对算法定
位精度的影响。 将IMCML法分别与MCL及MLE算法在不同测距误差下进行了比较,如 图4-11所示。三种算法的定位误差均随测距误差的增大而增大,本文的IMCML 算法相比MCL、MLE算法具有更高的定位精度,对测距误差有良好的适应能力, MCL算法次之,MLE算法对测距误差的变化最为敏感。

o}———‘■———商————石———1r———葛———■占———≮
步数
(b) O.4

||||o.z÷二—————————————————一
删o.1÷B—龟——}—号—导—_{}—号—_∈__—争—÷——}—}—乇卜—}—乇卜1}—罟—由
步数
o.4

岔o‘3 窑

7棘。e

。 ——弓一M?C^B——卜SCR一.乇三一_蚺CML。1。’1 一 '‘。 。 ‘。 。 。 一。 。 。 。V。 。 。 。●。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 _。 。_。 。 。 ●’。


e—e_—争—e_—争—伊—e_—争—铲—争—伊—e_1 j—卜-毛‘'e—母—争—e-—e一“卜_。呻—”一’弋卜一t’” 丫

o}———1_———亩————畜———1}———磊_———亩—_
—_∈卜一M-CAB——一SCR——三一MCML
e/



£m3。詹——争—牟—e—e一—B~汁_争—《P—e——争—_卜—e——寺——号—品 囊n2一.一——一一~一一一~—一一一——一——+—二
步数

£届——争——卜—e——e一。}~毛P—号一_争—《卜-—e——争—_卜—e——寺——卜——由

捌O.1一-一—三一.一一三一t}—一三一三-.-三一三二~.———÷一.‘三一——∈———三——‘i~————。E

图4.12(a)为随机路径模型VS定位误差.(b)随机路点模型VS定位误差.(c)随机 方向模型VS定位误差

4.7.7不同移动模型
本节对提出的三种定位方法在不同移动模型下的定位精度进行了分析。随 机路点模型是目前比较流行的一种移动模型,本文所有仿真均基于此模型。另

武汉理工大学硕士学位论文

外两种移动模型分别为随机路径模型和随机方向模型。保持节点的总数目为

300,导标密度(sd)为O.1,导标的最大移动速度(‰x)为R,分析不同移动模型对
提出的三种方法定位精度的影响,仿真结果如图4-12所示。

随机路径模型中,由于导标在每一时刻的运动速度和方向具有很强的随机
性,导致定位稳定性及定位精度较差。在随机路点模型中,导标经过仿真中心 区域的概率较高,未知节点易于收到更多的定位信息,故定位效果比其他两种 移动模型要好。如图4-12所示,SCR法和IMCML法比M.CAB法有更好的定 位稳定性,而IMCML法的定位精度最好。 综上所述,通过在不同条件下对提出的算法进行仿真验证,文中提出的 IMCML法的定位误差最小,且算法稳定性较好;SCR法简便易行,定位精度比

CAB法要好;CAB法的定位效果和稳定性均不如其他两种算法。
4.8本章小结
本章在第3章的基础上进行了进一步的研究,将多能量级的思想引入动态网 络,提出了一种基于多能量级的改进Monte Carlo的移动节点定位算法,并验证 了多能量级节点定位算法在动态网络中的有效性及限定区域随机投点法的实用 性。对移动定位中的几种节点移动模型进行了分析,并对改进Monte Carlo方法 进行了描述,对定位算法进行了设计,最后提出的算法通过仿真软件OMNeT++ 进行了仿真验,设计了算法的技术路线及算法仿真流程,分析了节点算法的定 位性能。通过改变不同的仿真条件,对三种节点定位方法的定位精度及算法稳 定性进行了分析比较,算法均表现出了良好的定位效果。另外,提出了一种导

标共线度约束策略,通过引入共线度限制因子(C驴),很好地解决导标共线问
题。仿真结果表明:通过改变CLF值,提出的移动节点定位算法的定位精度有了 显著提高,算法在低导标密度及高移动速度下均具有较高的定位精度,具有较 好的适应性和稳定性。

49

武汉理工大学硕士学位论文

第5章总结与展望
随着人们研究的不断深入,作为一种极具应用前景的新兴网络技术,无线 传感器网络逐渐走向成熟,为大规模应用于各种领域提供了可能。无线传感器 网络在海事监控传感网络、物联网等热点技术中均起着重要作用。但目前大多 数的场景都与节点的位置信息密切相关,有效获取节点位置信息是无线传感器 网络迈向实用化进程的基础和前提,展开对无线传感器网络节点定位的研究具 有十分重要的理论和现实意义。在节点定位中如何设计一种既可以有效提高节 点定位精度,又能使计算代价与网络寿命之间取得平衡的节点定算法,是研究 工作者面临的具有挑战性的课题。 5

1全文总结
本文探讨了无线传感器网络中节点定位问题,对节点定位技术进行了系统

介绍,着重分析了基于免测距的分布式节点定位算法。在研究多能量级节点定 位原理基础上,提出了一种导标优化选择策略,并利用OMNeT++分析了算法的 适应性。基于多能量级节点定位原理,对移动无线传感器网络节点定位算法进 行了研究,通过改进Monte Carlo定位算法,设计了一种改进Monte Carlo的移 动无线传感器网络节点定位算法。 本文的主要工作及研究成果总结如下: (1)概述了无线传感器网络的特点及体系结构,分析了国内外在无线传感 器网络领域的研究进展,并对无线传感器网络节点定位技术的研究成果、目前 存在的主要问题及节点定位算法的设计进行了详细分析。 (2)详细分析了离散事件仿真软件OMNeT++,对软件的系统结构及软件 发进行了介绍。总结了节点定位的常用的测距手段和节点位置计算方法,并对 当前常见的节点定位算法进行了分类。 (3)针对无线传感器网络的内在特点及免测距节点定位算法的局限性,在 分析多能量级节点定位原理的基础上,提出了一种基于多能量级的导标选择策 略。其主要的创新点在于采用节点能量分级思想的同时,采用公式论证了导标 节点拓扑结构对节点定位的影响,在此基础上提出了一种导标选择策略,并利 用OMNeT++对提出的算法进行了仿真验证。仿真结果表明:多能量级节点定位

50

武汉理工大学硕士学位论文

算法具有很好的适应性,提出的算法有效改善了节点定位的精度,并减少了估 计节点位置时的计算代价。 (4)在分析多能量级节点定位原理基础上,将多能量级思想引入动态网络 中。对MonteCarlo算法进行了改进,结合多能量级节点定位思想,提出了一种 分布式移动无线传感器网络节点定位算法。IMCML算法的主要优点是能够有效 解决Monte Carlo算法中样本采样过多问题,通过能量分级思想省去了重复采样 过程,有效避免了粒子退化现象,大大减小了计算量。同时为了解决导标共线 或接近共线时节点易出现的定位失效问题,引入共线度限制因子概念,提出了 一种基于导标约束的精度改善策略。最后利用OMNeT++完成了提出算法的仿真

验证。仿真结果表明,提出的节点定位策略在计算复杂度及定位稳定性等方面
表现出的良好的性能,可实现较高的定位精度。算法具有很好的自适应性、可 扩展性和鲁棒性。该算法的定位精度可满足多数对节点位置信息要求较好的无 线传感器网络场景。

5.2未来工作展望
本文在研究多能量级节点定位原理的基础上,围绕节点定位问题展开了研

究,针对算法的不足之处进行了改进,取得了一定的研究成果。但由于无线传
感器网络节点定位技术是一个很复杂的课题,未来研究中仍面临着诸多问题。 展望未来,后续的研究工作主要围绕以下几方面进行: (1)在节点定位的研究中,对节点通信不规则性考虑欠缺。无线传感器网 络节点的通信范围理想中都是一个圆形或球状,但在遇到障碍物或噪声影响时, 节点的通信范围就会变成不规则状,这样将会对节点的定位精度有一定影响。 未来研究工作需要考虑通信不规则性对节点定位的影响。 (2)节点定位模型的完善。本文在研究移动节点定位算法时,仅考虑了未 知节点静止而导标节点运动的情况,对网络内所有节点均移动的情况未进行深入 研究。对复杂环境下节点移动定位问题的模拟仿真工作有待进一步的深入研究。 (3)节点移动路径规划问题。本文在进行移动节点仿真时,采用的是目前 常用的随机移动模型,这种模型可以较真实的模拟节点移动轨迹。然而,对有 些应用场景来说,导标节点的运动轨迹是可以预先设定的,此时就需要对节点 的移动路径进行规划。因此,为满足不同应用场景的需要,实现未知节点的有 效定位,有必要对导标节点的移动模型进行进一步的研究。

5l

武汉理工大学硕士学位论文

此外,无线传感器网络技术逐渐走向成熟,为大规模应用在其他领域奠定 了良好的基础。由于无线传感器网络的特征与海事监控领域的信息需求具有很 强的适应性,基于无线传感器网络的海事监控系统,也可称为海事监控传感网

络,在无线传感器网络的推动下将具有很好的应用前景。近年来,包含无线传 感器网络技术的物联网逐渐走进了人们的生活,受到了人们的广泛关注。在国
家大力推动工业化与信息化融合的背景下,着手发展物联网产业将具有极广泛 的应用前景。

52

武汉理工大学硕士学位论文





转眼三年的研究生生活已接近尾声,值此论文完成之际,我要向在硕士研 究生阶段给予我悉心指导的老师、帮助支持我的同学及亲友们致以崇高的敬意
和衷心的感谢!

感谢我的导师郭志新副教授和刘克中副教授!感谢导师们为我提供了良好 的学习研究环境,他们乐观的进取精神、严谨的治学态度和勤奋工作的敬业精 神,使我受益匪浅,导师给予我的关怀和恩情,我将永远铭记于心。在课题研 究过程中,刘老师为我提供了许多交流锻炼的机会,使我的自身能力有了很大 的提高,这是我在硕士求学期间的最大收获!在此,向我的恩师表示诚挚的谢
意!

感谢课题组张金奋同学,张金奋在我发表研究成果、撰写毕业论文期间提 供了很大的帮助,他勤奋、刻苦,对工作认真负责又不失幽默,使我受益良多。 能够在硕士阶段认识他,并与之合作是一件非常愉快的事情,在此深表谢意。 感谢课题组熊迹、米小亮、程磊、陈巍博、干伟东、蔡学龙等同学及耿志 兵、李昊、李志等研究生同学,和他们在一起交流和讨论开阔了我的思路,他
们给我的工作和生活带来了无限的乐趣。

感谢华中科技大学胡富平博士及信息学院付琴老师,感谢他们在我学习 OMNeT++及课题研究中对我的无私帮助,使我最终取得了学业上的进步和成
功。

感谢精心培育我成长的父母和亲人们,感谢他们在我二十多年求学过程中 给予的精神与物质方面的无私付出,给予我无尽的信任与支持。他们的理解和
关爱是我不断进步的精神支柱。

在此衷心感谢各位评阅在百忙之中抽出时间对我的论文进行评阅。

崔永强 2011年5月

53

武汉理工大学硕士学位论文

参考文献
【l】Yick J,Mukherjee B,Ghosal 52(1 2):2292-2330.

D.Wireless删network
on

survey[J].Computer Networks,2008,

【2】Bojkovic Z,Bakmaz B.A survey
011

wireless sensor

networks deployment【J】.WSEAS

Trans.

Communications,2008,7(12):1172-1181.

【3】黄小桑,王汝传,叶宁.基于无线传感器网络的普适计算中分发机制研究叨.计算机科
学,2010,37(6):111.113.

【4】毛晓峰,杨珉,毛迪林.无线传感器网络应用综述【J】.计算机应用与软件,2008,25(3):
179-181.

【5】吴键,袁慎芳.无线传感器网络节点的设计和实现闭.仪器仪表学报,2006,27(9):
1120.1124.

【6】Robert D.The

Future

ofTechnology[J].Business Week,2003,25(8):1-5.

【7】Vivekanandan V Wong V W S.Concentric Anchor-Beacom(CAB)localization for wireless
sensor

networks【C】.Proceedings

of

2006

IEEE

International

Conference

on

Commulfications,Istanbul,Turkey,Jul.,2006:3972-3977.

【8】蒋志鹏,高随祥.无线传感器网络节点定位的同心圆改进算法【J】.计算机科学,2009,
36(10):4648.

【9】Chao Wang,Kai

Liu,Nan

Xiao.A Range

Free

Localization Algorithm Based of 3rd Multi-Conference

on OIl

Restricted-Area for Wireless Sensor

Networks[C].Proceedings

Computing in the Global Information Technology,Athens,Greece,Jul.,2008:97-101.

【10】史清江,何晨.多功率移动锚节点辅助的分布式节点定位方法【J】.通信学报,2009,30
(10):8.13.

【11】闫斌,周小佳,王厚军,等.无线传感器网络功率控制的质心定位算法明.电子科技大 学学报,2010,39(3):416419.
【12】Hu L X,Evans D.Localization for mobile sensor networks[C].Proceedings
International Conference 45—57.
on

of 10m annual

Mobile computing and networking,Philadelphia,USA,2004:

【1 3】Wang W D,Zhu Q X.Sequential monte carlo localizartion in mobile Wireless Networs,2009,15(4):481495. 【14】Sheu


sensor

networks[J].

P’Hu W K Lin J C.Distributed

Localization Scheme

for Mobile Sensor Networks[J].

IEEE

Tram.on Mobile Computing,2010,9(4):5 1 6-526.

武汉理工大学硕士学位论文 【15】石琴琴,霍宏,方涛,等.使用最速下降算法提高极大似然估计算法的节点定位精度【J】. 计算机应用研究,2008,25(7):2038.2040.
【16】Atzori
L,lera

A,Mombito G The Intemet ofThings:A survey[J].ComputerNetworks,2010,

54(1 5):2787-2805. 【17】Amardeo
C S,Girao J.Identifies in the Future

Intemet of Things[J].Wireless Personal

Communicalio璐,2009,49(3):353-363.
【18】http://news.xinhuanet.com/eworld/2010-08/04/c_12407101.hun

【19】沈苏彬,毛燕琴,范曲立,等.物联网概念模型与体系结构阴.南京邮电大学学报(自 然科学版),2010,30(4):1-8. 【20】张顺颐,宁向延.物联网的体系结构与相关技术研究【J】.南京邮电大学学报(自然科学 版),2010,30(4):30.35.
【2l】Kavelaars W;Marls M.Wireless Sensor Networks in
Proceedings of 222-229.


Maritime Environment[J].

SPIE—The

International Society for Optical Engineering,2005,5986(1):

【22】Carapezza E,Bucklin A.Intelligent Maritime Security System with Sensor Networks for
Coastal

Environmental

and Homeland Security Applications[J].Proceedings of SPIE

on

Unmmanned/unattended Sensor and Sensor networks IV,2007.6736(1):1-15

【23】刘克中,谭钦文,严新平,等.海事监控传感网络系统结构及功能研究【J】.中国航海,
2009。32(1):1.5.

【24】Yang

X,Liu



Cui Y,et al—Modeling and Simulation for Maritime Surveillance Sensor of 10m International Symposium
on

Networks[C].Proceedings

Communications

and

Information Technologies,Tokyo,Japan,Oct.,20 1 0:2 1 5-21 9.

【25】Yunhao Liu,Zheng Yang,Xiaoping Wang,et a1.Location,Locafization,and Localizability[J]. Journal of Computer Science and Technology,20 1 0,25(2):274_297.

【26】张佳,吴延海,石缝,等.基于Dv..HoP的无线传感器网络定位算法【J】.计算机应用,
2010,30(2):23.326.

【27】Vidyasagar P'Atif S,Chang E.Wireless
International Conference
on

sensor

networks:A survey[C].Proceedings of 23m Networking

Advanced

Information

and

Applications

Workshops,Bradford,UK,May,2009:636-64 1. 【28]Yuying Tai,Bo Yang.Collaborative Proceedings of
9m International target
on

tracking in wireless Electronic

Sensor network[C].

Conference

Measurement and Instruments.

Beijing,P.R.China,2009:1005-1010.

【29】曹晓梅,何欣,陈贵海.传感器节点定位系统攻防机制研究【J】.计算机科学,2008,35
(7):36-41.

55

武汉理工大学硕士学位论文 【30】王毅,董梁,梁涛涛等.分簇覆盖的移动自组织网中节点位置辅助路由算法【J】.软件学 报,2009,20(11):3086-3100.
【3 1】Xin He,Xiaolin Gui.The Localized Area Coverage Algorithm Based WSN[J].Joumal ofNetworks,2009,4(10):1001-1008. 【32】http://www.omnetpp.org/.
on

Game-Theory

for

【33】Xian

Xiaodong,Shi

Weiran,Huang He.Comparison

of OMNET++and other simulator for
on

WSN simulation[C].Proceedings of 3m IEEE Conference
Applications,Singapore,Singapore,Jun.,2008:1439-1443.

Industrial Electronics

and

【34]Xue Yunjiao,Ho Sung Lee,Yang Ming,ct a1.Performance evaluation ofNS_2
wireless∞11sor networks[C].Proceedings of 2007 Canadian Conference Computer Engineering,VanCOUVer,Canada,Apr.,2007:1372?1375.

simulator for
Electrical and

on

【35】夏娜,安宝磊,蒋建国.无线传感器网络中目标跟踪算法的OPNET仿真[J】.计算机仿
真,2008,25(9):146-149. 【36】Shau S J’Chan W’T0dd W.MATLAB algorithm availability simulation tool[I].GPS
Solutions,2009,1 3(4):327-332.

【37】Park

S,Savvides



Srivastava M

B.SensorSim:A

simulation framework for

sensor

networks[C].Proceedings

of 3阿ACM International

Workshop on Modeling.Analysis

and

Simulation ofWireless and Mobile

Systems,Boston,United states,Aug.,2000:104-1 1 1.

【38】Pongor Q Statistical Synchronization:a Different Approach of Parallel Discrete Event

Simulation[C].Proceedings

ofthe 1992 European

Simulation

Symposium(ESS 92),Dresden,

Germany,Nov.,1992:125-129.
【39】Varga
A.The

OMNeT++distrete

event

simulation

system.Software

on-line:

http://whale.hit.brae.hu/onmetpp/,1 999.

【40】Varga A.Using
on

the OMNeT++discrete

event simulation

system in education[J].IEEE

Tram.

Education,1 999,42(4):372.

【4l】孟令军,王宏涛,夏善红.WSN节点声测g巨TOA值频域估计方法【J】.电子与信息学报,
2010,32(4):993.997.

f42】Bishop

A N,Fidan

B,D瞻锄9ay IL

et

a1.Exploiting geometry for

improved

hybrid

AOA/rDOA-based localization[J].Signal Processing,2008,88(7):1775-1791.

【43】Kuakowski P,Vales—Alonso J,Egea-L6pez antenna
arrays for wireless sensor

E,et a1.Angle-of-arrival

localization based

on

networks[J].Computers and

Electrical Engineering,2010,

36(6):1181?1186.

Ⅲ】赵昭,陈小惠.无线传感器网络中基于RSSI的改进定位算法【J】.传感技术学报,2009,
22(3):391.394.

56

武汉理工大学硕+学位论文 【45】熊志广,石为人,许磊,等.基于加权处理的三边测量定位算法阴.计算机工程与应用,
2010,46(22):99.102.

【46]王殊,刘克中,胡富平.无线传感器网络中导标节点共线的解决策略【J】.计算机工程与 科学,2007,29(2):119.121. [47】Rusnac Wireless
and R I,Gontean A S.Maximum Likelihood Estimation Algodthm Evaluation for Sensor

Symbofic Numeric Algorithms for Scientific Computing,Timisoara,Romania,Sept.,201 0:95-98.
Networks[C].Proceedings
of 12m International Symposium
on

[48】曾凡仔,孙正章,罗娟等.无线传感器网络的节点定位算法叨.通信学报,2008,29
(11):62.66.

[49】Dil B,Dulman S,Havinga只Range-Based Localization in Mobile
Lecture Notes in Computer

Sensor

Networks[J].

Science,2006,3868(1):164-179.
on

【50]MacLe觚S,Datta

S.A lower bound

range-free Ilode
on

localization algorithms[C].
Communication Systems,

Proceedings of 2008 mEE International

Symposium

Wireless

Reykjavik,Iceland,Oct.,2008:628—632.
【5 1】Priyantha N B.The Cricket Indoor Location System[D].Ph.D
Institute ofTechnology,2005.

Thesis,Massachusetts

【52】Nieuleseu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Telecommunication Systems,2003,22(1):267—280. 【53】Chintalapudi K K Dhariwal A,Govindan K Sectoring[C].Proceedings
et

a1.Ad-Hoc
Joint

Localization Using p.anging and
On

of

23m

Annual

Conference

Computer

and

Communic撕ons Socicties(INFOCOM 2004),Hong Kong,China,Mar.,2004:2662-2672.
【54】Niculescu D,Naih B.Ad Hoc Positioning

System(APS)Using AOA[C].Proceedings of 22们
Societies(INFOCOM 2003),

Annual Joint Conference Oil Computer and Communications San Franciso,USA,Mar.,2003:1734-1743.

【55】Ding Zhiguo,Zhu Shouhong.A

simple

approach

of

range-based

positioning谢tll

low

computational complexity[J].IEEE Tram.Oil 5832.5836.

Wireless Communications,2009,8(12):

【56】朱博,陈曙.一种无线传感器网络质心定位改进算法【J】.传感技术学报,2010,23(6):
868.872.

【57】张佳,吴延海,石峰,等.基于Dr-HOP的无线传感器网络定位算法【J】.计算机应用,
2010,30(2):323.326.

【58】Park

J,Haan

J,Park F C.Convex Optimization Algorithms for Active

Balancing

of

Humanoid Robots[J].IEEE

Trans.011 Robotics,2007,23(4):8 1 7—822.

57

武汉理工大学硕士学位论文
【59】Shang Y,Ruml W.Improved MDS-Based Localization[C].Proceedings of 23帕Annual Joint
Conference
on

Computer and Communications Societies(INFOCOM 2003),Hong Kong,P.

R.Chin钆Mar.,2004:2640-265 1. 【60】Ssu K F'Ou C H,Jiau networks[J].IEEE
H C.Localization with mobile

anchor

points in

wireless∞鹏凹

Trans.on Vc:llicul

Technology,2005,54(3):l 187-I 197.
cost

【61】Bulusu

N,Heidemann J,Estrin D.GPS-Less low

outdoor

localization

for very small

devices.IEEE Personal Communications,2000,7(5):28~34

【62】程远国,徐辉.传感器网络加权质心自定位算法叨.计算机工程与应用,2009,45(7):
105.107.

【63】嵇玮玮,刘中.DV-Hop定位算法在随机传感器网络中的应用研究阴.电子与信息学报,
2008,30(4):970.974.

【64】Priyantha N B,Balakrishnan H,Demaine E D,et a1..Mobile-assisted localizationin wireless
sensor

networks[C].Proceedings of 24m Annual

Joint Conference of the IEEE Computer and

Communications Societies(INFOCOM 2005),Miami,USA,Mar.,2005:172—183. 【65】Wang Yun,Wang Xhodong,Wang
process in wireless s豇lsor

Detain,et a1.Range—free localization expected hop Trans.On Parallel

networks[J].IEEE

and

Distributed Systems,

2009,20(10):1540-1552.

【66】张翰,刘锋.无线传感器网络基于凸规划的改进定位算法:Convex.PIT[J】.传感技术学 报,2007,20(5):1129.1133. 【67】史清江,何晨.多功率移动锚节点辅助的分布式节点定位方法【J】.通信学报,2009,30
(10):8.13.

【68】Vivekanandan V Wong
Wireless
Sensor





S.Concentric Anchor Beacon Localization Algorithm for Trans.on Vehicular Technology.2007,56(5):

Networks[J].IEEE

2733.2744.

【69]Sheu J P'Hu W K Lin ⅢEE
Trans.on

J C.Distributed Localization Scheme for

Mobile Sensor Networks[J].

Mobile Computing,2010,9(4):5 16-526.

【70】Aboughantous C H.Contribution Monte Carlo Method[J].Nuclear Science and Engineering,
1994,1

18(3):160-177.
on trust

【7 1】Wang K Wu M.Cooperative communications based

model for mobile ad

hoc

networks[J].IET Information Security,2010,4(2):68-79. 【72】刘宴涛,安建平,卢继华,等.无线自组网个体移动模型分析【J】.通信学报,2010,31
(2):36-43.

【73】Bettstetter C,Resta G Santi P.The node distribution of the random waypoint mobility model
for

wireless

ad hoc

networks[J].IEEE Trans.on Mobile Computer,2003,2(3):257—269.

58

武汉理工大学硕士学位论文 【74】赵金晶,朱培栋.Adhoc网络移动模型及其应用阴.计算机工程与科学,2005,27(5):
15.16.

【75】Carofiglio G Chiasserini C E Garetto M,et a1.Route stability in MANETs under the rand
direction mobility

model[J].IEEE

Trans.on Mobile Computing,2009,8(9):1 167一l 179.
target

【76]Fidan B,Drake S P'Anderson B D O,et a1.Collinearity problems in passive
localization using direction finding
on

sensors[C].Proceedings of

5m International Conference

Intelligent Sensors,Sensor Networks and Information

Processing,Melbourne,Australia,

Dec..2009:l 15.120.

59

武汉理工大学硕士学位论文



攻读硕士学位期间发表的论文及参与的科研项目

,一、发表的学术论文
【1】刘克中,崔永强,张金奋,严新平.基于Monte Carlo的多能量级移动节点 定位算法研究[J】.计算机科学(已录用) 【2】Xing
Yang,Kezhong

L沁Yongqiang Cui.Modeling
Networks【C】.Proceedings

and Simulation

for

Maritime

Surveillance Sensor
on

of 10也International

Sysposium

Communications and Infromation Technologies.Tokyo,Japan,

Oct.,2010:215.219.(EI Compendex,检索号:201 10213579658)

[3】Kezhong
Scheme

Liu,Yongqiang Cui,Jinfen

Zhang,Fuping Hu.Anchor Selection

for

Multi—energy

Level

Localization

Method

in

Wireless Sensor
on

Networks[C].Proceedings

of

4恤International Conference

Ubiquitous

Information TeclmologiOS&Applications.Fulmoka,Japan,Dec.,2009:297?300.

’≤


(EI Compendex,检索号:20101712879847)

【4】刘克中,崔永强,杨星,柴勤芳.水运包装环境有害物质判别方法的探讨【J】.
航海技术.2009,(5):1
8.21.







二、参与项目情况
[1】2008.01.2010.12:移动无线传感器网络节点定位方法研究,国家自然科学基 金项目(项目编号:60703099) 【2】2 2009.06.2010.12:基于传感网络的水路危险货物在途状态监测技术研究,浙 江省交通运输厅科技计划资助项目(项目编号:2009W08) 【3】2009.01.2010.12:海事监控传感网络中的拓扑控制理论及方法,武汉市青年 科技晨光计划项目(项目编号:200950431206) 【4】2008.12.2009.12:海事监控传感网络中的位置管理理论与方法研究,中国博. 士后基金项目(项目编号:20080440969) 【5】201 1.01—2012.12:无线传感网络环境下事件检测质量保障机制研究,中国博 士后特别基金项目(项目编号:201003502)


基于OMNeT++的无线传感器网络节点定位方法研究
作者: 学位授予单位: 崔永强 武汉理工大学

本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1880625.aspx


相关文档

基于OMNeT++的无线传感器网络节点定位改进算法的研究
无线传感器网络节点定位方法研究
[学位论文]基于协作模式的移动无线传感器网络节点定位方法研究
基于微粒群算法的无线传感器网络节点定位方法
无线传感器网络环境感知的节点定位方法
无线传感器网络中的分布式节点定位方法
水下无线传感器网络节点的自定位方法
减少无线传感器网络节点定位误差的方法
无线传感器网络中检测女巫攻击的节点定位方法
基于协作模式的移动无线传感器网络节点定位方法研究
电脑版