41112007M11上 海 交 通 大 学 学 报JOURNAL OF SHANGHAI JIAOTONG UNIVERSIT YVol.41 No.11Nov.2007l:2006-11-25:SSES(NSF EIA-0103709),8vS/1(2005GG1101001)Te:CC(1983-),o,8X,V3,1VY3T.I(),3,q,(T el.):0531-8892930;E-mail:jzpsdu.com.cn.cI|:1006-2467(2007)11-1816-043TYdy:V%刘甜甜1 ,贾智平1 ,Edwin H.-M .Sha2(1.v9S/,62250061;2.Svrsn9S,X75083)K1:为了适应嵌入式通信系统的资源匮乏性、多因素、异构性和对等性等特点,提出了动态多因素马尔可夫决策路由(DMMDR)算法,分析了算法的时间和空间复杂度,并设计了路由的建立过程和链路状态的更新策略.研究结果表明,该算法能综合考虑各种因素,均衡和减少计算量和存储需求,并避免环路的产生.1oM:嵌入式;马尔可夫决策过程;动态多因素马尔可夫决策路由算法;链路状态更新ms|:TP 393DSM:ADynamic Multifactor-Based Markov Decision RoutinginEmbedded Communication SystemLIU Tian-tian1,JIA Zhi-ping1 ,Edwin H.-M.Sha2(1.School of Computer Science and Technology, Shandong Univ., Jinan 250061, China;2.Dept of Computer Science, Univ.of Texas at Dallas, Richardson, Texas 75083, America)Abstract:In order to adapt to the features of embedded communication system, such as resource limita-tion, multifactor-impact, heterogeneity, peer-to-peer characteristic and so on, a dynamic multifactorMarkov decision routing algorithm(DMMDR)was proposed, the time and space complexity of DMMDRwere analyzed, and the route establishing process and link state update strategy were designed.The resultsindicate that DMMDR can synthetically take different kind of factors into account, balance and reduce thecomputation and space requirement, and it is loop-free and fit for the application-oriented embedded net-work environment.Key words:embedded system;Markov decision process;dynamic multifactor Markov decision routing(DMMDR)algorithm;link state update3TdRPY9B5.3Td_、K#LH1p+,3T!#Y?X/.!,YV1g、USBTgh.,?h,yN,3Tn1%d!W5.75 1,2Y,?3T.s3T+$,:V%V,4By:V%(Dynamic Multifactor Markov Decision Routing,DMMDR)E.E?8Iny,(h9i%p,iE3,Vr3TdY5.13T+3TEs3Td&C、LH+,1In/+:(1)y.3T/1HIn#y.V?3M,Vs:HMyy.HMy.HW、Yq(.v,!)7M!y.Vz、!)?、=i、?、YM.HMyM,yN1vty,i9.y.HWYq(In+yYq)?3M!y.1、n、z、.q,!z.ty%,dq,B.Yq?3M.yNy1H.(2)s.3T!&$Y,3T!Yq9,1RS-2321g、USB,g、L,Bs“”.!,7!dYxps,PdBZT.,9Bs%5.(3).3T!W1.!;11-&?,1hY?T,AdHocK?3 .73T!&K,1T,yNExpV?,nHW,V79F3T!&?.2:V%1)45.3T!i%?K,Li.|3T!_m,!,gH.h.B,1H4BH?Nh,V7%BHK,L%V,H:V%V 4 .:VV+r,FT,S,A(i),P( i,a),r(i,a)VU.:T=0,1,%HY;SV?;idB,iS;A(i)diHV;aB,aA(i);P( i,a)Mq?p,P(j i,a)VU-i,4a,/B%HYMjq;r(i,a)Lf.A(i)、P( i,a)、r(i,a)G-d|,VN1.KV,.1EVK,yN,4HYVATK,#VyKf%.Kf%4HW%HYf%,K.Pf%FT,S,A(i),P( i,a),r(i,a)l.T=0,1,N-1,01;1,v,VU(LH)1p.(5)Mq181711刘甜甜,等:嵌入式通信系统中基于动态多因素的马尔可夫决策路由Pt(j|i,eij)=1-p(eij), j=jp(eij), j=next N0, j=:i,j,jS,eijE,t0,ttl;p(eij)eijMVL,HMy%,p(eij)=1j +2j +