Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/8643
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)
Probability
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.
URI: http://hdl.handle.net/10397/8643
ISBN: 978-1-4244-7150-8
978-1-4244-7151-5 (E-ISBN)
DOI: 10.1109/SECON.2010.5508251
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Oct 17, 2017

Page view(s)

45
Last Week
2
Last month
Checked on Oct 23, 2017

Google ScholarTM

Check

Altmetric



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