《基于遗传算法的无线AdHoc网络QoS组播路由研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
申请上海交通大学工学博士学位论文基于遗传算法的无线AdHoc网络QoS组播路由研究专业：研究方向：导师：博士生：电子科学与技术无线网络与通信朱杰教授芦薅上海交通大学电子信息与电气工程学院二零一三年六月一专一二年7、月 Ph．D．DissertationSubmittedtoShanghaiJiaoTongUniversityRESEARCHoNGENETICALGORITHMBASEDQOSMULTICASTROUTINGINWIRELESSADHOCNETWORKMajor：ElectronicsScienceandTechnologyResearch：WirelessNetworkandCommunicationSupervisor：Prof．ZhuJieCandidate：LuTingSchoolofElectronicsInformationandElectricalEngineeringShanghaiJiaoTongUniversityJune2013 上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个入或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：争酶日期：0Df3年6月IEl 上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和奄予版，允许论文被查阅和借阅。本人授权上海交逶大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文尊保密器，在』解密后适用本授权书。本学位论文属于／不保蜜窃。V(请在以上方框内抒“4")学位论文作者签名；卢暂指导教师签名：乞阻圜期：动p年6,El}EtEl期：衣。牌6月2-El 上海交通大学博士学位论文答辩决议书：IijlI。i．il。U8．1。1．1l奎．1离ll§li。lr必4姓名卢婷l学号l00803490021墨翥l电路与系譬。’。⋯朱杰l蓄翥I2013--'06"-02I薹萋l上海交大徐汇区北二楼lo狯议童．，指导教师论文题目基于遗传算法的无线AdHOC网络QoS组播路由研究投票表决结果：竖：』!!兰’(同意票数／实到委员妣到委员数)答辩结论．＼乒螽过口爿∈通过评语和决议：～⋯一．一、●●』一一一●●一‘‘。⋯’’⋯一一一⋯4⋯⋯+‘一一’●●论文从无线AdHoc网络}舂点出发，运用遗传算法针对AdHoc网络O．oS组播路由问题进行了深入的研I{究，论文选题具有较强的理论意义和应用参考价值。1．针对AdHoc网络自身的特赢和阐黄观状，提出了三介涉及路由延迟、传输『代价。躺肖事亳、网络生存期乖口组搔生．薜缫耕生能的AdHoc网络O．oS组播路由问题，作为论文的主要研究方向。并．运雕勤疆[}；去j哦起这三个旺珏鼹，襁猷黼话}计中，提出了树j寄鳊码法。葡釉媚i化7遗f专．算法。2．提出了-种延i尽抑制最，J、能槲懿璐由鲻去(DCMEGA)，葡抛的黼端延迟，并’制、总艟消耗。I3．提出—稍嘬大网络生存铡撮小代价组擢潞由算法(MaxNLMCGA)，该箱孳去定义并呈I化了网络生存l期，通过对变异算子的设计，改善瓶颈节点的剩余能量，从而延长网络生存期·4．提出_种蜘鳓制晟始酿醢癌期缍据路由算法(DCMaxLGA)．通过改善黼铡鲥疆l生靖期，i达到延长组播生存期的目的。论=虹蛔趄鬻捌珩了大猷禧读验，验证了算；去蜘茸效性，契雠吉果表哪耐罄酷倒瓤惰喝隋算}法。论．鲻鹱飙范，翁匿!清楚，论i鲞全面，仿]彭胡珂信，内剖影抡l新性·论文成果j翱髓蛀在该甸喊}具有I蝣广的麴龌量论和系统深入的专门灯氓，并．尉黜立从鞫湘ⅡIf乍自g倒邑I丁，达到了博．拦雠蚴学：才动谭。铡簸握中，该铂列彗青楚，台旺确固翳瓣专家的提问。经酎谇毂台商己名搦蕈匮觖，—墩1同裁蘑过觑鲥膊掣粼-论文答辩，羯童i3i墩学雠精受晁会授予其=【学博j薄位。l，乡年多月2日答辩委员厶召成员签名职务单位签名陈雁秋教授复旦大学委员陈惠民教授上海大学委员陈文教授上海交通大学委员罗汉文教授上海交通大学委员戎蒙恬教授上海交通大学委员周燕工程师上海交通大学 摘要基于遗传算法的无线AdHoc网络QoS组播路由研究服务质量(QualityofService，QoS)坌H播(multicas0路由是网络优化的难题之一。用启发式算法解决QoS组播路由问题，计算时间和代价会随着网络规模的扩大而急剧增大。遗传算法(GeneticAlgorithm，GA)眭I于具有较强的适应性、强壮性和灵活性，是求解QoS组播路由问题的重要手段。由于WANET(WirelessAdHocNetwork，WANET)节点能量有限，与有线网络不同，无线AdHoc网络QoS组播路由问题需要考虑能量消耗。随着多媒体应用的飞速发展，QoS组播路由也需要考虑传输延迟和代价。本论文主要围绕华为技术有限公司研究项目“BGP路由协议硬件加速"和“P流量探测技术”在无线AdHoc网络中的研究任务，从无线AdHoc网络的特点出发，对AdHoc网络QoS组播路由问题展开了深入研究，在QoS组播路由中考虑了传输延迟、路由代价、能量消耗、网络生存期和组播生存期。本文的主要创新性研究成果如下：(1)在无线AdHoc网络中提出了三个QoS组播路由问题，分别是：延迟抑制最小能耗组播路由(Delay-ConstrainedMinimum-EnergyMulticastRouting，DCMEMR)Ih-]题，目的是为了保证多媒体应用的延迟约束，并同时减小组播的能量消耗；最大网络生存期最小代价组播路由(Maximum-Network．LifetimeMinimum-CostMulticastRouting，MaxNLMCMR)问题，目的是为了减小组播传输代价的同时延长网络的生存期；延迟抑制最大组播生存期组播路由(Delay．ConstrainedMaximum．LifetimeMulticastRouting，DCMaxLMR)I'口-J题，目的是为了保证多媒体应用的延迟约束，并同时延长组播的工作时间。 上海交通大学博士学位论文(2)提出了树结构编码法。树结构编码法用组播树本身来描述染色体，省略了遗传算法执行过程中的编码／解码操作，可以简化遗传算法，加速算法的收敛。(3)针对DCMEMR问题，提出基于遗传算法的延迟抑制最小能耗组播路由算法(GA—basedDelay-ConstrainedMinimum-EnergyMulticastRoutingAlgorithm，DCMEGA)。该算法的遗传算子能减小组播树的延迟和能量消耗，加速算法的收敛。实验结果证明该算法构造的组播树不仅满足延迟抑制条件，而且能量消耗最小，并且该算法能快速收敛。(4)针对MaxNLMCMR问题，提出基于遗传算法的最大网络生存期最小代价组播路由算法(GA．basedMaximum-Network-LifetimeMinimum．CostMulticastRoutingAlgorithm，MaxNLMCGA)。该算法的遗传算子能减小组播树的传输代价和能量消耗，变异算子能延长网络生存期，加速算法的收敛。实验结果证明该算法构造的组播树不仅传输代价最小，而且网络生存期最长，并且该算法能快速收敛。(5)针对DCMaxLMR问题，提出基于遗传算法的延迟抑制最大组播生存期组播路由算法(GA-basedDelay．ConstrainedMaximum—LifetimeMulticastRoutingAlgorithm，DCMaxLGA)。该算法的遗传算子能减小组播树的延迟和能量消耗，变异算子能延长组播生存期，加速算法的收敛。实验结果证明该算法构造的组播树不仅满足延迟抑制条件，而且组播生存期最长，并且该算法能快速收敛。关键词：无线AdHoc网络，QoS路由，组播，遗传算法，能量II ABSTRACTRESEARCHoNGENETICALGORITHMBASEDQOSMULTICASTROUTINGINⅥ咖LESSADHOCNETWORKSABSTRACTQoS(QualityofService)mukicastroutingproblemisoneofthemostdifficultproblemsofnetworkoptimization．Therunningtimeandcostincreasegreatlywiththeexpansionofnetworksize．SinceGA(GeneticAlgorithm)hasstrongadaptability,roubustnessandflexibility,itisanimportantmeansofsolvingQoSmulticastroutingproblem．SincenodeenergyinaWANETislimited，unlikewirednetwork，QoSmulticastroutinginaWANETmustconsiderenergyconsumption．Withtherapiddevelopmentofmultimediaapplications，QoSmulticastroutingalsoneedtoconsiderthetransmissiondelayandcost．BasedonthecharacteristicsofWANETs，thisdissertationstudiestheQoSmulticastroutingproblemconsideringtransmissiondelay,cost，energyconsumption，networklifetimeandmulticastlifetime，whicharesupposedbyBGPRoutingProtocolHardwareAccelerationProgramandIPTrafficDetectionTechnologyProgram．Themaincontributionsofthisdissertationareasfollows：(1)ThreeQoSmulticastroutingproblemsinaWANETarepresented，i．e．，DCMEMR(Delay-ConstrainedMinimum-EnergyMulticastRouting)problem，MaxNLMCMR(Maximum-Network—LifetimeMinimum-CostMulticastRouting)problem，andDCMaxLMR(Delay-ConstrainedMaximum-LifetimeMulticastRouting)problem．DCMEMRproblemaimstoguaranteethedelayconstraintformultimediaapplicationsandreducetheenergyconsumptionsimultaneouslyMaxNLMCMRproblemaimstoreducethemulticasttransmissioncostandprolongthenetworklifetimesimultaneouslyDCMaxLMRproblemaimstoguaranteethedelayconstraintformultimediaapplicationsandprolongthemulticastlifetimesimultaneously．(2)Treestructureencodingmethodforthemulticasttreewaspresented．Thisencodingschemerepresentsachromosome谢t11themulticasttreedirectly．Wi血thismethod，encoding／decodingoperationsareomittedintheprocessofevolutionofGAIII 上海交通大学博士学位论文(GeneticAlgorithm)，whichsimplifiestheGAandacceleratestheconvergencespeedofGA．(3)DCMEGA(GA—basedDelay-ConstrainedMinimum-EnergyMulticastRoutingAlgorithm)fortheDCMEMRproblemWaspresented．Thegeneticoperatorsofthisalgorithmreducethetransmissiondelayandenergyconsumptionofmulticasttrees，thusacceleratingtheconvergencespeedofthealgorithm．Experimentresultsshowthatthemulticasttreefoundbythisalgorithmnotonlyguaranteethedelayconstraint,butalsohastheminimumenergyconsumption．Furthermore，thisalgorithmconvergesquickly．(4)MaxNLMCGA(GA-basedMaximum-Network．LifetimeMinimum．CostMulticastRoutingAlgorithm)fortheMaxNLMCMRproblemWaspresented．Thegeneticoperatorsofthisalgorithmreducethetransmissioncostandenergyconsumptionofmulticasttrees，andmutationoperatorprolongsthenetworklifetime，thusacceleratingtheconvergencespeedofthealgorithm．Experimentresultsshowthatthemulticasttreefoundbythisalgorithmnotonlyhastheminimumtransmissioncost，butalsohasthelongestnetworklifetime．Furthermore，thisalgorithmconvergesquickly．(5)DCMaxLGA(GA—basedDelay．ConstrainedMaximum．LifetimeMulticastRoutingAlgorithm)fortheDCMaxLMRproblemWaspresented．Thegeneticoperatorsofthisalgorithmreducethetransmissiondelayandenergyconsumptionofmulticasttrees，andmutationoperatorprolongsthemulticastlifetime，thusacceleratingtheconvergencespeedofthealgorithm．Experimentresultsshowthatthemulticasttreefoundbythisalgorithmnotonlyguaranteethedelayconstraint，butalsohasthelongestmulticastlifetime．Furthermore，thisalgorithmconvergesquickly．Keywords：WirelessAdHocnetwork，QoSrouting，Multicast，Geneticalgorithm，EnergyIV 表格索引表1．1常见应用的服务质量需求⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3表1-2三类度量的例子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．4表3．3编码方法比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46V 插图索引图1．1网络通信方式(a)单播：(b)组播⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．2图1．2路径选择(a)网络拓扑；(b)最短跳数路径；(c)最短距离路径：(d)最大带宽路径⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯!；图2．1Hwang的编码机制⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯23图2．2遗传算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26图2．3基本遗传算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26图2-4轮盘赌选择例子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯30图2．5遗传算法的均衡搜索实现⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32图3—1可行性和合法性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯36图3-2染色体解码为问题的解⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯37图3．3／7×n一维二进制编码(a)网络拓扑；(b)组播树及其编码⋯⋯⋯⋯⋯⋯⋯⋯⋯．．39图3．4向量表示法(a)网络拓扑；(b)组播树及其编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40图3．5父节点表示法(a)网络拓扑；(b)组播树及其编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40图3-6Priifernumber编码算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯41图3．7Priifernumber编码例子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯42图3．8Prflfernumber解码算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43图3-9ST编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯44图3．10ST编码算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．44图3．11ST解码算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．45图3．12树结构编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。45图3．13树节点结构声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．46图4．1组播树能量消耗计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯52图4．2DCMEGA算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。53图4．3DCM匣GA算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯53图4．4DCMeGA交叉算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯56图4．5交叉运算的例子(延迟抑制3=25)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯57图4-6DCMEGA变异算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．58图4．7路由成功率比较(组播组节点数：网络节点数的20％．30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯63图4．8能量代价比(组播组节点数：网络节点数的20％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯64图4-9能量代价比(组播组节点数：网络节点数的30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯64图4．10运行时间(组播组节点数：网络节点数的20％．30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。65图5．1MaxNLMCGA算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯70图5．2MaxNLMCGA算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。70图5．3Ma．xNLMCGA交叉算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72图5．4MaxNLMCGA变异算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯74 图5．5组播树(链路上的数字表示两个节点之间的距离)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．75图5．6传输代价比(组播组节点数：网络节点数的20％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．79图5．7传输代价比(组播组节点数：网络节点数的30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．79图5．8网络生存期比(组播组节点数：网络节点数的20％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．80图5-9网络生存期比(组播组节点数：网络节点数的30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．80图5．10运行时间(组播组节点数：网络节点数的20％．30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．81图6．1DCMaxLGA算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯86图6．2DCMaxLGA算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯86图6．3DCMaxLGA交叉算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯88图6．4DCMaxLGA变异算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯90图6．5组播树(链路上的数字表示两个节点之间的距离)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．91图6．6路由成功率比较(组播组节点数：网络节点数的20％．30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯95图6．7组播生存期比(组播组节点数：网络节点数的20％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．95图6．8组播生存期比(组播组节点数：网络节点数的30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．96图6．9运行时间(组播组节点数：网络节点数的20％．30％)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯96vIII ACOBSMACBTCDKSDARP!ADCMaxLGADCMaxLMRDCM匣GADCM匣~ⅡL缩略语表AntColonyOptimizationBoundedShortestMulticastAlgorithmCore．basedTreeConstrainedDijkstraHeuristicDefenseAdvancedResearchProjectsAgencyGA-basedDelay-ConstrainedMaximum-LifetimeMulticastRoutingAlgorithmDelay-ConstrainedMaximum-LifctimeMulticastRoutingGA-basedDelay-ConstrainedMinimum-EnergyMulticastRoutingAlgorithmDelay-ConstrainedMinimum—EnergyMulticastRoutingDFSDepth·FirstSearchAlgorithmDNADeoxybonucleicAcidGAGeneticAlgorithmGAlibGeneticAlgorithrnlibGloMoGlobleMobileInformationSystemsHGAHaghighat’SGAIETFIntemetEngineeringTaskForceKPPKompella-Pasquale·PolyzosHeuristicLDTLeast-DelayMulticastRoutingAlgorithmMAlmTMobileAdHoeNetworkMaxNMC6滔6滔．basedMaximum-Network．LifetimeMinimum-CostMulticastRoutingAlgorithmM幻：NLMCMRMaximum-Network-LifetimeMinimum．CostMulticastRoutingIX蚁群算法BSMA算法基于核心的树CDKS算法美国国防部高级研究计划署基于遗传算法的延迟抑制最大组播生存期组播路由算法延迟抑制最大组播生存期组播路由基于遗传算法的延迟抑制最小能耗组播路由算法延迟抑制最小能耗组播路由深度优先搜索算法脱氧核糖核酸遗传算法G舢ib库全球移动信息系统Haghighat的遗传算法Internet工程任务组KPP算法最短延迟组播路由算法移动自组网基于遗传算法的最大网络生存期最小代价组播路由算法最大网络生存期最小代价组播路由 Node’SIDIdentificationNPCPANPDAPIUJETQoSRSSASBTSR节点标识号Non-DeterministicPolynomialComplete多项式复杂程度的非确定性完全PerSonalAreaNetwork个人局域网PersonalDigitalAssistant掌上电脑PacketRadioNetwork分组无线网QualityofServiceRayward·SmithHeuristicSimulateAnnealSource．based1heSuccessRatioSTEncodingSequenceandTopologyEncodingSI瓜ANTMⅥ硝NETYGASurvivableAdaptiveNetworkTakahashi—MatsuyamaHeuristic服务质量RS算法模拟退火算法基于源的树路由成功率序列拓扑编码高残存性自适应网络TM算法WirelessAdHocNetwork无线自组网Yen’SGAXYen的遗传算法 目录基于遗传算法的无线ADHOC网络QOS组播路由研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．I摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．IABSTRACT⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯III表格索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯v插图索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯VII缩略语表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．Ⅸ目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯XI第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯l1．1．1组播的概念和特点⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．1．2QoS的概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。31．1．3QoS组播路由的概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．51．1．4无线AdHoc网络的概念和特点⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。61．1．5无线AdHoc网络QoS组播的研究意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．81．2无线ADHOC网络QoS组播的原理与研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯91．2．1组播路由的实现⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．91．2．2QoS组播的研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．111．2．3无线AdHoc网络QoS组播路由面临的问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯141．2．4无线AdHoc网络QoS组播的研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯151．3论文提出的研究问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。151．3．1延迟抑制最小能耗组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯161．3．2最大网络生存期最小代价组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯161．3．3延迟抑制最大组播生存期组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯161．4论文的内容安排和创新工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。171．4．1内容安排⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯171．4．2创新工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯18第二章遗传算法解决QOS组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯212．1遗传算法解决QoS组播路由问题有效性分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．21XI 上海交通大学博士学位论文2．2遗传算法解决QoS组播路由问题的研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。222．3遗传算法的基本原理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯242．3．1遗传算法的生物进化基础⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯242．3．2遗传算法的基本原理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯242．4遗传算法设计相关工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯252．4．1编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．272．4．2群体初始化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯272．4．3适应度评估⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯282．4．4选择算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯292．4．5交叉算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯302．4．6变异算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯312．5遗传算法收敛性分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯312．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯33第三章树结构编码法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。353．1组播树编码方法的研究意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯353．2编码设计需要考虑的问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯353．2．1编码技术分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯353．2．2可行性和合法性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯363．2．3编码设计需要满足的性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯373．3现有的组播树编码方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯383．3．1组播树节点编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯383．3．2n×玎一维二进制编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．383．3．3特征向量表示法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯393．3．4父节点表示法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯403．3．5PrllferNumber编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4l3．3．6序列拓扑编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯433．4本文提出的编码方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯453．5编码方法分析比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯463．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46第四章延迟抑制最小能耗组播路由算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。494．1延迟抑制最小能耗组播路由的研究意义和现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯494．2问题的提出⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯494．2．1网络模型的建立⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯494．2．2能量消耗模型的建立⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯504．2．3延迟抑制最小能耗组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯524．3DCMEGA算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．524．3．1编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．544．3．2群体初始化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯544．3．3适应度函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯554．3．4选择算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯55XII 目录4．3．5交叉算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯564．3．6变异算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯584．4理论分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．594．4．1算法收敛性分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯594．4．2与其他算法分析比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯604．5实验分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．624．5．1实验设置⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯624．5．2算法性能评价指标⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯624．5．3路由成功率比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯634．5．4能量消耗比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯644．5．5运行时间比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯654．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。65第五章最大网络生存期最小代价组播路由算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．675．1最大网络生存期最小代价组播路由的研究意义和现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯675．2问题的提出⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。675．2．1网络模型的建立⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯675．2．2网络生存期模型的建立⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯685．2．3最大网络生存期最小代价组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯695．3MAXNLMCGA算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．695．3．1编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．7l5．3．2群体初始化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯715．3．3适应度函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯7l5．3．4选择算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯715．3．5交叉算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯725．3．6变异算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯735．4理论分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。765．4．1算法收敛性分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯765．4．2与其他算法分析比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯765．5实验分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。775．5．1实验设置⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯775．5．2算法性能评价指标⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯785．5．3传输代价比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯795．5．4网络生存期比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯805．5．5运行时间比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯815．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。8l第六章延迟抑制最大组播生存期组播路由算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．836．1延迟抑制最大组播生存期组播路由的研究意义和现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯836．2问题的提出⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。836．2．1网络模型的建立⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯83 上海交通大学博士学位论文6．2．2组播生存期模型的建立⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯846．2．3延迟抑制最大组播生存期组播路由问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯856．3DCMAXLGA算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯856．3．1编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。876．3．2群体初始化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯876．3．3适应度函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯876．3．4选择算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯876．3．5交叉算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯886．3．6变异算子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯896．4理论分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯926．4．1算法收敛性分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯926．4．2与其他算法分析比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯926．5实验分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯936．5．1实验设置⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯936．5．2算法性能评价指标⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯946．5．3路由成功率比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯956．5．4组播生存期比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯956．5．5运行时间比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯966．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯97第七章总结和展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯997．1全文内容总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯997．2工作展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．100参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯103致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．115攻读博士学位期间的科研成果和项目经历⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯117XⅣ 1．1研究背景1．1．1组播的概念和特点第一章绪论随着各种多媒体业务的飞速发展与普及，如视频会议，网络游戏，远程教育，视频点播等等，网络需要将数据信息从一个源节点发送到多个目的节点。因此，网络必须具备点到多点的通信能力。传统的单播(u11icast)【lJ通信技术是一种点到点的通信方式，它在发送者(源节点)和每一个接收者(目的节点)之间分别实现点对点的网络连接。如果一个发送者需要同时向多个接收者传输相同的数据信息，对于这些信息，单播通信技术会复制多份(接收者的数量越多，复制的份数越多)相同的数据分组，然后把这些数据分组分别发送给对应的接收者。采用单播传输方式来实现点到多点的通信是一种效率极低的方法，它会使大大增加发送者的负担，使得传输延迟变长，甚至会造成网络拥塞，从而造成网络资源浪费和服务质量下降。为了使得大量信息在一个发送者和多个接收者之间能够有效地传输，一种新的信息传输方式一一组播【2J就应运而生。组播可以在一个发送者和多个接收者之间实现点对多点的网络通信，并能将相同的信息有效地从发送者传输到多个目的节点。在具有组播通信技术的网络中，源节点只需要向网络发送一份数据分组即可，网络节点能够根据组播路径将数据分组复制到必要的路径上，从而完成通信任务。因此，组播技术可以大大提高数据传输效率，有效利用网络资源(如节省网络带宽)，并降低发生网络拥塞的可能性，从而提高网络服务质量。为了阐述采用组播通信实现点到多点通信的优势，图1．1给出了单播通信和组播通信的数据传输方式。如图1．1(a)所示，当主机A(源主机)需要向主机C、F、G(目的主机)发送一个相同的数据分组时，单播通信必须为每一个接收主机制作一份数据拷贝，每个拷贝对应一个接收者。源主机轮流地将这些数据拷贝发送出去，网络将每个数据拷贝单独路由，分别发送至对应的目的主机。如果采用组播通信技术，如图 上海交通大学博士学位论文1-1Co)所示，源主机A只需要向网络发送一份数据拷贝，网络在到达每个接收者路径上的最后一个节点(路由器或主机)处复制这份数据，然后把这些数据发送至各个目的主机。目的主机图1-1网络通信方式(a)单播；(b)组播Fig．1—1Networkcommunicationmethod(a)unicasting；(b)multicasting从图1．1我们可以看出，与单播通信技术相比，采用组播通信技术实现点到多点的通信具有以下优势：(1)节约网络带宽资源。组播通信技术能够有效地利用网络带宽资源。当源节点向多个目的节点发送相同的数据信息时，如果采用单播通信技术，源节点会大量复制相同的数据信息，并将这些数据依次发送到网络中。因此，单播通信技术占用的网络带宽将随着目的节点数量的增加而急剧增加，特别是当传输的数据信息量很大时更为明显。如果采用组播通信技术，由于只需要向网络发送一份数据拷贝，并在必要的路径上复制此数据，因此会大大减小网络带宽的消耗，节约网络带宽。(2)减轻源节点的负载。由于单播通信技术需要在源节点处为每个目的节点制作一份相同的数据拷贝，并要求源节点将这些数据拷贝发送到网络中，因此，当目的节点的数量增加时，源节点的负载会急剧增加。而组播技术只需要源节点为每个组播服务发送一份数据拷贝即可，与目的节点的数量(即用户数量)无关，因此，即使目的节点的数量大大增加也不会增加源节点的负载。所以，与单播通信相比，组播通信技术可以降低网络业务对源节点的性能要求，从而提高网络业务运行的稳定性。 第一章绪论(3)降低网络负载。由于组播能够降低占用的网络带宽，占用网络带宽的减小会使得网络节点的负载也相应降低。1．1．2QoS的概念QoS是网络应用业务对网络传输服务提出的一组可度量的服务质量要求【3J。各种网络应用的QoS要求可以用一系列参数指标(metric)【4】来描述。这些参数指标对服务质量的保证起着至关重要的作用。路由算法在选择路径时必须要以这些参数指标为依据进行路径选择，从而保证服务质量。常用的QoS参数指标主要包括以下几种：表1-1常见应用的服务质量需求Table1-1Networkapplications’quality．of-servicerequirements(1)路径长度：源节点到目的节点的总路径长度，可以用路径所覆盖的节点个数(跳数)或路径的实际距离长度来表示。(2)带宽(bandwidth)：传输介质(网络链路)的有效通信容量，即链路能达到的最大吞吐量。(3)延迟(delay)：数据分组从发送端传输到接收端所经历的时间，它包含了主机的编码／解码时间、数据分组在传输介质中的传输时间、数据分组在交换机或路由器中的排队时间和处理时间等。(4)延迟抖动(delayjitter)：分组延迟的变化，即分组从发送方传输到接收方所经历的延迟变化。(5)包丢失率(packetlossratio)：在某段时间内，丢失的数据分组的总数占所传输的数据分组总数的比例。表1-1给出了一些常见的应用，以及它们对各种QoS需求的严格程度。在计算 上海交通大学博士学位论文机网络的分析中，通常将这些参数指标与网络链路相关联，也就是说，把这些参数看做是链路的属性。一条传输路径上某个参数指标的总值需要根据这个参数指标的数学特性来进行计算。不同的数学特性，计算方式是不同的。根据这些参数指标的数学特性，我们通常把这些参数指标分为三类：(1)加性度量(additivemetric)。(2)乘性度量(multiplicativemetric)。(3)凹性度量(concativemetric)。表1-2三类度量的例子Table1-2ExamplesofthreekindsofmetriCS表1．2针对三类度量分别给出了一些例子。对同一种类的度量，一条路径上总度量值的计算方法是相同的。假设网络中的每条链路e，具有一个加性度量％“Pf)、一个乘性度量Cm”t(e3和一个凹性度量c蜊@J，p(s，f)表示从节点S到节点f的路径，JJB／／_,：(1)加性总度量c础仞0，力)‰(p(驯))=∑％(q)(1．1)ejep(s，r)(2)乘性总度量％“如@，0)Cm“(p(s，f))=1一兀(1--Cm。水，))(1．2)eiep(s，f1(3)凹性总度量Cc鲫p@，0)巳铆(p(s，f))=所似(cc伽(吃))(1．3)根据不同的参数指标进行路径选择，得到的最优路径是不同的。换句话说，参数指标会影响路径选择的结果。图1．2给出了根据三个不同的参数指标选择最优路径的过程。图1-2(a)是网络拓扑，蓝色链路的带宽为1Gbps，黑色链路的带宽为155Mbps，链路上的数字表示链路的距离长度，节点A是源节点，节点H是目的节点。如果以跳数为参数选择最优路径，则最短跳数路径是A．D．H，如图1-2(b)所示。如果以距离为参数选择最优路径，则最短距离路径是A-C—F．H，如图1-2(c)所示。如果以带宽为4 第一章绪论参数选择最优路径，则最大带宽路径是A⋯BEG．H，如图1-2(d)所示。(a)网络拓扑(b)最短跳数路径(c)最短距离路径(d)最大带宽路径图l-2路径选择(a)网络拓扑；(b)最短跳数路径；(C)最短距离路径；(d)最大带宽路径Fig．1-2Pathselection(a)originaltopology；(b)shortesthoppath；(c)shortestdistancepath；(d)maximumbandwidthpath1．1．3QoS组播路由的概念为了实现组播通信，确定最优组播路径是非常重要的。确定从源节点到多个目的节点的通信路径的过程称为组播路由(multicastrouting)[5,6】。目前，实现组播路由的方法通常是采用基于树的转发方法【|卜10】，即构造连接源节点和所有目的节点的组播树。QoS组播路由是根据网络当前可用资源和网络业务对服务质量的要求，找出一棵连接源节点和所有目的节点的组播树，并且这棵组播树满足QoS约束条件。各种网络应用业务对服务质量的要求可以用一组QoS度量(一组QoS参数指标)来描述，这组QoS度量通常称为QoS约束集。研究者已经证明带约束的QoS组播路由问题是多项式复杂程度的非确定性完全问题(Non．DeterministicPolynomialCompleteProblem，NPC)t111。 上海交通大学博士学位论文1．1．4无线AdHoe网络的概念和特点“AdHoc”一词最早源自拉丁语，意思是指“专用的”、“特定的”Il2，13J。AdHoc网络是一种具有特殊用途的网络，它通常又被叫做“无固定设施网”、“自组织网”和“多跳网络”等等。IEEE802．11标准委员会把这种网络称为“AdHoc网”，而Intemet工程任务组(IntemetEngineeringTaskForce，IETF)把这种网络称为移动自组网(MobileAdHocNetwork．MANET)。AdHoc网络是通过自组织的方式来实现网络互联并进行通信的可移动网络。它是由一组具有无线收发装置的移动终端组成，是一种多跳、无中心、临时性的自治系统。与传统的无线网络(如蜂窝移动通信网)不同，AdHoc网络不需要依赖任何预先搭建好的固定网络基础设施(如基站、路由器等)。AdHoc网络中的每个用户终端可以自由移动，用户终端的无线覆盖范围是有限的。如果两个用户终端不处于对方的覆盖范围之内，那么它们是无法直接进行通信的，只能借助于其他节点进行分组转发(即多跳)。因此，AdHoc网络中的每个用户终端同时具有主机和路由器两种功能。作为主机，需要在用户终端运行各种各样的面向用户的应用程序；作为路由器，需要在用户终端运行各种路由协议，实现路由表的维护和分组转发。最初，AdHoc网络是应用于军事领域。1972年，美国国防部高级研究计划署(DefenseAdvancedResearchProjectsAgency,DARPA)资助了分组无线网(PacketRadioNetwork，PRNET)项卧14】，对AdHoc网络的研究从此开始。PRNET项目主要是研究分组无线网在军事领域(如战场环境中)的数据通信。此项目完成后，在1983年，DARPA又资助了高残存性自适应网络(SurvivableAdaptiveNetwork，SURAN)项卧DJ。DARPA项目的目标主要有两个，一个是研究如何将PRNET项目中取得的研究成果进行扩展，使这些研究成果可以应用到更大规模的网络中去；另一个是研发自适应的网络协议，这种网络协议能够适应快速变化的战场环境。1994年，DARPA又资助了全球移动信息系统(GlobleMobileInformationSystems，GloMo)项目的研究【l扣博J。GloMo项目的研究目标是想利用便携式手持设备为类似临时办公环境等这样的一些临时场合和军事领域提供一种可以在任何地点、任何时间进行通信的移动通信技术，并且要求这种通信技术具有较强的鲁棒性。AdHoe网络就是综合了上述三个项目的组网思想而产生的一种新型网络构架技术。1991年，IEEE正式成立了802．11标准委员会，提出将AdHoe网络应用于非军事领域。从此，对AdHoe网络的非军用领域研究便开始了。1997年，mTF成立了专门的AdHoc网络工作组，专门研究适用于中等规模AdHoe网络(具有几十个到几百个节点)的路由算法。此后，美国的许多公司、研究所和大学都积极地参与到研 第一章绪论究AdHoc网络的队伍中，并取得了许多有价值的研究成果。由于AdHoc网络具有组网灵活、投资少、鲁棒性强等优点，它在战场环境、紧急救助、抢险救灾、环境保护和检测、移动会议、以及各种商业应用中都具有十分重要的作用。AdHoc网络的特点可归纳为以下几点：(1)动态变化的网络拓扑结构。在AdHoc网络中，由于用户终端可以自由移动(以任意速度、任意方式)、用户终端可以自由开机或关机、无线发射装置的发射功率可变、无线信道的相互干扰和衰落、以及地形和气候等综合因素的影响，由节点和节点之间的无线信道组成的网络拓扑结构是动态变化的，而且变化的方式和速度都是不可预测的。(2)无中心网络的自组织性。由于构建AdHoc网络不需要依赖任何预设的网络基础通信设施，因此AdHoc网络具有一定的独立性。AdHoc网络没有严格的控制中心，所有的节点具有相同的地位。每个节点可以随时加入或离开网络。通常，某个节点的故障不会影响整个网络的正常运行，具有很强的抗毁坏性。节点与节点之间通过各种网络协议协调各自的行为，共同完成各种网络通信工作。AdHoc网络具有很强的自组织性。(3)移动终端资源有限，网络扩展性不强。在AdHoc网络中，移动终端的资源是非常有限的(如内存，电池能量，CPU等)。由于移动终端同时要实现主机功能和路由器功能，因而使得终端上有限的资源显得更加紧张。再加上AdHoc网络中各种控制信息的交换会消耗大量的网络资源，从而限制了网络的扩展性。(4)有限的网络带宽。由于AdHoc网络使用无线信道作为传输介质，无线信道本身的物理特性决定了它所能提供的网络带宽要远远小于有线信道。另外，很多因素会对无线信道的传输带宽造成影响，如竞争无线信道所产生的碰撞、信道间干扰、信号衰减、以及噪音干扰等，终端用户实际上能够使用的有效带宽要远远小于理论上的最大值。所以，AdHoc网络的带宽资源是非常珍贵的。(5)生存期短。由于AdHoc网络中各个移动终端的能量是有限的，因此，与有线网络相比，AdHoc网络的生存期一般非常短。(6)多跳组网。由于AdHoc网络中各个移动终端的发射功率有限，因此，每个移动终端的通信覆盖范围是有限的。当一个终端需要与其覆盖范围以外的终端进行通信时，此时需要借助于中间节点来转发信息(即多跳转发)。多跳是研究AdHoc网络路由协议的基 上海交通大学博士学位论文本前提。AdHoc网络的多跳路由与有线网络不同，有线网络的多跳路由是由专门的路由设备(如路由器)来完成的，而AdHoc网络中的多跳路由是由普通的网络节点(用户终端)来完成的【19J。(7)存在单向的无线信道。由于各个用户终端的发射功率不同，再加上地形、气候等因素对无线信道的影响，使得在AdHoc网络中存在单向的信道。(8)安全性差。由于AdHoc网络自身的一些特点，如AdHoc网络无控制中心、采用分布式控制方式、使用无线信道、节点电池能量有限等，使得AdHoc网络比有线网络更容易受到网络攻击，如被动窃听、主动入侵、拒绝服务和剥夺“睡眠”等等。再加上AdHoc网络直接使用移动终端实现路由功能，不存在专门的命名服务器和目录服务器等网络设施，使得AdHoc网络的安全问题变得非常复杂。1．1．5无线AdHoe网络QoS组播的研究意义首先，由于AdHoe网络不需要依赖任何事先搭建好的网络基础设施，这使得它在军事和民用领域都有着非常广泛的应用前景。它的应用场合主要有以下几类：(1)军事通信。通常，在大多数战场环境中没有像基站这样的预先搭建好的网络基础设施(或者网络基础设施遭到破坏)，此时，军事人员和军用装备可以利用AdHoc网络技术进行通信。由于AdHoc网络技术具有组网快速方便、抗毁坏性强等特点，它在战场环境中具有重要的地位。(2)临时场合。AdHoe网络快速、简单的组网能力使得它适用于各种临时通信，如移动会议、庆典和展览会等。(3)抢险救灾和紧急服务。当发生自然灾害或因为某些意外情况而导致网络设施无法正常使用时，可以通过AdHoc网络技术快速地搭建临时网络，以确保抢险救灾人员和医疗人员等的应急通信能够正常进行，这对抢险和救灾等工作具有非常重要的意义。(4)个人通信。AdHoc网络技术还可以应用到个人局域网(PersonalAreaNetwork，PAN)qb去。借助于AdHoc网络技术，不仅可以实现掌上电脑(PersonalDigitalAssistant，PDA)和 第一章绪论智能手机等个人电子设备之间的通信，还可以实现个人局域网之间的多跳通信。(5)传感器网络。在很多应用场合，人们常常使用传感器来探测环境参数。通过AdHoe网络技术，可以将分布在不同地点的大量传感器组成一个网络，使得传感器与传感器之间、传感器与控制中心之间可以进行通信。这样，传感器采集的数据就可以传回控制中心，人们通过控制中心就可以控制每个传感器，从而使得监测工作更加方便有效。(6)商业应用。可以通过AdHoc网络技术建立移动医疗监护系统等。(7)固定网络的接入网。可以通过AdHoe网络技术扩展蜂窝移动通信网的通信模式及其覆盖范围。其次，随着各种多媒体应用(如视频会议，远程教育，视频点播)的发展和网络规模的不断扩大，各种网络资源变得越来越珍贵。如何有效地利用各种网络资源成为当今网络研究的重要课题。由于组播能够有效地利用网络资源、减小网络拥塞和节点负载，在AdHoc网络中研究组播是非常重要和有价值的。最后，随着多媒体应用的飞速发展，需要在AdHoe网络中传输话音、图像等多媒体数据。这些多媒体业务对AdHoc网络的网络延迟、服务带宽和延迟抖动等服务质量提出了越来越高的要求【20。23】。因此，AdHoe网络需要针对不同的应用需求提供相应的服务质量保证。基于以上三个原因，研究AdHoc网络的QoS组播路由问题是非常有价值的。另外，由于AdHoc网络自身的特点，用于有线网络的传统的路由协议无法直接应用到AdHoc网络中。再加上AdHoe网络的节点计算能力有限、存储容量较低、节点能量有限、网络拓扑动态变化等因素，使得AdHoe网络路由算法的设计工作变得更加复杂。因此，路由算法设计已经成为AdHoe网络研究的重点和热点问题。1．2无线AdHoe网络QoS组播的原理与研究现状1．2．1组播路由的实现目前，基于树的转发方式是实现组播路由最常用的方法。基于树的方法是构造一棵连接源节点和目的节点的组播树。信息由源节点发出，然后沿着这棵组播树发送到所有目的节点。组播树通常分为两类，一类是基于源的树(Source-basedTree，SBT)[24。261，另一类是基于核心的树(Core．basedTree，CBT)[27‘291，基于核心的树又称为 上海交通大学博士学位论文共享树(sharedtree)。基于源的树以组播源为根节点并连接所有的目的节点。如果多播组(组播源节点和所有目的节点)中存在多个组播源，那么，需要分别为每一个组播源建立一棵相应的组播树。因为不同的组播源沿着各自对应的组播树发送信息，因此基于源的树有利于网络中数据流的均衡。此外，在建立基于源的树的过程中可以根据网络应用的QoS需求，找出连接组播源节点和目的节点的最优路径，从而优化网络资源并改善服务质量。但是，采用基于源的树来实现组播通信也存在缺点，它需要为每个组播源分别建立各自对应的组播树，而当组播数据流量较小时，构造组播树的开销相对较大。与基于源的树相比，基于核心的树只需要为一个多播组建立一棵组播树即可，所有的多播组成员共享这棵组播树。基于核心的树需要选定一个节点作为树的组播中心。在选择组播中心时，要尽量使组播中心的位置靠近多播组的中心位置。在构建基于核心的组播树时，组播中心应位于树的根节点处。每个组播消息都首先被传送到组播中心，然后沿着这棵组播树传送给每个接收者。采用基于核心的树实现组播通信，需要恰当地选取组播中心，如何有效地选取组播中心是件相当复杂、困难的工作。因而，找出最优的基于核心的树是非常困难的。基于核心的树并不能保证从源主机到各个目的主机的路径是最优的。并且，在基于核心的树中，所有组播源的组播消息都需要通过组播中心(根节点)来转发分组，这会增加会增加组播中心的负担，使得产生单点故障的可能性大大增加。组播路由是通过组播路由算法实现的。组播路由算法是路由协议的重要组成部分，用来确定从源节点到所有目的节点的组播树。组播路由算法可以根据不同的标准进行分类：(1)静态组播路由算法和动态组播路由算法。根据节点是否可以随时加入或离开多播组，可将组播路由算法分为静态算法【30】和动态算法plJ两类。静态组播路由算法根据初始的多播组成员构造一棵组播树，然后沿着这棵组播树传输信息。一旦组播树建立好后，如果多播组成员发生变化，静态组播路由算法不能根据变化迅速调整组播路径，对组播路径的调整需要经过一段时间后才能进行。然而，如果多播组成员或网络状态发生变化，动态组播路由算法可以根据变化及时地调整组播路径。但是，如果动态路由算法对组播路径调整过于频繁，会引起通信的不稳定，使得服务质量下降。另外，动态组播路由算法会消耗更多的网络资源。(2)集中式组播路由算法和分布式组播路由算法。组播路由算法按照其实现方式，可以分为集中式算法【32】和分布式算法【331两类。10 第一章绪论集中式组播路由算法又称为源路[扫(source．basedrouting)算法，它是由源节点掌握了整个网络的状态信息后，由源节点进行组播路由计算(即确定组播树)。分布式组播路由算法不需要节点掌握整个网络的状态信息，每个节点在只需掌握网络的局部状态信息，路由计算工作由路径上的中间节点来共同完成。这两类算法各有优缺点。源路由机制不会产生路由环，简单快速，容易实现。但是，如果采用源路由机制，网络中的每个节点都需要维护整个网络的状态信息。当网络规模较大时，源路由机制的开销较大。虽然分布式路由算法不需要维护整个网络的状态信息，但是分布式路由算法比源路由算法复杂，并且速度较慢。(3)分层路由算法。随着网络规模的不断扩大，网络中每个节点存储的路由表也会随着快速增大。庞大的路由表不仅占用大量的网络节点资源(如内存)，而且需要消耗大量的CPU时问来进行查表从而找出转发路径。另外，为了维护庞大的路由表，还需要消耗大量的网络带宽进行网络状态信息的交互。因此，为了避免路由表规模过于庞大而引起的问题，出现了分层路由(hierarchicanrouting)}Ell,$1J[34,35】。分层路由机制将网络划分成不同的层次，每个层次由多个区域组成，逐层路由。每个区域内的节点只需了解本区域内的网络状态信息，因而大大减小了路由表的规模，节省了网络资源。研究者己经证明基于QoS约束的组播路由问题是NPC问题【36刈】，用传统的路由算法难以解决。大量的研究提出了各种新颖的算法来解决QoS组播路由问题。我们大致把这些算法分成两类：一类是启发式算法【4l舶】，另一类是人工智能算法。其中，用于解决QoS组播路由问题的人工智能算法又可分为：神经网络(neuralnetwork)[47-521，模拟退火算法(SimulateAnneal，SA)[53,54】，蚁群算法(AntColonyOptimization．ACO)t55-63】和遗传算法【件176】。组播通信技术通过组播树将信息发送到所有目的节点。QoS组播路由的目的是找出满足QoS约束的组播树。过去大量对组播路由的研究主要集中在如何减小组播树的传输代价【_7。7。80】。组播树的传输代价等于构成组播树的所有边的传输代价的总和。通常，最小代价树被称为Steiner树【811。换句话说，Steiner树问题是找出最小代价组播树。求解QoS约束条件下的最优组播路由问题本质上是寻找满足约束条件的Steiner树问题。近年来，对基于QoS约束的组播路由问题的研究可以大致分为以下几类：延迟抑制最小代价组播路由问题[82-86]，带宽延迟抑制最小代价组播路由问题 上海交通大学博士学位论文[70,71,77,87-89]，度抑制的最小代价组播路由问题[90,911等。传统的路由算法很难解决基于QoS约束的组播路由问题，过去的研究往往采用启发式算法。用于解决Steiner问题的一些著名的启发式组播路由算法有RS算法(Rayward．SmithHeuristic)145l，TM算法(Takahashi．MatsuyamaHeuristic)146J和Chen-Nahrstedt算法mJ。用于解决延迟抑制最小代价组播路由问题的启发式算法有：KPP算法(Kompella-Pasquale．PolyzosHeuristic)⋯J，CDKS(ConstrainedDijkstraHeuristic)算法【42J和BSMA算法(BoundedShortestMulticastAlgorithm)[431。Chen-Nahrstedt算法是一个分布式算法。源节点采用分组扩散的方法沿着满足QoS约束条件的路径来发送探测报文。通过探测报文的扩散，找到满足QoS约束条件的最小代价路径，然后由这些路径构成组播树。1993年，Kompella提出的KPP算法用于求解延迟抑制的Steiner树问题。KPP算法主要分为三步：首先得到一个覆盖多播组并且满足延迟抑制的完全图，然后利用Prim算法得到一棵满足延迟抑制条件的最小生成树，最后用图中的路径替换最小生成树中的边。针对延迟抑制的Steiner树问题，Sun提出了CDKS算法。CDKS算法以Dijkstra算法为基础，首先计算出最小代价树，然后检查这棵最小代价树是否满足延迟抑制条件。如果组播树不满足延迟抑制条件，则重新计算得到另一棵最小代价树，然后把这两棵组播树合并得到新的组播树，使得合并后的新组播树满足延迟抑制条件。如果合并得到的组播树仍然不满足延迟约束，那么重复上述过程，直到找到满足延迟抑制条件的组播树为止(如果这样的组播树存在的话)。BSMA算法首先使用Dijkstra算法计算得到最小延迟组播树，然后用代价更小的路径替换最小延迟组播树上的边(替换过程要保证满足延迟抑制条件)，使得最小延迟组播树在满足延迟抑制条件的同时不断地减小组播树的总代价，从而得到最优解。KPP算法、CDKS算法和BSMA算法都是源路由算法，其中BSMA算法的精度最高(接近最优)，但是它的计算复杂度也最高。以上这些启发式算法都存在一个共同的问题：随着网络规模的扩大，计算时间会急剧增加。随着人工智能算法的不断发展，人们己尝试将一些智能算法用于解决各种复杂的最优解问题【92拼】。这些智能算法包括Hopfield神经网络(Hopfieldneuralnetwork)、模拟退火算法、蚁群算法和遗传算法。Chotipat等[471提出了基于Hopfield神经网络的算法来求解QoS组播路由问题。Hopfield神经网络是一种循环神经网络，具有输出到输入的反馈连接(反馈网络)。Hopfield神经网络用差分方程来表示它自身的状态变化。反馈网络的一大特点是具有稳定状态。如果把混合优化问题的目标函数转化为Hopfield神经网络的能量函数，把混合优化问题的变量看作神经网络的状态，那么Hopfield神经网络就可以用于求解基 第一章绪论于QoS约束的组播路由问题。但是，Hopfield神经网络能量函数系数的选择非常复杂，而且通常会引起不期望的解。另外，由于使用了连续的Hopfield神经网络，必须假设QoS组播路由问题的解是连续的，这使得问题变得更加复杂。模拟退火算法模拟了固体退火原理。首先将固体加热至高温，然后再让其慢慢冷却。加热时，固体内部的粒子会随着温度的升高而内能增大，粒子无序运动：固体慢慢冷却时，粒子的内能逐渐减小，粒子的运动逐渐变为有序。粒子在每个温度都达到平衡态，最后在常温时达到基态(常温时的内能最小)。用模拟退火算法求解混合优化问题时，混合优化问题的目标函数相当于金属的内能，优化问题的自变量的组合状态空间相当于金属内能的状态空间，优化问题的求解过程就是寻找使目标函数值最小的组合态的过程【95】。由Metropolis准则可知，粒子在温度丁时趋于平衡的概率为e-aE／kr，其中E表示温度丁时的内能，△E表示内能的改变量，k为玻尔兹曼常数。其中，温度丁演化为控制参数。模拟退火算法首先由初始解x和控制参数丁开始，对当前解反复执行“产生新解_计算目标函数差一接受或舍弃”的迭代过程，并逐步衰减控制参数丁的值，算法终止时的当前解即为最优解或准最优解。需要注意的是，退火过程是由冷却进度表(coolingschedule)控制的。冷却进度表包含了控制参数丁的初值、衰减因子△丁、每个丁值的迭代次数和停止条件S。尽管许多研究者己尝试用模拟退火算法求解QoS组播路由问题，但是由于它的参数很难控制，例如，如何设定温度丁的初始值(初始温度越高，搜索到全局最优解的可能性越大，但花费的计算时间也会随之增大；初始温度越低，计算时间越短，但搜索到的解的质量较差)、如何设定退火速度(同一温度下的“充分搜索”可以避免陷入局部最优，但这同样会增加计算时间)、采用何种温度管理方式(即什么样的降温方式能够在较短的时间内搜索到最优解)等，这大大影响了模拟退火算法的广泛应用，这些问题有待进一步研究。模拟退火算法原理简单、适用于并行处理、鲁棒性强，可用于求解各种复杂的组合优化问题，但是其收敛速度较慢，执行时间较长，算法性能与初始值密切相关，并且对算法参数非常敏感。蚁群算法最早是由MacroDorigo于1992年在他的博士论文“蚂蚁系统：通过一群合作机构实现优化”【96】中提出。蚁群算法是模拟蚂蚁寻找食物时发现路径的原理。一开始，所有蚂蚁并不知道食物位于什么地方，他们同时开始向西面八方寻找食物。一旦蚂蚁找到食物，它会立刻在当前位置释放一种挥发性的分泌物。通常这种分泌物被称为信息素。信息素有一种特性，它会随着时间的推移而渐渐挥发。信息素的浓度表明了当前位置距离食物所处位置的远近。通过对信息素的感知，越来越多的蚂蚁会向着有信息素的位置移动，这样就会有越来越多的蚂蚁找到食物。需要注意的是，并 上海交通大学博士学位论文不是所有的蚂蚁都会走相同的路径，少数蚂蚁会随机地开辟与其他蚂蚁不同的路径，这样可以避免算法陷入局部最优，使算法具有较好的全局搜索性能。如果这些蚂蚁开辟的新道路更短，那么，他们会通过释放信息素吸引更多的蚂蚁到这条路径上来。通过一段时间的搜索，会出现一条路径被大多数蚂蚁重复着(即算法趋于稳定)，从而这条路径就是最优路径或准最优路径。蚁群算法具有鲁棒性强和易实现分布式计算等优点，但是算法的难点在于如何确定蚂蚁释放信息素的方式和信息素随时间消失的方式问题。遗传算法是一种全局优化的自动搜索算法，它仅仅通过适应度函数和遗传操作(如交叉、变异、和选择)来控制搜索的方向和搜索的范围。遗传算法不依赖于问题本身的数学描述(仅通过适应度函数和遗传操作来搜索问题的解)[97】，因此具有很强的全局优化能力和并行性。由于遗传算法简单通用、鲁棒性强，适于并行处理，遗传算法己广泛用于求解各种网络优化／．J题【98。102J。在求解基于QoS约束的组播路由问题时，遗传算法可能会经过很多代的进化过程(进化代数越大，计算时间越长)。目前，已有大量研究提出了遗传算法的各种硬件实现，并证明了它们的计算速度是非常快的【103‘1051。另外，在求解基于QoS约束的组播路由问题时，遗传算法对网络规模并不十分敏感【106,107]，即遗传算法的计算时间不会随着网络规模的扩大而急剧增大。所以，用遗传算法来求解基于QoS约束的组播路由问题是非常有前景的。1．2．3无线AdHoe网络Oos组播路由面临的问题QoS组播路由问题本身就是网络路由协议的一个难题。再加上AdHoc网络自身的特点，如带宽有限、拓扑结构动态变化、网络节点资源有限(如CPU和能量)等，使得在AdHoc网络中研究QoS组播路由问题变得更加复杂。主要的问题可以归纳为以下几点：(1)无线AdHoc网络的节点可以任意移动，网络拓扑结构动态变化。当这种变化非常快时，这将导致链路性能无法预测，难以获得精确的网络状态信息。(2)节点的电池能量有限。在AdHoc网络中，每个节点通常以电池作为电源，因而它们的电池能量是有限的。并且，节点其它的资源也非常有限(如CPU和内存等)，所以在设计路由算法时必须要考虑如何有效地利用有限的节点资源，如节约能量并延长网络和组播生存时间等问题。(3)特殊的信道共享方式。AdHoc网络的信道是多跳共享的广播信道，即当一个节点发送数据分组时，处于发射节点覆盖范围之内的所有节点都可以接收到数据分14 第一章绪论组，而处于覆盖范围之外的节点则无法感知这些分组数据。因此，如何选择各个节点的数据通信范围，从而有效地利用节点能量是值得研究的重要问题。(4)信道带宽有限。由于无线信道的带宽有限，在设计路由协议和路由算法时，需要尽量减少节点之间的信息交互。(5)安全性较差。由于AdHoc网络采用无线信道进行通信、电源能量有限，并且采用分布式控制，所以AdHoc网络很容易受到攻击，网络安全性较差。1．2．4无线AdHoc网络QoS组播的研究现状对AdHoc网络QoS组播路由问题的研究已经提出了不少新颖的算法[21,108-111】，这些算法围绕着几种比较典型的QoS约束条件，如延迟[1121、带弹1131、包丢失率[1141、延迟抖动[115】、能量消耗【116-1211和组播生存期【122-126】等。但是这些算法只考虑了一个QoS约束条件。虽然近年来越来越多的研究同时考虑了两个或多个不同的QoS约束[63,68,70,77,88】，但是这些研究并没有考虑量消耗问题。在AdHoc网络路由算法中缺乏对能量消耗的考虑将会引起节点能量消耗过快，节点生存期和组播服务时间缩短，甚至会引起网络无法正常工作等问题【127】。因此，这些路由算法不能直接应用于AdHoc网络。但是这些新颖的算法为我们在AdHoc网络中研究QoS组播路由问题提供了一定启发。目前，对AdHoc网络QoS组播路由的研究还处于初级阶段，仍存在很多问题有待深入研究。对AdHoc网络QoS组播路由的研究主要集中于延迟抑制最小代价组播路由问题、带宽延迟抑制最小代价组播路由问题、度抑制的最小代价组播路由问题、以及延迟延迟抖动抑制的最小代价组播路由问题等等。这些研究工作虽然在一定程度上考虑了节点的移动性，但是如果节点的移动速度较快，这些研究成果很难有效地工作。另外，在这些研究工作中，并没有考虑能量消耗、网络生存期和组播生存期等问题。由于AdHoc网络的能量非常有限，如果不考虑能量问题，会使得AdHoc网络的能量过快耗尽从而无法正常工作。1．3论文提出的研究问题由于延迟抑制组播路由技术和传输代价对多媒体应用具有非常重要的意义，以及如何减小能量消耗、延长网络生存期和延长组播生存期对AdHoc网络的性能至关重要，所以本文在AdHoc网络中提出了三个QoS组播路由问题，在组播路由中考虑了 上海交通大学博士学位论文延迟、传输代价、能量消耗、网络生存期和组播生存期。1．3．1延迟抑制最小能耗组播路由问题大多数多媒体应用都是延迟敏感的【128。1311，如视频会议、远程医疗和远程教育等。所以在组播路由中需要考虑传输延迟。由于AdHoc网络中的移动终端使用电池作为唯一的供电来源，即能量是有限的，所以在组播路由中也需要考虑如何减小能量消耗。在AdHoc网络中，本文提出了延迟抑制最小能耗组播路由(Delay．ConstrainedMinimum．EnergyMulticastRouting，DCMEMR)Ih-]题。DCMEMR问题的目标是建立一棵连接源节点和目的节点的组播树，源节点到任一目的节点的传输延迟小于路由请求给出的延迟上界，并且这棵组播树的能量消耗最小。1．3．2最大网络生存期最小代价组播路由问题为了有效地使用AdHoc网络有限的能量资源，在组播树的建立和选择过程中，能量消耗较小的那些路径总是被经常选中并使用。这会使得这些路径上的节点因为大量转发信息而过快耗尽自身的能量【132,133J，从而使得这些节点失效，网络的连通性遭到破坏，甚至会引起整个网络无法再正常工作。因此，有时组播路由不仅需要考虑如何减小能量消耗，也需要尽可能地延长网络的生存期(即工作时间)。另外，传输代价(如总的资源消耗或总的传输开销)也是在组播路由中时常需要优化的参数。因此，本文提出了最大网络生存期最小代价组播路由(Maximum．Network．LifetimeMinimum．CostMulticastRouting，MaxNLMCMR)问题，主要目的是建立一棵连接源节点和目的节点的组播树，减小组播树的传输代价，同时延长网络的生存期。1．3．3延迟抑制最大组播生存期组播路由问题很多时候，组播传输任务还没有完成，参与组播的节点的能量就耗尽了。这会引起组播任务中断，路由协议需要重新寻找并建立新的组播树完成组播任务，造成网络资源的浪费(重新寻找和建立组播路径会占用更多的CPU资源、网络带宽和节点能量)，并影响组播的服务质量(如延迟变长)[134】。所以，在AdHoc网络中研究如何延长组播生存期(即组播树的工作时间)就显得极为重要。同时，为了满足多媒体应用的延迟约束，组播路由需要考虑延迟参数。因此，本文提出了延迟抑制最大组播生存期组播路由(Delay．ConstrainedMaximum．LifetimeMulticastRouting，DCMaxLMR) 第一章绪论问题，主要目的是建立一棵连接源节点和目的节点的组播树，源节点到任一目的节点的传输延迟小于路由请求给出的延迟上界，并且这棵组播树的组播生存期最长。1．4论文的内容安排和创新工作1．4．1内容安排本文的章节安排如下：第一章为绪论。首先简要介绍了组播、QoS、QoS组播和无线AdHoc网络的基本概念，以及无线AdHoc网络QoS组播的研究意义。然后简述了QoS组播路由的实现、无线AdHoc网络QoS组播路由面临的问题和研究现状。接着在无线AdHoc网络中提出了三个QoS组播路由问题。最后是本文的内容安排和创新工作。第二章是遗传算法解决QoS组播路由问题。首先分析了遗传算法解决QoS组播路由问题的有效性。然后简述了遗传算法解决QoS组播路由问题的研究现状，并介绍了遗传算法的基本原理。接着讨论了设计遗传算法的相关工作，指出编码、交叉算子(crossoveroperator)、变异算子(mutationoperator)和选择算子(selectionoperator)是设计遗传算法需要重点考虑的问题。最后讨论了遗传算法的收敛性问题。第三章是树结构编码法。首先讨论了研究组播树编码方法的重要意义，指出组播树编码方法对遗传算法的性能有重要影响。然后简述了编码设计需要考虑的问题(如可行性和合法性)以及需要满足的性质。接着，介绍了现存的组播树编码方法，其中重点介绍了PrtiferNumber编码和序列拓扑编码，因为这两种编码方法是目前最有效的组播树编码法。最后提出了新的组播树编码法，即树结构编码法，并将树结构编码法和其他组播树编码方法进行了分析比较。第四章是延迟抑制最小能耗组播路由算法。首先简述了在AdHoc网络中研究延迟抑制最小能耗组播路由的意义。然后根据无线AdHoe网络的特点，建立了网络模型和能量消耗模型。基于此网络模型，对延迟抑制最小能耗组播路由问题进行了数学定义。接着，针对延迟抑制最小能耗组播路由问题，提出了DCMEGA算法。在DCMEGA算法中，基于树结构编码法，设计了有效的交叉算子和变异算子。在交叉算子和变异算子中考虑了延迟和距离参数，使得DCMEGA算法快速收敛。最后实验证明了DCMEGA算法的有效性。第五章是最大网络生存期最小代价组播路由算法。首先简述了在AdHoc网络中 上海交通大学博士学位论文研究最大网络生存期最小代价组播路由的意义。然后根据无线AdHoc网络的特点，建立了网络模型和网络生存期模型。基于此网络模型，对最大网络生存期最小代价组播路由问题进行了数学定义。接着，针对最大网络生存期最小代价组播路由问题，提出了MaxNLMCGA算法。在MaxNLMCGA算法中，基于树结构编码法，设计了有效的交叉算子和变异算子。在交叉算子和变异算子中考虑了延迟和距离参数，使得MaxNLMCGA算法快速收敛。变异算子通过改善组播树瓶颈节点(bottlenecknode)的剩余能量，从而延长网络生存期。第六章是延迟抑制最大组播生存期组播路由算法。首先简述了在AdHoc网络中研究延迟抑制最大组播生存期组播路由的意义。然后根据无线AdHoc网络的特点，建立了网络模型和组播生存期模型。基于此网络模型，对延迟抑制最大组播生存期组播路由问题进行了数学定义。接着，针对延迟抑制最大组播生存期组播路由问题，提出了DCMaxLGA算法。在DCMaxLGA算法中，基于树结构编码法，设计了有效的交叉算子和变异算子。在交叉算子和变异算子中考虑了延迟和距离参数，使得DCMaxLGA算法快速收敛。变异算子通过改善组播树瓶颈节点的生存期，从而延长网络生存期。第七章是全文工作的总结及对未来工作的建议。AdHoc网络QoS组播路由协议的发展已经有近十五年的历史，然而，其迅速发展只是在近十年。在这一领域虽然不断有新的成果问世，但仍有很多基础层面的问题没有解决，离实际应用尚存在一定距离。本文试图通过对QoS组播路由的研究，在AdHoc网络中解决几类QoS组播路由问题，为后续研究奠定基础。1．4．2创新工作本文的创新性主要体现为以下几点：(1)目前对AdHoc网络组播路由的研究主要集中在如何节约能量方面。在组播路由中同时考虑传输延迟、传输代价、能量消耗、网络生存期和组播生存期的研究比较少。另外，关于QoS组播路由的研究主要是在有线网络中，这些研究成果并不能直接应用于AdHoc网络。虽然近年来有越来越多的研究工作关注AdHoc网络QoS组播路由问题，但是这些研究工作并没有在QoS组播路由中考虑能量消耗、网络生存期和组播生存期。因此，本文针对AdHoc网络自身的特点，在AdHoc网络中提出了三个QoS组播路由问题，它们分别是DCMEMR问题、MaxNLMCMR问题和DCMaxLMR问题，并给出了这三个问题的数学定义。这三个问题对AdHoc网络QoS 第一章绪论组播路由的研究有重要意义和价值。(2)在遗传算法中提出了树结构编码法。此方法直接用组播树本身表示染色体，在遗传算法中不需要再对组播树进行编码和解码操作，简化了遗传算法。并且树结构编码法具有较好的位置继承性，即能够将组播树的优良特性较好地遗传给下一代，使得基于树结构编码的遗传算法有较好的性能。(3)针对DCMEMR问题，提出了DCMEGA算法。在该算法中，为了减小端到端延迟和总的能量消耗，提出了新的交叉算子和变异算子。交叉算子将父个体中的相同链路遗传给子个体。根据适应度函数和选择算子的定义可知，父组播树中的相同链路有很大可能代表DCMEMR问题的解的优良结构，因此将这些链路遗传给新的组播树使得遗传算法能快速找到DCMEMR问题的最优解。变异算子在新的组播树中随机选择一些节点，并将这些节点与其父节点之间的链路从组播树中删掉(形成一些分离的子树)，然后用最短延迟路径或最小距离路径把产生的子树连接成一棵新的组播树，从而防止遗传算法陷入局部最优。变异操作还可以改善组播树的延迟和能量消耗。(4)针对MaxNLMCMR问题，提出了MaxNLMCGA算法。在此算法中，定义了网络生存期，使得网络生存期得以量化。为了延长网络生存期并减小传输代价，采用了DCMEGA算法中的交叉算子，并提出了新的变异算子。变异算子通过改善瓶颈节点的剩余能量，从而延长网络生存期。(5)针对DCMaxLMR问题，提出了DCMaxLGA算法。在此算法中，采用了DCMEGA算法中的交叉算子和MaxNLMCGA算法中的变异算子，为了延长组播生存期，对MaxNLMCGA算法中的变异算子进行了适当修改。变异算子通过改善瓶颈节点的生存期，从而延长组播生存期。 第二章遗传算法解决QoS组播路由问题2．1遗传算法解决QoS组播路由问题有效性分析QoS组播路由问题是带约束的优化问题。通常可以用下面的数学模型来描述一个优化问题：删sub池厂兰’c(2．1)_／ecttoXRandRU∈C、’其中，X是决策变量，只是满足约束条件的所有解构成的集合，U是基本空间，脚是目标函数(优化的对象)。对于一个优化问题，目标函数和约束条件是各种各样的，它们既可以是连续的，也可以是离散的；既可以是线性的，也可以是非线性的。对于一些较为复杂的优化问题，人们发现求解问题的复杂度高，当问题规模扩大时，这些求解方法的计算量和计算时间急剧增大【1351。甚至很多时候，要准确地求出最优解本身就是不可能的(这种情况下，人们转而去求近似最优解)。研究QoS组播路由问题时，主要有两种方法：一种是启发式算法(heuristicalgorithm)，另一种是人工智能算法(搜索算法)。用启发式算法解决QoS组播路由问题时，存在一个共同的缺点：算法的计算时间会随着网络规模的扩大而急剧增大。因而，越来越多的研究者采用人工智能算法解决QoS组播路由问题，如蚁群算法，神经网络，模拟退火算法和遗传算法等等。与其它的人工智能算法相比，遗传算法具有它自身独特的优势：(1)启发式算法直接用决策变量的值来进行优化计算，遗传算法用决策变量的编码为运算对象进行优化计算。通过编码，遗传算法可以模拟自然界的生物进化过程。(2)遗传算法具有较强的自适应。tO-、自组织性和自学习性。一旦编码机制、适应度函数和遗传算子(选择算子，交叉算子和变异算子)确定后，遗传算法就可以直接利用进化过程中获得的信息自动地搜索最优解。用遗传算法解决QoS组播路由问题，不需要预先描述QoS组播路由问题的全部特点。因此，用遗传算法解决QoS组播路由问题时，算法设计和实现比较简单。 上海交通大学博士学位论文(3)遗传算法仅仅通过适应度函数作为搜索信息进行最优解搜索，不再需要任何其它的与搜索空间相关的信息和辅助信息。遗传算法对适应度函数的设计没有严格的要求(不需要连续可微，定义域可以根据需要任意设定)，同一问题的适应度函数设计可以多种多样，唯一的要求就是能够准确反映解的好坏，并且适应度值为正，因而遗传算法的实现简单，应用范围很广。(4)遗传算法具有较强的并行性和全局最优性。许多传统搜索方法都是单点搜索算法(如爬山法)，即通过某种变化规则使问题的解从搜索空间中的一点(对应一个解)移动到另一点(另一个解)。在多峰(多个局部最优解)搜索空间中，这种点对点的搜索方法常常会陷入局部最优解(即处于某个峰)。然而，遗传算法是同时处理群体中的多个染色体(同时评估搜索空间中的多个解)，形象地说，遗传算法是并行地爬多个峰。所以，遗传算法具有较好的全局搜索性能，并且多点搜索特性使得遗传算法非常易于并行化。(5)遗传算法使用内在启发式随机搜索技术。遗传算法不采用确定性规则来进行搜索(一个点向另一个点的转移具有确定性)，而是采用自适应的、内在的概率搜索技术(选择、交叉、变异都以一定的概率进行)。确定性规则有可能使得搜索过程无法达到最优解，而概率搜索技术不仅使得遗传算法具有较强的灵活性，而且使得遗传算法具有明确的搜索方向(根据概率和适应度指引搜索方向)，使得搜索过程更加有效。综上所述，遗传算法原理简单、鲁棒性强、易于实现和易于并行化。用遗传算法解决复杂的QoS组播路由问题时具有独特的优势。2．2遗传算法解决QoS组播路由问题的研究现状为了解决组播路由问题，Hwang在文献[641中提出了一种基于二进制编码的遗传算法。这种编码方法维持了一组路由表。每个O，v3)对有一个对应的路由表，其中S是源节点，v，是目的节点(v，∈Do如果节点S和节点1l，，之间存在，．条路径，则路由表的大小为，．。路由表中的每条路径对应一个唯一的标识号f(0≤i≤，．一1)，路由表中的路径按照某种特定的顺序进行排列(例如：路径长度逐渐减小的顺序)。染色体(组播树的基因型)用一个长度为，的整数串表示。图2．1给出了这种编码方法的示意图。基于此编码方法，Hwang设计了相应的单点交叉算子和按位变异算子。Hwang提出的遗传算法需要预先建立源节点到每一目的节点的路由表，即找出源节点到每个目的节点的所有路径，这大大增加了算法的复杂度。尤其是当网络规模扩大时，这种算法 第二章遗传算法解决QoS组播路由问题效率会急剧降低。路由表标识号路径0S_魄1S_h_i纂薹置鬻耋j薹蠹。l篓囊轰意净l瑶。ci黔r-1S—}％位置：染色体：图2-1Hw蚰g的编码机制Fig．2-1Hwang’sencodingscheme为了解决延迟抑制最小代价组播路由问题，Sun【68】扩展了文献[66】中提出的遗传算法。该算法采用二进制位串编码机制。但是Sun的算法在解码过程中引入了另一个NPC问题，大大增加了算法的复杂度。Xiang在文献[65]中提出了一种新的遗传算法用于解决QoS组播路由问题。这个遗传算法采用甩×行一维二进制编码机制，其中n表示网络中的节点数。这个遗传算法的缺点是nxn一维二进制编码使得遗传空间(染色体)和解空间(问题的解)之间的转换过程非常复杂，尤其是网络规模非常大的时候尤为明显，同样会使得遗传算法效率较低(收敛性差，收敛速度较慢)。Haghighat等在文献[70】提出了基于Prtifernumber编码的遗传算法来解决带宽延迟抑制最小代价组播路由问题，并基于Priifernumber编码提出了相应的交叉算子和变异算子。Priifernumber编码的缺点是位置继承性较差。针对此问题，Yen[‘74】提出了基于序列拓扑编码(SequenceandTopologyEncoding，STEncoding)的遗传算法来解决能量有效的最小代价组播路由问题。但是，基于ST编码的交叉和变异操作会产生不合法的染色体(带路由环的组播树，甚至可能不是组播树)。大量的组播路由研究表明，Pmfernumber编码和ST编码是较为有效的组播树编码机制。以上简单地介绍了一些典型的基于遗传算法的组播路由算法，它们大多数是针对有线网络而设计的，并没有考虑能量问题，所以不能直接用于AdHoc网络。其中，虽然Yen的遗传算法是解决AdHoc网络中能量有效的最小代价组播路由问题，但是在计算网络中节点的能量消耗时没有考虑AdHoc网络节点的广播特性。在Yen建立的网络模型中，每个节点采用方向性天线，通过减小组播树上节点的度(degree)来减小能量消耗。 上海交通大学博士学位论文2．3遗传算法的基本原理各种生物自从诞生以来，就经历了从简单到复杂、从低级到高级的复杂进化过程，并且这一过程仍在继续。达尔文的“自然选择(naturalselection)”学说【136J解释了生物进化的原因：生存斗争。生存斗争使得各种生物得以进化，并且不断适应各种环境变化。只有在生存斗争中获胜的生物个体才能生存下来并繁衍后代。在生存斗争中为了适应环境，个体会发生变异。这些变异包括有利的变异和不利的变异。有利变异(变异后的个体更能适应环境、与其他物种之间的生存竞争更具优势)使得生物个体有更大的概率生存下来并繁衍后代；不利变异使得生物个体有很大可能被淘汰(无法存活而死亡)。所以，能够在生存斗争中存活下来的生物个体都具有较强的适应环境的能力。这种“适者生存，优胜劣汰”的过程就被称为“自然选择”过程。通过自然选择学说可知，生物进化的内在因素是遗传和变异。通过遗传，生物个体将好的生物特征和性状遗传给下一代，使得物种的特性得以保持和延续；通过变异，生物个体引入新的生物特征和性状，使得物种不断进化发展。生物进化是通过遗传物质实现的。脱氧核糖核酸(DeoxybonucleicAcid，DNA)是目前主要的遗传物质。染色体(chromosome)是遗传物质的主要载体(染色体的主要化学成分之一就是DNA)。基N(gene)是DNA的结构单位和功能单位。生物性状由基因控制。基因构成染色体，基因在染色体中的位置称为基因座(10cus)，染色体中某一位置上基因可取的值称为等位基因(alleles)。一旦基因座和基因座上的基因值确定，染色体的特征和生物个体的性状就固定了。通常，一个染色体有两种表现形式。一种是表现型(phenotype)，它是生物个体表现出来的生物性状；另一种是基因型(genetype)，它是决定表现型的基因构成。个体表现型是由基因型和环境共同决定的，也就是说，具有相同基因型的个体可以有不同的表现型。2．3．2遗传算法的基本原理遗传算法将某个问题的解看做是个体(individual)。解空间(问题空间)中的解看成是个体的表现型，遗传空间中的染色体看成是个体的基因型。遗传算法是作用在遗传空间上的，也就是说遗传算法处理的对象是染色体。一定数量的染色体构成群体24 (population)，群体中染色体的数量称为群体规模(populationsize)。遗传算法在进化过程中总是保持群体规模不变。遗传算法开始于问题的一组随机解，即初始群体(initialpopulation)。初始群体产生以后，遗传算法通过选择算子，选出群体中适应度较高的个体，让这些个体通过交叉算子和变异算子产生新个体。选择算子模拟生物进化过程中的“优胜劣汰”，交叉算子模拟生物的遗传操作，而变异算子模拟生物的自然变异。选择是以适应度(fitness)为依据进行的，适应度根据适应度函数(fitnessfunction)来计算。交叉操作将父个体的优良性状(对应解的优良结构)遗传给新个体，变异操作引入新的基因或基因结构，防止算法陷入局部最优。通过群体的不断进化(反复执行交叉、变异、选择)，使得解越来越接近最优解或准最优解。2．4遗传算法设计相关工作通常，设计一个遗传算法，需要研究遗传算法的几个基本组成部分。(1)编码。遗传算法不能直接处理解空间的数据，因此需要通过编码把问题的解表示成遗传空间里的染色体。(2)群体初始化。产生一定数量的染色体。(3)适应度评估。对当代群体中的每个染色体进行适应性评估，通过适应性的好坏评价染色体的好坏。(4)选择。选择的目的是为了从当前群体中选出优良个体，使它们有机会作为父代繁衍子孙。遗传算法通过选择算子体现了“优胜劣汰”这一思想。选择的原则是适应性强的个体产生后代的概率大。(5)交叉。交叉算子是遗传算法中最主要的遗传操作之一。通过交叉操作可以得到新个体，新个体继承了父个体的优良性状。交叉操作体现了遗传和继承的思想。(6)变异。变异对新个体进行变异操作。遗传算法中发生变异的概率很低，通常取值在0．001～0．01之间。变异防止搜索过程陷入局部最优。遗传算法的流程图和算法分别如图2．2和图2．3所示。初始群体经过反复的迭代，产生出更优良的下一代，使得解的质量越来越好。图中，f表示遗传算法的迭代次数或代数(thenumberofgeneration)。 上海交通大学博士学位论文图2-2遗传算法流程图Fig．2—2FlowchartofGA基本遗传算法Input：问题相关数据，遗传算法参数Output：最优解Begin1．f卜O；／*t：进化代数木／2．P(D卜null；／木P(D：第t代群体木／3．基于编码策略初始化P(O；4．解码后评估P(D；5．while(没达到终止条件)dof6．Cc(0卜在尸(D上执行交叉操作；7．cM(O卜在荆上执行变异操作；8．C(D解码后进行适应度评估；／木C(t)卜Cc(f)Uc00)木／9．P(升1)卜从P(f)和C(O中选择一组优良个体；10．f4----t+l：)11．输出最优个体；End图2-3基本遗传算法Fig．2-3PseudocodeofbasicGA 第二章遗传算法解决QoS组播路由问题2．4．1编码遗传算法不能直接处理解空间的解，因此需要将解空间中的解转换成遗传空间中的染色体，这一转换过程通常称为编码(encoding)或解的遗传表示(geneticrepresentation)。编码策略在遗传算法中占有举足轻重的地位。编码操作是遗传算法的基础，它不仅直接影响着交叉算子和变异算子的设计，而且在很大程度上决定了遗传算法的效率。因此，在用遗传算法解决QoS组播路由问题时，编码策略是需要重点研究的问题，即如何有效地编码组播树。2．4．2群体初始化在遗传算法的设计过程中，一旦确定了编码方法，接着就需要考虑如何产生初始群体。因为初始群体是遗传算法的起点，并以此起点一代一代进化，直到满足终止条件为止。产生初始群体需要考虑两个问题：(1)群体的规模。遗传算法在进化过程中，每代的个体数量是维持不变的，即群体规模是固定的。那么，群体规模该如何确定?(2)群体中每个个体的产生方法。初始群体中的个体如何产生?群体规模是遗传算法的主要控制参数之一，它对遗传算法的性能有重要的影响。如果群体规模过小，算法很可能找不到最优解。但是，如果群体规模过大，遗传算法将会不必要地浪费计算时间，从而导致较慢地收敛到最优解或准最优解。目前，群体规模的设定尚缺乏系统的理论研究，通常是将遗传算法设计好后，通过预先的实验测试选择一个合适的群体规模(在解的性能和计算时间之间找到一个平衡)。群体的初始化方法可以大致归纳为两种：(1)在遗传空间中直接产生，即在遗传空间中随机地产生染色体。以一维二进制编码为例，随机地产生二进制码序列。该方法简单并易于实现，但生成的染色体在解空间不一定对应合法的解。如果编码方法的码串对应合法解的概率较小，有可能产生的初始群体大多不是合法解，这会影响算法的有效性。(2)编码产生。根据具体的问题和采用的编码方法，将问题空间中的合法解转换到遗传空间。这种方法能够保证染色体对应的解是合法的(有意义的)，但是这种方法需要根据具体的编码方法来设计相应的初始化方法。 上海交通大学博士学位论文2．4．3适应度评估适应度评估对遗传算法的收敛性和搜索方向都有重要的影响。选择操作是以染色体的适应度为依据进行的，适应度通过适应度函数计算得到。染色体的适应度应该要能准确地描述染色体所对应的解的性能好坏：染色体的适应度越大，表明解的质量越高，该个体被选择成为父代进而产生后代的的概率越大。有时，一些研究者也用适应度越小表明解的质量越好，原理都是相同的。适应度函数需要根据问题的特点进行设计。不同的问题，适应度函数可以不同；相同的问题，也可以采用不同的适应度函数，只要适应度函数能够正确地评估解的好坏就行。通常，在设计适应度函数时，要遵循以下原则：(1)单值性。(2)非负性。(3)计算量小。适应性函数的计算应该尽量简单。复杂的适应性函数会增加算法计算空间和计算时间，从而使得算法的性能降低。适应度函数对遗传算法的影响主要体现在三个方面：(1)适应度函数和选择算子共同决定了群体中各个染色体产生后代的概率。适应度越大的个体产生后代的概率越大。(2)遗传算法的终止条件受到适应度函数的影响。目前，遗传算法的终止条件该如何设置并没有严格的理论支持。理想地，如果知道适应度函数的最大值，那么可以用遗传算法搜索到适应度函数最大值的时候作为算法终止条件。但是很多情况下，适应度的最大值并不知道，它本身就是搜索的对象。因此不能用适应度最大值作为算法终止条件。通常情况下，遗传算法是根据群体适应度在进化过程中趋于稳定状态来终止算法的。(3)问题的约束条件在适应度函数中考虑。如果所求的问题带约束条件，那么可以每产生一代新的群体就检查一下群体中的个体是否满足约束条件。满足约束条件的个体视为有效个体，可以继续参与进化；不满足约束条件的个体视为无效个体，不再参与进化。但是在很多时候，检测一个个体是否满足问题的抑制条件并不简单(复杂程度并不比找出问题的最优解低)，因而这种检测方法会使得算法变得更加复杂，导致算法的收敛速度变慢。对于带约束条件的问题，通常情况下是采用惩罚函数来抑制不满足约束条件的个体继续进化。如果个体不满足约束条件，惩罚函数会使得这个个体的适应度减小，这种方法简单并易于实现。 第二章遗传算法解决QoS组播路由问题2．4．4选择算子选择是通过选择算子来完成的。选择的目的是从当前群体中挑选出优良的个体直接遗传到下一代或通过交叉操作产生新个体，从而将解的优良性状遗传给予代。越优良的个体，被选成父代进行遗传操作的机会越大。选择操作是建立在适应度的基础上的。选择的原则是适应度越高的个体被选中的概率越大。下面是几种常见的选择算子：(1)轮盘赌选择法(roulettewheelselection)u37j。轮盘赌选择模型通常又被称为适应度比例选择(fitnessproportionalmodel)法。它的原理模仿了博彩游戏中的轮盘赌。个体f被选中的概率为：A2南亿2，其中，7；表示个体i的适应度，m是群体规模。轮盘赌选择法将一个轮盘划分为m个扇区，轮盘上有一个可自由转动的指针。每选择一个个体相当于转动一次轮盘指针，当指针停在某个扇区上就表明那个扇区对应的个体被选中。当用计算机来模拟这一过程时，转动指针相当于产生一个[O，1]之间的随机数，这个随机数和各个个体的选择概率P，共同决定了被选中的个体。每转动一次指针只能选出一个个体，若要选出多个个体，则需要转动指针多次。从公式(2．2)可以看出，概率P，描述了个体f的适应度在群体总适应度中所占的比例。个体f适应度越大，它被选中的概率就越大。图2-4是轮盘赌选择法的原理图，轮盘中扇形所对应的数字是个体被选中的概率，它是根据各个个体的适应度计算得到的。如果产生的随机数为0．21，则个体2被选中。(2)锦标赛选择法(tournamentselection)[138j。锦标赛选择法首先需要确定联赛规模x，即每轮联赛有多少个个体参与竞争。联赛规模确定后，锦标赛选择法随机地从群体中选出x个体，然后将这x个体中适应度最高的个体选为父个体并产生后代或将它直接保存到下一代。每轮选择只能够选出一个个体，当需要选出多个个体时，只需多次执行这一选择即可。联赛规模x越大，竞争越激烈。在许多研究中通常取x=2。(3)排序选择法(rank-basedmodel)[139J。顾名思义，排序选择法是将群体中的个体进行排序从而选出个体的一种选择方法。它的具体操作如下，首先将群体中的所有个体按照适应度大小进行排序，然后将29 上海交通大学博士学位论文预先设定好的概率表依次分配给每个个体。概率表中的每个概率即为个体被选中的概率。(4)最佳个体保存法(elitistmodel)[140】。最佳个体保存法是将群体中适应度最大的个体直接复制到下一代。这种选择机制是为了防止进化过程中每代的最优个体被遗传算子(交叉操作和变异操作)破坏。但是，这种选择法也引入了新的问题，由于局部最优解的基因结构(解结构)迅速增加，会使得遗传算法陷入局部最优。群体适应度个体115个体227个体36个体452个体5112．4．5交叉算子图2-4轮盘赌选择例子Fig．2-4Anexampleofroulettewheelselection交叉算子模拟自然界生物进化过程中的基因重组，把两个父个体的部分结构进行重组替换从而产生适应度更高的个体。交叉算子的设计与问题本身以及编码方法密切相关。交叉算子的设计是以编码方法为基础的。交叉算子既要能够将父个体的优良性状(好的个体结构模式)遗传给子个体，又要能够产生更好的新个体模式。交叉操作一般需要以下两个步骤来完成：(1)选择一对个体作为父个体。(2)根据某个概率，即交叉概率(crossoverrate)，实施交叉操作，从而产生一个新个体。 第二章遗传算法解决QoS组播路由问题交叉算子在设计中需要满足以下两点：(1)交叉算子要保证父个体的优良结构模式可以遗传给新个体。(2)交叉算子是基于编码方法的，因此，交叉算子的设计要结合编码方法，使得交叉算子简单有效、容易实现，避免在交叉过程中产生不合法的解。2．4．6变异算子变异算子模拟自然界生物进化过程中的基因突变，变化个体中的某些结构从而引入初始群体中不包含的基因模式。变异算子按照变异概率(mutationprobability)改变个体的结构。变异概率是一个很小的概率。变异算子的作用主要有两个。一方面，变异算子使得遗传算法具有局部最优搜索能力[14¨。当遗传算法通过交叉算子接近问题解空问的最优领域时，变异算子可以加速遗传算法收敛于最优解。另一方面，变异算子随机地引入初始群体中不含的个体模式，保持群体的多样性，防止遗传算法由于过早收敛从而陷入局部最优。变异算子的步骤一般是：(1)选择变异个体。(2)在变异个体中选择基因座(发生变异的位置)。(3)按照变异概率对个体进行变异操作。变异算子的设计和编码方法有密切关系，编码方法是设计变异算子的基础。设计变异算子时，需要遵循以下两个原则：(1)染色体变异前后的结构有部分相同、部分不同。(2)变异后的染色体是合法的染色体。如果变异后的新个体是不合法的，则需要遗传算法加入检查和修复操作，这会影响遗传算法的收敛速度。需要再次强调的一点是，交叉操作和变异操作是遗传算法产生新个体的两种不同手段。其中，以交叉操作为主，变异操作为辅。交叉操作决定了遗传算法的全局搜索能力，变异操作决定了遗传算法的局部搜索能力。交叉操作和变异操作协同工作使得遗传算法具有良好的搜索性能。2．5遗传算法收敛性分析遗传算法是一种智能搜索算法，它通过对编码方法、适应度函数、遗传算子(选择算子，交叉算子，变异算子)的设计可以实现全局搜索和局部搜索的均衡，具体的 上海交通大学博士学位论文实现如图2．5所示。应当指出的是，遗传算法虽然可以实现均衡的搜索，并能在很多复杂问题的求解中得到满意的结果，但是遗传算法的全局最优化收敛性问题尚缺乏系统的理论分析和证明。未成熟收敛是遗传算法中不可忽视的现象，它主要表现在两个方面：(1)群体中所有的个体都陷入同一极值(局部最优)而停止进化。(2)接近最优解的个体在进化过程中总是被淘汰，使得进化过程不能收敛。图2-5遗传算法的均衡搜索实现Fig．2—5RealizationofbalancedsearchofGA因此，在设计一个新的遗传算法时，需要考虑算法的收敛性。收敛性是指遗传算法的群体适应度达到稳定状态。通常有两种方法判断遗传算法是否收敛，一种是根据群体的平均适应度来判断，另一种是根据群体适应度的最大值来判断。为了评估遗传算法的收敛性，下面先对收敛性进行定义【142】：定义1：如果遗传算法在时刻f的群体尸(D满足以下条件：limP(t)=eo，P(t)∈P(2．3)则称遗传算法收敛。其中，尸是所有可能的群体构成的集合，Po是最优群体，Po∈P。定义1是针对整个群体定义的，描述了一种渐进的收敛过程。但是，由于遗传算法的搜索具有一定的随机性，很多时候渐进收敛性质并不能正确地描述遗传算法的收敛性。定义2：设厶(P(f))是f时刻群体尸(D中所含个体的适应度最大值，／是解空间中个体(解)适应度的最大值，若满足以下条件： 第二章遗传算法解决QoS组播路由问题姆p(f。(P(t))---)f’)=1(2．4)则称遗传算法收敛。公式(2．4)的含义是当时间卜∞时，群体尸(f)中个体适应度的最大值趋近于／的概率为l。定义2是针对个体适应度定义的。目前普遍认为，标准遗传算法并不保证全局最优化收敛。但是，在一定的约束条件下(例如，对选择算子作一定的修正后)，遗传算法是可以实现全局最优收敛的。2．6本章小结本章首先分析了遗传算法解决QoS组播路由问题的有效性和独特优势。然后简单介绍了遗传算法解决QoS组播路由问题的研究现状。接着，介绍了遗传算法的基本原理，讨论了遗传算法设计的相关工作，如编码方法、群体初始化、适应度函数、选择算子、交叉算子和变异算子。最后讨论了遗传算法的收敛性，从群体和个体两个方面分别对收敛性进行了定义。本章为后续各章的研究奠定了基础。 第三章树结构编码法3．1组播树编码方法的研究意义由于遗传算法不能直接处理问题空间里的解，所以需要将问题空间转换到遗传空间，也就是说需要将问题空间里的解(个体的表现型)转换为遗传空间里的染色体(个体的基因型)。换句话说，编码本质上就是将问题空间的解按照某种方式转化为遗传空间中由基因按照一定结构构成的染色体。编码在遗传算法中占有相当重要的地位，它是遗传算法的基础。选择算子、交叉算子和变异算子都是针对特定的编码技术进行设计的。因此，编码策略在很大程度上决定了遗传算法的搜索性能，如全局搜索性能(搜索到的是最优解还是局部最优解)、算法的复杂度、以及算法的收敛速度等。对组播树进行编码并不是一个简单的问题，因为：(1)不同的组播树包含不同数量的节点和链路。(2)节点和链路的随机序列并不一定对应一棵有意义的组播树。因此，在对QoS组播路由问题的研究过程中，如何设计组播树的编码策略是需要重点研究的问题。3．2编码设计需要考虑的问题不同的问题可以采用不同的编码策略。同一个问题也可以采用不同的编码策略。3．2．1编码技术分类遗传空间中的个体一一染色体由基因组成。染色体中的每个基因具有两个特征，一个是基因位置，另一个基因值。根据基因值所采用的符号，可以将编码方法分为以下四种类型：(1)二进制编码。 上海交通大学博士学位论文(2)实数编码。(3)整数编码。(4)常用数据结构编码。根据编码的结构特征，可以将编码方法分为：(1)一维编码。(2)多维编码。3．2．2可行性和合法性由于遗传操作作用在遗传空间(交叉和变异)，而适应度评估和选择操作是工作在解空间，所以遗传算法在工作时需要在遗传空间和解空间不断转换。从遗传空间到解空间的转换(即解码)对遗传算法的性能有巨大的影响，其中，需要考虑可行性(feasibility)和合法性(1egality)问题。●图3．1可行性和合法性Fig．3—1Feasibilityandlegality●可行性是指将染色体解码到解空问的解时，得到的解是可行的。简单地说，对组合优化问题和带抑制的优化问题，可行性是指由染色体解码得到的解满足抑制条件，即得到的解位于优化问题的可行区域。合法性是指染色体可以通过解码对应问题的一个解，这个解不一定是优化的，但是它具有解的基本结构。以组播路由问题为例，合法性是指染色体解码后可以对应一棵合法的组播树(有的时候，染色体解码后得到的结构不是组播树结构，这就不满足合法性)，可行性是指染色体解码后得到的组播树满足抑制条件。图3．1是可行性和合法性的示意图。 第三章树结构编码法3．2．3编码设计需要满足的性质对于一种新的编码策略，通常需要判断基于这种编码技术是否可以设计出有效的遗传操作，如交叉算子和变异算子。也就是说，这种编码方法是否有利于遗传算法快速地找到问题的优化解。对于组播路由问题，组播树有效的编码策略应该具有如下性质：图3-2染色体解码为问题的解Fig．3-2Decodingfromchromosomestosolutions性质1(空间有效性)：染色体不应该占用过多的内存空间。性质2(时间有效性)：对染色体执行评估(适应度计算)、重组(交叉运算)和变异等操作的时间复杂度不能太高。也就是说，编码／解码操作要简单且容易实现。性质3(合法性)：任何一个合法的编码串都应对应问题的一个解(能且只能表示组播树)。性质4(完整性)：问题的任何一个解都存在一个对应的编码(染色体)。这个性质保证问题的所有解都可以被搜索到。性质5(非冗余性)：将遗传空问中的染色体解码为解空间中的解，要一一对应，即一对一映射。将染色体解码到解空间中的解可能会存在三种情况(如图3．2所示)：(1)一对一映射；(2)一对多映射；(3)多对一映射。其中，一对一映射是最好的，一对多映射是最差的。性质6(公正性)：如果一种编码方法是冗余的，那么这种编码方法至少应该是公正的。也就是说，遗传空间中所有的染色体解码后，与解空间中的所有解相同。这个性质使得遗传算法能够公平地搜索到解空间中的每个解。性质7(位置性)：一个染色体的微小变化应该意味着在其对应的解中的微小变 上海交通大学博士学位论文化。因而执行交叉操作时才能将父组播树的优良特性遗传给子组播树。位置性有时又称为因果性。性质8(继承性)：从合法的父个体通过遗传操作(交叉、变异)得到的子个体也应该是合法的。3．3现有的组播树编码方法3．3．1组播树节点编码组播树节点编码技术用一个一维二进制向量表示组播树。这种编码策略是通过一个一维向量指出包含在组播树中的所有节点。网络中所有的节点都被分配一个节点标识(Node’SIdentification，Node’SID)i(0≤f≤刀一1，且i是正实数)。其中，n是网络节点数。基于组播树节点编码技术，用向量{岛，g。，92，．．．，gn一。}来表示一棵组播树，其中，gf∈{o，1}，f-o，1⋯．，(甩一1)。如果g,--1，表示节点f包含在组播树中；如果旷o，表示节点f不在组播树中。这种编码方法的优点是编码简单，主要缺点是解码过程比较复杂，在解码过程中需要解决另一个NPC问题。3．3．2n×n一维二进制编码刀×力一维二进制编码技术首先需要确定二进制码串的长度，记为三。其中，n是网络节点数。这种编码策略是通过一个一维向量指出包含在组播树中的所有边。在一个由以个节点组成的网络中(用有向图表示这个网络)，边的数量最多为nx玎条(其中包含了节点到其自身的边)，所以码串长度三最大为n2。这里需要特别说明的是，用图表示一个网络时通常不考虑节点到其自身的边(回路)，一维二进制编码这样做的目的是为了简化编码过程。网络中的每个节点分配一个节点标识f，0≤f≤，z一1。通过这种编码方法，一棵组播树被表示成{嘞，X1，．．．，xk，．．．Xn：一l}，xk∈{o，1}。xk的值表明了从节点f到节点，的边岛是否包含在组播树中，如果xk=1，表示组播树中含有边，f，；如果xk=0，则表示组播树中不包含边岛。注意，i=k／n，．，=k％n(符号“／”和“％”分别表示取整和取余操作)。图3．3给出了一棵组播树和其对应的刀×n一维二进制编码，图3-3(a)是网络拓扑结构，图3-3(b)是组播树和它的编码。节点0是组播树的根节点(源节点)，节点2和节点3是目的节点。 第三章树结构编码法编码：01∞00110000(a)(b)图3．3刀×疗一维二进制编码(a)网络拓扑；(b)组播树及其编码Fig．3-3nxnOnedimensionbinaryencoding(a)networktopology；(b)multicast仃eeanditScoding这种编码策略的主要缺点是编码／解码过程复杂，并且搜寻空间会随着网络规模的扩大急剧增大。所以，基于这种编码方法的遗传算法在大规模网络中的效率很低，扩展性差。3．3．3特征向量表示法特征向量表示法通过一个一维向量指出包含在组播树中的所有边。网络中所有的边都被分配一个唯一的正整数标识，如O，1，2，．．．。假设网络中有，条边，则一棵组播树被表示成{q，e2，e3，．．．，eI}的形式。其中，ek∈{o，1}，1≤k≤，。如果ek=1，表示组播树中包含边k；如果ek=0，表示组播树中不含边k。图3-4给出了特征向量表示法编码一棵组播树的例子，图3-4(a)是网络拓扑，边上的数字是边的标识号，图3-4(b)是一棵组播树和其对应的编码。特征向量表示法的编码／解码过程简单。与nxn一维二进制编码相比，特征向量表示法只需要用，个二进制数字表示一棵组播树，编码长度大大减小。如果一棵组播树中含有，条边，我们知道长度为Z的二进制码串存在2。种组合方式，其中只有极少数的码串能够表示一棵组播树。因而，特征向量表示法的主要缺点是当网络中边的数量增大时，一个长度为，的随机向量能够表示一棵合法组播树的概率将非常小。换句话说，遗传空间中的绝大部分个体并不对应合法的解(有意义的解)。因此，随机地产生初始群体(遗传算法的起点)时，很可能初始群体中的所有的染色体都对应不合法的解(不表示组播树)，这会使得基于这种编码策略的遗传算法效率很低。另外，这种编码方法在遗传空间和问题空间的转换复杂度为Df门21，n为网络的节点数。39 上海交通大学博士学位论文编码：100110(a)(b)图3-4向量表示法(a)网络拓扑；(b)组播树及其编码Fig．3-4Characteristicvector(a)networktopology；CO)multicasttreeanditscoding3．3．4父节点表示法父节点表示法为网络中的每个节点分配一个节点标识f，1≤f≤以。其中，以为网络节点数。通过这种编码技术，一棵组播树被表示为向量{A，仍，．．．，n，．．．n)，1≤f≤刀。如果节点f在组播树中的父节点是节点，，则令Pi=，；如果节点f没有包含在组播树中，则令穰=0：由于源节点J在组播树中位于树根处，特别地，令P=s。s基于这种编码策略，每个组播树都对应一个唯一的由，z个数字构成的向量(染色体)。图3．5给出了一棵组播树和其对应的父节点编码，图3-5(a)是网络拓扑结构，图3-5(b)是组播树和它的编码。节点4是组播树的源节点，节点2和节点3是目的节点。编码：41{140『【．．．．．．．．．．．．．．．．．．。．【．．．．．．。．。。，．!．．．．．，．．．，．，．．．I．．，．．．．．．．，．．，，，J。．．，．，．．．．，J(a)(b)图3．5父节点表示法(a)网络拓扑；(b)组播树及其编码Fig．3-5Parentnodevector(a)networktopology；(b)multicasttreeanditscoding虽然父节点编码方法很大程度上改善了特征向量表示法表示一棵组播树的概率，但是这种编码方法在遗传算法群体初始化和遗传过程中(如交叉、变异)仍会产生大量的不合法组播树。父节点编码方法的编码／解码复杂度为O(玎)。 第三章树结构编码法3．3．5PriiferNumber编码文献【69】首次提出用Prfifernumber来编码一棵组播树。如果一棵组播树由甩个节点构成，则这棵组播树对应的Priifernumber有玎．2个数字。换句话说，Pr(ifernumber编码技术是用刀．2个数字来描述一棵组播树，这疗．2个数字就称为组播树的Prttfernumber。PrtlferNumber编码算法Input：组播树丁Output：巴，PtBegin1．Pn卜null，马卜null；2．f卜O，j『卜0；3．While(T中的节点数大于2)do{4．f卜砷编号值最小的叶子节；5．，卜节点f在F中的父节点；6．从肿删除边ff『：严勺：组播树z节点f和节点，之间的边·／7．从肿删除节点f；8．粉记入R(从左到右)：)9．Pt卜从小到大排列节点x{xIx∈r，并血萑只}：严将排列好的x并记AP?／End图3-6PrOfernumber编码算法Fig．3—6PseudocodeofProfernumberencoding对一棵组播树丁，用R记录Prfifernumber序列，用尸，记录叶子节点串，则Priifernumber编码的步骤如下：·步骤1：为组播树T(由玎个节点构成)的每个节点分配一个节点编号(节点ID)。力是正整数。·步骤2：在组播树丁的叶子节点中选择编号值最小的那个节点，并把这个节点记为f。·步骤3：找到节点f的父节点，，把，的编号记作Prfifernumber，即将，的编号记入R(从左到右)。·步骤4：从组播树丁中删除节点f和节点，之间的边。因而，组播树丁中只剩下甩．1个节点。·步骤5：重复步骤2一步骤4，依次将节点编号从左到右记入R，直到组播树丁中只剩下两个节点。 上海交通大学博士学位论文·步骤6：将包含在组播树丁中但却没有出现在R中的其余节点编号，按照从4,N大的顺序进行排列，从而得到一个记录叶子节点的字符乒乃。编码过程：(1)R2{6)，Pt2{1)。(2)R={6，2)，Pf_{1，3)。(3)R2{6，2，4)，el2{1，3，5)。(4)R2{6，2，4，2)，el2{1，3，5)。(5)R2{6，2，4，2，4)，Pt2{1，3，5，7)。最终结果：P。={6，2，4，2，4)，el2{1，3，5，7)3图3．7Priifernumber编码例子Fig．3-7AnexampleofPrilfernumberencodingPriafernumber编码算法如图3-6所示。图3．7给出了一个Priifernumber编码的例子，从图中可以看到一组播树的详细编码过程。Prtifernumber解码过程如下：·步骤1：给定一个Pmfernumber字符串R和组播树叶子节点字符串局。·步骤2：用变量m表示字符串一中的最小编号，用n表示R最左边的节点编号；添加一条边把m和n连接起来，然后把m从R字符串中删除，并且从R中删除n。·步骤3：检查R中是否还存在，2。如果R中不再含有刀，则把聆添加到P，中，并按照从4,N大的顺序重新排列el：如果R中仍含有n，则什么也不做。·步骤4：重复步骤2一步骤4，直到R为空。·步骤5：此刻，一为空，尸，中只包含两个节点(两个数字)，用边连接这两个节点就完成Priifernumber到组播树的解码过程。图3．8是Priifernumber编码的解码算法。Prtifernumber编码满足唯一性，即问题空间中的解和遗传空间中的染色体一一对应。并且，与一维二进制编码技术相比，Priifernumber编码大大缩短了编码长度。并且遗传空间和问题空间的转换比较简单，即编码／解码过程简单。如果用堆(heap)来实现编码／解码操作复杂度为O(nlog门1。Priifernumber编码技术最大的缺点就是位置性差。用Priifernumber描述一棵组播树，即使仅改变PrOfernumber中的一个数字，也会引起组播树的结构发生很大的变化，42 第三章树结构编码法这就使得交叉操作很难将父组播树的优良结构遗传给子组播树，不利于解的进化过程。Begin1．While(R不为空)do{2．，l卜R中最左边的节点ID；3．if(，l∈只){4．m卜min(P／)；／奉用m记录局中的最小编号木／5．用边连接节点刀和节点m；／}节点行、节点m和，删边属于组播树丁幸／6．船f中删除m；7．从R中删除门；)else{8．把n添JJl至1]Pt中；9．从d,N大排列竹，结果记入尸f；)10．用边连接Pf中剩余的两个节点：／木组播树形成宰／End3．3．6序列拓扑编码图3-8Prtifernumber解码算法Fig．3-8PseudocodeofPmfernumberdecodingST编码用一个S染色体岱chromosome)和一个丁染色体(丁chromosome)共同表示一棵组播树。对一棵组播树，ST编码首先按照特定的顺序(如：从下往上、从左至右；或从上往下，从左至右)给组播树的每个节点赋予一个位置编号(记为L，)。初始位置编号为1，依次增加1。然后，将节点ID号依次填入S序列中，直到所有的节点都填入各自的位置中。S序列的第一个位置填入组播树上位置编号为1的节点ID，S序列的第二个位置填入组播树上位置编号为2的节点ID，依此类推。S序列是基因序歹U(genesequence)，表明构成组播树的所有节点成员。丁序列是基因拓Sb(genetopology)，用于记录当前位置的父节点的位置编号，丁序列记录了组播树的结构特性。 上海交通大学博士学位论文组播住3磔雠③④圆零雾雾鎏鬻节羔m位置4的父节点位置编号磔色体④⑧国蓼雾銎戳瓣图3-9ST编码ST编码算法Input：组播树正Output：序yUs，序列丁Begin1．编号乃的节点位置，记为f：2．把根节点放入研1]；3．玎1]卜0；4．扣，f=2ton{产n表示乃中的节点数木／5．研司卜位于位置f处的节点D；6．丌司卜位置f的父节点位置；)End图3．10ST编码算法Fig．3-10PseudocodeofSTencoding图3-9给出了ST编码的一个例子。图中节点5是组播树丁的源节点。ST编码的编码、解码算法分别见图3．10和图3．11。ST编码的编解码复杂度是O(甩)，0(刀)是当前组播树编码／解码复杂度最低的。 第三章树结构编码法ST解码算法Input：序YUs，序列丁Output：组播树正Begin1．用f表示瓦位置编号；2．让STl】为乃根节点；3．如，净2to玎{严玎表示乃中的节点数木／4．连接节点研妇和节点研丌司]；)End图3．11ST解码算法Fig．3-11PseudocodeofSTdecoding基于ST编码的遗传操作，会产生不合法的组播树(不是有意义的组播树)或带路由环的组播树。所以，在遗传操作中，需要对每个新产生的组播树进行合法性和路由环检测。一旦查出不合法的组播树和路由环，需要额外的步骤对它们进行修复。这些操作会增加算法的复杂度，降低算法的效率。3．4本文提出的编码方法本节针对现有编码方法存在的不足，提出了新的组播树编码方法一一树结构编码法。树结构编码法用组播树本身来描述遗传空间中的个体(染色体)，即用组播树的任何一种数据结构直接描述染色体。这样省略了遗传过程中的编码和解码操作，简化了遗传算法。—一指针组播树r采用的数据结构图3．12树结构编码Fig．3·12Treestructureencoding图3．12给出了树结构编码法的数据结构。其中，树节点定义如图3．13所示。 上海交通大学博士学位论文TypedefstructTreeNode木PtrToNode；struetTreeNode{ElementTypenode；／宰ElementType：节点类型牛／PtrToNodeFirstChildNode；严PtrToNode：指向节点的指针奉／PtrToNodeNextSibling；)3．5编码方法分析比较图3．13树节点结构声明Fig．3-13Declarationoftreenodestruct表3-3编码方法比较Table3-1Comparisonofencodingmethods编码方法空间编码合法性完整性非冗余公正性位置性继承性有效性复杂度组播树节点编码差00)不满足满足不满足一维二进制编码差O(n2)不满足满足不满足特征向量表示法差O(n2)不满足满足不满足父节点表示法好00)不满足满足不满足PrOferNumber编码好O(nlogn)不满足满足不满足ST编码好00)不满足满足不满足满足不满足树结构编码好不满足满足表3-1分析比较了现有的编码方法和本文提出的编码方法一一树结构编码法。从表中可以看出，与其它编码方法相比，树结构编码法省去了编码／解码操作，简化了遗传算法；树结构编码法有较好的空问有效性、完整性、非冗余性、公正性、位置性和继承性。3．6本章小结本章研究了遗传算法解决QoS组播路由问题的关键组成部分一一编码方法。首先讨论了组播树编码方法对遗传算法性能的影响，指出组播树编码问题不是一个简单 第三章树结构编码法的问题。然后讨论了组播树编码设计中需要考虑的问题和遵循的原则。接着简单介绍了现有的各种组播树编码方法，针对现有编码法方法存在的不足提出了新的编码方法(即树结构编码法)。最后把树结构编码法和其它编码方法进行了分析比较。从比较可以看出，树结构编码法具有较好的空间有效性、编码复杂度、完整性、非冗余性、公正性、位置性和继承性。 第四章延迟抑制最小能耗组播路由算法4．1延迟抑制最小能耗组播路由的研究意义和现状延迟抑制的组播路由技术对网络中的实时多媒体应用具有非常重要的意义[143,1441，因为大多数多媒体应用对网络有严格的延迟限制，甚至要求实时传输。另外，如何减小能量消耗是AdHoc网络的关键问题之J14孓1511。目前，在AdHoc网络中对QoS组播路由的研究主要集中于延迟抑制最小代价组播路由问题、带宽延迟抑制最小代价组播路由问题、延迟和延迟抖动抑制的最小代价组播路由问题等。这些研究并没有在寻找满足QoS约束条件的路径过程中考虑如何减小能量消耗，因而这些研究所提出的算法并不能直接应用于AdHoe网络。另外，已有许多研究者在AdHoc网络中研究如何有效地使用AdHoc网络有限的能量，并取得了很多有价值的成果，但是这些研究并没有考虑延迟约束。基于以上两个原因以及延迟约束最小能耗组播路由对AdHoc网络的重要性，本章在AdHoc网络中提出了延迟抑制最小能耗组播路由问题，并对延迟抑制最小能耗组播路由问题进行了定义，提出一种新的遗传算法(延迟抑制最小能耗组播路由算法)来解决此问题。延迟抑制最小能耗组播树保证从源节点到任一目的节点的传输延迟不超过给定上界，并且这棵组播树的能量消耗是最小的，从而在保证组播业务服务质量(延迟)的同时节约了AdHoc网络的能量。在AdHoc网络中，如果网络应用有较高的延迟要求，如视频会议和传感器网络实时数据监测等，可以采用延迟抑制最小能耗组播路由算法进行组播通信，不仅可以满足延迟抑制，而且可以优化总能量消耗。4．2问题的提出4．2．1网络模型的建立假设一个无线AdHoe网络有Ⅳ个节点，每个节点有一个唯一的标识符i，49 上海交通大学博士学位论文1≤f≤N。网络的连通性取决于每个节点的发射能量(transmissionpower)。网络中的每个节点可以动态地调整它们的发射能量。当一个节点参与了多个组播任务(即这个节点包含在多个组播树中)时，这个节点可以针对不同的组播树选择不同的发射能量来传输数据分组。为了简化，在本文中假设所有的数据分组都具有相同的大小。假设网络拓扑是变化的，但是变化没有频繁到让路由计算无效的程度。准确地说，假设拓扑变化后都会至少有一段时间的稳定期。假设无线AdHoc网络中的所有节点都使用全向天线。与有线网络相比，无线AdHoc网络具有“无线组播优势(wirelessmulticastadvantage)”B52-155]。即当一个节点发送一个数据分组时，位于这个节点发射功率覆盖范围之内的所有节点都能接收到这个数据分组。此外，每个节点f都具有两个覆盖范围(coveragearea)，它们分别是：(1)控制覆盖范[](controlcoveragearea)，记作CR。(2)数据覆盖范[](datacoveragearea)，记作DRf。其中，DRi∈CRi。控制覆盖范围和数据覆盖范围分别取决于节点f用于发射控制分组和数据分组的发射能量。根据网络中每个节点的控制覆盖范围，一个无线AdHoc网络可以用一个有向图G(y，E)表示。其中V={M，v2，．．．，％)表示网络中所有节点(移动终端)的集合，E={(f，，)lvf，v『∈V}表示网络中存在的所有边的集合。任意一条边(f，jf)((f，／)∈E)表示节点H位于节点v，的控制覆盖范围之内。每条边(f，，)有两个常量参数：边延迟呸，f和距离“。4，是从节点vf到节点u的数据传输延迟(datatransmissiondelay)，其中包括了队列延迟(queuingdelay)和传播延迟(propagationdelay)。t。，是节点Vf到节点吩之间的欧几里得距离(Euclideandistance)。dt，和t，都是正实数。4．2．2能量消耗模型的建立一条无线链路上的能量消耗模型在文献[19_o，156]qb进行了详细研究。典型的无线通信能量衰减模型为1／r卢。其中，卢是路径损耗因子，是与无线通信环境有关的常量，2≤∥≤4。根据无线通信能量衰减模型，从节点vf向节点吩传输一个数据分组，在节点'l，，处消耗的能量为：，、疗E，-，=后(‘，√+岛(4．1)其中，t，是节点1，，和节点吩之间的欧几里得距离，k是与天线特性有关的常量，岛 第四章延迟抑制最小能耗组播路由算法是接收一个数据分组消耗的能量。定义：邻居节点(neighbor)：位于节点vf控制覆盖范围(CR0内的节点称为节点Yi的邻居节点。用NB，表示节点v，的所有邻居节点构成的集合。定义：树邻居节点(treeneighbor)：给定一棵组播树丁和这棵树上的一个节点v，(M∈T)，如果节点吻是节点．1，f的邻居节点，并且v，∈T，则称节点v，是节点vf的树邻居节点。对给定的组播树丁，用TNB，表示节点v，的所有树邻居节点构成的集合。定义：连接的树邻居节点(connectedtreeneighbor)：给定一棵组播树丁，如果节点u是节点vi(v,∈丁)的树邻居节点，并且节点v，和节点Ⅵ在丁上仅通过一条边相连，则称节点Ⅵ是节点vf的连接的树邻居节点。对给定的T，CTNBf表示节点vf的所有连接的树邻居节点构成的集合。定义：非连接的树邻居节点(non-connectedtreeneighbor)：给定一棵组播树乃如果节点v，是节点v，的树邻居节点，并且节点vj和节点1，，在丁通过多于一条边相连，则称节点v，是节点vf的非连接的树邻居节点。对给定的T，NCTNBi表示节点vf的所有非连接的树邻居节点构成的集合。注意，对于给定的组播树丁和节点Vi(Vi∈T)，孙凰=CTNB，UNCTNBj。由于AdHoc网络的无线组播优势，对一棵给定的组播树乃节点的能量消耗取决于这个节点与它所有的子节,点(childrennode)之间的最大距离。传输一个组播分组，组播树上节点v，的能量消耗可通过如下公式计算：c1=后(矿岛，后(小岛如果节点Ⅵ是源节点如果节点Ⅵ是叶节点(4．2)，其它其中，∥是节点v，和它所有子节点间的最大距离。所以，沿着这棵组播树从源节点向所有目的节点发送一个数据分组的总能量消耗为：Ec(丁)=∑彳(4．3)vieT图4．1给出了一棵组播树。图中边上的蓝色数字表示边的距离长度。为了说明如何计算节点能量，假设公式(4．2)中的k=-I，E0=1，伊2。如图所示，节点1是源节点，i=lx52+1=26：节点2是叶节点，c2T=1；节点4的能量消耗i=1．22+l=5。以 上海交通大学博士学位论文此类推，各个节点的能量消耗分别为《=5，gT=10，蠢=|=《=《=1。这棵组播树上总的能量消耗们(丁)=26+1+5+5+10+1+1+1+1=51。图4-1组播树能量消耗计算Fig．4—1Energyconsumptionforamulticasttree4．2．3延迟抑制最小能耗组播路由问题定义：延迟抑制最小能耗组播路由问题(Delay．ConstrainedMinimum-EnergyMulticastRouting，DCMEMR)。对一个给定的无线AdHoc网络G(y，E)，s∈y表示组播源节点，D是所有组播目的节点构成的集合(Dcy一{J})，6表示源节点到目的节点所允许的最大延迟(痧O)。DCMEMR问题是找出一棵满足下列条件的组播树耶，D)：(1)砸，D)的根节点位于节点s，所有目的节点是№，D)的叶子节点。(2)从源节点J到任一目的节点的路径延迟比砸)，(所(J，u))≤J，V_∈D；其中，沈伽(所(s，vf))=∑(uM，叶^。(3)组播树上的总能量消耗嬲(丁)最小。4．3DCMEGA算法图4．2和图4．3分别是DCMEGA的流程图和算法。DCMEGA算法的输入是AdHoc网络拓扑图G，源节点S和目的节点的集合D。Chromosome(i)表示当前群体中的个体f。脸黜沱c攻)是选择算子。死、死和疋表示个体。randO是一个函数，产生一个0到1之间的随机数。CrossoverO和MutationO分别表示交叉算子和变异算子。％52 第四章延迟抑制最小能耗组播路由算法表示群体规模，垠表示迭代次数，％删表示最优个体的数量，Pc是交叉概率，砌是变异概率，RandomDFSO是随机深度优先算法。图4-2DCMEGA算法流程图Fig．4-2FlowchartofDCMEGADCM匣GA算法Input：Output：G，s，D组播树丁Begin1．for(f_liK2坼i附){2．Chromosome(i)一RandomDFS(G，s，D)；)3．for(产li产爿V方尹+){4．选出最优个体并直接复制到下一代：5．for(肛l；k<=Np-Noparn。，；—H斗){6．To=MSTSelect0；7．死=MSTSelect0：8．ifrand()<胁)9．疋=Crossove“Ta，Tb)；10．else11．疋一死or死；12．if(rand()
此文档下载收益归作者所有
