On greedy construction of connected dominating sets in wireless networks

檔案

日期

2005-12-01

類型

期刊名稱

WIRELESS COMMUNICATIONS & MOBILE COMPUTING

卷期與頁次

第 5 卷第 8 期,頁 927–932

ISSN

1530-8669

語言

英文

摘要

Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP-hard. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same. Copyright (c) 2005 John Wiley & Sons, Ltd.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Li, Y., Thai, M., Wang, F., Yi, C., Wan, P., & Du, D. (2005). On greedy construction of connected dominating sets in wireless networks. WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 5(8), 927–932. https://doi.org/10.1002/wcm.356

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/12991