دانلود رایگان ترجمه مقاله HACH الگوریتم اکتشافی برای خوشه بندی پروتکل سلسله مراتبی (نشریه الزویر 2017)

HACH: الگوریتم اکتشافی برای خوشه بندی پروتکل سلسله مراتبی در شبکه حسگر بی سیم

HACH: Heuristic Algorithm for Clustering Hierarchy protocol in wireless sensor networks

Abstract

Wireless sensor networks (WSNs) require energy management protocols to efficiently use the energy supply constraints of battery-powered sensors to prolong its network lifetime. This paper proposes a novel Heuristic Algorithm for Clustering Hierarchy (HACH), which sequentially performs selection of inactive nodes and cluster head nodes at every round. Inactive node selection employs a stochastic sleep scheduling mechanism to determine the selection of nodes that can be put into sleep mode without adversely affecting network coverage. Also, the clustering algorithm uses a novel heuristic crossover operator to combine two different solutions to achieve an improved solution that enhances the distribution of cluster head nodes and coordinates energy consumption in WSNs. The proposed algorithm is evaluated via simulation experiments and compared with some existing algorithms. Our protocol shows improved performance in terms of extended lifetime and maintains favourable performances even under different energy heterogeneity settings.

1 Introduction

Recent progress in wireless communications and microelectronics have contributed to the development of sensor nodes that are agile, autonomous, self-aware and self-configurable. These sensor nodes are densely deployed throughout a spatial region in order to sense particular event or abnormal environmental conditions such as moisture, motion, heat, smoke, pressure, etc. in the form of data [1]. These sensors, when in large numbers, can be networked and deployed in remote and hostile environments enabling sustained wireless sensor network (WSN) connectivity. Hitherto WSNs have been used in many military and civil applications, for example, in target field imaging, event detection, weather monitoring, tactile and security observation scenarios [2]. Nevertheless, sensor node distribution and network longevity are constrained by energy supply and bandwidth requirements. These noted constraints mixed with the common deployment of large numbers of sensor nodes must be considered when a WSN network topology is to be deployed. The design of energy efficient scheme is a major challenge especially in the domain of routing, which is one of the key functions of the WSNs [3]. Therefore, inventive techniques which reduce or eliminate energy inadequacies that would normally shorten the lifetime of the network are necessary. In this paper, the authors present a method which balances energy consumption among sensor nodes to prolong WSN lifetime. Energy resourcefulness is uniquely obtained using two described mechanisms; firstly, cluster head (CH) selection using a generic algorithm (GA) is employed that ensures appropriately distributed nodes with higher energies will be selected as CHs. Secondly, a Boltzmann inspired selection mechanism was utilized to select nodes to send into sleep mode without causing an adverse effect on the coverage.

The commonest routing protocols deployed to address the challenges discussed above are generally categorised into two classes, namely flat and hierarchical. Flat protocols comprise the well-known Direct Transmission (DT) and Minimum Transmission Energy (MTE), which do not provide balanced sensor energy distributions in a WSN. The disadvantage of the MTE is that a remote sensor normally employs a relay sensor when transmitting data to/from the sink and this results in the relay sensor being the first node to die. In the DT protocol, the sink communicates directly with sensors and this results in the death of the remote sensor first. Consequently when creating WSNs, energy-efficient clustering protocols act as a pivotal factor for sensor lifetime extension. Generally, clustering protocols can perform better than flat protocols in terms of balancing energy consumption and network lifetime prolongation by employing data aggregation mechanisms [4,5]. In WSNs, there are three types of nodes considered: the cluster-head (CH), member node (MN) and sink node (SN). The member node manages sensing of the raw data and utilizes Time Domain Multiple Access (TDMA) scheduling to send the raw data to the CH. The CH must aggregate data received fromMNs and forward the aggregated data to the SN through single-hop or multi-hop. CH selection can be carried out by the sensors individually, by the SN or can be pre-implemented by the wireless network designer. Here, CH selection is performed by the SN due to the fact that the SN has sufficient energy and can perform multifaceted calculations. The problem of CH selection can be considered as an optimization issue where the methods have employed GA to solve. Here the authors define an objective function that evaluates the discrete solution and propose an innovative heuristic crossover which is enhanced by the knowledge of our problem.

In this paper, we present a new Heuristic Algorithm for Clustering Hierarchy (HACH) protocol that simultaneously performs sleeping scheduling and clustering of sensor nodes upon each round. For sleep scheduling operation, the authors have developed the stochastic selection of inactive nodes (SSIN). A protocol that imitates the Boltzmann selection process in GA was used to decrease the number of active nodes in each round by putting some nodes to sleep or into inactive mode so that energy could be conserved and network lifetime increased without harming coverage. We further developed the Heuristic-Crossover Enhanced Evolutionary Algorithm for Cluster Head Selection (HEECHS) protocol for the clustering operation. HEECHS uses the known information around the problem to develop a useful heuristic crossover that combines genetic material in a unique way to produce improved CH configuration. This method described has some parallels with optimization algorithms known as Memetic Algorithm (MAs). This algorithm is a type of stochastic global search heuristics in which Evolutionary Algorithm-based techniques are mixed with a local search technique to improve the quality of the solutions proposed by evolution [6]. Sleep scheduling and clustering algorithms work together to optimize network lifetime by harmonizing energy consumption amongst sensor nodes during the communication times. Energy consumption optimization is performed by selecting spatially distributed nodes with higher energy as CHs and additionally placing certain nodes into sleep mode without harming coverage. The HACH protocol proposed performs very well compared to protocols that use GA because it integrates knowledge of the problem into GA crossover operator.

The rest of the paper is organised as follows. Section 2 presents related work on energy conservation techniques and clustering protocols in the area of energy-efficient wireless sensor networks. Section 3 describes the network and radio model assumptions that underlie the protocol presented. In Section 4 the authors describe our proposed algorithm under three pivotal operational phases, those being the sleep scheduling mechanism, clustering algorithm and the energy consumption calculation. Section 5 presents our experimental set-up, performance procedures, results and discussion. Finally, Section 6 provided our conclusion.