Minimum-latency broadcast scheduling in wireless Ad Hoc networks

被引：59
|
作者：
Huang, Scott C. -H. [1 ]
Wan, Peng-Jun [1 ,2 ]
Jia, Xiaohua [1 ]
Du, Hongwei [1 ]
Shang, Weiping [3 ]
机构：
[1] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
[2] IIT, Dept Comp Sci, Chicago, IL USA
[3] Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China
来源：
INFOCOM 2007, VOLS 1-5 | 2007年
关键词：
D O I：
10.1109/INFCOM.2007.91
中图分类号：
TM [电工技术]; TN [电子技术、通信技术];
学科分类号：
0808 ; 0809 ;
摘要：
A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. This paper studies the problem Minimum-Latency Broadcast Scheduling (MLBS) in wireless ad hoc networks represented by unit-disk graphs. This problem is NP-hard. A trivial lower bound on the minimum broadcast latency is the radius R of the network with respect to the source of the broadcast, which is the maximum distance of all the nodes from the source of the broadcast. The previously best-known approximation algorithm for MLBS produces a broadcast schedule with latency at most 648R. In this paper, we present three progressively improved approximation algorithms for MLBS. They produce broadcast schedules with latency at most 24R - 23, 16R - 15, and R + O (log R) respectively.
引用
收藏
页码：733 / +
页数：2
相关论文
共 50 条
  • [21] An Energy-Efficient Distributed Algorithm for Minimum-Latency Aggregation Scheduling in Wireless Sensor Networks
    Li, Yingshu
    Guo, Longjiang
    Prasad, Sushil K.
    2010 INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS ICDCS 2010, 2010,
  • [22] Minimum Latency Broadcast Scheduling in Duty-Cycled Multihop Wireless Networks
    Jiao, Xianlong
    Lou, Wei
    Ma, Junchao
    Cao, Jiannong
    Wang, Xiaodong
    Zhou, Xingming
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2012, 23 (01) : 110 - 117
  • [23] Minimum-Latency Gossiping in Multi-hop Wireless Networks
    Huang, Scott C. -H.
    Du, Hongwei
    Park, E. -K.
    MOBIHOC'08: PROCEEDINGS OF THE NINTH ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING, 2008, : 323 - 330
  • [24] Sleeping Schedule Aware Minimum Transmission Broadcast in Wireless Ad Hoc Networks
    Hong, Jue
    Li, Wenzhong
    Lu, Sanglu
    Ca, Jiannong
    Chen, Daoxu
    PROCEEDINGS OF THE 2008 14TH IEEE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, : 399 - +
  • [25] Erratum: Minimum-Energy Broadcast in Static Ad Hoc Wireless Networks
    P.-J. Wan
    G. CĂlinescu
    X.-Y. Li
    O. Frieder
    Wireless Networks, 2005, 11 : 531 - 533
  • [26] Distributed Strategies for Minimum-Latency Cooperative Retransmission in Wireless Networks
    Xiong, Lixiang
    Libman, Lavy
    Mao, Guoqiang
    2009 IEEE 34TH CONFERENCE ON LOCAL COMPUTER NETWORKS (LCN 2009), 2009, : 530 - +
  • [27] Memetic algorithm for minimum energy broadcast problem in wireless ad hoc networks
    Arivudainambi, D.
    Rekha, D.
    SWARM AND EVOLUTIONARY COMPUTATION, 2013, 12 : 57 - 64
  • [28] Minimum-energy broadcast routing in static ad hoc wireless networks
    Wan, PJ
    Calinescu, G
    Li, XY
    Frieder, O
    IEEE INFOCOM 2001: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS: TWENTY YEARS INTO THE COMMUNICATIONS ODYSSEY, 2001, : 1162 - 1171
  • [29] Minimum energy-cost broadcast routing in ad hoc wireless networks
    Li, DY
    Liu, H
    Jia, XH
    GLOBECOM'03: IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, VOLS 1-7, 2003, : 367 - 371
  • [30] Minimizing broadcast latency and redundancy in ad hoc networks
    Gandhi, Rajiv
    Mishra, Arunesh
    Parthasarathy, Srinivasan
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2008, 16 (04) : 840 - 851
12345