无线传感器网络拓扑中连通支配集的研究

来源 :苏州大学 | 被引量 : 0次 | 上传用户:snoopyfeile123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
无线传感器网络的一个核心问题是拓扑结构的构建。近年来,基于连通支配集及其变型的虚拟骨干网络结构受到广泛的研究,它们对改善网络路由性能,延长网络生存时间具有重要意义,并能为网络中移动节点的导航提供有效的追踪信息。然而在单位圆盘图的网络模型中计算最小连通支配集、其变型:-有效连通支配集、最小顶点覆盖集等问题都是NP-难的,因此研究者们大多设计多项式时间算法在图中寻找相应问题的近似解。本文根据研究现状和已有研究方法,首先在单位圆盘图中提出一个(3,2)-有效连通支配集的近似算法。对任意给定充分小的>0,算法在网络中使用网格划分和平移策略,计算出一个近似因子与有关的(3,2)-有效连通支配集。我们证明了该算法的正确性且其时间复杂度为多项式级的。其次,在顶点度有限的有界增长图中,当缺乏网络图几何表达时,本文分别对最小顶点覆盖和最小权顶点覆盖问题提出了近似因子为(1+)的多项式时间近似算法,其中>0。我们证明了相应算法的正确性且其时间复杂度为多项式级的。最后,本文通过-有效连通支配集为无线传感器网络中的移动节点构造一路径规划结构,并依据追踪该结构中作为临时目标的静态传感器节点的方法,提出移动节点的路径规划算法。在导航中,路径规划结构不仅作为网络骨干来传输消息,还用于更新算法计算出的路径以确保其有效性,并保证该路径具有常数倍的移动开销。模拟实验表明,移动节点通过与静态传感器节点通信和追踪,可以导航至目标区域,与现有算法相比,其导航效率有较大改善。
其他文献
与国内典型的报名系统不同,跨境招生报名系统具有用户类型多、用户交流所用语言不统一、系统性能受国际出口带宽限制、系统支撑平台复杂等诸多特点,在此诸多特点下,跨境招生
高血压是严重影响我国居民身心健康的疾病,但是目前我国的医疗卫生条件并不能跟上高血压患者的就医需求,存在“看病难、看病贵”等诸多问题,因此国家大力地推进医疗信息化建
聚类是数据挖掘的主要技术之一,也是学术界研究的热点问题,并在各个领域的数据分析中起到重要作用。聚类边界的识别有助于提高聚类结果的准确性和揭示聚类所具有的特性,对它
信息技术的发展使数据得到了爆炸性的增长,这些来自互联网及生活中的数据往往存在着紧密的关联性,图作为一种广泛应用的数据结构,非常适合用来描述这些具有紧密关联性的数据,这些
随着计算机技术的不断发展,计算机软硬件系统已经深入渗透到实际生活中的各个领域,若这些系统一旦出错,将给人类带来不可承受的损失,所以,安全问题已经逐渐成为人们的重点关
近年来,中国奶牛养殖业快速发展,黑龙江省的奶牛养殖业已经具有很大的规模,且呈逐年上升趋势。多数奶牛场尚缺乏有效的监测管理机制,当奶牛在养殖场饲养过程中,出现生理异常或走失
车辆图像检索是智能交通系统的重要组成部分,车辆检索在高速公路服务区、停车场等场所以及在停车场智能管理、高速公路自动收费、道路监控、超时停车检测等方面有着非常好的应
  随着互联网的普及应用,互联网已经成为影响人们工作和生活的一种新媒介。越来越多的人们更愿意通过互联网提供的各种平台表达个人情感、表达自己对国际形势、政府政策以及
随着信息化的高速发展和客观上硬件技术的有效支撑,使得数据集中的海量数据不免存在冗余、缺失、不确定数据和不一致数据等诸多情况,这些统称为“脏数据”。人们需要从数据集中
伴随着人们生活节奏的加快和物质水平的提高,由饮食不合理所引发的身体健康问题日趋严重,最具代表性的为高血压和心脑血管疾病。这些疾病多数是由于营养物质过剩,导致钙磷产