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.
최근 무선 네트워크는 센서 네트워크(sensor network), 펨토셀 네트워크(femtocell network), 메쉬 네트워크(mesh network) 등 다양한 응용시스템에 적용되어 활용가치를 크게 높이고 있다. 고정되어 있는 무선 기기들을 이용하여 구성된 무선 네트워크는 커버리지 문제, 연결성 문제, 전파 간섭 문제 등으로 인하여 네트워크 성능이 심각하게 저하될 수 있다. 이러한 문제들은 무선 기기의 신호 범위나 배치되어 있는 위치와 매우 밀접한 관련되어있기 때문에 기하 문제로 나타낼 수 있다. 본 학위논문에서는 무선 문제와 기하 문제가 동시에 연관된 다음 세 가지 문제를 정의하고 이를 해결하기 위한 성능이 보장되고 효율적인 알고리즘들을 제시하고자 한다.
먼저, 실내 환경의 펨토셀 네트워크에서 2가지 핵심적인 문제인 커버리지 문제와 데이터 부하 분산에 관한 연구를 진행하였다. 실내 환경에서는 건물 구조물이나 인공 장애물들로 인하여 커버리지를 정확하게 측정하는데 어려움이 따른다. 따라서 커버리지를 최대로 달성하기 위해서 실내 환경을 고려한 파워 할당 방법이 요구된다. 또한, 다수의 펨토 기지국을 이용하는 네트워크에서 동적인 데이터 트래픽에 따른 기지국들의 데이터 부하를 분산하는 파워 조절 방법이 필요하다. 전파 거리를 고려한 보로노이(Voronoi) 다이어그램을 이용하여 최소 파워로 실내 커버리지를 달성하는 방법을 제안하고 샘플 포인트를 이용하여 커버리지의 손실 없이 기지국의 데이터 부하를 동적으로 분산하는 새로운 방법을 제시한다. 우리는 앞서 개발한 중앙 방식의 파워 조절 방법을 대규모 네트워크에서 사용하기 위해서 분산 방식의 파워 조절 방법을 제시한다. 뿐만 아니라, 팸토 기지국의 동적인 추가 및 삭제에 대응할 수 있는 알고리즘을 제안한다.
다음으로 무선 센서 네트워크에서 다양한 외부환경으로 인해서 대규모로 센서 기기들이 유실되는 경우 발생하는 연결성 문제를 다룬다. 네트워크의 연결이 단절된 경우, 기지국에서는 배치되어 있는 센서로부터 정보를 수집할 수 없게 된다. 따라서 적은 비용으로 네트워크의 연결성을 회복시키는 효율적인 추가 노드 배치방법에 연구가 필요하다. 추가 노드 배치 문제는 계산 기하학 분야에서 오랫동안 연구되어온 길이 제한을 갖고 최소 Steiner point를 이용하여 구성하는 Steiner tree 문제와의 매우 큰 연관성을 보인다. 본 학위논문에서는 이 문제를 해결하는 $O(n\log{n})$ 시간복잡도를 지니는 3-approximation 알고리즘을 제시한다. 또한 3개의 점이 주어졌을 때, 상수 시간에 정확한 해를 구하는 알고리즘을 처음으로 제시한다. 위 두 가지 알고리즘을 통합하여 $O(n\log{n})$ 시간 복잡도를 가지면서 보다 향상된 성능을 보이는 3-approximation 알고리즘을 제안한다.
마지막으로 IEEE 802.11을 기반으로 하는 다중 채널, 다중 인터페이스를 지닌 무선 네트워크에서 발생하는 전파 간섭 문제를 해결하는 채널 할당 방법을 다룬다. 무선 네트워크에서는 동 채널 간섭 문제로 인하여 동시에 진행되는 통신 사이에서 충돌이 자주 발생한다. 통신 거리, 간섭 거리, 센싱 거리가 모두 다른 경우에 네트워크 성능 저하와 밀접한 관련이 있는 간섭(interference) 문제, 은닉 터미널(hidden terminal), 노출 터미널(exposed terminal) 문제가 발생되는 조건을 정의하고 이 조건을 기반으로 발생 가능한 충돌을 표현하는 가중 충돌 그래프를 생성한다. Max $k$-Cut 문제의 변형인 Max $list$-Cut 문제를 새롭게 정의하고 이를 해결하는 2-approximation 알고리즘을 개발하고 가중 충돌 그래프를 활용하여 채널 할당 문제에 적용하는 방법을 제시한다. 또한 채널 리스트가 주어지지 않은 네트워크에서 토폴로지를 유지하는 채널 할당 문제에 대한 2-approximation 알고리즘을 제공한다.
