基于Markov理论的移动Ad Hoc网络节点连接建模与分析
|
摘要
移动Ad Hoc网络(MANET)是在不依赖于现有固定主干网或基站的情况下,由一组分散的且具有无线通信功能的移动节点自组织形成的网络,广泛地应用在军事、救险、商业、民用和临时通信等领域,是目前通信技术研究的热点。在MANET中,节点间的连接变化对网络的性能有着重大的影响,而连接变化率反映了相邻的移动节点间连接变化问题,因此,连接变化率是研究网络连接的一个重要指标。本文将利用马尔可夫理论工具针对移动节点间的连接变化,在分析已有模型的基础上,提出了新的模型,并对所建立的模型进行分析。
首先,本文利用离散高斯-马尔可夫移动模型和一般化的离散高斯-马尔可夫移动模型得出节点间的连接变化率,并分析其特性,得出每个节点的连接数趋于稳定等结论。在模型中,节点的运动模式由时间、速率、方向这三个随机变量所描述,体现了一定的随机性,更符合实际场合的要求。
其次,利用随机微分方程工具,针对网络中任意布置的静态节点间的连接变化进行建模,构成由删除,重组,添加和无变化四种状态间进行切换的节点间连接变化系统,并对其进行分析,得出所建系统P阶指数递减、几乎处处指数稳定等结果,并针对此系统初步考虑节点的移动速度因素。
最后,综合考虑了对移动节点间连接变化产生影响的因素,针对移动节点间连接变化系统进行了一般化建模与分析,并给出了判断此系统不稳定或稳定的判定定理。
Nowadays, Mobile Ad Hoc Networks (MANET) has been one hot research subject in telecommunication technology fields, because it is decentralizing, self-organizing, and highly dynamic networks formed by a set of mobile hosts connected through wireless links, without requiring any existing fixed backbone or infrastructure. It is widely used in military, recovery, commercial, civil, and temporary communications and other fields. In the MANET, the linkage changing between two nodes has a significant impact in the performance of the network, but the link generation rate reflects the changing rate of neighborhoods of MANET. So the generation rate is an important index of a network connection. Several mobility models are first introduced and then new mobility models for MANET are presented in this paper. In the models, this paper will make use of Markov theoretical tool for modeling the link changing of mobile nodes, and the analysis is given in the following.
First of all, this paper will deduce the linking generation rate for discrete Gauss-Markov mobility model and generalized discrete Gauss-Markov mobility model. The characteristics of models are analysed, and the stability of node degree is discussed in the end. The movement pattern of mobile nodes in the model is characterized by time interval, speed and direction, which reflects a certain degree of randomness and yield more realistic behaviors.
Secondly, for the link changing of static network nodes in an arbitrary arrangement in the modeling, the system is composed by deleting, rewiring, adding, and no change to switch among four states of the link changing by the stochastic differential equations tool. Its analysis of a series of results obtained, and the important things are hth moment exponential decreasing and the stability analysis for the system. The mobile node speed factors are primarily taken into account in the systems.
Finally, for the link changing in the generalized system modeling and analysis of mobile nodes, this paper takes into account the impact of factors, and gives the judge this system instability or stability of the judge's theorem.
首先,本文利用离散高斯-马尔可夫移动模型和一般化的离散高斯-马尔可夫移动模型得出节点间的连接变化率,并分析其特性,得出每个节点的连接数趋于稳定等结论。在模型中,节点的运动模式由时间、速率、方向这三个随机变量所描述,体现了一定的随机性,更符合实际场合的要求。
其次,利用随机微分方程工具,针对网络中任意布置的静态节点间的连接变化进行建模,构成由删除,重组,添加和无变化四种状态间进行切换的节点间连接变化系统,并对其进行分析,得出所建系统P阶指数递减、几乎处处指数稳定等结果,并针对此系统初步考虑节点的移动速度因素。
最后,综合考虑了对移动节点间连接变化产生影响的因素,针对移动节点间连接变化系统进行了一般化建模与分析,并给出了判断此系统不稳定或稳定的判定定理。
Nowadays, Mobile Ad Hoc Networks (MANET) has been one hot research subject in telecommunication technology fields, because it is decentralizing, self-organizing, and highly dynamic networks formed by a set of mobile hosts connected through wireless links, without requiring any existing fixed backbone or infrastructure. It is widely used in military, recovery, commercial, civil, and temporary communications and other fields. In the MANET, the linkage changing between two nodes has a significant impact in the performance of the network, but the link generation rate reflects the changing rate of neighborhoods of MANET. So the generation rate is an important index of a network connection. Several mobility models are first introduced and then new mobility models for MANET are presented in this paper. In the models, this paper will make use of Markov theoretical tool for modeling the link changing of mobile nodes, and the analysis is given in the following.
First of all, this paper will deduce the linking generation rate for discrete Gauss-Markov mobility model and generalized discrete Gauss-Markov mobility model. The characteristics of models are analysed, and the stability of node degree is discussed in the end. The movement pattern of mobile nodes in the model is characterized by time interval, speed and direction, which reflects a certain degree of randomness and yield more realistic behaviors.
Secondly, for the link changing of static network nodes in an arbitrary arrangement in the modeling, the system is composed by deleting, rewiring, adding, and no change to switch among four states of the link changing by the stochastic differential equations tool. Its analysis of a series of results obtained, and the important things are hth moment exponential decreasing and the stability analysis for the system. The mobile node speed factors are primarily taken into account in the systems.
Finally, for the link changing in the generalized system modeling and analysis of mobile nodes, this paper takes into account the impact of factors, and gives the judge this system instability or stability of the judge's theorem.
引文
[1] John Jubin and Janet D. Tornow, The DARPA packet radio network protocols, Proceedings of the IEEE, 1987,75: 21-32.
[2] 郑少仁,王海涛,赵志峰等,Ad Hoc网络技术,人民邮电出版社,2005．
[3] B.Bollobas, Random Graphs, Academic Press, 1985.
[4] A. L. Barabasi, R. Albert, and H. Jeong, Mean field theory for scale free random networks, Physica A, 1999,272: 173-187.
[5] R. Albert and A.-L. Barabasi, Topology of evolving networks: local events and universality, Physical Review letters, 2000, 85: 5234-5237.
[6] Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002, 80-91.
[7] P. Santi, and D. M. Blough, An evaluation of connectivity in mobile wireless Ad Hoc networks, Proceeding of the International Conference on Dependable Systems and Networks, 2002, 89-98.
[8] S. Papavassiliou, J. Zhu, A continuum theory-based approach to the modeling of dynamic wireless sensor networks, IEEE Communications Letters, 2005, 9(4): 337-339.
[9] P. Santi, and D. M. Blough, The Critical Transmitting Range for Connectivity in Spare Wireless Ad Hoc Networks, IEEE Trans. On Mobile Computing, 2003, 2(1): 25-39.
[10] H.Li and D. Yu, A statistical study of neighbor node properties in ad hoc network, Proc. Of international Conference on Parallel Processing Workshops, 2002,103- 108.
[11] O. Dousse, P. Thiran and M. Hasler, Connectivity in ad hoc and hybrid networks, IEEE INFOCOM, 2002,1079-1088.
[12]C.Bettstetter,On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment,Proc.of IEEE Vehicular Technology Conference,2002,1706-1710.
[13]V.Ramasubramanian and D.Mosse,Statistical analysis of connectivity in unidirectional ad hoc networks,Proc.of the International Conference on Parallel Processing Workshops,2002,109-115.
[14]M.Desai and D.Manjunath,On the connectivity in finite ad hoc networks,IEEE Communications Letters,2002,6(10):437-439.
[15]D.Yu and H.Li,On the definition of ad hoc network connectivity,Proc.of International Conference on Communication Technology,2003,990-994.
[16]Robert Sedgewick,Algorithms in C parts 5:Graph algorithms,中国电力出版社,2003.
[17]Robert Sedgewick,Graph algorithms in C parts 1-4:fundamentals,data structures,sorting,searching,中国电力出版社,2003.
[18]T.H.Cormen,C.E.Leiserson,R.L.Rivest,et al.Introduction to algorithms,高等教育出版社,2002.
[19]张行文,孙宝林,Ad Hoc网络移动模型的研究,计算机工程与应用,2006,42(29):126-128.
[20]赵金晶,朱培栋,Ad Hoc网络移动模型及其应用,计算机工程与科学,2005,27(5):15-17.
[21]Dmitri D.Perkins,Herman D.Hughes,and Charles B.Owen,Factors affecting the performance of ad hoc networks,IEEE,Michigan,2004,2048-2052.
[22]Wang B,Yan B.Y,and Yuan D.H,The basic study of the features of the ad hoc nodes rfiobility model.Journal of Sichuan University.2006,42(1):68-72.
[23]Camp T,Boleng J,and Davies V,A survey of mobility models for ad hoc network research,Wireless Communication and Mobile Computing,2002,2(5):483-502.
[24]时锐,杨孝宗,自组网Random Direction移动模型点空间概率分布的研究,计算机研究与发展,2004,41(7):1166-1173.
[25]S.Cho and J.P.Hayes,Impact of mobility on connection stability in ad hoc networks,IEEE Wireless and Communications and Networking Conference,2005,3:1650-1656.
[26]Prince S and Stephen B.Wicker,On the Behavior of Communication Links of a Node in a Multi-Hop Mobile Environment,MobiHoc'04,2004,145-156.
[27]Xurrong Mao,Stochastic Differential Equations and their Applications,Chichester:Horwood Pulishing Limited,1997.
[28]Xuerong Mao,Stability of stochastic differential equations with Markov switching,Stochastic Process and Applications,1999,79:45-67.
[29]Xuerong Mao,A.Matasov,and A.B.Piunovskiy,Stochastic differential delay equations with Markov switching,Bernoulli,2000,6:73-90.
[30]Demin Li,Jie Zhou and Jiacun Wang,A Markov Jump Theory Based Approach to the Linking Model in Mobile Ad Hoc Network,Journal of Physics:Conference Series,2008,96.
[31]Mariton M.J ump Linear Systems in Automatic Control[M],New York:Marcel Dekker,1990.
[32]Sethi S.P,and Zhang Q,Hierarchical Decision Making in Stochastic Manufacturing Systems[M],Berlin:Birkhauser,1994.
[33]张利军,李春文,程代展,参数不确定马尔可夫跳变系统的鲁棒适应控制,控制与决策,2005,20(9):1030-1033.
[34]刘飞,苏宏业,褚健,含参数不确定性的马尔可夫跳变过程鲁棒正实控制,自动化学报,2003,29(5):761-766.
[35]李小勇,罗交晚,带马尔可夫跳跃参数的离散随机双线性系统的稳定性,长沙铁道学院学报,2003,21(4):73-76.
[36]何舒平,刘飞,基于观测器的不确定时滞Markov跳变系统H∞控制,系统工程与电子技术,2007,29(12).
[37]包俊东,邓飞其,罗琦,基于LMIs方法-不确定性随机分布型时滞Markov跳变系统的鲁棒镇定,系统工程理论与实践,2005,No.6:1-10.
[38]李顺祥,田彦涛,Markov切换系统的随机稳定性分析,控制工程,2004,11(4):325-327.
[39]Yuan Cheng-gui,and Xuerong Mao,Asymptotic stabiliity in dirtribution of stochastic differential equations with Markovian switching[J],Stochastic Process and Their Applications,2003,103:277-291.
[40]Yuan Cheng-gui,and Xuerong Mao,Robust stability and controllability of stochastic differential delay equations with Markovian switching[J].Automatic,2004,40:343-354.
[41]M.D.S.Aliyu,E.K.Boukas,H-∞ control for markovian jump nonlinear systems,Proceedings of the 37~(th) IEEE Conference on Decision & Control,Tampa,Florida USA,1998,1:766-771.
[42]M.D.S.Aliyu,Dissipativity and stability of nonlinear jump systems,Proceedings of the American Control Conference,1999,795-799.
[43]M.S.Branicky,S.K.Mitter,Algorithms for optimal hybrid control,Proceedings of the 34~(th) Conference on Decision & Control,1995,2661-2666.
[44]J.P.Hespanha,and A.S.Morse,Towards the high performance control of uncertain processes via supervision,Proceeding of the 30~(th) annual Conference on information science & systems,1996,405-410.
[45]Ben Liang and Zygmunt J.Haas,Predictive distance-based mobility management for multidimensional PCS networks,IEEE/ACM Transactions on Networking,2003,11(5):718-732.
[46]邝宁华等,强联系与跨部门复杂知识转移困难的客服,研究与发展管理,2004,20-25.
[47]Xuerong Mao,G.George Yin and Chenggui Yuan,Stabilization and destabilization of hybrid systems of stochastic differential equations,Automatica,2007,43:264-273.
[2] 郑少仁,王海涛,赵志峰等,Ad Hoc网络技术,人民邮电出版社,2005．
[3] B.Bollobas, Random Graphs, Academic Press, 1985.
[4] A. L. Barabasi, R. Albert, and H. Jeong, Mean field theory for scale free random networks, Physica A, 1999,272: 173-187.
[5] R. Albert and A.-L. Barabasi, Topology of evolving networks: local events and universality, Physical Review letters, 2000, 85: 5234-5237.
[6] Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002, 80-91.
[7] P. Santi, and D. M. Blough, An evaluation of connectivity in mobile wireless Ad Hoc networks, Proceeding of the International Conference on Dependable Systems and Networks, 2002, 89-98.
[8] S. Papavassiliou, J. Zhu, A continuum theory-based approach to the modeling of dynamic wireless sensor networks, IEEE Communications Letters, 2005, 9(4): 337-339.
[9] P. Santi, and D. M. Blough, The Critical Transmitting Range for Connectivity in Spare Wireless Ad Hoc Networks, IEEE Trans. On Mobile Computing, 2003, 2(1): 25-39.
[10] H.Li and D. Yu, A statistical study of neighbor node properties in ad hoc network, Proc. Of international Conference on Parallel Processing Workshops, 2002,103- 108.
[11] O. Dousse, P. Thiran and M. Hasler, Connectivity in ad hoc and hybrid networks, IEEE INFOCOM, 2002,1079-1088.
[12]C.Bettstetter,On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment,Proc.of IEEE Vehicular Technology Conference,2002,1706-1710.
[13]V.Ramasubramanian and D.Mosse,Statistical analysis of connectivity in unidirectional ad hoc networks,Proc.of the International Conference on Parallel Processing Workshops,2002,109-115.
[14]M.Desai and D.Manjunath,On the connectivity in finite ad hoc networks,IEEE Communications Letters,2002,6(10):437-439.
[15]D.Yu and H.Li,On the definition of ad hoc network connectivity,Proc.of International Conference on Communication Technology,2003,990-994.
[16]Robert Sedgewick,Algorithms in C parts 5:Graph algorithms,中国电力出版社,2003.
[17]Robert Sedgewick,Graph algorithms in C parts 1-4:fundamentals,data structures,sorting,searching,中国电力出版社,2003.
[18]T.H.Cormen,C.E.Leiserson,R.L.Rivest,et al.Introduction to algorithms,高等教育出版社,2002.
[19]张行文,孙宝林,Ad Hoc网络移动模型的研究,计算机工程与应用,2006,42(29):126-128.
[20]赵金晶,朱培栋,Ad Hoc网络移动模型及其应用,计算机工程与科学,2005,27(5):15-17.
[21]Dmitri D.Perkins,Herman D.Hughes,and Charles B.Owen,Factors affecting the performance of ad hoc networks,IEEE,Michigan,2004,2048-2052.
[22]Wang B,Yan B.Y,and Yuan D.H,The basic study of the features of the ad hoc nodes rfiobility model.Journal of Sichuan University.2006,42(1):68-72.
[23]Camp T,Boleng J,and Davies V,A survey of mobility models for ad hoc network research,Wireless Communication and Mobile Computing,2002,2(5):483-502.
[24]时锐,杨孝宗,自组网Random Direction移动模型点空间概率分布的研究,计算机研究与发展,2004,41(7):1166-1173.
[25]S.Cho and J.P.Hayes,Impact of mobility on connection stability in ad hoc networks,IEEE Wireless and Communications and Networking Conference,2005,3:1650-1656.
[26]Prince S and Stephen B.Wicker,On the Behavior of Communication Links of a Node in a Multi-Hop Mobile Environment,MobiHoc'04,2004,145-156.
[27]Xurrong Mao,Stochastic Differential Equations and their Applications,Chichester:Horwood Pulishing Limited,1997.
[28]Xuerong Mao,Stability of stochastic differential equations with Markov switching,Stochastic Process and Applications,1999,79:45-67.
[29]Xuerong Mao,A.Matasov,and A.B.Piunovskiy,Stochastic differential delay equations with Markov switching,Bernoulli,2000,6:73-90.
[30]Demin Li,Jie Zhou and Jiacun Wang,A Markov Jump Theory Based Approach to the Linking Model in Mobile Ad Hoc Network,Journal of Physics:Conference Series,2008,96.
[31]Mariton M.J ump Linear Systems in Automatic Control[M],New York:Marcel Dekker,1990.
[32]Sethi S.P,and Zhang Q,Hierarchical Decision Making in Stochastic Manufacturing Systems[M],Berlin:Birkhauser,1994.
[33]张利军,李春文,程代展,参数不确定马尔可夫跳变系统的鲁棒适应控制,控制与决策,2005,20(9):1030-1033.
[34]刘飞,苏宏业,褚健,含参数不确定性的马尔可夫跳变过程鲁棒正实控制,自动化学报,2003,29(5):761-766.
[35]李小勇,罗交晚,带马尔可夫跳跃参数的离散随机双线性系统的稳定性,长沙铁道学院学报,2003,21(4):73-76.
[36]何舒平,刘飞,基于观测器的不确定时滞Markov跳变系统H∞控制,系统工程与电子技术,2007,29(12).
[37]包俊东,邓飞其,罗琦,基于LMIs方法-不确定性随机分布型时滞Markov跳变系统的鲁棒镇定,系统工程理论与实践,2005,No.6:1-10.
[38]李顺祥,田彦涛,Markov切换系统的随机稳定性分析,控制工程,2004,11(4):325-327.
[39]Yuan Cheng-gui,and Xuerong Mao,Asymptotic stabiliity in dirtribution of stochastic differential equations with Markovian switching[J],Stochastic Process and Their Applications,2003,103:277-291.
[40]Yuan Cheng-gui,and Xuerong Mao,Robust stability and controllability of stochastic differential delay equations with Markovian switching[J].Automatic,2004,40:343-354.
[41]M.D.S.Aliyu,E.K.Boukas,H-∞ control for markovian jump nonlinear systems,Proceedings of the 37~(th) IEEE Conference on Decision & Control,Tampa,Florida USA,1998,1:766-771.
[42]M.D.S.Aliyu,Dissipativity and stability of nonlinear jump systems,Proceedings of the American Control Conference,1999,795-799.
[43]M.S.Branicky,S.K.Mitter,Algorithms for optimal hybrid control,Proceedings of the 34~(th) Conference on Decision & Control,1995,2661-2666.
[44]J.P.Hespanha,and A.S.Morse,Towards the high performance control of uncertain processes via supervision,Proceeding of the 30~(th) annual Conference on information science & systems,1996,405-410.
[45]Ben Liang and Zygmunt J.Haas,Predictive distance-based mobility management for multidimensional PCS networks,IEEE/ACM Transactions on Networking,2003,11(5):718-732.
[46]邝宁华等,强联系与跨部门复杂知识转移困难的客服,研究与发展管理,2004,20-25.
[47]Xuerong Mao,G.George Yin and Chenggui Yuan,Stabilization and destabilization of hybrid systems of stochastic differential equations,Automatica,2007,43:264-273.