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

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

本项目针对无线网络中的在线优化问题进行研究。随着无线网络技术的飞速发展，无线网络中的优化问题成为相关领域内的研究重点之一。其核心问题是充分利用有限资源，设计代价小、性能高的算法来满足用户请求或者得到需要的信息。项目研究期间，项目组成员分别针对着色，节点分配，装箱，定价等问题的在线模型展开了研究，取得了一定的进展，受到了国际上相关领域内专家的关注。通过研究，我们对无线网络中的在线优化问题有了更深刻的理解，通过对自身性质的刻画和分析，我们设计出了高性能的在线优化算法来解决这些问题。受项目资助，在国际高水平期刊上发表SCI论文21篇，在国际高水平会议上发表EI论文17篇，此外，8篇文章已经整理完稿，其中4篇处于投稿后的审理阶段。