Towards a Formal Validation of a Hybrid Multi-Agent Routing Protocol for Ad hoc Networks

Towards a Formal Validation of a Hybrid Multi-Agent Routing Protocol for Ad hoc Networks

Mohamed Amine Riahla, Ryma Abassi, Karim Tamine
DOI: 10.4018/IJBDCN.286703
Article PDF Download
Open access articles are freely available for download

Abstract

In the authors' previous papers, a new ant routing protocol for ad-hoc networks inspired from ant colony optimization was presented. They introduced a new approach that decreases both node energy consumption and routing overhead within the network. The validation of the routing protocol was based on series of simulations. The results show that the new algorithm provides a significant improvement compared to other protocols. After the algorithm is defined and published, they found it important to validate formally each one of its components in order to avoid any conflict, lack, or misbehaving situations. This process requires in a first step a formal specification. This is the main concern in this paper where the authors propose in a first part a formal specification using inference systems based on logical rules. A formal validation using these inference systems is proposed in a second step in order to prove the correctness, the soundness, the completeness, and the optimality of the proposition.
Article Preview
Top

Introduction

In a recent works (Riahla et al, 2014; Ait-Salem et al,2012), we proposed a hybrid method entailing proactive and reactive methods and based on the ant behavior (Dorigo et al, 2006; Dorigo et al, 1999; Di Caro et al, 1998; Singh et al,2020; Tseng et al, 2021; Okwu et al, 2021; A.C.J., Malar et al, 2020). The classic ant routing protocol (Correia et al, 2009; Correia et al, 2008; Bouazizi, 2006; Laxmi et al, 2006; Caro et al, 2005; Di Caro, 2004) use a broadcasting method that exponentially increases the routing overhead. In order to bypass this weakness, we introduced a new idea through an ant-based algorithm. The main idea consists of using Ant-Agents in order to find optimal routes in the network. These Agents are generated by each network node. When a new connection is planned to be established between nodes n and d without a corresponding entry in n’s routing table, this node n creates a new route request. Unlike other protocols, the node n set a local route request (rather than broadcasting it) available for Ant-Agents passing through it. It is, therefore, the role of these Ant-Agents that move within the network to 'intelligently' share this information in the network and to provide routes towards a destination node d. These Agents will disappear from the network whenever they accomplish their tasks or their lifetime is over. Each Ant-Agent will be created only if its predecessor is eliminated. Consequently, the number of Ant-Agents available in the network will be the same as the number of nodes. As a result, this approach will decrease the routing overhead.

The whole proposition performances were then evaluated using simulations. The obtained results showed a significantly improvement in terms of overhead, end-to-end delay and packets loss ratio.

Complete Article List

Search this Journal:
Reset
Volume 20: 1 Issue (2025): Forthcoming, Available for Pre-Order
Volume 19: 1 Issue (2024)
Volume 18: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 17: 2 Issues (2021)
Volume 16: 2 Issues (2020)
Volume 15: 2 Issues (2019)
Volume 14: 2 Issues (2018)
Volume 13: 2 Issues (2017)
Volume 12: 2 Issues (2016)
Volume 11: 2 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing