无线定位算法（精选12篇）
无线定位算法 篇1
0引言
在无线传感器网络(Wireless Sensor Network,WSN) 研究中,节点定位一直是热点问题,因为节点定位对无线传感器网络的有效性起着至关重要的作用[1]。目前,无线传感器网络已经广泛应用于智能物流、智能交通、智能家居以及智能农业等场合,而在这些应用场合中,对信息来源的精准定位至关重要,否则获取的信息将失去意义。目前,节点定位算法根据是否需要测量节点间的信息,划分为基于测距定位算法和无需测距定位算法[2]。基于测距技术定位算法定位精度高,但对硬件依赖性高,不适合低功耗、低成本的无线传感网应用领域。无需测距定位算法通过交换相邻节点间的信息确定未知节点的位置,其定位精度较低,但对硬件依赖性不高,并且能满足多数无线传感器网络的定位要 求,因此对其 研究和改 进有着重 要意义[3]。目前无需测距定位算法主要有质心算法、凸规划算法、DV-Hop算法和APIT算法等[4]。本文在质心和DVHop算法的基础上,提出了检测质心和DV-Hop算法节点可信度特征的算法,并对该算法进行了仿真测试。
1质心与DV-Hop算法
1.1质心算法
质心定位算法由南 加州大学Nirupama Bulusu等学者提出,它是一种无需测距的室外定位算法[5]。质心定位算法的基本思想是在一定通信范围内,通过计算包围未知节点的锚节点构成的多边形质心来估计未知节点的位置。 质心算法的伪代码如下:
begin
Each anchor node broadcasts its position.
Each sensor node listens for beacons(Xi,Yi)from anchors and computes a connectivity metric,for each anchor node Aiit has received beacons from.This metric is defined as follows:
;/*在时间t内,Nrecv(Ai,t)为从锚节点处接收到的信标总数,Nsent(Ai,t)为锚节点Ai发送的信标数目。*/
if(CMk,Ai≥M)then /*M是门限*/
end
质心算法的优点就是简单、计算量小,缺点是要达到较高的精确度,需要较多的锚节点数量[6]。
1.2DV-Hop算法
DV-Hop算法由美 国Rutgers大学的Niculescu提出[7]。DV-Hop算法的核心思想分为3个阶段:1计算未知节点与锚节点之 间的最小 跳数;2估算平均 每跳的距 离;3使用跳段距离代替实际距离计算未知节点的定位坐标。DV-Hop算法流程如图1所示。
DV-Hop算法的特点是:在节点分布均匀时,定位误差率低;而当节点分布不均匀时,由于计算距离过程中误差累积较大,因此定位误差率高。
2节点可信度特征分析算法设计
在相同的节点分布密度以及网络连通度情况下,质心与DV-Hop算法的可信度研究主要通过落在规定范围内的概率大小来反映,接下来将着重介绍如何设计概率分布检测规则。
2.1概率分布检测规则设计
概率分布检测规则 的主要思 想有:1分别用质 心和DV-Hop算法对同一未 知节点进 行定位,并分别记 录其值;2分别计算未知节点与两种算法计算值之间的距离; 3判断其距离与通信半径关系,记录落在规定范围内的概率,分别以2倍、1倍和0.5倍半径进行讨论。规则中之所以对2倍、1倍和0.5倍通信半 径所围成 的圆进行 讨论,是因为先以1倍半径为参照,然后对讨论的范围适当进行放大和缩小,如果目标节点落在了2倍半径之外,说明估算值误差大,如果目标节点落在了0.5倍半径内,说明估算值误差小。
图2给出了判断质心算法概率分布检测规则。其中A为目标结点,r为节点通信半径距离、D、D′、D′′为使用质心算法 估算的目 标节点可 能存在的 位置。以A为圆心,AB之间的距离为节点通信半径来讨论估算出的目标节点是否落在其围成的圆内。落在圆内,则进行记录,否则不记录。由于估算出的目标节点可能落在大于以A为圆心、AB之间的距离为半径的圆内D′的位置,也可能落在小于以A为圆心、AB之间的距离为半径的圆内D″的位置。为此,还要研究以A点为圆心、两倍的AB距离为半径和以A点为圆心、1/2的AB距离为半 径这两种 情况下,目标节点落在范围内的概率分布。DV-Hop算法的概率分布检测规则与上相同。
假设目标节点Ai的位置为(xi,yi),通过质心算法估算出的目标节点位置为Di,坐标为(pi,qi),则AiDi之间的距离为,r为节点通信半径距离,质心与DV-Hop算法概率检测公式为:
其中α为常量,其值为2、1或者0.5。
2.2节点可信度检测仿真算法
节点可信度检测仿真算法实现步骤:1产生节点均匀随机分布的网络拓扑;2分别用质心和DV-Hop算法估算出目标节点的位置;3用两点距离公式计算目标位置与估算出的目标位置之间的距离;4用概率检测公式(1)检测质心算法估算的目标节点是否落在规定范围内;5用概率检测公式(1)检测DV-Hop算法估算的目标节点是否落在规定范围内;6分别计算两种情况下的概率分布情况,计算公式为:
其中n为落在规定范围内的个数,N为节点总数,M为锚节点个数。
3仿真结果及分析
本文采用MATLAB 7.0对提出的算法进行仿真,仿真参数设置见表1,并对仿真结果进行比较分析,得到图3、图4、图5的结果。
图3、图4、图5为节点通信半径为30m,质心和DVHop算法概率分布 随锚节点 数量变化 及检测范 围分布图。试验结果表明,质心定位算法在锚节点数量少于20时,3种检测范围下其落在规定范围内的概率都较低,这说明质心算法在锚节点数量较少的情况下其可信度低于DV-Hop算法,同时也表明其定位误差率比DV-Hop算法大,但是随着锚节点数量的增加,特别是锚节点数量增加到25以后,其特性正好相反。
无线定位算法 篇2
定位数据在许多应用中可以显著提升所交换信息的价值。对于病患监控、资产追踪、库存控制、保全、仓储、制造物流以及对于高度敏感的服务与计费等相关应用而言，定位功能可以说是驱动了无线传感器网络的发展。节点或传感器位置信息也有助于无线网络的传递及调整。例如，无线节点可以使用全球定位系统(GPS)之类的现有系统取得位置信息。然而，GPS型系统可能相当昂贵，而且对于低成本且大范围的简易网络应用而言，也可能过于耗电且复杂。此外，GPS可以在室外环境有效又精确地发挥定位功能，但在室内则未必如此。
在许多无线个人局域网络(WPAN)应用中，针对具备定位功能的网络来说，其吸引力在于低成本的传感器装置，以及以低功耗自动运作达到较长的设备使用寿命。由于无线ZigBee传感器网络具有多样性，而且预期未来会相当普遍，因此区域定位很可能成为这类无线系统中最令人兴奋的特色之一。其中的概念是，透过简易且符合成本效益的方式，在大量的 无线ZigBee网络加入定位功能，即将定位功能加入传感器节点硅芯片装置中，这只会稍微提高复杂程度和成本。若将此类位置模块整合于芯片，并且运用无线信号处理过程中既有的信号指示器估计位置，例如接收信号强度指针(RSSI)，即可将增加的尺寸大小与功耗以及位置估计工作的复杂程度降至最低。无线射频定位是相当繁复的过程。透过分布式方法(算法)，可以将整个过程分成多个可管理的工作项目，这不仅能够使节点所需的资源量相对减轻，且相较于集中式的方法也能够明显减少位置相关的网络流量。
内建定位引擎的ZigBee SoC
对于大多数ZigBee型无线应用而言，若要使应用系统的成本及设计复杂程度降低，却又不减损IEEE 802.15.4/无线Zigbee网络技术的功能，具备最优设计的系统单芯片装置是重要关键。真正实行系统单芯片解决方案，也就是将无线射频收发器、数据处理单元、内存及使用者应用功能等所有的运作功能，整合于一个硅芯片，即可达到高效能、低成本及快速上市等优点。低功耗之所以能够发挥高效能，是因为芯片内建专门功能紧密交互作用，使得耗用的资源大幅降低。透过最低程度的系统物料清单 (BOM)、较小的体积尺寸与较少的组件、较简易的组装与测试，以及简单且可靠的设计，其制造成本得以降低并能加速上市时程。
图1是市售硅芯片解决方案中具有代表性的CC2431，这是一款真正的系统单芯片CMOS器件，不仅能够发挥高效能，而且能够满足以2.4GHz ISM频带运作的IEEE 802.15.4/ZigBee无线标准对于低成本及低功耗的需求。由于2.4GHz ISM频带具备最大频宽且全球通用，能够促进全球市场的发展及应用设计的弹性，IEEE 802.15.4标准的2.4GHz PHY因而具有相当大的潜力，
CC2431将高效能2.4GHz直接序列展频(DSSS)无线射频收发器结合广受业界肯定的精巧型高效率8051微控制器、8KB RAM、128KB嵌入式闪存，以及其他实用的支持功能。其中一项是强大的RSSI定位引擎，适用于低功耗ZigBee无线传感器网络应用，例如，资产追踪、病患监控、库存控制、保全及试行网络。芯片内建定位引擎的一项主要功能是分布算法，例如，在各个节点进行位置计算。由于过程中只传输计算的位置，而非进行计算所使用的数据，因此在节点进行位置计算能够减少集中式运算法会出现的网络流量及通信延迟。
图1 具备定位功能的ZigBee SoC装置
分布式定位功能(Distributed Localization)
CC2431的定位引擎是数字硬件区块，能够使无线节点在IEEE 802.15.4或无线ZigBee网络中以迅速有效的方式决定自身的平面位置坐标。利用相同引擎的多个参照节点或其他动态邻近节点所接收到的信号值，可以统计、演算与估计最可能的位置，以完成无线节点的定位。
定位引擎模块的设计使其便于使用及与芯片内建的微控制器接合。这个独立模块的功耗相当低并且运作快速，因此能够持续使用，完全不会耗用装置的运算资源。
在网络中，已知位置的节点称为参照节点，位置未知而需要计算的节点则称为待测节点(blind node)。根据距离最近的参照节点所收到的信息，CC2431能够运用分布式定位功能得知待测节点的位置。
其中的网络流量仅局限于(待测)节点的通信范围内所涵盖的节点，而不会扩及到可能相距甚远的中央节点。此分布式方法能够处理相同网络的大量待测节点，而集中式方法的网络流量则会因为待测节点过多而急遽增加。在参照节点与待测节点间交换的必要信息为参照节点的X与Y坐标。参照节点接收到的信息中内含所测得的RSSI值，定位引擎会根据参照(X，Y)坐标以及此RSSI值，计算出自身的(X，Y)坐标。
两个无线射频之间的RSSI值深受环境(变化)的影响，为了补足这个变动，CC2431的定位引擎会收集3～16个参照节点的数据，以用于计算位置。如果接收到的数据来自16个以上的节点，则会将接收的参照节点位置加以排序，并使用其中16个最强的参照RSSI值。
无线ZigBee网络使用CC2431进行的实际室内测量如图2所示。
图2 CC2431的分布式定位
结论
低功耗无线网络的应用除了具备可观的商机，还能够提升日常生活的安全性、舒适性及效率。采用高稳定IEEE 802.15.4标准的ZigBee具有技术质量与业界支持，能够促进无线传感器解决方案的普及。
无线网络室内定位系统研究 篇3
【关键词】 无线网络 室内定位 ZigBee 定位引擎
一、前言
随着计算机技术的快速发展和通信网络的普及，室内家电设备的单片机化和智能化得到了快速的拓展，促进了无线定位、组网技术、数字家庭等现代化理念不同程度的融入到人们的日常生活中来，提高了居家生活的自动化水平。无线技术的快速发展和不断成熟对新型无线业务的发展提供了条件，随着社会的发展，需要使用定位功能的应用越来越多。为了有效解决各类应用的自动定位问题，人们首先研发了基于卫星的全球定位系统，这种系统的定位精度较高，在军事领域解决了很多问题。但是，如果需要定位的设备位于室内时，这种定位方式的精度会显著下降。因此，需要对新的更优良的定位技术进行开发和研究，以弥补全球定位系统的不足。
到现在为止，比较常见的定位技术包括无线局域网、红外线、RFID和超声波技术等。已经应用到实际环境中的典型系统包括E-911、LANDMARC、Activebadge等，这类系统在工作原理和开发成本上都存在很大的区别，同时，不同系统的定位精度也存在不同。但是，如果只考虑室内移动设备的定位研究，则主要包括基于网络的和基于移动设备的方式。前者主要是根据不同的参考基站与移动设备的通信信息，并结合网络拓扑来计算设备的实际位置；后者则是根据移动设备当前与以前的和其通信基站的交流信息进行对比，来对设备的自身位置进行计算，GPS就是该领域最常用的应用。无线网络定位技术是使用无线射频信号或红外线信号等传输媒体构成的网络通信系统，因为不使用有线介质，因此能够满足网络用户随身化的需求。当前的短距无线技术主要包括无线局域网技术、蓝牙技术、ZigBee技术、NFC传输技术和超宽带技术，尤其是ZigBee技术已经成为领域研究的热点。和其他的技术对比，ZigBee具有低功耗、低速率和低成本的优秀特点，填补了当前无线通信领域的市场空缺，该技术的成功关键不只是因为本身的技术优势，还在于其功能的丰富性和使用的便捷性。所以，本文基于ZigBee技术，对高定位精度、高使用便捷性的室内定位系统进行了研究。
二、室内定位系统研究
2.1硬件设计
本室内定位系统的设计主要包括控制单元和基于ZigBee技术的无线通信网络系统两大部分构成。其中，系统控制单元主要是用来对定位数据和网络中的各个节点信息进行记录的构件。比较常见的控制单元包括ARM控制器和个人计算机等。但是，通常情况下，二者都不具有嵌入式的射频收发功能。所以，在实际的使用过程中，还需要和外部射频模块相连接。
基于ZigBee技术的无线网络主要使用IEEE802.15.4标准及ZigBee技术网络协议，该无线传输网络主要包含1个网关（该网管是ZigBee网络的的协调器，主要对整个无线网络服务的定位进行控制和协调，另外还对网络的当前状态进行检查）、不少于3个的参考节点（参考借点是位置已知的设备节点，而且要求该设备的物理位置保持固定不变）、以及定位节点（定位借点的位置会随着位置的变化而变化，详细的位置信息基于接收的参考节点位置，并通过硬件定位引擎的计算得到的）。
本系统在设计过程中，网关和参考节点使用CC2430射频芯片，定位节点使用支持2.4GHzIEEE802.15.4/ZigBee协议的、具有定位引擎硬件的CC2431射频芯片，控制器使用Samsung的处理器S3C2410。在数据的传输和处理过程你高中，网络节点间使用无线传输模式，而控制器和网关之间则使用串口通信的方式。
2.2定位算法概述
定位系统在接收到几个参考节点发出的信号以后，定位节点要对所得信号的传播损耗进行独立的计算。然后根据经验模型和理论化依据，把计算结果转化为实际的有效距离，最后再使用已有的算法对定位节点的真实位置进行定位。
接收信号的强度理论值计算公式为：
RSSI=-（10n*lgd+A）
其中，d表示设备到发射器之间的长度；n表示信号的传播常量；A表示1m处位置接收信号强度。
从公式中可以明显的发现，信号的强度与到发射器间的有效距离成对数衰减关系，定位节点和发射器间的长度离得越近，则信号强度偏差所产生的绝对距离误差就会越小。当这一距离到达某一个特定的数值以后，由RSSI波动造成的绝对距离误差就会显著的增大。
在实际的使用过程中，室内定位节点会使用较大的RSSI值的前面几个参考节点进行定位计算，这样能够有效降低系统带来的定位误差。这一硬件技术的要求比较低，使用的算法也相对简单。但是，由于定位设备所处的环境会经常变化，因此在实际的使用过程中要进行改进。
与一些常见的定位技术相比，CC2431定位引擎的定位速度快、定位精度高，而且在定位过程中不占用过多的处理器时间，因此可以作为本系统设计过程中的定位模块。
2.3软件系统介绍
本系统的开发主要基于Linux系统平台，在程序开发环境中对定位系统的图形化操作界面、信息展示界面和定位图形监控界面进行编写，并将其移植到控制单元ARM中。
在设计系统的串口程序过程中，需要首先建立一系列的数据发送和接收线程，在主函数中要使用信号机制实现数据的时时传递。详细的系统操作流程如下图所示：
三、结论
定位技术是无线网络技术在室内应用的主要支撑技术。该技术是对GPS技术的扩展和补充，在医疗救助、设备监测、物流跟踪、火灾报警等领域具有非常迫切的市场需求，因此具有广阔的市场应用前景。本文主要根据最近几年来的室内定位研究成果，对室内定位系统的设计思路和定位技术的模型分析进行了总结和归纳，对定位系统的硬件结构、定位算法和基本定位流程进行了研究和设计。由于室内楼层之间存在很多不确定的因素，而且定位数据的传输较其他环境也具有更大的复杂性，所以，对室内定位系统的研究必然会成为未来定位技术的研究热点。未来的室内定位技术要以高定位精度、强适应性和对环境、时间波动的适用性为前提，并能够进行快捷的、方便的部署，这对系统的推广和应用十分重要。
参 考 文 献
[1]翁宁龙，刘冉，吴子章.室内与室外定位技术研究[J].数字应用与技术.2011，11（5）：179.
[2]王小建，薛政，曾宇鹏.无基础设施WIFI室内定位算法设计[J].通信学报，2012，33（11）：240-243.
无线传感器网络节点自身定位算法 篇4
随着无线通信、微芯片制造等技术的进步,无线传感器网络的研究应用在许多方面都取得了重大进展,其发展受到了越来越多的网络研究者的关注。美国橡树岭国家实验室的研究人员甚至提出了“网络就是传感器(Network is Sensor)”的论断。2006年初我国发布的《国家中长期科学与技术发展规划纲要》(2006-2020年)为信息技术确定了三个前沿方向。其中有两个与WSN研究直接相关,即智能感知技术和自组织网络技术。目前一些重大项目的应用也推动了WSN的发展:北京奥运会、上海世博会的电子门票、食品安全追溯、安全防伪等遍布WSN足迹;中科院的“基于WSN的冰雪环境连续测量系统”将南极表面数据与遥感卫星测试数据相结合,对南极开展“天地一体”的监测研究;在医院和老年公寓的特殊人群、特殊药品、血液和特殊医疗设备的管理中WSN都扮演了不可缺少的角色。
WSN的应用前景广阔,对于大多数应用,不知道传感器位置而获得的数据是没有意义的。因此传感器节点必须明确自身位置才能说明“在什么区域发生的特定事件”,从而实现对目标的定位和追踪。从1992年AT&T开发出室内定位系统至今,研究者们一直致力于这一领域的研究,开发出多种系统,但不同的系统和算法只支持不同的应用,至今没有一种算法对所有的WSN定位是完全适应的。
2 计算节点位置的基本方法
在本文中,将WSN中需要定位的节点称为未知节点(unknown node);而坐标位置已知,并能协助未知节点定位的称为信标节点(anchor node);两节点间的跳段总数称为两节点间的跳数(hop count);两节点间的各跳段距离之和称为两节点间的跳段距离(hop distance)。传感器节点定位的过程中,未知节点在获得对于邻近信标节点的距离或者相对角度后,通常使用下列方法计算自己的位置。
2.1 三边测量法
其几何意义是:当得到未知节点到一个信标节点的距离时,就可以确定此未知节点在以此信标节点为圆心、以距离为半径的圆上;得到未知节点到3个信标节点的距离时,3个圆的交点就是未知节点的位置。若已知A、B、C三个信标节点的坐标分别为(xa,ya)(xb,yb)(xc,yc),以及它们到未知节点D的距离分别为da、db、dc,假设D点坐标为(x,y)那么存在下面公式 :
undefined
由式子可以得到节点D的坐标为:
undefined
2.2 三角测量法
其理论依据是:已知L1、L2、L3三个信标节点的坐标分别为(xa,ya)(xb,yb)(xc,yc),节点A相对于节点L1,L2,L3角度分别为:∠L1AL2, ∠L1AL3, ∠L2AL3,假设节点A的坐标为(x,y),对于节点L1,L3和∠L1AL3,如果弧段L1L3在△L1L2L3内,那么能够唯一确定一个圆,设圆心为O1 (xo1,yo1),半径为r1,那么α=∠L1O1L3=(2π-2∠L1AL3)并且存在下列公式:
undefined
由上式能够确定圆心O1点的坐标和半径r1。同理对L1,L2,∠L1AL2和L2,L3,∠L2AL3分别确定相应的圆心O2(x2,y2)、半径r2、圆心O3 (x3,y3)、半径r3。最后利用三边测量法,由点A(x,y),O1 (xo1,yo1), O2 (xo2,yo2), O3(xo3,yo3)确定未知节点D点坐标。
2.3 极大似然估计法
其理论依据是:已知1,2,3……等n个信标节点的坐标分别为(x1,y1), (x2,y2), (x3,y3)……(xn,yn),它们到未知节点D的距离分别为d1 ,d2 ,d3 ,……dn ,假设节点D的坐标为(x,y)。那么存在下列公式:从第一个方程开始分别减去最后一个方程,得
undefined
将线形方程组表示方式为:AX=b,其中:
undefined
undefined
。使用标准的最小均方差估计方法可以得到节点D的坐标为:undefined
3 典型的基于距离(range-based)的定位系统与算法
3.1 基于TOA的定位 [1]
算法中,已知信号的传播速度,根据信号的传播时间来计算节点间的距离,然后利用已有算法计算出来节点的位置。假设两个节点间时间同步,发送信号的模块在发送信号的同时,发送模块通过同步消息通知接收节点,根据信号的传播时间和速度计算发送节点和接收节点之间的距离。节点在计算出多个邻近信标节点的距离后,利用三边测量法或极大似然估计法计算自身的位置。 基于TOA 的定位算法精度高,但须保持节点间的时间同步,对传感器节点硬件和功耗提出较高的要求,不建议使用。
3.2 基于TDOA的定位[2]
算法中,发射节点同时发射两种不同的传播速度的信号,接收节点根据两种信号到达的时间差以及已知这两种信号的传播速度,计算两个节点之间的距离,再通过已有的基本定位算法计算节点的位置。发射节点同时发射无线射频信号和超声波信号。接收节点记录两种信号到达的时间T1、T2 ,已知无线电射频信号和超声波的传播速度为c1、c2,那么两点之间的距离为(T2-T1)×S,其中undefined。 由于TDOA不是采用到达的绝对时间来确定节点的位置,降低了时间同步的要求。但仍需要较精确的计时功能,而这对于无线传感器网络的分布密集和无线通信范围小的特点实现起来难度较大。
3.3 基于信号强度RSSI测量法[3]
算法中已知发射功率,在接收节点测量接收功率,计算传播损耗,使用理论或经验的信号传播模型将传播损耗转化为距离。在自由空间中,距发射机d 处的天线接收到的信号强度由下面的公式给出Pr(d)=PtGtGrλ2/(4π)2d2L其中,Pt为发射机功率;Pr(d )是在距离d 处的接收功率; Gt、Gr分别是发射天线和接收天线的增益;L为与传播无关的系统损耗因子;λ是波长, d 是距离,单位为米。通过测量接收信号的强度,再利用上式就能计算出收发节点间的大概距离。然后采用三边测量法或最大似然估计法计算出未知节点的位置。 RSSI借助的硬件设备少,对于复杂环境的适应能力弱,多径反射传播、非视距、天线方向都对其产生影响。但RSSI可作为其它测距方法的辅助手段而采用。随着信号强度的加大,可以逐步减少噪声的影响。
基于距离的定位能够实现精确的定位,但往往对无线传感器节点的定位器件要求高。出于硬件的成本、能耗等考虑,提出了距离无关的定位技术。距离无关的定位技术无需测量节点间的绝对距离或方位,一般通过网络的连通度来确定节点的坐标。
4 典型的无需测距(range-free based)的定位系统及算法
4.1 质心算法[4]
多边形的几何中心称为质心,多边形顶点坐标的平均值就是质心接点的坐标。利用这一理论计算质心坐标。若多边形ABCD的顶点坐标分别为A(x1 ,y1)B(x2,y2)C(x3,y3)D(x4,y4),则其质心坐标undefined。在质心算法中,利用信标节点周期性地向邻近节点广播信标分组,信标分组包含信标节点的标识号和位置信息。当未知节点收到来自不用信标节点的标识分组的数量超过某一个门限k或接收一定时间后,就确定自身位置为信标节点所组成的多边形的质心:undefined,即分组的信标节点坐标。该算法完全基于网络连通性,无需锚节点和未知节点间协调,但需要较高的锚节点密度。
4.2 SPA (self-positioning algorithm)相对定位算法[5]
算法在网络节点部署后,每个节点都开始运行一个随机定时器。与邻居节点相比,节点i 的定时器最早到期,则i 成为一个主节点(master),并向邻居节点广播一个消息,所有接收到该消息的邻居节点终止自己的定时器并成为一个从节点(slave),这些节点形成一个域。然后分别以这些主节点为原点使用与SPA 类似的方法建立各个域的局部坐标系统。然后以主节点ID 较小的局部坐标系统为参考,相邻域进行坐标转换,逐步建立全局坐标系统。因为通信量是随着域的数量而增长的,所以该算法的通信开销与网络中节点数量呈线性比,更适合于大规模网络的部署。
4.3 凸规划定位算法[6]
算法将节点间点到点的通信连接视为节点位置的几何约束,把整个网络模型化为一个凸集,从而将节点定位问题转化为凸约束优化问题,然后使用半定规划和线性规划方法得到一个全局优化的解决方案,确定节点位置。如图1所示,根据未知节点与信标节点之间的通信连接和节点无线射程,计算出未知节点可能存在的区域(图中阴影部分),然后以矩形的质心作为未知节点的位置。 凸规划定位中为了高效工作,锚节点需要被部署在网络的边缘,否则外围节点的位置估算会向网络中心偏移。
4.4 DV-Hop 定位算法[7]
算法由3步组成。首先使用典型的距离矢量交换协议,使网络中所有节点获得距信标节点的跳数。第2步,在获得其他信标节点位置和相隔跳距之后,信标节点计算网络平均每跳距离,然后将其作为一个校正值广播至网络中。当接收到校正值之后,节点根据跳数计算与信标节点之间的距离。利用下式可以估算平均每跳的实际距离:
undefined,其中,(xi,yi)(xj,yj)是信标节点的i,j的坐标,hi是信标节点i与j之间的跳段数。当未知节点获得与3 个或更多信标节点的距离时,则在第3步执行三边测量定位。DV-Hop算法仅在各向同性的密集网络中,校正值才能合理地估算平均每跳距离。
4.5 Euclidean 定位算法[8]
算法给出了计算与信标节点相隔两跳的未知节点位置的方法。假设节点拥有RSSI测距能力,如图2所示,已知未知节点B,C在信标节点L的无线射程内,BC距离已知或通过RSSI 测量获得;节点A与B,C相邻。对于四边形ABCL,所有边长和一条对角线BC已知,根据三角形的性质可以计算出AL 的长度(节点A 与L的距离)。使用这种方法,当未知节点获得与3个或更多信标节点之间的距离后定位自身。 当节点A的正确位置确定后,那么,根据图的实际关系,就可以得到三角形ACB、三角形BCL、三角形ACL。这样通过计算,就可以得到对角线AL了,然后经过运算就可以得到节点A的位置信息。
4.6 MDS-MAP定位算法[9]
它是一种集中式定位算法,可在range-free 和range-based 两种情况下运行,并可根据情况实现相对定位和绝对定位。MDS-MAP 算法由3个步骤组成:
(1)首先从全局角度生成网络拓扑连通图,并为图中每条边赋予距离值。当节点具有测距能力时,该值就是测距结果。当仅拥有连通性信息时,所有边赋值为1。然后使用最短路径算法生成节点间距矩阵。
(2)对节点间距矩阵应用MDS技术,生成整个网络的2维或3维相对坐标系统。
(3)当拥有足够的信标节点时(2 维最少3个,3维最少4个),将相对坐标系统转化为绝对坐标系统。
4.7 APIT算法(approximate point-in-triangulation test)近似三角形内点测试法[10]
在APIT算法中,一个未知节点从它所有能够与之通信的信标节点中选择3个节点,测试它自身是在这3个信标节点所组成的三角形内部还是在其外部;然后再选择另外3个信标节点进行同样的测试,直到穷尽所有的组合。未知节点将包含自己的所有三角形的相交区域的质心作为自己的估计位置。PIT测试如图3原理为:假如存在一个方向,沿着这个方向M点会同时远离或者同时接近A、B、C 3个点,那么M位于△ABC外;否则,M位于△ABC内。
在静态网络中,M点固定,不能朝着不同的方向移动,此时无法执行PIT测试,为此定义APIT测试(Approximate PIT)如图4:在无线传感器网络中,邻居节点间互相交换信息,仿效PIT测试的节点移动。图4左图中,节点M通过与邻居节点1交换信息,得知自身如果运动至节点1,将远离信标节点B和C,但会接近信标节点A,与邻居节点2、3、4的通信和判断过程类似,最终确定自身位于△ABC内,而图4的右图中,节点M可知假如自身运动至邻居节点2处,将同时远离信标节点A、B、C,故判断自身不在△ABC中。当节点M比较接近△ABC的一条边,或者M周围的邻居节点分布不均匀时,APIT的判断可能会发生错误,当未知节点密度较大时,APIT判断发生错误的概率较小。
在这些算法中,由于中心节点需要频繁的与周围节点进行通信,其节点能耗要比其他部件要大的多,而每个节点能量有限,因此不能将大量的通信和计算固定于某些节点,否则就造成中心节点能量耗尽,使网络节点不均衡,所以尽量采用分布式的节点定位算法。质心法、DV-Hop法、APIT法等是完全分布式的,需要通信量少、计算简单且具有良好的扩展性。无线传感器网络的自身定位算法的性能对于其可用性有直接的影响,下表给出了不基于测距的定位算法的一些基本算法评价的比较。
5 总结与展望
节点定位是无线传感器网络的一项关键技术,无需测距定位算法将是节点定位算法的主流。国内外学者对WSN节点自身定位的研究获得了丰富的成果,提出了许多定位解决方案和算法,但仅是初步研究还有一些方向值得注意:定位算法性能评价的模型化和量化;网络中移动节点的定位算法的自适应问题及对现有定位算法的优势融合,提出性能更佳的定位算法等。
参考文献
[1] Girod L, Bychovskiy V, et al. Locating tiny sensors in time and space: a case study [A ].IEEE, 2002.
[2]HarterA,HopperA,et al.The anatomy of a context aware ap-plication[A].ACM Press,1999.
[3] Girod L, Estrin D. Robust range estimation using acoustic and multimodal sensing [A ].IEEE, 2001.
[4] Bulusu N, Heidemann J. GPS less low cost outdoor localization for very small devices[J ].IEEE Personal Communications, 2000, 7 (5) .
[5]Capkun S,Hamdi M.GPS-Free positioning in mobile ad-hoc networks.Cluster Computing,2002,5(2):157?167.
[6] He T, Huang C D, et al. Range free localization schemes in large scale sensor networks [A ].Association for Computing Machinery, 2003.
[7] Niculescu D, Nath B. Ad hoc positioning system (APS) using AoA[A ].IEEE, 2003.
[8] NICOLESCU D , NATH B. Ad Hoc Positioning Systems ( APS )[A ].IEEE Communications Society, 2001.
[9]SHANG Y,RUMLW,et al.Localization from mere connectiv-ity[A].ACM Press,2003,6.
无线定位算法 篇5
为切实做好井下无线通讯、人员定位考勤两大系统的管理工作，充分发挥其功能，特做如下规定，望各单位严格执行。
一、井下无线通讯
1、做好小灵通的使用维护工作，如果因使用不当造成小灵通损坏的，按每部800元进行考核。
2、机关部室及区队值班、跟班人员必须严格按编定的号码使用手机并携带，区队值班人员在矿值班时须随身携带，出现调度台调度不接现象，每次考核相关责任人50元。
3、严禁人为故意损坏通讯系统在井上、下安装的相关设备，一经发现，按开除矿籍处理相关责任人。
4、我公司小灵通与调度电话实现了互联互通，小灵通、调度电话之间可以直接拨号。小灵通调度指挥平台号码为6998、6999。
二、井下人员定位考勤系统
1、做好人员定位卡的随身携带及使用，如因使用不当损坏，按每卡100元考核相关责任人。
2、系统投入运行后，人员定位卡将作为今后下井人员的井下考勤、个人信息采集的主要原件，如有丢失应及时到主管单位进行补卡，在新卡未到而需要下井时，必须由单位主要负责人签字并报生产班子主要领导签字后，方可对其下井进行考勤，否则不予考勤。
3、各单位员工必须严格遵守劳动纪律，按照公司规定的时间上下井，下井必须携带人员定位发射器，凡下井时间不足人员一律取消当日出勤，只有下井陪检人员除外，但必须由调度室开具陪检单证明。个人下井时间按月进行统计，月底按下井总时间除以公司规定的每天下井时间，得出实际下井天数，公司根据实际下井天数支付员工下井费，下井陪检人员必须根据调度室开具的陪检单考勤，下井天数为实际下井天数与陪检天数之和。
4、各单位需及时将本单位人员工种及班次变动情况汇报主管单位，由主管单位统一对考勤时间进行修改。若因汇报不及时影响员工考勤的，由各单位自行承担责任。
5、严禁将人员定位发射器交由他人携带下井，一经发现，给予双方当事人各1000元罚款，挂罚单位正职领导100元。
6、严禁人为故意损坏井下人员定位考勤系统系统在井上、下安装的相关设备，一经发现，按开除矿籍处理相关责任人。
无线定位算法 篇6
关键词：非视距传播；信号到达时间；最大似然估计
中图分类号：TN929文献标识码：A文章编号：1009-3044(2007)15-30791-02
A TOA-based Location Algorithm in NLOS Environment and the Comparison of Algorithms
FANG Peng,HU Zong-fu
(Tong Ji University,Communication and Information System,Shanghai 200092,China)
Abstract:An effective TOA algorithm which includes the influence of non-line-of sight(NLOS) Propagation when the Base stations are distributed arbitrarily is proposed. The main idea is that when identifying the NLOS error BS by the weight of each BS, the NLOS error is referred to the variable, and the nonlinear equation can be transformed into a maximum-likelihood(ML) linear estimation. This algorithm is simple and has higher accuracy. Then, other algorithms are compared with this.
Key words:non-line-of-sight propagation;time of arrival;maximum likelihood(ML) estimation
1 引言
在美国，移动运营商必须依照E-911标准为移动站提供比较精确的定位服务[1]。基于到达时间（TOA），到达时间差（TDOA）和信号场强的定位技术，经常被用于获取移动台与基站之间的距离信息。应用这些方法的前提是接收到的信号以视距传播。当存在NLOS误差时，将会出现比较大的定位误差。
LOS路径是连接发信机和接收机的直线路径，当不存在LOS路径，信号通过衍射反射等形式传播到达接收机。NLOS误差定义为多余的传播距离。因此NLOS误差都是正值，依据传播环境变化范围可达1300米[2]。
为了消除非视距误差对定位精度的严重影响，非视距鉴别技术与改进技术应运而生。文献[3]基于基站的历史统计信息，应用假设检验的方法鉴别存在非视距的基站并通过图像法修正NLOS数据为视距数据。在文献[4]中，一种剩余量加权算法被提出，这种算法不需要关于时间的统计数据和基站的历史信息，仅仅要求测量数据要多于定位最少需要的数据。还有一种算法被提出[5]，把残差作为权值修改初始估计值，它的特点是不需要统计信息和历史信息，并且仅需要三个测量数据即可。
本文分析在TOA移动定位环境中NLOS误差并提出一种算法，该算法能够鉴别出NLOS误差并且较好的修改NLOS误差。这种算法能够推广到TDOA、AOA和混合移动定位中。第二部分鉴别出NLOS误差和相应的基站，前提是仅存在一个非视距的基站，并且不是服务基站。第三部分修正NLOS误差，把它当成一个未知量，建立误差方程求解。算法比较放在第四部分。最后给出总结。
2 NLOS鉴别
假设在移动台周围有N个可用的基站,关于测量误差和非视距误差的方程如下：
Cti=Di+ni+ei (i=1，2，…，N)(1)
ti为信号从移动台到第i个基站的TOA测量时间；Di为移动台到第i个基站的真实距离；ni和ei分别为TOA测量误差和NLOS误差；C为光速。
再定义TOA剩余量：
移动台的初始坐标；Sk为基站的集合。
算法描述如下：
(1)基站集合大小为M(3 ≤ M＜N)，对于每一个M值，有K(从N中取M共有K种取法)个TOA测量值集合。用Sk(k=1,2,…,K)表示第K个基站集合。
(2)对于每一个基站集合Sk，用参考坐标( )计算相应的TOA剩余量Rk，把它作为基站集合Sk的权值。
(3)计算出所有TOA剩余量后，通过累加基站所属的基站集合的权值得出每一个基站的总权值。
(4)找到权值最大的基站，就是我们要找的基站。
算法解释如下：
例如N=5，
当M=3，K=10
S1=(1,2,3),S2=(1,2,4),S3=(1,2,5),S4=(1,3,4),S5(1,3,5),S6=(1,4,5),S7=(2,3,4),S8=(2,3,5),S9=(2,4,5),S10=(3,4,5)
当M=4,K=5
S1=(1,2,3,4),S2=(1,2,3,5),S3=(1,3,4,5),S4=(2,3,4,5),S5(1,2,4,5)
初始位置( 的选择在NLOS BS识别中是很重要的。理想情况下，应该使用移动台的真实坐标，但是它是未知的。可通过最小二乘法求出估计坐标，或者对于每个Sk，求出中间位置估计。
在M=3的情况下：
对于基站1，它的残差和为S1+S2+S3+S4+S5+S6
对于基站3，它的残差和为S1+S4+S5+S7+S8+S10
在M=5的情况下：
对于基站1，它的残差和为S1+S2+S3+S5
对于基站3，它的残差和为S1+S2+S3+S4
3 NLOS误差修正
NLOS误差依赖于信号传播环境，随着时间而不断变化。但是，在一个很短的时间内，NLOS误差可看作常值。因此可当作未知数求解。假设第N个基站存在非视距误差。
由Cti=Di+ni(i=1,2,…,N-1)和CtN=DN+nN+eN列出距离方程
Ri2=(xi-x)2+(yi-y)2=Ki-2xix-2yiy+x2+y2 i=1,2,…,M (3)
令r= x2+y2得到关于Za=[x,y,r,eN]T的矢量误差f=h-GaZa，其中
把ri=ri0+cni，代入(4) 误差矢量可近似化简为：
f=2cBn，B=diag{r10, r20,…, rN0} (5)
误差矢量f的协方差矩阵：
F=E[ffT]=4c2BQB (6)
Q为噪声估计的协方差矩阵，为已知量，可参考文献[7]。
对公式(4)用最大似然估计得到，
Za=arg min{(h-GaZa)TF-1(h-GaZa)}=(GaT F-1Ga)-1GaTF-1h (7)
当移动台离基站很远时，B可近似为diag{r0,r0,…,r0}那么F=4c2r02Q，因此公式(7)简化为：
Za= (GaTQ-1Ga)-1GaTQ-1h(8)
如果移动台离服务基站很近，我们首先利用公式(8)获取一初始值得到B，最后的定位结果可从公式(7)获得。虽然可以对公式(7)进行多次叠代，但仿真表明叠代一次就能得到精确的结果。
下面我们使用扰动的方法求Za的协方差矩阵。根据公式Ga=Ga0+△Ga，h=h0+△h,Za=Za0+△Za，Ga0*Za0=h0，误差矢量可重写为：
f=△h-△GaZa0(9)
保留线性扰动项，利用公式(5)和(7)，得到
Cov(Za)=E[△Za△ZaT]= (Ga0TF-1Ga0)-1(10)
4 算法比较
在文献[3]中，Wylie提出了一种NLOS环境下鉴别NLOS误差并通过图像法改正的方法。首先测量信号到达基站的传播时间(TOA)，在假设检验中，对每一个基站BS在不同时刻的距离测量值平滑处理，从而获取测量距离标准差，若远大于LOS环境下的标准方差，则判断存在非视距误差。我们还可以用残差分析秩检验的判断方法进一步确认NLOS误差。基于在LOS和NLOS环境下，平滑值与测量值的最大正差值是一致的原则，通过图像法修改测量数据。Wylie算法与本算法都能鉴别并修改NLOS误差，但是本算法不需要知道LOS环境下测量数据的标准方差和最大测量误差偏移量，因此不局限于低速的移动环境。
文献[4]提出了一种被称作Rwgh的算法。它首先对测量数据分成若干集合，对于每一个数据集合，应用最小二乘法算出初始位置，从而计算出相应的权值，用此权值权乘初始位置，最终得到修改后的估计位置。它的主要优点是不需判断是否存在NLOS误差，直接对数据修改即可。在LOS-NLOS环境下不需要关于时间的统计数据或者先验信息。仅仅假设距离测量值数量远大于所需的最小数量。本算法与Rwgh算法，在鉴别能力上相似，但是对误差的修正方面明显本算法较好。
文献[5]不需要NLOS误差的统计数据，也不像文献[5]需要大量的测量数据，它仅需要三个基站测量数据即可。思路是运用几何学和三角学的分析方法找到关于测量值与真实值比值的约束等式和最小边界，应用边界最佳算法解算出最佳估计[6]。
图1是本算法的仿真结果。其中四个基站分别位于(0 0)、(0 1)、(1 0)、(1 1)，MS位于(0.4 0.6)，对于每个非视距误差，重复计算100次得到估计值和真实值之间的均方误差。由图可见，定位误差绝大部分小于3*10-4，即若基站间的距离为3公里，定位误差小于1米。另外，从仿真数据看出，从非线性方程组解出的非视距误差与真实误差相差无几。
图1 仿真结果
5 结论
我们介绍了在宽带CDMA蜂窝系统中利用TOA测量值鉴别NLOS误差的算法，并运用最大似然估计对误差进行修改。NLOS鉴别基于TOA残差计算。我们把所有可用的基站分成不同大小的集合，对每一个集合利用参考位置获得残差，累加残差和最大的基站存在NLOS误差。把此误差当做未知数放在非线性方程组中求解。通过算法比较及算法仿真看出此算法的精度还是令人满意的。
参考文献：
[1]FCC.Revision of the Commissions Rules to Insure Compatibility with Enhanced 911 Emergency Calling Systems[Z].1996.
[2]M I Silventoinen,T Rantalainen.Mobile station emergency locating in gsm[C].IEEE International Conference on Personal Communication,1996.
[3]Marilynn P Wylie,J Holtzman.The non-line of sight problem in mobile location estimation[C].in Proc IEEE International Conference on Universal Personal Communications,1996(2):827-831.
[4]PI Chun-chen.A Non-Line-of-Sight Error Mitigation Algorithm in Location Estimation[M].
[5]S Venkatraman,J Caffery,Jr.Location Using LOS Range Estimation in NLOS Environments[M].
[6]P E Gill,W Murray,M H Wright.Practical Optimization[M].Boston,MA,USA:Academic Press,1981.
[7]W R Hahn.Optimum processing for delay-vector estimation in passive signal arrays[J].IEEE Trans,Inform.
无线传感器网络质心定位算法研究 篇7
无线传感器网络是现代传感器技术、微机电系统、通信技术、嵌入式计算技术和分布式信息处理技术等综合交叉起来的一个研究领域,是多学科交叉的新兴研究热点[1]。位置信息在无线传感器网络中承担着非常重要的作用,对于无线传感器网络得到的感知数据来说,如果没有相应的位置信息,往往是没有任何意义的[2]。根据定位过程中是否需要通过物理手段实际测量节点间的距离或角度,可把传感器网络中的定位算法分为基于测距的定位算法和无需测距的定位算法[3]。相比于基于测距的定位算法,无需测距的定位算法虽然没有较高的定位精度,但其成本和能耗开销较小,并且不需要额外的硬件支持,因此更加适用于大规模无线传感器网络中而备受关注[4]。
质心(Centroid)算法是作为一种很重要的无需测距定位算法,以其结构简单、易于操作等特点而广泛应用于室外定位应用中,但是该算法定位精度较低,针对这一缺陷,文献[5,6,7,8]对其进行了改进:文献[5]通过粒子群算法对质心算法的定位结果进行迭代求精从而提高了定位精度;文献[6]利用可变惯性权重的方法对质心算法进行了改进,通过对所接收到的所有锚节点信息进行加权处理从而减小了定位误差;文献[7]将质心算法与DV-Hop算法结合进而对其定位性能进行了改进;文献[8]利用未知节点接收到的锚节点所发送信号功率的强度对质心算法加以改进。
本文在介绍质心算法原理的基础上,通过对影响其定位精度及定位率的几个重要参数,包括节点个数、锚节点个数以及节点通信半径进行详细的仿真分析,并通过仿真对固定监测区域内的参数设置进行了优化。仿真结果表明,未知节点的平均邻锚节点个数对质心算法的定位精度起主导作用,锚节点单位时间内所发送的信息包的数量S及阈值CM对定位精度及定位时间起调节作用,而网络的平均连通度是确保质心算法能够正常运行的前提,其值的改变并不能影响定位精度;同时,考虑到算法的能量消耗,在一定网络连通度的基础上,在固定监测区域内通过设置较优的参数可以有效的提高定位精度以及定位率。
1 Centroid定位算法描述
Centroid定位算法最初是由南加州大学Nirupama Bulusu等人提出的一种无需测距的室外定位算法[9]。具体的定位过程为:锚节点每隔一段时间T发送一个自身的位置信息,在一个时间段t内,假设锚节点发送的位置信息数目为S,未知节点接收到的来自锚节点的位置信息数目为Nm,则Nm/S表示未知节点和这个锚节点的连通度。如果N/S大于预先设置的一个阈值CM,那么就认为未知节点和这个锚节点连通。当未知节点侦听t时段之后,把所有与自己连通的锚节点组成的多边质心作为自己的估计位置,计算公式如下:
式(2)中(xi,yi)表示未知节点所接收到的锚节点坐标,kr为所接收到锚节点坐标信息的个数,(x , y)为该未知节点坐标。
从上述质心算法的定位过程可知,该算法只是对未知节点坐标进行粗略的估计,必然存在较大的误差,另外节点个数、锚节点个数、节点的通信半径以及S与CM值的不同也可能对算法的定位性能产生一定影响。为了验证这一结论,利用Matlab 2010a分别对上述不同参数设置下的质心算法定位性能进行仿真,通过比较找出各个参数与定位性能之间的关系。
2 定位性能仿真分析
为了全面系统的分析质心算法的定位性能,假设节点随机均匀的部署在边长为100 m的方形平面监测区域内,并对其评价指标作以下设定。
(1)定位精度
这是定位算法最主要的性能指标,它一般用位置节点的估计位置和真实位置的距离偏差和节点的通信半径的百分比表示[10]。本文通过计算基于k次仿真实验结果统计的归一化平均定位误差作为评价指标,在不做特殊说明时,k=100,具体计算公式如下:
式(3)中k为实验次数,R为节点的通信半径,nc为可定位的节点个数,(xi,yi)、 (xi′,yi′)分别为未知节点的真实坐标和估计坐标。
(2)定位率
即可定位的节点个数与未知节点个数的比值,若定位率较低,网络则无法正常工作。
(3)算法的能量消耗
本文主要通过计算算法的运行时间来等效算法的能量消耗。
2.1 节点个数对定位性能的影响
节点个数是指在无线传感器网络中未知节点与锚节点个数的总和,其中锚节点坐标已知。
图1和图2给出了不同节点个数基于100次仿真实验的统计结果。图1为通信半径R=22 m、S=20、CM=0.9时锚节点个数分别为5、8、12和20的情况下随节点个数变化的定位情况。从图1(a)中可以看出,在锚节点个数固定不变时,随着节点个数的增多,定位误差基本保持不变,但随着锚节点个数的增多,定位误差才逐步减小。相比于5、8和12个锚节点的情况,20个锚节点的定位误差分别平均减小了14.83%、11.35% 和7.19%。从图1(b)中可以看出,随着节点个数的增多,算法的运行时间在逐步增加,在节点个数大于200时,平均运行时间上升的幅度增大,同时,锚节点个数的不同对算法的运行时间在节点个数较少时(小于250)基本没有影响影响, 但在节点个数较大时, 存在略微差异, 在500个节点时5个锚节点时的运行时间分别 比 8、12、20个锚节点时多了0.342 1 s、0.27 s和0.338 4 s。
邻锚节点个数是指未知节点通信范围内的平均锚节点个数。从图1(c)和图1(d)中可以看到,在随着节点个数增多的过程中,网络平均连通度也随之增加,而邻锚节点个数与平均定位率在锚节点个数不变时,基本保持不变。
图2给出了锚节点比例(占节点个数的比值)为10%、S=20、CM=0.9时通信半径R分别为15 m、20 m、25 m和30 m的情况下随节点个数变化的定位情况。从图2(a)中可以看出,随着节点个数的增多,在通信半径不变时,定位误差逐步减小,另外,节点的通信半径较大时,定位误差减小的幅度较大,相比于通信半径为15 m、20 m、25 m时的情况,通信半径为30 m时的定位误差平均减小了14.15%、8.1%和3.29%。从图2(b)中可以看到,在通信半径不变时,网络平均连通度随节点个数的增加而呈线性递增的趋势。
从图2(c)可知,在通信半径一定时,邻锚节点个数随着节点个数的增多也在逐步增加,另外,从图2(d)中可以看到,在节点个数逐步增加的过程中,算法的平均定位率也在逐渐增加并趋于稳定,但通信半径较小时随节点个数变化的幅度较大。从图1和图2中可以发现,邻锚节点个数对定位误差及定位率具有较大的影响,而网络的平均连通度对定位精度则没有较大影响,另外,节点个数是影响定位时间的主要因素。
2.2 锚节点数量对定位性能的影响
为了进一步验证邻锚节点个数对定位性能的影响,图3和图4分别给出了不同锚节点个数及锚节点比例下的定位结果。其中图3为节点个数为100、S=20、CM=0.9时通信半径R分别为15 m、22 m、24 m和30 m的情况下随锚节点个数变化的定位情况。
从图3(a)、图3(b)和图3(c)中可知,在通信半径保持不变时,定位误差随着锚节点个数增多而逐渐减小,而邻锚节点个数随之逐渐增加,而网络的平均连通度则基本保持不变,在通信半径增大时,相同锚节点个数的基础上,平均定位误差减小,邻锚节点个数及网络平均连通度均随之增大。这就说明了通信半径对网络平均连通度有较大影响;而在R=15时,网络连通度平均为6.137 3,但定位误差可以减小至40.68%,说明了邻锚节点个数对定位误差起主要作用,而网络的平均连通度则对其影响较小。从图3(d)中可以看出,在锚节点个数增加的过程中,平均定位率也逐步增加,另外,在锚节点个数为3左右时,定位率均能达到约95%。
图4给出了通信半径R=20 m、S=20、CM=0.9时节点个数分别为50、100、150和200的情况下随锚节点比例变化的定位情况。由图4可知,在节点个数一定时,随着锚节点比例的增加,定位误差逐步减小,邻锚节点个数呈线性递增的趋势,平均运行时间基本保持不变,而定位率也随之增加并趋于稳定。由图4(a)中可以看出,在随锚节点比例增加时,节点个数较多的定位误差减小的幅度较大,在200个节点时,相比于4%的锚节点,50%的锚节点平均定位误差减小了31.7%。
2.3 信息包数目S及阈值CM对定位性能的影响
在质心算法中,锚节点单位时间内发送信息包的数目S及阈值CM是两个重要的控制参数,为了分析其对定位性能的影响,图5给出了不同S及CM设置下的定位性能。
其中图5(a)与图5(b)给出了在通信半径为25 m、锚节点比例为10%、CM=0.9时节点个数分别为50、100、150和200条件下的定位结果。由图5(a)和图5(b)可知,随着S的增加,在节点个数不变时,定位误差与定位率均随之下降,同时,在节点个数较小时,下降的幅度较大,分别约为21.22%和17.55%,而在节点个数较大时,S的改变对定位误差及定位率的影响较小,同时可以发现,相同条件下,若要保证较低的定位误差,则会牺牲一部分定位率。
图5(c)和图5(d)给出了在节点个数为100,锚节点比例为10%且S=10时通信半径分别为10 m、20 m、30 m和40 m时随CM值变化的定位性能。由图上可知,在通信半径一定时,阈值较大的定位误差明显小于阈值较小的情况,同时,较大的阈值会减小算法的定位率,但影响程度相比于S较小。
2.4 参数优化后的定位性能
从上述的仿真结果分析可知,邻锚节点个数对定位误差及定位率的影响起主导作用,节点个数是直接影响算法运行时间的参数,另外该参数与通信半径直接影响网络的平均连通度,同时,S与CM对定位误差及定位率起调节作用,通过设置,可以在牺牲一定定位误差的基础上,确保算法较高的定位率。另一方面,在仿真分析过程中发现,在本实验的监测区域内,存在较优的参数设置,即邻锚节点个数为3时能够有效的提高定位精度及定位率,考虑到算法的平均运行时间及网络成本,锚节点设置为10%的节点个数,则100×100 m2监测区域内较优的参数设置如下:
根据表1的参数设置,在1 000次仿真的基础上,对四种参数设置下的定位算法进行了仿真,图6给出了这四种参数设置下的误差概率分布。
由图6可知,通过设置最优参数,定位误差集中分布在35%到45%之间。其中,图6(a)为120个节点时所设置较优参数后的概率分布,从图中可以看出最小定位误差为27.41%,最大定位误差为60.47%。图6(b)为150个节点时所设置较优参数后的概率分布,其中最小定位误差为28.20%,最大定位误差为56.88%;图6(c)为180个节点时所设置较优参数后的概率分布,最小定位误差为30.15%,最大定位误差为54.96%;图6(d)为200个节点时所设置较优参数后的概率分布,从图中可以看出最小定位误差为28.33%,最大定位误差为55.41%。从图6可以看出,通过设置较优的参数,定位误差及定位率均能达到较为理想的状态。
4 结论
本文针对传统质心算法中几个重要参数设置不同时存在误差及定位率等定位性能差异较大的问题,详细的对节点个数、锚节点数量、通信半径以及锚节点单位时间内发送的信息包数目S与阈值CM几个参数在定位过程中进行了仿真。通过仿真结果分析发现,邻锚节点个数对定位率及定位误差的影响起主要作用,S与CM对其起调节作用且其值在变化过程中不能既降低定位误差又提高定位率,节点个数直接影响算法的运行时间,同时网络平均连通度对定位率及定位误差仅有较小的影响。仿真结果表明,通过设置较优的参数,在固定监测区域内,在确保网络连通的前提下,邻锚节点个数保持在3左右时能够有效的提高定位精度及定位率。
摘要：质心算法是无线传感器网络中一种典型的无需测距定位算法。针对不同节点个数、锚节点个数、锚节点单位时间内发送信息的个数以及阈值对定位性能具有较大影响的问题,系统仿真了在固定监测区域内上述参数与定位误差、定位率以及定位时间的关系。通过仿真结果分析得出未知节点的邻锚节点个数是影响定位率及定位精度的主要因素。另外在确保较高定位率的基础上,在固定监测区域内存在较优的参数设置。仿真结果表明,参数优化后的质心算法有效地提高了定位精度及定位率。
关键词：无线传感器网络,定位,质心算法,参数优化
参考文献
[1] Akyildiz F,Su W,Sankarasubramaniam Y,et al.Wireless sensornetworks:a survey.Computer Networks,2002;38(4):393—442
[2]袁正午,梁均军.基于虚拟力的无线传感器网络多跳定位算法.重庆邮电大学学报(自然科学版),2010;22(1):122—126
[3]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和协议.软件学报,2005;16(5):857—868
[4] Kim S,Ko J G,Yoon J,et al.Multiple-objective metric for placingmultiple base stations in wireless sensor networks.Proc of the 2rd In-ternational Symposium on Wireless Pervasive Computing.New York:IEEE,2007:627—631
[5] Su Xiaoqing,Lei Zhaoming.Improved centroid algorithm localizationfor WSN based on Particle Swarm Optimization.Proc of 2011 FourthInternational Symposium on Computational Intelligence and Design,2011:139—142
[6] Cheng Haiqing,Wang Huakai,Wang Hua.Research on centroid io-calization algorithm that uses modified weight in WSN.Proc of Net-work Computing and Information Security,May 2011;(2):287—291
[7]王天阳.一种距离无关的无线传感器网络综合定位算法.吉林:吉林大学,2010
[8] Wang Jun,Urriza P,Han Yuxing,et al.Weighted Centroid localiza-tion algorithm:theoretical analysis and distributed implementation.Wireless Communications,2011;10(10):3403—3413
[9] Bulusu N,Heidemann J,Estrin D.GPS-less low-cost outdoor locali-zation for very small devices.IEEE Personal Communications,2000;7(5):28—34
无线定位算法 篇8
无线传感器网络(WSN)是指由大量成本低廉的,具有感知能力、计算能力、无线通信能力的传感器节点组成的网络。在WSN中,位置信息对WSN的监测活动至关重要,事件发生的位置或获取信息的节点位置是传感器节点监测消息中所必须包含的重要信息,因为没有位置信息的监测消息往往毫无意义。因此,确定事件发生的位置或确定获取消息的节点位置是WSN最基本的功能之一,对WSN应用的有效性起着关键的作用[1,2]。
结合WSN的特点和应用,采用一定的机制与算法实现WSN网络中节点的自定位是十分必要的。通常的,WSN自身定位系统节点定位算法可分为基于距离信息(Range-Based)和不基于距离信息(Range-Free)两类[3],前者是根据节点间的距离或角度等信息定位,后者仅仅根据节点间的连通信息实现节点定位。
在WSN中,Range-Free的主要方法有DV-hop、质心、三角形区域覆盖定位(APIT)等算法,这些方法虽然能够在不增加硬件成本的条件下,对节点进行定位计算,但是普遍都存在着定位精度不高或定位条件过于苛刻等不足。而在Range-Based的RSSI(Received Signal Strength Indicator)、TOA(Time of Arrival)、TDOA(Ti me Difference of Arrival)、AOA(Angle of Arrival)等常用方法中,RSSI与Range-Free方法一样存在着定位精度不高的问题,其他几种则都需要额外的硬件提供支持,这将增加节点的尺寸和成本,在大规模应用中很难实现。因此,怎样提高Range-Free方法的精度和不断放宽定位条件是无线传感器网络定位中迫切需要解决的问题[4,6]。
2 遗传算法
遗传算法是一种全局高效的搜索方法,它通过模仿自然界的生物进化机制而发展起来的随机优化方法。GA能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最优解。
遗传算法首先进行种群设定、再进行编码操作、接收进行选择算法、变异算法、交叉算子等操作,经过反复迭代运算求出最优解。本质上其仍是一种搜索算法,依据生物进化原理,模拟基因重组与进化的自然过程,把待解决问题的参数编成二或十进制编码(基因),若干基因组成一个个体,许多个体进行类似于自然选择、配对交叉和变异运算,经过世代遗传得到最优解。其中适应度值越大,解越优即定位中所具有的权值越大[7,8]。
3 基于遗传算法的定位方法
针对DV-hop和质心等Range-Free方法和基于RSSI的Range-Based方法,定位精度不高或定位条件苛刻的不足,本文在综合考虑每个锚节点剩余能量及到待定位的未知节点距离情况对未知节点定位计算和整个网络性能的影响的情况下,设计了一种基于遗传算法的高精度Range-Free算法。算法的具体步骤为[3,7,8]:
步骤1:遗传定位算法的适应度函数设置。
定义1:为了对锚节点j进行定位计算,需要建立的适应度函数。
称为训练适应度函数。式(1)中,αl是一个权值,它反映了待定位锚节点j与其他锚节点间的距离,距离越远则对定位计算的影响越小,相应地α越小。
由于锚节点j的位置信息已知,根据式(2)可得其误差值errmj。
其中,(xj,yj)和分别表示锚节点j提供的参考位置和估算位置,R为网络中节点的通信半径。随后采用轮盘法对网络中的其他锚节点进行相同的位置计算并获得对应的误差值,获得网络中所有锚节点的误差值后,作为一个数组并进行降序排列,最后得到的数组errm。
在式(1)的基础上,考虑到每个锚节点的剩余能量对网络定位性能和使用寿命的重要影响,该算法中提出采用的适应度函数为
其中,Dij和dij分别为未知节点i与锚节点间的真实距离和利用RSSI所得的测量距离,Ej分别为锚节点的剩余能量。
步骤2:遗传定位算法的染色体编码。
考虑无线传感器网络中节点数目较多,计算量较大的特点,以及二进制编码很难直接反映定位过程并且所耗内存较大的问题,文中所述的算法直接采用实数编码型的遗传算法。
步骤3:遗传算法的算子设计。
遗传算子主要包括选择、交叉和变异操作。选择操作采用基于适应度的赌轮选择法;交叉采用多点交叉,即x轴参数和y轴参数分别对应交叉;变异操作选择离散单点变异操作方式。
步骤4:遗传定位算法的终止条件设置。
当迭代次数达到预定次数或者群体的成熟度满足一定条件时,停止迭代。
4 仿真及讨论
实验在MATLAB 7.0的环境下进行,采用Matlab GA进行优化运算。假设传感器节点的通信半径R=10,实验首先在5R×5R的感知区域内随机分布100个传感器节点,同时假设锚节点比例为5%。
4.1 性能评价指标
(1)定位误差:估计位置与实际位置的距离相对于节点无线射程的大小。其计算公式为:
其中,n'为网络中被定位的未知节点个数。
(2)定位比例η:表示可定位节点占未知节点数的比例。其计算公式为:
4.2 仿真结果分析
由于锚节点密度、节点通信半径等变量之间具有直接关系,可以相关表征。因此,文中在分析该算法定位性能时,仅改变标准网络环境中的节点通信半径,测距误差因子分别取0%和1%,其它参数不变。为了验证算法的定位性能,对比不同通信范围下的定位误差。
由图1可知,不论代数如何改变,两种算法的平均定位误差都随着节点通信半径的增加而逐渐减小。这是由于当锚节点数目增多和节点通信半径增加时,节点可以利用的准确的位置信息增加,定位误差变小且通信半径达到90以后,定位精度区域平稳。在定位时,的区域中的定位误差理论值可以达到1.5%以下。
5 结论及展望
本文利用传统的遗传算法对传感器网络定位技术进行研究,提高了定位精度,并通过仿真对其优越性加以说明。但是,这种算法仍然存在着不足。算法对受测距误差影响较大。但是当测距误差在一定范围内时,该算法能获得非常高的定位精度。综上所述,该算法在今后的研究中将对测距误差的影响进行改进。
参考文献
[1]史龙,王福豹,段渭军,任丰厚.无线传感器网络Range-Free自身定位机制与算法.计算机工程与应用,2004,23
[2]马祖长,孙怡宁.无线传感器网络节点的定位算法.计算机工程,2004,(4)
[3]张华.基于遗传算法的无线传感器网络节点定位的自定位技术研究.杭州:浙江工业大学,2008
[4]Cheng XZ,Thaeler,Xue G L,Chen D C.TPS:a time-based positioning scheme for outdoor wireless sensor networks.IEEE INFO-COM'2004.Hong Kong,China.March7-11,2004,2685~2696
[5]He T,Huang C D,Blum B M,et al.Range-free localization schemes in large scale sensor networks.Proceedings of the9th Annual International Conference on Mobile Computing and Networking.San Diego,California,USA.ACM Press,2003:81-95
[6]Liu C,Wu K.Performance Evaluation of Range-Free Localization Methods for Wireless Sensor Networks.Computer Science Dept U-niversity of Victoria BC,Canada,2005
[7]王金鑫,赖旭芝,吴敏.一种基于遗传算法的无线传感器网络定位新算法.计算机技术与自动化,2007,(4)
无线定位算法 篇9
无线传感器网络的节点自定位就是根据少数已知未知的节点,按照某些定位机制确定自身的位置。只有在传感器节点自身定位之后,才能确定传感器节点检测到的事件发生的具体位置,这需要检测到该事件的多个传感器几点之间互相协作,并利用它们自身的未知信息,使用特定的机制确定发生的位置。因此,在传感器网络中,传感器节点自身的定位是提供监测事件未知信息的前提。
1 节点自定位算法分析
1.1 节点自定位算法的分类
根据定位机制可以将现有的无线传感器网络节点自定位算法分为两类[2]:Range-Based和Range-Free,前者需要通过测距或者角度信息;后者无需距离和角度信息,仅根据网络连通性等信息实现节点的定位。
距离无关的定位机制(Range-Free)[3]无需实际测量节点间的绝对距离或方位就能够计算未知节点的位置,因而降低了对节点硬件的要求,且定位性能受环境因素影响较小,适合应用于大规模的传感器网络,其中质心算法、DV-Hop算法[5]、Amorphous[6]算法和APIT算法是4种目前倍受关注的分布式的Range-Free定位机制。
基于距离的定位机制(Range-Based)需要根据节点间距离或角度的测量结果进行定位计算。常用的测距技术有Trilateration算法[4]和循环三边组合测量法(ACT)[6]。
1.2 几种节点自定位算法
该文主要研究基于距离的定位机制中的Trilateration算法和ACT算法,并且对ACT算法进行改进降低算法的复杂度,提高算法的定位精度。
1)Trilateration算法
Trilateration算法称为三边测量法,三个信标节点的坐标已知,分别为:(x1,y1),(x2,y2),(x3,y3)。三个信标节点到未知节点的距离分别为d1,d2,d3。按照如下关系式:
可计算出未知节点坐标为:
2)ACT算法
Trilateration算法三个信标节点的位置对于定位的误差影响很大,比如当三个信标节点成等边三角形分布时,定位的误差最小,当三个信标节点共线时,定位误差最大。
在这里我引入一个新的定义,角度权重函数:
W(a)min{Ad,Bd,Cd}
Ad,Bd,Cd分别为三角形ABC三个角的弧度值。
因为任意的三个信标节点可以确定一个顶点,所以N个信标节点根据排列组合可确定出CN3个权重多边形。
所以根据上面的分析ACT算法的步骤如下:
第一步:确定权重多边形的顶点坐标:每个信标节点广播自身的ID以及位置信息(Xi,Yi)(i=1,…,N),邻居节点均能收到这些信息并利用TDOA[3]技术估计它到信标节点的距离ri(i=1,…,N),根据信标节点中任意三个坐标值的组合及距离值计算权重多边形的顶点坐标。例如:(Xa,Ya)(Xb,Yb)(Xc,Yc),ra,rb,rc使用SSL算法计算权重多边形的顶点坐标(IXj,IYj)(j=1,…,N):
[LXj,IYj]T=(MTM-1)MTL
其中:
第二步:确定权重多边形顶点的权重值:
根据已知条件利用三角函数余弦定理计算出权重多边形三个角的弧度值Ad,Bd,Cd,再利用权重函数计算权重。
第三步:重复步骤1和2计算权重多边形其它的CN3-1个顶点坐标以及对应的权重值。
第四步:归一化权重
第五步:确定未知节点的坐标:
第六步:重复步骤1到5计算其它未知节点的坐标值。
3)改进的ACT算法
ACT算法有着良好的定位精度,但是缺点是显而易见的就是算法的复杂度偏高,因此需要对ACT算法进行简化,在之前我们分析过当三个节点成等边三角形分布时定位误差最小,共线时定位误差最大,因此我们得到了如下的启发:N个信标节点中我们没有必要选取所有可能的组合来进行定位运算,因为由于误差的累加定位误差可能越累计越大,所以我们通过某种方法选取信标节点分布较好(接近于等边三角形)的前m种组合,这样但可以大大的简化算法的复杂性同时也提高了定位的精度。从第3节的仿真结果中我们可以看到,总存在一个m使得定位的误差最小,同时也大幅度的降低了计算的复杂性,节省了开销。
对ACT算法改进如下:
第一步:采用不同的权重函数。
第二步:不对CN3种组合进行三边测量,改为取前m个权重值最大的进行三边测量。
改进的ACT算法实现步骤如下:
第一步:对于任意的三角形首先计算出三个顶点的正切值:
tan A=(K2-K3)/(1+K2K3)
tan B=(K1-K3)/(1+K1K3)
tan C=(K2-K1)/(1+K2K1)
其中K为三个顶点对应三条边的斜率
权重函数为:
W(a)=min{tan A,tan B,tan C}
第二步:利用上面的方法计算每个三角形的权重值:
W(aj)=tanaj(j=1,…,CN3)
第三步:对于所有的三角形按照权重值进行排序,取权重值最大的前m个。
W(ak)=tanak(k=1,…,CN3)
第四步:对于前m个权重值的进行归一化处理:
第五步:根据三边测量法计算m个顶点的坐标:
其中
第八步:确定未知节点的位置:
2 实验仿真和结果分析
2.1 仿真环境
该文选用MATLAB版本为R2007a,运行硬件平台为Inter(R)1.73GHz CPU,1.00GB RAM,120GB 7200RPM Hard disk的PC机进行仿真。
2.2 仿真对象
1)无线传感器网络节点自定位Trilateration算法。
2)无线传感器网络节点自定位ACT算法。
3)无线传感器网络节点自定位改进的ACT算法。
2.3 仿真结果
试验中选取100m*100m的仿真环境,加入20%的高斯噪声,通信半径R=10m,信标节点和未知节点的比例为1:10,即10个信标节点,100个未知节点,均为随机分布。如图1所示,蓝色星形为未知节点,黑色钻石型为信标节点。
1)Trilateration算法仿真结果
2)ACT算法仿真结果
图3为ACT算法进行定位后实际位置(星形)和估计位置(绿点)。
3)改进的ACT算法仿真结果
图4为改进ACT算法进行定位后实际位置(星形)和估计位置(红点)。
2.4 仿真结果分析
1)经验值m的选取
经过100次仿真总存在一个m值使得定位精度最大,如图5所示我们可以看出m取38时定位精度最高,因此我们可以根据经验来选取m(不同的环境可能存在不同的m值)。
2)三种方法的定位精度比较
如图6所示,绿色为Trilateration算法定位精度,红色为ACT算法的定位精度,蓝色为改进的ACT算法的定位精度。在相同的条件下对三种方法进行100次循环运算,Trilateration算法的平均定位精度为35.67%,ACT算法的平均定位精度为25.11%,改进的ACT算法的平均定位精度为21.45%。通过实验数据可以看出Trilateration算法的定位精度最差,改进的ACT算法的定位精度最好。
3)算法复杂度比较
本实验仿真N取100,m若取38则,ACT算法的乘除运算次数约为6720次,三角函数运算为360次,改进的ACT算法的乘除运算为2524次,没有三角函数运算,因此从算法复杂度来说Trilateration算法最简单,ACT算法最为复杂,改进的ACT算法大大简化了ACT算法的复杂性。
3 结束语
该文针对目前无线传感器网络的节点自定位算法中基于测距的Trilateration算法,ACT算法进行详细研究,可以看出两种算法各有特点。主要对ACT算法进行改进,不但大幅度降低了ACT算法的运算复杂度,而且提高了ACT算法的定位精度。
参考文献
[1]S Tilak,N.B Abu-Ghazaleh,W Heinzelman,A taxonomy of wireless micro-sensor network models.Mobile Computing and Communi-cations Review,2002,1-8.
[2]e T,Huang C,Blum B M.Range-free localization schemes for large scale sensor networks.In:Proc9th Annual Int'l Conf on Mobile Computing and Networking(MobiCom),San Diego,CA.,2003:81-95.
[3]孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005:3-5.
[4]K Langendoen,N Rejiers.Distributed localization in wireless sensor networks:Auqnatitative comparison[J].Computer Networks,2003,43(4):499-518.
[5]NiruPama Bulusu,John Heidemann,Deborah Estrin.CPS-less low cost outdoor localization for very small devices[J]IEEE Wireless Com-munications,2000,7(5):27-34
无线定位算法 篇10
无线传感网络的很多应用都涉及距离位置信息, 基于无线传感网络的大空间定位技术也因此成为这一研究热点的关键基础技术。无线传感网络定位技术有基于非测距定位技术和基于测距定位技术,基于测距的定位技术分为基于信号接收强度指示值测量(RSSI)方法、基于到达时间测量(TOA)方法以及基于时间差测量(TDOA)等方法等。本文对基于时间差的测量方法 (TDOA)进行分析研究和仿真,面对距离测量精度和范围的限制,寻找高精度的定位算法,面向无线传感网络结构参数通过仿真评估大空间定位精度。研究对设计满足一定定位精度的无线传感网络具有指导意义。
1原理分析及算法
基于距离测量的大空间定位方法通过测量移动节点到信标节点的距离实现移动节点的空间定位,高精度定位的关键点在于高精度的距离测量方法及高精度的定位算法。
假设在移动节点P(x,y,z)周围有n个位置已知的信标节点G1(x1,y1,z1),G2(x2,y2,z2),…, Gn(xn,yn,zn)参与测量,如图1所示,它们与移动节点的距离的测量值为D1,D2,…,Dn,而理论距离为:
以测量距离与其理论值的残余误差平方和最小为原则定位移动节点P(x,y,z),则测量模型为:
这是一个无约束非线性优化问题,理论上可以用非线性无约束优化方法求解[1]。在此,笔者提出一种线性迭代算法求解该非线性优化问题。
设方程组(3)的极大似然估计解为P0(x0,y0,z0),则有:
其中:
把移动节点近似解P0(x0,y0,z0),带入式(1)有:
将式(1)在P0处作一阶泰勒展开处理,有:
带入式(2),则式(2)转换成无约束的线性最小二乘问题,那么,其解为[2]:
其中:
因此,得移动节点的新定位坐标P1(x1,y1,z1),为P1(x0+∆x,y0+∆y,z0+∆z),将P0和P1分别带入式(2)计算两者残差平方和之差,如果满足收敛条件(即残差平方和之差的绝对值小于e),则停止计算,P1则为式(2) 的最优解;否则赋值P0=P1,进行新一轮迭代。该算法通过迭代线性最小二乘问题来求解非线性最小二乘问题,求解精度高于传统方法。
2选择性定位算法分析
基于TDOA的定位方法使用两种传播速度不同的无线信号(电磁波和超声波)实现移动节点到信标节点的距离测量。假设移动节点在T0时刻同时发射超声波和电磁脉冲信号,某信标节点在T1、T2时刻分别接收到无线脉冲信号和超声波信号,得移动节点到信标节点之间的测距公式为:
超声波在20℃环境下传播速度约为V超=344m/s、电磁波传播速度约为V电=3×108m/s,两者相差巨大,从而测距公式可以简化为:
由此带来的测量误差在百米范围内小于0.1mm。因此,所谓基于到达时间差的测距定位方法简化后就是超声波测距定位法,而电磁波信号的作用仅仅是确定超声波发射的时间。
超声波换能器具有较好的方向性和额定的发射功率,这些因素限制了超声波覆盖角度和可测距离范围。 假设超声波最大测距范围为Dmax、覆盖角度为θmax,若移动节点发射测距信号,距离可测区域为以其自身为中心、正传播方向为轴线、θmax为锥角、Dmax为半径的锥球体,如图2所示。因此,参与移动节点定位测量的信标节点是有选择性的,只有那些位于移动节点发射信号覆盖区域内的信标节点才能参与移动节点的定位测量, 故移动节点的定位测量模型为:
其中,
这是一个有约束非线性优化问题,算法类似于无约束定位算法,只是添加信标节点选择模块,算法流程如图3所示。
在基于距离测量的空间定位技术中,任何测量原理都存在着测量距离和角度的约束,因此笔者提出的选择性定位算法不仅可以用于超声波测距定位,也可以用于其他无线传感网大空间定位测量,只需要更改约束参数即可。
3空间定位精度分析
项目采用激光测距技术实现高精度超大空间坐标测量定位;采用无线传感网TDOA定位测量技术实现激光靶镜初定位,以引导激光跟踪,因此要求无线传感网定位实现激光靶镜的正确定位,确保激光光束不脱靶。 系统构架是:移动节点实现无线信号发射、信标节点接收无线信号,采用的超声波换能器发射波束角60°最大探测距离15m。经过测试实验,超声波最大测距范围为10m;覆盖角度为±30°。实验测得在此范围内超声波距离测量标准差为[2]。
在此,σ和D以mm为单位、θ以rad为单位。那么, 面对移动节点特定的定位空间要求50m×50m×10m以及定位精度±35mm要求,研究信标节点网络配置算法是十分必要的。
1)蒙特卡洛仿真模块
蒙特卡洛方法又称为随机事件模拟,随着计算机技术和软件技术的发展,该方法已广泛应用于测量不确定度评定、可靠性分析评估、仪器误差综合和精度分配等领域。其通过对不同分布的抽样来模拟仪器系统参数的随机误差源,引入仪器测量方程后,通过对大量仿真计算结果的统计来评估仪器精度[3,4]。
若某一信标节点位于移动节点P(x,y,z)的覆盖范围, 测得距离测量值为Di、与移动节点的角度估计值为θi, 带入式(5),获得距离测量的标准差σi。对每一个信标节点 , 设超声波 测距误差 服从均值 为零 、 方差为 σi(i=1,2,,m)(如式(5)所示)的正态分布,采用MATLAB命令在该分布中抽样随机数δi(i=1,2,,m)来模拟距 离测量误 差∆Di, 加上距离 测量值Di(i=1,2,,m)后带入式(4),计算移动节点的定位结果。计算定位误差:
对于某一移动节点,经过K次计算,对计算结果进行统计,统计获得该移动节点的定位误差的标准差。定位精度评估算法框图如图4所示。
2)仿真计算
设信标网络配置如图5所示。其中L表示信标节点间距;low,high表示研究区域的垂直范围;bianch表示研究区域的水平范围,整个研究区域即灰色部分。通过仿真计算萃取研究区域内满足一定定位精度的可定位空间范围。
信标网络配置参数如表1所示,面对表1所示的研究空间范围和不大于±35mm的定位误差要求。在研究区域内按照正方体的排列方式,每隔50mm取点计算移动节点的定位精度并把所有满足精度要求的点绘制成三维图。
图6~图8分别呈现了当信标节点间距L为1m、1.5m和2m时满足定位精度要求的移动节点可定位区域。显然,满足精度要求的移动节点可定位区域随信标节点间距的增加而逐步减小,并且离信标网络越远,水平可定位区域越小。
图9呈现的是当信标节点间距为1m,距离信标节点垂直距离为8m的XY平面上移动节点的精度分布情况, 显然定位精度在四个边角区域下降,有相当大的区域定位精度保持一致。
4结束语
基于RSA的无线加密算法研究 篇11
【关键词】无线网络 RSA 加密算法
近年来，计算机及通信科学发展突飞猛进，利用网络交流和处理信息变得越来越普遍。尤其 以无线局域网（WLAN）为代表的无线网络技术得到了高速发展和应用。无线网络作为有线网络的补充和延伸，在与日俱增的网络活动中，人们越来越关注其安全的问题。
一、无线网络的特点和存在的安全问题
（一）无线网络的特点
无线网络具有传统有线网络无法比拟的优点：灵活性，不受线缆的限制，可以随意增加和配置工作站；低成本，无线网络不需要大量的工程布线，同时节省了线路维护的费用；移动性，不受时间、空间的限制，随时随地可以上网；易安装，和有线相比，无线网络的组建、配置、维护都更容易。
（二）无线网络存在的安全问题。
1.影响WLAN的因素。IEEE 802.11的標准规定，WLAN的传输介质是无线电波。因此只要在WLAN信号覆盖范围内，入侵者可以在预期范围以外的地方访问WLAN，通过各种手段入侵WLAN，窃听网络中的数据并且对无线网络进行攻击。 其次，由于WLAN是遵循TCP/IP网络协议的一种计算机网络，所以WLAN内的计算机也会遭受来自计算机网络病毒的威胁，甚至会产生比有线网络更加严重的后果。
2.无线网络的安全问题主要表现。无线网络的安全问题主要在下面几个方面：（1）非法的AP，容易侵入。（2）未经授权使用服务和性能的限制。（3）地址欺骗和会话拦截。（4）流量分析与侦听。（5）高级入侵。基于上述特点，无线网络的通信保密能力需要一种强有效的安全机制来保障。数据加密是通过对信息进行重新编码，达到隐藏信息内容、使非法用户无法获得真实内容的一种技术，其核心就是加密算法。数据加密就是一种保障无线网络通信的有效方法。
二、无线网络的加密算法分析
数据加密的基本过程是，对明文的档或数据按某种算法进行处理，得到不可读的一段代码，通常称为“密文”，只有在输入相对应的密钥之后才能显示出本来内容，通常称“解密”。通过这样的方法来保护数据不被非法人窃取、阅读。无线网络的加密体制，按密钥方式划分，主要有对称式密钥加密和非对称式密钥加密两种。
（一）对称式密钥加密
对称式密钥又称常规密钥，是指加密的收发双方使用相同密钥的密码，且密钥是保密的，不公开，通常称之为“SessionKey”。其加密体制的特点是，收发双方具有相同的加密与解密的密钥，发送方用密钥对数据（明文）进行加密，接收方同一个密钥对收到的数据进行解密。对称密钥加密实现容易、速度快，但是为了保证密钥的安全，必须通过安全通道来传送密钥。
（二）非对称密钥加密
非对称加密算法又名“公开密钥加密算法”，需要两个密钥：公开密钥和私有密钥。如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密，所以这种算法叫作非对称加密算法。非对称密钥加密体制包括RSA、ELGamal、椭圆曲线加密等算法。其中RSA算法为当今世界上应用最为广泛的非对称加密算法
三、RSA算法
RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击。RSA公钥加密算法是在1977年提出的目前已被ISO推荐为公钥数据加密标准。
（一）RSA算法的原理
1.加密消息。假设甲想给乙送一个消息m，甲知道乙产生的N和e。那么甲使用事先与乙约定好的格式将m转换为一个小于N的整数n，比如甲首先将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如甲的信息非常长的话，也可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：。计算c并不复杂。甲算出c后就可以将它传递给乙。
2.解密消息。乙得到甲的消息c后就可以利用她的密钥d来译码。她可以用以下这个公式来将c转换为n： 得到n后，乙可以将原来的信息m重新复原。
3.签名消息。签名消息检测出数据在传播路径上有没有被篡改过，RSA也可以实现消息署名。假如甲想给乙传递一个署名的消息，那么甲为自己的消息计算一个散列值（Message digest），然后用甲自己的密钥（private key）加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用甲的公钥才能被解密。乙在获得消息后首先用甲的公钥解密这个散列值，然后将这个数据与乙为这个消息计算的散列值相比较，如果两者相符，乙就知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。
（二）RSA算法的攻击方法和应对
RSA算法的攻击方法主要有模数攻击、时间攻击和因子分解。解决模数攻击的办法是不共享模数。时间攻击。假如甲对乙的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么甲可以很快地推导出d。因为在进行加密时所进行的模指数运算每个位元进行的，所以如果能得到多组信息和信息的加密时间，就会有机会可以反推出私钥的内容。因子分解。因子分解在RSA安全性的时候已经论述，因子分解可以成功破解RSA，也是最流行的一种攻击方法。应对方法是在一定条件下尽可能选取大数。RSA算法易于理解和操作，是第一个能同时用于加密和数字签名的算法。RSA从诞生到现在历经各种攻击的考验，是被研究的最广泛的公钥算法，也是目前最优秀的公钥算法之一。
四、总结
将基于RSA的算法用于WLAN及更多的平台，确保具有开放性与共享性的无线网络不受到外界的攻击与破坏。随着计算机网络的不断发展，更多的优秀的加密算法也会涌现出来。
参考文献：
[1]杨峰，张浩军.无线局域网安全协议的研究和实现[J].计算机应用.北京邮电大学出版社
[2]贺雪晨.信息对抗.与网络安全清华大学出版社（第2版），2010，5.
无线定位算法 篇12
近年来,无线传感器网络技术及应用迅速发展,由于其节点成本低、功耗小、系统稳健、组网灵活,得到业界的广泛关注。清华大学提出城域感知与运营网络(Metropolitan Area Sensing and Operating Networks,MASON)概念,面向城市环境信息采集应用,在大空间尺度上部署传感器节点,通过节点移动性和动态组网扩展信息采集范围和传输效率。
在城市无线传感器网络应用中,传感器节点的位置信息十分重要[1,2],在生态环境监测、自然灾害的现场监控等应用中,传感器节点所发回的物理信息数据要有意义,就必须与其地理位置相关联,从而使上层得到信息来源的准确位置,有时甚至需要传感器节点发回单纯的位置信息[3,4],例如,在目标跟踪应用中,传感器节点通过监测所跟踪目标的移动速度,在知道其所在位置的情况下,用特定的分析算法,计算目标当前的运动轨迹并预测未来的移动路线。此外,节点位置信息还可以为其他协议层的设计提供帮助。在应用层,节点位置信息对基于位置的信息服务应用至关重要,同时,位置信息还可以提供整个网络对物理空间覆盖质量的评估;在网络层,位置信息可以帮助路由算法得到更好的性能,提高路由效率,实现网络的负载均衡和网络拓扑的自配置等;在城市环境的无线传感器网络的监测、跟踪、预警等应用中,传感器节点所发回的空气、水体、噪声、天气、交通、安全等意义信息都需要信息来源的准确位置来支持,因此,需要研究高效的定位方法来确定传感器节点的位置信息[2]。
由于传感器节点的位置信息在应用中的重要作用,节点定位成为了无线传感器网络的主要研究方向之一。由于传感器节点通常是用随机的方式部署到监测区域中的,因此预先确定节点的部署位置比较困难,只能在部署完成后,通过一定的技术手段获取节点的绝对地理坐标或相对位置信息。当前,最普遍使用的定位系统是全球定位系统(Global Positioning System,GPS),但是由于其需要单独的定位芯片组,成本开销和功耗较大,只适用于室外开阔地带,不适于低功耗、低成本、大规模的无线传感器网络。在机器人研究领域,目前也有很多关于定位的研究,但是由于该领域算法一般不关心计算复杂度,同时需要有特殊的硬件设备支持,所以在无线传感器网络中也不能方便地应用[5]。
无线传感器网络定位机制根据其应用不同可以分为两类:第一类是针对静态网络拓扑的定位机制,其又可细分为基于距离(Range-Based)的定位算法和距离无关(Range-Free)的定位算法[6,7]。基于距离的典型定位算法有到达时间TOA的定位、到达时间差TDOA的定位、到达角度AOA的定位和接收信号强度指示RSSI的定位。距离无关的典型定位算法有质心算法、距离向量-跳段DV-Hop算法、Amorphous算法和近似三角形内点测试APIT算法;第二类是针对可移动网络拓扑的定位机制。典型的有利用移动GPS和路点(Way Point)的路径预测算法[8]和利用GPS的蒙特卡洛定位(MCL)方法[9,10,11]。这两类定位机制都要求传感器节点之间可以直接通信,即依赖于网络拓扑的密集性。由于无论是静态网络拓扑,还是可移动网络拓扑,其定位机制通常都依赖于3种最基本的方法[1]:三边测量法、三角测量法和极大似然估计法。这3种方法有效的最基本的前提就是传感器节点之间可以直接通信,对于存在移动节点缺乏连续的网络连接性的稀疏、延时容忍网络(Delay Tolerant Networks,DTN),这些基本方法不能够直接使用。
由于城市无线传感器网络的规模大、覆盖面积广、节点间距离较远,一般互相不在彼此的通信半径之内,整网的拓扑是稀疏且短暂互联的,数据传输要依赖于节点的移动性,是一种延时容忍网络,故传统的无线传感器网络定位机制在城市传感器网络中不能够直接使用。另外由于城市无线传感器网络节点的大规模和稀疏性,从成本、可扩展性和易用性的角度考虑,在节点上配备GPS设备、加速度传感器或任意其他跟测量相关的硬件都是不可取的。因而,有必要设计特殊的定位算法,以解决这类网络中的定位问题。
笔者考虑城市无线传感器网络低成本、低能耗、节点数量众多和强延时容忍等特性,提出一种可应用于城市移动无线传感器网络的新定位算法,该算法不需要任何其他附属的硬件设备就能完成定位,分析其收敛条件,通过仿真验证,给出误差分析。
2 系统模型
根据不同类型节点对定位的不同作用,城市无线传感器网络可分为以下3类:
1)信标节点(Anchor)。数量较少,地理位置信息已知,可与接近它的移动节点交换信息,一般在无线传感器网络中负责信息汇集的作用。
2)传感节点(Sensor)。随机布撒,数量非常多,地理位置信息未知但位置保持不变,需要定位,可与接近它的移动节点交换信息。
3)移动节点(Carrier)。被车辆携带,从而在网络中移动,其地理位置信息未知且经常变化,可与路过的临近的信标节点和传感节点交换信息。
在城市无线传感器网络中,由于网络的稀疏性,无法直接通过测距、测角等基本方法来设计定位方法,但可以得到网络节点的其他信息,如移动节点的最大移动速度、信标节点的位置等[8,10],因而可以结合多节点协同[12]的方法来帮助定位。另外由于其延时容忍特性,还可以通过大量的观测得到城市环境下车辆流(Traffic Stream)的运行轨迹和统计学特性的经验统计模型,根据经验统计模型来给移动节点建立概率移动模型,在此基础上,应用统计学的方法,可以实现位置保持不变的传感节点的定位。
文献[13]在分析了车辆运行统计模型的基础之上,提出了曼哈顿格(Manhattan Lattice,ML)模型。ML模型在不失本质和普遍性的前提下模拟了大量车辆同时在城市中运行的统计学规律。笔者在有关Torus环结构的研究成果[14]下把该模型加以改进,并结合城市无线传感器网络的系统,形成了适用于城市无线传感器网络定位算法分析的曼哈顿环(Manhattan Torus,MT)模型。该模型使得针对城市无线传感器网络的理论和仿真分析更加容易,具体表述为:假设移动节点在n×n的MT图的边上自由行走在每个交叉点以一定的概率选择右转、前行和左转中的任意一种,如图1所示,其中图1a表示MT图,在Torus环的基础上加入了网格Lattice,图中两条粗线分别标示区域分块的长度和宽度。图1b表示车辆的行走方式,其在MT图的所有边上都是自由行走的。图1c则表示了移动节点在交叉点处的方向选择。
移动模型的基本假设:
1)所有移动节点的移动在图上满足MT模型,并在每个计时时刻以一定概率选择在下一个时间间隔内右转、前行或左转。每个计时时刻内的移动距离相当于MT图中一个短边的距离,设为1(称为一步)。
2)所有信标节点和传感节点均不重叠地位于各个交叉点上。事实上,如果传感节点与信标节点重叠,显然该传感节点已无需定位。
3)信标节点的数量和位置已知,传感节点则在交叉点上随机布撒。
4)移动节点与信标节点或传感节点的通信只能当它们位于同一个点上的时候才能进行。
3 定位算法
在上述移动模型的基础上,设计了一种基于位置概率分布收敛原理的定位算法,其基本原理为:每一个节点都维护了对自身当前位置的估计,以概率分布的形式表现。当两个节点相遇时,双方通过短距离无线通信信道,交换其对当前位置估计的概率分布,并根据两个概率分布函数计算新概率分布,以更新对当前位置的估计。直观上,由于网络中存在位置已知的固定信标节点和数目众多的移动车辆,这个方法可以通过车辆的移动定位大量随机布撒而位置未知的传感器节点。
在n×n的MT图中,概率分布可以表示为n2维向量的形式。由于移动节点无法直接获知自身移动方向,每移动一步,其概率分布区域随之扩大,由每一个点扩散到MT图中以该点为中心的周围5个点上。两节点相遇时,将双方的概率分布相乘后归一化,得到新的概率分布,完成概率更新。新的概率分布为
式中,pA和pB分别表示概率更新前的A,B节点位置的离散概率分布,是n2维向量。pA′和pB′则分别表示概率更新前的A,B节点位置的离散概率分布,也是n2维向量。pA×pB表示pA和pB对应元素相乘,其结果为n2维向量,分母pA·pB表示pA和pB的内积,是归一化因子。据此提出定位算法,如图2所示。
该算法的收敛性要依赖于信标节点的数量和位置,下面对其进行初步的分析。
由于直接分析二维MT的收敛情况比较困难,先讨论一维和二维ML图的收敛情况,并利用ML图的方法和结论,引出对MT的收敛性的证明。
1)已知节点间距离,对一维ML图定位,需要至少2个信标节点。如果网络中没有信标节点,则只能知道节点的相对位置信息,不能获得节点绝对位置坐标,因而至少需要1个信标节点。又因为若整个图以唯一信标节点为轴心旋转,可以在保持相对位置不变的前提下,改变节点绝对位置,所以至少还需要1个信标节点来消除旋转。事实上,以图中任意两点所成直线为轴的镜像都不能改变绝对位置。
2)至多3个信标节点可以保证一维ML图的收敛。对于一维n格ML图[13],如果n为偶数,则只需要2个信标节点占据一维ML图的两端,就能保证全图收敛;如果n为奇数,采取奇偶分解的方法,将一维ML图分解为n-1格和另外1个格,n-1格为偶数,需要2个信标节点,另外1个格子需要1个,在这种情况下,共需要3个信标节点就能够保证收敛。
3)已知节点间的距离,对二维ML图定位,需要至少3个信标节点。由2)可知,至少需要2个信标节点来消除旋转。又因为整个图是以这2个信标节点为轴的镜像翻转,可以在保持相对位置不变的情况下,改变节点的绝对位置,故还需要1个不在这2个信标节点所成直线上的信标节点来消除镜像。对于二维ML图,至少需要3个信标节点消除旋转和镜像。
4)至多9个信标节点可以保证二维ML图的收敛。对于二维n×m格ML图,如果n与m均为偶数,则由3)可知,只需要在ML图的四角放置4个信标节点就能保证最外围节点的点点收敛,而最外围节点的收敛又保证了中央所有节点的收敛;如果n和m不全为偶数,则仍采取奇偶分解的方法,这里仅以最复杂的n和m均为奇数的情况为例,将ML图分解为1个二维偶-偶ML图(二维(n-1)×(m-1)格ML图,需要4个信标节点)、2个一维偶ML图(一维(n-1)格ML图和一维(m-1)格ML图,均需要2个信标节点)和1个单格,故至多4+2×2+1=9个信标节点就能够保证全图点点收敛。
5)由3)可知,已知节点间的距离,对二维MT图定位,需要至少3个信标节点。
6)至多25个信标节点可以保证二维MT图的收敛。对于二维n×m格MT图,仍然采取4)的方法,保证分出的最大图的长宽分别为不大于n/2和n/2的最大整数,至少可以分解为4个二维偶-偶图、4个一维偶图和1个单个格点,故至多4×4+4×2+1=25个信标节点就能保证收敛。
综上所述,在二维MT图中,按4)和6)给出的方法布置信标节点,可以保证算法的收敛。
4 算法仿真
仿真在Matlab环境下完成,依据MT移动模型,使用20×20的区域(使用长度和宽度均为20的区域分块方式)、8个信标节点、80个传感节点和50个移动节点,这与大城市中的车辆密度基本相符。在100次仿真过程中,信标节点位置不变,传感节点的位置则在每次仿真开始时随机生成且不与信标节点重叠,50个移动节点在仿真过程中的随机时间加入网络开始运动,设定其在每个交叉点的前行概率为0.75,右转概率为0.17,左转概率为0.08,图3和图4显示100次仿真的收敛情况。由于目前还未有专门针对稀疏、容延时网络的定位算法,因而笔者不给出与相关算法的仿真比较。
图3显示100次仿真每次的收敛时间,均值为236,即平均236步就能够使所有传感节点的位置估计收敛到1点。所有100次仿真都在378步之内达到收敛,这与之前的分析一致,验证了该算法的收敛性,并且不会有长的收敛时间。
图4 则按时间显示出收敛的速度。主曲线显示在每一时间达到收敛的传感节点数量的平均值,竖线显示各时间点均值的标准差。可以看出,从统计意义上来讲,每一时间收敛节点的数量的变化不大,这说明节点收敛的速度是可预期的,从而验证了该算法的稳定性。
图5 显示了某次仿真估计位置与传感节点实际位置的对比,可以看出,仿真的估计位置与节点的实际位置相差不大,从而说明使用该算法可以得到较为精确的位置估计。
事实上,在该算法下,估计位置与实际位置的差别取决于区域分块的精细度。显然,对于同一区域来说,分块越精细,仿真结果越接近实际位置,但同时会影响收敛时间,并且算法的计算复杂度会提高;相反,分块越粗糙,仿真结果与实际位置的差别越大,但会节省收敛时间,同时也会降低算法的计算复杂度。因而,对于定位精度有不同需求的系统,可以选择不同精度的区域分块方式。但就方法而言,该定位算法对于不同的分块精度不会有差异。
5 小结