检索结果-南通市图书馆

传感器与微系统 2011年第1期30卷 70-72,93页

作者：毛健吴鸿雁无锡科技职业学院江苏无锡214028

针对已有的三维无线传感器网络路由协议均将三维问题转换到二维平面上解决,没有充分利用三维空间的特点,提出了一种基于地理信息的三维无线传感器网络贪婪地理路由(GGR)协议。该协议在通常状况下采用贪婪转发算法,针对基于地理信息的贪... 详细信息

针对已有的三维无线传感器网络路由协议均将三维问题转换到二维平面上解决,没有充分利用三维空间的特点,提出了一种基于地理信息的三维无线传感器网络贪婪地理路由(GGR)协议。该协议在通常状况下采用贪婪转发算法,针对基于地理信息的贪婪算法中易出现的路由空洞问题,给出一种三维滚动球边界遍历算法。实验结果表明:该协议具有较高的路由成功率,路由跳数也得到优化,尤其是在节点密度较低的情况下体现出较强的优势。

关键词：三维无线传感器网络地理路由协议贪婪转发算法路由空洞问题单位球图

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

异质无线网络的虚拟骨干构建研究

异质无线网络的虚拟骨干构建研究

引用

作者：易梦广西大学

学位级别：硕士

在无线网络中,虚拟骨干的大小是衡量网络质量的一个重要因素,即虚拟骨干越小,网络路由开销越小。因此,在研究上,常常将最小虚拟骨干网的构建问题抽象为图论中的最小连通控制集求解问题。求解最小连通控制集已经被证明是一个NP-难问题,... 详细信息

在无线网络中,虚拟骨干的大小是衡量网络质量的一个重要因素,即虚拟骨干越小,网络路由开销越小。因此,在研究上,常常将最小虚拟骨干网的构建问题抽象为图论中的最小连通控制集求解问题。求解最小连通控制集已经被证明是一个NP-难问题,一般可通过设计近似算法进行求解,而决定近似比的一个关键参数是极大独立集的上界。此外,由于均质无线网络中每个传感器所对应的节点都具有相同的传输半径,这显然并不符合现实中的大部分情况,因此具有不同传输半径的异质无线网络研究更具有现实意义。针对以上问题,本文从单位球图模型和有向图模型两个方面对无线网络中虚拟骨干网展开深入研究,其主要创新性研究包含以下三个方面:（1）在单位球图模型下,将极大独立集的上界优化到了12.5385,并提出一个近似算法,算法产生的连通控制集的近似比为12.5385+ln11;（2）将三维均质无线网络虚拟骨干网研究中的几何方法推广到三维异质无线网络的研究中,提出了一个强连通控制吸收集构造算法;（3）进一步拓展到具有路由保证的异质无线网络虚拟骨干研究,提出了两个具有路由保证的强连通控制吸收集构造算法。此外,本文通过仿真实验验证了算法的可行性,同时对比实验分析结果说明,本文提出的算法比已有的算法性能更好。

关键词：无线网络虚拟骨干单位球图有向图连通控制集强连通控制吸收集

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

最小权和的连通顶点P3覆盖问题

最小权和的连通顶点P3覆盖问题

引用

作者：王利民南京师范大学

学位级别：硕士

图的顶点覆盖问题是图论研究中的一个热点问题.给定一个简单图G=(E E),选取一个顶点子集S(?)V,如果图中的每一条边至少有一个顶点在集合S中,则称S是图G的一个顶点覆盖集.当图中的每一个顶点v∈V,赋予非负权值w(v),此时就是寻找一个顶点... 详细信息

图的顶点覆盖问题是图论研究中的一个热点问题.给定一个简单图G=(E E),选取一个顶点子集S(?)V,如果图中的每一条边至少有一个顶点在集合S中,则称S是图G的一个顶点覆盖集.当图中的每一个顶点v∈V,赋予非负权值w(v),此时就是寻找一个顶点权和最小的顶点覆盖.这个问题是顶点删除问题的一个特殊类.顶点删除问题就是寻找一个最小权和的顶点子集使得从图上删除这些顶点后,剩下的顶点导出的子图满足一个给定的特征.例如：顶点反馈集问题就是寻找一个最小权和的顶点子集S(?)V(G)使得V-S导出的子图G[V一S]不包含圈.受到上述顶点删除问题的启发,作为推广介绍最小权和的连通顶点Pk覆盖问题：寻找一个最小权和的顶点子集S(?)V(G)使得V-S导出的子图G[V-S]不包含Pk路,且S导出的子图G[S]是连通的,其中Pk是指有k个顶点的路.在本论文中主要考虑k=3的情况.对于顶点P3覆盖问题,已经有许多比较好的结果Bostjan (2011)证明最小顶点Pk(k是整数,k≥2)覆盖问题在一般图上是NP-完全的,Tu和Zhou(2011)利用原始对偶近似算法给出最小权和的顶点P3覆盖问题的一个2因子近似解.考虑到连通性,Liu(2013)等人给出了最小的连通顶点Pk覆盖问题在单位圆盘图上的一个近似解.但对于顶点加权和连通性的情况还没有结果,为此本文在这两个条件下考虑顶点P3覆盖问题在一些特殊图上的近似算法.本文共有四章内容,主要是研究几类特殊图的最小权和的连通顶点P3覆盖问题的多项式时间近似格式.第一章给出了文章用到的相关符号,基本概念以及顶点Pk覆盖问题的应用背景和已有的结论,并进一步阐述本文的方法和主要结果.在第二章中,首先证明这个问题在网格图上的NP-复杂性,其次得出这个问题在单位圆盘图上的一个常因子近似解,最后在假设最小权和的连通顶点P3覆盖问题是c-局部的和图的最小度是2的条件下,本文证明在单位圆盘图上可以求得这个问题的一个多项式时间近似格式.在第三章中,在最小权和的连通顶点P3覆盖问题是弱c-局部的和图的顶点权值是光滑性的条件下,本文证明在单位球图上可以求得这个问题的一个多项式时间近似格式.文章的最后,给出一些可以进一步探讨的问题.

关键词：多项式时间近似格式单位圆盘图单位球图顶点P3覆盖 c-局部问题光滑权值

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Distributed Graph Algorithms for Spectrum Allocation in Wireless Networks

Distributed Graph Algorithms for Spectrum Allocation in Wire...

引用

作者：施娅林南京师范大学

学位级别：硕士

频谱分配在无线自组织网络中是一个比较难的热点问题.有效的频谱分配方法是提高无线网络的服务质量和性能的一个关键因素.本文考虑这样的频谱分配问题：在某个区域如何分配最少的频谱块,并确保在该区域上随机的k个位置能得到同时服务.... 详细信息

频谱分配在无线自组织网络中是一个比较难的热点问题.有效的频谱分配方法是提高无线网络的服务质量和性能的一个关键因素.本文考虑这样的频谱分配问题：在某个区域如何分配最少的频谱块,并确保在该区域上随机的k个位置能得到同时服务.这种频谱分配问题的解决方法采用的是最小k-罗马控制集.对于在无线自组织网络中的频谱分配问题,我们提出两种分布式算法.一个是分布式的6k-近似算法,这个算法使得在单位球图上随机的k个位置能得到同时服务,并且近似度达到6k.另一个分布式算法确保在增长有界图上随机的任意两个位置能同时得到服务,并且近似度为(1+ε).我们还进一步进行了仿真实验并且分析了这些算法.

关键词：分布式近似算法频谱分配 κ-罗马控制集单位球图增长有界图

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：