Abstract
This Cluster has been well received as one of the most effective solutions to enhance energy efficiency and scalability of large-scale wireless sensor networks. However, it is rather challenging to conform a cohesive group of Clusters having permanent communication among Cluster heads. In this paper, a unique look at the Cluster head election problem is taken into account, specifically concentrating on applications in which the formation and maintenance of a virtual backbone among Cluster heads is the main requirement. Our approach for Cluster-based network organization is based on the use of collective social agents in order to lead the formation of these Clusters. Our algorithm uses ants to choose good Cluster head candidates and to create a virtual backbone among these router nodes. 
Abstract
Key words
Abstract
Redes de sensores multimídia sem fios, algoritmos de Clustering, otimização por colônia de formigas.
pAlAvrAs-chAve:
Redes de sensores multimídia sem fios, algoritmos de Clustering, otimização por colônia de formigas.
Introduction
T he availability of inexpensive hardware such as CMOS cameras and microphones that are able to ubiquitously capture multimedia content from the environment has fostered the development of Wireless Multimedia Sensor Networks (WMSNs), i.e., networks of wirelessly interconnected devices that allow retrieving video and audio streams, still images, and scalar sensor data (Akyildiz, Melodia & Chowdhury, 2008) . With rapid improvements and miniaturization in hardware, a single sensor device can be equipped with audio and visual information collection modules. Even though, there have been significant advances in recent years to improve these wireless sensor nodes, more energy-efficient solutions are required within the communication stack and middleware for the conservation of the battery power. Within the communication stack, an approach that is likely to succeed is the use of a hierarchical structure for routing (Akkaya & Younis, 2005) .
Introduction
Clustering with data aggregation is an important technique in this direction. Even though many protocols have been proposed in the literature to minimize energy dissipation on the forwarding paths, some nodes may still be drained quickly. By employing a dynamic Clustering technique, these nodes are rotated dynamically (Younis & Fahmy, 2006) . Various Clustering techniques in different contexts have been proposed. Most algorithms aim at generating the minimum number of Clusters and transmission distance. But most of them forget an important issue: permanent connection between Clusters. In that way, we can obtain reliability and robustness in the routes between nodes and sink.
Introduction
In this paper, we propose to biologically inspire the Clustering approach, whereby the network is Clustered around certain nodes deemed biologically fit. This work is based on the TANT algorithm (Selvakennedy, Sinnappan & Shang, 2009 ), but we have made improvements in order to create a virtual backbone among the CHs (Cluster heads) and to select the best nodes as CH candidates. According to this approach, when a node has a special agent, it selects itself to become a CH. Such election obviates the need to maintain many state variables, which is common in other Clustering algorithms. A fixed number of such agents are used to ensure that a certain number of Clusters are formed throughout the network useful life, and these Clusters are selected in such a way as to maximize the network lifetime and to get a permanent connection among them.
Clustering algorithm
F or large scale sensor networks that may have thousands of nodes, it is more realistic to have hierarchical models of network rather than flat ones. In that way, we can get scalability in our network. Nevertheless, scalability is not the only reason to Cluster the network. This process also allows improving network data aggregation mechanisms, while concentrating this activity in the CH, consequently reducing node workloads, saving energy and increasing the network lifetime. Arboleda & Nasser (2006) present other advantages of Clustering that apply to this novel protocol: the fact that only the CH transmits information out of the Cluster helps prevent collisions between the sensors inside the Cluster, as they do not have to share communication channels with nodes in other Clusters. This also promotes energy savings and avoids the black hole problem. Latency is also reduced. Although data must hop from one CH to another, they cover larger distances than when sensors use a multi-hop communication model (non-Clustered) as the one used in other protocols.
Clustering algorithm
Finally, Clustering is applied in order to take advantage of the existence of nodes of different abilities inside a WMSN. Table 1 (Misra, Reisslein, & Guoliang, 2008) presents the processing performance and memory capacities among standard (TelosB) and multimedia sensors. Table 1 shows that the memory and processing capacities of multimedia sensors are superior to those of conventional sensors. That is the reason for selecting multimedia sensors to become the network CHs. This novel algorithm will be designed to favor the selection of these nodes as CHs. Our Clustering algorithm aims at achieving the following goals:
Clustering algorithm
l Saving network resources by encouraging the selection of resourcerich nodes (multimedia sensor nodes) as network CHs.
Clustering algorithm
l Ensuring network connectivity by forming a virtual backbone among the different CHs. Each CH is in the radio range transmission of at least one other CH. Communication between two CHs is direct (there are no relay nodes between them).
Clustering algorithm
l Maximizing network lifetime by implementing a mechanism of CH rotation. Source. Misra, Reisslein & Guoliang (2008) With a virtual backbone in the network, only CHs are concerned with data transportation, and other nodes are free to pursue their sensing tasks. Such task sharing improves network performance with respect to routing overhead and, moreover, a smaller number of nodes need to be alert for data transportation. This procedure reduces energy consumption, thus simultaneously maximizing network lifetime.
Information update phase
In the same way to the protocol T-ANT (Selvakennedy, Sinnappan & Shang, 2009) , our Clustering protocol uses a collection of agents to form Clusters in a sensor network. It is completely distributed and completed in constant time. These are some of the reasons why this algorithm was selected.
Information update phase
As in T-ANT, in our Clustering algorithm, the Clustering operations are split into rounds. Each round comprises a Cluster setup phase and a steady phase. In the steady phase of the algorithm, data transmission takes place between sensors and the sink. A number of timers are used to control the process operations. During the Cluster setup phase, CHs are elected and Clusters are placed around them. In order to avoid the maintenance of many state variables, as one finds in numerous current Clustering proposals, a series of agents (known as Cluster-ants or CANTS) are used to control CH elections. A node with a CANT becomes a CH, whereas others choose to join the best Cluster in range.
Information update phase
The Cluster radius R Cluster is defined as a tunable parameter that determines the minimum distance between any two CH nodes in the network. The Clustering pheromone value determines whether it is appropriate for this node to become a CH. For each node, this value is calculated using the following formula:
Information update phase
Where m(n) denotes the available memory in the node, e(n) is the residual ratio of the node's energy and a and b denote the importance of each component of the pheromone: a for the memory capacity and b for the energy component. Thus, the network administrator can establish which component is most important when selecting a CH, namely, memory or energy or both. The state indicates if the node is a CH, a member of a Cluster or neither. These HELLO packets are constantly broadcast by the nodes throughout their lifetime.
Ant release phase
After the information update phase, the sink releases a fixed number of ants (i.e. control messages) into the network. Assuming that the terrain is square M×M, the number of ants to be released is set at: Where d depicts half of R Cluster . The latter formula also represents the number of Clusters that make up the network. Attempts are made to obtain complete coverage of the area with this number of Clusters, where every node belongs to a Cluster and the CHs are disseminated throughout the terrain. Ants move about the network in a random fashion, as far as they can, respecting the limits imposed by their Time-To-Live (TTL) values. The TTL value equals the number of ants. Hence, an ant can visit a large number of candidate nodes to become a CH before they die. When the sink releases an ant, it chooses one of its neighbors randomly according to the following probability distribution function:
Ant release phase
Where Φ c (j) denotes the Clustering pheromone value sent by node j, as defined in equation (1), and N s represents the set of all of the sink neighbors located at a distance of at least R Cluster . Before releasing the next Cluster ant, the sink waits for a timer to expire (Cluster_timer). Although the timer expiration is set at a random value, it always remains proportional to the delay of sending an ant from a node to a neighbor. The objective of this timer is to ensure that the ants' subsequent transmissions do not self-interfere. Aside from that, when the sink selects a neighbor, the pheromone value of that node is artificially decreased, in order to avoid choosing the same set of nodes repeatedly. It presents the algorithm with the tasks performed by the sink in order to start the Clustering process. When an ant arrives at a node, that node will execute the tasks. The algorithm shows that, in order to become a CH, the selected node must have received a Cluster ant from another CH (or the sink) located at a distance R Cluster from it. R_Cluster was previously defined as the minimal distance between two CHs. Hence, at the moment of selecting the following neighbor, the node reads its neighbors' information table and selects, with probability prob c , a node whose distance is a minimum of R Cluster in a random manner. The reason why a CH elects the next CH is to create a virtual backbone between the various CHs, a direct communication strategy between them. This backbone will facilitate the task of routing accomplished by the routing protocol which is in charge of delivering packages between nodes and the sinking in the network. When a node becomes a CH, it broadcasts an adv_Cluster message to advise its neighborhood of its new condition. It also changes the value of field state of a HELLO package subsequently sent by the node. Once a regular node receives an adv_Cluster message from a CH located at a distance below R Cluster , it stores the corresponding information that pertains to that CH. This information is later used to join a given Cluster. Contrary to other proposals documented in the literature, this CH election approach has a very small constant time and a low level of complexity. An ant's TTL indicates the maximum number of hops that it can perform. The CH pulverizes an ant once its TTL reaches the value zero. This situation shows the existence of a superfluous number of Clusters in the network, and the Cluster ant is destroyed in order to avoid the creation of new Clusters that would hinder the network.
Ant release phase
The actual Clustering process happens once another timer expires. A regular node decides to join a Cluster when its join_timer expires. This node chooses the nearest Cluster to join (from all of the adv_Cluster packages it received) by sending a join message with its ID. When a CH receives join messages, it stores such information in order to subsequently select a Cluster member as a new CH. If a regular node has never received an adv_ Cluster package from a CH, it starts a join_timer once again and repeats the latter process until this timer expires. However, if in the process, it receives neither an adv_Cluster message nor a HELLO package from a CH, the node uses the nearest neighboring Cluster member as a bridge to reach its CH. The properties of the proposed Clustering algorithm can be highlighted as follows:
Ant release phase
l The algorithm is completely distributed. A node locally decides to become a CH if an ant reaches it or joins a Cluster.
Ant release phase
l Given the absence of looping statements as a function of node quantity, it is clear that the election process has an O(1) time complexity.
Ant release phase
l The algorithm ensures the creation of a backbone among the CHs. As all CHs are connected, paths to a sink can be easily discovered.
Experimental results

I
n order to evaluate our Clustering process, NS-2 (VINT, 2013) was used to implement and simulate the novel algorithm. For this simulations, we consider there are two types of nodes: scalars and multimedia (with more energy and memory than scalar nodes). Half of the nodes are multimedia. The radio range of the nodes span 100 meters and the data rate equals 2 Mbit/s. At the MAC layer, a modified version of 802.11b DCF protocol was used. The modification was made in the queue politics of the MAC protocol in order to accept multi-class and multi-priority traffic.
I
It was assumed that 400 sensor nodes were distributed randomly over a square area of 400 m x 400 m. This scenario was executed during 600 seconds. In order to benchmark this new protocol, it was decided to compare it to T-ANT (Selvakennedy, Sinnappan & Shang, 2009) , as it was the base of our Clustering protocol and also since it outperformed other well-known Clustering algorithms, such as LEACH (Heinzelman, Chandrakasan & Balakrishnan, 2002) and HEED (Younis & Fahmy, 2004) . For this experiment, a R Cluster = 60m is assumed, and the CH rotation scheme is the same as in T-ANT: there are multiple rounds in the network lifetime, and in each round, a CH rotation is carried out. The CH finds its Cluster member whose level of pheromone, equation (1), is the highest, before it becomes the CH for the next round. Figure 3 depicts the CH connectivity of these Clustering algorithms at different simulation time. This property indicates if there is direct communication between the CHs of the network, meaning that no CH is isolated. This property is very important in this novel algorithm, as all of the traffic between source nodes and the sink is transported by the CH. If CHs are isolated, it is impossible to transmit information from that Cluster to the sink. In this simulation, any node can be a CH, in other words we set a = b = 0 in equation (1). Observe that after only 20 rounds (one round 20s each), the connectivity of T-ANT is acceptable. Meanwhile, the connectivity of our algorithm remains at a steady 100% from the beginning of the simulation. The main design goal of our Clustering algorithm is reached with the permanent connectivity of the CHs.
I
In Figure 4 , the improvement gained through our Clustering algorithm is further exemplified by the network lifetime graph. The network lifetime is defined as the time the first node in the network has a depleted battery. For this experiment, the memory component in the Clustering pheromone formula (parameter a in the equation (1)) was set to 0 (zero) and the energy component (parameter b in the equation (1)) was set to 1. This way, energy rich sensors have greater probabilities of becoming a CH.
I
Moreover, a Constant Bit Rate (CBR) traffic source was used to generate data traffic of 32-byte packets. All regular nodes sent the sink a packet/ second on average. Non sending nodes fall into a sleep mode. Five simulations were carried out, where the value of the energy component varied. The initial energy of the scalar nodes was 0.1J and for the multimedia nodes, this initial energy was 0.5J in order to let the nodes disappear sooner. However, this does not change the behavior pattern of these protocols. It is clear that our algorithm exhibits the longest lifetime with all nodes remaining fully functional. Test results show that our algorithm achieves more than twice the lifetime of T-ANT, which can be explained by the fact that the CHs never sleep, making them the first candidates to get their battery depleted. As the algorithm mainly chooses energy-rich nodes as CHs, the network lifetime is longer. T-ANT does not differentiate between scalar and multimedia nodes, and that is the reason of the poor performance of this algorithm. 
Conclusion
W e have presented an ant-based Clustering algorithm for Wireless Multimedia Sensor Networks, with heterogeneous nodes. Our Clustering algorithm selects Cluster heads based on its pheromone value. This pheromone depends on the residual energy and the other parameters, customizable by the network administrator. Besides that, our Clustering algorithm uses special agents (ants) to guide the selection of CHs in a totally distributed manner. In comparison with T-ANT (Selvakennedy, Sinnappan & Shang, 2009 ), another ant-based Clustering algorithm, our Clustering process achieves a permanent CH connection with lower energy costs.
Conclusion
Our future work will include mechanisms for CH rotation, in order to get a bigger network lifetime.

{'paper_id': '114467900', 'title': 'A novel cooperative ant-based clustering approach for wireless multimedia sensor networks', 's2_url': 'https://api.semanticscholar.org/CorpusID:114467900', 'source': 'S2ORC'}