黄河科技学院毕业论文（文献翻译） 第10 页
1 Introduction
Wireless sensor networks (WSN) have recently attracted interest for potential application in future ubiquitous computing systems. Due to limited and irreplaceable energy of sensors, the energy efficiency becomes one of the most challenging tasks for WSN design .Besides, coverage is another critical measure of network QoS offered by a WSN. It reflects how well an area is monitored or tracked by sensors .
For the initial reason of saving energy, a WSN is broken down into several clusters to reduce communication overhead, and then save energy consumption as in Fig. 1. Close nodes group themselves into local clusters with one node acting as cluster-head.
The cluster-head collects data from other cluster nodes and send aggregrated data to the base station (BS). Most of existing research on cluster-head selection is only based on energy consumption. Low-Energy Adaptive Clustering Hierarchy (LEACH) is a cluster-based protocol that uses randomized rotation of cluster-heads to distribute energy dissipation evenly throughout the sensors. Instead of randomly choosing the cluster-head like in LEACH, the HYENAS system in takes several parameters into consideration including node location and remaining energy. Though these approaches perform much better with regard to reducing energy consumption, they do not ensure to preserve the network coverage. On the other hand, there are also studies on coverage preservation in WSN. They show the concept and importance of this metric; however, their cluster-head selection methods are only based on coverage metric rather than integrate this with energy factor.
黄河科技学院毕业论文（文献翻译） 第11 页
Fig. 1.1Black nodes are cluster-heads. White nodes are ordinary cluster nodes For integration of coverage preservation and energy efficiency in cluster-based WSN, we propose a Coverage and Energy Aware Cluster-Head Selection (CEACHS) Algorithm. The main contribution of our paper is suggesting a method to select cluster-heads by taking advantage of nodes’ characteristic and especially their coverage cost metric. By applying the proposed CEACHS, we can modify HYENAS system in order to achieve the best sensing coverage and energy efficiency. Simulation results prove that the proposed approach consistently outperforms LEACH and HYENAS in terms of not only extending network lifetime by over 11%, but also enlarging total network coverage by over 20% from the middle phase of the network lifetime.
The rest of the paper is organized as follows. Section 2 is a brief description of the state-of-art work including LEACH, HYENAS and coverage cost metric. In Section 3, we present the overview and details of our algorithm. Section 4 is a discussion of the simulation and its results and we concludes our work.
黄河科技学院毕业论文（文献翻译） 第12 页
2 Related Work
2.1 Low-Energy Adaptive Clustering Hierarchy (LEACH)
LEACH is a self-organizing, adaptive clustering protocol. In LEACH, the nodes organize themselves into local clusters with one node acting as the cluster-head. At each round, every node m is assigned a random number X between 0 and 1. If X is less than a predefined threshold T (m), node m will be selected as a cluster-head node at the current round. The threshold T(m) is set to
p?,?T(m)??1-p??rmod(1/p)??0?n?Gotherwise (1)
Where p is the desired ratio of cluster-heads, λ is the current round and G is the set of nodes each of which has not acted as a cluster-head yet within a period of 1/p round.
These cluster-head nodes broadcast their status to the other sensors in the network. Each sensor determines which cluster it wishes to join by choosing the cluster-head that requires the minimum communication energy. Once all are organized into clusters, each cluster-head creates a schedule for the nodes in its cluster. Once the cluster-head has all the data of nodes in its cluster, the cluster- head node aggregates the data and then transmits the compressed data to the BS. Since the cluster-heads spend more energy than other nodes, it is essential to re-select cluster-heads periodically. 2.2 HYENAS System
The HYENAS System selects cluster-heads using a hybrid algorithm which combines model-based processing with a machine learning technique called Case Based Reasoning
黄河科技学院毕业论文（文献翻译） 第13 页
(CBR). To appropriately select a cluster-head for each cluster, the BS determines a node metric CH(m) for each node m in the cluster by taking into account each node’s remaining energy Er(m), the total sum of squared distance dmi from the concerned node m to other nodes in the same cluster and distance from node m to the BS dBS. CH (m) is calculated using the formula as below.
CH(m)?W1Er(m)?W2(1?1(?d)?d2mii?1N2BS) (2)
Where W1 and W2 are weights for the node’ s remaining energy and location respectively. N represents the number of all nodes in the cluster. 2.3 Coverage Cost Metric
Coverage cost is originally introduced in DAPR as a routing metric to avoid routing of data through areas sparely covered by the sensor nodes. Since then, there have been several studies which focus on analyzing the coverage cost metric to prolong network lifetime. In the Coverage Preserving Protocol, Y.R. Tsai proposed a cluster-head selection algorithm based on the coverage cost or normalized sensing coverage area of each sensor node m. Accordingly, they assume?ois the percent of sensing area only covered by node m and?iis the percent the percent of sensing area
黄河科技学院毕业论文（文献翻译） 第14 页
Fig. 2.1 The overlap of sensing areas for two adjacent nodes
covered by this node and other i neighbor nodes. Coverage cost η(m) of node m is defined as below
?(m)??0??i?0??ii?1 (3)
For the simplest example in Fig. 2(a), η(m) is calculated as
?(m)??0?AAA?1?(1?mn2)?mn2?1?mn22?R2?R2?R (4)
where η1is the percent the percent of sensing area covered by node m and node n, Amn is the overlapping are of those two nodes.
In fact, the sensing range of a specific node m likely overlaps with several nodes like Fig. 2(b), thus calculating becomes complicated and needs location information for all nodes. Therefore, they approximate all neighbor nodes as an equivalent node with an equivalent distance to the desired node m. The estimation of this distance is based on energy consumption to transmit and receive beacon messages to all its neighbor nodes.