Every aspect of modern mobile wireless networks is dynamic. As radios are now attached to moving objects which may make planned, spontaneous, or random movements, the mobility of these objects governs the network state and presents diverse and highly time-varying operating conditions. With increasing density and mobility, the operating regimes of the networks exponentially widen and network connectivity may drastically change over time.
Mobile Opportunistic Networks (MON) is a new paradigm network designed to be able to adapt quickly to such a dynamic regime. It is formed by heterogeneous connectivities (e.g., Wi-Fi, Bluetooth) and opportunistic contacts driven by human mobility. The data delivery is achieved by a method named as ``store,carry and forward", where each node can store and carry the packets until forwarding them over the opportunistic contacts with the next-hop nodes. Compared to the data delivery in the existing networks such as MANET or cellular networks, MON further considers carrying as an additional transmission option.
Such transition in the delivery paradigm can provide huge improvements over the existing networks in terms of capacity, implementation cost and energy efficiency.
The performance of MON depends on to what extent the nodes utilize their opportunistic contacts. There exist three key operations in MON which are directly related to such utilization: First operation is a packet forwarding. Whenever the opportunistic contact occurs, each node should make the forwarding decisions such as selecting the packet to be forwarded or next-hop neighbor nodes. Second operation is sensing other nodes in the vicinity. The effective sensing helps each node fully utilize the randomly encountering contacts without any missing opportunity. Third, a prediction is also essential. By predicting potential contacts, nodes can exploit their future opportunistic contacts in their forwarding decisions.
In this thesis, we study forwarding, sensing and prediction to fully utilize the opportunistic contacts in MON. In particular, since the opportunistic contacts occur from human mobility, we focus on demystifying the connection between the patterns of human mobility and the optimality or efficiency of each operation. First, we study the packet, route and link scheduling policy in forwarding. Based on the understanding of ``store,carry and forward", we develop an optimal forwarding and replication policy in MON. Second, we develop a new routing metric (or distance vector) in forwarding. The proposing routing metric incorporates a novel opportunistic gain from multiple probabilistic paths to the destination which are formed by nodes` mobility patterns. Third, we consider the Wi-Fi AP sensing problem. By showing that the aging pattern of human mobility determines the optimality of sensing efficiency, we design an aging-based optimal sensing algorithm. Fourth, we propose spatio-temporal mobility prediction algorithm. By observing that human frequently moves along deterministic paths, we profile the path as a prediction state instead of a grid and show that path-based prediction achieve much higher performance in terms of predictability and complexity compared to the existing predictors.
최근의 무선 단말 네트워크들에서의 단말들 간 연결성 또는 채널 환경들은 계속해서 유동적인 형태로 변화하고 있다. 무작위로 이동하거나 특정 패턴을 가지고 이동하는 사용자 단말들에
무선 통신 모듈들이 부착되기 시작 하면서 네트워크의 연결 구조가 인간 이동성에 의해 시공간에서 변화하기 때문이다. 따라서 이와같은 유동적인 연결 상황에서 효과적으로 동작할 수 있는 네트워크 설계 및 관리의 필요성이 대두되었다.
기회적 통신 기반 모바일 네트워크 (MON)은 인간 이동성에 의해 발생하는 단말들간의 만남을 통한 패킷 전달 기회와 이종 통신 기술들 (Wi-Fi, Bluetooth)에 의해 형성되는 네트워크이다. 네트워크를 구성하는 단말들은 자신의 패킷들을 저장 및 운반할 수 있고, 운반 도중 또다른 단말과 만났을 때에 무선 채널을 통해 기회적인 전송할 수 있으며, 이와 같은 방식으로 패킷을 다중 홉으로 목적지 까지 전달할 수 있다. 기존 셀룰러 네트워크 또는 MANET에 탑재된 프로토콜 들이 패킷 전송만을 고려하여 설계된 반면, MON은 패킷 전송 뿐만 아니라 단말들이 패킷 전송을 하지 않고 직접 저장 및 운반을 하는 것을 또하나의 옵션으로 고려함으로써 기존과는 다른 새로운 네트워크 패러다임을 형성한다. 이러한 패러다임의 전환은 MON이 인간 이동성에 의해 발생하는 유동적인 네트워크 상황에서도 효과적으로 적응하여 동작할 수 있도록 함과 동시에, 기존 MANET 또는 셀룰러 네트워크 대비 통신용량 증대, 구축 비용 감소, 단말 에너지 효율성 증가와 같은 성능 개선을 달성한다.
MON으로 대표되는 새로운 네트워크들이 높은 성능을 내기 위해서는 인간 이동성에 의해 발생하는 단말간 통신기회들을 효과적으로 활용할 수 있어야 한다. 통신기회들을 효과적으로 활용하기 위해 고려되어야 하는 요소는 크게 세가지이다. 첫번째는 패킷 전송(Forwarding) 이다. 단말들간 연결이 이루어 졌을때에 어떤 패킷을 누구에게 어떻게 전달하는지를 결정하는 문제는 해당 기회를 효과적으로 활용하기 위해 필수적으로 고려되어야 한다. 두번째는 에너지 효율적 기회 탐색(Sensing)이다. 기회적 전송을 하기 위해서는 전송을 할 상대를 효과적으로 탐색하는것이 우선되어야 한다. 마지막 요소로써 기회 예측 (Prediction)이 있다. 단말들이 이동하며 얻게 될 잠재적인 전송 기회들을 예측함으로써 현재 시점에서의 패킷 전달 결정을 보다 효과적으로 하여 패킷 전달 성능을 증진시킬 수 있다.
본 박사학위 논문에서는 앞서 언급한 기회적 통신을 구성하는 세가지 중요 요소인 패킷 전송, 기회 탐색 및 예측에 대한 연구를 진행한다. 기회적 통신은 인간 이동성에 의해 발생하는 것이기 때문에, 각 단원에서는 인간 이동성의 특성 및 패턴들에 대한 면밀한 분석을 통하여 각 요소별 성능과 인간 이동성 패턴간의 연결고리를 밝혀 내는것에 주안점을 두고 연구를 진행한다. 첫번째 단원에서는 패킷 전송에서의 패킷,루트,링크 스케줄링 기법에 대해 최적화 관점에서 접근하여 최적 스케줄링 기법을 제안한다. 두번째 단원에서는 패킷 전송이 기반하는 라우팅 메트릭에 대한 새로운 계산 방법을 제안한다. 단말들의 이동 패턴에 의해 발생하는 확률적 다중 경로들의 존재성이 패킷 전송 성능과 밀접한 관련이 있음을 밝혀내고 이를 활용한 라우팅 메트릭을 통해 MON성능을 개선한다. 세번째 단원에서는 MON에서 일반적으로 목적지로 활용되는 와이파이 AP를 탐색하는 문제를 최적화 관점에서 다룬다. 인간 이동성에서의 Aging특성이 탐색 에너지 효율과 밀접한 관련이 있음을 밝혀내고, 이를 활용한 최적 알고리즘을 제안하여 에너지 효율성을 개선한다. 네번째 단원에서는 시공간에서의 인간 이동성 예측 기법을 제안한다. 사람들이 특정 경로를 따라 이동하는 현상을 관측하고 이 특성에 기반하여 예측 단위를 그리드에서 경로로 바꿈으로써 기존 예측 알고리즘 대비 높은 성능을 이루어 낸다.
