Acquiring the snapshot of a distributed system helps gathering system related global state. In wireless sensor networks (WSNs), global state shows if a node is terminated or deadlock occurs along with many other situations which prevents a WSN from fully functioning. In this paper, we present a fully distributed snapshot acquisition algorithm adapted to tree topology wireless sensor networks (WSNs). Since snapshot acquisition is through control messages sent over highly lossy wireless channels and congested nodes, we enhanced the snapshot algorithm with a sink based reliability suit to achieve robustness. We analyzed the performance of the algorithm in terms of snapshot success ratio and response time in simulation and experimental small test bed environment. The results reveal that the proposed tailor made reliability model increases snapshot acquisition performance by a factor of seven and response time by a factor of two in a 30-node network. We have also shown that the proposed algorithm outperforms its counterparts in the specified network setting. 1. Introduction A distributed system consists of spatially separated computing machines that are able to communicate with each other using messages. These messages are passed over communication channels. A state of a distributed computing machine is characterized by its event history. This consists of the history of the local activities at a node and the message passing events on the communication channels. The global state of a distributed system is the collection of these properties. The global states are used to determine some stable properties such as termination detection and deadlock. In addition, they are used for protocol specification and verification and discarding obsolete information. A meaningful global state is obtained if the nodes under the distributed system record their states simultaneously [1]. This situation is technologically unfeasible because there is no global system clock for the distributed nodes. So, a distributed snapshot should be obtained with a coordinated manner. This can be possible when each node is able to receive a message which is used to alert it to take its local snapshot using a coordinated checkpointing algorithm. In addition, local states should be delivered in messages to a central node via reliable channels within a short time frame in order to generate meaningful global states. WSN can be considered as a distributed system consisting of a set of sensor nodes communicating via wireless channels. Yet WSN is not a complete distributed system since it lacks
References
[1]
A. D. Kshemkalyani, M. Raynal, and M. Singhal, “An introduction to snapshot algorithms in distributed computing,” Distributed Systems Engineering, vol. 2, no. 4, article 005, pp. 224–233, 1995.
[2]
A. da Silva, F. Teixeira, R. Lage, L. Ruiz, A. Loureiro, and J. Nogueira, “Using a distributed snapshot algorithm in wireless sensor networks,” in Proceedings of the 9th IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS '03), pp. 31–37, May 2003.
[3]
A. D. Kshemkalyani, “Fast and message-efficient global snapshot algorithms for large-scale distributed systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 9, pp. 1281–1289, 2010.
[4]
W. Wu, H. Liu, and H. Wu, “Res: a robust and efficient snapshot algorithm for wireless sensor networks,” in Proceedings of the 32nd International Conference on Distributed Computing Systems Workshops (ICDCSW '12), pp. 231–236, June 2012.
[5]
A. Segall, “Distributed network protocols,” IEEE Transactions on Information Theory, vol. 29, pp. 23–35, 1983.
[6]
J. Paek and R. Govindan, “RCRT: rate-controlled reliable transport for wireless sensor networks,” in Proceedings of the 5th ACM International Conference on Embedded Networked Sensor Systems (SenSys '07), pp. 305–319, November 2007.
[7]
Y. G. Iyer, S. Gandham, and S. Venkatesan, “STCP: a generic transport layer protocol for wireless sensor networks,” in Proceedings of the 14th International Conference on Computer Communications and Networks (ICCCN '05), pp. 449–454, October 2005.
[8]
S. Kim, R. Fonseca, P. Dutta et al., “Flush: a reliable bulk transport protocol for multihop wireless networks,” in Proceedings of the 5th ACM International Conference on Embedded Networked Sensor Systems (SenSys '07), pp. 351–365, New York, NY, USA, November 2007.
[9]
Y. Zhou, M. R. Lyu, J. Liu, and H. Wang, “PORT: a price-oriented reliable transport protocol for wireless sensor networks,” in Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering (ISSRE '05), pp. 117–126, November 2005.
[10]
A. Sharif, V. Potdar, and A. J. D. Rathnayaka, “Priority enabled transport layer protocol for wireless sensor network,” in Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications Workshops (WAINA '10), pp. 583–588, April 2010.
[11]
E. Giancoli, F. Jabour, and A. Pedroza, “CTCP: reliable transport control protocol for Sensor networks,” in Proceedings of the International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP '08), pp. 493–498, December 2008.
[12]
K. M. Chandy and L. Lamport, “Distributed snapshots: determining global states of distributed systems,” ACM Transactions on Computer Systems, vol. 3, no. 1, pp. 63–75, 1985.
[13]
J. Lian, L. Chen, K. Nak, Y. Liu, and G. B. Agnew, “Gradient boundary detection for time series snapshot construction in sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 10, pp. 1462–1475, 2007.
[14]
P. Levis, N. Lee, M. Welsh, and D. Culler, “TOSSIM: accurate and scalable simulation of entire TinyOS applications,” in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), pp. 126–137, New York, NY, USA, November 2003.
[15]
U. Department, TinyOS: an operating system for sensor networks, http://www.tinyos.net/.
[16]
T. Crossbow, TelosB Data Sheet, http://www.xbow.com/.
