Improvement of Connectivity in Mobile Ad Hoc Networks by Adding Static Nodes Based on a Realistic Mobility Model

  Improvement of Connectivity in Mobile Ad-hoc Networksby Adding Static Nodes Based on A Realistic MobilityModel Morteza Romoozi 1 , Hamideh Babaei 2   1 Computer Engineering Department, Islamic Azad University, Kashan BranchKashan, Iran 2 Computer Engineering Department, Islamic Azad University, Naragh BranchNaragh, Iran Abstract One of the ad hoc networks challenges is the connectivity problemcoming from changeable and dynamic topology of networks nodes.Adding static nodes is a solution for this challenge. These nodesare added in some critical points in network environment wherelack of mobile nodes is sensed in them. Many attempts have beenmade but in most of these studies no attention has been paid tonetwork mobility model or the problem has been solved based onunrealistic mobility model such as Random waypoint. This article presents an algorithm for finding best positions of these nodes,using two approximation methods, genetic algorithm and artificialfish swarm algorithm. Both algorithms consider both deploymentcost objective and connectivity efficiency objective in finding the positions. Simulation result shows that finding these critical pointsand adding static nodes in them can effect on performance of adhoc networks.  Keywords:  Ad-hoc networks, mobility model, connectivity, genetic algorithm, fish swarm algorithm.   1. Introduction Ad hoc networks are networks without any fixed structure.In this network each of nodes has two roles: one is network mobile node and another role is transferring packet of other nodes. One of the main properties of this network ismobility of its nodes which causes network topology tochange.Mobility model is one of the most important parts of the ad-hoc network simulator which dictates the nodes the way of  primary positioning and movement. Moreover, this modelshould be able to simulate a terrain that the node active in it.Consequently the closer model is to reality, the morereliable results of network evaluation are. In practice,evaluations that are done based on unrealistic mobilitymodel can produce different results in comparison tosimulation.Connectivity in ad hoc network vary because of continuesmovement of nodes. It is possible that the movement of oneor more nodes from one point to another causes the network  partitioning, because each node plays the role of router innetwork. This makes connectivity to one of the network‘smain problems and many researchers are trying to improvethe network connectivity by using different methods. Butsince the node movement is the main reason for partitioning,studies must be done by considering the node movementsand mobility models. However an efficient method that isindependent from other network parameters includingrouting protocol and signal propagation, is adding staticnodes in critical points of the network.Critical points are the points in which lack of nodes is morefelt and adding static node in them creates the most amountof connection in comparison to other points. Furthermore infinding such point, deployment cost of static nodes must beconsidered. It means each point of network terrain has twoobjectives for selecting as position of static point, itsefficiency for solving portioning problem and deploymentcost.This paper tries to find these points using twoapproximation algorithms, genetic algorithm and fish swarmalgorithm.The organization of this article is as follows: first the previous related works are reviewed. Then the mobilitymodel and its relation to connectivity is presented, and later a realistic mobility model is introduce, finally two methodsfor adding static nodes based on this mobility model issuggested. 2. Related Works In the section, we briefly review previous work related tothe connectivity issue in wireless networks.Gupta and Kumar showed in [1] that the critical commonrange r  n for connectivity of n randomly distributed wirelessnodes in a disk of unit area satisfies that, if  nncnr  n )(ln 2 += π   , IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011ISSN (Online): 1694-0814www.IJCSI.org176  then the resulting network is asymptotically connected with probability 1 if and only if c(n) → ∞.Ue and Kumar [2] studied the relationship betweenconnectivity and node degree from another angle. Theyassumed the same number of nearest neighbors aremaintained for each node, and showed that (i) the network isasymptotically disconnected with probability 1 as nincreases, if each node is connected to less than 0.074 lognnearest neighbors; and (ii) the network is asymptoticallyconnected with probability 1 as n increases, if each node isconnected to more than 5.1774 logn nearest neighbors.Wan and Yi [3] further studied the critical number of neighbors for k-connectivity and found the upper bound to be αe log n, where α > 1 is a real number and ≅ e 2.718 isthe natural base. Khuller [4] studied the Connectivity Augmentation  problem and determined a set of edges of minimum weight to be inserted so that the resulting graph isλ-vertex(edge)-connected. The problem is NP-hard for λ>1.Ausiello et al. [5] considered the  Minimum GeometricDisk Cover  (MGDC) problem. Given a set of points P in theEuclidean plane and a rational number r > 0, they intend tofind the set of centers C with the minimum cardinality, suchthat every point in P is covered by a disk of radius r that iscentered at one of the points in C. 3.Cluster Based Mobility Model There are different types of nodes in an ad-hoc networksthat are active in it. Each type has a movement pattern thatis represeted by mobility model in network simulators.Mobility model dictates to nodes how to move in their network environment. Many mobility models are proposed.Cluster Based Mobility Model [6, 7] has been proposed byauthors previously.In this model mobile nodes are grouped in several clustersas each cluster has several common characteristics such asspeed, pause time, activity area and finding path or destination method. Activity area is some areas that probability the nodes existence in those areas is more thanother places. This model can simulate environmentobstacles and pathways. It means this model constrains thenodes to move in predefined pathways and their signals areobstructed by obstacle environments. 4. Relation Between Connectivity and MobilityModel A simple way for solving the connectivity problem is to addstatic nodes in environment. In this way, if the mobile nodesof network leave a special area of network which causesnetwork partitioning, then these static nodes play the role of these nodes as their support. These special areas are some points of network terrain where are more sparse than other  points, therefore probability of partitioning in these points ismore than other points. These points are called critical points.This suggested solution has some problems, including toomany adding static nodes in network first puts the nature of ad hoc network under question and second it is very costly.But we need limited number of static nodes in ad-hocnetwork. These limited static nodes just are for shareinternet, intranet or file server and so on.But the question is how the mobility model of network nodes can be analyzed to find the critical points of network.To answer this question, a realistic mobility model can beused. This is because a realistic mobility model determinesthe realistic movement pattern of nodes and environmentobstacles, hence by analyzing such model the position of thecritical points can be located for adding static nodes. Itmeans, if we predict that how the nodes move in the terrainand have information about environment obstacle, we candetermine which points of the terrain can cause to partitioning of the networks. 5.Adding Static Nodes for ImprovingConnectivity Adding static nodes should be in places where leads to themaximum of connectivity and should has minimum cost.This cost includes deployment cost and static node cost. Buthow can these points are found. The simplest way to solvethis problem is to evaluate all the possible points in order todetermine the best points for static node position. Suchmethod has two problems.1.   Evaluating all points by consideration twoobjectives is a NP-Complete problem.2.   Evaluating each point is very time consuming. It is because computer simulation should be done toevaluate each solution.Therefore first the problem 1 must be proven and then asolution must be found to solve it with consideration to the problem 2. 5.1 NP-Completeness Proof  To prove that a problem is NP-Complete, it can be modeledto a known NP-Complete problem. 0-1 knapsack problem isused for this goal. In knapsack problem, there are n kinds of items, 1 through n . Each kind of item i has a value v i and aweight w i . It usually is assumed that all values and weightsare nonnegative. The maximum weight that can be carriedin the bag is W. There are several types of knapsack  problems which some of them such as fractional knapsack are solvable. But there is no polynomial solution for 0-1knapsack [8]. This problem can be formulated as a follow.  Maximize ∑ = niii  xv 1   (1)   IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011ISSN (Online): 1694-0814www.IJCSI.org177  Subject to W  xw niii < ∑ = 1  , }1,0{ ∈ i  x   (2)   As it is mentioned, the problem is selecting k points from n points so that each of them has two objectives for selection,deployment cost (c i ) and coverage efficiency (e i ). We wantto maximize connectivity but the cost increases byincreasing number of the static nodes. Hence the maximumcost for adding the static nodes must be less than W.Therefore this problem can be formulated as 0-1 knapsack if e i is considered as v i and w i as c i . 5.2 Proposed Algorithm Based on Mobility Model As it is proven, finding best points based on two mentionedobjectives is a NP-complete problem. Hence approximatealgorithms are suitable for such problems. Each approximation algorithm has a routine to evaluate eachsolution. But as it is mentioned, evaluating each solution is atime-consuming task due of simulation way. Hence someheuristics is needed to avoid simulation for evaluation.Therefore mobility model can be analyzed to find theseheuristics.Considering the mentioned mobility model, we realized thatdifferent node causes different mobility features. One of these features is nodes activity area. The existence of staticnodes in these areas can be very defective because themobile nodes in those areas are active and there is no needfor static nodes. Therefore these areas can be deleted fromthe areas permitted for placing the static nodes.On the other hand, obstacles prevent node signals from passing. Thus if a static node is located near an obstacle, itobstruct the great part of the node signal and this will prevent the node adding from producing a good result. Inother words the area around the obstacles can be deletedfrom the permitted for placing the static nodes.This paper presents two approximation algorithm for finding these points, genetic algorithms and fish swarmalgorithm. Both of them use mentioned heuristic for evaluation of a solution. 6. Genetic Algorithm and Finding Static NodesPlaces Genetic algorithm [9] can be used to find the best place for the static nodes by considering the building location andnode activity area. In this algorithm, the geographic pointsrelated to node activity area and buildings are certain fromthe beginning and search the whole terrain to find the pointsfor static nodes. 6.1 Problem Encoding As mentioned earlier the main problem is finding the placeof static nodes. Therefore each chromosome is a sequenceof 2D coordination of static nodes. Each gene is made up a point with horizontal and vertical axis. Number of thesegenes equals to number of required static points. 6.2 Designing Fitness Function Voronoi Diagram [10] does evaluation task for everysolution or chromosome. First coordination of obstacle andclusters activity areas are added to each solution which isallocation of static point’s coordination. The result is givento computation procedure of Voronoi diagram. Procedurecreates diagram then cells coordination of diagram arecalculated. Cells coordination is given to another procedureand its area value is calculated with triangulation method.Area difference of these cells is evaluation parameter. Theless the area differences cause to the better the solution.Since the operations mentioned above including creatingVoronoi diagram, extracting cells, and computing them have been done with standard methods which have been used atdifferent uses in different research [11], therefore it does notseem necessary to explain them in details again. 6.3 Proposed Algorithm The proposed genetic algorithm for finding the best order of static nodes is as follows:1)   Initial population is randomly selected from problemsolution space. About 50 chromosomes are producedrandomly. For each chromosome several coordinationof static point are produced randomly.2)   The generation operations are applied on the populationwhich is evaluated by fitness function.3)   Elitism: 10 percent out of whole chromosome with the best fitness remain for the next generation. This causeschromosome with appropriate fitness no to be destroyedaccidentally.4)   Crossover: we use standard methods such as divisionfrom one point in our algorithm. The amount of combination operator contribution to in constructingnext generation is considered 0.8.5)   Mutation: the mutation operator discover newchromosome in genetic algorithm. In this suggestedalgorithm the mutation operator is applied in a random point with the small probability p m in order to add newchromosome to the new population.6)   The new population created by the operators above isreevaluated by fitness function.7)   The condition for the algorithm stopping is evaluated. If the condition is not met, the algorithm is transferred tostep 2 again. In this implementation the algorithmrepetitions to 200 generations with the same bestchromosome have been considered. It means if the bestchromosome does not change for 200 generation,algorithm stop and best solution is selected. IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011ISSN (Online): 1694-0814www.IJCSI.org178  7. An Artificial Fish Swarm Algorithm forFinding Statick Nodes Positions Artificial Fish Swarm Intelligence Algorithm (AFSA) [12]is a swarm intelligence optimization algorithm. Fish usuallystay in the place with a lot of food, so this algorithmsimulates the behaviors of fish based on this characteristic tofind the global optimum by optimizing local optimum.Below code describes how this algorithm works.To describe this code, some definitions must be presented.These definitions are described as follow: •   AF : each Artificial Fish is considered asX=(n,s 1 ,s 2 ,s 3 ,….,s n ) that s i is optimizing variable.In our positioning problem x i is considered as astatic node position of the terrain which contain(x,y) coordination. Number of the static nodes is n. •   Distance : distance between two fishes is indicatedas d ij =||X i -X  j ||. To calculate it, a EuclideanMinimum Spanning Tree is used. It meansEuclidean minimum spanning trees for X i and X  j are calculated. Each x i as a static node position,coordination of centers of activity area andcoordination of centers of obstacles are assumed asvertices of a complete graph. In next step, spanningtree of this graph is calculated. Then total weightsof both trees are calculated. Difference betweentotal weight of tree of X i and X  j is considered asdistance between X i and X  j or d ij.   •   Visual : Visual   is the visual distance. Maximum of transmission range of each static node (r  s ) isassumed as Visual in this problem. •   Step : step is maximum step length of the fish. 2*r  s  is assumed as Step. 7.1 AF Initialization In initialization step, population of AFs is formed. As it ismentioned, there is the cost constraint for number of thestatic points. W is assumed as maximum of budget for allstatic points. So this step generates random population thatcontain AFs which number of their variable is betweenw/c min and w/c max . c min and c max are minimum andmaximum cost of adding a static point to the terrain. Thiscost is variable because of variable deployment cost. So togenerate each AF, n is a random number between w/c min  and w/c max and each s i , i={1,n} is generated randomly, iex i ,y i take a random number between 0 and maximum of terrain size. 7.2 AF Fitness (Food Consistency) Evaluation each AF must be capable to consider both costand connectivity efficiency objective for evaluation an AF.For measuring connectivity efficiency, the mentionedmobility model heuristics are used. Therefore the network terrain should be divided into homogeneous cells with highconnectivity. These cells should either include an activityarea of cluster or have static node which guarantees their connectivity. Hence these cells can guarantee theconnectivity of all parts of the terrain.To do this Voronoi diagram can be used. In the simplestcase, there are given a set of points S  in the plane, which arethe Voronoi sites. Each site  s has a Voronoi cell, V(s)  consisting of all points closer to  s than to any other site.Input points for Voronoi diagram are the building center, thenode activity area center and static nodes positions that areextracted from the AF. If these points cause to make theVoronoi diagram with homogeneous cells, we can said thatwe distribute static nodes properly. Homogeneous cells arethose cells that have same area and can cover theenvironment similarly. Therefore deference between areasof these cells is considered as connectivity efficiencyobjective.Cost objective of each AF includes cost of static node anddeployment cost of them that both of them must beconsidered. Equation 3,4 calculate cost objective.C= ∑ = + nidi si cc 1 (3)CF=C+D (4)   c si is cost of ith static node and c di is deployment cost of ithstatic node which is extracted from a labeled map thatindicates deployment cost of each region. FC is objectivefunction of the AF or food consistence of it. 7.3 AF Behaviors Four basic behaviors of AF are defined as follows: (1).AF_Prey: generally the fish perceives the concentration of food in water to determine the movement by vision or senseand then chooses the tendency. (2). AF_Swarm: The fishwill assemble in groups naturally in the moving process,which is a kind of living habits. This behavior is done if colony is not so congested. (3). AF_Follow: In the moving process of the fish swarm, when a single fish or several onesfind food, the neighborhood partners will trail and reach thefood quickly. (4). AF_Move: Fish swim randomly in water;in fact, they are seeking food or companions in larger ranges. IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011ISSN (Online): 1694-0814www.IJCSI.org179  To explain this behavior briefly, below pseudo codes are presented.AF Praying: X i is current state of the AF and X  j is a state invisual of the AF that is generated randomly (equation 5). If FC i <FC  j then AF moves toward Xj (equation 6). This process is done several times and if AF could not find a better state in its visual, a random state is selected (equation7).   X  j = X i + Random(Visual/2) (5)s i|next k  = s ik  + Random(Step) |||| i jik  jk   X  X  s s −− (6)s i|next k  = s ik  + Random(Step) (7)s ik  is kth variable in X i and s  jk  -s ik  is Euclidean distance between s  jk  and s ik  .AF Swarm: FCc is average FC of a swarm in visual of theAF. AF move toward center of the swarm (equation 8), if FCc/n f  > δ FC i , it means the swarm is not so crowded. δ iscrowd factor which is between 0 and 1. Otherwise the AFselects praying behavior. X i|next = X ik  + Random(Step) |||| icik ck   X  X  s s −− (8) AF Following: In following behavior, AF finds AF withmaximum of FC in its vision. Then if around it is not socrowded (FC R max R / n R f  R > δ FC R i R ) moves toward it (equation 9). 2B X R i|nextk  R = X R ik  R + Random(Step) |||| maxmax iik k   X  X  X  X  −− (9)AF Evaluation (Choosing Bahavior):For next behavior of the AF, all mentioned behaviors are evaluated and a behavior with best result is selected. Best result is a behavior with minimum FC. 8. Simulation The main purpose of any simulation done is usually toevaluate the suggested method and to compare it with the previous methods. However the presented method in thisarticle is not comparable with the previous ones. Becausenone of them have not considered the connectivity issue based on a realistic mobility model.In order to insure the accuracy of the suggested method, theauthors of this paper have considered a sample terrain withscale 0.1 of the real terrain (which will be discussed later).We divided that terrain in to 100 points in grid form. Thenwe evaluated the location of static points on these points bysimulation, the results of which were compared with themethod independent from simulation. The results indicatedthat the suggested method independent from simulationleads to similar results when compared with simulation of all possible points. However as for time, simulation of  possible points is much more time-consuming even withscale 0.1 and with one static node. It is because byincreasing the number of static nodes their places getdependent on each other and the number of simulationincreases exponentially. 8.1 Simulation Metrics To evaluate affect a new method on network performance,two aspects were considered:1. To understand the network topology characteristics thatinfluenced by our method, we evaluate the followingmetrics: Node Density: The average number of neighbors per node.Average Broken Links: The average number of broken linksalong the simulation.2. To evaluate effect of our method on routing protocol parameter we evaluate following parameters:Data Packet Reception: The number of data packetsreceived at their intended destinations.Control Packet Overhead: The number of network-layer control packet transmissions.It seems necessary to mentioned we used AODV routing protocol [13] in our simulation. Fig. 1 Simulation terrain 8.2 Simulation Parameters Figure1 shows the selected network terrain for evaluationthe mobility model. It is assumed that there are two clustersof nodes with different activity area. In this figure thedifferent activity area of two clusters are shown. Table1indicate the simulation parameters. You can see simulator software, simulation terrain size, node transmission rang,signal propagation model, MAC layer protocol, bandwidth,speed range, pause time range, number of nodesrespectively in this table. IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011ISSN (Online): 1694-0814www.IJCSI.org180