本书中介绍了无线通讯网络中的在线频率分配问题。这是一类资源优化配置问题，在包括数学、计算机、通信等多个学科中都受到了广泛而深入的研究。对于频率分配问题，本书介绍了两个模型：Non-Release模型 和Release模型，针对这两个模型，着重研究了线性网络和蜂窝网络中的在线频率分配。针对大规模无线网络，探讨了根据局部信息进行计算的分布式频率分配方案。*后，本书中还介绍了无线蜂窝网络中的呼叫控制问题，当无线带宽给定时，如何充分利用有限的带宽尽可能多的满足用户的通信请求。本书可供高等院校计算机、运筹等专业高年级及研究生阅读，也可供相关专业和工程技术领域中的研究人员参考阅读。

频率分配可以视为一个具有极强实际应用价值的传统问题。从实际应用来看， 频率分配是无线通信的关键技术， 而后者又是我们日常工作、生活的一个重要基石。没有无线网络，人们的生活将退回到二十年前。从基础理论来看， 频率分配的基本模型和算法可以追溯到1852 年前由Francis Guthr i e 提出的地图着色问题。如果对平面地图中的区域进行染色， 并且保证相邻区域使用不同的颜色， 他发现只要用4 种颜色就够了。这就是著名的 四色问题。近年来， 无论在工程应用还是理论研究中， 频率分配都是一个核心问题。无线通信网络通常将整个覆盖区域划分为很多小区， 每个小区通过一个基站与小区内的移动用户进行无线信号的通信。当一个通信请求出现在某小区时， 无线通信系统必须立即为其分配一个频率。为了避免干扰， 同一小区内或者两个相邻小区内的通话不能被分配同一个频率。
　　由于频率是非常稀缺的资源， 因而， 频率分配问题中最重要的研究方向是资源优化配置。一个最常见的目标是使用最少的频率资源来满足所有的通信请求； 与之对应， 另一个目标是当给定频率带宽时， 如何尽可能多地满足通信请求。此外， 当网络规模非常大时， 如果处理一个通信请求需要调用整个无线网络的结构信息，信息获取将十分复杂， 计算量巨大， 如何利用最少的计算资源来处理通信请求， 也是近年来被关注的一个热点研究方向。在实际场景中， 通信请求随时间不断到达， 每一个通信请求的到达时间和到达位置是不可提前预知的。这为频率分配方案的设计造成了极大的困难， 需要在不知道未来信息的情况下， 对当前到达的通信请求做出决策。更麻烦的是， 当前的决策可能导致处理未来请求的性能很差。因此， 设计在线频率分配方案时， 必须平衡当前性能及未来可能的情况。本书主要内容为张涌博士近年来针对在线频率分配问题获得的一系列研究成果：针对Non-Release 模型和Release 模型，研究和分析了多类在线频率分配模型和算法； 提出并证明了蜂窝网络中的最优在线频率分配方案； 研究了大规模网络中的局部分布式频率分配算法。
　　本书由张涌博士与花强教授共同撰写及整理， 负责全书大纲及内容的拟定并定稿。本书中相关问题的研究得到了香港大学计算机系钱玉麟教授领导的算法理论研究组中老师的大力协助。本书得到了国家自然科学基金重点项目 多语言大数据环境下的复杂网络行为分析、预测和干预（ 项目编号： 61433012）， 以及深圳市基础研究项目 大规模图中的连通性及子图挖掘研究（ 项目编号：JCYJ20160229195940462） 的支持

2007年博士毕业于复旦大学计算机系，之后分别于德国柏林工业大学数学系和香港大学计算机系进行博士后研究。现任中国科学院深圳先进技术研究院副研究员。

第1 章 引言····················································· 1
1.1 无线通信发展史················································ 2
1.2 移动通信流程··················································· 6
1.3 移动通信中的频率分配问题·································· 6
1.4 在线算法性能分析············································ 12
1.5 相关研究结果·················································· 13
1.6 本书的结构····················································· 17
第2 章 线性网络中的在线频率分配······················· 21
2.1 线性网络概述·················································· 21
2.2 贪心算法分析·················································· 22
2.3 线性网络在线频率分配的Non- Release 模型·············· 27
2.4 线性网络在线频率分配的Release 模型···················· 35
第3 章 蜂窝网络中在线频率分配的贪心算法············ 43
3.1 贪心算法概述·················································· 43
3.2 Non-Release 模型下的贪心算法分析························ 44
3.3 Release 模型下的贪心算法分析····························· 58
第4 章 算法Hybrid 在蜂窝网络中的性能分析··········· 63
4.1 概述····························································· 63
4.2 绝对竞争比····················································· 63
4.3 渐进竞争比····················································· 67
第5 章 蜂窝网络中在线频率分配的Release 模型······ 77
第6 章 蜂窝网络在线频率分配的分布式算法············ 87
6.1 分布式算法介绍··············································· 87
6.2 必要的概念····················································· 89
6.3 无三角形蜂窝网络中的分布式频率分配··················· 91
6.4 蜂窝网络中的分布式在线频率分配························· 97
第7 章 蜂窝网络中的在线呼叫控制问题················· 101
7.1 呼叫控制（ Call Control） 问题介绍·······················101
7.2 相关研究结果·················································103
7.3 在线呼叫控制的性能衡量···································103
7.4 在线呼叫控制的性能下界···································104
7.5 在线呼叫控制的频率分配算法·····························106
参考文献························································ 112