一种求受顶点数限制的最短路径的新算法

提出了一种基于逆邻接表求受顶点数限制的最短路径的新算法,其时间复杂度为O((m-2)*w)(m是受限制的顶点数,w是有向图中弧的条数),优于同类算法。采用逆邻接表作为图的存储结构,该算法很容易实现。

多跳无线网络中基于网络编码的多路径路由

提出了一种基于网络编码的多路径路由机制CAMP(networkcoding-awarem ulti-path routing).该机制能够根据路径的可靠性和编码机会,动态地在多条路径上进行数据包的传输.CAMP的路由发现机制能够向源节点返回多条可能的路径以及各条路径的每条边上的ETX(expected transmission count).与以往的多路径路由机制不同,CAMP可以通过转换它的传输路径来动态地创造而非仅仅等待编码机会.利用这一独特的路由机制,CAMP可以让多条路径分摊网络流量负载,并且最大化路径转换收益,从而改进网络的吞吐量.实验结果表明,在无线网络的数据传输过程中,CAMP能够取得比其他路由机制高得多的网络吞吐量.