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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 02,2014
  • Revised:June 29,2014
  • Adopted:
  • Online: February 06,2015
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063