ABSTRACT
Wireless Network is an active research area in computer networks. There are many research issues in wireless network such as Identification of optimal route for data communication, efficient utilization of energy, clustering, providing congestion free communication, offering scalability, maintaining the Quality of Service (QoS), in which routing become a very important research issue. Minimization of power requirement, utilizing minimal network resources like bandwidth, gathering information and updating link failures are few constraints for designing optimal routing protocol for wireless network. Therefore, the traditional wired routing protocols are not suitable for wireless environment. This study proposes a hybrid routing protocol which utilizes two swarm intelligence approaches, artificial bee colony and ant colony optimization, called as vast intelligence of swam usage, for efficient routing in wireless environment. In order to promote error free communication, the bee colony used for identifying efficient cluster head and the ant colony identifies shortest route from source to cluster head. The results of the proposed work shows that the proposed Hybrid swarm intelligence will provide optimality than existing systems.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/itj.2013.791.797
URL: https://scialert.net/abstract/?doi=itj.2013.791.797
INTRODUCTION
Wireless communication is based on the principle of broadcast and reception of electromagnetic waves. The wireless communication is in two forms, infrastructure based and Ad hoc networks. The wireless network has many challenging characteristics, such as path loss, interference and blockage. Therefore designing of wireless routing is very complex than wired routing due to these constraints. Also the wireless routing requires additional computational effort. Hence, the wireless routing needs some more tasks in addition to wired network which are added to meet the wireless environment. In the graph theory, the routing can be explained as follows: Let the routing is the problem of finding closed shortest tour between given source to destination which aims for minimal cost that visits each city once. This problem is also called as well known key term, Traveling Salesman Problem (TSP) (Siva and Manoj, 2000).
The traditional routing algorithm is known as Link State and Distance Vector and these algorithms are implemented in the well-known protocols such as Open Shortest Path First (OSPF), Routing Information Protocol (RIP). These routing protocols are in-efficient for the wireless environment, due to frequent mobility, limited bandwidth and power, hidden and exposed terminal and interference. The major research in the routing of ad hoc network should fulfill energy optimization (Alfawaer et al., 2007) which is more important in some applications. The Link State and Distance Vector can be modified for wireless network and the modified versions of these routing methodologies are already implemented such as DSR (Dynamic Source Routing), DSDV (Destination Sequenced Distance Vector) and AODV (Ad hoc On-demand Distance Vector). As the performance of these routing protocols are always not optimal, swarm intelligence is applied for routing model.
Implementation of Ant Colony Optimization (ACO) in the wireless environment requires many critical issues such as complexity, convergence (Yu and Zhang, 2009), mutation model (Ren et al., 2008). The ACO can be combined with other models which termed as hybrid model, for example, ACO with filtering model proposed by Wu et al. (2010).
Designing an efficient routing protocol for ad hoc network is a very challenging task and it has been an active area of research. Many routing protocols have been proposed and these protocols can be broadly classified as proactive and reactive. Ad hoc On-demand Distance Vector (AODV) and Dynamic Source Routing (DSR) protocols are well known examples of reactive protocols. Many other classification of wireless routing also used in industry, Zone Routing Protocol (ZRP) and the Hazy Sighted Link State (HSLS) protocol are example for hybrid protocol, the Greedy Perimeter Stateless Routing (GPSR) protocol is an example of geographic protocol (Wu et al., 2010).
The existing heuristics have addressed only some aspects of MANET characteristics, such as load balancing, mobility, or algorithmic convergence. Therefore, Xiao-Ming et al. (2010) introduced a novel approach to solving the connected dominating set election problem, in which the topology management by priority ordering or integrating multiple factors (energy and mobility) into a single metric for cluster election decisions. This approach uses the Neighbor-aware contention resolution (NCR) algorithm to provide fast convergence and load balancing with regard to the battery life and mobility of mobile nodes. Based on NCR, the authors assign randomized priorities to mobile stations and elect a minimal dominating set (MDS) and the Connected Dominating Set (CDS) of an ad hoc network according to these priorities. In doing so, the method proposes in this study, called TMPO, which requires only two-hop neighbor information for the MDS elections. The dynamic priorities assigned to nodes are derived from the node identifiers and their willingness to participate in the backbone formations. The willingness of a node is a function of the mobility and battery life of the node. The integrated consideration of mobility, battery life and deterministic node priorities makes TMPO one of the best performing heuristics for topology management in ad hoc networks.
In the recent network routing, Ant-Net Routing using Ant Colony Optimization (ACO) technique provide a better result than others due to its real time computation and less control overhead (Dorigo et al., 1996; Dorigo and Stutzle, 2004). Kwang and Sun (2003) compared all routing algorithms with ACO, concludes that ants are relatively small, can be piggybacked in data packets and more frequent transmission of ants may be possible in order to provide updates of routing information for solving link failures. Hence, using ACO for routing in dynamic network seems to be appropriate. Routing in ACO is achieved by transmitting ants rather than routing tables or by flooding LSPs. Even though it is noted that the size of an ant may vary in different systems/implementations, depending on their functions and applications, in general, the size of ants is relatively small, in the order of 6 bytes.
In an experiment known (Dorigo and Gambardella, 1997) as the double bridge experiment, the nest of a colony of Argentine ants was connected to a food source by two bridges of equal lengths. The ACO used the term Argentine ants for the ants which identifies the path, simply says the predictor of the path. The argentine ants always spread the work place, searching other possible routes. In such a setting, ants start to explore the surroundings of the nest and eventually reach the food source. Along their path between food source and nest, Argentine ants deposit pheromone.
PROPOSED WORK
In this proposed, combined swarm intelligence MANETs routing protocol, has two important tasks, which are (1) electing cluster head and (2) communicating data from source node to destination cluster head through the optimal path. These two tasks are different in execution and implementation; therefore, two different methodologies are applied as solution. The Swarm Intelligence based Artificial Bee Colony (ABC) is applied for identifying optimal cluster head and another popular Swarm Intelligence technique Ant Colony Optimization (ACO) is applied for optimal routing. These two Swarm intelligence techniques collectively called Combined Swarm Intelligence Routing Protocol (CSI-RP).
Swarm intelligence is a new discipline of study that contains a relatively optimal approach for problem solving which are the imitations inspired from the social behavior of insects and animals, for example, ACO algorithm, Honey Bee Algorithms, Fire Fly Algorithm. The ACO Algorithm is a study derived from the observation of real ants behavior and uses these models as a source of inspiration for the design of novel algorithms, which is the solution for optimization and distributed control problems. The Honey Bee Mating algorithm is the growing technique, which is proposed in late 2005, for many engineering applications.
The ACO is an optimization technique which is widely applied for a variety of optimization problems and in almost all engineering field of studies. The few application of ACO in the recent year are ad hoc network (Bao and Garcia-Luna-Aceves, 2010), project scheduling (Wang and Zhou, 2009), production management and maintenance scheduling (Osama et al., 2005), cash flow management (Wei-Neng et al., 2010), manpower scheduling and management (Lee et al., 2010), TSP (Lopez-Ibanez and Blum, 2010; Xing et al., 2010).
To identify the optimal location of bio-mass power plant (Vera et al., 2010), resource allocation (Quijanoa and Passino, 2010), constraint optimization problem (Karaboga and Akay, 2009), data clustering in data mining (Karaboga and Ozturk, 2011) are some of the successful solutions based on ABC algorithm. The detailed honey bee mating algorithm is explained. The proposed work in this study is extension of our earlier work (Visu et al., 2012a, b).
Electing efficient cluster head using ABC algorithm: The ABC algorithm requires a number of parameters to be set, namely:
• | Number of scout bees (n) |
• | Number of elite bees (e) |
• | Number of patches selected out of n visited points (m) |
• | Number of bees recruited for patches visited by "elite bees" (nep) |
• | Number of bees recruited for the other (m-e) selected patches (nsp) |
• | Size of patches (ngh) and |
• | Stopping criterion |
The algorithm starts with the n scout bees being placed randomly in the search space.
The bees search for food sources in a way that maximizes the ratio:
(1) |
where, E is the energy obtained and T is the time spent for foraging. Here, E is proportional to the nectar amount of food sources.
In a maximization problem, the goal is to find the maximum of the objective function F (θ), θ ε RP. RP represents the region of search area. Assume that θi is the position of the ith food source; F (θi) represents the nectar amount of the food source located at θi and it is proportional to the energy E (θi).
Let P(C) = {θi(C) | i = 1, 2... S} represent the population of food sources being visited by bees, in which, C is cycle and S is number of food sources around the hive. The preference of a food source by the worker bee depends on the nectar amount F (θ) of that food source. As the nectar amount of the food source increases, the probability with the preferred source by the worker bee increases proportionally. Therefore, the probability with the food source located at θi will be chosen by a bee can be expressed as:
(2) |
The position of the selected neighbour food source is calculated as the following:
(3) |
and the stop criteria of the system is:
(4) |
where, Ni (Q) represents the values of nectar of queen, Ni (E) represents the values of nectar of Elite bee and Hth represents the minimum threshold value of the Hive. At the end of iteration, the colony will have two parts to its new population-representatives from each selected patch and other scout bees assigned to conduct random searches.
The bees, both scout bees and elite bees, in the networking world are hello packets, which are flooded in the network on every unit of time (Δt), similar to ant and LSP. The hive in the ABC is mapped in the networking terminology as control center. The energy in the ABC is the value of battery power of ad hoc node which defined in Joules. The manufacturers of the ad hoc and sensor nodes are designed in such a way that the nodes will broadcast the energy based on request.
The bees are flooded on every unit of time, which is used for updating the changes in the network, failure node and energy of the nodes. Therefore, the changes in the energy of current cluster head is updated in the control centre. Based on these updated values, if the energy of the current cluster head is lesser than other nodes available in the same cluster then the concern node is elected as cluster head. This methodology gives better life time of the ad hoc and sensor nodes.
Optimal routing path between source to cluster head using ACO: The main idea of ACO is to model the problem as the search for a minimum cost path in a graph. Artificial ants walk through from nest to food, looking for good paths. Each ant has a rather simple behavior so that it will typically only find rather poor-quality paths on its own. Better paths are found as the emergent result of the global cooperation among ants in the colony. The behavior of artificial ants is inspired from real ants, they lay pheromone trails on the graph edges and choose their path with respect to probabilities that depend on pheromone trails and these pheromone trails progressively decrease by evaporation.
In addition, artificial ants have some extra features that do not find their counterpart in real ants. In particular, they live in a discrete world and their moves consist of transitions from nodes to nodes. Also, they are usually associated with data structures that contain the memory of their previous actions. In most cases, pheromone trails are updated only after having constructed a complete path and not during the walk and the amount of pheromone deposited is usually a function of the quality of the path. Finally, the probability for an artificial ant to choose an edge often depends not only on pheromones, but also on some problem-specific local heuristics. The detailed survey on ACO is available in (Mohan and Baskaran, 2011, 2012) for various engineering optimization problems.
In a traditional ACO model, consider that there are four ants (A1, A2, A3 and A4) and two routes (R1 and R2) leading to a food source (F0), where R1 and R2 such that R1>R2 and R1 = 2*R2. Initially, all ants are at the decision point Ne and they have to select between R1 and R2 to reach Fo:
• | At Ne, all ants have no knowledge about the location of food (F0). Hence, they randomly select from {R1, R2}. Suppose that A1 and A2 choose R1 and A3 and A4 choose R2 |
• | As A1 and A2 move along R1 and A3 and A4 move along R2, they leave a certain amount of pheromone along their paths τR1 and τR2, respectively. |
• | Since R1>R2, A3 and A4 reach F0 before A1 and A2. When A3 and A4 pass R2 to reach F0, τR2 = 2, but A1 and A2 have yet to reach F0 and τR1 = 0. To return to Ne from F0, A3 and A4 have to choose between R1 and R2. At F0, A3 and A4 detect that τR2 > τR1, hence they are more likely to select R2 |
• | As A3 and A4 pass R2 for the second time to reach Ne, τR2 is incremented to 4. The increase in τR2 further consolidates R2 as the shorter path. When A1 and A2 reach F0, τR2 = 4 and τR1 = 2. Hence, A1 and A2 are more likely to select R2 to return to Ne |
In this example, any ant at F0, (respectively, Ne ) will be able to determine the optimal path once A3 and A4 reach F0. If an ant is at a choice point when there is no pheromone (e.g., initially at Ne), it makes a random decision with a probability of 0.5 of choosing R1 or R2. However, when pheromone is present (e.g., when the ant is at F0), there is a higher probability that it will choose the path with the higher concentration of pheromone.
In every t unit of times, the forward ant is generated and forwarded to collect the information about the grid systems. The forward ants will collect the information of currently running process (traffic) and the expected time of completion. The information is stored in the scheduling table. The table contains next optimal resource allocation and also other feasible allocations. From the table, the optimal resource is selected or the load is shared into many feasible resources. The optimal load sharing is explained in the following mathematical models.
The following random proportional rule is applied as State transition rule: for choosing task ti, and the probability of selecting a grid/resources mj is:
(5) |
where, TD is the pheromone value corresponding to resource j for task i and 0<TD<1 is the local heuristic value. Fun (TD, i, j, η) is a function in TD and η (this function value is high when TD and η are high). Assuming that at a given moment in time, m1 ants have used the first resource and m2 the second one, therefore, the probability p1 for an ant to choose the first bridge is:
(6) |
where, T(r, s) is the pheromone deposited in the path between r and s, T(r, s) is the corresponding heuristic value. β is a parameter which determines the relative importance of pheromone versus execution time (β>0). The pheromone update policy is as follows:
(7) |
(8) |
The Fun (TD, r, s) identifies the probability of source nodes to every cluster head. In which, the highest probability is chosen as efficient path for communication. As this process is highly dynamic in the ACO, the efficient path will be automatically updated every unit time for avoiding path loss, and frequent mobility of the nodes.
The ant in network is a hello packet, flooded in the network on every unit of time (Δt), which is equivalent to Link State Packets (LSP) in Link State (LS) routing protocol. Pheromone in ACO is a value, which is computed in such a way that the every routing packet (ant) received in the source node. Initially, the pheromone value of each path in the source node is initialized as 0. The pheromone value is increased when the ant reaches the source node. In networking world, the food source and nest of ACO model are mapped as source node and destination node, respectively.
The proposed work is explained using the Fig. 1 which shows the sample ad hoc network with six clusters and each clusters has six nodes. The Table 1 shows sample node details of one cluster. The node address and node energy are noted in the Table 1. The proposed work is initiated to identify cluster head using ABC. The scout bees are flooded initially to every node, when the bee reaches the node, it collects node energy.
Fig. 1: | Ad hoc network with clustering and cluster head |
Table 1: | Sample node details in a cluster of Ad hoc network |
This node energy and the time to reach each node are noted down in the Table 1. Based on the Eq. 1, the energy factor of each node is calculated for all nodes shown in the Table 1. The node 2 has 10 units of energy factor which is higher than other nodes. Therefore, the node 2 is elected as cluster head of the concerned cluster.
RESULTS
The proposed CSI-RP is implemented in Network Simulator 2 (NS2). In the huge wireless routing, the AODV is prominent routing protocol (Kalwar, 2010) which modified by many researchers in the past few decades. In which, the neighbour detection for AODV (Krco and Dupcinov, 2003), improving efficiency of AODV (Song et al., 2004), combination of AODV with DSR (Bai and Sighal, 2006), secured AODV (Cerri and Ghioni, 2008), dynamic anomaly detection (Nakayama et al., 2009), Route Recovery mechanism (Pereira et al., 2010) are remarkable work. The proposed work is compared with recent AODV routing which is proposed by Pereira et al. (2010).
The performance is tested in a variety of nodes on wireless network and using various transport protocol on UDP.
Fig. 2: | Design of wireless network |
Table 2: | Response time in wireless routing |
Table 3: | Throughput in wireless routing |
Figure 2 show the design of type 1 wireless network and the Table 1 shows the various types of wireless network used for the simulations. The simulation is implemented for 10 sec. The throughput, response time and packet loss is calculated for entire 10 sec and the mean value of each calculation is shown in the tables.
The average response time shown in the tables and figures are the combination of route discovery time, transmission time, propagation delay in each node and waiting time in the intermediate queue.
The average response time and throughput in wireless environment are recorded in the Table 2 and 3. The throughput of CSI-RP is improved around 5 kbps than the existing routing protocol (Pereira et al., 2010) and a consequence the proposed work reduces the average response time (from 2 to 3 msec). As the result of reduced response time the number of packet travelled in a unit time is increased. This causes improvement in the throughput of proposed CSI-RP, which reflects in the Table 3.
CONCLUSION
The proposed CSI-RP protocol utilizes both ABC and ACO and reduces response time in UDP. The average response time shows transmission rate of the network, which leads to the number of packet travelled in a unit time, is increased. This efficient data transfer is visualized in the throughput. The throughput increased around 3%. Therefore, the proposed CSI-RP provides efficient data transmission on wireless network, hence concluded that CSI-RP is an efficient routing protocol than existing system.
REFERENCES
- Bao, L. and J.J. Garcia-Luna-Aceves, 2010. Stable energy-aware topology management in ad hoc networks. Ad Hoc Networks, 8: 313-327.
CrossRef - Mohan, B.C. and R. Baskaran, 2012. A survey: Ant colony optimization based recent research and implementation on several engineering domain. J. Exp. Syst. Appl., 39: 4618-4627.
CrossRefDirect Link - Mohan, B.C. and R. Baskaran, 2011. Survey on recent research and implementation of ant colony optimization in various engineering applications. Int. J. Comput. Intell. Syst., 4: 566-582.
Direct Link - Dorigo, M. and L.M. Gambardella, 1997. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE. Trans. Evol. Comput., 1: 53-66.
CrossRef - Dorigo, M., V. Maniezzo and A. Colorni, 1996. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B: Cybern., 26: 29-41.
CrossRefDirect Link - Karaboga, D. and B. Akay, 2009. A comparative study of artificial bee colony algorithm. Applied Math. Comput., 214: 108-132.
CrossRefDirect Link - Karaboga, D. and C. Ozturk, 2011. A novel clustering approach: Artificial Bee Colony (ABC) algorithm. Applied Soft Comput., 11: 652-657.
CrossRefDirect Link - Sim, K.M. and W.H. Sun, 2003. Ant colony optimization for routing and load-balancing: Survey and new directions. IEEE Trans. Syst. Man Cybernetics, Part A, 33: 560-572.
CrossRefDirect Link - Lee, H.Y., H.H. Tseng, M.C. Zheng and P.Y. Li, 2010. Decision support for the maintenance management of green areas. Expert Syst. Applied 37: 4479-4487.
CrossRef - Lopez-Ibanez, M. and C. Blum, 2010. Beam ACO for the traveling sales man problem with time windows. Comput. Operat. Res., 37: 1570-1583.
CrossRefDirect Link - Osama, H.H., N.S. Tarek and J.L. Myung, 2005. Probability routing algorithm for mobile ad hoc networks resources management. IEEE J. Sel. Areas Commun., 23: 2248-2259.
CrossRef - Quijanoa, N. and K.M. Passino, 2010. Honey bee social foraging algorithms for resource allocation: Theory and application. Eng. Appl. Artif. Intell., 23: 845-861.
CrossRef - Vera, D., J. Carabias, F. Jurado and N. Ruiz-Reyes, 2010. A Honey bee foraging approach for optimal location of a biomass power plant. Applied Energy, 87: 2119-2127.
CrossRefDirect Link - Visu, P., J. Janet, E. Kannan and S. Koteeswaran, 2012. Optimal energy management in wireless network using artificial bee colony based routing protocol. Eur. J. Sci. Res., 74: 301-302.
Direct Link - Wang, J. and Y. Zhou, 2009. Stochastic optimal competitive Hopfield network for partitional clustering. Exp. Syst. Applied, 36: 2072-2080.
CrossRef - Wei-Neng, C., J. Zhang, H.C. Shu-Hung, H. Rui-Zhang and O. Liu, 2010. Optimizing discounted cash flows in project scheduling-an ant colony optimization approach. IEEE Trans. Syst. Man Cybernetics-Part C: Applied Rev., 40: 64-77.
CrossRef - Xing, L.N., Y.W. Chen, P. Wang, Q.S. Zhao and J. Xiong, 2010. A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Comput., 10: 888-896.
CrossRef - Yu, X. and T. Zhang, 2009. Convergence and runtime of an ant colony optimization model. Inform. Technol. J., 8: 354-359.
CrossRefDirect Link - Wu, Z., Y. Kuang, N. Zhao and Y. Zhao, 2010. A hybrid CDMA multiuser detector with ant colony optimization and code filtering system. Inform. Technol. J., 9: 818-824.
CrossRefDirect Link - Ren, G., Z. Wu, N. Zhao and M. Lin, 2008. A mutated ant colony optimization algorithm for multiuser detection. Inform. Technol. J., 7: 948-952.
CrossRefDirect Link - Alfawaer, Z.M., G.W. Hua, M.Y. Abdullah and I.D. Mamady, 2007. Power minimization algorithm in wireless ad-hoc networks based on PSO. J. Applied Sci., 7: 2523-2526.
CrossRefDirect Link - Bai, R. and M. Sighal, 2006. DOA: DSR over AODV routing for mobile ad hoc networks. IEEE Trans. Mobile Comput., 5: 1403-1416.
CrossRefDirect Link - Pereira, N.C.V.N. and R.M. de Moraes, 2010. LatinCon05 - comparative analysis of aodv route recovery mechanisms in wireless ad hoc networks. IEEE Latin Am. Trans., 8: 385-393.
CrossRef - Cerri, D. and A. Ghioni, 2008. Securing AODV: The A-SAODV secure routing prototype. IEEE Commun. Mag., 46: 120-125.
Direct Link - Krco, S. and M. Dupcinov, 2003. Improved neighbor detection algorithm for AODV routing protocol. IEEE Communi. Lett., 7: 584-586.
CrossRef - Nakayama, H., S. Kurosawa, A. Jamalipour, Y. Nemoto and N. Kato, 2009. A dynamic anomaly detection scheme for AODV-based mobile ad hoc networks. IEEE Trans. Vehicular Technol., 58: 2471-2481.
CrossRef