이전 논문 리뷰에 이어 진행하겠습니다. 이 논문은 페이지가 압도적으로 많이 있습니다. 그래도 하나하나 살펴보며 여러분들과 저의 시야를 확장할 수 있는 기회가 되었으면 합니다.
1. 이전 포스팅 복습
이전 포스팅에서는 왜 다중 센서들을 서로소 집합으로 나누고 할당을 하는지 알아보았습니다. 그리고 NP-Complete도 알아보았죠.
NP-Complete는 어떤 비경론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합이라고 말씀드렸습니다. 이와 관련된 내용을 다시 한번 더 설명해 보죠. P 문제의 경우 정렬 문제와 같이 결정론적 튜링 머신으로 쉽게 풀 수 있는 문제들입니다. NP 문제는 비 결정론적 튜링머신으로 다항시간 내에 풀어낼 수 있는, 즉 시간이 오래 걸리는 문제들을 말합니다. 그리고 모든 NP 문제들을 어떤 문제 A로 환원(reduction)할 수 있고 환원한 문제를 해결할 수 있는다면, 이 문제 A는 NP-Complete라고 하고 환원한 문제를 해결할 수 없다면 이를 NP-Hard라고 합니다.
앞으로 이논문에서는 계속 NP-Complete 할 수 있다고 말을 한터인데 어렵고 다항시간(오래 걸림)이 걸릴 것인데 결국 해결할 수 있다는 것을 뜻합니다. 저번에 말씀드렸지만 비결정론은 병렬 연산이라 생각하시면 될 것 같습니다. 그러면 리뷰를 다시 진행해 보겠습니다.
2. Coverage 관점에서의 센서 선택
이 섹션에서는 선택된 센서가 전체 필드를 완벽하게 커버할 수 있도록 선택할 수 있는 최적의 방법에 대하여 논의 할 것입니다. 여기서 완벽한 Coverage란 원하는 필드 내에 목표물이 있을 때 적어도 하나의 센서가 목표물을 탐지하고 있는 상황을 말합니다. 그러면 센서가 멈춰 있을 경우와 움질 경우 두 가지 관점에서 한번 해석해 보겠습니다.
(1) 센서가 멈춰있을 경우
센서들이 빽빽하게 배치되어 커버리지에 중복이 되어 있을 경우, 모든 센서들이 활성화 될 필요가 당연히 없겠습니다. 즉, 불필요한 센서는 비활성화 상태로 들어가도 되겠지요. 이는 에너지를 절약시키고 네트워크 집단의 수명을 연장시키는 방법이 될 것입니다. 이 파트에서 센서 선택은 어떤 센서를 얼마나 활성화시키고 비활성화시킬지는 선택하는 것입니다. 물론 활성화 센서에 고장이 발생할 경우 비활성화 센서를 활성화시켜 그 부분을 채우는 것도 하나의 관점이 될 수 있겠지요.
예를 들어, Perillo와 Heinzlman은 각 센서 노드들을 집합으로 분할하여 각 집합이 필드의 커버리지를 완전히 커버할 수 있도록 구성하고, 한번에 하나의 집단만 활성화될 수 있도록 구성하였습니다. 아래 그림과 같지요.
이들이 제시한 것은 이러한 집합들을 최적으로 배치시키고 언제 어떻게 활성화/비활성화 할지 일정을 스캐쥴러 하여 네트워크 집단의 수명을 최대로 만들면서 대역폭 및 커버리지와 같은 다양한 미션을 만족시키는 방법입니다. 이 문제는 linear programing(LP) 통해 최적의 해를 찾습니다.
lenear programing이란 선형 계획법이라고 하며, 아래 그림처럼 최적화 문제의 일종으로 주어진 선형 조건들을 만족시키면서 선형인 목적 함수를 최적화하는 문제입니다.
Cardei와 Du는 센서들을 겹치지 않는 집합으로 나누어 모든 집합이 모든 대상을 완전히 커버하고 한 번에 하니의 집합만 활성화되게 하는 방법을 제시하였습니다. Perillo와 Heinzelman의 접근방법과 달이 집합들을 순환 순서로 일정하게 배치하여 겹치지 않는 최대 집합 개수를 찾는 문제에 초점이 맞춰져 있습니다. 집합의 개수가 증가할수록 당연히 효율성이 증가하게 됩니다. 비활성화할 수 있는 센서 집합의 개수가 늘어나기 때문이죠. 이 최대 개수의 겹치지 않는 집합을 찾는 문제를 DSC(Disjoint Set Cover) 문제로 정의하고 NP-complete임을 증명하여 휴리스틱 기반의 근사해를 제시합니다. Disjont set이란 여러 개의 중첩되지 않는 부분 집합으로 분할된 요소 집합을 뜻합니다. 즉, 겹치지 않는 것이죠. 휴리스틱은 경험에 기반하여 문제를 해결하는 방법입니다.
DSC 문제는 Mixed Interger Programming(MIP) 인스턴스로 정의된 max flow문제로 변환된다. MIP 출력을 사용하여 다항 시간 안에 겹치지 않는 집합들을 계산하게 됩니다.
단, 위의 접근 방식의 주요 단점은 센서 네트워크 환경에서 분산 방식으로는 구현하기가 상당히 어렵습니다.
SHhin 등은 중복되는 센서를 식별하고 비활성화함으로써 최소한의 센서로 완전한 커버리지를 얻는 연구를 하였고 성공하였습니다. 중복되는 센서의 식별은 Voronoi 다이어그램을 이용하게 돼 빈다. Voronoi 다이어그램은 센서의 물리적 위치와 그에 따른 커버리지를 표현하는 방법입니다. Voronoi 다이어그램은 여러 센서를 포함하는 다각형으로 평면을 나누는데, 각 다각형은 정확히 하나의 센서를 포함해야 하며, 해당 센서를 기준으로 다각형 내의 모든 부분은 다른 어떤 구역보다 가깝습니다. 아래 그림이 Voronoi 다이어 그램의 예시를 보여 줍니다.
Shih는 위 다이어그램을 이용하여 센서를 활성화하는 데 사용합니다. 이러한 알고리즘은 불필요한 센서를 비활성화시켜 에너지 소비를 균형 있게 조절하고 네트워크 수명을 연장하게 됩니다. 초기에는 모든 센서 노드들이 비활성화 상태이고 시작 노드는 다른 인접 노드가 활성화되어 있다고 가정하여 해당 노드를 기준으로 Voronoi 다이어 그램을 찾습니다. 그 후 Voronoi 셀의 영역이 해당 노드의 감지 영역 이하가 되도록 구성하여 활성 노드 집을 선택합니다. 이러한 최적의 이웃 집합을 찾는 것은 NP-complete문제이므로 n^2의 복잡도를 가지는 알고리즘을 제시합니다.
Yan 등은 self-scheduling 방식을 제안하였습니다. 이 방식은 각 센서 노드들이 특정 수준의 커버리지를 보장하면서 자체적으로 활성/비활성화를 하게 됩니다. 센서는 시간 동기화가 되어 있어야 하며, 각 센서는 주변 이웃들의 시간을 언제든지 참조할 수 있습니다. 그리고 이웃의 시간을 참조 및 관찰하여 자신의 활성/비활성 주기를 스스로 설정합니다. 각 노드들의 특정 변수를 조절함으로써 각 노드들의 차등 커버리지가 가능합니다. 이벤트가 많게 되면 당연히 커버리지가 커야 되어야 하며 많은 센서가 필요하게 되겠지요.
(2) 센서가 움직일 경우
센서가 이동 가능할 경우에는 다양한 옵션들이 발생하게 됩니다. 센서 노드는 커버리지의 빈틈을 채우기 위해 이동이 가능하기 때문이죠. 이로써 배치의 자유도가 올라가게 되는데 무작위 배치로 인해 커버리지가 부족할 경우에도 센서 노드들이 움직일 수 있기 때문에 재조정하여 커버리지를 보장할 수 있습니다. 마찬가지로, 특정 센서 노드에 문제가 발생하더라도 기타 노드들이 이동하여 네트워크를 지속적으로 유지/운용할 수 있습니다.
하지만 언제/어떻게/어디로 노드들을 이동시키는 선택 방식은 새로운 도전 과제이겠지요. 이동에 따른 추가적인 에너지 비용이 들기 때문에 어떤 노드들을 어떻게 이동할지 결정하는 것이 에너지 소모 측면에서 중요해집니다.
Kwok 등은 초기에 각 노드들을 무작위로 배치한 이후에 임무 지역을 완전히 커버하기 위해 제한된 범위에서 이동할 때 발생하는 비용을 최소화기 위한 방향을 제시합니다. 이 방법은 각 구역들을 그리드로 구분하고 그 그리드 안에 하나의 센서가 배치되어야 합니다. 이때 고려되는 것은 아래 2가지입니다.
- 센서가 이동하는 최대 거리를 최소화할 것
- 에너지(배터리) 사용량을 최소화 할 것
첫 번째 문제의 경우에는 센서와 그리드 포인트를 연결하는 이분 그래프에서 최대 비중치를 매칭해야 합니다. 그리드 중간/외각 이런 식으로 배치하는 것이죠. 두 번째 문제는 그리드 그래프에서 최소 가중치 매칭을 계산해서 해결하는 이는 7장에서 상세히 다뤄 보겠습니다.
Sekhar 등은 고장 난 센서 노드들을 대처하기 위해 최적의 노드를 선택하는 것을 목표로 하고 있습니다. 서로 다른 휴리스틱을 기반으로 하여 네 가지의 방식들이 어떤 것이 좋은지 평가받게 됩니다.
- 첫 번째 : 잔여 에너지가 많은 노드 선택
- 두 번째 : 이동 거리를 최소화
- 세 번째 : 첫 번째 방식과 두 번째 방식의 휴리스틱을 결합하여 최대이동거리/잔여 에너지 최솟값을 가진 노드를 선택
- 네 번째 : 각 노드가 이동해야 하는 최소 거 리르 계산하고, 이 최소 거리 중 최소인 노드들을 선택하여 커버되지 않은 영역을 커버시키는 가능성이 높은 것을 선택
Wang 등은 Bidding protocol을 사용하여 커버리지의 빈틈을 채우기 위해 어떤 센서들이 동할지를 결정하게 됩니다.
초기에 이동 센서가 불필요하게 중복 배치된 고정 및 이동 센서의 혼합 네트워크가 배치된 상태를 가정합니다. 고정 센서들은 필연적으로 커버리지에 빈틈이 발생하게 되고 이는 Voronoi 다각형을 사용하여 발견되게 됩니다. 아래 그림을 보시면 이 과정이 어떻게 진행되는지 설명되어 있습니다.
각 센서들은 커버리지의 빈틈을 채우기 위한 비용이 있는데 이 비용은 이동에 의해 생성된 새로운 빈틈의 크기와 관련이 있습니다. 네트워크의 고정 센서들은 커버리지 빈큼 크기를 추정하고 그에 따라 이동 센서들에 대한 입찰을 진행합니다. 이동 센서들 중 가장 높은 입찰을 선택하고 가장 큰 커버리지 빈틈을 매우기 위해 이동합니다.
여기까지 coverage 관점에서 어떤 고민들이 이뤄지는지 알아보았습니다. 다음 포스팅에서는 목표물 탐지 관점에서 센서가 어떻게 배치되어야 하는지 알아보시죠. 감사합니다.
'대학 과목 > 무선 모뎀 통신' 카테고리의 다른 글
| 논문 리뷰 : A Survey of Sensor Selection Schemes in Wireless Sensor Networks(4차 : Mission 관점) (33) | 2023.05.21 |
|---|---|
| 논문 리뷰 : A Survey of Sensor Selection Schemes in Wireless Sensor Networks(3차 : Tracking 관점) (26) | 2023.05.20 |
| 논문 리뷰 : A Survey of Sensor Selection Schemes in Wireless Sensor Networks(1차) (30) | 2023.05.18 |
| Error Function : 오차 함수 심화편(통신 관점) (24) | 2023.03.15 |
| Error Function : 오차함수의 개념 (8) | 2023.03.12 |
