There are currently two variations of mobile wireless networks. One is a cellular network and the other is an ad hoc network.
In a cellular network, a mobile node should be directly connected to the base station that is within its communication radius. Hence, the communication coverage of the network is limited around base stations. Moreover, the service rate is high because the construction of infrastructures takes large cost and long time. In an ad hoc network, our major concerns, a mobile node randomly moves and communicates with each other over radio. Hence, an ad hoc network does not require any infrastructure and reduces overall costs. But, it’s hard to provide stable communications in an ad hoc network because network topology changes dynamically.
The primary objective of this thesis is to provide a route for high quality communications. This objective can be achieved by providing a quality estimation model and a route search algorithm. Hence, this thesis proposes both a link stability estimation model and qualified route search algorithms.
Firstly, an enhanced link stability estimation model for wireless ad hoc networks is presented. Most routing algorithms for ad hoc networks find the shortest hop route that is, however, very unstable especially in highly dense networks. Some routing protocols such as Signal Stability based Adaptive routing (SSA) and Associativity Based Routing (ABR) were proposed to find more stable route by considering the link stability. SSA determines link stability from the current link state, and ABR determines from link history. In this thesis, we will propose Advanced signal Strength Based estimation Model (ASBM) and compare the proposed model with previous models. In the comparison, the route with ASBM has the longest lifetime with little increase in hop-length. The ASBM route has 2 times longer lifetime than the shortest path route.
Secondly, two distributed route search algorithms will be presented to search a qualified route in wireless ad hoc networks. The Minimum Weight Search (MWS) finds shortest path in the weighted ad hoc network. The weights of each links would be certain cost and the shortest path will minimize the sum of link cost. In the extensive simulation, we applied MWS for power aware routing and route stability routing. The comparison with Dynamic Source Routing (DSR) shows that MWS reduces the transmission power consumption by 20% in power aware routing and increases the route lifetime by 80% in stable routing respectively. MWS can be applied to many other applications by simply changing the link weight assignment function. The Multiple Grade Search (MGS) quantizes the route quality into discrete grades and finds the highest-grade route available. MGS is applied to more complex problems that the MWS can’t handle. However, MGS can’t find the best quality route and the procedures are more complex than MWS. In the simulation, MGS searches a route that satisfies requested bandwidth. The result shows that MGS successfully distributes traffic loads and reduces packet dropping-rate by 10% than ordinary DSR. Proposed MWS and MGS do not require additional control packets during route search process; they only require little more search time.
In this thesis we do not urge which route is the best because the meaning of the best route is different in each condition. However, if the route quality is represented by a single function, the proposed MWS and MGS will find the route with high quality. The qualified route can be used to provide more stable communication between mobile nodes and to enhance overall network performance. Eventually it will fully support QoS with resource reservation mechanism in near future.
무선 망은 현재 두 가지 형태로 나눌 수 있다. 하나는 셀룰러 (cellualr) 망이고, 다른 하나는 에드혹 (ad hoc) 망이다.
셀룰러 망에서는 이동 단말이 통신 반경 내의 기지국과 연결되어 있다. 이로 인해서, 이동 단말이 이동할 수 있는 범위는 기지국 주변으로 한정된다. 또한 기지국과 같은 시설물을 사용하므로, 사용료가 비싸고 이러한 기지국을 설치 하는데 많은 비용과 시간이 드는 단점이 있다.
본 논문의 관심사인 에드혹 망에서는 이동 단말이 자유롭게 움직이며 주변의 다른 이동 단말과 직접 통신을 한다. 그러므로, 에드혹 망 에서는 기지국과 같은 시설물이 불필요하며, 서비스 요금이 저렴하다. 그러나 에드혹 망의 동적 토폴로지로 인하여 안정적인 통신을 제공하는데 어려움이다.
본 논문의 목적은 에드혹 망에서 고품질의 통신을 위한 경로를 제공하는데 있다. 이러한 목적을 달성하기 위하여, 링크 안정성 추정 모델과, 조건부 경로 탐색 기법을 제시하고자 한다.
첫째로, 향상된 링크 안정성 추정 모델을 제시한다. 에드혹 망을 위한 대부분의 라우팅 알고리즘을 최단 경로를 찾는다. 그러나 이러한 경로는 고 밀도 망에서 매우 불안정한 특성을 갖는다. 신호 안정성 기반 적응 라우팅(Signal Stability based Adaptive Routing) 과 상관성 기반 라우팅 (Associativity Based Routing) 같은 몇몇 라우팅은 링크의 안정성을 고려하여 좀더 안정된 경로를 찾는다. 신호 기반 적응 라우팅은 링크의 현재 상태만을 고려하여 링크의 안정성을 판단하며, 상관성 기반 라우팅은 링크의 히스토리 기반으로 링크 안정성을 판단하다. 본 논문에서는 향상된 신호 세기 기반 추정 모델을 제시하고, 앞서 제시된 모델들과 성능을 비교한다. 비교 결과, 제시된 향상된 신호 기반 추정 모델 (Advanced Signal Strength based Estimation Model) 에 의한 경로는 약간의 길이 증가가 있으나 수명이 매우 증가한 것을 볼 수 있으며, 이는 최단 경로의 수명에 2배에 해당한다.
두 번째로, 에드혹 망에서 특정 조건을 만족하는 경로를 찾는 두 개의 분산 경로 탐색 방식을 제시한다. 최소 가중치 탐색 (Minimum Weight Search) 는 가중치 에드혹 망에서 최소 가중치 경로를 찾는다. 각 링크의 가중치는 각 경로의 비용이 되고, 최소 가중치 경로는 전체 경로의 가중치 합을 최소화 한다. 시뮬레이션 에서, 최소 가중치 탐색을 전력량 고려 경로 탐색과, 안정 경로 탐색에 적용하였고, 그 결과, 최소 가중치 탐색은 동적 소스 라우팅 (Dynamic Source Routing) 과 비교에서 20%의 전송 전력을 아낄 수 있었고, 80%의 수명 향상을 가져왔다. 최소 가중치 탐색은 가중치 함수를 바꿈으로써 다양한 문제에 적용될 수 있다. 다중 등급 탐색 (Multi-Grade Search) 은 경로의 품질을 다수의 등급으로 양자화 하여 최고 등급의 경로를 찾는다. 이때의 경로는 최고 품질이 아닌 최고 등급으로서 최소 가중치 탐색과는 다른 경로이다. 다중 등급 탐색은 최소 가중치 탐색이 다루지 못하는 좀더 복잡한 문제에 적용 할 수 있다. 그러나 동작이 더 복잡하고, 최고 품질 경로를 찾지 못하는 단점이 있다. 모의 실험에서 다중 등급 탐색을 이용하여 최대 대역폭 등급 경로를 찾았으며, 결과는 다중 등급 탐색이 대역폭 경로를 제공하여 통신 량이 네트워크 전체에 고루 분산된 것을 볼 수 있으며, 패킷 손실률이 동적 소스 라우팅에 비하여 10% 감소한 것을 보여준다. 제시된 최소 가중치 탐색과 다중 등급 탐색은 추가적인 제어 패킷을 요구하지 않으며 경로 탐색 시간의 증가도 기존 방식과 비교하여 크지 않다.
앞서 제시된 조건부 경로 탐색 방식은 에드혹 망에서 향상된 품질을 제공하여 망의 성능을 증가시켰다. 또한, 가까운 미래에 조건부 경로 탐색 방식은 자원 할당 기능을 추가하여 통신 품질 보장을 완전히 제공할 것이다.
