# Energy Efficient Multipath Routing Algorithm for Wireless Multimedia Sensor Network
## 4 Energy Efficient GA-Based Multipath Routing
### Cluster and Cluster Head Formation  
To ensure scalability, save the battery life of the individual multimedia wireless sensors, and to prolong the network lifetime, the sensor nodes in the wireless multimedia sensor network are divided into a set of clusters [43], where each cluster is managed by a cluster head (CH). Algorithm 1 shows  
Figure 3: Efficient multipath routing based on genetic algorithm (EMRGA). the procedure used to create a cluster. The cluster is formed dynamically. All nearby nodes whose received signal strength are beyond a given threshold value or nodes will form a cluster dynamically. The clusters are dynamically formed by the sensor nodes available in an area where a particular event occurs. Those nodes which are in the vicinity of event radius are included in the clustering. One node with better cost value will be selected among the nodes in the cluster as the CH. ```
1: Assign delay time \(T_{d}\) for every node
2: Event radius is \(R\)
3: Calculate \(Dist(v_{i},\ Event)\) based on \(RSS_{i}\)
4: WHILE (\(T_{d}\
eq 0\)) DO
5: IF (\(RSS_{i}\geq Threshold\)) THEN
6: IF(\(Dist(v_{i},\ Event)\leq R\)) && (\(RSS_{i}\geq Threshold\)))
7:\(m_{i}=m_{i}+1;//\) number of nodes in the cluster
8: END
9: END
10: END
```  
**Algorithm 1**Cluster Formation  
Once the cluster members are determined, the next step is to select a cluster head. The detail of the cluster formation algorithm is described as Algorithm 2.The algorithm used to select the CH can be explained as follows. Suppose we have \(m\) sensor nodes and let \(X=\{x_{1},x_{2},\ x_{3},\ x_{4},\ \ldots,\ x_{m}\}\) be the sensor nodes positions in the event area respectively. In the first round, the node positioned relatively in the middle of the cluster will be the cluster head. In subsequent rounds, the center of the event-region will be determined by computing its centroid and comparing the value with the position of each node in the cluster. A node which is relatively closer to the centroid of the event-region will be the CH. ```
1: INPUT: \(m\) nodes in a cluster
2:FOR i--1: \(m\)
3:\(v_{i}\) calculates its cost as \(cost\ (v_{i})\)
4:END-FOR
5: Assign delay time \(T_{d}\) for every non-CH node in the cluster
6:WHILE (\(T_{d}\
eq 0\))
7: wait \(T_{d}\) moreover, all nodes in the cluster receive CH request from other members;
8: Assign the node with higher cost value to be CH
9:END-WHILE
10: CH sends an advertisement message to other nodes in the cluster;
11: Connect CH with other remaining \(m-1\) non-CH members for data communication
12:END
```  
**Algorithm 2**Selection of Cluster Head  
The cluster members send their sensed data to the cluster head during their allocated time. The cluster head, in turn, collects these data and aggregates them before forwarding to the sink node. The aggregated data then are continuously transmitted to the base station until the event stops. As the cluster head performs extra work, it uses more energy compared to the other nodes in the cluster. To avoid premature death of any sensor nodes in the cluster, the cluster head responsibility is shared among the cluster members by switching the role between them. The algorithm considers the transmission energy cost, residual energy, distance between source nodes and CH, and distance between CH and base station. Specifically, a new CH is selected by computing the cost of the nodes as shown in Equation (14). Therefore, in each subsequent round, a node which has a higher cost value will be elected as CH. \[Cost(v_{i})=\ \frac{Dist(v_{i},\ C_{e})}{m}+\ \frac{Dist(v_{i},\ BS)}{m}+E_{res}(v_{i}) \tag{14}\]  
where \(Dist(v_{i},\ C_{e})\) is the distance between a node, \(v_{i}\), and, the center of the event area, and \(Dist(v_{i},\ BS)\) is the distance between a node, \(v_{i}\), and the base station (BS). \(E_{res}(v_{i})\) is the residual energy of the node. This function considers the remaining residual energy of the non-CH nodes in the cluster, the distance of each node to the centroid of the event region, and the distance of each node from the sink node.