無線網(wǎng)絡(luò)中的一種多點(diǎn)傳送與數(shù)據(jù)收集的快速算法.ppt

無線網(wǎng)絡(luò)中的一種多點(diǎn)傳送與數(shù)據(jù)收集的快速算法,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è)無線網(wǎng)絡(luò) G = (V，E)，我們提出以提高執(zhí)行一系列廣播的可能性為目的最大臨界能源問題。 本文提出了一種改進(jìn)最佳 O(|V | |E|) 時(shí)間（其中 V 代表一組節(jié)點(diǎn)，E 表示一組的網(wǎng)絡(luò)中的鏈接）的最佳解決方案算法。 這種算法適用于一個(gè)全方向的天線模型且可解決多址廣播通信，以最大限度地提高網(wǎng)絡(luò)的生存期問題并改善數(shù)據(jù)收集的運(yùn)行時(shí)間問題。,引言,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. 一個(gè)無線網(wǎng)絡(luò)就是指一組收發(fā)器通過無線電波來相互進(jìn)行通信。 它通常假定其傳輸?shù)絛距離所需的最小能量為。 傳輸可能產(chǎn)生能量分派從而引起通信圖形。 我們解決一個(gè)最大臨界能源問題 11 和全方向天線模型的多點(diǎn)傳送隊(duì)列及數(shù)據(jù)收集問題。無線網(wǎng)絡(luò)由加權(quán)定向圖形表示G = (V，E)（ |V | 節(jié)點(diǎn)和 |E| 邊緣）。定向邊緣 (u，v) 的加權(quán)值w (u，v)是節(jié)點(diǎn) u 傳送單位消息到節(jié)點(diǎn) v所需總能量。 通常，我們假定存在不對稱鏈接，即，w(u, v) w(v,u)。 在全方向設(shè)置中，節(jié)點(diǎn)u可以傳送相同的單元信息給節(jié)點(diǎn)u1、u2uk，其消耗的能量為w(u, uj)1=j=k的最大值。而在定向無線傳輸中，節(jié)點(diǎn)u消耗的能量是 。 為了從一個(gè)源節(jié)點(diǎn) s G執(zhí)行一個(gè)多點(diǎn)發(fā)送 / 廣播，我們使用一個(gè)多點(diǎn)發(fā)送/廣播樹T來組織整個(gè)網(wǎng)絡(luò)。 發(fā)送一個(gè)信息前用 ce(u)代表網(wǎng)絡(luò)中節(jié)點(diǎn) u 的初始能源。 節(jié)點(diǎn)u的剩余的能量re (u，T) = ce(u) max w (u，v) | 在數(shù)T中u 是v的一個(gè)子節(jié)點(diǎn)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è)無線網(wǎng)絡(luò)G = (V，E)和源節(jié)點(diǎn)s，一個(gè)多點(diǎn)發(fā)送/廣播樹T最大的能量是CE(G)。 2. 多點(diǎn)傳送隊(duì)列 (MS) 問題 。給定一個(gè)無線網(wǎng)絡(luò) G = (V，E)，源節(jié)點(diǎn)s 和一組的多點(diǎn)傳送節(jié)點(diǎn) M。 目標(biāo)是找到一個(gè) 多點(diǎn)傳送方案的樹 T以最大限度地提高生存期，即，激活此樹 T （我們可以進(jìn)行多路廣播傳輸?shù)臉洌┑某掷m(xù)時(shí)間最大化和總能量消耗多少由每個(gè)節(jié)點(diǎn)的初始能源決定。 注意，每次我們激活T，內(nèi)部節(jié)點(diǎn)的剩余的能量會減小。從某方面看，這兩個(gè)問題是十分相似除了一個(gè)我們后面將提到的問題，那就是找到最大生命周期的樹不是只有一個(gè)。 3數(shù)據(jù)收集 （DG) 問題 。給定一個(gè)無線網(wǎng)絡(luò) G = (V，E)，一個(gè)子集IV的數(shù)據(jù)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn) d。 我們旨在找到一種從數(shù)據(jù)節(jié)點(diǎn)I到目標(biāo)節(jié)點(diǎn)d傳輸單位消息的方案，以最大化網(wǎng)絡(luò)生存期 （即我們嘗試最大限度地提高從I節(jié)點(diǎn)到目標(biāo) d 節(jié)點(diǎn)的傳輸數(shù)）。 換句話說，我們希望查找一個(gè)能跨越I數(shù)據(jù)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)d的樹 DT，我們可以最大化的激活此樹 DT ，由節(jié)點(diǎn)I開始向目標(biāo)節(jié)點(diǎn)d 發(fā)送數(shù)據(jù)，同時(shí)樹DT中每個(gè)節(jié)點(diǎn)都保持一定的能源,2. 以往工作,Park 和 Sahni 11 是第一個(gè)提出并通過的最大臨界能源問題O (|V| |E|log |E|) 時(shí)間解決方案， 它只適用廣播樹的情況。 我們不得不提到 11 中給出的算法可以輕松地歸納計(jì)算出多點(diǎn)傳送樹運(yùn)行的時(shí)間。Orda和Yassour 9 解決了多點(diǎn)傳送（即廣播）隊(duì)列問題。該算法 9 給出了在多點(diǎn)傳送隊(duì)列中計(jì)算O(|E| |V |log |V |) 時(shí)間的問題。 有關(guān)數(shù)據(jù)收集（或數(shù)據(jù)聚合）問題，Kalpakis et al. 6 提供了解決方案，但是，缺少數(shù)學(xué)計(jì)算。 Xue et al. 15 也提出了有效的無線網(wǎng)絡(luò)的能源-數(shù)據(jù)的問題。,能源有效的區(qū)域中其他相關(guān)的工作，能量分配包括能源有效的廣播和無線網(wǎng)絡(luò)中多點(diǎn)傳播。給出一些無線節(jié)點(diǎn)與源節(jié)點(diǎn) s，問題是為每個(gè)節(jié)點(diǎn)找到最小能量分配的方法，這樣引出的通信圖包含一個(gè)跨越樹根節(jié)點(diǎn)s。 此問題NP-HARD已解決，在文獻(xiàn) 2,5,13,14 作者提出啟發(fā)式的解決方案并提供一些理論上的分析。Srinivas 和 Modiano 12 中的提供一種多項(xiàng)式算法，以最佳地查找 k 脫節(jié)節(jié)點(diǎn)的路徑，且最大限度地減少節(jié)點(diǎn)的數(shù)目。,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.,我們遵循文獻(xiàn) 11 中所建議的方法。 首先我們生成一個(gè)解決方案的潛在的候選值列表 C，然后，它建立檢查這些值的 Oracle數(shù)據(jù)庫，使得可行的解決方案有效。 給出這樣的 Oracle，即，對于一個(gè)給定的值 c 檢查是否CE(G) c的一種算法，顯然是對所有可能候選值 C進(jìn)行排序并在Oracle的二進(jìn)制文件已排序的值的列表上搜索。 但是，它會立即導(dǎo)致自 O (|E|log |E|) 時(shí)間，C 的基數(shù)是 O(|V | +|E|) 。 為了避免此順序，我們可以用隱式方式來進(jìn)行二進(jìn)制搜索。,3. 最大臨界能量（MCE）問題,本文描述一種 Oracle 算法，即給定一個(gè)可能的解決方案值 c，O(|E|) 時(shí)間中檢查是否存在一個(gè)根在源節(jié)點(diǎn)s的廣播/多點(diǎn)傳送樹T，且CE(G) c。 我們應(yīng)注意，此處 11 中的 oracle的運(yùn)行時(shí)間是 O(|V | |E|)而不是O(|E|)，而這對分析是很關(guān)鍵。 我們修改depth-first search (DFS) 算法以檢查c值 的可行性。 事實(shí)上，我們需要找到是否存在一個(gè)樹G ，它能跨越所有在 E邊緣子集(u, v) | w (u，v) +c ce(u)約束下的節(jié)點(diǎn)（多點(diǎn)傳送），不能使用DFS執(zhí)行過程。為此，可以在 O(|E|) 中通過對大量連接的所有節(jié)點(diǎn)得到樹G （它應(yīng)該只有一個(gè)）。 它還可以在多點(diǎn)傳送O(|E|)時(shí)間用以下列方式設(shè)置節(jié)點(diǎn)： 我們在第一個(gè)中節(jié)點(diǎn)包含源節(jié)點(diǎn)s下計(jì)算多點(diǎn)傳送系列節(jié)點(diǎn)總數(shù)。 我們的最后一步是介紹如何執(zhí)行一個(gè)隱式方式下使用所選內(nèi)容值二進(jìn)制搜索算法和上文所述的 Oracle 算法。,4.多點(diǎn)傳送隊(duì)列和數(shù)據(jù)收集問題,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.,在多點(diǎn)傳送隊(duì)列問題中我們旨在找到一個(gè)生命周期最大的多點(diǎn)傳送樹。Orda 和 Yassour 9 觀察到查找這樣的一個(gè)多多點(diǎn)傳送樹的問題，可以被轉(zhuǎn)換為以下問題。 給定一個(gè)定向加權(quán)的圖形 G = (V，E)，與源節(jié)點(diǎn)s、多點(diǎn)傳送節(jié)點(diǎn)M V。 每個(gè)邊緣 (u，v) 的新加權(quán)等于可以使用此邊緣的最大持續(xù)時(shí)間。即， =ce (u) / w (u，v)。 然后，我們的問題是找到一個(gè)多點(diǎn)傳送樹G，它能跨越所有的權(quán)重最小且邊緣是最大化 的M 節(jié)點(diǎn)。,4.多點(diǎn)傳送隊(duì)列和數(shù)據(jù)收集問題,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.,我們發(fā)現(xiàn)我們提出的算法完全適合上面提到的問題的解決方案。確實(shí)，所有可能的解決方案值的集，它的基數(shù) |E| 每個(gè)邊緣的權(quán)重屬于該組。Oracle 算法基于 DFS 算法的。 對于一個(gè)給定的值 c，Oracle算法檢查是否存在一個(gè)目錄樹G 。 顯然，這可以在O(|E|)時(shí)間里驗(yàn)證。,4.多點(diǎn)傳送隊(duì)列和數(shù)據(jù)收集問題,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|)時(shí)間里最佳解決方案值是等于、小于還是大于給定值c。我們用隱式方式來進(jìn)行二進(jìn)制搜索潛在的解決方案值，為了驗(yàn)證給定的值