LASCNN algorithm: Difference between revisions

Revision as of 14:35, 15 August 2020

Latest revision as of 19:57, 12 October 2024

(37 intermediate revisions by 7 users not shown)

Line 1:

In graph theory, '''LASCNN''' is a Localized'''L'''ocalized Algorithm'''A'''lgorithm for Segregation'''S'''egregation of Critical'''C'''ritical/Non'''N'''on-critical Nodes '''N'''odes<ref>Muhammad Imran, Muhammad, 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-11721167–1172.</ref> The algorithm works on the principle of distinguishing between critical and non-critical nodes for network connectivity based on limited topology information.<ref>Alnuem,N. MohammedJavaid, NazirA. Ahmad Zafar, MuhammadM. Imran, SanaA. Ullah,A. Alhamed and Mahmoud SM. Fayed.Guizani, "FormalBIETX: specificationA new quality link metric for Static Wireless Multi-hop Networks," 2016 International Wireless Communications and validationMobile ofComputing aConference localized(IWCMC), algorithmPaphos, for2016, segregationpp. of784–789, critical{{doi|10.1109/noncriticalIWCMC.2016.7577157}}.</ref> The algorithm finds the critical nodes inwith MAHSNspartial information within a few hops.<ref>Kim, Beom-Su, Kyong Hoon Kim, and Ki-Il Kim. "A Internationalsurvey Journalon ofmobility Distributedsupport Sensorin Networkswireless 10body area networks." Sensors 17, no. 64 (20142017): 140973797.</ref>

This algorithm can distinguish the critical nodes of the network with high precision, indeed, accuracy can reach 100% when identifying non-critical nodes.<ref>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. </ref> The performance of LASCNN is scalable and quite competitive compared to other schemes.<ref>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).</ref>

==Pseudocode==

The LASCNN algorithm establishes a {{Var|k}}-hop neighbor list and a duplicate free pair wise connection list based on {{Var|k}}-hop information. If the neighbors stay connected then the node is non-critical.<ref>G. Sugithaetal., International Journal of Advanced Engineering Technology E-ISSN 0976-3945</ref><ref>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</ref>

<pre>

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

</pre>

==Implementation==

[[File:Critical_Nodes_Application.png|thumb|300px|Critical Nodes Application - An implementation for the LASCNN algorithm using PWCT]]

The Critical Nodes application is a Free Open-Source implementation for the LASCNN algorithm. The application was developed in 2013 using [[PWCT|Programming Without Coding Technology]] software.<ref>Fayed, Al-Qurishi, Alamri, Aldariseh (2017) PWCT: visual language for IoT and cloud computing applications and systems, ACM</ref>

==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==

<references/>

==External links==

* [https://sourceforge.net/projects/criticalnodes/ Critical Nodes application]

[[Category:Networks]]

[[Category:Network theory]]

[[Category:Graph algorithms]]