文档介绍：国防科学技术大学
博士学位论文
无线传感器网络拓扑识别与构建技术研究
姓名:董德尊
申请学位级别:博士
专业:计算机科学与技术
指导教师:廖湘科
2010-10
国防科学技术大学研究生院博士学位论文
摘要
拓扑识别与构建是无线传感器网络研究中的重要问题。无线传感器网络对信
息的采集、处理和传输都需要有效组织的拓扑结构作为基本保障。现有的拓扑问
题研究大部分假设已知节点精确位置信息。获取准确的位置信息在大规模传感器
网络中非常困难。对位置信息的严格依赖很大程度上限制了这些方法的实际可用
性。不依赖位置信息的拓扑技术可极大提高网络系统在位置信息无法获取或部分
可用情况下的有效性,成为近年来拓扑问题的热点研究方向。本文以提高方法的
可用性和效能为目标,针对已有工作不足之处,系统地研究了不依赖于位置信息
的拓扑识别与构建中的一些重要问题。在拓扑识别部分,本文致力于从网络连通
信息中挖掘网络的几何和拓扑特征。在拓扑构建部分,本文致力于设计基于连通
信息的覆盖和连通拓扑结构。论文主要研究内容和创新点包括以下几方面。
第一,边界识别是传感器网络拓扑识别的核心问题。已有的不依赖位置信息
的方法从识别质量来讲都是粗粒度方法。粗粒度方法不能实现包括计算网络空洞
的数量和位置等边界识别问题所关心的重要目标。本文首次提出仅利用连通性信
息且可分布式执行的细粒度边界识别算法。本文从拓扑学角度对网络边界进行了
形式化的定义,并对每个网络边界明确地计算出有意义的边界环,实现对网络边
界的细粒度定位。
第二,本文进一步研究识别网络异常的高维拓扑特征,即网络由于遭受虫洞
攻击而产生的拓扑异常。虫洞攻击是无线传感器网络中的严重攻击。现存的虫洞
检测方法都需要依赖于专业的硬件设备或对网络设定很强的假设条件,制约了这
些方法在传感器网络中的适用性。本文首次提出不需要任何特殊硬件设备和严格
网络假设、仅利用连通性信息的分布式虫洞检测方法。本文通过分析虫洞对网络
拓扑产生的本质影响,设计拓扑学方法来捕捉由虫洞导致的拓扑背离现象,进而
通过追踪这些异常现象的根源来定位虫洞。
第三,本文基于边界识别得到的网络边界,进一步研究调度网络内部节点构
建面向覆盖应用的拓扑结构。覆盖拓扑构建是无线传感器网络拓扑构建的重要问
题。为实现确定性保证的区域覆盖,已有的覆盖方法大部分需要依赖位置信息或
测距信息,少数仅基于连通性的方法则存在需要集中式计算和覆盖粒度不可调等
严重限制。本文首次提出仅利用连通性信息、覆盖粒度可配置的、分布式的覆盖
模式。本文建立不依赖位置信息覆盖问题的图理论框架,设计了基于环分割技术
的覆盖判定准则,设计了利用连通性信息的分布式稀疏覆盖集调度算法,且算法
能够充分利用节点不同的感知能力或根据不同应用的覆盖需求调整覆盖粒度,实
现不同的覆盖质量。
第 i 页
国防科学技术大学研究生院博士学位论文
最后,本文研究面向新的应用需求的拓扑构建问题。本文致力于设计具有局
部监控能力的拓扑结构,使网络中每条通讯链路都能够被网络中一些点所监控。
本文首次形式化地建模自监控拓扑问题,并证明即使在有几何表出的单位盘图模
型中构造最优的自监控拓扑也是 NP 完全的,并在不同的图模型下对问题的理论可
近似性进行了深入分析。本文提出监控集受限图模型,并基于该模型设计出不依
赖位置信息的多项式时间近似模式(PTAS)的算法,和有近似比和时间复杂度保
证的局部化算法。
关键词:无线传感器网络;拓扑识别;拓扑构建;不依赖位置;连通性;边
界识别;虫洞检测;圈限覆盖;自监控拓扑
第 ii 页
国防科学技术大学研究生院博士学位论文
Abstract
Topology recognition and construction are important issues in wireless ad hoc and
works. anized structures work topology provide
necessary infrastructures for many work operations, . data gathering,
work processing munication etc. Most existing studies on topology issues
assume the knowledge of accurate location information of nodes. Such assumptions
substantially limit the applicability o