Abstract
A wireless sensor network (WSN) consists of spatially distributed autonomous devices which use sensor nodes to monitor physical or environmental conditions cooperatively. Currently, WSNs are expected to be integrated into the internet of things (IoT), where sensor nodes join the internet dynamically and collaborate to accomplish their tasks. In the application of the IoT, WSNs can play an important role by collecting surrounding contextual and environmental information. However, ensuring a stable and reliable topology is an important issue with regard to WSNs. To cope with the influence of faulty components, it is essential to reach a common agreement in the presence of faults, before performing certain tasks. However, the Byzantine agreement (BA) problem is a fundamental issue in fault-tolerant distributed systems. To enhance the fault tolerance and reliability of the WSN, the BA problem in the cluster-based WSN (CWSN) is revisited in this study. The proposed protocol can achieve agreement on a common value among all functional nodes in a minimal number of message exchange rounds, and can tolerate a maximal number of allowable faulty components in the CWSN.
Similar content being viewed by others
References
Akyildiz, I. F., Weilian, S., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. IEEE Communications Magazine, 40(8), 102–114.
Balakrishnan, R., & Ranganathan, K. (2012). A textbook of graph theory. Berlin: Springer.
Chen, G., Li, C., Ye, M., & Wu, J. (2009). An unequal cluster-based routing protocol in wireless sensor networks. Wireless Networks, 15(2), 193–207.
Christin, D., Reinhardt, A., Mogre, P. S., & Steinmetz, R. (2009). Wireless sensor networks and the internet of things: selected challenges. In Proceedings of the 8th GI/ITG KuVS Fachgesprch Drahtlose Sensornetze (pp. 31–33).
Correia, M., Neves, N. F., Lung, L. C., & Verıssimo, P. (2005). Low complexity Byzantine-resilient consensus. Distributed Computing, 17, 237–249.
Fischer, M. (1983). The consensus problem in unreliable distributed systems (A brief survey). Lecture Notes in Computer Science, 158, 127–140.
Kapron, B. M., Kempe, D., King, V., Saia, J., & Sanwalani, V. (2010). Fast asynchronous Byzantine agreement and leader election with full information. ACM Transactions on Algorithms, 6(4), 1038–1047.
Indranil, G., Riordan, D., Srinivas, S. (2005). Cluster-head election using fuzzy logic for wireless sensor networks. In Proceedings of the 3rd annual conference on communication networks and services research, (pp. 255–260).
Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine general problem. ACM Transactions on Programming Language and Systems, 4(3), 382–401.
Meyer, F. J., & Pradhan, D. K. (1991). Consensus with dual failure modes. IEEE Transactions on Parallel and Distributed Systems, 2(2), 214–222.
Olifer, N., & Olifer, V. (2006). Computer network: Principles, technologies and protocols for network design. New York: Wiley.
Siu, H. S., Chin, Y. H., & Yang, W. P. (1996). A note on consensus on dual failure modes. IEEE Transactions on Parallel and Distributed Systems, 7(3), 225–230.
Wang, S. C., Yan, K. Q., & Cheng, C. F. (2004). Efficient multicasting agreement protocol. Computer Standards & Interfaces, 26(2), 93–111.
Wang, S. C., Liau, W. B., Yan, K. Q., Huang, C. P. (2010). The anatomy study of efficient agreement in a cloud computing environment with fallible processes. In Proceedings of the 2010 3rd IEEE international conference on computer science and information technology (IEEE ICCSIT 2010) (pp. 124–128).
Wang, S. S., Yan, K. Q., & Wang, S. C. (2011). Achieving efficient agreement within a dual-failure cloud-computing environment. Expert Systems with Applications 38, 906–915.
Wang, S. S., Yan, K. Q., Wang, S. C., & Liu, C. W. (2011). An integrated intrusion detection system for cluster-based wireless sensor networks. Expert Systems with Applications, 38, 15234–15243.
Acknowledgments
This work was supported in part by the Taiwan National Science Council under Grants NSC101-2221-E-324-032 and 101-2221-E-324-034.
Author information
Authors and Affiliations
Corresponding authors
Appendices
Appendix 1: Manchester Encoding
Manchester encoding is a synchronous clock encoding technique used by the OSI physical layer to encode the clock and data of a synchronous bit stream [11]. In this technique, the actual binary data to be transmitted over the cable are not sent as a sequence of logical 1’s and 0’s. Instead, the bits are translated into a slightly different format that has a number of advantages over using straight binary encoding. The rules of Manchester encoding are shown in Table 1.
Figure 5 shows a typical Manchester encoded signal with the corresponding binary representation of the data (1,0,1,0,0,0) being sent.
In the Manchester encoding shown, logic 0 is indicated by a 0 to 1 (upward transition at bit centre) transition at the centre of the bit and logic 1 is indicated by a 1 to 0 (downward transition at bit centre) transition at the centre of the bit [11].
Due to the fact that a crash fault happens when a component is broken, in such a case, the component would not send any signal to the receiving processor. An omission fault occurs when a component fails to transmit or receive the signal on time or at all. A stuck-at fault occurs when the signal from a certain communication medium is constant. Therefore, a healthy processor can detect crash faults, omission faults, and stuck-at faults caused by the faulty components if the protocol encodes a transmitted message via the Manchester code before transmission.
Appendix 2: The Message-Gathering Tree (mg-tree)
Figure 4d shows an mg-tree for the CWSN model shown in Fig. 4a. Each healthy node maintains such an mg-tree during the execution of TAP. In the first round, the source (node \(n_{s}\)) multicasts its initial value to each cluster’s nodes by TTCB through TTCB control channel. When healthy node receives the value sent from the source, it stores the received value, denoted as \(\hbox {val}(s)\), at the root of its mg-tree as shown in Fig. 4b. In the second round, each node multicasts the value stored in the root of the mg-tree to each cluster’s nodes (except the source node) by TTCB through TTCB control channel. If the node \(n_{1}\) sends message \(\hbox {val}(s)\) to the nodes in cluster \(C_{4}\), then the nodes in cluster \(C_{4}\) stores the received value from node \(n_{1}\), denoted as \(\hbox {val}(s4)\), in vertex \(s4\) of its mg-tree, which is shown in Fig. 4c. Similarly, if the nodes in cluster \(C_{2}\) sends messages \(\hbox {val}(s1)\) to the nodes in cluster \(C_{1}\), then the value is denoted as \(\hbox {val}(s12)\) and stored in vertex \(s12\) of node \(n_{1}\)’s mg-tree in the third round, which is illustrated in Fig. 4d. The \(\hbox {val}({\upalpha }i)\) tells that the message is sent to a series of receivers, denoted as \(\upalpha \), and the nodes in cluster \(C_{i}\) are the latest receivers. For instance, the message \(\hbox {val}(s1{\ldots }4)\), stored in the vertex \(s1{\ldots }4\) of an mg-tree, which implies that the message just received was sent through the source, the nodes in cluster \(C_{1}\), the nodes in cluster \(C_{4}\) (the nodes in cluster \(C_{4}\) is the latest nodes to pass the message). And it is denoted as \(\hbox {val}(\upalpha 4)\). When the message is transmitted through the nodes in cluster more than once, the name of the cluster will be repeated correspondingly. For example, \(\hbox {val}(s11)\), stored in vertex \(s11\) of Fig. 4d, indicates that the message is sent from \(s\) to the nodes in cluster \(C_{1}\), then to the nodes in cluster \(C_{1}\) again.
In summary, the root of an mg-tree is always named \(s\) to denote that the stored message is sent from the source node in the first round, and the vertex of an mg-tree is labeled by a list of cluster names. The cluster name list contains the names of the clusters through which the stored message was transferred.
Appendix 3: The Information-Collecting tree (ic-tree)
An ic-tree is reorganized from a corresponding mg-tree by removing the vertices with repeated cluster names in order to reduce the influence from a faulty node repeatedly in an ic-tree. Figure 4e is an example of reorganizing an mg-tree to an ic-tree by deleting the repeated cluster names of mg-tree.
Rights and permissions
About this article
Cite this article
Wang, SS., Wang, SC. & Yan, KQ. Reaching Trusted Byzantine Agreement in a Cluster-Based Wireless Sensor Network. Wireless Pers Commun 78, 1079–1094 (2014). https://doi.org/10.1007/s11277-014-1802-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11277-014-1802-3