Center for Integrated Circuits and Devices Research (CIDR) - User contributions [en]

Energy Efficient Machine Learning Hardware Co-design

2023-06-28T10:49:26Z

Alvionne Baquiran: /* Personnel */

This component project of the CIDR program tackles the co-design of energy-efficient machine learning algorithms and hardware. Methodologies to integrate machine learning on-chip for distributed data processing, network lifespan improvement and security will be explored. These methodologies will likewise pave the way for automated hardware generation for the accelerator needed to perform these tasks.

==Personnel==
{| class="wikitable"
| Project Leader || Anastacia B. Alvarez, PhD
|-
| Senior Technical Specialist || Sherry Joy Alvionne S. Baquiran
|-
| rowspan="3" | Technical Specialist || Fredrick Angelo Galapon
|-
| Allen Jason Tan
|-
|Lawrence Roman Quizon
|-
| Administrative Officer || Maria Luz Limun
|-
|Technical Aide
|Patrick Jake Valdez [Y1Q1-Y1Q3]
Andrei Gabriel Ay-ay [Y1-Q4]
|-
| rowspan="3" | Project Staff || Ryan Albert Antonio
|-
| Rhandley D. Cajote, PhD
|-
| John Francis Chan
|-
| rowspan="2" | Student Affiliate || Joenard Matanguihan
|-
| Randolf Tamayo
|}

==Activities==
The project will have four (4) major activities:
#Design and implementation WSN machine learning for [[clustering and routing]]
#ISA-optimization of [[RISC-V processor for machine learning]]
#Design, implementation, and verification of a proof-of-concept [[distributed learning]] in 28nm FDSOI CMOS technology.
#Design and implementation of a proof-of-concept [[security module]] using physically unclonable functions (PUF)
==Resources==
*[[PSHS Internship 2023]]
*Tutorials
*Scripts
*Presentations
*Papers

Security module

2023-06-28T10:35:32Z

Alvionne Baquiran: Added Trends in PUF

==Security Module and Hardware Key Generation==

The pervasiveness and vast number of deployed nodes monitoring the environment makes security a fundamental challenge, especially in IoT applications. Security issues are expected to arise in terms of data authenticity, availability, integrity, and confidentiality<ref>T. Zia and A. Zomaya, "Security Issues in Wireless Sensor Networks," 2006 International Conference on Systems and Networks Communications (ICSNC'06), 2006, pp. 40-40, doi: 10.1109/ICSNC.2006.66.</ref>. Data as well as the sender of this data need to be verified and security must be assured down to the hardware level (i.e., each node needs to be confirmed to be). Security can be inserted in several levels. Chip authentication is necessary when nodes are added onto the network. Data sent between the nodes can also be secured via lightweight encryption. Finally commands for actuation need to be authenticated and verified. All these can be enhanced through machine learning.

Year 1 of this project focuses on the use of physically unclonable functions (PUFs) as unconditionally secure hardware key. The activities for this year are shown in the figure below.
[[File:Sec-year1 activities.png|center|thumb|600x600px|Figure 1. Year 1 Activities for the Security Module.]]

==Physically Unclonable Functions==
In the recent past, Physically Unclonable Functions (PUFs) have emerged as potentially highly secure and lightweight solution to ensure data and hardware security, assuring trustworthiness down to the chip level<ref>R. Maes, V. Rozic, I. Verbauwhede, P. Koeberl, E. van der Sluis, V. can der Leest, "Experimental Evaluation of Physically Unclonable Functions in 65 nm CMOS", in European Solid State Circuit Conference (ESSCIRC), 2012, pp. 486489.</ref>. A PUF is a function that maps an input (digital) challenge to an output (digital) response in a repeatable but unpredictable manner, leveraging on chip-specific random process variations. Machine learning was also proposed to improve authentication with PUF<ref>B. Chatterjee, D. Das, S. Sen, "RF-PUF: IoT Security Enhancement through Authentication of Wireless Nodes using In-situ Machine Learning", IEEE International Symposium on Hardware Oriented Security and Trust (HOST), 2018, pp. 205-208. </ref>.

PUFs have 3 main properties: randomness, uniqueness and reliability<ref>A. Alvarez and M. Alioto, “Security down to the Hardware Level,” in Enabling the Internet of Things - from Circuits to Networks, Springer, 2017.</ref>. Randomness refers to the bias of the generated key, or the ratio between logic 1 and logic 0 bits in the key (ideally, the bias would be 50%). Uniqueness is measured through the inter-PUF hamming distance fraction, or the percentage of PUF bits that are different between keys. Ideally, we would want a hamming distance fraction of 50%. Reliability, on the other hand measures the intra-PUF hamming distance or the bit error rate (BER) over several trials and under process, voltage and temperature (PVT) variations. Ideally, the BER should be 0, signifying no change in bit values despite PVT variations.

The concept of using device mismatches for started in the year 2000 with the IC identification (ICID) <ref>K. Lofstrom, W. R. Daasch, and D. Taylor, “IC Identification Circuit using Device Mismatch,” ISSCC Dig. Tech. Papers, 2000, pp. 372–373.</ref>. Using delay differences due to random mismatch was shown to also give the same function with the arbiter PUF <ref>J. W. Lee, B. Gassend, G. E. Suh, M. van Dijk, and S. Devadas, “A Technique to Build a Secret Key in Integrated Circuits for Identification and Authentication Applications,” IEEE Symp. VLSI Circuits, 2004, pp. 176–179.</ref><ref>D. Lim, J. W. Lee, B. Gassend, G. E. Suh, M. Van Dijk, and S. Devadas, “Extracting Secret Keys from Integrated Circuits,” IEEE Trans. Very Large Scale Integr. Syst., vol. 13, no. 10, pp. 1200–1205, 2005.</ref>. One of the most common delay-based PUFs is the ring oscillator (RO) PUF,<ref>R. Maes, V. Rozic, I. Verbauwhede, P. Koeberl, E. van der Sluis, and V. can der Leest, “Experimental Evaluation of Physically Unclonable Functions in 65 nm CMOS,” in European Solid State Circuit Conference (ESSCIRC), 2012, pp. 486–489.</ref> where the frequencies of a pair of ring oscillators are compared and decide the bit value (e.g. 1 if fB > fA). The power-on sate of memory elements can also be used to generate the hardware key, as demonstrated with the latch PUF<ref>Y. Su, J. Holleman, and B. Otis, “A 1.6pJ/bit 96% Stable Chip-ID Generating Circuit using Process Variations,” ISSCC Dig. Tech. Papers, 2007, pp. 406–408.</ref>, and more recently even for the RRAM crossbar<ref>Y. Pang, B. Gao, D. Wu, S. Yi, Q. Liu, W.-H. Chen, T.-W. Chang, W.-E. Lin, X. Sun, S. Yu, H. Qian, M. F. Chang, H. Wu, "A Reconfigurable RRAM PUF Utilizing Post-Process Randomness Source with <6×10-6 N-BER," 2019 IEEE International Solid-
State Circuits Conference - (ISSCC), San Francisco, CA, USA, 2019, pp. 402-403.</ref>. Leveraging on the memory cell's metastability <ref>S. K. Mathew, S. K. Satpathy, M. A. Anders, H. Kaul, S. K. Hsu, A. Agarwal, G. K. Chen, R. J. Parker, R. K. Krishnamurthy, and V. De, “A 0.19pJ/b PVT-Variation-Tolerant Hybrid Physically Unclonable Function Circuit for 100% Stable Secure Key Generation in 22nm CMOS,” ISSCC Dig. Tech. Papers, pp. 278–280.</ref>. Other types of PUFs have also been explored, such as the VIA PUF<ref>B. D. Choi, T. W. Kim, and D. K. Kim, “Zero bit error rate ID generation circuit using via formation probability in 0.18 µm CMOS process,” IET Journals Mag., vol. 50, no. 12, pp. 876–877, 2014.</ref> and oxide rupture PUF<ref>M.-Y. Wu, T.-H. Yang, L.-C. Chen, C.-C. Lin, H.-C. Hu, F.-Y. Su, C.-M. Wang, J. P.-H. Huang, H.-M. Chen, C. C.-H. Lu, E. C.-S. Yang, R. S.-J. Shen, “A PUF Scheme Using Competing Oxide Rupture with Bit Error RateApproaching Zero,” in IEEE International Solid State Circuits Conference (ISSCC), 2018, pp. 130–132.</ref>, to name a few.

{| class="wikitable" style="width: 70%;"
|-
! PUF Name !! ICID !! Arbiter !! Latch !! RO !! INV_PUF !! VIA !! Oxide !! RRAM
|-
| Type
|| Analog
|| Delay
|| Memory
|| Delay
|| Monostable
|| others
|| others
|| NVM
|-
| Technology (nm)
|| 350
|| 180
|| 130
|| 65
|| 65
|| 180
|| 55
|| 130
|-
| Worst Native Instability at Nominal Condition (%)
|| 1.3
|| 4.82
|| 3.04
|| 2.8
|| 2.34
|| N/A
|| N/A
|| 0.0006
|-
| Nominal Voltage
|| 2.5
|| 1.8
|| 1
|| 1.2
|| 1
|| 1.8
|| 1
|| 5.5
|-
|Maximum Instability under PVT Variation (%)
|5
|4.82
|5.46875
|3.9
|5.72
|<nowiki>--</nowiki>
|<nowiki>--</nowiki>
|0.0006
|-
|Voltage Range (V)
|1.1-5
|1.8+/-2%
|0.9-1.2
|1.2
|0.6-1
|0.01904
|0.0000238
|0.0006
|-
|Temperature Range (C)
|<nowiki>-25-125</nowiki>
|27-70
|N/A
|<nowiki>-40,25,90</nowiki>
|25-85
|1.6-2
|0.8-1.4
|2.5-5.5
|-
|Bit Error Rate (%)
|N/A
|4.82
|5.46875
|N/A
|N/A
|6
|
|
|-
|BER after stability enhancement
|N/A
|N/A
|N/A
|N/A
|N/A
|0.01904
|0.0000238
|0.0006
|-
|Energy per bit (pJ/bit)
|8333.333333
|0.17125
|0.93
|N/A
|0.015
|N/A
|5.2
|3.028
|-
|Area (sq.um)
|23436
|1468944
|9450
|241000
|6000
|1.06E+05
|
|2.86
|-
|Bits
|112
|64
|180
|3840
|3040
|128
|
|8.19E+03
|-
|Area per bit (F2 / bit)
|1708.163265
|708402.7778
|3106.508876
|14854.53649
|6000
|1.05E+06
|218.2
|169.2
|-
|Bias
|N/A
|N/A
|N/A
|N/A
|0.5015625
|N/A
|
|0.5
|-
|Inter-PUF FHD
|0.4910714286
|0.38
|0.50546875
|0.495
|0.5013671875
|N/A
|
|1
|-
|Intra-PUF FHD
|0.013392857
|0.02
|3.04
|0.028
|0.0033636719
|N/A
|0.031
|0.044
|-
|# of possible CRPs
|132
|4.5036E+15
|1
|256
|11
|1
|
|64
|}

== Trends in PUF ==
[[File:Energy and Area PUF Trend.png|thumb|600x600px|Figure 2. Energy and Area Per Bit of Weak PUFs.]]
Looking at PUFs implemented on ASIC, we can see that the majority of the PUFs are still weak PUFs, that is, they have limited challenge-response pairs (CRPs), as opposed to strong PUFs. Some of the trends in terms of area, stability and energy are shown in the figures on the right, and can be found in the PUFdb<ref>M. Alioto, A. Alvarez, "Green IC Physically Unclonable Function database," [Online]. Available: http://www.green-ic.org/pufdb.</ref> and HWsecdb<ref>M. Alioto, “HW security primitives database," [Online]. Available: http://www.green-ic.org/hwsecdb</ref>, which are public databases of PUFs, TRNGs and other hardware security implementations in ASIC.

Figure 2 shows the energy per bit and area per bit of existing implemented PUFs. These two metrics are important for resource-limited systems like WSN. It can be seen in Figure 3a that those with lowest energy to date are monostable PUFs, specifically the Automatic Self Checking and Healing (ASCH)<ref>Yan He et al. “An Automatic Self-Checking and Healing Physically Unclonable Function (PUF) with < 3x10−8 Bit Error Rate”. In: IEEE International Solid-State Circuits Conference. Vol. 64. February. 2021, pp. 506–508. </ref> PUF and sub-threshold inverter<ref>Dai Li and Kaiyuan Yang. “25.1 A 562F2 Physically Unclonable Function with a Zero-Overhead Stabilization Scheme”. In: 2019 IEEE International Solid- State Circuits Conference - (ISSCC). 2019, pp. 400–402.</ref>. In terms of area, the smallest are the memory bitcells, specifically the eDRAM PUF<ref>Sami Rosenblatt et al. “Field Tolerant Dynamic Intrinsic Chip ID Using 32 nm High-K/Metal Gate SOI Embedded DRAM”. In: IEEE Journal of Solid State Circuits (JSSC) 48.4 (2013), pp. 940–947.</ref> and the ReRAM PUF<ref>Y Yoshimoto et al. “A ReRAM-based Physically Unclonable Function with Bit Error Rate ¡ 0.5% after 10 years at 125◦C for 40nm Embedded Application”. In: Symposium on VLSI Technology. 2016, pp. 256–257.</ref>.
[[File:BER Trend in PUF.png|thumb|600x600px|Figure 3. Bit Error Rate of Weak PUFs.]]
One important property of PUFs is the bit error rate (BER), which specifies the percentage of bits that flip after several readings. Figure 3a shows the BER of weak PUFs implemented to date. The PUFs with low native BER are the memory PUFs, specifically the eDRAM PUF<ref>Sami Rosenblatt et al. “Field Tolerant Dynamic Intrinsic Chip ID Using 32 nm High-K/Metal Gate SOI Embedded DRAM”. In: IEEE Journal of Solid State Circuits (JSSC) 48.4 (2013), pp. 940–947.</ref>, with BER in the order of 10−5 and the eMemory<ref>Meng-Yi Wu et al. “A PUF Scheme Using Competing Oxide Rupture with Bit Error Rate Approaching Zero”. In: IEEE International Solid State Circuits Conference (ISSCC). 2018, pp. 130–132.</ref>. These, however, are greatly reduced after applying enhancement techniques such as masking, ECC and majority voting. After stability enhancement, the BER can go an order lower, and the PUF with lowest BER after enhancement is the sense amplifier based PUF<ref>Mudit Bhargava and Ken Mai. “An efficient reliable PUF-based cryptographic key generator in 65nm CMOS”. In: Design, Automation & Test in Europe Conference & Exhibition (DATE). Vol. 1. IEEE Conference Publications, 2014, pp. 1–6.</ref>.

==Curriculum and Manpower Development==
As part of the objective of the CIDR program to continuously improve the curriculum and manpower, the topic on physically unclonable functions was incorporated in the EE 226 (Digital Integrated Circuits) as a possible area of research. The introduction lecture can now be found in youtube<ref>https://youtu.be/JfNnSYuIOkc</ref>.

==References==

File:BER Trend in PUF.png

2023-06-28T10:33:00Z

Alvionne Baquiran:

BER Trend in PUF

File:BER Trends in PUF.png

2023-06-28T10:31:01Z

Alvionne Baquiran:

BER Trends in PUF

File:Energy and Area PUF Trend.png

2023-06-28T10:25:15Z

Alvionne Baquiran:

Energy and Area PUF Trend

Security module

2023-06-28T09:37:42Z

Alvionne Baquiran: Modified year 1 activities

==Security Module and Hardware Key Generation==

The pervasiveness and vast number of deployed nodes monitoring the environment makes security a fundamental challenge, especially in IoT applications. Security issues are expected to arise in terms of data authenticity, availability, integrity, and confidentiality<ref>T. Zia and A. Zomaya, "Security Issues in Wireless Sensor Networks," 2006 International Conference on Systems and Networks Communications (ICSNC'06), 2006, pp. 40-40, doi: 10.1109/ICSNC.2006.66.</ref>. Data as well as the sender of this data need to be verified and security must be assured down to the hardware level (i.e., each node needs to be confirmed to be). Security can be inserted in several levels. Chip authentication is necessary when nodes are added onto the network. Data sent between the nodes can also be secured via lightweight encryption. Finally commands for actuation need to be authenticated and verified. All these can be enhanced through machine learning.

Year 1 of this project focuses on the use of physically unclonable functions (PUFs) as unconditionally secure hardware key. The activities for this year are shown in the figure below.
[[File:Sec-year1 activities.png|center|thumb|600x600px|Figure 1. Year 1 Activities for the Security Module.]]

==Physically Unclonable Functions==
In the recent past, Physically Unclonable Functions (PUFs) have emerged as potentially highly secure and lightweight solution to ensure data and hardware security, assuring trustworthiness down to the chip level<ref>R. Maes, V. Rozic, I. Verbauwhede, P. Koeberl, E. van der Sluis, V. can der Leest, "Experimental Evaluation of Physically Unclonable Functions in 65 nm CMOS", in European Solid State Circuit Conference (ESSCIRC), 2012, pp. 486489.</ref>. A PUF is a function that maps an input (digital) challenge to an output (digital) response in a repeatable but unpredictable manner, leveraging on chip-specific random process variations. Machine learning was also proposed to improve authentication with PUF<ref>B. Chatterjee, D. Das, S. Sen, "RF-PUF: IoT Security Enhancement through Authentication of Wireless Nodes using In-situ Machine Learning", IEEE International Symposium on Hardware Oriented Security and Trust (HOST), 2018, pp. 205-208. </ref>.

PUFs have 3 main properties: randomness, uniqueness and reliability<ref>A. Alvarez and M. Alioto, “Security down to the Hardware Level,” in Enabling the Internet of Things - from Circuits to Networks, Springer, 2017.</ref>. Randomness refers to the bias of the generated key, or the ratio between logic 1 and logic 0 bits in the key (ideally, the bias would be 50%). Uniqueness is measured through the inter-PUF hamming distance fraction, or the percentage of PUF bits that are different between keys. Ideally, we would want a hamming distance fraction of 50%. Reliability, on the other hand measures the intra-PUF hamming distance or the bit error rate (BER) over several trials and under process, voltage and temperature (PVT) variations. Ideally, the BER should be 0, signifying no change in bit values despite PVT variations.

The concept of using device mismatches for started in the year 2000 with the IC identification (ICID) <ref>K. Lofstrom, W. R. Daasch, and D. Taylor, “IC Identification Circuit using Device Mismatch,” ISSCC Dig. Tech. Papers, 2000, pp. 372–373.</ref>. Using delay differences due to random mismatch was shown to also give the same function with the arbiter PUF <ref>J. W. Lee, B. Gassend, G. E. Suh, M. van Dijk, and S. Devadas, “A Technique to Build a Secret Key in Integrated Circuits for Identification and Authentication Applications,” IEEE Symp. VLSI Circuits, 2004, pp. 176–179.</ref><ref>D. Lim, J. W. Lee, B. Gassend, G. E. Suh, M. Van Dijk, and S. Devadas, “Extracting Secret Keys from Integrated Circuits,” IEEE Trans. Very Large Scale Integr. Syst., vol. 13, no. 10, pp. 1200–1205, 2005.</ref>. One of the most common delay-based PUFs is the ring oscillator (RO) PUF,<ref>R. Maes, V. Rozic, I. Verbauwhede, P. Koeberl, E. van der Sluis, and V. can der Leest, “Experimental Evaluation of Physically Unclonable Functions in 65 nm CMOS,” in European Solid State Circuit Conference (ESSCIRC), 2012, pp. 486–489.</ref> where the frequencies of a pair of ring oscillators are compared and decide the bit value (e.g. 1 if fB > fA). The power-on sate of memory elements can also be used to generate the hardware key, as demonstrated with the latch PUF<ref>Y. Su, J. Holleman, and B. Otis, “A 1.6pJ/bit 96% Stable Chip-ID Generating Circuit using Process Variations,” ISSCC Dig. Tech. Papers, 2007, pp. 406–408.</ref>, and more recently even for the RRAM crossbar<ref>Y. Pang, B. Gao, D. Wu, S. Yi, Q. Liu, W.-H. Chen, T.-W. Chang, W.-E. Lin, X. Sun, S. Yu, H. Qian, M. F. Chang, H. Wu, "A Reconfigurable RRAM PUF Utilizing Post-Process Randomness Source with <6×10-6 N-BER," 2019 IEEE International Solid-
State Circuits Conference - (ISSCC), San Francisco, CA, USA, 2019, pp. 402-403.</ref>. Leveraging on the memory cell's metastability <ref>S. K. Mathew, S. K. Satpathy, M. A. Anders, H. Kaul, S. K. Hsu, A. Agarwal, G. K. Chen, R. J. Parker, R. K. Krishnamurthy, and V. De, “A 0.19pJ/b PVT-Variation-Tolerant Hybrid Physically Unclonable Function Circuit for 100% Stable Secure Key Generation in 22nm CMOS,” ISSCC Dig. Tech. Papers, pp. 278–280.</ref>. Other types of PUFs have also been explored, such as the VIA PUF<ref>B. D. Choi, T. W. Kim, and D. K. Kim, “Zero bit error rate ID generation circuit using via formation probability in 0.18 µm CMOS process,” IET Journals Mag., vol. 50, no. 12, pp. 876–877, 2014.</ref> and oxide rupture PUF<ref>M.-Y. Wu, T.-H. Yang, L.-C. Chen, C.-C. Lin, H.-C. Hu, F.-Y. Su, C.-M. Wang, J. P.-H. Huang, H.-M. Chen, C. C.-H. Lu, E. C.-S. Yang, R. S.-J. Shen, “A PUF Scheme Using Competing Oxide Rupture with Bit Error RateApproaching Zero,” in IEEE International Solid State Circuits Conference (ISSCC), 2018, pp. 130–132.</ref>, to name a few.

{| class="wikitable" style="width: 70%;"
|-
! PUF Name !! ICID !! Arbiter !! Latch !! RO !! INV_PUF !! VIA !! Oxide !! RRAM
|-
| Type
|| Analog
|| Delay
|| Memory
|| Delay
|| Monostable
|| others
|| others
|| NVM
|-
| Technology (nm)
|| 350
|| 180
|| 130
|| 65
|| 65
|| 180
|| 55
|| 130
|-
| Worst Native Instability at Nominal Condition (%)
|| 1.3
|| 4.82
|| 3.04
|| 2.8
|| 2.34
|| N/A
|| N/A
|| 0.0006
|-
| Nominal Voltage
|| 2.5
|| 1.8
|| 1
|| 1.2
|| 1
|| 1.8
|| 1
|| 5.5
|-
|Maximum Instability under PVT Variation (%)
|5
|4.82
|5.46875
|3.9
|5.72
|<nowiki>--</nowiki>
|<nowiki>--</nowiki>
|0.0006
|-
|Voltage Range (V)
|1.1-5
|1.8+/-2%
|0.9-1.2
|1.2
|0.6-1
|0.01904
|0.0000238
|0.0006
|-
|Temperature Range (C)
|<nowiki>-25-125</nowiki>
|27-70
|N/A
|<nowiki>-40,25,90</nowiki>
|25-85
|1.6-2
|0.8-1.4
|2.5-5.5
|-
|Bit Error Rate (%)
|N/A
|4.82
|5.46875
|N/A
|N/A
|6
|
|
|-
|BER after stability enhancement
|N/A
|N/A
|N/A
|N/A
|N/A
|0.01904
|0.0000238
|0.0006
|-
|Energy per bit (pJ/bit)
|8333.333333
|0.17125
|0.93
|N/A
|0.015
|N/A
|5.2
|3.028
|-
|Area (sq.um)
|23436
|1468944
|9450
|241000
|6000
|1.06E+05
|
|2.86
|-
|Bits
|112
|64
|180
|3840
|3040
|128
|
|8.19E+03
|-
|Area per bit (F2 / bit)
|1708.163265
|708402.7778
|3106.508876
|14854.53649
|6000
|1.05E+06
|218.2
|169.2
|-
|Bias
|N/A
|N/A
|N/A
|N/A
|0.5015625
|N/A
|
|0.5
|-
|Inter-PUF FHD
|0.4910714286
|0.38
|0.50546875
|0.495
|0.5013671875
|N/A
|
|1
|-
|Intra-PUF FHD
|0.013392857
|0.02
|3.04
|0.028
|0.0033636719
|N/A
|0.031
|0.044
|-
|# of possible CRPs
|132
|4.5036E+15
|1
|256
|11
|1
|
|64
|}

Looking at PUFs implemented on ASIC, we can see that the majority of the PUFs are still weak PUFs, that is, they have limited challenge-response pairs (CRPs), as opposed to strong PUFs. Some of the trends in terms of area, stability and energy is shown in the figure below, and can be found in the PUFdb<ref>M. Alioto, A. Alvarez, "Green IC Physically Unclonable Function database," [Online]. Available: http://www.green-ic.org/pufdb.</ref> and HWsecdb<ref>M. Alioto, “HW security primitives database," [Online]. Available: http://www.green-ic.org/hwsecdb</ref>, which are public databases of PUFs, TRNGs and other hardware security implementations in ASIC.

==Curriculum and Manpower Development==
As part of the objective of the CIDR program to continuously improve the curriculum and manpower, the topic on physically unclonable functions was incorporated in the EE 226 (Digital Integrated Circuits) as a possible area of research. The introduction lecture can now be found in youtube<ref>https://youtu.be/JfNnSYuIOkc</ref>.

==References==

File:Sec-year1 activities.png

2023-06-28T09:35:19Z

Alvionne Baquiran:

Year 1 activities of Security Module

Distributed learning

2023-06-28T09:29:29Z

Alvionne Baquiran: Added Summary of survey and CIDR DLSF

{{DISPLAYTITLE:Distributed Machine Learning}}

The use of artificial intelligence (AI) in extreme edge devices such as wireless sensor nodes (WSNs) will greatly benefit its scalability and application space. AI can be applied to solve problems with clustering, data routing, and most importantly it can be used to reduce the volume of data transmission via data compression or making conclusions from data within the node itself <ref>Alsheikh, Mohammad Abu, et al. "Machine learning in wireless sensor networks: Algorithms, strategies, and applications." ''IEEE Communications Surveys & Tutorials'' 16.4 (2014): 1996-2018.</ref>.

At the moment, potential use cases for ML in WSN include, but are not limited to:

# General Pattern Classification (including recognizing speech commands, voice recognition for authentication, bio-signal processing for medical sensors)
# Image Processing (including presence detection a.k.a. visual wake words, car counting for traffic analytics)
# Node routing and scheduling to improve network scalability and lifespan (through the use of RL, see more in [[Clustering and routing|clustering]]).

However, since devices in the extreme edge are constrained to work with extremely low amounts of energy <ref>Ma, Dong, et al. "Sensing, computing, and communications for energy harvesting iots: A survey." ''IEEE Communications Surveys & Tutorials'' 22.2 (2019): 1222-1250.</ref>, even the simplest AI models are difficult to execute with typical sequential processors. WSNs have memories in the order of kB and clock speeds in the order of kHz to MHz due to energy constraints, rendering them unable to run state-of-the art AI applications.
{| class="wikitable"
|+
!Reference WSN Project
!Device
!CLK
!Memory
!Secondary Memory
!Processor
|-
|ReSE2NSE v1
|Digi XBee-Pro, TI MSP430F213
|16MHz
|512B
|8KB+256B
|16-bit MSP-430
|-
|ReSE2NSE v2
|ATSAMR21
|<48MHz
|32KB
|256KB
|ARM32-Cortex M0
|}
To contrast with the above specs, the TinyML recommended model to classify CIFAR-10 has 3.5MB parameters.

Apart from the above constraints, WSNs running AI are placed in potentially changing environments that are potentially different from the environment in which the AI was trained. This is a problem known as concept drift. AI algorithms running on WSN need to be able to work regardless of continuously changing patterns using concepts such as online learning.

Zhou '21 describes edge AI as using widespread edge resources to gain AI insight. This means not only running an AI algorithm on one node, but potentially cooperatively running inference and training on multiple nodes. There are several degrees to the concept, ranging from training and inference in the server, training in the server but inference in the node, and running both training and inference on the node itself. Ideally, for the highest scalability and lowest communication overhead, training and inference ideally take place in the nodes.

== Distributed Data Processing Survey ==
Running ML in WSN can encounter three problems: resource constraints, concept drift and lack of data for certain applications. From our survey, we found concepts for efficient computer vision that can be applied to most neural-network based ML, and further identified HDC as a good resource-efficient ML algorithm that can be hardware-accelerated. Online learning can be performed with as few resources as possible through the use of efficient libraries and heuristics by training only the most important parts of the model.
[[File:Conceptual Summary of Distributed Learning.png|center|thumb|1000x1000px|Figure 1. Conceptual Summary of Surveyed Algorithms in Distributed Data Processing.]]

=== TinyML and accepted benchmarks for Edge AI ===
The [https://www.tinyml.org/ TinyML organization] describes tinyML as the "field of machine learning technologies and applications including hardware, algorithms and software capable of performing on-device sensor data analytics at extremely low power, typically in the mW range and below, and hence enabling a variety of always-on use-cases and targeting battery operated devices".

MLPerfTiny<ref>Banbury, Colby, et al. "Mlperf tiny benchmark." ''arXiv preprint arXiv:2106.07597'' (2021).

</ref> is widely accepted as the common benchmarking requirement for TinyML works. It prescribes basic accuracy targets along with suggested models (if benchmarking hardware) for 4 selected basic use cases for TinyML as shown in the table below.
{| class="wikitable"
|+
!Use Case
!Dataset
!Suggested Model
!Quality Target
|-
|Visual Wakewords
|MSCOCO
|MobileNetv1
|80% (top-1)
|-
|Keyword Spotting
|Google Speech Commands
|DS-CNN
|90% (top-1)
|-
|Image Classification
|CIFAR-10
|ResNet
|85% (top-1)
|-
|Anomaly Detection
|DCASE2020
|FC-Autoencoder
|85% Area under Curve
|}
Visual Wakewords is a classification task of telling whether or not a person is in a picture. This covers similar tasks where complex high-resolution data is provided but the conclusions required are simple.

Anomaly detection is a similar task, where . This task covers cases where both the conclusions required and the input data are likely to be simple, but stakes are slightly higher where false positives and negatives must be minimized.

=== Efficient Software Models ===

==== State of the Art: Efficient Vision Models ====
Traditional ML techniques struggle most with high-dimension image classification tasks. This is the main task for which heavily parametrized resource-heavy neural networks are used. Additionally, similar architectures are applied to reinforcement learning (such as the one for AlphaZero)<ref>Silver, David, et al. "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play." Science 362.6419 (2018): 1140-1144.</ref>, and so similar efficient architectures are needed for running RL clustering models.

Shown below is a table summarizing the most efficient known vision models.
{| class="wikitable"
|+
!Notes
!Architecture
! colspan="2" |Applied to
!Parameters
!#FLOPs
|-
| rowspan="3" |Residual Blocks & Skip Connections
| rowspan="3" |ResNet-18
|CIFAR-10
|85% (Wan et al.)
| rowspan="3" |11M
| rowspan="3" |1800M
|-
|CIFAR-100
|82.3% (SAMix Augmented Data)
|-
|ImageNet
|72.33%/91.8% (SAMix Augmented Data)
|-
|Linear Bottleneck Blocks
|MobileNetv2
|ImageNet
|72%
|3.5M
|300M
|-
| rowspan="2" |Efficiently Scaled Model Depth & Width
| rowspan="2" |EfficientNetB0
|CIFAR-10
|'''93.52% (Main Paper) (Transfer Learning)'''
| rowspan="2" |5.3M
| rowspan="2" |390M
|-
|ImageNet
|'''77.1%/93.3% (Main Paper)'''
|-
| rowspan="2" |Grouped Pointwise Convolutions
|kEffNet-B0 16ch
|CIFAR-10/100
|92.24%/71.92%
|0.64M
|129M
|-
|kMobileNet Large 16ch
|CIFAR-10/100
|92.74%/71.36%
|'''0.40M'''
|'''81M'''
|-
|Neural Architecture Search
|MCUNetv2M4
|ImageNet
|64.90%
|0.47M
|119M
|-
|Neural Architecture Search
|MCUNetv2H7
|ImageNet
|71.80%
|0.67M
|256M
|}

==== Principles of Efficient Inference ====
Convolutional neural networks (CNNs) are widely used for any task with data that come with spatial relations, such as images or time-based data.

Empirically, deeper networks (with more layers) are known to perform better on more complicated tasks <ref>He, Kaiming, et al. "Deep residual learning for image recognition." ''Proceedings of the IEEE conference on computer vision and pattern recognition''. 2016.</ref>. However, making networks deeper had a limit where training them is no longer possible after a certain depth is reached. Models such as '''ResNet''' with sets of layers that skip connections (known as residual blocks) between layers was introduced to solve this problem allowing for extremely deep networks. <ref>He, Kaiming, et al. "Deep residual learning for image recognition." ''Proceedings of the IEEE conference on computer vision and pattern recognition''. 2016.</ref>

Improving upon that, it was found with '''MobileNetv2''' that models with residual blocks that reduce and then expand the number of channels (known as bottleneck residuals or inverted residuals) allows networks to keep good performance with a much lower parameter count and number of operations.<ref>Sandler, Mark, et al. "Mobilenetv2: Inverted residuals and linear bottlenecks." ''Proceedings of the IEEE conference on computer vision and pattern recognition''. 2018.</ref>

'''EfficientNet''' was developed when researchers attempted to analyze how performance changes in the former networks as you vary parameters of the architecture, like the number of channels or the network depth. They found both ways to improve accuracy by scaling the network up and also ways to improve efficiency by scaling the network down in a way that preserves accuracy.<ref>Tan, Mingxing, and Quoc Le. "Efficientnet: Rethinking model scaling for convolutional neural networks." ''International conference on machine learning''. PMLR, 2019.</ref>

Works this year ('''kEffNet, kMobileNet''') have found that applying old principles like grouped convolutions and pointwise convolutions to the recent efficient networks further reduce the needed parameters and float operations. <ref>Schuler, Joao Paulo Schwarz, et al. "Grouped Pointwise Convolutions Reduce Parameters in Convolutional Neural Networks." ''MENDEL''. Vol. 28. No. 1. 2022.</ref>

Apart from those, NAS is an approach where heuristic algorithms are used to find accurate models with parameter count constraints ('''ProxylessNAS, MCUNet''') by efficiently estimating the probability of high accuracy (on a specific task) from a candidate model before training and optimizing search spaces.<ref>Lin, Ji, et al. "Mcunet: Tiny deep learning on iot devices." ''Advances in Neural Information Processing Systems'' 33 (2020): 11711-11722.</ref><ref>Cai, Han, Ligeng Zhu, and Song Han. "Proxylessnas: Direct neural architecture search on target task and hardware." ''arXiv preprint arXiv:1812.00332'' (2018).</ref>

=== Running efficient software in small hardware ===

==== State of the Art: Models demonstrated in microcontrollers ====
Microcontrollers are devices that can be used for IoT and also as wireless sensors. Works in the TinyML field tend to demonstrate their works on resource-constrained microcontrollers, the best of whom are summarized here.

The table below summarizes the best demonstrations submitted to [https://mlcommons.org/en/inference-tiny-07/ MLCommons: Tiny Inference]. The most efficient work by far is by a digital accelerator, part of the open division, which used custom models (not the prescribed models) and special high level synthesis (HLS) on an FPGA, and is work by CERN. <ref>Borras, Hendrik, et al. "Open-source FPGA-ML codesign for the MLPerf Tiny Benchmark." ''arXiv preprint arXiv:2206.11791'' (2022).</ref>
{| class="wikitable"
|+
| rowspan="2" |'''Application'''
| rowspan="2" |'''Accuracy/AUC/Dist'''
| rowspan="2" |'''Inference Latency'''
| rowspan="2" |'''Energy Per Inference'''
| rowspan="2" |'''Software Stack'''
| colspan="5" |'''Device, Specs'''
|-
|'''Device'''
|'''CLK'''
|'''Memory + Secondary'''
|'''Processor'''
|'''Voltage'''
|-
|VWW
|80%
|151.63ms
|4.03mJ
| rowspan="4" |X-Cube-AI v.7.1.0
| rowspan="4" |Nucleo-U575ZI-Q
| rowspan="4" |160 MHz
| rowspan="4" |768k + 2M
| rowspan="4" |ARM32CM33
| rowspan="4" |1.8V / SMPS
|-
|CF10
|85%
|158.13ms
|4.15mJ
|-
|Speech Commands
|90%
|54.81ms
|1.48mJ
|-
|ToyADMOS Car
|85%
|5.73ms
|0.152mJ
|-
|VWW
|80%
|186ms
|1.721mJ
| rowspan="4" |Silicon Labs Gecko SDK/ TFLite Micro
| rowspan="4" |Silicon Labs xG24-DK2601B
| rowspan="4" |78 MHz
| rowspan="4" |256k + 1.5M
| rowspan="4" |ARM32CM33 w/ FPU + DSP + TrustZone
| rowspan="4" |1.8V
|-
|CF10
|85%
|240ms
|2.248mJ
|-
|Speech Commands
|90%
|63.1ms
|0.611mJ
|-
|ToyADMOS Car
|85%
|5.41ms
|0.045mJ
|-
|'''CF10'''
|'''84.5%'''
|'''1.5ms'''
|'''2.535mJ'''
|FINN
| rowspan="3" |Xilinx PynqZ2
| rowspan="3" |100 MHz / 650 MHz
| rowspan="3" |+ 128M
| rowspan="3" |Dual Core ARM, Cortex-A9 MPCore
|?
|-
|'''Speech Commands'''
|'''82.5%'''
|'''0.033ms'''
|'''0.0537mJ'''
|FINN
|?
|-
|'''ToyADMOS Car'''
|83%
|'''0.019ms'''
|'''0.03mJ'''
|hls4ml
|?
|}
In addition to the above, [https://hanlab.mit.edu/ MIT's Han Lab] has a lot of MLPerfTiny-passing works demonstrated on very small microcontrollers, as tabulated below.
{| class="wikitable"
|+
!
!
!
!
!Accuracy
!Latency
!Software Stack
!Device
!CLK
!Memory + Secondary
!Processor
!Voltage
|-
| rowspan="8" |MCUNet1
| rowspan="8" |MCUNet
| rowspan="4" |INT4
| rowspan="4" |ImageNet
|62
|
| rowspan="11" |TinyEngine
|STM32F412
|100 MHz
|256kB + 1M
|ARM32CM4
|1.7V-3.6V
|-
|63.5
|
|STM32F746
|216 MHz
|320k + 1M
|ARM32CM7
|1.7V-3.6V
|-
|65.9
|
|STM32F765
|216 MHz
|512k + 1M
|ARM32CM7
|1.7V-3.6V
|-
|70.7
|
|STM32H743
|480 MHz
|512k + 1M
|ARM32CM7
|1.7V-3.6V
|-
| rowspan="3" |INT8
| rowspan="3" |VWW
|92
|880ms
| rowspan="4" |STM32F746
| rowspan="4" |216 MHz
| rowspan="4" |320k + 1M
| rowspan="4" |ARM32CM7
| rowspan="4" |1.7V-3.6V
|-
|88.7
|200ms
|-
|87
|100ms
|-
|INT8
|Speech Commands
|96
|1105ms
|-
| rowspan="3" |MCUNet2
| rowspan="3" |MCUNet2
| rowspan="3" |INT8
| rowspan="3" |ImageNet
| rowspan="2" |71.8
| rowspan="2" |
|STM32H743
|480 MHz
|512k + 2M
|ARM32CM7
|1.7V-3.6V
|-
| rowspan="2" |STM32F412
| rowspan="2" |100 MHz
| rowspan="2" |256kB + 1M
| rowspan="2" |ARM32CM4
| rowspan="2" |1.7V-3.6V
|-
|64.9
|
|}

=== Hyperdimensional Computing<ref>Kanerva, P. (2009). Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors. Cognitive Computation, 1(2), 139–159.</ref> ===
Hyperdimensional computing (HDC) is an ML paradigm where sets of data are encoded into a single high-dimensional vector (hypervector or HV). If the HV is encoded properly, HVs of closely related data will be very similar to each other and very different from HVs of unrelated data. This property is taken advantage of for the ML task of clustering or classification. HDC is very efficient not only because of its single-operation classification, but also because it can be reduced into binary precision for which efficient dedicated accelerators can be made.
[[File:Gen Arch of HDC.png|thumb|500x500px|Figure 2. General Architecture of HDC.]]
The general architecture of an HDC is shown in Figure 2. The mapping module assigns or maps a hypervector to each feature of the system. These hypervectors are then manipulated in the encoding module using the bundling and binding operations. During the training phase, the result of the encoding module is stored in the associative memory, where each class or category has a unique class hypervector. During the inference or testing phase, the result of the encoding module is compared with the stored hypervectors in the associative memory. The class with the highest similarity becomes the predicted class of the input.

=== Online learning & Learning with little data ===
For some tasks, the ML model may need to be retrained on the spot on new data to account for changes in the environment or, more realistically, lack of sensor calibration for wireless sensor nodes. This task is known as Online Learning. Training is much more resource intensive than inference, making this task more challenging. This is addressed by using much more efficient ML models such as the ones surveyed leading to much less training parameters needed or by using efficient training software like that of MCUNet’s TinyLearningEngine.

If enough data is available to pretrain a WSN, the technique called '''''transfer learning and classifier tuning''''' <ref>Ji Lin et al. “On-device training under 256kb memory”. In: arXiv preprint arXiv:2206.15472 (2022). </ref>can be used. By pretraining a network on a general but difficult task, then freezing (not training) parameters of the earlier layers while fine-tuning or retraining only the last few layers of the AI model, online learning can be done much faster with data and using fewer resources.

If available data is not enough, the concept of explicit memory from '''''memory augmented neural networks'''''<ref>Geethan Karunaratne et al. “Robust high-dimensional memory-augmented neural networks”. In: Na- ture communications 12.1 (2021), p. 2468.</ref> can be used to store intermediate representations of data which can be compared to representation of new data to quickly learn to classify them.

In some extreme cases, we may desire to use WSNs in tasks for which no available related dataset exists. In this case, the ML algorithm to be used inside the WSN nodes must be trained with data on-the-spot. However, a weak WSN node on its own cannot train a full model. '''''Federated learning'''''<ref>Brendan McMahan et al. “Communication-efficient learning of deep networks from decentralized data”. In: Artificial intelligence and statistics. PMLR. 2017, pp. 1273–1282. </ref> allows a heterogeneous set of computing nodes to collectively train a model using data that is obtained by the nodes themselves. Federated learning works by running similar online learning AI model architectures called the “backbone” in many devices at once, then sending individual devices’ model updates (that is, parameters or gradients thereof) to a central host and then aggregating them. A powerful trained model can be created in the host which can then distribute the better model.

== CIDR Distributed Learning Simulation Framework ==
To introduce uniformity, add reproducibility, and interpretability to the simulations and the simulation code, we designed a simulation framework which we call the CIDR distributed learning (CIDR DL) simulation framework. The framework applies a Python object-oriented frontend to the necessary tools, like Pytorch<ref>PySyft. url: <nowiki>https://github.com/OpenMined/PySyft</nowiki>.</ref> for tensor computations and Flower<ref>Ekdeep Singh Lubana et al. “Orchestra: Unsupervised federated learning via globally consistent clustering”. In: arXiv preprint arXiv:2205.11506 (2022).</ref> for federated learning. Later on, we plan to include quantization and efficient inference compilers like MCUNet off the box.

The current structure, along with the class attributes that are yet to be implemented (TBI), are shown in Figure 3. In the framework, the base object is a distributed processing node (dp_node) which can contain a distributed processing model (dp_model) along with a communications module (comms_module) and a module that handles the federated learning tasks (federated_module). The dp_model class contains all of the objects necessary to run the machine learning hardware. As such, it is the one that uses Pytorch. The comms_module class will later simulate the algorithms for clustering and communication. Structuring it this way will allow us to instantiate multiple distributed processing nodes and simulate the function on the WSN network using a network simulator.
[[File:CIDR DLSF.png|center|thumb|600x600px|Figure 3. CIDR Simulation Framework]]

=== References ===

File:CIDR DLSF.png

2023-06-28T09:26:03Z

Alvionne Baquiran:

CIDR Distributed Learning Simulation Framework

File:Gen Arch of HDC.png

2023-06-28T09:12:41Z

Alvionne Baquiran:

General Architecture of HDC

File:Conceptual Summary of Distributed Learning.png

2023-06-28T08:50:47Z

Alvionne Baquiran:

Conceptual Summary of Distributed Learning

RISC-V processor for machine learning

2023-06-28T07:43:44Z

Alvionne Baquiran: Added vector coprocessor

Incorporating machine learning capabilities in wireless sensor networks (WSNs) will require an increase of computational capabilities of the sensor nodes. However, most WSNs use commercial, off-the-shelf Microcontroller Units (MCUs) that are low cost and have low power consumption but have limited processing capabilities<ref>F. Karray, M. W. Jmal, M. Abid, M. S. BenSaleh, and A. M. Obeid, “A Review on Wireless Sensor Node Architectures,” in 2014 9th International Symposium on Reconfigurable and CommunicationCentric Systems-on-Chip (ReCoSoC), May 2014, pp. 1–8.</ref> or System on Chips (SoCs) with high performance and low power consumption but has fixed configuration.<ref>M. Maxfield, “ASIC, ASSP, SoC, FPGA - What’s the Difference?” EE Times, June 2014, [Online]. Available: <nowiki>https://www.eetimes.com/asic-assp-soc-fpga-whats-the-difference/#</nowiki>.</ref> Due to these constraints, FPGA-based processors are currently being considered due to its rapid prototyping, dynamic reconfiguration, and acceleration of processing. It should be noted, though, that FPGA-based designs have greater power consumption as compared to SoC and MCU implementations. However, recent research shows that increasing computational capabilities at the network edge can shorten packet lengths, reduce sent packets<ref>V. Mihai, C. Dragana, G. Stamatescu, D. Popescu, and L. Ichim, “Wireless Sensor Network Architecture based on Fog Computing,” in 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT), Apr. 2018, pp. 743–747.</ref>, and reduce network usage, thus, significantly lowering the overall energy consumption of the sensor node.<ref>V. Mihai, C. E. Hanganu, G. Stamatescu, and D. Popescu, “WSN and Fog Computing Integration for Intelligent Data Processing,” in 2018 10th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), June 2018, pp. 1–4.</ref>
[[File:RISV Base Processor + Vector Extension.png|thumb|Figure 1. Project will implement an FPGA-based RISC-V Processor with Vector Extension.]]
To provide flexibility in the design of the processor, the RISC-V Instruction Set Architecture (ISA)<ref>[https://riscv.org/technical/specifications/ <nowiki>RISC-V Specifications. [Online] https://riscv.org/technical/specifications/</nowiki>]</ref>, an open-source, royalty-free ISA, offers a simple, modular and stable architecture that is ideal for a wide variety of embedded and IoT applications. RISC-V implementation is composed of a mandatory base ISA called RV32I and a number of ISA extensions that can be added depending on the application that it will be used for. For machine learning applications, RISC-V has a vector extension suitable for parallel computations.

For this project, an FPGA-based RISC-V processor with vector extension will be implemented.

== Baseline Processor Design ==
The design of the baseline processor is based on the paper of M.J. Neri, et al<ref>M. J. Neri, R. I. Ridao, V. E. Baylosis, P. M. Chua, A. J. Tan, “Design and Implementation of a Pipelined RV32IMC Processor with Interrupt Support for Large-Scale Wireless Sensor Networks,” in 2020 IEEE Region 10 Conference (TENCON), November 2020, pp. 806-8011.</ref> from EEEI in the University of the Philippines, Diliman. It is an FPGA-based RISC-V processor with integer multiplication and division extension and compressed instruction extension, thus, an RV32IMC processor. The processor is pipelined with 5 stages as shown in Figure 2.
[[File:Top Level Block Diagram of the RV32IMC Processor..png|border|center|thumb|669x669px|Figure 2. Top Level Block Diagram of the RV32IMC Processor.]]The Instruction Fetch or IF stage contains the Instruction Memory and the Program Counter (PC) blocks. The Instruction Memory block was halfword-addressable so the PC can be incremented by 2 or by 4 whether instructions are compressed or not. It also has Interrupt handling capabilities. This is done by saving the current PC address to the Save PC Register whenever an interrupt is detected.

The Instruction Decode or ID stage includes the Decode and Control Logic block, a Register File (RF) block with 31 general-purpose registers, and a Shift, Sign Extension, and Shuffle block. A Branch Prediction block which uses the concept of bimodal branch prediction and Branch History Table (BHT) is also available.<ref>S. McFarling, “Combining Branch Predictors,” Western Research Laboratory, California, Tech. Rep. TN36, June 1993.</ref> This block also handles control hazards.
[[File:RV32IMC commsProtocol.png|thumb|Figure 3. Protocol Controller Implementation using Memory Mapping]]
In the Execution or EXE stage, all operations, including branch comparison, are handled by the Arithmetic Logic Unit (ALU) and a Divider block with 38-46 cycle latency. It also includes a Store block which formats the data that will be stored in the Data Memory.

The MEM stage contains the Data Memory and the Load block, which formats the obtained data depending on the load instruction used.

Lastly, the Write Back or WB stage uses a single multiplexer to select the data that will be written to the Register File. A Forwarding Unit is also included to solve possible data dependencies between instructions.

The list of instructions that were implemented in this processor, the RV32I base integer, the “M” standard extension and the “C” standard extension instruction sets, are found in The RISC-V Instruction Set Manual.<ref>A. Waterman, K. Asanovic, “The RISC-V Instruction Set Manual,” [Online]. Available: <nowiki>https://github.com/riscv/riscv-isa-manual/releases/download/Ratified-IMAFDQC/riscv-spec-20191213.pdf</nowiki>.</ref>

The RV32IMC processor is also designed with the following communication blocks: an Inter-integrated Circuit (I2C), a Serial Peripheral Interface (SPI), and a Universal Asynchronous Receiver/Transmitter (UART). The protocol controller of these blocks are interfaced to the processor through memory mapping as shown in Figure 3.

== RISC-V Vector Coprocessor ==
The initial RISC-V vector coprocessor design implements a limited integer-only subset of the RISC-V Vector Extension. It supports 128 bit wide vector registers and is configured by default to process 128 bits per cycle for arithmetic instructions and up to 128 bits per cycle for memory read/write operations. With the implementation of forwarding for dependent elements, it is expected to have a speedup of up to 16x working on 8-bit integer workloads, and up to 4x on 32-bit workloads, compared to the baseline processor.

The coprocessor is intended to be integrated into a modified baseline RV32IMC processor as shown in Figure 4. The baseline processor detects vector instructions, and then sends those to the coprocessor for decoding and execution. The coprocessor is then responsible for sending and receiving data with the baseline processor and its internal data memory module, which facilitates transfers of data to and from memory, and between scalar and vector register registers.
[[File:Initial RISCVV.png|center|thumb|600x600px|Figure 4. Top Level Block Diagram of the RISC-V Vector Processor.]]
The vector coprocessor is divided into distinct blocks, with respective functionalities, that work together to execute every instruction that is fed into it. Once an instruction is issued to the vector coprocessor, it is fed into the internal decoder, V-Decoder. It generates control signals and decodes the instruction, such as its type, source and destination registers, and the specific operation to be performed.

The decoded instruction is then passed to the sequencer, which is responsible for dispatching instructions to the corresponding functional unit. Should there be a data hazard, or an unavailable corresponding functional unit, it is placed into the instruction queue until the conflict is resolved.

The functional units perform operations on inputs, which can be read from vector register groups. Scalar registers or immediate values encoded as part of the instruction can also be used as inputs. Once these are complete, the resulting outputs can then be written back into the output vector register group.

Each vector register stores individual elements together in packed data. These can be grouped together in register groups of up to 8 registers, resulting in an effective vector length of up to 1024 bits, based on a vector register width of 128 bits.

The vector coprocessor can transfer data to and from the baseline processor through the Vector Load/Store Unit (VLSU), mainly in the form of load/store operations on the data memory.

====== Sequencer and Scoreboard ======
The sequencer is responsible for both issuing instructions to functional units and accounting for the instructions being executed by the functional units. It also stores the current vector configuration for each instruction saved in its queue, which is also sent to the functional units. The configuration can change at any point after the instruction is dispatched, so applying the same configuration from the Vector CSRs to all ongoing operations will cause unintended behavior to occur.

The scoreboard is used by the sequencer to account for the current status of each functional unit. It also stores the attributes, such as the input and output registers, of the current instruction being executed to enable forwarding. This shortens the period where each instruction spends stalled waiting for its inputs in order to execute.

====== Arithmetic and Logic Unit (ALU) and Multiplier Unit ======
The vector ALU (VALU) handles most arithmetic operations that are supported by the vector coprocessor. It is divided into four lanes that can execute on 32 bits of data per cycle. This is how the ALU as a whole can operate on 128 bits of data at a time. Since each lane is designed to be independent from other lanes, the ALU can be scaled to accommodate more lanes to operate on more data per cycle. The 128 bit capacity was set to match the peak bandwidth of the memory.

To reduce the area occupied by the entire ALU, individual ALUs for wider element widths are reused by operations on narrower element widths. The outputs to these ALUs is truncated to preserve their element widths.

Multiplication operations are performed in a separate Vector Multiplier Unit (VMUL), to accommodate for their more complex nature. The Multiplier Unit also uses the same structure as the ALU. It is internally divided into lanes and, within each lane, multipliers for wider element widths are reused for narrower element widths.

====== Reduction Unit ======
The Reduction Unit is responsible for reduction operations, which work by performing the same binary operation on all vector elements. A binary operation takes two inputs and produces one output, which can be used as an intermediate value for the same operation. Another binary operation can then be performed using another vector element and the intermediate value. Repeating the operation leaves a final output in a single element.

====== Slide Unit ======
The Slide Unit is responsible for all permutation operations, which include moving values to and from vector registers, and vector slides. Vector slide operations move the indexes of all elements within a vector register group and saves the new arrangement as an output. All elements are shifted by the same offset. The contents of each element is not affected, but the location of each element is changed by the instruction.

====== Load/Store Unit ======
The load/store unit allows the coprocessor to access the data memory. When executing unit stride instructions, it can access up to 128 bits of memory per clock cycle, since the elements that are being accessed belong to a contiguous block of memory and require no further processing or packing to be used in a vector operation

=== List of Instructions ===
Only a limited subset of instructions in the RISC-V Vector Extension are implemented by the vector coprocessor to simplify the design and test processes. These instructions are listed in Table 1.
{| class="wikitable"
|+Table 1. '''List of Vector Instructions Implemented by the Vector Coprocessor'''
!Instruction Type
!Instruction
|-
|Configuration Settings
|vsetvli, vsetivli, vsetvl
|-
|Interger Arithmetic
|vadd, vsub, vand, vor, vxor, vsll, vsrl, vsra, vmseq, vmsne, vmslt, vmsle, vmsgt, vmin, vmax, vmerge
|-
|Fixed-point Arithmetic
|vsadd, vssub, vssrl, vssra, vnclip
|-
|Multiplication
|vmul, vmulh, vsmul
|-
|Load/Store
|vle, vse, vlse, vsse
|-
|Reduction
|vredsum, vredmax
|-
|Permutation
|vslideup, vslidedown, vslide1up, vslide1down, vmv
|}

== References ==
<references />

File:Initial RISCVV.png

2023-06-28T07:30:10Z

Alvionne Baquiran:

Initial RISCVV Top Level Block Diagram

File:RV32IMC commsProtocol.png

2023-06-28T07:24:47Z

Alvionne Baquiran:

Protocol Controller Implementation using Memory Mapping

Clustering and routing

2023-06-28T06:27:23Z

Alvionne Baquiran: Added Kaur and System Diagram

[[File:Clustered WSN.png|border|thumb|500x500px|Figure 1. Clustering in Wireless Sensor Networks.]]
Routing protocols in wireless sensor networks (WSNs) are generally classified into three main categories according to network structure: flat, hierarchical, and location-based.<ref>N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: A survey,” IEEE Wireless Communications, vol. 11, pp. 6–28, 12 2004.</ref><ref>N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient routing protocols in wireless sensor networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, pp. 551–591, 2013.</ref> In flat routing protocols, all nodes in the network are typically assigned equal roles, where each node senses the environment and sends the sensed data to a sink or base station. In hierarchical routing protocols, nodes are grouped into clusters. Each cluster has its own cluster head and member nodes, as shown in Figure 1. The member nodes still play the same role of sensing the environment. They forward their sensed data to the respective cluster heads (instead of the base station) for aggregation, and the cluster heads are the ones responsible for transmitting the aggregated data to the base station. In comparison to flat routing protocols, hierarchical routing protocols offer several advantages, including higher energy efficiency, increased scalability, and increased robustness, all of which are advantageous for WSNs.<ref name=":0">Raghavendra V. Kulkarni, Anna Forster, and Ganesh Kumar Venayagamoorthy. “Computational Intelligence in Wireless Sensor Networks: A Survey”. In: IEEE Communications Surveys & Tutorials 13.1 (2011), pp. 68–96. doi: 10.1109/SURV.2011.040310.00002.</ref>

== Computational Intelligence Paradigms ==
Different computational intelligence (CI) paradigms that can be applied in solving clustering and routing in WSNs are shown in Table 1. Among these paradigms, reinforcement learning (RL) is the most appropriate for WSN applications as it has been proven to achieve optimal routing results in WSNs.<ref>Mohammad Abu Alsheikh et al. “Machine Learning in Wireless Sensor Networks: Algorithms, Strategies, and Applications”. In: IEEE Communications Surveys & Tutorials 16.4 (2014), pp. 1996–2018. doi: 10.1109/COMST.2014.2320099.</ref> While it may need some time to learn the optimal routes, it is highly flexible to network topology changes. Moreover, it has low processing requirements, and low-cost or simple implementation. This makes RL suitable for energy-efficient routing at individual nodes, despite having medium memory requirements for keeping track of different possible actions and values. Thus, discussions on routing protocols with computational intelligence were focused on RL-based routing protocols.
{| class="wikitable"
|+Table 1. Different computational intelligence (CI) paradigms for solving clustering and routing in WSNs.<ref>Raghavendra V. Kulkarni, Anna Forster, and Ganesh Kumar Venayagamoorthy. “Computational Intelligence in Wireless Sensor Networks: A Survey”. In: IEEE Communications Surveys & Tutorials 13.1 (2011), pp. 68–96. doi: 10.1109/SURV.2011.040310.00002.</ref>
!CI Paradigms
!Computational Requirements
!Memory Requirements
!Flexibility
!Clustering & Routing
|-
|Neural Network
|medium
|medium
|low
|less appropriate
|-
|Fuzzy Logic
|medium
|medium
|high
|moderately appropriate
|-
|Evolutionary Algorithm
|medium
|high
|low
|less appropriate
|-
|Swarm Intelligence
|low
|medium
|high
|moderately appropriate
|-
|Reinforcement Learning
|low
|medium
|high
|most appropriate
|}
Since routing protocols with intelligence improves network lifetime more than traditional approaches for WSN applications, we decided to implement RL-based protocols, and consider CLIQUE protocol<ref>A. Förster and A. L. Murphy, “CLIQUE: Role-free clustering with Q-learning for wireless sensor networks,” in Proceedings of International Conference on Distributed Computing Systems, 2009, pp. 441–449.</ref> and the Deep Q-Network protocol by Kaur et al<ref>G. Kaur, P. Chanak, and M. Bhattacharya, “Energy-Efficient Intelligent Routing Scheme for IoT-Enabled WSNs,” IEEE Internet of Things Journal, vol. 8, no. 14, pp. 11440–11449, Jul 2021.</ref>. For our baseline protocol, we choose the LEACH protocol<ref>W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660–670, Oct 2002.</ref> as it is one of the pioneering clustering and routing approaches for WSNs.

== LEACH Protocol ==
One of the pioneering clustering and routing approaches for WSNs is the Low Energy Adaptive Clustering Hierarchy (LEACH). One of the pioneering clustering and routing approaches for WSNs is LEACH. In LEACH, the idea is to select the cluster heads by rotation so that the high energy dissipation in communicating with the base station is spread across all sensor nodes in the network.

The operation of the LEACH protocol is broken into multiple rounds, where each round has two phases: set-up phase and steady-state phase. In the set-up phase, cluster heads are selected and clusters are formed. In the steady-state phase, member nodes send their data to the respective cluster heads, and the cluster heads perform data aggregation for transmission to the base station. The duration of the steady-state phase is typically longer than that of the set-up phase in order to minimize the overhead due to cluster formation.

During the set-up phase, each node decides whether or not to become a cluster head (CH) for the current round. This decision is made by the node choosing a random number between 0 and 1. If the number is less than the following threshold, T(n), the node becomes a cluster head:

<math>T(n) = f(n) = \begin{cases} \frac{P}{1-P(r\bmod \frac{1}{P})}, & \text{if }n \in G \\ 0, & \text{otherwise} \end{cases}</math>

where P is the desired percentage of cluster heads, r is the current round, and G is the set of nodes that have not been elected as cluster heads in the last 1/P rounds. Based on the algorithm, this protocol ensures load balancing by preventing a node from being selected as a cluster head for multiple consecutive rounds.

After the cluster heads are determined, each elected cluster head then broadcasts an advertisement message so that the remaining nodes in the network can choose which cluster to join based on the received signal strength of each message. Each node sends a join request message to its chosen cluster head. After which, the cluster head creates a TDMA schedule, and assigns each node in its cluster a time slot to transmit the data.

Once the clusters are formed, the network can now proceed to the steady-state phase for data transmission. After some time spent on the steady-state phase, the network goes back into the set-up phase for another round of cluster formation.

== CLIQUE ==
[[File:Reinforcement_Learning_Model.png|thumb|400x400px|Figure 2. Reinforcement Learning Model Which Involves an Agent Taking Actions in an Environment.]]
CLIQUE is a cluster-based reinforcement learning (RL) algorithm based on Q-learning. Although it is a cluster-based algorithm, CLIQUE is different from traditional clustering approaches, such as LEACH. It removes the cluster head (CH) election process altogether, and thus its overhead in terms of communication and energy consumption. CLIQUE does this by employing reinforcement learning and enabling a node to independently decide whether or not to act as a CH.

A reinforcement learning model, as shown in Figure 2, involves an agent taking actions in an environment so as to maximize the notion of cumulative reward.<ref>R. V. Kulkarni, A. Forster, and G. K. Venayagamoorthy, “Computational intelligence in wireless sensor networks: A survey,” IEEE Communications Surveys and Tutorials, vol. 13, no. 1, pp. 68–96, 2011.</ref> In the context of routing problems in WSNs, the agents are the nodes themselves. When it is scheduled to transmit a packet, a node (selects an action or) chooses one of its neighbors as the next hop, so that the total routing cost (or reward) from the source node to the destination node is minimized. To determine these routing costs, CLIQUE employs the Q-learning algorithm.

Q-learning is a model-free RL algorithm that allows an agent to learn the goodness (or value) of an action in a particular state without requiring a model of the environment (hence, model-free). It does this by using the Bellman optimality equation to compute a value for each state-action pair,

<math>Q(S,A) \leftarrow Q(S,A) + \alpha\Bigl(R + \gamma \underset{a'}{max} Q(S',a') - Q(S,A)\Bigr)</math>

where Q(S,A) is the Q-value for a given state-action pair, R is the immediate reward, <math>\alpha</math> is the learning rate, and <math>\gamma</math> is the discount factor. By applying this equation iteratively, the real Q-values are learned over time. In most RL problems, the action with the highest Q-value for a given state is the best action. In routing, these Q-values are the routing costs, and the neighbor with the best Q-value (or minimum routing cost) is the next hop for an optimal route. These Q-values or routing costs in CLIQUE are calculated based on the following parameters: hop count and battery level of the nodes. The hop count aims to minimize the communication overhead for better energy efficiency, while the battery status ensures that low-powered nodes are avoided in the transmission path.

It is assumed that there are multiple sinks in the network, and that DATA packets generated by nodes should be transmitted to all sinks. It is also assumed that each node in the network knows which cluster it belongs to. Instead of identifying the CHs with an election process, each node makes a simple decision whether or not to act as a CH based on the Q-values. The node with the best Q-value (or lowest routing cost to all sinks) in a cluster is considered the cluster head. As such, it must aggregate all data from the other nodes in its cluster, and route this aggregated data to the sinks. Nodes that are not identified as cluster heads must route this data to another suited neighbor, towards the identified cluster head. By using Q-learning, the Q-values, and hence the cluster heads, are incrementally learned. And so, in CLIQUE, we are solving the intra-cluster routing problem, from a source node to a cluster head. The inter-cluster routing problem, from the cluster head to the sinks, can be solved by using any multi-hop routing approach.

Before learning begins, the Q-values are initialized first. These values may actually be any random values, and Q-learning should be able to converge to the optimal Q-values (or real routing costs). However, to speed up the learning process, we can initialize the Q-values close to the optimal Q-values. In CLIQUE, the Q-value of an action are initialized based on the approximate routing costs as follows:

<math>Q(A_{n_i}) = Q_{hops}(A_{n_i}) * Q_{battery}(A_{n_i})
= \sum_{d \in D} \text{hops}_d^{n_i} * \text{hcm} (\text{bat}_{n_i})</math>

where D is the set of sinks, <math>\text{hops}_d^{n_i}</math> is the number of hops neighbor <math>n_i</math> needs to reach sink d, and hcm is the hop count multiplier. We can see here that the lower the hop count is, the lower the Q-value or routing cost is. In estimating the hop count, it is assumed in CLIQUE that sinks flood the network with DATA_REQUEST packets to indicate their data interest. As this packet propagates in the network, each node knows some routing information to all sinks, including the hop count and battery status. On the other hand, the hcm( ) is a function whose value exponentially increases with decreasing battery levels. Hence, nodes with lower battery levels have higher hcm( ) values, and thus higher Q-values or higher routing costs.

Once the Q-values are initialized, the learning process begins. Here, we use the Bellman optimality equation iteratively to learn the real Q-values. In CLIQUE, since the Q-values are initialized to the approximate routing costs, the learning rate () is set to 1 for faster learning process. The immediate reward (R) is the cost of reaching a neighbor, and is always 1 in the RL model. The discount factor () is also set to 1 to account for future rewards. And since Q-values are routing costs, minimum Q-values are desired. With this, the equation for updating a Q-value is given by:

<math>Q(S,A) \leftarrow 1 + \underset{a'}{min} Q(S',a')</math>

In order to learn these Q-values, neighboring nodes exchange information. To reduce communication costs, these Q-values are piggybacked on normal DATA packets as feedback information, which allows for any downstream node (node that received the DATA packet) to update routing costs or Q-values at its upstream node (node from previous hop that sent the DATA packet) using the Bellman optimality equation. By sending and receiving this feedback information among neighboring nodes, the information is propagated through the network, and the real routing costs are learned over time without the need for a global knowledge of the network.

== Deep Q-Network protocol by Kaur et al. ==
As the number of neighbors (or state-action pairs) increases, the number of Q-values that are needed to be stored in the memory also increases, hence requiring a larger memory. For these routing problems, look-up table (LUT)-based algorithms, such as Q-learning, may no longer be practical. Instead, we train a function approximator, like a neural network, to achieve the same result of mapping each state-action pair to a Q-value. And, since we are now integrating deep learning to solve RL problems, these are typically called deep reinforcement learning algorithms.

Deep Q-network (DQN) is a deep RL algorithm based on Q-learning. Here, we estimate the Q-values by minimizing the loss at each step i given by the following equation using gradient descent:

<math>L_i(w_i) = \Epsilon_{s,a,r,s' \sim D_i} \left [ \Bigl(r + \gamma \underset{a'}{max} Q(s',a';w_i^\text{-}) - Q(s,a;w_i)\Bigr) ^2 \right ]</math>

where <math>L_i(w_i)</math> is the loss function, <math>Q(s,a;w_i)</math> is the approximate Q-value, and <math>r + \gamma max Q</math> is the Q-learning target, which is similar to the standard Q-learning target. However, updating the network (or the parameters of the network) incrementally at each time step using the latest transition (or data) may result in instability, where parameters can diverge.<ref>V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. A. Riedmiller, “Playing Atari with Deep Reinforcement Learning,” ArXiv, vol. abs/1312.5602, 2013.</ref> Instead, we compute the loss and its gradient using a mini-batch of transitions that are randomly sampled from what is called a replay memory, which essentially stores the transitions or data we have seen thus far. This technique, called experience replay, improves data efficiency by allowing a transition to be reused in multiple network updates, and ensures stability by removing correlation on the transition sequence (randomly sampled transitions are less likely to be correlated).

Aside from experience replay, a deep Q-network also uses fixed Q-targets for a more stable network update. It does this by maintaining two different networks, as is shown in the given loss function above (where there are two sets of parameters or weights). One network, also known as the Q-network, is used to predict the approximate Q-value, and is trained based on the loss function. The other network, which is called the target network, is fixed and not updated, and is used to estimate the Q-learning target. In the loss equation, <math>w_i^-</math> denotes that the parameters are not updated. By keeping this network frozen, we ensure that the target Q-values are stable (and thus, stable Q-network update). However, since the target Q-values are predictions after all, the target network is periodically synchronized with the main Q-network.

Kaur’s work utilizes DQN to solve the routing problem in WSNs. Unlike CLIQUE, it solves both the intra-cluster and inter-cluster routing problems. For the intra-cluster routing, the Q-values are optimized based on the following conflicting objectives: maximize the lifetime of the nodes, maximize network throughput, and minimize the communication delay. The inter-clustering routing is also solved using multi-objective deep RL, where we minimize the load on the CH, maximize the network throughput, and minimize the communication delay.
[[File:System Diagram of Clustering and Routing Block.png|thumb|500x500px|Figure 3. System Diagram for Clustering and Routing Block.]]
In this work, the network is heterogeneous, where the CHs, also called as supernodes, have higher energy than the other nodes. This work also proposes an unequal clustering scheme. The CHs near the sink (or base station) will typically consume more energy since they have to collect data from their cluster members, and from the other cluster heads for inter-cluster routing. To solve this problem, clusters near the sink are assigned a lower cluster radius (and thus smaller number of cluster members) than those far from the sink. By combining this clustering scheme and deep Q-network, Kaur’s work is able to outperform other RL-based routing algorithms.

== System Diagram ==
Figure 3 shows how each node is modeled, from input stream to output stream. The Carrier-sense Multiple Access with Collision Avoidance (CSMA-CA) protocol, which is used to avoid collision of packets, is handled by the MAC block. The data stream, which uses the IEEE 802.15.4 packet format, will be processed by the parser block and the corresponding information is sent to the clustering and routing protocol block.

=== References ===

File:System Diagram of Clustering and Routing Block.png

2023-06-28T06:22:11Z

Alvionne Baquiran:

System Diagram of Clustering and Routing Block

Clustering and routing

2023-06-28T05:55:44Z

Alvionne Baquiran: Added CLIQUE Protocol

[[File:Clustered WSN.png|border|thumb|500x500px|Figure 1. Clustering in Wireless Sensor Networks.]]
Routing protocols in wireless sensor networks (WSNs) are generally classified into three main categories according to network structure: flat, hierarchical, and location-based.<ref>N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: A survey,” IEEE Wireless Communications, vol. 11, pp. 6–28, 12 2004.</ref><ref>N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient routing protocols in wireless sensor networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, pp. 551–591, 2013.</ref> In flat routing protocols, all nodes in the network are typically assigned equal roles, where each node senses the environment and sends the sensed data to a sink or base station. In hierarchical routing protocols, nodes are grouped into clusters. Each cluster has its own cluster head and member nodes, as shown in Figure 1. The member nodes still play the same role of sensing the environment. They forward their sensed data to the respective cluster heads (instead of the base station) for aggregation, and the cluster heads are the ones responsible for transmitting the aggregated data to the base station. In comparison to flat routing protocols, hierarchical routing protocols offer several advantages, including higher energy efficiency, increased scalability, and increased robustness, all of which are advantageous for WSNs.<ref name=":0">Raghavendra V. Kulkarni, Anna Forster, and Ganesh Kumar Venayagamoorthy. “Computational Intelligence in Wireless Sensor Networks: A Survey”. In: IEEE Communications Surveys & Tutorials 13.1 (2011), pp. 68–96. doi: 10.1109/SURV.2011.040310.00002.</ref>

== Computational Intelligence Paradigms ==
Different computational intelligence (CI) paradigms that can be applied in solving clustering and routing in WSNs are shown in Table 1. Among these paradigms, reinforcement learning (RL) is the most appropriate for WSN applications as it has been proven to achieve optimal routing results in WSNs.<ref>Mohammad Abu Alsheikh et al. “Machine Learning in Wireless Sensor Networks: Algorithms, Strategies, and Applications”. In: IEEE Communications Surveys & Tutorials 16.4 (2014), pp. 1996–2018. doi: 10.1109/COMST.2014.2320099.</ref> While it may need some time to learn the optimal routes, it is highly flexible to network topology changes. Moreover, it has low processing requirements, and low-cost or simple implementation. This makes RL suitable for energy-efficient routing at individual nodes, despite having medium memory requirements for keeping track of different possible actions and values. Thus, discussions on routing protocols with computational intelligence were focused on RL-based routing protocols.
{| class="wikitable"
|+Table 1. Different computational intelligence (CI) paradigms for solving clustering and routing in WSNs.<ref>Raghavendra V. Kulkarni, Anna Forster, and Ganesh Kumar Venayagamoorthy. “Computational Intelligence in Wireless Sensor Networks: A Survey”. In: IEEE Communications Surveys & Tutorials 13.1 (2011), pp. 68–96. doi: 10.1109/SURV.2011.040310.00002.</ref>
!CI Paradigms
!Computational Requirements
!Memory Requirements
!Flexibility
!Clustering & Routing
|-
|Neural Network
|medium
|medium
|low
|less appropriate
|-
|Fuzzy Logic
|medium
|medium
|high
|moderately appropriate
|-
|Evolutionary Algorithm
|medium
|high
|low
|less appropriate
|-
|Swarm Intelligence
|low
|medium
|high
|moderately appropriate
|-
|Reinforcement Learning
|low
|medium
|high
|most appropriate
|}
Since routing protocols with intelligence improves network lifetime more than traditional approaches for WSN applications, we decided to implement RL-based protocols, and consider CLIQUE protocol<ref>A. Förster and A. L. Murphy, “CLIQUE: Role-free clustering with Q-learning for wireless sensor networks,” in Proceedings of International Conference on Distributed Computing Systems, 2009, pp. 441–449.</ref> and the Deep Q-Network protocol by Kaur et al<ref>G. Kaur, P. Chanak, and M. Bhattacharya, “Energy-Efficient Intelligent Routing Scheme for IoT-Enabled WSNs,” IEEE Internet of Things Journal, vol. 8, no. 14, pp. 11440–11449, Jul 2021.</ref>. For our baseline protocol, we choose the LEACH protocol<ref>W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660–670, Oct 2002.</ref> as it is one of the pioneering clustering and routing approaches for WSNs.

== LEACH Protocol ==
One of the pioneering clustering and routing approaches for WSNs is the Low Energy Adaptive Clustering Hierarchy (LEACH). One of the pioneering clustering and routing approaches for WSNs is LEACH. In LEACH, the idea is to select the cluster heads by rotation so that the high energy dissipation in communicating with the base station is spread across all sensor nodes in the network.

The operation of the LEACH protocol is broken into multiple rounds, where each round has two phases: set-up phase and steady-state phase. In the set-up phase, cluster heads are selected and clusters are formed. In the steady-state phase, member nodes send their data to the respective cluster heads, and the cluster heads perform data aggregation for transmission to the base station. The duration of the steady-state phase is typically longer than that of the set-up phase in order to minimize the overhead due to cluster formation.

During the set-up phase, each node decides whether or not to become a cluster head (CH) for the current round. This decision is made by the node choosing a random number between 0 and 1. If the number is less than the following threshold, T(n), the node becomes a cluster head:

<math>T(n) = f(n) = \begin{cases} \frac{P}{1-P(r\bmod \frac{1}{P})}, & \text{if }n \in G \\ 0, & \text{otherwise} \end{cases}</math>

where P is the desired percentage of cluster heads, r is the current round, and G is the set of nodes that have not been elected as cluster heads in the last 1/P rounds. Based on the algorithm, this protocol ensures load balancing by preventing a node from being selected as a cluster head for multiple consecutive rounds.

After the cluster heads are determined, each elected cluster head then broadcasts an advertisement message so that the remaining nodes in the network can choose which cluster to join based on the received signal strength of each message. Each node sends a join request message to its chosen cluster head. After which, the cluster head creates a TDMA schedule, and assigns each node in its cluster a time slot to transmit the data.

Once the clusters are formed, the network can now proceed to the steady-state phase for data transmission. After some time spent on the steady-state phase, the network goes back into the set-up phase for another round of cluster formation.

== CLIQUE ==
[[File:Reinforcement Learning Model.png|thumb|Figure 2. Reinforcement Learning Model Which Involves an Agent Taking Actions in an Environment.]]
CLIQUE is a cluster-based reinforcement learning (RL) algorithm based on Q-learning. Although it is a cluster-based algorithm, CLIQUE is different from traditional clustering approaches, such as LEACH. It removes the cluster head (CH) election process altogether, and thus its overhead in terms of communication and energy consumption. CLIQUE does this by employing reinforcement learning and enabling a node to independently decide whether or not to act as a CH.

A reinforcement learning model, as shown in Figure 2, involves an agent taking actions in an environment so as to maximize the notion of cumulative reward. In the context of routing problems in WSNs, the agents are the nodes themselves. When it is scheduled to transmit a packet, a node (selects an action or) chooses one of its neighbors as the next hop, so that the total routing cost (or reward) from the source node to the destination node is minimized. To determine these routing costs, CLIQUE employs the Q-learning algorithm.

Q-learning is a model-free RL algorithm that allows an agent to learn the goodness (or value) of an action in a particular state without requiring a model of the environment (hence, model-free). It does this by using the Bellman optimality equation to compute a value for each state-action pair,

<math>Q(S,A) \leftarrow Q(S,A) + \alpha\Bigl(R + \gamma \underset{a'}{max} Q(S',a') - Q(S,A)\Bigr)</math>

where Q(S,A) is the Q-value for a given state-action pair, R is the immediate reward, <math>\alpha</math> is the learning rate, and <math>\gamma</math> is the discount factor. By applying this equation iteratively, the real Q-values are learned over time. In most RL problems, the action with the highest Q-value for a given state is the best action. In routing, these Q-values are the routing costs, and the neighbor with the best Q-value (or minimum routing cost) is the next hop for an optimal route. These Q-values or routing costs in CLIQUE are calculated based on the following parameters: hop count and battery level of the nodes. The hop count aims to minimize the communication overhead for better energy efficiency, while the battery status ensures that low-powered nodes are avoided in the transmission path.

It is assumed that there are multiple sinks in the network, and that DATA packets generated by nodes should be transmitted to all sinks. It is also assumed that each node in the network knows which cluster it belongs to. Instead of identifying the CHs with an election process, each node makes a simple decision whether or not to act as a CH based on the Q-values. The node with the best Q-value (or lowest routing cost to all sinks) in a cluster is considered the cluster head. As such, it must aggregate all data from the other nodes in its cluster, and route this aggregated data to the sinks. Nodes that are not identified as cluster heads must route this data to another suited neighbor, towards the identified cluster head. By using Q-learning, the Q-values, and hence the cluster heads, are incrementally learned. And so, in CLIQUE, we are solving the intra-cluster routing problem, from a source node to a cluster head. The inter-cluster routing problem, from the cluster head to the sinks, can be solved by using any multi-hop routing approach.

Before learning begins, the Q-values are initialized first. These values may actually be any random values, and Q-learning should be able to converge to the optimal Q-values (or real routing costs). However, to speed up the learning process, we can initialize the Q-values close to the optimal Q-values. In CLIQUE, the Q-value of an action are initialized based on the approximate routing costs as follows:

<math>Q(A_{n_i}) = Q_{hops}(A_{n_i}) * Q_{battery}(A_{n_i})
= \sum_{d \in D} \text{hops}_d^{n_i} * \text{hcm} (\text{bat}_{n_i})</math>

where D is the set of sinks, <math>\text{hops}_d^{n_i}</math> is the number of hops neighbor <math>n_i</math> needs to reach sink d, and hcm is the hop count multiplier. We can see here that the lower the hop count is, the lower the Q-value or routing cost is. In estimating the hop count, it is assumed in CLIQUE that sinks flood the network with DATA_REQUEST packets to indicate their data interest. As this packet propagates in the network, each node knows some routing information to all sinks, including the hop count and battery status. On the other hand, the hcm( ) is a function whose value exponentially increases with decreasing battery levels. Hence, nodes with lower battery levels have higher hcm( ) values, and thus higher Q-values or higher routing costs.

Once the Q-values are initialized, the learning process begins. Here, we use the Bellman optimality equation iteratively to learn the real Q-values. In CLIQUE, since the Q-values are initialized to the approximate routing costs, the learning rate () is set to 1 for faster learning process. The immediate reward (R) is the cost of reaching a neighbor, and is always 1 in the RL model. The discount factor () is also set to 1 to account for future rewards. And since Q-values are routing costs, minimum Q-values are desired. With this, the equation for updating a Q-value is given by:

<math>Q(S,A) \leftarrow 1 + \underset{a'}{min} Q(S',a')</math>

In order to learn these Q-values, neighboring nodes exchange information. To reduce communication costs, these Q-values are piggybacked on normal DATA packets as feedback information, which allows for any downstream node (node that received the DATA packet) to update routing costs or Q-values at its upstream node (node from previous hop that sent the DATA packet) using the Bellman optimality equation. By sending and receiving this feedback information among neighboring nodes, the information is propagated through the network, and the real routing costs are learned over time without the need for a global knowledge of the network.

=== References ===

Clustering and routing

2023-06-28T05:27:49Z

Alvionne Baquiran: Added LEACH Protocol

File:Reinforcement Learning Model.png

2023-06-28T05:18:37Z

Alvionne Baquiran:

Reinforcement learning Model

Clustering and routing

2023-06-27T09:02:49Z

Alvionne Baquiran: /* Comparison of Different Cluster-Based Routing Protocols */

RISC-V processor for machine learning

2023-01-18T05:35:34Z

Alvionne Baquiran: Added Reference Title

Clustering and routing

2023-01-18T05:34:30Z

Alvionne Baquiran: Added Reference Title

[[File:Clustered WSN.png|border|thumb|500x500px|Figure 1. Clustering in Wireless Sensor Networks.]]
Routing protocols in wireless sensor networks (WSNs) are generally classified into three main categories according to network structure: flat, hierarchical, and location-based.<ref>N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: A survey,” IEEE Wireless Communications, vol. 11, pp. 6–28, 12 2004.</ref><ref>N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient routing protocols in wireless sensor networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, pp. 551–591, 2013.</ref> In flat routing protocols, all nodes in the network are typically assigned equal roles, where each node senses the environment and sends the sensed data to a sink or base station. In hierarchical routing protocols, nodes are grouped into clusters. Each cluster has its own cluster head and member nodes, as shown in Figure 1. The member nodes still play the same role of sensing the environment. They forward their sensed data to the respective cluster heads (instead of the base station) for aggregation, and the cluster heads are the ones responsible for transmitting the aggregated data to the base station. In comparison to flat routing protocols, hierarchical routing protocols offer several advantages, including higher energy efficiency, increased scalability, and increased robustness, all of which are advantageous for WSNs.<ref name=":0">X. Liu, “A survey on clustering routing protocols in wireless sensor networks,” Sensors, vol. 12, pp. 11113–11153, 8 2012.</ref>

== Comparison of Different Cluster-Based Routing Protocols ==
Different hierarchical or cluster-based routing protocols are discussed below. Each protocol is analyzed based on several performance metrics, such as energy efficiency, scalability, load balancing, and algorithm complexity.

=== Low Energy Adaptive Clustering Hierarchy (LEACH)<ref name=":0" /> ===
In LEACH, the idea is to select the cluster heads by rotation so that the high energy dissipation in communicating with the base station is spread across all sensor nodes in the network. By doing so, LEACH offers a balanced load among the nodes, which can greatly improve the network lifetime. It also has a simple algorithm, making it suitable for hardware implementation with limited resources. However, despite the good performance of the LEACH protocol, it has some drawbacks. This protocol does not consider the residual energy of the nodes in choosing the cluster heads. Nodes with low energy may be chosen as cluster heads and may die prematurely. Hence, this protocol cannot ensure real load balancing for nodes with varying energies. Furthermore, inter-cluster communication is single-hop, wherein the cluster heads directly communicate with the base station, which is not entirely applicable for large-scale networks. Besides, long-range communication entails too much energy consumption.

=== Two-Level LEACH (TL-LEACH)<ref>V. Loscri, G. Morabito, and S. Marano, “A two-levels hierarchy for low-energy adaptive clustering hierarchy (tl-leach),” vol. 3. IEEE, 9 2005, pp. 1809–1813.</ref> ===
TL-LEACH solves the inter-communication problem of LEACH by introducing another level of hierarchy in a cluster and defining two types of cluster heads: primary and secondary cluster heads. In a cluster, there can only be one primary cluster head. A primary cluster head can communicate directly to one or more secondary cluster heads, while a secondary cluster head can communicate directly to one or more member nodes. However, a two-hop inter-cluster routing is still not applicable for large-scale networks.11 Furthermore, TL-LEACH, like LEACH, cannot ensure real load balancing since cluster heads are elected without energy considerations.

=== Threshold-sensitive Energy-Efficient sensor Network (TEEN)<ref>A. Manjeshwar and D. P. Agrawal, “Teen: a routing protocol for enhanced efficiency in wireless sensor networks.” IEEE, 4 2001, pp. 2009–2015.</ref> ===
To reduce communication overhead, TEEN allows member nodes to transmit data only when a specific event occurs, such as when there are sudden changes in the sensed attributes. Hence, TEEN is applicable for time-critical applications or reactive networks. Assuming clusters are already formed, two thresholds are assigned by each cluster head in TEEN for all its member nodes: hard and soft thresholds. Based on the two thresholds, data transmission in TEEN can be controlled, which can lead to a significant energy reduction. However, like LEACH or TL-LEACH, TEEN may consume a lot of energy when there is a small number of levels in the hierarchy of a large-scale network, which requires transmission at far distances. In addition, since member nodes do not send data unless thresholds are met, a member node may die prematurely without the knowledge of the base station.

=== Adaptive Periodic TEEN (APTEEN)<ref name=":0" /> ===
APTEEN solves the problem mentioned above by allowing the member nodes to transmit periodically while still reacting to time-critical events. In APTEEN, member nodes that have not transmitted any data for a predefined duration (since thresholds are not met) will be required to send data. This protocol offers a lot of flexibility by combining both proactive and reactive policies. However, APTEEN is generally less energy-efficient and more complex to implement than TEEN.

=== Power-Efficient Gathering in Sensor Information System (PEGASIS)<ref>S. Lindsey and C. S. Raghavendra, “Pegasis: Power-efficient gathering in sensor information systems,” vol. 3. IEEE, 3 2002, pp. 1125–1130.</ref> ===
Another improvement over LEACH is PEGASIS. In PEGASIS, a chain of nodes is formed, wherein the chain is either assigned by the base station or accomplished by the nodes themselves using a greedy algorithm. The main idea behind PEGASIS is for each node to communicate only with its closest neighbors in the chain, thus transmitting only at short distances. All nodes take turns as the leader so as to distribute the load evenly across the network. Since the energy overhead of dynamic cluster formation is removed in PEGASIS, it was able to outperform LEACH in terms of network lifetime for different network sizes and topologies. Through the chain of data aggregation, the data transmission volume is also reduced. However, one disadvantage of this protocol is the overhead of chain construction, which requires each node to have a global knowledge of the network. As nodes also take turns as the leader, each node in PEGASIS is assumed to be capable of communicating directly with the base station. This is not always the case, especially for large-scale networks.

=== Concentric Clustering Scheme (CCS)<ref>S.-M. Jung, Y.-J. Han, and T.-M. Chung, “The concentric clustering scheme for efficient energy consumption in the pegasis,” vol. 1. IEEE, 2 2007, pp. 260–265.</ref> ===
CCS extends PEGASIS by dividing the network into a number of tracks or levels. In each level, a chain is formed similar to PEGASIS, and a leader or head node is selected. Nodes in each level also take turns as the head node for that level. As the chains in CCS are shorter than in PEGASIS, the communication delay in the network is reduced. Additionally, since only the nodes at the first level can communicate directly with the base station, the transmission distance to the base station is reduced in CCS, which saves a considerable amount of energy. However, in this protocol, levels with fewer nodes will deplete their energy faster, as the number of times a node is selected as head node is higher in these levels. CCS also does not ensure real load balancing because node energy is not considered during the selection of head nodes.

=== Hybrid Energy-Efficient Distributed clustering (HEED)<ref>O. Younis and S. Fahmy, “Heed: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, pp. 366–379, 10 2004.</ref> ===
To ensure load balancing, nodes with higher residual energy are probabilistically selected as cluster heads in HEED. In HEED, the election process goes through several iterations, where each node decides whether to be a cluster head or a member node. If the remaining energy of a node is high, it can elect itself as a cluster head. If its remaining energy is low, or if there is a neighboring node with a low intra-cluster communication cost, the node acts as a member node instead. HEED offers a more balanced load distribution compared to LEACH, which prolongs the network lifetime. However, the election process requires more iterations, which causes noticeable energy dissipation.

=== Distributed Weight-based Energy-efficient Hierarchical Clustering protocol (DWEHC)<ref>P. Ding, J. Holliday, and A. Celik, “Distributed energy-efficient hierarchical clustering for wireless sensor networks,” International Conference on Distributed Computing in Sensor Systems, pp. 322–339, 2005.</ref> ===
DWEHC is an example of a weight-based protocol that has a similar algorithm to HEED. In this protocol, each node calculates its weight based on its residual energy and distance to its neighbors. Nodes with the largest weight among their neighboring nodes are elected as temporary cluster heads. A real cluster head is then elected from the temporary cluster heads if a given percentage of its neighbors elect it as their temporary cluster head. Compared to LEACH and HEED, DWEHC offers a less random algorithm in choosing cluster heads and takes in more metrics to ensure a more balanced cluster distribution. To achieve further energy reduction, multihop intra-cluster communication is also supported in this protocol. However, DWEHC suffers from the iterative-based problem of HEED, which has a relatively high control message overhead compared to other protocols.

=== Energy-Efficient Clustering Algorithm Based on Neighbors (EECABN)<ref>W. Zhou, “Energy efficient clustering algorithm based on neighbors for wireless sensor networks,” Journal of Shanghai University (English Edition), vol. 15, pp. 150–153, 4 2011.</ref> ===
Another weight-based protocol is EECABN. In this centralized clustering protocol, nodes are divided into strong and weak nodes, where strong (or weak) nodes are those with energy higher (or lower) than the average energy of all the nodes in the network. The base station computes a weight for each node, and elects strong nodes with the highest weights as cluster heads. A high weight is given to a node not only if it has a high residual energy but also if its neighboring nodes have low residual energy or are near to it. A higher weight is also given to those nodes with more neighbors. As such, EECABN has been shown to improve the network lifetime, even outperforming LEACH and HEED. However, since EECABN is centralized, it does not scale well. Moreover, as nodes have to communicate with the base station during the cluster formation, energy consumption is increased.

=== Particle Swarm Optimization (PSO)<ref>S. Guru, S. K. Halgamuge, and S. Fernando, “Particle swarm optimisers for cluster formation in wireless sensor networks.” IEEE, 12 2005, pp. 319–324. </ref> ===
The PSO algorithm is inspired by the bird-flock choreography. It has been adopted for a more energy efficient cluster formation. However, there are no comparisons made between the PSO algorithm and the other clustering protocols in terms of energy consumption or network lifetime. Besides, the algorithm is centralized and may suffer from poor scalability.

=== Ant Colony Optimization (ACO)<ref>T. Camilo, C. Carreto, J. S. Silva, and F. Boavida, “An energy-efficient ant-based routing algorithm for wireless sensor networks,” International Workshop on Ant Colony Optimization and Swarm Intelligence, pp. 49–59, 2006.</ref> ===
The ACO algorithm is based on the actual behavior of ants, which communicate with each other by means of chemical pheromone. Employing the idea that ants like to travel along the trails that have the strongest pheromone, ACO algorithms are implemented such that the highest amount of pheromone is found along the optimal path in the network. As such, each node knows the optimal path to send a packet towards a specific destination. Some algorithms take the energy level of a path into account when updating the pheromone trail, which can significantly improve the network lifetime. However, one drawback of using ACO algorithms is the additional traffic overhead due to the ants that move through the network.

'''Table 1. Comparison of Different Cluster-Based Routing Protocols'''
{| class="wikitable"
|'''Protocol'''
|'''Energy Efficiency'''
|'''Scalability'''
|'''Load Balancing'''
|'''Algorithm Complexity'''
|-
|'''LEACH'''
|very low
|very low
|moderate
|low
|-
|'''TL-LEACH'''
|low
|moderate
|bad
|low
|-
|'''TEEN'''
|very high
|low
|good
|high
|-
|'''APTEEN'''
|moderate
|low
|moderate
|very high
|-
|'''PEGASIS'''
|low
|very low
|moderate
|high
|-
|'''CCS'''
|low
|low
|very bad
|moderate
|-
|'''HEED'''
|moderate
|moderate
|moderate
|moderate
|-
|'''DWECH'''
|very high
|moderate
|very good
|moderate
|-
|'''EECS'''
|moderate
|low
|moderate
|very high
|-
|'''PSO'''
|low
|very low
|moderate
|high
|-
|'''ACO'''
|high
|moderate
|good
|high
|}

=== References ===

RISC-V processor for machine learning

2023-01-16T21:48:30Z

Alvionne Baquiran: Added basic details on the RV32IMC baseline processor.

File:Top Level Block Diagram of the RV32IMC Processor..png

2023-01-16T21:44:21Z

Alvionne Baquiran:

Top Level Block Diagram of the RV32IMC Processor.

File:RISV Base Processor + Vector Extension.png

2023-01-16T21:36:22Z

Alvionne Baquiran:

Temporary image of top level block diagram

Clustering and routing

2023-01-16T21:21:56Z

Alvionne Baquiran: Added Comparison of Clustering Algorithms from Q1Y1 report.

[[File:Clustered WSN.png|border|thumb|500x500px|Figure 1. Clustering in Wireless Sensor Networks.]]
Routing protocols in wireless sensor networks (WSNs) are generally classified into three main categories according to network structure: flat, hierarchical, and location-based.<ref>N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: A survey,” IEEE Wireless Communications, vol. 11, pp. 6–28, 12 2004.</ref><ref>N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient routing protocols in wireless sensor networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, pp. 551–591, 2013.</ref> In flat routing protocols, all nodes in the network are typically assigned equal roles, where each node senses the environment and sends the sensed data to a sink or base station. In hierarchical routing protocols, nodes are grouped into clusters. Each cluster has its own cluster head and member nodes, as shown in Figure 1. The member nodes still play the same role of sensing the environment. They forward their sensed data to the respective cluster heads (instead of the base station) for aggregation, and the cluster heads are the ones responsible for transmitting the aggregated data to the base station. In comparison to flat routing protocols, hierarchical routing protocols offer several advantages, including higher energy efficiency, increased scalability, and increased robustness, all of which are advantageous for WSNs.<ref name=":0">X. Liu, “A survey on clustering routing protocols in wireless sensor networks,” Sensors, vol. 12, pp. 11113–11153, 8 2012.</ref>

== Comparison of Different Cluster-Based Routing Protocols ==
Different hierarchical or cluster-based routing protocols are discussed below. Each protocol is analyzed based on several performance metrics, such as energy efficiency, scalability, load balancing, and algorithm complexity.

=== Low Energy Adaptive Clustering Hierarchy (LEACH)<ref name=":0" /> ===
In LEACH, the idea is to select the cluster heads by rotation so that the high energy dissipation in communicating with the base station is spread across all sensor nodes in the network. By doing so, LEACH offers a balanced load among the nodes, which can greatly improve the network lifetime. It also has a simple algorithm, making it suitable for hardware implementation with limited resources. However, despite the good performance of the LEACH protocol, it has some drawbacks. This protocol does not consider the residual energy of the nodes in choosing the cluster heads. Nodes with low energy may be chosen as cluster heads and may die prematurely. Hence, this protocol cannot ensure real load balancing for nodes with varying energies. Furthermore, inter-cluster communication is single-hop, wherein the cluster heads directly communicate with the base station, which is not entirely applicable for large-scale networks. Besides, long-range communication entails too much energy consumption.

=== Two-Level LEACH (TL-LEACH)<ref>V. Loscri, G. Morabito, and S. Marano, “A two-levels hierarchy for low-energy adaptive clustering hierarchy (tl-leach),” vol. 3. IEEE, 9 2005, pp. 1809–1813.</ref> ===
TL-LEACH solves the inter-communication problem of LEACH by introducing another level of hierarchy in a cluster and defining two types of cluster heads: primary and secondary cluster heads. In a cluster, there can only be one primary cluster head. A primary cluster head can communicate directly to one or more secondary cluster heads, while a secondary cluster head can communicate directly to one or more member nodes. However, a two-hop inter-cluster routing is still not applicable for large-scale networks.11 Furthermore, TL-LEACH, like LEACH, cannot ensure real load balancing since cluster heads are elected without energy considerations.

=== Threshold-sensitive Energy-Efficient sensor Network (TEEN)<ref>A. Manjeshwar and D. P. Agrawal, “Teen: a routing protocol for enhanced efficiency in wireless sensor networks.” IEEE, 4 2001, pp. 2009–2015.</ref> ===
To reduce communication overhead, TEEN allows member nodes to transmit data only when a specific event occurs, such as when there are sudden changes in the sensed attributes. Hence, TEEN is applicable for time-critical applications or reactive networks. Assuming clusters are already formed, two thresholds are assigned by each cluster head in TEEN for all its member nodes: hard and soft thresholds. Based on the two thresholds, data transmission in TEEN can be controlled, which can lead to a significant energy reduction. However, like LEACH or TL-LEACH, TEEN may consume a lot of energy when there is a small number of levels in the hierarchy of a large-scale network, which requires transmission at far distances. In addition, since member nodes do not send data unless thresholds are met, a member node may die prematurely without the knowledge of the base station.

=== Adaptive Periodic TEEN (APTEEN)<ref name=":0" /> ===
APTEEN solves the problem mentioned above by allowing the member nodes to transmit periodically while still reacting to time-critical events. In APTEEN, member nodes that have not transmitted any data for a predefined duration (since thresholds are not met) will be required to send data. This protocol offers a lot of flexibility by combining both proactive and reactive policies. However, APTEEN is generally less energy-efficient and more complex to implement than TEEN.

=== Power-Efficient Gathering in Sensor Information System (PEGASIS)<ref>S. Lindsey and C. S. Raghavendra, “Pegasis: Power-efficient gathering in sensor information systems,” vol. 3. IEEE, 3 2002, pp. 1125–1130.</ref> ===
Another improvement over LEACH is PEGASIS. In PEGASIS, a chain of nodes is formed, wherein the chain is either assigned by the base station or accomplished by the nodes themselves using a greedy algorithm. The main idea behind PEGASIS is for each node to communicate only with its closest neighbors in the chain, thus transmitting only at short distances. All nodes take turns as the leader so as to distribute the load evenly across the network. Since the energy overhead of dynamic cluster formation is removed in PEGASIS, it was able to outperform LEACH in terms of network lifetime for different network sizes and topologies. Through the chain of data aggregation, the data transmission volume is also reduced. However, one disadvantage of this protocol is the overhead of chain construction, which requires each node to have a global knowledge of the network. As nodes also take turns as the leader, each node in PEGASIS is assumed to be capable of communicating directly with the base station. This is not always the case, especially for large-scale networks.

=== Concentric Clustering Scheme (CCS)<ref>S.-M. Jung, Y.-J. Han, and T.-M. Chung, “The concentric clustering scheme for efficient energy consumption in the pegasis,” vol. 1. IEEE, 2 2007, pp. 260–265.</ref> ===
CCS extends PEGASIS by dividing the network into a number of tracks or levels. In each level, a chain is formed similar to PEGASIS, and a leader or head node is selected. Nodes in each level also take turns as the head node for that level. As the chains in CCS are shorter than in PEGASIS, the communication delay in the network is reduced. Additionally, since only the nodes at the first level can communicate directly with the base station, the transmission distance to the base station is reduced in CCS, which saves a considerable amount of energy. However, in this protocol, levels with fewer nodes will deplete their energy faster, as the number of times a node is selected as head node is higher in these levels. CCS also does not ensure real load balancing because node energy is not considered during the selection of head nodes.

=== Hybrid Energy-Efficient Distributed clustering (HEED)<ref>O. Younis and S. Fahmy, “Heed: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, pp. 366–379, 10 2004.</ref> ===
To ensure load balancing, nodes with higher residual energy are probabilistically selected as cluster heads in HEED. In HEED, the election process goes through several iterations, where each node decides whether to be a cluster head or a member node. If the remaining energy of a node is high, it can elect itself as a cluster head. If its remaining energy is low, or if there is a neighboring node with a low intra-cluster communication cost, the node acts as a member node instead. HEED offers a more balanced load distribution compared to LEACH, which prolongs the network lifetime. However, the election process requires more iterations, which causes noticeable energy dissipation.

=== Distributed Weight-based Energy-efficient Hierarchical Clustering protocol (DWEHC)<ref>P. Ding, J. Holliday, and A. Celik, “Distributed energy-efficient hierarchical clustering for wireless sensor networks,” International Conference on Distributed Computing in Sensor Systems, pp. 322–339, 2005.</ref> ===
DWEHC is an example of a weight-based protocol that has a similar algorithm to HEED. In this protocol, each node calculates its weight based on its residual energy and distance to its neighbors. Nodes with the largest weight among their neighboring nodes are elected as temporary cluster heads. A real cluster head is then elected from the temporary cluster heads if a given percentage of its neighbors elect it as their temporary cluster head. Compared to LEACH and HEED, DWEHC offers a less random algorithm in choosing cluster heads and takes in more metrics to ensure a more balanced cluster distribution. To achieve further energy reduction, multihop intra-cluster communication is also supported in this protocol. However, DWEHC suffers from the iterative-based problem of HEED, which has a relatively high control message overhead compared to other protocols.

=== Energy-Efficient Clustering Algorithm Based on Neighbors (EECABN)<ref>W. Zhou, “Energy efficient clustering algorithm based on neighbors for wireless sensor networks,” Journal of Shanghai University (English Edition), vol. 15, pp. 150–153, 4 2011.</ref> ===
Another weight-based protocol is EECABN. In this centralized clustering protocol, nodes are divided into strong and weak nodes, where strong (or weak) nodes are those with energy higher (or lower) than the average energy of all the nodes in the network. The base station computes a weight for each node, and elects strong nodes with the highest weights as cluster heads. A high weight is given to a node not only if it has a high residual energy but also if its neighboring nodes have low residual energy or are near to it. A higher weight is also given to those nodes with more neighbors. As such, EECABN has been shown to improve the network lifetime, even outperforming LEACH and HEED. However, since EECABN is centralized, it does not scale well. Moreover, as nodes have to communicate with the base station during the cluster formation, energy consumption is increased.

=== Particle Swarm Optimization (PSO)<ref>S. Guru, S. K. Halgamuge, and S. Fernando, “Particle swarm optimisers for cluster formation in wireless sensor networks.” IEEE, 12 2005, pp. 319–324. </ref> ===
The PSO algorithm is inspired by the bird-flock choreography. It has been adopted for a more energy efficient cluster formation. However, there are no comparisons made between the PSO algorithm and the other clustering protocols in terms of energy consumption or network lifetime. Besides, the algorithm is centralized and may suffer from poor scalability.

=== Ant Colony Optimization (ACO)<ref>T. Camilo, C. Carreto, J. S. Silva, and F. Boavida, “An energy-efficient ant-based routing algorithm for wireless sensor networks,” International Workshop on Ant Colony Optimization and Swarm Intelligence, pp. 49–59, 2006.</ref> ===
The ACO algorithm is based on the actual behavior of ants, which communicate with each other by means of chemical pheromone. Employing the idea that ants like to travel along the trails that have the strongest pheromone, ACO algorithms are implemented such that the highest amount of pheromone is found along the optimal path in the network. As such, each node knows the optimal path to send a packet towards a specific destination. Some algorithms take the energy level of a path into account when updating the pheromone trail, which can significantly improve the network lifetime. However, one drawback of using ACO algorithms is the additional traffic overhead due to the ants that move through the network.

'''Table 1. Comparison of Different Cluster-Based Routing Protocols'''
{| class="wikitable"
|'''Protocol'''
|'''Energy Efficiency'''
|'''Scalability'''
|'''Load Balancing'''
|'''Algorithm Complexity'''
|-
|'''LEACH'''
|very low
|very low
|moderate
|low
|-
|'''TL-LEACH'''
|low
|moderate
|bad
|low
|-
|'''TEEN'''
|very high
|low
|good
|high
|-
|'''APTEEN'''
|moderate
|low
|moderate
|very high
|-
|'''PEGASIS'''
|low
|very low
|moderate
|high
|-
|'''CCS'''
|low
|low
|very bad
|moderate
|-
|'''HEED'''
|moderate
|moderate
|moderate
|moderate
|-
|'''DWECH'''
|very high
|moderate
|very good
|moderate
|-
|'''EECS'''
|moderate
|low
|moderate
|very high
|-
|'''PSO'''
|low
|very low
|moderate
|high
|-
|'''ACO'''
|high
|moderate
|good
|high
|}

File:Clustered WSN.png

2023-01-16T20:54:33Z

Alvionne Baquiran:

An image describing a WSN with nodes grouped in clusters.