论文研究 多路径优化问题的研究进展 .pdf

多路径优化问题的研究进展，高宏，张可佳，在各种网络中，尤其是无线传感器网络或者其它的无线ad hoc网络中，多路径路由成为了新的研究热点，如何优化的建立多条传输路径得到国科技论文在线增量的从这些区域中收集部分拓扑信息直到找到条不相交的路径。通过有效的拓扑抽象,算法可以在不收集所有拓扑信息的情况下保证答案正确性不相父路径问题的另一个变种就是长度受限的不相父路径问题,问题定义为:给定网络中的一对节点和,给定长度限制,寻找最多的长度小于的不相交路径。文献证明了当≥时这个问题是一个难问题。文献进一步证明了当≥时这个问题是一个完全问题,即不存在这个问题的多项式时间近似模式。文献给出了这个问题的一个启发式算法,但是没有提供仟何理论界限非干扰路径问题在不相交路径问题中,路径间不相交的性质保证了路径间的独立性。在有线网络中,如果多条路径是不相父路径,它们之间没有干扰。但是在无线网络尤其是无线网络的环境中,路径间仅仅保持不相交并不能保证多条路径不互相干扰。如图所示,假设网络中有两条不相交的路径和,和分别是和上的两个互为邻居的节点。当节点发送路径上的数据时,节点不能接收路径上的数据。同样,当节点接收路径上的数据时,节点不能发送路径上的数据。这就形成了路径和之间的相互干扰。如果上的许多节点与上的节点互为邻居,那么不相交路径带来的网终吞吐量、可靠性和负载平衡的提尹将会变待微不足道为此,研究者提出了非于扰路径的概念。条路径是非干扰路径如果它们是不相交路径且不同路径上没有互为邻居的节点。图无线干扰(虚线表示节点的通信范围)关于非千扰路径研究的比较多的是非千扰路径问题:给定网终中的一对节点和,寻找连接和的条非干扰路径。文献证明了这个问题是一个完全问题。文献给出了这个问题的启发式算法。这些算法都有一个基本思想:在和的连线两端划分一块如图所示的棼入区域,然后在禁入区域两侧寻找条路径。通过将禁入区域划分的足够宽,可以保证这条路径是非十扰路径。在网络节点密度一定的情冼卜,文献给山了个算法可以保证找到条非T扰路径的概率。如果无线网络中的节点都布置了有向天线,文献给出了算法寻找条非T扰路径图寻找条非干扰路径国科技论文在线广义多路径问题边不相交多路径问题边不相交多路径问题定义为:给定网络中的对节点,用边不相交路径连接最多的节点对。边不父路径是指这些路径中的任意两条不包含公共边。如前所述,可以将整个网络描述为一个图分别表示图中节点和边的数量边不相交多路径问题是一个经典的难问题如果这些节点对是按时间顺序依次到来的,文献给出了这个问题的一个联机算法,近似比为其中=是图的直径。该算法的思想是依次处理每个节点对。对于节点对,找到图中最短的路径,如果的长度不大于√,则输出并将上的边从图中删除。文献给出了这个问题的贪心算法,近似比为√。算法的基本思想是将输入的个节点对划分为两个集合已经被连接的节点对集合和未被连接的节点对集合c开始的时候,=,对于中的每对节点,找到图中最短的路径。然后找到路径∈。接下来用连接它所对应的节点对,将从中删除并力入到中,将从图中删除。这个过程一直重复到中没有可以被连接的节点对。文献证明了在有向图中,对于仟意的ε>,边不相交多路径问题不可能被近似,如果最小化拥塞问题最小化拥塞问题定义为:给定网络中的对节点,建立路径其中是一条路径。要求最小化网络的拥塞。对于图中的某条边来说,其上的拥塞为通过边的路径的数量。网终的拥塞定义为∈。拥塞这个概念定义了路径间的耦合程度,通过最小化拥塞可以增加路径的独立性,使之不互相干扰仍然表示网终中节氐的数量,仍然表示网终拓扑图中边的数量。显然,最小化拥塞问题是一个难问题。假设网络中路径的集合为其上的数据流为。于是,最小化拥塞问题可以表述为一个整数规划问题:∑for文献给出了最小化拥塞问题的一个近似算法,近似比可以达到其基本思想是:将最小化拥问题表示为个整数规划问题。通过将限制放松为∈得到个线性规划问题,而线性规划问题在多项式吋间内是可解的。解岀这个线性规划问题,得到每条路径上的流量。对于节点对来说,从中随机的选择一条路径作为迕接这对节点的路径,这些路径被选作的概率分别为。文献给出了这个问题的一个近似算法。如果网络的拓扑图是一个二维网格,最小化拥塞问题仍然是—个难问题。在这种情况卜,文献给出了这个问题的一个常数比的近似算法国科技论文在线假设给定的网络拓扑图是·个有向图,文献证明了这个问题没有近似比为近似算法,如果不包含于在同样假设下,文献证明了这个问题不可能被,如果不包含于伐改给定的网络拓扑图是一个无向图,文献证明了这个问题不可能被近似,如果不包含于非干扰多路径问题正如前面所述,在无线网络中,节点或者边不相交路径并不能描述完仝独立的路径,为此非干扰路径的概念被提出ε非千扰多路径问题定义为:给定网终中的对节点,用非十扰路径连接最多的节点对即使当时,这个问题也是个难问题。但是,如果是个常数并且给定的图是个可平面的有向图,这个问题则变成了个问题。在这种假设下,文献给出了这个问题的多项式时间算法尚待解决的问题关」多路径优化问题,有以下儿个具体问题在理论上具有很高的究价值。长度受限制的不相交路径问题。问題定义为:给定网络中的一对节点和,给定长度限制,寻找最多的长度小于的不相交路径。止如前面介绍的,当≥时,这个问题不但是一个难问题,而且是一个完全问题。但是除了这些结论以外,还没有关于这个问题的近似算法被提出非干扰路径问题。问题定义为:给定网络中的一对节点和,寻找条非干扰的路径。当时这个问题是一个难问题。对于的情况,还没有相关研究出现特殊图中的最小化拥塞问题。众所周知,无线网络的拓扑图并不是一个广义上的图。通常情况下,我们假设每个节点有一个固定的通信半径,当有其它节点在其通信半径范围以内,两个节点间就会有一个链接。对于大多数无线网络来说,节点的通信半径都是相冋的。这就使得无线网络更适合被描述为一个单位圆盘图()。在这种模型卜,给定网络中的对节点建立路径,其中是一条路径。要求最小化网络的拥塞非千扰多路径问题。问题定义为:给定网络中的对节点,用非千扰路径连接最多的节点对。如前所述,当不是常量或者网络的拓扑图不是一个有向可平面图时,这个问题是一个难问题。除此之外,没有关于这个问题的相关研究。大多数情况下,网终的拓扑图不可能是一个可平面图,而网终的路由需求不可能是一个常量。结论在各种网络中,尤其是在无线传感器网络或者其它的无线网络中,优化的建立多条传输路径成为新的研究热点。多路径优化问题可以分为两大类:多路径问题和`义多路径问题。优化的目标可以是路径的数目,路径的长度和路径的独立性。本文介绍了这两人类多路径优化问题在近年来取得的研究进展,尤其是理论上的研究成果。此外,总结了现有研究的不足,提出了今后关于多路径优化问题的研究方向国科技论文在线参考文献陈跃泉郭晓峰曾庆凯等一个基于网络最大流的多路径路由算沄电子学报方效林亻胜飞李建中无线传感器网络一种不相交眳径路由算法计算札研究与发展张可佳高宏在传感器网络屮寻找不相交路径的增量算法通信学报国科技论文在线