基于正三角形剖分的傳感器網絡快速k-覆蓋判定算法研究

電子通信論文編號:TX250  論文字數:14646,頁數:39 有開題報告，任務書

目    錄
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

摘    要

 傳感器網絡綜合了傳感器技術、嵌入式技術、分布式信息處理技術和無線通信技術，能夠協作地實時監測、感知和采集各種環境或監測對象的信息，并對其進行處理，傳送到這些信息的用戶。傳感器網絡是計算機科學技術的一個新的研究領域。覆蓋問題又是傳感器網絡研究中的一個基礎課題。如何判定某個感興趣的區域是否被一組給定的傳感器節點覆蓋, 在傳感器網絡的很多應用領域中具有重要意義。本論文提出了一種傳感器網絡中基于正三角形剖分的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