1

Differential Evolution based Routing Algorithm for

i i i i i

IoT i

Shreyas iJ, iHemant iKamat, iTejaswini iT, iSudarshan iPuranika, iVinayaka iHegde, iDilip iKumar iS
iM iDept. iof iComputer iScience iand iEngineering, iUniversity iVisvesvaraya iCollege iof
iEngineering, iBangalore, iIndia

e-mail: i([email protected]).
Abstract—The iInternet iof iThings i(IoT) inotion
ienables iembedded idevices ito iconnect iand ishare idata
ithrough iIP i i ior iweb. iIoT ibased iWireless iMesh
iNetworks i(WMN) iis iseverely iaffected iby inetwork
itraffic icaused iby ienormous idata igeneration iby ilarge
inumber iof iusers. iGenetic iAl- igorithms i(GA), idue ito
itheir iremarkable igenerality iand iversatality ihave igained
imuch iattention ias ikey ichallenges ito iovercome iin iIoT
ibased iWMN iwith iincrease iin iwireless iservice
iperformance. iHence, iwe ihave iproposed iGA ibased
imulti-objective idifferential ievolution i(MODE) iapproach
ifor ifinding ithe ioptimal iroute ifrom ia igiven isource ito i a
idestination iwith imultiple iand icompeting iobjectives.
iMODE ialgorithm ireduces iend-to-end idelay iand
imaximizes ipacket idelivery iratio iand iit imainly ifocuses
ion iobtaining iPareto- ioptimal isolutions. iFor imaintaining
igood idiversity, ithe iconcept iof iweight imapping
icrossover i(WMX) ibased irecom- ibination iand idynamic
icrowding idistances iare iimplemented iin ithe iMODE
ialgorithm. iMODE ihas ibeen iimplemented iand isimulated
ion iMATLAB iand iit iis iobserved ithat ithe ipro- iposed
ischeme iperformed isuperior ito ithe iexisting iclustering
ibased irouting ialgorithm ipresent iin ithe icurrent
iliterature ifor isimilar ipurposes. iThe iresults idemonstrate
ithat ithe iMODE ihas i14.6% imore i iPacket i iDelivery i
iRatio, i i20% i iless iend-to-end idelay iand ialso igenerates
iwell idistributed iPareto-optimal isolutions iover ialgorithm
ipresent iin ithe icurrent i literature.

I INTRODUCTION
Internet iof iThings i(IoT) iis ian iexpanding itechnology
iwhich iis iprogressively igrowing iinto idifferent ifields
isuch ias ismart ie-health iservices, ismart ihomes, ismart
icities, i ietc. iThis ifield ihas irecently idrawn iconsiderable
iattention iin ithe idomain iof iresearch i[1]. iIn ithe iIoT
ienvironment, imany iof ithe iobjects iwhich iare
iconnected ito ia inetwork ican iinteract iwith ieach iother
iand ico-operate iwith itheir i ineighbors ito ireach ia
icommon igoal. iIn iIoT, iWireless iMesh iNetworks
i(WMN) iis ian iarea iof iresearch iproviding ifastest iend ito
iend iconnectivity iamong itwo iphysical iobjects
iconnected ito ia inetwork. iAlthough ithe ifield iof iIoT iand
iWMN icomes iwith icertain ichallenges iwhich imust i be

Shreyas iJ:
 2

addressed iwhen ione idecides ito iexplore ithis ifield.

iOne iof isuch i challenges i we i come i across i is
i congestion.
Congestion iarises iwhen iseveral inetwork inodes
istart isending ipackets isimultaneously iat ithe ihigh irate
iof idata ithan ithe inetwork ican ihandle. iTypical ieffects
iof ithe icongestion iinclude iqueuing idelay, ipacket iloss
ior ithe iblocking iof inew iconnections. iCongestion
iincorporates i i i ia ideep iimpact ion ithe istandard iof i
iservice i iparameters iand ialso ithe ienergy iof isensing
ielement inodes i[2] i[3] i i i i iIn igeneral, itwo iimportant
itechniques iare iincorporated ito ialleviate icongestion iin
iIoT inetworks: itraffic iengineering iand itraffic icontrol.
iIn itraffic icontrol itechnique, ithe idata iflow irate iis
icontrolled iwhich iwill ibe ia idrawback ifor ithe itime
icritical iapplications, itraffic iengineering imethod iis
iwidely ipreferred iin iwhich ithrough ian ialternative
inon- icongested i path, i data i packets i will i be
i delivered.
In ithe ipast ifew idecades, iexperts iproposed imany
ischemes ithat ibalance ithe i idata i iflow i ion i irouting i
ipaths iin iWMNs. iA irouting imetric ithat iconsiders ia
ivariety iof iparameters iis ian iideal isolution ito iensure
iefficient irouting iamong iMSTAs iand irouters. iEven
ithough iWMNs iborrow irouting isolutions iof imobile
iad ihoc inetworks i(MANET) ito isatisfy ithe irouting
idemands, ithey iare inot ioptimized ifor iWMNs i[4].
iExisting irouting iprotocols idiscover ipaths iwith iaid iof
ithe ibroadcasting imethod. iIn iconsequence, inodes
iconsume imore ienergy, iwhile iincreasing ithe irate i iof
imessage icollisions idue ito inetwork icongestion. iThese
idrawbacks ihighlight ithe ineed ifor ispecifically idefined
irouting iprotocols. iIn iAODV irouting icontrol itraffic iis
ialarmingly ihigh idue ito iglobal iflooding imechansim.
iIn iaddition, ipure iAODV isuffers ifrom ilong isetup
ilatency, iwhich ihinders ithe iapplicability iof iAODV iin
ireal-time idata itransmission i[5].
A inumber iof irouting ialgorithms iare iproposed ito
ifacilitate iefficient idata irouting iin iWMN
ienvironment. iThe iclustering ibased irouting ialgorithm
iuses iselective ibroadcasting iwith iload ibalancing iand
iinference idelay iaware irouting ialgorithm. iBut
iefficient irouting itechniques ishould ibe idesigned ifor
iWMN iand ienusre ithat ithe idata ipackets ipropgate iin
ian ioptimal imanner iin iterms iof iseveral imetrics. iDue
ito ithe imultiple icriteria inature iof i the
 3

ipoint iof isignal. iRTT iperiodically ipings iits ineighbors

most ireal-world iproblems, ithe imulti-objective
iusing iunicast iprobe irequests. iHere, ia iprobe irequest iis ia
ievolution- iary ialgorithms(MOEA) iare ithe ibest ichoice
ispecial iframe isent i i by i a i client i station i requesting
ibecause iof iits ipopulation-based iapproach. iMulti-
i information i from i either i a
objective ioptimization iproblems iinvolve imultiple
iobjectives, iwhich ishould ibe ioptimized
isimultaneouosly iand iare ioften iin iconflict iwith ieach
iother. iIn imulti-objective ioptimization, ithere imay inot
iexist ia isolution ithat iis ithe ibest iwith irespect ito iall
iobjectives; iinstead, ithey iare iequally igood isolutions
iand i iit iis icalled iPareto-optimal i solutions.
In ithis ipaper, iwe ihave iproposed ian iextension iof
iDifferential iEvolution(DE) ifpr isolving imulti-objective
ioptimization iproblems. iDE ias ideveloped iby iStorn iand
iPrice i[6] iis ione iof ithe ibest ievolutionary ialgorithms,
iand ihas iproven ito ibe ipromising icandidate ito isolve
ireal-valued ioptimization iprobelms. iThe icomputational
ialgorithm iof iDE iis ivery isimple iand ieasy ito
iimplement, iwith ionly ifew iparameters irequired ito ibe
iset iby ia iuser. i iThe iobjective i i of ithis ipaper iis ito
isolve imulti-objective irouting iproblem iusing iMODE
ialgorithm. iWe iconsider iboth ipacket ideliv- iery
iratio(PDR) iand idelay isimultaneously ito idetermine ithe
i optimal i routing i for i wireless i mesh i network.
Our icontribution ito iliterature iis isummarized ibelow:
1. We iformulate ithe iproblem ias imulti-objective
ishort- iest ipath irouting ifor ithe imaximization iof
iPDR iand iminimization iof idelay.
2. We ipropose ia imulti-objective idifferential
ievolution i(MODE) ialgorithm ito ifind ia iPareto-
optimal isolution ito ithe iproblem iwhich iimproves
ithe iPDR iand ide- icreases ithe idelay. iThe
iredundancy ipath ican ibe ielim- iinated iusing
iweight imapping icrossover ialgorithm iand ithe
idiversity ican ibe iimproved iusing ithe idy- inamic
icrowding idistance imethod. iRelative iposition-
ibased i indexing i method i is i used i for i mutation
i phase.
3. Finally, iwe iperform iextensive ievaluation iof
iMODE iunder iseveral iscenarios. iWe idemonstrate
ithe ibene- ifits iof iproposed iapproach iusing
isimulation iexperi- iments.

II RELATED iWORKS
Congestion icontrol ialgorithms iplay ia ikey irole iin
idifferent iIoT iapplications. iThere ihave ibeen ia inumber
iof iworks i undertaken i to i detect i and i control i IoT
i congestion.
A. iAdya iet. ial. i[7], iproposed ia irouting imetric ibased
i ion iaverage imeasured iround itime itrip i(RTT). iIt iis ithe
ilength iof itime iit itakes ifor ia isignal ito ibe isent iplus ithe
ilength iof itime iit itakes ifor ian iacknowledgement iof
ithat isignal ito ibe ireceived. iThis itime i itherefore i
iconsists i of ithe ipropagation itimes ibetween ithe itwo
 4

ithat ifocuses ion iminimizing ithe iexisting iissues iof i

specific iaccess ipoint, ispecified iby iSSID, ior iall
inetwork. i iAlthough ithe iproposed ialgorithm ireduces
iaccess i ipoints iin ithe iarea, ispecified iwith ithe
iend-to-end idelay iand igives iconsideration ito iquality iof
ibroadcast iSSID. i iFinally iwhen iall ithe inodes iare
iservice, ireducing i the
ipinged iwith irequests, ithe ipath iwith ismaller iRTT iis
iselected ifor icommunications. iHowever, isince iRTT iis
iload isensitive, iit iperforms ipoorly ibecause iof
iinterference.
In ipaper iR. iDraves iet. ial. i[8] iproposed ia irouting
imetric icalled ibandwidth iadjusted iETX. iIt i simply
i multiplies ibandwidth iwith iETX ito ifix iload
i balancing i problem. iHowever, iincorrect icalculation
iof i ibandwidth i will i lead ito i chosing i an
i inappropriate i link. i This i will i be i a i issue i in ithe
iproposed imetric ito icaluclate i appropriate i bandwidth.
iAl-Turjman iet. ial. i[9] iproposed ia irouting imetric i to
imeasure i the i link i bandwidth i which i employed i a
i probing itechnique i in i transmitting i a i pair i of
i packets i to i its i neigh- ibors. iEventhough ithe
iproposed imetric imeasures i the i link iband iwidth, isuch
imeasurements idirectly iinfluence i the
packet itransmission itime ithus iaffecting ithe iQoS.
In ipaper iJilong iLi iet. ial. i[10] iproposed ia irouting
imetric inamed iWeighted iCumulative iExpected
iTransmis- ision iTime i(WCETT). iThe iWCETT imetric
iconsiders ithe iinterference iamong imultiple ilinks ithat
iutilise ithe isame ichannel iby icombining iindividual
ilink iweights iinto ia isingle ipath. iHowever, iWCETT
ilacks iperformance iin ihandling ilinks iload iexplicitly
iand iin iminimizing iintra i iflow i interference.
A ihierarchical imulti-path irouting iprotocol iwhich iis
ia icombination iof imultiple itopologies ihas ibeen
iproposed iin iGP iSunitha iet. ial. i[11]. iThe iproposed
iprotocol idetects icongestion iin iWSN iin ia itimely
imanner iby imonitoring ithe ipath iquality imetrics. iIt
idistributes ithe ipackets i on imultiple ipaths ito ialleviate
icongestion. iThis iis idone ito iachieve ihigh ienergy
iefficiency, inetwork idurability iand ibetter iquality iof
iservice. iHowever, ithe ipaper idoes inot imeet ithe
irequirements iof idelay-sensitive iapplications iby
iselecting ipackets ibased ion i priority.
Peng iet.al i[12] iproposes ia irandom ilinear inetwork
icoding-based ifault-tolerant irouting imechanism. iThis
imechanism icouples ithe imulti-path irouting iand
irandom inetwork icoding itechniques iand iit idoes inot
ineed ito iknow ithe itopology iinformation iof iglobal
inetworks iand iencod- iing ivectors iare imixed iat ieach
icoding inode iaccording ito ilocal icoding imethod. iA
ifinite iencoding ioperation iis idone iin ieach ilink-
disjoint ipath iwith ipiggyback iof ia icoding icoefficient,
iwhich ican igreatly ireduce ithe icomputational
icomplexity.
In ipaper iJilong iLi iet. ial. i i[13], i iproposed i ia i
icluster- iing ibased irouting ialgorithm iconsidering ian
iinterference iand iload ibalancing ias irouting imetric
 5

isource
delay i iwill i icause i idisturbance i iin i iother i iformats i
isuch i ias ipacket-delivery-ratio, ijitter iand iother ifactors.
iThus ipareto-optimal i soultions i will i not i be i obtained.

III PROBLEM iSTATEMENT

The iproblem iconsidered iin ithis ipaper iis ito ifind ithe
ishortest ipath ito ia imulti-objective iscenario iwith imaxi-
i imization iof iPDR iand iminimization iof idelay. iThe
iobjec- itives iare:
1) To iavoid icongestion iusing ithe ipro-active
ialgorithm.
2) To i maintain i the i network i in i a i steady i state.
3) To iincrease ithe ithroughput iand ito ireduce idelay
iand ienergy i consumption
4) To ifind ithe ioptimal irouting ipath iusing ifuzzy
iweighted isum imodel.

IV NETWORK iSETUP
In iour istudy, ithe inetwork itopology iis iconstructed
iusing iZone iRouting iProtocol(ZRP). iPrimarily, ieach
inode iin ithe itopology iindividually icreates iits iown
ineighborhood icalled irouting izone. iThis izone iis
icreated ibased ion ithe ipre-determined iradius iof izone
icalled ias izone iradius(K). iIn iFig.1, ithe iradius iK iis
inumber iof ihops ifrom ithe iprimary inode. iEach iof ithe
inodes istores ithe iinformation iabout inodes iin iits
irouting izone iin irouting itables.Initially, itwo itypes iof
inodes iare idetermined: iPrimary inode iand iPe- iripheral
inodes. iPrimary inode iis iinitially ithe isource inode iand
iperipheral inodes iare ithose inodes iwhose iminimum
idistance ifrom ithe iprimary inodes iis iequal ito ithe izone
iradius.

Fig. i1: iRouting izone iwith iradius, iK=1

In iZRP, itwo isub-routing iprotocols iare iimplemented:

iIntra iZRP(IARP) iand iInter iZRP(IERP). iWhen ithe
 6

and idestination inodes iare iselected, iprotocol ifirst Pi,j irepresents ithe iPDR ibetween ithe ilink i(i,j).
ichecks iif ithe idestination inode iis ipresent iin iprimary
inode irouting izone. iIf iit iis ipresent ithen iIARP iis iused
ito ifind ithe iroute iusing irouting itable iof ithe iprimary
inode ias idepicted iin i iFig. i2(A) iThis iis iachieved iby
isending ithe iroute irequest ipacket ito ineighboring
inodes. iWhen ithe iacknowledgment iis ireceived ifrom
ithe inodes iabout ithe iroutes, ithe iroute iwill ibe
i considered.
If idsestination inode iis inot ipresent iin ithe irouting
izone iof iprimary inode, ithen iIERP iis iused ias idepicted
iin iFig. i2(B). iIn iIERP ithe iroute irequest i iis i
iprimarily i isent i ito i ithe iperipheral inodes, iwhich i
ithen i iwill i ibe i iconsidered i ias iprimary inode. iFor
ieach iprimary inode iconsidered, iIARP iwill ibe
iimplemented iagain iand iprevious isteps iare ifollowed
i to i find i the i destination i node.

V MULTI iOBJECTIVE iDIFFERENTIAL

EVOLUTION
The itopology iof inetwork iis ispecified iby ian
iundirected igraph, iG i= i(V, iE) iwhere iV irepresents ithe
iset iof inodes iwhich iconsists iof iboth imesh iclients iand
imesh irouters iand iE irepresents iwireless iconnectivity
iamong ithe inodes. iA ipath ifrom inode iVi i ito iVj i iis ia
isequence iof inodes iand i ino inode iappears imore ithan
ionce. iThe ibinary idecision ivariable i Xi,j i represents ∈
i whether i a i particular i link i (i,j)
E iis iincluded iin ia irouting ipath ior inot.

A. Objective iFunction iand iRelated i Constraints

a) Delay

The itotal idelay ifunction iis ithe isum iof ithe i idelay i iof
i ilinks ialong ithe ipath ifrom ithe isource ito ithe
idestination. iObjective ifunction ifor idelay ican ibe
iexpressed ias ifollows: Σ

f1 i= imin Di,jXi,j (1)

(i,j)∈E

Di,j irepresents ithe idelay ibetween ithe ilink i(i,j).

b) Packet iDelivery iRatio i (PDR)

The iPDR ifunction iis ithe isum iof ithe iPDR iof ilinks
ialong ithe ipath ifrom ithe isource ito ithe isink. iIt iis ithe
inumber i i i i iof idata ipackets idelivered ito ithe
idestination idivided iby ithe itotal inumber iof ipackets
igenerated iby ithe isource. iThe iobjective ifunction iis
Σ
f2 i= imax Pi,jXi,j (2)
(i,j)∈E
 7

Fig. i2: iIARP iand iIERP i iprotocols

c) Flow iConservation iConstraints with ia iset iof iPareto-Optimal isilutions iand igive ithe
iliberty ito ichoose ithe ibest isolution ifrom ithe iset
To igurantee ithe iuniformity iof ithe imodel, iwe ihave ito idepending ion ithe ispecific i requirements.
imodel ithe iflow iconservation iconstraints iat ithe isource,
idestination iand iintermediate inodes. iS irepresents ithe a) Population i Initialization
isource inode iand iT irepresents ithe idestination inode.
iThe iflow iconservation iequation iis irepresented ias Encoding iis ithe iprocess iof imapping ia idecision
ivariable iinto ia ichromosome. iThis iis ione iof ithe imost
Σ
Xi,j i= i1, ii i= iS (3) iimportant istep itowards isolving ithe irouting iproblems
(i,j)∈E iusing ievo- ilutionary ialgorithms. iA ichromosome
Σ icorresponds ito ithe ipossible isolution iof ithe
Xi,j i= i−1, ii i= iT (4) ioptimization iproblem. iThe ilength iof ithe ichromosome
(i,j)∈E iis ivariable iand imay inot ibe igreater ithan ithe inumber iof
Σ i Σ i inodes, iN. iThe irouting ipath iis iencoded iby ia istring iof
Xi,j i− i Xj,i i= i0, ii iƒ= iS, ii iƒ= i T (5) ipositive iintegers ithat irepresent ithe iIDs i i i i iof i the
i nodes i through i which i the i path i passes. i The i intial
(i,j)∈E (i,j)∈E
population iis igenerated iusing iBreadth iFirst iSearch
i(BFS) ialgorithm. iUsing ithe iBFS ialgorithm, ithe
ishortest ipaths ifrom isource ito idestination iwill ibe
iobtained iand i such
B. Proposed i Algorithm ibehind i developing i such i algorithm i is i to i provide i the
i user
Multi-objective ioptimization iprooblem ican ibe isolved
ibt iDE istrategy, ithe ioriginal ischeme iof iDE ihas ito ibe
imod- iified isince ithe isolution iset iof ia iproblem iwith
imultiple iobjective idoes inot iconsists iof isingle
isolution. iThere iare itwo iissues iwhen idesigning ia
iMOEA: i(1) iSurvivor iSe- ilection, i(2) iPopulation
iDiversity. iThe ifirst ione iaddresses ithe iselection iof
iindividuals iin ithe ipopulation i through inon-dominated
isorting iapproach iand i ithe i isecond i issue iis ito
ipromote iwhich ican ibe iachieved imy imeans iof
idynamic icrowding idistancing imeasure. iThe imotivation
 8

obtained ipaths iare iconsidered ito ibe iinitial ipopulation.

b) Mutation

The imutation iof iDE ialgorithm iis idifferent ifrom iother

i ievolutionary ialgorithms. iThe ivariant iwhich iis
iproposed iin ithis ipaper iis idenoted ias
iDE/rand/1/WMX iwhere iDE irefers ito ithe iname iof
ithe ialgorithm; ithe iword irand iindicates ithat ithe
idonor i ivector i iselected i ito i icompute i ithe imutation
ivallue iis ichosen iat irandom. iThe ipairs iof isolutions
ichosen ito icalculate ithe imutation i idifferential iare
iindicated ias i1 iand ifinally iWMX istands ifor iWeight
iMapping iCrossover-based irecombination. iAssume
iXr1 iis
 9

the idonor isolution iwhich ican ibe ichosen ieither iat 1i

irandom ior iit ican ibe ithe ibest isolution iin ithe 4
ipopulation. iXr2 iand iXr3 iare ithe ipair iof isolutions 2i
r3 i= i
ichosen ialways iat irandom. iBut iin iour istudy, i iwe ihave 3
i chosen iall ithe isolutions ito i i be ibest isolutions iin ia 5ii
iordered imanner. iThis idifference i i i iis iscaled iwith ithe
6
iF iparameter. iAfter ithat, iit iis iadded ito iXr1 i to i define
i the i location i of i the i mutation i vector.

The itransformation iinto ifloating-point ivalues iis

Vi i= iXr1 i+ iF i(Xr2 i− iXr3) (6) iachieved iby idividing ieach ielement iof ithe ivector iby
ithe ilargest ione iof ithem.
where ir1ƒ i= iƒr2 i= ir3 iare imutually idistinct irandom
i
iindices, iand iF iis ia idifferential iweight, ia iscale ifactor 1i
iapplied ito ithe i differential i vector. i i i = i 1,2,. i i ,N 0.4
i represents i the i index
of ithe iindividual iin ithe ipopulation.
0.8
The iDE ialgorithm iis ioriginally iapplicable ito icon- Xr1 =
1
itinuous ioptimization iproblems ias iits isearch
imechanism iis ibased ion iperturbations ibuilt iwith
0.6
idifference ivectors. iHowever, iwhen idealing iwith
6
icombinatorial ioptimization iproblems iinvolving i
1i
ipermutations iof iinteger ivectors, ithe idirect iapplication
iof ithe idifferential imutation imechanism iis inot ivalid,
0.6
isince ithe iarithmetic ioperations ion isymbolic ivalues 0.8
Xr2 = i
iwould inot ilead ito iany imeaningful idirection iin i i ithe
isearch ispace. iAdditionally, iafter iscaling iand iadding i 1 i0.i
ithis iresult ito ia ithird ivector, iinvalid isolu- itions iare i 4 6
iusually iobtained. iTo icompensate ithis idrawback, iRela-
i
itive iPosition-based iIndexing i i(RPI) i iis i iused i ito i 1i
iconvert ia icontinuous iposition ivector ifor irouting. iThis 0.8
iapproach itransforms ithe ielements iof ithe iinteger
0.4
ipermutation ivector iinto ithe ifloating-point iinterval i[0, Xr3 = i
i1] iand iapply ithe idifferential imutation ias iin iEq. i i(6). i
i 1 i0.i
iThe i ifinal i ivalues i iare ithen iconverted iback iinto ithe
6
iinteger idomain iusing irelative iposition iindexing. 6
Three ibest ipaths iare ichosen ifrom ithe icurrent
ipopula- ition. iThe isource iand idestination inodes iare
ifixed. iLet ithe
source inode ibe i’1’ iand ithe idestination inode ibe Applying iin iEq. i(6) iwith iF i= i0.6, ithe imutant
i’6’. ivector i i i iis igiven iby
i
1i i
2 1i
0.28
i4 i 1.04
r1i= i i5 i
Vii=
6
3ii
6

1i
3
4i
r2 i= i
2
5ii
 10
0 e he inext ismallest ifloating-point ivalue iby i ithe inext
.
8 iinterger ivalue iuntil iall ithe ielements ihave ibeem
8 i
iconverted. i The i final i mutant i vector i is
b
y
i
t
i h
0 e

. i
s
6 m
a
l
i
l
e
s
t
6
i
i
T
n
o
t
icon
e
vert
g
ithe
e
imut
r
ant
ivect i
or v
ibac a
k l
iinto u
ithe e
iinte ,
ger
i
idom
a
ain
n
iusin
d
g
ithe i
iRPI t
, h
ithat e
iis n
ito
i
irepl
r
ace e
ithe
p
isma
l
llest a
ifloa
c
ting- e
poin
t i
ivalu t
 11

1i WMX ifinds imany inew ipaths iwithout iincreasing ithe

2 icomputational icomplexity.
5i
V i i= i
4 e) iDynamic iCrowding iDistance i(DCD)
3ii
6 The iDiversity iMaintenance iStrategy i(DMS) iis ithe ipro-
icess iof ipopulation imaintenance, iwhich iuses ia
itruncation
operator ito iwipe ioff ithe iindividuals, iwhen ithe inumber
This iapproach ialways iyields ia ifeasible isolution,
iof inon-dominated isolutions iexceeds ithe ipopulation
iexcept iwhen itwo ior imore ifloating-point ivalues iare ithe
isize. iIn ithis ipaper, idynamic icrowding idistance i(DCD)
isame.
ipresented iby iLuo iet ial. i[16] ibased iDMS iis iused. iOne
iindividual iwith ilowest iDCD ivalue ieverytime iis
c) Chromose i Repair
iremoved iand ithe iDCD ifor ithe iremaining iindividuals
iis irecalculated. iThe iindividual iDCD iis icalculated ias
The iconversion ioccurs ibetween itwo ioperational
ifollows:
idomains, iand ithe inumber iof iinfeasible isolution
icreated iwill ibe isignificant. i There i are i three i unique
i repairment i strategies
described i iby i iGodfrey i iand i iDonald i i[14] i ito i irepair i i i iCD
i i the
DCD . ii Σ (7)
replicated i values. i In i this i paper, i front i mutation i=
V
can iiThe
iused. be isteps iare ias ifollows: log 1i
1) Find iall ithe irepetitive ivalues iin ithe iinfeasible
isolu- ition. where iCDi iis icalculated ibased ion ithe iEq. i(8) iand iVi iis
2) Based ion ithe ireplicated iposition, ian iarray iof icalculated ifrom ithe iEq. i(9)
imissing ivalues iis igenerated.
3) An i insertion i array i which i indicates i the r
i position i of CD i =1 |f − if r | (8)
i Σ
the iinsertion iof ieach ivalue iis irandomly igenerated r
i i+1
based ion ithe imissing ivalues. iFinally, ithe ifeasible r i−1
k=1
isolutions ican ibe igenerated.
where i ir i iis i ithe i inumber i iof i iobejctives. i i f ik
i+1 is i
ithe i i kth k
objective iof i(i+1)th iindividual. i i f i is ithe ikth i objective
d) Weight iMapping iCrossover i (WMX) i−1
of i(i-1)th iindividual.
The inature iof ipriority-based iencoding iis ia ikind iof
ipermu-
tation irepresentations. iThis irepresentation iwill iproduce The iDCD ialgorithm iis igiven ibelow:
iillegal ioffsprings iby ione-cut ipoint icrossover ior iother
isim- iple icrossover ioperators. iIn ithis ipaper, iwe ihave
Algorithm i1: iDynamic iCrowding iDistance iAl-
iselected iweight i maping i crossover i (WMX) i proposed
igorithm.
i by i Lin i and
Gen i[15] ias icrossover ioperator. iIt iis ian iextension iof i one- i

cut ipoint icrossover ifor ipermutation irepresentation. iAt i 4) Offspring iwith imapping irelationship iare igenerated.
ione icut ipoint icrossover, itwo ichromosomes iwold
ichoose ia irandom-cut ipoint iand igenerate ithe ioffspring Here, isource iand idestination inodes iare ifixed. iIn iWMX
iusing ia isegment iof iits iown iparent ito ithe ileft iof ithe
icut ipoint, ithen iremap ithe iright isegment ibased ion ithe
iweight iof iother iparent iof iright isegment. iThe isteps iof
iWMX icrossover iare igiven ibelow:

1) Random i cutpoint i of i the i parents i are i generated.

2) Substring i between i the i parents i are i exchanged.
3) Weight iof ithe iright isegment iis i mapped.
 12

Init: iSet iN i= iPopulation iSize iand iLet iQ(t) iEq. i(7). iSort ithe inon-dominated i set.
ibe ithe inon-dominated iset, iM i= isizeof 6 Remove iindividual iwhich ihas ithe ilowest
i(Q) iDCD ivalue i in i Q(t), i go i to i step i 5.
1 if Q(t) N i then 7 if | Q(t) |≤ N i then
2 goto istep i7 8 Stop ithe ipopulation i maintenance
3 else 9 else
4 goto istep i5 10 goto istep i5
5 Calculate iindividuals iDCD iin iQ(t) ibased ion
crossover, i repetition i of i nodes i are i avoided i by i a i mapping i

function, ihence ino irepair ifunction iis ineeded. iTherefore,

 13

f) iMulti-Objective iDifferenetial iEvolution i Algorithm Algorithm i2: iMulti-obejctive iDifferential iEvolu-

(MODE) tion iAlgorithm.
Init: iSet it i= i0, iN i= iPopulation i Size
The ioptimization iprocess iin iMODE istarts iwith ia
1 Compute iinitial ipopulation iroutes iusing
irandom ipopulation iof isolutions iusing iBFS ialgorithm.
iBFS ialgorithm
iAll ithe iparents iin ithe ipopulation iP iare iused ifor
2 Pt i= icalculate ithe iobjective ifunctions ifor
icreating ithe imutated iparents iof isize iQM iusing iRPI.
ithe iinitial i population.
iFor iall ithe imutated iparents, ithe ioffspring iis icreated
3 repeat
iusing iWMX icrossover. iThe isize iof ioffspring iQC iis
4 Perform imutation ioperation iusing
ialso ihaving ithe isame isize iof iP. iNow iboth ithe ioriginal
iRPI iapproach.
iparent iand ithe ioffsprings igenerated ifrom
5 Apply iWMX icrossover ifor ithe ientire
irecombination ioperator iare icombined itogether ito iform
imutated iparents i to i generate i the i offspring
i2 i* iP iset iof i iindividuals. iAfter ia igeneration, ithe
i Qt
icombined iparent iand ioffspring ipopulation iis ithen
6 Rt i = i Qt∪ Pt
ireduced iback ito ioriginal ipopulation isize iusing inon-
7 Perform inon-dominated isorting ifor ithe
dominated isorting iand idynamic icrowding idistance. iIn
icombined iparent iand ioffspring
ithe inon-dominated isorting imethod, ithe inew ipopulation
ipopulation i(Rt).
iis ipacked iwith isolutions iof idifferent inon- idominated
8 Calculate iDCD ifor ithe icombined
ifronts. iThe ibest inon-dominated ifront iis icon- isidered
ipopulation ibased ion ithe iAlgorithm i 1
ifirst,then icontinued iby ithe isecond inon-dominated ifront
9 Apply ithe iselection iof iroutes ibased ion
iwhich iis ifollowed iby ithe ithird iand iso ion. iWhen ithe
ithe ibinary itournament iselection.
itotal inon-dominated isolutions iexceed ithe ipopulation
10 i i= ii i+ i 1
isize iZ, i reject i some i of i the i lower i ranked i non- 11 iuntil it i< iMax iGeneration;
dominated i solu-
tions. iThis iis iachieved ithrough ia isorting iprocedureiwhich i
is idone iaccording ito ithe idynamic icrowding idistance.
TABLE iI: iSimulation iParameters
Finally, ithe ipopulation iof iparents iare igenerated iusing
ithe ibinary itournament iselection ito ithe icurrent i i iParameters Values
ipopulation. i i iIt irandomly iselects ithe itwo isolutions Simulation i Area 1000 im iX i1000 i m
ifrom ithe icurrent ipopulation iand ichooses ithe ibest ione. Routing i Protocol ZRP
iThe ialgorithm iis iterminated iwhen ithe imaximum
Propogation i Model Two iRay iGround
inumber iof igenerations iis ireached.
Transmission i Range 250 i m
The ifollowing isteps iare iadopted ifor ithe
Simulation i Duration 100,200,300,400,500 i s
iimplementation iof ithe iproposed iMODE ialgorithm.
No i of i Nodes 20,40,60,80,100
Transmission i Rate 10,20,30,40,50 i kbps
VI IMPLEMENTATION Number iof iChannels i Used 1
To i ianalyze i ithe i iperformance i iof i iMODE i ialgorithm, i we i

consider ithe iZone iRouting iProtocol i(ZRP). iWe ihave

made iuse iof iMATLAB ifor isimluation istudy. iThe iof iexperiments ibe- ifore i performing i actual i runs i to
iperfor- imance imetrics iconsidered iin ithis ialgorithm iare i collect i the i results. i The
iPDR iand iaverage idelay. iThe iperformance imetrics iare
iobtained iby icalculating ithe iaverage iresult iof i20 itest
iruns. iThe iaverage ivalue iwith istandard ideviation iis
iplotted ias ierror igraphs iwith i95 i% iconfidence iinterval.
iA itotal iof ifour isimulation iscenarios iare icarried i out.

a) iParameter iSeclection

The ivarious imethods iof ioptimal iparameter

icombinations iare iexperimentally idetermined iwith
idifferent i iparame- iter isettings iby iconducting ia iseries
 14

crossover iprobability i(Pc) iis iselected ibetween i0.5 iand

0.95 iin isteps iof i0.01 iand ifor ieach iP ic iperformance
iis ianalyzed. iIt iis ifound ithat iP ic i= i0.85 iproduces ithe
ibest iresults. iThe iscaling ifactor iF iis ivaried iin ithe
irange i0.1 i– i1 iin isteps iof i0.1 iand iit iwas ifound ithat
iF i= i0.6 iproduces ithe ibest iresult. iTable i2 ishows ithe
iset iof icontrol iparameters iselected iafter iconducting
ithe iexperiments.

VII PERFORMANCE iEVALUATION

In ithis isection, iwe ihave ipresented ithe isimulation
iresults ias ithe iperformance ievaluation iof iour
ialgorithm. iThe iperformance iof iproposed ialgorithm iis
icompared iwith iClustering ibased irouting ialgorithm
i(CBRA) iin iWMN i i i iin i terms i of i PDR i and i delay.
 15

Fig. i3: iProposed i iModel iFlow

 16

TABLE iII: iControl iparameters iselected ifor iMODE

ialgorithm

i i iParameters Values
Population isize 100
Number iof iiteration 100
Crossover iprobability i(Pc) 0.85
Scaling iFactor i(F) 0.6
Generation iselection Elitist

Fig. i6: iPDR i(%) iunder iincreasing inode isize

with ithe iincrease iin isimulation itime. iDuring ithe iinitial

istage iitself, ithe iinfeasible isolution iis ieliminated iwith
iBFS ialgorithm iand ifront imutation iand iin iCBRA ithe
icongested iroute iwill inot ibe ieliminated iwhich imight
iresult iin icongestion iin ifuture iif ithe itraffic iis inot
icleared. iThese ifactors iresult ifor iless idelay iin iMODE
ithan iCBRA. iThe isimulation i iresults i iof i ithe i iPDR i
i(%) i ito i iincrease i iin ithe inumber iof inodes iare
Fig. i4: iPacket idelivery iratio i(%) iunder isimulation itime irepresented iin iFig. i6. iIn iMODE ialgorithm, idynamic
icrowding idistance imethod iremoves ionly ione
iindividual iat ia itime iand irecalculate ithe iindividuals
Figure i4 iplots ithe iPDR icomparison iof iMODE iand idistance, iso iit iprovides imore ipossibility ito iretain ithe
iCBRA ialgorithm iwith iincreasing isimulation itime. iThe iindividual iin ithe inon-dominated iset. iMODE iperforms
iPDR ivalue iof iMODE iis ihigher ithan iCBRA iwith iwell ifor iall ithe itopologies iand ihas ithe ihighest iPDR.
iincreasing isimulation itime. iSince iwe ihave iused i iBFS i Figure i7 ishows ithe isimulation iresults ifor ithe iaverage
ialgorithm i ifor iinitial ipopulation igeneration, ithe iend-to-end idelay ifor iincreasing ithe inumber iof inodes. i
inumber iof ifeasible isolution iis iincreased. iHence ithe i i iIn iMODE, iboth ifront imutation iand imapping
ipacket idelivery iratio iof iMODE iis ihigher ithan i CBRA. ifunction i i i iof iWMX icrossover ieliminate ithe
Figure i5 icompares ithe iaverage idelay iof ithe ialgorithms iredundancy iof ithe i ipath. iWhere i ias i iin i iCBRA, i ithe i
iwith iincreasing isimulation itime. iThe idelay iis iredundancy i iwill i inot i ibe ieliminated idue ito icluster
iincreased iformation. iHence iMODE iprovides ilower idelay ithan
i CBRA.
From iFig. i8, iwe iobserve ithat iaverage idelay iin iCBRA
iand iMODE icontinuously iincreases iwith ithe iincreasing
ipacket itransmission irate. iWhen ithe ipacket
itransmission irate icontinues ito iincrease, ithe iaverage
idelay iof iMODE i iis ishorter ithan iCBRA. iThis iis
ibecause iMODE iconsiders iboth ithe iPDR iand idelay ito
iselect ithe iappropriate ipath i for ipacket itransmission
iwhere ias iCBRA iconsiders ithem iseparately.

a) Optimal iParento iFront

The ibest iPareto ifront iis iobtained iamong i20 isimulation
iruns iusing iMODE, iwhich iis iportrayed iin iFig. i9. iFor
ia igood iMOEA, ia iuser iis iexpected ito ifind isolutions
iclose ito ithe itrue iPareto-optimal ifront ias iwell ias
Fig. i5: iAverage idelay iunder isimulation itime isolutions ithat ispan ithe ientire iPareto-optimal iregion
iuniformly. iIt i is
 17

used ito icalculate ifor igoodput iper isecond. iFig. i10

ishows ithe iaverage igood iput, iwhich iis iapproximately
i68.4 ibytes iper isecond. iIn icase iof iCBRA iis i61.5
ibytes iper isecond. iFig. i10 ishows ithat igoodput iis
ihigher iin icase iof iMODE ithan iCBRA. iThis iis idure ito
iMODE ihas ilow idelays iand igood idiversity iin irouting.

Fig. i7: iAverage idelay iunder iincreasing inode isize

Fig. i9: iPareto-optimal isolution iof iMODE iand iCBRA

Fig. i8: iAverage idelay iunder iincreasing ipacket

itransmission irate

obvious ifrom iFig. i9 ithat ithere iis ia igap ibetween ithe

iCBRA iand ithe ibest iPareto ifront iobtained ifrom
iMODE. iTo iobtain ithe ibest iPareto ifront, ithere ishould
ibe idiversity iand iselection iof iappropriat ipopulation. iIn
iMODE, ithese iare iobtained ifrom iusing iWMX iand Fig. i10: iGoodput
iDCD ioperators iin iboth irecombination iand iselection
istrategies ito iimprove ithe ilateral idiversity. iBut iin
iCBRA, idue ito ithe iimmobility iof ithe inodes, ithe b) Validation iof iPerformance i Metric
iclusters iwon’t ibe ichanged ias isuch. iDue ito ithe istatic
iclusters iin ithe inetwork, ithe idiversity iwill i not ibe To ivalidate iperformance iof ithe iproposed iMODE ial-
iobtained. iFrom ithe ifigure i9, iit iis iclear ithat iall i i i ithe igorithm, ispread imetric i(∆) iby iDeb i[17] iis iused. iAn
iobtained inon-dominant isolutions ilie ion ithe iPareto- ialgorithm ifinding ia ismaller i(∆) ivalue iis iable ito ifind ia
ioptimal ifront ialso imaintain ia iuniform idistribution ibetter idiverse iset iof inon-dominated isolutions.
iover ithe ientire iPareto-optimal i region.
Goodput iis igenerally idefined ias iapplication ilevel
ΣM Σ|Q| i i
throughput, ii.e. ithe inumber iof iuseful ibits iper iunit iof
m=1
e i i i+ i |di (9)
itime iforwarded iby ithe inetwork ifrom isource ito ∆ i= Σ
idestination, i − id|
dm
demi+i=1 ii
i|Q|d
excluding i iprotocol i ioverhead i isuch i ias i re-transmissions. ii M
m=1
The igoodput iis imeasured ias itotal inumber iof ipackets isecond ion ian iaverage. iThe iaverage ivalue iof ithroughput
imul-
tiplied iby isize iof ipackets imultiplied iand imeasured iper iis
 18
where idi iis idistance imeasure ibetween ineighboring
isolu-
tions. id iis imean ivalue iof ithe idistance imeasures. ide iis m
idistance ibetween ithe iextreme isolutions.
 19

maintain idiversity iamong ithe iset iof isolutions iin ithe

iPareto ifront. iThe iresults ishow ithat iMODE iis iefficient
ifor isolving imulti-objective irouting iproblem iwhere
imultiple iPareto-optimal isolutions ican ibe ifound iin ione
isimulation irun. iThe idiversity iperformance iof iMODE
ialgorithm iis ivalidated iusing ithe iperformance imeasure
ispread. iThe iapproach iis iquite iflexible iso ithat iother
iformulations iusing idifferent iobjectives iand/or ia ilarger
inumber iof iobjectives iare i possible.
For ifuture iwork iincluding ithe iextension iof iMODE-
ibased irouting iapproach ito iincorporate irouting ifor
imobile inetwork iand ifor imultiple ichannel iwould ibe
iinteresting. iThis i increases i efficiency i in i modern
Fig. i11: iComparison iof iMODE iagainst iCBRA iusing i areas i of i IOT.
ispread imetric

TABLE iIII: iStatistical icomparison iof iperformance imetric References

i i iPerformance i measures MODE CBRA
[1] P. iFishburn, i“Additive iutilities iwith iincomplete iproduct iset:
Spread i(∆)
iApplications ito ipriorities,” i1967.
Mean 0.4223 0.5885 [2] B. i Peres, i B. i P. iSantos, i A. i d. i O. i Otavio, i O.
Best 0.2340 0.4567 i Goussevskaia, i M.
A. iVieira,L. iF. iVieira, iand iA. iA. iLoureiro, i“Matrix:
Worst 0.6856 0.7509 iMultihop iaddress iallocation iand idynamic iany-to-any irouting
Variance 0.0823 0.0158 ifor i6lowpan,”
Computer iNetworks, ivol.140, ipp. i28–40, i2018
[3] Y. iQiu iand iM. iMa, i“Secure igroup imobility isupport ifor
i6lowpan inetworks,” iIEEE iInternet iof iThings iJournal, ivol. i5,
From iFig. i11, iall ithe iscenarios iDMODE ihave iless i ino. i2, ipp. i1131– i1141, i2018
[4] Sandeep iKumar, iMonika iGoyal, iDeepak iGoyal, iRamesh iC.
ispread ivalue ithan iNSGA-II iand iDEPT, iwhich iindicate
iPoonia, i”Routing iprotocols iand isecurity iissues iin i MANET”,
ithat idynamic icrowding idistance iimproves iconvergence ICTUS iInternational iConference, i2017
iand isimultaneously iimproves ithe idiversity iof ithe inon- [5] P. iSailaja, iBanoth iRavi, i iT. i i Jaisingh, i i”Performance i
idominated i solutions. iAnalysis i iof iAODV iand iEDAODV iRouting iProtocol iUnder
iCongestion iControl iin iVANETs”, iICICCT iInternational
The icomparison iof iperformance imetrics iwith iits ibest, i iCoference, i 2018
imean, iworst iand istandard ideviation ivalues iis [6] Storn iR., iPrice iK., i”Differential iEvolution i– iA iSimple iand
irepresented iin iTable iIII. iFrom iTable iIII, iit iis iclear iEffi- icient iHeuristic ifor iglobal iOptimization iover
ithat iSpread istatistical iperformance imeasures ihave iContinuous iSpaces”,
Journal iof iGlobal iOptimization i11, i341–359, i1997
iminimum imean ivalues iin iMODE ias icompared ito
[7] A. iAdya, iP. iBahl, iL.Zhou, iA. iWolman, iJ. iPadhye, i”A imulti-
iCBRA. iHence, iit iis iobvious ithat iMODE iperforms Radio iUnification i”, iIETE iTechnical iReview, i2017
imuch ibetter ithan iCBRA iin ithis icontingency [8] R. iDraves, iJ. iPadhye iand iB. iZill, i”Routing iin imulti-radio,
i condition. imulti- ihop i wireless i mesh i networks”, i in i MobiCom, i 2014
[9] Hasan iM., iAl-Rizzo iH. iand iAl-Turjman iF., i”A isurvey ion
imultipath irouting iprotocols ifor iQoS iassurances iin ireal-time
imultimedia iwireless isensor inetworks”, iIEEE
VIII CONCLUSION iCommunications iSurvey i& iTutorials, i 2017
In ithis ipaper, ithe irouting iproblem iis itaken iinto icon- [10]Li iJ., iKhan iM., iLee iB. iand iHan iK., i”Load ibalancing iand
isideration ifor ithe imulti-objective ioptimization iinterference idelay iaware irouting iin iIoT iaware iwireless
i mesh inetworks.”, iJournal iof iInternet iTechnology, i1607–
icontexts, iwhere iPDR iand idelay iare ioptimized 9264, i 2017
isimultaneously. iTo irepresent ithe iinitial isolution, ithe [11]G. iSunitha, iB. iV. iKumar, iand iS. iD. iKumar, i”Optimized
iBFS ialgorithm iwas iused iand ipenalty ifunction iwas icon- igestion iaware ienergy iefficient itraffic iload ibalancing
ischeme ifor irouting iin iwireless isensor inetworks”, iin
idesigned ito ieliminate ireplicated isolutions iduring ithe
iProceedings iof ithe i2015 iWorkshop ion iIoT ichallenges iin
imutation iprocess. iThe isimulation iresults ihave ishown iMobile iand iIndustrial iSystems. iACM, i2015, ipp. i25–30.
ithat iour iproposed ialgo- irithm iMODE iperforms ibetter [12]Peng iY, iSong iQ, iYu iY iand iWang iF, i”Fault-tolerant irouting
ithan iCBRA iand iit ihas iimproved ithe iPDR iand imecha- inism ibased ion inetwork icoding iin iwireless imesh
inet- iworks”, i J i Network i Comput i Appl i 37: i 259–272.
iminimized ithe idelay. iThe iconcept iof iWMX icrossover
[13]Jilong iLi, iBhagya iNathali iSilva, iMuhammad iDiyan, iZhenbo
iand iDCD iis isuccessfully iemployed iin iMODE iCao, iKijun iHan, i”A iclustering ibased irouting ialgorithm iin
ialgorithm ito iimprove iconvergence iand i to iIoT iaware iWireless iMesh iNetworks” iSustainable iCities iand
 20
iSociety i40 i(2018) i657–666, i Elsevier.
[14]Godfrey iCO iand iDonald iD, i”Differential ievolution: ia
ihandbook ifor iglobal ipermutation ibased icombinatorial
ioptimization”, i1st iinternational i conference i on i genetic
i algorithms, i pp i 154–159
 21

[15] Lin iL, iGen iM, i”Bicriteria inetwork idesign iproblem iusing
iinter- iactive iadaptive iweight iGA iand ipriority-based
iencoding imethod.”,
IEEE iTrans iEvol iComput
[16]Luo iB, iZheng iJ, iXie iJ, iWu iJ, i”Dynamic icrowding idis-
itance—new idiversity imaintenance istrategy ifor iMOEAs”, i4th
iIEEE iinternational iconference inatural icomputation, ipp
i 580–585
[17]Deb iK, i”Multi-objective ioptimization iusing ievolutionary
ialgo- irithms”, iWiley-Interscience iSeries iin iSystems iand
iOptimization- iWiley, iWest iSussex