In wireless sensor and actor networks (WSANs), a set of static sensor nodes and a set of (mobile) actor nodes form a network that performs distributed sensing and actuation tasks. In [1], Abbasi et al. presented DARA, a Distributed Actor Recovery Algorithm, which restores the connectivity of the interactor network by efficiently relocating some mobile actors when failure of an actor happens. To restore 1 and 2-connectivity of the network, two algorithms are developed in [1]. Their basic idea is to find the smallest set of actors that needs to be repositioned to restore the required level of connectivity, with the objective to minimize the movement overhead of relocation. Here, we show that the algorithms proposed in [1] will not work smoothly in all scenarios as claimed and give counterexamples for some algorithms and theorems proposed in [1]. We then present a general actor relocation problem and propose methods that will work correctly for several subsets of the problems. Specifically, our method does result in an optimum movement strategy with minimum movement overhead for the problems studied in [1].

Data aggregation is a key functionality in wireless sensor networks (WSNs). This paper focuses on data aggregation scheduling problem to minimize the delay (or latency). We propose an efficient distributed algorithm that produces a collision-free schedule for data aggregation in WSNs. We theoretically prove that the delay of the aggregation schedule generated by our algorithm is at most 16R + Δ - 14 time slots. Here, R is the network radius and Δ is the maximum node degree in the communication graph of the original network. Our algorithm significantly improves the previously known best data aggregation algorithm with an upper bound of delay of 24D + 6Δ + 16 time slots, where D is the network diameter (note that D can be as large as 2R). We conduct extensive simulations to study the practical performances of our proposed data aggregation algorithm. Our simulation results corroborate our theoretical results and show that our algorithms perform better in practice. We prove that the overall lower bound of delay for data aggregation under any interference model is max{log n,R}, where n is the network size. We provide an example to show that the lower bound is (approximately) tight under the protocol interference model when rI= r, where rIis the interference range and r is the transmission range. We also derive the lower bound of delay under the protocol interference model when rII≥ 3r.

It is imperative to design efficient and effective online spectrum allocation methods since requests for spectrums often come in an online fashion. In this paper, we propose SALSA, strategyproof online spectrum admission for wireless networks. We assume that the requests arrival follows the Poisson distribution. Upon receiving an online spectrum request, our protocol will decide immediately whether to grant its exclusive usage or not, and how much the request should pay. Preempting existing spectrum usage is not allowed. We proposed two protocols that have guaranteed performances for two different scenarios: 1) random-arrival case: the bid values and requested time durations follow some distributions that can be learned, or 2) semi-arbitrary-arrival case: the bid values could be arbitrary, but the request arrival sequence is random. We analytically prove that our protocols are strategyproof, and are both approximately social efficient and revenue efficient. Our extensive simulation results show that they perform almost optimum. Our method for semi-arbitrary-arrival model achieves social efficiency and revenue efficiency almost 20-30 percent of the optimum, while it has been proven that no mechanism can achieve social efficiency ratio better than 1/e \simeq 37 \rm percent. Our protocol for the random-arrival case even achieves social efficiency and revenue efficiency two-six times the expected performances by the celebrated VCG mechanism.

Data aggregation is a primitive communication task in wireless sensor networks (WSNs). In this paper, we study designing data aggregation schedules under the Protocol Interference Model for answering queries. Given a network consisting of a set of nodes V distributed in a two-dimensional plane, we address different kinds of queries in this paper. First and foremost, we consider a single one-off query which requires a subset of source nodes V' C V to send data to a distinguished sink node, we propose a delay-efficient algorithm that produces a collision-free schedule and theoretically prove that the delay achieved by our algorithm is nearly a small constant factor of the optimum. We further extend our discussion to the multiple one-off queries case and periodic query case and propose our data aggregation scheduling algorithms respectively with theoretical performance analysis.

Efficient aggregation of data collected by sensors is crucial for a successful application of wireless sensor networks (WSNs). Both minimizing the energy cost and reducing the time duration (or called latency) of data aggregation have been extensively studied for WSNs. Algorithms with theoretical performance guarantees are only known under the protocol interference model, or graph-based interference models generally. In this paper, we study the problem of designing time efficient aggregation algorithm under the physical interference model. To the best of our knowledge, no algorithms with theoretical performance guarantees are known for this problem in the literature. We propose an efficient algorithm that produces a data aggregation tree and a collision-free aggregation schedule. We theoretically prove that the latency of our aggregation schedule is bounded by O(R+Δ) time-slots. Here R is the network radius and Δ is the maximum node degree in the communication graph of the original network. In addition, we derive the lower-bound of latency for any aggregation scheduling algorithm under the physical interference model. We show that the latency achieved by our algorithm asymptotically matches the lower-bound for random wireless networks. Our extensive simulation results corroborate our theoretical analysis.