Abstract: Clustering routing protocols are more energy efficient than the other types of routing protocols for Wireless Sensor Networks (WSN) which also improve lifetime, as well as scalability of the network. Energy Aware Distributed Clustering (EADC) is one of the cluster-based routing protocols proposed for network with non-uniform node distribution. The authors introduced a distant threshold to select the nodes which should communicate with Base Station (BS) directly in multi-hop communication. The value of this parameter has a significant impact on the energy consumption and lifetime of the network. However, the presented value for this parameter is not adequate. Thus, in this study a distance threshold analysis is performed on EADC in order to study the impact of different values of threshold parameter on the network. In conclusion, an appropriate range for distance threshold is introduced.
INTRODUCTION
Wireless Sensor Network (WSN) is a special kind of ad-hoc network which consists of hundred to thousand sensor nodes. These sensor nodes are small in size, low cost, low power and low memory. They are capable of measuring a property form the environment in addition to processing and transmitting data. As discussed by Ferng et al. (2012), due to the task-oriented feature, WSN is more adequate for environment monitoring applications. However, it is also used in various applications such as disaster relief operations, agriculture, facility management, healthcare, biodiversity mapping and etc. (Heinzelman et al., 2000; Yick et al., 2008; Liu, 2012). Since, the battery of the sensors cannot be replaced after the deployment, the energy resources must be managed to prolong the network lifetime as well as fulfilling the requirements of the network.
As stated by Roseline and Sumath (2011), the protocols should be designed well in order to use effectively the limited power of the nodes. Researchers have proved that hierarchical (i.e., cluster-based) routing protocols have a higher utilization rate and more suitable for WSN among different categories of routing protocols based on the network organization. Since, it extends the lifetime and scalability of the network (Heinzelman et al., 2000; Younis and Fahmy, 2004; Yu et al., 2012). In cluster-based routing protocols, the monitoring field is divided into multiple clusters. In each cluster, one node is elected as a Cluster Head (CH) and responsible to gather the data from its cluster members (CMs). CMs are in charge of gather the information from environment. Once the CMs send data to their selected CH, it performs data aggregation to omit the redundant data and transmits it to Base Station (BS).
Cluster-based routing protocols have tendency to distribute CHs uniformly over the network with uniform node deployment to balance the energy consumption of the nodes and extend the network lifetime. However, the mechanisms used to balance the energy consumption of the nodes in the network with uniform node distribution are not always effective for network with non-uniform node deployment. Non-uniform node distribution makes cluster-based routing protocols less efficient (Shin et al., 2011; Yu et al., 2012).
Yu et al. (2012) proposed a cluster-based routing protocol for the network with non-uniform node distribution in order to solve the problem of the imbalanced energy consumption among the nodes. This routing protocol consists of an energy-aware clustering algorithm (i.e., EADC) and a cluster-based routing algorithm. EADC constructs clusters of equal sizes using competition range to balance the energy consumption of Cms. While, in cluster-based routing algorithm, intra-cluster and inter-cluster energy consumption of the CHs are adjusted. Inter-cluster communication is performed in multi-hop. Thus, some of the CHs should be chosen in order to communicate with the BS directly. Yu et al. (2012) introduced a threshold distance “DIST_TH” to choose these nodes. If the distance of a CH to the BS is less than the DIST_TH, it will communicate with BS directly. Otherwise, it will communicate with BS in a multi-hop manner. The value of DIST_TH has a significant impact on this routing protocol. If the chosen DIST_TH is less than the distance between the monitoring field and the BS, none of the CHs is able to communicate with the BS. Therefore, the data cannot be sent to the BS. However, if the distance is larger than the minimum distance between the field and the BS but still is considered as small, there may be no CH or small number of the CHs to communicate with the BS. This results in early death of these CHs or “hot spot” problem. On the other hand, if a large DIST_TH or larger than the maximum value between CHs and field is chosen, all the CHs will communicate with the BS in a single hop manner which is not adequate for WSN. Therefore, DIST_TH is an important value which should be controlled in a suitable range. However, the presented value for this parameter in EADC is not adequate.
This study aims to provide a DIST_TH analysis over EADC in order to find out an appropriate range for this routing protocol.
RELATED WORK
Low Energy Adaptive clustering Hierarchy (LEACH) (Heinzelman et al., 2000), is one of the first cluster-based routing protocol. Each node independently, elects itself as a CH with a predefined probability. The CHs collect the data from their members, perform data aggregation and send the data to BS directly. The role of CH is rotated among the nodes periodically, in order to distribute energy consumption evenly in the network. Although LEACH is simple and does not require large communication overhead, it does not consider the residual energy of nodes in CH selection. In addition, it is not adequate for the large networks. Therefore, in order to improve the performance of LEACH and solve its problems, several clustering routing protocols were proposed (Younis and Fahmy, 2004; Lindsey et al., 2002; Heinzelman et al., 2002).
Kumar et al. (2009), proposed Energy Efficient Heterogeneous Clustered (EEHC) routing protocol. EEHC considers a network with the heterogeneous nodes in terms of energy resources. EEHC elects CHs in a distributed fashion. Election is based on weighted election probabilities of each node according to the residual energy. However, it performs inter-cluster communication in single hop and does not consider initial energy of the nodes.
One of the clustering routing protocols which can gain a good CH distribution is Energy-Aware Data Gathering (EADEEG) (Liu et al., 2007). EADEEG selects the CHs based on the residual energy of the nodes and the average residual energy of its neighbors. Although it improves the network lifetime, there exists the problem of “isolated points” in EADEGG.
Yu et al. (2011) proposed Energy Aware Distributed Unequal Clustering (EADUC) routing protocol in order to solve the problem of “isolate points” in EADEGG. EADUC considers the heterogeneity of the nodes in terms of energy. Furthermore, it addressed the problem of “hot spot” by making clusters in unequal sizes. This phenomenon happens due to imbalance energy consumption of the nodes which causes some nodes die prematurely.
A novel routing protocol, Arranging Cluster sizes and Transmission ranges (ACT) was proposed by Lai et al. (2012). In ACT, network topology is separated into multiple levels. It reduces the size of the clusters near to BS in order to overcome the problem of “energy hole”. Furthermore, in order to avoid cluster reconfiguration in each round, a cluster maintenance phase was proposed. This routing protocol also utilize cross over transmissions in order to prolong the network lifetime.
All the above protocols consider the networks with uniform or random node deployment. Soro and Heinzelman (2009) proposed Coverage Preservation Clustering Protocol (CPCP) routing protocol which considers the non-uniform node distribution. Although, the protocol uses good CHs selection techniques, it main objective is coverage preservation. Therefore, the protocol does not consider network lifetime and balancing energy expenditure (Yu et al., 2012).
EADC ROUTING PROTOCOL
This cluster based routing protocol, consists of an energy aware clustering algorithm and a cluster-based routing algorithm. EADC starts to make clusters in equal sizes. It uses the competition range to perform this step. While, in the routing algorithm, the CHs choose next hop with more remaining energy, less cluster members and not further away from BS as the relay node which results in balancing the energy consumption among CHs.
EADC Algorithm: The energy aware clustering algorithm consists of three phases: information collection phase with the duration of T1; cluster head competition phase with the duration of T2; cluster formation phase whose duration is T3. The details about these phases are discussed in the following sections.
Information collection phase: During the period of T1, each node broadcasts a “Node_Msg”. This message consists of two values which are the node ID and the residual energy of the node within the radio range r. At the same time, each node receives “Node_Msg” messages from its neighbors. Then each node starts to calculate the average residual energy of its neighbors Eia using the following Eq. 1:
| (1) |
where, Ejr is the residual energy Sj (one neighbor node of Si) and D is the number of the neighbors of Si. Each node using the Eq. 2 in order to calculate its waiting time for broadcasting “Head_Msg” messages:
| (2) |
where, ti is waiting time of Si, Eir is residual energy of Si and Vr is a real value uniformly distributed in [0.9, 1] which is introduced to reduce the probability that two nodes send Head_Msg simultaneously.
Cluster head competition phase: When T1 has expired, EADC starts the next phase with the period of T2. In this phase, if the sensor node does not receive any “Head_Msg”, it will broadcast the “Head_Msg” within the radio range, RC to advertise. Otherwise, it gives up the competition.
Cluster formation phase: As T2 expires; cluster formation phase will be started with the duration of T3. In this phase, each non-CH node selects the CH based on the signal strength. They will choose the nearest CH and send the “Join_Msg”. The values of this control message are the ID and the residual energy of the node. The cluster heads create a node-scheduling list based on the received “Join_Msg” messages. Finally, the CHs create and send the “schedule_Msg” message to tell the nodes when to send the data and in other times, they can be in the sleep mode to save energy. After this phase, the entire process of clustering algorithm is completed.
Cluster-based routing algorithm: Duration of this phase is T4 in which a routing tree based on the CHs is constructed, since by using multi-hop communication, the energy consumption of the network will be reduced. The energy consumption of the CHs in multi hop communication is divided into intra-cluster energy consumption and inter-cluster energy consumption. Since, CHs in EADC are distributed uniformly in the network with equal cluster size, the energy consumption of Cms are balanced. However, due to non-uniform node distribution, the load is still imbalanced among CHs. Yu et al. (2012) adjust the ratio of the two parts of the energy consumption to balance energy expenditure. Among all the CHs, several nodes should be chosen to communicate with the BS directly. They will be chosen according their distance to the BS. The authors introduced a threshold distance “DIST_TH”. If the distance between CHs to the BS is less than DIST_TH, they will communicate with the BS in the single hop manner. Otherwise, they will communicate with the BS in a multi hop routing approach.
At the beginning of this phase, each CH broadcasts a “Route_MSG” message within the radius range Rr. Rr is twice larger than its RC in order to maintain the connectivity of the network. This control message contains the values of residual energy, number of cluster members and distance of node to the BS itself. If the distance of CH to the node is less than DIST_TH it will set the BS as its next hop. Otherwise, according to the received “Route_MSG” messages, it will chose a CH with higher residual energy, smaller number of members and no further away from BS as the next hop. The Eq. 3 is calculation of “relay” when CH Si chooses CH Sj as the next hop:
| (3) |
where, Ejr is the residual energy of CH Sj, Emax is the maximum initial energy of nodes in the network. Sj(cm-num) is the number of CMs of Sj and α is a real value uniformly distributed in [0, 1].
| Fig. 1: | EADC network topology |
It is obvious from Eq. 3 that the CH with higher residual energy and fewer cluster members will have a larger “relay”. A CH with a highest “relay” and closer to BS will be selected as the next hop in EADC. If there is more than one CH that has the same largest relay value, the one which has a longer distance to the BS, will be chosen. The reason is to avoid early death of the CH close to the BS due to much data forwarding.
Data transmission phase: Data transmission phase is consists of two sub-phases: Intra-cluster communication and Inter-cluster communication. In intra-cluster communication phase, CMs gather the data form the environment and send them in the allocated time slot to CH directly. Finally, in inter-cluster communication phase, CHs receive the data from the CMs, perform data aggregation and send the aggregated data to the next hop nodes. It should be mentioned that the CHs forward other nodes data without performing data aggregation since the data are not correlated. Figure 1 shows the topology of the EADC.
SIMULATION AND RESULTS
In this section, the performance of EADC based on the DIST_TH parameter is evaluated. A Discrete Event Simulation (DES) in a purpose language C# was developed in order to perform the simulation.
| Table 1: | Parameters of simulation |
The simulations were conducted for two scenarios as follows:
| Scenario 1: | 100 nodes are deployed over an area of 200x200 m2 randomly. In this case, the locations of the sensor nodes are selected randomly |
| Scenario 2: | 100 nodes are deployed over an area of 200x200 m2 non-uniformly. In this case, the sensor nodes are more grouped together in certain parts of the network. |
Every simulation result is the average of 30 independent experiments. The parameters of the simulation are listed in Table 1.
In EADC (Yu et al., 2012), value of the DIST_TH is set as 80 meter. However, this value is not adequate in different networks with random and non-uniform node deployment. In order to analyze the different values of DIST_TH, we set different values between 80 and 270 m and run the protocol to examine whether the network is connected to BS or not. Different values of DIST_TH, in 30 randomly selected experiments, for scenario1 and 2, is shown in Fig. 2.
| Fig. 2(a-b): | Different values of DIST_TH |
As shown in this figure when the value of DIST_TH is set between 80 and 140 m, it may happen than no CH can communicate with BS. Therefore, the data cannot be transmitted to BS and the network will be unavailable. However, when the value of DIST_TH is set more than 140 meter, at least one CH can communicate with BS and perform data transmission.
As discussed in pervious sections, the number of CHs which can communicate with BS directly, has a significant impact on the network lifetime. If the value of DIST_TH is small, small number of CH will be able to forward the load to BS. Thus, these nodes will die soon. In addition, if the value of DIST_TH is too large, all the CHs will communicate with BS directly. Consequently, the CHs that are further away from BS will lose a significant amount of energy and die early. In the two scenarios, we set the RC = 100; therefore the expected number of CHs is 4. Figure 3 shows the number of CH whose distance to BS is less than the threshold, where the DIST_TH is set between 140 and 270 m to make sure that the network is connected to the BS. We run the protocol in 30 different experiments for each values of DIST_TH to identify the number of CH which can communicate with BS directly.
As shown in Fig. 3, in scenarios 1, when DIST_TH is set as 140 and 150, the number of CHs which transmit data directly to BS, is either 1 or 2. In the case, where DIST_TH =160, the number of selected CH is between 1 and 3. In addition, the number of CHs will be either 2 or 3, where DIST_TH is set to 170-190. Moreover, in the experiments which the value of the threshold is set between 200 and 240, the number of CHs is between 2 and 4. Finally, the worst case happens when DIST_TH is set to 250-270, where all the CHs are in direct communication with the BS.
While in scenario 2, when DIST_TH is set as either 140 or 150, the number of selected CHs is 1 or 2. Moreover, in the case, where DIST_TH = 160, the number of CH which transmit data directly to BS is between 1 and 3. In addition, when DIST_TH is set between 170 and 220, the number of CHs which identify the BS as the next hop, is either 2 or 3. In addition, the number of CHs varies between 2 and 4, where this threshold is set between 230 and 240. In the cases that DIST_TH is in range of 250-260, the number of CHs is 3 and 4. Furthermore, all the CHs will communicate with BS directly, when DIST_TH = 270.
Consequently, when the DIST_TH is set between 140 and 160, the number of CH in the direct communication with BS is 2 frequently and appropriate for the network which the total number of CH is 4.
| Fig. 3(a-b): | No. of CHs communicate directly with BS |
CONCLUSION
In this study, we performed a distant threshold analysis on EADC, an energy efficient cluster-based routing protocol for network with non-uniform node distribution. In EADC, DIST_TH variable is used to identify the CHs which should communicate directly with the BS. Therefore, this parameter plays an important role in this routing protocol. Since, small values may result in unavailable network and too large values will result in wastage of the limited resources of the network. Therefore, the value of DIST_TH should be controlled properly. In this study, we investigate the impact of different DIST_TH values on EADC. In addition, an appropriate range of DIST_TH is proposed for two different scenarios in which the nodes are scattered randomly and non-uniformly in the network. In our future work, we will try to find a solution in order to determine an optimal value for “DIST_TH” parameter.