文件类型：PDF/Adobe Acrobat 文件大小：字节
1
计算机通信网络-研究方法和研究方向
胡晓东
应用数学研究所
中国科学院数学与系统科学研究院
北京 2734信箱,北京100080
xdhu@mail.amss.ac.cn
xdhu@public.bta.net.cn
www.amt.ac.cn/member/huxiaodong/index.html
提纲
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
《Physics World》(2002年9月)刊登了有读者评选出的最美丽
的物理实验前10位的排名,其中第四位是牛顿的棱镜分解太阳
光.(随后美国《New York Times》作了简单的解释.)以前
大家都认为白光是一种纯的没有其它颜色的光(亚里士多德就
是这样认为的),而彩色光是一种不知何故发生变化的光.而
牛顿并不这样认为.
为了验证这个假设,牛顿把一面三棱镜
放在阳光下,透过三棱镜,光在墙上被
分解为不同颜色(光谱).牛顿的结论是:
正是这些红红,,橙橙,,黄黄,,绿绿,,青青,,蓝蓝,,紫紫
基础色有不同的色谱才形成了表面上颜
色单一的白色光,如果你深入地看看,
会发现白光是非常美丽的.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
在光纤通信网络中通过使用波分复用技术(WDM -Wavelength
Division Multiplexing )来充分利用巨大的带宽.一束光纤可以
同时传输多个信道(channels),只要它们使用不同的波长.
因为波长是一种有限的网络资源,所以如何充分利用有限的波
长资源,即给所需要建立的信道合理地分配波长(wavelength
assignment),以满足尽可能多的通信需求,就是光纤通信网
络中的核心问题之一.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
波长分配问题(wavelength assignment problem, WAP)
实例一个图G(V, E)和一些路(path)的集合P.
可行解w个波长恰当地分配给集合P中地所有路.
目标使得w尽可能地小.
路由和波长分配问题(Routing-WAP, RWAP)
实例一个图G(V, E)和一些点对(node-pair)的集合P.
可行解给P中的每一个点对找一条路,并且将w个波长恰当地
分配给所有的路.
目标使得w尽可能地小.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
路由算法
1
2
3
4
波长分配
1
2
3
4
2
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
12 3 4 567891011
12 3 4 567891011
贪婪的波长分配算法是最优的(M. Slusarek, 1989).
首先考虑在线性网络上的波长分配问题(WAPin bus networks,
linear array):
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
对于一般网络上的波长分配问题(WAP),通常的方法是将它
转化成一个图的顶点着色问题(Vertex-Coloring Problem): 即给定
一个图G'(V', E'), 用最少的颜色给图的所有顶点着色使得若两
个相邻的顶点着有不同的颜色.
构造一个辅助图G'(V', E'): V'是路的集合P, 即V'=P, 且V'中
的两个顶点有边相连当且仅当它们在G(V, E)中相应的路有公用
的边.易知 网络G(V, E)上的波长分配问题(WAP)等价于G'(V',
E')中的顶点着色问题.
定理(T. Erlebach et al, 1996; V. Kumar et al, 1997)
波长分配问题(WAP)在树(tree)或者环(ring)网络上是NP-难解的.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
定理(T. Erlebach et al, 1996)
存在一个求解树上波长分配问题的近似算法A,它所用的波长数
目wA(P)满足wA(P)≤1.1 wopt(P)+0.8,这里wopt(P)是最优算
法所需要的波长数目.
算法的基本思想是这样的:
(1)将树上波长分配问题分解转化成星图上波长分配问题;
(2) 用求解边着色问题的方法处理星图上波长分配问题;
(3) 将星图上波长分配问题的(不完全)解合并成一个树上
波长分配问题的解.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
定理(G. Wilfong et al, 1998)
存在一个求解环图上波长分配问题的近似算法A,它所用的
波长数目wA(P)满足wA(P)≤2 wopt(P)-1, 这里wopt(P)是
最优算法所需要的波长数目.
算法的基本思想是这样的:
(1) 将环在一条路的端点切开,得到一个线性网络;
(2) 用前面叙述的贪婪算法给所有的路(或者路段)分配波长;
(3) 给切断的路分配一个波长(如果它们被分配了不同的波长).
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
在计算机分布式系统中,可以把一个数据(文件)复制若干份
(replica),然后把它们放到计算机网络中不同的节点上.
一方面可以达到提高终端用户读取(read)数据文件的速度
(因为我们可以通过访问最近的网络节点来获得数据文件);
另一方面也可以增强网络的可靠性(因为某一个网络发生了
故障,我们还可以通过访问(access)其它的网络节点来获
得同样的数据文件).
3
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
然而,数据备份放置的过多,会给数据更新(write)和管理
带来麻烦(因为当我们需要修改一个数据文件的时候,我们
需要同时修改它的备份,否则,它们就不一致了).
这里的一个组合优化问题(X.-D. Hu et al, 2001)就是如何
放置有限多个复制的数据(通常不是很多),使得网络的可靠
性最高且数据访问的速度最快.
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
Write-all
终端用户终端用户
Read-only
数据备份
Majority-voting
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
等间距放置严格等间距放置集中放置
is optimal for
read-dominant.
is optimal for
majority voting.
is optimal for
write-dominant.
1. 通信网路优化问题与图论算法问题-总结
通过对光纤网络中波长分配问题的介绍,我们可以看到网络
中的一些组合优化问题的研究和解决可以借助已有的一些图
论的理论知识(特别是算法部分).
通过对数据备份的放置问题的介绍,我们可以看到网络中的
一些组合优化问题与图论的研究对象和关心的问题又都是不
同的.在通信网路优化问题的研究中,图仅仅是作为网络的
拓扑结构,而edge-link和vertex-node不仅仅是名称上的区
别,更重要的是link和node还有网络中的功能作用.
此外,网络优化问题与经典的基于网络流理论的优化问题在
研究的内容和方法上也不同,前者比后者要广泛得多.
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
2.通信网络中的基本问题和数学模型-网络优化设计问题
经典的最小Steiner树问题可以简单地叙述为:给定平
面上若干个点,如何将它们连接起来使得连线的总长
最短.注意该问题的解一定有树的结构(Steiner树),
而且可能会引入一些新的点(Steiner点).
最小Steiner 树最小生成树费玛问题
(1601-1665 )
4
2.通信网络中的基本问题和数学模型-网络优化设计问题
定理(M. R. Garey et al, 1979)
最小Steiner树问题是NP-难解的.
定理(J. B. Kruskal, 1956; R. C. Prim, 1957)
最小生成树问题是可以用贪婪算法在多项式时间求解.
定理(D.-Z. Du et al, 1992)
最小生成树与最小Steiner树权重之比不超过2/√3.
定理(S. Arora, 1996)
最小Steiner树问题有多项式时间近似方案.
2.通信网络中的基本问题和数学模型-网络优化设计问题
在通讯网络的具体设计中,我们通常还要考虑其它
实际因素/约束.例如:如果连接两点的通讯线路
太长,那么信号在传输的过程中会有衰竭.一个解
决的方法就是在长线路中放置若干个信号放大器
(amplifier).
很自然地就产生了一个组合优化的问题:就是如何
设计网络使得所需要的信号放大器最少.
2.通信网络中的基本问题和数学模型-网络优化设计问题
最少Steiner点的Steiner树问题可以简单地叙述为:
给定平面上若干个点和一个正实数R,如何将它们
连接起来使得每段线的长度不超过R且所引入的
Steiner点最少.
>>RR
近似解最优解
定理(D.-H. Chen et al, 2000)
基于最小生成树的算法的近似比是4.
2.通信网络中的基本问题和数学模型-网络优化路由问题
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2. 通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
2.通信网络中的基本问题和数学模型-网络优化路由问题
在通信服务中经常需要把信息从一个源点传到多个收点,即
多播传输(multicast),如有线电视服务(video-on-demand),
或者要把一组点联结起来(group communication),如电视/
电话会议(tele-conference).这里的核心问题之一就是如何
将这些点连接起来(routing).
网络上的Steiner树问题
实例边赋权图G(V, E)和顶点集合的一个子集S V.
可行解联接了集合S中所有点的树T(Steiner tree).
目标极小化树T上所有边的权和.
定理(M. R. Garey et al, 1979)
网络上的Steiner树问题是NP-难解的.
2.通信网络中的基本问题和数学模型-网络优化路由问题
基于最小生成树的2-近似算法(K. Bharath-Kumar et al, 1983)
2
2
2
2
2
1
1
11
1
原始问题造辅助图造生成树
2
2
1
1
1
1
回到原图
2
1
1
1
1
破圈造树
1
1
11
1
最优解
5
2.通信网络中的基本问题和数学模型-总结
一般来讲,设计求解网络优化设计问题的算法时,主要关心
的是解的性质好坏(approximation performance ratio ),主要
的研究工具是(worst-case analysis),对于算法的复杂性
(time-complexity )要求不是太高.另外,这类问题通常是
离线问题(off-line),算法是全局的(centralized).
一般来讲,设计求解网络优化路由问题的算法时,主要关心
的是解是否好用或有所改进,主要的研究工具是(simulation
study);对于算法的时间复杂性(time-complexity )要求很
高.因此,即使理论上有一些更好性能的算法,例如,网络
上的Steiner树问题有近似比为11/6算法(A. Zelikovsky,
1996),但是因为它们太过复杂,在实际中不会直接应用.
另外,这类问题通常是在线问题(on-line),算法也要求是
局部性的(local )或者是分布式的(distributed).
2. 通信网络中的基本问题和数学模型-总结
通信网络中的基本数学模型之一就是路和树,大多数问题都
是用路(path)和树(tree)来描述的.与此有关的比较典型
问题,有的可以转化成下面几个组合优化问题,在度量空间
(metric spaces)或者 网络上(networks).
极小化最小权和(最小Steiner树问题)
极小化Steiner点的个数(最少Steiner点的Steiner树问题)
极小化最小权和(在直径约束下) (S. Khuller et al, 1995)
极小化平均点到点的距离(D. W. Wall, 1980)
极小化最大的顶点度数(M. Furer et al, 1994)
极小化图的树的分解(N. G. Beck et al, 1998)
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
3. 通信网络的研究方向和研究方法-研究方向和问题
基于基站的无线通信网络(Cellular Networks):
基站的选址问题(location problem)
频率分配问题(frequence assignment problem)
信号传输功率控制问题(transmission power control problem)
通信网络的核心技术和理论是在不断更新和发展的.从传统
的为话务服务(voice)的电话网络系统,到为数据传输
(data)的基于互联网技术的计算机网络;从铜线(copper)
和微波(microwave),到光纤(fiber)和无线(wireless).
这种更新和发展是日新月异的.当前通信网络的热点领域之
一是无线通信网络(wireless networks),相关的应用基础理论
问题可以归纳为三类.
3. 通信网络的研究方向和研究方法-研究方向和问题
移动Ad Hoc网络(mobile Ad Hoc networks)是一种无线通
讯网络.它主要是由配有信号接收发器(transceiver)的通
讯端点所构成的.通讯端点是可以移动的,其相互间的通讯
是通过无线信号的发射与接收来实现的.当信号从某一个端
点发出,位于此端点信号接收范围以内的其它端点都可以接
收到该信号.
移动Ad Hoc网络有很多实际的应用背景,其中包括
在野外条件下的紧急救援(search, rescue)
战时环境下军事通讯和联络(soldiers, tanks, commanders)
城市出租车/警车的服务调度(taxi, police cars)
3. 通信网络的研究方向和研究方法-研究方向和问题
若一个点要向不在它信号接收/发送范围的点,则需要借助
那些在它信号接收/发送范围的点传递信息(relay).
6
3. 通信网络的研究方向和研究方法-研究方向和问题
一个点的信号接收范围的大小主要是由该点的信号发射功率
(transmission power)强弱所决定的.
一个移动Ad Hoc网络的拓扑结构可以用一个图G(V, E)来表
示,其中图的点集V是网络中通讯端点的集合,图的边集E
是直接相连的通讯端点对的集合.移动Ad Hoc网络的拓扑
结构的一个最显著特点就是其拓扑结构是动态的,它随着
网络上通讯端点的移动和其信号发射功率强弱的调整而改
变.因为在移动Ad Hoc网络中,支持通讯端点接收发无线
信号的能量是由电池(battery)提供的,所以它是非常有限
的网络资源.
3. 通信网络的研究方向和研究方法-研究方向和问题
移动Ad Hoc网络中的一个核心问题就是如何建立网络的拓扑
结构以支持各种各样通讯.比较典型的问题有:
如何调整各个端点的无线信号发射功率(power adjustment),
使得拓扑结构满足一定的连通性质(connectivity)
如何设计单播或者多播路由算法(unicast/multicast routing)
如何动态地检测和恢复拓扑结构的特定性质(dynamic rebuild)
可以选择最小化能量消耗(energy consumption)为上述三个
问题的优化目标.这里可以是最小化所有通讯端点消耗能量
的总和(以节省整个网络的能量资源),也可以是所有通讯端点
消耗能量中的最大值(以避免某个通讯端点因能源消耗过大而
不能接收发信号,造成网络完全或部分地瘫痪).
3. 通信网络的研究方向和研究方法-研究方向和问题
传感器网络(sensor networks)是一种与移动Ad Hoc网络相似
的无线通讯网络.它主要是由配有传感器(sensors)的通讯
端点所构成的.通讯端点通常是不动的,其相互间的通讯是
通过无线信号的发射与接收来实现的.当信号从某一个端点
发出,位于此端点信号接收范围以内的其它端点都可以接收
到该信号.
传感器网络有很多实际的应用背景,其中包括
大气环境检测(environment detection)
用于野战临时军事通信网络(military networks)
传感器网络中问题与移动Ad Hoc网络中的问题是非常类似.
不同的是传感器比接收发器要小,功能要弱.
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
3. 通信网络的数学问题的研究方向-研究方法和思路
学习一些组合优化和图论方面的课程和书籍,比如
基础内容
Combinatorial Optimization: Algorithms and Complexity
C. H. Papadimitriou and K. Steiglitz, Prentice-Hall, 1982.
Introduction to Algorithms
T. H. Cormen, C. E. Leiserson, R. L. Rivest, MIT, 1990.
较深内容
Complexity and Approximation
G. Ausiello, et al, Springer, 1999.
Combinatorial Optimization: Theory and Algorithms
B. Korte and J. Vygen, Springer, 2000.
Approximation Algorithms
V. V. Vzairani, Springer, 2001.
3. 通信网络的数学问题和研究方向-研究方法和思路
与计算机科学/工程院系,信息或者通信理论/工程院系的
研究人员合作
从国际学术会议或者期刊中,获取研究问题和最新的成果
IEEE INFOCOM, GLOBECOM, MILCOM
IEEE Trans. Networking, Communications, Vehicular Technology, Computers
IEEE FOCS, ACM STOC, ACM-SIAM SODA
Information Processing Letters, Theoretical Computer Science, Networks,……
SIAM J. Computing, Discrete Math,
Discrete Math, Discrete Applied Math, J. Algorithm, Algorithmica
7
结束
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2. 通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的数学问题和研究方向
3.1 研究方向和问题
3.2 研究方法和思路
参考文献
S. Arora, FOCS, 1996.
N. G. Beck et al, Discrete Applied Math., 87 (1998).
K. Bharath-Kumar et al, IEEE Trans Communication, 31 (3) (1983).
D.-H. Chen et al, J. Global Optimization, 18 (1) (2000).
D.-Z. Du et al, Algorithmica, 7(1992).
T. Erlebach et al, Proc Workshop on Parallel Systems and Algorithm, 1996.
M. Furer et al, J. of Algorithms, 17 (1994).
M. R. Garey et al, Computers and Intractability, 1979.
X.-D. Hu et al, J. Parallel and Distributed Computing, 61 (10) (2001) .
S. Khuller et al, Algorithmica,14 (4) (1995).
J. B. Kruskal, Proc. of AMS, 7(1956).
R. C. Prim, Bell System Tech. J., 36(1957).
M. Slusarek, Lecture Notes in Computer Science, 379(1989).
D. W. Wall, Ph. D. thesis, Stanford University, June 1980.
A. Zelikovsky, Algorithmica, 9 (1993).
一个网络问题--"六级分离"猜想
你与阿诺德·施瓦辛格,萨达姆·侯赛因,本·拉登是朋友吗 似
乎不太可能.或者任意想出一个人来,如果你想联络到他,应
该怎么办 你可以这样做:找一个最有可能和他有联系的亲友,
把问候转达给他,然后他也照样去找下一位亲友.那么,一共
需要多少个这样的亲友,就能找到对方呢
这个问题的答案或许有点让人吃惊:不论你想找那位满身肌肉
的壮汉州长,被美军囚禁的总统还是难以找到的恐怖袭击的策
划者(或者这个星球上任何一个普通人),大约只需要6步
(最后一步就是目标)"中转".
35年以前,美国的一位心理学家Stanley Milgram在《今日心理
学》杂志上提出了他的"六级分离"(Six Degrees of Separation)
的理论.他认为,任何两个陌生人都可以通过"亲友的亲友"建
立联系,而这两个人之间的亲友数量大约是5.
一个网络问题--"六级分离"猜想
最新的实验结果来自哥伦比亚大学社会学系的Duncan Watts领
导的研究小组.《科学》杂志发表了他们关于在世界范围内大
规模检验"六级分离"假说的论文.Duncan Watts使用的是一种
更经济,快捷而且容易追踪的"包裹",那就是电子邮件.
研究"六级分离"—或者称作"小世界现象"—的作用不仅仅是让
人们大吃一惊,或者为剧作家提供创作的素材(还真的有那么
一部同名电影)."小世界现象的一些可能的应用是设计点对
点的网络和数据库.基本上,研究人们如何找到对方可以帮助
设计任何需要进行搜索的大型网络."它不仅仅可以用于改进
移动电话网络或者互联网的交通状况,科学家还能借此更好地
了解诸如传染病或者社会谣言的传播状况.
人们还不知道是不是"六级分离" 如果是,为什么是"六级分
离",而不是"60级分离"或者"100级分离".
谢谢大家!
胡晓东
应用数学研究所
中国科学院数学与系统科学研究院
北京 2734信箱,北京100080
xdhu@mail.amss.ac.cn
xdhu@public.bta.net.cn
www.amt.ac.cn/member/huxiaodong/index.html
计算机通信网络-研究方法和研究方向
胡晓东
应用数学研究所
中国科学院数学与系统科学研究院
北京 2734信箱,北京100080
xdhu@mail.amss.ac.cn
xdhu@public.bta.net.cn
www.amt.ac.cn/member/huxiaodong/index.html
提纲
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
《Physics World》(2002年9月)刊登了有读者评选出的最美丽
的物理实验前10位的排名,其中第四位是牛顿的棱镜分解太阳
光.(随后美国《New York Times》作了简单的解释.)以前
大家都认为白光是一种纯的没有其它颜色的光(亚里士多德就
是这样认为的),而彩色光是一种不知何故发生变化的光.而
牛顿并不这样认为.
为了验证这个假设,牛顿把一面三棱镜
放在阳光下,透过三棱镜,光在墙上被
分解为不同颜色(光谱).牛顿的结论是:
正是这些红红,,橙橙,,黄黄,,绿绿,,青青,,蓝蓝,,紫紫
基础色有不同的色谱才形成了表面上颜
色单一的白色光,如果你深入地看看,
会发现白光是非常美丽的.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
在光纤通信网络中通过使用波分复用技术(WDM -Wavelength
Division Multiplexing )来充分利用巨大的带宽.一束光纤可以
同时传输多个信道(channels),只要它们使用不同的波长.
因为波长是一种有限的网络资源,所以如何充分利用有限的波
长资源,即给所需要建立的信道合理地分配波长(wavelength
assignment),以满足尽可能多的通信需求,就是光纤通信网
络中的核心问题之一.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
波长分配问题(wavelength assignment problem, WAP)
实例一个图G(V, E)和一些路(path)的集合P.
可行解w个波长恰当地分配给集合P中地所有路.
目标使得w尽可能地小.
路由和波长分配问题(Routing-WAP, RWAP)
实例一个图G(V, E)和一些点对(node-pair)的集合P.
可行解给P中的每一个点对找一条路,并且将w个波长恰当地
分配给所有的路.
目标使得w尽可能地小.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
路由算法
1
2
3
4
波长分配
1
2
3
4
2
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
12 3 4 567891011
12 3 4 567891011
贪婪的波长分配算法是最优的(M. Slusarek, 1989).
首先考虑在线性网络上的波长分配问题(WAPin bus networks,
linear array):
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
对于一般网络上的波长分配问题(WAP),通常的方法是将它
转化成一个图的顶点着色问题(Vertex-Coloring Problem): 即给定
一个图G'(V', E'), 用最少的颜色给图的所有顶点着色使得若两
个相邻的顶点着有不同的颜色.
构造一个辅助图G'(V', E'): V'是路的集合P, 即V'=P, 且V'中
的两个顶点有边相连当且仅当它们在G(V, E)中相应的路有公用
的边.易知 网络G(V, E)上的波长分配问题(WAP)等价于G'(V',
E')中的顶点着色问题.
定理(T. Erlebach et al, 1996; V. Kumar et al, 1997)
波长分配问题(WAP)在树(tree)或者环(ring)网络上是NP-难解的.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
定理(T. Erlebach et al, 1996)
存在一个求解树上波长分配问题的近似算法A,它所用的波长数
目wA(P)满足wA(P)≤1.1 wopt(P)+0.8,这里wopt(P)是最优算
法所需要的波长数目.
算法的基本思想是这样的:
(1)将树上波长分配问题分解转化成星图上波长分配问题;
(2) 用求解边着色问题的方法处理星图上波长分配问题;
(3) 将星图上波长分配问题的(不完全)解合并成一个树上
波长分配问题的解.
1. 通信网路优化问题与图论算法问题-光纤网络中波长分配问题
定理(G. Wilfong et al, 1998)
存在一个求解环图上波长分配问题的近似算法A,它所用的
波长数目wA(P)满足wA(P)≤2 wopt(P)-1, 这里wopt(P)是
最优算法所需要的波长数目.
算法的基本思想是这样的:
(1) 将环在一条路的端点切开,得到一个线性网络;
(2) 用前面叙述的贪婪算法给所有的路(或者路段)分配波长;
(3) 给切断的路分配一个波长(如果它们被分配了不同的波长).
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
在计算机分布式系统中,可以把一个数据(文件)复制若干份
(replica),然后把它们放到计算机网络中不同的节点上.
一方面可以达到提高终端用户读取(read)数据文件的速度
(因为我们可以通过访问最近的网络节点来获得数据文件);
另一方面也可以增强网络的可靠性(因为某一个网络发生了
故障,我们还可以通过访问(access)其它的网络节点来获
得同样的数据文件).
3
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
然而,数据备份放置的过多,会给数据更新(write)和管理
带来麻烦(因为当我们需要修改一个数据文件的时候,我们
需要同时修改它的备份,否则,它们就不一致了).
这里的一个组合优化问题(X.-D. Hu et al, 2001)就是如何
放置有限多个复制的数据(通常不是很多),使得网络的可靠
性最高且数据访问的速度最快.
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
Write-all
终端用户终端用户
Read-only
数据备份
Majority-voting
1. 通信网路优化问题与图论算法问题-数据备份的放置问题
等间距放置严格等间距放置集中放置
is optimal for
read-dominant.
is optimal for
majority voting.
is optimal for
write-dominant.
1. 通信网路优化问题与图论算法问题-总结
通过对光纤网络中波长分配问题的介绍,我们可以看到网络
中的一些组合优化问题的研究和解决可以借助已有的一些图
论的理论知识(特别是算法部分).
通过对数据备份的放置问题的介绍,我们可以看到网络中的
一些组合优化问题与图论的研究对象和关心的问题又都是不
同的.在通信网路优化问题的研究中,图仅仅是作为网络的
拓扑结构,而edge-link和vertex-node不仅仅是名称上的区
别,更重要的是link和node还有网络中的功能作用.
此外,网络优化问题与经典的基于网络流理论的优化问题在
研究的内容和方法上也不同,前者比后者要广泛得多.
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
2.通信网络中的基本问题和数学模型-网络优化设计问题
经典的最小Steiner树问题可以简单地叙述为:给定平
面上若干个点,如何将它们连接起来使得连线的总长
最短.注意该问题的解一定有树的结构(Steiner树),
而且可能会引入一些新的点(Steiner点).
最小Steiner 树最小生成树费玛问题
(1601-1665 )
4
2.通信网络中的基本问题和数学模型-网络优化设计问题
定理(M. R. Garey et al, 1979)
最小Steiner树问题是NP-难解的.
定理(J. B. Kruskal, 1956; R. C. Prim, 1957)
最小生成树问题是可以用贪婪算法在多项式时间求解.
定理(D.-Z. Du et al, 1992)
最小生成树与最小Steiner树权重之比不超过2/√3.
定理(S. Arora, 1996)
最小Steiner树问题有多项式时间近似方案.
2.通信网络中的基本问题和数学模型-网络优化设计问题
在通讯网络的具体设计中,我们通常还要考虑其它
实际因素/约束.例如:如果连接两点的通讯线路
太长,那么信号在传输的过程中会有衰竭.一个解
决的方法就是在长线路中放置若干个信号放大器
(amplifier).
很自然地就产生了一个组合优化的问题:就是如何
设计网络使得所需要的信号放大器最少.
2.通信网络中的基本问题和数学模型-网络优化设计问题
最少Steiner点的Steiner树问题可以简单地叙述为:
给定平面上若干个点和一个正实数R,如何将它们
连接起来使得每段线的长度不超过R且所引入的
Steiner点最少.
>>RR
近似解最优解
定理(D.-H. Chen et al, 2000)
基于最小生成树的算法的近似比是4.
2.通信网络中的基本问题和数学模型-网络优化路由问题
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2. 通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
2.通信网络中的基本问题和数学模型-网络优化路由问题
在通信服务中经常需要把信息从一个源点传到多个收点,即
多播传输(multicast),如有线电视服务(video-on-demand),
或者要把一组点联结起来(group communication),如电视/
电话会议(tele-conference).这里的核心问题之一就是如何
将这些点连接起来(routing).
网络上的Steiner树问题
实例边赋权图G(V, E)和顶点集合的一个子集S V.
可行解联接了集合S中所有点的树T(Steiner tree).
目标极小化树T上所有边的权和.
定理(M. R. Garey et al, 1979)
网络上的Steiner树问题是NP-难解的.
2.通信网络中的基本问题和数学模型-网络优化路由问题
基于最小生成树的2-近似算法(K. Bharath-Kumar et al, 1983)
2
2
2
2
2
1
1
11
1
原始问题造辅助图造生成树
2
2
1
1
1
1
回到原图
2
1
1
1
1
破圈造树
1
1
11
1
最优解
5
2.通信网络中的基本问题和数学模型-总结
一般来讲,设计求解网络优化设计问题的算法时,主要关心
的是解的性质好坏(approximation performance ratio ),主要
的研究工具是(worst-case analysis),对于算法的复杂性
(time-complexity )要求不是太高.另外,这类问题通常是
离线问题(off-line),算法是全局的(centralized).
一般来讲,设计求解网络优化路由问题的算法时,主要关心
的是解是否好用或有所改进,主要的研究工具是(simulation
study);对于算法的时间复杂性(time-complexity )要求很
高.因此,即使理论上有一些更好性能的算法,例如,网络
上的Steiner树问题有近似比为11/6算法(A. Zelikovsky,
1996),但是因为它们太过复杂,在实际中不会直接应用.
另外,这类问题通常是在线问题(on-line),算法也要求是
局部性的(local )或者是分布式的(distributed).
2. 通信网络中的基本问题和数学模型-总结
通信网络中的基本数学模型之一就是路和树,大多数问题都
是用路(path)和树(tree)来描述的.与此有关的比较典型
问题,有的可以转化成下面几个组合优化问题,在度量空间
(metric spaces)或者 网络上(networks).
极小化最小权和(最小Steiner树问题)
极小化Steiner点的个数(最少Steiner点的Steiner树问题)
极小化最小权和(在直径约束下) (S. Khuller et al, 1995)
极小化平均点到点的距离(D. W. Wall, 1980)
极小化最大的顶点度数(M. Furer et al, 1994)
极小化图的树的分解(N. G. Beck et al, 1998)
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
3. 通信网络的研究方向和研究方法-研究方向和问题
基于基站的无线通信网络(Cellular Networks):
基站的选址问题(location problem)
频率分配问题(frequence assignment problem)
信号传输功率控制问题(transmission power control problem)
通信网络的核心技术和理论是在不断更新和发展的.从传统
的为话务服务(voice)的电话网络系统,到为数据传输
(data)的基于互联网技术的计算机网络;从铜线(copper)
和微波(microwave),到光纤(fiber)和无线(wireless).
这种更新和发展是日新月异的.当前通信网络的热点领域之
一是无线通信网络(wireless networks),相关的应用基础理论
问题可以归纳为三类.
3. 通信网络的研究方向和研究方法-研究方向和问题
移动Ad Hoc网络(mobile Ad Hoc networks)是一种无线通
讯网络.它主要是由配有信号接收发器(transceiver)的通
讯端点所构成的.通讯端点是可以移动的,其相互间的通讯
是通过无线信号的发射与接收来实现的.当信号从某一个端
点发出,位于此端点信号接收范围以内的其它端点都可以接
收到该信号.
移动Ad Hoc网络有很多实际的应用背景,其中包括
在野外条件下的紧急救援(search, rescue)
战时环境下军事通讯和联络(soldiers, tanks, commanders)
城市出租车/警车的服务调度(taxi, police cars)
3. 通信网络的研究方向和研究方法-研究方向和问题
若一个点要向不在它信号接收/发送范围的点,则需要借助
那些在它信号接收/发送范围的点传递信息(relay).
6
3. 通信网络的研究方向和研究方法-研究方向和问题
一个点的信号接收范围的大小主要是由该点的信号发射功率
(transmission power)强弱所决定的.
一个移动Ad Hoc网络的拓扑结构可以用一个图G(V, E)来表
示,其中图的点集V是网络中通讯端点的集合,图的边集E
是直接相连的通讯端点对的集合.移动Ad Hoc网络的拓扑
结构的一个最显著特点就是其拓扑结构是动态的,它随着
网络上通讯端点的移动和其信号发射功率强弱的调整而改
变.因为在移动Ad Hoc网络中,支持通讯端点接收发无线
信号的能量是由电池(battery)提供的,所以它是非常有限
的网络资源.
3. 通信网络的研究方向和研究方法-研究方向和问题
移动Ad Hoc网络中的一个核心问题就是如何建立网络的拓扑
结构以支持各种各样通讯.比较典型的问题有:
如何调整各个端点的无线信号发射功率(power adjustment),
使得拓扑结构满足一定的连通性质(connectivity)
如何设计单播或者多播路由算法(unicast/multicast routing)
如何动态地检测和恢复拓扑结构的特定性质(dynamic rebuild)
可以选择最小化能量消耗(energy consumption)为上述三个
问题的优化目标.这里可以是最小化所有通讯端点消耗能量
的总和(以节省整个网络的能量资源),也可以是所有通讯端点
消耗能量中的最大值(以避免某个通讯端点因能源消耗过大而
不能接收发信号,造成网络完全或部分地瘫痪).
3. 通信网络的研究方向和研究方法-研究方向和问题
传感器网络(sensor networks)是一种与移动Ad Hoc网络相似
的无线通讯网络.它主要是由配有传感器(sensors)的通讯
端点所构成的.通讯端点通常是不动的,其相互间的通讯是
通过无线信号的发射与接收来实现的.当信号从某一个端点
发出,位于此端点信号接收范围以内的其它端点都可以接收
到该信号.
传感器网络有很多实际的应用背景,其中包括
大气环境检测(environment detection)
用于野战临时军事通信网络(military networks)
传感器网络中问题与移动Ad Hoc网络中的问题是非常类似.
不同的是传感器比接收发器要小,功能要弱.
进度
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2.通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的研究方向和研究方法
3.1 研究方向和问题
3.2 研究方法和思路
3. 通信网络的数学问题的研究方向-研究方法和思路
学习一些组合优化和图论方面的课程和书籍,比如
基础内容
Combinatorial Optimization: Algorithms and Complexity
C. H. Papadimitriou and K. Steiglitz, Prentice-Hall, 1982.
Introduction to Algorithms
T. H. Cormen, C. E. Leiserson, R. L. Rivest, MIT, 1990.
较深内容
Complexity and Approximation
G. Ausiello, et al, Springer, 1999.
Combinatorial Optimization: Theory and Algorithms
B. Korte and J. Vygen, Springer, 2000.
Approximation Algorithms
V. V. Vzairani, Springer, 2001.
3. 通信网络的数学问题和研究方向-研究方法和思路
与计算机科学/工程院系,信息或者通信理论/工程院系的
研究人员合作
从国际学术会议或者期刊中,获取研究问题和最新的成果
IEEE INFOCOM, GLOBECOM, MILCOM
IEEE Trans. Networking, Communications, Vehicular Technology, Computers
IEEE FOCS, ACM STOC, ACM-SIAM SODA
Information Processing Letters, Theoretical Computer Science, Networks,……
SIAM J. Computing, Discrete Math,
Discrete Math, Discrete Applied Math, J. Algorithm, Algorithmica
7
结束
1.通信网路优化问题与图论算法问题
1.1 光纤网络中波长分配问题
1.2 数据备份的放置问题
2. 通信网络中的基本问题和数学模型
2.1 网络优化设计问题
2.2 网络优化路由问题
3.通信网络的数学问题和研究方向
3.1 研究方向和问题
3.2 研究方法和思路
参考文献
S. Arora, FOCS, 1996.
N. G. Beck et al, Discrete Applied Math., 87 (1998).
K. Bharath-Kumar et al, IEEE Trans Communication, 31 (3) (1983).
D.-H. Chen et al, J. Global Optimization, 18 (1) (2000).
D.-Z. Du et al, Algorithmica, 7(1992).
T. Erlebach et al, Proc Workshop on Parallel Systems and Algorithm, 1996.
M. Furer et al, J. of Algorithms, 17 (1994).
M. R. Garey et al, Computers and Intractability, 1979.
X.-D. Hu et al, J. Parallel and Distributed Computing, 61 (10) (2001) .
S. Khuller et al, Algorithmica,14 (4) (1995).
J. B. Kruskal, Proc. of AMS, 7(1956).
R. C. Prim, Bell System Tech. J., 36(1957).
M. Slusarek, Lecture Notes in Computer Science, 379(1989).
D. W. Wall, Ph. D. thesis, Stanford University, June 1980.
A. Zelikovsky, Algorithmica, 9 (1993).
一个网络问题--"六级分离"猜想
你与阿诺德·施瓦辛格,萨达姆·侯赛因,本·拉登是朋友吗 似
乎不太可能.或者任意想出一个人来,如果你想联络到他,应
该怎么办 你可以这样做:找一个最有可能和他有联系的亲友,
把问候转达给他,然后他也照样去找下一位亲友.那么,一共
需要多少个这样的亲友,就能找到对方呢
这个问题的答案或许有点让人吃惊:不论你想找那位满身肌肉
的壮汉州长,被美军囚禁的总统还是难以找到的恐怖袭击的策
划者(或者这个星球上任何一个普通人),大约只需要6步
(最后一步就是目标)"中转".
35年以前,美国的一位心理学家Stanley Milgram在《今日心理
学》杂志上提出了他的"六级分离"(Six Degrees of Separation)
的理论.他认为,任何两个陌生人都可以通过"亲友的亲友"建
立联系,而这两个人之间的亲友数量大约是5.
一个网络问题--"六级分离"猜想
最新的实验结果来自哥伦比亚大学社会学系的Duncan Watts领
导的研究小组.《科学》杂志发表了他们关于在世界范围内大
规模检验"六级分离"假说的论文.Duncan Watts使用的是一种
更经济,快捷而且容易追踪的"包裹",那就是电子邮件.
研究"六级分离"—或者称作"小世界现象"—的作用不仅仅是让
人们大吃一惊,或者为剧作家提供创作的素材(还真的有那么
一部同名电影)."小世界现象的一些可能的应用是设计点对
点的网络和数据库.基本上,研究人们如何找到对方可以帮助
设计任何需要进行搜索的大型网络."它不仅仅可以用于改进
移动电话网络或者互联网的交通状况,科学家还能借此更好地
了解诸如传染病或者社会谣言的传播状况.
人们还不知道是不是"六级分离" 如果是,为什么是"六级分
离",而不是"60级分离"或者"100级分离".
谢谢大家!
胡晓东
应用数学研究所
中国科学院数学与系统科学研究院
北京 2734信箱,北京100080
xdhu@mail.amss.ac.cn
xdhu@public.bta.net.cn
www.amt.ac.cn/member/huxiaodong/index.html
·上一篇：复杂网络研究的某些进展
·下一篇：互连网络