[본문스크랩] 센서 네트워크에서의 라우팅 프로토콜

 

▶ 무선 ad-hoc 라우팅 프로토콜과 센서 네트워크 라우팅 프로토콜의 차이

- 기존 무선 ad-hoc네트워크에서의 노드 수 < 센서 네트워크의 노드 수(엄청난 차이)

- 센서 노드들은 조밀하게 분포되고, 실패하기 쉽다.

- 센서 네트워크의 토폴로지는 매우 빈번하게 변화한다.

- 센서 노드들은 주로 방송(broadcast) 방식의 통신에 기반을 두지만, 대부분의 ad-hoc 네트워크는 점대점(point-to-point) 방식의 통신에 기반을 둔다.

- 센서 노드들은 제한된 전력, 연산 능력, 메모리를 가진다.

- 무선 센서 네트워크는 데이터 중심적 특성을 가지면서 특정 노드 간 라우팅이 필요하지 않으므로, 유일한 식별자를 기반으로 한 라우팅 기법은 적합하지 않다.

- 인접한 센서 노드들이 유사한 데이터를 가지므로, 각 센서 노드들이 데이터를 각각 전송하는 것보다, 전송 전에 데이터들을 모아서 전송하는 방법이 효과적이다.

- 응용에 따라 네트워크 요구 사항이 변하는 응용 특정적(application-specific) 특성을 가진다

 

 따라서, 무선 센서 네트워크를 위한 라우팅 프로토콜은 위에 언급된 차이점을 고려하면서, 다음의 부가적인 특성들을 수용하여야 한다.

- 무선 센서 네트워크에서는 감지될 물리적 파라미터를 지시하는 속성 기반 어드레싱이 일반적으로 사용된다.

- 대부분의 데이터가 위치에 기반을 두고 수집되므로, 노드들이 필요할 때마다 그들의 위치를 알 수 있도록 하여, 위치를 기반으로 한 라우팅이 가능하도록 한다.

▶ 무선 센서 네트워크의 큰 분류

 ①사전적 네트워크(proactive network): 노드들이 주기적으로 센서와 송신부의 스위치를 켜서, 환경을 감시하고, 응용의 관심(interest)에 속하는 데이터를 전송한다. 그래서, 주기적인 간격으로 네트워크의 상태를 파악할 수 있도록 하므로, 주기적인 데이터 감시를 요하는 응용에 적합하다.

 ②반응적 네트워크(reactive network): 노드들이 연속적으로 환경을 감지하여 감지된 속성값의 갑작스런 변화에 즉시 반응한다. 그래서, 이는 침입 탐지나 폭발 탐지와 시간 임계적인 응용에 적합하다.

▶ 무선 센서 네트워크에서의 라우팅 프로토콜

 참고로 무선 ad-hoc 라우팅 기법은 크게 평면 라우팅(flat routing)과 계층적 라우팅(hierarchical routing) 프로토콜로 나뉘어 진다.

평면 라우팅은 네트워크 전체를 하나의 영역으로 간주하여 모든 노드들이 동등하게 라우팅에 참여할 수 있고 멀티 홉 라우팅을 특징으로 한다. 반면에, 계층적 라우팅은 네트워크를 클러스터링을 기반으로 한 다수의 영역으로 분할하여 각각의 영역 내 특정 노드에 헤드의 역할을 부여하여 라우팅을 수행하도록 한다.

① 센서 네트워크를 위한 평면 라우팅 프로토콜

 기존의 무선 ad-hoc 평면 라우팅 프로토콜을 채택할 경우, 다음과 같은 문제점을 가진다. 요구 기반(on-demand) 방식을 적용할 경우, 수백에서 수천 개의 노드들이 경로를 찾기 위한 경로 요청 메시지들이 발생하게 되어 많은 에너지가 소비되고, 많은 지연이 발생하게 된다. 테이블 기반(table-driven) 방식에서는 센서 노드가 네트워크 내 수많은 노드까지의 경로를 유지하는데 한계가 존재한다.

가. Directed Diffusion

 Directed diffusion은 싱크의 질의 방송에 기반을 둔 데이터 중심적 라우팅 기법으로 질의 유포 및 처리 응용에 적합한 특성을 가진다. Directed diffusion에서 해당 응용에 대한 질의는 속성과 값의 쌍으로 구성되는 interest로 표현된다. Interest는 싱크에서 시작되어 네트워크 전체에 유포되고, 데이터 요청 노드로 질의에 부합하는 데이터를 전송하기 위한 경사(gradient)가 설정된다. 이때, 데이터는 다중 경로를 통해 요청 노드로 전송된다. 더 이상의 플러딩을 막기 위해 경로들 중 전송 품질이 좋은 몇 개의 경로들이 강화(reinforcement)되어, 강화된 경로를 통해 데이터 전송이 이루어진다. Directed diffusion의 이러한 정보 검색 방법은 요청 노드가 일정 기간 동안 질의에 부합하는 데이터를 요구하는 지속성 질의(persistent query)에 적합하다. 그러나, 경로를 단지 한번만 사용하는 형태의 질의에는 적합하지 않은 특성을 가진다. 또한, 이 프로토콜에서는 전송 경로의 중간 노드에서 데이터가 모아지므로 인접 노드들이 유사한 데이터를 가지는 센서 네트워크의 특성을 완전하게 이용하지 못한다.

나. Sensor Protocols for Information via Negotiation

 SPIN은 협상과 자원 적응에 의해 플러딩의 결함을 처리하기 위해 설계된 것으로, 센서 노드가 데이터에 대해 광고하고, 싱크로부터 요청을 기다리는 형태의 데이터 중심점 라우팅 기법이다. 이는 센서 노드가 데이터를 방송하는 대신 센서 데이터를 기술하는 메타 데이터를 전송하여 보다 효율적으로 동작하고 에너지를 보존하도록 한다.

 SPIN은 ADV, REQ, DATA 등의 세가지 메시지를 가진다. 센서 노드는 메타 데이터를 가지는 ADV 메시지를 방송한다. ADV의 메시지를 수신한 이웃 노드가, 데이터에 대한 관심을 가지고 REQ 메시지를 전송하면, 해당 이웃 노드를 위한 DATA 메시지를 전송한다. 결과적으로, 전체 센서 네트워크에서 해당 데이터에 관심있는 센서 노드들은 데이터에 대한 사본을 얻게 된다.

SPIN은 가까이 있는 노드들이 유사한 데이터를 가지는 속성을 활용하여, 다른 노드가 가지지 않는 데이터만을 분배하도록 한다. 또한, 사전적으로 동작하여, 사용자가 데이터를 요청하지 않은 경우에도 네트워크 전체에 정보를 분산시킨다.

다. Sequential Assignment Routing

 SAR에서는 라우팅 결정을 위해 각 경로에 있는 에너지 자원과 QoS, 그리고, 각 패킷의 우선 순위를 고려한다. 트리 구조의 다중 경로가 설정되어, 특정 경로가 실패하는 경우에도 경로 재계산을 위한 오버헤드가 없다. 각 노드에서 싱크까지의 다중 경로를 설정하기 위하여 싱크의 1홉 이웃들을 시작으로 낮은 QoS와 에너지 보유량을 가지는 노드들을 피하면서 구성된 다중 트리가 형성된다. 트리 설정 절차가 끝나면, 각 노드는 다중 경로에 속하게 되고, 각 노드는 싱크로 메시지를 전달할 트리를 선택할 수 있게 된다. 각 노드마다 다음 두 개의 파라미터가 싱크를 향한 각 경로(트리)와 연관된다.

- Energy resources: 해당 센서 노드가 경로를 독점하여 사용할 경우 전송할 수 있는 패킷 수

- Addictive QoS metric: 해당 값이 높을수록 낮은 QoS를 의미

 SAR에서는 addictive QoS metric과 패킷의 우선 순위와 관련된 가중치(weight) 계수의 곱인 weighted QoS metric을 계산하여 이의 평균값을 네트워크의 생존 기간 동안 최소화시키고자 한다. 위상 변화에 반응하기 위하여, 주기적인 경로 재계산이 싱크에 의해 시작된다. 실패에 대한 복구는 이웃 노드간의 핸드쉐이킹 절차를 통해 이루어지고, 지역 경로 복구 기법도 사용된다. 또한, 지역적인 협력 정보 처리를 위한 Single Winner Election(SWR)과 Multi Winner Election (MWE) 기법이 사용된다.

라. Minimum Cost Forwarding Algorithm for Large Sensor Networks

 이 기법은 센서 네트워크에서 데이터 흐름이 항상 싱크를 향한 방향으로 이루어지는 특성을 이용하였다. 이 기법에서 센서 노드는 유일한 ID나 메시지를 전송할 라우팅 테이블을 가질 필요 없이 싱크까지의 최소 비용 측정치만을 관리한다.

최소 비용 측정치를 관리하는 동작은 다음과 같다. 싱크에서 비용이 0으로 설정된 광고 메시지를 방송한다. 각 노드는 초기에 무한대로 설정된 측정 집합을 가진다. 노드가 광고 메시지를 수신하여 메시지의 측정치와 해당 메시지를 수신한 링크의 비용의 합이 현재의 측정치보다 작다고 판단하면, 이 값으로 현재의 측정치와 광고 메시지의 측정치를 갱신한다. 새로운 비용 측정치로 광고 메시지가 갱신된 경우에만, 해당 광고 메시지를 전송하고, 그렇지 않은 경우에는 제거한다. 이러한 과정을 통하여 네트워크 전체에 비용 필드가 구성된다.

 비용 필드를 기반으로 각 노드는 전송될 각 데이터 메시지를 방송하고, 데이터 메시지를 수신한 노드는 자신이 소스 센서 노드와 싱크간의 최소 비용 경로에 있는지 체크하여, 해당하는 경우에만 메시지를 방송한다.

노드에서 여러 번의 갱신이 일어나거나 여러 번의 전송을 수행하고, 싱크에서 멀리 떨어진 노드들이 더 많은 갱신이 일어날 수 있는 점을 해결하기 위하여, 현재 비용 측정치를 갱신할 때 백오프 기법을 적용하여, 갱신 시간으로부터 광고 메시지를 수신한 링크 비용의 정수배의 시간이 경과한 후에 광고 메시지를 전송하도록 한다.

② 센서 네트워크를 위한 클러스터링 기반 계층적 라우팅 프로토콜

 무선 선서 네트워크에서 인접한 노드간의 유사한 정보의 중복 전달로 인한 에너지 낭비를 줄이기 위한 “데이터 모음(data aggregation)”이 필요하다는 특성을 고려할 때 클러스터링에 기반한 계층적 라우팅 기법이 많은 장점을 가진다. 즉, 로컬 클러스터를 형성함으로써 인접한 지역에서 발생한 사건에 대한 유사한 정보를 클러스터 헤드로 전송하고 클러스터 헤드가 데이터 모음을 수행하여 보다 에너지 효율적인 라우팅을 가능하게 하며, 요청된 질의에 대한 클러스터 헤드에 의한 전달로 비효율적인 질의의 플러딩을 막을 수 있다.

 다음과 같은 전제가 필요하다.

- 지속적인 전력이 공급되는 싱크가 모든 센서 노드에 직접 데이터를 전달할 수 있고, 수집 데이터의 저장 및 데이터 가공 등의 에너지 집약적인 기능을 수행한다.

- 센서 필드내의 센서 노드들은 같은 특성을 가지며, 초기에 같은 에너지가 부여된다.

가. Low-Energy Adaptive Clustering Hierarchy

 LEACH는 클러스터링 기반 라우팅 기법으로, 클러스터 헤드가 클러스터의 멤버 노드들로부터 데이터를 수집하여 “데이터 퓨전”을 통해 데이터를 모아서 직접 싱크로 전달한다. 이 기법의 특징은 네트워크에 있는 모든 센서 노드들에 에너지 소비를 공정하게 분산시키기 위해, 에너지 집약적인 기능을 하는 클러스터 헤드를 무작위로 순환시키고, 전체적인 통신 비용을 줄이기 위해 클러스터 헤드에서 클러스터내의 데이터를 모아 지역적으로 퓨전하는 것이다. LEACH의 동작은 라운드라는 시간 단위로 이루어진다.

 각 라운드는 크게 클러스터가 구성되는 설정(setup) 단계와 여러 개의 TDMA 프레임으로 구성되는 지속 상태(steady-state) 단계로 이루어진다. 설정 단계의 시작에서 모든 노드는 자신이 현 라운드동안 클러스터 헤드가 될 수 있을지에 대해 이전 라운드들동안 클러스터 헤드였는지의 여부와 이상적 클러스터 헤드 수에 기반을 두고 결정한다. 현 라운드동안, 클러스터 헤드가 되기로 결정한 경우, 이를 이웃 센서 노드들에 알린다. 이를 수신한 비클러스터 헤드 노드들은 수신 강도 등의 파라미터를 기반으로 클러스터 헤드를 결정하며, 이를 클러스터 헤드로 전송하여 클러스터가 구성된다. 클러스터가 형성되면, 클러스터 헤드는 클러스터 멤버들의 데이터 전송 순서를 지시하는 TDMA 스케줄을 방송하고, 지속 상태 단계로 간다. 지속 상태 단계에서 각 클러스터 멤버 노드들은 자신의 전송 슬롯에서만 데이터를 전송하고 나머지 슬롯들에서는 sleep 모드로 가서 전력 소모를 줄인다. LEACH에서는 클러스터 내부에서는 TDMA를 사용하여 노드간 간섭을 피하고, 클러스터간의 간섭을 피하기 위하여 각 클러스터들이 서로 다른 확산 코드를 사용하는 방법을 채택한다.

LEACH의 성능은 매 라운드마다 일정한 수의 클러스터를 구성하고, 클러스터 헤드가 고르게 배치되는데 있으나, 자기 스스로 선출하는 방법으로는 이를 보장할 수가 없어, 싱크에서 센서 노드의 위치 정보와 에너지 보유량을 고려하여, 클러스터 헤드와 클러스터를 결정하는 LEACH-C 기법도 제안되었다.

나. Threshold sensitive Energy Efficient sensor Network protocol

 TEEN은 센서 노드들이 주기적으로 전송할 데이터를 가지지 않는다는 점을 제외하고, LEACH와 유사하게 동작한다. LEACH가 사전적 센서 네트워크에 적합한 특성을 가지지만, TEEN은 시간 임계적인 데이터를 처리한다는 점에서 반응적 센서 네트워크에 적합하다

 TEEN에서 센서 노드들은 클러스터 결정시간에 클러스터 헤드가 방송한 임계값인 Ht와 St에 기반을 두고 현재 감지된 데이터를 전송할지를 결정한다. 즉, 감지된 데이터의 값이 처음으로 Ht 를 초과하면, 이를 저장하여, 해당 시간 슬롯에 전송한다. 이후에는 감지된 데이터의 값이 저장된 값보다 St이상 큰 경우에 저장하고, 해당 시간 슬롯에 전송한다.

TEEN은 지진, 폭발 등과 같은 응용에서 요구되는 시간 임계적인 데이터가 실시간적으로 전달되고, 임계값이 클러스터 형성 결정 시간에 방송되므로 응용에 따라 사용자가 에너지 소비와 센서 네트워크 상태 판단의 정확성을 조절할 수 있다는 특징을 가진다. 반면에, 감지된 데이터의 값이 임계치에 도달하지 않는 경우 네트워크로부터 데이터를 얻어낼 수가 없어 모든 노드가 수명을 다한 경우에도 네트워크의 상태를 판단할 수 없고, 클러스터내에서 TDMA 스케줄링을 사용하여 시계 임계적 데이터의 보고에 지연을 가지며 모든 노드들이 해당 슬롯에 전송할 데이터를 가지는 것이 아니므로 자원이 낭비될 수 있다.

다. Adaptive Periodic Threshold-sensitive Energy Efficient Sensor Network Protocol

 APTEEN은 사전적 센서 네트워크와 반응적 센서 네트워크의 한계점을 최소화하면서 둘의 장점을 통합하는 하이브리드 네트워크를 제공한다. APTEEN을 채택한 하이브리드 네트워크에서, 센서 노드들은 데이터를 주기적으로 전송할 뿐만 아니라, 측정한 데이터의 속성 값의 갑작스런 변화에도 반응한다.

 APTEEN은 TEEN과 같은 형태로 시간 임계적 데이터를 처리하고, 사전적 동작을 위해서, 센서 노드가 카운트 시간동안 데이터를 전송하지 않은 경우 데이터를 감지해서 클러스터 헤드로 전송하도록 하여TEEN의 단점을 개선하였다.

 APTEEN에서는 인접한 노드들이 유사한 데이터를 감지하는 특성을 활용하여 인접한 두 노드의 쌍을 지어, 각 쌍에 대해 한 노드만이 질의에 응답하고, 다른 노드는 “sleep” 모드에서 전력 소비를 줄일 수 있도록 한다.

 APTEEN은 LEACH와 마찬가지로 클러스터 내부에서는 TDMA를 사용하여 노드간 간섭을 피하고, 클러스터간의 간섭을 피하기 위하여 각각의 클러스터들이 서로 다른 확산 코드를 사용하는 방법을 채택하나, 공통 CDMA 코드가 클러스터 헤드들로부터 싱크로 상향에서, 싱크에서 모든 센서 노드로 하향에서 사용된다. 그러므로, 클러스터 헤드와 싱크간의 전송 충돌을 막기 위해 (그림 8)과 같이 TDMA 스케줄에 싱크를 위한 별도의 슬롯이 할당된다.

 APTEEN은 주기적인 데이터를 전송해서 사용자에게 네트워크의 전반적 상황을 제공하고, 갑작스런 네트워크 상태의 변경에 즉각적으로 반응하여 시간 임계적 상황에 대응하도록 한다. 그리고, 사용자가 카운트 시간과 속성에 대한 임계값을 설정하여 에너지 소비를 제어할 수 있도록 한다. 그러나, APTEEN에서는 임계치 기능과 카운트 시간을 구현하는데 부가적인 비용이 요구되는 단점을 가진다.