In the construction of a communication network, the length of the network is an important but not unique factor determining the cost of the network. Among many possible network models, Gilbert proposed a flow-dependent model in which flow demands are assigned between each pair of points in a given point set A, and the cost per unit length of a link in the network is a function of the flow through the link. In this paper we first investigate the properties of this Gilbert model: the concavity of the cost function, decomposition, local minimality, the number of Steiner points and the maximum degree of Steiner points. Then we propose three heuristics for constructing minimum cost Gilbert networks. Two of them come from the fact that generally a minimum cost Gilbert network stands between two extremes: the complete network G(A) on A and the edge-weighted Steiner minimal tree W(A) on A. The first heuristic starts with $G(A)$ and reduces the cost by splitting angles; the second one starts with both G(A) and W(A), and reduces the cost by selecting low cost paths. As a generalisation of the second heuristic, the third heuristic constructs a new Gilbert network of less cost by hybridising known Gilbert networks. Finally we discuss some considerations in practical applications.

Date Published: 29 August 2002
PDF: 9 pages
Proc. SPIE 4909, Network Design and Management, (29 August 2002); doi: 10.1117/12.481078

Published in SPIE Proceedings Vol. 4909:
Network Design and Management
Qian Mao; Shoa-Kai Liu; Kwok-wai Cheung, Editor(s)