Abstract: We demonstrate a 40 Gb/s self-synchronizing, all-optical packet
clock recovery circuit designed for efficient packet-mode traffic. The circuit
locks instantaneously and enables sub-nanosecond packet spacing due to the
low clock persistence time. A low-Q Fabry-Perot filter is used as a passive
resonator tuned to the line-rate that generates a retimed clock-resembling
signal. As a reshaping element, an optical power-limiting gate is
incorporated to perform bitwise pulse equalization. Using two preamble
bits, the clock is captured instantly and persists for the duration of the data
packet increased by 16 bits. The performance of the circuit suggests its
suitability for future all-optical packet-switched networks with reduced
transmission overhead and fine network granularity.
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 powerdatatransmissions 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: Smart Dust is a special case of wireless sensor networks, comprised of a vast number of ultra-small fully autonomous computing, communication and sensing devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart Dust can be very useful in practice, i.e. in the local detection of remote crucial events and the propagation of data reporting their realization to a control center.
In this paper, we propose a new energy efficient and fault tolerant protocol for data propagation in smart dust networks, the Variable Transmission Range Protocol (VTRP). The basic idea of data propagation in VTRP is the varying range of datatransmissions, i.e. we allow the transmission range to increase in various ways. Thus, data propagation in our protocol exhibits high fault-tolerance (by bypassing obstacles or faulty sensors) and increases network lifetime (since critical sensors, i.e. close to the control center are not overused). As far as we know, it is the first time varying transmission range is used.
We implement the protocol and perform an extensive experimental evaluation and comparison to a representative protocol (LTP) of several important performance measures with a focus on energy consumption. Our findings indeed demonstrate that our protocol achieves significant improvements in energy efficiency and network lifetime.
Abstract: In this work we propose a new energy efficient and fault tolerant protocol for data propagation in wireless sensor networks, the Variable Transmission Range Protocol VTRP. The basic idea of data propagation in VTRP is the varying range of datatransmissions, ie. we allow the transmission range to increase in various ways. Thus data propagation in our protocol exhibits high fault-tolerance (by bypassing obstacles or faulty sensors) and increases network lifetime (since critical sensors, ie. close to the control center are not overused). As far as we know, it is the first time varying transmission range is used.
We implement the protocol and perform an extensive experimental evaluation and comparison to a representative protocol (LTP) of several important performance measures with a focus on energy consumption. Our findings indeed demonstrate that our protocol achieves significant improvements in energy efficiency and network lifetime.
Abstract: In this paper, we present a new hybrid optical burst switch architecture (HOBS) that takes advantage of the pre-transmission idle
time during lightpath establishment. In dynamic circuit switching (wavelength routing) networks, capacity is immediately hardreserved
upon the arrival of a setup message at a node, but it is used at least a round-trip time delay later. This waste of resources
is significant in optical multi-gigabit networks and can be used to transmit traffic of a lower class of service in a non-competing
way. The proposed hybrid OBS architecture, takes advantage of this idle time to transmit one-way optical bursts of a lower class of
service, while high priority data explicitly requests and establishes end-to-end lightpaths. In the proposed scheme, the two control
planes (two-way and one-way OBS reservation) are merged, in the sense that each SETUP message, used for the two-way lightpath
establishment, is associated with one-way burst transmission and therefore it is modified to carry routing and overhead information
for the one-way traffic as well. In this paper, we present the main architectural features of the proposed hybrid scheme and further
we assess its performance by conducting simulation experiments on the NSF net backbone topology. The extensive network study
revealed that the proposed hybrid architecture can achieve and sustain an adequate burst transmission rate with a finite worst case
delay.
Abstract: We study the problem of data propagation in sensor networks,
comprised of a large number of very small and low-cost nodes,
capable of sensing, communicating and computing. The distributed
co-operation of such nodes may lead to the accomplishment of large
sensing tasks, having useful applications in practice. We present
a new protocol for data propagation towards a control center
(``sink") that avoids flooding by probabilistically favoring
certain (``close to optimal") datatransmissions.
This protocol is very simple to implement in sensor devices
and operates under total absence
of co-ordination between sensors. We consider a network model of randomly deployed sensors of sufficient density.
As shown by a geometry analysis,
the protocol is correct, since it always propagates data
to the sink, under ideal network conditions (no failures). Using
stochastic processes, we show that the protocol is very energy efficient. Also, when part of the network is inoperative, the
protocol manages to propagate data very close to the sink, thus in
this sense it is robust. We finally present and discuss
large-scale experimental findings validating the analytical
results.
Abstract: We study the problem of data propagation in sensor networks,
comprised of a large number of very small and low-cost nodes,
capable of sensing, communicating and computing. The distributed
co-operation of such nodes may lead to the accomplishment of large
sensing tasks, having useful applications in practice. We present a new protocol for data propagation towards a control center ("sink") that avoids flooding by probabilistically favoring certain ("close to optimal") datatransmissions. Motivated by certain applications and also as a starting point for a rigorous analysis, we study here lattice-shaped sensor networks. We however show that this lattice shape emerges even in randomly deployed sensor networks of sufficient sensor density. Our work is inspired and builds upon the directed diffusion paradigm.
This protocol is very simple to implement in sensor devices, uses only local information and operates under total absence of co-ordination between sensors. We consider a network model of randomly deployed sensors of sufficient density. As shown by a geometry analysis, the protocol is correct, since it always propagates data to the sink, under ideal network conditions (no failures). Using stochastic processes, we show that the protocol is very energy efficient. Also, when part of the network is inoperative, the protocol manages to propagate data very close to the sink, thus in this sense it is robust. We finally present and discuss large-scale experimental findings validating the analytical results.
Abstract: We propose a MAC protocol for mobile ad hoc networks that
uses power control for the RTS/CTS and DATA frame
transmissions in order to improve energy and capacity
utilization efficiency. Unlike IEEE 802.11, in our scheme the
RTS frames are not sent using the maximum transmission
power to silence neighbouring nodes, and the CTS frames do
not silence all receiving nodes to the same degree. In contrast,
the transmission power of the RTS frames follows a slow
start principle, while the CTS frames, which are sent at
maximum transmission power, prevent the neighbouring
nodes from transmitting their DATA frames with power more
than a computed threshold, while allowing them to transmit at
power levels less than that threshold. This is done by
including in the RTS and the CTS frames additional
information, such as the power of the transmissions, and the
interference tolerance of the nodes. Moreover the DATA
frames are sent at the minimum required transmission power
increased by a small margin to ensure connectivity with the
intended receiver, so as to cause minimal interference to
neighbouring nodes and allow for future interference to be
added to the receiver of the DATA frames. The power to be
used by the transmitter is computed by the recipient of the
RTS frame and is included in the CTS frame. It is expected
that a network with such a power management scheme would
achieve a better throughput performance and more power
savings than a network without such a scheme.
Abstract: We propose a MAC protocol for mobile ad hoc networks that
uses power control for the RTS/CTS and DATA frame
transmissions in order to improve energy and capacity
utilization efficiency. Unlike IEEE 802.11, in our scheme the
RTS frames are not sent using the maximum transmission
power to silence neighbouring nodes, and the CTS frames do
not silence all receiving nodes to the same degree. In contrast,
the transmission power of the RTS frames follows a slow
start principle, while the CTS frames, which are sent at
maximum transmission power, prevent the neighbouring
nodes from transmitting their DATA frames with power more
than a computed threshold, while allowing them to transmit at
power levels less than that threshold. This is done by
including in the RTS and the CTS frames additional
information, such as the power of the transmissions, and the
interference tolerance of the nodes. Moreover the DATA
frames are sent at the minimum required transmission power
increased by a small margin to ensure connectivity with the
intended receiver, so as to cause minimal interference to
neighbouring nodes and allow for future interference to be
added to the receiver of the DATA frames. The power to be
used by the transmitter is computed by the recipient of the
RTS frame and is included in the CTS frame. It is expected
that a network with such a power management scheme would
achieve a better throughput performance and more power
savings than a network without such a scheme.
Abstract: Data propagation in wireless sensor networks can be performed either by hop-by-hop single transmissions or by multi-path broadcast of data. Although several energy-aware MAC layer protocols exist that operate very well in the case of single point-to-point transmissions, none is especially designed and suitable for multiple broadcast transmissions. The key idea of our protocols is the passive monitoring of local network conditions and the adaptation of the protocol operation accordingly. The main contribution of our adaptive method is to proactively avoid collisions by implicitly and early enough sensing the need for collision avoidance. Using the above ideas, we design, implement and evaluate three different, new strategies for proactive adaptation. We show, through a detailed and extended simulation evaluation, that our parameter-based family of protocols for multi-path data propagation significantly reduce the number of collisions and thus increase the rate of successful message delivery (to above 90%) by achieving satisfactory trade-offs with the average propagation delay. At the same time, our protocols are shown to be very energy efficient, in terms of the average energy dissipation per delivered message.
Abstract: We consider sensor networks where the sensor nodes are attached on entities that move in a highly dynamic, heterogeneous manner. To capture this mobility diversity we introduce a new network parameter, the direction-aware mobility
level, which measures how fast and close each mobile node is expected to get to the data destination (the sink). We then provide local, distributed data dissemination protocols
that adaptively exploit the node mobility to improve performance. In particular, "high" mobility is used as a low cost replacement for data dissemination (due to the ferrying of data), while in the case of "low" mobility either a) data propagation redundancy is increased (when highly mobile neighbors exist) or b) long-distance datatransmissions are used (when the entire neighborhood is of low mobility) to accelerate data dissemination towards the sink. An extensive performance comparison to relevant methods from
the state of the art demonstrates signicant improvements i.e. latency is reduced by even 4 times while keeping energy dissipation and delivery success at very satisfactory levels.
Abstract: Wireless Sensor Networks are complex systems consisting of a number of relatively simple autonomous sensing devices spread on a geographical area. The peculiarity of these devices lies on the constraints they face in relation to their energy reserves and their computational, storage and communication capabilities. The utility of these sensors is to measure certain environmental conditions and to detect critical events in relation to these measurements. Those events thereupon have to be reported to a specific central station namely the “sink”. This data propagation generally has the form of a hop-by-hop transmission. In this framework we work on distributed data propagation protocols which are taking into account the energy reserves of the sensors. In particular following the work of Chatzigiannakis et al. on the Probabilistic Forwarding Protocol (PFR) we present the distributed probabilistic protocol EFPFR, which favors transmission from the less depleted sensors in addition to favor transmissions close to the “optimal line”. This protocol is simple and relies only on local information for propagation decisions. Its main goal is to limit the total amount of energy dissipated per event and therefore to extend the network’s operation duration.
Abstract: Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their inveronment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. Each device has limited computational and energy resources, thus a basic issue in the applicastions of wireless sensor networks is the low energy consumption and hence, the maximization of the network lifetime.
The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays.
In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, a graph formation phase is executed by the sink during the initialization: the network area is partitioned in equal square regions, where the sink, pauses for a certain amount of time, during the network traversal, in order to collect data.
We propose two network traversal methods, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region.Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink datatransmissions only.
We evaluate our methods via simulation, in diverse network settings and comparatively to related state of the art solutions. Our findings demonstrate significant latency and energy consumption improvements, compared to previous research.
Abstract: Wireless sensor networks are a recently introduced category of ad hoc computer networks, which are comprised by nodes of small size and limited computing and energy resources. Such nodes are able of measuring physical properties such as temperature, humidity, etc., wireless communication between each other and in some cases interaction with their surrounding environments (through the use of electromechanical parts).
As these networks have begun to be widely available (in terms of cost and commercial hardware availability), their field of application and philosophy of use is constantly evolving. We have numerous examples of their applications, ranging from monitoring the biodiversity of a specific outdoor area to structural health monitoring of bridges, and also networks ranging from few tens of nodes to even thousands of nodes.
In this PhD thesis we investigated the following basic research lines related to wireless sensor networks:
a) their simulation,
b) the development of data propagation protocols suited to such networks and their evaluation through simulation,
c) the modelling of ``hostile'' circumstances (obstacles) during their operation and evaluation of their impact through simulation,
d) the development of a sensor network management application.
Regarding simulation, we initially placed an emphasis to issues such as the effective simulation of networks of several thousands of nodes, and in that respect we developed a network simulator (simDust), which is extendable through the addition of new data propagation protocols and visualization capabilities. This simulator was used to evaluate the performance of a number of characteristic data propagation protocols for wireless sensor networks. Furthermore, we developed a new protocol (VRTP) and evaluated its performance against other similar protocols. Our studies show that the new protocol, that uses dynamic changes of the transmission range of the network nodes, performs better in certain cases than other related protocols, especially in networks containing obstacles and in the case of non-homogeneous placement of nodes.
Moreover, we emphasized on the addition of ``realistic'' conditions to the simulation of such protocols, that have an adversarial effect on their operation. Our goal was to introduce a model for obstacles that adds little computational overhead to a simulator, and also study the effect of the inclusion of such a model on data propagation protocols that use geographic information (absolute or relative). Such protocols are relatively sensitive to dynamic topology changes and network conditions. Through our experiments, we show that the inclusion of obstacles during simulation can have a significant effect on these protocols.
Finally, regarding applications, we initially proposed an architecture (WebDust/ShareSense), for the management of such networks, that would provide basic capabilities of managing such networks and developing applications above it. Features that set it apart are the capability of managing multiple heterogeneous sensor networks, openess, the use of a peer-to-peer architecture for the interconnection of multiple sensor network. A large part of the proposed architecture was implemented, while the overall architecture was extended to also include additional visualization capabilities.
Abstract: We study the problem of energy-balanced data propagation
in wireless sensor networks. The energy balance property
guarantees that the average per sensor energy dissipation
is the same for all sensors in the network, during
the entire execution of the data propagation protocol. This
property is important since it prolongs the network˘s lifetime
by avoiding early energy depletion of sensors.
We propose a new algorithm that in each step decides
whether to propagate data one-hop towards the final destination
(the sink), or to send data directly to the sink. This
randomized choice balances the (cheap) one-hop transimssions
with the direct transimissions to the sink, which are
more expensive but “bypass” the sensors lying close to the
sink. Note that, in most protocols, these close to the sink
sensors tend to be overused and die out early.
By a detailed analysis we precisely estimate the probabilities
for each propagation choice in order to guarantee
energy balance. The needed estimation can easily be performed
by current sensors using simple to obtain information.
Under some assumptions, we also derive a closed form
for these probabilities.
The fact (shown by our analysis) that direct (expensive)
transmissions to the sink are needed only rarely, shows that
our protocol, besides energy-balanced, is also energy efficient.
Abstract: We study the problem of energy-balanced data propagation in wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, during the entire execution of the data propagation protocol. This property is important since it prolongs the network˘:s lifetime by avoiding early energy depletion of sensors.
We propose a new algorithm that in each step decides whether to propagate data one-hop towards the final destination (the sink), or to send data directly to the sink. This randomized choice balances the (cheap) one-hop transimssions with the direct transimissions to the sink, which are more expensive but “bypass” the sensors lying close to the sink. Note that, in most protocols, these close to the sink sensors tend to be overused and die out early.
By a detailed analysis we precisely estimate the probabilities for each propagation choice in order to guarantee energy balance. The needed estimation can easily be performed by current sensors using simple to obtain information. Under some assumptions, we also derive a closed form for these probabilities.
The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy-balanced, is also energy efficient.
Abstract: We present key aspects (hardware, software, topology, networking) of SenseWall, an experimental sensor network test-bed we have created for the implementation and engineering of distributed sensor network algorithms. We then describe how SenseWall has been in particular used to implement two recent state of the art algorithms for energy balanced sensor data propagation. We elaborate on the issues and challenges created by the restrictions and particularities of the experimental test-bed and how we dealt with them. We also carry out a detailed performance evaluation comparing the energy balance protocols to two baseline protocols that include only either single hop or direct datatransmissions.
Abstract: In this paper we present a multicost algorithm for the joint
time scheduling of the communication and computation
resources that will be used by a task. The proposed
algorithm selects the computation resource to execute the
task, determines the path to route the input data, and finds
the starting times for the datatransmission and the task
execution, performing advance reservations. We initially
present an optimal scheme of non-polynomial complexity
and by appropriately pruning the set of candidate paths we
also give a heuristic algorithm of polynomial complexity. We
evaluate the performance of our algorithm and compare it to
that of algorithms that handle only the computation or
communication part of the problem separately. We show that
in a Grid network where the tasks are CPU- and dataintensive
important performance benefits can be obtained by
jointly optimizing the use of the communication and
computation resources.
Abstract: A key problem in Grid networks is how to efficiently manage the available infrastructure, in order to
satisfy user requirements and maximize resource utilization. This is in large part influenced by the
algorithms responsible for the routing of data and the scheduling of tasks. In this paper,wepresent several
multi-cost algorithms for the joint scheduling of the communication and computation resources that
will be used by a Grid task. We propose a multi-cost scheme of polynomial complexity that performs
immediate reservations and selects the computation resource to execute the task and determines the
path to route the input data. Furthermore, we introduce multi-cost algorithms that perform advance
reservations and thus also find the starting times for the datatransmission and the task execution. We
initially present an optimal scheme of non-polynomial complexity and by appropriately pruning the set
of candidate paths we also give a heuristic algorithm of polynomial complexity. Our performance results
indicate that in a Grid network in which tasks are either CPU- or data-intensive (or both), it is beneficial
for the scheduling algorithm to jointly consider the computational and communication problems. A
comparison between immediate and advance reservation schemes shows the trade-offs with respect to
task blocking probability, end-to-end delay and the complexity of the algorithms.
Abstract: We investigate the problem of how to achieve energy balanced data propagation in distributed wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, throughout the execution of the data propagation protocol. This property is crucial for prolonging the network lifetime, by avoiding early energy depletion of sensors.
We survey representative solutions from the state of the art. We first present a basic algorithm that in each step probabilistically decides whether to propagate data one-hop towards the final destination (the sink), or to send it directly to the sink. This randomized choice trades-off the (cheap, but slow) one-hop transmissions with the direct transmissions to the sink, which are more expensive but bypass the bottleneck region around the sink and propagate data fast. By a detailed analysis using properties of stochastic processes and recurrence relations we precisely estimate (even in closed form) the probability for each propagation option necessary for energy balance.
The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy balanced, is also energy efficient. We then enhance this basic result by surveying some recent findings including a generalized algorithm and demonstrating the optimality of this two-way probabilistic data propagation, as well as providing formal proofs of the energy optimality of the energy balance property.
Abstract: Switching in core optical networks is currently being
performed using high-speed electronic or all-optical
circuit switches. Switching with high-speed electronics
requires optical-to-electronic (O/E) conversion of the
data stream, making the switch a potential bottleneck
of the network: any effort (including parallelization) for
electronics to approach the optical speeds seems to be
already reaching its practical limits. Furthermore, the
store-and-forward approach of packet-switching does
not seem suitable for all-optical implementation due to
the lack of practical optical random-access-memories
to buffer and resolve contentions. Circuit switching on
the other hand, involves a pre-transmission delay for
call setup and requires the aggregation of microlows
into circuits, sacriicing the granularity and the control
over individual lows, and is ineficient for bursty traf-
ic. Optical burst switching (OBS) has been proposed
by Qiao and Yoo (1999) to combine the advantages of
both packet and circuit switching and is considered a
promising technology for the next generation optical
internet.
Abstract: Recent rapid technological developments have led to the
development of tiny, low-power, low-cost sensors. Such devices
integrate sensing, limited data processing and communication
capabilities.The effective distributed collaboration
of large numbers of such devices can lead to the efficient
accomplishment of large sensing tasks.
This talk focuses on several aspects of energy efficiency.
Two protocols for data propagation are studied: the first
creates probabilistically optimized redundant datatransmissions
to combine energy efficiency with fault tolerance,
while the second guarantees (in a probabilistic way) the
same per sensor energy dissipation, towards balancing the
energy load and prolong the lifetime of the network.
A third protocol (in fact a power saving scheme) is also
presented, that directly and adaptively affects power dissipation
at each sensor. This “lower level” scheme can be
combined with data propagation protocols to further improve
energy efficiency.
Abstract: In this work we focus on the energy efficiency challenge in wireless sensor networks, from both an on-line perspective (related to routing), as well as a network design perspective (related to tracking). We investigate a few representative, important aspects of energy efficiency: a) the robust and fast data propagation b) the problem of balancing the energy
dissipation among all sensors in the network and c) the problem of efficiently tracking moving
entities in sensor networks. Our work here is a methodological survey of selected results that
have alre dy appeared in the related literature.
In particular, we investigate important issues of energy optimization, like minimizing the total
energy dissipation, minimizing the number of transmissions as well as balancing the energy
load to prolong the system˘s lifetime. We review characteristic protocols and techniques in the recent literature, including probabilistic forwarding and local optimization methods. We study the problem of localizing and tracking multiple moving targets from a network design perspective i.e. towards estimating the least possible number of sensors, their positions and operation characteristics needed to efficiently perform the tracking task. To avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps. Under this model, we abstract the tracking network design problem by a covering combinatorial problem and then design and analyze an efficient approximate method for sensor placement
and operation.
Abstract: This research further investigates the recently introduced
(in [4]) paradigm of radiation awareness in ambient environments with abundant heterogeneous wireless networking
from a distributed computing perspective. We call radiation
at a point of a wireless network the total amount of electromagnetic quantity the point is exposed to; our denition incorporates the eect of topology as well as the time domain
and environment aspects. Even if the impact of radiation to
human health remains largely unexplored and controversial,
we believe it is worth trying to understand and control, in
a way that does not decrease much the quality of service
oered to users of the wireless network.
In particular, we here focus on the fundamental problem
of ecient data propagation in wireless sensor networks, try-
ing to keep latency low while maintaining at low levels the
radiation cumulated by wireless transmissions. We rst propose greedy and oblivious routing heuristics that are radiation aware. We then combine them with temporal back-o
schemes that use local properties of the network (e.g. number of neighbours, distance from sink) in order to spread" radiation in a spatio-temporal way. Our proposed radiation
aware routing heuristics succeed to keep radiation levels low,
while not increasing latency.
Abstract: A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time and known data transfer size. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start and end transmission at each link so as to minimize the reception time at the destination, or optimize some other performance criterion. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so called non-dominated candidate paths, from which the optimal path can be found. We then propose two mechanisms to appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial-time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network propagation delays and link-state update policies have on performance.
Abstract: A key problem in networks that support advance reservations is the routing and time scheduling of
connections with flexible starting time and known data transfer size. In this paper we present a multicost
routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the
data should start and end transmission at each link so as to minimize the reception time at the destination,
or optimize some other performance criterion. The utilization profiles of the network links, the link
propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm.
We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated
candidate paths, from which the optimal path can be found. We then propose two mechanisms to
appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of
polynomial complexity. We examine the performance of the algorithms in the special case of an Optical
Burst Switched network. Our results indicate that the proposed polynomial time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network
propagation delays and link-state update policies have on performance.
Abstract: We consider the important problem of energy balanced data propagation in wireless sensor networks and we extend and generalize
previous works by allowing adaptive energy assignment. We consider the data gathering problem where data are generated by the sensors and
must be routed toward a unique sink. Sensors route data by either sending the data directly to the sink or in a multi-hop fashion by delivering
the data to a neighbouring sensor. Direct and neighbouring transmissions require different levels of energy consumption. Basically, the protocols balance the energy consumption among the sensors by computing the adequate ratios of direct and neighbouring transmissions. An abstract model of energy dissipation as a random walk is proposed, along with rigorous performance analysis techniques. Two efficient distributed algorithms are presented and analysed, by both rigorous means and simulation.
The first one is easy to implement and fast to execute. The protocol assumes that sensors know a-priori the rate of data they generate.
The sink collects and processes all these information in order to compute the relevant value of the protocol parameter. This value is transmitted
to the sensors which individually compute their optimal ratios of direct and neighbouring transmissions. The second protocol avoids the necessary a-priori knowledge of the data rate generated by sensors by inferring the relevant information from the observation of the data paths.
Furthermore, this algorithm is based on stochastic estimation methods and is adaptive to environmental changes.
Abstract: We propose and evaluate the performance of a new MAC-layer protocol for mobile ad hoc networks, called the Slow Start Power Controlled (abbreviated SSPC) protocol. SSPC improves on IEEE 802.11 by using power control for the RTS/CTS and DATA frame transmissions, so as to reduce energy consumption and increase network throughput and lifetime. In our scheme the transmission power used for the RTS frames is not constant, but follows a slow start principle. The CTS frames, which are sent at maximum transmission power, prevent the neighbouring nodes from transmitting their DATA frames at power levels higher than a computed threshold, while allowing them to transmit at power levels less than that threshold. Reduced energy consumption is achieved by adjusting the node transmission power to the minimum required value for reliable reception at the receiving node, while increase in network throughput is achieved by allowing more transmissions to take place simultaneously. The slow start principle used for calculating the appropriate DATA frames transmission power and the possibility of more simultaneous collision-free transmissions differentiate the SSPC protocol from the other MAC solutions proposed for IEEE 802.11. Simulation results indicate that the SSPC protocol achieves a significant reduction in power consumption, average packet delay and frequency of RTS frame collisions, and a significant increase in network throughput and received-to-sent packets ratio compared to IEEE 802.11 protocol.
Abstract: In this paper we study the threshold behavior of the fixed radius random graph model and its applications to the key management problem of sensor networks and, generally, for mobile ad-hoc networks. We show that this random graph model can realistically model the placement of nodes within a certain region and their interaction/sensing capabilities (i.e. transmission range, light sensing sensitivity etc.). We also show that this model can be used to define key sets for the network nodes that satisfy a number of good properties, allowing to set up secure communication with each other depending on randomly created sets of keys related to their current location. Our work hopes to inaugurate a study of key management schemes whose properties are related to properties of an appropriate random graph model and, thus, use the rich theory developed in the random graph literature in order to transfer ?good? properties of the graph model to the key sets of the nodes.
Partially supported by the IST Programme of the European Union under contact number IST-2005-15964 (AEOLUS) and the INTAS Programme under contract with Ref. No 04-77-7173 (Data Flow Systems: Algorithms and Complexity (DFS-AC)).
Abstract: We examine the problem of transmitting in minimum time a given amount of data between a
source and a destination in a network with finite channel capacities and nonzero propagation delays. In
the absence of delays, the problem has been shown to be solvable in polynomial time. In this paper, we
show that the general problem is NP-complete. In addition, we examine transmissions along a single path,
called the quickest path, and present algorithms for general and special classes of networks that improve
upon previous approaches. The first dynamic algorithm for the quickest path problem is also
given
Abstract: Data propagation in wireless sensor networks can be performed either by hop-by-hop single transmissions or by multi-path broadcast of data. Although several energy-aware MAC layer protocols exist that operate very well in the case of single point-to-point transmissions, none is especially designed and suitable for multiple broadcast transmissions.In this paper we propose a family of new protocols suitable of multi-path broadcast of data, and show, through a detailed and extended simulation evaluation, that our parameter-based protocols significantly reduce the number of collisions and thus increase the rate of successful message delivery (to above 90%) by trading off the average propagation delay. At the same time, our protocols are shown to be very energy efficient, in terms of the average energy dissipation per delivered message.