Theoretical Treatment of Target Coverage in Wireless Sensor Networks

来源 :计算机科学技术学报 | 被引量 : 0次 | 上传用户:yexj585
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
The target coverage is an important yet challenging problem in wireless sensor networks, especially when both coverage and energy constraints should be taken into account. Due to its nonlinear nature, previous studies of this problem have mainly focused on heuristic algorithms; the theoretical bound remains unknown. Moreover, the most popular method used in the previous literature, I.e., discretization of continuous time, has yet to be justified. This paper fills in these gaps with two theoretical results. The first one is a formal justification for the method. We use a simple example to illustrate the procedure of transforming a solution in time domain into a corresponding solution in the pattern domain with the same network lifetime and obtain two key observations. After that, we formally prove these two observations and use them as the basis to justify the method. The second result is an algorithm that can guarantee the network lifetime to be at least (1 -ε) of the optimal network lifetime, where ε can be made arbitrarily small depending on the required precision. The algorithm is based on the column generation (CG) theory, which decomposes the original problem into two sub-problems and iteratively solves them in a way that approaches the optimal solution. Moreover, we developed several constructive approaches to further optimize the algorithm. Numerical results verify the efficiency of our CG-based algorithm.
其他文献
2002年至2005年,用农药残留快速检测法-酶抑制法对玉溪市21个主要蔬菜集贸市场上市蔬菜和部分蔬菜生产基地生产的蔬菜共22 949个样品进行检测.结果表明,在抽检蔬菜样品中农药
为了对煤与瓦斯突出进行实时监测,在研究中采用了数据来源丰富的瓦斯监控数据.在对新安煤田煤的瓦斯解吸特征实验室研究的基础上,采用新安煤田始突瓦斯含量和瓦斯涌出的分源
This study investigates the correlation between PM10 and meteorological factors such as wind speed,atmospheric visibility,dew point,relative humidity,and ambien
针对露天矿生产需要,建立了基于挖掘机生产能力最大化目标的单斗-卡车间断工艺采掘带宽度优化模型,并进行了实例研究.根据单斗-卡车工艺端工作面生产特点,建立了挖掘机生产能
阜新地区处于辽宁西部,十年九旱的气候特点,严重束缚着该地区经济的可持续发展.因此研究该地区的水文气象资源特点,对于指导该地区的工农业生产具有重大的现实意义.
A novel inorganic-organic hybrid borate,[Al2(fum)(H3BO3)(OH)4]n·n(H3BO3)(1,H2fum=fumaric acid),has been synthesized and characterized by single-crystal X-ray d
The development of new drilling methods is important for the exploration and production of oil fields. The pulsed jet is a drilling technology of high potential
Compared with gentle dip long-wall caving, the length of a working face in fully-mechanized top-coal caving for extremely steep and thick seams is short, while
我们从已有的史料来发掘对我们现在的建设有用的思想和史实,譬如我国古代的司法制度,它是什么性质?如何适应我国古代中央集权体制,以及指导其思想又是什么,本文对此作了简要
目的 应用向量血流图(vector flow mapping,VFM)对比观察二叶式人工机械瓣置换术后心室流场变化规律.方法 30例正常志愿者为对照组,30例二尖瓣重度狭窄行二叶式人工机械瓣置