论文部分内容阅读
输出的路径集合在所有的可能解中具有最小的长度之和。现有的分布式寻找连接s和t的多条不相交路径的方法既不能保证答案正确性也不能保证结果最优性。虽然有一些集中式方法可以保证答案正确性和结果最优性,但是它们都需要收集全网的拓扑信息,从而不适合应用在传感器网络中。本文提出了一个高效的完全分布式算法OFDP,通过节点间交换少量的数据,就可以找到k条长度之和最小的不相交路径。OFDP既能保证答案正确性又能保证结果最优性。OFDP不需要从网络中收集任何信息,节点的信息交换也不依赖于任何结构。如果不考虑路径的长度,通过对OFDP进行简化,本文还提出了另一个用于解决k不相交路径问题的分布式算法FDP。实验结果验证了这两个算法的高效。 第三,本文研究了长度受限的不相交路径问题,即给定两个节点s和t以及长度限制L,寻找最多的连接s和t的不相交路径,使得每条路径的长度都不大于L。首先考虑每个链接的长度都是1的情况。当L≥5时,这个问题不但是NP完全问题而且是APX完全问题。因此不存在这个问题的多项式时间近似模式,以常数近似比来近似这个问题也是非常难的。迄今为止,只有一个关于这个问题的启发式算法被提出,而且该算法采取的是集中式的处理方式。本文提出了这个问题的一个√n近似算法GDA以及GDA的分布式实现。其中,n是网络中节点的数量。另外,本文还给出了这个问题的一个分布式的启发算法OPDA。OPDA可以很好地应对每个链接都有任意长度的情况。实验结果表明,无论是在找到的路径数量方面还是在通信效率方面,OPDA都有很高的效率。 第四,本文研究了(广义)非干扰路径问题,即给定网络中的k对节点{s1, t1},...,{sk, tk},用非干扰路径来连接最多的节点对。本文证明了即使当k=2时,这个问题也是一个NP难问题。本文还证明了对于任意近似这个问题是NP难的。其中,m是网络中链接的数量。因此,√m是可能取得的最好的近似比。本文给出了这个问题的一个贪心算法GSPW,并证明了GSPW的近似比为√m。本文还给出了这个问题的一个在线算法OSBPW,及其分布式实现,并证明了OSBPW拥有很好的理论下界。 针对所研究的问题,本文提出的方法充分考虑了传感器网络的特点,弥补了现有研究工作的不足。对于有些问题,本文更是首次给出了可分析的近似算法或者首次证明了问题的近似比下界,在理论上有所创新和发现。