Journal Publications
@Article{GhoshB08,
author = {Ghosh, R. and Basagni, S.},
title = {Mitigating the Impact of Node Mobility on Ad Hoc
Clustering},
journal = {Wiley InterScience's Wireless Communications \&
Mobile Computing, WCMC},
year = 2008,
volume = 8,
number = 3,
month = {March},
note = {To appear},
abstract = {This paper explores the impact of node
mobility on \emph{DMAC}, a typical
clustering protocol for mobile ad hoc
networks. In particular, in this paper we
evaluate the cost of maintaining the DMAC
clustering structures when the nodes move
according to three different mobility
models, namely, 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
investigating ways of mitigating the
impact of mobility on the clustering
structure and hence over 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 the corresponding
maintenance cost.}
}
@Article{BasagniPP07a,
author = {Basagni, S. and Petrioli, C. and Petroccia, R.},
title = {Efficiently Reconfigurable Backbones for
Wireless Sensor Networks},
journal = {Computer Communications Journal, Special Issue on
Algorithmic and Theoretical Aspects of Wireless
Ad Hoc and Sensor Networks, S. Misra, ed.},
year = 2007,
note = {In press},
abstract = {We present the definition and performance
evaluation of a protocol for building and
maintaining a connected backbone among the
nodes of a wireless sensor networks (WSN).
Building backbones first, and then coping
with network dynamics is typical of
protocols for backbone formation. Rules
for building the backbone, however, do not
take into account the following network
dynamics explicitly. This makes
maintaining a connected backbone quite
costly, especially in terms of
reorganization time, overhead and energy
consumption. Our protocol includes in the
backbone forming operations a fail-safe
mechanism for dealing with the addition
and the removal of nodes, which are
typical events in a WSN. More
specifically, the network is kept
partitioned into clusters that are
\emph{cliques}, i.e., nodes in each
cluster are directly connected to each
others. Therefore, removing a node does
not disrupt a cluster, and adding one
requires simple operations for checking
node admission to the cluster. The
protocol, termed CC (``double c,'' for
\emph{clique clustering}), comprises three
phases, each designed to render the
operations of the others swift and
efficient. The first phase partitions the
network into clusters that are cliques.
Clusters are then joined to form a
backbone that is provably connected.
Finally, the third, more on-line phase,
maintains the backbone connected in face
of node additions and removals. 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
network dynamics. Our comparison concerns
metrics that are central to WSN research,
such as time for clustering and backbone
reorganization, corresponding overhead,
extent of the reorganization (i.e., number
of nodes involved in it), and properties
of the resulting backbone, such as its
size, backbone route length, number of
gateway and nodes per cluster. Our
ns2-based simulation results show that the
design criteria chosen for CC are
effective in producing backbones that can
be reconfigured quickly and with
remarkably lower overhead.}
}
@Article{BasagniCMPW07,
author = {Basagni, S. and Carosi, A. and Melachrinoudis, E. and
Petrioli, C. and Wang, Z. M.},
title = {Controlled Sink Mobility for Prolonging Wireless
Sensor Networks Lifetime},
journal = {ACM/Elsevier Wireless Networks},
year = 2007,
note = {To appear},
abstract = {This paper demonstrates the advantages of
using controlled mobility in wireless
sensor networks (WSNs) for increasing
their lifetime i.e., the period of time
the network is able to provide its
intended functionalities. More
specifically, for WSNs that comprise a
large number of statically placed sensor
nodes transmitting data to a collection
point (the sink), we show that by
controlling the sink movements we can
obtain remarkable lifetime improvements.
In order to determine sink movements, we
first define a Mixed Integer Linear
Programming (MILP) analytical model whose
solution determines those sink routes that
maximize network lifetime. Our
contribution expands further by defining
the first heuristics for controlled sink
movements that are fully distributed and
localized. Our \emph{Greedy Maximum
Residual Energy} (GMRE) heuristic moves
the sink from its current location to a
new site as if drawn toward the area where
nodes have the highest residual energy.
We also introduce a simple distributed
mobility scheme (\emph{Random Movement} or
RM) according to which the sink moves
uncontrolled and randomly throughout the
network. The different mobility schemes
are compared through extensive ns2-based
simulations in networks with different
nodes deployment, data routing protocols,
and constraints on the sink movements. In
all considered scenarios, we observe that
moving the sink always increases network
lifetime. In particular, our experiments
show that controlling the mobility of the
sink leads to remarkable improvements,
which are as high as sixfold compared to
having the sink statically (and optimally)
placed, and as high as twofold compared to
uncontrolled mobility.}
}
@Article{BasagniCMPW06,
author = {Basagni, S. and Carosi, A. and Melachrinoudis, E. and
Petrioli, C. and Wang, Z. M.},
title = {Protocols and Model for Sink Mobility in Wireless
Sensor Networks},
journal = {ACM Mobile Computing and Communication Review, MC$^{2}$R},
year = 2006,
volume = 10,
number = 4,
pages = {28--30},
month = {October},
abstract = {This paper concerns the definition of an
analytical model and of a distributed
protocol, termed \emph{Greedy Maximum
Residual Energy} (GMRE), 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. An
ns2-based simulation comparison between
GMRE, optical static sink placement and
random sink mobility shows that GMRE
yields remarkable improvements both for
network lifetime and for balancing energy
consumptions throughout the network.}
}
@Article{BasagniMPP06,
author = {Basagni, S. and Mastrogiovanni, M. and Panconesi, A.
and Petrioli, C.},
title = {Localized Protocols for Ad Hoc Clustering and
Backbone Formation: A Performance Comparison},
journal = {IEEE Transactions on Parallel and Distributed Systems,
Special Issue on Localized Communication and Topology
Protocols for Ad Hoc Networks
(S.~Olariu, D.~Simplot-Ryl, and I.~Stojmenovic, editors)},
year = 2006,
volume = 17,
number = 4,
pages = {292--306},
month = {April},
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. Our
aim is twofold. We provide the first
simulation-based detailed investigation of
techniques for clustering and backbone
formation that are among the most
representative of this area of ad hoc
research. Furthermore, we delve into the
nature of the selected protocols to assess
the effects of the ``degree of
localization'' on their operations, i.e.,
how being able to execute the protocol
based only on local information affects
the overall protocol performance.
Extensive ns2-based simulation results
show that highly localized protocols are
rewarded with good performance with
respect to all metrics of interest which
include protocol duration, energy
consumption, message overhead, route
length and backbone size.}
}
@Article{BasagniBMP04,
author = {Basagni, S. and Bruno, R. and Mambrini, G. and
Petrioli, C.},
title = {Comparative Performance Evaluation of Scatternet
Formation Protocols for Networks of Bluetooth
Devices},
journal = {ACM/Kluwer Wireless Networks},
year = 2004,
volume = 10,
number = 2,
pages = {197--213},
month = {March},
abstract = {This paper describes the results of the first
ns2-based comparative performance
evaluation among four major solutions
presented in the literature for forming
multi-hop networks of Bluetooth devices
(\emph{scatternet formation}). The four
protocols considered in this paper are
\emph{BlueTrees} \cite{ZarubaBC01},
\emph{BlueStars} \cite{PetrioliBC03a},
\emph{BlueNet} \cite{WangTH02} and the
protocol presented in \cite{LiS02} which
proposes geometric techniques for topology
reduction combined with cluster-based
scatternet formation. We implemented the
operations of the four protocols from
device discovery to scatternet formation.
By means of a thorough performance
evaluation we have identified protocol
parameters and Bluetooth technology
features that affect the duration of the
formation process and the properties of
the produced scatternet. We have
investigated how possible modifications of
the BT technology (e.g., backoff duration,
possibility for a BT inquirer to identify
itself) make device discovery more
efficient for scatternet formation in
multi-hop networks. We have then
discussed implementation concerns for each
of the selected protocols. Finally, we
have analyzed the protocols overhead as
well as the effect of the different
protocols operations on key metrics of the
generated scatternets, which includes the
time needed for forming a scatternet, the
number of its piconets, the number of
slaves per piconet, the number of roles
assumed by each node and the scatternet
route lengths.}
}
@article{PetrioliBC04,
author = {Petrioli, C. and Basagni, S. and Chlamtac, I.},
title = {Blue{M}esh: Degree-Constrained Multihop Scatternet
Formation for {B}luetooth Networks},
journal = {ACM/Kluwer Journal on Special Topics in Mobile
Networking and Applications (MONET),
Special Issue on Advances in Research
of Wireless Personal Area Networking
and Bluetooth Enabled Networks
(G.~Zaruba and P.~Johansson, editors)},
volume = {9},
issue = {1},
pages = {33--47},
month = {February},
year = {2004},
abstract = {In this paper we describe \emph{BlueMesh}, a new
protocol for the establishment of
\emph{scatternets}, i.e., multi-hop wireless
networks of Bluetooth devices. BlueMesh defines
rules for device discovery, piconet formation
and piconet interconnection so to generate
connected scatternets with the following
desirable properties. BlueMesh forms
scatternets without requiring the Bluetooth
devices to be all in each other transmission
range. BlueMesh scatternet topologies are
meshes with multiple paths between any pair of
nodes. BlueMesh piconets are made up of no more
than $7$ slaves. Simulation results in networks
with over $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.4$ roles. Moreover, the
route length between any two nodes in the
network is comparable to that of the shortest
paths between the nodes.}
}
@article{PetrioliBC03a,
author = {Petrioli, C. and Basagni, S. and Chlamtac, I.},
title = {Configuring {B}lue{S}tars: Multihop Scatternet Formation
for {B}luetooth Networks},
journal = {IEEE Transactions on Computers, Special Issue on
Wireless Internet (Y.-B.~Lin and Y.-C.~Tseng, editors)},
volume = {52},
number = {6},
pages = {779--790},
month = {June},
year = {2003},
abstract = {This paper describes a new protocol for the
establishment of multi-hop ad hoc networks based
on Bluetooth devices. The protocol proceeds in
three phases: Device discovery, partitioning of
the network into \emph{Bluetooth piconets} and
interconnection of the piconets into a
\emph{connected scatternet} and has the
following desirable properties. It 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 scatternet is
a connected mesh with multiple paths between any
pair of nodes, thus achieving
robustness. Differently from existing solutions,
no extra hardware is required to run the
protocol at each node, and there is no need for
a designated node to start the scatternet
formation process. Simulation results are
provided which evaluate the impact of Bluetooth
device discovery phase on the performance of the
protocol.}
}
@article{BasagniCS01,
author = {Basagni, S. and Chlamtac, I. and Syrotiuk, V. R.},
title = {Location Aware, Dependable Multicast for Mobile Ad
Hoc Networks},
journal = {Computer Networks},
volume = {36},
number = {5/6},
pages = {659--670},
month = {August},
year = 2001,
abstract = "This paper introduces {\em Dynamic Source
Multicast} (DSM), a new protocol for
multi-hop wireless (i.e., {\em ad hoc}\,)
networks for the {\em multicast} of a
data packet from a source node to a group
of mobile nodes in the network. The
protocol assumes that, through the use of
positioning system devices, each node
knows its own geographic location and the
current (global) time, and it is able to
efficiently spread these measures to all
other nodes. When a packet is to be
multicast, the source node first locally
computes a snapshot of the complete
network topology from the collected node
measures. A {\em Steiner} (i.e.,
multicast) tree for the addressed
multicast group is then computed {\em
locally} based on the snapshot, rather
than maintained in a distributed manner.
The resulting Steiner tree is then
optimally encoded by using its unique
{\em Prufer sequence} and is included in
the packet header as in, and extending
the length of the header by no more than,
the header of packets in source routing
(unicast) techniques. We show that all
the local computations are executed in
polynomial time. More specifically, the
time complexity of the local operation of
finding a Steiner tree, and the
encoding/decoding procedures of the
related Prufer sequence, is proven to be
$O(n^{2})$, where $n$ is the number of
nodes in the network. The protocol has
been simulated in ad hoc networks with 30
and 60 nodes and with different multicast
group sizes. We show that DSM delivers
packets to all the nodes in a destination
group in more than $90\%$ of the
cases. Furthermore, compared to flooding,
DSM achieves improvements of up to $50\%$
on multicast completion delay."
}
@article{Basagni01,
author = {Basagni, S.},
title = {Finding a Maximal Weighted Independent Set in
Wireless Networks},
journal = {Telecommunication Systems, Special Issue on Mobile
Computing and Wireless Networks (S.~Olariu and
I.~Stojmenovic, editors)},
volume = {18},
number = {1/3},
pages = {155--168},
month = {September},
year = {2001},
abstract = {This paper introduces MWIS, a distributed algorithm
for the efficient determination of a maximal
weighted independent set in the topology graph $G$
of a wireless network. Motivated by the observation
that the problem of partitioning wireless nodes into
clusters easily reduces to the problem of finding a
maximal weighted independent set of nodes, the
proposed algorithm is described by taking into
account two main characteristics 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 a topology dependent parameter of the
network (the stability number $\alpha(G)$ of the
network topology graph $G$), rather than by the
invariant number $n$ of the network nodes. Finally,
by using a well known results on the stability
number in random graphs, we show that the average
time complexity of the MWIS is logarithmic in $n$.}
}
@Article{ChlamtacGB00,
author = {Chlamtac, I. and Gibbs, S. and Basagni, S.},
title = {An Overview of the {U}niversity of {T}exas at {D}allas'
{C}enter for {A}dvanced {T}elecommunications {S}ystems
and {S}ervices ({CATSS})},
journal = {ACM/SIGMOBILE Mobile Computing and Communications Review},
year = {2000},
volume = {4},
number = {2},
pages = {63--69},
month = {April},
note = {Special Feature on Wireless Research Centers}
}
@article{BasagniBC99,
author = {Basagni, S. and Bruschi, D. and Chlamtac, I.},
title = {A Mobility Transparent Deterministic Broadcast
Mechanism for Ad Hoc Networks},
journal = {ACM/IEEE Transactions on Networking},
volume = {7},
number = {6},
pages = {799--807},
month = {December},
year = {1999},
abstract = {Broadcast (distributing a message from a source node
to all other nodes) is a fundamental problem in
distributed computing. Several solutions for solving
this problem in mobile wireless networks are
available. In current solutions mobility is dealt
with either by the use of randomized retransmissions
or, in case of deterministic delivery protocols, by
using conflict-free transmission schedules which
need to be periodically recomputed when topology
changes. Randomized solutions can be used only when
unbounded delays can be tolerated. Solutions that
require schedule recomputation become unstable when
the topology rate of change exceeds the schedule
recomputation rate. The deterministic broadcast
protocol we introduce in this paper overcome the
above limitations by using a novel, mobility
transparent schedule, thus providing a delivery
(time) guarantee without the need to recompute the
schedules when topology changes. We show that the
proposed protocol is simple and easy to implement,
and that it is optimal in networks in which
assumptions on the maximum number of the neighbors
of a node can be made.}
}
@article{BasagniB00,
author = {Basagni, S. and Bruschi, D.},
title = {A Logarithmic Lower Bound for Time-Spread
Multiple-Access ({TSMA}) Protocols},
journal = {ACM/Kluwer Wireless Networks},
volume = {6},
number = {2},
pages = {161--163},
month = {May},
year = {2000},
abstract = {Time-Spread Multiple-Access (TSMA) protocols are
scheduled access protocols for mobile multi-hop
radio networks that guarantee deterministic access
to the shared channel regardless of the possibility
of radio interference. In scheduled access methods,
time is considered to be slotted and time slots are
cyclically organized into frames. In general, the
shorter the frame, the more efficient the
protocol. An $\Omega(\log\log n)$ lower bound is
known on the minimum length of the frame of TSMA
protocols in networks with $n$ nodes. In this note
we improve that lower bound by characterizing the
multiple access to the radio channel as
acombinatorial problem. The proposed
characterization allows us to prove that no TSMA
protocols can successfully schedule the
transmissions of the nodes of a multi-hop radio
network in frames with less than $\log n$ time
slots.}
}
@article{Basagni99a,
author = {Basagni, S.},
title = {A Note on Causal Trees and Their Applications to {CCS}},
journal = {International Journal of Computer Mathematics},
volume = {71},
pages = {137--159},
month = {April},
year = {1999},
abstract = {Causal Trees are a variant of Milner's
Synchronization Trees which aims at reconciling two
antagonistic views of semantics for concurrent
systems: the interleaving models and the truly
concurrent ones. The original model of Causal Trees
provides us with an interleaving description of a
concurrent system which faithfully expresses {\em
causality} by enriching the action labels of a
synchronization tree. These enriched labels supply
indication of the {\em observable} causes of {\em
observable} actions. In this note we revise the
original model of Causal Trees, so that {\em every}
action label bears the causal indication, and not
only the observable actions. This permits to inherit
{\em all} the results of Milner's original theory in
a natural way.}
}
@article{BasagniBR97,
author = {Basagni, S. and Bruschi, D. and Ravasio, F.},
title = {On the Difficulty of Finding Paths of Length $k$ in
Digraphs},
journal = {Theoretical Informatics and Applications},
volume = {31},
number = {5},
pages = {429--435},
month = {September},
year = {1997},
abstract = {We characterize from the computational point of view
the problem of finding a path of length {\em exactly}
$k$ in a weighted directed graph $G$. We show that
the decision version of the problem is NP-complete
not only for the class of all weighted directed
graphs $G$, but also for the special case when $G$ is
acyclic and when we deal with undirected graphs.
However, when the lengths of the arcs of $G$ are
polynomially bounded the problem can be solved by
efficient algorithms (i.e., the problem is
pseudo-polynomial). In such a case we also devise
algorithms for solving the search version of the
problem. More precisely, we give a polynomial time
algorithm and a random fast parallel algorithm for
finding a path of length $k$ for each pair of
vertices of a weighted acyclic directed graph $G$
whose length function is polynomially bounded.
Finally, we show that other well known routing
problems have the same properties of the problem
under consideration.
All algorithms are designed exploiting the strong
link between graph theory and linear algebra.}
}