Efficient Deployment of Base Stations in Wireless Communication Networks

In the design of wireless communication networks, we may have to interconnect n stations locating at given points in the plane such that the distance among each stations is as small as possible by introducing at most k extra stations subjective to a budget limit. In this paper, our goal is to determ...

Full description

Saved in:
Bibliographic Details
Main Authors: Li, Zimao, Wang, Yingying, Ma, Maode
Other Authors: School of Electrical and Electronic Engineering
Format: Article
Language:English
Published: 2016
Subjects:
Online Access:https://hdl.handle.net/10356/81679
http://hdl.handle.net/10220/40909
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-81679
record_format dspace
spelling sg-ntu-dr.10356-816792020-03-07T13:56:08Z Efficient Deployment of Base Stations in Wireless Communication Networks Li, Zimao Wang, Yingying Ma, Maode School of Electrical and Electronic Engineering Wireless communication networks bottleneck Steiner tree In the design of wireless communication networks, we may have to interconnect n stations locating at given points in the plane such that the distance among each stations is as small as possible by introducing at most k extra stations subjective to a budget limit. In this paper, our goal is to determine the locations of the extra k stations interconnecting the existing n stations to minimize the longest distance among stations. This is so-called bottleneck Steiner tree problem, which also has applications in VLSI routing, WDM optical networks design and phylogenetic tree reconstruction. The problem has been proved to be NP-hard and cannot be approximated in the performance ratio 2 in polynomial time in both Euclidean and rectilinear plane and approximation algorithms in the best possible performance ratios presented for the problem in both planes. In this paper, we improve the time complexity of the approximation algorithms and conduct simulations to demonstrate the validness of our improvements. Published version 2016-07-12T01:25:02Z 2019-12-06T14:35:58Z 2016-07-12T01:25:02Z 2019-12-06T14:35:58Z 2016 Journal Article Li, Z., Wang, Y., & Ma, M. (2016). Efficient Deployment of Base Stations in Wireless Communication Networks. Journal of Communications, 11(6), 609-615. 1796-2021 https://hdl.handle.net/10356/81679 http://hdl.handle.net/10220/40909 10.12720/jcm.11.6.609-615 en Journal of Communications © 2016 Journal of Communications. This paper was published in Journal of Communications and is made available as an electronic reprint (preprint) with permission of Academy Publisher. The published version is available at: [http://www.jocm.us/index.php?m=content&c=index&a=show&catid=162&id=996]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. 7 p. application/pdf
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Wireless communication networks
bottleneck Steiner tree
spellingShingle Wireless communication networks
bottleneck Steiner tree
Li, Zimao
Wang, Yingying
Ma, Maode
Efficient Deployment of Base Stations in Wireless Communication Networks
description In the design of wireless communication networks, we may have to interconnect n stations locating at given points in the plane such that the distance among each stations is as small as possible by introducing at most k extra stations subjective to a budget limit. In this paper, our goal is to determine the locations of the extra k stations interconnecting the existing n stations to minimize the longest distance among stations. This is so-called bottleneck Steiner tree problem, which also has applications in VLSI routing, WDM optical networks design and phylogenetic tree reconstruction. The problem has been proved to be NP-hard and cannot be approximated in the performance ratio 2 in polynomial time in both Euclidean and rectilinear plane and approximation algorithms in the best possible performance ratios presented for the problem in both planes. In this paper, we improve the time complexity of the approximation algorithms and conduct simulations to demonstrate the validness of our improvements.
author2 School of Electrical and Electronic Engineering
author_facet School of Electrical and Electronic Engineering
Li, Zimao
Wang, Yingying
Ma, Maode
format Article
author Li, Zimao
Wang, Yingying
Ma, Maode
author_sort Li, Zimao
title Efficient Deployment of Base Stations in Wireless Communication Networks
title_short Efficient Deployment of Base Stations in Wireless Communication Networks
title_full Efficient Deployment of Base Stations in Wireless Communication Networks
title_fullStr Efficient Deployment of Base Stations in Wireless Communication Networks
title_full_unstemmed Efficient Deployment of Base Stations in Wireless Communication Networks
title_sort efficient deployment of base stations in wireless communication networks
publishDate 2016
url https://hdl.handle.net/10356/81679
http://hdl.handle.net/10220/40909
_version_ 1681048197576785920