[논문]사물인터넷에서 주기적 센싱 데이터 제어를 위한 스마트 디바이스 집합 구성 방안

성윤영; 우현제; 이미정

doi:10.7840/kics.2017.42.4.758

사물인터넷에서 주기적 센싱 데이터 제어를 위한 스마트 디바이스 집합 구성 방안
Organizing the Smart Devices' Set for Control of Periodic Sensing Data in Internet of Things 원문보기

한국통신학회논문지 = The Journal of Korean Institute of Communications and Information Sciences, v.42 no.4, 2017년, pp.758 - 767

성윤영 (Ewha Womans University Department of Computer Science and Engineering) , 우현제 (Ewha Womans University Department of Computer Science and Engineering) , 이미정 (Ewha Womans University Department of Computer Science and Engineering)

초록
AI-Helper

인터넷에 연결된 사물이 인간의 명시적 개입 없이 정보를 생성하고, 다른 사물, 사람, 시스템과 연동하여 동작하는 사물인터넷(Internet of Things) 기술이 주목받고 있다. 2020년에는 각종 센서와 네트워크 기능이 탑재된 스마트 디바이스가 260억대에 이를 것으로 전망되고, 급증하는 스마트 디바이스로부터 생성되는 센싱 데이터는 기하급수적으로 증가하여 인터넷 연결 트래픽 증가와 무선 채널 혼잡을 야기할 수 있다. 이에 본 논문에서는 사물인터넷에서 주기적인 센싱 데이터를 수집 전달하기 위해 스마트 디바이스를 싱크노드로 활용하는 방안을 제안하고, 스마트 디바이스가 실행 중인 응용의 요구사항을 만족시키는 최적의 싱크노드 집합을 구하는 것은 NP-hard문제[1]이므로 휴리스틱 방법을 이용하여 싱크노드 집합을 구성하는 알고리즘을 제안한다. 제안하는 휴리스틱 알고리즘의 시간복잡도는 $O(m^3)$으로 최적의 싱크노드를 구하는 알고리즘보다 빠른 시간에 싱크노드 집합을 구할 수 있다.

Abstract ▼ AI-Helper

IoT paradigm which makes a information without direct intervention of a human and interworks with other objects, humans and systems is attracting attention. It will be expected the number of smart devices equipped with sensors and wireless communication capabilities is reached to about 260 billion by 2020. With the vast amount of sending data generated from rapidly increasing number of smart devices, it will bring up the traffic growth over internet and congestion in wireless networks. In this paper, we utilize the smart device as a sink node to collect and forward the sensing data periodically in IoT and propose a heuristic algorithm for a selection of sink nodes' set with each sink node satisfies the QoS its applications because a selection of optimal sink nodes' set is NP-hard problem. The complexity of proposed heuristic algorithm is $O(m^3)$ and faster than the optimal algorithm.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 사물인터넷 환경에서 급증하는 센싱데이터의 효율적인 제어를 위해 스마트 디바이스를 싱크노드로 활용하는 방안을 제안하고, 휴리스틱하게싱크노드를 선택하는 알고리즘을 제안하였다. 제안하는 휴리스틱 알고리즘의 복잡도는 O(m³)으로 최적의 싱크노드 집합을 구하는 알고리즘의 지수시간 복잡도 (O(2^m))보다 빠르게 싱크노드 집합을 구할 수 있다.
이에 본 논문에서는 사물인터넷에서 주기적인 센싱 데이터를 수집·전달하기 위해 스마트 디바이스를 싱크노드로 활용하는 방안을 제안하고 휴리스틱 방법을 이용하여 싱크노드 역할을 수행할 스마트 디바이스 집합을 구성하는 알고리즘을 제안한다.
증가하는 IoT 트래픽 관리를 위해 네트워크 경로 정보 파악 및 병목현상 발생 노드에 대한 관리를 통해 라우팅 경로를 견고히 하여 지연 및 에너지 소모를 줄이려는 연구^[7-9]들이 진행되고 있으나 무선 네트워크에서의 트래픽 부하를 줄여 링크의 품질을 향상시키려는 연구는 미비한 상태이다. 이에 본 논문에서는 일부의 스마트 디바이스가 대표가 되어 다른 디바이스들의 센싱 데이터를 취합하여 인터넷 서버에 전달하게 함으로써 무선 네트워크에서의 혼잡을 예방하고 인터넷 연결 트래픽을 줄이는 방안을 제안한다. 즉, 스마트 디바이스에게 본연의 역할을 수행함과 동시에센싱 데이터를 수집하여 인터넷 서버에 전달하는 싱크노도의 역할도 수행하게 하여 싱크노드 역할을 수행하는 스마트 디바이스만을 인터넷에 연결시키고자 하는 것이다.
그러나 사물인터넷의 스마트 디바이스는 센서와 달리 충전이 용이하거나 유선으로 전원을 공급받는 등 센서에 비해 배터리 제약을 덜 받으므로 에너지 효율을 위해 CH에 1-hop 혹은 2-hop으로 연결되는 방식의 클러스터링보다 클러스터의 수가 적어 최소한의 CH가 선출되는 것이 인터넷 연결 비용 절감에 유리하다. 이에 본 장에서는 센서 네트워크의 클러스터링 알고리즘 중에서 클러스터 구성 시 CH와 멤서 센서와의 hop 수가 고정되지 않는 알고리즘을 중심으로 관련연구를 살펴본다.
주기적으로 수집한 센싱 데이터를 인터넷 서버로 전달하기 위해 스마트 디바이스를 싱크노드로 활용할 경우 최적의 싱크노드 집합을 구하는 것은 NP-hard 문제이므로, 본 장에서는 이를 해결하기 위한 휴리스틱 알고리즘을 설명한다. 제안하는 알고리즘은 무선네트워크 및 인터넷 연결 트래픽 감소를 위해 응용의 서비스 품질을 고려하여 무선 네트워크에서의 스마트 디바이스로부터 싱크노드로의 홉 수에 대한 제약조건을 만족시키는 가능한 적은 수의 싱크노드 집합을 구성하는 것을 목표로 한다.
이에 본 논문에서는 일부의 스마트 디바이스가 대표가 되어 다른 디바이스들의 센싱 데이터를 취합하여 인터넷 서버에 전달하게 함으로써 무선 네트워크에서의 혼잡을 예방하고 인터넷 연결 트래픽을 줄이는 방안을 제안한다. 즉, 스마트 디바이스에게 본연의 역할을 수행함과 동시에센싱 데이터를 수집하여 인터넷 서버에 전달하는 싱크노도의 역할도 수행하게 하여 싱크노드 역할을 수행하는 스마트 디바이스만을 인터넷에 연결시키고자 하는 것이다.

가설 설정

사물인터넷을 구성하는 모든 스마트 디바이스는 싱크노드의 역할을 수행할 수 있으나 본 논문에서는 스마트 디바이스들 중에서 싱크노드가 될 수 있는 후보디바이스 집합이 별도로 있다고 가정하였다.
스마트 디바이스는 시나리오별로 각각 200, 300개이며 토폴로지 내에 무작위로 배치한다. 스마트 디바이스가 실행 중인 응용의 지연제약은 응용의 종류에 따라 다르나 실험에서는 모두 같다고 가정하여 지연 제약을 4~7 홉으로 변화시켜가며 싱크노드를 선택하였다. 싱크노드 선택 시 싱크노드 역할을 수행할 스마트 디바이스가 현재 처리하고 있는 데이터양은 특별히 고려하지 않는다.

제안 방법

제안하는 휴리스틱 알고리즘의 복잡도는 O(m³)으로 최적의 싱크노드 집합을 구하는 알고리즘의 지수시간 복잡도 (O(2^m))보다 빠르게 싱크노드 집합을 구할 수 있다. 블루투스 4.0과 zigbee를 사용하는 환경에서 제안하는 휴리스틱 알고리즘을 적용시켜 응용의 지연 제약을 변경해가며 선택되는 싱크노드의 수를 비교하였다. 지연 제약이 증가할수록 우회 연결이 가능한 싱크노드의 수가 증가하므로 휴리스틱하게 선택되는 싱크노드의 수는 감소하고 이로 인해 각 싱크노드가 서비스하는 스마트 디바이스의 수는 증가하는 것을 확인할 수 있었다.
주기적으로 수집한 센싱 데이터를 인터넷 서버로 전달하기 위해 스마트 디바이스를 싱크노드로 활용할 경우 최적의 싱크노드 집합을 구하는 것은 NP-hard 문제이므로, 본 장에서는 이를 해결하기 위한 휴리스틱 알고리즘을 설명한다. 제안하는 알고리즘은 무선네트워크 및 인터넷 연결 트래픽 감소를 위해 응용의 서비스 품질을 고려하여 무선 네트워크에서의 스마트 디바이스로부터 싱크노드로의 홉 수에 대한 제약조건을 만족시키는 가능한 적은 수의 싱크노드 집합을 구성하는 것을 목표로 한다.
한편, 실험을 통해 저전력 근거리 무선 통신 프로토콜인 블루투스 4.0, zigbee를 사용하는 경우에 대해 휴리스틱하게 싱크노드 집합을 구성하였다. 사물인터넷 토폴로지 크기는 1,000m×1,000m이고, 제안 방안의 가정대로 싱크노드가 될 수 있는 후보 디바이스는토폴로지 내에 균일한 간격으로 가로 8개, 세로 8개씩 총 64개를 배치하였다.
휴리스틱 알고리즘을 이용하여 가능한 적은 수의 싱크노드가 선택되는 것을 보이기 위해 시나리오 별로 선택된 싱크노드의 수를 측정하였고, 이 때, 각 싱크노드 별 연결된 센서의 수와 각 센서들로부터 연결된 싱크노드까지의 홉 수를 측정하였다. 모든 측정치는 실험을 10번 반복하여 평균을 낸 값이다.

대상 데이터

사물인터넷 토폴로지 크기는 1,000m×1,000m이고, 제안 방안의 가정대로 싱크노드가 될 수 있는 후보 디바이스는토폴로지 내에 균일한 간격으로 가로 8개, 세로 8개씩 총 64개를 배치하였다.

성능/효과

본 논문에서는 사물인터넷 환경에서 급증하는 센싱데이터의 효율적인 제어를 위해 스마트 디바이스를 싱크노드로 활용하는 방안을 제안하고, 휴리스틱하게싱크노드를 선택하는 알고리즘을 제안하였다. 제안하는 휴리스틱 알고리즘의 복잡도는 O(m³)으로 최적의 싱크노드 집합을 구하는 알고리즘의 지수시간 복잡도 (O(2^m))보다 빠르게 싱크노드 집합을 구할 수 있다. 블루투스 4.
[1]에서 분석한 최적의 싱크노드 집합을 구하는 알고리즘은 지수시간 복잡도 (O(2^m))를 갖는데, 그림 3은 지수시간의 복잡도와 다항시간의 복잡도를 비교하여 보인 것으로 m이 10 이상일 때 다항시간 복잡도가 지수시간 복잡도 보다 항상 빠름을 알 수 있다. 즉, 사물인터넷을 구성하는 스마트 디바이스의 수가 10대 이상이라고 가정하는 것에 큰 문제가 없으므로 제안하는 휴리스틱 알고리즘의 수행 시간이 최적의 알고리즘보다 빠르다고 결론지을 수 있다.
0과 zigbee를 사용하는 환경에서 제안하는 휴리스틱 알고리즘을 적용시켜 응용의 지연 제약을 변경해가며 선택되는 싱크노드의 수를 비교하였다. 지연 제약이 증가할수록 우회 연결이 가능한 싱크노드의 수가 증가하므로 휴리스틱하게 선택되는 싱크노드의 수는 감소하고 이로 인해 각 싱크노드가 서비스하는 스마트 디바이스의 수는 증가하는 것을 확인할 수 있었다. 제안하는 휴리스틱 알고리즘은 다른 싱크노드로 우회하여 연결할 때 응용의 지연 제약만을 고려하는데 향후 싱크노드의 처리 가능한 데이터양을 함께 고려하고 스마트 디바이스와 싱크노드의 이동성을 반영할 수 있도록 제안하는 알고리즘을 확장할 계획이다.
0과 zigbee를 사용할 때, 각 싱크노드에 연결된 스마트 디바이스의 수를 보인 것이다. 지연 제약이 증가함에 따라 선택되는 싱크노드의 수가 감소하므로 각 싱크노드가 서비스해야 하는 디바이스의 수가 증가하고, 실험을 통해 이를 확인할 수 있었다.
0과 zigbee를 이용하는 경우, 휴리스틱 알고리즘을 이용해 싱크노드를 선택할 때 싱크노드로부터 연결된 스마트 디바이스의 연결 홉 수의 최대값과 모든 스마트 디바이스에서 싱크노드에 연결된 홉 수의 평균을 다익스트라 알고리즘을 적용했을 때와 비교하여 보인 것이다. 지연제약이 증가할수록 우회하여 연결이 가능한 싱크노드가 늘어나므로 연결 홉의 최대값과 평균 연결 홉 수가 증가하나 연결 홉 수의 증가폭이 많이 크지 않음을 볼 수 있다.

후속연구

지연 제약이 증가할수록 우회 연결이 가능한 싱크노드의 수가 증가하므로 휴리스틱하게 선택되는 싱크노드의 수는 감소하고 이로 인해 각 싱크노드가 서비스하는 스마트 디바이스의 수는 증가하는 것을 확인할 수 있었다. 제안하는 휴리스틱 알고리즘은 다른 싱크노드로 우회하여 연결할 때 응용의 지연 제약만을 고려하는데 향후 싱크노드의 처리 가능한 데이터양을 함께 고려하고 스마트 디바이스와 싱크노드의 이동성을 반영할 수 있도록 제안하는 알고리즘을 확장할 계획이다.
사물인터넷 환경에서 송·수신되는 데이터는 멀티미디어 콘텐츠처럼 몇 십 또는 몇 백 메가바이트 수준의 대용량이 아니라 몇 킬로바이트 수준의 적은 양이다. 향후 다양한 멀티 미디어 콘텐츠들이 생산, 공유, 소비되겠지만 사물인터넷에서는 센싱 데이터 중심의 가벼운 연결이 기하급수적으로 증가하면서 멀티미디어 콘텐츠 같은 대용량 데이터의 트래픽을 뛰어넘는 환경이 될 것으로 예상한다^[3].

질의응답

핵심어	질문	논문에서 추출한 답변
	사물인터넷 환경에서 송·수신되는 데이터의 양은 얼마인가?	사물인터넷[2]은 인간과 사물, 서비스의 세 가지 분산된 환경 요소에 대해 인간의 명시적 개입 없이 상호협력적으로 센싱, 네트워킹, 정보 처리 등 지능형 관계를 형성하는 사물 공간 연결망으로 2020년에는 각종 센서와 네트워크 기능이 탑재된 스마트 디바이스가 260억대에 이를 것으로 전망된다. 사물인터넷 환경에서 송·수신되는 데이터는 멀티미디어 콘텐츠처럼 몇 십 또는 몇 백 메가바이트 수준의 대용량이 아니라 몇 킬로바이트 수준의 적은 양이다. 향후 다양한 멀티 미디어 콘텐츠들이 생산, 공유, 소비되겠지만 사물인터넷에서는 센싱 데이터 중심의 가벼운 연결이 기하급수적으로 증가하면서 멀티미디어 콘텐츠 같은 대용량 데이터의 트래픽을 뛰어넘는 환경이 될 것으로 예상한다[3].
	사물인터넷 기술이란?	인터넷에 연결된 사물이 인간의 명시적 개입 없이 정보를 생성하고, 다른 사물, 사람, 시스템과 연동하여 동작하는 사물인터넷(Internet of Things) 기술이 주목받고 있다. 2020년에는 각종 센서와 네트워크 기능이 탑재된 스마트 디바이스가 260억대에 이를 것으로 전망되고, 급증하는 스마트 디바이스로부터 생성되는 센싱 데이터는 기하급수적으로 증가하여 인터넷 연결 트래픽 증가와 무선 채널 혼잡을 야기할 수 있다.
	싱크노드 역할을 수행하는 스마트 디바이스만을 인터넷에 연결함으로 인해서 얻을 수 있는 이점은?	증가하는 IoT 트래픽 관리를 위해 네트워크 경로 정보 파악 및 병목현상 발생 노드에 대한 관리를 통해 라우팅 경로를 견고히 하여 지연 및 에너지 소모를 줄이려는 연구[7-9]들이 진행되고 있으나 무선 네트워크에서의 트래픽 부하를 줄여 링크의 품질을 향상시키려는 연구는 미비한 상태이다. 이에 본 논문에서는 일부의 스마트 디바이스가 대표가 되어 다른 디바이스들의 센싱 데이터를 취합하여 인터넷 서버에 전달하게 함으로써 무선 네트워크에서의 혼잡을 예방하고 인터넷 연결 트래픽을 줄이는 방안을 제안한다. 즉, 스마트 디바이스에게 본연의 역할을 수행함과 동시에센싱 데이터를 수집하여 인터넷 서버에 전달하는 싱크노도의 역할도 수행하게 하여 싱크노드 역할을 수행하는 스마트 디바이스만을 인터넷에 연결시키고자 하는 것이다.

참고문헌 (22)

H. J. Woo and M. J. Lee, "A study on the use of smart devices for effective control of the periodic sensing data in inter of things," in Proc. KICS Winter Conf., pp. 1052-1053, Gangwon-do, Korea, Jan. 2016.
K. S. Min, Internet of Things(2012), Retrieved Jan., 12, 2017, from http://www.kisa.or.kr
D. H. Shin, IoT era, three things are different from mobile era(2014), Retrieved Jan., 12, 2017, from http://www.lgeri.com
C. S. Oh, M. S. Seo, J. H. Lee, S. H. Kim, Y. D. Kim, and H. J. Park, "Indoor air quality monitoring systems in the IoT environment," J. KICS, vol. 4, no. 5, pp. 886-891, May 2015.
K. B. Kang, H. K. Ahn, H. S. Kim, S. H. Lee, and J. W. Jwa, "Development of vending machine for electricity based on Z-Wave mesh network," J. KICS, vol. 41, no. 10, pp. 1256-1262, Oct. 2016.

원문보기 상세보기
J. W. Cha, J. Y. Lee, and J. H. Lee, "Secure smart safety system using streetlight infrastructure," J. KICS, vol. 40, no. 5, pp. 851-856, May 2015.

원문보기 상세보기
J. H. Kim and J. Y. Lee, "A study about problem of routing with MPTCP for advanced performance in homegeneous network for IoT," in Proc. KICS Int. Conf. Commun., pp. 1043-1044, Jeju island, Korea, Jun. 2014.
S. H. Lee, J. H. Hong, N. U. Kim, and T. M. Chung, "Application of SDN technologies for IoT traffic management in MLN," in Proc. KICS Int. Conf. Commun., pp. 262-263, Jeju island, Korea, Jun. 2015.
I. J. Jung, S. H. Chung, and S. J. Lee, "A routing scheme considering bottleneck and route link quality in RPL-based IoT wireless networks," J. KIISE, vol. 42, no. 10, pp. 1268-1279, Oct. 2015.

상세보기
E. I. Oyman and C. Ersoy, "Multiple sink network design problem in large scale wireless sensor networks," in Proc. ICC 2004, pp. 3663-3667, Paris, France, Jun. 2004.
S. Dai, C. Tang, S. Qiao, K. Xu, H. Li, and J. Zhu, "Optimal multiple sink nodes deployment in wireless sensor networks based on gene expression programming," in Proc. ICCSN 2010, pp. 355-359, Singapore, Feb. 2010.
A. A. Abbasia and M. Younis, "A survey on clustering algorithms for wireless sensor networks," Computer Commun., vol. 30, no. 14-15, pp. 2826-2841, Oct. 2007.

상세보기
D. J. Baker and A. Ephremides, "The architectural organization of a mobile radio network via a distributed algorithm," IEEE Trans. Commun., vol. 29, no. 11, pp. 1694-1701, Nov. 1981.

상세보기
C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 15, no. 7, pp. 1265-1275, Sept. 1997.

상세보기
R. Nagpal and D. Coore, "An algorithm for group formation in an amorphous computer," in Proc. PDCS'98, Las Vegas, Oct. 1998.
W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "Application specific protocol architecture for wireless microsensor networks," IEEE Trans. Wirel. Commun., vol. 1, no. 4, pp. 660-670, Oct. 2002.

상세보기
M. Demirbas, A. Arora, and V. Mittal, "FLOC: a fast local clustering service for wireless sensor networks," in Proc. DIWANS'04, Florence, Italy, Jun. 2004.
O. Younis and S. Fahmy, "HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks," IEEE Trans. Mob. Comput., vol. 3, no. 4, pp. 366-379, Oct.-Dec. 2004.

상세보기
H. Huang and J. Wu, "A probabilistic clustering algorithm in wireless sensor networks," in Proc. IEEE VTC-2005-Fall, vol. 3, pp. 1796-1798, Dallas, TX, Sept. 2005.
K. Xu and M. Gerla, "A heterogeneous routing protocol based on a new stable clustering scheme," in Proc. MILCOM 2002, vol. 2, pp. 838-843, Anaheim, CA, Oct. 2002.
S. Bandyopadhyay and E. Coyle, "An energy efficient hierarchical clustering algorithm for wireless sensor networks," in Proc. INFOCOM 2003, vol. 3, pp. 1713-1723, San Francisco, California, Apr. 2003.
P. Ding, J. Holliday, and A. Celik, "Distributed energy efficient hierarchical clustering for wireless sensor networks," in Proc. DCOSS'05, pp. 322-339, Marina Del Rey, CA, Jun. 2005.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증