基于差分进化的多目标异构传感器网络节点部署机制

31820108ChineseJournalofScientificInstrumentVol131No18Aug.2010:2010201ReceivedDate:20102013:863(2006AA783201-2)(20060611010)3,(400030):,,maximinPareto,,,:;;;;:TP393:A:120.99Optimalmulti2objectivesensordeploymentschemebasedondifferentialevolutionalgorithminheterogeneoussensornetworksLiMing,ShiWeiren(CollegeofAutomation,ChongqingUniversity,Chongqing400030,China)Abstract:Aimingattheobjectivesofguaranteeingcoverageofsensors,satisfactorydetectionthresholdsandleastenergyconsumption,amulti2objectivedifferentialevolutionalgorithmisproposedtosolvetheheterogeneouswirelesssensornetwork(WSN)deploymentintheobservedarea,whichischaracterizedbythegeographicalirregularityofthesensedevents.Inthisalgorithm,maximinfitnessfunctionisusedforconvergingtowardtheParetooptimalsolu2tions.Thustheoptimalheterogeneoussensorplacementisobtained.Experimentresultsdemonstratethatthepro2posedapproachissuitableforsolvingdeploymentproblemsofheterogeneousWSNs.Keywords:wirelesssensornetwork;heterogeneousnetwork;sensordeployment;differentialevolutionalgorithm;multi2objectiveoptimization1,[123]8:1897,[425][6];[728],,;[9];[10],,;[11],,,,,[12213],[14],,2A,AN,1,K,(rks)(rkc),rkc2rks,GPS[15]2.1AKsi,(xi,yi),pj,sipj:d(si,pj)=(xi-xj)2+(yi-yj)2(1),d(si,pj)siris,pjsi,:cb(si,pj)=1,d(si,pj)rsi0,(2),:maxF1=Nj=1cb(Pj)N(3)2.2,pjt(pj),,,,,A,[16],P(si,pj)sipj,(4):P(si,pj)=1,d(si,pj)Ccond(si,pj),Ccond(si,pj)Cmax0,Cmaxd(si,pj)(4):si,,CconCmax1(1(1)),1;(1(2)),si;(1(3)),pj:P(pj)=1-Ki=1(1-P(si,pj))(5)1898311Fig.1Sensornodeprobabilitydetectionmodel,:maxF2=Nj=1DP(pj)Mj=1t(pj)(6):DP(pj)=t(pj),P(pj)t(pj)0,(7)2.3,[17],siEiris,:Ei=(rsi)2(8),:minF3=Ki=1(rsi)2N(9)A,,,,1(),,22():miny=(f1(x),f2(x),,fn(x))(10):x=(x1,x2,,xn)X,y=(y1,y2,,yn)Y:miny=(-F1,-F2,F3)(11)2(Pareto)X1,X2,,X2,X2ParetoX1(X2X1)Pi:fi(X1)fi(X2)vj:fj(X1)fj(X2)(12),X2ParetoX1Pi:fi(X1)fi(X2)(13)3(Pareto)X3,X3ParetoX,XParetoX3,,,,,,Pareto()Pareto,3(differentialevolution,DE)R.StornK.Pricechebyshev[18],,DEWnXi=(Xi1,,Xin)(i=1,2,,W),33.13.1.1DE,,(g)2(xr1(g),xr2(g)):vi(g+1)=xr1(g)+F(xr2(g)-xr3(g)),ir1r2r3(14):F,xi(g)giF,,8:1899;,,F[0,1.2]F0,1[19][20],:vi(g+1)=xr1(g)+(xr3(g)-xi(g))+F(xr2(g)-xr1(g))(15),[21],,,,3.1.2DExiui=[ui1,ui2,,uin]:uji=vji(g+1),randCRj=randrxji(g),randCRjrandr;i=1,2,,W;j=1,2,,n(16):rand[0,1];CR[0,1],CR,,CR=0;randr[1,n],uivi,,CR=0.6[22],3.1.3,Paretomaximin[23],:1)nmin(),:mini=1,2,,n{fi(s)-fi(t)}(17)2)smax,:maxj=1,2,,N;st{mini=1,2,,n{fi(s)-fi(t)}}(18)smaximin:fmaximin=maxj{mini{fi(s)-fi(t)}}(19):i=1,2,,n,j=1,2,,N;stmaximin,fmaximinParetomaximin(19)[24],,fmaximin=maxj{mini{fi(s)-fi(t)+}}(20):(1/(4),1/(2))Pareto,ParetoDEmaximin:xi(g+1)=ui(g+1),fmaximin(ui(g+1))fmaximin(xi(g))xi(g),(21)3.2maximin1)W,F,GmaxCR2)G=0,maximin,(Pareto)nonDomList3),Xi(g+1)4),Uji5),maximin,nonDomList6),44.140m40m,[12213],:F(k)=1-(ak)1-(ab)(22)(22)Pareto,2,,:150,=1.1,a=3,b=1001900312Fig.2Theobjectlayoutinthesystemmodel4,11Table1Sensorspecifications/mRcon/mRmax/m10.542420.5626318284212212W=30,Gmax=200,FCR3.1,=F,=1/90,,=1,=14.23maximin(Pareto),(a)(b)(c)maxmin-F1,-F2,F3;(d)200,maximin,,1,2,3,4456,Pareto()(-F1,-F2,F3),,8:19016F3Fig.6ThemeanobjectivevalueF3ofnondominatedsolutionsineachgeneration5500m500m,,22Table2Experimentsensorspecifications/dBmRcon/mRmax/m1CC24301050012002LM96C16L2050010003LM96C16S2550020004CC110015500700,Pareto,(),33Table3Comparisonoftheoreticalandexperimentalresults113800.950.90380,,,,,6,maximin,,,,,,,[1]AKYILDIZF,SUW,SANAKAMANIAMY.Wirelesssensornetworks:Asurvey[J].IEEEComputerNet2works,2002,38(4):3932422.[2],,.[J].,2003,14(7):128221291.RENFY,HUANGHN,LINCH.Wirelesssensornet2works[J].JournalofSoftware,2003,14(7):128221291.[3]YICKJ,MUKHERJEEB,GHOSALD.Wirelesssensornetworksurvey[J].IEEEComputerNetworks,2008,52(12):229222330.[4]YOUNISM,AKKAYAK.Strategiesandtechniquesfornodeplacementinwirelesssensornetworks:Asurvey[J].AdHocHetworks,2008,6(4):6212655.[5]GHOSHAA,DASBSK.Coverageandconnectivityis2suesinwirelesssensornetworks:Asurvey[J].PervasiveandMobileComputing,2008,4(3):3032334.[6]OHSC,TANCH,KONGFW,etal.Multiobjectiveoptimizationofsensornetworkdeploymentbyagenetical2gorithm[C].IEEECongressonEvolutionaryComputa2190231tion(CEC2007),Singapore,2007:391723921.[7],,,.[J].,2009,24(8):118121186.JIAJ,CHENJ,CHANGGR,etal.Optimallifetimemodelbasedonmulti2nodescooperationcoverageinwire2lesssensornetworks[J].ControlandDecision,2009,24(8):118121186.[8]JIAJ,CHENJ,CHANGGR,eta1.Energyefficientcoveragecontrolinwirelesssensornetworksbasedonmulti2objectivegeneticalgorithm[J].ComputersandMathematicswithApplications,2009,57(11212):175621766.[9]PRADHANPM,BAGHELV,PANDAG,etal.Ener2gyefficientlayoutforawirelesssensornetworkusingmulti2objectiveparticleswarmoptimization[C].IEEEInternationalAdvanceComputingConference(IACC2009),India,2009:65270.[10]KONSTANTINIDISA,YANGK,ZHANGQF.Anevo2lutionaryalgorithmtoamulti2objectivedeploymentandpowerassignmentprobleminwirelesssensornetworks[C].IEEEGlobalTelecommunicationsConference(GLOBECOM2008),NewOrleans,2008:126.[11],,,.[J].,2009,23(11):65271.TIANYM,LUY,WEIZH,etal.Researchonenergy2efficientoptimizationforcov