无线网络拓扑控制中支撑图构造算法

来源：软件学报杂志2015年第4期北京时间：

作者：张秀娟,禹继国

单位：张秀娟，曲阜师范大学 信息科学与工程学院, 山东 日照 27682611,禹继国，曲阜师范大学 信息科学与工程学院, 山东 日照 27682602

摘要：支撑图(spanner)在无线(自主、传感器)网络拓扑控制中起着重要作用,不但能保证最终的拓扑图链路减少,保持连通性,而且保证任意一对通信节点之间所需费用是最少可能费用的常数因子倍.针对无线网络拓扑控制问题,大量支撑图构造算法被提出,以尽可能高效地满足网络设计需要的各种拓扑特性,如局部性、稀疏性、小权值、有界度及容错性等.对支撑图的研究成果进行了详细讨论,依据支撑图的定义和不同的分类原则给出了支撑图分类,分析了各种支撑图的典型集中式和局部算法、满足某一或多个拓扑特性的算法,并提出了需要进一步研究的问题.与无线网络中新出现、更实用的模型结合,寻找更简单、性能更好的算法将是未来支撑图构造算法的主要研究方向.

关键词：无线网络;拓扑控制;支撑图;支撑比

基金资助：国家自然科学基金(61373027); 山东省自然科学基金(ZR2012FM023); 山东省高校科技计划(J14LN38); 曲阜师范大学科技计划(xkj201312)