Home Progress Partners People Publications Software Deliverables News Contact Links [Private Area]

Biology-Inspired techniques for Self-Organization in dynamic Networks Progress - Ad-hoc Networks 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. Routing in Mobile Ad-Hoc Networks 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. Minimum Power Connectivity in Ad-Hoc Networks [MG03a,MG03b,MGD04a,MG04c,,,MG04a,MG05] Bibliography 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].