Broadcasting P-Center and P-Median Problems in Tree Networks

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

NSC101-2221-E019-065

Translated Name/計畫中文名

樹狀網路上的廣播問題

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=2647402

Year

2012

Start date/計畫起

01-08-2012

Expected Completion/計畫迄

31-07-2013

Bugetid/研究經費

534千元

ResearchField/研究領域

資訊工程--硬體工程

網路通訊協定設計不僅是演算法領域的一個重要課題，同時也具有許多實務上的應用。其中廣播(broadcasting) 問題在網路通訊協定設計上扮演了重要的角色。對於廣播問題，我們希望在加權圖G = ( V, E ) 上尋找一個廣播中心 (broadcasting center) 以及一個最佳的廣播順序 (sequence of calls)，使得將訊息從廣播中心傳給圖形上其他點的廣播完成時間(broadcasting time) 為最小。我們已經在 98 年國科會計畫中 [14] 對於廣播問題做深入的研究與探討，並且將研究成果發表於COCOON 2010 [18] 以及 ISAAC 2011[19] 。延續之前的研究成果，我們將更深入探討一些在網路設計時，實務上經常會產生的問題。例如，廣播重心問題 (broadcasting median)，p-點廣播中心問題 (broadcasting p-center)，p-點廣播重心問題 (broadcasting p-median) 以及限制廣播完成時間下的廣播重心問題。對於廣播重心問題，我們希望尋找一個廣播重心以及一個最佳的廣播順序使得所有點收到訊息的時間和為最小。另一方面，限制廣播完成時間下的廣播重心問題則希望尋找一個廣播重心以及一個最佳的廣播順序使得在所有點收到訊息的時間都小於等於c 的限制下所有點收到訊息的時間和為最小。最後我們將探討當廣播中心或廣播重心有 p 個時，要如何找出這些廣播中心、廣播重心以及最佳廣播方法使得最大廣播完成時間或所有點收到訊息的時間和為最小。這些問題跟著名的p-點中心 (p-centers) 或 p-點重心 (p-medians) 問題有著相當密切的關係。 The design of network communication protocols is not only fundamental in algorithmic graph theory but also practically important in many applications. One of the most important issues in design of communication protocols is the broadcasting problem. 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. Based on the work we have done in the previous NSC project [14], which has been published in COCOON 2010 [18] and ISAAC 2011 [19], we further consider several important broadcasting issues that arise in applications from realistic network design. In this project, we start by topic concerning broadcasting median, which play an important role in the design of communication protocols in various kind of networks. Then, we investigate the broadcasting p-center and p-median problems with p > 1, and broadcasting median problem with bounded communication time. In the broadcasting median problem, instead of minimizing the maximum communication time, we minimize the sum of communication times from the center to all vertices in T. 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 is minimized under the constraint that the maximum communication time is no greater than a given constant value c > 0. The broadcasting p-center problem is a generalization of the broadcasting problem. In the broadcasting p-center problem, we want to locate p centers on a network and partition the set of n vertices in p subsets, such that the maximum broadcasting time from the centers to the associated subsets of vertices is minimized. On the other hand, in the broadcasting p-median problem, instead of minimizing the maximum broadcasting time, we minimize the sum of communication times from the centers to the associated subsets of vertices.

Keyword(s)

演算法
廣播中心
廣播重心
樹狀網路

DSpace CRIS

Broadcasting P-Center and P-Median Problems in Tree Networks

Details

Description