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

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