04-08-2012, 11:43 AM
AN ADAPTIVE ANT-BASED ROUTING ALGORITHM USED ROUTING
HISTORY IN DYNAMIC NETWORKS
3AN ADAPTIVE ANT-BASED.pdf (Size: 196.83 KB / Downloads: 39)
ABSTRACT
Recently, small and highly efficient personal digital assistants
such as cellular phone are developed, and mobile
communications are being indispensable in life.
The ad hoc network is observed in such circumstances.
However, conventional routing algorithms that keep the
optimum routing is difficult to perform flexible routing
in dynamic topology network, such as the ad hoc network.
This paper proposes Ants-Routing with routing
history(ARH) and Ants-Routing with routing history
and no return rule(ARHnr), that can perform a robust
routing by selecting stochastically the good route, and
learn quickly the route by using routing history. ARH
and ARHne adapt reinforcement learning to the routing
algorithm.
INTRODUCTION
In recent years, services provided on mobile communications
go on diversifying with according to an explosive
popularization of a cellular phone. In such
circumstances, the ad hoc network is observed as a
new medium of communication environment. The ad
hoc network is the network that is autonomously constructed
by mobile terminal(in the following, called
”node”), and it enables to communicate and share the
information between the nodes at any time, anywhere,
freely. The characteristics of the ad hoc network are
stated as follow.
THE PROBLEM OF CONVENTIONAL
ROUTING ALGORITHM
Major problems of conventional routing algorithm[1][2]
with reinforcement learning are necessity of a lot of
learning step and packets for learning. In particular,
when there are many packets, or when movement of
the node is intense, the route may not converge on a
good route because learning speed can not follow environmental
change.
Moreover, the problem peculiar to stochastically
routing algorithm such as Ants-Routing and AntNet
is routing-lock[3]. Routing-lock is a phenomenon in
which a route is fixed because a routing probability
converge in the vicinity of one during the progress of
learning. When change of topology takes place and it
becomes impossible to use the routes according to this
phenomenon, a lot of time is required to discover the
new route. In addition, although a new efficient route
is discovered, selecting the conventional route will be
continued without the ability of discovering a new one.
Updating process
Each node stores its own ID and sum of transmission
time, message processing time, and other information
as routing history in a message packet, and send to next
hop(Fig. 1). The size of queue to store routing history
is fixed. If the size of stored routing history is larger
than the size of queue, the oldest history is removed,
and new history is stored. It is because reliability of the
oldest history is low. A node that accepts a message
packet is trained by backward exploration.
CONCLUSION
In this study, new stochastic routing algorithms named
ARH and ARHnr for dynamic topology network like
the ad hoc network are proposed. In ARH, routing
history achieves quickly learning and efficient route.
Moreover, in ARHnr, no return rule achieves efficiently
search at the early phase of training.
In particular, ARHnr can quickly solve routing-lock
and it is excellent in discovering a new route in dynamic
environment. Future reserch will be addressed to make
a comparison with the other routing algorithm such as
DSR and AODV proposed in IETF.