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 ),방영철 ( 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에 따른 네트워크 자원의 사용효율을 극대화 하는데 기여할 것이다.

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

김문성 ( 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.

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

김문성 ( 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.

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

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

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

MWSN에서 채널 및 타임 슬롯 공동 스케줄링 데이터 집계를 위한 제안 계획 : 알고리즘 설계

( Vi Van Vo ),김문성 ( Moonseong Kim ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2020 한국정보처리학회 학술대회논문집 Vol.27 No.1

Aggregating data with an optimal delay, which is a critical problem in Wireless Sensor Networks applications, is proven as NP-hard. In this paper, we focus on optimizing the aggregation delay by presenting an idea for channel and timeslot co-scheduling data aggregation in MWSNs. The proposed scheme, which names Break and Join, maximizes the number of sensor nodes to be scheduled in a working period, so that the overall number of working periods and data collection delay are reduced.

무선 센서 네트워크에서 잔여 에너지와 전송거리의 조율을 통한 데이터 전송 프로토콜

서재완 ( Jaewan Seo ),김문성 ( Moonseong Kim ),조상훈 ( Sang-hun Cho ),추현승 ( Hyunseung Choo ) 한국인터넷정보학회 2008 인터넷정보학회논문지 Vol.9 No.5

본 논문에서는 에너지 효율적인 전송과 긴 네트워크 라이프타임을 보장하는 데이터 전송 프로토콜을 소개한다. 잘 알려진 SPIN에 비해 SPMS는 최단경로로 데이터를 전송하기 때문에 전송 시 에너지 효율을 극대화했다. 하지만 최단경로상의 특정 노드를 반복해서 사용함으로써 짧은 네트워크 라이프타임을 가진다. 본 논문에서는 거리와 에너지 잔량의 두 가지 속성을 고려한 ConBED(A protocol Considering Between Energy and Distance) 프로토콜을 제안한다. 시뮬레이션 결과, ConBED는 에너지 효율적인 전송을 보장하며 SPMS에 비해 네트워크 라이프 타임이 69%증가한 것을 보여준다. In this paper, we present a data dissemination protocol that guarantees energy-efficient data transmission and maximizes network lifetime. SPMS that outperforms the well-known protocol SPIN uses the shortest path to minimize the energy consumption. However, since it repeatedly uses the same path, maximizing the network lifetime is impossible. In this paper, we propose a protocol for data dissemination called the protocol Considering Between Energy and Distance (ConBED). It solves the network lifetime problem using the residual energy and the distance between nodes to determine a path for data dissemination. The simulation results show that ConBED guarantees energy-efficient transmission and increases the network lifetime by approximately 69% than that of SPMS.

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 ² )의 시간으로 구현된다.

듀티 사이클 MWSN 에서 데이터 집계를위한 개선 지연 효율적인 스케줄링 체계

( Van-vi Vo ),김문성 ( Moonseong Kim ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2020 한국정보처리학회 학술대회논문집 Vol.27 No.2

In multi-channel wireless sensor networks, optimizing data aggregation delay without any channels and timeslots conflicts has been concerned these days. The aggregation delay can be reduced by using different aggregation tree construction methods or scheduling in different methods in bottom-up or top-down manners. In this paper, we propose a new way of constructing aggregation tree purposing to decrease the total aggregation delay. The result shows that our proposed scheme can improve up to 64% comparing with state-of-the-art schemes.