논문 리뷰 : A Survey of Sensor Selection Schemes in Wireless Sensor Networks(1차)

  육상 또는 수중에서 통신/탐지를 하기 위해서는 다수의 안테나(센서)가 필요합니다. 이때, 안테나(센서)의 개수가 무한정 많으면 누구나 어디서든 고 품질의 통신/탐지가 가능할 것입니다.

 

 하지만 자원은 한정되어 있기 때문에 목적에 맞게 다수의 안테나(센서)를 적절한 위치/방법으로 설치하는 것이 좋겠지요. 그러면 어떠한 점들을 고려해야 하는지 알아보겠습니다.

 

반응형

 

 설명하기에 앞서 이 논문은 정말 재미없고 특별한 기술이 있는 것도 아니며, 단순히 남의 논문을 분석하여 사실관계만 적은 논문입니다. 개인적으로 이런 방식의 논문이 있는것도 놀랍습니다. 거기다가 그림도 없고 엄청난 양의 영어만 있습니다. 하지만 어쩌겠습니까. 리뷰를 하라고 하니 리뷰를 해야겠지요. 시작하겠습니다.

 

논문 제목

 

 1. Introduction

 센서 네트워크의 주요 목표 중 하나는 장기간 동안 센싱 필드에 대한 정확한 정보를 제공하는 것이고 이를 위해서는 가능한 많은 센서가 필요하게 됩니다.

 그러나 배터리나 기타 자원 등의 제약이 당연히 따르게 되고 최소한의 센서로 최대의 효과를 내야 하는 것이 항상 과제 중 하나가 됩니다. 이런 식으로 효율을 높여야 네트워크 활동 시간이 크게 늘어나겠지요. 일반적으로 각 장비들의 배터리는 한정되어 있기 때문에 감지 구역에 분산형태로 배치하게 됩니다. 이때, 센서 네트워크를 수개월에서 수년까지 긴 기간 동안 사용하도록 하도록 설계되어 있는데 모든 센서가 항상 동작상태로 남게 되면 에너지가 빠르게 고갈되어 센서의 활동 기간이 짧아지게 되겠지요.

 따라서, 센서네트워크 수명 연장을 위해 센서의 동작과 수면 상태를 번갈아 가며 동작해야 합니다. 이를 위해 여러 가지 센서 선택 알고리즘이 사용되며, 임무 목표를 달성하는 동시에 네트워크 수명을 연장해야 합니다. 어떤 센서를 동작해야 하는지 결정은 알고리즘에 따라 배터리 에너지, 필요한 통신/탐지 범위 또는 필요한 정보 등 다양한 것들을 고려해야 합니다. 따라서 본 논문에서는 센서 선택에 사용되는 최근 제안된 기법들을 소개합니다. 이러한 기법들은 다양한 방식들로 분류되는데 중앙집중식(모든 처리가 단일 센서에서 수행)이거나 분산형(처리 비용이 여러 센서에 분산) 일 수 있습니다.

 본 논문에서는 아래 4가지 관점에서 센서 선택방법을 분류하려고 합니다.

 (1) 통신/탐지 반경(coverage) : 관심 위치 또는 목표의 통신/탐지 반경을 보장하기 위한 선택 기법

 (2) 목표물 탐지 및 위치를 결정하는 정확도 측면(Accuracy) : 목표 추적 및 위치 결정을 위해 센서를 선택하는 기법

 (3) 단일 미션 할당 : 미션이 하나일 때 센서를 선택하는 기법

 (4) 다중 미션 할당 : 다중 미션일 때 센서를 선택하는 기법

 

 아래에서부터는 2장에서는 센서 선택 시 발생할 수 있는 문제를 제기하고 3~6장에서는 각 기법들에 대한 설명을 하겠습니다. 그리고 7장에서는 센서 선택과 임무(미션) 간의 상관관계를 고려하여 어떻게 센서할당을 해야 하는지를 알아보고 8장에서는 이 분야에서 설명한 모든 방법들의 문제점을 알아보겠습니다.

 

 자 이제 2장부터 리뷰를 들어가겠습니다. 벌써부터 지치네요... 

 

2. THE SENSOR SELECTION PROBLEM

 이 파트를 간단히 요약하면, 다수의 센서가 S = {S1,..., Sn}과 같이 있을 때 S내에 존재하는 k개의 센서들로 최적의 부분집합을 만들어 하나 또는 다수의 미션을 수행하게 끔 해야 합니다. 아래 그림을 보시면 제일 9개의 센서로 동그라미 크기의 목표를 달성하는데 아래의 부분집합은 5~6개의 센서로 9개 센서와 유사한 성능을 나타내게 됩니다. 이때, 3개의 부분집합을 번갈아가며 가동한다면 에너지를 많이 절약할 수 있겠지요. 

 

 

부분집합

 

 최적의 부분집합은 반드시 센서 배터리나 기타 비용 제약조건을 충족시키면서 작업에 대한 정보의 정확도와 목표를 달성하는 집합입니다. 이때 정확도와 자원은 반드시 Trade off가 될 수밖에 없습니다. 정확도를 높이려면 센서가 많아야 되고 센서가 많으면 자원 소모는 커지고.. 이게 반복되게 됩니다. 이를 유틸리티와 비용 측면에서 이 논문은 분석하고 있습니다.

 - 유틸리티 : 수집된 정보의 정확도 및 임무에 대한 유용성

 - 비용 : 센서의 동작 상태에서 소비되는 에너지로 구성되며, 선택된 센서의 개수 k에 비례하여 증가 또는 감소합니다. 여기서 무선통신을 사용할 경우 센서 개수가 증가될 때 k개의 센서들의 운용상태 등도 확인해야 되니 더 많은 자원이 들어가게 됩니다.

 센서 선택 기법의 목표는 전체 비용이 특정한 예산보다 작고 총유틸리티를 최대화하는 k개의 센서 부분집합을 선택하는 것입니다. 이러한 문제는 NP-complete가 약하거나 거의 없고 이는 다항 시간 알고리즘이 없다는 것과 동일합니다. 하지만 의사 다항 시간 알고리즘(센서 수와 센서 비용에 다항식 시간 복잡도를 가지는 알고리즘)은 존재합니다. 하지만 의사 다항 시간 알고리즘은 다양한고 넓은 비용문제를 가지는 것에 적용하기에는 적합하지 않습니다. 따라서, 실제에 어떠한 알고리즘을 적용해야 할지가 이슈이기는 합니다.  이러한 것들을 어떻게 해결해야 하는지 3장부터 알아보겠습니다.

 

 우선 3장에 들어가기에 앞서 결정문제, 다항시간알고리즘, 비결정론, NP-complete 알고리즘이 무엇인지 알아봐야겠습니다. 리뷰 논문이라서 그런지 자세한 설명은 없고 이거~저거 했다고 하는 게 정말 귀찮네요.

 

 (1) 결정 문제(decision problem)

 컴퓨터에서 문제의 정의 : 입력의 집합과 답의 집합 사이의 관계입니다. 즉, 문제를 풀기 위해서는 입력 집합에 대한 어떠한 행위를 해서 답의 집합을 도출하는 것이므로 어떤 관계나 수식 등이 있을 겁니다. 그리고 이 문제들을 고려해서 입력이 참인지 거짓인지 따지는 것을 결정 문제라고 합니다. 어떤 명제는 참이면서 동시에 거짓일 수는 없습니다.

 (2) 다항 시간 알고리즘(Polynomial-Time Algorithm)

 알고리즘은 어떤 문제를 해결하는 방법을 컴퓨터가 이해할 수 있게 단계로 풀어서 기술한 것입니다.

 복잡한 문제를 풀기 위해서는 알고리즘이 여러 단계를 거쳐야 합니다. 이때 어떤 입력에 대해 알고리즘이 거친 단계의 수가 곧 알고리즘의 수행시간에 대응합니다. 그러므로 입력의 크기가 커지면 수행시간이 늘어나게 됩니다. 이때 입력의 개수를 n이라고 할 때 알고리즘의 수행하는 단계의 수가 어떤 다항식(n^3+3n+5 등)을 항상 넘지 않는다면, 우리는 이 알고리즘이 다항 시간에 동작한다고 합니다.

 (3) 비결정론(Nondeterminism)

 -결정론적 알고리즘(deterministic algorithm) : 무언가를 선택해야 되는 상황에서 하나만 고른 후 다음단계로 넘어갈 수 있어 직렬적으로 일을 처리합니다. 

 - 비결정론적 알고리즘 : 선택의 기로에서 모든 선택지를 다 고르고 각 선택의 기로마다 평행 세계(parallel universe)를 만들어 병렬적으로 일을 처리합니다.

 (4) NP-complete

 앞서 설명드린 어떤 비경론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합입니다.

 

 자 기초 지식도 습득하였으니 다음 장은 다음 포스팅에서 하도록 하겠습니다. 감사합니다.