Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
| Marghny H.Mohamed1, Mahmoud.A Mofaddel1, Hamdy.H El-Sayed 1 CS Dept., Faculty of computer and information, Assiut University, Egypt. 2Mathematics Dept., faculty of science,Sohag University, Egypt. |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
Ad-hoc network is a collection of mobile nodes dynamically forming a temporary network without the use of any existing infrastructure or centralized administration. Building such a network poses many technical challenges such as routing, energy consumption, load balancing, and security. Routing in mobile ad-hoc network (MANETs) becomes more sophisticated issue especially when a certain quality of service (QOS) requirement is to be satisfied. In this paper, we address the problem of routing in mobile ad-hoc network under ad-hoc network characteristics. We concentrate on two parameter hop count and path distance changes with some ad-hoc network characteristics characteristics like topology changes, average number of neighbor nodes, number of nodes and transmission range. Different topologies are compared like circle, square and rectangle. Our results compared the effects of these characteristics on the Ad-Hoc On Demand Distance Vector (AODV) and our proposed algorithm Bee-Dijkstra Algorithm (BDA). Both of the path route and hop count in BDA and AODV is changed with the CTR (Critical Transmission Range) and this leads us that the CTR has clear effects on the network connectivity and the path routing.
INTRODUCTION |
| Ad-hoc networks do not rely on any pre-established infrastructure and can therefore be deployed in places with no infrastructure. This is useful in disaster recovery situations and places with non-existing or damaged communication infrastructure where rapid deployment of communication is needed. Forming ad-hoc network among all users wanting to communicate with each other means that all users participating in the ad-hoc network must be willing to forward data packets to make sure that the packets are delivered from source to destination. Because nodes forward packets for each other, some sort of routing protocols is necessary to make the routing decisions. Currently there exist some standards for the routing protocols of ad hoc networks, and the work is still in progress. Many problems remain to be solved before any standard can be determined and applied industrially [1]. Artificial Bee Colony (ABC) algorithm is one of the most recently introduced swarm-based algorithms. ABC simulates the intelligent foraging behavior of a honeybee swarm. Dervis Karaboga and Bahriye Akay [2] used ABC for optimizing a large set of numerical test functions and the results produced by ABC algorithm are compared with the results obtained by genetic algorithm, particle swarm optimization algorithm, and differential evolution algorithm and evolution strategies. Results show that the performance of the ABC is better than or similar to those of other population-based algorithms with the advantage of employing fewer control parameters. |
| In this paper, we propose a new optimization algorithm. We focus on the topological shape effects and transmission range effects on reactive routing ad hoc network algorithms. A number of characteristics like average number of neighbor nodes, area of ad hoc network, transmission area and node density are presented. The effects of changing topological circle and square shapes on the two different algorithms Ad-hoc On demand Distance Vector (AODV) and Bee-Dijkstra algorithms (BDA) are studied. Our comparison uses new feature like hop count and path cost parameter through circle shape ad-hoc network. |
| The CTR (critical transmission range) is the minimum transmitting range that produces a connected communication graph and may lead to save the energy of network devices. If the CTR is less than the minimum value, then the graph will be disconnected. If the transmission range increased, the path may be different from the path of the CTR state and the graph will be strong connected. The path route is changed in Both of BDA and AODV by changing the CTR and this lead us that the CTR has clear effects on the network connectivity and the path routing. |
| The rest of the paper is organized as follows. Section 2 looked at swarm intelligence. Section 3 proposed a new optimization algorithm Bee-Dijkstra Algorithm. Section 4 experimental results are presented. Section 5. concludes the results. |
SWARM INTELLIGENCE |
| Swarm intelligence has become interested to many research scientists related to the fields in recent years. Bonabeau et al [3] has defined the swarm intelligence as “any attempt to design algorithms or distributed problem-solving devices inspired by the collective behaviour of social insect colonies and other animal societies”. Bonabeau et al [3] concentrated the viewpoint on social insects alone such as termites, bees, wasps as well as other different ant species. However, the term swarm is used in a general manner to refer to any restrained collection of interacting agents or individuals. The classical example of a swarm is bees swarming around their hive; nevertheless the metaphor can easily be extended to other systems with a similar architecture. Similarly a flock of birds is a swarm of birds. An immune system [4] is a swarm of cells and molecules as well as a crowd is a swarm of people [5]. Particle Swarm Optimization (PSO)[6] assumes powerful algorithm for especially the bee colony algorithm that is used widely in ad hoc network. |
| The bee colony algorithm [7] is a swarm intelligent optimization algorithm inspired by honey bee foraging. It is a new optimizer algorithm for multivariable and multi-modal continuous function optimization.[8,9,10].The ABC algorithm classifies the foraging artificial bees into three groups namely employed bees, onlooker bees and scouts. The first half colony consists of the employed bees and second half consists of onlooker bees. For every food source, there is only one employed bee and the employed bee of abandoned food source becomes scout. In ABC algorithm, each solution to the problem is considered as food source and represented by a D-dimensional real-valued vector, whereas the fitness of the solution corresponds to the nectar amount of associated food resource. ABC algorithm is also similar to other swarm intelligent based approaches i.e., it is also an iterative process[11]. It starts with population of randomly distributed solutions or food sources. The following steps are repeated until a termination criterion is met. |
| a. Calculate the nectar amounts by sending the employed bees on to the food sources. |
| b. After sharing the information from employed bees select the food sources by the onlookers and .determine the nectar amount of food sources. |
| c. Determine the scout bees and send them to find out new food sources. |
| Pseudo code for ABC algorithm |
| a. Initialize population with random solutions. |
| b. repeat |
| c. place the bees on their food sources |
| d. place the bees on their food sources depending on their nectar amount. |
| e. send the scouts to the search area for discovering new food source. |
| f. Memorize the best food source found so far |
| g. Until requirement are met. |
| Next Anew idea for developing the bee colony algorithm is proposed by hybriding the bee colony algorithm with dijkstra algorithm. |
THE PROPOSED BEE –DIJKSTRA ALGORITHM (BDA) |
| The proposed bee-dijkstra algorithm uses Dijkstra algorithm that plays a prominent role in source routing, where searching for optimal routing plays an important role in the performance of routing in MANETs [12]. This paper proposes a new optimization algorithm that uses the bee behavior in food forging as the functions to be used by the processing engine. The algorithm is based on combined approach of Bee Colony algorithm and Dijkstra algorithm. The algorithm starts with the scout bees being placed randomly in the search space. |
| The Bee-Dijkstra algorithm is: |
| a. initialize the population |
| b. bees in the hive |
| c. bees search randomly for food |
| d. bees return to the hive |
| e. bees begin for a waggle dance |
| f. determine the distance from the hive to the food using dijkstra to compute the shortest distance (Short route) from the hive to the food |
| g. the hive uses this path (route) to send the bees for food without using guides or maps. |
| h. end |
| The parameters in the Bee-Dijkstra Algorithm are the number of food sources which is equal to the number of employed or onlooker bees which is Colony Size, the working bee rate and the number of cycles or number of iteration (MCN) that are required to terminate the program[13]. |
 |
| Figure 1 shows the flowchart of implementation of bee dijkstra algorithm for optimization of shortest path. In the initialization phase, the control parameters are set like colony size, iteration number (MCN) and the working of bees rate. In the next phase the flowchart is given as input with the number of locations that are to be visited. Then the path is obtained by using dijkstra algorithm. The path is reset for bees and the scout bees uses this path and the number of working bees is update. The optimization loop is terminate when the number of iteration are completed and the best path and cost are obtained. |
EXPERIMENTAL RESULTS |
| Our experimental focus on Hui Li and Dan Yu model [14] and the extension in [15] and [16] for investigating two important properties of ad hoc network, the average of neighbor nodes and number of nodes. The coverage shape is perfect circle that nodes move in it. this shape exactly the transmission area that could be calculating from the following equation. |
 |
| by using this equation we can calculate the radius R of this circle shape as following |
 |
| We focus on the topological shape effects and transmission range effects on reactive routing ad hoc network algorithms. A number of characteristics like transmission range, area of ad hoc network, transmission area and node density are presented. The effects of changing topological circle shape on the two different algorithms Ad-hoc On demand Distance Vector (AODV) and Bee-Dijkstra algorithms (BDA) are studied. Our comparison uses the hop count and path cost parameter through circle shape ad-hoc network. |
| The CTR (critical transmission range) is the minimum transmitting range that produces a connected communication graph and may lead to save the energy of network devices. If the CTR is less than the minimum value, then the graph will be disconnected. If the transmission range increased, the path may be different from the path of the CTR state and the graph will be strong connected. |
| Ad hoc network properties evaluations: |
| The network with 10 nodes in two dimension with minimum transmission range (CTR R=4.5) is used. The network will be possible connected. The CTR on AODV and the proposed algorithm BDA for routing in the network is tested as the follows: |
| In BDA state: |
| When the CTR is equal to 4.5 in the network with 10 nodes the path from node 1 to node 10 is 1 - 2 - 6- 8 – 10, hop count is 4 and the path distance is 14.5708. |
| After increasing the transmission range (R=6.5) the path becomes 1- 4 - 9 – 10 and the network is considered as strong connected. The hop count is 3 and the path distances is 12.6056 |
| In AODV state: |
| When the CTR is equal to 4.5 in the network with 10 nodes. The path from node 1 to node 10 is 1 - 2 – 3 – 4 -7 – 9 -10 and the network is connected the hop count is 6 and path distance is 20.6588. When the transmission range increasing (R =6.5) the path in the network becomes 1 – 2 – 3 – 4 - 9 - 8 -10 the hop count is 6 and path distance is 25.6927. |
| Both of the path route and hop count in BDA and AODV is changed with the CTR and this leads us that the CTR has clear effects on the network connectivity and the path routing. |
| Circle area: |
| Our experimental results examine the effects of some characteristics like the number of nodes, average number of nodes, transmission range and network area on the circle topological shape. Then, the changes of these characteristics on some parameters like hope count and path distance is evaluated. The simulation is implemented in Matlab [17]. The changing topological circle shape area, average number of neighbor node and node density (number of nodes) changes effects on the hop count and path distance is tested. |
 |
 |
 |
Square area: |
| Our experimental results examine the effects of some characteristics like the number of nodes, average number of nodes, and transmission range and network area on the square topological shape. Then, the changes of these characteristics on some parameters like hope count and path distance is evaluated. The simulation is implemented in Matlab [17]. The changing topological square shape area, average number of neighbor node and node density (number of nodes) changes effects on the hop count and path distance are tested. |
 |
 |
 |
| Rectangle area: |
| Our experimental results examine the effects of some characteristics like the number of nodes, average number of nodes, and transmission range and network area on the rectangle topological shape. Then, the changes of these characteristics on some parameters like hope count and path distance is evaluated. The simulation is implemented in Matlab [17]. The changing topological rectangle shape area, average number of neighbor node and node density (number of nodes) changes effects on the hop count and path distance are tested. |
 |
 |
 |
Results discussions and analysis: |
| In this paper a new parameters like node density, average number of neighbor nodes and topology changes on the hop count and path distance with changing the transmission area and area of network are studied. Minimum hop count and minimum path cost are computed for Ad hoc On Demand Distance Vector (AODV) and Bee-Dijkstra Algorithm (BDA) that has been showed in table 1, 2, 3, 4, 5 ,6 , 7 ,8 and 9. Results have been shown in the previous tables. |
| First in circle topological shape figure (a) and (b) BDA is more accurate than AODV. Figure depicts that (a) BDA is more efficient than AODV (b) BDA is more stable than AODV. Figure 4 shows that (a) BDA is more accurate than AODV (b) BDA is more stable than AODV. We can conclude that BDA gives better performance than AODV in circle shape. |
| Second in square shape figure 5 (a) and (b) shows that BDA has minimum hop count and path cost than AODV. Figure 6 (a) and (b) explain the average number of neighbor nodes on hop count and path cost respectively also explains that BDA has minimum hop count and path cost than AODV. Figure 7 depicts that BDA is more efficient than AODV both (a) and (b) BDA has minimum hop count and path cost. From the previous results again we can conclude that BDA gives better performance than AODV in square shape. |
| Third rectangle shape figure 8 depicts that BDA has minimum hop count and path cost than AODV in (a) and (b) respectively. Figure 9 shows that BDA is more accurate than AODV in (a) and (b). figure 10 number of nodes changes on hop count and path cost in (a ) and (b ) respectively BDA is more efficient than AODV. From these results the performance of BDA better than AODV. |
CONCLUSION |
| Together with emergence of MANETs, new routing approaches are required since MANETs are highly dynamic and distributed in nature. This paper looks at some of these problems and proposed a new optimization algorithm. The topological shape effects and transmission range effects on reactive routing ad hoc network algorithms are discussed. A number of characteristics like transmission range, area of ad hoc network, transmission area and node density are presented. The effects of changing topological circle and square shapes on the two different algorithms Adhoc On demand Distance Vector (AODV) and Bee-Dijkstra algorithms (BDA) are studied. Our comparison uses the hop count and path cost parameter through circle and square shapes ad-hoc network. This work concludes that BDA is better performance than AODV. The future work lies in incorporating factors like signal strength into these algorithms so that the routing algorithms will adjust to the dynamic topology. |
References |
|