최근 무선센서 네트워크는 화제감시, 사람의 출입이 어려운 장소의 모니터링, 군사지역의 보안 모니터링 등 다양한 응용 서비스를 제공하는 연구들을 바탕으로 언제, 어디서나 사용자가 정보 및 서비스를 제공받을 수 있는 유비쿼터스 기술의 실현을 가능하게 되었다[1]. 이러한 기술들이 더욱 유용한 정보를 제공하기 위해서는 감시대상인 모바일 노드의 위치정보를 제공해야 할 뿐만 아니라, 에너지의 효율적인 사용과 패킷전송의 성공확률을 높이기 위한 토폴로지를 구축해야한다. 하지만 위치인식을 위해서 가장 많이 이용되는 GPS는 실내에서는 사용할 수 없다는 문제가 발생한다. 따라서 무선센서 네트워크에서는 실내 위치 인식을 위해서 노드들 간의 거리나 각도를 측정하여, angle-of-arrival(AOA), time-of-arrival(TOA), time-difference-of-arrival(TDOA), received signal strength(RSS)와 같은 기술들을 사용하고 있다[2]. 하지만, 이와 같은 기술들은 노드들이 lineof-sight(LOS)환경에 있다는 가정 하에 사용되는 기술로써 실제 실내 환경인 non-line-of-sight (NLOS)환경에서는 심각한 오차가 발생하여 위치기반 네트워크의 성능을 저하시킨다[3]. 따라서 이러한 위치 오차를 보정하기 위해서 least square estimation(LSE)[4], min-max bounding box[5] 및 삼변측량법[6]과 같은 기법으로 위치추정 및 보정을 하는 많은 연구가 진행되고 있다.

본 논문에서는 서로 다른 정보를 이용해서 두 가지의 토폴로지를 구축하고, 이의 차이점을 이용해서 NLOS 환경에서 정확한 위치를 측정하고, 효율적인 토폴로지를 구축하는 알고리즘을 제안한다. 네트워크의 구성은 자신의 위치를 알고 있는 고정된 노드인 앵커노드와 위치추적의 대상인 모바일 노드로 구성된다. 첫 번째 토폴로지인 위치기반 토폴로지는 앵커노드의 위치로부터 측정된 모바일노드의 위치좌표를 이용해서 구축한다. 모바일노드의 위치좌표는 앵커노드와의 거리 값 정보를 토대로 minimum mean square error(MMSE)와 LSE 알고리즘을 활용하여 위치를 추정한다.

두 번째 토폴로지는 앵커노드를 제외하고 모바일 노드간의 측정된 거리 값을 가중치로 토폴로지를 구성한다. 두 번째 토폴로지는 위치정보를 알 수 없지만, 노드간의 거리 값만을 이용하기 때문에 NLOS환경으로 인한 위치오차의 문제점은 배제할 수 있다.

토폴로지 구축 후 각 모바일 노드는 두 토폴로지에서 각각의 연결과 가중치 값을 비교하여 토폴로지의 차이점을 찾아 위치오차가 있는 모바일노드를 찾고, 오차가 없는 모바일 노드들만을 이용해서 위치를 보정한다.

실제 실험에서 노드간의 거리를 측정하기 위해서 IEEE 802.15.4a에서 정의한 symmetric double sided two way ranging(SDS-TWR)[7]기술을 이용하는 NanoPAN 5375[8] 모트를 노드로 사용하여 수행되었다.

본 논문에서는 II장에서는 LOS와 NLOS환경에서 실제 측정되는 거리 값의 비교와 이 오차가 야기할 수 있는 문제점을 제시한 후, III장에서는 이를 해결하기 위한 알고리즘을 위치오차 탐지와 보정의 단계를 거쳐서 제안한다. 그리고 Ⅳ장에서는 실제 실험한 결과를 통하여 알고리즘의 성능을 확인하는 내용과 결론으로 구성된다.

무선센서 네트워크에서의 위치인식을 위해서는 노드 간에 데이터 패킷을 전송하여 거리를 측정해야 한다. 하지만 RF 신호의 특성으로 NLOS환경에서 반사, 굴절, 회절, 산란 등의 현상으로 오차가 발생한다.

그림1은 실내에서 벽과 가구가 거리측정 값에 미치는 영향을 나타내는 실험 결과로 60개의 RF 패킷을 SDS-TWR기술로 전송할 시 얻어지는 거리 값으로 구성되었다. 그림1에서의 결과는 NLOS환경의 경우는 LOS에 비하여 실제거리보다 멀게 인식이 되는 것을 보여준다. 이러한 결과는 그림2와 같은 문제를 발생시킬 것이다.

그림2는 무선센서 네트워크에서 발생할 수 있는 위치 인식 오차의 사례를 나타는 것으로 노드(w, z, u)는 모바일 노드이고, 노드(1, 2, 3)은 자신의 위치를 알고있는 앵커노드이다.

모바일 노드 u가 3개의 앵커노드로부터 SDS-TWR 기술을 이용해서 거리를 측정하고 LSE 알고리즘을 이용해서 위치를 추정하는 과정에서, 앵커노드1과 모바일 노드u 사이의 장해물 때문에 u의 위치는 u`로 추정이 된다. 이러한 오차는 위치 인식의 정확성을 떨어뜨린다. 또한 위치적으로 z와 u`의 좌표가 가깝게 인식되기 때문에 MST 알고리즘으로 위치기반 토폴로지를 구축한다면, 그림3(a)와 같은 이상적인 토폴로지가 아닌 그림 3(b)와 같이 연결되어 위치기반 네트워크의 성능을 저하시킨다.

실내 환경에서는 장해물에 의해서 NLOS환경이 발생하고, 이에 놓인 모바일 노드는 잘못된 위치 인식과 토폴로지 구축오류를 유발한다.

이러한 문제를 해결하기 위해서 새로운 알고리즘을 제안한다. 알고리즘은 위치 오차를 가지고 있는 모바일 노드를 찾는 단계를 거쳐 위치 오차를 보정하고 효율적인 토폴로지를 구축하는 것으로 구성된다.

위치오차를 감지하는 과정에서는 두 개의 토폴로지를 구축하고 차이점을 갖는 모바일 노드를 찾는 것을 목표로 한다. 우선 모든 앵커노드는 자신의 위치정보를 방송한다. 신호를 받은 모바일 노드는 식별 가능한 거리에 있는 모든 노드들과 서로 패킷을 주고받아 SDS-TWR기술을 통해서 모든 이웃 노드와의 거리와 앵커노드의 위치 정보가 담긴 테이블을 만든다. 각각의 모바일 노드는 테이블의 정보와 MMSE 와 LSE를 근간으로 하는 위치추정 알고리즘을 이용해서 자신의 위치를 추정한다.

추정된 모바일 노드의 좌표를 (x₀, y₀)라고 한다면 위치 추정 오차는 다음과 같은 식으로 나타낼 수 있다.

x_n 과 y_n 은 해당 모바일 노드의 이웃 중 n(1~N)번째 앵커노드의 좌표이고, 은 모바일 노드와 n(1~N)번째 앵커노드와의 좌표 상으로 계산된 거리 값이다. 위치추정 오차인 식(1)을 최소로 하는 미지수 (x₀, y₀)은 linear least square method(LLM)를 이용해서 계산한다. 선형화의 가정으로 ‘e_n(x₀, y₀) = 0’으로 설정하고, 추정 오차를 최소로 한 후 식(1)을 정리하면 다음과 같이 식(2)로 정리 할 수 있다.

식(2)는 이웃의 수만큼 만들 수 있으며, N번째 이웃의 거리 값과 n(1~N-1)번째 거리 값의 식을 연립하면 다음의 식(3)을 얻을 수 있다.

연립식인 식(3)은 총 N-1개를 만들 수 있기 때문에 총 이웃의 수인 N이 3이상이라면 (x₀, y₀)의 좌표 값을 얻을 수 있다. 위의 계산과정을 N-1의 행을 갖는 행렬로 연산을 표현하면 식(4)와 같이 정리하여 사용 할 수 있다.

이렇게 모바일 노드가 자신이 저장한 테이블의 정보로 자신의 위치를 추정한다면, 모든 노드들이 자신의 위치 좌표를 알기 때문에 좌표 상으로 계산된 거리가중치를 갖는 MST 토폴로지[9]를 구축할 수 있다.

MST 토폴로지의 구축은 Prim’ 알고리즘[10]을 따라서 그림4와 같은 과정으로 토폴로지를 구축한다.

위치 좌료를 이용해서 위치기반인 첫 번째 토폴로지를 구축 후, 모바일 노드는 모바일 노드 상호간의 거리만을 이용해서 두 번째 토폴로지를 구축한다. SDSTWR기술을 이용한 거리측정 결과를 가중치로 하여 MST 토폴로지를 구축하면, 모바일 노드들은 자신들의 위치 정보는 갖지 못하고 노드간의 거리 값과 자신과 연결된 노드의 정보만을 갖게 된다.

첫 번째로 구축한 토폴로지는 그림5(a)에서 나타내고 있다. 그림5(a)에서 모바일 노드 a는 위치오차로 인해서 실제로 가장 가까운 모바일 노드인 b가 아닌 d와 연결되어있는 문제가 발생한다. 두 번째로 구축한 토폴로지는 그림5(b)에서 나타내고 있다. 그림5(b)에서 각각의 모바일 노드는 자신들의 위치정보를 갖지 못한 상태이지만, 서로간의 거리 값만을 이용하기 때문에 NLOS환경으로 인한 위치오차의 영향을 받지 않는 것을 확인 할 수 있다.

두 가지 토폴로지가 구축되면, 각각의 모바일 노드는 두 토폴로지에서 자신과 연결이 되는 대상노드가 동일한가를 비교하고, 그 연결의 거리 값은 유사한지 파악을 한다. 이 때 연결되는 대상노드가 다르거나, 대상노드와의 거리 차이가 임계값(Δ_Th)을 넘어서면, 해당 모바일 노드는 위치오차를 가질 가능성이 있다고 판단한다. 임계값(Δ_Th)은 LOS환경에서 측정되는 거리 값의 표준편차(σ_d)값에 3배를 한 3σ_d로 설정하여, LOS환경을 NLOS환경으로 판단할 가능성을 1％ 미만으로 한다.

위치오차를 가질 가능성이 제기된 모바일 노드들은 다음 단계인 위치 보정의 단계를 거쳐서 위치를 보정하게 된다.

위치오차 감지 단계를 거치면, 모든 모바일 노드는 자신이 위치오차를 가질 가능성이 있는 노드인지 아닌지를 확인 할 수 있다. 만약 모바일 노드가 위치오차를 가질 가능성이 있는 노드라면, 자신의 위치오차 가능성을 방송한다.

패킷 정보를 수신한 모든 노드는 자신의 이웃노드를 Vn(위치오차 가능성이 없는 노드집합)과 Vm(위치오차 가능성이 있는 노드집합)로 구분을 짓는다. 만약 모바일 노드가 위치오차 가능성을 가지고, Vn에 속하는 노드가 3개 이상이라면, 해당 모바일 노드는 Vn의 노드정보를 이용해서 자신의 위치를 보정할 수 있고 식(5)와 같이 정의 할 수 있다.

만일 t시간 구간에서 Vn 집합의 원소의 수가 3개 미만이라면, 해당 모바일 노드의 보정은 수행할 수 없다. 하지만, 모바일 노드의 위치 보정은 동시에 각 노드마다 수행하기 때문에 시간 구간이 t+1이 되었을 시에는, Vn 집합의 원소의 수가 증가할 것이다. 따라서 모바일 노드 a의 시간 구간 t에서 위치오차를 식으로 표현한다면, 식(6)와 같이 나타낼 수 있다. 이를 토대로 시간이 지나면서 보정과정이 반복된다면, 식(6)의 위치오차 값은 식(7)로 표현할 수 있다.

위 식은 각 모바일 노드의 위치오차 값은 점점 작아진다는 것을 보여 주고 있다.

위의 그림5의 토폴로지로 예를 든다면, 모바일 노드 (a, b, d)는 위치오차의 가능성을 갖게 되고, 자신의 이웃을 Vn과 Vm집합으로 구분을 짓는다. 모바일 노드 a는 Vn집합인 {c, e, f}를 이용해서 자신의 위치를 보정할 수 있다.

제안된 알고리즘의 성능을 확인하기 위해서, NLOS 환경이 존재하는 실내 환경에서 실험을 하여 성능을 검증하였다. 실험을 수행하기 위해서 Nanotron에서 제공하는 NanoPAN5375[8] 모트를 노드로써 사용하여 SDS-TWR기술로 거리를 측정하였고, 결과확인을 위해서는 모트로 데이터를 수집하여 결과를 그림6으로 출력하였다.

실험환경은 10m X 10m의 환경에 4개의 앵커노드와 7개의 모바일 노드를 배치하였다. 모바일 노드 중 3,6번의 2개의 노드에 NLOS환경에 따른 거리 측정오차를 삽입하였고, LSE 알고리즘과 다변측량법으로 위치를 추정하였다.

실험결과인 그림6에서 (a)는 첫 번째로 구축되는 토폴로지로 모바일 노드 3, 6번에서 NLOS환경이 적용되어 위치오차가 생기는 것과 위치기반으로 구축된 토폴로지가 비효율적이라는 것을 보여주고 있다. 그림6(b)는 두 번째로 구축되는 토폴로지로 모바일 노드간의 거리 값만 인지하기 때문에 위치정보는 수정이 안 된 상태이다. 따라서 이웃 모바일 노드와의 거리만을 이용할 뿐 위치정보를 이용하지 않는 토폴로지이기 때문에 위치오차가 없을 경우에 구축될 토폴로지를 나타내고 있다.

그림6(a), (b)의 결과를 이용해서 토폴로지의 차이를 비교하면 위치 오차를 가질 가능성을 갖는 모바일 노드를 찾는다. 따라서 모바일 노드(2, 3), (6, 5), (7, 5), (3, 6)의 연결에서 차이점을 찾을 수 있고, 중복적으로 나타나는 3, 5, 6노드를 위치 오차를 가질 가능성이 있는 노드로 판단한다. 이제 각 모바일 노드는 자신의 이웃을 Vn과 Vm의 두 집합으로 구분을 하게 되는데, 3, 5, 6번 노드는 Vm집합에 포함되게 된다.

시간 구간 t에서는 1, 2, 4, 7번의 모바일 노드의 정보만으로 각각 자신의 위치정보를 보정하고, t+1시간 구간에서는 위치오차가 감지된 모바일 노드인 3, 5, 6번 노드가 Vn 집합의 원소로 인식된다. t+1구간에서 Vm 집합이 공집합이 되므로, 반복 보정은 중단되고, 최종적으로 보정된 추정위치를 이용해서 그림6(c)와 같은 결과를 확인 할 수 있다. 그림6(c)의 결과는 그림6(a)와 같은 가장 근거리에 있는 모바일 노드와 연결이 되는 토폴로지를 구축하고 있으며, 동시에 정확한 위치정보까지 알 수 있음을 확인하였고, 그 성능을 표1로 정리하였다.

표2는 제안된 알고리즘의 성능을 확인하기 위해서 동일한 실험 환경을 기준으로 기존의 다른 위치추정 알고리즘을 적용하여 성능을 비교한 결과이다. 기존의 알고리즘은 모바일 노드의 위치추정에 주안점을 두기 때문에 모바일 노드의 위치오차 평균값만을 비교하였다.

표2에서 비교하고 있는 알고리즘은 순서대로 linear least square(LLS), non linear least squares(NLS), minmax 그리고 w2 가중치를 이용한 extended min-max[11] 이다. LLS의 경우 구현이 가장 간단한 방법으로 제안된 알고리즘에서 초기위치를 구현할 때 이용된 알고리즘이다. LOS환경에 대해서는 NLS알고리즘이 가장 정확한 위치를 추정 할 수 있지만 위 실험환경과 같은 NLOS환경에서는 가장 부정확한 결과를 보인다. 또한 min-max와 extended min-max 결과에서도 알 수 있듯이 LOS환경에서 정확한 위치를 추정 할 수 있는 알고리즘 일수록 NLOS환경으로 받는 영향은 크다는 것을 알 수 있다.

본 논문은 실내 환경에서 효율적인 토폴로지를 구축함과 동시에 정확한 위치추정을 제공하는 알고리즘을 제안하였다. 기존에 존재하는 위치추정 알고리즘의 경우 LOS환경에 대하여 정확한 위치추정을 가능하게 하지만, NLOS의 경우에는 많은 오차 가능성을 가지고 있다. 그래서 위치인식 없이 노드간의 가중치만으로 토폴로지를 구축하여 기존 위치추정 알고리즘인 LSE알고리즘의 결과와 비교하고, 반복 보정하는 과정을 거쳐 NLOS환경에서의 위치 인식을 정확히 하였다.