# Hierarchical Protocol Based on Recursive Clusters for Smart Parking Applications Using Internet of Things (IOT)

Authors: Adil Hilmani; Abderrahim Maizate; Larbi Hassouni
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

With the increasing number of vehicles, the management of parking spaces in cities is becoming increasingly important in improving the quality of life and combating air pollution. Indeed, finding a parking space at peak times and in congested areas of the population becomes a huge challenge for drivers. To remedy this problem, most modern cities have smart parking. The equipment of these smart parking is mainly based on the implementation of wireless sensor networks (WSN) to monitor, track, and collect real-time information on the occupancy status of each parking space. This information is then made available to drivers who are looking for an available parking space. However, sensor nodes have limitations in terms of energy and communication that affect the performance and quality of the wireless sensor network. Therefore, the design of a self-organization protocol for WSN that minimizes power consumption and maximizes the longevity of the WSN network must be taken into account when implementing and developing a sustainable and viable intelligent parking system. In this paper, we propose a protocol for self-organization of wireless sensor networks (WSN) for the management of parking spaces in outdoor and urban car parks. This protocol is based on building clusters using ZigBee transmission technology for multihop communication. Each sensor node will be installed in the ground of each parking space to monitor its availability by sending the empty or busy state of that space to the gateway using cluster head nodes (CHs). This approach has a robust and efficient self-organizing algorithm that minimizes energy dissipation and increases the lifetime of sensor nodes and the WSN network. The simulation results show that parking management systems in outdoor and urban car parks using the self-organization protocol presented are efficient and sustainable in terms of energy consumption, reliability of data transmission, and the longevity of the WSN network compared to other existing parking systems that use different self-organizing protocols for wireless sensor networks.


---

## Body

## 1. Introduction

In recent years, many cities around the world are suffering from serious development problems because of urbanization and industrialization. One of the most serious problems is congestion of traffic and traffic due to the mismanagement of parking spaces especially in the most visited areas of the city by the motorists like the offices, the center of the city, and the institutions. Today, with the increase in the number of cars in cities, the search for a free parking space has become an impossible and tedious mission, as well as a source of driver frustration, traffic congestion, and pollution more serious in the city. To overcome this problem, several parking management systems have been developed for the management and monitoring of parking spaces using smart car parks. These systems rely on the deployment of wireless sensor networks (WSN) in order to minimize the difficulty of finding free places in different areas of the city [1–6]. Wireless sensor networks (WSN) consist of many small, low-cost sensor nodes that have wireless processing, sensing, and communication capabilities. However, these nodes have limited capabilities, such as reduced memory, limited power, and low processing and communication capacity [7, 8]. Wireless communication is a critical factor for nodes, as it often consumes more energy. As a result, the WSN begins to run out as the node battery begins to deplete, affecting the performances, quality, and lifespan of the WSN. One of the most popular techniques for balancing power consumption in nodes and extending the life of the WSN is clustering [9, 10]. During direct transmission, each sensor communicates its data directly to the gateway, which can be at a long distance. This results in a rapid loss of energy due to the long distance to travel, as well as congestion and collisions requiring the transmission of a signal. The clustering mechanism avoids these problems by allowing nodes in a cluster to send their data over shorter distances to their respective cluster head (CH). These aggregate the detected data from the nodes that form the cluster with the corresponding CH and transmit directly to the gateway or by using multihop communication with other CHs closest to the gateway. In clusters, the CH is the node that consumes more power compared to other nodes in the cluster, but this load can be lightened by selecting a few nodes as CH and alternating this role between members of the cluster. As a result, clustering results in a significant reduction in network power consumption that extends lifespan of the nodes and also increases the longevity of the WSN.To implement this clustering mechanism, we propose in this paper a protocol based on a recursive and autonomous algorithm for dividing the network into clusters. This protocol balances the power consumption between the various nodes of the network that extends the life of the WSN to obtain a viable and robust intelligent parking system. This is a self-organizing protocol for WSN that allows the management of parking spaces in outdoor smart car parks in a reliable and efficient manner. In the first round, the gateway collects the position of all the nodes of the WSN network in a recursive manner using progressive localization levels. Thus, the energy of the nodes is saved, knowing that their maximum distance of wireless communication varies between 100 m and 200 m. In this first step, clusters are formed and CHs are selected in each location level. During the next rounds, the selection of the CH in each cluster is done in an autonomous way without communicating with the gateway. The new CH of a cluster will be elected according to its residual energy and the communication distance with the higher level of location. This proposed algorithm solves the problem of unnecessary transmissions for the selection of CHs that consumes a lot of energy and also ensures the balance of energy between the different nodes of all clusters since the first round.The rest of this paper is organized as follows. The related works are introduced in Section2. In Section 3, we describe the WSN system and communication models. The proposed self-organization protocol is presented in Section 4. Section 5 presents the performance evaluation in terms of energy consumption, lifetime of the WSN network, etc. Finally, Section 6 ends with the conclusion.


## 2. Related Work

Many efforts have been made to design a self-organization protocol for wireless sensor networks (WSN) for managing parking spaces in outdoor smart parkings in the city, in order to extend the lifetime of the sensor nodes and to minimize the energy consumption of WSN. This paper presents a parking system which is based on the management and monitoring of parking spaces using a parking guidance system based on the deployment of the wireless sensor network [11]. The transmission of data to the base station is based on the use of an improved self-organization protocol using certain Hybrid Energy-Efficient Distributed Clustering- (HEED-) distributed protocol functionalities [12, 13]. This protocol (Alg1) allows the nodes of the network to form a cluster topology. Each cluster head (CH) is periodically selected based on its residual energy and its proximity to its neighbors in order to transmit all data from its cluster to the base station via a single hop. This algorithm creates a load imbalance between certain sensor nodes, especially for CHs that are far from the base station, because the communication of a single hop to the base station consumes a lot of energy, which causes the rapid exhaustion of these nodes and network. The author of this paper proposes a linear intelligent parking system using the deployment of the wireless sensor network based on hierarchical clustering [14]. This system uses a self-organization protocol (Alg2) that uses fixed clusters whose cluster members are invariable (Figure 1)Figure 1
Cluster topology in a linear parking.Every CH waits the reception of advertising messages from these member nodes to aggregate and transmit all received information to the sink node of a single hop that will route all received packets to the parking management center. All cluster nodes send a broadcast message to determine the node with the highest remaining energy, to be elected as much as an CH for the next round [15]. This system uses a self-organization protocol with single-hop communication between cluster members and the CH that causes a tremendous amount of power consumption when transmitting data knowing that has neighbouring nodes that can function as intermediate nodes to return the received data to the corresponding CH. The CH selection process used will quickly exhaust the sensor nodes far from the sink node, which will negatively affect the lifetime of these nodes and also the longevity of the entire network.In this article, the author presents a hybrid self-organization protocol for the management of linear parking’s using two modes of communications in the wireless sensor network: a single hop and multihop [16]. This hybrid protocol (Alg3) creates a tree topology between the different nodes installed in each parking space in order to send the states of occupation to the base station. Before sending the states of the parking spaces, each node detects the existence of the base station in its coverage area to transmit this data as a single hop; otherwise, it looks for an intermediate neighbor node to route the information to the base station using multihop communication. The selection of the intermediate neighbor node is based on the calculation of the energy consumed during transmission of data by the transmitter node to the base station using the intermediate node. This method allows the remote nodes of the base station to choose intermediate nodes that are in their coverage areas and that are closer to the base station. This algorithm misses a process of reconstruction of the topology in the case of failure or exhaustion of a node in order to ensure the reliability of reception of the data. In addition, the process of creating the tree topology consumes a great deal of energy which will cause rapid depletion of the nodes and the entire WSN network.This work presents a system for tracking parking spaces in linear outdoor car parks using the implementation of wireless sensor networks based on multihop communication [17]. This system proposes a BIWSLP (bidirectional wireless sensor line protocol) [18] linear self-organization protocol which makes it possible to form a chain topology between the different sensor nodes fixed in the ground of each parking space. Each sensor node detects the availability of the associated parking space and sends the empty or busy state to the sink node via intermediate sensor nodes existing between the source sensor node and the sink node. With this algorithm (Alg4), each node must have a single parent node that allows it to transmit the state of occupancy of the associated parking place to the sink node by creating a chain topology between the different nodes and the sink node. The chain structure adopted by this protocol makes it possible to create delays of reception of the data by the sink node which influences the quality and the stability of the system. In addition, this algorithm forces the nodes to be active all the time whatever their states for the aggregation and the data transmission which will cause the increase in energy consumption and the rapid exhaustion of the nodes [3] presents a new intelligent parking system which is based on the implementation of the network of wireless sensors in the parking spaces in order to collect their availability states to be operated by a guidance system which makes it easier for drivers to find a vacant space. This intelligent parking uses a self-organization protocol (Alg5) which creates a nonautonomous tree-type topology between the different nodes, where each monitoring node communicates via a single hop with the closest routing node which in turn communicates with the sink node via intermediate routing nodes to transmit the state of occupancy of each parking space to the parking management center. The tree structure formed by this algorithm, which uses routing nodes installed in strategic areas to perform the data routing role, creates an imbalance in the power consumption between the different monitoring nodes, especially for the nodes that are farthest from the routing nodes, and also, it decreases the quality of data delivery to the sink node when one of the routing nodes becomes failing or exhausting in the energyIn this paper, a new parking monitoring system is proposed using the deployment of a wireless sensor network that includes detection nodes, a sink node, and a gateway [19]. The detection nodes are installed in the center of each parking space in order to transmit the availability states to the parking management server. This system is based on the implementation of a self-organization protocol (Alg6) which creates a star topology allowing all the detection nodes to send their data to the sink node via a single hop. This algorithm is not adequate for the management of linear parkings and for large parkings because it will create a load imbalance between the different detection nodes during the communication of a single jump to the sink node, by quickly exhausting the furthest nodes, which will affect negatively on the quality of communication and on the reliability of the systemThe author proposes a new approach (Alg7) for the monitoring and management of parking spaces that uses the wireless sensor networks installed in the car park to communicate the availability of these spaces in the center of parking management using ZigBee wireless communication [20]. This algorithm divides the parking into several zones, and in each zone, there is a fixed router node which routes the occupancy statuses of the parking spaces of its zone to the coordinator node via the other router nodes by creating a tree-cluster topology between the different sensor nodes of the network. This algorithm will cause the rapid exhaustion of the router nodes in the network which will lead to the creation of dark areas for certain terminal nodes far from their associated router node, which they will not be able to communicate with it and which will cause degradation of the quality and feasibility of this type of parking.A new system (Alg8) for monitoring, navigation, and reservation in linear parkings is presented in this article which is based on the installation of the sensor nodes in each parking space by creating a cluster network topology that allows to send the availability of these places to the parking management server [21]. Each sensor node sends the empty or busy state of the space to the nearest repeater node to transmit it to the management server via a gateway, in order to be exploited by a mobile application for the purpose of facilitating the task to the drivers during the consultation, navigation, and the reservation of a free parking space in this car park. The direct communication between the different repeater nodes and the gateway creates enormous energy consumption especially for the repeater nodes furthest from the gateway, which negatively affects the stability and lifetime of the WSN (Figure 2).Figure 2
The architecture of the proposed system.All the intelligent parking systems studied use self-organization protocols allowing the creation of different topologies in the WSN network (clusters, tree, and chain). These protocols execute algorithms to collect data from the sensors and transmit it to the well. These algorithms have a negative impact on the deployment of the WSN network which results in the premature death of certain sensor nodes by causing a load imbalance and also a reduction in the lifetime of the nodes and the network. For this reason, we will propose a self-organization protocol based on an efficient and reliable algorithm which will solve all these problems allowing to balance the energy consumption between the different nodes of the network and which will prolong the longevity of the WSN in order to obtain a viable and sustainable intelligent parking system.


## 3. System Overview

### 3.1. Sensor Types

For the monitoring of parking spaces, several outdoor parking management systems use different types of sensors between them: magnetic sensors, ultrasonic sensors, light sensors, etc. But most outdoor systems use magnetic sensors installed in each parking space to accurately detect the state of occupation (busy or empty) by measuring the magnetic field generated by the presence of a car knowing that it contains more than 100 magnetic parts [22–24]. Table 1 shows a comparison made between the 3 types of most used sensors.Table 1
Comparison between the different types of most used sensors.
Magnetic sensorLight sensorUltrasonic sensorAdvantages(i) Low cost (20-120 €)(ii) Range greater(iii) Reacts to north pole and south pole(iv) Insensible to vibrations(v) Best detection of cars(i) Average cost (60-300 €)(ii) Large range (1 m)(iii) Insensible to vibrations and no wear(iv) Detects any type of room with reflective power (direct reflection mode)(i) Large range (15 m)(ii) Detect without contact any object whatever the material(iii) Adjustable sensitivityLimitations(i) Average range (<300 mm)(ii) Requires the use of a magnet(iii) Sensitive to electromagnetic disturbances(i) Supports badly the harsh environments(ii) Sensitive to the appearance of parts (material, surface condition, color, gloss, impact ...)(i) High cost (200-1000 €)(ii) Sensitive to drafts(iii) Sensitive to temperature


### 3.2. Wireless Communication Technologies

The wireless communication in the outdoor car parks is affected by various factors among them: the obstacles created by cars, noise, interferences, etc. It is therefore necessary that the WSN sensor network operates reliably and efficiently during wireless communication in outdoor parkings despite possible environmental variations. The most common wireless communication technologies used for sensor networks are Bluetooth, Wi-Fi, and ZigBee.The deployment of the WSN sensor network in urban outdoor parkings forces the sensor nodes to be installed in the ground whose signal propagation is obstructed by cars and is also affected by their noise. For this type of application, many previous works have shown that conventional wireless standards such as Bluetooth or Wi-Fi are not suitable for this type of network in terms of quality and performance compared to the ZigBee standard in terms of quality and performance based on some parameters like BER (bit error rate) and SNR [25–27]. The following figure demonstrates the performance of ZigBee compared to other types of technologies (Figure 3).Figure 3
ZigBee 802.15.4 performance based on SNR.Concretely, bluetooth technology supports a very short range and a relatively low bandwidth, but it brings better rates of 1 Mbps with a higher energy consumption. Bluetooth is more adapted to the communications’ voice (auricles) or the connections from equipment to a PC or portable devices.Wi-Fi is a standardized technology with the IEEE 802.11x standard (x: a, b, c, g, n), managed by its certification process and provided by Wi-Fi alliance; it operates at 2.4 GHz, 5 GHz, and 60 GHz with a bandwidth of 0.3, 0.6, or 2 MHz. 802.11b-defined Wi-Fi networks have a maximum data transfer rate of 11 Mbps, while the a and c versions have a maximum data transfer rate of 54 Mbps. In terms of power consumption, these versions of the Wi-Fi network consume a lot of energy during wireless communication and they require a good battery backup if you want to use them for more than 10 hours. For this reason, a new IEEE 802.11ah Wi-Fi standard has been created, which supports a large number of heterogeneous devices in the Internet of Things (IoT). It offers attractive features such as improved scalability, low power consumption, and extended coverage over traditional Wi-Fi standards. However, this standard has not been recognized as energy efficient standard with 63 mJ/Packet compared to ZigBee technology with 17 mJ/Packet in a network with 100 nodes [28].ZigBee technology is created by the ZigBee Alliance and the IEEE under the IEEE 802.15.4 standard. It operates in global RF (2.4 GHz global, 915 MHz America, or 868 MHz Europe) whose data rate is 250 kbps at 2.4 GHz, 40 kbps at 915 MHz, and 20 kbps at 868 MHz. This standard provides low cost, low data rate, and low power connectivity for equipment that requires a battery life of several months to several years.Table2 shows the benefits and limitations of ZigBee over other wireless networks [29].Table 2
Comparison between different wireless communication technologies.
Wireless parameterBluetoothIEEE 802.11bIEEE 802.11ahZigbeeFrequency band2.4GHz2.4GHzSub-1 GHz2.4GHzRange9 m75 to 90 m1000 m (without repeaters)100 m (without repeaters)Current consumption60 mA (Tx mode)400 mA (Tx mode) 20 mA (standby mode)90-140 mA (Tx mode) 5μA (standby mode)25-35 mA (Tx mode) 3μA (standby mode)Raw data rate1 Mbps11 Mbps650 Kbps250 KbpsMinimum bandwidth required15 MHz22 MHz2 MHz (MCS0)2 MHzMemory requirements+250 Ko+8 Mo+1 Mo4-32 KoNumber of nodes7+2568000+65000Battery lifeMonthDaysDaysYearsNetwork topologyPoint-to-point broadcast meshStar treeStar treeSelf-forming, self-healing MESHSecurity modeL2CAP, LMP protocolWEP, WPA, WPA2In the application levelAES-128The main objective of this article is to propose a framework to optimize the time and effort by which a car would find a parking spot in a designated parking area. Speaking of power consumption, ZigBee-based networks typically consume 25% of the power of Wi-Fi networks, and ZigBee’s battery life is a major advantage over Wi-Fi and Bluetooth. In terms of system integrity and quality, ZigBee technology offers great performance and capabilities when sending data to the base station through sensor nodes. For this reason, we will develop and propose a self-organization protocol for sensor networks based on ZigBee wireless communication technology in order to extend the battery life of these nodes and to increase the longevity and efficiency of the WSN network in outdoor and urban car parks.


### 3.3. Network and Radio Models

In the design of the self-organization protocol, we consider a WSN which consists ofN sensor nodes deployed in an urban outdoor parking and a gateway that will act as a base station (BS) located outside the network zone. We denote the node i by si and the set of sensor nodes by S=s1,s2,⋯..,sN, où 1≤i≤N. The main properties of the network model are
(i)
The base station is fixed and located far from the sensor nodes(ii)
All sensor nodes are homogeneous and have similar communication, detection, and processing capabilities(iii)
The sensor nodes are subject to energy constraints(iv)
The nodes do not contain GSM or any long-distance communication system to send their locations directly to the BS(v)
Nodes can use power control when transmitting data(vi)
Nodes are not mobile(vii)
The BS does not know the location of the sensor nodes in the networks(viii)
The sensor nodes used are not expensive that generally will not have a cost too high on the deployment of the network WSNIn wireless sensor networks, the study of power consumption is fundamental for the proper functioning of the network and also important for analyzing the sensor node lifetime and the longevity of the WSN network.Each node of the WSN network comprises 3 modules: detection module, processing module, and communication module (Figure4). During operation of the wireless sensor network, each sensor node operates in 3 modes; when the detected data is sent by the sensor, the latter is in communication mode whose communication module is active. However, in case there is no information sent, the sensor enters the sleep mode. In this mode, the sensor only needs to monitor and process the events detected in its monitoring area. In this case, both detection and processing modules are switched on. This process reduces the energy dissipation in the network and minimizes energy consumption in the nodes [30].Figure 4
The modules of a sensor node.We will consider that the energy consumed by the detection modules as well as that of the treatment will not be taken into account because they are relatively negligible compared to the energy consumed by the communication module. The following formula shows the total energy consumed by each sensor node.(1)ESensor=ESens+EProc+EComm,(2)ESensor≈EComm,where ESens is the energy consumed during the detection process, EProc is the energy consumed during the process, and EComm is the energy consumed during the communication process.In the development of the self-organization protocol, we adopt the same radio model described by Heinzelman [31]. In this radio model, the receiver consumes energy to operate the receiver circuits at the time of receiving the data, and the transmitter consumes power to operate the power amplifier circuits and the transmitter circuits at the time of data transmission (Figure 5).Figure 5
Radio energy model.To transmit anL-bit data at a distance d, the total energy consumption is described by
(3)ETots=ETxL,d+ERxL,d.The two most popular transmission models used in WSNs are the transmission model for free space and two-spoke ground [31, 32]. In free space transmission, there is a visibility path direct between the transmitter and receiver node. In the two-ray terrestrial transmission model, the transmission between the transmitter and receiver nodes is not direct and the electromagnetic wave arrives at the receiver from different paths at different times. The energy consumed for the transmission of l-bit data packets, with the distance “d” and the energy consumed for the reception of “l” bits data by the receiving nodes, is represented by
(4)ETxL,d=EElec×L+L×∈fs×d2,d<d0,EElec×L+L×∈mp×d4,d≥d0,(5)ERxL,d=EElec×L,where d is the transmission distance, EElec is the energy consumed by the electronic circuits of the sensor, and ∈fsand∈mp are parameters of the amplification circuits for the transmission which depend on the propagation model used (∈fs for free space and ∈mp for multipath fading). d0 is the threshold distance for which the choice to use one model or another depends
(6)d0=4πLhthrλ,where htandhr are, respectively, the heights of the transmitting and receiving antennas, L≥1 represents the loss factor of the system and λ is the wavelength of the signal.


## 3.1. Sensor Types

For the monitoring of parking spaces, several outdoor parking management systems use different types of sensors between them: magnetic sensors, ultrasonic sensors, light sensors, etc. But most outdoor systems use magnetic sensors installed in each parking space to accurately detect the state of occupation (busy or empty) by measuring the magnetic field generated by the presence of a car knowing that it contains more than 100 magnetic parts [22–24]. Table 1 shows a comparison made between the 3 types of most used sensors.Table 1
Comparison between the different types of most used sensors.
Magnetic sensorLight sensorUltrasonic sensorAdvantages(i) Low cost (20-120 €)(ii) Range greater(iii) Reacts to north pole and south pole(iv) Insensible to vibrations(v) Best detection of cars(i) Average cost (60-300 €)(ii) Large range (1 m)(iii) Insensible to vibrations and no wear(iv) Detects any type of room with reflective power (direct reflection mode)(i) Large range (15 m)(ii) Detect without contact any object whatever the material(iii) Adjustable sensitivityLimitations(i) Average range (<300 mm)(ii) Requires the use of a magnet(iii) Sensitive to electromagnetic disturbances(i) Supports badly the harsh environments(ii) Sensitive to the appearance of parts (material, surface condition, color, gloss, impact ...)(i) High cost (200-1000 €)(ii) Sensitive to drafts(iii) Sensitive to temperature


## 3.2. Wireless Communication Technologies

The wireless communication in the outdoor car parks is affected by various factors among them: the obstacles created by cars, noise, interferences, etc. It is therefore necessary that the WSN sensor network operates reliably and efficiently during wireless communication in outdoor parkings despite possible environmental variations. The most common wireless communication technologies used for sensor networks are Bluetooth, Wi-Fi, and ZigBee.The deployment of the WSN sensor network in urban outdoor parkings forces the sensor nodes to be installed in the ground whose signal propagation is obstructed by cars and is also affected by their noise. For this type of application, many previous works have shown that conventional wireless standards such as Bluetooth or Wi-Fi are not suitable for this type of network in terms of quality and performance compared to the ZigBee standard in terms of quality and performance based on some parameters like BER (bit error rate) and SNR [25–27]. The following figure demonstrates the performance of ZigBee compared to other types of technologies (Figure 3).Figure 3
ZigBee 802.15.4 performance based on SNR.Concretely, bluetooth technology supports a very short range and a relatively low bandwidth, but it brings better rates of 1 Mbps with a higher energy consumption. Bluetooth is more adapted to the communications’ voice (auricles) or the connections from equipment to a PC or portable devices.Wi-Fi is a standardized technology with the IEEE 802.11x standard (x: a, b, c, g, n), managed by its certification process and provided by Wi-Fi alliance; it operates at 2.4 GHz, 5 GHz, and 60 GHz with a bandwidth of 0.3, 0.6, or 2 MHz. 802.11b-defined Wi-Fi networks have a maximum data transfer rate of 11 Mbps, while the a and c versions have a maximum data transfer rate of 54 Mbps. In terms of power consumption, these versions of the Wi-Fi network consume a lot of energy during wireless communication and they require a good battery backup if you want to use them for more than 10 hours. For this reason, a new IEEE 802.11ah Wi-Fi standard has been created, which supports a large number of heterogeneous devices in the Internet of Things (IoT). It offers attractive features such as improved scalability, low power consumption, and extended coverage over traditional Wi-Fi standards. However, this standard has not been recognized as energy efficient standard with 63 mJ/Packet compared to ZigBee technology with 17 mJ/Packet in a network with 100 nodes [28].ZigBee technology is created by the ZigBee Alliance and the IEEE under the IEEE 802.15.4 standard. It operates in global RF (2.4 GHz global, 915 MHz America, or 868 MHz Europe) whose data rate is 250 kbps at 2.4 GHz, 40 kbps at 915 MHz, and 20 kbps at 868 MHz. This standard provides low cost, low data rate, and low power connectivity for equipment that requires a battery life of several months to several years.Table2 shows the benefits and limitations of ZigBee over other wireless networks [29].Table 2
Comparison between different wireless communication technologies.
Wireless parameterBluetoothIEEE 802.11bIEEE 802.11ahZigbeeFrequency band2.4GHz2.4GHzSub-1 GHz2.4GHzRange9 m75 to 90 m1000 m (without repeaters)100 m (without repeaters)Current consumption60 mA (Tx mode)400 mA (Tx mode) 20 mA (standby mode)90-140 mA (Tx mode) 5μA (standby mode)25-35 mA (Tx mode) 3μA (standby mode)Raw data rate1 Mbps11 Mbps650 Kbps250 KbpsMinimum bandwidth required15 MHz22 MHz2 MHz (MCS0)2 MHzMemory requirements+250 Ko+8 Mo+1 Mo4-32 KoNumber of nodes7+2568000+65000Battery lifeMonthDaysDaysYearsNetwork topologyPoint-to-point broadcast meshStar treeStar treeSelf-forming, self-healing MESHSecurity modeL2CAP, LMP protocolWEP, WPA, WPA2In the application levelAES-128The main objective of this article is to propose a framework to optimize the time and effort by which a car would find a parking spot in a designated parking area. Speaking of power consumption, ZigBee-based networks typically consume 25% of the power of Wi-Fi networks, and ZigBee’s battery life is a major advantage over Wi-Fi and Bluetooth. In terms of system integrity and quality, ZigBee technology offers great performance and capabilities when sending data to the base station through sensor nodes. For this reason, we will develop and propose a self-organization protocol for sensor networks based on ZigBee wireless communication technology in order to extend the battery life of these nodes and to increase the longevity and efficiency of the WSN network in outdoor and urban car parks.


## 3.3. Network and Radio Models

In the design of the self-organization protocol, we consider a WSN which consists ofN sensor nodes deployed in an urban outdoor parking and a gateway that will act as a base station (BS) located outside the network zone. We denote the node i by si and the set of sensor nodes by S=s1,s2,⋯..,sN, où 1≤i≤N. The main properties of the network model are
(i)
The base station is fixed and located far from the sensor nodes(ii)
All sensor nodes are homogeneous and have similar communication, detection, and processing capabilities(iii)
The sensor nodes are subject to energy constraints(iv)
The nodes do not contain GSM or any long-distance communication system to send their locations directly to the BS(v)
Nodes can use power control when transmitting data(vi)
Nodes are not mobile(vii)
The BS does not know the location of the sensor nodes in the networks(viii)
The sensor nodes used are not expensive that generally will not have a cost too high on the deployment of the network WSNIn wireless sensor networks, the study of power consumption is fundamental for the proper functioning of the network and also important for analyzing the sensor node lifetime and the longevity of the WSN network.Each node of the WSN network comprises 3 modules: detection module, processing module, and communication module (Figure4). During operation of the wireless sensor network, each sensor node operates in 3 modes; when the detected data is sent by the sensor, the latter is in communication mode whose communication module is active. However, in case there is no information sent, the sensor enters the sleep mode. In this mode, the sensor only needs to monitor and process the events detected in its monitoring area. In this case, both detection and processing modules are switched on. This process reduces the energy dissipation in the network and minimizes energy consumption in the nodes [30].Figure 4
The modules of a sensor node.We will consider that the energy consumed by the detection modules as well as that of the treatment will not be taken into account because they are relatively negligible compared to the energy consumed by the communication module. The following formula shows the total energy consumed by each sensor node.(1)ESensor=ESens+EProc+EComm,(2)ESensor≈EComm,where ESens is the energy consumed during the detection process, EProc is the energy consumed during the process, and EComm is the energy consumed during the communication process.In the development of the self-organization protocol, we adopt the same radio model described by Heinzelman [31]. In this radio model, the receiver consumes energy to operate the receiver circuits at the time of receiving the data, and the transmitter consumes power to operate the power amplifier circuits and the transmitter circuits at the time of data transmission (Figure 5).Figure 5
Radio energy model.To transmit anL-bit data at a distance d, the total energy consumption is described by
(3)ETots=ETxL,d+ERxL,d.The two most popular transmission models used in WSNs are the transmission model for free space and two-spoke ground [31, 32]. In free space transmission, there is a visibility path direct between the transmitter and receiver node. In the two-ray terrestrial transmission model, the transmission between the transmitter and receiver nodes is not direct and the electromagnetic wave arrives at the receiver from different paths at different times. The energy consumed for the transmission of l-bit data packets, with the distance “d” and the energy consumed for the reception of “l” bits data by the receiving nodes, is represented by
(4)ETxL,d=EElec×L+L×∈fs×d2,d<d0,EElec×L+L×∈mp×d4,d≥d0,(5)ERxL,d=EElec×L,where d is the transmission distance, EElec is the energy consumed by the electronic circuits of the sensor, and ∈fsand∈mp are parameters of the amplification circuits for the transmission which depend on the propagation model used (∈fs for free space and ∈mp for multipath fading). d0 is the threshold distance for which the choice to use one model or another depends
(6)d0=4πLhthrλ,where htandhr are, respectively, the heights of the transmitting and receiving antennas, L≥1 represents the loss factor of the system and λ is the wavelength of the signal.


## 4. Proposed Algorithm

The fundamental theme of our proposed self-organization protocol is energy efficiency in a larger wireless sensor network that allows real-time data retrieval for the end user. The architectural design of our protocol is based on the hierarchical grouping approach (clusters) using an efficient and optimized algorithm to minimize unnecessary energy consumption in large scale networks [33, 34]. In our proposed protocol, the nodes are placed in a uniform way in the network field whose BS, which is outside, collects the positions of these nodes during the first phase in a progressive way using levels of recursive locations to avoid the huge energy dissipation due to direct transmissions to the BS, knowing that the BS does not know the location of the sensor nodes in the network and that the nodes do not contain GSM or any long-distance communication system to send their locations directly to the BS. These direct transmissions consume a lot of energy, especially the more distant nodes in a large-scale network. Figure 6 shows the flowchart, and Figure 7 provides an overview of our proposed protocol, respectively. The protocol consists of three phases: (1) the collection of node positions and cluster formation, (3) the selection of cluster heads (CHs), and (4) the collection and transmission data.Figure 6
Flowchart of proposed protocol.Figure 7
The basic architecture of the proposed protocol.


### 4.1. Collection of Node Positions and Cluster Formation

In this phase, the sensor network is divided into several levels of localization (Level 1, Level 2, …), until reaching all the nodes of the network. The creation of the localization levels is done in a progressive and recursive way in which the BS is responsible for the training of the first level (Level 1). The BS sends a HELLO message to the nearest nodes to send their positions. Once the BS receives the positions of these nodes, it begins to divide this first level into several sections (clusters) based on the angular value of each nodeθi. The BS calculates for each node of the first level its corresponding angular value (Figure 8).
(7)θi=arctanyi−ybsxi−xbs,xi>xbs,yi>ybs,90+arctanyi−ybsxi−xbs,xi<xbs,yi>ybs.Figure 8
The angular value of each node of the first level.Then, the BS begins to divide the first level intoα clusters Clusteri, whose parameter α is the number of clusters in each localization level, using the formula (8) from which each node receives a Cluster_ADV message (Node-Id, Level, and Cluster-Id) which contains the identifier of the node, the location level, and the cluster identifier that is part of it.
(8)Clusteri∈i−1θmax−θminα,iθmax−θminα,iϵ1,2,⋯,α.To group the positions of all the nodes, the BS selects node the furthest away from each cluster of each level as much as relay node by sending a message RelayNode_ADV_MSG(Node-Id, Level, Cluster-Id, and Relay-Id) of which Relay-Id is the identifier of the relay node (Relay-Id is the BS for the first level). Each selected relay node will play the role of the BS by sending a broadcast message HELLO to all the nearest nodes to send their positions. The nodes that will send their positions are those that are not part of any localization level and also no cluster (this decision is based on the strength of the received signal). Then, each relay node of each cluster will gather all the positions received from the higher level of location and it will send them to its Relay-Id for transmission to the BS. Once the BS receives new positions of the relay nodes, it starts the same process in a recursive way by sending the two messages Cluster_ADV (Node-Id, Level, and Cluster-Id) and RelayNode_ADV_MSG (Node-Id, Level, Cluster- Id, and Relay-Id) to the new nodes with the value of the level of location which will be incremented and with the value of the cluster which will be the same as that of their relay node. Figure 9 shows the exchange of different messages, and Figure 10 provides a general overview of the recursive algorithm used to minimize energy consumption and increase the durability of the nodes during the collection of all the positions of these nodes by the BS.Figure 9
Messages exchanged in the first phase.Figure 10
Recursive algorithm for collecting positions of all WSN nodes.Figure11 shows an example of the formation of localization levels and also the formation of clusters in a wireless sensor network with the α value equal to 3.Figure 11
Formation of localization levels and clusters withα=3.


### 4.2. Cluster Head Selection

After cluster creation and location levels, multiple candidate nodes compete to be selected as cluster heads for the current round. In this phase, each node broadcasts a message in its cluster containing its location. Each node receiving this message updates its neighborhood table which contains the distance to its neighbors and the number of neighbors, and it calculates its weight according to formula (8). After calculating the weight, each node competes to be selected as much as CH in the next turn if its weight is greater than a certain threshold T (n) indicated in formula (10) [35, 36].
(9)Weighti=REi×∑j=1numberofneighbors1dist2Si,Sj,where REi is the estimated current residual energy of node i; distSi,Sj is the distance between node i and node j.
(10)Tn=P1-P∗rmod1/P,if n∈G,0,otherwisewhere n is the total number of sensor nodes; P is the percentage of CH; r is the current turn; and G is a set of sensor nodes eligible to become CH.In each cluster, the candidate nodes exchange their weight among themselves and the node with the largest weight is elected as CH in its cluster for the current round. Noncandidate nodes go into sleep to minimize power consumption while waiting to receive the Cluster_Head_ADV_MSG message from the CH node to begin transmitting the data.The selection of CHs is not done periodically in each round. During the selection phase of the CHs, each node CH checks the value of its weight if it is below the thresholdT (n). In this case, the process for selecting a new CH begins by sending a Selection_Cluster Head_MSG message (Figure 12). In the opposite case, the node remains as much as CH in the next round to prevent the nodes from consuming more power during the CHS selection process and to balance the load between the different nodes in the next rounds. The selection of a new CH in each cluster is done independently from the rest of the clusters in each location level.Figure 12
The selection phase of cluster heads.


### 4.3. Data Transmission

After selecting the CHs, the process of transmitting data to the base station begins. Based on the TDMA protocol, communication is initiated between the different nodes of each cluster and their respective CHs in their corresponding time slots. The CHs aggregate the collected data and transmit it to the intermediate CH node or the BS according to the location level. To maximize the energy levels of the nodes, we designed an energy-efficient multihop communication when transmitting intercluster data to the base station taking into account residual energy and distances from neighboring CH nodes and the base station.For the first level of location, all the nodes are close to the base station including the CHs. For this reason and in order to reduce the energy consumption of these nodes, we have to use the single-hop communication to the base station for the first level as shown in Figure13.Figure 13
The communication phase of the first level of location.For the other location levels, there are several routes between the neighboring CHs and the base station using the intercluster multihop communication. The process of selecting the optimal routes between the different CHs and the BS starts with the CHs of the first level of location. Each CHj selected in the second phase broadcasts a nexthop_ClusterHead_MSG message containing the residual energy, the cumulative distance of its route to the base station, its identifier CH-id, its location, its location level, and the identification of its Cluster Cluster-id. Each upper-level node CHi receiving this message updates its neighbor table CHs and calculates a Weight-CHj of each neighbor CHj according to the formula (11). Each CHi node chooses a neighbor node CHj with the largest weight belonging to the lower location level as the next hop to transmit the collected data to the base station.
(11)Weight−CHj=EjEmax+dcSj,BSdcSj,BS+dSj,Si,ifLeveli>Levelj,where Ej denotes the estimated current residual energy; Emax is the maximum energy for all nodes; dcSj,BS is the cumulative distance between the node j and the base station; and dSj,Si is the distance between node i and node j.This process of selecting optimal data paths is repeated in all network location levels (Figure14). Figure 15 illustrates the optimal route construction steps and the data transmission between the CHs.Figure 14
The phase of data transmission and the selection of optimal routes to the base station.Figure 15
Optimal routes and data transmission between CHs. (a) Message propagation, (b) the transmission distance between the first level CHs and the base station, (c) the different routes between the CHs, and (d) selection of the best routes for intercluster data transmission.
(a)(b)(c)(d)Figure16 illustrates an example of which the CH 22 fills its neighborhood table of the CHs after reception of the nexthop_ClusterHead_MSG messages from different neighboring CHs (1, 8, 27). The CH 22 deletes the route to the base station passing through the CH 27 because it belongs to the same level, and it chooses the optimal route passing through the CH 1 of which it belongs at the lower level and its weight is greater than that of the CH 8.Figure 16
(a) Reception of the nexthop_ClusterHead_MSG messages par a CH. (b) Example of a neighborhood table and the selection of the next hop by a CH.
(a)(b)When transmitting data, the CHs closest to the base station will consume more energy compared to the others. Then, it will have a new selection of the new CHs in each cluster in an independent way according to the phase of the CHs selection. For each newly selected cluster head, it sends a New_nexthop_ClusterHead_MSG broadcast message containing the residual energy, its CH-id, its location, its location level, and the identification of its cluster Cluster-Id. Each CHi node receiving this message and which belongs to the higher level modifies its neighborhood table according to the location level and the Cluster-id of the new CH selected to make a new selection of a new optimal route to the base station as shown in Figure17. For lower-level CHs receiving the same message, they send the nexthop_ClusterHead_MSG message to the new CH again so that it can refill its neighbor table and select the next hop as the best route to the base station.Figure 17
(a) Sending a New_nexthop_ClusterHead_MSG broadcast message by the new CH. (b) Example of a neighborhood table and selection of a new CHL.
(a)(b)


## 4.1. Collection of Node Positions and Cluster Formation

In this phase, the sensor network is divided into several levels of localization (Level 1, Level 2, …), until reaching all the nodes of the network. The creation of the localization levels is done in a progressive and recursive way in which the BS is responsible for the training of the first level (Level 1). The BS sends a HELLO message to the nearest nodes to send their positions. Once the BS receives the positions of these nodes, it begins to divide this first level into several sections (clusters) based on the angular value of each nodeθi. The BS calculates for each node of the first level its corresponding angular value (Figure 8).
(7)θi=arctanyi−ybsxi−xbs,xi>xbs,yi>ybs,90+arctanyi−ybsxi−xbs,xi<xbs,yi>ybs.Figure 8
The angular value of each node of the first level.Then, the BS begins to divide the first level intoα clusters Clusteri, whose parameter α is the number of clusters in each localization level, using the formula (8) from which each node receives a Cluster_ADV message (Node-Id, Level, and Cluster-Id) which contains the identifier of the node, the location level, and the cluster identifier that is part of it.
(8)Clusteri∈i−1θmax−θminα,iθmax−θminα,iϵ1,2,⋯,α.To group the positions of all the nodes, the BS selects node the furthest away from each cluster of each level as much as relay node by sending a message RelayNode_ADV_MSG(Node-Id, Level, Cluster-Id, and Relay-Id) of which Relay-Id is the identifier of the relay node (Relay-Id is the BS for the first level). Each selected relay node will play the role of the BS by sending a broadcast message HELLO to all the nearest nodes to send their positions. The nodes that will send their positions are those that are not part of any localization level and also no cluster (this decision is based on the strength of the received signal). Then, each relay node of each cluster will gather all the positions received from the higher level of location and it will send them to its Relay-Id for transmission to the BS. Once the BS receives new positions of the relay nodes, it starts the same process in a recursive way by sending the two messages Cluster_ADV (Node-Id, Level, and Cluster-Id) and RelayNode_ADV_MSG (Node-Id, Level, Cluster- Id, and Relay-Id) to the new nodes with the value of the level of location which will be incremented and with the value of the cluster which will be the same as that of their relay node. Figure 9 shows the exchange of different messages, and Figure 10 provides a general overview of the recursive algorithm used to minimize energy consumption and increase the durability of the nodes during the collection of all the positions of these nodes by the BS.Figure 9
Messages exchanged in the first phase.Figure 10
Recursive algorithm for collecting positions of all WSN nodes.Figure11 shows an example of the formation of localization levels and also the formation of clusters in a wireless sensor network with the α value equal to 3.Figure 11
Formation of localization levels and clusters withα=3.


## 4.2. Cluster Head Selection

After cluster creation and location levels, multiple candidate nodes compete to be selected as cluster heads for the current round. In this phase, each node broadcasts a message in its cluster containing its location. Each node receiving this message updates its neighborhood table which contains the distance to its neighbors and the number of neighbors, and it calculates its weight according to formula (8). After calculating the weight, each node competes to be selected as much as CH in the next turn if its weight is greater than a certain threshold T (n) indicated in formula (10) [35, 36].
(9)Weighti=REi×∑j=1numberofneighbors1dist2Si,Sj,where REi is the estimated current residual energy of node i; distSi,Sj is the distance between node i and node j.
(10)Tn=P1-P∗rmod1/P,if n∈G,0,otherwisewhere n is the total number of sensor nodes; P is the percentage of CH; r is the current turn; and G is a set of sensor nodes eligible to become CH.In each cluster, the candidate nodes exchange their weight among themselves and the node with the largest weight is elected as CH in its cluster for the current round. Noncandidate nodes go into sleep to minimize power consumption while waiting to receive the Cluster_Head_ADV_MSG message from the CH node to begin transmitting the data.The selection of CHs is not done periodically in each round. During the selection phase of the CHs, each node CH checks the value of its weight if it is below the thresholdT (n). In this case, the process for selecting a new CH begins by sending a Selection_Cluster Head_MSG message (Figure 12). In the opposite case, the node remains as much as CH in the next round to prevent the nodes from consuming more power during the CHS selection process and to balance the load between the different nodes in the next rounds. The selection of a new CH in each cluster is done independently from the rest of the clusters in each location level.Figure 12
The selection phase of cluster heads.


## 4.3. Data Transmission

After selecting the CHs, the process of transmitting data to the base station begins. Based on the TDMA protocol, communication is initiated between the different nodes of each cluster and their respective CHs in their corresponding time slots. The CHs aggregate the collected data and transmit it to the intermediate CH node or the BS according to the location level. To maximize the energy levels of the nodes, we designed an energy-efficient multihop communication when transmitting intercluster data to the base station taking into account residual energy and distances from neighboring CH nodes and the base station.For the first level of location, all the nodes are close to the base station including the CHs. For this reason and in order to reduce the energy consumption of these nodes, we have to use the single-hop communication to the base station for the first level as shown in Figure13.Figure 13
The communication phase of the first level of location.For the other location levels, there are several routes between the neighboring CHs and the base station using the intercluster multihop communication. The process of selecting the optimal routes between the different CHs and the BS starts with the CHs of the first level of location. Each CHj selected in the second phase broadcasts a nexthop_ClusterHead_MSG message containing the residual energy, the cumulative distance of its route to the base station, its identifier CH-id, its location, its location level, and the identification of its Cluster Cluster-id. Each upper-level node CHi receiving this message updates its neighbor table CHs and calculates a Weight-CHj of each neighbor CHj according to the formula (11). Each CHi node chooses a neighbor node CHj with the largest weight belonging to the lower location level as the next hop to transmit the collected data to the base station.
(11)Weight−CHj=EjEmax+dcSj,BSdcSj,BS+dSj,Si,ifLeveli>Levelj,where Ej denotes the estimated current residual energy; Emax is the maximum energy for all nodes; dcSj,BS is the cumulative distance between the node j and the base station; and dSj,Si is the distance between node i and node j.This process of selecting optimal data paths is repeated in all network location levels (Figure14). Figure 15 illustrates the optimal route construction steps and the data transmission between the CHs.Figure 14
The phase of data transmission and the selection of optimal routes to the base station.Figure 15
Optimal routes and data transmission between CHs. (a) Message propagation, (b) the transmission distance between the first level CHs and the base station, (c) the different routes between the CHs, and (d) selection of the best routes for intercluster data transmission.
(a)(b)(c)(d)Figure16 illustrates an example of which the CH 22 fills its neighborhood table of the CHs after reception of the nexthop_ClusterHead_MSG messages from different neighboring CHs (1, 8, 27). The CH 22 deletes the route to the base station passing through the CH 27 because it belongs to the same level, and it chooses the optimal route passing through the CH 1 of which it belongs at the lower level and its weight is greater than that of the CH 8.Figure 16
(a) Reception of the nexthop_ClusterHead_MSG messages par a CH. (b) Example of a neighborhood table and the selection of the next hop by a CH.
(a)(b)When transmitting data, the CHs closest to the base station will consume more energy compared to the others. Then, it will have a new selection of the new CHs in each cluster in an independent way according to the phase of the CHs selection. For each newly selected cluster head, it sends a New_nexthop_ClusterHead_MSG broadcast message containing the residual energy, its CH-id, its location, its location level, and the identification of its cluster Cluster-Id. Each CHi node receiving this message and which belongs to the higher level modifies its neighborhood table according to the location level and the Cluster-id of the new CH selected to make a new selection of a new optimal route to the base station as shown in Figure17. For lower-level CHs receiving the same message, they send the nexthop_ClusterHead_MSG message to the new CH again so that it can refill its neighbor table and select the next hop as the best route to the base station.Figure 17
(a) Sending a New_nexthop_ClusterHead_MSG broadcast message by the new CH. (b) Example of a neighborhood table and selection of a new CHL.
(a)(b)


## 5. Simulation and Analysis of the Results

### 5.1. Simulation Platform

In this paper, we simulated our algorithm using the NS2 (Network Simulator Version 2) object-oriented network simulation platform, which must run on the UNIX/LINUX platform.The execution environment of NS2 is described as follows:(1)
On the Windows 8.1 operating system, the virtual machine software VirtualBox-5.1.26 is installed(2)
On the virtual machine, the Ubuntu operating system with version 16.04.3 is installed(3)
On the 16.04.3 Ubuntu platform, the NS2 application with the ns-allinone-2.35 version is downloaded and unzipped into the/usr/ns-allinone-2.35 directoryThe simulation is configured as follows:(i)
The network size is set to200m×200m(ii)
The number of nodes is 26(iii)
There is only one base station deployed outside the network(iv)
The sensor nodes are subject to energy constraints; i.e., they are not rechargeable and always contain data to be sent(v)
The sink node is outside the surveillance zone, indicated by the number “25” in Figure18Figure 18
Network topology for simulations.The parameters used in the simulation are shown in Table3.Table 3
Network parameters.
ParametersValueNetwork area (meter)200×200Number of nodes (N)25BS location20×135Initial energy (E0)2 JETx50 nJERx50 nJPacket size500 bytesSimulation time600 sα (Nombre de cluster par niveau)4


### 5.2. Simulation Results and Analysis

The simulation of the proposed self-organization algorithm is compared with the other algorithms seen in Section2 (alg1, alg2, … …, alg8) using a uniform node distribution according to Figure 19. To evaluate the performance of the data traffic and the quality of service of our proposed system compared to other algorithms, we used the following performance metrics.Figure 19
Total number of alive nodes.


#### 5.2.1. Number of Alive Nodes

The number of alive nodes is the total number of sensor nodes that have not yet exhausted all their energy and have enough to continue communication. In Figure18, all nodes are dead before exceeding 100 s of the simulation time for alg6, alg4, and alg3 knowing that the first nodes are dead in 22 s, 41 s, and 48 s, respectively. The reason for the premature death of the nodes for these algorithms is due to the fact that the residual energy of the nodes is not taken into consideration during the transmission of the data, whose nodes furthest away from the base station exhaust their energies quickly. On the other hand, the algorithms 1, 2, and 3 prolonged the duration of the death of the first node and also of the majority of the nodes by using the technique of clustering to balance the consumption of energy between the different nodes of each cluster. But, the communication of a single jump between the different CHs and the base station consumes a lot of energy which quickly depletes the battery of nodes. On the other hand, our proposed algorithm takes into account the enormous energy consumption during the formation of the clusters and the selection of the CHs in each round by using the technique of the recursion, which prolongs the duration of the death of the first node after exceeded 250 s of simulation time compared to other algorithms, and also increases the network’s long life by improving the duration of the death of all nodes in 380 s.


#### 5.2.2. Number of Dead Nodes

The number of dead nodes is the total number of sensor nodes that have exhausted all their energy and did not have enough to continue communication. The number of dead nodes with respect to the simulation time is indicated in Figure20. It can be seen that the stability period of the algorithms 1, 2, and 8 is a little longer compared to the algorithms 6, 3, and 4, which causes a short overall network time. On the other hand, the stability duration of our algorithm arrives up to 249 s compared to 220 s and 228 of the algorithms 5 and 7, respectively. This long duration of stability that offers our algorithm is due to the selection and the autonomous management of clusters and CHs in each cluster without intervention of the base station which minimizes the enormous consumption of energy when sending useless messages during cluster formation and selection of CHs in each round.Figure 20
Total number of dead nodes.


#### 5.2.3. Energy Consumption

The energy consumption is the amount of energy consumed by nodes relative to a number of turns. The main objective of this experiment is to compare the influence of the different algorithms studied alg1, alg2, …, alg8 and our proposed algorithm on the energy consumption of the whole network. Figure21 shows the experimental results.Figure 21
Comparison of energy consumption.The majority of the algorithms have consumed all their energies before exceeding 300 s of simulation except our proposed algorithm and alg5 and alg7. The low power consumption of these algorithms is due to taking into account the relationship between the position of the nodes and the residual energy in the clustering process. Our proposed system uses a recursive standalone algorithm for cluster formation and CH selection in each cluster, which minimizes and balances the energy consumption of each node in the network and also reduces the accelerated energy consumption of the cluster heads. For this reason, our proposed algorithm extends the lifetime of the nodes and increases the longevity of the network compared to other algorithms.


#### 5.2.4. First Node Dead (FND) et Network Lifetime (NL)

The following result illustrated in Figure22 relates to the lifetime of the network. We represent the lifetime of the network using two main metrics. The first is the time elapsed until the death of the first node (FND). The duration FND is considered a period of stability for the network since a node leaves the network during this period. The second is the total lifetime of the network which represents the time that there is no more node to continue the communication; this time is called network lifetime (NL).Figure 22
Comparison of network lifetime.According to the results obtained, our proposed algorithm offers stability between the different nodes in terms of energy consumption which allowed on the one hand to prolong the duration of the death of the first node compared to other algorithms and on the other hand increase the lifetime and longevity of the entire network.


#### 5.2.5. Packet Delivery Ratio (PDR)

The packet delivery ratio is the ratio of the number of packets that are successfully delivered to the destination to the total number of packets that are sent by the source (Formula (12)). This metric provides an indication of the robustness and reliability of a protocol. Therefore, a high packet delivery rate indicates better protocol performance. Figure 23 shows the experimental results.
(12)PDR=∑numberofpacketreceive∑numberofpacketsend.Figure 23
Comparison of packet delivery ratio.Our proposed algorithm offers a better quality of data reception at the sink level compared to other studied algorithms, which guarantees excellent reliability and better robustness.


## 5.1. Simulation Platform

In this paper, we simulated our algorithm using the NS2 (Network Simulator Version 2) object-oriented network simulation platform, which must run on the UNIX/LINUX platform.The execution environment of NS2 is described as follows:(1)
On the Windows 8.1 operating system, the virtual machine software VirtualBox-5.1.26 is installed(2)
On the virtual machine, the Ubuntu operating system with version 16.04.3 is installed(3)
On the 16.04.3 Ubuntu platform, the NS2 application with the ns-allinone-2.35 version is downloaded and unzipped into the/usr/ns-allinone-2.35 directoryThe simulation is configured as follows:(i)
The network size is set to200m×200m(ii)
The number of nodes is 26(iii)
There is only one base station deployed outside the network(iv)
The sensor nodes are subject to energy constraints; i.e., they are not rechargeable and always contain data to be sent(v)
The sink node is outside the surveillance zone, indicated by the number “25” in Figure18Figure 18
Network topology for simulations.The parameters used in the simulation are shown in Table3.Table 3
Network parameters.
ParametersValueNetwork area (meter)200×200Number of nodes (N)25BS location20×135Initial energy (E0)2 JETx50 nJERx50 nJPacket size500 bytesSimulation time600 sα (Nombre de cluster par niveau)4


## 5.2. Simulation Results and Analysis

The simulation of the proposed self-organization algorithm is compared with the other algorithms seen in Section2 (alg1, alg2, … …, alg8) using a uniform node distribution according to Figure 19. To evaluate the performance of the data traffic and the quality of service of our proposed system compared to other algorithms, we used the following performance metrics.Figure 19
Total number of alive nodes.


### 5.2.1. Number of Alive Nodes

The number of alive nodes is the total number of sensor nodes that have not yet exhausted all their energy and have enough to continue communication. In Figure18, all nodes are dead before exceeding 100 s of the simulation time for alg6, alg4, and alg3 knowing that the first nodes are dead in 22 s, 41 s, and 48 s, respectively. The reason for the premature death of the nodes for these algorithms is due to the fact that the residual energy of the nodes is not taken into consideration during the transmission of the data, whose nodes furthest away from the base station exhaust their energies quickly. On the other hand, the algorithms 1, 2, and 3 prolonged the duration of the death of the first node and also of the majority of the nodes by using the technique of clustering to balance the consumption of energy between the different nodes of each cluster. But, the communication of a single jump between the different CHs and the base station consumes a lot of energy which quickly depletes the battery of nodes. On the other hand, our proposed algorithm takes into account the enormous energy consumption during the formation of the clusters and the selection of the CHs in each round by using the technique of the recursion, which prolongs the duration of the death of the first node after exceeded 250 s of simulation time compared to other algorithms, and also increases the network’s long life by improving the duration of the death of all nodes in 380 s.


### 5.2.2. Number of Dead Nodes

The number of dead nodes is the total number of sensor nodes that have exhausted all their energy and did not have enough to continue communication. The number of dead nodes with respect to the simulation time is indicated in Figure20. It can be seen that the stability period of the algorithms 1, 2, and 8 is a little longer compared to the algorithms 6, 3, and 4, which causes a short overall network time. On the other hand, the stability duration of our algorithm arrives up to 249 s compared to 220 s and 228 of the algorithms 5 and 7, respectively. This long duration of stability that offers our algorithm is due to the selection and the autonomous management of clusters and CHs in each cluster without intervention of the base station which minimizes the enormous consumption of energy when sending useless messages during cluster formation and selection of CHs in each round.Figure 20
Total number of dead nodes.


### 5.2.3. Energy Consumption

The energy consumption is the amount of energy consumed by nodes relative to a number of turns. The main objective of this experiment is to compare the influence of the different algorithms studied alg1, alg2, …, alg8 and our proposed algorithm on the energy consumption of the whole network. Figure21 shows the experimental results.Figure 21
Comparison of energy consumption.The majority of the algorithms have consumed all their energies before exceeding 300 s of simulation except our proposed algorithm and alg5 and alg7. The low power consumption of these algorithms is due to taking into account the relationship between the position of the nodes and the residual energy in the clustering process. Our proposed system uses a recursive standalone algorithm for cluster formation and CH selection in each cluster, which minimizes and balances the energy consumption of each node in the network and also reduces the accelerated energy consumption of the cluster heads. For this reason, our proposed algorithm extends the lifetime of the nodes and increases the longevity of the network compared to other algorithms.


### 5.2.4. First Node Dead (FND) et Network Lifetime (NL)

The following result illustrated in Figure22 relates to the lifetime of the network. We represent the lifetime of the network using two main metrics. The first is the time elapsed until the death of the first node (FND). The duration FND is considered a period of stability for the network since a node leaves the network during this period. The second is the total lifetime of the network which represents the time that there is no more node to continue the communication; this time is called network lifetime (NL).Figure 22
Comparison of network lifetime.According to the results obtained, our proposed algorithm offers stability between the different nodes in terms of energy consumption which allowed on the one hand to prolong the duration of the death of the first node compared to other algorithms and on the other hand increase the lifetime and longevity of the entire network.


### 5.2.5. Packet Delivery Ratio (PDR)

The packet delivery ratio is the ratio of the number of packets that are successfully delivered to the destination to the total number of packets that are sent by the source (Formula (12)). This metric provides an indication of the robustness and reliability of a protocol. Therefore, a high packet delivery rate indicates better protocol performance. Figure 23 shows the experimental results.
(12)PDR=∑numberofpacketreceive∑numberofpacketsend.Figure 23
Comparison of packet delivery ratio.Our proposed algorithm offers a better quality of data reception at the sink level compared to other studied algorithms, which guarantees excellent reliability and better robustness.


## 5.2.1. Number of Alive Nodes

The number of alive nodes is the total number of sensor nodes that have not yet exhausted all their energy and have enough to continue communication. In Figure18, all nodes are dead before exceeding 100 s of the simulation time for alg6, alg4, and alg3 knowing that the first nodes are dead in 22 s, 41 s, and 48 s, respectively. The reason for the premature death of the nodes for these algorithms is due to the fact that the residual energy of the nodes is not taken into consideration during the transmission of the data, whose nodes furthest away from the base station exhaust their energies quickly. On the other hand, the algorithms 1, 2, and 3 prolonged the duration of the death of the first node and also of the majority of the nodes by using the technique of clustering to balance the consumption of energy between the different nodes of each cluster. But, the communication of a single jump between the different CHs and the base station consumes a lot of energy which quickly depletes the battery of nodes. On the other hand, our proposed algorithm takes into account the enormous energy consumption during the formation of the clusters and the selection of the CHs in each round by using the technique of the recursion, which prolongs the duration of the death of the first node after exceeded 250 s of simulation time compared to other algorithms, and also increases the network’s long life by improving the duration of the death of all nodes in 380 s.


## 5.2.2. Number of Dead Nodes

The number of dead nodes is the total number of sensor nodes that have exhausted all their energy and did not have enough to continue communication. The number of dead nodes with respect to the simulation time is indicated in Figure20. It can be seen that the stability period of the algorithms 1, 2, and 8 is a little longer compared to the algorithms 6, 3, and 4, which causes a short overall network time. On the other hand, the stability duration of our algorithm arrives up to 249 s compared to 220 s and 228 of the algorithms 5 and 7, respectively. This long duration of stability that offers our algorithm is due to the selection and the autonomous management of clusters and CHs in each cluster without intervention of the base station which minimizes the enormous consumption of energy when sending useless messages during cluster formation and selection of CHs in each round.Figure 20
Total number of dead nodes.


## 5.2.3. Energy Consumption

The energy consumption is the amount of energy consumed by nodes relative to a number of turns. The main objective of this experiment is to compare the influence of the different algorithms studied alg1, alg2, …, alg8 and our proposed algorithm on the energy consumption of the whole network. Figure21 shows the experimental results.Figure 21
Comparison of energy consumption.The majority of the algorithms have consumed all their energies before exceeding 300 s of simulation except our proposed algorithm and alg5 and alg7. The low power consumption of these algorithms is due to taking into account the relationship between the position of the nodes and the residual energy in the clustering process. Our proposed system uses a recursive standalone algorithm for cluster formation and CH selection in each cluster, which minimizes and balances the energy consumption of each node in the network and also reduces the accelerated energy consumption of the cluster heads. For this reason, our proposed algorithm extends the lifetime of the nodes and increases the longevity of the network compared to other algorithms.


## 5.2.4. First Node Dead (FND) et Network Lifetime (NL)

The following result illustrated in Figure22 relates to the lifetime of the network. We represent the lifetime of the network using two main metrics. The first is the time elapsed until the death of the first node (FND). The duration FND is considered a period of stability for the network since a node leaves the network during this period. The second is the total lifetime of the network which represents the time that there is no more node to continue the communication; this time is called network lifetime (NL).Figure 22
Comparison of network lifetime.According to the results obtained, our proposed algorithm offers stability between the different nodes in terms of energy consumption which allowed on the one hand to prolong the duration of the death of the first node compared to other algorithms and on the other hand increase the lifetime and longevity of the entire network.


## 5.2.5. Packet Delivery Ratio (PDR)

The packet delivery ratio is the ratio of the number of packets that are successfully delivered to the destination to the total number of packets that are sent by the source (Formula (12)). This metric provides an indication of the robustness and reliability of a protocol. Therefore, a high packet delivery rate indicates better protocol performance. Figure 23 shows the experimental results.
(12)PDR=∑numberofpacketreceive∑numberofpacketsend.Figure 23
Comparison of packet delivery ratio.Our proposed algorithm offers a better quality of data reception at the sink level compared to other studied algorithms, which guarantees excellent reliability and better robustness.


## 6. Conclusion

In this paper, we have proposed a self-organizing protocol for WSNs that can aggregate data and transmit it to a base station using clustering. The proposed protocol adopts a recursive and autonomous algorithm for the management of the nodes and the CH of each cluster independently of the others. This allows to make uniform the distribution of CHs, make the election of CHs more reasonable and more energy efficient, efficiently reduce the energy consumption when transmitting data between CHs and the base station, and avoid premature node death, thus extending the lifetime of all nodes and also the network.In addition, our adopted recursive algorithm is flexible when extending parking areas in the city, because the new sensor nodes are integrated automatically without any configuration carried out at the parking management system.Finally, our proposed protocol can also be deployed in various areas especially in the management of parking spaces in smart car parks, as it can guarantee the availability, reliability, consistency, and synchronization of information transmitted from different nodes to the base station. The results of the simulation of the various self-organization protocols studied in our paper and which are used in the management of parking spaces, show that our protocol has significantly improved the stability of the network, has balanced the energy consumption between different nodes, and also has allowed to lighten the load of the cluster heads and extended the lifetime of the sensor network.



---

*Source: 9179530-2020-07-13.xml*