Link failures would result in changes in reachability between members, which consequently leads to changes in membership, called a view change. When a link failure for the nodes is suspected, a group leader constructs a new view where suspected nodes are excluded from the existing view. It then transmits it to the currently connected members. To maintain the frequent changes caused by node mobility, the group membership service for MANETs 1) needs to recognize the reachability status of the nodes as accurate as possible and 2) should reduce the meaningless view changes to avoid the capricious view change.
MANET environments are unstable due to the characteristics of MANETs such as node mobility and lack of infrastructure. If the network situation is unstable, the connection between hosts is repeatedly disconnected and reconnected. This situation brings about the frequent view changes. Furthermore the disconnection of multiple nodes rather than a single node is general in MANETs because the communication with far nodes out of a transmission range is possible, only if an intermediate node between the source and destination nodes exists. Therefore the effciency of group membership service in terms of the number of messages and view changes is influenced by how well the network partition is maintained. In this dissertation, we propose a network partition handling scheme based on the reachability estimation for group membership service.
The reachability guarantees nodes to communicate each other and the reachability status are collected using various schemes. The most widely adopted and simple scheme is to broadcast or send to specific nodes messages of reachability status periodically. The existing message exchange-based scheme generates messages periodically even though the reachability status itself does not change. However, although the proposed reachability estimation scheme does not use periodical messages, it provides more accurate information of reachability with less number of messages than the periodical scheme. The reachability estimation is based on the fact: if a node moves within transmission range, i.e., a confined area, the reachability status is the same before movement. To represent the confined area, a virtual grid, i.e. a hypothetical Cartesian coordinates on MANETs, is adopted. In the virtual grid each node calculates how long they stay and exchanges the duration with other nodes to estimate the probable duration of reachability between them.
To handle the network partition in MANETs, we predefine subgroups in a group as exploiting a confined area, i.e., a virtual grid. According to the proximity, neighboring nodes in MANETs can communicate with each other. It means that it is possible to predefine multiple disjoint subgroups within a group. A disjoint subgroup is composed of stable and mutually reachable members. From the result of the reachability estimation scheme, we define a set of regions, called $\It{contiguous regions}$, where all members in the regions are assured to be reachable in the virtual grid by the transitive property. As recognizing members in contiguous regions as one subgroup, the group membership service can construct a hierarchical structure for all members. The hierarchical maintenance scheme handles the partition and merging procedures with the predefined subgroup which is not only a basic partition unit, but also the set of reachability-guaranteed. Consequently, the concept of contiguous regions makes it possible to avoid the capricious view change.
최근 무선 통신을 이용한 모바일 단말기가 보편화 되고 있다. 핸드폰이나 PDA와 같은 이동 단말들은 CPU의 성능 향상, 메모리 용량 증가, 베터리 시간의 증가와 같이 계속 발전하고 있는 상황이다. 사용자들은 장소나 유선환경에 구한되지 않는 무선 단말기를 소지하고 자유로이 활동할 수 있다. 이러한 환경은 인프라스트럭쳐 없이 모바일 단말 간에 통신이 가능한 MANET(Mobile ad hoc networks) 까지 생각하게 되었으며, 최근 몇 년간 MANET에서의 라우팅, QoS(Quality of Service)등에 대해 연구가 진행되고 있다. MANET에서의 경매 시스템과 같이 다중 사용자 간의 모바일 상거래 응용들은 보다 진보된 형태로 그룹 통신 기반 응용의 대표격이라 할 수 있다. 이러한 응용들은 적시에 그리고 정확한 그룹 멤버쉽 정보를 요구한다.
기존의 그룹 멤버쉽 서비스는 뷰(view)라는 형태로 현재 동작하고 있고, 연결성이 존재하는 멤버들의 리스트를 제공한다. 멤버쉽은 가입 탈퇴와 같은 그룹 함수와 멤버의 결함(failure)으로 인해 변하게 되는데, 멤버쉽이 변경될 때마다 그룹 멤버쉽 서비스에는 기존 뷰에 변경사항을 반영하여야 하며 모든 멤버들 사이에 동일한 뷰를 제공하기 위해 새로 변경된 뷰를 현재의 멤버들과 공유해야 한다.
MANET에서의 이동성은 기존 유선 환경에서는 존재하지 않던 특징으로 이로 인한 연결 결함(link failure)이 발생하게 된다. 한편 연결 결함으로 인한 네트워크 단절(network partition)은 그룹 멤버쉽 서비스에 있어서 새로 도출된 문제점은 아니다. LAN 환경에서 동작하는 그룹멤버쉽 서비스를 WAN 환경에 적용할 경우 긴 지연시간(high latency)과 네트워크 혼잡(congestion)등의 원인으로 인해, 연결 결함이 발생했다. 결구 WAN 환경에서 발생하던 빈번한 변경(frequent change)과 불안전성(instability)이라는 문제는 MANET에서도 유사하게 나타나지만, 그 원인에 차이가 있다. MANET환경이 노드 이동성이 존재하고 인프라스트럭처가 없다는 점은 기존의 WAN 환경을 지원하는 그룹 멤버쉽 서비스를 MANTET에서 바로 활용할 수 없게 한다. 예를 들어 WAN에서의 글부 멤버쉽 서비스 연구에서는 특화된 중앙 서버를 활용하는 방식[26]이 있었는데 MANET에서는 중앙 서버를 둔다는 가정이 불가능하다.
연결 결함은 멤버들 사이의 연결성(reachability)을 변경시키며, 이는 뷰 변경을 야기한다. MANET 환경에서의 그룹 멤버쉽 서비스는 빈번한 변경과 불안정성 문제를 해결하기 위해, 1) 가능한 정확한 연결성 정보를 확인할 수 있어야 하며, 2) 뷰 변경 과정동안 연결성의 변화가 없는 멤버들 사이의 뷰를 확보할 수 있어야 한다. 이에 본 연구에서는 이 2가지 문제를 해결하기 위해 연결성 추정 기법과 안정된 하위 그룹을 활용한 계층적 그룹 관리 방식을 제안한다.
기존의 MANET에서의 그룹 멤버쉽 서비스 연구들 [8],[22],[27],[32]은 연결성 변경을 감지하기 위해 주기적으로 메시지를 교환했다. 주기적인 메시지 교환으로 연결성을 파악하는 방식은 메시지 수와 정확도 사이에서 트레이트오프가 있다. 교환 메시지 수가 많으면 많을수록 정확도는 높아지겠지만, 유한한 자원으로 인해 무한의 메시지를 교환할 수 는 없다. 여기서 두 노드가 통신반경 안에 존재한다고 생각해 보자. 이 때 두 노드는 이동 속도와 방향에 상관없이 직접적으로 통신이 가능하다. 이는 두 노드 사이의 연결성은 이들의 절대적인 위치가 아닌 상대적인 위치에 의해 결정된다는 것을 알 수 있다. 게다가 시간이 지났음에도 이들이 통신 반경 내에 존재한다면 연결성은 변화가 없으며 이 때에 연결성 파악을 위해 교환된 메시지는 무의미함을 알 수 있다. 본 연결성 추정 기법에서는 가상격자(virtual grid)를 정의하고 노드가 격자의 한칸에 해당하는 제한된 영역에 머무르는 시간과 해당 영역의 위치 정보를 활용하여, 주기적인 메시지 교환 방식보다 정확한 연결성 정보를 제공하는 방식을 제안했다.
연결성 추정 기법을 통해 가상 격자에 노드가 위치한 해당영역에 머무르는 시간을 기록한 RDmap(Reachable duration map)의 정보를 활용하여 멤버 노드에 대한 멤버쉽을 계층적 구조로 관리할 수 있다. 가상 격자의 한 영역크기는 이웃한 영역의 노드들과 직접적인 통신이 가능하도록 정의했다. 이웃 영역들에 대해 이행(transitive property)규칙을 반복적으로 적용하면 연속적인 영역(contiguous region)은 연속적이지 않은 영역에 비해, 연결성이 유지될 확률이 높다. 이러한 가상 격자의 특성에 따라 하나의 영역을 관리하는 영역 코디네이터(Region coordinator), 그리고 해당 그룹을 관리하는 리더(Leader)를 선출하여 활용함으로서 계측적인 그룹관리를 할 수 있다.
MANET 환경에서는 앞서 언급한 것처럼 빈번한 연결 결함이 발생하는데 이로 인해 그룹은 분할(partition)과 합병(merge)이 반복적으로 발생한다. 이 때 분할하는 단위를 기존의 유선망에서의 그룹 멤버쉽 서비스처럼 멤버 하나로 취급하게 되면 뷰 변경 과정에서 새로운 뷰를 추정하는 작업이 불안정한 연결성으로 인해 반복적으로 일어나게 된다. 이에 본 연구에서는 가상 격자 기반의 계층적 그룹관리에서의 연속 영역을 분할 및 병합 단위로 활용함으로서 개별 멤버를 분할 및 병합 단위로 활용할 때보다 뷰 변경 횟수를 단축할 수 있었다.