Autonomous fault-diagnosis and decision-making algorithm for determining faulty nodes in distributed wireless networks

Abstract

In this paper, we address fault-diagnosis agreement (FDA) problems in distributed wireless networks (DWNs) with arbitrary fallible nodes and healthy access points. We propose a new algorithm to reach an agreement among fault-free members about the faulty ones. The algorithm is designed for fully connected DWN and can also be easily adapted to partially connected networks. Our contribution is to reduce the bit complexity of the Byzantine agreement process by detecting the same list of faulty units in all fault-free members. Therefore, the malicious units can be removed from other consensus processes. Also, each healthy unit detects a local list of malicious units, which results in lower packet transmissions in the network. Our proposed algorithm solves FDA problems in 2t+1 rounds of packet transmissions, and the bit complexity in each wireless node is O(nt+1).

Keywords

Fault diagnosis / Decision making / Byzantine agreement / Distributed wireless networks / Consensus

References

[1] Alekeish, K., Ezhilchelvan, P., 2012. Consensus in sparse, mobile ad hoc networks. IEEE Trans. Parall. Distrib. Syst., 23(3):467–474. http://dx.doi.org/10.1109/TPDS.2011.182

[2] Ayeb, B., Farhat, A., 2004. A flexible formal framework for masking/demasking faults. Inform. Sci., 159(1-2):29–52. http://dx.doi.org/10.1016/j.ins.2003.03.004

[3] Buskens, R.W., Bianchini, R.P., 1993. Distributed on-line diagnosis in the presence of arbitrary faults. 23rd Int. Symp. on Fault-Tolerant Computing, p.470–479. http://dx.doi.org/10.1109/FTCS.1993.627350

[4] Chiang, M.L., Wang, S.C., Tseng, L.Y., 2009. An early fault diagnosis agreement under hybrid fault model. Expert Syst. Appl., 36(3):5039–5050. http://dx.doi.org/10.1016/j.eswa.2008.06.009

[5] Colon Osorio, F.C., 2007. Using Byzantine agreement in the design of IPS systems. Int. Performance, Computing, and Communications Conf., p.528–537. http://dx.doi.org/10.1109/PCCC.2007.358936

[6] Elhadef, M., Boukerche, A., Elkadiki, H., 2007. An adaptive fault identification protocol for an emergency/rescuebased wireless and mobile ad-hoc network. IEEE Int. Parallel and Distributed Processing Symp., p.1–8. http://dx.doi.org/10.1109/IPDPS.2007.370589

[7] Fischer, M.J., Lynch, N.A., 1982. A lower bound for the assure interactive consistency. Inform. Process. Lett., 14(4):183–186. http://dx.doi.org/10.1016/0020-0190(82)90033-3

[8] Hsiao, H.S., Chin, Y.H., Yang, W.P., 2000. Reaching fault diagnosis agreement under a hybrid fault model. IEEE Trans. Comput., 49(9):980–986. http://dx.doi.org/10.1109/12.869331

[9] Hsieh, H.C., Chiang, M.L., 2013. Robustness improvement for mobile P2P network by the Byzantine Agreement problem. 10th Annual Conf. on Wireless On-demand Network Systems and Services, p.104–106. http://dx.doi.org/10.1109/WONS.2013.6578329

[10] Jiang, J., He, C., 2005. A novel mutual authentication and key agreement protocol based on NTRU cryptography for wireless communications. J. Zhejiang Univ.-Sci., 6A(5): 399–404. http://dx.doi.org/10.1631/jzus.2005.A0399

[11] Khosravi, A., Mohammadi, K., Shiroie, M., 2011. Locating malicious links in fully-connected networks using a formal framework. Proc. Int. Conf. on Systems Engineering, p.247–250. http://dx.doi.org/10.1109/ICSEng.2011.51

[12] Lamport, L., Shostak, R., Pease, M., 1982. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401. http://dx.doi.org/10.1145/357172.357176

[13] Maggs, M.K., O’Keefe, S.G., Thiel, D.V., 2012. Consensus clock synchronization for wireless sensor networks. IEEE Sensors J., 12(6):2269–2277. http://dx.doi.org/10.1109/JSEN.2011.2182045

[14] Okun, M., Barak, A., 2008. Efficient algorithms for anonymous Byzantine agreement. Theory Comput. Syst., 42(2): 222–238. http://dx.doi.org/10.1007/s00224-007-9006-9

[15] Pasqualetti, F., Bicchi, A., Bullo, F., 2012. Consensus computation in unreliable networks: a system theoretic approach. IEEE Trans. Autom. Contr., 57(1):90–104. http://dx.doi.org/10.1109/TAC.2011.2158130

[16] Pease, M., Shostak, R., Lamport, L., 1980. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234. http://dx.doi.org/10.1145/322186.322188

[17] Silvestre, D., Rosa, P., Hespanha, J.P., , 2014. Finite-time average consensus in a Byzantine environment using set-valued observers. American Control Conf., p.3023–3028. http://dx.doi.org/10.1109/ACC.2014.6859426

[18] Wang, S.C., Chin, Y.H., Yan, K.Q., 1990. Reaching a fault detection agreement. Proc. Int. Conf. on Parallel Processing, p.251–258.

[19] Wang, S.C., Chin, Y.H., Yan, K.Q., 1995. Byzantine Agreement in a generalized connected network. IEEE Trans. Parall. Distrib. Syst., 6(4):420–427. http://dx.doi.org/10.1109/71.372796

[20] Wang, S.S., Yan, K.Q., Wang, S.C., 2010. An optimal solution for Byzantine agreement under a hierarchical clusteroriented mobile ad hoc network. Comput. Electr. Eng., 36(1):100–113. http://dx.doi.org/10.1016/j.compeleceng.2009.06.002

[21] Wu, S., Rabbat, M.G., 2013. Broadcast gossip algorithms for consensus on strongly connected digraphs. IEEE Trans. Signal Process., 61(16):3959–3971. http://dx.doi.org/10.1109/TSP.2013.2264056

RIGHTS & PERMISSIONS

2016 Zhejiang University and Springer-Verlag Berlin Heidelberg