Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks
文献类型：期刊论文
| 作者 | Shang, Wei-ping1; Wan, Peng-jun2; Hu, Xiao-dong3
|
| 刊名 | ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
 |
| 出版日期 | 2010 |
| 卷号 | 26期号:1页码:13-22 |
| 关键词 | Broadcast latency wireless ad hoc networks approximation algorithm |
| ISSN号 | 0168-9673 |
| DOI | 10.1007/s10255-008-8806-2 |
| 英文摘要 | A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648(r (max)/r (min))(2) times that of the optimal schedule, where r (max) and r (min) are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most (1 + 2r (max)/r (min))(2) + 32. Moreover, under the proposed scheduling each node just needs to forward a message at most once. |
| 资助项目 | National Natural Science Foundation of China[10531070] ; National Natural Science Foundation of China[10771209] ; National Natural Science Foundation of China[10721101] ; Chinese Academy of Sciences |
| WOS研究方向 | Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000272628300002 |
| 出版者 | SPRINGER HEIDELBERG |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/10905]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Shang, Wei-ping |
| 作者单位 | 1.Zhengzhou Univ, Dept Math, Zhengzhou 450052, Peoples R China 2.IIT, Dept Comp Sci, Chicago, IL 60616 USA 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Shang, Wei-ping,Wan, Peng-jun,Hu, Xiao-dong. Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks[J]. ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,2010,26(1):13-22. |
| APA | Shang, Wei-ping,Wan, Peng-jun,&Hu, Xiao-dong.(2010).Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks.ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,26(1),13-22. |
| MLA | Shang, Wei-ping,et al."Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks".ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES 26.1(2010):13-22. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。