LASCNN algorithm explained

In graph theory, LASCNN is a Localized Algorithm for Segregation of Critical/Non-critical Nodes^[1] The algorithm works on the principle of distinguishing between critical and non-critical nodes for network connectivity based on limited topology information.^[2] The algorithm finds the critical nodes with partial information within a few hops.^[3]

This algorithm can distinguish the critical nodes of the network with high precision, indeed, accuracy can reach 100% when identifying non-critical nodes.^[4] The performance of LASCNN is scalable and quite competitive compared to other schemes.^[5]

Pseudocode

The LASCNN algorithm establishes a -hop neighbor list and a duplicate free pair wise connection list based on -hop information. If the neighbors stay connected then the node is non-critical.^{[6] [7]}

Function LASCNN(MAHSN)
    For ∀ A ∈ MAHSN
        If (A->ConnList.getSize == 1) then
            A->SetNonCritical = LEAF
        Else
            Continue = TRUE
            While (Continue == TRUE)
                Continue = FALSE
                For ∀ ActiveConn ∈ ConnList
                    If (A∉ActiveConn) then
                        If (A->ConnNeighbors.getSize == 0)
                            A->ConnNeighbors.add(ActiveConn)
                            Continue = TRUE
                        else
                            If (ActiveConn ∩ ConnNeighbors == TRUE)
                                ActiveConn ∪ ConnNeighbors
                                Continue = TRUE
                            Endif
                        Endif
                    Endif
                End For
            End While
        Endif
        If (A->ConnNeighbors.getSize < A->Neighbors.getSize)
            A->SetCritical = TRUE
        else
            A->SetNonCritical = INTERMEDIATE
        Endif
    End For
End Function

Implementation

The Critical Nodes application is a Free Open-Source implementation for the LASCNN algorithm. The application was developed in 2013 using Programming Without Coding Technology software.^[8]

See also

• Connectivity (graph theory)
• Dynamic connectivity
• Strength of a graph
• Cheeger constant (graph theory)
• Critical point (network science)
• Depth-first search
• Breadth-first search

References

1. Muhammad Imran, Mohamed A. Alnuem, Mahmoud S. Fayed, and Atif Alamri. "Localized algorithm for segregation of critical/non-critical nodes in mobile ad hoc and sensor networks." Procedia Computer Science 19 (2013): 1167–1172.
2. N. Javaid, A. Ahmad, M. Imran, A. A. Alhamed and M. Guizani, "BIETX: A new quality link metric for Static Wireless Multi-hop Networks," 2016 International Wireless Communications and Mobile Computing Conference (IWCMC), Paphos, 2016, pp. 784–789, .
3. Kim, Beom-Su, Kyong Hoon Kim, and Ki-Il Kim. "A survey on mobility support in wireless body area networks." Sensors 17, no. 4 (2017): 797.
4. Zhang, Y.; Zhang, Z.; Zhang, B. A Novel Hybrid Optimization Scheme on Connectivity Restoration Processes for Large Scale Industrial Wireless Sensor and Actuator Networks. Processes 2019, 7, 939.
5. Kasali, F. A., Y. A. Adekunle, A. A. Izang, O. Ebiesuwa, and O. Otusile. "Evaluation of Formal Method Usage amongst Babcock University Students in Nigeria." Evaluation 5, no. 1 (2016).
6. G. Sugithaetal., International Journal of Advanced Engineering Technology E-ISSN 0976-3945
7. Mohammed Alnuem, Nazir Ahmad Zafar, Muhammad Imran, Sana Ullah, and Mahmoud S. Fayed. "Formal specification and validation of a localized algorithm for segregation of critical/noncritical nodes in MAHSNs." International Journal of Distributed Sensor Networks 10, no. 6 (2014): 140973
8. Fayed, Al-Qurishi, Alamri, Aldariseh (2017) PWCT: visual language for IoT and cloud computing applications and systems, ACM

External links

• Critical Nodes application