A mobile ad hoc network is a network in which no infrastructure for connectivity exists and participant hosts have a limited wireless transmission range. It allows mobile hosts to set up a temporary network and bears many potential applications including disaster relief, ad-hoc grouping for mobile conference, battle field communications, and so on. A communication is achieved by wireless transmission of a single hop or multi-hop. A wireless link is a shared resource, thus the effective use of a link is a very important issue in mobile ad hoc networks. A well-known scheme is to select some nodes and form a set of gateways, called a virtual backbone (VB). The key issue is to find an algorithm which builds and manages the VB efficiently. The metrics of VB algorithm's $\It{efficiency}$ are the number of messages to build the VB, the number of participating hosts as a member of VB, and the cost to maintain the VB. The smaller the participants of a VB are, the smaller the relaying messages to the destination host are.
The VB consists of two phases: the initial search and connection of related hosts ($\It{initial configuration}$ phase); and management of topology changes by host mobility and (or) failure (simply $\It{configuration management}$ phase). The algorithm to build a VB with the minimum number of participants is the same as the minimum connected dominating set (MCDS) problem, which is known as a NP-hard problem.
Approximation algorithms have focused on how to find a near MCDS at the initial configuration phase, but do not manage effectively the impact of host mobility.
In highly mobile networks, mobility causes frequent configuration changes and the efficient configuration management affects the performance of the VB more than the initial configuration. That is, it is more crucial to reduce the number of messages to manage configuration in the configuration management phase than in the initial configuration phase.
The proposed algorithm builds and manages a VB in the form of a distributed spanning tree concurrently. It may spend more messages than MIS-CDS, when sending messages to the same destination. MIS-CDS is known to be the best by the smaller number of participating hosts in the VB.
However, the proposed algorithm consumes fewer messages than MIS-CDS in terms of the total number of messages required for both initial configuration and mobility management (to the ratio of 2.5).
Two new algorithms as applications are described; a mobility management scheme in mobile ad hoc networks and an energy efficient path finding algorithm in wireless microsensor networks. The proposed algorithm in the mobility management builds a VB of a distributed spanning tree style and reconfigures the changes by mobility, failure, sleep mode, and etc.
The maximum cost to build and manage the VB, i.e. the number of explicitly generated control messages, is 2($\It{N}$-1), $\Theta$($\It{c}$($\It{N}$-1)), where 0 $\lt$ c $\le$ 2, where $\It{N}$ is the total number of hosts in the network. In the mobility management phase the proposed algorithm consumes only one message when a host joins or leaves at the end of configuration, i.e. at a leaf, and ($\It{N}$+1) when a host joins in the center of $\It{N}$ connected network.
The generated number of control messages at both phases is $\It{optimal}$, i.e. the required number of control messages is the minimum. Even though the number of participating hosts as members of the constructed VB is bigger than that of MIS-CDS, the total required number of messages for both phases is smaller. The more the hosts move, the more the difference of generated messages is.
The proposed algorithm is also utilized to find an energy-efficient path in wireless microsensor networks. It constructs an energy-efficient path to the destination host, i.e. the message receiver, in the combined style of both depth-first and breadth-first searches. It generates messages at most 2($\It{N}$-1), O(2($\It{N}$-1)), when the destination host is at the end of the network. The algorithm also builds $\It{k}$ less energy efficient paths, where ($\It{k}$ $\le$ N), which can be utilized as $\It{resilient}$ paths to the destination host. Each host in the proposed algorithm needs only one hop distance neighbors' information, e.g., the host identifier and its role, i.e. a parent or a child of the passed messages, in the configuration.
The proposed algorithm can be used in any situation of no infrastructure, i.e. the virtual backbone is needed, and does not spend more messages than other algorithms.
모바일 네트워크 혹은 센서 네트워크에서는 기존의 유선망에서 존재하는 인프라를 기대할 수 없다. 인프라는 전용 서버 또는 이미 정하여진 (그래서 모두에게 알려진) 기능을 수행하는 호스트와 같은 존재이다. 따라서 인프라가 없는 환경에서는 네트워크를 구성하는 호스트들이 인프라의 기능을 담당하여야 한다. 예를 들면 Multi hop 으로 연결된 호스트 간에 메시지를 주고 받기 위하여는 중간에 연결되는 호스트들이 router 역할을 하여 주어야 한다. 그러나 네트워크에 참여하는 모든 호스트가 그런 기능을 담당하면 여러가지 측면에서 비효율적이다. 특히 무선 대역폭은 공유하는 자원이므로 가능한 적은 수의 호스트가 동시에 접근하여야만 이용을 보장 받을 수 있을 뿐만 아니라 throughput 도 높아지게 된다.
인프라가 없는 네트워크 환경에서는 네트워크에 참여하는 몇 개의 호스트를 선정하여서 특정한 기능을 하게 하는 것이 일반적인 방법이다. 이때 참여하는 호스트가 만드는 네트워크 구성을 가상백본망(virtual backbone)이라고 하며 여기에 속하지 않는 호스트들은 네트워크에 있는 어느 호스트와도 가상백본망을 통하여 통신할 수 있게 된다. 가상백본망에서는 참여하는 호스트를 가능하면 적게 하는 것이 널리 연구되고 있는 주제이다. 주어진 네트워크에서 최소 호스트로 구성되는 가상백본망을 구하는 것은 그래프 상에서는 MCDS(minimum connected dominating set)를 구하는 것과 동일하나 이 문제는 NP-hard 로 알려져 있다. 따라서 MCDS 에 근접한 경우를 구하는 근사치 알고리즘이 많이 연구되고 있다. 현재까지 가장 좋은 근사치를 제공하는 알고리즘은 MIS를 기반으로 하는 CDS (MIS-CDS) 알고리즘으로 알려져 있다.
그러나 MIS-CDS 를 비롯한 많은 연구가 주로 주어진 네트워크에서 최소 참여호스트를 구하는 것에만 집중하고 이동성에 의한 네트워크 재구성에 따른 비용은 간과하고 있다. 아무리 적은 수의 호스트가 참여하는 가상백본망을 만들어 주는 알고리즘이 있다 하여도 이동성이 높은 환경에서는 곧 바로 가상백본망에서 변경된 네트워크 구성 부분을 다시 반영하여야 한다. 따라서 이동성을 얼마나 효율적으로 관리 하느냐가 오히려 더 중요하다고 할 수 있다. 즉 최소 참여 호스트로 구성되는 가상백본망을 구하는 알고리즘은 반드시 이동성이나 다른 이유로 가상백본망이 변경되었을 때 효율적으로 변경 사항을 반영하여 주는 것을 더 고려하여야 한다.
현재까지 제안된 알고리즘은 대부분 처음 가상백본망을 얼마나 효율적으로 구성하느냐에 초점을 맞추고 있다. 여기서 효율성은 사용하는 메시지 수와 가상백본망에 참여하는 호스트 수가 된다. 그러나 이동성에 따른 가상백본망의 변경 사항을 효율적으로 다루지 못한다면 처음 구성할 때의 효율성은 곧 바로 사라지고 오히려 비효율적인 방법이 된다.
본 논문에서는 가상백본망을 구성하고 이동성 등에 의하여 변경 사항이 발생하였을 때 효율적으로 변경 사항을 다루는 알고리즘을 제안하고 있다. 이 알고리즘이 구성하는 가상백본망은 참여 호스트 수는 기존의 최고 근사치 알고리즘인 MIS-CDS 방법보다 더 많은 호스트를 가상백본망에 참여하게 한다. 그러나 이동성이나 다른 사유로 네트워크 구성에 변경이 생겼을 경우는 MIS-CDS 보다 더 적은 수의 메시지를 사용하여서 변경 사항을 가상백본망에 반영한다. 제안한 알고리즘은 초기 가상백본망을 구성할 때 사용하는 메시지 수도 MIS-CDS 보다 적으며, 즉 ($\Theta$($\It{c}$($\It{N}$-1) vs. O($\It{N}$log$\It{N}$), 0 $\lt$ c $\le$ 2), 네크워크 구성 호스트에 변경 사항이 발생하였을 때 변경 사항을 반영하기 위하여 사용되는 메시지 수는 최고 2.5 배까지 차이가 난다. 따라서 이동성이 높은 환경에서는 가상백본망의 참여 호스트 수를 적게 하는 것이 중요한 것이 아니라 이동성을 쉽게 반영하여 주는 것이 더 중요하다는 것을 보여 주었다.
제안한 알고리즘의 응용 사례로서 2 개의 알고리즘을 개발하였다. 하나는MANET 에서의 효율적인 이동성 관리 방법이며 다른 하나는 마이크로 센서 네트워크에서 목적지까지의 최소 에너지를 사용하는 경로를 탐색하는 알고리즘이다. 분석과 simulation 을 수행한 결과 제안한 알고리즘들이 기존의 다른 알고리즘 보다 더 효율적(사용하는 메시지 수, 사용하는 에너지 소모량)이라는 것을 보여 주었다.
향후 연구로서는 네트워크에 참여하는 호스트가 많거나 호스트의 에너지가 제한되어 있을 경우에는 지역적으로 제한되는 가상백본망을 구성하는 것과 호스트의 이동 확률과 머무르는 기간 등을 반영하여서 보다 더 안정적인 가상백본망을 구성하는 방법을 생각할 수 있다.
