Clustering is an important mechanism in large wireless sensor networks for obtaining scalability, reducing energy consumption and achieving better network performance. Most of the research in this area has focused on clustering based on physical parameters such as: energy, mobility, connectivity, density.., without taking in the count the data stored in each nodes. The main objective of this paper is to provide a useful fully-distributed algorithm for clustering that maximize the intra-cluster access, so we used a new heuristic parameter that combine between energy, mobility and number of data to select the Cluster-Heads. Our clustering strategy was compared with Lowest-ID Cluster Algorithm (LID) and the results show that our algorithm improves system performance and increases its life.
A mobile ad-hoc network (MANET) is a collection of mobile nodes that form a wireless
network without the existence of a fixed infrastructure or centralized administration. This
type of network can survive without any infrastructure and can work independently. Hosts
forming an ad hoc network can take equal responsibility in maintaining the network. Each
host provides routing services to other hosts to deliver messages to remote destinations. As
such a network requires no fixed infrastructure; it makes them better for deployment in a
volatile environment such as battlefield and disaster relief situations [
Unfortunately, the majority of thus works do not take into account the management of
requests in the system [
The algorithms differ on the criterion of selection of cluster-head. Among these algorithms
we have: the Lowest-ID Cluster Algorithm (LID) [
Proper management of queries in an ah-hoc network improves the reliability and
usefulness of the system but increases energy and reduces the lifetime of the nodes. The
majority of the works cited above focus on the physical characteristics of networks such as:
energy, connectivity, mobility, density, without taking into account the usefulness of the
network itself, that is to say the goal of building the networks, the type of services provided
and the types of treatments that can be achieved. In this paper, we propose a new algorithm
for non-overlapping clustering (see definition 2) to minimize power consumption and
response time in the system. Minimizing the access time of queries depend on the location
and distribution of data in the system [
Fig2: Second system: three colors in each cluster
The system is modeled by an undirected graph G = (V, E) where V is the set of network nodes and E models all the connections between these nodes. An edge (u, v) E if and only if nodes u and v can mutually receive transmissions of each other. This means that all links between nodes are bidirectional. In this case, we say that u and v are neighbors. The set of neighbors of a node v V is denoted Neighv. Each node u of the network is associated to a unique id and can communicate with its neighbors Neigh V. Each node is characterized by its mobility Mob and energy Energ remaining in the battery, it also can store zero or more data Di. Users can initiate read requests to access data in the system.
For the sake of clarity, we will use later in this paper the following notations: - Neighu: The neighbors of node u. - Energu: The remaining energy of the battery of node u. - Mobu: The mobility of the node u. - ListLu: List local data stored in the node u.
- ListTu: Total list of data stored in the node u and its neighbors (see formula 2).
Before describing our clustering algorithm in detail, we make the following assumptions,
which are common in the design of clustering algorithms for MANETs [
The network topology is static during the execution of the clustering algorithm. A packet transmitted by a node can be received correctly by all its neighbors in a finite time. - Each node has a unique id and knows its neighbors and vice versa. - The inter-cluster access is expensive compared to intra-cluster access in terms of: bandwidth and energy.
One more of these assumptions, we also assume that all requests made by users are of the
reading type [
The clustering algorithm consists of two steps: the selection of cluster-head and then the construction of clusters.
Given the interest in the concept of clustering and its undeniable contributions to improve the performance of an ad hoc network, the choice of the clustering mechanism is important. Thus, a clustering algorithm must first be able to select the appropriate nodes to ensure the functionality of the cluster-head. In our algorithm, the cluster-head selection is based on a new metric γ: γ = || || (1) - ã : Metric of clustering. - || ||: The cardinality of the data list of the node u and its neighbors.
ListTu = m u (2) - m: The number of neighbors of node u.
The node with the maximum γ in the neighborhood can be selected as a cluster-head. The rapport between energy and mobility helps to select a cluster-head which has a relatively high energy capacity and low mobility witch increase the stability of the system. Held that the parameter || || can elect a cluster-head which has a great opportunity to satisfy read requests in a single degree at the neighborhood.
Maximize the number of different data per cluster can be achieved by choosing as clusterhead node, which in its first neighborhood has many different data including its own list of data (Maximum ||
|| . For example in Figure 3, assuming that the report
/i [
We note that the node1 in its neighborhood contains a lot of data compared to its neighbors: | |ListT1 ||>||ListT3 ||>||ListT2 ||>||ListT0 | |, so node 1 is capable of meet a lot of requests (read requests) by at most one jump (zero jump if data is stored in the node itself). In this case, the node 1 will be selected as a cluster-head and broadcasts its status to its neighbors.
Fig3. A system with 4 nodes
The construction of the clusters is through periodic exchange of messages which we will call hello messages. Each network node exchanges with its neighbors the hello messages. Each hello message sent by a node u contains four values are: idu, Statutu , (Energu / Mobu) and ListLu. - idu: the identifier of the node u. - Statutu: The role of the node u in the system (See definition 3).
This message is also used for each node to verify the presence of its neighbors. Thus, if a node no longer receives hello message from a neighbor at the end of a period, it considers that this neighbor has disappeared. So each node waits a specified period in advance and it is assumed that during this period, all nodes have sent their hello message. In our algorithm we use the following definitions:
Definition 1 (Cluster): We define a cluster Ci by a connected sub-graph of the network, with a diameter less than or equal to 2. The cluster has an identifier corresponding to the identity of the node with the higher γ in the cluster, that is to say that if the cluster is the cluster Ci then the cluster-head of this cluster has the identifier id = i.
Definition 2 (Non-overlapping): a non-overlapping clustering ensures that there is no node that belongs to two different clusters at the same time witch minimizes the conflict.
Definition 3 (node status): Each node u has a status Statutu, the Statutu can be one of the following: CH: cluster-head node, MN: member node, or GN: gateway node. These three roles are defined in definitions 3.1, 3.2 and 3.3:
Definition 3.1 (Cluster-head): A node u is called cluster-head of cluster Ci iff: idu =i ˄ v Neighu , γu>γv.
Definition 3.2 (member node): A node u is said member node if it is not a cluster-head and it does not have in its neighborhood a node associated to a different cluster. u Ci Then idu ≠ i ˄ [ v (Cj/Cj ≠ Ci) ˄ v Neighu]
Definition 3.3 (Gateway node) A node u is a Gateway node iff: u Ci Then v Neighu / v Cj ˄ Cj ≠ Ci. Gateway node has a special role. It provides access to one or more neighboring clusters.
nodes u and v is the size of the list of data that exists in a node and does not exist in the other (formula 2). Two nodes with a high need each other more then two nodes with a lower (disjointness of contents).
(u,v)= ||(ListLu ListLv ) - (ListLu ListLv )|| (3) Where: - u,v: Nodes.
- ListLu: List of local data in the node u.
For example, if local lists of data in nodes u, v, h are ListLu = {A, B, C}, ListLv = {A, E, F, G, H}, ListLh = {A, B, C, D} respectively then: - (u, v)= || {B, C, E, F, G, H} || = 6. - (u,h)= || {D} || =1.
Clustering steps are: 1. Each node calculates the parameter γ and disseminates information on its neighbors by the Hello packet. 2. If the node has the maximum γ among its neighbors then it becomes the cluster-head (Status = CH) and sends requests to join the cluster to the other. If two nodes u and v have γu = γv , then the cluster-head is the node that has the lowest id. 3. The node that receives a request to join a cluster, then it became with a Status = MN. 4. If the node receives several requests from different cluster-head to join their clusters, then it becomes a gateway node: Status = GN. But as a cluster selects the one with the maximum γ. In case of a tie, the node selects the cluster-head that has the maximum nosimilarity degree â with it. 5. If two neighboring nodes have both a Status = CH, then the first node that detects the conflict through hello messages received compared γ to that of its cluster-head neighbor. If the γ is smaller, it abandoned his status as cluster-head and becomes a member node and sends a hello message to its neighbors announcing its new status.
Otherwise, it retains the role of cluster-head. 6. The algorithm terminates when each node in the system specifies its status.
For example in Figure 4: γ0 = 20, means the node will be a cluster-head. The node 2 will be a node member in the cluster of node 0. Node 7 is a getaway node. The result of clustering is shown in Figure 4.
Fig 4. Example of clustering of 8 nodes
In ad hoc networks, topology changes frequently due to node mobility and energy. So we have to manage:1) nodes that move, 2) nodes that disappear and nodes that appear. Our algorithm can also manage these cases.
The appearance of a new node. When a new node enters the network, it broadcasts at a regular interval of time a message of type hello. At the end of the timeout, if it has not received any type hello message from a cluster-head, the node becomes clusterhead. If the node received a hello message from a cluster-head, the node becomes a member node. In the event that it receives from more than one cluster-head, the node becomes a gateway node (Execute step 4 of the clustering algorithm) Disappearance of a node. In the same way as for the appearance by exchanging hello messages the neighbors are aware of the disappearance.
Moving a node. Case equivalent to the emergence of a new node. In this case the hello messages will be received by the other new neighbors. 5
To validate our approach, we used our simulator that allows us to run and measure the
performance of our strategy of clustering CD (Data based Clustering) and compare it with
the LID strategy [
The number of nodes also affects the number of clusters. According to the results obtained in the second experiment (see Figure 6). Increasing the number of nodes increases the number of clusters, but not on the same frequency for both approaches. Our approach CD is better than LID approach with a gain estimated by 22.8%.
Fig5: Range vs Number of clusters.
Fig6: Number of nodes vs Number of clusters.
The number of transitions is a very important parameter; it reflects the stabilization of the
topology constructed by the clustering. The transition is the passage from configuration i to
configuration i +1. The configuration is the result of the execution of at least one step of the
clustering algorithm [
Fig7 : Number of nodes vs Number of transitions Fig8: Number of nodes vs response time In the last experiment, we studied the impact of number of read requests to the energy consumed in the system. We note that the energy increases with increasing number of applications for both approaches because each query must be redirected to other nodes in different clusters to reach the answer. But our approach CD decreases remarkably the energy consumption (a gain of 25%) because it maximizes the number of different data in each cluster taking in the account the mobility and the energy of each node, which improves the intra-cluster access and stabilize the topology (see Figure 9).
Fig9: Number of requests vs Consumption of energy.
In this report, we proposed a clustering strategy that maximizes intra-cluster access and
minimizes energy consumption. This strategy uses energy, mobility and the types of data
stored in the neighborhood to elect the cluster-head. The experimental results demonstrate
the effectiveness of our proposal. Our strategy can be used to create clusters in unstructured
P2P system as FastTrack and Gnutella [