无线网络中的一种多点传送与数据收集的快速算法ppt课件.ppt
《无线网络中的一种多点传送与数据收集的快速算法ppt课件.ppt》由会员分享,可在线阅读,更多相关《无线网络中的一种多点传送与数据收集的快速算法ppt课件.ppt(12页珍藏版)》请在三一文库上搜索。
1、无线网络中的一种多点传送与数据收集的快速算法,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
2、 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
3、 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 m
4、odel 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 imp
5、roved 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 custo
6、mary 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. 一个无线网络就是指一组收发器通过无线电波来相互进
7、行通信。 它通常假定其传输到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
8、执行一个多点发送 / 广播,我们使用一个多点发送/广播树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 sourc
9、e 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 和一组的多点
10、传送节点 M。 目标是找到一个 多点传送方案的树 T以最大限度地提高生存期,即,激活此树 T (我们可以进行多路广播传输的树)的持续时间最大化和总能量消耗多少由每个节点的初始能源决定。 注意,每次我们激活T,内部节点的剩余的能量会减小。从某方面看,这两个问题是十分相似除了一个我们后面将提到的问题,那就是找到最大生命周期的树不是只有一个。 3数据收集 (DG) 问题 。给定一个无线网络 G = (V,E),一个子集IV的数据节点和目标节点 d。 我们旨在找到一种从数据节点I到目标节点d传输单位消息的方案,以最大化网络生存期 (即我们尝试最大限度地提高从I节点到目标 d 节点的传输数)。 换句话说
11、,我们希望查找一个能跨越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 |) 时间的问题。 有关数据收集(或数据聚合)问题,Kalp
12、akis et al. 6 提供了解决方案,但是,缺少数学计算。 Xue et al. 15 也提出了有效的无线网络的能源-数据的问题。,能源有效的区域中其他相关的工作,能量分配包括能源有效的广播和无线网络中多点传播。给出一些无线节点与源节点 s,问题是为每个节点找到最小能量分配的方法,这样引出的通信图包含一个跨越树根节点s。 此问题NP-HARD已解决,在文献 2,5,13,14 作者提出启发式的解决方案并提供一些理论上的分析。Srinivas 和 Modiano 12 中的提供一种多项式算法,以最佳地查找 k 脱节节点的路径,且最大限度地减少节点的数目。,Park and Sahni 11
13、 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
14、 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 the
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 无线网络 中的 一种 多点 传送 数据 收集 快速 算法 ppt 课件
链接地址:https://www.31doc.com/p-3352562.html