Rethinking Cluster-based Routing in Wireless Sensor Networks

Dimitris Kanellopoulos*

Department of Mathematics, University of Patras, Patras, GR 26500, Greece

Corresponding Author E-mail: d_kan2006@yahoo.gr

DOI : http://dx.doi.org/10.13005/ojcst12.01.02

ABSTRACT:

A wireless sensor network (WSN) can be employed in many application areas such as traffic control and industrial automation. In WSNs, clustering achieves energy efficiency and scalable performance. A cluster is formed by several sensors nodes, and one of them is elected as cluster-head (CH). A CH collects information from the cluster members and sends aggregated sensed data to the base station (BS) or another CH. The main task of a routing protocol in a WSN is to forward these sensed data to the BS. This paper analyses the advantages of cluster-based routing protocols vs. flat routing protocols in WSNs.

KEYWORDS: Clustering; Clustering Routing Algorithms; Energy Efficiency; Routing Protocols; Wireless Sensor Networks

Copy the following to cite this article: Kanellopoulos D. Rethinking Cluster-based Routing in Wireless Sensor Networks. Orient.J. Comp. Sci. and Technol;12(1).

Copy the following to cite this URL: Kanellopoulos D. Rethinking Cluster-based Routing in Wireless Sensor Networks. Orient.J. Comp. Sci. and Technol;12(1). Available from: https://bit.ly/2DnaNP9

Wireless sensor networks (WSNs) can be employed in many application areas for various civilian and military scenarios. The main reason is that a WSN does not require a pre-defined network infrastructure and can be deployed on an ad-hoc basis. A sensor node in a WSN¹ senses the sensing field and gathers important data such as temperature and detection of enemy movement. Next, this data must be processed and sent to the base station (BS) for taking critical decisions. A BS is a piece of equipment that has more energy capacity, processing power, and memory than usual sensor nodes. A sensor node contains wireless transmitters or receiver antennas and is constrained in processing capability, power supply, and transmission bandwidth. As the sensor nodes are randomly deployed in the sensing field, their batteries are not recharged. As a result, prolonging the life span of a WSN is an important problem. To solve this problem, many cluster-based routing techniques^2,3 have been proposed.

Flat Routing vs. Hierarchical Routing in WSNs

Routing in a WSN can be flat or hierarchical (or cluster-based) routing.

Flat Routing

In a WSN with a flat network structure, all nodes operate similarly and perform the same tasks. Particularly, for the transmission of data in a flat WSN, the flooding technique is used (viz., the data are transferred hop-by-hop). In small-scale WSNs, flat routing protocols are reasonably efficient. On the contrary, in large-scale WSNs, flat routing schemes are useless because the resources in such networks are scarce, and all sensor nodes process additional sensing data and demand more bandwidth. Typical examples of flat routing protocols in WSNs are: Flooding and Gossiping, Sensor Protocols for Information via Negotiation (SPIN), Greedy Perimeter Stateless Routing (GPSR) and Rumor.

Hierarchical or cluster-based routing: In a hierarchical topology (Fig. 1), sensor nodes are formed into Clusters consistent with specific application requirements.

Figure 1: Hierarchical Network Topology4 Click here to View figure

Sensor nodes may perform diverse tasks in the WSN. For example, a sensor node may sense temperature, while another sensor node may sense the motion of an object. One of the cluster members is elected as Cluster-head (CH). A CH must have higher energy than a cluster member because its main task is to collect information from the cluster members and send these aggregated data to the BS or to another CH using the cluster-based routing protocol. Typical examples of cluster-based routing schemes in WSNs are: Low-energy Adaptive Clustering Hierarchy (LEACH), Two-Level Hierarchy LEACH (TL-LEACH), LEACH-ERE, and Power-Efficient Gathering in Sensor Information Systems (PEGASIS).

Compared with flat routing technology, the cluster-based routing protocols have critical advantages.⁵

Advantages of Cluster-Based Routing Protocols

More Scalability

The hierarchical network topology of clusters permits the route set up a process within each cluster to be a local process. That implies that each sensor node (within the cluster) keeps a Routing Table that has a small size due to this locality.^6,7 The hierarchical network topology is more scalable than the flat network topology. Moreover, it can sense more directly the sensing field.¹

Data Aggregation/Fusion

It is an important task in a WSN because sensor nodes generate redundant data. Particularly, it is the process of aggregating data from several nodes to eliminate redundant transmission and provide fused data to the BS. Obviously, eliminating redundant transmissions directs to energy savings.⁸ In the clustering data aggregation method,⁹ each CH aggregates the collected data and transmits the fused data to the BS. It is noteworthy that aggregated data are transmitted by using the multi-hopping technique through other CHs. This produces major energy savings.¹⁰

Less Load

As it was mentioned earlier, to eliminate redundant data transmissions in the network, the data aggregation/fusion process is performed at the CHs. This process combines data from different sensor nodes (sources) and offers a rich and multi-dimensional view of the targets being monitored.¹¹ Many cluster-based routing schemes with data aggregation capabilities must adopt suitable cluster formation techniques. Conclusively, the data aggregation/fusion process helps to radically reduce the transmission of data and save energy.

Less Energy Consumption

As only CHs perform inter-cluster communications, a small number of sensor nodes (CHs) carry out the task of long-distance communications. Consequently, the hierarchical network topology of clusters brings out less energy consumption for the entire network.

More Robustness

The network topology of clustering is more robust and can respond efficiently to various network changes, such as sensors nodes mobility; unpredicted failures; and sudden addition of cluster members. Within any cluster, a cluster-based routing scheme can handle these changes. As a result, the entire network is more robust and more controllable. In cluster-based routing protocols (e.g., LEACH) communication between CHs and BS is divided into rounds. The role of the CH can be assigned randomly to any cluster member per round. Every round has two states: (1) setup state; and (2) steady state. With such CH assignment, the malfunction (or failure) of any sensor node can be avoided.

Collision Avoidance

The multi-hop flat model has low efficiency in the usage of channel bandwidth because all sensor nodes access and share the wireless channel equally. On the contrary, in the multi-hop clustering model, data communications between sensor nodes include two modes:

        Intra-cluster communication for data collection; and
Inter-cluster communication for data transmissions.

In the multi-hop clustering model, a portion of channel bandwidth can be allocated rationally to each cluster in order to reduce collisions between the clusters, and if it is required this portion can be reused by other clusters.¹² Consequently, the multi-hop clustering model is appropriate for large-scale WSNs.

Latency Reduction

The inter-cluster communication assists to avoid collisions between the sensor nodes, because only the CHs participate in such communications. As a result, the number of hops from the data source to the BS is reduced, and thus the latency is reduced.

Load Balancing

An effective load balancing scheme can prolong the network lifetime in a WSN. Multi-path routing is a method that can achieve load balancing. Load balancing is mainly related to the distribution of sensor nodes among the clusters. Generally, the construction of equal-sized clusters is adopted for prolonging the network lifetime as this prevents the early energy depletion of CHs.

Fault-Tolerance

The sensor nodes in a WSN suffer from energy exhaustion, transmission errors, hardware malfunction, malicious attacks etc. Consequently, a WSN is prone to failures, and effective fault-tolerant approaches¹³ are required in order to avoid the loss of sensitive data from critical (for the application) sensor nodes. Re-clustering is the simplest method to recover from a cluster failure, but it usually disorders the in-progress operation of the cluster. The assignment of CH backup is a feasible recovery scheme from a CH failure.

Guarantee of Connectivity

Each sensor node must have the guarantee that it can connect to its next hop node (along the path). It is noteworthy that sensor nodes that cannot communicate with any other sensor node will get isolated. Moreover, their data can never be transmitted to the BS. The guarantee of connectivity determines mainly whether or not the data are successfully delivered to the BS. This guarantee is an essential goal of any cluster-based routing protocol in WSNs.¹¹ A typical example is when a designated fusion node has to gather particular information relating to all the sensor nodes in a cluster-based routing protocol.¹⁴

Energy Consumption Balancing (Hole Avoidance)

In a hierarchical WSN, each node transmits self-generated and relayed traffic data. Despite of MAC protocols, the sensor nodes which are near to the BS transmit more packets to the BS, and they prevent the remote nodes from sending their data packets to the BS.¹⁵ These remote nodes have enough remaining energy but they are isolated. As a result, the sensor nodes near to the BS leave an “energy hole” near to the BS.^{16, 17} Actually, the whole network is partitioned in two parts. In order to avoid this problem, three types of energy consumption balancing mechanisms have been proposed: (1) node deployment; (2) load balancing; and (3) energy mapping and assigning.¹⁸ Especially, uneven clustering is one of the methods of load balancing. In uneven clustering, a smaller cluster radius near to the sink and a larger cluster radius away from the sink are defined respectively. In this way, the energy consumption of processing data in inter-cluster is less for cluster having a smaller radius. As a result, the remote nodes use more of their energy to relay their data.¹⁹ However, it is difficult to analyze the optimization of cluster radius theoretically.²⁰

Maximizing of the Network Lifetime

In order to maximize the network lifetime, we must minimize the energy consumption of CHs. We remind that the energy consumed during communication mainly depends on the distance between the sending and the receiving nodes. By shortening the communication distances between sensors, the CH can protect itself and the other cluster members from fast battery drain. Such shortening saves energy while CHs receiving data. Obviously, a sensor node that is close to most of the sensor nodes (in the cluster) should be prone to be a CH. It is noteworthy that routes, composed of nodes with higher energy resources, must be selected in order to prolong the network lifetime in inter-cluster communications.

Conclusion

WSNs can be employed in many civilian and military application scenarios. The design and development of effective routing protocols for WSNs is a challenge for the research community. Many cluster-based routing protocols have been proposed that can match the required properties of a hierarchical WSN. In this editorial article, we have presented the main advantages of cluster-based routing protocols in WSNs. In the design of cluster-based routing protocols for real-time application scenarios (e.g., battle-target tracking), various quality of service (QoS) metrics must be considered. However, existing cluster-based routing protocols in WSNs mostly consider only on how to increase energy efficiency. However, they to provide QoS guarantees. We remark that some QoS requirements, such as the bounded end-to-end delay, can violate in practice the design assumptions of many of the existing cluster-based routing protocols.

References

1. Seah W., & Tan Y. (Eds) (2010) Sustainable Wireless Sensor Networks. InTech Open Access Publisher: Rijeka, Croatia, 2010.
2. Anisi M.H., Abdul-Salaam G., Idris M.Y.I., Wahab A.W.A., & Ahmedy I. (2017) Energy harvesting and battery power based routing in wireless sensor networks. Wireless Networks, 23(1), 249-266.
   CrossRef
3. Pantazis N.A., Nikolidakis S.A., & Vergados, D.D. (2013) Energy efficient routing protocols in wireless sensor networks: A survey. IEEE Communications Surveys & Tutorials, 15(2), 551–591.
   CrossRef
4. Popovic G., Djukanovic G., & Kanellopoulos D. (2018) Cluster head relocation based on the selfish herd hypothesis for prolonging the life span of wireless sensor networks. Electronics, 7(12), 403.
   CrossRef
5. Liu X. (2012) A survey on clustering routing protocols in wireless sensor networks. Sensors, 12(8), 11113-11153.
   CrossRef
6. Abbasi A.A., & Younis M. (2007) A survey on clustering algorithms for wireless sensor networks. Computer Communications, 30(14-15), 2826-2841.
   CrossRef
7. Akkaya K., & Younis M. (2005) A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3(3), 325-349.
   CrossRef
8. Rajagopalan R., & Varshney P.K. (2006) Data-aggregation techniques in sensor networks: A survey. IEEE Communications Surveys & Tutorials, 8(4), 48–63.
   CrossRef
9. Yue J., Zhang W., Xiao W., Tang D., & Tang J. (2012) Energy efficient and balanced cluster-based data aggregation algorithm for wireless sensor networks. Procedia Engineering, 29, 2009–2015.
   CrossRef
10. Ozdemir S., & Xiao Y. (2009) Secure data aggregation in wireless sensor networks: A comprehensive overview. Computer Networks, 53(12), 2022–2037.
    CrossRef
11. Li C., Zhang H., Hao B., & Li J. (2011) A survey on routing protocols for large-scale wireless sensor networks. Sensors, 11(4), 3498-3526.
    CrossRef
12. Lee S.H., Lee S., Song H., & Lee H.S. (2011) Gradual cluster head election for high network connectivity in large-scale sensor networks. In 13th International Conference on Advanced Communication Technology (ICACT2011) (pp. 168-172). IEEE.
13. Chitnis L., Dobra A., & Ranka S. (2009) Fault-tolerant aggregation in heterogeneous sensor networks. Journal of Parallel and Distributed Computing, 69(2), 210-219.
    CrossRef
14. Freris N.M., Kowshik H., & Kumar P.R. (2010) Fundamentals of large sensor networks: Connectivity, capacity, clocks, and computation. Proceedings of the IEEE, 98(11), 1828-1846.
    CrossRef
15. Li J., & Mohapatra P. (2007) Analytical modelling and mitigation techniques for the energy hole problem in sensor networks. Pervasive and Mobile Computing, 3(3), 233-254.
    CrossRef
16. Tran-Quang V., & Miyoshi T. (2010) A transmission range adjustment algorithm to avoid energy holes in wireless sensor networks. In Proc. of 2010 8th Asia-Pacific Symposium on Information and Telecommunication Technologies, Kuching, Malaysia, 15–18 June 2010; pp. 15–18.
17. Liu X. (2016) A novel transmission range adjustment strategy for energy hole avoiding in wireless sensor networks. Journal of Network and Computer Applications, 67, 43-52.
    CrossRef
18. Ishmanov F., Malik A.S., & Kim S.W. (2011) Energy consumption balancing (ECB) issues and mechanisms in wireless sensor networks (WSNs): A comprehensive overview. European Transactions on Telecommunications, 22(4), 151-167.
    CrossRef
19. Liu A. F., Zhang P. H., & Chen Z.G. (2011) Theoretical analysis of the lifetime and energy hole in cluster-based wireless sensor networks. Journal of Parallel and Distributed Computing, 71(10), 1327-1355.
    CrossRef
20. Chen G., Li C., Ye M., & Wu J. (2009) An unequal cluster-based routing protocol in wireless sensor networks. Wireless Networks, 15(2), 193-207.
    CrossRef

---

This work is licensed under a Creative Commons Attribution 4.0 International License.