센서 네트워크 구성 시 특정 목적(임무)을 달성하기 위해 가장 효율적으로 센서를 배치/활성/비활성화하는 방법에 대한 논문을 리뷰하였습니다. 최종적으로 정리를 해보겠으니 즐겁게 읽어 주시기 바랍니다.
1. Introduction
센서 네트워크 구성 시 성능(utility)을 최대로 하면서 비용을 최소화(수명을 최대화) 할 수 있는 방법에 대해 알아보겠습니다. 우선 센서를 아래와 같은 관점에서 센서 선택방법을 분류를 해 보겠습니다.
(1) 통신/탐지 반경(coverage) : 관심 위치 또는 목표의 통신/탐지 반경을 보장하기 위한 선택 기법
(2) 목표물 탐지 및 위치를 결정하는 정확도 측면(Accuracy) : 목표 추적 및 위치 결정을 위해 센서를 선택하는 기법
(3) 단일 미션 할당 : 미션이 하나일 때 센서를 선택하는 기법
(4) 다중 미션 할당 : 다중 미션일 때 센서를 선택하는 기법
위 그림을 확인해 보시면 파란색 점이 센서이고 (1)~(4)의 관점에서 각 센서들을 집합으로 만들어 구성해 놓은 원이 있습니다. 이 원은 coverage가 될 수 있고 accuracy 또는 미션이 될 수 있습니다. 즉, 센서를 어떤 목적으로 집합을 만들어 놓는지에 따라 다양한 관점에서 해답을 얻을 수 있습니다. 그러면 각 관점에 따른 센서 선택방법을 알아보겠습니다.
2. The Sensor Selection Problem
다수의 센서가 S = {S1,..., Sn}와 같이 있을 때 S내에 존재하는 k개의 센서들로 최적의 부분집합을 만들어 하나 또는 다수의 미션을 수행하게 끔 합니다. 아래 그림을 보시면 9개의 센서가 하나의 동그라미를 만들고 있는데 5개의 센서 만으로도 목표를 달성할 수 있습니다. 이때, 3개의 부분집합을 번갈아 가동하면 배터리 측면에서 네트워크 수명을 3배나 증가시킬 수 있겠지요. 그렇기 때문에 센서 선택은 필요하고 유틸리티와 비용 측면에서 고민을 해야 합니다.
- 유틸리티 : 수집된 정보의 정확도 및 임무에 대한 유용성
- 비용 : 센서의 동작 상태에서 소비되는 에너지로 구성되며, 선택된 센서의 개수 k에 비례하여 증가 또는 감소합니다. 여기서 무선통신을 사용할 경우 센서 개수가 증가될 때 k개의 센서들의 운용상태 등도 확인해야 되니 더 많은 자원이 들어가게 됩니다.
센서 선택 기법의 목표는 전체 비용이 특정한 예산보다 작고 총유틸리티를 최대화하는 k개의 센서 부분집합을 선택하는 것입니다. 다음 장에서는 이러한 문제들을 어떻게 해결하는지 알아볼 것입니다.
그전에 간단한 용어와 개념정리를 하고 넘어가겠습니다.
(1) 결정 문제(decision problem)
컴퓨터에서 문제의 정의 : 입력의 집합과 답의 집합 사이의 관계입니다. 즉, 문제를 풀기 위해서는 입력 집합에 대한 어떠한 행위를 해서 답의 집합을 도출하는 것이므로 어떤 관계나 수식 등이 있을 겁니다. 그리고 이 문제들을 고려해서 입력이 참인지 거짓인지 따지는 것을 결정 문제라고 합니다. 어떤 명제는 참이면서 동시에 거짓일 수는 없습니다.
(2) 다항 시간 알고리즘(Polynomial-Time Algorithm)
알고리즘은 어떤 문제를 해결하는 방법을 컴퓨터가 이해할 수 있게 단계로 풀어서 기술한 것입니다.
복잡한 문제를 풀기 위해서는 알고리즘이 여러 단계를 거쳐야 합니다. 이때 어떤 입력에 대해 알고리즘이 거친 단계의 수가 곧 알고리즘의 수행시간에 대응합니다. 그러므로 입력의 크기가 커지면 수행시간이 늘어나게 됩니다. 이때 입력의 개수를 n이라고 할 때 알고리즘의 수행하는 단계의 수가 어떤 다항식(n^3+3n+5 등)을 항상 넘지 않는다면, 우리는 이 알고리즘이 다항 시간에 동작한다고 합니다.
(3) 비결정론(Nondeterminism)
-결정론적 알고리즘(deterministic algorithm) : 무언가를 선택해야 되는 상황에서 하나만 고른 후 다음단계로 넘어갈 수 있어 직렬적으로 일을 처리합니다.
- 비결정론적 알고리즘 : 선택의 기로에서 모든 선택지를 다 고르고 각 선택의 기로마다 평행 세계(parallel universe)를 만들어 병렬적으로 일을 처리합니다.
(4) NP-complete
비경론적 알고리즘으로(병렬처리) 다항 시간(시간이 오래 걸리는 문제)에 해결할 수 있는 문제들의 집합입니다.
3. Coverage Schemes
선택된 센서가 전체 필드를 완벽하게 커버할 수 있는 최적의 방법에 설명하고 센서가 멈춰있거나 이동할 수 있는 환경에서도 어떻게 센서를 선택하는지 알아보겠습니다.
(1) 센서가 멈춰있는 경우
센서들이 밀집되어 잇는 경우 커버리지 달성을 위해 불필요하게 활성화되는 것들을 비활성화로 만들어야 자원을 최대한 절약할 수 있습니다. 즉, 어떤 센서를 활성/비활성화시키는 것이 상당히 중요한 관점이 될 것입니다.
Perillo와 Heinzlman은 각 센서 노드들을 집합으로 분할하여 각 집합이 필드의 커버리지를 완전히 커버할 수 있도록 구성하고, 한 번에 하나의 집단만 활성화될 수 있도록 구성하였습니다. 각 집단을 스케쥴러 하여(활성화/비활성화) 원하는 대역폭 및 커버리지를 달성하는데 이 문제는 Linear Programing(LP) 통해 최적의 해를 찾습니다.
Linear Programing(LP)이란 선형 계획법이라고 하며, 최적화 문제의 일종으로 주어진 선형 조건들을 만족시키면서 목적 함수를 최적화하는 방법입니다. 아래 그림에서 파란색과 빨간색 모두를 만족하는 최적 목적함수를 1차 함수로 나타낸 것입니다. 간단하지요.
Cardei와 Du도 비슷한 방법을 제시하였으나 위의 방법과 차이 나는 것은 집합에 겹쳐지는 센서가 없다는 점입니다. 즉, 집합들을 순환 순서로 일정하게 배치하여 겹치지 않는 최대 집합 개수를 찾는 것이죠. 집합의 개수가 증가할수록 당연히 효율성은 증가하게 됩니다. 최대한 겹쳐지지 않게 하는 문제는 DSC(Disjoint Set Cover)로 정의하고 NP-complete임을 증명하여 휴리스틱(경험적) 기반의 근사해를 제시합니다. 즉, 서로서 문제를 가져와 어떻게든 풀 수 있는 문제로 정의하고 경험적으로 문제를 푼다는 뜻입니다.
서로서 문제를 찾을 때 Mixed Integer Programming(MIP) 기법을 사용하는데 Max Flow 문제로 변환하게 됩니다. 이 최대플로우는 차 후에 자세히 설명드릴 건데 아래 그림에서 최대 유량을 보낼 수 있는 것을 선택하는 것입니다. 이 방법의 한계는 분산 방식으로 구현하기가 거의 불가능하다는 점입니다.
SHhin 등은 Voronoi 다이어그램을 이용해 중복되는 센서를 식별하고 비활성화 함으로써 최소한의 센서로 완전한 커버리지를 얻는 연구를 하였습니다. Voronoi 다이어그램은 아래 그림과 같으며, 센서의 물리적 위치와 그에 따른 커버리지를 표현한 것으로서 여러 센서를 포함하는 다각형으로 평면을 나누는데 이때 평면 안에는 하나의 센서로르 포함해야 하고 다른 센서보다 거리는 더 가까워야 합니다. 이렇게 함으로써 네트워크 수명을 연장하며, NP-complete 문제이므로 n^2의 복잡도를 가집니다.
Yan 등은 self-scheduling 방식을 제안하였습니다. 이 방식은 각 센서 노드들이 특정 수준의 커버리지를 보장하면서 자체적으로 활성/비활성화를 하게 됩니다. 이때 센서들은 서로 완벽히 동기화되어 있어야 하며, 주변 센서 노드들과 언제든 상호 참조할 수 있어야 합니다. 이 관찰을 통해 활성/비활성을 선택합니다. 하지만 이벤트가 많이 발생하게 되면 상당히 많은 에너지가 소모됩니다.
(2) 센서가 움직일 경우
센서가 움직일 경우에는 커버리지에 빈틈이 발생하였을 때 센서가 이동하여 언제든 빈틈을 매울 수 있고 이로써, 센서 배치의 자유도가 크게 상승하게 됩니다. 무작위로 배치하더라도 원하는 커버리지를 달성할 수 있죠. 물론 센서에 고장이 발생하였을 때도 유연하게 대처하여 네트워크를 지속적으로 유지/운용할 수 있습니다.
하지만, 센서들을 언제/어떻게/어디로/어떤 센서를 이동시키는 선택 방식은 새로운 과제입니다. 이동에 따른 추가적인 에너지 비용이 들기 때문에 어떻게 어떤 센서를 이동할지 경제적인 측면에서 고려가 필요합니다.
Kwok 등은 초기에 각 노드들을 무작위로 배치 후 이동시 발생하는 비용을 최소화하기 위한 방향으로 센서 선택을 합니다. 이 방법은 각 구역을 그리드로 구분하고 그리드 안에 하나의 센서가 존재해야 합니다. 이때 고려되는 것은 아래 2가지입니다.
- 센서가 이동하는 최대 거리를 최소화할 것
- 에너지(배터리) 사용량을 최소화 할 것
센서와 그리드 포인트를 연결하는 이분 그래프에서 최대 비중치를 매칭합니다.
Sekhar 등은 고장 난 센서 노드들을 대처하기 위해 최적의 노드를 선택하는 것을 목표로 하고 있습니다. 이를 선택하는 관점은 아래 4가지입니다.
- 첫 번째 : 잔여 에너지가 많은 노드 선택
- 두 번째 : 이동 거리를 최소화
- 세 번째 : 첫 번째 방식과 두 번째 방식의 휴리스틱을 결합하여 최대이동거리/잔여 에너지 최솟값을 가진 노드를 선택
- 네 번째 : 각 노드가 이동해야 하는 최소 거 리르 계산하고, 이 최소 거리 중 최소인 노드들을 선택하여 커버되지 않은 영역을 커버시키는 가능성이 높은 것을 선택
Wang 등은 Bidding protocol을 사용하여 커버리지의 빈틈을 채우기 위해 어떤 센서들이 동할지를 결정하게 됩니다.
초기에 이동 센서가 불필요하게 중복 배치된 고정 및 이동 센서의 혼합 네트워크가 배치된 상태를 가정합니다. 고정 센서들은 필연적으로 커버리지에 빈틈이 발생하게 되고 이는 Voronoi 다각형을 사용하여 발견되게 됩니다. 아래 그림을 보시면 이 과정이 어떻게 진행되는지 설명되어 있습니다.
각 센서들은 커버리지의 빈틈을 채우기 위한 비용이 있는데 이 비용은 이동에 의해 생성된 새로운 빈틈의 크기와 관련이 있습니다. 네트워크의 고정 센서들은 커버리지 빈틈 크기를 추정하고 그에 따라 이동 센서들에 대한 입찰을 진행합니다. 이동 센서들 중 가장 높은 입찰을 선택하고 가장 큰 커버리지 빈틈을 매우기 위해 이동합니다.
4. Target Tracking And Localization Schemes
목표물을 추적 및 위치 추정을 위해 센서들을 어떻게 선택해야 하는지에 대하여 설명드리겠습니다. 3가지 범주에서 선택되게 됩니다.
(1) 엔트로피 기반 설루션 : 측정 엔트로피를 최소화 하도록 설정
(2) 동적 정보 기반 솔루션 : 동적으로 수집된 정보에 기반하여 정보 획득을 최대로 하는 것
(3) 평균 제곱 오차 기반 설루션 : 측정값의 평균 제곱 오차를 최소화 하는 것이 목표
4.1. 엔트로피 기반 솔루션
엔트로피라는 것은 불확성의 척도(무질서도)를 의미합니다. 측정값의 엔트로피가 작을수록 정확성이 높아진다거나 안정화된다는 뜻입니다. 엔트로피 증가법칙이란 변화를 유발하는 온도차나 물질 구분이 없어지면서 더 이상의 변화가 일어나지 않는 상태를 뜻합니다.
- 볼츠만의 엔트로피
볼츠만은 기체 분자의 확률 또는 경우의 수를 써서 엔트로피를 표현하였습니다. 아래 그림을 보시면 많은 수의 기체 분자들을 한 곳에 몰려 있지 않고 골고루 흩어지죠. 이처럼 질서 정연하던 것이 무질서(disorder) 해지는 것을 볼 수 있습니다. 볼츠만은 기체 분자 거동에서 일어날 수 있는 경우의 수에 로그를 취한 값으로 정의하였습니다. 로그를 취함으로써 곱셈으로 늘어나는 경우의 수들이 덧셈으로 바뀌어 거듭제곱에 따라 증가하는 경우의 수를 선형적인 관계로 바꿀 수 있습니다.
Ertin과 Liu 등은 미래 상태와 현재 노드 측정값 간의 상호 정보를 통해 센서 정보를 획득하는데 센서 선택을 위해 탐욕 알고리즘을 사용합니다. 탐욕알고리즘이란 매 순간마다 해결책을 찾는 것으로써 The most obvious & immediate benefit를 가지고 방법을 선택하는데 엄청난 계산량이 발생할 수 있습니다. 그리고 눈앞의 이익만 취하기 때문에 종말에 가서는 그 답이 최적이란 보장도 없습니다. 여하튼 탐욕 알고리즘 적용은 아래와 같습니다(그리디가 탐욕 알고리즘입니다).
- 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
- 적정성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고 해결되지 않으면 선택 절차로 돌아간다.
그리고 이 알고리즘을 적용하려면 아래 조건을 만족해야 합니다.
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성된다.입니다.
이렇게 탐욕 알고리즘을 사용하면, 탐욕적 선택 시마다 목표물의 위치 분포의 엔트로피 감소가 최대화될 것으로 예산되는 센서와 관측값을 선택하게 됩니다. 새롭게 측정된 값은 재귀적인 베이시안 추정 기법을 사용하여 타깃 위치 분포를 결정합니다. 필요 이상의 센서를 사용하지 않으면서 엔트로피 수준에 도달하는 것이지요.
이 방식의 단점은 아래와 같습니다.
- 다양한 후보 센서들에 대한 데이터를 획득하지 않고 현재상태에서 미래 예측값만으로 센서를 선택하는 것이기 때문에 이 값이 효과적인지에 대한 평가가 불분명합니다.
- 현재 상태의 센서 값이 반드시 획득되어야 합니다.
- 후보 선택 결정을 단일 센서에서 하기 때문에 중앙 집중식이므로 확장성이 떨어지며, 통신 부하가 매우 크므로 많은 시나리오에 적용하기 어렵습니다.
Wang 등은 계산 비용이 많이 드는 상호 정보를 사용하여 최적의 솔루션을 찾는 대신, 하위 최적 솔루션을 제공하는 휴리스틱(경험적) 기법을 제안하였습니다. 이는 사전에 목표물에 대한 확률 분포와 일련의 센서 위치 및 모델이 주어진 경우 타겟 위치 분포, 선택된 센서 관측값 집합의 불확실성이 최대한으로 감소시킬 수 있도록 정보성 센서를 선택합니다. 제안된 휴리스틱 기법은 한 번에 한개의 센서를 활성화 하여 타겟 위치 분포의 엔트로피를 감소시키는데, 이방법 역시 중앙 집중식이어서 확장 가능성에 제한이 있습니다.
4.2 동적 정보 기반 솔루션
Zhao등은 센서 j개를 선택하여 목표물 위치 정확도를 가장 높게 하면서 비용을 최소화할 수 있는 방법을 제시하였습니다. 목표는 아래와 같습니다.
- 탐지 품질
- 추적 품질
- 확장성
- 생존성
- 자원 사용 개선
제안 방법은 표적이 있을 곳으로 예측되는 곳의 한 센서를 활성화시키고 그 센서를 리더 센서가 됩니다. 리더 센서는 정보성이 높다고 판단되는 후보 센서를 선택하여 리더를 넘기고 그다음리더가 다음 리더를 선택하는 형식으로 진행됩니다.
다음 리더를 선택할 때 현재 리더는 후보 센서의 정보 유틸리티 값을 고려해야 합니다. 정보 유틸리티는 추적에 대한 다양한 정보를 제공하고 센서의 위치, 모덜 리티, 신뢰 상태와 같은 정보 등이 됩니다.
저자는 센서 선택 시 엔트로피를 기반으로으로 한 정의와 거리 기반으로 한 정의 2가지를 고려합니다.
- 엔트로피 기반은 수학적으로 더 정확하지만, 실제 환경에 적용하기가 매우 어렵습니다. 이는 어떤 결정을 내리기 전에 센서의 측정값을 미리 알아야 되기 때문이지요.
- 거리기반 측정 기법을 이용하면, 리더 노드는 타깃 위치로부터 근접한 센서들의 유틸리티를 측정합니다. 직관적이며, 간단합니다. 이 방법의 단점은 첫 번째 리더의 선택이 전체 추적 품질에 영향을 미치는 것입니다. 첫 번째 리더 센서가 목표물과 멀리 떨어져 있을 경우, 예측 오류로 인하여 전체적인 추적 품질 저하가 일어 나거나 프로세스가 실패할 수 있습니다. 그리고 이방법의 경우 한 번에 하나의 센서만 선택하므로 에너지 측면에서 효율성이 있지만, 다양성을 보장하지 못합니다. 여러 개의 별령적 검사가 필요하겠지요?
Pahalawatta 등은 시간 단계마다 하나의 단일 센서를 선택하는 대신에 평균 에너지 제약 조건하에 정보 유틸리티 합이 최대화되는 센서 집합을 우선적으로 선택합니다. 그리고 리더센서에 목표물에 대한 데이터를 얻을 수 있는 기능을 추가하였습니다. 목표물에 대한 데이터를 우선적으로 수집하고 그 위치를 더 정확하게 추정한 후, 전체 집합에서 후보노드를 활성/비활성화시키는 방법입니다. 단, 리더노드가 모든 연산을 수행해야 하므로 리더 노드에 큰 부담을 주는 단점이 있습니다.
4.3 평균 제곱 오차(Mean Square Error, MSE) 기반 해결책
Kaplan 등은 시스템 응향특성을 이용하여 목표물의 방향(Direction of Arrival, DOA)을 추정할 수 있는 센서들을 구비하고 있습니다.
모든 센서를 활용하여 어떤 센서 집합이 목표물 위치를 찾기 위해 활성화되어야 하는지 결정하는 전역 노드 선택방법을 제시합니다.
- 초기 2개의 센서를 활성 집합으로 선택되는데 이를 선택하기 위해 모든 센서의 조합을 시도해야 하므로 계산량이 N^2으로 됩니다.
- 초기 활성화 센서 선택 후 탐욕알고리즘을 사용하여 후보 센서의 정보를 얻어 활성/비활성을 선택합니다. 즉, 표적 위치에 대한 MSE를 최소화하는 것입니다.
- 이 방법의 경우 비활성 노드들을 활성화시켜 품질을 개선할 수 있지만 전역 센서들 간의 정보 소통이 이뤄져야 하며, 이는 멀티홉 라우팅이 수행된다는 뜻이고 에너지 측면에서 너무 비효율 적이라 규모가 작은 네트워크에서만 사용 가능합니다.
이러한 단점을 파악한 Kaplan 등은 자율 노드 선택(Autonomous Nose Selection, ANS)이라는 로컬 노드 선택 방법을 제시하였습니다. 이 방법은 선택된 노드가 현재 활성 집합에 대해 상대적으로 얼마나 유용한지에 대한 로컬 정보에만 기반하여 노드를 선택합니다. 이를 위해 MSE 기법이 적용되며, 이 방법 역시 초기 활성화 집합을 선택하기 위해서는 전역 노드 선택방법이 사용됩니다. 초기 활성 집합을 선택한 이후에는 ANS가 활성 집합의 통신 범위 내에 있는 가 노드에서 사용됩니다. 이전에는 계속 광역으로 멀티홉 라우팅을 했던 거와 달리 로컬로 집합들을 확인해 가며, 유틸리를 계산하기 때문에 조금 더 낮다고 볼 수 있습니다. 하지만 이 방법 역시 초기에 멀티홉 라우팅을 시도하므로 많은 에너직 들어가기 때문에 규모가 작은 네트워크에서만 사용 가능합니다.
Tracking 관점에서 최정 정리는 다음과 같습니다.
- 엔트로피 : 탐욕 알고리즘을 사용하여 즉각적으로 엔트로피를 최소화시키는 방향으로 센서를 선택하며, 단일 노드에서 모든 판단을 해야 하므로 중앙 집중 방식이라 비 효율 적이며, 많은 시나리오에 적용하기 어렵습니다.
- 동적 정보 기반 : 수집된 정보에 기반하여 미래를 예측해 정보 획득하는 것이 최대의 목표이고 탐지 품질/추적 품질/확장성/생존성/자원 사용 개선 시점에서 리더 센서를 선택하고 후보 센서들 중 다음 리더 센서를 효율적으로 선택하는 방법입니다. 하지만 리더 노드는 다양한 판단을 해야 하므로 큰 부하를 가집니다.
- 평균 제곱 오차 : 목표물과의 거리가 최소가 되는 후보 센서를 선택하는 것이 목적인데 초기에 목표물의 위치를 찾기 위해 가용할 수 있는 모든 센서들을 이용해 스캐닝한 후 탐욕 알고리즘을 사용하므로 계산량이 상당히 크기 때문에 규모가 작은 네트워크에서나 적용 가능합니다.
5. Single Mission Assignment Schemes
이 세션 이후로 부터는 임무 기반에서 한번 센서 선택을 고려해 보겠습니다.
특정 미션을 반복수행하는 센서 네트워크에서 어떤 임무를 어떻게 수행할지 판단하는 것이 상당히 중요합니다.
즉, 임무에 따라 센서 노드를 선택해야 하는 것이죠. 이는 "응용 계측" 작업을 하는 것으로써 커버리지와 추적 성능 둘 다 끌어올리는 것이 목표입니다.
Byers와 Nasser 등은 목표 달성을 위해 아래의 것을 고려해서 비용 모델을 만들었습니다.
- 유틸리티 함수와 감지(정확도)
- 데이터 전송이로 인한 에너지 소비(비용)
알고리즘 세트에서는 센서들의 개수와 배치에 따라 얻을 수 있는 총 유틸리티 함수를 미리 가지고 있습니다. 그렇게 함으로써 미션마다 알고리즘 세트가 에너지 소비 측면에서 선택되어 네트워크 수명을 최대화합니다.
Bian 등은 총유틸리티를 최대화하면서 사용 가능한 에너지를 초과하지 않는 센서들의 집합을 만들고 선택하는 것입니다. 그리고 프레임워크를 사용하여 유틸리티와 센서 수명의 곱을 최대화할 수 있는 가장 효율적인 센서 집합을 찾습니다. 이때 프레임워크는 센서 유틸리티 값을 지정할 수 있습니다.
6. Multiple Missioin Assignment Schemes
여러 임무가 주어 졌을 때 센서 집합을 어떻게 선택하는지 알아보겠습니다. 이 또한 "응용 계측" 수준의 작업을 의미하고 다중 임무는 하나의 큰 작업에 속할 수 있고, 여러 분할된 작업일 수 있습니다.
Ai와 Abouzied는 최소한의 센서 수로 최대한 많은 목표물을 커버하는 것을 달성하기 위해 탐욕 알고리즘을 제안합니다. 이 경우 센서들은 방향성을 가지고 있으며, 각 표적의 커버리지 또는 다중 임무 관점에서 선택이 가능하게 됩니다.
- 초기 센서는 무작위 배치되어 모든 목표물을 커버하지 못합니다.
- 가장 많은 목표물을 커버하면서, 가능한 적은 수의 센서를 활성화하기 위한 방향으로 센서 방향을 설정합니다.
- 센서 개수(n), 목표물의 개수(m), 센서 가능 방향성(P)을 매개변수로 하는 정수 프로그래밍(IP : 정수로 설정된 목적함수) 문제로 정의합니다.
- 위 문제가 NP-Complete(별령적으로 임무를 다항시간 내에 완료하는 것) 임을 증명하였고, 탐욕 알고리즘 기반으로 해결책을 제시합니다.
- 모든 센서가 비활성화 상태에 있다가 위의 알고리즘을 반복적으로 수행하여 목표물 탐지를 위한 커버리지를 달성하기 위해 비활성화된 센서를 방향성에 맞게 다시 활성화시키게 됩니다. 이렇게 되면 목표물 커버리가 탐욕적으로 최대화가 되게 되며, 분산 방식으로도 구현이 가능합니다.
Mullen 등은 전체 시스템을 시장으로 모델링하여 전자 상거래 개념을 센서 관리에 통합하는 장점을 연구하였습니다. 이 시스템은 사전에 정의된 시스템의 목표와 우선순위에 기반하여 "상품"을 생산하게 됩니다. 이 모델의 주요 구성요소는 미션 매니저와 센서 매니저 그리고 유전 알고리즘(GA)을 사용하여 구현합니다.
- 미션 매니저 : 소비자와 관련된 다양한 임무와 그 요구상을 기초로 소비자에게 예산을 할당합니다.
- 미션 매니저 : 소비자는 예산 값을 기반으로 센서 매니저에게 입찰을 요구합니다. 입찰받은 센서 매니저는 임무에 맞는 센서를 할당하게 됩니다.
- 이 과정은 GA 방식으로 진행됩니다.
위 방식은 중앙 집중식 시스템이며, 모델의 복잡성과 GA 계산의 복잡성으로 분산 방식으로 구현하기가 매우 어려운데 유전 알고리즘(GA)에 대하여 잠깐 알아보고 가봅시다. 생물체가 환경에 적응하면서 진화해 가는 모습을 모방하여 찾아내는 방법으로 전역 최적점을 찾을 수 있으며, 수학적으로 명확히 정의되지 않은 문제에도 적응할 수 있습니다.
- 염색채(Chromosome) : 생물학적으로 유전 물질을 담고 있는 하나의 집합을 의미하여, 유전 알고리즘에는 하나의 해(solution)를 표현합니다.
- 유전자(Gene) : 염색체를 구성하는 요소로써, 하나의 유전 정보를 나타냅니다. 어떤 염색체가 A , B, C라면 이염색채는 각각 A, B 그리고 C을 갖는 3개의 gene가 존재합니다.
- 자손(Offspring) : 특정 시간 t에 존재했던 염색체들로부터 생성된 염색체를 t에 존재했던 염색체들의 자손이라고 합니다. 자손은 이전 세대와 비슷한 유전 정보를 갖습니다.
- 적합도(fitness) : 어떠한 염색체가 갖고 있는 고유 값으로써, 해당 문제에 대해 염색체가 표현하는 해가 얼마나 적합한지를 나타냅니다.
유전 알고리즘은 특정 시간 t에 존재하는 염색체들의 집합으로부터 적합도가 가장 좋은 염색체를 선택하고, 선택된 해의 방향성으로 반복하면서 최적의 해를 구하는 구조입니다. 적합도를 구하는 함수를 아래와 같으며, 일반적으로 롤렛 휠 선택방법을 사용하는데 정의된 P를 바탕으로 확률적으로 선택하는 것이 룰렛 휠 선택입니다. 적합도를 거리나 에너지를 봐도 되겠지요.
N은 염색체의 수이고 f는 염색체 적합도를 구하는 함수인데 이 함수가 최대로 되면 됩니다. 즉, 여러 개의 해로 구성된 해 집단을 만들고 평가한 뒤, 좋은 해를 선별해서 새로운 해 집단을 만드는 메타 휴리스틱 알고리즘입니다. 그림으로 알아보겠습니다. 아래와 같은 함수 f(x)가 있고, x에 따른 최솟값을 찾는다고 할 때, 토끼들을 배치시켜 놓으면 첫 번재 그림에서는 4, 5번만 살아님고 다 죽습니다. 다음 그림에서는 4, 5번의 자식들이 나오는대 다시 b, c 자식만 남기고 다 죽습니다. 이런식으로 최소값을 찾아가는 것이 유전자 알고리즘입니다.
아래는 유전자 알고리즘 순서도입니다.
위 문제를 해결하기 위해서는 해 표현의 방법/최대 세대수/종료 조건/세대 별 포함되는 해의 개수/ 교차 연산자/돌연변이 연산자/교차 비율/적합도 함수/돌연변이 비율 등이 미리 설정되어야 합니다.
Ostwald 등은 다중 모델 센서 들를 사용하고 다중 임무가 동시에 일어날 수 있다고 가정합니다. 가능한 센서 구성과 임무에 대한 임무 유틸리티값을 입찰로 변환합니다. 그리고 경매알고리즘을 적용하여 최적의 센서 집합을 선택 및 결정합니다.
7. Theoretical Approaches To Sensor-Mission Assignment
센서-임무 할당에 대한 이론적 접근을 해봅시다. 여러 임무들 사이에서 개별 센서를 선택하고 그 센서들을 임무에 맞게 할당을 해야 합니다. 즉, 개별 센서 사용의 비용과 개별 임무 간의 요구상에 따라 가장 좋은 방식으로 센서에 임무를 할당하는 것이 핵심이죠.
조금 더 상세하게는 센서 집합 S = {S1,.... Sm}와 임무 집합 M = {M1,.... Mn}이 주어졌을 때, 아래 그림처럼 (Si, Mj)와 같이 2분 그래프로 나타낼 수 있고 간선은 센서 Si를 임무 Mj에 할당하는 것을 의미합니다. 각 간선 (Si, Mj)는 유틸리티나 비용 값과 크게 연관이 됩니다.
7.1 플로우 기반 접근 방식
이분 그래프의 간선의 흐름을 플로우 기반으로 최적해를 도출해 보겠습니다. 위의 예시 그래프에서 최대 플로우를 찾음으로써 최적의 센서를 각 미션에 할당할 수 있겠지요.
7.1.1 최대 플로우
논문을 살펴보기 전에 최대 플로우에 대해서 이해해 보자. 최대 플로우는 간선에 흐르는 유량을 최대로 하는 것이다. 유량 네트워크에서 간선의 가중치는 비용이 아니라 용량(capacity)이라고 표현한다.
위 그림에서 간선을 비용(cost)라고 생각한다면, 총 14의 비용이 들며, 용량(capacity)라고 한다면 흐를 수 있는 유량은 2이니다. 최소치가 2이기 때문이 때문에 흘러 봤자 2가 됩니다. 우선 유량 네트워크의 용어부터 살펴보겠습니다.
- 유량 네트워크 : 간선에 용량이라는 속성이 있는 그래프
- 소스(source) : 유량이 시작하는 정점, 유일하게 유량이 발생하는 정점
- 싱크(sink) : 유량이 도착해야 하는 정점
- 용량(capacity) : 각 간선에 대해서 흐를 수 있는 최대 유량. c(u, v)
- 유량(flow) : 각 간선에 대해서 다음 constraints를 만족하는 값. f(u, v)
조건은 아래와 같습니다.
- 용량의 제한(capacity constraint) : 유량은 그 간선의 용량을 초과할 수 없다.
- 유량의 보전(conservation of flows) : 소스테어 싱크를 제외한 정점에는 들어오는 유량과 나가는 유량이 같다.
- 유량의 대칭성(skew symmetry) : u에서 v로 f만큼 유량이 흐르면 v에서 u로 -f만큼 유량이 흐른다.
- value of flow : 소스에서 싱크로 흘러가는 유량의 크기. 소스에서 나오는 유량은 모드 싱크로 흘러가므로 이는 소스에서 나오는 유량의 합과 같다.
- 최대 유량 문제 : value of flow의 최댓값을 구하는 문제이며 이를 구하는 알고리즘을 최대 유량 알고리즘이라고 한다.
포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm) : s(소스), t(싱크)
- 만약 s에서 t까지 모든 간선의 용량이 0보다 큰 경로 p를 구한다. 없으면 종료한다.
- 그 경로 용량의 최솟값 c를 구한다.
- p에 포함된 모든 간선(u, v)에 대해서 유량에 c를 더한다.
- 유량의 보존에 의해 반대 간선인(v, u)에는 유량에 c를 뺀다.
- 위 행위를 반복한다.
아래 그림 예제를 통해 한번 알아보도록 하겠습니다.
위 그림의 최대 유량 f는 아래 그림처럼 2가 됩니다.
라지만 아래 그림처럼 유량이 흐르며 어떻게 될까요.
s->a->b->t로 흐르게 되면 s->b, a->t로 더 이상 유량이 흐르지 못하므로 증가 경로가 없는 것처럼 보인다.
하지만 유량의 대칭성을 만족하기 위해서 포드-풀커슨 알고리즘에서는 t->b->a->s의 반대 간선으로 유량을 빼버렸습니다.
이렇게 되면 a->b->a->t로 아래 그림처럼 흘려보낼 수 있기 때문에 또 2개가 되지요.
이렇게 최대 유량/최적을 계산할 수 있습니다.
다시 논문 리뷰로 돌아오면, 포드-폴커슨 알고리즘은 다항시내에 해결이 됩니다. 출발지 s에서 t까지 아직 사용 가능한 경로가 남아 있는 한 경로 전체의 사용량을 가능한 높게 증가시킵니다. 남아 있는 경로가 없을 때까지 이 과정을 반복한 후 멈추게 되며, 포드-폴커슨에 의해 반환된 최대 플로우는 정수로 구성되며, 간선을 통과하는 플로우는 정수라는 뜻입니다.
7.1.2 최소 비용 최대 플로우
최대 플로우 문제의 경우, 최대 플로우 설루션이 유일하지 않을 수 있습니다. 간선의 용량과 단위 비용이 연관된 경우, 최소 총비용의 최대 플로우를 찾는 최소 비용 최대 플로우는 유일한 최대 플로우를 찾을 수 있습니다. 이를 다항시간 내에 해결하기 위해 다양한 방식들이 존재합니다. 그중에서 운용 문제에 관한 관점으로 해결해 보시죠.
운송 문제는 상품의 최소 비용 운송을 모델링하는 문제입니다. 이때, 소스와 터미널의 가중치가 있는 이분 그래프가 주어지고 간선의 가중치 wij는 si에서 mj로 상품 운송의 단위 비용입니다. 각 소스는 공급량 Pi를 가지고 각 터널은 수요량 Dj를 가지고 있습니다. 사용 가능한 공급량을 가지고 비용을 최소화하여 수요량을 맞춰야겠지요.
이 문제는 최소 비용 최대 플로우로 쉽게 해결이 가능한데, s와 t를 그래프에 추가하고 각 간선 (s, si)의 용량을 Pi로 설정하고, 각 간선(m, mj)의 용량을 Dj로 설정해서 포드-폴커슨 알고리즘을 사용하면 됩니다.
이분 그래프란 아래 그림처럼 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝정점이 서로 다른 그룹에 속하는 형태를 말합니다.
이분 매칭이란 A 정점으로 가는 간선, 각 B정점에서 싱크로 가는 간선들이 추가되고(이 간선들의 용량은 1), A, B 그룹 간의 간선 방향이 A->B일 때의 조건을 말합니다. 이분 매칭 문제의 답은 축약된 이분 그래프에서 매칭의 최대 개수를 말합니다. 이걸 최대 매칭이라 합니다.
위 그래프에서 A가 2와 5를 동시에 가리키고 있는데 이 둘을 동시에 선택하는 것은 불가능합니다. A를 두 번 선택하니까요. 포드-풀커슨 알고리즘을 돌리면, 소스 s에서 시작하는 경로를 찾기 위해 첫 번째로 방문하는 노드는 A에 속하는 점 중 하나입니다. 이걸 a라고 한다면, a에서 방문 가능한 정점은 반드시 B에 속합니다. 이걸 b라고 합시다. b에서는 일단 싱크 t로 밖에 갈 수 없습니다. 기본적 경로는 s->a->b->t 꼴이겠지요. 그러나 b에서는 음의 유량이 흐르는 경로를 찾아서 A에 속하는 다른 정점으로도 갈 수 있습니다. 이걸 반복하게되면, s->a->b->a'->b'->t, s->a->b->a''->b''->t시긍로 경로들이 발생합니다. A, B에 속하는 정점들이 반드시 교차되어 나타납니다.
양쪽 끝의 s, t를 생략해 버리고 중간 과정을 최대한 간소화 하는 것이 생략 기능입니다. 정점은 A 그룹의 것을 순서대로 훑으면서 아직 매칭이 안된 B가 있으면 매칭을 시도합니다. 또한 인접 리스트의 원소들(B 그룹에 속합) 역시 위부터 아래로 정렬되어 있다고 합시다. 맨 처음엔 (A,2) 매칭이 바로 이어집니다.
그다음, B의 인접 원소가 {2, 3, 4}인데 그중에 2가 이미 누군가와 매칭이 된 상태이고 그 상대가 A인데, A를 2 대신 다른 정점과 매칭시킬 수 있나 탐색했더니 5와 가능합니다. 그래서 매칭(A,2)이 소거되고 새로운 매칭(B,2), (A,5)가 생성됩니다.
매칭을 하는 데 성공했다는 말은 반드시 현재까지에 이어 매칭 수를 1 증가시켰다는 뜻입니다. 만약 이런 식으로 원래 매칭 상대이던 애를 다른 애와 매칭시키는 식으로 짝을 다시 지어주는 것이 불가능하면 실패입니다. 그다음 C는 1과 5로 가는데 1로 바로 매칭합니다. D는 1,2,5를 건드리니까, (C,1)은 소거되고 C를 5와 매칭시키고 원래 매칭이던 (A,5)가 소거되고 (AK,2)를 찾아주고 (B,2)도 사라지고 (B,3)을 찾아 줍니다. 이때 E를 더 이상 매칭을 만들 수 없습니다. 이렇게 되면 dead end가 발생하고 새로운 매칭을 할 수 없습니다. 이렇게 되면 최대 매칭은 4입니다.
7.2 매칭과 세미매칭
센서-미션 할당을 이분 매칭 문제로 표현하는 방법들을 살펴보겠습니다. 센서와 미션을 나타내는 두 개의 노드 집합에 대한 가장 큰 크기 또는 가장 큰 가중치를 갖는 매칭을 찾고자 합니다. 세미매칭 문제에서는 한쪽의 노드가 중복 사용될 수 있습니다. 즉, 여러 센서가 동일한 미션에 할당될 수 있다는 뜻이지요.
이분 매칭 문제는 이분 그래프가 주어지고 노드 집합 A와 B가 있다고 가정하면, 그래프에서 최대 매칭을 찾습니다. 최대 매칭이란, 선택된 에지들의 집합 중에 가장 크기가 큰 것을 의미하며, 선택된 두 에지가 동시에 하나의 끝점을 공유하면 안 됩니다. 이 문제를 다항시간 내에 해결하는 간단한 방법 중 하나는 최대 플로우로 축소하는 것입니다.
이분 매칭의 인스턴스를 최대 플로우 문제로 변화하기 위해서는 단순히 새로운 노드 s를 A의 각 집합에 연결하고, t를 B 집합에 연결하면 됩니다. 이때 모든 존재하는 에지의 용량은 1로 설정합니다. 그런 다음 최대 유량 알고리즘을 실행하여 정수 해를 생성하죠. 모든 에지의 용량이 1이므로, 결과적으로 유량으로부터 매칭을 얻어낼 수 있습니다.
가중치가 있는 이분매칭에서는, 음이 아닌 가중치를 갖는 두 노드 집합 A와 B의 이분 그래프가 주어집니다. 최대 가중치 매층, 즉 가중치의 합이 최대인 에지들의 부분 집합을 찾는 것입니다. 한번 선택된 에지는 두 번 선택되면 안 되며, 동시에 하나의 끝점을 공유해서도 안됩니다. 가중치는 음이 아니므로 , 모든 최대 가중치 매칭은 완전 매칭이 됩니다.
이분 세미-매칭은 일반적인 이분 매칭과 유사하지만 매칭 제약이 완화됩니다. A의 두 에지가 하나의 끝점을 공유하지 않는 에지들의 부분 집합을 찾고 최대 유량으로의 축소를 통해 문제를 해결할 수 있습니다.
가중치와 비가중치 매칭 모델은 센서 네트워크에 적용할 수 있는데 센서와 미션의 이분 그래프가 주어지면, 에지(Si, Mj)의 존재는 Si가 Mj에 어떤 서비스를 제공할 수 있다는 뜻입니다. 타당한 해결책에서 각 센서는 최대 하나의 미션에 할당되게 합니다.
가중치 반매칭 모델도 센서 할당 문제를 해결하는 데 사용됩니다. 센서와 미션의 가중치 이분 그래프가 주어지면, 각 에지(Si, Mj)는 센서가 미션에 대해 얼마나 유용한지를 나타내는 유틸리티값으로 판단합니다. 즉, 미션은 커버하되 더 나은 품질을 얻을 수 있는도록 하는데 목적이 있습니다. 그리고 각 센서는 하나의 미션에 할당될 수 있습니다. 이 방식은 간단하기 때문에 가중치 반매칭으로도 축소될 수 있습니다. 가중치 비가중치 버전의 매칭 문제는 Kowk 등이 센서-매션 할당의 문맥에서 연구하였습니다.
7.3 온라인 매칭과 반매칭
앞선 두 섹션에서는 전체 미션 집합이 한 번에 주어지고 오프라인 방식으로 문제를 해결한다고 하였습니다(동기화). 그러나 실제 현장에서 미션들은 서로 다른 시간에 들어오게 되고 이를 순차적인 온라인 모델로 설명합니다. 각가의 미션이 도착할 때마다 미션에 센서를 할당해야 합니다. 미래의 미션에 대한 정보 없이 이 결정들은 변경할 수 없습니다. 한번 센서가 할당되면, 이후의 어떤 미션에도 새할 당 될 수 없습니다.
Kalyanasundaram과 Pruhs는 B-Matching 문제의 온라인 비가중치 버전을 연구하였습니다.
B-Matching에서 서버와 요청을 포함하는 이분 그래프에 존재하는 에지들의 부분집합을 선택합니다. 에지의 존재는 서버가 요청을 처리할 수 있다는 것을 뜻합니다. 각각의 요청은 서버에 할당되어야 하며, 각 서버는 최대로 b개의 요청을 처리할 수 있습니다. 온라인 버전에서는 요청들과 그들의 모든 에너지가 한 번에 하나씩 도착합니다. 각 요청은 즉시 서버에 할당되거나 거부될 수 있습니다.
이때 BALANCE라는 알고리즘이 사용되는데, b가 클 경우 경쟁률이 1-1/e에 가까워집니다. 각각의 요청 r에 대해 BALNCE는 r의 이웃 중에서 지금까지 가장 적게 사용된 서버를 선택합니다.
센서와 미션 문제에 이를 적용하는 한 가지 방법은 각 센서가 최대 b개의 미션을 처리할 수 있다고 가정하는 것입니다. 이러한 제한이 주어지면, 미션들이 온라인으로 도착하는 상황에서 최대 매칭을 찾습니다.
8. Open Research Problems
센서 선택 문제는 해결해야 될 중요한 부분들이 있습니다.
- 서로 다른 우선순위를 가질 수 있는 여러 미션을 처리하는 문제
- 여러 미션은 상호 배타적이지 않을 수 있음
- 하나 이상의 작업이 미션 간에 공유될 수 있음
- 미션은 네트워크 수명동안 변경 될 수 있지만, 일부 작업은 변경되지 않을 수 있음
- 각 노드가 여러 작업을 수행 중 작업 일정을 조정하는 문제(미션은 서로 다른 우선순위를 가질 수 있으므로 노드를 미션에 할당하는 처리 과정에 이를 고려해야 함)
- 노드 재할당 문제(한 노드가 한 미션에 할당된 후에 더 유용한 다른 미션에 재 할당하는 문제) 이 경우 해당 노드는 대체 노드를 찾아야 합니다. 이러한 노드 재할당이 미션에 미치는 영향과 관련 비용을 연구해야 합니다. 아래 그림 예제를 보면 노드가 재 할당되는 것을 볼 수 있습니다. 이러한 상황에서 센서의 재구성은 작업 유틸리티와 정보 획득량을 모두 고려해야 하며, 기타 요소들과 함께 어떤 모드를 활성화할지 선택하는 것도 도전 과제입니다.
센서 유틸리티, 즉 센서가 작업에 얼마나 유용한지를 결정하는 문제는 앞선 포스팅에서 설명드렸습니다. 그러나 현재로서는 대부분의 방법이 센서의 위치와 같은 물리적 속성을 기반으로 유틸리티를 결정합니다.
즉, 물리적인 측면과 의미론적 측면 모두를 고려하는 정보 품질을 모두 다른 모델은 없는 실정입니다. 이때는 조건부 유틸리티에 대한 연구가 필요하게 됩니다. 조건부 유틸리티란 한 센서의 선택이 다른 센서의 유틸리티에 어떤 영향을 미치는지에 대한 연구입니다. 예를 들어 아래 그림에서 비디오 센서 A는 혼자 선택될 경우 높은 가치를 가질 수 있지만 F도 선택되면 중복으로 인해 A의 가치는 낮아질 수밖에 없습니다.
이러한 센서 선택 방법을 제안하는 많은 논문들은 이론적인 측면에서 문제를 고려합니다. 하지만 현실적인 다양한 것들이 고려되어야 하겠지요. 또한 수렴시간/통신 오버헤드/센서 네트워크 수명에 미치는 영향 등 다양한 요소들로 연구가 진행되어야 할 것입니다.
대부분의 센서 선택 시 고려되는 비용은 에너지뿐입니다. 에너지는 센서 노드에서 가장 값진 자원일 수 있지만, 다른 자원의 제약도 고려되어야 합니다. 대역폭도 센서 선택 시 결정적인 것이 될 수 있겠지요.
마지막으로 선택의 목적(모니터링, 쿼리 응답, 데이터 배포, 장애 허용 등)이 선택 방식에 어떻게 영향을 미칠 수 있는지에 대한 연구도 필요합니다.
9. Conclusion
이 논문에서는 무선 센서 네트워크에서 센서 선택 문제를 조사하였습니다. 우리는 아래 네 가지의 유형에서 살펴보았습니다.
- 커버리지 방법
- 대상 추적 및 위치 결정 방법
- 단일 미션 할당 방법
- 다중 미션 할당 방법
또한 다른 분야에서 유사한 선택 및 매칭 문제에 대한 설루션을 살펴보고 센서 네트워크 적용 가능성을 논의했습니다.
수일에 걸친 논문 리뷰를 마칩니다. 이번 논문을 어디에다 사용할지 깊은 고민에 빠지는군요.
