Swarm and Fuzzy based Ant Colony Optimization (ACO) Routing and Cache Framework for MANET

Swarm and Fuzzy based Ant Colony Optimization (ACO) Routing and Cache Framework for MANET

Mr. Gajendiran G,

II-ME- Computer and Communication Engineering,

Mahendra Engineering College, Namakkal 637 503, Tamil Nadu, India,

Abstract – In mobile ad hoc network, when the query directory increases, the hit ratio and total delay increases including traffic overhead. To overcome this issue and also to offer a combined solution for routing, cache sharing and consistency, in this project, we propose a swarm and fuzzy based co-operative cache management framework for MANET. In this technique, reservation node selection is performed using fuzzy logic technique and the data forwarding between the reservation node and the requesting node is performed by swarm based routing ant colony optimization (ACO). This process of generation of new routes involves two ant agent namely forward ant (FANT) and backward ant (BANT). The node receives the data, the caching decision is made based on the parameters such as information presence index and content drop time. The consistency maintenance is achieved using flexible Push and pull algorithm, which satisfies user-specified consistency requirements at minimum cost by associating cache-copy with a time-out value.

Index Terms MANET, ACO, Fuzzy Logic, Caching Decision, Caching Maintenance.

1 INTRODUCTION

1. MANET

   Mobile ad hoc network (MANET) is a multihop wireless network with mobile nodes that can move independently. MANET has no infrastructure in the sense that it does not require any access points or base stations for transmission [1]. Nodes can communicate with each other directly or through intermediates [2]. As the nodes move arbitrarily in the network, the network topology can change frequently. One node will communicate with the other node directly within sufficient radio propagation and indirectly through multihop routing with all other nodes. To help such kind of communication, many routing algorithms already have been developed. In MANET, the nodes are randomly present and they are supposed to develop and maintain the entire network automatically; hence, the routing algorithms are crucial. Due to active topology and limited resources, developing a dynamic routing protocol that can efficiently find arouting path with low control overhead is very important in MANETs [3-5]. Most of the devices and systems in MANET are designed in a performance-oriented manner, not considering the energy efficiency [6].

2. Significance of node and link lifetime prediction for route recovery process

   In general, the network depends on the node assistance for providing the packet routing. Routing is the basic operation in ad-hoc networks. The routing algorithm should be robust, adaptive, and in a self-organized way. Nodes cannot forward the data packets to the receiver node when the prediction error is less than a pre-configured threshold value. Prediction is used to make the decision for transmission Re-routing in a mobile ad-hoc network is costly and would result inflooding the network due to the lack of infrastructure.

3. Salient feature of Ant Colony Optimization (ACO)

   Swarm intelligence (SI), artificial intelligence techniques are nowadays involved in various applications. Several studies make use of genetic algorithm (GA)-based techniques to solve network problems. Ant Colony Optimization (ACO) is a paradigm for designing meta heuristic algorithms for combinatorial optimization problems. Technique for solving problems which can be expressed as finding good paths through graphs. Each ant tries to find a route between its nest and a food source. The behavior of each ant in nature is wander randomly at first, laying down a pheromone trail. If food is found, return to the nest laying down a pheromone trail. If pheromone is found, with some increased probability follow the pheromone trail. Once back at the nest, go out again in search of food However, pheromones evaporate over time, such that unless they are reinforced by more ants, the pheromones will disappear.

4. Cache Management

   One of the key issues in mobile ad-hoc networks (MANETs) is cache management, which improves the transmission capacity of the network. Replacement – this algorithm is responsible for evicting less important or expired data, with time to live (TTL) equal to zero, when the node cache is full and a new data is to be fetched on a request from client. Consistency – this algorithm guarantees that all the copies of a data are identical to the original one on the server. Prefetching – this mechanism fetches the most important data items (that have high probability to be requested in the near future) into the caching node and stores them in the cache memory for responding to the future requests and queries.

   1. RELATED WORKS

      Xin Ming Zhang et al. [5] have proposed an estimated distance (EstD)-based routing protocol (EDRP) to guide a route discovery. This protocol can restrict the propagation range of route request and reduce the routing

      3.1.3 Distance from the node (D)

      The distance (dij)among the sender node (Ni) and receiver node (Nj) can be estimated based on free space propagation model. It considers the wavelength utilized for transmission and reception.

      2

      overhead.

      P = P

      *

      * *

      (3)

      The change regularity of the received signal strength is exploited to estimate the geometrical distance between a

      rx tx

      4d

      ij

      pair of nodes, which is called the estimated geometrical distance (EGD). An estimated topological distance (ETD) is a topology-based EstD that can mitigate the effect of inaccurate EGD.

      Finally, this route lifetime prediction algorithm is implemented in the new protocol environment, which is based on the dynamic source routing (DSR) protocol. This new protocol outperforms the existing protocols like the lifetime prediction routing (LPR) and DSR protocols in terms of throughput, routing failure, routing overhead, packet loss ratio, and packet delivery ratio.

      .Devi Manickavelu have proposed a particle swarm optimization (PSO)-based lifetime prediction algorithm for route recovery in MANET has been proposed. This technique predicts the lifetime of link and node in the available bandwidth based on the parameters like relative mobility of nodes and energy drain rate, etc. Using predictions, the parameters are fuzzified and fuzzy rules have been formed to decide on the node status. This information is made to exchange among all the nodes. Thus, the status of the every node is verified before data transmission. Even for a weak node, the performance of a route recovery mechanism is made in such a way that corresponding routes are diverted to the strong nodes.

   2. WORK DESCRIPTION

1. Expected Time to Stay (ET)

   The expected time to stay is estimated based on the node mobility. The mobility between the two nodes can be estimated from the ratio of RSS obtained among the two consecutive packet transmissions from a neighbor node. Thus the mobility metric Moj (i) of the node j with respect to i is computed using the following formula.

   RSS new

   Where Prx = reception power Ptx = transmission power

   = wavelength

   = transmitter gain

2. Swarm and Fuzzy Based Co-operative Cache Management Framework

3.2.1 Fuzzy Based Reservation Node Selection

When the nodes are deployed in the network, it is examined whether it acts as caching node (CN) or reservation node (RN). The unction of reservation node is to store the queries presented by the requesting nodes. Caching node stores the response message to the queries. The reservation and cache node detection is performed using fuzzy logic. The node parameters such as expected time to stay, battery life, bandwidth, and distance from the node and link quality are considered as inputs parameters.

Fuzzification

This involves fuzzification of input variables such asexpected time to stay (ET), battery life (BL), bandwidth (AB), distance from the node (D) and link quality (LQ)(Estimated in sections 3.2.1-3.2.5) and these inputs are given a degree to appropriate fuzzy sets. The crisp inputs are combination of ET, BL, AB, D, and LQ. We take two possibilities, high and low for ET, BL, AB, D, and LQ.

Moj(i) = 10 log10

i j

RSS

RSS

old i j

(1)

When the estimated mobility value is more, the ET is less and vice versa.

1. Battery Life (BL)

   It is defined as the ratio of power received at the node (Prx) to the power transmitted (Ptx) by the neighbor node.

2. Bandwidth (AB)

The available bandwidth is computed using Eq (2) AB = (1 – Qd/Qt) Qt / tf (2)

Where Qd = number of allocation slots in one frame Qt = total slots in the sub-frame

tf = duration of the frame

= number of bits transmitted in downlink slots

Figure 1 Membership function of Expected Staying Time

Figure 2 Membership function of Battery Lifetime

Figure 3 Membership function of Available Bandwidth

1. Swarm Based Routing Technique

   In our approach, the data forwarding between the source node and the reservation node (RN) is performed by swarm based routing based on ant colony optimization (ACO) This process of generation of new routes involves two ant agent namely forward ant (FANT) and backward ant (BANT).

   Let S be the requesting node (Source) Let Ni be the intermediate node

   The steps involved in this algorithm are as follows.

   1. Each node Ni investigates its routing table to determine whether the valid routing information exists for RN.

      If valid data exists Then

      Node chooses the RN with the minimum number of hops to transmit the data.

      Else

      Performs swarm based routing.

      End if

      Figure 4 Membership function of Distance

   2. Initially S launches FANT. FANT visits each Ni whose mobility is based on probabilistic decision rule (shown in Eq.7).

      [a(N , S ) .[b(N , S )]

      i i

      Pr (Ni, S) = [a(Ni , S )] .[b(Ni , S )]

      NiNR

      0, otherwise

      (7)

      , if r RT (Ni )

      Where

      a(Ni , S) represent pheromone value

      b (Ni, So) represent the heuristic value

      Figure 5 Membership function of Link Quality

      Figure 6 Membership function of Combined Score

      Defuzzification

      The technique by which a crisp values is extracted from a fuzzy set as a representation value is referred to as defuzzification. The centroid of area scheme is taken into consideration for defuzzification during fuzzy decision making process.

      Fuzzy_cost =

      related to bandwidth.

      NR represents the receiver node.

      RT (Ni) represents the routing table for Ni.

      and are the parameters that control the relative weight of the pheromone and heuristic value respectively.

      [ allrules fi * (fi)]/[ allrules ( fi ) ] (6)

      Where fuzzy_cost is used to specify the degree of decision making, fi is the fuzzy all rules, and variable and

      ( fi ) is its membership function.

      Fuzzy Input Values

      Fuzzy Input Values

      Expected Staying Time of the Node (ET)

      Battery Lifetime (BL)

      Distance (D)

      Available Bandwidth (AB)

      End if

      1. The BANT then takes the same path as that of its corresponding forward ant, but in the opposite direction. It updates the pheromone table with the routing information of the respective Ni.

      2. Once S receives the BANT, it collects the routing information about all Ni along each path from its updated pheromone table.

         Fuzzification

         Fuzzification

      3. From the collected information, S chooses the route with minimum hop as primary path for data transmission to RN. The next level of minimum hop values from the collected information helps in deciding the backup path.

         Defuzzification

         Knowledge Base

         Knowledge Base

         InitialMembershi pFunction

2. Caching Decisions

After the node receives the data, the caching decision is made using the two observations such as overhear queries and information such as nodes distance on the wireless channel. Based on the observed information, the node estimates the information presence index (i) (Case 1).

Fuzzy Rule Base

Fuzzy Rule Base

Case – 1

Ni estimates i using the following equation. i (Ni, k) = min {1, Ci1 (Ni, k) + Ci2 (Ni, k)}

(9)

Where k = time step

Output Combined Score (CS)

Output Combined Score (CS)

Ci1 (Ni, k) = Source counter

Ci1 (Ni, k) reveals the existence of new copies of information ( ) deposited by the node to RN within the

transmission range at k. This counter value is updated each

Figure 7 Fuzzy Interference System

time the node acts as S.

1

Ci1 (Ni, k) = Ci1 (Ni, k) +

H 1

(10)

Where H1 = number of hops covered by the new copies of data

Ci2 (Ni, k) = movement counter

Ci2 reveals the existence of transmitted between

two nodes within transmission range and overheard by Ni at k.

Ci2 (Ni, k) = Ci2 (Ni, k) +

1 1

H 1 + H 2

(11)

Table 1 Fuzzy Rule for the Determining Output

1. Each FANT deposits a quantity of pheromone ( u

   in the visiting Ni as per the following equation

   (r) )

   H2 be the number of hops covered by the existing copies of data

   i (Ni, k) is in the range (0, 1).

   0 the presence of was not sensed by Ni during k 1 If is cached one hop away from Ni

   Case 2

   s

   s

   u (r) = 1/ X u (r)

   (8)

   When Ni contains large sized cache, it computes

   Where X u (r) represents the total number of N visited by

   cache drop time ( Tdi (Ni , k) ) at k for the data i.

   s i T

   (N , k) = (1- (N , k)) T

   (12)

   FANT during its tour at iteration r and u = 1, 2.n

   di i

   i i dmax

2. Using rule described in step 2, FANT moves through Ni

and verifies the existence of RN ID in its routing table. If RN ID exists,

Then

Where Tdmax = maximum cache drop time

The above estimated drop time can be used for all of data i

received during (k+1).

BANT is generated in respective Ni and the information collected by FANT is

Case 3

When Ni contains a small sized cache, it performs

transferred to BANT. cache content replacement technique. This allows balanced

distribution of data over the network such that the content remains close to requesting node. This technique allows removing chunks from the memory upon arrival of new content.

^

4. SIMULATION RESULTS

1. Simulation Model and Parameters

   The Network Simulator (NS2) [21], is used to simulate the proposed architecture. In the simulation, 40 mobile nodes

   ^

   Tdi (Ni , k) (1

   (i (Ni , k)

   ^

   max i {i (Ni , k}

   )Tp max

   (13)

   move in a 1000 meter x 1000 meter region for 50 seconds of simulation time. All nodes have the same transmission range of 250 meters. The simulated traffic is Constant Bit Rate

   Where Tpmax = maximum cache stability time

   After Tpmax, the chunk is discarded to prevent stored information from becoming out-dated and node movement resulting to discrepancies with respect to previous

   (CBR).

   information i

   ratings.

   3.2.4 Consistency Maintenance

   A flexible Push and pull algorithm is used to achieve the consistency maintenance which satisfies user-specified consistency requirements at minimum cost by associating cache-copy with a time-out value (u).

   This technique involves two actions:

   Push: S informs caching nodes about cache information.

   Pull: Caching node fetches cache information from S.

   The combined push pull action on the caching and source node is described as.

   1. When a query is received, the following condition is verified If u > 0

      Then

      The received query is offered with the cached copy.

2. Results

   1. Based on Speed

      In our first experiment we vary the mobile speed as 5,10,15,20 and 25m/s.

      Else

      SFCCM

      CODISC

      SFCCM

      CODISC

      Speed Vs Delay

      20

      15

      10

      5

      0

      5 10 15 20 25

      Speed(m/s)

      Speed Vs Delay

      20

      15

      10

      5

      0

      5 10 15 20 25

      Speed(m/s)

      Delay(Sec)

      Delay(Sec)

      u is decreased to zero.

      A renewal message is transmitted to perform

      renewal of u from S and cache copy is updated. The received query is offered with the

      cached copy. End if

      1. When S is ready to be updated, an invalid message is transmitted to each caching node with positive u value.

         Figure 8 Speed Vs Delay

         Speed Vs DeliveryRatio

         S {u}{invalid _mes} CN

         1.5

      2. If S receives an acknowledgement message (ACK_mes) for each invalid message, the source data is updated.

         S ACK_mes CN

      3. Following the reception of renewal message from CN

      If source data has been updated Then

      Pkts

      Pkts

      An update message has been transmitted to

      1

      0.5

      0

      SFCCM

      CODISC

      SFCCM

      CODISC

      DeliveryRatio

      DeliveryRatio

      5 10 15 20 25

      Speed(m/s)

      Speed Vs Drop

      5000

      4000

      3000

      2000

      1000

      0

      5 10 15 20 25

      Speed(m/s)

      Speed Vs Drop

      5000

      4000

      3000

      2000

      1000

      0

      5 10 15 20 25

      Speed(m/s)

      Figure 9 Speed Vs Delivery Ratio

      CN

      End if

      5. If there is no pending update Then

      Timeout u is allowed and data is updated to

      CN

      End if

      SFCCM

      CODISC

      SFCCM

      CODISC

      Figure 10 Speed Vs Drop

      Speed Vs Throughput

      Speed Vs Throughput

      5000

      4000

      3000

      2000

      1000

      0

      SFCCM

      CODISC

      SFCCM

      CODISC

      5000

      4000

      3000

      2000

      1000

      0

      SFCCM

      CODISC

      SFCCM

      CODISC

      5 10 15 20 25

      Speed(m/s)

      5 10 15 20 25

      Speed(m/s)

      Throughput

      Throughput

      Pkts

      Pkts

      Figure 11 Speed Vs Throughput

      Figure 8 shows the delay of SFCCM and CODISC techniques for different speed scenario. We can conclude that the delay of our proposed SFCCM approach has 92% of less than CODISC approach.

      Figure 9 shows the delivery ratio of SFCCM and CODISC techniques for different speed scenario. We can conclude that the delivery ratio of our proposed SFCCM approach has 42% of higher than CODISC approach.

      Figure 10 shows the drop of SFCCM and CODISC techniques for different speed scenario. We can conclude that the drop of our proposed SFCCM approach has 96% of less than CODISC approach.

      Figure 11 shows the throughput of SFCCM and CODISC techniques for different speed scenario. We can conclude that the throughput of our proposed SFCCM approach has 61% of higher than CODISC approach.

   2. Based on Cache Size

   In our second experiment we vary the cache size as 500, 750, 1000, 1250 and 1500.

   PacketSize Vs Delay

   Delay(Sec)

   Delay(Sec)

   15

   SFCCM

   CODISC

   SFCCM

   CODISC

   10

   5

   0

   500 750 1000 1250 1500

   PSize

   Figure 12 Psize Vs Delay

   PacketSize Vs DeliveyRatio

   DeliveryRatio

   DeliveryRatio

   1.5

   SFCCM

   CODISC

   SFCCM

   CODISC

   1

   0.5

   0

   500 750 1000 1250 1500

   PSize

   Figure 13 Psize Vs Delivery Ratio

   PacketSize Vs Drop

   3000

   2000

   1000

   0

   500 750 1000 1250 1500

   PSize

   PacketSize Vs Drop

   300

   2000

   1000

   0

   500 750 1000 1250 1500

   PSize

   Figure 14 Psize Vs Drop

   PacketSize Vs Throughput

   PacketSize Vs Throughput

   4000

   3000

   2000

   1000

   0

   SFCCM

   CODISC

   4000

   3000

   2000

   1000

   0

   SFCCM

   CODISC

   500 750 1000 1250 1500

   PSize

   500 750 1000 1250 1500

   PSize

   Throughput

   Throughput

   Figure 15 Psize Vs Throughput

   Figure 12 shows the delay of SFCCM and CODISC techniques for different packet size scenario. We can conclude that the delay of our proposed SFCCM approach has 95% of less than CODISC approach.

   Figure 13 shows the delivery ratio of SFCCM and CODISC techniques for different packet size scenario. We can conclude that the delivery ratio of our proposed SFCCM approach has 37% of higher than CODISC approach.

   Figure 14 shows the drop of SFCCM and CODISC techniques for different packet size scenario. We can conclude that the drop of our proposed SFCCM approach has 97% of less than CODISC approach.

   Figure 15 shows the throughput of SFCCM and CODISC techniques for different packet size scenario. We can conclude that the throughput of our proposed SFCCM approach has 66% of higher than CODISC approach.

   CONCLUSIONS

   In this paper we have presented a reservation node selection is performed using fuzzy logic technique and the data forwarding between the reservation node and the requesting node is performed by swarm based routing. The consistency maintenance is achieved using flexible Push and pull algorithm which satisfies user-specified consistency requirements at minimum cost by associating cache-copy with a time-out value.

   REFERENCES:

   1. Wensheng Zhang, Liangzhong Yin, and Guohong Cao,Zhang, Wensheng, Liangzhong Yin, and Guohong Cao. "Secure cooperative cache based data access in ad hoc networks." NSF International Workshop on Theoretical and Algorithmic Aspects of Wireless Ad Hoc, Sensor, and Peer-to-Peer Networks, 2004.

   2. Liangzhong Yin and Guohong Cao, Supporting Cooperative Caching in Ad Hoc Networks,Mobile Computing, IEEE Transactions on 5.1,2006, pp.77-89.

   3. Hassan Artail and Salem Saab, A Distributed System for Consuming Web Services and Caching Their Responses in MANETs,IEEE Transactions On Services Computing, Vol. 2, No. 1, January-March 2009, pp. 17-33.

   4. Yu Huang, Jiannong Cao, Beihong Jin, Xianping Tao, Jian Lu and Yulin Feng, Flexible Cache Consistency Maintenance over Wireless Ad Hoc Networks, IEEE Transactions On Parallel And Distributed Systems, Vol.21, No.8, August 2010.

   5. Hassan Artail, Haidar Safa, Khaleel Mershad, Zahy Abou-Atme and Nabeel Sulieman, COACS: A Cooperative and Adaptive Caching System for MANETs,IEEE Transactions on Mobile Computing, Vol. 7, No. 8, August 2008.

   6. Chandrani Chakravorty and Dr. Usha J, Cache Management Issues in Mobile Computing Environment,International Journal of Mobile Network Communications & Telematics (IJMNCT) Vol.2, No.1, February 2012.

   7. Gyorgy Dan, "Cache-to-cache: Could ISPs cooperate to decrease peer- to-peer content distribution costs?" Parallel and Distributed Systems, IEEE Transactions on 22.9 (2011): 1469-1482.

   8. Marco Fiore, Claudio Casettiand Carla-Fabiana Chiasserini, Caching Strategies Based on Information Density Estimation in Wireless Ad Hoc Networks,IEEE Transactions On Vehicular Technology, Vol. 60, No. 5, June 2011.

   9. Ch. Phaneendra, K.Srimathi, T.P.Shekhar and V.Ravi Kumar, Caching Approach Foundation on Information Density Evaluation in Wireless Ad Hoc Networks,International Journal of Advanced Research in Computer Science and Software Engineering,Volume 2, Issue 5, May 2012.

   10. C.Srinivas and Samreen Khan, Data Caching Placement based on information density in wireless ad hoc network,International Journal of Engineering Research and Applications,Vol. 2, Issue 4, July- August 2012, pp.120-125.