论文部分内容阅读
近年来,随着网络技术的发展,无线传感器网络作为连接物理世界和计算机世界的桥梁被广泛应用,具有很高的研究价值和应用价值。其中,定位技术是无线传感器网络设计和实现的一个关键问题,为网络提供重要的位置信息服务,是无线传感器网络的支撑技术之一。当前,前沿学者对定位技术进行了大量的研究工作,提出了很多面向传感器网络的定位算法,这些算法在特定的场景和特定的应用需求下都取得了良好的效果,但仍存在两方面的不足。第一,仅仅对单点定位进行研究而忽视了节点之间的合作特性。现有算法大都采用单个设备的定位技术来完成整个网络的定位,把网络定位建模成一系列的单点定位过程,忽略了节点之间潜在的合作定位的可能性,过度地简化了网络定位问题。事实上,在实际应用中很多不能进行单点定位的网络是可以通过节点之间的合作完成定位的,当前的研究工作都没有利用这个特点进行深入的研究。因此,定位技术研究在性能方面还有很大的提升空间。第二,误差处理无法满足应用需求。由于测距信息总是存在误差,有很多学者研究了测距误差对定位结果精度的影响,以期得到鲁棒(Robust)的定位结果。但这些算法对误差的处理过于保守,致使鲁棒定位结果的识别存在大量误判,这些误判使得很多节点无法定位,最终导致定位性能过低。针对上述技术瓶颈,本文系统地研究了无线传感器网络定位技术的关键问题,针对定位性能和鲁棒性这两个最重要的评价指标,展开以下几个方面研究:在高性能定位算法方面,本文突破传统单点定位技术研究的约束,提出了基于构件的定位技术。传统单点定位技术的基本定位单元是单个节点,限制了定位算法性能的提高,有很多可定位的网络实例无法通过单点定位技术实现定位。为了解决这一问题,本文提出了基于构件的定位技术,构件定位技术的基本定位单元是构件,即二维的刚性结构。通过聚合成构件,节点可以更好的进行合作,共享测距信息,从而实现节点集合的整体定位。本文建立了构件定位的理论基础,讨论了构件定位的实现方法,并分析了构件定位的性能收益,通过建立量化的评价体系,形式化地证明了基于构件技术的定位算法是目前性能最高的定位算法。在构件定位技术的基础上,本文进一步研究了鲁棒构件定位技术,使得构件定位能够有效地处理测距误差。基本构件定位技术采用的是理想测距模型,即假设节点间的测距信息是精确的,但是这个假设过于理想。为了使构件定位技术能够处理测距误差,本文进一步提出了鲁棒的构件定位算法,研究在有误差的情况下如何使构件定位结果具有鲁棒性。通过建立一系列鲁棒的坐标系统转换模式,解决了误差给构件定位带来的技术挑战。鲁棒构件定位技术不仅能够继承构件定位技术的高定位性能的特点,同时又保证了结果的鲁棒性。在定位鲁棒性方面,本文提出了强可定位网络概念。已有定位鲁棒性研究大都只关注结果的误差分布或者是网络的结构特性,导致分析结果仅适合特定场景下的定位问题,缺乏通用性。为了解决这一难题,本文提出了强可定位网络的概念来研究定位鲁棒性的一般问题,通过定位理论对定位鲁棒性做形式化分析,并提出了一个新的算法来定位一类特殊的强可定位网络——鲁棒三边测量网络。通过对误差的等价变换,分析误差对定位结果的影响,从而得到一种简洁高效的手段取得定位结果的鲁棒性。同现有算法相比,由强可定位网络得出的鲁棒三边测量技术能够更加精确地判定结果的鲁棒性,从而减少因误判而放弃定位的节点的数量,因此定位性能更高。在鲁棒三边测量网络研究基础之上,针对鲁棒性机制本身,本文提出了乐观的鲁棒定位机制。现有鲁棒定位算法大都采用悲观机制,即假定定位结果是非鲁棒的,然后通过鲁棒性判定条件来识别结果集合中鲁棒的结果,但这种机制只能识别全部鲁棒的定位结果的一部分,因此性能很低。为了解决这一问题,本文提出了乐观的鲁棒定位机制。乐观机制首先假定定位结果是鲁棒的,然后通过一致性检测识别那些错误定位的节点,在识别这些错误定位的节点后,乐观机制还能够纠正那些错误的定位结果。这样,乐观机制不仅能够保留那些鲁棒的定位结果,还能够有效处理那些错误的定位结果使之成为鲁棒的结果,其性能远高于悲观机制。通过概率模型,本文还形式化的分析了乐观机制的性能收益下界和开销。结果显示,乐观的鲁棒定位机制的定位性能严格高于悲观机制。综上所述,本文针对无线传感器网络中定位问题的性能和鲁棒性这两大关键技术难题提出新的解决方案,并且从形式化分析和模拟验证两个方面保证了本文所提出算法的有效性。