二维/三维无线传感器网络的骨架提取与应用研究

The key theories and technologis of wireless sensor networks have been extensively studied for a long time. Complicate topological features of sensor networks challenge for all kinds of applications, and topology recognition research is thus imperatively needed. Skeleton is an important descriptor of geometric and topological features of sensor networks,which can benefit other geometric and topological features discovery, and all kinds of applications of wireless sensor networks.This project is going to conduct a research on connectivity-based 2D/3D skeleton extraction in wireless sensor networks, without relience on boundary information. It firt maps the network into 1-dimensional real interval by constructing a feature function, and the reeb graph is obtained accordingly. Then,some critical points of Reeb graph can be detected and Reeb chords are generated. Based on the Reeb graph, the network is decomposed into a set of nicely shaped sub-networks,within each of which K feature functions will be constructed to build an index for each node. Skeleton nodes are identified based on their indice values. Next, a light-weight skeleton node connecting and refining algorithm is proposed to extract a multi-resolution skeleton. Finally, based on the established skeleton, a load-balanced and delivery-guarrented routing protocol with small stretch ratio is proposed.

传感器网络的关键理论与技术是当前国际研究热点，复杂的网络拓扑结构给传感器网络的各种应用提出了挑战，需要在拓扑特征提取上展开深入研究。骨架是传感器网络几何和拓扑特征的重要描述子，对于其他几何和拓扑特征的识别，以及传感器网络的各种应用具有重要的理论和实践意义。本项目拟研究在网络边界信息未知的前提下，基于连接信息的二维/三维传感器网络的骨架提取。首先，通过构建特征函数，将网络节点映射至一维实数空间，建立传感器网络的Reeb图；其次，在Reeb图中识别关键点和Reeb弦，进而将网络分解成若干形状规则的子网络，在每个子网络中构建K个特征函数，并设计指标来识别骨架节点；第三，设计轻量级的骨架节点连接与优化算法，提取多尺度网络骨架；最后，设计一种负载均衡、100%路由成功率以及低伸展率(Stretch Ratio)的路由算法，并通过仿真实验评价算法性能。

传感器网络几何和拓扑特征提取是无线传感器网络研究的关键技术之一，作为网络几何和拓扑特征的重要描述子，骨架信息可用于高性能的网络协议设计，进而延长网络生命周期。然而，现有骨架提取算法对网络边界噪声十分敏感，且主要针对二维传感器网络的特点而设计，无法直接应用于三维传感器网络中。此外，三维物体具有面骨架与线骨架两种表现形式，但没有任何文献提出三维传感器网络线骨架的定义及提取方法。尽管有学者提出了面骨架提取算法，但受通信成本、对网络密度要求的苛刻性和对噪声敏感等特点，无法在实践中进行大规模应用。..本项目主要研究二维／三维传感器网络的骨架提取及其应用。首先，研究在二维传感器网络中，当网络边界信息部分可知时，基于这些边界点建立起网络距离变换。利用节点的距离变换，识别骨架点并将之连接成为骨架线；其次，研究不依赖于边界信息的骨架提取算法，利用节点间的连接信息，构造指标来反映节点的中心度，进而提取骨架；第三，研究传感器网络的近似凸分解问题，并将凸分解结果应用于网络定位；第四，提出二维／三维传感器网络线骨架的统一定义，并设计出一种统一框架，同时提取二维／三维传感器网络的线骨架；第五，提出一种稳健的三维传感器网络面骨架提取算法，并利用面骨架信息来识别网络边界框，提高基于地理哈希表的数据存储协议性能；最后，在三维传感器网络边界信息未知时，提出算法构建特征函数，并构造出网络Reeb图，在此基础上提取网络线骨架。结合网络Reeb图与线骨架，设计两种负载均衡的数据存储与检索协议。..项目研究表明：1）骨架在提取传感器网络的其他拓扑特征(如凸分解、 网络边界等)方面具有重大价值；2）在三维传感器网络中，基于线骨架的路由协议，可以大幅提升网络负载均衡与路由成功率；3）三维传感器网络的面骨架，有助于计算出不规则网络边界框，进而提升GHT协议性能；4）作为网络的另一重要架构，Reeb图可用来提取网络线骨架，及高性能的数据存储与检索协议。总之，本项目的研究成果可为传感器网络的各种应用提供重要的理论依据。