## Part A On-Line Energy Optimization
### Theoretical Analysis  
[8] first provides some basic definitions. **Definition 1**: Let \(h_{opt}(p,\,{\cal W})\) be the (optimal) number of \"hops\" (direct, vertical to \({\cal W}\) transmissions) needed to reach the wall, in the _ideal_ case in which particles always exist in pair-wise distances \({\cal R}\) on the vertical line from \(p\) to \({\cal W}\). Let \(\Pi\) be _a smart-dust propagation protocol_, using _a transmission path_ of length \(L(\Pi,\,p,\,{\cal W})\) to send info about event \({\cal E}\) to wall \({\cal W}\). Let \(h(\Pi,\,p,\,{\cal W})\) be the actual number of hops (transmissions) taken to reach \({\cal W}\). The _\"hops\" efficiency_ of protocol \(\Pi\) is the ratio  
\[C_{h}\ =\ \frac{h(\Pi,\,p,\,{\cal W})}{h_{opt}(p,\,{\cal W})}\]  
Clearly, the number of hops (transmissions) needed characterizes the energy consumption and the time needed to propagate the information \({\cal E}\) to the wall. Remark that \(h_{opt}\ =\ \left\lceil\frac{d(p,{\cal W})}{{\cal R}}\right\rceil\), where \(d(p,{\cal W})\) is the (vertical) distance of \(p\) from the wall \({\cal W}\). In the case where the protocol \(\Pi\) is randomized, or in the case where the distribution of the particles in the cloud is a random distribution, the number of hops \(h\) and the efficiency ratio \(C_{h}\) are random variables and one wishes to study their expected values. The reason behind these definitions is that when \(p\) (or any intermediate particle in the information propagation to \({\cal W}\)) \"looks around\" for a particle as near to \({\cal W}\) as possible to pass its information about \({\cal E}\), it may not get any particle in the perfect direction of the line vertical to \({\cal W}\). This difficulty comes mainly from three causes: a) Due to the initial spreading of particles of the cloud in the area and because particles do not move, there might not be any particle in that direction. b) Particles of sufficient remaining battery power may not be currently available in the right direction. c) Particles may temporarily \"sleep\" (i.e. not listen to transmissions) in order to save battery power. Note that any given distribution of particles in the smart dust cloud may not allow the ideal optimal number of hops to be achieved at all. In fact, the least possible number of hops depends on the input (the positions of the grain particles). [8] however, compares the efficiency of protocols to the ideal case. A comparison with the best achievable number of hops in each input case will of course give better efficiency ratios for protocols. To enable a first step towards a rigorous analysis of smart dust protocols, [8] makes the following simplifying assumption: _The search phase always finds a_\(p^{\prime\prime}\) (of sufficiently high battery) in the semicircle of center the particle \(p^{\prime}\) currently possessing the information about the event and radius \(R\), in the direction towards \({\cal W}\). Note that this assumption on always finding a particle can be relaxed in the following ways: (a) by repetitions of the search phase until a particle is found. This makes sense if at least one particle exists but was sleeping during the failed searches, (b) by considering, instead of just the semicircle, a cyclic sector defined by circles of radiuses \({\cal R}-\Delta{\cal R},\,{\cal R}\) and also take into account the density of the smart cloud, (c) if the protocol during a search phase ultimately fails to find a particle towards the wall, it may _backtrack_. [8] also assumes that the position of \(p^{\prime\prime}\) is uniform in the arc of angle \(2a\) around the direct line from \(p^{\prime}\) vertical to \({\cal W}\). Each data transmission (one hop) takes constant time \(t\) (so the \"hops\" and time efficiency of our protocols coincide in this case). It is also assumed that each target selection is stochastically _independent_ of the others, in the sense that it is always drawn uniformly randomly in the arc \((-\alpha,\,\alpha)\).