Broadcasting p-Center and Related Problems in Heterogeneous Tree Networks

瀏覽統計 Email 通知 RSS Feed

簡歷

基本資料

Project title

Code/計畫編號

NSC102-2221-E019-038

Translated Name/計畫中文名

異質網路上的 p-點廣播中心及其相關問題

Project Coordinator/計畫主持人

Ching-Chi Lin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Department of Computer Science and Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=3104303

Year

2013

Start date/計畫起

01-08-2013

Expected Completion/計畫迄

31-07-2014

Bugetid/研究經費

499千元

ResearchField/研究領域

資訊工程--硬體工程

廣播 (broadcasting) 問題不僅在網路通訊協定設計方面具有許多實務上的應用，同時在演算法領域也是一個重要的研究議題。我們已經在 98 年以及 101 年國科會計畫中 [11, 12] 對於廣播相關問題做深入的研究與探討。例如，廣播中心問題 (broadcasting center)、廣播重心問題 (broadcasting median) 以及不確定性網路上的廣播中心問題 (broadcasting center with uncertainty)。並且將研究成果發表於 COCOON 2010 [15]、 ISAAC 2011 [17] 及 Journal of Combinatorial Optimization [16]，這些國際知名的會議及期刊。延續之前的研究成果，在本計畫中我們將更深入探討一些在網路設計時，實務上經常會產生的問題。例如，p-點廣播中心問題 (broadcasting p-center)、p- 點廣播重心問題 (broadcasting p-median) 以及限制廣播完成時間下的廣播重心問題。 p-點廣播中心問題以及 p-點廣播重心問題為廣播中心問題與廣播重心問題的一般化。對於廣播中心問題，我們希望在加權圖 G = ( V, E ) 上尋找一個廣播中心 (broadcasting center) 以及一個最佳的廣播順序 (sequence of calls)，使得將訊息從廣播中心傳給圖形上其他點的廣播完成時間 (broadcasting time) 為最小。對於廣播重心問題，我們希望尋找一個廣播重心以及一個最佳的廣播順序使得所有點收到訊息的時間和為最小。我們首先將探討當 p ＝ 2 時，要如何找出兩個廣播中心與兩個廣播重心以及最佳廣播順序使得最大廣播完成時間或所有點收到訊息的時間和為最小。接著我們將探討當 p > 2 時要如何找出這些廣播中心以及廣播重心。最後我們將研究限制廣播完成時間下的廣播重心問題。 Broadcasting is one of the most important operations in message-passing systems, such as distributed and parallel systems, and communication networks. The main objective of this operation is to quickly distribute data from a source vertex to the entire network for processing. In the previous NSC projects [11, 12], we have investigated some open problems related to broadcasting problems, such as the broadcasting center, the broadcasting median problems, and the broadcasting center problem with uncertainty. The results have been published in COCOON 2010 [15], ISAAC 2011 [17], and Journal of Combinatorial Optimization [16]. In this project, we further consider several important broadcasting issues such as the p-center and p-median problems with p > 1, and the broadcasting median problem with bounded communication time. The broadcasting p-center and p-median problems are generalizations of the broadcasting problem and the broadcasting median problem, respectively. Given a weighted graph G = (V, E), the broadcasting center problem is to find a broadcasting center and an optimal sequence of call such that the broadcasting time required to broadcast a message from the center to other vertices in G is minimized. Instead of minimizing the maximum communication time, we minimize the sum of communication times from the center to all vertices in T for the broadcasting median problem. On the other hand, the broadcasting problem with bounded communication time is to find a vertex vV(T) such that the sum of communication time of v in G is minimized under the constraint that the maximum communication time is no greater than a given constant value c > 0. In this project, we start by topic concerning broadcasting p-center and p-median problems with p = 2, which play an important role in the design of communication protocols in various kind of networks. Then, we consider the case when p > 2. Finally, we investigate the broadcasting median problem with bounded communication time.

Keyword(s)

p-點廣播中心
p-點廣播重心
廣播順序
廣播完成時間
p-center
p-median
sequence of call
broadcasting time

DSpace CRIS

Broadcasting p-Center and Related Problems in Heterogeneous Tree Networks

基本資料

Description