一种基于最小路径的多播路由优化算法  

On Algorithm of Multicast Routing Optimized Based on Minimal Path

作　　者：沈根海[1] 

机构地区：[1]嘉兴南洋职业技术学院电子信息工程系,浙江嘉兴314003

出　　处：《西南师范大学学报（自然科学版）》2014年第7期86-92,共7页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：浙江省教育厅高校科研项目资助(Y201329606);浙江省高等学校访问工程师校企合作项目资助(FW2013153)

摘　　要：信息物理融合系统(Cyber-Physical Systems,CPS)底层是传感器、控制器和执行器等异构节点构成的无线自组网络,不同节点之间需要通过通信网络传送给感兴趣目标节点,传统的无线自组织网络一般采用单播或广播技术,但是这些往往实时性不高,通信开销大,不利于在CPS中受限节点间通信.该文针对信息物理融合系统中无线多播路由问题构建网络模型,演化为最小路径问题,数学模型为约束Steiner最小树问题,并针对该NP难问题通过启发式算法求解,再通过贪婪思想构建一种最小路径多播路由算法.最后通过与uCast以及SenCast等经典的多播路由算法仿真比较,得出其算法在实时性以及能耗等方面性能优异.The underlying structure of cyber physical systems（CPS）are constituted of sensors,controllers and actuators such as heterogeneous nodes with Ad Hoc network.They contact each other through those networks while different nodes are needed to transmitted data to the target node.Traditional wireless selforganizing networks usually use unicast or broadcast technology,but these are often not high real-time performance,with high communication overhead.It is not appropriated to in the CPS.Wireless multicast routing issue in cyber physical systems is formulated to a minimum path problem.Mathematical model is constraint minimum Steiner tree problem.Heuristic algorithm for the NP-hard problem has been used to build a minimal path multicast routing algorithm by greedy algorithm.Finally,classic multicast routing algorithm as uCast,SenCast by simulation have been compared.Result proves that the algorithm has better performance in the real-time and energy consumption.

关 键 词：信息物理融合系统 多播路由 约束Steiner最小树问题 NP难问题 贪婪算法 

分 类 号：TP393.071[自动化与计算机技术—计算机应用技术]