Future Network Mobility

김문성(Moonseong Kim) 한국HCI학회 2007 한국HCI학회 학술대회 Vol.2007 No.2

N홉 접근보장의 백본을 이용한 무선 센서 네트워크 데이터 전송 프로토콜

김문성 ( Moonseong Kim ),조상훈 ( Sang-hun Cho ),추현승 ( Hyunseung Choo ) 한국인터넷정보학회 2009 인터넷정보학회논문지 Vol.10 No.1

잘 알려진 무선 센서 네트워크의 프로액티브 프로토콜인 Flooding과 SPIN은 싱크 노드의 요청 없이 감지한 데이터를 즉각적으로 전송한다. 그러나 이러한 전송방법은 그 데이터가 필요하지 않는 노드들에게까지 전송하기에 에너지 효율성 측면에서 비효율적이다. 본 논문에서는 이러한 단점을 극복하기 위해서 전체 노드 대신에 적절한 일부 노드들에게만 전송할 수 있는 세미프로액티브 프로토콜을 제안한다. 따라서 만일 싱크노드와 같은 어떠한 노드가 감지한 데이터를 필요로 할 경우 미리 설정한 몇 홉 이내에 그 데이터를 쉽게 얻을 수 있다. 시뮬레이션 결과는 잘 알려진 SPIN과 비교하여 노드의 에너지 효율성이 약 83%까지 높다는 것을 보여주었다. Flooding and SPIN, which are well-known WSN(Wireless Sensor Network) proactive protocols, spontaneously disseminate the sensed data without a request from an arbitrary sink node. However, these methods disseminate the data even to some nodes that do not need it, which is energy inefficient. In this paper, we introduce a semi-proactive protocol to disseminate only to pertinent nodes instead of all nodes in order to overcome this weakness. Thus some nodes, such as arbitrary sink nodes that need the sensed data, could easily obtain the data within some hops. The simulation result shows that the proposed protocol has higher average node energy efficiency than that of well-known earlier work, SPIN. If a proactive protocol, such as SPIN, is changed to semi-proactive and has only a 1-hop burden, then the energy efficiency enhancement is up to about 83% compared with SPIN.

고신뢰도 무선센서네트워크를 위한 홉핑 센서 재배치에 대한 연구

김문성 ( Moonseong Kim ),박광진 ( Kwangjin Park ) 한국인터넷정보학회 2011 인터넷정보학회논문지 Vol.12 No.2

무선센서네트워크에서 살포한 센서 중 일부의 결함이 발생하거나 에너지가 고갈될 시, 이동 센서(Mobile Sensor)들의 재배치로 결함이 발생한 지역(즉, 센싱 홀: Sensing Hole)을 복구할 수 있다. 수많은 바위 등이 즐비한 거친 지역에서는 바퀴 기반의 이동센서는 적당하지 않으므로 점프를 통해 이동이 가능한 홉핑 센서가 필요하다. 본 논문에서는 발생한 센싱 홀의 복구를 위한 재배치 문제 및 그에 따른 다양한 문제들을 살펴본다. 과거 홉핑 센서들을 이동시키기 위하여 단지 최단경로만을 고려하였으나, 본 논문에서는 최대 엇갈림 없는 경로 및 다중경로를 활용하여 또다른 센싱홀의 발생을 막을 수 있었다. 시뮬레이션 결과는 제안하는 기법들이 최단경로를 기반으로 한 기법에 비해 홉핑 센서의 균형적인 분배와 이동성공률에서 우수함을 보인다. When some sensors under Wireless Sensor Networks fail or become energy-exhausted, redundant mobile sensors might be moved to recover the sensing holes. Within rugged terrain where wheeled sensors are unsuitable, other type of mobile sensors, such as hopping sensors, are needed. In this paper, we address the problem of relocating hopping sensors to the detected sensing holes. Recent study for this work considered the relocation using the shortest path between clusters; however, the shortest path might be used repeatedly and create other sensing holes. In order to overcome the mentioned problem, we propose relocation schemes using the most disjointed paths or multi-paths. Simulation results show that the proposed schemes guarantee more balanced migration distributions of efficient sensors and higher movement success ratios of required sensors than those of the shortest path-based scheme.

무선 센서 네트워크에서 확률 기반의 클러스터링을 이용한 계층적 데이터 전송 프로토콜

김문성 ( Moonseong Kim ),조상훈 ( Sang-hun Cho ),임형진 ( Hyung-jin Lim ),추현승 ( Hyunseung Choo ) 한국인터넷정보학회 2009 인터넷정보학회논문지 Vol.10 No.2

무선 센서 네트워크를 위한 데이터 전송의 설계 중에서 가장 중요한 이슈 중 하나는 에너지 효율적인 측면이다. 이를 위해 최근 여러 연구들이 진행되고 있으며 그중에서 가장 대표적인 프로토콜은 SPMS이다. SPMS의 주요 특징 중 하나는 에너지소비를 줄이기 위한 수단으로 최단경로를 사용한다는 것이다. 그러나 반복적인 최단 경로의 사용으로 인하여 네트워크 라이프타임의 최대화는 불가능하다. 본 논문에서는 에너지 잔존량과 거리를 메트릭으로 사용하는 확률 함수 기반의 데이터 전송프로토콜을 제안한다. 시뮬레이션 결과, 제안 프로토콜은 에너지 효율적인 데이터 전송을 하며 SPMS보다 네트워크 라이프타임이 약 78%증가하였다. One of the major challenges of designing a dissemination protocol for Wireless Sensor Networks (WSNs) is energy efficiency. Recently, this issue has received much attention from the research community, and SPMS, which outperforms the well-known protocol SPIN, specially is a representative protocol. In addition, one of many characters of SPMS is the use of the shortest path to minimize the energy consumption. However, since it repeatedly uses the same path as the shortest path, the maximizing of the network lifetime is impossible, though it reduces the energy consumption. In this paper, we propose a dissemination protocol using probability-based clustering which guarantees energy-efficient data transmission and maximizes network lifetime. The proposed protocol solves the network lifetime problem by a novel probability function, which is related to the residual energy and the transmission radius between nodes. The simulation results show that it guarantees energy-efficient transmission and moreover increases the network lifetime by approximately 78% than that of SPMS.

경로 추정 기반의 지연시간을 고려한 저비용 유니캐스트 라우팅 알고리즘

김문성 ( Moonseong Kim ),방영철 ( Young-cheol Bang ),추현승 ( Hyunseung Choo ) 한국인터넷정보학회 2007 인터넷정보학회논문지 Vol.8 No.1

특정 시간 내에 데이터 전송이 이루어져야 하는 실시간 멀티미디어 응용 서비스의 특성은 네트워크의 QoS(Quality of Service) 보장을 위한 중요한 요소이다. 종단간(End-to-End) 지연시간 제한 조건을 만족하면서 최소 비용을 갖는 (Delay Constrained Least Cost, DCLC) 경로를 찾는 문제는 이미 NP-hard 문제로 알려져 있다. DCLC 문제의 해법은 경로 지연시간과 비용간의 적절할 선택으로 해결하야 한다. 그러나 최적에 가까운 알고리즘으로 알려진 Salama의 DCUR 알고리즘[1]은 알고리즘의 단순성을 위하여 임의의 노드에서 경로 선정 시 목적 노드까지의 최소 비용 경로나 최소 지연시간 경로상의 다음 노드로만 제한을 하여 라우팅 경로의 비용측면에서 다소 비효율적이다. 일반적으로 최소 지연시간 경로의 비용은 최소 비용 경로의 비용보다 상대적으로 높은 경로 비용을 갖으며, 역으로 최소 비용 경로의 지연시간은 최소 지연시간 경로의 지연 시간보다 상대적으로 높은 지연시간을 갖는다. 본 논문에서는 이러한 점에 착안하여 DCLC문제를 해결하기 위해 확률적 추정 기법을 사용한다. 최근 발표한 독립적 두 변수간의 확률적 조합 알고리즘은 이러한 현상을 극복하기에 충분한 알고리즘이다[2]. 따라서 확률적 새로운 변수에 기반한 경로 추정 기법을 사용하였으며, 그에 대한 성능평가를 하였다. The development of efficient Quality of Service (QoS) routing algorithms in high speed networks is very difficult since divergent services require various quality conditions. If the QoS parameter we concern is to measure the delay on that link, then the routing algorithm obtains the Least Delay (LD) path. Meanwhile, if the parameter is to measure of the link cost, then it calculates the Least Cost (LC) path. The Delay Constrained Least Cost (DCLC) path problem of the mixed issues on LD and LC has been shown to be NP-hard. The path cost of LD path is relatively more expensive than that of LC path, and the path delay of LC path is relatively higher than that of LD path in DCLC problem. In this paper, we propose the algorithm based on estimated path for the DCLC problem and investigate its performance. It employs a new parameter which is probabilistic combination of cost and delay. We have performed empirical evaluation that compares our proposed algorithm with the DCUR in various network situations.

네트워크 이동성을 고려한 NeMRI 기반의 멀티캐스트 라우팅 프로토콜

김문성 ( Moonseong Kim ),박정훈 ( Jeonghoon Park ),추현승 한국인터넷정보학회 2008 인터넷정보학회논문지 Vol.9 No.2

Mobile IP는 MN(Mobile Node)에 대한 이동성의 해결책을 제시할 뿐 네트워크 이동성(NEMO: NEtwork MObility)에 대해서는 해법이 될 수 없다. NBS(NEMO Basic Support) 프로토콜은 이동네트워크의 모든 노드들에게 세션 지속성을 보장한다. NEMO에서 멀티캐스트를 지원할 경우 Mobile IP에 기반을 둔 프로토콜들은 Mobile IP가 지닌 터널 중첩 문제(Tunnel Convergence Problem)와 같은 태생적인 문제들을 갖는다. 본 논문에서는 NEMO에서의 멀티캐스트 경로최적화 기법을 제안한다. 우선, MR(Mobile Router)이 멀티캐스트 기능과 NeMRI(Nested Mobile Router Information) 테이블을 가지고 있다고 가정하고, NeMRI는 MR의 하위 모든 MR들의 CoA(Care of Address) 리스트와 MR들의 멀티캐스트 서비스 수신여부를 저장한다. 또한 핀볼 라우팅(Pinball Routing) 문제를 위한 어떠한 경로최적화 기법이라도 여기에 적용할 수 있기 때문에 멀티캐스트에 기반을 둔 네트워크 환경에서 경로최적화를 이룰 수 있다. 제안한 기법의 성능을 분석하기 위해 적절한 수학적 비용분석 모델을 제시하였으며, NEMO 환경에서 우리가 제안한 기법은 NBS에 기반을 둔 Bi-directional Tunneling, Remote Subscription 등과 같은 이동 멀티캐스트 기법들에 비하여 매우 뛰어난 비용절감을 확인 할 수 있었다. Mobile IP is a solution to support mobile nodes, however, it does not handle NEtwork MObility (NEMO). The NEMO Basic Support (NBS) protocol ensures session continuity for all the nodes in the mobile network. Since the protocol is based on Mobile IP, it inherits the same fundamental problem such as tunnel convergence, when supporting the multicast for NEMO. In this paper, we propose the multicast route optimization scheme for NEMO environments. We assume that the Mobile Router (MR) has a multicast function and the Nested Mobile Router Information (NeMRI) table. The NeMRI is used to record a list of the CoAs of all the MRs located below it. And it covers whether MRs desire multicast services. Any Route Optimization (RO) scheme can be employed here for pinball routing. Therefore, we achieve optimal routes for multicasting based on the given architecture. We also propose cost analytic models to evaluate the performance of our scheme. We observe significantly better multicast cost in NEMO compared with other techniques such as Bi-directional Tunneling, Remote Subscription, and Mobile Multicast based on the NBS protocol.

가중치에 따른 독립적 두 변수의 효율적 조합을 사용한 경로 찾기 알고리즘

김문성 ( Moonseong Kim ),방영철 ( Young-cheol Bang ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.2

실시간 통신에 있어서 경로의 지연시간과 자원의 활용은 정말 중요한 요소들이다. 그렇기에 단 하나의 기준만으로 경로를 설정한다는 것은 많은 문제를 일으킨다. 따라서 여러 링크 요소들을 효율적으로 운용할 수 있는 프로토콜이 필요할 것이다. 본 논문에서는 NP-hard 문제로 알려진 DCLC (Delay Constrained Least Cost) 경로 문제를 풀기위한 새로운 인자를 소개하였다. 가중치를 주어 새롭게 링크의 인자를 만드는 휴리스틱 알고리즘은, 주어진 가중치에 따라서 효율적인 경로 설정을 한다는 것을 컴퓨터 시뮬레이션으로 확인하였다. 본 논문에서 소개하는 방법으로 CCLD (Cost Constrained Least Delay) 경로 문제 또한 가중치의 변화만으로 아주 쉽게 풀 수 있을 것이다.

두 독립변수의 효율적 조합을 사용한 멀티캐스트 트리 생성 알고리즘

김문성 ( Moonseong Kim ),방영철 ( Young-cheol Bang ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.1

멀티캐스트는 실시간 멀티미디어 전송 등에서 그 중요성이 매우 커지고 있다. 이러한 응용 기술들은 네트워크의 QoS(Quality of Service)보장을 위해 많은 자원을 필요로 한다. 네트워크의 자원은 한정되어 있기 때문에, 효율적인 자원의 사용을 위해서는 효율적인 멀티캐스트 라우팅 경로를 설정하는 것이 결정적 수단이다. 최소비용 멀티캐스트 라우팅 문제는 다양한 트리 최적화 문제를 해결하기 위한 기본적인 문제이며 다양한 연구가 있어왔다. 제안하는 알고리즘은 최소비용멀티캐스트 트리를 생성하는 휴리스틱 알고리즘으로 잘 알려진 TM 알고리즘과 가중치를 사용하여, 멀티캐스팅의 다양한 트리 최적화 문제에 적용되어 QoS에 따른 네트워크 자원의 사용효율을 극대화 하는데 기여할 것이다.

네트워크 이동성 환경에서 멀티캐스트 기반의 바인딩 갱신 기법에 대한 성능 분석

안수빈 ( Soobeen Ahn ),김문성 ( Moonseong Kim ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2008 한국정보처리학회 학술대회논문집 Vol.15 No.1

네트워크 이동성(Network Mobility: NEMO)은 하나 이상의 서브넷으로 이루어진 전체 네트워크가 인터넷 접속점을 동적으로 변화하여 네트워크 접근성도 변화하는 환경을 말한다. 이러한 환경에서 경로 최적화를 위한 여러 프로토콜들이 존재하지만 그중 Prefix Delegation 기법은 다른 기법들에 비해 다방면에서 우수하다. 그러나 본질적으로 바인딩 갱신 스톰(storm) 문제를 수반하기에 NEMO 환경에서의 바인딩 갱신 비용을 최소화 하기위한 연구가 대두하였다. 본 논문에서는 바인딩 갱신 비용의 최소화를 위하여 바인딩 갱신 시 멀티캐스트 기법을 적용하였으며, 경로 최적화 프로토콜은 Prefix Delegation 기법 중 바인딩 갱신 비용을 효율적으로 고려한 IPD[1]를 가정하였다. 성능평가를 위해서 수학적 모델링을 적용하였으며, 본 모델을 통하여 기존 방법들에 비하여 상당한 비용절감 효과를 얻을 수 있음을 보인다.

DVBMT 문제에 대한 효율적인 코어 노드 선택 알고리즘

안영진 ( Youngjin Ahn ),김문성 ( Moonseong Kim ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.2

멀티캐스트 기술이 발전함에 따라 멀티캐스트를 이용하는 응용 프로그램들 사이에서 실시간의 적용이 매우 중요한 문제로 제시되고 있다. 이러한 실시간 응용프로그램들을 만족시키는 요소 중 하나가 바로 지연시간 제한과 지연 변이 제한을 만족하는 멀티캐스트 트리(DVBMT : delay- and delay variation-bounded multicast tree) 문제이다. 이는 멀티캐스트 트리 상에서 각 목적노드는 요구 사항에 맞는 최적화 된 멀티캐스트 지연변이와 종단간의 제한된 지연시간을 함께 만족하도록 하는 문제이다. 이러한 문제는 현재 NP-complete 문제로 알려져 있으며, 꾸준하게 향상된 알고리즘이 제시되고 있는 상황이다. DVBMT 문제의 해법으로 원격 회의, 화상채팅, 또는 온라인 게임 같은 실시간 응용 프로그램에 적용시킬 수 있다. DVBMT 문제를 푸는 알고리즘들에는 DVMA, DDVCA 등이 있으며 본 논문에서 소개하는 알고리즘은 이들 알고리즘보다 효과적으로 구현하여 위와 같은 실시간 응용프로그램의 효율성을 한층 높일 수 있다. 이는 성능 평가로서 그 효율성을 확인하였으며, 이상적으로 알려진 DDVCA보다 inefficiency로 계산 했을 때, 약 9%에서 27%에 이른다. 시간복잡도는 DDVCA와 같은 O ( mn ² )의 시간으로 구현된다.