Artificial Bee Colony Based Energy Efficient Routing Protocols in MANET: A Survey

Artificial Bee Colony Based Energy Efficient Routing Protocols in MANET: A Survey

1.Akhil Dubey, 2.Deepak Meena

1,2. .M.Tech. Scholars, Dept. of Computer Science & Engg.

IEC-College of Engineering & Technology Greater Noida, U.P., INDIA

3. Rajnesh Singh

3. Associate Professor, Dept. of Computer Science & Engg. IEC-College of Engineering & Technology

Greater Noida, U.P., INDIA

Abstract–Now a day in computer science there are many exciting research being done all around of globe. In that routing protocols in MANET have vital place and more challenges for the scholars due to its limited bandwidth, power constraint and dynamic nature. Over the last ten or eleven years there are many efforts have been done by the researcher to make the energy efficient routing protocols either by doing modification in routing protocols or by developing new routing protocols like minimum energy routing protocol. But due to these modifications, network overhead occurs and it causes of the overall network degradation. So to heal this problem some researchers introduce swarm intelligence based algorithms for energy optimization in MANET. Basically swarm intelligence is a branch of entomology which deals with the study of the behavior and interaction of social insects like ants, bees, fire flies etc. The swarm intelligence based energy efficient routing protocols are based on the behavior of foraging insects. This collective behavior of insects helps to find the shortest path from hive to food sources. So in this paper we give the comprehensive study of energy efficient routing based on artificial bee colony optimization. We describe the behavior of the bees and artificial bee colony algorithm. Then we discuss bio inspired or predictive routing for MANETs.

KeywordsMANET, Energy Efficient Routing, Swarm Intelligence, BCO, Bio Inspired Routing, PEEBR

1. INTRODUCTION

   Mobile ad hoc networks [1] are a combination of different asymmetric wireless devices which are infrastructure less and create anywhere anytime. In this network devices are small and more powerful and make network as a fastest growing network. The devices of in this network are able to detect the other devices and create set up and provide the facility of communication, sharing data and perform other necessary actions. Due to ad hoc nature and mobility topology may rapidly change and in changing routing environment it more challenging to provide energy efficient routing. In MANET power resource and limited battery resources is the main constrain. Many scholars present many routing protocols that are classified as energy efficient protocols that are define in [2]. There are three main algorithms define in [3] for efficient routing which is given below-

   1. Energy Efficient Routing

      Each node which decides to forward packets that are wanted to send packet for a certain destination to a neighbor based on the minimum transmission power between this sending node and its neighbors.

   2. Cost Efficient Routing

      Every node chooses its neighbors to send the packet to the destination of the minimum cost. The cost function is defined as the sum of the cost of sending node to its neighbor plus the estimated cost of the route from its neighbor to the sender destination node.

   3. Power-Cost Efficient Routing

   It is the combinations of both above routing algorithms.

   According to this sender node use both routing techniques.

   So in this paper we present the five sections. In second section we present the swarm intelligence approach, in third we give the bee colony optimization, in forth we present ABCO based different energy efficient routing and then conclude our paper in last section.

2. THE SWARM INTELLIGENCE APPROACH

   In 1999 Bonabeau et. Al defines the Swarm intelligence is as a quality of artificial and natural systems involving multiple individuals interacting with each other and provides the environment to solve complex problems showing a collective intelligent behavior. In the swarm intelligence is the study of systems like colonies of ants and termites, schools of fish, flocks of birds, herds of land animals and Some human artifacts also fall into the domain of swarm intelligence. The properties of swarm intelligence are that it composed of many individuals behavior. In it the animals are either all identical or belong to a few other typologies. The acts on each other among the animals are based on simple behavioral rules that make use of local information exchanged directly or via the environment. The overall behavior of the system results from the interactions of individuals with each other and with their environment [4].

   The main advantages of swarm intelligence are first flexibility that means the group can quickly suitable to a changing environment. Second is robustness that means even

   when one or more insects fails, the group can still perform its tasks. Third is self organization that means the group needs relatively little supervision or top down control. These properties make swarm intelligence a successful design paradigm. There are mainly two swarming intelligence techniques first is ant colony optimization and second is bee colony optimization. In this paper we present artificial bee colony based optimization [5].

3. ARTIFICIAL BEE COLONY OPTIMIZATION

   Like the ant colony optimization Artificial Bee Colony Optimization (BCO) model is a new and basic general purpose Swarm Intelligence (SI) optimization technique which is based on efficient labor employment and efficient energy consumption and called as multi-agent distributed model. In the Ant Colony Optimization (ACO) model we adopted mainly one natural insect behavior which is the food searching. The main aims to discover the shortest path between the home and the food source place but from BCO model we adopted mainly two natural behaviors which is the social bees life like the mating process behavior and the foraging process behavior [6].

   In the bee colony model there are three types of bees Female Queen Bee, Male drone bees, Worker bees [7].

   1. Queen Bee

      The main work of queen bee is to laying egg which is used to develop a new colony because there is only one queen bee in the hive.

   2. Male Drone Bees

      In the hive there are two types of male drone bees first is Food Packers Bees the work of food packer bees is to serve the queen help it in laying the eggs. The second is Nurses Group Bees which is responsible for feeding the queen and the babies.

   3. Worker Bees

      . In the worker bees group there are three types of bees, first is Scouts Bees, main work is to discover the food. Second is Forager Bees, main work is to check the quality of food. Third is Primary Worker Bees, main work is to collect the food from the sources.

      The bee colony algorithm is based on worker types bees. In the bee colony algorithms scoot bees are responsible for the discovering the all possible food sources. After finding that they doing waggle dance to guide the forager bee and give them food direction in the sun defined angle. The forager bees are responsible for checking the quality of the food and also guide the worker bees to the food sources from the hive. The worker bees are responsible for the taking the nectar from source by following onlooker wangle dance.

      Now we see the flow graph diagram of artificial bee colony optimization is given below-[9]

      Start

      Initialize the Bee Population

      Identify the Food Sources

      Performing Scout Bee Scenario/p>

      Is Stopping N Criteria met?

      Y

      Performing Forager Bee Scenario

      Is Stopping N Criteria

      met?

      Y

      Select Food Source with Best Food Quality

      Stop

      Fig 1. Flowchart for Basic BCO Steps

      The algorithm for artificial bee colony optimization is given below-[8]

      Step-1 start the algorithm

      Step-2 first of all initializes the population of the worker bees

      Step-3 then in artificial bee colony optimization performing path exploration like scout bees discover the path

      Step-4 after finding the different paths by arranges the paths in decreasing order according to its distance.

      Step-5 now checks the path quality like work of forager bees and rearranges the path according to the nectar quality

      Step-6 after deciding the forager Path by performing path Exploration select the final path like forager bees

      Step-7 finalizes and stops the algorithm

      In the bee colony optimization there are some mathematical phenomenon define in [7]. Distance measurement is the first which is generally used for evaluating similarities between patterns.

      The simulation of ABC is done by producing a position randomly and replacing it with the abandoned one. So the limit of the abandoned source is zi and j {I, 2… D}, then the scout discovers a new food source to be replaced with zi, this operation can be defined as

      Zi i= Zimin + rand (O, l)( Zi max Zimin) (7)

      After each candidate source position Vi,j is produced and then evaluated by the artificial bee, its performance is compared with that of its old one.

      So in this section we present the bee colony optimization now we see the artificial bee colony based energy efficient routing techniques in next section.

      =1

      , =

      =1

      2

4. ENERGY EFFICIENT ROUTING BASED ON

   ARTIFICIAL BEE COLONY OPTIMIZATION

   (1)

   Where Given N objects, each object is allocated to one of K clusters, J(w,z) is the Euclidean distance and Xi (i = 1, … , N) is the location of the ith pattern and Zj G= 1, … , K) is the center of the Jth cluster, can be calculated as

   In the area of routing protocol in MANET there are many protocols are developed time to time by the authors. In swarm intelligence based routing scholars pay more attention on the ant colony optimization. But in this section we present some main protocols which are based on artificial bee colony

   optimization. These routing schemes are given as follows-

   = 1

   (2)

   =1

   1. Bee Ad Hoc Routing Scheme

      Where N, is the number of patterns in the jth cluster, Wij the association weight of pattern Xi with cluster j, which will be either 1 or 0. When the bee find the good nectar food in other location then bees forget the old position and memorized the new position. The cost function for the pattern i (f.) can be calculated as

      The routing schemes based on artificial bee colony, used in MANET are called as bio inspired routing. Now we presenting the first scheme based on ABCO. It is based on the searching method and foraging method of the honey bee. As I told earlier it is based on working bee model which has two bee scout bees and forager bees. The bee ad hoc architecture is depicted in detail in figure 2.

      = 1

      , ( )

      (3)

      In this scheme [11] every node is consider as the hive with three floor entrance, dance floor and packet floor. Now

      =1

      Where Dtrain is the number of training patterns which is used to normalize the sum that will range any distance within [0.0, 1,0] and (Pi CLknown(xj) ) defines the class that instance belongs

      we describe the working of these three floors separately.

      In the ad hoc network the protocols for routing is defined as in the transport layer. So according to the diagram the node

      to according to database. The nectar quality or fitness fiti be define as

      Fit =1/1+f

      can

      (4)

      hive is lye in between network layer and application layer. So

      entrance floor is work as the interface for the media access control protocol of the network layer and deals with incoming and outgoing packets. If the hive node is the internal node then

      i i at the entrance scout received the packet if it has live time and

      Where fi is the cost function of the clustering problem And Pi is define as

      =

      (5)

      broadcast it further. In a table the scout id and source node information is stored. If replica is already receive then killed it. If in dance floor forager has the same destination then scout has been appended to it. If current node is the destination node

      =1

      then forager sends it to packing floor otherwise forward it to MAC layer to the next node.

      To produce the candidate food position in memory from the old one the following formula is used in ABC.

      Vij= Zij + ij(Zij- Zkj) (6)

      Where k E {I, 2… SN} and j E {I, 2… D} are randomly chosen indexes. Although k is determined randomly, it has to be different from i. i,j is a random number between [-1,1]. It controls the production of neighbor food sources around Zij and represents the comparison of two food positions visible to a bee.

      Application layer (TCP, UDP)

      B E

      PACKING FLOOR A J

      DANCE FLOOR C F

      ENTERENCE

      Bee Hive Network layer

      Fig 2. Overview of the bee ad hoc architecture [10]

      Packing layer is providing the interface to the transport layer and received data from it. At once the data is come then it the packer to it. Packer stores the data packet. And it locket the new forager to it form the dance floor. If packer finds the perfect forager then it will hand over the data to it and dismiss. Dance floor is the important floor for this routing scheme.

      All important decision has been taken in this floor. According to the quality of path forager appoint the new forager after returning its journey that it traversed. By the remaining power of the nodes lying on its route forager decide the quality of route. The cloning of forager may be allowed many times in two conditions. First, route is good if all nodes of the route have enough remaining power and second is if the nodes lying on the route have less power because packers are waiting for foragers then we called it this route is not good. One other condition is that route is good, no packers are waiting for foragers because other is doing nice job in data transporting. This scheme is firmly based on scout and forager concept of swarm intelligence, through this many forager are regulating for each route.

   2. PEEBR

      D G I

      Fig 3. Example of path discovery process using bee agents[13]

      According to this figure there are 3 routes from source A to J like A-B-E-J, A-D-G-I-J and A-B-E-F-I-J but according to the algorithm the energy efficient path is A-B-E-J show bold in the figure.

      Now we show the algorithm proposed in [12]. According to this algorithm our motive is to select the energy efficient route. Now we have the information about source node and the destination node. We can start the procedure by searching the all possible optimal path with potential M. Every source node sends the scout for search the path according to it s time to live by the beacon massage and collect every information about the energy. If time to live is expired then it will reverse back. When scout agent reach to destination it reverse back by the same route that recorded to the source. Now the backward agent becomes forager. Packet has the information about the discovered path like battery power residual Pm. where i=1 to N nodes on each path j and the number of nodes h(Pj ) and end-to end delay D(Pj). Now source node calculate the total energy consumption by each node over the path by the given formula E(ni)=Et(Pni)+Er(Pni)+Eo(Pni) where E(p) = i * v * t p and Et (p) = 280mA * v * t p where E(p) is te energy required for packet transmission i represents the current consumption, v is the voltage used. Et(p) is the energy consumed by the node in transmit mode. Er(P) is the energy consumed in reception mode. And Er(p) = Eo(p) = 280mA * v

      * tp and tp is

      The PEEBR [12] means Predictive Energy Efficient Bee Routing algorithms. It is also the bio inspired routing

      =

      6

      610

      +

      54106

      Where Ph is the packet header size

      algorithm. It deliberates selection energy conversion and evolution during routing. It is also based on scout and forager bee concept of bee colony optimization. In this during the traveling node to node along with the routing path scout bee collects energy consumption and delay parameters. And forager assigns the routing path according to check the goodness of the routing path. It has two main phases. The first phase named Node-level for battery power saving and in second phase choosing the path with energy consumption, named network level. According to the network level energy consumption there are two main informations find about the energy of the path. First is how many energy is residual in the battery of the all nodes. Second is how many energy is consumed in transporting the data in the given routing path. We show this example by the figure 3.

      and Pa is the packet data size. Energy consumption will be

      calculated as

      E(Rj) = h(Rj)*Er(p) (8)

      Start with source node n

      Send scout to all neighbors with TTL

      Where N is the number of nodes on path R, d( nji,nji+l) is the propagation delay between each node i on path j and the next node i+1 on the same path. Finally goodness of all path can be calculate by

      = ( )

      (10)

      Y =1

      ( )

      If TTL expire

      N

      Destination node nd N reached

      Y

      Send back scout beacon from nd on Pj

      For each node ni on pj

      Compute energy consumed E(ni)

      Compute residual power P(ni)

      For each path Pj

      Foragers Compute energy consumed E(Rj) and delay D(Rj)

      Deduce the goodness ratio g(Rj)

      Then the forager decide the optimal path with highest goodness path by this formula Ro= max (g(Rj)). After deciding the path other path will be discarded. The flow graph of this algorithm is shown in figure 4.

   3. Dynamic Shortest Path Routing using ABC

   In [14] authors present the scheme about the dynamic shortest path routing problem. This is also based on artificial bee colony optimization. In this scheme four phases first is initialization phase in which the population of food are initialized and define the paths. Second phase is employed bees phase in which discovery of new food occurs by Employed bees. Third phase is on looker bee phase in which the quality of food is checked and last phase is scout bee phase in which bee trying to improve the quality of food by searching.

   So in this section we present the energy efficient routing schemes based on artificial bee colony optimization in swarm intelligence.

5. CONCLUSION

A mobile ad hoc network plays an important role in communication and natural calamities. It was vastly used in environmental monitoring like through it we can effectively act to prevent the consequences of floods or aware form it through signal communication. The ad hoc networks have been deployed in any where for monitor in real time. Ad hoc network also use at the time of earthquake. At the time of national disaster energy constraint is the main factor. So in this paper we have presented the different classes of routing protocols and different routing schemes which is based on artificial bee colony optimization, a field in swarm intelligence. Through this technology routing is makes easy and energy efficient at the time of natural disaster. In future we will try to present some different routing techniques and give the comparative simulated result with ant colony protocols.

R, is the optimal path between ns and nd where R,= max (g (Rj)

End

Fig 4. PEEBR algorithm flow chart [12]

Where h(Rj) is the number of hops over a path Rj and Er(P) is the amount of energy consumed during reception of a packet

p. the end to-end propagation delay is calculated as

ACKNOWLEDGEMENT

We all of us would like to thanks to lord Krishna and goddess Durga. We all of us would like to thanks our head of the department of our college computer science and engineering.

=1

=

(, + 1)

(9)

REFERENCES

1. Priyanka Goyal, Vinti Parmar, Rahul Rishi, MANET: Vulnerabilities, Challenges, Attacks, Application, IJCEM International Journal of Computational Engineering & Management, Vol. 11, January 2011 ISSN (Online): 2230-7893 www.IJCEM.org

2. L. M. Feeney. "An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks". Mobile Networks and Applications, 6(3):239-249,2001.

3. Mayur Tokekar and Radhika D. Joshi, "Enhancement of Optimized Linked state routing protocol for energy conservation", CS & IT-CSCP, 2011

4. Bonabeau, E.; Dorigo, M. & Theraulaz, G. (1999). Swarm Intelligence. From Natural to Artificial Systems, Oxford University Press, 0-19- 513159-2, Oxford

5. Bonabeau, E.; Dorigo, M. & Theraulaz, G. (2000). Inspiration for optimization from social insect behaviour, Nature, Vol. 406, No. 6, (July 2000) 39-42, 0028-0836

6. D. Karaboga and Ozturk, "A novel clustering approach: Artificial Bee Colony (ABC) algorithm", Elsevier, Applied Soft Computing 11 (2011) 652-657, 2011

7. D. Karaboga and B. Basturk, "On the performance of artificial bee colony (ABC) algorithm", Elsevier, Applied Soft Computing 8 (2008) 687-697, 2008

8. Dr. Arvinder Kaur, Shivangi Goyal, A Bee Colony Optimization Algorithm for Fault Coverage Based Regression Test Suite Prioritization, International Journal of Advanced Science and Technology Vol. 29, April, 2011

9. Dr. Arvinder Kaur, Shivangi Goyal, A Survey on the Applications of Bee Colony Optimization Techniques, International Journal on Computer Science and Engineering (IJCSE), ISSN : 0975-3397, Vol. 3 No. 8 August 2011

10. Horst. F. Wedde, Muddassar Farooq, Thorsten Pannenbaecker, Bjoern Vogel, Christian Mueller, Johannes Meth and Rene Jeruschkat, BeeAdHoc: An Energy Efficient Routing Algorithm for Mobile Ad Hoc Networks Inspired by Bee Behavior, GECCO05, June 2529, 2005,

    Washington, DC, USA. Copyright 2005 ACM 1-59593-010-8/05/0006

11. CH. V. Raghavendran, G. Naga Satish, P. Suresh Varma Prof., Intelligent Routing Techniques for Mobile Ad hoc Networks using Swarm Intelligence, I.J. Intelligent Systems and Applications, 2013, 01, 81-89 Published Online December 2012 in MECS (http://www.mecs- press.org/) DOI: 10.5815/ijisa.2013.01.08

12. Imane M. A. Fahrnv, Hesham A. Hefny, Laila Nassef, PEEBR: Predictive Energy Efficient Bee Routing Algorithm for Ad-hoc Wireless Mobile Networks, The 8th International Conference on INFOrmatics and Systems (INFOS2012) – 14-16 May, Computer Networks Track,

    Faculty of Computers and Information – Cairo University

13. Ahmed S. Nagy, Amr A. EI-Kadi, Mikhail N. Mikhail, "Swarm Congestion & Power Aware Routing Protocol for MANETs", Communication Networks and Services Research Conference, IEEE Computer Society, 2008

14. C.Ambika, M.Karnan, R.Sivakumar, Resolving Dynamic Shortest Path Routing Problems in Mobile Adhoc Networks Using ABCAnd ACO, International Journal of Computer & Organization Trends Volume3Issue3- 2013, ISSN: 2249-2593 http://www.ijcotjournal.org