## 3 Main Design
### Practical Issues  
To implement LACE on sensor nodes, we have several practical issues to tackle. Reducing complexity: According to the above equations, we can see that to calculate the short-term link correlation, the computational complexity is \(O(2^{m})\), which is high for sensor nodes. Apparently, there is a tradeoff between the accuracy and the complexity. To reduce the overhead, we do not calculate the average for all samples. Instead, we generate several bitmaps according to the \(m\) packet reception ratios (derived from Equation (6)) and calculate the average value of the generated bitmaps. We introduce a \(\delta\) factor, which is the number of bitmap generations to calculate in Equation (5). Intuitively, when \(\delta\) is large, more bitmaps are generated for calculation; the result will be more accurate, but the overhead will increase. Otherwise, the result will be less accurate, and the overhead will decrease. Therefore, for resource-constrained platforms, delta should be set small; for more powerful devices, delta should be set large. For example, when \(\delta=1\), \(R(n_{r}=k)\) is calculated as:  
\[R(n_{r}=k)=\prod_{j=1}^{k}p_{A}^{S}(j)\cdot p_{B}^{S}(j)\prod_{j=k+1}^{m}(1-p_ {A}^{S}(j)\cdot p_{B}^{S}(j)) \tag{9}\]  
for randomly selected \(k\) common packet receptions. Then, the calculation complexity can be reduced to \(O(m^{2})\), which is much more practical for resource-constrained sensor nodes. To find an appropriate \(\delta\) value, we conduct multiple experiments with varying \(\delta\) values on the TelosB platform [25]. Our experimental results show that \(\delta\) = 5 achieves accuracy over 70% with only a 1.506-ms delay. For more powerful devices, such as iMote [26], or in delay-tolerant application scenarios, \(\delta\) can be set larger to achieve more accurate estimation. Bitmap issues: As described above, the bitmaps are recorded at receivers and returned to the senders. There are two key issues: First, bitmaps at different receivers should be aligned with the same time offset. We use 32-bit length bitmaps to record the latest 32 received/lost data packets. However, the lost packet is indirectly identified (using the sequence number difference), _i.e._, when a receiver loses a packet, it can identify this packet loss only when it receives a new packet in the future. As a result, at the time when a node loses a packet, its bitmaps are not updated until the next packet reception. Further, bitmaps of different receivers may record different sets of packet transmissions, and the calculated link correlation would be meaningless (as shown in the example of Figure 3). For example, sender S transmits 10 packets; node A receives 1,2,3,5,7,9,10, and node B receives 1,2,3,6,7,8. If we set the bitmap length as five and collect the bitmaps after the time of the 10 th packet transmission, the bitmaps of A and B will be 01011 and 00111. Clearly, node B's bitmap does not record the latest five packets (6-10); instead, it records Packets 4-8. The reason is that it is unaware of Packet 9 and 10's transmissions. To solve this inconsistency, we add a initial offset at the beginning of each bitmap to indicate the start position of the bitmap. With the offset, the sender can align the bitmaps and calculate the link correlation. We use the same example as the above to illustrate how this works: When node A and B prepare to return the bitmaps, they add the start positions. Then, S receives two vectors, 601011 and 400111. Now, S uses the common parts of the bitmaps (010 and 111 for Packets 6-8, respectively) to calculate link correlation \(ch\) according to Equation (2). The second issue is the length of bitmaps: when the bitmap is long, it can represents more long-term link behavior, but requires more memory overhead. Considering that the TelosB platform has only 10 KB RAM and that the packet payload length is no longer than 114 bytes, we set the length of bitmaps according to the neighbor size: When a node has many neighbors, it uses short bitmaps to save memory/transmission overhead.