基于图论的区域覆盖与点集覆盖问题研究

发布时间：2017-12-09 00:20

  本文关键词：基于图论的区域覆盖与点集覆盖问题研究

  更多相关文章： 点集覆盖问题 区域覆盖问题 连通支配集 代数拓扑 圆packing

【摘要】：区域覆盖与点集覆盖问题是两个计算几何研究的基本问题,目前在实际中主要应用场景为无线传感器网络、生物网络等空间中分布的网络。最早被研究的区域覆盖问题是艺术画廊问题,主要研究如何部署最少数量的摄像机来覆盖整个画廊。高效的覆盖算法能够节约能耗或者延长网络生存时间。而无线网络在许多领域有着良好的应用前景,比如,国家安全、军事侦察、医疗卫生和环境监测等,因此研究高效的覆盖算法有着重要的实际意义。从分类的角度来讲,目前主要的各种网络覆盖问题有点集覆盖问题、区域覆盖问题、目标覆盖问题与路径覆盖问题。从目标来讲,覆盖问题主要研究如何用最少的节点来保证整个区域的覆盖,或者在保证整个区域被覆盖的前提下最大化整个网络生存时间。而研究覆盖问题采用的方法经常为一些计算几何和图论的方法,比如、Voronoi图和Delaunay三角剖分,和经典代数拓扑方法,连通支配集,整数规划。由于覆盖问题研究通常涉及非常经典的数学问题,比如,区域覆盖算法中检测是否存在空洞和自动控制中的一致性问题都可以采用高维拉普拉斯矩阵来进行建模,因此,覆盖问题吸引了不同学科,不同领域的大量研究人员进行理论和应用研究。本文的主要贡献如下：1.给出并证明了2维与3维空间中基于连通信息的区域覆盖规则。2.提出了有着较优近似度的DGB和BGB中连通支配集构建算法。本文详细阐述了区域覆盖问题、点集覆盖问题、目标覆盖问题与路径覆盖问题的国内外研究现状。本文分析了各种覆盖问题在算法设计目标和模型上的联系和区别,给出了一些解决覆盖问题常用的方法,比如线性规划、连通支配集问题。对于区域覆盖问题,本文首先给出了研究该问题的代数拓扑方法描述。具体研究方法包括单纯复形、混合拉普拉斯矩阵、环空间理论。然后针对空洞的检测,本文给出了在2维空间和3维空间中的一些具体实例。本文首次给出了3维空间中仅基于连通信息的区域覆盖规则,该规则对于设计在3维空间中的区域覆盖算法有着重要的理论指导意义。本文证明了当传感比为γ≤(?)其中n为2一单形的数目,一个2维闭链的内部区域被完全覆盖。由于高维空间中对于闭链群的研究难以应用求最短路等环空间中常用的图论方法,高维空间中闭链群没有环空间中的一些基本性质,因此,本文提出了一些和该问题相关的开放性问题。对于点集覆盖问题,本文提出了有着较优近似度DGB和BGB中连通支配集构建算法。首先,在2维空间中,本文采用经典圆packing问题方法详细的分析了DGB模型下最大独立集的上界,在DGB中,当最大通信半径与最小通信半径的比值为(1,1.152],(1.152,1.307],(1.307,1.407],(1.407,1.462],(1.462,1.515],(1.515,1.618],(1.618,1.932]时,最大独立集的上界为6opt+1,7opt+1,8opt+1,9opt+1,10opt+1,11opt+1,16.7778opt+1.2222,其中opt表示连通支配集问题的最优解。基于此,改进了基于最大独立集的两阶段连通支配集构建算法近似度。最后,本文将相应的分析方法拓展到3维空间,通过经典球packing问题方法,给出了BGB模型下最大独立集的上界。也就是说,本文给出的方法不仅适用于2维空间,也可推广至于3维空间中分布的网络。
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前9条

1 陈峰,姚恩瑜;箱覆盖问题的半定松驰算法[J];运筹学学报;2002年02期

2 王翰;;最大覆盖问题研究[J];科技传播;2011年22期

3 刘俊权;;移动通信信号隧道覆盖问题及解决方案[J];大众科技;2012年05期

4 吴志华;;SAT算法解决码覆盖问题之探讨[J];内江科技;2007年09期

5 徐高诚;m×n－1矩形的覆盖问题[J];数学通讯;1994年04期

6 张生;何尚录;;预算型最大覆盖问题的近似算法[J];河北大学学报(自然科学版);2008年01期

7 陆正福;洪孙焱;;密钥覆盖问题的NP完全性证明[J];云南大学学报(自然科学版);2006年03期

8 康庆德;格盘上的覆盖问题[J];自然杂志;1992年05期

9 ;[J];;年期

中国重要会议论文全文数据库 前2条

1 余立;丁海煜;刘佳;;GSM高速移动环境下的覆盖问题研究[A];2007年中国通信学会“移动增值业务与应用”学术年会论文集[C];2007年

2 黄洋;;“小灵通”技术创新与网络优化若干问题浅析[A];济宁市技术创新与可持续发展论文选编[C];2005年

中国重要报纸全文数据库 前2条

1 记者 于京玄;物料渣土覆盖问题突出[N];西安日报;2010年

2 黑龙江 郝高麟;用射频光纤拉远解决高铁弱覆盖问题(上)[N];电子报;2011年

中国博士学位论文全文数据库 前3条

1 宋志明;星座对地覆盖问题的形式化体系构建与求解算法研究[D];中国地质大学;2015年

2 白森;基于图论的区域覆盖与点集覆盖问题研究[D];吉林大学;2016年

3 张宗祥;基于服务质量的逐渐覆盖问题研究[D];华中科技大学;2013年

中国硕士学位论文全文数据库 前10条

1 唐浩龙;一维捆绑式箱子覆盖问题[D];云南大学;2016年

2 刘闯;无线传感器网络中扫描覆盖问题研究[D];哈尔滨工业大学;2016年

3 王利民;最小权和的连通顶点P_3覆盖问题[D];南京师范大学;2015年

4 李文军;覆盖问题的参数算法研究[D];中南大学;2010年

5 李，

本文编号：1268405