SLP Header

Analysis of Route Discovery in Mobile ad-hoc Network Routing using Information Systems

IJCSEC Front Page

Abstract
Mobile Ad hoc NET works (MANETs) are group of wireless mobile nodes that can dynamically form a network without any infrastructures wherein mobile nodes are highly co-operative. In MANETs, the movement of nodes is uncertain may cause links to break and low battery life of mobile nodes may cause nodes to fail. The connectivity of the entire network is uncertain and may not be known to any particular node. The work presented in this studies routing in cache-based ad hoc routing protocols, based on the Information Systems of Rough Set Theory (RST). The Rough Set Theory is a new mathematical tool to deals with vagueness and uncertainty and applied for cache based routing protocols in MANETs. The cache in mobile nodes looks similar to the information system of Rough Set Theory. The direct use of information systems in mobile nodes are used to assist routing of data packets and the decision systems are used to predict the next hop for a destination in MANETs.
Keywords:MANETs; Dynamic Source Routing (DSR); Rough Set Theory (RST);
I.Introduction
In the recent years Mobile Ad- hoc network (MANET) [4] has found applications especially to overcome the limitation of Bandwidth in wireless network. Wireless networks play an important role in both military and civilian systems. An ad hoc network is a collection of wireless mobile nodes forming a temporary network with no centralized entity and without aid of any established infrastructure. Messages are exchanged and relayed between mobile nodes. In fact, an ad hoc network has the capability of making communications possible even between two mobile nodes that are not in direct range with each other: packets to be exchanged between these two nodes are forwarded by intermediate nodes, using routing protocols. A number of routing protocols [1] and [2] has been proposed for MANETs. Most of the routing protocols in MANETs are either proactive, reactive or hybrid. Proactive protocols are table driven. In Proactive routing protocols, the mobile nodes are maintaining a table of routes to every destination for this reason they periodically exchange the control messages and hence there is no latency in discovering routes. In Reactive routing protocols routing information is acquired only when there is need for it. Each mobile node maintains a route cache of known routes. The needed routes are calculated on demand. Routes are discovered by some global search and hence there is latency in route discovery.

DYNAMIC SOURCE ROUTING PROTOCOL (DSR)DSR is a reactive routing protocol which is able to manage a MANET without using periodic table-update messages like table-driven routing protocols do stated in [3]. DSR was specifically designed for use in multi-hop wireless ad hoc networks. Ad-hoc protocol allows the network to be completely self-organizing and self-configuring which means that there is no need for an existing network infrastructure or administration. For restricting the bandwidth, the process to find a path is only executed when a path is required by a node (On-Demand-Routing). In DSR the sender (source, initiator) determines the whole path from the source to the destination node (Source-Routing) and deposits the addresses of the intermediate nodes of the route in the packets. DSR is beacon-less which means that there are no hello-messages used between the nodes to notify their neighbours about their presence.
ROUGH SET THEORY Rough set theory was proposed by Pawlak [5]. It is based on the rules of data mining and artificial intelligent algorithms. It is suitable to discover uncertain and incomplete implied knowledge. A data set is represented as a table, where each row represents an event or an object or an example or an entity or an element. Each column represents an attribute that can be measured for an element. This table is called an information system. The set of all elements is known as the universe. For example, if the information system describes a hospital, the elements may be patients; the attributes (condition attributes) may be Symptoms and tests; and the decisions (or decision attribute) may be diseases. In an information system, elements that have the same value for each attribute are indiscernible and are called elementary sets. Subsets of the universe with the same value of the decision attribute are called concepts. A positive element is an element of the universe that belongs to the concept. For each concept, the greatest union of elementary sets contained in the concept is called the lower approximation of the concept and the least union of elementary sets containing the concept is called the upper approximation of the concept. The set containing the elements from the upper approximation of the concept that are not members of the lower approximation is called the boundary region. The lower approximation of the concept is also known as the positive region. A set is said to be rough if the boundary region is non-empty. A set is said to be crisp if the boundary region is empty.

References:

  1. Barua, G.Andagarwal, M. (2002),”Caching of Routes in Ad hoc On Demand Distance Vector Routing for Mobile Ad hoc Networks”, Proceedings of 15th Int.Conference on Computer Communications(ICCC’02), Mumbai, India.
  2. Chun Hu, Johnson, “Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Networks”, Sixth Annual International Conference on Mobile Computing and Networking (MobiCom 2000), USA, August 2000.
  3. David Bjornson and David A. Maltz, “Dynamic Source Routing in Ad hoc Wireless Networks”, Mobile Computing, volume 353, Kluwer Academic Publishers, 1996.
  4. Donatas Sumyla, “Mobile Ad-hoc Networks (manets)” ,2006.
  5. Pawlak, Z. (1982), “Rough Set” , International Journal of Computer and Information Sciences.
  6. Pawlak,Z. (2002), “Rough Set Theory and its Application” , Journal of Telecommunications and Information Technology.
  7. Rajam, V.M.A., Maheswari, V.U., and Siromoney, A.(2008), “Temporal Information Systems and their Applications to Mobile Ad hoc Routing “, Ubiquitous Computing and Communications Journal,3(4):29-40.
  8. Rajam, V.M.A., Maheswari, V.U., and Siromoney, A.(2007), “Extension in Mobile Ad hoc Routing using Rough Set Theory”, Proceedings of 2006 International Conference on Hybrid Information Technology-Vol2, Korea.
  9. W.Ziarko. “Variable Precision Rough Set Model”, Journal of Computer and Systems Sciences, 46(1):39 – 59, 1993.
  10. W. Ziarko, “Set Approximation Quality Measures in the Variable Precision Rough Set Model”, in Proc. of 2nd Int. Conference on Hybrid Intelligent Systems, Santiago, Chile, 2002.
  11. K. Fall and K. Varadhan, “The NS Manual (Formerly NS Notes and Documentation)”, http://www.isi.edu/nsnam/ns/doc/index.html.