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

More articles like this

2D O(3) + 2D QG

Oct 04, 1993

D2 to D2

Jun 12, 2008

D2 or not D2?

on Alcoholism Clinical and Experi... August 1992

2D or not 2D

on Current Opinion in Chemical Bi... Jan 01, 2001
More articles like this..