In a static multi-hop wireless network, some nodes are chosen as gateways to the Internet while the other nodes cooperatively route traffic in a multi-hop fashion to the Internet through the gateways. Most traffic is directed to and from gateways for Internet access and thus the placement of gateways is critical to the performance and management of the network. A good gateway placement should provide throughput/delay guarantees to users and use wireless bandwidth efficiently. In this thesis, we propose an approach to optimize the gateway selection with QoS requirements such as throughput and delay. The optimization objectives are selecting a minimum number of gateways and balancing the load of gateways while satisfying QoS requirements. We employ collision domains, the sets of contending links sharing the capacity of the same channel, to model accurately the impact of wireless interference on network throughput. Accurate interference estimation increases the efficient use of wireless bandwidth by limiting the number of flows sharing the same channel, and thus it helps ensure throughput requirements to users. Balancing the load of gateways helps reduce contention at heavily-loaded gateways, and hence it increases the network resource utilization efficiency. We formulate the selection problem as a Multi-Objective Linear Program and design an efficient greedy algorithm for it. We extensively evaluate our approach and show that: (1) it satisfies node throughput requirements to a greater extent than do previous approaches; (2) it benefits not only single-radio single-channel networks but also multi-radio multi-channel networks; and (3) the greedy algorithm yields good suboptimal solutions.
본 논문에서 우리는 정지상태의 다중 홉 무선 네트워크에서 대역폭과 지연 요구사항을 만족하는 게이트웨이 선택 문제에 대해 연구하였다. 본 논문의 세 가지 주된 내용은 다음과 같다. 첫째, 본 논문에서는 게이트웨이 선택 문제를 충돌 도메인 모델(collision domain model)과 게이트웨이 부하 분산(gateway load balancing)을 적용하여 수식화하였다. 충돌 도메인 모델은 채널 이용시 충돌 영역내에 있는 링크간 무선 채널 간섭에 따른 간섭 영향을 정확하게 포착하였으며, 본 논문에서 제시하는 방법을 통해 간섭에 따른 영향을 정확하게 추정함으로써, 사용자를 위한 대역폭 요구사항을 좀더 정확하게 평가할 수 있었다. 둘째, 우리는 그리디 기반의 추정 알고리즘(greedy based approximation algorithm)을 제안하였고, 본 논문에서 제시하는 방법을 통해 게이트웨이로 선택된 숫자와 게이트웨이의 부하 분산을 시뮬레이션과 분석을 통해 제안한 알고리즘의 효율성을 평가하였다. 마지막으로, 본 논문에서 제시하는 알고리즘을 다중 전파(multi-radio)와 다중 채널(multi-channel) 환경에 적용할 수 있도록 개선하였다. 본 논문에서 제안한 방법은 무선 메쉬 네트워크(wireless mesh network)나 공동체를 위한 무선 네트워크의 수용량 계획시 도움을 줄 수 있다. 앞으로 본 논문의 남은 과제로서, IEEE 802.11 표준에서 제시하는 물리계층의 스펙을 통합하기 위한 충돌 도메인 모델의 확장과 여러 게이트웨이에 대한 각 노드의 다중 패스의 지원을 통해 장애 허용을 제공하는 그리디 알고리즘의 확장이다.
