基于正三角形剖分的传感器网络快速k-覆盖判定算法研究

论文编号:TX250  论文字数:14646,页数:39 有开题报告，任务书

摘    要

 传感器网络综合了传感器技术、嵌入式技术、分布式信息处理技术和无线通信技术，能够协作地实时监测、感知和采集各种环境或监测对象的信息，并对其进行处理，传送到这些信息的用户。传感器网络是计算机科学技术的一个新的研究领域。覆盖问题又是传感器网络研究中的一个基础课题。如何判定某个感兴趣的区域是否被一组给定的传感器节点覆盖, 在传感器网络的很多应用领域中具有重要意义。本论文提出了一种传感器网络中基于正三角形剖分的k-覆盖快速判定算ETP-RCDA(Equilateral Triangle Partition based Rapid k-Coverage Decision Algorithm)和最大k-覆盖问题的求解算法，TR-RCDA首先把感兴趣的区域剖分为正三角形区域，从而将复杂的区域覆盖问题转化为简单的正三角形区域覆盖问题。理论分析与仿真实验表明，针对具有n个节点的传感器网络，新算法的计算时间复杂度为O(n)，远低于已有算法O(nlogn) 的计算时间复杂度。

关键词：传感器网络，k-覆盖问题，剖分，算法

Researches on Cube Partition based Rapid 3D k-Coverage Decision Algorithm for Sensor Networks

Abstract

 Integrated with sensing techniques, embedded techniques, distributed Information Processing techniques and wireless communication techniques, sensor networks can be used for monitoring, sensing, collecting and processing information of monitored objects and transferring the processed information to users. Sensor network is a new research area of computer science and technology and has a wide application future. Coverage problem is a fundamental issue in the researches of sensor networks. It is important to determine whether a region of interest is sufficiently covered by a given set of sensors in lots of monitoring applications of sensor networks. An Equilateral Triangle Partition based Rapid k-Coverage Decision Algorithm is proposed, in which the region of interest is partitioned into triangles firstly, and then the complex area coverage problem is transformed into simple triangle coverage problem. Theoretical analysis and simulation results show that, for sensor networks with n different sensors, the new algorithm can solve the k-coverage problem correctly for any given region of interest with time costs of O(n) only, which is far below the time costs O(nlogn) of previously well-known algorithm.

Key Words: Sensor networks, k-coverage problem, Partition, Algorithm

目    录
1. 绪论 1
1.1 课题研究背景与意义 1
1.2 国内外研究现状 2
1.3论文结构和研究内容 3
1.4 小结 3
2. 传感器网络概述 4
2.1 传感器网络简介 4
 2.1.1 传感器网络的概念 4
 2.1.2 传感器网络的特点 5
 2.1.3 传感器网络的核心技术 6
2.2 传感器网络的应用 6
 2.2.1 环境的检测和保护 6
 2.2.2 医疗护理 7
 2.2.3 军事领域 7
 2.2.4 其他应用 7
2.3传感器网络面临的挑战 8
2.4小结 9
3. 传感器网络中的覆盖问题 10
3.1 配置方式的分类 10
 3.1.1 确定性覆盖 10
 3.1.2 随机覆盖 10
3.2 应用属性的分类 10
 3.2.1 节能覆盖 11
 3.2.2 栅栏覆盖 11
 3.2.3 连通性覆盖 11
 3.2.4 目标定位覆盖 12
3.3 小结 12
4. 基于正三角形剖分的快速k-覆盖判定算法 13
4.1 基本概念 13
4.2快速k-覆盖判定算法ETR-RCDA 14
4.3算法性能分析 15
4.4小结 16
5. 模拟实验的设计和实现 17
5.1 模拟环境 17
5.2 主要界面 17
 5.2.1 用户输入界面 17
 5.2.2 生成网络界面 18
 5.2.3 选定区域轮廓界面 20
 5.2.4 正三角形剖分界面 21
 5.2.5 去冗余网络界面 21
5.3模拟实验性能分析 22
5.4小结 22
结    论 23
致    谢 24
参考文献 25
附录A 主要源程序 27