|
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>Imran, 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-11721167–1172.</ref> The algorithm workedworks on the principle of distinguishing between the critical and non-critical nodes for the network connectivity based on limited topology information .<ref>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-789784–789, {{doi: |10.1109/IWCMC.2016.7577157}}.</ref> The algorithm findfinds the critical nodes with the partial information within a few hops. <ref>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.</ref>
This algorithm can distinguish the critical nodes of the network with high precision, and theindeed, accuracy can reach 90%. The accuracy of this algorithm 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> AlnuemG. 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>
LASCNNFunction LASCNN(MAHSN)
For ∀ A ∈ MAHSN
(1) For∀𝐴∈𝑀𝐴𝐻𝑆𝑁
(2) If (𝐴→𝐶𝑜𝑛𝑛𝐿𝑖𝑠𝑡A->ConnList.getSize() == 1) then
(3) 𝐴→SetNonCritical A->SetNonCritical() = LEAF
(4) Else
(5) Continue = TRUE
(6) While (Continue == TRUE)
(7) Continue = FALSE
For ∀ ActiveConn ∈ ConnList
(8) For∀𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛∈𝐶𝑜𝑛𝑛𝐿𝑖𝑠𝑡
(9) If (𝐴∉𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛A∉ActiveConn) then
(10) If (𝐴→𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠A->ConnNeighbors.getSize() == 0)
(11) 𝐴→𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠 A->ConnNeighbors.add(𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛ActiveConn)
(12) Continue = TRUE
(13) else
(14) If (𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛∩𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠ActiveConn ∩ ConnNeighbors == TRUE)
ActiveConn ∪ ConnNeighbors
(15) 𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛∪𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠
(16) Continue = TRUE
(17) Endif
(18) Endif
(19) Endif
(20) End For
(21) End While
(22) Endif
(23) If (𝐴→𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠A->ConnNeighbors.getSize() <𝐴→𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠 A->Neighbors.getSize())
(24) 𝐴→SetCritical A->SetCritical() = TRUE
(25) else
(26) 𝐴→SetNonCritical A->SetNonCritical() = INTERMEDIATE
(27) Endif
(28) End For
End Function
</pre>
==Implementation==
▲<ref>Alnuem, Mohammed, 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>
[[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)]]
* [[Critical_point_(network_science)|Critical point (network science)]] ▼* [[Dynamic connectivity]]
* [[Strength of a graph]]
* [[Cheeger constant (graph theory)]]
▲* [[ Critical_point_(network_science)|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]]
| 