Spanning Tree Objective Functions and Algorithms for Wireless Networks

Morgan, Mike J and Grout, Vic (2006) Spanning Tree Objective Functions and Algorithms for Wireless Networks. In: UNSPECIFIED.


Download (384kB) | Preview


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.

Item Type: Conference or Workshop Item
Additional Information: 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 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 By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
Keywords: Wireless network optimization, Spanning trees, Objective functions, Algorithms, Heuristics
Divisions: ?? GlyndwrUniversity ??
Depositing User: ULCC Admin
Date Deposited: 05 Oct 2011 09:14
Last Modified: 11 Dec 2017 20:06

Actions (login required)

Edit Item Edit Item