MANET Mining: Mining Association Rules
Ahmad Omar Jabas · InTech eBooks · 2011
IntroductionThe growing advances in mobile devices, processing power, display and storage capabilities, together with competitive market has enabled information technology to be more affordable and available to almost everybody around the world.Moreover, with the advent of wireless communications and mobile computing, another type of wireless communications, called Mobile Ad hoc NETworks (MANETs), came into existence.The operation of MANET does not depend on pre-existence infrastructure or base stations, since there is no central node in the network and nodes collaboratively share all the network activities.The simplicity of MANET deployment comes with a cost of complexity of the algorithms in different layers.In addition, the absence of the infrastructure induces new challenges to wireless networks in the fields of routing, security, power conservation, quality of service, and so on.For better perception of the new concepts in this chapter, a summary of the necessary background in Data Mining (DM) is given, and particularly more emphasis and in depth explanation is given on association rule mining technique, an area upon which the new concepts of this chapter revolves.DM or Knowledge Discovery in Databases (KDD) is defined as "The nontrivial extraction of implicit, previously unknown, and potentially useful information from data" (Frawley et al., 1992).DM is the process of finding hidden relationships in data sets and summarizing these patterns in models.These patterns can be utilized to understand the whole data sets.In simplified terms, DM is a technology that allows an applicant to discover knowledge, which is hidden in large data sets, by applying various algorithms (Hofmann, 2003).This chapter shows how DM approaches are applied to MANET, in that the traffic of MANET is mined in a simple way called "MANET Mining using Association Rule Techniques".MANET Mining enables the establishment of the fact that there are still some hidden relationships (patterns) amongst routing nodes, even though nodes are independent of each other.These relationships may be used to provide useful information to different MANET protocols in different layers.Precisely, MANET Mining, discovers hidden patterns (meta-data) in the third layer to be used as common tokens (keys) in the application layer in a bid to address one challenging security problem in MANET, namely, key distribution.This is the first time this approach has been used to solve key distribution problem in MANET.Interestingly, security in MANET has been paid a lot of attention over the past few years.One of the most challenging security issue in MANET is key management where there is no on-line access to trusted authorities.Key management is the central part of any secure communication, and is the weak point of system security and protocol design.Most 15 www.intechopen.comTheory and Applications of Ad Hoc Networks cryptographic systems rely on the underlining secure, robust, and efficient key management system.Key management scheme is the prerequisite for all security primitives and thus, it is the basis for secure MANETs.However, the performance of existing key distribution schemes developed so far is undesirable in the terms of efficiency and scalability.Besides, these schemes revolve around Third Trusted Party (TTP) and therefore, compromising this TTP means disclosing all the issued keys.Surprisingly, the fully distributed and self-organized key distribution schemes without TTP are still not robust to changing topology or intermittent links commonly encountered in MANETs (Chan, 2004).Section 2 gives an overview of association rule and its application to social networks.Section 3 explains how data mining approaches are applied in MANET and introduces a new distributed algorithm, MANET Mining.Section 4 provides a detailed explanation of applying Association Rule Techniques to MANET traffic.Section 5shows how Association Rule Mining Techniques are used on MANET traffic with a Step Threshold.Section 6 shows an important application of MANET Mining to key distribution.Section 7 concludes the chapter and draws some future research directions. Data Mining: An overview of association rule mining technique Association ruleThis section presents a methodology known as association rule mining, useful for discovering interesting relationships hidden in huge data sets.Association rules have received lots of attention in DM due to their many applications in marketing, advertising, inventory control, and many other areas (Simovici & Djeraba, 2008).Association Rules can be derived using supervised and unsupervised processes (Joe, 2009).Let A = {l 1 , l 2 , l 3 , l 4 , ..., l m } be a set of items.Let T be a set of transactions on a database.A transaction t is said to support an item l i ,ifl i is present in t.M o r e o v e r ,t is said to support a subset of items X ⊆ A,ift supports each item l in X (Pujari, 2001).X ⊆ A is said to have a Support s in T, denoted by s(X), if s percent of transactions in T support X. AsubsetX is said to be a Frequent Set (FS)inT with respect to σ (where σ is a user-specified minimum Support), if s(X) ≥ σ FS is called Maximal Frequent Set (MFS)ifnosuppersetofthissetisFS.The following are important properties of MFS:-Downward Closure: Any subset of FS is FS.-Upward Closure: Any supper set of an infrequent set is an infrequent set.Moreover, the set of all Maximal Frequent Sets (MFSs) is called maximum frequent set.For a given database, an association rule is an expression of the form:where X and Y are subsets of A. The intuitive meaning of such a rule is that a transaction of the database which contains X tends to contain Y.Some used measures of rule interestingness are:1. Confidence (τ): The association rule X =⇒ Y holds with confidence τ if τ% of transactions in T that supports X also supports Y.