problem, build an instance *I* of *OPT-CPACC* and then show that any algorithm
that resolves *I* resolves *SCP* as well.

Any instance SCP of the set covering problem is defined by a set of nodes, a set of
node subsets and a cost for each node subset. Let :

- $S = \{s_1..s_N\}$ be a set of $N$ nodes (sensors);

- $J = \{S_1..S_M\}$ be a set of $M$ node subsets defined by : $\forall j = 1..M, S_j = \{s_j\} \cup \{s_m \in S - \{s_j\} \text{ such that } s_m \text{ can reach } s_j \text{ using its lowest transmit power } P_1\}$;

- $\forall j = 1..M$, the cost of subset $S_j$ is defined by : $Cost(S_j) = (\frac{E_{CH}}{Er_j})^{\lambda}$.

The instance *SCP* being defined, let us consider the instance *I* of *OPT-CPACC*,
defined by the following input :

- Each cell of the monitored area is covered by exactly one sensor;

- The residual energy of nodes $s_i \in S, \forall i = 1..N$ is equal to $E_0$ and $E_0 > E_{CH} > E_{Active}(P_k), \forall k = 1..K$;

- Each sensor is equipped with exactly one transmit power $P_1$.

Since each sensor covers exactly one single cell, any admissible solution of the ins-
tance *I* will have all its sensors turned on, to satisfy the full coverage constraint. If
we could resolve *I*, then the solution of *SCP* can be derived from the solution of *I*
as follows : for every sensor $s_i$, ($1 \le i \le N$) designated as CH in the solution of *I*, $S_i$
is a member of the minimum-cost covering set. In fact, since the solution of *I* is fully
clustered and since sensors use their lowest power $P_1$ to connect to their CH, the
optimal solution of *I* exhibits the lowest-cost set of CHs. And, since the cost of subset
$S_j, \forall j = 1..M$, is exactly the weight of cluster head $s_j$ in the optimal solution of *I*,
the set $\{S_j, \text{ such that } s_j \text{ is designated CH in the optimal solution of I}\}$ is the lowest-
cost set of node subsets that fully covers all network nodes. Hence, any algorithm
that resolves the above instance *I* of *OPT-CPACC* can resolve any instance *SCP* of
the set covering problem. Such reduction proves that *OPT-CPACC* is NP-Complete.
<figure><img src="image_24.png" /><figcaption>FIGURE 4.4 Necessary condition to have a connected overlay CH graph : $R_t^{CH} \ge 2.(R_s + R_t(P_K))$</figcaption></figure>

**Proposition 4.4.2.** *When the inter-cluster transmission range* $R_t^{CH}$ *is greater or equal to* $2.(R_s + R_t(P_K))$, *any admissible solution exhibits a clustered configuration where the overlay graph composed of cluster heads is connected.*

**Proof.** Since the whole network is assumed to be covered and clustered, every node is either a CH or attached to a CH. Figure 4.4 depicts the admissible configuration exhibiting the longest distance between two adjacent CHs. In fact, when sensors are lined-up, each regular sensor has to be connected to a CH. Therefore, the maximum distance separating a regular *Active* sensor from an adjacent CH is $R_t(P_K)$. On the other hand, the monitored area is supposed to be fully covered, so the maximum distance separating two adjacent regular *Active* sensors is $2.R_s$. Hence, the maximum distance separating two CHs is $2.R_s + 2.R_t(P_K)$. In this worst-case configuration, it is clear that when $R_t^{CH} \ge 2.(R_t(P_K) + R_s)$, the overlay graph composed of CHs will be connected. This condition is very interesting because it will guarantee that the overlay graph formed by the CHs is connected and thus could be used as a routing topology, to convey data from any sensor toward the PN. However, this condition is a very conservative because, in practice, when the network is dense enough, the average distance between two adjacent CHs is likely to be less than $2.(R_s + R_t(P_K))$.
## 4.5 Proposed heuristic

As the considered problem is NP-Complete, we propose a Tabu search heuristic, called *Tabu search heuristic for Clustering and Power Assignment under Coverage Constraint* (T-CPACC), to tackle to exponentially-increasing processing time of the exact solution. T-CPACC will be run by the PN to find a near-optimal sensor state configuration. As shown in Algorithm 4.1, T-CPACC starts with an admissible solution and iteratively performs movements that consist in changing the state of one sensor at a time. The best solution found after the predefined number of iterations is transposed on sensors to form the new network configuration. The network will operate

**Algorithm 4.1 T-CPACC**: Tabu search algorithm for clustering and power assignment in WSN under coverage constraint

- **Initial solution**: the Tabu algorithm starts with a configuration where all sensors are activated as CHs. This configuration is obviously admissible;

- **Admissible configuration**: a configuration $S$ is defined by the states of its sensors ($Sleep$, $Active(P_k)$, $CH$) where $Active(P_k)$ is a state in which a sensor is $Active$ and is using transmit power $P_k$, $k = 1..K$. Only feasible configurations (i.e, satisfying model constraints (4.1b-4.1d) are considered;

- **Score function**: a configuration is evaluated using the score function of Equation (4.1a);

- **Neighborhood investigation**: a search movement $M < i, u, v >$ consists in changing the state of a single sensor $i$ from state $u$ to state $v$, such that the model constraints (4.1b-4.1d) are satisfied;

- **Aspiration criterion**: Tabu movements are allowed when the score of the resulting configuration is lower than the score of the best solution found so far over the whole search process;

- **Stop criterion**: The search algorithm stops after a predefined number of iterations.
rate with this configuration for a predefined period *T* during which residual energies of *Active* nodes and CHs will decrease, then T-CPACC is run again to find a new configuration based on the new values of residual energies. This new configuration will be kept for another period *T* and so fourth. The periodic execution of T-CPACC by the PN requires sensors-related information (e.g, residual energies) to be transmitted periodically to the PN (upstream communication) and the newly-computed sensor states to be transmitted to the sensors (downstream communication). In our architecture, sensor-related data will be conveyed exactly in the same manner as the sensed data, i.e, through the cluster-based hierarchical structure of the network. *Active* sensors that have data to report will send it to the PN via their respective CHs. They will append the value of their respective residual energies to the data packets they are sending. When they have no data to send, they will synchronize their energy information with the PN periodically. As for the switched-off sensors, their energy consumption is constant and very low and can therefore be estimated by the PN whenever needed, as long as they are in *Sleep* state. As far as state assignment to sensors is concerned, the PN will broadcast a notification message holding associations between sensors and their newly-computed states (*Sensor ID*, *Sensor State*). Only the sensors which state has changed will have an entry in the notification message while all other sensors will keep their ongoing state. The notification message will be routed to the sensors via their respective CHs.

## 4.6 Implementation and simulation results

In this paragraph, we assess the efficiency of T-CPACC. We first evaluate the quality of T-CPACC's solutions with respect to a lower bound provided by the exact resolution of the integer-variable model (4.3). Then, we compare, in terms of network lifetime and energy consumption balancing, T-CPACC to HEED (Younis et Fahmy, 2004), one of the most popular algorithms in literature for energy-efficient
clustering with transmit powers assignment.

4.6.1 Quality of the solution : T-CPACC vs its lower bound

To evaluate the quality of our heuristic, we compared the objective function provided
by T-CPACC to the lower bound derived from the exact resolution of the mathema-
tical model (4.3). Let's note though that the measure of the objective function has
no practical usefulness but is only meant to assess the quality of the heuristic's solu-
tions with respect to the lower bound (i.e, how far is the solution from optimality).
To compute the optimal solution, we implemented our linear integer-variable model
using ILOG CPLEX (ILOG, 2009). CPLEX is a mathematical programming and
optimization software that solves linear problems with continuous, integer or mixed
variables, using the branch-and-bound method. Figure 4.5 depicts the objective func-
tion of the solutions generated by CPLEX and by T-CPACC, for different network
sizes. Let's note here that, because of the exponentially-increasing processing time of
CPLEX, we were not able to solve the integer-variable system (4.3) in a reasonable

<figure><img src="image_25.png" /><figcaption>FIGURE 4.5 Objective function generated by T-CPACC vs Cplex</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>FIGURE 4.6 Network lifetime generated by T-CPACC vs HEED</figcaption></figure>

time for configurations higher than 64 nodes, so we measured and reported the solution of the continuous relaxation of the system (4.3), since the relaxed system takes much less time to be resolved than the original integer-variable system and obviously provides a lower bound. Nevertheless, for configurations with more than 256 sensors, it was difficult to get the relaxed system resolved in reasonable processing times. In Figure 4.5, we can observe that the objective function provided by T-CPACC is very close to the optimal solution for configurations up to 100 sensors and is less than 20% above the lower bound for configurations of more than 100 sensors. The increase in gap is due to the fact that the objective function of the relaxed system’s solution is lower than that of the original system. Still, the solution provided by T-CPACC is quite close to the optimal one, which shows that T-CPACC has a very acceptable performance.
<figure><img src="image_27.png" /><figcaption>FIGURE 4.7 Standard deviation of the dissipated energy, generated by T-CPACC vs HEED</figcaption></figure>

4.6.2 Measure of the network lifetime without coverage constraint : T-CPACC vs HEED

To evaluate the performance of T-CPACC in terms of network lifetime, we compa-
red it to a well-recognized clustering protocol : Hybrid Energy-Efficient Distributed
Clustering (HEED) (Younis et Fahmy, 2004). HEED is a distributed clustering pro-
tocol that uses a hybrid combination of the residual energy and the intra-cluster
communication cost as attribute for CH selection. In its initialization phase, HEED
allows sensors to compute a probability of becoming CH, proportional to its residual
energy and to a pre-determined percentage of CHs. Then, during a repetition phase,
sensors seek the best CH to connect to. If no CH is found, the sensor doubles its
probability to become CH and broadcasts it again to its neighbors, and so forth.
This phase stops either when this probability equals 1 (i.e, the sensor elects itself
as CH) or when it finds a CH to connect to. HEED performs clustering with one
or many transmit powers, but it does not address optimal coverage (i.e, it performs
clustering on a set of switched-on sensors). So, to be able to compare our heuristic
<figure><img src="image_28.png" /><figcaption>FIGURE 4.8 Network lifetime generated by T-CPACC vs HEED and the Modified HEED, for $R_s=1$</figcaption></figure>

to HEED without penalizing the latter with regards to optimal coverage, we considered, for T-CPACC, a configuration in which every sensor covers one and only one cell. With this configuration, any admissible solution provided by T-CPACC will have all its sensors switched on and only the clustering performance will be accounted for in comparison to HEED. Figure 4.6 depicts the network lifetime generated by T-CPACC versus HEED. We can see that T-CPACC outperforms HEED for all considered network sizes. This can be explained by a better balancing of the consumed energy over the sensors, so that all nodes’ batteries are drained roughly at the same time and thus the network lifetime is longer. This argument is confirmed by the results in Figure 4.7, on which we can see that T-CPACC has a lower standard deviation of the dissipated energy than HEED, which means the dissipated energy is better balanced over sensors.
<figure><img src="image_29.png" /><figcaption>FIGURE 4.9 Network lifetime generated by T-CPACC vs HEED and the Modified HEED, for $R_s=2$</figcaption></figure>

### 4.6.3 Measure of the network lifetime with coverage constraint : T-CPACC vs Modified HEED

As mentioned above, HEED does not address optimal area coverage. Hence, to compare T-CPACC to HEED in terms of the combined clustering and coverage constraint, we operated a small modification on HEED to include the optimal area coverage feature : this modification consists in computing, for each cluster generated by HEED, an optimal subset of non-CH sensors that will be activated while the other sensors are turned off, such that full area coverage is insured (Chamam et Pierre, 2007a). Figure 4.8 and Figure 4.9 depict the network lifetime generated by T-CPACC versus HEED and the modified version of HEED that handles optimal coverage, for two different values of the sensing range. We can see that, for $R_s = 1$, the solution generated by T-CPACC generates approximatively twice the network lifetime generated by HEED's solution and 1.5 times the network lifetime of the enhanced HEED's solution. For $R_s = 2$, T-CPACC performs even better. Let's note that the value of the network lifetime, whatever the algorithm used, increases
when the sensing range increases. This is due to the fact that when $R_s$ increases, less sensors need to be activated to insure full area coverage and thus, more energy is conserved, which allows for a higher network lifetime.

## 4.7 Conclusion and future work

In this paper, we proposed a novel centralized mechanism for near-optimal state and transmit power assignment to sensors in large-scale, cluster-based, monitoring wireless sensor networks. We considered dense sensor networks with overlapping sensing ranges and where sensors were equipped with multiple transmit powers, allowing them to reach a bigger set of cluster heads at a higher energy cost. Our mechanism seeks energy-optimal configurations where every sensor can be switched off, activated or promoted cluster head and where every active non-cluster-head sensor must be connected to a cluster head, reached using one of the transmit powers a sensor is equipped with. Our mechanism is based on a tabu algorithm that computes a near-optimal network configuration that maximizes network lifetime while ensuring the full coverage of the monitored area and the connectivity of every active sensor to a cluster head. Moreover, our algorithm provides an optimal assignment of transmit powers to active sensors. Simulations show that our mechanism achieves good results with respect to the exact solution of the derived ILP model. Despite its centralized aspect, our mechanism exhibits low complexity and low computation time making its practical implementation adaptable to large-scale networks.

As future research directions, we intend to develop a more sophisticated heuristic to improve the network lifetime. Furthermore, we intend to consider distance-dependent probabilistic event detection, where the probability that a sensor detects an event is function of the distance of that sensor from the event.
# CHAPITRE 5

## A DISTRIBUTED ENERGY-EFFICIENT CLUSTERING PROTOCOL FOR WIRELESS SENSOR NETWORKS

Ali Chamam and Samuel Pierre

Department of Computer & Software Engineering,

École Polytechnique de Montréal,

C.P 6079, succ. Centre-Ville, Montreal (QC), Canada H3C 3A7.

E-mail: {ali.chamam, samuel.pierre}@polymtl.ca

### ABSTRACT

Minimizing energy dissipation and maximizing network lifetime are among the central concerns when designing applications and protocols for sensor networks. Clustering has been proven to be energy-efficient in sensor networks since data routing and relaying are only operated by cluster heads. Besides, cluster heads can process, filter and aggregate data sent by cluster members, thus reducing network load and alleviating the bandwidth. In this paper, we propose a novel distributed clustering algorithm where cluster heads are elected following a three-way message exchange between each sensor and its neighbors. Sensor's eligibility to be elected cluster head is based on its residual energy and its degree. Our protocol has a message exchange complexity of $O(1)$ and a worst-case convergence time complexity of $O(N)$. Simulations show that our algorithm outperforms EESH, one of the most recently published distributed clustering algorithms, in terms of network lifetime and ratio of elected cluster heads.
**Key words :**

Wireless Sensor Networks, clustering, network lifetime, distributed, energy efficiency.

**5.1 Introduction**

Wireless sensor networks consist of a large number of low-power, limited-processing capability, MEMS (Micro-Electro-mechanical Systems) capable of measuring and reporting physical variables related to their environment. In surveillance applications, sensors are deployed in a certain field to detect and report events like presence, movement or intrusion in the monitored area (Chong et Kumar, 2003).

As depicted in Figure 5.1, data collected by sensors is transmitted to a special node equipped with higher energy and processing capabilities called "Processing Node" (PN) or "sink" (Chong et Kumar, 2003). The PN collects, filters and aggregates data sent by sensors in order to extract useful information. Due to their energy constraint, wireless sensors usually have a limited transmission range making multi-hop data routing toward the PN more energy-efficient than one-hop transmissions. Unlike in wired networks or in regular wireless networks (cellular, WLAN, etc.), energy conservation in wireless sensor networks is a critical issue that has been

<figure><img src="image_30.png" /><figcaption>FIGURE 5.1 Multi-hop routing of collected data</figcaption></figure>
addressed by substantial research works (Cardei et al., 2005; Raghunathan et al., 2002). Generally, energy conservation is dealt with on five different levels (Cardei et al., 2005; Chong et Kumar, 2003):

1. efficient scheduling of sensor states to alternate between sleep and active modes;

2. efficient control of transmission power to ensure an optimal tradeoff between energy consumption and connectivity;

3. data compression (source coding) to reduce the amount of uselessly transmitted data;

4. efficient channel access and packet retransmission protocols on the Data Link Layer;

5. energy-efficient routing, clustering and data aggregation.

This paper addresses the fifth issue and more specifically energy-efficient clustering. Clustering has been proven energy-efficient in sensor networks (Arboleda et Nasser, 2006; Chong et Kumar, 2003; Younis et al., 2006). In fact, CHs can process, filter and aggregate data sent by sensors belonging to their cluster, thus reducing network load and alleviating the bandwidth. Besides, clustering provides for substantial energy saving (Arboleda et Nasser, 2006; Karl et Willig, 2005) since non-CH sensors are not involved in routing and relaying data and transmissions are only operated by CHs. Yet, since CHs consume more energy in aggregating and routing data, it is important to have an energy-efficient mechanism for CH election and rotation (Heinzelman et al., 2000; Kwon et Gerla, 1999). In flat networks, data is routed from sensors to the PN through peer sensors using one of the many routing protocols proposed in the literature (Akkaya et Younis, 2005). In contrast, in hierarchical (clustered) sensor networks, CHs transmit aggregated data to the PN, either directly (one-hop) (Heinzelman et al., 2000) or in a multi-hop fashion (Mhatre et Rosenberg, 2004b). For the sake of minimizing energy consumption, both optimal number of CHs and
their optimal placement have to be sought.

In this paper, we propose a distributed clustering protocol for sensor networks, called Energy-Efficient Cluster Formation protocol (EECF). We suppose that any sensor can be either a regular sensor or a CH and that every regular sensor has to be connected to a CH, i.e., it has to have at least one CH in its fixed transmission range. We also suppose that only CHs can route data (because they have enough energy to do so and because this limits broadcasting). In EECF, the set of CHs is elected following a three-way message exchange between every sensor and its one-hop neighbors. CH election is mainly based on sensors' respective residual energies and degrees. Run on a flat network, our protocol ends up with a clustered (admissible) sensor configuration that maximizes the network lifetime, while ensuring, under a certain condition, the connectivity of the overlay network composed of CHs.

This paper is organized as follows: in the next section, we present some related work. In Section 5.3, we outline our problem and enumerate our assumptions. In Section 5.4, we describe EECF in detail. In Section 5.5, we provide an analytical study of the complexity of EECF and the connectivity of the solutions. In Section 5.6, we discuss our simulation results. Finally, Section 5.7 concludes this paper and points out some future directions.

## 5.2 Related work

Energy-efficient clustering algorithms for wireless sensor networks have been widely addressed in literature. The main goal of clustering is to efficiently maintain the energy consumption of sensor nodes by involving them in multi-hop communication within a particular cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the sink. Cluster formation is typically based on the energy reserve of sensors and sensor's proximity to the CH (Younis et al., 2006). For instance, Low-Energy Adaptive Clustering Hierarchy
(LEACH) (Heinzelman et al., 2000), one of the first clustering algorithms proposed for sensor networks, is a distributed, proactive, dynamic algorithm that forms clusters of sensors based on the received signal strength and uses local CHs as routers to the sink. Each node makes its own decision whether to become CH based on how often and the last time it has been CH but also on the optimal percentage of CHs in the network (pre-determined value). Transmissions are operated only by CHs which saves energy. LEACH provides a balance of energy consumption through a random rotation of CHs. However, CHs transmit data directly to the sink, which can be energy-consuming in large-scale sensor networks. Power-Efficient GAthering in Sensor Information Systems (PEGASIS) (Lindsey et Raghavendra, 2002) and its variation Hierarchical-PEGASIS are two improvements of LEACH. Rather than forming multiple clusters, PEGASIS forms chains of sensor nodes so that each sensor transmits and receives from a neighbor and only one node is selected from that chain to convey data to the PN. Still, communication between the elected CH and the PN is one-hop, which may waste energy and prove to be unsuitable for large-sized networks. Weighted Clustering Algorithm (WCA) (Chatterjee et al., 2002) is a reactive clustering algorithm where cluster election is based on the evaluation, for every sensor, of a score function called *combined weight*. This function is a weighted linear combination of the degree, the mobility level, the transmission power and the residual energy of the sensor. Every sensor broadcasts its *combined weight* to its neighbors and the sensor having the lowest weight is elected CH. Hybrid Energy-Efficient Distributed Clustering (HEED) (Younis et Fahmy, 2004) is a distributed clustering protocol that uses a hybrid combination of the residual energy and the intra-cluster communication cost as attribute for cluster head selection. HEED ensures a uniform distribution of CHs across the network and adjusts the probability of CH-selection to ensure inter-CH connectivity. In its initialization phase, HEED allows sensors to compute a probability of becoming CH, proportional to its residual energy and to a pre-determined percentage of CHs. Then, during a repetition phase, sensors seek
the best CH to connect to. If no CH is found, the sensor doubles its probability to become CH and broadcasts it again to its neighbors, and so forth. This phase stops either when this probability equals 1 (i.e., the sensor elects itself as CH) or when it finds a CH to connect to. Distributed Weight-based Energy-Efficient Hierarchical Clustering (DWEHC) (Ding et al., 2005) is a distributed clustering algorithm similar to HEED. In DWEHC, every sensor computes its score as a function of its residual energy and its proximity to its neighbors. In a neighborhood, the sensor with the largest score will be elected CH and all the neighborhood members become attached to that CH. Then, every non-CH member tries to find a "cheaper" way to reach the CH through its non-CH neighbors. These neighbors broadcast their cost to reach the CH and the sensor can then decide whether to use a multi-hop or a direct connection to the CH. Energy-Efficient Hierarchical Clustering (EEHC) (Bandyopadhyay et Coyle, 2003) is another distributed clustering algorithm that performs single and multi-level clustering. In the single-level process, every node announces itself to its k-hops neighbors (by forwarding, for $k > 1$) as a "volunteer" CH, with probability $p$. Then, every sensor connects to the closest CH. Sensors that do not receive any announcement and are not CHs become "Forced CHs". The same process is extended to the multi-level clustering with the exception that only designated CHs participate in the process of election of the second-level cluster set. Energy-Efficient Strong Head clustering (EESH) (Zhou et al., 2007) is a recently published clustering protocol. In EESH, nodes are promoted CHs according to their respective residual energies, their respective degrees and the distance to and the residual energy of their neighbors. For that, EESH evaluates a cost function for every sensor in the network and iteratively elects the node having the greatest cost as CH. This process terminates when all the sensors in the network are connected to at least one CH. EESH has been shown to outperform HEED and LEACH, so we used it as a comparative base in our performance evaluation.
## 5.3 Problem description and assumptions

As discussed in the Introduction, clustering has been proven energy-efficient in sensor networks (Arboleda et Nasser, 2006; Heinzelman et al., 2000; Kwon et Gerla, 1999; Younis et Fahmy, 2004). During the clustering process, it is necessary to take into account aspects such as : cluster size and form, criteria for CH selection, how to control inter-cluster and intra-cluster collisions and energy saving issues. The design of the clustering process is one of the more important issues for the correct functioning of the network, due to the probed efficiency of using a hierarchical communications scheme. In this paper, we consider a sensor network randomly deployed in a certain area and we propose an energy-efficient cluster formation protocol (EECF) that maximizes network lifetime. Run on a flat topology of sensors, EECF ends up with a hierarchical topology in which sensors are organized into clusters having, each, one sensor promoted as CH and all the other regular sensors connected to the closest CH. CHs also act as data relays since they route data received from peer CHs toward the PN, either directly if the PN is within their range, or through a neighbor CH if not. To control the sensors that perform data relaying, we restrict the routing task to CHs, since they are more eligible than the other nodes in terms of residual energy. Therefore, a route must exist from any CH to the PN. On the other hand, because of the energy-intensive data processing and routing tasks, a CH sensor consumes much more energy than regular sensors. If CHs were chosen a priori and fixed throughout the system's lifetime, these nodes would quickly exhaust all their limited energy making them no longer operational and therefore, all the nodes that belong to the cluster would lose their communication ability. In this paper, we dynamically designate CHs so that the elected CH sets are adaptive to the change in the residual energies and the network configuration.

In this paper, we make the following assumptions :
1. The ID and the position of each sensor are fixed and known to both the PN and the sensor itself.

2. Active sensors capture events occurring in their range and transmit data associated with these events straightaway, without any buffering, because sensors are usually not equipped with large (and costly) buffers. However, for some channel access protocols, like TDMA, some little buffers are still needed to hold data waiting to be sent.

3. All sensors have the same sensing range $R_s$.

4. All regular (non-CH) sensors have the same transmission range $R_t$ and consume the same power to transmit one bit of data. Likewise, all CHs have the same transmission range $R_t^{CH}$ and consume the same power for transmitting one bit of data. Typically, $R_t^{CH} \gg R_t$.

5. CHs consume more energy during a time period than regular sensors, since they have a higher transmission range and since they perform additional data-related tasks like aggregation, filtering and routing.

6. Each sensor has an initial energy $E_0$. The PN is assumed to have no energy limitation. We assume that regular sensors dissipate the same energy during a unit of time, no matter how the events' distribution is.

7. Network lifetime is defined as the time separating the instant the network starts operating and the instant the network is no more connected (because of the failure of one or more sensor).

8. Sensors have idealized sensing capabilities. That is, inside the sensor's range, quality of sensing is not altered with distance from the sensor.

9. We assume ideal MAC layer conditions, that is, perfect transmission of data on a node-to-node wireless link.
## 5.4 Description of the EECF protocol

EECF is fully distributed. As shown in Figure 5.2, it consists of a number of actions and message exchanges executed by each sensor, which leads to the election of a set of CHs and ensures that each regular sensor (not CH) is connected to a CH.

We will show later that, under a certain condition, any configuration provided by EECF will exhibit a spanning tree connecting all CHs (i.e., a route exists between any pair of CHs). This makes the logical overlay network formed by the set of CHs sufficient to route data from any sensor toward the PN. Here is the description of EECF :

1. Firstly, each sensor broadcasts to all its neighbors a message called Score Ad-vertisement Broadcast (SAB) containing a score function expressing its ability to be promoted CH. In EECF, the score function advertised by each sensor through the SAB is a linear combination of its degree and its residual energy. It is expressed by : $Score(i) = \alpha \cdot \frac{degree(i)}{N-1} + (1 - \alpha) \cdot \frac{Er(i)}{E_0}$. The coefficient $\alpha$ will weigh the importance of the residual energy with respect to the number of neighbors. We will discuss the choice of the value of $\alpha$ later.

2. After receiving a SAB from all its neighbors, each node $i$ partitions the set of its neighbors into two subsets : $N^+(i) = \{v \in Neighbors(i) \text{ such that } Score(v) \ge Score(i)\}$ and $N^-(i) = \{v \in Neighbors(i) \text{ such that } Score(v) < Score(i)\}$. The idea behind this partitioning is that a regular sensor tends to be connected to a CH that has a higher score (more eligible to be a CH) and thus belonging to $N^+(i)$. Subsequently, node $i$ computes, for each node $v \in N^+(i)$, a function $RCR_i(v)$ representing the relative preference that sensor $i$ has for sensor $v$ as its potential CH. In our implementation, $RCR_i(v)$ takes the form of a probability function for sensor $v$ to be CH for sensor $i$, that is proportional to the rank of
<figure><img src="image_31.png" /><figcaption>FIGURE 5.2 Description of the EECF protocol, executed by every sensor</figcaption></figure>
sensor $v$ within $N^+(i)$. It is expressed as follows :

$$ RCR_i(v) = \frac{|N^+(i)| + 1 - Rank(v)}{\frac{|N^+(i)|*|N^+(i)|+1}{2}} \quad (5.1) $$

where $Rank(v)$ is the rank of sensor $v$ within $N^+(i)$ and $\frac{|N^+(i)|*|N^+(i)|+1}{2}$ is the sum of all possible ranks.

3. Next, sensor $i$ broadcasts a message called Relative Cluster head Rank Adver- tisement (RCRA) containing the values $RCR_i(v)$ of all neighbors $v \in N^+(i)$. In the same manner, each sensor $i$ receives a distinct RCRA from all its $N^-(v)$ neighbors expressing its relative "importance" (as a potential CH) to each of them.

4. After receiving all RCRA messages from its $N^-(i)$ neighbors, every sensor $i$ computes a function $RCN(i)$ representing its Relative Contribution To the Network (RCN). $RCN(i)$ represents the probability for a node $i$ to be elected CH, based on the information received from its $N^-(i)$ neighbors. Since every sensor $i$ receives from each of its $N^-(i)$ neighbors an RCRA representing sensor $i$'s probability to be elected CH and since all $N^-(i)$ neighbors have the same weight, we express $RCN(i)$ as follows :

$$ RCN(i) = 1 - \prod_{v \in N^-(i)} (1 - RCR_v(i)) \quad (5.2) $$

Let us note that $RCN(i)$ represents the probability for sensor $i$ to be elected CH. Indeed, in our protocol, a sensor promotes itself CH if, at least, one of its $N^-(i)$ neighbors elects it as CH. Therefore, if we assume that the CH election probabilities are independent, the probability for a sensor of not being elected CH equals : $\prod_{v \in N^-(i)} (1 - RCR_v(i))$ and thus $RCN(i)$ represents the probability for sensor $i$ to be elected CH.

5. Afterwards, each sensor $i$ broadcasts a message, called Contribution to the
Network Advertisement (RCNA). The RCNA sent by sensor $i$ will be received by all sensors in $N^{-}(i)$. In the same manner, each node $i$ receives a distinct RCNA from all its $N^{+}(i)$ sensors.

6. Finally, after receiving all RCNAs from its $N^{+}(i)$ neighbors, each node $i$ takes its decision about the CH it will connect to, unless it has been elected, itself, CH by one of its $N^{-}(i)$ neighbors. If $N^{-}(i) \neq \emptyset$, sensor $i$ has to wait until all RCNAs are received from its $N^{+}(i)$ neighbors or until a predefined timeout has elapsed to make its decision. This decision is then broadcast to all neighbors through an *ElectionMessage* holding the ID of the sensor designated by sensor $i$ as its CH (either an existing CH or a newly elected one). The decision process for every node $i$ is as follows:

(a) If sensor $i$ has no neighbor with lower score ($N^{-}(i) = \emptyset$), it proceeds with step 6b. Otherwise, it waits until all the decisions of its $N^{-}(i)$ neighbors are received or until a predefined timeout has elapsed and then proceeds with step 6b.

(b) If, at least, one sensor in $i$'s one-hop neighborhood has already been elected CH, $i$ can connect to it and thus does not need to designate a CH among its $N^{+}(i)$. In this case, sensor $i$ will broadcast its *ElectionMessage* with the ID of its CH and a flag *CONNECTED* set to 1, which tells the sensors in $N^{+}(i)$ that sensor $i$ does not need to elect a new CH.

(c) If sensor $i$ does not have any already-elected CH in its range, it has to elect one among its $N^{+}(i)$ neighbors. It will then select the node $v_{max} = \arg\max_{N^{+}(i)}\{RCN(i)\}$ as its CH and broadcasts its *Election Message* with the ID of $v_{max}$ so that $v_{max}$ knows that it has been designated CH.

(d) Finally, if a sensor $i$ has no neighbors with higher score ($N^{+}(i) = \emptyset$) and has no elected CH within its range, it promotes itself CH.

7. When a sensor is elected CH, it broadcasts a message holding its ID and its new state to its neighbors.
Let us note here that a sensor is elected CH if, at least, one of its $N^-$ neighbors elects it as CH. Furthermore, to avoid having multiple CHs within the same cluster, every sensor waits for the decisions of its $N^-$ neighbors before making its own decision. In this way, CH election will be made in chain : sensors with the lowest *Score* (having an empty $N^-$ set) will be the first ones to elect their CH and broadcast their decision. When a sensor is elected CH, it will inform its neighbors so that they can connect to it instead of electing, uselessly, another CH within their respective $N^+$ neighbors. For the election chain to function properly, every sensor *i* has to send its *Election Message* to its $N^+(i)$ neighbors even if it chooses to connect to an already-elected CH neighbor, because sensors in $N^+(i)$ will wait for *i*'s decision to send their own decisions to their respective $N^+$ neighbors.

## 5.5 Protocol analysis

As described in the previous section, CH election is performed after a three-way message exchange between each sensor and its neighbors. After receiving the score of each of its neighbors through the SAB, every sensor processes and broadcasts the *RCR* function of its neighbors that have higher SAB. Some of these neighbors can be two-hops away from each other, so the *RCR* received by a sensor may encompass information about some neighbors of its neighbors that are two-hops away, which provides that sensor with aggregated information about its extended (two-hops) neighborhood. Then, every sensor assesses its capacity to become CH by computing its *RCN* function, based on the *RCRs* received from its neighbors having a lower score. Therefore, the *RCN* sent by a node to its one-hop neighbors to express its "eligibility" to become CH takes indirectly into account information about its two-hops neighbors, through the received *RCRs*. In this three-way message exchange, sensors play the role of "information relay" for their potential CH (neighbors having higher scores) by informing them through the *RCRA* about their relative "rank" among
the other potential CH in their range. Similarly, every sensor $i$ plays the same role of "information relay" for sensors in $N^{-}(i)$, by informing them (through the RCNA) of its "importance" (or eligibility) as a potential CH, so that they can decide which one of their neighbors will be chosen as their CH. This "importance", expressed by the RCN, cannot be computed by $i$'s neighbors since they do not necessarily reach each other and thus cannot necessarily hear each other's RCRA. Hence, the final CH election will be based not only on local information (one-hop) but also on aggregated information from the two-hops neighbors and this makes the election protocol more efficient than traditional localized clustering algorithms (Heinzelman et al., 2000; Younis et Fahmy, 2004) where each node's decision is based solely on its one-hop neighbors information. This is the main originality of EECF and we will show later that this novel clustering technique performs very well in terms of energy consumption and network lifetime. But let us discuss first the complexity of EECF and the connectivity of the set of elected CHs.

**Proposition 5.5.1.** EECF has an algorithmic complexity of $O(N)$ at each node.

*Proof.* The execution of EECF at each node $i$ consists of a sequence of four steps: (1) calculating the score and broadcasting it through the SAB message; (2) calculating the RCR($v$) function for each neighbor $v$ in $N^{+}(i)$ (after all SAB messages are received from neighbors) and broadcasting them through the RCRA; (3) calculating RCN($i$) (using the RCRs of $N^{-}(i)$ neighbors) and broadcasting it through the RCNA message; (4) choosing the neighbor having the highest RCN among $N^{+}(i)$ as CH and broadcasting the decision. Processing time at Steps (2) and (3) is proportional to the number of $i$'s neighbors which, in the worst case, is equal to $N$. Hence, the overall complexity is $O(N)$.

**Proposition 5.5.2.** EECF has a worst-case convergence time complexity of $O(N)$
and an average convergence time complexity of $O(\log(N))$.

**Proof.** We denote by "convergence time" the time it takes for a flat network to become fully clustered using EECF. The worst-case sensor configuration for the convergence time is the one in which sensors are sorted according to their *Scores* and placed in a chain of increasing scores, from right to left, for instance. In this case, the rightmost sensor will start the election process since it has the lowest *Score*. It will elect its left neighbor as CH. Then, every sensor will wait for the *Election Message* from its right neighbor ($N^-$) and send its own decision to its left neighbor ($N^+$). The process terminates at the leftmost sensor which will either be CH or connect to its right neighbor if this latter has been elected CH. With this worst-case configuration, the convergence time is proportional to the number of sensors and thus the complexity is $O(N)$. However, in a dense network where sensors are randomly scattered, we have, in average, $|N^+(i)| = |N^-(i)| = \frac{\delta_i}{2}$, where $\delta_i$ denotes the average degree of node $i$. In such a case, every sensor has to wait for the *Election Messages* of its $N^-(i)$ neighbors, which average number is $(\delta_i/2)$ and then sends its own decision to the set of its $N^+(i)$ neighbors, having the same average cardinality. The set of sensors having the lowest score (i.e., an empty $N^-$ set) start the process. Each of these sensors will send its decision to its $(\delta_i/2)$ neighbors. Then, each of these latter neighbors will send, in its turn, its own decision to its $(\delta_i/2)$ neighbors, and so forth. Hence, in average, the whole set of sensors can be seen as a layered structure of sensors in which sensors on a certain layer have their $N^-$ neighbors on the lower layer and their $N^+$ neighbors on the upper one. Therefore, if we start with $p$ sensors having the lowest score (and thus forming the first layer), the number of sensors on layer $k$ ($k > 1$) is $p.(\frac{\delta_i}{2})^k$. And since the average convergence time is proportional to the number of layers, it has thus a complexity of $O(\log(n))$.

**Proposition 5.5.3.** When the inter-cluster transmission range $R_t^{CH}$ is greater or
<figure><img src="image_32.png" /><figcaption>FIGURE 5.3 Necessary condition to have a connected overlay CH graph : $R_t^{CH} \geq 3.R_t$</figcaption></figure>

equal to three times the intra-cluster transmission range $R_t$, the EECF protocol ends up with a clustered configuration where the overlay graph composed of cluster heads is connected.

**Proof.** Since the whole network is assumed to be connected and clustered, every node is either a CH or attached to a CH.

Figure 5.3 depicts a configuration exhibiting the longest distance between two adjacent CHs. In fact, when sensors are lined-up, each regular sensor has to be connected to a CH and the two regular sensors have to be directly connected since the network is assumed to be connected. In this worst-case configuration, it is clear that when the transmission range of a CH is equal to or greater than three times $R_t$, the overlay graph composed of CHs will be connected.
## 5.6 Protocol implementation and Performance evaluation

### 5.6.1 Experiment setup

In our EECF protocol, CHs are elected based on their respective degrees (which are static) and their residual energies at the instant the clustering protocol is executed. Hence, different residual-energy maps can lead to different sets of CHs. When run once, the EECF protocol elects the set of CHs that tends to maximize the network lifetime as if this configuration will be kept for the whole network lifetime. However, since sensors' residual energies are gradually depleted during network operation, our protocol will be run periodically to adapt the dynamic residual energies : every pre-determined period of time $T$, a new set of CHs will be elected, based on the actual residual energies at the instant EECF is run. This adaptivity will balance the CH role among sensors and thus balance energy dissipation. The period $T$ could be chosen arbitrarily but it has to provide a tradeoff between network dynamic and stability. In fact, when $T$ is too small, the set of CHs will be re-computed too frequently leading to an instability in the network because of the frequent changes of sensor states. On the other hand, when $T$ is too big, the adaptivity aspect of the protocol will fade out due to the relatively quick change in residual energies. Without loss of generality, we chose $T = 1$ unit. To measure the sensors' energy dissipation during a time period $T$, we assumed a dense network and we used a simplified form of the log-distance path loss channel model described by Heinzelman et al. (2002) : we used the free-space fading model for both regular sensors and CHs. Thus, the energy dissipated by a sensor to transmit $l$ bits over a range $R$ is : $E_{Tx} = l.E_e + l.\epsilon.R^2$ and the energy spend to receive an $l$-bits message is : $E_{Rx} = l.E_e$ where $E_e$ is the energy dissipated by the radio hardware to transmit or receive the signal and $\epsilon.R^2$ is the amplifier's energy necessary to transmit 1 bit of data over a relatively short distance (Actually, $\epsilon = \frac{1}{G_e.G_r}.(\frac{4.\pi}{\lambda})^2$ where $G_t$ is the gain of the transmitter's antenna, $G_r$ is the gain of
the receiver's antenna and $\lambda$ is the wavelength). Thus, the energy dissipated by a CH to transmit $l$ bits of data over its range $R^{CH}$ and to receive and aggregate an $l$-bit length message from each of the regular sensors connected to it, is :

$$E_{CH} = l.E_e + l.\epsilon.(R_t^{CH})^2 + N_{CH}.l.E_e + N_{CH}.l.E_A$$

where $E_A$ is the energy dissipated in data aggregation and $N_{CH}$ is the number of regular sensors connected to the CH.

For our simulations, we considered the same parameter values as those used by Heinzelman et al. (2002), that are : $\epsilon = 10pJ/bit/m^2$, $E_e = 50nJ/bit$ and $E_A = 50nJ/bit/signal$. We also considered a unique data length value of 100 bytes for all messages.

To evaluate the performance of EECF, we implemented it in C++ and we first studied the effect of the score coefficients $\alpha$ and $\beta$ on the network lifetime and the cluster head ratio (number of elected CHs with respect to the total number of sensors). Then, we compared EECF to a recently published clustering protocol : EESH (Zhou et al., 2007). As performance metrics, we chose the network lifetime and the ratio of CHs with respect to the total number of sensors. The second metric assesses the efficiency of our protocol in terms of the minimum number of CHs required to fulfill a fully clustered network. For performance evaluation, we considered 4 grid networks of increasing sizes, composed, respectively, of 100, 400, 900 and 1600 sensors.

### 5.6.2 Effect of the score coefficient $\alpha$ on performance

As we can see from the protocol description, the weighting coefficient $\alpha$ is not analytically linked to the network lifetime or the cluster head ratio. In fact, $\alpha$ will only "push" nodes having a good tradeoff between the degree and the residual energy to be elected CHs but we cannot derive any exact mathematical relationship between
<figure><img src="image_33.png" /><figcaption>FIGURE 5.4 Network lifetime generated by EECF function of $\alpha$, for different values of $R_t$</figcaption></figure>

$\alpha$ and the network lifetime, or the cluster head ratio. In fact, these two metrics are average values that also depend on the energy map (residual energy of each sensor with respect to its neighbors’ residual energies). Hence, we empirically studied the effect of the weighting coefficient $\alpha$ on the network lifetime and the cluster head ratio.

Figure 5.4 depicts the variation of the network lifetime with respect to $\alpha$ for two values of the transmission range : $R_t = 1$ and $R_t = 3$. We can see that for $\alpha =0.1$, an optimal value of the network lifetime can be obtained. This small value of $\alpha$ means that the residual energy is a more important factor in CH election than the
<figure><img src="image_34.png" /><figcaption>FIGURE 5.5 Ratio "Number of CHs/Total number of sensors" generated by EECF function of $\alpha$, for different values of $R_t$</figcaption></figure>

degree. However, since the optimal value of $\alpha$ in not zero, the degree still has a small significance. This result was pretty expectable in our case because we considered a grid network where all nodes have almost the same degree (except edge nodes). The optimal value of $\alpha$ is roughly the same for $R_t = 1$ and $R_t = 3$ because, even if the sensors have a greater degree for $R_t = 3$, sensors still have the same degree as their neighbors. As far as the CH ratio is concerned, Figure 5.5 shows that the bigger the value of $\alpha$, the lower (the better) this ratio. This is also expectable because higher values of $\alpha$ favor the election of nodes having the highest degree as CHs, regardless of their residual energies, thus reducing the overall number of CHs. In the next paragraph, we will use the average value of $\alpha=0.5$ to compare our protocol to EESH.
<figure><img src="image_35.png" /><figcaption>FIGURE 5.6 Network lifetime generated by EECF vs. EESH, for different values of $R_t$</figcaption></figure>

### 5.6.3 Comparison of EECF and EESH in terms of network lifetime

To measure the network lifetime generated by EECF and EESH, we run these two protocols periodically, at instants $k.T$ ($k \in \mathbb{N}$) and we used $T$ as a measure unit of the network lifetime.

Figure 5.6 depicts the network lifetime generated by EECF and EESH, for 2 different values of the transmission range, $R_t = 1$ and $R_t = 3$. We can see that EECF outperforms EESH by approximately 60% for $R_t = 1$ and more than 70% for $R_t = 3$. This could be explained by the two-hops information (resulting from the 3-way message exchange) every sensor uses to make its decision, and which generates
<figure><img src="image_36.png" /><figcaption>FIGURE 5.7 Ratio "Number of CHs/Total number of sensors" generated by EECF vs. EESH, for different values of $R_t$</figcaption></figure>

better-cost clusters. We also notice that the better performance of EECF compared to EESH is more emphasized for $R_t = 3$ than for $R_t = 1$. This is because, the bigger the transmission range, the more potential CHS are reached by each sensor and thus EECF has more clustering possibilities and is more likely to find a better configuration compared to EESH.
### 5.6.4 Comparison of EECF and EESH in terms of the CH ratio (Number of CHs/Total number of sensors)

The ratio "Number of CHs/Total number of sensors" expresses the efficiency of the protocol in terms of the number of CHs required to cluster the network. Figure 5.7 depicts the ratio of CHs for EECF vs. EESH, for $R_t = 1$ and for $R_t = 3$. We can see that, for large-scale configurations (400 sensors and more), EECF outperforms EESH by approximately 20% for $R_t = 1$ and $R_t = 3$. This means that our protocol is able to find admissible configurations with less CHs, which is very consistent with the results regarding the network lifetime, because using less CHs will, in average, increase the network lifetime. Here again, the better CH ratio of EECF compared to EESH can be explained by the two-hops information that every sensor uses to make its clustering-related decision.

## 5.7 Conclusion

In this paper, we proposed EECF, a novel dynamic distributed cluster formation protocol for sensor networks. Our protocol is based on a three-way message exchange between every sensor and its one-hop neighbors and ends up with a clustered network where the overlay graph composed of CHs is connected when the CH transmission range is equal or greater than three times the transmission range of non-CH sensors. We showed that EECF has a message exchange complexity of $O(1)$ and a worst-case convergence time complexity of $O(N)$. Performance evaluation showed that EECF provides a better network lifetime and a better ratio "Number of CHs/Total number of sensors" than EESH, a recently published clustering protocol for wireless sensor networks.

As for future research, we intend to extend our protocol to sensor networks with
multiple transmission ranges, where sensors can reach more neighbors using higher transmission power (at higher cost). Furthermore, we plan on extending our protocol to handle multi-level clustering.
# CHAPITRE 6

# DISCUSSION GÉNÉRALE

Dans ce chapitre, nous faisons une synthèse de nos travaux et contributions en regard de nos objectifs de recherche. Nous discutons également l'approche méthodologique employée et nous analysons les résultats obtenus.

## 6.1 Synthèse des travaux

Comme dans tout travail de recherche, nous avons commencé cette thèse par une analyse critique de l'état de l'art dans le domaine. Ainsi, nous avons consacré le Chapitre 2 à une revue de littérature exhaustive des mécanismes d'optimisation de l'énergie dissipée et de maximisation de la durée de vie dans les réseaux de capteurs sans fil, et ce, à tous les niveaux du modèle OSI, ainsi que les mécanismes inter-couches (cross-layer). Cet état de l'art nous a permis de déceler les faiblesses et les lacunes des mécanismes existants afin de dégager quelques problèmes ouverts pertinents qui ont servi comme orientations de recherche pour cette thèse. Ensuite, nous avons traité dans nos chapitres 3, 4 et 5, trois problématiques différentes, présentées sous forme de trois articles scientifiques de revue.

Dans notre premier article, nous avons considéré un RCSF formé de nœuds déployés aléatoirement pour surveiller une zone donnée, et où chaque capteur pouvait être soit éteint, soit TG, soit allumé mais non TG, chacun de ces états ayant une consommation énergétique spécifique. Nous avons abordé la problématique de la maximisation de la durée de vie du RCSF par deux techniques : l'extinction de certains capteurs non nécessaires à la couverture de la zone surveillée et la structuration du réseau en
grappes, les TG étant les seuls nœuds pouvant relayer les données. Nous avons alors cherché la configuration optimale des capteurs, c'est à dire l'allocation optimale des états (éteint, TG, allumé mais non TG) aux capteurs, qui permet de maximiser la durée de vie du réseau tout en respectant les contraintes de couverture totale de la zone surveillée, de structuration en grappes et de routage entre les TG, qui sont en fait des contraintes très réalistes dans la pratique. En effet, l'une des applications phare des RCSF étant la surveillance des espaces, il est important d'assurer qu'un nombre suffisant de capteurs soit allumé pour assurer la couverture totale de la zone surveillée, le reste des capteurs "redondants" pouvant être éteints pour économiser de l'énergie. Par ailleurs, la formation de grappes permet, elle aussi, de conserver l'énergie, donc chaque capteur, quand il est allumé mais pas TG, doit avoir au moins une TG dans son voisinage. Enfin, les TG désignées doivent pouvoir véhiculer les données au centre de traitement en les faisant relayer par d'autres TG voisines. Ces TG doivent donc appartenir à un arbre de recouvrement. Trouver la configuration optimale qui satisfait à toutes ces contraintes fut l'objectif central de notre premier article. Pour y parvenir, nous avons modélisé notre problème sous forme de problème en nombres entiers, que nous avons prouvé NP-complet. Ensuite, nous avons proposé un mécanisme à base d'heuristique taboue pour résoudre ce modèle en des temps de calcul raisonnables.

Dans notre deuxième article présenté au Chapitre 4, nous avons traité le problème de la maximisation de la durée de vie d'un RCSF dont les nœuds sont munis de plusieurs puissances de transmission. Un capteur peut donc atteindre un plus grand nombre de TG potentielles en utilisant une plus grande puissance de transmission, mais à un coût énergétique plus élevé. Un niveau de complexité est ajouté par rapport au premier article : il s'agit de trouver la configuration optimale des états (éteint, TG, allumé mais pas TG) des capteurs mais aussi des puissances de transmission qui maximise la durée de vie du réseau, toujours sous la contrainte de couverture totale
de la zone surveillée. Ici, chaque capteur doit être soit une TG, soit connecté à une
TG voisine qu'il devra pouvoir atteindre moyennant la puissance de transmission qui
lui aura été allouée. Nous modélisons notre problème sous forme d'un problème d'op-
timisation à variables entières, que nous démontrons NP-complet. Nous proposons
ensuite un algorithme à base d'heuristique taboue pour trouver une solution proche
de l'optimalité en un temps de calcul raisonnable.

Dans notre troisième article présenté au chapitre 5, nous avons proposé un nouvel
algorithme réparti de formation de grappes dans les RCSF. Notre algorithme dif-
fère de la majorité des algorithmes proposés dans la littérature par la pertinence
des informations récoltées par chaque capteur de la part de ses voisins. Grâce à un
mécanisme d'échange de fonctions score, chaque capteur collecte des informations
compilées reflétant l'aptitude de ses voisins directs (1-hop neighbors) et ceux séparés
par deux sauts (2-hops neighbors), à devenir TG. Ces informations seront utilisées,
par chaque capteur, pour affiner sa prise de décision relativement à son état (devenir
TG ou non). Comme chaque capteur a plus de "visibilité" sur son voisinage, sa prise
de décision est meilleure, ce qui fait qu'à l'échelle du réseau, notre algorithme donne
de meilleurs résultats, en termes de durée de vie du réseau, que d'autres algorithmes
bien connus dans la littérature.

## 6.2 Méthodologie

Dans cette thèse, nous avons proposé de nouveaux algorithmes et mécanismes à base
d'heuristiques. Ces mécanismes et algorithmes ont été validés par des preuves de
concept basées, tantôt sur des preuves théoriques, tantôt sur des simulations expéri-
mentales. Afin d'évaluer la performance des mécanismes proposés, nous avons utilisé
des outils de simulation reconnus dans la communauté scientifique tels que ILOG
CPLEX (ILOG, 2009), le simulateur de réseaux OPNET ainsi que l'environnement
de développement Visual C++. Par ailleurs, pour générer nos résultats, nous avons suivi un mode opératoire formel et précis basé sur plusieurs batteries de tests qui ont permis de générer les valeurs moyennes ayant servi à la validation des résultats générés par nos heuristiques et algorithmes.

## 6.3 Analyse des résultats

Dans notre premier article, les résultats de simulation ont montré que l'heuristique que nous avons proposée génère des solutions proches de la solution optimale trouvée, moyennant l'outil de résolution mathématique CPLEX, et qu'elle donne de meilleures performances que d'autres algorithmes répartis de formation de grappes proposés dans la littérature scientifique récente. Dans notre second article, les simulations démontrent que notre heuristique génère de bons résultats, comparée à la solution optimale générée par CPLEX. Et comparé à HEED, un protocole réparti de formation de grappes dans les RCSF, notre algorithme génère de meilleurs résultats en termes de durée de vie du réseau et de répartition de l'énergie dissipée sur les capteurs. Dans notre troisième article, Les simulations montrent que notre nouvel algorithme réparti de formation de grappes donne de meilleurs résultats, en termes de durée de vie du réseau, que d'autres algorithmes répartis proposés dans la littérature scientifique récente.
# CHAPITRE 7

## CONCLUSION

### 7.1 Sommaire des contributions

Cette thèse a donné lieu à trois principales contributions :

- La modélisation et la résolution du problème de planification optimale des états des capteurs dans un RCSF, dans le but de maximiser la durée de vie du réseau, sous la triple contrainte de couverture, formation de grappes et routage. En effet, plusieurs travaux ont traité séparément certaines de ces contraintes comme, par exemple, la formation optimale de grappes (sans contrainte de couverture), ou encore la maximisation de la durée de vie du réseau par la sélection d'un sous-ensemble optimal de couverture, devant former un graphe connecté, pour qu'une route existe entre chaque paire de capteurs. Cependant, la maximisation de la durée de vie du réseau par une planification optimale des rôles des capteurs, tout en garantissant à la fois les trois contraintes fortement reliées de couverture, de formation de grappes et d'existence d'une arbre de recouvrement reliant les TG sélectionnées, constitue une contribution scientifique intéressante au domaine des RCSF. De plus, les solutions du modèle proposé constituent une borne supérieure, en termes de durée de vie du réseau, pour tout protocole réparti abordant le même problème. Notre modèle peut donc servir comme référence de comparaison pour évaluer la performance d'autres protocoles répartis traitant le même problème.

- La modélisation et la résolution du problème de maximisation de la durée de vie du réseau par formation de grappes dans un contexte de puissances de transmission variables, tout en assurant la couverture de la zone surveillée par le RCSF. Les solutions à ce problème offrent une borne supérieure, en termes de durée de vie du
réseau, aux algorithmes répartis traitant le même problème. En effet, la majorité
des protocoles répartis proposés dans la littérature, bien que plus adaptés aux
réseaux de grande taille que les algorithmes centralisés, sont généralement basés sur
la connaissance, très limitée, des paramètres des nœuds voisins. Ces informations
étant locales à chaque nœud, elles ne permettent pas d'aboutir à une configuration
optimale. Par contre, un algorithme centralisé, ayant une connaissance globale
des paramètres du réseau, génère des solutions optimales qui offrent une borne
supérieure sur la durée de vie du réseau, qui peut servir comme base d'évaluation
des performances des algorithmes répartis.

- La proposition d'un nouvel algorithme réparti de formation de grappes dans les réseaux de capteurs, qui génère de meilleures performances, en termes de durée de vie du réseau, que d'autres algorithmes répartis populaires dans la littérature scientifique relative au sujet. Notre algorithme constitue donc une amélioration de l' existant en ce qui a trait aux algorithmes répartis de formation de grappes dans les RCSF.

7.2 Limitation des travaux

Malgré les contributions énoncées ci-dessus, notre travail présente certaines limita-
tions dont nous pouvons citer :

- Dans les chapitres 3 et 4, nous avons fait l'hypothèse d'un rayon de détection uniforme (i.e, tous les événements qui se produisent à l'intérieur du rayon de détection d'un capteur ont la même probabilité d'être détectés par le capteur en question quelle que soient leurs distances de celui-ci). Cette hypothèse, bien que simplificatrice et souvent considérée dans la littérature, n'est pas toujours valide en pratique car la probabilité de detection d'un événement par un capteur peut
diminuer lorsque la distance entre la capteur et l'événement augmente. Toutefois, nos modèles mathématiques peuvent facilement être adaptés à une détection probabiliste.

- Le caractère centralisé de nos modèles mathématiques 4.3 et 4.1, bien qu'ayant l'avantage de produire des solutions optimales (résolution exacte) ou proches de l'optimalité (heuristiques), ne s'adapte pas au passage à l'échelle (scalability). Dans la pratique, les protocoles répartis sont souvent préférés quand il s'agit de réseaux de grande taille. Toutefois, nos algorithmes centralisés ont le grand avantage d'offrir une borne supérieure, en termes de durée de vie du réseau, aux algorithmes répartis qui donnent généralement des résultats sous-optimaux. De plus, si la taille du réseau est grande mais stable, le centre de traitement peut être dimensionné en termes de processeur et de mémoire, en fonction de la taille du réseau pour résoudre le problème en des temps de calcul raisonnables.

- Dans nos travaux, nous avons abordé la minimisation de l'énergie dépensée par l'application d'une technique intégrée qui associe la désactivation de certains nœuds non nécessaires pour la couverture de la zone surveillée et la formation optimale de grappes. Nous nous sommes alors basés sur l'hypothèse que les liens sans fil au niveau de la couche MAC sont idéaux et nous avons fait abstraction des collisions et des retransmissions, gourmandes en énergie, qui peuvent avoir lieu au niveau de la couche 2. Les pertes et retransmissions de paquets sont souvent dues aux collisions et aux interférences autour des capteurs. Considérer de tels phénomènes dans l'équation de l'énergie va certainement améliorer la pertinence du problème étudié. Par exemple, une planification temporelle optimisée des transmissions et la prise en compte de l'interférence, surtout dans le cas des puissances de transmission variables, sont des sujets qui ne sont pas encore bien maîtrisés dans la communauté scientifique et constituent donc des avenues très intéressantes de recherche future.
## 7.3 Indication des travaux futurs

Même si certaines implantations de réseaux de capteurs ont vu le jour les dernières années, elles sont encore en phase de recherche et beaucoup de défis qui leur sont associés demeurent encore posés. Dans ce qui suit, nous allons citer quelques pistes de recherche future en relation avec les travaux présentés dans cette thèse.

Une première piste de recherche serait d'implementer nos heuristiques à l'aide d'un simulateur de réseaux tel que OPNET ou NS-2, afin de mesurer la charge réseau générée par la transmission des données inhérentes au mécanisme d'allocation des états, comme les valeurs des énergies résiduelles, l'état alloué à un capteur ou encore la puissance de transmission allouée à celui-ci. La simulation des mécanismes proposés permettra également de mesurer, empiriquement, les retransmissions dues aux collisions et aux interférences et d'en déduire des valeurs moyennes plus réalistes de l'énergie dissipée par chaque capteur.

Une seconde piste consisterait à étendre notre modèle pour qu'il prenne en charge les modèles de détection probabilistes. Ceci consiste à considérer que le rayon de détection d'un capteur est divisé en plusieurs anneaux concentriques et que des probabilités de détection d'événements différentes leur sont associées.

Enfin, une autre piste serait d'aborder le problème d'allocation optimale des états dans les RCSF en tenant compte de l'énergie de transition entre les états "éteint" et "allumé". Sur le long terme, cette énergie de transition n'est pas négligeable (Raghunathan et al., 2002) et le séquencement des états devient donc important. Il serait intéressant de bâtir un planning optimisé des états des capteurs sur *N* périodes de temps, tout en garantissant à chaque période les contraintes exigées par l'application, telles que la couverture, la structuration en grappes et le routage entre les TG. Un tel planning sur le temps peut ne pas être fait en temps réel et donc le temps de
calcul relativement important de la solution centralisée deviendrait moins problématique. Nous avons publié une première ébauche de solution à une version simplifiée de ce problème (Chamam et Pierre, 2007b), qui ne prend pas en considération ni la structuration en grappes du réseau, ni le routage entre les têtes de grappes. Il serait donc intéressant d'aborder le problème général avec toutes ses contraintes.
# CONTRIBUTIONS À LA RECHERCHE

Cette thèse a donné lieu à plusieurs publications dans des journaux scientifiques et à des articles de conférences. En voici la liste :

## Articles publiés dans des revues scientifiques :

1. CHAMAM A. et PIERRE, S. (2009). "On the Planning of Wireless Sensor Networks: Energy-Efficient Clustering under the Joint Routing and Coverage Constraint". *IEEE Transactions on Mobile Computing*, **8**, 1077-1086. DOI : 10.1109/TMC.2009.16.

2. CHAMAM A. et PIERRE, S. (2009). "A distributed energy-efficient clustering protocol for wireless sensor networks", Accepté pour publication dans *Computers & Electrical Engineering (Elsevier)* (publié en ligne le 05 Mai 2009). ISSN 0045-7906.
DOI : 10.1016/j.compeleceng.2009.03.008.

## Articles soumis à des revues scientifiques :

3. CHAMAM A. et PIERRE, S. "Energy-Efficient Clustering with Transmit Power Assignment under Coverage Constraint in Wireless Sensor Networks". Soumis pour publication à la revue *Wireless Communications and Mobile Computing* (Wiley).
## Articles de conférences :

1. CHAMAM A. et PIERRE S. (2009). "A Distributed Energy-Efficient Cluster Formation Protocol for Wireless Sensor Networks". *IEEE Consumer Communications and Networking Conference (CCNC)*. 1-5.

DOI: 10.1109/CCNC.2009.4784896

2. CHAMAM A. et PIERRE S. (2008). "Power-Efficient Clustering in Wireless Sensor Networks under Coverage Constraint Networking and Communications". *IEEE International Conference on Wireless and Mobile Computing (WIMOB)*. 460-465. DOI: 10.1109/WiMob.2008.78

3. CHAMAM A. et PIERRE S. (2007). "Energy-Efficient State Scheduling for Maximizing Sensor Network Lifetime under Coverage Constraint". *IEEE International Conference on Wireless and Mobile Computing (WIMOB)*. 63-63.

DOI: 10.1109/WIMOB.2007.4390857

4. Chamam A. et Pierre, S. (2007). "Optimal Scheduling of Sensors' States to Maximize Network Lifetime in Wireless Sensor Networks". *IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS)*. 1-6. DOI:

DOI: 10.1109/MOBHOC.2007.4428707

5. Chamam A. et Pierre, S. (2007). "Dynamic sensor activation for maximizing network lifetime under coverage constraint". *International Symposium on Communications and Information Technologies (ISCIT)*. 971-976. DOI:

DOI: 10.1109/ISCIT.2007.4392156
BIBLIOGRAPHIE

AHMED, N., KANHERE, S. et JHA, S. (2005). "Probabilistic coverage in wireless sensor networks". *Proc. IEEE Conference on Local Computer Networks*. 678–681.

AKAN, O. B. et AKYILDIZ, I. F. (2005). "Event-to-sink reliable transport in wireless sensor networks". *IEEE/ACM Transactions on Networking*, **13**, 1003–1016.

AKKAYA, K. et YOUNIS, M. (2005). "A survey on routing protocols for wireless sensor networks". *Elsevier Ad Hoc Networks*, **3**, 325–349.

AKYILDIZ, I., SU, W., SANKARASUBRAMANIAM, Y. et CAYIRCI, E. (2002). "A survey on sensor networks". *IEEE Communications Magazine*, **40**, 102–114.

AL-KARAKI, J. et KAMAL, A. (2004). "Routing techniques in wireless sensor networks : a survey". *IEEE Wireless Communications*, **11**, 6–28.

ANASTASI, G., CONTI, M., FRANCESCO, M. D. et PASSARELLA, A. (2009). "Energy conservation in wireless sensor networks : A survey". *Elsevier Ad Hoc Networks*, **7**, 537–568.

ARBOLEDA, L. et NASSER, N. (2006). "Comparison of clustering algorithms and protocols for wireless sensor networks". *Proc. Canadian Conference on Electrical and Computer Engineering (CCECE)*. 1787–1792.

ARISHA, K., YOUSSEF, M. et YOUNIS, M. (2002). "Energy-aware TDMA-based MAC for sensor networks". *Proc. IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking (IMPACCT)*.

ASLAM, J., LI, Q. et RUS, D. (2002). "Three power-aware routing algorithms for sensor networks". *Wireless Communications and Mobile Computing*, **3**, 187–208.
BANDYOPADHYAY, S. et COYLE, E. (2003). "An energy efficient hierarchical clustering algorithm for wireless sensor networks". *Proc. Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)*. vol. 3, 1713–1723.

CARDEI, M., THAI, M., LI, Y. et WU, W. (2005). "Energy-efficient target coverage in wireless sensor networks". *Proc. Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)*. vol. 3, 1976–1984.

CARLE, J. et SIMPLOT-RYL, D. (2004). "Energy-efficient area monitoring for sensor networks". *Computer*, 37, 40–46.

CAYIRCI, E. (2004). "Wireless sensor networks". In: D. Katsaros et al. (éd), *Wireless information highways* (pp. 273-301). Hershey: Idea group inc.

CERPA, A. et ESTRIN, D. (2004). "ASCENT: adaptive self-configuring sensor networks topologies". *IEEE Transactions on Mobile Computing*, 3, 272–285.

CHAMAM, A. et PIERRE, S. (2007a). "Dynamic sensor activation for maximizing network lifetime under coverage constraint". *Proc. International Symposium on Communications and Information Technologies (ISCIT)*. 971–976.

CHAMAM, A. et PIERRE, S. (2007b). "Optimal scheduling of sensors’ states to maximize network lifetime in wireless sensor networks". *Proc. IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS)*. 1–6.

CHAMAM, A. et PIERRE, S. (2009a). "A distributed energy-efficient clustering protocol for wireless sensor networks". *Elsevier Computers and Electrical Engineering (To appear)*.

CHAMAM, A. et PIERRE, S. (2009b). "On the planning of wireless sensor networks: Energy-efficient clustering under the joint routing and coverage constraint". *IEEE Transactions on Mobile Computing*, 8, 1077–1086.
CHATTERJEE, M., DAS, S. et TURGUT, D. (2002). "WCA : A weighted clustering algorithm for mobile ad hoc networks". *Journal of Cluster Computing (Special Issue on Mobile Ad hoc Networks)*, 5, 193-204.

CHONG, C.-Y. et KUMAR, S. (2003). "Sensor networks : evolution, opportunities, and challenges". *91*, 1247-1256.

CHOU, J., PETROVIC, D. et RAMCHANDRAN, K. (2004). "A distributed and adaptive signal processing approach to exploiting correlation in sensor networks". *Elsevier Ad Hoc Networks*, 2, 387-403.

CHU, H.-C. et JAN, R.-H. (2007). "A GPS-less, outdoor, self-positioning method for wireless sensor networks". *Elsevier Ad Hoc Networks*, 5, 547-557.

CI, S., SHARIF, H. et NULI, K. (2005). "Study of an adaptive frame size predictor to enhance energy conservation in wireless sensor networks". *IEEE Journal on Selected Areas in Communications*, 23, 283-292.

CMOP (2009). "Projet CORIE", consulté le 02 juin 2009, tiré de :
http://www.cccalmr.ogi.edu/.

CORMEN, T., LEISERSON, C., RIVEST, R. et STEIN, C. (2001). *Introduction to Algorithms*. MIT Press and McGraw-Hill, seconde édition.

CORNELL, U. (2009). "Projet COUGAR", consulté le 06 juin 2009, tiré de :
http://www.cs.cornell.edu/bigreddata/cougar/index.php.

DING, P., HOLLIDAY, J. et CELIK, A. (2005). "Distributed energy-efficient hierarchical clustering for wireless sensor networks". *Distributed Computing in Sensor Systems*, 32-339.

ELSON, J. et ESTRIN, D. (2001). "Random, ephemeral transaction identifiers in dynamic sensor networks". *Proc. 21st International Conference on Distributed Computing Systems*. 459-468.
HEDETNIEMI, S. et LIESTMAN, A. (1988). "A survey of gossiping and broadcasting in communication networks". *IEEE Networks*, **18**, 319-349.

HEFEEDA, M. et AHMADI, H. (2007). "A probabilistic coverage protocol for wireless sensor networks". *Proc. IEEE International Conference on Network Protocols (ICNP)*. 41-50.

HEINZELMAN, W., CHANDRAKASAN, A. et BALAKRISHNAN, H. (2000). "Energy-efficient communication protocol for wireless microsensor networks". *Proc. 33rd Annual Hawaii International Conference on System Sciences*. vol. 2, 1-10.

HEINZELMAN, W., CHANDRAKASAN, A. et BALAKRISHNAN, H. (2002). "An application-specific protocol architecture for wireless microsensor networks". *IEEE Transactions on Wireless Communications*, **1**, 660-670.

HEINZELMAN, W., KULIK, J. et BALAKRISHNAN, H. (1999). "Adaptive protocols for information dissemination in wireless sensor networks". *Proc. 5th annual ACM/IEEE international conference on Mobile computing and networking (Mo biCom)*. 174-185.

HWANG, S.-F., SU, Y.-Y., LIN, Y.-Y. et DOW, C.-R. (2006). "A cluster-based coverage-preserved node scheduling scheme in wireless sensor networks". *Proc. 3rd Annual International Conference on Mobile and Ubiquitous Systems*. 1-7.

ILOG (2009). "ILOG CPLEX", consulté le 02 juin 2009, tiré de : http://www.ilog.com/products/cplex/.

INANC, M., MAGDON-ISMAIL, M. et YENER, B. (2003). "Power optimal connectivity and coverage in wireless sensor networks", vol. TR-03-06. Department of Computer Science, Rensselaer Polytechnic Institute.
INTANAGONWIWAT, C., GOVINDAN, R. et ESTRIN, D. (2000). "Directed diffusion: A scalable and robust communication paradigm for sensor networks". *ACM International Conference on Mobile Computing and Networking (MobiCom)*. 56–67.

KARL, H. et WILLIG, A. (2005). "Protocols and Architectures for Wireless Sensor Networks". John Wiley & Sons.

KOHVAKKA, M., KUORILEHTO, M., HÄNNIKÄINEN, M. et HÄMÄLÄINEN, T. D. (2006). "Performance analysis of ieee 802.15.4 and zigbee for large-scale wireless sensor network applications". *Proc. 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks (PEWASUN)*. ACM, 48–57.

KUBISCH, M., KARL, H., WOLISZ, A., ZHONG, L. et RABAEY, J. (2003). "Distributed algorithms for transmission power control in wireless sensor networks". *Proc. IEEE Wireless Communications and Networking (WCNC)*. vol. 1, 558–563.

KWON, T. et GERLA, M. (1999). "Clustering with power control". *Proc. IEEE Military Communications Conference (MILCOM)*. vol. 2, 1424–1428.

LI, X.-Y., WAN, P.-J. et FRIEDER, O. (2002). "Coverage in wireless ad-hoc sensor networks". *Proc. IEEE International Conference on Communications (ICC)*. vol. 5, 3174–3178.

LINDSEY, S. et RAGHAVENDRA, C. (2002). "PEGASIS: Power-efficient gathering in sensor information systems". *Proc. IEEE Aerospace Conference*. vol. 3, 1125–1130.

LIU, J.-S. et LIN, C.-H. R. (2005). "Energy-efficiency clustering protocol in wireless sensor networks". *Elsevier Ad Hoc Networks*, 3, 371–388.
LU, J., WANG, J. et SUDA, T. (2006). "Scalable coverage maintenance for dense wireless sensor networks". *Proc. 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON)*. vol. 2, 651–660.

MADDEN, S. R., FRANKLIN, M. J., HELLERSTEIN, J. M. et HONG, W. (2005). "TinyDB : an acquisitional query processing system for sensor networks". *ACM Transactions on Database Systems*, 30, 122–173.

MAINWARING, A., CULLER, D., POLASTRE, J., SZEWCZYK, R. et ANDERSON, J. (2002). "Wireless sensor networks for habitat monitoring". *Proc. 1st ACM international workshop on Wireless sensor networks and applications (WSNA)*. 88–97.

MHATRE, V. et ROSENBERG, C. (2004a). "Design guidelines for wireless sensor networks : communication, clustering and aggregation". *Elsevier Ad Hoc Networks*, 2, 45–63.

MHATRE, V. et ROSENBERG, C. (2004b). "Homogeneous vs heterogeneous clustered sensor networks : a comparative study". *Proc. IEEE International Conference on Communications*. vol. 6, 3646–3651.

MHATRE, V., ROSENBERG, C., KOFMAN, D., MAZUMDAR, R. et SHROFF, N. (2005). "A minimum cost heterogeneous sensor network with a lifetime constraint". *IEEE Transactions on Mobile Computing*, 4, 4–15.

NGAN, H., ZHU, Y., NI, L. et RENYI, X. (2005). "Stimulus-based adaptive sleeping for wireless sensor networks". *Proc. International Conference on Parallel Processing (ICPP)*. 381–388.

PANICHPAPIBOON, S., FERRARI, G. et TONGUZ, O. (2006). "Optimal transmit power in wireless sensor networks". *IEEE Transactions on Mobile Computing*, 5, 1432–1447.
PANTAZIS, N. et VERGADOS, D. (2007). "A survey on power control issues in wireless sensor networks". *IEEE Communications Surveys & Tutorials*, **9**, 86–107.

PATWARI, N., ASH, J., KYPEROUNTAS, S., HERO, A.O., I., MOSES, R. et CORREAL, N. (2005). "locating the nodes: cooperative localization in wireless sensor networks". *IEEE Signal Processing Magazine*, **22**, 54–69.

POLASTRE, J., HILL, J. et CULLER, D. (2004). "Versatile low power media access for wireless sensor networks". *Proc. 2nd international conference on Embedded networked sensor systems (SenSys)*. ACM, New York, NY, USA, 95–107.

POTTIE, G. J. et KAISER, W. J. (2000). "Wireless integrated network sensors". *ACM Communications*, **43**, 51–58.

RAGHUNATHAN, V., SCHURGERS, C., P., S. et SRIVASTAVA, M. (2002). "Energy-aware wireless microsensor networks". *IEEE Signal Processing Magazine*, **19**, 40–50.

RAJENDRAN, V., OBRACZKA, K. et GARCIA-LUNA-ACEVES, J. J. (2003). "Energy-efficient collision-free medium access control for wireless sensor networks". *Proc. 1st international conference on Embedded networked sensor systems (SenSys)*. ACM, New York, NY, USA, 181–192.

RUDAFSHANI, M. et DATTA, S. (2007). "Localization in wireless sensor networks". *Proc. 6th international conference on information processing in sensor networks (IPSN)*. ACM, New York, NY, USA, 51–60.

SEDDIK-GHALEB, A., GHAMRI-DOUDANE, Y. et SENOUCI, S.-M. (2006). "A performance study of TCP variants in terms of energy consumption and average goodput within a static ad hoc environment". *Proc. International Conference on Wireless Communications and Mobile Computing (IWCMC)*. ACM, New York, NY, USA, 503–508.
SHAH, R. et RABAEY, J. (2002). "Energy aware routing for low energy ad hoc sensor networks". *Proc. IEEE Wireless Communications and Networking Conference (WCNC)*. vol. 1, 350–355.

SHEN, C.-C., SRISATHAPORNPHAT, C. et JAIKAEO, C. (2001). "Sensor information networking architecture and applications". *IEEE Personal Communications, 8*, 52–59.

SLEPIAN, D. et WOLF, J. (1973). "Noiseless coding of correlated information sources". *IEEE Transactions on Information Theory, 19*, 471–480.

STANN, F. et HEIDEMANN, J. (2003). "RMST : reliable data transport in sensor networks". *Proc. 1st IEEE International Workshop on Sensor Network Protocols and Applications*. 102–112.

SUN, B., GAO, S.-X., CHI, R. et HUANG, F. (2008). "Algorithms for balancing energy consumption in wireless sensor networks". *Proc. 1st ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing (FOWANC)*. ACM, New York, NY, USA, 53–60.

TIAN, D. et GEORGANAS, N. (2002). "A coverage-preserving node scheduling scheme for large wireless sensor networks". *Proc. 1st ACM international workshop on Wireless sensor networks and applications (WSNA)*. ACM, New York, NY, USA, 32–41.

TINYOS (2009). "Projet tinyOS", consulté le 06 juin 2009, tiré de :
http://www.tinyos.net.

WAN, C.-Y., CAMPBELL, A. T. et KRISHNAMURTHY, L. (2002). "PSFQ : a reliable transport protocol for wireless sensor networks". *Proc. 1st ACM international workshop on Wireless sensor networks and applications (WSNA)*. ACM Press, 1–11.
WYNER, A. et ZIV, J. (1976). "The rate-distortion function for source coding with side information at the decoder". *IEEE Transactions on Information Theory*, **22**, 1–10.

XING, G., WANG, X., ZHANG, Y., LU, C., PLESS, R. et GILL, C. (2005). "Integrated coverage and connectivity configuration for energy conservation in sensor networks". *ACM Transactions on Sensor Networks*, **1**, 36–72.

XU, Y., HEIDEMANN, J. et ESTRIN, D. (2001). "Geography-informed energy conservation for ad hoc routing". *Proc. 7th annual international conference on Mobile computing and networking (MobiCom)*. 70–84.

YAN, T., HE, T. et STANKOVIC, J. (2003). "Differentiated surveillance for sensor networks". *Proc. 1st international conference on Embedded networked sensor systems (SenSys)*. ACM, New York, NY, USA, 51–62.

YAO, Y. et GIANNAKIS, G. (2005). "Energy-efficient scheduling for wireless sensor networks". *IEEE Transactions on Communications*, **53**, 1333–1342.

YE, W., HEIDEMANN, J. et ESTRIN, D. (2004). "Medium access control with coordinated adaptive sleeping for wireless sensor networks". *IEEE/ACM Transactions on Networking*, **12**, 493–506.

YEN, Y.-S., HONG, S., CHANG, R.-S. et CHAO, H.-C. (2007). "An energy efficient and coverage guaranteed wireless sensor network". *Proc. IEEE Wireless Communications and Networking Conference (WCNC)*. 2923–2928.

YOUNIS, M. et ABBASI, A. (2007). "A survey on clustering algorithms for wireless sensor networks". *Elsevier Computer Communications*, **30**, 2826–2841.

YOUNIS, M., MUNSHI, P., GUPTA, G. et ELSHARKAWY, S. (2006). "On efficient clustering of wireless sensor networks". *Proc. IEEE Workshop on Dependability and Security in Sensor Networks and Systems (DSSNS)*. 10–91.
YOUNIS, O. et FAHMY, S. (2004). "HEED : a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks". *IEEE Transactions on Mobile Computing*, 3, 366-379.

ZHOU, W., CHEN, H.-M. et ZHANG, X.-F. (2007). "An energy efficient strong head clustering algorithm for wireless sensor networks". *Proc. International Conference on Wireless Communications, Networking and Mobile Computing (WiCom)*. 2584-2587.

ZIXIANG, X., LIVERIS, A. et CHENG, S. (2004). "Distributed source coding for sensor networks". *IEEE Signal Processing Magazine*, 21, 80-94.