Affordable Access

Publisher Website

Homogeneous 2-hop broadcast in 2D

Authors
Journal
Computational Geometry
0925-7721
Publisher
Elsevier
Publication Date
Volume
43
Issue
2
Identifiers
DOI: 10.1016/j.comgeo.2009.06.005
Keywords
  • Range Assignment
  • Broadcast
  • Mobile Communication
  • Algorithm
Disciplines
  • Computer Science

Abstract

Abstract In this paper, two variations of the minimum cost homogeneous range assignment problem for 2-hop broadcast from a given source are considered. A set S = { s 0 , s 1 , … , s n } of radio stations are pre-placed in R 2 , and a source station s 0 (say) is marked. In our first problem, the objective is to find a real number r such that 2-hop homogeneous broadcast from s 0 is possible with range r, and the total power consumption of the entire network is minimum. In the second problem, a real number r is given and the objective is to identify the smallest subset of S for which range r can be assigned to accomplish the 2-hop broadcast from s 0 , provided such an assignment is possible. The first problem is solved in O ( n 2.376 log n ) time and O ( n 2 ) space. For the second problem, a 2-factor approximation algorithm is proposed that runs in O ( n 2 ) time and O ( n ) space.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments