李德財Lee, Der-Tsai臺灣大學:電子工程學研究所蘇育萱Su, Yu-HsuanYu-HsuanSu2010-07-142018-07-102010-07-142018-07-102009U0001-0208200922283600http://ntur.lib.ntu.edu.tw//handle/246246/189259本論文探討關於在異質性網路 (heterogeneous network) 上的廣播問題 (broadcasting problem) 和群體廣播問題 (multicasting problem)。異質性網路連接不同作業系統和通訊協定的工作站，因此工作站間傳遞訊息的時間不同。異質性網路可以用一個加權圖 G = ( V, E ) 代表，點集 V(G) 代表工作站的集合，邊集E(G) 代表工作站間通訊的集合。邊 (u,v) 的權重 w(u,v) 代表的是工作站間通訊時間。在異質性網路中工作站間的傳輸時間 (transmission time) 是不同的，而且每個工作站有連線時間 (connection time) 藉以設定和其他工作站的訊息傳輸。我們假設通訊傳輸使用 postal 模型，postal 模型假設傳送者 (sender) 需要一個單位的連線時間而且每次只能傳給一個相鄰的接收者 (receiver)。在傳送者設定連線之後，傳送者就可以傳輸訊息給下一個接收者，不管傳送者是否仍在傳輸訊息給前一個接收者。當傳送者完全將訊息傳輸給接收者之後，就完成訊息傳遞。但接收者必須等到傳送者完成訊息傳輸之後，才可以將此訊息傳輸出去。廣播問題是尋找一個廣播中心 (broadcast center)，使得將訊息從廣播中心傳給圖形上其他點的廣播完成時間 (broadcasting time) 為最小。群體廣播問題是廣問題的推廣。群體廣播問題要求在最佳時間內使一個點的子集 (A⊆V(G)) 廣播訊息給另一個點的子集 (B⊆V(G))。在本論文中我們在 postal 模型上分別對廣播問題和群體廣播問題提出線性時間演算法。The thesis concerns the problems related to the broadcasting and multicasting in heterogeneous networks. A heterogeneous network is a network connecting workstations with different operating systems and communication protocols. Thus the times to communicate between any pair of workstations are different. A heterogeneous network is represented by a weighted graph G = (V,E), in which V (G) represents a set of workstations and each edge (u, v) in E(G) represents a connection between two adjacent workstations. The weight of each edge represents the transmission time when transmitting messages between two adjacent workstations. In heterogeneous networks, each communication link may have different message transmission time, and each workstation may have connection time to set up the message transmission. We assume that the message transmission model follows the postal model. The postal model assumes that the sender requires one unit of time to set up the connection with an adjacent vertex. After the sender sets up the connection, the sender is allowed to transmit the messages to set up another connection to the next receiver while the sender is still transmitting the messages to the previous receiver.he message transmission is said to be completed after the sender completes transmitting the messages to the receiver, and the receiver cannot pass the messages until the sender completes the transmission. Moreover, we assume that the message transmission between two adjacent vertices is full-duplex, i.e., the sender and receiver can exchange the messages between them. We consider the broadcasting and multicasting problems in a heterogeneous tree network. The broadcasting problem is to find a broadcast center such that the broadcasting time from the broadcast center to all vertices in T is minimized. The multicasting problem is to broadcast messages from a subset of vertices A in V (T) to another subset of vertices B in V (T) in optimal time such that each vertex in B receives all the messages of the vertices in A. In this thesis, we propose linear-time algorithms for the broadcasting and multicasting problems, respectively, in a heterogeneous tree network following the postal model.Acknowledgements iibstract iiiist of Figures vihapter 1. Introduction 1.1 The Broadcasting and Multicasting Problems 1.2 Contributions 4.3 Organization of Thesis 5hapter 2. Previous Work 6.1 The Broadcasting and Multicasting in Trees 6.2 The Broadcasting and Multicasting in Graphs 7.3 Other Related Work 8hapter 3. Broadcasting in Heterogeneous Networks 9.1 Algorithm BROADCAST 9.2 Correctness and Time Complexity of the Algorithm BROADCAST 12hapter 4. Multicasting in Heterogeneous Networks 23.1 Algorithm MULTICAST 23.2 Correctness and Time Complexity of the Algorithm MULTICAST 24hapter 5. Conclusions and Future Work 30.1 Conclusions 30.2 Future Work 30ibliography 32ita 341851599 bytesapplication/pdfen-US廣播通訊協定異質性網路群體廣播algorithmbroadcastcommunication protocolheterogeneous networkthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/189259/1/ntu-98-R96943111-1.pdf