Broadcasting P-Centers in a Weighted Tree(1/2)

瀏覽統計 Email 通知 RSS Feed

簡歷

基本資料

Project title

Code/計畫編號

MOST109-2221-E019-050-MY2

Translated Name/計畫中文名

權重樹上的 p-廣播中心問題(1/2)

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

Year

2020

Start date/計畫起

01-08-2020

Expected Completion/計畫迄

31-07-2021

Bugetid/研究經費

788千元

ResearchField/研究領域

資訊科學--軟體

Broadcasting is a fundamental and important operation in communication networks. It delivers data packets from one or more (source) nodes to all other (destination) nodes. With different objectives, there are two kinds of source nodes, named centers and medians, for broadcasting. When centers are selected as source nodes, the broadcasting can be completed with minimum time delay. Instead, when medians are selected as source nodes, the overall time delay for each node to receive data packets can be minimized. There are two commonly used communication models, i.e., the telephone model and the postal model. The postal model [2, 3, 8] is a communication protocol, which assumes the sender requires connection time to set up a connection. After the sender sets up the connection, the sender is allowed to set up another connection to the next receiver while the sender is still transmitting the messages to the current receiver. In contrast to the postal model is the telephone model [1, 6, 20, 23, 32], in which the sender is allowed to set up another connection to the next receiver only after completing the transmission of messages to the current receiver. Therefore, the postal model is more efficient and high utilization. Hence, we adopt the postal model for data transmission in this project.Because the communication time and the broadcasting sequence must be considered at the same time, both finding a single center and finding a single median in a general graph are known to be NP-hard. In the previous MOST projects [26-29], considering a tree network, we have successfully found its broadcasting center, broadcasting 2-centers, broadcasting median and broadcasting 2-medians in polynomial time. The results have been published in COCOON [33], ISAAC [36], J. Comb. Optim [35], and Theor. Comput. Sci. [34], respectively. In this project, we further consider two important broadcasting issues:``broadcasting p-centers problem'' and ``broadcasting median with constraint''. Su et al. [34] introduced ``broadcasting center problem under the postal model'' and proposed an O(n)-time algorithm in Theor. Comput. Sci. In the previous MOST project [28], we have also successfully found broadcasting 2-centers in O(n) time. In this project, we plan to generalize the above results by designing a polynomial-time algorithm for ``broadcasting p-centers problem''. Then, based on the experience above, we will further try our best to investigate ``broadcasting median with constraint''. 廣播是指在網路中將資料從一個或多個來源節點 (source vertex) 快速的將訊息傳送到整個網路。根據不同的目標，來源節點可分為廣播中心 (broadcasting center) 或廣播重心 (broadcasting median)。當廣播中心被選為來源節點時，我們希望最晚收到訊息之節點其收到訊息之時間延遲要最小化。另一方面，若是廣播重心被選為來源節點，我們則希望所有節點收到訊息之時間延遲總和要最小化。廣播過程中的資料傳輸有兩種主要模式:郵政模式 (postal model) 與電話模式 (telephone model)。郵政模型 [2, 3, 8] 是一種在異質性網路架構下的通訊協定模型，容許裝置進行一對多的資料傳輸，也就是當兩個裝置進行資料傳輸的同時，裝置可以自由地與其他的裝置建立起新的連結並傳輸資料。相比於電話模型 [1, 6, 20, 23, 32] 來說，由於電話模型只容許裝置進行一對一的傳輸，郵件模型的傳輸效率和資源利用率更高，故為目前主流的通訊協定模型。在計畫中，我們將會預設郵件模型做為通訊協定模型。由於必須同時考慮通訊協定的溝通時間以及廣播順序，在一般圖形上尋找單一廣播中心問題以及尋找單一廣播重心都已被證明是 NP-hard。在前期的科技部計畫中 [26-29]，我們已成功地在多項式時間找到權重樹上的單一廣播中心、雙廣播中心、廣播重心以及雙廣播重心。並且將研究成果發表於 COCOON [33]、 ISAAC [36]、 J. Comb. Optim. [35] 及 TCS[34]，這些國際知名的會議及期刊。延續之前的研究成果，我們將在本計畫中更進一步探討網路通訊協定設計時，實務上經常會產生的兩個問題：「p-廣播中心問題」以及「限制廣播完成時間下的廣播重心問題」。Su 等人 [34] 首先提出了基於郵件模型的「廣播中心」問題，並且在權重樹 T 上發表了時間複雜度為 O(n) 的演算法。另一方面，在之前科技部計畫中 [28]，我們也已成功地設計出演算法，可以在 O(n) 時間內找到權重樹上的雙廣播中心。在本計畫中，我們首先希望可以延續之前的成果，一樣在郵政模型下深入探討「p-廣播中心問題」，並提出多項式時間複雜度的演算法。然後，根據解決以上問題所得到的知識與經驗，我們將進一步探討「限制廣播完成時間下的廣播重心問題」。

Keyword(s)

廣播中心
廣播重心
郵政模式
電話模式
最小時間延遲
broadcasting center
broadcasting median
postal model
telephone model
minimum time delay.

DSpace CRIS

Broadcasting P-Centers in a Weighted Tree(1/2)

基本資料

Description