Comments

Copyright © 2006 IEEE. This is a reprint of a paper presented to the 2006 IEEE Sarnoff Symposium (Sarnoff 2006) in March 2006. It was published by the Institute of Electrical and Electronics Engineers (IEEE), and details of the published paper are available at http://ieeexplore.ieee.org This material is posted here with permission of the IEEE and the author. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the products or services of Glyndwr University Wrexham. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Abstract

This paper considers various forms of objective function that may be applied in the calculation of spanning trees in different network situations. Conventional link and path cost approaches are compared to those based on switch or bridge costs more appropriate for wireless applications. Variant objectives are formulated and compared. Although efficient exact algorithmic approaches exist only for the link cost objectives, reasonable approximations for the switch/bridge equivalents are to be found with simple greedy heuristics and better results still through various forms of iterated local search such as tabu search and simulated annealing.

Disciplines

Computer and Systems Architecture | Digital Communications and Networking | Hardware Systems | Systems and Communications

Recommended Citation

Morgan, M. & Grout, V. (2006), ‘Spanning Tree Objective Functions and Algorithms for Wireless Networks’. [Paper presented to the 2006 IEEE Sarnoff Symposium (Sarnoff 2006), 27-28 March 2006]. Princeton, New Jersey, USA: IEEE