An Algorithm for a Constraint Optimization Problem in Mobile Ad-hoc Networks

A mobile ad-hoc network is considered as a dynamic autonomous system composed of mobile devices interconnected by links without wire, without the use of a fixed infrastructure and without centralized administration. The absence of a centralized infrastructure forces each device to work in a peer to peer distributed environment, and to act as a router to relay communications, or to generate its own data. The management of the network thus is strongly distributed on all elements of the network. In this paper, we present a modelling of the mobile ad-hoc network (MANET) problem in form of a constraint satisfaction/optimization problem called CSPADhoc. Then, to minimize the consumption of batteries for devices, we describe an approach based on an adaptation of the A star algorithm to the MANET problem called (MANET-Astar). Finally, we present some experimental results using our approach