Delay efficient link and aggregation scheduling under physical interference model

Xiaohua Xu, Wei Lou, Xuefeng Liu, Shaojie Tang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

In this work, we design efficient algorithms for scheduling node activities under the physical interference model, to minimize the delay for activating a set of communication links, or for finishing a data aggregation communication task. Given a set of communication links, assume that each link is associated with a positive weight (representing the award of transmission along this link). We consider two problems: the first one is to find an independent set of links with maximum total weight; the second one is to partition all links into independent subsets, such that the number of subsets is minimized. We are the first to develop distributed algorithms with constant approximations for both problems respectively. The other line of this work is to explore the relations between link scheduling and an important practical problem: Minimum Latency Aggregation Scheduling which seeks a shortest schedule for data aggregation in multi-hop wireless networks. By utilizing the algorithmic results for link scheduling, our proposed method can find an aggregation schedule that greatly improves the upper bound on latency, compared to the previous best result.
Original languageEnglish
Title of host publicationProceedings - 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011
Pages421-429
Number of pages9
DOIs
Publication statusPublished - 16 Dec 2011
Event8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011 - Valencia, Spain
Duration: 17 Oct 201122 Oct 2011

Conference

Conference8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011
CountrySpain
CityValencia
Period17/10/1122/10/11

Keywords

  • data aggregation
  • Independent set
  • Link scheduling
  • physical Interference model
  • wireless networks

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Cite this