Progress - Ad-hoc Networks
Mobile Ad Hoc Networks (MANETs) are communication networks in which all
nodes are mobile and communicate with each other via wireless connections.
There is no fixed infrastructure. All nodes are equal and there is no central
control or overview. There are no designated routers: all nodes can serve as
routers for each other, and data packets are forwarded from node to node in a
multi-hop fashion. A MANET can be useful in all those situations in which for
necessity or other practical or economical reasons no fixed network
infrastructure is available, such as military activities in enemy territory,
disaster recovery operations or big conference rooms. On the other hand, it is
quite clear that in the more technologically advanced societies in the near
future networking will be pervasive and highly heterogeneous: mobile ad hoc
networks, body area networks, GSM/GPRS networks, satellite networks, the wired
Internet ... will all be somehow interconnected, creating a sort of gigantic
hybrid mobile ad hoc network.
Routing, which is the task of directing data flows from sources to
destinations maximizing network performance, is at the very core of the
functioning of every network, and in particularly of MANETs. On the other hand,
routing is particularly challenging in MANETs. Due to the mobility of the
nodes, as well as the continual arrival and departure of nodes/users, the
topology of the network changes constantly. On the hand, it is necessary to
keep finding new paths to reach the newly arrived users, while on the other
hand, paths which were initially efficient can quickly become inefficient or
even infeasible. Moreover, the practical bandwidth of the network is limited
by the fact that the wireless medium is shared, such that appropriate complex
protocols must be used at the MAC layer (e.g., the popular IEEE 802.11a/b/g).
Another critical constraint for routing activities is given by the
on-board power/energy. A typical mobile device has limited on-board
power, which must be used wisely. Increasing the power used for radio
transmission/reception widen the radio range and so improves connectivity,
which is essential to guarantee routing and, more in general, network
functioning. Therefore, a good balance must be found between the local
connectivity and the amount of energy used to provide such level of
connectivity.
We have focused our research activities in MANETs precisely on these two core
related issues: adaptive routing and management of the node radio
power. So far, we have developed state-of-the-art algorithms for both these
two classes of problems. We are now trying to make the algorithms even better
performing and we are taking into account more and more realistic network
scenarios.
We have developed
AntHocNet a hybrid (reactive + proactive) routing algorithm
based on the framework of Ant Colony
Optimization
(ACO) [DDG,]. ACO reverse-engineers the pheromone
laying-following behavior of ants, which allows the colony as a whole to find
a shortest path between the nest and a food
source [CDF+01]. For wired networks, a number of
successful ACO routing algorithms exist (e.g. ABC [SHBR96] and
AntNet [DD98]). The main idea is to repeatedly sample paths
with small control packets, called ants, in order to adaptively
estimate the quality of each local routing choice. This results in a
collective and distributed learning of routing tables. ACO routing algorithms
exhibit some desirable properties for MANETs: they work in a distributed way,
are highly adaptive and robust, and provide automatic load balancing.
AntHocNet is an attempt to create an ACO routing algorithm which works
efficiently in MANETs, combining reactive path finding and repairing with
proactive path maintenance and improvement. AntHocNet also features the use
of local repair of path failures, multiple paths and
stochastic data load spreading.
AntHocNet is a hybrid routing algorithm, using ant agents to combine a
reactive path setup phase with proactive path improvement efforts based on
estimate bootstrapping techniques [SB98].
In an extensive set of simulation tests, we have compared AntHocNet to
AODV [PR99], a reactive algorithm which is an important reference in
this research area. We show that AntHocNet can outperform AODV for different
evaluation criteria in a wide range of different scenarios. AntHocNet is
also shown to scale well with respect to the number of nodes.
A full description of the algorithm can be found in the
papers [DDG05a,DDG05b,DDG05c,DDG04]
which are chronologically ordered.
[MG03a,MG03b,MGD04a,MG04c,,,MG04a,MG05]
- DDG
-
M. Dorigo, G. Di Caro, and L. M. Gambardella.
Ant algorithms for discrete optimization.
Artificial Life.
[Bibtex].
- CDF+01
-
S. Camazine, J.-L. Deneubourg, N. R. Franks, J. Sneyd, G. Theraulaz, and
E. Bonabeau.
Self-Organization in Biological Systems.
Princeton University Press, 2001.
[Bibtex].
- SHBR96
-
R. Schoonderwoerd, O. Holland, J. Bruten, and L. Rothkrantz.
Ant-based load balancing in telecommunications networks.
Adaptive Behavior, 5(2):169-207, 1996.
[Bibtex].
- DD98
-
G. Di Caro and M. Dorigo.
AntNet: Distributed stigmergetic control for communications
networks.
Journal of Artificial Intelligence Research (JAIR), 9:317-365,
1998.
[Bibtex].
- SB98
-
R. S. Sutton and A. G. Barto.
Reinforcement Learning: An Introduction.
Cambridge, MA: MIT Press, 1998.
[Bibtex].
- PR99
-
C. E. Perkins and E. M. Royer.
Ad-hoc on-demand distance vector routing.
In Proceedings of the Second IEEE Workshop on Mobile Computing
Systems and Applications, 1999.
[Bibtex].
- DDG05a
-
Frederick Ducatelle, Gianni Di Caro, and Luca Maria Gambardella.
Using ant agents to combine reactive and proactive strategies for
routing in mobile ad-hoc networks.
International Journal of Computational Intelligence and
Applications, Special Issue on Nature-Inspired Approaches to Networks
and Telecommunications, 5(2):169-184, June 2005.
To appear. Also Technical Report IDSIA 28-04.
[PDF],
[Bibtex].
- DDG05b
-
Gianni Di Caro, Frederick Ducatelle, and Luca Maria Gambardella.
AntHocNet: An adaptive nature-inspired algorithm for routing in
mobile ad hoc networks.
European Transactions on Telecommunications, Special Issue on
Self-organization in Mobile Networking, 16(5):443-455, 2005.
[PDF],
[Bibtex].
- DDG05c
-
Frederick Ducatelle, Gianni Di Caro, and Luca Maria Gambardella.
Ant agents for hybrid multipath routing in mobile ad hoc networks.
In In Proceedings of the Second Annual Conference on Wireless On
demand Network Systems and Services (WONS), St. Moritz, Switzerland, January
2005.
[PDF],
[Bibtex].
- DDG04
-
Gianni Di Caro, Frederick Ducatelle, and Luca Maria Gambardella.
Anthocnet: an ant-based hybrid routing algorithm for mobile ad hoc
networks.
In In Proceedings of PPSN VIII - Eight International Conference
on Parallel Problem Solving from Nature, number 3242 in Lecture Notes in
Computer Science, pages 461-470, Birmingham, UK, September 2004.
Springer-Verlag.
Best paper award.
[PDF],
[Bibtex].
- MG03a
-
Roberto Montemanni and Luca Maria Gambardella.
A new approach for the minimum power broadcast problem in wireless
networks, November 2003.
Submitted for publication.
[PDF],
[Bibtex].
- MG03b
-
Roberto Montemanni and Luca Maria Gambardella.
Minimizing power consumption while ensuring connectivity in wireless
networks: a new algorithm, December 2003.
Submitted for publication.
[PDF], [Bibtex].
- MGD04a
-
Roberto Montemanni, Luca Maria Gambardella, and Arindam Das.
The minimum power broadcast problem in wireless networks: a simulated
annealing approach, February 2004.
Submitted for publication.
[PDF],
[Bibtex].
- MG04c
-
R. Montemanni and L.M. Gambardella.
Power-aware distributed protocol for a connectivity problem in
wireless sensor networks, December 2004.
[PDF],
[Bibtex].
- MG04a
-
Roberto Montemanni and Luca Maria Gambardella.
Minimum power symmetric connectivity problem in wireless networks: a
new approach.
In Proceedings of the Sixth IFIP IEEE International Conference
on Mobile and Wireless Communication Networks (MWCN 2004), Paris, France,
October 2004.
[PDF],
[Bibtex].
- MG05
-
Roberto Montemanni and Luca Maria Gambardella.
The minimum power broadcast problem in wireless networks: a simulated
annealing approach.
In In Proceedings of the IEEE Wireless Communications and
Networking Conference (WCNC 2005), New Orleans, U.S.A., March 2005.
[PDF],
[Bibtex].
|