Research on the Repeater Optimization Based on Voronoi Model


Article Preview

This paper propose a two-tiered network in which lower-power users communicate with one another through repeaters, which amplify signals and retransmit them, have limited capacity, and may interfere with one another if their transmitter frequencies are close and they share the same private-line tone. Motivated by cellular networks, this paper gives a naive solution where the number of repeaters and their positions can be obtained analytically. In a circular area with radius 40 miles, 12 repeaters can accommodate 1,000 simultaneous users. This paper further propose an iterative refinement algorithm consisting of three fundamental modules that draw the Voronoi diagram, determine the centers of the circumscribed circles of the Voronoi regions, and escape the local optimum by using external optimization. The algorithm obtains a solution with 11 repeaters, which we prove to be the absolute minimum. For 10,000 users, it uses 104 repeaters, better than the naive solution's 108.



Advanced Materials Research (Volumes 588-589)

Edited by:

Lawrence Lim




B. T. Liu et al., "Research on the Repeater Optimization Based on Voronoi Model", Advanced Materials Research, Vols. 588-589, pp. 802-805, 2012

Online since:

November 2012




[1] Akyildiz, I.F., W. Su, Y. Sankarasubramaniam, and E. Cayirci. 2002. Wire- less sensor networks: A survey. Computer Networks 38: 393–422.


[2] Aurenhammer, F. 1991. Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Computing Surveys 23: 345–405.


[3] Bak, P., and K. Sneppen. 1993. Punctuated equilibrium and criticality in a simple model of evolution. Physical Review Letters 71: 4083.


[4] Balanis, C.A. 2005. Antenna Theory: Analysis and Design. 3rd ed. New York: Wiley.

[5] Boettcher, S., and A.G. Percus. 2001. Optimizationwith extremal dynamics. Physical Review Letters 86: 5211.

[6] Das, G.K., S. Das, S.C. Nandy, and B.P. Sinha. 2006. Efficient algorithm for placing a given number of base stations to cover a convex region. Journal of Parallel and Distributed Computing 66: 1353.