WSNs (Wireless Sensor Networks) are networks of many sensor nodes that are distributed and wirelessly connected with multi-hop fashion. Each node in the WSNs normally battery operated has at least one sensor, an embedded processor, and a low-power transceiver. In WSNs, coordination of wake-up and sleeping time, TDMA schedules, ordering of collected sensor data and events and cooperation of multiple sensor nodes require sensor network nodes to have a precise common timescale. The purpose of the coordination of wake-up and sleeping time is to minimize nodes’ duty cycle for energy efficiency. Because of energy efficiency, precise common timescale over the network is very important. Time synchronization with a GPS receiver or the highly accurate crystal oscillators like OCXO, TCXO are feasible, but generally are ruled out in sensor node design due to excessive form factor, tight cost budget, and additional power consumption. One of methods to achieve the precise common timescale over nodes is time synchronization. However, since nodes in WSNs have a cheap and imperfect hardware clock, each clock in the nodes may drift away each other in time. For keeping a precise common timescale over the nodes, we need to periodically compensate drift and offset between each clock of nodes networked with multi-hop by using time synchronization protocols.
Several time synchronization protocols have been proposed to achieve the precise common timescale over the nodes, but we still have problems to be solved; power consumption grows linearly with the required precision and sync error grows with network size. For keeping a highly precise common timescale in the network, a high-frequency clock is required and a node with the high-frequency clock consumes more power than a node with the low-frequency clock. A recent research proposes a possible solution of the power consumption problem by combining a low-frequency clock for a common operation and a high-frequency clock for a specific operation required for high precision. While time synchronization error between a reference node and 1-hop neighbor nodes is achieved under 1 μs, a precise common timescale in multi-hop sensor network is not solved yet. The synchronization error over nodes in widely used FTSP grows with network size. PulseSync proposes a solution to solve the problem of FTSP, which is quick distribution of a global time of a reference node to all other nodes is completed in a single beacon interval. However, as network size increases, the distribution interval of a global time of a reference node also increases. This dis-sertation provides the Ripple flooding scheme, which fundamentally improves the convergence time of flood-ing regardless of network configuration. Based on the Ripple flooding scheme, we proposed time synchroni-zation protocol, which is a precise time synchronization protocol that achieves the fastest distribution of a global time of a reference node in multi-hop configuration without any scheduling.
In the dissertation, the Ripple flooding scheme, which is sending multiple packets at the same time, is proved to be feasible through the feasibility analysis. We implement the proposed scheme on the real sensor node with the MSP430 microcontroller and the CC2420 transceiver and we evaluate the proposed scheme by performance metrics, which are the convergence time and the reliability in various network scales and densities. The convergence time is at least 3.5 times faster than simple flooding in the dense network environments. We investigate the necessary conditions to achieve a precise common timescale in multi-hop sensor networks experimentally and propose a time synchronization RFTS, which presents the fastest distribution of time information of a reference node to all other nodes by using simultaneous packet broadcasting and adoption of the sanity check. Our evaluation shows that a quick distribution of a global time of the reference node to all other nodes is necessary, but the application of a distribution method which contains less error is also necessary to reduce synchronization error in multi-hop configuration. The RFTS which satisfies the two necessary conditions outperforms the widely used FTSP by a factor of 10. Average sync error of nodes in any hops in 6-hop line topology is under 0.23 μs and standard deviation of sync error also is under 0.19 μs. Due to the ripple flooding scheme for time synchronization, we can quickly distribute the time information without an estimation error and an elaborate scheduling for nodes and we can perform the sanity check to improve accuracy.
무선 센서 네트워크는 분산되어 무선 멀티 홉 형태로 연결되어 있는 수많은 센서 노드의 네트워크이다. 보통 배터리로 동작되는 무선 센서 네트워크의 각 노드는 적어도 하나의 센서, 임베디드 프로세서 및 저전력 트랜시버를 가지고 있다. 무선 센서 네트워크에서 웨이크업과 잠자는 시간, TDMA 일정, 수집된 센서 데이터와 이벤트에 정확한 순서를 매기고 여러 센서 노드의 협력을 위해서는 센서 네트워크의 각 노드가 정확하면서 공통된 시간 척도를 가지고 있어야한다. 웨이크업과 수면 시간의 조정의 목적은 에너지 효율을 위해 노드들의 듀티 사이클을 최소화하는 것이다. 그래서, 에너지 효율 때문에 각 노드간에 정확한 시간을 유지하는 것이 매우 중요하다. GPS 수신기 또는 OCXO, TCXO와 같은 고정밀 수정발진자를 가지고 시각 동기화를 하는 것은 가능하지만, 이를 사용했을 때 노드의 크기가 커지고, 가격이 비싸지며 및 전력 소비량이 늘어나 일반적인 센서 노드 설계에서는 이 같은 방법을 배제한다. 노드를 통해 정확한 공통된 시간 척도를 갖기 위한 방법 중 하나는 시각 동기화이다. 그러나, 무선 센서 네트워크의 노드는 저렴하고 불완전한 하드웨어 클럭을 가지고 있고 각 노드의 시계가 시간이 지날수록 서로간 더 달라진다. 우리는 시각 동기화 프로토콜을 사용하여, 멀티 홉으로 네트워크 되어 있는 노드들의 각 클럭간 드리프트와 오프셋을 주기적으로 보상함으로써 노드들 간에 정확하면서 공통된 시간 척도를 유지할 수 있다.
여러 시각 동기화 프로토콜들이 무선 센서 네트워크의 노드에 정확하면서 공통된 시간 척도를 제공하기 위해 제안되고 있지만, 여전히 해결할 문제가 있다; 전력 소모 문제와 멀티 홉에서의 정확한 공통 시간 척도를 확보하는 것이다. 네트워크에 고도로 정밀한 공통 시간 척도를 지키위해서, 고주파수 클럭이 필요하고 고주파 클럭을 가진 노드는 낮은 주파수 클럭을 가진 노드보다 더 많은 전력을 소모한다. 그러나, 최근 연구는 가능한 해결책을 제안하는데, 일반적인 동작에는 저주파 클럭을 사용하고 고정확을 요구하는 특별한 동작에는 고주파 클럭을 사용하여 원하는 정밀도 및 전력소모 문제를 해결하는 것이다. 1홉에서 시각 동기화 에러는 많은 경우 1 μs 이하를 보이지만, 멀티 홉 센서 네트워크에서 정확하면서 공통된 시간 척도를 갖는 것은 아직 해결되지 않았다. 널리 사용되는 FTSP의 경우, 노드에서의 시각 동기화 오류는 네트워크의 크기에 따라 커진다. PulseSync는 기준 노드의 공통 시각을 모든 다른 노드에게 비콘 간격 안에 빠른 배포를 하여 FTSP의 문제를 해결하는 방안을 제안했다. 그러나, 네트워크의 크기가 증가할수록, 기준 노드의 시간 배포 간격도 증가하여 실제적으로 FTSP가 지니고 있는 문제의 해결책이 되지는 못한다. 이 연구는 네트워크의 구성에 상관없이 플러딩의 컨버젼스 시간을 획기적으로 개선하는 리플 플러딩을 제안한다. 또한, 리플 플러딩에 기반하여 시각 동기화를 제안하는데, 이를 통해 별도의 스케쥴링없이 멀티홉 구성에서도 기준 노드의 시간을 네트워크내 다른 노드들에게 가장 빠르게 배포할 수 있다.
논문에서는 동시에 여러 노드가 동일한 패킷을 보내는 리플 플러딩 스킴의 타당성 분석을 하였고, 이를 통해 리플 플러딩이 가능하다는 것을 보인다. 또한, 우리는 제안된 방법을 MSP430 마이크로 컨트롤러 및 CC2420 트랜시버를 갖는 실제 센서 노드에서 구현하였고, 다양한 네트워크 구성과 밀집도하에서 컨버전스 시간과 리라이어빌리티라는 성능 지표로 평가했다. 컨버전스 시간은 밀집된 네트워크 환경에서 심플 플러딩보다 적어도 3.5 배 빠르다는 결과를 얻었다. 우리는 실험적으로 멀티 홉 센서 네트워크에서 정확하면서 공통된 시간 척도를 달성하기 위해 필요한 조건을 조사하였고, 동시에 패킷을 브로드캐스팅하고 새니티 체크를 적용하여 다른 모든 노드에게 기준 노드의 시간 정보를 가장 빠르게 배포하는 새로운 시각 동기화 RFTS를 제안한다. 우리의 실험 결과에 따르면, 다른 모든 노드에게 기준 노드의 빠른 시간 빠른 배포가 필요하지만, 적은 오류를 포함하는 배포 방법의 적용이 멀티 홉 구성에서 시각 동기화 오류를 줄이는데 또한 필요하다. 두 필요한 조건을 만족하는 RFTS는 널리 사용되는 FTSP에 비해 10배 좋은 성능을 보였다. 6 홉 라인 토폴로지에 있는 모든 홉의 평균 시각 동기화 오류는 0.23 μs이하이고 동기화 오류의 표준 편차도 0.19 μs 였다. 시간 동기화를 위한 리플 플러딩 스킴의 적용을 통해, 우리는 추정 오류가 없고 노드를 위한 정교한 스케쥴링 없이 빠르게 시간 정보를 배포할 수 있으며, 정밀도를 개선하기 위해 새니티 체크 수행할 수 있다.
이에 본 연구에서 제안한 시각 동기화 기법이 향후 연구, 개발될 다양한 무선 센서 네트워크 시스템 및 표준 프로토콜에서 활용됨으로써, 무선 센서 네트워크 시스템의 활성화에 기여할 수 있기를 기대한다.
