[ieee 2007 international conference on intelligent and advanced systems (icias) - kuala lumpur...

International Conference on Intelligent and Advanced Systems 2007

QOS of Efficient GA-EMAN Routing MethodFor Future Mobile Tele-Emergency System

D. v. Viswacheda M. s. Arifianto M. Y.Hamid L. Barukang

School ofEngineering and Information TechnologyUniversiti Malaysia Sabah, Locked Bag No. 2073, 88999 Kota Kinabalu, Sabah, Malaysia

Tel: +60-8-832-0000 ext. 3569, Fax: +60-88-320348,E-mail: [email protected]@[email protected]@ums.edu.my

Abstract-This paper discusses the routing optimization formobile ad hoc network (MANET), using enhanced geneticalgorithm (GA). In MANET routing, the mobile wireless nodessufTer signal interference due to the existence of the otheractive nodes. For Wireless Telemedicine application, thereexists a dense group of active nodes inside a small area inMANET, and scattered active nodes surrounding the area. Thesmall and densely populated mobile nodes are at the center ofthe disaster area, in which less interference and less traffic ispreferred. To alleviate the interference and traffic problem,there should be a method to route the traffic from and to thegateway without presenting extra load to the area, whilemaintaining the quality of the links from the gateway to thedestinations within an acceptable level. Our approach .isthrough gateway routing technique using GA, incorporatedinto MANET, hence the name GA Enhanced Mobile Ad HocNetwork (GA-EMAN). The result of our simulation ingateway routing of mobile nodes over GA-EMAN is presented.The results shows that the best alternative routes given by GAEMAN can replace the conventional MANET routing protocol.

Keywords- Mobile Ad Hoc Network (MANET), GeneticAlgorithm (GA), GA-Enhanced MANET (GA-EMAN),Routing Optimization, Wireless Mobile Node, Voice over IP(VoIP).

I. INTRODUCTION

Telemedicine is defined as the delivery of medical healthcare and medical expertise using a combination oftelecommunications technologies. Telemedicine systemscan support applications ranging from videoconference toprovide diagnostics, high quality image and still-image, andmedical database record.

The Tele-emergency project in University MalaysiaSabah proposed tele-emergency units as mobiletelemedicine units based on three technologies, Le. MIPv6,MANET, and WLAN. The integration of the technologieswill produce a highly capable system with the ability to berapidly deployed to support medical services. Thediscussions of the integration of MANET with Mobile IPare available in [1 - 7].

In this paper, we are concerned about the routingalgorithm for the gateway of a WLAN based MANET.Here, the situation where all telemedicine units areconnected to an emergency response center through agateway needs an efficient routing algorithm. For theoptimization of the routing method, we applied geneticalgorithm (GA) to MANET and the outcome is GAEnhanced MANET (GA-EMAN).

378~

Before continuing with the problem and the GA basedenhancement, brief reviews on MANET and GA arepresented.

II. MOBILE AD HOC NETWORK (MANET)

Ad hoc literally means "formed or used fur specific orimmediate problems or needs". Thus, MANET means amobile network which can be formed or used for specific orimmediate problems or needs.

Mobile nodes in a MANET communicate to each otherwithout base station, without the aid of any centralizedadministration, hence it is also known as aninfrastructureless wireless network. MANET employs itsmobile nodes as a part of the networking system. Each nodein MANET can act as an intermediate node, Le. as a relay toforward packets of data [8] and do routing functionality. InMANET, mobile nodes are free to move arbitrarily. It leadsto an important property of MANET which is dynamictopology.

MANET routing protocols can be classified into demanddriven routing protocols and table-driven routing protocols.Demand-driven protocols create routes only when thesource node initiates a route discovery process. Examples ofdemand-driven protocols are Ad Hoc On-Demand DistanceVector (AODV) [9] and Dynamic Source Routing (DSR)[10]. Table-driven protocols attempt to maintain consistent,up to date routing information in routing tables on everynode. Examples of table-driven protocols are DestinationSequenced Distance Vector (DSDV) [11] and OptimizedLink State Routing (OLSR) [12].

III. GENETIC ALGORITHM (GA)

The genetic algorithm (GA) is an optimization andsearching technique based on the principles of genetics andnatural selection. A GA allows a population composed ofmany individuals to evolve under specified selection rules toa state that maximizes the "fitness" (Le., minimizes the costfunction) [13]. The method was developed by John Holland[14] over the course of the 19608 and 1970s and fmallypopularized by one of his students, David Goldberg, whowas able to solve a difficult problem involving the cmtrol ofgas-pipeline transmission for his dissertation [15]. He wasthe fIrst to develop a theoretical basis for GAs through hisschema theorem. Since then, many versions of evolutionaryprogramming have been tried with varying degrees ofsuccess.

1-4244-1355-9/07/$25.00 @2007 IEEE


Some of the advantages ofa GA include that it

• Optimizes the performance with continuous or discretevariables,

• Doesn't require derivative information,

• Simultaneously searches from a wide sampling of the costsurface,

• Works with a large number of variables,

• Is perfectly applicable for parallel computers,

• Optimizes variables with extremely complex cost surfaces(they canjump out ofa local minimum),

• Provides a list of optimum variables, not just a singlesolution,

• May encode the variables so that the optimization is donewith the encoded variables, and

• Works with numerically generated data, experimentaldata, or analytical functions

IV. ApPROACH AND METHODS

A. Density Problem in a MANET

During an emergency response in a disaster area, therewill be a dense group of medical units inside the center ofthe area, and sparsely scattered units surrounding the area.For the MANET based wireless telemedicine application,there should be a way to prevent the densely populated nodearea in the center of the disaster area from receiving toomuch interference and traffic load. The problem isillustrated in Fig. 1.

As a starting step, we consider the situation where thetraffic mostly comes from the communications between thenodes and the emergency response center. Hence, in thiscase the focus should be on the gateway routing. Here, thetraffic from and to the gateway should go through withoutoverloading the dense area, while maintaining the quality ofthe links from the gateway to the destinations within anacceptable level.

GA can handle the problem efficiently. The fITst thing tolook is the cost function to be optimized in the GA-EMAN.

Wireless Link

Alternative VVireless Link

Mobile Node

"" ,'QI)

IIIIII

-------------------~-----------~Fig. 1. MANET density in typical tele-emergency situation

B. Cost Function

We consider two costs that create the overall costfunction. Both terms basically are functions of the distancesbetween nodes and the routes being considered to link the

gateway to the other nodes.The fIrst one to be taken into account is the mean of

signal to interference ratio along the path from gateway tothe destination. Since we cannot exactly measure the signalto interference ratio on each nodes, we replace it with themeasurable one, Le. signal to interference noise ratio(SINR), and we assume that the background noise poweraffecting all nodes are equal. Here, we put negative sign onthe mean SINR so that the lower the cost means the higherthe SINR and the lower density area that the path goesthrough.

The fIrst term is represented as1 N

C1 =--LSINR" (1)N 11=1

where SINRn is the SINR (in ratio scale, not dB scale) at then-th intermediate node and N is the number of intermediatenodes. The maximum number of hops is 4, while therecannot be less than 1 hop, giving the range ofN as 0 :5 N :53. We assume that the maximum SNR in each node is 30dB, which means that when there is no interference themaximum value of SINR is 1000 in each node, whichprovides the minimum value as -1000. Whenever a hop isnot possible within an evaluated path, 0 will be directlygiven to C1 without checking the next hops.

The second term is the total time needed by one packetfrom the gateway to arrive at the destination. This total timeincludes packet transmission time t" delay caused bypropagation td, and mean packet processing time tp in theintermediate nodes.

Transmission time between hop is the time needed totransmit one packet.

, Ptt = R (2)

where P is the packet size and R is the data transmissionrate.

Propagation delay per hop is:d

(d=- (3)c

where d is the hop distance and c is the speed of light. Forthe processing time in one node, we consider an MlMIlqueue, where we have packets arriving in the form ofPoisson process, exponentially distributed service time atthe nodes, and large buffer for the queuing packets. Thearrival rate in one node is the sum of the rate of incomingpackets from all nearby nodes using the node of interest astheir router. We assume the same mean service time (Le.mean time for packet handling and forwarding) for allnodes.

Let At be the packet arrival rate coming from the j-thneighboring nodes into the node of interest. The total arrivalrate is

J

,1,= LA,j (4)j=1

If lip. is the mean service time and the utilization factorp = )jJ.l then the mean waiting time in the buffer is

W = P / J-l (5)I-p

The mean time spent in the node T is the sum of the meanservice time 1/11 and the mean waiting time in the buffer W.

--- 379


(7)

(8)

(6)

v. SIMULATIONS

A. Simulation Setup

In the simulations we generated 24 nodes randomly in a500 m x 500 m area. The simulation parameters arepresented in Table 1.

One node is designated as the gateway where most trafficis coming from or going to the network. The simulationbegins with no traffic being transmitted, and all nodes areoff. Afterwards, one connection is considered, where thegateway send packets to one of the other node, GA checksthe best permutation of intermediate nodes for creating thepath from gateway to the destination. Next, while the fIrstpath is maintained, gateway sends packets to another node.GA checks the best route for this second one whileconsidering the fIrst connection. It repeats for the next one.GA checks the best route for the third connection whileconsidering that there exist two other paths. In thesimulation, it continues on until we have 12 connections.

In the simulations, for comparison we have checked theresults with the assumption of using another algorithm forthe same MANET. Here we have assumed AODV [9] wherethe path with the shortest delay is always chosen, we haveapplied only the packet time without considering the routerequest and reply processes.The packet size being used is given in Table 2. It wasassumed that the packets are VOIP packets using G.723.1codec. The packet overhead consists of the 40 bytesminimum overhead (20 bytes IP header, 8 bytes UOPheader, 12 bytes RTP header).

means we are using three intermediate nodes, or four hopsfrom gateway 1 to destination D, Le. 1-2, 2-3, 3-20, 20-0. (33 20) means we are using two intermediate nodes (3 20), orthree hops, Le. 1-3, 3-20, 20-0. (2 3 2) is not acceptable.

The flow and parameters for the modified permutativeGA is shown in Fig. 2.

Fig. 2. Pennutative GA Flow Chart

Find Cost for EachChromosome

Cost Functions: CNumber of Genes in a Chromosome: N=3

Number of Initial Population: P=20Number of Generations: G=40

Mutation Rate: R=O.2

Generate InitialPopulation

1/,uT=--

I-p

The mean packet processing time tp is no other than T.

t = 1/.up 1-p

The equation for the second term is as follows:H

C2 = Ltth +t,." +tphh=l

where the subscript h represents the h-th hop in the link andH is the number of hop, 1 S H S 4. All terms inside are inmsec.

We consider that if one packet needs more than 1 secondto arrive at the destination then the path is not viable anddirectly labeled as unfit without the need of measuring thefIrst term.

For the combination ofthe cost function, we have

C = W1C1 + wzCz (9)

where WI and Wz are the weights given to CI and Czrespectively. Here, we use unequal weight, 80% for the fIrstterm and 20% for the second one. Considering themaximum mean SINR as 1000, the maximum total delay as1000 msec, and proportional weights, we have:

0.8 8 10-4 d 0.2 4WI =--= X an Wz =--=2x10- (10)

1000 1000which gives -0.8 :S C :S 0.2.

The cost function of one link from gateway to a particularnode depends on the route taken, i.e. the intermediate nodeschosen and their order in the path. Thus, the variant of GAapplicable for the GA-EMAN is Permutative GA.

C. Permutative GA

This paper describes a method for optimizing gatewayrouting using a permutative genetic algorithm [16 - 21]. Ininitial experiments, the population of permutationchromosomes Pg is initialized randomly by generatingdifferent random permutations of 1 to N, where P is knownas the population size. We worked on small networkbecause it was observed in a study that random initializationworks sufficiently only for small/middle scale networks(number of nodes~40) [22]. As for the larger network,random initialization appears to exhibit inefficiency inobtaining optimum solution (Le. the lower bound of framelength) [22].

Based on the position of nodes, the on-off status of thetransmitter, and the traffic they are relying, we may countthe cost functions at the gateway if the information is beingreported to the gateway. It is not necessary to know thenodes positions, but the SINR reported by the nodes areaffected by the positions.

In this case, the chromosomes with which the costfunction is measured can be simplified into a permutationproblem. The ordering of nodes number randomly picked Nat a time from a pool of all nodes in the network builds thecost function.

The permutative GA is not purely permutative, since wehave to be flexible to avoid having variations of number ofgenes. There should not be any reappearance of nodesexcept for direct repetition in which we considered as usingless number of intermediate nodes. For example, (2 3 20)

380 ---


end to end delay for all connecting nodes as shown in Fig. 5and Fig. 6 respectively. The result is as expected, since GAEMAN may introduce more hops or longer links, then the

Fig. 3. Number ofGeneration vs Cost for the 5th connections

TABLE 1SIMULATION PARAMETERS

Parameter Value

Number ofnodes 24

Number ofgateways 1

Transmitter power 15dBm

Receiver sensitivity -80dBm

Antenna gain 5.5dBi

Cable and Connection Losses -O.7dB

Losses due to Fresnel zone and diffraction -20dB

Wireless data rate 2 Mbps

MobilitylMovement Fixed

Environment size 0.5km x 0.5km

Number of connections 1-12

Number of initial population in GA 20

Mutation rate in GA 0.2

5 10 15 20 25generation

30 35 40

TABLE 2G.723.1 VOIPPACKET

Parameter Values

Packet Over Head 40 bytes

Frame Size 24 bytes

Frame Duration 30 ms

Frame per Packet 1 frames/packet

Packet Rate 33.33 packets/sec

Payload Size 24 bytes

Payload Bit Rate 6.4 kbps

Overall Packet size 64 bytes

Overall Bit Rate 17.07 kbps5 678

The ~th Connection10 11 12

201816

Fig. 4. Costs Comparisons GA Gateway routing vs AODVGateway Routing for The n-th Connection, given that

(n-l) connections had been previously established

Fig. S. Packet Delivery Fraction Comparison, AODV vs. GA-EMAN

40

30I---_~__--J..-_---I__--L-__-'--_---L______L...__ ___..J

4 10 12 14Number of Connections

50~"'''''''''''''''''''''' ; .

80

B. Results andDiscussions

Since in MANET the topology might change in a shortperiod of time, it is preferred to have a small number ofgenerations as possible, i.e. fast convergence is desirable.

Fig. 3 shows the convergence of the GA being used in thesimulation for the fifth connection. After 27 generations theGA has achieved the minimum cost function. We considerthis as acceptable since the GA based calculation is only onone node, not on all nodes. However, if the number ofnodesis large this will not be acceptable any more.

In Fig. 4, we plot the comparisons of the measured GAbased gateway routing minimum cost functions with the costfunction of the path chosen by AODV based system. Weconfmn that in our simulation environment, the shortestdelay path given by AODV is occupying the area with moredensity compared to the GA based gateway routing, becausethe cost function of the AODV path is higher than the GAbased cost, which is optimized to minimum value. Hence, itachieves our goal to avoid dense area inMANET.

The QoS tested are packet delivery fraction and average

~ 381


0.71--r-----,---,------r-----r----r-~==:I====~

0.6

! 0.5

i;'Qio 0.4"0c:W,g"0.n 0.3 .

&

i4( 0.2

0.1

o4~---:-----l...---1..1..-0--.....L12---1L-4--1-1-6---..118-----120

Number of Comections

Fig. 6. Average End To End Delay Comparison,AODV vs. GA-EMAN

EMAN may intrduce measured QoS of GA-EMAN is lessthan that ofAODV. However the differences are minor. Thisis the unavoidable trade-off from having less traffic in thecenter of the emergency region.

VI. CONCLUSIONS AND FUTURE WORKS

We have shown that GA converges relatively fast forchecking routing in a MANET. The purpose of this study,for which we would like to avoid densely populated area inMANET, has been achieved, since if we are using thebenchmarking MANET routing algorithm (AODV), we findthat it is taking the dense route. The differences of QoS inGA-EMAN and AODV are minor compared to the positiveeffect that GA-EMAN alleviates the routing burden at thedensely populated center of the disaster area.

For the future work, fmding the limits ofnumber ofnodesthat is still computationally acceptable to be handled by GAbased gateway routing is recommended.

REFERENCES

[1] D. V. Viswacheda, L. Barukang, M. Y. Hamid, and M. S. Arifianto,"Perfonnance Evaluation of Mobile Ad Hoc Network BasedCommunications for Future Mobile Tele-Emergency System",Journal ofApplied Sciences, vol. 7, no. 15, pp. 2111-2119,2007.

[2] D. V. Viswacheda, L. P. Y. Voon, M. S. Arifianto, and L. Barukang,"The Mobile Tele-Emergency System: Issues and Perspectives",Caledonian Journal ofEngineering, vol. 2, no. 2, pp. 23-33, 2006.

[3] E. M. Husni, Y. Heryadi, and M. S. Arifianto, "The Smart TeleEmergency Project: A Mobile Telemedicine Unit Based On MobileIPv6 and Mobile Ad Hoc Network for Sabah Areas", in Proceedingsof UiTM 2004 RF and Microwave Conference (RFM 2004), 5 - 6October 2004.

[4] E. M. Husni, Y. Heryadi, W. T. H. Woon, M. S. Arifianto, D. V.Viswacheda, L. Barukang, "Mobile Ad Hoc Network and Mobile IP

382 ---

for Future Mobile Telemedicine System", Proceedings of the thirdIEEE and IFIP International Conference on Wireless andOpticalCommunications Networks(WOCN 2006), Bangalore, India,April 11-13, 2006.

[5] L. Lamont, M. Wang, L. Villasenor, T. Randhawa, and R. Hardy,"Integrating WLANs & MANETs to the 1Pv6 based Internet", inProc. IEEE International Coriference on Communications, ICC '03.Anchorage, vol. 2: 1090 -1095, 11-15 May 2003.

[6] L. Lamont, M. Wang, L. Villasenor, T. Randhawa, R. Hardy, and P.McConnell, "An IPv6 and OLSR based Architecture for IntegratingWLANs & MANET to The Internet", in Proc. The Fifth InternationalSymposium on Wireless Personal Multimedia Communications,WPMC 2002. Honolulu" voL 2: 816-820,27-30 October, 2002.

[7] Y.C. Tseng, C.C. Shen, and W. T. Chen, "Integrating Mobile lP withAd Hoc Networks", IEEE Computer, issue 5, vol. 36: 48-55, May2003.

[8] C. K. Toh, "Ad Hoc Mobile Wireless Networks: Protocols andSystems", Upper Saddle River: NJ, Prentice Hall, 2002.

[9] C. E. Perkins, E. M. Royer, "Ad Hoc On-Demand Distance VectorRouting", IEEE Workshop on Mobile Computing Systems andApplications: 90-100, 1999.

[10] D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad HocWireless Networks", in Mobile Computing, T. Imielinski and H.Korth, Ed. Kluwer Academic Publishers, pp. 153-181, 1996.

[11] C. E. Perkins and P. Bhagwat, " Highly dynamic DestinationSequenced Distance-Vector routing (DSDV) for mobile computers",in Proc. of the ACM SIGCOMM '94 Conjerence on CommunicationArchitecture, Protocols and Applications. London, pp. 234-244,August 31-September 2 1994.

[12] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum and L.Viennot, "Optimized Link State Routing Protocol for Ad HocNetworks," in Proc. IEEE International Multi Topic Coriference,INMIC 2001. Lahore: 62-68,28-30 December 2001.

[13] Randy. H. Haupt, Sue Ellen Haupt, "Practical Genetic Algorithms",John Wiley&Sons, 2004..

[14] John. H. Holland, "Adaptation in Natural and Artificial systems",University ofMichigan Press, 1975.

[15] David. E. Goldberg, "Genetic Algorithm in Search, Optimization &machine Learning", Addison Wesley, reading MA, 1989.

[16] Z. Michalewicz, "Genetic Algorithms + Data Strnctures = Evolutionprograms", NY: Springer-Verlag, 1992.

[17] D. Knjazew, "OmeGA: A Competent Genetic Algorithm for SolvingPennutation and Scheduling Problems: Genetic Algorithms andEvolutionary Computation", Vo1.6. Norwell, MA: Kluwer Academic,2002.

[18] C. Bierwirth, "A generalized permutation approach to job shopscheduling with genetic algorithms", OR Spectrum, 17, pp. 87-92,1995.

[19] I. Oliver, D. Smith, J. Holland, "A study of permutation crossoveroperators on the traveling salesman problem", Proc of 2nd Int Confon Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NewJersey, pp. 224-230, 1987.

[20] Christian Bierwirth, Dirk C. Mattfeld, Herbert Kopfer, "OnPennutation Representations for Scheduling Problems", Proceedingsofthe 4th International Coriference on Parallel Problem SolvingfromNature, pp. 310-318, September 22-26, 1996.

[21] William H. Hsu, Haipeng Guo, B. Benjamin A. Perry,Julie Stilson, "APennutation Genetic Algorithm for Variable Ordering in LearningBayesian Networks from Data", Laboratory for Knowledge Discoveryin Databases, Kansas State University, 234 Nichols Hall, Manhattan,KS 66506.

[22] X. Wu, B.S. Sharif: O.R. Hinton and C.C. Tsimenidis, "Solvingoptimum TDMA broadcast scheduling in mobile ad hoc networks: acompetent pennutation genetic algorithm approach", in lEE Proc.Commun., vol. 152, no. 6, December 2005.

[ieee 2007 international conference on intelligent and advanced systems (icias) - kuala lumpur...

Documents