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

无线网络中的一种多点传送与数据收集的快速算法,Fast algorithm for multicast and data gathering in wireless networks,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) 10811090 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距离所需的最小能量为。 传输可能产生能量分派从而引起通信图形。 我们解决一个最大临界能源问题 11 和全方向天线模型的多点传送队列及数据收集问题。无线网络由加权定向图形表示G = (V，E)（ |V | 节点和 |E| 边缘）。定向边缘 (u，v) 的加权值w (u，v)是节点 u 传送单位消息到节点 v所需总能量。 通常，我们假定存在不对称链接，即，w(u, v) w(v,u)。 在全方向设置中，节点u可以传送相同的单元信息给节点u1、u2uk，其消耗的能量为w(u, uj)1=j=k的最大值。而在定向无线传输中，节点u消耗的能量是 。 为了从一个源节点 s G执行一个多点发送 / 广播，我们使用一个多点发送/广播树T来组织整个网络。 发送一个信息前用 ce(u)代表网络中节点 u 的初始能源。 节点u的剩余的能量re (u，T) = ce(u) max w (u，v) | 在数T中u 是v的一个子节点0。,引言,Next, we define three related problems considered in this paper. The maximum critical energy (MCE) problem 11asks to find, for a given wireless network G =(V ,E) and source node s, a multicast/broadcast tree T maximizing CE(G) (in the multicast tree version of the problem we are also given a set M of multicast nodes required to receive a message from s). 1. 最大临界能量（MCE）问题。给出了一个无线网络G = (V，E)和源节点s，一个多点发送/广播树T最大的能量是CE(G)。 2. 多点传送队列 (MS) 问题 。给定一个无线网络 G = (V，E)，源节点s 和一组的多点传送节点 M。 目标是找到一个 多点传送方案的树 T以最大限度地提高生存期，即，激活此树 T （我们可以进行多路广播传输的树）的持续时间最大化和总能量消耗多少由每个节点的初始能源决定。 注意，每次我们激活T，内部节点的剩余的能量会减小。从某方面看，这两个问题是十分相似除了一个我们后面将提到的问题，那就是找到最大生命周期的树不是只有一个。 3数据收集 （DG) 问题 。给定一个无线网络 G = (V，E)，一个子集IV的数据节点和目标节点 d。 我们旨在找到一种从数据节点I到目标节点d传输单位消息的方案，以最大化网络生存期 （即我们尝试最大限度地提高从I节点到目标 d 节点的传输数）。 换句话说，我们希望查找一个能跨越I数据节点和目标节点d的树 DT，我们可以最大化的激活此树 DT ，由节点I开始向目标节点d 发送数据，同时树DT中每个节点都保持一定的能源,2. 以往工作,Park 和 Sahni 11 是第一个提出并通过的最大临界能源问题O (|V| |E|log |E|) 时间解决方案， 它只适用广播树的情况。 我们不得不提到 11 中给出的算法可以轻松地归纳计算出多点传送树运行的时间。Orda和Yassour 9 解决了多点传送（即广播）队列问题。该算法 9 给出了在多点传送队列中计算O(|E| |V |log |V |) 时间的问题。 有关数据收集（或数据聚合）问题，Kalpakis et al. 6 提供了解决方案，但是，缺少数学计算。 Xue et al. 15 也提出了有效的无线网络的能源-数据的问题。,能源有效的区域中其他相关的工作，能量分配包括能源有效的广播和无线网络中多点传播。给出一些无线节点与源节点 s，问题是为每个节点找到最小能量分配的方法，这样引出的通信图包含一个跨越树根节点s。 此问题NP-HARD已解决，在文献 2,5,13,14 作者提出启发式的解决方案并提供一些理论上的分析。Srinivas 和 Modiano 12 中的提供一种多项式算法，以最佳地查找 k 脱节节点的路径，且最大限度地减少节点的数目。,Park and Sahni 11 were the first to introduce the maximum critical energy problem by providing O(|V| + |E|log |E|) time solution. They considered only the case of a broadcast tree. We have to mention that the algorithm given in 11 can be easily generalized to deal with a multicast tree not affecting the running time of their algorithm. The multicast (in fact, broadcast) sequence problem was solved in O(|E|log |V |) time in 7 with a subsequent improvementby Orda and Yassour 9.,3. 最大临界能量（MCE）问题,We follow the approach proposed in 11. First we produce a list C of potential candidate values for the solution and then build an oracle that checks these values for feasible solution efficiently. Given such oracle, i.e., an algorithm which for a given value c checks whether CE(G) c, the obvious approach is to sort all potential candidate values C and to use the oracle in a binary search fashion over the list of sorted values. However, it would lead immediately to O(|E|log |E|) time since the cardinality of C is O(|V | + |E|) as shown below. In order to avoid this, we can do the binary search in an implicit way.,我们遵循文献 11 中所建议的方法。 首先我们生成一个解决方案的潜在的候选值列表 C，然后，它建立检查这些值的 Oracle数据库，使得可行的解决方案有效。 给出这样的 Oracle，即，对于一个给定的值 c 检查是否CE(G) c的一种算法，显然是对所有可能候选值 C进行排序并在Oracle的二进制文件已排序的值的列表上搜索。 但是，它会立即导致自 O (|E|log |E|) 时间，C 的基数是 O(|V | +|E|) 。 为了避免此顺序，我们可以用隐式方式来进行二进制搜索。,3. 最大临界能量（MCE）问题,本文描述一种 Oracle 算法，即给定一个可能的解决方案值 c，O(|E|) 时间中检查是否存在一个根在源节点s的广播/多点传送树T，且CE(G) c。 我们应注意，此处 11 中的 oracle的运行时间是 O(|V | |E|)而不是O(|E|)，而这对分析是很关键。 我们修改depth-first search (DFS) 算法以检查c值 的可行性。 事实上，我们需要找到是否存在一个树G ，它能跨越所有在 E边缘子集(u, v) | w (u，v) +c ce(u)约束下的节点（多点传送），不能使用DFS执行过程。为此，可以在 O(|E|) 中通过对大量连接的所有节点得到树G （它应该只有一个）。 它还可以在多点传送O(|E|)时间用以下列方式设置节点： 我们在第一个中节点包含源节点s下计算多点传送系列节点总数。 我们的最后一步是介绍如何执行一个隐式方式下使用所选内容值二进制搜索算法和上文所述的 Oracle 算法。,4.多点传送队列和数据收集问题,In the multicast sequence problem we aim to find a multicast tree of maximum lifetime in terms of number of transmissions. Orda and Yassour 9 observed that the problem of finding such a multicast tree can be transformed to the following problem. Given a directed weighted graph G = (V ,E), with a source nodes and multicast set of nodes M V . The new weight w(u, v) of each edge (u, v) is equal to the maximal time during which this edge can be used before the energy of transmitting node drains, i.e., w(u, v) = ce(u)/w(u, v). Then, our problem is to find a multicast tree of G spanning all M nodes whose minimal weightedge is maximized.,在多点传送队列问题中我们旨在找到一个生命周期最大的多点传送树。Orda 和 Yassour 9 观察到查找这样的一个多多点传送树的问题，可以被转换为以下问题。 给定一个定向加权的图形 G = (V，E)，与源节点s、多点传送节点M V。 每个边缘 (u，v) 的新加权等于可以使用此边缘的最大持续时间。即， =ce (u) / w (u，v)。 然后，我们的问题是找到一个多点传送树G，它能跨越所有的权重最小且边缘是最大化 的M 节点。,4.多点传送队列和数据收集问题,We observe that our proposed strategy exactly fits a solution of the above-mentioned problem. Indeed, the set of all possible solution values is of cardinality |E| every edges weight belongs to this set. The oracle algorithm is based on DFS strategy and is almost identical to one described in the previous section. For a given value c, the oracle checks whether there exists a tree of G spanning the nodes of M under the constraint that edges (u, v) with w(u, v) c are forbidden for use.Definitely, this can be verified in O(|E|) time. The definition of Gx and Gx is slightly changed. Now, Gx is a subgraph of G without edges (u, v) such that w(u, v) x is a subgraph of G without edges(u, v) such that w(u, v) x.,我们发现我们提出的算法完全适合上面提到的问题的解决方案。确实，所有可能的解决方案值的集，它的基数 |E| 每个边缘的权重属于该组。Oracle 算法基于 DFS 算法的。 对于一个给定的值 c，Oracle算法检查是否存在一个目录树G 。 显然，这可以在O(|E|)时间里验证。,4.多点传送队列和数据收集问题,As before, we can determine in O(|E|) time whether the optimal solution is equal, smaller or larger than a given value c. We perform an implicit binary search on the potential solution values, using oracle at each step in order to verify the feasibility of the given value and to navigate our algorithm exactly as we did in the previous section. More precisely, if an optimal solution is less than some value x, we contract all connected components of the graph Gx into single vertices by joining all the nodes connected by edges of weight x (at least) into a single node and discarding these edges.,如前，我们可以确定在O(|E|)时间里最佳解决方案值是等于、小于还是大于给定值c。我们用隐式方式来进行二进制搜索潜在的解决方案值，为了验证给定的值