基於郵政模型在權重樹上的p-廣播中心問題

Abstract

本論文的主要目的是解決在郵政模型中權重樹上的 p-廣播中心問題。郵政模型是 眾多通訊網路模型之一，主要特色是任一節點想要將訊息傳給鄰居節點之前，必 須先花費 α 的時間先進行連線，而節點同時間只能和一個鄰居節點進行連線，但 節點可以同時與所有已經連線的鄰居節點傳遞訊息。這裡我們討論的通訊網路是 一個邊權重樹，其中邊的權重表示訊息經由這條邊傳遞不包含連線所需要花費的 時間。廣播中心是指那些一開始就擁有訊息的節點;廣播問題是要決定能使得網 路上所有節點都收到訊息的時間最短的廣播中心擺放位置;而 p 廣播中心問題是 指給定廣播中心的數量 p，要決定能使得網路上所有節點都收到訊息的時間最短 的 p 個廣播中心的擺放位置。 本論文提出兩個演算法:第一個演算法用來計算在給定一個時間限制 t 之下， 一個給定的樹狀網路最少需要幾個廣播中心、並且決定這些廣播中心的擺放位 置;第二個演算法用來計算在給定廣播中心數量 p 之下，一個給定的樹狀網路的 最短廣播時間。其中第一個演算法使用了貪進法以及動態規劃，依序由小子樹的 最佳解建構出大子樹的最佳解，時間複雜度為 O(n2)。第二個演算法先找出所求 最短廣播時間的候選集合，再將第一個演算法當作工具配合二分搜尋法，逐步 從候選集合中刪除掉不要的元素，最終找到所求最短廣播時間，時間複雜度為 O(n2 log n)。 利用第二個演算法得到最短廣播時間之後，再將其代回第一個演算法作為時間 限制，即可求得 p 個廣播中心的位置以及每個節點的傳訊給鄰居節點的順序，將 p-廣播中心問題解決。

The main purpose of this thesis is to solve p-center problem in a weighted tree under the postal model. The postal model is one of communication network models. In the postal model, every node should spend α time to set up connection with one of its neighbor node before transmitting message. Moreover, every node can only set up connection with one neighbor node at the same time, but can transmit message to all neighbor nodes that have connection set with simultaneously. The communication network we talk about is a edge- weighted tree, where weight of an edge represents the transmission time (not including the time to set up connection) through this edge. The broadcasting centers are those nodes in the network that initially own the message to be broadcast, the broadcasting problem is to determine the minimum time required and location of broadcasting center such that message is broadcast to all nodes in the network, and the p-center problem is to determine, given the number of broadcasting centers p, the minimum time required and location of the p centers such that message is broadcast to all nodes in the network. In this thesis, two algorithms are proposed: the first algorithm is to determine, given the time constraint t, the minimum number of broadcasting centers together with their lo- cations such that message is broadcast to all nodes in a given tree network; the second algorithm is to determine, given the number of broadcasting centers p, the minimum time required such that message is broadcast to all nodes in a given tree network. In the first algorithm, we use greedy method and dynamic programming to construct solution of bigger subtree from solutions of smaller subtrees in time complexity O(n2). In the second algorithm, we collect a set of candidates of minimum broadcast time first, then iteratively remove unwanted elements in the set; finally, only the solution would remain. Its time complexity is O(n2 log n). To solve the p-center problem, we use the second algorithm to determine the minimum broadcast time first, then plug the obtained time into the first algorithm as time constraint. Location of the p broadcast centers together with the transmission order of each node would then be determined.