# Adaptive Freeshape Clustering for Balanced Energy Saving in the WirelessHART Networks

Authors: Guangbing Xiao; Jiamin Shi; Ning Sun; Yong Chen; Yong Zhang
Journal: Complexity
 (2019)

---

## Abstract

The frequent data convergecasting from the sensor nodes to the gateways may cause imbalanced energy consumption in the Wireless Highway Addressable Remote Transducer (WirelessHART) networks, yielding a short network lifetime and frequent failures in the data acquisition. Existing solutions always tend to tradeoff between the hardware cost, routing complexity, and energy consumption, making the sensor nodes suffer from expensive hardware investment, overloaded network computation, or imbalanced energy consumption. In this paper, an Adaptive Freeshape Clustering (AFC) protocol is developed for saving and balancing the energy consumption in the WirelessHART networks. In AFC, the Region of Interest (RoI) is first divided into several fan-shaped clusters. The sensor nodes in each fan-shaped cluster compete for the positions of Cell Node (CN), and the nodes that have succeeded in the competition adjust the radius of their coverages to cover the fan-shaped clusters adaptively with the minimum overlapped areas. In this way, each fan-shaped cluster can be subdivided into several freeshape zones regarding each CN’s coverage, and the CN in each cluster takes charge of convergecasting the data to the CH. The simulations show that AFC can prolong the network lifetime by 37% compared with other related schemes, e.g., HEED, FLOODING, and DIRECT, whereas it can reduce the degree of energy imbalance by 1.29%.


---

## Body

## 1. Introduction

The Wireless Highway Addressable Remote Transducer (WirelessHART) networks are widely used for data convergecasting to address the needs in industrial applications, which usually consist of a number of low-power and short-range nodes for the sensing and monitoring of industrial environment [1]. As shown in Figure 1, the data acquired from the nodes is routed to the gateways and then uploaded to the host application for a comprehensive monitoring of events, status, and actions in the predefined Reign of Interest (RoI). These nodes are randomly distributed in the RoI and take charge of sensing, processing, and exchanging the physical information around the sensors, which are usually referred to asthe sensor nodes in the WirelessHART networks. The gateways in the WirelessHART networks are equipped with more on-chip resources in terms of the battery capacity, transmission range, data storage, computation power, etc. They are usually referred to asthe sinks in the WirelessHART networks, which take charge of collecting, analyzing, and forwarding the physical information from the sensor nodes and interacting with the application host for network management [2].Figure 1
The WirelessHART network is composed of a host application, several gateways, and a number of sensor nodes. The physical information sensed by the sensor nodes is collected by the gateways and then forwarded to the host application for the monitoring and control.The WirelessHART networks could be deployed in different application fields, e.g., the monitoring of meteorological environment, smart home, vehicle industry, and military defense, etc. [3]. Since the nodes are usually distributed in the harsh environment without attendance, a common drawback is that the batteries embedded in the nodes cannot be charged or replaced efficiently and conveniently. Therefore, the energy saving has become the primary task in the design of WirelessHART networks, which aims to prolong the network lifetime (i.e., the time duration between the instant when the network is initiated and the instant when the nodes fail to cover the RoI in the network) by improving the efficiency of energy utilization in the batteries embedded in the nodes. However, only executing the procedure of energy saving in the nodes is not sufficient as the nodes may suffer from unbalanced energy consumption in the WirelessHART networks [4]. For instance, some sensor nodes may consume the energy quickly and yield a short lifetime in the WirelessHART network, whereas some other sensor nodes may consume the energy slowly and yield a long lifetime in the WirelessHART network. Note that the network lifetime highly depends on the sensor node that has the shortest lifetime because any node that holds a dead battery may cause failures when convergecasting the data in the WirelessHART networks [5]. As a result, balancing the distribution of energy consumption among the nodes, which is referred to asthe consumption balancing in the rest of this paper, has become a key factor that should be considered when executing the procedure of energy saving in the WirelessHART networks.Many schemes on the energy saving have been proposed to address this issue, such as the energy harvesting, the routing optimization, the node dormancy, etc. [6]. However, these schemes either require a high cost in the hardware investment or increase the network complexity where the sensor nodes have to consume more energy in computing the optimal solution. This is highly against the original purpose of energy saving in the WirelessHART networks. In this paper, we have proposed a notable energy efficient protocol, namely, the Adaptive Freeshape Clustering (AFC), to prolong the lifetime of WirelessHART networks without balanced energy consumptions. In AFC, the RoI of WirelessHART network is divided into several fan-shaped clusters and each fan-shaped cluster is subdivided into several freeshape zones regarding the coverage of nodes. Each node keeps on adjusting the radius of its coverage and ensures all other nodes in the fan-shaped cluster can be covered with the minimum transmission range for the purpose of energy saving. Besides, the relationship between the network complexity and the performance of energy saving and consumption balancing is studied, and the simulation has shown that the proposed scheme can make a balanced distribution of energy consumption in both time and space, yielding an efficient mechanism of energy consumption and a long network lifetime in the WirelessHART networks.The paper is organized as follows. Some related works are reviewed in Section2, and the network model is given in Section 3. Section 4 introduces the preliminaries of routing algorithms in the wireless networks, and Section 5 presents an adaptive freeshape clustering protocol. Section 6 proves that the proposed clustering protocol can save the energy and balance the distribution of consumption in the network. Section 7 illustrates the simulation results, and Section 8 concludes the paper.


## 2. Related Work

As a traditional research topic in the area of WirelessHART networks, a lot of works have been carried out on the energy saving and consumption balancing. These works can be divided into three categories: the energy harvesting, the routing optimization, and the node dormancy.(  1) Energy Harvesting. To prolong the lifetime of batteries, the sensor nodes can be equipped with some energy harvesting devices to convert the solar energy and wind energy in the environment into electricity and charge the batteries. In [7], a hardware system for the collection of environmental energy is presented, which aims to charge the batteries in the sensor nodes by harvesting some electrical energy from the nature environment, e.g., the solar and wind energy. In [5], an energy harvesting system is developed to collect the electromagnetic energy from the commercial RF broadcast stations, e.g., GSM, broadcast radio, etc. However, due to the hardware cost in the energy harvesting devices and the low efficiency in converting the solar and wind energy into the electricity, the method of energy harvesting fails to meet the requirement of low cost, high efficiency of energy consumption in the WirelessHART networks.(  2) Routing Optimization. Compared with the method of energy harvest, the routing optimization does not require expensive hardware devices for converting the environmental energy into electricity to charge the batteries. Instead, it tends to save the energy by optimizing the path of data transmission in the network. In [8], a routing algorithm called DIRECT is proposed to prolong the network lifetime. However, the simulation results have shown that the network lifetime will be significantly shortened when the distance between the sink and sensor nodes increases. Another method is to optimize the path of data transmission based on the Low Energy Adaptive Clustering Hierarchy (LEACH) algorithm. In [9], a routing optimization based algorithm called Fuzzy LEACH (LEACH-F) is developed. In LEACH-F, the sink provides a list of sensor nodes for each cluster, and these sensor nodes help to collect and forward the data to the sinks for the purpose of energy saving. However, LEACH-F assumes that each sensor node can communicate with the sinks directly, which is not the case in the real world industrial environment. To address this issue, a Hybrid Energy-Efficient Distributed (HEED) clustering based algorithm is proposed for energy saving. The HEED based algorithm periodically elects some cluster heads among the sensor nodes, and the cluster heads cooperate with each other and forward the data to the sinks. Since not all the cluster heads have to transmit the data to the sink directly (within one hop), the energy consumption in transmitting the data can be significantly reduced.(  3) Node Dormancy. The node dormancy is another method that is frequently used to reduce the energy consumption, where the sensor nodes are scheduled between the status of sleeping and being active. Since the energy consumption in the sleeping status is much lower than that of the active status, a proper scheduling for the node dormancy can save the energy consumption and balance the consumption in the WirelessHART networks. In [10], the Low Energy Adaptive Clustering Hierarchical Central Sleep Protocol (LEACH-CS) is proposed with a scheduling function to decide which sensor node should be waked up for data transmission and which one should remain in the status of sleep. However, the performance on energy saving and data acquisition highly depends on the scheduling mechanism. If the sensor nodes cannot be awakened in time, it may cause failures in transmitting the data. In [11], a notable scheme on the dynamic dormancy of sensor nodes is proposed, where the sleep interval is varied in real time based on the estimated dwell time of the sensor nodes. The drawback is that the frequent scheduling of sensor nodes’ status will introduce large communication overhead in the WirelessHART networks. This is especially true when the number of sensor nodes is small, as the network structure formed by a limited number of sensor nodes is quite fragile where little improvement can be achieved in the energy saving and consumption balancing.


## 3. Network Model

In order to abstract the characteristics of energy consumptions in different applications, we model the WirelessHART network as a hierarchical cluster network as shown in Figure2, where the RoI of WirelessHART network is defined as a circle area with the radius of ro meters. Consider a set of nodes that are distributed in the WirelessHART network for the monitoring of physical information in the RoI, and a sink is located at the centre of the RoI. Each node is equipped with a radio transceiver with the radius of transmission range as r meters, which can be adjusted by employing different levels of transmission power. We assume the channel is symmetric and model the network topology as an undirected graph G=(N,L), where the vertices in N={ni∣i≤n,i∈Z+} represent n sensor nodes in the WirelessHART network and the edge lij in L={lij∣ni,nj∈N} denotes the wireless communication link between node ni and nj.Figure 2
The WirelessHART network is modelled as a hierarchical cluster network, where the red nodes represent the cluster heads and the blue nodes represent the cluster members.The RoI of WirelessHART network is first divided into several fan-shaped clusters, and the nodes in each fan-shaped cluster are subdivided into two groups: one Cluster Head (CH) and some Cluster Members (CMs). The CMs take charge of sensing the physical information in the surrounding environment and transmitting the data to the CH, whereas the CH takes charge of collecting the data from CMs in the cluster and communicates with the sink and other CHs for data convergecasting and network management. The CH is dynamically elected among the sensor nodes in the cluster based on some predefined metrics, e.g., the one with the maximum energy, the one with the maximum transmission range, etc. The elected CHs should be able to communicate with each CM in the cluster and ensure the data acquired by the CMs can be collected and uploaded to the sink reliably.To quantitatively describe the procedure of energy consumption in the WirelessHART networks, we use the formulation in (1) to calculate the energy consumption in the sensor nodes.(1)eni,nj=x0+εxαwhere e(ni,nj) is the energy consumed in transmitting one bit of data from the sending node ni to the receiving node nj; x0 is the energy consumption of the hardware circuit in the sending node; ε is the power amplifier coefficient when transmitting the data; x is the propagation distance between the sending node ni and the receiving node nj; α is the path loss factor, which varies between 2 and 4 regarding the signal blocks on the propagation path, such as the vegetation, buildings, etc.To evaluate the performance of energy saving and consumption balancing in the WirelessHART networks, the following key indicators are used to calculate the network lifetime and the energy balancing.(1)The coverage ratio, denoted by pcover, is defined as the ratio between the area that is covered by the sensor nodes and the whole area of the RoI in WirelessHART network.(2)The network lifetime, denoted by TN, is calculated as the time duration between the instant when the WirelessHART network is initiated and the instant when the coverage ratio pcover has dropped to a predefined threshold.(3)The lifetime of the first dead node in the WirelessHART network, denoted by T1st, is defined as the time duration between the instant when the WirelessHART network is initiated and the instant when a node has firstly run out of energy.(4)The degree of energy imbalance in the WirelessHART network, denoted by η=TN-T1st/TN, is calculated by dividing the difference between the network lifetime and the lifetime of the first dead node by the network lifetime.


## 4. Preliminary on Routing Algorithms

The routing algorithms in the WirelessHART networks can be divided into two categories regarding the number of hops between the sensor nodes and the sinks when convergecasting the data, e.g., the single-hop routing algorithms [12] and the multihop routing algorithms [13]. A classical single-hop routing algorithm is DIERCT [14], and it is usually regarded as a broadcast mechanism where the sending nodes transmitted the data to the sink directly. The DIRECT algorithms are easy to implement but are usually used in the networks with small RoIs due to the short transmission range of nodes. Therefore, they are often employed as a bench mark in the simulations and experiments for the purpose of performance comparison. Since the RoI of WirelessHART networks usually covers a large area in the industrial environment, we focus on the multihop routing algorithms, where the data can be transmitted over a long distance hop by hop via data forwarding. Considering the network structure, the multihop algorithms can be divided into planar routing algorithms and hierarchical routing algorithms.


### 4.1. The Planar Routing Algorithms

FLOODING [15] and GOSSIPING [16] are two groups of planar routing algorithms in the WirelessHART networks, where the sensor nodes are equally privileged, equipotent participants in the networks. In the FLOODING based routing algorithms, the sensor nodes send the data to all the neighboring nodes via broadcasting, and the neighboring nodes go on forwarding the data to their neighbors. In this way, the data can be forwarded hop by hop until it reaches the sinks. The FLOODING based routing algorithms enforce all the nodes to forward the data, yielding a high packet delivery ratio in the data convergecasting. However, the redundant data forwarding in the FLOODING based routing algorithms will cause a high risk of blocking the communication channels, and the nodes have to consume more energies to retransmit the data, which may even evolve into a DoS attack under certain conditions. To address this issue, the GOSSIPING based routing algorithms are proposed where the nodes only forward the data to a limited number of neighbors. This can alleviate the pressure of data congestion in the WirelessHART networks and reduce the energy consumption at the nodes. However, the inherent drawback of redundant data forwarding remains unsolved, and it may also yield unpredictable time delays in the delivery of data in the WirelessHART networks.


### 4.2. The Hierarchical Routing Algorithms

Different from the planar routing algorithms, the hierarchical routing algorithms divide the sensor nodes into several roles, e.g., cluster heads, cluster members, routers, gateways, etc., and the sensor nodes with different roles take charge of different tasks of data convergecasting in the WirelessHART networks. For instance, LEACH is a typical hierarchical routing algorithm which divides the RoI into several clusters by running the procedure of CH election periodically. All the nodes compete for the position of CHs based on some predefined metrics, e.g., the energy optimal, the coverage optimal, etc. The CHs collect the data from the CMs and then forward it to the sinks. Since the data from all the CMs is compressed into one packet and forwarded to the sinks by the CHs, it is not necessary for the CMs to communicate with the sink directly. Although the CHs tend to consume more energy than the CMs due to the data forwarding, the election of CHs will be executed periodically and the one with a low remaining energy will be replaced by other CMs. In this way, the overall energy consumption will be evenly distributed to all the CMs in the WirelessHART networks which helps to avoid continuous energy consumption at some nodes. However, the procedure of CH election in LEACH is executed without any control mechanism on the distribution of CHs, and the CHs may appear with a high density in some zones whereas they appear sparsely in other zones. Besides, LEACH assumes all the CHs can communicate with the sinks in one hop, which is not the case in the real world scenarios.To overcome the drawbacks in LEACH, the HEED based algorithms are developed which can cut down the redundant data forwarding in the WirelessHART networks [17]. As shown in Figure 3, the CHs collect the data from all the CMs in each cluster. The difference is the CHs that are close to the sink will help other CHs that are far away from the sink forward the data. In other words, not all CHs have to communicate with the sink directly, and the CHs that are close to the sinks will help to forward the data, which can save the energy in the data covergecasting. Similar to LEACH, the CHs in the HEED based algorithms are selected based on the remaining energy in the nodes, and the one with the remaining energy higher than a predefined threshold will be selected as the CH. Consider a sensor node ni in the WirelessHART network. Denote the initial election probability of the sensor node by pIniti, and Eremaini is the remaining energy in the sensor node ni, whereas Emax is the maximum energy capacity of the battery in the sensor node ni. Then, the probability of the sensor node ni being selected as the CH, denoted by pCHi, can be calculated as pCHi=pIniti×(Eremaini/Emax).Figure 3
The network topology in the HEED based algorithms, where the CHs collect the data from the CMs and then transmit it to the sink.Since the CHs help each other to forward the data and not all CHs have to communicate with the sinks directly, the HEED based routing algorithms can save more energy in the data convergecasting compared with that of LEACH. However, there is still much room for improvement in both the energy saving and consumption balancing. For instance, the task of data forwarding will cause extra energy consumption in the CHs, and the CMs can save the energy and balance the distribution of consumption in the cluster. In the following sections, we propose a new routing protocol based on the structure of HEED, namely, AFC, for energy saving energy and consumption balancing in the WirelessHART networks. In AFC, the procedure of CH elections is modified where a new role calledthe Cell Node (CN) is added. The CNs can make a reliable data delivery by covering the CMs redundantly, and it can also help the CHs to collect the data from the CMs with short distances in the data transmission.


## 4.1. The Planar Routing Algorithms

FLOODING [15] and GOSSIPING [16] are two groups of planar routing algorithms in the WirelessHART networks, where the sensor nodes are equally privileged, equipotent participants in the networks. In the FLOODING based routing algorithms, the sensor nodes send the data to all the neighboring nodes via broadcasting, and the neighboring nodes go on forwarding the data to their neighbors. In this way, the data can be forwarded hop by hop until it reaches the sinks. The FLOODING based routing algorithms enforce all the nodes to forward the data, yielding a high packet delivery ratio in the data convergecasting. However, the redundant data forwarding in the FLOODING based routing algorithms will cause a high risk of blocking the communication channels, and the nodes have to consume more energies to retransmit the data, which may even evolve into a DoS attack under certain conditions. To address this issue, the GOSSIPING based routing algorithms are proposed where the nodes only forward the data to a limited number of neighbors. This can alleviate the pressure of data congestion in the WirelessHART networks and reduce the energy consumption at the nodes. However, the inherent drawback of redundant data forwarding remains unsolved, and it may also yield unpredictable time delays in the delivery of data in the WirelessHART networks.


## 4.2. The Hierarchical Routing Algorithms

Different from the planar routing algorithms, the hierarchical routing algorithms divide the sensor nodes into several roles, e.g., cluster heads, cluster members, routers, gateways, etc., and the sensor nodes with different roles take charge of different tasks of data convergecasting in the WirelessHART networks. For instance, LEACH is a typical hierarchical routing algorithm which divides the RoI into several clusters by running the procedure of CH election periodically. All the nodes compete for the position of CHs based on some predefined metrics, e.g., the energy optimal, the coverage optimal, etc. The CHs collect the data from the CMs and then forward it to the sinks. Since the data from all the CMs is compressed into one packet and forwarded to the sinks by the CHs, it is not necessary for the CMs to communicate with the sink directly. Although the CHs tend to consume more energy than the CMs due to the data forwarding, the election of CHs will be executed periodically and the one with a low remaining energy will be replaced by other CMs. In this way, the overall energy consumption will be evenly distributed to all the CMs in the WirelessHART networks which helps to avoid continuous energy consumption at some nodes. However, the procedure of CH election in LEACH is executed without any control mechanism on the distribution of CHs, and the CHs may appear with a high density in some zones whereas they appear sparsely in other zones. Besides, LEACH assumes all the CHs can communicate with the sinks in one hop, which is not the case in the real world scenarios.To overcome the drawbacks in LEACH, the HEED based algorithms are developed which can cut down the redundant data forwarding in the WirelessHART networks [17]. As shown in Figure 3, the CHs collect the data from all the CMs in each cluster. The difference is the CHs that are close to the sink will help other CHs that are far away from the sink forward the data. In other words, not all CHs have to communicate with the sink directly, and the CHs that are close to the sinks will help to forward the data, which can save the energy in the data covergecasting. Similar to LEACH, the CHs in the HEED based algorithms are selected based on the remaining energy in the nodes, and the one with the remaining energy higher than a predefined threshold will be selected as the CH. Consider a sensor node ni in the WirelessHART network. Denote the initial election probability of the sensor node by pIniti, and Eremaini is the remaining energy in the sensor node ni, whereas Emax is the maximum energy capacity of the battery in the sensor node ni. Then, the probability of the sensor node ni being selected as the CH, denoted by pCHi, can be calculated as pCHi=pIniti×(Eremaini/Emax).Figure 3
The network topology in the HEED based algorithms, where the CHs collect the data from the CMs and then transmit it to the sink.Since the CHs help each other to forward the data and not all CHs have to communicate with the sinks directly, the HEED based routing algorithms can save more energy in the data convergecasting compared with that of LEACH. However, there is still much room for improvement in both the energy saving and consumption balancing. For instance, the task of data forwarding will cause extra energy consumption in the CHs, and the CMs can save the energy and balance the distribution of consumption in the cluster. In the following sections, we propose a new routing protocol based on the structure of HEED, namely, AFC, for energy saving energy and consumption balancing in the WirelessHART networks. In AFC, the procedure of CH elections is modified where a new role calledthe Cell Node (CN) is added. The CNs can make a reliable data delivery by covering the CMs redundantly, and it can also help the CHs to collect the data from the CMs with short distances in the data transmission.


## 5. Adaptive Freeshape Based Clustering

Based on the structure of HEED, a hierarchical clustering routing protocol called AFC is proposed to improve the efficiency of energy saving and consumption balancing in the WirelessHART networks. In AFC, the RoI is divided into several fan-shaped clusters, and each fan-shaped cluster periodically elects a CH based on a competition mechanism. Meanwhile, all the sensor nodes in the fan-shaped cluster compete for the role of CNs, which take charge of helping the CH collect data from the CMs. Putting it in another way, AFC has a three-layer network structure, e.g., the CHs in the upper layer, the CNs in the middle layer, and the CMs in the bottom layer. The CMs take charge of sensing the surrounding physical information and sending the data to the CNs, whereas the CNs take charge of collecting all the data inside of its coverage and forwarding it to the CH. Since the distance between the CMs and CNs is usually shorter than that between the CMs and the CH, the energy consumption of data convergecasting in AFC can be reduced. In the following subsection, we divide the procedure of AFC into three phases, e.g., the fan-shaped clustering, the adaptive freeshape subdividing, and data convergecasting.


### 5.1. Phase I: The Fan-Shaped Clustering

In the phase of fan-shaped clustering, the RoI of WirelessHART networks is divided into several fan-shaped clusters. For each cluster in the RoI, only one CH will be elected, which takes charge of collecting the data from CMs in the cluster and forwarding it to the sinks or other CHs. Consider a nodeni that is competing for CH, and the election depends on the following three factors.(  1) The Remaining Energy (RE). When electing the CH in the cluster, the more remaining energy a node has, the higher probability it will be elected as the CH. This is because the CHs tend to consume more energy when collecting and forwarding the data, and electing the nodes that have more remaining energy avoids overloading other nodes that have less remaining energy.(  2) The Link Connectivity to CHs (LCC). LCC is defined as the number of good links from node ni to other CHs, where the sink can be regarded as a special CH. The node with more good links to other CHs should be given a higher priority to be selected as a CH. This ensures the node can make a reliable delivery of packets to the sink directly or to other CHs for forwarding.(  3) The Reaching Energy Consumption (REC). REC is defined as the average energy consumption in transmitting one-bit data from each other node in the current cluster to node ni. Different from the election of CHs in the HEED based algorithms, the remaining energy is not the only factor that is considered in the election as REC will also impact the election of CHs which aims to balance the distribution of CHs in the cluster.The detailed procedure of CH election can be summarized within the following steps: (i) each node in the fan-shaped cluster calculates its remaining energy and generates a random number. The more remaining energy a node has, the larger random number it will generate; (ii) the nodes with a number that is larger than a predefined threshold will be elected as the CH candidates; (iii) the CH candidates that fail to reach any other CH or the sink will be excluded; (iv) if there is only one CH candidate in the fan-shaped cluster, it will be selected as the CH automatically; if there exist two or more CH candidates in the fan-shaped cluster, the one with a smaller REC will be selected as the CH.


### 5.2. Phase II: The Adaptive Freeshape Subdividing

In order to save energy and balance the distribution of consumption, each cluster is further divided into several freeshape zones. As shown in Figure4, a number of CMs will be elected to cover other CMs in the cluster, which are referred to asthe cell nodes in the WirelessHART networks. The CNs may use different radius of transmission range to cover the cluster cooperatively, where the fan-shaped cluster will be subdivided into some freeshaped zones regarding each CN’s radius of transmission range. The problem is how to elect the CNs in the cluster. To address this issue, we first give the definition on the Fully Constrained Circle (FCC) and then describe the procedure of CN election based on the concept of FCC.Figure 4
The comparison of data forwarding in HEED and AFC: CMs forward the data to the CH directly in HEED, whereas the CNs in AFC collect the data from CMs and then forward it to the CH.Definition 1.
Consider a fan-shaped cluster in the WirelessHART networks and assume the transmission range of each sensor node in the fan-shaped cluster is a circle area. If an arbitrary arc on the nodeni’s circumference has been covered by at least one sensor node’s transmission range, then the circumference of node ni is defined as a Fully Constrained Circumference (FCC).Suppose the radius of nodeni’s transmission range is r meters. If the circumference is not a FCC, then node ni should keep the transmission range r unchanged. If the circumference is a FCC, i.e., an arbitrary arc on the node ni’s circumference has been covered by at least one node’s circumferences, then node ni should use the following rules to explore the potential blind zones and adjust the radius of its transmission range for the energy saving and consumption balancing in the cluster.Rule 1.
Consider a sensor nodeni with a fully constrained circumference, and assume it is not a CH in the fan-shaped cluster. Let cj be one of the cross points inside of node ni’s circumference, and cj is the number of sensor nodes that cover the cross point cj inside of their transmission ranges.
( 1 ) If only two sensor nodes have covered the cross point inside of their transmission ranges, i.e., cj=2, then the cross point is a vertex of the blind zone.
( 2 ) If more than two sensor nodes have covered the cross point inside of their transmission ranges, i.e., cj≥2, then the cross point is a general vertex inside of node ni’s transmission range rather than a vertex of the blind zone.
( 3 ) Let C={c1,c2⋯cn} be the vertices of a blind zone inside of node ni’s circumference. Denote the centre point of node ni’s circumference by o, and d(o,ci) is the Euclidean distance between the centre point o and the vertex ci. Then, node ni should adjust the radius of transmission range as r′=maxdo,c1,do,c2…do,cn.Take the radius adjustment of nodeni in Figure 5 for example. {c1,c2,⋯c8} are the cross points covered by two sensor nodes, which indicate the vertices of a blind zone (the shaded block as shown in Figure 5). In contrast, {c1′,c2′} are the cross points that are covered by three sensor nodes, which indicate the general vertices in node ni’s circumference rather than the vertices of a blind zone. Then, node ni should adjust the radius of transmission range as r′=max{d(o,c1),d(o,c2)…d(o,c8)} to cover the blind zone in the shaded block and reduce the energy consumption by employing a small radius of transmission range. Note that there may exist some scenarios where none of the cross points is the vertex of a blind zone. In other words, there is no blind zone for the recovery of node ni, and node ni can set the radius of transmission range as r′=0. Then, the node with a none-zero radius will be elected as a CN; otherwise, it remains as a CM. Note that Rule 1 is not suitable for CHs in the fan-shaped cluster, and the radius of CH cannot be reduced even if satisfies the requirement in Rule 1; otherwise, it may fail to receive the packet from other CMs in the cluster. The pseudocode is presented in Algorithm 1.Algorithm 1:The adaptive subdividing at node ni.
Search the neighors in the cluster, and collect the information such as the centre point, radius, etc. if the circumference is a FCC then //Check the cross point forEach neighbor nj in the clusterdo Calculate the cross points at the circumference of node ni and nj; //Explore the blind zone for Each cross point at the circumference do if the cross point is covered by two nodes then The cross pint belongs to a blind zone; else The cross pint is a general vertex; //Adjust the radius if There exists a blind zone then Set the radius to cover the farthest vertex of the blind zone; else Set the radius as 0;Figure 5
The nodeni adjusts the radius of transmission range to cover the blind zone for the purpose of saving the energy and balancing the network.


### 5.3. Phase III: The Convergecasting

In the phase of convergecasting, each CM takes charge of sensing the surrounding physical information and transmits the data to the CNs, whereas the CNs help the CH collect the data from the CMs. Specifically, after the election of CH in the cluster, the CNs collect the data from the CMs inside of their freeshape zones and forward it to the CHs. After acquiring the data from the CNs, the CH will transmit it directly to the sink if the sink is inside of its coverage; otherwise, the CH will forward the data to other CHs that are close to the sink, so that the data can be relayed with a low energy consumption.


## 5.1. Phase I: The Fan-Shaped Clustering

In the phase of fan-shaped clustering, the RoI of WirelessHART networks is divided into several fan-shaped clusters. For each cluster in the RoI, only one CH will be elected, which takes charge of collecting the data from CMs in the cluster and forwarding it to the sinks or other CHs. Consider a nodeni that is competing for CH, and the election depends on the following three factors.(  1) The Remaining Energy (RE). When electing the CH in the cluster, the more remaining energy a node has, the higher probability it will be elected as the CH. This is because the CHs tend to consume more energy when collecting and forwarding the data, and electing the nodes that have more remaining energy avoids overloading other nodes that have less remaining energy.(  2) The Link Connectivity to CHs (LCC). LCC is defined as the number of good links from node ni to other CHs, where the sink can be regarded as a special CH. The node with more good links to other CHs should be given a higher priority to be selected as a CH. This ensures the node can make a reliable delivery of packets to the sink directly or to other CHs for forwarding.(  3) The Reaching Energy Consumption (REC). REC is defined as the average energy consumption in transmitting one-bit data from each other node in the current cluster to node ni. Different from the election of CHs in the HEED based algorithms, the remaining energy is not the only factor that is considered in the election as REC will also impact the election of CHs which aims to balance the distribution of CHs in the cluster.The detailed procedure of CH election can be summarized within the following steps: (i) each node in the fan-shaped cluster calculates its remaining energy and generates a random number. The more remaining energy a node has, the larger random number it will generate; (ii) the nodes with a number that is larger than a predefined threshold will be elected as the CH candidates; (iii) the CH candidates that fail to reach any other CH or the sink will be excluded; (iv) if there is only one CH candidate in the fan-shaped cluster, it will be selected as the CH automatically; if there exist two or more CH candidates in the fan-shaped cluster, the one with a smaller REC will be selected as the CH.


## 5.2. Phase II: The Adaptive Freeshape Subdividing

In order to save energy and balance the distribution of consumption, each cluster is further divided into several freeshape zones. As shown in Figure4, a number of CMs will be elected to cover other CMs in the cluster, which are referred to asthe cell nodes in the WirelessHART networks. The CNs may use different radius of transmission range to cover the cluster cooperatively, where the fan-shaped cluster will be subdivided into some freeshaped zones regarding each CN’s radius of transmission range. The problem is how to elect the CNs in the cluster. To address this issue, we first give the definition on the Fully Constrained Circle (FCC) and then describe the procedure of CN election based on the concept of FCC.Figure 4
The comparison of data forwarding in HEED and AFC: CMs forward the data to the CH directly in HEED, whereas the CNs in AFC collect the data from CMs and then forward it to the CH.Definition 1.
Consider a fan-shaped cluster in the WirelessHART networks and assume the transmission range of each sensor node in the fan-shaped cluster is a circle area. If an arbitrary arc on the nodeni’s circumference has been covered by at least one sensor node’s transmission range, then the circumference of node ni is defined as a Fully Constrained Circumference (FCC).Suppose the radius of nodeni’s transmission range is r meters. If the circumference is not a FCC, then node ni should keep the transmission range r unchanged. If the circumference is a FCC, i.e., an arbitrary arc on the node ni’s circumference has been covered by at least one node’s circumferences, then node ni should use the following rules to explore the potential blind zones and adjust the radius of its transmission range for the energy saving and consumption balancing in the cluster.Rule 1.
Consider a sensor nodeni with a fully constrained circumference, and assume it is not a CH in the fan-shaped cluster. Let cj be one of the cross points inside of node ni’s circumference, and cj is the number of sensor nodes that cover the cross point cj inside of their transmission ranges.
( 1 ) If only two sensor nodes have covered the cross point inside of their transmission ranges, i.e., cj=2, then the cross point is a vertex of the blind zone.
( 2 ) If more than two sensor nodes have covered the cross point inside of their transmission ranges, i.e., cj≥2, then the cross point is a general vertex inside of node ni’s transmission range rather than a vertex of the blind zone.
( 3 ) Let C={c1,c2⋯cn} be the vertices of a blind zone inside of node ni’s circumference. Denote the centre point of node ni’s circumference by o, and d(o,ci) is the Euclidean distance between the centre point o and the vertex ci. Then, node ni should adjust the radius of transmission range as r′=maxdo,c1,do,c2…do,cn.Take the radius adjustment of nodeni in Figure 5 for example. {c1,c2,⋯c8} are the cross points covered by two sensor nodes, which indicate the vertices of a blind zone (the shaded block as shown in Figure 5). In contrast, {c1′,c2′} are the cross points that are covered by three sensor nodes, which indicate the general vertices in node ni’s circumference rather than the vertices of a blind zone. Then, node ni should adjust the radius of transmission range as r′=max{d(o,c1),d(o,c2)…d(o,c8)} to cover the blind zone in the shaded block and reduce the energy consumption by employing a small radius of transmission range. Note that there may exist some scenarios where none of the cross points is the vertex of a blind zone. In other words, there is no blind zone for the recovery of node ni, and node ni can set the radius of transmission range as r′=0. Then, the node with a none-zero radius will be elected as a CN; otherwise, it remains as a CM. Note that Rule 1 is not suitable for CHs in the fan-shaped cluster, and the radius of CH cannot be reduced even if satisfies the requirement in Rule 1; otherwise, it may fail to receive the packet from other CMs in the cluster. The pseudocode is presented in Algorithm 1.Algorithm 1:The adaptive subdividing at node ni.
Search the neighors in the cluster, and collect the information such as the centre point, radius, etc. if the circumference is a FCC then //Check the cross point forEach neighbor nj in the clusterdo Calculate the cross points at the circumference of node ni and nj; //Explore the blind zone for Each cross point at the circumference do if the cross point is covered by two nodes then The cross pint belongs to a blind zone; else The cross pint is a general vertex; //Adjust the radius if There exists a blind zone then Set the radius to cover the farthest vertex of the blind zone; else Set the radius as 0;Figure 5
The nodeni adjusts the radius of transmission range to cover the blind zone for the purpose of saving the energy and balancing the network.


## 5.3. Phase III: The Convergecasting

In the phase of convergecasting, each CM takes charge of sensing the surrounding physical information and transmits the data to the CNs, whereas the CNs help the CH collect the data from the CMs. Specifically, after the election of CH in the cluster, the CNs collect the data from the CMs inside of their freeshape zones and forward it to the CHs. After acquiring the data from the CNs, the CH will transmit it directly to the sink if the sink is inside of its coverage; otherwise, the CH will forward the data to other CHs that are close to the sink, so that the data can be relayed with a low energy consumption.


## 6. The Analysis of Balanced Energy Saving

In AFC, the CHs not only have to collect the data from CNs but also help other CHs forward the data to the sinks. In this section, we prove that if certain conditions are satisfied, the adaptive clustering and data forwarding in AFC can save the energy and balance the consumption in the nodes.As shown in Figure6, suppose ns is a sending node and nd is a sink in the WirelessHART network. A forwarding node nf′ is located on the straight line between the sending node and the sink. Set the path loss factor α as 2, and the power amplifier coefficient ε is 1 in the energy propagation model. Then, the energy consumed in transmitting the data directly from node ns to the sink nd can be calculated as Esd=x0+d2, where x0 is the energy consumed by the hardware circuit in the sensor node; d is the propagation distance between the sending node and the sink. Note that the data can also be delivered to the sink via node nf′’s forwarding, which is located at the straight line between the node ns and the sink nd. The energy consumed in forwarding the data via the forwarding node nf′ is calculated as Esf′d=2x0+x2+(d-x)2. Denote the difference of the energy consumption between the directional transmission and the data forwarding by F(x), i.e., F(x)=Esd-Esf′d=2d·x-2x2-x0, and we can have Esd>Esf′d iff d>(2x0)1/2.Figure 6
Transmitting the data from nodens to nd via node nf and nf′.If the forwarding node is not on the straight line between the sending node and the sink, say the forwarding nodenf in Figure 6, then the node energy consumed via data forwarding is calculated as Esfd′=2x0+l2+(d-x)2+(l2-x2), where l is the distance between node ns and nf; x is the horizontal projection of the distance between node ns and nf. By comparing the energy consumption of Esf′d and Esfd′, we can have the conclusion that the data forwarding can save energy more than transmitting the data along the straight line iff the condition l2<d·x is satisfied.In AFC, each cluster in the WirelessHART network is subdivided into several freeshape zones. The CNs collect the data from other CMs inside of their zones and forward it to the CH. Since the CMs inside of the freeshape zones only have to communicate with the CNs and the distance from CMs to CNs is usually shorter than that of the CH, the energy consumption in transmitting the data can be reduced significantly. SupposeC=(n1,n2…n|C|) is the set of M nodes in one of the clusters and nch is the elected CH. CN=(cn1,cn2…cnN) is the set of N CNs in the cluster, where the combination of each CN’s transmission should cover the whole area of the cluster. Denote the number of CMs in each CN’s coverage by cn1,cn2,⋯cnN, and the number of nodes inside of the CH’s coverage is |ch|. Then, the energy consumption in AFC can be calculated as(2)EAFC=∑i=1Nx0+dcni2+Ech+Ecn1…+EcnN=∑i=1Nx0+dcni2+∑j=1chx0+dchj2…+∑l=1cn1x0+dcnl2+∑k=1cnNx0+dcnk2where dcni is the distance from the CN cni to the CH; Ecni is the energy consumed in transmitting data from each CM inside of cni’s coverage to cni; dchj is the distance from each node inside of the CH’s coverage to the CH; dcnj is the distance from each CM inside of cni’s coverage to cni.Meanwhile, the energy consumption in the HEED based algorithm can be calculated as(3)EHEED=∑i=1Mx0+dcmi2where dcmi is the distance from the CM cmi to the CH.To compare the energy consumption inEAFC and EHEED, we spilt the energy consumption into three parts: (1)the energy consumed by the CNs: since the CNs in AFC can also be regarded as general sensor nodes in the HEED based algorithm, the energy consumed by the CNs in AFC, i.e., ∑i=1N‍(x0+dcni2), must have been included and also be equal to that in EHEED; (2)the energy consumed by the nodes inside of the CH’s coverage: since both the HEED based algorithm and AFC have the same CH, e.g., the coverage, the transmission range, the number of nodes inside of the coverage, etc., the energy consumed by the nodes inside of the CH’s coverage in AFC is the same as that in the HEED based algorithm, that is, ∑i=1nm‍(x0+dchj2); (3)the energy consumed by the nodes inside of each CM’s coverage: for each node that is outside of CH’s coverage, the distance to the CN cni is shorter than that to the CH, i.e., dcni<dchi. According to the model of energy consumption in Section 3, it can be seen that the energy consumption in transmitting data from each CM inside of cni’s coverage is less than that of the HEED based algorithm. In summary, compared to the HEED based algorithm, AFC can reduce the energy consumption in transmitting the data, i.e., EAFC<EHEED.


## 7. Simulation and Analysis

To evaluate the performance of our proposed scheme, we run the simulations in Contiki 3.0 based on Cooja. Cooja is a Contiki network simulator capable of inspecting the behaviour of sensor nodes in wireless networks, e.g., the energy consumption, network lifetime, reception rate, etc. To simulate the energy consumption of sensor nodes in the real-world industrial environment, we use the Init/factory dataset to configure the wireless communication links in WirelessHARTs [18]. Since Init/factory contains a group of data sets that record the channel gains with multiple distances in a factory environment, we can assign these data sets of channel gains in Init/factory to each link in our simulation regarding the distance between the sensor nodes. Thereby, we can acquire the qualities of wireless links in the real-world WirelessHART networks.As shown in Figure7, we set the RoI of WirelessHART network as a circle area with the radius of 500 meters. A gateway in the WirelessHART network acts as the sink for convergecasting the data packets, which is located at the centre of the RoI. A set of 500 sensor nodes are randomly distributed in the WirelessHART networks, and the radius of each sensor node’s transmission range is set as 50 meters initially. Each node is embedded with a battery with the capacity of 1J. According to the experiments conducted in [19], we set x0=55×10-9J, ε=520×10-12Jm-2, α=2. In order to make an efficient convergecast of data packets in the WirelessHART networks, we set the duration in the phase of convergecasting as 40 times as the sum of the phase of fan-shaped clustering and adaptive subdividing. Since both the lifetime of the first dead node and the network lifetime highly depend on the slot length in the broadcast, e.g., the lifetime of the first dead node equals the product of slot length and its broadcast rounds, we use the number of broadcast rounds to indicate the lifetime of the first dead node and the network life, which helps to remove the impact of slot length.Figure 7
The number of broadcast rounds regarding the lifetime of first dead nodes and that of the network lifetime.Figure8 compares the number of broadcast rounds regarding the lifetime of the first dead node and the network lifetime in different routing protocols, where the number of CH is set as 6 in the WirelessHART network. The FLOODING based routing scheme has the shortest lifetime of the first dead node as most of the energy is consumed in forwarding the data blindly, and the nodes suffer from a fast speed in consuming the energy. The DIRECT based routing algorithm has a larger number of broadcast rounds in the lifetime of the first dead node, as the sensor nodes only have to convergecast its own data packets rather than forwarding other sensor nodes’ data packets. The HEED based algorithm has a much larger number of broadcast rounds in the lifetime of the first dead node due to the periodical election of CHs, where only the one with higher remaining energy will be elected. Putting it in another way, the nodes with high remaining energy will contribute to the data convergecasting, and once the remaining energy has dropped to a level that is lower than other sensor nodes, they will be replaced through the election of CH. Compared with the HEED based routing algorithm, AFC replaces the intercluster communications with the short intracluster communication through circular segmentation, where the path for data forwarding is much shorter. Therefore, it can improve the broadcast rounds in the lifetime of the first dead node by 37 percent and shows better energy consumption characteristics.Figure 8
The number of broadcast rounds regarding the lifetime of first dead nodes and that of the network lifetime.To evaluate the distribution of energy consumption in the WirelessHART network, we calculate the degree of energy imbalance for each algorithm. As shown in Figure9, AFC has the lowest degree of energy imbalance of 1.35%, and the reasons are twofold. First, it benefits from the periodical election of CHs, which gives a high priority to consuming the energy in the node that has more remaining energy in the batteries. Second, the subdivision inside of the cluster makes the nodes consume less energy in convergecasting the data. In fact, it is the CNs that convergecast the data packets, which consume less energy due to the short distance to the CH. HEED has a higher degree of energy imbalance of 6.49%, but it is still much lower than the DIRECT and the FLOODING based algorithms where the degrees of energy imbalance are 24.5% and 29.2%, respectively. This mainly results from the periodical election of CHs, which helps to balance the energy consumption as the one with more remaining energy will be elected as CH.Figure 9
The degree of energy imbalance in different schemes.Note that the radius of sensor nodes may impact the network lifetime. For instance, a small radius can cover fewer sensor nodes with a low coverage redundancy. However, most of the sensor nodes have to communicate with the sink directly, yielding a large energy consumption. Figure10(a) illustrates the relationship between the radius of sensor node, the coverage redundancy, and the network lifetime where no circle clustering is executed. Since each node sends the data to the CH directly, the network lifetime changes a little as the radius of the sensor node increases. However, the coverage redundancy increases sharply as the nodes tend to have a large overlapped area in their coverage. Figure 10(b) illustrates the relationship between the radius of sensor node, the coverage redundancy, and the network lifetime where the circle clustering is executed in the cluster. When the radius is small, the area of the cluster is not fully covered. In other words, the nodes have to communicate to the CH directly, which yields a short network lifetime. When the radius increases and the area of the cluster is fully covered, the node can send its data to the CN rather than communicating with the CH directly. Hence, the network lifetime increases due to the energy saving in the data convergecast. When the radius becomes large, the number of CNs decreases and most sensor nodes remain as CMs. This explains why the AFC can always maintain the coverage redundancy roughly unchanged, which helps to prolong the network lifetime with a low coverage redundancy.Figure 10
Relationship of the coverage redundancy, radius, and the network lifetime.
(a)
When the cluster is unsubdivided (b)
When the cluster is subdivided into freeshape zones


## 8. Conclusion

The energy saving and consumption balancing are two combined issues in the WirelessHART networks. Based on the structure of HEED, we have proposed an adaptive freeshape clustering protocol, namely, AFC, for energy saving and consumption balancing, where each fan-shaped cluster is subdivided into several freeshape zones. Since the CN takes charge of convergecasting the data, the sensor nodes do not have to communicate with the CH directly, which helps to reduce the energy consumption in the network. Meanwhile, the periodical election of CH helps to balance the distribution of energy consumption as the one with lower remaining energy in the battery will be replaced by other ones that have more remaining energy. The simulation results show that AFC can effectively reduce the energy consumption and extend the network lifetime with balanced energy consumption.



---

*Source: 2836981-2019-07-29.xml*