DePauw University, Greencastle, IN 46135
Wireless sensor networks (WSNs) are clusters of wireless and often mobile devices, called nodes, which are set up within an environment without any existing infrastructure. These nodes communicate with each other or a base station. A few common applications of WSNs include: monitoring (wildlife habitats, medical conditions), surveillance (military target-tracking and battle field monitoring), smart offices and robotics. In order for these sensor networks to be useful, they must be able to communicate effectively and gather reliable data. Environmental factors such as temperature, humidity and altitude, coupled with oscillator clock irregularities between nodes result in a phenomena known as clock drift. To combat clock drift and other factors, sensor nodes within a network may be synchronized to a reference node to establish a common notion of time. Currently there are many synchronization algorithms. However, the diverse and expanding demand for WSNs prompts the advanced investigation of such algorithms. In this work, we propose CAPS, an improvement to the current multi-hop propagation algorithm proposed for the Timing-sync Protocol for Sensor Networks (TPSN).
TPSN works in three phases by assigning nodes into a level hierarchy. During the first phase, it establishes the root node [level 0]. During the second phase, level discovery is performed. In the level discovery phase, nodes are assigned levels depending on their proximity from the root node: All the nodes within transmission range of the root node are assigned level 1; the nodes within range of those nodes are assigned level 2 and so on. This guarantees that any level i node can communicate with at least one level i-1 node. If the level discovery phase comes across a node that has been previously assigned a level, the node is ignored. The third phase is the synchronization phase. During this phase, a node at level i uses sync handshakes to synchronize its clock with an adjacent level i-1 node. Thus, the relationship between duration of synchronization process and number of nodes for TPSN is linear because each node pair must perform synchronization. At the end of the synchronization phase, the total sync handshakes is (n1 + n2 + ...ni = n - 1 where ni is the number of nodes on level i.
Our proposed algorithm groups nodes into clusters based on their proximity to the root node. The dynamic election of a root node has remained a fairly simple process. After analysis of a networks’ topology, the node with the highest degree (most adjacent nodes) is elected as the root node. Nodes connected to the root node are assigned the label of level one cluster head if they are isolated from already-existing clusters on the same cluster level. The cluster-head is responsible for conducting synchronization within its cluster. There is only one cluster-head per cluster and nodes within the cluster must be connected to the cluster head. Once the cluster-head has been synchronized with a node from the previous level, it synchronizes its clock with each of the nodes in its cluster. It is possible that some nodes in a level will never broadcast synchronization messages to nodes in the next level which reduces the overall power consumption and the number of packets exchanged. Clusters in the same level are constructed so that they are isolated from each other which allows these same-level clusters to synchronize simultaneously without sending interfering messages, dramatically reducing the overall time needed to synchronize an entire network.
We experimentally compared the performance of CAPS to the TPSN multi-hop sync algorithm. Our results show extensive time-savings when using CAPS. In fact, the performance of CAPS improves as the size of the network increases, which makes CAPS a scalable algorithm. The percentage of time savings when using CAPS was over 77% when using a network of 1024 nodes compared to the TPSN multi-hop sync algorithm.
Future work will investigate the cluster size and cluster level relationship, and better cluster-head election in optimizing the CAPS algorithm.
[Abstract (PDF)]