  


The optimal design of lowlatency virtual backbones
Hamidreza Validi (hamidreza.validiokstate.edu) Abstract: Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for the wireless network) which can be seen as a connected dominating set (CDS) of the associated graph. Ideally, these communication paths should be short, leading to the notion of a latencyconstrained CDS. In this paper, we point out several shortcomings of a previously studied formalization of a latencyconstrained CDS and propose an alternative one. We introduce an integer programming formulation for the problem that has a variable for each node and imposes the latency constraints via an exponential number of cutlike inequalities. Two nice properties of this formulation are that: (1) it applies when distances are hopbased and also when they are weighted; and (2) it easily generalizes to ensure fault tolerance. We provide a branchandcut implementation of this formulation and compare it with a new polynomialsize formulation. Computational experiments demonstrate the superiority of the cutlike formulation. We also study related questions from computational complexity such as approximation hardness and answer an open problem regarding the fault diameter of graphs. Keywords: connected dominating set; strongly connected dominating set; latency; delay; hop constraint; $k$club; lengthbounded cut; wireless networks; faulttolerant; integer programming; Category 1: Network Optimization Category 2: Combinatorial Optimization (Branch and Cut Algorithms ) Category 3: Integer Programming Citation: Accepted at INFORMS Journal on Computing Download: [PDF] Entry Submitted: 05/24/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  