在異質性網路下集合對集合的廣播

Set to Set Broadcasting in Heterogeneous Network

蕭安辰(An-Chen Hsiao)

指導教授 ： 李德財

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.02187

摘要

我們考慮在圖論上來討論廣播問題。所謂「集合對集合廣播問題」是指在給定的圖上,尋找一組傳播的順序使得一組點集合能在最短的時間內將資料傳送到另一組點集合。在這個模型中，每個點(vertex)都有各自的處理時間，每條邊(edge)有各自的傳輸延遲。處理時間指是每個點需要花多少時間來處理得到的資訊。而傳輸延遲是指每條邊將資料從一端點傳到另一端點所需要的時間。

在此論文中，我們從圖論的觀點探討在異質性網路下集合對集合廣播問題在樹狀結構中的表現。在電話模型中我們提供了時間複雜度是O(nlogn)的演算法來求出樹的傳播中心(Broadcasting center)，並且利用這這一個方法解決集合對集合傳播問題。

關鍵字

異質性網路 ； 廣播 ； 樹 ； 集合對集合 ； 電話模型

並列摘要

In a heterogeneous network the Broadcasting Problem, which is to find the Broadcasting Center from which to broadcast messages to all the vertices in the network takes the least time, is an interesting problem. In this thesis, we will focus on heterogeneous tree networks under the telephone communication model. Given a tree G =(V, E) in which each vertex v ∈ V has a weight W (v) and each edge e(u, w) ∈ E has a weight W (u, w), the weight W (v) of a vertex v represents the amount of time (in units) needed for v to process the information before it can be passed on to other vertices u which are connected to v by an edge and the weight W (u, w) of an edge e(u, w) represents the amount (in units) of time needed to transmit messages between two end vertices of e. Under the telephone communication model in which each vertex can be engaged in the transmission of messages to exactly one adjacent vertex at a given time, we present an algorithm that solves the Broadcasting Problem in O(n log n) time, where n is the number of vertices in the tree. A similar problem, called Gathering Problem, in which the messages of all the vertices are to be gathered at the Gathering Center in the least amount of time, is also investigated. An O(n log n) time algorithm for finding the Gathering Center in a tree network of n vertices is also presented. We also study the Set to Set Broadcasting Problem, where the messages in one set A of vertices are to be transmitted to all the vertices in another set B of vertices in the least amount of time under the same model. Based on the two algorithms obtained for the broadcasting problem and for the gathering problem, we present an O(n log n) time algorithm to solve the Set to Set Broadcasting Problem in a tree network.

並列關鍵字

Heterogeneous Networks ； Broadcasting ； Tree ； Set to Set ； Telephone Model

參考文獻

[1] A. Bar-Noy and S. Kipnis, Designing broadcasting algorithms in the Postal model for message-passing systems, Math. Systems Theory, 27 (1994), pp. 431V452.

[3] G. Fox, M. Johnson, G. Lyzenga, S. Otto, J. Salmon and D. Walker, Solving Problems on Concurrent Processors, Volume I : General Techniques and Regular Problems, Prentice-Hall, Englewood Cliffs, NJ, 1988.

[4] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, CA, 1979.

[6] Hsun-Ming Lee and Gerard J. Chang, Set to set broadcasting in communication networks, Discrete Applied Mathematics, v.40 n.3, p.411-421, Dec. 14, 1992 [doi¿10.1016/0166-218X(92)90010-8 ].

[7] D. Richards and A. L. Liestman, Generaliazation of broadcasting and gossiping, networks 18(1988) 125-138.