在线图着色与网络发现-无线网络中两类优化问题的研究

项目名称： 在线图着色与网络发现-无线网络中两类优化问题的研究

项目编号： No.11171086

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 数理科学和化学

项目作者： 张涌

作者单位： 河北大学

项目金额： 45万元

中文摘要： 随着无线网络技术的飞速发展，无线网络中的优化问题成为相关领域内的研究重点之一。其核心问题是充分利用有限资源，设计代价小、性能高的算法来满足用户请求或者得到需要的信息。在无线网络中，无线频率是最重要而又非常稀缺的资源；此外，在很多实践中，需要迅速低成本的获取某些网络拓扑信息。在本项目中，我们对无线网络中的两类优化问题进行研究，包括在线图着色与网络发现。研究目标是探索图着色与网络发现问题的在线模型，揭示所研究网络具有的特有性质，根据这些性质设计高性能的在线算法，并从理论上给出算法的性能保证，最终建立一套针对不同类别优化问题的理论模型以及高性能的解决方案。具体研究内容包括：设计在线算法，使用尽可能少的颜色满足尽可能多的请求，以及使用尽可能少的查询次数得到我们需要的网络参数。本项目为无线网络中的具体实践提供理论依据以及指导性的改进方案，对提高我国在相关领域内的理论基础与应用水平有着重要意义。

中文关键词： 在线算法；竞争比分析；图着色；网络发现；

英文摘要：

英文关键词： Online algorithms；competitive analysis；graph coloring；network discovery；