Conference Publications
@InProceedings{BasagniNP08,
author = {Basagni, S. and Nanni, M. A. and Petrioli, C.},
title = {Flow-fair Intra-Piconet ({F$\ell$IP}) Scheduling
for Communications in Personal Area Networks},
booktitle = {Proceedings of the IEEE Radio and Wireless Symposium,
RWS 2008},
year = 2008,
address = {Orlando, FL},
month = {January 22--25},
abtract = {As a building step of designing integrated
solution for forming multi-hop Personal
Area Networks (PANs) of Bluetooth devices,
in this paper we introduce a new
intra-piconet scheduling protocol that
defines the interaction among masters and
slaves with an eye to the flows passing
through their piconets. Differently from
previous intra-piconet solutions, such as
Pure Round Robin, its E-limited variation,
and the more recent Credit Scheme,
fairness and traffic adaptivity is now
achieved on a per-flow basis. Our
FLow-fair Intra-Piconet (\FIPS) scheduling
identifies the flows passing through each
piconet slave. Based on this information
the master can efficiently manage
intra-piconet resources. \FIPS\ is
compared with the three leading solutions
for intra-piconet scheduling mentioned.
Through ns2-based simulations we show that
\FIPS\ is effective in decreasing both
packet drop rate as well as end-to-end
packet latency.}
}
@InProceedings{BasagniPP07,
author = {Basagni, S. and Petrioli, C. and Petroccia, R.},
title = {Fail-safe Hierarchical Organization for Wireless
Sensor Networks},
booktitle = {Proceedings of the IEEE Military Communications Conference,
MILCOM 2007},
year = 2007,
address = {Orlando, FL},
month = {October 29--31},
abstract = {This paper presents the definition and
evaluation of a new protocol for providing
a wireless sensor network (WSN) with a
hierarchical organization. Differently
from previously proposed solutions, our
protocol, termed CC (``double c,'' for
\emph{clique clustering}), includes in its
operation a fail-safe mechanism for
dealing with node failure or removal,
which are typical of WSNs. More
specifically, the network is partitioned
into clusters that are \emph{cliques},
i.e., nodes in each clusters are directly
connected to each others. An efficient
mechanism for building a connected
backbone among the clusters is provided
within CC that is also resilient to node
failure. Both clustering and backbone
formation are completely localized, in the
precise sense that only nodes physically
close to a failing node are involved in
the reconfiguration process. We compare
the performance of CC with that of DMAC, a
protocol that has been previously proposed
for building and maintaining clusters and
backbones in presence of node removal. Our
comparison concerns metrics that are
central to WSN research, such as time for
clustering and backbone reorganization,
corresponding overhead (in bytes and
transmission energy), backbone size,
extent of (i.e., number of nodes involved
in) the reorganization, and backbone route
length. Our ns2-based simulation results
show that the design criteria chosen for
CC are effective in producing backbones
that can be reconfigured quickly ($152\%$
faster than DMAC's) and with remarkably
lower overhead (one order of magnitude
less than for DMAC).}
}
@InProceedings{BasagniCP07a,
author = {Basagni, S. and Carosi, A. and Petrioli, C.},
title = {Controlled Vs.\ Uncontrolled Mobility in Wireless
Sensor Networks: Some Performance Insights},
booktitle = {Proceedings of the $67$th Semi-Annual IEEE Vehicular
Technology Conference, VTC 2007 Fall},
year = 2007,
address = {Baltimore, MD},
month = {September 30--October 3},
abstract = {Among the many ways of improving the
performance of a wireless sensor network
(WSN) in terms of crucial metrics such as
its lifetime and data latency, exploiting
the mobility of some of the network
components has been recently observed to
be among the most promising. In this
paper we demonstrate how two very
different schemes for WSN mobility leads
to different benefits for network
performance. More specifically, we
consider the data MULEs kind of random,
uncontrolled mobility with single-hop data
collection and we compare it with the
controllable mobility of the data
collection point (sink) where
sensor-to-sink data routing follows
multi-hop paths. Through quite thorough
ns2-based simulations we show that data
MULEs are to be used in those WSNs
deployed for delay tolerant
applications. Benefits of this scheme
include low energy consumption and easier
protocol and nodal design. Data latency,
however, can be unbearably high. We
therefore show that a good tradeoff
between network lifetime gains and data
latency increases can be obtained by using
those solutions where the mobility of the
sink is controlled by the network
conditions.}
}
@InProceedings{NiditoBB07,
author = {Nidito, F. and Battelli, M. and Basagni, S.},
title = {Fault-tolerant and Load Balancing Localization of
Services in Wireless Sensor Networks},
booktitle = {Proceedings of the $67$th Semi-Annual IEEE Vehicular
Technology Conference, VTC 2007 Fall},
year = 2007,
address = {Baltimore, MD},
month = {September 30--October 3},
abstract = {Heterogeneous wireless sensor networks are
made up of different kinds of nodes. Some
nodes, the \emph{sensors}, are used as an
interface to the physical environment.
Other nodes act instead as servers,
providing various services to the sensors.
In this paper we define an architecture to
enable the sensors to efficiently localize
the services, and hence the servers. Our
is a two-tier server architecture. The
first tier is made up of the actual
\emph{servers}. The second tier is formed
by nodes that are basically standard nodes
(like the sensors). These nodes know the
current position of the servers (they are
called \emph{server locators}). Sensors
needing service query the server locators
to find the corresponding service. The
service locator sends a service position
to the sensor. Finally, once got ahold of
a server location, a sensor uses the
service directly. Our server architecture
provides load balancing (of queries to the
servers) and is tolerant to server
faults. Sensor nodes are endowed with
caches to maintain the location of popular
services. Experiments demonstrate the
effectiveness of using caches at the
sensor nodes.}
}
@InProceedings{BattelliB07,
author = {Battelli, M. and Basagni, S.},
title = {Localization for Wireless Sensor Networks: Protocols
and Perspectives},
booktitle = {Proceedings of IEEE CCECE 2007},
year = 2007,
address = {Vancouver, Canada},
month = {April 22--26},
abstract = {This paper briefly reviews the wide variety of
methods proposed for localizing wireless
sensor nodes. We describe the major
recent solutions where sensor nodes may
use \emph{beacons} (devices that know
their location and can broadcast it) or
not, and ranging measurements or not. Our
discussion presents pros and cons of using
different information or devices, and ends
up with describing where research in this
field in going.}
}
@InProceedings{BasagniNP06,
author = {Basagni, S. and Nanni, M. A. and Petrioli, C.},
title = {Bluetooth Scatternet Formation and Scheduling:
An Integrated Solution},
booktitle = {Proceedings of IEEE MILCOM 2006},
pages = {1--7},
year = 2006,
address = {Washington, DC},
month = {October 23--25},
abstract = {Building and deploying \emph{multi-hop}
networks of Bluetooth devices (aka
\emph{scatternets}) concerns devising
methods for forming \emph{piconets},
connecting them through shared
\emph{gateways}, and scheduling the
presence of these gateways among the
piconets they interconnect
(\emph{inter-piconet scheduling}). There
are several types of gateways, and their
efficient scheduling is affected by the
gateway type. Scatternet formation and
scheduling have been dealt with separately
in the past. This leads to network
performance degradation because of the
missed opportunity of designing scatternet
formation protocols that best address
scheduling requirements and vice-versa.
In this paper we propose SS-Blue, an
integrated mechanism for the joint design
of scatternet formation and scheduling.
Specifically, we enhance an efficient
scatternet formation protocol by adopting
methods for piconets interconnection that
favor types of gateways which will result
in a better performing inter-piconet
scheduling. At the same time, a fair and
traffic adaptive mechanism is proposed to
schedule all types of gateways
(inter-piconet scheduling), and for
managing \emph{intra-piconet scheduling},
i.e., for scheduling traffic transmission
within a piconet. Our solution is
evaluated through extensive simulations.
Our results show that SS-Blue succeeds in
producing scatternets whose gateways are
efficiently scheduled. The combination of
the proposed intra- and inter-piconet
scheduling is shown to be remarkably
effective in favoring packet forwarding
with very low end-to-end latency.}
}
@InProceedings{BasagniCMPW06a,
author = {Basagni, S. and Carosi, A. and Melachrinoudis, E. and
Petrioli, C. and Wang, M. Z.},
title = {A New {MILP} Formulation and Distributed Protocols for
Wireless Sensor Networks Lifetime Maximization},
booktitle = {Proceedings of the IEEE International Conference on
Communications, ICC 2006},
pages = {3517--3524},
volume = 8,
year = 2006,
address = {Istanbul, Turkey},
month = {June 11--15},
abstract = {This paper concerns the definition of an
analytical model and distributed protocols
for determining the routes of a mobile
data collector (\emph{sink}) traveling
through the nodes of a wireless sensor
network (WSN). The routes are determined
with the overall aim of maximizing the
network lifetime. The contribution of our
work is twofold. First, we introduce a
novel mixed integer linear programming
formulation for determining the sink's
route and the sojourn time at the
different ``sink sites.'' The model takes
into account realistic parameters such as
the maximum distance the sink can travel
between sites, different sink mobility
rates, as well as the costs to support and
perform data routing. Solutions to the
model provide the route of the sink as a
sequence of sites and the sojourn times at
those sites that induce the maximum
network lifetime. We then propose the
\emph{Greedy Maximum Residual Energy}
(GMRE) protocol for sink mobility. GMRE is
distributed and localized, thus being
suitable for wireless sensor networking.
In GMRE the sink greedily keeps moving
toward those areas in the network where
there is the most residual energy, as if
``drawn'' to them. This heuristic is then
compared with a very simple and
energy-unaware protocol where the next
site in the sink route is chosen randomly
and uniformly each time the sink moves.
Simulation results show that GMRE leads to
improvements in network lifetime that are
four times as much as the lifetime when
the sink is kept static, while balancing
energy consumption throughout the
network. At the same time, we show how the
expected increases in data latency are
reasonably contained.}
}
@InProceedings{KowalskiBB06,
author = {Kowalski, M. B. and Bertolino, K. D. and Basagni, S.},
title = {Hack {B}oston: Monitoring Wireless Security Awareness in
an Urban Setting},
booktitle = {Proceedings of the IEEE Canadian Conference on Electrical
and Computer Engineering, CCECE 2006},
pages = {1308--1311},
year = 2006,
address = {Ottawa, Canada},
month = {May 7--10},
abstract = {This paper describes ``Hack Boston,'' a
project carried out by members of the IEEE
student chapter at Northeastern University
(NU) in Boston, MA. Our purpose was to
identify the presence of wireless networks
in order to determine qualitatively and
quantitatively how secure these networks
are, thus monitoring the security
awareness of the wireless community around
NU. Our study goes beyond common ``war
driving/war walking.'' We present
statistical results over a range of
metrics that go from the number of
wireless signals in the scanned areas to
the specific encryption method they use
(if any). Experiments have been performed
in 2004 and 2005, which indicate an
increased awareness of the need for
securing in-home wireless Internet
connections. Our results are analyzed and
compared with national statistics. We
finally describe the activities that the
NU IEEE student chapter is proposing for
educating the community about the proper,
secure use of wireless technologies.}
}
@InProceedings{BasagniBIPS06,
author = {Basagni, S. and Battelli, M. and Iachizzi, M. and
Petrioli, C. and Salehi, M.},
title = {Limiting the Propagation of Localization Errors in
Multi-hop Wireless Networks},
booktitle = {Proceedings of the Second IEEE International Workshop
on Sensor Networks and Systems for Pervasive Computing,
PerSeNS 2006},
pages = {1--6},
year = 2006,
address = {Pisa, Italy},
month = {March 13--17},
abstract = {This paper concerns a study of the process of
localizing the nodes of a multi-hop
wireless networks, i.e., of having the
node computing their coordinates with
respect to a suitable reference system.
We consider networks where the nodes
perform measurements of distance and angle
of arrival from nodes within their
transmission radius. We describe a simple
localization protocol, termed Range-Based
Centroid (RBC), that starting from a
single node (the beacon) with given
coordinates localizes all the network
nodes with reasonable accuracy. We then
propose a new localization protocol that
achieves greater accuracy by containing
the propagation of the localization error
as the process progresses away from the
beacon. We quantify the improvements of
the proposed protocol, termed MEC$^{2}$
(for \emph{Minimum Enclosing Circle
Containment}) by simulations. In the
considered scenarios, MEC$^{2}$ keeps the
localization error within $21\%$ of the
nodes' transmission radius, with
$20$-$30\%$ improvements over RBC.}
}
@INPROCEEDINGS{GhoshB06,
AUTHOR = {Ghosh, R. and Basagni, S.},
TITLE = {Napping Backbones: Energy Efficient Topology Control for
Wireless Sensor Networks},
BOOKTITLE = {Proceedings of IEEE Radio and Wireless Symposium, RWS 2006},
YEAR = {2006},
ADDRESS = {San Diego, CA},
MONTH = {January 17--19},
ABSTRACT = {In this study we have investigated the
effectiveness of building ``napping
backbones'' for data dissemination in
wireless sensor networks. The NAPBACK
protocol builds connected backbones whose
nodes are endowed with a sleep/awake
schedule that induces considerable energy
savings, and hence prolongs the network
lifetime. Via simulations on networks with
up to $250$ nodes we have observed
increases on network lifetime up to almost
$70\%$ with respect to previous topology
control protocols (S-DMAC). Increased
latency is the price to pay for the
improvements on lifetime, which currently
makes NAPBACK a viable solution for
delay-insensitive WSN applications.
Multifold are the research directions
opened by this initial study. We are
planning to design different methods for
defining the schedules of the backbone
nodes. Final aims include the minimization
of the latency, as well as throughput
maximization. Sleep/awake scheduling
methods should also be independent of
nodes synchronization, and could be based
on deterministic strategies, rather than
the simple randomized technique used here.}
}
@INPROCEEDINGS{GhoshB05,
AUTHOR = {Ghosh, R. and Basagni, S.},
TITLE = {Limiting the Impact of Mobility on Ad Hoc Clustering},
BOOKTITLE = {Proceedings of the $2$nd ACM Workshop on Performance
Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous
Networks, PE-WASUN 2005},
YEAR = {2005},
ADDRESS = {Montral, Qc., Canada},
MONTH = {October 13},
ABSTRACT = {This paper explores the impact of node
mobility on \emph{DMAC}, a typical
clustering protocol for mobile ad hoc
networks. Several protocols for
clustering have been proposed, which are
quite similar in operations and
performance. We selected one and evaluate
the cost of maintaining the clustering
structures when the nodes move according
to three different mobility models,
na\-me\-ly, the random way point model,
the Brownian motion and the Manhattan
mobility model. Via ns2-based simulations
we have observed that the mobility models
have different impact on protocol
performance. The general trend, however,
appears to be the same for networks of
increasing size. The second contribution
of this paper concerns mitigating the
impact of mobility over the clustering
structure and hence on the overall network
performance. We consider a generalization
of DMAC (GDMAC) where rules are
established to decrease the number of
cluster updates. Via simulation we have
observed that GDMAC is effective in
reducing the clustering overhead imposed
by mobility, and hence its maintenance
cost.}
}
@INPROCEEDINGS{BasagniCMPW05,
AUTHOR = {Basagni, S. and Carosi, A. and Melachrinoudis, E. and
Wang, Z. M.},
TITLE = {Controlling Sink Mobility in Wireless Sensor Networks:
A New Model and Protocols},
BOOKTITLE = {Poster at ACM/SIGMOBILE MobiCom 2005},
YEAR = {2005},
ADDRESS = {Cologne, Germany},
MONTH = {August 28--September 2},
ABSTRACT = {This research concerns the definition of an
analytical model and protocols for
determining the routes of a mobile data
collector (\emph{sink}) traveling through
the nodes of a wireless sensor network
(WSN). The routes are determined with the
overall aim of maximizing the network
lifetime. The contribution of our work is
twofold. First, we introduce a novel mixed
integer linear programming formulation for
determining the sink's route and the
sojourn time at the different ``sink
sites.'' The model takes into account
realistic parameters such as the maximum
distance the sink can travel between sites
as well as constraints on the sojourn time
at a site. Solutions to the model provide
the route of the sink as a sequence of
sites and the sojourns time at those sites
that induce the maximum network lifetime.
We then propose the \emph{Greedy Maximum
Residual Energy} (GMRE) protocol for sink
mobility. Such protocol is distributed and
localized, thus being suitable for wireless
sensor networking. In GMRE the sink
greedily keeps moving toward those areas in
the network where there is the most
residual energy, as if ``drawn'' to
them. This heuristic is then compared with
a very simple and energy-unaware protocol
where the next site in the sink route is
chosen randomly and uniformly each time the
sink moves. Simulation results show
remarkable improvements both for network
lifetime and for balancing energy
consumptions throughout the network in case
GMRE is adopted.}
}
@INPROCEEDINGS{WangMB05,
AUTHOR = {Wang, Z. M. and Melachrinoudis, E. and Basagni, S.},
TITLE = {Voronoi Diagram-Based Linear Programming Modeling of
Wireless Sensor Networks with a Mobile Sink},
BOOKTITLE = {Proceedings of the IIE Annual Conference and Exposition},
YEAR = {2005},
ADDRESS = {Atlanta, GA},
MONTH = {May 14--18},
ABSTRACT = {Wireless sensor networks (WSNs) are
multi-hop wireless networks made up of
energy-constrained sensing devices capable
of delivering the sensed data to one or
more collection points (sinks). In a
typical WSN scenario the sink usually
keeps stationary among the sensors that
are static as well. A recent research
trend aims at proposing energy-efficient
protocols where the mobility of the sink
is exploited for maximizing the lifetime
of the network. A Linear Programming (LP)
model is used for determining the sink
sojourning points (SSPs) and the sojourn
times of the sink that maximize network
lifetime. Sensor nodes are assumed to be
deployed realistically at arbitrary
locations and the SSPs are selected among
the vertices of the Voronoi Diagram (VD)
corresponding to the sensor network
topology. Message routing is also
determined efficiently using the
VD. Experimental results demonstrate the
effectiveness of our LP model in
determining a sink route and sojourn times
along the route that considerably prolong
the network lifetime with respect to the
case with static sink.}
}
@INPROCEEDINGS{WangBMP05,
AUTHOR = {Wang, Z. M. and Basagni, S. and Melachrinoudis, E. and Petrioli, C.},
TITLE = {Exploiting Sink Mobility for Maximizing Sensor Networks Lifetime},
BOOKTITLE = {Proceedings of the $38$th Hawaii International Conference on System Sciences},
YEAR = {2005},
ADDRESS = {Big Island, Hawaii},
MONTH = {January 3--6},
ABSTRACT = {This paper explores the idea of exploiting the
mobility of data collection points (sinks)
for the purpose of increasing the lifetime
of a wireless sensor network with
energy-constrained nodes. We give a novel
linear programming formulation for the
joint problems of determining the movement
of the sink and the sojourn time at
different points in the network that induce
the maximum network lifetime. Differently
from previous solutions, our objective
function maximizes the overall network
lifetime (here defined as the time till the
first node ``dies'' because of energy
depletion) rather than minimizing the
energy consumption at the nodes. For
wireless sensor networks with up to $256$
nodes our model produces sink movement
patterns and sojourn times leading to a
network lifetime up to almost five times
that obtained with a static
sink. Simulation results are performed to
determine the distribution of the residual
energy at the nodes over time. These
results confirm that energy consumption
varies with the current sink location,
being the nodes more drained those in the
proximity of the sink. Furthermore, the
proposed solution for computing the sink
movement results in a fair balancing of the
energy depletion among the network nodes.}
}
@INPROCEEDINGS{BasagniEG04,
AUTHOR = {Basagni, S. and Elia, M. and Ghosh, R.},
TITLE = {{ViBES}: Virtual Backbone for Energy Saving in Wireless Sensor Networks},
BOOKTITLE = {Proceedings of the IEEE Military Communication Conference, MILCOM 2004},
YEAR = {2004},
ADDRESS = {Monterey, CA},
MONTH = {October 31--November 3},
ABSTRACT = {Prolonged lifetime, robustness and scalability
are important requirements in wireless
sensor networks (WSNs). In this paper we
show that via the energy-efficient
construction of a connected backbone and a
simple stateless routing over the backbone
it is possible to achieve these desired
goals. We present a ns2 simulation-based
comparison between data dissemination in
WSNs when a) each sensor routes the sensed
data to the sinks directly (flat network
organization), and b) a backbone is
constructed on top of the flat network
topology and only a few nodes are in charge
of data delivery to the sinks (hierarchical
organization, here termed ViBES: Virtual
Backbone for Energy Saving). Multiple
targets (i.e., moving nodes) are allowed to
roam throughout the network of static
sensors. Simulations are performed on
networks of increasing densities where up
to 3 targets are identified and reported to
up to 3 sinks. Our results show that
routing through the backbone increases the
network lifetime up to seven times over the
flat network organization where network
lifetime is defined as a) the time till the
first node dies because of energy
depletion, b) the time required for $30\%$
of the network nodes to die, and c) the
time required for the network to get
disconnected.}
}
@INPROCEEDINGS{BasagniMP04,
AUTHOR = {Basagni, S. and Mastrogiovanni, M. and Petrioli, C.},
TITLE = {A Performance Comparison of Protocols for Clustering and Backbone Formation in Large Scale Ad Hoc Network},
BOOKTITLE = {Proceedings of The $1$st IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS 2004},
YEAR = {2004},
ADDRESS = {Fort Lauderdale, FL},
MONTH = {October 25--27},
ABSTRACT = {This paper concerns the
comparative performance evaluation of
protocols for clustering and backbone
formation in ad hoc networks
characterized by a large number of
resource-constrained nodes. A typical
example of these networks are wireless
sensor networks. We selected protocols
that represent the main approaches to
clustering and backbone formation for
ad hoc networks. The DCA protocol
represents those protocols whose
backbone construction method is based
on selecting nodes as clusterheads and
then joining them to form a connected
backbone. The algorithm proposed by Wu
and Li has been chosen to exemplify
those algorithms that build a connected
backbone and then prune away redundant
nodes. Finally, the algorithm by Wan
et al.\ has been considered here for
its more theoretical properties of
producing a backbone with a constant
approximation factor, linear time
complexity and optimal message
complexity. Extensive ns2-based
simulation results show that simpler
algorithms are rewarded with good
performance with respect to most metric
of interest which include per node
energy consumption and message
overhead. However, they tend to produce
larger backbones. On the other side,
more complex solutions produce smaller
backbones at greater cost. In order to
obtain a backbone reasonably small at
reasonable cost we propose an
enhancement of the DCA algorithm,
termed DCA-S, which enriches the DCA
backbone construction with a recently
proposed and resource effective
sparsification rule. DCA-S leads to a
robust backbone close in size to that
generated by the Wan et al.\ protocol
without significantly degrading the
performance in terms of all the other
relevant metrics.}
}
@INPROCEEDINGS{BasagniCP04,
AUTHOR = {Basagni, S. and Carosi, A. and Petrioli, C.},
TITLE = {Sensor-{DMAC}: Dynamic Topology Control for Wireless Sensor Network},
BOOKTITLE = {Proceedings of IEEE VTC 2004 Fall},
YEAR = {2004},
ADDRESS = {Los Angles, CA},
MONTH = {September 26--29},
ABSTRACT = {We present Sensor-DMAC
(S-DMAC), a new mechanism for topology
control in wireless sensor networks. A
(connected) fraction of the network
nodes is efficiently selected to
perform the network operation while all
other nodes are switched to an
energy-conserving ``sleep mode.''
Based on DMAC, a clustering protocol
enhanced with backbone formation,
S-DMAC reduces to a minimum the
overhead associated to node selection,
backbone formation and maintenance,
thus increasing the overall network
lifetime. Ns2-based simulations have
been performed to compare S-DMAC with
DMAC and also with GAF, a recent
solution for topology control in
wireless sensor networks. These
results show S-DMAC as more effective
in providing connected and energy
efficient routes of data from the
sensor nodes to the network collection
point (sink).}
}
@INPROCEEDINGS{BasagniBP03,
AUTHOR = {Basagni, S. and Bruno, R. and Petrioli, C.},
TITLE = {A Performance Comparison of Scatternet Formation Protocols for Networks of {B}luetooth Devices},
BOOKTITLE = {Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, Per{C}om 2003},
PAGES = {341--350},
ADDRESS = {Forth Worth, TX},
MONTH = {March 23--26},
YEAR = {2003},
ABSTRACT = {This paper describes the results of an ns2-based
comparative performance evaluation among three
major solutions presented in the literature for
forming multi-hop networks of Bluetooth devices
(\emph{scatternet formation}). The three
protocols considered in this paper are
BlueTrees, BlueStars, and the ``Yao protocol.''
We observed that device discovery is the most
time-consuming operation, independently of the
particular protocol to which it is applied. By
means of a thorough performance evaluation we
have identified protocol parameters and
Bluetooth technology features that affect the
duration of device discovery. We have also
analyzed the effect of the different protocols
operations on key metrics of the generated
scatternets. The comparative performance
evaluation showed that due to the simplicity of
its operations and to its basic working
requirements BlueStars is by far the fastest
protocol for scatternet formation which also
yields to scatternets with a lower number of
piconets, average route length and number of
roles per node. However, BlueStars produces
scatternets with an unbounded, possibly large
number of slaves per piconet, which imposes the
use of potentially inefficient Bluetooth
operations. A good compromise when interested
in forming scatternets whose piconets have a
bounded number of slaves is obtained by
combining BlueStars and the Yao protocol.
Although the time for scatternet formation and
the route lengths are longer than in BlueStars,
with the combined solution we obtain an overall
good protocol performance and scatternets with
desired characteristics.}
}
@INPROCEEDINGS{PetrioliB02,
AUTHOR = {Petrioli, C. and Basagni, S.},
TITLE = {Degree-Constrained Multihop Scatternet Formation for
{B}luetooth Networks},
BOOKTITLE = {Proceedings of IEEE Globecom 2002},
PAGES = {222--226},
ADDRESS = {Taipei, Taiwan, R.O.C.},
MONTH = {November 17--21},
YEAR = {2002},
ABSTRACT = {In this paper we describe \emph{BlueMesh}, a new
protocol for the establishment of
\emph{scatternets}, i.e., multihop ad hoc
networks of Bluetooth devices. BlueMesh defines
rules for device discovery, piconet formation
and piconet interconnection so to achieve the
following desirable properties. $a)$ BlueMesh
generates connected scatternets without
requiring the Bluetooth devices to be all in
each other transmission range. $b)$ The
BlueMesh scatternet topology is a mesh with
multiple paths between any pair of nodes. $c)$
BlueMesh piconets are made up of no more than
$7$ slaves. Simulation results in networks with
$200$ nodes show that BlueMesh is effective in
quickly generating a connected scatternet in
which each node, on average, does not assume
more than $2.3$ roles. Moreover, the length of
routes between any two nodes in the network, is
comparable to that of the shortest paths between
the nodes.}
}
@INPROCEEDINGS{BasagniBP02b,
AUTHOR = {Basagni, S. and Bruno, R. and Petrioli, C.},
TITLE = {Performance Evaluation of a New Scatternet Formation Protocol for Multi-hop {B}luetooth Networks},
BOOKTITLE = {Proceedings of the $5$th International Symposium on Personal Wireless Multimedia Communications, WPMC 2002},
PAGES = {208--212},
ADDRESS = {Honolulu, Hawaii},
MONTH = {October 27--30},
YEAR = {2002},
ABSTRACT = {In this paper we evaluate the performance of a new
protocol for scatternet formation in Bluetooth
multi-hop networks. The protocol implements the
three fundamental steps to scatternet formation,
namely, device discovery, piconet formation and
piconet interconnection. A Bluetooth extension
to ns2, the VINT project simulator, has been
developed to address all the details pertinent
to scatternet formation. The performance
evaluation allows us to assess the impact of the
device discovery duration over the scatternet
formation process, to evaluate the time for the
protocol to generate a connected scatternet, and
to investigate metrics that pertain to the
``quality'' of the scatternet, such as the
average number of piconets, the average number
of slaves per piconets, the average number of
roles assumed by each node and the average
length of the routes between any two Bluetooth
devices.}
}
@INPROCEEDINGS{BasagniBP02a,
AUTHOR = {Basagni, S. and Bruno, R. and Petrioli, C.},
TITLE = {Device Discovery in {B}luetooth Networks:
A Scatternet Perspective},
BOOKTITLE = {Proceedings of the Second IFIP-TC6 Networking
Conference, Networking 2002},
EDITOR = {Gregori, E. and Conti, M. and Campbell, A. T. and
Omidyar, G. and Zuckerman, M.},
PAGE = {1087--1092},
YEAR = {2002},
ADDRESS = {Pisa, Italy},
MONTH = {May 19--24},
ABSTRACT = {The paper concerns device discovery in multi-hop
networks of Bluetooth devices. We start from the
observation that forming a Bluetooth
\emph{scatternet} (i.e., a multi-hop wireless
topology) requires each pair of neighboring
nodes to have a ``symmetric'' knowledge of each
other, i.e., if node $u$ \emph{knows} node $v$
then node $v$ knows node $u$. We investigate the
use of the Bluetooth procedures for device
discovery (\emph{inquiry} procedures) in order
to guarantee the needed symmetric knowledge for
scatternet formation. Through the use of
simulations we observed that despite the long
time required for each node to become aware of
the presence of all its neighbors, the Bluetooth
topologies obtained by using the devices
discovered after just $6$ seconds are
connected. The average number of neighbors of
each node and the average route length are also
consistently close to the values that we would
obtain if all the neighbors of a device were
discovered.}
}
@INPROCEEDINGS{BasagniP02,
AUTHOR = {Basagni, S. and Petrioli, C.},
TITLE = {A Scatternet Formation Protocol for Ad hoc Networks of
{B}luetooth Devices},
BOOKTITLE = {Proceedings of the IEEE Semiannual Vehicular
Technology Conference, VTC Spring 2002},
YEAR = {2002},
ADDRESS = {Birmingham, AL},
MONTH = {May 6--9},
ABSTRACT = {This paper describes a new protocol for the
establishment of multihop ad hoc networks based
on Bluetooth devices. The proposed solution is
specification compatible, and achieves the
following desirable properties, only a few of
which are available in previous solutions. The
protocol is executed at each node with no prior
knowledge of the network topology, thus being
fully distributed. The selection of the
\emph{Bluetooth masters} is driven by the
suitability of a node to be the ``best fit'' for
serving as a master. The generated topology (a
\emph{scatternet}, according to the Bluetooth
terminology) is a connected mesh with multiple
paths between any pair of nodes, thus achieving
robustness. Differently from existing protocols,
the proposed solution does not assume any
designated device to start the scatternet
formation process, and it is multihop in the
precise sense that there is no requirement for
each node to be in the transmission range of all
the other nodes (one-hop networks).}
}
@INPROCEEDINGS{BasagniHBR01,
AUTHOR = {Basagni, S. and Herrin, K. and Bruschi, D. and
Rosti, E.},
TITLE = {Secure Pebblenet},
BOOKTITLE = {Proceedings of the 2001 ACM Iternational Symposium
on Mobile Ad Hoc Networking \& Computing, MobiHoc 2001},
PAGES = {156--163},
YEAR = {2001},
ADDRESS = {Long Beach, CA},
MONTH = {October 4--5},
ABSTRACT = {We consider the problem of securing communication in
large ad hoc networks, i.e., wireless networks
with no fixed, wired infrastructure and with
multi-hop routes. Such networks, e.g., networks
of sensors, are deployed for applications such
as microsensing, monitoring and control, and for
extending the peer-to-peer communication
capability of smaller group of network users.
Because the nodes of these networks, which we
term {\em pebbles} for their very limited size
and large number, are resource constrained, only
symmetric key cryptography is feasible. We
propose a key management scheme to periodically
update the symmetric keys used by all pebbles.
By combining mobility-adaptive clustering and an
effective probabilistic selection of the
key-generating node, the proposed scheme meets
the requirements of efficiency, scalability and
security needed for the survivability of
networks of pebbles (\emph{pebblenets}).}
}
@INPROCEEDINGS{BasagniTD01,
AUTHOR = {Basagni, S. and Turgut, D. and Das, S. K.},
TITLE = {Mobility-Adaptive Protocols for Managing Large Ad Hoc
Networks},
BOOKTITLE = {Proceedings of the IEEE International Conference on
Communications, ICC 2001},
ADDRESS = {Helsinki, Finland},
MONTH = {June 11--14},
YEAR = {2001},
ABSTRACT = {In this paper, we propose a new protocol for
efficiently managing large ad hoc
networks, i.e., networks in which all
nodes can be mobile. We observe that,
since nodes in such networks are not
necessarily equal in that they may
have different resources, not all of
them should be involved in basic
network operations such as packet
forwarding, flooding, etc. In the
proposed protocol, a small subset of
the network nodes is selected based on
their status and they are organized to
form a \emph{backbone} (whence the
name ``backbone protocol'' or simply
\emph{B-protocol} to our proposed
solution). The B-protocol operates in
two phases: first the ``most
suitable'' nodes are selected to serve
as backbone nodes, then the selected
nodes are linked to form a backbone
which is guaranteed to be connected if
the original network is. The
effectiveness of the B-protocol in
constructing and maintaining in face
of node mobility and node/link failure
a connected backbone that uses only a
small fraction of the nodes and of the
links of the original networks is
demonstrated via simulation. The
obtained results show that both the
selected backbone nodes and the links
between them in the backbone are
considerably smaller than the nodes
and the links in the flat network.}
}
@INPROCEEDINGS{Basagni01a,
AUTHOR = {Basagni, S.},
EDITOR = {Sha, E.},
TITLE = {Proving Lower Bounds for Distributed Ad Hoc Broadcast},
BOOKTITLE = {Proceedings of the $14$th International Conference
on Parallel and Distributed Computing Systems,
PDCS 2001},
ADDRESS = {Dallas, TX},
MONTH = {August 8--10},
YEAR = {2001},
ABSTRACT = {\emph{Broadcast} is the network operation that
concerns disseminating a message from
a given node to every other node in
the network. When a network is
comprised of mobile nodes, as in
\emph{ad hoc} networks where
potentially all the nodes can be
mobile, broadcast protocols need to be
\emph{distributed}, i.e., they should
be executed at each node with the
minimum possible knowledge of the
dynamically changing network topology.
This paper presents a general method
for proving lower bounds for the
problem of distributed broadcast in
mobile ad hoc networks. As a
consequence of the generality of the
proposed method, previously proven
lower bounds, both for randomized and
deterministic broadcast, can be seen
as specific applications of the
proposed method. The effectiveness of
our framework is also demonstrated by
proving in a simpler and direct way
the linear lower bound proven for
deterministic broadcast in networks
with constant diameter.}
}
@INPROCEEDINGS{ZarubaBC01,
AUTHOR = {Z\'aruba, G. and Basagni, S. and Chlamtac, I.},
TITLE = {Blue{T}rees---{S}catternet Formation to Enable
{B}luetooth-Based Personal Area Networks},
BOOKTITLE = {Proceedings of the IEEE International Conference on
Communications, ICC 2001},
ADDRESS = {Helsinki, Finland},
MONTH = {June 11--14},
YEAR = {2001},
ABSTRACT = {Bluetooth is an open specification for
short-range wireless communication and
networking, mainly intended to be a
cable replacement between portable
and/or fixed electronic devices. The
specification also defines techniques
for interconnecting large number of
nodes in \emph{scatternets}, thus
enabling the establishment of a
\emph{mobile ad hoc network} (MANET).
While several solutions and commercial
products have been introduced for
one-hop Bluetooth communication, the
problem of \emph{scatternet formation}
has not yet been dealt with. This
problem concerns the assignment of the
roles of \emph{master} and
\emph{slave} to each node so that the
resulting MANET is connected. In this
paper we introduce two novel protocols
for forming connected scatternets. In
both cases, the resulting topology is
termed a \emph{bluetree}. In our
bluetrees the number of roles each
node can assume are limited to two or
three (depending on the protocol),
thus imposing low slave management
overhead. The effectiveness of both
protocols in forming MANETs is
demonstrated through extensive
simulations.}
}
@INPROCEEDINGS{CheccacciBBB00,
AUTHOR = {Checcacci, N. and Barni, M. and Bartolini, F. and
Basagni, S.},
TITLE = {Robust Video Watermarking for Wireless Multimedia
Communications},
BOOKTITLE = {Proceedings of the IEEE Wireless Communication and
Networking Conference, WCNC 2000},
ADDRESS = {Chicago, IL},
MONTH = {September 23--28},
YEAR = {2000},
ABSTRACT = {{\em Digital watermarking} involves embedding
copyright marks ({\em watermarks}\,),
often imperceptibly, in multimedia
objects to enhance or protect their
value. In this paper we describe a
novel watermarking algorithm suitable
for {\em video coding techniques} such
as MPEG-4 and H.263/.324 and we test
it in a wireless environment. The
proposed algorithm satisfies critical
properties not all of which are
available in previous solutions. These
properties include: Resistance
(robustness) of the embedded watermark
to the error-prone nature of wireless
channels as well as to video frame
loss or misplacement, negligible
probability of reading a non embedded
watermark, non-degradation of the
marked video sequence and the
possibility to mark video objects
(e.g., MPEG-4 objects) in a single
frame separately. Experimental results
are given that show how these and
other properties are achieved when
video sequences are corrupted with
errors that are typical of a wireless
channel.}
}
@INPROCEEDINGS{BasagniCST00,
AUTHOR = {Basagni, S. and Chlamtac, I. and Syrotiuk, V. and
Talebi, R.},
TITLE = {Dynamic Source Multicast for Multi-hop Wireless
Networks},
BOOKTITLE = {Proceedings of the IEEE Wireless Communication and
Networking Conference, WCNC 2000},
ADDRESS = {Chicago, IL},
MONTH = {September 23--28},
YEAR = {2000},
ABSTRACT = {This paper introduces {\em OLAM\,}, a novel
{\em On-demand Location Aware
Multicast} protocol for ad hoc
networks. The protocol assumes that,
through the use of positioning system
devices, such as Global Positioning
System (GPS) devices, each node knows
its own position and the current
(global) time, and it is able to
efficiently distribute these measures,
including its current transmission
radius, to all other nodes. As the
measures are received, each node
updates its local {\em snapshot} of
the complete network topology. When a
packet is to be multicast to a group,
a heuristic is then used to locally
compute the {\em Steiner} (i.e.,
multicast) tree for the addressed
multicast group based on the snapshot
rather than maintaining the tree in a
distributed manner. The resulting
Steiner tree is then optimally encoded
by using its unique {\em Pr\"{u}fer
sequence} and included along with the
packet, extending the length of the
header by no more than the header of
packets in source routing (unicast)
techniques. All local computations are
executed using efficient (i.e.,
polynomial time) algorithms. The
protocol has been simulated in ad hoc
networks with 30 and 60 nodes and with
different multicast group sizes. We
show that OLAM delivers packets to all
the nodes in a destination group in
more than $85\%$ of the cases.
Furthermore, compared to flooding,
OLAM achieves improvements of up to
$50\%$ on multicast completion delay.}
}
@INPROCEEDINGS{BasagniCS00,
AUTHOR = {Basagni, S. and Chlamtac, I. and Syrotiuk, V.},
TITLE = {Using Location Awareness for one-to-many Communication
in Mobile Multihop Wireless Networks},
BOOKTITLE = {Proceedings of the IEEE Semiannual Vehicular
Technology Conference, VTC 2000 Spring},
ADDRESS = {Tokyo, Japan},
MONTH = {May 15--18},
YEAR = {2000},
ABSTRACT = {This paper presents a uniform solution for
multipoint communication in mobile
multi-hop wireless networks, spanning
the full range of problems from
routing to broadcast. Using a
dissemination mechanism, each node
distributes its own attributes, such
as its position, time, and
transmission radius, to all other
nodes in the network. Through the
dissemination, each node becomes aware
of the location of all other nodes in
the network. Thus when a packet is to
be transmitted, the node that is the
source of the packet is able to
locally compute a ``snapshot'' of the
network topology from the collected
node attributes. A tree that
describes the path(s) to follow to
reach the destination(s) of the
multipoint communication is then
locally computed on the resulting
snapshot. The tree obtained is
optimally encoded by its unique {\em
Pr\"{u}fer sequence}, included in the
packet header, and then the path(s)
traversed hop-by-hop as in any source
routing technique. A finite tree with
$j$ nodes can be encoded by a
Pr\"{u}fer sequence of length $j-2$,
thus the Steiner tree for a multicast
packet or the spanning tree for a
broadcast packet is encoded as
efficiently as the longest path in
routing. All the local computations
are efficient, being executed in
polynomial time. Specifically,
computing the appropriate tree, and
the encoding/decoding procedures of
the related Pr\"{u}fer sequence,
requires $O(n^{2})$ time, where $n$ is
the number of nodes in the multi-hop
network. Our uniform solution to
multipoint communication has been
simulated in multi-hop wireless
networks with up to $n=30$ nodes,
showing a success rate of $98\%$ and
$97\%$ for routing and multicast,
respectively.}
}
@INPROCEEDINGS{BasagniCFST99,
AUTHOR = {Basagni, S. and Chlamtac, I. and Farag\'o, A. and
Syrotiuk, V. R. and Talebi, R.},
TITLE = {Route Selection in Mobile Multimedia Ad Hoc
Networks},
BOOKTITLE = {Proceedings of the Sixth IEEE International Workshop
on Mobile Multimedia Communications, MoMuC'99},
PAGES = {97--103},
ADDRESS = {San Diego, CA},
MONTH = {November 15--17},
YEAR = {1999},
ABSTRACT = {The problem of routing packets in ad hoc networks is
complex due to the lack of network infrastructure,
shifting the reliance of packet forwarding onto the
nodes of the network, all of which are mobile. In
order to improve the robustness and adaptation of
protocols for ad hoc networks to node mobility, in
this paper we propose a new metric that bases route
selection on the probability of the existence of the
route (route availability). Specifically, we derive
a simple closed form expression for the computation
of the availability of a route, that takes into
account node mobility and dependencies between
links, which can then be used to satisfy the
requirements of multimedia applications. In
particular, we show how by efficiently collecting
measures about the geographic location of other
nodes, each node of an ad hoc network can locally
and efficiently compute multiple paths to a given
destination node, and, based on the introduced
metric, choose the route that best meets the strict
requirements of multimedia applications.}
}
@INPROCEEDINGS{Basagni99e,
AUTHOR = {Basagni, S.},
TITLE = {A Distributed Algorithm for Finding a Maximal
Weighted Independent Set in Wireless Networks},
BOOKTITLE = {Proceedings of the Eleventh IASTED International
Conference on Parallel and Distributed Computing and
Systems ({PDCS'99})},
EDITOR = {Zheng, S. Q.},
PAGES = {517--522},
VOLUME = {1},
ADDRESS = {Cambridge, MA},
MONTH = {November 3--5},
YEAR = {1999},
ABSTRACT = {This paper introduces {\em MWIS}, a distributed
algorithm for the efficient determination of a
Maximum Weighted Independent Set in the topology
graph $G$ of a wireless network. Motivated by the
observation that the problem of partitioning
wireless nodes into {\em clusters} easily reduces to
the problem of finding a maximum weighted
independent set of nodes, the proposed algorithm is
described by taking into account two main
characteristic of wireless networks, namely, the
broadcast nature of the wireless medium and the
possibility to support nodes mobility. MWIS is
executed at each node by means of fast
message-triggered procedures that require the sole
knowledge of the topology local to the
node. Moreover, its time complexity is proven to be
bounded by the (topology dependent) {\em stability
number} $\alpha(G)$, rather than by the (invariant)
number $n$ of the network nodes. Finally, by using a
well known results on the stability number in {\em
random graphs}, we show that the average time
complexity of the MWIS is logarithmic in $n$.}
}
@INPROCEEDINGS{BasagniCS99b,
AUTHOR = {Basagni, S. and Chlamtac, I. and Syrotiuk, V. R.},
TITLE = {Dynamic Source Routing for Ad Hoc Networks Using the
Global Positioning System},
BOOKTITLE = {Proceedings of the IEEE Wireless Communications and
Networking Conference 1999 ({WCNC'99})},
ADDRESS = {New Orleans, LA},
MONTH = {September 21--24},
YEAR = {1999},
ABSTRACT = {This paper proposes a new routing protocol for ad
hoc networks built around the source routing
technique combined with the location (e.g., GPS
coordinates) of nodes obtained by an energy and
distance smart dissemination mechanism. The key new
observation used is that the location information
provides each node with a snapshot of the topology
of the complete network from which a source route
may be computed locally rather than through route
discovery. The resulting protocol has reduced delay,
and is more bandwidth and energy efficient, than
both traditional (proactive and reactive) ad hoc
routing protocols, as well as location based routing
protocols.}
}
@INPROCEEDINGS{Basagni99d,
AUTHOR = {Basagni, S.},
TITLE = {Distributed and Mobility-Adaptive Clustering for
Multimedia Support in Multi-Hop Wireless Networks},
BOOKTITLE = {Proceedings of the IEEE $50$th International
Vehicular Technology Conference, VTC 1999-Fall},
VOLUME = {2},
PAGES = {889--893},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {September 19--22},
YEAR = {1999},
ABSTRACT = {A distributed algorithm is presented that partitions
the nodes of a fully mobile network ({\em multi-hop
wireless} network) into {\em clusters}, thus giving
the network a hierarchical organization. The
algorithm is proven to be adaptive to changes in the
network topology due to nodes' mobility and to nodes
addition/removal. A new weight-based mechanism is
introduced for the efficient cluster
formation/maintenance that allows the cluster
organization to be configured for specific
applications and adaptive to changes in the network
status, not available in previous
solutions. Specifically, new and flexible criteria
are defined that allow the choice of the nodes that
coordinate the clustering process based on mobility
parameters and/or their current status. Simulation
results are provided that demonstrate up to an
$85\%$ reduction on the communication overhead
associated with the cluster maintenance with respect
to techniques used in clustering algorithms
previously proposed.}
}
@INPROCEEDINGS{Basagni99c,
AUTHOR = {Basagni, S.},
TITLE = {Distributed Clustering for Ad Hoc Networks},
BOOKTITLE = {Proceedings of the 1999 International Symposium on
Parallel Architectures, Algorithms, and Networks
({I-SPAN'99})},
EDITOR = {Zomaya, A. Y. and Hsu, D. F. and Ibarra, O. and
Origuchi, S. and Nassimi, D. and Palis, M.},
PUBLISHER = {IEEE Computer Society},
PAGES = {310--315},
ADDRESS = {Perth/Fremantle, Australia},
MONTH = {June 23--25},
YEAR = {1999},
ABSTRACT = {A {\em Distributed Clustering Algorithm} (DCA) and a
{\em Distributed Mobility-Adaptive Clustering}
(DMAC) algorithm are presented that partition the
nodes of a fully mobile network ({\em ad hoc}
network) into {\em clusters}, thus giving the
network a hierarchical organization. Nodes are
grouped by following a new {\em weight}-based
criterion that allows the choice of the nodes that
coordinate the clustering process based on node
mobility-related parameters. The DCA is suitable for
clustering ``quasi-static'' ad hoc networks. It is
easy to implement and its time complexity is proven
to be bounded by a network parameter that depends on
the {\em topology} of the network rather than on its
{\em size}, i.e., the invariant number of the
network nodes. The DMAC algorithm adapts to the
changes in the network topology due to the mobility
of the nodes, and it is thus suitable for any mobile
environment. Both algorithms are executed at each
node with the sole knowledge of the identity of the
one hop neighbors, and induce on the network the
same clustering structure.}
}
@INPROCEEDINGS{Basagni99b,
AUTHOR = {Basagni, S.},
TITLE = {Distributed Clustering for Multi-Hop Wireless
Networks},
BOOKTITLE = {Proceedings of the IEEE International Symposium on
Wireless Communications ({ISWC'99})},
EDITOR = {Annamalai, A. and Tellambura, C.},
PAGES = {41--42},
ADDRESS = {Victoria, BC, Canada},
MONTH = {June 3--4},
YEAR = {1999}
}
@INPROCEEDINGS{BasagniCS99a,
AUTHOR = {Basagni, S. and Chlamtac, I. and Syrotiuk, V. R.},
TITLE = {Geographic Messaging in Wireless Ad Hoc Networks},
BOOKTITLE = {Proceedings of the IEEE $49$th Annual International
Vehicular Technology Conference},
VOLUME = {3},
PAGES = {1957--1961},
ADDRESS = {Houston, TX},
MONTH = {May 16--20},
YEAR = {1999},
ABSTRACT = {This paper presents a network layer mechanism for
the efficient dissemination of Global Positioning
System (GPS) based node position in {\em ad hoc
networks}, and shows its application to problems
involving geographic awareness. In particular, we
describe how, based on a ``position database''
maintained through the dissemination mechanism, a
node of the network can direct messages to all the
nodes currently present in a precise geographic
area. The effectiveness and accuracy of the
dissemination mechanism is demonstrated through the
use of simulations. We show that for ad hoc networks
with up to $60$ nodes, the position database
correctly determines which nodes are actually in the
expected geographic area the $97\%$ of the time.}
}
@INPROCEEDINGS{BasagniMS99,
AUTHOR = {Basagni, S. and Myers, A. D. and Syrotiuk, V. R.},
TITLE = {Mobility-Independent Flooding for Real-Time,
Multimedia Applications in Ad Hoc Networks},
BOOKTITLE = {Proceedings of 1999 IEEE Emerging Technologies
Symposium on Wireless Communications \& Systems},
ADDRESS = {Richardson, TX},
MONTH = {April 12--13},
YEAR = {1999},
ABSTRACT = {This paper describes the use of {Time-Spread
Multiple-Access} (TSMA) protocols for realizing the
dissemination (``flooding'') of data and/or control
packets in networks characterized by the lack of a
fixed infrastructure ({\em ad hoc} networks). We
show that, due to the unique characteristics of
TSMA, namely, that it is independent of the changes
in the network topology due to node mobility and it
is deterministic, it is effective for implementing
and/or supporting those ad hoc networks primitives
that are crucial for delay-sensitive applications,
such as multimedia. Through the use of simulation,
we finally show that the average broadcast delay for
TSMA-based flooding remains stable for higher
network loads when compared to the average delay of
simple TDMA-, Aloha- and Slotted Aloha- based
flooding.}
}
@INPROCEEDINGS{FaragoCB99,
AUTHOR = {Farag\'o, A. and Chlamtac, I. and Basagni, S.},
TITLE = {Virtual Path Network Topology Optimization Using
Random Graphs},
BOOKTITLE = {Proceedings of IEEE INFOCOM'99. The Conference on
Computer Communications},
VOLUME = {2},
PAGES = {491--496},
ADDRESS = {New York, NY},
MONTH = {March 21--25},
YEAR = {1999},
ABSTRACT = {An algorithm is presented for designing the logical
topology of the virtual path (VP) network, an
important task in ATM network design. We prove that
the algorithm provides a VP network topology that is
asymptotically optimal with respect to both
connectivity and the diameter of the network. These
optimality properties are combined with algorithmic
simplicity and polynomial running time, thus
overcoming the notorious ``optimality vs.\
scalability'' dilemma. This result is made possible
by applying the theory of {\em random graphs} to
this type of networks. This theory has the
methodological advantage of increased accuracy with
growing network size, thus turning the ``curse of
dimensionality'' into a blessing. Therefore, the
paper exemplifies that the theory of random graphs,
beyond supporting analysis purposes, may serve as a
useful tool in the design of algorithms that
overcome the ``scalability bottleneck,'' a problem
that prevents current approaches from finding
near-optimal solutions as today's networks grow in
size and complexity.}
}
@INPROCEEDINGS{BasagniCSW98,
AUTHOR = {Basagni, S. and Chlamtac, I. and Syrotiuk, V. R.
and Woodward, B. A.},
TITLE = {A Distance Routing Effect Algorithm for Mobility
({DREAM})},
BOOKTITLE = {Proceedings of the Fourth Annual ACM/IEEE
International Conference on Mobile Computing and
Networking, MobiCom'98},
PAGES = {76--84},
ADDRESS = {Dallas, TX},
MONTH = {October 25--30},
YEAR = {1998},
ABSTRACT = {In this paper we introduce a new routing protocol for
ad hoc networks built around two novel observations.
One, called the {\em distance effect}, uses the fact
that the greater the distance separating two nodes,
the slower they appear to be moving with respect to
each other. Accordingly, the {\em location
information} in routing tables can be updated as a
function of the distance separating nodes without
compromising the routing accuracy. The second idea is
that of triggering the sending of location updates by
the moving nodes autonomously, based only on a node's
{\em mobility rate}. Intuitively, it is clear that
in a directional routing algorithm, routing
information about the slower moving nodes needs to be
updated less frequently than that about highly mobile
nodes. In this way each node can optimize the
frequency at which it sends updates to the networks
and correspondingly reduce the bandwidth and energy
used, leading to a fully distributed and
self-optimizing system. Based on these routing
tables, the proposed directional algorithm sends
messages in the ``recorded direction'' of the
destination node, guaranteeing delivery by following
the direction with a given probability. We show by
detailed simulation that our protocol always delivers
more than $80\%$ of the data messages by following
the direction computed, without using any recovery
procedure. In addition, it minimizes the overhead
used for maintaining routes using the two new
principles of update message frequency and distance.
Lastly, the algorithm is fully distributed, provides
loop-free paths, and is robust, since it supplies
multiple routes.}
}
@INPROCEEDINGS{BasagniC98,
AUTHOR = {Basagni, S. and Chlamtac, I.},
TITLE = {Broadcast in Peer-to-Peer Networks},
BOOKTITLE = {Proceedings of the Second IASTED International
Conference European Parallel and Distributed Systems,
Euro-PDS'98},
EDITOR = {Bukhres, O. and {El-Rewini}, H.},
PAGES = {117--122},
ADDRESS = {Vienna, Austria},
MONTH = {July 3--5},
YEAR = 1998,
ABSTRACT = {Broadcasting (distributing a message from a source
to all other nodes) is a fundamental requirement
of distributed computing. In this paper we propose
deterministic, delivery-guaranteed distributed
protocols for solving this problem in wireless networks
that have a peer-to-peer (i.e., non-cellular)
organization. Deterministic and
delivery-guaranteed protocols are defined as
solutions which are always executed within an a
priori determined period of time, and such that
their success does not depend on, or require,
collision detection mechanisms. The proposed protocols
are distributed in the sense that they can be
executed at each node without topology knowledge
and, moreover, they do not assume any underlying
network architecture. We characterize the broadcast
problem as a combinatorial problem for the
solution of which we propose here a novel,
explicit and completely deterministic method. The
derived protocol is proved to complete the broadcast
of a message in time that is polylogarithmic in
the size $n$ of the network, and we prove that it
is optimal for networks with specific topologies.}
}
@INPROCEEDINGS{BasagniCS98expo,
AUTHOR = {Basagni, S. and Chlamtac, I. and Syrotiuk, V. R.},
TITLE = {Directional Distance Routing ({$D^2 R$}) for Ad Hoc
Networks},
BOOKTITLE = {Technical Symposium and Exhibition SMTA/IMAPS
EXPO 98},
ADDRESS = {Plano, TX},
MONTH = {April 27--28},
YEAR = 1998
}
@INPROCEEDINGS{BasagniCF97,
AUTHOR = {Basagni, S. and Chlamtac, I. and Farag\'o, A.},
TITLE = {A Generalized Clustering Algorithm for Peer-to-Peer
Networks},
BOOKTITLE = {Workshop on Algorithmic Aspects of Communication,
satellite workshop of ICALP'97, invited paper},
ADDRESS = {Bologna, Italy},
MONTH = {July 11--12},
YEAR = 1997,
ABSTRACT = {An algorithm is proposed for efficiently
clustering the nodes of a mobile wireless network
that has a ``peer-to-peer'' (i.e., non-cellular)
organization. The algorithm is a common generalization
of different methods proposed for this problem so
far in the literature. We define the {\em worst
case performance ratio} $\rho$ of the algorithm in
a way that indicates how well the proposed
heuristic performs compared to the optimum algorithm.
We show that $\rho$ is non trivially bounded by a
function of the {\em degree} of the network.
Moreover, we prove that our algorithm is {\em
optimal}. Specifically, given that NP-complete
problems cannot be solved in polynomial time, we
show that in an unconstrained topology we cannot
devise efficient clustering algorithms that
perform better than ours.}
}