无线网络中的一种多点传送与数据收集的快速算法.pptVIP

无线网络中的一种多点传送与数据收集的快速算法 Fast algorithm for multicast and data gathering in wireless networks 摘要 引言 引言 2. 以往工作 3. 最大临界能量（MCE）问题 3. 最大临界能量（MCE）问题 4.多点传送队列和数据收集问题 4.多点传送队列和数据收集问题 4.多点传送队列和数据收集问题 数据收集问题 LOGO * LOGO * * Communication Systems Engineering Department, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel Received 15 April 2007; received in revised form 5 November 2007; accepted 18 December 2007 Available online 21 February 2008 Communicated by S.E. Hambrusch Abstract：Given a wireless network G = (V ,E), we consider a maximum critical energy problem [J. Park, S. Sahni, Maximum lifetime broadcasting in wireless networks, IEEE Transactions on Computers 54 (9) (2005) 1081–1090] that has an objective of increasing the chances of doing a sequence of broadcasts. We present an optimal generalized solution algorithm running in improved optimal O(|V | + |E|) time, where V stands for a set of nodes and E stands for a set of links in the network. Our approach is applicable in an omnidirectional antenna model and can be used to solve the problem of multicasting traffic so as to maximize the lifetime of the network [A. Orda, B.-A. Yassour, Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas, in: Proc. ACM MOBIHOC, 2005] and a data gathering problem with an improved running time 给定一个无线网络 G = (V，E)，我们提出以提高执行一系列广播的可能性为目的最大临界能源问题。 本文提出了一种改进最佳 O(|V | |E|) 时间（其中 V 代表一组节点，E 表示一组的网络中的链接）的最佳解决方案算法。 这种算法适用于一个全方向的天线模型且可解决多址广播通信，以最大限度地提高网络的生存期问题并改善数据收集的运行时间问题。 A wireless network consists of a set of transceivers communicating with each other by radio. It is customary to assume that the minimal transmission power required to transmit to a distance d is dα, where the distancepower gradient α is usually taken to be in the interval [2, 4] (see [10]). The transmission possibilities resulting from a power assignment induce a communication graph. 一个无线网络就是指一组收发器通过无线电波来相互进行通信。 它通常假定其传输到d距离所需的最小能量为。 传输可能产生能量分派从而引起通信