无线网络拓扑控制中支撑图构造算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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


Spanner Construction for Topology Control in Wireless Networks
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Spanners play important role in topology control of wireless (ad hoc, sensor) networks since they not only decrease the number of links and preserve connectivity of the final topology graph but also ensure that the cost between any pair of communication nodes is within some constant factor from the shortest possible cost. For topology control of wireless networks, a large number of spanner construction algorithms have been presented to efficiently satisfy various kinds of topological characteristics for the network design requests, such as locality, sparseness, lightness, small maximum degree, and fault-tolerance. In this comprehensive survey, the taxonomy for spanners is given according to the definition and different types of classification methods. For spanner construction, the typical centralized and localized algorithms and algorithms possessing one or more topological characteristics are analyzed, and some open problems worth of future research are proposed. The further work is to find simpler algorithms with better performance combining with novel and more practical models in wireless networks.

    参考文献
    相似文献
    引证文献
引用本文

张秀娟,禹继国.无线网络拓扑控制中支撑图构造算法.软件学报,2015,26(4):904-926

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2014-04-02
  • 最后修改日期:2014-06-29
  • 录用日期:
  • 在线发布日期: 2015-02-06
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号