Efficient algorithms with performance guarantees for geometric problems in wireless networks = 무선 네트워크 환경에서 기하 문제 해결을 위한 효율적인 성능 보장 알고리즘 연구

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 391
  • Download : 0
In recent years, wireless networks have been widely adopted in various application systems: sensor networks, femtocell networks, wireless mesh networks, etc. In the network consisting of static wireless devices, the performance of the network is significantly affected by a coverage problem, a connectivity problem, and an interference problem. In a fact that these problems are closely related to signal ranges and locations of the wireless devices, the problems can be formulated to geometric problems. In this dissertation, we address the following three problems associated with both wireless problems and geometric problems and present efficient algorithms for each problem with performance guarantees. First, we consider two fundamental problems in indoor femtocell networks: data load balancing and coverage problem. In an indoor environment, it is not easy to measure the degree of coverage due to artificial obstacles and building structures. Thus, to achieve maximal coverage, the power assignment algorithm is required regarding indoor environments. In addition, according to time-varying data traffic, the power control algorithm is required to accomplish data load balancing in the femtocell network with multiple base stations. We propose a novel framework exploiting the Voronoi diagram with respect to the radio propagation distance to achieve indoor coverage with minimum power and present a dynamic power control scheme to distribute data loads among base stations without coverage loss using sample point. We extend the centralized power control method to the distributed algorithm for large-scale networks. Moreover, we present an algorithm to cope with the dynamic deletion and insertion of femto base stations. Next, we deal with the connectivity problem caused by structural damages in wireless sensor networks. When the network is disconnected, the base station cannot gather the information from sensors in a sensing field. Thus, an efficient algorithm for a relay node placement is required to recover the connectivity of the network with a minimum cost. The relay node placement problem is indeed closely related to the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STP-MSPBEL) which has been well studied in computational geometry disciplines. In this dissertation, we present the 3-approximation algorithm for STP-MSPBEL in $O(n\log{n})$ time and give the first exact algorithm to provide an optimal Steiner tree for given three points in constant time. By combining these algorithms together, we present another 3-approximation algorithm that runs in $O(n \log{n})$ time with better performance. Finally, we consider a channel assignment problem in IEEE 802.11-based multi-channel, multi-interface wireless networks. Collisions among concurrent transmissions frequently occur in wireless networks due to co-channel interference. When the transmission range, interference range, and carrier sensing range are all different, we investigate the conditions causing hidden terminal, exposed terminal, and co-channel interference problems, which significantly degrade network performance. Based on the conditions, we generate a weighted conflict graph which represents possible conflicts among transmissions. We define the Max $list$-Cut problem and present a 2-approximation algorithm to resolve the channel assignment problem. Furthermore, we provide a 2-approximation algorithm for the topology preserving channel assignment when the channel lists are not given.
Choi, Sungheeresearcher최성희researcher
한국과학기술원 :전산학부,
Issue Date

학위논문(박사) - 한국과학기술원 : 전산학부, 2016.2 ,[vi, 71 p. :]


Geometric problems; Wireless networks; Dynamic power control; Steiner tree with bounded edge-length; Channel assignment; 기하 문제; 무선 네트워크; 동적 파워 조절; 길이 제한을 갖는 스타이너 트리; 채널 할당

Appears in Collection
Files in This Item
There are no files associated with this item.


  • mendeley


rss_1.0 rss_2.0 atom_1.0