Wireless sensor networks consist of many sensor nodes which have sensing, computing, and wireless communication capabilities. Due to the need of sensor nodes for various unattended monitoring applications, they are expected to be more prevalent as major sources in ubiquitous computing. Wireless sensor devices, however, typically have serious energy constraint i.e., limited battery power lasting only from several days to months. Thus, energy-efficiency should be considered a primary factor in developing sensor network applications. Especially, an efficient technique is required to transport data across a sensor network because energy consumption in data communication is much greater than that of local computation.
Geographic routing is an attractive choice for routing data in wireless sensor networks because of lightweight and scalable characteristics. The problem of geographic routing is that messages may be routed to a dead end. The void may be a disaster area where all sensors are destroyed, or it may be a bay where the sensors cannot survive. Once a message is routed to the dead end, it cannot proceed any further. Most geographic routing protocols include a void resolution method to detour a void area that has no active sensor. The previous solutions commonly use the right-hand rule for void resolution. However, the path produced by the right-hand rule is not energy-efficient in many cases.
Under certain ideal conditions, geographic routing works correctly and efficiently. The most commonly used geographic routing protocols include greedy forwarding coupled with face routing. Existing face routing algorithms use planarization techniques that rely on the unit-graph assumption. In real world, many conditions violate the unit-graph assumption of network connectivity, such as location errors, communication voids and radio irregularity, cause failure in planarization and consequently face routing.
We propose an efficient void resolution method, called Void-Resolution-Forwarding, which performs energy-efficient routing under realistic conditions without planarization techniques. Our method uses some variant of the conventional right-hand rule, called the quadrant-level right-hand rule, in determining a successor node when circumventing a void area. We show by performance experiments that the proposed method works better than the GPSR routing protocol.
계산 능력을 갖춘 무선 센서 장치들로 구성된 무선 센서 네트워크는 다양한 모니터링(monitoring) 응용에서 주로 사용되며 유비퀴터스 컴퓨팅에서 중요한 정보 수집원으로서 자리매김되고 있다. 그러나, 무선 센서 장치는 제한된 배터리 전원에 의존하므로 심각한 에너지 제약조건을 안고 있다. 따라서, 에너지 효율성은 무선 센서 네트워크 응용에서 가장 중요하게 고려해야 할 요소가 되고 있다. 특히, 무선 센서 장치에서 계산을 처리하는데 소요되는 에너지 소모량보다 무선 통신을 위한 에너지 소모량이 훨씬 많이 소요되기 때문에 무선 센서 네트워크의 수명을 연장하기 위해서는 에너지 효율적인 라우팅 기법이 요구된다.
또한, 센서 네트워크에서는 센서 노드들 사이에 다양한 형태의 장애물들이 존재할 수 있다. 이러한 장애물들로 인하여 라우팅 과정에서 해결해야 할 여러 가지 문제점들이 발생하게 된다. 즉, 장애물을 우회하는 과정에서 극복경로가 지나치게 길어질 수 있다. 따라서, 장애물이 많은 환경에서도 에너지 효율적으로 경로를 생성할 수 있는 라우팅 기법이 요구된다.
라우팅 과정에서 위치 정보를 활용하는 위치 기반 라우팅 방법은 기존 방법과는 달리 가볍고 확장성이 뛰어나므로 무선 센서 네트워크에서 널리 사용되고 있다. 위치 기반 라우팅 방법은 센서 네트워크 내에 존재하는 장애물 등으로 인해 라우팅이 실패할 수 있는 문제점이 존재한다. 대부분의 위치 기반 라우팅 프로토콜은 그리디 포워딩 방법과 장애물 지역을 벗어나기 위한 방법으로 구성되어 있다. 장애물 지역을 벗어나기 위한 기존의 솔루션은 통상 오른손-규칙을 사용한다. 그러나 대부분의 경우 오른손-규칙에 의해 생성되는 라우팅 경로는 에너지 비효율적이다.
위치 기반 라우팅 방법은 이상적인 조건 하에서 정확하고도 효율적으로 동작한다. 기존의 위치기반 라우팅 기법은 장애물 극복을 위해 전체 네트워크 그래프를 플라나(planar) 그래프로 변환하는 과정을 필요로 한다. 이 과정에서 실제 네트워크 토폴로지가 왜곡됨으로 인해 여러 가지 병폐가 나타날 수 있다.
이 논문에서는 센서 네트워크에서 에너지 효율적으로 장애물 지역을 벗어날 수 있는 방법을 제안한다. 즉, 목적지 중심의 극 좌표계를 기반으로 센서의 위치를 결정하고, 플라나 과정없이 장애물을 적응적으로 극복할 수 있는 라우팅 방법을 제안한다. 제안 방법에서는 장애물 지역을 우회하기 위해 메시지 수신 노드를 결정할 때 전통적인 오른손-규칙을 변형한 방법을 사용한다. 성능 실험에서 장애물을 극복하는 과정에서 제안방법이 GPSR 라우팅 프로토콜보다 에너지 효율적인 경로를 생성함을 보인다.
