基于正三角形剖分的傳感器網(wǎng)絡(luò)快速k-覆蓋判定算法研究

論文編號:TX250  論文字?jǐn)?shù):14646,頁數(shù):39 有開題報告，任務(wù)書

摘    要

 傳感器網(wǎng)絡(luò)綜合了傳感器技術(shù)、嵌入式技術(shù)、分布式信息處理技術(shù)和無線通信技術(shù)，能夠協(xié)作地實時監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息，并對其進(jìn)行處理，傳送到這些信息的用戶。傳感器網(wǎng)絡(luò)是計算機(jī)科學(xué)技術(shù)的一個新的研究領(lǐng)域。覆蓋問題又是傳感器網(wǎng)絡(luò)研究中的一個基礎(chǔ)課題。如何判定某個感興趣的區(qū)域是否被一組給定的傳感器節(jié)點覆蓋, 在傳感器網(wǎng)絡(luò)的很多應(yīng)用領(lǐng)域中具有重要意義。本論文提出了一種傳感器網(wǎng)絡(luò)中基于正三角形剖分的k-覆蓋快速判定算ETP-RCDA(Equilateral Triangle Partition based Rapid k-Coverage Decision Algorithm)和最大k-覆蓋問題的求解算法，TR-RCDA首先把感興趣的區(qū)域剖分為正三角形區(qū)域，從而將復(fù)雜的區(qū)域覆蓋問題轉(zhuǎn)化為簡單的正三角形區(qū)域覆蓋問題。理論分析與仿真實驗表明，針對具有n個節(jié)點的傳感器網(wǎng)絡(luò)，新算法的計算時間復(fù)雜度為O(n)，遠(yuǎn)低于已有算法O(nlogn) 的計算時間復(fù)雜度。

關(guān)鍵詞：傳感器網(wǎng)絡(luò)，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 國內(nèi)外研究現(xiàn)狀 2
1.3論文結(jié)構(gòu)和研究內(nèi)容 3
1.4 小結(jié) 3
2. 傳感器網(wǎng)絡(luò)概述 4
2.1 傳感器網(wǎng)絡(luò)簡介 4
 2.1.1 傳感器網(wǎng)絡(luò)的概念 4
 2.1.2 傳感器網(wǎng)絡(luò)的特點 5
 2.1.3 傳感器網(wǎng)絡(luò)的核心技術(shù) 6
2.2 傳感器網(wǎng)絡(luò)的應(yīng)用 6
 2.2.1 環(huán)境的檢測和保護(hù) 6
 2.2.2 醫(yī)療護(hù)理 7
 2.2.3 軍事領(lǐng)域 7
 2.2.4 其他應(yīng)用 7
2.3傳感器網(wǎng)絡(luò)面臨的挑戰(zhàn) 8
2.4小結(jié) 9
3. 傳感器網(wǎng)絡(luò)中的覆蓋問題 10
3.1 配置方式的分類 10
 3.1.1 確定性覆蓋 10
 3.1.2 隨機(jī)覆蓋 10
3.2 應(yīng)用屬性的分類 10
 3.2.1 節(jié)能覆蓋 11
 3.2.2 柵欄覆蓋 11
 3.2.3 連通性覆蓋 11
 3.2.4 目標(biāo)定位覆蓋 12
3.3 小結(jié) 12
4. 基于正三角形剖分的快速k-覆蓋判定算法 13
4.1 基本概念 13
4.2快速k-覆蓋判定算法ETR-RCDA 14
4.3算法性能分析 15
4.4小結(jié) 16
5. 模擬實驗的設(shè)計和實現(xiàn) 17
5.1 模擬環(huán)境 17
5.2 主要界面 17
 5.2.1 用戶輸入界面 17
 5.2.2 生成網(wǎng)絡(luò)界面 18
 5.2.3 選定區(qū)域輪廓界面 20
 5.2.4 正三角形剖分界面 21
 5.2.5 去冗余網(wǎng)絡(luò)界面 21
5.3模擬實驗性能分析 22
5.4小結(jié) 22
結(jié)    論 23
致    謝 24
參考文獻(xiàn) 25
附錄A 主要源程序 27