无线传感器网络中多路径路由及非干扰路由的研究

Routing with multiple paths, especially multiple disjoint paths, in wirelss sensor networks will effectively improve the performances of routing in the aspects of reliability, throughput and load balance. The key problem of multi-path routing is optimally finding multiple (disjoint) paths connecting the source and the destination . A set of paths are disjoint paths if they do not have any common nodes except the source and the destination. On the other side, since all the nodes share the same channel, there are wireless interferences among the nodes on different paths which are close to each other. A lot of wireless interferences among routing paths will greatly reduce throughput of routing and increase energy comsumption of sensor nodes. Thus, the notion of non-interfering paths is proposed. A set of paths are non-interfering paths if there is no wireless interference among these paths. Routing with multiple non-interfering paths will further improve the performance of routing. This subject will research on the problems of optimally finding multiple disjoint paths or non-interfering paths for routing in wireless sensor networks. The optimization goals include minimizing total cost of the routing paths, limiting cost of each routing path, minimizing wireless interference among the routing paths. Some of these problems lack of efficient algorithms that can be used in sensor networks, some of these problems lack of theoretical research, and some of these problems are proposed for the first time. The expected research results of this subject will have considerable theoretical and pratical significances.

在传感器网络中利用多条路径特别是多条不相交路径进行路由可以有效的提升路由的可靠性、吞吐量以及网络的负载平衡。多路径路由的核心问题是优化地寻找源节点和目的节点间多条不相交路径。不相交路径是多条除了源节点和目的节点外不包含任何其它公共节点的路径。另一方面，因为共用同一信道，不同路径上的节点会因为距离较近而发生无线干扰。路径间大量的无线干扰会很大程度上降低路由的吞吐量、增加节点的能量消耗。为此，非干扰路径的概念被提出。多条路径是非干扰路径如果它们彼此之间不存在无线干扰。利用多条非干扰路径进行路由可以进一步提升路由的性能。本课题将研究在传感器网络中优化地寻找多条不相交路径或非干扰路径进行路由的问题。优化的目标包括最小化路径的代价之和、限制每条路径的代价、最小化路径间的无线干扰等等。这些问题要么缺少适合传感器网络的算法，要么缺少理论研究，要么是首次被提出。预期的研究将具有重大的理论和实际意义。

无线传感器网络的特点决定了需要为其单独设计路由策略。相比于只用一条路径传输数据，在源节点和目的节点间采用多条路径，特别是多条不相交路径，来进行传输数据可以大大提升路由的可靠性、吞吐量以及负载平衡。本项目研究的第一个方面是在无线传感器网络中如何优化地建立多条不相交路径用于数据传输。此外，由于所有节点使用同一信道进行通信，节点间的无线干扰使得用户不再满足于不相交路径路由，而是希望使用相互干扰最小的多条路径进行数据传输。本项目研究的第二个方面就是在无线传感器网络中如何量化多条传输路径间的相互干扰并建立相互干扰最小的多条路径用于数据传输。本项目具体的研究问题包括：.第一个问题是在网络中给定节点s和t，如何在保证正确性的前提下，建立连接s和t的k条（k由用户指定）不相交路径。所谓正确性是指如果网络中存在k条不相交路径，所提出的方法一定能够输出k条不相交路径。针对这个问题，我们提出了两个能够保证正确性且适用于传感器网络的完全分布式方法EDA和DFDP。这两个方法都不需要sink节点收集网络的拓扑信息，仅通过节点间交换少量数据就能够输出正确的结果。据我们所知，EDA和DFDP是仅有的能够保证正确性的分布式方法。.第二个问题是给定节点s和t，建立连接s和t的长度之和最短的k条不相交路径。这个问题的难度在于如何保证正确性和最优性。所谓最优性是指输出的结果在所有可行解中具有最小的长度之和。针对这个问题，我们提出了一个能够保证正确性和最优性且适用于传感器网络的完全分布式方法OFDP。OFDP通过在节点间交换少量信息就能得到正确的结果，且信息的交换不依赖于任何预先建立的结构。据我们所知，OFDP是唯一一个能够保证正确性和最优性的分布式方法。.第三个问题是给定网络中的k对节点{s1,t1},…,{sk,tk}，如何建立k条路径来分别连接这些节点对使得路径间的相互干扰最小。针对这个问题，我们首先提出了一个衡量多条路径间相互干扰水平的标准。与以往的标准相比，我们的衡量无线干扰的方法适用于任何情况，更具有普遍性。在该标准下，给定的问题是一个NP难问题。我们为这个问题设计了一个高效的启发式分布算法DOAMI。DOAMI是在新的干扰标准下对该问题所提出的首个算法。.我们所提出的方法要么是首个能够保证正确性的分布式方法，要么是关于相关问题的首次研究，都具有重要的理论创新意义。实验结果证明了这些方法的效率