In a wireless sensor network, routing messages between two nodes s and t with multiple disjoint paths will increase the throughput, robustness and load balance of the network. The existing researches focus on finding ...In a wireless sensor network, routing messages between two nodes s and t with multiple disjoint paths will increase the throughput, robustness and load balance of the network. The existing researches focus on finding multiple disjoint paths connecting s and t efficiently, but they do not consider length constraint of the paths. A too long path will be useless because of high latency and high packet loss rate. This paper deals with such a problem: given two nodes s and t in a sensor network, finding as many as possible disjoint paths connecting s and t whose lengths are no more than L, where L is the length bound set by the users. By now, we know that this problem is not only NP hard but also APX complete [1,2], which means that there is no PTAS for this problem. To the best of our knowledge, there is only one heuristic algorithm proposed for this problem [3], and it is not suitable for sensor network because it processes in a centralized way. This paper proposes an efficient distributed algorithm for this problem. By processing in a distributed way, the algorithm is very communication efficient. Simulation results show that our algorithm outperforms the existing algorithm in both aspects of found path number and communication efficiency.展开更多
Several problems studied by professor R. V. Kadison are shown to be closely related. The problems were originally formulated in the contexts of homomorphisms of C*-algebras, cohomology of von Neumann algebras and pert...Several problems studied by professor R. V. Kadison are shown to be closely related. The problems were originally formulated in the contexts of homomorphisms of C*-algebras, cohomology of von Neumann algebras and perturbations of C*-algebras. Recent research by G. Pisier has demonstrated that all of the problems considered are related to the question of whether all C*-algebras have finite length.展开更多
文摘In a wireless sensor network, routing messages between two nodes s and t with multiple disjoint paths will increase the throughput, robustness and load balance of the network. The existing researches focus on finding multiple disjoint paths connecting s and t efficiently, but they do not consider length constraint of the paths. A too long path will be useless because of high latency and high packet loss rate. This paper deals with such a problem: given two nodes s and t in a sensor network, finding as many as possible disjoint paths connecting s and t whose lengths are no more than L, where L is the length bound set by the users. By now, we know that this problem is not only NP hard but also APX complete [1,2], which means that there is no PTAS for this problem. To the best of our knowledge, there is only one heuristic algorithm proposed for this problem [3], and it is not suitable for sensor network because it processes in a centralized way. This paper proposes an efficient distributed algorithm for this problem. By processing in a distributed way, the algorithm is very communication efficient. Simulation results show that our algorithm outperforms the existing algorithm in both aspects of found path number and communication efficiency.
文摘Several problems studied by professor R. V. Kadison are shown to be closely related. The problems were originally formulated in the contexts of homomorphisms of C*-algebras, cohomology of von Neumann algebras and perturbations of C*-algebras. Recent research by G. Pisier has demonstrated that all of the problems considered are related to the question of whether all C*-algebras have finite length.
