Finding K-Broadcast Centers and K-Broadcast Medians under the Postal Model

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

MOST106-2221-E019-014

Translated Name/計畫中文名

基於郵政模型中的「k-廣播中心點」以及「k-廣播重心點」問題

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

Year

2017

Start date/計畫起

01-08-2017

Expected Completion/計畫迄

31-07-2018

Bugetid/研究經費

578千元

ResearchField/研究領域

資訊科學--軟體

廣播(broadcasting) 問題不僅在演算法領域是一個重要的研究議題，同時在訊息傳遞方面也具有許多實務上的應用。例如：網路通訊協定、分散式系統、以及平行計算等[11,13, 20-22]。在之前科技部計畫中[31-33]，我們已經對於一些廣播相關問題做深入研究與探討並且有一些結果發表在國際會議論文與期刊論文上[37-40]。延續之前的研究成果，我們將在本計畫中更進一步探討兩個在網路通訊協定設計時，實務上經常會發生的問題：基於郵政模型中的「k-廣播中心點」以及「k-廣播重心點」問題。郵政模型(postal model) [2, 3, 8] 是一種在異質性網路架構下的通訊協定模型，容許裝置進行一對多的資料傳輸，也就是當兩個裝置進行資料傳輸的同時，裝置可以自由地與其他的裝置建立起新的連結並傳輸資料。相比於電話模型 (telephone model) [1,6,25,28,36]來說，由於電話模型只容許裝置進行一對一的傳輸，郵件模型的傳輸效率和資源利用率更高，故為目前主流的通訊協定模型。在計畫中，我們將會預設郵件模型做為異質性網路架構下所使用的通訊協定模型。另一方面，k-廣播是指裝置同時間，最多可與k 個裝置建立連結。對於 k-廣播中心問題，我們希望在加權圖T = ( V, E ) 上尋找一個廣播中心，使得將訊息從廣播中心傳給圖形上其它點的最長廣播完成時間(communication time) 為最小。對於 k-廣播重心問題，我們則希望找一個廣播重心使得圖形上所有節點廣播完成時間的和為最小。Harutyunyan 等 [18] 首先在 Networks 期刊提出了「基於電話模型的k-廣播中心問題」，並且在單一權重圖T 上發表了時間複雜度為O(n) 的演算法。在本計畫中，我們首先希望可以改進他們的成果，在加權圖T 上針對「郵政模型中的k-廣播中心點」提出時間複雜度為O(n) 的演算法。然後，根據解決以上問題所得到的知識與經驗，我們將進一步研究「基於郵政模型中的 k-廣播重心點問題」。 The broadcasting problem is not only fundamental in algorithmic graph theory but also practically important in message-passing systems, such as distributed systems for parallel computing, and communication networks; see [11,13,20-22] for books and survey papers. In the previous MOST projects [31-33], we have investigated some open problems related to broadcasting in heterogeneous networks and have published some results in [37-40]. In this project, we further consider two important broadcasting issues: “finding k-broadcast centers under postal model” and “finding k-broadcast medians under postal model”, which play a major role in communication networks. 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, 25, 28, 36], 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. Meanwhile, the k-broadcasting [15,16,18,26,29] is a generalization of classical broadcasting in which the sender is allowed to set up connections to k receivers simultaneously. Given a weighted tree T = (V, E), the k-broadcasting center problem is to find a broadcasting center such that the broadcasting time required to broadcast a message from the center to all vertices in T is minimized. For the k-broadcasting median problem, instead of minimizing the maximum communication time, we minimize the sum of communication times from the median to all vertices in T. Harutyunyan et al. [18] introduced “the k-broadcasting center problem under telephone model” and proposed an 􀜱(􀝊)-time algorithm in Networks. In this project, we plan to generalize the above results by designing an 􀜱(􀝊)-time algorithm under postal model. Then, based on the experience above, we will further try our best to investigate “the k-broadcasting median problem under postal model”.

Keyword(s)

廣播問題
k-廣播中心
k-廣播重心
郵件模型
broadcasting problem
k-broadcast center
k-broadcast median
postal model

DSpace CRIS

Finding K-Broadcast Centers and K-Broadcast Medians under the Postal Model

Details

Description