Neighbor Discovery Schemes for Multichannel Wireless Networks and Opportunistic Networks

Abstract

최근에, 기회 네트워크 (opportunistic network)나 인지 네트워크 (cognitive network)와 같은 새로운 유형의 이동 애드혹 네트워크 (mobile ad hoc network) 가 많은 관심을 받고 있다. 군사, 차량, 의료, 멀티미디어 전송 등 다양한 서비스에 응용될 수 있다. 이러한 네트워크는 일반적으로 기간 통신없이 자가 구성 (self-configuration) 을 할 수 있어야 한다. 이 자가 구성의 제일 첫번째 단계가 이웃 탐색이다. 전송거리 내에 있는 두 노드들은 데이타를 교환하기 전에, 서로를 인식하고 연결을 설정해야 한다. 만약 서로를 인식하지 못한다면, 통신 기회를 놓치게 되고, 전송 지연이 길어져 결국 데이타 전송을 하지 못하게 된다. 이웃 탐색하는 방법을 찾는 것은 노드들이 서로 언제 얼마나 오랫동안 만날지 모르기 때문에 상당히 어려운 문제이다. 본 연구에서는 분산적 (distributed)이고 결정적인 (deterministic) 방식으로 이웃 노드를 탐색하는 문제를 다루고자 한다. 본 연구의 첫 번째 주제에서는, 다중 채널 액세스 네트워크에서 채널 량데뷰 기법을 제안한다. 노드들은 데이터 전송을 시작하기 전에 하나의 공통된 채널에서 링크를 설정해야 한다. 그런 공통의 채널을 찾는 방법은 중앙 처리 또는 분산 처리 방식으로 이루어 질 수 있다. 본 연구에서는 별도의 제어 채널 없이 완전 분산 처리 (fully distributed) 방식으로 이루어지는 채널 랑데뷰 문제에 대해 초점을 맞춘다. 제안된 방식은 두개의 노드들이 2N+1 슬롯 내에 랑데뷰할 가용 채널을 방문하는 순서를 제공한다. 여기서 N은 채널의 수이고 슬롯은 공통 채널에서 두 노드가 링크를 설정하는데 필요한 최소의 시간 간격을 나타낸다. 지금까지 알려진 가장 좋은 방식으로는 N^2+N-1 슬롯 내에 랑데뷰한다고 알려져 있다. 그리고, 제안된 기법은 슬롯의 동기화 없이도 구현가능하다는 것을 증명하였다. 본 연구의 두 번째 주제에서는, 기회 네트워크에서 최적의 에너지 효율적인 이웃 탐색 방식을 제안한다. 기회 네트워크는 이동 애드혹 네트워크가 가장 흥미롭게 진화된 형태이다. 실제 이동 애드혹 네트워크에서는 노드의 짧은 전송거리와 사용자의 빠른 이동으로 인하여 빈번하게 연결이 끊긴다. 그러므로, 전체 네트워크는 연결되어 있고 노드들 사이에는 단대단 (end-to-end) 경로가 존재한다고 가정하하고 있는 기존의 이동 애드혹 네트워크에 대한 연구들은 적용할 수 없다. 신속한 이웃 탐색을 하기 위해서, 노드는 지속적으로 주변에 있는 다른 노드를 탐색하기 위해 probing 메시지를 broadcasting하고 있다. 이런 종류의 지속적인 probing은 너무 에너지 소모가 크기 때문에, 배터리로 동작하는 장치에게는 적합하지 않다. 에너지 소비를 최소화하기 위해서 다른 노드를 만나지 않을 때에는 radio 전원을 꺼서 sleeping mode로 설정하고, 오직 이웃 탐색과 데이타를 교환할 때에만 radio 전원을 켜야 한다. 우선, 에너지 효율적이고 최소의 missing 확률과 고정 지연 시간을 제공하는 probing 스케쥴 방식을 설계한다. 이후 제안된 probing 스케쥴과 함께 최적의 에너지 효율적인 listening 스케쥴 방식을 제안한다. 제안된 이웃 탐색 기법은 최소의 에너지 소모와 최소의 missing 확률을 제공하면서 고정 지연 시간을 제공한다는 점에서 최적의 알고리즘이라고 할 수 있다. 또한, 이론적 분석과 시뮬레이션 결과를 통해서 기존의 기법들과 성능을 비교하였다. 이 비교를 통해서 제안된 기법이 에너지 소모 및 contact의 missing 확률 측면에서 기본의 기법들보다 우수한 에너지 효율성과 높은 이웃 탐색 확률을 제공한다는 것을 보여 준다.

Recently, there has been a growing interest in new networking paradigms such as opportunistic networks and cognitive networks. Various applications of ubiquitous networking and cloud computing are at the heart of such development (e.g. military, vehicular, rescue, medical, and multimedia transfer service). These networks are typically deployed without any communication infrastructure and are required to configure themselves. Neighbor discovery is one of the first steps in the self-configuration. To enable reliable exchange of data or control information, two nodes in physical contact must recognize each other and establish a link in a common channel. If a node fails to accomplish it, it misses the contact and experiences very long delivery latency or a failure of data delivery. Moreover, since it is difficult to predict when a node gets and how long it keeps in contact with another node, it is very challenging to discover neighbor nodes. In this thesis, we focus on the problem of discovering neighbor nodes in a fully distributed and deterministic manner.In the first topic of this thesis, we propose a channel rendezvous scheme in multi-channel access networks. Nodes must establish a link on a common channel before data transmission begins. We focus on the distributed channel rendezvous problem without a separate control channel. Our scheme determines the order, in which two nodes visit available channels to rendezvous within 2N+1 slots, where $N$ is the number of channels and a slot is the minimum interval required for establishing a link between any pair of nodes that are in a common channel. The best bound known so far is N^2+N-1 slots. By Jain's fairness index, we justify the claim that all channels are fairly accessed. More notably, our scheme can be implemented without slot synchronization which is hard to accomplish in a distributed manner.In the second topic of this thesis, we propose an optimal energy-efficient neighbor discovery scheme for opportunistic networks. Opportunistic networks are one of the most interesting evolutions of MANETs (Mobile Adhoc Networks). For a practical MANET, links may be intermittently established due to short transmission range and high user mobility, which is not the case where most previous works have implicitly assumed that the network is connected and there is a contemporaneous end-to-end path between any two nodes. For prompt neighbor discovery, a node is assumed to broadcast continuously probing messages to discover another in its vicinity. This kind of persistent probing consumes too much energy for battery-operated devices to afford. In order to minimize the energy consumption for persistent probing, a node must be able to turn off its radio, thus setting it to sleeping mode, during non-contact times and be able to turn it on only for neighbor discovery and data exchange. We design a probing schedule which provides a bounded delay with the minimal miss probability of a contact. Then, we derive an energy-efficient probing and associated listening schedule. The proposed neighbor discovery scheme is optimal in the sense that it provides a bounded delay with the minimal energy consumption as well as with the minimal miss probability of a contact. The performance of the proposed neighbor discovery scheme is evaluated by an extensive theoretical analysis and simulation results. Performance metrics, such as energy consumption, and loss probability of a contact are compared with those of existing schemes. The theoretical analysis and simulation results are also used to show the performance of the proposed scheme could be improved. In opportunistic networks where contact between two nodes occurs infrequently, we show that the proposed scheme achieves more significant energy-efficiency and provides much higher successful neighbor discovery probability than existing schemes.