In Data-Centric Storage sensor networks where numerous sensors collaborate to monitor and to report occurrences of environmental events, geographic routing algorithm can be used to route packets efficiently for data insertions and queries. However, the routing algorithm usually routes packets completely around perimeters enclosing destination locations. Such perimeter walks incur considerable amount of redundant traffic on sensor networks and waste node energy. In this dissertation, we analytically show that the overhead generated by perimeter walks is significant in many sensor networks with the number of sensor nodes ranging from hundreds to thousands. Motivated by the result, we propose a basic algorithm for pruning those walks to improve performance of DCS sensor networks that use geographic routing. Under assumptions that localization service is precise and radio coverage is a perfect circle, our proposal incurs no additional communication overhead; only require the knowledge of radio transmission range; but can reduce significant amount of insertion/query overhead.
Considering practical scenarios where localization service can be erroneous and node radio range can be irregular, we provide additional parameters that capture effects of location errors and radio irregularity. With the parameters, we mathematically analyze effects of location error and radio irregularity by reasoning on pruning probability of perimeter walks. Our analysis shows two important and interesting facts. Firstly, increasing radio irregularity is similar to reducing node density. When radio irregularity exists, once can increase density of nodes to compensate negative effects of irregular node radios. Secondly, location error is more severe to performance of DCS sensor networks. Particularity, in the presence of erroneous localization, increasing node density does not always improve performance. If sensor networks are sufficiently dense, increasing node density even reduces pruning probability of perimeter walks and degrades performance of DCS sensor networks.
In order to deal with imperfect localization and radio range, we propose a broadcast-based replication mechanism and a periodic refreshment algorithm to work with our basic pruning algorithm. The additional mechanisms also handle unexpected failures of nodes and increase reliability of DCS sensor networks in dynamic conditions. The broadcast-based replication mechanism exploits the broadcast nature of wireless transmission media to reduce traffic in the network and to rectify negative effects of erroneous localization service and radio irregularity. And the periodic refinement algorithm guarantees robustness in dynamic situations with node failures and mobility. By simulations we show that our scheme outperforms existing geographic routing DCS protocols while guaranteeing reliability of DCS operations under practical situations
본 논문은 Data Centric Storage (DCS) 센서 네트워크의 더욱 효율적이고 실용적인 환경 제공을 위해 DCS 센서 네트워크의 라우팅 문제를 해결하는 기법을 다룬다. 즉 DCS 센서 네트워크에서 발생하는 위치기반 라우팅 페리미터 워크(routing perimeter walk) 문제를 연구하고 해결책을 제안한다. 페리미터 워크 문제는 DCS센서 네트워크에서 페리미터 라우팅, 페이스 라우팅, 또는 위치정보를 이용한 랑데부 노드를 찾는 기법의 알고리즘을 사용하는 프로토콜에서 발생한다. 대개 라우팅 이상현상(routing pathologies)은 노드가 밀집하지 않은 경우에 발생하는데, 페리미터 워크 문제는 노드들이 아주 밀집한 환경에서도 발생한다. 그것은 DCS센서 네트워크가 페리미터 라우팅을 이용해서 데이터와 가장 근접한 노드를 찾아내기 때문이다.
본 논문이 제안한 페리미터 워크 문제의 중요성을 부각시키기 위해 페리미터 워크에 의해 발생되는 오버헤드를 수학적 모델을 사용하여 분석하였다. 본 논문은 페리미터 워크에 대한 조사와 분석을 바탕으로 DCS 센서 네트워크에서 대부분의 페리미터 워크문제를 해결하는 Basic-PWP 기법을 제안한다. Basic-PWP 의 기본적인 아이디어는 패킷이 목적지에 충분히 근접하다면 그 패킷에 대한 페리미터 워크는 프루닝(prune)하는 것이다. 우리는 R/2가 페리미터 워크 프루닝에 적합한 경계값으로 정하고 그 타당성을 증명하였다. 여기서 R은 radio range를 의미한다. 본 논문은 흥미로운 두 가지 중요한 사실을 발견했다. 첫째, 전파의 불규칙성(Radio irregularity)에 의한 효과는 노드의 조밀도와 대등하다는 것이다. 다시 말해, 전파의 불규칙성에 의해 나타나는 노드의 주파수 범위 감소는 노드의 조밀도 감소에 의해 발생하는 범위 감소와 동일하고 그 역도 성립한다. 둘째, 위치 정보의 에러는 DCS 센서 네트워크의 성능에 독특한 영향을 미친다. 노드의 밀집도가 낮은 네트워크에서 불완전한 지역화(localization)가 발생한다면 노드의 밀집도의 상승은 페리미터 워크의 프루닝 확률을 높인다. 하지만 네트워크가 충분히 밀집도가 높다면 노드의 밀집도 상승은 프루닝 확률의 저하를 가져온다. 만약 노드의 밀집도가 무한에 접근하면 프루닝 확률도 0에 접근한다. 또한 위치 에러가 전파의 유효 범위의 절반이상을 넘으면 프루닝 확률은 0이 된다.
본 연구가 수행한 실험결과를 통해 전파의 불규칙성과 불완전한 지역화라는 실제적인 시나리오에서는 지역화 에러로 인해 페리미터 워크를 프루닝하는 것은 거의 불가능하다는 결론에 이르렀고 DCS 센서 네트워크에서 휴리스틱 방법을 이용하여 해결하는 방법을 제시하였다. 실제적으로 목적지에 가장 가까운 랑데부 노드를 찾는 것은 매우 어려운 방법이므로 하나의 가장 가까운 랑데부 노드가 데이터를 가지고 있는 것이 아니고 목적지에 충분히 가까운 노드들에 모두 데이터를 저장한다. 그런 아이디어를 바탕으로 우리는 Prac-PWP 즉 Basic-PWP 알고리즘에 두 가지 매카니즘을 추가한 알고리즘을 개발했다. 여기서 두가지 매카니즘은 브로드캐스트 기반 복제(broadcast-based replication) 기법과 주기적 리프래쉬(periodic refresh) 기법을 의미한다. Prac-PWP에서 Basic-PWP 알고리즘은 페리미터 워크를 프루닝한다. 그리고 보로드캐스트 기반 복제 매카니즘은 무선 브로드캐스팅의 특성을 살려 주변의 노드들에게 데이터를 전해줌으로써 위치에러에 대해 대처하고 데이터의 신뢰성을 높일 수 있다. 주기적 리프래쉬는 동적인 환경에서의 노드들의 이동성과 실패를 효율적으로 대처함으로써 신뢰성을 높일 수 있다.
본 논문에 제안된 방법과 기존의 평탄화 문제를 해결하는 기법들은 상호보완적인 관계를 갖는다. Prac-PWP를 통해 효과적으로 페리미터 워크 문제를 해결하지만 평탄화 실패 문제(planarization failure)를 해결하지는 못한다. 반대로, 평탄화 문제를 해결하는 기존의 기법들은 페리미터 워크 문제를 해결하지 못한다. 따라서, 두 가지 기법을 동시에 사용함으로써 페리미터 워크 문제와 평탄화 문제를 해결할 수 있으며 밀집된(dense) 네트웍과 성긴(sparse) 네트웍에서 모두 효율적으로 동작할 수 있을 것으로 기대된다.
