This thesis is concerned with the information dissemination process in a communication network, whereby a message, originated by one vertex, is transmitted to all vertices of the network. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time.
For the case of uniform edge transmission times, a moderate amount of work has been done to date. However, for the nonuniform case, few results have been found in the literature. The main objective of this thesis is to investigate the case of nonuniform edge transmission times.
In a tree-type network, it is shown that a simple ordering policy achieves the minimum broadcast time under the minimax criterion, and based on this, an O(NlogN) algorithm is derived to determine the broadcast center. Two extended models are considered. One is the model with an ACK scheme and the other is the model with due dates.
Broadcasting under the minimum criterion is also considered. The necessary and sufficient conditions is established for the optimal call sequencing in a tree. It is shown that the optimal call sequence is determined by edge transmission times and the sizes of the corresponding subtrees. An O (NlogN) algorithm is designed to determine the broadcast center in a tree under the criterion.
In a general-type network, some heuristics are designed based on the results of the tree-type network and vertex degrees. Through the computer simulation, their performances are evaluated. It is observed that in a sparse that in a sparse network, it is good to transmit a message first to the vertex with the largest number of uniformed neighbors. But it is also observed that in a dense network, one must take account of the eccentricity in determining call sequences.
본 연구는 통신망에서 한 구성원이 갖고 있는 정보를 다른 모든 구성원에 전달하는 정보전파과정을 다루었다. 정보전달 방법에는 여러가지가 있으나 여기에서는 어느 구성원이든 한 번에 한 곳으로부터만 정보를 받거나 한 곳으로만 보낼 수 있고, 이웃하는 구성원끼리만 정보전달을 하는 경우에 대해 고찰하였다.
각 라인에서의 전달시간이 동일한 경우에 대해서는 상당히 많은 연구가 이루어져 왔으나, 동일하지 않은 경우에 대해서는 거의 연구결과가 나와 있지 않다. 본 연구에서는 후자의 경우를 집중적으로 다루었다.
우선, 나무형 통신망의 경우 최소최대(minimax) 기준에 따른 최적 전달 순서를 구하여 브로드캐스트 센터(broadcast center)를 구하는 효과적인 해법을 개발하였다. 이의 확장으로서 정보전달 확인방식 (acknowledgement scheme)을 채택하는 경우와 각 구성원마다 정보를 받아야 할 시한이 있는 경우에 대해서도 최적 전달순서를 구하였다.
두번째로, 나무형 통신망에서 최소합계(minisum) 기준에 따른 최적 전달순서를 구하고, 이 경우의 브로드캐스트 센터를 구하는 해법을 고안하였다. 이 때 최적 순서는 최소최대 기준과는 달리 각 라인에서의 전달시간 및 서브트리의 크기에 의해 결정됨을 알 수 있었다.
마지막으로, 일반형 통신망에 대해서는 발견적 해법을 적용하였다. 전산모의실험을 통해 여러가지 전달 방법에 대한 성능을 평가하였다. 그 결과 라인 밀도(edge density)가 낮은 통신망에서는 이웃하는 구성원 중 정보를 전달해야 하는 이웃을 많이 갖고 있는 순서에 따라 정보전달을 하는 방법이 가장 좋은 것으로 나타났고, 라인 밀도가 높은 통신망에서는 편심률(eccentricity)이 큰 순서에 따라 전달하는 것이 대체적으로 좋은 것으로 관찰되었다.
