Minimum multicast time problem in wireless sensor networks
文献类型：期刊论文
| 作者 | Zhu, Jianming; Chen, Xujin ; Hu, Xiaodong
|
| 刊名 | WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS
 |
| 出版日期 | 2006 |
| 卷号 | 4138页码:490-501 |
| ISSN号 | 0302-9743 |
| 英文摘要 | Given an undirected graph representing a network of processors, and a source node needs to broadcast a message to all other nodes in the graph, the minimum broadcast time problem is to find a scheme that accomplishes the broadcast in a minimum number of time steps under the constraint that at each time round, any node can send the message to at most one of its neighbors in the network. This NP-complete problem has been extensively studied in literature. In this paper, we consider a generation of the minimum broadcast problem, the minimum multicast time problem, in unit disk graphs which model wireless sensor networks. The goal is to multicast a message from the source node to a set of specified sensor nodes of the network in a minimum number of time rounds. We prove that this problem is NP-complete, and give an O(1)-approximation algorithm for it. Our simulation results show that the practical performance of the proposed algorithm is much better than the theoretically proved approximation ratio. |
| WOS研究方向 | Computer Science ; Telecommunications |
| 语种 | 英语 |
| WOS记录号 | WOS:000240084000047 |
| 出版者 | SPRINGER-VERLAG BERLIN |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/2494]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Zhu, Jianming |
| 作者单位 | Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhu, Jianming,Chen, Xujin,Hu, Xiaodong. Minimum multicast time problem in wireless sensor networks[J]. WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS,2006,4138:490-501. |
| APA | Zhu, Jianming,Chen, Xujin,&Hu, Xiaodong.(2006).Minimum multicast time problem in wireless sensor networks.WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS,4138,490-501. |
| MLA | Zhu, Jianming,et al."Minimum multicast time problem in wireless sensor networks".WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS 4138(2006):490-501. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。