The Hopfield-Tank Neural Network for the Mobile Agent Planning Problem

The Hopfield-Tank Neural Network for the Mobile Agent Planning Problem

Cha-Hwa Lin (National Sun Yat-sen University, Taiwan) and Jin-Fu Wang (National Sun Yat-sen University, Taiwan)
DOI: 10.4018/978-1-61520-757-2.ch011
OnDemand PDF Download:
$37.50

Abstract

Mobile agent planning (MAP) is one of the most important techniques in the mobile computing paradigm to complete a given task in the most efficient manner. To tackle this challenging NP-hard problem, Hopfield-Tank neural network is modified to provide a dynamic approach which not only optimizes the cost of mobile agents in a spatio-temporal computing environment, but also satisfies the location-based constraints such as the starting and ending nodes of the routing sequence which must be the home site of the traveling mobile agent. Meanwhile, the energy function is reformulated into a Lyapunov function to guarantee the convergence to a stable state and the existence of valid solutions. Moreover, the objective function is designed to estimate the completion time of a valid solution and to predict the optimal routing path. This method can produce solutions rapidly that are very close to the minimum cost of the location-based and time-constrained distributed MAP problem.
Chapter Preview
Top

Introduction

In recent years, much research has been carried out into mobile agent in distributed computing. Mobile agent planning (MAP) is one of the most important techniques in the mobile computing paradigm to complete a given task in the most efficient manner (Baek, Yeo, Kim, & Yeom, 2001; Baek, Kim, & Yeom, 2002; Baek, Yeo, & Yeom, 2002; Baek & Yeom, 2003; Moizumi, 1998; MAL; Yang, Liu, Yang, & Wang, 2003). If it is possible to acquire the execution performance and the moving time of a mobile agent between sites of the entire network by long-term periodic detection, collection, or compilation statistics, a user can apply these data to plan the sequence the sites should be visited by the mobile agent, enabling which to efficiently complete a task and move among sites in minimum completion time. This scheduling activity is called the mobile agent planning problem. In general, to conduct the mobile agent planning problem, mobile agents must have knowledge of the network conditions so that they can adapt to the network environment and make the best use of the available resources such as the history of network conditions, which can facilitate their tasks in achieving the expected performances.

Moizumi (Moizumi, 1998) explored how mobile agents can efficiently spend their time traveling throughout the network completing distributed information retrieval. The planning problem was to decide in what sequence the sites should be visited in order to complete a task in minimum time, assuming the availability of the network statistics and the directory service. He named this mobile agent planning problem Traveling Agent Problem (TAP) because of its analogous to the traditional TSP problem. He treated the TAP problem as a traditional TSP problem and proved it is NP-complete. Moizumi used dynamic programming to solve the TAP problem in polynomial time by assuming that the network consisted of subnetworks where latencies between machines in the same subnetwork were constant while latencies between machines located in different subnetworks varied.

Baek et al. analyzed the characteristics of mobile agents, identified significant factors in MAP, and presented several useful planning methods. They tackled the number of agents and the execution time of the participating agent for retrieving information from distributed computing environment (Baek, Yeo, Kim, & Yeom, 2001). Using fewer agents could cause lower network traffic and consume less bandwidth, but badly scheduled agent itineraries could cause longer execution time as a result of higher routing cost. The number of agents created for a task could also influence the total routing cost. To reduce the overhead, they suggested two cost-effective mobile agent planning algorithms, BYKY1 and BYKY2. Consider the nodes that present correct information only for some time interval. If an agent is sent and arrives earlier than a specified update time to gather information, it may retrieve useless or corrupted information. In (Baek, Kim, & Yeom, 2002), they provided Time Planning method and extended versions of the BYKY1 and the BYKY2 algorithms to support the time constrains that reside on the node of the information repository. In (Baek, Yeo, & Yeom, 2002), they proposed a dynamic planning algorithm, named n-ary agent chaining which was based on static mobile agent planning to find a new itinerary taking into account dynamic traffic fluctuations on the network. Mobile agents could change their itinerary dynamically according to current network status using n-ary agent chaining algorithm. Finally in (Baek & Yeom, 2003), they presented an agent planning algorithm called d-agent for distributed information retrieval. This algorithm was based on the previous studies, and focused in particular on turn-around time.

Complete Chapter List

Search this Book:
Reset