NDLI: Exploiting multi-interface networks: Connectivity and Cheapest Paths

Content Provider	Springer Nature Link
Author	Kosowski, Adrian Navarra, Alfredo Pitti, Cristina M.
Copyright Year	2009
Abstract	Let G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at least one active interface. In general, every node holds a subset of all the possible k interfaces. Such networks are known as multi-interface networks. In this setting, we study two basic problems: Connectivity and Cheapest Path. The Connectivity problem corresponds to the well-known Minimum Spanning Tree problem in graph theory. In practice, we need to cover a subgraph of G of minimum cost which contains a spanning tree of G. The problem turns out to be APX-hard in general and for many restricted graph classes, however it is possible to provide approximation algorithms: a 2-approximation in general and a $$(2-\frac{1}{ k})$$ -approximation for the unit cost interface case, i.e. when the cost of activating an interface is unitary for any interface. We also consider the problem in special graph classes, such as graphs of bounded degree, planar graphs, graphs of bounded treewidth, complete graphs. The Cheapest Path problem corresponds to the well-known Shortest Path problem in graph theory. In the multi-interface setting this problem is still polynomially solvable, and we point out a simple Dijsktra-based algorithm with $$O(k\|E\|+k\|V\|\log (k+\|V\|))$$ runtime in general and O(k(\|E\| + \|V\|)) runtime for the unit cost interface case.
Starting Page	1063
Ending Page	1073
Page Count	11
File Format	PDF
ISSN	10220038
Journal	Wireless Networks
Volume Number	16
Issue Number	4
e-ISSN	15728196
Language	English
Publisher	Springer US
Publisher Date	2009-05-21
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Energy saving Wireless network Multi-interface network Business Information Systems Electrical Engineering Computer Communication Networks Communications Engineering, Networks
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Information Systems Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Network coding for multiple unicast sessions in multi-channel/interface wireless networks

Design and implementation of multicasting for multi-channel multi-interface wireless mesh networks

Weighted relay node placement for wireless sensor network connectivity

Connectivity properties of large-scale sensor networks

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

Single-path routing for life time maximization in multi-hop wireless networks

Impact of Interference on the Wireless Ad-Hoc Networks Capacity and Topology

Improving IEEE 802.11 power saving mechanism

Path diversified multi-QoS optimization in multi-channel wireless mesh networks

Exploiting multi-interface networks: Connectivity and Cheapest Paths

Similar Documents

Network coding for multiple unicast sessions in multi-channel/interface wireless networks

Design and implementation of multicasting for multi-channel multi-interface wireless mesh networks

Weighted relay node placement for wireless sensor network connectivity

Connectivity properties of large-scale sensor networks

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

Single-path routing for life time maximization in multi-hop wireless networks

Impact of Interference on the Wireless Ad-Hoc Networks Capacity and Topology

Improving IEEE 802.11 power saving mechanism

Path diversified multi-QoS optimization in multi-channel wireless mesh networks

Exploiting multi-interface networks: Connectivity and Cheapest Paths