黄河科技学院毕业论文（文献翻译） 第15 页
3 Coverage and Energy Aware Cluster-Head Selection (CEACHS)
Algorithm
3.1 Motivation
In HYENAS, the cluster-heads are selected according to their energy and location but not coverage while this is a vital metric, especially in surveillance applications. If nodes with large coverage area are selected as cluster-heads, they will spend a large amount of energy and die off first. As a result, the total network coverage quickly falls down. Vice versa, if nodes with small coverage area are selected as cluster-heads and run out of their energy first, the reduction of the total network coverage due to these dead nodes is minimized. In this paper, we propose a cluster-head selection algorithm which aims to integrate both coverage preservation and energy efficiency. Apart from those factors in HYENAS, coverage is carefully considered in cluster-head selection procedure. 3.2 Detailed Algorithm
Calculation of Coverage Cost η. At first, every R node m calculates its coverage cost or estimated normalized effective sensing area η(m) in the initialization and set-up phase. As shown in , it is too complicated to calculate the exact value of η(m). Therefore, an approximate approach which was based on the amount of energy consumption to transmit and receive beacon messages was proposed. The specific node m, with radius R, sends beacon messages to neighbors which are in range of 2R radius. Transmission energyErtrans(dB) is calculated as
Ertrans?L(2R) (5)
黄河科技学院毕业论文（文献翻译） 第16 页
where R is the sensing radius of node m. Ersens(dB) represents the sensitivity of radio receiver and L(2R) is denoted as the propagation loss for a distance of 2R. It is assumed that there are M neighbor nodes responding to beacon messages. Node m must spend Errecieve(dB) to receive these replies
Errecieve?10log10?Mi?010pi10M (6)
where Pi is the received signal energy level, for i = 1, 2,..., M .
The equivalent distant R from the equivalent node m to node m is approximated as
R??2R10(Ersens?Erreceive)10? (7)
where β is denoted as the path loss exponent.
With ρ = R /2R, the equivalent normalized overlapping area Φ(m) of node m is obtained.
2[cos?1(?)??1??2]?(m)?? (8)
According to (3), η(m) finally becomes:
?(m)?(m)?1? (9)
2Cluster-Head Selection. For each cluster, the BS calculates the CH(m) value for each node m. The node which possesses the maximum value of CH (m) in each cluster will become the cluster-head of that cluster. Five input factors related to node m’s characteristics are considered to decide CH(m) value.
Those are:
– Residual battery power Er(m). The higherEr(m), the higher the probability node m becomes cluster-head.
– Relative distance d1from node m to the other nodes in the same cluster.
黄河科技学院毕业论文（文献翻译） 第17 页
2d??dmi21i?1N (10)
where
dmi is the distance from node m to other nodes i which is in the same cluster with
node m and N is the size of the cluster which contains node m. The lesser d1, the higher the probability node m becomes cluster-head.
– Coverage cost η(m), which has already been calculated. The less η(m), the higher the probability node m becomes cluster-head.
All those factors are combined to calculate CH(m) value in the following formula:
CH(m)?W1Er(m)?W2(1??11?)?W1?3?? (11)
?(m)d12?d22??Where W1, W2and W3 are weights for the node’s remaining energy, location and coverage cost. coverage is the most critical metric in target tracking and surveillance applications, thus the value of W3here should be higher than the others. Otherwise, in networks where full coverage is not an important requirement, W1and W2should be increased while W3should be tuned into a small value. 3.3 Adaption of CEACHS
We apply the proposed algorithm into HYENAS in order to achieve the best improvement in both coverage and energy efficiency. The new protocol is named H-CEACHS. In H-CEACHS, the algorithm is executed in the initialization and set-up phase of each round or when CBR in HYENAS decides to reform clusters. Moreover, it is noted that calculation of coverage cost η should be done whenever the network topology changes. However, the energy consumption for this calculation is in significant since the amount of energy to transmit and receive beacon messages is too small to compare with that to transmit and receive sensing reports.
黄河科技学院毕业论文（文献翻译） 第18 页
4 Conclusion
In this paper, we proposed CEACHS, a hybrid algorithm to select appropriate cluster-heads. This algorithm considers many critical parameters including nodes’ remaining energy, location and, most importantly, coverage cost to achieve optimal energy efficiency and coverage preservation. The proposed algorithm outperforms other ones in baseline protocols such as LEACH and HYENAS in terms of both network sensing coverage and energy efficiency.
This work was supported by Korea Science and Engineering Foundation(KOSEF) grant
funded by the Korean government(MEST) (No. 2009-0076504). We would like to thank Mr. Nguyen Phuong Nam, Ohio University, for his valuable technical support.
From: 《The Coverage Problem in Wireless Sensor Network：Mobile Network Applications10》