Abstract: We here present the Forward Planning Situated Protocol (FPSP), for scalable, energy efficient and fault tolerant data propagation in situated wireless sensor networks. To deal with the increased complexity of such deeply networked sensor systems, instead of emphasizing on a particular aspect of the services provided, i.e. either for low-energy periodic, or low-latency event-driven, or high-success query-based sensing, FPSP uses two novel mechanisms that allow the network operator to adjust the performance of the protocol in terms of energy, latency and success rate on a per-task basis. We emphasize on distributedness, direct or indirect interactions among relatively simple agents, flexibility and robustness.
The protocol operates by employing a series of plan & forward phases through which devices self-organize into forwarding groups that propagate data over discovered paths. FPSP performs a limited number of long range, high power data transmissions to collect information regarding the neighboring devices. The acquired information, allows to plan a (parameterizable long by {\"e}) sequence of short range, low power transmissions between nearby particles, based on certain optimization criteria. All particles that decide to respond (based on local criteria) to these long range transmissions enter the forwarding phase during which information is propagated via the acquired plan. Clearly, the duration of the forwarding phases is characterized by the parameter {\"e}, the transmission medium and the processing speed of the devices. In fact the parameter {\"e} provides a mechanism to adjust the protocol performance in terms of the latency--energy trade-off. By reducing {\"e} the latency is reduced at the cost of spending extra energy, while by increasing {\"e}, the energy dissipation is reduced but the latency is increased.
To control the success rate--energy trade-off, particles react locally on environment and context changes by using a set of rules that are based on response thresholds that relate individual-level plasticity with network-level resiliency, motivated by the nature-inspired method for dividing labor, a metaphor of social insect behavior for solving problems [1]. Each particle has an individual response threshold {\`E} that is related to the "local" density (as observed by the particle, [2]); particles engage in propagation of events when the level of the task-associated stimuli exceeds their thresholds. Let s be the intensity of a stimulus associated with a particular sensing task, set by the human authorities. We adopt the response function T{\`e}(s) = snover sn + {\`e}n, the probability of performing the task as a function of s, where n > 1 determines the steepness of the threshold. Thus, when {\`e} is small (i.e. the network is sparse) then the response probability increases; when s increases (i.e. for critical sensing tasks) the response probability increases as well.
This role-based approach where a selective number of devices do the high cost planning and the rest of the network operates in a low cost state leads to systems that have increased energy efficiency and high fault-tolerance since these long range planning phases allow to bypass obstacles (where no sensors are available) or faulty sensors (that have been disabled due to power failure or other natural events).
Abstract: Algorithms are presented for the all-pairs min-cut problem in bounded tree-width, planar, and sparsenetworks. The approach used is to preprocess the inputn-vertex network so that afterward, the value of a min-cut between any two vertices can be efficiently computed. A tradeoff is shown between the preprocessing time and the time taken to compute min-cuts subsequently. In particular, after anO(n log n) preprocessing of a bounded tree-width network, it is possible to find the value of a min-cut between any two vertices in constant time. This implies that for such networks the all-pairs min-cut problem can be solved in timeO(n2). This algorithm is used in conjunction with a graph decomposition technique of Frederickson to obtain algorithms for sparse and planar networks. The running times depend upon a topological property, \~{a}, of the input network. The parameter \~{a} varies between 1 and {\`E}(n); the algorithms perform well when \~{a} = o(n). The value of a min-cut can be found in timeO(n + \~{a}2log \~{a}) and all-pairs min-cut can be solved in timeO(n2 + \~{a}4log \~{a}) for sparsenetworks. The corresponding running times for planar networks areO(n + \~{a} log \~{a}) andO(n2 + \~{a}3log \~{a}), respectively. The latter bounds depend on a result of independent interest; outerplanar networks have small “mimicking” networks that are also outerplanar.
Abstract: We introduce a new model of
ad-hoc mobile networks, which we call hierarchical,
that are comprised of dense subnetworks of mobile
users (corresponding to highly populated
geographical areas, such as cities),
interconnected across access ports
by sparse but frequently used connections
(such as highways).
For such networks, we present
an efficient routing protocol which extends
the idea (introduced in WAE00) of exploiting the co-ordinated
motion of a small part of an ad-hoc mobile
network (the ``support'') to achieve
very fast communication between any two mobile users of the network.
The basic idea of the new protocol presented here is, instead
of using a unique (large) support for the whole network,
to employ a hierarchy of (small) supports (one for each city)
and also take advantage of the regular traffic
of mobile users across the interconnection highways to communicate
between cities.
We combine here theoretical analysis (average case estimations based on random walk properties) and experimental implementations (carried out using the LEDA platform) to claim and validate results showing that such a hierarchical routing approach is,
for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the
basic ``support'' idea presented in WAE00.
Abstract: We introduce a new model of ad-hoc mobile networks,
which we call hierarchical, that are comprised of
dense subnetworks of mobile users (corresponding to highly
populated geographical areas), interconnected across access
ports by sparse but frequently used connections.
To implement communication in such a case, a possible
solution would be to install a very fast (yet limited) backbone
interconnecting such highly populated mobile user areas, while
employing a hierarchy of (small) supports (one for each lower level
site). This fast backbone provides a limited number of access
ports within these dense areas of mobile users.
We combine here theoretical analysis (average case estimations based on
random walk properties) to claim and validate
results showing that such a hierarchical routing approach is,
for this class of ad-hoc mobile networks, significantly
more efficient than a simple extension of the
basic ``support'' idea presented in [WAE00,DISC01].
Abstract: We present the first approximate distance oracle for sparse directed networks with time-dependent arc-travel-times determined by continuous, piecewise linear, positive functions possessing the FIFO property. Our approach precomputes (1 + {\aa}) −approximate distance summaries from selected landmark vertices to all other vertices in the network, and provides two sublinear-time query algorithms that deliver constant and (1 + {\'o}) −approximate shortest-travel-times, respectively, for arbitrary origin-destination pairs in the network. Our oracle is based only on the sparsity of the network, along with two quite natural assumptions about travel-time functions which allow the smooth transition towards asymmetric and time-dependent distance metrics.
Abstract: We study the important problem of tracking moving
targets in wireless sensor networks. We try to overcome the
limitations of standard state of the art tracking methods based on
continuous location tracking, i.e. the high energy dissipation and
communication overhead imposed by the active participation of
sensors in the tracking process and the low scalability, especially
in sparsenetworks. Instead, our approach uses sensors in a
passive way: they only record and judiciously spread information
about observed target presence in their vicinity; this information
is then used by the (powerful) tracking agent to locate the target
by just following the traces left at sensors. Our protocol is greedy,
local, distributed, energy efficient and very successful, in the
sense that (as shown by extensive simulations) the tracking agent
manages to quickly locate and follow the target; also, we achieve
good trade-offs between the energy dissipation and latency.
Abstract: In this paper, we demonstrate the significant impact of (a) the mobility rate and (b) the user density on the performance of routing protocols in ad-hoc mobile networks. In particular, we study the effect of these parameters on two different approaches for designing routing protocols: (a) the route creation and maintenance approach and (b) the support approach that forces few hosts to move, acting as helpers for message delivery. We study one representative protocol for each approach, i.e. AODV for the first approach and RUNNERS for the second. We have implemented the two protocols and performed a large scale and detailed simulation study of their performance. The main findings are: the AODV protocol behaves well in networks of high user density and low mobility rate, while its performance drops for sparsenetworks of highly mobile users. On the other hand, the RUNNERS protocol seems to tolerate well (and in fact benefit from) high mobility rates and low densities.
Abstract: In this paper we demonstrate the significant impact of (a) the mobility rate and (b) the user density on the performance of routing protocols in ad-hoc mobile networks. In particular, we study the effect of these parameters on two different approaches for designing routing protocols: (a) the route creation and maintenance approach and (b) the "support" approach, that forces few hosts to move acting as "helpers" for message delivery. We study one representative protocol for each approach, i.e., AODV for the first approach and RUNNERS for the second. We have implemented the two protocols and performed a large scale and detailed simulation study of their performance. For the first time, we study AODV (and RUNNERS) in the 3D case. The main findings are: the AODV protocol behaves well in networks of high user density and low mobility rate, while its performance drops for sparsenetworks of highly mobile users. On the other hand, the RUNNERS protocol seems to tolerate well (and in fact benefit from) high mobility rates and low densities. Thus, we are able to partially answer an important conjecture of [Chatzigiannakis, I et al. 2003].