Date Added: Dec 2011
The relay placement problem has been studied extensively in wireless networks. Existing work typically focuses on connectivity to prolong the network time or to achieve fault-tolerance. In contrast, the authors tackle the problem with the goal of achieving bandwidth sufficiency when real-time multimedia streams need to be sent to the sink. They consider the critical condition of heterogeneous link capacity and transmission range. Besides, they consider the relay placement and routing jointly because routing decides the path on which a stream traverses; and the bandwidth sufficiency depends on both supply (the link capacity) and demand (which streams use the link given the routing paths). They formulate the problem as a new variant of the Steiner tree problem called the heterogeneous bandwidth Steiner routing problem.