Broadcasting Problems in Heterogeneous Networks

瀏覽統計 Email 通知 RSS Feed

簡歷

基本資料

Project title

Code/計畫編號

NSC98-2221-E019-029

Translated Name/計畫中文名

異質網路上的廣播問題

Project Coordinator/計畫主持人

Ching-Chi Lin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

College of Electrical Engineering and Computer Science

Website

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

Year

2009

Start date/計畫起

01-08-2009

Expected Completion/計畫迄

31-07-2010

Bugetid/研究經費

559千元

ResearchField/研究領域

資訊工程--硬體工程

網路通訊協定設計不僅是演算法領域的一個重要課題，同時也具有許多實務上的應用。其中廣播 (broadcasting) 問題在網路通訊協定設計上扮演了重要的角色。對於廣播問題，我們希望在加權圖 G = ( V, E ) 上尋找一個廣播中心 (broadcast center) 以及一個廣播方法 (broadcast scheme)，使得將訊息從廣播中心傳給圖形上其他點的廣播完成時間 (broadcast time) 為最小。對於圖形上的每個邊 e∈E，附予權重 w(e)，代表在端點間傳送訊息所需的時間，訊息從任一點傳到另一點稱為一個通話 (a call)。在廣播的過程中，一個點在同一時間只能參與一個通話，且只能與它圖形上相鄰的點通話。廣播中心在一般圖形上已經被證明是屬於 NP-complete 的問題。廣播問題在特殊圖形樹 (tree) 上，已知最好的結果為O(n log n)。在本研究中，我們首先希望設計一個 “不需要排序’’ 的線性時間 (O(n)) 演算法來尋找廣播中心以及廣播方法以求得最短廣播完成時間。然後我們也會探討當廣播中心有p個時，要如何找出這些廣播中心及最佳廣播方法使得廣播完成時間或所有點收到訊息的時間和為最小。這個問題跟著名的 p-中心點 (p-centers) 或p-中位點 (p-medians) 問題有關。之後，我們將考慮邊上的權重為不固定值 (edge uncertainty) 的情況。在真實的網路中，傳輸線上的頻寬是隨時在變化的，因此基於實作上的重要性，有關邊上的權重為不固定值的研究是很有意義的。最後，我們將考量在樹上多重條件 (multi-criteria)的問題，希望在圖形上所有點收到訊息的時間和不大於M的條件下，廣播完成時間為最小。 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), we would like to find a broadcast center and a broadcast scheme such that the broadcast time required to broadcast a message from the center to other vertices in G is minimized. For each edge e∈E, w(e) represents the amount of time required to transmit messages between two end vertices of e. A message transmitting between two vertices is denoted a "call". A vertex can only join one call per unit of time and can only call adjacent vertices. The broadcasting problem has been proved to be NP-complete in general graphs. The best known result for the broadcasting problem in a weighted tree network is an O(nlogn)-time algorithm. In this project, we plan to propose a “non-sorting”, O(n)-time algorithm for finding a broadcast center and a broadcast scheme to minimize the broadcast time. Then we'll also investigate that if we have p broadcast centers, how can we find the location of these centers and design a broadcast scheme to minimize the broadcast time or the sum of broadcast time. These subjects are related to the well known p-centers or p-medians problems. Next, we will consider the broadcasting problem with edge uncertainty. In real networks, the bandwidth available on each edge could vary over time, so the edge uncertainty of this problem has attracted significant research efforts because of their importance for practice. Finally, we'll consider the multi-criteria version of this problem: minimizing the broadcast time such that the sum of receiving time for all vertices in G is not greater than a constant M.

Keyword(s)

廣播中心
廣播方法
p -中心點
p -中位點
不確定性
broadcast center
broadcast scheme
p-medians
p-centers
uncertainty

DSpace CRIS

Broadcasting Problems in Heterogeneous Networks

基本資料

Description