## 5 Network Model and Assumption  
In this paper we consider a wireless sensor network with a ground layer defined in a flat two-dimensional rectangular area where we randomly place n nodes. In order to assure a complete coverage of the selected area and a medium connectivity of the network we also put some other constraints on the minimum and maximum distance among nodes. Moreover the base station has higher computational capabilities and it is equipped with a different type of transceiver with a bigger transmitting range that allows it to reach the whole network  
We assume that the energy loss due to channel transmission is proportional to the square distance between sender and receiver. Thus, for the nodes that communicate in a round of the simulation, the energy cost of transmission (\(E_{Tx}\)) and receiving (\(E_{Rx}\)) are calculated as a consequence.  
According to [4] a simple radio model has been used in this work, where the radio dissipates \(E_{el}\) = 50 \(nJ/bit\) to run both the transmitter and receiver circuitry, and \(E_{amp}=100\frac{pJ}{bit\cdot m^{2}}\) for transmit amplifier to achieve an acceptable signal to noise ratio. An \(r^{2}\) energy path loss due to channel transmission is also assumed and thus to transmit a \(k\)-bit message to a distance \(d\) using this model, the single sensor node expends:  
\[E_{TX}(k,d)=E_{el}\cdot k+E_{amp}\cdot k\cdot m^{2} \tag{1}\]  
while to receive the same message the radio expends:  
\[E_{RX}(k)=E_{el}\cdot k \tag{2}\]  
We make also the assumption that the energy needed for the transmission of one bit of data from node P to node Q is the same as to transmit one bit from Q to P (symmetric propagation channel).  
We simulate the transmission of data from every node to the base station through a random sequence of senders. At each round of simulation a sender has to communicate the sensed data to the base station performing a multi-hop communication to reach it. At the beginning of each round the base station updates the topology of the network removing the dead nodes and calculates the next optimal path. Since it has no power constraints, the base station can broadcast the results of its search to the entire network and synchronize the network clock. The nodes receive the information sent so they know if they will participate in the next route. The control overhead to synchronize the network clock is taken into account within the system simulation, as described in [4] and further detailed in Section 6.  
The base station can easily update the battery level of the network at each step since collision and packet retransmission are avoided and only few nodes participate to communication. Thus, it is possible to calculate directly the energy waste associated to a single transmission (proportional to the distance between sender and receiver) and automatically update the battery level table after each round.  
The key idea of this algorithm is to address all the computational costs to the base station, in order to apply the optimization in run-time--without affecting the power consumption of the sensor nodes, which are involved only in communication and sensing tasks--and to switch the sensor node to Sleep mode whenever possible. The other main idea is to use the GSO presented in Section 4 to perform the choice of the optimal path between base station and nodes. In this study we wanted to check the real capability of the algorithm in discovering the optimal routes without exploring the entire range of possible routes (the whole connection graph, described more in details in Section 6).  
In literature there are different routing protocols that use one or more criteria to evaluate the efficiency of a route in terms of power consumption, link quality, message overhead, time delay in delivering packets, throughput. In order to prove the performances of the GSO we considered different metrics criteria, such as Maximum Available Power (MAP), Minimum Communication Power (MCP), Minimum Hop Number (MHN), and their combinations, as already described in [4].