论文部分内容阅读
随着信息技术的高速发展,工业无线网络成为自动化领域研究的热点。它成为一种新兴的,面向设备间短程的,信息交互的工业无线通信技术,适合部署在工业生产现场环境或人类不宜到达的区域,具有很强的抗干扰能力、超低能耗、实时通信等技术特征,是对现有工业通信技术在工业应用方向上的功能扩展和提升,也是对现有的现场总线控制网络的重要补充和完善。WIA-PA是我国863项目支持下,由中科院、西南大学等10余家单位自主研发的适用于过程自动化的工业无线网络技术,其形成的技术规范于2008年获得IEC的采纳,列入国际标准制定计划。WIA-PA网络底层基于IEEE 802.15.4标准,物理层为IEEE 802.15.4的各种信道,链路层兼容了IEEE 802.15.4的超帧结构并根据工业无线的需求对其进行了扩展。WIA-PA采用集中式与分布式相结合的无线通信资源分配方式。在MESH层,网关为路由设备集中分配资源,在STAR层,路由为下面的每个现场设备分配资源。本文主要研究WIA-PA在MESH层网关为路由设备集中分配的资源——簇信道。所谓簇信道,即是每个簇在进行簇内事务时所使用的信道。为了避免干扰,保证网络通信的可靠性,相邻的簇使用不同的簇信道进行通信,不相邻的在通信距离以外的簇则可以使用相同的信道。因此,WIA-PA的簇信道分配问题可转化为图的点着色问题。作者在参与WIA-PA项目的工作中,针对簇信道分配问题,进行了研究和探讨,经过分析表明目前现有的点着色算法不能满足WIA-PA这一工业无线网络的特定要求。传统的经典算法以及启发式算法与其混合算法复杂度高,运行时间长,不能满足WIA-PA的实时性要求；Welsh-Powell算法执行效率快,却不能适应网络拓扑的变化。为此,针对WIA-PA工业无线网络,本文基于通过每个代表一种颜色的集合维护不相邻的、可以着相同颜色的顶点,其信道分配的过程就是将顶点划分图的独立集的过程,也就是将顶点加入到某个集合的过程的思想,提出了一种简单高效的基于集合思想的图着色算法SBK-Coloring。该算法复杂度低,效率高；且当网络拓扑结构改变时,保留了原先的分配策略,避免了大量网络信息的更新与网络参数的重新设置,并提高了网络的实时性,降低了节点能耗。通过仿真实验,与两个典型的图着色算法混合遗传算法、Welsh-Powell算法进行分析比较,表明SBK-Coloring算法的执行效率明显超过了混合遗传算法,不管是不同规模的稀疏图还是不同规模的稠密图,其算法的执行时间均不超过几十毫秒,而混合遗传算法少到几秒,多至几分钟几十分钟不等。SBK-Coloring算法相比Welsh-Powell算法,在中小规模的稀疏图上表现相当,但随着问题规模的扩大,优势就越明显。当顶点数增加到400个时,SBK-Coloring算法相对Welsh-Powell算法的执行时间大约提高了47.8%,当顶点数增加到1000时,则大约提高了56.5%。同样,在稠密图上,当顶点数增加到95个时提高了约56.6%,增加到500个顶点时约提高了88.7%,1000个顶点时约提高了76.1%。总体来说,SBK-Coloring算法在执行效率上远远超过混合遗传算法,相比Welsh-Powell算法,大体提高50%左右。在解的质量上低于混合遗传算法,略低于Welsh-Powell算法。最后,将SBK-Coloring算法应用到几个典型的网络拓扑结构的WIA-PA簇信道分配中,其实际情况不管是信道使用的数目还是算法的执行时间,均能满足WIA-PA的要求。