Please use this identifier to cite or link to this item:
Title: Optimizing Link Assignment to Enhance Service in Probabilistic Network
Authors: Berchmans, FJ
Hon, WK
Huang, ACY
Liu, CS
Lo, E 
Yau, D
Keywords: Client-server systems
Computational complexity
Graph theory
Greedy algorithms
Integer programming
Learning (artificial intelligence)
Wireless channels
Issue Date: 2010
Publisher: IEEE
Source: 2010 7th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks (SECON), 21-25 June 2010, Boston, MA, p. 1-9 How to cite?
Abstract: We consider service enhancement in a wireless environment in which clients try to obtain service from a set of servers. Each client desires a minimum overall service success probability, which is achieved by establishing multiple independent connections with multiple servers. Given the service success probability of each potential client-server connection, our problem is to assign the connections such that the number of satisfied clients (whose overall service success probability is met) is maximized subject to server capacity constraints. In this paper, we make minor adaptations to the well-known notion of probabilistic network from the machine learning community and use it as our communication model. We then formally define the above optimization problem as the link assignment for successful service problem (LASS). While LASS can be reduced to the maximum matching problem in the deterministic case (where the success probabilities of each edge is 1), we show that in the probabilistic case it is NP-hard (and MaxSNP-hard). An equivalent integer programming formulation for LASS is obtained so that for small input size, the problem may be efficiently solved by the standard IP solver in practice. To tackle large input size, various heuristics are designed. Furthermore, in the special case where the underlying network graph is a tree (which is common in many real-life settings), we show that LASS can be solved in linear time based on a simple greedy algorithm. Experimental evaluations are performed and the results demonstrate the practicality of the algorithms and the heuristics.
ISBN: 978-1-4244-7150-8
978-1-4244-7151-5 (E-ISBN)
DOI: 10.1109/SECON.2010.5508251
Appears in Collections:Conference Paper

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Jan 16, 2019

Page view(s)

Last Week
Last month
Citations as of Jan 14, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.