모바일 애드-혹 네트워크에서 효율적인 서비스 디스커버리를 위한 혼합 메시지 전달 기법 = Hybrid Message Delivery Scheme for Improving Service Discovery in Mobile Ad Hoc Networks

국문 초록 (Abstract)

디바이스(Device)가 현재 속해 있는 네트워크상에서 사용 가능한 서비스 혹은 자원을 자동으로 검색, 사용할 수 있는 기술을 의미하는 서비스 디스커버리(Service Discovery)는 유비쿼터스 환경에서 중요한 이슈 이다. 잘 알려진 서비스 검색 메커니즘으로는 안정적인 중앙 집중형 디렉터리 방식(SLP, UDDI, Jini)과 플러딩을 기반으로 하는 기법(UPnP, Jxta)등이 있다. 그러나 이들은 일반적으로 유선망을 기준으로 설계되었기 때문에 노드가 자주 이동하고 전력 등 사용 자원이 제한되어 있는 모바일 애드-혹 네트워크에 적용하기에는 적합하지 않고 특히 중앙 서버 방식은 사용하기 어렵다. 플러딩 기반의 방식은 분산 방식에 적합하지만 무선망과 이동 노드의 제한된 자원을 고려할 때 전달하는 메시지 수가 너무 크다. 비록 모바일 컴퓨팅 기술이 더욱 파워풀해지고 전보다 더 사용 가능해 지고는 있지만 모바일 디바이스들은 보통으로 낮은 처리 능력과 전력 사용에 한계가 있는 배터리를 사용한다. 그런데 이들은 메시지를 주고 받을 때 많은 전력을 소모하므로 주고 받는 메시지수를 줄이면서도 빠르게 검색을 하는 것이 모바일 애드-혹 네트워크에서 성능 향상을 위한 중요한 요소이다.
본 논문에서 우리는 앞에 언급한 고려사항들과 제약사항들에도 불구하고, 애드-혹 네트워크에 알맞게 사용가능하고 시의 적절하게 서비스를 검색, 사용할 수 있는 향상된 서비스 디스커버리 기법들을 제안한다.
제안한 기법에서 서비스 광고 메시지는 서버가 가지고 있는 데이터 정보를 이웃 노드들에게 전달하고, 이를 수신 받은 노드들은 정보를 자신의 노드에 캐쉬함으로서 많은 정보의 전달 효과와 이 정보를 이용함으로서 여행 단축 효과를 가진다. 또한 서비스 검색을 요청할 때는 노드의 ID와 노드의 이웃 노드와의 연결을 기준으로 메시지를 전달하여 불필요한 메시지 전송을 없애 메시지 전달의 효율성을 높였다. 추가로 성능을 더 향상시키기 위하여 Lower Id와 Higher Degree의 장점을 취하여 혼합 접근 방식을 설계하였다.
본 논문에서 제안한 서비스 디스커버리 기법들은 네트워크의 노드수가 늘어난 커다란 네트워크에서도, 즉 확장성이 있고, 중앙 집중 방식이 아닌 분산적이며, 노드간에 링크의 연결이 중단되거나 노드의 떠남에도 잘 견딜 수 있도록 고장 감내성이 좋고, 노드에게 부하를 균등하게 배분하며, 이동성이 큰 모바일 환경에서도 유연하게 대처할 수 있다는 특징을 갖는다. 제안한 기법들은 서비스 디스커버리에 사용되는 주고 받는 메시지의 수를 줄이고 평균 탐색 거리를 줄임으로써 전체 네트워크 통신 비용과 전력 감소를 줄이고 응답 시간을 향상시킬 수 있다.

다국어 초록 (Multilingual Abstract)

Ubiquitous computing environments consist of not only desktop computers, but also various devices including wearable devices, PDAs, notebook computers, sensors, which are interconnected via wireless ad hoc networks and wireless infrastructure-based networks such as WLANs. Mobile devices and sensor nodes connected to a network in ubiquitous computing environments dynamically change their location over a period of time. In an extreme case, a ubiquitous computing environment can be a mobile ad hoc network (MANET) where numerous mobile devices are connected by wireless networks without infrastructure support. Examples of such environments can be found in the mobile devices used by emergency services in U-healthcare, by soldiers in battlefields, by people walking on streets, etc. We are designed to handle this extreme case, MANET.
In ubiquitous computing environments, numerous devices that provide various services are widely distributed and connected by wireless networks. In order to provide desired services to users anytime and anywhere in such environments, file sharing or service discovery is emerging as an important issue. Therefore, efficient service discovery is required. For example, a user wanting to receive a specific piece of music or movie will have to locate a device that provides the corresponding file. The user may also have to find a particular service or object he or she wants to use, such as a his primary care doctor or an ideal car model, in intelligent ubiquitous computing applications, like U-healthcare, RFID/USN application or intelligent transportation system.
It is difficult to apply P2P applications based on a fixed network environment to ad-hoc networks different from those fixed wired networks, because their nodes are free to move. Although mobile computing technologies grow ever more powerful and accessible, mobile devices have a lower level of processing capacity and use batteries of limited power. They consume substantial power when they exchange messages. In this sense, it is requirement that costs are reduced for P2P applications with mobile devices in a wireless network. An ad-hoc network enables reduction of energy consumption, and reduction of wireless bandwidth needed for transmission, by reducing query messages among P2P applications in the network.
In this paper, we design and evaluate capacity-efficient schemes by reducing messages and average hop counts. We propose a hybrid approach involving lower ID and higher degree delivery schemes suitable for an ad-hoc network. Especially, we propose 3 kinds of schemes: a lower ID delivery scheme, a higher degree delivery scheme, and a hybrid delivery scheme. Regarding lower ID delivery, a node with lower ID receives information from another node since messages are conveyed to the node with lower ID. In the higher degree scheme, because a node’s messages are always sent to another node with the same degree or higher degree, the receiving node has more neighbor information. The node of the highest degree functions as a distributed index server. The number of messages exchanged in a network and average hop counts between a service requester and a service provider are reduced since the probability of responding service messages increases. In addition, we designed a hybrid approach based on the advantages of the lower ID delivery scheme and the higher degree delivery scheme, to achieve greater performance. The results of simulations showed that the proposed scheme reduced total network cost and power consumption by reducing messages and average hop counts(query delay), and improving response time, by comparison with any other system.

목차 (Table of Contents)

• 제 1 장 서론 1
• 제 2 장 관련 연구 7
• 2.1 서비스 디스커버리 7
• 2.1.1 중앙 집중적 디렉터리 기반 서비스 디스커버리 8
• 2.1.2 분산 디렉터리 기반 서비스 디스커버리 10
• 2.1.3 디렉터리가 없는 분산 서비스 디스커버리 12
• 2.1.4 서비스 디스커버리 비교 16
• 2.2 피어-투-피어 17
• 2.2.1 피어-투-피어 17
• 2.2.2 구조적 P2P 19
• 2.2.3 비구조적 P2P 24
• 2.2.4 모바일 환경에서의 P2P 탐색 24
• 2.2.5 P2P 비교 분석 26
• 제 3 장 시스템 구조 29
• 3.1 구조 29
• 3.2 시스템 모델 31
• 3.3 시스템 개요 32
• 제 4 장 적응적 이웃 선택을 통한 메시지 전달의 서비스 디스커버리 35
• 4.1 메시지 종류 및 구조 35
• 4.2 Lower ID 메시지 전달 정책 36
• 4.3 Higher Degree 메시지 전달 정책 39
• 4.4 혼합 메시지 전달 정책 41
• 4.4.1 개요 41
• 4.4.2 서비스 광고 기법 42
• 4.4.3 혼합 메시지 전달 정책-서비스 검색 기법 43
• 4.4.4 혼합2 메시지 전달 정책-서비스 검색 기법 46
• 4.5 캐쉬 갱신 기법 49
• 제 5 장 성능 분석 51
• 5.1 이웃 노드 정보를 활용한 효율적 메시지 전달 기법 51
• 5.1.1 서비스 광고 캐쉬 효과 51
• 5.1.2 여행 단축 효과 52
• 5.2 이론적 분석을 위한 가정 52
• 5.3 네트워크 로드 분석 54
• 5.4 평균 탐색 거리 분석 56
• 5.5 평균 탐색 요청 메시지 분석 58
• 제 6 장 성능 평가 60
• 6.1 성능평가기준 60
• 6.2 시뮬레이션 환경 63
• 6.3 노드 수에 따른 성능 평가 64
• 6.3.1 네트워크 로드 65
• 6.3.2 성공률 66
• 6.3.3 평균탐색거리 67
• 6.3.4 탐색 요청 메시지 수 68
• 6.3.5 캐쉬히트율 69
• 6.4 노드 속도에 따른 성능 평가 71
• 6.4.1 네트워크 로드 71
• 6.4.2 성공률 72
• 6.4.3 평균탐색거리 73
• 6.4.4 탐색 요청 메시지 수 74
• 6.4.5 캐쉬히트율 75
• 6.5 무선 전송 범위에 따른 성능 평가 76
• 6.5.1 네트워크 로드 77
• 6.5.2 성공률 78
• 6.5.3 평균탐색거리 79
• 6.5.4 탐색 요청 메시지 수 80
• 6.5.5 캐쉬히트율 81
• 6.6 서버율에 따른 성능 평가 82
• 6.6.1 네트워크 로드 83
• 6.6.2 성공률 84
• 6.6.3 평균탐색거리 85
• 6.6.4 탐색 요청 메시지 수 86
• 6.6.5 캐쉬히트율 87
• 6.7 네트워크 영역에 따른 성능 평가 89
• 6.7.1 네트워크 로드 90
• 6.7.2 성공률 91
• 6.7.3 평균탐색거리 92
• 6.7.4 탐색 요청 메시지 수 93
• 6.7.5 캐쉬히트율 94
• 제 7 장 결론 97
• 참고문헌 99
• Abstract 106