Set to Set Broadcasting in Heterogeneous Network
Date Issued
2008
Date
2008
Author(s)
Hsiao, An-Chen
Abstract
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.
Subjects
Heterogeneous Networks
Broadcasting
Tree
Set to Set
Telephone Model
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95944024-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):c96fa1e913282322759a9299d016350e