无线传感器网络中的K覆盖问题

论文摘要

近年来,微电子技术的新发展使得建立密集的,价格低廉的无线传感器网络成为可能。传感器网络可以应用到很多方面。无线传感器网络是由大量的,任意配置的传感器节点所组成。因为所有的传感器节点的能量都是由电池提供的,所以节点工作时使用的能量非常有限。在传感器网络中,节省能量是主要问题之一。本文把区域覆盖问题近似的看成点覆盖问题。为了延长传感器网络的使用寿命,通常使得最少的传感器节点处于活跃状态来节省能量。本文将K覆盖问题归结为求解最小交叉集合H并给出了新的近似算法。首先,我们利用可调的感应半径来达到完全K覆盖,给出了两类排序的思想。其次,设计了一种寻找H中元素的算法。算法根据文中提到的两类优先权,把最有价值的传感器节点和必须活跃的传感器节点加入到交叉集合H中,达到节约能量的目的。在此基础上给出了一种新的K覆盖算法。本文算法的时间复杂度比原算法更优,复杂度为O(nlogn)。仿真结果验证了理论上的分析。

论文目录

• Abstract
• 摘要
• 1.INTRODUCTION
• 1.1 Background
• 1.2 Related Work
• 1.3 Basic Theory
• 1.4 Relative Article
• 1.5 Article Structure
• 2.PRELIMINARIE
• 2.1 Primary Theory Description
• 2.2 A Usual Method to Solve Connectivity
• 3.A NEW K-COVERAGE ALGORITHM
• 3.1 RKC Algorithm
• 3.2 NKC Algorithm
• 3.2.1 Arrangement
• 3.2.2 A New K-finder algorithm
• 3.3 The NKC Algorithm Process
• 3.4 The NKC Algorithm Complexity
• 4.PERFORMANCE EVALUATION
• 4.1 Simulation by Varying Initial Sensing Range R
• 4.2 Simulation by Varying Coverage Degree K
• 4.3 Simulation by Varying Sensors Number
• 4.4 Simulation Contrast
• 5.CONCLUSIONS
• REFERENCES
• ACKNOWLEDGEMENT