## 3 Problem Description
### Dynamic Behavior  
Besides the transmission distance, the energy consumption is also affected by the network protocols. In each data gathering cycle, sensors can detect the environment information within its sensing range and transmit \(a\) packets, each with \(m_{data}\) bits, to the base station hop-by-hop. Generally, the sensor will not fail unless its energy is exhausted. In this paper, we study the sensor deployment optimization problems based on the following protocol assumptions:  
* Routing protocol. The Greedy Perimeter Stateless Routing (GPSR) algorithm is applied to determine the next hop for transmitting data. In GPSR, it is preferred to forward the packet of a sensor to the neighboring sensor, which is the closest one to the base station, within its transmission range [2010]. To ensure that the data can only be transmitted between the sensors of neighboring grids, we assume \[d>\frac{\sqrt{3}R_{t}}{3}.\] (3)
* Sleep/wake-up protocol. Since a single sensor will run out of energy easily, it is common to deploy some redundant units. The Probing Environment and Adaptive Sleeping (PEAS) protocol proposed by [PERSON] _et al._[2010] is adopted in our model to control the sleep/wake-up mechanism. The  
Figure 1: The topology of homogeneous WSN.  
protocol wakes a sensor up only when no sensor is active within its probing range (which is usually the same as the sensing range). Thus, we assume that \[d>R_{s}\] (4) It is reasonable that much overlap exists and energy is wasted if \(d\leq R_{s}\). According to this protocol, at each sensor-deployed location, _i.e._, the center of each hexagonal grid in Figure 11, only one sensor is active that can be used to detect, transmit and receive message. The other sensors are in sleeping status with little energy consumption (ignorable).
* Retransmission protocol. Retransmission is widely used to improve the success rate of data transmission. In this paper, the reduced CSMA/CA protocol without RTS/CTS is adopted. Figure 11 illustrates the data transmission process. The transmitter sends DATA message to its next hop according to the routing protocol. If the receiver receives the message successfully, an ACK message will be sent back to the transmitter. Note that, the transmitter will keep on sending DATA message repeatedly until it receives the ACK message or reaches the maximum number of retry attempts. In our case, the maximum number of retry attempts is assumed to be \"2\".  
As suggested by [PERSON] _et al._[2], the retransmission rate can be measured by packet reception rate. For a Mica2 more using non-coherent frequency-shift keying modulation and encoded by Manchester, according to the IEEE 802.15.4 standard [2], its retransmission rate can be expressed as follows:  
\[RR(d)=\begin{cases}1-\left[1-\frac{1}{2}e^{-\left(\frac{P_{t}-20\log_{10}(\frac {3\pi f}{2\pi})-S_{r}}{1.28}\right)}\right]^{2m-l},&\text{if }d\leq 8\mathrm{m},\\ 1-\left[1-\frac{1}{2}e^{-\left(\frac{P_{t}-20\log_{10}(\frac{3\pi f}{2\pi})-3 \log_{10}(\frac{d}{2})-S_{r}}{1.28}\right)}\right]^{2m-l},&\text{otherwise}, \end{cases} \tag{5}\]  
where \(P_{t}\) is the transmission power, \(f\) is the band width, \(C\) is the speed of light, \(d\) is the transmission distance, \(S_{r}\) is the receiver's sensitivity, and \(m\) and \(l\) are the lengths of a single packet and the preamble (in bits), respectively.