## 6 Implementation, Results and Discussion  
As aforementioned in Section 4, the selection of the optimal path is here performed using the so-called GSO algorithm. The interaction between this procedure and the objective function has requested a novel approach to implement the original algorithm to fulfill the requirements of such a complex system. To apply optimization to the sensor network optimization problem considered in this paper it is necessary to represent the network model by a directed graph \(G=(V,A)\) where the set of vertexes \(V\) represents the sensor nodes and the set of arcs \(A\) represents valid communication links. Each sensor node \(i\in V\) of the sensor network represents a vertex while a communication link between two nodes is described by an arc \((i,j)\in A\). A path is a sequence of nodes \(<i,j,\ldots,k>\), where \(i,j,\ldots,k\in V\), such that each node is connected to the next node in the sequence: to obtain this condition each arc \((i,j)\), \((j,\ldots)\), \(\ldots\),(\(\ldots,k)\) must be in the arc set \(A\). When dealing with evolutionary algorithms the main issue is to generate a proper route, in order to evaluate it under the constrains of energy limitations and objective function, namely the metrics defined in Section 5. The issue that was addressed by the authors is to generate only feasible routes of variable lengths, thus avoiding loops and non-feasible paths. Fortunately, the adjacency matrix \(A\) presents several important features that can be suitably considered to generate proper solutions to this task. If \(d_{ij}\) represents the Euclidean distance between nodes \(i\) and \(j\) and \(d_{max}\) represents the maximum transmission range, a link between nodes \(i,j\) exist only if \(d_{ij}<d_{max}\). According to this feature, the adjacency matrix \(A\) can be dynamically updated by updating sensor power level after each communication, in order to remove connections associated to dead nodes: if \(A\) is the adjacency matrix of the undirected graph \(V\) of the network, then the matrix \(A_{n}\) (_i.e._, the matrix product of \(n\) copies of \(A\)) has an interesting property: the entry in row \(i\) and column \(j\) gives the number of paths of length \(n\) from vertex \(i\) to vertex \(j\) (which is always finite if there are no directed cycles). Therefore, here the matrix \(A_{n}\) is defined to be:  
\[A_{n+1}=A_{n}\cdot A_{1} \tag{3}\]  
where, in our particular case, to avoid loops, the main diagonal of every level of the adjacency matrix is forced to have all zero entries, where all non-zero entries have been indicated with 1. The generation of feasible multi-hop routes is therefore straightforward: if the number of nodes is \(N\), the maximum number of arcs in a route is \(N-1\), therefore, knowing \(A_{1}=A\) (updated step by step, as aforementioned) it is just a matter to compute \(A_{n}\)\(\forall n\in[1,N-1]\). At each iteration of GSO, therefore, a particular individual is selected and its \"genes\" are decoded in a suitable route according to these simple rules: starting from the sender \(i\), if \(i\) is connected to the destination node \(k\), a non-zero value is present in the corresponding entry of at least one \(A_{n}\). Therefore, a node \(j\) is chosen among those connected to \(i\) (by looking at \(A_{1}\)) and then the process is repeated for this node \(j\), considering now \(A_{n-1}\). This iterative procedure ends to node \(k\) in at most \(N-1\) steps, thanks to \(A_{n}\) features, therefore enabling the creation of consistent routes of variable lengths. Loops can be easily removed by post-processing the node sequence of the generated route. Once a feasible path has been identified, the GSO evaluates it associating a fitness score to it. Fitness function correlates closely with the algorithm's goal: in our case the objective is the maximization of the following fitness score \(F\), defined as a linear combination of the criteria previously described.