A Mobile-Directory Approach to Service Discovery in Wireless Ad Hoc Networks

We present the service directory placement algorithm (SDPA), a directory-placement scheme that leverages the performance of existing service discovery protocols over wireless ad hoc networks. SDPA promotes the deployment of a nomadic service directory, whose current location in the network varies according to the dynamics of service-discovery queries driven by the users´ applications and partial knowledge of the network´s topology. SDPA is based on a heuristic approach, whose performance is optimized by formulating the directory-placement problem as a semi-Markov decision process (SMDP) solved by the means of a reinforcement-learning technique known as Q-Learning. Performance evaluations obtained through computer simulations of networks with up to 45 hosts moving at pedestrian speeds reveal average bandwidth savings close to 50 percent over a default broadcast/multicast approach for service discovery once an efficient directory-placement policy is obtained.